Sage Journals: Discover world-class research

Abstract

Large-scale deployment of mobile wireless sensor networks has been widely used in some dangerous and hostile urban security surveillance scenarios. As a new network architecture, software-defined networks was introduced into wireless sensor networks to form a new software-defined wireless sensor networks to solve the problem of balanced large-scale deployment of sensor networks and simplify the complexity of network management. In this article, we first develop an original confident information coverage–based multiplicatively weighted Voronoi diagram through sensor clustering and sensor collaborative sensing. And then, we propose two sensor collaborative redeployment algorithms based on the novel confident information coverage–based multiplicatively weighted Voronoi diagram and software-defined wireless sensor networks architecture to provide high-confidence coverage and improve the coverage ratio. Finally, we demonstrate the superiority of the confident information coverage–based multiplicatively weighted Voronoi diagram and the effectiveness and efficiency of our proposed algorithms via a series of experiments.

Keywords

Software-defined wireless sensor networks high-confidence coverage multiplicatively weighted Voronoi sensor redeployment sensor collaborative sensing

Introduction

Mobile wireless sensor networks (MWSNs) combining a wealth of low cost, intelligent, multi-functional and high reliable sensing devices or sensors with mobility act as crucial components of core smart city infrastructure.^1,2 In the past few years, there are many critical applications of MWSNs including smart city safety surveillance, smart healthcare, intelligent transportation, smart building, smart lighting, and city event alert and prediction.^3,4

One important category of MWSNs-based applications for safety surveillance is the environmental radiation monitoring of nuclear facilities including nuclear power plants, nuclear fuel fabrication plants, and uranium tailings which all are remote, dangerous, and hostile industrial environments to human.⁵ In the 272 uranium tailing, as shown in Figure 1, some radionuclides may flow outside of the monitored area and diffuse to its surrounding environments via soil and ground water, which would pose a great threat to citizens.⁶ Therefore, radiation safety surveillance of the 272 uranium tailing is significantly critical for the health care and public security of citizens in Hengyang city.

Figure 1.

Radiation safety surveillance of the 272 uranium tailing.

How to efficiently provide effective coverage service to cover the target coverage area is one of the main concerns and challenges for the success of MWSNs-based applications. As a new type of network architecture, software-defined network (SDN) has brought tremendous innovation to network management. The application of software-defined technology to WSNs has brought new ideas to traditional WSNs to solve the problem of network balance.⁷ At present, software-defined wireless sensor networks (SDWSN) have attracted a lot of attention and research due to its unique advantages, such as the full use of resources, simple configuration and management, rapid update, and rapid technological innovation. SDWSN greatly meets the urgent requirements of the Internet of Things while overcoming some of the challenges of WSN.⁸ Figure 2 shows the SDWSN architecture, using SDN technology to achieve communication and control of the lower sensor nodes in the coverage area.

Figure 2.

Software-defined wireless sensor networks architecture.

Although scholars and industry have made great progress in the field of coverage control in MWSNs in recent years, most of them are based on the simple and ideal disk coverage model, which fails to fully consider the collaborative perception and cooperation of multiple sensors, thus unable to provide high-confident and reliable coverage service. Inspired by realistic field reconstruction applications, in this article, our previously proposed novel confident information coverage (CIC) model⁹ is adopted as the basic coverage model instead of the traditional disk coverage model. The CIC model can extremely develop the collaborative relationship among nearby sensors from the view of information cooperation, fusion, and reconstruction to provide high-confidence coverage performance.

By using the Voronoi diagram, region coverage problem can be treated as target coverage problem of each Voronoi polygon to reduce the complexity of the coverage problem,¹⁰ so many Voronoi-based sensor redeployment algorithms are emerging. In Liao et al.,¹¹ an algorithm based on group partition and a greedy algorithm based on Voronoi partition of the deployment area are proposed to solve the target coverage problem of the network. Considering the remaining energy consumption of mobile sensor nodes, a new autonomous joint sensing range and relocation control algorithm is proposed,¹² which optimizes network coverage and lifetime. In this proposed algorithm, the sensor iteratively adjusts its sensing range through the action of its residual energy, and moves within its respective multiplicatively weighted Voronoi (MW-Voronoi) area, which ultimately increases the field coverage. However, almost all existing Voronoi-based sensor deployment algorithms are based on disk model which is too simple and ideal and ignore the ability of collaborative sensing among neighboring sensors.

In order to overcome the above shortcomings and provide high-confidence coverage performance, this article introduces SDN technology to control large-scale sensor nodes to perform redeployment tasks, and two novel high-confidence sensor collaborative redeployment algorithms, respectively, named as CIC-Minmax-Vertex and CIC-Maxmin-Vertex, are proposed based on MW-Voronoi polygon theory and the CIC model.

Based on our analysis and investigation, to our best knowledge this work is the first to provide high-confidence coverage by fusing MW-Voronoi and node cooperative sensing. The main contributions of this work are summarized as follows.

A novel MW-Voronoi diagram based on sensor collaboration of the CIC model, namely CIC-based MW-Voronoi, is proposed to enlarge the coverage area and improve the coverage performance compared with the traditional disk coverage model.

Aiming to more efficiently and effectively redeploy sensors to obtain CIC, two novel sensor redeployment algorithms, namely CIC-Minmax-Vertex and CIC-Maxmin-Vertex, are proposed based on the CIC-based MW-Voronoi diagram under the SDWSN architecture.

