2 % v4.0 released April 2013
6 \usepackage{indentfirst}
8 \usepackage[algo2e,ruled,vlined]{algorithm2e}
11 \title{{\itshape Perimeter-based Coverage Optimization \\
12 to Improve Lifetime in Wireless Sensor Networks}}
14 \author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$$^{\ast}$\thanks{$^\ast$Corresponding author. Email: karine.deschinkel@univ-fcomte.fr}, Michel Salomon$^{a}$, and Rapha\"el Couturier $^{a}$
15 $^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, \\
16 University Bourgogne Franche-Comt\'e, Belfort, France}} \\
17 $^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}}
23 The most important problem in a Wireless Sensor Network (WSN) is to optimize the
24 use of its limited energy provision, so that it can fulfill its monitoring task
25 as long as possible. Among known available approaches that can be used to
26 improve power management, lifetime coverage optimization provides activity
27 scheduling which ensures sensing coverage while minimizing the energy cost. An approach called Perimeter-based Coverage Optimization protocol
28 (PeCO) is proposed. It is a hybrid of centralized and distributed methods: the region of
29 interest is first subdivided into subregions and the protocol is then
30 distributed among sensor nodes in each subregion. The novelty of the approach
31 lies essentially in the formulation of a new mathematical optimization model
32 based on the perimeter coverage level to schedule sensors' activities.
33 Extensive simulation experiments demonstrate that PeCO can offer longer lifetime
34 coverage for WSNs compared to other protocols.
37 Wireless Sensor Networks, Area Coverage, Energy efficiency, Optimization, Scheduling.
42 \section{Introduction}
43 \label{sec:introduction}
45 The continuous progress in Micro Electro-Mechanical Systems (MEMS) and wireless
46 communication hardware has given rise to the opportunity of using large networks
47 of tiny sensors, called Wireless Sensor Networks
48 (WSN)~\citep{akyildiz2002wireless,puccinelli2005wireless}, to fulfill monitoring
49 tasks. A WSN consists of small low-powered sensors working together by
50 communicating with one another through multi-hop radio communications. Each node
51 can send the data it collects in its environment, thanks to its sensor, to the
52 user by means of sink nodes. The features of a WSN makes it suitable for a wide
53 range of applications in areas such as business, environment, health, industry,
54 military, and so on~\citep{yick2008wireless}. Typically, a sensor node contains
55 three main components~\citep{anastasi2009energy}: a sensing unit able to measure
56 physical, chemical, or biological phenomena observed in the environment; a
57 processing unit which will process and store the collected measurements; a radio
58 communication unit for data transmission and reception.
60 The energy needed by an active sensor node to perform sensing, processing, and
61 communication is provided by a power supply which is a battery. This battery has
62 a limited energy provision and it may be unsuitable or impossible to replace or
63 recharge in most applications. Therefore it is necessary to deploy WSN with high
64 density in order to increase reliability and to exploit node redundancy thanks
65 to energy-efficient activity scheduling approaches. Indeed, the overlap of
66 sensing areas can be exploited to schedule alternatively some sensors in a low
67 power sleep mode and thus save energy. Overall, the main question that must be
68 answered is: how is it possible to extend the lifetime coverage of a WSN as long
69 as possible while ensuring a high level of coverage? These past few years many
70 energy-efficient mechanisms have been suggested to retain energy and extend the
71 lifetime of the WSNs~\citep{rault2014energy}.
73 This paper makes the following contributions :
75 \item A framework is devised to schedule nodes to be activated alternatively
76 such that the network lifetime is prolonged while ensuring that a certain
77 level of coverage is preserved. A key idea in the proposed framework is to
78 exploit spatial and temporal subdivision. On the one hand, the area of
79 interest is divided into several smaller subregions and, on the other hand,
80 the time line is divided into periods of equal length. In each subregion the
81 sensor nodes will cooperatively choose a leader which will schedule nodes'
82 activities, and this grouping of sensors is similar to typical cluster
84 \item A new mathematical optimization model is proposed. Instead of trying to
85 cover a set of specified points/targets as in most of the methods proposed in
86 the literature, a mixed-integer program based on the perimeter
87 coverage of each sensor is formulated. The model involves integer variables to capture the
88 deviations between the actual level of coverage and the required level.
89 Hence, an optimal schedule will be obtained by minimizing a weighted sum of
91 \item Extensive simulation experiments are conducted using the discrete event
92 simulator OMNeT++, to demonstrate the efficiency of the PeCO protocol. The PeCO protocol has been compared to two approaches found in the literature:
93 DESK~\citep{ChinhVu} and GAF~\citep{xu2001geography}, and also to the
94 protocol DiLCO published in~\citep{Idrees2}. DiLCO uses the same framework as
95 PeCO but is based on another optimization model for sensor scheduling.
98 The rest of the paper is organized as follows. In the next section some related
99 work in the field is reviewed. Section~\ref{sec:The PeCO Protocol Description}
100 is devoted to the PeCO protocol description and Section~\ref{cp} focuses on the
101 coverage model formulation which is used to schedule the activation of sensor
102 nodes. Section~\ref{sec:Simulation Results and Analysis} presents simulations
103 results and discusses the comparison with other approaches. Finally, concluding
104 remarks are drawn and some suggestions are given for future works in
105 Section~\ref{sec:Conclusion and Future Works}.
107 \section{Related Literature}
108 \label{sec:Literature Review}
110 This section summarizes some related works regarding the coverage problem and
111 presents specific aspects of the PeCO protocol common with other literature
114 The most discussed coverage problems in literature can be classified in three
115 categories~\citep{li2013survey} according to their respective monitoring
116 objective. Hence, area coverage \citep{Misra} means that every point inside a
117 fixed area must be monitored, while target coverage~\citep{yang2014novel} refers
118 to the objective of coverage for a finite number of discrete points called
119 targets, and barrier coverage~\citep{HeShibo,kim2013maximum} focuses on
120 preventing intruders from entering into the region of interest. In
121 \citep{Deng2012} authors transform the area coverage problem into the target
122 coverage one, taking into account the intersection points among disks of sensors
123 nodes or between disks of sensor nodes and boundaries. In
124 \citep{huang2005coverage} authors prove that if the perimeters of the sensors
125 are sufficiently covered it will be the case for the whole area. They provide an
126 algorithm in $O(nd~log~d)$ time to compute the perimeter-coverage of each
127 sensor. $d$ denotes the maximum number of sensors that are neighbors to a
128 sensor, and $n$ is the total number of sensors in the network. {\it In PeCO
129 protocol, instead of determining the level of coverage of a set of discrete
130 points, the optimization model is based on checking the perimeter-coverage of
131 each sensor to activate a minimal number of sensors.}
133 The major approach to extend network lifetime while preserving coverage is to
134 divide/organize the sensors into a suitable number of set covers (disjoint or
135 non-disjoint) \citep{wang2011coverage}, where each set completely covers a
136 region of interest, and to successively activate these set covers. The network
137 activity can be planned in advance and scheduled for the entire network lifetime
138 or organized in periods, and the set of active sensor nodes decided at the
139 beginning of each period \citep{ling2009energy}. In fact, many authors propose
140 algorithms working in such a periodic fashion
141 \citep{chin2007,yan2008design,pc10}. Active node selection is determined based
142 on the problem requirements (e.g. area monitoring, connectivity, or power
143 efficiency). For instance, \citet{jaggi2006} address the problem of maximizing
144 the lifetime by dividing sensors into the maximum number of disjoint subsets
145 such that each subset can ensure both coverage and connectivity. A greedy
146 algorithm is applied once to solve this problem and the computed sets are
147 activated in succession to achieve the desired network lifetime. {\it Motivated
148 by these works, PeCO protocol works in periods, where each period contains a
149 preliminary phase for information exchange and decisions, followed by a
150 sensing phase where one cover set is in charge of the sensing task.}
152 Various centralized and distributed approaches, or even a mixing of these two
153 concepts, have been proposed to extend the network lifetime
154 \citep{zhou2009variable}. In distributed
155 algorithms~\citep{ChinhVu,qu2013distributed,yangnovel} each sensor decides of
156 its own activity scheduling after an information exchange with its neighbors.
157 The main interest of such an approach is to avoid long range communications and
158 thus to reduce the energy dedicated to the communications. Unfortunately, since
159 each node has information on its immediate neighbors only (usually the one-hop
160 ones), it may make a bad decision leading to a global suboptimal solution.
161 Conversely, centralized
162 algorithms~\citep{cardei2005improving,zorbas2010solving,pujari2011high} always
163 provide nearly optimal solutions since the algorithm has a global view of the
164 whole network. The disadvantage of a centralized method is obviously its high
165 cost in communications needed to transmit to a single node, the base station
166 which will globally schedule nodes' activities, data from all the other sensor
167 nodes in the area. The price in communications can be huge since long range
168 communications will be needed. In fact the larger the WSN, the higher the
169 communication energy cost. {\it In order to be suitable for large-scale
170 networks, in the PeCO protocol the area of interest is divided into several
171 smaller subregions, and in each one, a node called the leader is in charge of
172 selecting the active sensors for the current period. Thus the PeCO protocol
173 is scalable and a globally distributed method, whereas it is centralized in
176 Various coverage scheduling algorithms have been developed these past few years.
177 Many of them, dealing with the maximization of the number of cover sets, are
178 heuristics. These heuristics involve the construction of a cover set by
179 including in priority the sensor nodes which cover critical targets, that is to
180 say targets that are covered by the smallest number of sensors
181 \citep{berman04,zorbas2010solving}. Other approaches are based on mathematical
183 formulations~\citep{cardei2005energy,5714480,pujari2011high,Yang2014} and
184 dedicated techniques (solving with a branch-and-bound algorithm available in
185 optimization solver). The problem is formulated as an optimization problem
186 (maximization of the lifetime or number of cover sets) under target coverage and
187 energy constraints. Column generation techniques, well-known and widely
188 practiced techniques for solving linear programs with too many variables, have
190 used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012column}.
191 {\it In the PeCO protocol, each leader, in charge of a subregion, solves an
192 integer program which has a twofold objective: minimizing the overcoverage and
193 the undercoverage of the perimeter of each sensor.}
195 The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage
196 Optimization (DiLCO) protocol, which maintains the coverage and improves the
197 lifetime in WSNs. It is an improved version of a research work presented
198 in~\citep{idrees2014coverage}. First, the area of interest is partitioned into
199 subregions using a divide-and-conquer method. The DiLCO protocol is then
200 distributed on the sensor nodes in each subregion in a second step. Hence this
201 protocol combines two techniques: a leader election in each subregion, followed
202 by an optimization-based node activity scheduling performed by each elected
203 leader. The proposed DiLCO protocol is a periodic protocol where each period is
204 decomposed into 4 phases: information exchange, leader election, decision, and
205 sensing. The simulations show that DiLCO is able to increase the WSN lifetime
206 and provides improved coverage performance. {\it In the PeCO protocol, a new
207 mathematical optimization model is proposed. Instead of trying to cover a set
208 of specified points/targets as in the DiLCO protocol, an integer
209 program based on the perimeter coverage of each sensor is formulated. The model involves
210 integer variables to capture the deviations between the actual level of
211 coverage and the required level. The idea is that an optimal scheduling will
212 be obtained by minimizing a weighted sum of these deviations.}
214 \section{ The P{\scshape e}CO Protocol Description}
215 \label{sec:The PeCO Protocol Description}
218 \subsection{Assumptions and Models}
221 A WSN consisting of $J$ stationary sensor nodes randomly and uniformly
222 distributed in a bounded sensor field is considered. The wireless sensors are
223 deployed in high density to ensure initially a high coverage ratio of the area
224 of interest. All the sensor nodes are supposed to be homogeneous in terms of
225 communication, sensing, and processing capabilities and heterogeneous from the
226 energy provision point of view. The location information is available to a
227 sensor node either through hardware such as embedded GPS or location discovery
228 algorithms. A Boolean disk coverage model, which is the most widely used sensor
229 coverage model in the literature, is considered and all sensor nodes have a
230 constant sensing range $R_s$. Thus, all the space points within a disk centered
231 at a sensor with a radius equal to the sensing range are said to be covered by
232 this sensor. The communication range $R_c$ is assumed to satisfy : $R_c
233 \geq 2 \cdot R_s$. In fact, \citet{Zhang05} proved that if the transmission
234 range fulfills the previous hypothesis, the complete coverage of a convex area
235 implies connectivity among active nodes.
237 The PeCO protocol uses the same perimeter-coverage model as
238 \citet{huang2005coverage}. It can be expressed as follows: a sensor is said to
239 be perimeter covered if all the points on its perimeter are covered by at least
240 one sensor other than itself. Authors \citet{huang2005coverage} proved that a
241 network area is $k$-covered (every point in the area is covered by at least
242 $k$~sensors) if and only if each sensor in the network is $k$-perimeter-covered
243 (perimeter covered by at least $k$ sensors).
245 Figure~\ref{figure1}(a) shows the coverage of sensor node~$0$. On this figure,
246 sensor~$0$ has nine neighbors. For each neighbor the two points
247 resulting from the intersection of the two sensing areas have been reported on its perimeter (the
248 perimeter of the disk covered by the sensor~$0$). These points are
249 denoted for neighbor~$i$ by $iL$ and $iR$, respectively for left and right from
250 a neighboring point of view. The resulting couples of intersection points
251 subdivide the perimeter of sensor~$0$ into portions called arcs.
255 \begin{tabular}{@{}cr@{}}
256 \includegraphics[width=75mm]{figure1a.eps} & \raisebox{3.25cm}{(a)} \\
257 \includegraphics[width=75mm]{figure1b.eps} & \raisebox{2.75cm}{(b)}
259 \caption{(a) Perimeter coverage of sensor node 0 and (b) finding the arc of
260 $u$'s perimeter covered by $v$.}
264 Figure~\ref{figure1}(b) describes the geometric information used to find the
265 locations of the left and right points of an arc on the perimeter of a sensor
266 node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the
267 west side of sensor~$u$, with the following respective coordinates in the
268 sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates the
269 euclidean distance between nodes~$u$ and $v$ is computed as follows:
271 Dist(u,v)=\sqrt{(u_x - v_x)^2 + (u_y-v_y)^2},
273 while the angle~$\alpha$ is obtained through the formula:
275 \alpha = \arccos \left(\frac{Dist(u,v)}{2R_s} \right).
277 The arc on the perimeter of~$u$ defined by the angular interval $[\pi -
278 \alpha,\pi + \alpha]$ is then said to be perimeter-covered by sensor~$v$.
280 Every couple of intersection points is placed on the angular interval $[0,2\pi)$
281 in a counterclockwise manner, leading to a partitioning of the interval.
282 Figure~\ref{figure1}(a) illustrates the arcs for the nine neighbors of
283 sensor $0$ and Table~\ref{my-label} gives the position of the corresponding arcs
284 in the interval $[0,2\pi)$. More precisely, the points are
285 ordered according to the measures of the angles defined by their respective
286 positions. The intersection points are then visited one after another, starting
287 from the first intersection point after point~zero, and the maximum level of
288 coverage is determined for each interval defined by two successive points. The
289 maximum level of coverage is equal to the number of overlapping arcs. For
290 example, between~$5L$ and~$6L$ the maximum level of coverage is equal to $3$
291 (the value is highlighted in yellow at the bottom of Figure~\ref{figure2}), which
292 means that at most 2~neighbors can cover the perimeter in addition to node $0$.
293 Table~\ref{my-label} summarizes for each coverage interval the maximum level of
294 coverage and the sensor nodes covering the perimeter. The example discussed
295 above is thus given by the sixth line of the table.
299 \includegraphics[width=0.95\linewidth]{figure2.eps}
300 \caption{Maximum coverage levels for perimeter of sensor node $0$.}
305 \tbl{Coverage intervals and contributing sensors for node 0 \label{my-label}}
306 {\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
308 \begin{tabular}[c]{@{}c@{}}Left \\ point \\ angle~$\alpha$ \end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ left \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ right \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Maximum \\ coverage\\ level\end{tabular} & \multicolumn{5}{c|}{\begin{tabular}[c]{@{}c@{}}Set of sensors\\ involved \\ in coverage interval\end{tabular}} \\ \hline
309 0.0291 & 1L & 2L & 4 & 0 & 1 & 3 & 4 & \\ \hline
310 0.104 & 2L & 3R & 5 & 0 & 1 & 3 & 4 & 2 \\ \hline
311 0.3168 & 3R & 4R & 4 & 0 & 1 & 4 & 2 & \\ \hline
312 0.6752 & 4R & 1R & 3 & 0 & 1 & 2 & & \\ \hline
313 1.8127 & 1R & 5L & 2 & 0 & 2 & & & \\ \hline
314 1.9228 & 5L & 6L & 3 & 0 & 2 & 5 & & \\ \hline
315 2.3959 & 6L & 2R & 4 & 0 & 2 & 5 & 6 & \\ \hline
316 2.4258 & 2R & 7L & 3 & 0 & 5 & 6 & & \\ \hline
317 2.7868 & 7L & 8L & 4 & 0 & 5 & 6 & 7 & \\ \hline
318 2.8358 & 8L & 5R & 5 & 0 & 5 & 6 & 7 & 8 \\ \hline
319 2.9184 & 5R & 7R & 4 & 0 & 6 & 7 & 8 & \\ \hline
320 3.3301 & 7R & 9R & 3 & 0 & 6 & 8 & & \\ \hline
321 3.9464 & 9R & 6R & 4 & 0 & 6 & 8 & 9 & \\ \hline
322 4.767 & 6R & 3L & 3 & 0 & 8 & 9 & & \\ \hline
323 4.8425 & 3L & 8R & 4 & 0 & 3 & 8 & 9 & \\ \hline
324 4.9072 & 8R & 4L & 3 & 0 & 3 & 9 & & \\ \hline
325 5.3804 & 4L & 9R & 4 & 0 & 3 & 4 & 9 & \\ \hline
326 5.9157 & 9R & 1L & 3 & 0 & 3 & 4 & & \\ \hline
332 In the PeCO protocol, the scheduling of the sensor nodes' activities is
333 formulated with a mixed-integer program based on coverage
334 intervals~\citep{doi:10.1155/2010/926075}. The formulation of the coverage
335 optimization problem is detailed in~Section~\ref{cp}. Note that when a sensor
336 node has a part of its sensing range outside the WSN sensing field, as in
337 Figure~\ref{figure3}, the maximum coverage level for this arc is set to $\infty$
338 and the corresponding interval will not be taken into account by the
339 optimization algorithm.
344 \includegraphics[width=57.5mm]{figure3.eps}
345 \caption{Sensing range outside the WSN's area of interest.}
351 \subsection{Main Idea}
353 The WSN area of interest is, in a first step, divided into regular homogeneous
354 subregions using a divide-and-conquer algorithm. In a second step the protocol
355 will be executed in a distributed way in each subregion simultaneously to
356 schedule nodes' activities for one sensing period. Sensor nodes are assumed to
357 be deployed almost uniformly over the region. The regular subdivision is made
358 such that the number of hops between any pairs of sensors inside a subregion is
359 less than or equal to 3.
361 As shown in Figure~\ref{figure4}, node activity scheduling is produced by the
362 proposed protocol in a periodic manner. Each period is divided into 4 stages:
363 Information (INFO) Exchange, Leader Election, Decision (the result of an
364 optimization problem), and Sensing. For each period there is exactly one set
365 cover responsible for the sensing task. Protocols based on a periodic scheme,
366 like PeCO, are more robust against an unexpected node failure. On the one hand,
367 if a node failure is discovered before taking the decision, the corresponding
368 sensor node will not be considered by the optimization algorithm. On the other
369 hand, if the sensor failure happens after the decision, the sensing task of the
370 network will be temporarily affected: only during the period of sensing until a
371 new period starts, since a new set cover will take charge of the sensing task in
372 the next period. The energy consumption and some other constraints can easily be
373 taken into account since the sensors can update and then exchange their
374 information (including their residual energy) at the beginning of each period.
375 However, the pre-sensing phases (INFO Exchange, Leader Election, and Decision)
376 are energy consuming, even for nodes that will not join the set cover to monitor
377 the area. Sensing period duration is adapted according to the QoS requirements
382 \includegraphics[width=80mm]{figure4.eps}
383 \caption{PeCO protocol.}
387 Two types of packets used by the PeCO protocol are defined:
389 \item INFO packet: sent by each sensor node to all the nodes inside a same
390 subregion for information exchange.
391 \item ActiveSleep packet: sent by the leader to all the nodes in its subregion
392 to transmit to them their respective status (stay Active or go Sleep) during
396 Five statuses are possible for a sensor node in the network:
398 \item LISTENING: waits for a decision (to be active or not);
399 \item COMPUTATION: executes the optimization algorithm as leader to
400 determine the activities scheduling;
401 \item ACTIVE: node is sensing;
402 \item SLEEP: node is turned off;
403 \item COMMUNICATION: transmits or receives packets.
406 \subsection{PeCO Protocol Algorithm}
408 The pseudocode implementing the protocol on a node is given below. More
409 precisely, Algorithm~\ref{alg:PeCO} gives a brief description of the protocol
410 applied by a sensor node $s_k$ where $k$ is the node index in the WSN.
415 \caption{PeCO pseudocode}
416 \eIf{$RE_k \geq E_{th}$}{
417 $s_k.status$ = COMMUNICATION\;
418 Send $INFO()$ packet to other nodes in subregion\;
419 Wait $INFO()$ packet from other nodes in subregion\;
420 Update K.CurrentSize\;
421 LeaderID = Leader election\;
422 \eIf{$s_k.ID = LeaderID$}{
423 $s_k.status$ = COMPUTATION\;
424 \If{$ s_k.ID $ is Not previously selected as a Leader}{
425 Execute the perimeter coverage model\;
427 \eIf{($s_k.ID $ is the same Previous Leader) {\bf and} \\
428 \indent (K.CurrentSize = K.PreviousSize)}{
429 Use the same previous cover set for current sensing stage\;
431 Update $a^j_{ik}$; prepare data for IP~Algorithm\;
432 $\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$)\;
433 K.PreviousSize = K.CurrentSize\;
435 $s_k.status$ = COMMUNICATION\;
436 Send $ActiveSleep()$ to each node $l$ in subregion\;
439 $s_k.status$ = LISTENING\;
440 Wait $ActiveSleep()$ packet from the Leader\;
444 Exclude $s_k$ from entering in the current sensing stage\;
448 In this algorithm, $K.CurrentSize$ and $K.PreviousSize$ respectively represent
449 the current number and the previous number of living nodes in the subnetwork of
450 the subregion. At the beginning of the first period $K.PreviousSize$ is
451 initialized to zero. Initially, the sensor node checks its remaining energy
452 $RE_k$, which must be greater than a threshold $E_{th}$ in order to participate
453 in the current period. Each sensor node determines its position and its
454 subregion using an embedded GPS or a location discovery algorithm. After that,
455 all the sensors collect position coordinates, remaining energy, sensor node ID,
456 and the number of their one-hop live neighbors during the information exchange.
457 Both INFO packet and ActiveSleep packet contain two parts: header and data payload. The sensor ID is included in the header, where the header size is 8 bits. The data part includes position coordinates (64 bits), remaining energy (32 bits), and the number of one-hop live neighbors (8 bits). Therefore the size of the INFO packet is 112 bits. The ActiveSleep packet is 16 bits size, 8 bits for the header and 8 bits for data part that includes only sensor status (0 or 1).
458 The sensors inside a same region cooperate to elect a leader. The selection
459 criteria for the leader are (in order of priority):
461 \item larger number of neighbors;
462 \item larger remaining energy;
463 \item and then, in case of equality, larger indexes.
465 Once chosen, the leader collects information to formulate and solve the integer
466 program which allows to build the set of active sensors in the sensing
469 \section{Perimeter-based Coverage Problem Formulation}
472 In this section, the perimeter-based coverage problem is mathematically
473 formulated. It has been proved to be a NP-hard problem
474 by \citep{doi:10.1155/2010/926075}. Authors study the coverage of the perimeter
475 of a large object requiring to be monitored. For the proposed formulation in
476 this paper, the large object to be monitored is the sensor itself (or more
477 precisely its sensing area).
479 The following notations are used throughout the section.
481 First, the following sets:
483 \item $S$ represents the set of sensor nodes;
484 \item $A \subseteq S $ is the subset of alive sensors;
485 \item $I_j$ designates the set of coverage intervals (CI) obtained for
488 $I_j$ refers to the set of coverage intervals which has been defined according
489 to the method introduced in Subsection~\ref{CI}. For a coverage interval $i$,
490 let $a^j_{ik}$ denote the indicator function of whether sensor~$k$ is involved
491 in coverage interval~$i$ of sensor~$j$, that is:
495 1 & \mbox{if sensor $k$ is involved in the } \\
496 & \mbox{coverage interval $i$ of sensor $j$}, \\
497 0 & \mbox{otherwise.}\\
500 Note that $a^k_{ik}=1$ by definition of the interval.
502 Second, several variables are defined. Hence, each binary variable $X_{k}$
503 determines the activation of sensor $k$ in the sensing phase ($X_k=1$ if the
504 sensor $k$ is active or 0 otherwise). $M^j_i$ is a variable which measures the
505 undercoverage for the coverage interval $i$ corresponding to sensor~$j$. In the
506 same way, the overcoverage for the same coverage interval is given by the
509 To sustain a level of coverage equal to $l$ all along the perimeter of sensor
510 $j$, at least $l$ sensors involved in each coverage interval $i \in I_j$ of
511 sensor $j$ have to be active. According to the previous notations, the number
512 of active sensors in the coverage interval $i$ of sensor $j$ is given by
513 $\sum_{k \in A} a^j_{ik} X_k$. To extend the network lifetime, the objective is
514 to activate a minimal number of sensors in each period to ensure the desired
515 coverage level. As the number of alive sensors decreases, it becomes impossible
516 to reach the desired level of coverage for all coverage intervals. Therefore
517 variables $M^j_i$ and $V^j_i$ are introduced as a measure of the deviation
518 between the desired number of active sensors in a coverage interval and the
519 effective number. And these deviations are minimized, first to force the
520 activation of a minimal number of sensors to ensure the desired coverage level,
521 and if the desired level cannot be completely satisfied, to reach a coverage
522 level as close as possible to the desired one.
524 The coverage optimization problem can then be mathematically expressed as follows:
527 \text{Minimize } & \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i ) \\
528 \text{Subject to:} & \\
529 & \sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i \geq l \quad \forall i \in I_j, \forall j \in S \\
530 & \sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i \leq l \quad \forall i \in I_j, \forall j \in S \\
531 & X_{k} \in \{0,1\}, \forall k \in A \\
532 & M^j_i, V^j_i \in \mathbb{R}^{+}
537 If a given level of coverage $l$ is required for one sensor, the sensor is said
538 to be undercovered (respectively overcovered) if the level of coverage of one of
539 its CI is less (respectively greater) than $l$. If the sensor $j$ is
540 undercovered, there exists at least one of its CI (say $i$) for which the number
541 of active sensors (denoted by $l^{i}$) covering this part of the perimeter is
542 less than $l$ and in this case : $M_{i}^{j}=l-l^{i}$, $V_{i}^{j}=0$. Conversely,
543 if the sensor $j$ is overcovered, there exists at least one of its CI (say $i$)
544 for which the number of active sensors (denoted by $l^{i}$) covering this part
545 of the perimeter is greater than $l$ and in this case: $M_{i}^{j}=0$,
548 $\alpha^j_i$ and $\beta^j_i$ are nonnegative weights selected according to the
549 relative importance of satisfying the associated level of coverage. For example,
550 weights associated with coverage intervals of the specified part of a region may
551 be given by a relatively larger magnitude than weights associated with another
552 region. This kind of mixed-integer program is inspired from the model developed
553 for brachytherapy treatment planning to optimize dose distribution
554 \citep{0031-9155-44-1-012}. The choice of the values for variables $\alpha$ and
555 $\beta$ should be made according to the needs of the application. $\alpha$
556 should be large enough to prevent undercoverage and so to reach the highest
557 possible coverage ratio. $\beta$ should be large enough to prevent overcoverage
558 and so to activate a minimum number of sensors. The mixed-integer program must
559 be solved by the leader in each subregion at the beginning of each sensing
560 phase, whenever the environment has changed (new leader, death of some sensors).
561 Note that the number of constraints in the model is constant (constraints of
562 coverage expressed for all sensors), whereas the number of variables $X_k$
563 decreases over periods, since only alive sensors (sensors with enough energy to
564 be alive during one sensing phase) are considered in the model.
566 \section{Performance Evaluation and Analysis}
567 \label{sec:Simulation Results and Analysis}
569 \subsection{Simulation Settings}
571 The WSN area of interest is supposed to be divided into 16~regular subregions
572 and the energy consumption model used is described in previous
573 work~\citep{Idrees2}. Table~\ref{table3} gives the chosen parameters settings.
576 \tbl{Relevant parameters for network initialization \label{table3}}{
580 Parameter & Value \\ [0.5ex]
582 % inserts single horizontal line
583 Sensing field & $(50 \times 25)~m^2 $ \\
584 WSN size & 100, 150, 200, 250, and 300~nodes \\
585 Initial energy & in range 500-700~Joules \\
586 Sensing period & duration of 60 minutes \\
587 $E_{th}$ & 36~Joules \\
590 $\alpha^j_i$ & 0.6 \\
595 To obtain experimental results which are relevant, simulations with five
596 different node densities going from 100 to 300~nodes were performed considering
597 each time 25~randomly generated networks. The nodes are deployed on a field of
598 interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a
599 high coverage ratio. Each node has an initial energy level, in Joules, which is
600 randomly drawn in the interval $[500-700]$. If its energy provision reaches a
601 value below the threshold $E_{th}=36$~Joules, the minimum energy needed for a
602 node to stay active during one period, it will no longer participate in the
603 coverage task. This value corresponds to the energy needed by the sensing phase,
604 obtained by multiplying the energy consumed in the active state (9.72 mW) with
605 the time in seconds for one period (3600 seconds), and adding the energy for the
606 pre-sensing phases. According to the interval of initial energy, a sensor may
607 be active during at most 20 periods. the information exchange to update the coverage
608 is executed every hour, but the length of the sensing period could be reduced
609 and adapted dynamically. On the one hand a small sensing period would allow the network to
610 be more reliable but would have resulted in higher communication costs. On the
611 other hand the choice of a long duration may cause problems in case of nodes
612 failure during the sensing period.
614 The values of $\alpha^j_i$ and $\beta^j_i$ have been chosen to ensure a good
615 network coverage and a longer WSN lifetime. Higher priority is given to the
616 undercoverage (by setting the $\alpha^j_i$ with a larger value than $\beta^j_i$)
617 so as to prevent the non-coverage for the interval~$i$ of the sensor~$j$. On
618 the other hand, $\beta^j_i$ is assigned to a value which is slightly lower so as
619 to minimize the number of active sensor nodes which contribute in covering the
620 interval. Subsection~\ref{sec:Impact} investigates more deeply how the values of
621 both parameters affect the performance of the PeCO protocol.
623 The following performance metrics are used to evaluate the efficiency of the
626 \item {\bf Network Lifetime}: the lifetime is defined as the time elapsed until
627 the coverage ratio falls below a fixed threshold. $Lifetime_{95}$ and
628 $Lifetime_{50}$ denote, respectively, the amount of time during which is
629 guaranteed a level of coverage greater than $95\%$ and $50\%$. The WSN can
630 fulfill the expected monitoring task until all its nodes have depleted their
631 energy or if the network is no more connected. This last condition is crucial
632 because without network connectivity a sensor may not be able to send to a
633 base station an event it has sensed.
634 \item {\bf Coverage Ratio (CR)} : it measures how well the WSN is able to
635 observe the area of interest. Here the sensor field is discretized as
636 a regular grid, which yields the following equation:
639 \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100
641 where $n$ is the number of covered grid points by active sensors of every
642 subregions during the current sensing phase and $N$ is total number of grid
643 points in the sensing field. A layout of $N~=~51~\times~26~=~1326$~grid points
644 is considered in the simulations.
645 \item {\bf Active Sensors Ratio (ASR)}: a major objective of the proposed protocol is to
646 activate as few nodes as possible, in order to minimize the communication
647 overhead and maximize the WSN lifetime. The active sensors ratio is defined as
651 \mbox{ASR}(\%) = \frac{\sum\limits_{r=1}^R \mbox{$|A_r^p|$}}{\mbox{$|J|$}} \times 100
653 where $|A_r^p|$ is the number of active sensors in the subregion $r$ in the
654 sensing period~$p$, $R$ is the number of subregions, and $|J|$ is the number
655 of sensors in the network.
657 \item {\bf Energy Saving Ratio (ESR)}:this metric, which shows the ability of a protocol to save energy, is defined by:
660 \mbox{ESR}(\%) = \frac{\mbox{Number of alive sensors during this round}}
661 {\mbox{Total number of sensors in the network}} \times 100.
663 \item {\bf Energy Consumption (EC)}: energy consumption can be seen as the total
664 energy consumed by the sensors during $Lifetime_{95}$ or $Lifetime_{50}$,
665 divided by the number of periods. The value of EC is computed according to
669 \mbox{EC} = \frac{\sum\limits_{p=1}^{P} \left( E^{\mbox{com}}_p+E^{\mbox{list}}_p+E^{\mbox{comp}}_p
670 + E^{a}_p+E^{s}_p \right)}{P},
672 where $P$ corresponds to the number of periods. The total energy consumed by
673 the sensors comes through taking into consideration four main energy
674 factors. The first one, denoted $E^{\scriptsize \mbox{com}}_p$, represents the
675 energy consumption spent by all the nodes for wireless communications during
676 period $p$. $E^{\scriptsize \mbox{list}}_p$, the next factor, corresponds to
677 the energy consumed by the sensors in LISTENING status before receiving the
678 decision to go active or sleep in period $p$. $E^{\scriptsize \mbox{comp}}_p$
679 refers to the energy needed by all the leader nodes to solve the integer
680 program during a period (COMPUTATION status). Finally, $E^a_{p}$ and
681 $E^s_{p}$ indicate the energy consumed by the WSN during the sensing phase
682 ({\it active} and {\it sleeping} nodes).
685 \subsection{Simulation Results}
688 The PeCO protocol has been implemented in OMNeT++~\citep{varga} simulator in order to assess and analyze its performance.
689 The simulations were run on a DELL laptop with an Intel Core~i3~2370~M (1.8~GHz)
690 processor (2 cores) whose MIPS (Million Instructions Per Second) rate is equal
691 to 35330. To be consistent with the use of a sensor node based on Atmels AVR
692 ATmega103L microcontroller (6~MHz) having a MIPS rate equal to 6, the original
693 execution time on the laptop is multiplied by 2944.2 $\left(\frac{35330}{2}
694 \times \frac{1}{6} \right)$. Energy consumption is calculated according to the
695 power consumption values, in milliWatt per second, given in Table~\ref{tab:EC},
696 based on the energy model proposed in \citep{ChinhVu}.
700 \caption{Power consumption values}
702 \begin{tabular}{|l||cccc|}
704 {\bf Sensor status} & MCU & Radio & Sensing & {\it Power (mW)} \\
706 LISTENING & On & On & On & 20.05 \\
707 ACTIVE & On & Off & On & 9.72 \\
708 SLEEP & Off & Off & Off & 0.02 \\
709 COMPUTATION & On & On & On & 26.83 \\
711 \multicolumn{4}{|l}{Energy needed to send or receive a 2-bit content message} & 0.515 \\
716 The modeling language for Mathematical Programming (AMPL)~\citep{AMPL} is used
717 to generate the integer program instance in a standard format, which is then
718 read and solved by the optimization solver GLPK (GNU linear Programming Kit
719 available in the public domain) \citep{glpk} through a Branch-and-Bound method.
720 In practice, executing GLPK on a sensor node is obviously intractable due to the
721 huge memory use. Fortunately, to solve the optimization problem, the use of
722 commercial solvers like CPLEX \citep{iamigo:cplex} which are less memory
723 consuming and more efficient is possible, or a lightweight heuristic may be implemented. For example,
724 for a WSN of 200 sensor nodes, a leader node has to deal with constraints
725 induced by about 12 sensor nodes. In that case, to solve the optimization
726 problem a memory consumption of more than 1~MB can be observed with GLPK,
727 whereas less than 300~KB would be needed with CPLEX.
729 Besides PeCO, three other protocols will be evaluated for comparison
730 purposes. The first one, called DESK, is a fully distributed coverage algorithm
731 proposed by \citep{ChinhVu}. The second one, called
732 GAF~\citep{xu2001geography}, consists in dividing the monitoring area into fixed
733 squares. Then, during the decision phase, in each square, one sensor is chosen
734 to remain active during the sensing phase. The last one, the DiLCO
735 protocol~\citep{Idrees2}, is an improved version of a research work presented
736 in~\citep{idrees2014coverage}. PeCO and DiLCO protocols
737 are based on the same framework. In particular, the choice for the simulations
738 of a partitioning in 16~subregions was made because it corresponds to the
739 configuration producing the best results for DiLCO. Of course, this number of
740 subregions should be adapted according to the size of the area of interest and
741 the number of sensors. The protocols are distinguished from one another by the
742 formulation of the integer program providing the set of sensors which have to be
743 activated in each sensing phase. The DiLCO protocol tries to satisfy the
744 coverage of a set of primary points, whereas the objective of the PeCO protocol
745 is to reach a desired level of coverage for each sensor perimeter. In the
746 experimentations, a level of coverage equal to one ($l=1$) is chosen
749 \subsubsection{Coverage Ratio}
751 Figure~\ref{figure5} shows the average coverage ratio for 200 deployed nodes
752 obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better
753 coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, compared to the
754 98.76\% produced by PeCO for the first periods. This is due to the fact that at
755 the beginning the DiLCO and PeCO protocols put more redundant sensors to sleep
756 status (which slightly decreases the coverage ratio), while the two other
757 protocols activate more sensor nodes. Later, when the number of periods is
758 beyond~70, it clearly appears that PeCO provides a better coverage ratio and
759 keeps a coverage ratio greater than 50\% for longer periods (15 more compared to
760 DiLCO, 40 more compared to DESK). The energy saved by PeCO in the early periods
761 allows later a substantial increase of the coverage performance.
766 \includegraphics[scale=0.5] {figure5.eps}
767 \caption{Coverage ratio for 200 deployed nodes.}
771 \subsubsection{Active Sensors Ratio}
773 Minimizing the number of active sensor nodes in each period is essential to minimize the
774 energy consumption and thus to maximize the network lifetime.
775 Figure~\ref{figure6} shows the average active nodes ratio for 200 deployed
776 nodes. DESK and GAF have 30.36~\% and 34.96~\% active nodes for
777 the first fourteen rounds, and the DiLCO and PeCO protocols compete perfectly with
778 only 17.92~\% and 20.16~\% active nodes during the same time interval. As the
779 number of periods increases, the PeCO protocol has a lower number of active nodes in
780 comparison with the three other approaches and exhibits a slow decrease, while
781 keeping a greater coverage ratio as shown in Figure \ref{figure5}.
785 \includegraphics[scale=0.5]{figure6.eps}
786 \caption{Active sensors ratio for 200 deployed nodes.}
790 \subsubsection{Energy Saving Ratio}
793 The simulation results show that the protocol PeCO saves
794 efficiently energy by turning off some sensors during the sensing phase. As
795 shown in Figure~\ref{figure7}, GAF provides better energy saving than PeCO for
796 the first fifty rounds. Indeed GAF balances the energy consumption among
797 sensor nodes inside each small fixed grid and thus permits to extend the life
798 of sensors in each grid fairly. However, at the same time it turns on a large
799 number of sensors and that leads later to quickly deplete sensor's batteries.
800 DESK algorithm shows less energy saving compared with other approaches. In
801 comparison with PeCO, DiLCO protocol usually provides lower energy saving
802 ratios. Moreover, it can be noticed that after round fifty, PeCO protocol
803 exhibits the slowest decrease among all the considered protocols.
807 % \begin{multicols}{6}
809 \includegraphics[scale=0.5]{figure7.eps} %\\~ ~ ~(a)
810 \caption{Energy Saving Ratio for 200 deployed nodes.}
814 \subsubsection{Energy Consumption}
816 The effect of the energy consumed by the WSN during the communication,
817 computation, listening, active, and sleep status is studied for different
818 network densities and the four approaches compared. Figures~\ref{figure8}(a)
819 and (b) illustrate the energy consumption for different network sizes and for
820 $Lifetime_{95}$ and $Lifetime_{50}$. The results show that the PeCO protocol is the most
821 competitive from the energy consumption point of view. As shown by both figures,
822 PeCO consumes much less energy than the other methods. One might think that the
823 resolution of the integer program is too costly in energy, but the results show
824 that it is very beneficial to lose a bit of time in the selection of sensors to
825 activate. Indeed the optimization program allows to reduce significantly the
826 number of active sensors and also the energy consumption while keeping a good
827 coverage level. The energy overhead when increasing network
828 size is the lowest with PeCO.
832 \begin{tabular}{@{}cr@{}}
833 \includegraphics[scale=0.5]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\
834 \includegraphics[scale=0.5]{figure8b.eps} & \raisebox{2.75cm}{(b)}
836 \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.}
840 \subsubsection{Network Lifetime}
842 In comparison with the two other approaches, PeCO and DiLCO protocols are better for prolonging the network lifetime. In
843 Figures~\ref{figure9}(a) and (b), $Lifetime_{95}$ and $Lifetime_{50}$ are shown for
844 different network sizes. As can be seen in these figures, the lifetime
845 increases with the size of the network, and it is clearly larger for the DiLCO and
846 PeCO protocols. For instance, for a network of 300~sensors and coverage ratio
847 greater than 50\%, it can be observed on Figure~\ref{figure9}(b) that the lifetime is
848 about twice longer with PeCO compared to the DESK protocol. The performance
849 difference is more obvious in Figure~\ref{figure9}(b) than in
850 Figure~\ref{figure9}(a) because the gain induced by protocols (PeCO and DiLCO) increases with
851 time, and the lifetime with a coverage over 50\% is far longer than with 95\%.
855 \begin{tabular}{@{}cr@{}}
856 \includegraphics[scale=0.5]{figure9a.eps} & \raisebox{2.75cm}{(a)} \\
857 \includegraphics[scale=0.5]{figure9b.eps} & \raisebox{2.75cm}{(b)}
859 \caption{Network Lifetime for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.}
863 Figure~\ref{figure10} compares the lifetime coverage of the DiLCO and PeCO protocols
864 for different coverage ratios. Protocol/70, Protocol/80,
865 Protocol/85, Protocol/90, and Protocol/95 correspond to the amount of time during which the
866 network can satisfy an area coverage greater than $70\%$, $80\%$, $85\%$,
867 $90\%$, and $95\%$ respectively, where the term Protocol refers to DiLCO or
868 PeCO. Indeed there are applications that do not require a 100\% coverage of the
869 area to be monitored. For example, forest
870 fire application might require complete coverage
871 in summer seasons while only require 80$\%$ of the area to be covered in rainy seasons~\citep{li2011transforming}. As another example, birds habit study requires only 70$\%$-coverage at nighttime when the birds are sleeping while requires 100$\%$-coverage at daytime when the birds are active~\citep{1279193}.
872 PeCO always outperforms DiLCO for the three lower coverage ratios, moreover the
873 improvements grow with the network size. DiLCO outperforms PeCO when the coverage ratio is required to be $>90\%$, but PeCO extends the network lifetime significantly when coverage ratio can be relaxed.
876 \centering \includegraphics[scale=0.55]{figure10.eps}
877 \caption{Network lifetime for different coverage ratios.}
881 \subsubsection{Impact of $\alpha$ and $\beta$ on PeCO's performance}
884 Table~\ref{my-labelx} shows network lifetime results for different values of
885 $\alpha$ and $\beta$, and a network size equal to 200 sensor nodes. On the one
886 hand, the choice of $\beta \gg \alpha$ prevents the overcoverage, and also
887 limits the activation of a large number of sensors, but as $\alpha$ is low, some
888 areas may be poorly covered. This explains the results obtained for
889 $Lifetime_{50}$ with $\beta \gg \alpha$: a large number of periods with low
890 coverage ratio. On the other hand, when $\alpha \gg \beta$ is chosen,
891 the coverage is favored even if some areas may be overcovered, so a high coverage ratio is
892 reached, but a large number of sensors are activated to achieve this goal.
893 Therefore the network lifetime is reduced. The choice $\alpha=0.6$ and
894 $\beta=0.4$ seems to achieve the best compromise between lifetime and coverage
895 ratio. That explains why this setting has been chosen for the experiments
896 presented in the previous subsections.
902 \caption{The impact of $\alpha$ and $\beta$ on PeCO's performance}
904 \begin{tabular}{|c|c|c|c|}
906 $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
907 0.0 & 1.0 & 151 & 0 \\ \hline
908 0.1 & 0.9 & 145 & 0 \\ \hline
909 0.2 & 0.8 & 140 & 0 \\ \hline
910 0.3 & 0.7 & 134 & 0 \\ \hline
911 0.4 & 0.6 & 125 & 0 \\ \hline
912 0.5 & 0.5 & 118 & 30 \\ \hline
913 {\bf 0.6} & {\bf 0.4} & {\bf 94} & {\bf 57} \\ \hline
914 0.7 & 0.3 & 97 & 49 \\ \hline
915 0.8 & 0.2 & 90 & 52 \\ \hline
916 0.9 & 0.1 & 77 & 50 \\ \hline
917 1.0 & 0.0 & 60 & 44 \\ \hline
922 \section{Conclusion and Future Works}
923 \label{sec:Conclusion and Future Works}
925 In this paper the problem of perimeter coverage optimization in
926 WSNs has been studied. A new protocol called Perimeter-based Coverage
927 Optimization is designed. This protocol schedules nodes' activities (wake up and sleep stages) with
928 the objective of maintaining a good coverage ratio while maximizing the network
929 lifetime. This protocol is applied in a distributed way in regular subregions
930 obtained after partitioning the area of interest in a preliminary step. It works
931 in periods and is based on the resolution of an integer program to select the
932 subset of sensors operating in active status for each period. This work is
933 original in so far as it proposes for the first time an integer program
934 scheduling the activation of sensors based on their perimeter coverage level,
935 instead of using a set of targets/points to be covered. Several simulations have
936 been carried out to evaluate the proposed protocol. The simulation results show
937 that PeCO is more energy-efficient than other approaches, with respect to
938 lifetime, coverage ratio, active sensors ratio, and energy consumption.
940 This framework will be extented so that the schedules are planned for multiple
941 sensing periods. The integer program would be improved to take into
942 account heterogeneous sensors from both energy and node characteristics point of
943 views. Finally, it would be interesting to implement the PeCO protocol using a
944 sensor-testbed to evaluate it in real world applications.
946 \subsection*{Acknowledgments}
947 The authors are deeply grateful to the anonymous reviewers for their
948 constructive advice, which improved the technical quality of the paper. As a
949 Ph.D. student, Ali Kadhum Idrees would like to gratefully acknowledge the
950 University of Babylon - Iraq for financial support and Campus France for the
951 received support. This work is also partially funded by the Labex ACTION program
952 (contract ANR-11-LABX-01-01).
954 \bibliographystyle{gENO}
955 \bibliography{biblio} %articleeo
