A Voronoi Diagram-Based Grouping Test Localization Scheme in Wireless Sensor Networks

Abstract

The wireless sensor network (WSN) provides us with a cost-effective way to remotely monitor a large number of objects, locations, and environmental parameters. Taking advantage of WSNs to applications can add new capabilities to existing products and bring out new services. We propose a novel range-free localization scheme, the Voronoi diagram-based grouping test localization (VTL) scheme, to estimate the location efficiently for WSNs. VTL divides the anchor nodes into multiple groups and uses the corresponding closest Voronoi cells to compute the estimated location. Apart from improving the accuracy of location estimation, it also largely simplifies the implementation. Simulation results show that the VTL scheme has better performance compared with other range-free localization schemes. When reaching a certain anchor node density, the VTL scheme will have higher localization accuracy and a larger percentage of localizable nodes. Hence, VTL is likely more appropriate for upcoming WSN scenarios with large ratios of anchor nodes being available.

1. Introduction

Wireless sensor networks (WSNs) provide us with a cost-effective way to remotely monitor a large number of objects, locations, and environmental parameters [1,2,3,4,5]. New technologies and applications for WSNs have been continually proposed, since monitoring capability is becoming more important than ever. For example, pervasive games [6] and sport training [7] are recent examples of applying WSN technologies to provide new services in our daily life. Surely, further taking advantage of WSNs for applications can add new capabilities to existing products and bring out new services. The challenge is to have sufficiently low setup, operation, and maintenance costs.

In WSN applications, especially in outdoor environments, how the wireless sensor node determines its location is an important issue. It will be meaningless if the measurement data do not include the node’s location information. For cost-effective consideration, it is likely that not all wireless sensor nodes have the capability to determine their locations only by themselves. In the early days, only a small number of wireless sensor nodes could specifically have the complete capability to determine their locations, i.e., they were anchor nodes with GPS receivers. Other wireless sensor nodes then computed their estimated locations with the assistance of signals/beacon messages broadcasted from anchor nodes. Depending on the balance among cost, precision, and complexity, different kinds of localization schemes have been proposed [8,9,10,11,12,13,14,15,16,17,18,19,20]. As hardware cost is rapidly falling, it is expected that a larger ratio of wireless sensor nodes can have complete localization capacity. Nevertheless, the localization problem for common wireless sensor nodes is still important. However, the approaches to solving this problem may be more direct and simpler.

Localization schemes can be categorized as range-based and range-free schemes. In range-based schemes, the computation of a node’s location largely relies on the measured distances to anchor nodes. Common distance measurement methods include time of arrival (TOA), time difference of arrival (TDOA), angle of arrival (AOA), and receiver signal strength index (RSSI) [8]. Range-based schemes are not frequently employed due to the equipment cost and sensitivity to environmental factors. In range-free schemes, a wireless sensor node is not required to measure the distances between it and anchor nodes. Instead, indirect methods are used for estimating the node’s location. Intuitive methods include using the centroid of all locations of direct detected anchor nodes as the estimated location [9]. As performance fluctuates easily with many factors such as anchor node distribution, different kinds of approaches are proposed. For example, one may have the estimated distances to anchor nodes if the information of average hop number to anchor nodes is available [10,11]. This increases the communication overhead and narrows the choice of routing schemes for WSNs, but a smaller number of anchor nodes is generally required. Another shortcoming of such approaches is that the distribution of all wireless sensor nodes, not only anchor nodes, will interfere with the accuracy of location estimation. Surely if extra communications between common wireless sensor nodes and anchor nodes are feasible, the performance of location estimation can be largely improved [12]. Without the assumption of extra communications, there are approaches that use areas of shapes computed from locations of anchor nodes and strengths of received signals to estimate locations [13,14,15]. Such approaches require rather primitive information from anchor nodes, but a large number of anchor nodes is commonly assumed. From this aspect, they are likely more appropriate for coming WSN scenarios, with large ratios of anchor nodes being available. To have better localization accuracy, however, some of them often need to generate large numbers of areas and others assume good capability of signal receiving. This may limit the practical applications of such approaches in another aspect. In this paper, we therefore propose a Voronoi diagram-based grouping test location (VTL) scheme to simplify the implementation and also improve the performance of location estimation.

