臺灣博碩士論文加值系統

隨網際網路的普及與相關技術日新月異，對於短距離的無線通訊需求也與日劇增，而IEEE 802.15.4 無線個人區域網路 (WPAN) 就是其中一種應用於短距離傳輸的技術。IEEE802.15.4 是由許多感測節點所組成，而感測節點因其運作環境的特性之故，多半是以電池供應其電源，故IEEE 802.15.4 技術的設計便以符合低功率、低耗電量、簡單、便宜以及長時間運作為考量。因此，IEEE 802.15.4 使用盲目型隨機後退 (blind random backoff) 競爭機制以達到省電的目的，但這項機制卻無法避免隱藏節點 (hidden node) 問題。在先前的研究中發現，在一個節點隨機分佈的網路裡，節點間發生隱藏節點問題的機率高達到41%，當環境中伴隨著隱藏節點碰撞鏈(hidden node collision chain)，不僅會對網路造成吞吐量下降、延遲傳送的情況、重複傳送資料外，亦會造成大量的能量耗損，因而降低網路的使用壽命。
由於以往避免隱藏節點的方式，如RTS/CTS (request to send/clear to send) 機制並不適用於IEEE 802.15.4 標準;為了不增加網路額外的負擔，本論文提出以分群策略為基礎的節點加入與群組機制來解決在IEEE 802.15.4 標準上的隱藏節點問題；有鑑於處理隱藏節點碰撞問題，事前預防勝過事後補救，故在節點一開始加入時便啟動執行本機制，直接避免隱藏節點碰撞問題影響網路效能。此機制將網路的成員分成若干群，每個群組內的節點互相不為隱藏節點，此外並依照群組內的節點個數以及群組內節點競爭程度將時間訊框分配與各群組合適的頻寬。在收集隱蔽節點關係資料方面，此論文提出了電力節省導向的方式來收集資料，並有效解決當新節點加入時，不需重新收集資料而只需對和新節點有相對關係的節點做資料更新，減少多餘訊息和電量功率消耗；並證明依照各群整體網路負載均等和先後加入的因素，在不更改已存在節點所在各群組的前提下，最多可分成九群。經由模擬的方式，將提出的方法與IEEE 802.15.4 標準以及先前的分群策略比較，模擬結果顯示本論文的方法有較佳的結果。

IEEE 802.15.4 wireless personal area network (WPAN) standard is an advanced wireless communication technology, which is designed to provide short-distance communication services. Due to most of IEEE 802.15.4 nodes relying on battery to operate IEEE 802.15.4 was designed with fetures of ultra low power consumption, low computation power and low hardware cost. To save power resource, IEEE 802.15.4 adopts the blind random backoff contention mechanism, which turns off the transceiver of device when a device does not have data to transmit. However, such design leads the hidden node problem to become inevitable. Previous research has shown that nodes in a random network have 41% probability to incur hidden node situation with the other nodes. Moreover, the hidden node collision chain problem may further downgrade the network throughput, increase transmission delay, retransmit data, and therefore cause more energy loss.
Because the conventional two way handshaking mechanism (such as request-to-send/clear-to-send (RTS/CTS)) is not suitable for IEEE 802.15.4 network, this thesis proposes an efficient grouping strategy, which is performed during node joining, to completely avoid the hidden node problem. Members of a group are non-hidden nodes to each other. In the presupposition that the new joining node does not affect the existent groups, this thesis proves that the maximal number of groups in a network is 9. Based on the grouping result, the proposed scheme partitions the time frame into several subperiods, one for each group. The length of subframe for a group is proportional to its group size. Simulation results illustrate that the proposed scheme can not only avoid hidden node problem but also outperform the IEEE 802.15.4 standard and pervious grouping strategy schemes.

中文摘要 i
ABSTRACT iii
TABLE OF CONTEXTS v
LIST OF FIGURES vii
LIST OF TABLE viii
1.Introduction 1
1-1. Preface 1
1-2. Problem Description 1
1-3. Goal of This Thesis 3
1-4. Thesis Organization 4
2.Related Works 5
2-1. The Operation of IEEE 802.15.4 5
2-2. Previous Researches 9
3.Node Joining and Grouping Scheme 12
3-1. Hidden Node Relationship Collection 12
3-2. Node Grouping 19
3-3. Access Period Allocation 26
3-4. Group Results and Notification 28
4.Mathematic Analysis 31
5.Simulation Results and Analysis 40
5-1. Simulation Model 40
5-2. Simulation Results 41
6.Methods of Hidden Node Information Collection 45
6-1. The Total Number of Transmission and Reception Packet 45
6-2. Re-executing While a New Node Coming and Executing Complexity 46
6-3. Reliability 47
7.Conclusions 50
References 51

[1]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
[2]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.
[3]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.
[4]IEEE 802.11 Working Group, “Information Technology Telecommunications and Information Exchange between Systems-Local and Metropolitan Area Network-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.
[5]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.
[6]Z. J. Haas and J. Deng, "Dual busy tone multiple access (DBTMA) - A multiple access control scheme for ad hoc networks," IEEE Transactions on Communications, vol. 50, pp. 975-985, 2002.
[7]P. Karn, "MACA - A New Channel Access Method for Packet Radio," in Proceedings of the ARRL/CRRL Amateur Radio 9th Computer Networking Conference, 1990.
[8]E. S. Jung and N. H. Vaidya, ”A power control MAC protocol for ad hoc networks,” in Proceedings of ACM MOBICOM, pp. 36-47, 2002
[9]Sheth and R. Han,”SHUSH: reactive transmit power control for wireless MAC protocols,” in Proceedings of WICON, pp. 18-25, 10-14 Jul. 2005.
[10]J. Zhu, X. Guo, L. L. Yang, and W. Steven, ”A single-channel solution for transmission power control in wireless ad hoc networks,” in Proceedings of ACM MOBIHOC, pp. 210-221, 2004
[11]S. Zhang and S.J. Yoo, “Fast Recovery from Hidden Node Collision for IEEE 802.15.4 LR-WPANs,” in Proceedings of CIT, 2007
[12]A. Koubâa, R. Severino, M. Alves, and E. Tovar, H-NAMe: Specifying, implementing and testing a hidden-node avoidance mechanism for wireless sensor networks, Tech, Rep. HURRAY-TR-071113, Nov. 2007.
[13]C.H. Kwon, R.J. Tek, K.H. Kim and S.H. Yoo, “Dynamic Group Allocation Scheme for avoiding Hidden Node Problem in IEEE 802.15.4,” in Proceedings of ISCIT, 2009
[14]J.H. Lee, J.K. Choi, and S.J. Yoo, “Group Node Contention Algorithm for Avoiding Continuous Collisions in LR-WPAN,” in Proceedings of CIT, 2009
[15]M.C. Golumbic,” Algorithm graph theory and perfect graphs.” New York: Academic, 1980
[16]M.R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitrou,“The complexity of coloring circular arcs and chords,” in Proceedings of SIAM J. Alg. Disc. Meth. 1(2):216–227, Jun. 1980.
[17]H.W. Tseng, A.C. Pang, J.H. C, and C.F. Kuo, “An Adaptive Contention Control Strategy for IEEE 802.15.4-Based Wireless Sensor Networks”, IEEE Transactions on Vehicular Technology, vol. 58 pp. 5164-5173, May 2009.