This paper focuses on the problem of automatic link selection in multi-channel multiple access control using bandit feedback. In particular, a controller assigns multiple users to multiple channels in a time slotted system, where in each time slot at most one user can be assigned to a given channel and at most one channel can be assigned to a given user. Given that user$i$is assigned to channel$j$, the transmission fails with a fixed probability$f_{i, j}$. The failure probabilities are not known to the controller. The assignments are made dynamically using success/failure feedback. The goal is to maximize the time average utility, where we consider an arbitrary (possibly nonsmooth) concave and entrywise nondecreasing utility function. The problem of merely maximizing the total throughput has a solution of always assigning the same user-channel pairs and can be unfair to certain users, particularly when the number of channels is less than the number of users. Instead, our scheme allows various types of fairness, such as proportional fairness, maximizing the minimum, or combinations of these by defining the appropriate utility function. We propose an algorithm for this task that is adaptive and gets within$\mathcal{O}\left(\log (T) / T^{1 / 3}\right)$of optimality over any interval of$T$consecutive slots over which the success probabilities do not change. This performance is improved to$\mathcal{O}(1 / \sqrt{T})$for single-channel problems with a minimum constraint on the rate of transmission attempts per user.

Future generation wireless technologies are expected to serve an increasingly dense and dynamic population of users that generate short bundles of information to be transferred over the shared spectrum. This calls for new distributed and low-overhead Multiple-Access-Control (MAC) strategies to serve such dynamic demands with spectral efficiency characteristics. In this work, we address this need by identifying and developing two fundamentally different MAC paradigms: (i) congestion-based paradigm that estimates the congestion level in the system and adapts to it; and (ii) age-based paradigm that prioritizes demands based on their ages. Despite their apparent differences, we develop policies under each paradigm in a generic multi-channel access scenario that are provably throughput-optimal when they employ any asymptotically-efficient channel encoding/decoding mechanism. We also characterize the stability regions of the two designs, and investigate the conditions under which one design outperforms the other. We perform extensive simulations to validate the theoretical claims and investigate the non-asymptotic performances of our designs.

This paper proves an impossibility result for stochastic network utility maximization for multi-user wireless systems, including multiple access and broadcast systems. Every time slot an access point observes the current channel states for each user and opportunistically selects a vector of transmission rates. Channel state vectors are assumed to be independent and identically distributed with an unknown probability distribution. The goal is to learn to make decisions over time that maximize a concave utility function of the running time average transmission rate of each user. Recently it was shown that a stochastic Frank-Wolfe algorithm converges to utility-optimality with an error of$O(\log (T)/T)$, where$T$is the time the algorithm has been running. An existing$\Omega (1/T)$converse is known. The current paper improves the converse to$\Omega (\log (T)/T)$, which matches the known achievability result. It does this by constructing a particular (simple) system for which no algorithm can achieve a better performance. The proof uses a novel reduction of the opportunistic scheduling problem to a problem of estimating a Bernoulli probability$p$from independent and identically distributed samples. Along the way we refine a regret bound for Bernoulli estimation to show that, for any sequence of estimators, the set of values$p \in [{0,1}]$under which the estimators perform poorly has measure at least 1/6.

This paper presents a network layer model for a wireless multiple access system with both persistent and nonpersistent users. There is a single access point with multiple identical channels. Each user who wants to send a file first scans a subset of the channels to find one that is idle. If at least one idle channel is found, the user transmits a file over that channel. If no idle channel is found, a persistent user will repeat the access attempt at a later time, while a nonpersistent user will leave. This is a useful mathematical model for situations where a group of persistent users stay near an access point for an extended period of time while nonpersistent users come and go. Users have heterogeneous activity behavior, file upload rates, and service durations. The system is a complex multi-dimensional Markov chain. The steady state probabilities are found by exploiting a latent reversibility property and leveraging a discrete Fourier transform. This enables simple expressions for throughput and blocking probability.

With the adoption of 5G wireless technology and the Internet-of-Things (IoT) networking, there is a growing interest in serving a dense population of low-complexity devices over shared wireless uplink channels. Different from the traditional scenario of persistent users, in these new networks each user is expected to generate only small bundles of information intermittently. The highly dynamic nature of such demand and the typically low-complexity nature of the user devices calls for a new MAC paradigm that is geared for low-overhead and distributed operation of dynamic users.In this work, we address this need by developing a generic MAC mechanism for estimating the number and coordinating the activation of dynamic users for efficient utilization of the time-frequency resources with minimal public feedback from the common receiver. We fully characterize the throughput and delay performance of our design under a basic threshold-based multi-channel capacity condition, which allows for the use of different channel utilization schemes. Moreover, we consider the Successive-Interference-Cancellation (SIC) Multi-Channel MAC scheme as a specific choice in order to demonstrate the performance of our design for a spectrally-efficient (albeit idealized) scheme. Under the SIC encoding/decoding scheme, we prove that our low-overhead distributed MAC can support maximum throughput, which establishes the efficiency of our design. Under SIC, we also demonstrate how the basic threshold-based success model can be relaxed to be adapted to the performance of a non-ideal success model.

This paper considers online optimization of a renewal-reward system. A controller performs a sequence of tasks back-to-back. Each task has a random vector of parameters, called the task type vector, that affects the task processing options and also affects the resulting reward and time duration of the task. The probability distribution for the task type vector is unknown and the controller must learn to make efficient decisions so that time-average reward converges to optimality. Prior work on such renewal optimization problems leaves open the question of optimal convergence time. This paper develops an algorithm with an optimality gap that decays like $O(1/\sqrt{k})$, where $k$ is the number of tasks processed. The same algorithm is shown to have faster $O(\log(k)/k)$ performance when the system satisfies a strong concavity property. The proposed algorithm uses an auxiliary variable that is updated according to a classic Robbins-Monro iteration. It makes online scheduling decisions at the start of each renewal frame based on this variable and the observed task type. A matching converse is obtained for the strongly concave case by constructing an example system for which all algorithms have performance at best $\Omega(\log(k)/k)$. A matching $\Omega(1/\sqrt{k})$ converse is also shown for the general case without strong concavity.

This paper proves an impossibility result for stochastic network utility maximization for multi-user wireless systems, including multi-access and broadcast systems. Every time slot an access point observes the current channel states and opportunistically selects a vector of transmission rates. Channel state vectors are assumed to be independent and identically distributed with an unknown probability distribution. The goal is to learn to make decisions over time that maximize a concave utility function of the running time average transmission rate of each user. Recently it was shown that a stochastic Frank-Wolfe algorithm converges to utility-optimality with an error of O(log(T)/T), where T is the time the algorithm has been running. An existing Ω(1/T) converse is known. The current paper improves the converse to Ω(log(T)/T), which matches the known achievability result. The proof uses a reduction from the opportunistic scheduling problem to a Bernoulli estimation problem. Along the way, it refines a result on Bernoulli estimation.

This paper considers online convex optimization over a complicated constraint set, which typically consists of multiple functional constraints and a set constraint. The conventional online projection algorithm (Zinkevich, 2003) can be difficult to implement due to the potentially high computation complexity of the projection operation. In this paper, we relax the functional constraints by allowing them to be violated at each round but still requiring them to be satisfied in the long term. This type of relaxed online convex optimization (with long term constraints) was first considered in Mahdavi et al. (2012). That prior work proposes an algorithm to achieve $O(\sqrt{T})$ regret and $O(T^{3/4})$ constraint violations for general problems and another algorithm to achieve an $O(T^{2/3})$ bound for both regret and constraint violations when the constraint set can be described by a finite number of linear constraints. A recent extension in Jenatton et al. (2016) can achieve $O(T^{\max\{\theta,1-\theta\}})$ regret and $O(T^{1-\theta/2})$ constraint violations where $\theta\in (0,1)$. The current paper proposes a new simple algorithm that yields improved performance in comparison to prior works. The new algorithm achieves an $O(\sqrt{T})$ regret bound with $O(1)$ constraint violations.

This paper considers the fundamental convergence time for opportunistic scheduling over time-varying channels. The channel state probabilities are unknown and algorithms must perform some type of estimation and learning while they make decisions to optimize network utility. Existing schemes can achieve a utility within ε of optimality, for any desired ε > 0, with convergence and adaptation times of O(1/ε2). This paper shows that if the utility function is concave and smooth, then O(log(1/ε)/ε) convergence time is possible via an existing stochastic variation on the Frank-Wolfe algorithm, called the RUN algorithm. Furthermore, a converse result is proven to show it is impossible for any algorithm to have convergence time better than O(1/ε), provided the algorithm has no a-priori knowledge of channel state probabilities. Hence, RUN is within a logarithmic factor of convergence time optimality. However, RUN has a vanishing stepsize and hence has an infinite adaptation time. Using stochastic Frank-Wolfe with a fixed stepsize yields improved O(1/ε2) adaptation time, but convergence time increases to O(1/ε2), similar to existing drift-plus-penalty based algorithms. This raises important open questions regarding optimal adaptation.

