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