new

[JournalMultiPeriods.git] / article.tex

diff --git a/article.tex b/article.tex
index 42d7890881781853ecf86df1d22cedb4ef44f272..1299026a35cc4c79a21957704e4d24582da37bb9 100644 (file)
--- a/article.tex
+++ b/article.tex
@@ -437,6 +437,7 @@ one-hop neighbors as  the primary criterion to reduce energy  consumption due to
 the communications.
 
 \subsection{Decision phase}
 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
 
 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


@@ -947,26 +948,28 @@ 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.
 

-% TO BE CONTINUED

 \textcolor{blue}{Energy consumption increases with the  size of the networks and
 \textcolor{blue}{Energy consumption increases with the  size of the networks and

-  the  number  of  rounds.  The  curve  Unlimited-MuDiLCO-7  shows  that  energy
+  the  number  of  rounds.   The curve  Unlimited-MuDiLCO-7  shows  that  energy

   consumption due to  the time spent to solve the  integer program to optimality
   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
   consumption due to  the time spent to solve the  integer program to optimality
   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.}
-
+  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
+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
 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}
+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.
 
 \begin{figure}[ht!]
 for different network sizes.
 
 \begin{figure}[ht!]


@@ -977,87 +980,84 @@ 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. The times obtained for $T=1,3$
-or $5$ seem bearable, but for $T=7$ they become quickly unsuitable for a sensor
-node, especially when  the sensor network size increases.   Again, we can notice
-that if we want  to schedule the nodes activities for a  large number of rounds,
-we need to choose a relevant number of subregions in order to avoid a complicated
-and cumbersome optimization.  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.
-
-%While MuDiLCO-1, 3, and 5 solves the optimization process with suitable execution times to be used on wireless sensor network because it distributed on larger number of small subregions as well as it is used acceptable number of round(s) T.  We think that in distributed fashion the solving of the optimization problem to produce T rounds in a subregion can be tackled by sensor nodes. Overall, to be able to deal with very large networks, a distributed method is clearly required.
+into  account to  schedule  the sensing  phase. \textcolor{blue}{Obviously,  the
+  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
+  $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  would have  been 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}
 
 The next  two figures,  Figures~\ref{fig8}(a) and \ref{fig8}(b),  illustrate the
 network lifetime  for different network sizes,  respectively for $Lifetime_{95}$
 
 \subsection{Network lifetime}
 
 The next  two figures,  Figures~\ref{fig8}(a) and \ref{fig8}(b),  illustrate the
 network lifetime  for different network sizes,  respectively for $Lifetime_{95}$

-and  $Lifetime_{50}$.  Both  figures show  that the  network  lifetime increases
+and  $Lifetime_{50}$.  Both  figures show  that the  network lifetime  increases

 together with the  number of sensor nodes, whatever the  protocol, thanks to the
 together with the  number of sensor nodes, whatever the  protocol, thanks to the

-node  density  which  results in  more  and  more  redundant  nodes that  can  be
+node  density  which results  in  more  and more  redundant  nodes  that can  be

 deactivated and thus save energy.  Compared to the other approaches, our MuDiLCO
 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 be 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
-linked. 
-%\textcolor{red}{As can be seen in these figures, the lifetime increases with the size of the network, and it is clearly largest for the MuDiLCO
-%and the GA-MuDiLCO protocols. GA-MuDiLCO prolongs the network lifetime obviously in comparison with both DESK and GAF, as well as the MuDiLCO-7 version for $lifetime_{95}$.  However, comparison shows that MuDiLCO protocol and GA-MuDiLCO protocol, which use distributed optimization over the subregions are the best ones because they are robust to network disconnection during the network lifetime as well as they consume less energy in comparison with other approaches.}
+protocol  maximizes the  lifetime of  the network.   In particular  the gain  in
+lifetime for a coverage  over 95\%, and a network of  250~nodes, is greater than
+38\% when switching from GAF to MuDiLCO-5.
+%The lower performance that can be 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
+%linked.
+\textcolor{blue}{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 most  suited
+  method in comparison with MuDiLCO-7.}
+

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

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

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

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

   \end{tabular}
   \caption{Network lifetime for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}
   \label{fig8}
 \end{figure} 
 
   \end{tabular}
   \caption{Network lifetime for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}
   \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 protocol efficiently prolonges the network lifetime. 
-
-%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.
-
-

 \section{Conclusion and future works}
 \label{sec:conclusion}
 
 \section{Conclusion and future works}
 \label{sec:conclusion}
 

-We have addressed  the problem of the coverage and of the lifetime optimization in
-wireless  sensor networks.  This is  a key  issue as  sensor nodes  have limited
+We have addressed  the problem of the coverage and  of the lifetime optimization
+in wireless sensor networks.   This is a key issue as  sensor nodes have limited

 resources in terms of memory, energy, and computational power. To cope with this
 resources in terms of memory, energy, and computational power. To cope with this

-problem,  the field  of sensing  is divided  into smaller  subregions  using the
+problem,  the field  of sensing  is divided  into smaller  subregions using  the

 concept  of divide-and-conquer  method, and  then  we propose  a protocol  which
 concept  of divide-and-conquer  method, and  then  we propose  a protocol  which

-optimizes coverage  and lifetime performances in each  subregion.  Our protocol,
-called MuDiLCO (Multiround  Distributed Lifetime Coverage Optimization) combines
+optimizes coverage and  lifetime performances in each  subregion.  Our protocol,
+called MuDiLCO (Multiround Distributed  Lifetime Coverage Optimization) combines

 two  efficient   techniques:  network   leader  election  and   sensor  activity
 two  efficient   techniques:  network   leader  election  and   sensor  activity

-scheduling.
-%,  where the challenges
-%include how to select the  most efficient leader in each subregion and
-%the best cover sets %of active nodes that will optimize the network lifetime
-%while taking the responsibility of covering the corresponding
-%subregion using more than one cover set during the sensing phase. 
-The activity  scheduling in each subregion  works in periods,  where each period
-consists of four  phases: (i) Information Exchange, (ii)  Leader Election, (iii)
-Decision Phase to plan the activity  of the sensors over $T$ rounds, (iv) Sensing
-Phase itself divided into $T$ rounds.
-
-Simulations  results show the  relevance of  the proposed  protocol in  terms of
+scheduling. The  activity scheduling in  each subregion works in  periods, where
+each  period consists  of four  phases:  (i) Information  Exchange, (ii)  Leader
+Election, (iii)  Decision Phase  to plan  the activity of  the sensors  over $T$
+rounds, (iv) Sensing Phase itself divided into $T$ rounds.
+
+Simulations results  show the  relevance of  the proposed  protocol in  terms of

 lifetime, coverage  ratio, active  sensors ratio, energy  consumption, execution
 time. Indeed,  when dealing with  large wireless sensor networks,  a distributed
 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
+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
 global optimization problem by partitioning it in many smaller problems, one per

-subregion, that can be solved  more easily. Nevertheless, results also show that
-it is not possible to plan the activity of sensors over too many rounds, because
-the resulting optimization problem leads to too high resolution times and thus to
-an excessive energy consumption.
+subregion,  that  can be  solved  more  easily.  \textcolor{blue}{  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.
 
 %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.