Update by Ali

[JournalMultiPeriods.git] / article.tex

diff --git a/article.tex b/article.tex
index fb4739a85b2288007a6b1b685f058efae9e1b1a3..23109b40dfa84efd57aff0d377af8921273b78fe 100644 (file)
--- a/article.tex
+++ b/article.tex
@@ -647,12 +647,71 @@ consumption due to the communications.
 
 \subsection{Decision phase}
 
 
 \subsection{Decision phase}
 

-Each  WSNL will solve  an integer  program to  select which  cover sets  will be
+Each  WSNL will \textcolor{red}{ execute an optimization algorithm (see section \ref{oa})} to  select which  cover sets  will be

 activated in  the following  sensing phase  to cover the  subregion to  which it
 activated in  the following  sensing phase  to cover the  subregion to  which it

-belongs.  The integer  program will produce $T$ cover sets,  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.  The  integer program  is based on  the model
+belongs.  The \textcolor{red}{optimization algorithm} will produce $T$ cover sets,  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.  
+
+%solve  an integer  program
+
+\subsection{Sensing phase}
+
+The sensing phase consists of $T$ rounds. Each sensor node in the subregion will
+receive an Active-Sleep packet from WSNL, informing it to stay awake or to go to
+sleep for each round of the sensing  phase.  Algorithm~\ref{alg:MuDiLCO}, which
+will be  executed by each node  at the beginning  of a period, explains  how the
+Active-Sleep packet is obtained.
+
+% In each round during the sensing phase, there is a cover set of sensor nodes,  in which  the active  sensors will  execute  their sensing  task  to preserve maximal  coverage and lifetime in the subregion and this will continue until finishing the round $T$ and starting new period. 
+
+\begin{algorithm}[h!]                
+ % \KwIn{all the parameters related to information exchange}
+%  \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)}
+  \BlankLine
+  %\emph{Initialize the sensor node and determine it's position and subregion} \; 
+  
+  \If{ $RE_j \geq E_{R}$ }{
+      \emph{$s_j.status$ = COMMUNICATION}\;
+      \emph{Send $INFO()$ packet to other nodes in the subregion}\;
+      \emph{Wait $INFO()$ packet from other nodes in the subregion}\; 
+      %\emph{UPDATE $RE_j$ for every sent or received INFO Packet}\;
+      %\emph{ Collect information and construct the list L for all nodes in the subregion}\;
+      
+      %\If{ the received INFO Packet = No. of nodes in it's subregion -1  }{
+      \emph{LeaderID = Leader election}\;
+      \If{$ s_j.ID = LeaderID $}{
+        \emph{$s_j.status$ = COMPUTATION}\;
+        \emph{$\left\{\left(X_{1,k},\dots,X_{T,k}\right)\right\}_{k \in J}$ =
+          Execute \textcolor{red}{Optimization Algorithm}($T,J$)}\;
+        \emph{$s_j.status$ = COMMUNICATION}\;
+        \emph{Send $ActiveSleep()$ to each node $k$ in subregion a packet \\
+          with vector of activity scheduling $(X_{1,k},\dots,X_{T,k})$}\;
+        \emph{Update $RE_j $}\;
+      }          
+      \Else{
+        \emph{$s_j.status$ = LISTENING}\;
+        \emph{Wait $ActiveSleep()$ packet from the Leader}\;
+        % \emph{After receiving Packet, Retrieve the schedule and the $T$ rounds}\;
+        \emph{Update $RE_j $}\;
+      }  
+      %  }
+  }
+  \Else { Exclude $s_j$ from entering in the current sensing phase}
+  
+ %   \emph{return X} \;
+\caption{MuDiLCO($s_j$)}
+\label{alg:MuDiLCO}
+
+\end{algorithm}
+
+
+
+
+
+
+\section{\textcolor{red}{ Optimization Algorithm for Multiround Lifetime Coverage Optimization}}
+\label{oa}
+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

 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


@@ -771,64 +830,21 @@ In our simulations priority is given  to the coverage by choosing $W_{U}$ very
 large compared to $W_{\theta}$.
 %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_{\theta}$.
 %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.
 

-\subsection{Sensing phase}
+This integer program can be solved using two approaches:

 
 

-The sensing phase consists of $T$ rounds. Each sensor node in the subregion will
-receive an Active-Sleep packet from WSNL, informing it to stay awake or to go to
-sleep for  each round of the sensing  phase.  Algorithm~\ref{alg:MuDiLCO}, which
-will be  executed by each node  at the beginning  of a period, explains  how the
-Active-Sleep packet is obtained.
-
-% In each round during the sensing phase, there is a cover set of sensor nodes,  in which  the active  sensors will  execute  their sensing  task  to preserve maximal  coverage and lifetime in the subregion and this will continue until finishing the round $T$ and starting new period. 
-
-\begin{algorithm}[h!]                
- % \KwIn{all the parameters related to information exchange}
-%  \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)}
-  \BlankLine
-  %\emph{Initialize the sensor node and determine it's position and subregion} \; 
-  
-  \If{ $RE_j \geq E_{R}$ }{
-      \emph{$s_j.status$ = COMMUNICATION}\;
-      \emph{Send $INFO()$ packet to other nodes in the subregion}\;
-      \emph{Wait $INFO()$ packet from other nodes in the subregion}\; 
-      %\emph{UPDATE $RE_j$ for every sent or received INFO Packet}\;
-      %\emph{ Collect information and construct the list L for all nodes in the subregion}\;
-      
-      %\If{ the received INFO Packet = No. of nodes in it's subregion -1  }{
-      \emph{LeaderID = Leader election}\;
-      \If{$ s_j.ID = LeaderID $}{
-        \emph{$s_j.status$ = COMPUTATION}\;
-        \emph{$\left\{\left(X_{1,k},\dots,X_{T,k}\right)\right\}_{k \in J}$ =
-          Execute Integer Program Algorithm($T,J$)}\;
-        \emph{$s_j.status$ = COMMUNICATION}\;
-        \emph{Send $ActiveSleep()$ to each node $k$ in subregion a packet \\
-          with vector of activity scheduling $(X_{1,k},\dots,X_{T,k})$}\;
-        \emph{Update $RE_j $}\;
-      }          
-      \Else{
-        \emph{$s_j.status$ = LISTENING}\;
-        \emph{Wait $ActiveSleep()$ packet from the Leader}\;
-        % \emph{After receiving Packet, Retrieve the schedule and the $T$ rounds}\;
-        \emph{Update $RE_j $}\;
-      }  
-      %  }
-  }
-  \Else { Exclude $s_j$ from entering in the current sensing phase}
-  
- %   \emph{return X} \;
-\caption{MuDiLCO($s_j$)}
-\label{alg:MuDiLCO}
+\subsection{Optimization solver for Multiround Lifetime Coverage Optimization}
+\label{glpk}
+The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is  employed to generate the integer 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. We named the protocol which is based on GLPK solver in the decision phase as MuDiLCO.

 
 

-\end{algorithm}

 
 %\textcolor{red}{\textbf{\textsc{Answer:}   ali   }}
 
 
 
 %\textcolor{red}{\textbf{\textsc{Answer:}   ali   }}
 
 

-\section{Genetic Algorithm (GA) for Multiround Lifetime Coverage Optimization}
+\subsection{Genetic Algorithm (GA) for Multiround Lifetime Coverage Optimization}

 \label{GA}
 \label{GA}

-Metaheuristics  are a generic search strategies for exploring search spaces for solving the complex problems. These strategies have to dynamically balance between the exploitation of the accumulated search experience and the exploration of the search space. On one hand, this balance can find regions in the search space with high-quality solutions. On the other hand, it prevents waste too much time in regions of the search space which are either already explored or don’t provide high-quality solutions. Therefore,  metaheuristic provides an enough good solution to an optimization problem, especially with incomplete  information or limited computation capacity \cite{bianchi2009survey}. Genetic Algorithm (GA) is one of the population-based metaheuristic methods that simulates the process of natural selection \cite{hassanien2015applications}.  GA starts with a population of random candidate solutions (called individuals or phenotypes) . GA uses genetic operators inspired by natural evolution, such as selection, mutation, evaluation, crossover, and replacement so as to improve the initial population of candidate solutions. This process repeated until a stopping criterion is satisfied.
+Metaheuristics  are a generic search strategies for exploring search spaces for solving the complex problems. These strategies have to dynamically balance between the exploitation of the accumulated search experience and the exploration of the search space. On one hand, this balance can find regions in the search space with high-quality solutions. On the other hand, it prevents waste too much time in regions of the search space which are either already explored or don’t provide high-quality solutions. Therefore,  metaheuristic provides an enough good solution to an optimization problem, especially with incomplete  information or limited computation capacity \cite{bianchi2009survey}. Genetic Algorithm (GA) is one of the population-based metaheuristic methods that simulates the process of natural selection \cite{hassanien2015applications}.  GA starts with a population of random candidate solutions (called individuals or phenotypes) . GA uses genetic operators inspired by natural evolution, such as selection, mutation, evaluation, crossover, and replacement so as to improve the initial population of candidate solutions. This process repeated until a stopping criterion is satisfied. Compared to GLPK optimization solver, GA provides a near optimal solution with acceptible execution time, while GLPK provides optimal solution but it requires high execution time for large problem.

 
 

-In this section, we present a metaheuristic based GA to solve our multiround lifetime coverage optimization problem. The proposed GA provides a near optimal sechedule for multiround sensing per period. The proposed GA is based on the mathematical model which is presented in Section \ref{pd}. Algorithm \ref{alg:GA} shows the proposed GA to solve the coverage lifetime optimization problem. We named the new protocol which is based on GA in the decision phase as GA-MuDiLCO. The proposed GA can be explained in more details as follow:
+In this section, we present a metaheuristic based GA to solve our multiround lifetime coverage optimization problem. The proposed GA provides a near optimal sechedule for multiround sensing per period. The proposed GA is based on the mathematical model which is presented in Section \ref{oa}. Algorithm \ref{alg:GA} shows the proposed GA to solve the coverage lifetime optimization problem. We named the new protocol which is based on GA in the decision phase as GA-MuDiLCO. The proposed GA can be explained in more details as follow:

 
 \begin{algorithm}[h!]                
  \small
 
 \begin{algorithm}[h!]                
  \small


@@ -870,7 +886,7 @@ In this section, we present a metaheuristic based GA to solve our multiround lif
   \emph{$\left\{\left(X_{1,1},\dots,X_{t,j},\dots,X_{T,J}\right)\right\}$ =
             Select Best Solution ($S_{pop}$)}\;
  \emph{return X} \;
   \emph{$\left\{\left(X_{1,1},\dots,X_{t,j},\dots,X_{T,J}\right)\right\}$ =
             Select Best Solution ($S_{pop}$)}\;
  \emph{return X} \;

-\caption{GA-MuDiLCO($s_j$)}
+\caption{GA($T, J$)}

 \label{alg:GA}
 
 \end{algorithm}
 \label{alg:GA}
 
 \end{algorithm}


@@ -1030,16 +1046,20 @@ $R_s$ & 5~m   \\
 $W_{\theta}$ & 1   \\
 % [1ex] adds vertical space
 %\hline
 $W_{\theta}$ & 1   \\
 % [1ex] adds vertical space
 %\hline

-$W_{U}$ & $|P|^2$
+$W_{U}$ & $|P|^2$ \\
+$P_c$ & 0.95   \\ 
+$P_m$ & 0.6 \\
+$S_{pop}$ & 50

 %inserts single line
 \end{tabular}
 \label{table3}
 % is used to refer this table in the text
 \end{table}
   
 %inserts single line
 \end{tabular}
 \label{table3}
 % is used to refer this table in the text
 \end{table}
   

-Our protocol  is declined into  four versions: MuDiLCO-1,  MuDiLCO-3, MuDiLCO-5,
+\textcolor{red}{Our first protocol based GLPK optimization solver 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
 and  MuDiLCO-7, corresponding  respectively to  $T=1,3,5,7$ ($T$  the  number of

-rounds in one sensing period).  In  the following, we will make comparisons with
+rounds in one sensing period). The second protocol based GA is declined into  four versions: GA-MuDiLCO-1,  GA-MuDiLCO-3, GA-MuDiLCO-5,
+and  GA-MuDiLCO-7 for the same reason of the first protocol. After extensive experiments, we chose the dedicated values for the parameters $P_c$, $P_m$, and $S_{pop}$ because they gave the best results}.  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.
 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.


