無線感測網路中的動態覆蓋和鏈結性維護演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：45

、訪客IP：3.139.86.56

姓名

林偉勛(Wei_Shin Lin) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

無線感測網路中的動態覆蓋和鏈結性維護演算法
(Dynamic Coverage and Connectivity Maintenance Algorithmfor the Wireless Sensor Networks)

相關論文

★ 無線行動隨建即連網路上之廣播與繞徑問題	★ 熱門電影的高效能廣播演算法
★ 無線行動隨建即連網路上之媒體存取問題	★ 使用功率調整來增加多節點封包無線網路
★ 在無線行動隨建即用網路下Geocast 之設計與實做經驗	★ 一個適用於熱門隨選視訊服務之快速排程廣播策略
★ 應用數位浮水印技術於影像之智慧財產權保護與認證	★ 在寬頻分碼多重擷取技術上分配及再分配多重正交可變展頻係數碼
★ 無線行動隨建即連網路上之廣播排程協定	★ 在無線行動隨建即連網路下支援即時多媒體傳送的媒介存取協定
★ 以樹狀結構為基礎的Scatternet建構協定	★ 在無線感應器網路中具有省電機制並且採用對角線路徑的方向性擴散
★ 隨意型無線網路上一個具有能量保存的GRID繞徑協定	★ 在無線感應器網路中具有省電機制的傳輸協定
★ 隨意型無線網路上一個具有能量保存以及平衡的繞徑協定	★ 環形藍芽網路：一個藍芽通訊網路的新拓樸及其繞徑協定

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在無線測網路的中，其中一個設計上的挑戰是如何維持在部署後節點間的覆蓋與鏈結性。無線感測網路所提供的覆蓋或者連接性對它的效能佔了非常關鍵之因素。較快失敗的節點會造成網路中覆蓋的損失，而覆蓋的損失需要覆蓋維護機制。相同地，因入侵或爆炸而損壞的節點也會令產生網路中產生未覆蓋區域。此外，節點的電量，環境因素，震動，以及電子零件損壞或是軟體錯誤都可能會造成結點忽然死亡，進而影響網路中原有的覆蓋與鏈結性。無線感測網路中有許多的重要的應用都是使用自主移動來維持網路中的覆蓋或鏈結性。然而，大部分的文獻修補網路中錯誤時都假設傳輸半徑為感測半徑的兩倍，如此一來便消耗更多的電量。我們在這裡提出一個假設傳輸大於或等於感測半徑的方法，讓感測器可以自我辨認是否為多餘的結點，並且彌補在覆蓋及鏈結性上的損失。此篇論文中我們利用具有最小的能量消耗的受限的移動性與只具有鄰近區域鄰居結點知識來解決覆蓋與鏈結上的損失。我們提出了三種維護演算法來決定當覆蓋問題、鏈結性問題、覆蓋問題與鏈結性問題同時發生時應該由哪一個節點來移動以及該移動多遠，使得電量消耗是最低的並且可以修復網路中的錯誤。此外在與其他演算法比較時，我們在覆蓋、鏈結性、平均移動距離、節點的省電與網路生命週期上優於其他演算法。

摘要(英)

In wireless sensor networks, one of the main design challenges is to maintain the connectivity and coverage among nodes in a post deployment scenario. Either the coverage or connectivity provided by sensor networks is very crucial to their effectiveness. Early failure of sensor nodes due to death of a node can lead to coverage loss that requires coverage maintenance schemes. Similarly, possible destruction of nodes due to intrusion or explosion in the network creates the communication holes. Besides, the power sources of nodes, environmental factors, vibration, and failure of electronic components or software bugs may lead the death of the nodes accidentally, thereby affecting the coverage and connectivity of the original network. Many of the important applications of sensor networks demand autonomous mobility for the sensor nodes to maintain either the coverage or connectivity. However, most of the literatures consider the communication range is twice, even if greater than twice the sensing radius to repair the fault, thereby consuming more energy, as communication is the main source of energy consumption. We propose here a potential approach that let sensors work alternatively by identifying redundant sensing regions in high-density networks and to compensate the loss of both coverage and connectivity with communication range is equal to or less than twice the sensing range. For this we use the low mobility of nodes with minimum expenditure of energy and having knowledge of only their local neighborhood topology to repair both connectivity and coverage loss. We propose three different maintenance algorithms for connectivity, coverage and both connectivity to decide which neighbors to migrate, and to what distance, such that the energy expended is minimized and the faults are repaired by the low mobility nodes. The decision and movement is completely autonomous in the network, and involves movement of one-hop neighbors of a dead sensor node. We have also compared the performance of different algorithms in terms of the improvement in coverage, connectivity, average mobility distance and in terms of energy saving of the nodes, and the lifetime of the network, under our assumption that communication range is equal to or less than twice the sensing range.

關鍵字(中)

★ 鏈結性
★ 覆蓋
★ 無線感測網路
★ 低移動性

關鍵字(英)

★ coverage
★ connectivity
★ low mobility
★ Wireless sensor networks

論文目次

Chapter 1 Introduction 1
Chapter 2 Related Work 4
Chapter 3 System Model 7
3.1 Motivations 7
3.2 Assumptions 9
3.3 Definitions 10
Chapter 4 Coverage and Connectivity Maintenance Algorithms 18
4.1 Coverage and Connectivity Problems 18
4.1.1 Estimation of MTMD 18
4.1.2 Estimation of MSMD 20
4.1.3 Available Mobility Distance (AMD) 21
4.2 Maintenance Algorithmes 22
4.2.1 Connectivity Maintenance 22
4.2.2 Coverage Maintenance 28
4.2.3 Connectivity and Coverage Maintenance 30
Chapter 5 Performance Analysis 33
5.1 Simulation Setups 33
5.2 Simulation Results 34
Chapter 6 Conclusion 43
References 45

