2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION

51

2.3.8 Conclusion and Future Work

We address shortcomings, which are caused by anisotropic network topology and complex terrain, of existing sensor positioning methods. Then, we explore the idea of using multidimensional scaling (MDS) technique to compute relative positions of sensors in a wireless sensor network. A distributed sensor positioning method based on MDS is proposed to get the accurate position estimation and reduce error cumulation. The method works in the manner of estimation–comparison–correction. Comparing with other positioning methods, with very few anchors, our approach can accurately estimate the sensors’ positions in networks with anisotropic topology and complex terrain as well as eliminate measurement error cumulation. We also study the position estimation based on MDS in a centralized paradigm. Experimental results indicate that our distributed method for sensor position estimation is very effective and efficient.

However, we did not analyze the communication costs during the operation of our methods yet. We are doing experiments related to message complexity and power consumption. Results will be reported very soon. We would also like to investigate the positioning problem for mobile sensors in wireless ad hoc sensor networks.

2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION

Duke Lee, Pravin Varaiya, and Raja Sengupta

The location estimation or localization problem in wireless sensor networks is to locate the sensor nodes based on ranging devices measurements of the distances between node pairs. These ranging measurements typically become unreliable when the distance is large; we say that such distances are censored. The section compares several approaches for estimating censored distances with a strategy proposed here called trigonometric k clustering, or TKC.

2.4.1 Background Information

Recent advances in microelectronic and mechanical structures (MEMS) sensors and lowpower radios have inspired proposals to deploy wireless sensor networks for monitoring a spatially distributed physical process such as the environment in a building or the traffic on a highway. In these applications, the network comprises a set of nodes, each consisting of one or more sensors, a processor, and a radio. The sensor measurements are locally processed and forwarded to a central place. To understand the received data, it is necessary to associate the measurements from each node with its physical location.

A significant literature is devoted to localization in wireless sensor networks. Bulusu et al. proposed localization using a grid of landmarks [52]. Niculescu and Nath [53, 54] introduced distributive censored distance estimation with an information exchange strategy similar to the distant vector routing algorithm. Doherty et al. [51] developed localization based on convex optimization. Simic and Sastry [55] devised a simple, distributive method for localization by restricting the connectivity area to a rectangular box. Savvides et al. [56], Savarese and Langendoen [57], and Whitehouse [58] among others called for

52 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

iterative refinement of position estimates using gradient descent algorithms. Nguyen and Sinopoli [59] proposed the use learning theory to cope with noisy observations.

In some situations the locations of the nodes may not be known or may be too costly to determine manually. However, the nodes may have ranging devices used to measure the distances between node pairs. One common way is to use the strength of a signal received by a node to estimate its distance from the transmitter. Another way is to measure the sound wave’s time of flight to infer the distance between transceivers by transmitting ultrasonic wave.

However, measurements from these ranging devices are unreliable when the distance between transmitting and receiving nodes is large. We then say that the distance is censored. In these cases, indirectly estimating the censored distance is a better option. For example, if there are three nodes, A, B, and C, and the distances between A and B and between B and C are not censored but the distance between A and C is censored, it may be better to estimate the latter as the sum of the two previous distances.

This section focuses on algorithms for censored distance estimation, also called multihop distance estimation. These algorithms estimate censored distances using distance measurements of neighboring node pairs. Three algorithms, DV-hop, DV-distance, and Euclidean method, are discussed in [54]. We expand on the discussion of censored distance estimation and introduce new concepts based on trigonometric constraints. In particular, we introduce a new algorithm, called trigonometric k clustering, or TKC. Furthermore, we will compare the performance of various censored distance estimation algorithms using data from a testbed that uses Berkeley Motes [60] and generated using both radio signal strength and ultrasonic wave flight time.

System Model and Notations An anchor node, or an anchor, can measure its position reliably. A floating node is a nonanchor node. We estimate location of target nodes in M- dimensional physical space, Y; V is the set of all nodes; and A is the set of all anchors. The position of node i is p(i ) Y; its measurement is p˜(i ); and the measurement error is

e(i ) = p˜	˜
	(i ) − p(i ). The distance between i and j is d(i, j ); its measurement is d(i, j ); and

= ˜ −

its measurement error is e(i, j ) d(i, j ) d(i, j ). The neighbors of node i, N (i ), is the set of all nodes when the distance from i can be measured reliably. The distance between node i and j is censored if the distance cannot be measured reliably. The following summarizes the notation for the measurements.

p˜i	=	pi + ei			i A
		NULL			otherwise
d˜(i, j )	=	d(i, j )	+	e(i, j )		j Ni
		NULL				otherwise
dˆ(i, j )	=	p˜i − p˜ j				i, j A
		NULL				otherwise
						˜
where δ(i, j ) is a distance estimate of d(i, j ) obtained from measurements {d(i, j )|i, j V }

{ ˆ | } =

and d(i, j ) i, j A . We assume that δ(i, j ) δ( j, i ), i, j V . The network topology is the graph (V , E) where E is the set of distance estimations between nodes labeled by δ(i, j ): An edge exists between node i and node j if δ(i, j ) =NULL.

