臺灣博碩士論文加值系統

無線感測網路 (wireless sensor network) 是一種新型態、具有特殊用途的隨意網路 (ad hoc network)，在不同領域上有許多的應用。因為不便於替感測節點充電或更換電池，在應用上如何節省節點電力，將是無線感測網路中一個重要的議題。為了降低感測節點的電力消耗，可設計新的通訊協定以減少資料的傳輸和計算，並讓節點有較長的睡眠時間。本研究將替無線感測網路設計新的集中式省電分時多工 (Time Division Multiple Access, TDMA) 媒體存取控制 (Medium Access Control, MAC) 協定，透過各節點間適當的時槽分配，減少封包的碰撞、idle listening、overhearing以及協定的control overhead，並降低封包傳輸的延遲時間，且我們提出的集中式TDMA MAC協定，也具備有效處理拓樸變動 (topology change) 的能力。經由實驗證明本研究所提出的協定不論在電力或時間上皆有優於TMAC和TRAMA的表現。

Wireless sensor network, which is a special type of ad hoc networks, has many applications in various fields. Because of the difficulties of changing or recharging batteries for sensor nodes in many applications, how to save energy becomes a crucial issue for wireless sensor network. In order to reduce energy consumption of the sensor nodes, new communication protocols are needed for decreasing the amount of data processing and transmission as well as increasing the amount of sleep time of the sensor nodes. This research devises novel centralized energy-efficient TDMA (Time Division Multiple Access) MAC (Medium Access Control) protocols for wireless sensor network. The main idea is to assign time slots to each node adaptively so that it would reduce the level of packet collision, idle listening, overhearing, control overheads, and the latency of packet transmitting. Although the proposed protocols are centralized TDMA-based protocols, they still can handle topology changes very well. Comparing to TMAC and TRAMA, experimental results indicate that the proposed protocols have better performance in saving energy and reducing latency.

