近年來，許多Range-Free定位技術利用具位置資訊的移動式感測器，幫助無位置資訊的固定式感測器獲得位置資訊，這類技術主要可分為 Area-Based 與 Point-Based 兩大類。雖然這兩類技術均可有效的賦予感測器位置資訊，然而，其中卻依然存在一些問題。在Area-Based 定位技術中，其並無針對移動式感測器該如何行走、該在哪些地點發送訊號，才可有效的提高移動式感測器定位效率進行探討，導致移動式感測器無法有效率的使用其有限的電量。此外，Area-Based 定位技術亦可能由於定位精準度不高，導致感測器間無法區別相對位置，進而影響現存需相對位置資訊之技術的效能，如具位置知覺之繞徑協定。另一方面，Point-Based 定位技術沒有將固定式感測器定位的時間納入考量，導致所有固定式感測器完成定位的時間是不可預期的。有鑑於此，本論文提出三種不同的定位技術，分別為Anchor-Guiding (AG) Scheme、Differentiating Relative Location (DRL) Scheme 與 Rapid Localization (RL) Scheme，用以改善現存 Area-Based 及 Point-Based 技術的效能。首先，本論文所提出之 AG 技術屬於Area-Based定位技術，其可幫助移動式感測器規劃移動路線及發送訊號的地點，進而提昇固定式感測器的位置精準度，並讓移動式感測器的移動方式更有效率。接著，本論文所提出之DRL技術為另一個Area-Based定位技術，其可幫助固定式感測器區別其與鄰居的相對位置，用以提高現存需位置資訊之技術的效能。最後，本論文所提出之 RL 技術屬於Point-Based技術，其將固定式感測器的定位時間納入考量，大幅減少固定式感測器定位所需的時間，進一步改善現存 Point-Based 定位技術的效能。實驗結果顯示，本論文所提出的三個定位技術，可有效的解決現存 Area-Based 及 Point-Based 技術所產生的問題，大幅提昇感測器定位的效能。

Recently, many range-free localization approaches employed a location-aware mobile anchor to help sensors acquire their location information. These approaches can be mainly classified into two categories: area-based localization approaches and point-based localization approaches. Although both area-based and point-based approaches can provide location information for sensors, however, some problems still exist. The area-based approaches did not discuss how the mobile anchor moves and where the beacons should be broadcasted. That is, the mobile anchor might consume a lot of energy in broadcasting unavailable beacons that cannot help sensors acquire accurate location information. In addition, since the area-based approaches only offered sensors rough location information, sensors might not distinguish relative locations with each of their neighbors, leading to a poor performance for some applications such as the location-aware routing. On the other hand, the point-based approaches did not take into account the time required for each sensor to complete localization process. Thereby, the time required for all sensors to exactly acquire their locations is unpredictable. This thesis proposes three localization schemes, including Anchor-Guiding (AG) scheme, Differentiating Relative Location (DRL) scheme, and Rapid Localization (RL) scheme. The AG scheme is developed for the mobile anchor to construct an efficient movement path and determine beacon locations, while the DRL scheme aims to help sensors distinguish relative locations with each of their neighbors. Finally, the RL scheme reduces the time required for each sensor to determine its location. Theoretical analyses and performance evaluations show that the three proposed schemes can significantly improve the performance of existing localization techniques.

Contents
Contents IV
List of Figures VI
List of Tables XI
Chapter 1. Introduction 1
Chapter 2. Related Work 5
2.1 Range-Based Localization Technique 5
2.2 Range-Free Localization Technique 7
Chapter 3. The Anchor-Guiding (AG) Scheme 12
3.1 Network Environment and Problem Statement 12
3.1.1 Network Environment 12
3.1.2 Problem Statement 13
3.2 The AG Scheme 17
3.2.1 Identifying Promising Region Phase 18
3.2.2 Weighting Phase 22
3.2.3 Beacon Locations Selection Phase 25
3.2.4 Path Construction Phase 30
3.3 Theoretical Analysis 32
3.4 Performance Study 38
3.5 Summary 49
Chapter 4. The Differentiating Relative Location (DRL) Scheme 50
4.1 Network Environment and Problem Statement 50
4.1.1 Network Environment 50
4.1.2 Problem Statement 51
4.2 The DRL Properties 54
4.2.1 Basic Concept 54
4.2.2 Handling the Table Ambiguous Problem 56
4.2.3 Handling the Location Ambiguous Problem 60
4.3 Moving Path for the Mobile Anchor 63
4.3.1 Two-Phase DRL Mechanism with Tones 64
4.3.2 Single-Phase DRL Mechanism with Tones 68
4.4 Theoretical Analysis 74
4.5 Performance Study 83
4.6 Summary 92
Chapter 5. The Rapid Localization (RL) Scheme 93
5.1 Network Environment and Problem Statement 93
5.2 The Path Planning Mechanism for the Mobile Anchor 96
5.3 The Location Determination Mechanism for Each Static Sensor 98
5.3.1 The LE Process 98
5.3.2 The LD Process 102
5.4 Theoretical Analysis 107
5.5 Performance Study 122
5.6 Summary 132
Chapter 6. Conclusions 133
References 136

