新興的無線個人網路 (wireless personal area network, WPAN) 傳輸技術IEEE 802.15.4因其特性符合短距離、低傳輸速率以及低功率消耗的感測網路之需求，因此成為無線感測網路 (wireless sensor network, WSN) 的主要建構方案之ㄧ。標準的IEEE 802.15.4傳送機制係採用盲目型隨機倒退 (random back-off) 競爭機制以減少電源消耗，然而這項設計並無法滿足在隱藏節點 (hidden-node) 環境中傳輸效能上的需求。尤其是此環境所伴隨而來的隱藏節點碰撞鏈 (hidden-node collision chain) 的情況將導致無法預測的網路效能耗損。遵照此倒退競爭機制，網路裝置之間激烈的競爭過程同樣地會使裝置無法在非隱藏節點環境之中獲得理想的傳輸效能。再者，在集中式管理拓撲(star topology) 下，任兩裝置之間的訊框 (frame) 傳輸皆須藉由協調者 (coordinator) 代為傳遞而加倍消耗網路資源；而在分散式管理拓撲(peer-to-peer topology) 下，任兩訊號範圍內的裝置雖然可以點對點直接傳送訊框，但接收端因為無法預測傳送端何時會提出傳送請求，而得花費許多電力與許久時間在等待傳送端提出請求。上述這些問題都將使得每一筆成功傳送的訊框遭受延遲以及消耗可觀的電力。因此本論文提出一系列新穎的策略以改善上述問題，其中包括：分群 (grouping) 策略、載波多重存取暨碰撞凍結協定 (carrier sense multiple access with collision freeze, CSMA/CF)、晝夜存取 (day and night access, DNA) 機制、以及輪聽策略 (rotational listening strategy, RLS)。分群策略係以犧牲少許網路存取時間而營造一個非隱藏節點的環境並提供顯著的傳輸效能。載波多重存取暨碰撞凍結協定則藉由動態分配專屬的傳輸時間給遭遇隱藏節點碰撞(hidden-node collision) 的裝置以達到減緩隱藏節點環境影響的功效。晝夜存取機制是一種可以改善無線個人網路中裝置間資料交換效能的方案。最後提出的輪聽策略係採用分時多重存取 (time division multiple access, TDMA) 機制與競爭機制兩者混合的概念以避免非隱藏節點環境下碰撞的發生而提供絕佳的傳輸效能。由效能分析與評估後的結果來看，本文所提出的方法策略將可明顯地改善效能、節省電力消耗、縮短存取時間花費並且提升傳輸的成功率。

The emerging IEEE 802.15.4 wireless personal area network (WPAN) is one of solutions for deploying wireless sensor networks (WSNs), wherein applications are restricted by low data rate, short transmission distance and low power consumption. The frame transmission mechanism of the IEEE 802.15.4 standard, which adopts the blind random back-off mechanism, was designed to minimize power consumption. However, it cannot provide satisfactory performance in a realistic hidden-node environment, as it may incur a hidden-node collision chain situation and unexpectedly limit the overall network capacity. Devices with the blind back-off mechanism also cannot obtain ideal transmission performance in a violent contention environment regardless of hidden-node situation. Moreover, transmissions among devices in the same WPAN cost double resources because the WPAN coordinator relays data in the star topology; or receiver would consume much power to wait sender to send a transmission request for the following data transmissions in the peer-to-peer topology. For each successful data transmission, any inefficient transmission mechanism will incur prolonged access delay and consume too much power. As a solution, we propose a series of novel strategies in this dissertation. Strategies include the grouping strategy, the carrier sense multiple access with collision freeze (CSMA/CF) protocol, the day and night access (DNA) scheme and the rotational listening strategy (RLS). The grouping strategy is designed to provide a non-hidden-node environment for devices to obtain notable transmission performance. The CSMA/CF protocol is proposed to alleviate influence of hidden-node situation by dynamically allotting a dedicated time slot for each node suffering from hidden-node collision. The DNA scheme is a novel solution to improve the efficiency of data exchange within a WPAN where data streams may be transmitted from source device to destination device directly or forwarded by the coordinator depending on the hidden-node relationship between sender and receiver. The RLS utilizes both time division multiple access (TDMA) scheme and contention scheme to avoid collisions in a non-hidden-node environment and provide high transmission performance. As confirmed by the results of analyses and performance evaluations, these proposed strategies can achieve significant performance improvement in terms of energy conservation, access delay reduction, and transmission reliability.

