New modifications (EC formula + Raphael remarks)

diff --git a/article.tex b/article.tex
index c729d584084041ea2d6465a88bd8dd2434e9996b..a3fb2092f1426f674c1981f2d9b5e82f8f969212 100644 (file)
--- a/article.tex
+++ b/article.tex
@@ -173,7 +173,7 @@ algorithms in WSNs according to several design choices:
 \item  Sensors   scheduling  algorithm  implementation,   i.e.   centralized  or
   distributed/localized algorithms.
 \item The objective of sensor coverage, i.e. to maximize the network lifetime or
 \item  Sensors   scheduling  algorithm  implementation,   i.e.   centralized  or
   distributed/localized algorithms.
 \item The objective of sensor coverage, i.e. to maximize the network lifetime or

-  to minimize the number of sensors during the sensing period.
+  to minimize the number of sensors during a sensing round.

 \item The homogeneous or heterogeneous nature  of the nodes, in terms of sensing
   or communication capabilities.
 \item The node deployment method, which may be random or deterministic.
 \item The homogeneous or heterogeneous nature  of the nodes, in terms of sensing
   or communication capabilities.
 \item The node deployment method, which may be random or deterministic.


@@ -272,9 +272,9 @@ 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
 responsibility of sensing and communication.
 
 Some  other  approaches (outside  the  scope  of our  work)  do  not consider  a

-synchronized and  predetermined period of time  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.
+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.

 
 The MuDiLCO protocol (for  Multiround Distributed Lifetime Coverage Optimization
 protocol) presented  in this  paper is an  extension of the  approach introduced
 
 The MuDiLCO protocol (for  Multiround Distributed Lifetime Coverage Optimization
 protocol) presented  in this  paper is an  extension of the  approach introduced


@@ -407,7 +407,7 @@ 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
 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 proposed  a  novel  distributed
+information.  In  \cite{ChinhVu}, the author  have proposed 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 maintained.  This heuristic
 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 maintained.  This heuristic


@@ -560,8 +560,9 @@ produce $T$ cover sets that will take the mission of sensing for $T$ rounds.
 % set cover responsible for the sensing task.  
 %For each round a set of sensors (said a cover set) is responsible for the sensing task.
 
 % set cover responsible for the sensing task.  
 %For each round a set of sensors (said a cover set) is responsible for the sensing task.
 

-This protocol is reliable against an unexpected node failure, because it works
-in periods. 
+This protocol minimizes the impact of unexpected node failure (not due to batteries
+running out of energy), because it works in periods. 
+%This protocol is reliable against an unexpected node failure, because it works in periods. 

 %%RC : why? I am not convinced
  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,
 %%RC : why? I am not convinced
  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,


@@ -569,6 +570,8 @@ 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.
 %%RC so if there are at least one failure per period, the coverage is bad...
 will be temporarily affected:  only during  the period of sensing until a new
 period starts.
 %%RC so if there are at least one failure per period, the coverage is bad...

+%%MS if we want to be reliable against many node failures we need to have an
+%% overcoverage...  

 
 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


@@ -730,7 +733,6 @@ U_{t,p} \in \lbrace0,1\rbrace, \hspace{10 mm}\forall p \in P, t = 1,\dots,T  \la
 
 %%RC why W_{\theta} is not defined (only one sentence)? How to define in practice Wtheta and Wu?
 
 
 %%RC why W_{\theta} is not defined (only one sentence)? How to define in practice Wtheta and Wu?
 

-

 \begin{itemize}
 \item $X_{t,j}$:  indicates whether  or not the  sensor $j$ is  actively sensing
   during the round $t$ (1 if yes and 0 if not);
 \begin{itemize}
 \item $X_{t,j}$:  indicates whether  or not the  sensor $j$ is  actively sensing
   during the round $t$ (1 if yes and 0 if not);


@@ -753,8 +755,9 @@ 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. In
-our simulations priority is given  to the coverage by choosing $W_{\theta}$ very
+to guarantee that the maximum number of points are covered during each round. 
+%% MS W_theta is smaller than W_u => problem with the following sentence
+In our simulations priority is given  to the coverage by choosing $W_{\theta}$ very

 large compared to $W_U$.
 %The Active-Sleep packet includes the schedule vector with the number of rounds that should be applied by the receiving sensor node during the sensing phase.
 
 large compared to $W_U$.
 %The Active-Sleep packet includes the schedule vector with the number of rounds that should be applied by the receiving sensor node during the sensing phase.
 


@@ -868,22 +871,21 @@ $W_{U}$ & $|P|^2$
   
 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
   
 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).   In the  following, the  general case  will be
