淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1507200700163300
中文論文名稱 在無線感測網路中具克障及共享之資料收集樹
英文論文名稱 On Supporting Obstacle-Free and Sharing Tree for Information Collection in Wireless Sensor Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 95
學期 2
出版年 96
研究生中文姓名 郭世君
研究生英文姓名 Shih-Chun Kuo
學號 694190512
學位類別 碩士
語文別 中文
口試日期 2007-06-09
論文頁數 64頁
口試委員 指導教授-張志勇
委員-陳裕賢
委員-陳宗禧
委員-王三元
中文關鍵字 無線感測網路  資料共享樹  克障繞徑  群播樹 
英文關鍵字 Steiner Tree  Share Tree  Multicast Tree  Obstacle-Free Routing 
學科別分類 學科別應用科學資訊工程
中文摘要 無線感測網路中,建立具共享能力之資料收集樹是一個重要的服務功能。雖然現有研究對共享樹的建立已有許多探討,當網路中存在障礙物或是共享樹上的Sensor電力耗盡無法繼續傳送資料時,將破壞其資料收集的整合性及通訊效能,因此,本論文主要在研究下列議題:給予一已建立之共享樹,當此共享樹中產生一影響通訊的大型障礙物時,如何以分散式的技術來局部重建共享樹,使資料的收集具有高度的共享能力以達到節省耗電及延長網路生命期之目的。在本研究中,我們擬從多種避開障礙物或空洞區域的路徑中,有效率的挑選出有高度共享以減少成本的封包傳輸路徑,並以較低的成本來重建具高度共享之資料收集樹。實驗數據顯示,我們所提出維護Share Tree的機制,能有效的克服障礙區,並能維持Share Tree共享的能力、減少電量的耗費以及延長WSNs的生命週期。
英文摘要 Constructing a share tree from sink node to a group of data source nodes can explore the potential of data aggregation in wireless sensor networks (WSNs). In literature, there are plenty researches developing mechanisms to construct a share tree, however, most of them can not resist obstacles which might damage the constructed tree topology and thus block the data transmission. This paper proposes a disturbed mechanism, namely obstacle-free sharing tree reconstruction protocol (OFST), to locally repair the injured share tree so that the reconstructed share tree can resist obstacles and explore the data aggregation potential. For a given three disconnected subtree, the proposed OFST initially identifies the share region where all points in the region can play the role of share point for resisting the existed obstacle and exploring the data aggregation potential. Based on the concept of steiner point, a theoretical study on selecting the best share point from the share region is presented for connecting the three subtrees. Simulation results reveal that the proposed OFST protocol can effectively overcome the obstacle and explore the data aggregation potential, and hence reduce the energy consumption and prolong the network lifetime of the WSN.
論文目次 目 錄
目 錄 I
圖 目 錄 II
I、Introduction 1
II、Related Work 5
III、Network Environment & Problem Statement 9
3.1 Network Model and Assumptions 9
3.2 Problem Statements 10
IV、Obstacle-Free Share Tree Reconfiguration Protocol 14
4.1 Faulty Tree Detection Phase 14
4.2 Tree Reconstruction Phase 18
4.2.1 Select The Reconstruction Set 18
4.2.2 Tree Establishment 29
4.2.3 Cost Analysis 33
V、Simulation 35
5.1 Simulation Setup 35
5.2 Performance Metrics 37
VI、Conclusion 53
REFERENCES 54
附錄─英文論文 57

