We study a new online matching problem termed Online Capacitated General Matching with Knapsack (OCGMK), which generalizes the Online General Matching (OGM) problem. In the original OGM, vertices arrive sequentially and need to be paired with other vertices to maximize the total reward of pairing. Our study is the first to consider capacitated vertices in OGM: we allow each vertex to be assigned to multiple vertices up to a capacity limit. We also consider a previously unexamined knapsack constraint in OGM: assigning a pair of vertices has a cost, but the total cost is budgeted. To solve the OCGMK problem, we propose the Online Capacity-Knapsack Assignment (OCKA) algorithm, which constructs capacity-friendly sets and knapsack-friendly sets to simultaneously and effectively address both constraints. OCKA achieves a competitive ratio of ⍺=?/2?, where ?=1/(3+e^(-2)) and ? is the ratio between the overall cost of all edges and the cost budget. When the knapsack constraint is not imposed but the capacitated vertices remain, the competitive ratio of OCKA is ⍺'=1/2, recovering the previous best result for single-capacity OGM. We implement trace-driven experiments to evaluate the practical performance of OCKA on a real-world dating dataset, demonstrating the superior performance of OCKA in online dating applications.

In Federated Learning (FL) with over-the-air aggregation, the quality of the signal received at the server critically depends on the receive scaling factors. While a larger scaling factor can reduce the effective noise power and improve training performance, it also compromises the privacy of devices by reducing uncertainty. In this work, we aim to adaptively design the receive scaling factors across training rounds to balance the trade-off between training convergence and privacy in an FL system under dynamic channel conditions. We formulate a stochastic optimization problem that minimizes the overall Rényi differential privacy (RDP) leakage over the entire training process, subject to a long-term constraint that ensures convergence of the global loss function. Our problem depends on unknown future information, and we observe that standard Lyapunov optimization is not applicable. Thus, we develop a new online algorithm, termed AdaScale, based on a sequence of novel per-round problems that can be solved efficiently. We further derive upper bounds on the dynamic regret and constraint violation of AdaSacle, establishing that it achieves diminishing dynamic regret in terms of time-averaged RDP leakage while ensuring convergence of FL training to a stationary point. Numerical experiments on canonical classification tasks show that our approach effectively reduces RDP and DP leakages compared with state-of-the-art benchmarks without compromising learning performance.

This paper studies power-efficient uplink transmission design for federated learning (FL) that employs over-the-air analog aggregation and multi-antenna beamforming at the server. We jointly optimize device transmit weights and receive beamforming at each FL communication round to minimize the total device transmit power while ensuring convergence in FL training. Through our convergence analysis, we establish sufficient conditions on the aggregation error to guarantee FL training convergence. Utilizing these conditions, we reformulate the power minimization problem into a unique bi-convex structure that contains a transmit beamforming optimization subproblem and a receive beamforming feasibility subproblem. Despite this unconventional structure, we propose a novel alternating optimization (AO) approach that guarantees monotonic decrease of the objective value, to allow convergence to a partial optimum. We further consider imperfect channel state information (CSI), which requires accounting for the channel estimation errors in the power minimization problem and FL convergence analysis. We propose a CSI-error-aware joint beamforming algorithm, which can substantially outperform one that does not account for channel estimation errors. Simulation with canonical classification datasets demonstrates that our proposed methods achieve significant power reduction compared to existing benchmarks across a wide range of parameter settings, while attaining the same target accuracy under the same convergence rate.

Federated learning (FL) over wireless networks using analog transmission can efficiently utilize the communication resource but is susceptible to errors caused by noisy wireless links. In this paper, assuming a multi-antenna base station, we jointly design downlink-uplink beamforming to maximize FL training convergence over time-varying wireless channels. We derive the round-trip model updating equation and use it to analyze the FL training convergence to capture the effects of downlink and uplink beamforming and the local model training on the global model update. Aiming to maximize the FL training convergence rate, we propose a low-complexity joint downlink-uplink beamforming (JDUBF) algorithm, which adopts a greedy approach to decompose the multi-round joint optimization and convert it into per-round online joint optimization problems. The per-round problem is further decomposed into three subproblems over a block coordinate descent framework, where we show that each subproblem can be efficiently solved by projected gradient descent with fast closed-form updates. An efficient initialization method that leads to a closed-form initial point is also proposed to accelerate the convergence of JDUBF. Simulation demonstrates that JDUBF substantially outperforms the conventional separate-link beamforming design.

This work invokes the notion of f-divergence to introduce a novel upper bound on the Bayes error rate of a general classification task. We show that the proposed bound can be computed by sampling from the output of a parameterized model. Using this practical interpretation, we introduce the Bayes optimal learning threshold (BOLT) loss whose minimization enforces a classification model to achieve the Bayes error rate. We validate the proposed loss for image and text classification tasks, considering MNIST, Fashion-MNIST, CIFAR10, and IMDb datasets. Numerical experiments demonstrate that models trained with BOLT achieve performance on par with or exceeding that of cross-entropy, particularly on challenging datasets. This highlights the potential of BOLT in improving generalization.

This work addresses the trade-off between convergence and the overall delay in heterogeneous distributed learning systems, where the devices encounter diverse and dynamic communication conditions. We propose to apply adaptive sparsification across the devices and over iterations, formulating an optimization problem to minimize the overall delay while ensuring a specified level of convergence. The resultant stochastic optimization problem cannot be handled by conventional Lyapunov optimization techniques due to the dependency of the per-iteration objective function on the previous iterations. To overcome this challenge, we propose AdaSparse, an online algorithm with a novel per-slot problem that can be solved optimally by searching over a finite discrete space. We further introduce a low-complexity approximation of AdaSparse, termed LC-AdaSparse, which features linear computational complexity and diminishing approximation error. We show that AdaSparse offers strong performance guarantees, simultaneously achieving sub-linear dynamic regret in terms of delay and the optimal rate in terms of convergence. Numerical experiments on classification tasks using standard datasets and various models demonstrate that our approach effectively reduces the communication delay compared with existing benchmarks, to achieve the same levels of learning accuracy.

We consider the partitioning of a deep neural network (DNN) inference job and offloading part of it from a resource-constrained device to a resource-rich server. The inference job is required to finish within a delay constraint, but it is allowed to perform early exit at some intermediate layer of the DNN, at the cost of lower accuracy. Since in practice both the processing delay and the communication delay of offloading usually are unknown ahead of time, this is naturally modelled as an online delay-constrained accuracy maximization problem. We propose Accuracy-Optimal Delay Constrained Online Partitioning (AODPart), a lightweight online algorithm that uses an adaptive thresholding strategy to solve the offloading problem. We derive the competitive ratio for AODPart and show that it is optimal in the sense that no other online algorithm can achieve a lower deterministic competitive ratio. Furthermore, we show that AODPart is robust and provides worst-case performance guarantee even with parameter estimation error. Through experimenting with common vision and language learning models, we demonstrate that AODPart substantially outperforms state-of-the-art alternatives and returns near optimal accuracy in practice.

Inverse problems, where the goal is to recover an unknown signal from noisy or incomplete measurements, are central to applications in medical imaging, remote sensing, and computational biology. Diffusion models have recently emerged as powerful priors for solving such problems. However, existing methods either rely on projection-based techniques that enforce measurement consistency through heuristic updates, or they approximate the likelihood $p(\boldsymbol{y} \mid \boldsymbol{x})$, often resulting in artifacts and instability under complex or high-noise conditions. To address these limitations, we propose a novel framework called coupled data and measurement space diffusion posterior sampling (C-DPS), which eliminates the need for constraint tuning or likelihood approximation. C-DPS introduces a forward stochastic process in the measurement space $\{\boldsymbol{y}_t\}$, evolving in parallel with the data-space diffusion $\{\boldsymbol{x}_t\}$, which enables the derivation of a closed-form posterior $p(\boldsymbol{x}_{t-1} \mid \boldsymbol{x}_t, \boldsymbol{y}_{t-1})$. This coupling allows for accurate and recursive sampling based on a well-defined posterior distribution. Empirical results demonstrate that C-DPS consistently outperforms existing baselines, both qualitatively and quantitatively, across multiple inverse problem benchmarks.

Differential privacy (DP) limits the impact of individual training data samples by bounding their gradient norms through clipping. Conventional clipping operations assign unequal scaling factors to sample gradients with different norms, leading to a direction mismatch between the true batch gradient and the aggregation of the clipped gradients. Applying a smaller but identical scaling factor to all sample gradients alleviates this direction mismatch; however, it intensifies the magnitude mismatch by excessively reducing the aggregation norm. This work proposes a novel clipping method, termed adaptive sigmoid (AdaSig), which uses a sigmoid function with an adjustable saturation slope to clip the sample gradients. The slope is adaptively adjusted during the training process to balance the trade-off between direction mismatch and magnitude mismatch, as the statistics of sample gradients evolve over the training iterations. Despite AdaSig’s adaptive nature, our convergence analysis demonstrates that differentially private stochastic gradient descent (DP-SGD) with AdaSig clipping retains the best-known convergence rate under non-convex loss functions. Evaluating AdaSig on sentence and image classification tasks across different datasets shows that it consistently improves learning performance compared with established clipping methods.

We study the online Generalized Magician’s Problem with Multiple Workers (GMPMW), where tasks arrive sequentially and must be assigned to one of several workers for processing, with each worker consuming a stochastic amount of resources and generating an unknown reward. The system must decide on the acceptance of each task and its assignment to a worker, in order to maximize the accumulated reward within the budget. To address this problem, we propose the Online Worker Assignment (OWA) Algorithm. It optimally solves an optimization problem to balance resource allocation across workers and maintains virtual resource utilization according to the joint evolution of different workers. The competitive ratio of OWA is lower bounded by the closed-form expression $\max${${1}/{L},c$}$\cdot(1-K^{-\frac{1}{2}})$, where $L$ is the number of workers, $K$ is the resource budget, and $c$ is a constant derived from the problem instance. We perform trace-driven experiments with real-time video analytics, demonstrating the excellent capability of OWA to accommodate multiple workers in GMPMW.

Federated learning (FL) with over-the-air computation efficiently utilizes the communication resources, but it can still experience significant latency when each device transmits a large number of model parameters to the server. This paper proposes the Segmented Over-The-Air (SegOTA) method for FL, which reduces latency by partitioning devices into groups and letting each group transmit only one segment of the model parameters in each communication round. Considering a multiantenna server, we model the SegOTA transmission and reception process to establish an upper bound on the expected model learning optimality gap. We minimize this upper bound, by formulating the per-round online optimization of device grouping and joint transmit-receive beamforming, for which we derive efficient closed-form solutions. Simulation results show that our proposed SegOTA substantially outperforms the conventional full-model OTA approach and other common alternatives.

We consider online distributed optimization in a networked system, where multiple devices assisted by a server collaboratively minimize the accumulation of a sequence of global loss functions that can vary over time. To reduce the amount of communication, the devices send quantized and compressed local decisions to the server, resulting in noisy global decisions. Therefore, there exists a tradeoff between the optimization performance and the communication overhead. Existing works separately optimize computation and communication. In contrast, we jointly consider computation and communication over time, by proactively encouraging temporal similarity in the decision sequence to control the communication overhead. We propose an efficient algorithm, termed Online Distributed Optimization with Temporal Similarity (ODOTS), where the local decisions are both computation- and communication-aware. Furthermore, ODOTS uses a novel tunable virtual queue, which removes the commonly assumed Slater’s condition through a modified Lyapunov drift analysis. ODOTS delivers provable performance bounds on both the optimization objective and constraint violation. Furthermore, we consider a variant of ODOTS with multi-step local gradient descent updates, termed ODOTS-MLU, and show that it provides improved performance bounds. As an example application, we apply both ODOTS and ODOTS-MLU to enable communication-efficient federated learning. Our experimental results based on canonical image classification demonstrate that ODOTS and ODOTS-MLU obtain higher classification accuracy and lower communication overhead compared with the current best alternatives for both convex and non-convex loss functions.

In decentralized machine learning over a network of workers, each worker updates its local model as a weighted average of its local model and all models received from its neighbors. Efficient consensus weight matrix design and communication resource allocation can increase the training convergence rate and reduce the wall-clock training time. In this paper, we jointly consider these two factors and propose a novel algorithm termed Communication-Efficient Network Topology (CENT), which reduces the latency in each training iteration by removing unnecessary communication links. CENT enforces communication graph sparsity by iteratively updating, with a fixed step size, a trade-off factor between the convergence factor and a weighted graph sparsity. We further extend CENT to one with an adaptive step size (CENT-A), which adjusts the trade-off factor based on the feedback of the objective function value, without introducing additional computation complexity. We show that both CENT and CENT-A preserve the training convergence rate while avoiding the selection of poor communication links. Numerical studies with real-world machine learning data in both homogeneous and heterogeneous scenarios demonstrate the efficacy of CENT and CENT-A and their performance advantage over state-of-the-art algorithms.

We consider online distributed optimization where a server and multiple devices collaborate to minimize a sequence of time-varying global loss functions. To accommodate slow devices that may require multiple time slots to compute their local decisions, the server uses semi-asynchronous aggregation of the local decisions, which complicates device scheduling and performance optimization. In this work, we first analyze the convergence of semi-asynchronous aggregation in the presence of time-varying local update delays and loss-function weights. Our analysis leads to an online scheduling problem to minimize the accumulated age of information on the local decision updates, subject to individual long-term constraints on the total weights of the scheduled devices. We then design an efficient scheduling policy, termed Age-of-Information Minimization with Weight Limits (AIMWeL), through a modified Lyapunov optimization approach that uses the weighted sum of linear age-of-information values and quadratic virtual queues as a new Lyapunov function. We show that AIMWeL has bounded optimality ratio, via a novel double relaxation approach to handle the unique scheduling-dependent communication indicator with time-varying probabilities of completing local decision update caused by semi-asynchronous aggregation. When AIMWeL is applied to semi-asynchronous federated learning, our simulation results based on standard image classification datasets demonstrate that AIMWeL uses significantly less time to reach the same classification accuracy achieved by the current best alternatives for both convex logistic regression and non-convex convolutional neural networks.

This paper studies the design of wireless federated learning (FL) for simultaneously training multiple machine learning models. We consider round robin device-model assignment and downlink beamforming for concurrent multiple model updates. After formulating the joint downlink-uplink transmission process, we derive the per-model global update expression over communication rounds, capturing the effect of beamforming and noisy reception. To maximize the multi-model training convergence rate, we derive an upper bound on the optimality gap of the global model update and use it to formulate a multi-group multicast beamforming problem. We show that this problem can be converted to minimizing the sum of inverse received signal-to-interference-plus-noise ratios, which can be solved efficiently by projected gradient descent. Simulation shows that our proposed multi-model FL solution outperforms other alternatives, including conventional single-model sequential training and multi-model zero-forcing beamforming.

We consider wireless network virtualization (WNV) in an uplink multiple-input multiple-output system, where multiple service providers (SPs) operate in virtually isolated networks managed by an infrastructure provider (InP) that owns the communication equipment. Service isolation is achieved at the physical layer by exploiting a large number of antennas at the base stations. We formulate this WNV as a non-convex optimization problem for the InP, jointly considering the uplink receive beamforming at the BS and the transmit power of the SPs' subscribing user devices. We decompose the problem into two subproblems and derive closed-form solutions to both. We then adopt an alternating optimization approach to combine the closed-form solutions to solve the original problem. Our simulation results show that the proposed method provides strong service isolation among the SPs while retaining efficiency similar to or better than centralized beamforming without virtualization, and it substantially outperforms traditional WNV with strict resource separation.

Jobs in computing environments have diverse and heterogeneous resource requirements. This paper presents a study of online, non-preemptive scheduling algorithms for multiple identical machines under the average weighted completion time objective. The key challenge addressed is resource allocation to jobs with non-uniform demands across multiple resource types, such as CPU, memory, and storage. We propose an online algorithm, termed Multi-Resource Interval Scheduling (MRIS) that achieves a competitive ratio of 8R(1 + ϵ) for the average weighted completion time, where R is the number of resource types. To the best of the authors’ knowledge, this is the first theoretical competitive analysis under the considered system. We further show that the well-known priority queue algorithms can have arbitrarily bad competitive ratios in this setting. In numerical experiments using production workload traces from Microsoft Azure, the proposed algorithm is shown to significantly outperform priority queue algorithms and other state-of-the-art schedulers.

In modern applications, the underlying computation and communication networks are often hierarchical, which is typified by the three-layer client-edge-cloud system that has become prominent in recent times. We study minimax fairness in distributed optimization over such systems, to provide robust performance guarantee for the worst-case mixture of loss functions. We propose HierMinimax, a communication efficient distributed algorithm to solve the minimax optimization problem. We provide convergence analysis for both convex and non-convex loss functions, leading to performance bounds that enable tuning the tradeoff between the communication complexity and the optimization convergence rate. Our experiments on classification problems with canonical datasets show that HierMinimax substantially improves the fairness in learning accuracy and reduces the communication overhead compared with the current best alternatives.

While momentum-based accelerated variants of stochastic gradient descent (SGD) are widely used when training machine learning models, there is little theoretical understanding on the generalization error of such methods. In this work, we first show that there exists a convex loss function for which the stability gap for multiple epochs of SGD with standard heavy-ball momentum (SGDM) becomes unbounded. Then, for smooth Lipschitz loss functions, we analyze a modified momentum-based update rule, i.e., SGD with early momentum (SGDEM) under a broad range of step-sizes, and show that it can train machine learning models for multiple epochs with a guarantee for generalization. Finally, for the special case of strongly convex loss functions, we find a range of momentum such that multiple epochs of standard SGDM, as a special form of SGDEM, also generalizes. Extending our results on generalization, we also develop an upper bound on the expected true risk, in terms of the number of training steps, sample size, and momentum. Our experimental evaluations verify the consistency between the numerical results and our theoretical bounds. SGDEM improves the generalization error of SGDM when training ResNet-18 on ImageNet in practical distributed settings.

We consider federated learning in a wireless edge network, where multiple power-limited mobile devices collaboratively train a global model, using their local data with the assistance of an edge server. Exploiting over-the-air computation, the edge server updates the global model via analog aggregation of the local models over noisy wireless fading channels. Unlike existing works that separately optimize computation and communication at each step of the learning algorithm, in this work, we jointly optimize the training of the global model and the analog aggregation of the local models over time. Our objective is to minimize the accumulated training loss at the edge server, subject to individual long-term transmit power constraints at the mobile devices. We propose an efficient algorithm, termed Online Model Updating with Analog Aggregation (OMUAA), to adaptively update the local and global models based on the time-varying communication environment. The trained model of OMUAA is channel-and power-aware, and it is in closed form incurring low computational complexity. We study the mutual impact between model training and analog aggregation over time, to derive performance bounds on the computation and communication performance metrics. Furthermore, we consider a variant of OMUAA with double regularization on both the local and global models, termed OMUAA-DR, and show that it can significantly reduce the convergence time to reach long-term transmit power constraints. In addition, we extend both OMUAA and OMUAA-DR to enable analog gradient aggregation, while preserving their performance bounds. Simulation results based on real-world image classification datasets and typical wireless network settings demonstrate substantial performance gain of OMUAA and OMUAA-DR over the known best alternatives.

We consider cooperative multiple-input multiple-output (MIMO) precoding design with multiple access points (APs) assisted by a central controller (CC) in a fading environment. Even though each AP may have its own local channel state information (CSI), due to the communication delay in the backhaul, neither the APs nor the CC has timely global CSI. Under this hierarchical semi-online setting, our goal is to minimize the accumulated precoding deviation, between the actual local precoders executed by the APs and an ideal cooperative precoder based on timely and perfect global CSI, subject to per-AP transmit power limits. We propose an efficient algorithm, termed Semi-Online Precoding with Information Parsing (SOPIP), which accounts for the network heterogeneity in information timeliness and computational capacity. SOPIP does not require the CC to send the full global CSI to each AP. Instead, it takes advantage of the precoder structure to substantially lower the communication overhead, while allowing each AP to effectively combine its own timely local CSI with the delayed global CSI to enable adaptive precoder updates. We analyze the performance of SOPIP in the presence of multi-slot communication delay, CSI inaccuracy, and gradient estimation error, showing that it has a bounded performance gap from an offline optimal solution. Simulation results under typical cellular system settings further demonstrate the substantial performance gain of SOPIP over other centralized and distributed schemes.

