定位(Localization)在無線感測網路(WSNs)中是一項很重要的議題。然而，即使每個感測器(Sensor)均配有GPS，其定位亦有誤差且耗費硬體成本。近年來已有許多相關研究提出以Mobile Anchor(MA)定位，在每個感測器不需額外硬體成本的前提下，透過發送Beacon message以及MA的移動性，來提供感測器大致的位置資訊。然而，其所提供的位置精準度並無法區別感測器之間的相對位置，間接影響現存之繞徑協定(Location Aware Routing; LAR)及物件追蹤等應用之效能。本論文除了位置精準度外，亦著重於鄰近感測器間的位置區別度，我們利用MA所廣播的Beacon及Tone兩種訊號，以分散式的方法提供每個感測器位置資訊並區別鄰近感測器間之相對位置。實驗結果顯示，本論文所提出的定位技術確實可區別感測器與鄰居間的相對位置關係，並大量改善現存之LAR及物件追蹤協定的效能。

Location information is of utmost importance for most applications in wireless sensor networks (WSNs). A number of bounding-box mechanisms have been proposed based on a mobile anchor which periodically broadcasts its location information to help nodes estimate their location using the bounding-box constraints. However, the bounding-box location information can not distinguish the relative locations between neighboring sensors, hence leading to a poor performance for some applications such as location-aware routing. This paper proposes a Differentiating Relative Locations (DRL) mechanism which adopts tones and beacons techniques aiming at distinguishing the relative locations between any two adjacent nodes. With the order of entering and existing tone transmission range, each sensor is able to identify its relative location relation with each of its neighbor. In addition, a path planning mechanism is proposed to guarantee that all sensors can identify their relative locations with their neighbors while the energy consumption of the mobile anchor can be reduced. Theoretical analysis is developed for determining the duration ratio of broadcasting tone and silence so that the mobile anchor can further achieve energy conservation during executing the proposed DRL mechanism. Experimental study reveals that the proposed DRL mechanism effectively distinguishes relative locations between any two adjacent nodes and hence improves the performance of upper layer applications in WSNs.

目錄
一、簡介 1
二、相關研究 4
三、網路環境與問題描述 8
3.1網路環境 8
3.2 問題描述 8
四、Differentiating Relative Locations (DRL) Properties 11
4.1 Basic Concept 11
4.2 DRL Properties 16
4.3 Rules for Ambiguous Conditions 19
五、Moving Path for Mobile Anchor 24
5.1 Two-Phase DRL Protocol with Tones 24
5.2 Single-Phase DRL Protocol with Tones 26
5.3 DRL Protocol with Beacons and Tones 33
六、Simulation Study 37
七、結論 44
參考文獻 45
附錄一英文論文 47

圖目錄
圖(一)：Bounding box Ba雖在Bb的西北方，但sa與sb的相對位置卻有ambiguous situation。 5
圖(二)：使用不同的訊號強度找出感測器可能存在區，並在感測器周圍三個地方廣播以找出sa存在之交集區。 6
圖(三)：MA移動時不斷地發送Beacon以找出三個座標，再利用中垂線以協助感測器定位。 7
圖(四)：本論文中MA循蛇形路徑移動，並交替發送Beacon message及Tone signal訊號以協助static sensor定位。 11
圖(五)：三個鄰近的感測器sa、sb及sc透過MA所發送的tone signal來區別彼此的東西相對位置之例子。 13
圖(六)：以「先接收到tone signal的感測器會位於較西邊的位置」的概念運作，可能產生判斷相對位置錯誤的例子。感測器sa雖較sb早收到MA之Tone signal，但其位置卻落在sb東邊。 14
圖(七)：以Basic Concept敘述之作法運作，可能造成判斷相對位置錯誤的例子。感測器sa與sb同時收到MA之Tone signal，導致兩Table的資訊錯亂。 15
圖(八)：Lemma 1的證明，先固定一個感測器sa，利用sa分析在不同時間點時sb所在範圍，最後取其交集。 17
圖(九)：MA由西向東前進，且感測器sa與sb同時收到MA之tone signal時，在MA通訊圓中留下較長移動軌跡的感測器位於較東邊的位置。 18
圖(十)：感測器sb較sa晚收到，卻較早失去MA所發之Tone signal。(a)與(b)兩種完全不同的情況，卻會得到相同的Entry以及Exit Table，導致兩感測器無法光憑Table資訊判斷相對位置關係。 19
圖(十一)：當感測器sa無法光憑Table資訊判斷其與鄰居間的相對位置時，將利用d值的大小輔助sa判斷。 20
圖(十二)：DRL Properties整理表。 23
圖(十三)：MA在Two-phase DRL Protocol with Tones中的行走路徑，必須東西方向和南北方向各蛇行一次，才可幫助感測器區別其與鄰居間的相對位置關係。 24
圖(十四)：感測器接收(失去) tone signal時所執行的演算法。 25
圖(十五)：Two-Phase DRL Algorithm。 26
圖(十六)：各感測器在MA通訊圓中留下的軌跡必為此圓之一弦。與其鄰居相比，弦越長之感測器代表離MA行走路線越接近。 27
圖(十七)：考慮感測器與其鄰居位在同一個半圓，若感測器sa在MA之通訊圓中留下的弦長度較感測器sb留下的弦長，則只會出現本圖中之兩種情況。 28
圖(十八)：MA由西向東直線前進，若遇到右邊界或左邊界，則分別向下移動r距離、2r距離。 29
圖(十九)：感測器收到tone signal時所執行的演算法。 31
圖(二十)：Single-Phase DRL Algorithm。 33
圖(二十一)：因為sb位於sa之通訊範圍之內，所以將sa之bounding box Ba向外以通訊半徑r的距離擴張，即可得到sb之bounding box Bb。 34
圖(二十二)：灰色區域為MA發送beacon之區域，故其中之感測器均有自己之bounding box，而白色區域則反之。 35
圖(二十三)：每個擁有bounding box之感測器，均有機會透過感測器間之溝通來縮小bounding box之範圍。 36
圖(二十四)：比較四種方法在相同條件下，判斷相對位置成功的機率。 38
圖(二十五)：感測器密度0.02、傳輸半徑變化時，判斷相對位置成功的機率。 39
圖(二十六)：傳輸半徑45、網路密度發生變化時，判斷相對位置成功的機率。 39
圖(二十七)：將「感測器可區分其與鄰居間之相對位置關係」的訊息加入的繞徑協定中，得到可大幅提升繞徑協定的結果。 41
圖(二十八)：在繞徑協定中加入相對位置關係的資訊，將可減少繞遠路的情況發生。 41
圖(二十九)：在定位協定中加入相對位置關係的資訊，可讓定位協定的效能提高，定位也可以更加地精準。 42
圖(三十)：Two-phase DRL演算法在區別相對位置的成功率上略高於Single-phase DRL演算法，但是在時間以及電量的消耗方面卻遜於Single-phase DRL演算法。 42

