Update for refrences and adding DiLCO to related works and adding the alfa and beta...

[LiCO.git] / PeCO-EO / articleeo.tex

diff --git a/PeCO-EO/articleeo.tex b/PeCO-EO/articleeo.tex
index 40af2f40796b23e0ae78c40e081e37ebf32833ef..39a0559f3c5a2e4d67885b8290bb981013203f04 100644 (file)
--- a/PeCO-EO/articleeo.tex
+++ b/PeCO-EO/articleeo.tex
@@ -27,7 +27,7 @@ as long as  possible. Among  known  available approaches  that can  be used  to
 improve  power  management,  lifetime coverage  optimization  provides  activity
 scheduling which ensures sensing coverage while minimizing the energy cost. We propose such an approach called Perimeter-based Coverage Optimization
 protocol (PeCO). It is a  hybrid of centralized and distributed methods: the
 improve  power  management,  lifetime coverage  optimization  provides  activity
 scheduling which ensures sensing coverage while minimizing the energy cost. We propose such an approach called Perimeter-based Coverage Optimization
 protocol (PeCO). It is a  hybrid of centralized and distributed methods: the

-region of interest is first subdivided into subregions and our protocol is then
+region of interest is first subdivided into subregions and the protocol is then

 distributed among sensor nodes in each  subregion.
 The novelty of our approach lies essentially in the formulation of a new
 mathematical optimization  model based on the  perimeter coverage level  to schedule
 distributed among sensor nodes in each  subregion.
 The novelty of our approach lies essentially in the formulation of a new
 mathematical optimization  model based on the  perimeter coverage level  to schedule


@@ -100,8 +100,8 @@ This paper makes the following contributions.
 
 
 
 
 
 

-The rest  of the paper is  organized as follows.  In the next section  we review
-some related work in the  field. Section~\ref{sec:The PeCO Protocol Description}
+The rest  of the paper is  organized as follows.  In the next section
+some related work in the  field is reviewed. Section~\ref{sec:The PeCO Protocol Description}

 is devoted to the PeCO protocol  description and Section~\ref{cp} focuses on the
 coverage model  formulation which is used  to schedule the activation  of sensor
 nodes.  Section~\ref{sec:Simulation  Results and Analysis}  presents simulations
 is devoted to the PeCO protocol  description and Section~\ref{cp} focuses on the
 coverage model  formulation which is used  to schedule the activation  of sensor
 nodes.  Section~\ref{sec:Simulation  Results and Analysis}  presents simulations


@@ -112,9 +112,9 @@ Section~\ref{sec:Conclusion and Future Works}.
 \section{Related Literature}
 \label{sec:Literature Review}
 
 \section{Related Literature}
 \label{sec:Literature Review}
 

-In  this section,  we  summarize  some  related works  regarding  the
-coverage problem and  distinguish our PeCO protocol from the  works presented in
-the literature.
+In  this section, some  related works  regarding  the
+coverage problem is summarized, and specific aspects of the PeCO protocol from the  works presented in
+the literature are presented.

 
 The most  discussed coverage problems in  literature can be classified  in three
 categories~\citep{li2013survey}   according   to  their   respective   monitoring
 
 The most  discussed coverage problems in  literature can be classified  in three
 categories~\citep{li2013survey}   according   to  their   respective   monitoring


@@ -129,8 +129,8 @@ nodes    or   between    disk   of    sensor   nodes    and   boundaries.     In
 \citep{Huang:2003:CPW:941350.941367}  authors prove  that  if  the perimeters  of
 sensors are sufficiently  covered it will be  the case for the  whole area. They
 provide an algorithm in $O(nd~log~d)$  time to compute the perimeter-coverage of
 \citep{Huang:2003:CPW:941350.941367}  authors prove  that  if  the perimeters  of
 sensors are sufficiently  covered it will be  the case for the  whole area. They
 provide an algorithm in $O(nd~log~d)$  time to compute the perimeter-coverage of

