臺灣博碩士論文加值系統

於本篇論文中，我們為降低無線感測網路中端點對端點之封包到達延遲以及能量消耗，實現出一個新的媒體存取控制協定(MAC)，其稱為分散式排程媒體存取控制協定(DS-MAC)。感測節點之狀態常常會來回切換於動作與睡眠狀態以減少能源上的損失，所以於傳輸過程中當封包需要經歷較多跳點(Hop)或是遇到網路交流量處於壅塞之情況時，其端點對端點的封包延遲將會升高許多。類似於廣為人知的S-MAC，DS-MAC於每個循環(Cycle)中有三個週期：Sync period、Control period與Data/Sleep period，而Data/Sleep period中又劃分為多個mini-frame，傳送端與接收端會在mini-frame中作傳輸或接收資料。於Sync period裡，每個感測節點須週期性發送或接收Sync封包，就是為了於無線感測網路中之每個感測節點都能同步化。於Control period中，每個節點會藉著CSMA/CA機制，來競爭通道使用權，並使用RTS/CTS封包中的mini-frame欄位與排程表(Scheduling table)來建立與記錄欲傳送的封包之排程，mini-frame欄位主要目的為讓接收節點依據傳送節點所指定的mini-frame來與傳送端作資料傳輸，傳送端也會根據接收端所指定的mini-frame來更新排程；每個節點會去接收不是給自己之RTS/CTS封包是為了能了解鄰近節點使用mini-frame之情況如何，而所有感測節點之排程都以分散的方式建立的。而於Data/Sleep period中，每個節點只會依照各自之封包排程表中所指定的mini-frame，來發送或接收DATA封包，這樣一來，各個節點可於一個循環中服務多個DATA封包，即為DS-MAC其最主要的優點。最後，我們將DS-MAC在封包到達延遲與總耗能中，與adaptive S-MAC協定做了比較。從模擬結果中可看出DS-MAC有更好的效能表現，尤其在流量負載較大的情況之下更為突出。

In this thesis, we implement a new medium access control protocol, named DS-MAC (Distributed-Scheduling MAC) for wireless sensor networks to lower end-to-end packet delay and energy consumption. Usually, sensor nodes switch between sleep and active modes to decrease energy loss. As a result, the end-to-end delays of packets that travel many hops or is under congested traffic are excessively large. Similar to the well-known S-MAC protocol, the DS-MAC protocol has three periods in each cycle: Sync period, Control period, and Data/Sleep period. We divide Data/Sleep period into multiple mini-frames. Sender and receiver execute DATA/ACK handshake in the mini-frames. In Sync period, each node broadcast or receive Sync packets to maintain a synchronized network. In Control period, every node contends for the communication channel by utilising the CSMA/CA mechanism. We use the scheduling table and the mini-frame field in one RTS/CTS packet to establish and record the packet schedules. The mini-frame field in RTS/CTS is that receivers execute DATA/ACK handshake with senders by being based on the mini-frame which is given by senders. Senders update the packet schedules according as the mini-frame is given by receivers. Then, each node receives RTS/CTS not for myself in order that per node can know the situations of using mini-frames for neighbor nodes. The packet schedules of all nodes are established in a distributed manner. In Data/Sleep period, each sensor node merely follows the assigned mini-frame in its own scheduling table to send or receive a DATA packet. The major benefit of DS-MAC is that a node can serve multiple packets in one cycle. We have compared the DS-MAC protocol with the adaptive S-MAC protocol in terms of end-to-end packet delay and energy consumption. The simulation results show that the DS-MAC protocol has great performance, especially under high traffic load.

