no more color

[JournalMultiPeriods.git] / article.tex

diff --git a/article.tex b/article.tex
index d886626c1b878f11ac8d571651f3212e606102ec..ed70b52271030df1fe6c5ade3585031169ab22c7 100644 (file)
--- a/article.tex
+++ b/article.tex
@@ -84,11 +84,11 @@
 %e-mail: ali.idness@edu.univ-fcomte.fr, \\
 %$\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr.}
 
 %e-mail: ali.idness@edu.univ-fcomte.fr, \\
 %$\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr.}
 

-\author{Ali   Kadhum   Idrees$^{a,b}$,   Karine  Deschinkel$^{a}$,   \\   Michel
-  Salomon$^{a}$,   and  Rapha\"el   Couturier   $^{a}$  \\   $^{a}${\em{FEMTO-ST
-      Institute/CNRS,   \\  Univ.  Bourgogne  Franche-Comt\'e,
-      Belfort, France}} \\ $^{b}${\em{Department of Computer Science, University
-      of Babylon, Babylon, Iraq}} }
+\author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$, \\
+  Michel Salomon$^{a}$, and Rapha\"el Couturier $^{a}$ \\
+  $^{a}${\em{FEMTO-ST Institute, DISC department, UMR 6174 CNRS, \\
+      Univ.  Bourgogne  Franche-Comt\'e (UBFC), Belfort, France}} \\
+  $^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}}}

 
 \begin{abstract}
 Coverage and  lifetime are  two paramount problems  in Wireless  Sensor Networks
 
 \begin{abstract}
 Coverage and  lifetime are  two paramount problems  in Wireless  Sensor Networks


@@ -99,17 +99,16 @@ divided into  subregions and  then the  MuDiLCO protocol  is distributed  on the
 sensor nodes in  each subregion. The proposed MuDiLCO protocol  works in periods
 during which sets of sensor nodes are  scheduled, with one set for each round of
 a period, to remain active during the  sensing phase and thus ensure coverage so
 sensor nodes in  each subregion. The proposed MuDiLCO protocol  works in periods
 during which sets of sensor nodes are  scheduled, with one set for each round of
 a period, to remain active during the  sensing phase and thus ensure coverage so

-as  to maximize  the  WSN lifetime.  The  decision process  is
-  carried out by a leader node,  which solves an optimization problem to produce
-  the  best representative  sets to  be used  during the  rounds of  the sensing
-  phase. The optimization problem formulated as  an integer program is solved to
-  optimality through a Branch-and-Bound method  for small instances.  For larger
-  instances, the best  feasible solution found by the solver  after a given time
-  limit threshold is considered.
-Compared  with some  existing protocols,  simulation results  based on  multiple
-criteria (energy consumption, coverage ratio, and  so on) show that the proposed
-protocol can prolong  efficiently the network lifetime and  improve the coverage
-performance.
+as to  maximize the  WSN lifetime.   The decision  process is  carried out  by a
+leader  node,  which  solves  an   optimization  problem  to  produce  the  best
+representative  sets to  be used  during the  rounds of  the sensing  phase. The
+optimization problem  formulated as an  integer program is solved  to optimality
+through a  Branch-and-Bound method for  small instances.  For  larger instances,
+the  best  feasible solution  found  by  the solver  after  a  given time  limit
+threshold  is considered.   Compared  with some  existing protocols,  simulation
+results based on  multiple criteria (energy consumption, coverage  ratio, and so
+on) show that the proposed protocol can prolong efficiently the network lifetime
+and improve the coverage performance.

 \end{abstract}
 
 \begin{keyword}
 \end{abstract}
 
 \begin{keyword}


@@ -150,24 +149,26 @@ in~\cite{idrees2015distributed}.
 %more  interesting  to  divide  the  area  into  several  subregions,  given  the
 %computation complexity.
 
 %more  interesting  to  divide  the  area  into  several  subregions,  given  the
 %computation complexity.
 

-\textcolor{green}{
- Compared to our previous paper~\cite{idrees2015distributed}, in this one we study the
-possibility of dividing  the sensing phase into multiple rounds. In fact, in this paper we make a multiround optimization, while it was
-a single round  optimization in our previous work.  The idea is
-  to take advantage  of the pre-sensing phase to plan  the sensor's activity for
+\textcolor{black}{ Compared  to our  previous work~\cite{idrees2015distributed},
+  in  this paper  we study  the  possibility of  dividing the  sensing phase  into
+  multiple rounds.   We make a  multiround optimization,
+  while previously it was a single round optimization.  The idea is to
+  take advantage  of the  pre-sensing phase  to plan  the sensor's  activity for

   several  rounds instead  of one,  thus saving  energy. In  addition, when  the
   optimization problem becomes  more complex, its resolution is  stopped after a
   several  rounds instead  of one,  thus saving  energy. In  addition, when  the
   optimization problem becomes  more complex, its resolution is  stopped after a

-  given time threshold. In this paper we also analyse the performance of our protocol according to the number of primary points used (area coverage is replaced by the coverage of a set of particular points called primary points, see section~\ref{pp}).}
-
-The remainder of the paper is organized as follows. The next section
-reviews the  related works  in the  field.  Section~\ref{pd}  is devoted  to the
-description of  MuDiLCO protocol. Section~\ref{exp} introduces  the experimental
-framework, it describes  the simulation setup and the different  metrics used to
-assess the  performances.  Section~\ref{analysis}  shows the  simulation results
-obtained using  the discrete event  simulator OMNeT++ \cite{varga}.   They fully
-demonstrate  the  usefulness  of  the   proposed  approach.   Finally,  we  give
-concluding    remarks   and    some    suggestions   for    future   works    in
-Section~\ref{sec:conclusion}.
+  given time  threshold. In this  paper we also  analyze the performance  of our
+  protocol according to the number of  primary points used (the area coverage is
+  replaced by the coverage of a  set of particular points called primary points,
+  see Section~\ref{pp}).}
+
+The remainder of the paper is organized as follows. The next section reviews the
+related works in  the field.  Section~\ref{pd} is devoted to  the description of
+MuDiLCO protocol.  Section~\ref{exp} introduces  the experimental  framework, it
+describes the  simulation setup  and the  different metrics  used to  assess the
+performances.   Section~\ref{analysis}  shows  the simulation  results  obtained
+using the discrete event simulator OMNeT++ \cite{varga}.  They fully demonstrate
+the usefulness  of the proposed  approach.  Finally, we give  concluding remarks
+and some suggestions for future works in Section~\ref{sec:conclusion}.

 
 \section{Related works} 
 \label{rw}
 
 \section{Related works} 
 \label{rw}


@@ -243,40 +244,40 @@ processing by the cooperating sensor nodes, but they are more scalable for large
 WSNs.  Localized and distributed algorithms generally result in non-disjoint set
 covers.
 
 WSNs.  Localized and distributed algorithms generally result in non-disjoint set
 covers.
 

-Many distributed algorithms have been  developed to perform the scheduling so as
-to          preserve         coverage,          see          for         example
-\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02,       yardibi2010distributed,
-  prasad2007distributed,Misra}.   Distributed  algorithms  typically operate  in
+Many distributed algorithms have been developed  to perform the scheduling so as
+to          preserve         coverage,          see         for          example
+\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02,      yardibi2010distributed,
+  prasad2007distributed,Misra}.   Distributed  algorithms typically  operate  in

 rounds for  a predetermined duration. At  the beginning of each  round, a sensor
 rounds for  a predetermined duration. At  the beginning of each  round, a sensor

-exchanges information with  its neighbors and makes a  decision to either remain
+exchanges information with  its neighbors and makes a decision  to either remain

 turned on or  to go to sleep for  the round. This decision is  basically made on
 turned on or  to go to sleep for  the round. This decision is  basically made on

-simple     greedy     criteria    like     the     largest    uncovered     area
+simple     greedy    criteria     like     the     largest    uncovered     area

 \cite{Berman05efficientenergy}      or       maximum      uncovered      targets
 \cite{lu2003coverage}.   The  Distributed  Adaptive Sleep  Scheduling  Algorithm
 \cite{Berman05efficientenergy}      or       maximum      uncovered      targets
 \cite{lu2003coverage}.   The  Distributed  Adaptive Sleep  Scheduling  Algorithm

-(DASSA) \cite{yardibi2010distributed}  does not require  location information of
+(DASSA) \cite{yardibi2010distributed}  does not require location  information of

 sensors while  maintaining connectivity and  satisfying a user  defined coverage
 target.  In  DASSA, nodes use the  residual energy levels and  feedback from the
 sink for  scheduling the activity  of their neighbors.  This  feedback mechanism
 sensors while  maintaining connectivity and  satisfying a user  defined coverage
 target.  In  DASSA, nodes use the  residual energy levels and  feedback from the
 sink for  scheduling the activity  of their neighbors.  This  feedback mechanism

