# Energy Efficient Sampling Policies for Edge Computing Feedback Systems

Vishnu Narayanan Moothedath, Jaya Prakash Champati, and James Gross Vishnu
Narayanan Moothedath and James Gross are with the Department of Intelligent
Systems, KTH Royal Institute of Technology, Malvinas Väg 10, Stockholm 11428,
Sweden. E-mail<EMAIL_ADDRESS>Jaya Prakash Champati is with the Edge
Networks Group, IMDEA Networks Institute, Avda. del Mar Mediterraneo 22, 28918
Leganes (Madrid), Spain. E-mail<EMAIL_ADDRESS>
###### Abstract

We study the problem of finding efficient sampling policies in an edge-based
feedback system, where sensor samples are offloaded to a back-end server that
processes them and generates feedback to a user. Sampling the system at
maximum frequency results in the detection of events of interest with minimum
delay but incurs higher energy costs due to the communication and processing
of redundant samples. On the other hand, lower sampling frequency results in
higher delay in detecting the event, thus increasing the idle energy usage and
degrading the quality of experience. We quantify this trade-off as a weighted
function between the number of samples and the sampling interval. We solve the
minimisation problem for exponential and Rayleigh distributions, for the
random time to the event of interest. We prove the convexity of the objective
functions by using novel techniques, which can be of independent interest
elsewhere. We argue that adding an initial offset to the periodic sampling can
further reduce the energy consumption and jointly compute the optimum offset
and sampling interval. We apply our framework to two practically relevant
applications and show energy savings of up to $36\%$ when compared to an
existing periodic scheme.

###### Index Terms:

Energy minimisation, optimal sampling, edge computing, feedback systems, event
detection, cyber physical systems, video analytics systems

##  1 Introduction

With the advent of next-generation mobile networks such as 5G Release 15 and
16, there is an increasing interest in realising various real-time services
and applications. Perhaps most prominently, this materialises with the Release
16 features of URLLC (ultra-reliable low latency communication) targeting sub-
millisecond end-to-end delays primarily for industrial automation
applications. However, in addition to these extreme use cases, a plethora of
new applications are arising that all process states of reality and accurately
provide feedback either to devices or humans. Examples of such feedback
systems with low latency requirements are human-in-the-loop applications like
augmented reality, wearable cognitive assistants (WCA), or ambient safety.
Also, in the domain of cyber-physical systems (CPS), such applications are
prominent, for example, in the context of automated video surveillance or
distributed control systems. All these applications have in common that
feedback depends on state capture and timely processing, whereas essential
state changes are random events and hence an efficient operation of the
application becomes a central aspect of the system. This is even more
emphasised by the recent trend to place most of the processing logic of such
feedback systems with edge computing facilities, leveraging supposedly
ubiquitous real-time compute capabilities with the additional costs of
offloading compute tasks (in terms of communication delays and energy
consumption).

In this paper, we study approaches that enable capturing the relevant system
changes in edge-based feedback systems while striking a balance with the total
energy consumption. We consider feedback systems that monitor a process (or
human activities) via sampling, while only reacting to a sub-set of samples,
referred to as essential events, that lead to a system change – for instance,
a new augmentation towards a human user, an alarm in a surveillance system, or
an actuation or fault detection in a general CPS set-up. After an essential
event is captured and processed (including the generation of feedback), the
feedback system transits to the next state where it starts monitoring for an
essential next event to happen. The trade-off that we study relates to the
strategy applied to sample the process. More frequent sampling leads to a
timely capture of the essential event. However, it also leads to the capture
of unimportant samples of the process, wasting system resources in terms of
energy, communication bandwidth, and computing cycles. We are interested in
mathematically characterising this trade-off between detection delay and
energy usage and studying the implied consequences in the system design.

###  1.1 Related Works

Some of the earliest ideas on detecting the relevant system changes (or
essential events) come from control systems with applications in manufacturing
and observable models [1]. The survey [2] looks at some important works that
focus on failure events in complex systems. This is viewed from a statistical
perspective in [3] and is later revisited in [4] where the authors look for
stochastic changes in the system with an aim of quickest detection. Moving on
to the recent research on edge computing and CPS, some important works use
data mining and post-processing to detect events from the collected data [5].
We, on the other hand, are interested in detecting live events and generating
corresponding feedback to dictate the process. Examples of such an event
detection occur in real-time video analytics systems which are explored
extensively in recent years from multiple perspectives [6, 7]. However, the
aspect of energy consumption is not considered in the above works. Instead of
using minimal energy, they look only at detecting the relevant system changes
as fast as possible.

Wireless video surveillance, where the video frames are captured by sensors
and are sent to the processing node over wireless sensor networks (WSN) is
studied in [8]. The authors discuss the challenges faced by these systems
including the energy consumption – that we are particularly interested in from
a general event detection perspective. The authors discuss some of the adopted
methods to reduce energy consumption. These methods include optimising sensor
topologies [9], optimising video coding and transmission techniques [10], and
forcing node cooperation between multiple sensors [11]. In a similar context
of object detection and tracking, [12] discusses the energy saving by sending
the camera to an idle state where the frames are dropped for a duration
determined adaptively based on the speed of the object. Energy-efficient
surveillance and tracking using a network of sensors are also discussed in
[13], where only a subset of the sensors are activated at any given time. A
different but widely studied method to save energy is offloading the sensor
data [14, 15]. The drawback of an increased latency compounded on a large
number of samples during an offloading is addressed (to a certain extent) by
making offloading decisions [16] for the samples. This includes binary
decisions [17, 18, 19, 20, 21, 22], partial offloading decisions [23, 24, 25],
and stochastic decisions [26].

###  1.2 Contributions

In this paper, we focus on detecting the essential events of an edge-based
feedback system in real-time in an energy-efficient manner. In contrast to all
the above-mentioned works, our approach minimises energy consumption by
reducing the amount of data generated by the sensors thereby reducing the
total amount of data in the communication and processing pipeline. While some
of the existing works reduce energy by lightly processing and filtering the
samples before transmitting, or taking a cluster wise sensing decision, we
look at statistically determining the optimum sampling or sensing time
instances. While the idea of offloading tends to concentrate on the sensor
side and take a hit at total energy consumption by shifting the energy usage
to the edge device, our work provides a framework for reducing the total
energy consumption in the system. To the best of our knowledge, our work is
the first attempt to find the energy-optimal sampling points of an edge-based
feedback system for capturing the relevant system changes.

For illustrating the performance of the proposed design, we focus on two
relevant and practical systems that are considered in the related works. The
first one is a general CPS that aims at fault detection. Such systems are
typically characterised by exponentially distributed inter-failure intervals,
a relatively small amount of data transfer, and a low-power communication
technology. A basic direction on how to approach the above-mentioned trade-off
for a CPS is given by the authors in [27]. The second system is a video
analytics system (VAS). The motivation for considering the VAS comes from a
WCA system, where a human task progress is monitored continuously for the
detection of the task completion. The task completion time comprises of
multiple system delays (communication, processing etc.) and a delay that is
tied to the response time and skill of the human user. Previous works on WCA
[28] and general distribution fitting indicates that this task completion time
can be modelled as a random variable following a Rayleigh distribution. Other
characteristics of a VAS are large data transfer and the requirement of a high
throughput communication technology, owing to the continuous sequence of video
frames that needs to be transmitted to the processing node.

Our key contributions are listed below.

  * •

We pose the problem to find the energy-minimising periodic sampling interval
of an edge-based feedback system as an optimisation problem. The convexity of
this problem is proved for certain distributions by developing a novel
approach that uses the Poisson sum formula and Fourier transforms – which can
be of independent academic interest elsewhere. The problem is solved using a
lightweight bisection algorithm that converges exponentially to the optimum.

  * •

We prove that adding an initial offset to the periodic sampling further
reduces the expected energy consumption when the TTE distribution is not
exponential. Thus we pose a more generic optimisation problem in two variables
and propose an algorithm to find a solution that achieves near-optimality.

  * •

Using simulations, we study the energy reduction on systems with a wide range
of parameterisations by considering the CPS and the VAS use-cases.
Particularly for the VAS, we show the inefficiency of systems used in practice
and the larger potential of energy optimisation where we obtain up to $40\%$
increase in battery life. One reason for this is the larger communication
content and power requirements for the VAS, which point to the increased
relevance of the proposed solution in these future systems. We also observe
that oversampling needs to be particularly avoided as it introduces a
substantial increase in energy usage.

The paper is organised as follows. In Section 2, we discuss the system model.
In Sections 3 and 4, we lay down the general solution approach and solutions
for exponential and Rayleigh distributed TTEs. We discuss the numerical
results in Section 5 and conclude in Section 6.

##  2 System Model and Problem Statement

Consider a feedback system consisting of a mobile terminal (simply terminal)
and a back-end server (simply back-end), that is designed to monitor a process
through sampling. The terminal captures samples that are sent to the back-end
for processing. Immediately after the occurrence of an essential event (simply
event), the process moves to an intermediate state where no more events are
expected. The next sample drawn at or after this transition point – referred
to as a successful sample – indicates the event detection at the back-end’s
processor, and causes feedback to the terminal. The reception of this feedback
triggers the start of a fresh monitoring cycle to detect the next event.
Within a monitoring cycle, the feedback is generated only to the successful
sample, and all other samples are discarded by the back-end. The time taken
from the start of a monitoring cycle to the event is termed as Time to event
(TTE), and the time between this event and the corresponding feedback is
termed as Time to feedback (TTF). We denote the TTE using the random variable
$\mathcal{T}$, and a value for $\mathcal{T}$ is denoted by $t$. The timing
diagram of the system is given in Fig. 1. Here we focus on modelling and
designing the monitoring cycle corresponding to a single event, and the
proposed design can be independently extended to all the (potentially
predetermined set of) events that the system is supposed to detect.

Figure 1: Timing diagram of an arbitrary monitoring cycle.

For example, in a CPS, the event might correspond to the detection of a system
failure. The feedback potentially triggers a reset and the terminal starts
monitoring for the next failure. In the VAS (or WCA) system studied in [29,
30], the user is assigned to complete a set of tasks and the events correspond
to the completion of each task. The terminal takes snapshots (video frames) of
the user activity using a camera and sends them to the back-end for image
processing.

The terminal can sample the process, transmit it to the back-end and can
receive feedback whenever available. The back-end on the other hand is capable
of receiving the sample, processing it and transmitting the feedback after an
essential event detection. At all other times, the terminal and back-end go to
their respective idle mode to save energy, and the power consumed while in
this mode is denoted by $P_{0}$. Though the back-end can possibly serve and
manage multiple terminals, we restrict our study to the back-end’s interaction
with a single terminal.

