Unmanned aerial vehicle–assisted node localization for wireless sensor networks

Abstract

Wireless sensor networks have been proposed for many location-dependent monitoring applications. Existing localization methods often suffer low accuracy and high energy consumption. In response to the above limitations, this article introduces a novel localization approach by virtue of a miniature unmanned aerial vehicle based on our previous IEEE 1851 project, which is named as unmanned aerial vehicle–assisted node localization. The localization process contains three stages, which are node image collection, non-occluded node localization, and occluded node localization, respectively. In the first stage, a unmanned aerial vehicle carrying Global Positioning System shoots the deployment area to collect node images. Then, in the non-occluded node localization phase, the convolutional neural network technique is employed to identify the nodes. And, their positions are determined through the graph matching or Bayesian model averaging approach. Finally, the localized non-occluded nodes start to act as the role of anchors. And, an improved received signal strength indicator–based algorithm is further designed to localize the occluded nodes. Extensive simulations are conducted to verify the effectiveness, in which the accuracy increases by 10%–30% compared with the state of the art methods. Moreover, we implement a prototype localization system with 49 CC2430 nodes and a miniature unmanned aerial vehicle. Results confirm its effectiveness for outdoor sensor networks.

Keywords

Wireless sensor network node identification and localization Bayesian model averaging

Introduction

Wireless sensor networks (WSNs) integrated with sensor technology, embedded computing technology, wireless communications technologies, and distributed information processing technology can monitor, perceive, and acquire various environmental or object information. As an important branch of wireless measurement systems, WSNs have been widely adopted in many location-sensitive applications,¹ such as environment surveillance,² industry data collection,³ and object tracking.⁴

For the monitoring systems with sensor networks, we have ever proposed a layered reference model which consists of sensing layer, collection layer, management layer, and application layer.^5,6 And, in the application layer, the IEEE 1851 standard is constructed for sharing the monitoring data. Giving continuity to that project, we further study the node localization problems in the sensing layer. That is because many data collection protocols are built on the assumption that the geographic positions of the sensor nodes are available. And, the monitoring data without the location information often make no sense.

Many excellent schemes have been proposed for node localization. Based on whether accurate ranging is required, there are basically two types of methods: (1) range-based localization schemes and (2) range-free localization schemes. Range-based localization schemes can obtain good localization accuracy but requires either ranging hardware or system calibration and environment profiling. Range-free localization schemes utilize simple sensing, such as wireless connectivity,⁷ anchor proximity,⁸ or localization event detection,⁹ to localize nodes. These approaches are cost-efficient but exhibit low accuracy. Although localization plays an important role in measurement systems and has been studied extensively, it is still a challenging problem due to extremely limited resources available at each low-cost and tiny sensor.

Recently, the unmanned aerial vehicles (UAVs) are widely used for monitoring outdoor environment. Meanwhile, image processing techniques have rapidly developed with the emergence of deep learning algorithms. Realizing the newest technologies, we try to seek a novel image-based localization method instead of a sole network-based scheme to improve localization performance. In this article, a unmanned aerial vehicle–assisted node localization (UNL) approach is proposed, in which a miniature UAV carrying the Global Positioning System (GPS) and a image sensor is employed to assist localization. The localization process consists of three phases: node image collection, non-occluded node localization, and occluded node localization. In the first stage, node images are collected through the mobile UAV in the deployment region. Image recognition techniques are then used to precisely localize sensor nodes captured by the UAVs in the second stage. The localized nodes are then updated to the anchor nodes in the last stage. Thus, classical location algorithms, such as Amorphous,¹⁰ approximate point-in triangulation (APIT),¹¹ and distance vector-hop (DV-hop),¹² can be adopted to determine node locations that have not been photographed. Specifically, we propose an improved received signal strength indicator (RSSI) method to localize nodes that have not been photographed. In contrast, the main contributions of this article are as follows:

A novel localization scheme is proposed based on image recognition and processing techniques. To the best of our knowledge, it is the first image-assisted node localization for WSNs. With little overhead, the proposed design can be conveniently applied as a transparent supporting layer for many state-of-the-art schemes to achieve better positioning accuracy.

We propose a novel method to evaluate the parameters of Log-normal Shadowing model for received signal strength (RSS) sensing, which fully utilizes the location information of known nodes and thus can improve the localization accuracy of the RSSI-based localization algorithm.

The performance of the proposed design is evaluated by extensive simulations, a prototype localization system with 49 nodes, and a miniature UAV. Results verify the effectiveness of the localization scheme.

This article is organized as follows. Section “Related work” describes related work for localization in WSNs and image recognition techniques. Section “Network model and definition” illustrates the problem formulation for the proposed design. Section “System design” presents the main design with detailed algorithm analysis. Section “Simulation evaluation” evaluates the algorithm in realistic settings and compares it with other localization algorithms. Section “A prototype localization system” introduces a prototype localization system. Section “Conclusion” concludes the article and provides future work direction.

Related work

