Improved Normalized Collinearity DV-Hop Algorithm for Node Localization in Wireless Sensor Network

Abstract

In recent years, collinearity theory is widely used in large-scale sensor network. When the anchor nodes are located at almost a straight line, the collinearity phenomenon will happen and usually cause negative influence on positioning accuracy. From detailed analysis of the relation between DV-Hop localization error and the collinearity, we proposed to select the anchor nodes which can meet the condition of hop count threshold and collinearity to participate in the localization procedure. Since there is uncertain situation that the anchor node's region is hard to be decided for the sensor nodes in one hop area, Voronoi diagram is adopted to divide the sensor network into several regions. Then, we can get the anchor node information in each Voronoi polygon. With this information and the collinearity condition, we can estimate the unknown node's position with relatively higher accuracy. Compared with the traditional DV-Hop and collinearity algorithm, our proposed algorithm can get better positioning accuracy in both homogeneous network and anisotropic network.

1. Introduction

Recently, wireless sensor network (WSN) is widely used in many fields such as disaster rescuing, environment monitoring, and target tracking. As a fundamental issue in sensor network, the node localization technology has become one of the research hot spots in WSN fields [1, 2].

According to distance measurement method, the sensor network localization is divided into two categories including range-based localization and range-free localization. The former mainly consists of time of arrival (TOA), time difference of arrival (TDOA), angle of arrival (AOA), and received signal strength (RSS) positioning. Range-free localization methods mainly consist of centroid algorithm, DV-Hop algorithm, amorphous algorithm, and APIT algorithm.

Based on the range-free localization mechanism, unknown node's location can be acquired with little consideration of environmental factors because it is unnecessary to calculate the actual distance or angle. The accuracy can meet the requirement for most of wireless sensor network applications, while reducing the requirement of node hardware and the cost greatly [3]. As a typical range-free localization method, DV-Hop algorithm has no extra requirement for WSN nodes and is characterized by such advantages as simple realization, low cost, and small payment.

This paper proposes a new method based on DV-Hop algorithm and Voronoi diagram (VNC-DV-Hop, Voronoi diagram-based NC-DV-Hop). We utilize Voronoi diagram to divide the network into several areas and then calculate the groups of anchor nodes conforming to threshold condition. Best sensor node groups are selected to localize the unknown nodes. This method has more advantages in calculation complexity and better position estimation in sensor network, including homogeneous network and anisotropic network. The rest of the paper is organized as follows. Section 2 briefly introduces related research. Section 3 analyzes the errors and collinearity of DV-Hop localization algorithm. In Section 4, the Voronoi diagram and the proposed algorithm are investigated. Section 5 reports simulation experiments with different sensor networks. Finally, Section 6 concludes the whole paper.

2. Related Works

In the premise of keeping advantages of DV-Hop algorithm, it is important to improve range measurement accuracy and take full use of anchor node resources [3]. At present, the modified methods of DV-Hop algorithm paid more closely attention to some influential factors, including the average of every hop size (AHS) of anchor nodes, sensor node selection, and collinearity [4–8].

In [4], a new method is proposed to calculate the average hop size. Through global and local parts of hop distance, a new AHS suitable to the network is acquired and adopted to improve localization accuracy effectively. But considering the inaccuracy of hop counts, the calculated hop distance of local part will result in errors and increase the calculation complexity. Reference [5] puts forward an improved method based on DV-Hop algorithm. Considering the estimated distance error of AHS for anchor nodes, the positioning accuracy of unknown nodes is enhanced greatly. However, it has limitation in large-scale randomly deployed sensor networks. After that, researchers begin to consider the influence of node deployment and hop counts in order to decrease the positioning errors. With deployment strategy of the anchor nodes, [9] uses the weight factors to improve the DV-Hop algorithm. However, due to high computation complexity, it is not suitable to deploy anchor nodes randomly in actual application. Similarly, [10] uses weight of anchor nodes to improve localization accuracy. Though it effectively improves the positioning accuracy, it also causes large calculation complexity. By analyzing the source of the error of distance estimate between unknown nodes and anchor nodes, [11] enhances the localization accuracy effectively when the nodes transmit signal in every direction. At the same time, by using the experience model and the filter method, it also changes the hop counts and improves the localization accuracy.

Except for the modified algorithm above, researchers also propose some methods such as linear transformation and division of node levels. For instance, [6] proposes a method to solve nonuniform network and describes the positioning problems of anisotropic features which apply linear transformation for localization. With the singular value decomposition pseudo-inverse technique, this method acquires an embedding space built upon adjacent observed values within geographic space. Then, the location can be achieved by transformation of distances between embedding spaces. Some researchers take advantage of Voronoi diagram to improve localization accuracy of DV-Hop algorithm. Reference [12] proposes a kind of DV-Loc algorithm. The author divides anchor nodes into different levels and constrains the flooding region through Voronoi diagram. This method effectively reduces the energy consumption, orientation range, and estimated errors of hop length. Furthermore, the extendibility of DV-Hop algorithm has been significantly improved. However, a number of anchor nodes are necessarily needed and the number grows exponentially, which would inevitably influence the actual performance. Based on the foundation above, Lee and Kim [13] propose an SDV-Hop algorithm which modifies Voronoi diagram and realizes the localization by constraint condition. SDV-Hop uses the broadcast cells of anchor nodes to divide the network and adds it to the constraint condition. It improves localization accuracy drastically. However, due to the complex procedure of classification, it also requires a large calculation duty.

