Wireless Sensor and Actuator Networks

222 Communication protocols, localization and signal processing techniques for WSANs

Obviously, by increasing the ratio r

0

/ 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-defi 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

(x

1

, y

1

)

(x

2

, y

2

)

(x

3

, y

3

)

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 fi 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 confi 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 confi gurations where groups of nodes are topologically

folded with respect to the true confi guration. AFL seeks to confi gure nodes into a ‘ fold-

free ’ confi 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.

Node

Spring

Figure 8.22 Anchor-free positioning as spring embedder system