@@ -1253,19 +1273,20 @@ rounds, and thus should extend the network lifetime.
 \label{fig3}
 \end{figure} 
 
 \label{fig3}
 \end{figure} 
 

+\textcolor{red}{ We
+can see that for the first thirty nine rounds GA-MuDiLCO provides a little bit better coverage ratio  than MuDiLCO. Both DESK and GAF provide a coverage
+which is a little bit better than the one of MuDiLCO and GA-MuDiLCO for the first thirty rounds because they activate a larger number of nodes during sensing phase. After that GA-MuDiLCO provides a coverage ratio near to the  MuDiLCO and better than DESK and GAF. GA-MuDiLCO gives approximate solution with activation a larger number of nodes than MuDiLCO during sensing phase while it activates a less number of nodes in comparison with both DESK and GAF. The results of GA-MuDiLCO seems to be comparable and can maintain the lifetime coverage as long as possible.}
+
+
+

 \subsubsection{Active sensors ratio} 
 
 It is crucial to have as few active nodes as possible in each round, in order to
 \subsubsection{Active sensors ratio} 
 
 It is crucial to have as few active nodes as possible in each round, in order to

-minimize    the    communication    overhead    and   maximize    the    network
-lifetime. Figure~\ref{fig4}  presents the active  sensor ratio for  150 deployed
+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
 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 clearly  outperforms them  with only 24.8\%  of active nodes.  After the
