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. 

We consider a resource-constrained Edge Device (ED), such as an IoT sensor or a microcontroller unit, embedded with a small-size ML model (S-ML) for a generic classification application and an Edge Server (ES) that hosts a large-size ML model (L-ML). Since the inference accuracy of S-ML is lower than that of the L-ML, offloading all the data samples to the ES results in high inference accuracy, but it defeats the purpose of embedding S-ML on the ED and deprives the benefits of reduced latency, bandwidth savings, and energy efficiency of doing local inference. In order to get the best out of both worlds, i.e., the benefits of doing inference on the ED and the benefits of doing inference on ES, we explore the idea of Hierarchical Inference (HI), wherein S-ML inference is only accepted when it is correct, otherwise the data sample is offloaded for L-ML inference. However, the ideal implementation of HI is infeasible as the correctness of the S-ML inference is not known to the ED. We propose an online meta-learning framework that the ED can use to predict the correctness of the S-ML inference. In particular, we propose to use the maximum softmax value output by S-ML for a data sample and decide whether to offload it or not. The resulting online learning problem turns out to be a Prediction with Expert Advice (PEA) problem with continuous expert space. We propose two different algorithms and prove sublinear regret bounds for them without any assumption on the smoothness of the loss function. We evaluate and benchmark the performance of the proposed algorithms for image classification application using four datasets, namely, Imagenette and Imagewoof, MNIST, and CIFAR-10. 

We consider a finite-state Discrete-Time Markov Chain (DTMC) source that can be sampled for detecting the events when the DTMC transits to a new state. Our goal is to study the trade-off between sampling frequency and staleness in detecting the events. We argue that, for the problem at hand, using Age of Information (AoI) for quantifying the staleness of a sample is conservative and therefore, study another freshness metric age penalty, which is defined as the time elapsed since the first transition out of the most recently observed state. We study two optimization problems: minimize average age penalty subject to an average sampling frequency constraint, and minimize average sampling frequency subject to an average age penalty constraint; both are Constrained Markov Decision Problems. We solve them using the Lagrangian MDP approach, where we also provide structural results that reduce the search space. Our numerical results demonstrate that the computed Markov policies not only outperform optimal periodic sampling policies, but also achieve sampling frequencies close to or lower than that of an optimal clairvoyant (non-causal) sampling policy, if a small age penalty is allowed.

We study task scheduling and offloading in a cloud computing system with multiple users where tasks have different processing times, release times, communication times, and weights. Each user may schedule a task locally or offload it to a shared cloud with heterogeneous processors by paying a price for the resource usage. We consider four different models in this paper: (i) zero task release and communication times, (ii) non-zero task release times and zero communication times, (iii) non-zero task release times and fixed communication times, and (iv) non-zero task release times and sequence-dependent communication times. Our work aims at identifying a task scheduling decision that minimizes the weighted sum completion time of all tasks, while satisfying the users' budget constraints. We propose an efficient solution framework for this NP-hard problem. As a first step, we use a relaxation and a rounding technique to obtain an integer solution that is a constant factor approximation to the minimum weighted sum completion time. This solution violates the budget constraints, but the average budget violation decreases as the number of users increases. Thus, we develop a scalable algorithm termed Single-Task Unload for Budget Resolution (STUBR), which resolves budget violations and orders the tasks to obtain robust solutions. IEEE

Computational offloading systems, where computational tasks can be processed locally or offloaded to a remote cloud, have become prevalent since the advent of cloud computing. The task scheduler in a computational offloading system decides both the selection of tasks to be offloaded to the remote cloud and the scheduling of tasks on the local processors. In this work, we consider the problem of minimizing a weighted sum of the makespan of the tasks and the offloading cost at the remote cloud. In contrast to prior works, we do not assume that the task processing times are known a priori. We show that the original problem can be solved by algorithms designed toward minimizing the maximum between the makespan and the weighted offloading cost, only with doubling of the competitive ratio. Furthermore, when the remote cloud is much faster than the local processors, the latter problem can be equivalently transformed into a makespan minimization problem with unrelated processors. For this case, we propose a Greedy-One-Restart (GOR) algorithm based on online estimation of the unknown processing times, and one-time cancellation and rescheduling of tasks that turn out to require long processing times. Given m local processors, we show that GOR has O(root m) competitive ratio, which is a substantial improvement over the best known algorithms in the literature. For the general case of arbitrary speed at the remote cloud, we extend GOR to a Greedy-Two-Restart (GTR) algorithm and show that it is O(root m)-competitive. Furthermore, where tasks arrive dynamically with unknown arrival times, we extend GOR and GTR to Dynamic-GOR (DGOR) and Dynamic-GTR (DGTR), respectively, and find their competitive ratios. Finally, we discuss how GOR can be extended to accommodate multiple remote processors. In addition to performance bounding by competitive ratios, our simulation results demonstrate that the proposed algorithms are favorable also in terms of average performance, in comparison with the well-known list scheduling algorithm and other alternatives.

