<figure><img src="image_1.png" /></figure>

HAL
open science

# A Localization Algorithm for Sparse-Anchored WSN in Agriculture

Chunjiang Zhao, Shufeng Wang, Kaiyi Wang, Zhongqiang Liu, Feng Yang, Xiandi Zhang

► To cite this version:

Chunjiang Zhao, Shufeng Wang, Kaiyi Wang, Zhongqiang Liu, Feng Yang, et al.. A Localization Algorithm for Sparse-Anchored WSN in Agriculture. 4th Conference on Computer and Computing Technologies in Agriculture (CCTA), Oct 2010, Nanchang, China. pp.76-86, 10.1007/978-3-642-18333-1_11. hal-01559597

HAL Id: hal-01559597

https://inria.hal.science/hal-01559597

Submitted on 10 Jul 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Localization Algorithm for Sparse-Anchored WSN in Agriculture

Chunjiang Zhao¹, Shufeng Wang¹, Kaiyi Wang¹, Zhongqiang Liu¹, Feng Yang¹, Xiandi Zhang¹

¹ Beijing Research Center for Information Technology in Agriculture, Beijing, China,
100097

{Zhaocj,Wangsf,Wangky,Liuzq,Yangf,Zhangxd}@nercita.org.cn

**Abstract.** The location information is very crucial for the sensing data in modern agriculture. However, positioning errors and sparse anchors are two key problems that should first be solved for the localization of the sensor nodes. We proposed a novel algorithm to tackle with these challenges. When the system of adjacent anchor distance equations is ill, a minimized-stress search algorithm (MSS) can decrease positioning error greatly. A collaborative sparse-anchored scheme (CSA) has an excellent positioning effect on low density of anchor, specifically on marginal sensor nodes. Our experimental result verified validity and accuracy of the algorithm. It improved feasibility and cost of WSN positioning technique, significantly.

**Keywords:** WSN, localization, Sparse anchors, Multi-hop cooperation.

## 1 Introduction

Recent advances in micro-electro-mechanical systems (MEMS) technology, wireless communications, and digital electronics have enabled the development of low-cost, low-power, multifunctional sensor nodes that are small in size and communicate in short distances [1]. These sensor nodes with sensing, data processing, and wireless communicating capabilities can be self-organized together in ad-hoc mode and be deployed in pre-determined or random fashion in inaccessible terrains or disaster relief operations. Therefore there are a wide range of applications for wireless sensor networks (WSN): military, infrastructure security, environment and habitat monitoring, industrial sensing, traffic control, etc [2]. Especially, WSN are applied to varied fields in agriculture to improve the agricultural informatization in recent years [3].

In the last decade, WSN have been increasingly applied in modern agriculture [4]. Sensor nodes can be used for monitoring a wide variety of agricultural parameters that include the following phenomena: temperature, humidity, moisture, lightning condition, soil makeup, livestock ID, and so on [5]. However, the sensing data is not meaningful without the company of the sensing location. Naturally, the localization of WSN nodes is very crucial for sensing data usage. Furthermore,
accurate location might also be useful for routing and coordination purposes in large scale WSN.

The Global Positioning System (GPS) is the most well known location service in use nowadays. The approach taken by GPS, however, is unsuitable for the low-cost, low-power large scale sensor networks nodes in agriculture because of the following reasons: cost, power consumption, inaccessibility, imprecision, size [6].

It is necessary to develop an alternative inexpensive, more applicable localization approach. This paper will present the novel localization algorithm in sparse-anchored WSN.

The rest of the paper is organized as follows: The next section gives a brief explanation of theoretical background. Section 3 is our proposed algorithm of localization system. Section 4 describes the resolution of the sparse-anchored problem. Section 5 is experimental results and analysis. Finally, section 6 concludes the paper.

## 2 Theoretical background

Triangulation, scene analysis, and proximity are the three principal techniques for location sensing [7]. Typically, lateration is the most popular location method that employs triangulation technique. Lateration computes the position of an unknown node by measuring its distance from multiple reference positions. Calculating an object's position in two dimensions requires distance measurements from 3 non-collinear anchors as shown in Figure 1. In 3 dimensions, distance measurements from 4 non-coplanar anchors are required. But, these circles can not intersect at the same point sometime for the error of distance measuring.