-each  sensor,  where  $d$  denotes  the  maximum  number  of  sensors  that  are
-neighbors  to  a  sensor and  $n$  is  the  total  number of  sensors  in  the
+each  sensor. $d$  denotes  the  maximum  number  of  sensors  that  are
+neighbors  to  a  sensor, and  $n$  is  the  total  number of  sensors  in  the

 network. {\it In PeCO protocol, instead  of determining the level of coverage of
   a set  of discrete  points, our  optimization model is  based on  checking the
   perimeter-coverage of each sensor to activate a minimal number of sensors.}
 network. {\it In PeCO protocol, instead  of determining the level of coverage of
   a set  of discrete  points, our  optimization model is  based on  checking the
   perimeter-coverage of each sensor to activate a minimal number of sensors.}


@@ -197,11 +197,20 @@ used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012col
 
 
 
 
 
 

+The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage Optimization (DiLCO) protocol, maintains the coverage and improves the lifetime in WSNs. It is  an improved version
+of a research work they presented in~\citep{idrees2014coverage}.  First, they partition the area of interest into subregions using a divide-and-conquer method. DiLCO protocol is then distributed on the sensor nodes in each subregion in a second step. DiLCO protocol combines two techniques: a leader election in each subregion, followed by an optimization-based node activity scheduling performed by each elected leader. The proposed DiLCO protocol is a periodic protocol where each period is decomposed into 4 phases: information exchange, leader election, decision, and sensing. The simulations show that DiLCO is able to increase the WSN lifetime and provides improved coverage performance. {\it  In the PeCO
+  protocol, We have proposed a new mathematical optimization model. Instead of trying to
+cover a set of specified points/targets as in DiLCO protocol, we formulate an integer program based
+on perimeter coverage of each sensor. The model involves integer variables to capture the deviations between the actual level of coverage and the required level. The idea is that an optimal scheduling will be obtained by minimizing a weighted sum of these deviations.}
+  
+  
+  
+

 \section{ The P{\scshape e}CO Protocol Description}
 \label{sec:The PeCO Protocol Description}
 
 \section{ The P{\scshape e}CO Protocol Description}
 \label{sec:The PeCO Protocol Description}
 

-In  this  section,  we  describe in  details  our Perimeter-based  Coverage
-Optimization protocol.  First we present the  assumptions we made and the models
+In  this  section,  the Perimeter-based  Coverage
+Optimization protocol is decribed in details.  First we present the  assumptions we made and the models

 we considered (in particular the perimeter coverage one), second we describe the
 background idea of our protocol, and third  we give the outline of the algorithm
 executed by each node.
 we considered (in particular the perimeter coverage one), second we describe the
 background idea of our protocol, and third  we give the outline of the algorithm
 executed by each node.


@@ -217,11 +226,7 @@ of interest.  We  assume that all the  sensor nodes are homogeneous  in terms of
 communication,  sensing,  and  processing capabilities  and  heterogeneous  from
 the energy provision  point of  view.  The  location information  is available  to a
 sensor node either  through hardware such as embedded GPS  or location discovery
 communication,  sensing,  and  processing capabilities  and  heterogeneous  from
 the energy provision  point of  view.  The  location information  is available  to a
 sensor node either  through hardware such as embedded GPS  or location discovery

-algorithms.   We  assume  that  each  sensor  node  can  directly  transmit  its
-measurements to  a mobile  sink node.  For  example, a sink  can be  an unmanned
-aerial  vehicle  (UAV)  flying  regularly  over  the  sensor  field  to  collect
-measurements from sensor nodes. A mobile sink node collects the measurements and
-transmits them to the base station.   We consider a Boolean disk coverage model,
+algorithms. We consider a Boolean disk coverage model,

 which is the most  widely used sensor coverage model in  the literature, and all
 sensor nodes  have a constant sensing  range $R_s$.  Thus, all  the space points
 within a disk centered at a sensor with  a radius equal to the sensing range are
 which is the most  widely used sensor coverage model in  the literature, and all
 sensor nodes  have a constant sensing  range $R_s$.  Thus, all  the space points
 within a disk centered at a sensor with  a radius equal to the sensing range are


