282 J.Comput.Sci.Technol.,Mar.2010,Vol.25,No.2 coordinates. distance-vector algorithm is used to determine the dis- 3)Transform the solution into global coordinates tance corresponding to the shortest distance path be- based on some number of fixed anchor nodes. tween the unknown nodes and reference nodes. MDS performs well on RSS data,getting perfor- 3)Iterative localization:One variant of above ap- mance on the order of half the radio range when the proaches is indirect use of beacon nodes.Initially an neighborhood size nocal is higher than 121471.The main unknown node,if possible,is located based on its neigh- problem with MDS,however,is its poor asymptotic per- bors by multilateration or other positioning techniques formance,which is O(n3)on account of stages 1 and 2. After being aware of its location,it becomes a refer- (b)SemiDefinite Programming(SDP) ence node to localize other unknown nodes in the sub- The semidefinite programming(SDP)approach was sequent localization process.This step continues iter- pioneered by Doherty et al.34 In their algorithm,ge atively,gradually turning the unknown nodes to the ometric constraints between nodes are represented as known.The process of iterative localization is illus linear matrix inequalities (LMIs).Once all the con- trated in Fig.9. straints in the network are expressed in this form,the LMIs can be combined to form a single semidefinite program,which is solved to produce a bounding region for each node.The advantage of SDP is its elegance 女女4 on concise problem formulation,clear model represen- tation,and elegant mathematic solution. Solving the linear or semidefinite program has to be Fig.9.Iterative localization. done centrally.The relevant operation is O(k2)for an- gle of arrival data,and O(k3)when radial (e.g.,hop Iterative trilateration only involves local information count)data is included,where k is the number of con- (information within neighborhood)and accordingly re- vex constraints needed to describe the network.Thus. duces communication cost.Nevertheless.the use of lo- the computation complexity of SDP is likely to preclude calized unknown nodes as reference nodes inherently itself in practice. introduces substantial cumulative error.Some works Unfortunately,not all geometric constraints can be characterize the error propagation in multihop locali- expressed as LMIs.In general,only constraints that zation approaches and make efforts to control error accumulation[50-51] form convex regions are amenable to representation as an LMI.Thus,AoA data can be represented as a trian- Experimental studies show that multilateration- gle and hop count data can be represented as a circle, based algorithms require an average node degree be- but precise range data cannot be conveniently repre- yond 10 to properly localize most of the nodes in a ran sented,as rings cannot be expressed as convex con- domly deployed networkl521.When the average degree strains.This inability to accommodate precise range is below 8,iterative multilateration will fail for most of data might prove to be a significant drawback. the nodes,since it makes the nodes form a chain of de- pendence and a single-point failure on one node would 2.2.3 Distributed Localization Approaches lead to further failures on a set of subsequent nodes. To make localization applicable for sparse networks, (a)Beacon Based Localization Sweeps[53)partially relaxes the requirement of node de- Beacon based localization approaches utilize esti- pendence.In contrast to the traditional unique position mates of distances to reference nodes that may be se- computation,Sweeps introduces a novel concept of fi- veral hops awayl4s-49.These distances are propagated nite localization which locates a target node to a set from reference nodes to unknown nodes using a basic of possible positions,called candidate positions.Finite distance-vector technique.Such a mechanism can be localization guarantees that the ground truth position seen as a top-down manner due to the progressive pro- of a node is one of its candidate positions.Further. pagation of location information from beacons to an Sweeps adopts a new positioning scheme,called bilate- entire network.There are three types as follows ration,to compute the candidate positions of a node by 1)DV-hop:In this approach,each unknown node utilizing only two ranging measurements.As shown in determines its distance from various reference nodes by Fig.10,bilateration produces two candidate positions multiplying the least number of hops to the reference for a node and one of them is the ground truth posi- nodes with an estimated average distance per hop that tion.Similar to multilateration,the finitely localized depends upon the network density. node,called swept node,can act as a reference node to 2)DV distance:If inter-node distance estimates localize other nodes.The only difference is that all can- are directly available for each link in the graph,the didate positions of the swept node are enumerated for282 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 coordinates. 3) Transform the solution into global coordinates based on some number of fixed anchor nodes. MDS performs well on RSS data, getting perfor￾mance on the order of half the radio range when the neighborhood size nlocal is higher than 12[47]. The main problem with MDS, however, is its poor asymptotic per￾formance, which is O(n 3 ) on account of stages 1 and 2. (b) SemiDefinite Programming (SDP) The semidefinite programming (SDP) approach was pioneered by Doherty et al. [34] In their algorithm, ge￾ometric constraints between nodes are represented as linear matrix inequalities (LMIs). Once all the con￾straints in the network are expressed in this form, the LMIs can be combined to form a single semidefinite program, which is solved to produce a bounding region for each node. The advantage of SDP is its elegance on concise problem formulation, clear model represen￾tation, and elegant mathematic solution. Solving the linear or semidefinite program has to be done centrally. The relevant operation is O(k 2 ) for an￾gle of arrival data, and O(k 3 ) when radial (e.g., hop count) data is included, where k is the number of con￾vex constraints needed to describe the network. Thus, the computation complexity of SDP is likely to preclude itself in practice. Unfortunately, not all geometric constraints can be expressed as LMIs. In general, only constraints that form convex regions are amenable to representation as an LMI. Thus, AoA data can be represented as a trian￾gle and hop count data can be represented as a circle, but precise range data cannot be conveniently repre￾sented, as rings cannot be expressed as convex con￾strains. This inability to accommodate precise range data might prove to be a significant drawback. 2.2.3 Distributed Localization Approaches (a) Beacon Based Localization Beacon based localization approaches utilize esti￾mates of distances to reference nodes that may be se￾veral hops away[48-49]. These distances are propagated from reference nodes to unknown nodes using a basic distance-vector technique. Such a mechanism can be seen as a top-down manner due to the progressive pro￾pagation of location information from beacons to an entire network. There are three types as follows. 1) DV-hop: In this approach, each unknown node determines its distance from various reference nodes by multiplying the least number of hops to the reference nodes with an estimated average distance per hop that depends upon the network density. 2) DV distance: If inter-node distance estimates are directly available for each link in the graph, the distance-vector algorithm is used to determine the dis￾tance corresponding to the shortest distance path be￾tween the unknown nodes and reference nodes. 3) Iterative localization: One variant of above ap￾proaches is indirect use of beacon nodes. Initially an unknown node, if possible, is located based on its neigh￾bors by multilateration or other positioning techniques. After being aware of its location, it becomes a refer￾ence node to localize other unknown nodes in the sub￾sequent localization process. This step continues iter￾atively, gradually turning the unknown nodes to the known. The process of iterative localization is illus￾trated in Fig.9. Fig.9. Iterative localization. Iterative trilateration only involves local information (information within neighborhood) and accordingly re￾duces communication cost. Nevertheless, the use of lo￾calized unknown nodes as reference nodes inherently introduces substantial cumulative error. Some works characterize the error propagation in multihop locali￾zation approaches and make efforts to control error accumulation[50-51] . Experimental studies show that multilateration￾based algorithms require an average node degree be￾yond 10 to properly localize most of the nodes in a ran￾domly deployed network[52]. When the average degree is below 8, iterative multilateration will fail for most of the nodes, since it makes the nodes form a chain of de￾pendence and a single-point failure on one node would lead to further failures on a set of subsequent nodes. To make localization applicable for sparse networks, Sweeps[53] partially relaxes the requirement of node de￾pendence. In contrast to the traditional unique position computation, Sweeps introduces a novel concept of fi- nite localization which locates a target node to a set of possible positions, called candidate positions. Finite localization guarantees that the ground truth position of a node is one of its candidate positions. Further, Sweeps adopts a new positioning scheme, called bilate￾ration, to compute the candidate positions of a node by utilizing only two ranging measurements. As shown in Fig.10, bilateration produces two candidate positions for a node and one of them is the ground truth posi￾tion. Similar to multilateration, the finitely localized node, called swept node, can act as a reference node to localize other nodes. The only difference is that all can￾didate positions of the swept node are enumerated for