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
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 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
\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
\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.}
+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, we describe in details our Perimeter-based Coverage
-Optimization protocol. 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
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, 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
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:
\[
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 the interval $[0,2\pi)$. More precisely, we can see that the points are
+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
from the first intersection point after point~zero, and the maximum level of
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. We
-start with a description of the notations that will be 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, 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;
\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 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
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
-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 \{
\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}
+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 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}
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
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
-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.
-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.
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:
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
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}
