Michel - Modifications made up to section 4 - to be continued

[LiCO.git] / PeCO-EO / articleeo.tex

diff --git a/PeCO-EO/articleeo.tex b/PeCO-EO/articleeo.tex
index 39a0559f3c5a2e4d67885b8290bb981013203f04..189f2363e4f773dcace0af8bd81a7c7213ff9c9e 100644 (file)
--- a/PeCO-EO/articleeo.tex
+++ b/PeCO-EO/articleeo.tex
@@ -5,36 +5,39 @@
 %\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
 %\renewcommand{\algorithmcfname}{ALGORITHM}
 \usepackage{indentfirst}
 %\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}
 
 \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}}
+\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,
 
 \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}};}
-
+          Belfort, France}}}

 
 \maketitle
 
 \begin{abstract}
 The most important problem in a Wireless Sensor Network (WSN) is to optimize the
 
 \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
+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
 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.
+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}
 \end{keywords}
 
 \end{abstract}


@@ -43,17 +46,17 @@ offer longer lifetime coverage for WSNs in comparison with some other protocols.
 \section{Introduction}
 \label{sec:introduction}
 
 \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
+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,
 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
+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.
 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.


@@ -62,192 +65,202 @@ 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
 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
+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
 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
+while  ensuring  a   high  level  of  coverage?   These  past   few  years  many

 energy-efficient mechanisms have been suggested  to retain energy and extend the
 energy-efficient mechanisms have been suggested  to retain energy and extend the

-lifetime of the WSNs~\citep{rault2014energy}.\\\\
+lifetime of the WSNs~\citep{rault2014energy}.
+

 This paper makes the following contributions.
 \begin{enumerate}
 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 schedule  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.
+\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 schedule 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  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}
 
 \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}
+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
 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
+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}
 
 Section~\ref{sec:Conclusion and Future Works}.
 
 \section{Related Literature}
 \label{sec:Literature Review}
 

-In  this section, some  related works  regarding  the
-coverage problem is summarized, and specific aspects of the PeCO protocol from the  works presented in
-the literature are presented.
+In  this  section,  some  related   works  regarding  the  coverage  problem  is
+summarized, and specific  aspects of the PeCO protocol from  the works presented
+in the literature are presented.

 
 The most  discussed coverage problems in  literature can be classified  in three
 
 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
+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
 to  the objective  of coverage  for a  finite number  of discrete  points called

-targets,  and  barrier coverage~\citep{HeShibo,kim2013maximum}  focuses  on
+targets,   and   barrier  coverage~\citep{HeShibo,kim2013maximum}   focuses   on

 preventing  intruders   from  entering   into  the   region  of   interest.   In
 preventing  intruders   from  entering   into  the   region  of   interest.   In

-\citep{Deng2012}  authors  transform the  area  coverage  problem into  the  target
+\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
 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
+\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
 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.}
+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
 
 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
+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
 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, and 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.
+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
 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
+\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
 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, maintains the coverage and improves the lifetime in WSNs. It is  an improved version
-of a research work they presented in~\citep{idrees2014coverage}.  First, they partition the area of interest into subregions using a divide-and-conquer method. DiLCO protocol is then distributed on the sensor nodes in each subregion in a second step. DiLCO protocol combines two techniques: a leader election in each subregion, followed by an optimization-based node activity scheduling performed by each elected leader. The proposed DiLCO protocol is a periodic protocol where each period is decomposed into 4 phases: information exchange, leader election, decision, and sensing. The simulations show that DiLCO is able to increase the WSN lifetime and provides improved coverage performance. {\it  In the PeCO
-  protocol, We have proposed a new mathematical optimization model. 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.}
+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}
 
 \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.
+%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}
 
 
 
 \subsection{Assumptions and Models}
 \label{CI}
 

-A WSN consisting of $J$ stationary sensor nodes randomly and uniformly
+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
 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
+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
 sensor node either  through hardware such as embedded GPS  or location discovery

