222 Communication protocols, localization and signal processing techniques for WSANs
Obviously, by increasing the ratio r
/ d (i.e., the range overlap of the anchor nodes), the
accuracy of the location estimate improves.
The more general case where a reduced anchor nodes range overlap and internode con-
straint (cooperation among nodes) exist is more challenging. The work in Doherty, Pister &
Ghaoui, 2001 presents a centralized methodology to solve this problem as a linear or
semi-deﬁ nite program. It is shown that the position estimation error can be dramatically
reduced as the network connectivity increases.
The DV-hop scheme, described in Section 8.4.2 and proposed in Niculescu & Nath, 2001,
is actually a range-free positioning algorithm since distance estimation between unknown
and anchor nodes is performed by hop counting.
In He, Huang, Blum, Stankovic & Abdelzaher, 2003 a range-free positioning algorithm
called APIT is proposed and compared with some of the previous described algorithms
in realistic environments. Results show that APIT performs better when more realistic
radio channel models and random node placement are considered and low communica-
tion overhead is desired.
8.5 Anchor-free localization
Most of the work present in the literature concerning localization in WSNs starts from
the assumption that a non-negligible fraction of nodes in the networks are a priori aware
(a) (b) (c)
Figure 8.21 The feasible region of solutions for the unknown node position (white node) as the
number of anchor nodes (black nodes) increases
Figure 8.20 Proximity-based positioning
Localization and time synchronization techniques for WSANs 223
of their position (anchor nodes). In many applications the anchor nodes are not available
or only relative coordinates among nodes are of interest.
The anchor-free localization problem can be formulated as follows: given a set of nodes
with unknown position and range measurements among neighbours ’ nodes, determine
the (relative) position coordinates of every node in the network.
Unfortunately, this problem is NP-hard. In addition, distributed algorithms are appre-
ciated. Some heuristic algorithms have been proposed to face this problem. For exam-
ple (see Figure 8.22 ), cooperative localization is analogous to ﬁ nding the resting point
of masses (representing the nodes) connected by springs (with length proportional to
distance measurements) (Patwari, Ash, Kyperountas, Hero, Moses & Correal, 2005).
Springs exert forces on the nodes which move until stabilization. The equilibrium point
of masses represents a minimum-energy localization estimate. Force-directed relaxation
methods can be used to converge toward a minimum-energy conﬁ guration. However,
such methods are susceptible to severe false local minima. From that it is important to
start from a reasonably good initial estimation.
In Priyantha, Balakrishnan, Demaine & Teller, 2003 a fully decentralized algorithm called
anchor-free localization (AFL) is proposed. It is composed of two phases. First, an initial
layout is computed to alleviate the false minimum problem. The strategy followed is based
on the observation that many false minima are caused because nodes operating on local
information converge falsely to conﬁ gurations where groups of nodes are topologically
folded with respect to the true conﬁ guration. AFL seeks to conﬁ gure nodes into a ‘ fold-
free ’ conﬁ guration. The second phase consists of the force-directed relaxation method.
The algorithm has been tested by simulation for different node connectivity and dens-
ities as well as distance estimation error conditions. It gives better precision and conver-
gence results than incremental algorithms as the one presented in Savarese et al., 2001.
Figure 8.22 Anchor-free positioning as spring embedder system