在無線感測網路中，正確的位置資訊將有助於計算覆蓋率並在建立繞徑時可大量減少control overhead。近年來已有許多研究提出以具有位置資訊(如裝設全球定位系統GPS)的 mobile anchor移動並廣播其位置資訊以協助其他static sensor定位，每個static sensor藉由收到的廣播均可確認其位置落在ㄧ矩形位置區域，因此其具有一模糊的位置資訊。然而在戶外的環境當中，由於風吹、敵軍惡意破壞或是動物遷移等因素皆可能使已具有模糊位置資訊的static sensor更動，致使許多static sensor紀錄錯誤的位置而不自知。當sensor的位置為一模糊位置或是更甚錯誤時，現存的Location Aware Routing Protocol均無法正常的運作。本論文將以分散式的技術偵測並修正錯誤的位置資訊，使sensors記錄正確的位置資訊，以提高網路繞徑的效能，之後，我們將進一步探討模糊位置對現有的Location Aware Routing Protocol的影響與衝擊，並且提出ㄧ分散式繞徑技術使其可運作於模糊位置資訊之下，改善現存Location Aware Routing Protocol的封包傳送成功率。實驗顯示，我們提出的分散式偵測與修正技術可以找出記錄錯誤位置的sensors並且修正之，我們所提出的分散式繞徑演算法也能提高封包的成功到達率，使得繞徑的效能大幅改善。

The accurate location information is more important to estimate the coverage and reduce the control overhead of routing in wireless sensor networks. Recently, some researches [13][14][15] propose the locating mechanism applying the mobile anchor equipped with the Global Position System (or GPS for short) to achieve the accuracy of localization for the static sensors in the WSNs (Wireless Sensor Networks)[1]. Each static sensor can estimate or adjust the bounding box which bounds its real location by receiving the location information broadcasted by the mobile anchor and hence can address its estimated location. However, the estimated location of each static sensor is easy to become incorrect since some abrupt accidents, such as strong breeze, malicious remove or animal movement, will cause the estimated location fall into location error. The location error will increase the control overhead for the location aware routing protocol or furthermore result routing fault. This paper proposes a distributed location-error detection and correction mechanism to prevent the location errors from the accidents and hence improve the routing performance. Simulation results show that the proposed protocols can make the sensors which have location error aware that mistakes correct the error, and therefore significantly reduce the control overheads of routing and average routing length.

目錄   I
圖目錄   II
表目錄   III
1 INTRODUCTION	1
2 BACKGROUND AND RELATED WORKS	5
3 NETWORK ENVIRONMENT & PROBLEM STATEMENT	11
3.1   Network Environment	11
3.2 Problem Statement	12
4 LOCATION-ERROR DETECTION AND CORRECT MECHANISM	14
4.1 單點移動發生之錯誤位置	17
4.2 多點移動發生之集體錯誤位置	20
5 INACCURATE LOCATION AWARE ROUTING PROTOCOL	28
5.1 Forwarder Select Strategy	28
5.2 Enhancement Routing Algorithm for GPSR	32
6 PERFORMANCE STUDY	36
7 CONCLUSION	45
參考文獻	47
附錄-英文論文  49

圖   目   錄
圖(一)、GPSR運作在模糊位置資訊下將發生繞徑錯誤，無法將封包傳送至Sink。 7
圖(二)、錯誤模糊位置帶來的嚴重性。 8
圖(三)、本論文所利用的符號。 12
圖(四)、LEDC演算法。 19
圖(五)、群體移動示意圖。 20
圖(六)、移動的sensor 其仍維持鄰居關係。 22
圖(七)、移動之後內外層皆有Border形成。 24
圖(八)、GLEDC演算法。 26
圖(九)、GLEDC演算法。 27
圖(十)、模糊位置區域繞徑所面臨的問題。 29
圖(十一)、黑色點滿足式子(3)，因此可轉送封包，而白點沒有滿足式子(3)，因此不轉送封包。 31
圖(十二)、所發展的分散式Routing Algorithm。33
圖(十三)、模糊位置資訊繞徑實例。  35
圖(十四)、不同點數之下的Packet delivery ratio。  37
圖(十五)、不同點數之下的End-to-end delay。 38
圖(十六)、不同精準度之ELR所產生的封包傳送率。 39
圖(十七)、不同ELR精確度之下的end-to-end delay。  40
圖(十八)、錯誤偵測及修正之實驗設計圖。  41
圖(十九)、不同點數下之packet delivery ratio。  42
圖(二十)、不同ELR誤差率下之packet delivery ratio。  43
圖(二十一)、GLEDC與LEDC之比較。  44