This paper considers utility optimal power control for energy-harvesting wireless devices with a finite capacity battery. The distribution information of the underlying wireless environment and harvestable energy is unknown, and only outdated system state information is known at the device controller. This scenario shares similarity with Lyapunov opportunistic optimization and online learning but is different from both. By a novel combination of Zinkevich's online gradient learning technique and the drift-plus-penalty technique from Lyapunov opportunistic optimization, this paper proposes a learning-aided algorithm that achieves utility within O(ϵ) of the optimal, for any desired ϵ > 0, by using a battery with an O(1/ϵ) capacity. The proposed algorithm has low complexity and makes power investment decisions based on system history, without requiring knowledge of the system state or its probability distribution.

This paper considers utility optimal power control for energy harvesting wireless devices with a finite capacity battery. The distribution information of the underlying wireless environment and harvestable energy is unknown and only outdated system state information is known at the device controller. This scenario shares similarity with Lyapunov opportunistic optimization and online learning but is different from both. By a novel combination of Zinkevich's online gradient learning technique and the drift-plus-penalty technique from Lyapunov opportunistic optimization, this paper proposes a learning-aided algorithm that achieves utility within O (ϵ) of the optimal, for any desired ϵ > 0, by using a battery with an 0 (1/ϵ) capacity. The proposed algorithm has low complexity and makes power investment decisions based on system history, without requiring knowledge of the system state or its probability distribution.

We propose a new primal-dual homotopy smoothing algorithm for a linearly constrained convex program, where neither the primal nor the dual function has to be smooth or strongly convex. The best known iteration complexity solving such a non-smooth problem is $\mathcal{O}(\varepsilon^{-1})$. In this paper, we show that by leveraging a local error bound condition on the dual function, the proposed algorithm can achieve a better primal convergence time of $\mathcal{O}\l(\varepsilon^{-2/(2+\beta)}\log_2(\varepsilon^{-1})\r)$, where $\beta\in(0,1]$ is a local error bound parameter. As an example application, we show that the distributed geometric median problem, which can be formulated as a constrained convex program, has its dual function non-smooth but satisfying the aforementioned local error bound condition with $\beta=1/2$, therefore enjoying a convergence time of $\mathcal{O}\l(\varepsilon^{-4/5}\log_2(\varepsilon^{-1})\r)$. This result improves upon the $\mathcal{O}(\varepsilon^{-1})$ convergence time bound achieved by existing distributed optimization algorithms. Simulation experiments also demonstrate the performance of our proposed algorithm.

The backpressure algorithm has been widely used as a distributed solution to the problem of joint rate control and routing in multi-hop data networks. By controlling a parameter V in the algorithm, the backpressure algorithm can achieve an arbitrarily small utility optimality gap. However, this in turn brings in a large queue length at each node and hence causes large network delay. This phenomenon is known as the fundamental utility-delay tradeoff. The best known utility-delay tradeoff for general networks is [O(1/V), O(V)] and is attained by a backpressure algorithm based on a drift-pluspenalty technique. This may suggest that to achieve an arbitrarily small utility optimality gap, the existing backpressure algorithms necessarily yield an arbitrarily large queue length. However, this paper proposes a new backpressure algorithm that has a vanishing utility optimality gap, so utility converges to exact optimality as the algorithm keeps running, while queue lengths are bounded throughout by a finite constant. The technique uses backpressure and drift concepts with a new method for convex programming.

This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich's OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d. generated at each round and are disclosed to the decision maker only after the decision is made. This formulation arises naturally when decisions are restricted by stochastic environments or deterministic environments with noisy observations. It also includes many important problems as special case, such as OCO with long term constraints, stochastic constrained convex optimization, and deterministic constrained convex optimization. To solve this problem, this paper proposes a new algorithm that achieves $O(\sqrt{T})$ expected regret and constraint violations and $O(\sqrt{T}\log(T))$ high probability regret and constraint violations. Experiments on a real-world data center scheduling problem further verify the performance of the new algorithm.

This paper considers a cost minimization problem for data centers with N servers and randomly arriving service requests. A central router decides which server to use for each new request. Each server has three types of states (active, idle, and setup) with different costs and time durations. The servers operate asynchronously over their own states and can choose one of multiple sleep modes when idle. We develop an online distributed control algorithm so that each server makes its own decisions. The request queues are bounded and the overall time average cost is near optimal with probability 1. First the algorithm does not need probability information for the arrival rate or job sizes. Finally, an improved algorithm that uses a single queue is developed via a “virtualization” technique, which is shown to provide the same (near optimal) costs. Simulation experiments on a real data center traffic trace demonstrate the efficiency of our algorithm compared with other existing algorithms.

This paper considers dynamic transmit covariance design in point-to-point multiple-input multiple-output fading systems with unknown channel state distributions and inaccurate channel state information subject to both long-term and shortterm power constraints. First, the case of instantaneous but possibly inaccurate channel state information at the transmitter (CSIT) is treated. By extending the drift-plus-penalty technique, a dynamic transmit covariance policy is developed and is shown to approach optimality with an O(δ) gap, where δ is the inaccuracy measure of CSIT, regardless of the channel state distribution and without requiring knowledge of this distribution. Next, the case of delayed and inaccurate channel state information is considered. The optimal transmit covariance solution that maximizes the ergodic capacity is fundamentally different in this case, and a different online algorithm based on convex projections is developed. The proposed algorithm for this delayed-CSIT case also has an O(δ) optimality gap, where δ is again the inaccuracy measure of CSIT.

This paper considers dynamic power allocation in MIMO fading systems with unknown channel state distributions. First, the ideal case of perfect instantaneous channel state information at the transmitter (CSIT) is treated. Using the drift-plus-penalty method, a dynamic power allocation policy is developed and shown to approach optimality, regardless of the channel state distribution and without requiring knowledge of this distribution. Next, the case of delayed and quantized channel state information is considered. Optimal utility is fundamentally different in this case, and a different online algorithm is developed that is based on convex projections. The proposed algorithm for this delayed-CSIT case is shown to have an O (δ) optimality gap, where δ is the quantization error of CSIT.

This paper considers optimization of power and delay in a time-varying wireless link using rateless codes. The link serves a sequence of variable-length packets. Each packet is coded and transmitted over multiple slots. Channel conditions can change from slot to slot and are unknown to the transmitter. The amount of mutual information accumulated on each slot depends on the random channel realization and the power used. The goal is to minimize average service delay subject to an average power constraint. We formulate this problem as a frame-based stochastic optimization problem and solve it via an online algorithm. We show that the subproblem within each frame is a simple integer program which can be effectively solved using a dynamic program. The optimality of this online algorithm is proved using the frame-based Lyapunov drift analysis.

Backpressure routing, in which packets are preferentially transmitted over links with high queue differentials, offers the promise of throughput-optimal operation for a wide range of communication networks. However, when traffic load is low, backpressure methods suffer from long delays. This is of particular concern in intermittent encounter-based mobile networks which are already delay-limited due to the sparse and highly dynamic network connectivity. While state of the art mechanisms for such networks have proposed the use of redundant transmissions to improve delay, they do not work well when traffic load is high. In this paper we propose backpressure with adaptive redundancy (BWAR), a novel hybrid approach that provides the best of both worlds. This approach is robust, distributed, and does not require any prior knowledge of network load conditions. We also present variants of BWAR that remove redundant packets via a timeout mechanism, and that improve energy use. These algorithms are evaluated by mathematical analysis and by simulations of real traces of taxis in Beijing, China. The simulations confirm that BWAR outperforms traditional backpressure at low load, while outperforming encounter-routing schemes (Spray and Wait and Spray and Focus) at high load.

This paper considers a problem where multiple devices make repeated decisions based on their own observed events. The events and decisions at each time-step determine the values of a utility function and a collection of penalty functions. The goal is to make distributed decisions over time to maximize time-average utility subject to time-average constraints on the penalties. An example is a collection of power-constrained sensors that repeatedly report their own observations to a fusion center. Maximum time-average utility is fundamentally reduced because devices do not know the events observed by others. Optimality is characterized for this distributed context. It is shown that optimality is achieved by correlating device decisions through a commonly known pseudo-random sequence. An optimal algorithm is developed that chooses pure strategies at each time-step based on a set of time-varying weights.

This paper considers a wireless link with randomly arriving data that are queued and served over a time-varying channel. It is known that any algorithm that comes within ε of the minimum average power required for queue stability must incur average queue size at least Ω(log(1/ε)). However, the optimal convergence time is unknown. This paper develops a scheduling algorithm that, for any ε > 0, achieves the optimal O(log(1/ε)) average queue size tradeoff with a convergence time of O(log(1/ε)/ε). An example system is presented for which all algorithms require convergence time at least Ω(1/ε), and so the proposed algorithm is within a logarithmic factor of the optimal convergence time. The method uses the simple drift-plus-penalty technique with an improved convergence time analysis.

