X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/LiCO.git/blobdiff_plain/d713a949431c9d95cd50776edaf8225fbfd7cee1..64b7f630f91f3e30575c2313f41cc9a400295640:/PeCO-EO/articleeo.tex diff --git a/PeCO-EO/articleeo.tex b/PeCO-EO/articleeo.tex index c0c6f7b..1236ff0 100644 --- a/PeCO-EO/articleeo.tex +++ b/PeCO-EO/articleeo.tex @@ -1,865 +1,990 @@ -% gENOguide.tex -% v4.0 released April 2013 - -\documentclass{gENO2e} -%\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e} -%\renewcommand{\algorithmcfname}{ALGORITHM} -\begin{document} - -%\jvol{00} \jnum{00} \jyear{2013} \jmonth{April} - -%\articletype{GUIDE} - -\title{{\itshape Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}} - -\author{Ali Kadhum Idrees$^{a}$, Karine Deschinkel$^{a}$$^{\ast}$\thanks{$^\ast$Corresponding author. Email: karine.deschinkel@univ-fcomte.fr}, Michel Salomon$^{a}$ and Rapha\"el Couturier $^{a}$ -$^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte, - Belfort, France}};} - - -\maketitle - -\begin{abstract} -The most important problem in a Wireless Sensor Network (WSN) is to optimize the -use of its limited energy provision, so that it can fulfill its monitoring task -as long as possible. Among known available approaches that can be used to -improve power management, lifetime coverage optimization provides activity -scheduling which ensures sensing coverage while minimizing the energy cost. We propose such an approach called Perimeter-based Coverage Optimization -protocol (PeCO). It is a hybrid of centralized and distributed methods: the -region of interest is first subdivided into subregions and our protocol is then -distributed among sensor nodes in each subregion. -The novelty of our approach lies essentially in the formulation of a new -mathematical optimization model based on the perimeter coverage level to schedule -sensors' activities. Extensive simulation experiments demonstrate that PeCO can -offer longer lifetime coverage for WSNs in comparison with some other protocols. - -\begin{keywords}Wireless Sensor Networks, Area Coverage, Energy efficiency, Optimization, Scheduling. -\end{keywords} - -\end{abstract} - - -\section{Introduction} -\label{sec:introduction} - -\noindent The continuous progress in Micro Electro-Mechanical Systems (MEMS) and -wireless communication hardware has given rise to the opportunity to use large -networks of tiny sensors, called Wireless Sensor Networks -(WSN)~\citep{akyildiz2002wireless,puccinelli2005wireless}, to fulfill monitoring -tasks. A WSN consists of small low-powered sensors working together by -communicating with one another through multi-hop radio communications. Each node -can send the data it collects in its environment, thanks to its sensor, to the -user by means of sink nodes. The features of a WSN made it suitable for a wide -range of application in areas such as business, environment, health, industry, -military, and so on~\citep{yick2008wireless}. Typically, a sensor node contains -three main components~\citep{anastasi2009energy}: a sensing unit able to measure -physical, chemical, or biological phenomena observed in the environment; a -processing unit which will process and store the collected measurements; a radio -communication unit for data transmission and receiving. - -The energy needed by an active sensor node to perform sensing, processing, and -communication is supplied by a power supply which is a battery. This battery has -a limited energy provision and it may be unsuitable or impossible to replace or -recharge it in most applications. Therefore it is necessary to deploy WSN with -high density in order to increase reliability and to exploit node redundancy -thanks to energy-efficient activity scheduling approaches. Indeed, the overlap -of sensing areas can be exploited to schedule alternatively some sensors in a -low power sleep mode and thus save energy. Overall, the main question that must -be answered is: how to extend the lifetime coverage of a WSN as long as possible -while ensuring a high level of coverage? These past few years many -energy-efficient mechanisms have been suggested to retain energy and extend the -lifetime of the WSNs~\citep{rault2014energy}.\\\\ -This paper makes the following contributions. -\begin{enumerate} -\item We have devised a framework to schedule nodes to be activated alternatively such - that the network lifetime is prolonged while ensuring that a certain level of - coverage is preserved. A key idea in our framework is to exploit spatial and - temporal subdivision. On the one hand, the area of interest is divided into - several smaller subregions and, on the other hand, the time line is divided into - periods of equal length. In each subregion the sensor nodes will cooperatively - choose a leader which will schedule nodes' activities, and this grouping of - sensors is similar to typical cluster architecture. -\item We have proposed a new mathematical optimization model. Instead of trying to - cover a set of specified points/targets as in most of the methods proposed in - the literature, we formulate an integer program based on perimeter coverage of - each sensor. The model involves integer variables to capture the deviations - between the actual level of coverage and the required level. Hence, an - optimal scheduling will be obtained by minimizing a weighted sum of these - deviations. -\item We have conducted extensive simulation experiments, using the discrete event - simulator OMNeT++, to demonstrate the efficiency of our protocol. We have compared - our PeCO protocol to two approaches found in the literature: - DESK~\citep{ChinhVu} and GAF~\citep{xu2001geography}, and also to our previous - work published in~\citep{Idrees2} which is based on another optimization model - for sensor scheduling. -\end{enumerate} - - - - - - -The rest of the paper is organized as follows. In the next section we review -some related work in the field. Section~\ref{sec:The PeCO Protocol Description} -is devoted to the PeCO protocol description and Section~\ref{cp} focuses on the -coverage model formulation which is used to schedule the activation of sensor -nodes. Section~\ref{sec:Simulation Results and Analysis} presents simulations -results and discusses the comparison with other approaches. Finally, concluding -remarks are drawn and some suggestions are given for future works in -Section~\ref{sec:Conclusion and Future Works}. - -\section{Related Literature} -\label{sec:Literature Review} - -\noindent In this section, we summarize some related works regarding the -coverage problem and distinguish our PeCO protocol from the works presented in -the literature. - -The most discussed coverage problems in literature can be classified in three -categories~\citep{li2013survey} according to their respective monitoring -objective. Hence, area coverage \citep{Misra} means that every point inside a -fixed area must be monitored, while target coverage~\citep{yang2014novel} refers -to the objective of coverage for a finite number of discrete points called -targets, and barrier coverage~\citep{HeShibo,kim2013maximum} focuses on -preventing intruders from entering into the region of interest. In -\citep{Deng2012} authors transform the area coverage problem into the target -coverage one taking into account the intersection points among disks of sensors -nodes or between disk of sensor nodes and boundaries. In -\citep{Huang:2003:CPW:941350.941367} authors prove that if the perimeters of -sensors are sufficiently covered it will be the case for the whole area. They -provide an algorithm in $O(nd~log~d)$ time to compute the perimeter-coverage of -each sensor, where $d$ denotes the maximum number of sensors that are -neighbors to a sensor and $n$ is the total number of sensors in the -network. {\it In PeCO protocol, instead of determining the level of coverage of - a set of discrete points, our optimization model is based on checking the - perimeter-coverage of each sensor to activate a minimal number of sensors.} - -The major approach to extend network lifetime while preserving coverage is to -divide/organize the sensors into a suitable number of set covers (disjoint or -non-disjoint)\citep{wang2011coverage}, where each set completely covers a region of interest, and to -activate these set covers successively. The network activity can be planned in -advance and scheduled for the entire network lifetime or organized in periods, -and the set of active sensor nodes is decided at the beginning of each period -\citep{ling2009energy}. Active node selection is determined based on the problem -requirements (e.g. area monitoring, connectivity, or power efficiency). For -instance, \citet{jaggi2006} address the problem of maximizing -the lifetime by dividing sensors into the maximum number of disjoint subsets -such that each subset can ensure both coverage and connectivity. A greedy -algorithm is applied once to solve this problem and the computed sets are -activated in succession to achieve the desired network lifetime. -\citet{chin2007}, \citet{yan2008design}, \citet{pc10}, propose algorithms -working in a periodic fashion where a cover set is computed at the beginning of -each period. {\it Motivated by these works, PeCO protocol works in periods, - where each period contains a preliminary phase for information exchange and - decisions, followed by a sensing phase where one cover set is in charge of the - sensing task.} - -Various centralized and distributed approaches, or even a mixing of these two -concepts, have been proposed to extend the network lifetime \citep{zhou2009variable}. In distributed algorithms~\citep{Tian02,yangnovel,ChinhVu,qu2013distributed} each sensor decides of its -own activity scheduling after an information exchange with its neighbors. The -main interest of such an approach is to avoid long range communications and thus -to reduce the energy dedicated to the communications. Unfortunately, since each -node has only information on its immediate neighbors (usually the one-hop ones) -it may make a bad decision leading to a global suboptimal solution. Conversely, -centralized -algorithms~\citep{cardei2005improving,zorbas2010solving,pujari2011high} always -provide nearly or close to optimal solution since the algorithm has a global -view of the whole network. The disadvantage of a centralized method is obviously -its high cost in communications needed to transmit to a single node, the base -station which will globally schedule nodes' activities, data from all the other -sensor nodes in the area. The price in communications can be huge since -long range communications will be needed. In fact the larger the WNS is, the -higher the communication and thus the energy cost are. {\it In order to be - suitable for large-scale networks, in the PeCO protocol, the area of interest - is divided into several smaller subregions, and in each one, a node called the - leader is in charge of selecting the active sensors for the current - period. Thus our protocol is scalable and is a globally distributed method, - whereas it is centralized in each subregion.} - -Various coverage scheduling algorithms have been developed these past few years. -Many of them, dealing with the maximization of the number of cover sets, are -heuristics. These heuristics involve the construction of a cover set by -including in priority the sensor nodes which cover critical targets, that is to -say targets that are covered by the smallest number of sensors -\citep{berman04,zorbas2010solving}. Other approaches are based on mathematical -programming formulations~\citep{cardei2005energy,5714480,pujari2011high,Yang2014} -and dedicated techniques (solving with a branch-and-bound algorithm available in -optimization solver). The problem is formulated as an optimization problem -(maximization of the lifetime or number of cover sets) under target coverage and -energy constraints. Column generation techniques, well-known and widely -practiced techniques for solving linear programs with too many variables, have -also been -used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012column}. {\it In the PeCO - protocol, each leader, in charge of a subregion, solves an integer program - which has a twofold objective: minimize the overcoverage and the undercoverage - of the perimeter of each sensor.} - - - -\section{ The P{\scshape e}CO Protocol Description} -\label{sec:The PeCO Protocol Description} - -\noindent In this section, we describe in details our Perimeter-based Coverage -Optimization protocol. First we present the assumptions we made and the models -we considered (in particular the perimeter coverage one), second we describe the -background idea of our protocol, and third we give the outline of the algorithm -executed by each node. - - -\subsection{Assumptions and Models} -\label{CI} - -\noindent A WSN consisting of $J$ stationary sensor nodes randomly and uniformly -distributed in a bounded sensor field is considered. The wireless sensors are -deployed in high density to ensure initially a high coverage ratio of the area -of interest. We assume that all the sensor nodes are homogeneous in terms of -communication, sensing, and processing capabilities and heterogeneous from -the energy provision point of view. The location information is available to a -sensor node either through hardware such as embedded GPS or location discovery -algorithms. We assume that each sensor node can directly transmit its -measurements to a mobile sink node. For example, a sink can be an unmanned -aerial vehicle (UAV) flying regularly over the sensor field to collect -measurements from sensor nodes. A mobile sink node collects the measurements and -transmits them to the base station. We consider a Boolean disk coverage model, -which is the most widely used sensor coverage model in the literature, and all -sensor nodes have a constant sensing range $R_s$. Thus, all the space points -within a disk centered at a sensor with a radius equal to the sensing range are -said to be covered by this sensor. We also assume that the communication range -$R_c$ satisfies $R_c \geq 2 \cdot R_s$. In fact, \citet{Zhang05} -proved that if the transmission range fulfills the previous hypothesis, the -complete coverage of a convex area implies connectivity among active nodes. - -The PeCO protocol uses the same perimeter-coverage model as \citet{huang2005coverage}. It can be expressed as follows: a sensor is -said to be perimeter covered if all the points on its perimeter are covered by -at least one sensor other than itself. They proved that a network area is -$k$-covered if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors). - -Figure~\ref{figure1}(a) shows the coverage of sensor node~$0$. On this -figure, we can see that sensor~$0$ has nine neighbors and we have reported on -its perimeter (the perimeter of the disk covered by the sensor) for each -neighbor the two points resulting from the intersection of the two sensing -areas. These points are denoted for neighbor~$i$ by $iL$ and $iR$, respectively -for left and right from a neighboing point of view. The resulting couples of -intersection points subdivide the perimeter of sensor~$0$ into portions called -arcs. - -\begin{figure}[ht!] - \centering - \begin{tabular}{@{}cr@{}} - \includegraphics[width=75mm]{figure1a.eps} & \raisebox{3.25cm}{(a)} \\ - \includegraphics[width=75mm]{figure1b.eps} & \raisebox{2.75cm}{(b)} - \end{tabular} - \caption{(a) Perimeter coverage of sensor node 0 and (b) finding the arc of - $u$'s perimeter covered by $v$.} - \label{figure1} -\end{figure} - -Figure~\ref{figure1}(b) describes the geometric information used to find the -locations of the left and right points of an arc on the perimeter of a sensor -node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the -west side of sensor~$u$, with the following respective coordinates in the -sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates we can -compute the euclidean distance between nodes~$u$ and $v$: $Dist(u,v)=\sqrt{\vert - u_x - v_x \vert^2 + \vert u_y-v_y \vert^2}$, while the angle~$\alpha$ is -obtained through the formula: - \[ -\alpha = \arccos \left(\frac{Dist(u,v)}{2R_s} -\right). -\] -The arc on the perimeter of~$u$ defined by the angular interval $[\pi - - \alpha,\pi + \alpha]$ is said to be perimeter-covered by sensor~$v$. - -Every couple of intersection points is placed on the angular interval $[0,2\pi]$ -in a counterclockwise manner, leading to a partitioning of the interval. -Figure~\ref{figure1}(a) illustrates the arcs for the nine neighbors of -sensor $0$ and figure~\ref{figure2} gives the position of the corresponding arcs -in the interval $[0,2\pi]$. More precisely, we can see that the points are -ordered according to the measures of the angles defined by their respective -positions. The intersection points are then visited one after another, starting -from the first intersection point after point~zero, and the maximum level of -coverage is determined for each interval defined by two successive points. The -maximum level of coverage is equal to the number of overlapping arcs. For -example, -between~$5L$ and~$6L$ the maximum level of coverage is equal to $3$ -(the value is highlighted in yellow at the bottom of figure~\ref{figure2}), which -means that at most 2~neighbors can cover the perimeter in addition to node $0$. -Table~\ref{my-label} summarizes for each coverage interval the maximum level of -coverage and the sensor nodes covering the perimeter. The example discussed -above is thus given by the sixth line of the table. - - -\begin{figure*}[t!] -\centering -\includegraphics[width=127.5mm]{figure2.eps} -\caption{Maximum coverage levels for perimeter of sensor node $0$.} -\label{figure2} -\end{figure*} - - - - - \begin{table} - \tbl{Coverage intervals and contributing sensors for sensor node 0 \label{my-label}} -{\begin{tabular}{|c|c|c|c|c|c|c|c|c|} -\hline -\begin{tabular}[c]{@{}c@{}}Left \\ point \\ angle~$\alpha$ \end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ left \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ right \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Maximum \\ coverage\\ level\end{tabular} & \multicolumn{5}{c|}{\begin{tabular}[c]{@{}c@{}}Set of sensors\\ involved \\ in coverage interval\end{tabular}} \\ \hline -0.0291 & 1L & 2L & 4 & 0 & 1 & 3 & 4 & \\ \hline -0.104 & 2L & 3R & 5 & 0 & 1 & 3 & 4 & 2 \\ \hline -0.3168 & 3R & 4R & 4 & 0 & 1 & 4 & 2 & \\ \hline -0.6752 & 4R & 1R & 3 & 0 & 1 & 2 & & \\ \hline -1.8127 & 1R & 5L & 2 & 0 & 2 & & & \\ \hline -1.9228 & 5L & 6L & 3 & 0 & 2 & 5 & & \\ \hline -2.3959 & 6L & 2R & 4 & 0 & 2 & 5 & 6 & \\ \hline -2.4258 & 2R & 7L & 3 & 0 & 5 & 6 & & \\ \hline -2.7868 & 7L & 8L & 4 & 0 & 5 & 6 & 7 & \\ \hline -2.8358 & 8L & 5R & 5 & 0 & 5 & 6 & 7 & 8 \\ \hline -2.9184 & 5R & 7R & 4 & 0 & 6 & 7 & 8 & \\ \hline -3.3301 & 7R & 9R & 3 & 0 & 6 & 8 & & \\ \hline -3.9464 & 9R & 6R & 4 & 0 & 6 & 8 & 9 & \\ \hline -4.767 & 6R & 3L & 3 & 0 & 8 & 9 & & \\ \hline -4.8425 & 3L & 8R & 4 & 0 & 3 & 8 & 9 & \\ \hline -4.9072 & 8R & 4L & 3 & 0 & 3 & 9 & & \\ \hline -5.3804 & 4L & 9R & 4 & 0 & 3 & 4 & 9 & \\ \hline -5.9157 & 9R & 1L & 3 & 0 & 3 & 4 & & \\ \hline -\end{tabular}} - - -\end{table} - - - - -In the PeCO protocol, the scheduling of the sensor nodes' activities is formulated with an -integer program based on coverage intervals. The formulation of the coverage -optimization problem is detailed in~section~\ref{cp}. Note that when a sensor -node has a part of its sensing range outside the WSN sensing field, as in -figure~\ref{figure3}, the maximum coverage level for this arc is set to $\infty$ -and the corresponding interval will not be taken into account by the -optimization algorithm. - - \newpage -\begin{figure}[h!] -\centering -\includegraphics[width=62.5mm]{figure3.eps} -\caption{Sensing range outside the WSN's area of interest.} -\label{figure3} -\end{figure} - - -\subsection{The Main Idea} - -\noindent The WSN area of interest is, in a first step, divided into regular -homogeneous subregions using a divide-and-conquer algorithm. In a second step -our protocol will be executed in a distributed way in each subregion -simultaneously to schedule nodes' activities for one sensing period. - -As shown in figure~\ref{figure4}, node activity scheduling is produced by our -protocol in a periodic manner. Each period is divided into 4 stages: Information -(INFO) Exchange, Leader Election, Decision (the result of an optimization -problem), and Sensing. For each period there is exactly one set cover -responsible for the sensing task. Protocols based on a periodic scheme, like -PeCO, are more robust against an unexpected node failure. On the one hand, if -a node failure is discovered before taking the decision, the corresponding sensor -node will not be considered by the optimization algorithm. On the other -hand, if the sensor failure happens after the decision, the sensing task of the -network will be temporarily affected: only during the period of sensing until a -new period starts, since a new set cover will take charge of the sensing task in -the next period. The energy consumption and some other constraints can easily be -taken into account since the sensors can update and then exchange their -information (including their residual energy) at the beginning of each period. -However, the pre-sensing phases (INFO Exchange, Leader Election, and Decision) -are energy consuming, even for nodes that will not join the set cover to monitor -the area. - -\begin{figure}[t!] -\centering -\includegraphics[width=80mm]{figure4.eps} -\caption{PeCO protocol.} -\label{figure4} -\end{figure} - -We define two types of packets to be used by PeCO protocol: - -\begin{itemize} -\item INFO packet: sent by each sensor node to all the nodes inside a same - subregion for information exchange. -\item ActiveSleep packet: sent by the leader to all the nodes in its subregion - to transmit to them their respective status (stay Active or go Sleep) during - sensing phase. -\end{itemize} - - -Five status are possible for a sensor node in the network: - -\begin{itemize} -\item LISTENING: waits for a decision (to be active or not); -\item COMPUTATION: executes the optimization algorithm as leader to - determine the activities scheduling; -\item ACTIVE: node is sensing; -\item SLEEP: node is turned off; -\item COMMUNICATION: transmits or receives packets. -\end{itemize} - - -\subsection{PeCO Protocol Algorithm} - -\noindent The pseudocode implementing the protocol on a node is given below. -More precisely, Algorithm~\ref{alg:PeCO} gives a brief description of the -protocol applied by a sensor node $s_k$ where $k$ is the node index in the WSN. - - - -\begin{algorithm} - % \KwIn{all the parameters related to information exchange} -% \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)} -% \BlankLine - %\emph{Initialize the sensor node and determine it's position and subregion} \; - -\noindent{\bf If} $RE_k \geq E_{th}$ {\bf then}\\ -\hspace*{0.6cm} \emph{$s_k.status$ = COMMUNICATION;}\\ -\hspace*{0.6cm} \emph{Send $INFO()$ packet to other nodes in subregion;}\\ -\hspace*{0.6cm} \emph{Wait $INFO()$ packet from other nodes in subregion;}\\ -\hspace*{0.6cm} \emph{Update K.CurrentSize;}\\ -\hspace*{0.6cm} \emph{LeaderID = Leader election;}\\ -\hspace*{0.6cm} {\bf If} $ s_k.ID = LeaderID $ {\bf then}\\ -\hspace*{1.2cm} \emph{$s_k.status$ = COMPUTATION;}\\ -\hspace*{1.2cm}{\bf If} \emph{$ s_k.ID $ is Not previously selected as a Leader} {\bf then}\\ -\hspace*{1.8cm} \emph{ Execute the perimeter coverage model;}\\ -\hspace*{1.2cm} {\bf end}\\ -\hspace*{1.2cm}{\bf If} \emph{($s_k.ID $ is the same Previous Leader)~And~(K.CurrentSize = K.PreviousSize)}\\ -\hspace*{1.8cm} \emph{ Use the same previous cover set for current sensing stage;}\\ -\hspace*{1.2cm} {\bf end}\\ -\hspace*{1.2cm} {\bf else}\\ -\hspace*{1.8cm}\emph{Update $a^j_{ik}$; prepare data for IP~Algorithm;}\\ -\hspace*{1.8cm} \emph{$\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$);}\\ -\hspace*{1.8cm} \emph{K.PreviousSize = K.CurrentSize;}\\ -\hspace*{1.2cm} {\bf end}\\ -\hspace*{1.2cm}\emph{$s_k.status$ = COMMUNICATION;}\\ -\hspace*{1.2cm}\emph{Send $ActiveSleep()$ to each node $l$ in subregion;}\\ -\hspace*{1.2cm}\emph{Update $RE_k $;}\\ -\hspace*{0.6cm} {\bf end}\\ -\hspace*{0.6cm} {\bf else}\\ -\hspace*{1.2cm}\emph{$s_k.status$ = LISTENING;}\\ -\hspace*{1.2cm}\emph{Wait $ActiveSleep()$ packet from the Leader;}\\ -\hspace*{1.2cm}\emph{Update $RE_k $;}\\ -\hspace*{0.6cm} {\bf end}\\ -{\bf end}\\ -{\bf else}\\ -\hspace*{0.6cm} \emph{Exclude $s_k$ from entering in the current sensing stage;}\\ -{\bf end}\\ -\label{alg:PeCO} -\end{algorithm} - - - -In this algorithm, K.CurrentSize and K.PreviousSize respectively represent the -current number and the previous number of living nodes in the subnetwork of the -subregion. Initially, the sensor node checks its remaining energy $RE_k$, which -must be greater than a threshold $E_{th}$ in order to participate in the current -period. Each sensor node determines its position and its subregion using an -embedded GPS or a location discovery algorithm. After that, all the sensors -collect position coordinates, remaining energy, sensor node ID, and the number -of their one-hop live neighbors during the information exchange. The sensors -inside a same region cooperate to elect a leader. The selection criteria for the -leader, in order of priority, are: larger numbers of neighbors, larger remaining -energy, and then in case of equality, larger index. Once chosen, the leader -collects information to formulate and solve the integer program which allows to -construct the set of active sensors in the sensing stage. - - -\section{Perimeter-based Coverage Problem Formulation} -\label{cp} - -\noindent In this section, the coverage model is mathematically formulated. We -start with a description of the notations that will be used throughout the -section.\\ -First, we have the following sets: -\begin{itemize} -\item $S$ represents the set of WSN sensor nodes; -\item $A \subseteq S $ is the subset of alive sensors; -\item $I_j$ designates the set of coverage intervals (CI) obtained for - sensor~$j$. -\end{itemize} -$I_j$ refers to the set of coverage intervals which have been defined according -to the method introduced in subsection~\ref{CI}. For a coverage interval $i$, -let $a^j_{ik}$ denotes the indicator function of whether sensor~$k$ is involved -in coverage interval~$i$ of sensor~$j$, that is: -\begin{equation} -a^j_{ik} = \left \{ -\begin{array}{lll} - 1 & \mbox{if sensor $k$ is involved in the } \\ - & \mbox{coverage interval $i$ of sensor $j$}, \\ - 0 & \mbox{otherwise.}\\ -\end{array} \right. -\end{equation} -Note that $a^k_{ik}=1$ by definition of the interval. - -Second, we define several binary and integer variables. Hence, each binary -variable $X_{k}$ determines the activation of sensor $k$ in the sensing phase -($X_k=1$ if the sensor $k$ is active or 0 otherwise). $M^j_i$ is an integer -variable which measures the undercoverage for the coverage interval $i$ -corresponding to sensor~$j$. In the same way, the overcoverage for the same -coverage interval is given by the variable $V^j_i$. - -If we decide to sustain a level of coverage equal to $l$ all along the perimeter -of sensor $j$, we have to ensure that at least $l$ sensors involved in each -coverage interval $i \in I_j$ of sensor $j$ are active. According to the -previous notations, the number of active sensors in the coverage interval $i$ of -sensor $j$ is given by $\sum_{k \in A} a^j_{ik} X_k$. To extend the network -lifetime, the objective is to activate a minimal number of sensors in each -period to ensure the desired coverage level. As the number of alive sensors -decreases, it becomes impossible to reach the desired level of coverage for all -coverage intervals. Therefore we use variables $M^j_i$ and $V^j_i$ as a measure -of the deviation between the desired number of active sensors in a coverage -interval and the effective number. And we try to minimize these deviations, -first to force the activation of a minimal number of sensors to ensure the -desired coverage level, and if the desired level cannot be completely satisfied, -to reach a coverage level as close as possible to the desired one. - - - - -Our coverage optimization problem can then be mathematically expressed as follows: - -\begin{equation} -\left \{ -\begin{array}{ll} -\min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\ -\textrm{subject to :}&\\ -\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i \geq l \quad \forall i \in I_j, \forall j \in S\\ -\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i \leq l \quad \forall i \in I_j, \forall j \in S\\ -X_{k} \in \{0,1\}, \forall k \in A -\end{array} -\right. -\end{equation} - -$\alpha^j_i$ and $\beta^j_i$ are nonnegative weights selected according to the -relative importance of satisfying the associated level of coverage. For example, -weights associated with coverage intervals of a specified part of a region may -be given by a relatively larger magnitude than weights associated with another -region. This kind of integer program is inspired from the model developed for -brachytherapy treatment planning for optimizing dose distribution -\citep{0031-9155-44-1-012}. The integer program must be solved by the leader in -each subregion at the beginning of each sensing phase, whenever the environment -has changed (new leader, death of some sensors). Note that the number of -constraints in the model is constant (constraints of coverage expressed for all -sensors), whereas the number of variables $X_k$ decreases over periods, since we -consider only alive sensors (sensors with enough energy to be alive during one -sensing phase) in the model. - -\section{Performance Evaluation and Analysis} -\label{sec:Simulation Results and Analysis} - - -\subsection{Simulation Settings} - - -The WSN area of interest is supposed to be divided into 16~regular subregions -and we use the same energy consumption than in our previous work~\citep{Idrees2}. -Table~\ref{table3} gives the chosen parameters settings. - -\begin{table}[ht] -\tbl{Relevant parameters for network initialization \label{table3}}{ - -\centering - -\begin{tabular}{c|c} - -\hline -Parameter & Value \\ [0.5ex] - -\hline -% inserts single horizontal line -Sensing field & $(50 \times 25)~m^2 $ \\ - -WSN size & 100, 150, 200, 250, and 300~nodes \\ - -Initial energy & in range 500-700~Joules \\ - -Sensing period & duration of 60 minutes \\ -$E_{th}$ & 36~Joules\\ -$R_s$ & 5~m \\ - -$\alpha^j_i$ & 0.6 \\ - -$\beta^j_i$ & 0.4 - -\end{tabular}} - - -\end{table} -To obtain experimental results which are relevant, simulations with five -different node densities going from 100 to 300~nodes were performed considering -each time 25~randomly generated networks. The nodes are deployed on a field of -interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a -high coverage ratio. Each node has an initial energy level, in Joules, which is -randomly drawn in the interval $[500-700]$. If its energy provision reaches a -value below the threshold $E_{th}=36$~Joules, the minimum energy needed for a -node to stay active during one period, it will no more participate in the -coverage task. This value corresponds to the energy needed by the sensing phase, -obtained by multiplying the energy consumed in active state (9.72 mW) with the -time in seconds for one period (3600 seconds), and adding the energy for the -pre-sensing phases. According to the interval of initial energy, a sensor may -be active during at most 20 periods. - -The values of $\alpha^j_i$ and $\beta^j_i$ have been chosen to ensure a good -network coverage and a longer WSN lifetime. We have given a higher priority to -the undercoverage (by setting the $\alpha^j_i$ with a larger value than -$\beta^j_i$) so as to prevent the non-coverage for the interval~$i$ of the -sensor~$j$. On the other hand, we have assigned to -$\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute -in covering the interval. - -We introduce the following performance metrics to evaluate the efficiency of our -approach. - - -\begin{itemize} -\item {\bf Network Lifetime}: the lifetime is defined as the time elapsed until - the coverage ratio falls below a fixed threshold. $Lifetime_{95}$ and - $Lifetime_{50}$ denote, respectively, the amount of time during which is - guaranteed a level of coverage greater than $95\%$ and $50\%$. The WSN can - fulfill the expected monitoring task until all its nodes have depleted their - energy or if the network is no more connected. This last condition is crucial - because without network connectivity a sensor may not be able to send to a - base station an event it has sensed. -\item {\bf Coverage Ratio (CR)} : it measures how well the WSN is able to - observe the area of interest. In our case, we discretized the sensor field as - a regular grid, which yields the following equation: - - -\[ - \scriptsize - \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100 -\] - - - where $n$ is the number of covered grid points by active sensors of every - subregions during the current sensing phase and $N$ is total number of grid - points in the sensing field. In our simulations we have set a layout of - $N~=~51~\times~26~=~1326$~grid points. -\item {\bf Active Sensors Ratio (ASR)}: a major objective of our protocol is to - activate as few nodes as possible, in order to minimize the communication - overhead and maximize the WSN lifetime. The active sensors ratio is defined as - follows: - -\[ - \scriptsize - \mbox{ASR}(\%) = \frac{\sum\limits_{r=1}^R \mbox{$|A_r^p|$}}{\mbox{$|S|$}} \times 100 -\] - - where $|A_r^p|$ is the number of active sensors in the subregion $r$ in the - current sensing period~$p$, $|S|$ is the number of sensors in the network, and - $R$ is the number of subregions. -\item {\bf Energy Consumption (EC)}: energy consumption can be seen as the total - energy consumed by the sensors during $Lifetime_{95}$ or $Lifetime_{50}$, - divided by the number of periods. The value of EC is computed according to - this formula: - -\[ - \scriptsize - \mbox{EC} = \frac{\sum\limits_{p=1}^{P} \left( E^{\mbox{com}}_p+E^{\mbox{list}}_p+E^{\mbox{comp}}_p - + E^{a}_p+E^{s}_p \right)}{P}, -\] - - where $P$ corresponds to the number of periods. The total energy consumed by - the sensors comes through taking into consideration four main energy - factors. The first one, denoted $E^{\scriptsize \mbox{com}}_p$, represents the - energy consumption spent by all the nodes for wireless communications during - period $p$. $E^{\scriptsize \mbox{list}}_p$, the next factor, corresponds to - the energy consumed by the sensors in LISTENING status before receiving the - decision to go active or sleep in period $p$. $E^{\scriptsize \mbox{comp}}_p$ - refers to the energy needed by all the leader nodes to solve the integer - program during a period. Finally, $E^a_{p}$ and $E^s_{p}$ indicate the energy - consumed by the WSN during the sensing phase (active and sleeping nodes). -\end{itemize} - - -\subsection{Simulation Results} - -In order to assess and analyze the performance of our protocol we have -implemented PeCO protocol in OMNeT++~\citep{varga} simulator. Besides PeCO, two -other protocols, described in the next paragraph, will be evaluated for -comparison purposes. The simulations were run on a DELL laptop with an Intel -Core~i3~2370~M (1.8~GHz) processor (2 cores) whose MIPS (Million Instructions -Per Second) rate is equal to 35330. To be consistent with the use of a sensor -node based on Atmels AVR ATmega103L microcontroller (6~MHz) having a MIPS rate -equal to 6, the original execution time on the laptop is multiplied by 2944.2 -$\left(\frac{35330}{2} \times \frac{1}{6} \right)$. The modeling language for -Mathematical Programming (AMPL)~\citep{AMPL} is employed to generate the integer -program instance in a standard format, which is then read and solved by the -optimization solver GLPK (GNU linear Programming Kit available in the public -domain) \citep{glpk} through a Branch-and-Bound method. - -As said previously, the PeCO is compared to three other approaches. The first -one, called DESK, is a fully distributed coverage algorithm proposed by -\citep{ChinhVu}. The second one, called GAF~\citep{xu2001geography}, consists in -dividing the monitoring area into fixed squares. Then, during the decision -phase, in each square, one sensor is chosen to remain active during the sensing -phase. The last one, the DiLCO protocol~\citep{Idrees2}, is an improved version -of a research work we presented in~\citep{idrees2014coverage}. Let us notice that -PeCO and DiLCO protocols are based on the same framework. In particular, the -choice for the simulations of a partitioning in 16~subregions was made because -it corresponds to the configuration producing the best results for DiLCO. The -protocols are distinguished from one another by the formulation of the integer -program providing the set of sensors which have to be activated in each sensing -phase. DiLCO protocol tries to satisfy the coverage of a set of primary points, -whereas the PeCO protocol objective is to reach a desired level of coverage for each -sensor perimeter. In our experimentations, we chose a level of coverage equal to -one ($l=1$). - -\subsubsection{\bf Coverage Ratio} - -Figure~\ref{figure5} shows the average coverage ratio for 200 deployed nodes -obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better -coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, compared to the 98.76\% -produced by PeCO for the first periods. This is due to the fact that at the -beginning the DiLCO protocol puts to sleep status more redundant sensors (which -slightly decreases the coverage ratio), while the three other protocols activate -more sensor nodes. Later, when the number of periods is beyond~70, it clearly -appears that PeCO provides a better coverage ratio and keeps a coverage ratio -greater than 50\% for longer periods (15 more compared to DiLCO, 40 more -compared to DESK). The energy saved by PeCO in the early periods allows later a -substantial increase of the coverage performance. - -\parskip 0pt -\begin{figure}[h!] -\centering - \includegraphics[scale=0.5] {figure5.eps} -\caption{Coverage ratio for 200 deployed nodes.} -\label{figure5} -\end{figure} - - - - -\subsubsection{\bf Active Sensors Ratio} - -Having the less active sensor nodes in each period is essential to minimize the -energy consumption and thus to maximize the network lifetime. Figure~\ref{figure6} -shows the average active nodes ratio for 200 deployed nodes. We observe that -DESK and GAF have 30.36 \% and 34.96 \% active nodes for the first fourteen -rounds and DiLCO and PeCO protocols compete perfectly with only 17.92~\% and -20.16~\% active nodes during the same time interval. As the number of periods -increases, PeCO protocol has a lower number of active nodes in comparison with -the three other approaches, while keeping a greater coverage ratio as shown in -figure \ref{figure5}. - -\begin{figure}[h!] -\centering -\includegraphics[scale=0.5]{figure6.eps} -\caption{Active sensors ratio for 200 deployed nodes.} -\label{figure6} -\end{figure} - -\subsubsection{\bf Energy Consumption} - -We studied the effect of the energy consumed by the WSN during the communication, -computation, listening, active, and sleep status for different network densities -and compared it for the four approaches. Figures~\ref{figure7}(a) and (b) -illustrate the energy consumption for different network sizes and for -$Lifetime95$ and $Lifetime50$. The results show that our PeCO protocol is the -most competitive from the energy consumption point of view. As shown in both -figures, PeCO consumes much less energy than the three other methods. One might -think that the resolution of the integer program is too costly in energy, but -the results show that it is very beneficial to lose a bit of time in the -selection of sensors to activate. Indeed the optimization program allows to -reduce significantly the number of active sensors and so the energy consumption -while keeping a good coverage level. - -\begin{figure}[h!] - \centering - \begin{tabular}{@{}cr@{}} - \includegraphics[scale=0.475]{figure7a.eps} & \raisebox{2.75cm}{(a)} \\ - \includegraphics[scale=0.475]{figure7b.eps} & \raisebox{2.75cm}{(b)} - \end{tabular} - \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.} - \label{figure7} -\end{figure} - - - -\subsubsection{\bf Network Lifetime} - -We observe the superiority of PeCO and DiLCO protocols in comparison with the -two other approaches in prolonging the network lifetime. In -Figures~\ref{figure8}(a) and (b), $Lifetime95$ and $Lifetime50$ are shown for -different network sizes. As highlighted by these figures, the lifetime -increases with the size of the network, and it is clearly largest for DiLCO -and PeCO protocols. For instance, for a network of 300~sensors and coverage -ratio greater than 50\%, we can see on figure~\ref{figure8}(b) that the lifetime -is about twice longer with PeCO compared to DESK protocol. The performance -difference is more obvious in figure~\ref{figure8}(b) than in -figure~\ref{figure8}(a) because the gain induced by our protocols increases with - time, and the lifetime with a coverage of 50\% is far longer than with -95\%. - -\begin{figure}[h!] - \centering - \begin{tabular}{@{}cr@{}} - \includegraphics[scale=0.475]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\ - \includegraphics[scale=0.475]{figure8b.eps} & \raisebox{2.75cm}{(b)} - \end{tabular} - \caption{Network Lifetime for (a)~$Lifetime_{95}$ \\ - and (b)~$Lifetime_{50}$.} - \label{figure8} -\end{figure} - - - -Figure~\ref{figure9} compares the lifetime coverage of our protocols for -different coverage ratios. We denote by Protocol/50, Protocol/80, Protocol/85, -Protocol/90, and Protocol/95 the amount of time during which the network can -satisfy an area coverage greater than $50\%$, $80\%$, $85\%$, $90\%$, and $95\%$ -respectively, where the term Protocol refers to DiLCO or PeCO. Indeed there are applications -that do not require a 100\% coverage of the area to be monitored. PeCO might be -an interesting method since it achieves a good balance between a high level -coverage ratio and network lifetime. PeCO always outperforms DiLCO for the three -lower coverage ratios, moreover the improvements grow with the network -size. DiLCO is better for coverage ratios near 100\%, but in that case PeCO is -not ineffective for the smallest network sizes. - -\begin{figure}[h!] -\centering \includegraphics[scale=0.5]{figure9.eps} -\caption{Network lifetime for different coverage ratios.} -\label{figure9} -\end{figure} - - - - -\section{Conclusion and Future Works} -\label{sec:Conclusion and Future Works} - -In this paper we have studied the problem of Perimeter-based Coverage Optimization in -WSNs. We have designed a new protocol, called Perimeter-based Coverage Optimization, which -schedules nodes' activities (wake up and sleep stages) with the objective of -maintaining a good coverage ratio while maximizing the network lifetime. This -protocol is applied in a distributed way in regular subregions obtained after -partitioning the area of interest in a preliminary step. It works in periods and -is based on the resolution of an integer program to select the subset of sensors -operating in active status for each period. Our work is original in so far as it -proposes for the first time an integer program scheduling the activation of -sensors based on their perimeter coverage level, instead of using a set of -targets/points to be covered. - - -We have carried out several simulations to evaluate the proposed protocol. The -simulation results show that PeCO is more energy-efficient than other -approaches, with respect to lifetime, coverage ratio, active sensors ratio, and -energy consumption. - -We plan to extend our framework so that the schedules are planned for multiple -sensing periods. - -We also want to improve our integer program to take into account heterogeneous -sensors from both energy and node characteristics point of views. - -Finally, it would be interesting to implement our protocol using a -sensor-testbed to evaluate it in real world applications. - -\bibliographystyle{gENO} -\bibliography{biblio} - - -\end{document} +% gENOguide.tex +% v4.0 released April 2013 + +\documentclass{gENO2e} +%\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e} +%\renewcommand{\algorithmcfname}{ALGORITHM} +\usepackage{indentfirst} +\usepackage[algo2e,ruled,vlined]{algorithm2e} +\begin{document} + +%\jvol{00} \jnum{00} \jyear{2013} \jmonth{April} + +%\articletype{GUIDE} + +\title{{\itshape Perimeter-based Coverage Optimization \\ + to Improve Lifetime in Wireless Sensor Networks}} + +\author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$$^{\ast}$\thanks{$^\ast$Corresponding author. Email: karine.deschinkel@univ-fcomte.fr}, Michel Salomon$^{a}$, and Rapha\"el Couturier $^{a}$ + $^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, \\ + University Bourgogne Franche-Comt\'e, Belfort, France}} \\ + $^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}} +} + +\maketitle + +\begin{abstract} +The most important problem in a Wireless Sensor Network (WSN) is to optimize the +use of its limited energy provision, so that it can fulfill its monitoring task +as long as possible. Among known available approaches that can be used to +improve power management, lifetime coverage optimization provides activity +scheduling which ensures sensing coverage while minimizing the energy cost. We +propose such an approach called Perimeter-based Coverage Optimization protocol +(PeCO). It is a hybrid of centralized and distributed methods: the region of +interest is first subdivided into subregions and the protocol is then +distributed among sensor nodes in each subregion. The novelty of our approach +lies essentially in the formulation of a new mathematical optimization model +based on the perimeter coverage level to schedule sensors' activities. +Extensive simulation experiments demonstrate that PeCO can offer longer lifetime +coverage for WSNs compared to other protocols. + +\begin{keywords} + Wireless Sensor Networks, Area Coverage, Energy efficiency, Optimization, Scheduling. +\end{keywords} + +\end{abstract} + +\section{Introduction} +\label{sec:introduction} + +The continuous progress in Micro Electro-Mechanical Systems (MEMS) and wireless +communication hardware has given rise to the opportunity of using large networks +of tiny sensors, called Wireless Sensor Networks +(WSN)~\citep{akyildiz2002wireless,puccinelli2005wireless}, to fulfill monitoring +tasks. A WSN consists of small low-powered sensors working together by +communicating with one another through multi-hop radio communications. Each node +can send the data it collects in its environment, thanks to its sensor, to the +user by means of sink nodes. The features of a WSN makes it suitable for a wide +range of applications in areas such as business, environment, health, industry, +military, and so on~\citep{yick2008wireless}. Typically, a sensor node contains +three main components~\citep{anastasi2009energy}: a sensing unit able to measure +physical, chemical, or biological phenomena observed in the environment; a +processing unit which will process and store the collected measurements; a radio +communication unit for data transmission and reception. + +The energy needed by an active sensor node to perform sensing, processing, and +communication is provided by a power supply which is a battery. This battery has +a limited energy provision and it may be unsuitable or impossible to replace or +recharge in most applications. Therefore it is necessary to deploy WSN with high +density in order to increase reliability and to exploit node redundancy thanks +to energy-efficient activity scheduling approaches. Indeed, the overlap of +sensing areas can be exploited to schedule alternatively some sensors in a low +power sleep mode and thus save energy. Overall, the main question that must be +answered is: how is it possible to extend the lifetime coverage of a WSN as long +as possible while ensuring a high level of coverage? These past few years many +energy-efficient mechanisms have been suggested to retain energy and extend the +lifetime of the WSNs~\citep{rault2014energy}. + +This paper makes the following contributions : +\begin{enumerate} +\item A framework is devised to schedule nodes to be activated alternatively + such that the network lifetime is prolonged while ensuring that a certain + level of coverage is preserved. A key idea in the proposed framework is to + exploit spatial and temporal subdivision. On the one hand, the area of + interest is divided into several smaller subregions and, on the other hand, + the time line is divided into periods of equal length. In each subregion the + sensor nodes will cooperatively choose a leader which will schedule nodes' + activities, and this grouping of sensors is similar to typical cluster + architecture. +\item A new mathematical optimization model is proposed. Instead of trying to + cover a set of specified points/targets as in most of the methods proposed in + the literature, we formulate a mixed-integer program based on the perimeter + coverage of each sensor. The model involves integer variables to capture the + deviations between the actual level of coverage and the required level. + Hence, an optimal schedule will be obtained by minimizing a weighted sum of + these deviations. +\item Extensive simulation experiments are conducted using the discrete event + simulator OMNeT++, to demonstrate the efficiency of our protocol. We have + compared the PeCO protocol to two approaches found in the literature: + DESK~\citep{ChinhVu} and GAF~\citep{xu2001geography}, and also to our previous + protocol DiLCO published in~\citep{Idrees2}. DiLCO uses the same framework as + PeCO but is based on another optimization model for sensor scheduling. +\end{enumerate} + +The rest of the paper is organized as follows. In the next section some related +work in the field is reviewed. Section~\ref{sec:The PeCO Protocol Description} +is devoted to the PeCO protocol description and Section~\ref{cp} focuses on the +coverage model formulation which is used to schedule the activation of sensor +nodes. Section~\ref{sec:Simulation Results and Analysis} presents simulations +results and discusses the comparison with other approaches. Finally, concluding +remarks are drawn and some suggestions are given for future works in +Section~\ref{sec:Conclusion and Future Works}. + +\section{Related Literature} +\label{sec:Literature Review} + +This section summarizes some related works regarding the coverage problem and +presents specific aspects of the PeCO protocol common with other literature +works. + +The most discussed coverage problems in literature can be classified in three +categories~\citep{li2013survey} according to their respective monitoring +objective. Hence, area coverage \citep{Misra} means that every point inside a +fixed area must be monitored, while target coverage~\citep{yang2014novel} refers +to the objective of coverage for a finite number of discrete points called +targets, and barrier coverage~\citep{HeShibo,kim2013maximum} focuses on +preventing intruders from entering into the region of interest. In +\citep{Deng2012} authors transform the area coverage problem into the target +coverage one, taking into account the intersection points among disks of sensors +nodes or between disks of sensor nodes and boundaries. In +\citep{huang2005coverage} authors prove that if the perimeters of the sensors +are sufficiently covered it will be the case for the whole area. They provide an +algorithm in $O(nd~log~d)$ time to compute the perimeter-coverage of each +sensor. $d$ denotes the maximum number of sensors that are neighbors to a +sensor, and $n$ is the total number of sensors in the network. {\it In PeCO + protocol, instead of determining the level of coverage of a set of discrete + points, our optimization model is based on checking the perimeter-coverage of + each sensor to activate a minimal number of sensors.} + +The major approach to extend network lifetime while preserving coverage is to +divide/organize the sensors into a suitable number of set covers (disjoint or +non-disjoint) \citep{wang2011coverage}, where each set completely covers a +region of interest, and to successively activate these set covers. The network +activity can be planned in advance and scheduled for the entire network lifetime +or organized in periods, and the set of active sensor nodes decided at the +beginning of each period \citep{ling2009energy}. In fact, many authors propose +algorithms working in such a periodic fashion +\citep{chin2007,yan2008design,pc10}. Active node selection is determined based +on the problem requirements (e.g. area monitoring, connectivity, or power +efficiency). For instance, \citet{jaggi2006} address the problem of maximizing +the lifetime by dividing sensors into the maximum number of disjoint subsets +such that each subset can ensure both coverage and connectivity. A greedy +algorithm is applied once to solve this problem and the computed sets are +activated in succession to achieve the desired network lifetime. {\it Motivated + by these works, PeCO protocol works in periods, where each period contains a + preliminary phase for information exchange and decisions, followed by a + sensing phase where one cover set is in charge of the sensing task.} + +Various centralized and distributed approaches, or even a mixing of these two +concepts, have been proposed to extend the network lifetime +\citep{zhou2009variable}. In distributed +algorithms~\citep{ChinhVu,qu2013distributed,yangnovel} each sensor decides of +its own activity scheduling after an information exchange with its neighbors. +The main interest of such an approach is to avoid long range communications and +thus to reduce the energy dedicated to the communications. Unfortunately, since +each node has information on its immediate neighbors only (usually the one-hop +ones), it may make a bad decision leading to a global suboptimal solution. +Conversely, centralized +algorithms~\citep{cardei2005improving,zorbas2010solving,pujari2011high} always +provide nearly optimal solutions since the algorithm has a global view of the +whole network. The disadvantage of a centralized method is obviously its high +cost in communications needed to transmit to a single node, the base station +which will globally schedule nodes' activities, data from all the other sensor +nodes in the area. The price in communications can be huge since long range +communications will be needed. In fact the larger the WSN, the higher the +communication energy cost. {\it In order to be suitable for large-scale + networks, in the PeCO protocol the area of interest is divided into several + smaller subregions, and in each one, a node called the leader is in charge of + selecting the active sensors for the current period. Thus the PeCO protocol + is scalable and a globally distributed method, whereas it is centralized in + each subregion.} + +Various coverage scheduling algorithms have been developed these past few years. +Many of them, dealing with the maximization of the number of cover sets, are +heuristics. These heuristics involve the construction of a cover set by +including in priority the sensor nodes which cover critical targets, that is to +say targets that are covered by the smallest number of sensors +\citep{berman04,zorbas2010solving}. Other approaches are based on mathematical +programming +formulations~\citep{cardei2005energy,5714480,pujari2011high,Yang2014} and +dedicated techniques (solving with a branch-and-bound algorithm available in +optimization solver). The problem is formulated as an optimization problem +(maximization of the lifetime or number of cover sets) under target coverage and +energy constraints. Column generation techniques, well-known and widely +practiced techniques for solving linear programs with too many variables, have +also been +used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012column}. +{\it In the PeCO protocol, each leader, in charge of a subregion, solves an + integer program which has a twofold objective: minimizing the overcoverage and + the undercoverage of the perimeter of each sensor.} + +The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage +Optimization (DiLCO) protocol, which maintains the coverage and improves the +lifetime in WSNs. It is an improved version of a research work presented +in~\citep{idrees2014coverage}. First, the area of interest is partitioned into +subregions using a divide-and-conquer method. The DiLCO protocol is then +distributed on the sensor nodes in each subregion in a second step. Hence this +protocol combines two techniques: a leader election in each subregion, followed +by an optimization-based node activity scheduling performed by each elected +leader. The proposed DiLCO protocol is a periodic protocol where each period is +decomposed into 4 phases: information exchange, leader election, decision, and +sensing. The simulations show that DiLCO is able to increase the WSN lifetime +and provides improved coverage performance. {\it In the PeCO protocol, a new + mathematical optimization model is proposed. Instead of trying to cover a set + of specified points/targets as in the DiLCO protocol, we formulate an integer + program based on the perimeter coverage of each sensor. The model involves + integer variables to capture the deviations between the actual level of + coverage and the required level. The idea is that an optimal scheduling will + be obtained by minimizing a weighted sum of these deviations.} + +\section{ The P{\scshape e}CO Protocol Description} +\label{sec:The PeCO Protocol Description} + +%In this section, the Perimeter-based Coverage +%Optimization protocol is decribed in details. First we present the assumptions we made and the models +%we considered (in particular the perimeter coverage one), second we describe the +%background idea of our protocol, and third we give the outline of the algorithm +%executed by each node. + + +\subsection{Assumptions and Models} +\label{CI} + +A WSN consisting of $J$ stationary sensor nodes randomly and uniformly +distributed in a bounded sensor field is considered. The wireless sensors are +deployed in high density to ensure initially a high coverage ratio of the area +of interest. All the sensor nodes are supposed to be homogeneous in terms of +communication, sensing, and processing capabilities and heterogeneous from the +energy provision point of view. The location information is available to a +sensor node either through hardware such as embedded GPS or location discovery +algorithms. A Boolean disk coverage model, which is the most widely used sensor +coverage model in the literature, is considered and all sensor nodes have a +constant sensing range $R_s$. Thus, all the space points within a disk centered +at a sensor with a radius equal to the sensing range are said to be covered by +this sensor. We also assume that the communication range $R_c$ satisfies $R_c +\geq 2 \cdot R_s$. In fact, \citet{Zhang05} proved that if the transmission +range fulfills the previous hypothesis, the complete coverage of a convex area +implies connectivity among active nodes. + +The PeCO protocol uses the same perimeter-coverage model as +\citet{huang2005coverage}. It can be expressed as follows: a sensor is said to +be perimeter covered if all the points on its perimeter are covered by at least +one sensor other than itself. Authors \citet{huang2005coverage} proved that a +network area is $k$-covered (every point in the area is covered by at least +$k$~sensors) if and only if each sensor in the network is $k$-perimeter-covered +(perimeter covered by at least $k$ sensors). + +Figure~\ref{figure1}(a) shows the coverage of sensor node~$0$. On this figure, +sensor~$0$ has nine neighbors and we have reported on its perimeter (the +perimeter of the disk covered by the sensor) for each neighbor the two points +resulting from the intersection of the two sensing areas. These points are +denoted for neighbor~$i$ by $iL$ and $iR$, respectively for left and right from +a neighboring point of view. The resulting couples of intersection points +subdivide the perimeter of sensor~$0$ into portions called arcs. + +\begin{figure}[ht!] + \centering + \begin{tabular}{@{}cr@{}} + \includegraphics[width=75mm]{figure1a.eps} & \raisebox{3.25cm}{(a)} \\ + \includegraphics[width=75mm]{figure1b.eps} & \raisebox{2.75cm}{(b)} + \end{tabular} + \caption{(a) Perimeter coverage of sensor node 0 and (b) finding the arc of + $u$'s perimeter covered by $v$.} + \label{figure1} +\end{figure} + +Figure~\ref{figure1}(b) describes the geometric information used to find the +locations of the left and right points of an arc on the perimeter of a sensor +node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the +west side of sensor~$u$, with the following respective coordinates in the +sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates the +euclidean distance between nodes~$u$ and $v$ is computed as follows: +$$ + Dist(u,v)=\sqrt{(u_x - v_x)^2 + (u_y-v_y)^2}, +$$ +while the angle~$\alpha$ is obtained through the formula: + \[ +\alpha = \arccos \left(\frac{Dist(u,v)}{2R_s} \right). +\] +The arc on the perimeter of~$u$ defined by the angular interval $[\pi - + \alpha,\pi + \alpha]$ is then said to be perimeter-covered by sensor~$v$. + +Every couple of intersection points is placed on the angular interval $[0,2\pi)$ +in a counterclockwise manner, leading to a partitioning of the interval. +Figure~\ref{figure1}(a) illustrates the arcs for the nine neighbors of +sensor $0$ and Table~\ref{my-label} gives the position of the corresponding arcs +in the interval $[0,2\pi)$. More precisely, the points are +ordered according to the measures of the angles defined by their respective +positions. The intersection points are then visited one after another, starting +from the first intersection point after point~zero, and the maximum level of +coverage is determined for each interval defined by two successive points. The +maximum level of coverage is equal to the number of overlapping arcs. For +example, between~$5L$ and~$6L$ the maximum level of coverage is equal to $3$ +(the value is highlighted in yellow at the bottom of Figure~\ref{figure2}), which +means that at most 2~neighbors can cover the perimeter in addition to node $0$. +Table~\ref{my-label} summarizes for each coverage interval the maximum level of +coverage and the sensor nodes covering the perimeter. The example discussed +above is thus given by the sixth line of the table. + +\begin{figure*}[t!] +\centering +\includegraphics[width=0.95\linewidth]{figure2.eps} +\caption{Maximum coverage levels for perimeter of sensor node $0$.} +\label{figure2} +\end{figure*} + +\begin{table} +\tbl{Coverage intervals and contributing sensors for node 0 \label{my-label}} +{\begin{tabular}{|c|c|c|c|c|c|c|c|c|} +\hline +\begin{tabular}[c]{@{}c@{}}Left \\ point \\ angle~$\alpha$ \end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ left \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ right \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Maximum \\ coverage\\ level\end{tabular} & \multicolumn{5}{c|}{\begin{tabular}[c]{@{}c@{}}Set of sensors\\ involved \\ in coverage interval\end{tabular}} \\ \hline +0.0291 & 1L & 2L & 4 & 0 & 1 & 3 & 4 & \\ \hline +0.104 & 2L & 3R & 5 & 0 & 1 & 3 & 4 & 2 \\ \hline +0.3168 & 3R & 4R & 4 & 0 & 1 & 4 & 2 & \\ \hline +0.6752 & 4R & 1R & 3 & 0 & 1 & 2 & & \\ \hline +1.8127 & 1R & 5L & 2 & 0 & 2 & & & \\ \hline +1.9228 & 5L & 6L & 3 & 0 & 2 & 5 & & \\ \hline +2.3959 & 6L & 2R & 4 & 0 & 2 & 5 & 6 & \\ \hline +2.4258 & 2R & 7L & 3 & 0 & 5 & 6 & & \\ \hline +2.7868 & 7L & 8L & 4 & 0 & 5 & 6 & 7 & \\ \hline +2.8358 & 8L & 5R & 5 & 0 & 5 & 6 & 7 & 8 \\ \hline +2.9184 & 5R & 7R & 4 & 0 & 6 & 7 & 8 & \\ \hline +3.3301 & 7R & 9R & 3 & 0 & 6 & 8 & & \\ \hline +3.9464 & 9R & 6R & 4 & 0 & 6 & 8 & 9 & \\ \hline +4.767 & 6R & 3L & 3 & 0 & 8 & 9 & & \\ \hline +4.8425 & 3L & 8R & 4 & 0 & 3 & 8 & 9 & \\ \hline +4.9072 & 8R & 4L & 3 & 0 & 3 & 9 & & \\ \hline +5.3804 & 4L & 9R & 4 & 0 & 3 & 4 & 9 & \\ \hline +5.9157 & 9R & 1L & 3 & 0 & 3 & 4 & & \\ \hline +\end{tabular}} + + +\end{table} + +In the PeCO protocol, the scheduling of the sensor nodes' activities is +formulated with a mixed-integer program based on coverage +intervals~\citep{doi:10.1155/2010/926075}. The formulation of the coverage +optimization problem is detailed in~Section~\ref{cp}. Note that when a sensor +node has a part of its sensing range outside the WSN sensing field, as in +Figure~\ref{figure3}, the maximum coverage level for this arc is set to $\infty$ +and the corresponding interval will not be taken into account by the +optimization algorithm. + +%\newpage +\begin{figure}[h!] +\centering +\includegraphics[width=57.5mm]{figure3.eps} +\caption{Sensing range outside the WSN's area of interest.} +\label{figure3} +\end{figure} + +\vspace{-0.25cm} + +\subsection{Main Idea} + +The WSN area of interest is, in a first step, divided into regular homogeneous +subregions using a divide-and-conquer algorithm. In a second step our protocol +will be executed in a distributed way in each subregion simultaneously to +schedule nodes' activities for one sensing period. Sensor nodes are assumed to +be deployed almost uniformly over the region. The regular subdivision is made +such that the number of hops between any pairs of sensors inside a subregion is +less than or equal to 3. + +As shown in Figure~\ref{figure4}, node activity scheduling is produced by the +proposed protocol in a periodic manner. Each period is divided into 4 stages: +Information (INFO) Exchange, Leader Election, Decision (the result of an +optimization problem), and Sensing. For each period there is exactly one set +cover responsible for the sensing task. Protocols based on a periodic scheme, +like PeCO, are more robust against an unexpected node failure. On the one hand, +if a node failure is discovered before taking the decision, the corresponding +sensor node will not be considered by the optimization algorithm. On the other +hand, if the sensor failure happens after the decision, the sensing task of the +network will be temporarily affected: only during the period of sensing until a +new period starts, since a new set cover will take charge of the sensing task in +the next period. The energy consumption and some other constraints can easily be +taken into account since the sensors can update and then exchange their +information (including their residual energy) at the beginning of each period. +However, the pre-sensing phases (INFO Exchange, Leader Election, and Decision) +are energy consuming, even for nodes that will not join the set cover to monitor +the area. Sensing period duration is adapted according to the QoS requirements +of the application. + +\begin{figure}[t!] +\centering +\includegraphics[width=80mm]{figure4.eps} +\caption{PeCO protocol.} +\label{figure4} +\end{figure} + +We define two types of packets to be used by the PeCO protocol: +\begin{itemize} +\item INFO packet: sent by each sensor node to all the nodes inside a same + subregion for information exchange. +\item ActiveSleep packet: sent by the leader to all the nodes in its subregion + to transmit to them their respective status (stay Active or go Sleep) during + the sensing phase. +\end{itemize} + +Five statuses are possible for a sensor node in the network: +\begin{itemize} +\item LISTENING: waits for a decision (to be active or not); +\item COMPUTATION: executes the optimization algorithm as leader to + determine the activities scheduling; +\item ACTIVE: node is sensing; +\item SLEEP: node is turned off; +\item COMMUNICATION: transmits or receives packets. +\end{itemize} + +\subsection{PeCO Protocol Algorithm} + +The pseudocode implementing the protocol on a node is given below. More +precisely, Algorithm~\ref{alg:PeCO} gives a brief description of the protocol +applied by a sensor node $s_k$ where $k$ is the node index in the WSN. + + +\begin{algorithm2e} + % \KwIn{all the parameters related to information exchange} +% \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)} +% \BlankLine + %\emph{Initialize the sensor node and determine it's position and subregion} \; + \label{alg:PeCO} + \caption{PeCO pseudocode} + \eIf{$RE_k \geq E_{th}$}{ + $s_k.status$ = COMMUNICATION\; + Send $INFO()$ packet to other nodes in subregion\; + Wait $INFO()$ packet from other nodes in subregion\; + Update K.CurrentSize\; + LeaderID = Leader election\; + \eIf{$s_k.ID = LeaderID$}{ + $s_k.status$ = COMPUTATION\; + \If{$ s_k.ID $ is Not previously selected as a Leader}{ + Execute the perimeter coverage model\; + } + \eIf{($s_k.ID $ is the same Previous Leader) {\bf and} \\ + \indent (K.CurrentSize = K.PreviousSize)}{ + Use the same previous cover set for current sensing stage\; + }{ + Update $a^j_{ik}$; prepare data for IP~Algorithm\; + $\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$)\; + K.PreviousSize = K.CurrentSize\; + } + $s_k.status$ = COMMUNICATION\; + Send $ActiveSleep()$ to each node $l$ in subregion\; + Update $RE_k $\; + }{ + $s_k.status$ = LISTENING\; + Wait $ActiveSleep()$ packet from the Leader\; + Update $RE_k $\; + } + }{ + Exclude $s_k$ from entering in the current sensing stage\; + } +\end{algorithm2e} + +%\begin{algorithm} +%\noindent{\bf If} $RE_k \geq E_{th}$ {\bf then}\\ +%\hspace*{0.6cm} \emph{$s_k.status$ = COMMUNICATION;}\\ +%\hspace*{0.6cm} \emph{Send $INFO()$ packet to other nodes in subregion;}\\ +%\hspace*{0.6cm} \emph{Wait $INFO()$ packet from other nodes in subregion;}\\ +%\hspace*{0.6cm} \emph{Update K.CurrentSize;}\\ +%\hspace*{0.6cm} \emph{LeaderID = Leader election;}\\ +%\hspace*{0.6cm} {\bf If} $ s_k.ID = LeaderID $ {\bf then}\\ +%\hspace*{1.2cm} \emph{$s_k.status$ = COMPUTATION;}\\ +%\hspace*{1.2cm}{\bf If} \emph{$ s_k.ID $ is Not previously selected as a Leader} {\bf then}\\ +%\hspace*{1.8cm} \emph{ Execute the perimeter coverage model;}\\ +%\hspace*{1.2cm} {\bf end}\\ +%\hspace*{1.2cm}{\bf If} \emph{($s_k.ID $ is the same Previous Leader)~And~(K.CurrentSize = K.PreviousSize)}\\ +%\hspace*{1.8cm} \emph{ Use the same previous cover set for current sensing stage;}\\ +%\hspace*{1.2cm} {\bf end}\\ +%\hspace*{1.2cm} {\bf else}\\ +%\hspace*{1.8cm}\emph{Update $a^j_{ik}$; prepare data for IP~Algorithm;}\\ +%\hspace*{1.8cm} \emph{$\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$);}\\ +%\hspace*{1.8cm} \emph{K.PreviousSize = K.CurrentSize;}\\ +%\hspace*{1.2cm} {\bf end}\\ +%\hspace*{1.2cm}\emph{$s_k.status$ = COMMUNICATION;}\\ +%\hspace*{1.2cm}\emph{Send $ActiveSleep()$ to each node $l$ in subregion;}\\ +%\hspace*{1.2cm}\emph{Update $RE_k $;}\\ +%\hspace*{0.6cm} {\bf end}\\ +%\hspace*{0.6cm} {\bf else}\\ +%\hspace*{1.2cm}\emph{$s_k.status$ = LISTENING;}\\ +%\hspace*{1.2cm}\emph{Wait $ActiveSleep()$ packet from the Leader;}\\ +%\hspace*{1.2cm}\emph{Update $RE_k $;}\\ +%\hspace*{0.6cm} {\bf end}\\ +%{\bf end}\\ +%{\bf else}\\ +%\hspace*{0.6cm} \emph{Exclude $s_k$ from entering in the current sensing stage;}\\ +%{\bf end}\\ +%\label{alg:PeCO} +%\end{algorithm} + +In this algorithm, $K.CurrentSize$ and $K.PreviousSize$ respectively represent +the current number and the previous number of living nodes in the subnetwork of +the subregion. At the beginning of the first period $K.PreviousSize$ is +initialized to zero. Initially, the sensor node checks its remaining energy +$RE_k$, which must be greater than a threshold $E_{th}$ in order to participate +in the current period. Each sensor node determines its position and its +subregion using an embedded GPS or a location discovery algorithm. After that, +all the sensors collect position coordinates, remaining energy, sensor node ID, +and the number of their one-hop live neighbors during the information exchange. +The sensors inside a same region cooperate to elect a leader. The selection +criteria for the leader are (in order of priority): +\begin{enumerate} +\item larger number of neighbors; +\item larger remaining energy; +\item and then, in case of equality, larger indexes. +\end{enumerate} +Once chosen, the leader collects information to formulate and solve the integer +program which allows to build the set of active sensors in the sensing +stage. + +\section{Perimeter-based Coverage Problem Formulation} +\label{cp} + +In this section, the perimeter-based coverage problem is mathematically +formulated. It has been proved to be a NP-hard problem +by \citep{doi:10.1155/2010/926075}. Authors study the coverage of the perimeter +of a large object requiring to be monitored. For the proposed formulation in +this paper, the large object to be monitored is the sensor itself (or more +precisely its sensing area). + +The following notations are used throughout the section. + +First, the following sets: +\begin{itemize} +\item $S$ represents the set of sensor nodes; +\item $A \subseteq S $ is the subset of alive sensors; +\item $I_j$ designates the set of coverage intervals (CI) obtained for + sensor~$j$. +\end{itemize} +$I_j$ refers to the set of coverage intervals which has been defined according +to the method introduced in Subsection~\ref{CI}. For a coverage interval $i$, +let $a^j_{ik}$ denote the indicator function of whether sensor~$k$ is involved +in coverage interval~$i$ of sensor~$j$, that is: +\begin{equation} +a^j_{ik} = \left \{ +\begin{array}{lll} + 1 & \mbox{if sensor $k$ is involved in the } \\ + & \mbox{coverage interval $i$ of sensor $j$}, \\ + 0 & \mbox{otherwise.}\\ +\end{array} \right. +\end{equation} +Note that $a^k_{ik}=1$ by definition of the interval. + +Second, several variables are defined. Hence, each binary variable $X_{k}$ +determines the activation of sensor $k$ in the sensing phase ($X_k=1$ if the +sensor $k$ is active or 0 otherwise). $M^j_i$ is a variable which measures the +undercoverage for the coverage interval $i$ corresponding to sensor~$j$. In the +same way, the overcoverage for the same coverage interval is given by the +variable $V^j_i$. + +To sustain a level of coverage equal to $l$ all along the perimeter of sensor +$j$, at least $l$ sensors involved in each coverage interval $i \in I_j$ of +sensor $j$ have to be active. According to the previous notations, the number +of active sensors in the coverage interval $i$ of sensor $j$ is given by +$\sum_{k \in A} a^j_{ik} X_k$. To extend the network lifetime, the objective is +to activate a minimal number of sensors in each period to ensure the desired +coverage level. As the number of alive sensors decreases, it becomes impossible +to reach the desired level of coverage for all coverage intervals. Therefore +variables $M^j_i$ and $V^j_i$ are introduced as a measure of the deviation +between the desired number of active sensors in a coverage interval and the +effective number. And we try to minimize these deviations, first to force the +activation of a minimal number of sensors to ensure the desired coverage level, +and if the desired level cannot be completely satisfied, to reach a coverage +level as close as possible to the desired one. + +The coverage optimization problem can then be mathematically expressed as follows: +\begin{equation} + \begin{aligned} + \text{Minimize } & \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i ) \\ + \text{Subject to:} & \\ + & \sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i \geq l \quad \forall i \in I_j, \forall j \in S \\ + & \sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i \leq l \quad \forall i \in I_j, \forall j \in S \\ + & X_{k} \in \{0,1\}, \forall k \in A \\ + & M^j_i, V^j_i \in \mathbb{R}^{+} + \end{aligned} +\end{equation} + +%\begin{equation} +%\left \{ +%\begin{array}{ll} +%\min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i ) & \\ +%\textrm{subject to :} &\\ +%\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i \geq l \quad \forall i \in I_j, \forall j \in S\\ +%\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i \leq l \quad \forall i \in I_j, \forall j \in S\\ +%X_{k} \in \{0,1\}, \forall k \in A \\ +%M^j_i, V^j_i \in \mathbb{R}^{+} +%\end{array} +%\right. +%\end{equation} + +If a given level of coverage $l$ is required for one sensor, the sensor is said +to be undercovered (respectively overcovered) if the level of coverage of one of +its CI is less (respectively greater) than $l$. If the sensor $j$ is +undercovered, there exists at least one of its CI (say $i$) for which the number +of active sensors (denoted by $l^{i}$) covering this part of the perimeter is +less than $l$ and in this case : $M_{i}^{j}=l-l^{i}$, $V_{i}^{j}=0$. Conversely, +if the sensor $j$ is overcovered, there exists at least one of its CI (say $i$) +for which the number of active sensors (denoted by $l^{i}$) covering this part +of the perimeter is greater than $l$ and in this case: $M_{i}^{j}=0$, +$V_{i}^{j}=l^{i}-l$. + +$\alpha^j_i$ and $\beta^j_i$ are nonnegative weights selected according to the +relative importance of satisfying the associated level of coverage. For example, +weights associated with coverage intervals of the specified part of a region may +be given by a relatively larger magnitude than weights associated with another +region. This kind of mixed-integer program is inspired from the model developed +for brachytherapy treatment planning to optimize dose distribution +\citep{0031-9155-44-1-012}. The choice of the values for variables $\alpha$ and +$\beta$ should be made according to the needs of the application. $\alpha$ +should be large enough to prevent undercoverage and so to reach the highest +possible coverage ratio. $\beta$ should be large enough to prevent overcoverage +and so to activate a minimum number of sensors. The mixed-integer program must +be solved by the leader in each subregion at the beginning of each sensing +phase, whenever the environment has changed (new leader, death of some sensors). +Note that the number of constraints in the model is constant (constraints of +coverage expressed for all sensors), whereas the number of variables $X_k$ +decreases over periods, since only alive sensors (sensors with enough energy to +be alive during one sensing phase) are considered in the model. + +\section{Performance Evaluation and Analysis} +\label{sec:Simulation Results and Analysis} + +\subsection{Simulation Settings} + +The WSN area of interest is supposed to be divided into 16~regular subregions +and we use the same energy consumption model as in our previous +work~\citep{Idrees2}. Table~\ref{table3} gives the chosen parameters settings. + +\begin{table}[ht] +\tbl{Relevant parameters for network initialization \label{table3}}{ +\centering +\begin{tabular}{c|c} +\hline +Parameter & Value \\ [0.5ex] +\hline +% inserts single horizontal line +Sensing field & $(50 \times 25)~m^2 $ \\ +WSN size & 100, 150, 200, 250, and 300~nodes \\ +Initial energy & in range 500-700~Joules \\ +Sensing period & duration of 60 minutes \\ +$E_{th}$ & 36~Joules \\ +$R_s$ & 5~m \\ +$R_c$ & 10~m \\ +$\alpha^j_i$ & 0.6 \\ +$\beta^j_i$ & 0.4 +\end{tabular}} +\end{table} + +To obtain experimental results which are relevant, simulations with five +different node densities going from 100 to 300~nodes were performed considering +each time 25~randomly generated networks. The nodes are deployed on a field of +interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a +high coverage ratio. Each node has an initial energy level, in Joules, which is +randomly drawn in the interval $[500-700]$. If its energy provision reaches a +value below the threshold $E_{th}=36$~Joules, the minimum energy needed for a +node to stay active during one period, it will no longer participate in the +coverage task. This value corresponds to the energy needed by the sensing phase, +obtained by multiplying the energy consumed in the active state (9.72 mW) with +the time in seconds for one period (3600 seconds), and adding the energy for the +pre-sensing phases. According to the interval of initial energy, a sensor may +be active during at most 20 periods. the information exchange to update the coverage +is executed every hour, but the length of the sensing period could be reduced +and adapted dynamically. On the one hand a small sensing period would allow the network to +be more reliable but would have resulted in higher communication costs. On the +other hand the choice of a long duration may cause problems in case of nodes +failure during the sensing period. + +The values of $\alpha^j_i$ and $\beta^j_i$ have been chosen to ensure a good +network coverage and a longer WSN lifetime. Higher priority is given to the +undercoverage (by setting the $\alpha^j_i$ with a larger value than $\beta^j_i$) +so as to prevent the non-coverage for the interval~$i$ of the sensor~$j$. On +the other hand, $\beta^j_i$ is assigned to a value which is slightly lower so as +to minimize the number of active sensor nodes which contribute in covering the +interval. Subsection~\ref{sec:Impact} investigates more deeply how the values of +both parameters affect the performance of the PeCO protocol. + +The following performance metrics are used to evaluate the efficiency of the +approach. +\begin{itemize} +\item {\bf Network Lifetime}: the lifetime is defined as the time elapsed until + the coverage ratio falls below a fixed threshold. $Lifetime_{95}$ and + $Lifetime_{50}$ denote, respectively, the amount of time during which is + guaranteed a level of coverage greater than $95\%$ and $50\%$. The WSN can + fulfill the expected monitoring task until all its nodes have depleted their + energy or if the network is no more connected. This last condition is crucial + because without network connectivity a sensor may not be able to send to a + base station an event it has sensed. +\item {\bf Coverage Ratio (CR)} : it measures how well the WSN is able to + observe the area of interest. In our case, the sensor field is discretized as + a regular grid, which yields the following equation: + \begin{equation*} + \scriptsize + \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100 + \end{equation*} + where $n$ is the number of covered grid points by active sensors of every + subregions during the current sensing phase and $N$ is total number of grid + points in the sensing field. A layout of $N~=~51~\times~26~=~1326$~grid points + is considered in the simulations. +\item {\bf Active Sensors Ratio (ASR)}: a major objective of our protocol is to + activate as few nodes as possible, in order to minimize the communication + overhead and maximize the WSN lifetime. The active sensors ratio is defined as + follows: + \begin{equation*} + \scriptsize + \mbox{ASR}(\%) = \frac{\sum\limits_{r=1}^R \mbox{$|A_r^p|$}}{\mbox{$|J|$}} \times 100 + \end{equation*} + where $|A_r^p|$ is the number of active sensors in the subregion $r$ in the + sensing period~$p$, $R$ is the number of subregions, and $|J|$ is the number + of sensors in the network. +\item {\bf Energy Consumption (EC)}: energy consumption can be seen as the total + energy consumed by the sensors during $Lifetime_{95}$ or $Lifetime_{50}$, + divided by the number of periods. The value of EC is computed according to + this formula: + \begin{equation*} + \scriptsize + \mbox{EC} = \frac{\sum\limits_{p=1}^{P} \left( E^{\mbox{com}}_p+E^{\mbox{list}}_p+E^{\mbox{comp}}_p + + E^{a}_p+E^{s}_p \right)}{P}, + \end{equation*} + where $P$ corresponds to the number of periods. The total energy consumed by + the sensors comes through taking into consideration four main energy + factors. The first one, denoted $E^{\scriptsize \mbox{com}}_p$, represents the + energy consumption spent by all the nodes for wireless communications during + period $p$. $E^{\scriptsize \mbox{list}}_p$, the next factor, corresponds to + the energy consumed by the sensors in LISTENING status before receiving the + decision to go active or sleep in period $p$. $E^{\scriptsize \mbox{comp}}_p$ + refers to the energy needed by all the leader nodes to solve the integer + program during a period (COMPUTATION status). Finally, $E^a_{p}$ and + $E^s_{p}$ indicate the energy consumed by the WSN during the sensing phase + ({\it active} and {\it sleeping} nodes). +\end{itemize} + +\subsection{Simulation Results} + +In order to assess and analyze the performance of our protocol we have +implemented the PeCO protocol in OMNeT++~\citep{varga} simulator. The +simulations were run on a DELL laptop with an Intel Core~i3~2370~M (1.8~GHz) +processor (2 cores) whose MIPS (Million Instructions Per Second) rate is equal +to 35330. To be consistent with the use of a sensor node based on Atmels AVR +ATmega103L microcontroller (6~MHz) having a MIPS rate equal to 6, the original +execution time on the laptop is multiplied by 2944.2 $\left(\frac{35330}{2} +\times \frac{1}{6} \right)$. Energy consumption is calculated according to the +power consumption values, in milliWatt per second, given in Table~\ref{tab:EC}, +based on the energy model proposed in \citep{ChinhVu}. + +\begin{table}[h] +\centering +\caption{Power consumption values} +\label{tab:EC} +\begin{tabular}{|l||cccc|} + \hline + {\bf Sensor status} & MCU & Radio & Sensing & {\it Power (mW)} \\ + \hline + LISTENING & On & On & On & 20.05 \\ + ACTIVE & On & Off & On & 9.72 \\ + SLEEP & Off & Off & Off & 0.02 \\ + COMPUTATION & On & On & On & 26.83 \\ + \hline + \multicolumn{4}{|l}{Energy needed to send or receive a 2-bit content message} & 0.515 \\ + \hline +\end{tabular} +\end{table} + +The modeling language for Mathematical Programming (AMPL)~\citep{AMPL} is used +to generate the integer program instance in a standard format, which is then +read and solved by the optimization solver GLPK (GNU linear Programming Kit +available in the public domain) \citep{glpk} through a Branch-and-Bound method. +In practice, executing GLPK on a sensor node is obviously intractable due to the +huge memory use. Fortunately, to solve the optimization problem we could use +commercial solvers like CPLEX \citep{iamigo:cplex} which are less memory +consuming and more efficient, or implement a lightweight heuristic. For example, +for a WSN of 200 sensor nodes, a leader node has to deal with constraints +induced by about 12 sensor nodes. In that case, to solve the optimization +problem a memory consumption of more than 1~MB can be observed with GLPK, +whereas less than 300~KB would be needed with CPLEX. + +Besides PeCO, three other protocols will be evaluated for comparison +purposes. The first one, called DESK, is a fully distributed coverage algorithm +proposed by \citep{ChinhVu}. The second one, called +GAF~\citep{xu2001geography}, consists in dividing the monitoring area into fixed +squares. Then, during the decision phase, in each square, one sensor is chosen +to remain active during the sensing phase. The last one, the DiLCO +protocol~\citep{Idrees2}, is an improved version of a research work we presented +in~\citep{idrees2014coverage}. Let us notice that the PeCO and DiLCO protocols +are based on the same framework. In particular, the choice for the simulations +of a partitioning in 16~subregions was made because it corresponds to the +configuration producing the best results for DiLCO. Of course, this number of +subregions should be adapted according to the size of the area of interest and +the number of sensors. The protocols are distinguished from one another by the +formulation of the integer program providing the set of sensors which have to be +activated in each sensing phase. The DiLCO protocol tries to satisfy the +coverage of a set of primary points, whereas the objective of the PeCO protocol +is to reach a desired level of coverage for each sensor perimeter. In our +experimentations, we chose a level of coverage equal to one ($l=1$). + +\subsubsection{Coverage Ratio} + +Figure~\ref{figure5} shows the average coverage ratio for 200 deployed nodes +obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better +coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, compared to the +98.76\% produced by PeCO for the first periods. This is due to the fact that at +the beginning the DiLCO and PeCO protocols put more redundant sensors to sleep +status (which slightly decreases the coverage ratio), while the two other +protocols activate more sensor nodes. Later, when the number of periods is +beyond~70, it clearly appears that PeCO provides a better coverage ratio and +keeps a coverage ratio greater than 50\% for longer periods (15 more compared to +DiLCO, 40 more compared to DESK). The energy saved by PeCO in the early periods +allows later a substantial increase of the coverage performance. + +\parskip 0pt +\begin{figure}[h!] +\centering + \includegraphics[scale=0.5] {figure5.eps} +\caption{Coverage ratio for 200 deployed nodes.} +\label{figure5} +\end{figure} + +\subsubsection{Active Sensors Ratio} + +Minimizing the number of active sensor nodes in each period is essential to minimize the +energy consumption and thus to maximize the network lifetime. +Figure~\ref{figure6} shows the average active nodes ratio for 200 deployed +nodes. We observe that DESK and GAF have 30.36~\% and 34.96~\% active nodes for +the first fourteen rounds, and the DiLCO and PeCO protocols compete perfectly with +only 17.92~\% and 20.16~\% active nodes during the same time interval. As the +number of periods increases, the PeCO protocol has a lower number of active nodes in +comparison with the three other approaches and exhibits a slow decrease, while +keeping a greater coverage ratio as shown in Figure \ref{figure5}. + +\begin{figure}[h!] +\centering +\includegraphics[scale=0.5]{figure6.eps} +\caption{Active sensors ratio for 200 deployed nodes.} +\label{figure6} +\end{figure} + +\subsubsection{Energy Consumption} + +The effect of the energy consumed by the WSN during the communication, +computation, listening, active, and sleep status is studied for different +network densities and the four approaches compared. Figures~\ref{figure7}(a) +and (b) illustrate the energy consumption for different network sizes and for +$Lifetime_{95}$ and $Lifetime_{50}$. The results show that the PeCO protocol is the most +competitive from the energy consumption point of view. As shown by both figures, +PeCO consumes much less energy than the other methods. One might think that the +resolution of the integer program is too costly in energy, but the results show +that it is very beneficial to lose a bit of time in the selection of sensors to +activate. Indeed the optimization program allows to reduce significantly the +number of active sensors and also the energy consumption while keeping a good +coverage level. Let us notice that the energy overhead when increasing network +size is the lowest with PeCO. + +\begin{figure}[h!] + \centering + \begin{tabular}{@{}cr@{}} + \includegraphics[scale=0.5]{figure7a.eps} & \raisebox{2.75cm}{(a)} \\ + \includegraphics[scale=0.5]{figure7b.eps} & \raisebox{2.75cm}{(b)} + \end{tabular} + \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.} + \label{figure7} +\end{figure} + +\subsubsection{Network Lifetime} + +We observe the superiority of both the PeCO and DiLCO protocols in comparison with +the two other approaches in prolonging the network lifetime. In +Figures~\ref{figure8}(a) and (b), $Lifetime_{95}$ and $Lifetime_{50}$ are shown for +different network sizes. As can be seen in these figures, the lifetime +increases with the size of the network, and it is clearly larger for the DiLCO and +PeCO protocols. For instance, for a network of 300~sensors and coverage ratio +greater than 50\%, we can see on Figure~\ref{figure8}(b) that the lifetime is +about twice longer with PeCO compared to the DESK protocol. The performance +difference is more obvious in Figure~\ref{figure8}(b) than in +Figure~\ref{figure8}(a) because the gain induced by our protocols increases with +time, and the lifetime with a coverage over 50\% is far longer than with 95\%. + +\begin{figure}[h!] + \centering + \begin{tabular}{@{}cr@{}} + \includegraphics[scale=0.5]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\ + \includegraphics[scale=0.5]{figure8b.eps} & \raisebox{2.75cm}{(b)} + \end{tabular} + \caption{Network Lifetime for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.} + \label{figure8} +\end{figure} + +Figure~\ref{figure9} compares the lifetime coverage of the DiLCO and PeCO protocols +for different coverage ratios. We denote by Protocol/50, Protocol/80, +Protocol/85, Protocol/90, and Protocol/95 the amount of time during which the +network can satisfy an area coverage greater than $50\%$, $80\%$, $85\%$, +$90\%$, and $95\%$ respectively, where the term Protocol refers to DiLCO or +PeCO. Indeed there are applications that do not require a 100\% coverage of the +area to be monitored. PeCO might be an interesting method since it achieves a +good balance between a high level coverage ratio and network lifetime. PeCO +always outperforms DiLCO for the three lower coverage ratios, moreover the +improvements grow with the network size. DiLCO is better for coverage ratios +near 100\%, but in that case PeCO is not ineffective for the smallest network +sizes. + +\begin{figure}[h!] +\centering \includegraphics[scale=0.55]{figure9.eps} +\caption{Network lifetime for different coverage ratios.} +\label{figure9} +\end{figure} + +\subsubsection{Impact of $\alpha$ and $\beta$ on PeCO's performance} +\label{sec:Impact} + +Table~\ref{my-labelx} shows network lifetime results for different values of +$\alpha$ and $\beta$, and a network size equal to 200 sensor nodes. On the one +hand, the choice of $\beta \gg \alpha$ prevents the overcoverage, and also +limits the activation of a large number of sensors, but as $\alpha$ is low, some +areas may be poorly covered. This explains the results obtained for +$Lifetime_{50}$ with $\beta \gg \alpha$: a large number of periods with low +coverage ratio. On the other hand, when we choose $\alpha \gg \beta$, we favor +the coverage even if some areas may be overcovered, so a high coverage ratio is +reached, but a large number of sensors are activated to achieve this goal. +Therefore the network lifetime is reduced. The choice $\alpha=0.6$ and +$\beta=0.4$ seems to achieve the best compromise between lifetime and coverage +ratio. That explains why we have chosen this setting for the experiments +presented in the previous subsections. + +%As can be seen in Table~\ref{my-labelx}, it is obvious and clear that when $\alpha$ decreased and $\beta$ increased by any step, the network lifetime for $Lifetime_{50}$ increased and the $Lifetime_{95}$ decreased. Therefore, selecting the values of $\alpha$ and $\beta$ depend on the application type used in the sensor nework. In PeCO protocol, $\alpha$ and $\beta$ are chosen based on the largest value of network lifetime for $Lifetime_{95}$. + +\begin{table}[h] +\centering +\caption{The impact of $\alpha$ and $\beta$ on PeCO's performance} +\label{my-labelx} +\begin{tabular}{|c|c|c|c|} +\hline +$\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline +0.0 & 1.0 & 151 & 0 \\ \hline +0.1 & 0.9 & 145 & 0 \\ \hline +0.2 & 0.8 & 140 & 0 \\ \hline +0.3 & 0.7 & 134 & 0 \\ \hline +0.4 & 0.6 & 125 & 0 \\ \hline +0.5 & 0.5 & 118 & 30 \\ \hline +{\bf 0.6} & {\bf 0.4} & {\bf 94} & {\bf 57} \\ \hline +0.7 & 0.3 & 97 & 49 \\ \hline +0.8 & 0.2 & 90 & 52 \\ \hline +0.9 & 0.1 & 77 & 50 \\ \hline +1.0 & 0.0 & 60 & 44 \\ \hline +\end{tabular} +\end{table} + + +\section{Conclusion and Future Works} +\label{sec:Conclusion and Future Works} + +In this paper we have studied the problem of perimeter coverage optimization in +WSNs. We have designed a new protocol, called Perimeter-based Coverage +Optimization, which schedules nodes' activities (wake up and sleep stages) with +the objective of maintaining a good coverage ratio while maximizing the network +lifetime. This protocol is applied in a distributed way in regular subregions +obtained after partitioning the area of interest in a preliminary step. It works +in periods and is based on the resolution of an integer program to select the +subset of sensors operating in active status for each period. Our work is +original in so far as it proposes for the first time an integer program +scheduling the activation of sensors based on their perimeter coverage level, +instead of using a set of targets/points to be covered. Several simulations have +been carried out to evaluate the proposed protocol. The simulation results show +that PeCO is more energy-efficient than other approaches, with respect to +lifetime, coverage ratio, active sensors ratio, and energy consumption. + +We plan to extend our framework so that the schedules are planned for multiple +sensing periods. We also want to improve the integer program to take into +account heterogeneous sensors from both energy and node characteristics point of +views. Finally, it would be interesting to implement the PeCO protocol using a +sensor-testbed to evaluate it in real world applications. + +\subsection*{Acknowledgments} +The authors are deeply grateful to the anonymous reviewers for their +constructive advice, which improved the technical quality of the paper. As a +Ph.D. student, Ali Kadhum Idrees would like to gratefully acknowledge the +University of Babylon - Iraq for financial support and Campus France for the +received support. This work is also partially funded by the Labex ACTION program +(contract ANR-11-LABX-01-01). + +\bibliographystyle{gENO} +\bibliography{biblio} %articleeo + +\end{document}