X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/LiCO.git/blobdiff_plain/d713a949431c9d95cd50776edaf8225fbfd7cee1..2b16e2d89b01a6fdda8ae3ccfe3b8fb7085c4dcb:/PeCO-EO/articleeo.tex?ds=inline

diff --git a/PeCO-EO/articleeo.tex b/PeCO-EO/articleeo.tex
index c0c6f7b..d4ae9d9 100644
--- a/PeCO-EO/articleeo.tex
+++ b/PeCO-EO/articleeo.tex
@@ -1,865 +1,991 @@
-% gENOguide.tex
-% v4.0 released April 2013
-
-\documentclass{gENO2e}
-%\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
-%\renewcommand{\algorithmcfname}{ALGORITHM}
-\begin{document}
-
-%\jvol{00} \jnum{00} \jyear{2013} \jmonth{April}
-
-%\articletype{GUIDE}
-
-\title{{\itshape Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}}
-
-\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}$
-$^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte,
-          Belfort, France}};}
-
-
-\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. We propose such an approach called Perimeter-based Coverage Optimization
-protocol (PeCO). It is a  hybrid of centralized and distributed methods: the
-region of interest is first subdivided into subregions and our protocol is then
-distributed among sensor nodes in each  subregion.
-The novelty of our 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 in comparison with some other protocols.
-
-\begin{keywords}Wireless Sensor Networks, Area Coverage, Energy efficiency, Optimization, Scheduling.
-\end{keywords}
-
-\end{abstract}
-
-
-\section{Introduction}
-\label{sec:introduction}
-
-\noindent The continuous progress in Micro Electro-Mechanical Systems (MEMS) and
-wireless communication hardware  has given rise to the opportunity  to use 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 made  it suitable for a wide
-range of application  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 receiving.
-
-The energy needed  by an active sensor node to  perform sensing, processing, and
-communication is supplied 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 it 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 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 We have devised a framework 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  our 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 We have proposed a new mathematical  optimization model.  Instead of  trying to
-  cover a set of specified points/targets as  in most of the methods proposed in
-  the literature, we formulate an integer program based on perimeter coverage of
-  each sensor.  The  model involves integer variables to  capture the deviations
-  between  the actual  level of  coverage and  the required  level.  Hence, an
-  optimal scheduling  will be  obtained by  minimizing a  weighted sum  of these
-  deviations.
-\item We have conducted extensive simulation  experiments, using the  discrete event
-  simulator OMNeT++, to demonstrate the  efficiency of our protocol. We have compared
-  our   PeCO   protocol   to   two   approaches   found   in   the   literature:
-  DESK~\citep{ChinhVu} and  GAF~\citep{xu2001geography}, and also to  our previous
-  work published in~\citep{Idrees2} which is  based on another optimization model
-  for sensor scheduling.
-\end{enumerate}
-
-
-
-
-
-
-The rest  of the paper is  organized as follows.  In the next section  we review
-some related work in the  field. 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}
-
-\noindent  In  this section,  we  summarize  some  related works  regarding  the
-coverage problem and  distinguish our PeCO protocol from the  works presented in
-the literature.
-
-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    disk   of    sensor   nodes    and   boundaries.     In
-\citep{Huang:2003:CPW:941350.941367}  authors prove  that  if  the perimeters  of
-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,  where  $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, our  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
-activate these set  covers successively. 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  is decided at the beginning  of each period
-\citep{ling2009energy}.  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.   
-\citet{chin2007},  \citet{yan2008design}, \citet{pc10},  propose  algorithms
-working in a periodic fashion where a  cover set is computed at the beginning of
-each period.   {\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{Tian02,yangnovel,ChinhVu,qu2013distributed} 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 only information on  its immediate neighbors (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  or close to  optimal solution 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 WNS  is, the
-higher the  communication and  thus the energy  cost are.   {\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 our  protocol is  scalable  and is 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: minimize the overcoverage and the undercoverage
-  of the perimeter of each sensor.}
-
-
-
-\section{ The P{\scshape e}CO Protocol Description}
-\label{sec:The PeCO Protocol Description}
-
-\noindent  In  this  section,  we  describe in  details  our Perimeter-based  Coverage
-Optimization protocol.  First we present the  assumptions we made and the models
-we considered (in particular the perimeter coverage one), second we describe the
-background idea of our protocol, and third  we give the outline of the algorithm
-executed by each node.
-
-
-\subsection{Assumptions and Models}
-\label{CI}
-
-\noindent 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.  We  assume that all the  sensor nodes are 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.   We  assume  that  each  sensor  node  can  directly  transmit  its
-measurements to  a mobile  sink node.  For  example, a sink  can be  an unmanned
-aerial  vehicle  (UAV)  flying  regularly  over  the  sensor  field  to  collect
-measurements from sensor nodes. A mobile sink node collects the measurements and
-transmits them to the base station.   We consider a Boolean disk coverage model,
-which is the most  widely used sensor coverage model in  the literature, 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. We also assume  that the communication range
-$R_c$ satisfies $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.  They  proved that  a network  area is
-$k$-covered 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, we can  see that sensor~$0$ has  nine neighbors and we  have reported on
-its  perimeter (the  perimeter  of the  disk  covered by  the  sensor) for  each
-neighbor  the  two  points  resulting  from the intersection  of  the  two  sensing
-areas. These points are denoted for  neighbor~$i$ by $iL$ and $iR$, respectively
-for  left and  right from  a neighboing  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 we can
-compute the euclidean distance between nodes~$u$ and $v$: $Dist(u,v)=\sqrt{\vert
-  u_x  - v_x  \vert^2 +  \vert u_y-v_y  \vert^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 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  figure~\ref{figure2} gives the position of  the corresponding arcs
-in  the interval  $[0,2\pi]$. More  precisely, we  can see  that 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=127.5mm]{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 sensor 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 an
-integer program  based on  coverage intervals. 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=62.5mm]{figure3.eps}  
-\caption{Sensing range outside the WSN's area of interest.}
-\label{figure3}
-\end{figure} 
-
-
-\subsection{The Main Idea}
-
-\noindent 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
-our  protocol  will  be  executed  in   a  distributed  way  in  each  subregion
-simultaneously to schedule nodes' activities for one sensing period.
-
-As  shown in  figure~\ref{figure4}, node  activity  scheduling is  produced by  our
-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.
-
-\begin{figure}[t!]
-\centering
-\includegraphics[width=80mm]{figure4.eps}  
-\caption{PeCO protocol.}
-\label{figure4}
-\end{figure} 
-
-We define two types of packets to be used by PeCO protocol:
-
-\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
-  sensing phase.
-\end{itemize}
-
-
-Five status 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}
-
-\noindent 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{algorithm}      
- % \KwIn{all the parameters related to information exchange}
-%  \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)}
-%  \BlankLine
-  %\emph{Initialize the sensor node and determine it's position and subregion} \; 
-  
-\noindent{\bf If} $RE_k \geq E_{th}$ {\bf then}\\
-\hspace*{0.6cm} \emph{$s_k.status$ = COMMUNICATION;}\\
-\hspace*{0.6cm}  \emph{Send $INFO()$ packet to other nodes in subregion;}\\
-\hspace*{0.6cm}  \emph{Wait $INFO()$ packet from other nodes in subregion;}\\
-\hspace*{0.6cm} \emph{Update K.CurrentSize;}\\
-\hspace*{0.6cm}  \emph{LeaderID = Leader election;}\\
-\hspace*{0.6cm} {\bf If} $ s_k.ID = LeaderID $ {\bf then}\\
-\hspace*{1.2cm}   \emph{$s_k.status$ = COMPUTATION;}\\
-\hspace*{1.2cm}{\bf If} \emph{$ s_k.ID $ is Not previously selected as a Leader} {\bf then}\\
-\hspace*{1.8cm} \emph{ Execute the perimeter coverage model;}\\
-\hspace*{1.2cm} {\bf end}\\
-\hspace*{1.2cm}{\bf If} \emph{($s_k.ID $ is the same Previous Leader)~And~(K.CurrentSize = K.PreviousSize)}\\
-\hspace*{1.8cm} \emph{ Use the same previous cover set for current sensing stage;}\\
-\hspace*{1.2cm}  {\bf end}\\
-\hspace*{1.2cm}  {\bf else}\\
-\hspace*{1.8cm}\emph{Update $a^j_{ik}$; prepare data for IP~Algorithm;}\\
-\hspace*{1.8cm} \emph{$\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$);}\\
-\hspace*{1.8cm} \emph{K.PreviousSize = K.CurrentSize;}\\
-\hspace*{1.2cm}  {\bf end}\\
-\hspace*{1.2cm}\emph{$s_k.status$ = COMMUNICATION;}\\
-\hspace*{1.2cm}\emph{Send $ActiveSleep()$ to each node $l$ in subregion;}\\
-\hspace*{1.2cm}\emph{Update $RE_k $;}\\
-\hspace*{0.6cm}  {\bf end}\\
-\hspace*{0.6cm}  {\bf else}\\
-\hspace*{1.2cm}\emph{$s_k.status$ = LISTENING;}\\
-\hspace*{1.2cm}\emph{Wait $ActiveSleep()$ packet from the Leader;}\\
-\hspace*{1.2cm}\emph{Update $RE_k $;}\\
-\hspace*{0.6cm}  {\bf end}\\
-{\bf end}\\
-{\bf else}\\
-\hspace*{0.6cm} \emph{Exclude $s_k$ from entering in the current sensing stage;}\\
-{\bf end}\\
-\label{alg:PeCO}
-\end{algorithm}
-
-
-
-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.  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.  The sensors
-inside a same region cooperate to elect a leader. The selection criteria for the
-leader, in order of priority,  are: larger numbers of neighbors, larger remaining
-energy, and  then in case  of equality, larger  index.  Once chosen,  the leader
-collects information to formulate and  solve the integer program which allows to
-construct the set of active sensors in the sensing stage.
-
-
-\section{Perimeter-based Coverage Problem Formulation}
-\label{cp}
-
-\noindent In this  section, the coverage model is  mathematically formulated. We
-start  with a  description of the notations that will  be used  throughout the
-section.\\
-First, we have the following sets:
-\begin{itemize}
-\item $S$ represents the set of WSN 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 have been defined according
-to the  method introduced in  subsection~\ref{CI}. For a coverage  interval $i$,
-let $a^j_{ik}$ denotes  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,  we define  several binary  and integer  variables.  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  an integer
-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$.
-
-If we decide to sustain a level of coverage equal to $l$ all along the perimeter
-of sensor  $j$, we have  to ensure  that at least  $l$ sensors involved  in each
-coverage  interval $i  \in I_j$  of  sensor $j$  are 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 we use variables  $M^j_i$ and $V^j_i$ as a measure
-of the  deviation between  the desired  number of active  sensors in  a coverage
-interval and  the effective  number. And  we try  to minimize  these deviations,
-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.
-
-
-
-
-Our coverage optimization problem can then be mathematically expressed as follows: 
-
-\begin{equation} 
-\left \{
-\begin{array}{ll}
-\min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\
-\textrm{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
-\end{array}
-\right.
-\end{equation}
-
-$\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 a specified part  of a region may
-be  given by a  relatively larger  magnitude than  weights associated  with another
-region. This  kind of integer program  is inspired from the  model developed for
-brachytherapy treatment planning  for optimizing dose  distribution
-\citep{0031-9155-44-1-012}. The 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 we
-consider only alive  sensors (sensors with enough energy to  be alive during one
-sensing phase) 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 we use the same energy consumption than in our 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   \\     
-
-$\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 more  participate in  the
-coverage task. This value corresponds to the energy needed by the sensing phase,
-obtained by multiplying  the energy consumed in 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 values  of $\alpha^j_i$ and  $\beta^j_i$ have been  chosen to ensure  a good
-network coverage and a longer WSN lifetime.  We have given a higher priority 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,  we have assigned to
-$\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute
-in covering the interval.
-
-We introduce the following performance metrics to evaluate the efficiency of our
-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. In our  case, we discretized the sensor field as
-  a regular grid, which yields the following equation:
-  
-
-\[
-    \scriptsize
-    \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100
-\]
-
-
-  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.  In  our simulations  we have  set a  layout of
-  $N~=~51~\times~26~=~1326$~grid points.
-\item {\bf Active Sensors Ratio (ASR)}: a  major objective of our 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:
- 
-\[
-    \scriptsize
-    \mbox{ASR}(\%) =  \frac{\sum\limits_{r=1}^R \mbox{$|A_r^p|$}}{\mbox{$|S|$}} \times 100
-\]
-
-  where $|A_r^p|$ is  the number of active  sensors in the subregion  $r$ in the
-  current sensing period~$p$, $|S|$ is the number of sensors in the network, and
-  $R$ is the number of subregions.
-\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:
-
-\[  
-  \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},
-\]
- 
-  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.  Finally, $E^a_{p}$ and $E^s_{p}$ indicate the energy
-  consumed by the WSN during the sensing phase (active and sleeping nodes).
-\end{itemize}
-
-
-\subsection{Simulation Results}
-
-In  order  to  assess and  analyze  the  performance  of  our protocol  we  have
-implemented PeCO protocol in  OMNeT++~\citep{varga} simulator.  Besides PeCO, two
-other  protocols,  described  in  the  next paragraph,  will  be  evaluated  for
-comparison purposes.   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)$.  The modeling  language for
-Mathematical Programming (AMPL)~\citep{AMPL} is  employed 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.
-
-As said previously, the PeCO is  compared to three other approaches. 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 we presented in~\citep{idrees2014coverage}. Let us notice that
-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. 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. DiLCO protocol tries to satisfy the coverage of a set of primary points,
-whereas the PeCO protocol objective is to reach a desired level of coverage for each
-sensor perimeter. In our experimentations, we chose a level of coverage equal to
-one ($l=1$).
-
-\subsubsection{\bf 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 protocol  puts to  sleep status  more redundant  sensors (which
-slightly decreases the coverage ratio), while the three 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{\bf Active Sensors Ratio}
-
-Having the less 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.   We observe that
-DESK and  GAF have 30.36  \% and  34.96 \% active  nodes for the  first fourteen
-rounds and  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, PeCO protocol  has a lower number of active  nodes in comparison with
-the three other approaches, 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{\bf Energy Consumption}
-
-We studied the effect of the energy  consumed by the WSN during the communication,
-computation, listening, active, and sleep status for different network densities
-and  compared  it for  the  four  approaches.  Figures~\ref{figure7}(a)  and  (b)
-illustrate  the  energy   consumption  for  different  network   sizes  and  for
-$Lifetime95$ and  $Lifetime50$. The results show  that our PeCO protocol  is the
-most competitive  from the energy  consumption point of  view. As shown  in both
-figures, PeCO consumes much less energy than the three 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 so the energy consumption
-while keeping a good coverage level.
-
-\begin{figure}[h!]
-  \centering
-  \begin{tabular}{@{}cr@{}}
-    \includegraphics[scale=0.475]{figure7a.eps} & \raisebox{2.75cm}{(a)} \\
-    \includegraphics[scale=0.475]{figure7b.eps} & \raisebox{2.75cm}{(b)}
-  \end{tabular}
-  \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.}
-  \label{figure7}
-\end{figure} 
-
-
-
-\subsubsection{\bf Network Lifetime}
-
-We observe the superiority of PeCO and DiLCO protocols in comparison with the
-two    other   approaches    in    prolonging   the    network   lifetime.    In
-Figures~\ref{figure8}(a)  and (b),  $Lifetime95$ and  $Lifetime50$ are  shown for
-different  network  sizes.   As  highlighted  by  these  figures,  the  lifetime
-increases with the size  of the network, and it is clearly   largest for DiLCO
-and PeCO  protocols.  For instance,  for a  network of 300~sensors  and coverage
-ratio greater than 50\%, we can  see on figure~\ref{figure8}(b) that the lifetime
-is about twice longer with  PeCO compared to DESK protocol.  The performance
-difference    is    more    obvious   in    figure~\ref{figure8}(b)    than    in
-figure~\ref{figure8}(a) because the gain induced  by our protocols increases with
- time, and the lifetime with a coverage  of 50\% is far  longer than with
-95\%.
-
-\begin{figure}[h!]
-  \centering
-  \begin{tabular}{@{}cr@{}}
-    \includegraphics[scale=0.475]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\  
-    \includegraphics[scale=0.475]{figure8b.eps} & \raisebox{2.75cm}{(b)}
-  \end{tabular}
-  \caption{Network Lifetime for (a)~$Lifetime_{95}$ \\
-    and (b)~$Lifetime_{50}$.}
-  \label{figure8}
-\end{figure} 
-
-
-
-Figure~\ref{figure9}  compares  the  lifetime  coverage of  our  protocols  for
-different coverage  ratios. We denote by  Protocol/50, Protocol/80, Protocol/85,
-Protocol/90, and  Protocol/95 the amount  of time  during which the  network can
-satisfy an area coverage greater than $50\%$, $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. PeCO might be
-an interesting  method since  it achieves  a good balance  between a  high level
-coverage ratio and network lifetime. PeCO always outperforms DiLCO for the three
-lower  coverage  ratios,  moreover  the   improvements  grow  with  the  network
-size. DiLCO is better  for coverage ratios near 100\%, but in  that case PeCO is
-not ineffective for the smallest network sizes.
-
-\begin{figure}[h!]
-\centering \includegraphics[scale=0.5]{figure9.eps}
-\caption{Network lifetime for different coverage ratios.}
-\label{figure9}
-\end{figure} 
-
-
-
-
-\section{Conclusion and Future Works}
-\label{sec:Conclusion and Future Works}
-
-In this paper  we have studied the problem of  Perimeter-based Coverage Optimization in
-WSNs. We have designed  a new protocol, called Perimeter-based  Coverage Optimization, which
-schedules nodes'  activities (wake up  and sleep  stages) with the  objective of
-maintaining a  good coverage ratio  while maximizing the network  lifetime. This
-protocol is  applied in a distributed  way in regular subregions  obtained after
-partitioning the area of interest in a preliminary step. It works in periods and
-is based on the resolution of an integer program to select the subset of sensors
-operating in active status for each period. Our work is original in so far as it
-proposes for  the first  time an  integer program  scheduling the  activation of
-sensors  based on  their perimeter  coverage level,  instead of  using a  set of
-targets/points to be covered.
-
-
-We  have carried out  several simulations  to  evaluate the  proposed protocol.   The
-simulation  results  show   that  PeCO  is  more   energy-efficient  than  other
-approaches, with respect to lifetime,  coverage ratio, active sensors ratio, and
-energy consumption.
-
-We plan to extend our framework so that the schedules are planned for multiple
-sensing periods.
-
-We also want  to improve our integer program to  take into account heterogeneous
-sensors  from both  energy  and node  characteristics point of views.
-
-Finally,  it   would  be   interesting  to  implement   our  protocol   using  a
-sensor-testbed to evaluate it in real world applications.
-
-\bibliographystyle{gENO}
-\bibliography{biblio}
-
-
-\end{document}
+% gENOguide.tex
+% v4.0 released April 2013
+
+\documentclass{gENO2e}
+%\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
+%\renewcommand{\algorithmcfname}{ALGORITHM}
+\usepackage{indentfirst}
+\usepackage[algo2e,ruled,vlined]{algorithm2e}
+\begin{document}
+
+%\jvol{00} \jnum{00} \jyear{2013} \jmonth{April}
+
+%\articletype{GUIDE}
+
+\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. We
+propose such  an approach called Perimeter-based  Coverage Optimization protocol
+(PeCO). 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 our 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 in comparison with some 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 to  use 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 made  it suitable for a wide
+range of application  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 receiving.
+
+The energy needed  by an active sensor node to  perform sensing, processing, and
+communication is supplied 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 it 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 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, we formulate an integer program based on perimeter coverage of
+  each sensor.  The  model involves integer variables to  capture the deviations
+  between  the actual  level  of coverage  and the  required  level.  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  our protocol.  We have
+  compared  the  PeCO  protocol  to  two approaches  found  in  the  literature:
+  DESK~\citep{ChinhVu} and GAF~\citep{xu2001geography}, and also to our previous
+  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    disk   of    sensor   nodes    and   boundaries.     In
+\citep{Huang:2003:CPW:941350.941367}  authors prove  that if  the perimeters  of
+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, our 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 activate these set covers  successively. 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  only information on its immediate neighbors  (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  or close to  optimal solution 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 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 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: minimize  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. 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  DiLCO protocol,  we formulate  an integer
+  program based on perimeter coverage of each sensor. The model involves integer
+  variables to capture  the deviations between the actual level  of coverage and
+  the required level. The idea is that an optimal scheduling will be obtained by
+  minimizing a weighted sum of these deviations.}
+  
+\section{ The P{\scshape e}CO Protocol Description}
+\label{sec:The PeCO Protocol Description}
+
+%In  this  section,  the Perimeter-based  Coverage
+%Optimization protocol is decribed in details.  First we present the  assumptions we made and the models
+%we considered (in particular the perimeter coverage one), second we describe the
+%background idea of our protocol, and third  we give the outline of the algorithm
+%executed by each node.
+
+
+\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.  We  also assume that the communication range  $R_c$ satisfies $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  and  we have  reported  on  its perimeter  (the
+perimeter of the  disk covered by the  sensor) for each neighbor  the two points
+resulting from  the intersection  of the  two sensing  areas.  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{\vert u_x - v_x \vert^2 + \vert u_y-v_y \vert^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    an    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 our 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} 
+
+We define two types of packets to be used by PeCO protocol:
+\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
+  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}      
+ % \KwIn{all the parameters related to information exchange}
+%  \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)}
+%  \BlankLine
+  %\emph{Initialize the sensor node and determine it's position and subregion} \;
+  \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}
+
+%\begin{algorithm}
+%\noindent{\bf If} $RE_k \geq E_{th}$ {\bf then}\\
+%\hspace*{0.6cm} \emph{$s_k.status$ = COMMUNICATION;}\\
+%\hspace*{0.6cm}  \emph{Send $INFO()$ packet to other nodes in subregion;}\\
+%\hspace*{0.6cm}  \emph{Wait $INFO()$ packet from other nodes in subregion;}\\
+%\hspace*{0.6cm} \emph{Update K.CurrentSize;}\\
+%\hspace*{0.6cm}  \emph{LeaderID = Leader election;}\\
+%\hspace*{0.6cm} {\bf If} $ s_k.ID = LeaderID $ {\bf then}\\
+%\hspace*{1.2cm}   \emph{$s_k.status$ = COMPUTATION;}\\
+%\hspace*{1.2cm}{\bf If} \emph{$ s_k.ID $ is Not previously selected as a Leader} {\bf then}\\
+%\hspace*{1.8cm} \emph{ Execute the perimeter coverage model;}\\
+%\hspace*{1.2cm} {\bf end}\\
+%\hspace*{1.2cm}{\bf If} \emph{($s_k.ID $ is the same Previous Leader)~And~(K.CurrentSize = K.PreviousSize)}\\
+%\hspace*{1.8cm} \emph{ Use the same previous cover set for current sensing stage;}\\
+%\hspace*{1.2cm}  {\bf end}\\
+%\hspace*{1.2cm}  {\bf else}\\
+%\hspace*{1.8cm}\emph{Update $a^j_{ik}$; prepare data for IP~Algorithm;}\\
+%\hspace*{1.8cm} \emph{$\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$);}\\
+%\hspace*{1.8cm} \emph{K.PreviousSize = K.CurrentSize;}\\
+%\hspace*{1.2cm}  {\bf end}\\
+%\hspace*{1.2cm}\emph{$s_k.status$ = COMMUNICATION;}\\
+%\hspace*{1.2cm}\emph{Send $ActiveSleep()$ to each node $l$ in subregion;}\\
+%\hspace*{1.2cm}\emph{Update $RE_k $;}\\
+%\hspace*{0.6cm}  {\bf end}\\
+%\hspace*{0.6cm}  {\bf else}\\
+%\hspace*{1.2cm}\emph{$s_k.status$ = LISTENING;}\\
+%\hspace*{1.2cm}\emph{Wait $ActiveSleep()$ packet from the Leader;}\\
+%\hspace*{1.2cm}\emph{Update $RE_k $;}\\
+%\hspace*{0.6cm}  {\bf end}\\
+%{\bf end}\\
+%{\bf else}\\
+%\hspace*{0.6cm} \emph{Exclude $s_k$ from entering in the current sensing stage;}\\
+%{\bf end}\\
+%\label{alg:PeCO}
+%\end{algorithm}
+
+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.
+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 index.
+\end{enumerate}
+Once chosen, the leader collects information  to formulate and solve the integer
+program  which allows  to construct  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 have 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 we try to  minimize these deviations, 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}
+
+%\begin{equation} 
+%\left \{
+%\begin{array}{ll}
+%\min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i ) & \\
+%\textrm{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{array}
+%\right.
+%\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 a 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  for   optimizing  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   we  use   the  same   energy  consumption   model  as   in  our   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. 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 to
+be more  reliable but would  have result 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 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. In our  case, 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 our 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 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}
+
+In  order  to  assess and  analyze  the  performance  of  our protocol  we  have
+implemented PeCO  protocol in OMNeT++~\citep{varga} simulator.   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 we  could use
+commercial  solvers  like  CPLEX  \citep{iamigo:cplex}  which  are  less  memory
+consuming and more efficient, or implement a lightweight heuristic. 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 we presented
+in~\citep{idrees2014coverage}. Let us  notice that 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. DiLCO protocol tries to satisfy the coverage of
+a set of primary  points, whereas PeCO protocol objective is  to reach a desired
+level of coverage for each sensor perimeter. In our experimentations, we chose a
+level of coverage equal to one ($l=1$).
+
+\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 DiLCO  and  PeCO protocols  put to  sleep  status more  redundant
+sensors  (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}
+
+Having the less 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.  We observe that DESK and GAF have 30.36~\% and 34.96~\% active nodes for
+the first fourteen  rounds, and 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, 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 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{figure7}(a)
+and (b)  illustrate the energy consumption  for different network sizes  and for
+$Lifetime95$ and $Lifetime50$.  The results show  that 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 so  the energy consumption  while keeping  a good
+coverage level. Let  us notice that the energy overhead  when increasing network
+size is the lowest with PeCO.
+
+\begin{figure}[h!]
+  \centering
+  \begin{tabular}{@{}cr@{}}
+    \includegraphics[scale=0.5]{figure7a.eps} & \raisebox{2.75cm}{(a)} \\
+    \includegraphics[scale=0.5]{figure7b.eps} & \raisebox{2.75cm}{(b)}
+  \end{tabular}
+  \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.}
+  \label{figure7}
+\end{figure} 
+
+\subsubsection{Network Lifetime}
+
+We observe the  superiority of both PeCO and DiLCO  protocols in comparison with
+the   two   other  approaches   in   prolonging   the  network   lifetime.    In
+Figures~\ref{figure8}(a) and  (b), $Lifetime95$  and $Lifetime50$ 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 largest for DiLCO and
+PeCO protocols.  For  instance, for a network of 300~sensors  and coverage ratio
+greater than  50\%, we can see  on Figure~\ref{figure8}(b) that the  lifetime is
+about  twice  longer with  PeCO  compared  to  DESK protocol.   The  performance
+difference    is   more    obvious    in    Figure~\ref{figure8}(b)   than    in
+Figure~\ref{figure8}(a) because the gain induced by our protocols 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]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\  
+    \includegraphics[scale=0.5]{figure8b.eps} & \raisebox{2.75cm}{(b)}
+  \end{tabular}
+  \caption{Network Lifetime for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.}
+  \label{figure8}
+\end{figure} 
+
+Figure~\ref{figure9} compares the lifetime coverage  of DiLCO and PeCO protocols
+for  different   coverage  ratios.   We  denote  by   Protocol/50,  Protocol/80,
+Protocol/85, Protocol/90,  and Protocol/95 the  amount of time during  which the
+network  can satisfy  an  area  coverage greater  than  $50\%$, $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. PeCO might be  an interesting method since  it achieves a
+good balance  between a  high level  coverage ratio  and network  lifetime. PeCO
+always  outperforms DiLCO  for the  three  lower coverage  ratios, moreover  the
+improvements grow  with the network  size. DiLCO  is better for  coverage ratios
+near 100\%, but  in that case PeCO  is not ineffective for  the smallest network
+sizes.
+
+\begin{figure}[h!]
+\centering \includegraphics[scale=0.55]{figure9.eps}
+\caption{Network lifetime for different coverage ratios.}
+\label{figure9}
+\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 so limit
+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 {\it Lifetime50}
+with $\beta \gg \alpha$: a large number  of periods with low coverage ratio.  On
+the other hand, when we choose $\alpha \gg \beta$, we favor the coverage even if
+some areas may  be overcovered, so high  coverage ratio is reached,  but a large
+number  of  sensors are  activated  to  achieve  this goal.   Therefore  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 we
+have  chosen  this  setting  for  the  experiments  presented  in  the  previous
+subsections.
+
+%As can be seen in Table~\ref{my-labelx},  it is obvious and clear that when $\alpha$ decreased and $\beta$ increased by any step, the network lifetime for $Lifetime_{50}$ increased and the $Lifetime_{95}$ decreased. Therefore, selecting the values of $\alpha$ and $\beta$ depend on the application type used in the sensor nework. In PeCO protocol, $\alpha$ and $\beta$ are chosen based on the largest value of network lifetime for $Lifetime_{95}$.
+
+\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 we have studied  the problem of perimeter coverage optimization in
+WSNs.   We  have  designed  a  new  protocol,  called  Perimeter-based  Coverage
+Optimization, which schedules nodes' activities  (wake up and sleep stages) with
+the objective of maintaining a good  coverage ratio while maximizing the network
+lifetime.  This protocol  is applied in a distributed way  in regular subregions
+obtained after partitioning the area of interest in a preliminary step. It works
+in periods and  is based on the  resolution of an integer program  to select the
+subset  of sensors  operating in  active status  for each  period.  Our  work is
+original  in so  far  as it  proposes  for  the first  time  an integer  program
+scheduling the  activation of sensors  based on their perimeter  coverage level,
+instead of using a set of targets/points to be covered. 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.
+
+We plan to extend  our framework so that the schedules  are planned for multiple
+sensing  periods. We  also want  to  improve the  integer program  to take  into
+account heterogeneous sensors from both energy and node characteristics point of
+views.  Finally,  it would  be interesting  to implement  PeCO protocol  using a
+sensor-testbed to evaluate it in real world applications.
+
+
+\subsection*{Acknowledgements}
+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}
