set of points called primary points~\cite{idrees2014coverage}. We assume that
the sensing disk defined by a sensor is covered if all the primary points of
this sensor are covered. By knowing the position of wireless sensor node
-(centered at the the position $\left(p_x,p_y\right)$) and it's sensing range
+(centered at the the position $\left(p_x,p_y\right)$) and its sensing range
$R_s$, we define up to 25 primary points $X_1$ to $X_{25}$ as decribed on
Figure~\ref{fig1}. The optimal number of primary points is investigated in
section~\ref{ch4:sec:04:06}.
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
solver returns the best solution found, which is not necessary the optimal
one. In practice, we only set time limit values for $T=5$ and $T=7$. In fact,
for $T=5$ we limited the time for 250~nodes, whereas for $T=7$ it was for the
- three largest network sizes. Therefore we used the following values (in
+ three largest network sizes. Therefore we used the following values (in
second): 0.03 for 250~nodes when $T=5$, while for $T=7$ we chose 0.03, 0.06,
- and 0.08 for respectively 150, 200, and 250~nodes.
- These time limit thresholds have been set empirically. The basic idea consists
- in considering the average execution time to solve the integer programs to
- optimality, then in dividing this average time by three to set the threshold
- value. 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.}
+ and 0.08 for respectively 150, 200, and 250~nodes. These time limit
+ thresholds have been set empirically. The basic idea is to consider the
+ average execution time to solve the integer programs to optimality for 100
+ nodes and then to adjust the time linearly according to the increasing network
+ 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.}
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
phase time.
Some preliminary experiments were performed to study the choice of the number of
-subregions which subdivides the sensing field, considering different network
+subregions which subdivides the sensing field, considering different network
sizes. They show that as the number of subregions increases, so does the network
lifetime. Moreover, it makes the MuDiLCO protocol more robust against random
-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.
+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.
\subsection{Energy model}
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
- most of the time the best coverage ratio up to round~80, after MuDiLCO-5 is
+ most of the time the best coverage ratio up to round~80, after that MuDiLCO-5 is
slightly better.}
\begin{figure}[ht!]
due to activating a larger number of redundant nodes as well as the energy
consumed during the different status of the sensor node.
-% TO BE CONTINUED
\textcolor{blue}{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 solve the integer program to optimality
+ 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.}
-
+ order whatever the MuDiLCO version. As can be seen with MuDiLCO-7.}
\subsection{Execution time}
\label{et}
-We observe the impact of the network size and of the number of rounds on the
+We observe the impact of the network size and of the number of rounds on the
computation time. Figure~\ref{fig77} gives the average execution times in
-seconds (needed to solve optimization problem) for different values of $T$. The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is employed to generate the Mixed Integer Linear Program instance in a standard format, which is then read and solved by the optimization solver GLPK (GNU linear Programming Kit available in the public domain) \cite{glpk} through a Branch-and-Bound method. The
-original execution time is computed on a laptop DELL with Intel Core~i3~2370~M
-(2.4 GHz) processor (2 cores) and the MIPS (Million Instructions Per Second)
-rate equal to 35330. To be consistent with the use of a sensor node with Atmels
-AVR ATmega103L microcontroller (6 MHz) and a MIPS rate equal to 6 to run the
-optimization resolution, this time is multiplied by 2944.2 $\left(
-\frac{35330}{2} \times \frac{1}{6} \right)$ and reported on Figure~\ref{fig77}
+seconds (needed to solve optimization problem) for different values of $T$. The
+modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is employed to
+generate the Mixed Integer Linear Program instance in a standard format, which
+is then read and solved by the optimization solver GLPK (GNU linear Programming
+Kit available in the public domain) \cite{glpk} through a Branch-and-Bound
+method. The original execution time is computed on a laptop DELL with Intel
+Core~i3~2370~M (2.4 GHz) processor (2 cores) and the MIPS (Million Instructions
+Per Second) rate equal to 35330. To be consistent with the use of a sensor node
+with Atmels AVR ATmega103L microcontroller (6 MHz) and a MIPS rate equal to 6 to
+run the optimization resolution, this time is multiplied by 2944.2 $\left(
+\frac{35330}{2} \times \frac{1}{6} \right)$ and reported on Figure~\ref{fig77}
for different network sizes.
\begin{figure}[ht!]
\end{figure}
As expected, the execution time increases with the number of rounds $T$ taken
-into account to schedule the sensing phase. The times obtained for $T=1,3$
-or $5$ seem bearable, but for $T=7$ they become quickly unsuitable for a sensor
-node, especially when the sensor network size increases. Again, we can notice
-that if we want to schedule the nodes activities for a large number of rounds,
-we need to choose a relevant number of subregions in order to avoid a complicated
-and cumbersome optimization. On the one hand, a large value for $T$ permits to
-reduce the energy-overhead due to the three pre-sensing phases, on the other
-hand a leader node may waste a considerable amount of energy to solve the
-optimization problem.
-
-%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.
+into account to schedule the sensing phase. \textcolor{blue}{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
+ $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
+ for 250 nodes, we also limited the execution time for $T=5$, otherwise the
+ execution time, denoted by Unlimited-MuDiLCO-5, is also above MuDiLCO-7. On the one hand, a large
+ value for $T$ permits to reduce the energy-overhead due to the three
+ 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.}
\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}$
-and $Lifetime_{50}$. Both figures show that the network lifetime increases
+and $Lifetime_{50}$. Both figures show that the network lifetime increases
together with the number of sensor nodes, whatever the protocol, thanks to the
-node density which results in more and more redundant nodes that can be
+node density which results in more and more redundant nodes that can be
deactivated and thus save energy. Compared to the other approaches, our MuDiLCO
-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 be observed for MuDiLCO-7 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
-linked.
-%\textcolor{red}{As can be seen in these figures, the lifetime increases with the size of the network, and it is clearly largest for the MuDiLCO
-%and the GA-MuDiLCO protocols. GA-MuDiLCO prolongs the network lifetime obviously in comparison with both DESK and GAF, as well as the MuDiLCO-7 version for $lifetime_{95}$. However, comparison shows that MuDiLCO protocol and GA-MuDiLCO protocol, which use distributed optimization over the subregions are the best ones because they are robust to network disconnection during the network lifetime as well as they consume less energy in comparison with other approaches.}
+protocol maximizes the lifetime of the network. In particular the gain in
+lifetime for a coverage over 95\%, and a network of 250~nodes, is greater than
+43\% when switching from GAF to MuDiLCO-5.
+%The lower performance that can be observed for MuDiLCO-7 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
+%linked.
+\textcolor{blue}{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.}
+
\begin{figure}[t!]
\centering
\begin{tabular}{cl}
- \parbox{9.5cm}{\includegraphics[scale=0.5]{F/LT95.pdf}} & (a) \\
+ \parbox{9.5cm}{\includegraphics[scale=0.5125]{F/LT95.pdf}} & (a) \\
\verb+ + \\
- \parbox{9.5cm}{\includegraphics[scale=0.5]{F/LT50.pdf}} & (b)
+ \parbox{9.5cm}{\includegraphics[scale=0.5125]{F/LT50.pdf}} & (b)
\end{tabular}
\caption{Network lifetime for (a) $Lifetime_{95}$ and
(b) $Lifetime_{50}$}
\label{fig8}
\end{figure}
-% By choosing the best suited nodes, for each round, by optimizing the coverage and lifetime of the network to cover the area of interest with a maximum number rounds and by letting the other nodes sleep in order to be used later in next rounds, our MuDiLCO protocol efficiently prolonges the network lifetime.
-
-%In Figure~\ref{fig8}, Comparison shows that our MuDiLCO protocol, which are used distributed optimization on the subregions with the ability of producing T rounds, is the best one because it is robust to network disconnection during the network lifetime as well as it consume less energy in comparison with other approaches. It also means that distributing the protocol in each sensor node and subdividing the sensing field into many subregions, which are managed independently and simultaneously, is the most relevant way to maximize the lifetime of a network.
-
-
-%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}
\label{sec:conclusion}
-We have addressed the problem of the coverage and of the lifetime optimization in
-wireless sensor networks. This is a key issue as sensor nodes have limited
+We have addressed the problem of the coverage and of 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
+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
+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
-%while taking the responsibility of covering the corresponding
-%subregion using more than one cover set during the sensing phase.
-The activity scheduling in each subregion works in periods, where each period
-consists of four phases: (i) Information Exchange, (ii) Leader Election, (iii)
-Decision Phase to plan the activity of the sensors over $T$ rounds, (iv) Sensing
-Phase itself divided into $T$ rounds.
-
-Simulations results show the relevance of the proposed protocol in terms of
+scheduling. The activity scheduling in each subregion works in periods, where
+each period consists of four phases: (i) Information Exchange, (ii) Leader
+Election, (iii) Decision Phase to plan the activity of the sensors over $T$
+rounds, (iv) Sensing Phase itself divided into $T$ rounds.
+
+Simulations results show the relevance of the proposed protocol in terms of
lifetime, coverage ratio, active sensors ratio, energy consumption, execution
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
+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. Nevertheless, results also show that
-it is not possible to plan the activity of sensors over too many rounds, because
-the resulting optimization problem leads to too high resolution times and thus to
-an excessive energy consumption.
+subregion, that can be solved more easily. \textcolor{blue}{ 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.}
%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.
