From 263eab05c343c1a339634d7d9dd4ce532e440334 Mon Sep 17 00:00:00 2001 From: ali Date: Mon, 2 Dec 2013 17:44:32 +0100 Subject: [PATCH] Ali makes a lot of updates --- IEEEtran.cls | 0 bare_conf.bib | 58 ++++++++++++++++++--- bare_conf.tex | 136 +++++++++++++++++++++++--------------------------- 3 files changed, 112 insertions(+), 82 deletions(-) mode change 100755 => 100644 IEEEtran.cls mode change 100755 => 100644 bare_conf.tex diff --git a/IEEEtran.cls b/IEEEtran.cls old mode 100755 new mode 100644 diff --git a/bare_conf.bib b/bare_conf.bib index 2af3c39..d6508f6 100644 --- a/bare_conf.bib +++ b/bare_conf.bib @@ -1,3 +1,53 @@ +@ARTICLE{Ammari01, + author = "Habib M. Ammari and Sajal K. Das", + title = "Scheduling protocols for homogeneous and heterogeneous k-covered wireless sensor networks", + YEAR = {2011}, + JOURNAL = {Pervasive and Mobile Computing}, + VOLUME = {7}, + NUMBER = {1}, + PAGES = {79-97}, + } + +@book{Akyildiz02, + author = {Ian F. Akyildiz and Mehmet Can Vuran}, + title = {Wireless Sensor Networks}, + year = {2010}, + isbn = {}, + publisher = {John Wiley and Sons Ltd.}, + address = {}, +} + +@book{Sudip03, + author = {Sudip Misra, Isaac Woungang and Subhas Chandra Misra}, + title = {Guide to Wireless Sensor Networks}, + year = {2009}, + isbn = {}, + publisher = {Springer-Verlag London Limited}, + address = {}, +} + +@book{Nayak04 , + author = {Amiya Nayak and Ivan Stojmenovic}, + title = {Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication}, + year = {2010}, + isbn = {}, + publisher = {John Wiley and Sons, Inc}, + address = {}, +} + + +@ARTICLE{Misra05, + author = "S. Misra, M.P. Kumar and M.S. Obaidat", + title = "Connectivity preserving localized coverage algorithm for area monitoring using wireless +sensor networks", + YEAR = {2011}, + JOURNAL = {Computer Communications}, + VOLUME = {34}, + NUMBER = {12}, + PAGES = {1484-1496}, + } + + @ARTICLE{wns07, author ={J. Wang, C. Niu, R. Shen }, title = {Randomized approach for target coverage scheduling in directional sensor network}, @@ -15,14 +65,6 @@ pages = {101-111} } -@ARTICLE{asc02, - author = "I. Akyildiz and W. Su and Y.Sankarasubramniam and E. Cayirci", - title = "A survey on sensor networks", - YEAR = {2002}, - JOURNAL = {IEEE Comm. Magazine}, -PAGES = {102-114}, - } - @ARTICLE{pc10, author = "T.V. Padmavathy and M. Chitra", title = "Extending the Network Lifetime of Wireless Sensor Networks Using Residual Energy Extraction—Hybrid Scheduling Algorithm", diff --git a/bare_conf.tex b/bare_conf.tex old mode 100755 new mode 100644 index 9e1ea25..c0ed90c --- a/bare_conf.tex +++ b/bare_conf.tex @@ -29,7 +29,7 @@ \usepackage{epsfig} \usepackage{caption} \usepackage{multicol} - +\usepackage{times} \usepackage{graphicx,epstopdf} \epstopdfsetup{suffix=} \DeclareGraphicsExtensions{.ps} @@ -37,15 +37,16 @@ \begin{document} +%\title{ Coverage and Lifetime Optimization in Heterogeneous Energy Wireless Sensor Networks} \title{Coverage and Lifetime Optimization in Heterogeneous Energy Wireless Sensor Networks} - %Activity Scheduling for Coverage and Lifetime Optimization in Wireless Sensor Networks} % author names and affiliations % use a multiple column layout for up to three different % affiliations -\author{\IEEEauthorblockN{Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier } -\IEEEauthorblockA{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte, Belfort, France \\ +\author{\IEEEauthorblockN{Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier} +\IEEEauthorblockA{FEMTO-ST Institute, UMR 6174 CNRS \\ +University of Franche-Comt\'e, Belfort, France \\ Email: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr} %\email{\{ali.idness, karine.deschinkel, michel.salomon, raphael.couturier\}@univ-fcomte.fr} %\and @@ -62,7 +63,7 @@ Email: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel, michel.salomon 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 coverage optimization protocol to +region) of interest. In this paper, a coverage optimization protocol to improve the lifetime in heterogeneous energy wireless sensor networks is proposed. The area of interest is first divided into subregions using a divide-and-conquer method and then the scheduling of sensor node @@ -71,46 +72,27 @@ considers rounds during which a small number of nodes, remaining active for sensing, is selected to ensure coverage. 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. +carried out by a leader node, which solves an integer program. Simulation results show that the proposed approach can prolong the network lifetime and improve the coverage performance. \end{abstract} -%\keywords{Area Coverage, Wireless Sensor Networks, lifetime Optimization, Distributed Protocol.} +\begin{IEEEkeywords} +Area Coverage, Network lifetime, Optimization, Scheduling, Distributed Protocol. +\end{IEEEkeywords} +%\keywords{Area Coverage, Network lifetime, Optimization, Distributed Protocol} \IEEEpeerreviewmaketitle \section{Introduction} -\noindent Recent years have witnessed significant advances in wireless -communications and embedded micro-sensing MEMS technologies which have -led to the emergence of wireless sensor networks as one of the most promising -technologies~\cite{asc02}. In fact, they present huge potential in -several domains ranging from health care applications to military -applications. A sensor network is composed of a large number of tiny -sensing devices deployed in a region of interest. Each device has -processing and wireless communication capabilities, which enable it to -sense its environment, to compute, to store information, and to deliver -report messages to a base station. -%These sensor nodes run on batteries with limited capacities. To achieve a long life of the network, it is important to conserve battery power. Therefore, lifetime optimisation is one of the most critical issues in wireless sensor networks. -One of the main design issues in Wireless Sensor Networks (WSNs) is to -prolong the network lifetime, while achieving acceptable quality of -service for applications. Indeed, sensor nodes have limited resources -in terms of memory, energy, and computational power. - -Since sensor nodes have limited battery life and without being able to -replace batteries, especially in remote and hostile environments, it -is desirable that a WSN should be deployed with high density because -spatial redundancy can then be exploited to increase the lifetime of -the network. In such a high density network, if all sensor nodes were -to be activated at the same time, the lifetime would be reduced. 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. -Obviously, the deactivation of nodes is only relevant if the coverage -of the monitored area is not affected. Consequently, future softwares -may need to adapt appropriately to achieve acceptable quality of -service for applications. In this paper we concentrate on the area +\noindent The fast developments in the low-cost sensor devices and wireless communications have allowed the emergence the WSNs. 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{Ammari01, Sudip03}. There are several applications used the WSN including health, home, environmental, military,and industrial applications~\cite{Akyildiz02}. +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 the WSNs design~\cite{Ammari01}, where it is difficult to replace and/or + recharge their batteries because the the area of interest nature (such as hostile 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 @@ -123,14 +105,14 @@ 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 +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. Section~\ref{pd} is devoted to the scheduling strategy for energy-efficient coverage. -Section~\ref{cp} gives the coverage model formulation which is used to +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 @@ -155,7 +137,8 @@ to recall the main definitions and assumptions related to our work. %\item Barrier Coverage An objective to determine the maximal support/breach paths that traverse a sensor field. Barrier coverage is expressed as finding one or more routes with starting position and ending position when the targets pass through the area deployed with sensor nodes~\cite{Santosh04,Ai05}. %\end{itemize} -{\bf Coverage} +\subsection{Coverage} +%{\bf Coverage} The most discussed coverage problems in literature can be classified into two types \cite{ma10}: area coverage (also called full or blanket @@ -165,10 +148,10 @@ area is within the sensing range of at least one working sensor node. Target coverage problem is to cover only a finite number of discrete points called targets. This type of coverage has mainly military applications. Our work will concentrate on the area coverage by design -and implementation of a strategy which efficiently selects the active +and implementation of a strategy, which efficiently selects the active nodes that must maintain both sensing coverage and network connectivity and at the same time improve the lifetime of the wireless -sensor network. But requiring that all physical points of the +sensor network. But, requiring that all physical points of the considered region are covered may be too strict, especially where the sensor network is not dense. Our approach represents an area covered by a sensor as a set of primary points and tries to maximize the total @@ -176,7 +159,8 @@ number of primary points that are covered in each round, while minimizing overcoverage (points covered by multiple active sensors simultaneously). -{\bf Lifetime} +\subsection{Lifetime} +%{\bf Lifetime} Various definitions exist for the lifetime of a sensor network~\cite{die09}. The main definitions proposed in the literature are @@ -191,7 +175,8 @@ during the WSN lifetime. 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. -{\bf Activity scheduling} +\subsection{Activity scheduling} +%{\bf Activity scheduling} Activity scheduling is to schedule the activation and deactivation of sensor nodes. The basic objective is to decide which sensors are in @@ -205,7 +190,8 @@ only using local neighbor information. In centralized algorithms, a central controller (a node or base station) informs every sensors of the time intervals to be activated. -{\bf Distributed approaches} +\subsection{Distributed approaches} +%{\bf Distributed approaches} Some distributed algorithms have been developed in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02} to perform the @@ -219,7 +205,7 @@ area \cite{Berman05efficientenergy}, maximum uncovered targets into rounds, where each round has a self-scheduling phase followed by a sensing phase. Each sensor broadcasts a message containing the node ID and the node location to its neighbors at the beginning of each round. A -sensor determines its status by a rule named off-duty eligible rule +sensor determines its status by a rule named off-duty eligible rule, which tells him to turn off if its sensing area is covered by its neighbors. A back-off scheme is introduced to let each sensor delay the decision process with a random period of time, in order to avoid @@ -254,7 +240,8 @@ sensor maintains its own timer and its wake-up time is randomized %In this paper we focus on centralized algorithms because distributed algorithms are outside the scope of our work. Note that centralized coverage algorithms have the advantage of requiring very low processing power from the sensor nodes which have usually limited processing capabilities. Moreover, a recent study conducted in \cite{pc10} concludes that there is a threshold in terms of network size to switch from a localized to a centralized algorithm. Indeed the exchange of messages in large networks may consume a considerable amount of energy in a localized approach compared to a centralized one. -{\bf Centralized approaches} +\subsection{Centralized approaches} +%{\bf Centralized approaches} Power efficient centralized schemes differ according to several criteria \cite{Cardei:2006:ECP:1646656.1646898}, such as the coverage @@ -268,15 +255,15 @@ these set covers successively. The first algorithms proposed in the literature consider that the cover sets are disjoint: a sensor node appears in exactly one of the generated cover sets. For instance, Slijepcevic and Potkonjak -\cite{Slijepcevic01powerefficient} propose an algorithm which +\cite{Slijepcevic01powerefficient} propose an algorithm, which allocates sensor nodes in mutually independent sets to monitor an area divided into several fields. Their algorithm builds a cover set by -including in priority the sensor nodes which cover critical fields, +including in priority the sensor nodes, which cover critical fields, that is to say fields that are covered by the smallest number of sensors. The time complexity of their heuristic is $O(n^2)$ where $n$ -is the number of sensors. \cite{cardei02}~describes a graph coloring -technique to achieve energy savings by organizing the sensor nodes -into a maximum number of disjoint dominating sets which are activated +is the number of sensors. In~\cite{cardei02}, a graph coloring +technique is described to achieve energy savings by organizing the sensor nodes +into a maximum number of disjoint dominating sets, which are activated successively. The dominating sets do not guarantee the coverage of the whole region of interest. Abrams et al.~\cite{Abrams:2004:SKA:984622.984684} design three approximation @@ -302,7 +289,7 @@ integer programming solving. %Cardei and Du \cite{Cardei:2005:IWS:1160086.1160098} propose a method to efficiently compute the maximum number of disjoint set covers such that each set can monitor all targets. They first transform the problem into a -maximum flow problem which is formulated as a mixed integer +maximum flow problem, which is formulated as a mixed integer programming (MIP). Then their heuristic uses the output of the MIP to compute disjoint set covers. Results show that this heuristic provides a number of set covers slightly larger compared to @@ -320,7 +307,7 @@ cover sets with a slight growth rate in execution time. %More recently Manju and Pujari\cite{Manju2011} In the case of non-disjoint algorithms \cite{Manju2011}, sensors may -participate in more than one cover set. In some cases this may +participate in more than one cover set. In some cases, this may prolong the lifetime of the network in comparison to the disjoint cover set algorithms, but designing algorithms for non-disjoint cover sets generally induces a higher order of complexity. Moreover, in @@ -338,9 +325,10 @@ authors have formulated the lifetime problem and suggested another algorithm~\cite{garg98}, provably near the optimal solution, is also proposed. -{\bf Our contribution} +\subsection{Our contribution} +%{\bf Our contribution} -There are three main questions which should be addressed to build a +There are three main questions, which should be addressed to build a scheduling strategy. We give a brief answer to these three questions to describe our approach before going into details in the subsequent sections. @@ -361,11 +349,11 @@ sections. \cite{pc10}, both centralized and distributed algorithms have their own advantages and disadvantages. Centralized coverage algorithms have the advantage of requiring very low processing power from the - sensor nodes which have usually limited processing capabilities. + sensor nodes, which have usually limited processing capabilities. Distributed algorithms are very adaptable to the dynamic and scalable nature of sensors network. Authors in \cite{pc10} conclude that there is a threshold in terms of network size to switch from a - localized to a centralized algorithm. Indeed the exchange of + localized to a centralized algorithm. Indeed, the exchange of messages in large networks may consume a considerable amount of energy in a centralized approach compared to a distributed one. Our work does not consider only one leader to compute and to broadcast @@ -432,7 +420,7 @@ active mode. %The working phase works in rounding fashion. Each round include 3 steps described as follow : \subsection{Leader election phase} -This step includes choosing the Wireless Sensor Node Leader (WSNL) +This step includes choosing the Wireless Sensor Node Leader (WSNL), which will be responsible for executing the coverage algorithm. Each subregion in the area of interest will select its own WSNL independently for each round. All the sensor nodes cooperate to @@ -464,7 +452,7 @@ starting a new round. %\noindent We try to produce an adaptive scheduling which allows sensors to operate alternatively so as to prolong the network lifetime. For convenience, the notations and assumptions are described first. %The wireless sensor node use the binary disk sensing model by which each sensor node will has a certain sensing range is reserved within a circular disk called radius $R_s$. -\noindent We consider a boolean disk coverage model which is the most +\indent We consider a boolean disk coverage model which is the most widely used sensor coverage model in the literature. Each sensor has a constant sensing range $R_s$. All space points within a disk centered at the sensor with the radius of the sensing range is said to be @@ -489,7 +477,7 @@ connectivity among the working nodes in the active mode. %We choose to representEach wireless sensor node will be represented into a selected number of primary points by which we can know if the sensor node is covered or not. % Figure ~\ref{fig:cluster2} shows the selected primary points that represents the area of the sensor node and according to the sensing range of the wireless sensor node. -\noindent Instead of working with the coverage area, we consider for each +\indent Instead of working with the coverage area, we consider for each sensor a set of points called primary points. We also assume that the sensing disk defined by a sensor is covered if all the primary points of this sensor are covered. @@ -509,7 +497,7 @@ increased or decreased if necessary) as references to ensure that the monitored region of interest is covered by the selected set of sensors, instead of using all the points in the area. -\noindent We can calculate the positions of the selected primary +\indent We can calculate the positions of the selected primary points in the circle disk of the sensing range of a wireless sensor node (see figure~\ref{fig2}) as follows:\\ $(p_x,p_y)$ = point center of wireless sensor node\\ @@ -549,13 +537,13 @@ $X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $. %To satisfy the coverage requirement, the set of the principal points that will represent all the sensor nodes in the monitored region as $PSET= \lbrace P_1,\ldots ,P_p, \ldots , P_{N_P^k} \rbrace $, where $N_P^k = N_{sp} * N^k $ and according to the proposed model in figure ~\ref{fig:cluster2}. These points can be used by the wireless sensor node leader which will be chosen in each region in A to build a new parameter $\alpha_{jp}$ that represents the coverage possibility for each principal point $P_p$ of each wireless sensor node $s_j$ in $A^k$ as in \eqref{eq12}:\\ -\noindent Our model is based on the model proposed by +\indent Our model is based on the model proposed by \cite{pedraza2006} where the objective is to find a maximum number of disjoint cover sets. To accomplish this goal, authors proposed an -integer program which forces undercoverage and overcoverage of targets +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_{j}$ which determine the +model, we consider binary variables $X_{j}$, which determine the activation of sensor $j$ in the sensing phase of the round. We also consider primary points as targets. The set of primary points is denoted by $P$ and the set of sensors by $J$. @@ -633,7 +621,7 @@ The first group of constraints indicates that some primary point $p$ should be covered by at least one sensor and, if it is not always the case, overcoverage and undercoverage variables help balancing the restriction equations by taking positive values. There are two main -objectives. First we limit the overcoverage of primary points in order to +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 @@ -689,11 +677,11 @@ defined by~\cite{HeinzelmanCB02} as energy consumption model for each wireless sensor node when transmitting or receiving packets. The energy of each node in a network is initialized randomly within the range 24-60~joules, and each sensor node will consume 0.2 watts during -the sensing period which will last 60 seconds. Thus, an +the sensing period, which will last 60 seconds. Thus, an active node will consume 12~joules during the sensing phase, while a sleeping node will use 0.002 joules. Each sensor node will not participate in the next round if its remaining energy is less than 12 -joules. In all experiments the parameters are set as follows: +joules. In all experiments, the parameters are set as follows: $R_s=5~m$, $w_{\Theta}=1$, and $w_{U}=|P^2|$. We evaluate the efficiency of our approach by using some performance @@ -806,11 +794,11 @@ simultaneously disconnected. \subsection{The percentage of stopped simulation runs} -We will now study the percentage of simulations which stopped due to +We will now study the percentage of simulations, which stopped due to network disconnections per round for each of the three approaches. Figure~\ref{fig6} illustrates the percentage of stopped simulation runs per round for 150 deployed nodes. It can be observed that the -simple heuristic is the approach which stops first because the nodes +simple heuristic is the approach, which stops first because the nodes are randomly chosen. Among the two proposed strategies, the centralized one first exhibits network disconnections. Thus, as explained previously, in case of the strategy with several subregions @@ -868,7 +856,7 @@ on a laptop of the decision phase (solving of the optimization problem) during one round. They are given for the different approaches and various numbers of sensors. The lack of any optimization explains why the heuristic has very low execution times. Conversely, the strategy -with one leader which requires to solve an optimization problem +with one leader, which requires to solve an optimization problem considering all the nodes presents redhibitory execution times. Moreover, increasing the network size by 50~nodes multiplies the time by almost a factor of 10. The strategy with two leaders has more @@ -878,7 +866,7 @@ nodes. Overall, to be able to deal with very large networks, a distributed method is clearly required. \begin{table}[ht] -\caption{The execution time(s) vs the number of sensors} +\caption{THE EXECUTION TIME(S) VS THE NUMBER OF SENSORS} % title of Table \centering @@ -974,12 +962,12 @@ 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. -In future work, we plan to study and propose a coverage protocol which +In future work, we plan to study and propose a coverage protocol, which computes all active sensor schedules in one time, using optimization methods such as swarms optimization or evolutionary algorithms. The round will still consist of 4 phases, but the - decision phase will compute the schedules for several sensing phases - which, aggregated together, define a kind of meta-sensing phase. + decision phase will compute the schedules for several sensing phases, + which aggregated together, define a kind of meta-sensing phase. The computation of all cover sets in one time is far more difficult, but will reduce the communication overhead. % use section* for acknowledgement -- 2.39.5