-algorithms. 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. Authors \citet{huang2005coverage}  proved that  a network  area is
-$k$-covered (every point in the area covered by at least k sensors) if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors). 
+algorithms. 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.  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 neighboing  point of  view.  The  resulting couples  of
-intersection points subdivide  the perimeter of sensor~$0$  into portions called
-arcs.
+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{figure}[ht!]
   \centering


@@ -260,40 +273,39 @@ arcs.
   \label{figure1}
 \end{figure} 
 
   \label{figure1}
 \end{figure} 
 

-Figure~\ref{figure1}(b) describes the geometric information used to find the
+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
 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: $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:
+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).
+\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$.
+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
 
 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
+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
 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$
+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.
 
 (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}  
 \begin{figure*}[t!]
 \centering
 \includegraphics[width=127.5mm]{figure2.eps}  


@@ -301,11 +313,8 @@ above is thus given by the sixth line of the table.
 \label{figure2}
 \end{figure*} 
 
 \label{figure2}
 \end{figure*} 
 

-
-
-
- \begin{table}
- \tbl{Coverage intervals and contributing sensors for sensor node 0 \label{my-label}}
+\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
 {\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


@@ -332,41 +341,43 @@ above is thus given by the sixth line of the table.
 
 \end{table}
 
 
 \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
+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
 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$
+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.
 
 and  the  corresponding  interval  will  not   be  taken  into  account  by  the
 optimization algorithm.
 

- \newpage
+\newpage

 \begin{figure}[h!]
 \centering
 \includegraphics[width=62.5mm]{figure3.eps}  
 \caption{Sensing range outside the WSN's area of interest.}
 \label{figure3}
 \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}
-
-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
+\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. Node Sensors  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
 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


@@ -375,17 +386,17 @@ 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
 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.
+the area. Sensing  period duration is adapted according to  the QoS requirements
+of the application.

 
 \begin{figure}[t!]
 \centering
 
 \begin{figure}[t!]
 \centering

-\includegraphics[width=80mm]{figure4.eps}  
+\includegraphics[width=85mm]{figure4.eps}  

 \caption{PeCO protocol.}
 \label{figure4}
 \end{figure} 
 
 We define two types of packets to be used by PeCO protocol:
 \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.
 \begin{itemize} 
 \item INFO  packet: sent  by each  sensor node to  all the  nodes inside  a same
   subregion for information exchange.


@@ -394,9 +405,7 @@ We define two types of packets to be used by PeCO protocol:
   sensing phase.
 \end{itemize}
 
   sensing phase.
 \end{itemize}
 

-

 Five statuses are possible for a sensor node in the network:
 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
 \begin{itemize} 
 \item LISTENING: waits for a decision (to be active or not);
 \item COMPUTATION: executes the optimization algorithm as leader to


@@ -406,78 +415,109 @@ Five statuses are possible for a sensor node in the network:
 \item COMMUNICATION: transmits or receives packets.
 \end{itemize}
 
 \item COMMUNICATION: transmits or receives packets.
 \end{itemize}
 

-

 \subsection{PeCO Protocol Algorithm}
 
 \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.
+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}      
+\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
  % \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}
-
-
+  %\emph{Initialize the sensor node and determine it's position and subregion} \;
+  \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
 
 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
+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
 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
+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
 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.
+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.

 
 

+% TO BE CONTINUED

 
 \section{Perimeter-based Coverage Problem Formulation}
 \label{cp}
 
 
 \section{Perimeter-based Coverage Problem Formulation}
 \label{cp}
 

-In this  section, the coverage model is  mathematically formulated. The following
-notations are used  throughout the
+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}
 section.\\
 First, the following sets:
 \begin{itemize}