-denoted by  MuDiLCO-T and we will  make comparisons with two  other methods. The
-first method, called DESK and  proposed by \cite{ChinhVu}, is a full 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
-phase time.
+rounds in one sensing period).  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  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 phase time.

 
 Some preliminary experiments were performed to study the choice of the number of
 subregions  which subdivide  the  sensing field,  considering different  network
 sizes. They show that as the number of subregions increases, so does the network
 
 Some preliminary experiments were performed to study the choice of the number of
 subregions  which subdivide  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-T protocol more  robust against random
-network  disconnection due  to  node failures.  However,  too much  subdivisions
+lifetime. Moreover,  it makes  the MuDiLCO protocol  more robust  against random
+network  disconnection due  to node  failures.  However,  too  much subdivisions

 reduces the advantage  of the optimization. In fact, there  is a balance between
 the  benefit  from the  optimization  and the  execution  time  needed to  solve
 reduces 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. Therefore, we  have set the number  of subregions to 16 rather  than 32. 
+it. Therefore, we have set the number of subregions to 16 rather than 32.

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


@@ -1005,28 +1007,40 @@ network, and $R$ is the total number of the subregions in the network.
   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
   follows:
   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
   follows:

- \begin{equation*}
-\scriptsize
-\mbox{EC} = \frac{\sum\limits_{m=1}^{M_L} \left( E^{\mbox{com}}_m+E^{\mbox{list}}_m+E^{\mbox{comp}}_m \right) +
-  \sum\limits_{t=1}^{T_L} \left( E^{a}_t+E^{s}_t \right)}{T_L},
-\end{equation*}

 
 

+  % New version with global loops on period
+  \begin{equation*}
+    \scriptsize
+    \mbox{EC} = \frac{\sum\limits_{m=1}^{M_L} \left[ \left( E^{\mbox{com}}_m+E^{\mbox{list}}_m+E^{\mbox{comp}}_m \right) +\sum\limits_{t=1}^{T_m} \left( E^{a}_t+E^{s}_t \right) \right]}{\sum\limits_{m=1}^{M_L} T_m},
+  \end{equation*}
+
+
+% Old version with loop on round outside the loop on period
+%  \begin{equation*}
+%    \scriptsize
+%    \mbox{EC} = \frac{\sum\limits_{m=1}^{M_L} \left( E^{\mbox{com}}_m+E^{\mbox{list}}_m+E^{\mbox{comp}}_m \right) +\sum\limits_{t=1}^{T_L} \left( E^{a}_t+E^{s}_t \right)}{T_L},
+%  \end{equation*}
+
+% Ali version 

 %\begin{equation*}
 %\scriptsize
 %\mbox{EC} =  \frac{\mbox{$\sum\limits_{d=1}^D E^c_d$}}{\mbox{$D$}} + \frac{\mbox{$\sum\limits_{d=1}^D %E^l_d$}}{\mbox{$D$}} + \frac{\mbox{$\sum\limits_{d=1}^D E^a_d$}}{\mbox{$D$}} + %\frac{\mbox{$\sum\limits_{d=1}^D E^s_d$}}{\mbox{$D$}}.
 %\end{equation*}
 
 %\begin{equation*}
 %\scriptsize
 %\mbox{EC} =  \frac{\mbox{$\sum\limits_{d=1}^D E^c_d$}}{\mbox{$D$}} + \frac{\mbox{$\sum\limits_{d=1}^D %E^l_d$}}{\mbox{$D$}} + \frac{\mbox{$\sum\limits_{d=1}^D E^a_d$}}{\mbox{$D$}} + %\frac{\mbox{$\sum\limits_{d=1}^D E^s_d$}}{\mbox{$D$}}.
 %\end{equation*}
 

-where $M_L$ and  $T_L$ are respectively the number of  periods and rounds during
-$Lifetime_{95}$ or  $Lifetime_{50}$.  The total  energy consumed by  the sensors
-(EC) comes through taking into consideration four main energy factors. The first
-one ,  denoted $E^{\scriptsize \mbox{com}}_m$, represent  the energy consumption
-spent  by  all  the  nodes   for  wireless  communications  during  period  $m$.
-$E^{\scriptsize  \mbox{list}}_m$, the  next  factor, corresponds  to the  energy
-consumed by the sensors in LISTENING  status before receiving the decision to go
-active or  sleep in  period $m$. $E^{\scriptsize  \mbox{comp}}_m$ refers  to the
-energy needed  by all  the leader nodes  to solve  the integer program  during a
-period. Finally, $E^a_t$ and $E^s_t$  indicate the energy consummed by the whole
-network in round $t$.
+% Old version -> where $M_L$ and  $T_L$ are respectively the number of  periods and rounds during
+%$Lifetime_{95}$ or  $Lifetime_{50}$. 
+% New version
+where  $M_L$ is  the number  of periods  and  $T_m$ the  number of  rounds in  a
+period~$m$, both  during $Lifetime_{95}$  or $Lifetime_{50}$.  The  total energy
+consumed by the  sensors (EC) comes through taking  into consideration four main
+energy  factors.   The  first  one  ,  denoted  $E^{\scriptsize  \mbox{com}}_m$,
+represent  the  energy   consumption  spent  by  all  the   nodes  for  wireless
+communications  during period  $m$.  $E^{\scriptsize  \mbox{list}}_m$,  the next
+factor, corresponds  to the energy consumed  by the sensors  in LISTENING status
+before  receiving   the  decision  to  go   active  or  sleep   in  period  $m$.
+$E^{\scriptsize \mbox{comp}}_m$  refers to the  energy needed by all  the leader
+nodes to solve the integer program during a period. Finally, $E^a_t$ and $E^s_t$
+indicate the energy consummed 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.