A Voronoi diagram provides us with a handy way to partition a plane. It has been widely applied in site selection, formation control, planning, face recognition, and network optimization [21,22]. Efficient algorithms are freely available for generating Voronoi diagrams. This largely simplifies the use of Voronoi diagrams in different algorithms. Furthermore, Voronoi diagrams have also been used in other localization schemes to improve the schemes’ performances [16,17,18,19,20]. In [16], Voronoi diagrams were used to limit the flooding messages required for the DV localization schemes. In [17], a half symmetric lens-based localization algorithm (HSL) was proposed using a Voronoi diagram to further refine the results. In [18], the indoor localization problem was solved with the radio map (fingerprinting) approach, and Voronoi-based interpolation improved the localization performance. In [19], the indoor locations of robots were estimated by matching the local laser scan-generated Voronoi diagram (LVD) with the global Voronoi diagram. In [20], the authors proposed a fingerprinting-based localization approach in conjunction with a Voronoi diagram to estimate the location in indoor parking lots. From the above review, one can observe that the Voronoi diagram is not the core technique for location estimation. In this paper, however, we only use the basic Voronoi cell feature and minimal radio signal detection for a VTL localization scheme. In Section 2, some foundations of VTL are briefly discussed, including the Voronoi diagram, the logarithmic attenuation model for radio signals, and the basic idea of VTL. Section 3 then goes through the VTL scheme in detail. The novelty of VTL is the proposed approach of generating multiple Voronoi diagrams with the same set of anchor nodes. Overlapping the closest Voronoi cells from the multiple Voronoi diagram provides us with more accurate location estimation. Section 4 presents simulation experiments and analysis. In Section 5, the possible application scenarios for VTL and implementation issues are discussed.

2. The Foundations of the VTL Scheme

2.1. Voronoi Diagram

In mathematics, a Voronoi diagram is a distance-based strategy for partitioning a plane. Set $\mathit{P}$ is assumed to be a set of $n$ discrete points $p_i$ in the plane domain, and the plane domain $\mathit{V}$ is partitioned into $n$ sub-regions (called Voronoi cells), given as (1).

$$\mathit{V}\left(\mathit{P}\right)=\left\{V\left(p_1\right),V\left(p_2\right),\cdots ,V\left(p_n\right)\right\}$$

(1)

$V\left(p_i\right)$ denotes the Voronoi cell of $p_i$, which is a set of the closest points to $p_i$ in the plane. We then have $V\left(p_i\right)$ as (2).

$$V\left(p_i\right)=\left\{d\left(g,p_i\right)\le d\left(g,p_j\right),\forall j\ne i,i=1,2,\cdots ,n\right\},$$

(2)

where $d\left(g,p_i\right)$ is the distance between nodes g and p_i. In this section, we use the dual relationship between Voronoi and Delaunay triangulation to illustrate the generation of the Voronoi diagram. By drawing circumcircles on the triangles using nodes as vertexes, one can have Delaunay triangulation of the n nodes if all circumcircles have no other node inside, apart from their triangle vertexes. The Voronoi diagram of the n nodes is then obtained by connecting all centers of the circumcircles. Figure 1a shows the example of having Delaunay triangulation of six nodes from p₁ to p₆. There are five circumcircles, each having only three of the nodes as vertexes of a triangle. Connecting the five centers and the extension lines to the edges of the square plane, we obtain the corresponding Voronoi diagram, as shown in Figure 1b, i.e., a node g in the Voronoi cell of p₁ will have the shortest distance to p₁ than to any other p_i, i ≠ 1. Note that currently available algorithms only require the time complexity of O(nlogn) to generate a Voronoi diagram. Using the Delaunay triangulation approach, however, we may need the time complexity of O(n²) in some exceptional cases.