Contents:
1  Introduction	1
1.1  Preface	1
1.2  Research Motives	2
2  IEEE 802.15.4 Standard	4
2.1  The Operation of IEEE 802.15.4	4
2.2  Collision Chain Problem (CCP) in IEEE 802.15.4 WPAN	8
2.3  Inefficient Transmission in IEEE 802.15.4 WPAN	11
3  The Grouping Strategy	13
3.1  Purpose	13
3.2  Grouping Strategy	13
3.3  Mathematical Analysis	18
3.4  Simulation Results	21
3.5  Conclusion	24
4  Carrier Sense Multiple Access with Collision Freeze (CSMA/CF) Protocol  26
4.1  Purpose	26
4.2  CSMA/CF	26
4.3  Performance Analysis	34
4.4  Simulations	43
4.5  Conclusion	52
5  Day and Night Access (DNA) Scheme	53
5.1  Purpose	53
5.2  Day and Night Access (DNA) Scheme	53
5.3  Simulation Model and Results	59
5.4  Conclusion	61
6  Rotational Listening Strategy (RLS)	62
6.1  Purpose	62
6.2  Rotational Listening Strategy (RLS)	62
6.3  Performance Analysis	73
6.4  Simulation Model and Results	81
6.5  Conclusion	91
7  Conclusions and Future Works	92
7.1  Conclusions	92
7.2  Future Works	95
Appendix A  Adaptive Interleaving Access Scheme (IAS)	98
A.1  Purpose	98
A.2  The Interleaving Access Scheme (IAS)	98
A.3  Simulation Model and Results	101
A.4  Conclusion	105