目錄
摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖表目錄 vii
表格目錄 xi
第一章 緒論 1
1.1 研究動機、背景與目的 1
1.2 論文架構 4
第二章 相關研究 5
2.1 無線感測網路環境簡介 5
2.2 MAC (Medium Access Control) 協定 8
2.2.1 以競爭為基礎 (contention-based) 的MAC協定 8
2.2.1.1 使用單一頻道的MAC協定 10
2.2.1.2 使用雙頻道的MAC協定 18
2.2.2 TDMA (Time Division Multiple Access) MAC協定 21
2.2.2.1 集中式TDMA MAC協定 23
2.2.2.2 分散式TDMA MAC協定 25
2.2.2.2.1 固定時槽個數分配法 26
2.2.2.2.2 可變動時槽個數分配法 30
2.2.3 其他協定 35
2.3 各協定間的優劣分析 36
第三章 集中式TDMA MAC協定 39
3.1 應用層與節點資料量關係 39
3.2集中式TDMA MAC協定 43
3.3 TDMA時槽分配 45
3.4 Direct transmitting method 48
3.4.1 Direct transmitting method - top-down (DTM-TD) 49
3.4.2 Direct transmitting method - bottom-up (DTM-BU) 58
3.4.3 Direct transmitting method - block (DTM-block) 64
3.5 Energy-efficient method 69
3.5.1 Static energy-efficient method (SEEM) 70
3.5.2 Dynamic energy-efficient method (DEEM) 76
第四章 拓樸管理 (topology management) 81
4.1 刪除節點 (node deletion) 81
4.2 新增節點 (node addition) 82
第五章 實驗評估 100
5.1 實驗環境及平台設定 100
5.2 實驗步驟及方法 101
5.3 實驗結果 102
5.3.1 不同節點數下電力和時間的比較 102
5.3.2 不同資料量下電力的比較 107
5.3.3 相同節點數不同樹狀結構下的時間比較 109
5.3.4 各種direct transmitting method時間和電力的比較 110
第六章 結論與未來研究 114
6.1 結論 114
6.2 未來研究 115
參考文獻 115
圖表目錄
圖2.1：EYES node電力花費情形 [11] 6
圖2.2：無線電資料 (RFM TR 1001) 6
圖2.3：SMAC中frame的duty cycle [8] 12
圖2.4：節點間可使用不同schedule [31] 12
圖2.5：Data gathering tree中錯開醒來的schedule時間 [20] 14
圖2.6：節點狀態依照pattern和schedule決定 [32] 16
圖2.7：協定使用雙頻道的收送情形 20
圖2.8：frame長度較schedule間隔短 23
圖2.9：frame長度較schedule間隔長 23
圖2.10：發生CS-collision的例子 [29] 25
圖2.11：frame內容 [7] 28
圖2.12：隨機選擇時槽後的碰撞發生 [4] 30
圖2.13：隨機選擇時槽後的死結發生 [4] 30
圖2.14：frame內容 [25] 31
圖2.15：frame內容 [19] 33
圖2.16：Control-slots table [19] 33
圖2.17：Data-slots table [19] 33
圖2.18：新增節點 35
圖3.1：query散佈和節點回傳資料在網路中傳遞情形 42
圖3.2：四種時槽分配的錯誤情形 47
圖3.3：DTM-TD使用depth-first traversal 50
圖3.4：DTM-TD使用breadth-first traversal 51
圖3.5：不在傳輸範圍內的節點時槽可重疊 52
圖3.6：不在傳輸範圍內的節點時槽可重疊 53
圖3.7：經由樹狀結構可快速的計算出frame長度 53
圖3.8：圖3.3經過時槽重疊後 54
圖3.9：使用DTM-TD後的時槽分配 55
圖3.10：DTM-TD演算法 55
圖3.11：DTM-TD使用interval-based query的運作方式 57
圖3.12：使用DTM-BU安排節點時槽 61
圖3.13：使用DTM-BU安排節點時槽 62
圖3.14：DTM-BU演算法 63
圖3.15：DTM-BU演算法 (測試節點在時槽中的傳輸正確性) 64
圖3.16：使用DTM-block分配節點時槽 66
圖3.17：使用DTM-block分配節點時槽 67
圖3.18：DTM-block演算法 68
圖3.19：SEEM時槽安排步驟 72
圖3.20：SEEM時槽安排步驟 72
圖3.21：SEEM時槽安排步驟 73
圖3.22：SEEM時槽安排步驟 73
圖3.23：SEEM時槽安排步驟 74
圖3.24：SEEM例子 75
圖3.25：SEEM演算法 76
圖3.26：DEEM時槽安排步驟 77
圖3.27：DEEM演算法 78
圖3.28：圖3.24樹狀結構使用DTM-TD 80
圖4.1：各種時槽在frame中的位置 83
圖4.2：Control slot時槽安排 (bottom-up) 86
圖4.3：Control slot時槽安排 (top-down) 86
圖4.4：新增節點使用control slot傳送訊息 88
圖4.5：Base station在control slot回應新增節點ACK訊息 89
圖4.6：Control slot中包含新增節點的部分 (bottom-up) 89
圖4.7：Control slot中包含新增節點的部分 (top-down) 90
圖4.8：使用SEEM新增節點的資料傳輸時槽 92
圖4.9：使用SEEM新增節點時影響原先已固定的資料傳輸時槽部分 93
圖4.10：使用DEEM新增節點可平行傳送的情形 94
圖4.11：DEEM節點原先安排時槽的情形 95
圖4.12：DEEM節點要求額外時槽的情形 96
圖5.1：不同節點個數下傳輸花費的時間 106
圖5.2：不同節點個數下傳輸花費的電力 106
圖5.3：不同資料量下花費的電力 109
圖5.4：不同高寬比的樹狀結構時間比較 110
表格目錄
表2.1：以競爭為基礎的MAC協定分析 22
表2.2：以競爭為基礎和TDMA MAC協定間的優劣分析 38
表5.1：三種direct transmitting method時槽個數比較 112
表5.2：三種direct transmitting method電力比較 (mA) 113

[1] IEEE 802.11. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 1999.

[2] D. J. Abadi, S. Madden, W. Lindner. REED: Robust, Efficient Filtering and Event Detection in Sensor Networks. In Proc. of the 31th VLDB Conference, 2005.

[3] K. A. Arisha, M. A. Youssef, M. F. Younis. Energy-aware TDMA-based MAC for sensor networks. In Proc. of IEEE Workshop on Integrated Management of Power Aware Communications Computing and Networking (IMPACCT), 2002.

[4] Z. Chen, A. Khokhar. Self organization and energy efficient TDMA MAC protocol by wake up for wireless sensor networks. In IEEE International Conference on Sensors and Ad hoc Communication and Networks (SECON), 2004.

[5] O. Chipara, C. Lu, G. C. Roman. Efficient power management based on application timing semantics for wireless sensor networks. In Proc. of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS), 2005.

[6] Chipcon products from Texas instruments: http://www.chipcon.com/

[7] S. Cho, K. Kanuri, J. W. Cho, J. Y. Lee, S. D. June. Dynamic Energy Efficient TDMA-based MAC Protocol forWireless Sensor Networks. In Proc. of the Joint International Conference on Autonomic and Autonomous Systems and International Conference on Networking and Services (ICAS/ICNS), 2005.

[8] T. V. Dam, K. Langendoen. An adaptive energy-efficient MAC protocol for wireless sensor networks. In Proc. of the First ACM Conference on Embedded Networked Sensor Systems (SenSys), 2003.