-reduces  the randomness  in scheduling  that would  otherwise occur  due  to the
-absence of location information.  In  \cite{ChinhVu}, the author have designed a
-novel distributed heuristic,  called Distributed Energy-efficient Scheduling for
+reduces  the randomness  in scheduling  that would  otherwise occur  due to  the
+absence of location information.  In \cite{ChinhVu}, the authors have designed a
+novel distributed heuristic, called  Distributed Energy-efficient Scheduling for

 k-coverage (DESK), which  ensures that the energy consumption  among the sensors
 is  balanced  and the  lifetime  maximized  while  the coverage  requirement  is
 k-coverage (DESK), which  ensures that the energy consumption  among the sensors
 is  balanced  and the  lifetime  maximized  while  the coverage  requirement  is

-maintained.   This heuristic  works in  rounds, requires  only  one-hop neighbor
+maintained.   This heuristic  works in  rounds, requires  only one-hop  neighbor

 information, and each  sensor decides its status (active or  sleep) based on the
 perimeter coverage model from~\cite{Huang:2003:CPW:941350.941367}.
 
 The  works presented  in  \cite{Bang, Zhixin,  Zhang}  focus on  coverage-aware,
 distributed energy-efficient,  and distributed clustering  methods respectively,
 information, and each  sensor decides its status (active or  sleep) based on the
 perimeter coverage model from~\cite{Huang:2003:CPW:941350.941367}.
 
 The  works presented  in  \cite{Bang, Zhixin,  Zhang}  focus on  coverage-aware,
 distributed energy-efficient,  and distributed clustering  methods respectively,

-which  aim at extending  the network  lifetime, while  the coverage  is ensured.
+which aim  at extending  the network  lifetime, while  the coverage  is ensured.

 More recently, Shibo et al.  \cite{Shibo} have expressed the coverage problem as
 a  minimum  weight submodular  set  cover  problem  and proposed  a  Distributed
 More recently, Shibo et al.  \cite{Shibo} have expressed the coverage problem as
 a  minimum  weight submodular  set  cover  problem  and proposed  a  Distributed

-Truncated Greedy  Algorithm (DTGA) to solve  it.  They take  advantage from both
+Truncated Greedy  Algorithm (DTGA) to solve  it.  They take advantage  from both

 temporal and spatial correlations between  data sensed by different sensors, and
 temporal and spatial correlations between  data sensed by different sensors, and

-leverage prediction, to improve  the lifetime.  In \cite{xu2001geography}, Xu et
-al.  have  described an algorithm, called Geographical  Adaptive Fidelity (GAF),
-which uses geographic  location information to divide the  area of interest into
-fixed square grids.   Within each grid, it keeps only one  node staying awake to
+leverage prediction, to improve the  lifetime.  In \cite{xu2001geography}, Xu et
+al.  have described  an algorithm, called Geographical  Adaptive Fidelity (GAF),
+which uses geographic  location information to divide the area  of interest into
+fixed square grids.  Within  each grid, it keeps only one  node staying awake to

 take the responsibility of sensing and communication.
 
 Some  other  approaches (outside  the  scope  of our  work)  do  not consider  a
 take the responsibility of sensing and communication.
 
 Some  other  approaches (outside  the  scope  of our  work)  do  not consider  a


@@ -289,39 +290,23 @@ Indeed, each sensor  maintains its own timer and its  wake-up time is randomized
 
 \subsection{Assumptions and primary points}
 \label{pp}
 
 \subsection{Assumptions and primary points}
 \label{pp}

-\textcolor{green}{Assumptions and coverage model are identical to those presented in~\cite{idrees2015distributed}.}
-
-
-\iffalse
-We  consider a  randomly and  uniformly  deployed network  consisting of  static
-wireless sensors.  The sensors are  deployed in high density to ensure initially
-a high  coverage ratio  of the interested  area.  We  assume that all  nodes are
-homogeneous  in   terms  of  communication  and   processing  capabilities,  and
-heterogeneous  from the  point  of view  of  energy provision.   Each sensor  is
-supposed  to get information  on its  location either  through hardware  such as
-embedded GPS or through location discovery algorithms.
-   
-To model  a sensor node's coverage  area, we consider the  boolean disk coverage
-model   which  is  the   most  widely   used  sensor   coverage  model   in  the
-literature. Thus, each  sensor has a constant sensing range  $R_s$ and all space
-points within  the disk centered  at the sensor  with the radius of  the sensing
-range  is  said  to  be  covered  by  this sensor.   We  also  assume  that  the
-communication   range  satisfies   $R_c  \geq   2R_s$.   In   fact,   Zhang  and
-Zhou~\cite{Zhang05} proved that if  the transmission range fulfills the previous
-hypothesis, a complete coverage of  a convex area implies connectivity among the
-active nodes.\fi
-
-\textcolor{green}{We consider a scenario where sensors are  deployed in high density to ensure initially
-a high  coverage ratio  of the interested  area. Each sensor has a predefined sensing range $R_s$, an initial energy supply (eventually different from each other) and is supposed to be equipped with module for locating its geographical positions. All space points within  the disk centered  at the sensor  with the radius of  the sensing
-range  is  said  to  be  covered  by  this sensor.}
+
+\textcolor{black}{The assumptions and the coverage model are identical to those presented
+  in~\cite{idrees2015distributed}. We  consider a  scenario in which  sensors are  deployed in  high
+  density to  initially ensure a high coverage ratio of the interested area. Each
+  sensor  has  a  predefined  sensing  range $R_s$,  an  initial  energy  supply
+  (eventually different  from each other)  and is  supposed to be  equipped with
+  a module to  locate its geographical  positions. All space points  within the
+  disk centered at the sensor with the radius of the sensing range are said to be
+  covered by this sensor.}

 
 \indent Instead of working with the coverage area, we consider for each sensor a
 set of  points called  primary points~\cite{idrees2014coverage}. We  assume that
 the sensing  disk defined by a  sensor is covered  if all the primary  points of
 this  sensor are  covered.   By knowing  the position  of  wireless sensor  node
 
 \indent Instead of working with the coverage area, we consider for each sensor a
 set of  points called  primary points~\cite{idrees2014coverage}. We  assume that
 the sensing  disk defined by a  sensor is covered  if all the primary  points of
 this  sensor are  covered.   By knowing  the position  of  wireless sensor  node

-(centered at  the the  position $\left(p_x,p_y\right)$)  and its  sensing range
-$R_s$,  we define  up to  25 primary  points $X_1$  to $X_{25}$  as decribed  on
-Figure~\ref{fig1}. The optimal number of primary points is investigated in
+(centered  at the  the position  $\left(p_x,p_y\right)$) and  its sensing  range
+$R_s$,  we define  up to  25 primary  points $X_1$  to $X_{25}$  as described  on
+Figure~\ref{fig1}.  The optimal  number  of primary  points  is investigated  in

 section~\ref{ch4:sec:04:06}.
 
 The coordinates of the primary points are defined as follows:\\
 section~\ref{ch4:sec:04:06}.
 
 The coordinates of the primary points are defined as follows:\\


@@ -361,61 +346,89 @@ $X_{25}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $.
 
 \subsection{Background idea}
 
 
 \subsection{Background idea}
 

-The WSN  area of  interest is,  at  first,  divided into
-  regular  homogeneous subregions  using  a divide-and-conquer  algorithm. Then, 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 and with high
-  density over the region. The regular  subdivision is made so that the number
-  of hops between any pairs of sensors  inside a subregion is less than or equal
-  to 3.
+The  WSN  area of  interest  is,  at  first,  divided into  regular  homogeneous
+subregions  using a  divide-and-conquer algorithm.  Then, 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 and with  high density  over the region.  The regular
+subdivision is  made so  that the number  of hops between  any pairs  of sensors
+inside a subregion is less than or equal to 3.

 
 As can  be seen  in Figure~\ref{fig2},  our protocol  works in  periods fashion,
 where   each   period   is    divided   into   4~phases:   Information~Exchange,
 
 As can  be seen  in Figure~\ref{fig2},  our protocol  works in  periods fashion,
 where   each   period   is    divided   into   4~phases:   Information~Exchange,

