Ali modification

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

diff --git a/PeCO-EO/articleeo.tex~ b/PeCO-EO/articleeo.tex~
index 58e1e1d5c1a0b3d7804a86267c221ee492572793..215576a0d37a700c4de1cd15a701bea12c2f052b 100644 (file)
--- a/PeCO-EO/articleeo.tex~
+++ b/PeCO-EO/articleeo.tex~
@@ -91,8 +91,7 @@ This paper makes the following contributions.
   simulator OMNeT++, to demonstrate the  efficiency of our protocol. We have compared
   our   PeCO   protocol   to   two   approaches   found   in   the   literature:
   DESK~\citep{ChinhVu} and  GAF~\citep{xu2001geography}, and also to  our previous
   simulator OMNeT++, to demonstrate the  efficiency of our protocol. We have compared
   our   PeCO   protocol   to   two   approaches   found   in   the   literature:
   DESK~\citep{ChinhVu} and  GAF~\citep{xu2001geography}, and also to  our previous

-  work published in~\citep{Idrees2} which is  based on another optimization model
-  for sensor scheduling.
+  protocol DilCO published in~\citep{Idrees2}. DilCO uses the same framework as PeCO but is  based on another optimization model for sensor scheduling.

 \end{enumerate}
 
 
 \end{enumerate}
 
 


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

+The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage Optimization (DiLCO) protocol, which 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,  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.
+%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.

 
 
 \subsection{Assumptions and Models}
 
 
 \subsection{Assumptions and Models}


@@ -217,11 +225,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


