Localization Algorithms for Wireless Sensor Networks by Vijayanth Vivekanandan B . A . S c . , Electr ical Engineering, University of Br i t i sh Columbia , 2003 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F A P P L I E D S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S (Electrical and Computer Engineering) T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A December 2005 © Vijayanth Vivekanandan, 2005 i i Abstract Many applications in wireless sensor networks require sensor nodes to obtain their ab-solute or relative geographical positions. Due to the size, cost and energy restrictions imposed by sensor nodes, only a few nodes can be equipped wi th the Globa l Posit ioning System (GPS) capability and act as anchors for the rest of the network. The algorithms based on classical Mult idimensional Scaling ( M D S ) [1][2] only require three or four anchor nodes and can provide higher accuracy than some other schemes. In the first part of this thesis, we propose and analyze the use of ordinal MDS for localization in wireless sensor networks. Ordina l M D S differs from classical M D S by that it only requires a monotonicity constraint between the shortest path distance and the Euclidean distance for each pair of nodes. Simulat ion studies are conducted under square and C-shaped topologies with different connectivity levels and number of anchors. Results show that ordinal M D S provides a lower position estimation error than classical M D S in both hop-based and range-based scenarios. In the second part of this thesis, we propose a concentric anchor-beacons ( C A B ) localization algorithm for wireless sensor networks. C A B is a range-free approach and uses a small number of anchor nodes. Each anchor emits several beacons at different Abstract i i i power levels. From the information received by each beacon heard, nodes determine which annular ring they are located wi th in each anchor. Each node uses the approximated center of intersection of the rings as its position estimate. Simulat ion results show that the estimation error reduces by half when anchors transmit beacons at two different power levels periodically instead of at a single level. C A B also gives a lower estimation error than other range-free localization schemes (e.g., Centroid, A P I T ) when the anchor-to-node range ratio is less than four. iv Table of Contents Abstract ii Table of Contents iv List of Tables viii List of Figures ix List of Abbreviations xii Acknowledgements xiv 1 Introduction 1 1.1 Motivations and Objectives 2 1.2 Structure of the Thesis 5 2 Related Work on Localization 6 2.1 Connectivity-Based Algorithms 7 2.1.1 Convex Optimization 7 2.1.2 MDS-MAP 9 Table of Contents v 2.1.3 M D S - M A P wi th Patches and Refinement (P, R) 11 2.1.4 Anchor-Init iated M D S - M A P , On-Demand M D S 12 2.2 Range-Based Techniques 15 2.2.1 T E R R A I N using A B C 15 2.2.2 A P S ' 16 . 2.2.3 Self-Positioning Algor i thm 18 2.2.4 Ad-hoc Locat ion System ( A H L o S ) . < . . . . 19 2.2.5 N - H o p Mult i la tera t ion Pr imi t ive 21 2.2.6 H o p - T E R R A I N with Refinement . ' 23 2.2.7 A P S / H o p - T E R R A I N / N - h o p Mult i la tera t ion Pr imi t ive 25 2.3 Angle-Based Techniques 26 2.3.1 A P S using A O A 26 2.3.2 DV-pos i t ion 29 2.3.3 Directionality Local izat ion 30 2.3.4 A d - H o c Ranging and Sectoring 31 2.4 Range-Free Techniques 32 2.4.1 Centroid 32 2.4.2 Approximated Point-in-Triangulation ( A P I T ) 34 2.5 Other Novel Techniques 36 2.5.1 Time-based Positioning Scheme T P S 36 2.5.2 Secure Posit ioning 38 Table of Contents v i 2.5.3 Anchor-Free Local izat ion ( A F L ) 40 2.5.4 Sequential Monte Carlo Localizat ion ( M C L ) 42 3 Ordinal Multidimensional Scaling 45 3.1 Motivations and Assumptions 45 3.2 MDS-MAP(P, O) Algor i thm 47 3.3 Performance Evaluat ion and Comparison 51 3.3.1 Random Uniform Network Topology 52 Hop-Based Performance 52 Range-Based Performance 55 Sensitivity Analysis of Range Error on Posit ioning Error 57 Sensitivity Analysis of Anchors ' Locat ion on Posit ioning Error . . 59 Further Improvement v ia (Optional) Globa l Relative M a p Refinement 61 3.3.2 Random Irregular Network Topology 63 Hop-Based Performance 64 Range-Based Performance 65 Further Improvement v ia (Optional) Globa l Relative M a p Refinement 67 3.4 Summary 69 4 Concentric Anchor-Beacons (CAB) Localization Algorithm 71 4.1 Motivat ions and Assumptions . 71 4.2 C A B Algor i thm 74 Table of Contents vii 4.3 Discussion 79 4.4 Performance Evaluat ion and Comparison 80 4.4.1 Performance of C A B 81 4.4.2 Comparisons between C A B , A P I T , and Centroid 88 4.5 C A B Extension to other Localizat ion Schemes 92 4.5.1 Possible Scheme-Specific Modifications 93 4.6 Summary 95 5 Conclusions and Future Work 97 5.1 Future Work 98 Bibliography 101 List of Tables 4.1 Information collected by a sensor from its anchors ix List of Figures 2.1 Connectivi ty Constraints 8 2.2 Sequential localization from starting anchor (A) to ending anchor (D). . . 13 2.3 On-Demand positioning from node A to anchors D , H , L 14 2.4 D V Euclidean model 18 2.5 Collaborative Mult i la terat ion model 21 2.6 Nodes obtaining relative angle measurements to other nodes 27 2.7 Localizat ion using Angulations 28 2.8 DV-pos i t ion model 29 2.9 Local izat ion using synchronized, offset, rotating beacon signals 30 2.10 Loca l grid maintaining overlapped triangle regions for localization 34 2.11 A P I T test using node neighbors 35 2.12 T P S coverage model 37 2.13 Sensor coverage model 39 2.14 Different configuration wi th degrees of freedom 41 2.15 Topology construction for fold-freedom 42 Lis t of Figures x 3.1 Topology results of hop-based M D S - M A P ( P , C) and M D S - M A P ( P , 0 ) . . 53 3.2 Performance of hop-based M D S - M A P (P, C) and M D S - M A P (P, 0 ) . . . . 54 3.3 Topology results of range-based M D S - M A P ( P , C) and M D S - M A P ( P , O) . 56 3.4 Performance of range-based M D S - M A P ( P , C) and M D S - M A P ( P , O) . . . 57 3.5 Effects of node ranging error on range-based M D S - M A P ( P , O) performance. 58 3.6 Node ranging error comparison between range-based M D S - M A P ( P , C) and M D S - M A P ( P , O) 59 3.7 Anchor topology results of range-based M D S - M A P ( P , O) . . . '. 60 3.8 Performance of hop-based M D S - M A P ( P , O) and MDS-MAP(P, 0 , R). . 61 3.9 Performance of range-based M D S - M A P ( P , O) and M D S - M A P ( P , O, R ) . 62 3.10 C-shaped topology results between hop-based M D S - M A P ( P , C) and M D S -M A P ( P , O) 64 3.11 Performance comparison between hop-based M D S - M A P ( P , C) and M D S -M A P (P, O) in a C-shaped network 65 3.12 C-shaped topology results between range-based M D S - M A P ( P , C) and M D S -M A P (P, O) 66 3.13 Performance of range-based M D S - M A P ( P , C ) and M D S - M A P ( P , 0 ) in a C-shaped network 67 3.14 Performance comparison between hop-based M D S - M A P ( P , O) and M D S -M A P (P, 0 , R) in a C-shaped network 68 List of Figures x i 3.15 Performance comparison between range-based M D S - M A P ( P , O) and M D S -M A P (P, 0 , R) in a C-shaped network 69 4.1 Anchor beacon transmission ranges wi th 3 power levels 73 4.2 A n example of localization using C A B 76 4.3 Irregular radio patterns for different values of D O I 81 4.4 Comparison of percentage of nodes localizable versus percentage of anchors deployed for varying levels of A N R 82 4.5 Average estimation error under different number of power levels of the beacons for C A B - E A and C A B - E W 83 4.6 Comparison of estimation error between C A B - E W and C A B - E A 85 4.7 Comparison of estimation error between C A B - E A and C A B - E W for dif-ferent D O I values 86 4.8 Comparison of estimation error using randomly heard anchors versus op-t imal ly chosen anchors 87 4.9 Percentage of anchors deployed comparison between Centroid, A P I T , C A B -E A , and C A B - E W 89 4.10 A N R comparison between Centroid, A P I T , C A B - E A , and C A B - E W . . . 90 4.11 D O I comparison between Centroid, A P I T , C A B - E A , and C A B - E W . . . . 91 List of Abbreviations A B C Assumption Based Coordinates A F L Anchor-Free Localizat ion A H L o S Ad-hoc Locat ion System A N R Anchor-to-Node Range A O A Angle-of-Arrival A P I T Approximated Point-In-Triangle A P S Ad-hoc Posit ioning System C A B Concentric Anchor-Beacons C A B - E A Concentric Anchor-Beacons with Equa l A r e a C A B - E W Concentric Anchor-Beacons wi th Equa l W i d t h D O I Degree of Irregularity D V Distance-Vector List of Abbreviations x i i i E K F Extended K a l m a n Fi l ter G P S Globa l Posit ioning System L M I Linear M a t r i x Inequality L R G Locat ion Reference Group M C L Monte Carlo Localizat ion M D S Mult idimensional Scaling P A V Pool-Adjacent Violators RSS Received Signal Strength S D P Semi-Definite Program S M C Sequential Monte Carlo T D O A Time-Difference-of-Arrival T E R R A I N Triangulation via Extended Range and Redun-dant Association of Intermediate Nodes T O A Time-of-Arr ival T P S Time-based Posit ioning Scheme xiv Acknowledgements I would like to express my sincere gratitude to my graduate supervisor Dr . Vincent Wong for his guidance and support during the course of my graduate studies. I appreciate the considerable amount of time and effort he invested in helping me wi th my research and thesis. Special thanks to Y i Shang, Wheeler R u m l , and Y i n g Zhang for providing us with their software code for testing and modification. I would also like to thank my fellow colleagues who have provided helpful suggestions along the way. This thesis could not have been completed without the endless encouragement and love from my family, I am deeply indebted to them. This work is supported by the Natural Sciences and Engineering Research Counci l of Canada under grant number 261604-03. 1 Chapter 1 Introduction The miniaturizat ion of small devices capable of sensing and communicating with each other has made the possibility of deploying large-scale wireless sensor networks a reality [3]. The. purpose of these networks are to remotely sense an area and communicate the results back to a central authority. In order for these sensory data to be valuable, the location from which they were obtained must be known. The functions presented in liter-ature range from mil i tary applications to wildlife monitoring. These applications propose of hundreds to thousands of sensors being dropped by airplane over a certain coverage area. This type of deployment would require the nodes to configure their network by themselves. Such vast deployments would restrict the individual placement or program-ming of al l nodes with their unique locations, and hence some system must be in place to accurately and efficiently localize these sensors. Thus, these sensor nodes have l imited processing power and battery supply, and need to configure themselves autonomously. For applications such as position-based routing, event discovery and target tracking, the geographic location of the sensor nodes need to be known. Consider the example where a sensor network is used to detect a fire event in a forest. Once a sensor node has detected that the temperature is higher than a certain threshold, it sends a message to the Chapter 1. Introduction 2 central authority by relaying through other nodes in a multi-hop manner. The message needs to indicate the location of the node which detected the event. When an event occurs (or a stimulus is detected), the sensor nodes can forward the data information along wi th their coordinates. Thus, localization of sensor nodes is important in certain applications. 1.1 Motivations and Objectives The current location technology such as global positioning system (GPS) does not meet the sensor nodes' requirements for low cost, low energy consumption, and small size [4]. In addition, G P S requires line-of-sight to global satellites that may not be available for some applications in sensor networks. In order to solve this dilemma, nodes in the network must collaboratively execute an algorithm in which the objective is to provide each node with an estimate of its position in the network. Posit ion estimates may be based on a relative coordinate system within the network, or an absolute geographical reference. Al though, much research has been conducted in the area of localization for cellular networks and mobile ad-hoc networks, sensor networks provide unique challenges that cannot be solved by using traditional techniques from these other areas. Various centralized [1][5] and distributed [6] [7] localization algorithms have been pro-posed recently. W i t h respect to robustness and energy efficiency, distributed algorithms are preferred over centralized schemes. The localization algorithms can further be divided Chapter 1. Introduction 3 into range-based [2] [6], angle-based [8] [9], and range-free [10] [11] approaches. Range-based schemes assume that sensor nodes have the abili ty to obtain distance estimates to other nodes. Th is distance information can be obtained through various techniques involving specialized hardware. Common methods of measuring distance be-tween wireless nodes include the use of received signal strength (RSS), time-of-arrival ( T O A ) , and time-difference-of-arrival ( T D O A ) . In the RSS method, the measured RSS is converted to a distance estimate by using a predetermined path loss model and a reference distance of which the signal strength is known. The T O A method relies on either synchronized nodes being able to determine the time required for a signal to reach the other receiver and the propagation speed, or unsynchronized nodes using round-trip times to estimate distance based on propagation speed. In the T D O A technique, refer-ence nodes determine the time difference between received signals from a common node to form hyperbolic regions that constrain the possible location of the source node, from which distance estimates can be obtained. In angle-based schemes, the relative angular information between nodes is required. This is achieved through the use of antenna ar-rays or directional antennas. Range-free approaches assume that no specialized angle or range-determining hardware is necessary for the sensor nodes. To determine the absolute geographical location, most of the localization algorithms also assume the use of special anchor nodes. Each anchor may be equipped wi th a G P S receiver to obtain, its absolute position information. It is generally true that distributed algorithms are more robust and energy efficient than centralized algorithms. In each Chapter 1. Introduction 4 group, some algorithms assume simple connectivity information between neighboring nodes [1][2] while some others need to gather the ranging information (e.g., estimated distance between two neighboring nodes) [6] [12] [13] and angle information [8] [9]. Since different localization algorithms perform well under different assumptions, it is difficult to determine which one is the optimal scheme. For most of the performance comparisons reported to date, the common performance metric is the localization error normalized with respect to the radio range. This metric depends on the node connectivity (density), anchor population, and the distance measurement error models. Thus, the main objective of our work is to design an accurate localization algorithm which requires a small number of anchor nodes. The second objective is to design a localization algorithm which is accurate, scalable and energy-efficient. These objectives are met by two different schemes we developed. Firs t , wi th the objective of accuracy, a range-based ordinal multidimensional scaling ( M D S ) distributed algorithm called M D S - M A P ( P , O) is proposed and analyzed [14]. Second, a range-free scheme called Concentric Anchor-Beacons ( C A B ) [15] is proposed and analyzed. This C A B scheme is proposed in two different implementations using Equa l Area ( C A B - E A ) and Equa l W i d t h ( C A B - E W ) . The M D S - M A P ( P , 0 ) and C A B algorithms encompass the two different extremes in the sensor localization problem and provide more accurate positioning of nodes than some other schemes proposed in the literature. Chapter 1. Introduction 5 1.2 Structure of the Thesis This thesis is structured as follows. In Chapter 2, a literature survey of the various local-ization schemes previously proposed is presented. These previous schemes are arranged in a taxonomy that identifies the key features that distinguish certain schemes from oth-ers. Add i t iona l schemes are included that provide insight into future research directions for localization in sensor network, for completeness. Chapter 3 describes our proposed ordinal multidimensional scaling ( M D S ) scheme, complete with: motivations and as-sumptions, the M D S - M A P ( P , O) algorithm, the performance evaluation of the scheme followed by a summary of its contributions. Chapter 4 describes our proposed concentric anchor-beacons ( C A B ) scheme. The motivations and assumptions are stated, followed by a detailed explanation of the scheme. This is then followed by a performance eval-uation of the algorithm, a discussion of possible extensions and lastly a summary. The conclusion in Chapter 5 outlines the main contributions of the thesis, summarizes the localization area factors to be optimized and explains future trends in the area. 6 Chapter 2 Related Work on Localization In recent years, the problem of localization in wireless sensor networks have been at-tempted from many different points of view. Most of the previous works have made some assumptions on the environment of the networks that differ amongst others. This has led to diverse techniques being used in localization, such as the availability of careful placement of anchor nodes in a network, the possibility of performing operations cen-trally and then propagating results back to the nodes. The use of range-based techniques by measuring the received signal strength, time of flight and time difference of flight, versus angle-based techniques using antenna arrays and beam finders, have also been ex-plored [4]. This chapter introduces the key papers in sensor localization in the following order: connectivity-based algorithms, range-based techniques, angle-based techniques, range-free techniques, and other novel techniques. One thing is clear however, no single system is the best in all cases. Currently, each application may have to determine the best technique to be used. In this chapter, we provide an overview of several localization algorithms. Survey papers can also be found in [3] [4] [16] [17] [18]. Chapter 2. Related Work on Localization 7 2.1 Connectivity-Based Algorithms The connectivity-based algorithms allow sensor nodes to obtain position estimates wi th-out the requirement of any range or angle measurement hardware. These algorithms rely on the information of which nodes are within communication range of each other, and solve for positions using two similar mathematical approaches. The first proposed scheme is based on convex optimization, which is a centralized method. The second scheme that has been proposed as a centralized method and recently extended to a decentralized case, is based on the psychoanalysis mathematical tool of multidimensional scaling. 2.1.1 Convex Optimization In [5], Doherty et al. considered a sensor network made up of anchor and normal nodes. The anchor nodes are required to impose absolute position constraints on nodes, whereas normal nodes impose relative position constraints. The constraints are based on the max-imum range of communication between nodes, or measured range. If two nodes are able to communicate then, they each must lie wi th in each other's transmission range, hence defining a circular area of possible positions wi th reference to each other. Addi t iona l connectivity wi th other neighboring nodes reduces the possible position of a node to the intersection of the individual constraint sets, as seen in Figure 2.1. These communication constraints imposed are convex and can be mathematically interpreted as linear matr ix inequalities ( L M I ) . The L M I are combined to form a semi-definite program (SDP) [5]. Semi-definite programs are generalizations of linear programs Chapter 2. Related Work on Localization 8 Figure 2.1: Connectivi ty Constraints, [5]. where the objective function is optimized subject to L M I s as opposed to linear inequal-ities. The nature of the solution set being circular regions, the constraints cannot be written as linear inequalities, but rather two-dimensional quadratic inequalities that can be represented as an L M L Thus, constructing the connectivity constraints in the entire network, and characterizing them as an S D P , allows the solution to be computed since many numerical techniques are available to solve SDPs . The drawback of this approach is the centralized computation required to assemble the constraints and solve them before propagating the solutions back to the nodes. F i n a l position estimates of the nodes are obtained from placing a bounding box around the intersection of the constraints on the node's positions and then choosing the center of the box as the estimate. The nature of the model, requires that anchors be placed near the corners and edges of the network for opt imal sufficient performance. It was found that using measured range as opposed to fixed node range improved accuracy of positions, as well, imposing additional angular constraints improved the algorithm at the cost of more information being gathered and computed. In addition, higher connectivities result in more accurate estimates; however networks wi th greater than 2000 nodes are deemed to be too computationally intensive Chapter 2. Related Work on Localization 9 to solve. 2.1.2 M D S - M A P In [1], Shang et al. proposed a localization scheme based on multidimensional scaling ( M D S ) , a psychoanalysis tool used to place objects in space in order to visualize their relationship based on similarity or dissimilarity measures. These measures are treated as distance-like data and used to construct the model, where m objects can be placed in n-dimensional space in order to satisfy the data. However in order to visualize and interpret the data, usually a 2D or 3D embedding of the objects is desired. Several different types of M D S techniques exist. If distance-like measures are available, then Metric MDS is used. If only ordered relationships exist (i.e. distance between objects A and B is greater than distance between objects A and C ) , then Non-Metric (Ordinal) MDS is applicable. Other types of M D S include Probabilistic MDS where objects are placed in space according to their probability distribution; Replicated MDS where measurements are obtained from several different objects' point of view; and Weighted MDS where different dimensions have different weights [1]. Shang et al. applied the Classical MDS, (i.e. the original Met r ic scaling technique), to solve for the positions of the sensor nodes in the 2D case. The M D S result is the optimal least squares configuration to satisfy the distance constraints between the nodes. The nature of M D S is similar to that of convex optimization, where constraints between nodes are used to obtain a satisfactory solution. The difference between metric M D S and convex optimization lies in the fact that in Chapter 2. Related Work on Localization 10 convex optimization the constraints l imit the maximum distance between two nodes, whereas M D S does not. The main drawback of M D S is the fact that it is a centralized scheme. The M D S - M A P algorithm described in [1] is as follows. Firs t , the shortest paths between al l nodes in the network are computed. These distances are used to bui ld the matr ix used by classical scaling to perform M D S , in obtaining the relative positions between all nodes. Lastly, in order to obtain absolute coordinates for the nodes, an alignment transformation is performed using anchor nodes (which know their positions, through G P S or manual configuration). A s opposed to the previous scheme in Section 2.1.1, anchors as well as nodes were randomly placed in the square coverage area. Results showed that wi th fixed range information (i.e. no distance information between nodes) the error was 46% of the range, whereas wi th range information the error reduced to 24% [1]. This was obtained wi th a connectivity of 12, and only 2% anchors, including 5% range estimation error. Also observed was that at low connectivities (less than 9), the performance of connectivity and range estimation was approximately the same. In addition, wi th connectivities greater than 6, more than 93% of al l nodes are localized, though at lower connectivities the position errors are much greater. Lastly, M D S obtained much more accurate results where networks were placed in a grid-like fashion wi th various placement error models. Chapter 2. Related Work on Localization 11 2.1.3 MDS-MAP with Patches and Refinement (P, R) In [2], Shang et al. proposed a decentralized scheme using M D S scaling, and included an additional step in the algorithm by incorporating a refinement scheme to further improve position estimates of nodes [2]. Whereas the work in [1] introduced a centralized M D S - M A P scheme which did not perform well in irregular shaped networks (i.e. non-square coverage areas), the new distributed method in [2] is aimed at improving the M D S performance in order to make it more robust under different network scenarios. The algorithm performs distributed M D S by first forming local maps at each node of the network and then combining the maps to form a global map. The size of the local maps is controlled by the hop count parameter, where nodes only consider other nodes that are wi th in the specified number of hops from their location. Firs t , each node determines which nodes are wi th in its local map. Then, as in centralized M D S , the shortest path distances between all nodes in the local map are computed, and M D S is performed on the constructed distance matrix. Then, a refinement procedure is used to perform the least-squares minimizat ion to improve errors due to inaccurate shortest path measurements, by weighting the distances between one-hop neighbors more than those of two hop neighbors. Next, the local maps are sequentially merged, starting from a randomly picked local map, to form a global map. A n optional least squares minimizat ion refinement is also performed on the global map. Last ly the map is converted to an absolute map by transformation using three or more anchor nodes in the entire network. The results show that the refinement steps are very computationally intensive and Chapter 2. Related Work on Localization 12 take the majority of computation time during local map refining. The size of the local maps is determined by the complexity of the M D S calculation. For random networks with connectivity greater than 12, a two-hop neighborhood was determined to be optimal. For regular and irregular randomly and uniformly placed topologies, the M D S - M A P ( P a t c h , Refinement) scheme consistently achieves errors less than 30% of radio range for con-nectivity only information and less than 20% of radio range for distance information [2]. The drawback of this approach is the significant refinement computation time, the prop-agation of errors from local maps, and sequential merging of local maps. In addition, the classical M D S algorithm performs well under high connectivities, but at low levels other M D S techniques such as ordinal M D S may be more accurate. Compared to other schemes, this algorithm is more robust under irregular topologies and more accurate for the low percentage of anchors present in the system. 2.1.4 Anchor-Initiated M D S - M A P , On-Demand M D S In [13], J i and Zha proposed a distributed M D S scheme in order to localize nodes in a sensor network, using the classical M D S algorithm. Also , they proposed an on-demand algorithm for a sensor node to obtain a position estimate of itself without having to localize the entire network first. In contrast to the previous distributed scheme, the absolute positions of the nodes in the network are obtained sequentially as the algorithm starts. One anchor named starting anchor node in the network wi l l flood its position to the network for other anchors named ending anchors to receive and reply back wi th Chapter 2. Related Work on Localization 13 Figure 2.2: Sequential localization from starting anchor (A) to ending anchor (D), [13]. their positions and the path of nodes traversed to reach them. Average hop counts between starting and ending anchors can be calculated in order to determine anisotropic environments in different directions of the network. Thus, the average radio ranges are computed from the hop counts and distances between the anchors. These ranges are used as distance estimates between nodes along certain paths [13]. Then, the starting anchor estimates the positions of the nodes that are on the paths to the ending anchors. Using • these estimates, the local maps around each node on these paths are computed using M D S of the pairwise distances in the local map and aligned relative to the previously estimated positions of the nodes on the path. This sequential localization proceeds down the path to the ending anchor, resulting in al l positions on the path and one hop away from the path being localized as in Figure 2.2. Nodes further away are localized using pairwise distances to 3 or more nodes that are already localized, and nodes wi th only two localized neighbors perform iterative M D S to compute position estimates. The results show that for 10% anchor population and 12.6 connectivity level, the error rate is less than 30% of radio range for up to 25% distance Chapter 2. Related Work on Localization 14 F igure 2.3: On-Demand positioning from node A to anchors D , H , L , [13] measurement error, in a randomly deployed square coverage area. In a square region with different radio ranges in different areas, the accuracy degrades to less than 35%, which proves that this algorithm is robust in dealing wi th anisotropic environments. The on-demand algorithm allows any sensor node that needs to be localized, to flood the network to at least the 3 nearest anchors and obtain the paths of nodes traversed to reach the anchors. The ini t ia l position of the node is obtained by trilateration using the anchors' positions. M D S is then used to compute relative positions of the nodes neighbors that are on the path to the anchors. Then, M D S is sequentially applied to the neighborhoods of the path towards the anchors. Thus, once the relative positions of the anchors are calculated, an alignment procedure between actual and relative positions is applied and propagated back to the ini t ia l node for an accurate position estimate as in Figure 2.3. W i t h distance measurement error of 25%, 8% anchors, the localization error is less than 40% in anisotropic environments [13]. Chapter 2. Related Work on Localization 15 2.2 Range-Based Techniques Range-based techniques make extensive use of the distance information to obtain position estimates of the sensor nodes. The algorithms presented in this section show many differ-ent approaches to the node localization problem, but have inherently similar architectures in design. One of the predominant architectures is the 3-step node-positioning scheme identified by Langendoen et al. [7]. In the first step, nodes obtain distance estimates to at least 3 anchors according to algorithm specific details. The second step consists of a rough estimation of the node based on the distance information tp the anchors (e.g., lateration, centroid computation, or bounding box). Lastly, a refinement procedure is executed in order to more accurately position all of the nodes from addit ional information such as inter-node distances and positions. Though quite a few exhibit this architecture, others exhibit other novel schemes that in certain applications may be useful. 2.2.1 TERRAIN using ABC These two schemes, developed by Savarese et al. [19], were one of the first proposals for distributed sensor positioning algorithms. Their model assumed a dense distribu-tion of sensor nodes accompanied by a small number of anchors,(e.g., four were used in simulation). Upon random sensor deployment, the sensor nodes have the additional capability to vary their transmission power in order to remain well connected with the network. Hence, the sensor nodes can themselves control their level of connectivity wi th the network, a unique assumption. The first function which T E R R A I N (Triangulation Chapter 2. Related Work on Localization 16 via Extended Range and Redundant Association of Intermediate Nodes) employs is the Assumption Based Coordinates ( A B C ) algorithm. In this algorithm, a node establishes itself as the origin of the coordinates. The first node that sends its ranging estimate to this node is placed on the x-axis at the range estimate value. The second node's position in the coordinate system is explicit ly solved using the range estimates to the original two nodes and placed in the positive y-axis coordinates. Further nodes are then placed in the relative system from their range estimates to existing nodes. This function thus iter-atively places all nodes on a relative coordinate system. T E R R A I N , first uses the A B C algorithm only at the four anchor nodes in the system. Once sensor nodes receive the propagated distance measurements from the four anchors, the least-square lateration is performed to obtain in i t ia l position estimates. Then, a-refinement scheme called Iterative Local Triangulation is performed locally between every node and its immediate one-hop neighbors. Each node uses the neighbors' position estimates and range measurements to the neighbors to locally laterate its position. This procedure, after many iterations, should result in nodes positions remaining fixed. 2.2.2 APS In the A d Hoc Positioning System ( A P S ) developed by Niculescu and Na th [6], a similar approach to T E R R A I N is used without a refinement procedure. Thei r approach to the position problem uses an aspect of distance vector (DV) routing to propagate range estimates of the anchor positions to the nodes. In the D V - H o p case, once the network Chapter 2. Related Work on Localization 17 is deployed, the anchors broadcast their positions wi th a hop count value of one. Each one-hop neighbor of the anchor receives the packet, stores it in memory and creates a new packet wi th the anchor position and a hop count value of 2. It then forwards it to al l of its one-hop neighbors. Thus al l nodes should be able to obtain at least three anchors' positions and the hop counts to them. In the case where nodes obtain packets containing the same anchor but different hop counts, the lowest hop value is kept. When anchors receive information about other anchors, an average hop size is calculated, by computing the distance between the two anchors, and dividing it by the respective hop count. This average hop size is then propagated to the other nodes, so as to provide the nodes wi th range estimates to the anchors by mult iplying their hop counts by the average hop value for each anchor. A t this point, each sensor performs a lateration computation to localize itself using the positions of at least 3 anchors and the estimated distances to them. The DV-Dis tance algorithm is exactly the same as D V - H o p , but it is assumed that sensor nodes are capable to obtain range estimates to other nodes [6]. Thus, instead of forwarding hop count values, the sum of the distances originating from the anchors is propagated to al l nodes, providing range estimates directly as opposed to mul t ip lying hop counts by average hop distances. The third A P S scheme is the DV-Euc l idean which uses geometric quadrilateral properties to position nodes, one at a time. A s shown in Figure 2.4, if node A has range values to B and C, both of which have range values to an anchor L, as well as a range value between themselves, then A can directly compute the Euclidean distance to the anchor L, and hence position itself between two possible Chapter 2. Related Work on Localization 18 Figure 2.4: D V Euclidean model, [6]. locations A and A '. Considering relations between A and its other neighbors solves for this ambiguity. Comparison of the schemes showed that for anisotropic environments, DV-Euc l idean performed the best wi th errors of less than 50% of radio range, wi th 20% anchors and 10% range estimation error. The DV-Hop /Di s t ance schemes performed well at relatively low connectivity (7), and isotropic environments wi th error less than 30% of radio range, 20% range estimation error, 20% anchors. The main benefit of this scheme is its low signaling complexity. 2.2.3 Self-Positioning Algorithm In the self-positioning algorithm [20], a relative coordinate system is constructed, without the use of anchor nodes that traditionally use G P S positioning. Similar to the A B C algorithm employed in the T E R R A I N scheme, first every node identifies its one-hop neighbors and obtains distance estimates to them preferably by some time-of-arrival ( T O A ) techniques suggested by the authors: T O A techniques have been determined to Chapter 2. Related Work on Localization 19 be more accurate than received signal strength (RSS) techniques. Then, this information is sent to al l of the one-hop neighbors, essentially providing every node wi th information of up to a two-hop neighborhood. Each node then assumes itself as the center of the system, and sequentially places al l nodes it has information for, into its coordinate system, as in A B C . A t this point, al l nodes have placed their one and two-hop neighbors in Cartesian coordinates centered upon themselves. A s opposed to aligning al l coordinate systems to a single node's system that may require network wide updates if the node is moved, the alignment is performed relative to a group of nodes. A Locat ion Reference Group ( L R G ) of nodes are chosen, of which a coordinate system is developed as the main system to which al l network nodes must align to. This is used to enable the presence of mobile nodes in the system. However it comes at the cost of extensive communication and data exchange. 2.2.4 Ad-hoc Location System (AHLoS) This distributed algorithm [12] uses three functions to produce an accurate fine-grained approach to sensor node localization. These functions combine to produce absolute node positions important for noting origins of events, routing, group querying and network coverage. The design goals included the ability for the network to be deployed indoors or outdoors, decentralized and use maximum-likelihood estimation of node positions. The network consists of both anchor and regular sensor nodes. B o t h of which have additional hardware to use time-based range measurements as opposed to R S S . The first Chapter 2. Related Work on Localization 20 function, atomic multilateration, can be used for nodes that have 3 or more anchors as neighbors. These nodes obtain position estimates by lateration, essentially solving a system of linear equations. If there are more than 3 anchors, then the position solution is the linear least squares solution of the overdetermined set of equations. For nodes that do not have at least 3 anchor neighbors, the iterative multi lateration approach is used. In this approach, nodes that are unable to perform atomic multilateration wait unti l other nodes have obtained their positions. Thus, those nodes that are successful wi th atomic multilateration behave as anchor nodes. The remaining nodes then use the presence of traditional anchors with these newly positioned anchors to perform multilateration. This iterative scheme, wi l l thus gradually resolve the positions of the majority of nodes in the network. The drawback in this scheme is the potential error propagation by using approximated anchors in iteratively solving node positions. Lastly, collaborative multilateration is used in cases where unpositioned neighbor nodes cannot laterate estimates by themselves since not enough resolved neighboring nodes are present, but the combination of their relations to other nodes can be used to solve for each of their positions, as in Figure 2.5. Thus, these schemes, involve the use of information greater than one-hop away, and is useful when the percentage of anchors nodes is low locally. In Figure 2.5 node A and B cannot resolve positions since each only has two resolved neighbors, but combining their information a system of four equations and two unknowns is used to solve each node's position. Of course, some nodes may not be able to position Chapter 2. Related Work on Localization 21 E C D F Figure 2 .5: Collaborative Mult i la terat ion model, [12]. themselves at al l if they have less than three neighbors, as the position wi l l have ambi-guity, the algorithm includes a test of participating neighbors to identify if collaborative multilateration can be used or not [12]. The main drawback of this approach is the rel-atively high percentage of anchors needed in the system to provide sufficient accuracy. This requirement can only be avoided by increasing the node density in the network that wi l l increase the iterations required to localize. 2.2.5 N-Hop Multilateration Primitive In this scheme [21], the positioning problem is generalized as a collaborative multilatera-tion approach as introduced in [12]. Anchor nodes are either placed in the network area or are capable of automatically establishing a coordinates system for the other nodes. The algorithm consists of three phases. In the first phase, collaborative subtrees are con-structed and the unique solvability of each unknown node is determined. Collaborative subtrees are explicit combinations of anchors and nodes that yield an overdetermined or exact number of non-linear equations to solve for the positions of the unknown nodes [21]. In addition, before computing solutions to these equations, tests are performed to Chapter 2. Related Work on Localization 22 determine if each unknown node satisfies the conditions necessary for unique positioning. The search for the possible uniqueness of the node extends from one-hop to two-hops to n-hops, in order to identify enough equations to solve for the nodes as well. Thus, this phase is an extension of the previous algorithm's collaborative multilateration approach to n-hops. Nodes that do not satisfy the conditions do not proceed to the next phase. The conditions for this uniqueness are summarized in the following rules. 1. A unique solution exists if the node has three neighbors wi th uniquely possible solutions. 2. The neighbors must not be co-linear, since this would result in multiple solutions after lateration. 3. For two nodes using each other as constraints, each node must also have another neighbor to which the other node is not directly constrained. The second phase, obtaining ini t ia l position estimates, uses bounding boxes to set the extreme possible locations of the node. The bounding box is constructed by taking the strictest constraints on node positions by the reference neighbor nodes determined in the collaborative subtrees algorithm. This approach is used as opposed to direct lateration due to its computational simplicity. The position of the node is then determined as the center of the bounding box. Phase three then performs refinement using the K a l m a n filter that is the least squares equivalent in the static network case. Th is refinement is performed distributively using approximated methods that control the global solution Chapter 2. Related Work on Localization 23 of each subtrees in order to reach global min ima and obtain accurate positions. Af-ter this procedure, nodes previously excluded in phase one are solved for using atomic multilateration. The drawbacks of this scheme are the extensive computations in the re-finement scheme, and its rapid increase in error with increased network size, in addition to requiring greater than 20 percent of nodes to be anchors for sufficient performance [21]. 2.2.6 H o p - T E R R A I N with Refinement A n algorithm similar to that of A P S , and an extension to the T E R R A I N approach, Hop T E R R A I N wi th Refinement [22] is an amalgamation of both schemes. As the name suggests, two phases are present in the scheme, and ini t ia l start-up phase followed by a refinement step. The design of this system assumes a very low percentage of anchors, wi th at least four being required in the network. The other main goal is to avoid the inaccurate ranging errors typical of RSS based approaches in obtaining positions estimates. The result is the use of anchors propagating their positions to al l nodes, wi th receiving nodes noting the hop counts to the anchors and forwarding anchor positions to neighbors. W h e n an anchor receives information from another anchor, an average hop distance is calculated as in A P S . This average distance is propagated throughout the network as in A P S . The difference in this implementation, however, is that once a node receives information about average hop distance, it uses the information for al l hop measurements to the anchors it knows, not only for the anchor that sent the information. This reduces Chapter 2. Related Work on Localization 24 the information being sent throughout the network. After obtaining at least 3 distance estimates to anchors, nodes use lateration to compute the in i t ia l positions estimates. A s new information from other anchors not previously used or closer estimates to known anchors are received by the node, additional laterations are performed to obtain better in i t ia l estimates. After this ini t ia l startup phase, al l nodes wi l l have position estimates. The refinement procedure consists of nodes exchanging ini t ia l positions wi th neighbors and obtaining range estimates to neighbors through a ranging technique. Then nodes perform local least squares lateration to improve ini t ia l position estimates. In addition, all nodes contain confidence weights indicating the certainty of their position estimate [22]. Anchor nodes have weights of 1.0 while other nodes have weights equal to the average of the weights of the surrounding neighbors. Thus nodes closer to anchors have higher confidences in their positions than others. Lastly, nodes that have confidence levels less than 0.1 are regarded as unpositionable. Other constraints are used to make sure refined positions meet the in i t ia l communication constraints imposed by the anchors estimated distances, and hence have not diverged during refinement. In general, the refinement scheme improves the ini t ia l estimates by at least 3 times the error rates. For an anchor population of 20%, range error of 5%, connectivity of 7, the position error is 30% of the range [22]. A s range error increases, the improvement provided by refinement decreases linearly, and at 40% range error the improvement is non-existent. This scheme has proved to be more accurate in lower connectivities compared to other schemes, and achieves performance comparably at high connectivities wi th others. Chapter 2. Related Work on Localization 25 2.2.7 A P S / H o p - T E R R A I N / N - h o p Multilateration Primitive In the paper by Langendoen and Reijers [7], a comparison of three distributed schemes that have been deemed to be the most robust distributed schemes of the ones proposed to that point, are compared. The authors identify the key similarities in the schemes as the 3 phases being incorporated in each. Firs t , distances between nodes and anchors are obtained. Then, the in i t ia l estimates are computed. Lastly, a refinement is performed to achieve more accurate results. In the in i t ia l phase, three possibilities are available as proposed by A P S : D V - H o p , DV-distance and DV-Euc l idean . The second phase has two options, lateration previously used by A P S and H o p - T E R R A I N , and min-max the bounding box scheme used by the N-hop primitive. Refinement was used as the third phase. The results from the simulations of the different combinations of the three phases provided several conclusions. In the first phase, DV-distance always overestimated dis-tances to anchors, D V - H o p is immune to range error but does not perform well under irregular topologies, and lastly DV-Euc l idean rapidly decays as range errors increase. In the second phase, lateration is better than min-max for precise range measurements but more computationally intensive than min-max. In addition, min-max requires anchor nodes to be located at edges for better performance. The combinations of DV-distance and min-max performed comparatively to D V - H o p / L a t e r a t i o n both achieving accuracy less than 25% of range for 10% range errors, connectivity of 12, and 5% anchors [7]. However, in both cases the number of nodes localized drops by approximately half due to refinement divergence and nodes not uniquely localizable. A t low connectivities (less Chapter 2. Related Work on Localization 26 than 9) D V - H o p / L a t e r a t i o n is best, while medium connectivities (less than 15) D V -d i s t ance /Min-Max is superior. A t high connectivities DV-dis tance/Latera t ion performed well. DV-Euc l idean was only worthwhile at zero range measurement errors and connec-tivities larger than 14. The main drawback of this family of schemes is the percentage of nodes achieving accurate positions, since refinement results in almost half the network's nodes not achieving acceptable positions, at the cost of improving the accuracy of other nodes' positions by more than half. 2.3 Angle-Based Techniques A s opposed to range-based schemes, angle-based schemes provide several advantages. These advantages depend on the type of angle or bearing techniques used. For example, whereas lateration using three anchors is needed for range-based techniques, two anchors are needed for angulation' using bearing information. If angles between anchors can be determined instead, then three anchors are sufficient in triangulation, the counterpart of trilateration. Though range-based techniques have been extensively proposed, several algorithms using some angle measurements have been proposed. 2.3.1 APS using AOA The extension of the A P S scheme to involve the use of angle-of-arrival ( A O A ) measure-ments at the nodes has been implemented in [8]. A l l sensor nodes are assumed to have additional hardware capable of determining the A O A of signals from other nodes. These Chapter 2. Related Work on Localization 27 Figure 2.6: Nodes obtaining relative angle measurements to other nodes, [8]. nodes can determine the direction of the signal relative to their own reference direction known as their heading. If these headings are absolute directions relative to the Nor th direction, and hence behave as compasses for the nodes, the localization is even easier, as shown in Figure 2.6. The hardware to achieve this A O A capability arises from the use of antenna arrays at each node and computations relating to signal strength at the antennas of the array and received signal time difference between the antennas. If a node can obtain a bearing to three anchors, then it can triangulate its positions using the angles between the anchors and the anchor positions as in Figure 2.7. The mathematical solution of triangulation is transformed into a trilateration problem and solved using the least-squares algorithm. If nodes' headings are relative to North , then only two measurements are needed, each providing the equation of a line and the intersection determining the position of the node. Chapter 2. Related Work on Localization 28 B O W c(* c Jy c) Figure 2.7: Local izat ion using Angulations, [8]. The two schemes proposed are DV-Bear ing and D V - R a d i a l [8]. Whereas bearing refers to the direction of a node from the originating node's point of view, the radial is the reverse bearing (from the other node's point of view). Th is distinction is made when the headings of the nodes are not absolute (i.e. relative to North) . If they were absolute, then the information would be redundant. The D V - R a d i a l case uses more communication as two packets of information are exchanged, but the resulting computations are less. In both schemes, nodes with anchor neighbors obtain bearings or radials to the anchors, them. This information is propagated to other nodes, which are then able to obtain bearings/radials to the anchors as well. However, in order for a two-hop neighbor to obtain its bearing to an anchor, it must have two neighbors that have bearings to the same anchor. Final ly, once nodes have bearings/radials to three anchors, they can compute their positions. The increased need of neighbors wi th measurements to the same anchor, increases the node connectivity to 9 or greater for A O A to produce sufficient results. The errors present in this system are inherent in the degree of accuracy in small angles as opposed to large ones. Of the two schemes, D V - R a d i a l is less dependent on percentage of Chapter 2. Related Work on Localization 29 Figure 2.8: DV-pos i t ion model, [23]. anchors needed, and obtains better accuracy than DV-Bea r ing . However, the accuracy is comparable to the radio range between nodes, not as precise as most range-based schemes. 2.3.2 DV-position Another scheme proposed by Niculescu and Na th includes both range and A O A mea-surements, and allows nodes to position themselves in one step if anchors have headings relative to Nor th [23]. A s shown in Figure 2.8, if node A has the bearing to anchor B and the anchor knows its bearing to node A , as well as its heading from North , then the equation of the line connecting A and B can be computed. In addition, range information between A and B wi l l select one point on the line, corresponding to node A ' s position. This is an example of mult imodal sensing, that combines two techniques of measure-ment to provide less requirement in terms of cooperation wi th other nodes, at the cost of additional sensor hardware. This scheme is optimal at anchor percentage of 10%, node Chapter 2. Related Work on Localization 30 F i g u r e 2.9: Local izat ion using synchronized, offset, rotating beacon signals, [24]. connectivity higher than 6 , wi th error rates less than 40% radio range. However, this is not practical due to the size restrictions imposed by sensor nodes and the hardware requirements needed by the nodes. Also , A O A measurements have been scrutinized over possible complications over reflections from objects, thus introducing considerable error into the system. 2.3.3 Directionality Localization The directionality localization algorithm [24] employs the use of at least three fixed high-powered directional anchors placed at the corners of a sensor network. It is assumed that al l nodes in the network can receive signals from every anchor when the direction of transmission of the anchor is towards the sensor node. In addition, the anchors are synchronized to be rotating their directional beacon signals 360 degrees at the same constant speed but with a fixed angle offset from each other, as shown in Figure 2.9. Chapter 2. Related Work on Localization 31 Nodes must be able to distinguish between the beacons received from the different anchors. The algorithm begins with each sensor node noting the times at which it receives each signal from the specific anchors. The time differences between the received signals can be translated to the angles between the anchors, given that the nodes know the offset and speed at which the anchors are rotating the signals, which is predetermined to sensor network deployment. Then the location of the node can be determined using two of the angles and the positions of the anchors using trigonometry. Simplist ic in nature, the complexity in the anchors is offset by the simplici ty of sensor nodes not requiring any special hardware. However, this scheme is not ad-hoc, though it is distributed and suffers from the possibility of mult ipath reflections, no line of sight between all nodes and anchors, and the precision (width) of the directional beam. 2.3.4 Ad-Hoc Ranging and Sectoring Another scheme that promotes the use of mult imodal sensing in order to solve the node-positioning problem is proposed by Chintalapudi et al. [9]. The authors proposed this scheme by pointing out that range-based schemes by themselves require much higher connectivities than needed in general for the sensor network to perform its actual sensing function. From the schemes presented in section 2.2, one can see that position errors less than half the radio range typically require connectivities greater than 9. Chintalapudi et al. state it is unacceptable to deploy so many extra nodes just to obtain the nodes' positions. They aim to reduce the connectivity required as well as keeping the percentage Chapter 2. Related Work on Localization 32 of special nodes (anchors) at a minimum. B y using range and sectoring this requirement can be alleviated, to needing only one neighbor that has positioned itself, as explained in DV-pos i t ion . Thus the scheme proposed is similar to iterative multilateration, but in this case neighbors to anchors position themselves first followed by other neighbors. To combat error propagation, refinement schemes are proposed such as least-mean-squares. The results show that for sectors as large as 60 degrees, wi th node connectivity of 5 and 20% anchors, more than 90% of network nodes are localized wi th 6% localization error [9]. These results are the most accurate of al l ad-hoc systems, though the physical feasibility of such a system is questioned. In addition, a large number of iterations are required to achieve these results during the refinement procedure, requiring a high computational capacity for such sensor nodes. 2.4 Range-Free Techniques Range-free approaches assume that no specialized angle or range-determining hardware is necessary for the sensor nodes. 2.4.1 Centroid Bulusu et al, proposed a simple, cost effective, RF-based positioning method called Cen-troid in [11]. B y design, the technique is classified as coarse grained since it computes localization using proximity methods and simple averaging to compute the centroid loca-tion. Fine-grained localization, in contrast, uses measurements or fixed ranges obtained Chapter 2. Related Work on Localization 33 from the sensor node to compute position estimates. In this technique, anchors are placed in a coverage area in a symmetric grid pattern. The transmission range by the anchors is assumed to be greater than those by normal sensor nodes, similar to the A P I T [10] algorithm. The coverage areas by each beacon overlap, providing sensors wi th the abili ty to hear several beacons from different anchors at any location in the coverage area. The anchors are synchronized to transmit one beacon during a specified time slot of a period T of system operation. Thus, the period depends on the number of anchors deployed. Sensor nodes determine their connectivity by listening to beacons for several consecutive time periods. A n anchor is determined to be wi th in range, if the node receives more than a threshold number of beacons during the listening period from the anchor. The position of the node is then calculated as the average of the coordinates of each anchor wi th in range, and hence is noted as the centroid or center of the anchors' positions. The scheme enables sensors to operate with minimum power consumption as no communica-tion is needed wi th other nodes, and very little computation is required. However, the density of the anchors in the coverage area determines the accuracy of the scheme. In addition, the deployment of anchors in an ad-hoc manner, severely affects the positioning accuracy as well. The synchronization of the anchors may be unreasonable for large-scale deployments. Chapter 2. Related Work on Localization 34 0 0 U 0 0 0 0 0 o 0 0 0 l i p pr 0 ,0 0 131 •2J §31 •21 •21 |R | flf 0 0 0 0 *1 -1 „„„l,^ .„ 0 0 0 0 HI E l 0 -V; v - l 0 0 0 121 -h -1 0 ,0 0 0 0 0 0 -r— - i : . i 0 0 0 0 0 0 0 0 0 0 Figure 2.10: Loca l grid maintaining overlapped triangle regions for localization, [10]. 2 . 4 . 2 A p p r o x i m a t e d P o i n t - i n - T r i a n g u l a t i o n ( A P I T ) A P I T [10] is range-free and does not require any additional hardware for sensor nodes. The design goals included performing under irregular radio patterns and having low communication overhead. The scheme assumes the availability of high powered anchors that are able to transmit much greater distances than normal sensor nodes. The main algorithm employs a unique test for localization, the Point-in-Triangulation (PIT) com-parison [10]. Each node is assumed to be able to hear many anchors (much greater than 3) and the connectivity is assumed to be higher than 6. The P I T comparison tests if a node is located wi th in each triangle formed by combinations of 3 anchors heard. A grid is maintained wi th positions in the grid satisfying the P I T test being incremented while those outside being decremented, as shown in Figure 2.10. After considering all combinations of anchors heard, the grid points with the highest values determine the position of the node. A node is located wi th in a triangle of anchors Chapter 2. Related Work on Localization 35 Figure 2 . 1 1 : A P I T test using node neighbors, [10]. if there is no neighboring position where it can be moved, that is not simultaneously closer or farther from all three anchors. This movement is avoided by just considering the position of the node's neighbors as the new position of the node and by comparing if they are closer or farther from all anchors at the same time. This is the Approximated P I T ( A P I T ) test as shown in Figure 2.11, which does have several degenerate cases that only account for 14% of the deployments actually being affected by the error. Though distance measurements are not used, each node in a table maintains the received signal levels of the anchors. Each node maintains its table and exchanges it wi th the neighbors so that al l nodes have information of the one-hop neighborhood. Then A P I T looks at a column to determine if al l the nodes wi th the same three anchors lie wi th in the triangle, (i.e. the signal levels at al l three anchors are not simultaneously greater or smaller than the nodes' levels). A l l combinations of anchors are examined and then the grid array is constructed with 0.10 radio range blocks. The position is then determined to be the center of the highest valued points area. The required reduction in anchor percentages is inversely proportional to the anchor to node range ratio ( A N R ) . Chapter 2. Related Work on Localization 36 The scheme achieves errors of 40% range, for node density of 8, anchors heard of 16 and A N R of 10 [10]. A l l of this comes at moderate communication cost and robust performance to irregular radio patterns and anchor positioning error. The work in [25] considered the possibility of quantized received signal strength (RSS) and presented mathematical analysis of the accuracy wi th varying levels of quantization. The performance comparisons between R O C R S S I and A P I T schemes are given in [26]. 2.5 Other Novel Techniques Other schemes exist that cannot be classified solely as one of the type of schemes men-tioned earlier. These localization algorithms provide unique ways of obtaining node positions and assume quite different network characteristics than previously mentioned schemes. 2.5.1 Time-based Positioning Scheme TPS A fixed anchor deployment scheme proposed by Cheng et al. is the Time-based Posi-tioning Scheme (TPS) [27]. In this scheme no time-synchronization is required between anchors. The anchors are deployed outside of the coverage area, enclosing the area in a triangular geometry, as shown in Figure 2.12. The anchors' transmission range is large enough to cover the entire area, hence any node wi thin the coverage area wi l l be able to hear al l three beacons from the anchors. Firs t , anchor A sends a beacon to the area. When anchor B hears the beacon, it sends Chapter 2. Related Work on Localization 37 Figure 2.12: T P S coverage model, [27]. its own beacon containing the information of the time between receiving A ' s beacon and sending its own beacon. Then anchor C also hears A ' s beacon and sends its own beacon containing similar information like B , but using C's reception and broadcast time difference. A l l three of these beacons are received by the nodes in the area, and the nodes wi l l maintain local time information of when the packets from the anchors are received. This constitutes one beaconing period for the system. This information is enough for nodes to triangulate their position based on geometric equations relating to the time differences between beacons and reception by the nodes. The accuracy of the position depends on the accuracy of the t iming measurements, and can be improved merely by nodes averaging their results over several beaconing intervals. Errors presented in the system include system delay in reception and transmission of beacons, non line-of-sight transmission and mult ipath fading. In addition, if a node is much closer to one anchor than the other two, significant error is present as well as the case where the node is Chapter 2. Related Work on Localization 38 much farther to al l three anchors [27]. Similar to Centroid, the nodes are able to position themselves without communication to other sensors, but more computations are required compared to Centroid. Th is is compensated by the lack of synchronization required by the anchors and nodes, since only time-difference of arrivals ( T D O A ) are used to compute distance estimates to anchors and the following trilateration. Thus, this is a fine-grained scheme as distance measurements are used as well as the anchor positions. The increased transmission ranges required by anchors may be troublesome for large-scale deployment and may require more anchors and coordination among subtriangular regions. 2.5.2 Secure Positioning A different area not previously considered in the node localization problem, is the secu-rity of the network and its communications, in the event of it being deployed in a hostile environment as suggested in many papers. In [28], several methods of obtaining sensor locations in a secure manner are employed. The threats inherent in a sensor network include the removal of sensors, manipulation of sensors and the compromise of the sys-tem. In order to counteract these issues, the anchors are assumed to be tamper resistant and physically immovable. A central authority where a l l network data is sent to is also assumed to be secure. In addition, the central system is able to maintain the location of all unique sensors in the system. Two notions considered are the introduction of mali-cious and compromised nodes in the system. Malicious nodes are controlled by attackers, but the central authority is aware of the malicious nodes. Compromised nodes, however, Chapter 2. Related Work on Localization 39 • Sensor • A n c h o r Figure 2.13: Sensor coverage model, [28]. are controlled by the attackers and are thought to be normal nodes by the system. The attacks considered to be possible include: displacement of a node, introduction of a worm-hole, malicious distance enlargements and dissemination of false position information. In order to prevent such instances from affecting a sensor network, the secure methods are meant to be used in conjunction with node localization algorithms previously proposed in the literature. In the authenticated distance estimation method, nodes communicate using cryptographic keys in order to obtain distance estimates to each other. Another method, authenticated distance bounding, enables each node to obtain distance bounds to other nodes independently. These methods are used to obtain verifiable trilateration for position estimates of nodes and verifiable T D O A for trilateration. These methods are employed in the sensor system using anchors deployed in a grid-like fashion consisting of triangles, as shown in Figure 2.13. Sensor nodes obtain position estimates by the methods previously mentioned. Since anchors are tamper proof, they wi l l be able to obtain true distances to al l nodes enclosed in their coverage triangle and Chapter 2. Related Work on Localization 40 thus provide true positions of nodes through authenticated communications, and therefore verify the locations claimed by the nodes. In the distributed sensor network, the use of Basic Distance Verification ( B D V ) w i l l also provide for reliable positions of nodes. The algorithm determines the position of a node by observing its placement wi th in a series of triangles enclosed by other nodes. However, in the case where more than one node is malicious or compromised, the system is subject to unreliable information. Results show that in order for a network to be more robust in terms of security, the node connectivity (density) must be higher than required for localization. In addition, the security of the system increases the communication and computations required by each node to perform localization. . . . 2.5.3 Anchor-Free Localization (AFL) The Anchor-Free Localizat ion ( A F L ) scheme is another distributed algorithm for sensor networks [29], which omits the use of specialized anchor nodes always required by other schemes. The algorithm, implemented without the use of anchors results in the network discovering its topology and connectivity, and hence relative node coordinates to one another. If absolute coordinates are required, three anchors can be used to translate or orientate the A F L ' s relative coordinates to achieve this. Th is scheme has two phases: fold-free embedding, and mass-spring optimization [29]. The objective of the first phase is to produce a map of the network that looks similar to the actual network topology. This approach is emphasized as important in order for the second phase to reach a glob-Chapter 2. Related Work on Localization 41 not r ig id r ig id globally r ig id Figure 2.14: Different configuration wi th degrees of freedom, [29]. ally opt imum solution that matches the actual topology. Previous methods of building local coordinate systems and aligning them, sometimes fall into obtaining local min ima solutions and result in topologies that match distances between nodes but fail to produce topologies matching the actual case. The authors identify this as graphs that are not globally rigid, meaning that given observed distance measurements between connected nodes, several different topologies are possible to satisfy the given constraints, as shown in Figure 2.14. The first phase of the scheme builds a reference coordinate system randomly, paying special attention to form a globally rigid system. A node is picked randomly as the starting point from which four extrema of the system are identified and the center node of the reference system is determined. Then all other nodes use estimated distances to these 5 points (excluding starting node), to'place them in the coordinate system using polar coordinates in Figure 2.15. The resulting embedding is usually larger than the actual topology, which aids in the avoidance of local minima. The second phase consists of nodes broadcasting their Chapter 2. Related Work on Localization 42 ri3 Figure 2.15: Topology construction for fold-freedom, [29]. estimated positions to neighbors, and calculating estimated distances to neighbors using the aforementioned data. Comparing estimated distances wi th actual measured distances, the second phase optimizes the estimates of the first phase iteratively by estimating node positions that reduce the overall network error, unti l a solution is reached analogous to a mass-spring system [17]. The robustness of the scheme, lies in the fact that even at low connectivities A F L is successful in obtaining a coordinate system, whereas other incremental schemes fail. 2.5.4 Sequential Monte Carlo Localization (MCL) In contrast to most schemes presented, H u and Evans proposed a localization scheme for mobile sensor networks [30], in which al l nodes are mobile. Thei r approach is based on the assumptions that no distance measurements can be made by nodes, anchor densities are low and nodes are deployed in an ad-hoc manner. The algorithm itself is based Chapter 2. Related Work on Localization 43 on the sequential monte carlo or particle filter technique, a statistical approach to the mobile node-positioning problem. In this technique, there are two steps, the prediction and filtering stage. The position of a node is maintained by a set of samples of the posterior distribution of the possible location of the node. In the first step, a prediction of the possible location of the node is made using the transition distribution probability and previous set of samples. The second step, involves the node using new information gathered after movement to eliminate previous prediction that do not correspond wi th the new data. To counteract the reduction of valid samples, resampling is performed to maintain a discrete number of samples for the posterior distr ibution of node location. The restrictions imposed in the first step, is due to the speed of the node, assuming constant speed v, the location of a node given a ini t ia l starting point wi l l be wi th in a circle of radius v*t, where t is the time from ini t ia l start [30]. Thus, the location is randomly picked wi th uniform distribution wi thin the circle. Nodes, using information of which anchors were within range in the previous time, and which anchors are now within range after movement, w i l l refine the samples generated from before. In addition, nodes share wi th neighbors, the anchors that are wi th in communication range, to provide further identification data. From the results, assuming a random walk node movement model, estimated errors as good as 50% of radio range are achieved for node density of 10, and anchor ratio of 10% [30]. A s more samples are kept, the greater the accuracy of the scheme and surprisingly, the faster the anchors and nodes move, the faster the algorithm converges in obtaining accurate position estimates. The last result is due to the fact that Chapter 2. Related Work on Localization 44 faster speed result in much more information on which anchors are wi th in communication range of which nodes at certain times, resulting in more information being available to filter bad position samples. Several schemes have explored the use of mobile anchors and nodes. In [31], a single mobile anchor traverses the network and allows stationary sensor nodes to compute their location estimates based on at least three neighboring nodes' locations. Mul t ip le mobile anchors are used in [32]. In [30], both anchors and sensor nodes are mobile. The Monte Carlo algorithm is used for localization. In [33], an extended K a l m a n filter (EKF)-based state estimator is used in tandem with mobile robots for localization. 45 Chapter 3 Ordinal Multidimensional Scaling In this chapter, we propose the implementation of ordinal MDS for localization in wireless sensor networks. We first state the motivations and assumptions. It is followed by the description of our M D S - M A P ( P , O) localization algorithm. We then present the simulation results for the performance comparisons between M D S - M A P ( P , O) and M D S -M A P ( P , C) [2]'. 3.1 Motivations and Assumptions The advantage of M D S localization algorithms is the relative low percentage of estima-tion error while using a small number of anchor nodes. The classical (or metric) M D S algorithm assumes that there exists a linear transformation which relates the shortest path distance and the Euclidean distance between each pair of nodes. For each pair of nodes (i, j), if the shortest path distance is denoted by p^- and the Euclidean distance is denoted by dy, then dij = mpij + c for some constants m and c. Classical M D S uses singular value decomposition [34] to determine the relative coordinates of the sensor nodes. Chapter 3. Ordinal Multidimensional Scaling 46 A s mentioned in Chapter 2, previously proposed localization algorithms based on classical Multidimensional Scaling ( M D S ) [1] [2] [13] have proven to be robust wi th respect to both hop-based and range-based implementations. Only three or four anchor nodes are necessary to determine the absolute locations, in two or three dimensions, respectively. These M D S algorithms achieve a higher accuracy than some other schemes. B y using the similar terminology in [1], the term M D S - M A P ( C ) is used for the classical M D S localization algorithm. The original M D S - M A P ( C ) is a centralized algorithm. In [2], a distributed M D S algorithm called M D S - M A P ( P , C) was proposed where P denotes the use of patching of local maps and C denotes the use of classical M D S . A s mentioned in the previous papers, further work is required to study the application of other M D S techniques (e.g., probabilistic M D S , ordinal M D S ) on localization in sensor networks. Our proposed scheme in this chapter is called M D S - M A P ( P , 0 ) where P again denotes the use of patching of local maps and O denotes the use of ordinal M D S . M D S - M A P ( P , 0 ) is also a distributed algorithm. The main difference between classical M D S and ordinal M D S is that the former as-sumes there is a linear equation which relates the shortest path distance and the Euclidean distance between each pair of nodes, the latter simply assumes a monotonicity constraint. That is, for ordinal M D S , given two pairs of nodes (i, j) and (k, I), if the shortest path distance of (i, j) is greater than that of (k, I), then the Euclidean distance of (i, j) is also greater than that of (k, I), and vice versa. Chapter 3. Ordinal Multidimensional Scaling 47 3.2 MDS-MAP(P, O) Algorithm The major steps of the M D S - M A P ( P , 0 ) algorithm are as follows: 1. Each node first gathers either the distance (for range-based) or hop count (for hop-based) information wi th in its two-hop neighborhood. 2. In each node, the Dijkstra's algorithm is invoked to determine the shortest path between each pair of nodes wi th in the two-hop neighborhood. We use the notation Pij to denote the shortest path distance between nodes i and j. 3. The ordinal MDS algorithm is applied to create the relative local map for each node. 4. Each local map is refined by using the least-squares minimizat ion between the calculated Euclidean distance and the measured distance (or hop) between each pair of neighboring nodes. 5. The local maps are then patched (or merged) into a global map by using a prede-termined ini t ia l starting node's local map and sequentially adding each neighbor that has the largest number of common nodes to the starting node. This map then grows unt i l al l nodes have been included. 6. The global absolute map is created by using the anchors' positions and the global relative map. Chapter 3. Ordinal Multidimensional Scaling 48 Assume that the average number of sensor nodes in each two-hop neighborhood is M, the average number of neighbors is K, the total number of sensor nodes is N, and total number of anchors is A. In the above M D S - M A P ( P , 0 ) algorithm, steps (2) and (4) have a complexity of 0 ( M 3 ) . Step (3) has a complexity of 0 ( M 4 ) . Steps (5) and (6) have a complexity of 0(K N) and 0(A3 + N), respectively. The ordinal MDS algorithm (step (3) above) is now describe in detail. The major steps of the ordinal MDS algorithm are as follows [35]: 1. Assign arbitrary ini t ia l location estimation (x° , y°) for i 6 M, where M includes all the nodes wi th in the two-hop neighborhood. Specify e > 0 and set n = 0. 2. For each i,j £ M, compute the Euclidean distance by d% = ^ ? - ^ ) 2 + ( y ? - y j ) 2 (3.1) 3. B y using the matrices [p^] and [d™], apply monotone regression by using the pool-adjacent violators (PAV) algorithm [35] to determine [d^]. For example, once the Py ' s are ordered from the least to the highest, if (p^- < pki) and (a!™- > d^), then Otherwise, d™- = cP- and — d^. If there are consecutive violators, they are al l Chapter 3. Ordinal 'Multidimensional Scaling 49 grouped and averaged together, as per the P A V algorithm, to maintain monotonic-ity throughout the entire set. 4. Increment n by 1. For i 6 M, compute the new relative coordinate for node % by 1 1 jeMjjti \ y where | M | denotes the number of sensor nodes wi th in the two-hop neighborhood. 5. For each i,j 6 M, update the Euclidean distance by using equation (1). 6. Use Kruskal 's Stressl test to determine the goodness of fit [36] [37]: Stressl h i < j [ l J l J ' (3.2) 2 13) 7. If Stressl < e, stop. Otherwise, go to Step (3). In the above algorithm, the first two steps calculate the Euclidean distance from an arbitrary ini t ia l configuration. Step (3) determines the disparities d?- by constructing a monotone regression relationship [38] between p^-'s and cP 's . Step (4) updates the Chapter 3. Ordinal Multidimensional Scaling 50 relative positions. The parameter a is the step width . We use a = 0.2 as suggested by Kruska l [39]. Step (5) updates the Euclidean distance. The Stressl measure in step (6) determines whether or not the updated values fit the given dissimilarities a™'1. Note that other goodness fit tests (e.g., Kruskal 's Stress2, normalized raw stress, S-Stress) can also be used; however we choose the Stressl measure since it is the most common measure used for ordinal M D S . Step (7) determines if the derived configuration's goodness fits are close enough such that the procedure can be terminated. The M D S - M A P ( P , 0 ) algorithm assumes that there is a monotonic relationship be-tween the shortest path distances and the actual Euclidean distances. Th is assumption may not be valid if the network being considered is sparse and large. However, most of the applications in wireless sensor networks require the networks to be dense (i.e., wi th a high connectivity or average node degree) in order to provide redundancy and robust-ness in case of a node's failure. In addition, in our distributed approach, only the nodes wi th in the 2-hop neighborhood are being considered. In this case, the assumption of the monotonic relationship between the shortest path distances and the actual Euclidean distances is valid. B y the iterative nature of the ordinal M D S algorithm in minimizing stress in equation (3.2), the final solution may not guarantee to be the global min imum [40]. In fact, the ordinal M D S algorithm can have several local minima. However, the use of the anchors in our application of the ordinal M D S algorithm increases the likelihood of reaching the global minimum. This is due to the imposed transformation required to obtain the Chapter 3. Ordinal Multidimensional Scaling 51 absolute coordinates for al l of the nodes. Another way to further increase the chance of reaching the global min imum is by using the multiple starting configurations approach and retaining the configuration which results in the lowest stress value. However, this approach is inefficient due to the additional computation effort required. 3.3 Performance Evaluation and Comparison To implement M D S - M A P ( P , O) algorithm, the source codes for M D S - M A P ( P , C) that were written in Mat lab by [2] were modified to implement ordinal MDS. Two different topologies are considered as the sensor network's coverage area. The first one is a uni-formly distributed square region. The second is an irregular C-shaped topology. In both topologies, the average connectivity levels (i.e., average number of neighboring sensors) are varied along wi th the number of anchors in the area. The average connectivity level is varied between 9 and 21 by modifying the radio range R, wi th in the fixed coverage area. In each set of simulation run, 50 trials were performed and 95% confidence intervals were plotted. It is envisioned that there is a large number of sensors wi th in a square coverage area to increase the robustness of the sensor network. In the simulations, either 160 or 200 sensor nodes were used. The number of anchors is between four and ten. Al though in theory only three anchors are necessary to obtain the absolute position estimates for M D S - M A P ( P , O) , the location of the anchors in this minimal case has a significant impact on the estimation error. Thus, it is recommended that a min imum of four anchors be Chapter 3. Ordinal Multidimensional Scaling 52 used for deployment. In the hop-based scenarios, hop count is used as the distance metric between a pair of nodes. For each node to have a unique position in M D S - M A P ( P , O) , the hop count values are blurred wi th noise so that nodes wi th identical hop count values to neighbors are not co-located. In the range-based scenarios, the range is modelled as the actual distance combined wi th Gaussian noise. Thus, the range is a random value drawn from a normal distr ibution with actual distance as mean and variance of 5%. The amount of Gaussian error is also varied and its effect on the average positioning error is studied. In the ordinal M D S algorithm, e is set to be 10~ 4 . 3.3.1 Random Uniform Network Topology For evaluation of the random uniform deployment, a l O r b y lOr square topology was used, where r represents the reference unit length. Anchor nodes are placed randomly wi thin the coverage area, and have the same communication range (i.e., radio range denoted by R) as other nodes. Hop-Based Performance In Figure 3.1, the topologies estimated by hop-based M D S - M A P ( P , C) and M D S - M A P ( P , O) are shown. The hollow circles represent the actual positions. The lines indicate the amount of error of the estimated positions. The filled circles represent the location of Chapter 3. Ordinal Multidimensional Scaling 53 (a) M D S - M A P ( P . C ) , ( e r r o r = 0 . 4 7 R ) ( b ) M D S - M A P ( P . O ) , ( e r r o r = Q . 4 2 R ) 0 2 4 6 8 1 0 0 2 4 6 8 1 0 Figure 3.1: Topology results of hop-based (a) M D S - M A P ( P , C) and (b) M D S - M A P ( P , 0 ) in a 10T X lOr square network region employing uniform random place-ment of 200 nodes wi th connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. Est imat ion error is represented by lines. the 4 anchors. The position estimation errors by M D S - M A P ( P , C) and M D S - M A P ( P , O) are 47% and 42% of the radio range, respectively. Figure 3.1 shows that the estimation error encountered by each sensor node is different. Most of them have small estimation error while a few of them may have higher estimation error. The ordinal M D S algorithm reduces the amount of estimation error for the nodes which would have a higher estimation error if classical M D S were used. This can be attributed to the fact that the ordinal algorithm iteratively improves the in i t ia l random topology estimate thereby improving the goodness fit of the ordered distances wi th in the 2-hop neighborhood of each node. In other words, the larger error encountered by classical M D S is due to the inaccurate modeling of the shortest path distances being equal to the actual distances between nodes, which may not always be the case. The Chapter 3. Ordinal Multidimensional Scaling 54 (a) 4 anchors (b) 6 anchors "8 50 en 4 0 o t LU S 30 — — — M D S - M A P ( P . C ) M D S - M A P ( P . O ) 10 15 20 Node Connectivity (c) 8 anchors — — — M D S - M A P ( P . C ) . * M D S - M A P ( P , 0 ) k 10 15 20 Node Connectivity 60 ~ 40 50 — — — M D S - M A P ( P . C ) w M D S - M A P ( P . O ) 10 15 20 Node Connectivity (d) 10 anchors M D S - M A P ( P . C ) M D S - M A P ( P . O ) 10 15 20 Node Connectivity Figure 3.2: Performance of hop-based M D S - M A P ( P , C) and M D S - M A P ( P , 0 ) in a lOr x lOr square network region employing uniform random placement of 200 nodes, for varying levels of connectivity and anchors deployed. monotonic constraint in ordinal M D S provides accurate iterative minimizat ion of stress and hence lower position errors for most nodes, especially nodes with large estimation errors. Figure 3.2 shows the position estimation errors as a function of the average con-nectivity level by hop-based M D S - M A P ( P , C) and M D S - M A P ( P , 0 ) , respectively, wi th different numbers of anchors deployed. Results show that M D S - M A P ( P , 0 ) outperforms M D S - M A P ( P , C) by a 5% lower position estimation error for a connectivity of 12 and four anchors deployed. The performance improvement confirms the conjecture that in sensors' localization problem, the use of the monotonic constraints in ordinal M D S is Chapter 3. Ordinal Multidimensional Scaling 55 more appropriate than the use of linear constraints in classical M D S . The estimated node positions wi th error less than 40% of the radio range have been proven to suit the applications of sensor networks [10]. When the number of anchors is greater than 3 and the connectivity level is greater than 12, the position estimation error is always less than 40% of the radio range (our target value). A s the average connectivity level increases, the confidence intervals reduce in size. This shows that dense networks can provide more consistent average error values. Th is is due to the fact that dense networks have smaller two-hop regions, which in turn lead to more accurate shortest path distances. These distances therefore improve the classical M D S results as well as the ordinal M D S results, since more accurate distances translate into more accurate proximities in the ordinal case. Range-Based Performance Figure 3.3 shows the topologies estimated by range-based M D S - M A P ( P , C) and M D S -M A P ( P , 0 ) , respectively. The position estimation errors by M D S - M A P ( P , C) and M D S -M A P ( P , O) are 16% and 13% of the radio range, respectively. Figure 3.4 shows the position estimation errors as a function of the average connec-t ivi ty level by range-based M D S - M A P ( P , C ) and M D S - M A P ( P , O) , respectively. A s the number of anchors deployed increases the additional gain in accuracy is minimal above 6 anchors. Results show that M D S - M A P ( P , O) outperforms M D S - M A P ( P , C) by a 2% lower position estimation error. We notice that the improvement in the range-based Chapter 3. Ordinal Multidimensional Scaling 56 ( a ) M D S - M A P ( P . C ) , ( e r r o r = 0 . 1 6 R ) o g o o O O S , O 0 0 o o © 0 o ^ 0 3 o 0 « o 0 o ° o _ oc£> cb* * 0 % 0 0 o o 0 CB) o o o <S> © es o o © o o 3 > o o o 0 o & o © o ° o © o © o 0 ° - . - o © O W S o o © ° o o ° o ' o < o o o o o O o o o © o ( b ) M D S - M A P ( P . O ) , ( e r r o f = 0 . 1 3 R ) Figure 3.3: Topology results of range-based (a) M D S - M A P ( P , C) and (b) M D S - M A P ( P , O) in a lOr x lOr square network region employing uniform random place-ment of 200 nodes wi th connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. Est imat ion error is represented by lines. case is only slightly better compared with the hop-based case. However, it is clear that the range-based case outperforms the hop-based scheme by a significant margin which is desirable in order for the tradeoff of additional ranging hardware to be accepted. Results show that in the range-based case, the position estimation error is more sensitive to the average connectivity level than to the number of anchors. Again , if the target position estimation error is less than 40%, our proposed M D S - M A P ( P , O) can achieve this value when the average node connectivity level is above 9. B y comparing Figures 3.2 and 3.4, it shows that the range-based scheme outperforms the hop-based scheme in M D S - M A P ( P , 0 ) . This is due to the fact that more accurate distance measurement information is available in the range-based scheme. B y just using the connectivity information (i.e., hop-count), the hop-based scheme wi l l have some nodes Chapter 3. Ordinal Multidimensional Scaling 57 (a) 4 anchors (b) 6 anchors cc o 30 en & 20 o UJ = 10 o en o Q - 0 o 30 TD to Ol s i 20 o UJ = 10 O T7> O a- 0 — — M D S - M A P ( P . C ) M D S - M A P ( P . Q ) 10 15 20 Node Connectivity (c) 8 anchors - M D S - M A P ( P , C ) *t M D S - M A P ( P . O ) 10 15 20 Node Connectivity 25 o 30 T 3 TO S. 20 _ 111 •= 10 .o m o cu 0 cc o 30 20 10 0 — — M D S - M A P ( P . C ) l v l D S - M A P ( P , 0 ) 10 15 20 Node Connectivity (d) 10 anchors • — — — M D S - M A P ( P . C ) x M D S - M A P ( P . O ) 10 15 20 Node Connectivity Figure 3.4: Performance of range-based M D S - M A P ( P , C) and M D S - M A P ( P , 0) in a lOr x lOr square network region employing uniform random placement of 200 nodes, for varying levels of connectivity and anchors deployed. having the same distance measurement when in fact their actual Euclidean distances may differ. This directly affects the ordinal scheme when it comes to applying the monotonic constraint and iterative stress reduction. Sensitivity Analysis of Range Error on Positioning Error In this section, the effect on the position estimation error when the distance between two neighboring nodes is not determined accurately is studied in the range-based scheme. A s mentioned earlier, a Gaussian noise model is used to model the estimated range distances between two nodes. The actual distance is taken as the mean value. The value of the Chapter 3. Ordinal Multidimensional Scaling 58 2 0 2 5 3 0 R a n g e E r r o r ( % ) Figure 3.5: Effects of node ranging error on performance of range-based M D S - M A P ( P , 0 ) in a lOr x lOr square network region employing uniform random place-ment of 200 nodes, and four deployed anchors. variance is changed from 0% to 50%. Figure 3.5 shows that the position estimation error increases as the range error (i.e., variance) increases. Results also show that the range-based scheme is more sensitive to the range error than to the average connectivity level. Figure 3.6 shows that both M D S - M A P ( P , O) and M D S - M A P ( P , C ) exhibit similar behavior to the increase of range error. This is due to the fact that both algorithms need to use the same shortest-path distance matr ix constructed from the measured node ranges. Chapter 3. Ordinal Multidimensional Scaling 59 F i g u r e 3 . 6 : Node ranging error comparison between range-based M D S - M A P ( P , C) and M D S - M A P ( P , O) using a network connectivity of 12 wi th four anchors. S e n s i t i v i t y A n a l y s i s o f A n c h o r s ' L o c a t i o n o n P o s i t i o n i n g E r r o r In this section, we study the effect on the position estimation error when anchors are being placed at different locations. Figure 3.7 shows the results when the anchors are being placed (a) linearly, (b) in a rectangular manner, (c) close to each other, and (d) randomly. A s we expect, the position estimation error is the highest when anchors are close to each other (see Figure 3.7 (c)). O n the other hand, the position estimation errors for the other three cases are similar (see Figure 3.7 (a), (b), (d)), wi th the rectangular case performing the best wi th an error of 9%. Since ordinal M D S algorithm does not require the use of triangulation, the position estimation error is s t i l l considered to be Chapter 3. Ordinal Multidimensional Scaling 60 (a) Linearly Aligned Anchors (error=0.11R) 10 e P ° 0 o ^ e P © & o o G°8 O ° ° o o o <© 0 0 ° n ° O (P( ° o o p? o C D O Pj o * o o F . O B o o o o1- o o • o°° O® C P 0 0 o % (9 Q Q O °o o Q O O SB 10 0 2 4 6 8 10 (c) Closely Spaced Anchors (error=0.25R) G-lb o ° , ^ G _ P Q P _ ©J ^P o P G P a @ GGG GO ° ° Q 0 & > G 0 ®JP 3 p @ o 0 O G o o< r * p P O" ^ -p o p P ° G - O G • © - ° 10 10 (b) Rectangular Aligned Anchors (error=0.09R) GTO G G G G£ -e-e .— G © o Q ( P P . G o 5 5 G P © o © Gd" G G P O G G ° Q°i °Q G GG° P G O GjG G | ° O G O . ° °G G 0 °G ( P O GO G Q G° 0 ^ o © 0 0 " 0 o 0 0 o o @ C P ° ° G © G G ° o o O O Q G ° 10 0 2 4 6 8 10 (d) Randomly Chosen Anchors (error=0.13R) . & % o o 0 ° o r©-e-o , 030 G G o ° G ° 5> G ' G°G G P n G o GEH G ^ G G 0 G" ( P G . G f > ° 0 O G 0 ^ o o o <p 0. G 0 0 © O ^ O ? < 3 D ° ° G ^ ° P G U G O ° © G 0 ° 10 Figure 3.7: Anchor topology results of range-based M D S - M A P ( P , O) when anchors are being placed (a) linearly, (b) in a rectangular manner, (c) close to each other, and (d) randomly. The topology consists of a lOr x lOr square network region employing uniform random placement of 200 nodes with connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. Est imat ion error is represented by lines. small even when the anchors are being placed linearly (see Figure 3.7 (a)). A s long as the anchors are not a l l located within a half radio range of each other, the orientation between the anchors has a small impact on the error as seen from the performance in Chapter 3. Ordinal Multidimensional Scaling 61 CD g 5 6 0 CD | 5 0 I 4 0 30 o £ 20 I 10 o a- o L (a) 4 anchors CD !=f 6 0 ro * 5 0 4 0 m OL ~ - 3 0 _ UJ 2 0 I 10 to o Q - 0 — — M D S - M A P ( P , 0 ) >< M D S - M A P ( P , O . R ) I-10 15 2 0 Node Connectivity (c) 8 anchors — — M D S - M A P ( P . O ) M D S - M A P ( P . O , R ) 10 1 5 2 0 Node Connectivity (b) 6 anchors 6 0 5 0 4 0 3 0 2 0 10 0 6 0 5 0 4 0 3 0 2 0 10 0 — — M D S - M A P ( P . O ) —* M D S - M A P ( P . O , R ) 10 15 2 0 Node Connectivity (d) 1 0 anchors — — M D S - M A P ( P . O ) >< M D S - M A P ( P , Q , R ) 10 15 2 0 Node Connectivity Figure 3.8: Performance of hop-based M D S - M A P ( P , 0) and M D S - M A P ( P , 0, R) in a lOr x lOr square network region employing uniform random placement of 200 nodes, for varying levels of connectivity and anchors deployed. both linear and rectangular cases (Figure 3.7 (a) - (b)). Further Improvement via (Optional) Global Relative Map Refinement The accuracy of the M D S - M A P ( P , 0) localization algorithm can further be improved by using an optional global relative map refinement [2]. This optional step is invoked after the patching of the local maps. The least-squares minimizat ion is used for the measured and calculated distances between neighboring nodes. This optional refinement step has a complexity of 0(N3) where N is the total number of sensor nodes. We use the notation M D S - M A P ( P , 0, R) to denote the original M D S - M A P ( P , 0) algorithm wi th Chapter 3. Ordinal Multidimensional Scaling 62 30 10 s i 20 (a) 4 anchors 10 15 20 Node Connectivity (c) 8 anchors M D S - M A P ( P . O ) M D S - M A P " ( P , 0 , R ) 10 15 20 Node Connectivity £ . 20 (b) 6 anchors — M D S - M A P ( P , 0 ) M D S - M A P ( P , 0 , R ) 10 15 20 Node Connectivity (d) 10 anchors M D S - M A P ( P . O ) M D S - M A P ( P . O , R ) 10 15 20 Node Connectivity Figure 3 . 9 : Performance between range-based M D S - M A P ( P , 0 ) and M D S - M A P ( P , 0 , R) in a lOr x lOr square network region employing uniform random place-ment of 200 nodes, for varying levels of connectivity and anchors deployed. global relative map refinement. Figures 3.8 and 3.9 show the performance comparisons between M D S - M A P ( P , O) and M D S - M A P ( P , 0 , R) in hop-based and range-based scenarios, respectively. The number of anchors deployed is varied from 4 to 10. In the hop-based case, there is significant reduction on the position estimation error when the average node connectivity level is above 9. 'The difference between the results is greater than 30% for high average connectivity levels. In the range-based case, there is only a slight improvement when the average connectivity level is greater than 12. The decrease in improvement as the node connectivity level increases can be attributed to the increased accuracy achieved by Chapter 3. Ordinal Multidimensional Scaling 63 each node wi thin its two-hop neighborhood. The higher connectivity levels provide much more range-information from which the ordinal M D S wi th local least-squares refinement methods result in accurate relative position estimates. Therefore, the global least-squares refinement performance decreases wi th node connectivity, since the local maps become more accurate and additional least-squares refinement does not increase the accuracy of the nodes significantly. Note that the global relative map refinement comes at a cost. A sensor node must process the global map and then propagate the results to al l the sensors in the network (e.g., v ia flooding). This may cause a higher signaling overhead. 3.3.2 Random Irregular Network Topology Whereas most papers presented have only considered uniform sensor network deploy-ments, the method in which these networks are meant to be deployed may not guarantee uniform coverage. Wireless sensor networks may exhibit regions of sparseness once de-ployed. Therefore, localization algorithms must be able to perform well under different conditions. In this section, we evaluate the performance of M D S - M A P ( P , O) by using the same topology in [2], (i.e., a C-shaped topology). In the simulations, it is noticed that the position estimation errors are changed when the anchors are placed at different positions. For good performance, it is recommended to have at least one anchor on each wing of the C-shaped topology. Chapter 3. Ordinal Multidimensional Scaling 64 ( a ) M D S - M A P ( P , C ) , ( e r r o r = 0 . 7 4 R ) *4?r — ( b ) M D S - M A P ( P . O ) , ( e r r o r = 0 . 6 5 R ) F i g u r e 3.10: Topology results of hop-based (a) M D S - M A P ( P , C) and (b) M D S - M A P ( P , 0 ) in a lOr x lOr irregular (C-shaped) network region employing uniform random placement of 160 nodes wi th connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. Est imat ion error is rep-resented by lines. H o p - B a s e d P e r f o r m a n c e Figure 3.10 shows the topologies estimated by hop-based M D S - M A P ( P , C) and M D S -M A P (P, 0 ) , respectively. The position estimation errors by M D S - M A P ( P , C) and M D S -M A P (P, O) are 74% and 65% of the radio range, respectively. The position estimation error of each individual sensor node varies. There is no correlation for sensors that are closer to the anchors to have better position estimation. Figure 3.11 shows the position estimation errors as a function of the average connec-t ivi ty level by hop-based M D S - M A P ( P , C) and M D S - M A P ( P , O) , in a C-shaped network topology. Results show that M D S - M A P ( P , O) outperforms M D S - M A P (P, C) by a 9% lower position estimation error when the network has a connectivity of 12 and four an-Chapter 3. Ordinal Multidimensional Scaling 65 (a) 4 anchors (b) 6 anchors 200 or 1 5 0 1 5 0 i 10 15 2 0 Node Connectivity (c) 8 anchors 10 15 2 0 Node Connectivity 1 5 0 s_ 1 0 0 ,S 5 0 10 15 2 0 Node Connectivity (d) 10 anchors 10 15 2 0 Node Connectivity F i g u r e 3 . 1 1 : Performance comparison between hop-based M D S - M A P ( P , C) and M D S -M A P (P, 0 ) in a lOr x lOr irregular (C-shaped) network region employing uniform random placement of 160 nodes, for varying levels of connectivity and anchors deployed. chors. This difference is greater than the square topology case; however, the confidence intervals among the two algorithms show considerable overlap. Th is is to be expected since the estimated shortest path distances are more prone to errors arising from the geometry of nodes that are wi th in the inside corners of the network. W h e n the average connectivity levels are 12 or higher, the position estimation error is less than 65%. R a n g e - B a s e d P e r f o r m a n c e Figure 3.12 shows the topologies estimated by range-based M D S - M A P ( P , C) and M D S -M A P ( P , 0 ) , respectively. The position estimation errors by M D S - M A P ( P , C) and M D S -Chapter 3. Ordinal Multidimensional Scaling 66 ( a ) M D S - M A P ( P , C ) , ( e r r o r = 0 . 5 2 R ) ( b ) M D S - M A P ( P . O ) , ( e r r o r = 0 . 4 6 R ) 0 2 4 6 8 1 0 0 2 4 6 8 1 0 Figure 3.12: Topology results of range-based (a) M D S - M A P ( P , C) and (b) M D S -M A P ( P , 0 ) in a lOr x lOr irregular (C-shaped) network region employing uniform random placement of 160 nodes with connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. Est imat ion error is represented by lines. M A P ( P , 0 ) are 52% and 46% of the radio range, respectively. Figure 3.13 shows the position estimation errors as a function of the average connectiv-ity level by range-based M D S - M A P ( P , C) and M D S - M A P ( P , 0 ) , for a C-shaped network topology. When the average connectivity level is 12, results show that M D S - M A P ( P , O) outperforms M D S - M A P ( P , C) by a 6% lower position estimation error. This difference is greater than the square topology case; however, once again the confidence intervals among the two algorithms show significant overlap. When the average connectivity level is 12 or higher, the estimation error is less than 46%. Chapter 3. Ordinal Multidimensional Scaling 67 100 20 1 (a) 4 anchors M D S - M A P ( P . C ) M D S - M A P ( P . O ) 10 15 20 Node Connectivity (c) 8 anchors M D S - M A P ( P , C ) M D S - M A P ( P , 0 ) 4^-4 10 15 20 Node Connectivity £. 80 •S 40 ^ 100 (b) 6 anchors — — M D S - M A P ( P , C ) - X M D S - M A P ( P . O ) 4 - 4 10 15 20 Node Connectivity (d) 10 anchors 10 15 20 Node Connectivity Figure 3.13: Performance of range-based M D S - M A P ( P , C) and M D S - M A P ( P , 0 ) in a lOr x lOr irregular (C-shaped) network region employing uniform random placement of 160 nodes, for varying levels of connectivity and anchors deployed. Further Improvement via (Optional) Global Relative Map Refinement Figures 3.14 and 3.15 show the performance comparisons between M D S - M A P ( P , O) and M D S - M A P ( P , 0 , R ) in hop-based and range-based scenarios, respectively. In the hop-based case, there is significant reduction on the position estimation error when the average node connectivity level is 12 or greater. The additional refinement scheme outperforms ordinal M D S in the hop-based results on average 25%, for connectivity levels 12 and greater, which is larger than in the square topology case. In the range-based case, the re-finement scheme achieves on average 26% better accuracy than the ordinal M D S scheme, Chapter 3. Ordinal Multidimensional Scaling 68 (a) 4 anchors (b) 6 anchors — - - M D S - M A P ( P . O ) M D S - M A P ( P , 0 , R ) V V 10 15 20 Node Connectivity (c) 8 anchors — — M D S - M A P ( P . O ) M D S - M A P ( P . O , R ) 10 15 20 Node Connectivity 25 50 — — M D S - M A P ( P . O ) - * M D S - M A P ( P , 0 , R ) 10 15 20 Node Connectivity (d) 1 0 anchors — — M D S - M A P ( P . O ) - X M D S - M A P ( P , C \ R ) 10 15 20 Node Connectivity 25 Figure 3.14: Performance comparison between hop-based M D S - M A P ( P , 0 ) and M D S -M A P ( P , 0 , R) in a lOr x lOr irregular (C-shaped) network region employ-ing uniform random placement of 160 nodes, for varying levels of connec-t ivi ty and anchors deployed. which again is a higher gain in accuracy compared to the square topology results. Thus the benefit of the M D S - M A P ( P , 0 , R) is greater in the irregular (C-shaped) topology than in the uniform (square) topology. This is expected, since the iterative refinement of the global map in the irregular case takes into account the topology from the result of the in i t ia l M D S - M A P ( P , 0 ) result. Thus, the refinement scheme is able to improve the result by iteratively reducing position estimation error from a global viewpoint of the network. Chapter 3. Ordinal Multidimensional Scaling 69 Figure 3.15: Performance comparison between range-based M D S - M A P ( P , O) and M D S - M A P ( P , 0 , R) in a 107- x lOr irregular (C-shaped) network region employing uniform random placement of 160 nodes, for varying levels of connectivity and anchors deployed. 3.4 Summary In this chapter we proposed and analyzed, the M D S - M A P ( P , O) localization algorithm for wireless sensor networks. The M D S - M A P ( P , O) algorithm is an extension of the M D S - M A P ( P , C) algorithm originally proposed in [2]. The algorithm is extended by using the ordinal M D S algorithm instead of the classical M D S algorithm. The proposed M D S - M A P ( P , O) algorithm is essential for future sensor applications which require a high accuracy of nodes' position by using a small number of anchor nodes. The algorithm can be applied not only to the case where nodes are equipped with distance-estimation hard-Chapter 3. Ordinal Multidimensional Scaling 70 ware (range-based), but also to the case where only connectivity information (hop-based) is available. Simulation studies were conducted under both regular (square) and irreg-ular (C-shaped) topologies, resulting wi th M D S - M A P ( P , O) providing a lower position estimation error than M D S - M A P ( P , C) in both hop-based and range-based scenarios. 71 Chapter 4 Concentric Anchor-Beacons (CAB) Localization Algorithm In this chapter, we propose two C A B localization algorithms for wireless sensor networks; C A B wi th Equa l Area ( C A B - E A ) and C A B wi th Equa l W i d t h ( C A B - E W ) . We first state the motivations and assumptions. It is followed by the description of the C A B algorithms. We then discuss the advantages and limitations of the proposed scheme. It is followed by the performance evaluation and comparison to other schemes. 4.1 Motivations and Assumptions Although distributed range-based algorithms have a higher accuracy than the distributed range-free approaches in general, the range-free approaches are more cost effective. In this chapter, we focus on the design of a distributed range-free localization algorithm that has a high accuracy and does not require communication between neighboring sensor nodes. In our proposed scheme, each sensor node estimates its position solely based on the information gathered directly from the anchor nodes. Since it does not depend on neigh-Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 72 boring sensor node communication, it is independent of network connectivity. Sensor nodes do not require any special range-determining hardware for localization. O n the other hand, anchors are equipped wi th G P S modules. Thus, anchor nodes are more costly, consume more energy, and are larger in size than normal sensor nodes. In addition, as in the case of some other schemes (e.g., [10]), anchors are assumed to have larger com-munication range than normal sensor nodes. The anchor-to-node range ( A N R ) ratio is equal to the maximum communication range of an anchor divided by the communication range of a sensor node. The main difference between C A B and other range-free localization approaches is that in C A B , anchors transmit several beacon signals at different power levels. This requirement is feasible in current wireless sensor networks. For example, the Mica2 mote sensor nodes have a range of 18 meters for transmission power of -10 dbm, and 50 meters for 0 dbm [41] [42]. Ideally, the different power levels divide the possible transmission ranges of an anchor into a circle and rings. A s shown in Figure 4.1, the lowest power level creates a circular coverage area, and the following higher levels are distinguished by rings emanating from this lowest level. In the wireless propagation environment, the signal power received by a sensor node (PrCv) is related to the signal power transmitted by an anchor node ( P t x ) by the following Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 73 (a) (b) Figure 4 .1 : Anchor beacon transmission ranges with (a) Equa l area beacon signals with 3 power levels; and (b) Equa l width beacon signals wi th 3 power levels. Ai (i = 1,2,3) denotes the area of the i t h ring/circle; Wi (i = 1, 2, 3) denotes the width of the ith r ing/circle. equation [17]: P r c v = r n (4-1) where r denotes the distance between the anchor node and the sensor, A; is a constant, and n denotes the path loss exponent. Given the target B E R , we let Pthreshoid denote the min imum required received signal power in order to decode the signal correctly. Let Pmax (milliWatts) denote the maximum power that an anchor node can transmit. The maximum range (distance) r m a x (metres) corresponds to the necessary distance between the anchor and the sensor node such that the sensor can decode the signal correctly. The resulting formula can be solved in terms of r m a x as shown in the following equations. Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 74 k-PT max threshold ,71 max max threshold max r-, max (4.2) The abili ty of a node to hear beacons with lower transmitted powers, implies that the node lies closer to the anchor than the maximum range. Consider an example in Figure 4.1(a). If the sensor node can hear the beacons wi th power levels P i , Pi and P3, then the distance between the anchor and the node is less than r\. Tha t is, the sensor node lies wi th in the inner-most circle, O n the other hand, if the node can only hear the beacon wi th power level P3, then it lies wi th in the outermost ring. The C A B algorithm is developed based on the above assumptions. Note that if a beacon is heard by a node, it is assumed that the received signal power at the node is greater than or equal to the minimum threshold power. In this work, two variations of the C A B localization algorithm are considered, namely: C A B - E A and C A B - E W . For C A B - E A ( C A B wi th Equa l Area) , it is assumed that the area of the inner-most circle and the rings are al l the same. Tha t is, in Figure 4.1(a), the circle wi th radius r\ has the same area as each of the rings outside that circle. The 4.2 CAB Algorithm Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 75 relationship between the beacon transmission ranges r-j and the maximum transmission range rmax is given by the following equation: where i denotes the beacon number starting from the lowest power level (or transmission range), m denotes the total number of different beacon power levels, denotes the transmission range for beacon i, and rmax denotes the maximum range that an anchor can transmit at the corresponding maximum power level Pmax-Therefore, in relation to power levels, the corresponding equation is as follows: where again i denotes the beacon number starting from the lowest power level, m denotes the total number of power levels, n denotes the path loss exponent, and P; represents the transmit power for beacon % in terms of the maximum transmit power Pmax. For C A B - E W ( C A B wi th Equa l Wid th ) , it is assumed that the width of the inner-most circle and the rings are al l the same. The relationship between the beacon transmission ranges and the maximum transmission range r m a x is given by the following equation: (4.3) (4.4) i (4.5) i = 1,2, • • • ,m The corresponding relationship between power transmission levels P; and the maxi-Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 76 Invalid Intersection Points Figure 4.2: A n example of localization using C A B . mum transmit power P m a x is given below: P i = (j^ Pmax i = 1,2, • • - ,m (4.6) Before deployment, measurement is necessary to relate the transmission power Pj and coverage range r-j. Thus, the maximum range is empirically determined to be the distance from an anchor node, transmitting at maximum power, at which a sensor node has a received signal power equal to the minimum threshold power. Th is is important in order to ensure the accuracy of the range-free approach. In Section 4.4, the effects when the information between p and r; is not accurate due to interference from the neighboring environments w i l l be studied. The C A B localization algorithm is now described in detail. The algorithm described below is applicable to both C A B - E A and C A B - E W . Anchors transmit beacon signals Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 77 Table 4.1: Information collected by a sensor from its anchors. Anchor 3 Posit ion (xj,Vj) Beacons Transmit Power Info Constraint Region A (5.6, 6.2) (ri - r) ring B (9.6, 8.2) P2 (7*1 - r) r ing C (9.9, 5.2) Pl, P2 r\ circle at varying power levels during random time periods. Tha t is, anchors alternate from transmit and non-transmit modes randomly. For each anchor, the mode intervals consist of a random process of independent and identically distributed random variables each having a uniform distribution up to a maximum time T. W h e n in transmit mode, the anchor broadcasts the beacon. A t each transmit mode the beacon is sent at a different power level, intermittently repeating the cycle of power levels transmitted. Each beacon signal packet includes the anchor's ID , the anchor's location, the transmit power level Pi information, and the estimated maximum distance that the beacon signal can be heard. Each node listens for beacons and collects the anchor's information. For each beacon heard, the sensor node determines wi th in which region of the anchor's concentric transmission circles it lies. Figure 4.2 shows an example wi th a sensor node surrounded by three anchors. Each anchor transmits beacons at two different power levels. The corresponding information table collected by the sensor is shown in Table 4.1. Depending on the percentage of anchors deployed, each sensor node can hear multiple beacons from different anchors. For computational simplicity, information from at most Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 78 three neighboring anchors is used to estimate a sensor's location. In order to increase the accuracy of the position estimate, it is necessary to minimize the region of intersection by choosing the three anchors that are farthest. This . is accomplished by calculating all the possible triangular areas that are made up of the anchors heard, and by choosing the three anchors that form the largest triangle. Each sensor node can receive multiple beacons wi th different power level information from the same anchor. Based on this information, the sensor node can determine which particular ring or inner circle it lies wi th in from that anchor. Th is is called the constraint region. Mathematically, this region is bound by either two equations of circles (for the ring case) or just one equation of a circle (for the inner-most region of the anchor). The last column in Table 4.1 shows the constraint regions that the sensor node lies within based on the scenario in Figure 4 .2 . Given the three chosen anchors, two of them are selected at a time to calculate the intersection points. The valid intersection points satisfy a l l three anchors' constraint regions. The invalid intersection points are those that do not lie wi th in the other anchor's constraint region. Consider the example in Figure 4 .2 . Let (XA,VA), {XB,VB), (xc,yc) denote the positions of anchors A, B, and C, respectively. Let I denote the set of intersection points. For each point (x,y) € I, it is a valid intersection point if the following constraints are satisfied: Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 79 n < y (xA - xf + (VA - yf < r, n < \j(xB - xf + (yB - yf < r, \J{xc ~ xf + (yc - yf < rl. The final position estimate is taken as the average of al l the valid intersection points. Figure 4.2 shows the estimated position determined by four valid intersection points. 4.3 D i s c u s s i o n There are three distinct advantages of the C A B localization algorithm. First of al l , C A B is distributed and is simple to implement. For the anchors, their only task is to transmit beacon signals at varying power levels. For each sensor node, the determination of the intersection points from three chosen anchors as well as the position estimate by averaging are not computationally intensive. Secondly, no information exchange between neighboring sensors is necessary. This reduces the energy requirement for localization. In addition, C A B has a higher accuracy than some other range-free localization algorithms. Simulation comparisons wi l l be presented in the next section. For the qualitative comparisons wi th some other localization algorithms, A P I T [10] requires communication between neighboring nodes for the exchange of tabular infor-mation of nearby anchors. C A B does not require that procedure and achieves better results under smaller anchor-to-node range ( A N R ) ratio. In comparison to Centroid [11] Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 80 which requires a grid-based deployment, C A B is able to perform sufficiently well in ad hoc deployments. Whereas ring sizes are determined from RSS values in R O C R S S I [26], the rings in C A B are pre-determined according to the number of power levels desired to be used by the anchor. No communication is required between anchors in C A B . The C A B scheme does have its l imitations. Being solely dependent on anchor nodes for position estimation, the accuracy depends on the percentage of anchor nodes deployed. This percentage can be decreased by increasing the maximum radio range of the anchors. However, this results in less accuracy since the intersection areas become larger. Also, since the scheme's computation relies on a circular radio model, it can be affected by irregular radio propagation, of which other range-free schemes are relatively immune to. In Section 4.4, we wi l l also present the results of the scheme under a different degree of radio pattern irregularity. 4 . 4 Performance Evaluation and Comparison In this section, the performance evaluation of C A B - E A and C A B - E W as well as the comparisons wi th A P I T [10] and Centroid [11] algorithms are presented. A l l algorithms are simulated in Mat lab . The wireless sensor network consists of 280 nodes and a varying number of anchors are randomly placed. The network topology is a square of side 10R by 10R, where R is the sensor node communication range. The average connectivity among nodes is set to 8. The technique in [10] to model the irregular radio pattern is used in this simulation Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 81 DOI = 0.01 DOI = 0.05 DOI = 0.10 Figure 4.3: Irregular radio patterns for different values of D O I . model. In this model, al l nodes wi th in half of the maximum transmit radio range of anchors are guaranteed to hear from the anchor, whereas nodes between the maximum radio range and half of that range may or may not hear from the anchor depending on the radio pattern in that direction. The degree of irregularity (DOI) parameter is defined as the maximum radio range variation per unit degree change in direction. Examples of different D O I values of this irregular radio pattern model are shown in Figure 4.3. For the simulation of C A B , it is assumed that the path loss exponent (n) is equal to 2. The anchor-to-node range ( A N R ) ratio is set to 3. The D O I value is set to 0.05. The estimation errors are normalized wi th respect to the sensor node range (R). 4.4.1 Performance of C A B In Figure 4.4, the percentage of nodes that are able to hear at least three.anchors versus the percentage of anchors deployed is shown. In general, it is desirable to deploy a minimal percentage of anchors nodes to localize the system. The results show that for 12% of anchor nodes deployed, A N R values of 3 or higher enable at least 90% of al l nodes Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 82 100 9 0 8 0 - | 7 0 6 0 5 0 4 0 3 0 2 0 1 0 A N R = 4 A N R = 3 A N R = 2 A N R = 1 4 6 8 1 0 1 2 1 4 P e r c e n t a g e o f A n c h o r s D e p l o y e d ( % ) 1 6 1 8 Figure 4 . 4 : Comparison of percentage of nodes localizable versus percentage of anchors deployed for varying levels of A N R . ( D 0 I = 0.05) to obtain position estimates. A s the A N R value increases, the percentage of nodes able to hear at least three anchors also increases; however, this results in less accurate position estimation. Considering this tradeoff, it can be reasoned that an A N R of 3 is suitable for anchor percentages as low as 16%. Figure 4.5 shows the accuracy gain of (a) C A B - E A and (b) C A B - E W by increasing the number of power levels of the beacons (i.e., increase of m). W h e n beacons are being transmitted at a single power level (m = 1), the intersection area is constructed by determining the intersections of three circles centered at their corresponding anchors. It is clear that wi th two different power levels (m = 2), it reduces the intersection area to intersections of rings and circles. Figure 4.5 shows that the estimation error reduces by Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 83 (a) C A B - E A on B - Number of Power Levels = 1 -0— Number of Power Levels = 2 * Number of Power Levels = 3 LU c o 2 2 LU 6 8 10 12 14 Percentage of Anchors Deployed (%) (b) C A B - E W 16 18 ^ 3 on LU .1 2 1 -t—» CO E -*—* in LU - B - Number of Power Levels = 1 0 Number of Power Levels = 2 • • • * • • Number of Power Levels = 3 6 8 10 12 14 Percentage of Anchors Deployed (%) 16 18 Figure 4.5: Average estimation error under different number of power levels of the bea-cons for (a) C A B - E A and (b) C A B - E W . ( A N R = 3, D O I = 0.05) Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 84 at least 0.441? when m increases from 1 to 2 for C A B - E A , a significant improvement. Notice that when the number of different power levels increases to 3 (or higher), the performance improvement is marginal. This is due to the fact that when m is further increased, the anchor coverage area is subdivided into a circle and more concentric rings. The irregular radio pattern model introduces more errors to the rings wi th smaller ring width . However for C A B - E W , the performance improvement is significantly better for 3 power levels than 2. Th is can be attributed to the fact that the outer ring widths are wider in C A B - E W than in C A B - E A , which provides higher tolerance for radio pattern irregularity in determining which ring the node resides within . For anchor percentages greater than 12% C A B - E W wi th 3 levels outperforms its 2 power level counterpart by 0.251?. Thus for C A B - E W , it is be beneficial to use 3 power levels, while for C A B - E A , 2 power levels are sufficient. Figure 4.6 shows the performance comparison for C A B - E W and C A B - E A for 2 power levels. Clearly, the C A B - E A scheme outperforms C A B - E W in this case, since the estima-tion error is reduced by 0.221? on average when using C A B - E A . This can be attributed to the fact that with only 2 power levels, and the choosing of anchors that are furthest apart, the node positions are determined more by the intersection area of the outer rings. The radio pattern irregularity does not significantly affect the wrong judgement of the node to which section of an anchor it lies wi th in because the ring sizes are greater for the 2 power level case than the 3 level case. B y scheme model, C A B - E A has a smaller outer ring width than C A B - E W . Therefore, wi th C A B - E A the intersection area of the outer Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 85 0 . 5 1 ' 1 ' 1 L — 1 1 1 2 4 6 8 1 0 1 2 1 4 1 6 1 8 P e r c e n t a g e o f A n c h o r s D e p l o y e d ( % ) Figure 4 . 6 : Comparison of estimation error between C A B - E W and C A B - E A . (m = 2, A N R = 3, D O I = 0.05) rings is on average smaller than the intersection area of the C A B - E W scheme, hence resulting in C A B - E A achieving more accurate positioning estimates. Comparison of C A B - E W and C A B - E A using three beacons and varying D O I values is shown in Figure 4.7. In Figure 4.7(a), the perfect radio propagation model results in the C A B - E A marginally outperforming C A B - E W . When the D O I value is increased to 0.05 as shown in (b), the C A B - E W achieves lower estimation error for anchors deployed of 7% or greater. A s the D O I value is further increased to 0.10 in (c), C A B - E W is clearly more accurate, achieving 0.27i? lower error for 16% of anchors deployed. These results show that, C A B - E W is more resilient to D O I irregularity than C A B - E A . Of course, the relatively small difference in performance indicates that this result is sensitive to the Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 86 (a) DOI = 0 LU Q I I I I I I I I I 2 4 6 8 10 12 14 16 18 Percentage of Anchors Deployed (%) (b) DOI = 0.05 i i i i i i i i i 2 4 6 8 10 12 14 16 18 Percentage of Anchors Deployed (%) (c) DOI = 0.10 2 4 6 8 10 12 14 16 18 Percentage of Anchors Deployed (%) Figure 4.7: Comparison of estimation error between C A B - E A and C A B - E W for differ-ent D O I values: (a) D O I = 0, (b) D O I = 0.05, and (c) D O I = 0.10. (m = 3, A N R = 3) Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 87 2 . 5 9=. 2 •M 1 - 5 0 . 5 E3 — A n c h o r s C h o i c e = R a n d o m 0 A n c h o r s C h o i c e = O p t i m a l 6 8 1 0 1 2 1 4 P e r c e n t a g e o f A n c h o r s D e p l o y e d ( % ) 1 6 1 8 Figure 4.8: Comparison of estimation error using randomly heard anchors versus opti-mally chosen anchors, (m = 2, A N R = 3, D O I = 0.05). actual model of irregular radio pattern used. A n explanation for this may be due to the fact that C A B - E A has rings closer together near the maximal transmission range, and therefore for larger D O I values, the irregularity results in error prone determinations of which ring the sensor node is within. C A B - E W , however, has uniformly separated rings, and is therefore less prone to errors near the edge of the maximal transmission range. Therefore, we can conclude that the use of C A B - E A is suitable for m = 2 and for C A B - E W it is best to use m — 3. It is possible that a sensor node may receive beacon signals from more than three anchors. In C A B , only three neighboring anchors are used for localization. Figure 4.8 shows the comparison between two different ways of choosing those neighboring anchors. Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 88 For the case of random, the three anchors heard wi th the lowest IDs are chosen. For the case of optimal, the three anchors which form the largest triangle are chosen. Results in Figure 4.8 show that the - optimal approach provides a much lower estimation error than the random choice. A s an example, when the percentage of anchors deployed is 11%, the opt imal choice provides an estimation error 0.95.R lower than the random choice on average. In addition, for the optimal choice, the estimation error decreases when the percentage of anchors deployed increases. This is expected since there are more anchors from which to choose. The choice of using only three anchors for position estimation is to reduce the compu-tational requirement, since considering more anchors results in many more intersection points to be computed. We are aware that choosing the anchors that result in the largest triangular region does not always guarantee the smallest coverage intersection, since the intersection also depends on the size of the circle or ring constraining the position of the node. However, further results show that choosing the 3 anchors that form the largest triangle is sufficient in achieving good accuracy. 4.4 .2 Comparisons between CAB, APIT, and Centroid Figure 4.9 shows the position estimation errors as a function of the percentage of an-chors deployed. C A B has a better performance than both A P I T and Centroid. As an illustration, when the percentage of anchors deployed is 16%, C A B - E W wi th three power levels achieves 0.78R accuracy and C A B - E A wi th two power levels has an average error Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 89 2 . 5 0 . 5 O.. O • • C e n t r o i d — A. — A P I T C A B - E A — Q — C A B - E W 6 8 1 0 1 2 1 4 P e r c e n t a g e o f A n c h o r s D e p l o y e d ( % ) 1 6 1 8 Figure 4 .9: Comparison between Centroid, A P I T , C A B - E A (m = 2), and C A B - E W (m = 3) by increasing the percentage of anchors deployed. ( A N R = 3, D O I = 0.05) of 0.81i?. The other schemes, A P I T and Centroid achieve 0.94.R, and 1.31/2 accuracy, respectively. Note that the performance of C A B can further be improved by ut i l izing information from more than three anchors at the expense of a higher number of com-putations. More specifically, in C A B for each pair of anchors the maximum number of system of equations to be solved is 4. A s the set of anchors used to compute the position estimation increases, the number of possible systems of equations to be solved follows a complexity of 0(N2), where N denotes the number of anchors used in the computation of the position estimate. Figure 4.10 shows the results of the estimation error as a function of A N R ratio. Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 90 3 4 5 6 A n c h o r - t o - N o d e R a n g e ( A N R ) R a t i o F i g u r e 4 .10: Comparison between Centroid, A P I T , C A B - E A (m = 2), and C A B - E W (m = 3) for varying levels of A N R . (DOI = 0.05) The percentage of anchors deployed is 9%. As the A N R value increases, this results in a loss of accuracy in al l schemes. In the Centroid scheme, nodes can now hear anchors that are farther, and the result is a more coarse grained estimation of position. In the A P I T scheme, the A N R actually improves the accuracy unt i l A N R equals 5. The error then increases wi th higher A N R values. This unique behavior can be attributed to the InToOut error identified in [10] which is more significant at low A N R values and diminishes wi th increasing A N R . The C A B algorithm only relies on anchor information and thus increases in error as A N R increases, as can-be seen by the C A B - E A and C A B -E W plots. Once again, C A B - E W uses three different power levels whereas C A B - E A uses two levels. The higher A N R values result in larger ring areas that in turn create larger Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 91 2.5 h 9=. LU CO J 1. 5 4 -0.5 o O . . , Q . . C e n t r o i d — A. — A P I T 0 C A B - E A — • — C A B - E W _ ^ A /V- - -V\ A Ar -| f i — • — Q - • — 0.02 0.04 0.06 0.08 R a d i o P a t t e r n D e g r e e o f I r r e g u l a r i t y ( D O I ) 0.1 Figure 4.11: Comparison between Centroid, A P I T , C A B - E A (m = 2), and C A B - E W (m = 3) under different D O I values. ( A N R = 3) intersections wi th in which the node estimate is taken. Figure 4.10 also shows that A P I T outperforms both C A B schemes for A N R greater than 4. Note that in A P I T , each sensor node consumes additional energy for the exchange of information between neighboring nodes. In C A B , information exchange between neighboring nodes is not necessary. In other words, the accuracy of C A B does not depend on the average node degree or the connectivity information. Figure 4.11 shows the effects of irregular radio propagation on the accuracy of the range-free schemes. The percentage of anchors deployed is 9%. Due to the use of the fixed empirical range values for different transmit power levels of the beacons, the C A B schemes are more sensitive to the irregular radio pattern than Centroid and A P I T . When D O I Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 92 values are less than 0.09, C A B - E A outperforms the other two schemes, whereas C A B - E W outperforms all schemes since it incorporates 3 power levels. Based on the above results, it is suggested that the following parameters be used for the implementation of the C A B - E A localization algorithm: m = 2, r i = 0.707r, ANR < 3, percentage of anchors deployed higher than 9%. For applications requiring greater accuracy, the use of C A B - E W is suitable, wi th the following parameters: m == 3, ?'i = 0.33r, r2 = 0.66r, ANR < 3, and percentage of anchors deployed higher than 9%. 4.5 C A B Extension to other Localization Schemes The novelty of the C A B algorithm is the different power levels at which the anchor nodes broadcast beacons. Al though this property has been used to construct a range-free scheme that estimates positions of sensor nodes to be wi th in the intersections of rings or circles, it is evident that different aspects of C A B can be applied to some other previously proposed localization schemes. The three different aspects of the C A B algorithm are: (1) different power level beacons, (2) circular and ring position constraints, and (3) position estimation based on selected anchors' information. These techniques can be independently applied to several other schemes to enhance the performance. In tradit ional range-based schemes, specialized ranging hardware is required to obtain the distance information between nodes. However, due to channel fading and interference, estimation based on R S S does not always provide a robust means of distance information. B y incorporating the beaconing anchor property, the reliance on specialized hardware Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 93 and/or RSS measurements can be reduced. The corresponding result is that range-based schemes can function in a relatively range-free manner depending on scheme-specific details. The only assumption in C A B is that there is a reference maximum transmission power and the corresponding transmission range that is empirically derived prior to system deployment to take into account environment propagation characteristics. The incorporation of circular and ring constraints can be separately included to the existing schemes, in order to provide an overlapping region based localization as opposed to lateration or triangulation. Lastly, as evidenced in the C A B scheme, instead of using all information gathered from al l anchors heard to determine position estimates, three anchors were selectively chosen from which the position estimate was to be computed. In the proposed C A B algorithm, it is advantageous to do so from a computational point of view which is necessary for practical implementations. Other schemes may also be able to benefit from the selectivity of anchor information, whether to reduce computational needs of the scheme or to avoid information that may be prone to errors. 4.5.1 Possible Scheme-Specific Modifications In the convex positioning scheme [5], instead of using anchors and nodes wi th fixed radio range, the use of different power level beaconing can be advantageous. Nodes can listen to beacons from other nodes and determine their communication constraint as the distance corresponding to the lowest power level heard from another node. The accuracy of the Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 9 4 approach depends on the number of power levels used. Once the nodes have determined their constraining circles, the linear matr ix inequalities ( L M I ) can be obtained and the solutions can be determined by the corresponding semi-definite programs (SDPs) . For anchor propagation schemes such as A P S [6], in addition to the hop-by-hop trans-mission of beacons, the anchors can also transmit at different power levels to directly reach further sensor nodes. Nodes can then simultaneously execute both A P S and C A B proce-dures and ensure that the estimated position based on A P S falls wi th in the intersection of the rings and circles determined by C A B . Alternatively, when nodes calculate distances based on hop count, they can use the information from the power levels heard to ensure that the calculated distances are accurate prior to computing a position estimate. In addition, A P S can benefit from selecting only the closest anchors for position estimation, since distances calculated from anchors that are farther away can be inaccurate. Range-free schemes can also benefit from the use of multiple beacons from anchors. The main benefit is the additional information gathered by the node, in terms of how close it is from the anchor by simply monitoring the received power levels. In the Centroid scheme, each node determines its location by averaging the positions based on all of the different anchors heard. B y using multiple power levels, more information is gathered by nodes to further enhance the position estimate. Nodes can therefore assess the different power levels in order to estimate their position more accurately. Thus, a node that can hear more than one power level from an anchor wi l l give more weight to that anchor than another where it can only hear a single power level. Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 95 The A P I T scheme can also be extended since its structure is similar to C A B in the use of anchors wi th larger transmission ranges than nodes. Instead of using a S C A N - g r i d algorithm to determine the overlapping of only triangles formed by anchor positions, the overlapping of circular regions can also be included to further optimize the position estimate. Alternatively, the overlapping of rings can be used in the S C A N - g r i d algorithm to estimate the position of the node. In order to reduce the errors identified as InToOut and OutToIn in [10], sensor nodes can obtain estimates of distance from the three closest anchors by using the corresponding distance related to the lowest power level heard from an anchor. Using these three estimated distances, lateration can be used to ensure that the A P f T results satisfy the circular constraints. 4.6 Summary In this chapter, the C A B localization algorithm for wireless sensor networks was proposed. C A B is a distributed range-free approach that does not require information exchange between neighboring sensors. It has a low computational overhead that is simple to implement. C A B uses anchors that broadcast beacon signals at varying power levels. Th is allows each sensor node to identify which annular ring centered at the anchor that the node resides in . The estimated position of the node is taken as the average of all the valid intersection points. Simulation results show that C A B provides a lower position estimation error than A P I T and Centroid under a wide range of conditions. It is also evident that the novel method of anchor-beaconing can be applied to previously Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 96 proposed schemes that may be worthwhile in reducing position estimation error and even outperform C A B itself. Further modifications of the scheme can be performed in order to optimize the location of the ring boundaries, given an accurate radio propagation model. In addition, analysis on the benefits of additional anchor information could be conducted. 97 Chapter 5 Conclusions and Future Work A s evidenced from the diverse techniques being employed to solve the sensor node lo-calization problem, this area is under continued refinement and development. Though many different proposals have been made, the assumptions in the models have l imited the applicabili ty of the individual schemes in other networks. Hence, for future work, the continued search for a technique or algorithm capable of providing accurate sensor positions, lies in the realm of robustness under different network conditions. To suit this purpose, the scheme must work in a decentralized manner, contain a low percentage of anchor nodes (less than 10%), and be able to cope wi th low node connectivity. In general, connectivity is considered to be low if a node has less than 9 neighbors, medium if it has up to 15 neighbors and high if the connectivity is greater than 15. Decentralized networks may contain anchors deployed in random fashion or carefully placed in the coverage area. The latter being a more suitable design goal for new schemes. In addition, the aspect of positioning delay has seldom been considered in proposed schemes. In terms of this delay, the better scheme is able to provide the positions of a l l nodes wi th in a specified amount of time, having much relevancy to the way in which the algorithm is executed in the network. Chapter 5. Conclusions and Future Work 98 5.1 Future Work In terms of future work, several areas are of interest: mul t imodal and measurement-free techniques, accuracy, energy consumption, mobility, and security. The use of mult imodal techniques employing both range and angle measurements, have outperformed sole range or angle-based techniques in terms of measurement accu-racy. Indeed, this wi l l be an area to further explore, as only a few papers have explored this possibility, and have not yet come wi th an efficient way of combining both measure-ments in a decentralized and parallel manner. The main problem in this approach has been the actual feasibility of sensor nodes being equipped wi th mult imodal hardware. The complete opposite to this approach is avoiding measurements at al l , sighting inaccu-racies of measurement approaches, several papers have presented novel schemes [10] [28] involving reducing the possible position of nodes by constraining regions as has been proposed in this thesis. In general, al l schemes have quoted their accuracy wi th respect to sensor commu-nication range. In terms of future work, the development of more accurate schemes is clearly possible. According to results so far, the most accurate schemes contain medium or high node connectivity levels, as evidenced by the unsurpassed results obtained by M D S techniques. Further work must be done in order to achieve accuracy at low levels of connectivity, thus having a greater impact by drastically reducing the amount of nodes that need to be deployed. In addition, the development of ranging technology to be used in the sensors can greatly affect the accuracies achieved. The use of U W B technology Chapter 5. Conclusions and Future Work 99 has shown to provide incredibly accurate results in the presence of obstacles from indoor deployments. The extension to outdoor sensor networks has yet to be explored. Another aspect of the localization problem is the energy consumption. Few, if any, schemes have actually explored the impact of their techniques on the sensor nodes' bat-tery power. This is by far the most under-developed aspect of this area, relative to the significance in an actual sensor network deployment. Since localization of the nodes is only necessary to aid the sensor network in achieving its deployment purpose, the posi-tioning scheme must not deplete the sensor nodes and thus prevent them from achieving their main deployment purpose. This can be avoided by schemes involving the passive localization of sensor nodes, in which nodes position themselves relative to fixed system anchors, and need not communicate with other sensors in order to obtain accurate po-sitions. Of course, this again affects the robustness of the scheme in terms of ad-hoc deployments, and thus further work may have to be done in developing hybrid models where the necessary communication between nodes is l imited. Another important step is in the development of positioning schemes for mobile sensor nodes. A few papers have extended their schemes from fixed positions to enable moderate mobil i ty in the network, but clearly such schemes do not make use of the increased information available to them due to node movement. Whereas, some have presented the case that mobil i ty adversely affects position estimation, others have countered that claim. A s nodes become mobile, the neighborhood information is constantly changing wi th respect to each node. This additional information, unavailable in static networks, Chapter 5. Conclusions and Future Work 100 should be used as an advantage in the node localization problem. One promising approach is in the realm of statistical based techniques, extensively used in the target tracking and signal processing communities. Such techniques use information to construct probability density functions of each node's position in the network to obtain position information. The continuous movement of nodes wi l l eventually result in accurate tracking of all nodes in the network. Many questions st i l l remain to be answered in this area, including the accuracies possible, energy consumptions, computational effort required and the efficacy of decentralized approaches. Lastly, a facet remaining to be explored is the issue of security in the network com-munications of the sensors. Many applications have been proposed for such networks in adversarial settings, which impose security threats on the network. Several papers have outlined some of these issues and proposed methods to be employed in existing schemes to make them more secure. However, separate development of security and positioning techniques is inefficient, and a better approach would be to incorporate security measures wi th in the localization scheme. The more robust architectures in terms of security are more centralized, since it is assumed that fixed anchors and central computation author-ities are trusted, whereas in distributed systems sensor nodes greatly affect the systems information and thus malicious nodes have greater impact on the system. 101 Bibliography [1] Y . Shang, W . R u m l , Y . Zhang, and M . Fromherz, "Localization from mere connec-tivity," in Proc. of ACM MobiHoc, Annapolis , M D , June 2003, pp. 201-212. [2] Y . Shang, W . R u m l , and Y . Zhang, "Improved MDS-based localization," in Proc. IEEE Infocom, Hong Kong , China , March 2004, pp. 2640-2651. [3] I. A k y i l d i z , W . Su, Y . Sankarasubramaniam, and E . Cayi rc i , "Wireless sensor net-works: A survey," Elsevier Computer Networks, vol. 38, pp. 393-422, 2002. [4] D . Niculescu, "Positioning in ad hoc sensor networks," IEEE Network Magazine, vol. 18, no. 4, pp. 24-29, Ju ly 2004. [5] L . Doherty, K . Pister, and L . Ghaoui , "Convex position estimation in wireless sensor networks," in Proc. of IEEE Infocom, Anchorage, A K , A p r i l 2001, pp. 1655-1663. [6] D . Niculescu and B . Nath , "Ad-hoc positioning system," in Proc. of IEEE Globecom, San Antonio, T X , Nov. 2001, pp. 2926-2931. [7] K . Langendoen and N . Reijers, "Distributed localization in wireless sensor networks: A quantitative comparison," Computer Networks, vol . 43, pp. 499-518, Nov. 2003. Bibliography 102 [8] D . Niculescu and B . Nath , "Ad-hoc positioning system ( A P S ) using A O A , " in Proc. of IEEE Infocom, San Francisco, C A , A p r i l 2003, pp. 1734-1743. [9] K . Chintalapudi , A . Dhariwal , R. Govindan, and G . Sukhatme, "Ad-hoc localization using ranging and sectoring," in Proc. of IEEE Infocom, Hong Kong , China , March 2004, pp. 2662-2672. [10] T . He, C . Huang, B . L u m , J . Stankovic, and T . Adelzaher, "Range-free localization schemes for large scale sensor networks," in Proc. of ACM MobiCom, San Diego, C A , September 2003, pp. 81-95. [11] N . Bulusu, J . Heidemann, and D . Es t r in , "GPS-less low cost outdoor localization for very small devices," IEEE Personal Communications Magazine, vol . 7, no. 5, pp. 28-34, Oct. 2000. [12] A . Savvides, C . - C . Han, and M . Srivastava, "Dynamic fine-grained localization in ad-hoc networks of sensors," in Proc. of ACM MobiCom, Rome, Italy, July 2001, pp. 166-179. [13] X . J i and H . Zha, "Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling," in Proc. IEEE Infocom, Hong Kong , China , March 2004, pp. 2652-2661. [14] V . Vivekanandan and V . Wong, "Ordinal MDS-based localization for wireless sensor networks," submitted to IEEE WCNC 2006. Bibliography 103 [15] V . Vivekanandan and V . Wong, "Concentric anchor-beacons ( C A B ) localization algorithm for wireless sensor networks," submitted to IEEE ICC 2006. [16] J . Hightower and G . Boriello, "Location systems for ubiquitous computing," IEEE Computer, vol . 34, no. 8, pp. 57-66, 2001. [17] N . Patwari , J . A s h , S. Kyperountas, A . Hero III, R. Moses, and N . Correal , "Locat-ing the nodes: Cooperative localization in wireless sensor networks," IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 54-69, Ju ly 2005. [18] A . Savvides, M . Srivastava, L . Gi rod , and D . Es t r in , "Localizat ion in sensor net-works," book chapter in Wireless Sensor Networks, Springer, 2005. [19] C . Savarese, J . Rabaey, and J . Beutel , "Location in distributed ad-hoc wireless sensor networks," in Proc. of IEEE ICASSP, Salt Lake Ci ty , U T , M a y 2001, pp. 2037-2040. [20] S. Capkun, M . Hamdi , and J.-P. Hubaux, "GPS-free positioning in mobile ad-hoc networks," in Proc. of Hawaii Int. Conf. on System Sciences (HICSS-34), M a u i , Hawaii , Jan. 2001. [21] A . Savvides, H . Park, and M . Srivastava, "The bits and flops of the n-hop multilat-eration primitive for node localization problems," in Proc. of ACM WSNA, At lanta , G A , September 2002, pp. 112-121. Bibliography 104 [22] C . Savarese, J . Rabaey, and K . Langendoen, "Robust positioning algorithms for distributed ad-hoc wireless sensor networks," in Proc. of USENIX Technical Annual Conference, Monterey, C A , June 2002, pp. 317-327. [23] D . Niculescu and B . Nath , "Error characteristics of ad hoc positioning systems ( A P S ) , " in Proc. of ACM MobiHoc, Roppongi, Japan, M a y 2004, pp. 20-30. [24] A . Nasipuri and K . L i , " A directionality based location discovery scheme for wireless sensor networks," in Proc. of ACM WSNA, At lanta , G A , September 2002, pp. 105-111. [25] N . Patwari and A . Hero I I I , "Using proximity and quantized RSS for sensor local-ization in wireless networks," in Proc. of ACM WSNA, San Diego, C A , September 2003, pp. 20-29. [26] C . L i u and K . W u , "Performance evaluation of range-free localization methods for wireless sensor networks," in Proc. of IEEE IPCCC, Phoenix, A Z , A p r i l 2005, pp. 59-66. [27] X . Cheng, A . Thaeler, G . Xue , and D . Chen, " T P S : A time-based positioning scheme for outdoor wireless sensor networks," in Proc. of IEEE Infocom, Hong Kong , China , March 2004, pp. 2685-2696. [28] S. Capkun and J.-P. Hubaux, "Secure positioning in sensor networks," in Technical Report (EPFL/IC/200444) Swiss Federal Institute of Technology Lausanne, M a y 2004. Bibliography 105 [29] N . Priyantha, H . Balakrishnan, E . Demaine, and S. Teller, "Anchor-free distrib-uted localization in sensor networks," in Technical Report 892 MIT Laboratory for Computer Science, A p r i l 2003. [30] L . H u and D . Evans, "Localization for mobile sensor networks," in Proc. of ACM MobiCom, Philadelphia, P A , Sept. 2004, pp. 45-57. [31] M . Sichit iu and V : Ramadurai , "Localizat ion of wireless sensor networks wi th a mobile beacon," in Proc. of IEEE MASS, Fort Lauderdale, F L , Oct . 2004, pp. 174-183. [32] K . - F . Ssu, C . - H . Ou , and H . J iau, "Localizat ion wi th mobile anchor points in wireless sensor networks," IEEE Trans, on Vehicular Technology, vol . 54, pp. 1186-1197, M a y 2005. [33] P. Pathirana, N . Bulusu, A . Savkin, and S. Jha, "Node localization using mobile robots in delay-tolerant sensor networks," IEEE Trans, on Mobile Computing, vol. 4, pp. 285-296, J u l y / A u g . 2005. [34] D . Lay, Linear Algebra and Its Applications, 3rd ed. Addison Wesley, 2003. [35] W . Hardle and L . Simar, Applied Multivariate Statistical Analysis. Springer-Verlag, 2003. [36] J . Kruskal , "Nonmetric multidimensional scaling: a numerical method," Psychome-trika, vol. 29, pp. 115-129, 1964. Bibliography 106 [37] J . Kruska l and M . W i s h , Multidimensional Scaling, ser. Sage University Paper series on Quantitative Applicat ions in the Social Sciences. Beverly Hil ls and London: Sage Publications, 1978, no. 07-011. [38] I. Borg and P. Groenen, Modern Multidimensional Scaling: Theory and Applications. New York: Springer, 1997. [39] J . Kruskal , "Analysis of factorial experiments by estimating monotone transforma-tions of the data," Journal of the Royal Statistical Society, vol. 27:2, pp. 251-263, 1965. [40] P. Groenen and M . VandeVelden, "Mult idimensional scaling," in Econometric Insti-tute Report EI 2004-15, A p r i l 2004. [41] G . X i n g , C . L u , Y . Zhang, Q. Huang, and R. Pless, " M i n i m u m power configuration in wireless sensor networks," in Proc. of ACM MobiHoc, New York, N Y , M a y 2005, pp. 390-401. [42] "Crossbow Technology," h t tp : / /www.xbow.com/ .
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Localization algorithms for wireless sensor networks
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Localization algorithms for wireless sensor networks Vivekanandan, Vijayanth 2006
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Localization algorithms for wireless sensor networks |
Creator |
Vivekanandan, Vijayanth |
Publisher | University of British Columbia |
Date Issued | 2006 |
Description | Many applications in wireless sensor networks require sensor nodes to obtain their absolute or relative geographical positions. Due to the size, cost and energy restrictions imposed by sensor nodes, only a few nodes can be equipped with the Global Positioning System (GPS) capability and act as anchors for the rest of the network. The algorithms based on classical Multidimensional Scaling (MDS) [1][2] only require three or four anchor nodes and can provide higher accuracy than some other schemes. In the first part of this thesis, we propose and analyze the use of ordinal MDS for localization in wireless sensor networks. Ordinal MDS differs from classical MDS by that it only requires a monotonicity constraint between the shortest path distance and the Euclidean distance for each pair of nodes. Simulation studies are conducted under square and C-shaped topologies with different connectivity levels and number of anchors. Results show that ordinal MDS provides a lower position estimation error than classical MDS in both hop-based and range-based scenarios. In the second part of this thesis, we propose a concentric anchor-beacons (CAB) localization algorithm for wireless sensor networks. CAB is a range-free approach and uses a small number of anchor nodes. Each anchor emits several beacons at different power levels. From the information received by each beacon heard, nodes determine which annular ring they are located within each anchor. Each node uses the approximated center of intersection of the rings as its position estimate. Simulation results show that the estimation error reduces by half when anchors transmit beacons at two different power levels periodically instead of at a single level. CAB also gives a lower estimation error than other range-free localization schemes (e.g., Centroid, APIT) when the anchorto- node range ratio is less than four. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-06 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0064953 |
URI | http://hdl.handle.net/2429/17613 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2006-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2006-0126.pdf [ 4.68MB ]
- Metadata
- JSON: 831-1.0064953.json
- JSON-LD: 831-1.0064953-ld.json
- RDF/XML (Pretty): 831-1.0064953-rdf.xml
- RDF/JSON: 831-1.0064953-rdf.json
- Turtle: 831-1.0064953-turtle.txt
- N-Triples: 831-1.0064953-rdf-ntriples.txt
- Original Record: 831-1.0064953-source.json
- Full Text
- 831-1.0064953-fulltext.txt
- Citation
- 831-1.0064953.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0064953/manifest