Sampling the system for detecting the event is governed by a set of sampling
policies ${\Pi}$. We consider sampling policies $\pi\in\Pi$ that sample the
system periodically with a sampling interval $T_{\text{s}}$, except for the
first sample, which is sampled after waiting for a duration $\delta\geq
T_{\text{s}}$. We refer to $\delta$ as offset. This offset takes care of a
minimum time threshold, sampling before which only adds to the energy wastage.
We elaborate this in detail in Section 4. Apart from the set of sampling
policies $\Pi$, we also consider a special case with $\delta=T_{\text{s}}$,
referred to as $\hat{\Pi}$. In other words, under $\Pi$ the samples are taken
at $t=kT_{\text{s}}+\delta,\;k\in\mathbb{N}$ whereas under $\hat{\Pi}$ the
samples are taken at $t=kT_{\text{s}},\;k\in\mathbb{N}^{+}$. While the optimum
policy under $\Pi$ comprises of an optimum sampling interval
$T_{\text{s}}^{*}$ and an optimum phase $\delta^{*}$, the optimum policy under
the analytically simpler subset $\hat{\Pi}$ corresponds to (only) an optimum
sampling interval $T_{\text{s}}^{\\#}$. We use the notation $(\cdot)^{\\#}$
instead of $(\cdot)^{*}$ to have a clear distinction between the underlying
set of policies. Following the same conventions, we refer to these optimum
policies as $\pi^{*}$ and $\pi^{\\#}$, respectively.

The number of samples taken is denoted by a random variable $\mathcal{S}$, and
a value for $\mathcal{S}$ is denoted by $s$. This includes both the discarded
samples taken during TTE as well as the final sample that leads to detecting
the event. This TTF consists of a (potential) random lag $\mathcal{W}$ until
the next sample is drawn as well as a deterministic processing and two-way
communication delays. The random lag $\mathcal{W}$ is referred to as wait and
$w$ denotes a value of $\mathcal{W}$. Note that only the processing and
communication delay corresponding to the final sample contributes to the delay
after the wait. In this work, we assume that the total power consumption
during transmission and reception is the same at both the terminal and the
back-end and we refer to it simply as communication power denoted by
$P_{\text{c}}$, which is typically much larger than the idle power $P_{0}$. We
also assume that the communication delay in either direction is
$\tau_{\text{c}}$ and the processing time of the successful sample be
$\tau_{\text{s}}$.

When not performing a transmission, reception, or processing, both the
terminal and the back-end enter idle mode, which incurs an idle power
consumption. The total time within a state, during which the terminal or back-
end is in an idle mode is referred to as the idle time and is denoted by the
random variable $\mathcal{T}_{0}$. The notations used and their meanings are
reiterated in TABLE I for readability.

$\mathcal{S}$ | number of samples | $\mathcal{W}$ | wait time
---|---|---|---
$\mathcal{T}$ | time to event (TTE) | $\mathcal{T}_{0}$ | idle time
${F}_{\mathcal{X}}(\cdot)$ | CDF $X$ | $\bar{F}_{\mathcal{X}}(\cdot)$ | CCDF of $\mathcal{X}$
$T_{\text{s}}$ | sampling interval | $\delta$ | offset
$\tau_{\text{c}}$ | communication delay | $\tau_{\text{s}}$ | processing delay
$P_{\text{c}}$ | communication power | $P_{0}$ | idle power
$\mathrm{E}$ | energy | $\mathcal{E}$ | energy penalty
$\mathbb{N}$ | {0,1,2,…} | $\mathbb{N}^{+}$ | {1,2,3,…}
TABLE I: Table of notations.

###  2.1 Problem Statement

An ideal sampling policy should sample the system immediately after the event
so that the wait is zero and the number of samples required per event is
exactly 1. However, such a sampling policy is unattainable given the fact the
TTE is randomly distributed. As a result, we have to settle with a sampling
policy that simultaneously reduces the expected wait and expected number of
discarded samples to yield the maximum attainable benefit. Note that this is
not straightforward as the wait time and the number of samples shows opposite
behaviour with a change in sampling frequency. For instance, an aggressive
sampling reduces the wait time, but it also increases the number of samples.
In this work, we use energy as a metric to quantify this opposing behaviour.
Each sample warrants energy in terms of communication and processing; and
during the wait $w$, energy is expended as governed by the idle power. It is
this optimal trade-off of energy usage between the sampling frequency and the
number of samples that we seek to quantify.

Note that the fundamental random variable here is the TTE $\mathcal{T}$ and
the other random variables – $\mathcal{S},\mathcal{W}$ and $\mathcal{T}_{0}$ –
are derived from $\mathcal{T}$ through the selection of the optimization
variables $T_{\text{s}}$ and $\delta$. We can compute the idle time denoted by
$\mathcal{T}_{0}$ in terms of other parameters as follows:

$\displaystyle\mathcal{T}_{0}$ $\displaystyle\ =\ $
$\displaystyle\mathcal{T}+\mathcal{W}+\tau_{\text{s}}-(\mathcal{S}-1)\tau_{\text{c}}\;.$
(1)

Let $\mathrm{E}$ be the energy required for detecting one event.

$\displaystyle\mathrm{E}$
$\displaystyle=(\mathcal{S}+1)\tau_{\text{c}}P_{\text{c}}+\mathcal{T}_{0}P_{0}$
$\displaystyle=\mathcal{S}\tau_{\text{c}}(P_{\text{c}}-P_{0})+\mathcal{W}P_{0}+(\mathcal{T}+\tau_{\text{c}}+\tau_{\text{s}})P_{0}+\tau_{\text{c}}P_{\text{c}}\;.$
(2)

We aim to minimise the expected energy for a given TTE statistics. In (2), the
terms except those containing the number of samples $\mathcal{S}$ or the wait
$\mathcal{W}$ are either constants or have constant expectations for a fixed
distribution of $\mathcal{T}$. Hence these terms are irrelevant in the
optimisation where we minimise the expected energy. Let
$\mathcal{E}(T_{\text{s}},\delta)$ be the component of the total energy which
is relevant for the optimisation and let us call it energy penalty. We obtain

$\displaystyle\mathcal{E}(T_{\text{s}},\delta)=\alpha\mathbb{E}[\mathcal{S}]+\beta\mathbb{E}[\mathcal{W}]\;,$
(3) where we use the constants $\alpha$ and $\beta$ for mathematical
tractability in the upcoming sections. Here,
$\displaystyle\alpha=\tau_{\text{c}}(P_{\text{c}}-P_{0})\;\text{ and
}\;\beta=P_{0}\;.$ (4)

In (3), $\beta\,\mathbb{E}[\mathcal{W}]$ corresponds to the additional energy
expended for waiting, and $\alpha$ represents the energy wasted per discarded
sample due to the additional communication and processing. The minimum values
of $\mathcal{E}$ under the policies $\Pi$ and $\hat{\Pi}$ are referred to as
$\mathcal{E}^{*}$ and $\mathcal{E}^{\\#}$, respectively. That is

$\mathcal{E}^{*}=\mathcal{E}(T_{\text{s}}^{*},\delta^{*})\text{ and
}{\mathcal{E}}^{\\#}=\mathcal{E}(T_{\text{s}}^{\\#},T_{\text{s}}^{\\#})\;.$

In what follows, we study the general optimisation problems $\mathcal{P}$ and
$\hat{\mathcal{P}}$ under the set of sampling policies ${\Pi}$ and
$\hat{\Pi}$, respectively. These optimisation problems are defined as follows:

$\displaystyle\begin{split}\mathcal{P}:&\;\;\pi^{*}=\\{T_{\text{s}}^{*},\delta^{*}\\}=\;\underset{\\{T_{\text{s}},\delta\\}}{\text{arg\,min}}\
\mathcal{E}(T_{\text{s}},\delta)\\\
\hat{\mathcal{P}}:&\;\;\pi^{\\#}=\\{T_{\text{s}}^{\\#}\\}=\;\underset{T_{\text{s}}}{\text{arg\,min}}\
\mathcal{E}(T_{\text{s}},T_{\text{s}})\;,\end{split}$ (5)

where $\pi^{*}$ and $\pi^{\\#}$ are the optimum policies for $\mathcal{P}$ and
$\hat{\mathcal{P}}$, respectively. We will solve these problems for the CPS
and the VAS where the TTEs follow exponential and Rayleigh distributions,
respectively.

##  3 Solution to the Problem $\hat{\mathcal{P}}$

Being the simpler one, we start with the optimisation problem
$\hat{\mathcal{P}}$ in this section and find the optimum periodic sampling
interval by minimising $\mathcal{E}(T_{\text{s}},\delta)$ given in (3).
Throughout this section, we will drop the redundant second argument
$\delta\,(=\\!T_{\text{s}}\text{ under }\hat{\mathcal{P}})$ from the energy
penalty for simplicity. As the solution is specific to the distribution of
$\mathcal{T}$, we will first lay down the solution approach to find the energy
penalty for any general distribution and later apply this to particular
distributions.

###  3.1 General TTE Distribution

Here, we derive the expressions for the expected number of samples and the
expected wait time under a general TTE distribution, which together
constitutes $\mathcal{E}(T_{\text{s}})$.

####  3.1.1 Expected number of samples

Recall that $\mathcal{S}$ is the random number of samples taken for detecting
an event. We have

$\displaystyle\mathbb{P}(\mathcal{S}=k)$ $\displaystyle\ =\ $
$\displaystyle\mathbb{P}\big{(}\left\lceil\nicefrac{{t}}{{T_{\text{s}}}}\right\rceil=k\big{)},\;\forall
k\geq 1$ $\displaystyle\ =\ $
$\displaystyle\mathbb{P}(k-1<\nicefrac{{t}}{{T_{\text{s}}}}\leq k)$
$\displaystyle\ =\ $ $\displaystyle
F_{\mathcal{T}}\big{(}kT_{\text{s}}\big{)}-F_{\mathcal{T}}\big{(}(k-1)T_{\text{s}}\big{)}$
$\displaystyle\Rightarrow\mathbb{E}[\mathcal{S}]$ $\displaystyle\ =\ $
$\displaystyle\sum_{k=1}^{\infty}k\Big{(}F_{\mathcal{T}}\big{(}kT_{\text{s}}\big{)}-F_{\mathcal{T}}\big{(}(k-1)T_{\text{s}}\big{)}\Big{)}\;.$
(6)

####  3.1.2 Expected wait time

Recall that w denotes a value of the random wait time $\mathcal{W}$. We have a
fixed set of sampling instances governed by $T_{\text{s}}$. The CDF of the
wait $F_{\mathcal{W}}(w)$ can be obtained by taking the probability of the TTE
to fall at most $w$ short of any sampling instance. Even though the TTEs are
finite in practice, we consider they can be arbitrarily large for the sake of
generalised analysis. As a result, a successful sample can be located anywhere
from the first sampling instance to possibly infinity. For real systems,
however, there is an upper bound for the TTE (preemption or otherwise) and it
implies that the corresponding probability is zero beyond this point. We can
compute the CDF of $\mathcal{W}$ as follows.

$\displaystyle F_{\mathcal{W}}(w)$ $\displaystyle\ =\ $
$\displaystyle\sum_{k=1}^{\infty}\mathbb{P}\big{(}kT_{\text{s}}-w<t\leq
kT_{\text{s}}\big{)}$ $\displaystyle\ =\ $
$\displaystyle\sum_{k=1}^{\infty}\big{(}F_{\mathcal{T}}(kT_{\text{s}})-F_{\mathcal{T}}(kT_{\text{s}}-w)\big{)}\;.$
(7) Since $\mathcal{W}$ is a non-negative random variable, we have
$\displaystyle\mathbb{E}[\mathcal{W}]$ $\displaystyle\ =\ $
$\displaystyle{\int_{0}^{\infty}}\big{(}1-F_{\mathcal{W}}(w)\big{)}\,\mathrm{d}w$
$\displaystyle\ =\ $
$\displaystyle\int_{0}^{T_{\text{s}}}\Big{(}1-\sum_{k=1}^{\infty}\big{(}F_{\mathcal{T}}(kT_{\text{s}})-F_{\mathcal{T}}(kT_{\text{s}}-w)\big{)}\Big{)}\,\mathrm{d}w\;.$
Here, integral limits and infinite sum are finite, and the summand is non-
negative. Thus $\displaystyle\mathbb{E}[\mathcal{W}]$ $\displaystyle\ =\ $
$\displaystyle
T_{\text{s}}-\sum_{k=1}^{\infty}\int_{0}^{T_{\text{s}}}\big{(}F_{\mathcal{T}}(kT_{\text{s}})-F_{\mathcal{T}}(kT_{\text{s}}-w)\big{)}\,\mathrm{d}w\;.$
(8)

Using (6) and (8), we can calculate the energy penalty given in (3). Clearly,
the expected number of samples decrease with an increase in $T_{\text{s}}$. We
can see that the summation containing the integral in the expected wait time
expression also decrease with an increase in $T_{\text{s}}$, thus increasing
$\mathbb{E}[\mathcal{W}]$. This opposing behaviour of the two penalties result
in a minima in their weighted sum $\mathcal{E}(T_{\text{s}})$ (with weights
$\alpha$ and $\beta$) at the optimum sampling interval $T_{\text{s}}^{\\#}$.
Depending on the distribution of $\mathcal{T}$ and the resultant energy
penalty, $T_{\text{s}}^{\\#}$ can be computed using known optimisation
techniques or numerical solvers [31].

###  3.2 Exponentially Distributed TTE

In this subsection, we look into a feedback system where the TTEs are
exponentially distributed. This part of the work describing about the solution
of $\hat{\mathcal{P}}$ under an exponentially distributed TTE was published
earlier by the authors in [27].

######  Lemma 1.

For exponentially distributed TTE with mean $\nicefrac{{1}}{{\lambda}}$, the
energy penalty $\mathcal{E}(T_{\text{s}})$ imparted by a periodic sampling
policy with a period $T_{\text{s}}$ is given by

$\mathcal{E}(T_{\text{s}})=\dfrac{\alpha\lambda+\beta\big{(}e^{-\lambda
T_{\text{s}}}+\lambda T_{\text{s}}-1\big{)}}{\lambda(1-e^{-\lambda
T_{\text{s}}})}\;.$ (9)

###### Proof.

Given that the TTEs are exponentially distributed with rate parameter
$\lambda$, we have $F_{\mathcal{T}}(t)=1-e^{-\lambda t}\;$. From (6), the
expected number of samples can be computed as

$\displaystyle\mathbb{E}[\mathcal{S}]$ $\displaystyle\ =\ $
$\displaystyle\dfrac{1}{1-e^{-\lambda T_{\text{s}}}}.$ (10) Substituting
$F_{\mathcal{T}}(t)$ in (7) $\displaystyle F_{\mathcal{W}}(w)$ $\displaystyle\
=\ $ $\displaystyle\sum_{k=1}^{\infty}\big{(}(1-e^{-\lambda
kT_{\text{s}}})-(1-e^{-\lambda(kT_{\text{s}}-w)})\big{)}$ $\displaystyle\ =\ $
$\displaystyle\sum_{k=1}^{\infty}e^{-\lambda kT_{\text{s}}}(e^{\lambda
w}-1)=\dfrac{e^{\lambda w}-1}{e^{\lambda T_{\text{s}}}-1}$
$\displaystyle\Rightarrow f_{\mathcal{W}}(w)$ $\displaystyle\ =\ $
$\displaystyle\dfrac{\lambda e^{\lambda w}}{e^{\lambda T_{\text{s}}}-1}$
$\displaystyle\Rightarrow\mathbb{E}[\mathcal{W}]$ $\displaystyle\ =\ $
$\displaystyle\dfrac{e^{-\lambda T_{\text{s}}}+\lambda
T_{\text{s}}-1}{\lambda(1-e^{-\lambda T_{\text{s}}})}\;.$ (11) Substituting
(10) and (11) in (5), we get the energy penalty $\mathcal{E}(T_{\text{s}})$
for using a particular sampling interval $T_{\text{s}}$ as
$\displaystyle\mathcal{E}(T_{\text{s}})$ $\displaystyle\ =\ $
$\displaystyle\dfrac{\alpha\lambda+\beta\big{(}e^{-\lambda
T_{\text{s}}}+\lambda T_{\text{s}}-1\big{)}}{\lambda(1-e^{-\lambda
T_{\text{s}}})}\;.$

∎

######  Lemma 2.

The energy penalty $\mathcal{E}(T_{\text{s}})$ is convex in $T_{\text{s}}\;$.

###### Proof.

In the following, we drop the argument $T_{\text{s}}$ from
$\mathcal{E}(T_{\text{s}})$ for simplicity in presentation. Note from (4) that
$\beta>0$.

$\displaystyle\mathcal{E}^{\prime}\ :=\ $
$\displaystyle\dfrac{\mathop{}\mathrm{d}\mathcal{E}}{\mathop{}\mathrm{d}T_{\text{s}}}\
=\ $ $\displaystyle\dfrac{\beta\big{(}1-e^{-\lambda T_{\text{s}}}(\lambda
T_{\text{s}}+\tfrac{\alpha}{\beta}\lambda+1)\big{)}}{(1-e^{-\lambda
T_{\text{s}}})^{2}}\;,$ $\displaystyle\mathcal{E}^{\prime\prime}\ :=\ $
$\displaystyle\dfrac{\mathop{}\mathrm{d}^{2}\mathcal{E}}{\mathop{}\mathrm{d}T_{\text{s}}^{2}}\
=\ $ $\displaystyle\dfrac{\beta\lambda e^{-\lambda
T_{\text{s}}}\big{(}(1+e^{-\lambda T_{\text{s}}})(\lambda
T_{\text{s}}+\tfrac{\alpha}{\beta}\lambda)+2e^{-\lambda
T_{\text{s}}}-2\big{)}}{(1-e^{-\lambda T_{\text{s}}})^{3}}\;.$
$\displaystyle\mathcal{E}^{\prime\prime}\ \geq 0\Rightarrow\ $
$\displaystyle\tilde{\mathcal{E}}\ $ $\displaystyle:=\ $
$\displaystyle(1+e^{-\lambda T_{\text{s}}})(\lambda
T_{\text{s}}+\tfrac{\alpha}{\beta}\lambda)+2e^{-\lambda T_{\text{s}}}-2\geq
0\;,$ $\displaystyle\tilde{\mathcal{E}}^{\prime}\ $ $\displaystyle:=\ $
$\displaystyle\dfrac{\mathop{}\mathrm{d}\tilde{\mathcal{E}}}{\mathop{}\mathrm{d}T_{\text{s}}}\
=\ \lambda(1-e^{-\lambda T_{\text{s}}}(\lambda
T_{\text{s}}+\tfrac{\alpha}{\beta}\lambda+1))\;,$
$\displaystyle\tilde{\mathcal{E}}^{\prime\prime}\ $ $\displaystyle:=\ $
$\displaystyle\dfrac{\mathop{}\mathrm{d}^{2}\tilde{\mathcal{E}}}{\mathop{}\mathrm{d}T_{\text{s}}^{2}}\
=\ \lambda^{2}e^{-\lambda T_{\text{s}}}(\lambda
T_{\text{s}}+\tfrac{\alpha}{\beta}\lambda)\;.$

From the above expressions, since $\tilde{\mathcal{E}}^{\prime\prime}\geq 0\
\forall T_{\text{s}}$, we can conclude that $\tilde{\mathcal{E}}$ is globally
convex and any infimum point is its minimum. To find this infimum:

$\displaystyle\tilde{\mathcal{E}}^{\prime}=0$ $\displaystyle\Rightarrow\lambda
T_{\text{s}}+\tfrac{\alpha}{\beta}\lambda=e^{\lambda T_{\text{s}}}-1\;.$

Substituting in the above expression for $\tilde{\mathcal{E}}$, we obtain

$\displaystyle\underset{T_{\text{s}}>0}{\min}\\{\tilde{\mathcal{E}}\\}=$
$\displaystyle(1+e^{-\lambda T_{\text{s}}})(e^{\lambda
T_{\text{s}}}-1)+2e^{-\lambda T_{\text{s}}}-2$ $\displaystyle=$ $\displaystyle
e^{\lambda T_{\text{s}}}+e^{-\lambda T_{\text{s}}}-2$ $\displaystyle\geq$
$\displaystyle 0\ \forall T_{\text{s}}>0$
$\displaystyle\Rightarrow\tilde{\mathcal{E}}\geq$ $\displaystyle 0\ \forall
T_{\text{s}}>0$ $\displaystyle\Rightarrow\mathcal{E}^{\prime\prime}\geq$
$\displaystyle 0\ \forall T_{\text{s}}>0\;.$

As $T_{\text{s}}$ is non-negative, the energy penalty $\mathcal{E}$ is convex.
∎

######  Proposition 1.

The optimum sampling interval $T_{\text{s}}^{\\#}$ under an exponentially
distributed TTE with mean $\nicefrac{{1}}{{\lambda}}$ is the solution to the
expression

$e^{\lambda T_{\text{s}}^{\\#}}-\lambda
T_{\text{s}}^{\\#}=\tfrac{\alpha}{\beta}\lambda+1\;.$ (12)

###### Proof.

The proof follows from Lemma 1 and Lemma 2. We can find the optimum by
equating the first derivative of total penalty to zero.

$\displaystyle\dfrac{\mathop{}\mathrm{d}\mathcal{E}(T_{\text{s}})}{\mathop{}\mathrm{d}T_{\text{s}}}=0$
$\displaystyle\Rightarrow 1-e^{-\lambda T_{\text{s}}}(\lambda
T_{\text{s}}+\tfrac{\alpha}{\beta}\lambda+1)=0$ $\displaystyle\Rightarrow
e^{\lambda T_{\text{s}}}-\lambda T_{\text{s}}$
$\displaystyle=\tfrac{\alpha}{\beta}\lambda+1\;.$

∎

We know that $e^{x}-x$ is a monotonically increasing convex function in $x$
with $e^{x}-x\geq 1,\ \forall x\geq 0$. Hence, this single variable expression
can be solved using well-known numerical solvers.

Though the value of energy penalty depends on the values of $\beta$ and
$\alpha$, the optimum sampling interval $T_{\text{s}}^{\\#}$ only depends on
their ratio. Furthermore, from (4), it can be seen that this ratio
$\nicefrac{{\beta}}{{\alpha}}$ does not depend on the individual power figures
but only on the percentage additional power necessary for communication or
processing when compared to their respective idle power requirement. In other
words, for fixed $\lambda$, $\nicefrac{{\beta}}{{\alpha}}$ and thus the
optimum sampling interval is a function of only $\tau_{\text{c}}$ and
$\nicefrac{{P_{\text{c}}}}{{P_{0}}}$.

###  3.3 Rayleigh Distributed TTE

We will now consider a Rayleigh distributed TTE with mean
$\mu\\!=\\!\sigma\sqrt{\tfrac{\pi}{2}}$ and CDF
$F_{\mathcal{T}}(t)\\!=\\!1-e^{-t^{2}/2\sigma^{2}}$; where $\sigma$ is the
scale parameter.

######  Lemma 3.

The expected number of samples is given by

$\mathbb{E}[\mathcal{S}]=\sum_{k=0}^{\infty}e^{-k^{2}T_{\text{s}}^{2}/2\sigma^{2}}\;.$
(13)

###### Proof.

Substituting the Rayleigh CDF in (6) gives

$\displaystyle\mathbb{E}[\mathcal{S}]$ $\displaystyle\ =\ $
$\displaystyle\sum_{k=1}^{\infty}k\bigg{(}e^{-(k-1)^{2}T_{\text{s}}^{2}/2\sigma^{2}}-e^{-k^{2}T_{\text{s}}^{2}/2\sigma^{2}}\bigg{)}\;.$

Since the positive and negative terms converges individually to a finite
value, we can rearrange the terms to complete the proof. ∎

######  Lemma 4.

The expected wait time is given by

$\mathbb{E}[\mathcal{W}]=T_{\text{s}}\sum_{k=0}^{\infty}e^{-(kT_{\text{s}})^{2}/2\sigma^{2}}-\sigma\sqrt{\tfrac{\pi}{2}}\;.$
(14)

###### Proof.

Substituting the Rayleigh CDF in (8) gives

$\displaystyle\mathbb{E}[\mathcal{W}]$ $\displaystyle\ =\ $ $\displaystyle
T_{\text{s}}-\sum_{k=1}^{\infty}\int_{0}^{T_{\text{s}}}\big{(}e^{\nicefrac{{-(kT_{\text{s}}-w)^{2}}}{{2\sigma^{2}}}}-e^{\nicefrac{{-(kT_{\text{s}})^{2}}}{{2\sigma^{2}}}}\big{)}\,\mathrm{d}w$
$\displaystyle\ =\ $ $\displaystyle
T_{\text{s}}+T_{\text{s}}\sum_{k=1}^{\infty}e^{-(kT_{\text{s}})^{2}/2\sigma^{2}}-\sum_{k=1}^{\infty}\int_{0}^{T_{\text{s}}}e^{\nicefrac{{-(kT_{\text{s}}-w)^{2}}}{{2\sigma^{2}}}}\,\mathrm{d}w$
$\displaystyle\ =\ $ $\displaystyle
T_{\text{s}}\sum_{k=0}^{\infty}e^{-(kT_{\text{s}})^{2}/2\sigma^{2}}-\sum_{k=1}^{\infty}\int_{0}^{T_{\text{s}}}e^{\nicefrac{{-(kT_{\text{s}}-w)^{2}}}{{2\sigma^{2}}}}\,\mathrm{d}w\;.$

Let $\text{{erf}}(x)$ be the error function defined as

$\text{{erf}}(x)=\dfrac{2}{\sqrt{\pi}}\int_{0}^{x}e^{-t^{2}}\,\mathop{}\mathrm{d}t\;.$

Also, let $\text{{erfc}}(x)=1-\text{{erf}}(x)$ be the complimentary error
function. Substituting $\dfrac{(kT_{\text{s}}-w)}{\sigma\sqrt{2}}=t$, we get

$\displaystyle\mathbb{E}[\mathcal{W}]=T_{\text{s}}\sum_{k=0}^{\infty}e^{-(kT_{\text{s}})^{2}/2\sigma^{2}}-\sigma\sqrt{2}\sum_{k=1}^{\infty}{\int_{\nicefrac{{(k-1)T_{\text{s}}}}{{\sigma\sqrt{2}}}}^{\nicefrac{{kT_{\text{s}}}}{{\sigma\sqrt{2}}}}}e^{-t^{2}}\,\mathop{}\mathrm{d}t$
$\displaystyle\ =\ $ $\displaystyle
T_{\text{s}}\sum_{k=0}^{\infty}e^{-(kT_{\text{s}})^{2}/2\sigma^{2}}-\sigma\sqrt{\tfrac{\pi}{2}}\sum_{k=1}^{\infty}\Big{(}\text{{erf}}\big{(}{\tfrac{kT_{\text{s}}}{\sigma\sqrt{2}}}\big{)}-\text{{erf}}\big{(}\tfrac{(k-1)T_{\text{s}}}{\sigma\sqrt{2}}\big{)}\Big{)}$
$\displaystyle\ =\ $ $\displaystyle
T_{\text{s}}\sum_{k=0}^{\infty}e^{-(kT_{\text{s}})^{2}/2\sigma^{2}}-\sigma\sqrt{\tfrac{\pi}{2}}\sum_{k=1}^{\infty}\Big{(}\text{{erfc}}\big{(}\tfrac{(k-1)T_{\text{s}}}{\sigma\sqrt{2}}\big{)}-\text{{erfc}}\big{(}{\tfrac{kT_{\text{s}}}{\sigma\sqrt{2}}}\big{)}\Big{)}$
$\displaystyle\ =\ $ $\displaystyle
T_{\text{s}}\sum_{k=0}^{\infty}e^{-(kT_{\text{s}})^{2}/2\sigma^{2}}-\sigma\sqrt{\tfrac{\pi}{2}}\Big{(}\text{{erfc}}(0)-\text{{erfc}}(\infty)\Big{)}$
$\displaystyle\ =\ $ $\displaystyle
T_{\text{s}}\sum_{k=0}^{\infty}e^{-(kT_{\text{s}})^{2}/2\sigma^{2}}-\sigma\sqrt{\tfrac{\pi}{2}}\;.$

∎

Substituting (14) and (13) in (5), we obtain the total energy penalty, given
by

$\displaystyle\mathcal{E}(T_{\text{s}})$ $\displaystyle\ =\ $
$\displaystyle\alpha\sum_{k=0}^{\infty}e^{-k^{2}T_{\text{s}}^{2}/2\sigma^{2}}+\beta\Big{(}T_{\text{s}}\sum_{k=0}^{\infty}e^{-(kT_{\text{s}})^{2}/2\sigma^{2}}-\sigma\sqrt{\tfrac{\pi}{2}}\Big{)}$
$\displaystyle\ =\ $ $\displaystyle(\alpha+\beta
T_{\text{s}})\sum_{k=0}^{\infty}e^{-k^{2}T_{\text{s}}^{2}/2\sigma^{2}}-\beta\sigma\sqrt{\tfrac{\pi}{2}}\;.$
(15)

Note that this energy penalty can be expressed using the Jacobi third theta
function $\theta_{3}(z,q)$ given by [32]

$\theta_{3}(z,q)=\sum_{n=-\infty}^{\infty}q^{n^{2}}e^{2niz}\;.$ (16)

Although the Jacobi theta functions do not have a closed-form solution, it is
finite and can be computed numerically or from tables. If required by the
numerical solvers, this infinite sum can be approximated to a finite sum with
a sufficiently large number of terms.

In what follows, we prove the convexity of $\mathcal{E}(T_{\text{s}})$. Note
that it involves a sum of infinite terms, and one can show that some of those
terms are non-convex. Therefore, using typical methods to prove convexity is
not applicable. Instead, we use a novel approach that involves a
transformation of the infinite sum using the Poisson sum formula, which can be
of independent interest in proving convexity for a sum of infinite terms, in
general.

######  Lemma 5.

Let $f(k,t)=e^{-k^{2}t^{2}/2\sigma^{2}}$. Then for $t\in(0,\infty)$,

$\sum\limits_{k=0}^{\infty}f(k,t)=\sqrt{2\pi}\>\dfrac{\sigma}{t}\sum\limits_{k=0}^{\infty}f(k,\tfrac{2\pi\sigma^{2}}{t})\;.$

###### Proof.

According to the Poisson sum formula, periodic summation of an aperiodic
function is equal to the periodic summation of its Fourier transform. That is,
for the given function $f(k,t)$

$\displaystyle\sum\limits_{k=-\infty}^{\infty}f(k,t)$
$\displaystyle=\sum\limits_{n=-\infty}^{\infty}\int_{-\infty}^{\infty}f(x,t)e^{-2\pi
inx}\,\mathop{}\mathrm{d}x$
$\displaystyle=\sum\limits_{n=-\infty}^{\infty}\int_{-\infty}^{\infty}e^{-x^{2}t^{2}/2\sigma^{2}}e^{-2\pi
inx}\,\mathop{}\mathrm{d}x$
$\displaystyle=\sqrt{2\pi}\>\dfrac{\sigma}{t}\sum\limits_{n=-\infty}^{\infty}e^{-2\pi^{2}n^{2}\sigma^{2}/t^{2}}$
$\displaystyle\Rightarrow\sum\limits_{k=-\infty}^{\infty}f(k,t)$
$\displaystyle=\sqrt{2\pi}\>\dfrac{\sigma}{t}\sum\limits_{k=-\infty}^{\infty}f(k,\tfrac{2\pi\sigma^{2}}{t})\;.$
Since $f(k,t)$ is an even function of $k$, we get
$\displaystyle\sum\limits_{k=0}^{\infty}f(k,t)$
$\displaystyle=\sqrt{2\pi}\>\dfrac{\sigma}{t}\sum\limits_{k=0}^{\infty}f(k,\tfrac{2\pi\sigma^{2}}{t})\;.$

∎

######  Lemma 6.

The function $f(t)=\sum_{k=0}^{\infty}f(k,t)$ is convex in $t\;$.

###### Proof.

We prove the convexity using the second derivative test. Since the function
sequence converges, it is sufficient to prove that the terms inside the
summation are independently convex. For this, we make use of the function and
its alternate expression given by Lemma 5.

$\displaystyle f(t)$
$\displaystyle=1+\sum\limits_{k=1}^{\infty}e^{-k^{2}t^{2}/2\sigma^{2}}$
$\displaystyle\Rightarrow f^{\prime\prime}(t)$
$\displaystyle=\sum\limits_{k=1}^{\infty}\dfrac{k^{2}}{\sigma^{4}}(k^{2}t^{2}-\sigma^{2})e^{-k^{2}t^{2}/2\sigma^{2}}$
$\displaystyle\geq 0\Leftarrow t\geq\dfrac{\sigma}{k}\quad,\forall k\geq 1\;.$
$\displaystyle\text{Therefore, $f(t)$ is convex if }t\geq\sigma\;.$ (17) Now
using Lemma 5, we get $\displaystyle f(t)$
$\displaystyle=\sqrt{2\pi}\>\dfrac{\sigma}{t}\Big{(}1+\sum\limits_{k=0}^{\infty}e^{-2\pi^{2}k^{2}\sigma^{2}/t^{2}}\Big{)}$
$\displaystyle\Rightarrow f^{\prime\prime}(t)$
$\displaystyle=2\sqrt{2\pi}\>\dfrac{\sigma}{t^{3}}\Big{(}1+\dfrac{1}{x^{4}}\big{(}x^{4}-10\pi^{2}k^{2}\sigma^{2}x^{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad+8\pi^{4}k^{4}\sigma^{4}\big{)}e^{-2\pi^{2}k^{2}\sigma^{2}/t^{2}}\Big{)}$
$\displaystyle\geq 0\Leftarrow
t\notin\Big{(}\pi\sigma\sqrt{5-\sqrt{17}}k,\,\pi\sigma\sqrt{5+\sqrt{17}}k\Big{)},\,\forall
k\geq 1\;.$ $\displaystyle\text{Therefore, $f(t)$ is convex if }t\leq
2.9\,\sigma\;.$ (18)

The proof is complete by combining the conditional convexity of $f(t)$ given
in (17) and (18). ∎

######  Lemma 7.

The function $g(t)=tf(t)$ is convex in $t$ .

###### Proof.

We prove the convexity in a way similar to Lemma 6.

$\displaystyle f(t)$
$\displaystyle=t\Big{(}1+\sum\limits_{k=1}^{\infty}e^{-k^{2}t^{2}/2\sigma^{2}}\Big{)}$
$\displaystyle\Rightarrow f^{\prime\prime}(t)$
$\displaystyle=\sum\limits_{k=1}^{\infty}\dfrac{k^{2}t}{\sigma^{4}}(k^{2}t^{2}-3\sigma^{2})e^{-k^{2}t^{2}/2\sigma^{2}}$
$\displaystyle\geq 0\Leftarrow t\geq\sqrt{3}\,\dfrac{\sigma}{k}\quad,\forall
k\geq 1\;.$ $\displaystyle\text{Therefore, $f(t)$ is convex if }t\geq
1.74\,\sigma\;.$ (19) Now using Lemma 5, we get $\displaystyle f(t)$
$\displaystyle=\sqrt{2\pi}\,\sigma\Big{(}1+\sum\limits_{k=0}^{\infty}e^{-2\pi^{2}k^{2}\sigma^{2}/t^{2}}\Big{)}$
$\displaystyle\Rightarrow f^{\prime\prime}(t)$
$\displaystyle=\dfrac{4\sqrt{2\pi^{5}}\,k^{2}\sigma^{3}}{t^{6}}\big{(}4\pi^{2}k^{2}\sigma^{2}-3t^{2}\big{)}e^{-2\pi^{2}k^{2}\sigma^{2}/t^{2}}$
$\displaystyle\geq 0\Leftarrow t\leq\dfrac{2\pi\sigma}{\sqrt{3}}\cdot
k\quad,\forall k\geq 1\;.$ $\displaystyle\text{Therefore, $f(t)$ is convex if
}t\leq 3.6\,\sigma\;.$ (20)

The proof is complete by combining the conditional convexity of $f(t)$ given
in (19) and (20). ∎

######  Proposition 2.

The energy penalty $\mathcal{E}(T_{\text{s}})$ is convex in $T_{\text{s}}\;$.

###### Proof.

The proof is straightforward from Lemma 6 and 7. ∎

With the convexity in hand, we can use known optimisation techniques[31] to
solve $\hat{\mathcal{P}}$. Later in Section 5, we will use a simple bisection
algorithm for this optimisation.

##  4 Solution to the Problem $\mathcal{P}$

In this section, we consider the optimisation problem $\mathcal{P}$ and find
the optimal sampling interval and offset $\\{T_{\text{s}}^{*},\delta^{*}\\}$.
Before going into the details, it is worth mentioning the motivation behind
the introduction of the offset $\delta$ to the model. In practice, there is a
minimum time threshold before which the event does not occur. For example, in
a WCA, a human user takes a strictly non-zero minimum amount of time to finish
a task and sampling before this minimum threshold simply adds to the energy
wastage. The addition of an offset to the policy mitigates this energy wastage
by not allowing the first sample to fall before a given time. However, this
threshold is not necessary for benefiting from the offset. Even in the absence
of a threshold, an offset in sampling is particularly useful in situations
where the TTE distribution has a small variance and/or large mode. Here, the
probability of the event occurring before the first sample is small enough so
that the expected energy saving in delaying the sampling outweighs the
expected cost of the encountered wait due to a (potential) event. As a result,
the optimum value of an offset is always greater than or equal to the minimum
threshold.

###  4.1 General TTE Distribution

As in the earlier section, we start by assuming a general TTE distribution and
later extend it to particular distributions.

####  4.1.1 Expected number of samples

The probability that the number of samples taking any given integer value can
be computed from the CDF and CCDF of of the TTE.

$\displaystyle\mathbb{P}(\mathcal{S}=1)$
$\displaystyle=F_{\mathcal{T}}\big{(}\delta\big{)}$
$\displaystyle\mathbb{P}(\mathcal{S}=k)$
$\displaystyle=F_{\mathcal{T}}\big{(}(k-1)T_{\text{s}}+\delta\big{)}-F_{\mathcal{T}}\big{(}(k-2)T_{\text{s}}+\delta\big{)},\
\forall\ k\geq 2$ $\displaystyle\Rightarrow\mathbb{P}(\mathcal{S}\leq k)$
$\displaystyle=F_{\mathcal{T}}\big{(}(k-1)T_{\text{s}}+\delta\big{)},\
\forall\ k\geq 1$ $\displaystyle\Rightarrow\mathbb{P}(\mathcal{S}>k)$
$\displaystyle=\bar{F}_{\mathcal{T}}\big{(}(k-1)T_{\text{s}}+\delta\big{)},\
\forall\ k\geq 1\;.$ (21)

The expected number of samples can be computed as

$\displaystyle\mathbb{E}[\mathcal{S}]$
$\displaystyle=\sum_{k=0}^{\infty}\mathbb{P}(\mathcal{S}>k)$
$\displaystyle=1+\sum_{k=1}^{\infty}\bar{F}_{\mathcal{T}}\big{(}(k-1)T_{\text{s}}+\delta\big{)}$
$\displaystyle\Rightarrow\mathbb{E}[\mathcal{S}]$
$\displaystyle=1+\sum_{k=0}^{\infty}\bar{F}_{\mathcal{T}}\big{(}kT_{\text{s}}+\delta\big{)}\;.$
(22)

####  4.1.2 Expected wait time

Recall that the offset $\delta\geq T_{\text{s}}$ and that the maximum possible
wait $w$ is upper-bounded by the sampling interval (at the time of the event).
As a result, a value of $w$ such that $T_{\text{s}}<w\leq\delta$ can arise
only before the first sample while a value $w\leq T_{\text{s}}$ can
potentially arise before any sampling instance. The CDF of wait penalty
$F_{\mathcal{W}}(w)$ can be obtained by taking the probability of the TTE to
fall at most $w$ short of any sampling instance.

$\displaystyle F_{\mathcal{W}}(w)$
$\displaystyle=\begin{cases}\sum\limits_{k=0}^{\infty}\big{(}F_{\mathcal{T}}(kT_{\text{s}}+\delta)-F_{\mathcal{T}}(kT_{\text{s}}+\delta-w)\big{)}&\text{if
}w\leq T_{\text{s}}\\\ 1-F_{\mathcal{T}}\big{(}\delta-w\big{)}&\text{if
}T_{\text{s}}<w\leq\delta\\\ 1&\text{if }w>\delta\end{cases}$ Since
$\mathcal{W}$ is a non-negative random variable, we have
$\displaystyle\mathbb{E}[\mathcal{W}]$
$\displaystyle={\int_{0}^{\infty}}\big{(}1-F_{\mathcal{W}}(w)\big{)}\,\mathop{}\mathrm{d}w$
$\displaystyle=\int_{0}^{T_{\text{s}}}\Big{(}1-\sum_{k=0}^{\infty}\big{(}F_{\mathcal{T}}(kT_{\text{s}}+\delta)-F_{\mathcal{T}}(kT_{\text{s}}+\delta-w)\big{)}\Big{)}\,\mathop{}\mathrm{d}w$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad+\int_{T_{\text{s}}}^{\delta}F_{\mathcal{T}}\big{(}\delta-w\big{)}\,\mathop{}\mathrm{d}w\;.$
Since integral limits and infinite sum are finite, and the summand is non-
negative, we get $\displaystyle\mathbb{E}[\mathcal{W}]$
$\displaystyle=T_{\text{s}}-\sum_{k=0}^{\infty}\int_{0}^{T_{\text{s}}}\big{(}F_{\mathcal{T}}(kT_{\text{s}}+\delta)-F_{\mathcal{T}}(kT_{\text{s}}+\delta-w)\big{)}\,\mathop{}\mathrm{d}w$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad+\int_{T_{\text{s}}}^{\delta}F_{\mathcal{T}}\big{(}\delta-w\big{)}\,\mathop{}\mathrm{d}w\;.$
(23)

As expected, a substitution of $\delta=T_{\text{s}}$ in (22) or (23) under the
policy $\Pi$ returns the same result that we obtained under the policy
$\hat{\Pi}$ discussed in Section 3.

###  4.2 Exponentially Distributed TTE

Due to the memory-less property of the distribution, it is predictable that
the optimum offset under an exponentially distributed TTE takes the default
value of $\delta=T_{\text{s}}$; thus making the solution of $\mathcal{P}$ and
$\hat{\mathcal{P}}$ one and the same. Before formally proving this in
Proposition 3, we will first compute the energy penalty
$\mathcal{E}(T_{\text{s}},\delta)$ by substituting the CCDF and CDF of the
exponential distribution in (22) and (23), respectively. We get

$\displaystyle\qquad\;\;\;\mathbb{E}[\mathcal{S}]=1+\dfrac{e^{-\lambda\delta}}{1-e^{-\lambda
T_{\text{s}}}}$
$\displaystyle\qquad\;\;\mathbb{E}[\mathcal{W}]=\dfrac{(1-\lambda\delta)e^{-\lambda
T_{\text{s}}}+\lambda
T_{\text{s}}\,e^{-\lambda\delta}+\lambda\delta-1}{\lambda(1-e^{-\lambda
T_{\text{s}}})}$
$\displaystyle\Rightarrow\mathcal{E}(T_{\text{s}},\delta)=\alpha\mathbb{E}[\mathcal{S}]+\beta\mathbb{E}[\mathcal{S}]$
$\displaystyle=\dfrac{e^{-\lambda
T_{\text{s}}}\big{(}\beta\\!-\\!\lambda(\beta\delta\\!+\\!\alpha)\big{)}+\lambda\big{(}\beta\delta\\!+\\!\alpha\\!+\\!e^{-\lambda\delta}(\beta
T_{\text{s}}\\!+\\!\alpha)\big{)}-\beta}{\lambda(1-e^{-\lambda
T_{\text{s}}})}\;.$ (24)

######  Proposition 3.

Given that the TTEs are exponentially distributed,
$\delta^{*}=T_{\text{s}}^{*}$ under an optimal policy for $\mathcal{P}$;
therefore, $\mathcal{P}$ and $\hat{\mathcal{P}}$ are equivalent.

###### Proof.

Let $\pi^{(t_{1},t_{2}\dots)}$ be a sampling policy with sampling intervals
given by $t_{1},\,t_{2},\dots$ and let
$\mathcal{E}\big{(}\pi^{(t_{1},t_{2}\dots)}\big{)}$ be the associated energy
penalty. Let $T_{\text{s}}^{\\#}$ be the optimum sampling interval obtained by
solving $\hat{\mathcal{P}}$, where there is no offset. That is

$\mathcal{E}\big{(}\pi^{(t,t,t,\dots)}\big{)}\geq\mathcal{E}\big{(}\pi^{(T_{\text{s}}^{\\#},T_{\text{s}}^{\\#},T_{\text{s}}^{\\#},\dots)}\big{)},\;\forall
t\geq 0\;.$ (25)

Now, let $T_{\text{s}}^{*}$ and $\delta^{*}$ be the solution to $\mathcal{P}$
resulting in an optimal policy
$\pi^{(\delta^{*},{T_{\text{s}}}^{*},{T_{\text{s}}}^{*},{T_{\text{s}}}^{*},\dots)}$
and let $F_{\mathcal{T}|\delta^{*}}$ be the conditional CDF of the TTE given
$\mathcal{T}>\delta^{*}$. If the problem to compute the optimum sampling
interval and phase is repeated at time $\delta^{*}$ using the conditional CDF,
we get a new solution containing an optimum sampling interval
$\tilde{T_{\text{s}}}^{*}$ and an optimum (second) offset
$\tilde{\delta}^{*}$. As this updated set of sampling policy denoted by
$\pi^{(\delta^{*},\tilde{\delta}^{*},\tilde{T_{\text{s}}}^{*},\tilde{T_{\text{s}}}^{*},\dots)}$
is a superset of the previously obtained sampling policy
$\pi^{(\delta^{*},{T_{\text{s}}}^{*},{T_{\text{s}}}^{*},{T_{\text{s}}}^{*},\dots)}$,
the new solution provides us with an energy penalty that is not worse than the
one obtained before. However, due to the memory-less property of the
exponential distribution we know that

$F_{\mathcal{T}}(t)=F_{\mathcal{T}|\mathcal{T}>k\delta^{*}}(t+k\delta^{*}),\;\forall
k\in\mathbb{N}\;.$

Therefore by using the conditional CDF, optimisation problem is essentially
unchanged and the newly obtained solution will be numerically equal to the
corresponding values obtained in the previous step; i.e.,
$\tilde{T_{\text{s}}}^{*}={T_{\text{s}}}^{*}$ and
$\tilde{\delta}^{*}={\delta}^{*}$. By repeating this process supported by
similar arguments, we get a sequence of non-increasing energy penalties. That
is

$\displaystyle\mathcal{E}\big{(}\pi^{(T_{\text{s}}^{\\#},T_{\text{s}}^{\\#},\dots)}\big{)}$
$\displaystyle\geq\mathcal{E}\big{(}\pi^{(\delta^{*},T_{\text{s}}^{*},T_{\text{s}}^{*},\dots)}\big{)}$
$\displaystyle\geq\mathcal{E}\big{(}\pi^{(\delta^{*},\delta^{*},T_{\text{s}}^{*},T_{\text{s}}^{*},\dots)}\big{)}$
$\displaystyle\vdots$
$\displaystyle\geq\mathcal{E}\big{(}\pi^{(\delta^{*},\delta^{*},\dots)}\big{)}$
$\displaystyle\geq\mathcal{E}\big{(}\pi^{(T_{\text{s}}^{\\#},T_{\text{s}}^{\\#},\dots)}\big{)}$
(from (25))
$\displaystyle\Rightarrow\mathcal{E}\big{(}\pi^{(T_{\text{s}}^{\\#},T_{\text{s}}^{\\#},\dots)}\big{)}$
$\displaystyle=\mathcal{E}\big{(}\pi^{(\delta^{*},\delta^{*},\dots)}\big{)}\;.$

Therefore, $\delta^{*}=T_{\text{s}}^{\\#}$ as a result of the convexity of
$\mathcal{E}(T_{\text{s}})$ from Proposition 2. Thus, the optimum set of
sampling instances under ${\Pi}$ is
$\\{t=kT_{\text{s}}^{*},\,k\in\mathcal{N}^{+}\\}$, which is essentially the
solution to $\hat{\mathcal{P}}$, proving that
$\mathcal{P}\equiv\hat{\mathcal{P}}$. ∎

As a result of the equivalence of $\mathcal{P}$ and $\hat{\mathcal{P}}$, we do
not benefit from proceeding with the relatively complex optimisation of (24)
and we can use the solution from Proposition 1 to find the optimum energy
penalty.

###  4.3 Rayleigh Distributed TTE

######  Lemma 8.

The energy penalty $\mathcal{E}$ under Rayleigh distributed TTE is given by

$\mathcal{E}(T_{\text{s}},\delta)=(\alpha+\beta
T_{\text{s}})\sum_{k=0}^{\infty}e^{-(kT_{\text{s}}+\delta)^{2}/2\sigma^{2}}-\beta\sigma\sqrt{\tfrac{\pi}{2}}+\beta\delta+\alpha\;.$
(26)

###### Proof.

Substituting the CDF of the Rayleigh distribution,
$F_{\mathcal{T}}(t)=1-e^{-t^{2}/2\sigma^{2}}$ in (22) or (23) gives

$\displaystyle\mathbb{E}[\mathcal{S}]$
$\displaystyle=1+\sum_{k=0}^{\infty}e^{-(kT_{\text{s}}+\delta)^{2}/2\sigma^{2}}$
(27) $\displaystyle\mathbb{E}[\mathcal{W}]$
$\displaystyle=\delta+T_{\text{s}}\sum_{k=0}^{\infty}e^{-(kT_{\text{s}}+\delta)^{2}/2\sigma^{2}}-\sigma\sqrt{{\dfrac{\pi}{2}}}\;.$
(28)

The energy penalty $\mathcal{E}(T_{\text{s}},\delta)$ can be computed by
adding $\mathbb{E}[\mathcal{S}]$ and $\mathbb{E}[\mathcal{W}]$ using the
weights $\alpha$ and $\beta$, respectively. ∎

Initialise the upper limit of optimising variables,
$T_{\text{s}}^{(\text{max})}$ and $n^{(\text{max})}$;
Initialise stopping criterion $\xi\,$;
$n^{(\text{L})}\leftarrow 1\,;\;n^{(\text{H})}\leftarrow n^{(\text{max})}\,$;
for  _$i\leftarrow 0$ to
$\left\lceil\log_{2}(n^{(\text{max})}-1)\right\rceil$_ do

$n\leftarrow(n^{(\text{L})}+n^{(\text{H})})/2\,$;
$T_{\text{s}}^{(\text{L})}=0;\;T_{\text{s}}^{(\text{H})}=T_{\text{s}}^{(\text{max})}\,$;
while  _$T_{\text{s}}^{(\mathrm{H})}-T_{\text{s}}^{(\mathrm{L})} >\xi$_ do

$T_{\text{s}}\leftarrow(T_{\text{s}}^{(\text{L})}+T_{\text{s}}^{(\text{H})})/2\,$;
if  _$\tfrac{\partial}{\partial
T_{\text{s}}}\mathcal{E}(T_{\text{s}},nT_{\text{s}})\geq 0$_ then

$T_{\text{s}}^{(\text{H})}\leftarrow T_{\text{s}}\,$;

else

$T_{\text{s}}^{(\text{L})}\leftarrow T_{\text{s}}\,$;

end if

end while

if
_$\mathcal{E}(T_{\text{s}},nT_{\text{s}})-\mathcal{E}(T_{\text{s}},(n-1)T_{\text{s}})\geq
0$_ then

$n^{(\text{H})}\leftarrow n\,$;

else

$n^{(\text{L})}\leftarrow n\,$;

end if

end for

$T_{\text{s}}^{*}=T_{\text{s}}\,;\;\delta^{*}=nT_{\text{s}}^{*}\,;$

Algorithm 1 Algorithm to find optimum sampling interval $T_{\text{s}}^{*}$ and
optimum offset $\delta^{*}$ with the constraint
$\delta=nT_{\text{s}},\,n\in\mathbb{N}^{+}$.

Proving the convexity of $\mathcal{E}(T_{\text{s}},\delta)$ in the two
variables $T_{\text{s}}$ and $\delta$ is hard. The difficulty arises as we
need to prove that the Hessian is non-negative and showing this for the
infinite sum is highly non-trivial. Furthermore, the proof that we used in
Lemma 5 cannot be extended as the function is not even in $T_{\text{s}}$ after
the addition of the second variable $\delta$. Instead, we will consider a sub-
optimal solution by assuming that the offset is an integer multiple of the
sampling interval. We will now show that the energy penalty is convex in
$T_{\text{s}}$ for a fixed offset of the form $\delta=nT_{\text{s}}$.

######  Lemma 9.

The function $f_{n}(t)=(a+bt)\sum_{k=0}^{\infty}e^{-((k+n)t)^{2}/2\sigma^{2}}$
is convex in $t$ for $n\in\mathbb{N}\;$.

###### Proof.

See that $f_{n}(t)$ for any $n$ is obtained by removing first $n-1$ terms from
$f_{0}(t)$. From Proposition 2, we know that $f_{0}(t)$ is convex.

$\Rightarrow 0\leq
f_{0}^{\prime\prime}(t)=\sum_{k=0}^{\infty}\dfrac{k^{2}t^{2}(a+bt)-s^{2}(a+3bt)}{\sigma^{2}}k^{2}e^{{-(k+n)^{2}t^{2}}/{2\sigma^{2}}}\;.$

As the terms in $f_{0}^{\prime\prime}(t)$ are non-decreasing with $k$,
removing first $n-1$ terms will not affect the sign of the sum and therefore
$f_{n}(t)$ is also convex. ∎

We can see with the help of (16) and (26) that the energy penalty is the sum
of a linear function and a continuously decreasing and convex Jacobi theta
function. This shows the presence of a single minima with respect to $\delta$
for any fixed $T_{\text{s}}$. With this information and the convexity in
$T_{\text{s}}$ for any fixed $\delta$ (Lemma 9), we use Algorithm 1 to find
the sampling interval and offset that attains a minimal energy penalty while
satisfying the constraint $\delta=nT_{\text{s}},\;n\in\mathbb{N}$. In the next
section, we will compare this energy penalty to $\mathcal{E}^{*}$ obtained
using a brute force search and show that Algorithm 1 attains near-optimality.
As a direct result of this near-optimality, we will reuse the same notations
$(\cdot)^{*}$ to represent the solution obtained using Algorithm 1, unless
otherwise necessary.

##  5 Numerical Results

In this section, we present the numerical results to illustrate the behaviour
of the energy penalty, the gain achieved by the proposed design, and their
dependency on the system parameters. We consider two parameter settings that
are motivated by the characteristics of the CPS and the VAS. We start with
describing the characterisation of both of these systems and the underlying
distribution of the observed process. Afterwards, we compare the proposed
design(s) with a baseline sampling policy that is used in practice.
Furthermore, to verify the near-optimality of Algorithm 1 in solving
$\mathcal{P}$, we compare its solution with that of a brute force method. For
the CPS with an exponentially distributed TTE, the offset is irrelevant and
hence we are not using Algorithm 1. As a result, this comparison with a brute-
force solution is required only for the VAS but not for the CPS.

###  5.1 Parameter Settings

(a) $\mathrm{log}_{10}(\mathbb{E}[\mathcal{S}]),\,\mathbb{E}[\mathcal{W}]$ vs.
$T_{s}$.

(b) Penalty components, $\mathcal{E}$ vs. $T_{\text{s}}$.

(c) $\mathcal{E}$ vs. $\mathbb{E}[\mathcal{T}]$.

Figure 2: Expected number of samples $\mathbb{E}[\mathcal{S}]$, expected wait
$\mathbb{E}[\mathcal{W}]$, energy penalty $\mathcal{E}$ and its components
plotted against the sampling interval $T_{\text{s}}$ and mean TTE
$\mathbb{E}[\mathcal{T}]$ for the CPS. Proposed policy $\pi^{\\#}$ is compared
with the baseline policy $\pi_{0}$.

(a) $\mathrm{log}_{10}(\mathbb{E}[\mathcal{S}]),\,\mathbb{E}[\mathcal{W}]$ vs.
$T_{s}$.

(b) Penalty components, $\mathcal{E}$ vs. $T_{\text{s}}$.

(c) $\mathcal{E}$ vs. $\mathbb{E}[\mathcal{T}]$.

Figure 3: Expected number of samples $\mathbb{E}[\mathcal{S}]$, expected wait
$\mathbb{E}[\mathcal{W}]$, energy penalty $\mathcal{E}$ and its components vs.
the sampling interval $T_{\text{s}}$ and mean TTE $\mathbb{E}[\mathcal{T}]$
for the VAS. Proposed policies $\pi^{\\#}$ and $\pi^{*}$ are compared with the
baseline policy $\pi_{0}$.

For the CPS, we consider a failure detection system where the TTE is
exponentially distributed with a mean of 10s. To detect the events (i.e.,
failures for a CPS), the terminal samples the process and sends the sample to
the back-end via a low-power, low-throughput transmitter. For the device, we
refer to the wireless sensor network characterisation in [33] with the data
size fixed at 127 Bytes. For communication technology, we choose 802.15.4
operating in the Sub1GHz ISM band with an approximate throughput of 250kbps,
resulting in a communication delay of 4ms. The device is assumed to work at 3V
drawing a current of 15mA during communication and 5mA during idling. We also
assume that the processing time of the successful sample
$\tau_{\text{s}}=5$ms.

On the other hand, a VAS typically need to transmit video frames, thus
requiring a larger throughput. We refer to the WCA Lego experiment [28] where
a set of tasks performed by a human user are monitored to detect the task
completion by taking snapshots of the progress. The frame size used in the
experiment is roughly 300kB ($640\times 480$ resolution) and the mean task
time observed is 4.846s. The processing time observed at the back end is
approximately 525ms. For the terminal device, we consider a Google Glass using
an 802.11ax transmitter providing a data rate of 400Mbps thus resulting in a
5.85ms communication delay for each snapshot. The Google Glass typically takes
334mW during active/screen-off and 2960mW during video chat[34]. Thus, we
assume these power figures as the idle power and the communication power,
respectively. On top of this, we also assume a minimum possible task time
$t_{\text{min}}$ (response time of the human user) of 0.5s. The parameters
used for the CPS and the VAS are presented in TABLE II.

| $P_{0}$ | $P_{\text{c}}$ | $\tau_{\text{c}}$ | $\tau_{\text{s}}$ | $\nicefrac{{\beta}}{{\alpha}}$ | $\mathbb{E}[\mathcal{T}]$ | $t_{\text{min}}$
---|---|---|---|---|---|---|---
CPS | 15mW | 45mW | 4ms | 5ms | 125 | 10s | –
VAS | 334mW | 2.96W | 5.85ms | 525ms | 21.7 | 4.84s | 0.5s

TABLE II: Parameters used for the cyber-physical system(CPS) and the video
analytics system (VAS).

Even though our solution does not depend on the type of energy source, we
assume that the CPS and the VAS are powered by a fixed battery pack of
arbitrary capacity. As battery life improvement is one of the directly
observable results of energy saving, we evaluate the performance of the
proposed solution in terms of percentage increase in battery life. Note that
as we use a percentage increase, the exact capacity of the battery is
irrelevant.

|  | $\pi_{0}$ | ${\pi^{\\#}}$ | $\pi^{*}$ | $\pi_{\text{b}}$
---|---|---|---|---|---
CPS | $T_{\text{s}}$ |  $83.3$ ms | $T_{\text{s}}^{\\#}$ | - | -
VAS | $T_{\text{s}}$ |  $83.3$ ms | $T_{\text{s}}^{\\#}$ | $T_{\text{s}}^{*}$ | Brute
$\delta$ | - | - | $\delta^{*}$ | Force
TABLE III: Various sampling policies considered for comparison and their
corresponding sampling interval and offset.

For the performance evaluation of the proposed policies $\pi^{\\#}$ and
$\pi^{*}$, we consider a baseline periodic sampling policy denoted by
$\pi_{0}$ as shown in TABLE III. For selecting the baseline sampling rate for
the VAS, we take a hint from the WCA system [28] that motivated the system
model. The authors use a video camera to capture the monitored process that
runs at a frame rate of 24fps which ideally results in a sampling interval of
$41.6$ms. However, whenever the processing of the discarded samples takes more
than $41.6$ms, the next sample is delayed accordingly. As a result, the mean
sampling interval is observed to be around $83.3$ms thus justifying a baseline
with sampling interval anywhere in between $41.6$ms and $83.3$ms. That being
said, we will see in the next subsection that the optimum sampling interval
for the considered VAS is around $300$ms. As a result, even though our model
does not take samples by considering the processing time, we take our baseline
sampling to be $83.3$ms to show the minimum performance improvement when the
baseline is closest to the optimum We use the same baseline sampling interval
for the CPS for simplicity in comparison.

To verify the near-optimality of $\pi^{*}$ obtained using Algorithm 1, we
compare it with that of a brute force solution of $\mathcal{P}$. To find this
brute force solution, we divide the practically feasible domain of the two-
dimensional plane formed by $T_{\text{s}}$ and $\delta$ into grids of size
$10^{-3}\times 10^{-3}\;\mathrm{s}^{2}$ and search for the optimum solution
(also known as grid search).

As the explanations to some of the figures of the CPS and the VAS involve
similar arguments, we explain them concurrently whenever it is convenient.
Also, note that the y-axes of some of these figures are kept different
intentionally for better visualisation. The parameters for all the plots are
taken from TABLE II and TABLE III, with a potential exception to the variable
parameter under discussion in a particular plot.

###  5.2 Energy Penalty

In Fig. 2(a) and Fig. 3(a) we present the the expected number of samples
$\mathbb{E}[\mathcal{S}]$ and the expected wait $\mathbb{E}[\mathcal{W}]$ by
varying $T_{\text{s}}$ for the CPS and the VAS, respectively. For comparison,
at $T_{\text{s}}=10$ms, the CPS and the VAS expect 1000 and 100 samples per
event, respectively. The expected wait however is approximately the same at
around $4$ms. As noted in Sections 3 and 4, $\mathbb{E}[\mathcal{S}]$ and
$\mathbb{E}[\mathcal{W}]$ show opposing behaviour with an increase in
$T_{\text{s}}$. After a very rapid decrease, $\mathbb{E}[\mathcal{S}]$ goes
asymptotically to $1$ with increasing $T_{\text{s}}$. This points to the
single sample that is ideally required for the event detection. On the other
hand, $\mathbb{E}[\mathcal{W}]$ shows a gradual (approximately linear)
increase with $T_{\text{s}}$. For instance, doubling the sampling interval
doubles the wait. For a VAS operating at a sampling frequency of 0.5s, this
corresponds to approximately $50\%$ increase in the TTF. Recall that TTF is
the effective delay experienced by the human user.

In Fig. 2(b) and Fig. 3(b), we show the energy penalty and its components as a
function of $T_{\text{s}}$. Observe $\mathbb{E}[\mathcal{S}]$ and
$\mathbb{E}[\mathcal{W}]$ exhibit an opposing behaviour with a change in
$T_{\text{s}}$ resulting in an energy penalty minima in their weighted sum.
This minima and the corresponding $T_{\text{s}}$ is also marked in the
figures. The qualitative behaviour of the energy penalty and its components is
similar for the CPS and the VAS with a minimum value of $6$mJ and $100$mJ,
respectively. Another important observation is the change in $\mathcal{E}$ as
a result of a deviation of $T_{\text{s}}$ from the optimum. As $\mathcal{E}$
increases much more rapidly with a negative deviation than with a positive
deviation, it is particularly important to avoid any negative errors in
calculating this optimum. That is, an oversampling can cost much more than an
undersampling by a similar amount. These errors can arise due to an incorrect
estimation of the TTE statistics or insufficient convergence of the
optimisation algorithm.

###  5.3 Energy Saving

In Fig. 2(c) and Fig. 3(c) we show energy penalty incurred for the CPS and the
VAS as a function of the mean TTE for various sampling policies from TABLE
III. Since the mean TTE value is application-specific, plotting energy penalty
across mean TTE values provides an insight into how the behaviour of the
particular CPS and VAS scales across application scenarios with different
parameterisation. The energy penalty reduction achieved by the proposed
policies is clear from these figures. Note that when the sampling interval of
$83.3$ms is smaller than $T_{\text{s}}^{\\#}$ or $T_{\text{s}}^{*}$, the
penalty is dominated by the discarded samples. As a result, the difference in
$\mathcal{E}$ increases with an increase in mean TTE. This increase is much
more prominent for the VAS.

The increase in battery life is a more direct measure of energy saving from an
application perspective. In Fig. 4 we present this by plotting the percentage
increase in the expected battery life of the terminal. In Fig. 4(a) we choose
the baseline $\pi_{0}$ whereas in Fig. 4(b) we choose a different baseline
sampling interval of $2$s. We can see that irrespective of the baseline or the
application considered, there is an observable increase in battery life.
Particularly for the VAS, the proposed sampling policy improves the battery
life by $36\%$ over $\pi_{0}$ at the considered mean TTE of 4.84s.

The motivation to consider two baselines is the value of their sampling
interval relative to the optimum sampling interval (for the TTE range
considered). The sampling interval of $0.83$ms is much smaller, and the
sampling interval 2s is much larger than the optimal sampling intervals.
Therefore, the former results in oversampling and the latter results in
undersampling which results in shifting the dominating component of the energy
penalty from $\mathbb{E}[\mathcal{S}]$ to $\mathbb{E}[\mathcal{W}]$. As a
result, the increase in battery life is a increasing function of the mean TTE
in Fig. 4(a), whereas it is a decreasing function in Fig. 4(b). Note that the
optimum sampling interval is positively correlated with the mean task time and
the battery life is inversely proportional to the energy. Therefore, this
change of percentage increase in battery life is in alignment with the
variation of $\mathbb{E}[\mathcal{S}]$ and $\mathbb{E}[\mathcal{W}]$ with
$T_{\text{s}}$ observed earlier in Fig. 2 and Fig. 3.

(a) Baseline policy $\pi_{0}$

(b) Baseline policy with $T_{\text{s}}=2$s.

Figure 4: Percentage increase in battery life achieved by the policy $\pi^{*}$
vs. mean TTE $\mathbb{E}[\mathcal{T}]$ for the CPS and the VAS. The increase
is calculated by considering two baselines policies: (a) $\pi_{0}$, and (b) a
policy with sampling interval $T_{\text{s}}=2$s.

(a) $T_{\text{s}}^{*},\;\delta^{*}$ vs. $\mathbb{E}[\mathcal{T}]$.

(b) $\mathcal{E}$ vs. $\mathbb{E}[\mathcal{T}]$.

Figure 5: Optimum sampling interval $T_{\text{s}}^{*}$, optimum offset
$\delta^{*}$ and the corresponding energy penalty $\mathcal{E}^{*}$ for
various sampling policies vs. the mean TTE $\mathcal{E}[\mathcal{T}]$ for the
VAS.

###  5.4 Comparison of Sampling Policies

We saw the battery life improvement provided by $\pi^{*}$ over $\pi_{0}$
earlier in Fig. 4. Even though we have two solutions – $\pi^{\\#}$ and
$\pi^{*}$ – for the VAS, we considered only the better performing $\pi^{*}$ in
that figure. Now in 5, we compare the performance of the two policies and see
the benefit provided by adding the offset $\delta$. We also compare the
proposed $\pi^{*}$ with the brute force solution discussed in Section 5.1. In
Fig. 5(a), we compare the optimum sampling interval and offset obtained by
Algorithm 1 and brute-force, whereas Fig. 5(b) compares the optimum energy
penalty attained by $\pi^{\\#}$ and $\pi^{*}$. From Fig. 5(a), we can see that
there is an observable (albeit small) difference in $T_{\text{s}}^{*}$ (and
$\delta^{*}$) obtained by the algorithm and the brute-force. Nonetheless, Fig.
5(b) shows that the difference in energy penalty generated as a result of this
difference is very minimal, thus confirming the near-optimality of Algorithm
1. We also observe that the additional penalty reduction offered by
$\mathcal{P}$ over $\hat{\mathcal{P}}$ amounts to roughly $51\%$ at a mean
task time of $1$s and $14\%$ at a mean task time of $5$s, thus demonstrating
the advantage of introducing the offset.

(a) $\mathcal{E}^{*},\,T_{\text{s}}^{*}$ vs. $\tau_{\text{c}}$ for fixed
$P_{\text{c}},P_{0}$.

(b) $\mathcal{E}^{*},\,T_{\text{s}}^{*}$ vs.
log${}_{10}(\nicefrac{{P_{\text{c}}}}{{P_{0}}})$ for fixed
$\tau_{\text{c}},P_{\text{c}}$.

Figure 6: Variation of optimum sampling interval $T_{\text{s}}^{*}$ and the
corresponding energy penalty $\mathcal{E}^{*}$ for various sampling policies
with variation in communication delay $\tau_{\text{c}}$ and idle power $P_{0}$
for the VAS. The vertical lines denotes $\tau_{\mathrm{c}}$ and
log${}_{10}(\nicefrac{{P_{\text{c}}}}{{P_{0}}})$ of the VAS from TABLE II.

###  5.5 Variation of $\mathcal{E}$ with System Parameters

Recall that the optimum sampling interval depends only on the ratio
$\nicefrac{{\beta}}{{\alpha}}=\tau_{\text{c}}^{-1}(\tfrac{P_{\text{c}}}{P_{0}}-1)^{-1}$.
Fig. 6(a) and Fig. 6(b) illustrates the variation of the energy penalty of the
VAS with respect to the system parameters $\tau_{\text{c}}$ and
$\nicefrac{{P_{\text{c}}}}{{P_{0}}}$. Observe from the figures that the energy
penalty obtained by solving $\mathcal{P}$ varies much less with the system
parameters than the baseline policy. This shows the relative independence of
the optimum energy penalty with the system parameters. Since these results are
qualitatively similar for the CPS, we omit them due to space constraints.

For fixed power, communication delay $\tau_{\text{c}}$ is dictated by the data
size per sample and the transmission schemes. Fig. 6(a) illustrate the
dependency of $\mathcal{E}$ with respect to these aspects of communication. We
can see that a larger communication delay results in larger
$T_{\text{s}}^{*}$. However, the corresponding increase in the incurred
penalty is much smaller for the proposed optimum. In Fig. 6(b) we show the
change in $T_{\text{s}}^{*}$ and $\mathcal{E}$ with respect to
$\nicefrac{{P_{\text{c}}}}{{P_{0}}}$ for constant $\tau_{\text{c}}$ and
${P_{\text{c}}}$. We can see that the optimum sampling interval increases with
an increase in the difference between the communication power and idle power.
However, a more interesting observation is the corresponding change in the
energy penalty. With $P_{0}<<P_{\text{c}}$, we obtain a significant penalty
reduction by using $\pi^{*}$. On the other hand, as the $P_{0}$ approaches
$P_{\text{c}}$ (i.e., 0dB in the figure), the penalty reduction goes to zero.

With advancements in semiconductor technology that reduces $P_{0}$ and the
emergence of communication standards like the mmWave,
$\nicefrac{{P_{\text{c}}}}{{P_{0}}}$ ratio is expected to increase from the
9.47dB that we modelled. Similarly, increasing image processing capabilities
increase $\tau_{\text{c}}$ as well. As a result, it is evident from the
figures that the gain offered by the proposed algorithm is more likely to
increase in the future.

##  6 Conclusion and Future Scope

We considered an edge-based feedback system that captures essential events via
sampling and proposed an optimisation framework with which the sampling
interval that minimises the energy consumption can be computed. Apart from the
generic approach to solve the optimisation problem for an arbitrary task time
distribution, we also considered two particular examples of interests – a VAS
(video analytics system) and a CPS (cyber physical system). The TTE (time to
event) of the VAS follows a Rayleigh distribution while that of the CPS
follows an exponential distribution. These two systems are used to illustrate
the behaviour of the variable components of energy. We discussed the energy
savings enabled by the optimum sampling interval, the benefit provided by
offsetting the first sample and the near-optimality of the proposed algorithm.
We also discussed the dependency of the optimum to the system parameters like
communication delay and idle power. Finally, we also discussed the additional
energy expended as a result of a computation error and concluded that this
expense is relatively steeper for a negative error.

From a mathematical perspective, the basic difference between a CPS and a VAS
is the underlying TTE distribution. However, from a design perspective, the
one important distinction is the benefit of adding the offset $\delta$. As
explained before, offset is particularly useful when the statistical mode of
the TTE distribution is large enough and the variance of the distribution is
small enough so that the probability of events occurring in the early stages
of a monitoring cycle is small. As a result, offset is not useful for an
application with an exponentially distributed TTE (see Proposition 3) but is
useful when TTE is Rayleigh distributed. However, there are other
distributions where the offset is much more useful and the proposed solution
can provide a higher performance improvement. For instance, the exponentially
modified Gaussian distribution can model the human response times in some
similar applications.

In this work, we considered the problem with only one single category of
event. However in a CPS, systems might need to capture different categories of
failures, and thus might have different severity or costs associated with
them. Similarly in a VAS, the responsiveness of the system need to be
considered and any minimisation of energy usage that affects the
responsiveness over a certain limit should be avoided. Such demands for an
additional characterisation that adds a variable weight to the required energy
savings is the primary direction for the future scope of this work.

## References

  * [1] W. A. Shewhart, “The application of statistics as an aid in maintaining quality of a manufactured product,” _Journal of the American Statistical Association_ , vol. 20, no. 152, pp. 546–548, 1925.
  * [2] J. Gertler, “Survey of model-based failure detection and isolation in complex plants,” _IEEE Control Systems Magazine_ , vol. 8, no. 6, pp. 3–11, 1988\.
  * [3] E. S. Page, “Continuous inspection schemes,” _Biometrika_ , vol. 41, no. 1/2, pp. 100–115, 1954.
  * [4] V. V. Veeravalli and T. Banerjee, “Quickest change detection,” 2012.
  * [5] A. Mahmood, K. Shi, S. Khatoon, and M. Xiao, “Data mining techniques for wireless sensor networks: A survey,” _International Journal of Distributed Sensor Networks_ , vol. 9, no. 7, p. 406316, 2013.
  * [6] G. Ananthanarayanan, P. Bahl, P. Bodík, K. Chintalapudi, M. Philipose, L. Ravindranath, and S. Sinha, “Real-time video analytics: The killer app for edge computing,” _Computer_ , vol. 50, no. 10, pp. 58–67, 2017.
  * [7] B. Luo, S. Tan, Z. Yu, and W. Shi, “Edgebox: Live edge video analytics for near real-time event detection,” in _2018 IEEE/ACM Symposium on Edge Computing (SEC)_ , 2018, pp. 347–348.
  * [8] Y. Ye, S. Ci, A. K. Katsaggelos, Y. Liu, and Y. Qian, “Wireless video surveillance: A survey,” _IEEE Access_ , vol. 1, pp. 646–660, 2013.
  * [9] X. Wang, S. Wang, and D. Bi, “Distributed visual-target-surveillance system in wireless sensor networks,” _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , vol. 39, no. 5, pp. 1134–1146, 2009.
  * [10] H. Wang, F. Zhai, Y. Eisenberg, and A. K. Katsaggelos, “Cost-distortion optimized unequal error protection for object-based video communications,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 15, no. 12, pp. 1505–1516, 2005.
  * [11] S. Cui and A. J. Goldsmith, “Cross-layer optimization of sensor networks based on cooperative mimo techniques with rate adaptation,” in _IEEE 6th Workshop on Signal Processing Advances in Wireless Communications_ , 2005, pp. 960–964.
  * [12] M. Casares and S. Velipasalar, “Adaptive methodologies for energy-efficient object detection and tracking with battery-powered embedded smart cameras,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 21, no. 10, pp. 1438–1452, 2011.
  * [13] J. A. Fuemmeler and V. V. Veeravalli, _Smart Sleeping Policies for Energy-Efficient Tracking in Sensor Networks_. Boston, MA: Springer US, 2008, pp. 267–287.
  * [14] B. Shi, J. Yang, Z. Huang, and P. Hui, “Offloading guidelines for augmented reality applications on wearable devices,” in _Proc. of ACM International Conference on Multimedia_ , 2015, p. 1271–1274.
  * [15] R. Kemp, N. Palmer, T. Kielmann, F. Seinstra, N. Drost, J. Maassen, and H. Bal, “eyeDentify: Multimedia cyber foraging from a smartphone,” in _Proc. IEEE International Symposium on Multimedia_ , 2009, pp. 392–399.
  * [16] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” _IEEE Communications Surveys Tutorials_ , vol. 19, no. 4, pp. 2322–2358, 2017.
  * [17] J. P. Champati and B. Liang, “Semi-online algorithms for computational task offloading with communication delay,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 28, no. 4, pp. 1189–1201, 2017.
  * [18] ——, “Single restart with time stamps for parallel task processing with known and unknown processors,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 31, no. 1, pp. 187–200, 2020.
  * [19] W. Zhang, Y. Wen, K. Guan, D. Kilper, H. Luo, and D. O. Wu, “Energy-optimal mobile cloud computing under stochastic wireless channel,” _IEEE Transactions on Wireless Communications_ , vol. 12, no. 9, pp. 4569–4581, 2013.
  * [20] C. You, K. Huang, and H. Chae, “Energy efficient mobile cloud computing powered by wireless energy transfer,” _IEEE Journal on Selected Areas in Communications_ , vol. 34, no. 5, pp. 1757–1771, 2016.
  * [21] K. Kumar and Y. Lu, “Cloud computing for mobile users: Can offloading computation save energy?” _Computer_ , vol. 43, no. 4, pp. 51–56, 2010.
  * [22] S. Barbarossa, S. Sardellitti, and P. Di Lorenzo, “Communicating while computing: Distributed mobile cloud computing over 5G heterogeneous networks,” _IEEE Signal Processing Magazine_ , vol. 31, no. 6, pp. 45–55, 2014.
  * [23] M. Zhao, J.-J. Yu, W.-T. Li, D. Liu, S. Yao, W. Feng, C. She, and T. Q. S. Quek, “Energy-aware offloading in time-sensitive networks with mobile edge computing,” _CoRR_ , vol. abs/2003.12719, 2020.
  * [24] S. E. Mahmoodi, R. N. Uma, and K. P. Subbalakshmi, “Optimal joint scheduling and cloud offloading for mobile applications,” _IEEE Transactions on Cloud Computing_ , vol. 7, no. 2, pp. 301–313, 2019.
  * [25] W. Zhang, Y. Wen, and D. O. Wu, “Collaborative task execution in mobile cloud computing under a stochastic wireless channel,” _IEEE Transactions on Wireless Communications_ , vol. 14, no. 1, pp. 81–93, 2015.
  * [26] D. Huang, P. Wang, and D. Niyato, “A dynamic offloading algorithm for mobile computing,” _IEEE Transactions on Wireless Communications_ , vol. 11, no. 6, pp. 1991–1995, 2012.
  * [27] V. N. Moothedath, J. P. Champati, and J. Gross, “Energy-optimal sampling of edge-based feedback systems,” in _2021 IEEE International Conference on Communications Workshops (ICC Workshops)_ , 2021, pp. 1–6.
  * [28] K. Ha, Z. Chen, W. Hu, W. Richter, P. Pillai, and M. Satyanarayanan, “Towards wearable cognitive assistance,” in _Proc. of the 12th Annual International Conference on Mobile Systems, Applications, and Services_. Association for Computing Machinery, 2014, p. 68–81.
  * [29] Z. Chen, W. Hu, J. Wang, S. Zhao, B. Amos, G. Wu, K. Ha, K. Elgazzar, P. Pillai, R. Klatzky, D. Siewiorek, and M. Satyanarayanan, “An empirical study of latency in an emerging class of edge computing applications for wearable cognitive assistance,” in _Proc. ACM/IEEE Symposium on Edge Computing_ , 2017.
  * [30] M. O. Muñoz, R. Klatzky, J. Wang, P. Pillai, M. Satyanarayanan, and J. Gross, “Impact of delayed response on wearable cognitive assistance,” _CoRR_ , vol. abs/2011.02555, 2020.
  * [31] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, 2004.
  * [32] E. T. Whittaker and G. N. Watson, _A Course of Modern Analysis_ , 4th ed., ser. Cambridge Mathematical Library. Cambridge University Press, 1996.
  * [33] A. Moschitta and I. Neri, “Power consumption assessment in wireless sensor networks,” _ICT-Energy-Concepts Towards Zero-Power Information and Communication Technology_ , 02 2014.
  * [34] R. LiKamWa, Z. Wang, A. Carroll, F. X. Lin, and L. Zhong, “Draining our glass: An energy and heat characterization of google glass,” in _Proceedings of 5th Asia-Pacific Workshop on Systems_ , ser. APSys ’14. New York, NY, USA: Association for Computing Machinery, 2014.