@@ -1049,22 +1063,20 @@ network in round $t$.
 
 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
 
 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

-which is a little bit better than the one of MuDiLCO-T.  
-%%RC : need to uniformize MuDiLCO or MuDiLCO-T?
-
+which is a little bit better than the one of MuDiLCO.  
+%%RC : need to uniformize MuDiLCO or MuDiLCO-T? 
+%%MS : MuDiLCO everywhere

 %%RC maybe increase the size of the figure for the reviewers, no?
 %%RC maybe increase the size of the figure for the reviewers, no?

-
-This is due to the fact
-that in comparison with MuDiLCO-T that  uses optimization to put in SLEEP status
-redundant sensors,  more sensor  nodes remain  active with DESK  and GAF.   As a
-consequence,  when the  number  of rounds  increases,  a larger  number of  node
-failures can be observed in DESK and  GAF, resulting in a faster decrease of the
-coverage ratio.  Furthermore,  our protocol allows to maintain  a coverage ratio
-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-T
-saves more  energy, with less dead nodes,  at most for several  rounds, and thus
-should extend the network lifetime.
+This is due  to the fact that in comparison with  MuDiLCO that uses optimization
+to put in  SLEEP status redundant sensors, more sensor  nodes remain active with
+DESK and GAF.   As a consequence, when the number of  rounds increases, a larger
+number of node failures  can be observed in DESK and GAF,  resulting in a faster
+decrease of the coverage ratio.   Furthermore, our protocol allows to maintain a
+coverage ratio  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 should extend the network lifetime.

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


@@ -1080,11 +1092,11 @@ minimize    the    communication    overhead    and   maximize    the    network
 lifetime. Figure~\ref{fig4}  presents the active  sensor ratio for  150 deployed
 nodes all along the network lifetime. It appears that up to round thirteen, DESK
 and GAF have  respectively 37.6\% and 44.8\% of nodes  in ACTIVE status, whereas
 lifetime. Figure~\ref{fig4}  presents the active  sensor ratio for  150 deployed
 nodes all along the network lifetime. It appears that up to round thirteen, DESK
 and GAF have  respectively 37.6\% and 44.8\% of nodes  in ACTIVE status, whereas

-MuDiLCO-T clearly outperforms  them with only 24.8\% of  active nodes. After the
-thirty  fifth round,  MuDiLCO-T exhibits  larger number  of active  nodes, which
-agrees with  the dual observation of  higher level of  coverage made previously.
+MuDiLCO clearly  outperforms them  with only 24.8\%  of active nodes.  After the
+thirty fifth round, MuDiLCO exhibits larger number of active nodes, which agrees
+with  the  dual  observation  of  higher  level  of  coverage  made  previously.

 Obviously, in  that case DESK  and GAF have  less active nodes, since  they have
 Obviously, in  that case DESK  and GAF have  less active nodes, since  they have

-activated many nodes at the beginning. Anyway, MuDiLCO-T activates the available
+activated many nodes  at the beginning. Anyway, MuDiLCO  activates the available

 nodes in a more efficient manner.
 
 \begin{figure}[ht!]
 nodes in a more efficient manner.
 
 \begin{figure}[ht!]


@@ -1102,7 +1114,7 @@ Figure~\ref{fig6} reports the cumulative  percentage of stopped simulations runs
 per round for  150 deployed nodes. This figure gives the  breakpoint for each of
 the methods.  DESK stops first,  after around 45~rounds, because it consumes the
 more energy by  turning on a large number of redundant  nodes during the sensing
 per round for  150 deployed nodes. This figure gives the  breakpoint for each of
 the methods.  DESK stops first,  after around 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.  MuDiLCO-T overcomes
+phase. GAF  stops secondly for the  same reason than  DESK.  MuDiLCO overcomes

 DESK and GAF because the  optimization process distributed on several subregions
 leads  to coverage  preservation and  so extends  the network  lifetime.  Let us
 emphasize that the  simulation continues as long as a network  in a subregion is
 DESK and GAF because the  optimization process distributed on several subregions
 leads  to coverage  preservation and  so extends  the network  lifetime.  Let us
 emphasize that the  simulation continues as long as a network  in a subregion is


