]> AND Private Git Repository - LiCO.git/blob - PeCO-EO/articleeo.tex~
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
96b4465cc70683363758f94036cda1a65c9a3c78
[LiCO.git] / PeCO-EO / articleeo.tex~
1 % gENOguide.tex
2 % v4.0 released April 2013
3
4 \documentclass{gENO2e}
5 %\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
6 %\renewcommand{\algorithmcfname}{ALGORITHM}
7 \usepackage{indentfirst}
8 \begin{document}
9
10 %\jvol{00} \jnum{00} \jyear{2013} \jmonth{April}
11
12 %\articletype{GUIDE}
13
14 \title{{\itshape Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}}
15
16 \author{Ali Kadhum Idrees$^{a}$, Karine Deschinkel$^{a}$$^{\ast}$\thanks{$^\ast$Corresponding author. Email: karine.deschinkel@univ-fcomte.fr}, Michel Salomon$^{a}$ and Rapha\"el Couturier $^{a}$
17 $^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte,
18           Belfort, France}};}
19
20
21 \maketitle
22
23 \begin{abstract}
24 The most important problem in a Wireless Sensor Network (WSN) is to optimize the
25 use of its limited energy provision, so that it can fulfill its monitoring task
26 as long as  possible. Among  known  available approaches  that can  be used  to
27 improve  power  management,  lifetime coverage  optimization  provides  activity
28 scheduling which ensures sensing coverage while minimizing the energy cost. We propose such an approach called Perimeter-based Coverage Optimization
29 protocol (PeCO). 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.
32 The novelty of our approach lies essentially in the formulation of a new
33 mathematical optimization  model based on the  perimeter coverage level  to schedule
34 sensors' activities.  Extensive simulation experiments demonstrate that PeCO  can
35 offer longer lifetime coverage for WSNs in comparison with some other protocols.
36
37 \begin{keywords}Wireless Sensor Networks, Area Coverage, Energy efficiency, Optimization, Scheduling.
38 \end{keywords}
39
40 \end{abstract}
41
42
43 \section{Introduction}
44 \label{sec:introduction}
45
46 The continuous progress in Micro Electro-Mechanical Systems (MEMS) and
47 wireless communication hardware  has given rise to the opportunity  to use large
48 networks    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 made  it suitable for a wide
54 range of application  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 receiving.
60
61 The energy needed  by an active sensor node to  perform sensing, processing, and
62 communication is supplied 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 it in  most applications. Therefore it is necessary  to deploy WSN with
65 high density in order to increase  reliability and to exploit node redundancy
66 thanks to energy-efficient activity  scheduling approaches.  Indeed, the overlap
67 of sensing  areas can be exploited  to schedule alternatively some  sensors in a
68 low power sleep mode and thus save  energy. Overall, the main question that must
69 be answered is: how to extend the lifetime coverage of a WSN as long as possible
70 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}.\\\\
73 This paper makes the following contributions.
74 \begin{enumerate}
75 \item We have devised a framework to schedule nodes to be activated alternatively such
76   that the network lifetime is prolonged  while ensuring that a certain level of
77   coverage is preserved.  A key idea in  our framework is to exploit spatial and
78   temporal subdivision.   On the one hand,  the area of interest  is divided into
79   several smaller subregions and, on the other hand, the time line is divided into
80   periods of equal length. In each subregion the sensor nodes will cooperatively
81   choose a  leader which will schedule  nodes' activities, and this  grouping of
82   sensors is similar to typical cluster architecture.
83 \item We have proposed a new mathematical  optimization model.  Instead of  trying to
84   cover a set of specified points/targets as  in most of the methods proposed in
85   the literature, we formulate an integer program based on perimeter coverage of
86   each sensor.  The  model involves integer variables to  capture the deviations
87   between  the actual  level of  coverage and  the required  level.  Hence, an
88   optimal schedule  will be  obtained by  minimizing a  weighted sum  of these
89   deviations.
90 \item We have conducted extensive simulation  experiments, using the  discrete event
91   simulator OMNeT++, to demonstrate the  efficiency of our protocol. We have compared
92   our   PeCO   protocol   to   two   approaches   found   in   the   literature:
93   DESK~\citep{ChinhVu} and  GAF~\citep{xu2001geography}, and also to  our previous
94   work published in~\citep{Idrees2} which is  based on another optimization model
95   for sensor scheduling.
96 \end{enumerate}
97
98
99
100
101
102
103 The rest  of the paper is  organized as follows.  In the next section
104 some related work in the  field is reviewed. Section~\ref{sec:The PeCO Protocol Description}
105 is devoted to the PeCO protocol  description and Section~\ref{cp} focuses on the
106 coverage model  formulation which is used  to schedule the activation  of sensor
107 nodes.  Section~\ref{sec:Simulation  Results and Analysis}  presents simulations
108 results and discusses the comparison  with other approaches. Finally, concluding
109 remarks   are  drawn   and  some   suggestions are  given  for   future  works   in
110 Section~\ref{sec:Conclusion and Future Works}.
111
112 \section{Related Literature}
113 \label{sec:Literature Review}
114
115 In  this section, some  related works  regarding  the
116 coverage problem is summarized, and specific aspects of the PeCO protocol from the  works presented in
117 the literature are presented.
118
119 The most  discussed coverage problems in  literature can be classified  in three
120 categories~\citep{li2013survey}   according   to  their   respective   monitoring
121 objective.  Hence,  area coverage \citep{Misra}  means that every point  inside a
122 fixed area  must be monitored, while  target coverage~\citep{yang2014novel} refers
123 to  the objective  of coverage  for a  finite number  of discrete  points called
124 targets,  and  barrier coverage~\citep{HeShibo,kim2013maximum}  focuses  on
125 preventing  intruders   from  entering   into  the   region  of   interest.   In
126 \citep{Deng2012}  authors  transform the  area  coverage  problem into  the  target
127 coverage one taking into account the  intersection points among disks of sensors
128 nodes    or   between    disk   of    sensor   nodes    and   boundaries.     In
129 \citep{Huang:2003:CPW:941350.941367}  authors prove  that  if  the perimeters  of
130 sensors are sufficiently  covered it will be  the case for the  whole area. They
131 provide an algorithm in $O(nd~log~d)$  time to compute the perimeter-coverage of
132 each  sensor. $d$  denotes  the  maximum  number  of  sensors  that  are
133 neighbors  to  a  sensor, and  $n$  is  the  total  number of  sensors  in  the
134 network. {\it In PeCO protocol, instead  of determining the level of coverage of
135   a set  of discrete  points, our  optimization model is  based on  checking the
136   perimeter-coverage of each sensor to activate a minimal number of sensors.}
137
138 The major  approach to extend network  lifetime while preserving coverage  is to
139 divide/organize the  sensors into a suitable  number of set covers  (disjoint or
140 non-disjoint)\citep{wang2011coverage}, where  each set completely  covers a  region of interest,  and to
141 activate these set  covers successively. The network activity can  be planned in
142 advance and scheduled  for the entire network lifetime or  organized in periods,
143 and the set  of active sensor nodes  is decided at the beginning  of each period
144 \citep{ling2009energy}.  Active node selection is determined based on the problem
145 requirements (e.g.   area monitoring,  connectivity, or power  efficiency).  For
146 instance, \citet{jaggi2006}  address the problem of maximizing
147 the lifetime  by dividing sensors  into the  maximum number of  disjoint subsets
148 such  that each  subset  can ensure  both coverage  and  connectivity. A  greedy
149 algorithm  is applied  once to  solve  this problem  and the  computed sets  are
150 activated  in   succession  to  achieve   the  desired  network   lifetime.   
151 \citet{chin2007},  \citet{yan2008design}, \citet{pc10},  propose  algorithms
152 working in a periodic fashion where a  cover set is computed at the beginning of
153 each period.   {\it Motivated by  these works,  PeCO protocol works  in periods,
154   where each  period contains a  preliminary phase for information  exchange and
155   decisions, followed by a sensing phase where one cover set is in charge of the
156   sensing task.}
157
158 Various centralized  and distributed approaches, or  even a mixing  of these two
159 concepts, have  been proposed  to extend the  network lifetime \citep{zhou2009variable}.   In distributed algorithms~\citep{Tian02,yangnovel,ChinhVu,qu2013distributed} each sensor decides of its
160 own activity scheduling  after an information exchange with  its neighbors.  The
161 main interest of such an approach is to avoid long range communications and thus
162 to reduce the energy dedicated to the communications.  Unfortunately, since each
163 node has only information on  its immediate neighbors (usually the one-hop ones)
164 it may make a bad decision leading to a global suboptimal solution.  Conversely,
165 centralized
166 algorithms~\citep{cardei2005improving,zorbas2010solving,pujari2011high}     always
167 provide nearly  or close to  optimal solution since  the algorithm has  a global
168 view of the whole network. The disadvantage of a centralized method is obviously
169 its high  cost in communications needed to  transmit to a single  node, the base
170 station which will globally schedule  nodes' activities, and data from all the other
171 sensor nodes  in the area.  The price  in communications can be  huge since
172 long range  communications will be  needed. In fact  the larger the WNS  is, the
173 higher the  communication and  thus the energy  cost are.   {\it In order  to be
174   suitable for large-scale  networks, in the PeCO protocol,  the area of interest
175   is divided into several smaller subregions, and in each one, a node called the
176   leader  is  in  charge  of  selecting  the active  sensors  for  the  current
177   period.  Thus our  protocol is  scalable  and is a  globally distributed  method,
178   whereas it is centralized in each subregion.}
179
180 Various  coverage scheduling  algorithms have  been developed  these past few years.
181 Many of  them, dealing with  the maximization of the  number of cover  sets, are
182 heuristics.   These  heuristics involve  the  construction  of  a cover  set  by
183 including in priority the sensor nodes  which cover critical targets, that is to
184 say   targets   that  are   covered   by   the   smallest  number   of   sensors
185 \citep{berman04,zorbas2010solving}.  Other  approaches are based  on mathematical
186 programming formulations~\citep{cardei2005energy,5714480,pujari2011high,Yang2014}
187 and dedicated techniques (solving with a branch-and-bound algorithm available in
188 optimization  solver).  The  problem is  formulated as  an optimization  problem
189 (maximization of the lifetime or number of cover sets) under target coverage and
190 energy  constraints.   Column  generation   techniques,  well-known  and  widely
191 practiced techniques for  solving linear programs with too  many variables, have
192 also                                                                        been
193 used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012column}. {\it  In the PeCO
194   protocol, each  leader, in charge  of a  subregion, solves an  integer program
195   which has a twofold objective: minimize the overcoverage and the undercoverage
196   of the perimeter of each sensor.}
197
198
199
200 The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage Optimization (DiLCO) protocol, maintains the coverage and improves the lifetime in WSNs. It is  an improved version
201 of a research work they presented in~\citep{idrees2014coverage}.  First, they partition the area of interest into subregions using a divide-and-conquer method. DiLCO protocol is then distributed on the sensor nodes in each subregion in a second step. DiLCO protocol combines two techniques: a leader election in each subregion, followed by an optimization-based node activity scheduling performed by each elected leader. The proposed DiLCO protocol is a periodic protocol where each period is decomposed into 4 phases: information exchange, leader election, decision, and sensing. The simulations show that DiLCO is able to increase the WSN lifetime and provides improved coverage performance. {\it  In the PeCO
202   protocol, We have proposed a new mathematical optimization model. Instead of trying to
203 cover a set of specified points/targets as in DiLCO protocol, we formulate an integer program based
204 on perimeter coverage of each sensor. The model involves integer variables to capture the deviations between the actual level of coverage and the required level. The idea is that an optimal scheduling will be obtained by minimizing a weighted sum of these deviations.}
205   
206   
207   
208
209 \section{ The P{\scshape e}CO Protocol Description}
210 \label{sec:The PeCO Protocol Description}
211
212 In  this  section,  the Perimeter-based  Coverage
213 Optimization protocol is decribed in details.  First we present the  assumptions we made and the models
214 we considered (in particular the perimeter coverage one), second we describe the
215 background idea of our protocol, and third  we give the outline of the algorithm
216 executed by each node.
217
218
219 \subsection{Assumptions and Models}
220 \label{CI}
221
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.  We  assume that all the  sensor nodes are homogeneous  in terms of
226 communication,  sensing,  and  processing capabilities  and  heterogeneous  from
227 the 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. We consider a Boolean disk coverage model,
230 which is the most  widely used sensor coverage model in  the literature, and all
231 sensor nodes  have a constant sensing  range $R_s$.  Thus, all  the space points
232 within a disk centered at a sensor with  a radius equal to the sensing range are
233 said to be covered  by this sensor. We also assume  that the communication range
234 $R_c$ satisfies $R_c  \geq 2 \cdot R_s$. In fact,  \citet{Zhang05}
235 proved  that if  the  transmission  range fulfills  the  previous hypothesis,  the
236 complete coverage of a convex area implies connectivity among active nodes.
237
238 The PeCO protocol  uses the  same perimeter-coverage  model as \citet{huang2005coverage}. It  can be expressed as follows:  a sensor is
239 said to be perimeter  covered if all the points on its  perimeter are covered by
240 at least  one sensor  other than  itself. Authors \citet{huang2005coverage}  proved that  a network  area is
241 $k$-covered (every point in the area covered by at least k sensors) if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors). 
242  
243 Figure~\ref{figure1}(a)  shows  the coverage  of  sensor  node~$0$. On  this
244 figure, sensor~$0$ has  nine neighbors and we  have reported on
245 its  perimeter (the  perimeter  of the  disk  covered by  the  sensor) for  each
246 neighbor  the  two  points  resulting  from the intersection  of  the  two  sensing
247 areas. These points are denoted for  neighbor~$i$ by $iL$ and $iR$, respectively
248 for  left and  right from  a neighboing  point of  view.  The  resulting couples  of
249 intersection points subdivide  the perimeter of sensor~$0$  into portions called
250 arcs.
251
252 \begin{figure}[ht!]
253   \centering
254   \begin{tabular}{@{}cr@{}}
255     \includegraphics[width=75mm]{figure1a.eps} & \raisebox{3.25cm}{(a)} \\
256     \includegraphics[width=75mm]{figure1b.eps} & \raisebox{2.75cm}{(b)}
257   \end{tabular}
258   \caption{(a) Perimeter  coverage of sensor node  0 and (b) finding  the arc of
259     $u$'s perimeter covered by $v$.}
260   \label{figure1}
261 \end{figure} 
262
263 Figure~\ref{figure1}(b) describes the geometric information used to find the
264 locations of the  left and right points of  an arc on the perimeter  of a sensor
265 node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the
266 west  side of  sensor~$u$,  with  the following  respective  coordinates in  the
267 sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates 
268 the euclidean distance between nodes~$u$ and $v$ is computed: $Dist(u,v)=\sqrt{\vert
269   u_x  - v_x  \vert^2 +  \vert u_y-v_y  \vert^2}$, while  the angle~$\alpha$  is
270 obtained through  the formula:
271  \[
272 \alpha =  \arccos \left(\frac{Dist(u,v)}{2R_s}
273 \right).
274 \] 
275 The arc on the perimeter of~$u$ defined by the angular interval $[\pi
276   - \alpha,\pi + \alpha]$ is said to be perimeter-covered by sensor~$v$.
277
278 Every couple of intersection points is placed on the angular interval $[0,2\pi)$
279 in  a  counterclockwise manner,  leading  to  a  partitioning of  the  interval.
280 Figure~\ref{figure1}(a)  illustrates  the arcs  for  the  nine neighbors  of
281 sensor $0$ and  Figure~\ref{figure2} gives the position of  the corresponding arcs
282 in  the interval  $[0,2\pi)$. More  precisely, the  points are
283 ordered according  to the  measures of  the angles  defined by  their respective
284 positions. The intersection points are  then visited one after another, starting
285 from the first  intersection point  after  point~zero,  and  the maximum  level  of
286 coverage is determined  for each interval defined by two  successive points. The
287 maximum  level of  coverage is  equal to  the number  of overlapping  arcs.  For
288 example, 
289 between~$5L$  and~$6L$ the maximum  level of  coverage is equal  to $3$
290 (the value is highlighted in yellow  at the bottom of Figure~\ref{figure2}), which
291 means that at most 2~neighbors can cover  the perimeter in addition to node $0$. 
292 Table~\ref{my-label} summarizes for each coverage  interval the maximum level of
293 coverage and  the sensor  nodes covering the  perimeter.  The  example discussed
294 above is thus given by the sixth line of the table.
295
296
297 \begin{figure*}[t!]
298 \centering
299 \includegraphics[width=127.5mm]{figure2.eps}  
300 \caption{Maximum coverage levels for perimeter of sensor node $0$.}
301 \label{figure2}
302 \end{figure*} 
303
304
305
306
307  \begin{table}
308  \tbl{Coverage intervals and contributing sensors for sensor node 0 \label{my-label}}
309 {\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
310 \hline
311 \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
312 0.0291    & 1L                                                                        & 2L                                                        & 4                                                                     & 0                     & 1                     & 3                    & 4                    &                      \\ \hline
313 0.104     & 2L                                                                        & 3R                                                        & 5                                                                     & 0                     & 1                     & 3                    & 4                    & 2                    \\ \hline
314 0.3168    & 3R                                                                        & 4R                                                        & 4                                                                     & 0                     & 1                     & 4                    & 2                    &                      \\ \hline
315 0.6752    & 4R                                                                        & 1R                                                        & 3                                                                     & 0                     & 1                     & 2                    &                      &                      \\ \hline
316 1.8127    & 1R                                                                        & 5L                                                        & 2                                                                     & 0                     & 2                     &                      &                      &                      \\ \hline
317 1.9228    & 5L                                                                        & 6L                                                        & 3                                                                     & 0                     & 2                     & 5                    &                      &                      \\ \hline
318 2.3959    & 6L                                                                        & 2R                                                        & 4                                                                     & 0                     & 2                     & 5                    & 6                    &                      \\ \hline
319 2.4258    & 2R                                                                        & 7L                                                        & 3                                                                     & 0                     & 5                     & 6                    &                      &                      \\ \hline
320 2.7868    & 7L                                                                        & 8L                                                        & 4                                                                     & 0                     & 5                     & 6                    & 7                    &                      \\ \hline
321 2.8358    & 8L                                                                        & 5R                                                        & 5                                                                     & 0                     & 5                     & 6                    & 7                    & 8                    \\ \hline
322 2.9184    & 5R                                                                        & 7R                                                        & 4                                                                     & 0                     & 6                     & 7                    & 8                    &                      \\ \hline
323 3.3301    & 7R                                                                        & 9R                                                        & 3                                                                     & 0                     & 6                     & 8                    &                      &                      \\ \hline
324 3.9464    & 9R                                                                        & 6R                                                        & 4                                                                     & 0                     & 6                     & 8                    & 9                    &                      \\ \hline
325 4.767     & 6R                                                                        & 3L                                                        & 3                                                                     & 0                     & 8                     & 9                    &                      &                      \\ \hline
326 4.8425    & 3L                                                                        & 8R                                                        & 4                                                                     & 0                     & 3                     & 8                    & 9                    &                      \\ \hline
327 4.9072    & 8R                                                                        & 4L                                                        & 3                                                                     & 0                     & 3                     & 9                    &                      &                      \\ \hline
328 5.3804    & 4L                                                                        & 9R                                                        & 4                                                                     & 0                     & 3                     & 4                    & 9                    &                      \\ \hline
329 5.9157    & 9R                                                                        & 1L                                                        & 3                                                                     & 0                     & 3                     & 4                    &                      &                      \\ \hline
330 \end{tabular}}
331
332
333 \end{table}
334
335
336
337
338 In the PeCO  protocol, the scheduling of the sensor  nodes' activities is formulated  with an
339 integer program  based on  coverage intervals. The  formulation of  the coverage
340 optimization problem is  detailed in~Section~\ref{cp}.  Note that  when a sensor
341 node  has a  part of  its sensing  range outside  the WSN  sensing field,  as in
342 Figure~\ref{figure3}, the maximum coverage level for  this arc is set to $\infty$
343 and  the  corresponding  interval  will  not   be  taken  into  account  by  the
344 optimization algorithm.
345
346  \newpage
347 \begin{figure}[h!]
348 \centering
349 \includegraphics[width=62.5mm]{figure3.eps}  
350 \caption{Sensing range outside the WSN's area of interest.}
351 \label{figure3}
352 \end{figure} 
353
354
355 \subsection{The Main Idea}
356
357 The  WSN area of  interest is, in a  first step, divided  into regular
358 homogeneous subregions  using a divide-and-conquer  algorithm. In a  second step
359 our  protocol  will  be  executed  in   a  distributed  way  in  each  subregion
360 simultaneously to schedule nodes' activities for one sensing period.
361
362 As  shown in  Figure~\ref{figure4}, node  activity  scheduling is  produced by  our
363 protocol in a periodic manner. Each period is divided into 4 stages: Information
364 (INFO)  Exchange,  Leader Election,  Decision  (the  result of  an  optimization
365 problem),  and  Sensing.   For  each  period there  is  exactly  one  set  cover
366 responsible for  the sensing task.  Protocols  based on a periodic  scheme, like
367 PeCO, are more  robust against an unexpected  node failure. On the  one hand, if
368 a node failure is discovered before  taking the decision, the corresponding sensor
369 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.
379
380 \begin{figure}[t!]
381 \centering
382 \includegraphics[width=80mm]{figure4.eps}  
383 \caption{PeCO protocol.}
384 \label{figure4}
385 \end{figure} 
386
387 We define two types of packets to be used by PeCO protocol:
388
389 \begin{itemize} 
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
394   sensing phase.
395 \end{itemize}
396
397
398 Five statuses are possible for a sensor node in the network:
399
400 \begin{itemize} 
401 \item LISTENING: waits for a decision (to be active or not);
402 \item COMPUTATION: executes the optimization algorithm as leader to
403   determine the activities scheduling;
404 \item ACTIVE: node is sensing;
405 \item SLEEP: node is turned off;
406 \item COMMUNICATION: transmits or receives packets.
407 \end{itemize}
408
409
410 \subsection{PeCO Protocol Algorithm}
411
412 The  pseudocode implementing the  protocol on  a node is  given below.
413 More  precisely,  Algorithm~\ref{alg:PeCO}  gives  a brief  description  of  the
414 protocol applied by a sensor node $s_k$ where $k$ is the node index in the WSN.
415
416
417
418 \begin{algorithm}      
419  % \KwIn{all the parameters related to information exchange}
420 %  \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)}
421 %  \BlankLine
422   %\emph{Initialize the sensor node and determine it's position and subregion} \; 
423   
424 \noindent{\bf If} $RE_k \geq E_{th}$ {\bf then}\\
425 \hspace*{0.6cm} \emph{$s_k.status$ = COMMUNICATION;}\\
426 \hspace*{0.6cm}  \emph{Send $INFO()$ packet to other nodes in subregion;}\\
427 \hspace*{0.6cm}  \emph{Wait $INFO()$ packet from other nodes in subregion;}\\
428 \hspace*{0.6cm} \emph{Update K.CurrentSize;}\\
429 \hspace*{0.6cm}  \emph{LeaderID = Leader election;}\\
430 \hspace*{0.6cm} {\bf If} $ s_k.ID = LeaderID $ {\bf then}\\
431 \hspace*{1.2cm}   \emph{$s_k.status$ = COMPUTATION;}\\
432 \hspace*{1.2cm}{\bf If} \emph{$ s_k.ID $ is Not previously selected as a Leader} {\bf then}\\
433 \hspace*{1.8cm} \emph{ Execute the perimeter coverage model;}\\
434 \hspace*{1.2cm} {\bf end}\\
435 \hspace*{1.2cm}{\bf If} \emph{($s_k.ID $ is the same Previous Leader)~And~(K.CurrentSize = K.PreviousSize)}\\
436 \hspace*{1.8cm} \emph{ Use the same previous cover set for current sensing stage;}\\
437 \hspace*{1.2cm}  {\bf end}\\
438 \hspace*{1.2cm}  {\bf else}\\
439 \hspace*{1.8cm}\emph{Update $a^j_{ik}$; prepare data for IP~Algorithm;}\\
440 \hspace*{1.8cm} \emph{$\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$);}\\
441 \hspace*{1.8cm} \emph{K.PreviousSize = K.CurrentSize;}\\
442 \hspace*{1.2cm}  {\bf end}\\
443 \hspace*{1.2cm}\emph{$s_k.status$ = COMMUNICATION;}\\
444 \hspace*{1.2cm}\emph{Send $ActiveSleep()$ to each node $l$ in subregion;}\\
445 \hspace*{1.2cm}\emph{Update $RE_k $;}\\
446 \hspace*{0.6cm}  {\bf end}\\
447 \hspace*{0.6cm}  {\bf else}\\
448 \hspace*{1.2cm}\emph{$s_k.status$ = LISTENING;}\\
449 \hspace*{1.2cm}\emph{Wait $ActiveSleep()$ packet from the Leader;}\\
450 \hspace*{1.2cm}\emph{Update $RE_k $;}\\
451 \hspace*{0.6cm}  {\bf end}\\
452 {\bf end}\\
453 {\bf else}\\
454 \hspace*{0.6cm} \emph{Exclude $s_k$ from entering in the current sensing stage;}\\
455 {\bf end}\\
456 \label{alg:PeCO}
457 \end{algorithm}
458
459
460
461 In this  algorithm, K.CurrentSize and K.PreviousSize  respectively represent the
462 current number and  the previous number of living nodes in  the subnetwork of the
463 subregion.  Initially, the sensor node checks its remaining energy $RE_k$, which
464 must be greater than a threshold $E_{th}$ in order to participate in the current
465 period.  Each  sensor node  determines its position  and its subregion  using an
466 embedded  GPS or a  location discovery  algorithm. After  that, all  the sensors
467 collect position coordinates,  remaining energy, sensor node ID,  and the number
468 of their  one-hop live  neighbors during the  information exchange.  The sensors
469 inside a same region cooperate to elect a leader. The selection criteria for the
470 leader, in order of priority,  are: larger numbers of neighbors, larger remaining
471 energy, and  then in case  of equality, larger  index.  Once chosen,  the leader
472 collects information to formulate and  solve the integer program which allows to
473 construct the set of active sensors in the sensing stage.
474
475
476 \section{Perimeter-based Coverage Problem Formulation}
477 \label{cp}
478
479 In this  section, the coverage model is  mathematically formulated. The following
480 notations are used  throughout the
481 section.\\
482 First, the following sets:
483 \begin{itemize}
484 \item $S$ represents the set of WSN sensor nodes;
485 \item $A \subseteq S $ is the subset of alive sensors;
486 \item  $I_j$  designates  the  set  of  coverage  intervals  (CI)  obtained  for
487   sensor~$j$.
488 \end{itemize}
489 $I_j$ refers to the set of  coverage intervals which have been defined according
490 to the  method introduced in  subsection~\ref{CI}. For a coverage  interval $i$,
491 let $a^j_{ik}$ denotes  the indicator function of whether  sensor~$k$ is involved
492 in coverage interval~$i$ of sensor~$j$, that is:
493 \begin{equation}
494 a^j_{ik} = \left \{ 
495 \begin{array}{lll}
496   1 & \mbox{if sensor $k$ is involved in the } \\
497         &       \mbox{coverage interval $i$ of sensor $j$}, \\
498   0 & \mbox{otherwise.}\\
499 \end{array} \right.
500 \end{equation}
501 Note that $a^k_{ik}=1$ by definition of the interval.
502
503 Second, several binary  and integer  variables are defined.  Hence,  each binary
504 variable $X_{k}$  determines the activation of  sensor $k$ in the  sensing phase
505 ($X_k=1$ if  the sensor $k$  is active or 0  otherwise).  $M^j_i$ is  an integer
506 variable  which  measures  the  undercoverage  for  the  coverage  interval  $i$
507 corresponding to  sensor~$j$. In  the same  way, the  overcoverage for  the same
508 coverage interval is given by the variable $V^j_i$.
509
510 If we decide to sustain a level of coverage equal to $l$ all along the perimeter
511 of sensor  $j$, we have  to ensure  that at least  $l$ sensors involved  in each
512 coverage  interval $i  \in I_j$  of  sensor $j$  are active.   According to  the
513 previous notations, the number of active sensors in the coverage interval $i$ of
514 sensor $j$  is given by  $\sum_{k \in A} a^j_{ik}  X_k$.  To extend  the network
515 lifetime,  the objective  is to  activate a  minimal number  of sensors  in each
516 period to  ensure the  desired coverage  level. As the  number of  alive sensors
517 decreases, it becomes impossible to reach  the desired level of coverage for all
518 coverage intervals. Therefore  variables  $M^j_i$ and $V^j_i$ are introduced as a measure
519 of the  deviation between  the desired  number of active  sensors in  a coverage
520 interval and  the effective  number. And  we try  to minimize  these deviations,
521 first to  force the  activation of  a minimal  number of  sensors to  ensure the
522 desired coverage level, and if the desired level cannot be completely satisfied,
523 to reach a coverage level as close as possible to the desired one.
524
525
526
527
528 Our coverage optimization problem can then be mathematically expressed as follows: 
529
530 \begin{equation} 
531 \left \{
532 \begin{array}{ll}
533 \min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\
534 \textrm{subject to :}&\\
535 \sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i  \geq l \quad \forall i \in I_j, \forall j \in S\\
536 \sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i  \leq l \quad \forall i \in I_j, \forall j \in S\\
537 X_{k} \in \{0,1\}, \forall k \in A
538 \end{array}
539 \right.
540 \end{equation}
541
542 $\alpha^j_i$ and $\beta^j_i$  are nonnegative weights selected  according to the
543 relative importance of satisfying the associated level of coverage. For example,
544 weights associated with  coverage intervals of a specified part  of a region may
545 be  given by a  relatively larger  magnitude than  weights associated  with another
546 region. This  kind of integer program  is inspired from the  model developed for
547 brachytherapy treatment planning  for optimizing dose  distribution
548 \citep{0031-9155-44-1-012}. The integer  program must be solved by  the leader in
549 each subregion at the beginning of  each sensing phase, whenever the environment
550 has  changed (new  leader,  death of  some  sensors). Note  that  the number  of
551 constraints in the model is constant  (constraints of coverage expressed for all
552 sensors), whereas the number of variables $X_k$ decreases over periods, since 
553 only alive  sensors (sensors with enough energy to  be alive during one
554 sensing phase) are considered in the model.
555
556 \section{Performance Evaluation and Analysis}  
557 \label{sec:Simulation Results and Analysis}
558
559
560 \subsection{Simulation Settings}
561
562
563 The WSN  area of interest is  supposed to be divided  into 16~regular subregions
564 and we use the same energy consumption model as in our previous work~\citep{Idrees2}.
565 Table~\ref{table3} gives the chosen parameters settings.
566
567 \begin{table}[ht]
568 \tbl{Relevant parameters for network initialization \label{table3}}{
569
570 \centering
571
572 \begin{tabular}{c|c}
573
574 \hline
575 Parameter & Value  \\ [0.5ex]
576    
577 \hline
578 % inserts single horizontal line
579 Sensing field & $(50 \times 25)~m^2 $   \\
580
581 WSN size &  100, 150, 200, 250, and 300~nodes   \\
582
583 Initial energy  & in range 500-700~Joules  \\  
584
585 Sensing period & duration of 60 minutes \\
586 $E_{th}$ & 36~Joules\\
587 $R_s$ & 5~m   \\     
588 $R_c$ & 10~m   \\   
589 $\alpha^j_i$ & 0.6   \\
590
591 $\beta^j_i$ & 0.4
592
593 \end{tabular}}
594
595
596 \end{table}
597 To  obtain  experimental  results  which are  relevant,  simulations  with  five
598 different node densities going from  100 to 300~nodes were performed considering
599 each time 25~randomly  generated networks. The nodes are deployed  on a field of
600 interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a
601 high coverage ratio. Each node has an  initial energy level, in Joules, which is
602 randomly drawn in the interval $[500-700]$.   If its energy provision reaches a
603 value below  the threshold $E_{th}=36$~Joules,  the minimum energy needed  for a
604 node  to stay  active during  one period,  it will  no longer  participate in  the
605 coverage task. This value corresponds to the energy needed by the sensing phase,
606 obtained by multiplying  the energy consumed in the active state  (9.72 mW) with the
607 time in  seconds for one  period (3600 seconds), and  adding the energy  for the
608 pre-sensing phases.  According  to the interval of initial energy,  a sensor may
609 be active during at most 20 periods.
610
611 The values  of $\alpha^j_i$ and  $\beta^j_i$ have been  chosen to ensure  a good
612 network coverage and a longer WSN lifetime.  Higher priority is given to
613 the  undercoverage  (by  setting  the  $\alpha^j_i$ with  a  larger  value  than
614 $\beta^j_i$)  so as  to prevent  the non-coverage  for the  interval~$i$ of  the
615 sensor~$j$.  On the  other hand,  
616 $\beta^j_i$ is assigned to a value which is slightly lower so as to minimize the number of active sensor nodes which contribute
617 in covering the interval.
618
619 The following performance metrics are used to evaluate the efficiency of the
620 approach.
621
622
623 \begin{itemize}
624 \item {\bf Network Lifetime}: the lifetime  is defined as the time elapsed until
625   the  coverage  ratio  falls  below a  fixed  threshold.   $Lifetime_{95}$  and
626   $Lifetime_{50}$  denote, respectively,  the  amount of  time  during which  is
627   guaranteed a  level of coverage  greater than $95\%$  and $50\%$. The  WSN can
628   fulfill the expected  monitoring task until all its nodes  have depleted their
629   energy or if the network is no  more connected. This last condition is crucial
630   because without  network connectivity a  sensor may not be  able to send  to a
631   base station an event it has sensed.
632 \item {\bf  Coverage Ratio (CR)} : it  measures how  well the  WSN is  able to
633   observe the area of interest. In our  case, the sensor field is discretized as
634   a regular grid, which yields the following equation:
635   
636
637 \[
638     \scriptsize
639     \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100
640 \]
641
642
643   where $n$  is the  number of covered  grid points by  active sensors  of every
644   subregions during  the current sensing phase  and $N$ is total  number of grid
645   points in  the sensing  field.  In  simulations  a  layout of
646   $N~=~51~\times~26~=~1326$~grid points is considered.
647 \item {\bf Active Sensors Ratio (ASR)}: a  major objective of our protocol is to
648   activate  as few nodes as possible,  in order  to minimize  the communication
649   overhead and maximize the WSN lifetime. The active sensors ratio is defined as
650   follows:
651  
652 \[
653     \scriptsize
654     \mbox{ASR}(\%) =  \frac{\sum\limits_{r=1}^R \mbox{$|A_r^p|$}}{\mbox{$|J|$}} \times 100
655 \]
656
657   where $|A_r^p|$ is  the number of active  sensors in the subregion  $r$ in the
658   current sensing period~$p$, $|J|$ is the number of sensors in the network, and
659   $R$ is the number of subregions.
660 \item {\bf Energy Consumption (EC)}: energy consumption can be seen as the total
661   energy  consumed by  the  sensors during  $Lifetime_{95}$ or  $Lifetime_{50}$,
662   divided by  the number of  periods. The value of  EC is computed  according to
663   this formula:
664
665 \[  
666   \scriptsize
667     \mbox{EC} = \frac{\sum\limits_{p=1}^{P} \left( E^{\mbox{com}}_p+E^{\mbox{list}}_p+E^{\mbox{comp}}_p  
668       + E^{a}_p+E^{s}_p \right)}{P},
669 \]
670  
671   where $P$ corresponds  to the number of periods. The  total energy consumed by
672   the  sensors  comes  through  taking   into  consideration  four  main  energy
673   factors. The first one, denoted $E^{\scriptsize \mbox{com}}_p$, represents the
674   energy consumption spent  by all the nodes for  wireless communications during
675   period $p$.  $E^{\scriptsize \mbox{list}}_p$,  the next factor, corresponds to
676   the energy  consumed by the sensors  in LISTENING status before  receiving the
677   decision to go active or sleep in period $p$.  $E^{\scriptsize \mbox{comp}}_p$
678   refers to  the energy  needed by  all the  leader nodes  to solve  the integer
679   program during a period.  Finally, $E^a_{p}$ and $E^s_{p}$ indicate the energy
680   consumed by the WSN during the sensing phase (active and sleeping nodes).
681 \end{itemize}
682
683
684 \subsection{Simulation Results}
685
686 In  order  to  assess and  analyze  the  performance  of  our protocol  we  have
687 implemented PeCO protocol in  OMNeT++~\citep{varga} simulator.  Besides PeCO, two
688 other  protocols,  described  in  the  next paragraph,  will  be  evaluated  for
689 comparison purposes.   The simulations were run  on a DELL laptop  with an Intel
690 Core~i3~2370~M (1.8~GHz)  processor (2  cores) whose MIPS  (Million Instructions
691 Per Second) rate  is equal to 35330. To  be consistent with the use  of a sensor
692 node based on  Atmels AVR ATmega103L microcontroller (6~MHz) having  a MIPS rate
693 equal to 6,  the original execution time  on the laptop is  multiplied by 2944.2
694 $\left(\frac{35330}{2} \times  \frac{1}{6} \right)$.  The modeling  language for
695 Mathematical Programming (AMPL)~\citep{AMPL} is  employed to generate the integer
696 program instance  in a  standard format, which  is then read  and solved  by the
697 optimization solver  GLPK (GNU  linear Programming Kit  available in  the public
698 domain) \citep{glpk} through a Branch-and-Bound method.
699
700 As said previously, the PeCO is  compared to three other approaches. The first
701 one,  called  DESK,  is  a  fully distributed  coverage  algorithm  proposed  by
702 \citep{ChinhVu}. The second one,  called GAF~\citep{xu2001geography}, consists in
703 dividing  the monitoring  area into  fixed  squares. Then,  during the  decision
704 phase, in each square, one sensor is  chosen to remain active during the sensing
705 phase. The last  one, the DiLCO protocol~\citep{Idrees2}, is  an improved version
706 of a research work we presented in~\citep{idrees2014coverage}. Let us notice that
707 PeCO and  DiLCO protocols are  based on the  same framework. In  particular, the
708 choice for the simulations of a partitioning in 16~subregions was made because
709 it corresponds to the configuration producing  the best results for DiLCO. The
710 protocols are distinguished  from one another by the formulation  of the integer
711 program providing the set of sensors which  have to be activated in each sensing
712 phase. DiLCO protocol tries to satisfy the coverage of a set of primary points,
713 whereas the PeCO protocol objective is to reach a desired level of coverage for each
714 sensor perimeter. In our experimentations, we chose a level of coverage equal to
715 one ($l=1$).
716
717 \subsubsection{\bf Coverage Ratio}
718
719 Figure~\ref{figure5}  shows the  average coverage  ratio for  200 deployed  nodes
720 obtained with the  four protocols. DESK, GAF, and DiLCO  provide a slightly better
721 coverage ratio with respectively 99.99\%,  99.91\%, and 99.02\%, compared to the 98.76\%
722 produced by  PeCO for the  first periods. This  is due to  the fact that  at the
723 beginning the DiLCO protocol  puts to  sleep status  more redundant  sensors (which
724 slightly decreases the coverage ratio), while the three other protocols activate
725 more sensor  nodes. Later, when the  number of periods is  beyond~70, it clearly
726 appears that  PeCO provides a better  coverage ratio and keeps  a coverage ratio
727 greater  than 50\%  for  longer periods  (15  more compared  to  DiLCO, 40  more
728 compared to DESK). The energy saved by  PeCO in the early periods allows later a
729 substantial increase of the coverage performance.
730
731 \parskip 0pt    
732 \begin{figure}[h!]
733 \centering
734  \includegraphics[scale=0.5] {figure5.eps} 
735 \caption{Coverage ratio for 200 deployed nodes.}
736 \label{figure5}
737 \end{figure} 
738
739
740
741
742 \subsubsection{\bf Active Sensors Ratio}
743
744 Having the less active sensor nodes in  each period is essential to minimize the
745 energy consumption  and thus to  maximize the network  lifetime.  Figure~\ref{figure6}
746 shows the  average active nodes ratio  for 200 deployed nodes.   We observe that
747 DESK and  GAF have 30.36  \% and  34.96 \% active  nodes for the  first fourteen
748 rounds and  DiLCO and PeCO  protocols compete perfectly  with only 17.92~\% and
749 20.16~\% active  nodes during the same  time interval. As the  number of periods
750 increases, PeCO protocol  has a lower number of active  nodes in comparison with
751 the three other approaches, while keeping a greater coverage ratio as shown in
752 Figure \ref{figure5}.
753
754 \begin{figure}[h!]
755 \centering
756 \includegraphics[scale=0.5]{figure6.eps}  
757 \caption{Active sensors ratio for 200 deployed nodes.}
758 \label{figure6}
759 \end{figure} 
760
761 \subsubsection{\bf Energy Consumption}
762
763 We studied the effect of the energy  consumed by the WSN during the communication,
764 computation, listening, active, and sleep status for different network densities
765 and  compared  it for  the  four  approaches.  Figures~\ref{figure7}(a)  and  (b)
766 illustrate  the  energy   consumption  for  different  network   sizes  and  for
767 $Lifetime95$ and  $Lifetime50$. The results show  that our PeCO protocol  is the
768 most competitive  from the energy  consumption point of  view. As shown  in both
769 figures, PeCO consumes much less energy than the three other methods.  One might
770 think that the  resolution of the integer  program is too costly  in energy, but
771 the  results show  that it  is very  beneficial to  lose a  bit of  time in  the
772 selection of  sensors to  activate.  Indeed the  optimization program  allows to
773 reduce significantly the number of active  sensors and so the energy consumption
774 while keeping a good coverage level.
775
776 \begin{figure}[h!]
777   \centering
778   \begin{tabular}{@{}cr@{}}
779     \includegraphics[scale=0.475]{figure7a.eps} & \raisebox{2.75cm}{(a)} \\
780     \includegraphics[scale=0.475]{figure7b.eps} & \raisebox{2.75cm}{(b)}
781   \end{tabular}
782   \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.}
783   \label{figure7}
784 \end{figure} 
785
786
787
788 \subsubsection{\bf Network Lifetime}
789
790 We observe the superiority of PeCO and DiLCO protocols in comparison with the
791 two    other   approaches    in    prolonging   the    network   lifetime.    In
792 Figures~\ref{figure8}(a)  and (b),  $Lifetime95$ and  $Lifetime50$ are  shown for
793 different  network  sizes.   As  highlighted  by  these  figures,  the  lifetime
794 increases with the size  of the network, and it is clearly   largest for DiLCO
795 and PeCO  protocols.  For instance,  for a  network of 300~sensors  and coverage
796 ratio greater than 50\%, we can  see on Figure~\ref{figure8}(b) that the lifetime
797 is about twice longer with  PeCO compared to DESK protocol.  The performance
798 difference    is    more    obvious   in    Figure~\ref{figure8}(b)    than    in
799 Figure~\ref{figure8}(a) because the gain induced  by our protocols increases with
800  time, and the lifetime with a coverage  of 50\% is far  longer than with
801 95\%.
802
803 \begin{figure}[h!]
804   \centering
805   \begin{tabular}{@{}cr@{}}
806     \includegraphics[scale=0.475]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\  
807     \includegraphics[scale=0.475]{figure8b.eps} & \raisebox{2.75cm}{(b)}
808   \end{tabular}
809   \caption{Network Lifetime for (a)~$Lifetime_{95}$ \\
810     and (b)~$Lifetime_{50}$.}
811   \label{figure8}
812 \end{figure} 
813
814
815
816 Figure~\ref{figure9}  compares  the  lifetime  coverage of  our  protocols  for
817 different coverage  ratios. We denote by  Protocol/50, Protocol/80, Protocol/85,
818 Protocol/90, and  Protocol/95 the amount  of time  during which the  network can
819 satisfy an area coverage greater than $50\%$, $80\%$, $85\%$, $90\%$, and $95\%$
820 respectively, where the term Protocol refers to  DiLCO  or PeCO.  Indeed there  are applications
821 that do not require a 100\% coverage of  the area to be monitored. PeCO might be
822 an interesting  method since  it achieves  a good balance  between a  high level
823 coverage ratio and network lifetime. PeCO always outperforms DiLCO for the three
824 lower  coverage  ratios,  moreover  the   improvements  grow  with  the  network
825 size. DiLCO is better  for coverage ratios near 100\%, but in  that case PeCO is
826 not ineffective for the smallest network sizes.
827
828 \begin{figure}[h!]
829 \centering \includegraphics[scale=0.5]{figure9.eps}
830 \caption{Network lifetime for different coverage ratios.}
831 \label{figure9}
832 \end{figure} 
833
834
835 \subsubsection{\bf Impact of $\alpha$ and $\beta$ on PeCO's performance}
836 Table~\ref{my-labelx} explains all possible network lifetime result of the relation between the different values of $\alpha$ and $\beta$, and for a network size equal to 200 sensor nodes. As can be seen in Table~\ref{my-labelx},  it is obvious and clear that when $\alpha$ decreased and $\beta$ increased by any step, the network lifetime for $Lifetime_{50}$ increased and the $Lifetime_{95}$ decreased. Therefore, selecting the values of $\alpha$ and $\beta$ depend on the application type used in the sensor nework. In PeCO protocol, $\alpha$ and $\beta$ are chosen based on the largest value of network lifetime for $Lifetime_{95}$.
837
838 \begin{table}[h]
839 \centering
840 \caption{The impact of $\alpha$ and $\beta$ on PeCO's performance}
841 \label{my-labelx}
842 \begin{tabular}{|c|c|c|c|}
843 \hline
844 $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
845 0.0 & 1.0 & 151 & 0 \\ \hline
846 0.1 & 0.9 & 145 & 0 \\ \hline
847 0.2 & 0.8 & 140 & 0 \\ \hline
848 0.3 & 0.7 & 134 & 0 \\ \hline
849 0.4 & 0.6 & 125 & 0 \\ \hline
850 0.5 & 0.5 & 118 & 30 \\ \hline
851 0.6 & 0.4 & 94 & 57 \\ \hline
852 0.7 & 0.3 & 97 & 49 \\ \hline
853 0.8 & 0.2 & 90 & 52 \\ \hline
854 0.9 & 0.1 & 77 & 50 \\ \hline
855 1.0 & 0.0 & 60 & 44 \\ \hline
856 \end{tabular}
857 \end{table}
858
859
860 \section{Conclusion and Future Works}
861 \label{sec:Conclusion and Future Works}
862
863 In this paper  we have studied the problem of  Perimeter-based Coverage Optimization in WSNs. We have designed  a new protocol, called Perimeter-based  Coverage Optimization, which schedules nodes'  activities (wake up  and sleep  stages) with the  objective of maintaining a  good coverage ratio  while maximizing the network  lifetime. This protocol is  applied in a distributed  way in regular subregions  obtained after partitioning the area of interest in a preliminary step. It works in periods and
864 is based on the resolution of an integer program to select the subset of sensors operating in active status for each period. Our work is original in so far as it proposes for  the first  time an  integer program  scheduling the  activation of sensors  based on  their perimeter  coverage level,  instead of  using a  set of targets/points to be covered.   
865
866
867 We have carried out  several simulations  to  evaluate the  proposed protocol. The simulation  results  show   that  PeCO  is  more   energy-efficient  than  other approaches, with respect to lifetime,  coverage ratio, active sensors ratio, and energy consumption. 
868
869 We plan to extend our framework so that the schedules are planned for multiple sensing periods. We also want to improve our integer program to  take into account heterogeneous sensors  from both  energy and node characteristics point of views. Finally,  it would  be interesting to implement our protocol using  a sensor-testbed to evaluate it in real world applications.
870
871 \bibliographystyle{gENO}
872 \bibliography{biblio} %articleeo
873
874
875 \end{document}