In the last few years, collinearity idea has been widely applied to the localization of wireless sensor network. Owing to the close relationship between the localization errors and the deployment of anchor nodes, the localization accuracy will be seriously influenced when three anchor nodes are in linear relationship (in a straight line). The collinearity idea imposes a large effect on localization of anchor nodes. Reference [7] initially proposes the collinearity method. It determines the groups of anchor nodes by selecting the minimum height of triangle of three anchor nodes. However, the basic parameters are three angles of the interior triangle. Considering the topological structure between nodes, [14] uses cosine law to improve the collinearity and successfully selects the appropriate groups of anchor nodes to localize the unknown nodes. The localization error is obviously decreased. Reference [15] gives deep analysis of the collinearity influence exerted on the localization accuracy of anchor nodes and deduces mathematic theory of collinearity. It adds the detection steps of implicit collinearity to locate the nodes. Thus, the nodes can be located with the help of elimination of ambiguity.

In recent years, localization algorithms for anisotropic networks, with uneven nodal distribution and irregular deployment region, have become a research hotspot. In the anisotropic networks, the shortest path between two nodes may be detoured and its length may be estimated much larger than the corresponding Euclidean distance [16]. Reference [8] proposes a pattern-driven localization scheme which adopts different anchor-sensor distance estimation algorithms for different patterns. The average anchor-sensor distance estimation accuracy of our scheme is improved to be better than $0.4r$ when the average sensor density is above eight. By path rendering and virtual hole construction operations in a distributed manner, [17] proposes a Rendered Path (REP) protocol to accurately estimate the node-to-node distances and calculate node locations with only 3 seeds. In [18], an anchor node selects a “friendly” subset from all other anchor nodes to which its distance estimates are accurate and broadcasts the selection result to neighboring common nodes. The localization error of DV-Hop is reduced by an average factor of 71%. Reference [19] proposes selective multilateration (SM), an RFML protocol in which a node adaptively selects a subset of anchor nodes with accurate distance estimates and good geometric distribution to perform multilateration. Reference [16] proposes a reliable anchor node selection algorithm in which each normal node selects the three anchor nodes with triangular rule to enhance localization accuracy. These methods above improve the localization accuracy in anisotropic networks effectively.

In this paper, a new method is proposed based on DV-Hop algorithm. Voronoi diagram is used to divide the network into several areas. Proper anchor groups are selected to localize the unknown nodes. Experiment results show that the calculation complexity is decreased while the position estimation effectively improved. Compared with existent methods, the strength of our proposed algorithms is that we select proper anchor nodes to participate in the localization procedure according to NC value. Through threshold setting, the anchor node closer to the unknown node is selected. In densely distributed networks, including anisotropic networks with hole, our method can provide an effective way to estimate the unknown nodes' location.

3. Analysis of DV-Hop Algorithm Error and Collinear Effect

According to maximum likelihood estimation, when we use three anchor nodes to calculate unknown node location, we can calculate the distance bias as follows:

$$\begin{array}{cc}& f_i\left(x_{\mathrm{0}},y_{\mathrm{0}}\right)=d{s}_i-\sqrt{{\left(x_i-x_{\mathrm{0}}\right)}^{\mathrm{2}}+{\left(y_i-y_{\mathrm{0}}\right)}^{\mathrm{2}}}\hspace{1em}i=\mathrm{1,2},\mathrm{3}.\end{array}$$

(1)

Here, $(x_{\mathrm{0}},y_{\mathrm{0}})$ and $(x_i,y_i)$ mean the coordinates of the unknown node and those of anchor nodes, respectively. $d{s}_i\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},3)$ means the estimated distance between anchor node and unknown node. When $f_i(x_{\mathrm{0}},y_{\mathrm{0}})=0$ , the localization accuracy is high. Thus, we can get

$$\begin{array}{cc}& d{s}_i=\sqrt{{\left(x_i-x_{\mathrm{0}}\right)}^{\mathrm{2}}+{\left(y_i-y_{\mathrm{0}}\right)}^{\mathrm{2}}}\hspace{1em}i=\mathrm{1,2},\mathrm{3}.\end{array}$$

(2)

Then,

$$\begin{array}{cc}& -x_{\mathrm{1}}^{\mathrm{2}}-y_{\mathrm{1}}^{\mathrm{2}}=\left(x_{\mathrm{0}}^{\mathrm{2}}+y_{\mathrm{0}}^{\mathrm{2}}\right)-\mathrm{2}{x}_{\mathrm{1}}{x}_{\mathrm{0}}-\mathrm{2}{y}_{\mathrm{1}}{y}_{\mathrm{0}}-d{s}_{\mathrm{1}}^{\mathrm{2}},\\ -x_{\mathrm{2}}^{\mathrm{2}}-y_{\mathrm{2}}^{\mathrm{2}}=\left(x_{\mathrm{0}}^{\mathrm{2}}+y_{\mathrm{0}}^{\mathrm{2}}\right)-\mathrm{2}{x}_{\mathrm{2}}{x}_{\mathrm{0}}-\mathrm{2}{y}_{\mathrm{2}}{y}_{\mathrm{0}}-d{s}_{\mathrm{2}}^{\mathrm{2}},\\ -x_{\mathrm{3}}^{\mathrm{2}}-y_{\mathrm{3}}^{\mathrm{2}}=\left(x_{\mathrm{0}}^{\mathrm{2}}+y_{\mathrm{0}}^{\mathrm{2}}\right)-\mathrm{2}{x}_{\mathrm{3}}{x}_{\mathrm{0}}-\mathrm{2}{y}_{\mathrm{3}}{y}_{\mathrm{0}}-d{s}_{\mathrm{3}}^{\mathrm{2}}.\end{array}$$