Motivated by a wide range of applications from parallel computing to distributed learning, we study distributed online load balancing among multiple workers. We aim to minimize the pointwise maximum over the workers' local cost functions. We propose a novel algorithm termed Distributed Online Load Balancing with rIsk-averse assistancE (DOLBIE), which jointly considers the worker heterogeneity and system dynamics. The workload is distributed to workers in an online manner, where the underloaded workers learn to provide an appropriate amount of assistance to the most overloaded worker for the next online round without making themselves overwhelmed. In DOLBIE, all workers participate in updating the workload simultaneously, and no computationally intensive gradient or projection calculation is required. DOLBIE can be implemented in both the master-worker and fully-distributed architectures. We analyze the worst-case performance of DOLBIE by deriving an upper bound on its dynamic regret. We further demonstrate the application of DOLBIE to online batch-size tuning in distributed machine learning. Our experimental results show that, in comparison with state-of-the-art alternatives, DOLBIE can substantially speed up the training process and reduce the workers' idle time.

We consider online distributed optimization in a networked system, where multiple devices assisted by a server collaboratively minimize the accumulation of a sequence of global loss functions that can vary over time. To reduce the amount of communication, the devices send quantized and compressed local decisions to the server, resulting in noisy global decisions. Therefore, there exists a tradeoff between the optimization performance and the communication overhead. Existing works separately optimize computation and communication. In contrast, we jointly consider computation and communication over time, by encouraging temporal similarity in the decision sequence to control the communication overhead. We propose an efficient algorithm, termed Online Distributed Optimization with Temporal Similarity (ODOTS), where the local decisions are both computation- and communication-aware. Furthermore, ODOTS uses a novel tunable virtual queue, which completely removes the commonly assumed Slater’s condition through a modified Lyapunov drift analysis. ODOTS delivers provable performance bounds on both the optimization objective and constraint violation. As an example application, we apply ODOTS to enable communication-efficient federated learning. Our experimental results based on real-world image classification demonstrate that ODOTS obtains higher classification accuracy and lower communication overhead compared with the current best alternatives for both convex and non-convex loss functions.

Combining over-the-air uplink transmission and multi-antenna beamforming can improve the efficiency of federated learning (FL). However, to mitigate the significant aggregation error due to communication noise and signal distortion, pre-processing of device signals and post-processing at the server are required. In this paper, we study the optimization of receiver beamforming and device transmit weights in over-the-air FL, to minimize the total transmit power in each communication round while guaranteeing the convergence of FL. We establish sufficient convergence conditions based on the analysis of gradient descent with error and formulate a power minimization problem. An alternating optimization approach is then employed to decompose the problem into tractable subproblems, and efficient solutions are developed for these subproblems. Our proposed method is evaluated through simulation on standard image classification tasks, demonstrating its effectiveness in achieving substantial reductions in transmit power compared with existing alternatives.

Despite the many known benefits of Federated Learning (FL), in the wireless environment, its performance is significantly impacted by the statistical and system heterogeneities among the local data sets and local clients. Therefore, judicious sampling of clients and resource allocation among them are of vital importance in FL. In this work, we consider the online joint optimization of probabilistic client sampling and power allocation to improve the training performance of wireless FL. Our optimization is based on a new convergence bound for non-convex loss functions under probabilistic client sampling, which considers the different data ratios and gradient norms among clients. We propose a new algorithm based on the Lyapunov optimization framework, termed PCSPA, that accounts for how the statistical and system heterogeneities affect both the convergence rate and training time of FL, as well as the long-term power constraints and the expected number of sampled clients. Experiments on image classification with wireless FL show that the proposed algorithm can substantially outperform conventional separate optimization strategies and a state-of-the-art joint optimization method.

We study joint downlink-uplink beamforming design for wireless federated learning (FL) with a multi-antenna base station. Considering analog transmission over noisy channels and uplink over-the-air aggregation, we derive the global model update expression over communication rounds. We then obtain an upper bound on the expected global loss function, capturing the downlink and uplink beamforming and receiver noise effect. We propose a low-complexity joint beamforming algorithm to minimize this upper bound, which employs alternating optimization to breakdown the problem into three subproblems, each solved via closed-form gradient updates. Simulation under practical wireless system setup shows that our proposed joint beamforming design solution substantially outperforms the conventional separate-link design approach and nearly attains the performance of ideal FL with error-free communication links.

In many dynamic systems, decisions on system operation are updated over time, and the decision maker requires an online learning approach to optimize its strategy in response to the changing environment. When the loss and constraint functions are convex, this belongs to the general family of online convex optimization (OCO). In existing OCO works, the environment is assumed to vary in a time-slotted fashion, while the decisions are updated at each time slot. However, many wireless communication systems permit only periodic decision updates,i.e.each decision is fixed over multiple time slots, while the environment changes between the decision epochs. The standard OCO model is inadequate for these systems. Therefore, in this work, we consider periodic decision updates for OCO. We aim to minimize the accumulation of time-varying convex loss functions, subject to both short-term and long-term constraints. Feedback information about the loss functions within the current update period may be delayed and incomplete. We propose an efficient algorithm, termed Periodic Queueing and Gradient Aggregation (PQGA), which employs novel periodic queues together with possibly multi-step aggregated gradient descent to update the decisions over time. We derive upper bounds on the dynamic regret, static regret, and constraint violation of PQGA. As an example application, we study the performance of PQGA for network virtualization in a large-scale multi-antenna system shared by multiple wireless service providers. Simulation results show that PQGA converges fast and substantially outperforms the current best alternative.

This paper considers the problem of fair allocation of multiple types of resources in heterogeneous servers, along with a resource type external to those servers. Our work is motivated by the need for fair multi-resource allocation in mobile edge computing (MEC), where the users must upload their tasks over a single dedicated wireless communication link that exists outside the computing servers. We propose a fair multi-resource allocation mechanism for this environment, termed Task Share Fairness with External Resource (TSF-ER), which finds the Kalai-Smorodinsky bargaining solution satisfying important fairness properties. We show that TSF-ER is envy-free, Pareto optimal, and strategy-proof, and it satisfies the property of sharing incentive. Large-scale simulation driven by Google and Alibaba cluster trace further shows that TSF-ER significantly outperforms the existing utilitarian, Nash social welfare maximizer, and egalitarian solutions, leading to fairer resource allocation while maintaining a high level of resource utilization.

We consider online convex optimization (OCO) with multi-slot feedback delay. An agent selects a sequence of online decisions to minimize the accumulation of time-varying convex loss functions, subject to short-term and long-term constraints that may be time-varying. Both the convex loss function and the long-term constraint function may experience multiple time slots of feedback delay to be received by the agent. Existing works on OCO under this general setting has focused on the static regret, which measures the gap of losses between an online decision sequence and a time-invariant static offline benchmark. In this work, besides the static regret, we also consider a more practically meaningful metric, the dynamic regret, where the benchmark is a time-varying online optimal decision sequence. We propose an efficient algorithm, termed Delay-Tolerant Constrained-OCO (DTC-OCO), which uses a novel double regularization together with a new penalty mechanism on the long-term constraint violation, to tackle the asynchrony between information feedback and decision updates. We obtain upper bounds for its static regret, dynamic regret, and constraint violation, proving that they are sublinear under mild conditions. Furthermore, we consider a variation of DTC-OCO with multi-step gradient descent, and show it provides improved dynamic regret and constraint violation bounds for strongly convex loss functions. For numerical demonstration, we apply DTC-OCO to a general network resource allocation problem. Our simulation results suggest substantial performance gain by DTC-OCO over the current best alternative.

The strong interference suffered by users can be a severe problem in cache-enabled networks (CENs) due to the content-centric user association mechanism. To tackle this issue, multi-antenna technology may be employed for interference management. In this paper, we consider a user-centric interference nulling (IN) scheme in two-tier multi-user multi-antenna CEN, with a hybrid most-popular and random caching policy at macro base stations (MBSs) and small base stations (SBSs) to provide file diversity. All the interfering SBSs within the IN range of a user are requested to suppress the interference at this user using zero-forcing beamforming. Using stochastic geometry analysis techniques, we derive a tractable expression for the area spectral efficiency (ASE). A lower bound on the ASE is also obtained, with which we then consider ASE maximization, by optimizing the caching policy and IN coefficient. To solve the resultant mixed integer programming problem, we design an alternating optimization algorithm to minimize the lower bound of the ASE. Our numerical results demonstrate that the proposed caching policy yields performance that is close to the optimum, and it outperforms several existing baselines.

We consider federated learning in a wireless edge network, where multiple power-limited mobile devices collaboratively train a global model, using their local data with the assistance of an edge server. Exploiting over-the-air computation, the edge server updates the global model via analog aggregation of the local models over noisy wireless fading channels. Unlike existing works that separately optimize computation and communication at each step of the learning algorithm, in this work, we jointly optimize the training of the global model and the analog aggregation of local models over time. Our objective is to minimize the accumulated training loss at the edge server, subject to individual long-term transmit power constraints at the mobile devices. We propose an efficient algorithm, termed Online Model Updating with Analog Aggregation (OMUAA), to adaptively update the local and global models based on the time-varying communication environment. The trained model of OMUAA is channel- and power-aware, and it is in closed form with low computational complexity. We study the mutual impact between model training and analog aggregation over time, to derive performance bounds on the computation and communication performance metrics. Simulation results based on real-world image classification datasets and typical Long-Term Evolution network settings demonstrate substantial performance gain of OMUAA over the known best alternatives.

We consider cooperative multiple-input multiple-output (MIMO) precoding design with multiple access points (APs) assisted by a central controller (CC) in a fading environment. Even though each AP may have its own local channel state information (CSI), due to the communication delay in the backhaul, neither the APs nor the CC has timely global CSI. Under this semi-online setting, our goal is to minimize the accumulated precoding deviation between the actual local precoders executed by the APs and an ideal cooperative precoder based on the global CSI, subject to per-AP transmit power limits. We propose an efficient algorithm, termed Semi-Online Precoding with Information Parsing (SOPIP), which accounts for the network heterogeneity in information timeliness and computational capacity. SOPIP does not require the CC to send the full global CSI to each AP. Instead, it takes advantage of the precoder structure to substantially lower the communication overhead, while allowing each AP to effectively combine its own timely local CSI with the delayed global CSI to enable adaptive precoder updates. We analyze the performance of SOPIP in the presence of both multi-slot communication delay and gradient estimation error, showing that it has a bounded performance gap from an offline optimal solution. Simulation results under typical Long-Term Evolution network settings further demonstrate the substantial performance gain of SOPIP over other centralized and distributed schemes.

We consider device-to-device (D2D) communication underlaid in a cellular network to share the uplink resource of cellular users (CUs). It is a key the emerging Internet of Things to support vehicle-to-everything communication networks. In a multicell scenario, both D2D pairs and CUs may cause significant significant intercell interference (ICI) to the neighboring cells. Furthermore, due to substantial signaling overhead, we assume only partial channel state information (CSI) of D2D links at the base station. We consider joint power control, beamforming, and CU-D2D matching problem, assuming partial CSI from D2D pairs under the general Nakagami fading model. We formulate a joint receive beamforming and robust power control optimization problem for a CU-D2D pair to expected sum rate under the power budget, while meeting the minimum SINR requirements and worst case ICI limits at neighboring cells in a probabilistic sense. We propose an efficient algorithm that combines an iterative D2D feasibility check and a ratio-of-expectation approximation. A performance upper bound is also developed for benchmarking. For multiple CUs and D2D pairs, due to orthogonal channelization within each cell, we first focus on the problem of joint power control and beamforming for a CU-D2D pair and show how our proposed solution can be leveraged to find a solution for this general problem. The complexity analysis of the proposed approach is also provided. Simulation results show that the proposed algorithm gives performance close to the upper bound.

We study task scheduling and offloading in a cloud computing system with multiple users where tasks have different processing times, release times, communication times, and weights. Each user may schedule a task locally or offload it to a shared cloud with heterogeneous processors by paying a price for the resource usage. We consider four different models in this article: (i) zero task release and communication times; (ii) non-zero task release times and zero communication times; (iii) non-zero task release times and fixed communication times; and (iv) non-zero task release times and sequence-dependent communication times. Our article aims at identifying a task scheduling decision that minimizes the weighted sum completion time of all tasks, while satisfying the users’ budget constraints. We propose an efficient solution framework for this NP-hard problem. As a first step, we use a relaxation and a rounding technique to obtain an integer solution that is a constant factor approximation to the minimum weighted sum completion time. This solution violates the budget constraints, but the average budget violation decreases as the number of users increases. Thus, we develop a scalable algorithm termed Single-Task Unload for Budget Resolution (STUBR), which resolves budget violations and orders the tasks to obtain robust solutions. We prove performance bounds for the rounded solution as well as for the budget-resolved solution, for all four models considered. Via extensive trace-driven simulation for both chess and compute-intensive applications, we observe that STUBR exhibits robust performance under practical scenarios and outperforms existing alternatives. We also use simulation to study the scalability of STUBR algorithm as the number of tasks and the number of users in the system increases.

Compared with traditional observation satellites, agile earth observation satellites are capable of prolonging observation time windows (OTWs) for targets, which significantly alleviates observation conflicts, thereby facilitating imaging data collection. However, it also leads to more uncertainties in determining the start time to image targets within these longer OTWs for an agile satellite network (ASN) to collect imaging data. Furthermore, these collected data are offloaded only within short transmission time windows between data collectors and data sinks, thus resulting in a transmission scheduling problem. Toward this end, this paper investigates joint observation and transmission scheduling in ASNs, aiming at accommodating more imaging data to be collected and offloaded successfully. Specifically, we formulate the studied problem as integer linear programming (ILP) to maximize the weighted sum of scheduled imaging tasks. Then, we explore the hidden structure of this ILP and transform it into a special framework, which can be solved efficiently through semidefinite relaxation (SDR). To reduce computation complexity, we further propose a fast yet efficient algorithm by combining the advantages of the devised SDR method and a genetic algorithm with special population initialization. Finally, simulation results demonstrate that the proposed algorithm can significantly increase the weighted sum of scheduled tasks.

This paper presents a new virtualization method for the downlink of a multi-cell multiple-input multiple-output (MIMO) network, to achieve service isolation among multiple Service Providers (SPs) that share the base station resources of an Infrastructure Provider (InP). Each SP designs a virtual precoder for its users in each cell, as its service demand to the InP, without the need to be aware of the existence of the other SPs or to know the channel state information (CSI) outside the cell. The InP performs network virtualization to meet the SPs’ service demands while managing both the inter-SP and inter-cell interference. We consider coordinated multi-cell precoding at the InP and formulate an optimization problem to minimize a weighted sum of signal leakage and precoding deviation, with per-cell transmit power constraints. We propose a fully distributed semi-closed-form solution at each cell, without any CSI exchange across cells. We further propose a low-complexity scheme to allocate the virtual transmit power, for the InP to regulate between interference elimination and virtual demand maximization. Simulation results demonstrate that our precoding solution for network virtualization substantially outperforms the traditional spectrum isolation alternative. It can approach the performance of fully cooperative precoding when the number of antennas is large.

We consider online coordinated precoding design for downlink wireless network virtualization (WNV) in a multi-cell multiple-input multiple-output (MIMO) network with imperfect channel state information (CSI). In our WNV framework, an infrastructure provider (InP) owns each base station that is shared by several service providers (SPs) oblivious of each other. The SPs design their precoders as virtualization demands for user services, while the InP designs the actual precoding solution to meet the service demands from the SPs. Our aim is to minimize the long-term time-averaged expected precoding deviation over MIMO fading channels, subject to both per-cell long-term and short-term transmit power limits. We propose an online coordinated precoding algorithm for virtualization, which provides a fully distributed semi-closed-form precoding solution at each cell, based only on the current imperfect CSI without any CSI exchange across cells. Taking into account the two-fold impact of imperfect CSI on both the InP and the SPs, we show that our proposed algorithm is within an$O(\delta)$gap from the optimum over any time horizon, where$\delta $is a CSI inaccuracy indicator. Simulation results validate the performance of our proposed algorithm under two commonly used precoding techniques in a typical urban micro-cell network environment.

Network traffic classification using machine learning techniques has been widely studied. Most existing schemes classify entire traffic flows, but there are major limitations to their practicality. At a network router, the packets need to be processed with minimum delay, so the classifier cannot wait until the end of the flow to make a decision. Furthermore, a complicated machine learning algorithm can be too computationally expensive to implement inside the router. In this paper, we introduce flow-packet hybrid traffic classification (FPHTC), where the router makes a decision per packet based on a routing policy that is designed through transferring the learned knowledge from a flow-based classifier residing outside the router. We analyze the generalization bound of FPHTC and show its advantage over regular packet-based traffic classification. We present experimental results using a real-world traffic dataset to illustrate the classification performance of FPHTC. We show that it is robust toward traffic pattern changes and can be deployed with limited computational resource.

Large datasets in machine learning often contain missing data, which necessitates the imputation of missing data values. In this work, we are motivated by network traffic classification, where traditional data imputation methods do not perform well. We recognize that no existing method directly accounts for classification accuracy during data imputation. Therefore, we propose a joint data imputation and data classification method, termed generative adversarial classification network (GACN), whose architecture contains a generator network, a discriminator network, and a classification network, which are iteratively optimized toward the ultimate objective of classification accuracy. For the scenario where some data samples are unlabeled, we further propose an extension termed semi-supervised GACN (SS-GACN), which is able to use the partially labeled data to improve classification accuracy. We conduct experiments with real-world network traffic data traces, which demonstrate that GACN and SS-GACN can more accurately impute data features that are more important for classification, and they outperform existing methods in terms of classification accuracy.

We consider multi-group multicast beamforming in large-scale systems to minimize the transmit power subject to the signal-to-interference-plus-noise ratio (SINR) requirements. Based on the optimal multicast beamforming structure, we propose a fast first-order algorithm to obtain the beamforming solution. The algorithm utilizes the successive convex approximation (SCA) method and solves each SCA subproblem by dual reformulation along with the extra-gradient method for fast closed-form updates. Initialization methods are also explored, including an extragradient-based fast initialization approach that is proposed to generate initial feasible points for SCA. Simulations show that the proposed algorithm provides a near-optimal performance with substantially lower computational complexity for large-scale systems than the existing algorithm.

Malicious data manipulation reduces the effectiveness of machine learning techniques, which rely on accurate knowledge of the input data. Motivated by real-world applications in network flow classification, we address the problem of robust online learning with delayed feedback in the presence of malicious data generators that attempt to gain favorable classification outcome by manipulating the data features. We propose online algorithms termed ROLC-NC and ROLC-C when the malicious data generators are non-clairvoyant and clairvoyant, respectively. We derive regret bounds for both algorithms and show that they are sub-linear under mild conditions. We further evaluate the proposed algorithms in network flow classification via extensive experiments using real-world data traces. Our experimental results demonstrate that both algorithms can approach the performance of an optimal static offline classifier that is not under attack, while outperforming the same offline classifier when tested with a mixture of normal and manipulated data.

We consider online convex optimization (OCO) with multi-slot feedback delay, where an agent makes a sequence of online decisions to minimize the accumulation of time-varying convex loss functions, subject to short-term and long-term constraints that are possibly time-varying. The current convex loss function and the long-term constraint function are revealed to the agent only after the decision is made, and they may be delayed for multiple time slots. Existing work on OCO under this general setting has focused on the static regret, which measures the gap of losses between the online decision sequence and an offline benchmark that is fixed over time. In this work, we consider both the static regret and the more practically meaningful dynamic regret, where the benchmark is a time-varying sequence of per-slot optimizers. We propose an efficient algorithm, termed Delay-Tolerant Constrained-OCO (DTC-OCO), which uses a novel constraint penalty with double regularization to tackle the asynchrony between information feedback and decision updates. We derive upper bounds on its dynamic regret, static regret, and constraint violation, proving them to be sublinear under mild conditions. We further apply DTC-OCO to a general network resource allocation problem, which arises in many systems such as data networks and cloud computing. Simulation results demonstrate substantial performance gain of DTC-OCO over the known best alternative.

