Bipartite queueing networks with unknown statistics, where jobs are routed to and queued at servers and yield job-type and server-dependent utilities upon completion, model a wide range of problems in communications and related research areas (e.g., call routing in call centers, task assignment in crowdsourcing, job dispatching to cloud servers). Additionally, many such problems have additional routing constraints, such as quality of service or budgeted server cost constraints. The utility maximization problem in a bipartite queueing network with unknown statistics and subject to additional routing constraints is a constrained bandit learning problem with delayed feedback that depends on the server queueing delay. In this paper, we propose an efficient algorithm that overcomes the technical shortcomings of the state-of-the-art and effectively balances utility regret and peak job completion delay, while achieving constant peak constraint violation for the additional sample path routing constraints. Empirically, our algorithm is shown to simultaneously achieve low regret, peak delay, and peak constraint violation compared to existing algorithms.

Combinatorial multi-armed bandit (CMAB) model is designed to maximize cumulative rewards in the presence of uncertainty by selecting a subset of arms in each round. This paper is inspired by two critical applications in wireless networks, where it’s not only essential to maximize cumulative rewards but also to guarantee fairness among arms (i.e., the minimum average reward required by each arm) and ensure reward regularity (i.e., how often each arm receives the reward). In this paper, we propose a parameterized regular and fair learning algorithm to achieve these three objectives. In particular, the proposed algorithm linearly combines virtual queue-lengths (tracking the fairness violations), Time-Since-Last-Reward (TSLR) metrics, and Upper Confidence Bound (UCB) estimates in its weight measure. Here, TSLR is inspired by age-of-information and measures the elapsed number of rounds since an arm last received a reward, capturing the reward regularity performance, and UCB estimates are utilized to balance the tradeoff between exploration and exploitation in online learning. By uncovering a key relationship between the dynamics of virtual queue-lengths and TSLR metrics and utilizing several non-trivial Lyapunov functions, we analytically characterize zero cumulative fairness violation, reward regularity, and cumulative regret performance under our proposed algorithm. These theoretical outcomes are verified by simulations based on two real-world datasets.

Cybersickness remains a major challenge in virtual and mixed reality (VR/MR), yet existing methods primarily focus on predicting its onset without offering formal guarantees regarding its occurrence or effective mitigation. As VR/MR applications expand into safety-critical domains like healthcare, defense, verifiable safety assurances become essential to protect users from adverse physiological and psychological effects. This paper introduces a probabilistic verification framework leveraging Bayesian Networks (BN) to explicitly model the interactions among system parameters, human physiological responses, and cybersickness severity. Unlike deep learning approaches that lack interpretability and formal verification capabilities, the proposed BN model explicitly captures how environmental and system-level factors (e.g., luminance, spectral entropy, and image gradient complexity via HoG features) influence physiological responses (e.g., heart rate, reaction time, eye tracking), ultimately affecting cybersickness severity. By learning the joint probability distribution of these factors, our approach provides rigorous formal guarantees on cybersickness risk under specified operational conditions. If these guarantees are not met, automated adaptive adjustments are recommended to restore safe conditions. Experimental validation involving physiological and systemlevel data demonstrates that Bayesian Networks provide an interpretable and efficient framework, uniquely enabling formal probabilistic verification of cybersickness risks. This capability makes the proposed approach particularly suitable for designing and deploying VR/MR systems with explicitly verified safety constraints.

Immersive technologies, such as virtual and augmented reality, demand high framerate, low latency, and precise synchronization between real and virtual environments. To meet these requirements, an edge server typically needs to perform high-quality rendering, and must predict user head motion and transmit a portion of the rendered panoramic scene that is large enough to cover the user's viewport, yet small enough to satisfy bandwidth constraints. Each portion yields two feedback signals: prediction feedback, indicating whether the selected portion covers the actual viewport, and transmission feedback, indicating whether all data packets are successfully delivered. While prior work models this setting as a multi-armed bandit with two-level bandit feedback, it overlooks that prediction feedback can be retrospectively computed for all possible portions, thus providing full-information feedback. In this work, we introduce a new two-level feedback model that combines full-information feedback with bandit feedback, and we formulate the portion selection problem as an online learning task under this hybrid setting. We derive an instance-dependent regret lower bound for this new hybrid feedback setting, and we propose AdaPort, a hybrid learning algorithm that leverages both the full-information feedback and bandit feedback to improve learning efficiency. We then show that the instance-dependent regret upper bound for AdaPort matches the lower bound asymptotically, proving its asymptotic optimality. Simulations using synthetic data and real-world traces demonstrate that AdaPort consistently outperforms state-of-the-art baselines, validating the benefits of exploiting the hybrid feedback structure.

Wireless interactive panoramic scene delivery imposes unique challenges compared to its wired or non-interactive counterparts. The wireless channel is throughput-constrained, which limits the ability to deliver large and high-quality panoramic images. On the other hand, the interactivity imposes a real-time constraint on the system and limits the use of a playback buffer. Also, wireless inputs are not delivered instantaneously like wired interrupt-based inputs, so the system must predict the user's head pose and the portion of the scene visible to them, called the viewport. This reveals a tradeoff: delivering a portion too small may not cover the viewport if the prediction error is too large, while delivering a portion too large may result in a failed wireless transmission. Likewise, delivering the portion at too high a quality may result in a failed transmission. Despite these challenges, we would like to guarantee an immersive experience for the user by delivering a high-quality and visually consistent panoramic scene. To that end, we aim to maximize the user's quality of experience, which we define as the combination of (1) cumulative quality, (2) long-term consistency, which quantifies the overall variance in perceived quality, and (3) short-term consistency, which quantifies abrupt quality changes. We formulate this problem as a risk-averse multi-armed bandit problem with reward-dependent switching costs, and develop a novel block-based UCB algorithm with opportunistic switching. We derive its theoretical regret upper bound, which matches results in prior work, and corroborate this result in trace-based simulations using a panoramic video streaming data trace.

The integration of Large Language Models (LLMs) like GPT-4 with Extended Reality (XR) technologies offers the potential to build truly immersive XR environments that interact with human users through natural language, e.g., generating and animating 3D scenes from audio inputs. However, the complexity of XR environments makes it difficult to accurately extract relevant contextual data and scene/object parameters from an overwhelming volume of XR artifacts. It leads to not only increased costs with pay-per-use models, but also elevated levels of generation errors. Moreover, existing approaches focusing on coding script generation are often prone to generation errors, resulting in flawed or invalid scripts, application crashes, and ultimately a degraded user experience. To overcome these challenges, we introduce LLMER, a novel framework that creates interactive XR worlds using JSON data generated by LLMs. Unlike prior approaches focusing on coding script generation, LLMER translates natural language inputs into JSON data, significantly reducing the likelihood of application crashes and processing latency. It employs a multi-stage strategy to supply only the essential contextual information adapted to the user's request and features multiple modules designed for various XR tasks. Our preliminary user study reveals the effectiveness of the proposed system, with over 80% reduction in consumed tokens and around 60% reduction in task completion time compared to state-of-the-art approaches. The analysis of users' feedback also illuminates a series of directions for further optimization.

Bipartite queueing networks with unknown statistics, where jobs are routed to and queued at servers and yield server-dependent utilities upon completion, model a wide range of problems in communications and related research areas (e.g., call routing in call centers, task assignment in crowdsourcing, job dispatching to cloud servers). The utility maximization problem in bipartite queueing networks with unknown statistics is a bandit learning problem where the delayed semi-bandit feedback depends on the server queueing delay. In this paper, we propose an efficient algorithm that overcomes the technical shortcomings of the state-of-the-art and achieves square root regret, queue length, and feedback delay. Our approach also accommodates additional constraints, such as quality of service, fairness, and budgeted cost constraints, with constant expected peak violation and zero expected violation after a fixed timeslot. Empirically, our algorithm’s regret is competitive with the state-of-the-art for some problem instances and outperforms it in others, with much lower delay and constraint violation.

