無線感測網路偵測覆蓋空洞機制之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：34

、訪客IP：3.139.82.23

姓名

馬驊群(Hwa-Chun Ma) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

無線感測網路偵測覆蓋空洞機制之研究
(Study of Coverage Hole Detection Schemes for Wireless Sensor Networks)

相關論文

★ 應用MSPP至DWDM都會光纖網路的設計	★ 光網路與WiMAX整合架構研究及其簡化雛型實驗
★ 以Linux系統為基礎之NAT效能優化研究及其實作	★ 光波長劃分多工網路之路徑保護機制研究
★ 標籤交換網路下具有服務品質路由安排之研究	★ 以訊務相關性為基礎的整合性服務可調整QoS排程器之研究
★ 以群體播送支援IPv6環境下移動式網路連結更新之研究	★ 無線區域網路資源動態分配之效能研究
★ 在微觀移動環境下有效資源保留之路徑管理研究	★ 無線網路交握程序之預先認證方法分析與比較
★ 無線區域網路虛擬允入控制之研究	★ IPv6環境下移動網路之連結更新程序及其效能之研究
★ 具有限數量波長轉換節點的分波多工網路之群播波長分配與容量計算研究	★ 階層化行動式IPv6移動錨點選擇機制研究
★ 具高能量移動節點之叢集式感測網路效能研究	★ 預先註冊之快速換手階層化行動式IPv6研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

無線感測網路中的應用已被廣泛使用在很多領域上，包括環境的監控、災難的救護及戰場監測等等。在無線感測網路的隨機初期佈建上，由於無法保證會有完全的覆蓋，加上佈建後感測器會因節點的電力耗盡與被外力破壞等因素，很難以避免在無線感測網路監控區域中會有覆蓋空洞的問題，而這些覆蓋空洞的存在，也因此會影響無線感測網路的效能在很多層面上，因此在無線感測網路，需要每一節點皆能執行簡單又有效的覆蓋空洞偵測方法，以提供無線感測網路所需的覆蓋品質，及確保網路之可靠性。基於此，因此在本論文中，我們提出以計算幾何為基礎，使用簡單而且有效率的覆蓋空洞偵測機制，經由此一機制可以有效偵測出存在於監控區域中的覆蓋空洞，在我們所設計協定中，藉由每一節點收集兩倍感測距離內相鄰節點的資訊並使用三角形及多邊形幾何法來找出此一節點附近的空洞，此一分散式偵測演算法亦可以應用在不同形狀與大小的監控區。另外在我們所提出的偵測演算法經所發展出理論定理證明，說明此演算法是完全正確的，並透過ns-2的模擬，結果顯示我們的覆蓋空洞偵測協定演算法在偵測時間上與能量消耗上，比其他方法還要好。

摘要(英)

Wireless sensor networks have been employed in many applications, such as environment monitoring, disaster relief operation and battlefield surveillance. However, in initial random deployment there is no guarantee of complete coverage. Besides, in the post deployment sensor nodes may fail due to power depletion, or physical destruction. Therefore, coverage holes problem can hardly be avoided in wireless sensor networks. The presences of holes have an influential impact on the performance of the sensor network at many levels. Thus, sensor nodes must execute simple and efficient coverage hole detection mechanism for providing the required QoS of coverage and ensuring network reliability. Accordingly, in this dissertation we propose the computational geometry based distributed coverage hole detection algorithm using both triangular and polygon methods to find out the holes. Detection of the holes are done using simple and efficient geometric methods taking only one and two-hop neighbors of each node to detect the hole around it and therefore requires less computation time. Global view of the coverage hole detection is proposed taking local information of the nodes. The algorithm is completely distributed and can also detect the coverage holes irrespective of any shape or size of the monitoring region. We also make proofs for each of the lemmas used in the construction of the algorithms. The algorithms are shown to be theoretically correct. Performance evaluation of our algorithm shows that the hole detection time and energy consumption due to hole detection outperforms over similar hole detection algorithms.

關鍵字(中)

★ 分散式
★ 空洞偵測
★ 無線感測網路
★ 覆蓋空洞

