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