version amélioree pour eviter copie

diff --git a/article.bib b/article.bib
index b53ef03742f8a0bd468ae5ae522cdff49af9bb48..2bb24a73504393ad5bddae73059d04133caf5787 100644 (file)
--- a/article.bib
+++ b/article.bib
@@ -582,4 +582,16 @@ title={α-Coverage to extend network lifetime on wireless sensor networks},
 publisher={Springer-Verlag},
 author={Gentili, Monica and Raiconi, Andrea},
 pages={157-172},
 publisher={Springer-Verlag},
 author={Gentili, Monica and Raiconi, Andrea},
 pages={157-172},

-}
\ No newline at end of file
+}
+
+
+@article{idrees2015distributed,
+  title={Distributed lifetime coverage optimization protocol in wireless sensor networks},
+  author={Idrees, Ali Kadhum and Deschinkel, Karine and Salomon, Michel and Couturier, Rapha{\"e}l},
+  journal={The Journal of Supercomputing},
+  volume={71},
+  number={12},
+  pages={4578--4593},
+  year={2015},
+  publisher={Springer US}
+}

diff --git a/article.tex b/article.tex
index 629a7e41f74847847475ceca7f9c9a1fee783b2d..d886626c1b878f11ac8d571651f3212e606102ec 100644 (file)
--- a/article.tex
+++ b/article.tex
@@ -41,7 +41,7 @@
 %% for the whole article with \linenumbers.
 %% \usepackage{lineno}
 
 %% for the whole article with \linenumbers.
 %% \usepackage{lineno}
 

-\journal{Ad Hoc Networks}
+\journal{Journal of Supercomputing}

 
 \begin{document}
 
 
 \begin{document}
 


@@ -86,7 +86,7 @@
 
 \author{Ali   Kadhum   Idrees$^{a,b}$,   Karine  Deschinkel$^{a}$,   \\   Michel
   Salomon$^{a}$,   and  Rapha\"el   Couturier   $^{a}$  \\   $^{a}${\em{FEMTO-ST
 
 \author{Ali   Kadhum   Idrees$^{a,b}$,   Karine  Deschinkel$^{a}$,   \\   Michel
   Salomon$^{a}$,   and  Rapha\"el   Couturier   $^{a}$  \\   $^{a}${\em{FEMTO-ST

-      Institute,  UMR  6174  CNRS,   \\  University  Bourgogne  Franche-Comt\'e,
+      Institute/CNRS,   \\  Univ.  Bourgogne  Franche-Comt\'e,

       Belfort, France}} \\ $^{b}${\em{Department of Computer Science, University
       of Babylon, Babylon, Iraq}} }
 
       Belfort, France}} \\ $^{b}${\em{Department of Computer Science, University
       of Babylon, Babylon, Iraq}} }
 


@@ -99,13 +99,13 @@ 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.   \textcolor{blue}{The  decision process  is
+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
   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.} 
+  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
 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


@@ -142,6 +142,23 @@ regions to turn-off redundant sensor nodes  and thus save energy. In this paper,
 we concentrate  on the area coverage  problem, with the  objective of maximizing
 the network lifetime by using an optimized multiround scheduling.
 
 we concentrate  on the area coverage  problem, with the  objective of maximizing
 the network lifetime by using an optimized multiround scheduling.
 

+The MuDiLCO protocol (for  Multiround Distributed Lifetime Coverage Optimization
+protocol) presented  in this paper  is an  extension of the  approach introduced
+in~\cite{idrees2015distributed}.  
+% In~\cite{idrees2015distributed},  the  protocol  is
+%deployed over  only two subregions.  Simulation results  have shown that  it was
+%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
+  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
 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


@@ -184,11 +201,11 @@ network. Note that  centralized algorithms have the advantage  of requiring very
 low  processing  power  from  the  sensor  nodes,  which  usually  have  limited
 processing  capabilities. The  main drawback  of this  kind of  approach is  its
 higher cost in communications, since the  node that will make the decision needs
 low  processing  power  from  the  sensor  nodes,  which  usually  have  limited
 processing  capabilities. The  main drawback  of this  kind of  approach is  its
 higher cost in communications, since the  node that will make the decision needs