Malicious data manipulation reduces the effectiveness of machine learning techniques, which rely on accurate knowledge of the input data. Motivated by real-world applications in network flow classification, we address the problem of robust online learning with delayed feedback in the presence of malicious data generators that attempt to gain favorable classification outcome by manipulating the data features. When the feedback delay is static, we propose online algorithms termed ROLC-NC and ROLC-C when the malicious data generators are non-clairvoyant and clairvoyant, respectively. We then consider the dynamic delay case, for which we propose online algorithms termed ROLC-NC-D and ROLC-C-D when the malicious data generators are non-clairvoyant and clairvoyant, respectively. We derive regret bounds for these four algorithms and show that they are sub-linear under mild conditions. We further evaluate the proposed algorithms in network flow classification via extensive experiments using real-world data traces. Our experimental results demonstrate that the proposed algorithms can approach the performance of an optimal static offline classifier that is not under attack, while outperforming the same offline classifier when tested with a mixture of normal and manipulated data.

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

Network flow classification is essential to proper provisioning of Quality of Service (QoS). Conventional machine-learning based flow classification methods assume reliable knowledge of the flow features. However, in practice, malicious flow generators can manipulate the flow features to increase the likelihood of certain learning outcomes, e.g., in terms of the QoS requirement label. Training a classifier that is robust to such feature manipulation is imperative. In this work, we present a study on robust flow classification against malicious feature manipulation. We leverage a detailed system model to capture the relation between the classifier and malicious flow generators and propose a Stackelberggame based solution framework to train a robust classifier. We conduct extensive experimentation using real-world traces. For flows with manipulated features, the Stackelberg classifier trained by our solution framework significantly outperforms a non-robust classifier that is oblivious to manipulation, achieving accuracy close to that of the non-robust classifier on unmanipulated flows. Furthermore, the Stackelberg classifier on manipulated test flows is no worse than the non-robust classifier on unmanipulated flows.

In distributed online optimization over a computing network with heterogeneous nodes, slow nodes can adversely affect the progress of fast nodes, leading to drastic slowdown of the overall convergence process. To address this issue, we consider a new algorithm termed Distributed Any-Batch Mirror Descent (DABMD), which is based on distributed Mirror Descent but uses a fixed per-round computing time to limit the waiting by fast nodes to receive information updates from slow nodes. DABMD is characterized by varying minibatch sizes across nodes. It is applicable to a broader range of problems compared with existing distributed online optimization methods such as those based on dual averaging, and it accommodates time-varying network topology. We study two versions of DABMD, depending on whether the computing nodes average their primal variables via single or multiple consensus iterations. We show that both versions provide strong theoretical performance guarantee, by deriving upperbounds on their expected dynamic regret, which capture the variability in minibatch sizes. Our experimental results show substantial reduction in cost and acceleration in convergence compared with the known best alternative.

We consider online downlink precoding design for multiple-input multiple-output (MIMO) wireless network virtualization (WNV) in a fading environment with imperfect channel state information (CSI). In our WNV framework, a base station owned by an infrastructure provider (InP) is shared by several service providers (SPs) that are oblivious to each other. The SPs design their virtual MIMO transmission demands to serve their own users, while the InP designs the actual downlink precoding to meet the service demands from the SPs. Therefore, the impact of imperfect CSI is two-fold, on both the InP and the SPs. We aim to minimize the long-term time-averaged expected precoding deviation, considering both long-term and short-term transmit power limits. We propose a new online MIMO WNV algorithm to provide a semi-closed-form precoding solution based only on the current imperfect CSI. We derive a performance bound for our proposed algorithm and show that it is within an O(δ) gap from the optimum over any given time horizon, where δ is a normalized measure of CSI inaccuracy. Simulation results with two popular precoding techniques validate the performance of our proposed algorithm under typical urban micro-cell Long-Term Evolution network settings.

We consider the problem of fair multi-resource allocation for mobile edge computing (MEC) with multiple access points. In MEC, user tasks are uploaded over wireless communication channels to the access points, where they are then processed with multiple types of computing resources. What distinguishes fair multi-resource allocation in the MEC environment from more general cloud computing is that a user may experience different levels of wireless channel quality on different access points, so that the user's channel bandwidth demand is not fixed. Existing resource allocation studies for cloud computing generally consider Pareto Optimality (PO), Envy-Freeness (EF), Sharing Incentive (SI), and Strategy-Proofness (SP) as the most desirable fairness properties. In this work, we show these properties are no longer compatible in MEC, since there exists no resource allocation rule that can satisfy PO+EF+SP or PO+SI+SP. Hence, we propose a resource allocation rule, called Maximum Task Product (MTP), that retains PO, EF, and SI. Extensive simulation driven by Google cluster traces further shows that MTP improves resource utilization while achieving these fairness properties.

We study the problem of scheduling n tasks on m + m' parallel processors, where the processing times on m processors are known while those on the remaining m' processors are not known a priori. This semi-online model is an abstraction of certain heterogeneous computing systems, e.g., with them known processors representing local CPU cores and the unknown processors representing remote servers with uncertain availability of computing cycles. Our objective is to minimize the makespan of all tasks. We initially focus on the case m' = 1 and propose a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(nlogn). We derive its competitive ratio in comparison with the optimal offline solution. If the unknown processing times are deterministic, the competitive ratio of SRTS is shown to be either always constant or asymptotically constant in practice, respectively in cases where the processing times are independent and dependent on m. A similar result is obtained when the unknown processing times are random. Furthermore, extending the ideas of SRTS, we propose a heuristic algorithm termed SRTS-Multiple (SRTS-M) for the case m' > 1. Finally, where tasks arrive dynamically with unknown arrival times, we extend SRTS to Dynamic SRTS (DSRTS) and find its competitive ratio. Besides the proven competitive ratios, simulation results further suggest that SRTS and SRTS-M give superior performance on average over randomly generated task processing times, substantially reducing the makespan over the best known alternatives. Interestingly, the performance gain is more significant for task processing times sampled from heavy-tailed distributions.

By acquiring cloud-like capacities at the edge of a network, edge computing is expected to significantly improve user experience. In this paper, we formulate a hybrid edge-cloud computing system where an edge device with limited local resources can rent more from a cloud node and perform resource allocation to serve its users. The resource procurement and allocation decisions depend not only on the cloud's multiple rental options but also on the edge's local processing cost and capacity. We first propose an offline algorithm whose decisions are made with full information of future demand. Then, an online algorithm is proposed where the edge node makes irrevocable decisions in each timeslot without future information of demand. We show that both algorithms have constant performance bounds from the offline optimum. Numerical results acquired with Google cluster-usage traces indicate that the cost of the edge node can be substantially reduced by using the proposed algorithms, up to 80% in comparison with baseline algorithms. We also observe how the cloud's pricing structure and edge's local cost influence the procurement decisions.

We consider downlink multiple-input multiple-output (MIMO) wireless network virtualization (WNV) in a fading environment, via a base station (BS) precoding design. The BS is owned by an infrastructure provider (InP) and is shared by several service providers (SPs) who are oblivious to each other. The SPs realize their virtual-cell transmissions via MIMO precoding provided by the InP. We aim to minimize the time-averaged expected deviation of the precoding provided by the InP from the SPs' virtualization demands, considering both long-term and short-term transmit power limits at the BS. We propose an online MIMO WNV algorithm to provide a precoding solution through Lyapunov optimization. Our online precoding solution only requires the current channel state information, and it has a semi-closed form with low computational complexity. We provide an upper bound on the performance of the proposed algorithm, showing that it can be arbitrarily close to the optimum over any given time horizon. Simulation results validate the performance of our proposed algorithm under typical urban micro-cell settings.

We study the problem of joint offloading decision and resource allocation for mobile cloud networks with a computing access point (CAP) and a remote cloud center. We consider the case where the task computing requirement is not fully known before their execution. We aim to jointly optimize the offloading decisions as well as the allocation of computation and communication resources, to minimize a weighted sum of the average cost and cost variation. The problem is formulated as a mixed-integer program. We propose an efficient algorithm, termed Task Offloading and Resource Allocation with Uncertain Computing (TORAUC), and show that it always converges to a Karush-Kuhn-Tucker (KKT) point of an alternate form of the original problem, which has its binary constraints removed but guarantees an offloading decision solution that is arbitrarily close to binary. We extend TORAUC to TORAUC-MP for the case of a multi-processor CAP. Through trace-based simulation, we study the performance of TORAUC and TORAUC-MP. We observe that TORAUC is nearly optimal, and both algorithms substantially outperform several alternatives.

Large-scale machine learning (ML) models are routinely trained in a distributed fashion, due to their increasing complexity and data sizes. In a shared cluster handling multiple distributed learning workloads with a parameter server framework, it is important to determine the adequate number of concurrent workers and parameter servers for each ML workload over time, in order to minimize the average completion time and increase resource utilization. Existing schedulers for machine learning workloads involve meticulously designed heuristics. However, as the execution environment is highly complex and dynamic, it is challenging to construct an accurate model to make online decisions. In this paper, we design an experience-driven approach that learns to manage the cluster directly from experience rather than using a mathematical model. We propose Chic, a scheduler that is tailored for scheduling machine learning workloads in a cluster by leveraging deep reinforcement learning techniques. With our design of the state space, action space, and reward function, Chic trains a deep neural network with a modified version of the cross-entropy method to approximate the policy for assigning workers and parameter servers for future workloads based on the experience of the agent. Furthermore, a simplified version named Chic-Pair with a shorter training time for the policy is purposed by assigning workers and parameter servers in a pair. We compare Chic and Pair with state-of-the-art heuristics, and our results show that Chic and Chic-Pair are able to reduce the average training time significantly for machine learning workloads under a wide variety of conditions.

Mobile Edge Computing can be used to realize the low latency requirements of vehicular networks. However, by compromising the road side units (RSUs), an adversary can introduce an extra delay leading to various problems such as the wastage of edge computing resources and disruption of navigational and safety functions. The compromised RSU can for instance deliberately corrupt the PHY layer payload of the packets to be transmitted to the vehicles. With this simple attack, the adversary would increase latency and through that effect, create serious disruptions. Such an attack can affect many critical delay sensitive applications such as collision avoidance. To detect the presence of such an adversary, we propose a trust based detection system in this paper. Each vehicle transmits a feedback packet about every RSU it has interacted with to a central trusted server. Using the feedback obtained from multiple vehicles, at regular intervals, an aggregated trust value for each RSU in the network is obtained and is compared with a threshold to classify the RSU as authentic or malicious. We also present a mechanism to detect the presence of malicious vehicles reporting false feedback in the network. Simulation results presented demonstrate the effectiveness of the proposed detection mechanism and the impact of the choice of adversary parameters on the detection system.

We utilize the orthogonality and channel hardening properties of massive multiple-input multiple- output (MIMO) systems to propose an efficient uplink transmission scheme for a heterogeneous network (HetNet). Such a network consists of multiple user-equipments (UEs) communicating with a macro-cell base station (MCBS) through a small-cell BS (SCBS) where both BSs have a large number of antennas and deploy zero-forcing (ZF) detection. The SCBS helps relay UEs' information using quantize-forward (QF) relaying with Wyner-Ziv (WZ) binning and multiple-timeslot transmission for the binning indices to the MCBS. The MCBS then deploys separate and sequential decoding for each UE's message. To maximize the rate region, we optimize the quantization levels through geometric programming and further obtain the optimal transmission timeslot durations in terms of the optimal quantization. We show that the proposed scheme has linear codebook size and decoding complexity in the number of UEs, while it achieves the same rate region of other QF schemes that employ joint transmission at the SCBS and/or joint decoding at the MCBS, all of which have exponential complexity. Furthermore, simulation results show that the SCBS should employ finer quantization for UE signals that have strong UE-SCBS links compared with the UE-MCBS links, and the proposed scheme can substantially outperform several existing alternatives under a wide range of parameter settings.

We study the scheduling decision for an application consisting of dependent tasks, in a generic cloud computing system comprising a network of heterogeneous local processors and a remote cloud server. We formulate an optimization problem to find the offloading decision that minimizes the overall application execution cost, subject to an application completion deadline. Since this problem is NP-hard, we propose a heuristic algorithm termed Individual Time Allocation with Greedy Scheduling (ITAGS) to obtain an efficient solution. ITAGS first uses a binary-relaxed version of the original problem to allocate a completion deadline to each individual task, and then greedily optimizes the scheduling of each task subject to its time allowance. Through trace-based simulation using real applications, as well as various randomly generated task trees, we study the performance of ITAGS, highlighting the effect of the application deadline, communication delay, number of processors, and number of tasks. We further demonstrate the substantial performance advantage of ITAGS over existing alternatives.

We study task scheduling and offloading in a cloud computing system with multiple users, where tasks have different processing times, release times, communication times, and weights. Each user may schedule a task locally or offload it to a finite-capacity shared cloud with heterogeneous processors by paying a price for the resource usage. Our work aims at identifying a task scheduling decision that minimizes the weighted sum completion time of all tasks, while satisfying the users' budget constraints. We propose an efficient solution framework for this NP-hard problem. As a first step, we solve an integer-relaxed problem and use a rounding technique to obtain an integer solution that is a constant factor approximation to the minimum weighted sum completion time. This solution violates the budget constraints, but the average budget violation decreases as the number of users increases. Thus, we develop a scalable Single-Task Unload for Budget Resolution (STUBR) algorithm, which resolves budget violations and orders the tasks to reduce the weighted sum completion time. Our trace-driven simulation shows that STUBR exhibits robust performance under practical scenarios and outperforms several alternatives.

We consider a mobile cloud computing system with multiple users, a remote cloud server, and a computing access point (CAP). The CAP serves both as the network access gateway and a computation service provider to the mobile users. It can either process the received tasks from mobile users or offload them to the cloud. We jointly optimize the offloading decisions of all users, together with the allocation of computation and communication resources, to minimize the overall cost of energy consumption, computation, and maximum delay among users. The joint optimization problem is formulated as a mixed-integer program. We show that the problem can be reformulated and transformed into a non-convex quadratically constrained quadratic program, which is NP-hard in general. We then propose an efficient solution to this problem by semidefinite relaxation and a novel randomization mapping method. Furthermore, when there is a strict delay constraint for processing each user's task, we further propose a three-step algorithm to guarantee the feasibility and local optimality of the obtained solution. Our numerical results show that the proposed solutions give nearly optimal performance under a wide range of parameter settings, and the addition of a CAP can significantly reduce the cost of multi-user task offloading compared with conventional mobile cloud computing where only the remote cloud server is available.

In underlay device-to-device (D2D) communications, a D2D pair reuses the cellular spectrum causing interference to regular cellular users. Maximizing the performance of underlay D2D communications requires joint consideration for the achieved D2D rate and the interference to cellular users. In this paper, we consider the D2D power allocation optimization over multiple resource blocks (RBs), aimed at maximizing either the ergodic D2D rate or the ergodic sum rate of D2D and cellular users, under the long-term sum-power constraint of the D2D users and per-RB probabilistic signal-to-interference-and-noise (SINR) requirements for all cellular users. We formulate stochastic optimization problems for D2D power allocation over time. The proposed optimization framework is applicable to both uplink and downlink cellular spectrum sharing. To solve the proposed stochastic optimization problems, we first convexify the problems by introducing a family of convex constraints as a replacement for the non-convex probabilistic SINR constraints. We then present two dynamic power allocation algorithms: a Lagrange dual-based algorithm that is optimal but with a high computational complexity and a low-complexity heuristic algorithm based on dynamic time averaging. Through simulation, we show that the performance gap between the optimal and heuristic algorithms is small, and the effective long-term stochastic D2D power optimization over the shared RBs can lead to substantial gains in the ergodic D2D rate and the ergodic sum rate.

User-centric base station (BS) cooperation has been regarded as an effective solution for improving network coverage and throughput in next-generation wireless systems. However, it also introduces more complicated handoff patterns, which may potentially degrade user performance. In this paper, we aim to theoretically quantify the tradeoff between handoff cost and data rate. Two user-centric clustering modes are investigated: number-based cooperation (NBC), which is easier to implement, and distance-based cooperation (DBC), which gives higher data rate performance. In the NBC mode, a user is served by its K closest BSs, while in the DBC mode, it is served by all BSs within a given distance. However, due to the randomness of network topology, it is a challenging task to track handoffs and to characterize data rates. To address this issue, we propose a stochastic geometric analysis framework on user mobility, to derive a theoretical expression for the handoff rate experienced by an active user with arbitrary movement trajectory. Then, we characterize the average downlink user data rate under a common non-coherent joint-transmission scheme, which is used to illustrate the tradeoff between handoff rate and data rate in optimizing the cooperative cluster size. We conclude that in the NBC (resp. DBC) mode, the optimal cluster size is asymptotically inversely (resp. inversely) proportional to the square of the user speed and asymptotically inversely (resp. inversely) proportional to the BS intensity. Finally, computer simulation is conducted to validate the correctness and usefulness of our analysis.

We consider a general multi-user mobile cloud computing (MCC) system where each mobile user has multiple independent tasks. These mobile users share the computation and communication resources while offloading tasks to the cloud. We study both the conventional MCC where tasks are offloaded to the cloud through a wireless access point, and MCC with a computing access point (CAP), where the CAP serves both as the network access gateway and a computation service provider to the mobile users. We aim to jointly optimize the offloading decisions of all users as well as the allocation of computation and communication resources, to minimize the overall cost of energy, computation, and delay for all users. The optimization problem is formulated as a non-convex quadratically constrained quadratic program, which is NP-hard in general. For the case without a CAP, an efficient approximate solution named MUMTO is proposed by using separable semidefinite relaxation (SDR), followed by recovery of the binary offloading decision and optimal allocation of the communication resource. To solve the more complicated problem with a CAP, we further propose an efficient three-step algorithm named MUMTO-C comprising of generalized MUMTO SDR with CAP, alternating optimization, and sequential tuning, which always computes a locally optimal solution. For performance benchmarking, we further present numerical lower bounds of the minimum system cost with and without the CAP. By comparison with this lower bound, our simulation results show that the proposed solutions for both scenarios give nearly optimal performance under various parameter settings, and the resultant efficient utilization of a CAP can bring substantial cost benefit.

For device-to-device (D2D) underlaid cellular networks, the perfect channel state information (CSI) may not be available at the base station (BS). In this work, under an assumption of partial CSI, we study the problem of maximizing the expected sum rate for a cellular user (CU) and a D2D pair, with receive beamforming at the BS, subject to minimum SINR requirements for both the CU and D2D pair, per-node maximum power, and inter-cell interference constraints in multiple neighboring cells. We solve this non-convex joint optimization problem in two steps. We first consider the D2D admissibility problem to determine whether the D2D pair can reuse the channel resource of the CU. We then propose a robust power control algorithm using a ratio-of-expectation approximation to maximize the expected sum rate. For benchmarking, we further provide an upper bound on the maximum expected sum rate. Simulation results show that our proposed solution gives performance close to the upper bound.

We revisit the problem of assigning n jobs to m machines/servers. We study this problem under more general settings, which capture important aspects of applications that arise in networking and information systems. In particular, we consider jobs that have placement constraints and machines that are heterogeneous. The cost incurred at a machine is given by any general convex function on the number of jobs assigned to it. We aim to minimize the sum cost and the maximum differential cost. Through a network-flow equivalence transformation, we observe how these two objectives are fundamentally related, showing that sum-cost minimization implies maximum-differential-cost minimization. We propose an efficient algorithm termed Maximum Edge-Cost Cycle Cancelling (MEC3) to solve the sum-cost minimization problem with O(n2m2) time complexity. Furthermore, for applications where only the maximum differential cost is of concern, we further improve the efficiency of MEC3by proposing an early stop condition. We implement MEC3and two other algorithms from the literature. Using benchmark input instances, we show that MEC3has substantially lower run time than the other algorithms.