In this section, we mainly elaborate and discuss the research development of classical localization technologies, as well as image processing technologies.

Existing sensor localization schemes can be divided into two categories: (1) range-based localization schemes and (2) range-free localization schemes. Range-based schemes mainly contain angle of arrival (AOA),¹³ time of arrival (TOA),¹⁴ time difference of arrival (TDOA),¹⁵ RSSI, and so on. The AOA method obtains nodes’ locations based on the angle from the received signal. The TOA and TDOA methods calculate the distance by measuring the propagation speed and time. The RSSI approach utilizes the loss of power in communication module to estimate the distance. In conclusion, the above algorithms perform well by virtue of additional and costly hardware, while they are not suitable for large-scale systems. On the contrary, range-free methods, such as APIT¹¹ and DV-Hop, utilize distance relationship with beacon nodes instead of measuring actual distances or angles. For instance, APIT estimates the node position by means of dividing the localization space into triangular regions. The most possible region where a node resides can be acquired by combining multiple locations of beacon nodes. In the DV-Hop¹² scheme, beacon nodes broadcast their position information throughout the entire network where each node is equipped with a running hop count. The anchor positions, the hop count, and the average distance per hop are the essential information for nodes to estimate their locations. In those systems, only a small quantity of anchors are required, which significantly reduces the system cost. Range-free methods make use of the proximity information for pursuing a low-cost design.¹⁶ To achieve a good accuracy, a high anchor density is often required, which is also impractical for large-scale systems.^17,18

Recently, researchers have proposed several novel location schemes based on channel state information (CSI).¹⁹ As a substitute for MAC layer RSSI, fine-grained PHY layer CSI has gained increasing attention because of its frequency diversity at the granularity of Orthogonal Frequency Division Multiplexing (OFDM).^20–22 In addition, CSI is an informative signature that benefits non-invasive human detection. This scheme has been employed in non-invasive motion detection, entity localization, crowd counting, and walking activity recognition. However, the extraction of CSI is mainly available on few Wi-Fi devices, which is also impractical for large-scale sensor networks.

Image processing, as a key component in this article, is an interesting field because it improves pictorial information for human interpretation. Image processing deals with image acquisition, image enhancement, image segmentation, feature extraction, and image classification. Image recognition has rapidly developed using convolutional neural network (CNN).²³ This network can simulate the human brain; that is, it processes information hierarchically and obtains direct image features from the original pixel of the image. Krizhevsky et al. trained an eight-layer deep model ImageNet database and won the championship in the famous ImageNet image classification match using this model.^24,25 The recognition accuracy rate of the proposed model increased by 10% compared with that of the previous methods. In addition, literature²⁶ pointed that they achieved 4.94% top 5 test errors on the ImageNet 2012 classification data set; this result is the first to surpass human-level performance on visual recognition challenge.

Realizing the limitations of previous works and the rapid development of image processing technologies, this article presents the idea of image-assisted localization. Acting as a transparent supporting layer, our design can effectively improve the system accuracy of state-of-the-art methods with little extra cost.

Network model and definition

A network model in which sensors are randomly deployed is considered in this article. These sensors are located using image processing techniques with the mobile UAV (can be defined $M_{a}$ ), which can fly and photograph over the network. This section presents the following definitions for the proposed design:

Non-occluded node. Sensors can be captured by $M_{a}$ .

Occluded node. Sensors are blocked and thus cannot be captured by $M_{a}$ (such as tree leaf or weed).

Valid picture. The image containing sensors is considered as a valid picture. The set of valid pictures is denoted by $P_{valid}$ .

Invalid picture. The image that does not have any sensor is regarded as an invalid picture. The set of invalid pictures is represented by $P_{invalid}$ .

Real graph. Let the whole real graph be $G_{w} = (V_{w}, E_{w})$ , as shown in Figure 1(a), where $V_{w} = {s_{1}, s_{2}, \dots, s_{n}}$ is a set of sensors in the network and $E_{w} = [v_{ij}]$ is the matrix of distance $v_{ij}$ between sensors $s_{i}$ and $s_{j}$ . The distance can be computed by Euclidean distance formula. Particularly, two nodes can be communicated only in this case where the distance of the two nodes is less than the communication radius. Thus, we should remove these edges with distance higher than the communication radius, and the removing result is a real graph $G_{r} = (V_{r}, E_{r})$ , as shown in Figure 1(b).

Virtual graph. Let $G_{v} = (V_{v}, E_{v})$ is a signal strength virtual graph where $V_{v} = {v_{1}, v_{2}, \dots, v_{n}}$ is a set of sensors, and $E_{v} = [v_{ij}]$ is a matrix of the estimated distance between sensors $s_{i}$ and $s_{j}$ . The estimated distance is calculated based on the Log-normal Shadowing model with signal strength between sensors. The virtual graph is isomorphic to the real graph, as shown in Figure 1(c).

Figure 1.