-Leader~Election,  Decision,  and Sensing. \textcolor{green}{Compared to protocol DiLCO described in~\cite{idrees2015distributed}}  each  sensing  phase is itself
-divided into $T$ rounds of  equal duration and for each round
-a set of sensors (a cover set) is  responsible for the sensing task. In this way
-a  multiround  optimization  process  is  performed  during  each  period  after
-Information~Exchange and Leader~Election  phases, in order to  produce $T$ cover
-sets that will take the mission of sensing for $T$ rounds. \textcolor{green}{Algorithm~\ref{alg:MuDiLCO} is
-executed  by  each sensor  node~$s_j$ (with enough remaining energy) at the  beginning  of a  period.}
+Leader~Election,  Decision, and  Sensing. \textcolor{black}{Compared  to 
+ the DiLCO protocol described in~\cite{idrees2015distributed},} each sensing phase is itself
+divided into $T$ rounds of equal duration and for each round a set of sensors (a
+cover  set) is  responsible  for the  sensing  task. In  this  way a  multiround
+optimization process is performed  during each period after Information~Exchange
+and Leader~Election  phases, in order to  produce $T$ cover sets  that will take
+the           mission           of           sensing           for           $T$
+rounds. \textcolor{black}{Algorithm~\ref{alg:MuDiLCO} is  executed by each sensor
+  node~$s_j$ (with enough remaining energy) at the beginning of a period.}

 \begin{figure}[t!]
 \centering \includegraphics[width=125mm]{Modelgeneral.pdf} % 70mm
 \caption{The MuDiLCO protocol scheme executed on each node}
 \label{fig2}
 \begin{figure}[t!]
 \centering \includegraphics[width=125mm]{Modelgeneral.pdf} % 70mm
 \caption{The MuDiLCO protocol scheme executed on each node}
 \label{fig2}

-\end{figure} 
+\end{figure}

 
 

-\textcolor{green}{As already described in~\cite{idrees2015distributed}}, two types of packets are used by the proposed protocol:
+\begin{algorithm}[h!]                
+  \BlankLine  
+  \If{ $RE_j \geq E_{R}$ }{
+      \emph{$s_j.status$ = COMMUNICATION}\;
+      \emph{Send $INFO()$ packet to other nodes in the subregion}\;
+      \emph{Wait $INFO()$ packet from other nodes in the subregion}\; 
+      
+      \emph{LeaderID = Leader election}\;
+      \If{$ s_j.ID = LeaderID $}{
+        \emph{$s_j.status$ = COMPUTATION}\;
+        \emph{$\left\{\left(X_{1,k},\dots,X_{T,k}\right)\right\}_{k \in J}$ =
+          Execute Integer Program Algorithm($T,J$)}\;
+        \emph{$s_j.status$ = COMMUNICATION}\;
+        \emph{Send $ActiveSleep()$ packet to each node $k$ in subregion: a packet \\
+          with vector of activity scheduling $(X_{1,k},\dots,X_{T,k})$}\;
+        \emph{Update $RE_j $}\;
+      }          
+      \Else{
+        \emph{$s_j.status$ = LISTENING}\;
+        \emph{Wait $ActiveSleep()$ packet from the Leader}\;
+        \emph{Update $RE_j $}\;
+      }  
+  }
+  \Else { Exclude $s_j$ from entering in the current sensing phase}
+  
+\caption{MuDiLCO($s_j$)}
+\label{alg:MuDiLCO}
+\end{algorithm}
+
+\textcolor{black}{As  already   described  in~\cite{idrees2015distributed}},  two
+types of packets are used by the proposed protocol:

 \begin{enumerate}[(a)] 
 \begin{enumerate}[(a)] 

-\item INFO  packet: such a  packet  will be sent by  each sensor node  to all the
+\item INFO  packet: such a packet  will be sent by  each sensor node to  all the

   nodes inside a subregion for information exchange.
 \item  Active-Sleep  packet: sent  by  the  leader to  all  the  nodes inside  a
   nodes inside a subregion for information exchange.
 \item  Active-Sleep  packet: sent  by  the  leader to  all  the  nodes inside  a

-  subregion to  inform them to remain Active  or to go Sleep  during the sensing
+  subregion to inform  them to remain Active  or to go Sleep  during the sensing

   phase.
 \end{enumerate}
 
 There are five status for each sensor node in the network:
 \begin{enumerate}[(a)] 
 \item LISTENING: sensor node is waiting for a decision (to be active or not);
   phase.
 \end{enumerate}
 
 There are five status for each sensor node in the network:
 \begin{enumerate}[(a)] 
 \item LISTENING: sensor node is waiting for a decision (to be active or not);

-\item  COMPUTATION: sensor  node  has been  elected  as leader  and applies  the
+\item  COMPUTATION: sensor  node  has been  elected as  leader  and applies  the

   optimization process;
 \item ACTIVE: sensor node is taking part in the monitoring of the area;
 \item SLEEP: sensor node is turned off to save energy;
 \item COMMUNICATION: sensor node is transmitting or receiving packet.
 \end{enumerate}
 
   optimization process;
 \item ACTIVE: sensor node is taking part in the monitoring of the area;
 \item SLEEP: sensor node is turned off to save energy;
 \item COMMUNICATION: sensor node is transmitting or receiving packet.
 \end{enumerate}
 

-
-
-

 This  protocol minimizes  the  impact of  unexpected node  failure  (not due  to
 This  protocol minimizes  the  impact of  unexpected node  failure  (not due  to

-batteries running out of energy), because it works in periods.
- On the one hand, if a node  failure is detected before making the decision, the
- node will not  participate to this phase,  and, on the other hand,  if the node
- failure occurs  after the  decision, the  sensing task of  the network  will be
- temporarily affected:  only during  the period  of sensing  until a  new period
- starts.  The   duration   of  the   rounds  is  a   predefined
-   parameter. Round duration  should be long enough to hide  the system control
-   overhead and  short enough to minimize  the negative effects in  case of node
-   failures.
+batteries running out of energy), because it works in periods.  On the one hand,
+if a  node failure  is detected before  making the decision,  the node  will not
+participate to this  phase, and, on the  other hand, if the  node failure occurs
+after  the  decision, the  sensing  task  of  the  network will  be  temporarily
+affected: only  during the  period of  sensing until a  new period  starts.  The
+duration of the rounds is a  predefined parameter. Round duration should be long
+enough to  hide the  system control  overhead and short  enough to  minimize the
+negative effects in case of node failures.

 
 The  energy consumption  and some  other constraints  can easily  be  taken into
 account,  since the  sensors  can  update and  then  exchange their  information
 
 The  energy consumption  and some  other constraints  can easily  be  taken into
 account,  since the  sensors  can  update and  then  exchange their  information


@@ -424,28 +437,23 @@ pre-sensing  phases (Information  Exchange, Leader  Election, and  Decision) are
 energy  consuming for some  nodes, even  when they  do not  join the  network to
 monitor the area.
 
 energy  consuming for some  nodes, even  when they  do not  join the  network to
 monitor the area.
 

-
-
-
-At the beginning of each period, each sensor wich has enough remaining energy ($RE_j$) to be alive during at least one round ( $E_{R}$ is the  amount of energy
-required to be alive during one round) sends (line 3 of algorithm~\ref{alg:MuDiLCO}) its position, remaining energy $RE_j$, and the number
-of neighbors $NBR_j$  to all wireless sensor nodes in its  subregion by using an
-INFO packet  (containing information on position  coordinates, current remaining
-energy, sensor node ID, number of its one-hop live neighbors) and then waits for
-packets sent by other nodes (line 4). 
-
-After  that, each node will have information about
-all  the sensor  nodes in  the subregion.  
- The  nodes in the  same subregion
-will select (line 5) a Wireless Sensor Node Leader (WSNL) based on the received information from all other nodes in
-the same subregion.  The selection criteria  are, in order of importance: larger
-number of  neighbors, larger  remaining energy,  and then  in case  of equality,
-larger index. Observations on previous simulations  suggest to use the number of
-one-hop neighbors as  the primary criterion to reduce energy  consumption due to
-the communications.\\
-
-
-
+At the beginning  of each period, each sensor which  has enough remaining energy
+($RE_j$) to be alive during at least  one round ($E_{R}$ is the amount of energy
+required    to   be    alive   during    one   round)    sends   (line    3   of
+Algorithm~\ref{alg:MuDiLCO})  its position,  remaining  energy  $RE_j$, and  the
+number of  neighbors $NBR_j$ to  all wireless sensor  nodes in its  subregion by
+using an  INFO packet (containing  information on position  coordinates, current
+remaining energy, sensor node ID, number of its one-hop live neighbors) and then
+waits for packets sent by other nodes (line 4).
+
+After that, each  node will have information  about all the sensor  nodes in the
+subregion.  The  nodes in  the same  subregion will select  (line 5)  a Wireless
+Sensor Node Leader (WSNL) based on the received information from all other nodes
+in the  same subregion.   The selection  criteria are,  in order  of importance:
+larger  number of  neighbors,  larger  remaining energy,  and  then  in case  of
+equality, larger index. Observations on  previous simulations suggest to use the
+number  of  one-hop  neighbors  as   the  primary  criterion  to  reduce  energy
+consumption due to the communications.

 
 %Each WSNL will solve an integer program to  select which cover
 %  sets will be  activated in the following sensing phase  to cover the subregion
 
 %Each WSNL will solve an integer program to  select which cover
 %  sets will be  activated in the following sensing phase  to cover the subregion


@@ -455,27 +463,28 @@ the communications.\\
 %  each round of the sensing phase.
 \subsection{Multiround Optimization model}
 \label{mom}
 %  each round of the sensing phase.
 \subsection{Multiround Optimization model}
 \label{mom}