We study the problem of scheduling n tasks on m + m' parallel processors, where the processing times on m processors are known while those on the remaining m' processors are not known a priori. This semi-online model is an abstraction of certain heterogeneous computing systems, e.g., with the m known processors representing local CPU cores and the unknown processors representing remote servers with uncertain availability of computing cycles. Our objective is to minimize the makespan of all tasks. We initially focus on the case m' = 1 and propose a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(n log n). We derive its competitive ratio in comparison with the optimal offline solution. If the unknown processing times are deterministic, the competitive ratio of SRTS is shown to be either always constant or asymptotically constant in practice, respectively in cases where the processing times are independent and dependent on m. A similar result is obtained when the unknown processing times are random. Furthermore, extending the ideas of SRTS, we propose a heuristic algorithm termed SRTS-Multiple (SRTS-M) for the case m' > 1. Besides the proven competitive ratios, simulation results further suggest that SRTS and SRTS-M give superior performance on average over randomly generated task processing times, substantially reducing the makespan over the best known alternatives. Interestingly, the performance gain is more significant for task processing times sampled from heavy-tailed distributions.

We consider a general multi-user mobile cloud computing system with a computing access point (CAP), where each mobile user has multiple independent tasks that may be processed locally, at the CAP, or at a remote cloud server. The CAP serves both as the network access gateway and a computation service provider to the mobile users. We aim to jointly optimize the offloading decisions of all users' tasks as well as the allocation of computation and communication resources, to minimize the overall cost of energy, computation, and delay for all users. This problem is NP-hard in general. We propose an efficient three-step algorithm comprising of semidefinite relaxation (SDR), alternating optimization (AO), and sequential tuning (ST). It is shown to always compute a locally optimal solution, and give nearly optimal performance under a wide range of parameter settings. Through evaluating the performance of different combinations of the three components of this SDR-AO-ST algorithm, we provide insights into their roles and contributions in the overall solution. We further compare the performance of SDR-AO-ST against a lower bound to the minimum cost, purely local processing, purely cloud processing, and hybrid local-cloud processing without using the CAP. Our numerical results demonstrate the effectiveness of the proposed algorithm in the joint management of computation and communication resources in mobile cloud computing systems with a CAP.

Statistical characterization of the signal-to-interference-plus-noise ratio (SINR) via its cumulative distribution function (CDF) is ubiquitous in a vast majority of technical contributions in the area of cellular networks since it boils down to averaging the Laplace transform of the aggregate interference, a benefit accorded at the expense of confinement to the simplistic Rayleigh fading. In this work, to capture diverse fading channels that appear in realistic outdoor/indoor wireless communication scenarios, we tackle the problem differently. By exploting the moment generating function (MGF) of the SINR, we succeed in analytically assessing cellular networks performance, namely the achievable rate and and the bit error probability (BEP), over the shadowed κ-μ, κ-μ and η-μ fading models. These models offer higher flexibility to capture diverse and more realistic fading environments than the classical Rayleigh, Nakagami-m, and Rician ones.

This paper provides an analytically tractable framework for investigating a fading model-free statistical distribution of the signal-to-interference-plus-noise power ratio (SINR) in Poison distributed cellular networks subject to device-to-device (D2D) transmissions. Our main finding show that a closed-form SINR distribution may be obtained for any fading scenario in which the per-link power gain follows the product of two Fox's H-function probability density function thereby subsuming most of the coverage probability expressions previously presented for all the known simple and composite fading models.

We consider both offline and online computational offloading of tasks from multiple users to a cloud or nearby cloud at the edge. We model the offline problem as an -player finite game where each user has access to information from other users, and we use an optimization approach to find a mixed-strategy Nash equilibrium solution. We also consider a practical online version wherein tasks arrive over time and a user does not require information from other users. We suggest a solution to this online problem by adopting a payoff-based reinforcement learning algorithm, which converges to a pure-strategy solution. Through simulation, we observe that the trends of the Nash equilibrium obtained from the offline technique and the pure-strategy point obtained from the online solution are similar. While the offline algorithm obtains a better solution on average, the online algorithm is much faster, particularly for larger systems.

Statistical characterization of the signal-tointerference-plus-noise ratio (SINR) via its cumulative distribution function is ubiquitous in a vast majority of technical contributions in the area of cellular networks, since it boils down to averaging the Laplace transform of the aggregate interference, a benefit accorded at the expense of confinement to the simplistic Rayleigh fading. In this paper, to capture diverse fading channels that arise in realistic outdoor/indoor wireless communication scenarios, we tackle the problem differently. By exploiting the moment generating function of the SINR, we succeed in analytically assessing cellular networks performance over the shadowed κ-μ, κ-μ, and η-μ fading models. These channel models offer high flexibility by capturing diverse fading channels, including Rayleigh, Nakagami-m, Rician, and Rician shadow fading distributions. These channel models have been recently promoted for their capability to accurately model dense urban environments, future femtocells, and device-to-device shadowed channels. In addition to unifying the analysis for different channel models, this paper integrates the coverage, the achievable rate, and the bit error probability, which are largely treated separately in the literature. The developed model and analysis are validated over a broad range of simulation setups and parameters.

We study the scheduling of computational tasks on one local processor and one remote processor with communication delay. This problem has important application in cloud computing. Although the communication time to transmit a task can be inferred from the known data size of the task and the transmission bandwidth, the processing time of the task is generally unknown until it is processed to completion. Given a set of independent tasks with unknown processing times, our objective is to minimize makespan. We study the problem under two scenarios: (1) the communication times of the tasks to the remote processor are smaller than their corresponding processing times on the remote processor, and (2) the communication times of the tasks to the remote processor are larger than their corresponding processing times on the remote processor. For the first scenario we propose the Semi-online Partitioning and Communication (SPaC) algorithm, and for the second scenario we propose the SPaC-Restart (SPaC-R) algorithm. Even though the offline version of this problem, with a priori known processing times, is NP-hard, we show that the proposed semionline algorithms achieve O(1) competitive ratios for their intended scenarios. We also provide competitive ratios for both algorithms for more general communication times. We use simulation to demonstrate that SPaC and SPaC-R outperform online list scheduling and performs comparably well with the best known offline heuristics.

We investigate distributed flow control and power allocation strategies for delay-aware device-to-device (D2D) communication underlaying large wireless networks, where D2D pairs reuse the resource blocks of interior cellular users (CUEs). We consider a distributed D2D power allocation framework, where the D2D pairs individually attempt to maximize their own time-average throughput utility, while collectively guaranteeing the time-average coverage probability of CUEs in multiple cells. We design a novel method to compute the individual budget of interference from each D2D pair to CUEs based on stochastic geometry tools. Then, accounting for time-varying channel fading and dynamic D2D traffic arrival, we design a distributed interference-and-delay-aware (DIDA) flow control and power allocation strategy based on Lyapunov optimization and several interference estimation methods. We also analytically derive the performance bounds of D2D pairs, and prove that the coverage probability of CUEs can be guaranteed regardless of the interference estimation error at D2D receivers. Finally, simulation results suggest that adaptive interference estimation methods are preferred and demonstrate that the DIDA strategy achieves substantial performance improvement against alternative strategies.

For device-to-device (D2D) communication under laid in a cellular network with uplink resource sharing, both cellular and D2D pairs may cause significant inter-cell interference (ICI) at a neighboring base station (BS). In this paper, under optimal BS receive beamforming, we jointly optimize the power of a cellular user (CU) and a D2D pair for their sum rate maximization, while satisfying minimum SINR requirements and worst-case ICI limit in multiple neighboring cells. We solve this non-convex joint optimization problem in two steps. First, the necessary and sufficient condition for the D2D admissibility under given constraints is obtained. Finally, we consider joint power control of the CU and D2D transmitters. We propose a power control algorithm to maximize the sum rate. Depending on the severity of ICI that D2D and CU may cause, we categorize the feasible solution region into five cases, each of which may further include several scenarios based on minimum SINR requirements. The proposed algorithm is optimal when ICI to a single neighboring cell is considered. For multiple neighboring cells, we provide an upper bound on the performance loss by the proposed algorithm and conditions for its optimality. We further extend our consideration to the scenario of multiple CUs and D2D pairs, and formulate the joint power control and CU-D2D matching problem. We show how our proposed solution for one CU and one D2D pair can be utilized to solve this general joint optimization problem. Simulation demonstrates the effectiveness of our power control algorithm and the nearly optimal performance of the proposed approach in the setting of multiple CUs and D2D pairs.

We consider a cellular network where each cell contains multiple source-destination pairs communicating through multiple amplify-and-forward relays using orthogonal channels. We propose an optimal relay beamforming design that minimizes the maximum interference at the neighboring cells subject to per-relay power limits and minimum received signal-to-noise ratio (SNR) requirements. Even though the problem is non-convex, we show that it has zero Lagrange duality gap, and we convert its dual problem to a semi-definite programming problem. Depending on the values of the optimal dual variables, we study three cases to obtain the optimal beam vectors accordingly. This results in an iterative algorithm that provides a semi-closed-form optimal solution. We extend our algorithm to the problem of maximizing the minimum SNR subject to some pre-determined maximum interference constraints at neighboring cells, by the solution to the min-max interference problem along with a bisection search. The solution to this max-min SNR problem gives insight into the worst-case signal-to-interference-and-noise ratio given some maximum interference target. The performance of the proposed algorithm is studied numerically, both for when the knowledge of interference channel is perfect and for when it is imperfect due to either limited feedback or channel estimation error.

Hybrid automatic repeat request (HARQ) is widely used in heterogeneous cellular networks (HCNs) to improve communication reliability. The temporal interference correlation caused by the common set of interferers makes the performance of HARQ more complex, especially for Type-II HARQ where the unsuccessful packets are combined with the new one to decode the packet. In general, due to the complexity of network performance analysis, the existing research focused on the performance of HARQ in single-tier wireless networks without considering cell association or base station (BS) load or the case that the combined number of transmissions is no larger than 2. In view of this, we study the performance of HARQ in HCNs jointly considering the temporally correlated interference, flexible cell association, and BS load. To this end, we adopt the popular HCN model, where different types of BSs in HCNs are modeled as K independent Poisson point processes with different densities and transmission powers. Leveraging the tool of stochastic geometry, we derive the success probability and delay-limited throughput for HCNs with Type-I HARQ and Type-II HARQ, respectively, for any number of transmissions. We show that the network performance in multiple time slots is decided by the performance in a single time slot and the temporal interference correlation. Finally, we conduct simulations to validate our analysis and show that the analysis without considering temporal interference correlation overestimates the performance of HCNs with HARQ.

Cloud radio access network (C-RAN) is emerging as a potential alternative for the next generation RAN by merging RAN and cloud computing together. In this paper, we consider the baseband unit (BBU) pool of C-RAN as a collection of virtual machines (VMs). We allow each user equipment (UE) to associate with multiple VMs in the BBU pool, and each remote radio head (RRH) can only serve a limited number of UEs. Under this model, we jointly optimize the VM activation in the BBU pool and sparse beamforming in the coordinated RRH cluster, which is constrained by limited fronthaul capacity, to minimize the system cost of C-RAN. We formulate this problem as a mixed-integer nonlinear programming problem, and then propose efficient methods to optimize the number of active VMs, as well as the sparse beamforming vectors. Moreover, we derive a closed-form solution for the beamforming vectors. Simulation results suggest that our proposed algorithms have better performance than the benchmark algorithms in terms of both system cost and robustness.

In underlay device-to-device (D2D) communication, a D2D pair reuses the cellular spectrum and creates interference to regular cellular users. Optimal operation requires joint consideration for the achieved D2D rate and the added interference to cellular users. Most existing work on D2D rate maximization concerns only the simplified scenario where the D2D pair has access to a single channel or resource block. In this work, we present an optimization solution to allocate the D2D transmission power over multiple channels, to maximize the sum rate between D2D and cellular users, under a sum-power constraint on the D2D transmitter and minimum SINR guarantees at each RB for all cellular users. The proposed optimization is applicable to both uplink and downlink cellular spectrum sharing. Our simulation studies further shed light into how the maximum sum rate is impacted by the available D2D power and the SINR guarantees.

We consider a mobile cloud computing system consisting of multiple users, one computing access point (CAP), and one remote cloud server. The CAP can either process the received tasks from mobile users or offload them to the cloud. We aim to jointly optimize the offloading decisions of all users and the CAP, together with communication and processing resource allocation, to minimize the overall cost of energy, computation, and the maximum delay among all users. It is shown that the problem can be formulated as a non-convex quadratically constrained quadratic program, which is NP-hard in general. We further propose an efficient solution to this problem by semidefinite relaxation and a novel randomization mapping method. Our simulation results show that the proposed algorithm gives nearly optimal performance with only a small number of randomization iterations.

We consider a general multi-user mobile cloud computing system where each mobile user has multiple independent tasks. These mobile users share the communication resource while offloading tasks to the cloud. We aim to jointly optimize the offloading decisions of all users as well as the allocation of communication resource, to minimize the overall cost of energy, computation, and delay for all users. The optimization problem is formulated as a non-convex quadratically constrained quadratic program, which is NP-hard in general. An efficient approximate solution is proposed by using separable semidefinite relaxation, followed by recovery of the binary offloading decision and optimal allocation of the communication resource. For performance benchmark, we further propose a numerical lower bound of the minimum system cost. By comparison with this lower bound, our simulation results show that the proposed algorithm gives nearly optimal performance under various parameter settings.

This paper considers a downlink Coordinated Multi Point (CoMP) transmission network, where the base stations (BSs) are connected to a central unit via backhaul links to serve mobile users (MUs). The objective is to jointly optimize the BS mode (active or sleep), MU association, and cooperative beamforming to minimize the total power consumption including backhauling power. We formulate the problem as a mixed-integer non-convex problem under the constraints of signal-to-interference-plus-noise ratio (SINR) requirements and limited BS power. By exploiting a hidden convexity structure of the SINR, the problem is first transformed equivalently into a mixed-integer second-order core programming (MI-SOCP) problem. Due to the coupled integer variables, the complexity of exhaustive search grows exponentially with network size, which motivates developing low-complexity heuristic algorithms. We propose a novel Two-stage Rank Selection (TRS) method to approximately solve the coupled MI-SOCP problem by determining the BS operation mode and MU association successively, which enables the remaining beamforming computation to be achieved through an efficient SOCP solution. We compare the computational complexity and numerical performance of TRS against several state-of-the-art alternatives. Analytical and simulation results demonstrate that the proposed method can significantly reduce the computational complexity and the total power consumption over existing alternatives.

User-centric base station (BS) cooperation has been regarded as an effective solution to improve network coverage and throughput in next-generation wireless systems. However, it also introduces more complicated handoff patterns, which may potentially degrade user performance. In this paper, we aim to quantify the number of handoffs in user-centric cooperative wireless networks. The challenges are two-fold: (1) BSs are spatially randomly deployed, and (2) user-centric BS cooperation further creates complicated network topologies so that it is difficult to track handoffs in the system. We propose a stochastic geometric analysis framework on user mobility, to derive a theoretical expression for the handoff rate experienced by an active user with arbitrary movement trajectory. Furthermore, we characterize the average downlink user data rate under a common non-coherent joint-transmission scheme, which is used to illustrate the tradeoff between handoff rate and data rate in optimizing the cooperative cluster size for each user. Finally, computer simulation is conducted to validate the correctness and usefulness of our analysis.

Providing quality-of-service guarantees by means of fair sharing has never been more challenging in datacenters. Due to the heterogeneity of machine configurations, datacenter jobs frequently specify placement constraints, restricting them to run on a particular class of machines meeting specific hardware/software requirements. In addition, jobs have diverse demands across multiple resource types, and may saturate any of the CPU, memory, or storage resources. Despite the rich body of recent work on datacenter scheduling, it remains unclear how multi-resource fair sharing is defined and achieved for jobs with placement constraints. In this paper, we propose a new sharing policy called Task Share Fairness (TSF). With TSF, jobs are better off sharing the datacenter, and are better off reporting demands and constraints truthfully. We have prototyped TSF on Apache Mesos and confirmed its service guarantees in a 50-node EC2 cluster. Trace-driven simulations have further revealed that TSF speeds up 60% of tasks over existing fair schedulers.

Multi-resource fair schedulers have been widely implemented in compute clusters to provide service isolation guarantees. Existing multi-resource sharing policies, notably Dominant Resource Fairness (DRF) and its variants, are designed for unconstrained jobs that can run on all machines in a cluster. However, an increasing number of datacenter jobs specify placement constraints and can only run on a particular class of machines meeting specific hardware/software requirements (e.g., GPUs or a particular kernel version). We show that directly extending existing policies to constrained jobs either compromises isolation guarantees or allows users to gain more resources by deceiving the scheduler. It remains unclear how multi-resource fair sharing is defined and achieved in the presence of placement constraints. We address this open problem by a new sharing policy, called Task Share Fairness (TSF), that provides provable isolation guarantees and is strategy-proof against gaming the allocation policy. TSF is shown to be envy-free and Pareto optimal as well.

We investigate the optimal relay beamforming problem for multi-user peer-to-peer communication with amplify-and-forward relaying in a multi-channel system. Assuming each source-destination (S-D) pair is assigned an orthogonal channel, we formulate the problem as a min-max per-relay power minimization problem with minimum signal-to-noise (SNR) guarantees. After showing that strong Lagrange duality holds for this nonconvex problem, we transform its Lagrange dual problem to a semi-definite programming problem and obtain the optimal relay beamforming vectors. We identify that the optimal solution can be obtained in three cases, depending on the values of the optimal dual variables. These cases correspond to whether the minimum SNR requirement at each S-D pair is met with equality, and whether the power consumption at a relay is the maximum among relays at optimality. We obtain a semi-closed form solution structure of relay beam vectors, and propose an iterative approach to determine relay beam vector for each S-D pair. We further show that the reverse problem of maximizing the minimum SNR with per-relay power budgets can be solved using our proposed algorithm with an iterative bisection search. Through simulation, we analyze the effect of various system parameters on the performance of the optimal solution. Furthermore, we investigated the effect of imperfect channel side information of the second hop on the performance and quantify the performance loss due to either channel estimation error or limited feedback.

In heterogeneous cellular networks (HCNs), the interference received at a user is correlated over time slots since it comes from the same set of randomly located base stations (BSs). This results in the correlations of link successes, thus affecting network performance. Under the assumptions of a K-tier Poisson network, strongest long-term averaged biased-received- power based BS association, and independent Rayleigh fading, we first quantify the correlation coefficients of interference. We observe that the interference correlation is independent of the number of tiers, BS density, signal-to-interference-ratio (SIR) threshold, and transmit power. Then, we study the correlations of link successes in terms of the joint success probability over multiple time slots.We show that analysis without considering the temporal interference correlation underestimates the joint success probability. Moreover, we explore the effects of BS density, transmit power and user association bias on the joint success probability. In particular, BS density and transmit power affect the joint success probability of the overall network by influencing the association probability of each tier. We also reveal that the unbiased cell association outperforms the biased cell association in terms of the joint success probability. Finally, we conduct simulations to validate our analysis.

We consider a wireless cellular network with multiple amplify-and-forward (AF) relays in each cell, assisting the communication of multiple source-destination pairs with relay transmission beamforming. Our objective is to minimize the maximum interference power among all active receivers in a neighboring cell subject to per-relay power and minimum received SNR constraints. We propose an efficient algorithm to obtain the optimal relay beamforming vectors. We show that even though the optimization problem is non-convex, it has zero Lagrange duality gap and can be converted to a semi-definite programming problem. The performance of the proposed algorithm is studied numerically, both for the case where the interference channel information is exactly known and for the case of inaccurate channel information due to either limited feedback or channel estimation error. It is demonstrated that the min-max interference approach substantially outperforms the alternative where we simply minimize the maximum relay transmission power.

We study optimal radio resource allocation across multiple tiers of a heterogeneous wireless network in order to maximize the downlink sum throughput. Different from prior works, we consider both the randomness of base stations in space and dynamic user traffic session arrivals in time, accounting for both elastic and inelastic user traffic. A new stochastic analysis framework, which accommodates both spatial and temporal dimensions, is proposed to quantify the throughput objective. The derived throughput function is not in closed form and is non-concave in terms of the radio resource allocation factors to be optimized, hindering the search for an efficient optimization solution. Therefore, we further develop closed-form concave bounds that envelop the throughput function, to form convex approximations of the original optimization problem that can be solved efficiently. We characterize the performance gap when these bounds are used instead of the original objective. Both analytical bounding and simulation experiments demonstrate that the proposed solution is nearly optimal.

