X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/JournalMultiRounds.git/blobdiff_plain/9864f80a0ad836b0a625455f3445cb62cd5f3073..HEAD:/elsarticle-template-num.tex diff --git a/elsarticle-template-num.tex b/elsarticle-template-num.tex index 691beda..05f7884 100644 --- a/elsarticle-template-num.tex +++ b/elsarticle-template-num.tex @@ -81,33 +81,41 @@ %% \address{Address\fnref{label3}} %% \fntext[label3]{} -\title{Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks} +\title{Distributed Lifetime Coverage Optimization Protocol \\ +in Wireless Sensor Networks} %% use optional labels to link authors explicitly to addresses: %% \author[label1,label2]{} %% \address[label1]{} %% \address[label2]{} -\author{Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier} +\author{Ali Kadhum Idrees, Karine Deschinkel, \\ +Michel Salomon, and Rapha\"el Couturier} %\thanks{are members in the AND team - DISC department - FEMTO-ST Institute, University of Franche-Comt\'e, Belfort, France. % e-mail: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr.}% <-this % stops a space %\thanks{}% <-this % stops a space - -\address{FEMTO-ST Institute, University of Franche-Comt\'e, Belfort, France. \\ e-mail: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr.} +\address{FEMTO-ST Institute, University of Franche-Comt\'e, Belfort, France. \\ +e-mail: ali.idness@edu.univ-fcomte.fr, \\ +$\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr.} \begin{abstract} -One of the fundamental challenges in Wireless Sensor Networks (WSNs) -is the coverage preservation and the extension of the network lifetime -continuously and effectively when monitoring a certain area (or -region) of interest. In this paper, a Distributed Lifetime Coverage Optimization Protocol (DiLCO) -to maintain the coverage and to improve the lifetime in wireless sensor networks is proposed. The area of interest is first divided into subregions using a divide-and-conquer method and then the DiLCO protocol is distributed on the sensor nodes in each subregion. The DiLCO combines two efficient techniques: Leader election for each subregion after that activity scheduling based optimization is planned for each subregion. The proposed -DiLCO works into rounds during which a small number of nodes, -remaining active for sensing, is selected to ensure coverage so as to maximize the lifetime of wireless sensor network. Each round consists of four phases: (i)~Information Exchange, (ii)~Leader -Election, (iii)~Decision, and (iv)~Sensing. The decision process is -carried out by a leader node, which solves an integer program. Compared with some existing -protocols, simulation results show that the proposed protocol can prolong the -network lifetime and improve the coverage performance effectively. - +One of the fundamental challenges in Wireless Sensor Networks (WSNs) is the +coverage preservation and the extension of the network lifetime continuously and +effectively when monitoring a certain area (or region) of interest. In this +paper, a Distributed Lifetime Coverage Optimization protocol (DiLCO) to maintain +the coverage and to improve the lifetime in wireless sensor networks is +proposed. The area of interest is first divided into subregions using a +divide-and-conquer method and then the DiLCO protocol is distributed on the +sensor nodes in each subregion. The DiLCO combines two efficient techniques: +leader election for each subregion, followed by an optimization-based planning +of activity scheduling decisions for each subregion. The proposed DiLCO works +into rounds during which a small number of nodes, remaining active for sensing, +is selected to ensure coverage so as to maximize the lifetime of wireless sensor +network. Each round consists of four phases: (i)~Information Exchange, +(ii)~Leader Election, (iii)~Decision, and (iv)~Sensing. The decision process is +carried out by a leader node, which solves an integer program. Compared with +some existing protocols, simulation results show that the proposed protocol can +prolong the network lifetime and improve the coverage performance effectively. \end{abstract} \begin{keyword} @@ -119,51 +127,61 @@ Optimization, Scheduling. \end{frontmatter} \section{Introduction} -\indent In the last years, there has been increasing development in wireless networking, -Micro-Electro-Mechanical Systems (MEMS), and embedded computing technologies, which are led to construct low-cost, small-sized and low-power sensor nodes that can perform detection, computation and data communication of surrounding environment. WSN -includes a large number of small, limited-power sensors that can -sense, process and transmit data over a wireless communication. They -communicate with each other by using multi-hop wireless communications, cooperate together to monitor the area of interest, -and the measured data can be reported to a monitoring center called sink -for analysis it~\cite{Sudip03}. There are several applications used the -WSN including health, home, environmental, military, and industrial -applications~\cite{Akyildiz02}. One of the major scientific research challenges in WSNs, which are addressed by a large number of literature during the last few years is to design energy efficient approches for coverage and connectivity in WSNs~\cite{conti2014mobile}.The coverage problem is one of the -fundamental challenges in WSNs~\cite{Nayak04} that consists in monitoring efficiently and continuously -the area of interest. The limited energy of sensors represents the main challenge in WSNs -design~\cite{Sudip03}, where it is impossible or inconvenient to replace and/or recharge their batteries because the the area of interest nature (such -as remote, hostile or unpractical environments) and the cost. So, it is necessary that a WSN -deployed with high density because spatial redundancy can then be -exploited to increase the lifetime of the network. However, turn on -all the sensor nodes, which monitor the same region at the same time -leads to decrease the lifetime of the network. To extend the lifetime -of the network, the main idea is to take advantage of the overlapping -sensing regions of some sensor nodes to save energy by turning off -some of them during the sensing phase~\cite{Misra05}. WSNs require -energy-efficient solutions to improve the network lifetime that is -constrained by the limited power of each sensor node ~\cite{Akyildiz02}. In this paper, we concentrate on the area -coverage problem, with the objective of maximizing the network -lifetime by using an adaptive scheduling. The area of interest is -divided into subregions and an activity scheduling for sensor nodes is -planned for each subregion. In fact, the nodes in a subregion can be -seen as a cluster where each node sends sensing data to the cluster head or the sink node. Furthermore, the activities in a -subregion/cluster can continue even if another cluster stops due to -too many node failures. Our scheduling scheme considers rounds, where -a round starts with a discovery phase to exchange information between -sensors of the subregion, in order to choose in a suitable manner a -sensor node to carry out a coverage strategy. This coverage strategy -involves the solving of an integer program, which provides the -activation of the sensors for the sensing phase of the current round. +\indent In the last years, there has been an increasing development in wireless +networking, Micro-Electro-Mechanical Systems (MEMS), and embedded computing +technologies, which have led to construct low-cost, small-sized, and low-power +sensor nodes that can perform detection, computation, and data communication of +surrounding environment. A WSN includes a large number of small, limited-power +sensors that can sense, process, and transmit data over a wireless +communication. They communicate with each other by using multi-hop wireless +communications and cooperate together to monitor the area of interest, so that +each measured data can be reported to a monitoring center called sink for +further analysis~\cite{Sudip03}. + +There are several fields of application covering a wide spectrum for a WSN, +including health, home, environmental, military, and industrial +applications~\cite{Akyildiz02}. One of the major scientific research challenges +in WSNs, which has been addressed by a large amount of literature during the +last few years, is the design of energy efficient approaches for coverage and +connectivity~\cite{conti2014mobile}. On the one hand an optimal +coverage~\cite{Nayak04} is required to monitor efficiently and continuously the +area of interest and on the other hand the energy consumption must be as low as +possible, due to the limited energy of sensors~\cite{Sudip03} and the +impossibility or difficulty to replace and/or recharge their batteries because +of the area of interest nature (such as remote, hostile, or unpractical +environments) and the cost. So, it is of great relevance for a WSN to be +deployed with high density, because spatial redundancy can then be exploited to +increase the lifetime of the network. However, turning on all the sensor nodes +which monitor the same region at the same time reduces the the lifetime of the +network. Therefore, to extend the lifetime of the network, the main idea is to +take advantage of the overlapping sensing regions of some sensor nodes to save +energy by turning off some of them during the sensing phase~\cite{Misra05}. + +In this paper we concentrate on the area coverage problem with the objective of +maximizing the network lifetime by using an adaptive scheduling. The area of +interest is divided into subregions and an activity scheduling for sensor nodes +is planned for each subregion. In fact, the nodes in a subregion can be seen as +a cluster where each node sends sensing data to the cluster head or the sink +node. Furthermore, the activities in a subregion/cluster can continue even if +another cluster stops due to too many node failures. Our scheduling scheme +considers rounds, where a round starts with a discovery phase to exchange +information between sensors of the subregion, in order to choose in a suitable +manner a sensor node to carry out a coverage strategy. This coverage strategy +involves the solving of an integer program, which provides the activation of the +sensors for the sensing phase of the current round. The remainder of the paper is organized as follows. The next section % Section~\ref{rw} -reviews the related work in the field. In section~\ref{prel}, the problem definition and some background are described. Section~\ref{pd} is devoted to -the DiLCO Protocol Description. Section~\ref{cp} gives the coverage model formulation, which is used -to schedule the activation of sensors. Section~\ref{exp} 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}. +reviews the related work in the field. In section~\ref{prel}, the problem +definition and some background are described. Section~\ref{pd} is devoted to the +DiLCO protocol Description. Section~\ref{cp} gives the coverage model +formulation which is used to schedule the activation of sensors. +Section~\ref{exp} 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}. +% MICHEL - OK up to here \section{Related works} \label{rw} @@ -382,7 +400,7 @@ $X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $. \centering \includegraphics[scale=0.20]{fig21.pdf}\\~ ~ ~ ~ ~(a) \includegraphics[scale=0.20]{fig22.pdf}\\~ ~ ~ ~ ~(b) -\includegraphics[scale=0.20]{principles13.eps}\\~ ~ ~ ~ ~(c) +\includegraphics[scale=0.20]{principles13.pdf}\\~ ~ ~ ~ ~(c) %\includegraphics[scale=0.10]{fig25.pdf}\\~ ~ ~(d) %\includegraphics[scale=0.10]{fig26.pdf}\\~ ~ ~(e) %\includegraphics[scale=0.10]{fig27.pdf}\\~ ~ ~(f) @@ -398,7 +416,7 @@ then our coverage protocol will be implemented in each subregion simultaneously. Our DiLCO protocol works in rounds fashion as shown in figure~\ref{fig2}. \begin{figure}[ht!] \centering -\includegraphics[width=95mm]{FirstModel.eps} % 70mm +\includegraphics[width=95mm]{FirstModel.pdf} % 70mm \caption{DiLCO protocol} \label{fig2} \end{figure} @@ -840,7 +858,7 @@ In this experiment, Figure~\ref{fig3} shows the average coverage ratio for 150 d \parskip 0pt \begin{figure}[h!] \centering - \includegraphics[scale=0.5] {R1/CR.eps} + \includegraphics[scale=0.5] {R1/CR.pdf} \caption{The impact of the number of rounds on the coverage ratio for 150 deployed nodes} \label{fig3} \end{figure} @@ -856,7 +874,7 @@ the area of interest into 8, 16 and 32~subregions if one of the subregions becom Figure~\ref{fig4} shows the average active nodes ratio for 150 deployed nodes. \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R1/ASR.eps} +\includegraphics[scale=0.5]{R1/ASR.pdf} \caption{The impact of the number of rounds on the active sensors ratio for 150 deployed nodes } \label{fig4} \end{figure} @@ -866,7 +884,7 @@ The results presented in figure~\ref{fig4} show the increase in the number of s Figure~\ref{fig6} illustrates the percentage of stopped simulation runs per round for 150 deployed nodes. \begin{figure}[h!] \centering -\includegraphics[scale=0.43]{R1/SR.eps} +\includegraphics[scale=0.43]{R1/SR.pdf} \caption{The percentage of stopped simulation runs compared to the number of rounds for 150 deployed nodes } \label{fig6} \end{figure} @@ -879,7 +897,7 @@ We measure the energy consumed by the sensors during the communication, listenin \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R1/EC95.eps} +\includegraphics[scale=0.5]{R1/EC95.pdf} \caption{The Energy Consumption for Lifetime95} \label{fig95} \end{figure} @@ -890,7 +908,7 @@ The results show that DiLCO-16 and DiLCO-32 are the most competitive from the e As shown in Figures~\ref{fig95} and ~\ref{fig50} , DiLCO-2 consumes more energy than the other versions of DiLCO, especially for large sizes of network. This is easy to understand since the bigger the number of sensors involved in the integer program, the larger the time computation to solve the optimization problem as well as the higher energy consumed during the communication. \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R1/EC50.eps} +\includegraphics[scale=0.5]{R1/EC50.pdf} \caption{The Energy Consumption for Lifetime50} \label{fig50} \end{figure} @@ -902,7 +920,7 @@ The original execution time is computed on a laptop DELL with intel Core i3 2370 \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R1/T.eps} +\includegraphics[scale=0.5]{R1/T.pdf} \caption{Execution Time (in seconds)} \label{fig8} \end{figure} @@ -918,7 +936,7 @@ In figure~\ref{figLT95} and \ref{figLT50}, network lifetime, $Lifetime95$ and $L \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R1/LT95.eps} +\includegraphics[scale=0.5]{R1/LT95.pdf} \caption{The Network Lifetime for $Lifetime95$} \label{figLT95} \end{figure} @@ -934,7 +952,7 @@ our DiLCO-16 protocol efficiently extends the network lifetime because the bene Comparison shows that the DiLCO-16 protocol, which uses 16 leaders, is the best one because it is used less number of active nodes during the network lifetime compared with DiLCO-32. It also means that distributing the protocol in each 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. \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R1/LT50.eps} +\includegraphics[scale=0.5]{R1/LT50.pdf} \caption{The Network Lifetime for $Lifetime50$} \label{figLT50} \end{figure} @@ -949,7 +967,7 @@ In this experiment, we Figure~\ref{fig33} shows the average coverage ratio for 1 \parskip 0pt \begin{figure}[h!] \centering - \includegraphics[scale=0.5] {R2/CR.eps} + \includegraphics[scale=0.5] {R2/CR.pdf} \caption{The impact of the number of rounds on the coverage ratio for 150 deployed nodes} \label{fig33} \end{figure} @@ -962,7 +980,7 @@ thanks to Model~2, which is slightly more efficient than other Models, because Figure~\ref{fig44} shows the average active nodes ratio for 150 deployed nodes. \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R2/ASR.eps} +\includegraphics[scale=0.5]{R2/ASR.pdf} \caption{The impact of the number of rounds on the active sensors ratio for 150 deployed nodes } \label{fig44} \end{figure} @@ -978,7 +996,7 @@ runs per round for 150 deployed nodes. \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R2/SR.eps} +\includegraphics[scale=0.5]{R2/SR.pdf} \caption{The percentage of stopped simulation runs compared to the number of rounds for 150 deployed nodes } \label{fig66} \end{figure} @@ -990,14 +1008,14 @@ As shown in Figure~\ref{fig66}, when the number of primary points are increased, In this experiment, we study the effect of increasing the primary points to represent the area of the sensor on the energy consumed by the wireless sensor network for different network densities. Figures~\ref{fig2EC95} and ~\ref{fig2EC50} illustrate the energy consumption for different network sizes for $Lifetime95$ and $Lifetime50$. \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R2/EC95.eps} +\includegraphics[scale=0.5]{R2/EC95.pdf} \caption{The Energy Consumption with $95\%-Lifetime$} \label{fig2EC95} \end{figure} \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R2/EC50.eps} +\includegraphics[scale=0.5]{R2/EC50.pdf} \caption{The Energy Consumption with $Lifetime50$} \label{fig2EC50} \end{figure} @@ -1010,7 +1028,7 @@ In this experiment, we study the impact of the increase in primary points on the \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R2/T.eps} +\includegraphics[scale=0.5]{R2/T.pdf} \caption{The Execution Time(s) vs The Number of Sensors } \label{figt} \end{figure} @@ -1024,7 +1042,7 @@ Finally, we will study the effect of increasing the primary points on the lifeti \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R2/LT95.eps} +\includegraphics[scale=0.5]{R2/LT95.pdf} \caption{The Network Lifetime for $Lifetime95$} \label{fig2LT95} \end{figure} @@ -1032,7 +1050,7 @@ Finally, we will study the effect of increasing the primary points on the lifeti \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R2/LT50.eps} +\includegraphics[scale=0.5]{R2/LT50.pdf} \caption{The Network Lifetime for $Lifetime50$} \label{fig2LT50} \end{figure} @@ -1051,7 +1069,7 @@ In this experiment, Figure~\ref{fig333} shows the average coverage ratio for 15 \parskip 0pt \begin{figure}[h!] \centering - \includegraphics[scale=0.5] {R3/CR.eps} + \includegraphics[scale=0.5] {R3/CR.pdf} \caption{The coverage ratio for 150 deployed nodes} \label{fig333} \end{figure} @@ -1067,7 +1085,7 @@ in order to minimize the energy consumption and maximize the network lifetime. \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R3/ASR.eps} +\includegraphics[scale=0.5]{R3/ASR.pdf} \caption{The active sensors ratio for 150 deployed nodes } \label{fig444} \end{figure} @@ -1080,7 +1098,7 @@ Figure~\ref{fig666} illustrates the percentage of stopped simulation runs per round for 150 deployed nodes. \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R3/SR.eps} +\includegraphics[scale=0.5]{R3/SR.pdf} \caption{The percentage of stopped simulation runs compared to the number of rounds for 150 deployed nodes } \label{fig666} \end{figure} @@ -1091,14 +1109,14 @@ In this experiment, we study the effect of the energy consumed by the wireless s \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R3/EC95.eps} +\includegraphics[scale=0.5]{R3/EC95.pdf} \caption{The Energy Consumption with $95\%-Lifetime$} \label{fig3EC95} \end{figure} \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R3/EC50.eps} +\includegraphics[scale=0.5]{R3/EC50.pdf} \caption{The Energy Consumption with $Lifetime50$} \label{fig3EC50} \end{figure} @@ -1110,7 +1128,7 @@ In this experiment, we are observed the superiority of our DiLCO-16 and DiLCO-32 \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R3/LT95.eps} +\includegraphics[scale=0.5]{R3/LT95.pdf} \caption{The Network Lifetime for $Lifetime95$} \label{fig3LT95} \end{figure} @@ -1118,7 +1136,7 @@ In this experiment, we are observed the superiority of our DiLCO-16 and DiLCO-32 \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{R3/LT50.eps} +\includegraphics[scale=0.5]{R3/LT50.pdf} \caption{The Network Lifetime for $Lifetime50$} \label{fig3LT50} \end{figure}