747 sensor network operation-1-187-6

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