List of Figures:
1.1  Last hop communication between nodes and the coordinator in a WPAN with multiple clusters.	2
2.1  Illustrating the superframe interval controlled by standard’s parameters BO and SO.	6
2.2  An example illustrating the collision chain problem (CCP).	10
2.3  Comparisons of derived goodputs of IEEE 802.15.4 protocol under hidden and non-hidden node environments.	10
3.1  Two possible collision cases in WPAN.	14
3.2  An example illustrates how the coordinator builds the hidden node graph.	15
3.3  The network topologies with different numbers of nodes N are considered for analyzing the maximal number of groups.	20
3.4  Comparisons of derived goodputs of three protocols under different environments.	23
3.5  Comparisons of the average battery lifetime of nodes with three protocols under different environments.	24
4 1  Frame format of the IEEE 802.15.4 MAC frame.	28
4.2  An example illustrating that one of the nodes (say node A) has been successfully recognized by the coordinator and is removed from the contention group using GTS.	29
4.3  An example illustrating how the collision chain is resolved smoothly by means of the collision resolving scheme (CRS).	30
4.4  Flowchart of the coordinator with CSMA/CF.	32
4.5  Flowchart of the node with CSMA/CF.	33
4.6  Statistical model of the proposed carrier sense multiple access with collision freeze (CSMA/CF).	35
4.7  Comparisons of goodputs between CSMA/CF and standard protocols under different settings of BO, frame length (L), and traffic load.	44
4.8  Comparisons of the channel utilization percentage between the proposed CSMA/CF and standard protocol under different settings of BO, frame length (L), and traffic load.	44
4 9  Comparisons of the average access delays derived from the CSMA/CF and legacy standard protocols under different settings of BO, frame length (L), and traffic load.	46
4.10  Comparisons of the power consumption of the CSMA/CF and standard protocols under different settings of BO, frame length (L), and traffic load.	48
4.11  Distributions of numbers of collided nodes in CC and HNC with different settings of BO, frame length (L), network size (M), and traffic load.	50
4.12  The average collision chain duration under different settings of BO, frame length (L), and traffic load.	51
5.1  Illustrating the direct and indirect links in WPAN where sink A receives data from source B and source D via direct and indirect links respectively.	54
5.2  Timing diagrams of establishing direct and indirect links in DNA scheme.	56
5.3 Performance Comparisons among DNA scheme, Standard-GTS and Standard-noGTS.	61
6.1	Examples of Node-2 transmitting/receiving data frames to/from coordinator in WPAN with RLS. (a) The success of twice CCAs at the first attempt. (b) The failure of twice CCAs at the first attempt. (c) Frame reception process of Node-2.	66
6.2	The flowchart of R-node updating CSSN when it receives the sequence control command.	69
6.3  The beacon frame format defined in RLS-enabled WPANs.	70
6.4  An example of illustrating the CSSN reassignment for load unbalanced situation.	72
6.1	Examples of Node-2 transmitting/receiving data frames to/from coordinator in WPAN with RLS. (a) The success of twice CCAs at the first attempt. (b) The failure of twice CCAs at the first attempt. (c) Frame reception process of Node-2.	66
6.2	The flowchart of R-node updating CSSN when it receives the sequence control command.	69
6.3  The beacon frame format defined in RLS-enabled WPANs.	70
6.4  An example of illustrating the CSSN reassignment for load unbalanced situation.	72
6.5  The M/M/K queueing model, in which the boundary is at Nx6.1	Examples of Node-2 transmitting/receiving data frames to/from coordinator in WPAN with RLS. (a) The success of twice CCAs at the first attempt. (b) The failure of twice CCAs at the first attempt. (c) Frame reception process of Node-2.	66
6.2	The flowchart of R-node updating CSSN when it receives the sequence control command.	69
6.3  The beacon frame format defined in RLS-enabled WPANs.	70
6.4  An example of illustrating the CSSN reassignment for load unbalanced situation.	72
6.5  The M/M/K queueing model, in which the boundary is at NxM frames in the system.	74
6.6  Comparisons of goodputs derived from RLS, RLS-analysis, and standard protocol under different network sizes (N), mean lengths (L) and network loads (NNL).	83
6.7  Comparisons of expected queue lengths derived from RLS, RLS-analysis, and standard protocol under different network sizes (N), mean lengths (L) and network loads (NNL).	84
6.8  Comparisons of the expected access delays of RLS, RLS-analysis, and the standard protocol under different network sizes (N), mean lengths (L) and network loads (NNL).	84
6.9  Comparisons of the collision probabilities of RLS and standard protocol under different network sizes (N), mean lengths (L) and network loads (NNL).	86
6.10  Comparisons of the active time percentages of RLS and the standard protocol under different network sizes (N), mean lengths (L) and network loads (NNL).	86
6.11  Comparisons of the average MAC access delays of RLS and the standard protocol under different network sizes (N), mean lengths (L) and network loads (NNL).	87
6.12	Comparisons of the derived goodputs of RLS and enhanced RLS in the coexistent environment under different network sizes (N), mean lengths (L) and NR-node ratios (NRR).	87
6.13  Comparisons of the average goodputs of R-nodes and NR-nodes in RLS and RLS-CE modes under different network sizes (N), mean lengths (L) and NR-node ratios (NRR).	89
6.14  Comparisons of the derived goodputs of RLS with/without the CSSN reassignment and the standard protocol under the balanced/unbalanced traffic load environments.	90
7.1  Comparisons among IEEE 802.15.4 and the proposed protocols.	94
7.2  Practicable combinations among the proposed strategies.	96
7.3  Comparisons of criteria among practicable combinations.	96
A.1  Illustrating superframe structure adjusted by proposed IAS with interleaving order (IO).	99
A.2  Comparisons of derived goodputs from standard protocol and IAS under different parameter settings.	102
A.3  Comparisons of derived average data renew intervals from standard protocol and IAS under different parameter settings.	102
A.4  Comparisons of derived average battery lifetimes of nodes from standard protocol and IAS under different parameter settings.	104
A.5  The most proper proportions of inactive period to active period (RIA) for different sensing frequencies and different BO values.	105

