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