]> AND Private Git Repository - UIC2013.git/blob - bare_conf.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
80629a9ab5ce13add24e38a18896876a47bfef22
[UIC2013.git] / bare_conf.tex
1 \documentclass[conference]{IEEEtran}
2
3 \ifCLASSINFOpdf
4   
5 \else
6   
7 \fi
8
9 \hyphenation{op-tical net-works semi-conduc-tor}
10
11 \usepackage{float} 
12 \usepackage{epsfig}
13 \usepackage{calc}
14  \usepackage{times,amssymb,amsmath,latexsym}
15 \usepackage{graphics}
16 \usepackage{graphicx}
17 \usepackage{amsmath}
18 %\usepackage{txfonts}
19 \usepackage{algorithmic}
20 \usepackage[T1]{fontenc}
21 \usepackage{tikz}
22 %\usepackage{algorithm}
23 %\usepackage{algpseudocode}
24 %\usepackage{algorithmwh}
25 \usepackage{subfigure}
26 \usepackage{float}
27 \usepackage{xspace}
28 \usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
29 \usepackage{epsfig}
30 \usepackage{caption}
31 \usepackage{multicol}
32 \usepackage{times}
33 \usepackage{graphicx,epstopdf}
34 \epstopdfsetup{suffix=}
35 \DeclareGraphicsExtensions{.ps}
36 \DeclareGraphicsRule{.ps}{pdf}{.pdf}{`ps2pdf -dEPSCrop -dNOSAFER #1 \noexpand\OutputFile}
37
38 \begin{document}
39
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}
43
44 % author names and affiliations
45 % use a multiple column layout for up to three different
46 % affiliations
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 \\
50 Belfort, France \\
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}
53 %\and
54 %\IEEEauthorblockN{Homer Simpson}
55 %\IEEEauthorblockA{FEMTO-ST Institute, UMR CNRS, University of Franche-Comte, Belfort, France}
56 %\and
57 %\IEEEauthorblockN{James Kirk\\ and Montgomery Scott}
58 %\IEEEauthorblockA{FEMTO-ST Institute, UMR CNRS, University of Franche-Comte, Belfort, France}
59 }
60
61 \maketitle
62
63 \begin{abstract}
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.
79 \end{abstract}
80
81 \begin{IEEEkeywords}
82 Area Coverage, Network lifetime, Optimization, Scheduling, Distributed Protocol.
83 \end{IEEEkeywords}
84 %\keywords{Area Coverage, Network lifetime, Optimization, Distributed Protocol}
85  
86 \IEEEpeerreviewmaketitle
87
88 \section{Introduction}
89
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.
111
112 The remainder of the paper is organized as follows.  The next section
113 % Section~\ref{rw}
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}.
121
122 \section{Related works}
123 \label{rw}
124
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.
131
132 %\begin{itemize}
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}.
136
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}. 
138
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}.
140 %\end{itemize}
141 \subsection{Coverage} 
142 %{\bf Coverage}
143
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
161 simultaneously).
162
163 \subsection{Lifetime} 
164 %{\bf Lifetime}
165
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.
178
179 \subsection{Activity scheduling} 
180 %{\bf Activity scheduling}
181
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.
193
194 \subsection{Distributed approaches}
195 %{\bf Distributed approaches}
196
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}.
229
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
235
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
238 %period of time.
239
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. 
241
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. 
243
244 \subsection{Centralized approaches}
245 %{\bf Centralized approaches}
246
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.
255
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.
277
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.
279
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}
309
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.
328
329 \subsection{Our contribution}
330 %{\bf Our contribution}
331
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
335 sections.
336 \begin{itemize}
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.
341
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
347   objectives.
348
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.
364 \end{itemize}
365
366 \section{Activity scheduling}
367 \label{pd}
368
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
380 figure~\ref{fig1}.
381
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. \\ 
383
384 \begin{figure}[ht!]
385 \centering
386 \includegraphics[width=85mm]{FirstModel.eps} % 70mm
387 \caption{Multi-round coverage protocol}
388 \label{fig1}
389 \end{figure} 
390
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.
408
409 \subsection{Information exchange phase}
410
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
417 active mode.
418
419 %\subsection{\textbf Working Phase:}
420
421 %The working phase works in rounding fashion. Each round include 3 steps described as follow :
422
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.
433
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. 
441
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.
450
451 %\subsection{Sensing coverage model}
452 %\label{pd}
453
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}:
466
467 %\begin{figure}[h!]
468 %\centering
469 %\begin{tabular}{cc}
470 %%\includegraphics[scale=0.25]{fig1.pdf}\\ %& \includegraphics[scale=0.10]{1.pdf} \\
471 %%(A) Figure 1 & (B) Figure 2
472 %\end{tabular}
473 %\caption{Unit Circle in radians. }
474 %\label{fig:cluster1}
475 %\end{figure}
476
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.
480
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.
485 %\begin{figure}[h!]
486 %\centering
487 %\begin{tabular}{cc}
488 %%\includegraphics[scale=0.25]{fig2.pdf}\\ %& \includegraphics[scale=0.10]{1.pdf} \\
489 %%(A) Figure 1 & (B) Figure 2
490 %\end{tabular}
491 %\caption{Wireless Sensor Node Area Coverage Model.}
492 %\label{fig:cluster2}
493 %\end{figure}
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.
500
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\\  
505 $X_1=(p_x,p_y)$ \\ 
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})) $.
518
519  \begin{figure}[h!]
520 %\centering
521 % \begin{multicols}{6}
522 \centering
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)
529 %\end{multicols} 
530 \caption{Wireless sensor node represented by 13 primary points}
531 \label{fig2}
532 \end{figure}
533
534 \section{Coverage problem formulation}
535 \label{cp}
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}:\\
537
538
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}:\\
540
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$.
551
552 \noindent  For  a primary  point  $p$,  let  $\alpha_{jp}$ denote  the
553 indicator function of whether the point $p$ is covered, that is:
554 \begin{equation}
555 \alpha_{jp} = \left \{ 
556 \begin{array}{l l}
557   1 & \mbox{if the primary point $p$ is covered} \\
558  & \mbox{by sensor node $j$}, \\
559   0 & \mbox{otherwise.}\\
560 \end{array} \right.
561 %\label{eq12} 
562 \end{equation}
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:
565 \begin{equation}
566 X_{j} = \left \{ 
567 \begin{array}{l l}
568   1& \mbox{if sensor $j$  is active,} \\
569   0 &  \mbox{otherwise.}\\
570 \end{array} \right.
571 %\label{eq11} 
572 \end{equation}
573 We define the Overcoverage variable $\Theta_{p}$ as:
574 \begin{equation}
575  \Theta_{p} = \left \{ 
576 \begin{array}{l l}
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.}\\
580 \end{array} \right.
581 \label{eq13} 
582 \end{equation}
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
586 by:
587 \begin{equation}
588 U_{p} = \left \{ 
589 \begin{array}{l l}
590   1 &\mbox{if the primary point $p$ is not covered,} \\
591   0 & \mbox{otherwise.}\\
592 \end{array} \right.
593 \label{eq14} 
594 \end{equation}
595
596 \noindent Our coverage optimization problem can then be formulated as follows\\
597 \begin{equation} \label{eq:ip2r}
598 \left \{
599 \begin{array}{ll}
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\\
603 %\label{c1} 
604 %\sum_{t \in T} X_{j,t} \leq \frac{RE_j}{e_t} &\forall j \in J \\
605 %\label{c2}
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
609 \end{array}
610 \right.
611 \end{equation}
612 \begin{itemize}
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).
619 \end{itemize}
620
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
630 round.
631  
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}
635
636 %\begin{itemize}
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
654
655 %\end{itemize}
656
657 \section{Simulation results}
658 \label{exp}
659
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
674 event they sense).
675
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|$.
687
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
700 phase.
701
702 \subsection{The impact of the number of rounds on the coverage ratio} 
703
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
721 subregion.
722
723 \parskip 0pt 
724 \begin{figure}[h!]
725 \centering
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}
728 \label{fig3}
729 \end{figure} 
730
731 \subsection{The impact of the number of rounds on the active sensors ratio} 
732
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:
737 \begin{equation*}
738 \scriptsize
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.
742 \end{equation*}
743 Figure~\ref{fig4} shows  the average active nodes ratio versus rounds
744 for 150 deployed nodes.
745
746 \begin{figure}[h!]
747 \centering
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 }
750 \label{fig4}
751 \end{figure} 
752
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.
762
763 \subsection{The impact of the number of rounds on the energy saving ratio} 
764
765 In this experiment, we consider a performance metric linked to energy.
766 This metric, called Energy Saving Ratio (ESR), is defined by:
767 \begin{equation*}
768 \scriptsize
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.
771 \end{equation*}
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.
776
777 \begin{figure}[h!]
778 %\centering
779 % \begin{multicols}{6}
780 \centering
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}
783 \label{fig5}
784 \end{figure} 
785
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.
795
796 \subsection{The percentage of stopped simulation runs}
797
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.
809
810 \begin{figure}[h!]
811 \centering
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 }
814 \label{fig6}
815 \end{figure} 
816
817 \subsection{The energy consumption}
818
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.
828
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.
841
842 \begin{figure}[h!]
843 \centering
844 \includegraphics[scale=0.5]{TheEnergyConsumptiong.eps} 
845 \caption{The energy consumption}
846 \label{fig7}
847 \end{figure} 
848
849 \subsection{The impact of the number of sensors on execution time}
850
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.
868
869 \begin{table}[ht]
870 \caption{THE EXECUTION TIME(S) VS THE NUMBER OF SENSORS}
871 % title of Table
872 \centering
873
874 % used for centering table
875 \begin{tabular}{|c|c|c|c|}
876 % centered columns (4 columns)
877       \hline
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]
882 % inserts table
883 %heading
884 \hline
885 % inserts single horizontal line
886 50 & 0.097 & 0.189 & 0.001 \\
887 % inserting body of the table
888 \hline
889 100 & 0.419 & 1.972 & 0.0032 \\
890 \hline
891 150 & 1.295 & 13.098 & 0.0032 \\
892 \hline
893 200 & 4.54 & 169.469 & 0.0046 \\
894 \hline
895 250 & 12.252 & 1581.163 & 0.0056 \\
896 % [1ex] adds vertical space
897 \hline
898 %inserts single line
899 \end{tabular}
900 \label{table1}
901 % is used to refer this table in the text
902 \end{table}
903
904 \subsection{The network lifetime}
905
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.
914
915 \begin{figure}[h!]
916 %\centering
917 % \begin{multicols}{6}
918 \centering
919 \includegraphics[scale=0.5]{TheNetworkLifetimeg.eps} %\\~ ~ ~(a)
920 \caption{The network lifetime }
921 \label{fig8}
922 \end{figure} 
923
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.
937
938 \section{Conclusion and future works}
939 \label{sec:conclusion}
940
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.
965
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}
976
977 \bibliographystyle{IEEEtran}
978 \bibliography{bare_conf}
979
980 % that's all folks
981 \end{document}
982
983