The hybrid cloud architecture utilizes both privately owned cloud servers and rented instances from public cloud providers, to offer flexible services that are particularly suited to enterprise computing. The task scheduler at a hybrid cloud decides both the selection of tasks to be offloaded to the public cloud and the scheduling of the remaining tasks on the processors at the private cloud. In this work, we consider the problem of minimizing a weighted sum of the makespan at the private cloud and the offloading cost to the public cloud. In contrast to prior works, we do not assume that the task processing times are known a priori. We show that the original problem can be solved by the same algorithms designed toward minimizing the maximum between the makespan and the weighted offloading cost, only with doubling of the competitive ratio. Furthermore, the latter problem can be equivalently transformed into a makespan minimization problem with unrelated processors. In the case where all tasks arrive at time zero, we propose a Greedy-One-Restart (GOR) algorithm based on online estimation of the unknown processing times, and one-time cancellation and rescheduling of tasks that turn out to require long processing times. We derive its competitive ratio and show that it is upper bounded on the order of the square root of the number of private processors, which is a substantial improvement over the best known algorithms in the literature. We present also a tight constant competitive ratio for the special two-processor case. In the case where tasks arrive dynamically with unknown arrival times, we extend GOR to Dynamic-GOR (DGOR) and find its competitive ratio. Further simulation results demonstrate that GOR and DGOR are favorable also in terms of average performance, in comparison with the well-known list scheduling algorithm and idealized offline algorithms.

In multi-tier heterogeneous wireless networks (HWNs), both horizontal and vertical handoffs impact the signaling overhead and quality of service in the system. However, they are difficult to analyze due to the diverse and irregularly shaped cells in HWNs. The causes of this irregularity are three-fold: (1) small-cell base stations (BSs) tend to be deployed with a high level of spatial randomness; (2) BSs are likely to aggregate around highly populated geographical regions; (3) various transmission power levels in different tiers further create diverse cell sizes and shapes. In this work we present a new stochastic geometric analysis framework on user mobility in HWNs. Each tier of BSs is modeled as either a Poisson point process (PPP) or a Poisson cluster process (PCP), to capture their spatial randomness and their non-uniform and dependent aggregation in space. Flexible user association is also taken into consideration, such that various scales of cell sizes are accommodated. We derive analytical expressions for the rates of all handoff types experienced by an active user with arbitrary movement trajectory. We also demonstrate an example application of the proposed analysis, in optimizing the multi-tier BS selection by users, to balance the tradeoff between data rate and handoff overhead. Finally, extensive simulation is conducted to validate the correctness and usefulness of our analysis.

Horizontal and vertical handoffs are important ramifications of user mobility in multitier heterogeneous wireless networks. They directly impact the signaling overhead and quality of calls. However, they are difficult to analyze due to the irregularly shaped network topologies introduced by multiple tiers of cells. In this paper, a stochastic geometric analysis framework on user mobility is proposed, to capture the spatial randomness and various scales of cell sizes in different tiers. We derive theoretical expressions for the rates of all handoff types experienced by an active user with arbitrary movement trajectory. Furthermore, noting that the data rate of a user depends on the set of cell tiers that it is willing to use, we provide guidelines for optimal tier selection under various user velocities, taking both the handoff rates and the data rate into consideration. Empirical studies using user mobility trace data and extensive simulation are conducted, demonstrating the correctness and usefulness of our analysis.

The joint user association and spectrum allocation problem is studied for multi-tier heterogeneous networks (HetNets) in both downlink and uplink in the interference-limited regime. Users are associated with base-stations (BSs) based on the biased downlink received power. Spectrum is either shared or orthogonally partitioned among the tiers. This paper models the placement of BSs in different tiers as spatial point processes and adopts stochastic geometry to derive the theoretical mean proportionally fair utility of the network based on the coverage rate. By formulating and solving the network utility maximization problem, the optimal user association bias factors and spectrum partition ratios are analytically obtained for the multi-tier network. The resulting analysis reveals that the downlink and uplink user associations do not have to be symmetric. For uplink under spectrum sharing, if all tiers have the same target signal-to-interference ratio (SIR), distance-based user association is shown to be optimal under a variety of path loss and power control settings. For both downlink and uplink, under orthogonal spectrum partition, it is shown that the optimal proportion of spectrum allocated to each tier should match the proportion of users associated with that tier. Simulations validate the analytical results. Under typical system parameters, simulation results suggest that spectrum partition performs better for downlink in terms of utility, while spectrum sharing performs better for uplink with power control.

We study joint spectrum allocation and user association in heterogeneous cellular networks with multiple tiers of base stations. A stochastic geometric approach is applied as the basis to derive the average downlink user data rate in a closed-form expression. Then, the expression is employed as the objective function in jointly optimizing spectrum allocation and user association, which is of a non-convex programming in nature. A computationally efficient structured spectrum allocation and user association (SSAUA) approach is proposed, solving the problem optimally and asymptotically optimally in two regions divided by a parameter specific threshold. A surcharge pricing scheme (SPS) is also presented, such that the designed association bias values can be achieved in Nash equilibrium. Simulations and numerical studies are conducted to validate the accuracy and efficiency of the proposed SSAUA approach and SPS.

We study the multi-resource allocation problem in cloud computing systems where the resource pool is constructed from a large number of heterogeneous servers, representing different points in the configuration space of resources such as processing, memory, and storage. We design a multi-resource allocation mechanism, called DRFH, that generalizes the notion of Dominant Resource Fairness (DRF) from a single server to multiple heterogeneous servers. DRFH provides a number of highly desirable properties. With DRFH, no user prefers the allocation of another user; no one can improve its allocation without decreasing that of the others; and more importantly, no coalition behavior of misreporting resource demands can benefit all its members. DRFH also ensures some level of service isolation among the users. As a direct application, we design a simple heuristic that implements DRFH in real-world systems. Large-scale simulations driven by Google cluster traces show that DRFH significantly outperforms the traditional slot-based scheduler, leading to much higher resource utilization with substantially shorter job completion times.

Infrastructure-as-a-service (IaaS) clouds offer diverse instance purchasing options. A user can either run instances on demand and pay only for what it uses, or it can prepay to reserve instances for a long period, during which a usage discount is entitled. An important problem facing a user is how these two instance options can be dynamically combined to serve time-varying demands at minimum cost. Existing strategies in the literature, however, require either exact knowledge or the distribution of demands in the long-term future, which significantly limits their use in practice. Unlike existing works, we propose two practical online algorithms, one deterministic and another randomized, that dynamically combine the two instance options online without any knowledge of the future. We show that the proposed deterministic (resp., randomized) algorithm incurs no more than 2 - α (resp., e/(e-1 + α)) times the minimum cost obtained by an optimal offline algorithm that knows the exact future a priori, where a is the entitled discount after reservation. Our online algorithms achieve the best possible competitive ratios in both the deterministic and randomized cases, and can be easily extended to cases when short-term predictions are reliable. Simulations driven by a large volume of real-world traces show that significant cost savings can be achieved with prevalent IaaS prices.

Infrastructure-as-a-Service clouds offer diverse pricing options, including on-demand and reserved instances with various discounts to attract different cloud users. A practical problem facing cloud users is how to minimize their costs by choosing among different pricing options based on their own demands. In this paper, we propose a new cloud brokerage service that reserves a large pool of instances from cloud providers and serves users with price discounts. The broker optimally exploits both pricing benefits of longterm instance reservations and multiplexing gains. We propose dynamic strategies for the broker to make instance reservations with the objective of minimizing its service cost. These strategies leverage dynamic programming and approximation algorithms to rapidly handle large volumes of demand. Our extensive simulations driven by large-scale Google cluster-usage traces have shown that significant price discounts can be realized via the broker.

Multi-tier architecture improves the spatial reuse of radio spectrum in cellular networks, but it introduces complicated heterogeneity in the spatial distribution of transmitters, which brings new challenges in interference analysis. In this work, we present a stochastic geometric model for evaluating the uplink interference in a two-tier network considering multi-type users and base stations. Each type of tier-1 users and tier-2 base stations are modeled as independent homogeneous Poisson point processes, and tier-2 users are modeled as locally non-homogeneous clustered Poisson point processes centered at tier-2 base stations. By applying a superposition-aggregation-superposition approach, we quantify the interference at both tiers. Our model is also able to capture the impact of two types of exclusion regions, where either tier-2 base stations or tier-2 users are restricted to avoid cross-tier interference. As an important application of this analytical model, an intensity planning scenario is investigated, in which we aim to maximize the total income of the network operator with respect to the intensities of tier-2 cells, under constraints on the outage probabilities of tier-1 and tier-2 users. The result of our interference analysis suggests that this maximization can be converted to a standard convex optimization problem. Finally, numerical studies further demonstrate the correctness of our analysis.

We introduce a stochastic analytical framework to compare the performance of open-access and closed-access modes in a two-tier femtocell network with regard to the uplink interference and the outage at both the macrocell and femtocell levels. A stochastic geometric approach is employed as the basis for our analysis. We present numerical methods to characterize the distributions of the uplink interference and the outage probabilities. We further derive sufficient conditions for the open-access and closed-access modes to outperform each other in terms of the outage probability at either the macrocell level or the femtocell level. This leads to closed-form expressions to upper and lower bound the difference in the targeted received power between the two access modes. Simulations are conducted to validate the accuracy of the analytical model and the correctness of the bounds.

A cross-network cross-layer design method is proposed to exploit the trunking, diversity, and best service assignment gains available in a heterogeneous wireless network (HWN), consisting of orthogonal radio access networks (RANs) and interference-limited RANs. Accounting for traffic-level dynamics and channel fading, we jointly design the distribution strategy for elastic and inelastic traffic, and the radio resource management strategy for RANs, in a network-separable control architecture. Optimal and quantified near-optimal radio allocation schemes are proposed for each type of RAN, which are combined into an on-line design framework that over time provides asymptotically optimal performance, maximizing the sum throughput utility for elastic traffic while guaranteeing the throughput requirements of inelastic traffic. Extensive simulation results demonstrate substantial performance improvement against suboptimal alternatives.

Middleboxes are widely deployed in today's networks. They apply a variety of complex network functions to transform, filter, and optimize incoming traffic based on the payload of packets. These functions require the support of multiple types of resources, such as CPU and link bandwidth, for processing incoming packets. Hence, a multi-resource packet scheduling algorithm is needed to allow flows to share these resources fairly and efficiently. However, unlike traditional fair queueing where bandwidth is the only concern, we show in this paper that fairness and efficiency are conflicting objectives that cannot be achieved simultaneously in the presence of multiple resources. Ideally, a scheduling algorithm should allow network operators to flexibly specify their fairness and efficiency requirements, so as to meet the Quality of Service demands while keeping the system at a high utilization level. Yet, existing multi-resource scheduling algorithms focus on fairness only, and may lead to poor resource utilization. In this paper, we propose a new scheduling algorithm to achieve a flexible tradeoff between fairness and efficiency for packet processing, consuming both CPU and link bandwidth. Experimental results based on both real-world implementation and trace-driven simulation suggest that trading off a modest level of fairness can potentially improve the efficiency to the point where the system capacity is almost saturated.

We present a new method for spectrum allocation in a heterogeneous cellular network with multiple tiers of randomly placed base stations and random user session arrivals. Different from previous works, inelastic network traffic is considered, so as to accommodate application sessions with fixed data rate requirements. We first quantify the average downlink sum throughput of the network in terms of a given spectrum allocation vector. We then derive concave upper and lower bounds to the throughput to allow efficient approximate solutions to optimize spectrum allocation. We show that the proposed approach has a worst case optimization performance gap of 12.6% and further demonstrate via simulation that its actual performance is often near optimal.

We study the multi-resource allocation problem in cloud computing systems where the resource pool is constructed from a large number of heterogeneous servers, representing different points in the configuration space of resources such as processing, memory, and storage. We design a multi-resource allocation mechanism, called DRFH, that generalizes the notion of Dominant Resource Fairness (DRF) from a single server to multiple heterogeneous servers. DRFH provides a number of highly desirable properties. With DRFH, no user prefers the allocation of another user; no one can improve its allocation without decreasing that of the others; and more importantly, no user has an incentive to lie about its resource demand. As a direct application, we design a simple heuristic that implements DRFH in real-world systems. Large-scale simulations driven by Google cluster traces show that DRFH significantly outperforms the traditional slot-based scheduler, leading to much higher resource utilization with substantially shorter job completion times.

We study joint spectrum allocation and user association in heterogeneous cellular networks with multiple tiers of base stations. A stochastic geometric approach is applied as the basis to derive the average downlink user data rate in a closed-form expression. Then, the expression is employed as the objective function in jointly optimizing spectrum allocation and user association, which is of non-convex programming in nature. A computationally efficient Structured Spectrum Allocation and User Association (SSAUA) approach is proposed, solving the optimization problem optimally when the density of users is low, and near-optimally with a guaranteed performance bound when the density of users is high. A Surcharge Pricing Scheme (SPS) is also presented, such that the designed association bias values can be achieved in Nash equilibrium. Simulations and numerical studies are conducted to validate the accuracy and efficiency of the proposed SSAUA approach and SPS.

Middleboxes are ubiquitous in today's networks. They perform deep packet processing such as content-based filtering and transformation, which requires multiple categories of resources (e.g., CPU, memory bandwidth, and link bandwidth). Depending on the processing requirement of traffic, packet processing for different flows may consume vastly different amounts of resources. Multi-resource fair queueing allows flows to obtain a fair share of these resources, providing service isolation across flows. However, previous solutions for multi-resource fair queueing are either expensive to implement at high speeds, or incurring high scheduling delay for flows with uneven weights. In this paper, we present a new fair queueing algorithm, called Group Multi-Resource Round Robin (GMR3), that schedules packets in O(1) time, while achieving near-perfect fairness with a low scheduling delay bounded by a small constant. To our knowledge, it is the first provably fair, highly efficient multi-resource fair queueing algorithm with bounded delay.

We present a jointly optimal selection and scheduling scheme for the lossy transmission of frames governed by a dependency relation and a delay constraint over a link with limited capacity. A main application for this is scalable video streaming. Our objective is to select a subset of frames and decide their transmission schedule such that the overall video quality at the receiver is maximized. The problem is solved for two of the most common classes of dependency structures for video encoding, which include as a special case the popular hierarchical dyadic structure. We formally characterize the structural properties of an optimal transmission schedule in terms of frame dependency. It is shown that regardless of the subset of frames selected for transmission, any optimal schedule has an equivalent canonical form that is a subsequence of a unique universal sequence containing all frames. The canonical form can be computed efficiently through the construction of a dependency tree. This leads to separable but jointly optimal frame selection and scheduling algorithms that have quadratic computational complexity in the number of frames. Simulation with video traces demonstrates that the optimal scheme can substantially outperform existing suboptimal alternatives.

Horizontal and vertical handoffs are important ramifications of user mobility in multi-tier heterogeneous cellular networks. They directly affect the signaling overhead and quality of calls in the system. However, they are difficult to analyze due to the irregularly shaped network topologies introduced by multiple tiers of cells. In this work, a stochastic geometric analysis framework on user mobility is proposed, to capture the spatial randomness and various scales of cell sizes in different tiers. We derive theoretical expressions for the rates of all handoff types experienced by an active user with arbitrary movement trajectory. Empirical study using real user mobility trace data and extensive simulation are conducted, demonstrating the correctness and usefulness of our analysis.

Market-driven spectrum auctions offer an efficient way to improve spectrum utilization by transferring unused or underused spectrum from its primary license holder to spectrum-deficient secondary users. Such a spectrum market exhibits strong locality in two aspects: 1) that spectrum is a local resource and can only be traded to users within the license area, and 2) that holders can partition the entire license areas and sell any pieces in the market. We design a spectrum double auction that incorporates such locality in spectrum markets, while keeping the auction economically robust and computationally efficient. Our designs are tailored to cases with and without the knowledge of bid distributions. Complementary simulation studies show that spectrum utilization can be significantly improved when distribution information is available. Therefore, an auctioneer can start from one design without any a priori information, and then switch to the other alternative after accumulating sufficient distribution knowledge. With minor modifications, our designs are also effective for a profit-driven auctioneer aiming to maximize the auction revenue.

Based on the Gauss-Markov channel model, we investigate the stochastic feedback control for transmit beamforming in multiple-input-single-output systems and design practical implementation algorithms leveraging techniques in dynamic programming and reinforcement learning. We first validate the Markov decision process formulation of the underlying feedback control problem with a 4R-variable (4R-V) state, where R is the number of the transmit antennas. Due to the high complexity of finding an optimal feedback policy under the 4R-V state, we consider a reduced 2-V state. As opposed to a previous study that assumes the feedback problem under such a 2-V state remaining an MDP formulation, our analysis indicates that the underlying problem is no longer an MDP. Nonetheless, the approximation as an MDP is shown to be justifiable and efficient. Based on the quantized 2-V state and the MDP approximation, we propose practical implementation algorithms for feedback control with unknown state transition probabilities. In particular, we provide model-based offline and online learning algorithms, as well as a model-free learning algorithm. We investigate and compare these algorithms through extensive simulations and provide their efficiency analysis. According to these results, the application rule of these algorithms is established under both statistically stable and unstable channels.

Infrastructure-as-a-Service clouds offer diverse pricing options, including on-demand and reserved instances with various discounts to attract different cloud users. A practical problem facing cloud users is how to minimize their costs by choosing among different pricing options based on their own demands. In this paper, we propose a new cloud brokerage service that reserves a large pool of instances from cloud providers and serves users with price discounts. The broker optimally exploits both pricing benefits of long-term instance reservations and multiplexing gains. We propose dynamic strategies for the broker to make instance reservations with the objective of minimizing its service cost. These strategies leverage dynamic programming and approximate algorithms to rapidly handle large volumes of demand. Our extensive simulations driven by large-scale Google cluster-usage traces have shown that significant price discounts can be realized via the broker.

Middleboxes are widely deployed in today's enterprise networks. They perform a wide range of important network functions, including WAN optimizations, intrusion detection systems, network and application level firewalls, etc. Depending on the processing requirement of traffic, packet processing for different traffic flows may consume vastly different amounts of hardware resources (e.g., CPU and link bandwidth). Multi-resource fair queueing allows each traffic flow to receive a fair share of multiple middlebox resources. Previous schemes for multi-resource fair queueing, however, are expensive to implement at high speeds. Specifically, the time complexity to schedule a packet is O(log n), where n is the number of backlogged flows. In this paper, we design a new multi-resource fair queueing scheme that schedules packets in a way similar to Elastic Round Robin. Our scheme requires only O(1) work to schedule a packet and is simple enough to implement in practice. We show, both analytically and experimentally, that our queueing scheme achieves nearly perfect Dominant Resource Fairness.

The location of active users is an important factor in the performance analysis of mobile multicell networks, but it is difficult to quantify due to the wide variety of user mobility and session patterns. In particular, the channel holding times in each cell may be arbitrarily distributed and dependent on those in other cells. In this work, we study the stationary distribution of users by modeling the system as a multi-route queueing network with Poisson inputs. We consider arbitrary routing and arbitrary joint probability distributions for the channel holding times in each route. Using a decomposition-composition approach, we show that the user distribution (1) is insensitive to the user movement patterns, (2) is insensitive to general and dependent distributed channel holding times, (3) depends only on the average arrival rate and average channel holding time at each cell, and (4) is completely characterized by an open network with M/M/∞ queues. This result is validated by experiments with the Dartmouth user mobility traces.

The concept of vehicle-to-grid (V2G) has gained recent interest as more and more electric vehicles (EVs) are put to use. In this paper, we consider a dynamic aggregator-EVs system, where an aggregator centrally coordinates a large number of EVs to perform regulation service. We propose a Welfare-Maximizing Regulation Allocation (WMRA) algorithm for the aggregator to fairly allocate the regulation amount among the EVs. The algorithm operates in real time and does not require any prior knowledge on the statistical information of the system. Compared with previous works, WMRA accommodates a wide spectrum of vital system characteristics, including limited EV battery size, EV self charging/discharging, EV battery degradation cost, and the cost of using external energy sources. Furthermore, our simulation results indicate that WMRA can substantially outperform a suboptimal greedy algorithm.