In this paper, we consider a large-scale heterogeneous mobile edge computing system, where each device's mean computing task arrival rate, mean service rate, mean energy consumption, and mean offloading latency are drawn from different bounded continuous probability distributions to reflect the diverse compute-intensive applications, mobile devices with different computing capabilities and battery efficiencies, and different types of wireless access networks (e.g., 4G/SG cellular networks, WiFi). We consider a class of distributed threshold-based randomized offloading policies and develop a threshold update algorithm based on its computational load, average offloading latency, average energy consumption, and edge server processing time, depending on the server utilization. We show that there always exists a unique Mean-Field Nash Equilibrium (MFNE) in the large-system limit when the task processing times of mobile devices follow an exponential distribution. This is achieved by carefully partitioning the space of mean arrival rates to account for the discrete structure of each device's optimal threshold. Moreover, we show that our proposed threshold update algorithm converges to the MFNE. Finally, we perform simulations to corroborate our theoretical results and demonstrate that our proposed algorithm still performs well in more general setups based on the collected real-world data and outperforms the well-known probabilistic offloading policy.

Bandits with arm selection constraints and bandits with switching costs have both gained recent attention in wireless networking research. Pessimistic-optimistic algorithms, which combine bandit learning with virtual queues to track the constraints, are commonly employed in the former. Block-based algorithms, where switching is disallowed within a block, are commonly employed in the latter. While efficient algorithms have been developed for both problems, it remains challenging to guarantee low regret and constraint violation in a bandit problem that includes both arm selection constraints and switching costs due to the tight coupling between the two. Here, switching may be necessary to decrease the constraint violation but comes at the cost of increased switching regret. In this paper, we tackle the constrained bandits with switching costs problem, for which we design a block-based pessimistic-optimistic algorithm. We identify three timely wireless networking applications for this framework in edge computing, mobile crowdsensing, and wireless network selection. We also prove that our algorithm achieves sublinear regret and vanishing constraint violation and corroborate these results with synthetic simulations and extensive trace-based simulations in the wireless network selection setting.

The Internet of Things (IoT) interconnects a vast number of physical devices with each other and enables remote monitoring and control of the physical system. This, together with the recent progress of virtual reality (VR) technology, provides an immersive experience for the user to perform remote monitoring and control as if she observes and controls the physical system in person. In this demo, we develop an immersive remote monitoring and control system consisting of 3D virtual monitoring and control panel and the physical water pump system. Users can remotely control and monitor the water level of the physical water pump system through the 3D virtual panel in real-time. We use Fourier transform to filter out the noise when the water level remains static and the exponential running average method to make the collected data more smooth when the water level dynamically changes. The experimental evaluations demonstrate that the difference between the physical and virtual water levels is small in both static and dynamic water levels.

Rate adaptation is a key mechanism in current IEEE 802.11 networks and next-generation cellular systems. Observing that the operating time scale of rate adaptation is usually much smaller than the user association and scheduling, we study a joint design of wireless user association and scheduling and rate adaptation with different time scales to maximize cumulative system throughput while guaranteeing desired fairness among users. We develop a maximum-weight type user association and scheduling algorithm that combines the virtual queues (tracking the scheduling debt for each user to ensure the desired fairness guarantee) and Upper Confidence Bound (UCB) estimates in its weight measure; each selected user then adopts the UCB algorithm to perform rate adaptation in a smaller time scale. We show that our proposed algorithm yields a cumulative regret growing with the square root of the time horizon up to a logarithmic factor, and achieves zero cumulative fairness violation after a certain number of time frames. We demonstrate the efficiency of the proposed algorithm via simulations using synthetic and realistic data traces.

In this article, we consider a discrete-time information-update system, where a service provider can proactively retrieve information from the information source to update its data and users query the data at the service provider. One example is crowdsensing-based applications. In order to keep users satisfied, the application desires to provide users with fresh data, where the freshness is measured by the age-of-information (AoI). However, maintaining fresh data requires the application to update its database frequently, which incurs an update cost (e.g., incentive payment). Hence, there exists a natural tradeoff between the AoI and the update cost at the service provider who needs to make update decisions. To capture this tradeoff, we formulate an optimization problem with the objective of minimizing the total cost, which is the sum of the staleness cost (which is a function of the AoI) and the update cost. Then, we provide two useful guidelines for the design of efficient update policies. Following these guidelines and assuming that the aggregated request arrival process is Bernoulli, we prove that there exists a threshold-based policy that is optimal among all online policies and thus focus on the class of threshold-based policies. Furthermore, we derive the closed-form formula for computing the long-term average cost under any threshold-based policy and obtain the optimal threshold. Finally, we perform extensive simulations using both synthetic data and real traces to verify our theoretical results and demonstrate the superior performance of the optimal threshold-based policy compared with several baseline policies.

Mobile cloud computing enables compute-limited mobile devices to perform real-time intensive computations such as speech recognition or object detection by leveraging powerful cloud servers. An important problem in large-scale mobile cloud computing is computational offloading, where each mobile device decides when and how much computation should be uploaded to cloud servers by considering the local processing delay and the cost of using cloud servers. In this paper, we develop a distributed threshold-based offloading algorithm where it uploads an incoming computing task to cloud servers if the number of tasks queued at the device reaches the threshold and processes it locally otherwise. The threshold is updated iteratively based on the computational load and the cost of using cloud servers. We formulate the problem as a symmetric game, and characterize the sufficient and necessary conditions for the existence and uniqueness of the Nash Equilibrium (NE) assuming exponential service times. Then, we show the convergence of our proposed distributed algorithm to the NE when the NE exists. Further, we characterize the performance gap between cost under our proposed distributed algorithm and the minimum cost in terms of Price of Anarchy (PoA) when the cost of using cloud servers is high. Finally, we perform extensive simulations to validate our theoretical findings, demonstrate the efficiency of our proposed distributed algorithm under various scenarios such as hyperexponential service times, imperfect server utilization estimation, and asynchronous threshold updates, and reveal the superior performance of threshold-based policies over their probabilistic counterpart.

In this paper, we consider a discrete-time information-update system, where a service provider can proactively retrieve information from the information source to update its data and users query the data at the service provider. One example is crowdsensing-based applications. In order to keep users satisfied, the application desires to provide users with fresh data, where the freshness is measured by the Age-of-Information (AoI). However, maintaining fresh data requires the application to update its database frequently, which incurs an update cost (e.g., incentive payment). Hence, there exists a natural tradeoff between the AoI and the update cost at the service provider who needs to make update decisions. To capture this tradeoff, we formulate an optimization problem with the objective of minimizing the total cost, which is the sum of the staleness cost (which is a function of the AoI) and the update cost. Then, we provide two useful guidelines for the design of efficient update policies. Following these guidelines and assuming that the aggregated request arrival process is Bernoulli, we prove that there exists a threshold-based policy that is optimal among all online policies and thus focus on the class of threshold-based policies. Furthermore, we derive the closed-form formula for computing the long-term average cost under any threshold-based policy and obtain the optimal threshold. Finally, we perform extensive simulations using both synthetic data and real traces to verify our theoretical results and demonstrate the superior performance of the optimal threshold-based policy compared with several baseline policies.