參考文獻

[1] S. Ganeriwal, A. Kansal, and M. B. Srivastava, “Self aware actuation for fault repair in sensor networks”, in Proc. IEEE International Conference on Robotics and Automation, vol 5, pp.5244-5249, Spain, May, 2004
[2] A. Sekhar, B. S. Manoj, and C. S. R. Murthy, "Dynamic Coverage Maintenance Algorithms for Sensor Networks with Limited Mobility,” in Proc. IEEE International Conference on Pervasive Computing and Communications, pp. 51-60, USA, Mar., 2005.
[3] A. Howard, M. J. Mataric, and G. S. Sukhatme, "Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem," in Proc. International Symposium on Distributed Autonomous Robotic Systems, pp. 299-308 , Japan, Jun., 2002.
[4] G. Wang, G. Cao, and T. L. Porta, “Movement-assisted sensor deployment,” IEEE Transactions on Mobile Computing, Volume 5, Issue6, pp. 640-652, Jun., 2006.
[5] D. W. Gage, “Command control for many-robot systems,” in Nineteenth Annual AUVS Technical Symposium, pp. 22-24, USA, Jun., 1992.
[6] N. Ahmed, S. Kanhere and S. Jha, “The Holes Problem in Wireless Sensor Networks: A survey,” ACM Sigmobile Mobile Computing and Communications Review , vol. 9, Issue 2, pp.4-18, Apr., 2005.
[7] N. Heo and P. K. Varshney, “An intelligent deployment and clustering algorithm for a distributed mobile sensor network,” in Proc. IEEE International Conference on Systems, Man and Cybernetics, vol. 5, pp. 4576–4581, USA, Oct., 2003.
[8] Z. Butler and D. Rus, “Event-based Motion Control for Mobile Sensor Networks,” in IEEE Pervasive Computing Magazine, vol. 2, pp. 34-42, Oct., 2003.
[9]J. P. Sheu, C. H. Yu, and S. C. Tu, “A Distributed protocol for query execution in sensor networks,” in Proc. of the IEEE Wireless Communications & Networking Conference, vol. 3, pp. 1824-1829, USA, Mar., 2005.
[10] J. P. Sheu, P. W. Cheng, and K. Y. Hsieh, “Design and Implementation of a Smart Mobile Robot,” in Proc. IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, vol. 3, pp. 422-429, Canada, Aug., 2005.
[11] S. Doumit and D. P. Agrawal, “Bio-InspiredMobility in Environment Aware Wireless Sensor Networks,” in Proc. IEEE International Conference on Pervasive Computing and Communications, pp. 514-517, USA, Mar., 2003.
[12] G. Kesidis, T. Konstantopoulos, and S. Phoha, “Surveillance Coverage of Sensor Networks under a Random Mobility Strategy,” in Proc. IEEE Sensors, vol. 2, pp. 961-965, Canada, Oct., 2003.
[13] G. T. Sibley, M. H. Rahimi, G. S. Sukhatme, “Robomote: A Tiny Mobile Robot Platform for Large-Scale Sensor Networks," in Proc. IEEE International Conference on Robotics and Automation, pp.1143-1148, USA, Sep., 2002.
[14] X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks,” in ACM Conference on Embedded Networked Sensor Systems, pp 28-33, USA, Nov., 2003.
[15] N. Bulusu, J. Heidemann, D. Estrin, and Tommy Tran, “Self-configuring localization systems: Design and experimental evaluation,” ACM Transactions on Embedded Computing Systems, vol. 3, issue 1, pp. 24-60, Feb., 2003.
[16] B. Karp, and H.T. Kung, “Greedy Perimeter Stateless Routing for Wireless Networks,” in Proc. ACM/IEEE International Conference on Mobile Computing and Networking , pp. 243-254, USA, Aug., 2000.
[17]A. Caruso, S. Chessa, S. De, and A. Urpi, “GPS Free Coordinate Assignment and Routing in Wireless Sensor Networks,” in Proc. IEEE International Conference on Computer Communication, vol. 1, pp.150-160, USA, Mar., 2005
[18] M. B. McMickell, B. Goodwine, and L. A. Montestruque, “MICAbot: A Robotic Platform for Large-Scale Distributed Robotics,” in Proc. IEEE International Conference on Robotics and Automation, vol. 2, pp. 1600-1605, Taipei, Taiwan, Sep. 2003.
[19] S. Bergbreiter and K. S. J. Pister, “CotsBots: An Off-the-Shelf Platform for Distributed Robotics,” in Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, vol.2, pp. 1632-1637, USA, Oct., 2003.
[20] S.Capkun, M. Hamdi, and J. P.Hubaux, “GPS-Free Positioning in Mobile Ad Hoc Networks,” in Proc. Annual Hawaii International Conference on System Sciences, vol. 9, pp. 9008, USA, Jan., 2001.
[21] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. E. Culler, and K. S. J. Pister, “System Architecture Directions for Networked Sensors,” in Proc. International Conference Architectural Support for Programming Languages and Operating Systems, pp. 93-104, USA, November 2000.
[22] http://www.kvh.com/DigiComp/

指導教授

許健平(Jang Ping Sheu)

審核日期

2006-7-21

推文