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

Private GIT Repository
ajout fig
[LiCO.git] / PeCO-EO / articleeo.tex~
index caeaa1852971859b7194eed3a9139b81395a77a0..64383e2396c69ee7ab18fe68f7eb02c05b265600 100644 (file)
-% gENOguide.tex\r
-% v4.0 released April 2013\r
-\r
-\documentclass{gENO2e}\r
-%\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}\r
-%\renewcommand{\algorithmcfname}{ALGORITHM}\r
-\begin{document}\r
-\r
-%\jvol{00} \jnum{00} \jyear{2013} \jmonth{April}\r
-\r
-%\articletype{GUIDE}\r
-\r
-\title{{\itshape Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}}\r
-\r
-\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}$\r
-$^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte,\r
-          Belfort, France}};}\r
-\r
-\r
-\maketitle\r
-\r
-\begin{abstract}\r
-The most important problem in a Wireless Sensor Network (WSN) is to optimize the\r
-use of its limited energy provision, so that it can fulfill its monitoring task\r
-as long as  possible. Among  known  available approaches  that can  be used  to\r
-improve  power  management,  lifetime coverage  optimization  provides  activity\r
-scheduling which ensures sensing coverage while minimizing the energy cost. In\r
-this paper,  we propose such an approach called Perimeter-based Coverage Optimization\r
-protocol (PeCO). It is a  hybrid of centralized and distributed methods: the\r
-region of interest is first subdivided into subregions and our protocol is then\r
-distributed among sensor nodes in each  subregion.\r
-The novelty of our approach lies essentially in the formulation of a new\r
-mathematical optimization  model based on the  perimeter coverage level  to schedule\r
-sensors' activities.  Extensive simulation experiments have been performed using\r
-OMNeT++, the  discrete event simulator, to  demonstrate that PeCO  can\r
-offer longer lifetime coverage for WSNs in comparison with some other protocols.\r
-\r
-\begin{keywords}Wireless Sensor Networks, Area Coverage, Energy efficiency, Optimization, Scheduling.\r
-\end{keywords}\r
-\r
-\end{abstract}\r
-\r
-\r
-\section{Introduction}\r
-\label{sec:introduction}\r
-\r
-\noindent The continuous progress in Micro Electro-Mechanical Systems (MEMS) and\r
-wireless communication hardware  has given rise to the opportunity  to use large\r
-networks    of     tiny    sensors,    called    Wireless     Sensor    Networks\r
-(WSN)~\citep{akyildiz2002wireless,puccinelli2005wireless}, to  fulfill monitoring\r
-tasks.   A  WSN  consists  of  small low-powered  sensors  working  together  by\r
-communicating with one another through multi-hop radio communications. Each node\r
-can send the data  it collects in its environment, thanks to  its sensor, to the\r
-user by means of  sink nodes. The features of a WSN made  it suitable for a wide\r
-range of application  in areas such as business,  environment, health, industry,\r
-military, and so on~\citep{yick2008wireless}.   Typically, a sensor node contains\r
-three main components~\citep{anastasi2009energy}: a  sensing unit able to measure\r
-physical,  chemical, or  biological  phenomena observed  in  the environment;  a\r
-processing unit which will process and store the collected measurements; a radio\r
-communication unit for data transmission and receiving.\r
-\r
-The energy needed  by an active sensor node to  perform sensing, processing, and\r
-communication is supplied by a power supply which is a battery. This battery has\r
-a limited energy provision and it may  be unsuitable or impossible to replace or\r
-recharge it in  most applications. Therefore it is necessary  to deploy WSN with\r
-high density in order to increase  reliability and to exploit node redundancy\r
-thanks to energy-efficient activity  scheduling approaches.  Indeed, the overlap\r
-of sensing  areas can be exploited  to schedule alternatively some  sensors in a\r
-low power sleep mode and thus save  energy. Overall, the main question that must\r
-be answered is: how to extend the lifetime coverage of a WSN as long as possible\r
-while  ensuring   a  high  level  of   coverage?   These past few years  many\r
-energy-efficient mechanisms have been suggested  to retain energy and extend the\r
-lifetime of the WSNs~\citep{rault2014energy}.\\\\\r
-This paper makes the following contributions.\r
-\begin{enumerate}\r
-\item We have devised a framework to schedule nodes to be activated alternatively such\r
-  that the network lifetime is prolonged  while ensuring that a certain level of\r
-  coverage is preserved.  A key idea in  our framework is to exploit spatial and\r
-  temporal subdivision.   On the one hand,  the area of interest  is divided into\r
-  several smaller subregions and, on the other hand, the time line is divided into\r
-  periods of equal length. In each subregion the sensor nodes will cooperatively\r
-  choose a  leader which will schedule  nodes' activities, and this  grouping of\r
-  sensors is similar to typical cluster architecture.\r
-\item We have proposed a new mathematical  optimization model.  Instead of  trying to\r
-  cover a set of specified points/targets as  in most of the methods proposed in\r
-  the literature, we formulate an integer program based on perimeter coverage of\r
-  each sensor.  The  model involves integer variables to  capture the deviations\r
-  between  the actual  level of  coverage and  the required  level.  Hence, an\r
-  optimal scheduling  will be  obtained by  minimizing a  weighted sum  of these\r
-  deviations.\r
-\item We have conducted extensive simulation  experiments, using the  discrete event\r
-  simulator OMNeT++, to demonstrate the  efficiency of our protocol. We have compared\r
-  our   PeCO   protocol   to   two   approaches   found   in   the   literature:\r
-  DESK~\citep{ChinhVu} and  GAF~\citep{xu2001geography}, and also to  our previous\r
-  work published in~\citep{Idrees2} which is  based on another optimization model\r
-  for sensor scheduling.\r
-\end{enumerate}\r
-\r
-\r
-\r
-\r
-\r
-\r
-The rest  of the paper is  organized as follows.  In the next section  we review\r
-some related work in the  field. Section~\ref{sec:The PeCO Protocol Description}\r
-is devoted to the PeCO protocol  description and Section~\ref{cp} focuses on the\r
-coverage model  formulation which is used  to schedule the activation  of sensor\r
-nodes.  Section~\ref{sec:Simulation  Results and Analysis}  presents simulations\r
-results and discusses the comparison  with other approaches. Finally, concluding\r
-remarks   are  drawn   and  some   suggestions are  given  for   future  works   in\r
-Section~\ref{sec:Conclusion and Future Works}.\r
-\r
-\section{Related Literature}\r
-\label{sec:Literature Review}\r
-\r
-\noindent  In  this section,  we  summarize  some  related works  regarding  the\r
-coverage problem and  distinguish our PeCO protocol from the  works presented in\r
-the literature.\r
-\r
-The most  discussed coverage problems in  literature can be classified  in three\r
-categories~\citep{li2013survey}   according   to  their   respective   monitoring\r
-objective.  Hence,  area coverage \citep{Misra}  means that every point  inside a\r
-fixed area  must be monitored, while  target coverage~\citep{yang2014novel} refers\r
-to  the objective  of coverage  for a  finite number  of discrete  points called\r
-targets,  and  barrier coverage~\citep{HeShibo,kim2013maximum}  focuses  on\r
-preventing  intruders   from  entering   into  the   region  of   interest.   In\r
-\citep{Deng2012}  authors  transform the  area  coverage  problem into  the  target\r
-coverage one taking into account the  intersection points among disks of sensors\r
-nodes    or   between    disk   of    sensor   nodes    and   boundaries.     In\r
-\citep{Huang:2003:CPW:941350.941367}  authors prove  that  if  the perimeters  of\r
-sensors are sufficiently  covered it will be  the case for the  whole area. They\r
-provide an algorithm in $O(nd~log~d)$  time to compute the perimeter-coverage of\r
-each  sensor,  where  $d$  denotes  the  maximum  number  of  sensors  that  are\r
-neighbors  to  a  sensor and  $n$  is  the  total  number of  sensors  in  the\r
-network. {\it In PeCO protocol, instead  of determining the level of coverage of\r
-  a set  of discrete  points, our  optimization model is  based on  checking the\r
-  perimeter-coverage of each sensor to activate a minimal number of sensors.}\r
-\r
-The major  approach to extend network  lifetime while preserving coverage  is to\r
-divide/organize the  sensors into a suitable  number of set covers  (disjoint or\r
-non-disjoint)\citep{wang2011coverage}, where  each set completely  covers a  region of interest,  and to\r
-activate these set  covers successively. The network activity can  be planned in\r
-advance and scheduled  for the entire network lifetime or  organized in periods,\r
-and the set  of active sensor nodes  is decided at the beginning  of each period\r
-\citep{ling2009energy}.  Active node selection is determined based on the problem\r
-requirements (e.g.   area monitoring,  connectivity, or power  efficiency).  For\r
-instance, \citet{jaggi2006}  address the problem of maximizing\r
-the lifetime  by dividing sensors  into the  maximum number of  disjoint subsets\r
-such  that each  subset  can ensure  both coverage  and  connectivity. A  greedy\r
-algorithm  is applied  once to  solve  this problem  and the  computed sets  are\r
-activated  in   succession  to  achieve   the  desired  network   lifetime.   \r
-\citet{chin2007},  \citet{yan2008design}, \citet{pc10},  propose  algorithms\r
-working in a periodic fashion where a  cover set is computed at the beginning of\r
-each period.   {\it Motivated by  these works,  PeCO protocol works  in periods,\r
-  where each  period contains a  preliminary phase for information  exchange and\r
-  decisions, followed by a sensing phase where one cover set is in charge of the\r
-  sensing task.}\r
-\r
-Various centralized  and distributed approaches, or  even a mixing  of these two\r
-concepts, have  been proposed  to extend the  network lifetime \citep{zhou2009variable}.   In distributed algorithms~\citep{Tian02,yangnovel,ChinhVu,qu2013distributed} each sensor decides of its\r
-own activity scheduling  after an information exchange with  its neighbors.  The\r
-main interest of such an approach is to avoid long range communications and thus\r
-to reduce the energy dedicated to the communications.  Unfortunately, since each\r
-node has only information on  its immediate neighbors (usually the one-hop ones)\r
-it may make a bad decision leading to a global suboptimal solution.  Conversely,\r
-centralized\r
-algorithms~\citep{cardei2005improving,zorbas2010solving,pujari2011high}     always\r
-provide nearly  or close to  optimal solution since  the algorithm has  a global\r
-view of the whole network. The disadvantage of a centralized method is obviously\r
-its high  cost in communications needed to  transmit to a single  node, the base\r
-station which will globally schedule  nodes' activities, data from all the other\r
-sensor nodes  in the area.  The price  in communications can be  huge since\r
-long range  communications will be  needed. In fact  the larger the WNS  is, the\r
-higher the  communication and  thus the energy  cost are.   {\it In order  to be\r
-  suitable for large-scale  networks, in the PeCO protocol,  the area of interest\r
-  is divided into several smaller subregions, and in each one, a node called the\r
-  leader  is  in  charge  of  selecting  the active  sensors  for  the  current\r
-  period.  Thus our  protocol is  scalable  and is a  globally distributed  method,\r
-  whereas it is centralized in each subregion.}\r
-\r
-Various  coverage scheduling  algorithms have  been developed  these past few years.\r
-Many of  them, dealing with  the maximization of the  number of cover  sets, are\r
-heuristics.   These  heuristics involve  the  construction  of  a cover  set  by\r
-including in priority the sensor nodes  which cover critical targets, that is to\r
-say   targets   that  are   covered   by   the   smallest  number   of   sensors\r
-\citep{berman04,zorbas2010solving}.  Other  approaches are based  on mathematical\r
-programming formulations~\citep{cardei2005energy,5714480,pujari2011high,Yang2014}\r
-and dedicated techniques (solving with a branch-and-bound algorithm available in\r
-optimization  solver).  The  problem is  formulated as  an optimization  problem\r
-(maximization of the lifetime or number of cover sets) under target coverage and\r
-energy  constraints.   Column  generation   techniques,  well-known  and  widely\r
-practiced techniques for  solving linear programs with too  many variables, have\r
-also                                                                        been\r
-used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012column}. {\it  In the PeCO\r
-  protocol, each  leader, in charge  of a  subregion, solves an  integer program\r
-  which has a twofold objective: minimize the overcoverage and the undercoverage\r
-  of the perimeter of each sensor.}\r
-\r
-\r
-\r
-\section{ The P{\scshape e}CO Protocol Description}\r
-\label{sec:The PeCO Protocol Description}\r
-\r
-\noindent  In  this  section,  we  describe in  details  our Perimeter-based  Coverage\r
-Optimization protocol.  First we present the  assumptions we made and the models\r
-we considered (in particular the perimeter coverage one), second we describe the\r
-background idea of our protocol, and third  we give the outline of the algorithm\r
-executed by each node.\r
-\r
-\r
-\subsection{Assumptions and Models}\r
-\label{CI}\r
-\r
-\noindent A WSN consisting of $J$ stationary sensor nodes randomly and uniformly\r
-distributed in  a bounded sensor field  is considered. The wireless  sensors are\r
-deployed in high density  to ensure initially a high coverage  ratio of the area\r
-of interest.  We  assume that all the  sensor nodes are homogeneous  in terms of\r
-communication,  sensing,  and  processing capabilities  and  heterogeneous  from\r
-the energy provision  point of  view.  The  location information  is available  to a\r
-sensor node either  through hardware such as embedded GPS  or location discovery\r
-algorithms.   We  assume  that  each  sensor  node  can  directly  transmit  its\r
-measurements to  a mobile  sink node.  For  example, a sink  can be  an unmanned\r
-aerial  vehicle  (UAV)  flying  regularly  over  the  sensor  field  to  collect\r
-measurements from sensor nodes. A mobile sink node collects the measurements and\r
-transmits them to the base station.   We consider a Boolean disk coverage model,\r
-which is the most  widely used sensor coverage model in  the literature, and all\r
-sensor nodes  have a constant sensing  range $R_s$.  Thus, all  the space points\r
-within a disk centered at a sensor with  a radius equal to the sensing range are\r
-said to be covered  by this sensor. We also assume  that the communication range\r
-$R_c$ satisfies $R_c  \geq 2 \cdot R_s$. In fact,  \citet{Zhang05}\r
-proved  that if  the  transmission  range fulfills  the  previous hypothesis,  the\r
-complete coverage of a convex area implies connectivity among active nodes.\r
-\r
-The PeCO protocol  uses the  same perimeter-coverage  model as \citet{huang2005coverage}. It  can be expressed as follows:  a sensor is\r
-said to be perimeter  covered if all the points on its  perimeter are covered by\r
-at least  one sensor  other than  itself.  They  proved that  a network  area is\r
-$k$-covered if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors).\r
\r
-Figure~\ref{figure1}(a)  shows  the coverage  of  sensor  node~$0$. On  this\r
-figure, we can  see that sensor~$0$ has  nine neighbors and we  have reported on\r
-its  perimeter (the  perimeter  of the  disk  covered by  the  sensor) for  each\r
-neighbor  the  two  points  resulting  from the intersection  of  the  two  sensing\r
-areas. These points are denoted for  neighbor~$i$ by $iL$ and $iR$, respectively\r
-for  left and  right from  a neighboing  point of  view.  The  resulting couples  of\r
-intersection points subdivide  the perimeter of sensor~$0$  into portions called\r
-arcs.\r
-\r
-\begin{figure}[ht!]\r
-  \centering\r
-  \begin{tabular}{@{}cr@{}}\r
-    \includegraphics[width=75mm]{figure1a.eps} & \raisebox{3.25cm}{(a)} \\\r
-    \includegraphics[width=75mm]{figure1b.eps} & \raisebox{2.75cm}{(b)}\r
-  \end{tabular}\r
-  \caption{(a) Perimeter  coverage of sensor node  0 and (b) finding  the arc of\r
-    $u$'s perimeter covered by $v$.}\r
-  \label{figure1}\r
-\end{figure} \r
-\r
-Figure~\ref{figure1}(b) describes the geometric information used to find the\r
-locations of the  left and right points of  an arc on the perimeter  of a sensor\r
-node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the\r
-west  side of  sensor~$u$,  with  the following  respective  coordinates in  the\r
-sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates we can\r
-compute the euclidean distance between nodes~$u$ and $v$: $Dist(u,v)=\sqrt{\vert\r
-  u_x  - v_x  \vert^2 +  \vert u_y-v_y  \vert^2}$, while  the angle~$\alpha$  is\r
-obtained through  the formula:\r
- \[\r
-\alpha =  \arccos \left(\frac{Dist(u,v)}{2R_s}\r
-\right).\r
-\] \r
-The arc on the perimeter of~$u$ defined by the angular interval $[\pi\r
-  - \alpha,\pi + \alpha]$ is said to be perimeter-covered by sensor~$v$.\r
-\r
-Every couple of intersection points is placed on the angular interval $[0,2\pi]$\r
-in  a  counterclockwise manner,  leading  to  a  partitioning of  the  interval.\r
-Figure~\ref{figure1}(a)  illustrates  the arcs  for  the  nine neighbors  of\r
-sensor $0$ and  figure~\ref{figure2} gives the position of  the corresponding arcs\r
-in  the interval  $[0,2\pi]$. More  precisely, we  can see  that the  points are\r
-ordered according  to the  measures of  the angles  defined by  their respective\r
-positions. The intersection points are  then visited one after another, starting\r
-from the first  intersection point  after  point~zero,  and  the maximum  level  of\r
-coverage is determined  for each interval defined by two  successive points. The\r
-maximum  level of  coverage is  equal to  the number  of overlapping  arcs.  For\r
-example, \r
-between~$5L$  and~$6L$ the maximum  level of  coverage is equal  to $3$\r
-(the value is highlighted in yellow  at the bottom of figure~\ref{figure2}), which\r
-means that at most 2~neighbors can cover  the perimeter in addition to node $0$. \r
-Table~\ref{my-label} summarizes for each coverage  interval the maximum level of\r
-coverage and  the sensor  nodes covering the  perimeter.  The  example discussed\r
-above is thus given by the sixth line of the table.\r
-\r
-\r
-\begin{figure*}[t!]\r
-\centering\r
-\includegraphics[width=127.5mm]{figure2.eps}  \r
-\caption{Maximum coverage levels for perimeter of sensor node $0$.}\r
-\label{figure2}\r
-\end{figure*} \r
-\r
-\r
-\r
-\r
- \begin{table}\r
- \tbl{Coverage intervals and contributing sensors for sensor node 0 \label{my-label}}\r
-{\begin{tabular}{|c|c|c|c|c|c|c|c|c|}\r
-\hline\r
-\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\r
-0.0291    & 1L                                                                        & 2L                                                        & 4                                                                     & 0                     & 1                     & 3                    & 4                    &                      \\ \hline\r
-0.104     & 2L                                                                        & 3R                                                        & 5                                                                     & 0                     & 1                     & 3                    & 4                    & 2                    \\ \hline\r
-0.3168    & 3R                                                                        & 4R                                                        & 4                                                                     & 0                     & 1                     & 4                    & 2                    &                      \\ \hline\r
-0.6752    & 4R                                                                        & 1R                                                        & 3                                                                     & 0                     & 1                     & 2                    &                      &                      \\ \hline\r
-1.8127    & 1R                                                                        & 5L                                                        & 2                                                                     & 0                     & 2                     &                      &                      &                      \\ \hline\r
-1.9228    & 5L                                                                        & 6L                                                        & 3                                                                     & 0                     & 2                     & 5                    &                      &                      \\ \hline\r
-2.3959    & 6L                                                                        & 2R                                                        & 4                                                                     & 0                     & 2                     & 5                    & 6                    &                      \\ \hline\r
-2.4258    & 2R                                                                        & 7L                                                        & 3                                                                     & 0                     & 5                     & 6                    &                      &                      \\ \hline\r
-2.7868    & 7L                                                                        & 8L                                                        & 4                                                                     & 0                     & 5                     & 6                    & 7                    &                      \\ \hline\r
-2.8358    & 8L                                                                        & 5R                                                        & 5                                                                     & 0                     & 5                     & 6                    & 7                    & 8                    \\ \hline\r
-2.9184    & 5R                                                                        & 7R                                                        & 4                                                                     & 0                     & 6                     & 7                    & 8                    &                      \\ \hline\r
-3.3301    & 7R                                                                        & 9R                                                        & 3                                                                     & 0                     & 6                     & 8                    &                      &                      \\ \hline\r
-3.9464    & 9R                                                                        & 6R                                                        & 4                                                                     & 0                     & 6                     & 8                    & 9                    &                      \\ \hline\r
-4.767     & 6R                                                                        & 3L                                                        & 3                                                                     & 0                     & 8                     & 9                    &                      &                      \\ \hline\r
-4.8425    & 3L                                                                        & 8R                                                        & 4                                                                     & 0                     & 3                     & 8                    & 9                    &                      \\ \hline\r
-4.9072    & 8R                                                                        & 4L                                                        & 3                                                                     & 0                     & 3                     & 9                    &                      &                      \\ \hline\r
-5.3804    & 4L                                                                        & 9R                                                        & 4                                                                     & 0                     & 3                     & 4                    & 9                    &                      \\ \hline\r
-5.9157    & 9R                                                                        & 1L                                                        & 3                                                                     & 0                     & 3                     & 4                    &                      &                      \\ \hline\r
-\end{tabular}}\r
-\r
-\r
-\end{table}\r
-\r
-\r
-\r
-\r
-In the PeCO  protocol, the scheduling of the sensor  nodes' activities is formulated  with an\r
-integer program  based on  coverage intervals. The  formulation of  the coverage\r
-optimization problem is  detailed in~section~\ref{cp}.  Note that  when a sensor\r
-node  has a  part of  its sensing  range outside  the WSN  sensing field,  as in\r
-figure~\ref{figure3}, the maximum coverage level for  this arc is set to $\infty$\r
-and  the  corresponding  interval  will  not   be  taken  into  account  by  the\r
-optimization algorithm.\r
-\r
- \newpage\r
-\begin{figure}[h!]\r
-\centering\r
-\includegraphics[width=62.5mm]{figure3.eps}  \r
-\caption{Sensing range outside the WSN's area of interest.}\r
-\label{figure3}\r
-\end{figure} \r
-\r
-\r
-\subsection{The Main Idea}\r
-\r
-\noindent The  WSN area of  interest is, in a  first step, divided  into regular\r
-homogeneous subregions  using a divide-and-conquer  algorithm. In a  second step\r
-our  protocol  will  be  executed  in   a  distributed  way  in  each  subregion\r
-simultaneously to schedule nodes' activities for one sensing period.\r
-\r
-As  shown in  figure~\ref{figure4}, node  activity  scheduling is  produced by  our\r
-protocol in a periodic manner. Each period is divided into 4 stages: Information\r
-(INFO)  Exchange,  Leader Election,  Decision  (the  result of  an  optimization\r
-problem),  and  Sensing.   For  each  period there  is  exactly  one  set  cover\r
-responsible for  the sensing task.  Protocols  based on a periodic  scheme, like\r
-PeCO, are more  robust against an unexpected  node failure. On the  one hand, if\r
-a node failure is discovered before  taking the decision, the corresponding sensor\r
-node will  not be considered  by the optimization  algorithm. On  the other\r
-hand, if the sensor failure happens after  the decision, the sensing task of the\r
-network will be temporarily affected: only  during the period of sensing until a\r
-new period starts, since a new set cover will take charge of the sensing task in\r
-the next period. The energy consumption and some other constraints can easily be\r
-taken  into  account since  the  sensors  can  update  and then  exchange  their\r
-information (including their  residual energy) at the beginning  of each period.\r
-However, the pre-sensing  phases (INFO Exchange, Leader  Election, and Decision)\r
-are energy consuming, even for nodes that will not join the set cover to monitor\r
-the area.\r
-\r
-\begin{figure}[t!]\r
-\centering\r
-\includegraphics[width=80mm]{figure4.eps}  \r
-\caption{PeCO protocol.}\r
-\label{figure4}\r
-\end{figure} \r
-\r
-We define two types of packets to be used by PeCO protocol:\r
-\r
-\begin{itemize} \r
-\item INFO  packet: sent  by each  sensor node to  all the  nodes inside  a same\r
-  subregion for information exchange.\r
-\item ActiveSleep packet: sent  by the leader to all the  nodes in its subregion\r
-  to transmit to  them their respective status (stay Active  or go Sleep) during\r
-  sensing phase.\r
-\end{itemize}\r
-\r
-\r
-Five status are possible for a sensor node in the network:\r
-\r
-\begin{itemize} \r
-\item LISTENING: waits for a decision (to be active or not);\r
-\item COMPUTATION: executes the optimization algorithm as leader to\r
-  determine the activities scheduling;\r
-\item ACTIVE: node is sensing;\r
-\item SLEEP: node is turned off;\r
-\item COMMUNICATION: transmits or receives packets.\r
-\end{itemize}\r
-\r
-\r
-\subsection{PeCO Protocol Algorithm}\r
-\r
-\noindent The  pseudocode implementing the  protocol on  a node is  given below.\r
-More  precisely,  Algorithm~\ref{alg:PeCO}  gives  a brief  description  of  the\r
-protocol applied by a sensor node $s_k$ where $k$ is the node index in the WSN.\r
-\r
-\r
-\r
-\begin{algorithm}      \r
- % \KwIn{all the parameters related to information exchange}\r
-%  \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)}\r
-%  \BlankLine\r
-  %\emph{Initialize the sensor node and determine it's position and subregion} \; \r
-  \r
-\noindent{\bf If} $RE_k \geq E_{th}$ {\bf then}\\\r
-\hspace*{0.6cm} \emph{$s_k.status$ = COMMUNICATION;}\\\r
-\hspace*{0.6cm}  \emph{Send $INFO()$ packet to other nodes in subregion;}\\\r
-\hspace*{0.6cm}  \emph{Wait $INFO()$ packet from other nodes in subregion;}\\\r
-\hspace*{0.6cm} \emph{Update K.CurrentSize;}\\\r
-\hspace*{0.6cm}  \emph{LeaderID = Leader election;}\\\r
-\hspace*{0.6cm} {\bf If} $ s_k.ID = LeaderID $ {\bf then}\\\r
-\hspace*{1.2cm}   \emph{$s_k.status$ = COMPUTATION;}\\\r
-\hspace*{1.2cm}{\bf If} \emph{$ s_k.ID $ is Not previously selected as a Leader} {\bf then}\\\r
-\hspace*{1.8cm} \emph{ Execute the perimeter coverage model;}\\\r
-\hspace*{1.2cm} {\bf end}\\\r
-\hspace*{1.2cm}{\bf If} \emph{($s_k.ID $ is the same Previous Leader)~And~(K.CurrentSize = K.PreviousSize)}\\\r
-\hspace*{1.8cm} \emph{ Use the same previous cover set for current sensing stage;}\\\r
-\hspace*{1.2cm}  {\bf end}\\\r
-\hspace*{1.2cm}  {\bf else}\\\r
-\hspace*{1.8cm}\emph{Update $a^j_{ik}$; prepare data for IP~Algorithm;}\\\r
-\hspace*{1.8cm} \emph{$\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$);}\\\r
-\hspace*{1.8cm} \emph{K.PreviousSize = K.CurrentSize;}\\\r
-\hspace*{1.2cm}  {\bf end}\\\r
-\hspace*{1.2cm}\emph{$s_k.status$ = COMMUNICATION;}\\\r
-\hspace*{1.2cm}\emph{Send $ActiveSleep()$ to each node $l$ in subregion;}\\\r
-\hspace*{1.2cm}\emph{Update $RE_k $;}\\\r
-\hspace*{0.6cm}  {\bf end}\\\r
-\hspace*{0.6cm}  {\bf else}\\\r
-\hspace*{1.2cm}\emph{$s_k.status$ = LISTENING;}\\\r
-\hspace*{1.2cm}\emph{Wait $ActiveSleep()$ packet from the Leader;}\\\r
-\hspace*{1.2cm}\emph{Update $RE_k $;}\\\r
-\hspace*{0.6cm}  {\bf end}\\\r
-{\bf end}\\\r
-{\bf else}\\\r
-\hspace*{0.6cm} \emph{Exclude $s_k$ from entering in the current sensing stage;}\\\r
-{\bf end}\\\r
-\label{alg:PeCO}\r
-\end{algorithm}\r
-\r
-\r
-\r
-In this  algorithm, K.CurrentSize and K.PreviousSize  respectively represent the\r
-current number and  the previous number of living nodes in  the subnetwork of the\r
-subregion.  Initially, the sensor node checks its remaining energy $RE_k$, which\r
-must be greater than a threshold $E_{th}$ in order to participate in the current\r
-period.  Each  sensor node  determines its position  and its subregion  using an\r
-embedded  GPS or a  location discovery  algorithm. After  that, all  the sensors\r
-collect position coordinates,  remaining energy, sensor node ID,  and the number\r
-of their  one-hop live  neighbors during the  information exchange.  The sensors\r
-inside a same region cooperate to elect a leader. The selection criteria for the\r
-leader, in order of priority,  are: larger numbers of neighbors, larger remaining\r
-energy, and  then in case  of equality, larger  index.  Once chosen,  the leader\r
-collects information to formulate and  solve the integer program which allows to\r
-construct the set of active sensors in the sensing stage.\r
-\r
-\r
-\section{Perimeter-based Coverage Problem Formulation}\r
-\label{cp}\r
-\r
-\noindent In this  section, the coverage model is  mathematically formulated. We\r
-start  with a  description of the notations that will  be used  throughout the\r
-section.\\\r
-First, we have the following sets:\r
-\begin{itemize}\r
-\item $S$ represents the set of WSN sensor nodes;\r
-\item $A \subseteq S $ is the subset of alive sensors;\r
-\item  $I_j$  designates  the  set  of  coverage  intervals  (CI)  obtained  for\r
-  sensor~$j$.\r
-\end{itemize}\r
-$I_j$ refers to the set of  coverage intervals which have been defined according\r
-to the  method introduced in  subsection~\ref{CI}. For a coverage  interval $i$,\r
-let $a^j_{ik}$ denotes  the indicator function of whether  sensor~$k$ is involved\r
-in coverage interval~$i$ of sensor~$j$, that is:\r
-\begin{equation}\r
-a^j_{ik} = \left \{ \r
-\begin{array}{lll}\r
-  1 & \mbox{if sensor $k$ is involved in the } \\\r
-       &       \mbox{coverage interval $i$ of sensor $j$}, \\\r
-  0 & \mbox{otherwise.}\\\r
-\end{array} \right.\r
-\end{equation}\r
-Note that $a^k_{ik}=1$ by definition of the interval.\r
-\r
-Second,  we define  several binary  and integer  variables.  Hence,  each binary\r
-variable $X_{k}$  determines the activation of  sensor $k$ in the  sensing phase\r
-($X_k=1$ if  the sensor $k$  is active or 0  otherwise).  $M^j_i$ is  an integer\r
-variable  which  measures  the  undercoverage  for  the  coverage  interval  $i$\r
-corresponding to  sensor~$j$. In  the same  way, the  overcoverage for  the same\r
-coverage interval is given by the variable $V^j_i$.\r
-\r
-If we decide to sustain a level of coverage equal to $l$ all along the perimeter\r
-of sensor  $j$, we have  to ensure  that at least  $l$ sensors involved  in each\r
-coverage  interval $i  \in I_j$  of  sensor $j$  are active.   According to  the\r
-previous notations, the number of active sensors in the coverage interval $i$ of\r
-sensor $j$  is given by  $\sum_{k \in A} a^j_{ik}  X_k$.  To extend  the network\r
-lifetime,  the objective  is to  activate a  minimal number  of sensors  in each\r
-period to  ensure the  desired coverage  level. As the  number of  alive sensors\r
-decreases, it becomes impossible to reach  the desired level of coverage for all\r
-coverage intervals. Therefore we use variables  $M^j_i$ and $V^j_i$ as a measure\r
-of the  deviation between  the desired  number of active  sensors in  a coverage\r
-interval and  the effective  number. And  we try  to minimize  these deviations,\r
-first to  force the  activation of  a minimal  number of  sensors to  ensure the\r
-desired coverage level, and if the desired level cannot be completely satisfied,\r
-to reach a coverage level as close as possible to the desired one.\r
-\r
-\r
-\r
-\r
-Our coverage optimization problem can then be mathematically expressed as follows: \r
-\r
-\begin{equation} \r
-\left \{\r
-\begin{array}{ll}\r
-\min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\\r
-\textrm{subject to :}&\\\r
-\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i  \geq l \quad \forall i \in I_j, \forall j \in S\\\r
-\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i  \leq l \quad \forall i \in I_j, \forall j \in S\\\r
-X_{k} \in \{0,1\}, \forall k \in A\r
-\end{array}\r
-\right.\r
-\end{equation}\r
-\r
-$\alpha^j_i$ and $\beta^j_i$  are nonnegative weights selected  according to the\r
-relative importance of satisfying the associated level of coverage. For example,\r
-weights associated with  coverage intervals of a specified part  of a region may\r
-be  given by a  relatively larger  magnitude than  weights associated  with another\r
-region. This  kind of integer program  is inspired from the  model developed for\r
-brachytherapy treatment planning  for optimizing dose  distribution\r
-\citep{0031-9155-44-1-012}. The integer  program must be solved by  the leader in\r
-each subregion at the beginning of  each sensing phase, whenever the environment\r
-has  changed (new  leader,  death of  some  sensors). Note  that  the number  of\r
-constraints in the model is constant  (constraints of coverage expressed for all\r
-sensors), whereas the number of variables $X_k$ decreases over periods, since we\r
-consider only alive  sensors (sensors with enough energy to  be alive during one\r
-sensing phase) in the model.\r
-\r
-\section{Performance Evaluation and Analysis}  \r
-\label{sec:Simulation Results and Analysis}\r
-\r
-\r
-\subsection{Simulation Settings}\r
-\r
-\r
-The WSN  area of interest is  supposed to be divided  into 16~regular subregions\r
-and we use the same energy consumption than in our previous work~\citep{Idrees2}.\r
-Table~\ref{table3} gives the chosen parameters settings.\r
-\r
-\begin{table}[ht]\r
-\tbl{Relevant parameters for network initialization \label{table3}}{\r
-\r
-\centering\r
-\r
-\begin{tabular}{c|c}\r
-\r
-\hline\r
-Parameter & Value  \\ [0.5ex]\r
-   \r
-\hline\r
-% inserts single horizontal line\r
-Sensing field & $(50 \times 25)~m^2 $   \\\r
-\r
-WSN size &  100, 150, 200, 250, and 300~nodes   \\\r
-\r
-Initial energy  & in range 500-700~Joules  \\  \r
-\r
-Sensing period & duration of 60 minutes \\\r
-$E_{th}$ & 36~Joules\\\r
-$R_s$ & 5~m   \\     \r
-\r
-$\alpha^j_i$ & 0.6   \\\r
-\r
-$\beta^j_i$ & 0.4\r
-\r
-\end{tabular}}\r
-\r
-\r
-\end{table}\r
-To  obtain  experimental  results  which are  relevant,  simulations  with  five\r
-different node densities going from  100 to 300~nodes were performed considering\r
-each time 25~randomly  generated networks. The nodes are deployed  on a field of\r
-interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a\r
-high coverage ratio. Each node has an  initial energy level, in Joules, which is\r
-randomly drawn in the interval $[500-700]$.   If its energy provision reaches a\r
-value below  the threshold $E_{th}=36$~Joules,  the minimum energy needed  for a\r
-node  to stay  active during  one period,  it will  no more  participate in  the\r
-coverage task. This value corresponds to the energy needed by the sensing phase,\r
-obtained by multiplying  the energy consumed in active state  (9.72 mW) with the\r
-time in  seconds for one  period (3600 seconds), and  adding the energy  for the\r
-pre-sensing phases.  According  to the interval of initial energy,  a sensor may\r
-be active during at most 20 periods.\r
-\r
-The values  of $\alpha^j_i$ and  $\beta^j_i$ have been  chosen to ensure  a good\r
-network coverage and a longer WSN lifetime.  We have given a higher priority to\r
-the  undercoverage  (by  setting  the  $\alpha^j_i$ with  a  larger  value  than\r
-$\beta^j_i$)  so as  to prevent  the non-coverage  for the  interval~$i$ of  the\r
-sensor~$j$.  On the  other hand,  we have assigned to\r
-$\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute\r
-in covering the interval.\r
-\r
-We introduce the following performance metrics to evaluate the efficiency of our\r
-approach.\r
-\r
-\r
-\begin{itemize}\r
-\item {\bf Network Lifetime}: the lifetime  is defined as the time elapsed until\r
-  the  coverage  ratio  falls  below a  fixed  threshold.   $Lifetime_{95}$  and\r
-  $Lifetime_{50}$  denote, respectively,  the  amount of  time  during which  is\r
-  guaranteed a  level of coverage  greater than $95\%$  and $50\%$. The  WSN can\r
-  fulfill the expected  monitoring task until all its nodes  have depleted their\r
-  energy or if the network is no  more connected. This last condition is crucial\r
-  because without  network connectivity a  sensor may not be  able to send  to a\r
-  base station an event it has sensed.\r
-\item {\bf  Coverage Ratio (CR)} : it  measures how  well the  WSN is  able to\r
-  observe the area of interest. In our  case, we discretized the sensor field as\r
-  a regular grid, which yields the following equation:\r
-  \r
-\r
-\[\r
-    \scriptsize\r
-    \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100\r
-\]\r
-\r
-\r
-  where $n$  is the  number of covered  grid points by  active sensors  of every\r
-  subregions during  the current sensing phase  and $N$ is total  number of grid\r
-  points in  the sensing  field.  In  our simulations  we have  set a  layout of\r
-  $N~=~51~\times~26~=~1326$~grid points.\r
-\item {\bf Active Sensors Ratio (ASR)}: a  major objective of our protocol is to\r
-  activate  as few nodes as possible,  in order  to minimize  the communication\r
-  overhead and maximize the WSN lifetime. The active sensors ratio is defined as\r
-  follows:\r
\r
-\[\r
-    \scriptsize\r
-    \mbox{ASR}(\%) =  \frac{\sum\limits_{r=1}^R \mbox{$|A_r^p|$}}{\mbox{$|S|$}} \times 100\r
-\]\r
-\r
-  where $|A_r^p|$ is  the number of active  sensors in the subregion  $r$ in the\r
-  current sensing period~$p$, $|S|$ is the number of sensors in the network, and\r
-  $R$ is the number of subregions.\r
-\item {\bf Energy Consumption (EC)}: energy consumption can be seen as the total\r
-  energy  consumed by  the  sensors during  $Lifetime_{95}$ or  $Lifetime_{50}$,\r
-  divided by  the number of  periods. The value of  EC is computed  according to\r
-  this formula:\r
-\r
-\[  \r
-  \scriptsize\r
-    \mbox{EC} = \frac{\sum\limits_{p=1}^{P} \left( E^{\mbox{com}}_p+E^{\mbox{list}}_p+E^{\mbox{comp}}_p  \r
-      + E^{a}_p+E^{s}_p \right)}{P},\r
-\]\r
\r
-  where $P$ corresponds  to the number of periods. The  total energy consumed by\r
-  the  sensors  comes  through  taking   into  consideration  four  main  energy\r
-  factors. The first one, denoted $E^{\scriptsize \mbox{com}}_p$, represents the\r
-  energy consumption spent  by all the nodes for  wireless communications during\r
-  period $p$.  $E^{\scriptsize \mbox{list}}_p$,  the next factor, corresponds to\r
-  the energy  consumed by the sensors  in LISTENING status before  receiving the\r
-  decision to go active or sleep in period $p$.  $E^{\scriptsize \mbox{comp}}_p$\r
-  refers to  the energy  needed by  all the  leader nodes  to solve  the integer\r
-  program during a period.  Finally, $E^a_{p}$ and $E^s_{p}$ indicate the energy\r
-  consumed by the WSN during the sensing phase (active and sleeping nodes).\r
-\end{itemize}\r
-\r
-\r
-\subsection{Simulation Results}\r
-\r
-In  order  to  assess and  analyze  the  performance  of  our protocol  we  have\r
-implemented PeCO protocol in  OMNeT++~\citep{varga} simulator.  Besides PeCO, two\r
-other  protocols,  described  in  the  next paragraph,  will  be  evaluated  for\r
-comparison purposes.   The simulations were run  on a DELL laptop  with an Intel\r
-Core~i3~2370~M (1.8~GHz)  processor (2  cores) whose MIPS  (Million Instructions\r
-Per Second) rate  is equal to 35330. To  be consistent with the use  of a sensor\r
-node based on  Atmels AVR ATmega103L microcontroller (6~MHz) having  a MIPS rate\r
-equal to 6,  the original execution time  on the laptop is  multiplied by 2944.2\r
-$\left(\frac{35330}{2} \times  \frac{1}{6} \right)$.  The modeling  language for\r
-Mathematical Programming (AMPL)~\citep{AMPL} is  employed to generate the integer\r
-program instance  in a  standard format, which  is then read  and solved  by the\r
-optimization solver  GLPK (GNU  linear Programming Kit  available in  the public\r
-domain) \citep{glpk} through a Branch-and-Bound method.\r
-\r
-As said previously, the PeCO is  compared to three other approaches. The first\r
-one,  called  DESK,  is  a  fully distributed  coverage  algorithm  proposed  by\r
-\citep{ChinhVu}. The second one,  called GAF~\citep{xu2001geography}, consists in\r
-dividing  the monitoring  area into  fixed  squares. Then,  during the  decision\r
-phase, in each square, one sensor is  chosen to remain active during the sensing\r
-phase. The last  one, the DiLCO protocol~\citep{Idrees2}, is  an improved version\r
-of a research work we presented in~\citep{idrees2014coverage}. Let us notice that\r
-PeCO and  DiLCO protocols are  based on the  same framework. In  particular, the\r
-choice for the simulations of a partitioning in 16~subregions was made because\r
-it corresponds to the configuration producing  the best results for DiLCO. The\r
-protocols are distinguished  from one another by the formulation  of the integer\r
-program providing the set of sensors which  have to be activated in each sensing\r
-phase. DiLCO protocol tries to satisfy the coverage of a set of primary points,\r
-whereas the PeCO protocol objective is to reach a desired level of coverage for each\r
-sensor perimeter. In our experimentations, we chose a level of coverage equal to\r
-one ($l=1$).\r
-\r
-\subsubsection{\bf Coverage Ratio}\r
-\r
-Figure~\ref{figure5}  shows the  average coverage  ratio for  200 deployed  nodes\r
-obtained with the  four protocols. DESK, GAF, and DiLCO  provide a slightly better\r
-coverage ratio with respectively 99.99\%,  99.91\%, and 99.02\%, compared to the 98.76\%\r
-produced by  PeCO for the  first periods. This  is due to  the fact that  at the\r
-beginning the DiLCO protocol  puts to  sleep status  more redundant  sensors (which\r
-slightly decreases the coverage ratio), while the three other protocols activate\r
-more sensor  nodes. Later, when the  number of periods is  beyond~70, it clearly\r
-appears that  PeCO provides a better  coverage ratio and keeps  a coverage ratio\r
-greater  than 50\%  for  longer periods  (15  more compared  to  DiLCO, 40  more\r
-compared to DESK). The energy saved by  PeCO in the early periods allows later a\r
-substantial increase of the coverage performance.\r
-\r
-\parskip 0pt    \r
-\begin{figure}[h!]\r
-\centering\r
- \includegraphics[scale=0.5] {figure5.eps} \r
-\caption{Coverage ratio for 200 deployed nodes.}\r
-\label{figure5}\r
-\end{figure} \r
-\r
-\r
-\r
-\r
-\subsubsection{\bf Active Sensors Ratio}\r
-\r
-Having the less active sensor nodes in  each period is essential to minimize the\r
-energy consumption  and thus to  maximize the network  lifetime.  Figure~\ref{figure6}\r
-shows the  average active nodes ratio  for 200 deployed nodes.   We observe that\r
-DESK and  GAF have 30.36  \% and  34.96 \% active  nodes for the  first fourteen\r
-rounds and  DiLCO and PeCO  protocols compete perfectly  with only 17.92~\% and\r
-20.16~\% active  nodes during the same  time interval. As the  number of periods\r
-increases, PeCO protocol  has a lower number of active  nodes in comparison with\r
-the three other approaches, while keeping a greater coverage ratio as shown in\r
-figure \ref{figure5}.\r
-\r
-\begin{figure}[h!]\r
-\centering\r
-\includegraphics[scale=0.5]{figure6.eps}  \r
-\caption{Active sensors ratio for 200 deployed nodes.}\r
-\label{figure6}\r
-\end{figure} \r
-\r
-\subsubsection{\bf Energy Consumption}\r
-\r
-We studied the effect of the energy  consumed by the WSN during the communication,\r
-computation, listening, active, and sleep status for different network densities\r
-and  compared  it for  the  four  approaches.  Figures~\ref{figure7}(a)  and  (b)\r
-illustrate  the  energy   consumption  for  different  network   sizes  and  for\r
-$Lifetime95$ and  $Lifetime50$. The results show  that our PeCO protocol  is the\r
-most competitive  from the energy  consumption point of  view. As shown  in both\r
-figures, PeCO consumes much less energy than the three other methods.  One might\r
-think that the  resolution of the integer  program is too costly  in energy, but\r
-the  results show  that it  is very  beneficial to  lose a  bit of  time in  the\r
-selection of  sensors to  activate.  Indeed the  optimization program  allows to\r
-reduce significantly the number of active  sensors and so the energy consumption\r
-while keeping a good coverage level.\r
-\r
-\begin{figure}[h!]\r
-  \centering\r
-  \begin{tabular}{@{}cr@{}}\r
-    \includegraphics[scale=0.475]{figure7a.eps} & \raisebox{2.75cm}{(a)} \\\r
-    \includegraphics[scale=0.475]{figure7b.eps} & \raisebox{2.75cm}{(b)}\r
-  \end{tabular}\r
-  \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.}\r
-  \label{figure7}\r
-\end{figure} \r
-\r
-\r
-\r
-\subsubsection{\bf Network Lifetime}\r
-\r
-We observe the superiority of PeCO and DiLCO protocols in comparison with the\r
-two    other   approaches    in    prolonging   the    network   lifetime.    In\r
-Figures~\ref{figure8}(a)  and (b),  $Lifetime95$ and  $Lifetime50$ are  shown for\r
-different  network  sizes.   As  highlighted  by  these  figures,  the  lifetime\r
-increases with the size  of the network, and it is clearly   largest for DiLCO\r
-and PeCO  protocols.  For instance,  for a  network of 300~sensors  and coverage\r
-ratio greater than 50\%, we can  see on figure~\ref{figure8}(b) that the lifetime\r
-is about twice longer with  PeCO compared to DESK protocol.  The performance\r
-difference    is    more    obvious   in    figure~\ref{figure8}(b)    than    in\r
-figure~\ref{figure8}(a) because the gain induced  by our protocols increases with\r
- time, and the lifetime with a coverage  of 50\% is far  longer than with\r
-95\%.\r
-\r
-\begin{figure}[h!]\r
-  \centering\r
-  \begin{tabular}{@{}cr@{}}\r
-    \includegraphics[scale=0.475]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\  \r
-    \includegraphics[scale=0.475]{figure8b.eps} & \raisebox{2.75cm}{(b)}\r
-  \end{tabular}\r
-  \caption{Network Lifetime for (a)~$Lifetime_{95}$ \\\r
-    and (b)~$Lifetime_{50}$.}\r
-  \label{figure8}\r
-\end{figure} \r
-\r
-\r
-\r
-Figure~\ref{figure9}  compares  the  lifetime  coverage of  our  protocols  for\r
-different coverage  ratios. We denote by  Protocol/50, Protocol/80, Protocol/85,\r
-Protocol/90, and  Protocol/95 the amount  of time  during which the  network can\r
-satisfy an area coverage greater than $50\%$, $80\%$, $85\%$, $90\%$, and $95\%$\r
-respectively, where the term Protocol refers to  DiLCO  or PeCO.  Indeed there  are applications\r
-that do not require a 100\% coverage of  the area to be monitored. PeCO might be\r
-an interesting  method since  it achieves  a good balance  between a  high level\r
-coverage ratio and network lifetime. PeCO always outperforms DiLCO for the three\r
-lower  coverage  ratios,  moreover  the   improvements  grow  with  the  network\r
-size. DiLCO is better  for coverage ratios near 100\%, but in  that case PeCO is\r
-not ineffective for the smallest network sizes.\r
-\r
-\begin{figure}[h!]\r
-\centering \includegraphics[scale=0.5]{figure9.eps}\r
-\caption{Network lifetime for different coverage ratios.}\r
-\label{figure9}\r
-\end{figure} \r
-\r
-\r
-\r
-\r
-\section{Conclusion and Future Works}\r
-\label{sec:Conclusion and Future Works}\r
-\r
-In this paper  we have studied the problem of  Perimeter-based Coverage Optimization in\r
-WSNs. We have designed  a new protocol, called Perimeter-based  Coverage Optimization, which\r
-schedules nodes'  activities (wake up  and sleep  stages) with the  objective of\r
-maintaining a  good coverage ratio  while maximizing the network  lifetime. This\r
-protocol is  applied in a distributed  way in regular subregions  obtained after\r
-partitioning the area of interest in a preliminary step. It works in periods and\r
-is based on the resolution of an integer program to select the subset of sensors\r
-operating in active status for each period. Our work is original in so far as it\r
-proposes for  the first  time an  integer program  scheduling the  activation of\r
-sensors  based on  their perimeter  coverage level,  instead of  using a  set of\r
-targets/points to be covered.\r
-\r
-\r
-We  have carried out  several simulations  to  evaluate the  proposed protocol.   The\r
-simulation  results  show   that  PeCO  is  more   energy-efficient  than  other\r
-approaches, with respect to lifetime,  coverage ratio, active sensors ratio, and\r
-energy consumption.\r
-\r
-We plan to extend our framework so that the schedules are planned for multiple\r
-sensing periods.\r
-\r
-We also want  to improve our integer program to  take into account heterogeneous\r
-sensors  from both  energy  and node  characteristics point of views.\r
-\r
-Finally,  it   would  be   interesting  to  implement   our  protocol   using  a\r
-sensor-testbed to evaluate it in real world applications.\r
-\r
-\bibliographystyle{gENO}\r
-\bibliography{biblio}\r
-\r
-\r
-\end{document}\r
+% gENOguide.tex
+% v4.0 released April 2013
+
+\documentclass{gENO2e}
+
+\usepackage{indentfirst}
+\usepackage{color}
+\usepackage[algo2e,ruled,vlined]{algorithm2e}
+\begin{document}
+
+\title{{\itshape Perimeter-based Coverage Optimization \\
+  to Improve Lifetime in Wireless Sensor Networks}}
+
+\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}$
+  $^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, \\
+  University Bourgogne Franche-Comt\'e, Belfort, France}} \\ 
+  $^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}}
+}         
+         
+\maketitle
+
+\begin{abstract}
+The most important problem in a Wireless Sensor Network (WSN) is to optimize the
+use of its limited energy provision, so  that it can fulfill its monitoring task
+as  long as  possible. Among  known  available approaches  that can  be used  to
+improve  power  management,  lifetime coverage  optimization  provides  activity
+scheduling which ensures  sensing coverage while minimizing the  energy cost. An approach called Perimeter-based  Coverage Optimization protocol
+(PeCO) is proposed. It is a hybrid  of centralized and  distributed methods: the  region of
+interest  is  first  subdivided  into   subregions  and  the  protocol  is  then
+distributed among sensor  nodes in each subregion.  The novelty  of the approach
+lies essentially  in the  formulation of a  new mathematical  optimization model
+based  on  the  perimeter  coverage   level  to  schedule  sensors'  activities.
+Extensive simulation experiments demonstrate that PeCO can offer longer lifetime
+coverage for WSNs compared to other protocols.
+
+\begin{keywords}
+  Wireless Sensor Networks, Area Coverage, Energy efficiency, Optimization, Scheduling.
+\end{keywords}
+
+\end{abstract}
+
+\section{Introduction}
+\label{sec:introduction}
+
+The continuous progress in Micro  Electro-Mechanical Systems (MEMS) and wireless
+communication hardware has given rise to the opportunity of using large networks
+of      tiny       sensors,      called      Wireless       Sensor      Networks
+(WSN)~\citep{akyildiz2002wireless,puccinelli2005wireless}, to fulfill monitoring
+tasks.   A  WSN  consists  of  small low-powered  sensors  working  together  by
+communicating with one another through multi-hop radio communications. Each node
+can send the data  it collects in its environment, thanks to  its sensor, to the
+user by means of sink nodes. The features  of a WSN makes it suitable for a wide
+range of applications in areas  such as business, environment, health, industry,
+military, and so on~\citep{yick2008wireless}.  Typically, a sensor node contains
+three main components~\citep{anastasi2009energy}: a sensing unit able to measure
+physical,  chemical, or  biological  phenomena observed  in  the environment;  a
+processing unit which will process and store the collected measurements; a radio
+communication unit for data transmission and reception.
+
+The energy needed  by an active sensor node to  perform sensing, processing, and
+communication is provided by a power supply which is a battery. This battery has
+a limited energy provision and it may  be unsuitable or impossible to replace or
+recharge in most applications. Therefore it is necessary to deploy WSN with high
+density in order  to increase reliability and to exploit  node redundancy thanks
+to  energy-efficient activity  scheduling  approaches.  Indeed,  the overlap  of
+sensing areas can  be exploited to schedule alternatively some  sensors in a low
+power sleep mode and  thus save energy. Overall, the main  question that must be
+answered is: how is it possible to extend the lifetime coverage of a WSN as long
+as possible while ensuring a high level  of coverage?  These past few years many
+energy-efficient mechanisms have been suggested  to retain energy and extend the
+lifetime of the WSNs~\citep{rault2014energy}.
+
+This paper makes the following contributions :
+\begin{enumerate}
+\item A  framework is devised  to schedule  nodes to be  activated alternatively
+  such that  the network  lifetime is  prolonged while  ensuring that  a certain
+  level of coverage  is preserved.  A key  idea in the proposed  framework is to
+  exploit  spatial and  temporal  subdivision.  On  the one  hand,  the area  of
+  interest is  divided into several smaller  subregions and, on the  other hand,
+  the time line is divided into periods  of equal length.  In each subregion the
+  sensor nodes  will cooperatively  choose a leader  which will  schedule nodes'
+  activities,  and  this grouping  of  sensors  is  similar to  typical  cluster
+  architecture.
+\item A new  mathematical optimization model is proposed.  Instead  of trying to
+  cover a set of specified points/targets as  in most of the methods proposed in
+  the literature, a  mixed-integer program based on  the perimeter
+  coverage of each sensor is formulated.  The model  involves integer variables to capture the
+  deviations  between the  actual  level  of coverage  and  the required  level.
+  Hence, an  optimal schedule will be  obtained by minimizing a  weighted sum of
+  these deviations.
+\item Extensive  simulation experiments are  conducted using the  discrete event
+  simulator OMNeT++,  to demonstrate  the efficiency of  the PeCO protocol.   The  PeCO  protocol has been compared to  two approaches  found  in  the  literature:
+  DESK~\citep{ChinhVu} and GAF~\citep{xu2001geography}, and also to the
+  protocol DiLCO published in~\citep{Idrees2}. DiLCO  uses the same framework as
+  PeCO but is based on another optimization model for sensor scheduling.
+\end{enumerate}
+
+The rest of the paper is organized as follows.  In the next section some related
+work in the  field is reviewed. Section~\ref{sec:The  PeCO Protocol Description}
+is devoted to the PeCO protocol  description and Section~\ref{cp} focuses on the
+coverage model  formulation which is used  to schedule the activation  of sensor
+nodes.  Section~\ref{sec:Simulation  Results and Analysis}  presents simulations
+results and discusses the comparison  with other approaches. Finally, concluding
+remarks  are  drawn  and  some  suggestions   are  given  for  future  works  in
+Section~\ref{sec:Conclusion and Future Works}.
+
+\section{Related Literature}
+\label{sec:Literature Review}
+
+This section  summarizes some related  works regarding the coverage  problem and
+presents  specific aspects  of the  PeCO protocol  common with  other literature
+works.
+
+The most  discussed coverage problems in  literature can be classified  in three
+categories~\citep{li2013survey}   according  to   their  respective   monitoring
+objective.  Hence, area  coverage \citep{Misra} means that every  point inside a
+fixed area must be monitored, while target coverage~\citep{yang2014novel} refers
+to  the objective  of coverage  for a  finite number  of discrete  points called
+targets,   and   barrier  coverage~\citep{HeShibo,kim2013maximum}   focuses   on
+preventing  intruders   from  entering   into  the   region  of   interest.   In
+\citep{Deng2012} authors  transform the  area coverage  problem into  the target
+coverage one, taking into account the intersection points among disks of sensors
+nodes   or    between   disks    of   sensor    nodes   and    boundaries.    In
+\citep{huang2005coverage} authors  prove that if  the perimeters of  the sensors
+are sufficiently covered it will be the case for the whole area. They provide an
+algorithm  in  $O(nd~log~d)$ time  to  compute  the perimeter-coverage  of  each
+sensor.  $d$ denotes  the maximum  number  of sensors  that are  neighbors to  a
+sensor, and  $n$ is the  total number  of sensors in  the network. {\it  In PeCO
+  protocol, instead  of determining the level  of coverage of a  set of discrete
+  points, the optimization model is  based on checking the perimeter-coverage of
+  each sensor to activate a minimal number of sensors.}
+
+The major  approach to extend network  lifetime while preserving coverage  is to
+divide/organize the  sensors into a suitable  number of set covers  (disjoint or
+non-disjoint)  \citep{wang2011coverage},  where  each set  completely  covers  a
+region of interest,  and to successively activate these set covers. The network
+activity can be planned in advance and scheduled for the entire network lifetime
+or organized  in periods,  and the  set of  active sensor  nodes decided  at the
+beginning of each  period \citep{ling2009energy}. In fact,  many authors propose
+algorithms       working       in       such      a       periodic       fashion
+\citep{chin2007,yan2008design,pc10}.  Active node  selection is determined based
+on  the problem  requirements  (e.g.  area  monitoring,  connectivity, or  power
+efficiency).  For instance, \citet{jaggi2006}  address the problem of maximizing
+the lifetime  by dividing sensors  into the  maximum number of  disjoint subsets
+such  that each  subset  can ensure  both coverage  and  connectivity. A  greedy
+algorithm  is applied  once to  solve  this problem  and the  computed sets  are
+activated in succession to achieve  the desired network lifetime. {\it Motivated
+  by these works,  PeCO protocol works in periods, where  each period contains a
+  preliminary  phase  for information  exchange  and  decisions, followed  by  a
+  sensing phase where one cover set is in charge of the sensing task.}
+
+Various centralized  and distributed approaches, or  even a mixing of  these two
+concepts,    have   been    proposed    to   extend    the   network    lifetime
+\citep{zhou2009variable}.                      In                    distributed
+algorithms~\citep{ChinhVu,qu2013distributed,yangnovel}  each  sensor decides  of
+its own  activity scheduling after  an information exchange with  its neighbors.
+The main interest of such an approach  is to avoid long range communications and
+thus to reduce the energy dedicated to the communications.  Unfortunately, since
+each node has  information on its immediate neighbors only  (usually the one-hop
+ones),  it may  make a  bad decision  leading to  a global  suboptimal solution.
+Conversely,                                                          centralized
+algorithms~\citep{cardei2005improving,zorbas2010solving,pujari2011high}   always
+provide nearly  optimal solutions since the  algorithm has a global  view of the
+whole network.  The disadvantage of a  centralized method is obviously  its high
+cost in  communications needed to  transmit to a  single node, the  base station
+which will globally  schedule nodes' activities, data from all  the other sensor
+nodes in  the area.  The  price in communications can  be huge since  long range
+communications  will be  needed. In  fact  the larger  the WSN,  the higher  the
+communication  energy  cost.  {\it  In  order  to  be suitable  for  large-scale
+  networks, in  the PeCO protocol the  area of interest is  divided into several
+  smaller subregions, and in each one, a  node called the leader is in charge of
+  selecting the active  sensors for the current period.  Thus  the PeCO protocol
+  is scalable  and a globally distributed  method, whereas it is  centralized in
+  each subregion.}
+
+Various coverage scheduling algorithms have been developed these past few years.
+Many of  them, dealing with  the maximization of the  number of cover  sets, are
+heuristics.   These  heuristics involve  the  construction  of  a cover  set  by
+including in priority the sensor nodes  which cover critical targets, that is to
+say   targets   that  are   covered   by   the   smallest  number   of   sensors
+\citep{berman04,zorbas2010solving}.  Other approaches  are based on mathematical
+programming
+formulations~\citep{cardei2005energy,5714480,pujari2011high,Yang2014}        and
+dedicated  techniques (solving  with a  branch-and-bound algorithm  available in
+optimization  solver).  The  problem is  formulated as  an optimization  problem
+(maximization of the lifetime or number of cover sets) under target coverage and
+energy  constraints.   Column  generation   techniques,  well-known  and  widely
+practiced techniques for  solving linear programs with too  many variables, have
+also                                                                        been
+used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012column}.
+{\it In  the PeCO  protocol, each leader,  in charge of  a subregion,  solves an
+  integer program which  has a twofold objective: minimizing  the overcoverage and
+  the undercoverage of the perimeter of each sensor.}
+
+The  authors   in  \citep{Idrees2}  propose  a   Distributed  Lifetime  Coverage
+Optimization (DiLCO)  protocol, which  maintains the  coverage and  improves the
+lifetime  in WSNs.   It is  an  improved version  of a  research work  presented
+in~\citep{idrees2014coverage}.  First, the area  of interest is partitioned into
+subregions  using  a  divide-and-conquer  method. The  DiLCO  protocol  is  then
+distributed on the sensor  nodes in each subregion in a  second step. Hence this
+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 protocol,  a new
+  mathematical optimization model is proposed. Instead  of trying to cover a set
+  of specified points/targets as in the  DiLCO protocol, an integer
+  program based  on the perimeter  coverage of  each sensor is formulated. 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.}
+  
+\section{ The P{\scshape e}CO Protocol Description}
+\label{sec:The PeCO Protocol Description}
+
+
+\subsection{Assumptions and Models}
+\label{CI}
+
+A  WSN  consisting  of  $J$  stationary  sensor  nodes  randomly  and  uniformly
+distributed in  a bounded sensor field  is considered. The wireless  sensors are
+deployed in high density  to ensure initially a high coverage  ratio of the area
+of interest.  All  the sensor nodes are  supposed to be homogeneous  in terms of
+communication, sensing,  and processing capabilities and  heterogeneous from the
+energy provision  point of  view.  The  location information  is available  to a
+sensor node either  through hardware such as embedded GPS  or location discovery
+algorithms. A Boolean disk coverage model,  which is the most widely used sensor
+coverage model  in the  literature, is  considered and all  sensor nodes  have a
+constant sensing range $R_s$.  Thus, all the space points within a disk centered
+at a sensor with  a radius equal to the sensing range are  said to be covered by
+this sensor.  The communication range  $R_c$ is assumed to satisfy : $R_c
+\geq 2  \cdot R_s$.  In  fact, \citet{Zhang05}  proved that if  the transmission
+range fulfills the  previous hypothesis, the complete coverage of  a convex area
+implies connectivity among active nodes.
+
+The    PeCO   protocol    uses    the   same    perimeter-coverage   model    as
+\citet{huang2005coverage}. It can  be expressed as follows: a sensor  is said to
+be perimeter covered if all the points  on its perimeter are covered by at least
+one sensor other  than itself.  Authors \citet{huang2005coverage}  proved that a
+network area  is $k$-covered  (every point in  the area is  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).
+Figure~\ref{figure1}(a) shows the coverage of  sensor node~$0$.  On this figure,
+sensor~$0$  has nine  neighbors. For each neighbor  the two points
+resulting from  the intersection  of the  two sensing  areas have been reported  on  its perimeter  (the
+perimeter of the  disk covered by the  sensor~$0$).  These  points are
+denoted for neighbor~$i$ by $iL$ and  $iR$, respectively for left and right from
+a  neighboring point  of view.   The  resulting couples  of intersection  points
+subdivide the perimeter of sensor~$0$ into portions called arcs.
+
+\begin{figure}[ht!]
+  \centering
+  \begin{tabular}{@{}cr@{}}
+    \includegraphics[width=75mm]{figure1a.eps} & \raisebox{3.25cm}{(a)} \\
+    \includegraphics[width=75mm]{figure1b.eps} & \raisebox{2.75cm}{(b)}
+  \end{tabular}
+  \caption{(a) Perimeter  coverage of sensor node  0 and (b) finding  the arc of
+    $u$'s perimeter covered by $v$.}
+  \label{figure1}
+\end{figure} 
+
+Figure~\ref{figure1}(b)  describes the  geometric information  used to  find the
+locations of the  left and right points of  an arc on the perimeter  of a sensor
+node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the
+west  side of  sensor~$u$,  with  the following  respective  coordinates in  the
+sensing area~:  $(v_x,v_y)$ and $(u_x,u_y)$.  From the previous  coordinates the
+euclidean distance between nodes~$u$ and $v$ is computed as follows:
+$$
+  Dist(u,v)=\sqrt{(u_x - v_x)^2 + (u_y-v_y)^2},
+$$
+while the angle~$\alpha$ is obtained through the formula:
+ \[
+\alpha = \arccos \left(\frac{Dist(u,v)}{2R_s} \right).
+\] 
+The  arc  on the  perimeter  of~$u$  defined by  the  angular  interval $[\pi  -
+  \alpha,\pi + \alpha]$ is then said to be perimeter-covered by sensor~$v$.
+
+Every couple of intersection points is placed on the angular interval $[0,2\pi)$
+in  a  counterclockwise manner,  leading  to  a  partitioning of  the  interval.
+Figure~\ref{figure1}(a)  illustrates  the arcs  for  the  nine neighbors  of
+sensor $0$ and  Table~\ref{my-label} gives the position of  the corresponding arcs
+in  the interval  $[0,2\pi)$. More  precisely, the  points are
+ordered according  to the  measures of  the angles  defined by  their respective
+positions. The intersection points are  then visited one after another, starting
+from the first  intersection point  after  point~zero,  and  the maximum  level  of
+coverage is determined  for each interval defined by two  successive points. The
+maximum  level of  coverage is  equal to  the number  of overlapping  arcs.  For
+example, between~$5L$  and~$6L$ the maximum  level of  coverage is equal  to $3$
+(the value is highlighted in yellow  at the bottom of Figure~\ref{figure2}), which
+means that at most 2~neighbors can cover  the perimeter in addition to node $0$. 
+Table~\ref{my-label} summarizes for each coverage  interval the maximum level of
+coverage and  the sensor  nodes covering the  perimeter.  The  example discussed
+above is thus given by the sixth line of the table.
+
+\begin{figure*}[t!]
+\centering
+\includegraphics[width=0.95\linewidth]{figure2.eps}  
+\caption{Maximum coverage levels for perimeter of sensor node $0$.}
+\label{figure2}
+\end{figure*} 
+
+\begin{table}
+\tbl{Coverage intervals and contributing sensors for node 0 \label{my-label}}
+{\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
+\hline
+\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
+0.0291    & 1L                                                                        & 2L                                                        & 4                                                                     & 0                     & 1                     & 3                    & 4                    &                      \\ \hline
+0.104     & 2L                                                                        & 3R                                                        & 5                                                                     & 0                     & 1                     & 3                    & 4                    & 2                    \\ \hline
+0.3168    & 3R                                                                        & 4R                                                        & 4                                                                     & 0                     & 1                     & 4                    & 2                    &                      \\ \hline
+0.6752    & 4R                                                                        & 1R                                                        & 3                                                                     & 0                     & 1                     & 2                    &                      &                      \\ \hline
+1.8127    & 1R                                                                        & 5L                                                        & 2                                                                     & 0                     & 2                     &                      &                      &                      \\ \hline
+1.9228    & 5L                                                                        & 6L                                                        & 3                                                                     & 0                     & 2                     & 5                    &                      &                      \\ \hline
+2.3959    & 6L                                                                        & 2R                                                        & 4                                                                     & 0                     & 2                     & 5                    & 6                    &                      \\ \hline
+2.4258    & 2R                                                                        & 7L                                                        & 3                                                                     & 0                     & 5                     & 6                    &                      &                      \\ \hline
+2.7868    & 7L                                                                        & 8L                                                        & 4                                                                     & 0                     & 5                     & 6                    & 7                    &                      \\ \hline
+2.8358    & 8L                                                                        & 5R                                                        & 5                                                                     & 0                     & 5                     & 6                    & 7                    & 8                    \\ \hline
+2.9184    & 5R                                                                        & 7R                                                        & 4                                                                     & 0                     & 6                     & 7                    & 8                    &                      \\ \hline
+3.3301    & 7R                                                                        & 9R                                                        & 3                                                                     & 0                     & 6                     & 8                    &                      &                      \\ \hline
+3.9464    & 9R                                                                        & 6R                                                        & 4                                                                     & 0                     & 6                     & 8                    & 9                    &                      \\ \hline
+4.767     & 6R                                                                        & 3L                                                        & 3                                                                     & 0                     & 8                     & 9                    &                      &                      \\ \hline
+4.8425    & 3L                                                                        & 8R                                                        & 4                                                                     & 0                     & 3                     & 8                    & 9                    &                      \\ \hline
+4.9072    & 8R                                                                        & 4L                                                        & 3                                                                     & 0                     & 3                     & 9                    &                      &                      \\ \hline
+5.3804    & 4L                                                                        & 9R                                                        & 4                                                                     & 0                     & 3                     & 4                    & 9                    &                      \\ \hline
+5.9157    & 9R                                                                        & 1L                                                        & 3                                                                     & 0                     & 3                     & 4                    &                      &                      \\ \hline
+\end{tabular}}
+
+
+\end{table}
+
+In  the  PeCO protocol,  the  scheduling  of  the  sensor nodes'  activities  is
+formulated    with    a    mixed-integer     program    based    on    coverage
+intervals~\citep{doi:10.1155/2010/926075}.  The  formulation   of  the  coverage
+optimization problem is  detailed in~Section~\ref{cp}.  Note that  when a sensor
+node  has a  part of  its sensing  range outside  the WSN  sensing field,  as in
+Figure~\ref{figure3}, the maximum coverage level for this arc is set to $\infty$
+and  the  corresponding  interval  will  not   be  taken  into  account  by  the
+optimization algorithm.
+
+%\newpage
+\begin{figure}[h!]
+\centering
+\includegraphics[width=57.5mm]{figure3.eps}  
+\caption{Sensing range outside the WSN's area of interest.}
+\label{figure3}
+\end{figure}
+
+\vspace{-0.25cm}
+
+\subsection{Main Idea}
+
+The WSN area of  interest is, in a first step,  divided into regular homogeneous
+subregions using a  divide-and-conquer algorithm. In a second  step the protocol
+will  be executed  in  a distributed  way in  each  subregion simultaneously  to
+schedule nodes' activities  for one sensing period. Sensor nodes  are assumed to
+be deployed  almost uniformly over the  region. The regular subdivision  is made
+such that the number of hops between  any pairs of sensors inside a subregion is
+less than or equal to 3.
+
+As shown  in Figure~\ref{figure4}, node  activity scheduling is produced  by the
+proposed protocol  in a periodic manner.  Each period is divided  into 4 stages:
+Information  (INFO)  Exchange,  Leader  Election, Decision  (the  result  of  an
+optimization problem),  and Sensing.  For each  period there is exactly  one set
+cover responsible for  the sensing task.  Protocols based on  a periodic scheme,
+like PeCO, are more robust against an  unexpected node failure. On the one hand,
+if a  node failure is discovered  before taking the decision,  the corresponding
+sensor node will  not be considered by the optimization  algorithm. On the other
+hand, if the sensor failure happens after  the decision, the sensing task of the
+network will be temporarily affected: only  during the period of sensing until a
+new period starts, since a new set cover will take charge of the sensing task in
+the next period. The energy consumption and some other constraints can easily be
+taken  into  account since  the  sensors  can  update  and then  exchange  their
+information (including their  residual energy) at the beginning  of each period.
+However, the pre-sensing  phases (INFO Exchange, Leader  Election, and Decision)
+are energy consuming, even for nodes that will not join the set cover to monitor
+the area. Sensing  period duration is adapted according to  the QoS requirements
+of the application.
+
+\begin{figure}[t!]
+\centering
+\includegraphics[width=80mm]{figure4.eps}  
+\caption{PeCO protocol.}
+\label{figure4}
+\end{figure} 
+
+Two types of packets used by the PeCO protocol are defined:
+\begin{itemize} 
+\item INFO  packet: sent  by each  sensor node to  all the  nodes inside  a same
+  subregion for information exchange.
+\item ActiveSleep packet: sent  by the leader to all the  nodes in its subregion
+  to transmit to  them their respective status (stay Active  or go Sleep) during
+  the sensing phase.
+\end{itemize}
+
+Five statuses are possible for a sensor node in the network:
+\begin{itemize} 
+\item LISTENING: waits for a decision (to be active or not);
+\item COMPUTATION: executes the optimization algorithm as leader to
+  determine the activities scheduling;
+\item ACTIVE: node is sensing;
+\item SLEEP: node is turned off;
+\item COMMUNICATION: transmits or receives packets.
+\end{itemize}
+
+\subsection{PeCO Protocol Algorithm}
+
+The  pseudocode implementing  the  protocol  on a  node  is  given below.   More
+precisely, Algorithm~\ref{alg:PeCO}  gives a  brief description of  the protocol
+applied by a sensor node $s_k$ where $k$ is the node index in the WSN.
+
+
+\begin{algorithm2e}      
+  \label{alg:PeCO}
+  \caption{PeCO pseudocode}
+  \eIf{$RE_k \geq E_{th}$}{
+    $s_k.status$ = COMMUNICATION\;
+    Send $INFO()$ packet to other nodes in subregion\;
+    Wait $INFO()$ packet from other nodes in subregion\;
+    Update K.CurrentSize\;
+    LeaderID = Leader election\;
+    \eIf{$s_k.ID = LeaderID$}{
+      $s_k.status$ = COMPUTATION\;
+      \If{$ s_k.ID $ is Not previously selected as a Leader}{
+        Execute the perimeter coverage model\;
+      }
+      \eIf{($s_k.ID $ is the same Previous Leader) {\bf and} \\
+        \indent (K.CurrentSize = K.PreviousSize)}{
+        Use the same previous cover set for current sensing stage\;
+      }{
+        Update $a^j_{ik}$; prepare data for IP~Algorithm\;
+        $\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$)\;
+        K.PreviousSize = K.CurrentSize\;
+      }
+      $s_k.status$ = COMMUNICATION\;
+      Send $ActiveSleep()$ to each node $l$ in subregion\;
+      Update $RE_k $\;
+    }{
+      $s_k.status$ = LISTENING\;
+      Wait $ActiveSleep()$ packet from the Leader\;
+      Update $RE_k $\;
+    }
+  }{
+    Exclude $s_k$ from entering in the current sensing stage\;
+  }
+\end{algorithm2e}
+
+In this  algorithm, $K.CurrentSize$ and $K.PreviousSize$  respectively represent
+the current number and the previous number  of living nodes in the subnetwork of
+the  subregion.   At the  beginning  of  the  first period  $K.PreviousSize$  is
+initialized to  zero.  Initially,  the sensor node  checks its  remaining energy
+$RE_k$, which must be greater than  a threshold $E_{th}$ in order to participate
+in  the current  period.   Each  sensor node  determines  its  position and  its
+subregion using an  embedded GPS or a location discovery  algorithm. After that,
+all the sensors collect position  coordinates, remaining energy, sensor node ID,
+and the number of their one-hop  live neighbors during the information exchange.
+Both INFO packet and ActiveSleep packet contain two parts: header and data payload. The sensor ID is included in the header, where the header size is 8 bits. The data part includes position coordinates (64 bits), remaining energy (32 bits), and the number of one-hop live neighbors (8 bits). Therefore the size of the INFO packet is 112 bits. The ActiveSleep packet is 16 bits size, 8 bits for the header and 8 bits for data part that includes only sensor status (0 or 1).
+The sensors  inside a same  region cooperate to  elect a leader.   The selection
+criteria for the leader are (in order  of priority):
+\begin{enumerate}
+\item larger number of neighbors;
+\item larger  remaining energy;
+\item and then,  in case  of equality,  larger indexes.
+\end{enumerate}
+Once chosen, the leader collects information  to formulate and solve the integer
+program  which allows  to build  the set  of active  sensors in  the sensing
+stage.
+
+\section{Perimeter-based Coverage Problem Formulation}
+\label{cp}
+
+In  this  section,  the   perimeter-based  coverage  problem  is  mathematically
+formulated.    It    has    been    proved   to    be    a    NP-hard    problem
+by \citep{doi:10.1155/2010/926075}. Authors  study the coverage of  the perimeter
+of a  large object requiring  to be monitored.  For the proposed  formulation in
+this paper,  the large  object to  be monitored  is the  sensor itself  (or more
+precisely its sensing area).
+
+The following notations are used  throughout the section.
+
+First, the following sets:
+\begin{itemize}
+\item $S$ represents the set of sensor nodes;
+\item $A \subseteq S $ is the subset of alive sensors;
+\item  $I_j$  designates  the  set  of  coverage  intervals  (CI)  obtained  for
+  sensor~$j$.
+\end{itemize}
+$I_j$ refers to the set of  coverage intervals which has been defined according
+to the  method introduced in  Subsection~\ref{CI}. For a coverage  interval $i$,
+let $a^j_{ik}$ denote  the indicator function of whether  sensor~$k$ is involved
+in coverage interval~$i$ of sensor~$j$, that is:
+\begin{equation}
+a^j_{ik} = \left \{ 
+\begin{array}{lll}
+  1 & \mbox{if sensor $k$ is involved in the } \\
+       &       \mbox{coverage interval $i$ of sensor $j$}, \\
+  0 & \mbox{otherwise.}\\
+\end{array} \right.
+\end{equation}
+Note that $a^k_{ik}=1$ by definition of the interval.
+
+Second,  several variables  are defined.   Hence, each  binary variable  $X_{k}$
+determines the  activation of sensor  $k$ in the  sensing phase ($X_k=1$  if the
+sensor $k$ is active or 0 otherwise).   $M^j_i$ is a variable which measures the
+undercoverage for the coverage interval  $i$ corresponding to sensor~$j$. In the
+same  way, the  overcoverage for  the  same coverage  interval is  given by  the
+variable $V^j_i$.
+
+To sustain a  level of coverage equal  to $l$ all along the  perimeter of sensor
+$j$, at  least $l$  sensors involved in  each coverage interval  $i \in  I_j$ of
+sensor $j$ have  to be active.  According to the  previous notations, the number
+of  active sensors  in the  coverage  interval $i$  of  sensor $j$  is given  by
+$\sum_{k \in A} a^j_{ik} X_k$.  To extend the network lifetime, the objective is
+to activate  a minimal number  of sensors in each  period to ensure  the desired
+coverage level. As the number of  alive sensors decreases, it becomes impossible
+to reach  the desired level  of coverage  for all coverage  intervals. Therefore
+variables  $M^j_i$ and  $V^j_i$ are  introduced as  a measure  of the  deviation
+between the  desired number  of active  sensors in a  coverage interval  and the
+effective number.  And these deviations are minimized, first  to force the
+activation of a minimal number of  sensors to ensure the desired coverage level,
+and if  the desired level  cannot be completely  satisfied, to reach  a coverage
+level as close as possible to the desired one.
+
+The coverage optimization problem can then be mathematically expressed as follows:
+\begin{equation}
+  \begin{aligned}
+    \text{Minimize } & \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i ) \\
+    \text{Subject to:} & \\
+    & \sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i  \geq l \quad \forall i \in I_j, \forall j \in S  \\
+    & \sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i  \leq l \quad \forall i \in I_j, \forall j \in S \\
+    & X_{k} \in \{0,1\}, \forall k \in A \\
+    & M^j_i, V^j_i \in \mathbb{R}^{+} 
+  \end{aligned}
+\end{equation}
+
+
+If a given level of coverage $l$ is  required for one sensor, the sensor is said
+to be undercovered (respectively overcovered) if the level of coverage of one of
+its  CI  is  less  (respectively  greater)  than $l$.   If  the  sensor  $j$  is
+undercovered, there exists at least one of its CI (say $i$) for which the number
+of active  sensors (denoted by $l^{i}$)  covering this part of  the perimeter is
+less than $l$ and in this case : $M_{i}^{j}=l-l^{i}$, $V_{i}^{j}=0$. Conversely,
+if the sensor $j$ is overcovered, there exists  at least one of its CI (say $i$)
+for which the  number of active sensors (denoted by  $l^{i}$) covering this part
+of  the  perimeter  is  greater  than  $l$  and  in  this  case:  $M_{i}^{j}=0$,
+$V_{i}^{j}=l^{i}-l$.
+
+$\alpha^j_i$ and $\beta^j_i$  are nonnegative weights selected  according to the
+relative importance of satisfying the associated level of coverage. For example,
+weights associated with  coverage intervals of the specified part  of a region may
+be given by  a relatively larger magnitude than weights  associated with another
+region. This kind of mixed-integer program  is inspired from the model developed
+for   brachytherapy  treatment   planning  to optimize  dose   distribution
+\citep{0031-9155-44-1-012}.  The choice of the values for variables $\alpha$ and
+$\beta$  should be  made according  to the  needs of  the application.  $\alpha$
+should be  large enough  to prevent  undercoverage and so  to reach  the highest
+possible coverage ratio. $\beta$ should  be large enough to prevent overcoverage
+and so to activate a minimum  number of sensors.  The mixed-integer program must
+be solved  by the  leader in  each subregion  at the  beginning of  each sensing
+phase, whenever the environment has changed (new leader, death of some sensors).
+Note that  the number of  constraints in the  model is constant  (constraints of
+coverage  expressed for  all sensors),  whereas  the number  of variables  $X_k$
+decreases over periods, since only alive  sensors (sensors with enough energy to
+be alive during one sensing phase) are considered in the model.
+
+\section{Performance Evaluation and Analysis}  
+\label{sec:Simulation Results and Analysis}
+
+\subsection{Simulation Settings}
+
+The WSN  area of interest is  supposed to be divided  into 16~regular subregions
+and the  energy  consumption   model  used is described in previous
+work~\citep{Idrees2}.  Table~\ref{table3} gives the chosen parameters settings.
+
+\begin{table}[ht]
+\tbl{Relevant parameters for network initialization \label{table3}}{
+\centering
+\begin{tabular}{c|c}
+\hline
+Parameter & Value  \\ [0.5ex]
+\hline
+% inserts single horizontal line
+Sensing field & $(50 \times 25)~m^2 $ \\
+WSN size &  100, 150, 200, 250, and 300~nodes \\
+Initial energy  & in range 500-700~Joules \\  
+Sensing period & duration of 60 minutes \\
+$E_{th}$ & 36~Joules \\
+$R_s$ & 5~m \\     
+$R_c$ & 10~m \\   
+$\alpha^j_i$ & 0.6 \\
+$\beta^j_i$ & 0.4
+\end{tabular}}
+\end{table}
+
+To  obtain  experimental  results  which are  relevant,  simulations  with  five
+different node densities going from  100 to 300~nodes were performed considering
+each time 25~randomly  generated networks. The nodes are deployed  on a field of
+interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a
+high coverage ratio. Each node has an  initial energy level, in Joules, which is
+randomly drawn in  the interval $[500-700]$.  If its energy  provision reaches a
+value below  the threshold $E_{th}=36$~Joules,  the minimum energy needed  for a
+node to  stay active  during one period,  it will no  longer participate  in the
+coverage task. This value corresponds to the energy needed by the sensing phase,
+obtained by multiplying  the energy consumed in the active  state (9.72 mW) with
+the time in seconds for one period (3600 seconds), and adding the energy for the
+pre-sensing phases.  According  to the interval of initial energy,  a sensor may
+be active during at most 20 periods. the information exchange to update the coverage
+is executed every  hour, but the length  of the sensing period  could be reduced
+and adapted dynamically. On  the one hand a small sensing  period would allow the network to
+be more  reliable but would  have resulted in  higher communication costs.  On the
+other hand  the choice of a  long duration may  cause problems in case  of nodes
+failure during the sensing period.
+
+The values  of $\alpha^j_i$ and  $\beta^j_i$ have been  chosen to ensure  a good
+network coverage  and a longer  WSN lifetime.  Higher  priority is given  to the
+undercoverage (by setting the $\alpha^j_i$ with a larger value than $\beta^j_i$)
+so as  to prevent the non-coverage  for the interval~$i$ of  the sensor~$j$.  On
+the other hand, $\beta^j_i$ is assigned to a value which is slightly lower so as
+to minimize the  number of active sensor nodes which  contribute in covering the
+interval. Subsection~\ref{sec:Impact} investigates more deeply how the values of
+both parameters affect the performance of the PeCO protocol.
+
+The following performance metrics are used to evaluate the efficiency of the
+approach.
+\begin{itemize}
+\item {\bf Network Lifetime}: the lifetime  is defined as the time elapsed until
+  the  coverage  ratio  falls  below a  fixed  threshold.   $Lifetime_{95}$  and
+  $Lifetime_{50}$  denote, respectively,  the  amount of  time  during which  is
+  guaranteed a  level of coverage  greater than $95\%$  and $50\%$. The  WSN can
+  fulfill the expected  monitoring task until all its nodes  have depleted their
+  energy or if the network is no  more connected. This last condition is crucial
+  because without  network connectivity a  sensor may not be  able to send  to a
+  base station an event it has sensed.
+\item {\bf  Coverage Ratio (CR)} : it  measures how  well the  WSN is  able to
+  observe the area of interest. Here the sensor field is discretized as
+  a regular grid, which yields the following equation:
+  \begin{equation*}
+    \scriptsize
+    \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100
+  \end{equation*}
+  where $n$  is the  number of covered  grid points by  active sensors  of every
+  subregions during  the current sensing phase  and $N$ is total  number of grid
+  points in the sensing field. A layout of $N~=~51~\times~26~=~1326$~grid points
+  is considered in the simulations.
+\item {\bf Active Sensors Ratio (ASR)}: a  major objective of the proposed protocol is to
+  activate as  few nodes  as possible,  in order  to minimize  the communication
+  overhead and maximize the WSN lifetime. The active sensors ratio is defined as
+  follows:
+  \begin{equation*}
+   \scriptsize
+   \mbox{ASR}(\%) =  \frac{\sum\limits_{r=1}^R \mbox{$|A_r^p|$}}{\mbox{$|J|$}} \times 100
+  \end{equation*}
+  where $|A_r^p|$ is  the number of active  sensors in the subregion  $r$ in the
+  sensing period~$p$, $R$  is the number of subregions, and  $|J|$ is the number
+  of sensors in the network.
+  
+\item {\bf Energy Saving Ratio (ESR)}:this metric, which shows the ability of a protocol to save energy, is defined by:
+\begin{equation*}
+\scriptsize
+\mbox{ESR}(\%) = \frac{\mbox{Number of alive sensors during this round}}
+{\mbox{Total number of sensors in the network}} \times 100.
+\end{equation*}  
+\item {\bf Energy Consumption (EC)}: energy consumption can be seen as the total
+  energy  consumed by  the  sensors during  $Lifetime_{95}$ or  $Lifetime_{50}$,
+  divided by  the number of  periods. The value of  EC is computed  according to
+  this formula:
+  \begin{equation*} 
+    \scriptsize
+    \mbox{EC} = \frac{\sum\limits_{p=1}^{P} \left( E^{\mbox{com}}_p+E^{\mbox{list}}_p+E^{\mbox{comp}}_p  
+      + E^{a}_p+E^{s}_p \right)}{P},
+  \end{equation*}
+  where $P$ corresponds  to the number of periods. The  total energy consumed by
+  the  sensors  comes  through  taking   into  consideration  four  main  energy
+  factors. The first one, denoted $E^{\scriptsize \mbox{com}}_p$, represents the
+  energy consumption spent  by all the nodes for  wireless communications during
+  period $p$.  $E^{\scriptsize \mbox{list}}_p$,  the next factor, corresponds to
+  the energy  consumed by the sensors  in LISTENING status before  receiving the
+  decision to go active or sleep in period $p$.  $E^{\scriptsize \mbox{comp}}_p$
+  refers to  the energy  needed by  all the  leader nodes  to solve  the integer
+  program  during  a  period   (COMPUTATION  status).   Finally,  $E^a_{p}$  and
+  $E^s_{p}$ indicate  the energy consumed  by the  WSN during the  sensing phase
+  ({\it active} and {\it sleeping} nodes).
+\end{itemize}
+
+\subsection{Simulation Results}
+
+
+The PeCO  protocol has been implemented  in  OMNeT++~\citep{varga}   simulator in  order  to  assess and  analyze  its  performance. 
+The simulations were  run on a  DELL laptop  with an Intel  Core~i3~2370~M (1.8~GHz)
+processor (2 cores)  whose MIPS (Million Instructions Per Second)  rate is equal
+to 35330.  To be consistent with  the use of a  sensor node based on  Atmels AVR
+ATmega103L microcontroller (6~MHz)  having a MIPS rate equal to  6, the original
+execution  time on  the laptop  is multiplied  by 2944.2  $\left(\frac{35330}{2}
+\times \frac{1}{6} \right)$.  Energy consumption  is calculated according to the
+power consumption values, in milliWatt  per second, given in Table~\ref{tab:EC},
+based on the energy model proposed in \citep{ChinhVu}.
+
+\begin{table}[h]
+\centering
+\caption{Power consumption values}
+\label{tab:EC}
+\begin{tabular}{|l||cccc|}
+  \hline
+  {\bf Sensor status} & MCU & Radio & Sensing & {\it Power (mW)} \\
+  \hline
+  LISTENING & On & On & On & 20.05 \\
+  ACTIVE & On & Off & On & 9.72 \\
+  SLEEP & Off & Off & Off & 0.02 \\
+  COMPUTATION & On & On & On & 26.83 \\
+  \hline
+  \multicolumn{4}{|l}{Energy needed to send or receive a 2-bit content message} & 0.515 \\
+  \hline
+\end{tabular}
+\end{table}
+
+The modeling  language for Mathematical Programming  (AMPL)~\citep{AMPL} is used
+to generate  the integer program  instance in a  standard format, which  is then
+read and  solved by  the optimization  solver GLPK  (GNU linear  Programming Kit
+available in the public domain)  \citep{glpk} through a Branch-and-Bound method.
+In practice, executing GLPK on a sensor node is obviously intractable due to the
+huge memory  use. Fortunately, to  solve the  optimization problem, the use of
+commercial  solvers  like  CPLEX  \citep{iamigo:cplex}  which  are  less  memory
+consuming and more efficient is possible, or a lightweight heuristic may be implemented. For example,
+for  a WSN  of 200  sensor nodes,  a leader  node has  to deal  with constraints
+induced  by about  12 sensor  nodes.  In  that case,  to solve  the optimization
+problem  a memory  consumption of  more  than 1~MB  can be  observed with  GLPK,
+whereas less than 300~KB would be needed with CPLEX.
+
+Besides  PeCO,   three  other  protocols   will  be  evaluated   for  comparison
+purposes. The first one, called DESK,  is a fully distributed coverage algorithm
+proposed      by     \citep{ChinhVu}.       The      second     one,      called
+GAF~\citep{xu2001geography}, consists in dividing the monitoring area into fixed
+squares. Then, during  the decision phase, in each square,  one sensor is chosen
+to  remain  active   during  the  sensing  phase.   The  last   one,  the  DiLCO
+protocol~\citep{Idrees2}, is an improved version of a research work presented
+in~\citep{idrees2014coverage}. PeCO  and DiLCO protocols
+are based on  the same framework. In particular, the  choice for the simulations
+of  a partitioning  in  16~subregions was  made because  it  corresponds to  the
+configuration producing  the best results for  DiLCO. Of course, this  number of
+subregions should be adapted  according to the size of the  area of interest and
+the number of sensors.  The protocols  are distinguished from one another by the
+formulation of the integer program providing the set of sensors which have to be
+activated  in each  sensing  phase.  The DiLCO  protocol  tries  to satisfy  the
+coverage of a set of primary points,  whereas the objective of the PeCO protocol
+is  to reach  a desired  level of  coverage for  each sensor  perimeter. In the
+experimentations, a level of coverage equal to one ($l=1$) is chosen
+.
+
+\subsubsection{Coverage Ratio}
+
+Figure~\ref{figure5} shows  the average  coverage ratio  for 200  deployed nodes
+obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better
+coverage ratio with respectively 99.99\%,  99.91\%, and 99.02\%, compared to the
+98.76\% produced by PeCO for the first periods.  This is due to the fact that at
+the beginning the  DiLCO and PeCO protocols put more  redundant sensors to sleep
+status  (which slightly  decreases  the  coverage ratio),  while  the two  other
+protocols activate  more sensor  nodes.  Later,  when the  number of  periods is
+beyond~70, it  clearly appears that  PeCO provides  a better coverage  ratio and
+keeps a coverage ratio greater than 50\% for longer periods (15 more compared to
+DiLCO, 40 more compared to DESK). The  energy saved by PeCO in the early periods
+allows later a substantial increase of the coverage performance.
+
+\parskip 0pt    
+\begin{figure}[h!]
+\centering
+ \includegraphics[scale=0.5] {figure5.eps} 
+\caption{Coverage ratio for 200 deployed nodes.}
+\label{figure5}
+\end{figure} 
+
+\subsubsection{Active Sensors Ratio}
+
+Minimizing the number of active sensor nodes in  each period is essential to minimize the
+energy   consumption    and   thus    to   maximize   the    network   lifetime.
+Figure~\ref{figure6}  shows the  average  active nodes  ratio  for 200  deployed
+nodes. DESK and GAF have 30.36~\% and 34.96~\% active nodes for
+the first fourteen  rounds, and the DiLCO and PeCO protocols  compete perfectly with
+only 17.92~\%  and 20.16~\% active nodes  during the same time  interval. As the
+number of periods increases, the PeCO protocol has a lower number of active nodes in
+comparison with the  three other approaches and exhibits a  slow decrease, while
+keeping a greater coverage ratio as shown in Figure \ref{figure5}.
+
+\begin{figure}[h!]
+\centering
+\includegraphics[scale=0.5]{figure6.eps}  
+\caption{Active sensors ratio for 200 deployed nodes.}
+\label{figure6}
+\end{figure} 
+
+\subsubsection{Energy Saving Ratio} 
+
+
+The  simulation  results  show  that the  protocol  PeCO  saves
+  efficiently energy by  turning off some sensors during the  sensing phase.  As
+  shown in  Figure~\ref{figure7}, GAF provides  better energy saving than  PeCO for
+  the  first fifty  rounds. Indeed  GAF  balances the  energy consumption  among
+  sensor nodes inside each small fixed grid  and thus permits to extend the life
+  of sensors in each grid fairly. However, at  the same time it turns on a large
+  number of sensors and that leads  later to quickly deplete sensor's batteries.
+  DESK algorithm  shows less energy  saving compared with other  approaches.  In
+  comparison  with PeCO,  DiLCO protocol  usually provides  lower energy  saving
+  ratios. Moreover,  it can  be noticed  that after  round fifty,  PeCO protocol
+  exhibits the slowest decrease among all the considered protocols.
+
+\begin{figure}[h!]
+%\centering
+% \begin{multicols}{6}
+\centering
+\includegraphics[scale=0.5]{figure7.eps} %\\~ ~ ~(a)
+\caption{Energy Saving Ratio for 200 deployed nodes.}
+\label{figure7}
+\end{figure}
+
+\subsubsection{Energy Consumption}
+
+The  effect  of  the  energy  consumed by  the  WSN  during  the  communication,
+computation,  listening,  active, and  sleep  status  is studied  for  different
+network densities  and the  four approaches  compared.  Figures~\ref{figure8}(a)
+and (b)  illustrate the energy consumption  for different network sizes  and for
+$Lifetime_{95}$ and $Lifetime_{50}$.  The results show  that the PeCO protocol is the most
+competitive from the energy consumption point of view. As shown by both figures,
+PeCO consumes much less energy than the  other methods. One might think that the
+resolution of the integer program is too  costly in energy, but the results show
+that it is very beneficial to lose a  bit of time in the selection of sensors to
+activate.  Indeed  the optimization program  allows to reduce  significantly the
+number of  active sensors  and also  the energy consumption  while keeping  a good
+coverage level. The energy overhead  when increasing network
+size is the lowest with PeCO.
+
+\begin{figure}[h!]
+  \centering
+  \begin{tabular}{@{}cr@{}}
+    \includegraphics[scale=0.5]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\
+    \includegraphics[scale=0.5]{figure8b.eps} & \raisebox{2.75cm}{(b)}
+  \end{tabular}
+  \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.}
+  \label{figure8}
+\end{figure} 
+
+\subsubsection{Network Lifetime}
+
+In comparison with the   two   other  approaches, PeCO and DiLCO  protocols  are better for prolonging   the  network   lifetime.    In
+Figures~\ref{figure9}(a) and  (b), $Lifetime_{95}$  and $Lifetime_{50}$ are  shown for
+different  network  sizes.  As  can  be  seen  in  these figures,  the  lifetime
+increases with the size of the network,  and it is clearly larger for the DiLCO and
+PeCO protocols.  For  instance, for a network of 300~sensors  and coverage ratio
+greater than  50\%, it can be observed on Figure~\ref{figure9}(b) that the  lifetime is
+about  twice  longer with  PeCO  compared  to  the DESK protocol.   The  performance
+difference    is   more    obvious    in    Figure~\ref{figure9}(b)   than    in
+Figure~\ref{figure9}(a) because the gain induced by protocols (PeCO and DiLCO) increases with
+time, and the lifetime with a coverage over 50\% is far longer than with 95\%.
+
+\begin{figure}[h!]
+  \centering
+  \begin{tabular}{@{}cr@{}}
+    \includegraphics[scale=0.5]{figure9a.eps} & \raisebox{2.75cm}{(a)} \\  
+    \includegraphics[scale=0.5]{figure9b.eps} & \raisebox{2.75cm}{(b)}
+  \end{tabular}
+  \caption{Network Lifetime for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.}
+  \label{figure9}
+\end{figure} 
+
+Figure~\ref{figure10} compares the lifetime coverage  of the DiLCO and PeCO protocols
+for  different   coverage  ratios.   Protocol/70,  Protocol/80,
+Protocol/85, Protocol/90,  and Protocol/95 correspond to the  amount of time during  which the
+network  can satisfy  an  area  coverage greater  than  $70\%$, $80\%$,  $85\%$,
+$90\%$, and  $95\%$ respectively,  where the  term Protocol  refers to  DiLCO or
+PeCO. Indeed there are applications that do not require a 100\% coverage of the
+area to be  monitored. For example, forest
+fire application might require complete coverage
+in summer seasons while only require 80$\%$ of the area to be covered in rainy seasons~\citep{li2011transforming}. As another example, birds habit study requires only 70$\%$-coverage at nighttime when the birds are sleeping while requires 100$\%$-coverage at daytime when the birds are active~\citep{1279193}. 
+ PeCO always  outperforms DiLCO  for the  three  lower coverage  ratios, moreover  the
+improvements grow  with the network  size. DiLCO outperforms PeCO when the coverage ratio is required to be $>90\%$, but PeCO extends the network lifetime significantly when coverage ratio can be relaxed.
+
+\begin{figure}[h!]
+\centering \includegraphics[scale=0.55]{figure10.eps}
+\caption{Network lifetime for different coverage ratios.}
+\label{figure10}
+\end{figure} 
+
+\subsubsection{Impact of $\alpha$ and $\beta$ on PeCO's performance}
+\label{sec:Impact}
+
+Table~\ref{my-labelx}  shows network  lifetime results  for different  values of
+$\alpha$ and $\beta$, and  a network size equal to 200 sensor  nodes. On the one
+hand,  the choice  of $\beta  \gg \alpha$  prevents the  overcoverage, and  also
+limits the activation of a large number of sensors, but as $\alpha$ is low, some
+areas  may  be   poorly  covered.   This  explains  the   results  obtained  for
+$Lifetime_{50}$ with  $\beta \gg  \alpha$: a  large number  of periods  with low
+coverage ratio.  On the other hand, when  $\alpha \gg \beta$ is chosen, 
+the coverage is  favored even if some areas may  be overcovered, so a high coverage ratio is
+reached,  but a  large number  of sensors  are activated  to achieve  this goal.
+Therefore  the  network  lifetime  is  reduced.   The  choice  $\alpha=0.6$  and
+$\beta=0.4$ seems to  achieve the best compromise between  lifetime and coverage
+ratio.   That explains  why  this  setting  has been chosen for the  experiments
+presented in the previous subsections.
+
+
+
+\begin{table}[h]
+\centering
+\caption{The impact of $\alpha$ and $\beta$ on PeCO's performance}
+\label{my-labelx}
+\begin{tabular}{|c|c|c|c|}
+\hline
+$\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
+0.0 & 1.0 & 151 & 0 \\ \hline
+0.1 & 0.9 & 145 & 0 \\ \hline
+0.2 & 0.8 & 140 & 0 \\ \hline
+0.3 & 0.7 & 134 & 0 \\ \hline
+0.4 & 0.6 & 125 & 0 \\ \hline
+0.5 & 0.5 & 118 & 30 \\ \hline
+{\bf 0.6} & {\bf 0.4} & {\bf 94} & {\bf 57} \\ \hline
+0.7 & 0.3 & 97 & 49 \\ \hline
+0.8 & 0.2 & 90 & 52 \\ \hline
+0.9 & 0.1 & 77 & 50 \\ \hline
+1.0 & 0.0 & 60 & 44 \\ \hline
+\end{tabular}
+\end{table}
+
+
+\section{Conclusion and Future Works}
+\label{sec:Conclusion and Future Works}
+
+In this paper the problem of perimeter coverage optimization in
+WSNs has been studied.  A new  protocol called  Perimeter-based  Coverage
+Optimization is designed. This protocol 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  is based on the  resolution of an integer program  to select the
+subset  of sensors  operating in  active status  for each  period.  This  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. Several simulations have
+been carried out 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.
+
+This framework will be extented so that the schedules  are planned for multiple
+sensing  periods. The  integer program  would be improved to take  into
+account heterogeneous sensors from both energy and node characteristics point of
+views.  Finally, it would be interesting  to implement the PeCO protocol using a
+sensor-testbed to evaluate it in real world applications.
+
+\subsection*{Acknowledgments}
+The  authors  are   deeply  grateful  to  the  anonymous   reviewers  for  their
+constructive advice,  which improved the  technical quality  of the paper.  As a
+Ph.D.   student, Ali  Kadhum Idrees  would  like to  gratefully acknowledge  the
+University of  Babylon - Iraq  for financial support  and Campus France  for the
+received support. This work is also partially funded by the Labex ACTION program
+(contract ANR-11-LABX-01-01).  
+\bibliographystyle{gENO}
+\bibliography{biblio} %articleeo
+
+\end{document}