Virtual Reality (VR), together with the network infrastructure, can provide an interactive and immersive experience for multiple users simultaneously and thus enables collaborative VR applications (e.g., VR-based classroom). However, the satisfactory user experience requires not only high-resolution panoramic image rendering but also extremely low latency and seamless user experience. Besides, the competition for limited network resources (e.g., multiple users share the total limited bandwidth) poses a significant challenge to collaborative user experience, in particular under the wireless network with time-varying capacities. While existing works have tackled some of these challenges, a principled design considering all those factors is still missing. In this paper, we formulate a combinatorial optimization problem to maximize the Quality of Experience (QoE), defined as the linear combination of the quality, the average VR content delivery delay, and variance of the quality over a finite time horizon. In particular, we incorporate the influence of imperfect motion prediction when considering the quality of the perceived contents. However, the optimal solution to this problem can not be implemented in real-time since it relies on future decisions. Then, we decompose the optimization problem into a series of combinatorial optimization in each time slot and develop a low-complexity algorithm that can achieve at least 1/2 of the optimal value. Despite this, the trace-based simulation results reveal that our algorithm performs very close to the decomposed optimal offline solution. Furthermore, we implement our proposed algorithm in a practical system with commercial mobile devices and demonstrate its superior performance over state-of-the-art algorithms. We open-source our implementations on https://github.com/SNeC-Lab-PSU/ICDCS-CollaborativeVR.

Interactive panoramic scene delivery not only consumes 4∼6× more bandwidth than traditional video streaming of the same resolution but also requires timely displaying the delivered content to ensure smooth interaction. Since users can only see roughly 20% of the entire scene at a time (called the viewport), it is sufficient to deliver the relevant portion of the panoramic scene if we can accurately predict the user’s motion. It is customary to deliver a portion larger than the viewport to tolerate inaccurate predictions. Intuitively, the larger the delivered portion, the higher the prediction accuracy and lower the wireless transmission success probability. The goal is to select an appropriate delivery portion to maximize system throughput. We formulate this problem as a multi-armed bandit problem and use the classical Kullback-Leibler Upper Confidence Bound (KL-UCB) algorithm for the portion selection. We further develop a novel variant of the KL-UCB algorithm that effectively leverages two-level feedback (i.e., both prediction and transmission outcomes) after each decision on the selected portion and show its asymptotical optimality, which may be of independent interest by itself. We demonstrate the superior performance of our proposed algorithms over existing heuristic methods using both synthetic simulations and real experimental evaluations.

Multi-armed bandit frameworks, including combinatorial semi-bandits and sleeping bandits, are commonly employed to model problems in communication networks and other engineering domains. In such problems, feedback to the learning agent is often delayed (e.g. communication delays in a wireless network or conversion delays in online advertising). Moreover, arms in a bandit problem often represent entities required to be treated fairly, i.e. the arms should be played at least a required fraction of the time. In contrast to the previously studied asymptotic fairness, many real-time systems require such fairness guarantees to hold even in the short-term (e.g. ensuring the credibility of information flows in an industrial Internet of Things (IoT) system). To that end, we develop the Learning with Delays under Fairness (LDF) algorithm to solve combinatorial semi-bandit problems with sleeping arms and delayed feedback, which we prove guarantees strong (short-term) fairness. While previous theoretical work on bandit problems with delayed feedback typically derive instance-dependent regret bounds, this approach proves to be challenging when simultaneously considering fairness. We instead derive a novel instance-independent regret bound in this setting which agrees with state-of-the-art bounds. We verify our theoretical results with extensive simulations using both synthetic and real-world datasets.

We study adaptive video streaming for multiple users in wireless access edge networks with unreliable channels. The key challenge is to jointly optimize the video bitrate adaptation and resource allocation such that the users' cumulative quality of experience is maximized. This problem is a finite-horizon restless multi-armed multi-action bandit problem and is provably hard to solve. To overcome this challenge, we propose a computationally appealing index policy entitled Quality Index Policy, which is well-defined without the Whittle indexability condition and is provably asymptotically optimal without the global attractor condition. These two conditions are widely needed in the design of most existing index policies, which are difficult to establish in general. Since the wireless access edge network environment is highly dynamic with system parameters unknown and time-varying, we further develop an index-aware reinforcement learning (RL) algorithm dubbed QA-UCB. We show that QA-UCB achieves a sub-linear regret with a low-complexity since it fully exploits the structure of the Quality Index Policy for making decisions. Extensive simulations using real-world traces demonstrate significant gains of proposed policies over conventional approaches. We note that the proposed framework for designing index policy and index-aware RL algorithm is of independent interest and could be useful for other large-scale multi-user problems.

In remote Multi-user AR (MuAR), a user shares with remote users his/her physical environment, which is enhanced by computer-generated perceptual information. Despite its important role in Metaverse, a user may have serious privacy concerns for MuAR: the user may want to share only a portion, or may want to block certain areas in their environment. Today's object detection and AR tracking techniques fall short of reliably, efficiently, and accurately supporting this use case, in particular on an (already overloaded) headset without offloading to an edge/cloud server for privacy preservation purposes.

Multi-user panoramic video streaming demands 4~6× bandwidth of a regular video with the same resolution, which poses a significant challenge on the wireless scheduling design to achieve desired performance. On the other hand, recent studies reveal that one can effectively predict the user's Field-of-View (FoV) and thus simply deliver the corresponding portion instead of the entire scenes. Motivated by this important fact, we aim to employ autoregressive process for motion prediction and analytically characterize the user's successful viewing probability as a function of the delivered portion. Then, we consider the problem of wireless scheduling design with the goal of maximizing application-level throughput (i.e., average rate for successfully viewing the desired content) and service regularity performance (i.e., how often each user gets successful views) subject to the minimum required service rate and wireless interference constraints. As such, we incorporate users' successful viewing probabilities into our scheduling design and develop a scheduling algorithm that not only asymptotically achieves the optimal application-level throughput but also provides service regularity guarantees. Finally, we perform simulations to demonstrate the efficiency of our proposed algorithm using a real dataset of users' head motion.

Motivated by the recent trend of integrating artificial intelligence into the Internet-of-Things (IoT), we consider the problem of scheduling packets from multiple sensing sources to a central controller over a wireless network. Here, packets from different sensing sources have different values or degrees of importance to the central controller for intelligent decision making. In such a setup, it is critical to provide timely and valuable information for the central controller. In this paper, we develop a parameterized maximum-weight type scheduling policy that combines both the AoI metrics and Upper Confidence Bound (UCB) estimates in its weight measure with parameter η. Here, UCB estimates balance the tradeoff between exploration and exploitation in learning and are critical for yielding a small cumulative regret. We show that our proposed algorithm yields the running average total age at most by O(N2η). We also prove that our proposed algorithm achieves the cumulative regret over time horizon T at most by O(NT/η+ √{NTlogT} ). This reveals a tradeoff between the cumulative regret and the running average total age: when increasing η, the cumulative regret becomes smaller, but is at the cost of increasing running average total age. Simulation results are provided to evaluate the efficiency of our proposed algorithm.