This paper treats power-aware throughput maximization in a multiuser file downloading system. Each user can receive a new file only after its previous file is finished. The file state processes for each user act as coupled Markov chains that form a generalized restless bandit system. First, an optimal algorithm is derived for the case of one user. The algorithm maximizes throughput subject to an average power constraint. Next, the one-user algorithm is extended to a low-complexity heuristic for the multiuser problem. The heuristic uses a simple online index policy. In a special case with no power-constraint, the multiuser heuristic is shown to be throughput-optimal. Simulations are used to demonstrate effectiveness of the heuristic in the general case. For simple cases where the optimal solution can be computed offline, the heuristic is shown to be near-optimal for a wide range of parameters.

We consider the problem of simultaneous on-demand streaming of stored video to multiple users in a multicell wireless network where multiple unicast streaming sessions are run in parallel and share the same frequency band. Each streaming session is formed by the sequential transmission of video “chunks,” such that each chunk arrives into the corresponding user playback buffer within its playback deadline. We formulate the problem as a network utility maximization (NUM) where the objective is to fairly maximize users' video streaming quality of experience (QoE) and then derive an iterative control policy using Lyapunov optimization, which solves the NUM problem up to any level of accuracy and yields an online protocol with control actions at every iteration decomposing into two layers interconnected by the users' request queues : 1) a video streaming adaptation layer reminiscent of dynamic adaptive streaming over HTTP (DASH), implemented at each user node; and 2) a transmission scheduling layer where a max-weight scheduler is implemented at each base station. The proposed chunk request scheme is a pull strategy where every user opportunistically requests video chunks from the neighboring base stations and dynamically adapts the quality of its requests based on the current size of the request queue. For the transmission scheduling component, we first describe the general max-weight scheduler and then particularize it to a wireless network where the base stations have multiuser multiple-input multiple-output (MU-MIMO) beamforming capabilities. We exploit the channel hardening effect of large-dimensional MIMO channels (massive MIMO) and devise a low complexity user selection scheme to solve the underlying combinatorial problem of selecting user subsets for downlink beamforming, which can be easily implemented and run independently at each base station. Furthermore, through simulations, we show that deploying MU-MIMO significantly improves video streaming performance and also that the proposed cross-layer approach is able to serve users more fairly than a baseline scheme representative of current systems running independently designed protocol layers.

This paper considers a wireless link with randomly arriving data that is queued and served over a time-varying channel. It is known that any algorithm that comes within ε of the minimum average power required for queue stability must incur average queue size at least Ω(log(l/ε)). However, the optimal convergence time is unknown, and prior algorithms give convergence time bounds of O(l/ε2). This paper shows that it is possible to achieve the optimal O(log(l/ε)) average queue size tradeoff with an improved convergence time of O(log(l/ε)/ε). Further, this is shown to be within a logarithmic factor of the best possible convergence time. The method uses the simple drift-plus-penalty technique with an improved convergence time analysis.

One practical open problem is the development of a distributed algorithm that achieves near-optimal utility using only a finite (and small) buffer size for queues in a stochastic network. This paper studies utility maximization (or cost minimization) in a finite-buffer regime and considers the corresponding delay and reliability (or rate of packet drops) tradeoff. A floating-queue algorithm allows the stochastic network optimization framework to be implemented with finite buffers at the cost of packet drops. Further, the buffer size requirement is significantly smaller than previous works in this area. With a finite buffer size of B packets, the proposed algorithm achieves within O(e-B) of the optimal utility while maintaining average per-hop delay of O(B) and an average per-hop drop rate of O(e-B) in steady state. From an implementation perspective, the floating-queue algorithm requires little modification of the well-known Drift-Plus-Penalty policy (including MaxWeight and Backpressure policies). As a result, the floating-queue algorithm inherits the distributed and low complexity nature of these policies.

This paper considers time-average stochastic optimization, where a time average decision vector, an average of decision vectors chosen in every time step from a time-varying (possibly non-convex) set, minimizes a convex objective function and satisfies convex constraints. This formulation has applications in networking and operations research. In general, time-average stochastic optimization can be solved by a Lyapunov optimization technique. This paper shows that the technique exhibits a transient phase and a steady state phase. When the problem has a unique vector of Lagrange multipliers, the convergence time can be improved. By starting the time average in the steady state, the convergence times become O(1/ε) under a locally-polyhedral assumption and O(1/ε1.5) under a locally-non-polyhedral assumption, where e denotes the proximity to the optimal objective cost.

We consider the design of a scheduling policy for video streaming in a wireless network formed by several users and helpers (e.g., base stations). In such networks, any user is typically in the range of multiple helpers. Hence, an efficient policy should allow the users to dynamically select the helper nodes to download from and determine adaptively the quality level of the requested video segment. In order to obtain a tractable formulation, we follow a “divide and conquer” approach. First, we formulate a network utility maximization (NUM) problem where the network utility function is a concave and component-wise nondecreasing function of the time-averaged users' requested video quality index, and maximization is subject to the stability of all queues in the system. Second, we solve the NUM problem by using a Lyapunov drift plus penalty approach, obtaining a dynamic adaptive scheme that decomposes into two building blocks: 1) adaptive video quality and helper selection (run at the user nodes); and 2) dynamic allocation of the helper-to-user transmission rates (run at the help nodes). Our solution provably achieves NUM optimality in a strong per-sample path sense (i.e., without assumptions of stationarity and ergodicity). Third, we observe that, since all queues in the system are stable, all requested video chunks shall be eventually delivered. Fourth, in order to translate the requested video quality into the effective video quality at the user playback, it is necessary that the chunks are delivered within their playback deadline. This requires that the largest delay among all queues at the helpers serving any given user is less than the pre-buffering time of that user at its streaming session startup phase. In order to achieve this condition with high probability, we propose an effective and decentralized (albeit heuristic) scheme to adaptively calculate the pre-buffering and re-buffering time at each user. In this way, the system is forced to work in the “smooth streaming regime,” i.e., in the regime of very small playback buffer underrun rate. Through simulations, we evaluate the performance of the proposed algorithm under realistic assumptions of a network with densely deployed helper and user nodes, including user mobility, variable bit-rate video coding, and users joining or leaving the system at arbitrary times.

An information collection problem in a wireless network with random events is considered. Wireless devices report on each event using one of multiple reporting formats. Each format has a different quality and uses different data lengths. Delivering all data in the highest-quality format can overload system resources. The goal is to make intelligent format selection and routing decisions to maximize time-averaged information quality subject to network stability. Lyapunov optimization theory can be used to solve such a problem by repeatedly minimizing the linear terms of a quadratic drift-plus-penalty expression. To reduce delays, this paper proposes a novel extension of this technique that preserves the quadratic nature of the drift minimization while maintaining a fully separable structure. In addition, to avoid high queuing delay, paths are restricted to at most 2 hops. The resulting algorithm can push average information quality arbitrarily close to optimum, with a tradeoff in queue backlog. The algorithm compares favorably to the basic drift-plus-penalty scheme in terms of backlog and delay.

This comment points out several mathematical errors in the proof of Therorem 3, and gives the correct expression of B3.

This paper considers a problem where multiple users make repeated decisions based on their own observed events. The events and decisions at each time step determine the values of a utility function and a collection of penalty functions. The goal is to make distributed decisions over time to maximize time average utility subject to time average constraints on the penalties. An example is a collection of power constrained sensors that repeatedly report their own observations to a fusion center. Maximum time average utility is fundamentally reduced because users do not know the events observed by others. Optimality is characterized for this distributed context. It is shown that optimality is achieved by correlating user decisions through a commonly known pseudorandom sequence. An optimal algorithm is developed that chooses pure strategies at each time step based on a set of time-varying weights.

This paper treats power-aware throughput maximization in a multi-user file downloading system. Each user can receive a new file only after its previous file is finished. The file state processes for each user act as coupled Markov chains that form a generalized restless bandit system. First, an optimal algorithm is derived for the case of one user. The algorithm maximizes throughput subject to an average power constraint. Next, the one-user algorithm is extended to a low complexity heuristic for the multi-user problem. The heuristic uses a simple online index policy and its effectiveness is shown via simulation. For simple 3-user cases where the optimal solution can be computed offline, the heuristic is shown to be near-optimal for a wide range of parameters.

We investigate optimal resource allocation for delay-limited cooperative communication in time varying wireless networks. Motivated by real-time applications that have stringent delay constraints, we develop a dynamic cooperation strategy that makes optimal use of network resources to achieve a target outage probability (reliability) for each user subject to average power constraints. Using the technique of Lyapunov optimization, we first present a general framework to solve this problem and then derive quasi-closed form solutions for several cooperative protocols proposed in the literature. Unlike earlier works, our scheme does not require prior knowledge of the statistical description of the packet arrival, channel state, and node mobility processes and can be implemented in an online fashion.

