無線感測網路中，建立具共享能力之資料收集樹是一個重要的服務功能。雖然現有研究對共享樹的建立已有許多探討，當網路中存在障礙物或是共享樹上的Sensor電力耗盡無法繼續傳送資料時，將破壞其資料收集的整合性及通訊效能，因此，本論文主要在研究下列議題：給予一已建立之共享樹，當此共享樹中產生一影響通訊的大型障礙物時，如何以分散式的技術來局部重建共享樹，使資料的收集具有高度的共享能力以達到節省耗電及延長網路生命期之目的。在本研究中，我們擬從多種避開障礙物或空洞區域的路徑中，有效率的挑選出有高度共享以減少成本的封包傳輸路徑，並以較低的成本來重建具高度共享之資料收集樹。實驗數據顯示，我們所提出維護Share Tree的機制，能有效的克服障礙區，並能維持Share Tree共享的能力、減少電量的耗費以及延長WSNs的生命週期。

Constructing a share tree from sink node to a group of data source nodes can explore the potential of data aggregation in wireless sensor networks (WSNs). In literature, there are plenty researches developing mechanisms to construct a share tree, however, most of them can not resist obstacles which might damage the constructed tree topology and thus block the data transmission. This paper proposes a disturbed mechanism, namely obstacle-free sharing tree reconstruction protocol (OFST), to locally repair the injured share tree so that the reconstructed share tree can resist obstacles and explore the data aggregation potential. For a given three disconnected subtree, the proposed OFST initially identifies the share region where all points in the region can play the role of share point for resisting the existed obstacle and exploring the data aggregation potential. Based on the concept of steiner point, a theoretical study on selecting the best share point from the share region is presented for connecting the three subtrees. Simulation results reveal that the proposed OFST protocol can effectively overcome the obstacle and explore the data aggregation potential, and hence reduce the energy consumption and prolong the network lifetime of the WSN.

目    錄
目    錄	I
圖 目 錄	II
I、Introduction	1
II、Related Work	5
III、Network Environment & Problem Statement	9
3.1 Network Model and Assumptions	9
3.2 Problem Statements	10
IV、Obstacle-Free Share Tree Reconfiguration Protocol	14
4.1 Faulty Tree Detection Phase	14
4.2 Tree Reconstruction Phase	18
4.2.1 Select The Reconstruction Set	18
4.2.2 Tree Establishment	29
4.2.3 Cost Analysis	33
V、Simulation	35
5.1 Simulation Setup	35
5.2 Performance Metrics	37
VI、Conclusion	53
REFERENCES	54
附錄─英文論文	57

圖 目 錄
圖 一：障礙區域產生破壞Share Tree的結構	10
圖 二：Information_Gathering封包格式	17
圖 三：Share Region	22
圖 四：最接近Steiner Point的位置	24
圖 五：Steiner tree is the minimum cost	26
圖 六：共享點的成本比較	27
圖 七：Reconfiguration	31
圖 八：實驗場景-障礙區產生	37
圖 九：實驗場景-克服障礙區域	37
圖 十：網路Sensor個數 vs. Total Length	38
圖 十一：Damage Ratio vs. Total Length	39
圖 十二：Source Density vs. Total Length	40
圖 十三：網路Sensor個數 vs. Reduction Ratio	42
圖 十四：Damage Ratio vs. Reduction Ratio	43
圖 十五：Source Density vs. Reduction Ratio	44
圖 十六：網路Sensor個數 vs. Energy Cost	46
圖 十七：Damage Ratio vs. Energy Cost	47
圖 十八：Source Density vs. Energy Cost	48
圖 十九：網路Sensor個數 vs. Delay Time	50
圖 二十：Damage Ratio vs. Delay Time	51
圖 二十一：Source Density vs. Delay Time	52