A new timeliness metric, called Age-of-Information (AoI), has recently attracted a lot of research interests for real-time applications with information updates. It has been extensively studied for various queueing models based on the probabilistic approaches, where the analyses heavily depend on the properties of specific distributions (e.g., the memoryless property of the exponential distribution or the i.i.d. assumption). In this work, we take an alternative new approach, the robust queueing approach, to analyze the Peak Age-of-Information (PAoI). Specifically, we first model the uncertainty in the stochastic arrival and service processes using uncertainty sets. This enables us to approximate the expected PAoI performance for very general arrival and service processes, including those exhibiting heavy-tailed behaviors or correlations, where traditional probabilistic approaches cannot be applied. We then derive a new bound on the PAoI in the single-source single-server setting. Furthermore, we generalize our analysis to two-source single-server systems with symmetric arrivals, which involves new challenges (e.g., the service times of the updates from two sources are coupled in one single uncertainty set). Finally, through numerical experiments, we show that our new bounds provide a good approximation for the expected PAoI. Compared to some well-known bounds in the literature (e.g., one based on Kingman's bound under the i.i.d. assumption) that tends to be inaccurate under light load, our new approximation is accurate under both light and high loads, both of which are critical scenarios for the AoI performance.

Mobile cloud computing enables compute-limited mobile devices to perform real-time intensive computations such as speech recognition or object detection by leveraging powerful cloud servers. An important problem in large-scale mobile cloud computing is computational offloading where each mobile device decides when and how much computation should be uploaded to cloud servers by considering the local processing delay and the cost of using cloud servers. In this paper, we develop a distributed threshold-based offloading algorithm where it uploads an incoming computing task to cloud servers if the number of tasks queued at the device reaches the threshold, and processes it locally otherwise. The threshold is updated iteratively based on the computational load and the cost of using cloud servers. We formulate the problem as a symmetric game, and characterize the sufficient and necessary conditions for the existence and uniqueness of the Nash Equilibrium (NE) assuming exponential service times. Then, we show the convergence of our proposed distributed algorithm to the NE when the NE exists. Finally, we perform extensive simulations to validate our theoretical findings and demonstrate the efficiency of our proposed distributed algorithm under various practical scenarios such as general service times, imperfect server utilization estimation, and asynchronous threshold updates.

This paper considers stochastic linear bandits with general nonlinear constraints. The objective is to maximize the expected cumulative reward over horizon $T$ subject to a set of constraints in each round $\tau\leq T$. We propose a pessimistic-optimistic algorithm for this problem, which is efficient in two aspects. First, the algorithm yields $\tilde{\cal O}\left(\left(\frac{K^{0.75}}{\delta}+d\right)\sqrt{\tau}\right)$ (pseudo) regret in round $\tau\leq T,$ where $K$ is the number of constraints, $d$ is the dimension of the reward feature space, and $\delta$ is a Slater's constant; and {\em zero} constraint violation in any round $\tau>\tau',$ where $\tau'$ is {\em independent} of horizon $T.$ Second, the algorithm is computationally efficient. Our algorithm is based on the primal-dual approach in optimization and includes two components. The primal component is similar to unconstrained stochastic linear bandits (our algorithm uses the linear upper confidence bound algorithm (LinUCB)). The computational complexity of the dual component depends on the number of constraints, but is independent of the sizes of the contextual space, the action space, and the feature space. Thus, the computational complexity of our algorithm is similar to LinUCB for unconstrained stochastic linear bandits.

The proliferation of smart mobile devices has spurred an explosive growth of mobile crowd-learning services, where service providers rely on the user community to voluntarily collect, report, and share real-time information for a collection of scattered points of interest (PoI). A critical factor affecting the future large-scale adoption of such mobile crowd-learning applications is the freshness of the crowd-learned information, which can be measured by a metric termed "age-of-information" (AoI). However, we show that the AoI of mobile crowd-learning could be arbitrarily bad under selfish and rational users' behaviors if the system is poorly designed. This motivates us to design efficient reward mechanisms to incentivize mobile users to report information in time, with the goal to keep the AoI and congestion level of each PoI low. Toward this end, we consider a simple linear AoI-based reward mechanism and analyze its AoI and congestion performances in terms of price of anarchy (PoA), which characterizes the degradation of the system efficiency due to selfish and rational behavior of users. In this paper, we consider both average maximum age and average weighted sum of age. Remarkably, we show that the proposed mechanism achieves the optimal AoI performance in terms of average maximum age asymptotically in a deterministic scenario, i.e., the corresponding PoA decreases to 0 asymptotically. Moreover, the PoA in terms of average total age under our proposed mechanism can be upper-bounded by 1/2 asymptotically. Further, we prove that the proposed mechanism achieves a bounded PoA in general stochastic cases, and the bound only depends on system parameters. Particularly, when the service rates of PoIs are symmetric in stochastic cases, the achieved PoA is upper-bounded by 1/2 asymptotically. Collectively, this work advances our understanding of information freshness in mobile crowd-learning systems.

Unmanned Aerial Vehicle (UAV) Networks have recently attracted great attention as being able to provide convenient and fast wireless connections. One central question is how to allocate a limited number of UAVs to provide wireless services across a large number of regions, where each region has dynamic arriving flows and flows depart from the system once they receive the desired amount of service (referred to as the flow-level dynamic model). In this article, we propose a MaxWeight-type scheduling algorithm taking into account sharp flow-level dynamics that efficiently redirect UAVs across a large number of regions. However, in our considered model, each flow experiences an independent fading channel and will immediately leave the system once it completes its service, which makes its evolution quite different from the traditional queueing model for wireless networks. This poses significant challenges in our performance analysis. Nevertheless, we incorporate sharp flow-dynamic into the Lyapunov-drift analysis framework, and successfully establish both throughput and heavy-traffic optimality of the proposed algorithm. Extensive simulations are performed to validate the effectiveness of our proposed algorithm.

With the rapid growth of Internet-of-Things (IoT) applications in recent years, there is a strong need for wireless uplink scheduling algorithms that determine when and which subset of a large number of users should transmit to the central controller. Different from the downlink case, the central controller in the uplink scenario typically has very limited information about the users. On the other hand, periodically collecting all such information from a large number of users typically incurs a prohibitively high communication overhead. This motivates us to investigate the development of an efficient and low-overhead uplink scheduling algorithm that is suitable for large-scale IoT applications. Specifically, we first characterize a capacity outer bound subject to the sampling constraint where only a small subset of users are allowed to use control channels for system state reporting at each time. Next, we relax the sampling constraint and propose a joint sampling and transmission algorithm, which utilizes full knowledge of channel state distributions and instantaneous queue lengths to achieve the capacity outer bound. The insights obtained from this capacity-achieving algorithm allow us to develop a low-overhead scheduling algorithm that can strictly satisfy the sampling constraint with asymptotically diminishing throughput loss.

The Age-of-Information is an important metric for investigating the timeliness performance in information-update systems. In this paper, we study the AoI minimization problem under a new Pull model with replication schemes, where a user proactively sends a replicated request to multiple servers to “pull” the information of interest. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different values of the AoI across the servers (due to the random updating processes) and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process for the servers and exponentially distributed response time, we derive a closed-form formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Then, we extend our analysis to the setting where the user aims to maximize the AoI-based utility, which represents the user's satisfaction level with respect to freshness of the received information. Furthermore, we consider a more realistic scenario where the user has no prior knowledge of the system. In this case, we reformulate the utility maximization problem as a stochastic Multi-Armed Bandit problem with side observations and leverage a special linear structure of side observations to design learning algorithms with improved performance guarantees. Finally, we conduct extensive simulations to elucidate our theoretical results and compare the performance of different algorithms. Our findings reveal that under the Pull model, waiting does not necessarily lead to aging; waiting for more than one response can often significantly reduce the AoI and improve the AoI-based utility in most scenarios.

Motivated by the Internet of Things (IoT) and Cyber-Physical Systems (CPS), we consider dynamic wireless fading networks, where each incoming flow has a random service demand and leaves the system once its service request is completed. In such networks, one of the primary goals of network algorithm design is to achieve short-term fairness that characterizes how often each flow is served, in addition to the more traditional goals such as throughput-optimality and delay-insensitivity to the flow size distribution. In wireline networks, all of these desired properties can be achieved by the round-robin scheduling algorithm. In the context of wireless networks, a natural extension of round-robin scheduling has been developed in the last few years through the use of a counter called the Time-Since-Last-Service (TSLS) that keeps track of the time that passed since the last service time of each flow. However, the performance of this round-robin-like algorithm has been primarily studied in the context of persistent flows that continuously inject packets into the network and do not ever leave the network. The analysis of dynamic flow arrivals and departures is challenging since each individual flow experiences independent wireless fading and thus, flows cannot be served in a strict round-robin manner. In this paper, we overcome this difficulty by exploring the intricate dynamics of TSLS-based algorithm and show that flows are provided round-robin-like service with a very high probability. Consequently, we then show that our algorithm can achieve throughput-optimality. Moreover, through simulations, we demonstrate that the proposed TSLS-based algorithm also exhibits desired properties such as delay-insensitivity and excellent short-term fairness performance in the presence of dynamic flows over wireless fading channels.

With the rapid growth of wireless compute-intensive services (such as image recognition, real-time language translation, or other artificial intelligence applications), efficient wireless algorithm design should not only address when and which users should transmit at each time instance (referred to as wireless scheduling) but also determine where the computation should be executed (referred to as offloading decision) with the goal of minimizing both computing latency and energy consumption. Despite the presence of a variety of earlier works on the efficient offloading design in wireless networks, to the best of our knowledge, there does not exist a work on the realistic user- level dynamic model, where each incoming user demands a heavy computation and leaves the system once its computing request is completed. To this end, we formulate a problem of an optimal offloading design in the presence of dynamic compute-intensive applications in wireless networks. Then, we show that there exists a fundamental logarithmic energy- workload tradeoff for any feasible offloading algorithm, and develop an optimal threshold-based offloading algorithm that achieves this fundamental logarithmic bound.

The proliferation of smart mobile devices has spurred an explosive growth of mobile crowd-learning services, where service providers rely on the user community to voluntarily collect, report, and share real-time information for a collection of scattered points of interest (PoI). A critical factor affecting the future large-scale adoption of such mobile crowd-learning applications is the freshness of the crowd-learned information, which can be measured by a metric termed “age-of-information” (AoI). However, we show that the AoI of mobile crowd-learning could be arbitrarily bad under selfish users' behaviors if the system is poorly designed. This motivates us to design efficient reward mechanisms to incentivize mobile users to report information in time, with the goal of keeping the AoI and congestion level of each PoI low. Toward this end, we consider a simple linear AoI-based reward mechanism and analyze its AoI and congestion performances in terms of price of anarchy (PoA), which characterizes the degradation of the system efficiency due to selfish behavior of users. Remarkably, we show that the proposed mechanism achieves the optimal AoI performance asymptotically in a deterministic scenario. Further, we prove that the proposed mechanism achieves a bounded PoA in general stochastic cases, and the bound only depends on system parameters. Particularly, when the service rates of PoIs are symmetric in stochastic cases, the achieved PoA is upperbounded by 1/2 asymptotically. Collectively, this work advances our understanding of information freshness in mobile crowd-learning systems.

In this paper, we consider the problem of joint offloading and wireless scheduling design for parallel computing applications with hard deadlines. This is motivated by the rapid growth of compute-intensive mobile parallel computing applications (e.g., real-time video analysis, language translation) that require to be processed within a hard deadline. While there are many works on joint computing and communication algorithm design, most of them focused on the minimization of average computing time and may not be applicable for mobile applications with hard deadlines. In this work, we explicitly take hard deadlines for computing tasks into account and develop a joint offloading and scheduling algorithm based on the stochastic network optimization framework. The proposed algorithm is shown to achieve average energy consumption arbitrarily close to the optimal one. However, this algorithm involves a strong coupling between offloading and scheduling decisions, which yields significant challenges on its implementation. Towards this end, we first successfully decouple the offloading and scheduling decisions in the case with one time slot deadline by exploring the intrinsic structure of the proposed algorithm. Based on this, we further implement the proposed algorithm in the general setups. Simulations are provided to corroborate our findings.

The deployment of drone small cells has emerged as a promising solution to agile provisioning of Internet backbone access for Internet of Things devices, and many other types of users/devices. In this paper, we consider the problem of deploying a set of drone cells operating on multiple channels in a target area to provide access to the backbone/core network, which is formulated as a combinatorial network utility maximization problem. Since an offline and centralized solution to such a problem is not feasible, a low-complexity and distributed online algorithm is highly desired. Therefore, we propose a measurement-aided dynamic planning (MAD-P) algorithm, where the dispatched drones perform position and channel configurations autonomously on the fly based on the real-time measurement of network throughput to solve the problem in a distributed fashion during flight with minimal centralized control. We prove that the proposed MAD-P algorithm is asymptotically optimal, and investigate how long it takes for the convergence to stationarity under the MAD-P algorithm by giving a mixing time analysis. We also derive an upper bound of the performance gap in presence of measurement errors. Simulation results are provided to validate our analytic results and demonstrate the effectiveness of our algorithm.

With the advent of Network Function Virtualization (NFV), Physical Network Functions (PNFs) are gradually being replaced by Virtual Network Functions (VNFs) that are hosted on general purpose servers. Depending on the call flows for specific services, the packets need to pass through an ordered set of network functions (physical or virtual) called Service Function Chains (SFC) before reaching the destination. Conceivably for the next few years during this transition, these networks would have a mix of PNFs and VNFs, which brings an interesting mix of network problems that are studied in this paper: (1) How to find an SFC-constrained shortest path between any pair of nodes? (2) What is the achievable SFC-constrained maximum flow? (3) How to place the VNFs such that the cost (the number of nodes to be virtualized) is minimized, while the maximum flow of the original network can still be achieved even under the SFC constraint? In this work, we will try to address such emerging questions. First, for the SFC-constrained shortest path problem, we propose a transformation of the network graph to minimize the computational complexity of subsequent applications of any shortest path algorithm. Second, we formulate the SFC-constrained maximum flow problem as a fractional multicommodity flow problem, and develop a combinatorial algorithm for a special case of practical interest. Third, we prove that the VNFs placement problem is NP-hard and present an alternative Integer Linear Programming (ILP) formulation. Finally, we conduct simulations to elucidate our theoretical results.

We consider the load-balancing design for forwarding incoming flows to access points (APs) in high-density wireless networks with both channel fading and flow-level dynamics, where each incoming flow has a certain amount of service demand and leaves the system once its service request is complete. The efficient load-balancing design is strongly needed for supporting high-quality wireless connections in high-density areas. In this work, we propose a Joint Load-Balancing and Scheduling (JLBS) Algorithm that always forwards the incoming flows to the AP with the smallest workload in the presence of flow-level dynamics and each AP always serves the flow with the best channel quality. Our analysis reveals that our proposed JLBS Algorithm not only achieves maximum system throughput, but also minimizes the total system workload in the heavy-traffic regime. Moreover, we observe from both our theoretical and simulation results that the mean total workload performance under the proposed JLBS Algorithm does not degrade as the number of APs increases, which is strongly desirable in high-density wireless networks.

We consider the problem of scheduling real-time traffic with hard deadlines in a wireless ad hoc network. In contrast to existing real-time scheduling policies that merely ensure a minimal timely throughput, our design goal is to provide guarantees on both the timely throughput and data freshness in terms of age-of-information (AoI), which is a newly proposed metric that captures the "age" of the most recently received information at the destination of a link. The main idea is to introduce the AoI as one of the driving factors in making scheduling decisions. We first prove that the proposed scheduling policy is feasibility-optimal, i.e., satisfying the per-traffic timely throughput requirement. Then, we derive an upper bound on a considered data freshness metric in terms of AoI, demonstrating that the network-wide data freshness is guaranteed and can be tuned under the proposed scheduling policy. Interestingly, we reveal that the improvement of network data freshness is at the cost of slowing down the convergence of the timely throughput. Extensive simulations are performed to validate our analytical results. Both analytical and simulation results confirm the capability of the proposed scheduling policy to improve the data freshness without sacrificing the feasibility optimality.

In recent years, virtual/augmented reality (VR/AR) technology has received great attention due to its capability of creating various levels of immersive experiences. However, current wireless VR/AR devices are quite expensive, which hinders its large-scale deployment in practice. In this demo, we present a wireless interactive VR/AR teaching system based on popular Android phones. In such a demo, when a teacher explains a 3D model, multiple students can see it from exactly the same perspective as the teacher does through VR/AR glasses. When one student has a concern or question regarding a particular part of the 3D model, he/she can point it out, and a corresponding blue cursor will appear on screens of all users. Moreover, in the absence of 3D models in Android phones, we broadcast 3D models based on their visual priorities.

With the rapid growth of Internet of Things (IoT) applications in recent years, there is a strong need for wireless uplink scheduling algorithms that determine when and which subset of a large number of users should transmit to the central controller. Different from the downlink case, the central controller in the uplink scenario typically has very limited information about the users. On the other hand, collecting all such information from a large number of users typically incurs a prohibitively high communication overhead. This motivates us to investigate the development of an efficient and low-overhead uplink scheduling algorithm that is suitable for large-scale IoT applications with limited amount of coordination from the central controller. Specifically, we first characterize a capacity outer bound subject to the sampling constraint where only a small subset of users are allowed to use control channels for system state reporting and wireless channel probing. Next, we relax the sampling constraint and propose a joint sampling and transmission algorithm, which utilizes full knowledge of channel state distributions and instantaneous queue lengths to achieve the capacity outer bound. The insights obtained from this capacity-achieving algorithm allow us to develop an efficient and low-overhead scheduling algorithm that can strictly satisfy the sampling constraint with asymptotically diminishing throughput loss. Moreover, the throughput performance of our proposed algorithm is independent of the number of users, a highly desirable property in large-scale IoT systems. Finally, we perform extensive simulations to validate our theoretical results.

There is a rich theory and plethora of algorithms in the literature aiming at the efficient scheduling of stochastic networks. These solutions are predominantly designed under the assumption of traffic demands that are independently generated at network nodes, without any requirement for synchronization among their received services. In this work, we note that many applications, including cloud computing, virtual reality, gaming, autonomous vehicular networks and collaborative design, generate traffic simultaneously at multiple nodes when they arrive, with possibly non-uniform file sizes, whose performance relies on the synchronous completion of the traffic across the network. This calls for the design of new scheduling algorithms that aims to coordinate the service of packets of the same traffic across the network. Towards this end, we propose a novel scheduling algorithm that not only accounts for the heterogeneity of the file size distributions, but also works towards synchronizing the completion time of the same traffic stream across the network. This is achieved by employing two insights that emanate from key motivating examples we develop: (1) the normalization of traffic load with respect to the non-uniform file sizes; and (2) the incorporation of deviation of normalized loads across network nodes that serve synchronized traffic. After establishing the throughput-optimality of our algorithm in general stochastic networks, we perform extensive simulations under various (spanning both wired and wireless) settings to reveal the potential completion time gains that it yields over other throughput-optimal strategies designed under the assumption of independent traffic generation.

The Age-of-Information (AoI) has recently been proposed as an important metric for investigating the timeliness performance in information-update systems. Prior studies on AoI optimization often consider a Push model, which is concerned about when and how to "push" (i.e., generate and transmit) the updated information to the user. In stark contrast, in this paper we introduce a new Pull model, which is more relevant for certain applications (such as the real-time stock quotes service), where a user sends requests to the servers to proactively "pull" the information of interest. Moreover, we propose to employ request replication to reduce the AoI. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different levels of information freshness and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process at the servers and exponentially distributed response time, we derive a closed-form formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Finally, we conduct numerical simulations to elucidate our theoretical results. Our findings show that waiting for more than one response can significantly reduce the AoI in most scenarios.

Round robin and its variants are well known scheduling policies that are popular in wireline networks due to their throughput optimality, delay insensitivity to file size distributions and short-term fairness. The latter two properties are also extremely important for emerging wireless applications, such as Internet of Things and cyber-physical systems. However, there is no direct wireless analog of round robin with all the desirable properties in wireless networks, where wireless interference and channel fading are predominant. The main reason is due to the fact that it is very difficult to even define what round robin means in wireless networks. This motivates us to develop a round-robin-like algorithm in wireless networks that has nice properties as round robin in wireline networks. To that end, we utilize a counter called the Time-Since-Last-Service (TSLS) that keeps track of the time of each file since its last service, and observe that scheduling a file with maximum TSLS in a single server is equivalent to serving files in a round robin fashion. Based on this key observation, we develop a TSLS-based algorithm that balances the tradeoff between the TSLS value and the channel rate for each link and show that the proposed algorithm achieves maximum system throughput, which demands a nontraditional approach due to the abrupt dynamics of the TSLS metrics. Numerous simulations are provided to validate its desired properties such as delay insensitivity and excellent short-term fairness performance as in the case of round robin algorithms of wireline networks.

We study cloud-storage systems with a very large number of files stored in a very large number of servers. In such systems, files are either replicated or coded to ensure reliability, i.e., file recovery from server failures. This redundancy in storage can further be exploited to improve system performance (mean file access delay) through appropriate load-balancing (routing) schemes. However, it is unclear whether coding or replication is better from a system performance perspective since the corresponding queueing analysis of such systems is, in general, quite difficult except for the trivial case when the system load asymptotically tends to zero. Here, we study the more difficult case where the system load is not asymptotically zero. Using the fact that the system size is large, we obtain a mean-field limit for the steady-state distribution of the number of file access requests waiting at each server. We then use the mean-field limit to show that, for a given storage capacity per file, coding strictly outperforms replication at all traffic loads while improving reliability. Further, the factor by which the performance improves in the heavy-traffic is at least as large as in the light-traffic case. Finally, we validate these results through extensive simulations.

We consider the design of throughput-optimal scheduling policies in multihop wireless networks that also possess good mean delay performance and provide regular service for all links-critical metrics for real-time applications. To that end, we study a parametric class of maximum-weight-type scheduling policies, called Regular Service Guarantee (RSG) Algorithm, where each link weight consists of its own queue length and a counter that tracks the time since the last service, namely Time-Since-Last-Service (TSLS). The RSG Algorithm not only is throughput-optimal, but also achieves a tradeoff between the service regularity performance and the mean delay, i.e., the service regularity performance of the RSG Algorithm improves at the cost of increasing mean delay. This motivates us to investigate whether satisfactory service regularity and low mean-delay can be simultaneously achieved by the RSG Algorithm by carefully selecting its design parameter. To that end, we perform a novel Lyapunov-drift-based analysis of the steady-state behavior of the stochastic network. Our analysis reveals that the RSG Algorithm can minimize the total mean queue length to establish mean delay optimality under heavily loaded conditions as long as the design parameter weighting for the TSLS scales no faster than the order of [1/({5}√{ε})], where ε measures the closeness of the network load to the boundary of the capacity region. To the best of our knowledge, this is the first work that provides regular service to all links while also achieving heavy-traffic optimality in mean queue lengths.

We consider a system in which two nodes take correlated measurements of a random source with time-varying and unknown statistics. The observations of the source at the first node are to be losslessly replicated with a given probability of outage at the second node, which receives data from the first node over a constant-rate channel. We develop a system and associated strategies for joint distributed source coding (encoding and decoding) and transmission control in order to achieve low end-to-end delay. Slepian-Wolf coding in its traditional form cannot be applied in our scenario, since the encoder requires the joint statistics of the observations and the associated decoding delay is very high. We analytically evaluate the performance of our strategies and show that the delay achieved by them are order optimal, as the conditional entropy of the source approaches to the channel rate. We also evaluate the performance of our algorithms based on real-world experiments using two cameras recording videos of a scene at different angles. Having realized our schemes, we demonstrated that, even with a very low-complexity quantizer, a compression ratio of approximately 50% is achievable for lossless replication at the decoder, at an average delay of a few seconds.

It is well-known that maximum weight scheduling, with link weights which are either functions of queue lengths or the ages of the Head-of-Line (HoL) packets in each queue, maximizes the throughput region of wireless networks with persistent flows. In particular, with only persistent flows, it does not matter for throughput optimality whether one uses queue lengths or HoL ages as weights. In this paper, we show the following interesting result: when some flows in the network are dynamic (i.e., they arrive and depart from the network and are not persistent), then HoL-age-based scheduling algorithms are throughput-optimal while it has previously been shown that queue-length-based algorithms are not. This reveals that, age-based algorithms are universal in the sense that their throughput optimality does not depend on whether the arriving traffic is persistent or not. We also present a distributed implementation of the proposed age-based algorithm using CSMA techniques, where each flow only knows its own age and carrier sensing information. Finally, we support our analytical results through simulations. The proof of throughput optimality may be interesting in its own right: it uses a novel Lyapunov function which is the sum of the ages of all the packets in the network.

The backpressure scheduling algorithm for multihop wireless networks is known to be throughput optimal, but it requires each node to maintain per-destination queues. Recently, a clever generalization of processor sharing has been proposed which is also throughput optimal, but which only uses per-link queues. Here we propose another algorithm called Queue Proportional Rate Allocation (QPRA) which also only uses per-link queues, and allocates service rates to links in proportion to their queue-lengths and employs the Serve-In-Random-Order (SIRO) discipline within each link. Through fluid limit techniques and using a novel Lyapunov function, we show that the QPRA achieves the maximum throughput. We demonstrate an advantage of QPRA by showing that, for the so-called primary interference model, it is able to develop a low-complexity scheduling scheme which approximates QPRA and achieves a constant fraction of the maximum throughput region, independent of network size.

It is energy-consuming and operationally cumbersome for all users to continuously estimate the channel quality before each transmission decision in opportunistic scheduling over wireless fading channels. This observation motivates us to understand whether and how opportunistic gains can still be achieved with significant reductions in channel probing requirements and without centralized coordination amongst the competing users. To that end, we first study a simple scenario that motivates us to consider the general setup and develop probing and transmission schemes that are amenable to distributed implementation. After characterizing the maximum achievable throughput region under the probing constraints, we provide an optimal probing algorithm. Noting the difficulties in the implementation of the centralized solution, we develop a novel Sequential Greedy Probing (SGP) algorithm, which is naturally well-suited for physical implementation and distributed operation. We show that the SGP algorithm is optimal in the important scenario of symmetric and independent ON-OFF fading channels. Then, we study a variant of the SGP algorithm in general fading channels to obtain its efficiency ratio as an explicit function of the channel statistics and rates, and note its tightness in the symmetric and independent ON-OFF fading scenario. We further discuss the distributed implementation of these greedy solutions by using the Fast-CSMA technique.

In this paper, we study the design of joint flow-rate control and scheduling policies in multihop wireless networks for achieving maximum network utility with provably optimal convergence speed. Fast convergence is especially important in wireless networks that are dominated by the dynamics of incoming and outgoing flows as well as the time-sensitive applications. Yet, the design of fast converging policies in wireless networks is complicated by: 1) the interference-constrained communication capabilities, and 2) the finite set of transmission rates to select from due to operational and physical-layer constraints. We tackle these challenges by explicitly incorporating such discrete constraints to understand their impact on the convergence speed at which the running average of the received service rates and the network utility over a finite time horizon T converges to their limits. In particular, we establish a fundamental fact that the convergence speed of any feasible policy cannot be faster than Ω(1/T) under both the rate and utility metrics. Then, we develop an algorithm that achieves this optimal convergence speed in both metrics. We also show that the well-known dual algorithm can achieve the optimal convergence speed in terms of its utility value. These results reveal the interesting fact that the convergence speed of rates and utilities in wireless networks is dominated by the discrete choices of scheduling and transmission rates, which also implies that the use of higher-order flow-rate controllers with fast convergence guarantees cannot overcome the aforementioned fundamental limitation.