-information  from all  the  sensor nodes.   \textcolor{blue}{Exact or  heuristic
+information  from all  the  sensor nodes.   Exact or  heuristic

   approaches  are designed  to provide  cover sets.  Contrary to  exact methods,
   heuristic  ones can  handle very  large  and centralized  problems.  They  are
   proposed to reduce  computational overhead such as  energy consumption, delay,
   approaches  are designed  to provide  cover sets.  Contrary to  exact methods,
   heuristic  ones can  handle very  large  and centralized  problems.  They  are
   proposed to reduce  computational overhead such as  energy consumption, delay,

-  and generally allow to increase the network lifetime.}
+  and generally allow to increase the network lifetime.

 
 The first algorithms proposed in the literature consider that the cover sets are
 disjoint:  a  sensor  node  appears  in  exactly  one  of  the  generated  cover
 
 The first algorithms proposed in the literature consider that the cover sets are
 disjoint:  a  sensor  node  appears  in  exactly  one  of  the  generated  cover


@@ -213,9 +230,9 @@ selection algorithm to minimize the number of  active nodes so as to prolong the
 network  lifetime.   Various  centralized  methods based  on  column  generation
 approaches                   have                    also                   been
 proposed~\cite{gentili2013,castano2013column,rossi2012exact,deschinkel2012column}.
 network  lifetime.   Various  centralized  methods based  on  column  generation
 approaches                   have                    also                   been
 proposed~\cite{gentili2013,castano2013column,rossi2012exact,deschinkel2012column}.

-\textcolor{blue}{In~\cite{gentili2013}, authors highlight  the trade-off between
+In~\cite{gentili2013}, authors highlight  the trade-off between

   the  network lifetime  and the  coverage  percentage. They  show that  network
   the  network lifetime  and the  coverage  percentage. They  show that  network

-  lifetime can be hugely improved by decreasing the coverage ratio.}
+  lifetime can be hugely improved by decreasing the coverage ratio.

 
 \subsection{Distributed approaches}
 
 
 \subsection{Distributed approaches}
 


@@ -267,27 +284,15 @@ synchronized and  predetermined time-slot where  the sensors are active  or not.
 Indeed, each sensor  maintains its own timer and its  wake-up time is randomized
 \cite{Ye03} or regulated \cite{cardei2005maximum} over time.
 
 Indeed, each sensor  maintains its own timer and its  wake-up time is randomized
 \cite{Ye03} or regulated \cite{cardei2005maximum} over time.
 

-The MuDiLCO protocol (for  Multiround Distributed Lifetime Coverage Optimization
-protocol) presented  in this paper  is an  extension of the  approach introduced
-in~\cite{idrees2014coverage}.   In~\cite{idrees2014coverage},  the  protocol  is
-deployed over  only two subregions.  Simulation results  have shown that  it was
-more  interesting  to  divide  the  area  into  several  subregions,  given  the
-computation complexity. Compared to our previous paper, in this one we study the
-possibility of dividing  the sensing phase into multiple rounds  and we also add
-an  improved  model of  energy  consumption  to  assess  the efficiency  of  our
-approach. In fact, in this paper we make a multiround optimization, while it was
-a single round  optimization in our previous work.  \textcolor{blue}{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
-  given time threshold}.
-
-

 \section{MuDiLCO protocol description}
 \label{pd}
 
 \section{MuDiLCO protocol description}
 \label{pd}
 

-\subsection{Assumptions}
+\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
 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


@@ -304,7 +309,11 @@ 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
 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.
+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.}

 
 \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
 
 \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


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

-\textcolor{blue}{The WSN  area of  interest is,  at  first,  divided into
+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
   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.}
+  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.   Each  sensing  phase may  be  itself
-divided into $T$ rounds \textcolor{blue} {of  equal duration} and for each round
+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
 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.
+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.}

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