Experimental results demonstrate significant superiority of our proposed algorithms than other peer sensor deployment schemes by the metrics of the network coverage ratio and the iteration time.

The rest of this article is as follows, section “Related works” introduces the related works. Section “System model” describes the selected models. In section “The proposed sensor redeployment algorithms,” two novel redeployment schemes are discussed in detail. Performance evaluations and conclusions are drawn in section “Performance evaluation” and section “Conclusion,” respectively.

Related works

Coverage control of MWSN is an optimization problem that maximizes coverage ratio while ensures minimal consumption. In many current studies, regional division methods have been adopted to divide an entire sensing field into a number of small areas and then studies the coverage of each small area rather than the coverage of entire field to reduce coverage complexity.

For the problem of regional division, in the literature,¹³ three deployment methods based on Voronoi diagram area division are proposed to detect coverage vulnerabilities, which are Voronoi algorithm (VOR), vector algorithm (VEC) and Minimax algorithm.

In Lee et al.,¹⁴ two schemes are proposed to maximize sensor coverage by using Voronoi diagrams, which are centroid and dual-centroid schemes. The Voronoi diagram is also used in the centroid algorithm in Fang et al.,¹⁵ which iteratively calculates the centroid position of each small Voronoi region as the desired position for sensor movement. Moreover, an algorithm considering the blind-zone center of the neighbors is further proposed to reduce the overlapping coverage area of the sensor. In addition, regarding the movement of nodes, the authors in Kong et al.¹⁶ design a multi-node adaptive barrier system and use SDN technology to control node movement. An efficient distribution mechanism is proposed for the SDWSN controller using fragmentation in Kobo et al.¹⁷

In some heterogeneous networks, the physical properties of the sensor itself will not be exactly identical. Based on this, the MW-Voronoi diagram is proposed considering the coverage priority at different positions in the entire field area.¹⁸ In Abbasi et al.,¹⁹ aiming at the blanket coverage problem, a method is proposed to make the nodes move to the centroids of the respective Voronoi units while considering the influence of the moving boundary to ensure the local optimality of the moving coverage area. The authors in Song et al.²⁰ proposed an intuitive method for dealing with limited sensor communication ranges and achieving uniformly deployed position optimization while considering the energy consumption caused by sensor movement. In Elwin et al.,²¹ the robot recognizes the distance to determine Voronoi neighbors more effectively, which is more helpful to solve the positioning problem. In Chang et al.,²² weighted Voronoi is used to divide the self-sensing regions responsible for each sensor, and a sensing radius adaptive (SRA) mechanism is proposed according to the remaining energy. The sensor can adjust its own sensing radius and neighbors’ location to maximize network life. The authors in Mahboubi et al.²³ proposed several MW-Voronoi-based algorithms for performing iterative sensor redeployment.

All mentioned algorithms above are based on simple disk model which does not consider the collaborative sensing between sensors. In recent years, a new type of CIC model has emerged,⁹ which constructs a new coverage relationship between sensor nodes and physical space points, uses a stochastic process to model environmental variables, examines information collaborative reconstruction from the spatial dimension, and measures the coverage by root mean square error of the reconstructed information on the spatial point. In order to solve the deficiencies in the above technology and seek to develop a new and more effective method, we aim to design a novel CIC-based MW-Voronoi diagram and introduce SDWSN technology to propose sensor redeployment algorithms to achieve greater coverage with fewer sensor nodes.

System model

CIC model

Definition 1

CIC

For any random environment, under a given reconstruction function $F$ , if the time-average root mean square error (RMSE) of the reconstructed information $Φ (p)$ of a spatial point $p$ is not larger than the application requirement $ε$ ,that is, $Φ (p) \leq ε$ , this point $p$ is called being confident information covered (or $Φ$ -covered). The environment is fully confident covered when all spatial points in the environment are confident information covered.

In the definition above, the CIC model chooses the classical Ordinary Kriging estimator²⁴ as the reconstruction function and selects the time-average RMSE to estimate the quality and precision of the confident information reconstruction for each reconstruction point $p$

Φ (p) \equiv \sqrt{\frac{1}{T} \sum_{t = 1}^{T} {(u^{t} (p) - {\hat{u}}^{t} (p))}^{2})}

(1)

where the $u^{t} (p)$ represents the actual value of the environmental variable and ${\hat{u}}^{t} (p)$ denotes the estimated value of sensor cooperative sensing at the point $p$ . $T$ is the number of samples of the $u^{t} (p)$ and the ${\hat{u}}^{t} (p)$ .

The novel CIC model fully utilizes the advantages of the OK estimator and the spatial correlation range $a$ to exploit the intrinsic spatial correlation of the physical attributes and makes full use of cooperative sensing among the sensors within the $a$ to remarkably improve the coverage quality and significantly save the cost of network deployment. As can be seen in Figure 3, under the disk coverage model with sensing radius $r$ , p1 and p2 can be covered by sensors s1 and s2, respectively, but p3 and p4 cannot be covered because p3 and p4 are out of the coverage range of s1, s2, s3, and s4. If we adopt the CIC model, p3 and p4 can be $Φ$ -covered by the cooperative sensing among the sensors s1, s2, s3 and s4.

Figure 3.

The CIC model: an example of cooperative sensing.

Voronoi diagram and weighted Voronoi