Cloud service pricing plays a pivotal role towards the success of cloud computing. Existing pricing schemes, however, either provide no service guarantees (e.g., Spot Instances in Amazon EC2), or use static on-demand pricing in which the price cannot respond quickly to market dynamics (e.g., On-demand Instances in Amazon EC2). To overcome these problems, in this paper we design dynamic auctions where computing instances are periodically auctioned off to accommodate user demands over time. We address the two main challenges of revenue maximization and auction truthfulness. Our design encompasses a capacity allocation scheme, which determines the amount of instances to be auctioned off in each period, as well as the underlying auction mechanisms, based on dynamic payment schemes corresponding to the proposed capacity allocations over time. We show that our design is two-dimensionally truthful, and it is asymptotically optimal when demand is sufficiently high. Furthermore, by identifying certain optimization structures, we substantially reduce the computational complexity of our solution. Extensive simulations show that our design closely tracks market changes, while generating higher revenues than on-demand pricing.

Middleboxes have found widespread adoption in today's networks. They perform a variety of network functions such as WAN optimization, intrusion detection, and network-level firewalls. Processing packets to serve these functions often require multiple middlebox resources, e.g., CPU and link band-width. Furthermore, different packet traffic flows may consume significantly different amounts of various resources, depending on the network functions that are applied. Multi-resource fair queueing is therefore needed to allow flows to share multiple middlebox resources in a fair manner. In this paper, we clarify the fairness requirements of a queueing scheme and present Dominant Resource Generalized Processor Sharing (DRGPS), a fluid flow-based fair queueing idealization that strictly realizes Dominant Resource Fairness (DRF) at all times. As a form of Generalized Processor Sharing (GPS) running on multiple resources, DRGPS serves as a benchmark that practical packet-by-packet fair queueing algorithm should follow. With DRGPS, techniques and insights that have been developed for traditional fair queueing can be leveraged to schedule multiple resources. As a case study, we extend Worst-case Fair Weighted Fair Queueing (WF2Q) to the multi-resource setting and analyze its performance.

We introduce a comprehensive analytical framework to compare between open access and closed access in two-tier femtocell networks, with regard to uplink interference and outage. Interference at both the macrocell and femtocell levels is considered. A stochastic geometric approach is employed as the basis for our analysis. We further derive sufficient conditions for open access and closed access to outperform each other in terms of the outage probability, leading to closed-form expressions to upper and lower bound the difference in the targeted received power between the two access modes. Simulations are conducted to validate the accuracy of the analytical model and the correctness of the bounds.

This paper addresses the relation between message delivery delay and reliability for the communication between a vehicle and a road side unit (RSU). We focus on sparse vehicular sensor networks (VSNs), where timely message delivery and reliable transmission are of significant importance. We present a mathematical framework for the message delivery delay distribution for a two-lane road, where vehicles in one direction act as message carriers for the ones in the other direction and have the freedom to leave the road from randomly distributed road junctions with a certain probability. Packet generator vehicles store the original packets till meeting an RSU while sending multiple copies of each packet to packet carrier vehicles. Our analysis offers an analytical tool for an intelligent transportation system (ITS) service provider to determine the minimum RSU density required to cover a road for meeting a probabilistic requirement of the message delay. Extensive computer simulation results show the accuracy of our analysis and clearly indicate the relation of packet delay and the number of packet replicas.

The location of active users is an important factor in the performance analysis of mobile multicell networks, but it is difficult to quantify due to the wide variety of user mobility and session patterns. In this work, we study the stationary distribution of users by modeling the system as a multi-route queueing network with Poisson inputs. We consider arbitrary routing and arbitrary joint probability distributions for the channel holding times in each route. Through a decomposition-composition approach, we derive a closed-form expression for the joint stationary distribution for the number of users in all cells. The stationary user distribution (1) is insensitive to the user movement patterns, (2) is insensitive to general and dependently distributed channel holding times, (3) depends only on the average arrival rate and average channel holding time at each cell, and (4) is completely characterized by an open network with M/M/∞ queues. We use the Dartmouth trace to validate our analysis, which shows that the analytical model is accurate when new session arrivals are Poisson and remains useful when non-Poisson session arrivals are also included in the data set. Our results suggest that accurate calculation of the user distribution, and other associated metrics such as the system workload, can be achieved with much lower complexity than previously expected.

A dynamic optimization algorithm is proposed for the joint allocation of subframes, resource blocks, and power in the Type 1 inband relaying scheme mandatory in the LTE-Advanced standard. Following the general framework of Lyapunov optimization, we decompose the original problem into three sub-problems in the forms of convex programming, linear programming, and mixed-integer programming. We solve the last sub-problem in the Lagrange dual domain, showing that it has zero duality gap, and that a primal optimum can be obtained with probability one. The proposed algorithm dynamically adapts to traffic and channel fluctuations, it accommodates both instantaneous and average power constraints, and it obtains arbitrarily near-optimal sum utility of each user's average throughput. Simulation results demonstrate that the joint optimum can significantly outperform suboptimal alternatives.

We consider amplify-and-forward multi-antenna relaying between a single pair of source and destination under per-antenna power constraints. Our objective is to obtain the optimal relay processing matrix to minimize the maximum individual antenna power for a given received SNR target. The problem is not convex, but it can be shown to satisfy strong Lagrange duality. We reveal a prominent structure of this problem, by establishing its duality with direct point-to-point SIMO beamforming with an uncertain noise. This enables us to derive a semi-closed form expression for the optimal relay processing matrix that depends on a set of dual variables, thus converting the original optimization of a N×N matrix with (N+1) constraints, to a dual problem with (N+1) variables and three constraints. We further show that the dual problem has a semi-definite programming form, so that the proposed solution has polynomial worst-case complexity.

Cloud resources are usually priced in multiple markets with different service guarantees. For example, Amazon EC2 prices virtual instances under three pricing schemes -- the subscription option (a.k.a., Reserved Instances), the pay-as-you-go offer (a.k.a., On-Demand Instances), and an auction-like spot market (a.k.a., Spot Instances) -- simultaneously. There arises a new problem of capacity segmentation: how can a provider allocate resources to different categories of pricing schemes, so that the total revenue is maximized? In this paper, we consider an EC2-like pricing scheme with traditional pay-as-you-go pricing augmented by an auction market, where bidders periodically bid for resources and can use the instances for as long as they wish, until the clearing price exceeds their bids. We show that optimal periodic auctions must follow the design of m+1-price auction with seller's reservation price. Theoretical analysis also suggests the connections between periodic auctions and EC2 spot market. Furthermore, we formulate the optimal capacity segmentation strategy as a Markov decision process over some demand prediction window. To mitigate the high computational complexity of the conventional dynamic programming solution, we develop a near-optimal solution that has significantly lower complexity and is shown to asymptotically approach the optimal revenue.

We aim to enhance the end-to-end rate of a general dual-hop relay network with multiple channels and finite modulation formats, by jointly optimizing channel pairing, power allocation, and integer bit loading. Such an optimization problem has both a discrete feasible region, due to the combinatoric nature of channel pairing, and a discrete objective, due to the bit loading requirement. For this type of mixed-integer programming problems, the Lagrange dual method generally is inapplicable, due to the non-zero duality gap. However, by exploring the structure of our problem, we are able to bound the gap to within one bit, allowing the extraction of an exact optimal integer solution. We further present complexity reduction techniques, and demonstrate that the proposed solution only requires a computational complexity that is polynomial in the number of channels, realizing efficient implementation in practical systems. Through numerical experiments, we show that the jointly optimal solution can significantly outperform common sub-optimal alternatives.

We consider the problem of jointly optimizing channel pairing, channel-user assignment, and power allocation, to maximize the weighted sum-rate, in a single-relay cooperative system with multiple channels and multiple users. Common relaying strategies are considered, and transmission power constraints are imposed on both individual transmitters and the aggregate over all transmitters. The joint optimization problem naturally leads to a mixed-integer program. Despite the general expectation that such problems are intractable, we construct an efficient algorithm to find an optimal solution, which incurs computational complexity that is polynomial in the number of channels and the number of users. We further demonstrate through numerical experiments that the jointly optimal solution can significantly improve system performance over its suboptimal alternatives.

We consider the problem of jointly optimizing channel pairing, channel-user assignment, and power allocation in a single-relay multiple-access system. The optimization objective is to maximize the weighted sum-rate under total and individual power constraints on the transmitters. By observing the special structure of a three-dimensional assignment problem derived from the original problem, we propose a polynomial-time algorithm based on continuity relaxation and dual minimization. The proposed method is shown to be optimal for all relaying strategies that give a concave rate function in terms of power constraints.

Market-driven spectrum auctions offer an efficient way to improve spectrum utilization by transferring unused or under-used spectrum from its primary license holder to spectrum-deficient secondary users. Such a spectrum market exhibits strong locality in two aspects: 1) that spectrum is a local resource and can only be traded to users within the license area, and 2) that holders can partition the entire license areas and sell any pieces in the market. We design a spectrum double auction that incorporates such locality in spectrum markets, while keeping the auction economically robust and computationally efficient. Our designs in District are tailored to cases with and without knowledge of bid distributions. An auctioneer can start from one design without any a priori information, and then switch to the other alternative after accumulating sufficient distribution knowledge. Complementary simulation studies show that spectrum utilization can be significantly improved when distribution information is available.

In this paper, we address the relation between message delivery delay and reliability for the communication between a vehicle and a road side unit (RSU). We focus on sparse or low density vehicular ad hoc networks (VANETs), where timely message delivery and reliable transmission are of significant importance. We present an exact message delivery delay distribution for a two-lane road, where vehicles in one direction act as message carriers for the ones in the other direction and have the freedom to leave the road from randomly distributed exits with a certain probability. Our analysis offers a tool for an intelligent transportation system (ITS) service provider to determine the minimal separation between two consecutive RSUs for meeting a probabilistic requirement of the message delay. Simulation results show the accuracy of our analysis.

Despite much research on the throughput of relaying networks under idealized interference models, many practical wireless networks rely on physical-layer protocols that preclude the concurrent reception of multiple transmissions. In this work, we develop analytical frameworks for the uplink of a multi- source single-channel relay-aided wireless system where transmissions are scheduled to avoid collisions. We study amplify-and-forward and decode-and-forward strategies, in both time-sharing and network-coded variants, and provide mathematical models to investigate their achievable rate regions. Both general and optimal power allocations are considered. We also find the cut-set outer bounds for the rate regions. Moreover, we present a comparison between these methods with the simple time sharing scheme. Our numerical results reveal that optimizing power allocation favors the time sharing scheme significantly more than it does the relaying schemes, so that time sharing under some circumstances can provide higher maximum sum rates, even if the links to the relay have strong channel gains. The proposed analysis provides a means to quantitatively evaluate the efficacy of relaying under the collision model, leading to pragmatic design guidelines.

Opportunistic routing significantly increases unicast throughput in wireless mesh networks by effectively utilizing the wireless broadcast medium. With network coding, opportunistic routing can be implemented in a simple and practical way without resorting to a complicated scheduling protocol. Traditionally, due to the constraints of computational complexity, a protocol utilizing network coding needs to partition the data into multiple segments and encode only packets in the same segment. However, it is extremely challenging to decide the optimal time to move to the transmissions of the next segment, and existing designs all resort to different heuristic ideas that might harm network throughput. To address this problem, we proposeSlideOR, a new protocol to encode source packets in overlapping sliding windows such that coded packets from one window position may be useful towards decoding the source packets inside another window position. Through extensive simulations, we show thatSlideORoutperforms the existing solutions and is amenable to much simpler implementation than solutions with complicated scheduling among multiple segments.

In this paper, we consider the problem of optimal control for throughput utility maximization in cognitive radio networks with dynamic user arrivals and departures. The cognitive radio network considered in this paper consists of a number of heterogeneous sub-networks. These sub-networks may be power-constrained and are required to operate in such a way that the average total interference received on primary channels are kept below given thresholds. We develop a control policy that performs joint admission control and resource scheduling. Through Lyapunov optimization techniques, we show that the proposed policy achieves a utility performance within O(¿) of optimality for any positive ¿. We further show that this arbitrarily closeness to optimality comes at the price of having a delay that is O(1/¿) in admitting users. We also propose constant factor approximations of the policy for distributed implementation.

We study the effect of relay cluster selection on throughout in multi-hop cooperative communications with one source and one destination. We evaluate the effective relay throughput as a function of the source transmission rate and the network outage probability. Assuming channel side information (CSI) only available at the receivers, we formulate the cluster size optimization to maximize throughput. Furthermore, since the bottleneck of the multi-hop relaying is at the first hop where there is in general a lack of cooperation from the source, for the scenario where CSI is available at the source, we may incorporate opportunistic relay selection at the first hop in the cluster optimization problem. Our results demonstrate how the optimal selection of cluster sizes can significantly increase the relaying throughput.

Fairness index among competing hosts in communication networks is an important system measurement. Several fairness index measurements have been proposed in the technical literature. However, most of these measurements, such as the max/min fairness index and Jain's index, reflect only a long-term average fairness of the system. Instantaneous fairness property has not been captured. In this paper, we propose a new fairness index to reflect such short-term fairness and long-term fairness at the same time. Comparisons of our proposed fairness index, termed Fairness Index based on Variational Distance (FIVD), and related fairness indices are presented to show the benefit of our measurement.

Video streaming over wireless links is a challenging problem due to both the unreliable, time-varying nature of the wireless channel and the stringent delivery requirements of media traffic. Layered encoded video can be used to improve the system performance by adapting the sending rate for different video frame layers to the varying network and playout situations. In this paper, we study the adaptive control of sending rates for both the base layer and enhancement layer based on feedback information from the wireless receiver. We formulate the problem in a framework of Markov decision processes to minimize a weighted sum of video quality and playout continuity degradation. In order to decrease the computation complexity, we then develop an online greedy algorithm, which only considers the current control time period. Simulation results show that the propose adaptive rate control provides significantly improved video quality and playout smoothness. Furthermore, when rate control is not performed very frequently, the greedy algorithm achieves a video distortion rate nearly matching that of the ideal optimal dynamic programming policy.

In this paper, we study power allocation (PA) in a single-relay OFDM system with limited feedback. We propose a PA scheme that uses a codebook of quantized PA vectors designed offline and known to the source, relay, and destination. The destination, which has full knowledge of channel side information (CSI), chooses one of the codebook vectors and conveys back to the source and relay. With the limited amount of available feedback, the design of an appropriate codebook is central to PA, which varies depending on the destination's strategy to choose the optimal PA vector. Assuming high received SNR on either link in the relay path, we first derive the optimal PA solutions as the function of channel realizations with two design criteria, maximizing capacity and minimizing error rate. It is found that when there is high received SNR in either the relay path or the direct path, the optimal solutions for both criteria reduce to simple forms. For maximizing capacity, the available power should be equally allocated to each OFDM subcarrier shared by the source and relay; while for minimum error rate, the available power should be allocated such that the received SNRs for all subcarriers at the destination are the same. The findings lead us to the sub-optimal solutions with great complexity reduction. We then present an adaptation of Lloyd's algorithm to construct a codebook to quantize the optimal PA vectors subject to the amount of feedback. Simulations show that a mild to negligible performance loss can be achieved with only a few bits of feedback at different SNR values.

With the co-existence of different wireless networks, which exhibit largely different bandwidth and coverage characteristics, much interest has been involved in integrating these networks to support smooth and efficient multimedia services. In this paper, we present an analytical framework for variable-bit-rate (VBR) video streaming in a two-tier wireless network with VBR channels. We derive the expected number of jitters and average buffering delay during video playback as measures of system performance. Our objective is to discover heterogeneous networking attributes that may influence the streaming performance, in terms of the tradeoff between jitter frequency and buffering delay. Through experimenting with a wide range of fixed, separate, and jointly optimal jitter-recovery buffering schemes, based on buffering delay, buffered data, and buffered playback duration, we quantify the benefit of incorporating user location information in streaming over heterogeneous wireless networks.

In this paper, we investigate into optimal admission control policies for Heterogeneous Wireless Networks (HWN), considering an integration of wireless mesh networks with an overlaying cellular infrastructure. In order to characterize the overflow traffic from the underlaying mesh to the overlay, a Partially-Observable Markov-Modulated Poisson Process (PO-MMPP) traffic model is developed. This model captures the burstiness of the overflow traffic under the imperfect observability of the mesh network states. Then, by modeling the overlay network as a controlled PO-MMPP/M/C/C queueing system and obtaining structured decision theoretic results, it is shown that the optimal control policies for this class of HWNs can be characterized as monotonic threshold curves. Further, these results are used to design a computationally efficient algorithm to determine the optimal policy in terms of thresholds. Numerical observations suggest that the proposed algorithm is efficient in terms of time-complexity and can drastically reduce the cost of dropped and blocked calls.

The highly stochastic nature of wireless environments makes it desirable to monitor link loss rates in wireless sensor networks. In this paper, we study the loss inference problem in sensor networks with network coding. Unlike traditional transmission protocols, network coding offers reliable communication without using control messages for individual packets. We show, however, that network coding changes the fundamental connection between path and link loss probabilities such that new inference algorithms need to be developed. As end- to-end data are not sufficient to compute link loss rates precisely, we propose inference algorithms based on Bayesian principles to discover the set of highly lossy links in sensor networks. We show that our algorithms achieve high detection and low false-positive rates through extensive simulations.

Node churn and failures exist as fundamental characteristics in both peer-to-peer (P2P) and sensor networks. Peers in P2P networks are highly dynamic, whereas sensors are not dependable. As such, maintaining the persistence of periodically measured data in a scalable fashion has become a critical challenge in such systems, without the use of centralized servers. To better cope with node dynamics and failures, we propose priority random linear codes (RLCs), as well as their affiliated predistribution protocols, to maintain measurement data in different priorities, such that critical data have a higher opportunity to survive node failures than data of less importance. A salient feature of priority RLCs is the ability to partially recover more important subsets of the original data with higher priorities, when it is not feasible to recover all of them due to node dynamics. We present extensive analytical and experimental results to show the effectiveness of priority RLCs.

Cooperative communication is emerging as an effective approach for realizing efficient wireless networks. Performance of these networks has been shown to be enhanced significantly by dynamic resource allocation, especially in orthogonal frequency division multiplexing (OFDM) systems, where there are more degrees of freedom. On the other hand, dynamic resource allocation imposes signalling and computational overhead on the system. In this paper, a multi-relay OFDM system is considered, where the cooperation gain of distributed antenna array is exploited. First we introduce the optimal power allocation problem and discuss the signaling overhead for implementing the optimal solution. We then propose suboptimal schemes with considerably less overhead and study the conditions under which they perform close to the optimal scheme. Furthermore, we investigate how imperfect implementation of these scheme results in performance degradation. We also analyze how much feedback is needed to implement this scheme with a desirable accuracy.

Wireless sensor networks consist of unreliable and energy-constrained sensors connecting to each other wirelessly. As measured data may be lost due to sensor failures, maintaining the persistence of periodically measured data in a scalable fashion has become a critical challenge in sensor networks, without the use of centralized servers. To cope with node failures, while providing convenient access to measured data, we propose geometric random linear codes, to encode data in a hierarchical fashion in geographic regions with different sizes, such that data are easy to access, if the original sensors producing the data are alive. Otherwise, data are persistently available elsewhere in the network. Although our coding scheme is simple, we have shown that it enjoys the same low encoding cost as sparse random linear codes, while dramatically decreasing the decoding cost. We present extensive analytical and experimental results to show the effectiveness of geometric random linear codes.

With network coding, intermediate nodes between the source and the receivers of an end-to-end communication session are not only capable of relaying and replicating data messages, but also of coding incoming messages to produce coded outgoing ones. It has been the traditional wisdom in information theory that network coding improves the capacity of multicast sessions in directed networks. Studies have also shown that network coding is beneficial for content distribution in peer-to-peer networks, since it resolves the "last block" problem, and eliminates content reconciliation. In this paper, we show that such benefits of network coding does not come without costs and trade-offs. In particular, we refute the previous claim that peers receive linearly independent coded blocks with very high probabilities. Using example scenarios and extensive simulations, we show that it is very likely for peers to receive linearly dependent non-innovative blocks, thus decreasing their efficiency as these redundant blocks consume bandwidth. We observe that such redundancy of network coding is critically dependent on the randomness and sparsity of the P2P topology. We conclude with suggestions on topologies of certain characteristics that are preferred over others, in order to minimize the network coding redundancy, the time to distribute data, and the server cost.