There is a growing interest in analysing freshness of data in networked systems. Age of Information (AoI) has emerged as a relevant metric to quantify this freshness at a receiver, and minimizing this metric for different system models has received significant research attention. However, a fundamental question remains: what is the minimum achievable AoI in any single-server-single-source queuing system for a given service-time distribution? We address this question for the average peak AoI (PAoI) statistic by considering generate-at-will source model, service preemptions, and request delays. Our main result is on the characterization of the minimum achievable average PAoI, and we show that it is achieved by a fixed-threshold policy among the set of all causal policies. We use the characterization to provide necessary and sufficient condition for preemptions to be beneficial for a given service-time distribution. Our numerical results, obtained using well-known distributions, demonstrate that the heavier the tail of a distribution the higher the performance gains of using preemptions.

Age of Information (AoI) has proven to be a useful metric in networked systems where timely information updates are of importance. In the literature, minimizing "average age" has received considerable attention. However, various applications pose stricter age requirements on the updates which demand knowledge of the AoI distribution. Furthermore, the analysis of AoI distribution in a multi-hop setting, which is important for the study of Wireless Networked Control Systems (WNCS), has not been addressed before. Toward this end, we study the distribution of AoI in a WNCS with two hops and devise a problem of minimizing the tail of the AoI distribution with respect to the frequency of generating information updates, i.e., the sampling rate of monitoring a process, under first-come-first-serve (FCFS) queuing discipline. We argue that computing an exact expression for the AoI distribution may not always be feasible; therefore, we opt for computing upper bounds on the tail of the AoI distribution. Using these upper bounds, we formulate Upper Bound Minimization Problems (UBMP), namely, Chernoff-UBMP and alpha-relaxed Upper Bound Minimization Problem (alpha-UBMP), where alpha > 1 is an approximation factor, and solve them to obtain "good" heuristic rate solutions for minimizing the tail. We demonstrate the efficacy of our approach by solving the proposed UBMPs for three service distributions: geometric, exponential, and Erlang. Simulation results show that the rate solutions obtained are near optimal for minimizing the tail of the AoI distribution for the considered distributions.

We consider a finite-state Discrete-Time Markov Chain (DTMC) source that can be sampled for detecting the events when the DTMC transits to a new state. Our goal is to study the trade-off between sampling frequency and staleness in detecting the events. We argue that, for the problem at hand, using Age of Information (AoI) for quantifying the staleness of a sample is conservative and therefore, introduce age penalty for this purpose. We study two optimization problems: minimize average age penalty subject to an average sampling frequency constraint, and minimize average sampling frequency subject to an average age penalty constraint; both are Constrained Markov Decision Problems. We solve them using linear programming approach and compute Markov policies that are optimal among all causal policies. Our numerical results demonstrate that the computed Markov policies not only outperform optimal periodic sampling policies, but also achieve sampling frequencies close to or lower than that of an optimal clairvoyant (non-causal) sampling policy, if a small age penalty is allowed.

In future industrial scenarios, Wireless Sensor Net-works (WSN) are envisioned to support the traffic of Net-worked Control Systems (NCS). WirelessHART is a prevalentWSN protocol that uses the Time Slotted Channel Hopping(TSCH) medium access to cope with the delay and reliabilityrequirements of NCS in the harsh industrial environment. InTSCH, time slots and frequencies can be scheduled by a networkcoordinator to provide Quality of Service (QoS). In contrast toprevious works that consider the end-to-end delay requirement ofa flow of packets, we focus on a finite sequence of time-criticalpackets. These packets may belong to a time-critical messagewhose latency could significantly impact the NCS. Given an end-to-end delay deadline, our objective is to minimize the DelayViolation Probability (DVP) for a finite sequence of packets bydynamically scheduling the time slots in each frame. This is achallenging task as DVP depends on the instantaneous state ofthe network and requires its transient analysis. In this work,we model the wireless NCS as a two-queues WirelessHARTnetwork and propose the first transient analysis of DVP fora finite sequence of time-critical packets. Noting that DVPcannot be directly used for dynamic resource allocation, wepropose a heuristic algorithm by relating DVP with the network’sthroughput. The proposed heuristic maximizes the expectedthroughput, is computed by solving a finite-horizon MarkovDecision Process (MDP) and can be implemented at the networkcoordinator. Using simulation we demonstrate that the MDP-based heuristic achieves lower DVP compared to the classicalMaxWeight and Weighted-Fair Queuing.