From: Michel Salomon Date: Tue, 3 Jan 2017 12:48:55 +0000 (+0100) Subject: Some minor changes X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/JournalMultiPeriods.git/commitdiff_plain/f7dcdff7f2151372dfabe5d5a70f4f4e3d13324b Some minor changes --- diff --git a/article.tex b/article.tex index d886626..cd6a361 100644 --- a/article.tex +++ b/article.tex @@ -84,11 +84,11 @@ %e-mail: ali.idness@edu.univ-fcomte.fr, \\ %$\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr.} -\author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$, \\ Michel - Salomon$^{a}$, and Rapha\"el Couturier $^{a}$ \\ $^{a}${\em{FEMTO-ST - Institute/CNRS, \\ Univ. Bourgogne Franche-Comt\'e, - Belfort, France}} \\ $^{b}${\em{Department of Computer Science, University - of Babylon, Babylon, Iraq}} } +\author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$, \\ + Michel Salomon$^{a}$, and Rapha\"el Couturier $^{a}$ \\ + $^{a}${\em{FEMTO-ST Institute, DISC department, UMR 6174 CNRS, \\ + Univ. Bourgogne Franche-Comt\'e (UBFC), Belfort, France}} \\ + $^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}}} \begin{abstract} Coverage and lifetime are two paramount problems in Wireless Sensor Networks @@ -99,17 +99,16 @@ divided into subregions and then the MuDiLCO protocol is distributed on the 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. 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. -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 -performance. +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. 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 performance. \end{abstract} \begin{keyword} @@ -150,24 +149,26 @@ in~\cite{idrees2015distributed}. %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 +\textcolor{blue}{ 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 -framework, it describes the simulation setup and the different metrics used to -assess the performances. Section~\ref{analysis} shows the simulation results -obtained using the discrete event simulator OMNeT++ \cite{varga}. They fully -demonstrate the usefulness of the proposed approach. Finally, we give -concluding remarks and some suggestions for future works in -Section~\ref{sec:conclusion}. + given time threshold. In this paper we also analyze the performance of our + protocol according to the number of primary points used (the 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 framework, it +describes the simulation setup and the different metrics used to assess the +performances. Section~\ref{analysis} shows the simulation results obtained +using the discrete event simulator OMNeT++ \cite{varga}. They fully demonstrate +the usefulness of the proposed approach. Finally, we give concluding remarks +and some suggestions for future works in Section~\ref{sec:conclusion}. \section{Related works} \label{rw} @@ -243,40 +244,40 @@ processing by the cooperating sensor nodes, but they are more scalable for large WSNs. Localized and distributed algorithms generally result in non-disjoint set covers. -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 +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 +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 +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 +(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 +reduces the randomness in scheduling that would otherwise occur due to the +absence of location information. In \cite{ChinhVu}, the authors 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 +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}. The works presented in \cite{Bang, Zhixin, Zhang} focus on coverage-aware, distributed energy-efficient, and distributed clustering methods respectively, -which aim at extending the network lifetime, while the coverage is ensured. +which aim at extending 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 +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 +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 @@ -289,8 +290,9 @@ Indeed, each sensor maintains its own timer and its wake-up time is randomized \subsection{Assumptions and primary points} \label{pp} -\textcolor{green}{Assumptions and coverage model are identical to those presented in~\cite{idrees2015distributed}.} +\textcolor{blue}{Assumptions and coverage model are identical to those presented + in~\cite{idrees2015distributed}.} \iffalse We consider a randomly and uniformly deployed network consisting of static @@ -311,17 +313,21 @@ 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.\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.} +\textcolor{blue}{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 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 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 +(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 described on +Figure~\ref{fig1}. The optimal number of primary points is investigated in section~\ref{ch4:sec:04:06}. The coordinates of the primary points are defined as follows:\\ @@ -361,61 +367,89 @@ $X_{25}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $. \subsection{Background idea} -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. +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. 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. \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. \textcolor{green}{Algorithm~\ref{alg:MuDiLCO} is -executed by each sensor node~$s_j$ (with enough remaining energy) at the beginning of a period.} +Leader~Election, Decision, and Sensing. \textcolor{blue}{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. \textcolor{blue}{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} +\end{figure} + +\begin{algorithm}[h!] + \BlankLine + \If{ $RE_j \geq E_{R}$ }{ + \emph{$s_j.status$ = COMMUNICATION}\; + \emph{Send $INFO()$ packet to other nodes in the subregion}\; + \emph{Wait $INFO()$ packet from other nodes in the subregion}\; + + \emph{LeaderID = Leader election}\; + \If{$ s_j.ID = LeaderID $}{ + \emph{$s_j.status$ = COMPUTATION}\; + \emph{$\left\{\left(X_{1,k},\dots,X_{T,k}\right)\right\}_{k \in J}$ = + Execute Integer Program Algorithm($T,J$)}\; + \emph{$s_j.status$ = COMMUNICATION}\; + \emph{Send $ActiveSleep()$ packet to each node $k$ in subregion: a packet \\ + with vector of activity scheduling $(X_{1,k},\dots,X_{T,k})$}\; + \emph{Update $RE_j $}\; + } + \Else{ + \emph{$s_j.status$ = LISTENING}\; + \emph{Wait $ActiveSleep()$ packet from the Leader}\; + \emph{Update $RE_j $}\; + } + } + \Else { Exclude $s_j$ from entering in the current sensing phase} + +\caption{MuDiLCO($s_j$)} +\label{alg:MuDiLCO} +\end{algorithm} -\textcolor{green}{As already described in~\cite{idrees2015distributed}}, two types of packets are used by the proposed protocol: +\textcolor{blue}{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 +\item INFO packet: such a packet will be sent by each sensor node to all the nodes inside a subregion for information exchange. \item Active-Sleep packet: sent by the leader to all the nodes inside a - subregion to inform them to remain Active or to go Sleep during the sensing + subregion to inform them to remain Active or to go Sleep during the sensing phase. \end{enumerate} There are five status for each sensor node in the network: \begin{enumerate}[(a)] \item LISTENING: sensor node is waiting for a decision (to be active or not); -\item COMPUTATION: sensor node has been elected as leader and applies the +\item COMPUTATION: sensor node has been elected as leader and applies the optimization process; \item ACTIVE: sensor node is taking part in the monitoring of the area; \item SLEEP: sensor node is turned off to save energy; \item COMMUNICATION: sensor node is transmitting or receiving packet. \end{enumerate} - - - 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. +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 @@ -424,28 +458,23 @@ 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 (line 4). - -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.\\ - - - +At the beginning of each period, each sensor which 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 (line 4). + +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. %Each WSNL will solve an integer program to select which cover % sets will be activated in the following sensing phase to cover the subregion @@ -455,27 +484,28 @@ the communications.\\ % 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. - - -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 -of targets to become minimal at the same time. They use binary variables -$x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our model, we -consider binary variables $X_{t,j}$ to determine the possibility of activating -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. \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$.} + +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 the +cover sets to 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. + +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 of targets to become minimal at the same +time. They use binary variables $x_{jl}$ to indicate if sensor $j$ belongs to +cover set $l$. In our model, we consider binary variables $X_{t,j}$ to +determine the possibility of activating 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. +\textcolor{blue}{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: @@ -504,7 +534,7 @@ We define the Overcoverage variable $\Theta_{t,p}$ as: \begin{array}{l l} 0 & \mbox{if the primary point $p$}\\ & \mbox{is not covered during round $t$,}\\ - \left( \sum_{j \in J} \alpha_{jp} * X_{tj} \right)- 1 & \mbox{otherwise.}\\ + \left( \sum_{j \in J} \alpha_{jp} * X_{t,j} \right)- 1 & \mbox{otherwise.}\\ \end{array} \right. \label{eq13} \end{equation} @@ -570,17 +600,16 @@ There are two main objectives. First, we limit the overcoverage of primary points in order to activate a minimum number of sensors. Second we prevent the absence of monitoring on some parts of the subregion by minimizing the undercoverage. The weights $W_\theta$ and $W_U$ must be properly chosen so as -to guarantee that the maximum number of points are covered during each round. +to guarantee that the maximum number of points are covered during each round. In our simulations, priority is given to the coverage by choosing $W_{U}$ very large compared to $W_{\theta}$. -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})). +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})). \iffalse \subsection{Sensing phase} @@ -592,36 +621,6 @@ 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 - \If{ $RE_j \geq E_{R}$ }{ - \emph{$s_j.status$ = COMMUNICATION}\; - \emph{Send $INFO()$ packet to other nodes in the subregion}\; - \emph{Wait $INFO()$ packet from other nodes in the subregion}\; - - \emph{LeaderID = Leader election}\; - \If{$ s_j.ID = LeaderID $}{ - \emph{$s_j.status$ = COMPUTATION}\; - \emph{$\left\{\left(X_{1,k},\dots,X_{T,k}\right)\right\}_{k \in J}$ = - Execute Integer Program Algorithm($T,J$)}\; - \emph{$s_j.status$ = COMMUNICATION}\; - \emph{Send $ActiveSleep()$ packet to each node $k$ in subregion: a packet \\ - with vector of activity scheduling $(X_{1,k},\dots,X_{T,k})$}\; - \emph{Update $RE_j $}\; - } - \Else{ - \emph{$s_j.status$ = LISTENING}\; - \emph{Wait $ActiveSleep()$ packet from the Leader}\; - \emph{Update $RE_j $}\; - } - } - \Else { Exclude $s_j$ from entering in the current sensing phase} - -\caption{MuDiLCO($s_j$)} -\label{alg:MuDiLCO} - -\end{algorithm} - \section{Experimental framework} \label{exp} @@ -631,11 +630,11 @@ We conducted a series of simulations to evaluate the efficiency and the relevance of our approach, using the discrete event simulator OMNeT++ \cite{varga}. The simulation parameters are summarized in Table~\ref{table3}. Each experiment for a network is run over 25~different random topologies and the -results presented hereafter are the average of these 25 runs. -We performed simulations for five different densities varying from 50 to -250~nodes deployed over a $50 \times 25~m^2 $ sensing field. More precisely, -the deployment is controlled at a coarse scale in order to ensure that the -deployed nodes can cover the sensing field with the given sensing range. +results presented hereafter are the average of these 25 runs. We performed +simulations for five different densities varying from 50 to 250~nodes deployed +over a $50 \times 25~m^2 $ sensing field. More precisely, the deployment is +controlled at a coarse scale in order to ensure that the deployed nodes can +cover the sensing field with the given sensing range. \begin{table}[ht] \caption{Relevant parameters for network initializing.} @@ -656,27 +655,26 @@ $W_{U}$ & $|P|^2$ \\ \label{table3} \end{table} -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 - threshold has been fixed when solving large instances. In these cases, the - 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 - 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 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. +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 threshold has been fixed when +solving large instances. In these cases, the 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 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 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 + method, called DESK and proposed by \cite{ChinhVu}, is a fully distributed coverage algorithm. The second method, called GAF~\cite{xu2001geography}, consists in dividing the region into fixed squares. During the decision phase, in each square, one sensor is then chosen to remain active during the sensing @@ -687,14 +685,19 @@ 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 +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 \textcolor{green}{as recommended in~\cite{idrees2015distributed}}. +the following we have set the number of subregions to~16 \textcolor{blue}{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?} +\textcolor{blue}{The energy consumption model is detailed + in~\cite{raghunathan2002energy}. 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} @@ -756,27 +759,30 @@ alive during at most 20 rounds. \subsection{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$.} +\textcolor{blue}{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 {{\bf Coverage Ratio (CR)}:} the coverage ratio measures how much of the area - of a sensor field is covered. In our case, the sensing field is represented as - a connected grid of points and we use each grid point as a sample point to - compute the coverage. The coverage ratio can be calculated by: +\item {{\bf Coverage Ratio (CR)}:} the coverage ratio measures how much of the + area of a sensor field is covered. In our case, the sensing field is + represented as a connected grid of points and we use each grid point as a + sample point to compute the coverage. The coverage ratio can be calculated by: \begin{equation*} \scriptsize \mbox{CR}(\%) = \frac{\mbox{$n^t$}}{\mbox{$N$}} \times 100, \end{equation*} where $n^t$ is the number of covered grid points by the active sensors of all -subregions during round $t$ in the current sensing phase and $N$ is the total number -of grid points in the sensing field of the network. In our simulations $N = 51 -\times 26 = 1326$ grid points. +subregions during round $t$ in the current sensing phase and $N$ is the total +number of grid points in the sensing field of the network. In our simulations $N += 51 \times 26 = 1326$ grid points. \item{{\bf Number of Active Sensors Ratio (ASR)}:} it is important to have as - few active nodes as possible in each round, in order to minimize the - communication overhead and maximize the network lifetime. The Active Sensors + few active nodes as possible in each round, in order to minimize the + communication overhead and maximize the network lifetime. The Active Sensors Ratio is defined as follows: \begin{equation*} \scriptsize \mbox{ASR}(\%) = \frac{\sum\limits_{r=1}^R @@ -787,18 +793,18 @@ $t$ in the current sensing phase, $|J|$ is the total number of sensors in the network, and $R$ is the total number of subregions in the network. \item {{\bf Network Lifetime}:} we define the network lifetime as the time until - the coverage ratio drops below a predefined threshold. We denote by - $Lifetime_{95}$ (respectively $Lifetime_{50}$) the amount of time during - which the network can satisfy an area coverage greater than $95\%$ - (respectively $50\%$). We assume that the network is alive until all nodes have - been drained of their energy or the sensor network becomes - disconnected. Network connectivity is important because an active sensor node - without connectivity towards a base station cannot transmit information on an - event in the area that it monitors. + the coverage ratio drops below a predefined threshold. We denote by + $Lifetime_{95}$ (respectively $Lifetime_{50}$) the amount of time during which + the network can satisfy an area coverage greater than $95\%$ (respectively + $50\%$). We assume that the network is alive until all nodes have been drained + of their energy or the sensor network becomes disconnected. Network + connectivity is important because an active sensor node without connectivity + towards a base station cannot transmit information on an event in the area + that it monitors. \item {{\bf Energy Consumption (EC)}:} the average energy consumption can be seen as the total energy consumed by the sensors during the $Lifetime_{95}$ or - $Lifetime_{50}$ divided by the number of rounds. EC can be computed as + $Lifetime_{50}$ divided by the number of rounds. EC can be computed as follows: \begin{equation*} @@ -844,24 +850,27 @@ indicate the energy consumed by the whole network in round $t$. \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 (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. \textcolor{green}{Note that results presented in~\cite{idrees2015distributed} corresponds to Model-13 (13 primary points)}. +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. \textcolor{blue}{Note that results + presented in~\cite{idrees2015distributed} correspond to Model-13 (13 primary + points)}. \subsubsection{Coverage ratio} Figure~\ref{Figures/ch4/R2/CR} shows the average coverage ratio for 150 deployed nodes. As can be seen, at the beginning the models which use a larger number of primary points provide slightly better coverage ratios, but latter they are the -worst. -Moreover, when the number of periods increases, the coverage ratio produced by -all models decrease due to dead nodes. However, Model-5 is the one with the -slowest decrease due to lower numbers of active sensors in the earlier periods. -Overall this model is slightly more efficient than the other ones, because it -offers a good coverage ratio for a larger number of periods. +worst. Moreover, when the number of periods increases, the coverage ratio +produced by all models decrease due to dead nodes. However, Model-5 is the one +with the slowest decrease due to lower numbers of active sensors in the earlier +periods. Overall this model is slightly more efficient than the other ones, +because it offers a good coverage ratio for a larger number of periods. + \begin{figure}[t!] \centering \includegraphics[scale=0.5] {R2/CR.pdf} @@ -871,11 +880,11 @@ offers a good coverage ratio for a larger number of periods. \subsubsection{Network lifetime} -Finally, we study the effect of increasing the number of primary points on the lifetime of the network. -As highlighted by Figures~\ref{Figures/ch4/R2/LT}(a) and -\ref{Figures/ch4/R2/LT}(b), the network lifetime obviously increases when the -size of the network increases, with Model-5 which leads to the largest lifetime -improvement. +Finally, we study the effect of increasing the number of primary points on the +lifetime of the network. As highlighted by Figures~\ref{Figures/ch4/R2/LT}(a) +and \ref{Figures/ch4/R2/LT}(b), the network lifetime obviously increases when +the size of the network increases, with Model-5 which leads to the largest +lifetime improvement. \begin{figure}[h!] \centering @@ -897,7 +906,7 @@ experiments presented thereafter. \subsection{Coverage ratio} Figure~\ref{fig3} shows the average coverage ratio for 150 deployed nodes. We -can notice that for the first thirty rounds both DESK and GAF provide a coverage +can notice that for the first 30~rounds both DESK and GAF provide a coverage which is a little bit better than the one of MuDiLCO. This is due to the fact that, in comparison with MuDiLCO which uses optimization to put in SLEEP status redundant sensors, more sensor nodes remain active with DESK and GAF. As a @@ -908,9 +917,8 @@ greater than 50\% for far more rounds. Overall, the proposed sensor activity 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. MuDiLCO-7 seems to have - most of the time the best coverage ratio up to round~80, after that MuDiLCO-5 is - slightly better. +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. \begin{figure}[ht!] \centering @@ -939,22 +947,22 @@ efficient manner. \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 -the more energy by turning on a large number of redundant nodes during the -sensing phase. GAF stops secondly for the same reason than DESK. Let us -emphasize that the simulation continues as long as a network in a subregion is -still connected. + +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 break point for each method. DESK stops first, after approximately +45~rounds, because it consumes the more energy by turning on a large number of +redundant nodes during the sensing phase. GAF stops secondly for the same reason +than DESK. Let us emphasize that the simulation continues as long as a network +in a subregion is still connected. \begin{figure}[ht!] \centering \includegraphics[scale=0.5]{F/SR.pdf} -\caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes } +\caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes} \label{fig6} \end{figure} @@ -983,29 +991,30 @@ consumption point of view. The other approaches have a high energy consumption due to activating a larger number of redundant nodes as well as the energy consumed during the different status of the sensor node. -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. +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. \subsection{Execution time} \label{et} + 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} -for different network sizes. +seconds (needed to solve the 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!] \centering @@ -1015,19 +1024,19 @@ for different network sizes. \end{figure} As expected, the execution time increases with the number of rounds $T$ taken -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{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 - 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. +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{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 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} @@ -1046,14 +1055,13 @@ lifetime for a coverage over 95\%, and a network of 250~nodes, is greater than %This point was already noticed in subsection \ref{subsec:EC} devoted to the %energy consumption, since network lifetime and energy consumption are directly %linked. -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. +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 @@ -1088,22 +1096,24 @@ 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 global optimization problem by partitioning it in many smaller problems, one per -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. +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. %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. % use section* for acknowledgement \section*{Acknowledgment} -This work is partially funded by the Labex ACTION program (contract ANR-11-LABX-01-01). -As a Ph.D. student, Ali Kadhum IDREES would like to gratefully acknowledge the -University of Babylon - Iraq for the financial support, Campus France (The -French national agency for the promotion of higher education, international -student services, and international mobility).%, and the University ofFranche-Comt\'e - France for all the support in France. +This work is partially funded by the Labex ACTION program (contract +ANR-11-LABX-01-01). Ali Kadhum IDREES would like to gratefully acknowledge the +University of Babylon - Iraq for the financial support and Campus France (The +French national agency for the promotion of higher education, international +student services, and international mobility) for the support received when he +was Ph.D. student in France. +%, and the University ofFranche-Comt\'e - France for all the support in France.