(3)

Thus, we can acquire the coordinates as follows:

$$\begin{array}{cc}& x_{\mathrm{0}}=\frac{{\gamma }_{\mathrm{1}}-{\beta }_{\mathrm{1}}\left(\left({\gamma }_{\mathrm{2}}-{\gamma }_{\mathrm{1}}\alpha \right)/\left({\beta }_{\mathrm{2}}-{\beta }_{\mathrm{1}}\alpha \right)\right)}{{\alpha }_{\mathrm{1}}},\\ y_{\mathrm{0}}=\frac{{\gamma }_{\mathrm{2}}-{\gamma }_{\mathrm{1}}\alpha }{{\beta }_{\mathrm{2}}-{\beta }_{\mathrm{1}}\alpha }.\end{array}$$

(4)

Here,

$$\begin{array}{cc}& {\alpha }_{\mathrm{1}}=\left(x_{\mathrm{3}}-x_{\mathrm{1}}\right),\hspace{1em}\hspace{1em}{\alpha }_{\mathrm{2}}=\left(x_{\mathrm{3}}-x_{\mathrm{2}}\right),\hspace{1em}\hspace{1em}\alpha =\frac{{\alpha }_{\mathrm{2}}}{{\alpha }_{\mathrm{1}}},\\ {\beta }_{\mathrm{1}}=\left(y_{\mathrm{3}}-y_{\mathrm{1}}\right),\hspace{1em}\hspace{1em}{\beta }_{\mathrm{2}}=\left(y_{\mathrm{3}}-y_{\mathrm{2}}\right),\end{array}$$

(5)

$$\begin{array}{cc}& {\gamma }_{\mathrm{1}}=\frac{\left(x_{\mathrm{3}}^{\mathrm{2}}+y_{\mathrm{3}}^{\mathrm{2}}-x_{\mathrm{1}}^{\mathrm{2}}-y_{\mathrm{1}}^{\mathrm{2}}+d{s}_{\mathrm{1}}^{\mathrm{2}}-d{s}_{\mathrm{3}}^{\mathrm{2}}\right)}{\mathrm{2}},\\ {\gamma }_{\mathrm{2}}=\frac{\left(x_{\mathrm{3}}^{\mathrm{2}}+y_{\mathrm{3}}^{\mathrm{2}}-x_{\mathrm{2}}^{\mathrm{2}}-y_{\mathrm{2}}^{\mathrm{2}}+d{s}_{\mathrm{2}}^{\mathrm{2}}-d{s}_{\mathrm{3}}^{\mathrm{2}}\right)}{\mathrm{2}}.\end{array}$$

(6)

According to formula (5), when equation has no solution, we get ${\alpha }_{\mathrm{1}}=\mathrm{0}$ and ${\beta }_{\mathrm{2}}-{\beta }_{\mathrm{1}}\alpha =\mathrm{0}$ . That is, when $x_{\mathrm{1}}=x_{\mathrm{3}}$ , the equation has no answer. It means that anchor nodes are almost at a straight line.

From this conclusion, the literature [7] puts forward the collinearity thoughts firstly. NC is the normalized collinearity which represents the height of triangle made by three anchor nodes. However, this method is only valid for uniformly dense network. When the network is sparse or unevenly distributed, there might be no solution for NC value. Furthermore, the heights' value may be inaccurate and cause large error for NC value. Therefore, this method has limitations in real application. In fact, DV-Hop localization errors mainly originate from three situations: (1) when anchors are almost in a straight line; (2) when the relative position of any two anchors is too close, while they are also far from the unknown nodes; (3) when three anchors are all nearby, no matter what triangular shape that they compose is, if unknown nodes have a further distance to them, it will lead to a large error. Figures 1(a), 1(b), and 1(c) represent the three situations above, respectively. Here, $a_1$ , $a_2$ , and $a_3$ are anchor nodes. p and $p^{\prime }$ are unknown nodes' estimated location. To solve these problems, [14] proposes a method based on collinearity theory. Since the length related to a cosine value is variable, this method can provide better accuracy for unknown nodes. Here, we also use cosine interior angle to calculate collinearity:

$$\begin{array}{cc}& C_A=\left|\frac{b_{C,A}^{\mathrm{2}}+c_{A,B}^{\mathrm{2}}-c_{B,C}^{\mathrm{2}}}{\mathrm{2}{b}_{C,A}{c}_{A,B}}\right|,\\ C_B=\left|\frac{a_{B,C}^{\mathrm{2}}+c_{A,B}^{\mathrm{2}}-b_{C,A}^{\mathrm{2}}}{\mathrm{2}{a}_{B,C}{c}_{A,B}}\right|,\\ C_C=\left|\frac{a_{B,C}^{\mathrm{2}}+b_{C,A}^{\mathrm{2}}-c_{A,B}^{\mathrm{2}}}{\mathrm{2}{a}_{B,C}{b}_{C,A}}\right|,\end{array}$$