Let $S = {s_{1}, s_{2}, \dots, s_{n}}$ denote the set of sensor nodes in the entire sensing area $R^{2}$ . These sensor nodes divide the plane into $n$ convex polygons, and there is only one sensor node in each polygon. The edge of each polygon is the vertical bisector of the line connecting two neighboring nodes, and each polygon vertex is the intersection of the corresponding vertical bisector. We refer to these nodes as generating nodes of polygons, and at any point in the plane, we have the following properties: one is that any position point is closest to the generated node within its polygon, the other is that the distance between the point on the polygon edge and the adjacent two nodes is equal. The resultant diagram is called a Voronoi diagram shown in Figure 4. The mathematical characterization of each region can be expressed as follows

Π_{i} = {q \in R^{2} | d (q, s_{i}) \leq d (q, s_{j}), j \in {1, \dots, n}, j \neq i}

(2)

where $q$ is any point in the $s_{i}$ partition and $d (q, s_{i})$ is the euclidean distance between the points $q$ and $s_{i}$ .

Figure 4.

An example of the Voronoi diagram.

Sensor nodes are not exactly of the same properties in some cases. Without considering the influence of external factors, we assume that each sensor node has different coverage capabilities. At this time, we lead into the knowledge of weights. Consider a set of $n$ sensor nodes with different weighting values in the plane. Let $S = {(s_{1}, ω_{1}), (s_{2}, ω_{2}), \dots, (s_{n}, ω_{n})}$ represent the collections of these nodes, and $ω_{n}$ is the weighting factor of each node. The weighted distance from any position point $q$ to node $s_{i}$ is defined as follows

d_{ω} (q, s_{i}) = \frac{d (q, s_{i})}{ω_{i}}

(3)

Based on the definition above, the plane is divided into $n$ regions through the $n$ nodes. Each region has only one node and any point within that region to this node is the closest in the sense of weighted distance. The resulting diagram is called the MW-Voronoi diagram. Regional features are mathematically expressed by equation (4)

Π_{i} = {q \in 2 R^{2} | d_{ω} (q, s_{i}) \leq d ω (q, s_{j}), j \in {1, \dots, n}, j \neq i}

(4)

Definition 2

Under any given two nodes $s_{1}$ and $s_{2}$ , the trajectory formed by the set of points $q_{m}$ whose distance ratio of the two nodes is a constant, such as $d (q_{m}, s_{1}) / d (q_{m}, s_{2}) = k$ , is called Apollonius circle shown in Figure 5.

Figure 5.

Apollonius circle.

To construct the MW-Voronoi region $Π_{i}$ , we need to find the Apollonius circle for all nodes except $s_{i}$ . In all these Apollonius circles, the smallest enclosed region containing $s_{i}$ is the MW-Voronoi region of $s_{i}$ . Figure 6 is an example of MW-Voronoi diagram.

Figure 6.

An example of MW-Voronoi diagram.

The proposed CIC-based MW-Voronoi

In the first two sections of this chapter, we introduced the CIC model and the Voronoi polygon. In the application of MWSNs, CIC model utilizes collaborative sensing of nodes to increase disk coverage area, thus forming a new heterogeneous overlay network, which we call the CIC collaborative disk. Next we will introduce the Voronoi partitioning based on the CIC model. In this section, we will discuss a novel CIC-based multiplicatively weighted Voronoi (CIC-MW-Voronoi) diagram based on the CIC model and MW-Voronoi diagram which are, respectively, described in section “CIC model” and section “Voronoi diagram and weighted Voronoi.”

Node clustering

In some applications of MWSN, sensor nodes are initially randomly deployed in the target sensing field, which will lead to uneven distribution of sensor nodes, coverage holes, and overlapping coverage. In order to form the optimal virtual node set suitable for collaborative sensing between neighboring nodes, we adopt the classic agglomerative hierarchical clustering method to re-cluster the randomly distributed sensor nodes.²⁵

There are three main steps in the process of aggregation.

Initialization. Each sensor node is considered as a cluster, and the distance between all clusters is calculated.

Iteration. Combine the two clusters with the smallest distance into a new cluster, and recalculate the distance between the new cluster and all clusters.

Termination. When the new cluster contains six sensor nodes, this cluster stops aggregation. When the distance between any clusters is greater than the communication radius $r_{c}$ , the entire aggregation process stops.

Figure 7 gives an example of aggregation in which 30 sensor nodes are clustered into 16 clusters. Each different clusters is marked with different colors and different symbols for easy observation.

Figure 7.

An example of aggregation.

As described in Deng et al.,⁹ the equilateral triangular, rectangle, and hexagonal are the most widely used polygons for sensor deployment, so in this article we only design CIC-based MW-Voronoi Diagram under the three major polygons. This means the number of sensor nodes of each virtual node set must be three, four, or six.

CIC-based MW-Voronoi diagram

After the number of sensor nodes of each virtual node set is determined, the positions of the $n$ sensor nodes in each virtual node set can be calculated by equation (5)²⁶

\frac{1}{n} \sum_{j = 1}^{n} e^{- \frac{4 r_{n}^{2}}{a^{2}} \overset{2}{\sin} \frac{π j}{n}} - 2 e^{- \frac{r_{n}^{2}}{a^{2}}} + 1 - ε^{2} = 0

(5)