@@ -273,7 +277,7 @@ The arc on the perimeter of~$u$ defined by the angular interval $[\pi
 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
 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
+sensor $0$ and  table~\ref{my-label} gives the position of  the corresponding arcs

 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
 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


@@ -331,7 +335,7 @@ above is thus given by the sixth line of the table.
 
 
 In the PeCO  protocol, the scheduling of the sensor  nodes' activities is formulated  with an
 
 
 In the PeCO  protocol, the scheduling of the sensor  nodes' activities is formulated  with an

-integer program  based on  coverage intervals. The  formulation of  the coverage
+mixed-doi:10.1155/2010/926075integer program  based on  coverage intervals. The  formulation of  the coverage

 optimization problem is  detailed in~Section~\ref{cp}.  Note that  when a sensor
 node  has a  part of  its sensing  range outside  the WSN  sensing field,  as in
 Figure~\ref{figure3}, the maximum coverage level for  this arc is set to $\infty$
 optimization problem is  detailed in~Section~\ref{cp}.  Note that  when a sensor
 node  has a  part of  its sensing  range outside  the WSN  sensing field,  as in
 Figure~\ref{figure3}, the maximum coverage level for  this arc is set to $\infty$


@@ -352,7 +356,7 @@ optimization algorithm.
 The  WSN area of  interest is, in a  first step, divided  into regular
 homogeneous subregions  using a divide-and-conquer  algorithm. In a  second step
 our  protocol  will  be  executed  in   a  distributed  way  in  each  subregion
 The  WSN area of  interest is, in a  first step, divided  into regular
 homogeneous subregions  using a divide-and-conquer  algorithm. In a  second step
 our  protocol  will  be  executed  in   a  distributed  way  in  each  subregion

-simultaneously to schedule nodes' activities for one sensing period.
+simultaneously to schedule nodes' activities for one sensing period. In the study, sensors are assumed to be deployed almost uniformly over the region. The regular subdivision is made such that the number of hops between any pairs of sensors inside a subregion is less than or equal to 3. 

 
 As  shown in  Figure~\ref{figure4}, node  activity  scheduling is  produced by  our
 protocol in a periodic manner. Each period is divided into 4 stages: Information
 
 As  shown in  Figure~\ref{figure4}, node  activity  scheduling is  produced by  our
 protocol in a periodic manner. Each period is divided into 4 stages: Information


@@ -370,7 +374,7 @@ taken  into  account since  the  sensors  can  update  and then  exchange  their
 information (including their  residual energy) at the beginning  of each period.
 However, the pre-sensing  phases (INFO Exchange, Leader  Election, and Decision)
 are energy consuming, even for nodes that will not join the set cover to monitor
 information (including their  residual energy) at the beginning  of each period.
 However, the pre-sensing  phases (INFO Exchange, Leader  Election, and Decision)
 are energy consuming, even for nodes that will not join the set cover to monitor

-the area.
+the area. Sensing period duration is adapted according to the QoS requirements of the application.

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


@@ -471,8 +475,9 @@ 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. The following
-notations are used  throughout the
+In this  section, the perimeter-based coverage problem is  mathematically formulated. It has been proved to be a NP-hard problem by\citep{doi:10.1155/2010/926075}. Authors study the coverage of the perimeter of a large object requiring to be monitored. For the proposed formulation in this paper, the large object to be monitored is the sensor itself (or more precisely its sensing area).
+
+The following notations are used  throughout the

 section.\\
 First, the following sets:
 \begin{itemize}
 section.\\
 First, the following sets:
 \begin{itemize}


@@ -495,16 +500,16 @@ 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, several binary  and integer  variables are defined.  Hence,  each binary
+Second, several variables are defined.  Hence,  each binary

 variable $X_{k}$  determines the activation of  sensor $k$ in the  sensing phase
 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
+($X_k=1$ if  the sensor $k$  is active or 0  otherwise).  $M^j_i$ is  a

 variable  which  measures  the  undercoverage  for  the  coverage  interval  $i$
 corresponding to  sensor~$j$. In  the same  way, the  overcoverage for  the same
 coverage interval is given by the variable $V^j_i$.
 
 variable  which  measures  the  undercoverage  for  the  coverage  interval  $i$
 corresponding to  sensor~$j$. In  the same  way, the  overcoverage for  the same
 coverage interval is given by the variable $V^j_i$.
 

-If we decide to sustain a level of coverage equal to $l$ all along the perimeter
-of sensor  $j$, we have  to ensure  that at least  $l$ sensors involved  in each
-coverage  interval $i  \in I_j$  of  sensor $j$  are active.   According to  the
+To sustain a level of coverage equal to $l$ all along the perimeter
+of sensor  $j$, at least  $l$ sensors involved  in each
+coverage  interval $i  \in I_j$  of  sensor $j$ have to be active.   According to  the

 previous notations, the number of active sensors in the coverage interval $i$ of
 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
 previous notations, the number of active sensors in the coverage interval $i$ of
 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


@@ -520,33 +525,37 @@ to reach a coverage level as close as possible to the desired one.
 
 
 
 
 
 

-Our coverage optimization problem can then be mathematically expressed as follows: 
+The coverage optimization problem can then be mathematically expressed as follows: 

 
 \begin{equation} 
 \left \{
 \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{equation} 
 \left \{
 \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  = 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
+\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\\
+X_{k} \in \{0,1\}, \forall k \in A \\
+M^j_i, V^j_i \in  \mathbb{R}^{+}

 \end{array}
 \right.
 \end{equation}
 
 \end{array}
 \right.
 \end{equation}
 

+If a given level of coverage $l$ is required  for one sensor, the sensor is said to be undercovered (respectively overcovered) if the level of coverage of one of its CI is less (respectively greater) than $l$. If the sensor $j$ is undercovered, there exists at least one of its CI (say $i$) for which the number of active sensors (denoted by $l^{i}$) covering this part of the perimeter is less than $l$ and in this case : $M_{i}^{j}=l-l^{i}$, $V_{i}^{j}=0$. In the contrary, if the sensor $j$ is overcovered, there exists at least one of its CI (say $i$) for which the number of active sensors (denoted by $l^{i}$) covering this part of the perimeter is greater than $l$ and in this case : $M_{i}^{j}=0$, $V_{i}^{j}=l^{i}-l$.  
+

 $\alpha^j_i$ and $\beta^j_i$  are nonnegative weights selected  according to the
 relative importance of satisfying the associated level of coverage. For example,
 weights associated with  coverage intervals of a specified part  of a region may
 be  given by a  relatively larger  magnitude than  weights associated  with another
 $\alpha^j_i$ and $\beta^j_i$  are nonnegative weights selected  according to the
 relative importance of satisfying the associated level of coverage. For example,
 weights associated with  coverage intervals of a specified part  of a region may
 be  given by a  relatively larger  magnitude than  weights associated  with another

-region. This  kind of integer program  is inspired from the  model developed for
+region. This  kind of mixed-integer program  is inspired from the  model developed for

 brachytherapy treatment planning  for optimizing dose  distribution
 brachytherapy treatment planning  for optimizing dose  distribution

-\citep{0031-9155-44-1-012}. The integer  program must be solved by  the leader in
+\citep{0031-9155-44-1-012}.  The choice of variables $\alpha$ and $\beta$ should be made according to the needs of the application. $\alpha$ should be enough large to prevent undercoverage and so to reach the highest possible coverage ratio. $\beta$ should be enough large to prevent overcoverage and so to activate a minimum number of sensors. 
+The mixed-integer  program must be solved by  the leader in

 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 
 only alive  sensors (sensors with enough energy to  be alive during one
 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 
 only alive  sensors (sensors with enough energy to  be alive during one

-sensing phase) are considered in the model.
+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}


@@ -792,8 +801,8 @@ ratio greater than 50\%, we can  see on Figure~\ref{figure8}(b) that the lifetim
 is about twice longer with  PeCO compared to DESK protocol.  The performance
 difference    is    more    obvious   in    Figure~\ref{figure8}(b)    than    in
 Figure~\ref{figure8}(a) because the gain induced  by our protocols increases with
 is about twice longer with  PeCO compared to DESK protocol.  The performance
 difference    is    more    obvious   in    Figure~\ref{figure8}(b)    than    in
 Figure~\ref{figure8}(a) because the gain induced  by our protocols increases with

- time, and the lifetime with a coverage  of 50\% is far  longer than with
-95\%.
+ time, and the lifetime with a coverage  over 50\% is far  longer than with
+95\%. 

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


@@ -827,40 +836,45 @@ not ineffective for the smallest network sizes.
 \end{figure} 
 
 
 \end{figure} 
 
 

+\subsubsection{\bf Impact of $\alpha$ and $\beta$ on PeCO's performance}
+Table~\ref{my-labelx} shows network lifetime results for the different values of $\alpha$ and $\beta$, and for a network size equal to 200 sensor nodes. The choice of $\beta \gg \alpha$  prevents the overcoverage, and so limit the activation of a large number of sensors, but as $\alpha$ is  low, some areas may be poorly covered. This explains the results obtained for {\it Lifetime50} with $\beta \gg \alpha$: a large number of periods with low coverage ratio. With $\alpha \gg \beta$, we priviligie the coverage even if some areas may be overcovered, so high coverage ratio is reached, but a large number of sensors are activated to achieve this goal. Therefore network lifetime is reduced. The choice $\alpha=0.6$ and $\beta=0.4$ seems to achieve the best compromise between lifetime and coverage ratio.     
+%As can be seen in Table~\ref{my-labelx},  it is obvious and clear that when $\alpha$ decreased and $\beta$ increased by any step, the network lifetime for $Lifetime_{50}$ increased and the $Lifetime_{95}$ decreased. Therefore, selecting the values of $\alpha$ and $\beta$ depend on the application type used in the sensor nework. In PeCO protocol, $\alpha$ and $\beta$ are chosen based on the largest value of network lifetime for $Lifetime_{95}$.
+
+\begin{table}[h]
+\centering
+\caption{The impact of $\alpha$ and $\beta$ on PeCO's performance}
+\label{my-labelx}
+\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
+{\bf 0.6} & {\bf 0.4} & {\bf 94} & {\bf 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}
 \label{sec:Conclusion and Future Works}
 
 
 
 \section{Conclusion and Future Works}
 \label{sec:Conclusion and Future Works}
 

-In this paper  we have studied the problem of  Perimeter-based Coverage Optimization in
-WSNs. We have designed  a new protocol, called Perimeter-based  Coverage Optimization, which
-schedules nodes'  activities (wake up  and sleep  stages) with the  objective of
-maintaining a  good coverage ratio  while maximizing the network  lifetime. This
-protocol is  applied in a distributed  way in regular subregions  obtained after
-partitioning the area of interest in a preliminary step. It works in periods and
-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
-targets/points to be covered.
-
-
-We  have carried out  several simulations  to  evaluate the  proposed protocol.   The
-simulation  results  show   that  PeCO  is  more   energy-efficient  than  other
-approaches, with respect to lifetime,  coverage ratio, active sensors ratio, and
-energy consumption.
+In this paper  we have studied the problem of  Perimeter-based Coverage Optimization in WSNs. We have designed  a new protocol, called Perimeter-based  Coverage Optimization, which schedules nodes'  activities (wake up  and sleep  stages) with the  objective of maintaining a  good coverage ratio  while maximizing the network  lifetime. This protocol is  applied in a distributed  way in regular subregions  obtained after partitioning the area of interest in a preliminary step. It works in periods and
+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 targets/points to be covered.   

 
 

-We plan to extend our framework so that the schedules are planned for multiple
-sensing periods.

 
 

-We also want  to improve our integer program to  take into account heterogeneous
-sensors  from both  energy  and node  characteristics point of views.
+We have carried out  several simulations  to  evaluate the  proposed protocol. The simulation  results  show   that  PeCO  is  more   energy-efficient  than  other approaches, with respect to lifetime,  coverage ratio, active sensors ratio, and energy consumption. 

 
 

-Finally,  it   would  be   interesting  to  implement   our  protocol   using  a
-sensor-testbed to evaluate it in real world applications.
+We plan to extend our framework so that the schedules are planned for multiple sensing periods. We also want to improve our integer program to  take into account heterogeneous sensors  from both  energy and node characteristics point of views. Finally,  it would  be interesting to implement our protocol using  a sensor-testbed to evaluate it in real world applications.

 
 \bibliographystyle{gENO}
 
 \bibliographystyle{gENO}

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

 
 
 \end{document}
 
 
 \end{document}