表   目   錄
表I：Only one node moves in the environment.  17

[1]	I.F Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survery,” Computer Networks, vol. 38, pp. 393-422, March 2002.
[2]	Q. Li, M. D. Rosa, and D. Rus, “Distributed algorithms for guiding navigation across a sensor network,” Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pp. 313–325, Sept. 2003.
[3]	Q. Huang, C. Lu, and G.-C. Roman, “Reliable mobicast via face-aware routing,” Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2004.
[4]	M. Ding, D. Chen, A. Thaeler, and X. Cheng, “Fault-tolerant target detection in sensor networks,” Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Mar. 2005.
[5]	S. Megerian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Worst and best-case coverage in sensor networks,” IEEE Transactions on Mobile Computing, vol. 4, no. 1, pp. 84–92, Jan./Feb. 2005.
[6]	D. Niculescu, and B. Nath, “Ad-hoc positioning system (APS) using AOA,” Proceeding  of IEEE Infocom, vol 3, March 2003.
[7]	P. Bahl, and V. N. Padmanabhan, “RADAR: an inbuilding RF-based user location and tracking system,” Proceeding  of IEEE Infocom, vol 2, 2000.
[8]	K. Chintalapudi, A. Dhariwal, R. Govindan, and G. Sukhatme, “Ad-hoc localization using ranging and sectoring,” Proceeding  of IEEE Infocom,  vol 4, March 2004.
[9]	Y. Shang, W. Ruml, and Y. Zhang, “Improved MDS-based localization,” Proceeding  of IEEE Infocom, vol 4, March 2004.
[10]	T. He, C. Huang, B. Lum, J. Stankovic, and T. Adelzaher, “Range-free localization schemes for large scale sensor networks,” Proceeding of ACM MobiCom, 2003.
[11]	Chong Liu ,Kui Wu, and Tian HeComputer, “Sensor Localization with Ring Overlapping Based on Comparison of Received Signal Strength Indicator,” Proceedings of IEEE MASS, Oct 2004.
[12]	Vijayanth Vivekanandan, and Vincent Wong, “Concentric Anchor-Beacons (CAB) Localization for Wireless Sensor Networks,“ Proceeding  of IEEE ICC, June 2006.
[13]	Srinath T V, “Localization in Resource Constrained Sensor Networks using a Mobile Beacon with In-Ranging,” Proceedings of IEEE WOCN,  April 2006.
[14]	Jang Ping Sheu, Jian Ming Li, and C. S. Hsu, “A Distributed Location Estimating Algorithm for Wireless Sensor Networks,” IEEE SUTC,  June 2006.
[15]	A. Galstyan, B. Krishnamachari, and K. Lerman, ”Distributed online localization in sensor networks using a moving target,” The 3rd International Symposium on Information Processing in Sensor Networks(IPSN), April 2004.
[16]	B. Karp, and H.T. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” Proc. ACM MobiCom, pp. 243-254, August 2000.
[17]	P. Bose, P. Morin, Ivan Stojmenovic, and J. Urrutia, “Routing with guaranteed delivery in ad hoc wireless networks,” ACM Wireless Netwokrs, pp.609-616, vol.7 no.6, Nov. 2001.
[18]	K. Seada, A. Helmy, and R. Govindan, “Modeling and analyzing the correctness of geographic face routing under realistic conditions,” Ad hoc Networks, vol 5, issue 6, August. 2007.
[19]	W. Matthias, and T. Volker, “The Impact of Location Errors on Geographic Routing in Sensor Networks,” International Conference on Wireless and Mobile Communications, pp. 76-81, July 2006.