(7)

where $C_A$ , $C_B$ , and $C_C$ represent the cosine of triangle, while $a_{B,C}$ ,   $b_{C,A}$ , and $c_{A,B}$ represent the sides responding to angles A, B, and C, respectively. Then, we can get the normalized collinearity of anchor nodes as follows:

$$\begin{array}{cc}& \text{NC}=\max \left\{C_A,C_B,C_C\right\}.\end{array}$$

(8)

Since NC represents the cosine of minimal angle of the triangle, it ranges from 0.5 to 1.0 (the angle from 0° to 60°). When NC equals 0.5, the triangle is equilateral and the localization accuracy will be the best. When NC equals 1, the anchor nodes are nearly in a straight line and cause bad localization result. Therefore, the suitable threshold value is the key point for nodes localization. According to normalized collinearity, appropriate anchor-node terns can be selected to ensure the unknown nodes' localization.

Figure 1

Three situations of DV-Hop localization error.

In [15], the collinearity theory is analyzed with mathematical methods. The author draws the conclusion that the localization procedure will attain the best performance when the anchor nodes distribution forms an equilateral triangle. In this paper, we adopt the method in [15] to get qualified anchor-node terns for localization. As shown in Figure 2, let $p_{\mathrm{1}}$ and $p_{\mathrm{2}}$ be the two anchor nodes with large distance, and let $p_{\mathrm{3}}$ be another anchor node. The localization procedure can attain the best result when these three anchor nodes make an equilateral triangle. Hence, with $d_{12}$ as the radius and $p_1$ and $p_{\mathrm{2}}$   as the center, respectively, we can get the region shown in Figure 2(a). Let h represent the height of the equilateral triangle, and let A represent the region surrounded by $\overline{p_1{p}_2}$ , $\widehat{p_2{p}_t}$ , and $\widehat{p_t{p}_1}$ ; then, we can get

$$\begin{array}{cc}& h=\frac{\sqrt{\mathrm{3}}{d}_{\mathrm{12}}}{\mathrm{2}},\hspace{1em}\hspace{1em}{S}_A=\left(\frac{\pi }{\mathrm{3}}-\frac{\sqrt{\mathrm{3}}}{\mathrm{4}}\right)d_{\mathrm{12}}^{\mathrm{2}}.\end{array}$$

(9)

Set $e_l$ as the threshold, which is correlated with communication radius. As shown in Figure 2(b), when $h\le 2e_l$ and $d_{12}\le 4e_l/\sqrt{3}$ , the collinearity value is set as 1. This anchor node tern has collinearity and is not suitable for unknown node localization. The collinearity value is

$$\begin{array}{cc}& \text{P}{\text{r}}_c\left(p_{\mathrm{1}},p_{\mathrm{2}},p_{\mathrm{3}}\right)=\mathrm{1},\hspace{1em}\left(\mathrm{0}<d_{\mathrm{12}}\le \frac{\mathrm{4}{e}_l}{\sqrt{\mathrm{3}}}\right).\end{array}$$

(10)

When   $h>{2e}_l$ , the situation is shown in Figure 2(c). l is the line which parallels $p_{\mathrm{1}}{p}_{\mathrm{2}}$ and keeps a distance of ${2e}_l$ . $S_{t1}$ and $S_{t2}$ represent the acreage of $\Delta m_1{m}_2{m}_3$ and $\Delta p_1{p}_2{m}_3$ , respectively. Let $S_B$ represent the acreage of the region surrounded by line l and $p_1{p}_2$ , and let $S_S$ represent the acreage of circular sector $p_1{p}_2{m}_1$ . Then, we can get

$$\begin{array}{l}\text{P}{\text{r}}_c\left(p_{\mathrm{1}},p_{\mathrm{2}},p_{\mathrm{3}}\right)\approx \frac{S_B}{S_A}\\ =\frac{\mathrm{2}{S}_S-S_{t\mathrm{2}}+S_{t\mathrm{1}}}{S_A}\\ =\frac{\arcsin \left(\mathrm{2}{e}_l/d_{\mathrm{12}}\right)+\mathrm{2}{e}_l\sqrt{d_{\mathrm{12}}^{\mathrm{2}}-\mathrm{4}{e}_l^{\mathrm{2}}}/d_{\mathrm{12}}^{\mathrm{2}}-\mathrm{2}{e}_l/d_{\mathrm{12}}}{\pi /\mathrm{3}-\sqrt{\mathrm{3}}/\mathrm{4}},\\ \phantom{hhhhhhhhhhhhhhhhhhhhhhhhhhh}\left(d_{\mathrm{12}}>\frac{{\mathrm{4}e}_l}{\sqrt{\mathrm{3}}}\right).\end{array}$$

(11)

Through this method, we can get the anchor node terns, which can meet the requirement of collinearity, to localize the unknown node.

Figure 2

Analysis of collinearity.

4. Improved Normalized Collinearity DV-Hop Localization Algorithm

Based on collinearity principle, suitable groups of anchor nodes can effectively improve the positioning precision. In view of the three kinds of collinearity situation discussed above, we can use cosine theory to select anchor nodes for localization. However, since current methods cannot distinguish the distance between anchor-node terns and the unknown nodes, the localization error cannot be neglected.

4.1. Formation Principle of Voronoi Diagram