<figure><img src="image_3.png" /><figcaption>Figure 1. Lateration localization scheme.</figcaption></figure>

The most classic distributed lateration algorithm is AH-Los algorithm proposed by Andreas Savvides, et al. This algorithm defined three operational primitives: atomic multilateration, collaborative multilateration and iterative multilateration.

If an unknown node have three or more neighboring anchors and have measured the distance to neighboring anchors, atomic multilateration can be deployed to determine the position of unknown node. Figure 2(a) illustrates a topology for which atomic multilateration can be applied.
<figure><img src="image_4.png" /><figcaption>Figure 2. Multilateration examples</figcaption></figure>

The error of estimated position can be expressed as the difference between the measured distance $d_i$ and the estimated Euclidean distance (Equation 1). The $x$ and $y$ are the estimated coordinates for the unknown node. According to the minimal mean square estimate (MMSE) [8], i.e. Equation 2, the optimal solution of $x$ and $y$ can be obtained.

$$f_i(x, y) = d_i - \sqrt{(x - x_i)^2 + (y - y_i)^2} \qquad (1)$$

$$\min(F(x, y)) = \min \sum_{i=1}^{n} f_i(x, y)^2 \qquad (2)$$

If a node has three or more neighboring anchors, an over-determined system with a unique solution for the position of unknown node can be yielded. By setting $f_i(x,y)=0$, squaring and rearranging terms, equation 1 became equation 3.

$$x^2 + y^2 - 2x_i x - 2y_i y = d_i^2 - (x_i^2 + y_i^2) \qquad (3)$$

If unknown node has $k$ neighboring anchors, $k$ equations like equation 3 can be achieved. Then, we can eliminate the $x^2 + y^2$ terms by subtracting the $k$th equation from the rest, depicted as equation 4.

$$2(x_k - x_i)x + 2(y_k - y_i)y = d_i^2 - d_k^2 - (x_i^2 + y_i^2) + (x_k^2 + y_k^2) \qquad (4)$$

This system of equations has the form of $AX = b$ and can be solved using the matrix solution for MMSE.

Collaborative multilateration can be deployed in the situation where the number of 1-hop neighboring anchors is less than 3, but multi-hop anchors can provide adequate information to locate the position of the unknown node. Figure 2(b) illustrates a basic example. The unknown node 1 has two 1-hop anchors and two 2-hop anchors through the unknown node 2. We can build the system of linear equations like equation 4 and then obtain the solution of equations using MMSE.

When an unknown node achieved its position using atomic multilateration or collaborative multilateration, it can inform its neighboring unknown nodes that it has become an anchor. If the informed unknown node satisfies the conditions of atomic
multilateration or collaborative multilateration, it can estimate itself position. This process can be iterative until the positions of all the nodes that can have three or more anchors are estimated eventually. This is iterative multilateration principle.

In this paper, we proposed novel algorithms to improve position error and position ratio under sparse-anchored condition.

## 3 Localization algorithm

AH-Los algorithm eliminates the $x^2 + y^2$ term in equation 3 by subtracting the kth equation from the rest. Essentially, the solution of system is the intersection of common chord equations between ith circle and kth circle. As depicted in figure 3, equations 5 represent 3 circles with each anchor position as center and the distance from the unknown to the anchor as radius. The first equation subtracted from the second equation gives common chord line L1 and The first equation subtracted from the third equation gives common chord line L2. The intersection of line L1 and the line L2 is the estimated position of the unknown node.

$$ 
\begin{aligned}
x^2 + y^2 - 2x_1x - 2y_1y &= d_1^2 - (x_1^2 + y_1^2) \\
x^2 + y^2 - 2x_2x - 2y_2y &= d_2^2 - (x_2^2 + y_2^2) \\
x^2 + y^2 - 2x_3x - 2y_3y &= d_3^2 - (x_3^2 + y_3^2)
\end{aligned}
\qquad (5) $$

<figure><img src="image_5.png" /><figcaption>Figure 3. The intersection of L1 and L2 is the estimated position.</figcaption></figure>