Wireless sensor network: (a) whole real graph $G_{w} = (V_{w}, E_{w})$ , (b) real graph $G_{r} = (V_{r}, E_{r})$ , and (c) signal strength virtual graph $G_{v} = (V_{v}, E_{v})$ .

System design

The overview of the localization system is shown in Figure 2, which consists of three phases: image collection, non-occluded node localization, and occluded node localization:

Step 1. Image collection—In the node deployment area, a UAV $M_{a}$ automatically takes pictures in accordance with pre-established flight route; these pictures consist of a picture set P, where $P = P_{valid} \cup P_{invalid}$ . The UAV will capture numerous images, which may contain many invalid images. Hence, we use the deep learning–based image recognition technology to screen valid pictures, which mainly includes image preprocessing, image segmentation, and image recognition.

Step 2. Non-occluded node localization—After screening the valid picture, we locate non-occluded nodes by image template matching. By utilizing image template matching, we obtain the coordinates of the nodes in the image. These coordinates are converted into the actual position coordinates because the location information of the pictures taken is known; the coordinate conversion ratio can be calculated by the height of the picture taken and the camera pixels of the UAV $M_{a}$ . Each non-occluded node can obtain a location coordinate $(x, y)$ . Each location coordinate $(x, y)$ of the non-occluded node that corresponds to the sensor node is determined by graph matching or Bayesian model averaging approach.

Step 3. Occluded node localization—Through the last step, the non-occluded nodes are precisely localized and they can be updated to the anchors, leading to the large proportion of the anchors in the network. In this case, we can directly use classical localization algorithms, such as Amorphous, APIT, or DV-hop to localize occluded nodes. For this specific network with a large proportion of anchor nodes, we propose a method for calculating the parameters of Log-normal Shadowing model using the known location information of the non-occluded nodes. This method improves the localization accuracy of the RSSI localization algorithm. The improved RSSI algorithm can be used to accurately locate occluded nodes.

Figure 2.

Localization system overview.

Image collection

The scheme for image collection is designed to ensure that the UAV $M_{a}$ can photograph numerous nodes. In this scheme, $M_{a}$ flight in a circular trajectory, in which the initial position of $M_{a}$ is the center of the circle; the flight radius is continuously expanded to cover the entire node development area. The flying height of $M_{a}$ is set to $2 m$ , and a photo is captured at $1 - s$ interval. After image collection, the picture set P contains a large number of invalid images. Therefore, the following section introduces how to screen the valid picture using image recognition technology.

The size of the picture set P is very large. To ensure the accuracy of localization, we develop a method for screening the valid picture set $P_{valid}$ using deep learning models (such as CNN). The screening process includes the following steps. (1) Image pretreatment—some pictures may be blurred, especially when taken under bad weather (such as foggy day or rainy day). To ensure the accuracy of image recognition, we preprocess these pictures with image enhancement operation based on Retinex algorithm.²⁷Figure 3(a) shows a blurred original image, which is processed by image enhancement algorithm to obtain the improved image shown in Figure 3(b). The picture becomes clear after this operation. (2) Image segmentation—sensor area is extracted by the tested image segmentation algorithm, and the result is shown in Figure 3(c). (3) Image recognition—after image segmentation, the pictures are identified based on CNN to judge that whether the picture is valid or invalid. Literature²⁶ points out that the image recognition accuracy can reach 95% when using ImageNet data set based on CNN. Thus, image processing technology is used to accurately and effectively screen valid pictures.

Figure 3.

Valid picture: (a) original image, (b) enhanced image, and (c) divided image.

Non-occluded node localization

After screening the valid picture, we localize non-occluded nodes by the following steps. First, the positioning coordinates of the non-occluded nodes are obtained by image template matching. Second, the accuracy of the positioning coordinates is analyzed. Third,we introduces the methods for refining the positioning coordinates, which are then matched to the corresponding sensors by graph matching method or Bayesian model averaging approach.

Obtaining the positioning coordinates of non-occluded nodes

Template matching is used in digital image processing to determine small parts of an image that matches a template image. This technique can be used in manufacturing as part of quality control, mobile robot navigation, or image edge detection.²⁸ Image template matching can be employed to obtain the pixel coordinate $(u, v)$ of non-occluded node with the set $P_{valid}$ ; the accuracy of this method is evaluated in Section “Localization performance of non-occluded nodes.” Next, pixel coordinates $(u, v)$ should be converted into the actual position coordinate $(x, y)$ . For each valid picture, two different coordinate systems (pixel coordinate system $O_{uv}$ and actual position coordinate $O_{xy}$ ) are shown in Figure 4. In $O_{uv}$ , the top left corner of the picture is the origin $O_{0}$ . Pixel coordinates $(u, v)$ represent the pixel coordinate of the sensor. In $O_{xy}$ , the center of the picture is the origin $O_{1}$ . The position coordinates $(x, y)$ represent the latitude and the longitude, respectively. Supposing that $(u_{0}, v_{0})$ represents the pixel coordinates of $O_{1}$ and $(x_{0}, y_{0})$ represents the position coordinates of $O_{1}$ . Thus, the coordinate transformation formula is as follows