-As shown in Algorithm~\ref{alg:MuDiLCO} at line 8, the leader (WNSL) will execute an optimization
-algorithm based on an integer program. to  select which cover
-sets will be  activated in the following sensing phase  to cover the subregion
-to which it belongs.  $T$ cover sets will be produced, one for each round. The
-WSNL will send an Active-Sleep packet to each sensor in the subregion based on
-the algorithm's results (line 10),  indicating if the sensor should be  active or not in
-each round of the sensing phase.
-
-
-The integer program is based on the model
-proposed by \cite{pedraza2006}  with some modifications, where  the objective is
-to find  a maximum  number of disjoint  cover sets.  To  fulfill this  goal, the
-authors proposed an integer program  which forces undercoverage and overcoverage
-of  targets to  become minimal  at  the same  time.  They  use binary  variables
-$x_{jl}$ to indicate if  sensor $j$ belongs to cover set $l$.   In our model, we
-consider binary variables  $X_{t,j}$ to determine the  possibility of activating
-sensor $j$ during round $t$ of a  given sensing phase.  We also consider primary
-points as targets.  The  set of primary points is denoted by $P$  and the set of
-sensors by  $J$. Only sensors  able to  be alive during  at least one  round are
-involved in the integer program. \textcolor{green}{Note that the proposed integer program is an extension of that formulated in~\cite{idrees2015distributed}, 
-variables are now indexed in addition with the number of round $t$.}
+
+As  shown in  Algorithm~\ref{alg:MuDiLCO}  at  line 8,  the  leader (WNSL)  will
+execute an  optimization algorithm  based on  an integer  program to  select the
+cover sets to be activated in the following sensing phase to cover the subregion
+to which it belongs.   $T$ cover sets will be produced, one  for each round. The
+WSNL will send an  Active-Sleep packet to each sensor in  the subregion based on
+the algorithm's results (line 10), indicating  if the sensor should be active or
+not in each round of the sensing phase.
+
+The integer  program is based on  the model proposed by  \cite{pedraza2006} with
+some modifications, where the objective is  to find a maximum number of disjoint
+cover sets.  To fulfill this goal, the authors proposed an integer program which
+forces undercoverage and  overcoverage of targets to become minimal  at the same
+time.  They use  binary variables $x_{jl}$ to indicate if  sensor $j$ belongs to
+cover  set  $l$.  In  our  model,  we  consider  binary variables  $X_{t,j}$  to
+determine the possibility  of activating sensor $j$ during round  $t$ of a given
+sensing phase.  We also consider primary  points as targets.  The set of primary
+points is denoted by $P$ and the set  of sensors by $J$. Only sensors able to be
+alive  during  at  least  one  round   are  involved  in  the  integer  program.
+\textcolor{black}{Note that the proposed integer  program is an
+  extension of the one   formulated  in~\cite{idrees2015distributed},  variables  are  now  indexed  in
+  addition with the number of round $t$.}

 
 For a  primary point  $p$, let $\alpha_{j,p}$  denote the indicator  function of
 whether the point $p$ is covered, that is:
 
 For a  primary point  $p$, let $\alpha_{j,p}$  denote the indicator  function of
 whether the point $p$ is covered, that is:


@@ -504,7 +513,7 @@ We define the Overcoverage variable $\Theta_{t,p}$ as:
 \begin{array}{l l}
   0 & \mbox{if the primary point $p$}\\
     & \mbox{is not covered during round $t$,}\\
 \begin{array}{l l}
   0 & \mbox{if the primary point $p$}\\
     & \mbox{is not covered during round $t$,}\\

-  \left( \sum_{j \in J} \alpha_{jp} * X_{tj} \right)- 1 & \mbox{otherwise.}\\
+  \left( \sum_{j \in J} \alpha_{jp} * X_{t,j} \right)- 1 & \mbox{otherwise.}\\

 \end{array} \right.
 \label{eq13} 
 \end{equation}
 \end{array} \right.
 \label{eq13} 
 \end{equation}


@@ -570,57 +579,17 @@ There are  two main  objectives.  First,  we limit  the overcoverage  of primary
 points in order to activate a minimum  number of sensors.  Second we prevent the
 absence  of  monitoring  on  some  parts of  the  subregion  by  minimizing  the
 undercoverage.  The weights  $W_\theta$ and $W_U$ must be properly  chosen so as
 points in order to activate a minimum  number of sensors.  Second we prevent the
 absence  of  monitoring  on  some  parts of  the  subregion  by  minimizing  the
 undercoverage.  The weights  $W_\theta$ and $W_U$ must be properly  chosen so as

-to guarantee that the maximum number of points are covered during each round.
+to guarantee  that the maximum number  of points are covered  during each round.

 In our simulations,  priority is given to the coverage  by choosing $W_{U}$ very
 large compared to $W_{\theta}$.
 
 In our simulations,  priority is given to the coverage  by choosing $W_{U}$ very
 large compared to $W_{\theta}$.
 

-The size of the problem depends  on the number of variables and
-  constraints. The number of variables is  linked to the number of alive sensors
-  $A \subseteq J$,  the number of rounds  $T$, and the number  of primary points
-  $P$.  Thus  the integer  program contains $A*T$  variables of  type $X_{t,j}$,
-  $P*T$ overcoverage variables and $P*T$  undercoverage variables. The number of
-  constraints  is equal  to $P*T$  (for constraints  (\ref{eq16})) $+$  $A$ (for
-  constraints (\ref{eq144})).
-
-\iffalse
-\subsection{Sensing phase}
-
-The sensing phase consists of $T$ rounds. Each sensor node in the subregion will
-receive an Active-Sleep packet from WSNL, informing it to stay awake or to go to
-sleep for each  round of the sensing  phase.  Algorithm~\ref{alg:MuDiLCO}, which
-will  be executed  by  each sensor  node~$s_j$  at the  beginning  of a  period,
-explains how the Active-Sleep packet is obtained.
-\fi
-
-\begin{algorithm}[h!]                
-  \BlankLine  
-  \If{ $RE_j \geq E_{R}$ }{
-      \emph{$s_j.status$ = COMMUNICATION}\;
-      \emph{Send $INFO()$ packet to other nodes in the subregion}\;
-      \emph{Wait $INFO()$ packet from other nodes in the subregion}\; 
-      
-      \emph{LeaderID = Leader election}\;
-      \If{$ s_j.ID = LeaderID $}{
-        \emph{$s_j.status$ = COMPUTATION}\;
-        \emph{$\left\{\left(X_{1,k},\dots,X_{T,k}\right)\right\}_{k \in J}$ =
-          Execute Integer Program Algorithm($T,J$)}\;
-        \emph{$s_j.status$ = COMMUNICATION}\;
-        \emph{Send $ActiveSleep()$ packet to each node $k$ in subregion: a packet \\
-          with vector of activity scheduling $(X_{1,k},\dots,X_{T,k})$}\;
-        \emph{Update $RE_j $}\;
-      }          
-      \Else{
-        \emph{$s_j.status$ = LISTENING}\;
-        \emph{Wait $ActiveSleep()$ packet from the Leader}\;
-        \emph{Update $RE_j $}\;
-      }  
-  }
-  \Else { Exclude $s_j$ from entering in the current sensing phase}
-  
-\caption{MuDiLCO($s_j$)}
-\label{alg:MuDiLCO}
+The size of the problem depends on  the number of variables and constraints. The
+number of variables  is linked to the  number of alive sensors  $A \subseteq J$,
+the  number of  rounds $T$,  and the  number of  primary points  $P$.  Thus  the
+integer program contains  $A*T$ variables of type  $X_{t,j}$, $P*T$ overcoverage
+variables and $P*T$ undercoverage variables.  The number of constraints is equal
+to $P*T$ (for constraints (\ref{eq16})) $+$ $A$ (for constraints (\ref{eq144})).

 
 

-\end{algorithm}

 
 \section{Experimental framework}
 \label{exp}
 
 \section{Experimental framework}
 \label{exp}


@@ -631,11 +600,11 @@ We  conducted  a series  of  simulations  to  evaluate  the efficiency  and  the
 relevance  of  our   approach,  using  the  discrete   event  simulator  OMNeT++
 \cite{varga}.  The  simulation parameters are summarized  in Table~\ref{table3}.
 Each experiment for a network is run over 25~different random topologies and the
 relevance  of  our   approach,  using  the  discrete   event  simulator  OMNeT++
 \cite{varga}.  The  simulation parameters are summarized  in Table~\ref{table3}.
 Each experiment for a network is run over 25~different random topologies and the

