X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/JournalMultiPeriods.git/blobdiff_plain/f7dcdff7f2151372dfabe5d5a70f4f4e3d13324b..refs/heads/master:/article.tex?ds=sidebyside diff --git a/article.tex b/article.tex index cd6a361..ed70b52 100644 --- a/article.tex +++ b/article.tex @@ -149,10 +149,10 @@ in~\cite{idrees2015distributed}. %more interesting to divide the area into several subregions, given the %computation complexity. -\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 +\textcolor{black}{ Compared to our previous work~\cite{idrees2015distributed}, + in this paper we study the possibility of dividing the sensing phase into + multiple rounds. We make a multiround optimization, + while previously it was a single round optimization. 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 @@ -291,34 +291,13 @@ Indeed, each sensor maintains its own timer and its wake-up time is randomized \subsection{Assumptions and primary points} \label{pp} -\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 -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 -homogeneous in terms of communication and processing capabilities, and -heterogeneous from the point of view of energy provision. Each sensor is -supposed to get information on its location either through hardware such as -embedded GPS or through location discovery algorithms. - -To model a sensor node's coverage area, we consider the boolean disk coverage -model which is the most widely used sensor coverage model in the -literature. Thus, each sensor has a constant sensing range $R_s$ and 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. We also assume that the -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.\fi - -\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 +\textcolor{black}{The assumptions and the coverage model are identical to those presented + in~\cite{idrees2015distributed}. We consider a scenario in which sensors are deployed in high + density to initially ensure 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 + a module to locate its geographical positions. All space points within the + disk centered at the sensor with the radius of the sensing range are said to be covered by this sensor.} \indent Instead of working with the coverage area, we consider for each sensor a @@ -377,14 +356,14 @@ 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{blue}{Compared to protocol - DiLCO described in~\cite{idrees2015distributed},} each sensing phase is itself +Leader~Election, Decision, and Sensing. \textcolor{black}{Compared to + the DiLCO protocol 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 +rounds. \textcolor{black}{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 @@ -421,7 +400,7 @@ rounds. \textcolor{blue}{Algorithm~\ref{alg:MuDiLCO} is executed by each sensor \label{alg:MuDiLCO} \end{algorithm} -\textcolor{blue}{As already described in~\cite{idrees2015distributed}}, two +\textcolor{black}{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 @@ -503,8 +482,8 @@ 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 +\textcolor{black}{Note that the proposed integer program is an + extension of the one 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 @@ -611,15 +590,6 @@ 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} - -The sensing phase consists of $T$ rounds. Each sensor node in the subregion will -receive an Active-Sleep packet from WSNL, informing it to stay awake or to go to -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 \section{Experimental framework} \label{exp} @@ -687,79 +657,19 @@ 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 \textcolor{blue}{as +the following we have set the number of subregions to~16 \textcolor{black}{as recommended in~\cite{idrees2015distributed}}. \subsection{Energy model} -\textcolor{blue}{The energy consumption model is detailed +\textcolor{black}{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} - -We use an energy consumption model proposed by~\cite{ChinhVu} and based on -\cite{raghunathan2002energy} with slight modifications. The energy consumption -for sending/receiving the packets is added, whereas the part related to the -sensing range is removed because we consider a fixed sensing range. - -For our energy consumption model, we refer to the sensor node Medusa~II which -uses an Atmels AVR ATmega103L microcontroller~\cite{raghunathan2002energy}. The -typical architecture of a sensor is composed of four subsystems: the MCU -subsystem which is capable of computation, communication subsystem (radio) which -is responsible for transmitting/receiving messages, the sensing subsystem that -collects data, and the power supply which powers the complete sensor node -\cite{raghunathan2002energy}. Each of the first three subsystems can be turned -on or off depending on the current status of the sensor. Energy consumption -(expressed in milliWatt per second) for the different status of the sensor is -summarized in Table~\ref{table4}. - -\begin{table}[ht] -\caption{The Energy Consumption Model} -\centering -\begin{tabular}{|c|c|c|c|c|} - \hline -Sensor status & MCU & Radio & Sensing & Power (mW) \\ [0.5ex] -\hline -LISTENING & on & on & on & 20.05 \\ -\hline -ACTIVE & on & off & on & 9.72 \\ -\hline -SLEEP & off & off & off & 0.02 \\ -\hline -COMPUTATION & on & on & on & 26.83 \\ -\hline -\end{tabular} - -\label{table4} -\end{table} - -For the sake of simplicity we ignore the energy needed to turn on the radio, to -start up the sensor node, to move from one status to another, etc. -Thus, when a sensor becomes active (i.e., it has already chosen its status), it -can turn its radio off to save battery. MuDiLCO uses two types of packets for -communication. The size of the INFO packet and Active-Sleep packet are 112~bits -and 24~bits respectively. The value of energy spent to send a 1-bit-content -message is obtained by using the equation in ~\cite{raghunathan2002energy} to -calculate the energy cost for transmitting messages and we propose the same -value for receiving the packets. The energy needed to send or receive a 1-bit -packet is equal to 0.2575~mW. - -The initial energy of each node is randomly set in the interval $[500;700]$. A -sensor node will not participate in the next round if its remaining energy is -less than $E_{R}=36~\mbox{Joules}$, the minimum energy needed for the node to -stay alive during one round. This value has been computed by multiplying the -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 + values.} \subsection{Metrics} -\textcolor{blue}{To evaluate our approach we consider the performance metrics +\textcolor{black}{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 @@ -828,21 +738,7 @@ indicate the energy consumed by the whole network in round $t$. %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 - used for the sensing phase, not for the pre-sensing ones. - -\item {{\bf 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. -\end{enumerate} -\fi \section{Experimental results and analysis} \label{analysis} @@ -856,7 +752,8 @@ 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 +Model-9, Model-13, Model-17, and Model-21. \textcolor{black}{Note + that the results presented in~\cite{idrees2015distributed} correspond to Model-13 (13 primary points)}. @@ -873,7 +770,7 @@ because it offers a good coverage ratio for a larger number of periods. \begin{figure}[t!] \centering - \includegraphics[scale=0.5] {R2/CR.pdf} + \includegraphics[scale=0.5] {R2CR.pdf} \caption{Coverage ratio for 150 deployed nodes} \label{Figures/ch4/R2/CR} \end{figure} @@ -889,9 +786,9 @@ lifetime improvement. \begin{figure}[h!] \centering \centering -\includegraphics[scale=0.5]{R2/LT95.pdf}\\~ ~ ~ ~ ~(a) \\ +\includegraphics[scale=0.5]{R2LT95.pdf}\\~ ~ ~ ~ ~(a) \\ -\includegraphics[scale=0.5]{R2/LT50.pdf}\\~ ~ ~ ~ ~(b) +\includegraphics[scale=0.5]{R2LT50.pdf}\\~ ~ ~ ~ ~(b) \caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$} \label{Figures/ch4/R2/LT} @@ -922,7 +819,7 @@ the best coverage ratio up to round~80, after that MuDiLCO-5 is slightly better. \begin{figure}[ht!] \centering - \includegraphics[scale=0.5] {F/CR.pdf} + \includegraphics[scale=0.5] {FCR.pdf} \caption{Average coverage ratio for 150 deployed nodes} \label{fig3} \end{figure} @@ -941,7 +838,7 @@ efficient manner. \begin{figure}[ht!] \centering -\includegraphics[scale=0.5]{F/ASR.pdf} +\includegraphics[scale=0.5]{FASR.pdf} \caption{Active sensors ratio for 150 deployed nodes} \label{fig4} \end{figure} @@ -961,7 +858,7 @@ in a subregion is still connected. \begin{figure}[ht!] \centering -\includegraphics[scale=0.5]{F/SR.pdf} +\includegraphics[scale=0.5]{FSR.pdf} \caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes} \label{fig6} \end{figure} @@ -977,9 +874,9 @@ network sizes, for $Lifetime_{95}$ and $Lifetime_{50}$. \begin{figure}[h!] \centering \begin{tabular}{cl} - \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC95.pdf}} & (a) \\ + \parbox{9.5cm}{\includegraphics[scale=0.5]{FEC95.pdf}} & (a) \\ \verb+ + \\ - \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC50.pdf}} & (b) + \parbox{9.5cm}{\includegraphics[scale=0.5]{FEC50.pdf}} & (b) \end{tabular} \caption{Energy consumption for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$} @@ -1018,7 +915,7 @@ Figure~\ref{fig77} for different network sizes. \begin{figure}[ht!] \centering -\includegraphics[scale=0.5]{F/T.pdf} +\includegraphics[scale=0.5]{FT.pdf} \caption{Execution Time (in seconds)} \label{fig77} \end{figure} @@ -1066,9 +963,9 @@ 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.5125]{F/LT95.pdf}} & (a) \\ + \parbox{9.5cm}{\includegraphics[scale=0.5125]{FLT95.pdf}} & (a) \\ \verb+ + \\ - \parbox{9.5cm}{\includegraphics[scale=0.5125]{F/LT50.pdf}} & (b) + \parbox{9.5cm}{\includegraphics[scale=0.5125]{FLT50.pdf}} & (b) \end{tabular} \caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$}