表目錄
Table 1：Simulation Parameters 37

[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 2001), 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,” Proceedings of International Conference on Mobile Computing and Networking (MobiCom 1999), August 1999.

[4] D. Niculescu, and B. Nath, “Ad-hoc positioning system (APS) using AOA,” Proceeding of the IEEE International Conference on Computer and Communications (INFOCOM 2003), April 2003.

[5] P. Bahl, and V.N. Padmanabhan, “RADAR: an in-building RF-based user location and tracking system,” Proceeding of the IEEE International Conference on Computer and Communications (INFOCOM 2000), March 2000.

[6] K. Chintalapudi, A. Dhariwal, R. Govindan, and G. Sukhatme, “Ad-hoc localization using ranging and sectoring,” Proceeding of the IEEE International Conference on Computer and Communications (INFOCOM 2004), March 2004.

[7] Y. Shang, W. Ruml, and Y. Zhang, “Improved MDS-based localization,” Proceeding of the IEEE International Conference on Computer and Communications (INFOCOM 2004), March 2004.

[8] T. He, C. Huang, B. Lum, J. Stankovic, and T. Adelzaher, “Range-free localization schemes for large scale sensor networks,” Proceedings of International Conference on Mobile Computing and Networking (MobiCom 2003), September 2003.

[9] C. Liu, K. Wu, and T. He, “Sensor Localization with Ring Overlapping Based on Comparison of Received Signal Strength Indicator,” IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2004), October 2004.

[10] V. Vivekanandan, and V. Wong, “Concentric Anchor-Beacons (CAB) Localization for Wireless Sensor Networks,” Proceeding of IEEE International Conference on Communications (ICC 2006), Istanbul, Turkey, June 2006.

[11] T.V. Srinath, “Localization in Resource Constrained Sensor Networks using a Mobile Beacon with In-Ranging,” IEEE International Conference on Wireless and Optical Communications Networks(WOCN 2006), April 2006.

[12] J.P. Sheu, J.M. Li, and C.S. Hsu, “A Distributed Location Estimating Algorithm for Wireless Sensor Networks,” IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC 2006), June 2006.

[13] A. Galstyan, B. Krishnamachari, and K. Lerman, “Distributed online localization in sensor networks using a moving target,” Information Processing in Sensor Networks (IPSN 2004), Berkeley, CA, April 2004.

[14] Brad Karp and H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings of International Conference on Mobile Computing and Networking (MobiCom 2000), August 2000.

[15] Karim Seada, Ahmed Helmy and Ramesh Govindan, “Modeling and Analyzing the Correctness of Geographic Face Routing under Realistic Conditions,” Information Processing in Sensor Networks (IPSN 2004), Berkeley, CA, April 2004.

[16] K.-F. Ssu, C.-H. Ou, and H. Jiau, “Localization with Mobile Anchor Points in Wireless Sensor Networks,” IEEE Transactions on Vehicular Technology, vol. 54, pp. 1186–1197, May 2005.