[\begin{matrix} x \\ y \\ 1 \end{matrix}] = [\begin{matrix} θ_{x} & 0 & x_{0} \\ 0 & θ_{y} & y_{0} \\ 0 & 0 & 1 \end{matrix}] [\begin{matrix} u_{x} - u_{0} \\ v_{y} - v_{0} \\ 1 \end{matrix}]

(1)

where $θ_{x}$ and $θ_{y}$ are the conversion ratio coefficients that can be calculated with the correlation parameters and flight height of the UAV. The pixel coordinates $(u_{x}, v_{y})$ can be obtained by image template matching. Therefore, we can determine the actual position coordinate $(x, y)$ using equation (1).

Figure 4.

Two coordinate systems.

Location error analysis

This section analyzes the error of non-occluded nodes localized by image template matching. Suppose the absence of error in the GPS device of the UAVs; only the height of the UAV can affect the accuracy of localization because it affects the coordinate conversion factor. Although the height of the UAV is set to $2 m$ , the actual flight height is not always the same as the setting. The localization of the center of the picture is known using a GPS device; then, the non-occluded localization error should belong to $[0, 1 / 2 \times \sqrt{L^{2} + W^{2}}]$ , where L is the length of the picture, and W is the width of the picture. The UAV flight altitude may contain some errors and thus must be within $1 - 3 m$ . Under this condition, the area shoot by the UAV is very small for each picture. Therefore, the image template matching exhibits high accuracy for localizing non-occluded nodes.

Refining the location of non-occluded nodes

The shooting interval of the UAV is short; thus, the same node may appear to be repeated in different pictures, resulting in repetition of the position of the same node. To solve this problem, we use an iterative refinement method that can handle duplicate location information. This method aims to use the characteristic at which the positioning accuracy of the picture is very high to screen repeated position coordinates. We then calculate the mean of the repeated position coordinates. First, let $l (x, y)$ be the position coordinates of the non-occluded nodes and L be the set of the position coordinates of all non-occluded nodes. Thus, $D (l_{i}, l_{j})$ represents the distance between the position coordinate $l_{i}$ and the position coordinate $l_{j}$ and can be computed as follows

D (l_{i}, l_{j}) = \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}}

(2)

If $D (l_{i}, l_{j}) < ε$ , then the position coordinate $l_{i}$ and the position coordinate $l_{j}$ represent the same non-occluded node, where $ε$ is the error threshold of the non-occluded nodes. Based on such method, we can find all the duplicate coordinates in set L. Finally, we merge the duplicate coordinates by calculating their mean values. Through the above operation, we can refine the position coordinate set L.

Matching with the corresponding sensors

We obtain a position coordinate set L, which represents the location of non-occluded nodes. However, the sensor represented by each coordinate remains unknown. In this section, we discuss the problem in two different cases. Case 1—the number of coordinates in the set L is equal to the number of sensors in the network; that is, each node is photographed by $M_{a}$ without any occluded node. Case 2—some occluded nodes are present, and the number of coordinates in the set L is not equal to the number of sensors. We can handle these two cases by graph matching and Bayesian model averaging approach, respectively.

Case 1

Under the condition without any occluded nodes, graph matching is used to match the node with the corresponding sensors. Using the precise position coordinates of the non-occluded nodes, we obtain the distance among the non-occluded nodes to construct a real graph $E_{r}$ , as defined in section “Related work.” We can also use the signal strength between any pair of non-occluded nodes to construct a virtual graph $E_{v}$ . This real graph $E_{r}$ is matched with virtual graph $E_{v}$ , which are isomorphic to each other, to identify the node that corresponds to each position coordinate. In the present algorithm, the method proposed by Umeyama²⁹ is used for graph matching. Graph matching can be defined as searching for the $n \times n$ permutation matrix P to satisfy the following: in which, P is the row permutation matrix, and $P^{T}$ is the column permutation matrix

Φ (P) = | | E_{r} - P E_{v} P^{T} | |_{2}^{2}

(3)

\leftarrow \arg \min_{\hat{P}} Φ (\hat{P})

(4)

{\hat{E}}_{v} \leftarrow P {\tilde{E}}_{v} P^{T}

(5)

where P is the $n \times n$ optimal permutation matrix of equation (4) in terms of the minimum estimation error. The result ${\hat{E}}_{v}$ of equation (5) is a matrix isomorphic $E_{r}$ , where indices in both matrices indicate the node identifiers; the vertex in ${\tilde{E}}_{v}$ corresponds to the vertex in $E_{r}$ . This optimization problem is called weighted graphing problem. For graph matching, the edges of the two graphs need not be identical because this method works well when all edges have the same constant scaling factor, as proven in literature.³⁰ Methods for calculating the estimated distance based on the Log-normal Shadowing model may present some errors; thus, we investigated the effect of errors in the next section.

Case 2