-results presented hereafter are the average of these 25 runs.
-We  performed  simulations for  five  different  densities  varying from  50  to
-250~nodes deployed  over a $50 \times  25~m^2 $ sensing field.   More precisely,
-the deployment  is controlled  at a  coarse scale  in order  to ensure  that the
-deployed nodes can cover the sensing field with the given sensing range.
+results presented  hereafter are  the average  of these  25 runs.   We performed
+simulations for five  different densities varying from 50  to 250~nodes deployed
+over a  $50 \times 25~m^2  $ sensing field.   More precisely, the  deployment is
+controlled at  a coarse  scale in order  to ensure that  the deployed  nodes can
+cover the sensing field with the given sensing range.

 
 \begin{table}[ht]
 \caption{Relevant parameters for network initializing.}
 
 \begin{table}[ht]
 \caption{Relevant parameters for network initializing.}


@@ -656,27 +625,26 @@ $W_{U}$ & $|P|^2$ \\
 \label{table3}
 \end{table}
 
 \label{table3}
 \end{table}
 

-Our  protocol  is  declined   into  four  versions:  MuDiLCO-1,
-  MuDiLCO-3, MuDiLCO-5, and MuDiLCO-7, corresponding respectively to $T=1,3,5,7$
-  ($T$ the  number of rounds in  one sensing period). Since  the time resolution
-  may  be prohibitive  when the  size  of the  problem increases,  a time  limit
-  threshold has  been fixed when  solving large  instances. In these  cases, the
-  solver returns  the best solution  found, which  is not necessary  the optimal
-  one. In practice, we only set time  limit values for $T=5$ and $T=7$. In fact,
-  for $T=5$ we limited the time for  250~nodes, whereas for $T=7$ it was for the
-  three  largest network  sizes.  Therefore  we  used the  following values  (in
-  second): 0.03 for  250~nodes when $T=5$, while for $T=7$  we chose 0.03, 0.06,
-  and  0.08  for  respectively  150,  200,  and  250~nodes.   These  time  limit
-  thresholds  have been  set  empirically. The  basic idea  is  to consider  the
-  average execution  time to solve  the integer  programs to optimality  for 100
-  nodes and then to adjust the time linearly according to the increasing network
-  size. After that,  this threshold value is increased if  necessary so that the
-  solver is able to deliver a feasible  solution within the time limit. In fact,
-  selecting the optimal  values for the time limits will  be investigated in the
-  future.
+Our protocol  is declined into  four versions: MuDiLCO-1,  MuDiLCO-3, MuDiLCO-5,
+and  MuDiLCO-7, corresponding  respectively to  $T=1,3,5,7$ ($T$  the number  of
+rounds in one sensing period). Since the time resolution may be prohibitive when
+the size of  the problem increases, a  time limit threshold has  been fixed when
+solving large  instances. In these cases,  the solver returns the  best solution
+found, which  is not necessary  the optimal one. In  practice, we only  set time
+limit values for  $T=5$ and $T=7$.  In  fact, for $T=5$ we limited  the time for
+250~nodes,  whereas for  $T=7$  it  was for  the  three  largest network  sizes.
+Therefore we  used the  following values  (in second):  0.03 for  250~nodes when
+$T=5$, while for $T=7$ we chose 0.03,  0.06, and 0.08 for respectively 150, 200,
+and 250~nodes.  These time limit thresholds have been set empirically. The basic
+idea is to consider the average execution  time to solve the integer programs to
+optimality for 100 nodes  and then to adjust the time  linearly according to the
+increasing  network size.   After that,  this  threshold value  is increased  if
+necessary so that the  solver is able to deliver a  feasible solution within the
+time limit. In  fact, selecting the optimal  values for the time  limits will be
+investigated in the future.

 
  In the  following, we will make  comparisons with two other  methods. The first
 
  In the  following, we will make  comparisons with two other  methods. The first

- method,  called DESK  and proposed  by  \cite{ChinhVu}, is  a full  distributed
+ method,  called DESK  and proposed  by \cite{ChinhVu},  is a  fully distributed

  coverage  algorithm.   The  second method,  called  GAF~\cite{xu2001geography},
  consists in dividing the region into fixed squares.  During the decision phase,
  in each square, one  sensor is then chosen to remain  active during the sensing
  coverage  algorithm.   The  second method,  called  GAF~\cite{xu2001geography},
  consists in dividing the region into fixed squares.  During the decision phase,
  in each square, one  sensor is then chosen to remain  active during the sensing


@@ -687,96 +655,44 @@ subregions  which subdivides  the sensing  field, considering  different network
 sizes. They show that as the number of subregions increases, so does the network
 lifetime. Moreover,  it makes  the MuDiLCO protocol  more robust  against random
 network  disconnection due  to node  failures.  However,  too many  subdivisions
 sizes. They show that as the number of subregions increases, so does the network
 lifetime. Moreover,  it makes  the MuDiLCO protocol  more robust  against random
 network  disconnection due  to node  failures.  However,  too many  subdivisions

-reduce the  advantage of the optimization.  In fact, there is  a balance between
+reduce the advantage  of the optimization.  In fact, there  is a balance between

 the benefit from the optimization and the  execution time needed to solve it. In
 the benefit from the optimization and the  execution time needed to solve it. In

-the following we have set the number of subregions to 16 \textcolor{green}{as recommended in~\cite{idrees2015distributed}}.
+the following  we have  set the number  of subregions  to~16 \textcolor{black}{as
+  recommended in~\cite{idrees2015distributed}}.

 
 \subsection{Energy model}
 
 \subsection{Energy model}

