A Sensor Positioning Scheme with High Accuracy in Nonuniform Wireless Sensor Networks

Abstract

In wireless sensor networks, a geographical positioning scheme is one of core technologies for sensor applications such as disaster monitoring, environment monitoring, and military services. For this reason, the research for range-free positioning schemes had progressing actively. And a density probability scheme based on the central limit theorem and normal distribution theory has been proposed to improve the location accuracy in nonuniform sensor network environments. The density probability scheme estimates 1-hop distance by using communication between nodes. After that, it estimates the final position of an unknown node. But the density probability scheme has a problem that it has equivalent 1-hop distance for all of nodes in the same area. To overcome this problem, we propose a novel sensor positioning scheme in non-uniform wireless sensor networks. As a result, the proposed scheme ensures the high accuracy of sensor positioning in non-uniform networks. To show the superiority of our proposed scheme, we compare it with the existing scheme such as DV-based position scheme. Our experimental results show that the proposed scheme improves by about 36% sensor positioning accuracy over the existing scheme on average even in non-uniform wireless sensor networks.

1. Introduction

By the remarkable development of computing technologies, the ubiquitous environment has been served to provide human beings with more convenient life. This ubiquitous environment provides us with diverse and convenient services through the organic interaction among human beings, computers, and things. The wireless sensor network, one of basic technologies to detect the event and to control the external human environment in the ubiquitous environment, has been vigorously studied. The ad hoc wireless sensor network is constructed autonomously and collects diverse environment information through the communication among sensor nodes. A sink node receives sensing values from sensor nodes in sensing area and transmits them to a user. The collected information is used for diverse purposes such as observation of wildlife's habitat, military affair, fire detection, environmental monitoring, medical service, and U-City for application environment [1, 2].

In the sensor network, the positioning technology is one of the most required and basic technologies. In the positioning scheme using the wireless devices, every equipment is generally carrying the Global Positioning System (GPS) in order to collect positioning information. But it causes problems such as excessive energy consumption due to GPS modules and high costs for their construction in the large-scale sensor network environments [3, 4]. Therefore, the positioning schemes to reduce the energy consumption in the sensor network with limited energy have been actively studied.

Typical positioning schemes are classified into the range-based schemes and range-free schemes. The range-based schemes measure the position of sensor nodes by using signal strength or time difference between nodes and the range-free schemes measure the distance and estimate the position through the connection information between nodes and the position information of an anchor node without any subsidiary hardware equipments [5]. Recently range-free schemes have been proposed [6–9]. Unlikely range-based schemes, range-free schemes measure the distance and estimate the position through the connection information between nodes and the position information of an anchor node. In addition, it is efficient in the energy consumption and the cost to construct the network because only an anchor node is equipped with GPS module. Therefore, the positioning schemes through the anchor nodes have been actively studied. The existing schemes estimated the distance between nodes and decided the position in the uniform sensor network environments without considering density. However, in real applications, since sensors are distributed on the sensing fields randomly through aircrafts, missile, and so on, the nonuniform sensor network environments are constructed in specific areas [10]. Therefore, the positioning schemes for the uniform sensor network environments are not suitable for the actual situations since their error rates of density probability are very high in the non-uniform sensor network environments.

To solve the problem of the existing range-free schemes, we propose a novel positioning scheme by using the density probability model in the non-uniform network environment. In the proposed scheme, the minimum anchor nodes are used and the distance is estimated according to the density in the non-uniform sensor network environments. By doing so, the cost to construct the sensor network can be minimized and the positioning precision can be improved.

The remainder of this paper is organized as follows. Section 2 overviews the existing positioning schemes in the wireless sensor networks and analyzes their problems. In Section 3, we present our sensor positioning scheme using density probability models in non-uniform wireless sensor networks. Section 4 shows the simulated experiments and compares the existing scheme with the proposed scheme. Finally, we present concluding remarks in Section 5.

2. Related Work

2.1. Range-Based Positioning Schemes

Range-based schemes use absolute point-to-point distance or angle information to calculate positions between neighboring sensors using extra communication modules. After this, the node estimates position of unknown nodes by trilateration algorithm [11]. Common approaches for range-based schemes include Time of Arrival (ToA), Time Difference of Arrival (TDoA), and Angle of Arrival (AoA) for this algorithm [3]. ToA and TDoA measure signal arrival time or the difference of arrival times to calculate distance based on transmission time and speed. They can be applied to many different kinds of signals such as RF, acoustic, and ultrasound signals.

