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 21 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 proposed \linebreak
\r
441 by~\cite{ChinhVu} and based on ~\cite{raghunathan2002energy} with slight
\r
442 modifications. The energy consumed by the communications is added and the part
\r
443 relative to a variable sensing range is removed. We also assume that the nodes
\r
444 have the characteristics of the Medusa II sensor node platform
\r
445 \cite{raghunathan2002energy}. A sensor node typically consists of four units: a
\r
446 MicroController Unit, an Atmels AVR ATmega103L in case of Medusa II, to perform
\r
447 the computations; a communication (radio) unit able to send and receive
\r
448 messages; a sensing unit to collect data; a power supply which provides the
\r
449 energy consumed by node. Except the battery, all the other unit can be switched
\r
450 off to save energy according to the node status. Table~\ref{table4} summarizes
\r
451 the energy consumed (in milliWatt per second) by a node for each of its possible
\r
455 \caption{Energy consumption model.}
\r
458 % used for centering table
\r
460 \begin{tabular}{|c|c|c|c|c|}
\r
461 % centered columns (4 columns)
\r
463 %inserts double horizontal lines
\r
464 Sensor status & MCU & Radio & Sensing & Power (mW) \\ [0.5ex]
\r
466 % inserts single horizontal line
\r
467 Listening & ON & ON & ON & 20.05 \\
\r
468 % inserting body of the table
\r
470 Active & ON & OFF & ON & 9.72 \\
\r
472 Sleep & OFF & OFF & OFF & 0.02 \\
\r
474 Computation & ON & ON & ON & 26.83 \\
\r
476 %\multicolumn{4}{|c|}{Energy needed to send/receive a 1-bit} & 0.2575\\
\r
483 Less influent energy consumption sources like when turning on the radio,
\r
484 starting the sensor node, changing the status of a node, etc., will be neglected
\r
485 for the sake of simplicity. Each node saves energy by switching off its radio
\r
486 once it has received its decision status from the corresponding leader (it can
\r
487 be itself). As explained previously in subsection~\ref{main_idea}, two kinds of
\r
488 packets for communication are considered in our protocol: INFO packet and
\r
489 ActiveSleep packet. To compute the energy needed by a node to transmit or
\r
490 receive such packets, we use the equation giving the energy spent to send a
\r
491 1-bit-content message defined in~\cite{raghunathan2002energy} (we assume
\r
492 symmetric communication costs), and we set their respective size to 112 and
\r
493 24~bits. The energy required to send or receive a 1-bit-content message is thus
\r
494 equal to 0.2575~mW.
\r
496 Each node has an initial energy level, in Joules, which is randomly drawn in
\r
497 $[500-700]$. If its energy provision reaches a value below the threshold
\r
498 $E_{th}=36$~Joules, the minimum energy needed for a node to stay active during
\r
499 one period, it will no longer take part in the coverage task. This value
\r
500 corresponds to the energy needed by the sensing phase, obtained by multiplying
\r
501 the energy consumed in active state (9.72 mW) by the time in seconds for one
\r
502 period (3,600 seconds), and adding the energy for the pre-sensing phases.
\r
503 According to the interval of initial energy, a sensor may be active during at
\r
506 In the simulations, we introduce the following performance metrics to evaluate
\r
507 the efficiency of our approach:
\r
510 \item {{\bf Network Lifetime}:} we define the network lifetime as the time until
\r
511 the coverage ratio drops below a predefined threshold. We denote by
\r
512 $Lifetime_{95}$ (respectively $Lifetime_{50}$) the amount of time during which
\r
513 the network can satisfy an area coverage greater than $95\%$ (respectively
\r
514 $50\%$). We assume that the sensor network can fulfill its task until all its
\r
515 nodes have been drained of their energy or it becomes disconnected. Network
\r
516 connectivity is crucial because an active sensor node without connectivity
\r
517 towards a base station cannot transmit any information regarding an observed
\r
518 event in the area that it monitors.
\r
520 \item {{\bf Coverage Ratio (CR)}:} it measures how well the WSN is able to
\r
521 observe the area of interest. In our case, we discretized the sensor field
\r
522 as a regular grid, which yields the following equation to compute the
\r
525 \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100,
\r
527 where $n$ is the number of covered grid points by active sensors of every
\r
528 subregions during the current sensing phase and $N$ is the total number of grid
\r
529 points in the sensing field. In our simulations, we have a layout of $N = 51
\r
530 \times 26 = 1326$ grid points.
\r
532 \item {{\bf Energy Consumption}:} energy consumption (EC) can be seen as the
\r
533 total amount of energy consumed by the sensors during $Lifetime_{95}$
\r
534 or $Lifetime_{50}$, divided by the number of periods. Formally, the computation
\r
535 of EC can be expressed as follows:
\r
537 \mbox{EC} = \frac{\sum\limits_{m=1}^{M} \left( E^{com}_m+E^{list}_m+E^{comp}_m
\r
538 + E^{a}_m+E^{s}_m \right)}{M},
\r
540 where $M$ corresponds to the number of periods. The total amount of energy
\r
541 consumed by the sensors (EC) comes through taking into consideration four main
\r
542 energy factors. The first one, denoted $E^{com}_m$, represents the energy
\r
543 consumption spent by all the nodes for wireless communications during period
\r
544 $m$. $E^{list}_m$, the next factor, corresponds to the energy consumed by the
\r
545 sensors in LISTENING status before receiving the decision to go active or sleep
\r
546 in period $m$. $E^{comp}_m$ refers to the energy needed by all the leader nodes
\r
547 to solve the integer program during a period. Finally, $E^a_{m}$ and $E^s_{m}$
\r
548 indicate the energy consumed by the whole network in the sensing phase (active
\r
549 and sleeping nodes).
\r
552 \subsection{Performance analysis}
\r
555 In this subsection, we first focus on the performance of our DiLCO protocol for
\r
556 different numbers of subregions. We consider partitions of the WSN area into
\r
557 $2$, $4$, $8$, $16$, and $32$ subregions. Thus the DiLCO protocol is declined in
\r
558 five versions: DiLCO-2, DiLCO-4, DiLCO-8, DiLCO-16, and DiLCO-32. Simulations
\r
559 without partitioning the area of interest, cases which correspond to a
\r
560 centralized approach, are not presented because they require high execution
\r
561 times to solve the integer program and thus consume too much energy.
\r
563 We compare our protocol to two other approaches. The first one, called DESK and
\r
564 proposed by~\cite{ChinhVu}, is a fully distributed coverage algorithm. The
\r
565 second one, called GAF~\cite{xu2001geography}, consists in dividing the region
\r
566 into fixed squares. During the decision phase, in each square, one sensor is
\r
567 chosen to remain active during the sensing phase.
\r
569 \subsubsection{Coverage ratio}
\r
571 Figure~\ref{fig3} shows the average coverage ratio for 150 deployed nodes. It
\r
572 can be seen that both DESK and GAF provide a coverage ratio which is slightly
\r
573 better compared to DiLCO in the first thirty periods. This can be easily
\r
574 explained by the number of active nodes: the optimization process of our
\r
575 protocol activates less nodes than DESK or GAF, resulting in a slight decrease
\r
576 of the coverage ratio. In case of DiLCO-2 (respectively DiLCO-4), the coverage
\r
577 ratio exhibits a fast decrease with the number of periods and reaches zero value
\r
578 in period~18 (respectively 46), whereas the other versions of DiLCO, DESK, and
\r
579 GAF ensure a coverage ratio above 50\% for subsequent periods. We believe that
\r
580 the results obtained with these two methods can be explained by a high
\r
581 consumption of energy and we will check this assumption in the next subsection.
\r
583 Concerning DiLCO-8, DiLCO-16, and DiLCO-32, these methods seem to be more
\r
584 efficient than DESK and GAF, since they can provide the same level of coverage
\r
585 (except in the first periods where DESK and GAF slightly outperform them) for a
\r
586 greater number of periods. In fact, when our protocol is applied with a large
\r
587 number of subregions (from 8 to 32~regions), it activates a restricted number of
\r
588 nodes, and thus enables the extension of the lifetime.
\r
592 \scalebox{0.5}{\includegraphics{R/CR.pdf}}
\r
594 \caption{Coverage ratio}
\r
598 \subsubsection{Energy consumption}
\r
600 Based on the results shown in Figure~\ref{fig3}, we focus on the DiLCO-16 and
\r
601 DiLCO-32 versions of our protocol, and we compare their energy consumption with
\r
602 the DESK and GAF approaches. For each sensor node we measure the energy consumed
\r
603 according to its successive status, for different network densities. We denote
\r
604 by $\mbox{\it Protocol}/50$ (respectively $\mbox{\it Protocol}/95$) the amount
\r
605 of energy consumed while the area coverage is greater than $50\%$ (repectively
\r
606 $95\%$), where {\it Protocol} is one of the four protocols we compare.
\r
607 Figure~\ref{fig95} presents the energy consumptions per period observed for
\r
608 network sizes going from 50 to 250~nodes. Let us notice that the same network
\r
609 sizes will be used for the different performance metrics.
\r
613 \scalebox{0.5}{\includegraphics{R/EC.pdf}}
\r
615 \caption{Energy consumption per period.}
\r
619 The results depict the good performance of the different versions of our
\r
620 protocol. Indeed, the protocols DiLCO-16/50, DiLCO-32/50, DiLCO-16/95, and
\r
621 DiLCO-32/95 consume less energy than their DESK and GAF counterparts for a
\r
622 similar level of area coverage. This observation reflects the larger number of
\r
623 nodes set active by DESK and GAF.
\r
625 % New paragraph - Michel
\r
626 Now, if we consider a same protocol, we can notice that the average consumption
\r
627 per period increases slightly for our protocol when increasing the level of
\r
628 coverage and the number of nodes, whereas it increases more largely for DESK and
\r
629 GAF. That means even if a larger network allows to improve the number of periods
\r
630 with a minimum coverage level value, this improvement has a higher energy cost
\r
631 per period due to communication overhead and a more difficult optimization
\r
632 problem. However, in comparison with DESK and GAF, our approach has a
\r
633 reasonable energy overcost.
\r
635 \subsubsection{Execution time}
\r
637 Another interesting point to investigate is the evolution of the execution time
\r
638 with the size of the WSN and the number of subregions. Therefore, we report for
\r
639 every version of our protocol the average execution times in seconds needed to
\r
640 solve the optimization problem for different WSN sizes. The execution times are
\r
641 obtained on a laptop DELL which has an Intel Core~i3~2370~M (2.4~GHz) dual core
\r
642 processor and a MIPS rating equal to 35330. The corresponding execution times on
\r
643 a MEDUSA II sensor node are then extrapolated according to the MIPS rate of the
\r
644 Atmels AVR ATmega103L microcontroller (6~MHz), which is equal to 6, by
\r
645 multiplying the laptop times by $\left(\frac{35330}{2} \times
\r
646 \frac{1}{6}\right)$.
\r
647 % The expected times on a sensor node are reported on Figure~\ref{fig8}.
\r
651 \scalebox{0.5}{\includegraphics{R/T.pdf}}
\r
653 \caption{Execution time in seconds.}
\r
657 Figure~\ref{fig8} shows that DiLCO-32 has very low execution times in comparison
\r
658 with other DiLCO versions, because the activity scheduling is tackled by a
\r
659 larger number of leaders and each leader solves an integer problem with a
\r
660 limited number of variables and constraints. Conversely, DiLCO-2 requires to
\r
661 solve an optimization problem with half of the network nodes and thus presents a
\r
662 high execution time. Nevertheless if we refer to Figure~\ref{fig3}, we observe
\r
663 that DiLCO-32 is slightly less efficient than DilCO-16 to maintain as long as
\r
664 possible high coverage. In fact an excessive subdivision of the area of interest
\r
665 prevents it to ensure a good coverage especially on the borders of the
\r
666 subregions. Thus, the optimal number of subregions can be seen as a trade-off
\r
667 between execution time and coverage performance.
\r
669 \subsubsection{Network lifetime}
\r
671 In the next figure, the network lifetime is illustrated. Obviously, the lifetime
\r
672 increases with the network size, whatever the considered protocol, since the
\r
673 correlated node density also increases. A high network density means a high
\r
674 node redundancy which allows to turn-off many nodes and thus to prolong the
\r
679 \scalebox{0.5}{\includegraphics{R/LT.pdf}}
\r
681 \caption{Network lifetime.}
\r
687 As highlighted by Figure~\ref{figLT95}, when the coverage level is relaxed
\r
688 ($50\%$) the network lifetime also improves. This observation reflects the fact
\r
689 that the higher the coverage performance, the more nodes must be active to
\r
690 ensure the wider monitoring. For a similar level of coverage, DiLCO outperforms
\r
691 DESK and GAF for the lifetime of the network. More specifically, if we focus on
\r
692 the larger level of coverage ($95\%$) in the case of our protocol, the
\r
693 subdivision in $16$~subregions seems to be the most appropriate.
\r
695 \section{Conclusion and future work}
\r
696 \label{sec:Conclusion and Future Works}
\r
698 A crucial problem in WSN is to schedule the sensing activities of the different
\r
699 nodes in order to ensure both coverage of the area of interest and longer
\r
700 network lifetime. The inherent limitations of sensor nodes, in energy provision,
\r
701 communication and computing capacities, require protocols that optimize the use
\r
702 of the available resources to fulfill the sensing task. To address this
\r
703 problem, this paper proposes a two-step approach. Firstly, the field of sensing
\r
704 is divided into smaller subregions using the concept of divide-and-conquer
\r
705 method. Secondly, a distributed protocol called Distributed Lifetime Coverage
\r
706 Optimization is applied in each subregion to optimize the coverage and lifetime
\r
707 performances. In a subregion, our protocol consists in electing a leader node
\r
708 which will then perform a sensor activity scheduling. The challenges include how
\r
709 to select the most efficient leader in each subregion and the best
\r
710 representative set of active nodes to ensure a high level of coverage. To assess
\r
711 the performance of our approach, we compared it with two other approaches using
\r
712 many performance metrics like coverage ratio or network lifetime. We have also
\r
713 studied the impact of the number of subregions chosen to subdivide the area of
\r
714 interest, considering different network sizes. The experiments show that
\r
715 increasing the number of subregions improves the lifetime. The more subregions
\r
716 there are, the more robust the network is against random disconnection resulting
\r
717 from dead nodes. However, for a given sensing field and network size there is
\r
718 an optimal number of subregions. Therefore, in case of our simulation context a
\r
719 subdivision in $16$~subregions seems to be the most relevant. The optimal number
\r
720 of subregions will be investigated in the future.
\r
722 \section{Acknowledgments}
\r
724 As a Ph.D. student, Ali Kadhum IDREES would like to gratefully acknowledge the
\r
725 University of Babylon - IRAQ for the financial support and Campus France for the
\r
726 received support. This paper is also partially funded by the Labex ACTION
\r
727 program (contract ANR-11-LABX-01-01).
\r
729 \bibliography{Example}
\r