2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION

53

2.4.2 Distance Measurements

Ranging technologies are ways of measuring the distance between a pair of nodes. We investigate four popular ranging technologies—network connectivity, radio signal strength, RF time of flight, and acoustic time of flight; these differ in their range, accuracy, directionality, and response to obstacles. We conclude this section with a strategy to combine various measurements.

Network Connectivity Network connectivity can be used to approximate the distance between a pair of nodes. For instance, the range of an omnidirectional communication device can be simplified as a circle centered at the device with radius RANGE; this yields,

d(i, j )	≤ RANGE	if(i, j ) E
	> RANGE	otherwise

Network connectivity information can be readily obtained from on-board radios. However, modeling range accurately is difficult due to obstacles and atmospheric conditions. In fact, the range can be quite irregular in shape as shown in [58]. Second, the range may be too coarse for reliable distance estimation—an IEEE 802.11 radio, for example, can communicate over 1-km distance in an open area; in this case, the connectivity information is ineffective for finer-grained localization.

Signal Strength A receiver can estimate its distance from a transmitter by measuring the signal attenuation. Similar to the network connectivity-based solutions, on-board RFbased communication devices can be readily used. However, inaccuracies can result from unpredictable power attenuation due to multipath, interference, fading, and shadowing. This is seen in Figure 2.37, a log–log plot of received signal strength between a pair of Cisco IEEE 802.11b wireless cards with respect to the distance between the cards. The measurements were taken from a slow-moving vehicle with respect to a fixed transmitter in an open area at the UC Berkeley Richmond Field Station. Furthermore, the direction and altitude of the antenna can affect signal strength greatly. According to [56], raising the antenna 1.5 m above ground can increase the radio transmission range from 20 to 100 m.

RF Time of Flight The Global Positioning System (GPS) [61], a widely available technology for localization, uses RF time difference of arrival from four GPS satellites synchronized with atomic clocks. GPS technology is scalable and has a resolution of 2 to 3 m with an error of up to 10 to 20 m. However, there are three main concerns when using GPS technology in wireless sensor networks. First, each GPS receiver needs line-of-sight connections to at least four GPS satellites. Thus localization solutions solely based on GPS readings may not work well indoors or near tall buildings. Second, each receiver needs an accurate clock—an inaccuracy of 1 Ms corresponds to a 300-m error. Third, GPS receivers are still too costly for many sensor network applications and consume a great deal of power. A typical GPS receiver costs around $100 and consumes power in the order of watts [52].

However, with single-chip GPS solutions, such as [62], cost and power consumption are expected to decrease dramatically. Furthermore, if the mobility of sensors is limited, sensors can further reduce the impact of the high-energy consumption by running localization algorithms sparingly. This leads us to believe that the GPS solution can be viable in the

54 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

Figure 2.37 Signal-strength-based ranging.

future for outdoor sensor network applications with moderate accuracy requirement for position estimation.

Acoustic Time of Flight Ranging technologies using acoustic time of flight is used in MIT’s Cricket [42], ActiveBat [63], UCLA’s AHLoS [56, 64], and UC Berkeley’s Motes [58]. This technology is robust against fluctuating received signal strength. Savvides et al. [56] observed error less than 2 cm up to a range of 3 m. Data collected by Whitehouse [65] also showed reliability of the measurement—less than a 10-cm error up to the distance of 5 m in the best case. The error varied somewhat between calibration locations and measurement locations (Section 2.4.5). However, compared to RF technologies, acoustic time-of-flight technologies are more susceptible to atmospheric conditions, shorter in range, higher in reflection coefficients, and less able to penetrate into solid objects such as walls.

Furthermore, acoustic time-of-flight technology needs time synchronization between transceivers. Because a global time synchronization is difficult to achieve, most wireless sensor network systems including [42], [63], [56], and [58] use an RF signal as a time synchronizing signal. A transmitter sends an RF signal and an acoustic signal at the same time; and a receiver measures the time difference of arrival of the two signals. For this to work, the algorithm must correctly identify which acoustic signal corresponds to which RF signal.

Calibration Calibration is one major challenge of ranging in wireless sensor networks. As mentioned in [66], an uncalibrated wireless communication radio can transmit twice the power of another radio. In addition, the characteristics of acoustic and RF signals vary

2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION

55

significantly depending on the terrain. As noted earlier, raising the antenna 1.5 m above ground can increase the radio transmission range from 20 to 100 m.

Furthermore, the cost of each wireless sensor must be kept at a minimum; and in many applications on-site calibration is difficult due to the inaccessibility of the terrain. One approach is to predict the calibration coefficient from simulated settings. Whitehouse [58] advocates calibration of transmission and reception gains for each transceiver by linear regression using all transmission and reception information.

Distance Estimation According to the model in Section 2.4.1, we have up to three mea-

ˆ	˜	˜
surements for d(i, j ) : d(i, j ), d(i, j ), and d( j, i ). If the joint probability density function
f is known, the maximum-likelihood estimate of δ(i, j ) of d(i, j ) is
	max	ˆ	˜	˜	(2.9)
