-% 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. In\r
-this paper, 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 have been performed using\r
-OMNeT++, the discrete event simulator, to 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}
+\usepackage{color}
+\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.
+\textcolor{green}{Both INFO packet and ActiveSleep packet contain two parts: header and data payload. The sensor ID is included in the header, where the header size is 8 bits. The data part includes position coordinates (64 bits), remaining energy (32 bits), and the number of one-hop live neighbors (8 bits). Therefore the size of the INFO packet is 112 bits. The ActiveSleep packet is 16 bits size, 8 bits for the header and 8 bits for data part that includes only sensor status (0 or 1).}
+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 \textcolor{green}{Energy Saving Ratio (ESR)}}:
+\textcolor{green}{this metric, which shows the ability of a protocol to save energy, is defined by:
+\begin{equation*}
+\scriptsize
+\mbox{ESR}(\%) = \frac{\mbox{Number of alive sensors during this round}}
+{\mbox{Total number of sensors in the network}} \times 100.
+\end{equation*}
+ }
+\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{\textcolor{green}{Energy Saving Ratio}}
+
+
+\textcolor{green}{The simulation results show that our protocol PeCO saves
+ efficiently energy by turning off some sensors during the sensing phase. As
+ shown in Figure~\ref{fig5}, GAF provides better energy saving than PeCO for
+ the first fifty rounds. Indeed GAF balances the energy consumption among
+ sensor nodes inside each small fixed grid and thus permits to extend the life
+ of sensors in each grid fairly. However, at the same time it turns on a large
+ number of sensors and that leads later to quickly deplete sensor's batteries.
+ DESK algorithm shows less energy saving compared with other approaches. In
+ comparison with PeCO, DiLCO protocol usually provides lower energy saving
+ ratios. Moreover, it can be noticed that after round fifty, PeCO protocol
+ exhibits the slowest decrease among all the considered protocols.}
+
+\begin{figure}[h!]
+%\centering
+% \begin{multicols}{6}
+\centering
+\includegraphics[scale=0.5]{ESR.eps} %\\~ ~ ~(a)
+\caption{Energy Saving Ratio for 200 deployed nodes}
+\label{fig5}
+\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/70, Protocol/80,
+Protocol/85, Protocol/90, and Protocol/95 the amount of time during which the
+network can satisfy an area coverage greater than $70\%$, $80\%$, $85\%$,
+$90\%$, and $95\%$ respectively, where the term Protocol refers to DiLCO or
+PeCO. \textcolor{green}{Indeed there are applications that do not require a 100\% coverage of the
+area to be monitored. For example, forest
+fire application might require complete coverage
+in summer seasons while only require 80$\%$ of the area to be covered in rainy seasons~\citep{li2011transforming}. As another example, birds habit study requires only 70$\%$-coverage at nighttime when the birds are sleeping while requires 100$\%$-coverage at daytime when the birds are active~\citep{1279193}.
+ PeCO always outperforms DiLCO for the three lower coverage ratios, moreover the
+improvements grow with the network size. DiLCO outperforms PeCO when the coverage ratio is required to be $>90\%$, but PeCO extends the network lifetime significantly when coverage ratio can be relaxed.}
+
+\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}