where $a$ is the correlation range and $ε$ is the RMSE threshold. After the clustering is completed, according to the CIC model theory, we compare the $Φ (x)$ of the arbitrary position point with the preset threshold $ε$ , if it is less than $ε$ , the point is covered by confident information. For the formation of the CIC collaborative sensing disk, we divide the entire sensing area into countless tiny areas. The algorithm calculates the RMSE for these extremely small areas in turn. If the coverage condition is met, the area is CIC area. After the algorithm is completed, the area that satisfies the coverage of confident information is defined as a CIC collaborative sensing disk, and then, it will be called the virtual node. Virtual node weight value is defined next.

Definition 3

The maximum inner circle radius $R_{s}$ of the coverage area of the virtual node set is the weight value $ω$ .

Based on the Definitions 2 and 3, the edge of the CIC-based MW-Voronoi diagram can be uniquely determined. Figure 8 gives the division method and comparison of different MW-Voronoi region edges between nodes and virtual node set. The nodes and virtual node set in the figure are represented by different circle centers, and the maximum inner circle is represented by a dashed line. It can be seen from Figure 8

\begin{matrix} \frac{d (q_{1}, S_{1})}{d (q_{1}, S_{2})} = \frac{ω_{1}}{ω_{2}}; \frac{d (q_{2}, S_{3})}{d (q_{2}, S_{4})} = \frac{ω_{3}}{ω_{4}}; \\ \frac{d (q_{3}, S_{5})}{d (q_{3}, S_{6})} = \frac{ω_{5}}{ω_{6}}; \frac{d (q_{4}, S_{7})}{d (q_{4}, S_{8})} = \frac{ω_{7}}{ω_{8}} \end{matrix}

(6)

Figure 8.

CIC-based MW-Voronoi edges: (a) single node with three nodes, (b) single node with four nodes, (c) single node with six nodes, and (d) four nodes with six nodes.

The proposed sensor redeployment algorithms

In this section, two novel sensor redeployment algorithms namely the CIC-Minmax-Vertex and the CIC-Maxmin-Vertex are discussed based on our proposed CIC-based MW-Voronoi diagram and the methods proposed in Mahboubi et al.²³ under the SDWSN architecture. The basic process of these two algorithms consists of four stages. In the first stage, a virtual node set is constructed through node clustering. Then, each virtual node set constructs MW-Voronoi region $Π_{i}$ according to its own and surrounding node weight information. In the third stage, the algorithm will check if there are coverage holes inside the polygon. If any hole exists, the target position of the movement, the current local coverage area $β_{i}$ of polygon and the target local coverage area $β_{i}^{'}$ are calculated. Only the local coverage area increases when the sensor moves to the target position, that is, $β_{i}^{'} > β_{i}$ , the point is used as the next iteration position point. It is worth mentioning that this point is the target location of the virtual node set and the sensor nodes included in the virtual node set are simultaneously moved accordingly. Finally, all iterations stop when the entire area coverage increases less than a certain threshold or reaches a predetermined round. Termination conditions guarantee the time finiteness of the algorithm.

We denote $V_{i} = {v_{1 l}, v_{2 l}, \dots, v_{il}}$ as the vertex points of the ith MW-Voronoi region $Π_{i}$ , which is the intersection point of the MW-Voronoi boundary curve, among which, there is no region with a vertex number of one.

The CIC-Minmax-Vertex algorithm

In the research of sensor network coverage, introducing the concept of Voronoi is actually to segment the entire sensor area and research each small block independently. The basic principle of the CIC-Minmax-Vertex algorithm is that, under normal circumstances, for a uniformly covered sensor network, each sensor node should not be too far away from any vertices of the polygon. That is to say, for each node in theMW-Voronoi, we want to make the position of the node as close as possible to any one of the vertices. Therefore, the goal of the algorithm is to find a position point in the polygon for the MW-Voronoi region formed by the virtual node set, so that the distance from this position point to the farthest MW-Voronoi vertex is the smallest, and the position point is used as the target point of the virtual node set iteration. This point will be called the CIC-Minmax-Vertex centroid point, denoted by Ô_i for the ith region, $i \in n$ . The distance to the farthest vertex is expressed as ${\hat{r}}_{i}$ . Detailed steps are presented in Algorithm 1.

Algorithm 1. Procedure of CIC-Minmax-Vertex Centroid.
(01) Notations :(02) $S = {s_{1}, s_{2}, \dots, s_{n}}$ : $n$ sensors(03) $S_{v} = {s_{v 1}, s_{v 2}, \dots, s_{vm}}$ : $m$ virtual node sets(04) $V = {v_{1 l}, v_{2 l}, \dots, v_{il}}$ : $l$ vertices of region $Π_{i}$ (05)Generally $m \leq n$ (06) Main Procedure :(07)Randomly deploy n sensors in the 2D sensor field;(08)Cluster and generate $m$ virtual node sets;(09)repeat(10) Construct the MW-Voronoi polygons for all $m$ virtual node sets;(11) for $i \dot{=} 1$ to $m$ do(12) Consider the number of vertices $v_{il}$ in each region $Π_{i}$ (13) if $l$ = 0 then(14) CIC-Minmax-Vertex centroid: Case 1;(15) Enter the SubProcedure;(16) else if $l$ = 2 then(17) CIC-Minmax-Vertex centroid: Case 2;(18) Enter the SubProcedure;(19) else(20) CIC-Minmax-Vertex centroid: Case 3;(21) Enter the SubProcedure;(22) end if(23) end for(24)until Meet the termination condition.(25) SubProcedure :(26)Calculate coverage area $C_{cur}$ of the $s_{vi}$ at the current position;(27)Calculate coverage area $C_{cen}$ of the $s_{vi}$ move to the new position;(28)if $C_{cur} \leq C_{cen}$ (29) Move $s_{vi}$ to the new position;(30)else(31) $s_{vi}$ stays without movement;(32)end if

