--- /dev/null
+% This is IJUC.TEX the demonstration file of\r
+% the LaTeX macro package for International Journal of Unconventional Computation,\r
+% version 0.1 for LaTeX2e\r
+\r
+\documentclass{ijuc}\r
+\usepackage[pdftex]{graphics}\r
+\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}\r
+\r
+\begin{document}\r
+\r
+\title{Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}\r
+\r
+\author{Ali Kadhum Idrees\inst{1}\r
+\and Karine Deschinkel\inst{1}\r
+\and Michel Salomon\inst{1}\email{michel.salomon@univ-fcomte.fr}\r
+\and Rapha\"el Couturier\inst{1}\r
+}\r
+\r
+\institute{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comt\'e, France}\r
+\r
+\def\received{Received 21 October 2014}\r
+\r
+\maketitle\r
+\r
+\begin{abstract}\r
+One of the main research challenges faced in wireless sensor networks is to\r
+preserve continuously and effectively the coverage of an area of interest to be\r
+monitored, while simultaneously preventing as much as possible a network failure\r
+due to battery-depleted nodes. In this paper we propose a protocol which\r
+maintains the coverage and improves the lifetime of a wireless sensor network.\r
+First, we partition the area of interest into subregions using a classical\r
+divide-and-conquer method. Our protocol is then distributed on the sensor nodes\r
+in each subregion in a second step. To fulfill our objective, the proposed\r
+protocol combines two techniques: a leader election in each subregion, followed\r
+by an optimization-based node activity scheduling performed by each elected\r
+leader. This two-step process takes place periodically. The simulations done\r
+using the discrete event simulator OMNeT++ show that our approach is able to\r
+increase the WSN lifetime and provides improved coverage performance.\r
+\end{abstract}\r
+\r
+\keywords{Wireless Sensor Networks, Area Coverage, Network lifetime,\r
+ Optimization, Scheduling.}\r
+\r
+\section{Introduction}\r
+\label{sec:introduction}\r
+\r
+Energy efficiency is a crucial issue in Wireless Sensor Networks (WSNs) since\r
+sensory consumption, in order to maximize the network lifetime, represents the\r
+major difficulty when designing WSNs. As a consequence, one of the scientific\r
+research challenges in WSNs, which has been addressed by a large amount of\r
+literature during the last few years, is the design of energy efficient\r
+approaches for coverage and connectivity~\cite{conti2014mobile}. Coverage\r
+reflects how well a sensor field is monitored. On the one hand we want to\r
+monitor the area of interest in the most efficient way~\cite{Nayak04}. On the\r
+other hand we want to use as little energy as possible. Sensor nodes are\r
+battery-powered with no means of recharging or replacing, usually due to\r
+environmental (hostile or unpractical environments) or cost reasons. Therefore,\r
+it is desired that the WSNs are deployed with high densities so as to exploit\r
+the overlapping sensing regions of some sensor nodes to save energy by turning\r
+off some of them during the sensing phase to prolong the network lifetime.\r
+\r
+In this paper we design a protocol that focuses on the area coverage problem\r
+with the objective of maximizing the network lifetime. Our proposition, the\r
+Distributed Lifetime Coverage Optimization (DILCO) protocol, maintains the\r
+coverage and improves the lifetime in WSNs. The area of interest is first\r
+divided into subregions using a divide-and-conquer algorithm and an activity\r
+scheduling for sensor nodes is then planned by the elected leader in each\r
+subregion. In fact, the nodes in a subregion can be seen as a cluster where each\r
+node sends sensing data to the cluster head or the sink node. Furthermore, the\r
+activities in a subregion/cluster can continue even if another cluster stops due\r
+to too many node failures. Our DiLCO protocol considers periods, where a period\r
+starts with a discovery phase to exchange information between sensors of the\r
+same subregion, in order to choose in a suitable manner a sensor node (the\r
+leader) to carry out the coverage strategy. In each subregion the activation of\r
+the sensors for the sensing phase of the current period is obtained by solving\r
+an integer program. The resulting activation vector is broadcast by a leader\r
+to every node of its subregion.\r
+\r
+The remainder of the paper continues with Section~\ref{sec:Literature Review}\r
+where a review of some related works is presented. The next section describes\r
+the DiLCO protocol, followed in Section~\ref{cp} by the coverage model\r
+formulation which is used to schedule the activation of\r
+sensors. Section~\ref{sec:Simulation Results and Analysis} shows the simulation\r
+results. The paper ends with a conclusion and some suggestions for further work.\r
+\r
+\section{Literature Review}\r
+\label{sec:Literature Review}\r
+\r
+In this section, we summarize some related works regarding the coverage problem\r
+and distinguish our DiLCO protocol from the works presented in the literature.\r
+\r
+The most discussed coverage problems in literature can be classified into three\r
+types \cite{li2013survey}: area coverage \cite{Misra} where every point inside\r
+an area is to be monitored, target coverage \cite{yang2014novel} where the main\r
+objective is to cover only a finite number of discrete points called targets,\r
+and barrier coverage \cite{Kumar:2005}\cite{kim2013maximum} to prevent intruders\r
+from entering into the region of interest. In \cite{Deng2012} authors transform\r
+the area coverage problem to the target coverage problem taking into account the\r
+intersection points among disks of sensors nodes or between disk of sensor nodes\r
+and boundaries. {\it In DiLCO protocol, the area coverage, i.e. the coverage of\r
+ every point in the sensing region, is transformed to the coverage of a\r
+ fraction of points called primary points. }\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), 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
+\cite{ling2009energy}. Active node selection is determined based on the problem\r
+requirements (e.g. area monitoring, connectivity, power efficiency). For\r
+instance, Jaggi et al. \cite{jaggi2006} address the problem of maximizing\r
+network 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. Vu\r
+\cite{chin2007}, Padmatvathy et al. \cite{pc10}, propose algorithms working in a\r
+periodic fashion where a cover set is computed at the beginning of each period.\r
+{\it Motivated by these works, DiLCO protocol works in periods, where each\r
+ period contains a preliminary phase for information exchange and decisions,\r
+ followed by a sensing phase where one cover set is in charge of the sensing\r
+ task.}\r
+\r
+Various approaches, including centralized, or distributed algorithms, have been\r
+proposed to extend the network lifetime. In distributed\r
+algorithms~\cite{yangnovel,ChinhVu,qu2013distributed}, information is\r
+disseminated throughout the network and sensors decide cooperatively by\r
+communicating with their neighbors which of them will remain in sleep mode for a\r
+certain period of time. The centralized\r
+algorithms~\cite{cardei2005improving,zorbas2010solving,pujari2011high} always\r
+provide nearly or close to optimal solution since the algorithm has global view\r
+of the whole network. But such a method has the disadvantage of requiring high\r
+communication costs, since the node (located at the base station) making the\r
+decision needs information from all the sensor nodes in the area and the amount\r
+of information can be huge. {\it In order to be suitable for large-scale\r
+ network, in the DiLCO protocol, the area coverage is divided into several\r
+ smaller subregions, and in each one, a node called the leader is in charge for\r
+ selecting the active sensors for the current period.}\r
+\r
+A large variety of coverage scheduling algorithms has been developed. Many of\r
+the existing algorithms, dealing with the maximization of the number of cover\r
+sets, are heuristics. These heuristics involve the construction of a cover set\r
+by including in priority the sensor nodes which cover critical targets, that is\r
+to say targets that are covered by the smallest number of sensors\r
+\cite{berman04,zorbas2010solving}. Other approaches are based on mathematical\r
+programming formulations~\cite{cardei2005energy,5714480,pujari2011high,Yang2014}\r
+and dedicated techniques (solving with a branch-and-bound algorithms available\r
+in 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~\cite{castano2013column,rossi2012exact,deschinkel2012column}. {\it In DiLCO\r
+ protocol, each leader, in each subregion, solves an integer program with a\r
+ double objective consisting in minimizing the overcoverage and limiting the\r
+ undercoverage. This program is inspired from the work of \cite{pedraza2006}\r
+ where the objective is to maximize the number of cover sets.}\r
+\r
+\section{Description of the DiLCO protocol}\r
+\label{sec:The DiLCO Protocol Description}\r
+\r
+In this section, we introduce the DiLCO protocol which is distributed on each\r
+subregion in the area of interest. It is based on two efficient techniques:\r
+network leader election and sensor activity scheduling for coverage preservation\r
+and energy conservation, applied periodically to efficiently maximize the\r
+lifetime in the network.\r
+\r
+\subsection{Assumptions and models}\r
+\r
+We consider a sensor network composed of static nodes distributed independently\r
+and uniformly at random. A high density deployment ensures a high coverage\r
+ratio of the interested area at the start. The nodes are supposed to have\r
+homogeneous characteristics from a communication and a processing point of view,\r
+whereas they have heterogeneous energy provisions. Each node has access to its\r
+location thanks, either to a hardware component (like a GPS unit), or a location\r
+discovery algorithm.\r
+\r
+We consider a boolean disk coverage model which is the most widely used sensor\r
+coverage model in the literature. Thus, since a sensor has a constant sensing\r
+range $R_s$, every space points within a disk centered at a sensor with the\r
+radius of the sensing range is said to be covered by this sensor. We also assume\r
+that the communication range $R_c \geq 2R_s$. In fact, Zhang and\r
+Hou~\cite{Zhang05} proved that if the transmission range fulfills the previous\r
+hypothesis, a complete coverage of a convex area implies connectivity among the\r
+working nodes in the active mode.\r
+\r
+For each sensor we also define a set of points called primary\r
+points~\cite{idrees2014coverage} to approximate the area coverage it provides,\r
+rather than working with a continuous coverage. Thus, a sensing disk\r
+corresponding to a sensor node is covered by its neighboring nodes if all its\r
+primary points are covered. Obviously, the approximation of coverage is more or\r
+less accurate according to the number of primary points.\r
+\r
+\subsection{Main idea}\r
+\label{main_idea}\r
+\r
+We start by applying a divide-and-conquer algorithm to partition the area of\r
+interest into smaller areas called subregions and then our protocol is executed\r
+simultaneously in each subregion.\r
+\r
+\begin{figure}[ht!]\r
+\begin{center}\r
+\scalebox{0.5}{\includegraphics{FirstModel.pdf}}\r
+\end{center}\r
+\caption{DiLCO protocol.}\r
+\label{fig2}\r
+\end{figure}\r
+\r
+As shown in Figure~\ref{fig2}, the proposed DiLCO protocol is a periodic\r
+protocol where each period is decomposed into 4~phases: Information Exchange,\r
+Leader Election, Decision, and Sensing. For each period there will be exactly\r
+one cover set in charge of the sensing task. A periodic scheduling is\r
+interesting because it enhances the robustness of the network against node\r
+failures. First, a node that has not enough energy to complete a period, or\r
+which fails before the decision is taken, will be excluded from the scheduling\r
+process. Second, if a node fails later, whereas it was supposed to sense the\r
+region of interest, it will only affect the quality of the coverage until the\r
+definition of a new cover set in the next period. Constraints, like energy\r
+consumption, can be easily taken into consideration since the sensors can update\r
+and exchange their information during the first phase. Let us notice that the\r
+phases before the sensing one (Information Exchange, Leader Election, and\r
+Decision) are energy consuming for all the nodes, even nodes that will not be\r
+retained by the leader to keep watch over the corresponding area.\r
+\r
+During the execution of the DiLCO protocol, two kinds of packet will be used:\r
+%\begin{enumerate}[(a)]\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 inform them to stay Active or to go Sleep during the sensing phase.\r
+\end{itemize}\r
+%\end{enumerate}\r
+and each sensor node will have five possible status in the network:\r
+%\begin{enumerate}[(a)] \r
+\begin{itemize} \r
+\item LISTENING: sensor is waiting for a decision (to be active or not);\r
+\item COMPUTATION: sensor applies the optimization process as leader;\r
+\item ACTIVE: sensor is active;\r
+\item SLEEP: sensor is turned off;\r
+\item COMMUNICATION: sensor is transmitting or receiving packet.\r
+\end{itemize}\r
+%\end{enumerate}\r
+\r
+An outline of the protocol implementation is given by Algorithm~\ref{alg:DiLCO}\r
+which describes the execution of a period by a node (denoted by $s_j$ for a\r
+sensor node indexed by $j$). At the beginning a node checks whether it has\r
+enough energy to stay active during the next sensing phase. If yes, it exchanges\r
+information with all the other nodes belonging to the same subregion: it\r
+collects from each node its position coordinates, remaining energy ($RE_j$), ID,\r
+and the number of one-hop neighbors still alive. Once the first phase is\r
+completed, the nodes of a subregion choose a leader to take the decision based\r
+on the following criteria with decreasing importance: larger number of\r
+neighbors, larger remaining energy, and then in case of equality, larger index.\r
+After that, if the sensor node is leader, it will execute the integer program\r
+algorithm (see Section~\ref{cp}) which provides a set of sensors planned to be\r
+active in the next sensing phase. As leader, it will send an Active-Sleep packet\r
+to each sensor in the same subregion to indicate it if it has to be active or\r
+not. Alternately, if the sensor is not the leader, it will wait for the\r
+Active-Sleep packet to know its state for the coming sensing phase.\r
+\r
+\r
+\begin{algorithm} \r
+\r
+ \BlankLine\r
+ %\emph{Initialize the sensor node and determine it's position and subregion} \; \r
+ \r
+ \If{ $RE_j \geq E_{th}$ }{\r
+ \emph{$s_j.status$ = COMMUNICATION}\;\r
+ \emph{Send $INFO()$ packet to other nodes in the subregion}\;\r
+ \emph{Wait $INFO()$ packet from other nodes in the subregion}\; \r
+ %\emph{UPDATE $RE_j$ for every sent or received INFO Packet}\;\r
+ %\emph{ Collect information and construct the list L for all nodes in the subregion}\;\r
+ \r
+ %\If{ the received INFO Packet = No. of nodes in it's subregion -1 }{\r
+ \emph{LeaderID = Leader election}\;\r
+ \If{$ s_j.ID = LeaderID $}{\r
+ \emph{$s_j.status$ = COMPUTATION}\;\r
+ \emph{$\left\{\left(X_{1},\dots,X_{k},\dots,X_{J}\right)\right\}$ =\r
+ Execute Integer Program Algorithm($J$)}\;\r
+ \emph{$s_j.status$ = COMMUNICATION}\;\r
+ \emph{Send $ActiveSleep()$ to each node $k$ in subregion} \;\r
+ \emph{Update $RE_j $}\;\r
+ } \r
+ \Else{\r
+ \emph{$s_j.status$ = LISTENING}\;\r
+ \emph{Wait $ActiveSleep()$ packet from the Leader}\;\r
+\r
+ \emph{Update $RE_j $}\;\r
+ } \r
+ % }\r
+ }\r
+ \Else { Exclude $s_j$ from entering in the current sensing phase}\r
+ % \emph{return X} \;\r
+\caption{DiLCO($s_j$)}\r
+\label{alg:DiLCO}\r
+\end{algorithm}\r
+\r
+\section{Coverage problem formulation}\r
+\label{cp}\r
+\r
+Our model is based on the model proposed by \cite{pedraza2006} where the\r
+objective is to find a maximum number of disjoint cover sets. To accomplish\r
+this goal, the authors proposed an integer program which forces undercoverage\r
+and overcoverage of targets to become minimal at the same time. They use binary\r
+variables $x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our\r
+model, we consider that the binary variable $X_{j}$ determines the activation of\r
+sensor $j$ in the sensing phase. We also consider primary points as targets.\r
+The set of primary points is denoted by $P$ and the set of sensors by $J$.\r
+\r
+Let $\alpha_{jp}$ denote the indicator function of whether the primary point $p$\r
+is covered, that is:\r
+\begin{equation}\r
+\alpha_{jp} = \left \{ \r
+\begin{array}{l l}\r
+ 1 & \mbox{if the primary point $p$ is covered} \\\r
+ & \mbox{by sensor node $j$}, \\\r
+ 0 & \mbox{otherwise.}\\\r
+\end{array} \right.\r
+%\label{eq12} \r
+\end{equation}\r
+The number of active sensors that cover the primary point $p$ can then be\r
+computed by $\sum_{j \in J} \alpha_{jp} * X_{j}$ where:\r
+\begin{equation}\r
+X_{j} = \left \{ \r
+\begin{array}{l l}\r
+ 1& \mbox{if sensor $j$ is active,} \\\r
+ 0 & \mbox{otherwise.}\\\r
+\end{array} \right.\r
+%\label{eq11} \r
+\end{equation}\r
+We define the Overcoverage variable $\Theta_{p}$ as:\r
+\begin{equation}\r
+ \Theta_{p} = \left \{ \r
+\begin{array}{l l}\r
+ 0 & \mbox{if the primary point}\\\r
+ & \mbox{$p$ is not covered,}\\\r
+ \left( \sum_{j \in J} \alpha_{jp} * X_{j} \right)- 1 & \mbox{otherwise.}\\\r
+\end{array} \right.\r
+\label{eq13} \r
+\end{equation}\r
+\noindent More precisely, $\Theta_{p}$ represents the number of active sensor\r
+nodes minus one that cover the primary point~$p$. The Undercoverage variable\r
+$U_{p}$ of the primary point $p$ is defined by:\r
+\begin{equation}\r
+U_{p} = \left \{ \r
+\begin{array}{l l}\r
+ 1 &\mbox{if the primary point $p$ is not covered,} \\\r
+ 0 & \mbox{otherwise.}\\\r
+\end{array} \right.\r
+\label{eq14} \r
+\end{equation}\r
+\r
+\noindent Our coverage optimization problem can then be formulated as follows:\r
+\begin{equation} \label{eq:ip2r}\r
+\left \{\r
+\begin{array}{ll}\r
+\min \sum_{p \in P} (w_{\theta} \Theta_{p} + w_{U} U_{p})&\\\r
+\textrm{subject to :}&\\\r
+\sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, &\forall p \in P\\\r
+%\label{c1} \r
+%\sum_{t \in T} X_{j,t} \leq \frac{RE_j}{e_t} &\forall j \in J \\\r
+%\label{c2}\r
+\Theta_{p}\in N, &\forall p \in P\\\r
+U_{p} \in \{0,1\}, &\forall p \in P\\\r
+X_{j} \in \{0,1\}, &\forall j \in J\r
+\end{array}\r
+\right.\r
+\end{equation}\r
+\r
+\begin{itemize}\r
+\item $X_{j}$ : indicates whether or not the sensor $j$ is actively sensing (1\r
+ if yes and 0 if not);\r
+\item $\Theta_{p}$ : {\it overcoverage}, the number of sensors minus one that\r
+ are covering the primary point $p$;\r
+\item $U_{p}$ : {\it undercoverage}, indicates whether or not the primary point\r
+ $p$ is being covered (1 if not covered and 0 if covered).\r
+\end{itemize}\r
+\r
+The first group of constraints indicates that some primary point $p$ should be\r
+covered by at least one sensor and, if it is not always the case, overcoverage\r
+and undercoverage variables help balancing the restriction equations by taking\r
+positive values. Two objectives can be noticed in our model. First, we limit the\r
+overcoverage of primary points to activate as few sensors as possible. Second,\r
+to avoid a lack of area monitoring in a subregion we minimize the\r
+undercoverage. Both weights $w_\theta$ and $w_U$ must be carefully chosen to\r
+guarantee that the maximum number of points are covered during each period.\r
+\r
+\section{Protocol evaluation}\r
+\label{sec:Simulation Results and Analysis}\r
+\r
+\subsection{Simulation framework}\r
+\r
+To assess the performance of our DiLCO protocol, we have used the discrete event\r
+simulator OMNeT++ \cite{varga} to run different series of simulations.\r
+Table~\ref{table3} gives the chosen parameters setting.\r
+\r
+\begin{table}\r
+\caption{Relevant parameters for network initializing.}\r
+% title of Table\r
+\centering\r
+% used for centering table\r
+\begin{tabular}{c|c}\r
+% centered columns (4 columns)\r
+\hline\r
+%inserts double horizontal lines\r
+Parameter & Value \\ [0.5ex]\r
+%Case & Strategy (with Two Leaders) & Strategy (with One Leader) & Simple Heuristic \\ [0.5ex]\r
+% inserts table\r
+%heading\r
+\hline\r
+% inserts single horizontal line\r
+Sensing Field & $(50 \times 25)~m^2 $ \\\r
+% inserting body of the table\r
+%\hline\r
+Nodes Number & 50, 100, 150, 200 and 250~nodes \\\r
+%\hline\r
+Initial Energy & 500-700~joules \\ \r
+%\hline\r
+Sensing Period & 60 Minutes \\\r
+$E_{th}$ & 36 Joules\\\r
+$R_s$ & 5~m \\ \r
+%\hline\r
+$w_{\Theta}$ & 1 \\\r
+% [1ex] adds vertical space\r
+%\hline\r
+$w_{U}$ & $|P|^2$\r
+%inserts single line\r
+\end{tabular}\r
+\label{table3}\r
+% is used to refer this table in the text\r
+\end{table}\r
+\r
+Simulations with five different node densities going from 50 to 250~nodes were\r
+performed considering each time 25~randomly generated networks, to obtain\r
+experimental results which are relevant. 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.\r
+\r
+We chose as energy consumption model the one proposed proposed \linebreak\r
+by~\cite{ChinhVu} and based on ~\cite{raghunathan2002energy} with slight\r
+modifications. The energy consumed by the communications is added and the part\r
+relative to a variable sensing range is removed. We also assume that the nodes\r
+have the characteristics of the Medusa II sensor node platform\r
+\cite{raghunathan2002energy}. A sensor node typically consists of four units: a\r
+MicroController Unit, an Atmels AVR ATmega103L in case of Medusa II, to perform\r
+the computations; a communication (radio) unit able to send and receive\r
+messages; a sensing unit to collect data; a power supply which provides the\r
+energy consumed by node. Except the battery, all the other unit can be switched\r
+off to save energy according to the node status. Table~\ref{table4} summarizes\r
+the energy consumed (in milliWatt per second) by a node for each of its possible\r
+status.\r
+\r
+\begin{table}\r
+\caption{Energy consumption model.}\r
+% title of Table\r
+\centering\r
+% used for centering table\r
+{\scriptsize\r
+\begin{tabular}{|c|c|c|c|c|}\r
+% centered columns (4 columns)\r
+\hline\r
+%inserts double horizontal lines\r
+Sensor status & MCU & Radio & Sensing & Power (mW) \\ [0.5ex]\r
+\hline\r
+% inserts single horizontal line\r
+Listening & ON & ON & ON & 20.05 \\\r
+% inserting body of the table\r
+\hline\r
+Active & ON & OFF & ON & 9.72 \\\r
+\hline\r
+Sleep & OFF & OFF & OFF & 0.02 \\\r
+\hline\r
+Computation & ON & ON & ON & 26.83 \\\r
+%\hline\r
+%\multicolumn{4}{|c|}{Energy needed to send/receive a 1-bit} & 0.2575\\\r
+ \hline\r
+\end{tabular}\r
+}\r
+\label{table4}\r
+\end{table}\r
+\r
+Less influent energy consumption sources like when turning on the radio,\r
+starting the sensor node, changing the status of a node, etc., will be neglected\r
+for the sake of simplicity. Each node saves energy by switching off its radio\r
+once it has received its decision status from the corresponding leader (it can\r
+be itself). As explained previously in subsection~\ref{main_idea}, two kinds of\r
+packets for communication are considered in our protocol: INFO packet and\r
+ActiveSleep packet. To compute the energy needed by a node to transmit or\r
+receive such packets, we use the equation giving the energy spent to send a\r
+1-bit-content message defined in~\cite{raghunathan2002energy} (we assume\r
+symmetric communication costs), and we set their respective size to 112 and\r
+24~bits. The energy required to send or receive a 1-bit-content message is thus\r
+ equal to 0.2575~mW.\r
+\r
+Each node has an initial energy level, in Joules, which is randomly drawn in\r
+$[500-700]$. If its energy provision reaches a value below the threshold\r
+$E_{th}=36$~Joules, the minimum energy needed for a node to stay active during\r
+one period, it will no longer take part in the coverage task. This value\r
+corresponds to the energy needed by the sensing phase, obtained by multiplying\r
+the energy consumed in active state (9.72 mW) by the time in seconds for one\r
+period (3,600 seconds), and adding the energy for the pre-sensing phases.\r
+According to the interval of initial energy, a sensor may be active during at\r
+most 20 periods.\r
+\r
+In the simulations, we introduce the following performance metrics to evaluate\r
+the efficiency of our approach:\r
+\r
+\begin{itemize}\r
+\item {{\bf Network Lifetime}:} we define the network lifetime as the time until\r
+ the coverage ratio drops below a predefined threshold. We denote by\r
+ $Lifetime_{95}$ (respectively $Lifetime_{50}$) the amount of time during which\r
+ the network can satisfy an area coverage greater than $95\%$ (respectively\r
+ $50\%$). We assume that the sensor network can fulfill its task until all its\r
+ nodes have been drained of their energy or it becomes disconnected. Network\r
+ connectivity is crucial because an active sensor node without connectivity\r
+ towards a base station cannot transmit any information regarding an observed\r
+ event in the area that it monitors.\r
+ \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\r
+ as a regular grid, which yields the following equation to compute the\r
+ coverage ratio: \r
+ $$\r
+ \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100,\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 the total number of grid\r
+ points in the sensing field. In our simulations, we have a layout of $N = 51\r
+ \times 26 = 1326$ grid points.\r
+\r
+\item {{\bf Energy Consumption}:} energy consumption (EC) can be seen as the\r
+ total amount of energy consumed by the sensors during $Lifetime_{95}$ \r
+ or $Lifetime_{50}$, divided by the number of periods. Formally, the computation\r
+ of EC can be expressed as follows:\r
+ $$\r
+ \mbox{EC} = \frac{\sum\limits_{m=1}^{M} \left( E^{com}_m+E^{list}_m+E^{comp}_m \r
+ + E^{a}_m+E^{s}_m \right)}{M},\r
+ $$\r
+where $M$ corresponds to the number of periods. The total amount of energy\r
+consumed by the sensors (EC) comes through taking into consideration four main\r
+energy factors. The first one, denoted $E^{com}_m$, represents the energy\r
+consumption spent by all the nodes for wireless communications during period\r
+$m$. $E^{list}_m$, the next factor, corresponds to the energy consumed by the\r
+sensors in LISTENING status before receiving the decision to go active or sleep\r
+in period $m$. $E^{comp}_m$ refers to the energy needed by all the leader nodes\r
+to solve the integer program during a period. Finally, $E^a_{m}$ and $E^s_{m}$\r
+indicate the energy consumed by the whole network in the sensing phase (active\r
+and sleeping nodes).\r
+\end{itemize}\r
+\r
+\subsection{Performance analysis}\r
+\label{sub1}\r
+\r
+In this subsection, we first focus on the performance of our DiLCO protocol for\r
+different numbers of subregions. We consider partitions of the WSN area into\r
+$2$, $4$, $8$, $16$, and $32$ subregions. Thus the DiLCO protocol is declined in\r
+five versions: DiLCO-2, DiLCO-4, DiLCO-8, DiLCO-16, and DiLCO-32. Simulations\r
+without partitioning the area of interest, cases which correspond to a\r
+centralized approach, are not presented because they require high execution\r
+times to solve the integer program and thus consume too much energy.\r
+\r
+We compare our protocol to two other approaches. The first one, called DESK and\r
+proposed by~\cite{ChinhVu}, is a fully distributed coverage algorithm. The\r
+second one, called GAF~\cite{xu2001geography}, consists in dividing the region\r
+into fixed squares. During the decision phase, in each square, one sensor is\r
+chosen to remain active during the sensing phase.\r
+\r
+\subsubsection{Coverage ratio} \r
+\r
+Figure~\ref{fig3} shows the average coverage ratio for 150 deployed nodes. It\r
+can be seen that both DESK and GAF provide a coverage ratio which is slightly\r
+better compared to DiLCO in the first thirty periods. This can be easily\r
+explained by the number of active nodes: the optimization process of our\r
+protocol activates less nodes than DESK or GAF, resulting in a slight decrease\r
+of the coverage ratio. In case of DiLCO-2 (respectively DiLCO-4), the coverage\r
+ratio exhibits a fast decrease with the number of periods and reaches zero value\r
+in period~18 (respectively 46), whereas the other versions of DiLCO, DESK, and\r
+GAF ensure a coverage ratio above 50\% for subsequent periods. We believe that\r
+the results obtained with these two methods can be explained by a high\r
+consumption of energy and we will check this assumption in the next subsection.\r
+\r
+Concerning DiLCO-8, DiLCO-16, and DiLCO-32, these methods seem to be more\r
+efficient than DESK and GAF, since they can provide the same level of coverage\r
+(except in the first periods where DESK and GAF slightly outperform them) for a\r
+greater number of periods. In fact, when our protocol is applied with a large\r
+number of subregions (from 8 to 32~regions), it activates a restricted number of\r
+nodes, and thus enables the extension of the lifetime.\r
+ \r
+\begin{figure}\r
+\begin{center}\r
+\scalebox{0.5}{\includegraphics{R/CR.pdf}}\r
+\end{center}\r
+\caption{Coverage ratio}\r
+\label{fig3}\r
+\end{figure} \r
+\r
+\subsubsection{Energy consumption}\r
+\r
+Based on the results shown in Figure~\ref{fig3}, we focus on the DiLCO-16 and\r
+DiLCO-32 versions of our protocol, and we compare their energy consumption with\r
+the DESK and GAF approaches. For each sensor node we measure the energy consumed\r
+according to its successive status, for different network densities. We denote\r
+by $\mbox{\it Protocol}/50$ (respectively $\mbox{\it Protocol}/95$) the amount\r
+of energy consumed while the area coverage is greater than $50\%$ (repectively\r
+$95\%$), where {\it Protocol} is one of the four protocols we compare.\r
+Figure~\ref{fig95} presents the energy consumptions per period observed for\r
+network sizes going from 50 to 250~nodes. Let us notice that the same network\r
+sizes will be used for the different performance metrics.\r
+\r
+\begin{figure}\r
+\begin{center}\r
+\scalebox{0.5}{\includegraphics{R/EC.pdf}}\r
+\end{center}\r
+\caption{Energy consumption per period.}\r
+\label{fig95}\r
+\end{figure} \r
+\r
+The results depict the good performance of the different versions of our\r
+protocol. Indeed, the protocols DiLCO-16/50, DiLCO-32/50, DiLCO-16/95, and\r
+DiLCO-32/95 consume less energy than their DESK and GAF counterparts for a\r
+similar level of area coverage. This observation reflects the larger number of\r
+nodes set active by DESK and GAF. \r
+\r
+% New paragraph - Michel\r
+Now, if we consider a same protocol, we can notice that the average consumption\r
+per period increases slightly for our protocol when increasing the level of\r
+coverage and the number of nodes, whereas it increases more largely for DESK and\r
+GAF. That means even if a larger network allows to improve the number of periods\r
+with a minimum coverage level value, this improvement has a higher energy cost\r
+per period due to communication overhead and a more difficult optimization\r
+problem. However, in comparison with DESK and GAF, our approach has a\r
+reasonable energy overcost.\r
+\r
+\subsubsection{Execution time}\r
+\r
+Another interesting point to investigate is the evolution of the execution time\r
+with the size of the WSN and the number of subregions. Therefore, we report for\r
+every version of our protocol the average execution times in seconds needed to\r
+solve the optimization problem for different WSN sizes. The execution times are\r
+obtained on a laptop DELL which has an Intel Core~i3~2370~M (2.4~GHz) dual core\r
+processor and a MIPS rating equal to 35330. The corresponding execution times on\r
+a MEDUSA II sensor node are then extrapolated according to the MIPS rate of the\r
+Atmels AVR ATmega103L microcontroller (6~MHz), which is equal to 6, by\r
+multiplying the laptop times by $\left(\frac{35330}{2} \times\r
+\frac{1}{6}\right)$.\r
+% The expected times on a sensor node are reported on Figure~\ref{fig8}.\r
+\r
+\begin{figure}\r
+\begin{center}\r
+\scalebox{0.5}{\includegraphics{R/T.pdf}}\r
+\end{center}\r
+\caption{Execution time in seconds.}\r
+\label{fig8}\r
+\end{figure} \r
+\r
+Figure~\ref{fig8} shows that DiLCO-32 has very low execution times in comparison\r
+with other DiLCO versions, because the activity scheduling is tackled by a\r
+larger number of leaders and each leader solves an integer problem with a\r
+limited number of variables and constraints. Conversely, DiLCO-2 requires to\r
+solve an optimization problem with half of the network nodes and thus presents a\r
+high execution time. Nevertheless if we refer to Figure~\ref{fig3}, we observe\r
+that DiLCO-32 is slightly less efficient than DilCO-16 to maintain as long as\r
+possible high coverage. In fact an excessive subdivision of the area of interest\r
+prevents it to ensure a good coverage especially on the borders of the\r
+subregions. Thus, the optimal number of subregions can be seen as a trade-off\r
+between execution time and coverage performance.\r
+\r
+\subsubsection{Network lifetime}\r
+\r
+In the next figure, the network lifetime is illustrated. Obviously, the lifetime\r
+increases with the network size, whatever the considered protocol, since the\r
+correlated node density also increases. A high network density means a high\r
+node redundancy which allows to turn-off many nodes and thus to prolong the\r
+network lifetime.\r
+\r
+\begin{figure}\r
+\begin{center}\r
+\scalebox{0.5}{\includegraphics{R/LT.pdf}}\r
+\end{center}\r
+\caption{Network lifetime.}\r
+\label{figLT95}\r
+\end{figure} \r
+\r
+\newpage\r
+\r
+As highlighted by Figure~\ref{figLT95}, when the coverage level is relaxed\r
+($50\%$) the network lifetime also improves. This observation reflects the fact\r
+that the higher the coverage performance, the more nodes must be active to\r
+ensure the wider monitoring. For a similar level of coverage, DiLCO outperforms\r
+DESK and GAF for the lifetime of the network. More specifically, if we focus on\r
+the larger level of coverage ($95\%$) in the case of our protocol, the\r
+subdivision in $16$~subregions seems to be the most appropriate.\r
+\r
+\section{Conclusion and future work}\r
+\label{sec:Conclusion and Future Works} \r
+\r
+A crucial problem in WSN is to schedule the sensing activities of the different\r
+nodes in order to ensure both coverage of the area of interest and longer\r
+network lifetime. The inherent limitations of sensor nodes, in energy provision,\r
+communication and computing capacities, require protocols that optimize the use\r
+of the available resources to fulfill the sensing task. To address this\r
+problem, this paper proposes a two-step approach. Firstly, the field of sensing\r
+is divided into smaller subregions using the concept of divide-and-conquer\r
+method. Secondly, a distributed protocol called Distributed Lifetime Coverage\r
+Optimization is applied in each subregion to optimize the coverage and lifetime\r
+performances. In a subregion, our protocol consists in electing a leader node\r
+which will then perform a sensor activity scheduling. The challenges include how\r
+to select the most efficient leader in each subregion and the best\r
+representative set of active nodes to ensure a high level of coverage. To assess\r
+the performance of our approach, we compared it with two other approaches using\r
+many performance metrics like coverage ratio or network lifetime. We have also\r
+studied the impact of the number of subregions chosen to subdivide the area of\r
+interest, considering different network sizes. The experiments show that\r
+increasing the number of subregions improves the lifetime. The more subregions\r
+there are, the more robust the network is against random disconnection resulting\r
+from dead nodes. However, for a given sensing field and network size there is\r
+an optimal number of subregions. Therefore, in case of our simulation context a\r
+subdivision in $16$~subregions seems to be the most relevant. The optimal number\r
+of subregions will be investigated in the future.\r
+\r
+\section{Acknowledgments}\r
+\r
+As a Ph.D. student, Ali Kadhum IDREES would like to gratefully acknowledge the\r
+University of Babylon - IRAQ for the financial support and Campus France for the\r
+received support. This paper is also partially funded by the Labex ACTION\r
+program (contract ANR-11-LABX-01-01).\r
+\r
+\bibliography{Example}\r
+\r
+\end{document}\r
--- /dev/null
+% BibTeX standard bibliography style `plain'\r
+ % version 0.99a for BibTeX versions 0.99a or later, LaTeX version 2.09.\r
+ % Copyright (C) 1985, all rights reserved.\r
+ % Copying of this file is authorized only if either\r
+ % (1) you make absolutely no changes to your copy, including name, or\r
+ % (2) if you do make changes, you name it something other than\r
+ % btxbst.doc, plain.bst, unsrt.bst, alpha.bst, and abbrv.bst.\r
+ % This restriction helps ensure that all standard styles are identical.\r
+ % The file btxbst.doc has the documentation for this style.\r
+\r
+ENTRY\r
+ { address\r
+ author\r
+ booktitle\r
+ chapter\r
+ edition\r
+ editor\r
+ howpublished\r
+ institution\r
+ journal\r
+ key\r
+ month\r
+ note\r
+ number\r
+ organization\r
+ pages\r
+ publisher\r
+ school\r
+ series\r
+ title\r
+ type\r
+ volume\r
+ year\r
+ }\r
+ {}\r
+ { label }\r
+\r
+INTEGERS { output.state before.all mid.sentence after.sentence after.block }\r
+\r
+FUNCTION {init.state.consts}\r
+{ #0 'before.all :=\r
+ #1 'mid.sentence :=\r
+ #2 'after.sentence :=\r
+ #3 'after.block :=\r
+}\r
+\r
+STRINGS { s t }\r
+\r
+FUNCTION {output.nonnull}\r
+{ 's :=\r
+ output.state mid.sentence =\r
+ { ", " * write$ }\r
+ { output.state after.block =\r
+ { add.period$ write$\r
+ newline$\r
+ "\newblock " write$\r
+ }\r
+ { output.state before.all =\r
+ 'write$\r
+ { add.period$ " " * write$ }\r
+ if$\r
+ }\r
+ if$\r
+ mid.sentence 'output.state :=\r
+ }\r
+ if$\r
+ s\r
+}\r
+\r
+FUNCTION {output}\r
+{ duplicate$ empty$\r
+ 'pop$\r
+ 'output.nonnull\r
+ if$\r
+}\r
+\r
+FUNCTION {output.check}\r
+{ 't :=\r
+ duplicate$ empty$\r
+ { pop$ "empty " t * " in " * cite$ * warning$ }\r
+ 'output.nonnull\r
+ if$\r
+}\r
+\r
+FUNCTION {output.bibitem}\r
+{ newline$\r
+ "\bibitem{" write$\r
+ cite$ write$\r
+ "}" write$\r
+ newline$\r
+ ""\r
+ before.all 'output.state :=\r
+}\r
+\r
+FUNCTION {fin.entry}\r
+{ add.period$\r
+ write$\r
+ newline$\r
+}\r
+\r
+FUNCTION {new.block}\r
+{ output.state before.all =\r
+ 'skip$\r
+ { after.block 'output.state := }\r
+ if$\r
+}\r
+\r
+FUNCTION {new.sentence}\r
+{ output.state after.block =\r
+ 'skip$\r
+ { output.state before.all =\r
+ 'skip$\r
+ { after.sentence 'output.state := }\r
+ if$\r
+ }\r
+ if$\r
+}\r
+\r
+FUNCTION {not}\r
+{ { #0 }\r
+ { #1 }\r
+ if$\r
+}\r
+\r
+FUNCTION {and}\r
+{ 'skip$\r
+ { pop$ #0 }\r
+ if$\r
+}\r
+\r
+FUNCTION {or}\r
+{ { pop$ #1 }\r
+ 'skip$\r
+ if$\r
+}\r
+\r
+FUNCTION {new.block.checka}\r
+{ empty$\r
+ 'skip$\r
+ 'new.block\r
+ if$\r
+}\r
+\r
+FUNCTION {new.block.checkb}\r
+{ empty$\r
+ swap$ empty$\r
+ and\r
+ 'skip$\r
+ 'new.block\r
+ if$\r
+}\r
+\r
+FUNCTION {new.sentence.checka}\r
+{ empty$\r
+ 'skip$\r
+ 'new.sentence\r
+ if$\r
+}\r
+\r
+FUNCTION {new.sentence.checkb}\r
+{ empty$\r
+ swap$ empty$\r
+ and\r
+ 'skip$\r
+ 'new.sentence\r
+ if$\r
+}\r
+\r
+FUNCTION {field.or.null}\r
+{ duplicate$ empty$\r
+ { pop$ "" }\r
+ 'skip$\r
+ if$\r
+}\r
+\r
+FUNCTION {emphasize}\r
+{ duplicate$ empty$\r
+ { pop$ "" }\r
+ { "{\em " swap$ * "}" * }\r
+ if$\r
+}\r
+\r
+FUNCTION {parenthesize}\r
+{ duplicate$ empty$\r
+ { pop$ "" }\r
+ { "(" swap$ * ")" * }\r
+ if$\r
+}\r
+\r
+\r
+INTEGERS { nameptr namesleft numnames }\r
+\r
+FUNCTION {format.names}\r
+{ 's :=\r
+ #1 'nameptr :=\r
+ s num.names$ 'numnames :=\r
+ numnames 'namesleft :=\r
+ { namesleft #0 > }\r
+ { s nameptr "{ff~}{vv~}{ll}{, jj}" format.name$ 't :=\r
+ nameptr #1 >\r
+ { namesleft #1 >\r
+ { ", " * t * }\r
+ { numnames #2 >\r
+ { "," * }\r
+ 'skip$\r
+ if$\r
+ t "others" =\r
+ { " {\it et~al.}" * }\r
+ { " and " * t * }\r
+ if$\r
+ }\r
+ if$\r
+ }\r
+ 't\r
+ if$\r
+ nameptr #1 + 'nameptr :=\r
+ namesleft #1 - 'namesleft :=\r
+ }\r
+ while$\r
+}\r
+\r
+FUNCTION {format.authors}\r
+{ author empty$\r
+ { "" }\r
+ { author format.names }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.editors}\r
+{ editor empty$\r
+ { "" }\r
+ { editor format.names\r
+ editor num.names$ #1 >\r
+ { ", editors" * }\r
+ { ", editor" * }\r
+ if$\r
+ }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.title}\r
+{ title empty$\r
+ { "" }\r
+ { title "t" change.case$ }\r
+ if$\r
+}\r
+\r
+FUNCTION {n.dashify}\r
+{ 't :=\r
+ ""\r
+ { t empty$ not }\r
+ { t #1 #1 substring$ "-" =\r
+ { t #1 #2 substring$ "--" = not\r
+ { "--" *\r
+ t #2 global.max$ substring$ 't :=\r
+ }\r
+ { { t #1 #1 substring$ "-" = }\r
+ { "-" *\r
+ t #2 global.max$ substring$ 't :=\r
+ }\r
+ while$\r
+ }\r
+ if$\r
+ }\r
+ { t #1 #1 substring$ *\r
+ t #2 global.max$ substring$ 't :=\r
+ }\r
+ if$\r
+ }\r
+ while$\r
+}\r
+\r
+\r
+FUNCTION {format.datea}\r
+{ year empty$\r
+ { month empty$\r
+ { "" }\r
+ { "there's a month but no year in " cite$ * warning$\r
+ month\r
+ }\r
+ if$\r
+ }\r
+ { month empty$\r
+ 'year\r
+ { month " " * year * }\r
+ if$\r
+ }\r
+ if$\r
+}\r
+\r
+\r
+FUNCTION {format.date}\r
+{ format.datea parenthesize\r
+}\r
+\r
+FUNCTION {format.btitle}\r
+{ title emphasize\r
+}\r
+\r
+FUNCTION {tie.or.space.connect}\r
+{ duplicate$ text.length$ #3 <\r
+ { "~" }\r
+ { " " }\r
+ if$\r
+ swap$ * *\r
+}\r
+\r
+FUNCTION {either.or.check}\r
+{ empty$\r
+ 'pop$\r
+ { "can't use both " swap$ * " fields in " * cite$ * warning$ }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.bvolume}\r
+{ volume empty$\r
+ { "" }\r
+ { "volume" volume tie.or.space.connect\r
+ series empty$\r
+ 'skip$\r
+ { " of " * series emphasize * }\r
+ if$\r
+ "volume and number" number either.or.check\r
+ }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.number.series}\r
+{ volume empty$\r
+ { number empty$\r
+ { series field.or.null }\r
+ { output.state mid.sentence =\r
+ { "number" }\r
+ { "Number" }\r
+ if$\r
+ number tie.or.space.connect\r
+ series empty$\r
+ { "there's a number but no series in " cite$ * warning$ }\r
+ { " in " * series * }\r
+ if$\r
+ }\r
+ if$\r
+ }\r
+ { "" }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.edition}\r
+{ edition empty$\r
+ { "" }\r
+ { output.state mid.sentence =\r
+ { edition "l" change.case$ " edition" * }\r
+ { edition "t" change.case$ " edition" * }\r
+ if$\r
+ }\r
+ if$\r
+}\r
+\r
+INTEGERS { multiresult }\r
+\r
+FUNCTION {multi.page.check}\r
+{ 't :=\r
+ #0 'multiresult :=\r
+ { multiresult not\r
+ t empty$ not\r
+ and\r
+ }\r
+ { t #1 #1 substring$\r
+ duplicate$ "-" =\r
+ swap$ duplicate$ "," =\r
+ swap$ "+" =\r
+ or or\r
+ { #1 'multiresult := }\r
+ { t #2 global.max$ substring$ 't := }\r
+ if$\r
+ }\r
+ while$\r
+ multiresult\r
+}\r
+\r
+FUNCTION {format.pages}\r
+{ pages empty$\r
+ { "" }\r
+ { pages multi.page.check\r
+ { "pages" pages n.dashify tie.or.space.connect }\r
+ { "page" pages tie.or.space.connect }\r
+ if$\r
+ }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.vol.num.pages}\r
+{ volume field.or.null\r
+ number empty$\r
+ 'skip$\r
+ { "(" number * ")" * *\r
+ volume empty$\r
+ { "there's a number but no volume in " cite$ * warning$ }\r
+ 'skip$\r
+ if$\r
+ }\r
+ if$\r
+ pages empty$\r
+ 'skip$\r
+ { duplicate$ empty$\r
+ { pop$ format.pages }\r
+ { ":" * pages n.dashify * }\r
+ if$\r
+ }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.chapter.pages}\r
+{ chapter empty$\r
+ 'format.pages\r
+ { type empty$\r
+ { "chapter" }\r
+ { type "l" change.case$ }\r
+ if$\r
+ chapter tie.or.space.connect\r
+ pages empty$\r
+ 'skip$\r
+ { ", " * format.pages * }\r
+ if$\r
+ }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.in.ed.booktitle}\r
+{ booktitle empty$\r
+ { "" }\r
+ { editor empty$\r
+ { "In " booktitle emphasize * }\r
+ { "In " format.editors * ", " * booktitle emphasize * }\r
+ if$\r
+ }\r
+ if$\r
+}\r
+\r
+FUNCTION {empty.misc.check}\r
+{ author empty$ title empty$ howpublished empty$\r
+ month empty$ year empty$ note empty$\r
+ and and and and and\r
+ key empty$ not and\r
+ { "all relevant fields are empty in " cite$ * warning$ }\r
+ 'skip$\r
+ if$\r
+}\r
+\r
+FUNCTION {format.thesis.type}\r
+{ type empty$\r
+ 'skip$\r
+ { pop$\r
+ type "t" change.case$\r
+ }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.tr.number}\r
+{ type empty$\r
+ { "Technical Report" }\r
+ 'type\r
+ if$\r
+ number empty$\r
+ { "t" change.case$ }\r
+ { number tie.or.space.connect }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.article.crossref}\r
+{ key empty$\r
+ { journal empty$\r
+ { "need key or journal for " cite$ * " to crossref " * crossref *\r
+ warning$\r
+ ""\r
+ }\r
+ { "In {\em " journal * "\/}" * }\r
+ if$\r
+ }\r
+ { "In " key * }\r
+ if$\r
+ " \cite{" * crossref * "}" *\r
+}\r
+\r
+FUNCTION {format.crossref.editor}\r
+{ editor #1 "{vv~}{ll}" format.name$\r
+ editor num.names$ duplicate$\r
+ #2 >\r
+ { pop$ " {\it et~al.}" * }\r
+ { #2 <\r
+ 'skip$\r
+ { editor #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" =\r
+ { " {\it et~al.}" * }\r
+ { " and " * editor #2 "{vv~}{ll}" format.name$ * }\r
+ if$\r
+ }\r
+ if$\r
+ }\r
+ if$\r
+}\r
+\r
+FUNCTION {format.book.crossref}\r
+{ volume empty$\r
+ { "empty volume in " cite$ * "'s crossref of " * crossref * warning$\r
+ "In "\r
+ }\r
+ { "Volume" volume tie.or.space.connect\r
+ " of " *\r
+ }\r
+ if$\r
+ editor empty$\r
+ editor field.or.null author field.or.null =\r
+ or\r
+ { key empty$\r
+ { series empty$\r
+ { "need editor, key, or series for " cite$ * " to crossref " *\r
+ crossref * warning$\r
+ "" *\r
+ }\r
+ { "{\em " * series * "\/}" * }\r
+ if$\r
+ }\r
+ { key * }\r
+ if$\r
+ }\r
+ { format.crossref.editor * }\r
+ if$\r
+ " \cite{" * crossref * "}" *\r
+}\r
+\r
+FUNCTION {format.incoll.inproc.crossref}\r
+{ editor empty$\r
+ editor field.or.null author field.or.null =\r
+ or\r
+ { key empty$\r
+ { booktitle empty$\r
+ { "need editor, key, or booktitle for " cite$ * " to crossref " *\r
+ crossref * warning$\r
+ ""\r
+ }\r
+ { "In {\em " booktitle * "\/}" * }\r
+ if$\r
+ }\r
+ { "In " key * }\r
+ if$\r
+ }\r
+ { "In " format.crossref.editor * }\r
+ if$\r
+ " \cite{" * crossref * "}" *\r
+}\r
+\r
+FUNCTION {article}\r
+{ output.bibitem\r
+ format.authors "author" output.check\r
+ new.block\r
+ format.date "year" output.check\r
+ new.block\r
+ format.title "title" output.check\r
+ new.block\r
+ crossref missing$\r
+ { journal emphasize "journal" output.check\r
+ format.vol.num.pages output\r
+ }\r
+ { format.article.crossref output.nonnull\r
+ format.pages output\r
+ }\r
+ if$\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {book}\r
+{ output.bibitem\r
+ author empty$\r
+ { format.editors "author and editor" output.check }\r
+ { format.authors output.nonnull\r
+ crossref missing$\r
+ { "author and editor" editor either.or.check }\r
+ 'skip$\r
+ if$\r
+ }\r
+ if$\r
+ new.block\r
+ format.date "year" output.check\r
+ new.block\r
+ format.btitle "title" output.check\r
+ crossref missing$\r
+ { format.bvolume output\r
+ new.block\r
+ format.number.series output\r
+ new.sentence\r
+ publisher "publisher" output.check\r
+ address output\r
+ }\r
+ { new.block\r
+ format.book.crossref output.nonnull\r
+ }\r
+ if$\r
+ format.edition output\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {booklet}\r
+{ output.bibitem\r
+ format.authors output\r
+ new.block\r
+ format.date output\r
+ new.block\r
+ format.title "title" output.check\r
+ howpublished address new.block.checkb\r
+ howpublished output\r
+ address output\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {inbook}\r
+{ output.bibitem\r
+ author empty$\r
+ { format.editors "author and editor" output.check }\r
+ { format.authors output.nonnull\r
+ crossref missing$\r
+ { "author and editor" editor either.or.check }\r
+ 'skip$\r
+ if$\r
+ }\r
+ if$\r
+ new.block\r
+ format.date "year" output.check\r
+ new.block\r
+ format.btitle "title" output.check\r
+ crossref missing$\r
+ { format.bvolume output\r
+ format.chapter.pages "chapter and pages" output.check\r
+ new.block\r
+ format.number.series output\r
+ new.sentence\r
+ publisher "publisher" output.check\r
+ address output\r
+ }\r
+ { format.chapter.pages "chapter and pages" output.check\r
+ new.block\r
+ format.book.crossref output.nonnull\r
+ }\r
+ if$\r
+ format.edition output\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {incollection}\r
+{ output.bibitem\r
+ format.authors "author" output.check\r
+ new.block\r
+ format.date "year" output.check\r
+ new.block\r
+ format.title "title" output.check\r
+ new.block\r
+ crossref missing$\r
+ { format.in.ed.booktitle "booktitle" output.check\r
+ format.bvolume output\r
+ format.number.series output\r
+ format.chapter.pages output\r
+ new.sentence\r
+ publisher "publisher" output.check\r
+ address output\r
+ format.edition output\r
+ }\r
+ { format.incoll.inproc.crossref output.nonnull\r
+ format.chapter.pages output\r
+ }\r
+ if$\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {inproceedings}\r
+{ output.bibitem\r
+ format.authors "author" output.check\r
+ new.block\r
+ format.date "year" output.check\r
+ new.block\r
+ format.title "title" output.check\r
+ new.block\r
+ crossref missing$\r
+ { format.in.ed.booktitle "booktitle" output.check\r
+ format.bvolume output\r
+ format.number.series output\r
+ format.pages output\r
+ address empty$\r
+ { organization publisher new.sentence.checkb\r
+ organization output\r
+ publisher output\r
+ }\r
+ { address output.nonnull\r
+ new.sentence\r
+ organization output\r
+ publisher output\r
+ }\r
+ if$\r
+ }\r
+ { format.incoll.inproc.crossref output.nonnull\r
+ format.pages output\r
+ }\r
+ if$\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {conference} { inproceedings }\r
+\r
+FUNCTION {manual}\r
+{ output.bibitem\r
+ author empty$\r
+ { organization empty$\r
+ 'skip$\r
+ { organization output.nonnull\r
+ address output\r
+ }\r
+ if$\r
+ }\r
+ { format.authors output.nonnull }\r
+ if$\r
+ new.block\r
+ format.date output\r
+ new.block\r
+ format.btitle "title" output.check\r
+ author empty$\r
+ { organization empty$\r
+ { address new.block.checka\r
+ address output\r
+ }\r
+ 'skip$\r
+ if$\r
+ }\r
+ { organization address new.block.checkb\r
+ organization output\r
+ address output\r
+ }\r
+ if$\r
+ format.edition output\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {mastersthesis}\r
+{ output.bibitem\r
+ format.authors "author" output.check\r
+ new.block\r
+ format.date "year" output.check\r
+ new.block\r
+ format.title "title" output.check\r
+ new.block\r
+ "Master's thesis" format.thesis.type output.nonnull\r
+ school "school" output.check\r
+ address output\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {misc}\r
+{ output.bibitem\r
+ format.authors output\r
+ format.date output\r
+ title howpublished new.block.checkb\r
+ format.title output\r
+ howpublished new.block.checka\r
+ howpublished output\r
+ new.block\r
+ note output\r
+ fin.entry\r
+ empty.misc.check\r
+}\r
+\r
+FUNCTION {phdthesis}\r
+{ output.bibitem\r
+ format.authors "author" output.check\r
+ new.block\r
+ format.date "year" output.check\r
+ new.block\r
+ format.btitle "title" output.check\r
+ new.block\r
+ "PhD thesis" format.thesis.type output.nonnull\r
+ school "school" output.check\r
+ address output\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {proceedings}\r
+{ output.bibitem\r
+ editor empty$\r
+ { organization output }\r
+ { format.editors output.nonnull }\r
+ if$\r
+ new.block\r
+ format.date "year" output.check\r
+ new.block\r
+ format.btitle "title" output.check\r
+ format.bvolume output\r
+ format.number.series output\r
+ address empty$\r
+ { editor empty$\r
+ { publisher new.sentence.checka }\r
+ { organization publisher new.sentence.checkb\r
+ organization output\r
+ }\r
+ if$\r
+ publisher output\r
+ }\r
+ { address output.nonnull\r
+ new.sentence\r
+ editor empty$\r
+ 'skip$\r
+ { organization output }\r
+ if$\r
+ publisher output\r
+ }\r
+ if$\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {techreport}\r
+{ output.bibitem\r
+ format.authors "author" output.check\r
+ new.block\r
+ format.date "year" output.check\r
+ new.block\r
+ format.title "title" output.check\r
+ new.block\r
+ format.tr.number output.nonnull\r
+ institution "institution" output.check\r
+ address output\r
+ new.block\r
+ note output\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {unpublished}\r
+{ output.bibitem\r
+ format.authors "author" output.check\r
+ new.block\r
+ format.date output\r
+ new.block\r
+ format.title "title" output.check\r
+ new.block\r
+ note "note" output.check\r
+ fin.entry\r
+}\r
+\r
+FUNCTION {default.type} { misc }\r
+\r
+MACRO {jan} {"January"}\r
+\r
+MACRO {feb} {"February"}\r
+\r
+MACRO {mar} {"March"}\r
+\r
+MACRO {apr} {"April"}\r
+\r
+MACRO {may} {"May"}\r
+\r
+MACRO {jun} {"June"}\r
+\r
+MACRO {jul} {"July"}\r
+\r
+MACRO {aug} {"August"}\r
+\r
+MACRO {sep} {"September"}\r
+\r
+MACRO {oct} {"October"}\r
+\r
+MACRO {nov} {"November"}\r
+\r
+MACRO {dec} {"December"}\r
+\r
+MACRO {acmcs} {"ACM Computing Surveys"}\r
+\r
+MACRO {acta} {"Acta Informatica"}\r
+\r
+MACRO {cacm} {"Communications of the ACM"}\r
+\r
+MACRO {ibmjrd} {"IBM Journal of Research and Development"}\r
+\r
+MACRO {ibmsj} {"IBM Systems Journal"}\r
+\r
+MACRO {ieeese} {"IEEE Transactions on Software Engineering"}\r
+\r
+MACRO {ieeetc} {"IEEE Transactions on Computers"}\r
+\r
+MACRO {ieeetcad}\r
+ {"IEEE Transactions on Computer-Aided Design of Integrated Circuits"}\r
+\r
+MACRO {ipl} {"Information Processing Letters"}\r
+\r
+MACRO {jacm} {"Journal of the ACM"}\r
+\r
+MACRO {jcss} {"Journal of Computer and System Sciences"}\r
+\r
+MACRO {scp} {"Science of Computer Programming"}\r
+\r
+MACRO {sicomp} {"SIAM Journal on Computing"}\r
+\r
+MACRO {tocs} {"ACM Transactions on Computer Systems"}\r
+\r
+MACRO {tods} {"ACM Transactions on Database Systems"}\r
+\r
+MACRO {tog} {"ACM Transactions on Graphics"}\r
+\r
+MACRO {toms} {"ACM Transactions on Mathematical Software"}\r
+\r
+MACRO {toois} {"ACM Transactions on Office Information Systems"}\r
+\r
+MACRO {toplas} {"ACM Transactions on Programming Languages and Systems"}\r
+\r
+MACRO {tcs} {"Theoretical Computer Science"}\r
+\r
+READ\r
+\r
+FUNCTION {sortify}\r
+{ purify$\r
+ "l" change.case$\r
+}\r
+\r
+INTEGERS { len }\r
+\r
+FUNCTION {chop.word}\r
+{ 's :=\r
+ 'len :=\r
+ s #1 len substring$ =\r
+ { s len #1 + global.max$ substring$ }\r
+ 's\r
+ if$\r
+}\r
+\r
+FUNCTION {sort.format.names}\r
+{ 's :=\r
+ #1 'nameptr :=\r
+ ""\r
+ s num.names$ 'numnames :=\r
+ numnames 'namesleft :=\r
+ { namesleft #0 > }\r
+ { nameptr #1 >\r
+ { " " * }\r
+ 'skip$\r
+ if$\r
+ s nameptr "{vv{ } }{ll{ }}{ ff{ }}{ jj{ }}" format.name$ 't :=\r
+ nameptr numnames = t "others" = and\r
+ { " {\it et~al.}" * }\r
+ { t sortify * }\r
+ if$\r
+ nameptr #1 + 'nameptr :=\r
+ namesleft #1 - 'namesleft :=\r
+ }\r
+ while$\r
+}\r
+\r
+FUNCTION {sort.format.title}\r
+{ 't :=\r
+ "A " #2\r
+ "An " #3\r
+ "The " #4 t chop.word\r
+ chop.word\r
+ chop.word\r
+ sortify\r
+ #1 global.max$ substring$\r
+}\r
+\r
+FUNCTION {author.sort}\r
+{ author empty$\r
+ { key empty$\r
+ { "to sort, need author or key in " cite$ * warning$\r
+ ""\r
+ }\r
+ { key sortify }\r
+ if$\r
+ }\r
+ { author sort.format.names }\r
+ if$\r
+}\r
+\r
+FUNCTION {author.editor.sort}\r
+{ author empty$\r
+ { editor empty$\r
+ { key empty$\r
+ { "to sort, need author, editor, or key in " cite$ * warning$\r
+ ""\r
+ }\r
+ { key sortify }\r
+ if$\r
+ }\r
+ { editor sort.format.names }\r
+ if$\r
+ }\r
+ { author sort.format.names }\r
+ if$\r
+}\r
+\r
+FUNCTION {author.organization.sort}\r
+{ author empty$\r
+ { organization empty$\r
+ { key empty$\r
+ { "to sort, need author, organization, or key in " cite$ * warning$\r
+ ""\r
+ }\r
+ { key sortify }\r
+ if$\r
+ }\r
+ { "The " #4 organization chop.word sortify }\r
+ if$\r
+ }\r
+ { author sort.format.names }\r
+ if$\r
+}\r
+\r
+FUNCTION {editor.organization.sort}\r
+{ editor empty$\r
+ { organization empty$\r
+ { key empty$\r
+ { "to sort, need editor, organization, or key in " cite$ * warning$\r
+ ""\r
+ }\r
+ { key sortify }\r
+ if$\r
+ }\r
+ { "The " #4 organization chop.word sortify }\r
+ if$\r
+ }\r
+ { editor sort.format.names }\r
+ if$\r
+}\r
+\r
+FUNCTION {presort}\r
+{ type$ "book" =\r
+ type$ "inbook" =\r
+ or\r
+ 'author.editor.sort\r
+ { type$ "proceedings" =\r
+ 'editor.organization.sort\r
+ { type$ "manual" =\r
+ 'author.organization.sort\r
+ 'author.sort\r
+ if$\r
+ }\r
+ if$\r
+ }\r
+ if$\r
+ " "\r
+ *\r
+ year field.or.null sortify\r
+ *\r
+ " "\r
+ *\r
+ title field.or.null\r
+ sort.format.title\r
+ *\r
+ #1 entry.max$ substring$\r
+ 'sort.key$ :=\r
+}\r
+\r
+ITERATE {presort}\r
+\r
+SORT\r
+\r
+STRINGS { longest.label }\r
+\r
+INTEGERS { number.label longest.label.width }\r
+\r
+FUNCTION {initialize.longest.label}\r
+{ "" 'longest.label :=\r
+ #1 'number.label :=\r
+ #0 'longest.label.width :=\r
+}\r
+\r
+FUNCTION {longest.label.pass}\r
+{ number.label int.to.str$ 'label :=\r
+ number.label #1 + 'number.label :=\r
+ label width$ longest.label.width >\r
+ { label 'longest.label :=\r
+ label width$ 'longest.label.width :=\r
+ }\r
+ 'skip$\r
+ if$\r
+}\r
+\r
+EXECUTE {initialize.longest.label}\r
+\r
+ITERATE {longest.label.pass}\r
+\r
+FUNCTION {begin.bib}\r
+{ preamble$ empty$\r
+ 'skip$\r
+ { preamble$ write$ newline$ }\r
+ if$\r
+ "\begin{thebibliography}{" longest.label * "}" * write$ newline$\r
+}\r
+\r
+EXECUTE {begin.bib}\r
+\r
+EXECUTE {init.state.consts}\r
+\r
+ITERATE {call.type$}\r
+\r
+FUNCTION {end.bib}\r
+{ newline$\r
+ "\end{thebibliography}" write$ newline$\r
+}\r
+\r
+EXECUTE {end.bib}\r
