284 J.Comput.Sci.Technol.,Mar.2010,Vol.25,No.2 target tracking,or other tasks. (b)Node Density A more general form of coordinate system stitch- Many localization algorithms are sensitive to node ing is the component based localization561.A compo- density.For instance,hop-count-based schemes gene- nent is defined as a group of nodes that form a rigid rally require high node density so that the hop count structure.Using rigid components as basic units,the approximation for distance is accurate.Similarly,al- algorithm56]merges and localizes components through gorithms that depend on beacon nodes fail when the inter-component distance measurements and anchor in- beacon density is not sufficiently high in a specific re- formation. gion.Thus when designing or analyzing an algorithm, As shown in Fig.13 three inter-component distance it is important to consider its requirement on node den- measurements constrain the relative geometric relation- sity,since high density may not be always true. ship between two components A and B,both of which (c)Accuracy are adjacent to two anchors.From the perspective of Given a localization algorithm,location accuracy each single node,none of them has(at least)two neigh- shows how well the computed locations match with the boring anchors.In contrast,from the perspective of physical positions of the nodes.To be specific,location components,component A and component B can be accuracy is defined as the expected Euclidean distance merged into a bigger component,which is localizable between the location estimate and the actual location by referring to the four anchors.Next,all nodes in the of an unknown node,while location precision indicates two components are localized.The component-based the percentage of the results satisfying a pre-defined localization algorithms are applicable for sparse net- accuracy requirement. works.Similar to Sweeps,this design cannot guarantee terminating in polynomial time either,which is a major For a given localization result,location accuracy trades off with location precision.If we relax the ac- drawback. curacy requirement,we can increase precision,and vice versa.Thus,we must put these two metrics in a com- mon framework for comparison.We can fix location precision,say 95%,and evaluate the localization algo- Component A Component B rithms based on the corresponding accuracy achieve- ments. The error propagation demonstrates how location accuracy varies with the increase of measurement er- ror.Intuitively,localization error is linear with mea- Fig.13.Component-based localization. surement error.However,it is not true for many local- Coordinate system stitching techniques are quite ization systems,especially for those sequential locali- compelling.They are inherently distributed,since sub- zation algorithms,such as trilateration and bilatera- region and local map formation can trivially occur in tion.Nodes with large location errors would contami- the network and stitching is easily formulated as a peer- nate their neighbors'estimates.In this scenario,mea- to-peer algorithm. surement error is no longer the only factor contributing to localization error. 2.2.4 Comparative Study and Directions of Future (d)Cost Research In general,the cost of a localization system includes (a)Beacon Nodes hardware cost and energy cost.Hardware cost consists Beacon nodes (a.k.a.seeds or anchors)are necessary of three parts:node density,beacon density,and mea- for localizing a network in the global coordinate system. surement equipment.Usually,expensive equipments Beacon nodes have no difference from ordinary network provide more accurate measurements.A localization nodes except knowing their global locations as a priori. procedure often involves inter-node measurement,com- This knowledge can be hard-coded,or acquired through putation and communication,among which communi- some extra hardware like a GPS receiver cation consumes most energy.This is why distributed Beacon configuration has significant impact on lo- algorithms are often more compelling than centralized calization.Existing work finds that higher localization algorithms. accuracy can be achieved if beacons are placed in a con- After years of extensive study on this topic,many vex hull around the network.Placing additional bea- localization solutions are presented.Table 2 presents cons in the center of the network is also helpful.Thus. an overview of typical approaches in terms of accu- it is necessary for system designers to plan the beacon racy,node density,beacon percentage,computation layout before deploying a network. cost,communication cost,and error propagation.284 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 target tracking, or other tasks. A more general form of coordinate system stitch￾ing is the component based localization[56]. A compo￾nent is defined as a group of nodes that form a rigid structure. Using rigid components as basic units, the algorithm[56] merges and localizes components through inter-component distance measurements and anchor in￾formation. As shown in Fig.13 three inter-component distance measurements constrain the relative geometric relation￾ship between two components A and B, both of which are adjacent to two anchors. From the perspective of each single node, none of them has (at least) two neigh￾boring anchors. In contrast, from the perspective of components, component A and component B can be merged into a bigger component, which is localizable by referring to the four anchors. Next, all nodes in the two components are localized. The component-based localization algorithms are applicable for sparse net￾works. Similar to Sweeps, this design cannot guarantee terminating in polynomial time either, which is a major drawback. Fig.13. Component-based localization. Coordinate system stitching techniques are quite compelling. They are inherently distributed, since sub￾region and local map formation can trivially occur in the network and stitching is easily formulated as a peer￾to-peer algorithm. 2.2.4 Comparative Study and Directions of Future Research (a) Beacon Nodes Beacon nodes (a.k.a. seeds or anchors) are necessary for localizing a network in the global coordinate system. Beacon nodes have no difference from ordinary network nodes except knowing their global locations as a priori. This knowledge can be hard-coded, or acquired through some extra hardware like a GPS receiver. Beacon configuration has significant impact on lo￾calization. Existing work finds that higher localization accuracy can be achieved if beacons are placed in a con￾vex hull around the network. Placing additional bea￾cons in the center of the network is also helpful. Thus, it is necessary for system designers to plan the beacon layout before deploying a network. (b) Node Density Many localization algorithms are sensitive to node density. For instance, hop-count-based schemes gene￾rally require high node density so that the hop count approximation for distance is accurate. Similarly, al￾gorithms that depend on beacon nodes fail when the beacon density is not sufficiently high in a specific re￾gion. Thus when designing or analyzing an algorithm, it is important to consider its requirement on node den￾sity, since high density may not be always true. (c) Accuracy Given a localization algorithm, location accuracy shows how well the computed locations match with the physical positions of the nodes. To be specific, location accuracy is defined as the expected Euclidean distance between the location estimate and the actual location of an unknown node, while location precision indicates the percentage of the results satisfying a pre-defined accuracy requirement. For a given localization result, location accuracy trades off with location precision. If we relax the ac￾curacy requirement, we can increase precision, and vice versa. Thus, we must put these two metrics in a com￾mon framework for comparison. We can fix location precision, say 95%, and evaluate the localization algo￾rithms based on the corresponding accuracy achieve￾ments. The error propagation demonstrates how location accuracy varies with the increase of measurement er￾ror. Intuitively, localization error is linear with mea￾surement error. However, it is not true for many local￾ization systems, especially for those sequential locali￾zation algorithms, such as trilateration and bilatera￾tion. Nodes with large location errors would contami￾nate their neighbors’ estimates. In this scenario, mea￾surement error is no longer the only factor contributing to localization error. (d) Cost In general, the cost of a localization system includes hardware cost and energy cost. Hardware cost consists of three parts: node density, beacon density, and mea￾surement equipment. Usually, expensive equipments provide more accurate measurements. A localization procedure often involves inter-node measurement, com￾putation and communication, among which communi￾cation consumes most energy. This is why distributed algorithms are often more compelling than centralized algorithms. After years of extensive study on this topic, many localization solutions are presented. Table 2 presents an overview of typical approaches in terms of accu￾racy, node density, beacon percentage, computation cost, communication cost, and error propagation