Algorithm 1. Procedure of CIC-Minmax-Vertex Centroid.

(01) Notations :(02)

S = {s_{1}, s_{2}, \dots, s_{n}}

n

sensors(03)

S_{v} = {s_{v 1}, s_{v 2}, \dots, s_{vm}}

m

virtual node sets(04)

V = {v_{1 l}, v_{2 l}, \dots, v_{il}}

l

vertices of region

Π_{i}

(05)Generally

m \leq n

(06) Main Procedure :(07)Randomly deploy n sensors in the 2D sensor field;(08)Cluster and generate

m

virtual node sets;(09)repeat(10) Construct the MW-Voronoi polygons for all

m

virtual node sets;(11) for

i \dot{=} 1

m

do(12) Consider the number of vertices

v_{il}

in each region

Π_{i}

(13) if

l

= 0 then(14) CIC-Minmax-Vertex centroid: Case 1;(15) Enter the SubProcedure;(16) else if

l

= 2 then(17) CIC-Minmax-Vertex centroid: Case 2;(18) Enter the SubProcedure;(19) else(20) CIC-Minmax-Vertex centroid: Case 3;(21) Enter the SubProcedure;(22) end if(23) end for(24)until Meet the termination condition.(25) SubProcedure :(26)Calculate coverage area

C_{cur}

of the

s_{vi}

at the current position;(27)Calculate coverage area

C_{cen}

of the

s_{vi}

move to the new position;(28)if

C_{cur} \leq C_{cen}

(29) Move

s_{vi}

to the new position;(30)else(31)

s_{vi}

stays without movement;(32)end if

Definition 4

A circle with ${\hat{r}}_{i}$ as the radius Ô_i is called the CIC-Minmax-Vertex circle, mark as $C (Ô_{i}, {\hat{r}}_{i})$ . The circle is the smallest circle whose center is inside MW-Voronoi, so that all vertices are inside or on the circle.

There are three cases regarding the position of the CIC-Minmax-Vertex circle of the MW-Voronoi.

Case 1: When the MW-Voronoi has only one boundary edge, the edge is actually a circle, then it is also the CIC-Minmax-Vertex circle of the area, the center of the circle is the CIC-Minmax-Vertex centroid.

Case 2: When MW-Voronoi has more than two edges, there must be at least two vertices on the CIC-Minmax-Vertex circle. When the circle exactly passes through two vertices, if the midpoint of the two vertices is in the region, then the point is the center of the circle. otherwise, the center of the circle is one of the intersection points of the vertical bisector connecting the vertex line segment and the boundary line of the ith MW-Voronoi region, and the one with the smallest distance to the vertices can be selected.

Case 3: When the CIC-Minmax-Vertex circle passes through more than two vertices, the Minimum encirclement that only needs to find these points is the CIC-Minmax-Vertex circle. The method is to find the center of the circle of any three vertices, and the intersection of the perpendicular and the edge of any two vertices, and the intersection of the vertical line and the line connecting any vertex, then remove the point outside the MW-Voronoi region. The point at which the maximum distance to each vertex in the remaining points is the smallest is the CIC-Minmax-Vertex centroid point.

The CIC-maxmin-vertex algorithm

The difference between the CIC-Maxmin-Vertex algorithm and the CIC-Minmax-Vertex algorithm mainly reflects how to select the optimal location for sensor nodes in the Voronoi region, so as to maximize the coverage area. The core idea of the CIC-Maxmin-Vertex algorithm is that, under normal circumstances, for a uniformly covered sensor network, each sensor node should not be too close to any one of the vertices of the polygon. In other words, for each node in the MW-Voronoi, we want to make the position of this node as far away from any of the vertices as possible. Therefore, the main goal is to find a target point in the polygon for the MW-Voronoi region formed by the virtual node set, so that the distance from this point to the nearest MW-Voronoi vertex is maximized, and this point is used as the target position of the virtual node set iteration. This point will be called the CIC-Maxmin-Vertex centroid point, denoted by ${\overset{\cdot\cdot}{O}}_{i}$ for the ith region, $i \in n$ . The distance to the nearest vertex is expressed as ${\overset{\cdot\cdot}{r}}_{i}$ . Algorithm 2 gives the detailed steps of the CIC-Maxmin-Vertex Algorithm.

Algorithm 2. Procedure of CIC-Maxmin-Vertex Centroid.
(01) Notations :(02) $S$ , $S_{v}$ , $V$ are the same meaning as those in Algorithm 1;(03) Main Procedure :(04) Randomly deploy n sensors in the 2D sensor field;(05) Cluster and generate $m$ virtual node sets;(06) repeat(07) Construct the MW-Voronoi polygons for all $m$ virtual node sets;(08) for $i \dot{=} 1$ to $m$ do(09) Consider the number of vertices $v_{il}$ in each region $Π_{i}$ (10) if $l$ = 0 then(11) CIC-Maxmin-Vertex centroid: Case a;(12) Enter the SubProcedure;(13) else if $l$ = 2 then(14) CIC-Maxmin-Vertex centroid: Case b;(15) Enter the SubProcedure;(16) else(17) CIC-Maxmin-Vertex centroid: Case c;(18) Enter the SubProcedure;(19) end if(20) end for(21) until Meet the termination condition.(22) SubProcedure :(23) Calculate coverage area $C_{cur}$ of the $s_{vi}$ at the current position;(24) Calculate coverage area $C_{cen}$ of the $s_{vi}$ move to the new position;(25) if $C_{cur} \leq C_{cen}$ (26) Move $s_{vi}$ to the new position;(27) else(28) $s_{vi}$ stays without movement;(29) end if