Range-based positioning schemes, such as ToA, TDoA, and AoA, suffer from the positioning errors since wireless channels are very sensitive to the surrounding environment when they use the strength and arrival time of each signal for positioning. ToA, TDoA, and AoA also have problems such as the usage of additional equipments, additional costs, and large energy consumption due to extra modules for a synchronization system among sensor nodes. Therefore, the range-based schemes in the wireless sensor network have a difficulty to positioning.

2.2. Range-Free Positioning Schemes

DV-HOP algorithm [7] and improved DV-HOP scheme [8, 9] are range-free and multi-hop routing positioning scheme in wireless sensor networks. They measure the positions of the unknown nodes by using the average distance of 1-hop between anchor nodes. DV-HOP algorithm is composed of steps as follows.

Firstly, each anchor node broadcasts a beacon frame containing its position with a hop-count value initialized to 0 to be flooded throughout the network. Then, the nodes that receive the information of anchor nodes store the cumulated hop counts from the anchor nodes to themselves and the positions of the anchor nodes. After that, all of the nodes calculate average 1-hop distance through the hop count from each anchor node to themselves. The average 1-hop distance of anchor node i is estimated using (1). Here $h_{ij}$ is the minimum hop count of anchor nodes i and j, and ( $x_i$ , $y_i$ ) and ( $x_j$ , $y_j$ ) are their coordinates. As a result, $C_{ij}$ is the calculated average 1-hop distance. In the example in Figure 1, nodes L1, L2, and L3 are anchor nodes. Consider

$$\begin{array}{cc}& C_{ij}=\hspace{0.17em}\hspace{0.17em}\frac{\sum \sqrt{{\left(x_i-x_j\right)}^{\mathrm{2}}+{\left(y_i-y_j\right)}^2}}{\sum h_{ij}},\hspace{1em}\hspace{0.17em}\hspace{0.17em}i\ne j.\end{array}$$

(1)

Figure 1

Example of DV-HOP estimated distance.

In a similar manner, the estimated average distances of 1-hop of L2 and L3 are 16.42 m and 15.90 m, respectively. Unknown node A selects 1-hop distance of anchor node L2 as the average 1-hop distance since node L2 has the shortest path for the node A compared with nodes L1 and L3. And then, node A calculates the estimated distance from three anchor nodes, anchor nodes i, j, and k as (2). Finally, node A is assuming its position from three anchor nodes using trilateration. Consider

$$\begin{array}{cc}& D_i=\hspace{0.17em}\hspace{0.17em}{h}_{ai}\times C_{ij},\hspace{1em}\hspace{0.17em}\hspace{0.17em}\left(i=\mathrm{1},\mathrm{2,3}\dots ,n\right).\end{array}$$

(2)

DV-HOP causes lower positioning error and uses fewer anchor nodes than the existing schemes However, in non-uniform environments where each area has a different density, DV-HOP causes higher positioning errors. DV-HOP should also distribute many anchor nodes to increase positioning accuracy. Therefore, we propose the node density probability model and the positioning scheme to overcome the problems of DV-HOP.

3. The Proposed Sensor Positioning Scheme Based on Neighbor Density

In this paper, we propose a novel positioning scheme to reduce the positioning error and to decrease the construction costs in the non-uniform distributed sensor networks. The existing schemes cause very large positioning errors in each area with a different density. To reduce the positioning errors, it needs to distribute more anchor nodes in the network. However, it significantly increases the construction cost due to many anchor nodes. To solve this problem, the proposed scheme uses at least 4 anchor nodes placed at the boundary of the sensing fields. Thereby, the proposed scheme minimizes the cost of construction of the sensor network. Figure 2 shows the process of the proposed positioning scheme. First, when a position query is issued in the sensor network, the unknown nodes assume their distances through the information of the anchor nodes. Second, the distances of the unknown nodes are refined with distances between the anchor nodes and them. We explain steps 1 and 2 of Figure 2 in detail in Sections 3.2 and 3.3.

Figure 2

Flow chart of the proposed scheme.

The proposed scheme is composed of the following four steps.

Step 1.

The anchor nodes that exist in the boundary of the network broadcast their positions.

Step 2.

The unknown nodes estimate the 1-hop distances of their neighbor nodes according to the densities of themselves and their neighboring nodes.

Step 3.

