\indent The fast developments of low-cost sensor devices and wireless
communications have allowed the emergence of WSNs. A WSN includes a large number
-of small, limited-power sensors that can sense, process and transmit data over a
-wireless communication. They communicate with each other by using multi-hop
+of small, limited-power sensors that can sense, process, and transmit data over
+a wireless communication. They communicate with each other by using multi-hop
wireless communications and cooperate together to monitor the area of interest,
so that each measured data can be reported to a monitoring center called sink
-for further analysis~\cite{Sudip03}. There are several fields of application
+for further analysis~\cite{Sudip03}. There are several fields of application
covering a wide spectrum for a WSN, including health, home, environmental,
military, and industrial applications~\cite{Akyildiz02}.
On the one hand sensor nodes run on batteries with limited capacities, and it is
-often costly or simply impossible to replace and/or recharge batteries,
+often costly or simply impossible to replace and/or recharge batteries,
especially in remote and hostile environments. Obviously, to achieve a long life
-of the network it is important to conserve battery power. Therefore, lifetime
+of the network it is important to conserve battery power. Therefore, lifetime
optimization is one of the most critical issues in wireless sensor networks. On
-the other hand we must guarantee coverage over the area of interest. To fulfill
-these two objectives, the main idea is to take advantage of overlapping sensing
+the other hand we must guarantee coverage over the area of interest. To fulfill
+these two objectives, the main idea is to take advantage of overlapping sensing
regions to turn-off redundant sensor nodes and thus save energy. In this paper,
-we concentrate on the area coverage problem, with the objective of maximizing
-the network lifetime by using an optimized multirounds scheduling.
+we concentrate on the area coverage problem, with the objective of maximizing
+the network lifetime by using an optimized multiround scheduling.
% One of the major scientific research challenges in WSNs, which are addressed by a large number of literature during the last few years is to design energy efficient approaches for coverage and connectivity in WSNs~\cite{conti2014mobile}. The coverage problem is one of the
%fundamental challenges in WSNs~\cite{Nayak04} that consists in monitoring efficiently and continuously
\item The homogeneous or heterogeneous nature of the nodes, in terms of sensing
or communication capabilities.
\item The node deployment method, which may be random or deterministic.
-\item Additional requirements for energy-efficient coverage and connected
- coverage.
+\item Additional requirements for energy-efficient and connected coverage.
\end{itemize}
The choice of non-disjoint or disjoint cover sets (sensors participate or not in
many cover sets) can be added to the above list.
% The independency in the cover set (i.e. whether the cover sets are disjoint or non-disjoint) \cite{zorbas2010solving} is another design choice that can be added to the above list.
-\subsection{Centralized Approaches}
+\subsection{Centralized approaches}
+
The major approach is to divide/organize the sensors into a suitable number of
set covers where each set completely covers an interest region and to activate
these set covers successively. The centralized algorithms always provide nearly
size increases.
The first algorithms proposed in the literature consider that the cover sets are
-disjoint: a sensor node appears in exactly one of the generated cover sets~\cite{abrams2004set,cardei2005improving,Slijepcevic01powerefficient}.
-
-
-In the case of non-disjoint algorithms \cite{pujari2011high}, sensors may
+disjoint: a sensor node appears in exactly one of the generated cover
+sets~\cite{abrams2004set,cardei2005improving,Slijepcevic01powerefficient}. In
+the case of non-disjoint algorithms \cite{pujari2011high}, sensors may
participate in more than one cover set. In some cases, this may prolong the
lifetime of the network in comparison to the disjoint cover set algorithms, but
designing algorithms for non-disjoint cover sets generally induces a higher
order of complexity. Moreover, in case of a sensor's failure, non-disjoint
-scheduling policies are less resilient and less reliable because a sensor may be
-involved in more than one cover sets. For instance, the proposed work in ~\cite{cardei2005energy, berman04}
-
+scheduling policies are less resilient and reliable because a sensor may be
+involved in more than one cover sets.
+%For instance, the proposed work in ~\cite{cardei2005energy, berman04}
-
-
-In~\cite{yang2014maximum}, the authors have proposed a linear programming
+In~\cite{yang2014maximum}, the authors have considered a linear programming
approach for selecting the minimum number of working sensor nodes, in order to
-as to preserve a maximum coverage and extend lifetime of the network. Cheng et
+preserve a maximum coverage and extend lifetime of the network. Cheng et
al.~\cite{cheng2014energy} have defined a heuristic algorithm called Cover Sets
Balance (CSB), which choose a set of active nodes using the tuple (data coverage
range, residual energy). Then, they have introduced a new Correlated Node Set
lifetime. Various centralized methods based on column generation approaches have
also been proposed~\cite{castano2013column,rossi2012exact,deschinkel2012column}.
-
-
-
-
\subsection{Distributed approaches}
%{\bf Distributed approaches}
In distributed and localized coverage algorithms, the required computation to
WSNs. Localized and distributed algorithms generally result in non-disjoint set
covers.
-Some distributed algorithms have been developed
-in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02, yardibi2010distributed, prasad2007distributed,Misra}
-to perform the scheduling so as to preserve coverage. Distributed algorithms
-typically operate in rounds for a predetermined duration. At the beginning of
-each round, a sensor exchanges information with its neighbors and makes a
-decision to either remain turned on or to go to sleep for the round. This
-decision is basically made on simple greedy criteria like the largest uncovered
-area \cite{Berman05efficientenergy} or maximum uncovered targets
-\cite{lu2003coverage}. The authors in \cite{yardibi2010distributed} have developed a Distributed
-Adaptive Sleep Scheduling Algorithm (DASSA) for WSNs with partial coverage.
-DASSA does not require location information of sensors while maintaining
-connectivity and satisfying a user defined coverage target. In DASSA, nodes use
-the residual energy levels and feedback from the sink for scheduling the
-activity of their neighbors. This feedback mechanism reduces the randomness in
-scheduling that would otherwise occur due to the absence of location
-information. In \cite{ChinhVu}, the author have proposed a novel distributed
-heuristic, called Distributed Energy-efficient Scheduling for k-coverage (DESK),
-which ensures that the energy consumption among the sensors is balanced and the
-lifetime maximized while the coverage requirement is maintained. This heuristic
-works in rounds, requires only one-hop neighbor information, and each sensor
-decides its status (active or sleep) based on the perimeter coverage model
-proposed in \cite{Huang:2003:CPW:941350.941367}.
+Many distributed algorithms have been developed to perform the scheduling so as
+to preserve coverage, see for example
+\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02, yardibi2010distributed,
+ prasad2007distributed,Misra}. Distributed algorithms typically operate in
+rounds for a predetermined duration. At the beginning of each round, a sensor
+exchanges information with its neighbors and makes a decision to either remain
+turned on or to go to sleep for the round. This decision is basically made on
+simple greedy criteria like the largest uncovered area
+\cite{Berman05efficientenergy} or maximum uncovered targets
+\cite{lu2003coverage}. The Distributed Adaptive Sleep Scheduling Algorithm
+(DASSA) \cite{yardibi2010distributed} does not require location information of
+sensors while maintaining connectivity and satisfying a user defined coverage
+target. In DASSA, nodes use the residual energy levels and feedback from the
+sink for scheduling the activity of their neighbors. This feedback mechanism
+reduces the randomness in scheduling that would otherwise occur due to the
+absence of location information. In \cite{ChinhVu}, the author have designed a
+novel distributed heuristic, called Distributed Energy-efficient Scheduling for
+k-coverage (DESK), which ensures that the energy consumption among the sensors
+is balanced and the lifetime maximized while the coverage requirement is
+maintained. This heuristic works in rounds, requires only one-hop neighbor
+information, and each sensor decides its status (active or sleep) based on the
+perimeter coverage model from~\cite{Huang:2003:CPW:941350.941367}.
%Our Work, which is presented in~\cite{idrees2014coverage} proposed a coverage optimization protocol to improve the lifetime in
%heterogeneous energy wireless sensor networks.
The works presented in \cite{Bang, Zhixin, Zhang} focuses on coverage-aware,
distributed energy-efficient, and distributed clustering methods respectively,
-which aims to extend the network lifetime, while the coverage is ensured. More recently, Shibo et al. \cite{Shibo} have expressed the coverage
-problem as a minimum weight submodular set cover problem and proposed a
-Distributed Truncated Greedy Algorithm (DTGA) to solve it. They take advantage
-from both temporal and spatial correlations between data sensed by different
-sensors, and leverage prediction, to improve the lifetime. In
-\cite{xu2001geography}, Xu et al. have proposed an algorithm, called
-Geographical Adaptive Fidelity (GAF), which uses geographic location information
-to divide the area of interest into fixed square grids. Within each grid, it
-keeps only one node staying awake to take the responsibility of sensing and
-communication.
+which aims to extend the network lifetime, while the coverage is ensured. More
+recently, Shibo et al. \cite{Shibo} have expressed the coverage problem as a
+minimum weight submodular set cover problem and proposed a Distributed Truncated
+Greedy Algorithm (DTGA) to solve it. They take advantage from both temporal and
+spatial correlations between data sensed by different sensors, and leverage
+prediction, to improve the lifetime. In \cite{xu2001geography}, Xu et al. have
+described an algorithm, called Geographical Adaptive Fidelity (GAF), which uses
+geographic location information to divide the area of interest into fixed square
+grids. Within each grid, it keeps only one node staying awake to take the
+responsibility of sensing and communication.
Some other approaches (outside the scope of our work) do not consider a
synchronized and predetermined period of time where the sensors are active or
not. Indeed, each sensor maintains its own timer and its wake-up time is
randomized \cite{Ye03} or regulated \cite{cardei2005maximum} over time.
-The MuDiLCO protocol (for Multiround Distributed Lifetime Coverage Optimization
+The MuDiLCO protocol (for Multiround Distributed Lifetime Coverage Optimization
protocol) presented in this paper is an extension of the approach introduced
in~\cite{idrees2014coverage}. In~\cite{idrees2014coverage}, the protocol is
deployed over only two subregions. Simulation results have shown that it was
computation complexity. Compared to our previous paper, in this one we study the
possibility of dividing the sensing phase into multiple rounds and we also add
an improved model of energy consumption to assess the efficiency of our
-approach.
-
-
-
-
+approach. In fact, in this paper we make a multiround optimization, while it was
+a single round optimization in our previous work.
\iffalse
lifetime. Various centralized methods based on column generation approaches have
also been proposed~\cite{castano2013column,rossi2012exact,deschinkel2012column}.
-
-
\subsection{Distributed approaches}
%{\bf Distributed approaches}
In distributed and localized coverage algorithms, the required computation to
WSNs. Localized and distributed algorithms generally result in non-disjoint set
covers.
-Some distributed algorithms have been developed
-in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02, yardibi2010distributed}
-to perform the scheduling so as to preserve coverage. Distributed algorithms
-typically operate in rounds for a predetermined duration. At the beginning of
-each round, a sensor exchanges information with its neighbors and makes a
-decision to either remain turned on or to go to sleep for the round. This
-decision is basically made on simple greedy criteria like the largest uncovered
-area \cite{Berman05efficientenergy} or maximum uncovered targets
-\cite{lu2003coverage}. In \cite{Tian02}, the scheduling scheme is divided into
-rounds, where each round has a self-scheduling phase followed by a sensing
-phase. Each sensor broadcasts a message containing the node~ID and the node
-location to its neighbors at the beginning of each round. A sensor determines
-its status by a rule named off-duty eligible rule, which tells him to turn off
-if its sensing area is covered by its neighbors. A back-off scheme is introduced
-to let each sensor delay the decision process with a random period of time, in
-order to avoid simultaneous conflicting decisions between nodes and lack of
-coverage on any area. In \cite{prasad2007distributed} a model for capturing the
-dependencies between different cover sets is defined and it proposes localized
-heuristic based on this dependency. The algorithm consists of two phases, an
-initial setup phase during which each sensor computes and prioritizes the covers
-and a sensing phase during which each sensor first decides its on/off status,
-and then remains on or off for the rest of the duration.
+Many distributed algorithms have been developed to perform the scheduling so as
+to preserve coverage, see for example
+\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02,yardibi2010distributed}.
+Distributed algorithms typically operate in rounds for a predetermined
+duration. At the beginning of each round, a sensor exchanges information with
+its neighbors and makes a decision to either remain turned on or to go to sleep
+for the round. This decision is basically made on simple greedy criteria like
+the largest uncovered area \cite{Berman05efficientenergy} or maximum uncovered
+targets \cite{lu2003coverage}. In \cite{Tian02}, the scheduling scheme is
+divided into rounds, where each round has a self-scheduling phase followed by a
+sensing phase. Each sensor broadcasts a message containing the node~ID and the
+node location to its neighbors at the beginning of each round. A sensor
+determines its status by a rule named off-duty eligible rule, which tells him to
+turn off if its sensing area is covered by its neighbors. A back-off scheme is
+introduced to let each sensor delay the decision process with a random period of
+time, in order to avoid simultaneous conflicting decisions between nodes and
+lack of coverage on any area. In \cite{prasad2007distributed} a model for
+capturing the dependencies between different cover sets is defined and it
+proposes localized heuristic based on this dependency. The algorithm consists of
+two phases, an initial setup phase during which each sensor computes and
+prioritizes the covers and a sensing phase during which each sensor first
+decides its on/off status, and then remains on or off for the rest of the
+duration.
The authors in \cite{yardibi2010distributed} have developed a Distributed
Adaptive Sleep Scheduling Algorithm (DASSA) for WSNs with partial coverage.
communication range satisfies $R_c \geq 2R_s$. In fact, Zhang and
Zhou~\cite{Zhang05} proved that if the transmission range fulfills the previous
hypothesis, a complete coverage of a convex area implies connectivity among the
-working nodes in the active mode.
+active nodes.
Instead of working with a continuous coverage area, we make it discrete by
considering for each sensor a set of points called primary points. Consequently,
As can be seen in Figure~\ref{fig2}, our protocol works in periods fashion,
where each is divided into 4 phases: Information~Exchange, Leader~Election,
Decision, and Sensing. Each sensing phase may be itself divided into $T$ rounds
-and for each round a set of sensors (said a cover set) is responsible for the
-sensing task. A multiround optimization process executed in each period after information exchange and leader election in order to produce a $T$ cover sets of sensors to take the mission of sensing for $T$ rounds.
+and for each round a set of sensors (a cover set) is responsible for the sensing
+task. In this way a multiround optimization process is performed during each
+period after Information~Exchange and Leader~Election phases, in order to
+produce $T$ cover sets that will take the mission of sensing for $T$ rounds.
\begin{figure}[ht!]
\centering \includegraphics[width=100mm]{Modelgeneral.pdf} % 70mm
\caption{The MuDiLCO protocol scheme executed on each node}
$E_{R}$ & 36 Joules\\
$R_s$ & 5~m \\
%\hline
-$w_{\Theta}$ & 1 \\
+$W_{\Theta}$ & 1 \\
% [1ex] adds vertical space
%\hline
-$w_{U}$ & $|P^2|$
+$W_{U}$ & $|P|^2$
%inserts single line
\end{tabular}
\label{table3}
the benefit from the optimization and the execution time needed to solve
it. Therefore, we have set the number of subregions to 16 rather than 32.
-\subsection{Energy Model}
+\subsection{Energy model}
We use an energy consumption model proposed by~\cite{ChinhVu} and based on
\cite{raghunathan2002energy} with slight modifications. The energy consumption
\end{enumerate}
-
\section{Results and analysis}
\subsection{Coverage ratio}
saves more energy, with less dead nodes, at most for several rounds, and thus
should extend the network lifetime.
-\begin{figure}[t!]
+\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5] {R1/CR.pdf}
\caption{Average coverage ratio for 150 deployed nodes}
activated many nodes at the beginning. Anyway, MuDiLCO-T activates the available
nodes in a more efficient manner.
-\begin{figure}[t!]
+\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{R1/ASR.pdf}
\caption{Active sensors ratio for 150 deployed nodes}
%%% The optimization effectively continues as long as a network in a subregion is still connected. A VOIR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{figure}[t!]
+\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{R1/SR.pdf}
\caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes }
\label{fig6}
\end{figure}
-\subsection{Energy Consumption} \label{subsec:EC}
+\subsection{Energy consumption} \label{subsec:EC}
We measure the energy consumed by the sensors during the communication,
listening, computation, active, and sleep status for different network densities
\frac{35330}{2} \times \frac{1}{6} \right)$ and reported on Figure~\ref{fig77}
for different network sizes.
-\begin{figure}[t!]
+\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{R1/T.pdf}
\caption{Execution Time (in seconds)}
%While MuDiLCO-1, 3, and 5 solves the optimization process with suitable execution times to be used on wireless sensor network because it distributed on larger number of small subregions as well as it is used acceptable number of round(s) T. We think that in distributed fashion the solving of the optimization problem to produce T rounds in a subregion can be tackled by sensor nodes. Overall, to be able to deal with very large networks, a distributed method is clearly required.
-\subsection{Network Lifetime}
+\subsection{Network lifetime}
The next two figures, Figures~\ref{fig8}(a) and \ref{fig8}(b), illustrate the
network lifetime for different network sizes, respectively for $Lifetime_{95}$
MuDiLCO-T protocol maximizes the lifetime of the network. In particular the
gain in lifetime for a coverage over 95\% is greater than 38\% when switching
from GAF to MuDiLCO-3. The slight decrease that can bee observed for MuDiLCO-7
-in case of $Lifetime_{95}$ with large wireless sensor networks result from the
+in case of $Lifetime_{95}$ with large wireless sensor networks results from the
difficulty of the optimization problem to be solved by the integer program.
This point was already noticed in subsection \ref{subsec:EC} devoted to the
energy consumption, since network lifetime and energy consumption are directly
%We see that our MuDiLCO-7 protocol results in execution times that quickly become unsuitable for a sensor network as well as the energy consumption seems to be huge because it used a larger number of rounds T during performing the optimization decision in the subregions, which is led to decrease the network lifetime. On the other side, our MuDiLCO-1, 3, and 5 protocol seems to be more efficient in comparison with other approaches because they are prolonged the lifetime of the network more than DESK and GAF.
-\section{Conclusion and Future Works}
+\section{Conclusion and future works}
\label{sec:conclusion}
-In this paper, we have addressed the problem of the coverage and the lifetime
-optimization in wireless sensor networks. This is a key issue as sensor nodes
-have limited resources in terms of memory, energy, and computational power. To
-cope with this problem, the field of sensing is divided into smaller subregions
-using the concept of divide-and-conquer method, and then we propose a protocol
-which optimizes coverage and lifetime performances in each subregion. Our
-protocol, called MuDiLCO (Multiround Distributed Lifetime Coverage
-Optimization) combines two efficient techniques: network leader election and
-sensor activity scheduling.
+We have addressed the problem of the coverage and the lifetime optimization in
+wireless sensor networks. This is a key issue as sensor nodes have limited
+resources in terms of memory, energy, and computational power. To cope with this
+problem, the field of sensing is divided into smaller subregions using the
+concept of divide-and-conquer method, and then we propose a protocol which
+optimizes coverage and lifetime performances in each subregion. Our protocol,
+called MuDiLCO (Multiround Distributed Lifetime Coverage Optimization) combines
+two efficient techniques: network leader election and sensor activity
+scheduling.
%, where the challenges
%include how to select the most efficient leader in each subregion and
%the best cover sets %of active nodes that will optimize the network lifetime