@@ -500,16 +540,16 @@ a^j_{ik} = \left \{
 \end{equation}
 Note that $a^k_{ik}=1$ by definition of the interval.
 
 \end{equation}
 Note that $a^k_{ik}=1$ by definition of the interval.
 

-Second, several binary  and integer  variables are defined.  Hence,  each binary
+Second, several variables are defined.  Hence,  each binary

 variable $X_{k}$  determines the activation of  sensor $k$ in the  sensing phase
 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
+($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$.
 
 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
+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
 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


@@ -525,33 +565,37 @@ to reach a coverage level as close as possible to the desired one.
 
 
 
 
 
 

-Our coverage optimization problem can then be mathematically expressed as follows: 
+The 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 :}&\\
 
 \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  = l \quad \forall i \in I_j, \forall j \in S\\
-\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i  = l \quad \forall i \in I_j, \forall j \in S\\
-X_{k} \in \{0,1\}, \forall k \in A
+\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}
 
 \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$. In the contrary, 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
 $\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
+region. This  kind of mixed-integer program  is inspired from the  model developed for

 brachytherapy treatment planning  for optimizing dose  distribution
 brachytherapy treatment planning  for optimizing dose  distribution

-\citep{0031-9155-44-1-012}. The integer  program must be solved by  the leader in
+\citep{0031-9155-44-1-012}.  The choice of variables $\alpha$ and $\beta$ should be made according to the needs of the application. $\alpha$ should be enough large to prevent undercoverage and so to reach the highest possible coverage ratio. $\beta$ should be enough large 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
 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.
+sensing phase) are considered in the model. 

 
 \section{Performance Evaluation and Analysis}  
 \label{sec:Simulation Results and Analysis}
 
 \section{Performance Evaluation and Analysis}  
 \label{sec:Simulation Results and Analysis}


@@ -797,8 +841,8 @@ ratio greater than 50\%, we can  see on Figure~\ref{figure8}(b) that the lifetim
 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
 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\%.
+ time, and the lifetime with a coverage  over 50\% is far  longer than with
+95\%. 

 
 \begin{figure}[h!]
   \centering
 
 \begin{figure}[h!]
   \centering


@@ -833,13 +877,13 @@ not ineffective for the smallest network sizes.
 
 
 \subsubsection{\bf Impact of $\alpha$ and $\beta$ on PeCO's performance}
 
 
 \subsubsection{\bf Impact of $\alpha$ and $\beta$ on PeCO's performance}

-
-Table~\ref{tbl} shows the  impact of $\alpha$ and $\beta$ on PeCO's performance.
+Table~\ref{my-labelx} shows network lifetime results for the different values of $\alpha$ and $\beta$, and for a network size equal to 200 sensor nodes. 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. With $\alpha \gg \beta$, we priviligie 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.     
+%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}
 
 \begin{table}[h]
 \centering
 \caption{The impact of $\alpha$ and $\beta$ on PeCO's performance}

-\label{my-label}
+\label{my-labelx}

 \begin{tabular}{|c|c|c|c|}
 \hline
 $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
 \begin{tabular}{|c|c|c|c|}
 \hline
 $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline


@@ -849,7 +893,7 @@ $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
 0.3 & 0.7 & 134 & 0 \\ \hline
 0.4 & 0.6 & 125 & 0 \\ \hline
 0.5 & 0.5 & 118 & 30 \\ \hline
 0.3 & 0.7 & 134 & 0 \\ \hline
 0.4 & 0.6 & 125 & 0 \\ \hline
 0.5 & 0.5 & 118 & 30 \\ \hline

-0.6 & 0.4 & 94 & 57 \\ \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
 0.7 & 0.3 & 97 & 49 \\ \hline
 0.8 & 0.2 & 90 & 52 \\ \hline
 0.9 & 0.1 & 77 & 50 \\ \hline


@@ -861,35 +905,16 @@ $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
 \section{Conclusion and Future Works}
 \label{sec:Conclusion and Future Works}
 
 \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.
+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 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.
+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. 

 
 

-Finally,  it   would  be   interesting  to  implement   our  protocol   using  a
-sensor-testbed to evaluate it in real world applications.
+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}
 
 \bibliographystyle{gENO}

-\bibliography{articleeo}
+\bibliography{biblio} %articleeo

 
 
 \end{document}
 
 
 \end{document}