Opportunistic routing significantly increases unicast throughput in wireless mesh networks by effectively utilizing the wireless broadcast medium. With network coding, opportunistic routing can be implemented in a simple and practical way without resorting to a complicated scheduling protocol. Due to constraints of computational complexity, a protocol utilizing network coding needs to perform segmented network coding, which partitions the data into multiple segments and encode only packets in the same segment. However, existing designs transmit only one segment at any given time while waiting for its acknowledgment, which degrades performance as the size of the network scales up. In this paper, we propose CodeOR, a new protocol that uses network coding in opportunistic routing to improve throughput. By transmitting a window of multiple segments concurrently, it improves the performance of existing work by a factor of two on average (and a factor of four in some cases). CodeOR is especially appropriate for real-time multimedia applications through the use of a small segment size to decrease decoding delay, and is able to further increase network throughput with a smaller packet size and a larger window size.

Most routing protocols in disruption tolerant networks (DTN) use redundant transmissions to explore the diversities in routing paths in order to reduce data transmission delay. However, mobile nodes in DTN usually have limited energy and may prefer fewer transmissions for longer lifetime. Hence, it is vital to carefully balance the tradeoff between data transmission delay and the amount of transmissions among mobile nodes. In this paper, we consider the problem to route a batch of data packets in DTN. By making an analogy between the routing protocol and low-density erasure codes, we investigate the information-theoretical optimal number of data transmissions in delivering data. With such insights, we propose E-NCP, an efficient protocol in DTNs based on network coding, that reduces data transmissions significantly, while increasing data transmission delay only slightly as compared to the protocol with the best performance. With extensive theoretical analysis and simulations, we show that network coding facilitates a better tradeoff between resource usage and protocol performance, and that our protocol offers unique advantages over replication-based protocols.

It is well known that the generalized max-weight matching (GMWM) scheduling policy, and in general throughput-optimal scheduling policies, often require the solution of a complex optimization problem, making their implementation prohibitively difficult in practice. This has motivated many researchers to develop distributed sub-optimal algorithms that approximate the GMWM policy. One major assumption commonly shared in this context is that the time required to find an appropriate schedule vector is negligible compared to the length of a timeslot. This assumption may not be accurate as the time to find schedule vectors usually increases polynomially with the network size. On the other hand, we intuitively expect that for many sub-optimal algorithms, the schedule vector found becomes a better estimate of the one returned by the GMWM policy as more time is given to the algorithm. We thus, in this paper, consider the problem of scheduling from a new perspective through which we carefully incorporate channel variations and time-efficiency of sub-optimal algorithms into the scheduler design. Specifically, we propose a dynamic control policy (DCP) that works on top of a given sub-optimal algorithm, and dynamically but in a large time-scale adjusts the time given to the algorithm according to queue backlog and channel correlations. This policy does not require the knowledge of the structure of the given sub-optimal algorithm, and with low-overhead can be implemented in a distributed manner. Using a novel Lyapunov analysis, we characterize the stability region induced by DCP, and show that our characterization can be tight. We also show that the stability region of DCP is at least as large as the one for any other static policy. Finally, we provide two case studies to gain further intuition into the performance of DCP.

The problem of communication among nodes in an extended network is considered, where radio power decay and interference are limiting factors. It has been shown previously that, with simple multi-hopping, the achievable total communication rate in such a network is at most Theta(radic(N)). In this work, we study the benefit of node cooperation in conjunction with multi-hopping on the network capacity. We propose a multi-phase communication scheme, combining distributed MIMO transmission with multi-hop forwarding among clusters of nodes. We derive the network throughput of this communication scheme and determine the optimal cluster size. This provides a constructive lower bound on the network capacity. We first show that in regular networks a rate of omega(N2/3) can be achieved with transmission power scaling of Theta(Nalpha/6-1/3), where alpha > 2 is the signal path-loss exponent. We further extend this result to random networks, where we show a rate of omega(N2/3(logN)2-alpha/6) can be achieved with transmission power scaling of Theta(Nalpha/6-1/3(logN)(alpha-2)2/6. In particular, as alpha approaches 2, only constant transmission power is required.

Epidemic routing has been proposed to reduce the data transmission delay in disruption tolerant wireless networks, in which data can be replicated along multiple opportunistic paths as different nodes move within each other's communication range. With the advent of network coding, it is intuitive that data can not only be replicated, but also coded, when the transmission opportunity arises. However, will opportunistic communication with network coding perform any better than simple replications? In this paper, we present a stochastic analytical framework to study the performance of epidemic routing using network coding in opportunistic networks, as compared to the use of replication. We analytically show that network coding is superior when bandwidth and node buffers are limited, reflecting more realistic scenarios. Our analytical study is able to provide further insights towards future designs of efficient data communication protocols using network coding. As an example, we propose a priority based coding protocol, with which the destination can decode a high priority subset of the data much earlier than it can decode any data without the use of priorities. The correctness of our analytical results has also been confirmed by our extensive simulations.

Recently wireless sensor networks featuring direct sink access have been studied as an efficient architecture to gather and process data for numerous applications. We focus on the joint effect of clustering and data correlation on the performance of such networks. We propose a novel cluster-based data collection scheme for sensor networks with direct sink access (CDC-DSA), and provide an analytical framework to evaluate its performance in terms of energy consumption, latency, and robustness. In our scheme, CHs use a low-overhead and simple medium access control (MAC) conceptually similar to ALOHA to contend for the reachback channel to the data sink. Since in our model data is collected periodically, the packet arrival is not modeled by a continuous random process and, therefore, our framework is based on transient analysis rather than a steady state analysis. Using random geometry tools, we study how the optimal average cluster size and energy savings vary in a response to various data correlation levels under the proposed MAC. Extensive simulations for various protocol parameters show that our analysis is fairly accurate for a wide range of parameters. Our results suggest that despite the tradeoff between energy consumption and latency, both of which can be substantially reduced by proper clustering design.

The future-generation wireless systems will combine heterogeneous wireless access technologies to provide mobile users with seamless access to a diverse set of applications and services. The heterogeneity in this inter-technology roaming paradigm magnifies the mobility impact on system performance and user perceived service quality, necessitating novel mobility modeling and analysis approaches for performance evaluation. In this paper, we present and compare three mobility models in two-tier integrated heterogeneous wireless systems, the independence model as a naive extension of the traditional cell residence time modeling techniques for homogeneous cellular networks, the basic Coxian model which takes into consideration the correlation between the residence time within different access technologies, and the extended-Coxian model for further improved estimation accuracy. We propose a general stochastic performance analysis framework based on application session models derived from these mobility models, applying it to a 3G-WLAN integrated system as an example. Our numerical and simulation results demonstrate the general superiority of Coxian-based mobility modeling over the independence model. Furthermore, using the proposed modeling and analysis methods, we investigate the impact of different parameters on system performance metrics such as network utilization time, handoff rates, and forced termination probability, for a wide range of user applications.

We study the optimal streaming of variable bit-rate (VBR) video over a random VBR channel. The goal of a streaming application is to enable the successful decoding of each video object before its displaying deadline is violated. Hence, we define the main performance metric of a streaming system as the probability of un-interrupted video presentation, or jitter-free probability. Previous literature has described solutions to estimate the jitter-free probability by assuming either independence in the encoded data process or simplistic channel models. In this work, we present a novel analytical framework, which requires only some basic statistical information of an arbitrary VBR channel, to bound the probability of jitter-free playout under the constraint of initial playout delay and receiver buffer size. Both the infinite and finite buffer cases are considered. This technique is then applied to investigate streaming over a wireless system modeled by an extended Gilbert channel with ARQ transmission control. Experimental results with MPEG-4 VBR encoded video demonstrates that the proposed analysis derives close bounds to the actual system performance. Finally, we show that the proposed analysis provides a theoretical foundation to quantify the tradeoffs between the initial playout delay, the receiver buffer size, and the jitter-free probability for a general class of VBR streaming over random VBR channels.

Using relays in wireless networks can potentially lead to significant capacity increases. However, within an asynchronous multi-user communication setting, relaying might cause more interference in the network, and significant sum-rate deterioration may be observed. In this work the effect of cooperation in an interference limited, narrow-band wireless network is investigated. It is crucial to determine the optimal trade-off between the amount of throughput gain obtained via cooperation and the amount of interference introduced to the network. We quantify the amount of cooperation using the notion of a cooperative region for each active node. The nodes which lie in such a region are allowed to cooperate with the source. We adopt the decode-and-forward scheme at the relays and use the physical interference model to determine the probability that a relay node correctly decodes its corresponding source. Through numerical analysis and simulation, we study the optimal cooperative region size to maximize the network sum-rate and energy efficiency, based on network size, relay availability, node decoding threshold, and destination reception capability. It is shown that optimized system performance in terms of the network sum-rate and the power efficiency is significantly improved compared with cases where relay nodes are not exploited or where the cooperative region size is suboptimal.

Prefetching has been shown to be an effective technique for reducing resource cost and delay in heterogeneous wireless networks. However, in modern wireless local area networks, there is little centralized management, with no control of upper-level functions such as prefetching, and so users are free to behave selfishly. This work focuses on how pricing can be used to control the suboptimality that results from prefetching and selfish users in heterogeneous wireless networks, and how the perceived cost for the user can be optimized. We derive an analytic model to characterize the optimal network and Nash equilibrium prefetching strategies. We present a pricing scheme that optimizes the best achievable perceived cost when the network is in a Nash equilibrium.

Both peer-to-peer and sensor networks have the fundamental characteristics of node churn and failures. Peers in P2P networks are highly dynamic, whereas sensors are not dependable. As such, maintaining the persistence of periodically measured data in a scalable fashion has become a critical challenge in such systems, without the use of centralized servers. To better cope with node dynamics and failures, we propose priority random linear codes, as well as their affiliated pre-distribution protocols, to maintain measurement data in different priorities, such that critical data have a higher opportunity to survive node failures than data of less importance. A salient feature of priority random linear codes is the ability to partially recover more important subsets of the original data with higher priorities, when it is not feasible to recover all of them due to node dynamics. We present extensive analytical and experimental results to show the effectiveness of priority random linear codes.

The main goal of a streaming application is to enable the successful decoding of each video object before its displaying deadline is violated, and to recover from a deadline violation properly. Hence, we define the main performance metric of a streaming system as the number of interruptions during a video presentation, or the number of jitters. Previous literature has described solutions to estimate the jitter-free probability for an entire video segment. In this work, we present a novel analytical framework, which requires only a Markov Variable Bit Rate (VBR) channel model, to study the frequency of jitters under the constraint of initial playback delay, receiver buffer size, and different jitter recovering schemes. Both the infinite and finite buffer cases are considered. This technique is then applied to investigate streaming over a wireless system modeled by an extended Gilbert channel with ARQ transmission control. Experimental results with MPEG-4 VBR encoded video validate our analysis. Finally, we show that the proposed analysis provides a theoretical foundation to quantify the tradeoffs between the jitter frequency, jitter recovering delay, initial delay, and the receiver buffer size for a general class of VBR streaming over random VBR channels with different jitter recovering schemes.

It may not be feasible for sensor networks monitoring nature and inaccessible geographical regions to include powered sinks with Internet connections. We consider the scenario where sinks are not present in large-scale sensor networks, and unreliable sensors have to collectively resort to storing sensed data over time on themselves. At a time of convenience, such cached data from a small subset of live sensors may be collected by a centralized (possibly mobile) collector. In this paper, we propose a decentralized algorithm using fountain codes to guarantee the persistence and reliability of cached data on unreliable sensors. With fountain codes, the collector is able to recover all data as long as a sufficient number of sensors are alive. We use random walks to disseminate data from a sensor to a random subset of sensors in the network. Our algorithms take advantage of the low decoding complexity of fountain codes, as well as the scalability of the dissemination process via random walks. We have proposed two algorithms based on random walks. Our theoretical analysis and simulation-based studies have shown that, the first algorithm maintains the same level of fault tolerance as the original centralized fountain code, while introducing lower overhead than naive random-walk based implementation in the dissemination process. Our second algorithm has lower level of fault tolerance than the original centralized fountain code, but consumes much lower dissemination cost.

Throughput optimal scheduling policies in general require the solution of a complex optimization problem. The past literature has shown that the complexity of this optimization problem can be greatly reduced, but at the expense of memory requirement that is exponential with the number of users. In this paper, we study the stability region of a class of linear-memory scheduling policies for time varying channels, and investigate how the channel memory impacts the supportable input rates. The set of scheduling policies in this paper covers a wide spectrum of resource allocation algorithms, which allows us to study policies with different complexity levels. In particular, we are able to model a class of low-complexity scheduling policies with linear memory, which are suitable for practical implementation.

In the near future, demand for Heterogeneous Wireless Networking (HWN) is expected to to increase. QoS provisioning in these networks is a challenging issue considering the diversity in wireless networking technologies and the existence of mobile users with different communication requirements. In HWNs with their increased complexity, "the curse of dimensionality" problem makes it impractical to directly apply the decision theoretic optimal control methods that are previously used in homogeneous wireless networks to achieve desired QoS levels. In this paper, optimal call admission control policies for HWNs are considered. A decision theoretic framework for the problem is derived by a dynamic programming formulation. We prove that for a two-tier wireless network architecture, the optimal policy has a two-dimensional threshold-based structure. Further, a novel algorithm called Structured Value Iteration is proposed as a numerically efficient method to determine the optimal policy in terms of its thresholds. Extensive simulation experiments are conducted. The numerical results show that the proposed algorithm is efficient in terms of its time-complexity and in achieving the optimal performance.

This paper addresses the problem of optimizing the packet transmission schedule in a multihop wireless network with end-to-end delay constraints. The emphasis is to determine the proper relative weights assigned to the remaining distance and the remaining lifetime in order to rank the urgency of a packet. We consider a general class of cross-layer transmission schemes that represent such relative weights using a single lifetime-distance factor, which includes, as special cases, schedules such as earliest-deadline-first and largest-distance-first. We propose an analytical framework, based on recursive non-homogeneous Markovian analysis, to study the effect of the lifetime-distance factor on packet loss probability in a general multihop environment, with different configurations of peer-node channel contention. Numerical results are presented to illustrate how various network parameters affect the optimal lifetime-distance factor. We demonstrate quantitatively how the proper balance between distance and lifetime in a transmission schedule can significantly improve the network performance, even under imperfect schedule implementation.

On-demand and live multimedia streaming applications (such as Internet TV) are well known to utilize a significant amount of bandwidth from media streaming servers, especially as the number of participating peers in the streaming session scales up. To scale to higher bit rates of media streams and larger numbers of participating peers, overlay tree or mesh topologies are typically constructed, such that peers utilize their available upload capacities to alleviate the excessive bandwidth demands on stream servers. Previous works rely on random selections of upstream peers, without optimizing the topologies towards maximized utilization of peer upload bandwidth, and as a result, minimized bandwidth costs on streaming servers. We propose Outreach, a distributed algorithm to construct overlay topologies among participating peers in streaming sessions. The design objective of Outreach is to optimize the quality of overlay topologies towards scalability, with respect to the number of participating peers in the session. To be scalable, Outreach seeks to maximize the utilization of available upload bandwidth on each participating peer, and consequently minimize the total bandwidth costs on streaming servers. With analysis, we show that Outreach constructs topologies such that peers can fully utilize their upload capacities, and present a practical distributed algorithm. With simulation-based comparison studies, we show that Outreach effectively achieves its goals in a high-churn peer-to-peer network with an assortment of peer uplink capacities and link delays.

Ad hoc networks offer infrastructure-free operation, where no entity can provide reliable coordination among nodes. Medium Access Control (MAC) protocols in such a network must overcome the inherent unreliability of the network and provide high throughput and adequate fairness to the different flows of traffic. In this paper, we propose a MAC protocol that can achieve an excellent balance between throughput and fairness. Our protocol has two versions: Randomly Ranked Mini Slots (RRMS) utilizes control-message handshakes similar to IEEE 802.11. Randomly Ranked Mini Slots with Busy Tone (RRMS-BT) is the better performer of the two, but requires a receiver busy tone. The protocol makes use of granule time slots and sequences of pseudorandom numbers to maximize spatial reuse and divide the throughput fairly among nodes. We demonstrate the performance of this protocol using simulation with fixed and random topologies and show that these results are robust to difficult network configurations and unsynchronized clocks. We further develop novel metrics of long-term and short-term fairness for rigorous performance evaluation. Our simulation results include a detailed comparison between the proposed protocol and existing protocols that have been shown to excel in terms of throughput or fairness.

With the proliferation of wireless local area network (WLAN) technologies, wireless Internet access via public hotspots will become a necessity in the near future. In outdoor areas where the installation of a large number of wired access points is practically or economically infeasible, mobile users located at the edge of the network communicate with the access point at a very low rate and, in turn, waste network resources. In this work, we promote the use of tetherless relay points (TRPs) to improve the throughput ot a WLAN in such environments. We first provide a high level description on how to integrate TRPs in a multirate WLAN architecture. We then propose an integer-programming optimization formulation and an iterative approach to compute the best placement of a fixed number of TRPs. Finally, we show in numerical analysis, through a case study based on relay-enabled rate adaptation and IEEE 802.11-like multirate physical model with Rayleigh fading, that, for a wide range of system parameters, significant performance gain can be achieved when TRPs are strategically installed in the network

In this paper, we propose an effective distributed algorithm to solve the minimum energy data gathering (MEDG) problem in wireless sensor networks. The problem objective is to find an optimal transmission structure on the network graph, such that the total energy consumed by the sensor nodes is minimized. We formulate the problem as a non-linear optimization problem. The formulation considers in-network data aggregation and respects the capacity of the wireless shared-medium. We apply Lagrangian dualization technique on this formulation to obtain a subgradient algorithm for computing the optimal transmission structure. The subgradient algorithm is asynchronous and amenable to fully distributed implementations, which corresponds to the decentralized nature of sensor networks.

Next-generation wireless networking is evolving towards a multi-service heterogeneous paradigm that converges different pervasive access technologies and provides a large set of novel revenue generating applications. Hence, system complexity increases due to its embedded heterogeneity, which can not be accounted by the existing modeling and performance evaluation techniques. Consequently, the development of new modeling approaches becomes as a crucial requirement for proper system design and performance evaluation. This paper presents a novel mobility model for a two-tier integrated wireless system using a new modeling approach that accommodates the aforementioned complexity. Additionally, a novel session model is developed as an adapted version of the proposed mobility model. These models use phase-type distributions that are known to approximate any generic probability laws. Using the proposed session model, a novel generic analytical framework is developed to obtain several salient performance metrics such as network utilization times and handoff rates. Simulation and analysis results prove the proposed model validity and demonstrate the accuracy of the novel modeling approach when compared with traditional modeling techniques.

It is well-known that live multimedia streaming applications operate more efficiently when organized in peer-to-peer (P2P) topologies, since peer upload capacities are utilized to support other peers, and to alleviate the load and operating costs on the streaming servers. To date, there have been a number of existing experimental proposals with respect to how such peer-to-peer topologies are organized to support live streaming sessions. However, most of the existing proposals resort to intuition and heuristics when it comes to the design of such topology construction (i.e., neighbor selection) protocols. In this paper, we investigate the scaling laws of live P2P multimedia streaming, by quantitatively studying the asymptotic effects and tradeoffs among three key parameters in P2P streaming: server bandwidth cost, the maximum number of peers that can be supported, and the maximum number of streaming hops experienced by a peer. To further generalize our studies, we do not make restrictive assumptions in our theoretical analysis of such scaling laws: both peer upload capacities and peer lifetimes in a session may come from arbitrary distributions. With the theoretical insights we have developed, we propose Affinity, a simple and realistic heuristic to demonstrate the key benefits of our theoretical analysis in dynamic P2P networks, as compared to the topology construction algorithms in existing work.

This paper addresses the problem of optimizing the packet transmission schedule in an ad hoc network with end-to-end delay constraints. The emphasis is to determine the proper relative weights assigned to the remaining distance and the remaining lifetime in order to rank the urgency of a packet. We consider a general class of transmission schemes that represent such relative weights using a single lifetime-distance factor, which includes, as special cases, schedules such as Earliest-Deadline-First and Largest-Distance-First. We propose an analytical framework, based on recursive non-homogeneous Markovian analysis, to study the effect of the lifetime-distance factor on packet loss probability in a general multihop environment, with different configurations of peer-node channel contention. Numerical results are presented to demonstrate how various network parameters affect the optimal lifetime-distance factor. We demonstrate quantitatively how the proper balance between distance and lifetime in a transmission schedule can significantly improve the network performance, even under imperfect schedule implementation.

We study the performance of a multi-user prefetching strategy in a two-tier heterogeneous wireless network. A predictive framework was previously introduced for mobility-aware document prefetching to enhance the experience of a mobile user roaming between heterogeneous wireless access networks. However, an undesirable effect of multiple prefetching users is the potential for system instability due to the racing behavior between document access delay and user prefetch quantity. This phenomenon is particularly acute in the heterogeneous environment. We propose to alleviate the system traffic load through optimizing a prefetch thresholding algorithm, accounting for server queuing prioritization. We evaluate the performance of the proposed algorithm through numerical analysis and simulation. We show that stability can be maintained even under heavy usage, providing both the same scalability as a non-prefetching system and the performance gains associated with prefetching.

In this paper, we study the optimal streaming of variable bit-rate (VBR) videos over random VBR channels. We define the main performance metric of a streaming system as the probability of un-interrupted video presentation, or jitter-free probability. Previous literature has described solutions to estimate the jitter-free probability by assuming either independence in the encoded data process or simplistic channel models. In this work, we present an novel analytical framework, which requires only the maximum channel bit rate and some statistical information of an arbitrary VBR channel, to bound the probability of jitter-free playback under the constraint of initial playback delay and receiver buffer size. Both the infinite and finite buffer cases are considered. This technique is then applied to investigate streaming over a wireless system modelled by an extended Gilbert channel with ARQ transmission control. Experimental results with MPEG-4 VBR encoded videos show that the proposed analysis provides close bounds to the actual system performance. Finally, we show that the proposed analysis provides a theoretical foundation to quantify the tradeoff between initial playback delay, receiver buffer size, and the jitter free probability for a general class of VBR video streaming over random VBR channels.

Fixed Broadband Wireless Access (FBWA) technology is designed to serve as a wireless DSL replacement technology to provide broadband access in underserved areas where no other access technology exists. Due to the enormousness of the target service area, relay equipment play an important role in such networks, and the installation and maintenance cost of the network is directly proportional to the cost of the relay equipment. To minimize the network operational cost, we develop an optimization framework which computes the minimum number of relay stations and their placement in the network such that the demands from the end users are met.

We study the effect of cooperation in an interference limited, narrow-band wireless sensor network. Cooperation among available sensors can potentially lead to significant capacity increases. However, in an interference limited setting with asynchronous transmissions, exploiting more available sensors to help active sources will cause more interference to other sensors. Therefore, it is crucial to find the optimal trade-off between the amount of cooperation and the amount of interference introduced to the network. In this work we quantify the amount of cooperation using the notion of relay zones for each active sensor. The sensors that lie in such a zone are allowed to cooperate with the source. We then use the physical interference model to determine the probability that a relay node correctly decodes its corresponding source. Through numerical and simulation studies, we investigate the optimization of the relay-zone radius to maximize the network sum-rate based on relay availability and the sink reception capability. We show that the overall system capacity increases significantly under the proposed scheme, compared with cases where relay nodes are not exploited or where the relay zone radius is suboptimal

Virtual backbone routing (VBR) is a scalable hybrid routing framework for ad hoc networks, which combines local proactive and global reactive routing components over a variable-sized zone hierarchy. The zone hierarchy is maintained through a novel distributed virtual backbone maintenance scheme, termed the distributed database coverage heuristic (DDCH), also presented in this paper. Borrowing from the design philosophy of the zone routing protocol, VBR limits the proactive link information exchange to the local routing zones only. Furthermore, the reactive component of VBR restricts the route queries to within the virtual backbone only, thus improving the overall routing efficiency. Our numerical results suggest that the cost of the hybrid VBR scheme can be a small fraction of that of either one of the purely proactive or purely reactive protocols, with or without route caching. Since the data routes do not necessarily pass through the virtual backbone nodes, traffic congestion is considerably reduced. Yet, the average length of the VBR routes tends to be close to optimal. Compared with the traditional one-hop hierarchical protocols, our results indicate that, for a network of moderate to large size, VBR with an optimal zone radius larger than one can significantly reduce the routing traffic. Furthermore, we demonstrate VBR's improved scalability through analysis and simulations

The throughput capacity of a wireless local area network (WLAN) can be improved synergically by 1) the multi-rate capability of modern WLAN equipments and 2) the spatial diversity provided by its relay infrastructure. In this work, we investigate the effect of multi-path fading and opportunistic utilization of a fixed number of immobile relay nodes on the throughput capacity of a rate adaptive WLAN. We develop an analytical framework that computes the throughput capacity of an IEEE 802.11 WLAN with relay infrastructure in the Rayleigh fading environment. We compare the performance of MAC-layer and network-layer relaying. Our results show that up to 200% performance gain can be achieved by an optimal relay infrastructure over a network with no relay. Furthermore, for a wide range of system parameters, optimally placed relay nodes can significantly increase the network throughput capacity

