source: Publications/Wilfried Dron/JOURNAL - Scheduling Method for Network Lifetime Estimation of WSN/original.tex @ 158

\documentclass[conference]{IEEEtran}
\usepackage{cite}  
\usepackage{graphicx}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{upquote}
%\usepackage{hyperref}
\usepackage{url}
\usepackage{arydshln}
\usepackage{listings}
\usepackage{subfigure}
\usepackage{balance}
\usepackage{xspace}

\newcommand{\pmsg}{{\textit{PowerMessage}}}
\newcommand{\imsg}{{\textit{InterfaceMessage}}}
\newcommand{\smsg}{{\textit{SignalMessage}}}
\newcommand{\dmsg}{{\textit{DigitalMessage}}}
\newcommand{\amsg}{{\textit{AnalogMessage}}}
\newcommand{\cmsg}{{\textit{ControlMessage}}}
\newcommand{\phymsg}{{\textit{PhysicalMessage}}}
\newcommand{\fm}{{{FM}}}
\newcommand{\pmm}{{{PM}}}
\newcommand{\phym}{{{PhyM}}}

\newcommand{\warn}{\textcolor{red}{\textbf{[REF]\space}}}
\newcommand{\tuple}[1]{\ensuremath{\left \langle #1 \right \rangle }}
\newcommand{\todo}[1]{\textcolor{blue}{{\bf Todo --\xspace}{\em #1}}}
\newcommand{\ie}{{\it i.e.},\xspace}
\newcommand{\eg}{{\it e.g.},\xspace}
\newcommand{\etal}{{\it et al.}\xspace}
\newcommand{\cf}{{\it c.f.},\xspace}

\newcommand{\sa}{{\textit{SA}}}
\newcommand{\fed}{{\textit{FED}}}
\newcommand{\sued}{{\textit{SUED}}}
\newcommand{\ffs}{{\textit{FFS}}}

\graphicspath{{D:/_DOCUMENTS/_DOCS/_THESE/Publications/Publications/Publications/_illustrations/}}

%\hyphenation{op-tical net-works semi-conduc-tor IEEEtran Power-Port OMNeT xMIPv6}

\begin{document}
\title{Scheduling Methods for Network Lifetime Estimation of Wireless Sensor Networks}
\author{
        Wilfried Dron\qquad Khalil Hachicha\qquad Patrick Garda\\       
        \normalsize{UPMC Univ Paris 6, UMR 7606, Laboratoire d'Informatique de Paris 6;}\\
        \normalsize{CNRS, UMR7606, LIP6;}\\
        \normalsize{F-75005, Paris, France} \\
        \texttt{[wilfried.dron; khalil.hachicha; patrick.garda]@lip6.fr}
}

\maketitle
\begin{abstract}
The network lifetime is a major constraint for the design of WSN's hardware and software. 
%While several simulation tools are focused on power consumption estimation, the network lifetime has been estimated using an ideal battery model. 
While several simulation tools are focused on estimating power consumption, the lifetime is commonly computed using a simple ideal battery model.
As a consequence, issues related with the use of a more realistic (non-ideal) battery model are not addressed yet. 
Considering the error that is made in node's lifetime estimation using an ideal battery model (up to 40\%), specifications-based models have been implemented to achieve more reliable predictions. 
In this context, we introduce four scheduling methods to address the challenges relative to such battery models.
These methods aim to manage energy transactions between the wireless node model and a non-ideal battery model.
%In this context, we introduce four scheduling methods to manage the energy transactions between the wireless node model and a non-ideal battery model, allowing a more accurate network lifetime estimation to be achieved. 
Each of our methods is analyzed and compared through a typical temperature sensing application case. 
We conducted several simulations considering power consumption estimation, simulation performances, node lifetime estimation and scalability. 
Comparison of the obtained results highlights two methods, one more accurate but, rather slow, whereas the other is strongly scalable but less accurate.
\end{abstract}

\section{Introduction}
The network lifetime is a key parameter of the wireless sensor network characterization~\cite{lifetime}. 
It reflects the time while the network can operate properly according to application-defined constraints.
%Even if almost every application defines its own constraints, the network lifetime cannot be estimated without being able to estimate the node's lifetime.
Even if almost every application defines its own constraints, the network lifetime is estimated using the individual node's lifetime information. 
Since some specific application requires the nodes to have a long lifetime~\cite{outdoor_gplatform} (\eg from several weeks to several years) and/or the network to count several dozen of nodes~\cite{wsn_trends}, it is common to use simulation and modeling tools to design such devices.

Nodes are battery-powered, thus the power consumption of the node and its battery characteristics are both necessary to determine its lifetime.
The power consumption profile is easily accessible from hardware measurements~\cite{wsn_energy} whereas it is more challenging to extract battery characteristics. 
Hence, it is common to use an ideal battery model to model the node's power source. 
This model is known as a battery with a linear discharge curve and a fixed output voltage.
Far from the real battery behavior, this model has the advantage to be flexible enough to not address the physical and electrical laws that exist in a real system. %between a real battery and the node that it supplies. 
%Nevertheless, when more accuracy is needed (as it is for medical applications for instance~\cite{wsn_app_medical_survey}) a more realistic battery model is required. 
To obtain more accurate lifetime estimation, another battery model, closer to the real battery behavior, is required. 
It can be either based on experimental measurements or technical specifications. 
To remain consistent using such a model, electrical laws have to be applied. 
Therefore, it is important to pay attention to the way power transactions between battery and supplied components are acheived.
In other words, the scheduling of the energy transactions trough the simulated time is crucial (\cf Fig.~\ref{archi_methods}).
%As a consequence, the scheduling of the energy transactions among the battery and the electronic components models is important. 
%Actually, it has a strong impact over the node's lifetime prediction. 
%In this article, we show that the way this scheduling is achieved impact significantly the lifetime estimation.
%Moreover, the way this scheduling is managed impacts the overall simulation performances and therefore, the ability to run large scale and/or long time simulation. 
%As a side effect, the scheduling method also impact the overall simulation performances, restricting the ability to simulate large scale and/or long time lasting networks.

In this context, we introduce four scheduling methods to schedule the energy transactions in a modeled wireless sensor network node. 
%We show that these methods are influencing the node lifetime estimation. 
We show that the way this scheduling is achieved impact significantly the lifetime estimation \todo{put figures\%}. 
%Moreover, the simulation's performance is also impacted, bounding the uses of certain methods to small-sized networks or short lifetime modeling.
As a side effect, the scheduling method also impacts the overall simulation performances, restricting the ability to simulate large scale and/or long time lasting networks.
This article is structured as follows. 
The second section hold the background of this work. 
The scheduling methods principles are explained in the section 3. 
The fourth section address the implementation of these methods in OMNeT++ trough a WSN framework that is oriented toward power consumption estimation. 
Finally, the two last sections hold respectively the simulation results and the discussion of these results.

\begin{figure}
\begin{center}
\includegraphics[scale=0.35]{architecture.pdf}
\caption{\label{archi_methods}
\textbf{Application example of the scheduling methods:} 
Here, \textsl{scheduling} stands for the way the supply voltage (v) is transmitted from battery to components and the way the instantaneous current draw (i) is transmitted from the component to the battery through the simulated time.
}
\end{center}
\end{figure}

\section{Background}
The scheduling method for energy transactions have not been addressed yet, thus there is no previous work on that subject. 
However, there are related works that are dealing with the power consumption estimation issues for the wireless sensor network simulation. 
Since the node lifetime estimation relies on the battery models as well it is important to give a brief introduction to the battery behavior. 
In that purpose, this section holds a short background about the battery behavior before addressing the core-related works.

\subsection{Battery Behavior and Modeling} \label{sect:battery_desc}
The batteries are electrochemical power sources. 
In contrast with the wired power sources, the amount of energy that they carry is limited. 
This amount of energy is called \textit{nominal capacity} if the battery is new or \textit{residual capacity} (shorten to \textit{residual}) if it has been partially used. 
Considering a battery under use, its residual varies with the ambient temperature and the instantaneous current draw. 
In other words, the available amount of energy change over the time according to the aforementioned factors. 
The battery's \textit{nominal current} (set by the manufacturer) represent the ``normal operation'' current limit under continuous draw.
The term \textit{effective capacity} stands for the battery's capacity that is really available given a set of condition (\eg specific instantaneous current draw and a temperature). 
Furthermore, their supply voltage varies as well with temperature and instantaneous current draw but also with the residual. 
As a consequence, a specific current draw can produce a drift in the battery's supply voltage value. 
According to the ohm law, this drift will change the current draw itself leading to a new drift. 
%Considering a resistive circuit, the voltage value would reach an equilibrium which is not the case considering regulated system like voltage regulators for instance. 
%All these assumptions were experimentally validated.

A first study highlights the fact that the way in which the components are drawing the current has a strong influence in the \textsl{effective capacity}~\cite{battery_char}. 
These observations were confirmed by a more recent work that characterized commercial Li-Ion batteries behaviors through real measurements~\cite{battery_char_new}. 
In this work, {K. Mikhaylov} and {J. Tervonen} observed again that the available capacity of the battery depends mainly on the instant current draw under constant temperature. 
Another article that focuses on remaining capacity measurements agrees on the same conclusion~\cite{remaining_capacity_measurement}. 
This last work addressed the specific case of determining the remaining battery capacity for a wireless sensor node using a method that consider the effective capacity and the instantaneous current draw instead of the voltage information. 

More battery centered work were achieved to reach a better understanding of the battery properties. 
Among them, another property known as \textit{relaxation effect} is explained in two articles written by L. Feeney and al.~\cite{battery_feeney,battery_model_feeney}.
As mentioned, when a strong current is drawn from the battery, its \textsl{effective capacity} decrease. 
In other words, its actual available energy is lower than the nominal value. 
This assumption is valid for a current draw that remains the same until the end of the battery life. 
If, for instance, the current draw decrease to a value that is beyond the battery's ``nominal current'', the battery will ``recover'' some capacity. 

To summarize, there are strong evidences that explain the limitations of ideal battery model. 
While this model is extremely flexible and fast thanks to the fact that it is not dependent on any phenomena, it is highly inaccurate and does not reproduce the behavior of a real battery.

\subsection{Simulation and Modeling Environments}
There are several simulators and frameworks that enable the power consumption estimation. 
Among them, a distinction is made between the environments that are oriented towards a specific platform and those that are more general, allowing any platform to be modeled. 
TOSSIM~\cite{tossim_ws} is, for instance, a network simulator dedicated to Tiny-OS~\cite{tinyos}. 
This simulator is extended by many further work. 
The most noticeable are Power-TOSSIM~\cite{powertossim_ws} and mTOSSIM~\cite{mtossim}.
Power-TOSSIM enables the power consumption to be computed after the simulation ends.
In contrast, mTOSSIM go further allowing the lifetime to be estimated.
It does so using a super-capacitor to model the power supply of the nodes.
The super-capacitor behavior is very different from battery behavior (\cf Section~\ref{sect:battery_desc}).
As a consequence, this model cannot be used to estimate the lifetime of nodes equipped with batteries.

%Platform-dedicated simulation environment are for instance Cooja~\cite{cooja}, the simulator of ContikiOS or Power-Tossim~\cite{powertossim_ws}, the simulator of Tiny-OS. 
%While these two simulators can achieve a precise power consumption estimation according to a specific application and its targeted hardware platform~\cite{powertossimz}, their main drawback is to be limited to the OS that they are simulating. 
%Furthermore, none of them is providing a node lifetime estimation or only based on ideal battery model. 
%As a consequence, these works are out of the scope of this paper.
 
Regarding the more general simulation environments, there are several network simulators like NS-2/3~\cite{ns2_ws}, OMNeT++~\cite{omnet_ws}, WSNeT~\cite{wsnet} or IdeaOne~\cite{ideaone}. 
Some of them are able to estimate power consumption thanks to extension called \textit{frameworks}.
However, the goal of these environments is to deal with network modeling issues more than network lifetime estimation. 
The OMNeT++ simulator is less concerned than the other environments since its flexibility allows new features to be integrated more easily as described in many surveys \cite{sim_survey_0,sim_survey_1,sim_survey_2,sim_survey_3} or in dedicated report from A. Varga and R. Hornig~\cite{omnet_overview}. 
As a consequence, several~\textit{power-aware} framework were developed over the previous years. 
Energy Model~\cite{modeling_energy}, Pawis~\cite{pawis_fm_2} and Energy Framework~\cite{energy_fm} were thus introduced. 
Unfortunately a common short-coming of these framework is that none of them provides a non-ideal battery model.

Nevertheless, this short-coming was partially covered in an extension of the Energy Framework. 
In their article, K. Mikhaylov and J. Tervonen were presenting a battery model~\cite{energy_fm_2} that was validated through measurement of real battery. 
Unfortunately, this validation does not consider battery supply voltage variations due to the current draw.
Furthermore, it neglects the internal resistance of the battery and the relaxation effect.
A side observation that the authors made is the fact that using an ideal battery model leads to an over-evaluation of the battery lifetime of almost $40$\%.
%Their first conclusion is the fact that using an ideal battery model leads to an over-evaluation of the battery lifetime of almost $40$\%. 
%Unfortunately, the techniques that were used to schedule the transaction between the battery model and the components model were not presented. 
%Moreover, the simulation case that was chosen was limited to a simple resistive model in which the supply voltage drifts were not considered. 
%As a result, it is difficult to re-use this work as a base for the network lifetime estimation. 
A last power-aware framework for OMNeT++ was introduced~\cite{newcas}. 
The battery model that is provided by the authors was build following technical specifications. 
Finally, the conclusion of their work states on the fact that using of the event driven technique together with their battery model results in erroneous battery lifetime estimations. 
To address this issue, they introduced a periodical scheduling method called \textit{Fixed Frequency Sampling} method.

%This latest framework was selected to implement the scheduling method because of its unique component oriented architecture and the several proposed models. 
%The following section is dedicated to the description of the methods. 
%Therefore, the firstly introduced scheduling method \textit{Fixed Frequency Sampling} will be exposed again in a more detailed way.

\section{Scheduling Methods} \label{sec:schedul_meth}
Our scheduling methods can be used in any structure that model one to N battery-supplied components. 
Modeling of the supply voltage and the instantaneous current draw is the only requirement that could limit their application. 
The architecture that is considered here is composed of one to N components model and a battery that supply them (\cf Fig.\ref{archi_methods}). 
A concrete application case is added as example after the general descriptions.
% in order to expose the differences between every scheduling method. 
Integration of these scheduling algorithms is explained as the conclusion of the section. 

%%%%% METHODS DESCRIPTION
\begin{figure}
\begin{center}
\includegraphics[scale=0.45]{schedule_FFS.pdf}
\caption{\label{figure1}
\textbf{Fixed frequency sampling method states graphic:} 
This graph shows the principle of the \ffs\xspace method. 
It appears that the battery update are triggered periodically (each \textit{T} second) after the step~5.
}
\end{center}
\end{figure}

\subsection{Fixed Frequency Sampling method (FFS)}
The \textit{Fixed Frequency Sampling} method (shorten to \ffs) was introduced into prior work~\cite{newcas}. 
This method relies on a periodic update of the battery's parameters and the current drawn by the components. 
Figure~\ref{figure1} is a state chart that describe its algorithm. 
First of all, the battery initiates the simulation by sending its supply voltage value to the component.
This allow the components to turn into ON mode. 
Then, they sends back their averaged instantaneous current consumption over the previous period (which is null for the very first period).
The battery residual and the supply voltage are then updated according to the received current draw value. 
Finally, if there is enough energy in the battery, the next update is scheduled at $t+T$ time (\textit{T} being the ``sampling period'' expressed in second). 
If the battery is depleted, it sends a $0.0$V supply voltage that turns the components into OFF mode.

\subsection{Self Updating Event Driven method (SUED)}
In contrast with the \ffs\xspace method, the \textit{Self Updating Event Driven} method takes into account every current draw changes instantaneously. 
The \sued\xspace scheduling method uses the same state chart as the \ffs\xspace method (\cf Fig.\ref{figure1}) except that it triggers additional battery updates as explained in the following.
When the simulation starts, the battery sends its supply voltage value to the components. 
The components send back their instantaneous current draw. 
Then the supply voltage and the remaining capacity of the battery are updated using the received value of the current draw. 
This current draw value is stored. 
If none of the components change their instantaneous current draw value, the battery will be updated every \textit{T} seconds. 
When a component changes its power mode (\eg ON $\rightarrow$ POWER DOWN), the corresponding instantaneous current draw value is sent to the battery. 
Then, the regular updating process is interrupted. 
The battery residual and the supply voltage are updated for the time elapsed from the last battery's update using the latest stored current draw value. 
Finally, the just received instantaneous current draw value is stored and the regular updating process starts again by scheduling the next update at $t+T$.

\begin{figure} 
\begin{center}
\includegraphics[scale=0.45]{schedule_FED.pdf}
\caption{\label{figure3}
\textbf{Fast event driven method state graphic:} 
This graph shows the principle of the \fed\xspace method. 
In this method, the battery update are triggered by each changes in the operating state of the components.
}
\end{center}
\end{figure}

\subsection{Fast Event Driven method (FED)}
The \textit{Fast Event Driven} method is derived from the ``formal'' event driven simulation technique. 
As a consequence, the battery updates are triggered by each current draw changes. 
The sate chart depicted Figure~\ref{figure3} represent the behavior of this scheduling method. 
The battery initiates the simulation by sending its supply voltage value. 
As a consequence, the components change their state from OFF to ON and send back their associated instantaneous current draw value. 
Alike the \sued\xspace method, this value is stored in the battery model. 
When the component changes its state again, this value will be updated. 
Before storing the just received value, a battery update is processed. 
%Actually, it will estimate and check its new residual value considering the time elapsed from the previous update. 
This update consist of checking and computing the new battery's residual considering the time elapsed from the previous update.
Battery's supply voltage value is also updated but using the new instantaneous current draw value and the residual that has just been estimated. 
Finally, this supply voltage value is sent to the component. 

Since the \fed\xspace scheduling method do not update the battery periodically, using this method can lead to node operating without energy.
If there is no event that makes the current draw change such as power mode changing, the simulation can run even if the battery is totally depleted at a certain point. 
%As a consequence, another mechanism is required. 
A way to avoid this issue is to ``plan'' the end of the battery life assuming that there will be no more event. 
To be consistent, this end of life forecast has to be re-evaluated each time the current draw value changes. 
In other words, the battery's end of life has to be re-planned each time that a battery update is triggered.

\subsection{Self Adaptive method (SA)}
The \textit{Self Adaptive} method is based on both a periodical update schedule and a event-driven like schedule. 
%Actually, the previously introduced method are sensitive to the time and/or to the current draw changes events. 
In addition, the \sa\xspace method is sensitive to the current draw value.
Battery behavior observations allow us to make the following assumption: The discharge curve can be separated in two areas, a pseudo-linear area (before the \textit{nominal current} value) and a non-linear area (after the \textit{nominal current} value). 
The border between these two areas is the \textit{nominal current draw} (\cf Sec.~\ref{sect:battery_desc}).
As a consequence, the \sa\xspace scheduling method changes the way it triggers battery's and components updates according to the instantaneous current draw value. 
When this value is under the \textit{nominal current} value of the modeled battery, the battery updates are triggered in the same way as if the \fed\xspace method were used. 
In the opposite case (the current draw is under the \textit{nominal current} value), these updates are triggered as if the \ffs\xspace scheduling method were used. 

On the one hand, this scheduling algorithm is able to enhance the accuracy of the estimation when it is necessary (when the battery model is strongly non-linear) and on the other hand, it is able to run the simulation faster when there is no need to (when the battery model is almost linear).

\subsection{Application example}
The chosen application example is a single component that is supplied by a battery. 
The functional behavior of this component is not discussed here since the meaningful information is its current draw consumption. 
As a consequence, the power mode states are the only information that are considered. 
The following mode sequence was arbitrarily chosen: 
\begin{itemize}
\item OFF $\rightarrow$ ON $\rightarrow$ POWER DOWN $\rightarrow$ ON.
\end{itemize}
The Figure~\ref{time} is a representation of each scheduling method applied to our example. 
%Each of the four graphs illustrates the results of its method applied to the example case. 
All the graph are time aligned making the difference between each scheduling method easier to understand.

\begin{figure}
\begin{center}
\includegraphics[scale=0.45]{method_global.pdf}
\caption{\label{time}
\textbf{Application example of the scheduling methods:} 
This figure is a time graph that shows the application of each scheduling method to our application example. 
The \ffs\xspace method trigger battery update according to its sampling period \textit{T}. 
The \sued\xspace method trigger as well the update of the battery each \textit{T} seconds but also when a component changes its operating state. 
The \fed\xspace method only triggers battery updates on the components change. 
The \sa\xspace method use periodic update when precision is required and event driven updates when less precision is needed.
}
\end{center}
\end{figure}

Figure~\ref{time}a is the graph that represent the \ffs\xspace method application. 
The updates of the battery and the component's current draw changes are asynchronous. 
Moreover, the supply voltage updates are delayed by one period in comparison with the current draw updates. 
In other words, the supply voltage value that is used by the component to compute its draw is the one that has been estimated the previous period by the battery model.
Figure~\ref{time}b represent the application of the \sued\xspace method. 
In contrast with the \ffs\xspace method, it appears that the battery's updates are synchronized with the current draw changes. 
The periodical update is also observable while the component is in LOW POWER mode. 
Alike the \ffs\xspace method, the supply voltage updates are also delayed.

The application of the \fed\xspace method is plotted in the graph Figure~\ref{time}c. 
%The fact that the battery updates happen only in synchronization with the component's power mode changes is highlighted. 
The graph highlight that the battery updates happen only in synchronization with the component's power mode changes.
The Figure~\ref{time}d illustrates the application of the \sa\xspace method. 
This method is sensitive to the current draw value in respect with the battery characteristics.
The current drawn in ON mode is assumed as being over the \textit{nominal current} value and the current drawn in the POWER DOWN mode is assumed as being under. 
Consequently, periodical updates are achieved when the components is in ON mode whereas there is no update while the component is in LOW POWER mode.

%\section{Modeling and integration in the Framework}
\subsection{Framework Integration}\label{implementation}
As mentioned previously, we chose to implement our scheduling method in an OMNeT++ framework~\cite{newcas}.
%As mentioned previously, a power aware simulation environment was chosen to implement the scheduling methods \cite{newcas}. 
%Actually, this environment is an OMNeT++'s framework that allows the wireless sensor node to be described with each of its electronic components. 
This environment allows a node to be described with every of its electronic components. 
Each component is described using two levels of description: a functional and a hardware one. 
Practically, the components are described using a functional model and a power model. 
Regarding the battery, a ``technical specification based'' model is provided.

The integration of our scheduling methods requires few modifications in the provided models. 
Theoretically, each power model should be modified according to the chosen scheduling method.
Fortunately, the simulated architecture use a DC/DC step-down converter to keep the supply voltage between the battery and the components steady. 
Therefore we consider the following assumption: the voltage do not change between the components' power model and the step down converter's output. 
%WD: to moove in the discussion
%Actually, even if some precision can be lost by doing this, this assumption is realistic since the modeled converter is not used in its limitations. 
Consequently to this assumption, the only models that requires to be modified are the battery model and the converter model.

To ensure reliable simulation results, mechanisms of the modified components were isolated into functions that takes every necessary information as parameters. 
Even if it needed additional formalizing and coding efforts, this approach allows us to described the models independently from the scheduling method. 
%The way and the sequence order in which the function are called determined the scheduling method. 

\section{Modelling and simulation configuration}
\subsection{Battery Modelling}
The battery model that was used in the simulation is a model of the CR2032 battery from Panasonic~\cite{cr2032}. 
The instantaneous current draw is considered to estimate the residual capacity and thus, predict the battery lifetime according to the technical specifications. %(cf. Fig.\ref{cr2032}). 
%\begin{figure} 
%\begin{center}
%\includegraphics[scale=1.1]{cr2032_capacity_vs_load_resistance.pdf}
%\caption{\label{cr2032}Panasonic CR2032: \textit{capacity vs. load resistance characteristic} \cite{cr2032} }
%\end{center}
%\end{figure}
The impact of the temperature variation on the battery were not considered in the following simulation case. 
As a consequence, the battery's \textit{effective capacity} varies only with the instantaneous current draw. 
\begin{figure}
\begin{center}
\includegraphics[scale=0.40]{eq_current_plot.pdf}
\caption{\label{eq_current}
\textbf{Equivalent and instantaneous current draw estimations:} 
This graph show the difference between the instantaneous current drawn by the components (shorten to \textit{Inst.}, \cf $i(t)$ in Eq.~\ref{ieq}) and the current that is actually seen by the battery (shorten to \textit{Eq.}, \cf $i_{eq}$ in Eq.~\ref{ieq}).
}
\end{center}
\end{figure}

In this model, the capacity of the battery is considered as fixed. 
Therefore, to model the impact of the instantaneous current draw on the \textit{relative capacity}, the equivalent current draw $i_{eq}$ was considered. 
It has been defined using the following equation:
\begin{equation}\label{ieq}
i_{eq} = \frac{C_{nominal}}{C_{relative}(i(t))} \times i(t)
\end{equation}
Where $C_{nominal}$ is the \textit{nominal capacity} and $C_{relative}$ is the \textit{relative capacity} (according to the instantaneous current draw), both expressed in mAh. 
The $i(t)$ is the instantaneous current expressed in mA. 
The factor between $C_{nominal}$ and $C_{relative}$ is called the \textit{overdraw factor}. 
Therefore, the equivalent current draw is expressed as a function of the present instantaneous current draw as depicted in the chart Figure~\ref{eq_current}. 
This graph was plotted using a current draw ramp directly plugged in the battery model. 
This battery modeling technique has the advantage of modeling both the \textit{effective capacity} and the \textit{relaxation} effects as well.
%Even if this abstraction of the real battery behavior is not perfect, it has the advantage of modeling both the \textit{effective capacity} and the \textit{relaxation} effects as well.

The equation that is used to estimate the battery's residual $R$ at the $t+\Delta t$ instant is the following one:
\begin{equation}
R(t+\Delta t) = R(t) -  i_{eq} \times \frac{\Delta t}{3600}
\end{equation}
Where $R(t)$ is the previous residual value in mAh, $i_{eq}$ is the \textit{equivalent current draw} (\cf Eq.\ref{ieq}) in mA, $\Delta t$ the time while the $i_{eq}$ current was drawn expressed in second. 
Finally, the $3600$ value stands for the conversion of $\Delta t$ in hours.

%\section{Simulation}
\subsection{Simulated Architecture}
The platform used as modeling base was a prototype under development.
It is composed of a NTC temperature sensor, a Texas Instruments (TI) MSP430FR5739 micro-controller~\cite{msp430_fr}, a TI CC2520 radio frequency transceiver~\cite{cc2520} and a TI TPS62122 step-down DC/DC converter~\cite{tps62122}. 
The power supply is handled by 4 CR2032 batteries~\cite{cr2032} that are assembled in serial. 
%The figure \ref{omnet} is a screen shot of the modelled node into the simulation environment.
%\begin{figure}
%\begin{center}
%\includegraphics[scale=0.55]{node_omnet.jpg}
%\caption{\label{omnet}Description of the node's architecture inside the WSN framework}
%\end{center}
%\end{figure}
The measurements that were used to build the MCU and the transceiver models are reported in Table~\ref{msp_meas}. 
These measurements were made using an \todo{add ref} ampere-meter integrated in a PXI rack from National Instruments. 
The used precision was \todo{add figure} digit, the maximum precision of the device. 
The MCU firmware that was used to achieve this was the application that is embedded in the sensing node. 
Consumption measurements of the MSP430 are not restricted to the core but include also the consumption of the whole chip.

\begin{table}[h]
\centering
\subtable[MSP430]{
        \begin{tabular}{|c||c|c|c|c|}
                \hline
                \textit{Mode} & Active & ADC+LPM4 & LPM4 \\ 
                \hline
                Inst. current & 0.813mA & 0.326mA & 0.226mA \\
                \hline
        \end{tabular}
}
%\begin{tabular}{cccccccc}
 %& & & & & & &\\
%\end{tabular}
\subtable[CC2520]{
        \begin{tabular}{|c||c|c|c|c|c|c|}
                \hline
                \textit{Mode} & XOSC Off & Idle & RX & RX LP & TX-18dBm \\
                \hline
                Inst. current & 0.178mA & 1.776mA & 22.48mA & 18.79mA &  16.63mA\\
                \hline
        \end{tabular}
}
\smallskip
\caption{\label{msp_meas}{\bf Experimental measurements of the current draw}}
\end{table}

Regarding the functional behavior, the application that is modeled is a typical temperature measuring scenario. 
The network is organized in a star topology and the IEEE 802.15.4 protocol is used by the node to communicate. 
The sensing node behavior is the following: 
\begin{enumerate}
\item The node start to listen the channel to seek for a broadcast frame that comes from the central node;
\item Once it received the frame with the same PAN-ID and the expected source address, it acknowledge the subscription;
\item Every second it wakes up, takes a measure of the temperature and send it to the central node before going back to sleep.
\end{enumerate}
Each sensor has a time slot that is computed according to its own address, at the beginning of the run. 
The central node is periodically broadcasting its subscription frame an turns into reception mode right after. 
Therefore, its power consumption is high in comparison with the sensor node. 
In the simulation, it is considered as being supplied by an ideal power source with infinite energy.

\section{Results}
All along this section, several simulation cases and their results are presented. 
The sampling period \textit{T} of the \ffs, the \sued\xspace and the \sa\xspace (\cf Sect.~\ref{sec:schedul_meth}) scheduling methods were set to the same value ($50$us). 
This choice is motivated by the simulation performances (\cf Sect.~\ref{sim_perfs}).
The computer that was used to obtain the results is based on a Core i7 860 @ 2.80GHz processor from Intel and 8 gigabytes of RAM. 
Ubuntu LTS 12.04 was used as operating system. 
The OMNeT++ version was the 4.3. 
Simulator was configured to use only one core over eight in order to have no hardware acceleration that could biased the performance results.
%Each simulation case was run at least 10 times in order to verify the reliability of the obtained results. 

\subsection{Power consumption estimation}
The power consumption estimation results were obtained by simulating four instances of the same node for one hour of simulated time. 
Each node implements a different method to schedule the power transaction between the batteries and the components. 
As a reference, another simulation was run within the same conditions but using ideal battery models instead of CR2032 models. 
The battery's residual value results for both simulations are presented in Table~\ref{residual_results}. 

\begin{table}[h]
\centering
\begin{tabular}{|c||c|c|c|c|}
        \hline
                & FFS & SUED & FED & SA\\
        \hline
        \multicolumn{5}{|c|}{Nodes with Ideal model (\textit{T}=50us)}  \\
        \hline
        Residual (mAh) & $\textbf{219.9273}$ & $\textbf{219.9273}$ & $\textbf{219.9273}$ & $\textbf{219.9273}$\\
        Consumed Energy (mAh) &$0.0727$&$0.0727$&$0.0727$& $0.0727$\\
        Av. eq. current (uA) &$72.7$&$72.7$&$72.7$&$72.7$\\
        %Av. voltage (V)&$12.00$&$12.00$&$12.00$&$12.00$\\
        \hline
        \hline
        \multicolumn{5}{|c|}{Nodes with CR2032 model (\textit{T}=50us)}  \\
        \hline
        Residual (mAh) & $\textbf{219.9249}$& $\textbf{219.9248}$ & $\textbf{219.9167}$& $\textbf{219.9137}$\\
        Consumed Energy (mAh) & $0.0751$& $0.0752$& $0.0833$& $0.0863$\\
        Av. eq. current (uA) & $75.1$& $75.2$& $83.3$& $86.3$\\
        \hline
\end{tabular}
\smallskip
\caption{\label{residual_results}
{\bf Battery's residual estimation results:}
{\textnormal{
The battery residual estimation does not change for the ideal battery model regardless of the scheduling method. 
In contrast, the residual estimation are different for each scheduling method using the technical specification based battery model}
}
}
\end{table}

%\begin{table}[h]
%\centering
%\caption{\label{consumption_result}Power consumption estimation}
%\begin{tabular}{|c||c|c|c|c|}
%\hline
%\multicolumn{5}{|c|}{Simulated time = 60 minutes}  \\
%\hline
% & FFS & SUED & FED & SA\\
%\hline
%\hline
%\multicolumn{5}{|c|}{Power Consumption: Ideal model}  \\
%\hline
%Residual (mAh) & $\textbf{219.9273}$ & $\textbf{219.9273}$ & $\textbf{219.9273}$ & $\textbf{219.9273}$\\
%Consumed C. (mAh) &$0.0727$&$0.0727$&$0.0727$& $0.0727$\\
%Av. eq. current (uA) &$72.7$&$72.7$&$72.7$&$72.7$\\
%Av. voltage (V)&$12.00$&$12.00$&$12.00$&$12.00$\\
%\hline
%\hline
%\multicolumn{5}{|c|}{Power Consumption: CR2032 model}  \\
%\hline
%Residual (mAh) & $\textbf{219.9249}$& $\textbf{219.9248}$ & $\textbf{219.9167}$& $\textbf{219.9137}$\\
%Consumed Energy (mAh) & $0.0751$& $0.0752$& $0.0833$& $0.0863$\\
%\hline
%Max current (mA) & $3.99$ & $3.99$& $3.92$& $3.99$\\
%Min current (mA) & $0.073$ & $0.073$& $0.071$& $0.071$\\
%\hline
%Max eq. current (mA) & $7.359$& $7.359$& $7.033$& $7.359$\\
%Min eq. current (mA) & $0.70$& $0.073$& $0.071$& $0.071$\\
%Av. eq. current (uA) & $75.1$& $75.2$& $83.3$& $86.3$\\
%\hline
%Max voltage (V) & $12.0$& $12.0$& $12.0$& $12.0$\\
%Min voltage (V) & $9.98$& $9.98$& $10.67$& $9.98$\\
%Av. voltage (V) & $10.62$& $10.54$& $11.40$& $10.70$\\
%\hline
%\end{tabular}
%\end{table}

The first important observation is the fact that scheduling method do not influence the lifetime estimation in the case of ideal battery modeling. 
Actually, the four nodes reach the end of the simulation with the same residual value ($219.9273$ mAh), the same current draw and the same voltage value. 
In contrast, the results obtained by the node that were equipped with CR2032 models are not equal. 
These variations in the power consumption estimations highlight the fact that scheduling method do influence the residual estimation. 
Consequently, the node lifetime estimation is also influenced even if each battery model and each component model is the same.

\begin{table}[h]
\begin{center}
\begin{tabular}{|c||c|c|c|c|}
\hline
 & FFS & SUED & FED & SA\\
\hline
Max current (mA) & $3.99$ & $3.99$& $3.92$& $3.99$\\
Min current (mA) & $0.073$ & $0.073$& $0.071$& $0.071$\\
\hline
Max eq. current (mA) & $7.359$& $7.359$& $7.033$& $7.359$\\
Min eq. current (mA) & $0.70$& $0.073$& $0.071$& $0.071$\\
%\hline
%Av. eq. current (uA) & $75.1$& $75.2$& $83.3$& $86.3$\\
\hline
\end{tabular}
\end{center}
\smallskip
\caption{\label{current_results}{\bf Instantaneous and equivalent current draw estimation:} \textnormal{The estimated values are slightly different for each scheduling method.}}
\end{table}

Focusing on the detailed results, the residual estimation that is obtained using the \ffs\xspace method is the highest one with $219.9429$ mAh. 
Firstly, the current draw is integrated over the \textit{T} period. 
This is comparable to a \textit{low pass filter} that cuts the edges of the current draw spikes. 
Secondly, the supply voltage value is the one that has been computed using the previous current draw value. 
The impact of the voltage drifts are consequently lowered. 
The \sued\xspace method suffers from the same observations, except for the spike transition thanks to the synchronized current updates. 
This explains why the average \textit{equivalent current draw} (\cf Eq.~\ref{ieq}) value that is obtained using the \sued\xspace scheduling method is slightly more important than the \ffs\xspace one ($75.2$uA $>$ $75.1$uA). 
To achieve better results with these scheduling methods, the Shannon theorem should be observed. 
In other word, the sampling period should be at least twice short as the shorter power mode changing of the system. 
In the present case, the shorter period is around 5us. 
Therefore a 2.5us period is the minimum period length regarding the accuracy and the precision of the estimation. 
Unfortunately, using such a small period results in an extremely slow simulation as presented in the next section. 

%Another fact that could explain that the result of the sampling based method are not the same as the \fex\xspace and \sa\xspace methods is the numeric precision. 
Another noticeable result is the difference in the residual estimated with \ffs\xspace and \sued\xspace methods in comparison with \fed\xspace and \sa\xspace methods. 
These variations could be explained by the numeric precision. 
Since there is more computation using the CR2032 model than the ideal battery model, precision could have been lost in every intermediary value computation ending to a under-estimated power consumption. 
Actually, this phenomena is partially observable considering the current draw and the equivalent current draw estimation (\cf Tab.~\ref{current_results}). 

\begin{table}[h]
\centering
\begin{tabular}{|c||c|c|c|c|}
        \hline
        & FFS & SUED & FED & SA\\
        \hline
        Max voltage (V) & $12.0$& $12.0$& $12.0$& $12.0$\\
        Min voltage (V) & $9.98$& $9.98$& $10.67$& $9.98$\\
        %Av. voltage (V) & $10.62$& $10.54$& $11.40$& $10.70$\\
        \hline
\end{tabular}
\smallskip
\caption{\label{voltage_results}
{{\bf Battery supply voltage estimation:}
\textnormal{The estimated supply voltage values are the same except for the FED method.}
}
}
\end{table}

Focusing on the event-driven based scheduling method \fed, the obtained residual estimation is lower than the \ffs\xspace and the \sued\xspace method but higher than the \sa\xspace method. 
This is a result of the event driven-like algorithm. 
The current drawn by the components is updated immediately when one of them changes its power mode. 
Once a new current value draw has been transmitted to the battery, its residual is computed and its voltage value is updated but there is no further updates from both the components and the battery until a components change its current draw again. 
This explain also why the average equivalent current obtained thanks to the \sa\xspace method was higher with $86.3$uA (\cf Tab.~\ref{residual_results}). 
The observation of the current draw and the equivalent current draw in the Table~\ref{current_results} are confirming this assumption. 
Actually, even if every battery has to supply the same current both the maximal current and the maximal equivalent current estimated using the \fed\xspace method are lower than the other methods.

The sampling mechanism of the \sa\xspace method allows the battery model to react almost instantly to every current draw variation. 
Finally, while the average voltage obtained using the \ffs\xspace, \sued\xspace and \sa\xspace methods are quite close, the supply voltage value obtained using the \fed\xspace method is higher (\cf Tab.~\ref{voltage_results}). 
This highlights once again the fact that updates are driven by the components' power state changes.

\subsection{Simulation performance} \label{sim_perfs}
The simulation performance results were obtained by running the nodes for five minutes of CPU time (300 seconds). 
Two series of simulation were conducted. 
The first one consist of running one single node and its base station at a time. 
Each scheduling method is therefore evaluated on its own. 
The second one consist of the same principle but running a network of five identical nodes. 
The main results are presented in Table~\ref{residual_results}. 
In this table there is several abbreviation: 
\begin{itemize}
\item the simulated time: \textit{\textbf{Sim.time}}
\item the average simulated sec. per sec. ratio: \textit{\textbf{Av.Sim.s/s}}
\item the number of simulated events: \textit{\textbf{N.ev.}}
\item the average number of event per sec.: \textit{\textbf{Ev/s}}
\end{itemize}


The time indications give basic idea on how much of CPU time it would take if the simulation has to reach a specific time. 
The event indications give idea about the load of the simulation kernel. 
It allows to figure out the raw performances and eventually deduce the impact of porting the scheduling methods to another simulation environment.
\begin{table}[h]
\centering
\begin{tabular}{|c||c|c|c|c|}
\hline
\multicolumn{5}{|c|}{CPU time = 5min (300 s)}  \\
\hline
 & FFS & SUED & FED & SA\\
\hline
\hline
\multicolumn{5}{|c|}{1 Node}  \\
\hline
Av.Sim.s\slash s & \textbf{2.695} & \textbf{5.474} & \textbf{6699} & \textbf{3342}\\
\hline
Sim.time & 13min:28s& 27min:22s & 23d:6h & 11d:22h\\
N.ev. &$48\times10^6$&$98\times10^6$&$80\times10^6$&$82\times10^6$ \\
Ev\slash s &$1.6\times10^5$&$3.2\times10^5$&$2.7\times10^5$&$2.7\times10^5$ \\
\hline
\multicolumn{5}{|c|}{5 Nodes}  \\
\hline
Av.Sim.s\slash s & \textbf{0.576} & \textbf{1.218} & \textbf{1330} & \textbf{713.5}\\
\hline
Sim.time & {2min:52s}&{6min:5s}& {4d:14h}& {2d:11h}\\
N.ev. &$51.8\times10^6$&$109.6\times10^6$&$86.6\times10^6$&$89.3\times10^6$ \\
Ev\slash s &$1.7\times10^5$&$3.6\times10^5$&$2.8\times10^5$&$2.9\times10^5$ \\
\hline
\end{tabular}
\smallskip
\caption{\label{perf_table}
{{\bf Simulation performance (\textit{T}=50us)}:
\textnormal{This table summarize the performances of each method. The FFS and SUED scheduling methods are the slowest and the less scalable methods. In contrast, the FED and the SA scheduling methods allow to simulate in a faster way larger networks}
}
}
\end{table}

Regarding the simulated time for a single node, the results are quite clear. 
The \ffs\xspace and the \sued\xspace method reach $13$ and $27$ minutes respectively. 
In contrast, the \sa\xspace method is able to simulate almost $12$ days in $5$ minutes of CPU time. 
The \fed\xspace method outperforms by reaching $23$ days of simulated time and almost $2$h simulated per second.
The results of the 5 nodes are following the same trends. 
The average simulated second per second rate of the \ffs\xspace method decrease to $0.57$ sim.s/s which is quite slow since its under the ``unity rate'' of $1$ sim.s/s. 
The \sued\xspace method is slightly faster with 1.2 sim.s/s rate that enables it to reach $6$ minutes of simulated time in $5$ minutes. 
Finally, the best performances were obtained using the \sa\xspace and the \fed\xspace method with respectively 2 days and 4 days of simulated time.

As a consequence, the \ffs\xspace and the \sued\xspace method are not considered in the following experiments. 
This choice is motivated by the fact that these two methods are not suitable for long-time simulation (several months) nor for networks that implies several nodes.

\subsection{Node lifetime estimation}
The node lifetime estimation results were obtained by running one single node and the central node until the first voltage drops that makes the node reset. 
This scenario focuses on the real node lifetime as it has been defined in the beginning of this article. 
If, for any reason, there is a voltage drop that makes the node reset, there is high chances that it happens again and again until the complete depletion of the battery. 
Therefore the node can be considered as dead or not reliable enough from the point of view of the network.

As mentioned before, only the \fed\xspace and the \sa\xspace method were considered in this experiments. 
Making the same run with the \ffs\xspace method would have require approximately 1 month of continuous run. 
The theoretical lifetime $L_{TH}$ of the node obtained with an ideal battery model is around 4 months ($L_{TH} \approx 220\slash 0.0727 \approx$ 4.2 months). 
This estimation implicitly assumes that the battery is able to supply the node until its total depletion, which is not the case. 
The node lifetime estimation results are presented in the Table~\ref{sim_table_2}. 
First analysis of these results reveals that estimation obtained by the \fed\xspace and the \sa\xspace methods are significantly different. 
The \fed\xspace node lasted three months and twelve days while the \sa\xspace node lasted three months and one day. 
This represent a difference of $11.7$\% between the two methods and a difference of $20.8$\% (\fed) and $35.0$\% (\sa) between each method's lifetime estimation and $L_{TH}$.

\begin{table}[h]
\centering
\begin{tabular}{|c||c|c|}
\hline
 & FED & SA\\
\hline
\hline
\multicolumn{3}{|c|}{Node lifetime (\textit{T}=50us)}  \\
\hline
Lifetime &  3m:12d:7h:29min:0s & 3m:1d:8h:50min:29s\\
\hline
Residual (mAh) & $0.0176$ & $\textbf{16.8062}$\\
\hline
Simulation time &  22min:25s & 38min:18s\\
Av.Sim.s\slash s &  $6700$ & $3510$\\.
N.ev. &$3.6\times10^8$ &$64\times10^8$ \\
Ev\slash s &$2.7\times10^5$ & $2.8\times10^5$\\
\hline
%Gain Factor  & $98.5$ & $1.35$\\
%\hline
\end{tabular}
\smallskip
\caption{\label{sim_table_2}
{\bf Node lifetime estimation performance}:
\textnormal{The difference of 11.7\% between the two methods highlight the fact that scheduling methods do influence the lifetime estimation.}
}
\end{table}

A closer observation of the residual values at the end of the simulation is highlighting the fact that the \sa\xspace node stops operate properly before the \fed\xspace node. 
It appears that the battery's voltages drift are not well modeled with the \fed\xspace method since the likelihood of the fact that the battery lasts until almost complete depletion ($0.0176$ mAh) is low. 
Considering the technical specification, the battery should not be able to handle the current spike of a RF frame transmission at this depletion level. 
Consequently, the results obtained by the \sa\xspace method are more realistic. 
Unfortunately, there is no means to measure the remaining capacity in a real battery to have a comparison point. 
Further experiments about battery discharge in this particular application case will be conducted in order to experimentally validate this hypothesis. 

\subsection{Scalability}
The last exposed experiment was conducted to evaluate the scalability of the \fed\xspace and the \sa\xspace scheduling methods. 
The simulated time was set to $24$h hours. 
Each simulation contained a complete network with $10$ to $250$ nodes and a central station. 
The obtained result are presented in the table \ref{sim_table_3}. 

\begin{table}[h]
\centering
\begin{tabular}{|c||c|c|}
\hline
\multicolumn{3}{|c|}{Simulated time = 24h (\textit{T}=50us)}\\
\hline
 &FED&SA\\
\hline
10 nodes & $2$min $11$s & $4$min $6$s \\
%\cdashline{2-3}
50 nodes & $13$min $57$s & $24$min $3$s \\
%\cdashline{2-3}
100 nodes & $36$min $17$s & $56$min $52$s\\
%\cdashline{2-3}
250 nodes & $2$h $58$min & $3$h $45$min \\
\hline
\end{tabular}
\smallskip
\caption{\label{sim_table_3}
{\bf Scalability comparison: simulation time for 10 to 250 nodes}:
\textnormal{This table is a comparison of the time that is required for each methods to reach 24h of simulated time considering various network size. The results show clearly that the SA method needs almost twice the time of the FED method to achieve it. However, when the size of the network increase, this factor decreases.}
}
\end{table}

First observation that can be made is the fact the evolution of the time as a function of the number of the nodes is not linear. 
Actually, simulating 250 nodes should be 25 times longer than simulating 10 nodes. 
Simulating 10 nodes with the \fed\xspace method takes 2.18 minutes but simulating 250 node takes almost three hours instead of 54 minutes as it could be expected. 
This is explained by the fact that each additional node adds a significant traffic load. 
A second observation is the fact that when network are small ($<$50 nodes) the \fed\xspace method is roughly two time faster than the \sa\xspace method. 
This difference seems to decrease when the size of the network increase. 
With a 250 nodes network, using the \sa\xspace method takes only 26\% more time than the \fed\xspace method. 

More generally, these results are highlighting the high scalability of the \fed\xspace method in comparison with the \sa\xspace method that is slower.

\section{Conclusion}
In this work, we have introduced four scheduling methods to address the specific issue of network lifetime estimation when a non-ideal battery model is used. 
Our first experiments revealed that the scheduling methods do have an impact on battery's lifetime estimations and thus on the node lifetime prediction. 
As expected, our results are showing that the sampling based methods are not suitable for large scale simulation whereas it seems to be the most intuitive way to reach an accurate and precise estimation. 
In contrast, event-driven based method is the fastest scheduling method whereas it appears to lead to inaccurate results. 
Finally, the compromise between the event-driven and the periodical scheduling methods was found as the \sa\xspace method which enables a fast and accurate network lifetime estimation. 

Our future work will address the comparison of the lifetime prediction and the real measurement thanks to a WSN testbed oriented towards network lifetime characterization. 
The technical based proposed model will be compared to real measurement of the battery behavior. 
Finally, we will accentuate our efforts on the scheduling methods optimization with the goal of very-large scale and reliable network lifetime estimation.


%\section*{Acknowledgement}
%Liam McNamara (SICS), Beshr Al Nahas (SICS).

\balance
\bibliographystyle{IEEEtran}
\bibliography{bib}

\end{document}