-\textcolor{green}{The energy consumption  model is detailed in~\cite{}. It is based on the model proposed by~\cite{ChinhVu}. We  refer to the sensor  node Medusa~II which
-uses an Atmels  AVR ATmega103L microcontroller~\cite{raghunathan2002energy} to use numerical values.}
-\textcolor{red}{Est-ce qu'il faut en ecrire plus et redonner le tableau de valeurs?}
-\iffalse
-\subsection{Energy model}
-
-We  use an  energy consumption  model  proposed by~\cite{ChinhVu}  and based  on
-\cite{raghunathan2002energy} with slight  modifications.  The energy consumption
-for  sending/receiving the packets  is added,  whereas the  part related  to the
-sensing range is removed because we consider a fixed sensing range.
-
-For our  energy consumption model, we  refer to the sensor  node Medusa~II which
-uses an Atmels  AVR ATmega103L microcontroller~\cite{raghunathan2002energy}. The
-typical  architecture  of a  sensor  is composed  of  four  subsystems: the  MCU
-subsystem which is capable of computation, communication subsystem (radio) which
-is responsible  for transmitting/receiving messages, the  sensing subsystem that
-collects  data, and  the  power supply  which  powers the  complete sensor  node
-\cite{raghunathan2002energy}. Each  of the first three subsystems  can be turned
-on or  off depending on  the current status  of the sensor.   Energy consumption
-(expressed in  milliWatt per second) for  the different status of  the sensor is
-summarized in Table~\ref{table4}.
-
-\begin{table}[ht]
-\caption{The Energy Consumption Model}
-\centering
-\begin{tabular}{|c|c|c|c|c|}
-  \hline
-Sensor status & MCU & Radio & Sensing & Power (mW) \\ [0.5ex]
-\hline
-LISTENING & on & on & on & 20.05 \\
-\hline
-ACTIVE & on & off & on & 9.72 \\
-\hline
-SLEEP & off & off & off & 0.02 \\
-\hline
-COMPUTATION & on & on & on & 26.83 \\
-\hline
-\end{tabular}
-
-\label{table4}
-\end{table}
-
-For the sake of simplicity we ignore the  energy needed to turn on the radio, to
-start up the sensor node, to move from one status to another, etc.
-Thus, when a sensor becomes active (i.e.,  it has already chosen its status), it
-can turn its radio  off to save battery.  MuDiLCO uses two  types of packets for
-communication. The size of the INFO  packet and Active-Sleep packet are 112~bits
-and 24~bits  respectively.  The value  of energy  spent to send  a 1-bit-content
-message is  obtained by using  the equation in  ~\cite{raghunathan2002energy} to
-calculate the  energy cost  for transmitting  messages and  we propose  the same
-value for receiving  the packets. The energy  needed to send or  receive a 1-bit
-packet is equal to 0.2575~mW.
-
-The initial energy of each node is  randomly set in the interval $[500;700]$.  A
-sensor node will  not participate in the  next round if its  remaining energy is
-less than  $E_{R}=36~\mbox{Joules}$, the minimum  energy needed for the  node to
-stay alive  during one round.  This  value has been computed  by multiplying the
-energy consumed in  active state (9.72 mW)  by the time in second  for one round
-(3600 seconds).   According to the interval  of initial energy, a  sensor may be
-alive during at most 20 rounds.
-\fi
+\textcolor{black}{The      energy     consumption      model     is      detailed
+  in~\cite{raghunathan2002energy}.   It  is   based   on   the  model   proposed
+  by~\cite{ChinhVu}. We refer to the sensor  node Medusa~II which uses an Atmels
+  AVR ATmega103L  microcontroller~\cite{raghunathan2002energy} to  use numerical
+  values.}  

 
 \subsection{Metrics}
 
 
 \subsection{Metrics}
 

-\textcolor{green} {To evaluate our approach we consider the performance metrics detailed in~\cite{idrees2015distributed} which are Coverage Ratio, Network Lifetime and Energy Consumption.  
-Compared to the previous definitions, formulations of Coverage Ratio and Energy Consumption are enriched with the index of round $t$.} 
+\textcolor{black}{To evaluate  our approach  we consider the  performance metrics
+  detailed in~\cite{idrees2015distributed},  which are: Coverage  Ratio, Network
+  Lifetime  and  Energy  Consumption.   Compared to  the  previous  definitions,
+  formulations of  Coverage Ratio and  Energy Consumption are enriched  with the
+  index of round $t$.}

 
 \begin{enumerate}[i]
   
 
 \begin{enumerate}[i]
   

-\item {{\bf Coverage Ratio (CR)}:} the coverage ratio measures how much of the area
-  of a sensor field is covered. In our case, the sensing field is represented as
-  a connected grid  of points and we use  each grid point as a  sample point to
-  compute the coverage. The coverage ratio can be calculated by:
+\item {{\bf Coverage  Ratio (CR)}:} the coverage ratio measures  how much of the
+  area  of  a sensor  field  is  covered. In  our  case,  the sensing  field  is
+  represented as  a connected grid  of points  and we use  each grid point  as a
+  sample point to compute the coverage. The coverage ratio can be calculated by:

 \begin{equation*}
 \scriptsize
 \mbox{CR}(\%) = \frac{\mbox{$n^t$}}{\mbox{$N$}} \times 100,
 \end{equation*}
 where $n^t$ is  the number of covered  grid points by the active  sensors of all
 \begin{equation*}
 \scriptsize
 \mbox{CR}(\%) = \frac{\mbox{$n^t$}}{\mbox{$N$}} \times 100,
 \end{equation*}
 where $n^t$ is  the number of covered  grid points by the active  sensors of all

-subregions during round $t$ in the current sensing phase and $N$ is the total number
-of grid points  in the sensing field of  the network. In our simulations $N = 51
-\times 26 = 1326$ grid points.
+subregions during round  $t$ in the current  sensing phase and $N$  is the total
+number of grid points in the sensing field of the network. In our simulations $N
+= 51 \times 26 = 1326$ grid points.

 
 \item{{\bf Number  of Active Sensors Ratio  (ASR)}:} it is important  to have as
 
 \item{{\bf Number  of Active Sensors Ratio  (ASR)}:} it is important  to have as

-  few  active  nodes  as  possible  in  each  round, in  order  to  minimize  the
-  communication overhead  and maximize the network lifetime.  The Active Sensors
+  few  active  nodes  as possible  in  each  round,  in  order to  minimize  the
+  communication overhead and maximize the  network lifetime.  The Active Sensors

   Ratio is defined as follows:
 \begin{equation*}
 \scriptsize  \mbox{ASR}(\%) = \frac{\sum\limits_{r=1}^R
   Ratio is defined as follows:
 \begin{equation*}
 \scriptsize  \mbox{ASR}(\%) = \frac{\sum\limits_{r=1}^R


@@ -787,18 +703,18 @@ $t$ in the  current sensing phase, $|J|$  is the total number of  sensors in the
 network, and $R$ is the total number of subregions in the network.
 
 \item {{\bf Network Lifetime}:} we define the network lifetime as the time until
 network, and $R$ is the total number of subregions in the network.
 
 \item {{\bf Network Lifetime}:} we define the network lifetime as the time until

-  the  coverage  ratio  drops  below   a  predefined  threshold.  We  denote  by
-  $Lifetime_{95}$ (respectively  $Lifetime_{50}$) the amount of  time during
-  which  the  network   can  satisfy  an  area  coverage   greater  than  $95\%$
-  (respectively $50\%$). We assume that the network is alive until all nodes have
-  been   drained    of   their   energy   or   the    sensor   network   becomes
-  disconnected. Network connectivity is  important because an active sensor node
-  without connectivity towards a base  station cannot transmit information on an
-  event in the area that it monitors.
+  the  coverage  ratio  drops  below  a  predefined  threshold.   We  denote  by
+  $Lifetime_{95}$ (respectively $Lifetime_{50}$) the amount of time during which
+  the network  can satisfy  an area coverage  greater than  $95\%$ (respectively
+  $50\%$). We assume that the network is alive until all nodes have been drained
+  of  their  energy   or  the  sensor  network   becomes  disconnected.  Network
+  connectivity is important  because an active sensor  node without connectivity
+  towards a  base station cannot  transmit information on  an event in  the area
+  that it monitors.

 
 \item {{\bf  Energy Consumption  (EC)}:} the average  energy consumption  can be
   seen as the total energy consumed by the sensors during the $Lifetime_{95}$ or
 
 \item {{\bf  Energy Consumption  (EC)}:} the average  energy consumption  can be
   seen as the total energy consumed by the sensors during the $Lifetime_{95}$ or

-  $Lifetime_{50}$  divided  by the  number  of rounds.  EC  can  be computed  as
+  $Lifetime_{50}$  divided by  the  number of  rounds.  EC  can  be computed  as

   follows:
 
   \begin{equation*}
   follows:
 
   \begin{equation*}


@@ -822,21 +738,7 @@ indicate the energy consumed by the whole network in round $t$.
 %nodes  have  been drained  of  their  energy  or each  sensor  network monitoring  an area has become  disconnected.
 \end{enumerate}
 
 %nodes  have  been drained  of  their  energy  or each  sensor  network monitoring  an area has become  disconnected.
 \end{enumerate}
 

-\iffalse
-\begin{enumerate}
- \setcounter{5}
-\item {{\bf  Execution Time}:}  a sensor node  has limited energy  resources and
-  computing power, therefore it is important that the proposed algorithm has the
-  shortest possible execution  time. The energy of a sensor  node must be mainly
-  used for the sensing phase, not for the pre-sensing ones.
-  
-\item {{\bf Stopped simulation runs}:} a simulation ends when the sensor network
-  becomes disconnected (some nodes are dead and are not able to send information
-  to the base station). We report the number of simulations that are stopped due
-  to network disconnections and for which round it occurs.

 
 

-\end{enumerate}
-\fi

 
 \section{Experimental results and analysis}
 \label{analysis}
 
 \section{Experimental results and analysis}
 \label{analysis}


@@ -844,45 +746,49 @@ indicate the energy consumed by the whole network in round $t$.
 \subsection{Performance analysis for different number of primary points}
 \label{ch4:sec:04:06}
 
 \subsection{Performance analysis for different number of primary points}
 \label{ch4:sec:04:06}
 

-In this  section, we study the  performance of MuDiLCO-1 approach (with only one round as in~\cite{idrees2015distributed}) for different
-numbers of  primary points. The  objective of this  comparison is to  select the
-suitable number  of primary points  to be used by  a MuDiLCO protocol.   In this
-comparison,  MuDiLCO-1 protocol  is used  with five  primary point  models, each
-model corresponding to a number of  primary points, which are called Model-5 (it
-uses 5 primary points), Model-9, Model-13, Model-17, and Model-21. \textcolor{green}{Note that results presented in~\cite{idrees2015distributed} corresponds to Model-13 (13 primary points)}.
+In this section,  we study the performance of MuDiLCO-1  approach (with only one
+round  as  in~\cite{idrees2015distributed})  for different  numbers  of  primary
+points. The  objective of this  comparison is to  select the suitable  number of
+primary points to be used by  a MuDiLCO protocol.  In this comparison, MuDiLCO-1
+protocol is used  with five primary point models, each  model corresponding to a
+number of primary  points, which are called Model-5 (it  uses 5 primary points),
+Model-9, Model-13,  Model-17, and  Model-21. \textcolor{black}{Note
+  that the results
+  presented in~\cite{idrees2015distributed}  correspond to Model-13  (13 primary
+  points)}.

 
 \subsubsection{Coverage ratio} 
 
 Figure~\ref{Figures/ch4/R2/CR} shows the average coverage ratio for 150 deployed
 nodes.  As can be seen, at the beginning the models which use a larger number of
 primary points provide slightly better coverage  ratios, but latter they are the
 
 \subsubsection{Coverage ratio} 
 
 Figure~\ref{Figures/ch4/R2/CR} shows the average coverage ratio for 150 deployed
 nodes.  As can be seen, at the beginning the models which use a larger number of
 primary points provide slightly better coverage  ratios, but latter they are the

-worst.
-Moreover, when the  number of periods increases, the coverage  ratio produced by
-all models  decrease due  to dead nodes.  However, Model-5 is  the one  with the
-slowest decrease due to lower numbers of active sensors in the earlier periods.
-Overall this  model is slightly more  efficient than the other  ones, because it
-offers a good coverage ratio for a larger number of periods.
+worst.   Moreover, when  the number  of  periods increases,  the coverage  ratio
+produced by all models decrease due to  dead nodes.  However, Model-5 is the one
+with the slowest decrease due to lower  numbers of active sensors in the earlier
+periods.  Overall  this model is  slightly more  efficient than the  other ones,
+because it offers a good coverage ratio for a larger number of periods.
+

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

- \includegraphics[scale=0.5] {R2/CR.pdf} 
+ \includegraphics[scale=0.5] {R2CR.pdf} 

 \caption{Coverage ratio for 150 deployed nodes}
 \label{Figures/ch4/R2/CR}
 \end{figure} 
 
 \subsubsection{Network lifetime}
 
 \caption{Coverage ratio for 150 deployed nodes}
 \label{Figures/ch4/R2/CR}
 \end{figure} 
 
 \subsubsection{Network lifetime}
 

-Finally, we study the effect of increasing the number of primary points on the lifetime of the network. 
-As       highlighted       by       Figures~\ref{Figures/ch4/R2/LT}(a)       and
-\ref{Figures/ch4/R2/LT}(b), the  network lifetime  obviously increases  when the
-size of the network increases, with  Model-5 which leads to the largest lifetime
-improvement.
+Finally, we study the  effect of increasing the number of  primary points on the
+lifetime of  the network.  As highlighted  by Figures~\ref{Figures/ch4/R2/LT}(a)
+and \ref{Figures/ch4/R2/LT}(b),  the network  lifetime obviously  increases when
+the  size of  the network  increases, with  Model-5 which  leads to  the largest
+lifetime improvement.

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

-\includegraphics[scale=0.5]{R2/LT95.pdf}\\~ ~ ~ ~ ~(a) \\
+\includegraphics[scale=0.5]{R2LT95.pdf}\\~ ~ ~ ~ ~(a) \\

 
 

-\includegraphics[scale=0.5]{R2/LT50.pdf}\\~ ~ ~ ~ ~(b)
+\includegraphics[scale=0.5]{R2LT50.pdf}\\~ ~ ~ ~ ~(b)

 
 \caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$}
   \label{Figures/ch4/R2/LT}
 
 \caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$}
   \label{Figures/ch4/R2/LT}


@@ -897,7 +803,7 @@ experiments presented thereafter.
 \subsection{Coverage ratio} 
 
 Figure~\ref{fig3} shows  the average coverage  ratio for 150 deployed  nodes. We
 \subsection{Coverage ratio} 
 
 Figure~\ref{fig3} shows  the average coverage  ratio for 150 deployed  nodes. We

-can notice that for the first thirty rounds both DESK and GAF provide a coverage
+can notice  that for the  first 30~rounds both DESK  and GAF provide  a coverage

 which is a little  bit better than the one of MuDiLCO.  This  is due to the fact
 that, in comparison with MuDiLCO which  uses optimization to put in SLEEP status
 redundant sensors,  more sensor  nodes remain  active with DESK  and GAF.   As a
 which is a little  bit better than the one of MuDiLCO.  This  is due to the fact
 that, in comparison with MuDiLCO which  uses optimization to put in SLEEP status
 redundant sensors,  more sensor  nodes remain  active with DESK  and GAF.   As a


@@ -908,13 +814,12 @@ greater than  50\% for far more  rounds.  Overall, the proposed  sensor activity
 scheduling based on optimization in  MuDiLCO maintains higher coverage ratios of
 the area of interest  for a larger number of rounds. It  also means that MuDiLCO
 saves more energy,  with less dead nodes,  at most for several  rounds, and thus
 scheduling based on optimization in  MuDiLCO maintains higher coverage ratios of
 the area of interest  for a larger number of rounds. It  also means that MuDiLCO
 saves more energy,  with less dead nodes,  at most for several  rounds, and thus

-should  extend the  network lifetime.  MuDiLCO-7 seems  to have
-  most of the  time the best coverage  ratio up to round~80,  after that MuDiLCO-5 is
-  slightly better.
+should extend  the network lifetime.  MuDiLCO-7  seems to have most  of the time
+the best coverage ratio up to round~80, after that MuDiLCO-5 is slightly better.

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

- \includegraphics[scale=0.5] {F/CR.pdf} 
+ \includegraphics[scale=0.5] {FCR.pdf} 

 \caption{Average coverage ratio for 150 deployed nodes}
 \label{fig3}
 \end{figure} 
 \caption{Average coverage ratio for 150 deployed nodes}
 \label{fig3}
 \end{figure} 


@@ -933,28 +838,28 @@ efficient manner.
 
 \begin{figure}[ht!]
 \centering
 
 \begin{figure}[ht!]
 \centering

-\includegraphics[scale=0.5]{F/ASR.pdf}  
+\includegraphics[scale=0.5]{FASR.pdf}  

 \caption{Active sensors ratio for 150 deployed nodes}
 \label{fig4}
 \end{figure} 
 
 \subsection{Stopped simulation runs}
 \caption{Active sensors ratio for 150 deployed nodes}
 \label{fig4}
 \end{figure} 
 
 \subsection{Stopped simulation runs}

-A simulation ends when the sensor network
-  becomes disconnected (some nodes are dead and are not able to send information
-  to the base station). We report the number of simulations that are stopped due
-  to network disconnections and for which round it occurs.
-Figure~\ref{fig6} reports the cumulative  percentage of stopped simulations runs
-per round  for 150  deployed nodes.  This figure gives  the breakpoint  for each
-method.  DESK  stops first, after  approximately 45~rounds, because  it consumes
-the more  energy by  turning on  a large  number of  redundant nodes  during the
-sensing  phase. GAF  stops  secondly for  the  same reason  than  DESK.  Let  us
-emphasize that the simulation  continues as long as a network  in a subregion is
-still connected.
+
+A simulation ends  when the sensor network becomes disconnected  (some nodes are
+dead and are not  able to send information to the base  station).  We report the
+number of  simulations that are  stopped due  to network disconnections  and for
+which round it  occurs.  Figure~\ref{fig6} reports the  cumulative percentage of
+stopped simulations  runs per round for  150 deployed nodes.  This  figure gives
+the  break  point  for  each  method.  DESK  stops  first,  after  approximately
+45~rounds, because it consumes  the more energy by turning on  a large number of
+redundant nodes during the sensing phase. GAF stops secondly for the same reason
+than DESK.  Let us emphasize that the  simulation continues as long as a network
+in a subregion is still connected.

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

-\includegraphics[scale=0.5]{F/SR.pdf} 
-\caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes }
+\includegraphics[scale=0.5]{FSR.pdf} 
+\caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes}

 \label{fig6}
 \end{figure} 
 
 \label{fig6}
 \end{figure} 
 