This paper addresses the problem of optimizing packet transmission schedule at the medium access control layer of an ad hoc network, in order to minimize the probability of packet loss due to excessive end-to-end delay. We study a family of multihop latency aware (MLA) schedules, where the scheduling of each packet takes into account its remaining hop count and remaining lifetime. We propose a numerical analysis framework to evaluate the performance of MLA scheduling. Using the proposed analysis framework, we study the optimization of MLA parameters to minimize packet loss probability. We show that the MLA scheme significantly out performs other scheduling schemes such as first-in-first-out, earliest-deadline-first, and largest-distance-first.

The next generation (4G) wireless network is envisioned as a convergence of different wireless access technologies providing the user with the best anywhere anytime connection and improving the system resource utilization. The integration of wireless local area network (WLAN) hotspots and the third generation (3G) cellular network has recently received much attention. While the 3G-network can provide global coverage with a low data-rate service, the WLAN can provide a high data-rate service within the hotspots. Although increasing the underlay network utilization is expected to increase the user available bandwidth, it may violate the quality-of-service (QoS) requirements of active real-time applications. Hence, achieving seamless handoff between different wireless technologies, known as vertical handoff (VHO), is a major challenge for 4G-system implementation. Several factors, such as application QoS requirements and handoff delay, should be considered to realize an application transparent handoff. We present a novel framework to evaluate the impact of VHO algorithm design on system resource utilization and user perceived QoS. We used this framework to compare the performance of two different VHO algorithms. The results show a very good match between simulation and analytical results. In addition, it clarifies the tradeoff between achieving high resource utilization and satisfying user QoS expectations.

This paper presents a novel mobility modeling approach for a two-tier integrated wireless system that accommodates the system complexity represented by the residence-time correlation between different access networks. Additionally, a novel session model is presented as an adapted version of the proposed mobility model. Furthermore, we develop an analytical framework using this session model to obtain several salient performance metrics such as network utilization times and handoff rates. Simulation results demonstrate that the proposed mobility model is substantially more accurate than existing modeling techniques, and that the proposed analytical framework provide tractable performance evaluation based on the new mobility model.

Wireless extension points (EPs) are immobile devices that relay data between the access point and the mobile users in a heterogeneous wireless local area network (WLAN). In this paper, we investigate the optimal placement of EPs such that the throughput capacity of a rectilineal WLAN is maximized. Two channel models are studied, based on the Shannon capacity bound and IEEE 802.11 specifications. We propose an efficient EP placement algorithm that determines the optimal locations of a fixed number of EPs. Our results show that, for a wide range of system parameters, the optimally placed EPs can significantly increase the network throughput capacity. Moreover, we study how the number of EPs, transmission power, path loss exponent, channel models and traffic characteristics affect the optimal EP placement and expected throughput capacity of the network

Wireless sensor networks with mobile access points are effective tools for collecting data in a variety of environments. Mobile agents are powerful hardware units with sophisticated transceivers. Low-cost and low-power sensors in the reachback operation contend for the channel to transmit their own data packets to the mobile agent. This data communication should be designed to ensure energy efficiency and low latency. We propose a clustering scheme for wireless sensor networks with reachback mobile agents (C-SENMA). C-SENMA groups sensors into clusters such that nodes communicate only with the nearest clusterhead (CH) and the CH takes the task of data aggregation and communication with the mobile agent. CHs use a low-overhead medium access control (MAC) mechanism, similar to the conventional ALOHA, to contend for the channel. Using results from random geometry theory, we analyze the clustering performance under the realistic MAC algorithm. Our analysis enables us to obtain the optimal average cluster size which minimizes energy consumption. We justify our analysis results by extensive simulations according to various clustering parameters. Furthermore, we study the effect of underlying physical layer characteristics on the amount of energy reduction achievable by the proposed clustering architecture.

Wireless relay nodes can improve the capacity of wireless networks. In this work, we integrate wireless relay nodes into the infrastructure of a wireless local area network (WLAN). In particular, we investigate the effect of different relay strategies and optimal utilization of a fixed number of immobile relay nodes, which maximizes the expected throughput capacity of the network. We study how the number of relay nodes, the range of users, transmission power, path loss exponent, and traffic characteristics affect the optimal relay node placement and expected throughput capacity of the network. Our results show that a time-division relay strategy can far outperform a receive-and-retransmit relay strategy. Furthermore, for a wide range of system parameters, optimally placed relay nodes can significantly increase the network expected throughput capacity.

We investigate the effects of the carrier sensing range of the IEEE 802.11 multiple access control (MAC) scheme in this paper. Contrary to the simple and inaccurate cut-off circular collision model that is commonly used, we employ a more accurate collision model to realistically simulate MAC schemes in ad hoc networks. We argue that the carrier sensing range is a tunable parameter that can significantly affect the MAC performance in multihop ad hoc networks. An optimal carrier sensing range should balance the trade-off between the amount of spatial frequency reuse and the possibility of packet collisions. A reward formulation for the optimization of the carrier sensing range is presented. Extensive simulation results are provided to substantiate our study.

This paper presents a predictive framework for mobility-aware prefetching to enhance the experience of a mobile Web user roaming between heterogeneous wireless access networks. We consider a heterogeneous two-tier wireless access network system, composed of smaller, but faster and cheaper wireless local area networks (WLAN) placed within a much larger, but slower and more expensive cellular wireless data network. An optimal prefetch threshold algorithm is proposed, which takes into consideration the user mobility pattern, the relative characteristics of the networks, and the user perceived value of time. Using current industry network parameters, we study the performance of the proposed prefetching algorithm. Our numerical results show how user mobility and the heterogeneous network configuration significantly alter the prefetching threshold. The performance of this algorithm is compared with that of a static prefetching algorithm, demonstrating that mobility-aware prefetching can significantly improve the performance of future-generation heterogeneous wireless networks.

In wireless sensor networks, clustering allows the aggregation of sensor data. It is well known that leveraging the correlation between different samples of the observed data will lead to better utilization of energy reserve. However, no previous work has analyzed the effect of non-ideal data aggregation in multi-hop sensor networks. In this paper, we propose a novel analytical framework to study how partially correlated data affect the performance of clustering algorithms. We analyze the behavior of multi-hop routing and, by combining random geometry techniques and rate distortion theory, predict the total energy consumption and network lifetime. We show that when a moderate amount of correlation is available, the optimal probabilities that lead to minimum energy consumption are far from optimality in terms of network lifetime. In addition, we study the sensitivity of the total energy consumption and network lifetime to the amount of correlation and compression distortion constraint.

In this paper, the performance of a distributed mobility management scheme, the Randomized Database Group (RDG), for mobile ad hoc networks is presented. In this scheme, databases are used to store the location of the network nodes and to manage the mobility of nodes. When a mobile's location changes, a number of randomly selected databases are updated. When a mobile's location is needed, such as upon a call arrival, a number of randomly selected databases are queried. A number of different RDG query schemes are studied and their performance are compared. In particular, the optimum update-group size and the query-group size are found. We also present the probability of the first query being successful and the average query delay to find the mobile's location. Finally, we estimate the cost of implementing the RDG scheme as a function of different number of databases.

On-demand routing reduces the control overhead in mobile ad hoc networks, but it has the major drawback of introducing latency between route-request arrival and the determination of a valid route. This paper addresses the issue of minimizing the delay in on-demand routing protocols through optimizing the Time-to-Live (TTL) interval for route caching. An analytical framework is introduced to compute the expected routing delay when a source node or an intermediate node has a cached route with any given TTL value. Furthermore, numerical methods are proposed to determine the optimal TTL of a newly cached route. We present simulation results that support the validity of our analysis. Using the proposed analytical framework, we study how the routing delay is affected by route length, route-request frequency, and the frequency of topology variation. We show that the proposed optimal route-cache TTL strategy can significantly reduce the routing delay over systems that either does not use route-cache or keeps route-cache indefinitely long. We further show that the performance gain of optimizing the route-cache TTL increases with increasing traffic pattern localization.

This paper presents a mobile tracking scheme that exploits the predictability of user mobility patterns in wireless PCS networks. In this scheme, a mobile's future location is predicted by the network, based on the information gathered from the mobile's recent report of location and velocity. When a call is made, the network pages the destination mobile around the predicted location. A mobile makes the same location prediction as the network does; it inspects its own location periodically and reports the new location when the distance between the predicted and the actual locations exceeds a threshold. To more realistically represent the various degrees of velocity correlation in time, a Gauss-Markov mobility model is used. For practical systems where the mobility pattern varies over time, we propose a dynamic Gauss-Markov parameter estimator that provides the mobility parameters to the prediction algorithm. Based on the Gauss-Markov model, we describe an analytical framework to evaluate the cost of mobility management for the proposed scheme. We also present an approximation method that reduces the computational complexity of the cost evaluation for multidimensional systems. We then compare the cost of predictive mobility management against that of the regular, nonpredictive distance-based scheme, for both the case with ideal Gauss-Markov mobility pattern and the case with time-varying mobility pattern.

In ad hoc networks, each node utilizes its limited resources to carry out the collective operation of the network. It is not always in the best interests of the network's nodes to demand the continuous participation of all nodes in the network operations. We propose an energy dependent participation (EDP) scheme, where a node periodically re-evaluates its participation in the network based on the residual energy in its battery. More importantly, a node gives special consideration to supporting the communication needs of its active network applications and preventing further network partitioning. EDP's localized partition checking algorithm is particularly well suited for the zone routing protocol, where the link-state information is proactively maintained within each node's local zone and routes to faraway nodes are reactively obtained via global queries. Through simulations, we evaluate the impact of our proposed scheme on battery life and network connectivity. Our results suggest that the EDP scheme can increase the usable lifetime of a battery-constraint ad hoc network by over 50%.

In this paper, we present the implementation issues of a virtual backbone that supports the operations of the uniform quorum system (UQS) and the randomized database group (RDG) mobility management schemes in an ad hoc network. The virtual backbone comprises nodes that are dynamically selected to contain databases that store the location information of the network nodes. Together with the UQS and RDG schemes, the virtual backbone allows both dynamic database residence and dynamic database access, which provide high degree of location data availability and reliability. We introduce a distributed database coverage heuristic (DDCH), which is equivalent to the centralized greedy algorithm for virtual backbone generation, but only requires local information exchange and local computation. We show how DDCH can be employed to dynamically maintain the structure of the virtual backbone, along with database merging, as the network topology changes. We also provide a means to maintain connectivity among the virtual backbone nodes. We discuss optimization issues of DDCH through simulations. Simulation results suggest that the cost of ad hoc mobility management with a virtual backbone can be far below that of the conventional link-state routing.

A distributed mobility management scheme using randomized database groups (RDG) is proposed and analyzed for ad-hoc networks. In the proposed scheme, location databases are stored in the network nodes, comprising a virtual backbone within the flat network architecture. Upon location update or call arrival, a mobile's location information is written to or read from, respectively, a group of randomly chosen databases. Compared with a centralized scheme (such as the home location register) with fixed associations, this scheme is more suitable for ad-hoc networks, where the connectivity of the nodes with the rest of the network can be intermittent and sporadic, and the databases are relatively unstable. The expected cost due to call loss and location updates using this scheme is analyzed in the presence of database disconnections. Based on the expected cost, we present the numerical determination and approximation of the optimal total location database number, the optimal database access group size, and the optimal location update frequency, under different network stability, traffic, and mobility conditions. Numerical results show that the RDG scheme provides an robust and efficient approach to ad-hoc mobility management.

This paper presents a mobile tracking scheme that exploits the predictability of user mobility patterns in wireless PCS networks. Instead of the constant velocity fluid-flow or the random-walk mobility model, a more realistic Gauss-Markov model is introduced, where a mobile's velocity is correlated in time to a various degree. Based on the Gauss-Markov model, a mobile's future location is predicted by the network based on the information gathered from the mobile's last report of location and velocity. When a call is made, the network pages the destination mobile at and around the predicted location of the mobile and in the order of descending probability until the mobile is found. A mobile shares the same prediction information with the network and reports its new location whenever it reaches some threshold distance away from the predicted location. We describe an analytical framework to evaluate the cost of mobility management for the proposed predictive distance-based scheme. We then compare this cost against that of the regular, non-predictive distance-based scheme, which is obtained through simulations. Performance advantage of the proposed scheme is demonstrated under various mobility and call patterns, update cost, page cost, and frequencies of mobile location inspections.

In this correspondence, a new viewpoint is proposed for estimating an image from its distorted versions in presence of noise without the a priori knowledge of the distortion functions. In z-domain, the desired image can be regarded as the greatest common polynomial divisor among the distorted versions. With the assumption that the distortion filters are finite impulse response (FIR) and relatively coprime, in the absence of noise, this becomes a problem of taking the greatest common divisor (GCD) of two or more two-dimensional (2-D) polynomials. Exact GCD is not desirable because even extremely small variations due to quantization error or additive noise can destroy the integrity of the polynomial system and lead to a trivial solution. Our approach to this blind deconvolution approximation problem introduces a new robust interpolative 2-D GCD method based on a one-dimensional (1-D) Sylvester-type GCD algorithm. Experimental results with both synthetically blurred images and real motion-blurred pictures show that it is computationally efficient and moderately noise robust.

A distributed mobility management scheme using a class of uniform quorum systems (UQS) is proposed for ad hoc networks. In the proposed scheme, location databases are stored in the network nodes themselves, which form a self-organizing virtual backbone within the flat network structure. The databases are dynamically organized into quorums, every two of which intersect at a constant number of databases. Upon location update or call arrival, a mobile's location information is written to or read from all the databases of a quorum, chosen in a nondeterministic manner. Compared with a conventional scheme [such as the use of home location register (HLR)] with fixed associations, this scheme is more suitable for ad hoc networks, where the connectivity of the nodes with the rest of the network can be intermittent and sporadic and the databases are relatively unstable. We introduce UQS, where the size of the quorum intersection is a design parameter that can be tuned to adapt to the traffic and mobility patterns of the network nodes. We propose the construction of UQS through the balanced incomplete block designs. The average cost, due to call loss and location updates using such systems, is analyzed in the presence of database disconnections. Based on the average cost, we investigate the tradeoff between the system reliability and the cost of location updates in the UQS scheme. The problem of optimizing the quorum size under different network traffic and mobility patterns is treated numerically. A dynamic and distributed HLR scheme, as a limiting case of the UQS, is also analyzed and shown to be suboptimal in general. It is also shown that partitioning of the network is sometimes necessary to reduce the cost of mobility management.

We examine the applicability of the previously proposed greatest common divisor (GCD) method to blind image deconvolution. In this method, the desired image is approximated as the GCD of the two-dimensional polynomials corresponding to the z-transforms of two or more distorted and noisy versions of the same scene, assuming that the distortion filters are FIR and relatively co-prime. We justify the breakdown of two-dimensional GCD into one-dimensional Sylvester-type GCD algorithms, which lowers the computational complexity while maintaining the noise robustness. A way of determining the support size of the true image is also described. We also provide a solution to deblurring using the GCD method when only one blurred image is available. Experimental results are shown using both synthetically blurred images and real motion-blurred pictures.