||Grid-based hole recovery mechanism in hybrid wireless sensor networks
||Department of Computer Science and Information Engineering
hybrid sensor network
||無線感測器網路(Wireless Sensor Networks, WSNs)其技術可廣泛應用在許多領域中，尤其是環境監測。然而，由於部署無線感測器節點時的不平均，或有障礙物例如湖和山丘的存在，或感測器節點的電量耗盡與被外力破壞等因素，進而造成無線感測器網路中存在著空洞(Hole)，而這些空洞會使無線感測器網路的效能降低。因此，如何找出這些空洞的位置，並利用這些空洞位置所獲得的資訊進行空洞修復，提升無線感測器網路之效能，是一個相當重要的研究議題。
||In wireless sensor networks, the nodes are typically empowered with scarce energy resource and limited computing power. The network can not get fully connectivity due to the randomly deploy static sensor nodes which may cause the hole problem. However, the network performance could be improved by the high coverage ratio because of saving the energy for transmitting. Hence, the hole problem is one of the important issues in wireless sensor networks.
We proposed a hole recovering mechanism based on grid architecture with mobile sensor nodes. The virtual force theory is used for determining which mobile sensor node should recover the hole. The proposed mechanism could efficiently maintain high coverage ratio and prolong the entire network lifetime. The simulation results demonstrate that our mechanism indeed recover routing holes and prolong the network lifetime.
List of Figures V
List of Tables VI
1. Introduction 1
2. Related Works 4
2.1 Wireless Sensor Networks 4
2.1.1 Hardware Components 6
2.1.2 Charateristic Requirements 9
2.1.3 Salient Features of Sensor Networks 11
2.1.4 Common Design Problems in WSNs 14
2.2 Coverage and Connectivity Issues in Wireless Sensor Networks 17
2.2.1 Mathmatical Frameworks 18
220.127.116.11 Sensing Model 18
18.104.22.168 Communication Model 19
22.214.171.124 Coverage Model 21
2.2.2 Coverage based on Exposure Paths 23
126.96.36.199 Minimal exposure path: Worst-case coverage 23
188.8.131.52 Maximal exposure path: Best-case coverage 26
184.108.40.206 Maximal breach path: Worst-case coverage 27
220.127.116.11 Maximal support path: Worst-case coverage 28
2.2.3 Coverage based on Sensor Deployment Strategies 29
18.104.22.168 Imprecise detection algorithm (IDA) 29
22.214.171.124 Potential field algorithm (PFA) 30
126.96.36.199 Distributed self-spreading algorithm (DSSA) 32
188.8.131.52 Bidding Protocol (BIDP) 33
184.108.40.206 Energy-efficient Coverage Hole Self-repair in Mobile Sensor Networks (DSEPA) 33
220.127.116.11 On-demand Deployment Algorithm for a Hybrid Sensor Network (On-demand) 34
3. Grid-based hole recovery mechanism 35
3.1 Virtual Force Formulation 39
3.2 Network Initiation Phase 40
3.2.1 Griding Phase 40
3.2.2 Hole Detecting Phase 47
3.2.3 Hole Recovering Phase 53
3.3 Network Maintaining Phase 57
4. Simulation and Results 61
4.1 Simulation Environment 61
4.2 Simulation Results and Analysis 63
5. Conclusion and Future Works 68
Appendix A. Publication List 75
Appendix B. “Grid-based Mobile Target Tracking Mechanism in Wireless Sensor Networks” JOURNAL OF COMMUNICATIONS 79
Appendix C. “QPPS : Qos Provision Packet Scheduling Algorithm in High Speed Downlink Packet Access” JOURNAL OF WSEAS TRANSACTIONS ON COMMUNICATIONS 87
List of Figures
Figure 2-1: Main sensor node hardware components 6
Figure 2-2: Example of probabilistic sensing model 19
Figure 2-3: Example of communication model 20
Figure 3-1: System framework 37
Figure 3-2: Example of system environment 38
Figure 3-3: Relation between R and d 41
Figure 3-4: Example of numbering grid 42
Figure 3-5: Example of gridding network scenario 44
Figure 3-6: Procedures of gridding phase 45
Figure 3-7: Procedures of message forwarding 47
Figure 3-8: Procedures of hole detecting 51
Figure 3-9: Example of completing hole detecting phase 52
Figure 3-10: Procedures of selecting MNs 55
Figure 3-11: Procedures of network maintaining phase 58
Figure 4-1: Message complexity 64
Figure 4-2: Coverage ratio 65
Figure 4-3: Energy consumption 66
Figure 4-4: System lifetime 67
List of Tables
Table 3-1: Grid Information Table 43
Table 3-2: Det_Hole_Message Format 48
Table 3-3: Det_Hole_Ack Format 49
Table 3-4: Hole Grid Information Table 53
Table 4-1: Simulation parameters 62
|| E. S. Biagioni and K. W. Bridges, “The application of remote sensor technology to assist the recovery of rare and endangered species”, High Performance Computing Applications, Vol. 17, No. 3, August 2002, pp. 315-324.
 A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson, “Wireless sensor networks for habitat monitoring”, Proceedings of ACM Wireless Sensor Networks and Applications, Atlanta GA, September 2002, pp. 88-97.
 L. Schwiebert, S. K. S. Gupta, and J. Weinmann, “Research challenges in wireless networks of biomedical sensors”, Proceedings of ACM Sigmobile, Rome, Italy, July 2001, pp 151-165.
 J. Aslam, Z. Butler, F. Constantin, V. Crespi, G. Cybenko, and D. Rus, “Tracking a moving object with a binary sensor network”, Proceedings of the ACM Embedded Networked Sensor Systems, Los Angeles, USA, November 2003, pp. 150-161.
 H. T. Kung and D. Vlah, “Efficient Location Tracking Using Sensor Networks”, Proceedings of IEEE Wireless Communications and Networking, New Orleans, Louisiana, USA, Vol. 3, March 2003, pp. 1954-1961.
 J. F. Chen, Y. H. Wang, K. F. Huang, T. W. Chang, “Grid-based Mobile Target Tracking Mechanism in Wireless Sensor Networks”, Journal of Communications, Vol. 5, No. 6, June 2010, pp. 475-482.
 A. Agah, S. K. Das, K. Basu, and M. Asadi, “Intrusion detection in sensor networks: a non-competitive game approach”, Proceedings of IEEE Vehicular Technology, Los Angeles, USA, Vol. 4, Fall 2004, pp. 343-346.
 R. Roman, J. Zhou, and J. Lopez, “Applying intrusion detection systems to wireless sensor networks”, Proceedings of IEEE Consumer Communications and Networking, Las Vegas, USA, Vol. 1, January 2006, pp. 640-644.
 G. T. Sibely, M. H. Rahimi, and G. S. Sukhatme, “Robomote: A Tiny Mobile Robot Platform for Large-Scale Sensor Networks”, Proceedings of IEEE Robotics and Automation, Washington DC, USA, May 2002, pp. 1143-1148.
 Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization Based on Virtual Forces”, Proceedings of IEEE INFOCOM, San Franciso, USA, Vol. 2, March 2003, pp. 1293-1302.
 A. Howard, M.J. Mataric, and G.S. Sukhatme, “An Incremental Self-Deployment Algorithm for Mobile Sensor Networks”, Autonomous Robots, Vol. 13, No. 2, 2003, pp 113-126.
 A. Howard, M.J. Mataric, and G.S. Sukhatme, “Mobile Sensor Networks Deployment Using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem”, Proceedings of Distributed Autonomous Robotics Systems, Fukuoka, Japan, June 2002, pp. 299-308.
 M. Locateli and U. Raber, “Packing equal circles in a square: a deterministic global optimization approach”, Discrete Applied Mathematics, Vol. 122, October 2002, pp. 139-166.
 I. F. Akyildiz, W. Su, Y. Sankasubramaniam, and E. Cayirci, “Wireless Sensor Networks: A Survey”. Computer Networks, Vol. 38, pp.393–422, 2002.
 G. Asada, M. Dong, T. S. Lin, F. Newberg, G. Pottie, and W. J. Kaiser, “Wireless Integrated Network Sensors: Low Power Systems on a chip”. Proceedings of 24th European Solid State Circuits Conference, Netherlands, September 1998, pp. 9-12.
 G. Boriello and R. Want, “Embedded Computation Meets the World Wide Web”. ACM Communications, Vol. 43, Issue 5, pp. 59–66, 2000.
 J. Burrell, T. Brooke, and R. Beckwith, “Vineyard Computing: Sensor Networks in Agricultural Production.” IEEE Pervasive Computing, Vol. 3, Issue 1, pp. 38–45, 2004.
 A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao, “Habitat Monitoring: Application Driver for Wireless Communications Technology.” ACM Special Interest Group on Data Communication, Vol. 31, No. 2, pp. 20-41, Apr. 2001.
 R. Szewczyk, E. Osterweil, J. Polastre, M. Hamilton, A. Mainwaring, and D. Estrin, “Habitat Monitoring with Sensor Networks.” ACM Communication, Vol. 47, Issue 6, pp.34–40, 2004.
 G. J. Pottie and W. J. Kaiser, “Embedding the Internet: Wireless Integrated Network Sensors.” ACM Communications, Vol. 43, Issue 5, pp. 51–58, 2000.
 V. Raghunathan, C. Schurgers, S. Park, and M. B. Srivastava, “Energy-Aware Wireless Microsensor Networks.” IEEE Signal Processing Magazine, Vol. 19, pp. 40–50, 2002.
 J. M. Kahn, R. H. Katz, and K. S. J. Pister, “Next Century Challenges: Mobile Networking for “Smart Dust”.” Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking, Seattle, WA, pp. 271-278, August 1999.
 J. M. Rabaey, M. J. Ammer, J. L. da Silva, D. Patel, and S. Roundy, “PicoRadio Supports Ad Hoc Ultra-Low Power Wireless Networking.” IEEE Computer, Vol. 33, Issue 7, pp. 42–48, 2000.
 W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks.” IEEE Transactions on Wireless Communications, Vol. 1, Issue 4, pp. 660-670, 2002.
 S. Kulkarni, A. Iyer, and C. P. Rosenberg, “An address-light, integrated mac and routing protocol for wireless sensor networks.” IEEE/ACM Transactions on Networking, Vol. 14, Issue 4, pp.793–806, 2006.
 C. Savarese, J. M. Rabaey, and J. Beutel, “Locationing in distributed ad-hoc wireless sensor networks.” Proceedings of the USENIX Technical Annual, pp. 317-327, May 2002.
 P. Gupta and P. R. Kumar, “The capacity of wireless networks.” IEEE Transactions on Information Theory, Vol. 46, Issue 2, pp.388–404, 2000.
 D. W. Gage, “Command control for many-robot systems.” Unmanned System Magazine. Vol. 10, Issue 4, pp. 28-34, 1992.
 S. Megerian, F. Koushanfar, G. Qu, G. Veltri, and M. Potkonjak, “Exposure in wireless sensor networks: Theory and practical solutions.” Wireless Networks, Vol. 8, Issue 5, pp.443-454, 2002.
 Y. Zou and K. Chakrabarty, “Sensor deployment and target localization in distributed sensor networks.” IEEE Embedded Computer System, Vol. 3, Issue 1, pp.61-91, 2004.
 S. Megerian, F. Koushanfar, G. Qu, G. Veltri, and M. Potkonjak, “Exposure in wireless sensor networks: Theory and practical solutions.” Wireless Networks, Vol. 8, Issue 5, pp. 443–454, 2002.
 X.-Y. Li, P.-J. Wan, and O. Frieder, “Coverage in wireless ad-hoc sensor networks.” IEEE Transaction Computer, Vol. 52, pp.753–763, 2003.
 S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage problems in wireless ad-hoc sensor networks.” Proceeding of IEEE Computer Communications, Anchorage, AK, pp. 115–121, April 2001.
 G. Veltri, Q. Huang, G. Qu, and M. Potkonjak, “Minimal and maximal exposure path algorithms for wireless embedded sensor networks.” Proceeding of Embedded Networked Sensor Systems, Los Angeles, pp. 40–50, Nov. 2003.
 S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak, “Exposure in wire less ad-hoc sensor networks.” Proceeding of Mobile Computing and Networking, Rome, Italy, pp. 139–150, July 2001.
 S. S. Dhilon, K. Chakrabarty, and S. S. Iyengar, “Sensor placement for grid coverage under imprecise detections.” Proceeding of 5th Information Fusion, Annapolis, MD, pp. 1-10, July 2002.
 S. Poduri and G. S. Sukhatme, “Constrained coverage in mobile sensor networks.” Proceeding of Robotics and Automation, New Orleans, LA , pp. 40-50, April–May 2004.
 N. Heo and P. K. Varshney, “A distributed self-spreading algorithm for mobile wireless sensor networks.” Proceeding of IEEE Wireless Communications and Networking, New Orleans, LA, pp. 1597-1602, March 2003.
 G. Wang, G. Cao, and T. LaPorta, “A bidding protocol for deploying mobile sensors.” Proceeding of IEEE Network Protocols, Atlanta, GA, pp. 80-91, Nov. 2003.
 R. Wu, J. He, T.J. Li, H. S, “Energy-efficient coverage hole self-repair in mobile sensor network.” Proceeding of IEEE New Trends in Information and Service Science, Beijing, China, pp. 1297-1302, June 2009.
 L.C. Shiu, C.Y. Lee, T.W. Song, and C.S. Yang “On-demand deployment algorithm for a hybrid sensor network.” Proceeding of IEEE Embedded and Ubiquitous Computing, Shanghai, China, pp. 697 – 702, Dec. 2008.
 Minghua Yang, Yuanda Cao, Li Tan, Jiong Yu, “A New Self-Deployment Algorithm in Hybrid Sensor Network.” Proceeding of IEEE Intelligent Information Technology Application, Shanghai, China, pp. 268-272, Dec. 2008