Suppose that $a_1$ and $a_2$ are two spots in a plane. As the perpendicular bisector of $\overline{a_{\mathrm{1}}{a}_{\mathrm{2}}}$ , L divides the plane into two parts including $L_L$ and $L_R$ . The spots $a_L$ within $L_L$ are accordant with the condition $d(a_L,a_1)<d(a_L,a_2)$ . $d(a_L,a_i)$ represents the Euclidean distance between $a_L$ and $a_i$    $(i=\mathrm{1,2})$ . This means that the spots $a_L$ in $L_L$ are close to $a_1$ which is marked as $V(a_1)$ . Similarly, the spots $a_R$ in $L_R$ are closer to $a_2$ than other points in Figure 3.

Figure 3

Formation principle of Voronoi diagram.

4.2. Formation of Voronoi Diagram in Localization Network

We set up n sensor nodes of $p_1,p_2,\dots ,p_n$ in the network. There are m anchor nodes, $a_1,a_2,\dots ,a_m$ . $V(a_i)$ is consisted of the tree with the nodes closer to anchor node $a_i$ than the other anchor node $a_j\hspace{0.17em}\hspace{0.17em}(j=\overline{\mathrm{1},m},j\ne i)$ . Therefore, $V(a_i)$ is a Voronoi polygon related to $a_i$ , while Voronoi diagram is consisted of all $V(a_i)\hspace{0.17em}\hspace{0.17em}(i=\overline{\mathrm{1},m})$ . Before building the Voronoi diagram, spot set must be selected. Here, we take anchor nodes in space as spot set shown in Figure 4. In $100\times 100\hspace{0.17em}{\text{m}}^2$ area, there are several Voronoi polygons.

Figure 4

Voronoi diagram in localization network.

In Figure 4, we give an example for anchor nodes $a_1$ and $a_2$ . The sensor node $p_i$ is in Voronoi polygon $s_1{s}_2{s}_3{s}_4{s}_5{s}_6{s}_{10}$ centered at anchor node $a_1$ . $d(p_i,a_1)$ represents the Euclidean distance from $p_i$ to anchor node $a_1$ . $d(p_i,a_2)$ represents the Euclidean distance from $p_i$ to anchor node $a_2$ , which is different from $a_1$ . The Voronoi polygon is $s_6{s}_7{s}_8{s}_9{s}_{10}$ . From Voronoi diagram, we can find that $d(p_i,a_1)<d(p_i,a_2)$ .

4.3. Improved Normalized Collinearity DV-Hop Localization Algorithm

4.3.1. Threshold Setting of the Hop Count for Anchor Node

In the anisotropic networks, as the S-type network and C-type network shown in Figure 5, DV-Hop always causes large localization error. The reason lies in two factors: (1) there is large difference between the estimated distance and real situation, because there are such phenomena as uneven node distribution, network hole, and path roundabout; (2) the average hop distance is influenced by the uneven distribution. For instance, if there is path roundabout between two anchor nodes, the hop count will be large while the real distance and the average hop size acquired by hop count will decrease. This will cause a smaller estimated distance between the unknown node and the anchor node.

Figure 5

Typical anisotropic network.

Since there are holes and path roundabout, it is difficult to get accurate distance estimation with hop counts. Considering this situation, we propose a threshold of hop counts. In [20], the limitation of hop count is used to improve the localization accuracy and avoid the bad influence caused by path roundabout. According to the experience, the hop count threshold is set as 5 in this paper. If the hop count between an anchor node and the unknown node is not more than the threshold, the anchor node will be chosen to participate in the localization procedure. Otherwise, it will be given up.

4.3.2. Improved Normalized Collinearity DV-Hop Localization Algorithm

All anchor nodes broadcast their information to the whole network based on DV-Hop localization method. After all unknown nodes receive these hop counts and average hop size, a threshold value of NC between 0.5 and 1 is chosen as a standard. According to collinearity theory, these anchor nodes are extracted randomly to form a combination set (take three anchor nodes as a tern $C_m^{\mathrm{3}}$ ). Then, the NC of these terns is calculated and compared with predefined threshold value. If NC is less than or equal to threshold, the tern is chosen as anchor nodes for localization. Totally, there will be t ( $t\le C_m^{\mathrm{3}}$ ) terns which can meet corresponding threshold parameters. According to anchor node location information, Voronoi diagram is used to divide the network into several parts. Using these anchor-node terns consisting of anchor nodes in their own region, which is formed by Voronoi diagram, the unknown nodes' location can be estimated. At last, multiple localization coordinates can be acquired to calculate final estimated location with proper weights.

Appropriate threshold of the collinearity parameters is the key factor in localization. If its value is too large, it will lead to fewer participant anchor-node terns to be selected for localization and cause a waste of sensor node resource. If it is too small, the collinearity theory applies invalidly and may cause the fussy localization process. According to [7, 14, 15] and experimental analysis, we simulate NC threshold value in two kinds of environment and choose 0.9 as appropriate value (Figure 5 shows simulation results). It can make smaller error than other values in both environments. Each anchor node chooses all the sets of the anchor nodes including itself in its region which satisfies the threshold. Then, the sets of anchor nodes are used to localize the unknown nodes. This process implements selection and purification. Using related anchor-node terns in its own region, unknown node can avoid inefficient utilization of anchor nodes and unnecessary calculation.

The overall process is implemented as follows.

• (1)