As we discussed in the Introduction, an unknown node (i.e., a wireless sensor node with unknown location) such as g in Figure 1b is not able to determine its location by itself only, but its localization is possible with the help from anchor nodes (such as p₁ to p₆) the locations of which are known. In general, g can realize the location distribution of p₁ to p₆ by detecting the beacon messages broadcasted from them. Nevertheless, having the map of all anchor nodes does not imply that g can easily determine its location. Note that g does not know the exact distance to any anchor node. As shown in the next section, although g may know the strengths of radio signals received from p₁ to p₆, g is unable to absolutely determine which one in any pair of anchor nodes is closer to it. Using the centroid of the locations of p₁ to p₆ as the estimated location of g is a simple solution, but its accuracy will vary largely with the distribution of p₁ to p₆. Figure 1b shows us another simple solution using the Voronoi diagram. Note that we can have the Voronoi cells of p₁ to p₆ using their location information only. As shown in the next section, the received signal will have less variance if the anchor node is closer to the unknown node. Such a property implies that g in Figure 1b can correctly select p₃ with a large probability as its closest anchor node by checking the received radio signal strength. Hence, g can also easily determine the closest Voronoi cell, i.e., the Voronoi cell corresponding to the closest anchor node. As shown in Figure 1b, g must be inside the closest Voronoi cell. We can therefore estimate the location of g from the location and shape of the closest Voronoi cell. Unless the measurement error of distance between nodes is sufficiently large to cause g to choose the wrong closest anchor node, it will have no impact on the location estimation. Based on such an observation, a more accurate result can be obtained if the proper scheme has been designed for the location estimation. A more detailed discussion will be given in Section 2.3.

2.2. Logarithmic Attenuation Model

Some localization algorithms may not be workable in environments with irregular topologies and barriers. This is because they assume a perfect circular radio model (i.e., regular radio signal propagation model) and do not take into account propagation loss in complicated environments. Hence, VTL assumes signal propagation using the logarithmic attenuation model as shown in (3).

$$P_r\left(d\right)=P_t-P_L(d_0)-10\eta \lg (\frac{d}{d_0})+X_{\sigma },$$

(3)

where $P_t$ is the radio signal strength at the transmitting anchor node [17]. The unit of $P_t$, $P_r\left(d\right)$, and $P_L\left(d_0\right)$ is in dBm. $P_r\left(d\right)$ is the radio signal strength at the receiving nodes, where $d$ is the distance between receiving nodes and the transmitting anchor node. The reference distance (typically 1 m) is $d_0$, and the radio signal strength of $d_0$ is denoted as $P_L\left(d_0\right)$. $\eta$ is the coefficient of path loss in relation to the surroundings and structures. $X_{\sigma }$ is a normal distribution random noise, which has an expected mean value of 0 and a standard deviation of σ determined by the environment. Specific parameter values used in this paper are given in caption of Figure 2 and also

Table 1. Simulation parameters and values.

Parameters	Values
$\eta$	4
$P_t$	0 dBm
$P_L\left(d_0\right)$	−55 dBm
$d_0$	1 m
σ	4

.

As shown in Figure 2a, we illustrate the change in radio signal intensity with distance for the regular and logarithmic attenuation models. By comparing the strength curves of the two models, we observe that the closer the point is to the transmitting node, the smaller the impact of the attenuation component and noise will be. This is because the same value has less influence on the higher received radio signal strength (Rss).

As seen in Figure 2b, we further used the logarithmic attenuation model to calculate the mean and standard deviation of the distances between nodes with the same radio signal strength at the receiving nodes. Consequently, Figure 2b confirms the conclusion that the distribution of nodes with weak signal strength will have a larger fluctuation. This also implies that an unknown node can have a larger probability to select its closest anchor node by checking the received radio signal strength. Using the associated Voronoi cell of the closest anchor node will have advantages in improving the accuracy of location estimation. This observation provides us with a hint to design a VTL scheme.

2.3. The Main Ideas of VTL