@@ -969,9 +874,9 @@ network sizes, for $Lifetime_{95}$ and $Lifetime_{50}$.
 \begin{figure}[h!]
   \centering
   \begin{tabular}{cl}
 \begin{figure}[h!]
   \centering
   \begin{tabular}{cl}

-    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC95.pdf}} & (a) \\
+    \parbox{9.5cm}{\includegraphics[scale=0.5]{FEC95.pdf}} & (a) \\

     \verb+ + \\
     \verb+ + \\

-    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC50.pdf}} & (b)
+    \parbox{9.5cm}{\includegraphics[scale=0.5]{FEC50.pdf}} & (b)

   \end{tabular}
   \caption{Energy consumption for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}
   \end{tabular}
   \caption{Energy consumption for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}


@@ -983,51 +888,52 @@ consumption point of view.  The other  approaches have a high energy consumption
 due to  activating a  larger number  of redundant  nodes as  well as  the energy
 consumed during the different status of the sensor node.
 
 due to  activating a  larger number  of redundant  nodes as  well as  the energy
 consumed during the different status of the sensor node.
 

-Energy consumption increases with the  size of the networks and
-  the  number  of  rounds.   The curve  Unlimited-MuDiLCO-7  shows  that  energy
-  consumption due to  the time spent to  optimally solve the  integer program
-  increases drastically with  the size of the network. When  the resolution time
-  is limited for large network sizes, the energy consumption remains of the same
-  order whatever the MuDiLCO version. As can be seen with MuDiLCO-7.
+Energy consumption  increases with the  size of the  networks and the  number of
+rounds.  The curve Unlimited-MuDiLCO-7 shows  that energy consumption due to the
+time spent to optimally solve the integer program increases drastically with the
+size  of the  network. When  the resolution  time is  limited for  large network
+sizes, the  energy consumption remains  of the  same order whatever  the MuDiLCO
+version. As can be seen with MuDiLCO-7.

 
 \subsection{Execution time}
 \label{et}
 
 \subsection{Execution time}
 \label{et}

+

 We observe  the impact of the  network size and of  the number of rounds  on the
 computation  time.   Figure~\ref{fig77} gives  the  average  execution times  in
 We observe  the impact of the  network size and of  the number of rounds  on the
 computation  time.   Figure~\ref{fig77} gives  the  average  execution times  in

