]> AND Private Git Repository - JournalMultiPeriods.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Update by Ali
authorali <ali@ali.lan>
Thu, 20 Aug 2015 00:07:46 +0000 (02:07 +0200)
committerali <ali@ali.lan>
Thu, 20 Aug 2015 00:07:46 +0000 (02:07 +0200)
article.bib
article.tex

index c33504c612bb2b696f08fb6b8fe7ba0a8608c506..b5b41718ab5a4627ed4653e20a72dd24abd294cf 100644 (file)
@@ -571,4 +571,20 @@ year = {2012}
   volume={1},
   pages={69--93},
   year={1991}
   volume={1},
   pages={69--93},
   year={1991}
+}
+
+@BOOK{AMPL,
+  AUTHOR =       "Robert Fourer and David M. Gay and Brian W. Kernighan",
+  TITLE =        "AMPL: A Modeling Language for Mathematical Programming",
+  PUBLISHER =    "Cengage Learning",
+  YEAR =         "November 12, 2002",
+  edition =      "2nd",
+}
+
+@ARTICLE{glpk,
+author = {Andrew Makhorin},
+title = {The GLPK (GNU Linear Programming Kit)},
+journal = {Available: https://www.gnu.org/software/glpk/},
+year = {2012}
 }
\ No newline at end of file
 }
\ No newline at end of file
index fb4739a85b2288007a6b1b685f058efae9e1b1a3..b1a25fa10f26d85403f19576396e7276b50c75f1 100644 (file)
@@ -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}
-
-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. 
+This integer program can be solved using two approaches:
 
 
-\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}.  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.