X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/Sensornets15.git/blobdiff_plain/cec3b1150a4effa0c5b6c66627d74813226f79eb..9bc38095022b21c8005ea6af50223a60ace36718:/Example.tex diff --git a/Example.tex b/Example.tex index 29cd9c6..06be273 100644 --- a/Example.tex +++ b/Example.tex @@ -26,16 +26,17 @@ %\title{Authors' Instructions \subtitle{Preparation of Camera-Ready Contributions to SCITEPRESS Proceedings} } -\title{Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks} - -\author{Ali Kadhum Idrees, Karine Deschinkel,\\ Michel Salomon, and Rapha\"el Couturier\\ -%\affiliation{ -FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comt\'e,\\ - Belfort, France\\ -%} -%\affiliation{\sup{2}Department of Computing, Main University, MySecondTown, MyCountry} +\title{Distributed Lifetime Coverage Optimization Protocol \\ + in Wireless Sensor Networks} + +\author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$,\\ Michel Salomon$^{a}$, and Rapha\"el Couturier$^{a}$\\ +$^{a}$FEMTO-ST Institute, UMR 6174 CNRS, \\ University Bourgogne Franche-Comt\'e, Belfort, France\\ +$^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}}\\ email: ali.idness@edu.univ-fcomte.fr,\\ $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr} -%\email{\{f\_author, s\_author\}@ips.xyz.edu, t\_author@dc.mu.edu} + +%\author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$,\\ Michel Salomon$^{a}$, and Rapha\"el Couturier $^{a}$ \\ +%$^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, University Bourgogne Franche-Comt\'e,\\ Belfort, France}} \\ +%$^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}} } \begin{document} \maketitle @@ -55,11 +56,12 @@ email: ali.idness@edu.univ-fcomte.fr,\\ $\lbrace$karine.deschinkel, michel.salom scheduling performed by each elected leader. This two-step process takes place periodically, in order to choose a small set of nodes remaining active for sensing during a time slot. Each set is built to ensure coverage at a low - energy cost, allowing to optimize the network lifetime. %More precisely, a + energy cost, allowing to optimize the network lifetime. +%More precisely, a %period consists of four phases: (i)~Information Exchange, (ii)~Leader %Election, (iii)~Decision, and (iv)~Sensing. The decision process, which - results in an activity scheduling vector, is carried out by a leader node - through the solving of an integer program. +% results in an activity scheduling vector, is carried out by a leader node +% through the solving of an integer program. % MODIF - BEGIN Simulations are conducted using the discret event simulator OMNET++. We refer to the characterictics of a Medusa II sensor for @@ -77,24 +79,34 @@ email: ali.idness@edu.univ-fcomte.fr,\\ $\lbrace$karine.deschinkel, michel.salom \label{sec:introduction} \noindent -Energy efficiency is a crucial issue in wireless sensor networks since sensory +Energy efficiency is a crucial issue in wireless sensor networks since sensory consumption, in order to maximize the network lifetime, represents the major difficulty when designing WSNs. As a consequence, one of the 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}. Coverage reflects how well a +coverage and connectivity~\cite{conti2014mobile}. Coverage reflects how well a sensor field is monitored. On the one hand we want to monitor the area of -interest in the most efficient way~\cite{Nayak04}. On the other hand we want to -use as little energy as possible. Sensor nodes are battery-powered with no -means of recharging or replacing, usually due to environmental (hostile or -unpractical environments) or cost reasons. Therefore, it is desired that the -WSNs are deployed with high densities so as to exploit the overlapping sensing -regions of some sensor nodes to save energy by turning off some of them during -the sensing phase to prolong the network lifetime. +interest in the most efficient way~\cite{Nayak04}, \textcolor{blue}{which means + that we want to maintain the best coverage as long as possible}. On the other +hand we want to use as little energy as possible. Sensor nodes are +battery-powered with no means of recharging or replacing, usually due to +environmental (hostile or unpractical environments) or cost reasons. Therefore, +it is desired that the WSNs are deployed with high densities so as to exploit +the overlapping sensing regions of some sensor nodes to save energy by turning +off some of them during the sensing phase to prolong the network +lifetime. \textcolor{blue}{A WSN can use various types of sensors such as + \cite{ref17,ref19}: thermal, seismic, magnetic, visual, infrared, acoustic, + and radar. These sensors are capable of observing different physical + conditions such as: temperature, humidity, pressure, speed, direction, + movement, light, soil makeup, noise levels, presence or absence of certain + kinds of objects, and mechanical stress levels on attached objects. + Consequently, there is a wide range of WSN applications such as~\cite{ref22}: + health-care, environment, agriculture, public safety, military, transportation + systems, and industry applications.} In this paper we design a protocol that focuses on the area coverage problem with the objective of maximizing the network lifetime. Our proposition, the -Distributed Lifetime Coverage Optimization (DILCO) protocol, maintains the +Distributed Lifetime Coverage Optimization (DiLCO) protocol, maintains the coverage and improves the lifetime in WSNs. The area of interest is first divided into subregions using a divide-and-conquer algorithm and an activity scheduling for sensor nodes is then planned by the elected leader in each @@ -115,10 +127,10 @@ framework of the DiLCO approach and the coverage problem formulation. In this paper we made more realistic simulations by taking into account the characteristics of a Medusa II sensor ~\cite{raghunathan2002energy} to measure the energy consumption and the computation time. We have implemented two other -existing approaches (a distributed one, DESK ~\cite{ChinhVu}, and a centralized -one called GAF ~\cite{xu2001geography}) in order to compare their performances -with our approach. We also focus on performance analysis based on the number of -subregions. +existing \textcolor{blue}{and distributed approaches} (DESK ~\cite{ChinhVu}, and +GAF ~\cite{xu2001geography}) in order to compare their performances with our +approach. We also focus on performance analysis based on the number of +subregions. % MODIF - END The remainder of the paper continues with Section~\ref{sec:Literature Review} @@ -243,7 +255,8 @@ less accurate according to the number of primary points. \label{main_idea} \noindent We start by applying a divide-and-conquer algorithm to partition the area of interest into smaller areas called subregions and then our protocol is -executed simultaneously in each subregion. +executed simultaneously in each subregion. \textcolor{blue}{Sensor nodes are assumed to +be deployed almost uniformly over the region and the subdivision of the area of interest is regular.} \begin{figure}[ht!] \centering @@ -256,8 +269,9 @@ As shown in Figure~\ref{fig2}, the proposed DiLCO protocol is a periodic protocol where each period is decomposed into 4~phases: Information Exchange, Leader Election, Decision, and Sensing. For each period there will be exactly one cover set in charge of the sensing task. A periodic scheduling is -interesting because it enhances the robustness of the network against node -failures. First, a node that has not enough energy to complete a period, or +interesting because it enhances the robustness of the network against node failures. +% \textcolor{blue}{Many WSN applications have communication requirements that are periodic and known previously such as collecting temperature statistics at regular intervals. This periodic nature can be used to provide a regular schedule to sensor nodes and thus avoid a sensor failure. If the period time increases, the reliability and energy consumption are decreased and vice versa}. +First, a node that has not enough energy to complete a period, or which fails before the decision is taken, will be excluded from the scheduling process. Second, if a node fails later, whereas it was supposed to sense the region of interest, it will only affect the quality of the coverage until the @@ -288,23 +302,37 @@ and each sensor node will have five possible status in the network: \end{itemize} %\end{enumerate} -An outline of the protocol implementation is given by Algorithm~\ref{alg:DiLCO} +An outline of the protocol implementation is given by Algorithm~\ref{alg:DiLCO} which describes the execution of a period by a node (denoted by $s_j$ for a -sensor node indexed by $j$). At the beginning a node checks whether it has -enough energy to stay active during the next sensing phase. If yes, it exchanges -information with all the other nodes belonging to the same subregion: it -collects from each node its position coordinates, remaining energy ($RE_j$), ID, -and the number of one-hop neighbors still alive. Once the first phase is -completed, the nodes of a subregion choose a leader to take the decision based -on the following criteria with decreasing importance: larger number of -neighbors, larger remaining energy, and then in case of equality, larger index. -After that, if the sensor node is leader, it will execute the integer program -algorithm (see Section~\ref{cp}) which provides a set of sensors planned to be -active in the next sensing phase. As leader, it will send an Active-Sleep packet -to each sensor in the same subregion to indicate it if it has to be active or -not. Alternately, if the sensor is not the leader, it will wait for the -Active-Sleep packet to know its state for the coming sensing phase. - +sensor node indexed by $j$). At the beginning a node checks whether it has +enough energy \textcolor{blue}{(its energy should be greater than a fixed + treshold $E_{th}$)} to stay active during the next sensing phase. If yes, it +exchanges information with all the other nodes belonging to the same subregion: +it collects from each node its position coordinates, remaining energy ($RE_j$), +ID, and the number of one-hop neighbors still alive. \textcolor{blue}{INFO + packet contains two parts: header and data payload. The sensor ID is included + in the header, where the header size is 8 bits. The data part includes + position coordinates (64 bits), remaining energy (32 bits), and the number of + one-hop live neighbors (8 bits). Therefore the size of the INFO packet is 112 + bits.} Once the first phase is completed, the nodes of a subregion choose a +leader to take the decision based on the following criteria with decreasing +importance: larger number of neighbors, larger remaining energy, and then in +case of equality, larger index. After that, if the sensor node is leader, it +will solve an integer program (see Section~\ref{cp}). \textcolor{blue}{This + integer program contains boolean variables $X_j$ where ($X_j=1$) means that + sensor $j$ will be active in the next sensing phase. Only sensors with enough + remaining energy are involved in the integer program ($J$ is the set of all + sensors involved). As the leader consumes energy (computation energy is + denoted by $E^{comp}$) to solve the optimization problem, it will be included + in the integer program only if it has enough energy to achieve the computation + and to stay alive during the next sensing phase, that is to say if $RE_j > + E^{comp}+E_{th}$. Once the optimization problem is solved, each leader will + send an ActiveSleep packet to each sensor in the same subregion to indicate it + if it has to be active or not. Otherwise, if the sensor is not the leader, it + will wait for the ActiveSleep packet to know its state for the coming sensing + phase.} +%which provides a set of sensors planned to be +%active in the next sensing phase. \begin{algorithm}[h!] @@ -352,7 +380,7 @@ We formulate the coverage optimization problem with an integer program. The objective function consists in minimizing the undercoverage and the overcoverage of the area as suggested in \cite{pedraza2006}. The area coverage problem is expressed as the coverage of a fraction of points called primary points. Details on the choice and the number of primary points can be found in \cite{idrees2014coverage}. The set of primary points is denoted by $P$ -and the set of sensors by $J$. As we consider a boolean disk coverage model, we use the boolean indicator $\alpha_{jp}$ which is equal to 1 if the primary point $p$ is in the sensing range of the sensor $j$. The binary variable $X_j$ represents the activation or not of the sensor $j$. So we can express the number of active sensors that cover the primary point $p$ by $\sum_{j \in J} \alpha_{jp} * X_{j}$. We deduce the overcoverage denoted by $\Theta_p$ of the primary point $p$ : +and the set of alive sensors by $J$. As we consider a boolean disk coverage model, we use the boolean indicator $\alpha_{jp}$ which is equal to 1 if the primary point $p$ is in the sensing range of the sensor $j$. The binary variable $X_j$ represents the activation or not of the sensor $j$. So we can express the number of active sensors that cover the primary point $p$ by $\sum_{j \in J} \alpha_{jp} * X_{j}$. We deduce the overcoverage denoted by $\Theta_p$ of the primary point $p$ : \begin{equation} \Theta_{p} = \left \{ \begin{array}{l l} @@ -396,9 +424,14 @@ X_{j} \in \{0,1\}, &\forall j \in J \end{array} \right. \end{equation} -The objective function is a weighted sum of overcoverage and undercoverage. The goal is to limit the overcoverage in order to activate a minimal number of sensors while simultaneously preventing undercoverage. Both weights $w_\theta$ and $w_U$ must be carefully chosen in -order to guarantee that the maximum number of points are covered during each -period. +The objective function is a weighted sum of overcoverage and undercoverage. The goal is to limit the overcoverage in order to activate a minimal number of sensors while simultaneously preventing undercoverage. \textcolor{blue}{ By + choosing $w_{U}$ much larger than $w_{\theta}$, the coverage of a + maximum of primary points is ensured. Then for the same number of covered + primary points, the solution with a minimal number of active sensors is + preferred. } +%Both weights $w_\theta$ and $w_U$ must be carefully chosen in +%order to guarantee that the maximum number of points are covered during each +%period. % MODIF - END @@ -712,7 +745,7 @@ nodes, and thus enables the extension of the network lifetime. \parskip 0pt \begin{figure}[t!] \centering - \includegraphics[scale=0.45] {R/CR.pdf} + \includegraphics[scale=0.45] {CR.pdf} \caption{Coverage ratio} \label{fig3} \end{figure} @@ -733,7 +766,7 @@ used for the different performance metrics. \begin{figure}[h!] \centering -\includegraphics[scale=0.45]{R/EC.pdf} +\includegraphics[scale=0.45]{EC.pdf} \caption{Energy consumption per period} \label{fig95} \end{figure} @@ -769,7 +802,7 @@ Figure~\ref{fig8}. \begin{figure}[h!] \centering -\includegraphics[scale=0.45]{R/T.pdf} +\includegraphics[scale=0.45]{T.pdf} \caption{Execution time in seconds} \label{fig8} \end{figure} @@ -796,7 +829,7 @@ network lifetime. \begin{figure}[h!] \centering -\includegraphics[scale=0.45]{R/LT.pdf} +\includegraphics[scale=0.45]{LT.pdf} \caption{Network lifetime} \label{figLT95} \end{figure}