Some occluded nodes exist in the sensor network. In this case, the UAV $M_{a}$ moves in different locations and joins the WSN. $M_{a}$ can be seen as different virtual anchor nodes because it moves in different locations. These virtual anchor nodes can be used to match the position coordinates with the corresponding sensors. Supposing $M_{a}$ moves K different locations, the network contains K virtual anchor nodes $(A_{k})$ . Each virtual anchor nodes can be used to construct an evaluation model for calculating the probability that the position coordinate match with one sensor, such as $M_{k}$ (based on $A_{k}$ ). The RSS values from $A_{k}$ form a set $R_{k}$ . Let $l_{i} (x_{i}, y_{i})$ be a known position coordinate and $s_{i}$ be a sensor ID, then the probability that $l_{i}$ corresponds to $s_{i}$ can be computed as follows

P (s = s_{i} | M^{k}, rss) = {\begin{matrix} \frac{rs s_{i}}{rss} & rs s_{i} \leq rss \\ \frac{rss}{rs s_{i}} & rs s_{i} > rss \end{matrix}

(6)

where $rs s_{i}$ represents the signal strength received by sensor i from $A_{k}$ . rss can be computed using the distance $l_{i}$ and the location of $A_{k}$ based on Log-normal Shadowing model because $l_{i}$ and the location of $A_{k}$ are known. However, the signal intensity calculated by the Log-normal Shadowing model is not very accurate due to various factors. To improve this method, we use the Bayesian model average approach. The calculation formula is as follows

P (s = s_{i} | rss) = \sum_{k = 1}^{K} P (s = s_{i} | M^{k}, rss) \times P (M^{k} | rss)

(7)

where $P (y | M^{k}, rss)$ is the probability that $l_{i}$ corresponds to $s_{i}$ based on the evaluation model $M^{k}$ and can be calculated by equation (6). $P (M^{k} | rss)$ is the weight of $M^{k}$ , which can be calculated as follows

P (M^{k} | rss) = 1 - \frac{\sqrt{{({x'}_{k} - x_{i})}^{2} + {({y'}_{k} - y_{i})}^{2}}}{\sum_{i = 1}^{K} \sqrt{{({x'}_{j} - x_{i})}^{2} + {({y'}_{j} - y_{i})}^{2}}}

(8)

where $(x_{i}, y_{i})$ is the position coordinate of the non-occluded node. $(x'_{j}, y'_{j}) (0 < j \leq K)$ represents the position coordinate of virtual anchor nodes, and the anchor node k is represented as $(x'_{k}, y'_{k})$ . In formula (6), the numerator is the distance between the anchor node k and the position coordinates of the non-occluded node $l_{i} (x_{i}, y_{i})$ ; the denominator is the sum of the distance between the virtual anchor nodes and the non-occluded node i. The rationale behind the formula is simple; that is, anchor nodes with higher weight are closer to the non-occluded node position.

Occluded node localization

Using the above-mentioned steps, the non-occluded nodes can be precisely positioned. In this section, we introduce methods for localizing these occluded nodes.

In this stage, non-occluded nodes can be updated to anchor nodes, resulting in large proportion of anchor nodes in the network. As such, we can directly use classical localization algorithms, such as Amorphous, APIT, and DV-hop, to localize the occluded nodes. These algorithms can be named as Amorphous-UNL, APIT-UNL, and DV-hop-UNL, respectively. Specifically, we propose a novel method for improving RSSI method, which can be used to calculate the parameters of Log-normal Shadowing model using the known location information of all anchors. Generally, the common used Log-normal Shadowing model is as follows

f (d) = f (d_{0}) - ξ 10 \log (\frac{d}{d_{0}}) + β

(9)

In equation (9), the key point is to choose appropriate parameters $ξ$ and $β$ because the unreasonable parameters will directly affect the positioning accuracy. Here, the known localization of non-occluded nodes is used to calculate reasonable parameters through regression, which can be deviated and calculated as follows.

Supposing $D = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{m}, y_{m})}$ is known, where x is the RSS value and y is the physical distance, we select appropriate parameters to obtain $f (x_{i}) \approx y_{i}$

f (x_{i}) = ξ \log_{10} x_{i} + β

(10)

Thus, we need the minimum mean square deviation between $f (x_{i})$ and $y_{i}$ , as expressed in the following formula

\begin{array}{l} (ξ *, β *) = \underset{(ξ, β)}{arg min} \sum_{i = 1}^{m} {(f (x_{i}) - y_{i})}^{2} \\ = \underset{(ξ, β)}{arg min} \sum_{i = 1}^{m} {(y_{i} - \log_{10} x_{i} - β)}^{2} \end{array}

(11)

The problem is transformed to calculate $ξ$ and obtain the minimum $E (ξ, β) = \sum_{i = 1}^{m} {(y_{i} - \log 10 x_{i} - β)}^{2}$ . We derive $ξ$ and $β$ in $E_{(ξ, β)}$

\frac{\partial E_{(ξ, β)}}{\partial ξ} = 2 (ξ \sum_{i = 1}^{m} {(\log x_{i})}^{2} - \sum_{i = 1}^{m} (y_{i} - β) \log x_{i}))