This paper considers a base station that delivers packets to multiple receivers through a sequence of coded transmissions. All receivers overhear the same transmissions. Each receiver may already have some of the packets as side information, and requests another subset of the packets. This problem is known as the index coding problem and can be represented by a bipartite digraph. An integer linear program is developed that provides a lower bound on the minimum number of transmissions required for any coding algorithm. Conversely, its linear programming relaxation is shown to provide an upper bound that is achievable by a simple form of vector linear coding. Thus, the information theoretic optimum is bounded by the integrality gap between the integer program and its linear relaxation. In the special case, when the digraph has a planar structure, the integrality gap is shown to be zero, so that exact optimality is achieved. Finally, for nonplanar problems, an enhanced integer program is constructed that provides a smaller integrality gap. The dual of this problem corresponds to a more sophisticated partial clique coding strategy that time-shares between maximum distance separable codes. This paper illuminates the relationship between index coding, duality, and integrality gaps between integer programs and their linear relaxations.

This paper considers peer-to-peer scheduling for a network with multiple wireless devices. A subset of the devices are mobile users that desire specific files. Each user may already have certain popular files in its cache. The remaining devices are access points that typically have a larger set of files. Users can download packets of their requested file from an access point or from another user. A dynamic algorithm that opportunistically grabs packets from current neighbors is developed. Under a simple model where each user desires a single file with infinite length, the algorithm is shown to optimize utility while incentivizing participation. The algorithm extends as an efficient heuristic in more general cases with finite file sizes and random active and idle periods. Example simulations demonstrate the dramatic throughput gains enabled by wireless peering.

This paper considers a stochastic optimization approach for job scheduling and server management in large-scale, geographically distributed data centers. Randomly arriving jobs are routed to a choice of servers. The number of active servers depends on server activation decisions that are updated at a slow time scale, and the service rates of the servers are controlled by power scaling decisions that are made at a faster time scale. We develop a two-time-scale decision strategy that offers provable power cost and delay guarantees. The performance and robustness of the approach is illustrated through simulations.

We consider the jointly optimal design of a transmission scheduling and admission control policy for adaptive video streaming over small cell networks. We formulate the problem as a dynamic network utility maximization and observe that it naturally decomposes into two subproblems: admission control and transmission scheduling. The resulting algorithms are simple and suitable for distributed implementation. The admission control decisions involve each user choosing the quality of the video chunk asked for download, based on the network congestion in its neighborhood. This form of admission control is compatible with the current video streaming technology based on the DASH protocol over TCP connections. Through simulations, we evaluate the performance of the proposed algorithm under realistic assumptions for a small-cell network.

This demo abstract describes an initial design of a new adaptive video streaming protocol for device-to-device WiFi-based mobile platforms and its software implementation. For the demonstration, two mobile servers and two mobile users will be deployed verifying that our device-to-device adaptive video streaming implementation works with desirable user experience.

We consider a wireless broadcast station that transmits packets to multiple users. The packet requests for each user may overlap, and some users may already have certain packets. This presents a problem of broadcasting in the presence of side information, and is a generalization of the well-known (and unsolved) index coding problem of information theory. We represent the problem by a bipartite demand graph. Uncoded transmission is optimal if and only if this graph is acyclic. Next, we define a code-constrained capacity region that restricts attention to any prespecified set of coding actions. A dynamic max-weight algorithm that acts over variable length frames is developed. The algorithm allows for random packet arrivals and supports any traffic inside the code-constrained capacity region. A simple set of codes that exploit cycles in the demand graph are shown to be optimal for a class of broadcast relay problems.

There has been considerable work developing a stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay-efficient. In this paper, we show that the Backpressure algorithm, when combined with the last-in-first-out (LIFO) queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is withinO(1/V) of the optimal value, for any scalarV≥ 1, while maintaining an average delay ofO([log(V)]2) for all but a tiny fraction of the network traffic. This result holds for a general class of problems with Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show a good match between theory and practice. Because some packets may stay in the queues for a very long time under LIFO-Backpressure, we further develop the LIFOp-Backpressure algorithm, which generalizes LIFOp-Backpressure by allowing interleaving between first-in-first-out (FIFO) and LIFO. We show that LIFOpBackpressure also achieves the sameO(1/V) close-to-optimal utility performance and guarantees an average delay ofO([log(V)]2) for the packets that are served during the LIFO period.

In this paper, we show how to achieve close-to-optimal utility performance in energy-harvesting networks with only finite capacity energy storage devices. In these networks, nodes are capable of harvesting energy from the environment. The amount of energy that can be harvested is time-varying and evolves according to some probability law. We develop an online algorithm, called the Energy-limited Scheduling Algorithm (ESA), which jointly manages the energy and makes power allocation decisions for packet transmissions. ESA only has to keep track of the amount of energy left at the network nodes and does not require any knowledge of the harvestable energy process. We show that ESA achieves a utility that is within O(ε) of the optimal, for any ε > 0, while ensuring that the network congestion and the required capacity of the energy storage devices are deterministically upper-bounded by bounds of size O(1/ε). We then also develop the Modified-ESA (MESA) algorithm to achieve the same O(ε) close-to-utility performance, with the average network congestion and the required capacity of the energy storage devices being only O([log(1/ε)]2), which is close to the theoretical lower bound O(log(1/ε)).

It is well known that max-weight policies based on a queue backlog index can be used to stabilize stochastic networks, and that similar stability results hold if a delay index is used. Using Lyapunov optimization, we extend this analysis to design a utility maximizing algorithm that uses explicit delay information from the head-of-line packet at each user. The resulting policy is shown to ensure deterministic worst-case delay guarantees and to yield a throughput utility that differs from the optimally fair value by an amount that is inversely proportional to the delay guarantee. Our results hold for a general class of 1-hop networks, including packet switches and multiuser wireless systems with time-varying reliability .

An information collection problem in a wireless network with random events is considered. Wireless nodes report on each event using one of multiple reporting formats. Each format has a different quality and uses a different number of bits. Delivering all data in the highest quality format can overload system resources. The goal is to make intelligent format selection and routing decisions to maximize time-averaged information quality subject to network stability. Lyapunov optimization theory can be used to solve such a problem by repeatedly minimizing the linear terms of a quadratic drift-plus-penalty expression. To reduce delays, a novel extension of this technique that preserves the quadratic nature of the drift minimization while maintaining a separable decision structure is proposed. Also, paths are restricted to 1 or 2 hops to avoid high queuing delay. The resulting algorithm can push average information quality arbitrarily close to optimum, with a trade-off in average delay. The algorithm compares favorably to the basic drift-pluspenalty scheme in terms of backlog and delay.

Backpressure scheduling and routing, in which packets are preferentially transmitted over links with high queue differentials, offers the promise of throughput-optimal operation for a wide range of communication networks. However, when the traffic load is low, due to the corresponding low queue occupancy, backpressure scheduling/routing experiences long delays. This is particularly of concern in intermittent encounter-based mobile networks which are already delay-limited due to the sparse and highly dynamic network connectivity. While state of the art mechanisms for such networks have proposed the use of redundant transmissions to improve delay, they do not work well when the traffic load is high. We propose in this paper a novel hybrid approach that we refer to as backpressure with adaptive redundancy (BWAR), which provides the best of both worlds. This approach is highly robust and distributed and does not require any prior knowledge of network load conditions. We evaluate BWAR through both mathematical analysis and simulations based on a cell-partitioned model. We prove theoretically that BWAR does not perform worse than traditional backpressure in terms of the maximum throughput, while yielding a better delay bound. The simulations confirm that BWAR outperforms traditional backpressure at low load, while outperforming a state of the art encounter-routing scheme (Spray and Wait) at high load.

We study two convex optimization problems in a multi-class M/G/1 queue with adjustable service rates: minimizing convex functions of the average delay vector, and minimizing average service cost, both subject to per-class delay constraints. Using virtual queue techniques, we solve the two problems with variants of dynamic cμ rules. These algorithms adaptively choose a strict priority policy, in response to past observed delays in all job classes, in every busy period. Our policies require limited or no statistics of the queue. Their optimal performance is proved by Lyapunov drift analysis and validated through simulations.

We consider a wireless broadcast station that transmits packets to multiple users. The packet requests for each user may overlap, and some users may already have certain packets. This presents a problem of broadcasting in the presence of side information, and is a generalization of the well known (and unsolved) index coding problem of information theory. Rather than achieving the full capacity region, we develop a code-constrained capacity region, which restricts attention to a pre-specified set of coding actions. We develop a dynamic max-weight algorithm that allows for random packet arrivals and supports any traffic inside the code-constrained capacity region. Further, we provide a simple set of codes based on cycles in the underlying demand graph. We show these codes are optimal for a class of broadcast relay problems.

In this work we focus on a stochastic optimization based approach to make distributed routing and server management decisions in the context of large-scale, geographically distributed data centers, which offers significant potential for exploring power cost reductions. Our approach considers such decisions at different time scales and offers provable power cost and delay characteristics. The utility of our approach and its robustness are also illustrated through simulation-based experiments under delay tolerant workloads.