-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.   \textcolor{blue}{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
-(including their residual energy) at the beginning of each period.  However, the
-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.
-
-We define two types of packets that will be used by the proposed protocol:
+\textcolor{green}{As already described in~\cite{idrees2015distributed}}, two types of packets are used by the proposed protocol:

 \begin{enumerate}[(a)] 
 \item INFO  packet: such a  packet  will be sent by  each sensor node  to all the
   nodes inside a subregion for information exchange.
 \begin{enumerate}[(a)] 
 \item INFO  packet: such a  packet  will be sent by  each sensor node  to all the
   nodes inside a subregion for information exchange.


@@ -411,43 +403,68 @@ There are five status for each sensor node in the network:
 \item COMMUNICATION: sensor node is transmitting or receiving packet.
 \end{enumerate}
 
 \item COMMUNICATION: sensor node is transmitting or receiving packet.
 \end{enumerate}
 

-Below, we describe each phase in more details.

 
 

-\subsection{Information Exchange Phase}

 
 

-Each sensor node $j$ sends its position, remaining energy $RE_j$, and the number
+
+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.
+
+The  energy consumption  and some  other constraints  can easily  be  taken into
+account,  since the  sensors  can  update and  then  exchange their  information
+(including their residual energy) at the beginning of each period.  However, the
+pre-sensing  phases (Information  Exchange, Leader  Election, and  Decision) are
+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
 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.  After  that, each node will have information about
-all  the sensor  nodes in  the subregion.   In our  model, the  remaining energy
-corresponds to the time that a sensor can live in the active mode.
-
-\subsection{Leader Election phase}
+packets sent by other nodes (line 4). 

 
 

-This step  consists in choosing  the Wireless  Sensor Node Leader  (WSNL), which
-will be responsible for executing the coverage algorithm.  Each subregion in the
-area of  interest will select its  own WSNL independently for  each period.  All
-the sensor  nodes cooperate to  elect a WSNL.  The  nodes in the  same subregion
-will select the leader based on the received information from all other nodes in
+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 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.
+the communications.\\
+
+

 
 

-\subsection{Decision phase}
-\label{decision}

 
 

-Each WSNL will  \textcolor{blue}{solve 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,  indicating if the sensor should be  active or not in
-  each round of the sensing phase.}
+%Each WSNL will solve 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,  indicating if the sensor should be  active or not in
+%  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.

 
 

-As shown in Algorithm~\ref{alg:MuDiLCO}, the leader will execute an optimization
-algorithm based on an integer program. The integer program is based on the model
+
+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
 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


@@ -457,7 +474,8 @@ 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
 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.
+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$.}

 
 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:


@@ -556,14 +574,15 @@ 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}$.
 

-\textcolor{blue}{The size of the problem depends  on the number of variables and
+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. 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})).}
+  constraints (\ref{eq144})).

 
 

+\iffalse

 \subsection{Sensing phase}
 
 The sensing phase consists of $T$ rounds. Each sensor node in the subregion will
 \subsection{Sensing phase}
 
 The sensing phase consists of $T$ rounds. Each sensor node in the subregion will


@@ -571,6 +590,7 @@ 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.
 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  
 
 \begin{algorithm}[h!]                
   \BlankLine  


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

-\textcolor{blue}{Our  protocol  is  declined   into  four  versions:  MuDiLCO-1,
+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
   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


@@ -653,7 +673,7 @@ $W_{U}$ & $|P|^2$ \\
   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
   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.}
+  future.

 
  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
 
  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


@@ -669,8 +689,13 @@ 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
 the benefit from the optimization and the  execution time needed to solve it. In
 network  disconnection due  to node  failures.  However,  too many  subdivisions
 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 following we have set the number of subregions to 16.
+the following we have set the number of subregions to 16 \textcolor{green}{as recommended in~\cite{idrees2015distributed}}.

 
 

+\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
 \subsection{Energy model}
 
 We  use an  energy consumption  model  proposed by~\cite{ChinhVu}  and based  on


@@ -727,10 +752,12 @@ 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.
 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

 
 \subsection{Metrics}
 
 
 \subsection{Metrics}
 

-To evaluate our approach we consider the following performance 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$.} 

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


