%% for the whole article with \linenumbers.
%% \usepackage{lineno}
-\journal{Ad Hoc Networks}
+\journal{Journal of Supercomputing}
\begin{document}
\author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$, \\ Michel
Salomon$^{a}$, and Rapha\"el Couturier $^{a}$ \\ $^{a}${\em{FEMTO-ST
- Institute, UMR 6174 CNRS, \\ University Bourgogne Franche-Comt\'e,
+ Institute/CNRS, \\ Univ. Bourgogne Franche-Comt\'e,
Belfort, France}} \\ $^{b}${\em{Department of Computer Science, University
of Babylon, Babylon, Iraq}} }
sensor nodes in each subregion. The proposed MuDiLCO protocol works in periods
during which sets of sensor nodes are scheduled, with one set for each round of
a period, to remain active during the sensing phase and thus ensure coverage so
-as to maximize the WSN lifetime. \textcolor{blue}{The decision process is
+as to maximize the WSN lifetime. The decision process is
carried out by a leader node, which solves an optimization problem to produce
the best representative sets to be used during the rounds of the sensing
phase. The optimization problem formulated as an integer program is solved to
optimality through a Branch-and-Bound method for small instances. For larger
instances, the best feasible solution found by the solver after a given time
- limit threshold is considered.}
+ limit threshold is considered.
Compared with some existing protocols, simulation results based on multiple
criteria (energy consumption, coverage ratio, and so on) show that the proposed
protocol can prolong efficiently the network lifetime and improve the coverage
we concentrate on the area coverage problem, with the objective of maximizing
the network lifetime by using an optimized multiround scheduling.
+The MuDiLCO protocol (for Multiround Distributed Lifetime Coverage Optimization
+protocol) presented in this paper is an extension of the approach introduced
+in~\cite{idrees2015distributed}.
+% In~\cite{idrees2015distributed}, the protocol is
+%deployed over only two subregions. Simulation results have shown that it was
+%more interesting to divide the area into several subregions, given the
+%computation complexity.
+
+\textcolor{green}{
+ Compared to our previous paper~\cite{idrees2015distributed}, in this one we study the
+possibility of dividing the sensing phase into multiple rounds. In fact, in this paper we make a multiround optimization, while it was
+a single round optimization in our previous work. The idea is
+ to take advantage of the pre-sensing phase to plan the sensor's activity for
+ several rounds instead of one, thus saving energy. In addition, when the
+ optimization problem becomes more complex, its resolution is stopped after a
+ given time threshold. In this paper we also analyse the performance of our protocol according to the number of primary points used (area coverage is replaced by the coverage of a set of particular points called primary points, see section~\ref{pp}).}
+
The remainder of the paper is organized as follows. The next section
reviews the related works in the field. Section~\ref{pd} is devoted to the
description of MuDiLCO protocol. Section~\ref{exp} introduces the experimental
low processing power from the sensor nodes, which usually have limited
processing capabilities. The main drawback of this kind of approach is its
higher cost in communications, since the node that will make the decision needs
-information from all the sensor nodes. \textcolor{blue}{Exact or heuristic
+information from all the sensor nodes. Exact or heuristic
approaches are designed to provide cover sets. Contrary to exact methods,
heuristic ones can handle very large and centralized problems. They are
proposed to reduce computational overhead such as energy consumption, delay,
- and generally allow to increase the network lifetime.}
+ and generally allow to increase the network lifetime.
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
network lifetime. Various centralized methods based on column generation
approaches have also been
proposed~\cite{gentili2013,castano2013column,rossi2012exact,deschinkel2012column}.
-\textcolor{blue}{In~\cite{gentili2013}, authors highlight the trade-off between
+In~\cite{gentili2013}, authors highlight the trade-off between
the network lifetime and the coverage percentage. They show that network
- lifetime can be hugely improved by decreasing the coverage ratio.}
+ lifetime can be hugely improved by decreasing the coverage ratio.
\subsection{Distributed approaches}
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
-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
-more interesting to divide the area into several subregions, given the
-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. In fact, in this paper we make a multiround optimization, while it was
-a single round optimization in our previous work. \textcolor{blue}{The idea is
- to take advantage of the pre-sensing phase to plan the sensor's activity for
- several rounds instead of one, thus saving energy. In addition, when the
- optimization problem becomes more complex, its resolution is stopped after a
- given time threshold}.
-
-
\section{MuDiLCO protocol description}
\label{pd}
-\subsection{Assumptions}
+\subsection{Assumptions and primary points}
+\label{pp}
+\textcolor{green}{Assumptions and coverage model are identical to those presented in~\cite{idrees2015distributed}.}
+
+\iffalse
We consider a randomly and uniformly deployed network consisting of static
wireless sensors. The sensors are deployed in high density to ensure initially
a high coverage ratio of the interested area. We assume that all nodes are
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
-active nodes.
+active nodes.\fi
+
+\textcolor{green}{We consider a scenario where sensors are deployed in high density to ensure initially
+a high coverage ratio of the interested area. Each sensor has a predefined sensing range $R_s$, an initial energy supply (eventually different from each other) and is supposed to be equipped with module for locating its geographical positions. All space points within the disk centered at the sensor with the radius of the sensing
+range is said to be covered by this sensor.}
\indent Instead of working with the coverage area, we consider for each sensor a
set of points called primary points~\cite{idrees2014coverage}. We assume that
\subsection{Background idea}
-\textcolor{blue}{The WSN area of interest is, at first, divided into
+The WSN area of interest is, at first, divided into
regular homogeneous subregions using a divide-and-conquer algorithm. Then, our protocol will be executed in a distributed way in each
subregion simultaneously to schedule nodes' activities for one sensing
period. Sensor nodes are assumed to be deployed almost uniformly and with high
density over the region. The regular subdivision is made so that the number
of hops between any pairs of sensors inside a subregion is less than or equal
- to 3.}
+ to 3.
As can be seen in Figure~\ref{fig2}, our protocol works in periods fashion,
where each period is divided into 4~phases: Information~Exchange,
-Leader~Election, Decision, and Sensing. Each sensing phase may be itself
-divided into $T$ rounds \textcolor{blue} {of equal duration} and for each round
+Leader~Election, Decision, and Sensing. \textcolor{green}{Compared to protocol DiLCO described in~\cite{idrees2015distributed}} each sensing phase is itself
+divided into $T$ rounds of equal duration 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.
+sets that will take the mission of sensing for $T$ rounds. \textcolor{green}{Algorithm~\ref{alg:MuDiLCO} is
+executed by each sensor node~$s_j$ (with enough remaining energy) at the beginning of a period.}
\begin{figure}[t!]
\centering \includegraphics[width=125mm]{Modelgeneral.pdf} % 70mm
\caption{The MuDiLCO protocol scheme executed on each node}
\label{fig2}
\end{figure}
-This protocol minimizes the impact of unexpected node failure (not due to
-batteries running out of energy), because it works in periods.
- On the one hand, if a node failure is detected before making the decision, the
- node will not participate to this phase, and, on the other hand, if the node
- failure occurs after the decision, the sensing task of the network will be
- temporarily affected: only during the period of sensing until a new period
- starts. \textcolor{blue}{The duration of the rounds is a predefined
- parameter. Round duration should be long enough to hide the system control
- overhead and short enough to minimize the negative effects in case of node
- failures.}
-
-The energy consumption and some other constraints can easily be taken into
-account, since the sensors can update and then exchange their information
-(including their residual energy) at the beginning of each period. However, the
-pre-sensing phases (Information Exchange, Leader Election, and Decision) are
-energy consuming for some nodes, even when they do not join the network to
-monitor the area.
-
-We define two types of packets that will be used by the proposed protocol:
+\textcolor{green}{As already described in~\cite{idrees2015distributed}}, two types of packets are used by the proposed protocol:
\begin{enumerate}[(a)]
\item INFO packet: such a packet will be sent by each sensor node to all the
nodes inside a subregion for information exchange.
\item COMMUNICATION: sensor node is transmitting or receiving packet.
\end{enumerate}
-Below, we describe each phase in more details.
-\subsection{Information Exchange Phase}
-Each sensor node $j$ sends its position, remaining energy $RE_j$, and the number
+
+This protocol minimizes the impact of unexpected node failure (not due to
+batteries running out of energy), because it works in periods.
+ On the one hand, if a node failure is detected before making the decision, the
+ node will not participate to this phase, and, on the other hand, if the node
+ failure occurs after the decision, the sensing task of the network will be
+ temporarily affected: only during the period of sensing until a new period
+ starts. The duration of the rounds is a predefined
+ parameter. Round duration should be long enough to hide the system control
+ overhead and short enough to minimize the negative effects in case of node
+ failures.
+
+The energy consumption and some other constraints can easily be taken into
+account, since the sensors can update and then exchange their information
+(including their residual energy) at the beginning of each period. However, the
+pre-sensing phases (Information Exchange, Leader Election, and Decision) are
+energy consuming for some nodes, even when they do not join the network to
+monitor the area.
+
+
+
+
+At the beginning of each period, each sensor wich has enough remaining energy ($RE_j$) to be alive during at least one round ( $E_{R}$ is the amount of energy
+required to be alive during one round) sends (line 3 of algorithm~\ref{alg:MuDiLCO}) its position, remaining energy $RE_j$, and the number
of neighbors $NBR_j$ to all wireless sensor nodes in its subregion by using an
INFO packet (containing information on position coordinates, current remaining
energy, sensor node ID, number of its one-hop live neighbors) and then waits for
-packets sent by other nodes. After that, each node will have information about
-all the sensor nodes in the subregion. In our model, the remaining energy
-corresponds to the time that a sensor can live in the active mode.
-
-\subsection{Leader Election phase}
+packets sent by other nodes (line 4).
-This step consists in choosing the Wireless Sensor Node Leader (WSNL), which
-will be responsible for executing the coverage algorithm. Each subregion in the
-area of interest will select its own WSNL independently for each period. All
-the sensor nodes cooperate to elect a WSNL. The nodes in the same subregion
-will select the leader based on the received information from all other nodes in
+After that, each node will have information about
+all the sensor nodes in the subregion.
+ The nodes in the same subregion
+will select (line 5) a Wireless Sensor Node Leader (WSNL) based on the received information from all other nodes in
the same subregion. The selection criteria are, in order of importance: larger
number of neighbors, larger remaining energy, and then in case of equality,
larger index. Observations on previous simulations suggest to use the number of
one-hop neighbors as the primary criterion to reduce energy consumption due to
-the communications.
+the communications.\\
+
+
-\subsection{Decision phase}
-\label{decision}
-Each WSNL will \textcolor{blue}{solve an integer program to select which cover
- sets will be activated in the following sensing phase to cover the subregion
- to which it belongs. $T$ cover sets will be produced, one for each round. The
- WSNL will send an Active-Sleep packet to each sensor in the subregion based on
- the algorithm's results, indicating if the sensor should be active or not in
- each round of the sensing phase.}
+%Each WSNL will solve an integer program to select which cover
+% sets will be activated in the following sensing phase to cover the subregion
+% to which it belongs. $T$ cover sets will be produced, one for each round. The
+% WSNL will send an Active-Sleep packet to each sensor in the subregion based on
+% the algorithm's results, indicating if the sensor should be active or not in
+% each round of the sensing phase.
+\subsection{Multiround Optimization model}
+\label{mom}
+As shown in Algorithm~\ref{alg:MuDiLCO} at line 8, the leader (WNSL) will execute an optimization
+algorithm based on an integer program. to select which cover
+sets will be activated in the following sensing phase to cover the subregion
+to which it belongs. $T$ cover sets will be produced, one for each round. The
+WSNL will send an Active-Sleep packet to each sensor in the subregion based on
+the algorithm's results (line 10), indicating if the sensor should be active or not in
+each round of the sensing phase.
-As shown in Algorithm~\ref{alg:MuDiLCO}, the leader will execute an optimization
-algorithm based on an integer program. The integer program is based on the model
+
+The integer program is based on the model
proposed by \cite{pedraza2006} with some modifications, where the objective is
to find a maximum number of disjoint cover sets. To fulfill this goal, the
authors proposed an integer program which forces undercoverage and overcoverage
sensor $j$ during round $t$ of a given sensing phase. We also consider primary
points as targets. The set of primary points is denoted by $P$ and the set of
sensors by $J$. Only sensors able to be alive during at least one round are
-involved in the integer program.
+involved in the integer program. \textcolor{green}{Note that the proposed integer program is an extension of that formulated in~\cite{idrees2015distributed},
+variables are now indexed in addition with the number of round $t$.}
For a primary point $p$, let $\alpha_{j,p}$ denote the indicator function of
whether the point $p$ is covered, that is:
In our simulations, priority is given to the coverage by choosing $W_{U}$ very
large compared to $W_{\theta}$.
-\textcolor{blue}{The size of the problem depends on the number of variables and
+The size of the problem depends on the number of variables and
constraints. The number of variables is linked to the number of alive sensors
$A \subseteq J$, the number of rounds $T$, and the number of primary points
$P$. Thus the integer program contains $A*T$ variables of type $X_{t,j}$,
$P*T$ overcoverage variables and $P*T$ undercoverage variables. The number of
constraints is equal to $P*T$ (for constraints (\ref{eq16})) $+$ $A$ (for
- constraints (\ref{eq144})).}
+ constraints (\ref{eq144})).
+\iffalse
\subsection{Sensing phase}
The sensing phase consists of $T$ rounds. Each sensor node in the subregion will
sleep for each round of the sensing phase. Algorithm~\ref{alg:MuDiLCO}, which
will be executed by each sensor node~$s_j$ at the beginning of a period,
explains how the Active-Sleep packet is obtained.
+\fi
\begin{algorithm}[h!]
\BlankLine
\label{table3}
\end{table}
-\textcolor{blue}{Our protocol is declined into four versions: MuDiLCO-1,
+Our protocol is declined into four versions: MuDiLCO-1,
MuDiLCO-3, MuDiLCO-5, and MuDiLCO-7, corresponding respectively to $T=1,3,5,7$
($T$ the number of rounds in one sensing period). Since the time resolution
may be prohibitive when the size of the problem increases, a time limit
size. After that, this threshold value is increased if necessary so that the
solver is able to deliver a feasible solution within the time limit. In fact,
selecting the optimal values for the time limits will be investigated in the
- future.}
+ future.
In the following, we will make comparisons with two other methods. The first
method, called DESK and proposed by \cite{ChinhVu}, is a full distributed
network disconnection due to node failures. However, too many subdivisions
reduce the advantage of the optimization. In fact, there is a balance between
the benefit from the optimization and the execution time needed to solve it. In
-the following we have set the number of subregions to 16.
+the following we have set the number of subregions to 16 \textcolor{green}{as recommended in~\cite{idrees2015distributed}}.
+\subsection{Energy model}
+\textcolor{green}{The energy consumption model is detailed in~\cite{}. It is based on the model proposed by~\cite{ChinhVu}. We refer to the sensor node Medusa~II which
+uses an Atmels AVR ATmega103L microcontroller~\cite{raghunathan2002energy} to use numerical values.}
+\textcolor{red}{Est-ce qu'il faut en ecrire plus et redonner le tableau de valeurs?}
+\iffalse
\subsection{Energy model}
We use an energy consumption model proposed by~\cite{ChinhVu} and based on
energy consumed in active state (9.72 mW) by the time in second for one round
(3600 seconds). According to the interval of initial energy, a sensor may be
alive during at most 20 rounds.
+\fi
\subsection{Metrics}
-To evaluate our approach we consider the following performance metrics:
+\textcolor{green} {To evaluate our approach we consider the performance metrics detailed in~\cite{idrees2015distributed} which are Coverage Ratio, Network Lifetime and Energy Consumption.
+Compared to the previous definitions, formulations of Coverage Ratio and Energy Consumption are enriched with the index of round $t$.}
\begin{enumerate}[i]
%\item {Network Lifetime:} we have defined the network lifetime as the time until all
%nodes have been drained of their energy or each sensor network monitoring an area has become disconnected.
+\end{enumerate}
+\iffalse
+\begin{enumerate}
+ \setcounter{5}
\item {{\bf Execution Time}:} a sensor node has limited energy resources and
computing power, therefore it is important that the proposed algorithm has the
shortest possible execution time. The energy of a sensor node must be mainly
to network disconnections and for which round it occurs.
\end{enumerate}
+\fi
\section{Experimental results and analysis}
\label{analysis}
\subsection{Performance analysis for different number of primary points}
\label{ch4:sec:04:06}
-In this section, we study the performance of MuDiLCO-1 approach for different
+In this section, we study the performance of MuDiLCO-1 approach (with only one round as in~\cite{idrees2015distributed}) for different
numbers of primary points. The objective of this comparison is to select the
suitable number of primary points to be used by a MuDiLCO protocol. In this
comparison, MuDiLCO-1 protocol is used with five primary point models, each
model corresponding to a number of primary points, which are called Model-5 (it
-uses 5 primary points), Model-9, Model-13, Model-17, and Model-21.
+uses 5 primary points), Model-9, Model-13, Model-17, and Model-21. \textcolor{green}{Note that results presented in~\cite{idrees2015distributed} corresponds to Model-13 (13 primary points)}.
\subsubsection{Coverage ratio}
scheduling based on optimization in MuDiLCO maintains higher coverage ratios of
the area of interest for a larger number of rounds. It also means that MuDiLCO
saves more energy, with less dead nodes, at most for several rounds, and thus
-should extend the network lifetime. \textcolor{blue}{MuDiLCO-7 seems to have
+should extend the network lifetime. MuDiLCO-7 seems to have
most of the time the best coverage ratio up to round~80, after that MuDiLCO-5 is
- slightly better.}
+ slightly better.
\begin{figure}[ht!]
\centering
\end{figure}
\subsection{Stopped simulation runs}
-
+A simulation ends when the sensor network
+ becomes disconnected (some nodes are dead and are not able to send information
+ to the base station). We report the number of simulations that are stopped due
+ to network disconnections and for which round it occurs.
Figure~\ref{fig6} reports the cumulative percentage of stopped simulations runs
per round for 150 deployed nodes. This figure gives the breakpoint for each
method. DESK stops first, after approximately 45~rounds, because it consumes
due to activating a larger number of redundant nodes as well as the energy
consumed during the different status of the sensor node.
-\textcolor{blue}{Energy consumption increases with the size of the networks and
+Energy consumption increases with the size of the networks and
the number of rounds. The curve Unlimited-MuDiLCO-7 shows that energy
consumption due to the time spent to optimally solve the integer program
increases drastically with the size of the network. When the resolution time
is limited for large network sizes, the energy consumption remains of the same
- order whatever the MuDiLCO version. As can be seen with MuDiLCO-7.}
+ order whatever the MuDiLCO version. As can be seen with MuDiLCO-7.
\subsection{Execution time}
\label{et}
\end{figure}
As expected, the execution time increases with the number of rounds $T$ taken
-into account to schedule the sensing phase. \textcolor{blue}{Obviously, the
+into account to schedule the sensing phase. Obviously, the
number of variables and constraints of the integer program increases with $T$,
- as explained in section~\ref{decision}, the times obtained for $T=1,3$ or
+ as explained in section~\ref{mom}, the times obtained for $T=1,3$ or
$5$ seem bearable. But for $T=7$, without any limitation of the time, they
become quickly unsuitable for a sensor node, especially when the sensor
network size increases as demonstrated by Unlimited-MuDiLCO-7. Notice that
pre-sensing phases, on the other hand a leader node may waste a considerable
amount of energy to solve the optimization problem. Thus, limiting the time
resolution for large instances allows to reduce the energy consumption without
- any impact on the coverage quality.}
+ any impact on the coverage quality.
\subsection{Network lifetime}
%This point was already noticed in subsection \ref{subsec:EC} devoted to the
%energy consumption, since network lifetime and energy consumption are directly
%linked.
-\textcolor{blue}{Overall, it clearly appears that computing a scheduling for
+Overall, it clearly appears that computing a scheduling for
several rounds is possible and relevant, providing that the execution time to
solve the optimization problem for large instances is limited. Notice that
rather than limiting the execution time, similar results might be obtained by
replacing the computation of the exact solution with the finding of a
suboptimal one using a heuristic approach. For our simulation setup and
considering the different metrics, MuDiLCO-5 seems to be the best suited
- method compared to MuDiLCO-7.}
+ method compared to MuDiLCO-7.
\begin{figure}[t!]
\centering
time. Indeed, when dealing with large wireless sensor networks, a distributed
approach, like the one we propose, 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. \textcolor{blue}{ Furthermore,
+subregion, that can be solved more easily. Furthermore,
results also show that to plan the activity of sensors for large network
sizes, an approach to obtain a near optimal solution is needed. Indeed, an
exact resolution of the resulting optimization problem leads to prohibitive
- computation times and thus to an excessive energy consumption.}
+ computation times and thus to an excessive energy consumption.
%In future work, we plan to study and propose adjustable sensing range coverage optimization protocol, which computes all active sensor schedules in one time, by using
%optimization methods. This protocol can prolong the network lifetime by minimizing the number of the active sensor nodes near the borders by optimizing the sensing range of sensor nodes.
