Sage Journals: Discover world-class research

Abstract

Dynamic k-coverage planning for multiple events with mobile robots is proposed in the article. In mobile sensor networks, movement with the minimum energy for multiple events detection is a challenge which is discussed in the article. The problem of multiple events coverage is divided into two subproblems, namely mobile robots’ uniform deployment and nodes’ selection. Assuming that sparse mobile robots randomly deploy in the environment, mobile robots need to uniformly deploy firstly in order to effectively communicate with static nodes and extremely cover the entire region. A weighted-sub-Voronoi-half-gravity method and a weighted-sub-Voronoi-half-incenter method are presented for mobile robots’ uniform deployment. Two algorithms guarantee mobile robots are deploying with a higher coverage ratio. Meanwhile, analog game theoretic algorithm is proposed for nodes’ selection (static node’s selection and mobile robots’ selection). Only one static node is selected to detect an event and notifies candidate mobile robots which can communicate with the selected one of the event’s occurrence. Moreover, k mobile robots are selected for event coverage. The proposed algorithm achieves k-coverage of each event with less energy consumption. Performance analysis and simulations show that the proposed algorithm achieves very good results.

Keywords

Event detection uniform deployment nodes selection mobile robots

Introduction

Multi-robot systems have been widely used in search and rescue task,^1,2 intruder detection mission,^{3

–6} and environmental monitoring mission.⁷ In these tasks, regional coverage and event detection are fundamental problems. However, each mobile robot possesses limited sensing capability and battery power.^8,9 If mobile robots deploy in a region sparsely, complete sensing coverage is a difficult task for multi-robot system.

If a region in which a point is not covered by any mobile robots exists, a coverage hole emerges. Coverage holes may affect the overall performance of multi-robot systems: decreasing the data reliability and destroying communication links. So, coverage holes’ detection and holes’ repair (namely each point in the region is possibly covered by any mobile robots) are essential problems for regional coverage.

In the problem of coverage, unbalanced energy consumption exists among mobile robots due to mobility and communication. The maximum coverage area with the minimum number of mobile robots and the minimum energy consumption is a challenge for multi-robot coverage.

Many scholars concerned about holes detection and repair. Wang et al.¹⁰ proposed three algorithms, namely VECtor-based algorithm, VORonoi-based algorithm, and Minimax algorithm, to detect coverage holes and repair them. Minimax algorithm gets the best performance compared with other two algorithms in most scenarios. But VOR and Minimax algorithms cannot repair coverage holes completely in case of a node locating close to a narrow edge in its Voronoi polygon. While VEC only moves at a low sensor density. Mahboubi et al.¹¹ proposed four movement strategies, namely maxmin-vertex strategy, minmax-edge strategy, maxmin-edge strategy, and VEDGE strategy (the combination of minimax- and maxmin-edge), to select a candidate location within its Voronoi polygon as the node’s new location to increase the coverage. Dai et al.¹² detected coverage holes and identified border nodes based on the distance between a node and the vertex or edges of its Voronoi cell. Classic Voronoi diagram represents positions of holes with vertices, while it cannot accurately describe positions and sizes of holes.

Moreover, in the problem of event detection, k-coverage is presented to guarantee the accuracy of the event that can be detected.¹³ If each event is within the sensing range of at least k mobile nodes, it is defined as k-coverage. Nodes’ selection with the minimum movement energy to prolong the network’s lifetime is a challenge for k-coverage of event.¹⁴

Many works have been proposed to detect the event and cover it. Alam et al.¹³ proposed a game theoretic model (GTM) for event coverage, and it can balance the energy consumption due to mobility and keep the traveling distance minimum. It considers the following factors including distance from an event, remaining energy, density, and the likeliness of event occurrence around it. But it cannot apply in a network with less number of mobile nodes because density has a large influence on the node’s selection algorithm, and it may select a node with larger movement energy to cover the event. Ammari and Das^15,16 proposed a pseudorandom sensor placement strategy that guarantees k-coverage of a region of interest (RoI). Meanwhile, centralized and distributed methods are proposed to move sensors toward a RoI and achieve k-coverage of RoI while minimizing the mobility energy. Alam et al.¹⁷ proposed an on-demand k-coverage method for event detection by adjusting the sensing radii of k-1 static nodes once the event is detected by at least one node. The optimal node set whose sensing radii are to be adjusted is selected based on a cost function comprising energy consumption and aggregated event detection probability. However, it needs a large number of static nodes for k-coverage. Lambrou¹⁸ proposed an uncovered region monitoring algorithm in a sensor field consisting of sparse static nodes and mobile nodes. Single mobile node moves to search two nonconnected uncovered regions with the minimum average detection delay or the maximum dynamic coverage. However, the performance of path planning strategy depends on the neighborhood size.

Our major contributions can be summarized as follows:

The problems of regional coverage and multiple events coverage with the minimum movement energy in mobile sensor networks are solved in the article.

A weighted-sub-Voronoi-half-gravity (WSVHG) algorithm and a weighted-sub-Voronoi-half-incenter (WSVHI) algorithm are proposed for the maximum coverage of the region with sparse mobile robots and they guarantee the shortest movement distance.

Nodes (including static nodes and mobile robots) selection algorithm with analog game theoretic algorithm is proposed for the selection of activated ones. Only a static node is selected as the activated one, and it depends on the remaining energy of the static node and the number of mobile robots which can communicate with the static node. k mobile robots are selected as activated nodes, and they depend on (i) the remaining energy, (ii) movement energy, and (iii) communication energy.

