臺灣博碩士論文加值系統

無線感測器網路在許多的應用中，都會要求感測器的偵測範圍能夠涵蓋整個網路。若網路中存在無法偵測的空洞，可能會對使用者造成不同程度的傷害。在以往的研究中，有著作提出感測器能量的消耗有地域集中的性質。此一特性會造成網路上鄰近的節點有相近程度的耗電量。如此將造成網路上即將耗盡電量的節點會集中在某一區域，而形成偵測的空洞。由於此一空洞是集中在某一區域，會造成許多偵測事件的遺失。此時整個無線感測器網路的功能性就不能夠達成。這篇論文中，我們提出了一個嶄新的網路模型和一個演算法可以解決網路電量空洞的問題。我們利用分散式演算法找出網路上電量空洞的範圍，並且透過有效率的規劃讓行動感測器節點可以移動到電量空洞的位置。透過我們所設計的演算法，可以避免擺放許多感測器節點的龐大成本。模擬效能的實驗中，我們的協定可以減少控制封包的負擔，達到相當高的行動感測器節點利用率。

Many applications in wireless sensor networks require maintaining full sensing coverage in target area with time went by. Coverage hole may cause injuries to surveillance applications. Because of the energy consumption spatial locality, neighboring sensor nodes deplete their energy off almost simultaneously. These neighboring sensor nodes are called energy hole. Energy holes may cause large coverage hole, and any events occurred within coverage hole will not be detected by sensor networks. In this circumstance, the requirements of surveillance applications can not be satisfied. In this paper, an algorithm is proposed to resolve the energy hole problem. The distribute algorithm can cover energy holes by using mobile sensors. Mobile sensors heal energy hole in parallel way to avoid the large cost of manual sensor deployment. The energy hole expansion problem is overcome by hexagon mechanism. We evaluate the performance of the proposed scheme through simulations. The simulation results show that our proposed protocol has low control message overhead on energy hole information collection and high utilization of mobile sensors about healing energy hole.

Contents

1. Introduction 1
2. Related Works 5
3. Backgrounds and Basic Concepts 10
3.1 Energy Consumption Spatial Locality 10
3.2 Reasons for Applying Mobile Sensors 12
3.3 Protocol Overview 14
3.4 Network Model 15
4. Energy Hole Healing Protocol 17
4.1 Role Determination 17
4.2 Energy Hole Information Collection 23
4.3 Energy Hole Healing 27
4.4 Energy Hole Expansion Phenomenon 34
4.5 Energy Depletion of Mobile Sensors 36
4.6 Discussions 38
5. Simulation 47
5.1 Effectiveness of Modified Right-Hand Rule 48
5.2 Effectiveness of Mobile Sensors to Heal Energy Hole 49
5.3 Overcome Energy Hole Expansion 51
5.4 Effectiveness of Hexagon Placement to Overcome Energy Hole Problem 53
6. Conclusion 55
7.References 56