Algorithm 2. Procedure of CIC-Maxmin-Vertex Centroid.

(01) Notations :(02)

S

S_{v}

V

are the same meaning as those in Algorithm 1;(03) Main Procedure :(04) Randomly deploy n sensors in the 2D sensor field;(05) Cluster and generate

m

virtual node sets;(06) repeat(07) Construct the MW-Voronoi polygons for all

m

virtual node sets;(08) for

i \dot{=} 1

m

do(09) Consider the number of vertices

v_{il}

in each region

Π_{i}

(10) if

l

= 0 then(11) CIC-Maxmin-Vertex centroid: Case a;(12) Enter the SubProcedure;(13) else if

l

= 2 then(14) CIC-Maxmin-Vertex centroid: Case b;(15) Enter the SubProcedure;(16) else(17) CIC-Maxmin-Vertex centroid: Case c;(18) Enter the SubProcedure;(19) end if(20) end for(21) until Meet the termination condition.(22) SubProcedure :(23) Calculate coverage area

C_{cur}

of the

s_{vi}

at the current position;(24) Calculate coverage area

C_{cen}

of the

s_{vi}

move to the new position;(25) if

C_{cur} \leq C_{cen}

(26) Move

s_{vi}

to the new position;(27) else(28)

s_{vi}

stays without movement;(29) end if

Definition 5

A circle with ${\overset{\cdot\cdot}{r}}_{i}$ as the radius Ö_i is called the CIC-Maxmin-Vertex circle, mark as $C (Ö_{i}, {\overset{\cdot\cdot}{r}}_{i})$ . The circle is the largest circle whose center is inside MW-Voronoi, so that all vertices of the region are outside or on the circle.

Regarding the position of the CIC-Maxmin-Vertex circle, we also discuss three cases.

Case a: The first case are consistent with the above Case 1, the center of the circle is the CIC-Maxmin-Vertex centroid point.

Case b: In the second case, no matter whether the midpoint of the line connecting the two vertices is in the MW-Voronoi region, the midpoint position is no longer the optimal choice. At this time we choose the point with the largest distance to the vertex from the intersection of area edge and the vertical bisector line connecting the two vertices is the CIC-Maxmin-Vertex centroid.

Case c: Then we discuss the third case. When there are three or more vertices in the MW-Voronoi region, we assume that the CIC-Maxmin centroid point exists, there must be a case of Lemma 1 and a proof is given. Since this point is located in the MW-Voronoi region, it should be the intersection of the vertical bisector of some vertex connections, or the intersection of a vertical bisector with an edge. Generalized to multiple vertices, because any three vertices can make a triangle, so we only need to find all the edge curves, straight lines, and vertical bisector of any two vertices. Then calculate the intersection of any two lines in these line sets, remove the points outside the MW-Voronoi region, and calculate the minimum distance to each vertex for the remaining points. The point where the minimum value is the largest is the CIC-Maxmin-Vertex centroid point.

Lemma 1

The distance from the centroid position to the three vertices must be at least two equal.

Proof

Suppose that $A$ , $B$ , and $C$ are, respectively, represented as vertices in the MW-Voronoi region with only three vertices. Suppose the CIC-Maxmin-Vertex centroid point $D$ exists, the distance to the three vertices is $a$ , $b$ , $c$ , and any two are not equal, there is $a < b < c$ . Then there always exists in two minimum values $u$ , $v$ , when the point $D$ moves very small in a certain direction, making $a \to (a + u)$ and $b \to (b - v)$ . There is still $(a + u) < (b - v)$ , $c$ is changing at the same time, but the amplitude is very small. Therefore, the value is increased from $a$ to $(a + u)$ , which contradicts the assumption of point $D$ . Thus, the position must be on the vertical bisection of two vertices.

Performance evaluation

In this section, we evaluate the performance of our proposed CIC-Maxmin-Vertex algorithm and CIC-Minmax-Vertex algorithm comparing with the previously peer algorithms namely Maxmin-Vertex algorithm and Minmax-Vertex algorithm proposed in Mahboubi et al.²³ In order to prevent special situations, we set these four algorithms simultaneously in the ideal $2 D$ sensor field measuring $5 km \times 5 km$ and make them have the same initial random deployment. All sensor nodes are the same, and the communication radius is twice the coverage radius ( $r_{s} \dot{=} 0.2 km$ , $r_{c} \dot{=} 0.4 km$ ). The range a under the CIC model is $1 km$ . The termination condition is that when the coverage increment of the sensor in its MW-Voronoi polygon does not exceed 0.5% after the next movement, the maximum number of iterations of the algorithm is 30.

