X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/Sensornets15.git/blobdiff_plain/c5d35ebf9a8ac33354f3f6514280bce5ec92a729..9bc38095022b21c8005ea6af50223a60ace36718:/Example.tex?ds=sidebyside diff --git a/Example.tex b/Example.tex index c30cff5..06be273 100644 --- a/Example.tex +++ b/Example.tex @@ -26,7 +26,8 @@ %\title{Authors' Instructions \subtitle{Preparation of Camera-Ready Contributions to SCITEPRESS Proceedings} } -\title{Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks} +\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\\ @@ -78,20 +79,30 @@ 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. \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.} +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 @@ -116,9 +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 \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. +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} @@ -290,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!] @@ -354,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} @@ -398,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