Localization Algorithms for Wireless Sensor Networks by Vijayanth Vivekanandan B . A . S c . , E l e c t r i c a l Engineering, University of B r i t i s h C o l u m b i a , 2003 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L M E N T OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in T H E F A C U L T Y OF G R A D U A T E STUDIES (Electrical and Computer Engineering) T H E UNIVERSITY OF BRITISH C O L U M B I A December 2005 Â© V i j a y a n t h Vivekanandan, 2005 ii Abstract M a n y applications i n 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 w i t h the G l o b a l Positioning System ( G P S ) capability and act as anchors for the rest of the network. T h e algorithms based on classical M u l t i d i m e n s i o n a l 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 i n wireless sensor networks. O r d i n a 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 E u c l i d e a n distance for each pair of nodes. Simulation studies are conducted under square and C-shaped topologies w i t h 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 i n 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. E a c h anchor emits several beacons at different Abstract power levels. iii F r o m the information received by each beacon heard, nodes determine which annular ring they are located w i t h i n each anchor. E a c h 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. C A B also gives a lower estimation error than other range-free localization schemes (e.g., Centroid, A P I T ) when the anchorto-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 2.1 6 Connectivity-Based Algorithms 7 2.1.1 Convex Optimization 7 2.1.2 MDS-MAP 9 Table of Contents 2.2 2.1.3 M D S - M A P w i t h Patches and Refinement (P, R ) 11 2.1.4 Anchor-Initiated M D S - M A P , O n - D e m a n d M D S 12 Range-Based Techniques 15 2.2.1 T E R R A I N using A B C 15 2.2.2 APS . 2.2.3 2.3 2.4 2.5 v ' 16 Self-Positioning A l g o r i t h m 18 2.2.4 A d - h o c L o c a t i o n System ( A H L o S ) .<.... 2.2.5 N-Hop Multilateration Primitive 2.2.6 H o p - T E R R A I N w i t h Refinement 2.2.7 A P S / H o p - T E R R A I N / N - h o p Multilateration Primitive 19 21 .' 23 25 Angle-Based Techniques 26 2.3.1 A P S using A O A 26 2.3.2 DV-position 29 2.3.3 Directionality L o c a l i z a t i o n 30 2.3.4 A d - H o c Ranging and Sectoring 31 Range-Free Techniques 32 2.4.1 Centroid 32 2.4.2 A p p r o x i m a t e d Point-in-Triangulation ( A P I T ) 34 Other Novel Techniques 36 2.5.1 Time-based Positioning Scheme T P S 36 2.5.2 Secure Positioning 38 Table of Contents 3 vi 2.5.3 Anchor-Free L o c a l i z a t i o n ( A F L ) 40 2.5.4 Sequential Monte Carlo Localization ( M C L ) 42 Ordinal Multidimensional Scaling 45 3.1 Motivations and Assumptions 45 3.2 MDS-MAP(P, O) A l g o r i t h m 47 3.3 Performance Evaluation and Comparison 51 3.3.1 R a n d o m Uniform Network Topology 52 Hop-Based Performance 52 Range-Based Performance 55 Sensitivity Analysis of Range E r r o r on Positioning E r r o r 57 Sensitivity Analysis of Anchors' L o c a t i o n on Positioning E r r o r . . 59 Further Improvement v i a (Optional) G l o b a l Relative M a p Refinement 61 R a n d o m Irregular Network Topology 63 Hop-Based Performance 64 Range-Based Performance 65 Further Improvement v i a (Optional) G l o b a l Relative M a p Refinement 67 3.3.2 3.4 Summary 69 4 Concentric Anchor-Beacons (CAB) Localization Algorithm 4.1 Motivations and Assumptions 4.2 C A B Algorithm 71 . 71 74 Table of Contents 4.3 Discussion 79 4.4 Performance E v a l u a t i o n 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 C e n t r o i d 88 4.5 4.6 5 vii C A B Extension to other L o c a l i z a t i o n Schemes 92 4.5.1 93 Possible Scheme-Specific Modifications Summary 95 Conclusions and Future Work 97 5.1 98 Future W o r k Bibliography 101 List of Tables 4.1 Information collected by a sensor from its anchors ix List of Figures 2.1 C o n n e c t i v i t y Constraints 8 2.2 Sequential localization from starting anchor ( A ) to ending anchor (D). . . 13 2.3 O n - D e m a n d positioning from node A to anchors D , H , L 14 2.4 D V Euclidean model 18 2.5 Collaborative M u l t i l a t e r a t i o n model 21 2.6 Nodes obtaining relative angle measurements to other nodes 27 2.7 L o c a l i z a t i o n using Angulations 28 2.8 D V - p o s i t i o n model 29 2.9 L o c a l i z a t i o n using synchronized, offset, rotating beacon signals 30 2.10 L o c a 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 w i t h degrees of freedom 41 2.15 Topology construction for fold-freedom 42 L i s 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 ) . . 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) 53 59 3.7 A n c h o r topology results of range-based M D S - M A P ( P , O ) . . . '. 3.8 Performance of hop-based M D S - M A P ( P , O) and 3.9 Performance of range-based M D S - M A P ( P , O) and M D S - M A P ( P , O , R ) . MDS-MAP(P, 0 , R). 60 . 61 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 ) i n 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 ) i n 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 xi 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 A n c h o r beacon transmission ranges w i t h 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 C o m p a r i s o n of percentage of nodes localizable versus percentage of anchors deployed for varying levels of A N R 4.5 82 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 C o m p a r i s o n 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 different D O I values 4.8 86 C o m p a r i s o n of estimation error using randomly heard anchors versus opt i m a l l y chosen anchors 4.9 87 Percentage of anchors deployed comparison between C e n t r o i d , A P I T , C A B E A , and C A B - E W 4.10 A N R comparison between Centroid, A P I T , C A B - E A , and C A B - E W . 89 . . 4.11 D O I comparison between C e n t r o i d , A P I T , C A B - E A , and C A B - E W . . . . 90 91 List of Abbreviations ABC A s s u m p t i o n Based Coordinates AFL Anchor-Free L o c a l i z a t i o n AHLoS A d - h o c L o c a t i o n System ANR Anchor-to-Node Range AOA Angle-of-Arrival APIT A p p r o x i m a t e d Point-In-Triangle APS A d - h o c Positioning System CAB Concentric Anchor-Beacons CAB-EA Concentric Anchor-Beacons w i t h E q u a l A r e a CAB-EW Concentric Anchor-Beacons w i t h E q u a l W i d t h DOI Degree of Irregularity DV Distance-Vector L i s t of Abbreviations EKF Extended K a l m a n F i l t e r GPS G l o b a l Positioning System LMI Linear M a t r i x Inequality LRG L o c a t i o n Reference G r o u p MCL M o n t e C a r l o Localization MDS M u l t i d i m e n s i o n a l Scaling PAV Pool-Adjacent Violators RSS Received Signal Strength SDP Semi-Definite P r o g r a m SMC Sequential Monte C a r l o TDOA Time-Difference-of-Arrival TERRAIN Triangulation v i a Extended Range and R e d u n dant Association of Intermediate Nodes TOA Time-of-Arrival TPS Time-based Positioning Scheme xiii xiv Acknowledgements I would like to express my sincere gratitude to my graduate supervisor D r . Vincent W o n g for his guidance and support during the course of my graduate studies. I appreciate the considerable amount of time and effort he invested i n helping me w i t h my research and thesis. Special thanks to Y i Shang, Wheeler R u m l , and Y i n g Zhang for providing us w i t h their software code for testing and modification. I would also like to thank my fellow colleagues who have provided helpful suggestions along the way. T h i s thesis could not have been completed without the endless encouragement and love from my family, I am deeply indebted to them. T h i s work is supported by the N a t u r a l Sciences and Engineering Research C o u n c i l of C a n a d a under grant number 261604-03. 1 Chapter 1 Introduction T h e m i n i a t u r i z a t i o n of small devices capable of sensing and communicating w i t h 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. T h e functions presented i n literature range from m i l i t a r y applications to wildlife monitoring. These applications propose of hundreds to thousands of sensors being dropped by airplane over a certain coverage area. T h i s type of deployment would require the nodes to configure their network by themselves. Such vast deployments would restrict the i n d i v i d u a l placement or programming of a l l nodes w i t h their unique locations, and hence some system must be i n place to accurately and efficiently localize these sensors. Thus, these sensor nodes have limited 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 i n 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 i n a multi-hop manner. T h e message needs to indicate the location of the node which detected the event. W h e n an event occurs (or a stimulus is detected), the sensor nodes can forward the data information along w i t h their coordinates. Thus, localization of sensor nodes is important in certain applications. 1.1 Motivations and Objectives T h e current location technology such as global positioning system ( G P S ) 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 i n sensor networks. In order to solve this dilemma, nodes i n the network must collaboratively execute an algorithm i n which the objective is to provide each node w i t h an estimate of its position i n the network. P o s i t i o n estimates may be based on a relative coordinate system w i t h i n the network, or an absolute geographical reference. A l t h o u g h , much research has been conducted i n 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 proposed recently. W i t h respect to robustness and energy efficiency, distributed algorithms are preferred over centralized schemes. T h e 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 ability to obtain distance estimates to other nodes. T h i s distance information can be obtained through various techniques involving specialized hardware. C o m m o n methods of measuring distance between wireless nodes include the use of received signal strength ( R S S ) , time-of-arrival ( T O A ) , and time-difference-of-arrival ( T D O A ) . In the R S S method, the measured R S S is converted to a distance estimate by using a predetermined path loss model and a reference distance of which the signal strength is known. T h e 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, reference 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. T h i s is achieved through the use of antenna arrays 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. E a c h anchor may be equipped w i t h 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 o p t i m a l scheme. For most of the performance comparisons reported to date, the common performance metric is the localization normalized error with respect to the radio range. T h i s metric depends on the node connectivity (density), anchor population, and the distance measurement error models. Thus, the m a i n objective of our work is to design an accurate localization algorithm which requires a small number of anchor nodes. T h e 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. F i r s t , w i t h 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. T h i s C A B scheme is proposed i n two different implementations using E q u a l A r e a ( C A B - E A ) and E q u a l W i d t h ( C A B - E W ) . T h e M D S - M A P ( P , 0 ) and C A B algorithms encompass the two different extremes i n the sensor localization problem and provide more accurate positioning of nodes than some other schemes proposed i n the literature. Chapter 1. 1.2 Introduction 5 Structure of the Thesis T h i s thesis is structured as follows. In Chapter 2, a literature survey of the various localization schemes previously proposed is presented. These previous schemes are arranged in a taxonomy that identifies the key features that distinguish certain schemes from others. A d d i t i o n a l schemes are included that provide insight into future research directions for localization i n sensor network, for completeness. Chapter 3 describes our proposed ordinal multidimensional scaling ( M D S ) scheme, complete w i t h : 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. T h e motivations and assumptions are stated, followed by a detailed explanation of the scheme. T h i s is then followed by a performance evaluation of the algorithm, a discussion of possible extensions and lastly a summary. T h e conclusion i n Chapter 5 outlines the m a i n contributions of the thesis, summarizes the localization area factors to be optimized and explains future trends i n the area. 6 Chapter 2 Related Work on Localization In recent years, the problem of localization i n wireless sensor networks have been attempted from many different points of view. M o s t of the previous works have made some assumptions on the environment of the networks that differ amongst others. T h i s has led to diverse techniques being used i n localization, such as the availability of careful placement of anchor nodes i n a network, the possibility of performing operations centrally and then propagating results back to the nodes. T h e 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 explored [4]. T h i s chapter introduces the key papers i n 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 i n 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 i n [3] [4] [16] [17] [18]. Chapter 2.1 2. Related Work on Localization 7 Connectivity-Based Algorithms T h e connectivity-based algorithms allow sensor nodes to obtain position estimates w i t h out the requirement of any range or angle measurement hardware. These algorithms rely on the information of which nodes are w i t h i n communication range of each other, and solve for positions using two similar mathematical approaches. T h e first proposed scheme is based on convex optimization, which is a centralized method. T h e 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 n o r m a l nodes. T h e anchor nodes are required to impose absolute position constraints on nodes, whereas normal nodes impose relative position constraints. T h e constraints are based on the maxi m u m range of communication between nodes, or measured range. If two nodes are able to communicate then, they each must lie w i t h i n each other's transmission range, hence defining a circular area of possible positions w i t h reference to each other. Additional connectivity w i t h other neighboring nodes reduces the possible position of a node to the intersection of the i n d i v i d u a l constraint sets, as seen i n Figure 2.1. These communication constraints imposed are convex and can be mathematically interpreted as linear m a t r i x inequalities ( L M I ) . T h e L M I are combined to form a semidefinite program ( S D P ) [5]. Semi-definite programs are generalizations of linear programs Chapter 2. Related Work on Localization 8 F i g u r e 2.1: C o n n e c t i v i t y Constraints, [5]. where the objective function is optimized subject to L M I s as opposed to linear inequalities. T h e 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 T h u s , constructing the connectivity constraints i n 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 S D P s . T h e 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. T h e nature of the model, requires that anchors be placed near the corners and edges of the network for o p t i m a l 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 i n more accurate estimates; however networks w i t h greater than 2000 nodes are deemed to be too computationally intensive Chapter 2. Related Work on Localization 9 to solve. 2.1.2 MDS-MAP 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 i n order to visualize their relationship based on similarity or dissimilarity measures. These measures are treated as distance-like d a t a and used to construct the model, where m objects can be placed in ndimensional space i n order to satisfy the data. However i n order to visualize and interpret the data, usually a 2D or 3 D embedding of the objects is desired. Several different types of M D S techniques exist. If distance-like measures are available, then Metric used. If only ordered relationships exist (i.e. MDS is distance between objects A and B is greater than distance between objects A and C ) , then Non-Metric applicable. Other types of M D S include Probabilistic (Ordinal) MDS is MDS where objects are placed i n 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 M e t r i c scaling technique), to solve for the positions of the sensor nodes in the 2 D case. T h e M D S result is the optimal least squares configuration to satisfy the distance constraints between the nodes. T h e nature of M D S is similar to that of convex optimization, where constraints between nodes are used to obtain a satisfactory solution. T h e difference between metric M D S and convex optimization lies i n the fact that i n Chapter 2. Related Work on Localization 10 convex o p t i m i z a t i o n the constraints limit the m a x i m u m distance between two nodes, whereas M D S does not. T h e m a i n drawback of M D S is the fact that it is a centralized scheme. T h e M D S - M A P algorithm described i n [1] is as follows. First, the shortest paths between a l l nodes i n the network are computed. These distances are used to b u i l d the m a t r i x used by classical scaling to perform M D S , i n obtaining the relative positions between all nodes. Lastly, i n 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 i n Section 2.1.1, anchors as well as nodes were randomly placed i n the square coverage area. Results showed that w i t h fixed range information (i.e. no distance information between nodes) the error was 46% of the range, whereas w i t h range information the error reduced to 24% [1]. T h i s was obtained w i t h 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, w i t h connectivities greater than 6, more than 93% of a l 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 i n a grid-like fashion w i t h various placement error models. Chapter 2.1.3 2. Related Work on Localization 11 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 i n the algorithm by incorporating a refinement scheme to further improve position estimates of nodes [2]. Whereas the work i n [1] introduced a centralized M D S - M A P scheme which d i d not perform well i n irregular shaped networks (i.e. nonsquare coverage areas), the new distributed method i n [2] is aimed at improving the M D S performance i n order to make it more robust under different network scenarios. T h e 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. T h e size of the local maps is controlled by the hop count parameter, where nodes only consider other nodes that are w i t h i n the specified number of hops from their location. First, each node determines which nodes are w i t h i n its local map. T h e n , as i n centralized M D S , the shortest p a t h distances between all nodes in the local map are computed, and M D S is performed on the constructed distance m a t r i x . T h e n , a refinement procedure is used to perform the leastsquares m i n i m i z a t i o n 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 m i n i m i z a t i o n refinement is also performed on the global map. L a s t l y the map is converted to an absolute map by transformation using three or more anchor nodes i n the entire network. T h e 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. T h e size of the local maps is determined by the complexity of the M D S calculation. For random networks w i t h 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 connectivity only information and less than 20% of radio range for distance information [2]. T h e drawback of this approach is the significant refinement computation time, the propagation 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. C o m p a r e d to other schemes, this algorithm is more robust under irregular topologies and more accurate for the low percentage of anchors present i n the system. 2.1.4 Anchor-Initiated M D S - M A P , On-Demand M D S In [13], J i and Z h a proposed a distributed M D S scheme in order to localize nodes i n a sensor network, using the classical M D S algorithm. A l s o , 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 i n the network are obtained sequentially as the algorithm starts. One anchor named starting anchor node i n the network will flood its position to the network for other anchors named ending anchors to receive and reply back w i t h 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 i n order to determine anisotropic environments i n different directions of the network. T h u s , 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]. T h e n , 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 i n the local map and aligned relative to the previously estimated positions of the nodes on the path. T h i s sequential localization proceeds down the path to the ending anchor, resulting i n a l l positions on the path and one hop away from the path being localized as i n Figure 2.2. Nodes further away are localized using pairwise distances to 3 or more nodes that are already localized, and nodes w i t h only two localized neighbors perform iterative M D S to compute position estimates. T h e 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 i g u r e 2.3: O n - D e m a n d positioning from node A to anchors D , H , L , [13] measurement error, i n a randomly deployed square coverage area. In a square region w i t h different radio ranges i n different areas, the accuracy degrades to less than 35%, which proves that this algorithm is robust i n dealing w i t h anisotropic environments. T h e ondemand 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. T h e initial 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. T h e n , 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 initial node for an accurate position estimate as i n 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.2 2. Related Work on Localization 15 Range-Based Techniques Range-based techniques make extensive use of the distance information to obtain position estimates of the sensor nodes. T h e algorithms presented i n this section show many different approaches to the node localization problem, but have inherently similar architectures i n 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. T h e 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 i n order to more accurately position a l l of the nodes from a d d i t i o n a l information such as inter-node distances and positions. T h o u g h quite a few exhibit this architecture, others exhibit other novel schemes that i n 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. T h e i r model assumed a dense distribution of sensor nodes accompanied by a small number of anchors,(e.g., four were used in simulation). U p o n random sensor deployment, the sensor nodes have the additional capability to vary their transmission power i n order to remain well connected w i t h the network. Hence, the sensor nodes can themselves control their level of connectivity w i t h the network, a unique assumption. T h e first function which T E R R A I N (Triangulation Chapter 2. Related Work on 16 Localization v i a E x t e n d e d 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. T h e first node that sends its ranging estimate to this node is placed on the x-axis at the range estimate value. T h e second node's position in the coordinate system is explicitly solved using the range estimates to the original two nodes and placed i n the positive y-axis coordinates. Further nodes are then placed i n the relative system from their range estimates to existing nodes. T h i s function thus iteratively 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 i n the system. Once sensor nodes receive the propagated distance measurements from the four anchors, the least-square lateration is performed to obtain i n i t i a l position estimates. T h e n , a-refinement scheme called Iterative L o c a l Triangulation is performed locally between every node and its immediate one-hop neighbors. E a c h node uses the neighbors' position estimates and range measurements to the neighbors to locally laterate its position. T h i s procedure, after many iterations, should result in nodes positions remaining fixed. 2.2.2 APS In the A d H o c Positioning System ( A P S ) developed by Niculescu and N a t h [6], a similar approach to T E R R A I N is used without a refinement procedure. T h e i r approach to the position problem uses an aspect of distance vector ( D V ) 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 w i t h a hop count value of one. E a c h one-hop neighbor of the anchor receives the packet, stores it i n memory and creates a new packet w i t h the anchor position and a hop count value of 2. It then forwards it to a l l of its one-hop neighbors. T h u s a l 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. W h e n anchors receive information about other anchors, an average hop size is calculated, by computing the distance between the two anchors, and d i v i d i n g it by the respective hop count. T h i s average hop size is then propagated to the other nodes, so as to provide the nodes w i t h range estimates to the anchors by m u l t i p l y i n g 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. T h e D V - D i s t a n c e 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]. T h u s , instead of forwarding hop count values, the sum of the distances originating from the anchors is propagated to a l l nodes, providing range estimates directly as opposed to m u l t i p l y i n g hop counts by average hop distances. T h e t h i r d A P S scheme is the D V - E u c l i d e a n which uses geometric quadrilateral properties to position nodes, one at a time. A s shown i n 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 E u c l i d e a n distance to the anchor L, and hence position itself between two possible Chapter 2. Related Work on Localization 18 F i g u r e 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, D V - E u c l i d e a n performed the best w i t h errors of less than 50% of radio range, w i t h 20% anchors and 10% range estimation error. T h e D V - H o p / D i s t a n c e schemes performed well at relatively low connectivity (7), and isotropic environments w i t h error less t h a n 30% of radio range, 20% range estimation error, 20% anchors. T h e m a i n 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 i n 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. T h e n , this information is sent to a l l of the one-hop neighbors, essentially providing every node w i t h information of up to a two-hop neighborhood. E a c h node then assumes itself as the center of the system, and sequentially places a l l nodes it has information for, into its coordinate system, as i n A B C . A t this point, a l l nodes have placed their one and two-hop neighbors i n Cartesian coordinates centered upon themselves. A s opposed to aligning a l 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 Location Reference G r o u p ( L R G ) of nodes are chosen, of which a coordinate system is developed as the m a i n system to which a l l network nodes must align to. T h i s is used to enable the presence of mobile nodes i n the system. However it comes at the cost of extensive communication and d a t a exchange. 2.2.4 Ad-hoc Location System (AHLoS) T h i s 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. T h e design goals included the ability for the network to be deployed indoors or outdoors, decentralized and use maximum-likelihood estimation of node positions. T h e 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 . T h e 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 multilateration approach is used. In this approach, nodes that are unable to perform atomic multilateration wait until other nodes have obtained their positions. Thus, those nodes that are successful w i t h atomic multilateration behave as anchor nodes. T h e remaining nodes then use the presence of traditional anchors w i t h these newly positioned anchors to perform multilateration. T h i s iterative scheme, will thus gradually resolve the positions of the majority of nodes i n the network. T h e drawback i n this scheme is the potential error propagation by using approximated anchors i n iteratively solving node positions. Lastly, collaborative multilateration is used i n 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 i n 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. O f course, some nodes may not be able to position Chapter 2. Related Work on Localization E 21 C D F F i g u r e 2 . 5 : Collaborative M u l t i l a t e r a t i o n model, [12]. themselves at a l l if they have less than three neighbors, as the position w i l l have ambiguity, the algorithm includes a test of participating neighbors to identify if collaborative multilateration can be used or not [12]. T h e m a i n drawback of this approach is the relatively high percentage of anchors needed in the system to provide sufficient accuracy. T h i s requirement can only be avoided by increasing the node density i n the network that w i 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 multilateration approach as introduced i n [12]. A n c h o r nodes are either placed i n 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 constructed 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. T h e search for the possible uniqueness of the node extends from one-hop to two-hops to n-hops, i n 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. T h e conditions for this uniqueness are summarized i n the following rules. 1. A unique solution exists if the node has three neighbors w i t h uniquely possible solutions. 2. T h e neighbors must not be co-linear, since this would result i n 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. T h e second phase, obtaining initial position estimates, uses bounding boxes to set the extreme possible locations of the node. T h e bounding box is constructed by taking the strictest constraints on node positions by the reference neighbor nodes determined i n the collaborative subtrees algorithm. T h i s approach is used as opposed to direct lateration due to its computational simplicity. T h e 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 i n the static network case. T h i s refinement is performed distributively using approximated methods that control the global solution Chapter 2. Related Work on Localization 23 of each subtrees i n order to reach global m i n i m a and obtain accurate positions. A f ter this procedure, nodes previously excluded in phase one are solved for using atomic multilateration. T h e drawbacks of this scheme are the extensive computations i n the refinement scheme, and its rapid increase i n error w i t h increased network size, i n 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, H o p T E R R A I N w i t h Refinement [22] is an amalgamation of both schemes. A s the name suggests, two phases are present i n the scheme, and initial start-up phase followed by a refinement step. T h e design of this system assumes a very low percentage of anchors, w i t h at least four being required i n the network. T h e other m a i n goal is to avoid the inaccurate ranging errors typical of R S S based approaches i n obtaining positions estimates. The result is the use of anchors propagating their positions to a l l nodes, w i t h 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 i n A P S . T h i s average distance is propagated throughout the network as i n A P S . T h e difference in this implementation, however, is that once a node receives information about average hop distance, it uses the information for a l l hop measurements to the anchors it knows, not only for the anchor that sent the information. T h i s 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 i n i t i a 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 i n i t i a l estimates. After this initial startup phase, a l l nodes w i l l have position estimates. T h e refinement procedure consists of nodes exchanging initial positions w i t h neighbors and obtaining range estimates to neighbors through a ranging technique. T h e n nodes perform local least squares lateration to improve initial position estimates. In addition, all nodes contain confidence weights indicating the certainty of their position estimate [22]. A n c h o r nodes have weights of 1.0 while other nodes have weights equal to the average of the weights of the surrounding neighbors. T h u s nodes closer to anchors have higher confidences i n their positions than others. Lastly, nodes that have confidence levels less t h a n 0.1 are regarded as unpositionable. Other constraints are used to make sure refined positions meet the i n i t i a l communication constraints imposed by the anchors estimated distances, and hence have not diverged during refinement. In general, the refinement scheme improves the initial 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. T h i s scheme has proved to be more accurate i n lower connectivities compared to other schemes, and achieves performance comparably at high connectivities w i t h others. Chapter 2. Related Work on Localization 2.2.7 25 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. T h e authors identify the key similarities i n the schemes as the 3 phases being incorporated i n each. F i r s t , distances between nodes and anchors are obtained. T h e n , the i n i t i a l estimates are computed. Lastly, a refinement is performed to achieve more accurate results. In the i n i t i a l phase, three possibilities are available as proposed by A P S : D V - H o p , D V - d i s t a n c e and D V - E u c l i d e a n . T h e second phase has two options, lateration previously used by A P S and H o p - T E R R A I N , and m i n - m a x the bounding box scheme used by the N - h o p primitive. Refinement was used as the t h i r d phase. T h e results from the simulations of the different combinations of the three phases provided several conclusions. In the first phase, D V - d i s t a n c e always overestimated distances to anchors, D V - H o p is immune to range error but does not perform well under irregular topologies, and lastly D V - E u c l i d e a n rapidly decays as range errors increase. In the second phase, lateration is better than m i n - m a x for precise range measurements but more computationally intensive than min-max. In addition, m i n - m a x requires anchor nodes to be located at edges for better performance. T h e combinations of D V - d i s t a n c e 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, i n 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 m e d i u m connectivities (less than 15) D V d i s t a n c e / M i n - M a x is superior. A t high connectivities D V - d i s t a n c e / L a t e r a t i o n performed well. D V - E u c l i d e a n was only worthwhile at zero range measurement errors and connectivities larger than 14. T h e m a i n 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 i n triangulation, the counterpart of trilateration. T h o u g h range-based techniques have been extensively proposed, several algorithms using some angle measurements have been proposed. 2.3.1 APS using AOA T h e extension of the A P S scheme to involve the use of angle-of-arrival ( A O A ) measurements at the nodes has been implemented i n [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 F i g u r e 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 N o r t h direction, and hence behave as compasses for the nodes, the localization is even easier, as shown i n Figure 2.6. T h e 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 i n Figure 2.7. T h e mathematical solution of triangulation is transformed into a trilateration problem and solved using the least-squares algorithm. If nodes' headings are relative to N o r t h , 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 B O W 28 c(* y ) cJ c F i g u r e 2.7: Localization using Angulations, [8]. T h e two schemes proposed are D V - B e a r i n g 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). T h i s distinction is made when the headings of the nodes are not absolute (i.e. relative to N o r t h ) . If they were absolute, then the information would be redundant. T h e 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 w i t h anchor neighbors obtain bearings or radials to the anchors, them. T h i s information is propagated to other nodes, which are then able to obtain bearings/radials to the anchors as well. However, i n 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. Finally, once nodes have bearings/radials to three anchors, they can compute their positions. T h e increased need of neighbors w i t h measurements to the same anchor, increases the node connectivity to 9 or greater for A O A to produce sufficient results. T h e errors present in this system are inherent i n the degree of accuracy i n small angles as opposed to large ones. O f 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: D V - p o s i t i o n model, [23]. anchors needed, and obtains better accuracy than D V - B e a r i n g . 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 N a t h includes b o t h range and A O A measurements, and allows nodes to position themselves i n one step if anchors have headings relative to N o r t h [23]. A s shown i n 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 N o r t h , then the equation of the line connecting A and B can be computed. In addition, range information between A and B w i l l select one point on the line, corresponding to node A ' s position. T h i s is an example of m u l t i m o d a l sensing, that combines two techniques of measurement to provide less requirement i n terms of cooperation w i t h other nodes, at the cost of additional sensor hardware. T h i s scheme is o p t i m a l at anchor percentage of 10%, node Chapter 2. Related Work on Localization 30 F i g u r e 2 . 9 : Localization using synchronized, offset, rotating beacon signals, [24]. connectivity higher than 6 , w i t h 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. A l s o , 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 T h e directionality localization algorithm [24] employs the use of at least three fixed highpowered directional anchors placed at the corners of a sensor network. It is assumed that a l l nodes i n 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 w i t h a fixed angle offset from each other, as shown i n Figure 2.9. Chapter 2. Related Work on Localization 31 Nodes must be able to distinguish between the beacons received from the different anchors. T h e algorithm begins w i t h each sensor node noting the times at which it receives each signal from the specific anchors. T h e 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. T h e n the location of the node can be determined using two of the angles and the positions of the anchors using trigonometry. Simplistic i n nature, the complexity i n the anchors is offset by the simplicity 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 m u l t i p a t h reflections, no line of sight between a l l 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 m u l t i m o d a l sensing i n order to solve the nodepositioning problem is proposed by C h i n t a l a p u d i et al. [9]. T h e authors proposed this scheme by pointing out that range-based schemes by themselves require much higher connectivities than needed i n general for the sensor network to perform its actual sensing function. F r o m the schemes presented i n section 2.2, one can see that position errors less than half the radio range typically require connectivities greater than 9. C h i n t a l a p u d i et al. state it is unacceptable to deploy so many extra nodes just to obtain the nodes' positions. T h e y 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 m i n i m u m . B y using range and sectoring this requirement can be alleviated, to needing only one neighbor that has positioned itself, as explained in D V - p o s i t i o n . T h u s the scheme proposed is similar to iterative multilateration, but i n 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. T h e results show that for sectors as large as 60 degrees, w i t h node connectivity of 5 and 20% anchors, more than 90% of network nodes are localized w i t h 6% localization error [9]. These results are the most accurate of a l 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 B u l u s u et al, proposed a simple, cost effective, R F - b a s e d positioning method called Centroid i n [11]. B y design, the technique is classified as coarse grained since it computes localization using p r o x i m i t y methods and simple averaging to compute the centroid location. Fine-grained localization, i n 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 i n a symmetric grid pattern. T h e transmission range by the anchors is assumed to be greater than those by n o r m a l sensor nodes, similar to the A P I T [10] algorithm. T h e coverage areas by each beacon overlap, providing sensors w i t h the ability to hear several beacons from different anchors at any location i n the coverage area. T h e anchors are synchronized to transmit one beacon d u r i n g a specified time slot of a period T of system operation. T h u s , 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 w i t h i n range, if the node receives more than a threshold number of beacons during the listening period from the anchor. T h e position of the node is then calculated as the average of the coordinates of each anchor w i t h i n range, and hence is noted as the centroid or center of the anchors' positions. T h e scheme enables sensors to operate w i t h m i n i m u m power consumption as no communication is needed w i t h other nodes, and very little computation is required. However, the density of the anchors i n the coverage area determines the accuracy of the scheme. In addition, the deployment of anchors i n an ad-hoc manner, severely affects the positioning accuracy as well. T h e synchronization of the anchors may be unreasonable for large-scale deployments. Chapter 2. Related Work on Localization 0 0 0 0 U 0 131 Â§31 â€¢21 0 2.4.2 0 0 0 o 0 lip pr 0 ,0 0 0 0 -1 0 0 -V;v - l 0 -h -1 â€¢ 2 J â€¢21 | R | flf 0 F i g u r e 2.10: 0 0 0 HI E l 0 0 121 *1 0 â€žâ€žâ€žl,^.â€ž 0 ,0 0 0 0 0 0 -râ€” . i 0 0 0 0 0 0 0 -i: 0 0 34 0 L o c a l grid maintaining overlapped triangle regions for localization, [10]. Approximated Point-in-Triangulation (APIT) A P I T [10] is range-free and does not require any additional hardware for sensor nodes. T h e design goals included performing under irregular radio patterns and having low communication overhead. T h e scheme assumes the availability of high powered anchors that are able to transmit much greater distances than n o r m a l sensor nodes. T h e m a i n algorithm employs a unique test for localization, the Point-in-Triangulation ( P I T ) comparison [10]. E a c h node is assumed to be able to hear many anchors (much greater than 3) and the connectivity is assumed to be higher than 6. T h e P I T comparison tests if a node is located w i t h i n each triangle formed by combinations of 3 anchors heard. A grid is maintained w i t h positions i n the grid satisfying the P I T test being incremented while those outside being decremented, as shown i n Figure 2.10. After considering a l l combinations of anchors heard, the grid points w i t h the highest values determine the position of the node. A node is located w i t h i n a triangle of anchors Chapter 2. Related Work on Localization 35 F i g u r e 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 a l l three anchors. T h i s 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 a l l anchors at the same time. T h i s is the A p p r o x i m a t e d P I T ( A P I T ) test as shown i n Figure 2.11, which does have several degenerate cases that only account for 14% of the deployments actually being affected by the error. T h o u g h distance measurements are not used, each node i n a table maintains the received signal levels of the anchors. E a c h node maintains its table and exchanges it w i t h the neighbors so that a l l nodes have information of the one-hop neighborhood. T h e n A P I T looks at a column to determine if a l l the nodes w i t h the same three anchors lie w i t h i n the triangle, (i.e. the signal levels at a l l three anchors are not simultaneously greater or smaller t h a n the nodes' levels). A l l combinations of anchors are examined and then the grid array is constructed w i t h 0.10 radio range blocks. T h e position is then determined to be the center of the highest valued points area. T h e 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 T h e 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. T h e work i n [25] considered the possibility of quantized received signal strength (RSS) and presented mathematical analysis of the accuracy w i t h varying levels of quantization. T h e performance comparisons between R O C R S S I and A P I T schemes are given i n [26]. 2.5 Other N o v e l Techniques Other schemes exist that cannot be classified solely as one of the type of schemes mentioned 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 Positioning Scheme ( T P S ) [27]. In this scheme no time-synchronization is required between anchors. T h e anchors are deployed outside of the coverage area, enclosing the area i n a triangular geometry, as shown i n Figure 2.12. T h e anchors' transmission range is large enough to cover the entire area, hence any node w i t h i n the coverage area w i l l be able to hear a l l three beacons from the anchors. First, anchor A sends a beacon to the area. W h e n anchor B hears the beacon, it sends Chapter 2. Related Work on Localization 37 F i g u r e 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. T h e n 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 i n the area, and the nodes w i l l maintain local time information of when the packets from the anchors are received. T h i s constitutes one beaconing period for the system. T h i s 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. T h e accuracy of the position depends on the accuracy of the t i m i n g measurements, and can be improved merely by nodes averaging their results over several beaconing intervals. Errors presented i n the system include system delay i n reception and transmission of beacons, non line-of-sight transmission and m u l t i p a t h 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 a l 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 C e n t r o i d . T h i s 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. T h u s , this is a fine-grained scheme as distance measurements are used as well as the anchor positions. T h e 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 i n the node localization problem, is the security of the network and its communications, i n the event of it being deployed i n a hostile environment as suggested i n many papers. In [28], several methods of obtaining sensor locations i n a secure manner are employed. T h e threats inherent i n a sensor network include the removal of sensors, m a n i p u l a t i o n of sensors and the compromise of the system. 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 d a t a is sent to is also assumed to be secure. In addition, the central system is able to maintain the location of all unique sensors i n the system. T w o notions considered are the introduction of malicious and compromised nodes i n the system. Malicious nodes are controlled by attackers, but the central authority is aware of the malicious nodes. C o m p r o m i s e d nodes, however, Chapter 2. Related Work on Localization â€¢ Sensor â€¢ Anchor 39 F i g u r e 2.13: Sensor coverage model, [28]. are controlled by the attackers and are thought to be n o r m a l nodes by the system. T h e attacks considered to be possible include: displacement of a node, introduction of a wormhole, 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 i n conjunction w i t h node localization algorithms previously proposed in the literature. In the authenticated distance estimation method, nodes communicate using cryptographic keys i n order to obtain distance estimates to each other. A n o t h e r 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 i n the sensor system using anchors deployed i n a gridlike fashion consisting of triangles, as shown i n Figure 2.13. Sensor nodes obtain position estimates by the methods previously mentioned. Since anchors are tamper proof, they w i l l be able to obtain true distances to a l l nodes enclosed i n 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. T h e algorithm determines the position of a node by observing its placement w i t h i n a series of triangles enclosed by other nodes. However, i n the case where more than one node is malicious or compromised, the system is subject to unreliable information. Results show that i n 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) T h e Anchor-Free Localization ( 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. T h e algorithm, implemented without the use of anchors results i n 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. T h i s scheme has two phases: fold-free embedding, and mass-spring optimization [29]. T h e objective of the first phase is to produce a map of the network that looks similar to the actual network topology. T h i s approach is emphasized as important i n order for the second phase to reach a glob- Chapter 2. Related Work on Localization not r i g i d rigid 41 globally r i g i d F i g u r e 2.14: Different configuration w i t h degrees of freedom, [29]. ally o p t i m u m solution that matches the actual topology. Previous methods of building local coordinate systems and aligning them, sometimes fall into obtaining local m i n i m a solutions and result i n topologies that match distances between nodes but fail to produce topologies matching the actual case. T h e 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. T h e 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. T h e n a l l other nodes use estimated distances to these 5 points (excluding starting node), to'place them i n the coordinate system using polar coordinates i n Figure 2.15. T h e resulting embedding is usually larger than the actual topology, which aids i n the avoidance of local m i n i m a . T h e second phase consists of nodes broadcasting their Chapter 2. Related Work on Localization 42 ri3 F i g u r e 2.15: Topology construction for fold-freedom, [29]. estimated positions to neighbors, and calculating estimated distances to neighbors using the aforementioned data. C o m p a r i n g estimated distances w i t h actual measured distances, the second phase optimizes the estimates of the first phase iteratively by estimating node positions that reduce the overall network error, until a solution is reached analogous to a mass-spring system [17]. T h e robustness of the scheme, lies i n the fact that even at low connectivities A F L is successful i n 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], i n which a l l nodes are mobile. T h e i r approach is based on the assumptions that no distance measurements can be made by nodes, anchor densities are low and nodes are deployed i n an ad-hoc manner. T h e 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. T h e 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. T h e second step, involves the node using new information gathered after movement to eliminate previous prediction that do not correspond w i t h the new data. T o counteract the reduction of valid samples, resampling is performed to maintain a discrete number of samples for the posterior d i s t r i b u t i o n of node location. The restrictions imposed i n the first step, is due to the speed of the node, assuming constant speed v, the location of a node given a initial starting point will be w i t h i n a circle of radius v*t, where t is the time from initial start [30]. T h u s , the location is randomly picked w i t h uniform distribution w i t h i n the circle. Nodes, using information of which anchors were w i t h i n range i n the previous time, and which anchors are now w i t h i n range after movement, w i l l refine the samples generated from before. In addition, nodes share w i t h neighbors, the anchors that are w i t h i n communication range, to provide further identification data. F r o m 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 i n obtaining accurate position estimates. T h e last result is due to the fact that Chapter 2. Related Work on Localization 44 faster speed result i n much more information on which anchors are w i t h i n communication range of which nodes at certain times, resulting i n 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. M u l t i p l e mobile anchors are used i n [32]. In [30], b o t h anchors and sensor nodes are mobile. T h e Monte C a r l o algorithm is used for localization. In [33], an extended K a l m a n filter ( E K F ) - b a s e d state estimator is used i n tandem w i t h mobile robots for localization. 45 Chapter 3 Ordinal Multidimensional Scaling In this chapter, we propose the implementation of ordinal MDS for localization i n 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. W e 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 A s s u m p t i o n s T h e advantage of M D S localization algorithms is the relative low percentage of estimation error while using a small number of anchor nodes. T h e 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 d y , then dij = mpij + c for some constants m and c. uses singular value decomposition nodes. Classical M D S [34] to determine the relative coordinates of the sensor Chapter 3. Ordinal Multidimensional Scaling 46 A s mentioned i n Chapter 2, previously proposed localization algorithms based on classical Multidimensional Scaling ( M D S ) [1] [2] [13] have proven to be robust w i t h respect to both hop-based and range-based implementations. O n l y three or four anchor nodes are necessary to determine the absolute locations, i n two or three dimensions, respectively. These M D S algorithms achieve a higher accuracy than some other schemes. B y using the similar terminology i n [1], the term M D S - M A P ( C ) is used for the classical M D S localization algorithm. T h e 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 i n sensor networks. Our proposed scheme i n 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. T h e m a i n difference between classical M D S and ordinal M D S is that the former assumes there is a linear equation which relates the shortest path distance and the E u c l i d e a n distance between each pair of nodes, the latter simply assumes a monotonicity constraint. T h a t 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 E u c l i d e a n distance of (i, j) is also greater than that of (k, I), and vice versa. Chapter 3.2 3. Ordinal Multidimensional Scaling 47 M D S - M A P ( P , O) Algorithm T h e major steps of the M D S - M A P ( P , 0 ) algorithm are as follows: 1. E a c h node first gathers either the distance (for range-based) or hop count (for hop-based) information w i t h i n its two-hop neighborhood. 2. In each node, the Dijkstra's algorithm is invoked to determine the shortest path between each pair of nodes w i t h i n the two-hop neighborhood. We use the notation Pij to denote the shortest path distance between nodes i and j. 3. T h e ordinal MDS algorithm is applied to create the relative local map for each node. 4. E a c h local map is refined by using the least-squares minimization between the calculated Euclidean distance and the measured distance (or hop) between each pair of neighboring nodes. 5. T h e local maps are then patched (or merged) into a global map by using a predetermined initial starting node's local map and sequentially adding each neighbor that has the largest number of common nodes to the starting node. T h i s map then grows u n t i l a l l nodes have been included. 6. T h e 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 i n 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 ) . Step (3) has a complexity of 0 ( M ) . Steps (5) and (6) 3 have a complexity of 0(K 4 N) and 0(A T h e ordinal MDS algorithm 3 + N), respectively. (step (3) above) is now describe i n detail. T h e major steps of the ordinal MDS algorithm are as follows [35]: 1. Assign arbitrary initial location estimation ( x Â° , yÂ°) for i 6 M, where M includes all the nodes w i t h i n 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?-yj) 2 (3.1) 3. B y using the matrices [p^] and [dâ„¢], apply monotone regression by using the pooladjacent violators (PAV) algorithm [35] to determine [d^]. For example, once the P y ' 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 a l l Chapter 3. Ordinal 'Multidimensional 49 Scaling grouped and averaged together, as per the P A V algorithm, to maintain monotonicity 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 w i t h i n 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 2 ' (3.2) 13) 7. If Stressl < e, stop. Otherwise, go to Step (3). In the above algorithm, the first two steps calculate the E u c l i d e a n distance from an arbitrary initial configuration. Step (3) determines the disparities d?- by constructing a monotone regression relationship [38] between p^-'s and c P ' s . Step (4) updates the Chapter 3. Ordinal Multidimensional Scaling 50 relative positions. T h e parameter a is the step w i d t h . We use a = 0.2 as suggested by K r u s k a l [39]. Step (5) updates the E u c l i d e a n distance. T h e Stressl measure i n step (6) determines whether or not the updated values fit the given dissimilarities aâ„¢' . Note 1 that other goodness fit tests (e.g., K r u s k a l ' 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. T h e M D S - M A P ( P , 0 ) algorithm assumes that there is a monotonic relationship between the shortest p a t h distances and the actual E u c l i d e a n distances. T h i s 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., w i t h a high connectivity or average node degree) in order to provide redundancy and robustness i n case of a node's failure. In addition, i n our distributed approach, only the nodes w i t h i n 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 i n m i n i m i z i n g stress i n equation (3.2), the final solution may not guarantee to be the global m i n i m u m [40]. In fact, the ordinal M D S algorithm can have several local m i n i m a . However, the use of the anchors i n our application of the ordinal M D S algorithm increases the likelihood of reaching the global m i n i m u m . T h i s is due to the imposed transformation required to obtain the Chapter 3. Ordinal Multidimensional Scaling 51 absolute coordinates for a l l of the nodes. A n o t h e r way to further increase the chance of reaching the global m i n i m u m is by using the multiple starting configurations approach and retaining the configuration which results i n the lowest stress value. However, this approach is inefficient due to the additional computation effort required. 3.3 Performance Evaluation and C o m p a r i s o n 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 i n M a t l a b by [2] were modified to implement ordinal MDS. T w o different topologies are considered as the sensor network's coverage area. T h e first one is a uniformly distributed square region. T h e second is an irregular C-shaped topology. In both topologies, the average connectivity levels (i.e., average number of neighboring sensors) are varied along w i t h the number of anchors i n the area. T h e average connectivity level is varied between 9 and 21 by modifying the radio range R, w i t h i n 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 w i t h i n a square coverage area to increase the robustness of the sensor network. In the simulations, either 160 or 200 sensor nodes were used. T h e number of anchors is between four and ten. Although 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 i n this m i n i m a l case has a significant impact on the estimation error. T h u s , it is recommended that a m i n i m u m 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 i n M D S - M A P ( P , O ) , the hop count values are blurred w i t h noise so that nodes w i t h identical hop count values to neighbors are not co-located. In the range-based scenarios, the range is modelled as the actual distance combined w i t h Gaussian noise. Thus, the range is a random value drawn from a normal d i s t r i b u t i o n w i t h actual distance as mean and variance of 5%. T h e 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 l O r square topology was used, where r represents the reference unit length. A n c h o r nodes are placed randomly w i t h i n 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. T h e hollow circles represent the actual positions. T h e lines indicate the amount of error of the estimated positions. T h e filled circles represent the location of Chapter (a) 0 3. MDS-MAP(P.C), 2 4 Ordinal Multidimensional (b) (error=0.47R) 6 8 10 Scaling 53 M D S - M A P ( P . O ) , (error=Q.42R) 0 2 4 6 8 1 0 F i g u r e 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 ) i n a 10T X l O r square network region employing uniform random placement of 200 nodes w i t h connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. E s t i m a t i o n error is represented by lines. the 4 anchors. T h e 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. M o s t of them have small estimation error while a few of them may have higher estimation error. T h e 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. T h i s can be attributed to the fact that the ordinal algorithm iteratively improves the i n i t i a l random topology estimate thereby i m p r o v i n g the goodness fit of the ordered distances w i t h i n 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 (a) 4 anchors â€” (b) 6 anchors â€” â€” MDS-MAP(P.C) MDS-MAP(P.O) 60 ~ 10 Node " 8 en o t 50 â€” â€” â€” MDS-MAP(P.C) w MDS-MAP(P.O) 40 15 20 Connectivity 10 Node (c) 8 anchors â€” 54 Scaling 15 20 Connectivity (d) 10 anchors â€” â€” MDS-MAP(P.C) . * MDS-MAP(P,0) MDS-MAP(P.C) MDS-MAP(P.O) 50 k 40 LU S 30 10 Node 15 20 Connectivity 10 Node 15 20 Connectivity F i g u r e 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 l O r square network region employing uniform random placement of 200 nodes, for varying levels of connectivity and anchors deployed. monotonic constraint i n ordinal M D S provides accurate iterative m i n i m i z a t i o n of stress and hence lower position errors for most nodes, especially nodes w i t h large estimation errors. Figure 3.2 shows the position estimation errors as a function of the average connectivity level by hop-based M D S - M A P ( P , C ) and M D S - M A P ( P , 0 ) , respectively, w i t h 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. T h e performance improvement confirms the conjecture that i n sensors' localization problem, the use of the monotonic constraints i n ordinal M D S is Chapter 3. Ordinal Multidimensional Scaling 55 more appropriate t h a n the use of linear constraints i n classical M D S . The estimated node positions w i t h error less than 40% of the radio range have been proven to suit the applications of sensor networks [10]. W h e n 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. T h i s shows that dense networks can provide more consistent average error values. T h i s is due to the fact that dense networks have smaller two-hop regions, which i n 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 i n 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. T h e 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 connect i v i t y 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 i n accuracy is m i n i m a l 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 i n the range-based Chapter (a) M D S - M A P ( P . C ) , g o o ( e r r o r = 0 . 16 R ) (b) 56 Scaling M D S - M A P ( P . O ) , (errof=0.13R) o 0 OS, O Ordinal Multidimensional 3. % O 0 0 0 0 o o Â© ^ 0 3 o _ ocÂ£> cb* o 0 o Â« o 0 0 o o o Â° <S> Â© o es * o o o o Â© o o & 3> Â° - 0 o 0 o o . - o O Â© o o o Â© o Â° o Â© o Â© 0 CB) O W S Â° o o o Â© o o Â© o o o o o Â° o ' o < o o o 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) i n a l O r x l O r square network region employing uniform random placement of 200 nodes w i t h connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. E s t i m a t i o n error is represented by lines. case is only slightly better compared w i t h 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 i n order for the tradeoff of additional ranging hardware to be accepted. Results show that i n the range-based case, the position estimation error is more sensitive to the average connectivity level than to the number of anchors. A g a i n , 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 i n M D S - M A P ( P , 0 ) . T h i s is due to the fact that more accurate distance measurement information is available i n the range-based scheme. B y just using the connectivity information (i.e., hop-count), the hop-based scheme w i l l have some nodes Chapter 3. Ordinal Multidimensional Scaling (b) 6 anchors (a) 4 anchors â€” cc o â€” MDS-MAP(P.C) MDS-MAP(P.Q) â€” 30 o 0 S. 20 â€¢= 10 .o m 10 Node o 15 20 Connectivity cu 0 (c) 8 anchors o TD to *t 30 10 Node 15 20 Connectivity (d) 10 anchors â€¢ MDS-MAP(P,C) MDS-MAP(P.O) â€” cc o Ol si â€” MDS-MAP(P.C) lvlDS-MAP(P,0) 111 10 en Q- 30 _ UJ o o T3 TO en & 20 o = 57 â€” â€” MDS-MAP(P.C) x MDS-MAP(P.O) 30 20 20 o 10 UJ = 10 a- 0 O T7> O 10 Node 15 20 Connectivity 25 0 10 Node 15 20 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) i n a lOr x l O r 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 E u c l i d e a n distances may differ. T h i s 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 i n the range-based scheme. A s mentioned earlier, a Gaussian noise model is used to model the estimated range distances between two nodes. T h e actual distance is taken as the mean value. T h e value of the Chapter 3. Ordinal Multidimensional Scaling 20 2 5 R a n g e F i g u r e 3.5: Error 58 3 0 (%) Effects of node ranging error on performance of range-based M D S - M A P ( P , 0 ) i n a l O r x l O r square network region employing uniform random placement 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. T h i s is due to the fact that both algorithms need to use the same shortest-path distance m a t r i x 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 w i t h four anchors. Sensitivity Analysis of A n c h o r s ' L o c a t i o n on Positioning 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) i n 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)), w i t h the rectangular case performing the best w i t h an error of 9%. Since ordinal M D S algorithm does not require the use of triangulation, the position estimation error is still considered to be Chapter 3. Ordinal Multidimensional (a) Linearly Aligned Anchors (error=0.11R) 10 o ePÂ° o 0 0 Â° 0 n Â° o o <Â© Â° O (P 60 (b) Rectangular Aligned Anchors (error=0.09R) -e-e 10 o GÂ°8 O Â° Scaling .â€” Â© GTO G G G G GÂ£ o P (PP. G Gd" OG o GG Â° Â°i G 5 5 ( Q Q ^ & Â° o ePÂ© o CD p ?o * o .OB o o o 0 o o% Q Q O Â°o o Q O O 2 OÂ® C P 4 0 0 6 0 SB 8 10 0 2 4 G- P Q P ^P o _ G P GG G Pa @ GO o o< r*pP O" O ^ o ^ p @ 0 f> G p P Â°G-OG â€¢Â© 6 GÂ° 8 10 o 0 GÂ° - Â° G G Â° 0 0 G G ' G P n GEH G G" G Â©. G o 0 0 (P O ^ O ? 0. G 10 5> GÂ°G -p <p o Q o Â° o Â° , 030 G G 0 & > G 0 Â®JP 3 O o . &% o o oÂ° , lb Â©J Â° Â° Q C P Â° Â° rÂ©-e- 10 _ G o 0^ Â© Q o (d) Randomly Chosen Anchors (error=0.13R) 10 ^ G 0 0 0 (c) Closely Spaced Anchors (error=0.25R) 0 " GÂ° O. Â° Â°G G 0 Â°G ( P O GO o o@ G Â© GÂ°ooO G o (9 GGÂ° O GjG | Â° O G F â€¢ oÂ°Â° 1 O Pj o Â°Q G GPÂ© Â© G oo o- o G P G 0^ o o <3DÂ°Â° G ^ G PG O Â° U O Â© G Â° 0 Â° 10 Figure 3.7: A n c h o r topology results of range-based M D S - M A P ( P , O) when anchors are being placed (a) linearly, (b) i n a rectangular manner, (c) close to each other, and (d) randomly. T h e topology consists of a l O r x l O r square network region employing uniform random placement of 200 nodes w i t h connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. E s t i m a t i o n 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 w i t h i n a half radio range of each other, the orientation between the anchors has a small impact on the error as seen from the performance i n Chapter 3. Ordinal Multidimensional 61 Scaling (a) 4 anchors (b) 6 anchors CD g 5 CD | 60 â€” â€” MDS-MAP(P,0) >< MDS-MAP(P,O.R) 50 I I- 40 â€” â€”* 60 50 â€” MDS-MAP(P.O) MDS-MAP(P.O,R) 40 30 30 o Â£ I o a- 20 20 10 10 0 o L 10 15 20 10 Node Connectivity (c) 8 anchors CD !=f ro * m OL â€” 60 50 (d) â€” MDS-MAP(P.O) MDS-MAP(P.O,R) 50 30 30 20 20 10 10 to o Q- 1 0 anchors 40 40 UJ I 20 â€” â€” MDS-MAP(P.O) >< MDS-MAP(P,Q,R) 60 ~- _ 15 Node Connectivity 0 0 10 15 20 10 N o d e Connectivity 15 20 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 l O r square network region employing uniform random placement of 200 nodes, for varying levels of connectivity and anchors deployed. b o t h linear and rectangular cases (Figure 3.7 (a) - (b)). Further Improvement via (Optional) Global Relative Map Refinement T h e 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 after the patching of the local maps. [2]. T h i s optional step is invoked T h e least-squares minimization is used for the measured and calculated distances between neighboring nodes. T h i s optional refinement step has a complexity of 0(N ) 3 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 w i t h Chapter 3. Ordinal Multidimensional (a) 4 anchors Scaling 62 (b) 6 anchors â€” 30 MDS-MAP(P,0) MDS-MAP(P,0,R) 10 10 15 20 Node Connectivity 10 15 20 Node Connectivity (c) 8 anchors (d) 10 anchors MDS-MAP(P.O) MDS-MAP"(P,0,R) si MDS-MAP(P.O) MDS-MAP(P.O,R) Â£ . 20 20 10 15 20 Node Connectivity 10 15 20 Node Connectivity F i g u r e 3 . 9 : Performance between range-based M D S - M A P ( P , 0 ) and M D S - M A P ( P , 0 , R ) i n a l O r x l O r square network region employing uniform random placement 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 ) i n hop-based and range-based scenarios, respectively. number of anchors deployed is varied from 4 to 10. The In the hop-based case, there is significant reduction on the position estimation error when the average node connectivity level is above 9. ' T h e 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. T h e decrease i n improvement as the node connectivity level increases can be attributed to the increased accuracy achieved by Chapter 3. Ordinal Multidimensional Scaling 63 each node w i t h i n its two-hop neighborhood. T h e higher connectivity levels provide much more range-information from which the ordinal M D S w i t h local least-squares refinement methods result i n accurate relative position estimates. Therefore, the global least-squares refinement performance decreases w i t h 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 a l l the sensors i n the network (e.g., v i a flooding). T h i s may cause a higher signaling overhead. 3.3.2 Random Irregular Network Topology Whereas most papers presented have only considered uniform sensor network deployments, the method i n which these networks are meant to be deployed may not guarantee uniform coverage. Wireless sensor networks may exhibit regions of sparseness once deployed. 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 i n [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 ( a ) M D S - M A P ( P , C ) , 3. Ordinal ( e r r o r = 0 . 7 4 R ) Multidimensional ( b ) 64 Scaling M D S - M A P ( P . O ) , ( e r r o r = 0 . 6 5 R ) *4?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 l O r x l O r irregular (C-shaped) network region employing uniform random placement of 160 nodes w i t h connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. E s t i m a t i o n error is represented by lines. Hop-Based Performance Figure 3.10 shows the topologies estimated by hop-based M D S - M A P ( P , C ) and M D S MAP (P, 0 ) , respectively. T h e position estimation errors by M D S - M A P ( P , C ) and M D S - MAP (P, O) are 74% and 65% of the radio range, respectively. T h e 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 connect i v i t y level by hop-based M D S - M A P ( P , C ) and M D S - M A P ( P , O ) , i n 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 (a) 4 anchors (b) 6 anchors 200 or 65 Scaling 150 150 s_ 10 15 100 20 10 N o d e Connectivity 15 20 N o d e Connectivity (c) 8 anchors (d) 1 0 anchors 150 i ,S 10 15 N o d e Connectivity 20 50 10 15 20 N o d e 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 ) i n a l O r x l O r irregular (C-shaped) network region employing uniform random placement of 160 nodes, for varying levels of connectivity and anchors deployed. chors. T h i s difference is greater than the square topology case; however, the confidence intervals among the two algorithms show considerable overlap. T h i s is to be expected since the estimated shortest path distances are more prone to errors arising from the geometry of nodes that are w i t h i n 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%. Range-Based Performance 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. T h e position estimation errors by M D S - M A P ( P , C ) and M D S - Chapter (a) 0 3. M D S - M A P ( P , C ) , 2 4 Ordinal Multidimensional ( e r r o r = 0 . 5 2 R ) 6 8 66 Scaling ( b ) M D S - M A P ( P . O ) , 1 0 0 2 4 ( e r r o r = 0 . 4 6 R ) 6 8 1 0 F i g u r e 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 ) i n a l O r x l O r irregular (C-shaped) network region employing uniform random placement of 160 nodes w i t h connectivity level of 12 and four anchors. Anchors are denoted by shaded circles. E s t i m a t i o n 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 connectivity 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. W h e n 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. T h i s difference is greater than the square topology case; however, once again the confidence intervals among the two algorithms show significant overlap. W h e n the average connectivity level is 12 or higher, the estimation error is less than 46%. Chapter 3. Ordinal Multidimensional (a) 4 anchors (b) 6 anchors MDS-MAP(P.C) MDS-MAP(P.O) â€” -X Â£. 80 â€¢S 40 10 15 20 N o d e Connectivity 100 â€” MDS-MAP(P,C) MDS-MAP(P.O) 4-4 10 (c) 8 anchors MDS-MAP(P,C) MDS-MAP(P,0) 67 Scaling 15 20 N o d e Connectivity (d) 10 anchors ^ 100 4^-4 20 1 Figure 3.13: 10 15 20 N o d e Connectivity 10 15 20 N o d e Connectivity Performance of range-based M D S - M A P ( P , C ) and M D S - M A P ( P , 0 ) i n a l O r x l O r 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 ) i n hop-based and range-based scenarios, respectively. In the hopbased case, there is significant reduction on the position estimation error when the average node connectivity level is 12 or greater. T h e additional refinement scheme outperforms ordinal M D S i n the hop-based results on average 25%, for connectivity levels 12 and greater, which is larger than i n the square topology case. In the range-based case, the refinement scheme achieves on average 26% better accuracy than the ordinal M D S scheme, Chapter 3. Ordinal Multidimensional (a) 4 anchors â€” - - 68 Scaling (b) 6 anchors MDS-MAP(P.O) â€” MDS-MAP(P,0,R) -* â€” MDS-MAP(P.O) MDS-MAP(P,0,R) V V 50 10 Node 15 20 Connectivity 10 Node (c) 8 anchors â€” (d) 1 0 anchors â€” MDS-MAP(P.O) â€” MDS-MAP(P.O,R) 10 Node 15 20 Connectivity 15 20 Connectivity -X 25 10 Node â€” MDS-MAP(P.O) MDS-MAP(P,C\R) 15 20 Connectivity 25 F i g u r e 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 ) i n a l O r x l O r irregular (C-shaped) network region employing uniform random placement of 160 nodes, for varying levels of connect i v i t y and anchors deployed. which again is a higher gain i n accuracy compared to the square topology results. T h u s the benefit of the M D S - M A P ( P , 0 , R ) is greater i n the irregular (C-shaped) topology than i n the uniform (square) topology. T h i s is expected, since the iterative refinement of the global map i n the irregular case takes into account the topology from the result of the i n i t i a 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 F i g u r e 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 ) i n a 107- x l O r 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. T h e 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 i n [2]. T h e algorithm is extended by using the ordinal M D S algorithm instead of the classical M D S algorithm. T h e 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. T h e algorithm can be applied not only to the case where nodes are equipped w i t h 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 irregular (C-shaped) topologies, resulting w i t h M D S - M A P ( P , O) providing a lower position estimation error than M D S - M A P ( P , C ) i n 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 w i t h E q u a l A r e a ( C A B - E A ) and C A B w i t h E q u a 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 A l t h o u g h distributed range-based algorithms have a higher accuracy than the distributed range-free approaches i n 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 w i t h G P S modules. Thus, anchor nodes are more costly, consume more energy, and are larger i n size than n o r m a l sensor nodes. In addition, as in the case of some other schemes (e.g., [10]), anchors are assumed to have larger communication range than normal sensor nodes. T h e anchor-to-node range ( A N R ) ratio is equal to the m a x i m u m communication range of an anchor divided by the communication range of a sensor node. T h e m a i n difference between C A B and other range-free localization approaches is that i n C A B , anchors transmit several beacon signals at different power levels. This requirement is feasible i n current wireless sensor networks. For example, the M i c a 2 mote sensor nodes have a range of 18 meters for transmission power of -10 d b m , and 50 meters for 0 d b m [41] [42]. Ideally, the different power levels divide the possible transmission ranges of an anchor into a circle and rings. A s shown i n 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 (P v) is related to the signal power transmitted by an anchor node ( P ) by the following rC t x Chapter 4. Concentric Anchor-Beacons (CAB) Localization (a) Algorithm 73 (b) F i g u r e 4 . 1 : A n c h o r beacon transmission ranges w i t h (a) E q u a l area beacon signals w i t h 3 power levels; and (b) E q u a l w i d t h beacon signals w i t h 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 w i d t h of the ith ring/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. G i v e n the target B E R , we let Pthreshoid denote the m i n i m u m required received signal power i n order to decode the signal correctly. Let P max (milliWatts) denote the m a x i m u m power that an anchor node can transmit. T h e m a x i m u m 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. T h e resulting formula can be solved i n terms of r m a x as shown i n the following equations. Chapter 4. Concentric Anchor-Beacons (CAB) k-P T Localization Algorithm 74 max threshold max ,71 max max threshold (4.2) r-,max The ability of a node to hear beacons w i t h lower transmitted powers, implies that the node lies closer to the anchor than the m a x i m u m range. Consider an example i n Figure 4.1(a). If the sensor node can hear the beacons w i t h power levels P i , Pi and P3, then the distance between the anchor and the node is less than r\. T h a t is, the sensor node lies w i t h i n the inner-most circle, O n the other hand, if the node can only hear the beacon w i t h power level P3, then it lies w i t h i n 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 m i n i m u m threshold power. 4.2 CAB Algorithm 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 w i t h E q u a l A r e a ) , it is assumed that the area of the inner-most circle and the rings are a l l the same. T h a t is, i n Figure 4.1(a), the circle w i t h radius r\ has the same area as each of the rings outside that circle. T h e Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 75 relationship between the beacon transmission ranges r-j and the m a x i m u m transmission range r max is given by the following equation: (4.3) 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, transmission range for beacon i, and r max denotes the denotes the m a x i m u m range that a n anchor can transmit at the corresponding m a x i m u m power level P max Therefore, i n relation to power levels, the corresponding equation is as follows: (4.4) 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 % i n terms of the m a x i m u m transmit power P . max For C A B - E W ( C A B w i t h E q u a l W i d t h ) , it is assumed that the w i d t h of the inner-most circle and the rings are all the same. T h e relationship between the beacon transmission ranges and the m a x i m u m transmission range r i m a x is given by the following equation: i = 1,2, â€¢ â€¢ â€¢ ,m (4.5) T h e corresponding relationship between power transmission levels P ; and the m a x i - Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 76 Invalid Intersection Points F i g u r e 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 m a x i m u m range is empirically determined to be the distance from an anchor node, transmitting at m a x i m u m power, at which a sensor node has a received signal power equal to the m i n i m u m threshold power. T h i s 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 i n detail. T h e 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 T a b l e 4.1: Information collected by a sensor from its anchors. Anchor 3 Position ( j,Vj) x Beacons Transmit Constraint Power Info Region A (5.6, 6.2) B (9.6, 8.2) P2 (7*1 - r) ring C (9.9, 5.2) Pl, P2 r\ circle (ri - r) ring at varying power levels d u r i n g random time periods. T h a 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 m a x i m u m time T. W h e n i n 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. E a c h beacon signal packet includes the anchor's I D , the anchor's location, the transmit power level Pi information, and the estimated m a x i m u m distance that the beacon signal can be heard. E a c h node listens for beacons and collects the anchor's information. For each beacon heard, the sensor node determines w i t h i n which region of the anchor's concentric transmission circles it lies. Figure 4.2 shows an example w i t h a sensor node surrounded by three anchors. E a c h anchor transmits beacons at two different power levels. T h e 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. T h i s . i s 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. E a c h sensor node can receive multiple beacons w i t h 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 w i t h i n from that anchor. T h i s is called the constraint region. M a t h e m a t i c a l l y , this region is b o u n d 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). T h e last column i n Table 4.1 shows the constraint regions that the sensor node lies w i t h i n based on the scenario i n Figure 4.2. G i v e n the three chosen anchors, two of them are selected at a time to calculate the intersection points. T h e valid intersection regions. T h e invalid intersection points satisfy a l l three anchors' constraint points are those that do not lie w i t h i n the other anchor's constraint region. Consider the example i n Figure 4 . 2 . L e t (XA,VA), denote the positions of anchors A, B, and C, respectively. intersection points. For each point (x,y) following constraints are satisfied: {XB,VB), (xc,yc) Let I denote the set of â‚¬ I, it is a valid intersection point if the Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm n < y (x - xf + (VA - yf < r, n - xf + (y - yf A < \j(x B B 79 < r, \J{xc ~ xf + (y - yf < r . c l T h e final position estimate is taken as the average of all the valid intersection points. Figure 4.2 shows the estimated position determined by four valid intersection points. 4.3 Discussion There are three distinct advantages of the C A B localization algorithm. F i r s t of a l 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. T h i s reduces the energy requirement for localization. In addition, C A B has a higher accuracy than some other range-free localization algorithms. Simulation comparisons will be presented i n the next section. For the qualitative comparisons w i t h some other localization algorithms, A P I T [10] requires communication between neighboring nodes for the exchange of tabular information 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 i n ad hoc deployments. Whereas ring sizes are determined from R S S values i n R O C R S S I [26], the rings i n C A B are pre-determined according to the number of power levels desired to be used by the anchor. N o communication is required between anchors i n C A B . T h e C A B scheme does have its limitations. Being solely dependent on anchor nodes for position estimation, the accuracy depends on the percentage of anchor nodes deployed. T h i s percentage can be decreased by increasing the m a x i m u m 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 will 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 w i t h A P I T [10] and Centroid [11] algorithms are presented. A l l algorithms are simulated i n M a t l a b . T h e wireless sensor network consists of 280 nodes and a varying number of anchors are randomly placed. T h e network topology is a square of side 10R by 10R, where R is the sensor node communication range. T h e average connectivity among nodes is set to 8. T h e technique i n [10] to model the irregular radio pattern is used i n this simulation Chapter 4. Concentric Anchor-Beacons DOI = 0.01 (CAB) DOI = 0.05 Localization Algorithm 81 DOI = 0.10 F i g u r e 4.3: Irregular radio patterns for different values of D O I . model. In this model, a l l nodes w i t h i n half of the m a x i m u m transmit radio range of anchors are guaranteed to hear from the anchor, whereas nodes between the m a x i m u m radio range and half of that range may or may not hear from the anchor depending on the radio pattern in that direction. T h e degree of irregularity ( D O I ) parameter is defined as the m a x i m u m radio range variation per unit degree change i n 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. T h e anchor-to-node range ( A N R ) ratio is set to 3. T h e D O I value is set to 0.05. T h e estimation errors are normalized w i t h respect to the sensor node range 4.4.1 (R). 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 m i n i m a l percentage of anchors nodes to localize the system. T h e results show that for 12% of anchor nodes deployed, A N R values of 3 or higher enable at least 90% of a l l nodes Chapter 100 90 80 4. Concentric A N R = A N R = 3 A N R = 2 A N R = 1 Anchor-Beacons (CAB) Localization 82 Algorithm 4 - | 70 60 50 4 0 30 20 10 4 6 P e r c e n t a g e 8 10 of A n c h o r s 12 D e p l o y e d 14 16 18 (%) F i g u r e 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 i n 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 w i t h 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 (a) 83 CAB-EA B - Number of Power Levels = 1 -0â€” Number of Power Levels = 2 * Number of Power Levels = 3 on LU c o 2 2 LU 6 8 10 12 14 Percentage of Anchors Deployed (%) (b) 16 18 CAB-EW - B - Number of Power Levels = 1 0 Number of Power Levels = 2 â€¢ â€¢ â€¢ * â€¢ â€¢ Number of Power Levels = 3 ^ on 3 LU .1 2 1 -tâ€”Â» CO E in -*â€”* LU 6 8 10 12 14 Percentage of Anchors Deployed (%) 16 18 F i g u r e 4.5: Average estimation error under different number of power levels of the beacons 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. T h i s 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 w i t h smaller ring w i d t h . However for C A B - E W , the performance improvement is significantly better for 3 power levels than 2. T h i s can be attributed to the fact that the outer ring widths are wider i n C A B - E W than i n C A B - E A , which provides higher tolerance for radio pattern irregularity i n determining which ring the node resides w i t h i n . For anchor percentages greater than 12% C A B - E W w i t h 3 levels outperforms its 2 power level counterpart by 0.251?. T h u s 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 i n this case, since the estimation error is reduced by 0.221? on average when using C A B - E A . T h i s can be attributed to the fact that w i t h 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 w i t h i n 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 w i d t h than C A B - E W . Therefore, w i t h C A B - E A the intersection area of the outer Chapter 0.5 1 2 4. Concentric ' 4 1 6 Anchor-Beacons ' 8 P e r c e n t a g e (CAB) 1 10 of A n c h o r s Localization â€” 12 L D e p l o y e d 1 14 85 Algorithm 1 1 16 18 (%) F i g u r e 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 i n 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 i n Figure 4.7. In Figure 4.7(a), the perfect radio propagation model results i n the C A B - E A marginally outperforming C A B - E W . W h e n the D O I value is increased to 0.05 as shown i n (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 i n (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 . O f course, the relatively small difference in performance indicates that this result is sensitive to the 4. Concentric Anchor-Beacons (CAB) Localization Chapter (a) Algorithm 86 DOI = 0 LU Q I I 2 4 I I I I I 6 8 10 12 14 Percentage of Anchors Deployed (%) I 16 I 18 (b) DOI = 0.05 i i i i 2 4 6 8 10 12 14 Percentage of Anchors Deployed (%) (c) DOI = 0.10 16 18 2 4 6 8 10 12 14 Percentage of Anchors Deployed (%) 16 18 i i i i i Figure 4.7: C o m p a r i s o n of estimation error between C A B - E A and C A B - E W for different 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 E3 0 â€” A n c h o r s C h o i c e = R a n d o m A n c h o r s C h o i c e = Optimal 87 2.5 9=. 2 â€¢M 1-5 0.5 6 8 P e r c e n t a g e 10 12 of A n c h o r s D e p l o y e d 14 16 18 (%) Figure 4.8: C o m p a r i s o n of estimation error using randomly heard anchors versus optimally 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 m a x i m a l 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 m a x i m a l 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 w i t h the lowest I D s are chosen. For the case of optimal, the three anchors which form the largest triangle are chosen. Results i n 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 o p t i m a l 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. T h i s is expected since there are more anchors from which to choose. T h e choice of using only three anchors for position estimation is to reduce the computational requirement, since considering more anchors results i n many more intersection points to be computed. W e are aware that choosing the anchors that result i n 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 i n 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 anchors deployed. C A B has a better performance than both A P I T a n d Centroid. A s an illustration, when the percentage of anchors deployed is 16%, C A B - E W w i t h three power levels achieves 0.78R accuracy and C A B - E A w i t h two power levels has an average error Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm O.. â€” O â€¢ â€¢ Centroid A. â€” A P I T 89 C A B - E A â€” Qâ€” 2.5 C A B - E W 0.5 6 8 P e r c e n t a g e 10 of A n c h o r s 12 D e p l o y e d 14 16 18 (%) F i g u r e 4 . 9 : C o m p a r i s o n 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?. T h e 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 utilizing information from more than three anchors at the expense of a higher number of computations. M o r e specifically, in C A B for each pair of anchors the m a x i m u m 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(N ), where N denotes the number of anchors used i n the computation 2 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 3 4 A n c h o r - t o - N o d e (CAB) Localization 5 6 R a n g e 90 Algorithm ( A N R ) Ratio F i g u r e 4 . 1 0 : Comparison between Centroid, A P I T , C A B - E A (m = 2), and (m = 3) for varying levels of A N R . ( D O I = 0.05) CAB-EW T h e percentage of anchors deployed is 9%. A s the A N R value increases, this results i n a loss of accuracy i n all 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 u n t i l A N R equals 5. T h e error then increases w i t h higher A N R values. T h i s unique behavior can be attributed to the I n T o O u t error identified i n [10] which is more significant at low A N R values and diminishes w i t h increasing A N R . T h e C A B algorithm only relies on anchor information and thus increases i n 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. T h e higher A N R values result i n larger ring areas that i n t u r n create larger Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm .. , Q .. Centroid â€” A. â€”A P I T C A B 0 â€” â€¢â€” 2.5 h 9=. o 91 E A C A B - E W O LU _ ^ CO J 1. 5 4 - |fiâ€” 0.5 â€¢ â€” Q - A /V- - -V\ A Ar - â€¢ â€” 0.02 R a d i o 0.04 Pattern D e g r e e 0.06 0.08 0.1 of Irregularity ( D O I ) F i g u r e 4.11: C o m p a r i s o n 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 w i t h i n which the node estimate is taken. F i g u r e 4.10 also shows that A P I T outperforms both C A B schemes for A N R greater than 4. Note that i n 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. T h e 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 C e n t r o i d and A P I T . W h e n 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 a l l 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, w i t h 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. A l t h o u g h this property has been used to construct a range-free scheme that estimates positions of sensor nodes to be w i t h i n 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. T h e 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 traditional 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 a n d / o r R S S measurements can be reduced. T h e corresponding result is that range-based schemes can function in a relatively range-free manner depending on scheme-specific details. T h e only assumption i n C A B is that there is a reference m a x i m u m transmission power and the corresponding transmission range that is empirically derived prior to system deployment to take into account environment propagation characteristics. T h e incorporation of circular and ring constraints can be separately included to the existing schemes, i n 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 a l 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 w i t h 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. T h e accuracy of the Chapter 4. Concentric Anchor-Beacons (CAB) Localization Algorithm 94 approach depends on the number of power levels used. Once the nodes have determined their constraining circles, the linear m a t r i x inequalities ( L M I ) can be obtained and the solutions can be determined by the corresponding semi-definite programs ( S D P s ) . For anchor propagation schemes such as A P S [6], i n addition to the hop-by-hop transmission of beacons, the anchors can also transmit at different power levels to directly reach further sensor nodes. Nodes can then simultaneously execute b o t h A P S and C A B procedures and ensure that the estimated position based on A P S falls w i t h i n 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. T h e m a i n benefit is the additional information gathered by the node, i n 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 a l l 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 will 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 T h e A P I T scheme can also be extended since its structure is similar to C A B i n the use of anchors w i t h 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 I n T o O u t and O u t T o I n i n [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. U s i n g 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. implement. It has a low computational overhead that is simple to C A B uses anchors that broadcast beacon signals at varying power levels. T h i s allows each sensor node to identify which annular ring centered at the anchor that the node resides i n . T h e 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 C e n t r o i d 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 i n reducing position estimation error and even outperform C A B itself. Further modifications of the scheme can be performed i n 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 localization problem, this area is under continued refinement and development. Though many different proposals have been made, the assumptions i n the models have limited the applicability of the i n d i v i d u a l schemes i n other networks. Hence, for future work, the continued search for a technique or algorithm capable of providing accurate sensor positions, lies i n the realm of robustness under different network conditions. To suit this purpose, the scheme must work i n a decentralized manner, contain a low percentage of anchor nodes (less than 10%), and be able to cope w i t h low node connectivity. In general, connectivity is considered to be low if a node has less than 9 neighbors, m e d i u m if it has up to 15 neighbors and high if the connectivity is greater than 15. Decentralized networks may contain anchors deployed i n random fashion or carefully placed i n the coverage area. T h e latter being a more suitable design goal for new schemes. In addition, the aspect of positioning delay has seldom been considered i n proposed schemes. In terms of this delay, the better scheme is able to provide the positions of a l l nodes w i t h i n a specified amount of time, having much relevancy to the way i n which the algorithm is executed i n the network. Chapter 5.1 5. Conclusions and Future Work 98 Future Work In terms of future work, several areas are of interest: m u l t i m o d a l and measurement-free techniques, accuracy, energy consumption, mobility, and security. T h e use of m u l t i m o d a l techniques employing both range and angle measurements, have outperformed sole range or angle-based techniques in terms of measurement accuracy. Indeed, this w i l l be an area to further explore, as only a few papers have explored this possibility, and have not yet come w i t h an efficient way of combining both measurements i n a decentralized and parallel manner. T h e m a i n problem in this approach has been the actual feasibility of sensor nodes being equipped w i t h m u l t i m o d a l hardware. T h e complete opposite to this approach is avoiding measurements at a l l , sighting inaccuracies 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 i n this thesis. In general, a l l schemes have quoted their accuracy w i t h respect to sensor communication range. In terms of future work, the development of more accurate schemes is clearly possible. A c c o r d i n g to results so far, the most accurate schemes contain m e d i u m or high node connectivity levels, as evidenced by the unsurpassed results obtained by M D S techniques. Further work must be done i n 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. T h e use of U W B technology Chapter 5. Conclusions and Future Work 99 has shown to provide incredibly accurate results i n the presence of obstacles from indoor deployments. T h e 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' battery power. T h i s is by far the most under-developed aspect of this area, relative to the significance i n an actual sensor network deployment. Since localization of the nodes is only necessary to aid the sensor network i n achieving its deployment purpose, the positioning scheme must not deplete the sensor nodes and thus prevent them from achieving their main deployment purpose. T h i s can be avoided by schemes involving the passive localization of sensor nodes, i n which nodes position themselves relative to fixed system anchors, and need not communicate w i t h other sensors i n order to obtain accurate positions. O f course, this again affects the robustness of the scheme i n terms of ad-hoc deployments, and thus further work may have to be done i n developing hybrid models where the necessary communication between nodes is limited. A n o t h e r 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 mobility i n 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 mobility adversely affects position estimation, others have countered that claim. A s nodes become mobile, the neighborhood information is constantly changing w i t h respect to each node. T h i s additional information, unavailable i n static networks, Chapter 5. Conclusions and Future Work 100 should be used as an advantage i n 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 i n the network to obtain position information. T h e continuous movement of nodes w i l l eventually result i n accurate tracking of all nodes in the network. M a n y questions still remain to be answered i n 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 communications of the sensors. M a n y applications have been proposed for such networks i n adversarial settings, which impose security threats on the network. Several papers have outlined some of these issues and proposed methods to be employed i n 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 w i t h i n the localization scheme. T h e more robust architectures i n terms of security are more centralized, since it is assumed that fixed anchors and central computation authorities are trusted, whereas i n 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 connectivity," i n Proc. of ACM MobiHoc, A n n a p o l i s , M D , June 2003, pp. 201-212. [2] Y . Shang, W . R u m l , and Y . Zhang, "Improved M D S - b a s e d localization," in Proc. IEEE Infocom, H o n g K o n g , C h i n a , M a r c h 2004, pp. 2640-2651. [3] I. A k y i l d i z , W . Su, Y . Sankarasubramaniam, and E . C a y i r c i , "Wireless sensor networks: A survey," Elsevier Computer Networks, vol. 38, pp. 393-422, 2002. [4] D . Niculescu, "Positioning i n ad hoc sensor networks," IEEE Network Magazine, vol. 18, no. 4, pp. 24-29, J u l y 2004. [5] L . Doherty, K . Pister, and L . G h a o u i , "Convex position estimation i n wireless sensor networks," i n Proc. of IEEE Infocom, Anchorage, A K , A p r i l 2001, pp. 1655-1663. [6] D . Niculescu and B . N a t h , " A d - h o c positioning system," i n Proc. of IEEE Globecom, San A n t o n i o , T X , N o v . 2001, pp. 2926-2931. [7] K . Langendoen and N . Reijers, "Distributed localization i n wireless sensor networks: A quantitative comparison," Computer Networks, v o l . 43, pp. 499-518, Nov. 2003. 102 Bibliography [8] D . Niculescu and B . N a t h , " A d - h o c positioning system Proc. of IEEE ( A P S ) using A O A , " i n Infocom, San Francisco, C A , A p r i l 2003, pp. 1734-1743. [9] K . C h i n t a l a p u d i , A . D h a r i w a l , R. G o v i n d a n , and G . Sukhatme, " A d - h o c localization using ranging and sectoring," i n Proc. of IEEE Infocom, H o n g K o n g , C h i n a , M a r c h 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," i n Proc. of ACM MobiCom, San Diego, C A , September 2003, pp. 81-95. [11] N . B u l u s u , J . Heidemann, and D . E s t r i n , "GPS-less low cost outdoor localization for very small devices," IEEE Personal Communications Magazine, v o l . 7, no. 5, pp. 28-34, Oct. 2000. [12] A . Savvides, C . - C . H a n , and M . Srivastava, " D y n a m i c fine-grained localization i n ad-hoc networks of sensors," i n Proc. of ACM MobiCom, Rome, Italy, J u l y 2001, pp. 166-179. [13] X . J i and H . Zha, "Sensor positioning i n wireless ad-hoc sensor networks using multidimensional scaling," i n Proc. IEEE Infocom, H o n g K o n g , C h i n a , M a r c h 2004, pp. 2652-2661. [14] V . Vivekanandan and V . W o n g , " O r d i n a l M D S - b a s e d localization for wireless sensor networks," submitted to IEEE WCNC 2006. 103 Bibliography [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, v o l . 34, no. 8, pp. 57-66, 2001. [17] N . P a t w a r i , J . A s h , S. Kyperountas, A . Hero III, R . Moses, and N . Correal, "Locating the nodes: Cooperative localization i n wireless sensor networks," IEEE Processing Magazine, Signal vol. 22, no. 4, pp. 54-69, J u l y 2005. [18] A . Savvides, M . Srivastava, L . G i r o d , and D . E s t r i n , " L o c a l i z a t i o n i n sensor networks," book chapter i n Wireless Sensor Networks, Springer, 2005. [19] C . Savarese, J . Rabaey, and J . Beutel, "Location in distributed ad-hoc wireless sensor networks," i n Proc. of IEEE ICASSP, Salt Lake City, U T , M a y 2001, pp. 2037-2040. [20] S. C a p k u n , M . H a m d i , and J.-P. H u b a u x , "GPS-free positioning i n mobile ad-hoc networks," i n Proc. of Hawaii Int. Conf. on System Sciences (HICSS-34), Maui, Hawaii, Jan. 2001. [21] A . Savvides, H . Park, and M . Srivastava, "The bits and flops of the n-hop multilateration primitive for node localization problems," i n Proc. of ACM G A , September 2002, pp. 112-121. WSNA, Atlanta, 104 Bibliography [22] C . Savarese, J . Rabaey, and K . Langendoen, "Robust positioning algorithms for distributed ad-hoc wireless sensor networks," i n Proc. of USENIX Technical Annual Conference, Monterey, C A , June 2002, pp. 317-327. [23] D . Niculescu a n d B . N a t h , "Error characteristics of ad hoc positioning systems ( A P S ) , " i n Proc. of ACM MobiHoc, Roppongi, Japan, M a y 2004, pp. 20-30. [24] A . N a s i p u r i a n d K . L i , " A directionality based location discovery scheme for wireless sensor networks," i n Proc. of ACM WSNA, A t l a n t a , G A , September 2002, pp. 1 0 5 111. [25] N . P a t w a r i and A . Hero I I I , "Using proximity a n d quantized R S S for sensor localization i n wireless networks," i n 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," i n Proc. of IEEE IPCCC, Phoenix, A Z , A p r i l 2005, pp. 59-66. [27] X . Cheng, A . Thaeler, G . X u e , and D . C h e n , " T P S : A time-based positioning scheme for outdoor wireless sensor networks," i n Proc. of IEEE Infocom, Hong K o n g , C h i n a , M a r c h 2004, pp. 2685-2696. [28] S. C a p k u n a n d J.-P. Hubaux, "Secure positioning i n sensor networks," i n Technical Report (EPFL/IC/200444) 2004. Swiss Federal Institute of Technology Lausanne, M a y 105 Bibliography [29] N . P r i y a n t h a , H . Balakrishnan, E . Demaine, and S. Teller, "Anchor-free distributed localization i n sensor networks," i n 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," i n Proc. of MobiCom, ACM P h i l a d e l p h i a , P A , Sept. 2004, pp. 45-57. [31] M . Sichitiu and V : R a m a d u r a i , " L o c a l i z a t i o n of wireless sensor networks w i t h a mobile beacon," i n Proc. of IEEE MASS, Fort Lauderdale, F L , O c t . 2004, pp. 174- 183. [32] K . - F . Ssu, C . - H . O u , and H . J i a u , "Localization w i t h mobile anchor points i n wireless sensor networks," IEEE Trans, on Vehicular Technology, v o l . 54, pp. 1186-1197, M a y 2005. [33] P. Pathirana, N . B u l u s u , A . Savkin, and S. Jha, "Node localization using mobile robots i n 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, [35] W . Hardle and L . Simar, Applied Multivariate 3rd ed. Statistical A d d i s o n Wesley, 2003. Analysis. Springer-Verlag, 2003. [36] J . K r u s k a l , "Nonmetric multidimensional scaling: a numerical method," trika, vol. 29, pp. 115-129, 1964. Psychome- Bibliography [37] J . K r u s k a l and M . W i s h , 106 Multidimensional Scaling, ser. Sage University Paper series on Quantitative A p p l i c a t i o n s i n the Social Sciences. Beverly Hills and London: Sage Publications, 1978, no. 07-011. [38] I. B o r g and P. Groenen, Modern Multidimensional Scaling: Theory and Applications. New York: Springer, 1997. [39] J . K r u s k a l , "Analysis of factorial experiments by estimating monotone tions of the data," transforma- Journal of the Royal Statistical Society, vol. 27:2, pp. 251-263, 1965. [40] P. Groenen and M . VandeVelden, " M u l t i d i m e n s i o n a l scaling," i n 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," i n Proc. of ACM MobiHoc, N e w Y o r k , N Y , M a y 2005, pp. 390-401. [42] "Crossbow Technology," h t t p : / / w w w . x b o w . c o m / .
- 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
Page Metadata
Item Metadata
Title | Localization algorithms for wireless sensor networks |
Creator |
Vivekanandan, Vijayanth |
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 |
Graduation Date | 2006-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | 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}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0064953/manifest