In the first example, 200 sensor nodes with the same sensing capability are randomly spread on a sensing field. Figures 9 and 10 show the snapshots of the nodes under the Minmax-Vertex algorithm and the CIC-Minmax-Vertex algorithm, respectively, each snapshot depicts the current coverage of sensor and the MW-Voronoi area. Figure 9(a) is a randomly deployed sensor node. The Minmax-Vertex algorithm increased its coverage from the initial value of 60.59% to 72.98% after the first round of movement. The algorithm reaches the stop condition after 9 rounds of movement, and the termination coverage rate at this time is 83.35%. Under the CIC-Minmax-Vertex algorithm, Figure 10(b) is the CIC sensing formed by the initial random deployment of sensor nodes through node clustering. At this time, the coverage increased to 88.01% and then increased to 93.30% after the first round. The algorithm The algorithm reaches the stop condition after five rounds of movement, and the coverage rate eventually stopped at 94.96%. The results show that in terms of the iteration period and final coverage ratio, the CIC-Minmax-Vertex algorithm is significantly outperforms the Minmax-Vertex algorithm.

Figure 9.

The coverage ratio of different iteration rounds under the Minmax-Vertex algorithm: (a) initial (60.59%), (b) round 1 (72.98%), (c) round 2 (77.66%), and (d) final round (83.35%).

Figure 10.

The coverage ratio of different iteration rounds under the CIC-Minmax-Vertex algorithm: (a) initial (60.59%), (b) round 1 (88.01%), (c) round 2 (93.30%), and (d) final round (94.96%).

Figure 11 demonstrates how the coverage ratio of different numbers of sensor nodes changes with the iteration period. The initial deployment of the sensors of the four sensor redeployment algorithms is the same for fair comparison, and the results obtained are average values obtained through multiple simulations of the random initial position of the sensors. We can observe that all these algorithms can quickly achieve satisfactory coverage requirements in a few rounds. However, our proposed CIC-Minmax-Vertex algorithm and CIC-Maxmin-Vertex algorithm are obviously superior to the Minmax-Vertex algorithm and the Maxmin-Vertex algorithm by the metrics of coverage ratio and the iteration rounds. Moreover, the Minmax-Vertex strategy is significantly preferable to the Maxmin-Vertex strategy.

Figure 11.

Relationship between coverage ratio and iteration rounds under different numbers of sensor nodes: (a) 150 sensor nodes, (b) 200 sensor nodes, (c) 250 sensor nodes, and (d) 300 sensor nodes.

In order to more clearly compare the performance of the proposed algorithm in terms of the number of deployed sensors, we set up the different number of sensors with $n = 100, 150, 200, 250$ , and $300$ . As can be seen from Figure 12, when the number of sensor nodes continues to increase, the performance of coverage gets better and better. The CIC-Minmax-Vertex algorithm significantly outperforms other three algorithms and demonstrates 100% coverage at 300 sensor nodes. The CIC-Maxmin-Vertex algorithms also show higher performance than the Minmax-Vertex and the Maxmin-Vertex algorithms. So, the excellent performance of our proposed algorithm also reflects the superiority of the CIC-based MW-Voronoi diagram.

Figure 12.

Relationship between coverage ratio and the number of sensor nodes.

Another important evaluation index to measure the efficiency of sensor redeployment algorithm is the number of the iteration rounds. As the real redeployment only occurred in the last round of the algorithms, so the number of iteration rounds to reach termination is used as an evaluation index of time efficiency. Figure 13 demonstrates the average number of termination rounds of sensor node motion under different algorithms. It can be seen that the curve has a process of rising to falling. The reason is that if the number of sensors is set small, then each sensor has a small probability of covering its own MW-Voronoi polygon area, sensor movement is inactive. When increasing the number of set sensors, sensor density increases and sensors’ redeployment becomes active. Until the number of sensors increases to a certain degree, the covering probability becomes larger and the algorithm can reach the termination condition in a short time. The number of iteration rounds of the proposed algorithms is obviously lower than other peer algorithms, which demonstrates the superiority of our proposed algorithms.

Figure 13.

Relationship between the number of iteration rounds and the number of sensor nodes.

Conclusion

Aiming to solve the uneven distribution of sensor nodes of the initial randomly deployment stage, a novel CIC-based the MW-Voronoi diagram is proposed to provide high-confidence coverage via sensor clustering and sensor cooperative sensing. To conduct the sensor redeployment effectively and efficiently, we propose two MW-Voronoi-based sensor collaborative redeployment algorithms, namely, the CIC-Minmax-Vertex and the CIC-Maxmin-Vertex, to improve the total coverage ration of the target sensing field under the SDWSN architecture. Simulation results show that the proposed CIC-Minmax-Vertex algorithm and the CIC-Maxmin-Vertex algorithm are significantly superior than other peer algorithms by the metrics of iteration rounds and network coverage ratio.

Footnotes

Handling Editor: Yanjiao Chen

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 National Natural Science Foundation of China under Grant 61971215, in part by the Natural Science Foundation of Hunan Province under Grant 2020JJ4526, in part by the Hunan Province Key Laboratory for Ultra-Fast Micro/Nano Technology and Advanced Laser Manufacture under Grant 2018TP1041, and in part by the Opening Project of Cooperative Innovation Center for Nuclear Fuel Cycle Technology and Equipment, University of South China under Grant 2019KFZ12.

ORCID iD

Minghua Wang

References

Duan

Zhao

, et al. Distributed algorithms to compute Walrasian equilibrium in mobile crowdsensing. IEEE Trans Ind Electron 2017; 64(5): 4048–4057.