[1]Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, “A Survey on Sensor Networks,” IEEE Communications Magazine, Volume 40, issue 8, pp.102-114, August 2002.
[2]Yonggang Jerry Zhao, Ramesh Govindan, and Deborah Estrin, “Residual Energy Scan for Monitoring Wireless Sensor Networks,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC 2002), Volume 1, pp.356-362, Orlando, USA, March 2002.
[3]Guiling Wang, Guohong Cao, and Tom La Porta, “Movement-Assisted Sensor Deployment,” in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), Volume 4, pp.2469-2479, Hong Kong, March 2004.
[4]Guiling Wang, Guohong Cao, Tom La Porta, and Wensheng Zhang, “Sensor Relocation in Mobile Sensor Networks,” in Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005), Miami, USA, March 2005.
[5]Guiling Wang, Guohong Cao, and Tom La Porta, “A Bidding Protocol for Deploying Mobile Sensors,” in Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP 2003), pp.315-324, Atlanta, Georgia, USA, November 2003.
[6]Guiling Wang, Guohong Cao, and Tom La Porta, “Proxy-Based Sensor Deployment for Mobile Sensor Networks,” in Proceedings of the 1st IEEE International Conference on Mobile Ad hoc and Sensor Systems (MASS 2004), pp.493-502, Florida, USA, October 2004.
[7]Saurabh Ganeriwal, Aman Kansal, and Mani B. Srivastava, “Self Aware Actuation for Fault Repair in Sensor Networks,” in Proceedings of the 2004 IEEE International Conference on Robotics and Automation (ICRA 2004), Volume 5, pp.5244-5249, New Orleans, LA, USA, April 2004.
[8]Joengmin Hwang, David H. C. Du, and Ewa Kusmierek, “Energy Efficient Organization of Mobile Sensor Networks,” in Proceedings of IEEE International Conference on Parallel Processing Workshops (ICPP Workshops 2004), pp.84-91, Montreal, Canada, August 2004.
[9]Archana Sekhar, B.S. Manoj, and C.Siva Ram Murphy, “Dyanmic Coverage Maintenance Algorithms for Sensor Networks with Limited Mobility,” in Proceedings of the 3rd IEEE International Conference on Pervasive Computing and Communications (PerCom 2005), Kauai Island, Hawaii, USA, March 2005.
[10]Seapahn Meguerdichian, Farinaz Koushanfar, Miodrag Potkonjak, and Mani B. Srivastava, “Coverage Problems in Wireless Ad-hoc Sensor Network,” in Proceedings of 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), Volume 3, pp.22-26, Alaska, USA, April 2001.
[11] Chi-Fu Huang and Yu-Chee Tseng, “The Coverage Problem in a Wireless Sensor Network,” in Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications (WSNA 2003), pp.115-121, San Diego, California, USA, September 2003.
[12]Di Tian and Nicolas D. Georganas, “A Coverage-Preserving Node Scheduling Scheme for Large Wireless Sensor Networks,” in Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA 2002), pp.32-41, Atlanta, Georgia, USA, September 2002.
[13] Di Tian and Nicolas D. Georganas, “A Node Scheduling Scheme for Energy Conservation in Large Wireless Sensor Networks,” Journal of Wireless Communications and Mobile Computing Journal, pp.271-290, May 2003.
[14]Fan Ye, Gary Zhong, Jesse Cheng, Songwu Lu, and Lixia Zhang, “PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks,” in Proceedings of 23rd IEEE International Conference on Distributed Computing Systems (ICDCS 2003), pp.28-37, Rhode Island, USA, May 2003.
[15]Ting Yan, Tian He, and John A. Stankovic, “Differentiated Surveillance for Sensor Networks,” in Proceedings of the 1st ACM International Conference on Embedded Networked Sensor Systems (SenSys 2003), pp.51-62, Los Angeles, California, USA, November 2003.
[16]Chi-Fu Huang, Li-Chu Lo, Yu-Chee Tseng, and Wen-Tsuen Chen, “Decentralized Energy-Conserving and Coverage-Preserving Protocols for Wireless Sensor Networks,” in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS 2005), Kobe, Japan, May 2005.
[17]Xiaorui Wang, Guoliang Xing, Yuanfang Zhang, Chenyang Lu, Robert Pless, and Christopher Gill, “Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks,” in Proceedings of the 1st ACM International Conference on Embedded Networked Sensor Systems (SenSys 2003), pp.28-39, Los Angeles, California, USA, November 2003.
[18]Honghai Zhang and Jennifer C. Hou, “Maintaining Sensing Coverage and Connectivity in Large Sensor Networks,” in NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, February 2004.
[19]Chih-fan Hsin and Mingyan Liu, “Network Coverage Using Low Duty-Cycled Sensors: Random & Coordinated Sleep Algorithms,” in Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN 2004), pp.433-442, Berkeley, California, USA, April 2004.
[20] Guoliang Xing, Chenyang Lu, Robert Pless, and Joseph A. O'Sullivan, “Co-Grid: An Efficient Coverage Maintenance Protocol for Distributed Sensor Networks,” in Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN 2004), pp.414-423, Berkeley, California, USA, April 2004.
[21]Chao Gui and Prasant Mohapatra, “Power Conservation and Quality of Surveillance in Target Tracking Sensor Networks,” in Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MobiCom 2004), pp.129-143, Philadelphia, USA, September, 2004.
[22] You-Chiun Wang, Chun-Chi Hu, and Yu-Chee Tseng, “Efficient Deployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks,” in Proceedings of the 1st IEEE International Conference on Wireless Internet (WICON 2005), Budapest, Hungary, July 2005.
[23] Brad Karp and H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” in Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom 2000), pp.243-254, Boston, Massachusetts, USA, August 2000.
[24] Qingfeng Huang, Chengyang Lu, and Gruia-Catalin Roman, “Reliable Mobicast via Face-Aware Routing,” in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), Volume 3, pp.2108-2118, Hong Kong, March 2004.
[25]Gabriel T. Sibley, Mohammad H. Rahimi, and Gaurav S. Sukhatme, “Robomote: A Tiny Mobile Robot Platform for Large-Scale Sensor Networks,” in Proceedings of the 2002 IEEE International Conference on Robotics and Automation (ICRA 2002), Volume 2, pp.1143-1148, Washington, DC, USA, May 2002.
[26]Mohammad Rahimi, Hardik Shah, Gaurav S. Sukhatme, John Heidemann, and Deborah Estrin, “Studying the Feasibility of Energy Harvesting in a Mobile Sensor Network,” in Proceedings of the 2003 IEEE International Conference on Robotics and Automation (ICRA 2003), Volume 1, pp.19-24, Taipei, Taiwan, September 2003.
[27]Sze-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, and Jang-Ping Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” the Special Issue of ACM/Kluwer Wireless Networks, Volume 8, No. 2, pp.153-167, March 2002.
[28]Sze-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, and Jang-Ping Sheu, “The Broadcast Storm Problem in a Mobile Ad hoc Network,” in Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom’99), pp.151-162, Seattle Washington, USA, August 1999.
[29] Qing Cao, Tarek Abdelzaher, Tian He, and John Stankovic, “Towards Optimal Sleep Scheduling in Sensor Networks for Rare-Event Detection,” in Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN 2005), Sunset Village, Los Angeles, USA, April 2005.
[30] Chao Gui and Prasant Mohapatra, “Virtual Patrol: A New Power Conservation Design For Surveillance Using Sensor Networks,” in Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN 2005), Sunset Village, Los Angeles, USA, April 2005.
[31]Jang-Ping Sheu, Po-Wen Cheng, and Kun-Ying Hsieh, “Design and Implementation of a Smart Mobile Robot,” in Proceedings of the 1st IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob 2005), Montreal, Canada, August 2005.