1 % This is IJUC.TEX the demonstration file of
\r
2 % the LaTeX macro package for International Journal of Unconventional Computation,
\r
3 % version 0.1 for LaTeX2e
\r
6 \usepackage[pdftex]{graphics}
\r
7 \usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
\r
11 \title{Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}
\r
13 \author{Ali Kadhum Idrees\inst{1}
\r
14 \and Karine Deschinkel\inst{1}
\r
15 \and Michel Salomon\inst{1}\email{michel.salomon@univ-fcomte.fr}
\r
16 \and Rapha\"el Couturier\inst{1}
\r
19 \institute{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comt\'e, France}
\r
21 \def\received{Received 23 October 2014}
\r
26 One of the main research challenges faced in wireless sensor networks is to
\r
27 preserve continuously and effectively the coverage of an area of interest to be
\r
28 monitored, while simultaneously preventing as much as possible a network failure
\r
29 due to battery-depleted nodes. In this paper we propose a protocol which
\r
30 maintains the coverage and improves the lifetime of a wireless sensor network.
\r
31 First, we partition the area of interest into subregions using a classical
\r
32 divide-and-conquer method. Our protocol is then distributed on the sensor nodes
\r
33 in each subregion in a second step. To fulfill our objective, the proposed
\r
34 protocol combines two techniques: a leader election in each subregion, followed
\r
35 by an optimization-based node activity scheduling performed by each elected
\r
36 leader. This two-step process takes place periodically. The simulations done
\r
37 using the discrete event simulator OMNeT++ show that our approach is able to
\r
38 increase the WSN lifetime and provides improved coverage performance.
\r
41 \keywords{Wireless Sensor Networks, Area Coverage, Network lifetime,
\r
42 Optimization, Scheduling.}
\r
44 \section{Introduction}
\r
45 \label{sec:introduction}
\r
47 Energy efficiency is a crucial issue in Wireless Sensor Networks (WSNs) since
\r
48 sensory consumption, in order to maximize the network lifetime, represents the
\r
49 major difficulty when designing WSNs. As a consequence, one of the scientific
\r
50 research challenges in WSNs, which has been addressed by a large amount of
\r
51 literature during the last few years, is the design of energy efficient
\r
52 approaches for coverage and connectivity~\cite{conti2014mobile}. Coverage
\r
53 reflects how well a sensor field is monitored. On the one hand we want to
\r
54 monitor the area of interest in the most efficient way~\cite{Nayak04}. On the
\r
55 other hand we want to use as little energy as possible. Sensor nodes are
\r
56 battery-powered with no means of recharging or replacing, usually due to
\r
57 environmental (hostile or unpractical environments) or cost reasons. Therefore,
\r
58 it is desired that the WSNs are deployed with high densities so as to exploit
\r
59 the overlapping sensing regions of some sensor nodes to save energy by turning
\r
60 off some of them during the sensing phase to prolong the network lifetime.
\r
62 In this paper we design a protocol that focuses on the area coverage problem
\r
63 with the objective of maximizing the network lifetime. Our proposition, the
\r
64 Distributed Lifetime Coverage Optimization (DILCO) protocol, maintains the
\r
65 coverage and improves the lifetime in WSNs. The area of interest is first
\r
66 divided into subregions using a divide-and-conquer algorithm and an activity
\r
67 scheduling for sensor nodes is then planned by the elected leader in each
\r
68 subregion. In fact, the nodes in a subregion can be seen as a cluster where each
\r
69 node sends sensing data to the cluster head or the sink node. Furthermore, the
\r
70 activities in a subregion/cluster can continue even if another cluster stops due
\r
71 to too many node failures. Our DiLCO protocol considers periods, where a period
\r
72 starts with a discovery phase to exchange information between sensors of the
\r
73 same subregion, in order to choose in a suitable manner a sensor node (the
\r
74 leader) to carry out the coverage strategy. In each subregion the activation of
\r
75 the sensors for the sensing phase of the current period is obtained by solving
\r
76 an integer program. The resulting activation vector is broadcast by a leader
\r
77 to every node of its subregion.
\r
79 The remainder of the paper continues with Section~\ref{sec:Literature Review}
\r
80 where a review of some related works is presented. The next section describes
\r
81 the DiLCO protocol, followed in Section~\ref{cp} by the coverage model
\r
82 formulation which is used to schedule the activation of
\r
83 sensors. Section~\ref{sec:Simulation Results and Analysis} shows the simulation
\r
84 results. The paper ends with a conclusion and some suggestions for further work.
\r
86 \section{Literature Review}
\r
87 \label{sec:Literature Review}
\r
89 In this section, we summarize some related works regarding the coverage problem
\r
90 and distinguish our DiLCO protocol from the works presented in the literature.
\r
92 The most discussed coverage problems in literature can be classified into three
\r
93 types \cite{li2013survey}: area coverage \cite{Misra} where every point inside
\r
94 an area is to be monitored, target coverage \cite{yang2014novel} where the main
\r
95 objective is to cover only a finite number of discrete points called targets,
\r
96 and barrier coverage \cite{Kumar:2005}\cite{kim2013maximum} to prevent intruders
\r
97 from entering into the region of interest. In \cite{Deng2012} authors transform
\r
98 the area coverage problem to the target coverage problem taking into account the
\r
99 intersection points among disks of sensors nodes or between disk of sensor nodes
\r
100 and boundaries. {\it In DiLCO protocol, the area coverage, i.e. the coverage of
\r
101 every point in the sensing region, is transformed to the coverage of a
\r
102 fraction of points called primary points. }
\r
104 The major approach to extend network lifetime while preserving coverage is to
\r
105 divide/organize the sensors into a suitable number of set covers (disjoint or
\r
106 non-disjoint), where each set completely covers a region of interest, and to
\r
107 activate these set covers successively. The network activity can be planned in
\r
108 advance and scheduled for the entire network lifetime or organized in periods,
\r
109 and the set of active sensor nodes is decided at the beginning of each period
\r
110 \cite{ling2009energy}. Active node selection is determined based on the problem
\r
111 requirements (e.g. area monitoring, connectivity, power efficiency). For
\r
112 instance, Jaggi et al. \cite{jaggi2006} address the problem of maximizing
\r
113 network lifetime by dividing sensors into the maximum number of disjoint subsets
\r
114 such that each subset can ensure both coverage and connectivity. A greedy
\r
115 algorithm is applied once to solve this problem and the computed sets are
\r
116 activated in succession to achieve the desired network lifetime. Vu
\r
117 \cite{chin2007}, Padmatvathy et al. \cite{pc10}, propose algorithms working in a
\r
118 periodic fashion where a cover set is computed at the beginning of each period.
\r
119 {\it Motivated by these works, DiLCO protocol works in periods, where each
\r
120 period contains a preliminary phase for information exchange and decisions,
\r
121 followed by a sensing phase where one cover set is in charge of the sensing
\r
124 Various approaches, including centralized, or distributed algorithms, have been
\r
125 proposed to extend the network lifetime. In distributed
\r
126 algorithms~\cite{yangnovel,ChinhVu,qu2013distributed}, information is
\r
127 disseminated throughout the network and sensors decide cooperatively by
\r
128 communicating with their neighbors which of them will remain in sleep mode for a
\r
129 certain period of time. The centralized
\r
130 algorithms~\cite{cardei2005improving,zorbas2010solving,pujari2011high} always
\r
131 provide nearly or close to optimal solution since the algorithm has global view
\r
132 of the whole network. But such a method has the disadvantage of requiring high
\r
133 communication costs, since the node (located at the base station) making the
\r
134 decision needs information from all the sensor nodes in the area and the amount
\r
135 of information can be huge. {\it In order to be suitable for large-scale
\r
136 network, in the DiLCO protocol, the area coverage is divided into several
\r
137 smaller subregions, and in each one, a node called the leader is in charge for
\r
138 selecting the active sensors for the current period.}
\r
140 A large variety of coverage scheduling algorithms has been developed. Many of
\r
141 the existing algorithms, dealing with the maximization of the number of cover
\r
142 sets, are heuristics. These heuristics involve the construction of a cover set
\r
143 by including in priority the sensor nodes which cover critical targets, that is
\r
144 to say targets that are covered by the smallest number of sensors
\r
145 \cite{berman04,zorbas2010solving}. Other approaches are based on mathematical
\r
146 programming formulations~\cite{cardei2005energy,5714480,pujari2011high,Yang2014}
\r
147 and dedicated techniques (solving with a branch-and-bound algorithms available
\r
148 in optimization solver). The problem is formulated as an optimization problem
\r
149 (maximization of the lifetime or number of cover sets) under target coverage and
\r
150 energy constraints. Column generation techniques, well-known and widely
\r
151 practiced techniques for solving linear programs with too many variables, have
\r
153 used~\cite{castano2013column,rossi2012exact,deschinkel2012column}. {\it In DiLCO
\r
154 protocol, each leader, in each subregion, solves an integer program with a
\r
155 double objective consisting in minimizing the overcoverage and limiting the
\r
156 undercoverage. This program is inspired from the work of \cite{pedraza2006}
\r
157 where the objective is to maximize the number of cover sets.}
\r
159 \section{Description of the DiLCO protocol}
\r
160 \label{sec:The DiLCO Protocol Description}
\r
162 In this section, we introduce the DiLCO protocol which is distributed on each
\r
163 subregion in the area of interest. It is based on two efficient techniques:
\r
164 network leader election and sensor activity scheduling for coverage preservation
\r
165 and energy conservation, applied periodically to efficiently maximize the
\r
166 lifetime in the network.
\r
168 \subsection{Assumptions and models}
\r
170 We consider a sensor network composed of static nodes distributed independently
\r
171 and uniformly at random. A high density deployment ensures a high coverage
\r
172 ratio of the interested area at the start. The nodes are supposed to have
\r
173 homogeneous characteristics from a communication and a processing point of view,
\r
174 whereas they have heterogeneous energy provisions. Each node has access to its
\r
175 location thanks, either to a hardware component (like a GPS unit), or a location
\r
176 discovery algorithm.
\r
178 We consider a boolean disk coverage model which is the most widely used sensor
\r
179 coverage model in the literature. Thus, since a sensor has a constant sensing
\r
180 range $R_s$, every space points within a disk centered at a sensor with the
\r
181 radius of the sensing range is said to be covered by this sensor. We also assume
\r
182 that the communication range $R_c \geq 2R_s$. In fact, Zhang and
\r
183 Hou~\cite{Zhang05} proved that if the transmission range fulfills the previous
\r
184 hypothesis, a complete coverage of a convex area implies connectivity among the
\r
185 working nodes in the active mode.
\r
187 For each sensor we also define a set of points called primary
\r
188 points~\cite{idrees2014coverage} to approximate the area coverage it provides,
\r
189 rather than working with a continuous coverage. Thus, a sensing disk
\r
190 corresponding to a sensor node is covered by its neighboring nodes if all its
\r
191 primary points are covered. Obviously, the approximation of coverage is more or
\r
192 less accurate according to the number of primary points.
\r
194 \subsection{Main idea}
\r
197 We start by applying a divide-and-conquer algorithm to partition the area of
\r
198 interest into smaller areas called subregions and then our protocol is executed
\r
199 simultaneously in each subregion.
\r
201 \begin{figure}[ht!]
\r
203 \scalebox{0.5}{\includegraphics{FirstModel.pdf}}
\r
205 \caption{DiLCO protocol.}
\r
209 As shown in Figure~\ref{fig2}, the proposed DiLCO protocol is a periodic
\r
210 protocol where each period is decomposed into 4~phases: Information Exchange,
\r
211 Leader Election, Decision, and Sensing. For each period there will be exactly
\r
212 one cover set in charge of the sensing task. A periodic scheduling is
\r
213 interesting because it enhances the robustness of the network against node
\r
214 failures. First, a node that has not enough energy to complete a period, or
\r
215 which fails before the decision is taken, will be excluded from the scheduling
\r
216 process. Second, if a node fails later, whereas it was supposed to sense the
\r
217 region of interest, it will only affect the quality of the coverage until the
\r
218 definition of a new cover set in the next period. Constraints, like energy
\r
219 consumption, can be easily taken into consideration since the sensors can update
\r
220 and exchange their information during the first phase. Let us notice that the
\r
221 phases before the sensing one (Information Exchange, Leader Election, and
\r
222 Decision) are energy consuming for all the nodes, even nodes that will not be
\r
223 retained by the leader to keep watch over the corresponding area.
\r
225 During the execution of the DiLCO protocol, two kinds of packet will be used:
\r
226 %\begin{enumerate}[(a)]
\r
228 \item INFO packet: sent by each sensor node to all the nodes inside a same
\r
229 subregion for information exchange.
\r
230 \item ActiveSleep packet: sent by the leader to all the nodes in its subregion
\r
231 to inform them to stay Active or to go Sleep during the sensing phase.
\r
234 and each sensor node will have five possible status in the network:
\r
235 %\begin{enumerate}[(a)]
\r
237 \item LISTENING: sensor is waiting for a decision (to be active or not);
\r
238 \item COMPUTATION: sensor applies the optimization process as leader;
\r
239 \item ACTIVE: sensor is active;
\r
240 \item SLEEP: sensor is turned off;
\r
241 \item COMMUNICATION: sensor is transmitting or receiving packet.
\r
245 An outline of the protocol implementation is given by Algorithm~\ref{alg:DiLCO}
\r
246 which describes the execution of a period by a node (denoted by $s_j$ for a
\r
247 sensor node indexed by $j$). At the beginning a node checks whether it has
\r
248 enough energy to stay active during the next sensing phase. If yes, it exchanges
\r
249 information with all the other nodes belonging to the same subregion: it
\r
250 collects from each node its position coordinates, remaining energy ($RE_j$), ID,
\r
251 and the number of one-hop neighbors still alive. Once the first phase is
\r
252 completed, the nodes of a subregion choose a leader to take the decision based
\r
253 on the following criteria with decreasing importance: larger number of
\r
254 neighbors, larger remaining energy, and then in case of equality, larger index.
\r
255 After that, if the sensor node is leader, it will execute the integer program
\r
256 algorithm (see Section~\ref{cp}) which provides a set of sensors planned to be
\r
257 active in the next sensing phase. As leader, it will send an Active-Sleep packet
\r
258 to each sensor in the same subregion to indicate it if it has to be active or
\r
259 not. Alternately, if the sensor is not the leader, it will wait for the
\r
260 Active-Sleep packet to know its state for the coming sensing phase.
\r
266 %\emph{Initialize the sensor node and determine it's position and subregion} \;
\r
268 \If{ $RE_j \geq E_{th}$ }{
\r
269 \emph{$s_j.status$ = COMMUNICATION}\;
\r
270 \emph{Send $INFO()$ packet to other nodes in the subregion}\;
\r
271 \emph{Wait $INFO()$ packet from other nodes in the subregion}\;
\r
272 %\emph{UPDATE $RE_j$ for every sent or received INFO Packet}\;
\r
273 %\emph{ Collect information and construct the list L for all nodes in the subregion}\;
\r
275 %\If{ the received INFO Packet = No. of nodes in it's subregion -1 }{
\r
276 \emph{LeaderID = Leader election}\;
\r
277 \If{$ s_j.ID = LeaderID $}{
\r
278 \emph{$s_j.status$ = COMPUTATION}\;
\r
279 \emph{$\left\{\left(X_{1},\dots,X_{k},\dots,X_{J}\right)\right\}$ =
\r
280 Execute Integer Program Algorithm($J$)}\;
\r
281 \emph{$s_j.status$ = COMMUNICATION}\;
\r
282 \emph{Send $ActiveSleep()$ to each node $k$ in subregion} \;
\r
283 \emph{Update $RE_j $}\;
\r
286 \emph{$s_j.status$ = LISTENING}\;
\r
287 \emph{Wait $ActiveSleep()$ packet from the Leader}\;
\r
289 \emph{Update $RE_j $}\;
\r
293 \Else { Exclude $s_j$ from entering in the current sensing phase}
\r
294 % \emph{return X} \;
\r
295 \caption{DiLCO($s_j$)}
\r
299 \section{Coverage problem formulation}
\r
302 Our model is based on the model proposed by \cite{pedraza2006} where the
\r
303 objective is to find a maximum number of disjoint cover sets. To accomplish
\r
304 this goal, the authors proposed an integer program which forces undercoverage
\r
305 and overcoverage of targets to become minimal at the same time. They use binary
\r
306 variables $x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our
\r
307 model, we consider that the binary variable $X_{j}$ determines the activation of
\r
308 sensor $j$ in the sensing phase. We also consider primary points as targets.
\r
309 The set of primary points is denoted by $P$ and the set of sensors by $J$.
\r
311 Let $\alpha_{jp}$ denote the indicator function of whether the primary point $p$
\r
312 is covered, that is:
\r
314 \alpha_{jp} = \left \{
\r
316 1 & \mbox{if the primary point $p$ is covered} \\
\r
317 & \mbox{by sensor node $j$}, \\
\r
318 0 & \mbox{otherwise.}\\
\r
319 \end{array} \right.
\r
322 The number of active sensors that cover the primary point $p$ can then be
\r
323 computed by $\sum_{j \in J} \alpha_{jp} * X_{j}$ where:
\r
327 1& \mbox{if sensor $j$ is active,} \\
\r
328 0 & \mbox{otherwise.}\\
\r
329 \end{array} \right.
\r
332 We define the Overcoverage variable $\Theta_{p}$ as:
\r
334 \Theta_{p} = \left \{
\r
336 0 & \mbox{if the primary point}\\
\r
337 & \mbox{$p$ is not covered,}\\
\r
338 \left( \sum_{j \in J} \alpha_{jp} * X_{j} \right)- 1 & \mbox{otherwise.}\\
\r
339 \end{array} \right.
\r
342 \noindent More precisely, $\Theta_{p}$ represents the number of active sensor
\r
343 nodes minus one that cover the primary point~$p$. The Undercoverage variable
\r
344 $U_{p}$ of the primary point $p$ is defined by:
\r
348 1 &\mbox{if the primary point $p$ is not covered,} \\
\r
349 0 & \mbox{otherwise.}\\
\r
350 \end{array} \right.
\r
354 \noindent Our coverage optimization problem can then be formulated as follows:
\r
355 \begin{equation} \label{eq:ip2r}
\r
358 \min \sum_{p \in P} (w_{\theta} \Theta_{p} + w_{U} U_{p})&\\
\r
359 \textrm{subject to :}&\\
\r
360 \sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, &\forall p \in P\\
\r
362 %\sum_{t \in T} X_{j,t} \leq \frac{RE_j}{e_t} &\forall j \in J \\
\r
364 \Theta_{p}\in N, &\forall p \in P\\
\r
365 U_{p} \in \{0,1\}, &\forall p \in P\\
\r
366 X_{j} \in \{0,1\}, &\forall j \in J
\r
372 \item $X_{j}$ : indicates whether or not the sensor $j$ is actively sensing (1
\r
373 if yes and 0 if not);
\r
374 \item $\Theta_{p}$ : {\it overcoverage}, the number of sensors minus one that
\r
375 are covering the primary point $p$;
\r
376 \item $U_{p}$ : {\it undercoverage}, indicates whether or not the primary point
\r
377 $p$ is being covered (1 if not covered and 0 if covered).
\r
380 The first group of constraints indicates that some primary point $p$ should be
\r
381 covered by at least one sensor and, if it is not always the case, overcoverage
\r
382 and undercoverage variables help balancing the restriction equations by taking
\r
383 positive values. Two objectives can be noticed in our model. First, we limit the
\r
384 overcoverage of primary points to activate as few sensors as possible. Second,
\r
385 to avoid a lack of area monitoring in a subregion we minimize the
\r
386 undercoverage. Both weights $w_\theta$ and $w_U$ must be carefully chosen to
\r
387 guarantee that the maximum number of points are covered during each period.
\r
389 \section{Protocol evaluation}
\r
390 \label{sec:Simulation Results and Analysis}
\r
392 \subsection{Simulation framework}
\r
394 To assess the performance of our DiLCO protocol, we have used the discrete event
\r
395 simulator OMNeT++ \cite{varga} to run different series of simulations.
\r
396 Table~\ref{table3} gives the chosen parameters setting.
\r
399 \caption{Relevant parameters for network initializing.}
\r
402 % used for centering table
\r
403 \begin{tabular}{c|c}
\r
404 % centered columns (4 columns)
\r
406 %inserts double horizontal lines
\r
407 Parameter & Value \\ [0.5ex]
\r
408 %Case & Strategy (with Two Leaders) & Strategy (with One Leader) & Simple Heuristic \\ [0.5ex]
\r
412 % inserts single horizontal line
\r
413 Sensing Field & $(50 \times 25)~m^2 $ \\
\r
414 % inserting body of the table
\r
416 Nodes Number & 50, 100, 150, 200 and 250~nodes \\
\r
418 Initial Energy & 500-700~joules \\
\r
420 Sensing Period & 60 Minutes \\
\r
421 $E_{th}$ & 36 Joules\\
\r
424 $w_{\Theta}$ & 1 \\
\r
425 % [1ex] adds vertical space
\r
428 %inserts single line
\r
431 % is used to refer this table in the text
\r
434 Simulations with five different node densities going from 50 to 250~nodes were
\r
435 performed considering each time 25~randomly generated networks, to obtain
\r
436 experimental results which are relevant. The nodes are deployed on a field of
\r
437 interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a
\r
438 high coverage ratio.
\r
440 We chose as energy consumption model the one proposed
\r
441 by~\cite{ChinhVu} and based on ~\cite{raghunathan2002energy} with
\r
442 slight modifications. The energy consumed by the communications is
\r
443 added and the part relative to a variable sensing range is removed. We
\r
444 also assume that the nodes have the characteristics of the Medusa II
\r
445 sensor node platform \cite{raghunathan2002energy}. A sensor node
\r
446 typically consists of four units: a MicroController Unit, an Atmels
\r
447 AVR ATmega103L in case of Medusa II, to perform the computations; a
\r
448 communication (radio) unit able to send and receive messages; a
\r
449 sensing unit to collect data; a power supply which provides the energy
\r
450 consumed by node. Except the battery, all the other unit can be
\r
451 switched off to save energy according to the node status.
\r
452 Table~\ref{table4} summarizes the energy consumed (in milliWatt per
\r
453 second) by a node for each of its possible status.
\r
456 \caption{Energy consumption model.}
\r
459 % used for centering table
\r
461 \begin{tabular}{|c|c|c|c|c|}
\r
462 % centered columns (4 columns)
\r
464 %inserts double horizontal lines
\r
465 Sensor status & MCU & Radio & Sensing & Power (mW) \\ [0.5ex]
\r
467 % inserts single horizontal line
\r
468 Listening & ON & ON & ON & 20.05 \\
\r
469 % inserting body of the table
\r
471 Active & ON & OFF & ON & 9.72 \\
\r
473 Sleep & OFF & OFF & OFF & 0.02 \\
\r
475 Computation & ON & ON & ON & 26.83 \\
\r
477 %\multicolumn{4}{|c|}{Energy needed to send/receive a 1-bit} & 0.2575\\
\r
484 Less influent energy consumption sources like when turning on the radio,
\r
485 starting the sensor node, changing the status of a node, etc., will be neglected
\r
486 for the sake of simplicity. Each node saves energy by switching off its radio
\r
487 once it has received its decision status from the corresponding leader (it can
\r
488 be itself). As explained previously in subsection~\ref{main_idea}, two kinds of
\r
489 packets for communication are considered in our protocol: INFO packet and
\r
490 ActiveSleep packet. To compute the energy needed by a node to transmit or
\r
491 receive such packets, we use the equation giving the energy spent to send a
\r
492 1-bit-content message defined in~\cite{raghunathan2002energy} (we assume
\r
493 symmetric communication costs), and we set their respective size to 112 and
\r
494 24~bits. The energy required to send or receive a 1-bit-content message is thus
\r
495 equal to 0.2575~mW.
\r
497 Each node has an initial energy level, in Joules, which is randomly drawn in
\r
498 $[500-700]$. If its energy provision reaches a value below the threshold
\r
499 $E_{th}=36$~Joules, the minimum energy needed for a node to stay active during
\r
500 one period, it will no longer take part in the coverage task. This value
\r
501 corresponds to the energy needed by the sensing phase, obtained by multiplying
\r
502 the energy consumed in active state (9.72 mW) by the time in seconds for one
\r
503 period (3,600 seconds), and adding the energy for the pre-sensing phases.
\r
504 According to the interval of initial energy, a sensor may be active during at
\r
507 In the simulations, we introduce the following performance metrics to evaluate
\r
508 the efficiency of our approach:
\r
511 \item {{\bf Network Lifetime}:} we define the network lifetime as the time until
\r
512 the coverage ratio drops below a predefined threshold. We denote by
\r
513 $Lifetime_{95}$ (respectively $Lifetime_{50}$) the amount of time during which
\r
514 the network can satisfy an area coverage greater than $95\%$ (respectively
\r
515 $50\%$). We assume that the sensor network can fulfill its task until all its
\r
516 nodes have been drained of their energy or it becomes disconnected. Network
\r
517 connectivity is crucial because an active sensor node without connectivity
\r
518 towards a base station cannot transmit any information regarding an observed
\r
519 event in the area that it monitors.
\r
521 \item {{\bf Coverage Ratio (CR)}:} it measures how well the WSN is able to
\r
522 observe the area of interest. In our case, we discretized the sensor field
\r
523 as a regular grid, which yields the following equation to compute the
\r
526 \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100,
\r
528 where $n$ is the number of covered grid points by active sensors of every
\r
529 subregions during the current sensing phase and $N$ is the total number of grid
\r
530 points in the sensing field. In our simulations, we have a layout of $N = 51
\r
531 \times 26 = 1,326$ grid points.
\r
533 \item {{\bf Energy Consumption}:} energy consumption (EC) can be seen as the
\r
534 total amount of energy consumed by the sensors during $Lifetime_{95}$
\r
535 or $Lifetime_{50}$, divided by the number of periods. Formally, the computation
\r
536 of EC can be expressed as follows:
\r
538 \mbox{EC} = \frac{\sum\limits_{m=1}^{M} \left( E^{com}_m+E^{list}_m+E^{comp}_m
\r
539 + E^{a}_m+E^{s}_m \right)}{M},
\r
541 where $M$ corresponds to the number of periods. The total amount of energy
\r
542 consumed by the sensors (EC) comes through taking into consideration four main
\r
543 energy factors. The first one, denoted $E^{com}_m$, represents the energy
\r
544 consumption spent by all the nodes for wireless communications during period
\r
545 $m$. $E^{list}_m$, the next factor, corresponds to the energy consumed by the
\r
546 sensors in LISTENING status before receiving the decision to go active or sleep
\r
547 in period $m$. $E^{comp}_m$ refers to the energy needed by all the leader nodes
\r
548 to solve the integer program during a period. Finally, $E^a_{m}$ and $E^s_{m}$
\r
549 indicate the energy consumed by the whole network in the sensing phase (active
\r
550 and sleeping nodes).
\r
553 \subsection{Performance analysis}
\r
556 In this subsection, we first focus on the performance of our DiLCO protocol for
\r
557 different numbers of subregions. We consider partitions of the WSN area into
\r
558 $2$, $4$, $8$, $16$, and $32$ subregions. Thus the DiLCO protocol is declined in
\r
559 five versions: DiLCO-2, DiLCO-4, DiLCO-8, DiLCO-16, and DiLCO-32. Simulations
\r
560 without partitioning the area of interest, cases which correspond to a
\r
561 centralized approach, are not presented because they require high execution
\r
562 times to solve the integer program and thus consume too much energy.
\r
564 We compare our protocol to two other approaches. The first one, called DESK and
\r
565 proposed by~\cite{ChinhVu}, is a fully distributed coverage algorithm. The
\r
566 second one, called GAF~\cite{xu2001geography}, consists in dividing the region
\r
567 into fixed squares. During the decision phase, in each square, one sensor is
\r
568 chosen to remain active during the sensing phase.
\r
570 \subsubsection{Coverage ratio}
\r
572 Figure~\ref{fig3} shows the average coverage ratio for 150 deployed nodes. It
\r
573 can be seen that both DESK and GAF provide a coverage ratio which is slightly
\r
574 better compared to DiLCO in the first thirty periods. This can be easily
\r
575 explained by the number of active nodes: the optimization process of our
\r
576 protocol activates less nodes than DESK or GAF, resulting in a slight decrease
\r
577 of the coverage ratio. In case of DiLCO-2 (respectively DiLCO-4), the coverage
\r
578 ratio exhibits a fast decrease with the number of periods and reaches zero value
\r
579 in period~18 (respectively 46), whereas the other versions of DiLCO, DESK, and
\r
580 GAF ensure a coverage ratio above 50\% for subsequent periods. We believe that
\r
581 the results obtained with these two methods can be explained by a high
\r
582 consumption of energy and we will check this assumption in the next subsection.
\r
584 Concerning DiLCO-8, DiLCO-16, and DiLCO-32, these methods seem to be more
\r
585 efficient than DESK and GAF, since they can provide the same level of coverage
\r
586 (except in the first periods where DESK and GAF slightly outperform them) for a
\r
587 greater number of periods. In fact, when our protocol is applied with a large
\r
588 number of subregions (from 8 to 32~regions), it activates a restricted number of
\r
589 nodes, and thus enables the extension of the lifetime.
\r
593 \scalebox{0.5}{\includegraphics{R/CR.pdf}}
\r
595 \caption{Coverage ratio.}
\r
599 \subsubsection{Energy consumption}
\r
601 Based on the results shown in Figure~\ref{fig3}, we focus on the DiLCO-16 and
\r
602 DiLCO-32 versions of our protocol, and we compare their energy consumption with
\r
603 the DESK and GAF approaches. For each sensor node we measure the energy consumed
\r
604 according to its successive status, for different network densities. We denote
\r
605 by $\mbox{\it Protocol}/50$ (respectively $\mbox{\it Protocol}/95$) the amount
\r
606 of energy consumed while the area coverage is greater than $50\%$ (repectively
\r
607 $95\%$), where {\it Protocol} is one of the four protocols we compare.
\r
608 Figure~\ref{fig95} presents the energy consumptions per period observed for
\r
609 network sizes going from 50 to 250~nodes. Let us notice that the same network
\r
610 sizes will be used for the different performance metrics.
\r
614 \scalebox{0.5}{\includegraphics{R/EC.pdf}}
\r
616 \caption{Energy consumption per period.}
\r
620 The results depict the good performance of the different versions of our
\r
621 protocol. Indeed, the protocols DiLCO-16/50, DiLCO-32/50, DiLCO-16/95, and
\r
622 DiLCO-32/95 consume less energy than their DESK and GAF counterparts for a
\r
623 similar level of area coverage. This observation reflects the larger number of
\r
624 nodes set active by DESK and GAF.
\r
626 % New paragraph - Michel
\r
627 Now, if we consider a same protocol, we can notice that the average consumption
\r
628 per period increases slightly for our protocol when increasing the level of
\r
629 coverage and the number of nodes, whereas it increases more largely for DESK and
\r
630 GAF. That means even if a larger network allows to improve the number of periods
\r
631 with a minimum coverage level value, this improvement has a higher energy cost
\r
632 per period due to communication overhead and a more difficult optimization
\r
633 problem. However, in comparison with DESK and GAF, our approach has a
\r
634 reasonable energy overcost.
\r
636 \subsubsection{Execution time}
\r
638 Another interesting point to investigate is the evolution of the execution time
\r
639 with the size of the WSN and the number of subregions. Therefore, we report for
\r
640 every version of our protocol the average execution times in seconds needed to
\r
641 solve the optimization problem for different WSN sizes. The execution times are
\r
642 obtained on a laptop DELL which has an Intel Core~i3~2370~M (2.4~GHz) dual core
\r
643 processor and a MIPS rating equal to 35330. The corresponding execution times on
\r
644 a MEDUSA II sensor node are then extrapolated according to the MIPS rate of the
\r
645 Atmels AVR ATmega103L microcontroller (6~MHz), which is equal to 6, by
\r
646 multiplying the laptop times by $\left(\frac{35330}{2} \times
\r
647 \frac{1}{6}\right)$.
\r
648 % The expected times on a sensor node are reported on Figure~\ref{fig8}.
\r
652 \scalebox{0.5}{\includegraphics{R/T.pdf}}
\r
654 \caption{Execution time in seconds.}
\r
658 Figure~\ref{fig8} shows that DiLCO-32 has very low execution times in comparison
\r
659 with other DiLCO versions, because the activity scheduling is tackled by a
\r
660 larger number of leaders and each leader solves an integer problem with a
\r
661 limited number of variables and constraints. Conversely, DiLCO-2 requires to
\r
662 solve an optimization problem with half of the network nodes and thus presents a
\r
663 high execution time. Nevertheless if we refer to Figure~\ref{fig3}, we observe
\r
664 that DiLCO-32 is slightly less efficient than DilCO-16 to maintain as long as
\r
665 possible high coverage. In fact an excessive subdivision of the area of interest
\r
666 prevents it to ensure a good coverage especially on the borders of the
\r
667 subregions. Thus, the optimal number of subregions can be seen as a trade-off
\r
668 between execution time and coverage performance.
\r
670 \subsubsection{Network lifetime}
\r
672 In the next figure, the network lifetime is illustrated. Obviously, the lifetime
\r
673 increases with the network size, whatever the considered protocol, since the
\r
674 correlated node density also increases. A high network density means a high
\r
675 node redundancy which allows to turn-off many nodes and thus to prolong the
\r
680 \scalebox{0.5}{\includegraphics{R/LT.pdf}}
\r
682 \caption{Network lifetime.}
\r
688 As highlighted by Figure~\ref{figLT95}, when the coverage level is relaxed
\r
689 ($50\%$) the network lifetime also improves. This observation reflects the fact
\r
690 that the higher the coverage performance, the more nodes must be active to
\r
691 ensure the wider monitoring. For a similar level of coverage, DiLCO outperforms
\r
692 DESK and GAF for the lifetime of the network. More specifically, if we focus on
\r
693 the larger level of coverage ($95\%$) in the case of our protocol, the
\r
694 subdivision in $16$~subregions seems to be the most appropriate.
\r
696 \section{Conclusion and future work}
\r
697 \label{sec:Conclusion and Future Works}
\r
699 A crucial problem in WSN is to schedule the sensing activities of the different
\r
700 nodes in order to ensure both coverage of the area of interest and longer
\r
701 network lifetime. The inherent limitations of sensor nodes, in energy provision,
\r
702 communication and computing capacities, require protocols that optimize the use
\r
703 of the available resources to fulfill the sensing task. To address this
\r
704 problem, this paper proposes a two-step approach. Firstly, the field of sensing
\r
705 is divided into smaller subregions using the concept of divide-and-conquer
\r
706 method. Secondly, a distributed protocol called Distributed Lifetime Coverage
\r
707 Optimization is applied in each subregion to optimize the coverage and lifetime
\r
708 performances. In a subregion, our protocol consists in electing a leader node
\r
709 which will then perform a sensor activity scheduling. The challenges include how
\r
710 to select the most efficient leader in each subregion and the best
\r
711 representative set of active nodes to ensure a high level of coverage. To assess
\r
712 the performance of our approach, we compared it with two other approaches using
\r
713 many performance metrics like coverage ratio or network lifetime. We have also
\r
714 studied the impact of the number of subregions chosen to subdivide the area of
\r
715 interest, considering different network sizes. The experiments show that
\r
716 increasing the number of subregions improves the lifetime. The more subregions
\r
717 there are, the more robust the network is against random disconnection resulting
\r
718 from dead nodes. However, for a given sensing field and network size there is
\r
719 an optimal number of subregions. Therefore, in case of our simulation context a
\r
720 subdivision in $16$~subregions seems to be the most relevant. The optimal number
\r
721 of subregions will be investigated in the future.
\r
723 \section{Acknowledgments}
\r
725 As a Ph.D. student, Ali Kadhum IDREES would like to gratefully acknowledge the
\r
726 University of Babylon - IRAQ for the financial support and Campus France for the
\r
727 received support. This paper is also partially funded by the Labex ACTION
\r
728 program (contract ANR-11-LABX-01-01).
\r
730 \bibliography{Example}
\r