Wang

Zhu

Yang

, et al. Offloading-assisted energy-balanced IoT edge node relocation for confident information coverage. IEEE Intern Things J 2019; 6(3): 4482–4490.

Dong

Ota

Liu

. RMER: reliable and energy efficient data collection for large-scale wireless sensor networks. IEEE Intern Things J 2016; 3(4): 511–519.

Huang

Duan

Xing

, et al. Topology control for building a large-scale and energy-efficient internet of things. IEEE Wirel Commun 2017; 24(1): 67–73.

Ishigaki

Matsumoto

Ichimiya

, et al. Development of mobile radiation monitoring system utilizing smartphone and its field tests in Fukushima. IEEE Sens J 2013; 13(10): 3520–3526.

Wang

Yang

, et al. Multi-sensor fusion based intelligent sensor relocation for health and safety monitoring in BSNs. Inform Fus 2020; 54: 61–71.

Liu

Chen

, et al. Software-defined internet of things for smart urban sensing. IEEE Commun Mag 2015; 53(9): 55–63.

Modieginyane

Letswamotse

Malekian

, et al. Software defined wireless sensor networks application opportunities for efficient network management: a survey. Comput Electr Eng 2018; 66(2): 274–287.

Deng

Jiang

Yang

, et al. Data fusion based coverage optimization in heterogeneous sensor networks: a survey. Inform Fus 2019; 52: 90–105.

10.

Aurenhammer

Klein

Lee

. Voronoi diagrams and Delaunay triangulations. Singapore: World Scientific Publishing Company, 2013.

11.

Liao

Wang

Zhang

, et al. Minimizing movement for target coverage and network connectivity in mobile sensor networks. IEEE Trans Parall Distrib Syst 2015; 26(7): 1971–1983.

12.

Mahboubi

Aghdam

Sayrafian-Pour

. Toward autonomous mobile sensor networks technology. IEEE Trans Ind Inform 2016; 12(2): 576–586.

13.

Wang

Cao

La Porta

. Movement-assisted sensor deployment. IEEE Trans Mobile Comput 2006; 5(6): 640–652.

14.

Lee

Kim

Han

, et al. Centroid-based movement assisted sensor deployment schemes in wireless sensor networks. In: Proceedings of the 2009 IEEE 70th vehicular technology conference fall, Anchorage, AK, 20–23 September 2009, pp.1–5. New York: IEEE.

15.

Fang

Song

, et al. Novel efficient deployment schemes for sensor coverage in mobile wireless sensor networks. Inform Fus 2018; 41: 25–36.

16.

Kong

Lin

Xie

, et al. Adaptive barrier coverage using software defined sensor networks. IEEE Sens J 2016; 6(20): 7364–7372.

17.

Kobo

Abu-Mahfouz

Hancke

. Fragmentation-based distributed control system for software-defined wireless sensor networks. IEEE Trans Ind Inform 2019; 15(2): 901–910.

18.

Mahboubi

Habibi

Aghdam

, et al. Distributed deployment strategies for improved coverage in a network of mobile sensors with prioritized sensing field. IEEE Trans Ind Inform 2012; 9(1): 451–461.

19.

Abbasi

Mesbahi

Mohammadpour Velni

. A new Voronoi-based blanket coverage control method for moving sensor networks. IEEE Trans Control Syst Technol 2019; 27(1): 409–417.

20.

Song

Wang

Shi

, et al. Distributed algorithms for energy-efficient even self-deployment in mobile sensor networks. IEEE Trans Mobile Comput 2014; 13(5): 1035–1047.

21.

Elwin

Freeman

Lynch

. Distributed Voronoi neighbor identification from inter-robot distances. IEEE Robot Autom Lett 2017; 2(3): 1320–1327.

22.

Chang

Zhao

, et al. SRA: a sensing radius adaptation mechanism for maximizing network lifetime in WSNs. IEEE Trans Veh Technol 2016; 65(12): 9817–9833.

23.

Mahboubi

Moezzi

Aghdam

, et al. Distributed sensor coordination algorithms for efficient coverage in a network of heterogeneous mobile sensors. IEEE Trans Autom Control 2017; 62(11): 5954–5961.

24.

Harrington

Huang

Yang

, et al. Energy-efficient map interpolation for sensor fields using Kriging. IEEE Trans Mobile Comput 2009; 8(5): 622–635.

25.

Neamatollahi

Abrishami

Naghibzadeh

, et al. Hierarchical clustering-task scheduling policy in cluster-based wireless sensor networks. IEEE Trans Ind Inform 2018; 14(5): 1876–1886.

26.

Zhu

Wang

. The optimal placement pattern for confident information coverage in wireless sensor networks. IEEE Trans Mobile Comput 2016; 15(4): 1022–1032.

Multiplicatively weighted Voronoi-based sensor collaborative redeployment in software-defined wireless sensor networks

Abstract

Keywords

Introduction

Related works

System model

CIC model

Definition 1

CIC

Voronoi diagram and weighted Voronoi

Definition 2

The proposed CIC-based MW-Voronoi

Node clustering

CIC-based MW-Voronoi diagram

Definition 3

The proposed sensor redeployment algorithms

The CIC-Minmax-Vertex algorithm

Definition 4

The CIC-maxmin-vertex algorithm

Definition 5

Lemma 1

Proof

Performance evaluation

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References