Anchor nodes traverse the whole network and the unknown nodes receive the information to acquire the accurate hop count to all anchor nodes.

(2)

Through the Voronoi diagram, the whole network is divided into several regions for unknown nodes. The average hop size of anchor nodes is recorded in each region. Then, the value is multiplied with every average hop size of the node. The distance between the anchor node and the unknown node is calculated.

(3)

Three anchor nodes are randomly taken as a group. The law of cosines is used to obtain collinearity value.

(4)

According to collinearity theory, all NCs about anchor-node terns are calculated. Then, the appropriate anchor-node terns are selected as the anchor nodes to estimate the unknown nodes' position.

(5)

Every unknown node uses anchor node in its own region and related terns for localization. From the anchor-node terns satisfying threshold condition, anchor-node terns containing their own region anchor node are selected. So, unknown node can get different coordinates and calculate the weights as follows:

$$\begin{array}{cc}& W_i=\frac{1/\text{N}{\text{C}}_i}{{\sum }_i\left(1/\text{N}{\text{C}}_i\right)}.\end{array}$$

(12)

(6)

At last, final position is estimated by multiplying a set of locations with their corresponding weight:

$$\begin{array}{cc}& \text{Position}={\displaystyle \sum }_i\left[\begin{array}{c}{x}_i\\ y_i\end{array}\right]{W_i}^{\prime }.\end{array}$$

(13)

In Figure 6, there are 24 anchor nodes in randomly deployed network of 100 nodes. Voronoi diagram theory is used to divide the network into 24 regions. Suppose that we need to estimate the position of unknown node p. After dividing network, NCis calculated based on anchor-node terns. We get three anchor-node terns satisfying threshold condition. They are $\Delta a_1{a}_2{a}_5$ , $\Delta a_3{a}_4{a}_5$ , and $\Delta a_6{a}_7{a}_8$ . As the unknown node p has the related sets of $\Delta a_1{a}_2{a}_5$ and $\Delta a_3{a}_4{a}_5$ , these five anchor nodes are used to estimate p's position.

Figure 6

VNC-DV-Hop localization algorithm.

5. Simulation Results and Analysis

To validate the algorithm, a sensor network, with 200 nodes and communication radius as 20 m, is assumed to be randomly distributed in a $\mathrm{100}\times \mathrm{100}{\hspace{0.17em}\text{m}}^{\mathrm{2}}$ region. In each experiment, 1000 tests are implemented to reduce location error. We compare DV-Hop algorithm (DV-Hop) and normalized collinearity DV-Hop algorithm (NC-DV-Hop) with our proposed method (VNC-DV-Hop, Voronoi diagram-based NC-DV-Hop) in homogeneous network and anisotropic network, respectively. Localization error rate (LER) is used as the evaluation criteria for the algorithms:

$$\begin{array}{cc}& \text{ALE}=\frac{\sqrt{{\sum }_{i=\mathrm{1}}^N{\left({\widehat{x}}_i-x_i\right)}^{\mathrm{2}}+{\left({\widehat{y}}_i-y_i\right)}^{\mathrm{2}}}}{N},\\ \text{LER}=\frac{\text{ALE}}{R}\times \mathrm{100}\%.\end{array}$$

(14)

Here, $({\widehat{x}}_i,{\widehat{y}}_i)$ and $(x_i,y_i)$ are the estimated and real coordinates of the ith sensor node, respectively. N is the quantity of unknown nodes; R is the communication radius.

5.1. Simulation Experiment of Homogeneous Sensor Network

The simulation results and related analysis are given as follows.

(1) Influence of TNC on Localization Accuracy. As shown in Figure 7(a), with TNC increasing, VNC-DV-Hop algorithm localization accuracy is higher than the other two algorithms. When TNC is between 0.6 and 0.95, the localization accuracy of VNC-DV-Hop is about 20%, which means that the localization error is about 5 m. VNC-DV-Hop algorithm can attain the best accuracy when TNC equals 0.9. When TNC increases from 0.95 to 1, the localization accuracy of DV-Hop is better than NC-DV-Hop and VNC-DV-Hop. The reason is that anchor nodes are in a straight line, which means collinearity condition; few anchor nodes can be used to estimate unknown node position and lead to low accuracy.

Figure 7

Effect of TNC on localization accuracy.

Figure 7(b) shows the influence of TNC and the quantity of anchor nodes upon localization errors in Environment I. With the quantity of anchor nodes increasing, the influence of TNC on location errors also changes. The deeper color means lower location error. It is easy to find that the location errors related to different TNC value are different. When TNC is about 0.9, the location error is the lowest. For specific TNC, the estimated location will be close to the real location when there are more anchor node terns participant in the localization procedure. Therefore, the influence of TNC upon location error cannot be ignored. For posterior analysis, we choose the value of TNC as 0.9.

(2) Influence of the Quantity of Anchor Nodes on Localization Accuracy. By changing the ratio of anchor nodes, it is convenient to analyze the localization accuracy. In Figure 8, as the ratio of anchor node increases, the localization accuracy declines gradually. The performance of VNC-DV-Hop algorithm is the best. Compared with DV-Hop and NC-DV-Hop algorithms, VNC-DV-Hop's accuracy is improved by 13% and 8%, respectively.

Figure 8

Effect of the number of anchor nodes on localization accuracy.

