無線感測器網路(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.

Contents	III
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
2.2.1.1  Sensing Model	18
2.2.1.2  Communication Model	19
2.2.1.3  Coverage Model	21
2.2.2  Coverage based on Exposure Paths	23
2.2.2.1  Minimal exposure path: Worst-case coverage	23
2.2.2.2  Maximal exposure path: Best-case coverage	26
2.2.2.3  Maximal breach path: Worst-case coverage	27
2.2.2.4  Maximal support path: Worst-case coverage	28
2.2.3  Coverage based on Sensor Deployment Strategies	29
2.2.3.1  Imprecise detection algorithm (IDA)	29
2.2.3.2  Potential field algorithm (PFA)	30
2.2.3.3  Distributed self-spreading algorithm (DSSA)	32
2.2.3.4  Bidding Protocol (BIDP)	33
2.2.3.5  Energy-efficient Coverage Hole Self-repair in Mobile Sensor Networks (DSEPA)	33
2.2.3.6  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
Bibliography	70
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

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	I. F. Akyildiz, W. Su, Y. Sankasubramaniam, and E. Cayirci, “Wireless Sensor Networks: A Survey”. Computer Networks, Vol. 38, pp.393–422, 2002.
[15]	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.
[16]	G. Boriello and R. Want, “Embedded Computation Meets the World Wide Web”.  ACM Communications, Vol. 43, Issue 5, pp. 59–66, 2000.
[17]	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.
[18]	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.
[19]	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.
[20]	G. J. Pottie and W. J. Kaiser, “Embedding the Internet: Wireless Integrated Network Sensors.” ACM Communications, Vol. 43, Issue 5, pp. 51–58, 2000.
[21]	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.
[22]	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.
[23]	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.
[24]	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.
[25]	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.
[26]	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.
[27]	P. Gupta and P. R. Kumar, “The capacity of wireless networks.” IEEE Transactions on Information Theory, Vol. 46, Issue 2, pp.388–404, 2000.
[28]	D. W. Gage, “Command control for many-robot systems.” Unmanned System Magazine. Vol. 10, Issue 4, pp. 28-34, 1992.
[29]	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.
[30]	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.
[31]	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.
[32]	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.
[33]	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.
[34]	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.
[35]	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.
[36]	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.
[37]	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.
[38]	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.
[39]	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.
[40]	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.
[41]	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.
[42]	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