[1]	Chalermek Intanagonwiwat, Deborah Estrin, John Heidemann, “Impact of Network Density on Data Aggregation in Wireless Sensor Networks,” Proceedings of IEEE International Conference on Distributed Computing Systems (ICDCS), 2002.
[2]	Shinji Mikami, Takafumi Aonishi, Hironori Yoshino, Chikara Ohta, Hiroshi Kawaguchi and Masahiko Yoshimoto, “Aggregation Efficiency-Aware Greedy Incremental Tree Routing for Wireless Sensor Networks,” IEICE Transactions on Communications, v E89-B, n 10, p 2741-2750, October, 2006.
[3]	S.-J. Lee and M. Gerla and C.-C. Chiang, “On-Demand Multicast Routing Protocol,” Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), pp.1298-1304, New Orleans, 1999.
[4]	Oliver Stanze and Martina Zitterbart, “On-Demand Overlay Multicast in Mobile Ad hoc Networks,” Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), pp.2155-2161, 2005.
[5]	S. Das, B, Manoj et al, “A dynamic core based multicast routing protocol for ad hoc wireless networks,” Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing (MOBICOM), pp.24-35, 2002.
[6]	Shibo Wu, K. Selcuk Candan, “GMP: Distributed Geographic Multicast Routing in Wireless Sensor Networks,” Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS), 2006.
[7]	Juan A. Sanchez, Pedro M. Ruiz, Ivan Stojmenovic, “GMR: Geographic Multicast Routing for Wireless Sensor Networks,” The 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks (SECON), pp.20-29, 2006.
[8]	R. Hwang, D. Richards et al, ”The Steiner Tree Problem,” Annals of Discrete Mathematics,1992.
[9]	Alexandr O. Ivanov and Alexei A. Tuzhilin. “Minimal Networks: The Steiner Problem and its Generalizations,” CRC Press, 1994.
[10]	P. Bose, P. Morin, Ivan Stojmenovic, and J. Urrutia, “Routing with guaranteed delivery in ad hoc wireless networks,” ACM Wireless Networks, pp.609-616, Vol.7 no.6, Nov. 2001.
[11]	Y.-B. Ko and N.H. Vaidya, “Geocasting in mobile ad hoc networks: location-based multicast algorithm, “   in: IEEE Workshop on Mobile Computer Systems and Applications,   February 1999.
[12]	Chih-Yung Chang , Chao-Tsun Chang , Shin-Chih Tu, “Obstacle-Free Geocasting Protocols for Single/Multi-Destination Short Message Services in Ad Hoc Networks, “ Wireless Networks, p.143-155 , March 2003.
[13]	Le Zou,  Mi Lu, and Zixiang Xiong, “A Distributed Algorithm for the Dead End Problem of Location Based Routing in Sensor Networks,“ IEEE Transactions, Vehicular Technology , 2005.
[14]	B. Karp and H.T. Kung, “GPSR：Greedy Perimeter Stateless Routing for Wireless Networks,” Proc. 6th Annual International Conference on Mobile Computing and Networking (MOBICOM), pp.243-254, 2000.
[15]	Caruso, A. Urpi, S. Chessa, and S. De, “GPS-Free Coordinate Assignment and Routing in Wireless Sensor Networks,” Proceedings of IEEE International Conference on Computer Communication (INFOCOM), Vol. 1, pp. 150-160, Miami, March, 2005.
[16]	Vijayanth Vivekanandan, and Vincent Wong, “Concentric Anchor-Beacons (CAB) Localization for Wireless Sensor Networks,“ Proc. of IEEE International Conference on Communications (ICC), 2006.
[17]	C. Y. Chang, K. P. Shih, S. C. Lee, and S. W. Chang, "RGP: Active Route Guiding Protocol for Wireless Sensor Networks with Obstacle," International Conference on IEEE Mobile Ad hoc and Sensor Systems (MASS), pp.367-376,Oct. 2006.
[18]	Xiaoyun Li, David K. Hunter, Kun Yang , “Distributed Coordinate-free Hole Detection and Recovery,” IEEE Global Telecommunications Conference (GLOBECOM), Nov. 2006.