(12)

\frac{\partial E (ξ, β)}{\partial β} = 2 (m β - \sum_{i = 1}^{m} (y_{i} - ξ \log x_{i}))

(13)

Making equations (12) and (13) equal to 0, we obtain the optimal closed form of $ξ$ and $β$ as follows

ξ = \frac{\sum_{i = 1}^{m} y_{i} (\log x_{i} - \bar{x})}{\sum_{i = 1}^{m} {(\log x_{i})}^{2} - \frac{1}{m} {(\sum_{i = 1}^{m} \log x_{i})}^{2}}

(14)

β = \frac{1}{m} \sum_{i = 1}^{m} (y_{i} - ξ \log x_{i})

(15)

where $\bar{x} = (1 / m) \sum_{i = 1}^{m} \log x_{i}$

We can utilize the obtained optimized model parameters to calculate the distance between the occluded nodes and the known nodes. And, the localization process is performed by utilizing the multilateration method.

Simulation evaluation

In this section, extensive simulations are constructed to evaluate the proposed design. We model the area of interest as a square map without holes where radio cannot reach. Unless mentioned otherwise, Table 1 lists the default simulation configuration for the following sections. All the statistics reported were averaged over 100 runs to obtain high confidence level. In addition, the localization error LE is defined as follows

LE = \frac{\sum_{i = 1}^{n} \sqrt{{(x_{ie} - x_{ir})}^{2} + {(y_{ie} - y_{ir})}^{2}}}{N_{unknown} \times R}

(16)

where n is the number of all sensor nodes, $(x_{ie}, y_{ie})$ is the estimated coordinate of node $v_{i}$ , $(x_{ir}, y_{ir})$ is the real coordinate of node $v_{i}$ , $N_{unknown}$ means the number of unknown nodes, and R represents the radio communication range.

Table 1.

Default configurations for simulation.

Parameter	Default values and description
System scale	1000 m × 1000 m
Parameters of model	$ξ = 4$ and $β = 6$
Number of sensor nodes	300, randomly deployed withuniform distribution
Communication radiusof sensor node	200 m

Localization performance of non-occluded nodes

We evaluate the localization performance of non-occluded nodes. Figure 5(a)–(c) represents the localization error when GPS errors are 0, 3, and 5 m, respectively. Figure 5(a) shows the lack of error when the GPS device does not have any error in three different image template matching methods including adjustment, correlation coefficient, and normalized cross-correlation methods. Figure 5(b) and (c) shows that the localization error of the non-occluded nodes is approximately equal to the GPS error. Thus, the localization performance of the non-occluded nodes is very good when the GPS device of the UAV exhibits satisfactory localization performance.

Figure 5.

Localization results of non-occluded node in GPS error: (a) 0 m, (b) 5 m, and (c) 10 m.

Performance of graph matching

In this section, we evaluate the performance of graph matching. The distance calculated using the Log-normal Shadowing model may have some errors, which will affect the performance of graph matching. To test the robustness of graph matching method, we set different distance errors, ranging from 1 to 10 m. As shown in Figure 6, the maximum and mean accuracy can maintain more than 90% despite the presence of error in the estimated distance. Thus, graph matching exhibits the robustness and can be used to localize the ndoes.

Figure 6.

Performance of graph matching.

Performance of regression Log-normal Shadowing model

Here, we evaluate the impact of parameters $ξ$ and $β$ , which are the parameters of Log-normal Shadowing model which are described in detail in the occluded node localization part. The Log-normal Shadowing model is first used to generate RSS value among the nodes, in which $ξ = 4$ and $β = 6$ . Based on the generated RSS values, we select different values of $ξ$ and $β$ to backstep the distance between nodes and perform the localization process. The final localization results are shown in Figure 7. We can find that the localization result is evidently affected by the selection of appropriate parameters. When $ξ = 4$ and $β = 6$ , the localization error is the minimum value; selecting other values leads to worse localization results. Specifically, the parameters $ξ$ has a great effect on the localization results. Therefore, we should select the right model parameter as much as possible for obtaining better accuracy.

Figure 7.

Effect of parameters.

To prove that the proposed method can correctly calculate the model parameters, a verification simulation is performed in different cases where the known data show different error levels. First, we generate 150 distance values given the model parameters. Then, the distance values are added to the error, which obey the uniform distribution on $[0, 2 m]$ . At last, we use these noised distance values to calculate the model parameters. Figure 8 shows the comparison between the real and predicted values. In addition, we conduct the evaluation in which the error obeys the uniform distribution on $[0, 5 m]$ , as shown in Figure 9. In both figures, the blue circular points represent the real values, and the square points represent the predicted values. We try each for 100 runs. Results show that the predicted value is close to the real value even though the known data set has some errors. Therefore, the proposed method works well for calculating the parameters of the Log-normal Shadowing model.

Figure 8.

Predicted result of parameter with $2 m$ error.