-seconds (needed to solve optimization problem)  for different values of $T$. The
-modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is employed to
-generate the Mixed  Integer Linear 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)  \cite{glpk}  through a  Branch-and-Bound
-method. The  original execution  time is  computed on a  laptop DELL  with Intel
-Core~i3~2370~M (2.4 GHz) processor (2  cores) and the MIPS (Million Instructions
-Per Second) rate equal to 35330. To be  consistent with the use of a sensor node
-with Atmels AVR ATmega103L microcontroller (6 MHz) and a MIPS rate equal to 6 to
-run  the optimization  resolution, this  time  is multiplied  by 2944.2  $\left(
-\frac{35330}{2} \times  \frac{1}{6} \right)$ and reported  on Figure~\ref{fig77}
-for different network sizes.
+seconds  (needed to  solve the  optimization  problem) for  different values  of
+$T$. The  modeling language  for Mathematical Programming  (AMPL)~\cite{AMPL} is
+employed to  generate the Mixed  Integer Linear  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) \cite{glpk}  through a
+Branch-and-Bound method.  The original  execution time is  computed on  a laptop
+DELL  with Intel  Core~i3~2370~M  (2.4 GHz)  processor (2  cores)  and the  MIPS
+(Million Instructions Per Second) rate equal to 35330. To be consistent with the
+use of a  sensor node with Atmels  AVR ATmega103L microcontroller (6  MHz) and a
+MIPS rate equal to 6 to run the optimization resolution, this time is multiplied
+by 2944.2  $\left( \frac{35330}{2} \times  \frac{1}{6} \right)$ and  reported on
+Figure~\ref{fig77} for different network sizes.

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

-\includegraphics[scale=0.5]{F/T.pdf}  
+\includegraphics[scale=0.5]{FT.pdf}  

 \caption{Execution Time (in seconds)}
 \label{fig77}
 \end{figure} 
 
 As expected,  the execution time increases  with the number of  rounds $T$ taken
 \caption{Execution Time (in seconds)}
 \label{fig77}
 \end{figure} 
 
 As expected,  the execution time increases  with the number of  rounds $T$ taken

-into  account to  schedule  the sensing  phase. Obviously,  the
-  number of variables and constraints of the integer program increases with $T$,
-  as  explained  in section~\ref{mom}, the times obtained  for $T=1,3$ or
-  $5$ seem  bearable. But for  $T=7$, without any  limitation of the  time, they
-  become  quickly unsuitable  for  a  sensor node,  especially  when the  sensor
-  network size  increases as  demonstrated by Unlimited-MuDiLCO-7.   Notice that
-  for 250  nodes, we also  limited the execution  time for $T=5$,  otherwise the
-  execution time, denoted by Unlimited-MuDiLCO-5, is also above  MuDiLCO-7.  On the  one hand,  a large
-  value  for  $T$  permits  to  reduce the  energy-overhead  due  to  the  three
-  pre-sensing phases, on  the other hand a leader node  may waste a considerable
-  amount of  energy to solve the  optimization problem. Thus, limiting  the time
-  resolution for large instances allows to reduce the energy consumption without
-  any impact on the coverage quality.
+into account to  schedule the sensing phase. Obviously, the  number of variables
+and  constraints of  the integer  program increases  with $T$,  as explained  in
+section~\ref{mom}, the times obtained for $T=1,3$  or $5$ seem bearable. But for
+$T=7$, without any limitation of the  time, they become quickly unsuitable for a
+sensor node, especially  when the sensor network size  increases as demonstrated
+by  Unlimited-MuDiLCO-7.   Notice  that  for  250 nodes,  we  also  limited  the
+execution   time  for   $T=5$,  otherwise   the  execution   time,  denoted   by
+Unlimited-MuDiLCO-5, is  also above MuDiLCO-7.  On  the one hand, a  large value
+for  $T$ permits  to reduce  the energy-overhead  due to  the three  pre-sensing
+phases, on  the other  hand a  leader node  may waste  a considerable  amount of
+energy to solve the optimization problem. Thus, limiting the time resolution for
+large instances  allows to reduce the  energy consumption without any  impact on
+the coverage quality.

 
 \subsection{Network lifetime}
 
 
 \subsection{Network lifetime}
 


@@ -1046,21 +952,20 @@ lifetime for a coverage  over 95\%, and a network of  250~nodes, is greater than
 %This  point was  already noticed  in subsection  \ref{subsec:EC} devoted  to the
 %energy consumption,  since network lifetime and energy  consumption are directly
 %linked.
 %This  point was  already noticed  in subsection  \ref{subsec:EC} devoted  to the
 %energy consumption,  since network lifetime and energy  consumption are directly
 %linked.

-Overall,  it  clearly appears  that  computing a  scheduling for
-  several rounds is possible and relevant,  providing that the execution time to
-  solve the  optimization problem for  large instances is limited.   Notice that
-  rather than limiting the execution time,  similar results might be obtained by
-  replacing  the  computation of  the  exact  solution  with  the finding  of  a
-  suboptimal  one using  a  heuristic  approach. For  our  simulation setup  and
-  considering  the different  metrics, MuDiLCO-5  seems  to be  the best  suited
-  method compared to MuDiLCO-7.
+Overall, it  clearly appears that computing  a scheduling for several  rounds is
+possible  and  relevant,  providing  that   the  execution  time  to  solve  the
+optimization problem  for large instances  is limited.  Notice that  rather than
+limiting the execution time, similar results  might be obtained by replacing the
+computation of the exact  solution with the finding of a  suboptimal one using a
+heuristic  approach. For  our  simulation setup  and  considering the  different
+metrics, MuDiLCO-5 seems to be the best suited method compared to MuDiLCO-7.

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

-    \parbox{9.5cm}{\includegraphics[scale=0.5125]{F/LT95.pdf}} & (a) \\
+    \parbox{9.5cm}{\includegraphics[scale=0.5125]{FLT95.pdf}} & (a) \\

     \verb+ + \\
     \verb+ + \\

-    \parbox{9.5cm}{\includegraphics[scale=0.5125]{F/LT50.pdf}} & (b)
+    \parbox{9.5cm}{\includegraphics[scale=0.5125]{FLT50.pdf}} & (b)

   \end{tabular}
   \caption{Network lifetime for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}
   \end{tabular}
   \caption{Network lifetime for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}


@@ -1088,22 +993,24 @@ lifetime, coverage  ratio, active  sensors ratio, energy  consumption, execution
 time. Indeed,  when dealing with  large wireless sensor networks,  a distributed
 approach, like the one  we propose, allows to reduce the  difficulty of a single
 global optimization problem by partitioning it in many smaller problems, one per
 time. Indeed,  when dealing with  large wireless sensor networks,  a distributed
 approach, like the one  we propose, allows to reduce the  difficulty of a single
 global optimization problem by partitioning it in many smaller problems, one per

-subregion,  that  can be  solved  more  easily. Furthermore,
-  results  also show  that to  plan the  activity of  sensors for  large network
-  sizes, an  approach to obtain  a near optimal  solution is needed.  Indeed, an
-  exact resolution  of the resulting  optimization problem leads  to prohibitive
-  computation times and thus to an excessive energy consumption.
+subregion, that can  be solved more easily. Furthermore, results  also show that
+to plan the activity of sensors for large network sizes, an approach to obtain a
+near optimal solution  is needed.  Indeed, an exact resolution  of the resulting
+optimization  problem leads  to prohibitive  computation  times and  thus to  an
+excessive energy consumption.

 
 %In  future work, we plan  to study and propose adjustable sensing range coverage optimization protocol, which computes  all active sensor schedules in one time, by using
 %optimization  methods. This protocol can prolong the network lifetime by minimizing the number of the active sensor nodes near the borders by optimizing the sensing range of sensor nodes.
 % use section* for acknowledgement
 
 \section*{Acknowledgment}
 
 %In  future work, we plan  to study and propose adjustable sensing range coverage optimization protocol, which computes  all active sensor schedules in one time, by using
 %optimization  methods. This protocol can prolong the network lifetime by minimizing the number of the active sensor nodes near the borders by optimizing the sensing range of sensor nodes.
 % use section* for acknowledgement
 
 \section*{Acknowledgment}

-This work is  partially funded by the Labex ACTION program (contract ANR-11-LABX-01-01).
-As a Ph.D.  student, Ali Kadhum IDREES would like to gratefully acknowledge the
-University  of Babylon  - Iraq  for the  financial support,  Campus  France (The
-French  national agency  for the  promotion of  higher  education, international
-student   services,  and   international  mobility).%,   and  the   University  ofFranche-Comt\'e - France for all the support in France. 
+This  work   is  partially  funded   by  the  Labex  ACTION   program  (contract
+ANR-11-LABX-01-01). Ali Kadhum  IDREES would like to  gratefully acknowledge the
+University of  Babylon - Iraq for  the financial support and  Campus France (The
+French  national agency  for the  promotion of  higher education,  international
+student services, and  international mobility) for the support  received when he
+was Ph.D. student in France.
+%, and the University ofFranche-Comt\'e - France for all the support in France.