關鍵字(英)

★ Wireless sensor networks
★ hole detection
★ coverage hole
★ Distributed

論文目次

ABSTRACT ii
ACKNOWLEDGEMENTS iii
Table of Contents iv
List of Figures vi
List of Tables ix
Chapter 1. Introduction 1
1.1 Overviews of Wireless Sensor Networks 1
1.2 Coverage and Holes Problems 2
1.3 Research Motivations 4
1.4 Contributions 5
1.5 Organization of the Dissertation 6
Chapter 2. Related Works 7
Chapter 3. Preliminaries 11
3.1 Problem Formulation 11
3.2 Definitions 12
3.3 System Model 14
Chapter 4. Triangle-Based Hole Detection Algorithm 17
4.1 Neighbor discovery phase 17
4.2 Hole detection phase 19
4.3 Theoretical Analysis 24
4.4 Summary 35
Chapter 5. Polygon-Based Hole Detection Algorithm 36
5.1 Neighbor discovery 37
5.2 Hole Detection Phase 38
5.3 Comparison Examples and Discussion 41
5.4 Summary 42
Chapter 6. Experimental Analysis 43
6.1. Simulation Setup 43
6.2. Simulation Results 45
6.2.1 Effects of the Number of Nodes 45
6.2.2 Analysis of the Detection Time 46
6.2.3 Analysis of Energy Consumption 49
6.2.4 Comparison with other schemes 51
Chapter 7. Conclusions and Future Works 57
Bibliography 59
List of Publications 67

參考文獻