The remainder of the article is organized as follows. “Problem description and system models” section introduces several system models. “Mobile robots’ uniform deployment” section describes the mobile robots’ uniform deployment algorithm. “Nodes’ selection algorithm” section presents the static node’s selection algorithm and mobile robots’ selection algorithm. The fifth section presents simulations and discussions. The sixth section concludes the article.

Problem description and system models

Problem description

Mobile sensor networks exist many static nodes and sparse mobile robots for k-coverage of each event. Static nodes uniformly deploy for 1-coverage of the region. Mobile robots randomly deploy in the region for detecting events. Mobile robots can effectively moves through the field to monitor coverage and detect events.

In order to effectively communicate with static nodes and possibly cover the entire region, mobile robots need to uniformly deploy in the region (that is the problem of mobile robots’ uniform deployment). WSVHG and WSVHI are proposed for uniform deployment of mobile robots. Events occurred in the region are detected by static nodes firstly. But only one is activated to detect each event and notifies candidate mobile robots which can communicate with the activated one of the event’s occurrence, k mobile robots are selected based on analog game theoretic algorithm to move and cover the event.

Energy consumption exists in the process of sensing, communication, and movement. Therefore, we present several models for k-coverage of each event.

Voronoi diagram

Voronoi diagram divided the region into a number of polygons called Voronoi cells. Definitions of Voronoi diagram and Voronoi cell are given as follows.

Definition 1: (Voronoi cell)

Consider a node set $P : = {P_{1}, P_{2}, ..., P_{N_{m}}}$ , where N_m ≥ 2 denotes the number of points randomly deployed in the region and P_i ≠ P_j for i ≠ j, $i, j = 1, 2, ..., N_{m}$ . The Voronoi cell of a point P_i is defined as $V C (P_{i}) =$ ${P | d (P, P_{i}) < d (P, P_{j}), j \neq i, j = 1, 2, ..., N_{m}}$ , where $d (P, P_{j})$ denotes the Euclidean distance between P_j and a point P.

Definition 2: (Voronoi diagram)

The set of all Voronoi cells given by $V D (P) = {V C (P_{1}), V C (P_{2}), \dots, V C (P_{N_{m}})}$ is called the Voronoi diagram generated by P.

Each Voronoi cell contains one point and two adjacent Voronoi cells share a Voronoi edge. Each point only needs to sense its own Voronoi cell.

Minimum number of static nodes for 1-coverage

In the square region A , the position of i-th static node is $X_{i} = (x_{i}, y_{i}), i = 1, ..., N_{sta}$ , where N_sta denotes the minimum number of static nodes for 1-coverage of A . The sensing radius of each static node is r_s and the communication radius is r_c. Connectivity in communication is guaranteed if $r_{c} \geq 2 r_{s}$ .^{19
–21}

N_sta is computed based on the following description. The sensing area of static node s_i is $A_{s} = π r_{s}^{2}$ . Because of overlapping, actually sensing area of s_i is less than $π r_{s}^{2}$ . Take s_i as example, we compute the actual sensing area of s_i which is denoted by A_sta.

Assuming that the sensing disk of s_i intersects with the sensing disk of s_i+1 as shown as the shaded part in Figure 1, the area of overlapping sensing between two static nodes is computed with equation (1)

A_{overlap} = r_{s}^{2} \times (θ - sin θ)

where the distance between s_i and s_i+1 is less than r_s and θ represents the angle subtended by the chord of intersection between two sensing disks to the center of the disk.

Figure 1.

Area of overlap.

