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}
+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}
-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}
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
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 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$
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
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
\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}
\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
-($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$.
-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
-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 :}&\\
-\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}
+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
-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
-\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
-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}
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
\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}
-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}
-\bibliography{biblio}
+\bibliography{biblio} %articleeo
\end{document}