[1] Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, “Wireless Sensor Networks: A Survey”, Journal of Computer Networks, vol.38, pp.393–422, 2002
[2] Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin, “Directed diffusion: A scalable and robust communication paradigm for sensor networks”, In Proceedings of the Sixth Annual ACM/IEEE MobiCom, pp.56–67, August 2000
[3] Haiyun Luo, Fan Ye, Jerry Cheng, Songwu Lu, and Lixia Zhang, “Two-tier data dissemination model for large-scale wireless sensors networks”, In Proceedings of ACM/IEEE MobiCom’02, September 2002
[4] Fan Ye, Gary Zhong, Songwu Lu, and Lixia Zhang, ”Gradient broadcast: A robust data delivery protocol for large scale sensor networks”, In IPSN, April 2003
[5] Brad Karp and H. T. Kung, GPSR: Greedy, “perimeter stateless routing for wireless networks”, In Proceedings of the ACM/IEEE MobiCom’2000, pp. 243–254, 2000
[6] John Heidemann, Fabio Silva, and Deborah Estrin, “Matching data dissemination algorithms to application requirements”, In Proceedings of the ACM SenSys ’03, Nov. 2003
[7] David Braginsky and Deborah Estrin, “Rumor routing algorithm for sensor networks”, In 1st ACM WSNA ’02, Sep. 2002
[8] Di Tian and Nicolas D. Georganas, “Energy efficient routing with guaranteed delivery in wireless sensor networks”, In IEEE WCNC ’03, April 2003
[9] Deepak Ganesan, Ramesh Govindan, Scott Shenker, and Deborah Estrin, “Highly-resilient energy-efficient multipath routing in wireless sensor networks”, Mobile Computing and Communications Review, 2001
[10] I-Hsuan Peng and Yen-Wen Chen, “Energy consumption bounds analysis and its applications for grid based wireless sensor networks”, Journal of Network and Computer Applications, DOI: 10.1016/j.jnca.2012.04.014, May 2012
[11] Jamal N. Al-Karaki, Ahmed E. Kamal, “Routing Techniques in Wireless Sensor Networks: A Survey”, IEEE Wireless Communications, pp. 6-28, Dec. 2004
[12] Guiling Wang, Guohong Cao, and Tom La Porta, “Movement-assisted sensor deployment”, In IEEE INFOCOM 2004, June 2004
[13] Nojeong Heo and Pramod K. Varshney, “An intelligent deployment and clustering algorithm for a distributed mobile sensor network”, In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, volume 5, pp.4576–4581, Oct. 2003
[14] Saurabh Ganeriwal, Aman Kansal, and Mani B.Srivastava, “Self aware actuation for fault repair in sensor networks”, In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), May 2004.
[15] Andrew Howard, Maja J Mataric, and Gaurav S Sukhatme, “An incremental self-deployment algorithm for mobile sensor networks”, Autonomous Robots, Special Issue on Intelligent Embedded Systems, vol 13, no 2, pp.113–126, September 2002
[16] Prasan Kumar Sahoo, “Modeling and Performance Analysis of IEEE 802.15.4 MAC for Wireless Sensor Networks “, National central University, PhD Disseration, June 2009
[17] M. Cardei and L. Wu, "Coverage in wireless sensor networks", Handbook of Sensor Networks, CRC Press, chapter 19, 2004
[18] Guiling Wang, Guohong Cao, and Tom La Porta, “A bidding protocol for deploying mobile sensors”, In 11th IEEE International Conference on Network Protocol ICNP ’03, pp. 315–324, Nov 2003
[19] Maxim A. Batalin and Gaurav S. Sukhtame, “ Coverage, exploration and deployment by a mobile robot and communication network”, Telecommunication Systems Journal, Special Issue on Wireless Sensor Networks, vol.26, no. 2, pp.181–196, 2004
[20] Honghai Zhang and Jennifer C. Hou, “Maintaining sensing coverage and connectivity in large sensor networks”, Technical Report UIUDCS-R-2003-2351, Department of Computer Science, University of Illinois at Urbana Champaign, 2003
[21] T. Yan, T. He, and J. Stankovic, “Differentiated surveillance for sensor networks”, In Proceedings of the ACM SenSys ’03, Nov 2003
[22] Peter Corke, Steven Hrabar, Ronald Peterson, Daniela Rus, Srikanth Saripalli, and GauravSukhatme, “ Autonomous deployment and repair of a sensor network using an unmanned aerial vehicle”, In Proceedings of the IEEE 2004 International Conference on Robotics and Automation, Volume 4, pp. 3602–3608, May 2004
[23] Jie Jiang and Wenhua Dou, “A coverage preserving density control algorithm for wireless sensor networks”, In ADHOC-NOW’04, Springer-Verlag, pp.42–55, July 2004
[24] Di Tian and Nicolas D. Georganas, “A coverage preserving node scheduling scheme for large wireless sensor networks”, In Proceedings of the first ACM WSNA’02, Sep 2002
[25] G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated coverage and connectivity configuration for energy conservation in sensor networks”, ACM Transactions on Sensor Network, vol. 1, no.1, pp. 36–72 , 2005
[26] A. Cerpa, and D. Estrin, “ASCENT: Adaptive Self-Configuring Sensor Networks Topologies”, IEEE Transactions on Mobile Computing, vol.3, no.3, pp.272–284, 2004
[27] H. Zhang and J.C. Hou, “Maintaining Sensing Coverage and Connectivity in Large Sensor Networks”, Ad Hoc & Sensor Wireless Networks, vol. 1, no. 1, pp.89-124, 2005
[28] S. Podurl, and G.S. Sukhatme, “Constrained coverage for mobile sensor networks”, In Proceedings of the IEEE International Conference on Robotics and Automation, pp. 165–172, 2004
[29] L. Lazos, and R. Poovendran, “Stochastic Coverage in Heterogeneous Sensor Networks”, ACM Transactions on Sensor Network,vol.2, no.3, pp.325-358, 2006
[30] J. Wu, F. Dai, M. Gao and I. Stojmenovic, “On calculating power aware connected dominating sets for efficient routing in ad hoc wireless networks”, Journal of Communications and Networks, vol. 4, no. 1, pp. 59–70, March 2002
[31] S. Kumar, T. H. Lai, and J. Balogh, “On K-Coverage in A Mostly Sleeping Sensor Network”, In Proceedings of the tenth Annual International Conference on Mobile Computing and Networking (MobiCom), pp.144–158, 2004
[32] J. Wu and H. Li, “On calculating connected dominating set for efficient routing in ad hoc wireless networks”, In Proceedings of the Third International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp.7–14, 1999
[33] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocols for wireless microsensor networks”, In Proceedings of Hawaiian International Conference on Systems Science, 2000
[34] M. Cardei, and D.Z. Du, “Improving wireless sensor network lifetime through power aware organization”, ACM Wireless Networks, vol.11, no.3, pp. 333–340, 2005
[35] H. Zhang, H. Wang, and H. Feng, "A Distributed Optimum Algorithm for Target Coverage in Wireless Sensor Networks", In Proceedings of the 2009 Asia-Pacific Conference on Information Processing, 2009
[36] M. Cardei, M. T. Thai, Y. Li, and W. Wu, "Energy-Efficient Target Coverage in Wireless Sensor Networks", In INFOCOM 2005 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp.1976-1984, 2005
[37] D. Zorbas, D. Glynos, P. Kotzanikolaou, and C. Douligeris, "Solving Coverage Problems in Wireless Sensor Networks Using Cover Sets", Ad Hoc Networks, vol. 8, pp. 400-415, 2010.
[38] G. Fan and S. Jin, "A Simple Coverage-Evaluating Approach for Wireless Sensor Networks with Arbitrary Sensing Areas", Inf. Process Letter, volume 106, pp.159 - 161, 2008
[39] B. L. Don and D. Towsley, "On the Coverage and Delectability of Large-scale Wireless Sensor Networks", presented at the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks Conference, 2003.
[40] S. Megerian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, "Worst and Best-Case Coverage in Sensor Networks", IEEE Transactions on Mobile Computing, vol. 4, pp. 84-92, 2005
[41] H. Tan, Y. Wang, X. Hao, Q.-S. Hua, and F. C. M. Lau, "Arbitrary Obstacles Constrained Full Coverage in Wireless Sensor Networks", presented at the International Conference on Wireless Algorithms, Systems, and Applications, Beijing, China, Aug 2010.
[42] M. Shyam and A. Kumar, "Obstacle Constrained Total Area Coverage in Wireless Sensor Networks", CoRR abs/1001.4753, January 2010.
[43] Y. Wang, J. Gao, and Joseph S.B. Mitchell, “Boundary recognition in sensor networks by topological methods”, In proc. 12th Annual International Conference on Mobile Computing and Networking (Mobi-Com’’06), Los Angeles, California, September 2006.
[44] J. Staddon, D. Balfanz, and G. Durfe, “Efficient Tracing of Failed Nodes in Sensor Networks”, In proc. of the 1st ACM international workshop on Wireless sensor networks and applications, pp. 122 – 130, Atlanta,Georgia, USA , 2002
[45] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson, “Wireless sensor networks for habitat monitoring”, ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, September 2002.
[46] E. S. Biagioni and K. W. Bridges, “The application of remote sensor technology to assist the recovery of rare and endangered species”, International Journal of High Performance Computing, vol. 17, no.3, August 2002
[47] J. Aslam, Z. Butler, F. Constantin, V. Crespi, G. Cybenko, and D. Rus, “Tracking a moving object with a binary sensor network”, ACM SenSys, Los Angeles, November 2003
[48] H. T. Kung and D. Vlahi, “Efficient Location Tracking Using Sensor Networks”, IEEE Wireless Communications and Networking Conference (WCNC), vol. 3, pp. 1954-1961, March 2003
[49] R. Selmic, J. Kanno, J. Buchart, and N. Richardson, “Quadratic optimal control of sensor network deployment”, Cyberspace Research Workshop, Shreveport, LA, November 2007
[50 Elaine Shi and Adrian Perrig, “Designing Secure Sensor Networks”, IEEE Wireless Communications, pp. 38-43, December 2004
[51] Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, “A Survey on Sensor Networks”, IEEE Communications Magazine, pp.102-114, August 2002
[52] M. K. Watfa, and S. B. Commuri, “Power conservation approaches to the border coverage problem in wireless sensor networks”, In Proceedings of ICWN, 2006
[53] G. Wang, G. Cao, L. Porta, and W. Zhang, ”Sensor relocation in mobile sensor networks”, In Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) , 2005
[54] P. J. Wan, and C.W. Yi, “Coverage by randomly deployed wireless sensor networks”, In IEEE Transactions on Information Theory, pp.2658-2669, 2006
[55] V.D. Silva, and R. Ghrist, “Homological sensor networks”, In Notices of the American Mathematical Society, vol.54, no 1, pp.10-17, 2007
[56] R. Ghrist, and A. Muhammad, “Coverage and hole-detection in sensor networks via homology”, In Proceedings of the 4th international symposium on Information processing in sensor networks, pp.254-260, 2005
[57] S. Funke, ”Topological hole detection in wireless sensor networks and its applications”, In Proceedings of the joint workshop on Foundations of Mobile Computing, pp.44-53, 2005
[58] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Coverage problems in wireless ad-hoc sensor networks”, In Proceeding of INFCOOM, pp. 1380-1387, 2001
[59] S. Funke, and C. Klen, ”Hole detection or How much geometry hides in connectivity?”, In Proceeding of the 22nd ACM Sympos. on Computational Geometry, pp.377-385, 2006
[60] K.-Y. Hsieh, and J.-P. Sheu, ”Hole detection and boundary recognition in wireless sensor networks”, In Proceedings of IEEE 20th International Symposium on Personal, Indoor and Mobile Radio Communications, 2009
[61] P. Soreanu, Z. Volkovich, and Z. Barzily, ”Energy-Efficient Predictive Jamming Holes Detection Protocol for Wireless Sensor Networks”, In Proceedings of Second International Conference on Sensor Technologies and Application (SENSORCOMM), pp. 306-311, 2008
[62] F. Yu., Y. Choi, S. Park, E. Lee, Y. Tian, M. Jin, and S.-H. Kim, ”Anchor Node Based Virtual Modeling of Holes in Wireless Sensor Networks”, In Proceedings of IEEE International Conference on Communications (ICC), pp.3120-3124, 2008
[63] C. Zhang, Y. Zhang, and Y. Fang, ”Detecting Coverage Boundary Nodes in Wireless Sensor Networks”, In Proceedings of IEEE International Conference on Networking, Sensing and Control, 2006.
[64] M. K. Watfa, and S. Commuri, “Energy-efficient approaches to coverage holes detection in wireless sensor networks”, In Proceedings of IEEE International Symposium on Intelligent Control, pp.131-136, 2006
[65] P. Corke, R. Peterson, and D. Rus, “Finding holes in sensor networks”, In Proceedings of the Workshop on Omniscient Space: Robot Control Architecture Geared toward Adapting to Dynamic Environments at ICRA, 2007
[66] Y. Bejerano, ”Simple and Efficient k-Coverage Verification without Location Information”, In Proceedings of IEEE 27th Conference on Computer Communications (INFOCOM), pp.291-295, 2006
[67] Li, Xiaoyun and Hunter, K.David, “Distributed Coordinate-free Hole Recovery”, In Proceedings of ICC, pp.189-194, 2008
[68] Xia Zhang and Cheng Wang, “Distributed Coverage Preserving Algorithm with Connectivity Information”, In Proceeding of the 2nd International Conference on Power Electronics and Intelligent Transportation System, pp. 29 -33, Dec. 2009.
[69] B. Liu, P. Brass, O. Dousse, P. Nain, and D.Towsley, “Mobility improves coverage of sensor networks”, In Proceedings of the 6th ACM International Symposium on Mobile ad hoc networking and computing, Urbana Champaign, Illinois, May 2005
[70] Hwa-Chun Ma, Prasan Kumar Sahoo and Yen-Wen Chen, “Computational Geometry based Distributed Coverage Hole Detection Protocol for the Wireless Sensor Networks”, Journal of Network and Computer Applications, vol. 34 , pp. 1743–1756 , Sept. 2011.
[71] The Network Simulator (NS), URLhttp://www.isi.edu/nsnam/ns/

指導教授

陳彥文、沙庫瑪
(Yen-Wen Chen、Prasan Kumar Sahoo)

審核日期

2012-7-11

推文