Last updates

[JournalMultiPeriods.git] / article.tex

diff --git a/article.tex b/article.tex
index 42d7890881781853ecf86df1d22cedb4ef44f272..5e7bea7711b8cebaf28c726e523bb6823f5fbc77 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


@@ -643,16 +644,16 @@ $W_{U}$ & $|P|^2$ \\
   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
   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
+  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,
   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 consists
-  in considering  the average execution  time to  solve the integer  programs to
-  optimality, then in  dividing this average time by three  to set the threshold
-  value.  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.}
+  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
  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


@@ -662,13 +663,13 @@ $W_{U}$ & $|P|^2$ \\
  phase time.
 
 Some preliminary experiments were performed to study the choice of the number of
  phase time.
 
 Some preliminary experiments were performed to study the choice of the number of

-subregions  which subdivides  the  sensing field,  considering different  network
+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
 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
-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.
+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.

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


@@ -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, 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}
 
 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
+43\% 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.