[9] J. Denga, Y. S. Han, W. B. Heinzelman, P. K. Varshney. Balanced-energy sleep scheduling scheme for high-density cluster-based sensor networks. Elsevier Computer Communications Journal, Special Issue on ASWN ’04, vol. 28, no. 14, pp. 1631-42, September 2005.

[10] A. Deshpande, S. Nath, P. B. Gibbons, S. Seshan. Cache-and-Query for Wide Area Sensor Databases. In Proc. of the ACM SIGMOD International Conference on Management of Data, 2003.

[11] Eyes energy efficient sensor networks: http://www.eyes.eu.org/sensnet.htm

[12] T. Herman, S. Tixeuil. A distributed TDMA slot assignment algorithm for wireless sensor networks. First International Workshop, ALGOSENSORS, 2004.

[13] L. v. Hoesel, P. Havinga. A lightweight medium access protocol (LMAC) for wireless sensor networks: Reducing preamble transmissions and transceiver state switches. In Proc. of the 1st International Workshop on Networked Sensing Systems (INSS), 2004.

[14] L. Hoesel, T. Nieberg, H. Kip, P. Havinga. Advantages of a TDMA based, energy-efficient, self-organizing MAC protocol for WSNs. In Proc. of the 59th IEEE Vehicular Technology Conference (VTC), 2004.

[15] R. Kalidindi, L. Ray, R. Kannan, S. Iyengar. Distributed energy aware MAC layer protocol for wireless sensor networks. International Conference on Wireless Networks, 2003.

[16] A. Kanzaki, T. Hara, S. Nishio. An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks. In Proc. of the ACM symposium on Applied computing (SAC), 2005.

[17] S. S. Kulkami, M. Arumugam. TDMA service for sensor networks. In Proc. of the 3rd International Workshop on Assurance in Distributed Systems and Networks (ADSN), 2004.
[18] Y. Li, W. Ye, J. Heidemann. Energy and latency control in low duty cycle MAC protocols. In Proc. of the IEEE Wireless Communications and Networking Conference (WCNC), 2005.

[19] A. Liu; H. Yu; L. Li. An energy-efficiency and collision-free MAC protocol for wireless sensor networks. Vehicular Technology Conference (VTC), 2005.

[20] G. Lu, B. Krishnamachari, C. S. Raghavendra. An adaptive energy-efficient and low-latency MAC for data gathering in wireless sensor networks. In Proc. of the 18th International Parallel and Distributed Processing Symposium (IPDPS), 2004.

[21] S. Madden, M. J. Franklin, J. M. Hellerstein W. Hong. The design of an acquisitional query processor for sensor networks. In Proc. of the 2003 ACM SIGMOD International Conference on Management of Data, 2003.

[22] S. Mao, Y. T. Hou. BeamStar: A new low-cost data routing protocol for wireless sensor networks. Global Telecommunications Conference (GLOBECOM), 2004.

[23] M. J. Miller, N. H. Vaidya. Power save mechanisms for multi-hop wireless networks. In Proc. of the First International Conference on Broadband Networks (BROADNETS), 2004.

[24] P. C. Nar, E. Cayirci. PCSMAC: A power controlled sensor-MAC protocol for wireless sensor networks. In Proc. of the 2nd European Workshop on Wireless Sensor Network (EWSN), 2005.

[25] V. Rajendran, K. Obraczka, J. Garcia-Luna-Aceves. Energy-efficient, collison-free medium access control for wireless sensor networks. In SenSys, 2003.

[26] M. Ringwald, K. Romer. BitMAC: A deterministic, collision-free, and robust MAC protocol for sensor networks. In Proc. of the Second European Workshop, 2005.
[27] C. Schurgers, V. Tsiatsis, S. Ganeriwal, M. Srivastava. Topology management for sensor networks: Exploiting latency and density. In Proc. of the 3rd ACM international symposium on Mobile ad hoc networking & computing, 2002.

[28] M. A. Sharaf, J. Beaver, A. Labrinidis, P. K. Chrysanthis. Balancing Energy Efficiency and Quality of Aggregate Data in Sensor Networks. The Very Large Data Base (VLDB) Journal manuscript, 2004.

[29] T. Wu, S. Biswas. Reducing inter-cluster TDMA interference by adaptive MAC allocation in sensor networks. World of Wireless Mobile and Multimedia Networks (WoWMoM), 2005.

[30] Crossbow technology incorporation: http://www.xbow.com/index.aspx

[31] W. Ye, J. Heidemann, D. Estrin. An energy-efficient MAC protocol for wireless sensor networks. In Proc. of the 21th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2002.

[32] T. Zheng, S. Radhakrishnan, V. Sarangan. PMAC: An adaptive energy-efficient MAC protocol for wireless sensor networks. In Proc. of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2005.