\begin{abstract}
The most important problem in a Wireless Sensor Network (WSN) is to optimize the
-use of its limited energy provision, so that it can fulfill its monitoring task
-as long as possible. Among known available approaches that can be used to
+use of its limited energy provision, so that it can fulfill its monitoring task
+as long as possible. Among known available approaches that can be used to
improve power management, lifetime coverage optimization provides activity
scheduling which ensures sensing coverage while minimizing the energy cost. In
this paper, we propose such an approach called Perimeter-based Coverage Optimization
-protocol (PeCO). It is a hybrid of centralized and distributed methods: the
+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
distributed among sensor nodes in each subregion.
% A sensor node which runs LiCO protocol repeats periodically four stages:
%More precisely, the scheduling of nodes' activities (sleep/wake up duty cycles)
%is achieved in each subregion by a leader selected after cooperation between
%nodes within the same subregion.
-The novelty of our approach lies essentially in the formulation of a new
-mathematical optimization model based on perimeter coverage level to schedule
+The novelty of our approach lies essentially in the formulation of a new
+mathematical optimization model based on the perimeter coverage level to schedule
sensors' activities. Extensive simulation experiments have been performed using
-OMNeT++, the discrete event simulator, to demonstrate that PeCO is capable to
+OMNeT++, the discrete event simulator, to demonstrate that PeCO can
offer longer lifetime coverage for WSNs in comparison with some other protocols.
\end{abstract}
% Note that keywords are not normally used for peerreview papers.
\begin{IEEEkeywords}
-Wireless Sensor Networks, Area Coverage, Network lifetime, Optimization, Scheduling.
+Wireless Sensor Networks, Area Coverage, Network Lifetime, Optimization, Scheduling.
\end{IEEEkeywords}
\IEEEpeerreviewmaketitle
communication is supplied by a power supply which is a battery. This battery has
a limited energy provision and it may be unsuitable or impossible to replace or
recharge it in most applications. Therefore it is necessary to deploy WSN with
-high density in order to increase the reliability and to exploit node redundancy
+high density in order to increase reliability and to exploit node redundancy
thanks to energy-efficient activity scheduling approaches. Indeed, the overlap
of sensing areas can be exploited to schedule alternatively some sensors in a
low power sleep mode and thus save energy. Overall, the main question that must
be answered is: how to extend the lifetime coverage of a WSN as long as possible
-while ensuring a high level of coverage? So, this last years many
+while ensuring a high level of coverage? These past few years many
energy-efficient mechanisms have been suggested to retain energy and extend the
lifetime of the WSNs~\cite{rault2014energy}.
\item We have devised a framework to schedule nodes to be activated alternatively such
that the network lifetime is prolonged while ensuring that a certain level of
coverage is preserved. A key idea in our framework is to exploit spatial and
- temporal subdivision. On the one hand, the area of interest if divided into
+ temporal subdivision. On the one hand, the area of interest is divided into
several smaller subregions and, on the other hand, the time line is divided into
periods of equal length. In each subregion the sensor nodes will cooperatively
choose a leader which will schedule nodes' activities, and this grouping of
to the objective of coverage for a finite number of discrete points called
targets, and barrier coverage~\cite{HeShibo}\cite{kim2013maximum} focuses on
preventing intruders from entering into the region of interest. In
-\cite{Deng2012} authors transform the area coverage problem to the target
+\cite{Deng2012} authors transform the area coverage problem into the target
coverage one taking into account the intersection points among disks of sensors
nodes or between disk of sensor nodes and boundaries. In
\cite{Huang:2003:CPW:941350.941367} authors prove that if the perimeters of
main interest of such an approach is to avoid long range communications and thus
to reduce the energy dedicated to the communications. Unfortunately, since each
node has only information on its immediate neighbors (usually the one-hop ones)
-it may take a bad decision leading to a global suboptimal solution. Conversely,
+it may make a bad decision leading to a global suboptimal solution. Conversely,
centralized
algorithms~\cite{cardei2005improving,zorbas2010solving,pujari2011high} always
provide nearly or close to optimal solution since the algorithm has a global
view of the whole network. The disadvantage of a centralized method is obviously
its high cost in communications needed to transmit to a single node, the base
station which will globally schedule nodes' activities, data from all the other
-sensor nodes in the area. The price in communications can be very huge since
+sensor nodes in the area. The price in communications can be huge since
long range communications will be needed. In fact the larger the WNS is, the
higher the communication and thus the energy cost are. {\it In order to be
suitable for large-scale networks, in the PeCO protocol, the area of interest
period. Thus our protocol is scalable and is a globally distributed method,
whereas it is centralized in each subregion.}
-Various coverage scheduling algorithms have been developed this last years.
+Various coverage scheduling algorithms have been developed these past few years.
Many of them, dealing with the maximization of the number of cover sets, are
heuristics. These heuristics involve the construction of a cover set by
including in priority the sensor nodes which cover critical targets, that is to
\section{ The PeCO Protocol Description}
\label{sec:The PeCO Protocol Description}
-\noindent In this section, we describe in details our Lifetime Coverage
+\noindent 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
deployed in high density to ensure initially a high coverage ratio of the area
of interest. We assume that all the sensor nodes are homogeneous in terms of
communication, sensing, and processing capabilities and heterogeneous from
-energy provision point of view. The location information is available to a
+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
within a disk centered at a sensor with a radius equal to the sensing range are
said to be covered by this sensor. We also assume that the communication range
$R_c$ satisfies $R_c \geq 2 \cdot R_s$. In fact, Zhang and Zhou~\cite{Zhang05}
-proved that if the transmission range fulfills the previous hypothesis, a
+proved that if the transmission range fulfills the previous hypothesis, the
complete coverage of a convex area implies connectivity among active nodes.
The PeCO protocol uses the same perimeter-coverage model as Huang and
Figure~\ref{pcm2sensors}(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
its perimeter (the perimeter of the disk covered by the sensor) for each
-neighbor the two points resulting from intersection of the two sensing
+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
-for left and right from neighbor point of view. The resulting couples of
+for left and right from a neighboing point of view. The resulting couples of
intersection points subdivide the perimeter of sensor~$0$ into portions called
arcs.
%The optimization algorithm that used by PeCO protocol based on the perimeter coverage levels of the left and right points of the segments and worked to minimize the number of sensor nodes for each left or right point of the segments within each sensor node. The algorithm minimize the perimeter coverage level of the left and right points of the segments, while, it assures that every perimeter coverage level of the left and right points of the segments greater than or equal to 1.
-In the PeCO protocol, scheduling of 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
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
\end{algorithm}
In this algorithm, K.CurrentSize and K.PreviousSize respectively represent the
-current number and the previous number of alive nodes in the subnetwork of the
+current number and the previous number of living nodes in the subnetwork of the
subregion. Initially, the sensor node checks its remaining energy $RE_k$, which
must be greater than a threshold $E_{th}$ in order to participate in the current
period. Each sensor node determines its position and its subregion using an
collect position coordinates, remaining energy, sensor node ID, and the number
of their one-hop live neighbors during the information exchange. The sensors
inside a same region cooperate to elect a leader. The selection criteria for the
-leader, in order of priority, are: larger number of neighbors, larger remaining
+leader, in order of priority, are: larger numbers of neighbors, larger remaining
energy, and then in case of equality, larger index. Once chosen, the leader
collects information to formulate and solve the integer program which allows to
construct the set of active sensors in the sensing stage.
% The leader has the responsibility of applying the integer program algorithm (see section~\ref{cp}), which provides a set of sensors planned to be active in the sensing stage. As leader, it will send an Active-Sleep packet to each sensor in the same subregion to inform it if it has to be active or not. On the contrary, if the sensor is not the leader, it will wait for the Active-Sleep packet to know its state for the sensing stage.
-\section{Lifetime Coverage problem formulation}
+\section{Perimeter-based Coverage Problem Formulation}
\label{cp}
\noindent In this section, the coverage model is mathematically formulated. We
-start with a description of the notations that will be used throughout the
+start with a description of the notations that will be used throughout the
section.
First, we have the following sets:
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
-brachytherapy treatment planning for optimizing dose distribution
+brachytherapy treatment planning for optimizing dose distribution
\cite{0031-9155-44-1-012}. The 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
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 for
+network coverage and a longer WSN lifetime. We have given a higher priority 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 given a little bit lower value for
-$\beta^j_i$ so as to minimize the number of active sensor nodes which contribute
+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
in covering the interval.
We introduce the following performance metrics to evaluate the efficiency of our
points in the sensing field. In our simulations we have set a layout of
$N~=~51~\times~26~=~1326$~grid points.
\item {\bf Active Sensors Ratio (ASR)}: a major objective of our protocol is to
- activate nodes as few as possible, in order to minimize the communication
+ 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
follows:
\begin{equation*}
In order to assess and analyze the performance of our protocol we have
implemented PeCO protocol in OMNeT++~\cite{varga} simulator. Besides PeCO, two
other protocols, described in the next paragraph, will be evaluated for
-comparison purposes. The simulations were run on a laptop DELL with an Intel
+comparison purposes. The simulations were run on a DELL laptop with an Intel
Core~i3~2370~M (2.4~GHz) processor (2 cores) whose MIPS (Million Instructions
Per Second) rate is equal to 35330. To be consistent with the use of a sensor
node based on Atmels AVR ATmega103L microcontroller (6~MHz) having a MIPS rate
optimization solver GLPK (GNU linear Programming Kit available in the public
domain) \cite{glpk} through a Branch-and-Bound method.
-As said previously, the PeCO is compared with three other approaches. The first
+As said previously, the PeCO is compared to three other approaches. The first
one, called DESK, is a fully distributed coverage algorithm proposed by
\cite{ChinhVu}. The second one, called GAF~\cite{xu2001geography}, consists in
dividing the monitoring area into fixed squares. Then, during the decision
phase. The last one, the DiLCO protocol~\cite{Idrees2}, is an improved version
of a research work we presented in~\cite{idrees2014coverage}. Let us notice that
PeCO and DiLCO protocols are based on the same framework. In particular, the
-choice for the simulations of a partitioning in 16~subregions was chosen because
-it corresponds to the configuration producing the better results for DiLCO. The
+choice for the simulations of a partitioning in 16~subregions was made because
+it corresponds to the configuration producing the best results for DiLCO. The
protocols are distinguished from one another by the formulation of the integer
program providing the set of sensors which have to be activated in each sensing
phase. DiLCO protocol tries to satisfy the coverage of a set of primary points,
-whereas PeCO protocol objective is to reach a desired level of coverage for each
+whereas the PeCO protocol objective is to reach a desired level of coverage for each
sensor perimeter. In our experimentations, we chose a level of coverage equal to
one ($l=1$).
\subsubsection{\bf Coverage Ratio}
Figure~\ref{fig333} shows the average coverage ratio for 200 deployed nodes
-obtained with the four protocols. DESK, GAF, and DiLCO provide a little better
-coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, against 98.76\%
+obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better
+coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, compared to the 98.76\%
produced by PeCO for the first periods. This is due to the fact that at the
-beginning DiLCO protocol puts in sleep status more redundant sensors (which
+beginning the DiLCO protocol puts to sleep status more redundant sensors (which
slightly decreases the coverage ratio), while the three other protocols activate
more sensor nodes. Later, when the number of periods is beyond~70, it clearly
appears that PeCO provides a better coverage ratio and keeps a coverage ratio
\subsubsection{\bf Active Sensors Ratio}
Having the less active sensor nodes in each period is essential to minimize the
-energy consumption and so maximize the network lifetime. Figure~\ref{fig444}
+energy consumption and thus to maximize the network lifetime. Figure~\ref{fig444}
shows the average active nodes ratio for 200 deployed nodes. We observe that
DESK and GAF have 30.36 \% and 34.96 \% active nodes for the first fourteen
rounds and DiLCO and PeCO protocols compete perfectly with only 17.92 \% and
\subsubsection{\bf Energy Consumption}
-We study the effect of the energy consumed by the WSN during the communication,
+We studied the effect of the energy consumed by the WSN during the communication,
computation, listening, active, and sleep status for different network densities
-and compare it for the four approaches. Figures~\ref{fig3EC}(a) and (b)
+and compared it for the four approaches. Figures~\ref{fig3EC}(a) and (b)
illustrate the energy consumption for different network sizes and for
$Lifetime95$ and $Lifetime50$. The results show that our PeCO protocol is the
most competitive from the energy consumption point of view. As shown in both
\subsubsection{\bf Network Lifetime}
-We observe the superiority of PeCO and DiLCO protocols in comparison against the
+We observe the superiority of PeCO and DiLCO protocols in comparison with the
two other approaches in prolonging the network lifetime. In
Figures~\ref{fig3LT}(a) and (b), $Lifetime95$ and $Lifetime50$ are shown for
different network sizes. As highlighted by these figures, the lifetime
-increases with the size of the network, and it is clearly the larger for DiLCO
+increases with the size of the network, and it is clearly largest for DiLCO
and PeCO protocols. For instance, for a network of 300~sensors and coverage
ratio greater than 50\%, we can see on Figure~\ref{fig3LT}(b) that the lifetime
is about twice longer with PeCO compared to DESK protocol. The performance
difference is more obvious in Figure~\ref{fig3LT}(b) than in
Figure~\ref{fig3LT}(a) because the gain induced by our protocols increases with
-the time, and the lifetime with a coverage of 50\% is far more longer than with
+ time, and the lifetime with a coverage of 50\% is far longer than with
95\%.
\begin{figure}[h!]
different coverage ratios. We denote by Protocol/50, Protocol/80, Protocol/85,
Protocol/90, and Protocol/95 the amount of time during which the network can
satisfy an area coverage greater than $50\%$, $80\%$, $85\%$, $90\%$, and $95\%$
-respectively, where Protocol is DiLCO or PeCO. Indeed there are applications
+respectively, where the term Protocol refers to DiLCO or PeCO. Indeed there are applications
that do not require a 100\% coverage of the area to be monitored. PeCO might be
an interesting method since it achieves a good balance between a high level
coverage ratio and network lifetime. PeCO always outperforms DiLCO for the three
lower coverage ratios, moreover the improvements grow with the network
size. DiLCO is better for coverage ratios near 100\%, but in that case PeCO is
-not so bad for the smallest network sizes.
+not ineffective for the smallest network sizes.
\begin{figure}[h!]
\centering \includegraphics[scale=0.5]{R/LTa.eps}
\section{Conclusion and Future Works}
\label{sec:Conclusion and Future Works}
-In this paper we have studied the problem of lifetime coverage optimization in
-WSNs. We have designed a new protocol, called Lifetime Coverage Optimization, which
+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
approaches, with respect to lifetime, coverage ratio, active sensors ratio, and
energy consumption.
%Indeed, when dealing with large and dense WSNs, a distributed optimization approach on the subregions of WSN like the one we are proposed allows to reduce the difficulty of a single global optimization problem by partitioning it in many smaller problems, one per subregion, that can be solved more easily. We have identified different research directions that arise out of the work presented here.
-We plan to extend our framework such that the schedules are planned for multiple
+We plan to extend our framework so that the schedules are planned for multiple
sensing periods.
%in order to compute all active sensor schedules in only one step for many periods;
We also want to improve our integer program to take into account heterogeneous
\section*{Acknowledgments}
-\noindent As a Ph.D. student, Ali Kadhum IDREES would like to gratefully
+\noindent As a Ph.D. student, Ali Kadhum IDREES would like to gratefully
acknowledge the University of Babylon - IRAQ for financial support and Campus
France for the received support. This work is also partially funded by the Labex ACTION program (contract ANR-11-LABX-01-01).