From Section 2.1, we realize that it is possible to find the closest Voronoi cell from a set of anchor nodes to allocate the unknown node. However, the estimated location from the area of only a single Voronoi cell may not be sufficiently close to the real location. To improve the accuracy, VTL computes the estimated location using the area from the overlapping of multiple Voronoi cells, each being generated from a subset of anchor nodes. We use Figure 3 as an example. Instead of using all 12 anchor nodes to find a single Voronoi cell to compute the estimated location, we divide the anchor nodes into two groups (triangles and dots) and solve the two corresponding closest Voronoi cells. The overlapping area of the two Voronoi cells is marked as the “estimated region” in Figure 3. Clearly, using the “estimated region” to compute the estimated location is more accurate than using any single Voronoi cell from the two groups of anchor nodes. Simulation verification (please refer to Section 4) shows that dividing anchor nodes into multiple groups to compute the estimated location can have a more accurate result than that based on the whole set of anchor nodes.

3. The VTL Localization Scheme

In this section, we further explain the VTL scheme in detail. Figure 4 shows the detailed flow diagram of the VTL scheme.

3.1. Beacon Messages Exchange

We first assume that each anchor node has the location information of all other anchor nodes. If an unknown node receives a beacon message from any anchor node, it will have a map of all anchor nodes. We further assume that anchor nodes broadcast the beacon messages periodically. Moreover, an unknown node maintains a table including its own index (id), location flag $\epsilon$, index of anchor node (id), and $Rss$. Equation (4) gives the specific assignment of location flag $\epsilon$:

$$\epsilon =\left\{\begin{array}{c}1, m=0\\ 2, m\ge 1\end{array}\right.$$

(4)

where m is the number of received beacon messages from different anchor nodes, i.e., m is the number of detectable anchor nodes. Note that $\epsilon$ = 1 means no meaningful message having been received. When an unknown node would like to determine its location, it will set its location flag $\epsilon$ to 1. After $\epsilon$ changing to 2, it obtains the map of anchor nodes and starts the step of anchor grouping.

3.2. Grouping of Anchor Nodes

Assuming there are N_a anchor nodes on the plane. Figure 3 shows us the approach of directly dividing the anchor nodes into two groups, each having N_a/2 members and generating the two corresponding Voronoi diagrams to estimate the unknown node location. To have K ≥ 2 Voronoi diagrams with the same approach, an unknown node is required to divide the N_a anchor nodes into K groups, where group j has H_j members, j = 1, … K, and $N_a={{\displaystyle \sum }}_{j=1}^K{H}_j$. Note that K must be smaller than N_a and not larger than the number of detectable anchor nodes m in (4). From each group of anchor nodes, the unknown node generates the corresponding Voronoi diagram and determines the Voronoi cell closest to it. After having the K closest Voronoi cells, the overlapping area of these Voronoi cells is used as the estimated region for computing the estimated location of the unknown node. By following such an approach, however, the number of members in each group, H_j, will decrease with the increase of K. As a result, we will have smaller numbers of cells in each Voronoi diagram and K closest Voronoi cells with larger sizes. Clearly, this will degrade the accuracy of location estimation and limit our flexibility of using a large K, though we can in principle increase the number of group K up to the number of detectable anchor nodes m.

To eliminate the inflexibility of using large K, a flexible grouping approach is proposed for the anchor nodes. In short, we randomly select two anchor nodes among the m detectable anchor nodes and further randomly divide the remaining anchor nodes (i.e., the m–2 detectable anchor nodes and N_a–m other anchor nodes) into two equal groups. After adding the two selected anchor nodes to the two groups, we then have two groups of anchor nodes, each with at least one detectable anchor node. By repeating the procedure T times, we then have K = 2T proper anchor node groups, each with N_a/2 randomly selected members. As the group size H_j does not decrease with the increase of K, we get back the flexibility of using large K.

To demonstrate the proposed method, we use the same set of anchor nodes as that in Figure 3 to generate four more groups of anchor nodes, i.e., K = 6. For simplicity, all anchor nodes are assumed to be detectable by the unknown node. Without the need to first select two detectable anchor nodes, we can simply divide all anchor nodes at random into two new anchor node groups, as shown in Figure 5a, i.e., the group of squares and the group of diamonds. Using the same approach, we have another two anchor node groups, as shown in Figure 5b, i.e., the group of pluses and the group of x-marks. Similar to that of Figure 3, the Voronoi diagrams corresponding to the anchor nodes of the groups are also plotted in Figure 5a,b. As seen in Figure 3 and Figure 5, we have a total of six Voronoi diagrams, each having six Voronoi cells for the location estimation.

3.3. Voronoi Cell Testing

After grouping, the Voronoi diagram is drawn for each group of anchor nodes. We classify Voronoi cells into two types: the closest cell having the unknown node inside (called the positive region), and other cells without the unknown node (called the negative region) according to Rss. For example, we assume that Rss₁, Rss₂, and Rss₃ are the radio signal strengths received by the unknown node from anchor nodes $P_1$, $P_2$, and $P_3$. When the radio signal strengths are in the order of Rss₃ > Rss₁ > Rss₂, the Voronoi cell of $P_3$ is reasonably considered as the most likely to include the unknown node in it, as shown in Figure 6. After testing the $K$ groups of anchor nodes, $K$ “positive regions” can be obtained. Then superimposing the positive regions, the overlapping region, which is called the estimated region, is obtained by using the grid scanning method proposed in Section 3.4.

3.4. Grid Scanning

The $K$ “positive regions” obtained by the method introduced in Voronoi Cells Testing of Section 3.3 will not have an overlapping area every time. Owing to environmental and other factors, certain errors in $Rss$ may affect the judgment of the estimated region where the unknown node is located. Note that the unknown node may choose the wrong closest anchor nodes. Additionally, inaccuracy may occur in the location information of anchor nodes, e.g., GPS location errors. Considering such uncertainties with overlapping of the K closest Voronoi cells, a grid scan method similar to that in [12] is used to obtain the estimated region.

The proposed grid scan method assumes that the area around the unknown node consists of $W$ grids, each with square area $l^2$. For an area with the size of $L\times M$, we have $W=L\times M/l^2$. The initial weights of all grids are set to 0. Note that a point inside a Voronoi cell will have the shortest distance to the corresponding anchor node compared to other anchor nodes (see the Voronoi diagram property in Section 2.1). The weight of the $j$-th grid will be increased by one if its center is deemed to be inside the positive region after a test of one group. If not, the weight is decreased by one, as shown in (5). Equation (6) shows the formulas for calculating weights when all tests of $K$ groups are finished.

$${\omega }_{j-k}=\left\{\begin{array}{c}1, inside\\ -1, outside\end{array}, 1\le j\le W, 1\le k\le K\right.,$$

(5)

$$C_j={\sum }_{k=1}^K{\omega }_{j-k},1\le j\le W.$$

(6)

In principle, the estimated region is the area with grids of largest weights. Figure 7 shows us the estimated region (with grids of weight = 3) by overlapping three positive regions. To compute the estimated location of an unknown node, (7) is used to approximate the unknown node’s coordinates $\left(X_{\mathrm{est}},Y_{\mathrm{est}}\right)$.

$$\left(X_{\mathrm{est}},Y_{\mathrm{est}}\right)=(\frac{1}{m}{\sum }_{i=1}^m x_i,\frac{1}{N}{\sum }_{i=1}^m y_i)$$

(7)

where m is the number of grids with the maximum weights; $\left(x_i,y_i\right)$ denotes the coordinates of centers of the grids; and i = 1, … m. In the example of Figure 7, we assume that the coordinate of the grid at the bottom left corner is (1, 1) and that of the grid at the top right corner is (10, 10). Four grids have a maximum weight of 3. They have coordinates (x, y) of {(3, 5), (3, 6), (4, 5), (4, 6)}. Hence the estimated location of the unknown node (the dot in Figure 7) is (3.5, 5.5).

4. Simulations and Analysis

We conducted extensive virtual experiments using MATLAB as the simulation platform to test the performance of the VTL scheme. Performance evaluations at different sensor deployments were discussed. Two localization schemes, Centroid localization [8] and APIT [12], were used for comparison. The APIT scheme uses a randomly composed triangle of anchor nodes communicating with unknown nodes, and Centroid localization is a typical indirect estimation (range-free) localization scheme. The performance of the three localization schemes was visualized through average estimation error (E_a) and estimation percentage (P_e), given in (8) and (9).

$$E_{\mathrm{a}}=\frac{{\sum }_{i=1}^{{N^{\prime }}_{\mathrm{u}}}\sqrt{(X_{\mathrm{est}}-X_i{)}^2+(Y_{\mathrm{est}}-Y_i{)}^2}}{{N^{\prime }}_{\mathrm{u}}·R},0<{N^{\prime }}_{\mathrm{u}}\le N_{\mathrm{u}}$$

(8)

$$P_{\mathrm{e}}=\left({N^{\prime }}_{\mathrm{u}}/N_{\mathrm{u}}\right)\times 100\%,$$

(9)

where $N_{\mathrm{u}}$ and ${N^{\prime }}_{\mathrm{u}}$ represent the number of total unknown nodes and localizable unknown nodes, respectively. $\left(X_i,Y_i\right)$ denotes the actual coordinates of node $i$. $E_{\mathrm{a}}$ denotes the ratio of the average positioning error of nodes to the communication radius R, which indicates the positioning accuracy of the algorithm. $P_{\mathrm{e}}$ demonstrates the percentage of localizable nodes.

4.1. Settings of Simulation Parameters

Assuming that the virtual experimental environment is in an open outdoor area, the performance of the VTL scheme was evaluated with a square topology in which wireless sensor nodes were randomly distributed with uniform probability distribution. We used the radio signal model (i.e., (3)), as discussed in Section 2.2, and Table 1 lists the parameters that are commonly used for WSN simulations. We studied several parameters that may directly affect the performance of range-free schemes, as shown in

Table 2. Simulation parameters and values.

Parameters	Values
Network size (S)	100 × 100, 200 × 200
Number of total nodes ( $N_{\mathrm{t}}$)	60–200
Anchors ration ($r_a$)	10–70%
Radius of unknown nodes (R)	20 m, 40 m
Radius of anchor nodes (Ra)	20–80 m
GPS error ($E_{GPS}$)	0, 5–10 m
Number of groups (K)	2–10
Grid size (l)	2 m

.

Let N_t = N_a + N_u be the number of total nodes. The ratio of anchor nodes $r_a$ is the proportion of anchor nodes to the total number of nodes, as written in (10).

$$r_{\mathrm{a}}=\left(N_{\mathrm{a}}/N_{\mathrm{t}}\right)\times 100\%$$

(10)

The GPS error ($E_{GPS}$) refers to the maximum error introduced by GPS equipment when acquiring positions of anchor nodes. In this paper, we assumed that GPS errors are isotropic.

4.2. Number of Groups

In Figure 8, the effect of the number of groups ($K$) changing from 2 to 10 on $E_{\mathrm{a}}$ and $P_{\mathrm{e}}$ is illustrated. Though we did not plot the case of K = 1 in the figure, we observed that dividing the anchor nodes into multiple groups can improve the accuracy of location estimation. It can be seen that the change in $P_{\mathrm{e}}$ was rather minor when $K$ was varied. However, the value of $E_{\mathrm{a}}$ kept decreasing as $K$ was increased. When $K$ = 6, the decreases in $E_{\mathrm{a}}$ became negligible. Therefore, in the following experiments, we chose $K=6$.

4.3. Density of Nodes

In this section, we explored the effect of density of nodes on the VTL scheme at four different setups, as shown in

Table 3. Four setups.

Name	ra (%)	${\mathit{R}}_{\mathit{a}}\left(\mathbf{m}\right)$	$\mathbf{Size} \mathbf{of} \mathbf{Area} ({\mathit{m}}^2)$
Setup 1	40	40	200 × 200
Setup 2	40	20	200 × 200
Setup 3	40	40	100 × 100
Setup 4	40	20	100 × 100

.

As shown in Figure 9a,b, E_a decreased but $P_{\mathrm{e}}$ increased when $N_{\mathrm{t}}$ varied from 60 to 200 in all four situations. We had the worst E_a and P_e with setup 2. With the increases of density of nodes, unknown nodes could receive more beacon messages from anchor nodes, which therefore improved the location accuracy effectively. Note that the effect of node density on the VTL scheme was mainly due to the increase of anchor node density. VTL does not rely on the communications between unknown nodes, i.e., it is insensitive to unknown node density.

4.4. Performance Comparisons with Square Topology

A comparison of simulation outcomes of three range-free schemes (VTL, APIT, and Centroid) is shown in Figure 10. As it may not be easy to compare the performance of different schemes from Figure 10, we list the statistical data in

Table 4. Performance comparison (Figure 9).

Algorithms	${\mathit{E}}_{\mathit{a}}\left(\mathit{R}\right)$	${\mathit{P}}_{\mathit{e}}(\%)$
VTL	0.361	100
Centroid	0.434	99
APIT	0.396	84

. We observed that the VTL algorithm proposed in this paper outperformed both in localization accuracy and percentage of localizable unknown nodes. Apart from Figure 10, we compared the performance of the three schemes by varying other parameters such as anchor node ratio, communication radius, and GPS error rate in the following sections.

4.4.1. Anchor Node Ratio

The parameters set for the simulation environment were an area of 100 × 100 (${\mathrm{m}}^2$), E_GPS of 0.1 m, R of 20 m, and $N_{\mathrm{t}}$ of 100. In this section, anchor nodes were randomly arranged in a uniform probability distribution. The randomness was reflected by the one-to-one correspondence between the position coordinates of anchor nodes and two-dimensional random numbers. As shown in Figure 11, the effect of the ratio of anchor nodes on the three schemes with respect to $E_{\mathrm{a}}$ and $P_{\mathrm{e}}$ is illustrated. As can be seen in Figure 11a, $P_{\mathrm{e}}$ of three algorithms kept increasing. We observed that $P_{\mathrm{e}}$ of the VTL algorithm was always the highest. As can be seen in Figure 11b, when $r_{\mathrm{a}}$ was less than 30%, the error of VTL was larger because most the unknown nodes in the VTL scheme could complete the estimation with only one beacon message, but $E_{\mathrm{a}}$ was larger in this case, while more beacon messages needed to be obtained in the Centroid and APIT schemes. When $r_{\mathrm{a}}$ varied from 10% to 70%, $E_{\mathrm{a}}$ of the VTL scheme fell the most. As a result, VTL improved the level of location accuracy while maintaining a high positioning coverage rate.

4.4.2. Communication Radius of Anchor Nodes

The larger the communication radius R_a of the anchor node, the more unknown nodes can be covered by beacon messages, which is equivalent to increasing the density of anchor nodes and is conducive to reducing costs. In this part, we studied the influence of the anchor node radius R_a on localization accuracy, as shown in Figure 12. We observed that the estimation errors of Centroid and APIT increased greatly, while VTL barely increased when R_a became larger. The reason why the $E_{\mathrm{a}}$ of Centroid and APIT increased when varying $R_{\mathrm{a}}$ is that larger beacon propagation distances result in a larger accumulated error (see the discussion with Figure 2). In these two schemes, each beacon message was equal in estimating the location of unknown nodes. On the contrary, in VTL, only the closest anchor node was needed to find a “positive region” in each group of anchor nodes. Beacons from farther anchors will have no influence on VTL unless the error in Rss is sufficiently large to cause the wrong closest anchor nodes to be chosen. As all radio signal strengths increase simultaneously, an unknown node’s choice of its closest anchor node will not change. Therefore, the VTL scheme is insensitive to the increase of $R_{\mathrm{a}}$.

4.4.3. GPS Error

In reality, randomly distributed anchor nodes use GPS circuits to obtain their own position. In order to make the simulation experiment more comprehensive, we explored the effect of E_GPS in this section with $R$ equal to 20 m. The simulation result is shown in Figure 13.

As the E_GPS varied from 0 to 20 m, the errors of all schemes increased. This is because the location of the anchor node was used as a reference for estimating the location of an unknown node, which affected the location accuracy directly. Nevertheless, the growth rate of E_a was lower than that of E_GPS, and that of the VTL scheme was the lowest. In general, E_a was rather insensitive to GPS errors.

4.5. Performance Comparisons with C-Shaped Topology

To further investigate the features of the VTL scheme, simulations were arranged with the C-shaped topology, as seen in Figure 14. The C-shaped topology was generated by removing a small rectangle (80 × 60 m²) from a large square (100 × 100 m²). Its total area was only 52% of the square topology in Figure 10. In Figure 14, there are in total 140 nodes (100 unknown nodes (circles) and 40 anchor nodes (asterisks)). Its node density is approximately double that of the square area in Figure 10. One should also be aware that the radio signals sent from the anchor nodes are not bounded by the boundary of the area, no matter the square topology in Figure 10 or the C-shaped topology in Figure 14. This point has no significant effect on the simulation results of Figure 10 but has impacts on the C-shaped topology in Figure 14. Moreover, we assumed that the Voronoi diagrams can only be drawn inside the area of C-shaped topology.

Figure 15 shows the effect of the ratio of anchor nodes r_a on three schemes (VTL, APIT, and Centroid). We increased r_a from 10% to 70% and plotted the estimation percentage (P_e) and estimation error (E_a). Comparing Figure 15 with that of Figure 11, one can observe that P_e of all schemes in the C-shaped topology was higher. Moreover, the P_e of Centroid was closed to that of VTL. This was due to the smaller effective area and higher node density. For E_a performance, those of APIT first slightly decreased but increased again after r_a exceeding 30%, which is because APIT used the overlapping area of triangles formed by detectable anchor nodes to estimate locations. The number of triangles increases with r_a, but some of them may have had areas outside the boundary of the C-shaped topology. Hence, increasing r_a can improve P_e of APIT but may degrade its E_a performance. Both Centroid and VTL had their E_a decreasing with r_a. From the range 10% to 35% of r_a, however, the performance of Centroid was better than VTL, which is because Centroid used the centroid of all detectable anchor nodes to estimate an unknown node’s location. Since Voronoi diagrams must be drawn within the boundary but the boundary does not block radio signals, Centroid may have an advantage unless the density of Voronoi cells is sufficiently high for VTL. Evidently, the performance improvement of VTL is faster than Centroid with increases of r_a even though it is an irregular topology network, e.g., the C-shaped topology. Moreover, one can make the same observation from Figure 11, i.e., VTL has better E_a performance than Centroid when r_a exceeds 15%.

5. Conclusions and Discussion

In this paper, we proposed a novel range-free localization scheme, the Voronoi diagram-based grouping test localization (VTL) scheme, to estimate the location efficiently for wireless sensor networks (WSNs). Unlike many other schemes, VTL only relies on the information broadcasted from static anchor nodes. No communication between nodes is required. The number of locatable unknown nodes can therefore be greatly increased. VTL divides the anchor nodes into multiple groups and uses the corresponding Voronoi cells to compute the estimated location. Apart from improving the accuracy of location estimation, it also largely simplifies the implementation because efficient algorithms are freely available.

From simulation results on regular and irregular network topologies (i.e., square and C-shaped topologies), it shows that VTL will have better performance compared with other range-free localization schemes when it reaches a certain anchor node density, e.g., 30% in the simulations. Hence, a possible application scenario of VTL will be for the extension of an existing WSN with most of the nodes having localization capacity. With VTL, the added sensor nodes do not need sophisticated hardware for communications and localization. Instead, a minimal computational capability is still required for solving the Voronoi diagrams, which grows with O(N_alogN_a), where N_a is the number of original nodes being used as anchors. As computational hardware is continuously improving and the cost is rapidly falling, it should not be an issue for VTL in the coming future. One advantage of VTL is that its location estimation accuracy always grows with the number of anchor nodes. Other range-free localization schemes may not have such features.