在WSN(Wireless Sensor Network)中，Sensor定位是一個非常重要的議題，Sensors位置資訊越精準對於如物體追蹤，資料繞送，覆蓋區域偵測等問題越有幫助，在文獻中已有許多的方法被提出，以GPS(Global Positioning System )定位來提供精確位置資訊，其方式雖然簡單但是硬體成本過於昂貴。而近年來有人提出使用具有精確位置資訊(如裝設全球定位系統GPS)的 Mobile Anchor移動以提供或改善其他Sensors位置資訊的精確度。但是未針對Mobile Anchor的移動方式加以討論，本論文提出一個分散式路徑Guiding 技術, 使Mobile Anchor 依現有Static Sensors 的位置精準程度作有效率的移動，實驗顯示，本論文所提的方法不僅可使Static Sensors快速改善定位的精準度，亦可最佳化Mobile Anchor有效移動，使其單位移動量所改善的位置精準度最大，得到的利益最多。

In the most proposed range-free algorithms, nodes estimate their location using the geometric constraints imposed by the location of mobile anchor. However, there is no discussion on how the mobile anchor moves so that all sensor nodes can obtain the maximal location accuracies under the constraints of time for localization or the remaining energy of the robot. This paper assumes that traditional range-free algorithms have been executed for a certain time period and the deployed sensors are with different location accuracies. We propose path guiding mechanisms that sensor nodes cooperatively guide the mobile anchor moving along an efficient path which can maximize the improvement of location accuracies or minimize the accuracy differences for all sensor nodes in a given WSN. Experimental study reveals that the proposed path guiding mechanisms effectively guide the mobile anchor moving along the efficient path and thereby saves time and energy consumptions for improving or balancing the location accuracies of all sensor nodes.

List of Contents

List of Contents	I
List of Figures	II
I.Introduction	1
II.Related Work	4
III.Network Environment & Problem Statement	7
3.1 Network Environment	7
3.2 Problem Statement	7
3.3 Problem formation	9
IV.The Guiding Mechanisms	12
4.1 Identifying Promising Region Phase (IPRP)	12
4.2 Weighting Phase (WP)	14
4.3 Beacon Locations Selection Phase (BLSP)	17
4.3.1 Benefit-Based Selection Scheme	18
4.3.2 Distance-Based Selection Scheme	20
4.3.3 Accuracy-Balancing Based Selection Scheme	21
4.4 Path Construction Phase (PCP)	26
V.Performance Study	29
5.1 The Impact of Network Density and Localization Time on Mean Position Error	29
5.2 The ratio of Localization Accuracies and Energy Consumption	31
5.3 The Mean Error and threshold 	33
5.4 Performance Comparison in terms of Balance Index	34
5.4 A Look on the Physical Scenarios	35
VI.Conclusions	39
REFERENCES	40
附錄-英文論文	42



List of Figures

Figure 1: An example that illustrates the calculation of new estimate region ERs,t’ of sensor s when it receives a beacon b(xm, ym)t’ from mobile anchor m.	8
Figure 2: Mobile anchor moves along path p1 and broadcasts a beacon at location b will contribute more benefits to the localization than moves along path p2 and broadcasts a beacon at location c.	10
Figure 3: The promising region of sensor s can be determined by the constraint that the mobile anchor is located with the communication range of sensor s.	13
Figure 4: The promising region of sensor s excludes the sub-region where the range-constraint contains the estimate region of sensor s.	14
Figure 5: (a)The gray area represents the possible locations that mobile anchor m can communicate with sensor s. (b)The new estimate region ERs,t’, denoted by the dotted rectangle, is evaluated according to the new range-constraint.	16
Figure 6: Mobile anchor broadcasts a beacon at grid g(x, y) so that a new estimate region ERs,t’ of sensor s has been formed. Let the ERs,t’ is sized with m×n. The helpless region to ERs,t’ will be the gray rectangle.	18
Figure 7: An example of applying the Benefit-Based Grid Selection Scheme to select grids for broadcasting beacons.	20
Figure 8: (a) Grid g(2, 4) is selected as a beacon location in  . (b) Broadcasting a beacon at grid g(2, 4) will form a new ER which is represented by the dotted rectangle. (c) The shadow region represents the new HLR. (d) Grid g(6, 3) is located outside the HLR and hence is selected for being a beacon location. (e)The shadow region represents the new ER after selecting grid g(6, 3) as a beacon location. (f)The SEBA procedure is completed when  is covered by HLR set.	26
Figure 9: An example for illustrating the PCP phase. (a)The edge connecting g(xm, ym) and a is constructed. (b) Another edge that connects grids a and b is constructed.	27
Figure 10: The impact of network densities and time spent for localization on the position error.	31
Figure 11: BB-PGM, DB-PGM and AB-PGM achieve higher localization efficiency than the other two mechanisms under the energy constraint.	33
Figure 12: The impact of threshold values on the anchor’s energy consumption as well as the mean position error.	34
Figure 13: DB-PGM and AB-PGM achieves higher balance of the location accuracies of all sensors under the constraint of energy consumption.	35
Figure 14: The snapshot of the simulation scenario.	37
Figure 15: The path and the beacon locations by applying the proposed BB-PGM,DB-PGM and AB-PGM.	37

[1]D. Niculescu, and B. Nath, “Ad-hoc positioning system (APS) using AOA,” Proc. of IEEE Infocom, 2003.
[2]P. Bahl, and V. N. Padmanabhan, “RADAR: an in-building RF-based user location and tracking system,” Proc. of IEEE Infocom, 2000.
[3]K. Chintalapudi, A. Dhariwal, R. Govindan, and G. Sukhatme, “Ad-hoc localization using ranging and sectoring,” Proc. of IEEE Infocom, 2004.
[4]Y. Shang, W. Ruml, and Y. Zhang, “Improved MDS-based localization,” Proc. of IEEE Infocom, 2004.
[5]T. He, C. Huang, B. Lum, J. Stankovic, and T. Adelzaher, “Range-free localization schemes for large scale sensor networks,” Proc. of ACM MobiCom, 2003. 
[6]Chong Liu ,Kui Wu, and Tian HeComputer, “Sensor Localization with Ring Overlapping Based on Comparison of Received Signal Strength Indicator,” Proc. of IEEE  MASS, 2004. 
[7]Vijayanth Vivekanandan, and Vincent Wong, “Concentric Anchor-Beacons (CAB) Localization for Wireless Sensor Networks,“ Proc. of IEEE ICC, 2006.
[8]Srinath T V, “Localization in Resource Constrained Sensor Networks using a Mobile Beacon with In-Ranging,” Proc. of IEEE WOCN, 2006.
[9]Jang Ping Sheu, Jian Ming Li, and C. S. Hsu, “A Distributed Location Estimating Algorithm for Wireless Sensor Networks,” Proc. of IEEE SUTC, 2006.
[10]A. Galstyan, B. Krishnamachari, and K. Lerman, ”Distributed online localization in sensor networks using a moving target,” Proc. of IEEE  IPSN, 2004.
[11]Yongguo Mei, Yung-Hsiang Lu, Y. Charlie Hu, and C.S. George Lee, "Deployment Strategy for Mobile Robots with Energy and Timing Constraints," Proc. of IEEE ICRA, 2005.
[12]X. Zeng, R. Bagrodia and M. Gerla, “GloMoSim: a library for parallel simulation of large-scale wireless networks,” Proc. of PADS, 1998.