無線感測網路(Wireless Sensor Networks)會因為無線感測元件(Sensors)無法工作而使得網路產生分割(Partition)，Partition將嚴重影響Coverage 的情況與Connectivity 的品質。因此，我們提出一個有效避免Partition 產生的分散式無分割移動之通訊協定(Distributed Partition-Free Lazy Movement Protocol，PLMP)，PLMP 使用具移動性的感測裝置(Mobile Sensors)以避免Partition 的產生。
PLMP主要包括「Network Initialization Phase」和「Network Maintenance Phase」二個部分。在「Network Initialization Phase」中，整個行動感測網路(Mobile Sensor Network，MSN)將以Sink為主進行網路初始化的動作，這個部分將提供未來Mobile Sensors移動方向的依據。「Network Maintenance Phase」則是應用於網路可能產生Partition時，Mobile Sensors所需移動的位置與方向之計算。當Partition可能產生時，Connectivity 較差的Mobile Sensors將利用右手法則(Right Hand Rule)方式傳送封包並蒐集相關資訊，據以計算出一個考量到區域Coverage情況的移動位置，最後再移至該處維護網路的Connectivity。另外我們在效能分析中提出二個效能指標EIn與EIc分別判斷移動位置對於WSN中Coverage與Connectivity的影響。
PLMP 具有下列特色(1) 分散式的協定；(2)有效維護網路的Connectivity；(3)盡量減少Mobile Sensors 移動的時機與次數，以減少電量的消耗。實驗模擬的結果顯示出，分散式無分割移動之通訊協定較其他相關文獻所提出之協定更能避免Partition 的產生，使所有能夠工作的Mobile Sensors 可以貢獻他們的能力，以增加WSN 的存活時間。

According to the advancement of wireless technology, wireless sensor networks (WSNs) are widely adopted to many applications. Some partitions will appear in WSNs because some sensors are inactive. Partitions will reduce the coverage and weaken the connectivity of the WSN. We will provide a protocol (Distributed Partition-Free Lazy Movement Protocol, PLMP) which can prevent the appearance of partitions effectively. PLMP has some characteristics as follows:(1) It is distributed (2) It can maintain the connectivity of the WSN effectively (3)Less Number of movements.

第 1 章	緒論	1
1.1	研究背景	1
1.2	研究動機	2
1.3	研究目的及方法	7
1.4	論文架構	9
第 2 章	背景知識	10
2.1	網路模型	10
2.2	Connectivity對感測任務影響之分析	11
2.3	網路拓樸結構對Coverage影響之分析	13
2.4	線性方程式	21
第 3 章	分散式無分割移動之通訊協定	23
3.1	Network Initialization Phase	23
3.2	Network Maintenance Phase	25
3.2.1	Stock Node Determination	25
3.2.2	Attach Nodes Discovery	28
3.2.3	Target Position Calculation	30
3.3	特殊情況處理	40
第 4 章	實驗與模擬	42
4.1	實驗環境	42
4.2	實驗結果	42
4.2.1	可與Sink連結的Mobile Sensors數量(ES)	42
4.2.2	移動次數	44
4.2.3	Mobile Sensors對MSN之貢獻(EIn)	45
4.2.4	整合EIn與EIc與的比較(EI)	47
4.2.5	結論	48
第 5 章	結論與未來研究方向	49
參考文獻	52
圖一 MSN中已形成一包含3個Mobile Sensors的Partition	4
圖二	相同數量的Mobile Sensors對MSN中感測結果的影響	12
圖三	三種網路拓樸對於Coverage與Connectivity的分析比較	15
圖四	S將計算與鄰居外心或中點距離標準差	19
圖五	直線L將平面區分為兩個區域R1與R2	21
圖六	網路初始化後，Mobile Sensors將可設定本身的Minimum Hop Count	25
圖七	MSN中已形成一包含3個Mobile Sensors的Partition	27
圖八	J收到I的封包後，以I為基準逆時針找到第一個鄰居K	28
圖九	Stock Node S將發起以Right Hand Rule為傳送方式的偵測封包	30
圖十	尋找Temporary Position	32
圖十一	任兩個Affecting Nodes彼此距離必須在2R內	33
圖十二	Protocol運作流程圖	34
圖十三	利用向量微調決定Stock Node移動位置	39
圖十四	特殊情況探討	41
圖十五	環境設定	42
圖十六	Non-Partition Sensors數的比較(ES)	43
圖十七	圖十六的放大圖	44
圖十八	移動次數的比較	45
圖十九	EIn的比較	46
圖二十	圖十九的放大圖	47
圖二十一	EI的比較	48

