3 \documentclass[conference]{IEEEtran}
12 \hyphenation{op-tical net-works semi-conduc-tor}
19 \usepackage{times,amssymb,amsmath,latexsym}
24 \usepackage{algorithmic}
25 \usepackage[T1]{fontenc}
27 %\usepackage{algorithm}
28 %\usepackage{algpseudocode}
29 %\usepackage{algorithmwh}
30 \usepackage{subfigure}
33 \usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
38 \usepackage{graphicx,epstopdf}
39 \epstopdfsetup{suffix=}
40 \DeclareGraphicsExtensions{.ps}
41 \DeclareGraphicsRule{.ps}{pdf}{.pdf}{`ps2pdf -dEPSCrop -dNOSAFER #1 \noexpand\OutputFile}
47 % can use linebreaks \\ within to get better formatting as desired
48 \title{Coverage and Lifetime Optimization in Heterogeneous Energy Wireless Sensor Networks}
50 \author{\IEEEauthorblockN{Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier}
51 \IEEEauthorblockA{FEMTO-ST Institute, UMR 6174 CNRS \\
52 University of Franche-Comt\'e \\
54 Email: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr}}
60 One of the fundamental challenges in Wireless Sensor Networks (WSNs)
61 is the coverage preservation and the extension of the network lifetime
62 continuously and effectively when monitoring a certain area (or
63 region) of interest. In this paper, a coverage optimization protocol to
64 improve the lifetime in heterogeneous energy wireless sensor networks
65 is proposed. The area of interest is first divided into subregions
66 using a divide-and-conquer method and then the scheduling of sensor node
67 activity is planned for each subregion. The proposed scheduling
68 considers rounds during which a small number of nodes, remaining
69 active for sensing, is selected to ensure coverage. Each round
70 consists of four phases: (i)~Information Exchange, (ii)~Leader
71 Election, (iii)~Decision, and (iv)~Sensing. The decision process is
72 carried out by a leader node, which solves an integer program.
73 Simulation results show that the proposed approach can prolong the
74 network lifetime and improve the coverage performance.
78 Wireless Sensor Networks, Area Coverage, Network lifetime, Optimization, Scheduling.
80 %\keywords{Area Coverage, Network lifetime, Optimization, Distributed Protocol}
82 \IEEEpeerreviewmaketitle
85 \section{Introduction}
87 \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
88 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
89 to a monitoring center
90 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}.
91 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
92 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}.
93 In this paper, we concentrate on the area
94 coverage problem, with the objective of maximizing the network
95 lifetime by using an adaptive scheduling. The area of interest is
96 divided into subregions and an activity scheduling for sensor nodes is
97 planned for each subregion.
98 In fact, the nodes in a subregion can be seen as a cluster where
99 each node sends sensing data to the cluster head or the sink node.
100 Furthermore, the activities in a subregion/cluster can continue even
101 if another cluster stops due to too many node failures.
102 Our scheduling scheme considers rounds, where a round starts with a
103 discovery phase to exchange information between sensors of the
104 subregion, in order to choose in a suitable manner a sensor node to
105 carry out a coverage strategy. This coverage strategy involves the
106 solving of an integer program, which provides the activation of the
107 sensors for the sensing phase of the current round.
109 The remainder of the paper is organized as follows. The next section
111 reviews the related work in the field. Section~\ref{pd} is devoted to
112 the scheduling strategy for energy-efficient coverage.
113 Section~\ref{cp} gives the coverage model formulation, which is used to
114 schedule the activation of sensors. Section~\ref{exp} shows the
115 simulation results obtained using the discrete event simulator OMNeT++ \cite{varga}. They fully demonstrate the usefulness of the
116 proposed approach. Finally, we give concluding remarks and some
117 suggestions for future works in Section~\ref{sec:conclusion}.
120 \section{Related works}
122 \indent In this section, we only review some recent work with the coverage lifetime maximization problem, where the objective is to optimally schedule sensors' activities in
123 order to extend network lifetime in WSNS. Authors in \cite{chin2007} propose a novel
124 distributed heuristic named Distributed Energy-efficient Scheduling
125 for k-coverage (DESK) so that the energy consumption among all the
126 sensors is balanced, and network lifetime is maximized while the
127 coverage requirement is being maintained. This algorithm works in
128 round, requires only 1-sensing-hop-neighbor information, and a sensor
129 decides its status (active/sleep) based on the perimeter coverage
130 model, which proposed in \cite{Huang:2003:CPW:941350.941367}.
131 Shibo et al.\cite{Shibo} studied the coverage problem, which is formulated as a minimum weight submodular set cover problem. To address this problem,
132 a distributed truncated greedy algorithm (DTGA) is proposed. They exploited from the
133 temporal and spatialcorrelations among the data sensed by different sensor nodes and leverage
134 prediction to extend the WSNs lifetime.
135 Bang et al. \cite{Bang} proposed a coverage-aware clustering protocol(CACP), which used computation method for the optimal cluster size to minimize the average energy consumption rate per unit area. They defied in this protocol a cost metric that prefer the redundant sensors
136 with higher power as best candidates for cluster heads and select the active sensors that cover the area of interest more efficiently.
137 Zhixin et al. \cite{Zhixin} propose a Distributed Energy-
138 Efficient Clustering with Improved Coverage(DEECIC) algorithm
139 which aims at clustering with the least number of cluster
140 heads to cover the whole network and assigning a unique ID
141 to each node based on local information. In addition, this
142 protocol periodically updates cluster heads according to the
143 joint information of nodes $’ $residual energy and distribution.
144 Although DEECIC does not require knowledge of a node's
145 geographic location, it guarantees full coverage of the
146 network. However, the protocol does not make any activity
147 scheduling to set redundant sensors in passive mode in order
148 to conserve energy. C. Liu and G. Cao \cite{Changlei} studied how to
149 schedule sensor active time to maximize their coverage during a specified network lifetime. Their objective is to maximize the spatial-temporal coverage by scheduling sensors activity after they have been deployed. They proposed both centralized and distributed algorithms. The distributed parallel optimization protocol can ensure each sensor to converge to local optimality without conflict with each other. S. Misra et al. \cite{Misra} proposed a localized algorithm for coverage in sensor
150 networks. The algorithm conserve the energy while ensuring the network coverage by activating the subset of sensors, with the minimum overlap area.The proposed method preserves
151 the network connectivity by formation of the network backbone. L. Zhang et al. \cite{Zhang} presented a novel distributed clustering algorithm
152 called Adaptive Energy Efficient Clustering (AEEC) to maximize network lifetime. In this study, they are introduced an optimization, which includes restricted global re-clustering,
153 intra-cluster node sleeping scheduling and adaptive
154 transmission range adjustment to conserve the energy, while connectivity and coverage is ensured. J. A. Torkestani \cite{Torkestani} proposed a learning automata-based energy-efficient coverage protocol
155 named as LAEEC to construct the degree-constrained connected dominating set (DCDS) in WSNs. He shows that the correct choice of the degree-constraint of DCDS balances the network load on the active nodes and leads to enhance the coverage and network lifetime.
157 The main contribution of our approach addresses three main questions to build a
158 scheduling strategy. We give a brief answer to these three questions
159 to describe our approach before going into details in the subsequent
163 {\bf How must the phases for information exchange, decision and
164 sensing be planned over time?} Our algorithm divides the time line
165 into a number of rounds. Each round contains 4 phases: Information
166 Exchange, Leader Election, Decision, and Sensing.
169 {\bf What are the rules to decide which node has to be turned on
170 or off?} Our algorithm tends to limit the overcoverage of points of
171 interest to avoid turning on too many sensors covering the same
172 areas at the same time, and tries to prevent undercoverage. The
173 decision is a good compromise between these two conflicting
177 {\bf Which node should make such a decision?} As mentioned in
178 \cite{pc10}, both centralized and distributed algorithms have their
179 own advantages and disadvantages. Centralized coverage algorithms
180 have the advantage of requiring very low processing power from the
181 sensor nodes, which have usually limited processing capabilities.
182 Distributed algorithms are very adaptable to the dynamic and
183 scalable nature of sensors network. Authors in \cite{pc10} conclude
184 that there is a threshold in terms of network size to switch from a
185 localized to a centralized algorithm. Indeed, the exchange of
186 messages in large networks may consume a considerable amount of
187 energy in a centralized approach compared to a distributed one. Our
188 work does not consider only one leader to compute and to broadcast
189 the scheduling decision to all the sensors. When the network size
190 increases, the network is divided into many subregions and the
191 decision is made by a leader in each subregion.
196 \section{Activity scheduling}
199 We consider a randomly and uniformly deployed network consisting of
200 static wireless sensors. The wireless sensors are deployed in high
201 density to ensure initially a full coverage of the interested area. We
202 assume that all nodes are homogeneous in terms of communication and
203 processing capabilities and heterogeneous in term of energy provision.
204 The location information is available to the sensor node either
205 through hardware such as embedded GPS or through location discovery
206 algorithms. The area of interest can be divided using the
207 divide-and-conquer strategy into smaller areas called subregions and
208 then our coverage protocol will be implemented in each subregion
209 simultaneously. Our protocol works in rounds fashion as shown in
212 %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. \\
216 \includegraphics[width=85mm]{FirstModel.eps} % 70mm
217 \caption{Multi-round coverage protocol}
221 Each round is divided into 4 phases : Information (INFO) Exchange,
222 Leader Election, Decision, and Sensing. For each round there is
223 exactly one set cover responsible for the sensing task. This protocol is
224 more reliable against an unexpected node failure because it works
225 in rounds. On the one hand, if a node failure is detected before
226 making the decision, the node will not participate to this phase, and,
227 on the other hand, if the node failure occurs after the decision, the
228 sensing task of the network will be temporarily affected: only during
229 the period of sensing until a new round starts, since a new set cover
230 will take charge of the sensing task in the next round. The energy
231 consumption and some other constraints can easily be taken into
232 account since the sensors can update and then exchange their
233 information (including their residual energy) at the beginning of each
234 round. However, the pre-sensing phases (INFO Exchange, Leader
235 Election, Decision) are energy consuming for some nodes, even when
236 they do not join the network to monitor the area. Below, we describe
237 each phase in more details.
239 \subsection{Information exchange phase}
241 Each sensor node $j$ sends its position, remaining energy $RE_j$, and
242 the number of local neighbours $NBR_j$ to all wireless sensor nodes in
243 its subregion by using an INFO packet and then listens to the packets
244 sent from other nodes. After that, each node will have information
245 about all the sensor nodes in the subregion. In our model, the
246 remaining energy corresponds to the time that a sensor can live in the
249 %\subsection{\textbf Working Phase:}
251 %The working phase works in rounding fashion. Each round include 3 steps described as follow :
253 \subsection{Leader election phase}
254 This step includes choosing the Wireless Sensor Node Leader (WSNL),
255 which will be responsible for executing the coverage algorithm. Each
256 subregion in the area of interest will select its own WSNL
257 independently for each round. All the sensor nodes cooperate to
258 select WSNL. The nodes in the same subregion will select the leader
259 based on the received information from all other nodes in the same
260 subregion. The selection criteria in order of priority are: larger
261 number of neighbours, larger remaining energy, and then in case of
262 equality, larger index.
264 \subsection{Decision phase}
265 The WSNL will solve an integer program (see section~\ref{cp}) to
266 select which sensors will be activated in the following sensing phase
267 to cover the subregion. WSNL will send Active-Sleep packet to each
268 sensor in the subregion based on the algorithm's results.
269 %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.
270 %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.
272 \subsection{Sensing phase}
273 Active sensors in the round will execute their sensing task to
274 preserve maximal coverage in the region of interest. We will assume
275 that the cost of keeping a node awake (or asleep) for sensing task is
276 the same for all wireless sensor nodes in the network. Each sensor
277 will receive an Active-Sleep packet from WSNL informing it to stay
278 awake or to go to sleep for a time equal to the period of sensing until
279 starting a new round.
281 %\subsection{Sensing coverage model}
284 %\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.
285 %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$.
286 \indent We consider a boolean disk coverage model which is the most
287 widely used sensor coverage model in the literature. Each sensor has a
288 constant sensing range $R_s$. All space points within a disk centered
289 at the sensor with the radius of the sensing range is said to be
290 covered by this sensor. We also assume that the communication range is
291 at least twice the size of the sensing range. In fact, Zhang and
292 Zhou~\cite{Zhang05} proved that if the transmission range fulfills the
293 previous hypothesis, a complete coverage of a convex area implies
294 connectivity among the working nodes in the active mode.
295 %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}:
300 %%\includegraphics[scale=0.25]{fig1.pdf}\\ %& \includegraphics[scale=0.10]{1.pdf} \\
301 %%(A) Figure 1 & (B) Figure 2
303 %\caption{Unit Circle in radians. }
304 %\label{fig:cluster1}
307 %By using the Unit Circle in figure~\ref{fig:cluster1},
308 %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.
309 % 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.
311 \indent Instead of working with the coverage area, we consider for each
312 sensor a set of points called primary points. We also assume that the
313 sensing disk defined by a sensor is covered if all the primary points of
314 this sensor are covered.
318 %%\includegraphics[scale=0.25]{fig2.pdf}\\ %& \includegraphics[scale=0.10]{1.pdf} \\
319 %%(A) Figure 1 & (B) Figure 2
321 %\caption{Wireless Sensor Node Area Coverage Model.}
322 %\label{fig:cluster2}
324 By knowing the position (point center: ($p_x,p_y$)) of a wireless
325 sensor node and its $R_s$, we calculate the primary points directly
326 based on the proposed model. We use these primary points (that can be
327 increased or decreased if necessary) as references to ensure that the
328 monitored region of interest is covered by the selected set of
329 sensors, instead of using all the points in the area.
331 \indent We can calculate the positions of the selected primary
332 points in the circle disk of the sensing range of a wireless sensor
333 node (see figure~\ref{fig2}) as follows:\\
334 $(p_x,p_y)$ = point center of wireless sensor node\\
336 $X_2=( p_x + R_s * (1), p_y + R_s * (0) )$\\
337 $X_3=( p_x + R_s * (-1), p_y + R_s * (0)) $\\
338 $X_4=( p_x + R_s * (0), p_y + R_s * (1) )$\\
339 $X_5=( p_x + R_s * (0), p_y + R_s * (-1 )) $\\
340 $X_6= ( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (0)) $\\
341 $X_7=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (0))$\\
342 $X_8=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
343 $X_9=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
344 $X_{10}=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
345 $X_{11}=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
346 $X_{12}=( p_x + R_s * (0), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
347 $X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $.
351 % \begin{multicols}{6}
353 %\includegraphics[scale=0.10]{fig21.pdf}\\~ ~ ~(a)
354 %\includegraphics[scale=0.10]{fig22.pdf}\\~ ~ ~(b)
355 \includegraphics[scale=0.25]{principles13.eps}
356 %\includegraphics[scale=0.10]{fig25.pdf}\\~ ~ ~(d)
357 %\includegraphics[scale=0.10]{fig26.pdf}\\~ ~ ~(e)
358 %\includegraphics[scale=0.10]{fig27.pdf}\\~ ~ ~(f)
360 \caption{Wireless sensor node represented by 13 primary points}
364 \section{Coverage problem formulation}
366 %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}:\\
369 %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}:\\
371 \indent Our model is based on the model proposed by
372 \cite{pedraza2006} where the objective is to find a maximum number of
373 disjoint cover sets. To accomplish this goal, authors proposed an
374 integer program, which forces undercoverage and overcoverage of targets
375 to become minimal at the same time. They use binary variables
376 $x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our
377 model, we consider binary variables $X_{j}$, which determine the
378 activation of sensor $j$ in the sensing phase of the round. We also
379 consider primary points as targets. The set of primary points is
380 denoted by $P$ and the set of sensors by $J$.
382 \noindent For a primary point $p$, let $\alpha_{jp}$ denote the
383 indicator function of whether the point $p$ is covered, that is:
385 \alpha_{jp} = \left \{
387 1 & \mbox{if the primary point $p$ is covered} \\
388 & \mbox{by sensor node $j$}, \\
389 0 & \mbox{otherwise.}\\
393 The number of active sensors that cover the primary point $p$ is equal
394 to $\sum_{j \in J} \alpha_{jp} * X_{j}$ where:
398 1& \mbox{if sensor $j$ is active,} \\
399 0 & \mbox{otherwise.}\\
403 We define the Overcoverage variable $\Theta_{p}$ as:
405 \Theta_{p} = \left \{
407 0 & \mbox{if the primary point}\\
408 & \mbox{$p$ is not covered,}\\
409 \left( \sum_{j \in J} \alpha_{jp} * X_{j} \right)- 1 & \mbox{otherwise.}\\
413 \noindent More precisely, $\Theta_{p}$ represents the number of active
414 sensor nodes minus one that cover the primary point $p$.\\
415 The Undercoverage variable $U_{p}$ of the primary point $p$ is defined
420 1 &\mbox{if the primary point $p$ is not covered,} \\
421 0 & \mbox{otherwise.}\\
426 \noindent Our coverage optimization problem can then be formulated as follows\\
427 \begin{equation} \label{eq:ip2r}
430 \min \sum_{p \in P} (w_{\theta} \Theta_{p} + w_{U} U_{p})&\\
431 \textrm{subject to :}&\\
432 \sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, &\forall p \in P\\
434 %\sum_{t \in T} X_{j,t} \leq \frac{RE_j}{e_t} &\forall j \in J \\
436 \Theta_{p}\in \mathbb{N} , &\forall p \in P\\
437 U_{p} \in \{0,1\}, &\forall p \in P \\
438 X_{j} \in \{0,1\}, &\forall j \in J
443 \item $X_{j}$ : indicates whether or not the sensor $j$ is actively
444 sensing in the round (1 if yes and 0 if not);
445 \item $\Theta_{p}$ : {\it overcoverage}, the number of sensors minus
446 one that are covering the primary point $p$;
447 \item $U_{p}$ : {\it undercoverage}, indicates whether or not the primary point
448 $p$ is being covered (1 if not covered and 0 if covered).
451 The first group of constraints indicates that some primary point $p$
452 should be covered by at least one sensor and, if it is not always the
453 case, overcoverage and undercoverage variables help balancing the
454 restriction equations by taking positive values. There are two main
455 objectives. First, we limit the overcoverage of primary points in order to
456 activate a minimum number of sensors. Second we prevent the absence of monitoring on
457 some parts of the subregion by minimizing the undercoverage. The
458 weights $w_\theta$ and $w_U$ must be properly chosen so as to
459 guarantee that the maximum number of points are covered during each
462 %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
463 %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.
464 %\subsection{Notations and assumptions}
467 %\item $m$ : the number of targets
468 %\item $n$ : the number of sensors
469 %\item $K$ : maximal number of cover sets
470 %\item $i$ : index of target ($i=1..m$)
471 %\item $j$ : index of sensor ($j=1..n$)
472 %\item $k$ : index of cover set ($k=1..K$)
473 %\item $T_0$ : initial set of targets
474 %\item $S_0$ : initial set of sensors
475 %\item $T $ : set of targets which are not covered by at least one cover set
476 %\item $S$ : set of available sensors
477 %\item $S_0(i)$ : set of sensors which cover the target $i$
478 %\item $T_0(j)$ : set of targets covered by sensor $j$
479 %\item $C_k$ : cover set of index $k$
480 %\item $T(C_k)$ : set of targets covered by the cover set $k$
481 %\item $NS(i)$ : set of available sensors which cover the target $i$
482 %\item $NC(i)$ : set of cover sets which do not cover the target $i$
483 %\item $|.|$ : cardinality of the set
487 \section{Simulation results}
490 In this section, we conducted a series of simulations to evaluate the
491 efficiency and the relevance of our approach, using the discrete event
492 simulator OMNeT++ \cite{varga}. We performed simulations for five
493 different densities varying from 50 to 250~nodes. Experimental results
494 were obtained from randomly generated networks in which nodes are
495 deployed over a $(50 \times 25)~m^2 $ sensing field.
496 More precisely, the deployment is controlled at a coarse scale in
497 order to ensure that the deployed nodes can fully cover the sensing
498 field with the given sensing range.
499 10~simulation runs are performed with
500 different network topologies for each node density. The results
501 presented hereafter are the average of these 10 runs. A simulation
502 ends when all the nodes are dead or the sensor network becomes
503 disconnected (some nodes may not be able to send, to a base station, an
506 Our proposed coverage protocol uses the radio energy dissipation model
507 defined by~\cite{HeinzelmanCB02} as energy consumption model for each
508 wireless sensor node when transmitting or receiving packets. The
509 energy of each node in a network is initialized randomly within the
510 range 24-60~joules, and each sensor node will consume 0.2 watts during
511 the sensing period, which will last 60 seconds. Thus, an
512 active node will consume 12~joules during the sensing phase, while a
513 sleeping node will use 0.002 joules. Each sensor node will not
514 participate in the next round if its remaining energy is less than 12
515 joules. In all experiments, the parameters are set as follows:
516 $R_s=5~m$, $w_{\Theta}=1$, and $w_{U}=|P^2|$.
518 We evaluate the efficiency of our approach by using some performance
519 metrics such as: coverage ratio, number of active nodes ratio, energy
520 saving ratio, energy consumption, network lifetime, execution time,
521 and number of stopped simulation runs. Our approach called strategy~2
522 (with two leaders) works with two subregions, each one having a size
523 of $(25 \times 25)~m^2$. Our strategy will be compared with two other
524 approaches. The first one, called strategy~1 (with one leader), works
525 as strategy~2, but considers only one region of $(50 \times 25)$ $m^2$
526 with only one leader. The other approach, called Simple Heuristic,
527 consists in uniformly dividing the region into squares of $(5 \times
528 5)~m^2$. During the decision phase, in each square, a sensor is
529 randomly chosen, it will remain turned on for the coming sensing
532 \subsection{The impact of the number of rounds on the coverage ratio}
534 In this experiment, the coverage ratio measures how much the area of a
535 sensor field is covered. In our case, the coverage ratio is regarded
536 as the number of primary points covered among the set of all primary
537 points within the field. Figure~\ref{fig3} shows the impact of the
538 number of rounds on the average coverage ratio for 150 deployed nodes
539 for the three approaches. It can be seen that the three approaches
540 give similar coverage ratios during the first rounds. From the
541 9th~round the coverage ratio decreases continuously with the simple
542 heuristic, while the two other strategies provide superior coverage to
543 $90\%$ for five more rounds. Coverage ratio decreases when the number
544 of rounds increases due to dead nodes. Although some nodes are dead,
545 thanks to strategy~1 or~2, other nodes are preserved to ensure the
546 coverage. Moreover, when we have a dense sensor network, it leads to
547 maintain the full coverage for a larger number of rounds. Strategy~2 is
548 slightly more efficient than strategy 1, because strategy~2 subdivides
549 the region into 2~subregions and if one of the two subregions becomes
550 disconnected, the coverage may be still ensured in the remaining
556 \includegraphics[scale=0.5]{TheCoverageRatio150g.eps} %\\~ ~ ~(a)
557 \caption{The impact of the number of rounds on the coverage ratio for 150 deployed nodes}
561 \subsection{The impact of the number of rounds on the active sensors ratio}
563 It is important to have as few active nodes as possible in each round,
564 in order to minimize the communication overhead and maximize the
565 network lifetime. This point is assessed through the Active Sensors
566 Ratio (ASR), which is defined as follows:
569 \mbox{ASR}(\%) = \frac{\mbox{Number of active sensors
570 during the current sensing phase}}{\mbox{Total number of sensors in the network
571 for the region}} \times 100.
573 Figure~\ref{fig4} shows the average active nodes ratio versus rounds
574 for 150 deployed nodes.
578 \includegraphics[scale=0.5]{TheActiveSensorRatio150g.eps} %\\~ ~ ~(a)
579 \caption{The impact of the number of rounds on the active sensors ratio for 150 deployed nodes }
583 The results presented in figure~\ref{fig4} show the superiority of
584 both proposed strategies, the strategy with two leaders and the one
585 with a single leader, in comparison with the simple heuristic. The
586 strategy with one leader uses less active nodes than the strategy with
587 two leaders until the last rounds, because it uses central control on
588 the whole sensing field. The advantage of the strategy~2 approach is
589 that even if a network is disconnected in one subregion, the other one
590 usually continues the optimization process, and this extends the
591 lifetime of the network.
593 \subsection{The impact of the number of rounds on the energy saving ratio}
595 In this experiment, we consider a performance metric linked to energy.
596 This metric, called Energy Saving Ratio (ESR), is defined by:
599 \mbox{ESR}(\%) = \frac{\mbox{Number of alive sensors during this round}}
600 {\mbox{Total number of sensors in the network for the region}} \times 100.
602 The longer the ratio is, the more redundant sensor nodes are
603 switched off, and consequently the longer the network may live.
604 Figure~\ref{fig5} shows the average Energy Saving Ratio versus rounds
605 for all three approaches and for 150 deployed nodes.
609 % \begin{multicols}{6}
611 \includegraphics[scale=0.5]{TheEnergySavingRatio150g.eps} %\\~ ~ ~(a)
612 \caption{The impact of the number of rounds on the energy saving ratio for 150 deployed nodes}
616 The simulation results show that our strategies allow to efficiently
617 save energy by turning off some sensors during the sensing phase. As
618 expected, the strategy with one leader is usually slightly better than
619 the second strategy, because the global optimization permits to turn
620 off more sensors. Indeed, when there are two subregions more nodes
621 remain awake near the border shared by them. Note that again as the
622 number of rounds increases the two leaders' strategy becomes the most
623 performing one, since it takes longer to have the two subregion networks
624 simultaneously disconnected.
626 \subsection{The percentage of stopped simulation runs}
628 We will now study the percentage of simulations, which stopped due to
629 network disconnections per round for each of the three approaches.
630 Figure~\ref{fig6} illustrates the percentage of stopped simulation
631 runs per round for 150 deployed nodes. It can be observed that the
632 simple heuristic is the approach, which stops first because the nodes
633 are randomly chosen. Among the two proposed strategies, the
634 centralized one first exhibits network disconnections. Thus, as
635 explained previously, in case of the strategy with several subregions
636 the optimization effectively continues as long as a network in a
637 subregion is still connected. This longer partial coverage
638 optimization participates in extending the network lifetime.
642 \includegraphics[scale=0.5]{TheNumberofStoppedSimulationRuns150g.eps}
643 \caption{The percentage of stopped simulation runs compared to the number of rounds for 150 deployed nodes }
647 \subsection{The energy consumption}
649 In this experiment, we study the effect of the multi-hop communication
650 protocol on the performance of the strategy with two leaders and
651 compare it with the other two approaches. The average energy
652 consumption resulting from wireless communications is calculated
653 by taking into account the energy spent by all the nodes when transmitting and
654 receiving packets during the network lifetime. This average value,
655 which is obtained for 10~simulation runs, is then divided by the
656 average number of rounds to define a metric allowing a fair comparison
657 between networks having different densities.
659 Figure~\ref{fig7} illustrates the energy consumption for the different
660 network sizes and the three approaches. The results show that the
661 strategy with two leaders is the most competitive from the energy
662 consumption point of view. A centralized method, like the strategy
663 with one leader, has a high energy consumption due to many
664 communications. In fact, a distributed method greatly reduces the
665 number of communications thanks to the partitioning of the initial
666 network in several independent subnetworks. Let us notice that even if
667 a centralized method consumes far more energy than the simple
668 heuristic, since the energy cost of communications during a round is a
669 small part of the energy spent in the sensing phase, the
670 communications have a small impact on the network lifetime.
674 \includegraphics[scale=0.5]{TheEnergyConsumptiong.eps}
675 \caption{The energy consumption}
679 \subsection{The impact of the number of sensors on execution time}
681 A sensor node has limited energy resources and computing power,
682 therefore it is important that the proposed algorithm has the shortest
683 possible execution time. The energy of a sensor node must be mainly
684 used for the sensing phase, not for the pre-sensing ones.
685 Table~\ref{table1} gives the average execution times in seconds
686 on a laptop of the decision phase (solving of the optimization problem)
687 during one round. They are given for the different approaches and
688 various numbers of sensors. The lack of any optimization explains why
689 the heuristic has very low execution times. Conversely, the strategy
690 with one leader, which requires to solve an optimization problem
691 considering all the nodes presents redhibitory execution times.
692 Moreover, increasing the network size by 50~nodes multiplies the time
693 by almost a factor of 10. The strategy with two leaders has more
694 suitable times. We think that in distributed fashion the solving of
695 the optimization problem in a subregion can be tackled by sensor
696 nodes. Overall, to be able to deal with very large networks, a
697 distributed method is clearly required.
700 \caption{THE EXECUTION TIME(S) VS THE NUMBER OF SENSORS}
704 % used for centering table
705 \begin{tabular}{|c|c|c|c|}
706 % centered columns (4 columns)
708 %inserts double horizontal lines
709 Sensors number & Strategy~2 & Strategy~1 & Simple heuristic \\ [0.5ex]
710 & (with two leaders) & (with one leader) & \\ [0.5ex]
711 %Case & Strategy (with Two Leaders) & Strategy (with One Leader) & Simple Heuristic \\ [0.5ex]
715 % inserts single horizontal line
716 50 & 0.097 & 0.189 & 0.001 \\
717 % inserting body of the table
719 100 & 0.419 & 1.972 & 0.0032 \\
721 150 & 1.295 & 13.098 & 0.0032 \\
723 200 & 4.54 & 169.469 & 0.0046 \\
725 250 & 12.252 & 1581.163 & 0.0056 \\
726 % [1ex] adds vertical space
731 % is used to refer this table in the text
734 \subsection{The network lifetime}
736 Finally, we have defined the network lifetime as the time until all
737 nodes have been drained of their energy or each sensor network
738 monitoring an area has become disconnected. In figure~\ref{fig8}, the
739 network lifetime for different network sizes and for both strategy
740 with two leaders and the simple heuristic is illustrated.
741 We do not consider anymore the centralized strategy with one
742 leader, because, as shown above, this strategy results in execution
743 times that quickly become unsuitable for a sensor network.
747 % \begin{multicols}{6}
749 \includegraphics[scale=0.5]{TheNetworkLifetimeg.eps} %\\~ ~ ~(a)
750 \caption{The network lifetime }
754 As highlighted by figure~\ref{fig8}, the network lifetime obviously
755 increases when the size of the network increases, with our approach
756 that leads to the larger lifetime improvement. By choosing the best
757 suited nodes, for each round, to cover the region of interest and by
758 letting the other ones sleep in order to be used later in next rounds,
759 our strategy efficiently prolonges the network lifetime. Comparison shows that
760 the larger the sensor number is, the more our strategies outperform
761 the simple heuristic. Strategy~2, which uses two leaders, is the best
762 one because it is robust to network disconnection in one subregion. It
763 also means that distributing the algorithm in each node and
764 subdividing the sensing field into many subregions, which are managed
765 independently and simultaneously, is the most relevant way to maximize
766 the lifetime of a network.
768 \section{Conclusion and future works}
769 \label{sec:conclusion}
771 In this paper, we have addressed the problem of the coverage and the lifetime
772 optimization in wireless sensor networks. This is a key issue as
773 sensor nodes have limited resources in terms of memory, energy and
774 computational power. To cope with this problem, the field of sensing
775 is divided into smaller subregions using the concept of
776 divide-and-conquer method, and then a multi-rounds coverage protocol
777 will optimize coverage and lifetime performances in each subregion.
778 The proposed protocol combines two efficient techniques: network
779 leader election and sensor activity scheduling, where the challenges
780 include how to select the most efficient leader in each subregion and
781 the best representative active nodes that will optimize the network lifetime
782 while taking the responsibility of covering the corresponding
783 subregion. The network lifetime in each subregion is divided into
784 rounds, each round consists of four phases: (i) Information Exchange,
785 (ii) Leader Election, (iii) an optimization-based Decision in order to
786 select the nodes remaining active for the last phase, and (iv)
787 Sensing. The simulations show the relevance of the proposed
788 protocol in terms of lifetime, coverage ratio, active sensors ratio,
789 energy saving, energy consumption, execution time, and the number of
790 stopped simulation runs due to network disconnection. Indeed, when
791 dealing with large and dense wireless sensor networks, a distributed
792 approach like the one we propose allows to reduce the difficulty of a
793 single global optimization problem by partitioning it in many smaller
794 problems, one per subregion, that can be solved more easily.
796 In future work, we plan to study and propose a coverage protocol, which
797 computes all active sensor schedules in one time, using
798 optimization methods such as swarms optimization or evolutionary
799 algorithms. The round will still consist of 4 phases, but the
800 decision phase will compute the schedules for several sensing phases,
801 which aggregated together, define a kind of meta-sensing phase.
802 The computation of all cover sets in one time is far more
803 difficult, but will reduce the communication overhead.
804 % use section* for acknowledgement
805 %\section*{Acknowledgment}
810 \bibliographystyle{IEEEtran}
811 \bibliography{bare_conf}
