Wireless Sensor Networks已廣泛地應用在軍事用途、目標追蹤及環境監測。然而，Sensor Node在經過長時間的環境感測下，可能因為電量耗盡、訊號的干擾或是其他的外力因素，使其喪失環境感測的能力，導致在Wireless Sensor Networks環境中形成感測上的空洞區，並逐漸擴大影響範圍而使得網路形成斷裂的情形，進而使一些Sensor Nodes雖能正確的感測到資料卻無法將訊息回傳給Sink Node，影響資料收集的精確度。因此在本論文中，我們將針對網路斷裂的產生，提出一個預先偵測及預防的方法。在網路因空洞而導致斷裂分割前，我們針對成長中的空洞進行偵測及監控，並利用資料Aggregation的特性來監控空洞是否讓網路進入不安全(Unsafe)狀態，避免可能發生的網路斷路。
除此之外，本論文也提出一個網路修復的機制，在網路斷裂前利用Mobile Sensor予以修復。在本論文中，我們所設計的網路斷裂偵測及修復機制，不但能以分散式的方式，偵測感測空洞的大小與形狀，並且預測空洞的成長，在其造成網路斷裂前，找出最符合成本效益之修補路徑，並以WSNs所提供的有限的Mobile Nodes依循演算法所找出的最佳路徑，進行修復感測空洞的任務，使Wireless Sensor Network回復正常的感測及資料回傳的能力。
經由本論文的實驗數據顯示，本論文所提出的障礙物處理通訊協定，不但能有效地在Wireless Sensor Network中預防因空洞所造成的網路斷裂情形，並且能確保所有感測的訊息都能成功的回傳至資料收集點。

Wireless Sensor Network (WSN) is one kind of wireless network system which comprised with a sink node and a number of sensor nodes. The main purpose of WSN is to monitor and to track every single movement in a specific area. Sensor nodes are deployed density in the network and transmit the gathered information to sink node in a multi-hop manner. Therefore, some sensor nodes tend to exhaust their energy more easily than other nodes due to their heavy traffic load on packet forwarding. In wireless sensor network environment, network partition is a frequent phenomenon which could make the seasoning data much less preciously. Therefore, WSN need a partition detection mechanism to mark the “Undetected Area” and bypass this area when forwarding message to sink node. This paper proposes an efficient Partition Detection and Avoidance Protocol to detect the network undetected area, to avoid network partition phenomenon and to extend the sensor network life time. 
According the experiments of this paper, simulation results shows that the developed partition detection and avoidance protocols can efficiently detect and monitor the obstacle to prevent network partition and keep network always connected, Moreover, It could indeed extend the sensor network lifetime.

第一章、簡介	1
第二章、背景及基本概念	7
第三章、網路斷裂偵測及避免協定	14
A、INITIAL PHASE	16
B、PHASE II：DETECTION AND MONITOR PHASE	20
C、PHASE III；MAINTANENCE PHASE	24
第四章、效能評估	30
(A)  AVERAGE END-TO-END DELAY與SENSOR NODES個數	32
(B)  NETWORK LIFETIME與SENSOR NODES個數	33
(C)  NETWORK THROUGHTPUT與TIME NEEDED間	34
第五章、結論	35
參考文獻…………………………………………………………..……36
英文論文……………………………………………………….………A1
圖 目 錄
圖(1)、發生感測空洞的網路，不過網路封包仍能找到替代路徑回傳資料……………………………………………………………………....4
圖(2)、感測空洞過大，將網路分割成兩個無交集的子網路，要傳送的封包無法找到傳送資料的替代路徑…………………………………5
圖(3)、網路拓撲架構圖…………………………………………….….7
圖(4)、Backbone架構………………………………………………….9
圖(5)、Monitor Node Selection Mechanism……………………..……10
圖(6)、Maintenance Phase……………………………………………..11
圖(7)、Backbone Concept…………………………………….………..17
圖(8)、Boundary Node Selection Mechanism………………………....19
圖(9)、Monitor Node Selection.....................………………………….21
圖(10)、Monitor Node Selection Algorithm……………………..……22
圖(11A)、當網路空洞超過右邊界的情況………………………….…23
圖(11A)、當網路空洞超過上邊界的情況………………………….…23
圖(11A)、當網路空洞超過下邊界的情況………………………….…23
圖(11A)、當網路空洞超過左邊界的情況………………………….…24
圖(12A)、計算需要補點的集合……………………………………….26
圖(12B)、更新目前可用的Mobile Sensor位置資訊..……………….27
圖(12C)、利用Mobile Sensor達到最佳成本的補點，並將網路回復為連接的狀態計算需要補點的集合……………………………………..29
圖(13)、評估比較Network Average End-to-End Delay……………..32
圖(14)、評估比較Network Lifetime…………………………………33
圖(15)、評估比較Network Throughput……………………………...34 
表 目 錄
表格(1)、論文中所使用的符號列表…………………………………14
表格(2)、模擬環境之相關參數………………………………………30