Figure 9.

Predicted result of parameter with $5 m$ error.

Comparison of localization results

To compare the localization results, we set the rate of anchors to be $10 %$ in the network. Figure 10(a)–(c) depicts the comparison of the localization results of Amorphous, APIT, and DV-hop with those of Amorphous-UNL, APIT-UNL, and DV-hop-UNL. UNL-embedded methods exhibit reduced errors compared with traditional methods. Figure 10(d) shows that RSSI-UNL method exhibits the optimal performance. Thus, we conclude that UNL-embedded methods can improve the localization accuracy of traditional methods. We also propose that the improved methods exhibit good localization accuracy.

Figure 10.

Comparison of localization results: (a) Amorphous vs Amorphous-UNL, (b) Dv-hop vs Dv-hop-UNL, (c) APIT vs APIT-UNL, and (d) comparison of UNL-embedded methods.

Effect of occlusion rate

Occlusion rate is the ratio of occluded nodes to the total nodes. This rate can affect the localization performance of the proposed algorithm. To determine the effect of occlusion rate, we set different occlusion rates from 0.1 to 0.7. We use the improved RSSI localization method to localize occluded nodes. Figure 11 shows that the positioning error increases with increasing occlusion rate. At occlusion rate of 0.7, the location accuracy of the proposed algorithm is higher than that of the other algorithms. The occlusion rate rarely exceeds 0.7 in the actual situation.

Figure 11.

Effect of occlusion rate.

Analysis of energy consumption

In our localization scheme, the energy consumption of sensors can be effectively reduced by UAV-assisted method. Suppose that there are n nodes in the network, which contains m non-occluded nodes. In the non-occluded node localization phase, non-occluded nodes have scarcely any energy consumption as that they are located by UAV. Thus, for our localization scheme, the node energy consumption can be reduced by $((m / n) \times 100) %$ . In the positioning process, the energy consumption reduces along with the increase in non-occluded nodes. Especially, if the nodes in the network are all non-occluded, there would be no energy consumption of nodes.

A prototype localization system

System setup

As shown in Figure 12, we place 49 CC2430 sensor nodes in a $7 \times 7$ grid. The network covers an area of about $50 m \times 50 m$ . The rows and columns are both approximately $5 m$ apart. A miniature UAV with GPS device is used to take photos of nodes.

Figure 12.

Experiment scene.

Localization performance

Figure 13 depicts the node recognition accuracy, and results show that the accuracy is more than 90% when the flying height of the UAV is less than $3 m$ . In addition, Figure 14 depicts the localization results of the proposed algorithm. The black blocks are used to denote the occluded nodes, while the blue stars represent the estimated locations of the non-occluded nodes. The line segment is the offset between the real and estimated positions. Finally, we test the improved RSSI method, and the results are shown in Figure 15. Using the proposed method, we can calculate the parameters ( $ξ = 3.3$ and $β = 4.2$ ) of the Log-normal Shadowing model. We also compare the default parameters ( $ξ = 4$ and $β = 6$ ) with the calculated parameters. The proposed method exhibits high localization accuracy.

Figure 13.

Node recognition accuracy.

Figure 14.

Results of localization.

Figure 15.

Predicted result of parameter.

Conclusion

To improve the localization accuracy and reduce energy consumption for WSNs, this article introduces a UAV-assisted accurate localization approach, which employs image processing techniques to precisely localize sensor nodes captured. An improved RSSI algorithm is further proposed to localize the remaining sensor nodes. Extensive simulations indicate that the proposed localization scheme is robust to realistic settings. Compared with traditional localization algorithms, the proposed design exhibits increased accuracy of about 10%–30%. In addition, we implemented our design with 49 CC2430 nodes and an aerial photography. The proposed localization scheme exhibits robustness, expansibility, and accuracy of positioning. Future work should extend the application and practicability of UNL.

Footnotes

Handling Editor: Qi Han

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported, in part, by the Fundamental Research Funds for the Central Universities (grant no. 2017XKQY080).

ORCID iD

Xu Yang

References

Basten

Wessels

. An overview of sensor networks for environmental noise monitoring. In: Proceedings of the 21st international congress on sound and vibration (ICSV21), Beijing, China, 13–17 July 2014. International Institute of Acoustics and Vibrations.

Werner-Allen

Johnson

Ruiz

et al . Monitoring volcanic eruptions with a wireless sensor network. In: Proceedings of the 2nd European workshop on wireless sensor networks, Istanbul, 2 February 2005, pp.108–120. New York: IEEE.

Yang

Pan

et al . Evaluating service disciplines for on-demand mobile data collection in sensor networks. IEEE T Mobile Comput 2014; 13(4): 797–810.

Padmavathi

Shanmugapriya

Kalaivani

A study on vehicle detection and tracking using wireless sensor networks. Wirel Sensor Netw 2015; 2(2): 2173–2185.

Guo

Chen

Zhang

et al . IMA: an integrated monitoring architecture with sensor networks. IEEE T Instrum Meas 2012; 61(5): 1287–1295.