[1]. W.Zhang and G.Cao, “Optimizing tree reconfiguration for mobile target tracking in sensor networks,” in Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Mar. 2004, pp.2434–2445.
[2]. F. Ye, H. Luo, J. Cheng, S. Lu and L. Zhang, “A two-tier data dissemination model for large-scale wireless sensor networks,” in Proceedings of the 8th Annual International Conference on Mobile Computing and Networking
(MobiCom), Sep. 2002, pp. 148-159.
[3]. X. Ji, H. Zha, J. J. Metzner and G. Kesidis, “Dynamic cluster structure for object detection and tracking in wireless ad-hoc sensor networks,” in Proceedings of the IEEE International Conference on Communications (ICC), Jun. 2004, pp.3807-3811.
[4]. D. Tian and N. 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, 2002, pp. 32–41.
[5]. F. Ye, G. Zhong, J. Cheng, S. Lu, and L. Zhang,“PEAS: a robust energy conserving protocol for long-lived sensor networks,” in Proceedings of the IEEE 23th International Conference on Distributed Computing Systems(ICDCS), May 2003, pp. 28–37.
[6]. Z. Zhou, S. Das, and H. Gupta, “Connected K-coverage problem in sensor networks,” in Proceedings of the 13th International Conference on Computer Communications and Networks, 2004, pp. 373–378.
[7]. S. Kumar, T. H. Lai, and J. Balogh, “On k-coverage in a mostly sleeping sensor network,” in Proceedings of the 10th annual international conference on Mobile computing and networking, 2004, pp. 144–158.
[8]. H. Gupta, S. R. Das, and Q. Gu, “Connected sensor cover : self-organization of sensor networks for efficient query execution,” in Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, 2003, pp.189–200.
[9]. H. Zhang and J. 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,2004.
[10]. C. F. Hsin and M. Liu, “Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), Apr. 2004, pp. 433–442.
[11]. G. Xing, C. Lu, R. Pless, and J. O’Sullivan, “Co-Grid: an efficient coverage maintenance protocol for distributed sensor networks,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks(IPSN), Apr. 2004, pp. 414–423.
[12]. G. Wang, G. Cao, and T. LaPorta, “Movement-assisted sensor deployment,” in Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Mar. 2004, pp. 2469–2479.
[13]. N. Heo and P. Varshney, “A distributed self spreading algorithm for mobile wireless sensor networks,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Mar. 2003, pp. 1597–1602.
[14]. P. Varshney and N. Heo, “An intelligent deployment and clustering algorithm for a distributed mobile sensor network,” in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Oct. 2003, pp. 4576–4581.
[15]. T. Wong, T. Tsuchiya, and T. Kikuno, “A self-organizing technique for sensor placement in wireless micro-sensor networks,” in Proceedings of the 18th International Conference on Advanced Information Networking and Applications(AINA), 2004, pp. 78–83.
[16]. 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, Feb. 2004.
[17]. G. Wang, G. Cao, and T. LaPorta, “A bidding protocol for deploying mobile sensors,” in Proceedings of the 11th IEEE International Conference on Network Protocols(ICNP), Nov. 2003, pp. 315–324.
[18]. S. Ganeriwal, A. Kansal, and M. Srivastava, “Self aware actuation for fault repair in sensor networks,” in Proceedings of the 2004 IEEE International Conference on Robotics and Automation(ICRA), May 2004, pp. 5244–5249.
[19]. J. Hwang, D. Du, and E. Kusmierek, “Energy efficient organization of mobile sensor networks,” in Proceedings of the 2004 IEEE International Conference on Parallel Processing Workshops(ICPPW), Aug. 2004, pp. 84–91.
[20]. S. Zhou, M.-Y. Wu, and W. Shu, “Finding optimal placements for mobile sensors: wireless sensor network topology adjustment,” in Proceedings of the IEEE 6th Circuits and Systems Symposium on Emerging Technologies: Frontiers of Mobile and Wireless Communication(CAS), Jun. 2004, pp. 529–532.
[21]. A. Caruso, A. Urpi, S. Clessa, and S. De, “GPS Free Coordinate Assignment and Routing in Wireless Sensor Networks,” in Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Mar. 2005.
[22]. T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-free localization schemes for large scale sensor networks,” in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom), 2003, pp. 81–95.
[23]. R. Iyengar and B. Sikdar, “Scalable and distributed GPS free positioning for sensor networks,” in Proceedings of the IEEE International Conference on Communications (ICC), May 2003, pp. 338–342.
[24]. K. Kalpakis, K. Dasgupta, and P. Namjoshi,“Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks,” The International Journal of Computer and Telecommunications Networking, pp.697–716, Aug. 2003.
[25]. S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage problems in wireless ad-hoc sensor networks,” in Proceedings of the IEEEInternational Conference on Computer Communications (INFOCOM), 2001, pp. 1380–1387.
[26]. H. Yang and B. Sikdar, “A protocol for tracking mobile targets using sensor networks,” in Proceedings of the IEEE International Workshop on Sensor Network Protocols and Applications (SNPA), May 2003, pp. 71–81.
[27]. K. Young-Bae and N. H. Vaidya, “Location-aided routing (LAR) in mobile ad hoc networks,” Wireless Networks, pp. 307–321, 2000.