(3) Influence of Average Hop Size (AHS) on Localization Accuracy. In DV-Hop localization algorithm, AHS influences the localization accuracy seriously. To depress the localization errors, the modified AHS [14] is used to conduct the simulation experiment. The modified AHS is defined as follows:

$$\begin{array}{cc}& \text{HopSize}=\frac{{\sum }_{i=n}\text{HopSiz}{\text{e}}_i}{n},\end{array}$$

(15)

where n is the number of anchor nodes. $\text{HopSiz}{\text{e}}_i$ is the traditional AHS which can be calculated as follows:

$$\begin{array}{cc}& \text{HopSiz}{\text{e}}_i=\frac{{\sum }_{j\ne i}\sqrt{{\left(x_i-x_j\right)}^{\mathrm{2}}+{\left(y_i-y_j\right)}^{\mathrm{2}}}}{{\sum }_{j\ne i}{h}_j}.\end{array}$$

(16)

Here, $(x_i,y_i)$ and $(x_j,y_j)$ are coordinates of anchor nodes i and j. $h_j$ is the hops between anchor node j and all other anchor nodes.

To analyze the influence of AHS, NC-DV-Hop is compared with the VNC-DV-Hop algorithm. In Figure 9, the dotted line represents the localization results with average hop size in formula (16) while the solid line represents localization results in formula (15). The number of anchor nodes in the network changes from 100 to 200, in which the anchor nodes are 20%. From Figure 9, the location error of VNC-DV-Hop algorithm becomes low. Comparing with traditional AHS method, the modified algorithm has lower localization error. VNC-DV-Hop algorithm owns good accuracy and is suitable for multinode network.

Figure 9

Influence of the number of nodes on localization accuracy.

(4) Influence of the Communication Radius upon Localization Accuracy. In Figure 10, location errors change with the communication radius of anchor nodes. When the communication radius of anchor nodes becomes larger, location errors decrease gradually. Localization accuracy of our VNC-DV-Hop algorithm is the best. When the communication radius is above 25 m, all the three algorithms can attain steady localization accuracy.

Figure 10

Influence of radio range of anchor node on localization accuracy.

(5) Estimated Coordinates of Unknown Node and Localization Error. Figure 11 shows the comparison of location errors among the three algorithms in homogeneous sensor network.

Figure 11

Localization error of DV-Hop, NC-DV-Hop, and VNC-DV-Hop in homogeneous sensor network.

The directions of the arrows are pointed to the actual coordinates of unknown nodes. The lengths of the arrows represent the difference between estimated and actual coordinates of the unknown nodes. According to Figure 11(a), the unknown nodes which locate in the ellipsoid region own higher error because the arrows are large and messy. Compared with Figure 11(c), Figure 11(b) shows lower localization error. In Figure 11(c), our VNC-DV-Hop algorithm shows the best performance, with almost all the estimated coordinates of unknown nodes located in their own Voronoi polygons. Figure 11(d) shows that localization errors of DV-Hop algorithm are relatively large with an average value of 10 m and a fluctuation range as much as 27 m. Comparatively, NC-DV-Hop shows the error of 8 m and fluctuation range as 15 m. Our VNC-DV-Hop algorithm owns the smallest localization error of 5 m and very small fluctuation.

5.2. Simulation Experiment of Anisotropic Network

In this paper, we mainly consider S-type network. Through simulation experiments, the influences of path roundabout and uneven distribution are discussed.

(1) Influence of TNC upon the Localization Accuracy. As shown in Figure 12, when 0.65 < TNC < 0.95, the localization error decreases with TNC growing. VNC-DV-Hop algorithm and NC-DV-Hop algorithm can acquire better performance than DV-Hop algorithm. When 0.65 < TNC < 0.95, the LER of VNC-DV-Hop is about 30%, which means that the localization error is about 7 m. When TNC equals 0.9, the LER is the smallest. However, when 0.95 < TNC < 1, DV-Hop algorithm can get the best performance. The reason lies in that the anchor nodes are almost at a line when cosine value is at 0.95–1. At this range, NC-DV-Hop and VNC-DV-Hop are not as good as DV-Hop, because they use less anchor nodes to participate in the localization procedure.

Figure 12

Influence of TNC value on positioning accuracy in anisotropic network.

(2) Influence of the Ratio of Anchor Node upon Localization Accuracy. By changing the ratio of anchor nodes in the network, we can analyze its influence upon the localization accuracy. As shown in Figure 13, the localization error decreases gradually with the ratio of anchor nodes growing from 10% to 30%. When the ratio of anchor node is about 16%, the localization error encounters an abrupt rise. However, our VNC-DV-Hop algorithm can get more stable localization accuracy.

Figure 13

Influence of anchor node percentage upon positioning accuracy in anisotropic network.

(3) Influence of Communication Radius upon Localization Accuracy. When the communication radii increase from 15 m to 35 m, the localization errors of the three algorithms decrease significantly. As shown in Figure 14, VNC-DV-Hop algorithm can acquire the best performance when the communication radius is below 25 m. Therefore, it can work well in densely deployed sensor network. When the communication radius is above 25 m, the three algorithms can get almost the same accuracy.

Figure 14

Influence of communication radius on positioning accuracy in anisotropic network.

(4) Influence of the Node Quantity upon Localization Accuracy. In Figure 15, the localization error decreases with the quantity of sensor nodes increase. VNC-DV-Hop can get the smallest error. Furthermore, its trend is much steadier than NC-DV-Hop and DV-Hop.