When this common chord lines is parallel to each other, only small error of estimated anchor position can make a very large error of the intersection position. As demonstrated in figure 4, three anchors upside are close to each other and a anchor downside is far from the other anchors, the solution of equations has higher error. Let different anchor equation as the subtrahend, the solution have different error. The red circle represents the real position of the unknown node. Four red asterisks denote four
neighboring anchors of the unknown node. Four blue triangles denote the estimated position with different anchor as the subtrahend.

<figure><img src="image_6.png" /><figcaption>Figure 4. Let different kth as the subtrahend have different error</figcaption></figure>

Our algorithm does not eliminate $x^2 + y^2$ term in equation 3. Setting $z = x^2 + y^2$, we can get the system of equations as follows:

$$ 
\begin{aligned}
z - 2x_1x - 2y_1y &= d_1^2 - (x_1^2 + y_1^2) \\
z - 2x_2x - 2y_2y &= d_2^2 - (x_2^2 + y_2^2) \\
&\vdots \\
z - 2x_ix - 2y_iy &= d_i^2 - (x_i^2 + y_i^2)
\end{aligned} 
\quad (6) $$

The system of equations has the form of $AX = b$ where

$$ A = \begin{bmatrix} 1,-2x_1,-2y_1 \\ 1,-2x_2,-2y_2 \\ \vdots \\ 1,-2x_i,-2y_i \end{bmatrix} \qquad X = [z, x, y]^T $$

$$ \text{and } b = \begin{bmatrix} d_1^2 - x_1^2 - y_1^2 \\ d_2^2 - x_2^2 - y_2^2 \\ \vdots \\ d_i^2 - x_i^2 - y_i^2 \end{bmatrix}. $$

The solution can be solved by $X = (A^T A)^{-1} A^T b$. At the same time, using $\delta = z - x^2 - y^2$ as judge condition, we can judge if the system of equations is ill. When the condition number of the equations is very large, the delta is also very large. This means the position error is too large to locate the node. We proposed the minimized-stress search localization algorithm (MSS) to tackle with this situation.

Before presenting the algorithm, we first make some definitions.

**Definition 1.** The distance between the current position of the unknown $(x,y)$ and
the ith neighboring anchor $(x_i, y_i)$ is $d_{icur}$ and the measured distance to ith neighboring anchor is $d_i$. The stress from ith anchor is $\vec{F}_i$ where

$$ \vec{F}_i = ((1 - d_i / d_{icur}) * (x_i - x), (1 - d_i / d_{icur}) * (y_i - y)) \quad (7) $$

As $d_{icur}, d_i$, the direction of $\vec{F}_i$ is pointed to the ith anchor from current position, vice versa.

**Definition 2.** The resultant stress of the unknown, $\vec{F}$, is composed of every component stress $\vec{F}_i$.

$$ \vec{F} = \vec{F}_1 + \vec{F}_2 + \dots + \vec{F}_i \quad (8) $$

The process of the MSS algorithm is described as follows:

Step 1: when the system of equations 6 is ill, we first select two anchors which the distance between them is the farthest and then compute the intersection of two anchor circles which radius is the measured distance from anchor to unknown node.

Step 2: We select each of intersection as search original position and compute the each component stress $\vec{F}_i$ and then composed the resultant stress $\vec{F}$ by equation 7 and equation 8, respectively.

Step 3: Pulled by the resultant stress $\vec{F}$, each estimated position move to new position $(x_n, y_n)$. Next, we judge if the new position have less distance error than the old position As shown by equation 9, $\vec{F}_x$, $\vec{F}_y$, Lstep denotes x axis component, y axis component and the steplength for moving, respectively.

$$ \begin{gathered} x_n = x_0 + L_{step} * \vec{F}_x \\ y_n = y_0 + L_{step} * \vec{F}_y \end{gathered} \quad (9) $$

$$ \text{Xigma} = \sum_{i=1}^{k} (d_{icur} - d_i)^2 $$