@@ -1137,7 +1149,7 @@ network sizes, for $Lifetime_{95}$ and $Lifetime_{50}$.
   \label{fig7}
 \end{figure} 
 
   \label{fig7}
 \end{figure} 
 

-The  results  show  that MuDiLCO-T  is  the  most  competitive from  the  energy
+The  results  show  that  MuDiLCO  is  the  most  competitive  from  the  energy

 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. Among  the different
 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. Among  the different


@@ -1191,11 +1203,11 @@ network lifetime  for different network sizes,  respectively for $Lifetime_{95}$
 and  $Lifetime_{50}$.  Both  figures show  that the  network  lifetime increases
 together with the  number of sensor nodes, whatever the  protocol, thanks to the
 node  density  which  result in  more  and  more  redundant  nodes that  can  be
 and  $Lifetime_{50}$.  Both  figures show  that the  network  lifetime increases
 together with the  number of sensor nodes, whatever the  protocol, thanks to the
 node  density  which  result in  more  and  more  redundant  nodes that  can  be

-deactivated  and  thus save  energy.   Compared  to  the other  approaches,  our
-MuDiLCO-T protocol  maximizes the  lifetime of the  network.  In  particular the
-gain in  lifetime for a coverage over  95\% is greater than  38\% when switching
-from GAF to MuDiLCO-3.  The slight  decrease that can bee observed for MuDiLCO-7
-in case of $Lifetime_{95}$ with  large wireless sensor networks results from the
+deactivated and thus save energy.  Compared to the other approaches, our MuDiLCO
+protocol  maximizes the  lifetime of  the network.   In particular  the  gain in
+lifetime for a  coverage over 95\% is greater than 38\%  when switching from GAF
+to MuDiLCO-3.  The  slight decrease that can bee observed  for MuDiLCO-7 in case
+of  $Lifetime_{95}$  with  large  wireless  sensor  networks  results  from  the

 difficulty  of the optimization  problem to  be solved  by the  integer program.
 This  point was  already noticed  in subsection  \ref{subsec:EC} devoted  to the
 energy consumption,  since network lifetime and energy  consumption are directly
 difficulty  of the optimization  problem to  be solved  by the  integer program.
 This  point was  already noticed  in subsection  \ref{subsec:EC} devoted  to the
 energy consumption,  since network lifetime and energy  consumption are directly


@@ -1213,9 +1225,9 @@ linked.
   \label{fig8}
 \end{figure} 
 
   \label{fig8}
 \end{figure} 
 

-% By choosing the best suited nodes, for each round, by optimizing the coverage and lifetime of the network to cover the area of interest with a maximum number rounds and by letting the other nodes sleep in order to be used later in next rounds, our MuDiLCO-T protocol efficiently prolonges the network lifetime. 
+% By choosing the best suited nodes, for each round, by optimizing the coverage and lifetime of the network to cover the area of interest with a maximum number rounds and by letting the other nodes sleep in order to be used later in next rounds, our MuDiLCO protocol efficiently prolonges the network lifetime. 

 
 

-%In Figure~\ref{fig8}, Comparison shows that our MuDiLCO-T protocol, which are used distributed optimization on the subregions with the ability of producing T rounds, is the best one because it is robust to network disconnection during the network lifetime as well as it consume less energy in comparison with other approaches. It also means that distributing the protocol in each sensor node and subdividing the sensing field into many subregions, which are managed independently and simultaneously, is the most relevant way to maximize the lifetime of a network.
+%In Figure~\ref{fig8}, Comparison shows that our MuDiLCO protocol, which are used distributed optimization on the subregions with the ability of producing T rounds, is the best one because it is robust to network disconnection during the network lifetime as well as it consume less energy in comparison with other approaches. It also means that distributing the protocol in each sensor node and subdividing the sensing field into many subregions, which are managed independently and simultaneously, is the most relevant way to maximize the lifetime of a network.

 
 
 %We see that our MuDiLCO-7 protocol results in execution times that quickly become unsuitable for a sensor network as well as the energy consumption seems to be huge because it used a larger number of rounds T during performing the optimization decision in the subregions, which is led to decrease the network lifetime. On the other side, our MuDiLCO-1, 3, and 5 protocol seems to be more efficient in comparison with other approaches because they are prolonged the lifetime of the network more than DESK and GAF.
 
 
 %We see that our MuDiLCO-7 protocol results in execution times that quickly become unsuitable for a sensor network as well as the energy consumption seems to be huge because it used a larger number of rounds T during performing the optimization decision in the subregions, which is led to decrease the network lifetime. On the other side, our MuDiLCO-1, 3, and 5 protocol seems to be more efficient in comparison with other approaches because they are prolonged the lifetime of the network more than DESK and GAF.