Motivated by the regular service requirements of video applications for improving quality of experience (QoE) of users, we consider the design of scheduling strategies in multihop wireless networks that not only maximize system throughput but also provide regular interservice times for all links. Since the service regularity of links is related to the higher-order statistics of the arrival process and the policy operation, it is challenging to characterize and analyze directly. We overcome this obstacle by introducing a new quantity, namely the time-since-last-service (TSLS), which tracks the time since the last service. By combining it with the queue length in the weight, we propose a novel maximum-weight-type scheduling policy, called Regular Service Guarantee (RSG) Algorithm. The unique evolution of the TSLS counter poses significant challenges for the analysis of the RSG Algorithm. To tackle these challenges, we first propose a novel Lyapunov function to show the throughput optimality of the RSG Algorithm. Then, we prove that the RSG Algorithm can provide service regularity guarantees by using the Lyapunov-drift-based analysis of the steady-state behavior of the stochastic processes. In particular, our algorithm can achieve a degree of service regularity within a factor of a fundamental lower bound we derive. This factor is a function of the system statistics and design parameters and can be as low as two in some special networks. Our results, both analytical and numerical, exhibit significant service regularity improvements over the traditional throughput-optimal policies, which reveals the importance of incorporating the metric of time-since-last-service into the scheduling policy for providing regulated service.

