From 36db960042a3c1e4f89192ddb4ebd8916f310b92 Mon Sep 17 00:00:00 2001 From: ali Date: Thu, 20 Aug 2015 02:07:46 +0200 Subject: [PATCH 1/1] Update by Ali --- article.bib | 16 ++++++ article.tex | 138 ++++++++++++++++++++++++++++++---------------------- 2 files changed, 95 insertions(+), 59 deletions(-) diff --git a/article.bib b/article.bib index c33504c..b5b4171 100644 --- a/article.bib +++ b/article.bib @@ -571,4 +571,20 @@ year = {2012} 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 diff --git a/article.tex b/article.tex index fb4739a..b1a25fa 100644 --- a/article.tex +++ b/article.tex @@ -647,12 +647,71 @@ consumption due to the communications. \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 @@ -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. -\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 @@ -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} \; -\caption{GA-MuDiLCO($s_j$)} +\caption{GA($T, J$)} \label{alg:GA} \end{algorithm} @@ -1030,16 +1046,20 @@ $R_s$ & 5~m \\ $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. -- 2.39.5