Guo

Chen

Feng

et al . ISDP: interactive software development platform for household appliance testing industry. IEEE T Instrum Meas 2010; 59(5): 1439–1452.

Rezazadeh

Moradi

Ismail

et al . Impact of static trajectories on localization in wireless sensor networks. Wirel Netw 2015; 21(3): 809–827.

Lasla

Younis

Ouadjaout

et al . On optimal anchor placement for efficient area-based localization in wireless networks. In: Proceedings of the 2015 IEEE international conference on communications, London, 8–12 June 2015, pp.3257–3262. New York: IEEE.

Zhong

Sensor node localization with uncontrolled events. ACM T Embed Comput S 2012; 11(3): 668–679.

10.

Chen

Gao

et al . SSL: signal similarity-based localization for ocean sensor networks. Sensors 2015; 15(11): 29702–29720.

11.

Doherty

Pister

KSJ

Ghaoui

LE.

Convex position estimation in wireless sensor networks. In: Proceedings of the IEEE international conference on computer communications (INFOCOM 2001), Anchorage, AK, 22–26 April 2001, vol. 3, pp.1655–1663. New York: IEEE.

12.

Niculescu

Nath

DV based positioning in ad hoc networks. Telecommun Syst 2003; 22(1): 267–280.

13.

Savvides

. Dynamic fine-grained localization in ad-hoc networks of sensors. In: Proceedings of the international conference on mobile computing and networking, Rome, 16–21 July 2001, pp.166–179. New York: ACM.

14.

Cheng

Thaeler

Xue

et al . TPS: a time-based positioning scheme for outdoor wireless sensor networks. In: Proceedings of the IEEE international conference on computer communications (INFOCOM 2004), Hong Kong, China, 7–11 March 2004, vol. 4, pp.2685–2696. New York: IEEE.

15.

Priyantha

Chakraborty

Balakrishnan

. The cricket location-support system. In: Proceedings of the 6th annual international conference on mobile computing and networking (MOBICOM 2000), Boston, MA, 6–11 August 2000, pp.32–43. New York: ACM.

16.

Lederer

Wang

Gao

Connectivity-based localization of large-scale sensor networks with complex shape. ACM T Sensor Network 2009; 5(4): 789–797.

17.

Liu

Cui

A range-free multiple target localization algorithm using compressive sensing theory in wireless sensor networks. In: Proceedings of the IEEE 11th international conference on mobile ad hoc and sensor systems, Philadelphia, PA, 28–30 October 2014, pp.690–695. New York: IEEE.

18.

Niu

Huan

Chen

NMCT: a novel Monte Carlo-based tracking algorithm using potential proximity information. Int J Distrib Sens N 2016; 12: 1–10.

19.

Yang

Zhou

Liu

From RSSI to CSI: indoor localization via channel response. ACM Comput Surv 2013; 46(2): 25.

20.

Liu

Cao

Tang

et al . Wi-Sleep: contactless sleep monitoring via WiFi signals. In: Proceedings of the 2014 IEEE real-time systems symposium, Rome, 2–5 December 2014, pp.346–355. New York: IEEE.

21.

Zhou

Yang

et al . Towards omnidirectional passive human detection. In: Proceedings of the IEEE international conference on computer communications (INFOCOM 2013), Turin, 14–19 April 2013, vol. 12, pp.3057–3065. New York: IEEE.

22.

Wang

Liu

Chen

et al . E-eyes: device-free location-oriented activity identification using fine-grained WiFi signatures. In: Proceedings of the IEEE real-time systems symposium, Maui, HI, 7 September 2014, pp.617–628. Association for Computing Machinery.

23.

Hinton

Salakhutdinov

RR.

Reducing the dimensionality of data with neural networks. Science 2006; 313(5786): 504–507.

24.

Fergus

Perona

et al . Learning object categories from internet image searches. P IEEE 2010; 98: 1453–1466.

25.

Russakovsky

Deng

et al . Imagenet large scale visual recognition challenge. Int J Comput Vision 2015; 115(3): 211–252.

26.

Zhang

Ren

et al . Delving deep into rectifiers: surpassing human-level performance on ImageNet classification. In: Proceedings of the 2015 IEEE international conference on computer vision (ICCV), Santiago, Chile, 7–13 December 2015, pp.1026–1034. New York: IEEE.

27.

Jiang

Woodell

Jobson

DJ.

Novel multi-scale retinex with color restoration on graphics processing unit. J Real-Time Image Pr 2015; 10(2): 239–253.

28.

Duan

Zhang

XY.

A novel image template matching based on particle filtering optimization. Pattern Recogn Lett 2010; 31(13): 1825–1832.

29.

Umeyama

An eigendecomposition approach to weighted graph matching problems. IEEE T Pattern Anal 1988; 10(5): 695–703.

30.

Jeong

Guo

et al . Autonomous passive localization algorithm for road sensor networks. IEEE T Comput 2011; 60(11): 1622–1637.