In this paper, we study the design of joint flow rate control and scheduling policies in multi-hop wireless networks for achieving maximum network utility with provably optimal convergence speed. Fast convergence is especially important in wireless networks which are dominated by the dynamics of incoming and outgoing flows as well as the time sensitive applications. Yet, the design of fast converging policies in wireless networks is complicated by: (i) the interference-constrained communication capabilities, and (ii) the finite set of transmission rates to select from due to operational and physical-layer constraints. We tackle these challenges by explicitly incorporating such discrete constraints to understand their impact on the convergence speed at which the running average of the received service rates and the network utility converges to their limits. In particular, we establish a fundamental fact that the convergence speed of any feasible policy cannot be faster than Ω (1/T) under both the T rate and utility metrics. Then, we develop an algorithm that achieves this optimal convergence speed in both metrics. We also show that the well-known dual algorithm can achieve the optimal convergence speed in terms of its utility value. These results reveal the interesting fact that the convergence speed of rates and utilities in wireless networks is dominated by the discrete choices of scheduling and transmission rates, which also implies that the use of higher-order flow rate controllers with fast convergence guarantees cannot overcome the aforementioned fundamental limitation.

Motivated by the low-jitter requirements of streaming multi-media traffic, we focus on the development of scheduling strategies under fading conditions that not only maximize throughput performance but also provide regular inter-service times to users. Since the service regularity of the traffic is related to the higher-order statistics of the arrival process and the policy operation, it is highly challenging to characterize and analyze directly. We overcome this obstacle by introducing a new quantity, namely the time-since-last-service, which has a unique evolution different from a tradition queue. By combining it with the queue-length in the weight, we propose a novel maximum-weight type scheduling policy that is proven to be throughput-optimal and also provides provable service regularity guarantees. In particular, our algorithm can achieve a degree of service regularity within a constant factor of a fundamental lower bound we derive. This constant is independent of the higher-order statistics of the arrival process and can be as low as two. Our results, both analytical and numerical, exhibit significant service regularity improvements over the traditional throughput-optimal policies, which reveals the importance of incorporating the metric of time-since-last-service into the scheduling policy for providing regulated service.