[1]	G. J. Pottie, W. J. Kaiser, “Wireless Integrate Network Sensors,” in 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,” in International Conference on Acoustics, Speech, and Signal Processing (ICASSP), May 2001.
[3]	D. Estrin, R. Govindan, “Next Century Challenges: Scalable Coordination in Sensor Networks,” in Mobicom 1999, August 1999, pp. 263 – 270.
[4]	C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. Srivastava, “Topology Management for Sensor Networks: Exploiting Latency and Density,” in Proceedings of the 3rd ACM International Symposium on Mobile ad hoc Networking & Computing (MobiHoc), June 2002, pp. 135 - 145.
[5]	K. Sohrabi, J. Gao, V. Ailawadhi, G. Pottie, “Protocols for Self-organization of a Wireless Sensor Network,” in IEEE Personal Communications Magazine, October 2000, pp. 16 – 27.
[6]	J. Pan, Y. T. Hou, L. Cai, Y. Shi, and S. X. Shen, “Topology control for wireless Sensor networks,” in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, September 2003, pp. 286 - 299.
[7]	Y.-C. Tseng, Y.-N. Chang, and P.-H. Tseng, “Energy-efficient topology control for wireless ad hoc Sensor networks,” in Proceedings of International Computer Symposium (ICS), 2002.
[8]	M. Duque-Anton, F. Bruyaux, P. Semal, Measuring the survivability of a network: connectivity and rest-connectivity, European Transaction of Telecomunications, 11, 2, 149-159, 2000. 
[9]	Y. Deng and I. Stojmenovic, Partial Delaunay triangulation based routing, data storage, and addressing in ad hoc networks, manuscript, 2004. 
[10]	D. Goyal and J. Caffery, Partitioning avoidance in mobile ad hoc networks using network survivability concepts, Proc. IEEE Int. Symp. Computers and Communications ISCC, Taormina, Italy, July 2002, 553-558. 
[11]	T. Hara, Replica allocation methods in ad hoc networks with data update, Mobile Networks and Applications 8, 2003, 343-354. 
[12]	M. T. Hajiaghayi, N. Immorlica, V.S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, Proc. ACM MOBICOM, Sept. 2003. 
[13]	M. Hauspie, D. Simplot, and J. Carle. Partition detection in mobile ad-hoc networks. Proc. 2nd IFIP Mediterranean Ad Hoc Networking Workshop (MED-HOC-NET 2003), (Mahdia, Tunisia, 2003). 
[14]	M. Hauspie, D. Simplot-Ryl, M. Jorgic, I. Stojmenovic, Localized algorithms for service replication in ad hoc networks, in preparation. 
[15]	L. Jia and C. Scheideler, On local algorithms for topology control and routing in ad hoc networks, Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 220-229, June 2003. 
[16]	M. Jorgic, A. Nayak, I. Stojmenovic, Localized algorithms for detection of k-connectivity in ad hoc networks, 2004, in preparation. 
[17]	H. Koskinen, Statistical model describing connectivity in ad hoc networks, Proc. Modeling and optimization in mobile, ad hoc, wireless networks WiOpt, INRIA, Sophia-Antipolis, March 2003. 
[18]	G. Karumanchi, S. Muralidharan, R. Prakash, Information dissemination in partitionable mobile ad hoc networks, Proc. IEEE Symp. Reliable Distributed Systems, October 1999. 
[19]	Q. Li and D. Rus, Communication in disconnected ad hoc networks using message relays, ACM MOBICOM 2000; J. Parallel and Distributed Computing, 63, 2003, 75-86. 
[20]	U. Manber, Introduction to Algorithms, A Creative Approach, Addison Wesley, 1989, p. 217-225. 
[21]	V.D. Park and M. S. Corson. A highly adaptive distributed routing algorithm for mobile wireless networks. IEEE INFOCOM ’97, Kobe, Japan, April 1997.
[22]	S.H. Shah, K. Chen, and K. Nahrstedt. Cross-layer design for data accessibility in mobile ad hocnetworks. In Proc. of 5th World multiconference on systemics, cybernetics and informatics (SCI 2001), Orlando, Florida, July 2001; Wireless Personal Communications, vol. 21, pp. 49-76, 2002. 
[23]	I. Stojmenovic, M. Russell, and B. Vukojevic, Depth first search and location based localized routing and QoS routing in wireless networks, Computer Science, SITE, University of Ottawa, TR-00-01, January 2000; Computers and Informatics, Vol. 21, No. 2, 2002, 149-165.
[24]	R. Tarjan, Depth first search and linear graph algorithms, SIAM J. Computing, 1, 2, 146-160, 1972.
[25]	A. Vahadat, D. Becker, Epidemic routing for partially connected ad hoc networks, Technical Report CS-200006, Duke University, April 2000.
[26]	K.H. Wang, B. Li, Efficient and guaranteed service coverage in partitionable mobile ad hoc networks, INFOCOM, 2002.
[27]	K.H. Wang and B. Li, Group mobility and partition prediction in wireless ad hoc networks, IEEE ICC, April 2002.