We analyze a generalized index coding problem that allows multiple users to request the same packet. For this problem we introduce a novel coding scheme called partition multicast. Our scheme can be seen as a natural generalization of clique cover for directed index coding problems. Further, partition multicast corresponds to an achievable scheme for the generalized bipartite index coding problem that we introduce in this paper. Our scheme partitions the nodes into groups and solves a multicasting problem within each group. We show that Partition Multicast is optimal for a few families of graphs and generalizes previous achievable schemes, namely directed cycle covers. We also show that finding the best partition is computationally intractable to compute in general.

This paper considers optimal control for a collection of separate Markov decision systems that operate asynchronously over their own state spaces. Decisions at each system affect: (i) the time spent in the current state, (ii) a vector of penalties incurred, and (iii) the next-state transition probabilities. An example is a network of smart devices that perform separate tasks but share a common wireless channel. The model can also be applied to data center scheduling and to various types of cyber-physical networks. The combined state space grows exponentially with the number of systems. However, a simple strategy is developed where each system makes separate decisions. Total complexity grows only linearly in the number of systems, and the resulting performance can be pushed arbitrarily close to optimal.

We investigate opportunistic cooperation between secondary (femtocell) users and primary (macrocell) users in cognitive femtocell networks. We consider two models for such cooperation. In the first model, called the Cooperative Relay Model, a secondary user cannot transmit its own data concurrently with a primary user. However, it can employ cooperative relaying of primary user data in order to improve the latter's effective transmission rate. In the second model, called the Interference Model, a secondary user is allowed to transmit its data concurrently with a primary user. However, the secondary user can "cooperate" by deferring its transmissions when the primary user is busy. In both models, the secondary users must make intelligent cooperation decisions as they seek to maximize their own throughput subject to average power constraints. The decision options are different during idle and busy periods of the primary user, and the decisions in turn influence the durations of these periods according to a controllable infinite state Markov chain. Such problems can be formulated as constrained Markov decision problems, and conventional solution techniques require either extensive knowledge of the system dynamics or learning based approaches that suffer from large convergence times. However, using a generalized Lyapunov optimization technique, we design a novel greedy and online control algorithm that overcomes these challenges. Remarkably, this algorithm does not require any knowledge of the network arrival rates and is provably optimal.

With the advent of smartphone technology, it has become possible to conceive of entirely new classes of applications. Social swarming, in which users armed with smartphones are directed by a central director to report on events in the physical world, has several real-world applications: search and rescue, coordinated fire-fighting, and the DARPA balloon hunt challenge. In this paper, we focus on the following problem: how does the director optimize the selection of reporters to deliver credible corroborating information about an event. We first propose a model, based on common notions of believability, about the credibility of information. We then cast the problem posed above as a discrete optimization problem, prove hardness results, introduce optimal centralized solutions, and design an approximate solution amenable to decentralized implementation whose performance is about 20 percent off, on average, from the optimal (on real-world data sets derived from Google News) while being three orders of magnitude more computationally efficient. More interesting, a time-averaged version of the problem is amenable to a novel stochastic utility optimization formulation, and can be solved optimally, while in some cases yielding decentralized solutions. To our knowledge, we are the first to propose and explore the problem of extracting credible information from a network of smartphones.

With the advent of smartphone technology, it has become possible to conceive of entirely new classes of applications. Social swarming, in which users armed with smartphones are directed by a central director to report on events in the physical world, has several real-world applications. In this paper, we focus on the following problem: how does the director optimize the selection of reporters to deliver credible corroborating information about an event? We first propose a model, based on common intuitions of believability, about the credibility of information. We then cast the problem as a discrete optimization problem, and introduce optimal centralized solutions and an approximate solution amenable to decentralized implementation whose performance is about 20% off on average from the optimal while being 3 orders of magnitude more computationally efficient. More interesting, a time-averaged version of the problem is amenable to a novel stochastic utility optimization formulation, and can be solved optimally, while in some cases yielding decentralized solutions.

We first consider a multi-user, single-hop wireless network with arbitrarily varying (and possibly non-ergodic) arrivals and channels. We design an opportunistic scheduling algorithm that guarantees all sessions have a bounded worst case delay. The algorithm has no knowledge of the future, but yields throughput-utility that is close to (or better than) that of a T-slot lookahead policy that makes “ideal” decisions based on perfect knowledge up to T slots into the future. We then extend the algorithm to treat worst case delay guarantees in multi-hop networks. Our analysis uses a sample-path version of Lyapunov optimization together with a novel virtual queue structure.

We consider a peer-to-peer network where nodes can send and receive files amongst their peers. File requests are generated randomly, and each new file can correspond to a different subset of peers that already have the file and hence can assist in the download. Nodes that help others are rewarded by being able to download more. The goal is to design a control algorithm that allocates requests and schedules transmissions to maximize overall throughput-utility, subject to meeting “tit-for-tat” constraints that incentivize participation. Our algorithm is shown to operate efficiently on networks with arbitrary traffic and channel sample paths, including wireless networks whose capacity can be significantly extended by the peer-to-peer functionality.

The multiple-access framework of ZigZag decoding [1] is a useful technique for combating interference via multiple repeated transmissions, and is known to be compatible with distributed random access protocols. However, in the presence of noise this type of decoding can magnify errors, particularly when packet sizes are large. We present a simple soft-decoding version, called SigSag, that improves performance. We show that for two users, collisions result in a cycle-free factor graph that can be optimally decoded via belief propagation. For collisions between more than two users, we show that if a simple bit-permutation is used then the graph is locally tree-like with high probability, and hence belief propagation is near optimal. Through simulations we show that our scheme performs better than coordinated collision-free time division multiple access (TDMA) and the ZigZag decoder.

In this paper, we show how to achieve close-to-optimal utility performance in energy harvesting networks with only finite capacity energy storage devices. In these networks, nodes are capable of harvesting energy from the environment. The amount of energy that can be harvested is time varying and evolves according to some probability law. We develop an online algorithm, called the Energy-limited Scheduling Algorithm (ESA), which jointly manages the energy and makes power allocation decisions for packet transmissions. ESA only has to keep track of the amount of energy left at the network nodes and does not require any knowledge of the harvestable energy process. We show that ESA achieves a utility that is within O(ε) of the optimal, for any ε > 0, while ensuring that the network congestion and the required capacity of the energy storage devices are deterministically upper bounded by bounds of size O(1/ε). We then also develop the Modified-ESA algorithm (MESA) to achieve the same O(ε) close-to-utility performance, with the average network congestion and the required capacity of the energy storage devices being only O([log(1/ε)]2).

Since the electricity bill of a data center constitutes a significant portion of its overall operational costs, reducing this has become important. We investigate cost reduction opportunities that arise by the use of uninterrupted power supply (UPS) units as energy storage devices. This represents a deviation from the usual use of these devices as mere transitional fail-over mechanisms between utility and captive sources such as diesel generators. We consider the problem of opportunistically using these devices to reduce the time average electric utility bill in a data center. Using the technique of Lyapunov optimization, we develop an online control algorithm that can optimally exploit these devices to minimize the time average cost. This algorithm operates without any knowledge of the statistics of the workload or electricity cost processes, making it attractive in the presence of workload and pricing uncertainties. An interesting feature of our algorithm is that its deviation from optimality reduces as the storage capacity is increased. Our work opens up a new area in data center power management.

There has been considerable recent work developing a new stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay efficient. In this paper, we show that the Backpressure algorithm, when combined with the LIFO queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is within O(1/V) of the optimal value for any scalar V ≥ 1, while maintaining an average delay of O([log(V)]2) for all but a tiny fraction of the network traffic. This result holds for general stochastic network optimization problems and general Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show good match between theory and practice.

This paper considers maximizing throughput utility in a multi-user network with partially observable Markov ON/OFF channels. Instantaneous channel states are never known, and all control decisions are based on information provided by ACK/NACK feedback from past transmissions. This system can be viewed as a restless multi-armed bandit problem with a concave objective function of the time average reward vector. Such problems are generally intractable. However, we provide an approximate solution by optimizing the concave objective over a non-trivial inner bound on the network performance region, where the inner bound is constructed by randomizing well-designed stationary policies. Using a new frame-based Lyapunov drift argument, we design a policy of admission control and channel selection that stabilizes the network with throughput utility that can be made arbitrarily close to the optimal in the inner performance region. Our problem has applications in limited channel probing in wireless networks, dynamic spectrum access in cognitive radio networks, and target tracking of unmanned aerial vehicles. Our analysis generalizes the MaxWeight-type scheduling policies in stochastic network optimization theory from time-slotted systems to frame-based systems that have policy-dependent frame sizes.

We investigate Quality of Information (QoI) aware scheduling in task processing networks. Specifically, we consider the scenario where a network sequentially receives tasks from an end user, utilizes its resources to process them, and sends back its response. The utility derived by the end user from this response depends on both the accuracy and the freshness of the information. There is often a trade-off between these two attributes and we present a model that quantifies this dependence. Using dynamic programming and optimal stopping theory, we characterize the optimal scheduling policy that maximizes the time average utility delivered by the network. We show that for many scenarios of practical interest, the optimal policy has a simple threshold structure. We also propose a method to approximately compute the threshold in closed-form. This work takes a step towards incorporating application aware objectives in making optimal scheduling decisions.