Assuming that the sensing disk of a static node intersects with another $N_{sta}^{'}$ static nodes actually, so the coverage area of s_i becomes

A_{sta} = π r_{s}^{2} - \frac{N_{sta}^{'}}{2} \times r_{s}^{2} \times (θ - sin θ)

where $N_{sta}^{'} = \frac{2 π}{θ}$ ²²

The minimum number of static nodes required for 1-coverage of region A is given by

N_{sta} = \frac{A_{A}}{A_{sta}} = \frac{A_{x} \times A_{y}}{r_{s}^{2} [π - \frac{N_{sta}^{'}}{2} (θ - sin θ)]}

where A_x denotes the length of A and A_y denotes the width of A .

Sensing model of mobile robots

N_mob mobile robots randomly deploy in region A . The sensing radius of each mobile robot is R_s ≥ r_s and the communication radius is R_c ≥ r_c. Moreover, R_c ≥ 2R_s.

Sensing models available in the literature are broadly classified into three types²³: disk sensing model, probabilistic sensing model, and directional sensing model. Disk sensing model is used in this article.

Assuming that the position of a mobile robot s is $p (x_{s}, y_{s})$ , an arbitrary point P in the two-dimensional plane is $p (x_{p}, y_{p})$ , so the probability of a mobile robot s sensing the point P gets with equation (4)

P_{r} (s, P) = {\begin{matrix} 1, & if d (s, P) \leq R_{s} \\ 0, & otherwise \end{matrix}

where d(s, P) denotes the Euclidean distance between s and P, and R_s denotes the sensing radius of a mobile robot.

Moreover, static nodes use this model to detect events.

Model of event occurrence

In wireless sensor networks, time property and spatial property are important for events.²⁴ Based on the time property (occurring at a point-in-time or a time interval) and spatial property (occurring at a certain position or a region), we describe the event model used in the article.

Definition 3: (event model)

Static event occurs in time interval [t^ON, t^OFF ] with position $e = (x_{e}, y_{e})$ , where [t^ON, t^OFF ] are the times that an event is turned on or off.

Energy model

Energy is a critical resource in a wireless sensor network and mobile robots. Energy model specifically refers to the energy consumption in the process of data transmission, data reception, sensing, and movement. In the article, static nodes and mobile robots have the same energy model of sensing and energy model of communication. Moreover, mobile robots exist energy consumption of movement, but static nodes not exist energy consumption of movement. Therefore, we take mobile robots as examples to explain the energy model.

Energy consumption of sensing

A mobile robot j with sensing radius R_s uses sensors to detect surrounding environment, and there exists energy consumption of sensing in the process. Energy consumption of sensing $E r_{s} (j)$ is defined as

E r_{s} (j) = α \times R_{s}^{α_{s}}

where parameter α_s is related to the sensing technology in use and varies in the range^2,4 in the case of sensors adopting an active sensing technology, and α stands for the loss coefficient.^17,25,26

Energy consumption of communication

In the process of communication, there exist data transmission and data reception; therefore, the energy consumption of communication of a mobile robot j, $E r_{c} (j)$ , is composed of the energy consumption of transmission $E r_{t} (j)$ and the energy consumption of reception $E r_{r} (j)$ . $E r_{c} (j)$ is defined as

E r_{c} (j) = E r_{t} (j) + E r_{r} (j)

where $E r_{t} (j)$ to transmit one bit of data is defined as

E r_{t} (j) = δ \times {(d_{j}^{c})}^{α_{t}} + c_{t}

where $d_{j}^{c}$ denotes the data transmission distance in the process of communication, δ is the loss coefficient, c_t is energy/bit needed to run the transceiver circuit, and $α_{t} \in [2, 4]$ is the path loss factor.^17,27

And $E r_{r} (j)$ to receive one bit of data is defined as

E r_{r} (j) = c_{t}

where c_t denotes energy/bit needed to run the transceiver circuit.

Energy consumption of movement

Considering a mobile robot j with traveling distance L, the energy consumption of movement is defined as

E r_{m} (j) = e_{m} \times L

where e_m is the energy cost for a mobile robot to move one unit distance.¹⁶

Degree of coverage

k (degree of coverage, DOC) is an important performance for accurate and reliable event detection in mobile sensor networks. Increasing k increases the quality of service metrics at the cost of higher network traffic, energy consumption, and deployment cost. While decreasing k would exhibit degraded accuracy and loss of robustness.¹⁷

In the article, k_i represents the DOC of a static node i, and the set of DOC in mobile sensor networks is denoted by $K = {k_{1}, k_{2}, ..., k_{N_{sta}}}$ . k_i is computed based on the number of mobile robots which can communicate with a static node. DOCs of all static nodes are computed and they compose set K. The minimum DOC among K is selected as the DOC of the system. The DOC of the system is used to determine the number of mobile robots for event detection guaranteeing less energy consumption and higher accuracy.

Mobile robots’ uniform deployment

N_mob mobile robots randomly deploy in a large square region. WSVHG and WSVHI are proposed for uniform deployment. The difference between two algorithms is the target selection of each mobile robot in each sub-Voronoi cell. Taking WSVHG as example to detail, and WSVHI is briefly described as the last part. The pseudocode of WSVHG is described in algorithm 1, where Ne_j represents the number of sub-Voronoi cell in j-th Voronoi cell. W_h1(l), W_h2(l), and W_h(l) are described as follows.

Algorithm 1.

Weighted-sub-Voronoi-half-gravity (WSVHG) algorithm

Require: N_mob mobile robots randomly deploy in the region; R_s: the sensing radius of a mobile robot; R_c: the communication radius of a mobile robot;

Ensure: Mobile robots’ uniform deployment

1: The partition of Voronoi cell

2: Based on the number of N_mob and the current position of each mobile robot, the region is divided into N_mob Voronoi cells; each Voronoi cell contains one node, and two adjacent Voronoi cells share one Voronoi edge;

3: initial j = 1;

4: repeat

5: The partition of sub-Voronoi cell

6: j-th Voronoi cell is divided into several sub-Voronoi cells which have the same number with its Voronoi edges; a sub-Voronoi cell is composed based on the mobile robot and any two adjacent Voronoi vertices;

7: initial l = 1;

8: repeat

9: The computation of movement distance weight

W_{h 1} (l)

10:

W_{h 1} (l)

represents the movement distance weight of the l-th sub-Voronoi cell in j-the Voronoi cell, and it is calculated based on Eq. (10);

11: The computation of coverage hole area weight

W_{h 2} (l)

12:

W_{h 2} (l)

represents the coverage hole area weight of the l-th sub-Voronoi cell in j-the Voronoi cell, and it is calculated based on Eq. (11);

13: The computation of coverage hole weight

W_{h} (l)

14:

W_{h} (l)

represents the coverage hole weight of the l-th sub-Voronoi cell in j-the Voronoi cell, and it is calculated based on Eq. (12);

15: until (

l = N e_{j}

)

16: The selection of target sub-Voronoi cell

17: A sub-Voronoi cell with the maximum coverage hole weight is selected as the target sub-Voronoi cell, and j-th mobile robot moves to the midpoint between the gravity of target sub-Voronoi cell and the current position of the robot;

18: until (

j = N_{m o b}

)

19: All mobile robots complete positions update and redraw Voronoi diagram till termination condition is achieved; mobile robots uniformly deploy in the region.

Movement distance weight

The movement distance weight W_h1(l) of the l-th sub-Voronoi cell is computed with equation (10)

W_{h 1} (l) = {\begin{array}{l} \frac{d_{min} - d_{l}}{d_{max} - d_{l}}, & d_{l} \leq d_{min} \\ \frac{d_{m} - d_{l}}{d_{max} - d_{l}}, & d_{min} < d_{l} \leq d_{m} \\ \frac{d_{max} - d_{l}}{d_{max} - d_{m}}, & d_{m} < d_{l} < d_{max} \\ 0, & d_{l} \geq d_{max} \end{array}

where d_l denotes the distance between a mobile robot and its target in l-th sub-Voronoi cell, d_min denotes the distance between a mobile robot and its nearest Voronoi vertex, and d_max denotes the distance between a mobile robot and its farthest Voronoi vertex. $d_{m} = (d_{min} + d_{max}) / 2$

Target of a mobile robot in l-th sub-Voronoi cell is selected based on the midpoint between the gravity of l-th sub-Voronoi cell and the current position of a mobile robot.

Coverage hole area weight

The coverage hole area weight W_h2(l) of the l-th sub-Voronoi cell is computed with equation (11)

W_{h 2} (l) = \frac{S_{S V C}}{S_{V C}}

where S_SVC represents the hole area of l-th sub-Voronoi cell and S_VC represents the hole area of a Voronoi cell. S_SVC and S_VC are calculated based on the geometric relationship between the sub-Voronoi cell/Voronoi cell and its sensing disk.

Coverage hole weight

A coverage hole weight of l-th sub-Voronoi cell for one mobile robot is defined

W_{h} (l) = μ_{1} W_{h 1} (l) + μ_{2} W_{h 2} (l)

Equation (12) is composed of two terms. The first term represents the movement distance weight of l-th sub-Voronoi cell and the second term represents the coverage hole area weight of l-th sub-Voronoi cell. μ₁, μ₂ are adjustable positive parameters and $μ_{1} + μ_{2} = 1.0$ .

In equation (10), if target of a mobile robot in l-th sub-Voronoi cell is selected based on the midpoint between the incenter of l-th sub-Voronoi cell and the current position of a mobile robot, the algorithm is defined as WSVHI algorithm.

The proposed mobile robots’ uniform deployment algorithms, WSVHG and WSVHI, not only consider the coverage hole area of each sub-Voronoi cell, but also consider the distance to its target in each sub-Voronoi cell. The coverage hole’s area of each sub-Voronoi cell is larger, the greater the chance of selected, and it can repair coverage holes perfectly and achieve the goal of mobile robots’ uniform deployment. The moving distance is larger, the smaller the chance of selected, and it can prevent the excessive moving energy consumption.

Nodes’ selection algorithm

The objective of nodes’ selection algorithm is to select one activated static node to detect an event and select k mobile robots to cover it. Analog game theoretic algorithm is proposed for nodes’ selection. We model our problem among candidate nodes as a selection weight defined based on the related parameters, enumerate all the selection weights, and finally select a node with the highest weight.

In the article, multiple static nodes may detect the same event, and only one needs to be activated to transmit event’s information and DOC.

All mobile robots which can communicate with the activated static node compose the candidate set. k mobile robots in the candidate set need to be selected to sense the event. Multiple events may occur at the same time, while one mobile robot only can detect one event.

Static node’s selection algorithm

Assuming that N_de static nodes detect an event e at the same time, their numbers are stored in set S_S in sequence. The activated node is selected based on the following weight—static node selection weight ω_s

ω_{s} (p) = λ_{1} \frac{E n_{r e m} (p)}{E n_{i n} (p)} + λ_{2} \frac{n_{m} (p)}{N_{m o b}}

where $p = 1, 2, ..., N_{d e}$ represents the p-th node which detects the event, $E n_{r e m} (p)$ and $E n_{i n} (p)$ represent the remaining energy and the initial energy of the p-th node, λ₁ and λ₂ are adjustable positive parameters, $λ_{1} + λ_{2} = 1.0$ . n_m(p) denotes the number of mobile robots which can communicate with the p-th node, and N_mob denotes the total number of mobile robots. Equation (13) is composed of two terms. First term displays the remaining energy of the p-th node, the remaining energy is larger, the greater the weight, and the greater the possibility of selected. Second term shows the communication ability of the p-th node.

Enumerating all the ω_s of N_de nodes, and one with the maximum weight is selected to be activated. If multiple nodes have equal maximum weight, the one with the greater remaining energy is to be selected. If multiple nodes have equal maximum weight and equal remaining energy, the one with the greater n_m is to be selected. In case further tie, any one of them is selected randomly.

Mobile robots’ selection algorithm

Assuming that n_mc mobile robots communicate with the activated static node, their numbers are stored in set S_m. k robots in S_m need to be selected to detect e . (Note, each robot is only allowed to cover an event at the same time. If a mobile robot has been selected to cover an event, it cannot be selected as a candidate to cover other events.) k robots are selected based on the following weight—mobile robot’s selection weight ω_m

\begin{matrix} ω_{m} (q) = ξ_{1} \frac{E r_{r e m} (q)}{E r_{i n} (q)} + ξ_{2} (1 - exp (- \frac{E r_{r e m} (q)}{E r_{m} (q)})) \\ + ξ_{3} (1 - exp (- \frac{E r_{r e m} (q)}{E r_{c} (q)})) \end{matrix}

where $q = 1, 2, ..., n_{m c}$ represents the q-th candidate robot, $ξ_{1}, ξ_{2}, ξ_{3}$ are adjustable positive parameters and $ξ_{1} + ξ_{2} + ξ_{3} = 1.0$ . $E r_{r e m} (q)$ and $E r_{i n} (q)$ represent the remaining energy and initial energy of the q-th robot. $E r_{m} (q)$ denotes the energy consumption of movement which is computed based on equation (9). $E r_{c} (q)$ denotes the communication energy consumption which is computed based on equation (6). Equation (14) is composed of three terms. First term displays the remaining energy weight. Second term displays the movement energy’s weight of the q-th robot from the current position moving to the target position in which a mobile robot detects the event. Third term displays the communication energy’s weight.

Enumerating all the ω_m of n_mc robots, and selecting k larger as activated robots to detect e .

Target position which a robot moves to detect the event is computed with equation (15) ( $x_{e} \neq x_{m}$ ),

{\begin{matrix} y_{g} - y_{e} = \frac{y_{m} - y_{e}}{x_{m} - x_{e}} (x_{g} - x_{e}) \\ R_{s}^{2} = {(x_{g} - x_{e})}^{2} + {(y_{g} - y_{e})}^{2} \end{matrix}

where $(x_{g}, y_{g})$ denotes the position of target, $(x_{m}, y_{m})$ denotes the position of mobile robot, and $(x_{e}, y_{e})$ denotes the position of event.

Data transmission

Data transmission in the process of static node’s selection and mobile robots’ selection is shown in Figure 2.

Figure 2.

Data transmission process.

N_de static nodes which detect an event at the same time transmit information in accordance with the order of S_S, the information includes the remaining energy of the static node, number of mobile robots which can communicate with the static node, position of the static node, and position of an event. Meanwhile, static nodes except the first one in S_S (because it only needs to transmit information to other nodes) exist an energy consumption of reception. Last one in S_S computes ω_s, selects the activated static node, and notifies the activated one. Thus, the static node’s selection requires N_de data transmission.

n_mc mobile robots which can communicate with the activated static node also transmit information in accordance with the order of S_m. First one in S_m receives information from the activated static node. Information transmitted between two mobile robots contains the position of an event, position of the activated static node, position of the mobile robot, and remaining energy of the mobile robot. Meanwhile, mobile robots except the first one in S_m exist an energy consumption of reception. Last one in S_m computes ω_m, selects k activated mobile robots, and notifies them. Thus, activated mobile robots’ selection requires n_mc + k data transmission.

The total number of data transmission in the selection of activated static node and in the selection of activated mobile robots is $N_{d e} + n_{m c} + k$ .

Simulations and discussions

Several simulations are carried out for illustrating the performance of the proposed algorithm using Matlab R2011a. Experimental environment is 50 m × 50 m. N_sta static nodes uniformly distribute in the environment for 1-coverage and the minimum N_sta is computed based on equation (3). Mobile robots and events randomly deploy in the environment. In order to completely detect events, we hope the candidate set S_m larger, so we assume that the communication radius of a static node is equal to the communication radius of a mobile robot, that is, $r_{c} = R_{c}$ . All parameters used in the article are listed in Table 1.

Table 1.

The list of parameters.

Parameter	N _sta	θ	${N ′}_{sta}$	α	α_s	δ	α_t	c_t	Data packet size
Value	126	$\frac{π}{3}$	6	1P J/m³	3	10 PJ/bit/m³	3	50 nJ/bit	500
Parameter	e_m	Initial energy of static node	Initial energy of mobile robot	$\frac{μ_{1}}{λ_{1}}$	$\frac{μ_{2}}{λ_{2}}$	ξ ₁	ξ ₂	ξ ₃
Value	0.8 J/ m	2 J	50 J	0.7	0.3	0.2	0.6	0.2

In the simulation, coverage efficiency reflects the degree of redundancy of networks. Coverage efficiency P_CE is equal to the ratio between the sensing area in the network and the sum of all sensing disks (equation (16)).

P_{C E} = \frac{\sum_{j = 1}^{N_{m}} S_{S} (j)}{N_{m} π R_{s}^{2}}

where S_S(j) denotes the sensing area of the j-th node and N_m denotes the number of mobile robots randomly deployed in the region.

Coverage ratio reflects the DOC of networks. Coverage ratio P_CR is equal to the ratio between the sensing area in the network and the area of region (equation (17))

P_{C R} = \frac{\sum_{j = 1}^{N_{m}} S_{S} (j)}{S_{A}}

where S_A denotes the area of region A .

Algorithm validation

The simulation is used to validate the effectiveness of the proposed regional coverage and k-coverage of events algorithm.

In the simulation, 25 mobile robots with R_s = 5 m and R_c = 17 m randomly deploy in the environment; 126 static nodes with r_s = 3 m uniformly distribute in the environment. The initial Voronoi diagram of mobile robots is shown in Figure 3(a), the average coverage ratio is 50.18%, and the average coverage efficiency is 63.89%. Voronoi diagram is built based on the number of mobile robots.

Figure 3.

Mobile robots are uniform distribution: Each mobile robot is expressed by ‘*’ and each static node is expressed by ‘o’. (a) Initial Voronoi diagram of mobile robots. (b) Final Voronoi diagram with WSVHI. (c) Final Voronoi diagram with WSVHG. WSVHI: weighted-sub-Voronoi-half-incenter; WSVHG: weighted-sub-Voronoi-half-gravity.

In order to maximize the coverage region, WSVHG and WSVHI are used for holes detection and repair. The final Voronoi diagram of mobile robots with WSVHI is shown in Figure 3(b). The final coverage ratio increases to 71.90% and the final coverage efficiency increases to 91.55%. The final Voronoi diagram of mobile robots with WSVHG is shown in Figure 3(c). The final coverage ratio increases to 72.84% and the final coverage efficiency increases to 92.74%. From figures, it is to be noted that mobile robots deploy more evenly in the final Voronoi diagram than in the initial Voronoi diagram.

In order to validate the proposed nodes’ selection algorithm (a static node’s selection and k mobile robots’ selection), we assume that k is provided in advance. When k changes, validating that the proposed algorithm can successfully achieve k-coverage of events.

Two events occur in the region at the same time, and the initial configuration is shown in Figure 4(a). Event 1 (position is (2.6 m, 4.5 m)) is sensed by nearly three static nodes (the numbers are 1, 11, 12, and position are (2.6 m, 1.5 m), (0 m, 6 m), and (5.2 m, 6 m), respectively), but only one is activated to transmit information. Based on equation (13) to compute weight values of three nodes are 0.736, 0.736, and 0.76, respectively. So node 12 is activated to sense event. Event 2 is sensed by one static node and it is activated to transmit information.

Assuming k = 2. For event 1, five candidate robots can communicate with node 12. Based on equation (14), we can compute weight values of five candidate robots and two robots are selected to cover the event finally. Moreover, other two robots are selected with the same algorithm to cover event 2. Figure 4(b) shows event coverage’s trajectories of activated robots. Each robot moves till detecting the event.

Assuming k = 3, k = 4, and k = 5, event coverage’s trajectories of activated robots are shown in Figure 4(c), (d), and (e), respectively.

Figure 4.

Algorithm validation: each static node is denoted by ‘o’, each mobile robot is denoted by ‘♦’, event 1 is denoted by ‘▴’, event 2 is denoted by ‘★’, ‘*’ denotes trajectories of each mobile robot, and each circle represents the sensing disk of each node. (a) Initial configuration. (b) Event coverage’s trajectories when k = 2. (c) Event coverage’s trajectories when k = 3. (d) Event coverage’s trajectories when k = 4. (e) Event coverage’s trajectories when k = 5.

But if based on OVSC (on-demand variable sensing k-coverage)¹⁷ to select static node, any of them (nodes 1, 11, 12) can be selected randomly under the circumstances because they have the equal strongest signal and the same remaining energy. Assuming that node 1 is selected to be activated, there only have three robots within its communication radius. Selecting mobile robots for 4-coverage and 5-coverage of an event based on OVSC cannot be achieved (only have three robots within the communication radius of node 1). While the proposed algorithm can achieve it, because the selection of activated static node is related with the number of mobile robots which can communicate with each node. So, node 12 is activated to sense event 1 with the proposed algorithm. The proposed algorithm has better performance than OVSC.¹⁷

It can be noted from several figures that WSVHG and WSVHI can extremely cover the region and analog game theoretic algorithm can successfully select the optimal static node to transmit information and k mobile robots to cover each event.

Regional coverage algorithm comparison

The simulation compares the proposed WSVHG and WSVHI algorithm, which are used for regional coverage with VOR and Maxmin-edge in the previous researches.

In the simulation, 10 mobile robots with R_s = 6 m and R_c = 17 m are randomly deployed in the environment. The algorithm is set to terminate when 15 rounds are carried out in each simulation. The maximum coverage ratio is $P_{M C R} = (π R_{s}^{2} \times N_{m o b}) / 50 \times 50 = 45.24 %$ .

It is to be noted that all results presented in this simulation are the average values obtained by performing 10 simulations with random initial locations for mobile robots. Figure 5 shows several results of the comparison. In each round, it is averaged with the coverage ratio/efficiency of 10 simulations, and the average value is average coverage ratio/efficiency.

Figure 5.

The proposed algorithm comparison with existing algorithms. (a) Average coverage ratio comparison. (b) Average coverage efficiency comparison. (c) Average movement distance comparison.

Figure 5(a) and (b) shows the average coverage ratio and average coverage efficiency in each round with different algorithms. With the increment of round, the performance of mobile networks becomes better. Moreover, the average coverage ratio/efficiency with WSVHG and WSVHI is much higher than with VOR and Maxmin-edge. It is to be noted that WSVHG and WSVHI have better coverage performance.

Figure 5(c) shows the average movement distance for all mobile robots in each round with different algorithms. The smaller of the average movement distance, the less of the movement energy. From the figure, it is to be noted that the average movement distance with WSVHG and WSVHI is much smaller than with VOR, but larger than with Maxmin-edge. That is, movement energy with WSVHG and WSVHI is much smaller than with VOR. However, movement energy with WSVHG and WSVHI is larger than Maxmin-edge. How to detect the region with the maximum coverage and the minimum movement energy will be the future work.

Moreover, values of all kinds of performance are shown in Table 2, which intuitively and quantitatively describes the performance with different algorithms. WSVHG and WSVHI have higher coverage efficiency and coverage ratio than VOR and Maxmin-edge and have smaller movement distance than VOR.

Table 2.

Performance comparison with different algorithms.

	Maximum efficiency (%)	Maximum ratio (%)	Average movement distance (m)
VOR	78.61	35.56	110.1787
Maxmin-edge	95.14	43.04	16.3844
WSVHG	98.08	44.37	28.5823
WSVHI	97.98	44.33	23.9971

WSVHG: weighted-sub-Voronoi-half-gravity; WSVHI: weighted-sub-Voronoi-half-incenter. Italic values used to highlight the advantages of the WSVHG and WSVHI.

With the above comparison, it can be observed that the proposed regional coverage algorithms with WSVHG and WSVHI have higher coverage ratio and coverage efficiency compared with other existing algorithms. Meanwhile, the proposed algorithms can maximize the coverage of mobile networks and maximize the utilization of each mobile robots.

Event coverage algorithm comparison

The simulation compares the proposed analog game theoretic algorithm with GTM proposed in Alam et al.¹³ for multiple events coverage. Three events randomly deploy in the region as shown in Figure 6.

Figure 6.

Initial configuration: each event is expressed by ‘★’, each static node is denoted by ‘o’, and each mobile robot is denoted by ‘♦’.

Different number of mobile robots

In the simulation, the number of mobile robots varies from 20 to 31, the sensing radius is R_s = 5 m, and the communication radius is R_c = 17 m. K = 2.

The total remaining energy and the total energy consumption of all mobile robots in each scenario are computed and results are shown in Figure 7.

Figure 7.

Results with different number of mobile robots. (a) Total remaining energy of all mobile robots. (b) Total energy consumption of all mobile robots.

In Alam et al.,¹³ density around a mobile node’s current location has a great influence on the node’s selection, so it may select a node which has a higher density, but it has larger movement energy to cover events. Nevertheless, our proposed analog game theoretic algorithm for event coverage mainly depends on the movement energy, remaining energy, and communication energy simultaneously.

From Figure 7(a) and (b), it can be observed that the total remaining energy of all mobile robots in each scenario with the proposed algorithm is much more than the remaining energy with the algorithm in Alam et al.,¹³ and the total energy consumption of all mobile robots in each scenario with the proposed algorithm is much less than the energy consumption with the algorithm in Alam et al.¹³

The proposed algorithm achieves k-coverage of each event with the minimizing energy consumption.

Different communication radii

In the simulation, communication radius of each mobile robot varies from 15 to 30 m. The number of mobile robots is 23 and its sensing radius is R_s = 5 m. The sensing radius of a static node is r_s = 3 m.

Because the required DOC (k) is determined based on the number of mobile robots which can communicate with a static node, so k is varied with the change of the communication radius.

The total remaining energy and the total energy consumption of all mobile robots and k in each scenario are computed and results are shown in Figure 8. Figure 8(a) illustrates the total remaining energy of all mobile robots in the process of event coverage with different communication radii, Figure 8(b) illustrates the total energy consumption of all mobile robots with different radii, and Figure 8(c) shows the DOC with different communication radii.

Figure 8.

Results with different communication radii. (a) Total remaining energy of all mobile robots. (b) Total energy consumption of all mobile robots. (c) DOC variation. DOC: degree of coverage.

From figures, it is to be noted that the increment of the communication radius will lead to the increment of k and the increment of energy consumption. We note that the total remaining energy of all mobile robots in each scenario with the proposed algorithm is much more than with the algorithm in Alam et al.,¹³ and the total energy consumption of all mobile robots with the proposed algorithm is much less than with the algorithm in Alam et al.¹³

From the above comparisons, it can be observed that the proposed algorithm effectively achieves k-coverage planning of multiple events with the minimum energy consumption.

Conclusion

The article studies the k-coverage planning of multiple events using a wireless sensor network and mobile robots. Regional coverage and event detection are main subproblems. WSVHG and WSVHI are proposed for regional coverage with the maximum coverage ratio/efficiency and the minimum moving distance. Static nodes uniformly distribute in the region for 1-coverage. Multiple static nodes may detect an event, but only one is activated and used to notify candidate mobile robots. Candidate mobile robots are within the communication radius of the activated node. Analog game theoretic algorithm is used for the selection of k mobile robots which cover one event. One mobile robot only detects one event. Simulations compared with other existing algorithms show that the proposed algorithm can cover the region with the maximum coverage ratio/efficiency and achieve k-coverage of events with less energy consumption.

Footnotes

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 High-Tech Research and Development Program 863, China (2015AA042307), National Natural Science Foundation, China (61601256), Shandong Provincial Scientific and Technological Development Foundation, China (2014GGX103038), Shandong Provincial Independent Innovation and Achievement Transformation Special Foundation, China (2015ZDXX0101E01), the Fundamental Research Funds of Shandong University, China (2015JC027), and the Fundamental Research Funds of Qilu University of Technology (0412048472).

References

Berger

. An innovative multi-agent search-and-rescue path planning approach. Comput Oper Res 2015; 53: 24–31.

Khan

Chan

Khan

. Optimized dynamic task allocation and priority assignments in an immunized autonomous multi-robot search and rescue operation. Sci Technol 2012; 15(2): 129–145.

Xiao

Liang

. Bio-inspired group modeling and analysis for intruder detection in mobile sensor/robotic networks. IEEE Trans Cybern 2015; 45(1): 103–115.

Howard

Parker

LE,

Sukhatme

. Experiments with a large heterogeneous mobile robot team: exploration, mapping, deployment and detection. Int J Robot Res 2006; 25(5–6): 431–447.

Parker

. Intruder detection using a wireless sensor network with an intelligent mobile robot response. In: IEEE southeastcon, Huntsville, AL, 3–6 April 2008, pp. 37–42. IEEE.

Parker

. Detecting and monitoring time-related abnormal events using a wireless sensor network and mobile robot. In: IEEE/RSJ international conference on intelligent robots and systems, Nice, France, 22–26 September 2008, pp. 3292–3298. IEEE.

Jadaliha

Choi

. Environmental monitoring using autonomous aquatic robots: sampling algorithms and experiments. IEEE Trans Control Syst Technol, 2013; 21(3): 899–905.

Kerman

Jiang

Blumberg

. Event detection challenges, methods, and applications in natural and artificial systems. In: Proceeding of the international command and control research and technology symposium, Washington, DC, 15–17 June 2009, pp. 1–19. Lockheed Martin MS2.

Wang

Sun

. Node placement for long bounded belt complete 2-coverage in wireless sensor networks. Math Probl Eng 2015; 57: 1–14.

10.

Wang

Cao

La Porta

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

11.

Mahboubi

Moezzi

Aghdam

. Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors. IEEE Trans Ind Inf 2014; 10(1): 163–174.

12.

Dai

Chen

Zhou

. Coverage hole detection algorithm based on Voronoi diagram in wireless sensor network. J Comput Appl 2015; 35(3): 620–623.

13.

Alam

Kamruzzaman

Karmakar

. Dynamic event coverage in hybrid wireless sensor networks. In: IEEE international symposium on network computing and applications, Cambridge, MA, 25–27 August 2011, pp. 348–353. IEEE.

14.

Nasridinov

Ihm

Jeong

. Event detection in wireless sensor networks: survey and challenges. In: Mobile, ubiquitous, and intelligent computing, Gwangju, Korea, 4–6 September 2013, pp. 585–590. Berlin Heidelberg: Springer-Verlag.

15.

Ammari

Das

. Mission-oriented k-coverage in mobile wireless sensor networks. In: International conference on distributed computing and networking, Kolkata, India, 3–6, January 2010, pp. 92–103. Berlin Heidelberg: Springer-Verlag.

16.

Ammari

. On the problem of k-coverage in mission-oriented mobile wireless sensor networks. Comput Networks 2012; 56: 1935–1950.

17.

Alam

Kamruzzaman

Karmakar

. Dynamic adjustment of sensing range for event coverage in wireless sensor networks. J Netw Comput Appl 2014; 46(0): 139–153.

18.

Lambrou

. Optimized cooperative dynamic coverage in mixed sensor networks. ACM Trans Sens Netw 2015; 11(3): 46.

19.

Xing

Wang

Zhang

. Integrated coverage and connectivity configuration for energy conservation in sensor networks. ACM Trans Sen Netw 2005; 1(1): 36–72.

20.

Wang

Xing

Zhang

. Integrated coverage and connectivity configuration in wireless sensor networks. In: Proceedings of the international conference on embedded networked sensor systems, Los Angeles, California, 5–7 November 2003, pp. 28–39. ACM Digital Library.

21.

Honghai

Hou

. Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc Sens Wireless Netw 2005; 1(1–2): 89–124.

22.

Zaidi

Hafeez

Khayam

. On minimum cost coverage in wireless sensor networks. In: Annual conference on information sciences and systems, Baltimore, MD, 18–20 March 2009, pp. 213–218. IEEE.

23.

Gaojun

. Evaluating and improving coverage performance for wireless sensor networks. PhD dissertation, National University of Defense Technology, CA, USA, 2009.

24.

Wei

. Research on complex event detection in wireless sensor networks. Master’s thesis, Harbin Institute of Technology, China, 2012.

25.

Pattem

Poduri

Krishnamachari

. Energy-quality trade-offs for target tracking in wireless sensor networks. In: Proceedings of the 2nd international conference on information processing in sensor networks, Palo Alto, CA, 22–23 April 2003, pp. 32–46. Berlin Heidelberg: Springer-Verlag.

26.

Zhou

Das

SR,

Gupta

. Variable radii connected sensor cover in sensor networks. ACM Trans Sens Netw 2009; 5(1): 8.

27.

Azad

Kamruzzaman

. Energy-balanced transmission policies for wireless sensor networks. IEEE Trans Mobile Comput 2011; 10(7): 927–940.

Dynamic k -coverage planning for multiple events with mobile robots

Abstract

Keywords

Introduction

Problem description and system models

Problem description

Voronoi diagram

Definition 1: (Voronoi cell)

Definition 2: (Voronoi diagram)

Minimum number of static nodes for 1-coverage

Sensing model of mobile robots

Model of event occurrence

Definition 3: (event model)

Energy model

Energy consumption of sensing

Energy consumption of communication

Energy consumption of movement

Degree of coverage

Mobile robots’ uniform deployment

Movement distance weight

Coverage hole area weight

Coverage hole weight

Nodes’ selection algorithm

Static node’s selection algorithm

Mobile robots’ selection algorithm

Data transmission

Simulations and discussions

Algorithm validation

Regional coverage algorithm comparison

Event coverage algorithm comparison

Different number of mobile robots

Different communication radii

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References