@@ -232,11 +237,11 @@ complete coverage of a convex area implies connectivity among active nodes.
 
 The PeCO protocol  uses the  same perimeter-coverage  model as \citet{huang2005coverage}. It  can be expressed as follows:  a sensor is
 said to be perimeter  covered if all the points on its  perimeter are covered by
 
 The PeCO protocol  uses the  same perimeter-coverage  model as \citet{huang2005coverage}. It  can be expressed as follows:  a sensor is
 said to be perimeter  covered if all the points on its  perimeter are covered by

-at least  one sensor  other than  itself.  They  proved that  a network  area is
-$k$-covered if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors).
+at least  one sensor  other than  itself. Authors \citet{huang2005coverage}  proved that  a network  area is
+$k$-covered (every point in the area covered by at least k sensors) if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors). 

  
 Figure~\ref{figure1}(a)  shows  the coverage  of  sensor  node~$0$. On  this
  
 Figure~\ref{figure1}(a)  shows  the coverage  of  sensor  node~$0$. On  this

-figure, we can  see that sensor~$0$ has  nine neighbors and we  have reported on
+figure, sensor~$0$ has  nine neighbors and we  have reported on

 its  perimeter (the  perimeter  of the  disk  covered by  the  sensor) for  each
 neighbor  the  two  points  resulting  from the intersection  of  the  two  sensing
 areas. These points are denoted for  neighbor~$i$ by $iL$ and $iR$, respectively
 its  perimeter (the  perimeter  of the  disk  covered by  the  sensor) for  each
 neighbor  the  two  points  resulting  from the intersection  of  the  two  sensing
 areas. These points are denoted for  neighbor~$i$ by $iL$ and $iR$, respectively


@@ -259,8 +264,8 @@ Figure~\ref{figure1}(b) describes the geometric information used to find the
 locations of the  left and right points of  an arc on the perimeter  of a sensor
 node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the
 west  side of  sensor~$u$,  with  the following  respective  coordinates in  the
 locations of the  left and right points of  an arc on the perimeter  of a sensor
 node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the
 west  side of  sensor~$u$,  with  the following  respective  coordinates in  the

-sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates we can
-compute the euclidean distance between nodes~$u$ and $v$: $Dist(u,v)=\sqrt{\vert
+sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates 
+the euclidean distance between nodes~$u$ and $v$ is computed: $Dist(u,v)=\sqrt{\vert

   u_x  - v_x  \vert^2 +  \vert u_y-v_y  \vert^2}$, while  the angle~$\alpha$  is
 obtained through  the formula:
  \[
   u_x  - v_x  \vert^2 +  \vert u_y-v_y  \vert^2}$, while  the angle~$\alpha$  is
 obtained through  the formula:
  \[


@@ -274,7 +279,7 @@ Every couple of intersection points is placed on the angular interval $[0,2\pi)$
 in  a  counterclockwise manner,  leading  to  a  partitioning of  the  interval.
 Figure~\ref{figure1}(a)  illustrates  the arcs  for  the  nine neighbors  of
 sensor $0$ and  Figure~\ref{figure2} gives the position of  the corresponding arcs
 in  a  counterclockwise manner,  leading  to  a  partitioning of  the  interval.
 Figure~\ref{figure1}(a)  illustrates  the arcs  for  the  nine neighbors  of
 sensor $0$ and  Figure~\ref{figure2} gives the position of  the corresponding arcs

-in  the interval  $[0,2\pi)$. More  precisely, we  can see  that the  points are
+in  the interval  $[0,2\pi)$. More  precisely, the  points are

 ordered according  to the  measures of  the angles  defined by  their respective
 positions. The intersection points are  then visited one after another, starting
 from the first  intersection point  after  point~zero,  and  the maximum  level  of
 ordered according  to the  measures of  the angles  defined by  their respective
 positions. The intersection points are  then visited one after another, starting
 from the first  intersection point  after  point~zero,  and  the maximum  level  of


@@ -471,10 +476,10 @@ construct the set of active sensors in the sensing stage.
 \section{Perimeter-based Coverage Problem Formulation}
 \label{cp}
 
 \section{Perimeter-based Coverage Problem Formulation}
 \label{cp}
 

-In this  section, the coverage model is  mathematically formulated. We
-start  with a  description of the notations that will  be used  throughout the
+In this  section, the coverage model is  mathematically formulated. The following
+notations are used  throughout the

 section.\\
 section.\\

-First, we have the following sets:
+First, the following sets:

 \begin{itemize}
 \item $S$ represents the set of WSN sensor nodes;
 \item $A \subseteq S $ is the subset of alive sensors;
 \begin{itemize}
 \item $S$ represents the set of WSN sensor nodes;
 \item $A \subseteq S $ is the subset of alive sensors;


@@ -495,7 +500,7 @@ a^j_{ik} = \left \{
 \end{equation}
 Note that $a^k_{ik}=1$ by definition of the interval.
 
 \end{equation}
 Note that $a^k_{ik}=1$ by definition of the interval.
 

-Second,  we define  several binary  and integer  variables.  Hence,  each binary
+Second, several binary  and integer  variables are defined.  Hence,  each binary

 variable $X_{k}$  determines the activation of  sensor $k$ in the  sensing phase
 ($X_k=1$ if  the sensor $k$  is active or 0  otherwise).  $M^j_i$ is  an integer
 variable  which  measures  the  undercoverage  for  the  coverage  interval  $i$
 variable $X_{k}$  determines the activation of  sensor $k$ in the  sensing phase
 ($X_k=1$ if  the sensor $k$  is active or 0  otherwise).  $M^j_i$ is  an integer
 variable  which  measures  the  undercoverage  for  the  coverage  interval  $i$


@@ -510,7 +515,7 @@ sensor $j$  is given by  $\sum_{k \in A} a^j_{ik}  X_k$.  To extend  the network
 lifetime,  the objective  is to  activate a  minimal number  of sensors  in each
 period to  ensure the  desired coverage  level. As the  number of  alive sensors
 decreases, it becomes impossible to reach  the desired level of coverage for all
 lifetime,  the objective  is to  activate a  minimal number  of sensors  in each
 period to  ensure the  desired coverage  level. As the  number of  alive sensors
 decreases, it becomes impossible to reach  the desired level of coverage for all

-coverage intervals. Therefore we use variables  $M^j_i$ and $V^j_i$ as a measure
+coverage intervals. Therefore  variables  $M^j_i$ and $V^j_i$ are introduced as a measure

 of the  deviation between  the desired  number of active  sensors in  a coverage
 interval and  the effective  number. And  we try  to minimize  these deviations,
 first to  force the  activation of  a minimal  number of  sensors to  ensure the
 of the  deviation between  the desired  number of active  sensors in  a coverage
 interval and  the effective  number. And  we try  to minimize  these deviations,
 first to  force the  activation of  a minimal  number of  sensors to  ensure the


@@ -527,8 +532,8 @@ Our coverage optimization problem can then be mathematically expressed as follow
 \begin{array}{ll}
 \min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\
 \textrm{subject to :}&\\
 \begin{array}{ll}
 \min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\
 \textrm{subject to :}&\\

-\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i  \geq l \quad \forall i \in I_j, \forall j \in S\\
-\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i  \leq l \quad \forall i \in I_j, \forall j \in S\\
+\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i  = l \quad \forall i \in I_j, \forall j \in S\\
+\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i  = l \quad \forall i \in I_j, \forall j \in S\\

 X_{k} \in \{0,1\}, \forall k \in A
 \end{array}
 \right.
 X_{k} \in \{0,1\}, \forall k \in A
 \end{array}
 \right.


@@ -544,9 +549,9 @@ brachytherapy treatment planning  for optimizing dose  distribution
 each subregion at the beginning of  each sensing phase, whenever the environment
 has  changed (new  leader,  death of  some  sensors). Note  that  the number  of
 constraints in the model is constant  (constraints of coverage expressed for all
 each subregion at the beginning of  each sensing phase, whenever the environment
 has  changed (new  leader,  death of  some  sensors). Note  that  the number  of
 constraints in the model is constant  (constraints of coverage expressed for all

-sensors), whereas the number of variables $X_k$ decreases over periods, since we
-consider only alive  sensors (sensors with enough energy to  be alive during one
-sensing phase) in the model.
+sensors), whereas the number of variables $X_k$ decreases over periods, since 
+only alive  sensors (sensors with enough energy to  be alive during one
+sensing phase) are considered in the model.

 
 \section{Performance Evaluation and Analysis}  
 \label{sec:Simulation Results and Analysis}
 
 \section{Performance Evaluation and Analysis}  
 \label{sec:Simulation Results and Analysis}


@@ -580,7 +585,7 @@ Initial energy  & in range 500-700~Joules  \\
 Sensing period & duration of 60 minutes \\
 $E_{th}$ & 36~Joules\\
 $R_s$ & 5~m   \\     
 Sensing period & duration of 60 minutes \\
 $E_{th}$ & 36~Joules\\
 $R_s$ & 5~m   \\     

-
+$R_c$ & 10~m   \\   

 $\alpha^j_i$ & 0.6   \\
 
 $\beta^j_i$ & 0.4
 $\alpha^j_i$ & 0.6   \\
 
 $\beta^j_i$ & 0.4


@@ -604,14 +609,14 @@ pre-sensing phases.  According  to the interval of initial energy,  a sensor may
 be active during at most 20 periods.
 
 The values  of $\alpha^j_i$ and  $\beta^j_i$ have been  chosen to ensure  a good
 be active during at most 20 periods.
 
 The values  of $\alpha^j_i$ and  $\beta^j_i$ have been  chosen to ensure  a good

-network coverage and a longer WSN lifetime.  We have given a higher priority to
+network coverage and a longer WSN lifetime.  Higher priority is given to

 the  undercoverage  (by  setting  the  $\alpha^j_i$ with  a  larger  value  than
 $\beta^j_i$)  so as  to prevent  the non-coverage  for the  interval~$i$ of  the
 the  undercoverage  (by  setting  the  $\alpha^j_i$ with  a  larger  value  than
 $\beta^j_i$)  so as  to prevent  the non-coverage  for the  interval~$i$ of  the

-sensor~$j$.  On the  other hand,  we have assigned to
-$\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute
+sensor~$j$.  On the  other hand,  
+$\beta^j_i$ is assigned to a value which is slightly lower so as to minimize the number of active sensor nodes which contribute

 in covering the interval.
 
 in covering the interval.
 

-We introduce the following performance metrics to evaluate the efficiency of our
+The following performance metrics are used to evaluate the efficiency of the

 approach.
 
 
 approach.
 
 


@@ -625,7 +630,7 @@ approach.
   because without  network connectivity a  sensor may not be  able to send  to a
   base station an event it has sensed.
 \item {\bf  Coverage Ratio (CR)} : it  measures how  well the  WSN is  able to
   because without  network connectivity a  sensor may not be  able to send  to a
   base station an event it has sensed.
 \item {\bf  Coverage Ratio (CR)} : it  measures how  well the  WSN is  able to

-  observe the area of interest. In our  case, we discretized the sensor field as
+  observe the area of interest. In our  case, the sensor field is discretized as

   a regular grid, which yields the following equation:
   
 
   a regular grid, which yields the following equation:
   
 


@@ -637,8 +642,8 @@ approach.
 
   where $n$  is the  number of covered  grid points by  active sensors  of every
   subregions during  the current sensing phase  and $N$ is total  number of grid
 
   where $n$  is the  number of covered  grid points by  active sensors  of every
   subregions during  the current sensing phase  and $N$ is total  number of grid

-  points in  the sensing  field.  In  our simulations  we have  set a  layout of
-  $N~=~51~\times~26~=~1326$~grid points.
+  points in  the sensing  field.  In  simulations  a  layout of
+  $N~=~51~\times~26~=~1326$~grid points is considered.

 \item {\bf Active Sensors Ratio (ASR)}: a  major objective of our protocol is to
   activate  as few nodes as possible,  in order  to minimize  the communication
   overhead and maximize the WSN lifetime. The active sensors ratio is defined as
 \item {\bf Active Sensors Ratio (ASR)}: a  major objective of our protocol is to
   activate  as few nodes as possible,  in order  to minimize  the communication
   overhead and maximize the WSN lifetime. The active sensors ratio is defined as


@@ -827,6 +832,30 @@ not ineffective for the smallest network sizes.
 \end{figure} 
 
 
 \end{figure} 
 
 

+\subsubsection{\bf Impact of $\alpha$ and $\beta$ on PeCO's performance}
+
+Table~\ref{tbl} shows the  impact of $\alpha$ and $\beta$ on PeCO's performance.
+
+\begin{table}[h]
+\centering
+\caption{The impact of $\alpha$ and $\beta$ on PeCO's performance}
+\label{my-label}
+\begin{tabular}{|c|c|c|c|}
+\hline
+$\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
+0.0 & 1.0 & 151 & 0 \\ \hline
+0.1 & 0.9 & 145 & 0 \\ \hline
+0.2 & 0.8 & 140 & 0 \\ \hline
+0.3 & 0.7 & 134 & 0 \\ \hline
+0.4 & 0.6 & 125 & 0 \\ \hline
+0.5 & 0.5 & 118 & 30 \\ \hline
+0.6 & 0.4 & 94 & 57 \\ \hline
+0.7 & 0.3 & 97 & 49 \\ \hline
+0.8 & 0.2 & 90 & 52 \\ \hline
+0.9 & 0.1 & 77 & 50 \\ \hline
+1.0 & 0.0 & 60 & 44 \\ \hline
+\end{tabular}
+\end{table}

 
 
 \section{Conclusion and Future Works}
 
 
 \section{Conclusion and Future Works}


@@ -842,7 +871,7 @@ is based on the resolution of an integer program to select the subset of sensors
 operating in active status for each period. Our work is original in so far as it
 proposes for  the first  time an  integer program  scheduling the  activation of
 sensors  based on  their perimeter  coverage level,  instead of  using a  set of
 operating in active status for each period. Our work is original in so far as it
 proposes for  the first  time an  integer program  scheduling the  activation of
 sensors  based on  their perimeter  coverage level,  instead of  using a  set of

-targets/points to be covered.
+targets/points to be covered.   

 
 
 We  have carried out  several simulations  to  evaluate the  proposed protocol.   The
 
 
 We  have carried out  several simulations  to  evaluate the  proposed protocol.   The


@@ -860,7 +889,7 @@ Finally,  it   would  be   interesting  to  implement   our  protocol   using  a
 sensor-testbed to evaluate it in real world applications.
 
 \bibliographystyle{gENO}
 sensor-testbed to evaluate it in real world applications.
 
 \bibliographystyle{gENO}

-\bibliography{biblio}
+\bibliography{articleeo}

 
 
 \end{document}
 
 
 \end{document}