δ(i, j ) = arg d(i, j )		f [d(i,	j ), d(i, j ), d( j, i )|d(i, j )]

Suppose that e(i ), e(i, j ), and e( j, i ) are independent Gaussian random variables, that

= = = ˆ

is, e(i ) N (0, σp ), e(i, j ) N (0, σdi j ), and e( j, i ) N (0, σd ji ). Then VAR[d(i, j )] is

ˆ

VAR[e(i )] + VAR[e j ]. Thus, d(i, j ) = N [d(i, j ), 2σp ]. The maximum-likelihood estimate

for d(i, j ) is δ(i, j ) such that

∂

ˆ

˜

˜

∂δ(i, j ) ln f (d(i, j ), d(i, j ), d( j, i )|δ(i, j )) = 0

This reduces to

ˆ

j )

˜

˜

d(i, j ) − δ(i,

+

d(i, j ) − δ(i, j )

+

d( j, i ) − δ(i, j )

=

0

2σp

σd ji

σdi j

And we get an explicit expression for δ(i, j ):

ˆ

˜

˜

δ(i, j )

=

σdi j σd ji d(i, j ) + 2σp σd ji d(i

, j ) + 2σp σdi j d( j, i )

σdi j σd ji + 2σp σdi j + 2σp σd ji

2.4.3 Censored Distance Estimation

A ranging device for localization is useful within a limited range. Distance estimates outside this range are censored. The following example demonstrates the importance of censored distance estimation. Suppose the (i, j )th element of matrix (2.10) is the estimated distance between nodes i and j , 1 ≤ i, j ≤ 4. The censored distances are marked NULL in the matrix. If we ignore the knowledge that δ(1, 2) is censored, it would be impossible to distinguish between the two configurations of Figure 2.38 using the distance estimates (2.10):

0NULL δ(1, 3) δ(1, 4)

		NULL	0	δ(2, 3)	δ(2, 4)		(2.10)
		δ(3, 1)	δ(3, 2)	0	δ(3, 4)
	δ(4, 1)		δ(4, 2)	δ(4, 3)	0

56 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

3		3
d(1,3)
d(3,2)			d(3,2)
1	d(3,4)	d(1,3)
d(3,4)
2		d(4,2)	2
d(1,4)
d(4,2)		d(1,4)	1
4	4

Figure 2.38 Two acceptable configurations specified by (2.10).

Simple Substitution Method A censored distance between a pair of nodes can be replaced by a value based on prior knowledge about topology and ranging technologies. We call this the simple substitution method. For instance, we can replace censored distances with an average of {d(i, j )|d(i, j ) > RANGE}. Suppose δ(i, j ) = [({d(i, j )|d(i, j ) > RANGE}] and δ(i, j ) < d(1, 2). We estimate location of nodes in two-dimensional physical space (M = 2). If all measurements are accurate, node placements that satisfies the censored distance estimate δ(i, j ) and (2.10) requires a three-dimensional space as in Figure 2.39. Projecting this three-dimensional placement onto the two-dimensional physical space reduces estimated distances between nodes: In the figure, node 1 is projected closer to node 3 and node 4 than indicated by δ(1, 3) and δ(1, 4), respectively. One can do better by incorporating more observations from neighboring nodes, as we discuss next.

Shortest-Hop Method In a network with evenly distributed nodes, the shortest-hop count in (V , E) multiplied by an estimated hop length can effectively estimate the distance between nodes. One challenge is to restrict the connectivity to achieve a good resolution while maintaining a set of core neighbors. To see the reason for restricting connectivity, consider a fully connected network. In that network, connectivity information is ineffective in discriminating between nearby nodes from far-away nodes. Another challenge is to estimate the average hop length. DV-hop [53] is a distributed algorithm, wherein anchors

d(1,3)
	3
r	d(3,2)

1	d(1,4)
	d(3,4)

2

d(4,2)

4

Figure 2.39 Inaccuracies in simple substitution.

2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION		57
	3
d(1,3)	d(3,2)
1	2
d(1,4)	d(4,2)

4

Figure 2.40 Preference of negative error for shortest-path algorithm.

estimate the hop length by averaging hop length to other anchors; and nodes obtain average hop length from their nearest anchor.

Shortest-Path Method For dense networks with relatively accurate ranging devices, the shortest-path length [along the graph (V , E)] between any two nodes can be used to approximate the distance between them. Because the shortest path length is greater than or equal to the straight-line distance between them, there is a tendency for the shortestpath method to overestimate the distance. However, this tendency is partly balanced by the algorithm’s tendency toward negative error when minimizing over various paths. To illustrate, the shortest path estimate of d(1, 2) in Figure 2.40 is

δ(1, 2)	=	δ(1, 3)	+ δ(3, 2)	if δ(1, 3) + δ(3, 2) < δ(1, 4) + δ(4, 2)
		δ(1, 4)	+ δ(4, 2)	otherwise

If δ(1, 3), δ(3, 2), δ(1, 4), and δ(4, 2) are unbiased, the shortest-path algorithm tends to underestimate path lengths because it always picks the shorter of the two equal-length paths.

Lemma 2.4.1 If δ(i, j ) is an unbiased estimate of d(i, j ) for all i, j V , the expected value of the output of the shortest-path algorithm is less than or equal to the shortest-path length.

PROOF	We	denote 2pk = [k1, k2, . . . , kMk ]		to be	kth path between two fixed
nodes. Since		min : R → R is a	concave	function, Jensen’s inequality implies
E{mink [	l δ(kl , kl+1)]} ≤ mink {E[		l δ(kl , kl+1)]}. But		since E[δ(i, j )] = d(i, j ), we
have E{mink [		l δ(kl , kl+1)]} ≤ mink [	l d(kl , kl+1)].

2.4.4 Trigonometric Censored Distance Estimation

We discuss strategies to estimate censored distances using trigonometric constraints from two adjoining triangles. We focus on techniques on two-dimensional physical space. As shown in Figure 2.38, δ(1, 3), δ(1, 4), δ(3, 2), δ(4, 2), and δ(3, 4) in (2.10) form two adjoining triangles (δ(3, 2), δ(4, 2), δ(3, 4)) and (δ(3, 4), δ(1, 3), δ(1, 4)). Using the law of cosine, δ(1, 2) can be identified up to the ambiguity shown in the figure. This trigonometric constraint of two adjoining triangles is the basis for the trigonometric censored distance

58 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

estimation. To generalize, we relabel nodes 1, 2, 3, and 4 of Figure 2.38 as nodes i, j, k, and l, respectively. Using the new notation, the localization problem is restated: find δ(i, j ) given l and k, such that δ(i, k), δ(k, j ), δ(i, l), δ(l, j ), and δ(k, l) are defined. The following equations can be derived using the law of cosine:

θ

=

cos−1

δ(k, j )2 + δ(k, l)2 − δ(l, j )2

jlk

2δ(k, j )δ(k, l)

θ

=

cos−1

δ(i, k)2 + δ(k, l)2 − δ(i, l)2

ilk

2δ(i, k)δ(k, l)

θilminj

= min(|θilk − θ jlk |, |θilk + θ jlk |)

θilmaxj

= max(|θilk − θ jlk |, |θilk + θ jlk |)

δ(i, j )min =

δ(i, k)2

+ δ(k, j )2 − 2δ(i, k)δ(k, j ) cos θ minjlk

δ(i, j )max =

δ(i, k)2

+ δ(k, j )2 − 2δ(i, k)δ(k, j ) cos θ maxjlk

These equations produce two random variables, δ(i, j )min and δ(i, j )max, corresponding to the two possible configurations as shown in Figure 2.38. One of the two possible configurations corresponds to the desired estimate. The following algorithms, called trigonometric resolution methods, decide between δ(i, j )min and δ(i, j )max by attempting to find the true configuration.

Trigonometric Resolution Methods Trigonometric resolution methods resolve the ambiguity between the two configurations shown in Figure 2.38.

Random Resolution Method The random resolution method chooses between the two configurations at random. This method is simple and does not give preference to δ(i, j )min or δ(i, j )max. In a well-connected network where multiple pairs of node l and node k that satisfy such configuration can be found for each node pair i and j , the random resolution method often produces more accurate results than those of more sophisticated algorithms with a bias toward δ(i, j )min or δ(i, j )max.

Threshold Resolution Method The threshold resolution method uses the knowledge of the ranging device’s ability to measure the distance between a pair of nodes as a function of the distance between them. Suppose that P(d) represents the probability that a pair of nodes at distance d from each other can measure the distance between them. Using P(d) we can choose between δ(i, j )min and δ(i, j )max by

δ(i,	j )max	if P(δ(i, j )min) > P(δ(i, j )max)
δ(i, j ) = δ(i,	j )min	otherwise

Using the concept above, we can devise a simple filtering method by assuming a value for RANGE: δ(i, j )max > RANGE implies that δ(i, j ) = δ(i, j )min.

Euclidean Method The Euclidean method of Niculescu and Nath [53] is based on the observation that choosing between the ambiguities is equivalent to choosing between one

2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION

59

of two partitions of the plane separated by the line connecting node l and node k; then node j is likely to be in the same partition as node i if a majority of N j is connected to node i . More specifically,

δ(i, j )	=	δ(i, j )max	if 2|Ni ∩ N j | < |(Ni N j ) − (Ni ∩ N j )|
		δ(i, j )min	otherwise

We found from our experiments that the Euclidean method is robust when distance measurements are accurate. Euclidean method slightly outperforms the random resolution method in sparse networks and slightly underperforms the random resolution method in dense networks.

Degenerate Triangle Method Suppose (δ(k, j ), δ(l, j ), δ(k, l)) or (δ(k, l), δ(i, k), δ(i, l)) is a degenerate or an approximately degenerate triangle. If (δ(k, j ), δ(l, j ), δ(k, l)) or (δ(k, l), δ(i, k), δ(i, l)) approximately form a line, then the triangle is degenerate. From this, we can estimate the distance without ambiguity. If δ( j, k), δ( j, l), and δ(l, k) forms a line then

if (abs(δ(l, k) − (δ(l, j ) + δ( j, k))) ≈ 0)

δ(i, j ) = min((δ(l, j ) + δ(l, i )), (δ( j, k) + δ(i, k)))

k)

+

δ( j, k)))

