280 J.Comput.Sci.Technol.,Mar.2010,Vol.25,No.2 when the density of reference nodes is sufficiently high so that there are often multiple reference nodes within the range of an unknown nodel421.Let there be k refer- ence nodes within the proximity of the unknown node As shown in Fig.8,we use the centroid of the polygon constructed by the k reference nodes as the estimated position of the unknown node.This is actually a k- nearest-neighbor approximation in which all reference nodes have equal weights. (a) Fig.8.k-neighbor proximity. This centroid technique has been investigated using a model with each node having a simple circular range R in an infinite square mesh of reference nodes spaced a distance d apart3).It is shown through simulation that,as the overlap ratio R/d is increased from 1 to 4, 。 the average error in localization decreases from 0.5d to 。 0.25d. . The k-neighbor proximity approach inherits the (b) merit of computational simplicity from the single neigh- bor proximity approach;while at the same time,it pro- Fig.7.Hop count measurement.(a)Per-hop distance measure- vides more accurate localization results statistically. ment.(b)Distance mismatch. 2.1.6 Comparative Study and Directions of Future network is isotropic,unbalanced power consumption Research among nodes will easily create holes in the network. Recently,a distributed methodtol has been proposed A comparative study is presented in this subsection to detect hole boundary by using only the connecti- for existing physical measurement approaches.Table 1 vity information.Based on that work,REPl is pro- provides an overview of these approaches in terms of ac- posed to deal with the "distance mismatch"problem in curacy,hardware cost,and environment requirements. anisotropic networks. All approaches have their own merits and drawbacks, making them suitable for different scenarios. 2.1.5 Neighborhood Measurement Recent technical advances foster two novel ranging The radio connectivity measurement can be con- sidered economic since no extra hardware is needed. Table 1.Comparative Study of Physical Measurements Perhaps the most basic positioning technique is that of one neighbor proximity,involving a simple decision Physical Measurements Accuracy Hardware Computa- of whether two nodes are within the reception range Cost tion Cost Distance RSS of each other.A set of reference nodes is placed in Median Low Low TDoA the network with some non-overlapping (or nearly non- High High Low overlapping)sub-regions.Reference nodes periodically Angle AoA High High Low emit beacons including their location IDs.Unknown Area Single reference Median*Median* Median nodes use the received locations as their own location, Multi-reference Median*Median*High achieving a course-grained localization.The major ad- Hop Count Per-hop distance Median Low Median vantage of such a neighbor proximity approach is the Neighborhood Single neighbor Low Low Low simplicity of computation. Multi-neighbor Low Low Low The neighborhood information can be more useful *depends on the diverse geometric constrains280 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 Fig.7. Hop count measurement. (a) Per-hop distance measure￾ment. (b) Distance mismatch. network is isotropic, unbalanced power consumption among nodes will easily create holes in the network. Recently, a distributed method[40] has been proposed to detect hole boundary by using only the connecti￾vity information. Based on that work, REP[41] is pro￾posed to deal with the “distance mismatch” problem in anisotropic networks. 2.1.5 Neighborhood Measurement The radio connectivity measurement can be con￾sidered economic since no extra hardware is needed. Perhaps the most basic positioning technique is that of one neighbor proximity, involving a simple decision of whether two nodes are within the reception range of each other. A set of reference nodes is placed in the network with some non-overlapping (or nearly non￾overlapping) sub-regions. Reference nodes periodically emit beacons including their location IDs. Unknown nodes use the received locations as their own location, achieving a course-grained localization. The major ad￾vantage of such a neighbor proximity approach is the simplicity of computation. The neighborhood information can be more useful when the density of reference nodes is sufficiently high so that there are often multiple reference nodes within the range of an unknown node[42]. Let there be k refer￾ence nodes within the proximity of the unknown node. As shown in Fig.8, we use the centroid of the polygon constructed by the k reference nodes as the estimated position of the unknown node. This is actually a k￾nearest-neighbor approximation in which all reference nodes have equal weights. Fig.8. k-neighbor proximity. This centroid technique has been investigated using a model with each node having a simple circular range R in an infinite square mesh of reference nodes spaced a distance d apart[43]. It is shown through simulation that, as the overlap ratio R/d is increased from 1 to 4, the average error in localization decreases from 0.5d to 0.25d. The k-neighbor proximity approach inherits the merit of computational simplicity from the single neigh￾bor proximity approach; while at the same time, it pro￾vides more accurate localization results statistically. 2.1.6 Comparative Study and Directions of Future Research A comparative study is presented in this subsection for existing physical measurement approaches. Table 1 provides an overview of these approaches in terms of ac￾curacy, hardware cost, and environment requirements. All approaches have their own merits and drawbacks, making them suitable for different scenarios. Recent technical advances foster two novel ranging Table 1. Comparative Study of Physical Measurements Physical Measurements Accuracy Hardware Computa￾Cost tion Cost Distance RSS Median Low Low TDoA High High Low Angle AoA High High Low Area Single reference Median* Median* Median Multi-reference Median* Median* High Hop Count Per-hop distance Median Low Median Neighborhood Single neighbor Low Low Low Multi-neighbor Low Low Low ∗: depends on the diverse geometric constrains