在WSNs中，大型空洞的產生，將影響資料蒐集的準確性，並阻礙sensor間的通訊，因此近年來已有多種演算法，利用一群mobile sensor集體移動，以修復網路空洞及解決空洞造成之通訊問題，然而，這些演算法必須具備額外的mobile sensor才可修復網路上的空洞，以達到full coverage的目的。當網路中沒有多餘的mobile sensor存在時，有部分研究利用mobile sensor移動的特性，使網路中未被sensor覆蓋的區域，在一特定時間內可覆蓋以達到temporal full coverage的目的，但整個網路中只有少數mobile sensor需因移動而耗費電量，如此將造成sensor間耗電量不平衡，進而縮短生命期或造成網路不連結的問題。為達到full coverage的目的並強化追蹤物件的品質，本論文在不具任何多餘sensor的環境下發展Basic，Forward-Only及Any-Direction等三種分散式空洞移動法則，在總移動耗電量最小或耗電量平衡考量下，將空洞移至一事先定義好的位置，使空洞在一特定時間內達到full coverage。實驗結果顯示，本論文所提出的空洞搬遷技術可強化WSN中的coverage並平衡所有sensor的移動耗電量。

Coverage is one of the most important issues in Wireless Sensor networks (WSNs). In a WSN, the existence of big coverage holes may reduce the accuracy of data collection and the efficiency of communication. A class of algorithms that relocate a group of mobile sensors to cover the existing hole has been proposed in recent years. However, the full coverage purpose only can be achieved when the surplus mobile sensors contribute a larger coverage area than the hole size. When there is no surplus mobile sensor to cover the big hole, some other works utilize the mobile sensor to move the hole from one location to another and therefore achieve the full coverage purpose during a fixed time interval. However, only some mobile sensors participate in the hole-movement task, resulting in an energy-unbalanced WSN. This thesis considers a mobile WSN that contains a big hole but there is no surplus mobile sensor. To achieve the full coverage purpose or enhance the tracking quality, three distributed algorithms are proposed for moving the existing big coverage hole to a predefined location. Firstly, the sink chooses a promising direction for hole movement. Then the Basic, Forward-only and Any-Direction movement mechanisms are proposed to move the hole along the promising direction in a manner of minimizing the total power consumption or balancing the power consumption of the given WSN. Simulation results reveal that the proposed Hole-movement mechanisms enhance the coverage of WSN and balance the power consumption of mobile sensor nodes.

Contents
 
1   Introduction……………………………………………….………….1
2   Related Work……………………………………………….………..5 
3   Hole-Movement Strategies…………………………………………..9
3.1: Application Scenarios and Motivation for Hole-Movement……9
3.2: Network Environment and Problem statement………………...10
3.2.1: Network Environment………………………………….10
3.2.2: Problem Formulation…………………………………...11
3.3: Energy-balanced hole-movement protocols…………………...13
3.3.1: Direction Determination Phase…………………………15
3.3.2: Hole Moving Phase……………………………………..17
A.  Basic movement mechanism………………………18
B.  Forward-Only movement mechanism……………..21
C.  Any-Direction movement mechanism…………….29
4   Complexity Analysis and Tradeoff of The Proposed Strategies... 40
A.  Performance Analysis…………………………..…40
B.  Optimal movement for deterministic constraint in the maximal power consumption……………………..44
5   Performance Evaluations…………………………………………..48
A.  The maximal power consumption…………………………49
B.  The total power consumption…………………………...…51
C.  The balanced index……………………………………...…52
D.  Temporal coverage……………………………………...…54
6   Conclusions and Future Work…………………….………………56
References………………………………………………………………57
Appendix A   Conference Version…………………………….………59