≈

0)

elseif (abs(δ(l, j ) − (δ(l, 2

, k)

2

2

)/(2

δ(i, k)*δ(l, k)))

θ = π − a cos((δ(l, k)

+ δ(i

− δ(l, i )

δ(i, j )

=

δ(i, k)

2

+ δ( j, k)

2

− 2*δ(i, k)*δ( j, k)* cos(θ )

else

θ = π − a cos((δ(l, k)2

+ δ(l, i )2 − δ(i, k)2)/(2*δ(l, i )*δ(l, k)))

δ(i, j ) =

δ(l, i )2 + δ(l, j )2 − 2*δ(l, i )*δ(l, j )* cos(θ )

Multiple Trigonometric Resolution Methods

Let T (i, j ) denote a set of all (l, k)

for each unknown δ(i, j ) for which δ(i, k), δ(k, j ), δ(i, l), δ(l, j ), and δ(k, l) exist. Multiple trigonometric resolution methods estimate d(i, j ) given {δ(i, k), δ(k, j ), δ(i, l), δ(l, j ), and δ(k, l)|(l, k) T (i, j )}.

Averaging We can average estimates obtained from trigonometric resolution algorithms to obtains δ(i, j ). Assuming that estimates obtained from trigonometric resolution methods correspond to the true configuration, we hope to obtain a better estimate by averaging. However, we have no guarantee that each estimate is obtained from the true configuration. The next algorithm, trigonometric k clustering, tries to correct the wrong guesses on the true configuration by a refinement process.

Trigonometric k Clustering Trigonometric k clustering (TKC) obtains δ(i, j ) by refin-

ing the choices between δ(i, j )min(l,k) and δ(i, j )max(l,k), (l, k) T (i, j ) using a variant of the k-clustering algorithm. The intuition is based on the assumption that every pair contains a

random variable that corresponds to the true configuration. With small estimation errors, each pair is likely to contain an element that is close to the unknown d(i, j ). TKC attempts to identify clusters among the pairs, such that a cluster is formed near d(i, j ). The following is the pseudocode for the variant of the k-clustering algorithm used by TKC. We start out

60 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

with an estimate on the distance that may be obtained from any censored distance estimation algorithm.

1.We form a cluster by selecting one from each pair closer to the current estimate for d(i, j ).

2.If there is no change in the membership of the cluster, exit; otherwise, continue.

3.We set the mean of cluster as the new estimate for d(i, j ), and go back to the first step.

This algorithm is guaranteed to converge since (2.11) is monotonically decreasing, and there are only finitely many values for (2.11):

		1			2
	(l,k) T (i, j ) δ(i, j )(l,k) −		(l,k) T (i, j ) δ(i, j )(l,k)		(2.11)
		|T (i, j )|

2.4.5 Experimental Results

All ranging data used below are collected by Whitehouse and presented in his study [65]. The experimental data are calibrated using a method developed by Whitehouse [66]. From the analysis of the experimental data we attempt to gain an insight into the performance of ranging devices and behavior of censored distance estimation algorithms. Furthermore, we establish disErr (2.12) as a performance metric for censored distance estimation algorithms:

disErr =	1		d(i, j ) − δ(i, j )	(2.12)
	|V |2 i, j V

To investigate the usefulness of disErr (2.12) as a performance measure of censored distance estimation algorithms, we used distance estimates obtained from each algorithm to obtain position estimates. In the analysis, disErr (2.12) is compared with posErr (2.13), a sum of position errors from a position estimation. To obtain position estimates, we used multidimensional scaling, or MDS [67].

posErr =	1		p(i ) − p˜(i )	(2.13)
	|V | i V

Using the experimental data, we compare the performance of shortest-hop (Section 2.4.3), shortest-path (Section 2.4.3), and trigonometric resolution methods (Section 2.4.4). We denote shortest hop as Hop and the shortest-path algorithm as Path. As for the trigonometric resolution methods, we focus on four configurations: MEuclid, MRand, TKCEuclid, and TKCRand. MEuclid takes the mean of results from the Euclidean method (Section 2.4.4). TKCRand applies the trigonometric k clustering (Section 2.4.4) starting from an initial estimate obtained from MRand.

Signal-Strength-Based Ranging We discuss two experiments carried out in an open, grassy field at the west gate of the UC Berkeley campus and in an office space in the east wing of the Intel Lab at Berkeley. Information about the experiment can be found at [68]. Berkeley Mica Motes [69] were placed on a 4 × 4 grid with 3-m spacing in the field and a

2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION

61

Measured distance (m)

12			Outside5/1,2,3,4,					12			Lab2/1,3,4,5,
10							(m)	10
								8
6							distance
								6
8
4							Measured	4
2								2
0								0
0	2	4	6	8	10	12		0	2	4	6	8	10	12
			True distance (m)								True distance (m)

(a)

(b)

Figure 2.41 Accuracy of signal strength ranging: (a) outside and (b) lab.

3 × 6 grid with 2-m spacing in the lab. They were intentionally placed carelessly to achieve random antenna orientation. Using ChipCon CC1000 radios on-board on the Mica Motes, each node took turns transmitting 10 messages, and the signal strengths of transmitted signals were collected at each node. The experiments were repeated five times; each time the motes were shuffled around on the grid.

We used four of five experiments to find a mapping from received signal strength to distance and used the remaining experiment for measurements. Figure 2.41 is a scatter plot of distance measurements against their true distances. Outside5/1,2,3,4 means that experiment 1, 2, 3, and 4 were used to derive coefficients for distance measurements in experiment 5. In the figure, points below the true distance 45◦ line are underestimates; and points above the line represent overestimates. The standard deviations of errors are plotted as brackets around the true distance line. As seen by the large standard deviations, the distance measurements from the ChipCon CC1000 radio are not very accurate. The lab measurements are more inaccurate.

Table 2.2 summarizes the results for signal-strength-based distance estimation technique using ChipCon radios. The posErr (2.13) is obtained from MDS using four corner nodes at (0,0), (0,9), (9,0), and (9,9) as anchor nodes. With respect to posErr (2.13), Path and TKCRand perform equally well outdoors. However, Path does poorly indoors compared to TKCRand, when ranging errors are increased. Figure 2.42a shows placements of nodes in Outside5/1,2,3,4 obtained by MDS and TKCRand. As shown in Figure 2.42b the position

Table 2.2 Chipcon Radio Signal-Strength-Based Ranging Experimental Results

Measured/Trained	Hop	Path	MRand	MEuclid	TKCRand	TKCEuclid
			dis Err
Outside5/1,2,3,4	0.090	0.056	0.058	0.070	0.058	0.068
Lab2/1,3,4,5	0.102	0.094	0.095	0.096	0.094	0.096
			posErr
Outside5/1,2,3,4	3.063	1.281	1.499	1.747	1.193	1.720
Lab2/1,3,4,5	3.003	2.935	3.023	2.529	2.488	2.529

62 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

Meters

12			LMDS,TKCRand						10		LMDS,TKCRand
10									8
8									6
6								Meters
4									4
2									2
0									0
−2−4	−2	0	2	4	6	8	10		−2−2 −1 0	1	2	3	4	5	6	7
			Meters								Meters
				(a)								(b)

Figure 2.42 Position estimation based on signal strength ranging: (a) outside and (b) lab.

estimates obtained indoors are terribly inaccurate. In fact, MDS/TKCRand does worse than a simple position estimation algorithm that places all floating nodes at (2, 4), the center of all anchors.

Ultrasonic-Based Ranging The ranging data were collected in three different environments: grass, grasscups, and pavement. In the grasscups environment, nodes were placed on top of cups on the grass to increase the range area. The topologies were the same for all three experiments. We focus on four configurations, namely Grass Grasscups, Grass Pavement, Grasscups Grass, and Grasscups Pavement. Grass Grasscups were a set of distance measurements taken in the grass environment with calibration coefficients obtained from the grasscups environment. As shown in Figure 2.43, the accuracy of the acoustic-based estimation is significantly better than that of signal-strength-based ranging from the ChipCon CC1000 radio.

Table 2.3 summarizes the results for time difference of arrival based on a distance estimation technique using concurrent ultrasonic and RF signals. The posErr in Table 2.3 is obtained from MDS using the censored distance estimation algorithms with four corner nodes at (3.08, 2.88), (0.45, 0.11), (4.24, 3.95), and (4.08, 1.22) as anchor nodes. TKCRand, TKCEuclid, and Path all perform well with respect to posErr in the grasscups environment. However, TKCEuclid and Path do not do as well in the grass environment compared with TKCRand. This is due to increased error in the grasscups environment compared to the grass environment. In this example, TKCRand is more robust against ranging errors. Figure 2.44 shows placements obtained by TKCRand.

Figure 2.45 is a histogram of posErr divided by the corresponding disErr from all experimental results. It is apparent that there is a correlation between disErr and posErr. We make the cautious claim that disErr is a good performance metric for a censored distance estimation algorithm. The ultimate performance metric for a censored distance estimation algorithm, however, needs to be determined from a metric based on positional error. The choice of the localization algorithm and the choice of the performance metric for position estimation can affect the preference for the censored distance estimation performance metric.

2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION

63

Grass/Grasscups

		4.5
	(m)	4
		3.5
	distance
		3
		2.5
	Measured	2
		1.5
		1

	0.5
	0
	0	0.5	1	1.5	2	2.5	3	3.5	4	4.5
				True distance (m)
						(a)
	6			Grasscups/Grass
(m)	5
distance	4
Measured	3
	2
	1
	0 0		1	2		3		4	5	6

		4.5			Grass/Pavement
(m)		4
		3.5
distance
		3
		2.5
Measured
		2
		1.5
		1
		0.5
		0
		0	0.5	1	1.5	2	2.5	3	3.5	4	4.5
					True distance (m)
							(b)
		6			Grasscups/Pavement
	(m)	5
	distance	4
	Measured	3
		2
		1
		0
		0		1	2		3	4		5	6

True distance (m)	True distance (m)
(c)	(d )

Figure 2.43 Accuracy of acoustic ranging: (a) grass trained on grasscups, (b) grass trained on pavement, (c) grasscups trained on grass, and (d) grass trained on pavement.

Table 2.3 Acoustic-Based Ranging Experimental Results

Measured/Trained	Hop	Path	MRand	MEuclid	TKCRand	TKCEuclid
			dis Err
Grass/Pavement	0.020	0.003	0.017	0.017	0.004	0.008
Grass/Grasscups	0.020	0.005	0.014	0.017	0.005	0.009
Grasscups/Pavement	0.038	0.002	0.003	0.008	0.002	0.002
Grasscups/Grass	0.038	0.003	0.004	0.009	0.003	0.003
			posErr
Grass/Pavement	0.679	0.091	0.479	0.638	0.072	0.405
Grass/Grasscups	0.695	0.090	0.468	0.642	0.088	0.432
Grasscups/Pavement	1.430	0.052	0.069	0.108	0.045	0.045
Grasscups/Grass	1.555	0.067	0.066	0.105	0.066	0.066

64 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

Meters

LMDS,TKCRand 5

4.5

4

3.5

3

2.5

2

1.5

1

0.5

0

0	0.5	1	1.5	2	2.5	3	3.5	4	4.5
				Meters

(a)

Meters

LMDS,TKCRand 5

4.5

4

3.5

3

2.5

2

1.5

1

0.5

0

0	0.5	1	1.5	2	2.5	3	3.5	4	4.5
				Meters

(b)

Meters

LMDS,TKCRand 5

4.5

4

3.5

3

2.5

2

1.5

1

0.5

0

0	0.5	1	1.5	2	2.5	3	3.5	4	4.5
				Meters

(c)

Meters

LMDS,TKCRand 5

4.5

4

3.5

3

2.5

2

1.5

1

0.5

0

0	0.5	1	1.5	2	2.5	3	3.5	4	4.5
				Meters

(d )

Figure 2.44 Position estimation based on acoustic ranging: (a) grass trained on grasscups, (b) grass trained on pavement, (c) grasscups trained on grass, and (d) grasscups trained on pavement.

posErr / disErr

8
7
6
5
4
3
2
1
0	15	20	25	30	35	40	45	50	55
10

Figure 2.45 disErr as a metric for censored distance estimation algorithm: histogram of posErr/disErr.

2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION

65

	0.09		Acoustic Measurement Variance									20	ChipCon CC1000 Measurement Variance
																		Outside5/1,2,3,4
						Grass--Pavement
												18
																		Lab2/1,3,4,5
	0.08					Grass--Grasscups
)						Grasscups--Pavement					)	16
2	0.07					Grasscups--Grass					2
(m											(m	14
error	0.06										error
							0.004x 2					12
	0.05
of											of	10
Variance	0.04						0.003x 2				Variance
												8
	0.03						0.002x 2					6
	0.02											4					2.63164
							0.001x 2
	0.01											2
	0											0
	0.5	1	1.5	2	2.5	3	3.5	4	4.5	5		2	3	4	5	6	7	8	9	10	11
					True distance (m)											True distance (m)
					(a)												(b)

Figure 2.46 Modeling of ranging error: Variance of ranging error versus distance: (a) acoustic and (b) signal strength.

2.4.6 Simulation Results

Our simulation models are based on the experimental results in the previous section. In the case of acoustic ranging, we model the ranging error on a Gaussian random variable with variance proportional to the square of the distance. Given a distance estimate δ(i, j ), the variance of error DVAR is modeled as

DVAR = α × δ2(i, j )

(2.14)

To obtain the scaling constant α, we fit square curves to the sample variance curve obtained from acoustic ranging data, as shown in Figure 2.46.

As for the signal strength data, we assume the variance to be constant over the distance measurements up to 11 m. We assume that the ranging area is roughly symmetrical. Figure 2.47 plots the probability of reliable distance measurement as a function of distance. For

	1	Acoustic Measurement Success Rate							1
of distance measurement						Grass--Pavement
	0.9							distance measurement
						Grasscups--Grass			0.95
	0.8
									0.9
	0.7
	0.6								0.85
	0.5								0.8
	0.4				exp[−0.35(x−1.3725)2]				0.75
	0.3
Success								Success of	0.7
	0.2
	0.1								0.65
	0								0.6
		1	2	3	4	5	6
	0

ChipCon CC1000 Measurement Success Rat

				Outside5−1,2,3,4
				Lab2−1,3,4,5
		exp[−0.0035(x−1.0607)2]
0	2	4	6	8	10	12

True distance (m)	True distance (m)
(a)	(b)

Figure 2.47 Modeling of ranging area: Successful ranging versus distance: (a) acoustic and (b) signal strength.

66	SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION
Table 2.4 Signal-Strength-Based Ranging Simulation Results
		Hop	Path	MRand	MEuclid	TKCRand	TKCEuclid
8 × 8gvc				dis Err
		0.0265	0.0296	0.0099	0.0206	0.0059	0.0078
9-5 × 9-5g1c		0.0169	0.0081	0.0050	0.0055	0.0049	0.0049
10 × 10g3c		0.0228	0.0575	0.0745	0.0636	0.0168	0.0091
8 × 8gvc				posErr
		2.7226	7.0072	0.8169	1.3477	0.5107	0.6285
9-5 × 9-5g1c		2.9364	0.6592	0.4691	0.5613	0.4750	0.4495
10 × 10g3c		2.2554	4.5291	7.3757	3.2778	1.6357	1.0763

the simulations, we approximate the success rate curve by an exponential curve, as shown in Figure 2.47. We censor distances greater than 12 m because of the lack of experimental data.

As explained in more detail below, we find that TKC is a reliable censored distance estimation algorithm. TKCEuclid tends to perform slightly better than TKCRand if ranging measurements are accurate or network is sparse. When network connectivity is high, TKCRand seems to outperform all other algorithms. The performance of Path is not consistent because its tendency to overestimate (path curvatures) and its tendency to underestimate (preference of negative error) need to be balanced. Low network connectivity, uniformly placed nodes, and large ranging error all increase the comparative performance of Hop against other algorithms. However, the performance of Hop fell below Path in most of the cases.

Signal-Strength-Based Ranging Simulation Table 2.4 summarizes results from simulation using the signal strength ranging model. The first experiment, 8 × 8vc (Figs. 2.48 and 2.49), is run on a 8 × 8 grid with varying spacing with four anchor nodes at (0,0), (0,11.2), (11.2,0), and (11.2,11.2). This is a well-connected network, as all nodes are reachable in two hops indicated by Figure 2.48a—only one estimate of distance is evaluated using Hop. Both TKCEuclid and TKCRand perform well, as plotted in Figure 2.49. TKCRand performs slightly better than TKCEuclid, since the network is well-connected and ranging error is relatively high. The performance of Path is poor due to the large variance of ranging error. The preference for negative error is illustrated in Figure 2.48b.

The topology for the second experiment, 9-5 × 9-5g1c (Figs. 2.50 and 2.51), is a 9 × 9 grid with a 5 × 5 hole in the middle. Anchors are located at (0, 0), (0, 8), (8, 0), and (8, 8). Path greatly underestimates the distances. Trigonometric-constraints-based algorithms outperform path-based algorithms due to the dominance of ranging error and uneven topology.

The third experiment, 10 × 10g3c (Figs. 2.52 and 2.53), is on a 10 × 10 grid with 3-m spacing. The anchors are located at (0, 0), (0, 27), (27, 0), and (27,27). Path performs less well due to increased underestimation caused by increased size of the network. TKCEuclid performs better than TKCRand, since the network is not as well-connected as in the first example.

2.4 TRIGONOMETRIC K CLUSTERING (TKC) FOR CENSORED DISTANCE ESTIMATION

67

Estimated distance (m)

Estimated distance (m)

16													Hop
14																																																(m)
12																																																distance
10																																																Estimated
8
6
4
2
0
0		2	4			6			8									10						12								14														16
							True distance (m)
															(a)
16											TKCRand
14																																																(m)
12																																																distance
10
8																																																Estimated
6
4
2
0
		2	4			6			8									10						12								14														16
0

True distance (m)

(c)

Path

16

14

12

10

8

6

4

2

0 0 2 4 6 8 10 12 14 16

True distance (m)

(b)

TKCEuclid

16

14

12

10

8

6

4

2

0

0	2	4	6	8	10	12	14	16
			True distance (m)

(d )

Figure 2.48 Distance estimations (8 × 8gvc: 8 × 8, variable spacing, ChipCon CC1000): (a) shortest hop, (b) shortest path, (c) TKC random, and (d) TKC Euclidean.

Acoustic-Based Ranging Simulation	Table 2.5 summarizes the results from sim-
ulations using acoustic ranging model. In	the first experiment, 8 × 8va (Figs. 2.54

and 2.55), nodes are placed on a 8 × 8 grid with varied spacing. The anchors are located at (0, 0), (0, 5.6), (5.6, 0), and (5.6, 5.6). In this example, TKCEuclid and TKCRand perform well (Fig. 2.55) thanks to the superiority of acoustic ranging compared to signal-strength- based ranging. Path performs better than with signal-strength-based ranging because the error from its preference of negative error is reduced. However, TKCEuclid and TKCRand both outperform Path because the uneven density of nodes negatively affects the performance of Path.

The second experiment (Figs. 2.56 and 2.57), denoted by 10 × 10g1a, nodes are placed on 10 × 10 grid with 1-m spacing with anchors at (0,0), (0,8), (8,0), and (8,8). In this example, TKCEuclid is clearly the best, as plotted in Figure 2.57. The Euclidean method is superior to the random resolution method due to accuracy of measurements. Poorer performance of Path comes from its preference for negative error as shown in Figure 2.56. As the number of hops increases, error due to the negative bias also increases.