1 \documentclass[conference]{IEEEtran}
9 \hyphenation{op-tical net-works semi-conduc-tor}
14 \usepackage{times,amssymb,amsmath,latexsym}
19 \usepackage{algorithmic}
20 \usepackage[T1]{fontenc}
22 %\usepackage{algorithm}
23 %\usepackage{algpseudocode}
24 %\usepackage{algorithmwh}
25 \usepackage{subfigure}
28 \usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
33 \usepackage{graphicx,epstopdf}
34 \epstopdfsetup{suffix=}
35 \DeclareGraphicsExtensions{.ps}
36 \DeclareGraphicsRule{.ps}{pdf}{.pdf}{`ps2pdf -dEPSCrop -dNOSAFER #1 \noexpand\OutputFile}
40 %\title{ Coverage and Lifetime Optimization in Heterogeneous Energy Wireless Sensor Networks}
41 \title{Coverage and Lifetime Optimization in Heterogeneous Energy Wireless Sensor Networks}
42 %Activity Scheduling for Coverage and Lifetime Optimization in Wireless Sensor Networks}
44 % author names and affiliations
45 % use a multiple column layout for up to three different
47 \author{\IEEEauthorblockN{Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier}
48 \IEEEauthorblockA{FEMTO-ST Institute, UMR 6174 CNRS \\
49 University of Franche-Comt\'e \\
51 Email: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr}
52 %\email{\{ali.idness, karine.deschinkel, michel.salomon, raphael.couturier\}@univ-fcomte.fr}
54 %\IEEEauthorblockN{Homer Simpson}
55 %\IEEEauthorblockA{FEMTO-ST Institute, UMR CNRS, University of Franche-Comte, Belfort, France}
57 %\IEEEauthorblockN{James Kirk\\ and Montgomery Scott}
58 %\IEEEauthorblockA{FEMTO-ST Institute, UMR CNRS, University of Franche-Comte, Belfort, France}
64 One of the fundamental challenges in Wireless Sensor Networks (WSNs)
65 is the coverage preservation and the extension of the network lifetime
66 continuously and effectively when monitoring a certain area (or
67 region) of interest. In this paper, a coverage optimization protocol to
68 improve the lifetime in heterogeneous energy wireless sensor networks
69 is proposed. The area of interest is first divided into subregions
70 using a divide-and-conquer method and then the scheduling of sensor node
71 activity is planned for each subregion. The proposed scheduling
72 considers rounds during which a small number of nodes, remaining
73 active for sensing, is selected to ensure coverage. Each round
74 consists of four phases: (i)~Information Exchange, (ii)~Leader
75 Election, (iii)~Decision, and (iv)~Sensing. The decision process is
76 carried out by a leader node, which solves an integer program.
77 Simulation results show that the proposed approach can prolong the
78 network lifetime and improve the coverage performance.
82 Area Coverage, Network lifetime, Optimization, Scheduling, Distributed Protocol.
84 %\keywords{Area Coverage, Network lifetime, Optimization, Distributed Protocol}
86 \IEEEpeerreviewmaketitle
88 \section{Introduction}
90 \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
91 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
92 to a monitoring center
93 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}.
94 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
95 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}.
96 In this paper, we concentrate on the area
97 coverage problem, with the objective of maximizing the network
98 lifetime by using an adaptive scheduling. The area of interest is
99 divided into subregions and an activity scheduling for sensor nodes is
100 planned for each subregion.
101 In fact, the nodes in a subregion can be seen as a cluster where
102 each node sends sensing data to the cluster head or the sink node.
103 Furthermore, the activities in a subregion/cluster can continue even
104 if another cluster stops due to too many node failures.
105 Our scheduling scheme considers rounds, where a round starts with a
106 discovery phase to exchange information between sensors of the
107 subregion, in order to choose in a suitable manner a sensor node to
108 carry out a coverage strategy. This coverage strategy involves the
109 solving of an integer program, which provides the activation of the
110 sensors for the sensing phase of the current round.
112 The remainder of the paper is organized as follows. The next section
114 reviews the related work in the field. Section~\ref{pd} is devoted to
115 the scheduling strategy for energy-efficient coverage.
116 Section~\ref{cp} gives the coverage model formulation, which is used to
117 schedule the activation of sensors. Section~\ref{exp} shows the
118 simulation results obtained using the discrete event simulator OMNeT++ \cite{varga}. They fully demonstrate the usefulness of the
119 proposed approach. Finally, we give concluding remarks and some
120 suggestions for future works in Section~\ref{sec:conclusion}.
122 \section{Related works}
125 \noindent This section is dedicated to the various approaches proposed
126 in the literature for the coverage lifetime maximization problem,
127 where the objective is to optimally schedule sensors' activities in
128 order to extend network lifetime in a randomly deployed network. As
129 this problem is subject to a wide range of interpretations, we have chosen
130 to recall the main definitions and assumptions related to our work.
133 %\item Area Coverage: The main objective is to cover an area. The area coverage requires
134 %that the sensing range of working Active nodes cover the whole targeting area, which means any
135 %point in target area can be covered~\cite{Mihaela02,Raymond03}.
137 %\item Target Coverage: The objective is to cover a set of targets. Target coverage means that the discrete target points can be covered in any time. The sensing range of working Active nodes only monitors a finite number of discrete points in targeting area~\cite{Mihaela02,Raymond03}.
139 %\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}.
141 \subsection{Coverage}
144 The most discussed coverage problems in literature can be classified
145 into two types \cite{ma10}: area coverage (also called full or blanket
146 coverage) and target coverage. An area coverage problem is to find a
147 minimum number of sensors to work, such that each physical point in the
148 area is within the sensing range of at least one working sensor node.
149 Target coverage problem is to cover only a finite number of discrete
150 points called targets. This type of coverage has mainly military
151 applications. Our work will concentrate on the area coverage by design
152 and implementation of a strategy, which efficiently selects the active
153 nodes that must maintain both sensing coverage and network
154 connectivity and at the same time improve the lifetime of the wireless
155 sensor network. But, requiring that all physical points of the
156 considered region are covered may be too strict, especially where the
157 sensor network is not dense. Our approach represents an area covered
158 by a sensor as a set of primary points and tries to maximize the total
159 number of primary points that are covered in each round, while
160 minimizing overcoverage (points covered by multiple active sensors
163 \subsection{Lifetime}
166 Various definitions exist for the lifetime of a sensor
167 network~\cite{die09}. The main definitions proposed in the literature are
168 related to the remaining energy of the nodes or to the coverage percentage.
169 The lifetime of the network is mainly defined as the amount
170 of time during which the network can satisfy its coverage objective (the
171 amount of time that the network can cover a given percentage of its
172 area or targets of interest). In this work, we assume that the network
173 is alive until all nodes have been drained of their energy or the
174 sensor network becomes disconnected, and we measure the coverage ratio
175 during the WSN lifetime. Network connectivity is important because an
176 active sensor node without connectivity towards a base station cannot
177 transmit information on an event in the area that it monitors.
179 \subsection{Activity scheduling}
180 %{\bf Activity scheduling}
182 Activity scheduling is to schedule the activation and deactivation of
183 sensor nodes. The basic objective is to decide which sensors are in
184 what states (active or sleeping mode) and for how long, so that the
185 application coverage requirement can be guaranteed and the network
186 lifetime can be prolonged. Various approaches, including centralized,
187 distributed, and localized algorithms, have been proposed for activity
188 scheduling. In distributed algorithms, each node in the network
189 autonomously makes decisions on whether to turn on or turn off itself
190 only using local neighbor information. In centralized algorithms, a
191 central controller (a node or base station) informs every sensors of
192 the time intervals to be activated.
194 \subsection{Distributed approaches}
195 %{\bf Distributed approaches}
197 Some distributed algorithms have been developed
198 in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02} to perform the
199 scheduling. Distributed algorithms typically operate in rounds for
200 a predetermined duration. At the beginning of each round, a sensor
201 exchanges information with its neighbors and makes a decision to either
202 remain turned on or to go to sleep for the round. This decision is
203 basically made on simple greedy criteria like the largest uncovered
204 area \cite{Berman05efficientenergy}, maximum uncovered targets
205 \cite{1240799}. In \cite{Tian02}, the scheduling scheme is divided
206 into rounds, where each round has a self-scheduling phase followed by
207 a sensing phase. Each sensor broadcasts a message containing the node ID
208 and the node location to its neighbors at the beginning of each round. A
209 sensor determines its status by a rule named off-duty eligible rule,
210 which tells him to turn off if its sensing area is covered by its
211 neighbors. A back-off scheme is introduced to let each sensor delay
212 the decision process with a random period of time, in order to avoid
213 simultaneous conflicting decisions between nodes and lack of coverage on any area.
214 \cite{Prasad:2007:DAL:1782174.1782218} defines a model for capturing
215 the dependencies between different cover sets and proposes localized
216 heuristic based on this dependency. The algorithm consists of two
217 phases, an initial setup phase during which each sensor computes and
218 prioritizes the covers and a sensing phase during which each sensor
219 first decides its on/off status, and then remains on or off for the
220 rest of the duration. Authors in \cite{chin2007} propose a novel
221 distributed heuristic named Distributed Energy-efficient Scheduling
222 for k-coverage (DESK) so that the energy consumption among all the
223 sensors is balanced, and network lifetime is maximized while the
224 coverage requirement is being maintained. This algorithm works in
225 round, requires only 1-sensing-hop-neighbor information, and a sensor
226 decides its status (active/sleep) based on its perimeter coverage
227 computed through the k-Non-Unit-disk coverage algorithm proposed in
228 \cite{Huang:2003:CPW:941350.941367}.
230 Some other approaches do not consider a synchronized and predetermined
231 period of time where the sensors are active or not. Indeed, each
232 sensor maintains its own timer and its wake-up time is randomized
233 \cite{Ye03} or regulated \cite{cardei05} over time.
234 %A ecrire \cite{Abrams:2004:SKA:984622.984684}p33
236 %The scheduling information is disseminated throughout the network and only sensors in the active state are responsible
237 %for monitoring all targets, while all other nodes are in a low-energy sleep mode. The nodes decide cooperatively which of them will remain in sleep mode for a certain
240 %one way of increasing lifeteime is by turning off redundant nodes to sleep mode to conserve energy while active nodes provide essential coverage, which improves fault tolerance.
242 %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.
244 \subsection{Centralized approaches}
245 %{\bf Centralized approaches}
247 Power efficient centralized schemes differ according to several
248 criteria \cite{Cardei:2006:ECP:1646656.1646898}, such as the coverage
249 objective (target coverage or area coverage), the node deployment
250 method (random or deterministic) and the heterogeneity of sensor nodes
251 (common sensing range, common battery lifetime). The major approach is
252 to divide/organize the sensors into a suitable number of set covers
253 where each set completely covers an interest region and to activate
254 these set covers successively.
256 The first algorithms proposed in the literature consider that the cover
257 sets are disjoint: a sensor node appears in exactly one of the
258 generated cover sets. For instance, Slijepcevic and Potkonjak
259 \cite{Slijepcevic01powerefficient} propose an algorithm, which
260 allocates sensor nodes in mutually independent sets to monitor an area
261 divided into several fields. Their algorithm builds a cover set by
262 including in priority the sensor nodes, which cover critical fields,
263 that is to say fields that are covered by the smallest number of
264 sensors. The time complexity of their heuristic is $O(n^2)$ where $n$
265 is the number of sensors. In~\cite{cardei02}, a graph coloring
266 technique is described to achieve energy savings by organizing the sensor nodes
267 into a maximum number of disjoint dominating sets, which are activated
268 successively. The dominating sets do not guarantee the coverage of the
269 whole region of interest. Abrams et
270 al.~\cite{Abrams:2004:SKA:984622.984684} design three approximation
271 algorithms for a variation of the set k-cover problem, where the
272 objective is to partition the sensors into covers such that the number
273 of covers that includes an area, summed over all areas, is maximized.
274 Their work builds upon previous work
275 in~\cite{Slijepcevic01powerefficient} and the generated cover sets do
276 not provide complete coverage of the monitoring zone.
278 %examine the target coverage problem by disjoint cover sets but relax the requirement that every cover set monitor all the targets and try to maximize the number of times the targets are covered by the partition. They propose various algorithms and establish approximation ratio.
280 In~\cite{Cardei:2005:IWS:1160086.1160098}, the authors propose a
281 heuristic to compute the disjoint set covers (DSC). In order to
282 compute the maximum number of covers, they first transform DSC into a
283 maximum-flow problem, which is then formulated as a mixed integer
284 programming problem (MIP). Based on the solution of the MIP, they
285 design a heuristic to compute the final number of covers. The results
286 show a slight performance improvement in terms of the number of
287 produced DSC in comparison to~\cite{Slijepcevic01powerefficient}, but
288 it incurs higher execution time due to the complexity of the mixed
289 integer programming solving. %Cardei and Du
290 \cite{Cardei:2005:IWS:1160086.1160098} propose a method to efficiently
291 compute the maximum number of disjoint set covers such that each set
292 can monitor all targets. They first transform the problem into a
293 maximum flow problem, which is formulated as a mixed integer
294 programming (MIP). Then their heuristic uses the output of the MIP to
295 compute disjoint set covers. Results show that this heuristic
296 provides a number of set covers slightly larger compared to
297 \cite{Slijepcevic01powerefficient} but with a larger execution time
298 due to the complexity of the mixed integer programming resolution.
299 Zorbas et al. \cite{Zorbas2007} present B\{GOP\}, a centralized
300 coverage algorithm introducing sensor candidate categorization
301 depending on their coverage status and the notion of critical target
302 to call targets that are associated with a small number of
303 sensors. The total running time of their heuristic is $0(m n^2)$ where
304 $n$ is the number of sensors, and $m$ the number of targets. Compared
305 to algorithm's results of Slijepcevic and Potkonjak
306 \cite{Slijepcevic01powerefficient}, their heuristic produces more
307 cover sets with a slight growth rate in execution time.
308 %More recently Manju and Pujari\cite{Manju2011}
310 In the case of non-disjoint algorithms \cite{Manju2011}, sensors may
311 participate in more than one cover set. In some cases, this may
312 prolong the lifetime of the network in comparison to the disjoint
313 cover set algorithms, but designing algorithms for non-disjoint cover
314 sets generally induces a higher order of complexity. Moreover, in
315 case of a sensor's failure, non-disjoint scheduling policies are less
316 resilient and less reliable because a sensor may be involved in more
317 than one cover sets. For instance, Cardei et al.~\cite{cardei05bis}
318 present a linear programming (LP) solution and a greedy approach to
319 extend the sensor network lifetime by organizing the sensors into a
320 maximal number of non-disjoint cover sets. Simulation results show
321 that by allowing sensors to participate in multiple sets, the network
322 lifetime increases compared with related
323 work~\cite{Cardei:2005:IWS:1160086.1160098}. In~\cite{berman04}, the
324 authors have formulated the lifetime problem and suggested another
325 (LP) technique to solve this problem. A centralized solution based on the Garg-K\"{o}nemann
326 algorithm~\cite{garg98}, provably near
327 the optimal solution, is also proposed.
329 \subsection{Our contribution}
330 %{\bf Our contribution}
332 There are three main questions, which should be addressed to build a
333 scheduling strategy. We give a brief answer to these three questions
334 to describe our approach before going into details in the subsequent
337 \item {\bf How must the phases for information exchange, decision and
338 sensing be planned over time?} Our algorithm divides the time line
339 into a number of rounds. Each round contains 4 phases: Information
340 Exchange, Leader Election, Decision, and Sensing.
342 \item {\bf What are the rules to decide which node has to be turned on
343 or off?} Our algorithm tends to limit the overcoverage of points of
344 interest to avoid turning on too many sensors covering the same
345 areas at the same time, and tries to prevent undercoverage. The
346 decision is a good compromise between these two conflicting
349 \item {\bf Which node should make such a decision?} As mentioned in
350 \cite{pc10}, both centralized and distributed algorithms have their
351 own advantages and disadvantages. Centralized coverage algorithms
352 have the advantage of requiring very low processing power from the
353 sensor nodes, which have usually limited processing capabilities.
354 Distributed algorithms are very adaptable to the dynamic and
355 scalable nature of sensors network. Authors in \cite{pc10} conclude
356 that there is a threshold in terms of network size to switch from a
357 localized to a centralized algorithm. Indeed, the exchange of
358 messages in large networks may consume a considerable amount of
359 energy in a centralized approach compared to a distributed one. Our
360 work does not consider only one leader to compute and to broadcast
361 the scheduling decision to all the sensors. When the network size
362 increases, the network is divided into many subregions and the
363 decision is made by a leader in each subregion.
366 \section{Activity scheduling}
369 We consider a randomly and uniformly deployed network consisting of
370 static wireless sensors. The wireless sensors are deployed in high
371 density to ensure initially a full coverage of the interested area. We
372 assume that all nodes are homogeneous in terms of communication and
373 processing capabilities and heterogeneous in term of energy provision.
374 The location information is available to the sensor node either
375 through hardware such as embedded GPS or through location discovery
376 algorithms. The area of interest can be divided using the
377 divide-and-conquer strategy into smaller areas called subregions and
378 then our coverage protocol will be implemented in each subregion
379 simultaneously. Our protocol works in rounds fashion as shown in
382 %Given the interested Area $A$, the wireless sensor nodes set $S=\lbrace s_1,\ldots,s_N \rbrace $ that are deployed randomly and uniformly in this area such that they are ensure a full coverage for A. The Area A is divided into regions $A=\lbrace A^1,\ldots,A^k,\ldots, A^{N_R} \rbrace$. We suppose that each sensor node $s_i$ know its location and its region. We will have a subset $SSET^k =\lbrace s_1,...,s_j,...,s_{N^k} \rbrace $ , where $s_N = s_{N^1} + s_{N^2} +,\ldots,+ s_{N^k} +,\ldots,+s_{N^R}$. Each sensor node $s_i$ has the same initial energy $IE_i$ in the first time and the current residual energy $RE_i$ equal to $IE_i$ in the first time for each $s_i$ in A. \\
386 \includegraphics[width=85mm]{FirstModel.eps} % 70mm
387 \caption{Multi-round coverage protocol}
391 Each round is divided into 4 phases : Information (INFO) Exchange,
392 Leader Election, Decision, and Sensing. For each round there is
393 exactly one set cover responsible for the sensing task. This protocol is
394 more reliable against an unexpected node failure because it works
395 in rounds. On the one hand, if a node failure is detected before
396 making the decision, the node will not participate to this phase, and,
397 on the other hand, if the node failure occurs after the decision, the
398 sensing task of the network will be temporarily affected: only during
399 the period of sensing until a new round starts, since a new set cover
400 will take charge of the sensing task in the next round. The energy
401 consumption and some other constraints can easily be taken into
402 account since the sensors can update and then exchange their
403 information (including their residual energy) at the beginning of each
404 round. However, the pre-sensing phases (INFO Exchange, Leader
405 Election, Decision) are energy consuming for some nodes, even when
406 they do not join the network to monitor the area. Below, we describe
407 each phase in more details.
409 \subsection{Information exchange phase}
411 Each sensor node $j$ sends its position, remaining energy $RE_j$, and
412 the number of local neighbours $NBR_j$ to all wireless sensor nodes in
413 its subregion by using an INFO packet and then listens to the packets
414 sent from other nodes. After that, each node will have information
415 about all the sensor nodes in the subregion. In our model, the
416 remaining energy corresponds to the time that a sensor can live in the
419 %\subsection{\textbf Working Phase:}
421 %The working phase works in rounding fashion. Each round include 3 steps described as follow :
423 \subsection{Leader election phase}
424 This step includes choosing the Wireless Sensor Node Leader (WSNL),
425 which will be responsible for executing the coverage algorithm. Each
426 subregion in the area of interest will select its own WSNL
427 independently for each round. All the sensor nodes cooperate to
428 select WSNL. The nodes in the same subregion will select the leader
429 based on the received information from all other nodes in the same
430 subregion. The selection criteria in order of priority are: larger
431 number of neighbours, larger remaining energy, and then in case of
432 equality, larger index.
434 \subsection{Decision phase}
435 The WSNL will solve an integer program (see section~\ref{cp}) to
436 select which sensors will be activated in the following sensing phase
437 to cover the subregion. WSNL will send Active-Sleep packet to each
438 sensor in the subregion based on the algorithm's results.
439 %The main goal in this step after choosing the WSNL is to produce the best representative active nodes set that will take the responsibility of covering the whole region $A^k$ with minimum number of sensor nodes to prolong the lifetime in the wireless sensor network. For our problem, in each round we need to select the minimum set of sensor nodes to improve the lifetime of the network and in the same time taking into account covering the region $A^k$ . We need an optimal solution with tradeoff between our two conflicting objectives.
440 %The above region coverage problem can be formulated as a Multi-objective optimization problem and we can use the Binary Particle Swarm Optimization technique to solve it.
442 \subsection{Sensing phase}
443 Active sensors in the round will execute their sensing task to
444 preserve maximal coverage in the region of interest. We will assume
445 that the cost of keeping a node awake (or asleep) for sensing task is
446 the same for all wireless sensor nodes in the network. Each sensor
447 will receive an Active-Sleep packet from WSNL informing it to stay
448 awake or to go to sleep for a time equal to the period of sensing until
449 starting a new round.
451 %\subsection{Sensing coverage model}
454 %\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.
455 %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$.
456 \indent We consider a boolean disk coverage model which is the most
457 widely used sensor coverage model in the literature. Each sensor has a
458 constant sensing range $R_s$. All space points within a disk centered
459 at the sensor with the radius of the sensing range is said to be
460 covered by this sensor. We also assume that the communication range is
461 at least twice the size of the sensing range. In fact, Zhang and
462 Zhou~\cite{Zhang05} proved that if the transmission range fulfills the
463 previous hypothesis, a complete coverage of a convex area implies
464 connectivity among the working nodes in the active mode.
465 %To calculate the coverage ratio for the area of interest, we can propose the following coverage model which is called Wireless Sensor Node Area Coverage Model to ensure that all the area within each node sensing range are covered. We can calculate the positions of the points in the circle disc of the sensing range of wireless sensor node based on the Unit Circle in figure~\ref{fig:cluster1}:
470 %%\includegraphics[scale=0.25]{fig1.pdf}\\ %& \includegraphics[scale=0.10]{1.pdf} \\
471 %%(A) Figure 1 & (B) Figure 2
473 %\caption{Unit Circle in radians. }
474 %\label{fig:cluster1}
477 %By using the Unit Circle in figure~\ref{fig:cluster1},
478 %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.
479 % 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.
481 \indent Instead of working with the coverage area, we consider for each
482 sensor a set of points called primary points. We also assume that the
483 sensing disk defined by a sensor is covered if all the primary points of
484 this sensor are covered.
488 %%\includegraphics[scale=0.25]{fig2.pdf}\\ %& \includegraphics[scale=0.10]{1.pdf} \\
489 %%(A) Figure 1 & (B) Figure 2
491 %\caption{Wireless Sensor Node Area Coverage Model.}
492 %\label{fig:cluster2}
494 By knowing the position (point center: ($p_x,p_y$)) of a wireless
495 sensor node and its $R_s$, we calculate the primary points directly
496 based on the proposed model. We use these primary points (that can be
497 increased or decreased if necessary) as references to ensure that the
498 monitored region of interest is covered by the selected set of
499 sensors, instead of using all the points in the area.
501 \indent We can calculate the positions of the selected primary
502 points in the circle disk of the sensing range of a wireless sensor
503 node (see figure~\ref{fig2}) as follows:\\
504 $(p_x,p_y)$ = point center of wireless sensor node\\
506 $X_2=( p_x + R_s * (1), p_y + R_s * (0) )$\\
507 $X_3=( p_x + R_s * (-1), p_y + R_s * (0)) $\\
508 $X_4=( p_x + R_s * (0), p_y + R_s * (1) )$\\
509 $X_5=( p_x + R_s * (0), p_y + R_s * (-1 )) $\\
510 $X_6= ( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (0)) $\\
511 $X_7=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (0))$\\
512 $X_8=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
513 $X_9=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
514 $X_{10}=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
515 $X_{11}=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
516 $X_{12}=( p_x + R_s * (0), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
517 $X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $.
521 % \begin{multicols}{6}
523 %\includegraphics[scale=0.10]{fig21.pdf}\\~ ~ ~(a)
524 %\includegraphics[scale=0.10]{fig22.pdf}\\~ ~ ~(b)
525 \includegraphics[scale=0.25]{principles13.eps}
526 %\includegraphics[scale=0.10]{fig25.pdf}\\~ ~ ~(d)
527 %\includegraphics[scale=0.10]{fig26.pdf}\\~ ~ ~(e)
528 %\includegraphics[scale=0.10]{fig27.pdf}\\~ ~ ~(f)
530 \caption{Wireless sensor node represented by 13 primary points}
534 \section{Coverage problem formulation}
536 %We can formulate our optimization problem as energy cost minimization by minimize the number of active sensor nodes and maximizing the coverage rate at the same time in each $A^k$ . This optimization problem can be formulated as follow: Since that we use a homogeneous wireless sensor network, we will assume that the cost of keeping a node awake is the same for all wireless sensor nodes in the network. We can define the decision parameter $X_j$ as in \eqref{eq11}:\\
539 %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}:\\
541 \indent Our model is based on the model proposed by
542 \cite{pedraza2006} where the objective is to find a maximum number of
543 disjoint cover sets. To accomplish this goal, authors proposed an
544 integer program, which forces undercoverage and overcoverage of targets
545 to become minimal at the same time. They use binary variables
546 $x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our
547 model, we consider binary variables $X_{j}$, which determine the
548 activation of sensor $j$ in the sensing phase of the round. We also
549 consider primary points as targets. The set of primary points is
550 denoted by $P$ and the set of sensors by $J$.
552 \noindent For a primary point $p$, let $\alpha_{jp}$ denote the
553 indicator function of whether the point $p$ is covered, that is:
555 \alpha_{jp} = \left \{
557 1 & \mbox{if the primary point $p$ is covered} \\
558 & \mbox{by sensor node $j$}, \\
559 0 & \mbox{otherwise.}\\
563 The number of active sensors that cover the primary point $p$ is equal
564 to $\sum_{j \in J} \alpha_{jp} * X_{j}$ where:
568 1& \mbox{if sensor $j$ is active,} \\
569 0 & \mbox{otherwise.}\\
573 We define the Overcoverage variable $\Theta_{p}$ as:
575 \Theta_{p} = \left \{
577 0 & \mbox{if the primary point}\\
578 & \mbox{$p$ is not covered,}\\
579 \left( \sum_{j \in J} \alpha_{jp} * X_{j} \right)- 1 & \mbox{otherwise.}\\
583 \noindent More precisely, $\Theta_{p}$ represents the number of active
584 sensor nodes minus one that cover the primary point $p$.\\
585 The Undercoverage variable $U_{p}$ of the primary point $p$ is defined
590 1 &\mbox{if the primary point $p$ is not covered,} \\
591 0 & \mbox{otherwise.}\\
596 \noindent Our coverage optimization problem can then be formulated as follows\\
597 \begin{equation} \label{eq:ip2r}
600 \min \sum_{p \in P} (w_{\theta} \Theta_{p} + w_{U} U_{p})&\\
601 \textrm{subject to :}&\\
602 \sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, &\forall p \in P\\
604 %\sum_{t \in T} X_{j,t} \leq \frac{RE_j}{e_t} &\forall j \in J \\
606 \Theta_{p}\in \mathbb{N} , &\forall p \in P\\
607 U_{p} \in \{0,1\}, &\forall p \in P \\
608 X_{j} \in \{0,1\}, &\forall j \in J
613 \item $X_{j}$ : indicates whether or not the sensor $j$ is actively
614 sensing in the round (1 if yes and 0 if not);
615 \item $\Theta_{p}$ : {\it overcoverage}, the number of sensors minus
616 one that are covering the primary point $p$;
617 \item $U_{p}$ : {\it undercoverage}, indicates whether or not the primary point
618 $p$ is being covered (1 if not covered and 0 if covered).
621 The first group of constraints indicates that some primary point $p$
622 should be covered by at least one sensor and, if it is not always the
623 case, overcoverage and undercoverage variables help balancing the
624 restriction equations by taking positive values. There are two main
625 objectives. First, we limit the overcoverage of primary points in order to
626 activate a minimum number of sensors. Second we prevent the absence of monitoring on
627 some parts of the subregion by minimizing the undercoverage. The
628 weights $w_\theta$ and $w_U$ must be properly chosen so as to
629 guarantee that the maximum number of points are covered during each
632 %In equation \eqref{eq15}, there are two main objectives: the first one using the Overcoverage parameter to minimize the number of active sensor nodes in the produced final solution vector $X$ which leads to improve the life time of wireless sensor network. The second goal by using the Undercoverage parameter to maximize the coverage in the region by means of covering each primary point in $SSET^k$.The two objectives are achieved at the same time. The constraint which represented in equation \eqref{eq16} refer to the coverage function for each primary point $P_p$ in $SSET^k$ , where each $P_p$ should be covered by
633 %at least one sensor node in $A^k$. The objective function in \eqref{eq15} involving two main objectives to be optimized simultaneously, where optimal decisions need to be taken in the presence of trade-offs between the two conflicting main objectives in \eqref{eq15} and this refer to that our coverage optimization problem is a multi-objective optimization problem and we can use the BPSO to solve it. The concept of Overcoverage and Undercoverage inspired from ~\cite{Fernan12} but we use it with our model as stated in subsection \ref{Sensing Coverage Model} with some modification to be applied later by BPSO.
634 %\subsection{Notations and assumptions}
637 %\item $m$ : the number of targets
638 %\item $n$ : the number of sensors
639 %\item $K$ : maximal number of cover sets
640 %\item $i$ : index of target ($i=1..m$)
641 %\item $j$ : index of sensor ($j=1..n$)
642 %\item $k$ : index of cover set ($k=1..K$)
643 %\item $T_0$ : initial set of targets
644 %\item $S_0$ : initial set of sensors
645 %\item $T $ : set of targets which are not covered by at least one cover set
646 %\item $S$ : set of available sensors
647 %\item $S_0(i)$ : set of sensors which cover the target $i$
648 %\item $T_0(j)$ : set of targets covered by sensor $j$
649 %\item $C_k$ : cover set of index $k$
650 %\item $T(C_k)$ : set of targets covered by the cover set $k$
651 %\item $NS(i)$ : set of available sensors which cover the target $i$
652 %\item $NC(i)$ : set of cover sets which do not cover the target $i$
653 %\item $|.|$ : cardinality of the set
657 \section{Simulation results}
660 In this section, we conducted a series of simulations to evaluate the
661 efficiency and the relevance of our approach, using the discrete event
662 simulator OMNeT++ \cite{varga}. We performed simulations for five
663 different densities varying from 50 to 250~nodes. Experimental results
664 were obtained from randomly generated networks in which nodes are
665 deployed over a $(50 \times 25)~m^2 $ sensing field.
666 More precisely, the deployment is controlled at a coarse scale in
667 order to ensure that the deployed nodes can fully cover the sensing
668 field with the given sensing range.
669 10~simulation runs are performed with
670 different network topologies for each node density. The results
671 presented hereafter are the average of these 10 runs. A simulation
672 ends when all the nodes are dead or the sensor network becomes
673 disconnected (some nodes may not be able to send, to a base station, an
676 Our proposed coverage protocol uses the radio energy dissipation model
677 defined by~\cite{HeinzelmanCB02} as energy consumption model for each
678 wireless sensor node when transmitting or receiving packets. The
679 energy of each node in a network is initialized randomly within the
680 range 24-60~joules, and each sensor node will consume 0.2 watts during
681 the sensing period, which will last 60 seconds. Thus, an
682 active node will consume 12~joules during the sensing phase, while a
683 sleeping node will use 0.002 joules. Each sensor node will not
684 participate in the next round if its remaining energy is less than 12
685 joules. In all experiments, the parameters are set as follows:
686 $R_s=5~m$, $w_{\Theta}=1$, and $w_{U}=|P^2|$.
688 We evaluate the efficiency of our approach by using some performance
689 metrics such as: coverage ratio, number of active nodes ratio, energy
690 saving ratio, energy consumption, network lifetime, execution time,
691 and number of stopped simulation runs. Our approach called strategy~2
692 (with two leaders) works with two subregions, each one having a size
693 of $(25 \times 25)~m^2$. Our strategy will be compared with two other
694 approaches. The first one, called strategy~1 (with one leader), works
695 as strategy~2, but considers only one region of $(50 \times 25)$ $m^2$
696 with only one leader. The other approach, called Simple Heuristic,
697 consists in uniformly dividing the region into squares of $(5 \times
698 5)~m^2$. During the decision phase, in each square, a sensor is
699 randomly chosen, it will remain turned on for the coming sensing
702 \subsection{The impact of the number of rounds on the coverage ratio}
704 In this experiment, the coverage ratio measures how much the area of a
705 sensor field is covered. In our case, the coverage ratio is regarded
706 as the number of primary points covered among the set of all primary
707 points within the field. Figure~\ref{fig3} shows the impact of the
708 number of rounds on the average coverage ratio for 150 deployed nodes
709 for the three approaches. It can be seen that the three approaches
710 give similar coverage ratios during the first rounds. From the
711 9th~round the coverage ratio decreases continuously with the simple
712 heuristic, while the two other strategies provide superior coverage to
713 $90\%$ for five more rounds. Coverage ratio decreases when the number
714 of rounds increases due to dead nodes. Although some nodes are dead,
715 thanks to strategy~1 or~2, other nodes are preserved to ensure the
716 coverage. Moreover, when we have a dense sensor network, it leads to
717 maintain the full coverage for a larger number of rounds. Strategy~2 is
718 slightly more efficient than strategy 1, because strategy~2 subdivides
719 the region into 2~subregions and if one of the two subregions becomes
720 disconnected, the coverage may be still ensured in the remaining
726 \includegraphics[scale=0.5]{TheCoverageRatio150g.eps} %\\~ ~ ~(a)
727 \caption{The impact of the number of rounds on the coverage ratio for 150 deployed nodes}
731 \subsection{The impact of the number of rounds on the active sensors ratio}
733 It is important to have as few active nodes as possible in each round,
734 in order to minimize the communication overhead and maximize the
735 network lifetime. This point is assessed through the Active Sensors
736 Ratio (ASR), which is defined as follows:
739 \mbox{ASR}(\%) = \frac{\mbox{Number of active sensors
740 during the current sensing phase}}{\mbox{Total number of sensors in the network
741 for the region}} \times 100.
743 Figure~\ref{fig4} shows the average active nodes ratio versus rounds
744 for 150 deployed nodes.
748 \includegraphics[scale=0.5]{TheActiveSensorRatio150g.eps} %\\~ ~ ~(a)
749 \caption{The impact of the number of rounds on the active sensors ratio for 150 deployed nodes }
753 The results presented in figure~\ref{fig4} show the superiority of
754 both proposed strategies, the strategy with two leaders and the one
755 with a single leader, in comparison with the simple heuristic. The
756 strategy with one leader uses less active nodes than the strategy with
757 two leaders until the last rounds, because it uses central control on
758 the whole sensing field. The advantage of the strategy~2 approach is
759 that even if a network is disconnected in one subregion, the other one
760 usually continues the optimization process, and this extends the
761 lifetime of the network.
763 \subsection{The impact of the number of rounds on the energy saving ratio}
765 In this experiment, we consider a performance metric linked to energy.
766 This metric, called Energy Saving Ratio (ESR), is defined by:
769 \mbox{ESR}(\%) = \frac{\mbox{Number of alive sensors during this round}}
770 {\mbox{Total number of sensors in the network for the region}} \times 100.
772 The longer the ratio is, the more redundant sensor nodes are
773 switched off, and consequently the longer the network may live.
774 Figure~\ref{fig5} shows the average Energy Saving Ratio versus rounds
775 for all three approaches and for 150 deployed nodes.
779 % \begin{multicols}{6}
781 \includegraphics[scale=0.5]{TheEnergySavingRatio150g.eps} %\\~ ~ ~(a)
782 \caption{The impact of the number of rounds on the energy saving ratio for 150 deployed nodes}
786 The simulation results show that our strategies allow to efficiently
787 save energy by turning off some sensors during the sensing phase. As
788 expected, the strategy with one leader is usually slightly better than
789 the second strategy, because the global optimization permits to turn
790 off more sensors. Indeed, when there are two subregions more nodes
791 remain awake near the border shared by them. Note that again as the
792 number of rounds increases the two leaders' strategy becomes the most
793 performing one, since it takes longer to have the two subregion networks
794 simultaneously disconnected.
796 \subsection{The percentage of stopped simulation runs}
798 We will now study the percentage of simulations, which stopped due to
799 network disconnections per round for each of the three approaches.
800 Figure~\ref{fig6} illustrates the percentage of stopped simulation
801 runs per round for 150 deployed nodes. It can be observed that the
802 simple heuristic is the approach, which stops first because the nodes
803 are randomly chosen. Among the two proposed strategies, the
804 centralized one first exhibits network disconnections. Thus, as
805 explained previously, in case of the strategy with several subregions
806 the optimization effectively continues as long as a network in a
807 subregion is still connected. This longer partial coverage
808 optimization participates in extending the network lifetime.
812 \includegraphics[scale=0.5]{TheNumberofStoppedSimulationRuns150g.eps}
813 \caption{The percentage of stopped simulation runs compared to the number of rounds for 150 deployed nodes }
817 \subsection{The energy consumption}
819 In this experiment, we study the effect of the multi-hop communication
820 protocol on the performance of the strategy with two leaders and
821 compare it with the other two approaches. The average energy
822 consumption resulting from wireless communications is calculated
823 by taking into account the energy spent by all the nodes when transmitting and
824 receiving packets during the network lifetime. This average value,
825 which is obtained for 10~simulation runs, is then divided by the
826 average number of rounds to define a metric allowing a fair comparison
827 between networks having different densities.
829 Figure~\ref{fig7} illustrates the energy consumption for the different
830 network sizes and the three approaches. The results show that the
831 strategy with two leaders is the most competitive from the energy
832 consumption point of view. A centralized method, like the strategy
833 with one leader, has a high energy consumption due to many
834 communications. In fact, a distributed method greatly reduces the
835 number of communications thanks to the partitioning of the initial
836 network in several independent subnetworks. Let us notice that even if
837 a centralized method consumes far more energy than the simple
838 heuristic, since the energy cost of communications during a round is a
839 small part of the energy spent in the sensing phase, the
840 communications have a small impact on the network lifetime.
844 \includegraphics[scale=0.5]{TheEnergyConsumptiong.eps}
845 \caption{The energy consumption}
849 \subsection{The impact of the number of sensors on execution time}
851 A sensor node has limited energy resources and computing power,
852 therefore it is important that the proposed algorithm has the shortest
853 possible execution time. The energy of a sensor node must be mainly
854 used for the sensing phase, not for the pre-sensing ones.
855 Table~\ref{table1} gives the average execution times in seconds
856 on a laptop of the decision phase (solving of the optimization problem)
857 during one round. They are given for the different approaches and
858 various numbers of sensors. The lack of any optimization explains why
859 the heuristic has very low execution times. Conversely, the strategy
860 with one leader, which requires to solve an optimization problem
861 considering all the nodes presents redhibitory execution times.
862 Moreover, increasing the network size by 50~nodes multiplies the time
863 by almost a factor of 10. The strategy with two leaders has more
864 suitable times. We think that in distributed fashion the solving of
865 the optimization problem in a subregion can be tackled by sensor
866 nodes. Overall, to be able to deal with very large networks, a
867 distributed method is clearly required.
870 \caption{THE EXECUTION TIME(S) VS THE NUMBER OF SENSORS}
874 % used for centering table
875 \begin{tabular}{|c|c|c|c|}
876 % centered columns (4 columns)
878 %inserts double horizontal lines
879 Sensors number & Strategy~2 & Strategy~1 & Simple heuristic \\ [0.5ex]
880 & (with two leaders) & (with one leader) & \\ [0.5ex]
881 %Case & Strategy (with Two Leaders) & Strategy (with One Leader) & Simple Heuristic \\ [0.5ex]
885 % inserts single horizontal line
886 50 & 0.097 & 0.189 & 0.001 \\
887 % inserting body of the table
889 100 & 0.419 & 1.972 & 0.0032 \\
891 150 & 1.295 & 13.098 & 0.0032 \\
893 200 & 4.54 & 169.469 & 0.0046 \\
895 250 & 12.252 & 1581.163 & 0.0056 \\
896 % [1ex] adds vertical space
901 % is used to refer this table in the text
904 \subsection{The network lifetime}
906 Finally, we have defined the network lifetime as the time until all
907 nodes have been drained of their energy or each sensor network
908 monitoring an area has become disconnected. In figure~\ref{fig8}, the
909 network lifetime for different network sizes and for both strategy
910 with two leaders and the simple heuristic is illustrated.
911 We do not consider anymore the centralized strategy with one
912 leader, because, as shown above, this strategy results in execution
913 times that quickly become unsuitable for a sensor network.
917 % \begin{multicols}{6}
919 \includegraphics[scale=0.5]{TheNetworkLifetimeg.eps} %\\~ ~ ~(a)
920 \caption{The network lifetime }
924 As highlighted by figure~\ref{fig8}, the network lifetime obviously
925 increases when the size of the network increases, with our approach
926 that leads to the larger lifetime improvement. By choosing the best
927 suited nodes, for each round, to cover the region of interest and by
928 letting the other ones sleep in order to be used later in next rounds,
929 our strategy efficiently prolonges the network lifetime. Comparison shows that
930 the larger the sensor number is, the more our strategies outperform
931 the simple heuristic. Strategy~2, which uses two leaders, is the best
932 one because it is robust to network disconnection in one subregion. It
933 also means that distributing the algorithm in each node and
934 subdividing the sensing field into many subregions, which are managed
935 independently and simultaneously, is the most relevant way to maximize
936 the lifetime of a network.
938 \section{Conclusion and future works}
939 \label{sec:conclusion}
941 In this paper, we have addressed the problem of the coverage and the lifetime
942 optimization in wireless sensor networks. This is a key issue as
943 sensor nodes have limited resources in terms of memory, energy and
944 computational power. To cope with this problem, the field of sensing
945 is divided into smaller subregions using the concept of
946 divide-and-conquer method, and then a multi-rounds coverage protocol
947 will optimize coverage and lifetime performances in each subregion.
948 The proposed protocol combines two efficient techniques: network
949 leader election and sensor activity scheduling, where the challenges
950 include how to select the most efficient leader in each subregion and
951 the best representative active nodes that will optimize the network lifetime
952 while taking the responsibility of covering the corresponding
953 subregion. The network lifetime in each subregion is divided into
954 rounds, each round consists of four phases: (i) Information Exchange,
955 (ii) Leader Election, (iii) an optimization-based Decision in order to
956 select the nodes remaining active for the last phase, and (iv)
957 Sensing. The simulations show the relevance of the proposed
958 protocol in terms of lifetime, coverage ratio, active sensors ratio,
959 energy saving, energy consumption, execution time, and the number of
960 stopped simulation runs due to network disconnection. Indeed, when
961 dealing with large and dense wireless sensor networks, a distributed
962 approach like the one we propose allows to reduce the difficulty of a
963 single global optimization problem by partitioning it in many smaller
964 problems, one per subregion, that can be solved more easily.
966 In future work, we plan to study and propose a coverage protocol, which
967 computes all active sensor schedules in one time, using
968 optimization methods such as swarms optimization or evolutionary
969 algorithms. The round will still consist of 4 phases, but the
970 decision phase will compute the schedules for several sensing phases,
971 which aggregated together, define a kind of meta-sensing phase.
972 The computation of all cover sets in one time is far more
973 difficult, but will reduce the communication overhead.
974 % use section* for acknowledgement
975 %\section*{Acknowledgment}
977 \bibliographystyle{IEEEtran}
978 \bibliography{bare_conf}