Each node refines the estimated 1-hop distance by calculating distance error ratio between the real distances of anchor nodes and the relative distances through the shortest paths between anchor nodes.

Step 4.

The unknown nodes estimate their positions by using the refined distance.

3.1. Network Model and Characteristics

The anchor nodes A1, A2, A3, and A4 are deployed in each corner of the sensing area. In the initial step, anchor nodes broadcast their positioning information messages (node ID, hop, coordinates) to all the nodes. The normal sensor nodes save the information of the anchor nodes and neighbor nodes like Table 1.

Table 1

Shortest path and neighbor node list.

Shortest path ID	Shortest path hop	Neighbor list
$n_i$	Cumulated hop	$n_i,n_{i+\mathit{1}},\dots ,n_{i+n}$

3.2. Distance Estimation Considering Neighbor Density Probability

Each node estimates 1-hop distance by using Central Limit Theorem [12, 13] based on a normal probability distribution. The normal distribution or Gaussian distribution is a continuous probability distribution that has a bell-shaped probability density function. If the number of trials or samples objects increase, it shows the normal distribution curve. The theory that sensor network environment is consistent with the normal distribution model is the central limit theorem. The average of normal distribution model approximates to μ as the number of samples increases. In the sensor network environment where thousands of sensors are deployed, samples are located in the center of the normal distribution curve. Therefore, on the basis of the central limit theorem and the normal distribution model, each sensor node estimates the distances to the neighboring nodes. For 1-dimension, there is a point of the specific node that is an average of zero point. In other words, the point of 1/2 of the communication radius is the probability that node exists.

As shown in Figure 3, if the node draws a circle for the communication range and angle ( $\theta =360$ °), it is farther away than the estimated position of 1-dimension. Therefore, the estimated position for 2-dimension unlike the position of 1-dimension is a point in the circle that the area of its inner circle is equal to the area of its outer circle. As a result, it is possible to estimate the distance between nodes through the values of the normal distribution table.

Figure 3

The estimated position of a sensor node.

Equation (3) is the distance calculation equation between neighbor nodes based on the values of the normal distribution table. R is a communication range of a sensor node and n is the number of its neighbor nodes. And then, the entire sensor nodes estimate the distance between them and their neighbor nodes through (3). It makes it possible to estimate more real distance in the non-uniform sensor network where the areas have different densities. Consider

$$\begin{array}{cc}& d_{\text{Est}\left(k\right)}=\sqrt{\frac{\pi r^{\mathrm{2}}/\mathrm{3}}{\pi }}=\sqrt{\frac{r^{\mathrm{2}}}{\mathrm{3}}},\hspace{1em}n=\mathrm{2},\\ d_{\text{Est}\left(k\right)}=\sqrt{\frac{r^{\mathrm{2}}}{n+\mathrm{1}}},\hspace{1em}\hspace{0.17em}\hspace{0.17em}n\ge \mathrm{3}.\end{array}$$

(3)

3.3. Error Correction of an Estimated Distance

If the position of a node is localized using the estimated distance, it has an error for shorter or longer than the real distance since the size of the whole network is not considered. As a result, the proposed scheme needs the correction to reduce the error rate of the estimated distance. Figure 4 shows the error rate of an estimated distance. A real distance between anchor node A2 and anchor node A3 is 100 m. However, the estimated distance through (3) is 148 m. Therefore, in order to correct the error between the real distance and the estimated distance, each node through (4) calculates an error rate for the accumulated distance of the two anchor nodes through their shortest path and their real linear distance.

Figure 4

Correction of error rate for an estimated distance.

And then, each unknown node refines the estimated distance through the error rate. Finally, the unknown nodes through 4 anchor nodes measure their positions with traditional trilateration. Consider

$$\begin{array}{cc}& d_{\text{est}\hspace{0.17em}-\hspace{0.17em}\text{All}\left(k\right)}=\sum _{\text{Node}\hspace{0.17em}\hspace{0.17em}\text{ID}\left(k\right)=\mathrm{0}}^i{d}_{\text{Est}\left(k\right)}+\sum _{\text{Node}\hspace{0.17em}\hspace{0.17em}\text{ID}\left(k\right)=\mathrm{0}}^j{d}_{\text{Est}\left(k\right)},\hspace{1em}\hspace{0.17em}\hspace{0.17em}i\ne j,\\ d_{\text{Real}\left(i,j\right)}=\sqrt{{\left(x_i-x_j\right)}^{\mathrm{2}}+{\left(y_i-y_j\right)}^{\mathrm{2}}},\\ \text{error}\left(k\right)=\frac{d_{\text{Real}}}{d_{\text{Est}-\text{All}\left(k\right)}},\\ d_{\text{ref}\left(k\right)}=d_{\text{Est}\left(k\right)}\times \text{error}.\end{array}$$