List of Figures
1     The optimal deployment that minimizes the overlap region but maintains the full coverage………………………………………….6
2     Cascaded movement……………….……………..……………….…7
3     A   big hole moved with distance x………...….…………….…12
4    (a) Sensor Si has six neighbors, including Si.UL, Si.Up, Si.UR, Si.DR, Si.Down, Si.DL. (b) Sensor Si has six moving directions ….…....…14
5    (a) Hole moves one hop along the direction which is perpendicular to the shorter side of the coverage hole. (b) Holw moves one hop along the direction which is perpendicular to the longer side of the coverage hole……………….……………..……………….………17
6     An example of the Basic movement mechanism…………………...20
7     An example of the Basic movement mechanism with size  ......20
8     The moving trajectory by applying the Forward-Only movement mechanism on the big hole with size  .........................................22
9    A round consists of three sections: (1) exchange hop information (2) determine moving direction (3) moving…………….........................23
10    An example for illustrating the Forward-Only movement mechanisms…...................................................................................28
11   Algorithm of the Forward-Only movement.......................................29 
12   The moving trajectory by applying the Any-Direction movement mechanism on the big hole size  …..……...................................30
13   The movement priority of the hole cell h which belongs to the left side of the big hole is labeled on each detector.................................32 
14   Two cases that the detector implements the Rule 3 of the Any-Direction movement mechanism………………...............................35
15   Two cases that the detector implements the Rule 4 of the Any-Direction movement mechanism……………...................................37
16   An Example of the Any-Direction movement mechanism…………38
17   Algorithm of the Any-Direction movement……………..................39
18   The migrating order of hole cells that they leave from their initial locations of a big hole with size …………….............................42
19   Two examples show who will help the last moved hole cell migrate…………………………………………………..………….43
20   Performance evaluation of the five different hybrid movement strategies that apply the Forward-Only movement mechanism first. The evaluation compares the total power consumption of the five strategies……………………………………………………...…….46
21   Performance evaluation of the five different hybrid movement strategies that apply the Basic mechanism first. The evaluation compares the total power consumption of the five strategies……...47
22   Performance evaluation of the five different hybrid movement strategies that apply the Basic mechanism first. The measurement compares the maximal power consumption of all movers for the five strategies…………………………………………………………....47
23   The maximal power consumption of movers with different big hole size by moving a fixed distance……………………….………..….50 
24   Performance evaluation of the three proposed movement mechanisms in terms of the maximal power consumption of movers with fixing the height of the big hole…………………………………………...51
25   Performance evaluation of the three proposed movement mechanisms in terms of the total power consumption of movers with fixing moving distance of the big hole…………........................................52
26   Performance evaluation of the three proposed movement mechanisms in terms of balanced index with fixing moving distance of the big hole……………………………………............................................53
27   Performance evaluation of five different movement mechanisms in terms of balanced index………………............................................54
28   Performance evaluation of the three proposed movement mechanisms in terms of the total power consumption with a fixed the hole sweep area…………………........................................................................55
 




List of Tables
1	The forbidden moving direction of the last moving direction…..…..37
2    Simulation parameters……………………………………………....49