目錄
中文摘要 ............................................................................................................................. I
英文摘要 .......................................................................................................................... III
目錄 .................................................................................................................................... V
圖目錄 ............................................................................................................................. VII
表目錄 .............................................................................................................................. IX
第一章 緒論....................................................................................................................... 1
1.1 序言……................................................................................................................ 1
1.2 研究動機與目的.................................................................................................. 3
1.3 論文概述.............................................................................................................. 3
第二章 相關背景與研究................................................................................................... 5
2.1 無線感測網路簡述….......................................................................................... 5
2.2 IEEE 802.11 MAC簡介 ...................................................................................... 11
2.2.1 載波偵測多重存取/碰撞避免(CSMA/CA)機制 ................................... 12
2.2.2 分散式協調功能(DCF)之簡介 ............................................................... 13
2.2.3 二元指數後退演算法機制(BEB)之簡介 ............................................... 16
2.2.4四向交握機制(4-way handshake) ................................................... 17
2.2.5 網路配置向量(Network Allocate Vector) ................................................ 19
2.3 S-MAC簡介 ........................................................................................................ 20
第三章 DS-MAC簡介...................................................................................................... 29
3.1 起因 .............................................................................................................. 29
3.2排程上存取控制之概述 .................................................................................. 30
3.3排程上之協調方式 .................................................................................. 32
3.4 DS-MAC封包排程協調的state machine ......................................................... 37
3.5 New Callback Mechanism ................................................................................41
3.6 減少碰撞發生頻率之方法 ................................................................................ 45
第四章 模擬結果與分析................................................................................................. 50
4.1 模擬環境及參數設定 ........................................................................................ 50
4.2直線型雙向網路拓樸 ........................................................................................ 52
4.3十字型雙向網路拓樸 ........................................................................................ 54
4.4 3×3棋盤式網路拓樸 ........................................................................................ 57
4.5 5×5棋盤式網路拓樸 ........................................................................................ 60
第五章結論與未來展望................................................................................................. 63
參考文獻........................................................................................................................... 64


圖目錄
圖2.1無線感測網路架構圖................................................................................................. 6
圖2.2(a) 傳送資料封包前，利用RTS/CTS機制來作交握.............................................. 9
圖2.2(b) 傳送資料封包後，利用ACK封包來回覆傳送成功......................................... 9
圖2.3 封包發生示意圖..................................................................................................... 10
圖2.4 IEEE 802.11協調機制關係示意圖........................................................................ 11
圖2.5訊框間隔之間的關係示意圖(Reference from IEEE 802.11 standard).................. 14
圖2.6 CSMA/CA之運作示意圖........................................................................................ 14
圖2.7二元競爭視窗示意圖.............................................................................................. 16
圖2.8四向交握機制示意圖............................................................................................... 17
圖2.9隱藏節點問題示意圖............................................................................................... 18
圖2.10網路配置向量之範例圖......................................................................................... 19
圖2.11週期性的監聽和睡眠............................................................................................. 20
圖2.12監聽週期、同步週期與睡眠週期架構圖............................................................... 21
圖2.13同步週期訊框示意圖............................................................................................. 21
圖2.14偷聽情形之示意圖................................................................................................. 22
圖2.15 S-MAC的Message Passing ................................................................................... 23
圖2.16原始S-MAC的架構流程圖................................................................................... 24
圖2.17原始S-MAC的傳輸樣貌....................................................................................... 25
圖2.18 S-MAC with Adaptive Listening的架構流程圖.................................................... 26
圖2.19 S-MAC with Adaptive Listening傳輸過程之示意圖............................................ 27
圖3.1 A cycle of DS-MAC.................................................................................................. 31
圖3.2 DS-MAC概念圖...................................................................................................... 31
圖3.3簡單式直線拓樸之範例圖....................................................................................... 33
圖3.4封包排程協調之示意圖........................................................................................... 34
圖3.5針對圖3.4中每節點的封包排程表之示意圖......................................................... 35
圖3.6 DS-MAC封包協調排程的state machine................................................................ 37
圖3.7 MAC層與Queue層的callback機制之關聯性....................................................... 39
圖3.8(a) callback機制之執行(1)........................................................................................ 43
圖3.8(b) callback機制之執行(2)....................................................................................... 44
圖3.9(a) 發生碰撞的情況1之示意圖.............................................................................. 45
圖3.9(b) 針對碰撞情況1之避免方式示意圖.................................................................. 46
圖3.10(a) 碰撞發生的情況2............................................................................................. 46
圖3.10(b) 針對碰撞情況2之解決方式示意圖................................................................ 47
圖3.11節點間作DATA/ACK handshake時所產生碰撞之示意圖.................................. 48
圖4.1感測節點之無線電傳送與接收範圍....................................................................... 50
圖4.2直線型雙向網路拓樸樣式圖................................................................................... 52
圖4.3(a) 雙向拓樸式平均封包延遲比較圖..................................................................... 52
圖4.3(b) 雙向拓樸式平均能耗比較圖............................................................................. 53
圖4.4十字型雙向網路拓樸之示意圖............................................................................... 54
圖4.5(a) 十字型式平均封包延遲比較圖......................................................................... 55
圖4.5(b) 十字型式平均能耗比較圖................................................................................. 56
圖4.6 3×3九宮格式網路拓樸之示意圖............................................................................ 57
圖4.7(a) 3×3棋盤式平均封包延遲比較圖....................................................................... 58
圖4.7(b) 3×3棋盤式平均能耗比較圖............................................................................... 59
圖4.8 5×5九宮格式網路拓樸之示意圖............................................................................ 60
圖4.9(a) 5×5棋盤式平均封包到達延遲比較圖............................................................... 61
圖4.9(b) 5×5棋盤式平均能耗比較圖............................................................................... 62