@@ -793,7 +820,11 @@ indicate the energy consumed by the whole network in round $t$.
 
 %\item {Network Lifetime:} we  have defined the network  lifetime as the  time until all
 %nodes  have  been drained  of  their  energy  or each  sensor  network monitoring  an area has become  disconnected.
 
 %\item {Network Lifetime:} we  have defined the network  lifetime as the  time until all
 %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
 \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


@@ -805,6 +836,7 @@ indicate the energy consumed by the whole network in round $t$.
   to network disconnections and for which round it occurs.
 
 \end{enumerate}
   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}


@@ -812,12 +844,12 @@ 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  for different
+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
 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.
+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)}.

 
 \subsubsection{Coverage ratio} 
 
 
 \subsubsection{Coverage ratio} 
 


@@ -876,9 +908,9 @@ 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.  \textcolor{blue}{MuDiLCO-7 seems  to have
+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
   most of the  time the best coverage  ratio up to round~80,  after that MuDiLCO-5 is

-  slightly better.}
+  slightly better.

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


@@ -907,7 +939,10 @@ efficient manner.
 \end{figure} 
 
 \subsection{Stopped simulation runs}
 \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
 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


@@ -948,12 +983,12 @@ 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.
 

-\textcolor{blue}{Energy consumption increases with the  size of the networks and
+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
   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.}
+  order whatever the MuDiLCO version. As can be seen with MuDiLCO-7.

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


@@ -980,9 +1015,9 @@ for different network sizes.
 \end{figure} 
 
 As expected,  the execution time increases  with the number of  rounds $T$ taken
 \end{figure} 
 
 As expected,  the execution time increases  with the number of  rounds $T$ taken

-into  account to  schedule  the sensing  phase. \textcolor{blue}{Obviously,  the
+into  account to  schedule  the sensing  phase. Obviously,  the

   number of variables and constraints of the integer program increases with $T$,
   number of variables and constraints of the integer program increases with $T$,

-  as  explained  in section~\ref{decision}, the times obtained  for $T=1,3$ or
+  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
   $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


@@ -992,7 +1027,7 @@ into  account to  schedule  the sensing  phase. \textcolor{blue}{Obviously,  the
   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
   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.}
+  any impact on the coverage quality.

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


@@ -1011,14 +1046,14 @@ 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.

-\textcolor{blue}{Overall,  it  clearly appears  that  computing a  scheduling for
+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
   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.}
+  method compared to MuDiLCO-7.

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


@@ -1053,11 +1088,11 @@ 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.  \textcolor{blue}{  Furthermore,
+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
   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.}
+  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.
 
 %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.

diff --git a/biblio.bib b/biblio.bib
index bed9b2fbac504def810b702c8ef94223c68cb011..d5643ba2ab7fd272eb2c3d574e9b35bb5778b2be 100755 (executable)
--- a/biblio.bib
+++ b/biblio.bib
@@ -469,6 +469,18 @@ ISSN={1536-1276},
   year={2014}
 }
 
   year={2014}
 }
 

+@article{idrees2015distributed,
+  title={Distributed lifetime coverage optimization protocol in wireless sensor networks},
+  author={Idrees, Ali Kadhum and Deschinkel, Karine and Salomon, Michel and Couturier, Rapha{\"e}l},
+  journal={The Journal of Supercomputing},
+  volume={71},
+  number={12},
+  pages={4578--4593},
+  year={2015},
+  publisher={Springer US}
+}
+
+

 @inproceedings{xu2001geography,
   title={Geography-informed energy conservation for ad hoc routing},
   author={Xu, Ya and Heidemann, John and Estrin, Deborah},
 @inproceedings{xu2001geography,
   title={Geography-informed energy conservation for ad hoc routing},
   author={Xu, Ya and Heidemann, John and Estrin, Deborah},

diff --git a/reponse2.pdf b/reponse2.pdf
index 1adc53501057add1ee91f285aec212c67814404e..e87ad0aba56fe7f95efe2fa0dfdee22656d32fd8 100644 (file)
Binary files a/reponse2.pdf and b/reponse2.pdf differ