Step 4: If $Xigma_{now} < Xigma_{old}$, $x_0 \leftarrow x_n$, $y_0 \leftarrow y_n$. Otherwise steplength $\leftarrow$ steplength/2 and repeat step 2 for several times.

Step 5: when estimated position cannot move on, we turn $\vec{F}$ 90 degrees clockwise or 90 degrees counter clockwise to test a new marching direction. If we find a new direction, step 2 is repeated again. Otherwise the process is terminated. So we estimated two possible final positions.

Step 6: We compare the two final distance residuals and then select the final position with the smallest residual as the position of the unknown node.

The MSS algorithm have overcome the defect of higher position error when the equations is ill-conditioned and conquered the drawback of one starting point that is easy to get in the local minimum. A sample process of MSS algorithm is demonstrated in the figure 5.
<figure><img src="image_7.png" /><figcaption>Figure 5. The example of MSS algorithm process</figcaption></figure>

## 4 Sparse-anchored localization algorithm

After iterative multilateration localization is repeated, The position of the unknown nodes that only have two anchors or one anchor eventually can not be determined. We proposed to utilize the collaboration of its one or two anchors to locate the position of the unknown.

Under the condition of only two adjacent anchors, the unknown can estimate itself position U or U', as shown in figure 6.

<figure><img src="image_8.png" /><figcaption>Figure 6. Localization algorithm with only two 2-hop anchors</figcaption></figure>

The unknown sent the two possible positions, U and U' to its 1-hop anchors, i.e. A₁ and A₂, and then the one-hop anchors pass the possible positions to the 2-hop anchors, i.e. A₃ and A₄. The two-hop anchors will judge if U or U' is in its maximum sensing range, R_max. Once either of the two possible positions belongs to the maximum sensing range of A₃ or A₄ by computing distance, the unknown node is informed that this position is excluded from the estimated position because A₃ or A₄ have not been its 1-hop anchor. When each of U and U' can not be excluded, their midpoint is taken as the estimated position. This method can be deployed in the larger
scale, such as 3-hop scale or multi-hop scale.

Another case is where the unknown node only has a 1-hop anchor. The previous algorithm will be helpless. We will resort to another method to locate the position approximately.

<figure><img src="image_9.png" /><figcaption>Figure 7. The Localization algorithm with only one 1-hop anchor</figcaption></figure>

As shown in figure 7, the unknown node has one 1-hop anchor and three 2-hop anchors. The circle with the distance *d* as radius has six intersection points with the maximum sensing range of three 2-hop anchors, i.e. I₁, I₂, I₃, I₄, I₅ and I₆. We can compute the distances from the intersection points to three 2-hop anchors, respectively. Once the distance for the intersection point is less than Rmax (the largest sensing range), the intersection point is excluded. Finally, the intersection points, I₁ and I₆, are left. So the estimated position is on the pink arc from I₁ to I₆. We can take the midpoint of the arc or the midpoint of the line from I₁ to I₆ as the estimated position. As this scheme has a larger error, the estimated position should not be taken as anchor in the iterative process.

# 5 Experimental results

To verify our proposed localization algorithm, we randomly generate a scenario with 200 nodes within a square field (100x100) in Matlab. These nodes are deployed randomly in the field and can measure the distances to the adjacent nodes in the sensing range R by RSSI or other ranged methods. The anchor ratio to all nodes is Aratio. To simulate real ranged error, the true distances (d) are blurred with Gaussian noise, er. So the measured distance have the distribution, d*(1+N(0, er)).

When the transmission range of the nodes(R), the range error(er) and anchor ratio (Aratio) is set to 15, 5% and 10%, respectively, the topology is shown in figure 8. The blue triangles represent the anchors, the red circles represent the unknown nodes, and the azury lines represent the wireless connections between the nodes.
<figure><img src="image_10.png" /><figcaption>Figure 8. The topology with R=15, c=5% and A<sub>ratio</sub>=10%.</figcaption></figure>

Figure 9 shows the positioning result of our MSS and CSA algorithms. The starting point of the blue arrows represents the estimated position and the end point of the blue arrows represents the real position. The longer the blue arrow is, the larger the positioning error is.