圖 目 錄
圖 一:障礙區域產生破壞Share Tree的結構 10
圖 二:Information_Gathering封包格式 17
圖 三:Share Region 22
圖 四:最接近Steiner Point的位置 24
圖 五:Steiner tree is the minimum cost 26
圖 六:共享點的成本比較 27
圖 七:Reconfiguration 31
圖 八:實驗場景-障礙區產生 37
圖 九:實驗場景-克服障礙區域 37
圖 十:網路Sensor個數 vs. Total Length 38
圖 十一:Damage Ratio vs. Total Length 39
圖 十二:Source Density vs. Total Length 40
圖 十三:網路Sensor個數 vs. Reduction Ratio 42
圖 十四:Damage Ratio vs. Reduction Ratio 43
圖 十五:Source Density vs. Reduction Ratio 44
圖 十六:網路Sensor個數 vs. Energy Cost 46
圖 十七:Damage Ratio vs. Energy Cost 47
圖 十八:Source Density vs. Energy Cost 48
圖 十九:網路Sensor個數 vs. Delay Time 50
圖 二十:Damage Ratio vs. Delay Time 51
圖 二十一:Source Density vs. Delay Time 52
參考文獻 [1] Chalermek Intanagonwiwat, Deborah Estrin, John Heidemann, “Impact of Network Density on Data Aggregation in Wireless Sensor Networks,” Proceedings of IEEE International Conference on Distributed Computing Systems (ICDCS), 2002.
[2] Shinji Mikami, Takafumi Aonishi, Hironori Yoshino, Chikara Ohta, Hiroshi Kawaguchi and Masahiko Yoshimoto, “Aggregation Efficiency-Aware Greedy Incremental Tree Routing for Wireless Sensor Networks,” IEICE Transactions on Communications, v E89-B, n 10, p 2741-2750, October, 2006.
[3] S.-J. Lee and M. Gerla and C.-C. Chiang, “On-Demand Multicast Routing Protocol,” Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), pp.1298-1304, New Orleans, 1999.
[4] Oliver Stanze and Martina Zitterbart, “On-Demand Overlay Multicast in Mobile Ad hoc Networks,” Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), pp.2155-2161, 2005.
[5] S. Das, B, Manoj et al, “A dynamic core based multicast routing protocol for ad hoc wireless networks,” Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing (MOBICOM), pp.24-35, 2002.
[6] Shibo Wu, K. Selcuk Candan, “GMP: Distributed Geographic Multicast Routing in Wireless Sensor Networks,” Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS), 2006.
[7] Juan A. Sanchez, Pedro M. Ruiz, Ivan Stojmenovic, “GMR: Geographic Multicast Routing for Wireless Sensor Networks,” The 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks (SECON), pp.20-29, 2006.
[8] R. Hwang, D. Richards et al, ”The Steiner Tree Problem,” Annals of Discrete Mathematics,1992.
[9] Alexandr O. Ivanov and Alexei A. Tuzhilin. “Minimal Networks: The Steiner Problem and its Generalizations,” CRC Press, 1994.
[10] P. Bose, P. Morin, Ivan Stojmenovic, and J. Urrutia, “Routing with guaranteed delivery in ad hoc wireless networks,” ACM Wireless Networks, pp.609-616, Vol.7 no.6, Nov. 2001.
[11] Y.-B. Ko and N.H. Vaidya, “Geocasting in mobile ad hoc networks: location-based multicast algorithm, “ in: IEEE Workshop on Mobile Computer Systems and Applications, February 1999.
[12] Chih-Yung Chang , Chao-Tsun Chang , Shin-Chih Tu, “Obstacle-Free Geocasting Protocols for Single/Multi-Destination Short Message Services in Ad Hoc Networks, “ Wireless Networks, p.143-155 , March 2003.
[13] Le Zou, Mi Lu, and Zixiang Xiong, “A Distributed Algorithm for the Dead End Problem of Location Based Routing in Sensor Networks,“ IEEE Transactions, Vehicular Technology , 2005.
[14] B. Karp and H.T. Kung, “GPSR:Greedy Perimeter Stateless Routing for Wireless Networks,” Proc. 6th Annual International Conference on Mobile Computing and Networking (MOBICOM), pp.243-254, 2000.
[15] Caruso, A. Urpi, S. Chessa, and S. De, “GPS-Free Coordinate Assignment and Routing in Wireless Sensor Networks,” Proceedings of IEEE International Conference on Computer Communication (INFOCOM), Vol. 1, pp. 150-160, Miami, March, 2005.
[16] Vijayanth Vivekanandan, and Vincent Wong, “Concentric Anchor-Beacons (CAB) Localization for Wireless Sensor Networks,“ Proc. of IEEE International Conference on Communications (ICC), 2006.
[17] C. Y. Chang, K. P. Shih, S. C. Lee, and S. W. Chang, "RGP: Active Route Guiding Protocol for Wireless Sensor Networks with Obstacle," International Conference on IEEE Mobile Ad hoc and Sensor Systems (MASS), pp.367-376,Oct. 2006.
[18] Xiaoyun Li, David K. Hunter, Kun Yang , “Distributed Coordinate-free Hole Detection and Recovery,” IEEE Global Telecommunications Conference (GLOBECOM), Nov. 2006.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-07-19公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-07-19起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信