We consider the design of throughput-optimal scheduling policies in multi-hop wireless networks that also possess good mean delay performance and provide regular service for all links -- critical metrics for real-time applications. To that end, we study a parametric class of maximum-weight type scheduling policies with parameter α ≥ 0, called Regular Service Guarantee (RSG) Algorithm, where each link weight consists of its own queue-length and a counter that tracks the time since the last service. This policy has been shown to be throughput-optimal and to provide more regular service as the parameter α increases, however at the cost of increasing mean delay.

Recently, low-complexity and distributed Carrier Sense Multiple Access (CSMA)-based scheduling algorithms have attracted extensive interest due to their throughput-optimal characteristics in general network topologies. However, these algorithms are not well-suited for time-varying environments (i.e., serving real-time traffic under time-varying channel conditions in wireless networks) for two reasons: (1) the mixing time of the underlying CSMA Markov Chain grows with the size of the network, which, for large networks, generates unacceptable delay for deadline-constrained traffic; (2) since the dynamic CSMA parameters are influenced by the arrival and channel state processes, the underlying CSMA Markov Chain may not converge to a steady-state under strict deadline constraints and fading channel conditions. In this paper, we attack the problem of distributed scheduling for time-varying environments. Specifically, we propose a Fast-CSMA (FCSMA) policy in fully-connected topologies, which converges much faster than the existing CSMA algorithms and thus yields significant advantages for time-varying applications. Then, we design optimal policies based on FCSMA techniques in two challenging and important scenarios in wireless networks for scheduling inelastic traffic with/without channel state information (CSI) over wireless fading channels.