We investigate two quantities of interest in a delay-tolerant mobile ad hoc network: the network capacity region and the minimum energy function. The network capacity region is defined as the set of all input rates that the network can stably support considering all possible scheduling and routing algorithms. Given any input rate vector in this region, the minimum energy function establishes the minimum time-average power required to support it. In this paper, we consider a cell-partitioned model of a delay-tolerant mobile ad hoc network with general Markovian mobility. This simple model incorporates the essential features of locality of wireless transmissions as well as node mobility and enables us to exactly compute the corresponding network capacity and minimum energy function. Furthermore, we propose simple schemes that offer performance guarantees that are arbitrarily close to these bounds at the cost of an increased delay.

It is well known that max-weight policies based on a queue backlog index can be used to stabilize stochastic networks, and that similar stability results hold if a delay index is used. Using Lyapunov Optimization, we extend this analysis to design a utility maximizing algorithm that uses explicit delay information from the head-of-line packet at each user. The resulting policy is shown to ensure deterministic worst-case delay guarantees, and to yield a throughput-utility that differs from the optimally fair value by an amount that is inversely proportional to the delay guarantee. Our results hold for a general class of 1-hop networks, including packet switches and multi-user wireless systems with time varying reliability.

Many applications are enabled by the ability to capture videos on a smartphone and to have these videos uploaded to an Internet-connected server. This capability requires the transfer of large volumes of data from the phone to the infrastructure. Smartphones have multiple wireless interfaces -- 3G/EDGE and WiFi -- for data transfer, but there is considerable variability in the availability and achievable data transfer rate for these networks. Moreover, the energy costs for transmitting a given amount of data on these wireless interfaces can differ by an order of magnitude. On the other hand, many of these applications are often naturally delay-tolerant, so that it is possible to delay data transfers until a lower-energy WiFi connection becomes available. In this paper, we present a principled approach for designing an optimal online algorithm for this energy-delay tradeoff using the Lyapunov optimization framework. Our algorithm, called SALSA, can automatically adapt to channel conditions and requires only local information to decide whether and when to defer a transmission. We evaluate SALSA using real-world traces as well as experiments using a prototype implementation on a modern smartphone. Our results show that SALSA can be tuned to achieve a broad spectrum of energy-delay tradeoffs, is closer to an empirically-determined optimal than any of the alternatives we compare it to, and, can save 10-40% of battery capacity for some workloads.

We investigate optimal resource allocation and power management in virtualized data centers with time-varying workloads and heterogeneous applications. Prior work in this area uses prediction based approaches for resource provisioning. In this work, we take an alternate approach that makes use of the queueing information available in the system to make online control decisions. Specifically, we use the recently developed technique of Lyapunov Optimization to design an online admission control, routing, and resource allocation algorithm for a virtualized data center. This algorithm maximizes a joint utility of the average application throughput and energy costs of the data center. Our approach is adaptive to unpredictable changes in the workload and does not require estimation and prediction of its statistics.

Downlink scheduling schemes are well-known and widely investigated under the assumption that the channel state is perfectly known to the scheduler. In the multiuser MIMO (broadcast) case, downlink scheduling in the presence of non-perfect channel state information (CSI) is only scantly treated. In this paper we provide a general framework that addresses the problem systematically. Also, we illuminate the key role played by the channel state prediction error: our scheme treats in a fundamentally different way users with small channel prediction error ("predictable" users) and users with large channel prediction error ("non-predictable" users), and can be interpreted as a near-optimal opportunistic time-sharing strategy between MIMO downlink beamforming to predictable users and space-time coding to non-predictable users. Our results, based on a realistic MIMO channel model used in 3GPP standardization, show that the proposed algorithms can significantly outperform a conventional "mismatched" scheduling scheme that treats the available CSI as if it was perfect.

We consider a wireless base station serving L users through L time-varying channels. It is well known that opportunistic scheduling algorithms with full channel state information (CSI) can stabilize the system with any data rates within the capacity region. However, such opportunistic scheduling algorithms may not be energy efficient when the cost of channel acquisition is high and traffic rates are low. In particular, under the low traffic rate regime, it may be sufficient and more energy efficient to transmit data with no CSI, i.e., to transmit data blindly, since no power for channel acquisition is consumed. In general, we show strategies that probe channels in every slot or never probe channels in any slot are not necessarily optimal, and we must consider mixed strategies. We derive a unified scheduling algorithm that dynamically chooses to transmit data with full or no CSI based on queue backlog and channel statistics. Our methodology is general and can be naturally extended to include timing overhead due to channel acquisition, and to treat systems that allow any subset of channels to be measured. Through Lyapunov analysis, we show that the unified algorithm is throughput-optimal and stabilizes the downlink with optimal power consumption, balancing well between channel-aware and channel-blind transmission modes.

We investigate optimal resource allocation for delay-limited cooperative communication in time varying wireless networks. Motivated by real-time applications that have stringent delay constraints, we develop dynamic cooperation strategies that make optimal use of network resources to achieve a target outage probability (reliability) for each user subject to average power constraints. Using the technique of Lyapunov optimization, we first present a general framework to solve this problem and then derive quasi-closed form solutions for several cooperative protocols proposed in the literature.

In this paper, we consider the problem of reducing network delay in stochastic network utility optimization problems. We start by studying the recently proposed quadratic Lyapunov function based algorithms (QLA). We show that for every stochastic problem, there is a corresponding deterministic problem, whose dual optimal solution ldquoexponentially attractsrdquo the network backlog process under QLA. In particular, the probability that the backlog vector under QLA deviates from the attractor is exponentially decreasing in their Euclidean distance. This suggests that one can roughly ldquosubtract outrdquo a Lagrange multiplier from the system induced by QLA. We thus develop a family of Fast Quadratic Lyapunov based Algorithms (FQLA) that achieve an [O(1/V ),O(log2(V ))] performance-delay tradeoff. These results highlight the ldquonetwork gravityrdquo role of Lagrange Multipliers in network scheduling. This role can be viewed as the counterpart of the ldquoshadow pricerdquo role of Lagrange Multipliers in flow regulation for classic flow-based network problems.

We investigate the throughput improvement that ZIGZAG decoding (Gollakota and Katabi (2008)) can achieve in multi-user random access systems. ZIGZAG is a recently proposed 802.11 receiver design that allows successful reception of packets despite collision. Thus, the maximum achievable throughput of a wireless LAN can be significantly improved by using ZIGZAG decoding. We analyze the throughput bounds in three different idealized slotted multi-access system models for the case when ZIGZAG decoding is used. We also provide results for the Aloha and CSMA models where exact closed form solutions are infeasible to calculate. Our analysis and simulation results show that ZIGZAG decoding can significantly improve the maximum throughput of the random access system.

We develop opportunistic scheduling policies for cognitive radio networks that maximize the throughput utility of the secondary (unlicensed) users subject to maximum collision constraints with the primary (licensed) users. We consider a cognitive network with static primary users and potentially mobile secondary users. We use the technique of Lyapunov Optimization to design an online flow control, scheduling, and resource allocation algorithm that meets the desired objectives and provides explicit performance guarantees.

We consider the delay properties of one-hop networks with general interference constraints and multiple traffic streams with time-correlated arrivals. We first treat the case when arrivals are modulated by independent finite state Markov chains. We show that the well known maximal scheduling algorithm achieves average delay that grows at most logarithmically in the largest number of interferers at any link. Further, in the important special case when each Markov process has at most two states (such as bursty ON/OFF sources), we prove that average delay is independent of the number of nodes and links in the network, and hence is order-optimal. We provide tight delay bounds in terms of the individual auto-correlation parameters of the traffic sources. These are perhaps the first order-optimal delay results for controlled queueing networks that explicitly account for such statistical information.

We develop opportunistic scheduling policies for cognitive radio networks that maximize the throughput utility of the secondary (unlicensed) users subject to maximum collision constraints with the primary (licensed) users. We consider a cognitive network with static primary users and potentially mobile secondary users. We use the technique of Lyapunov Optimization to design an online flow control, scheduling and resource allocation algorithm that meets the desired objectives and provides explicit performance guarantees.

