臺灣博碩士論文加值系統

無線感測網路除了感測的功能外，一些感測器(Sensor)還必須擔任資料轉傳的工作，這些感測器被稱之為路由器(Router)，建立叢集樹(Cluster Tree)的機制有效降低路由器的數量，以往叢集樹建立方式通常由叢集管理者(Cluster Head)互相串接而成。雖然可以用少量的Cluster便連通整個網路，但是叢集樹對於多點跳躍(Multi-hop)的資料傳輸是以分時多工的方式進行排程，感測器到收集器(Sink)傳輸路徑上的Cluster個數過多，就會造成傳輸延遲，減弱收集感測資料的效率。
本篇論文以IEEE 802.15.4為網路架構，除了利用Cluster Head做分群，再利用一種稱為橋接器(Bridge)的路由器來橋接兩個Cluster，增加Cluster在一個運作週期內封包可以傳遞的Hop數，如此可以縮短感測器到達Sink的延遲時間，並參考在圖論上尋找樹狀架構上的最大獨立集合的觀念，配合著無線感測網路資料主要由感測器傳向Sink的單一方向匯集特性，挑選網路上無子節點的感測器成為葉節點(Leaf Node)，開始朝Sink方向建立叢集樹；而建立方法依照Leaf Node挑選順序不同分為兩種，第一種為了降低建立時間，一旦感測器成為Leaf Node便開始進行建立動作；另一種方法著眼於控制封包的節省，當感測器成為離Sink最遠的Leaf Node才開始建立叢集樹。最終建造出的叢集樹可以使得各感測器到Sink路徑上所經過的Cluster個數最少，讓傳送延遲降到最低，提升無線感測網路資料收集的即時性，我們也做模擬實驗來驗證此兩方法對於建樹的影響。

第一章 緒論
1.1 簡介IEEE 802.15.4
1.2 研究動機
1.3 研究目標

第二章 相關研究與成果
2.1 IEEE 802.15.4
2.2 建造無Bridge的叢集樹的相關成果
2.3 建造有Bridge的叢集樹的相關成果
2.4 拓樸分配對排程的影響

第三章 最短延遲叢集樹的架構
3.1 網路架構
3.2 Leaf Node
3.3 Cluster Head
3.4 Bridge

第四章 建立最短延遲的叢集樹
4.1 參考在樹狀架構上的最大獨立集合的角色分配概念
4.2 從Leaf Node開始進行叢集樹建置的兩種方法
4.2.1 一旦設為Leaf Node後即時開始建立叢集樹
4.2.2 由距離Sink最遠的Leaf Node開始建立叢集樹
4.3 感測器資訊的交換機制
4.4 Backoff Time的設定
4.5 選擇Cluster Head的方法
4.5.1 選擇未擔任角色的Father鄰居
4.5.2 選擇已擔任CH的Father鄰居
4.5.3 選擇已擔任CH的Brother鄰居
4.5.4 選擇已擔任Bridge的Father Neighbor
4.5.4.1 Longest_Hop比自己小的Bridge
4.5.4.2 Longest_Hop比自己大的Bridge
4.5.5 Cluster Head發送CH封包進行分群
4.6 選擇Bridge的方法
4.6.1 選擇未擔任角色的Father鄰居
4.6.2 選擇已擔任CH的Father鄰居
4.6.3 選擇已擔任Leaf Node的Father鄰居
4.7 例外狀況的處理方式
4.7.1 只能成為特定Bridge的節點
4.7.2 只能成為CH的節點

第五章 模擬實驗
5.1 模擬環境與架構
5.2 最遠Leaf Node跨越的Cluster個數比較
5.3 Leaf Node個數比較
5.4 CH與Bridge個數比較
5.5 控制封包個數比較
5.6 叢集樹建立時間比較
5.7 CH與Bridge運作次數比較

第六章 結論與未來展望

參考文獻

[1] IEEE standard for information technology - telecommunications and information exchange between systems - local and metropolitan area networks specific re-quirements part 15.4: wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs), 2003.

[2] ZigBee Specification, ZigBee Document 053474r06, Version 1.0, Sponsored by: ZigBee Alliance.

[3] 財團法人資訊工業策進會, http://www.iii.org.tw/index.html

[4] 台灣zigbee產業聯盟, http://www.twzigbee.org.tw/default.asp

[5] 張志龍, “感測網路應用實例-以科博館為例,” 資策會科技專案研發成果展覽會暨研討會, 2005.

[6] W. Ye, J. Heidemann, D. Estrin, “An Energy-Efficient MAC Protocol for Wire-less Sensor Networks,” in Annual Joint Conference of the IEEE Computer and Communications Societies 2002, vol. 3, pp. 1567-1576.

[7] X. Du and F. Lin, “Improving routing in sensor networks with heterogeneous sensor nodes,” in IEEE Vehicular Technology Conference 2005, vol. 4, pp. 2528-2532.

[8] C. Gao, R. Jantti, “Link-State Clustering Based on IEEE 802.15.4 MAC for Wireless Ad-hoc/Sensor Networks,” in IEEE Wireless Communications and Networking Conference 2006, vol. 1, pp. 499-504.

[9] B. Das and V. Bharghavan, "Routing in ad-hoc networks using minimum con-nected dominating sets," in IEEE International Conference on Communications 1997, vol. 1, pp. 376-380.

[10] K. Alzoubi, X. Y. Li, Y. Wang, P. J. Wan, and O. Frieder, "Geometric Span-ners for Wireless Ad Hoc Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 4, pp. 408-421, 2003.

[11] Y. S. Chen and T. H. Lin, "A QoS Routing Protocol using Cluster-Mesh-Tree for IEEE 802.15.4 Low-Rate WPANs," in Workshop on Wireless, Ad Hoc, and Sen-sor Networks 2005, pp. 83-90.

[12] 李文仲 and 段朝玉, ZigBee無線網路技術入門與實戰, 北京航空航天大學出版社, 2007.

[13] J. Ma, M. Gao, Q. Zhang, L. M. Ni, and W. Zhu, "Localized Low-Power Topol-ogy Control Algorithms in IEEE 802.15.4-based Sensor Networks," in IEEE In-ternational Conference on Distributed Computing Systems 2005, pp. 27-36.

[14] G. Lu, N. Sadagopan, B. Krishnamachari,and A. Goel, " Delay Efficient Sleep Scheduling in Wireless Sensor Networks," in Annual Joint Conference of the IEEE Computer and Communications Societies 2005, vol. 4, pp.2470-2481.

[15] Y. C. Tseng and M. S. Pan, "Quick Convergecast in ZigBee/IEEE 802.15.4 Tree-Based Wireless Sensor Networks," in ACM International Workshop on Mobility Management and Wireless Access Protocols 2006, pp.60-66.

[16] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2006.