[1]	G. J. Pottie, and W. J. Kaiser, “Wireless Integrate Network Sensors,” Communications of the ACM, vol. 43, no. 5, pp. 551-558, May 2002.
[2]	D. Estrin, L. Girod, G. Pottie, and M. Strivastava, “Instrumenting the World With Wireless Sensor Networks,” International Conference of Acoustics, Speech, and Signal Processing (ICASSP), vol. 4, pp. 2033-2036 May 2001.
[3]	D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next century challenges: Scalable coordination in sensor networks,” IEEE/ACM Mobicom’99, pp. 263-270, Aug 1999.
[4]	A. Chandrakasan, R. Amritaharajah, S. Cho, J. Goodman, G. Konduri, J. Kullik, W. Rabiner, and A. Wang, “Design considerations for distributed microsensor systems,” IEEE Custom Integrated Circuits Conference, pp. 279-286, 1999.
[5]	S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage Problem in Wireless Ad-Hoc Sensor Networks,” IEEE INFOCOM, vol. 3, pp. 1380-1387, April 2001.
[6]	S. Slijepcevic and M. Potkonjak, “Power Efficient Organization of Wireless Sensor Networks,” Pervasive Computing and Communications Wirkshop (PerCom), pp. 406-410, March 2005.
[7]	H. O. Sanli and H. Cam, “Energy Efficient Differentiable Coverage Service Protocols for Wireless Sensor Networks,” IEEE International Conference on Communications (ICC), pp. 472-476, 2001.
[8]	G. Wang, G. Cao and T. La Porta, “A Bidding Protocol for Deploying Mobile Sensors,” The 11th IEEE International Conference on Network Protocol, pp. 315-324, Nov. 2003.             
[9]	J. Hwang, D. H. C. Du and E. Kusmierek, “Energy Efficient Organization of Mobile Sensor Networks,” IEEE International Conference on Parallel Processing Workshop, pp. 84-91, 2004.           
[10]	Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Transactions on Embedded Computing Systems (TECS), vol. 3, pp. 61-91, 2004.               
[11]	G. Wang, G. Cao, and T. L. Porta, “Movement-Assisted Sensor Deployment,” IEEE Infocom, vol. 4, pp. 2469-2479, March 2004.               
[12]	X. Shan and J. Tan, “Mobile Sensor Deployment for a Dynamic Cluster-based Target Tracking Sensor Network,” IEEE International Conference on Intelligent Robots and Systems, pp. 1452-1457, Aug 2005.
[13]	M. Zhang, X. Du, and K. Nygard, “Improving Coverage Performance in Sensor Networks by using Mobile Sensors,” IEEE MILCOM, pp. 17-20, Oct 2005.  
[14]	C. Gui, and P. Mohapatra, “Virtual Patrol: A New Power Conservation Design for Surveillance Using Sensor Networks,” Information Processing in Sensor Networks (IPSN), pp. 246-253, April 2005.
[15]	B. Liu, P. Brass, and O. Dousse, “Mobility Improves Coverage of Sensor Networks,” International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc), pp. 300-308, 2005.
[16]	G. Wang, G. Cao, T. L. Porta, and W. Zhang, “Sensor Relocation in Mobile Sensor Networks,” INFOCOM, vol. 4, pp. 2302-2312, March 2005.
[17]	A. R. Shahani, D. K. Schaeffer, and T. H. Lee, “A 12 mW Wide Dynamic Range COMS Front-End for a portable GPS Receiver,” Digest of Technical Papers, IEEE International Solid State Circuits Conference, vol. 40, pp. 368-369, February 1997.
[18]	N. B. Priyantha, H. Balakrishnan, E. D. Demaine, and S. Teller, “Mobile-assisted Localization in Wireless Sensor Networks,” INFOCOM, vol. 1, pp. 172-183, March 2005.
[19]	K. F. Ssu, C. H. Ou and H. C. Jiau, “Localization with mobile Anchor points in Wireless Sensor Networks,” IEEE Transactions on Vehicular Technology, vol. 54, pp. 1187-1197, May 2005.
[20]	M. D. Berg, O. Schwarzkopf. M. V. Kreveld, and M. Overmars, “Computational Geometry: Algorithms and Applications,” 2nd Edition, Springer, 2000.
[21]	Y. Guo and Z. Qu, “Coverage Control for a mobile robot patrolling a dynamic and uncertain environment,” Proc. of world Congress on Intelligent Control and Automation, June 2004.  
[22]	W. Ye, J. Heidemann, D. Estrin, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks,” Proc. of IEEE Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp. 1567-1576, June 2002.  
[23]	X. Bai, S. Kumar, Z. Yun, D. Xuan and T. H. Lai, “Deploying Wireless Sensors to Achieve Both Coverage and Connectuivity,” Proc. of the Seventh International Symposium on Mobile Ad Hoc Networking and Computing (ACM MobiHoc), 2006.  
[24]	J. Xu, X. Tang, and W. C. Lee, “EASE: An Energy-efficient In-network Storage Scheme for Object Tracking in Sensor Networks,” Second Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (IEEE SECON), pp. 396-405, 2005.  
[25]	W. P. Chen, J. C. Hou, and L. Sha, “Dynamic Clustering for Acoustic Target Tracking in Wireless sensor Networks,” IEEE Transactions on Mobile Computing, vol. 3, pp. 258-271, 2004.
[26]	S. Ganeriwal, A. Kansal and M. B. Srivastava, “Self Aware Actuation for Fault Repair in Sensor Neworks,” IEEE International Conference on Robotics and Automation (ICRA), 2004.
[27]	J. Hill and D. Culler, “A Wireless Embedded Sensor Architecture for System-level Optimization,” Technical report, Computer Science Department, University of California at Berkeley, 2000.