An Optimized Strategy Coverage Control Algorithm for WSN

Abstract

The problem of using lesser wireless sensor network nodes to achieve coverage and connection of certain areas under given coverage conditions is a priority and hotspot issue of WSN. For this reason, in this paper, an optimized strategy coverage control (OSCC) algorithm is proposed. First of all, a relation mapping model of sensor nodes and target nodes is established by OSCC which is based on geometric figure and related theories, probability theory, converge property, and so forth to complete effective reasoning and calculate certain network models. Secondly, OSCC makes efficient analysis of the calculating results figure out the least number of sensor nodes to cover specific monitoring area. Thirdly, OSCC picks out the optimal routing solution while conducting combinatorial optimization of routing path using ant colony optimization (ACO) algorithm, thus reducing the energy spending of whole network. In the end, this paper verifies OSCC algorithm by simulation experiment and proves it can use least sensor nodes to effectively cover target area. Also, OSCC helps greatly reduce network energy consuming, minimize network resources layout costs, and enhance network life cycle, simultaneously.

1. Introduction

Wireless sensor network (WSN) is a wireless self-organization network which consists of large number of cheap sensor nodes. It is a system having the capabilities of calculating, perceiving, and communicating which can be widely applied in national defense monitoring, environment detecting, mine wrecking, medicine, traffic realms, and so forth. The coverage problem, the connectivity problem among nodes or between nodes and station, and the energy consuming problem of nodes are all hotspot issues of WSN [1–4]. The coverage and connectivity problem not only directly affects the working of network, but also determines network energy consuming, network life cycle length, and network quality of service.

The coverage problem and the connectivity problem are fundamental questions in WSN. There are two ways of deploying sensor nodes: definite deployment and random deployment. Definite deployment concentrates on optimal deployment strategies of 2-dimensional and 3-dimensional space which satisfies different coverage demand and connectivity demand by handwork. However, while deploying large numbers of sensor nodes or deployment area is not appropriate for handwork, random deployment is adopted. By the way, most applications do not ask for full cover of sensor network. Instead, keeping sensor nodes cover certain rate of detected area to complete specific work is enough. The coverage problem and connectivity problem are important issues for WSN for they reflect the network state of detected area. The coverage control of WSN for specific application helps master node energy consuming improve quality of service in perceiving and extend overall life cycle. However, it will also bring problems such as increase in the cost of network transmission, management, storage, and computing. Also, network life cycle holds a critical part when coverage rate and connectivity rate are satisfied. Thus, how to meet certain coverage condition using least sensor nodes to complete coverage and connectivity of specific area while holding nodes energy consuming is a challenging project. Above all, this paper is organized as follows. (1)

Related literatures are studied and different algorithms are concluded to find their advantages and disadvantages in applications. This paper puts forward an improved algorithm to make up the insufficiency of algorithms studied.

(2)

A probabilistic model of WSN is established, giving out the function between nodes and their detected area and the relation of different parameters by geometrical theory. Though effectively reasoning and verifying of solved function with mathematics method, details of reasoning and verifying process are given to make sure the least nodes and most coverage of specific area.

(3)

While making sure of the coverage of detected area, this paper adopts ant colony optimization of artificial intelligence and virtual force between nodes. Though vector theory to calculate node moving path and direction, and finally making sensor nodes to optimal location.

(4)

The proof of routing path convergence speed under ant colony optimization is given which enhances the coverage of WSN. Simulation result shows that OSCC fulfill high-speed and effective and stable coverage of sensor network.

2. Related Works

In recent years, theories and solutions about the coverage problem and the connectivity problem in WSN have been proposed. Tamboli and Younis [5] suggested a method about the sensor coverage and connectivity restoration in removable sensor networks where the main idea is integrating the coverage problem and the connectivity problem. The Coverage C³R (conscious connectivity restoration) algorithm is used to recover one or more invalid nodes from neighbors', each neighbor node is relocated and invalid nodes are replaced to its initial position; thus the connectivity is recovered and the target nodes are detected at the initial position within the coverage region. Sheu and Lin [6] developed a CPP algorithm which made an improvement of the CCAP algorithm. The CPP algorithm employs working nodes as less as possible while keeping the coverage area. The centrally controlled approach adopted by CPP algorithm results in restricted scale of WSN. What is more, little work is done on three-dimensional sensor networks introducing probability coverage model. However, most applied WSN are located in 3-dimensional sensor networks, thus making it more precise for simulation. De Mello et al. [7] introduced an algorithm focusing on the issues of coverage and redundancy, which is based on the GA (genetic algorithm) to optimize the coverage and reduce energy consuming without losing coverage. Habib and Safar [8] established a model that lattices the coverage area where each lattice has a sensor located in the position of the lattices. According to the row and column position in the matrix, an optimal model on the consumption and the coverage rate of WSN is given. Finally, genetic algorithm (GA) is used to figure out the best solution. A virtual power algorithm put forward by [9] is frequently used in dynamic deployment of sensor nodes. The receiving information strength of nodes is regarded as a virtual power within sensor nodes. The process of dynamic deployment will not be finished until the balance of the virtual power each node finished. An algorithm based on the virtual power in combination with particle swarm optimization (PSO) [10] is applied in controlling coverage regions while ignoring the minimum consumption of nodes' energy. The maximum coverage, the minimum communication costs, and the energy depleted in nodes' moving were all considered by Wang et al. [11]. However, the searching space of a PSO would be in exponential growth with the increase of dimensions of optimize vectors, thus making computing time complexity be a bottleneck in the process of networks' optimization. All the algorithms mentioned above are able to solve the problem of coverage and connectivity to a large extent, but the process is complicated. Moreover, with the increase of nodes and change of coverage regions, the complexity of algorithms will be increased and the computing efficiently will be decreased. Tian et al. [12] introduced an algorithm based on simulate anneal arithmetic (SAA) to minimize the distance mistake. Each lattice has a sensor in initial. If node configuration cost does not reach the threshold given before, then loop the procedure as follows. First of all, delete a sensor node randomly, and make an evaluation of replacement cost. If replacement cost fails, move this node to another random position and then reevaluate. A coverage and connectivity method to cluster topology (CCC) in WSN algorithm was put forward by Wang et al. [13] that an optimal cluster should have 15 nodes and if the clusters make an equilateral triangle, the efficiency of coverage and connectivity is the best. According to the ideas mentioned, this paper puts forward a coverage algorithm using the linear relationship on topology control to establish a probabilistic model of WSN. Function relation about perception radius and monitoring regions is given though the path and direction of a moving node can be figured out by vector theory and compute an optimal solution by ACO. OSCC supports data's transmission after many-hop route. Finally, simulation results show that OSCC not only reduces sensor nodes energy consuming, but also improves the coverage with less nodes. What is more, interference is reduced effectively, the quality of WSN service is improved, and the life cycle of the network is increased.