List of Figures
1.1 Distinguishing relative locations of neighboring sensors has a significant impact on location-aware routing performance. 3
3.1 An example that illustrates the calculation of new estimative region ERs,t’ of sensor s when it receives a beacon b(xm, ym)t’ from mobile anchor m. 14
3.2 Mobile anchor moving along path p1 and broadcasting a beacon at location b will contribute more benefits for localization than moving along path p2 and broadcasting a beacon at location c. 16
3.3 The promising region of sensor s can be determined by the constraint that the mobile anchor is located within the communication range of sensor s. 18
3.4 The condition that ERs,t is fully covered by Rt’(xm, ym) is necessary for deriving the HLRs,t. That is, the Exps. (3.9), (3.10), (3.11), and (3.12) hold. 19
3.5 (a) The gray area represents the possible locations of sensor s that mobile anchor m can communicate with sensor s. (b) The new estimative region ERs,t’, denoted by the dotted rectangle, is evaluated according to the new range-constraint. 24
3.6 (a) Mobile anchor broadcasts a beacon at grid g(x1, y1) so that a new estimative region ERs,t1 of sensor s has been formed. (b) A new range-constraint which constructed by mobile anchor at grid g(x2, y2) will totally cover the ERs,t1. (c) The shadow region shows the new helpless region formed due to the change of ER of s from ERs,t0 to ERs,t1. 26
3.7 An example of applying the Benefit-Based Selection policy to select grids for broadcasting beacons. 28
3.8 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. 32
3.9 The effective broadcasting rectangle can be treated as a rectangle region which has the effective communication area size as the circle region. 33
3.10 The effective broadcasting rectangle of the sensors is partitioned into the grids with the size of d ×d. 33
3.11 Applying the BBS policy, the anchor will move and beacon t times and the moving distance for each beacon is Db in the worst case. 36
3.12 The impact of network density and time spent for localization on the location error. 40
3.13 The BB-AGM and DB-AGM achieve higher localization efficiency than the other two mechanisms under the energy constraint. 42
3.14 The impact of threshold values on the anchor’s energy consumption as well as the mean location error by applying the BB-AGM approach. 43
3.15 Comparison of the routing error of the BB-AGM, DB-AGM and Random approaches. 44
3.16 The snapshot obtained by applying the BB-AGM. 45
3.17 The BB-AGM achieves better performance in terms of location inaccuracies of all sensors under the constraint of mobile anchor’s remaining energy. 46
3.18 Comparison of Balance Index of the proposed approaches and Snake-Like movement under various threshold values where the constraint of mobile anchor’s remaining energy is set at 10 kW. 47
3.19 Comparison of the BB-AGM, DB-AGM, and Snake-Like in terms of beacon benefits. 48
3.20 Comparison of the BB-AGM, DB-AGM, and Snake-Like in terms of BI. 48
4.1 The path construction for mobile anchor is discussed based on the snake-like path. 51
4.2 Sensors sa and sb distinguish their relative locations with each other based on their EntryE tables. 54
4.3 Sensors sa and sb enter tone-signal at the same time and hence they cannot distinguish their relative locations. 55
4.4 Relative location cannot be correctly determined because the shape of tone-signal range is a disc. 55
4.5 The scenario applied in the proof of Lemma 4.1: (a) The moment that sa enters tone-signal range. (b) The moment that sa leaves tone-signal range. (c) The combination of Figures 4.5(a) and 4.5(b). 57
4.6 If sensors sa and sb enter tone-signal range at the same time, they can distinguish their relative location relation by comparing the values of |λa| and |λb|. 58
4.7 Two scenarios that have the same contents in EntryE and ExitE tables but have different relative location relations. (a) The first scenario arisen the Location Ambiguous Problem. (b) The second scenario arisen the Location Ambiguous Problem. 60
4.8 If d>0, the relation sa||sb holds. Otherwise, the relation sb||sa holds. 61
4.9 The Procedure of Enter_Leave_Tone(Status). 65
4.10 The Procedure of Receiving_Broadcast(Message). 66
4.11 The Procedure of Table_Completed(Direction). 67
4.12 There are three possible situations that sensors sa and sb can know whether or not they are located at the same side of the anchor’s trajectory. 70
4.13 The Procedure of Enter Tone. 72
4.14 The Procedure of Receiving Entering Message. 72
4.15 The Procedure of Single-Phase DRL. 73
4.16 The monitoring region can be divided into several basic segments. 75
4.17 Sensors located in the green regions can receive boundary tones while sensors located in the gray regions are s_abg^enter or s_abg^leave, respectively. 76
4.18 Two situations that the relative locations cannot be correctly determined. 79
4.19 The mobile anchor moves from STP (p, q) to location (p+2r, q). 80
4.20 If any sensor located in the shadow red region, it must leave the tone-signal range earlier than sa. 81
4.21 The comparison of four mechanisms in terms of routing length. 85
4.22 The impacts of duty time ξ on the success percentage of distinguishing relative locations. 86
4.23 The comparison of the proposed mechanisms in terms of EEI. 87
4.24 The radio propagation pattern. 88
4.25 The impacts of transmission range r and the value of β on success percentage of distinguishing relative locations. 89
4.26 The impacts of ignoring time ε on the error and undistinguishable percentages for distinguishing relative locations of any two neighboring sensors. 89
4.27 The impacts of transmission range r and the value of β on routing performance. 90
4.28 The impacts of network density and the value of β on location accuracy. 91
5.1 The path planning mechanism develops a snake-like movement path for the mobile anchor to ensure that all sensors can receive beacon messages from the mobile anchor. 97
5.2 After completing the LE process, each sensor can calculate its two candidate locations. 99
5.3 The pseudocode of the LE process. 102
5.4 The proposed AN and UN rules can help each sensor eliminate the inappropriate location of its two candidate locations in most situations. 104
5.5 The proposed AN and UN rules might be unavailable when both candidate locations of a sensor are too close. 105
5.6 The pseudocode of the LD process. 106
5.7 For fairness reason, both RL and PB apply the same movement strategy to the mobile anchor. 108
5.8 Consider that there are npath movement paths existed in the upper semicircle of node sj’s communication disk. 110
5.9 The sensors in set S_RL_listen(2) can determine their locations without applying the MA rule. 119
5.10 Radio propagation pattern of the mobile anchor. 122
5.11 The average location errors of the four compared approaches by varying the mobile anchor’s beacon interval. 124
5.12 The average location errors of the four compared approaches by varying the value of ξ. 125
5.13 The success percentages of the four compared approaches by varying the value of ξ. 127
5.14 The EIs of the four compared approaches over time. 130