It is energy-consuming and operationally cumbersome for all users to continuously estimate the channel quality before each data transmission decision in opportunistic scheduling over wireless fading channels. This observation motivates us to understand whether and how opportunistic gains can still be achieved with significant reductions in channel probing requirements and without centralized coordination amongst the competing users. In this work, we first provide an optimal centralized probing and transmission algorithm under the probing constraints. Noting the difficulties in the implementation of the centralized solution, we develop a novel Sequential Greedy Probing (SGP) algorithm by using the maximum-minimums identity, which is naturally well-suited for physical implementation and distributed operation. We show that the SGP algorithm is optimal in the important scenario of symmetric and independent ON-OFF fading channels. Then, we study a variant of the SGP algorithm in general fading channels to obtain its efficiency ratio as an explicit function of the channel statistics and rates, and note its tightness in the symmetric and independent ON-OFF fading scenario. We further expand on the distributed implementation of these greedy solutions by using the Fast-CSMA technique.

There has been substantial interest over the last decade in developing low complexity decentralized scheduling algorithms in wireless networks. In this context, the queue-length based Carrier Sense Multiple Access (CSMA) scheduling algorithms have attracted significant attention because of their attractive throughput guarantees. However, the CSMA results rely on the mixing of the underlying Markov chain and their performance under fading channel states is unknown. In this work, we formulate a partially decentralized randomized scheduling algorithm for a two transmitter receiver pair set up and investigate its stability properties. Our work is based on the Fast-CSMA (FCSMA) algorithm first developed in [1] and we extend its results to a signal to interference noise ratio (SINR) based interference model in which one or more transmitters can transmit simultaneously while causing interference to the other. In order to improve the performance of the system, we split the traffic arriving at the transmitter into schedule based queues and combine it with the FCSMA based scheduling algorithm. We theoretically examine the performance of our algorithm in both non-fading and fading environment and characterize the set of arrival rates which can be stabilized by our proposed algorithm.

Randomization is a powerful and pervasive strategy for developing efficient and practical transmission scheduling algorithms in interference-limited wireless networks. Yet, despite the presence of a variety of earlier works on the design and analysis of particular randomized schedulers, there does not exist an extensive study of the limitations of randomization on the efficient scheduling in wireless networks. In this paper, we aim to fill this gap by proposing a common modeling framework and three functional forms of randomized schedulers that utilize queue-length information to probabilistically schedule nonconflicting transmissions. This framework not only models many existing schedulers operating under a timescale separation assumption as special cases, but it also contains a much wider class of potential schedulers that have not been analyzed. We identify some sufficient and some necessary conditions on the network topology and on the functional forms used in the randomization for throughput optimality. Our analysis reveals an exponential and a subexponential class of functions that exhibit differences in the throughput optimality. Also, we observe the significance of the network's scheduling diversity for throughput optimality as measured by the number of maximal schedules each link belongs to. We further validate our theoretical results through numerical studies.

Randomization is a powerful and pervasive strategy for developing efficient and practical transmission scheduling algorithms in interference-limited wireless networks. Yet, despite the presence of a variety of earlier works on the design and analysis of particular randomized schedulers, there does not exist an extensive study of the limitations of randomization on the efficient scheduling in wireless networks. In this work, we aim to fill this gap by proposing a common modeling framework and three functional forms of randomized schedulers that utilize queue-length information to probabilistically schedule non-conflicting transmissions. This framework not only models many existing schedulers operating under a time-scale separation assumption as special cases, but it also contains a much wider class of potential schedulers that have not been analyzed. Our main results are the identification of necessary and sufficient conditions on the network topology and on the functional forms used in the randomization for throughput-optimality. Our analysis reveals an exponential and a sub-exponential class of functions that exhibit differences in the throughput-optimality. Also, we observe the significance of the network's scheduling diversity for throughput-optimality as measured by the number of maximal schedules each link belongs to. We further validate our theoretical results through numerical studies.

Abstract IEEE 802.11 protocol supports adaptive rate mechanism, which selects the transmission rate according to the condition of the wireless channel, to enhance the system performance. Thus, research of multi‐rate IEEE 802.11 medium access control (MAC) performance has become one of the hot research topics. In this paper, we study the performance of multi‐rate IEEE 802.11 MAC over a Gaussian channel. An accurate analytical model is presented to compute the system saturation throughput. We validate our model in both single‐rate and multi‐rate networks through various simulations. The results show that our model is accurate and channel error has a significant impact on system performance. In addition, our numerical results show that the performance of single‐rate IEEE 802.11 DCF with basic access method is better than that with RTS/CTS mechanism in a high‐rate and high‐load network and vice versa. In a multi‐rate network, the performance of IEEE 802.11 DCF with RTS/CTS mechanism is better than that with basic access method in a congested and error‐prone wireless environment. Copyright © 2008 John Wiley & Sons, Ltd.