3. Definition of the Problem and the Network Model

3.1. Definition of the Problem

Coverage control is a key topic in the research of wireless sensor network which directly affects the quality of the WSN coverage services. In this paper, the main idea is to build a WSN model through functions vector relationship with sensors movement and nodes final location. In the model, all pheromone on the path of nodes movements will be updated using ACO which will make dynamic balance within all sensor nodes.

The research on coverage and the connectivity discussed in this paper is based on regional local positioning algorithm and equipped with the following basic assumptions.

Hypothesis 1.

Both coverage radius and communication radius of each node are disc-shaped.

Hypothesis 2.

The sensor nodes can get its own location information through localization algorithms, such as RSSI locating algorithm and Euclidean locating algorithm.

Hypothesis 3.

Identification of each sensor node is unique.

Hypothesis 4.

The perception range of each sensor node is far less than the entire network coverage area, and all nodes are heterogeneous and independent and have the same initial energy.

Hypothesis 5.

While moving, the sensor has enough energy to complete the required distance.

Definition 1.

Given target set $T = {t_{1}, t_{2}, t_{3}, \dots, t_{k}}$ and sensor node set $V = {v_{1}, v_{2}, v_{3}, \dots, v_{n}}$ , in certain time slot, if all nodes in T are covered by at least one node in V, then it is called full coverage of target set T.

Definition 2.

Suppose there are nodes $s_{i}$ and $s_{j}$ , whose target monitoring regions are $C_{i}$ and $C_{j}$ . If $C_{i} \cap C_{j} \neq \emptyset$ , then nodes $s_{i}$ and $s_{j}$ are coverage related. Let T be the set of m nodes which are randomly distributed in the target area; E is the edge set of network graph, which represents set of position relationship of $e_{i j} = 1$ , where $e_{i j}$ indicates position relationship of node $S_{i}$ and target node $t_{j}$ , when and only when the Euler distance between target node $t_{j}$ and sensor node $S_{i}$ is less than or equal to the sensing radius r, $e_{i} = 1$ ; otherwise $e_{i} = 0$ . $W = {w_{1}, w_{2}, \dots, w_{n}}$ is the initial energy set of the sensor nodes, and w follows $W ~ N (u, σ^{2})$ normal distribution, $w_{i}$ represents the initial energy of sensor nodes $s_{i}$ , and $w_{i}$ is also the maximum energy during its working.

Definition 3.

In the monitoring area, each node is at least covered by K sensor nodes at the same time; then we called it the K-degree coverage, namely, $A_{k} \in ⋂_{i = c}^{c + k} A s_{i} π$ , where $1 \leq c \leq n$ .

3.2. The Establishment of the Network Model

In a square monitoring area, N sensor nodes are randomly deployed. Eight were chosen as center nodes arbitrarily at the initial time. Then, divide the square into eight different areas whose intersection point is the center of the square based on the eight center nodes. Suppose there is a sensor named S and a hexagon whose center is S. Now arbitrarily choose four points from the hexagon's vertexes randomly and assume they are cluster head nodes; thus the associated attributes formed between each central node and cluster head node is $f = {(i, j) | f i : (S j), i \in [1,8], j \in [1,4]}$ . Considering central node 1 in area $f 1$ , we know that node 1 is in the lower half area of midperpendiculars between $S 3$ and $S 4$ through the perception radius of $S j$ , so the central node 1 is closer to $S 4$ , with $S 3$ following. As each cluster head node has the same energy from initial state, its perception radius and communication radius are the same. Similarly, node 1 is on the right of the midperpendiculars between $S 1$ and $S 2$ and closer to $S 2$ . Then it can be proved that perception capacity of $S 2$ is greater than $S 1$ from geometrical knowledge. With the same reason, we know that the perception of $S 3$ is stronger than $S 2$ ; that is, the associated attribute of node 1 is as follows: $f 1 : (S 4, S 3, S 2, S 1)$ . Similar considerations apply to all other nodes' associated attributes shown in Figure 1.

Figure 1

Schematic for associated attribute between cluster head nodes and center node.

3.3. Determination of the Relationship Vector

Definition 4.

The mobile node i in the position $x_{i}$ , another node j in the other position $x_{j}$ , the repulsive force from node j to node i are defined as follows:

\begin{matrix} F_{exc} = {\begin{cases} k (\frac{1}{r} - \frac{1}{d (i, j)}) (\frac{x_{i} - x_{j}}{d {(i, j)}^{2}}) & d (i, j) \leq r \\ 0 & d (i, j) > r, \end{cases} \end{matrix}

(1)

where

d (i, j)

is the Euclidean distance between sensor node i and sensor node j;

F_{exc}

is the repulsive force between sensor node i and sensor node j, also known as the exclusive power; r is the perception radius of any sensor node.

Similarly, the attraction between node i and node j is defined as

\begin{matrix} F_{att} = {\begin{cases} k \frac{1}{d {(i, j)}^{2}} (\frac{x_{i} - x_{j}}{d (i, j)}) & d (i, j) > 2 r \\ 0 & d (i, j) \leq 2 r . \end{cases} \end{matrix}

(2)

In order to make repulsion and attraction not too big or not too small, we introduced the proportionality constant coefficients k, and its purpose is to adjust the range of repulsive force and attractive force. The repulsive force and attractive force, respectively, are

\begin{matrix} F = {\begin{cases} F_{exc} = \sum_{j \in Ω} F_{c 1} (i, j) \\ F_{att} = \sum_{j \in Ω} F_{c 2} (i, j), \end{cases} \end{matrix}

(3)

where

F_{c 1}

is the repulsive force acting on the node

S_{i}

, and

F_{c 2}

is the attraction acting

S_{i}

. For the boundedness of coverage area, repulsive and attractive forces can also be applied to other models for mobile nodes on the boundary of target area. The position

x_{i}

is located in the vertical projection of the point i to its nearest distance from the boundary line of the target region. Considering the random disturbance force between nodes, the resultant force in a node is available:

\begin{matrix} F_{i} = \sum (ξ_{1} F_{exc} + ξ_{2} F_{att} + ξ_{3} F_{bor} + ξ_{4} F_{wan}), \end{matrix}

(4)

wherein

F_{bor}

is repulsive force from the boundary of the target area on nodes,

F_{wan}

is a random disturbance force between nodes, and ξ is the force control parameters. The motion equation of the mobile node i at time t can be defined as

v^{′′} (x) = (F_{i} - μ x_{i}^{'} / m)

, where μ is proportional damping factor and m is the node's virtual mass.

Mobile node is defined by the virtual force and vector relationship. Take Figure 1 for example, at the initial moment, the deployment of a sensor node is a random shape and its location is random. Virtual force exists between any two nodes, and each sensor node is looking for a stable state of equilibrium as for the regular hexagon which is the vertex positions of hexagon. At the initial moment, the direction of virtual force formed by six vertices of the hexagon centered on node S is transferred out in the form of news broadcast to look for its six neighboring nodes. Assuming that sensor node $S_{i}$ is a point within the regular hexagon, receiving S message to lower right direction and receiving the message $S 3$ to lower left, as shown in Figure 1, Euclidean distance can be obtained between S and $S_{i}$ by the Euler's formula (2), where the direction is $\overset{⃑}{D_{s s_{i}}}$ and the angle θ is the inner product of $\overset{⃑}{D_{s s 3}}$ and $\overset{⃑}{D_{s s_{i}}}$ , namely,

\begin{matrix} θ = arccos \frac{| \overset{⃑}{D_{s s 3}} \cdot \overset{⃑}{D_{s s_{i}}} |}{| \overset{⃑}{D_{s s 3}} | | \overset{⃑}{D_{s s_{i}}} |}, \\ d_{s 3 s_{i}} = {(d_{s s_{i}}^{2} + r^{2} - 2 d_{s s_{i}} r \cos θ)}^{1 / 2} . \end{matrix}

(5)

β can be obtained in the same way; substituting formula (5) into formulas (1) and (3), repulsive force size and direction of sensor node $S_{i}$ can be obtained, that is, the $S_{i}$ vector relation

\begin{array}{l} F_{exc} = k^{2} (\frac{1}{r} - \frac{1}{d_{s s_{i}}}) (\frac{x_{s 3} - x_{s i}}{d_{s s_{i}}^{2}}) \\ \cdot (\frac{1}{r} - \frac{1}{d_{s 3 s_{i}}}) (\frac{x_{s 3}}{d_{s 3 s_{i}}^{2}}) \cdot \cos (θ + β) . \end{array}

(6)

The actual process is that six sensors chosen by sensor node S in sleep state turn into active state following indicator of censor node S. If six neighbor nodes are independent, then they, respectively, move to the vertices of a regular hexagon, forming relatively stable position information. And the message is transmitted to S, when all message from six entry points is received by S, by (5) and (6); if Euclidean distance of sensor node

S_{i}

within the regular hexagon is smaller than sensing radius, it will be removed outside the hexagon. Meanwhile the sensor node S is turned off to reduce energy consumption to improve overall network life cycle.

Theorem 5.

In the monitoring region, the maximum overlapped area of three arbitrary sensor nodes is $E A = 82.73 %$ .

Proof.

In the monitoring region, the basic pattern of overlapped area of three arbitrary sensor nodes is that one in two others' coverage region, as show in Figure 2(a).

Situation 1. If three circles are circumscribed with each other, inanition will exist but without coverage which contradicts with the condition of full coverage, so the situation is abolished.

Situation 2. Figure 2(b) shows the model of WSN’ multiple coverage; the shadow is $k = 3$ , that is, 3-coverage. If the overlapping portion is maximum, meaning $\lim_{s \to 0} S_{sh} = 0$ , when $S_{sh} = 0$ , three circles are circumscribed with each other at point A, so the Euler distance of any two circles are equal. Connect point A and point O2, and then point O1 and O2, the line intersects with circle O2 at point B, draw the midperpendicular of line point O1 and point O2 and the midperpendicular intersects with line O1O2 at point p, $∠ θ = π / 6$ . Supposing the bow’ area is $S_{APB}$ , which equals the difference between sector area $S_{AO 2 B}$ and triangle area $S_{AO 2 P}$ , there are 12 bows in Figure 2(b), and the sum of the areas can be calculated as

\begin{array}{l} 12 S_{APB} = 12 (S_{AO 2 B} - S_{AO 2 P}) \\ = 12 (\frac{π r^{2}}{12} - \frac{\sqrt{3}}{8} r^{2}) = \frac{2 π - 3 \sqrt{3}}{2} r^{2} . \end{array}

(7)

For the whole coverage region, the maximum area is

\begin{array}{l} S = 3 π r^{2} - 12 S_{APB} \\ = 3 π r^{2} - π r^{2} + \frac{3 \sqrt{3}}{2} r^{2} = 2 π r^{2} + \frac{3 \sqrt{3}}{2} r^{2} . \end{array}

(8)

The expectation $E A$ of the whole networks is

\begin{array}{l} E A = \frac{S_{Δ APO 2}}{S_{ABO 2}} = \frac{S_{ABO 2} - S_{ABP}}{S_{ABO 2}} \\ = 1 - \frac{S_{ABP}}{S_{ABO 2}} = 1 - (1 - \frac{3 \sqrt{3}}{2 π}) \\ = \frac{3 \sqrt{3}}{2 π} = 82.73 % . \end{array}

(9)

The proof is over.

Figure 2

(a) Three circles intersection. (b) Three circles intersect into a point.

Theorem 6.

Suppose the probability of an event happened among the sensors coverage region is p, the target nodes are multioverlapped. Let $K = 2$ , for the two loops, the number of moving nodes is m and n, the probability of the event is $p^{2} q^{n - 2}$ , and the conditional probability is $p q^{n - m - 1}$ , where $q = 1 - p$ .

Proof.

Suppose X is the number of moving nodes in the first loop, Y is the number of moving nodes in the second loop. From the Theorem 6, we know that the target node is covered by sensor at the m time for the first loop. For the second loop, the target node is covered twice at the n time; $n - 2$ times are not covered, so the probability of sensor nodes is

\begin{matrix} P (X = m, Y = n) = p^{2} q^{n - 2} . \end{matrix}

(10)

The joint probability of two loops is

\begin{array}{l} P (X = m) = \sum_{n = m + 1}^{\infty} P (X = m, Y = n) \\ = \sum_{n = m + 1}^{\infty} p^{2} q^{n - 2} = p q^{m - 1}, \end{array}

(11)

\begin{array}{l} P (X = n) = \sum_{m = 1}^{n - 1} P (X = m, Y = n) \\ = \sum_{m = 1}^{n - 1} p^{2} q^{n - 2} = (n - 1) p^{2} q^{n - 2} . \end{array}

(12)

According to the multiplication formula of probability theory, the result is

\begin{array}{l} P (Y = n | X = m) = \frac{P (X = m, Y = n)}{P (X = m)} \\ = \frac{p^{2} q^{n - 2}}{p q^{m - 1}} = p q^{n - m - 1} . \end{array}

(13)

4. Optimized Scheduling Strategy

4.1. Ant Colony Optimization and Evolution of Probability

Coverage control plays a vital role in coverage efficiency of wireless sensor network. How to effectively deploy the sensor nodes to cover the monitoring area completely and how to reduce the energy consumption of sensors in the process of deploying in order to extend the lifecycle of the whole network are all hot spots including focusing on how to reduce redundant code during the transmission of data and increase the transmission ratio of communication channel. For this reason, this section introduces the ant colony algorithm (ACO) to optimize the deployment of sensor nodes, mainly because ACO is an intelligent algorithm for group pattern whose workspace is a continuous search space with which all the sensor nodes can be moved to the desired area by adapting function. Combining the own characteristics of wireless sensor network and the characteristics of local convergence and global search of the ant colony optimization, which make it more flexible to deploy the sensor nodes, thus, reduces the cost of network energy and prolongs the lifecycle.

Definition 7.

In the process of traversal search, ant calculates the state transition probability according to the amount of information and the heuristic information on each path. Assume the transition probability between any two points is p, that is,

\begin{matrix} p = {\begin{cases} \frac{{[τ_{i j} (t)]}^{α} [η_{i j} {(t)}^{β}]}{(\sum_{s \subset allowed} {[τ_{i j} (t)]}^{α} [η_{i j} {(t)}^{β}])} & s \in allowed \\ 0 & s \notin allowed, \end{cases} \end{matrix}

(14)

where α is the informational heuristic factor which indicates the relative importance of track and shows the role played by the accumulated information during the movement of ant. The larger it is, the greater the possibility that other ants tend to choose the path is, and the stronger the ants collaborate. β is the expected heuristic factor, which indicates the relative importance of visibility and shows the degree of attention, paid by ant to heuristic information during the path selection. The value increases, when the state transition probability is close to 1; it becomes the greedy algorithm.

τ_{i j} (t)

and

η_{i j} (t)

represent the pheromone residual function and the heuristic function, respectively. In order to avoid the excessive residual pheromone affecting the operation of heuristic information, after the end of each traversal, the amount of information on the path should be updated, and the update function is

\begin{matrix} τ_{i j} (t + 1) = (1 - ρ) τ_{i j} (t) + ρ \sum_{k = 1}^{m} Δ τ_{i j}^{k} (t), \end{matrix}

(15)

where ρ is the pheromone evaporation coefficient, and its value range is

ρ \subset [0,1]

1 - ρ

is the number of residual pheromone factors on the path, and

\sum_{k = 1}^{m} Δ τ_{i j}^{k} (t)

represents the increment of residual pheromone produced by the former k ants on the road.

Theorem 8.

In the coverage area, any sensor node moves between the path $(i, j)$ and the iteration rule satisfies (15); the limit of the sum of incremental coverage of adjacent iterations tends to 1.

Proof.

In order to illustrate the problem better, using the incremental pheromone of the ACO to represent the incremental coverage of adjacent iterations, equations (14) and (15) show that, the value of $Δ τ_{i j}^{k} (t)$ depends on the solution function corresponding to the ants within the current search cycle. Consider $Δ τ_{i j}^{k} (t) = φ (f_{x})$ ; suppose that the target value of the solution function is $f_{s}$ ; the function of $Δ τ_{i j}^{k} (t)$ can be obtained by using $f_{s}$ as a variable of the corresponding path. Consider $Δ τ_{i j}^{k} (t) = φ (f_{x})$ , and $f_{s}$ is nonnegative; since it is the target value, to some extent it depends on the traversal paths of all the ants within the former $m - 1$ search cycles. That is, $C = \sum_{k = 1}^{m} Δ τ_{i j}^{k} (t)$ , $C \subset [0,1]$ . When $C = 0$ , as the initial time, the informational increment does not change between t and $t + 1$ ; that is, the increment of pheromone does not change within the segment of $t + 1$ ; that is, $τ_{i j} (t + 1) = τ_{i j} (t)$ . When $C \neq 0$ , the increment of pheromone depends on the incremental pheromone of the former $m - 1$ search paths; that is, $Δ τ_{i j} = C^{- 1} \sum_{k = 1}^{m} Δ τ_{i j}^{k}$ . Applying the equations described above to formula (15) and getting the limit:

\begin{matrix} \lim_{c \to 1} \sum_{k = 1}^{m} Δ τ_{i j}^{k} = \frac{1}{C} = 1 . \end{matrix}

(16)

The proof is over.

Theorem 8 shows, in the cowering area, that the limit of incremental coverage of mobile nodes within a limited number of iterations is 1, so as to achieve the purpose of complete coverage of the area.

Theorem 9.

Assume in the coverage area that the coverage rate of sensor nodes is p, the maximum upper bound of iteration is N, and the expected number of sensor nodes is $E (X) = [1 - {(1 - p)}^{N}] p^{- 1}$ until the target node is covered.

Proof.

Assume X is the number of transfers at the first time to cover the target node; the possible values of $X : X \in [0,1, 2, \dots, N]$ , when $X = k$ and $1 \leq k \leq N - 1$ , which means the target node has not been covered within the former $N - 1$ times. So, the distribution density functions of X are

\begin{matrix} P (X = k) = {\begin{cases} p {(1 - p)}^{k - 1} & k = 1,2, 3, \dots, N - 1 \\ {(1 - p)}^{N - 1} & k = N . \end{cases} \end{matrix}

(17)

Then

\begin{matrix} E (X) = \sum_{k = 1}^{N - 1} k p {(1 - p)}^{k - 1} + N {(1 - p)}^{N - 1} . \end{matrix}

(18)

Let

q = 1 - p

S = \sum_{k = 1}^{N - 1} k {(1 - p)}^{k - 1}

; then,

S = \sum_{k = 1}^{N - 1} k q^{k - 1}

; multiplying both sides of the equation with q, we get

q S = \sum_{k = 1}^{N - 1} k q^{k}

; that is,

\begin{array}{l} (1 - p) S = \sum_{k = 1}^{N - 2} q^{k} - (N - 1) q^{N - 1} \\ = \frac{1 - q^{N - 1}}{1 - q} - (N - 1) q^{N - 1}, \\ S = \frac{1 - q^{N - 1}}{{(1 - q)}^{2}} - \frac{(N - 1) q^{N - 1}}{1 - q} \\ = \frac{1 - {(1 - p)}^{N - 1}}{p^{2}} - \frac{(N - 1) {(1 - p)}^{N - 1}}{p} . \end{array}

(19)

Substituting into (18) we have:

\begin{array}{l} E (X) = p (\frac{1 - {(1 - p)}^{N - 1}}{p^{2}} - \frac{(N - 1) {(1 - p)}^{N - 1}}{p}) \\ + N {(1 - p)}^{N - 1} \\ = \frac{1 - {(1 - p)}^{N - 1}}{p} - (N - 1) {(1 - p)}^{N - 1} + N {(1 - p)}^{N - 1} \\ = \frac{1 - {(1 - p)}^{N - 1} + p {(1 - p)}^{N - 1}}{p} = [1 - {(1 - p)}^{N}] p^{- 1} . \end{array}

(20)

The proof is over.

Corollary 10.

Assume, in the coverage area, the coverage rate of sensor nodes is $P (A)$ ; then the coverage rate of node i in the area is $P (A) = 1 - \prod_{1 \leq i \leq k}$ ( $1 - P (A)$ ).

Proof.

Using mathematical induction to prove it, in the area of coverage, each sensor node is not independent of each other when the sensor node works. Therefore, the probability that two sensor nodes work is

\begin{array}{l} P (A + A) = P (A) + P (A) - P (A) P (A) \\ = 2 p - p^{2} = 1 - {(1 - p)}^{2} . \end{array}

(21)

The probability of three nodes is

\begin{matrix} P (A + A + A) = P (A + A) + P (A) - P (A + A) P (A) . \end{matrix}

(22)

Applying formula (21) to the formula above

\begin{matrix} P (A + A + A) = 1 - {(1 - p)}^{3} . \end{matrix}

(23)

When

i = n

, then

\begin{matrix} P (n A) = P [(n - 1) A] + P (A) - P [(n - 1) A] P (A) . \end{matrix}

(24)

When

i = n + 1

, applying it to the formula left,

\begin{matrix} P (A) = 1 - \prod_{1 \leq i \leq k} (1 - P (A)) . \end{matrix}

(25)

The proof is over.

Corollary 11.

Generally, assume when sensor node covers some area, the minimum probability of making the whole network work normally is $P_{2}$ ; the coverage rate of working node is $P_{1}$ ( $P_{1} \geq P_{2}$ ), so when coverage rate of the whole network is not less than $P_{3}$ ( $P_{3} \geq P_{2}$ ), N, the minimum number of sensor nodes is

\begin{matrix} N = k^{2} p_{1} (1 - p_{1}) {(p_{1} - p_{2})}^{- 2}, w h e r e, k = φ^{- 1} (p_{3}) . \end{matrix}

(26)

Proof.

According to Di Morpho Laplace central limit theorem

\begin{array}{l} P (X \geq P_{2} N) = 1 - P (X < P_{2} N) \\ = 1 - P (\frac{X - P_{1} N}{\sqrt{N P_{1} (1 - P_{1})}} < \frac{P_{2} N - P_{1} N}{\sqrt{N P_{1} (1 - P_{1})}}) \\ \approx 1 - φ (- \frac{P_{1} N - P_{2} N}{\sqrt{N P_{1} (1 - P_{1})}}) \\ = φ (\frac{P_{1} N - P_{2} N}{\sqrt{N P_{1} (1 - P_{1})}}) \geq P_{3} . \end{array}

(27)

Let

k = φ^{- 1} (p_{3})

, the formula above could be simplified to

((P_{1} N - P_{2} N) / \sqrt{N P_{1} (1 - P_{1})}) \geq k

, so

\begin{matrix} N = k^{2} p_{1} (1 - p_{1}) {(p_{1} - p_{2})}^{- 2} . \end{matrix}

(28)

The proof is over.

4.2. Dynamic Parameter Settings and Update Policies

In the process of wireless sensor network optimization coverage, the process of moving of mobile node could be quickly completed after the introduction of the ACO, thus reaching the determined final position. There are a number of parameters of the ACO; each parameter has its own practical significance. Reasonable parameter settings can improve the convergence speed, Enhance the global search capability, effective inhibition appears premature stagnation. When α is too large, it will cause a positive feedback enhancement in the local optimal path. Consider

\begin{matrix} α = {\begin{cases} κ α & τ_{i j} (t + 1) \leq τ_{i j} (t) \\ α & otherwise, \end{cases} \\ β = {\begin{cases} κ β & τ_{i j} (t + 1) \geq τ_{i j} (t) \\ β & otherwise, \end{cases} \end{matrix}

(29)

where k is the scale factor. Consider

k = τ_{i j} (t) / τ_{i j} (t + 1)

. α and β can be adjusted dynamically by k, ensuring the effectiveness of the algorithm. When the optimal value obtained by the algorithm did not change significantly within the largest circulation

N_{c \max}

, it is needed to make dynamic adjustments to ρ; the adjusted ρ should not be less than

ρ_{\min}

. Consider

\begin{matrix} ρ (t) = {\begin{cases} 0.95 ρ (t - 1) & 0.95 ρ (t - 1) \geq ρ_{\min} \\ ρ_{\min} & otherwise . \end{cases} \end{matrix}

(30)

For ACO, when the ants move to the next position in a unit of time, the pheromone of path will increase substantially, making the most of the ants choose the same path. When the number of ants that choose the same path reaches a certain quantity, stopping traversal due to the current distance exceeds the length of previous optimal path, thus making the chance of other ants to choose the other paths increase, and the solution obtained by search tends to be diverse. The update policies of pheromone update according to (15).

4.3. OSCC Algorithm Description

Through geometric theory, the sensor nodes are deployed in key target node range and ensure that the concerned target nodes are covered by at least one sensor node; we find out the associated properties relationship of the working sensor nodes in a sensor node collection. Through the ACO iterative relations and event probability function, we find the optimal subset of iterative optimization after applying the iterative optimization to divided subregions. Thus making the entire network nodes have been optimized, obtaining the minimum number of coverage nodes. Computational cost and complexity of OSCC algorithm is low, which can save energy effectively, extend the life cycle of the network, and improve the performance. (See Algorithm 1 and Procedure 1).

Procedure 1

Begin

IF (When N is empty)

S = emptyset ( $N = 0$ )

End IF

While (N)

{Do

$S = S + S_{i}$

$N = N + 1$

{switch (n)

$n = 1$ IF ( $t < = t_{\max}$ )

Set each ant colony transition probability;

Update the ant probability formula;

{ $S_{i} \leftarrow S_{i}$ ;

Dynamic parameter Settings}

IF ( $S_{i} = = 0$ );

continue;

end IF

$n = 2$ For $k = 1$ to N do

transfer (Update probability formula)

IF (flag)

flag = 1

else

flag = 0

end IF

end For

$}}$ while(S)

Algorithm 1

Initialization: The sensor nodes are initialized to 0.

Input: sensor node set $S = {s_{1}, s_{2}, \dots, s_{n}}$ ; Target monitoring area A; maximum target set T;

Output: the minimum node set achieving cover the monitoring area S;

Step 1. Initialize the target monitoring area, generate the initial velocity and the initial position of each node, and set the

size of the network N.

Step 2. Assess the effective coverage performance; give the probability of each node by formula (14), then update the local

optimum of each node particle and the global optimum of entire particle swarm by the comparison of formula (15).

Step 3. According to the formula (29) and formula (30), update the dynamic parameters respectively in order to

find suitable comparison relationships.

Step 4. After some effective iteration for Step 2, if the change of optimal value obtained by OSCC algorithm is not obvious,

go to Step 2, otherwise, continue.

Step 5. When the distance between the sensor nodes to the minimum is the minimum or the coverage rate is the maximum,

the algorithm terminates.

Compared with the traditional single coverage or coverage under other controlled forms, the OSCC algorithm has stronger search capabilities and faster convergence in the process of node optimization and deployment. However, the ability to identify the precise direction for sensor nodes is needed and more energy consumption during the node deployment.

4.4. OSCC Algorithm Complexity Analysis

In order to verify the complexity of the algorithm in this paper, we will describe some parameters:

α: information heuristic factor;

β: expectation heuristic factor;

ρ: pheromone volatilization coefficient;

n: number of sensor nodes;

m: collection of connected edges of nodes;

τ: values of pheromone;

$Δ τ$ : increment of pheromone;

t: iteration time;

p: transition probability;

$b, c$ : constant.

Assuming the number of sensor nodes is n, the number of edges between any two sensor nodes m, $τ_{0}$ , and $τ_{1}$ is the minimum and maximum of pheromone, respectively; $Δ τ$ is the incremental pheromone after iteration and ρ is the amount of residual information on the path. Let $τ_{0} = c$ , $τ_{1} = b n$ , where c and b are constant factors, t represents the number of iterations, and pheromone on the path at initial time is $τ (0) = b / n$ ; according to the probability transfer (14), at time t, the transfer probability of a sensor node is greater than $c / 2 b n$ , that the minimum probability of sensor nodes transfer is $p_{\min} = c / 2 b n$ . Pheromone update function (15) shows that the updated pheromone at time t is $τ (t) = ρ τ_{0} + (1 - ρ) τ (t - 1)$ , let $R = (1 - ρ) τ (t - 1)$ , that is, $τ (t) = ρ c + R$ . At time $t + 1$ , transition probabilities of sensor nodes are

\begin{array}{l} p (t + 1) = \frac{τ_{t + 1} (t + 1)}{τ_{t + 1} (t + 1) + τ_{t} (t + 1)} \leq \frac{τ_{t + 1} (t + 1)}{c + τ_{t} (t + 1)} \\ \leq \frac{b}{(1 - ρ) (c + c ρ + R)} . \end{array}

(31)

Let

L = b / (1 - ρ) (c + c ρ + R)

; the time complexity of the OSCC algorithm is

\begin{array}{l} E (T) = \sum_{m = 1}^{n - 1} (\frac{2 b n}{c (n - m)} \cdot {[1 - \frac{L}{n}]}^{1 - n}) \\ = \frac{2 b n}{c} {[1 - \frac{L}{n}]}^{1 - n} \sum_{m = 1}^{n - 1} \frac{1}{m} \leq \frac{2 b n}{c} e^{L} H_{n - 1} . \end{array}

(32)

Because

\sum_{m = 1}^{n - 1} (1 / m)

is the sum of the first n items of harmonic series, let

H_{n - 1} = \sum_{m = 1}^{n - 1} (1 / m)

; thus,

\sum_{x = 1}^{n - 1} (1 / x) - 1 < \int_{1}^{n - 1} (1 / x) d x < \sum_{x = 1}^{n - 1} (1 / x)

; that is,

\begin{matrix} H_{n - 1} = \sum_{m = 1}^{n - 1} \frac{1}{x} = \int_{1}^{n - 1} \frac{1}{x} d x = O (\ln n) . \end{matrix}

(33)

5. Algorithm Evaluations

To better evaluate the validity and stability of OSCC, MATLAB7 is used to be experimental platform and parameter settings are shown in Table 1.

Table 1

Data parameter list.

Parameter	Parameter values
Area I	100 * 100 m²
Area II	200 * 200 m²
Area III	400 * 400 m²
Sensor numbers	0–400
Radius	5 m
Sensor energy	2 J
α	1
β	4
ρ	0.5
Times	100

According to the parameters setting in the previous section, sensor nodes are randomly scattered in a square area of $100 * 100$ m², $200 * 200$ m², and $400 * 400$ m². Figures 3, 4, 5, 6, 7, and 8 are all network layout figures after randomly deploying nodes in the above three target areas and node deployment with OSCC.

Figure 3

$100 * 100$ m², the deployment of nodes in random form.

Figure 4

The deployment of nodes after executing OSCC algorithm.

Figure 5

$200 * 200$ m², the deployment of nodes in random form.

Figure 6

The deployment of nodes after executing OSCC algorithm.

Figure 7

$400 * 400$ m², the deployment of nodes in random form.

Figure 8

The deployment of nodes after executing OSCC algorithm.

Comparing the deployment of network nodes with Figures 3, 4, 5, 6, 7, and 8 where can be seen that network coverage with OSCC is significantly higher than that of random deployment, and the distribution of nodes is more evenly deployed. When a target area is $100 * 100$ m² and the number of nodes $N = 95$ , its coverage rate is 71.53% under usual condition, but it can reach 80.37% only with 83 sensor nodes after with OSCC; when a target area is $200 * 200$ m² and the number of nodes $N = 135$ , its coverage rate is 72.36%, but it can reach 85.08% only with 125 sensor nodes with OSCC; when a target area is $400 * 400$ m² and the number of nodes $N = 270$ , its coverage rate is 74.92%, but it can reach 91.15% only with 249 sensor nodes with OSCC.

To better evaluate validity of OSCC algorithm, simulation is done in MATLAB7 under Windows XP operating system while selecting three different coverage areas to do a comparative experiment about coverage rates. The curve between coverage rates and sensor nodes is shown in Figure 9.

Figure 9

The number of nodes and coverage rate graph.

Figure 9 reflects the relation between the number of nodes and coverage. Three curves, respectively, represent the degree of coverage rates with different sensor nodes. With the expansion of network size, the nodes needed to be deployed increase to meet the needs of network coverage, and the higher the network coverage rates are, the faster the nodes increase, meaning that full coverage is choosing different coverage areas to complete coverage with different sensor nodes. It is true that coverage of different target areas needs a different number of sensor nodes, when different areas have different coverage rate. Under certain coverage rate with the same nodes base, $100 \times 100$ m² needs minimum and maximum in $400 \times 400$ m².

This is a comparative experiment among OSCC algorithm, SCCP algorithm mentioned in [14], and PHOA algorithm mentioned in [15]. When the coverage rate is 99%, it is considered to be full coverage. The coverage area is $400 \times 400$ m² and data are based on the average of the 200 times simulations, as shown in Figure 10.

Figure 10

Three algorithms coverage variation curve under different node number.

In Figure 10, with the increasing of sensor nodes, the coverage rate increases. When $N = 320$ , the coverage rate is close to 100% with OSCC, while the other two have not yet reached 100%. This shows a coverage rate in OSCC algorithm is much higher than the other two algorithms which prove the validity of the algorithm. In Figure 11, the coverage rates of the three algorithms are the same at initial moment, but the two other algorithms' coverage rates have decreased with time going on. The main reason is that SCCP algorithm uses uninterrupted coverage about nodes in the coverage control which means that SCCP algorithm is the continuing coverage to monitoring region's target node, until the energy of the nodes is completely consumed. During the coverage process of the PHOA algorithm, after the first time's coverage, the energy consumption of the leader node is almost the same with that of other nodes, which means each node's energy is consumed in the networks, thus the coverage is decreased rapidly with time going by. However, at $t = 150$ , the OSCC declines obviously compared with two other target algorithms, the coverage of these three algorithms are 94.25%, 70.19%, and 20.13%. During the whole period of the time, the average coverage of OSCC is higher than that of other two algorithms, so OSCC would keep a higher coverage. It comes to conclusion that OSCC mentioned in this paper is the best of the three; the simulation proves its effectiveness.

Figure 11

Three algorithms coverage variation curve under different times.

6. Conclusions

Firstly, this paper gives a brief introduction of WSN applications. Secondly, literatures on coverage of WSN are studied and their algorithms are analyzed to introduce what this paper is concerned about. Thirdly, a network model is built in which the relation between sensor node and target node is given, including vector relations of different parameters. Also, the proof and derivation of maximum coverage rate and expectation in a full coverage WSN model is given. Then, the proof and derivation of coverage condition and coverage rate of multi-overage model is studied. Fourthly, this paper introduces a local fast research of ant colony optimization to improve its research performance which accelerate coverage speed of detected area and improve its coverage. What is more, the proof and derivation of coverage rate increment and expectation of target coverage is given, thus getting the coverage rate of specific detected point. Fifthly, to avoid the influence of some dynamically changed parameters on global research, this paper makes adjustments on some parameters to give out a better algorithm description. Sixthly, Simulations on different coverage areas and comparison simulations with other algorithms verify the effectiveness of OSCC. There is still some work on scheduling of multicoverage nodes and minimum set of covering surface and so on.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

National “863” High Technology Research and Development plans to fund Projects under Grant nos. 2011A01A204 and 2012AA01A306. Also this work is supported by the National Natural Science Foundation of China under Grant no. 61170245, Science of Technology Research of Foundation Project of Henan Province Education Department under Grant no. 2014B520099, Natural Science and Technology Research of Foundation Project of Henan Province Department of Science under Grant no. 142102210471, Natural Science Foundation for Young Scientists of Shanxi Province under Grant no. 2013JQ8024, Scientific Research Program Funded by Shaanxi Provincial Education Department Project no. 2013JK1139, and China Postdoctoral Science Foundation Project no. 2013M542370.

References

Hou

Y. T.

Shi

Sherali

H. D.

Rate allocation and network lifetime problems for wireless sensor networks

IEEE/ACM Transactions on Networking 2008 16 2 321 334

2-s2.0-42549161882

10.1109/TNET.2007.900407

Chen

Sun

Coverage and connectivity in duty-cycled wireless sensor networks for event monitoring

IEEE Transactions on Parallel and Distributed Systems 2012 23 3 475 482

2-s2.0-84855720973

10.1109/TPDS.2011.191

Derr

Manic

Wireless sensor network configuration-part II: adaptive coverage for decentralized algorithms

IEEE Transactions on Industrial Informatics 2013 9 3 1728 1738

2-s2.0-84882969282

10.1109/TII.2013.2245907

Chiwewe

T. M.

Hancke

G. P.

A distributed topology control technique for low interference and energy efficiency in wireless sensor networks

IEEE Transactions on Industrial Informatics 2012 8 1 11 19

2-s2.0-84856352376

10.1109/TII.2011.2166778

Tamboli

Younis

Coverage-aware connectivity restoration in mobile sensor networks

Journal of Network and Computer Applications 2010 33 4 363 374

2-s2.0-79953013278

10.1016/j.jnca.2010.03.008

Sheu

J.-P.

Lin

H.-F.

Probabilistic coverage preserving protocol with energy efficiency in wireless sensor networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '07)

March 2007

2633 2638

2-s2.0-36348967336

10.1109/WCNC.2007.489

De Mello

R. F.

Cuenca

R. G.

Yang

L. T.

Genetic algorithms applied to organize wireless sensor networks aiming good coverage and redundancy

Proceedings of the 1st International Conference on Communications and Networking in China (ChinaCom '06)

October 2006

2-s2.0-36048973993

10.1109/CHINACOM.2006.344694

Habib

Safar

Sensitivity study of sensors' coverage within wireless sensor networks

Proceedings of the 16th International Conference on Computer Communications and Networks (ICCCN '07)

August 2007

876 881

2-s2.0-40949154017

10.1109/ICCCN.2007.4317928

Lee

Dharne

A. D.

Jayasuriya

Potential field based hierarchical structure for mobile sensor network deployment

Proceedings of the American Control Conference (ACC '07)

July 2007

5946 5951

2-s2.0-46449112941

10.1109/ACC.2007.4282565

10.

Wang

J.-J.

An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment

Sensors 2007 7 3 354 370

2-s2.0-34047170719

11.

Wang

J.-J.

Wang

D.-W.

Distributed particle swarm optimization and simulated annealing for energy-efficient coverage in wireless sensor networks

Sensors 2007 7 5 628 648

2-s2.0-34249885891

12.

Tian

Wang

Zhang

S.-F.

A distributed probabilistic-coverage node scheduling scheme for large wireless sensor networks

Proceedings of the International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM '07)

September 2007

2464 2468

2-s2.0-38049076365

10.1109/WICOM.2007.614

13.

Wang

Y.-H.

C.-N.

P.-F.

A coverage and connectivity method to cluster topology in wireless sensor networks

Proceedings of the 21st International Conference on Advanced Information Networking and ApplicationsWorkshops/Symposia (AINAW '07)

May 2007

97 102

2-s2.0-35248853382

10.1109/AINAW.2007.16

14.

Xing

Wang

Square region-based coverage and connectivity probability model in wireless sensor networks

Proceedings of the 5th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom '09)

November 2009

1 8

2-s2.0-76349085440

10.4108/ICST.COLLABORATECOM2009.8335

15.

Zeyu

Zhenping

Wireless sensor network path optimization based on hybrid algorithm

TELKOMNIKA, Indonesian Journal of Electrical Engineering 2013 11 9 5352 5358