This paper focuses on energy-efficient packet transmission with individual packet delay constraints. The solution presented herein is a generalization of Uysal-Biyikoglu (2002), which considered energy-efficient transmissions for a group of M packets subject to a single transmission deadline. First, the optimal offline scheduler (vis-À-vis total transmission energy) for packet transmissions with individual packet delay constraints is developed. It is shown that when packet inter-arrival times are independent and identically distributed (i.i.d.), the optimal transmission durations of packet $m$ and packet M-m+1, m ∈ [1,...,M, M ≥ 1, are identically distributed. This symmetry property leads to a simple and exact solution of the average packet delay for any i.i.d. inter-arrival times under the optimal offline scheduling. In addition, the packet delay performance for the single transmission deadline model is analyzed and shown to grow monotonically with $M$ and at a rate proportional to √M. A heuristic online scheduler, which assumes no future arrival information, is also studied and shown to achieve a comparable energy performance to the optimal offline scheduler in a wide range of scenarios. The flexible energy and delay tradeoff provided by the individual delay constraint model is further illustrated via simulations.

This paper focuses on energy-efficient packet transmission with individual packet delay constraints. The optimal offline scheduler (vis-a-vis total transmission energy), assuming information of all packet arrivals before scheduling, was developed by Zafer, et al. (2005) and Chen et al. (2006). This paper shows that when packet inter-arrival times are identically and independently distributed (Ltd.), the resulting optimal transmission durations of packets m and M - m +1, m epsiv [1, .. ., M], M ges 1, are identically distributed. This symmetry property leads to a simple and exact solution of the average packet delay under the optimal offline schedule. Two heuristic online scheduling algorithms, which assume no future arrival information, are then studied. These online schedulers are compared with the optimal offline scheduler in terms of delay and energy performance via analysis and simulations. While both online schedulers are inherently inferior, one online scheduler is shown to achieve a comparable energy performance to the optimal offline scheduler in a wide range of scenarios.

We consider an ad-hoc wireless network operating within a free market economic model. Users send data over a choice of paths, and scheduling and routing decisions are updated dynamically based on time varying channel conditions, user mobility, and current network prices charged by intermediate nodes. Each node sets its own price for relaying services, with the goal of earning revenue that exceeds its time average reception and transmission expenses. We first develop a greedy pricing strategy that maximizes social welfare while ensuring all participants make non-negative profit. We then construct a (non-greedy) policy that balances profits more evenly by optimizing a profit fairness metric. Both algorithms operate in a distributed manner and do not require knowledge of traffic rates or channel statistics. This work demonstrates that individuals can benefit from carrying wireless devices even if they are not interested in their own personal communication.

This paper focuses on delay-constrained energy-efficient packet transmission over a static multihop link. Optimal offline scheduling (vis-à-vis total transmission energy), assuming information of all packet arrivals before scheduling, is derived. The optimal offline schedule relies on a simple delay budget allocation scheme, which allocates the delay budget to the first hop (from source to the first relaying node) as much as possible. All the relaying nodes simply perform buffer-clearing during any transmission opportunities. The total transmission energy and average packet delay are analyzed and characterized. It is demonstrated that energy savings via multihopping are possible, but depend heavily on factors such as multihop resource orthogonalization mode, delay constraints, and SNR operating regimes.

In this paper, we study the dynamic resource allocation problem for a class of time-varying wireless multicast networks with intra-multicast network coding. We provide distributed and dynamic cross-layer strategy to simultaneously achieve utility optimization and network stability under given power constraints. Our result shows when combined with Lyapunov drift technique for optimal flow control, "one shot" type of network codes, i.e., codes that restrict network coding within packets in a multicast that enter the network in the same timeslot, are sufficient to achieve performance optimality in this class of networks.

We consider the fundamental delay tradeoffs for minimizing energy expenditure in a multiuser wireless downlink with randomly varying channels. First, we extend the Berry-Gallager bound to a multiuser context, demonstrating that any algorithm that yields average power withinO(1/V) of the minimum power required for network stability must also have an average queueing delay greater than or equal to Omega(radicV). We then develop a class of algorithms, parameterized byV, that come within a logarithmic factor of achieving this fundamental tradeoff. The algorithms overcome an exponential state-space explosion, and can be implemented in real time withoutaprioriknowledge of traffic rates or channel statistics. Further, we discover a ldquosuperfastrdquo scheduling mode that beats the Berry-Gallager bound in the exceptional case when power functions are piecewise linear.

We consider the fundamental delay tradeoffs for utility optimal scheduling in a general network with time-varying channels. A network controller acts on randomly arriving data and makes flow control, routing, and resource allocation decisions to maximize a fairness metric based on a concave utility function of network throughput. A simple set of algorithms are constructed that yield total utility within O(1/V) of the utility-optimal operating point, for any control parameter V>0, with a corresponding end-to-end network delay that grows only logarithmically in V. This is the first algorithm to achieve such super-fast performance. Furthermore, we show that this is the best utility-delay tradeoff possible. This work demonstrates that the problem of maximizing throughput utility in a data network is fundamentally different than related problems of minimizing average power expenditure, as these latter problems cannot achieve such performance tradeoffs

We consider the fundamental delay tradeoffs for minimizing energy expenditure in a multi-user wireless downlink with randomly varying channels. First, we extend the Berry- Gallager bound to a multi-user context, demonstrating that any algorithm that yields average power within O(1/V ) of the minimum power required for network stability must also have an average queueing delay greater than or equal to ( p V ). We then develop a class of algorithms, parameterized by V , that come within a logarithmic factor of achieving this fundamental tradeoff. The algorithms overcome an exponential state space explosion, and can be implemented in real time without a- priori knowledge of traffic rates or channel statistics. Further, we discover a super-fast scheduling mode that beats the Berry- Gallager bound in the exceptional case when power functions are piecewise linear.

This paper investigates proactive packet dropping to achieve transmission energy savings. Such a scheme can be employed for applications which can tolerate a small fraction of packet losses. For a group of packets subject to a single transmission deadline, the optimal dropping scheme (vis-` a-vis total transmission energy) is derived. For packets subject to individual delay constraints, the optimal scheme depends on the energy function and packet sizes. Thus, asymptotically optimal dropping schemes, i. e., when packet size grows large, are pursued. The asymptotically optimal dropping scheme for a single dropped packet is obtained. For dropping more than one packet, two suboptimal, recursive schemes are proposed. These schemes achieve performance very close to the asymptotically optimal schemes as determined by an exhaustive search. Additionally, two performance bounds are derived. It is observed via simulations that significant energy savings are possible via intelligent packet dropping schemes.

We derive iterative message passing update rules for solving the bipartite maximum weighted matching problem. It is shown that if the optimal matching solution is unique, the algorithm converges to this optimal solution at a rate comparable to the algorithm of Bayati et. al. It is shown that the two algorithms are both standard messages passing, but on dual graphs of each other. Also, the algorithm presented here requires less storage. We also provide a method to use the proposed algorithm to solve the integer maximal weighted matching problem - i.e., where the optimal solution is generally not unique

We investigate two quantities of fundamental interest in a mobile ad-hoc network: the capacity region and the minimum energy function of the network. The capacity region is defined as the closure of the set of all input rates that the network can stably support. The minimum energy function establishes a lower bound on the amount of energy required to support a given set of input rates. We consider a specific model of the mobile ad-hoc network that enables us to exactly compute these quantities. Further, we propose schemes that offer performance guarantees that are arbitrarily close to these bounds at the cost of an increased delay. The exact nature of the associated delay tradeoff when performance is pushed towards the minimum energy bound is another fundamental characteristic of the network that is discussed in this work.

We consider the fundamental delay tradeoffs for utility optimal scheduling in a general network with time-varying channels. A network controller acts on randomly arriving data and makes flow control, routing, and resource allocation decisions to maximize a fairness metric based on a concave utility function of network throughput. A simple set of algorithms are constructed that yield total utility within O(1/V) of the utility-optimal operating point, for any control parameter V>0, with a corresponding end-to-end network delay that grows only logarithmically in V. This is the first algorithm to achieve such "super-fast" performance. Furthermore, we show that this is the best utility-delay tradeoff possible. This work demonstrates that the problem of maximizing throughput utility in a data network is fundamentally different than related problems of minimizing average power expenditure, as these latter problems cannot achieve such performance tradeoffs

We develop a dynamic control strategy for minimizing energy expenditure in a time-varying wireless network with adaptive transmission rates. The algorithm operates without knowledge of traffic rates or channel statistics, and yields average power that is arbitrarily close to the minimum possible value achieved by an algorithm optimized with complete knowledge of future events. Proximity to this optimal solution is shown to be inversely proportional to network delay. We then present a similar algorithm that solves the related problem of maximizing network throughput subject to peak and average power constraints. The techniques used in this paper are novel and establish a foundation for stochastic network optimization

We develop a dynamic control strategy for minimizing energy expenditure in a time varying wireless network with adaptive transmission rates. The algorithm operates without knowledge of traffic rates or channel statistics, and yields average power that is arbitrarily close to the minimum possible value achieved by an algorithm optimized with complete knowledge of future events. Proximity to this optimal solution is shown to be inversely proportional to network delay. We then present a similar algorithm that solves the related problem of maximizing network throughput subject to peak and average power constraints. The techniques used in this paper are novel and establish a foundation for stochastic network optimization.

We consider optimal control for general networks with both wireless and wireline components and time varying channels. A dynamic strategy is developed to support all traffic whenever possible, and to make optimally fair decisions about which data to serve when inputs exceed network capacity. The strategy is decoupled into separate algorithms for flow control, routing, and resource allocation, and allows each user to make decisions independent of the actions of others. The combined strategy is shown to yield data rates that are arbitrarily close to the optimal operating point achieved when all network controllers are coordinated and have perfect knowledge of future events. The cost of approaching this fair operating point is an end-to-end delay increase for data that is served by the network. Analysis is performed at the packet level and considers the full effects of queueing.

We consider dynamic routing and power allocation for a wireless network with time-varying channels. The network consists of power constrained nodes that transmit over wireless links with adaptive transmission rates. Packets randomly enter the system at each node and wait in output queues to be transmitted through the network to their destinations. We establish the capacity region of all rate matrices (/spl lambda//sub ij/) that the system can stably support-where /spl lambda//sub ij/ represents the rate of traffic originating at node i and destined for node j. A joint routing and power allocation policy is developed that stabilizes the system and provides bounded average delay guarantees whenever the input rates are within this capacity region. Such performance holds for general arrival and channel state processes, even if these processes are unknown to the network controller. We then apply this control algorithm to an ad hoc wireless network, where channel variations are due to user mobility. Centralized and decentralized implementations are compared, and the stability region of the decentralized algorithm is shown to contain that of the mobile relay strategy developed by Grossglauser and Tse (2002).

In this correspondence, we develop fundamental convexity properties of unfinished work and packet waiting time in a queue serving general stochastic traffic. The queue input consists of an uncontrollable background process and a rate-controllable input stream. We show that any moment of unfinished work is a convex function of the controllable input rate. The convexity properties are then extended to address the problem of optimally routing arbitrary input streams over a collection of K queues in parallel with different (possibly time-varying) server rates (/spl mu//sub 1/(t),...,/spl mu//sub K/(t)). Our convexity results hold for stream-based routing (where individual packet streams must be routed to the same queue) as well as for packet-based routing where each packet is routed to a queue by probabilistic splitting. Our analysis uses a novel technique that combines sample path observations with stochastic equivalence relationships.

We consider the throughput/delay tradeoffs for scheduling data transmissions in a mobile ad hoc network. To reduce delays in the network, each user sends redundant packets along multiple paths to the destination. Assuming the network has a cell partitioned structure and users move according to a simplified independent and identically distributed (i.i.d.) mobility model, we compute the exact network capacity and the exact end-to-end queueing delay when no redundancy is used. The capacity-achieving algorithm is a modified version of the Grossglauser-Tse two-hop relay algorithm and provides O(N) delay (where N is the number of users). We then show that redundancy cannot increase capacity, but can significantly improve delay. The following necessary tradeoff is established: delay/rate/spl ges/O(N). Two protocols that use redundancy and operate near the boundary of this curve are developed, with delays of O(/spl radic/N) and O(log(N)), respectively. Networks with non-i.i.d. mobility are also considered and shown through simulation to closely match the performance of i.i.d. systems in the O(/spl radic/N) delay regime.

In this correspondence, we analyze feedforward tree networks of queues serving fixed-length packets. Using sample path conservation properties and stochastic coupling techniques, we analyze these systems without making any assumptions about the nature of the underlying input processes. In the case when the server rate is the same for all queues, the exact packet occupancy distribution in any queue of a multistage network is obtained in terms of a reduced two-stage equivalent model. Simple and exact expressions for occupancy mean and variance are derived from this result, and the network is shown to exhibit a natural traffic smoothing property, where preliminary stages act to smooth or improve traffic for downstream nodes. In the case of heterogeneous server rates, a similar type of smoothing is demonstrated, and upper bounds on the backlog distribution are derived. These bounds hold for general input streams and are tighter than currently known bounds for leaky bucket and stochastically bounded bursty traffic.

We consider the throughput/delay tradeoffs for scheduling data transmissions in a mobile ad-hoc network. To reduce delays in the network, each user sends the redundant packets along multiple paths to the destination. Assuming the network has a cell partitioned structure and users move according to a simplified iid mobility model, we compute the exact network capacity and the exact end-to-end queueing delay when no redundancy is used. The capacity achieving algorithm is a modified version of the Grossglauser-Tse 2-hop relay algorithm and provides O(N) delay (where N is the number of users). We then show that redundancy cannot increase capacity, but can significantly improve delay. The following necessary tradeoff is established: delay/rate /spl ges/ O(N). Two protocols which use redundancy and operate near the boundary of this curve are developed, with delays of O(/spl radic/N) and O(log(N)), respectively. Networks with non-iid mobility are also considered and shown through simulation to closely match the performance of iid systems in the O(/spl radic/N) delay regime.

We consider a discrete time tandem of queues serving fixed length packets, where each queue can serve a single packet during a timeslot. Arrivals and departures take place at each stage according to arbitrary stochastic processes. Using the sample path techniques and stochastic coupling methods, we present an exact analysis of the queue occupancy distribution at each stage when all queues operate according to the furthest-to-go service discipline. Explicit expressions for average queue occupancies are provided in terms of the average occupancy in a single queue with a superposition of the original inputs. To our knowledge, this is the first analysis of a multi-input multi-output queueing network yielding exact solutions for general arrival processes.

We consider dynamic routing and power allocation for a wireless network with time varying channels. The network consists of power constrained nodes which transmit over wireless links with adaptive transmission rates. Packets randomly enter the system at each node and wait in output queues to be transmitted through the network to their destinations. We establish the capacity region of all rate matrices (/spl lambda//sub ij/) that the system can stably support - where (/spl lambda//sub ij/) represents the rate of traffic originating at node i and destined for node j. A joint routing and power allocation policy is developed which stabilizes the system and provides bounded average delay guarantees whenever the input rates are within this capacity region. Such performance holds for general arrival and channel state processes, even if these processes are unknown to the network controller. We then apply this control algorithm to an ad-hoc wireless network where channel variations are due to user mobility, and compare its performance with the Grossglauser-Tse (2001) relay model.

We consider power and server allocation in a multibeam satellite downlink which transmits data to N different ground locations over N time-varying channels. Packets destined for each ground location are stored in separate queues and the server rate for each queue, i, depends on the power, p/sub i/(t), allocated to that server and the channel state, c/sub i/(t), according to a concave rate-power curve /spl mu//sub i/(p/sub i/,c/sub i/). We establish the capacity region of all arrival rate vectors (/spl lambda//sub 1/,...,/spl lambda//sub N/) which admit a stabilizable system. We then develop a power-allocation policy which stabilizes the system whenever the rate vector lies within the capacity region. Such stability is guaranteed even if the channel model and the specific arrival rates are unknown. Furthermore, the algorithm is shown to be robust to arbitrary variations in the input rates and a bound on average delay is established. As a special case, this analysis verifies stability and provides a performance bound for the choose-the-K-largest-connected-queues policy when channels can be in one of two states (ON or OFF ) and K servers are allocated at every timestep (K

We consider power and server allocation in a multi-beam satellite downlink which transmits data to N different ground locations over N time-varying channels. Packets destined for each ground location are stored in separate queues, and the server rate for each queue i depends on the power p/sub i/(t) allocated to that server and the channel state c/sub i/(t) according to a concave rate-power curve /spl mu//sub i/(p/sub i/, c/sub i/). We establish the capacity region of all arrival rate vectors which admit a stabilizable system. For the case when channel states and arrivals are iid from timeslot to timeslot, we develop a particular power allocation policy which stabilizes the system whenever the rate vector lies within the capacity region. Such stability is guaranteed even if the channel model and the specific arrival rates are unknown. As a special case, this analysis verifies the stability of the "choose-the-K-largest-connected-queues" policy when channels can be in one of two states (ON or OFF) and K servers are allocated at every timestep (K

In this paper we develop fundamental convexity properties of unfinished work and packet waiting time in a work conserving */*/1 queue. The queue input consists of an uncontrollable background process and a rate-controllable input stream. We show that any moment of unfinished work is a convex function of the controllable input rate. The convexity properties are then extended to address the problem of optimal routing of arbitrary input streams over a collection of N queues in parallel with different (possibly time-varying) linespeeds (/spl mu//sub 1/(t),..., /spl mu//sub N/(t)). Our convexity results hold for stream-based routing (where individual packet streams must be routed to the same queue) as well as for packet-based routing where each packet is routed to a queue using some pre-determined splitting method, such as probabilistic splitting. Our analysis of these general systems is carried out by introducing a new function of the superposition of two input streams that we call the blocking function. Using this function facilitates analysis and provides much insight into the sample path dynamics of */*/1 queues.

In this paper we examine the queuing behavior of a multi-stage multiplexer with fixed length packets flowing through the stages. The system consists of two components: a front end multi-input, multi-output device as a preliminary stage, and a single-server, deterministic service time queue system (multiplexer) as a final stage. We treat arbitrary exogenous arrival patterns and examine sample path characteristics of packet occupancy in the system. Under identical inputs, we compare the multi-stage system to the corresponding single-stage system without the front end. Treating both the infinite buffer (unlimited capacity) and finite buffer (fixed capacity) cases, we prove a two-part MultiStage Multiplexing Theorem. From the first part, we conclude that any type of multi-staging is "sub-optimal." However, from the second part we find that deterministic service time queues-if they need to be installed as front ends for a larger network-actually improve upon or smooth the data traffic for downstream nodes.