Ali modification

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

diff --git a/PeCO-EO/articleeo.tex~ b/PeCO-EO/articleeo.tex~
index 96b4465cc70683363758f94036cda1a65c9a3c78..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,7 +196,7 @@ 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
+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
 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


@@ -209,11 +208,11 @@ on perimeter coverage of each sensor. The model involves integer variables to ca
 \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}


@@ -278,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


@@ -336,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$


@@ -357,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


@@ -375,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


@@ -476,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}


@@ -500,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


@@ -525,7 +525,7 @@ 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{equation} 
 \left \{


@@ -534,24 +534,28 @@ Our coverage optimization problem can then be mathematically expressed as follow
 \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\\
 \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\\

-X_{k} \in \{0,1\}, \forall k \in A
+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}


@@ -797,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


@@ -833,7 +837,8 @@ not ineffective for the smallest network sizes.
 
 
 \subsubsection{\bf Impact of $\alpha$ and $\beta$ on PeCO's performance}
 
 
 \subsubsection{\bf Impact of $\alpha$ and $\beta$ on PeCO's performance}

-Table~\ref{my-labelx} explains all possible network lifetime result of the relation between the different values of $\alpha$ and $\beta$, and for a network size equal to 200 sensor nodes. 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}$.
+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
 
 \begin{table}[h]
 \centering


@@ -848,7 +853,7 @@ $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
 0.3 & 0.7 & 134 & 0 \\ \hline
 0.4 & 0.6 & 125 & 0 \\ \hline
 0.5 & 0.5 & 118 & 30 \\ \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
+{\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
 0.7 & 0.3 & 97 & 49 \\ \hline
 0.8 & 0.2 & 90 & 52 \\ \hline
 0.9 & 0.1 & 77 & 50 \\ \hline