Figure 15

Influence of the number of nodes on positioning accuracy in anisotropic network.

(5) Estimated Coordinates of Unknown Node and Localization Error. Figure 16 shows the localization error of DV-Hop, NC-DV-Hop, and VNC-DV-Hop in anisotropic sensor network. The directions of the arrows are pointed to the actual coordinates of unknown nodes. The lengths of the arrows represent the difference between estimated and actual coordinates of the unknown nodes.

Figure 16

Unknown nodes' estimated coordinates and localization error in S-type anisotropic network.

According to Figures 16(a), 16(b), and 16(c), the unknown nodes which locate in the ellipsoid region own higher error because the arrows are large and messy. DV-Hop in Figure 16(a) shows large localization error, while NC-DV-Hop in Figure 16(b) can get better accuracy. In Figure 16(c), our VNC-DV-Hop algorithm shows the best performance. According to Figure 16(d), VNC-DV-Hop has a localization error of about 7 m and very small fluctuation. DV-Hop algorithm shows relatively large error with an average value of 15 m and a fluctuation range as much as 30 m. NC-DV-Hop shows the error of 11 m and fluctuation range as 20 m.

For C-type sensor network, the proposed algorithm is also effective. Figure 17 shows the localization performance of DV-Hop, NC-DV-Hop, and VNC-DV-Hop.

Figure 17

Unknown nodes' estimated coordinates and localization error in C-type anisotropic network.

Similar to Figure 16, the directions of the arrows are pointed to the actual coordinates of unknown nodes. The lengths of the arrows represent the difference between estimated and actual coordinates of the unknown nodes. It can be seen that traditional DV-Hop has large error because the estimated position is far from the real location. According to Figure 17(d), the localization errors of DV-Hop, NC-DV-Hop, and VNC-DV-Hop algorithms are about 40 m, 30 m, and 12 m, while their fluctuation ranges are 1 m~35 m, 1 m~75 m, and 1 m~80 m, respectively. Therefore, our proposed algorithm is more accurate and steadier.

5.3. Performance Discussion

For NC-based DV-Hop algorithms, different situations of anchor node triangle will cause some special situations which may cause the algorithm to be invalid. Reference [15] gives a typical algorithm which considers the influence of collinearity upon the localization accuracy of anchor nodes. However, there are some situations which are difficult to be solved.

As shown in Figure 18(a), anchor nodes A, B, C form a triangle. Both the distance between A and B and the distance between B and C are ${2e}_l$ ; the corresponding NC is 0.7. According to the simulation in this paper, the localization accuracy in this situation is not satisfactory. In Figure 18(b), the distance between A and B is $e_l$ ; h is far larger than ${2e}_l$ ; therefore, anchor node C is far from $AB$ ; NC value is about 1. For this situation, it cannot be adopted to anisotropic networks. Therefore, the algorithm in [15] is more suitable for homogeneous networks. According to Figure 18(c), when anchor nodes A and B are used for the localization of unknown node P, there will be two possible positions $P_1$ and $P_2$ . Anchor node C is related with $P_1$ and $P_2$ ; it is difficult to judge which side should be chosen for node P. Therefore, the algorithm in [15] cannot deal with these situations in Figure 18 effectively. Comparatively, on basis of the cosine value of anchor node tern, the proposed VNC-DV-Hop algorithm can deal with these different situations effectively.

Figure 18

Special situations for NC-based DV-Hop algorithm.

As a range-free localization technique, DV-Hop algorithm has a large communication cost of $O(n·m)$ , whereas the complexity of message exchange of traditional DV-Hop algorithm is $O(n·(m+1))$ . Here, n and m are the numbers of sensor nodes and anchor nodes, respectively.

For the proposed VNC-DV-Hop algorithm, the communication cost is the same as $O(n·m)$ , because it starts by flooding the position information in the sensor network. However, the message exchange is limited to the Voronoi polygon of the unknown node. In other words, the position information of anchor nodes will only propagate inside the specific region. Each node only computes the Voronoi diagram inside its Voronoi polygon. To compute its Voronoi polygon, a node needs only $m-1$ float operations, where m is the number of anchor nodes information at each node, which is about $3+\log (n-3)$ . Furthermore, it is unnecessary to compute the Voronoi polygon of the nodes at each step, because only the nearest anchor nodes will be used. Thus, the computational cost of our proposed VNC-DV-Hop is lower than traditional DV-Hop. Since the energy dissipation has close relation with the computation cost, our algorithm also has lower energy cost than traditional DV-Hop algorithm.

6. Conclusion

DV-Hop localization algorithm is one of the most efficient methods suitable for range-free localization in large sensor network. In order to overcome the deficient characteristics of DV-Hop algorithm, this paper proposes a modified algorithm which takes full advantage of Voronoi diagram and combines improved collinearity theory to determine the location of unknown nodes. By selecting the appropriate groups of anchor nodes, our method improves the localization accuracy of unknown nodes and reduces the redundant computational process. Meanwhile, the utilization rate of anchor nodes has been significantly improved. From the results of simulation tests, we can draw the conclusion that our modified algorithm has higher localization accuracy than traditional DV-Hop algorithm and is appropriate for the large sensor network localization. For both homogeneous network and anisotropic network, our algorithm can acquire excellent performance.