(4)

4. Performance Evaluation

4.1. Network Environment

We have developed a simulator based on JAVA to evaluate our proposed scheme and the existing scheme, DV-Hop. The sensor network is based on random and non-uniform (Gaussian) models by considering the real distribution characteristics of sensors. Table 2 shows the evaluation environments. The size of the sensor network is a square area of 200 m × 200 m. Four anchor nodes are deployed at each corner of the sensing field and the number of sensor nodes is varied from 100 to 500. The communication ranges for sensor nodes and anchor nodes are 10 m, 15 m, 20 m, 25 m, and 30 m. The performance evaluation is performed based on J-Sim v.0.6.0 [14].

Table 2

Evaluation environment.

Parameter	Value
Size of sensor networks ( $\text{m}\times \text{m}$ )	$\mathit{200}\times \mathit{200}$
Number of distributed normal nodes	100~500
Number of distributed anchor nodes	4
Radius of communication (m)	10~30

A positioning error rate is difference between a real coordinate and an estimated coordinate. Therefore, we evaluate the accuracy as the distance error rate between the real coordinate of a node and the coordinate of its estimated position. Equation (5) for a real distance and a positioning coordinate is used:

$$\begin{array}{cc}& \text{Position}\hspace{0.17em}\hspace{0.17em}\text{Error}\hspace{0.17em}\hspace{0.17em}\left(\%R\right)=\frac{\sqrt{{\left(x^{\prime }-x\right)}^2+{\left(y^{\prime }-y\right)}^2}}{r_{\max }}\times \mathrm{100}.\end{array}$$

(5)

4.2. Performance Evaluation Results

Figure 5 shows the localization results of DV-HOP and the proposed scheme. As shown in Figure 5, our proposed scheme achieves better performance than the DV-HOP. In Figure 5, black points are anchor nodes and white points are unknown nodes. And, a black line is the distance between a real position and an estimated position. Simulation calculated the average error rates every ten times for the proposed and DV-HOP algorithms when the communication range is varied from 10 m to 30 m.

Figure 5

Comparison of localization results.

Figure 6 shows the average positioning error rate according to the communication range. With the same communication range, the position error rate of our proposed scheme is smaller than that of DV-HOP. In the case of DV-HOP, since the hop distance is proportional to the communication range, the accuracy of its positioning is low. In the random mode, the proposed scheme achieves about 30% performance improvements over DV-HOP in terms of the positioning accuracy. In the non-uniform model that has very large deviation of density, the proposed scheme achieves about 36% higher accuracy than DV-HOP. The reason is that the proposed scheme measures the positions of the nodes by considering their densities. As a result, our scheme improves the accuracy of positioning over the existing scheme.

Figure 6

Average positioning error according to the communication range.

Figures 7 and 8 show the average positioning error rate according to the network size and the number of sensor nodes. Figure 7 shows similar positioning error ratio for our scheme and DV-Hop in the small 50 × 50 scale network. However, the proposed scheme in the large 500 × 500 scale network improves the accuracy of positioning over DV-Hop. Figure 8 shows the average positioning error according to the number of total nodes. Our scheme improves the accuracy of positioning by about 49% over DV-Hop on average. Unlike DV-Hop, the proposed scheme shows the high position accuracy as each node has a different 1-hop distance. As a result, our scheme has an advantage that it can be applied to various environments because it has high accuracy in the large scale network as well as the small scale network.

Figure 7

Average position error according to the network size.

Figure 8

Average positioning error according to the sensor nodes.

5. Conclusion

In this paper, we have proposed the sensor positioning scheme using density probability models in non-uniform wireless sensor networks that considered characteristics of the sensor node deployment. The proposed scheme estimates the distance between nodes using the characteristics of density in non-uniform sensor network environments. The proposed scheme performs error correction between the estimated distance and the real distance. Therefore, it is possible to reduce the positioning error. As the results of performance evaluation, the proposed scheme showed that the positioning accuracy was significantly improved over the existing scheme. In the future work, we plan to extend our work to estimate the positions of sensor nodes in the case of network-hole occurrence.