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
-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, 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
+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.
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:
\[
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
\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.\\
-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 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$
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
\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.
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
\end{figure}
+\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}$.
+
+\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
+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}
\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}