when there are approximate 9 connectivity degree and 10 percent anchor ratio, AH-
Los algorithm can achieve 90 percent position ratio and 6-7% position error (about
20 cm) [9,10]. But under sparse-anchored conditions, there are higher position error
and lower position ratio.

<figure><img src="image_11.png" /><figcaption>Figure 9. Final position estimation result.</figcaption></figure>

Under the same situation, our algorithms have a higher positioning ratio of 100% and lower average positioning error of 2.45%.
Anchor density has a significant effect on the positioning ratio and error. Contrast to the AH-Los algorithm, the positioning ratio was shown with various anchor density in figure 10. As shown, when the percentage of anchors is low, our MS-CSAL algorithm substantially increased the positioning ratio. These algorithms can not only effectively decrease the number of anchors to lower the cost of WSN, but also improve the localizing of the unknown node on the edge of the networks.

<figure><img src="image_12.png" /><figcaption>Figure 10. Effect contrast between AH-Los and MSS-CSPL</figcaption></figure>

# 6. Conclusion

We have proposed a novel MSS-CSA algorithm for WSN positioning in agriculture. The minimized-stress algorithm improved the positioning precision greatly when the system of multi-anchors positioning equations is ill. The collaborative sparse-anchored localization algorithm has solved the positioning problem of anchor deficiency, special for the unknown node on the edge of WSN in agricultural positioning. Our simulation experiments have verified the effect of the algorithm in terms of positioning ratio and positioning errors. Our future work will be concentrated on the Zigbee-based implementation and analysis of error propagation in agricultural positioning.

# Acknowledgments.

This work is supported by National 11th Five-year Plan for Science & Technology of China under Grant no. 2009BADB6B02.

# References

1. Hautefeuille, Mathieu; O'Mahony, Conor; O'Flynn, Brendan; Khalfi, Krimo; Peters, Frank. A MEMS-based wireless multisensor module for environmental monitoring. Microelectronics Reliability, v 48, n 6, p 906-910, June 2008.
2. Mariño, P.; Fontán, F.P.; Domínguez, M.A.; Otero., S. Viticulture zoning by an experimental WSN. International Journal of Information Technology and Web Engineering, v 4, n 1, p 14-30, January-March 2009.

3. O'Shaughnessy, S.A.; Evett, S.R. Developing wireless sensor networks for monitoring crop canopy temperature using a moving sprinkler system as a platform. Applied Engineering in Agriculture, v 26, n 2, p 331-341, 2010.

4. Matese, A. ; Di Gennaro, S.F. ; Zaldei, A.1; Genesio, L.1; Vaccari, F.P.. A wireless sensor network for precision viticulture: The NAV system. Computers and Electronics in Agriculture, v 69, n 1, p 51-58, November 2009.

5. Siuli Roy, A.D.; Bandyopadhyay, S.. Agro-sense: precision agriculture using sensor-based wireless mesh networks. Proceedings of the First ITU-T Kaleidoscope Academic Conference. Innovations in NGN. Future Network and Services, p 383-7, 2008.

6. Heraud, Jorge A.; Lange, Arthur F. . Agricultural Automatic Vehicle Guidance from Horses to GPS: How We Got Here, and Where We are Going, ASABE Distinguished Lecture Series, p 1-67, 2009.

7. Yuan; Law, Choi Look; Chin, Francois. Construction of local anchor map for indoor position measurement system Zhou. IEEE Transactions on Instrumentation and Measurement, v 59, n 7, p 1986-1988, July 2010.

8. Savvides A, Han C-C, Srivastava MB. Dynamic fine-grained localization in ad-hoc networks of sensors. In: Proc. of the 7th Annual Int'l Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 166-179.

9. W. Greene, Econometric Analysis, Third Edition, Prentice Hall 1997

10. Wang, Fu-Bao; Shi, Long; Ren, Feng-Yuan . Self-localization systems and algorithms for wireless sensor networks. Ruan Jian Xue Bao/Journal of Software, v 16, n 5, May, 2005, p 857-868.

11. Savvides, Andreas; Park, Heemin; Srivastava, Mani B. The bits and flops of the n-hop multilateration primitive for node localization problems.Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications, 2002, p 112-121.