278 J.Comput.Sci.Technol..Mar.2010,Vol.25,No.2 such as the lack of real-time control,software delay,in- compute the intersection of all overlapping coverage re- terrupt handling delay,system loads,etc.These two gions and choose the centroid as the location estimate. delays,if not carefully controlled,can easily add up Along with the increasing number of constraining areas. to several milliseconds on average,which translates to higher localization accuracy can be achieved. several feet of ranging error.BeepBeep(301,a recently According to how area is estimated,we classify the designed high-accuracy acoustic-based ranging system, existing approaches into two categories:single reference achieves the localization accuracy as good as one or two area estimation and multi-reference area estimation. centimeters within a range of more than ten meters (a)Single Reference Area Estimation which is so far the best ranging result for off-the-shelf In this case,constraining areas are obtained accord- cell phones. ing to a single reference.For instance,the region of ra- In conclusion,many localization algorithms use dio coverage may be upper-bounded by a circle of radius TDoA simply because it is dramatically more accurate Rmax.In other words,if node B hears node A,it knows than radio-only methods.The tradeoff is that nodes must be equipped with acoustic transceivers in addi- that it must be no more than a distance Rmax from A. If an unknown node hears from several reference nodes, tion to radio transceivers,significantly increasing both it can determine that it must lie in the geometric region the complexity and the cost of the system. described by the intersection of circles of radius Rmax 2.1.2 Angle Measurement centered at these nodes,as illustrated in Fig.6(a).This can be extended to other scenarios.For instance.when Another approach for localization is the use of both lower bound Rmin and upper bound Rmax can be angular estimates instead of distance estimates.In determined,the shape of a single node's coverage is trigonometry and geometry,triangulation is the process an annulus,as illustrated in Fig.6(c);when an angu- of determining the location of a point by measuring an- lar sector (Omin,0max)and a maximum range Rmax can gles to it from two known reference points at either end be determined for some radio antennas,the shape for a of a fixed baseline,using the law of sines.Triangulation single node's coverage would be a cone with given angle was once used to find the coordinates and sometimes and radius,illustrated in Fig.6(d). the distance from a ship to the shore. The Angle of Arrival (AoA)data is typically gath- ered using radio or microphone arrays,which allow a receiver to determine the direction of a transmitter. Suppose several(3~4)spatially separated microphones hear a single transmitted signal.By analyzing the phase or time difference between the signal arrivals at different microphones,it is possible to discover the AoA of the signal. (a Those methods can obtain accuracy within a few degrees31.A straightforward localization technique. involving three rotating reference beacons at the boun- dary of a sensor network providing localization for all interior nodes,is described in [32].A more detailed de- scription of AoA-based triangulation techniques is pro- vided in 33. Unfortunately,AoA hardware tends to be bulkier Fig.6.Area measurements. and more expensive than TDoA ranging hardware, Localization techniques using geometric regions are since each node must have one speaker and several mi- first described by [34].One of the nice features of these crophones.Furthermore,the need of spatial separation techniques is that not only can the unknown nodes use between microphones is difficult to be accommodated the centroid of the overlapping region as a specific lo- in small size sensor nodes. cation estimate if necessary,but also they can deter- 2.1.3 Area Measurement mine a bound on the location error using the size of this region.When the upper bounds on these regions If the radio or other signal coverage region can be are tight,the accuracy of this geometric approach can described by a geometric shape,locations can be es- be further enhanced by incorporating "negative infor- timated by determining which geometric areas that a mation"about which reference nodes are not within node is in.The basic idea of area estimation is to rangel351.Although arbitrary shapes can be potentially278 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 such as the lack of real-time control, software delay, in￾terrupt handling delay, system loads, etc. These two delays, if not carefully controlled, can easily add up to several milliseconds on average, which translates to several feet of ranging error. BeepBeep[30], a recently designed high-accuracy acoustic-based ranging system, achieves the localization accuracy as good as one or two centimeters within a range of more than ten meters, which is so far the best ranging result for off-the-shelf cell phones. In conclusion, many localization algorithms use TDoA simply because it is dramatically more accurate than radio-only methods. The tradeoff is that nodes must be equipped with acoustic transceivers in addi￾tion to radio transceivers, significantly increasing both the complexity and the cost of the system. 2.1.2 Angle Measurement Another approach for localization is the use of angular estimates instead of distance estimates. In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring an￾gles to it from two known reference points at either end of a fixed baseline, using the law of sines. Triangulation was once used to find the coordinates and sometimes the distance from a ship to the shore. The Angle of Arrival (AoA) data is typically gath￾ered using radio or microphone arrays, which allow a receiver to determine the direction of a transmitter. Suppose several (3∼4) spatially separated microphones hear a single transmitted signal. By analyzing the phase or time difference between the signal arrivals at different microphones, it is possible to discover the AoA of the signal. Those methods can obtain accuracy within a few degrees[31]. A straightforward localization technique, involving three rotating reference beacons at the boun￾dary of a sensor network providing localization for all interior nodes, is described in [32]. A more detailed de￾scription of AoA-based triangulation techniques is pro￾vided in [33]. Unfortunately, AoA hardware tends to be bulkier and more expensive than TDoA ranging hardware, since each node must have one speaker and several mi￾crophones. Furthermore, the need of spatial separation between microphones is difficult to be accommodated in small size sensor nodes. 2.1.3 Area Measurement If the radio or other signal coverage region can be described by a geometric shape, locations can be es￾timated by determining which geometric areas that a node is in. The basic idea of area estimation is to compute the intersection of all overlapping coverage re￾gions and choose the centroid as the location estimate. Along with the increasing number of constraining areas, higher localization accuracy can be achieved. According to how area is estimated, we classify the existing approaches into two categories: single reference area estimation and multi-reference area estimation. (a) Single Reference Area Estimation In this case, constraining areas are obtained accord￾ing to a single reference. For instance, the region of ra￾dio coverage may be upper-bounded by a circle of radius Rmax. In other words, if node B hears node A, it knows that it must be no more than a distance Rmax from A. If an unknown node hears from several reference nodes, it can determine that it must lie in the geometric region described by the intersection of circles of radius Rmax centered at these nodes, as illustrated in Fig.6(a). This can be extended to other scenarios. For instance, when both lower bound Rmin and upper bound Rmax can be determined, the shape of a single node’s coverage is an annulus, as illustrated in Fig.6(c); when an angu￾lar sector (θmin, θmax) and a maximum range Rmax can be determined for some radio antennas, the shape for a single node’s coverage would be a cone with given angle and radius, illustrated in Fig.6(d). Fig.6. Area measurements. Localization techniques using geometric regions are first described by [34]. One of the nice features of these techniques is that not only can the unknown nodes use the centroid of the overlapping region as a specific lo￾cation estimate if necessary, but also they can deter￾mine a bound on the location error using the size of this region. When the upper bounds on these regions are tight, the accuracy of this geometric approach can be further enhanced by incorporating “negative infor￾mation” about which reference nodes are not within range[35]. Although arbitrary shapes can be potentially