表目錄
表3.1(a) RTS封包格式.................................................................................................... 32
表3.1(b) CTS封包格式.................................................................................................... 32
表3.2 Scheduling table之範例圖....................................................................................... 33
表4.1細項參數設定........................................................................................................... 51

[1] Smart Dust, http://robotics.eecs.berkeley.edu/~pister/SmartDust/
[2]Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci,“A Survey on Sensor Networks,”IEEE Communications Magazine, vol. 40,no. 8,pp. 102 – 114, Aug. 2002.
[3]IEEE Std 802.11-2007, “IEEE Standard for Information Technology Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,” June 12 2007.
[4]Wei Ye, Heidemann J. and Estrin D.,“An Energy-Efficient MAC Protocol for Wireless Sensor Networks,” IEEE INFOCOM’02, June 2002.
[5]Wei Ye, Heidemann, J. and Estrin, D., “Medium Access Control with Coordinated Adaptive Sleeping for Wireless Sensor Networks, ” IEEE/ACM Trans. Networking, vol. 12, no. 3, pp. 493–506, 2004.
[6]M. Stemm and R. H. Katz, “Measuring and Reducing Energy Consumption of Network Interfaces in Hand-Held Devices, ” IEICE Transactions, vol. E80-B, no. 8, pp. 1125-1131, Aug. 1997.
[7]IEEE Std 802.15.4-2006, “IEEE Standard for Information Technology Telecommunications and Information Exchange Between Systems- Local and Metropolitan Area Networks- Specific Requirements Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (WPANs), ” 2006.
[8]Zigbee Standards Organization, “ZIGBEE SPECIFICATION V1.0 r13,”2006.
[9]Qian Hu and Zhenzhou Tang, “An Improved Adaptive MAC Protocol for Wireless Sensor Networks Based on Cross-layer Architecture, ” Wireless Communications & Signal Processing, 2009. WCSP 2009., pp. 1-5, November 2009.
[10]Peng Lin, Chunming Qiao and Xin Wang, “Medium Access Control With A Dynamic Duty Cycle For Sensor Networks,” Wireless Communications and Networking Conference, 2004. WCNC. 2004 IEEE, Vol. 3, pp. 1534-1539, March 2004.
[11]Shih-Hsien Yang, Hung-Wei Tseng, Eric Hsiao-Kuang Wu and Gen-Huey Chen, “Utilization Based Duty Cycle Tuning MAC Protocol for Wireless Sensor Networks,” Global Telecommunications Conf. , 2005. GLOBECOM '05. IEEE, vol. 6, pp. 3258-3262, 2005.
[12]Tijs van Dam and Koen Langendoen, “An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks,” in SenSys’03, pp. 171-180, 2003.
[13]Changsu Suh, Deepesh Man Shrestha and Young-Bae Ko, “An Energy-Efficient MAC Protocol for Delay-Sensitive Wireless Sensor Networks,” IFIP International Federation for Information Processing 2006, EUC Workshops 2006, LNCS 4097, pp. 445–454, 2006.
[14]Cristina Cano, Boris Bellalta, Anna Sfairopoulou and Jaume Barcel´o, “A low power listening MAC with scheduled wake up after transmissions for WSNs,” IEEE Communications Letters, vol. 13, no. 4, April 2009.
[15]Bashir Yahya and Jalel Ben-Othman, “A Scalable and Energy-Efficient Hybrid-Based MAC Protocol for Wireless Sensor Networks, ” PM2HW2N’08, pp. 67-71, 2008.
[16]Texas Instruments, CC2530 Data Sheet, http://www.ti.com/.
[17] Pei Huang, Li Xiao, Soroor Soltani , Matt W. Mutka and Ning Xi, “The Evolution of MAC Protocols in Wireless Sensor Networks：A Survey”, IEEE Communications Surveys & Tutorials, vol.15, No.1, First Quarter 2013.
[18] Kwuang-Jyz Liu, “Simulation Study on Wireless Sensor Network”, Department of Electrical Engineering, National Chi Nan University, 2013.