\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
-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
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 }}
-\section{Genetic Algorithm (GA) for Multiround Lifetime Coverage Optimization}
+\subsection{Genetic Algorithm (GA) for Multiround Lifetime Coverage Optimization}
\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
\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}
$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}
-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
-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.