[1] B. Sinopoli, C. Sharp, L. Schenato, S. Schaffert and S. S. Sastry, “Distributed control applications within sensor networks,” in Proceed¬ings of IEEE Special Issue on Sensor Networks and Applications, vol. 91, no. 8, pp. 1235-1246, Aug. 2003.
[2] R. Szewczyk, E. Osterweil, J. Polastre, M. Hamilton, A. Mainwaring, and D. Estrin, “Habitat Monitoring With Sensor Networks,” in Communications of the ACM, vol. 47, no. 6, pp. 34-40, Jun. 2004.
[3] E. Hanada, Y. Hoshino, and T. Kudou, “Safe Introduction of In-hospital Wireless LAN,” in Proceedings of International Medical Informatics 2004 (Medinfo. 2004), pp. 1426-1429, Sep. 2004.
[4] J. H. Lee and H. Hashimoto, “Controlling Mobile Robots in Distributed Intelligent Sensor Network,” IEEE Transactions on Industrial Electronics, vol. 50, no. 5, pp. 890-902, Oct. 2001.
[5] S. Ray, D. Starobinski, A. Trachtenberg, and R. Ungrangsi, “Robust Location Detection with Sensor Networks,” IEEE Journal on Selected Areas in Communications, vol. 22, no. 6, pp. 1016-1025, Aug. 2004.
[6] IEEE 802 Working Group, “Standard for Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low Rate Wireless Personal Area Networks (LR-WPANs),” ANSI/IEEE 802.15.4, Sep. 2006.
[7] J. Mišić, C. J. Fung, and V. B. Mišić, “On Node Population in a Multi-Level 802.15.4 Sensor Network,” in Proceedings of IEEE GLOBECOM 2006, pp. 1-6, Nov. 2006.
[8] F. A. Tobagi and L. Kleinrock, “Packet Switching in Radio Channels: Part II-The Hidden Terminal Problem in Carrier Sense Multiple-Access and the Busy-Tone Solution,” IEEE Transactions on Communications, vol. 23, no. 12, pp. 1417-1433, Dec. 1975.
[9] Y. C. Tseng, S. Y. Ni, and E. Y. Shih, “Adaptive Approaches to Relieving Broadcast Storms in a Wireless Multihop Mobile Ad Hoc Network,” IEEE Transactions on Computers, vol. 52, no. 5, pp. 545-557, May 2003.
[10] IEEE 802.11 Working Group, “Information Technology Telecommunications and Information Exchange between Systems-Local and Metropolitan Area Networks-Specific Requirement. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,” ANSI/IEEE Std. 802.11b-1999/Cor 1-2001-7, Mar. 2007.
[11] S. T. Sheu, Y. Y. Shih and Y. C. Cheng, “Grouping Strategy for Solving Hidden Node Problem in IEEE 802.15.4 LR-WPAN”, in Proceedings of WICON, pp. 26-32, Jul. 2005.
[12] S. T. Sheu and Y. Y. Shih, “P-Frozen Contention Strategy (PFCS) for Solving Collision Chain Problem in IEEE 802.15.4 WPANs”, in Proceedings of IEEE VTC 2006 Spring, vol. 3, pp. 1323-1327, May 2006.
[13] S. T. Sheu, Y. Y. Shih and W. T. Lee, “Carrier Sense Multiple Access with Collision Freeze (CSMA/CF) Protocol for IEEE 802.15.4 WPANs,” IEEE Transactions on Vehicular Technology, Mar. 2009.
[14] S. T. Sheu, Y. Y. Shih and L. W. Chen, “Day and Night Access (DNA) Scheme for Low Power IEEE 802.15.4 WPANs”, in Proceedings of IEEE VTC 2006 Fall, Sep. 2006.
[15] S. T. Sheu and Y. Y. Shih, “A Collision-free Based Rotational Listening Strategy (RLS) for IEEE 802.15.4 WPAN”, in Proceedings of IEEE ICC 2007, Jun. 2007.
[16] W. L. Lee, A. Datta, and R. C. Oliver, “FlexiTP: “A Flexible-Schedule-Based TDMA Protocol for Fault-Tolerant and Energy-Efficient Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 6, Jun. 2008.
[17] J. Mišić, S. Shafi, and V. B. Mišić, “Avoiding the Bottlenecks in the MAC Layer in 802.15.4 Low Rate WPAN,” in Proceedings of Parallel and Distributed Systems, vol. 2, pp. 363-367, Jul. 2005.
[18] R. Iyer and L. Kleinrock, “QoS Control for Sensor Networks,” in Proceedings of IEEE ICC 2003, vol. 1, pp. 517–521, May 2003.
[19] Y. Sankarasubramaniam, O. B. Akan, and I. F. Akyildiz, “ESRT: Event to Sink Reliable Transport in Wireless Sensor Networks,” in Proceedings of 4th ACM MobiHoc, pp. 177–188, Jun. 2003.
[20] J. Mišić, S. Shafi, and V. B. Mišić, “Maintaining Reliability Through Activity Management in an 802.15.4 Sensor Cluster,” IEEE Transactions on Vehicular Technology, vol. 55, Issue 3, pp. 779-788, May 2006.
[21] K. Whitehouse, A. Woo, F. Jiang, J. Polastre, and D. Culler, “Exploiting the Capture Effect for Collision Detection and Recovery,” The Second IEEE Workshop on Embedded Networked Sensors 2005 (EmNetS-II 2005), pp.45-52, May 2005.
[22] A. C. Pang and H. W. Tseng, “Dynamic Backoff for Wireless Personal Networks,” in Proceedings of IEEE Globecom 2004, vol. 3, pp. 1580-1584, Dec. 2004.
[23] S. Srirangarajan, A. H. Tewfik, and Z. Q. Luo, “Distributed sensor network localization using SOCP relaxation,” IEEE Transactions on Wireless Communications, vol. 7, no. 12, pp. 4886-4895, Dec. 2008.
[24] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company, Jun. 1979.
[25] Data Sheet for 8-bit Microcontroller with 128K Bytes In-System Programmable Flash, available online at http://www.atmel.com/dyn/resources/prod_documents /doc2467.pdf.
[26] Data Sheet for CC2420 2.4GHz IEEE 802.15.4/Zigbee RF Transceiver, available online at http://www.chipcon.com/files/CC2420_Data_Sheet_1_4.pdf.
[27] Data Sheet for UZ2400 Low Power 2.4GHz Transceiver for IEEE 802.15.4 Standard, available online at http://www.ubec.com.tw/product/downfiles/ uz2400/DS-2400-02_v1%200_RN.pdf.
[28] D. Gross and Carl M. Harris, “Fundamentals of Queueing Theory 3rd edition,” John Wiley & Sons, 1997.
[29] Bluetooth special interest group “Bluetooth Core Specification Addendum 1,” Jun. 2008.
[30] ZigBee Alliance, “ZigBee Specification r17,” ZigBee Document 053474r17, Oct. 2007.
[31] S. Zhang and S. J. Yoo, “Fast Recovery from Hidden Node Collision for IEEE 802.15.4 LRWPANs,” in Proceedings of IEEE CIT 2007, pp. 393-398, Oct. 2007.