-thirty-fifth round, MuDiLCO exhibits larger numbers 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
-activated many nodes  at the beginning. Anyway, MuDiLCO  activates the available
-nodes in a more efficient manner.
+MuDiLCO clearly outperforms them  with only 24.8\%  of active nodes. \textcolor{red}{GA-MuDiLCO activates a number of sensor nodes larger than MuDiLCO but lower than both DESK and GAF. GA-MuDiLCO-1, GA-MuDiLCO-3, and GA-MuDiLCO-5 continue in providing a larger number of active sensors until the forty-sixth round after that it provides less number of active nodes due to the died nodes. GA-MuDiLCO-7 provides a larger number of sensor nodes and maintains a better coverage ratio compared to MuDiLCO-7 until the fifty-seventh round.  After the thirty-fifth round, MuDiLCO exhibits larger numbers of active nodes compared with DESK  and GAF, 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 activated many nodes  at the beginning. Anyway, MuDiLCO  activates the available nodes in a more efficient manner. \textcolor{red}{GA-MuDiLCO activates near optimal number of sensor nodes also in efficient manner compared with both DESK  and GAF}.

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


@@ -1274,6 +1295,9 @@ nodes in a more efficient manner.
 \label{fig4}
 \end{figure} 
 
 \label{fig4}
 \end{figure} 
 

+%\textcolor{red}{GA-MuDiLCO activates a sensor nodes larger than MuDiLCO but lower than both DESK and GAF }
+
+

 \subsubsection{Stopped simulation runs}
 %The results presented in this experiment, is to show the comparison of our MuDiLCO protocol with other two approaches from the point of view the stopped simulation runs per round. Figure~\ref{fig6} illustrates the percentage of stopped simulation
 %runs per round for 150 deployed nodes. 
 \subsubsection{Stopped simulation runs}
 %The results presented in this experiment, is to show the comparison of our MuDiLCO protocol with other two approaches from the point of view the stopped simulation runs per round. Figure~\ref{fig6} illustrates the percentage of stopped simulation
 %runs per round for 150 deployed nodes. 


@@ -1281,11 +1305,9 @@ nodes in a more efficient manner.
 Figure~\ref{fig6} reports the cumulative  percentage of stopped simulations runs
 per round for  150 deployed nodes. This figure gives the  breakpoint for each method.  DESK stops first,  after approximately 45~rounds, because it consumes the
 more energy by  turning on a large number of redundant  nodes during the sensing
 Figure~\ref{fig6} reports the cumulative  percentage of stopped simulations runs
 per round for  150 deployed nodes. This figure gives the  breakpoint for each method.  DESK stops first,  after approximately 45~rounds, because it consumes the
 more energy by  turning on a large number of redundant  nodes during the sensing

-phase. GAF  stops secondly for the  same reason than  DESK.  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
-still connected.
+phase. GAF  stops secondly for the  same reason than  DESK. \textcolor{red}{GA-MuDiLCO  stops thirdly for the  same reason than  DESK and GAF.} \textcolor{red}{MuDiLCO and GA-MuDiLCO overcome}
+DESK and GAF because \textcolor{red}{they activate less number of sensor nodes, as well as }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 still connected. 

 
 %%% The optimization effectively continues as long as a network in a subregion is still connected. A VOIR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 
 %%% The optimization effectively continues as long as a network in a subregion is still connected. A VOIR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%