List of Tables
4.1 Applied rule and result of relative location corresponding to each case 63
4.2 Simulation Parameters 84
5.1 Notations used in this analysis 109
5.2 Simulation Parameters 123

[1] S. He, J. Chen, and Y. Sun, “Coverage and Connectivity in Duty-Cycled Wireless Sensor Networks for Event Monitoring,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 3, pp. 475–482, Mar. 2012.
[2] X. Wang, M. Fu, and H. Zhang, “Target Tracking in Wireless Sensor Networks Based on the Combination of KF and MLE Using Distance Measurements,” IEEE Transactions on Mobile Computing, vol. 11, no. 4, pp. 567–576, Apr. 2012.
[3] H. Zhang, and H. Shen, “Energy-Efficient Beaconless Geographic Routing in Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 6, pp. 881–896, Jun. 2010.
[4] B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” ACM International Conference on Mobile Computing and Networking (ACM MobiCom), USA, Aug. 2000.
[5] E. Biagioni and G. Sasaki, “Wireless Sensor Placement for Reliable and Efficient Data Collection,” IEEE Hawaii International Conference on System Sciences (IEEE HICSS), USA, Jan. 2003.
[6] L. Schwiebert, S. K. S. Gupta, and J. Weinmann, “Research Challenges in Wireless Networks of Biomedical Sensors,” ACM International Conference on Mobile Computing and Networking (ACM MobiCom), Italy, Jul. 2001.
[7] J. O’Rourke, Art Gallery Theorem and Algorithms, New York, NY: Oxford University Press, 1987.
[8] G. Dommety and R. Jain, “Potential Networking Applications of Global Positioning Systems (GPS),” Technical Report TR–24, The Ohio State University, Apr. 1996.
[9] B. W. Parkinson and S. W. Gilbert, “NAVSTAR: Global Positioning System–Ten Years Later,” Proceedings of the IEEE, vol. 71, no. 10, pp. 1177–1186, Oct. 1983.
[10] Y. Weng, W. Xiao, and L. Xie, “Total Least Squares Method for Robust Source Localization in Sensor Networks Using TDOA Measurements,” International Journal of Distributed Sensor Networks, vol. 2011, Article ID 172902, 2011.
[11] D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS) Using AoA,” Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM), USA, Mar. 2003.
[12] J. Hightower, G. Boriello, and R. Want, “SpotON: An Indoor 3D Location Sensing Technology Based on RF Signal Strength,” UW CSE Technical Report #2000–02–02, University of Washington, Feb. 2000.
[13] P. Bahl and V. N. Padmanabhan, “RADAR: An In-Building RF-Based User Location and Tracking System,” Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM), Israel, Mar. 2000.
[14] N. Patwari and A. O. Hero III, “Using Proximity and Quantized RSS for Sensor Localization in Wireless Networks,” ACM International Workshop on Wireless Sensor Networks and Applications (ACM WSNA), USA, Sep. 2003.
[15] A. Savvides, C. C. Han, and M. B. Strivastava, “Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors,” ACM International Conference on Mobile Computing and Networking (ACM MobiCom), Italy, Jul. 2001.
[16] N. B. Priyantha, A. Chakraborty, H. Balakrishnan, “The Cricket Location-Support System,” ACM International Conference on Mobile Computing and Networking (ACM MobiCom), USA, Aug. 2000.
[17] D. Niculescu and B. Nath, “DV Based Positioning in Ad Hoc Networks,” Telecommunication Systems, vol. 22, no. 1–4, pp. 267–280, Jan. 2003.
[18] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-Free Localization Schemes for Large Scale Sensor Networks,” ACM International Conference on Mobile Computing and Networking (ACM MobiCom), USA, Sep. 2003.
[19] Y. Kwon and G. Agha, “Passive Localization: Large Size Sensor Network Localization Based on Environmental Events,” ACM/IEEE International Symposium on Information Processing in Sensor Networks (ACM/IEEE IPSN), USA, Apr. 2008.
[20] M. Rudafshani and S. Datta, “Localization in Wireless Sensor Networks,” ACM/IEEE International Symposium on Information Processing in Sensor Networks (ACM/IEEE IPSN), USA, Apr. 2007.
[21] V. Vivekanandan and V. W. S. Wong, “Concentric Anchor Beacon Localization Algorithm for Wireless Sensor Networks,” IEEE Transactions on Vehicular Technology, vol. 56, no. 5, pp. 2733–2744, Sep. 2007.
[22] K. Kim and W. Lee, “MBAL: A Mobile Beacon-Assisted Localization Scheme for Wireless Sensor Networks,” IEEE International Conference on Computer Communications and Networks (IEEE ICCCN), USA, Aug. 2007.
[23] G. Teng, K. Zheng, and W. Dong, “Adapting Mobile Beacon-Assisted Localization in Wireless Sensor Networks,” Sensors, vol. 9, no. 4, pp. 2760–2779, Apr. 2009.
[24] B. Xiao, H. Chen, and S. Zhou, “Distributed Localization Using a Moving Beacon in Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 5, pp. 587–600, May 2008.
[25] 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 (IEEE WOCN), India, Apr. 2006.
[26] S. Zhang, J. Cao, L. Chen, and D. Chen, “Accurate and Energy-Efficient Range-Free Localization for Mobile Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 9, no. 6, pp.897–910, Jun. 2010.
[27] J. P. Sheu, W. K. Hu, and J. C. Lin, “Distributed Localization Scheme for Mobile Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 9, no. 4, pp. 516–526, Apr. 2010.
[28] S. Zhang, J. Cao, L. Chen, and D. Chen, “Locating Nodes in Mobile Sensor Networks More Accurately and Faster,” IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (IEEE SECON), USA, Jun. 2008.
[29] A. Galstyan, B. Krishnamachari, K. Lerman, and S. Pattem, “Distributed Online Localization in Sensor Networks Using a Moving Target,” ACM/IEEE International Symposium on Information Processing in Sensor Networks (ACM/IEEE IPSN), USA, Apr. 2004.
[30] K. F. Ssu, C. H. Ou, and H. C. Jiau, “Localization with Mobile Anchor Points in Wireless Sensor Networks,” IEEE Transactions on Vehicular Technology, vol. 54, no. 3, pp. 1187–1197, May 2005.
[31] C. H. Ou and K. F. Ssu, “Sensor Position Determination with Flying Anchors in Three-Dimensional Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 7, no. 9, pp. 1084–1097, Sep. 2008.
[32] C. H. Ou, K. F. Ssu, and H. C. Jiau, “Range-Free Localization with Aerial Anchors in Wireless Sensor Networks,” International Journal of Distributed Sensor Networks, vol. 2, no. 1, pp. 1–21, 2006.
[33] P. Bergamo and G. Mazzini, “Localization in Sensor Networks with Fading and Mobility,” IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (IEEE PIMRC), Portugal, Sep. 2002.
[34] X. Zeng, R. Bagrodia, and M. Gerla, “GloMoSim: A Library for Parallel Simulation of Large-Scale Wireless Networks,” IEEE Workshop on Parallel and Distributed Simulation (IEEE PADS), Canada, May 1998.