Satellite edge computing has emerged as a promising paradigm to support global-scale low-latency services by enabling remote code execution in orbit. However, unlike terrestrial networks, satellite communication is fundamentally vulnerable to eavesdropping due to its wide broadcast range, high accessibility, and long-distance propagation, which is further exacerbated by the high altitudes allowing a vast set of potential eavesdropper positions. Despite these unique risks, most prior works have either ignored security or treated it as a uniform concern across services. In this paper, we take an initial step toward secure satellite edge computing by explicitly modeling and optimizing for security heterogeneity, i.e., diverse security demands across different services and dynamic jamming strategies. We formulate a novel optimization problem that jointly minimizes average information leakage for security-sensitive services and overall energy consumption while meeting latency constraints. To solve it, we propose a stochastic optimization-based algorithm, namelySOS, which dynamically controls code offloading, resource allocation, and jamming strategy with respect to service-specific security requirements. Extensive simulations show thatSOSoutperforms existing schemes by achieving up to a 92% reduction in average information leakage with only an 18% increase in energy consumption at the same latency compared to an existing algorithm. Moreover,SOSmaintains high jamming efficiency and leakage robustness under both colluding and non-colluding attacks. Our findings highlight a fundamental yet overlooked security-energy-latency trade-off and positionSOSas a pioneering step toward security-aware satellite edge computing.

Centralized Training and Decentralized Execution (CTDE) is a widely adopted paradigm to solve cooperative multi-agent reinforcement learning (MARL) problems. Despite the successes achieved with CTDE, partial observability still limits cooperation among agents. While previous studies have attempted to overcome this challenge through communication, direct information exchanges could be restricted and introduce additional constraints. Alternatively, if an agent can infer the global information solely from local observations, it can obtain a global view without the need for communication. To this end, we propose the Multi-Agent Masked Auto-Encoder (MA$^2$E), which utilizes the masked auto-encoder architecture to infer the information of other agents from partial observations. By employing masking to learn to reconstruct global information, MA$^2$E serves as an inference module for individual agents within the CTDE framework. MA$^2$E can be easily integrated into existing MARL algorithms and has been experimentally proven to be effective across a wide range of environments and algorithms.

Transfer learning is a cornerstone of modern deep learning, yet it remains constrained by challenges in model selection and the overhead of extensive model storage. In this work, we present Diffusion-based Neural Network Weights Generation, D2NWG, a novel framework that leverages diffusion processes to synthesize task-specific network weights. By modeling the distribution of weights from a diverse ensemble of pretrained models and conditioning the generation process on dataset characteristics, task descriptions, and architectural specifications, D2NWG circumvents the need for storing and searching through massive model repositories. We evaluate D2NWG across multiple experimental settings. On in-distribution tasks, our framework achieves performance that is on par with or superior to conventional pretrained models, while also serving as an effective initialization strategy for novel domains, resulting in faster convergence and a 6\% improvement in few-shot learning scenarios. Extensive ablation studies further indicate that our approach scales robustly with increased diversity and volume of pretrained models. Moreover, D2NWG demonstrates significant promise for large language model applications. In evaluations on the OpenLM leaderboard, our method improved LLaMA-3-2-1B-Instruct performance by 3\% on challenging mathematical reasoning tasks, with a consistent gain of 0.36\% across a range of benchmarks. These findings establish D2NWG as a versatile and powerful framework for neural network weight generation, offering a scalable solution to the limitations of traditional transfer learning.

In cellular networks, edge intelligence is often enabled by MultiAccess Edge Computing (MEC), which aims to bring AI services closer to end users. Although MEC reduces latency by placing computation near the network edge, it remains external to the Radio Access Network (RAN) and its native execution environment, thereby introducing additional transport and buffering delays. The emerging AI-on-RAN paradigm proposes to overcome these limitations but remains largely conceptual, lacking practical implementation and feasibility validation. In this paper, we present AoRA, the first framework realizing the AI-on-RAN vision by dynamically utilizing available computational headroom in GPU- and NPU-accelerated RAN platforms to deliver AI services directly from within the base stations. AoRA leverages containerized AI workloads in the 5G RAN stack to enable inlined and opportunistic AI service provisioning without degrading core telecom operations. The framework is fully compliant with O-RAN interfaces and can operate seamlessly alongside existing edge computing infrastructures. Evaluations show that AoRA reduces transport latency by over 30% compared to MEC and 70% compared to cloud-based setups.

On-device deep neural network (DNN) inference is often desirable for user experience and privacy. Existing solutions have fully utilized resources to minimize inference latency. However, they result in severe energy inefficiency by completing DNN inference much earlier than the required service interval. It poses a new challenge of how to make DNN inferences in a punctual and energy-efficient manner. To tackle this challenge, we propose a new resource allocation strategy for DNN processing, namelypunctual lazinessthat disperses its workload as efficiently as possible over time within its strict delay constraint. This strategy is particularly beneficial for neural workloads since a DNN comprises a set of popular operators whose latency and energy consumption are predictable. Through this understanding, we propose NeuroBalancer, an operator-aware core and memory frequency scaling framework that balances those frequencies as efficiently as possible while making timely inferences. We implement and evaluate NeuroBalancer on off-the-shelf Android devices with various state-of-the-art DNN models. Our results show that NeuroBalancer successfully meets a given inference latency requirements while saving energy consumption up to 43.9% and 21.1% compared to the Android's default governor and up to 42.1% and 18.6% compared to SysScale, the state-of-the-art mobile governor on CPU and GPU, respectively.

We present Preference Flow Matching (PFM), a new framework for preference alignment that streamlines the integration of preferences into an arbitrary class of pre-trained models. Existing alignment methods require fine-tuning pre-trained models, which presents challenges such as scalability, inefficiency, and the need for model modifications, especially with black-box APIs like GPT-4. In contrast, PFM utilizes flow matching techniques to directly learn from preference data, thereby reducing the dependency on extensive fine-tuning of pre-trained models. By leveraging flow-based models, PFM transforms less preferred data into preferred outcomes, and effectively aligns model outputs with human preferences without relying on explicit or implicit reward function estimation, thus avoiding common issues like overfitting in reward models. We provide theoretical insights that support our method’s alignment with standard preference alignment objectives. Experimental results indicate the practical effectiveness of our method, offering a new direction in aligning a pre-trained model to preference. Our code is available at https://github.com/jadehaus/preference-flow-matching.

With the rapid advances of deep learning and the commercialization of high-definition cameras in mobile and embedded devices, the demands from latency-critical applications such as AR and XR for high-quality video analytics (HVA) are soaring. By the nature of HVA aiming at enabling detailed analytics even for small objects, its on-device implementation is suffering from thermal and battery issues, which makes offloaded HVA an attractive solution. This work provides unique observations on the tradeoff pertaining to offloaded HVA: the frame encoding time, the frame transmission time, and the HVA accuracy. Our observations pose a fundamental question: given a latency budget, how to choose the encoding option that properly combines between the encoding time and the transmission time to maximize the HVA accuracy. To answer this question, we propose an offloaded HVA system, ENTRO, which exploits this tradeoff in real-time to maximize the HVA accuracy under the latency budget. Our extensive evaluations with ENTRO implemented on Nvidia AGX Xavier and Samsung Galaxy S20 Ultra over WiFi networks show 8.8× improvement in latency without accuracy loss compared to DDS, the state-of-the-art offloaded video analytics. Our evaluation over commercial 5G and LTE networks also indicates that ENTRO flexibly adapts its encoding option under the tradeoff and enables the latency-bounded HVA with 4K frames.

Computational resources are increasingly virtualized to enable computational tasks to be offloaded to remote facilities along the route between the source and destination. The principle that underlies traditional routing, i.e., that only networking resources need to be considered, may no longer be true in a virtualized environment. In this paper, we propose a framework for the efficient utilization of multi-resource infrastructures in which computational resources can be used via the network. Such a framework intrinsically calls for the joint consideration of networking and computational resources. In particular, we focus on unifying the controls in dynamic service chaining and multiple resource management, which are the key technologies in an integrated SDN/NFV architecture. We formulate a multi-path problem for choosing the resources to use in different services. The problem can be viewed as variational inequality using the Lagrange duality and saddle point theory. Based on this, we develop an extragradient-based algorithm that controls and splits the sending rate of each service. We prove that the algorithm converges to the optimal, minimizing the system cost while maximizing service utility. Simulations for diverse scenarios demonstrate that our algorithm achieves high QoS while reducing the system cost by jointly considering dual-resource coupling and service characteristics.

The demand for video conferencing applications has seen explosive growth while users still often face unsatisfactory quality of experience (QoE). Video conferencing applications adopt Forward Error Correction (FEC) as a recovery mechanism to meet tight latency requirements and overcome packet losses prevalent in the network. However, many studies mainly focused on video rate control by neglecting the complex interactions of this video recovery mechanism on the rate control and its impact on the user QoE. Deciding the right amount of FEC for the current video rate under a dynamically changing network environment is not straightforward. For instance, the higher FEC may enhance the tolerance to packet losses, but it may increase latency due to FEC processing overhead and hurt the video quality due to the additional bandwidth used for FEC. To address this issue, we propose R-FEC which is a reinforcement learning (RL) based framework for video and FEC bitrate decisions in video conferencing. R-FEC aims to improve overall QoE by automatically learning through the results of past decisions and adjusting video and FEC bitrates to maximize the user QoE while minimizing the congestion in the network. Our experiments show that R-FEC outperforms the state-of-the-art solutions in video conferencing, with up to 27% improvement in its video rate and 6dB PSNR improvement in video quality over the default WebRTC.

Massive Multi-Input Multi-Output (MIMO) and Coordinated MultiPoint (CoMP) technologies in Cloud-RAN (C-RAN) architecture become inevitable trend due to the advent of next-generation mobile applications, which are traffic-intensive, such as ultra high definition (UHD) video. In this paper, we study a joint beam activation and user scheduling problem in a 5G cellular network with massive MIMO and CoMP utilizing orthogonal random beamforming technique. This paper aims to minimize total Remote Radio Heads’ (RRHs’) energy expenditure in a dynamic C-RAN architecture while ensuring finite service time for all user traffic arrivals in the communication coverage. We leverage Lyapunov drift-plus-penalty framework to transform an original long-term average problem into a series of per-slot modified problems. Since the provided per-slot problem is combinatorial and nonlinear optimization problem, we are inspired by a greedy algorithm to design energy and delay guaranteed joint beam activation and user scheduling policy, namelyBEANS. We prove that the proposedBEANSensures finite upper bounds of average RRH energy consumption and average queue backlogs for all traffic arrival rates within constant ratio of capacity region and all energy-delay tradeoff parameters. These proofs are the first attempt to theoretically demonstrate guarantees of energy and queue bounds in a framework consisting of possiblynegative submodular objective functionandnon-matriod constraints. Finally, via extensive simulations, we compare the capacity region and energy-queue backlog tradeoff ofBEANSwith optimal and existing algorithms, and show thatBEANSattains up to 65% of energy saving for the same average queue backlog compared to the algorithms which do not take traffic dynamics and energy consumption into considerations.

DVFS (dynamic voltage and frequency scaling) is a system-level technique that adjusts voltage and frequency levels of CPU/GPU at runtime to balance energy efficiency and high performance. DVFS has been studied for many years, but it is considered still challenging to realize a DVFS that performs ideally for mobile devices for two main reasons: i) an optimal power budget distribution between CPU and GPU in a power-constrained platform can only be defined by the application performance, but conventional DVFS implementations are mostly application-agnostic; ii) mobile platforms experience dynamic thermal environments for many reasons such as mobility and holding methods, but conventional implementations are not adaptive enough to such environmental changes. In this work, we propose a deep reinforcement learning-based frequency scaling technique, zTT. zTT learns thermal environmental characteristics and jointly scales CPU and GPU frequencies to maximize the application performance in an energy-efficient manner while achieving zero thermal throttling. Our evaluations for zTT implemented on Google Pixel 3a and NVIDIA JETSON TX2 platform with various applications show that zTT can adapt quickly to changing thermal environments, consistently resulting in high application performance with energy efficiency. In a high-temperature environment where a rendering application with the default mobile DVFS fails to keep producing more than a target frame rate, zTT successfully manages to do so even with 23.9% less average power consumption.

For deployment, neural architecture search should be hardware-aware, in order to satisfy the device-specific constraints (e.g., memory usage, latency and energy consumption) and enhance the model efficiency. Existing methods on hardware-aware NAS collect a large number of samples (e.g., accuracy and latency) from a target device, either builds a lookup table or a latency estimator. However, such approach is impractical in real-world scenarios as there exist numerous devices with different hardware specifications, and collecting samples from such a large number of devices will require prohibitive computational and monetary cost. To overcome such limitations, we propose Hardware-adaptive Efficient Latency Predictor (HELP), which formulates the device-specific latency estimation problem as a meta-learning problem, such that we can estimate the latency of a model's performance for a given task on an unseen device with a few samples. To this end, we introduce novel hardware embeddings to embed any devices considering them as black-box functions that output latencies, and meta-learn the hardware-adaptive latency predictor in a device-dependent manner, using the hardware embeddings. We validate the proposed HELP for its latency estimation performance on unseen platforms, on which it achieves high estimation performance with as few as 10 measurement samples, outperforming all relevant baselines. We also validate end-to-end NAS frameworks using HELP against ones without it, and show that it largely reduces the total time cost of the base NAS method, in latency-constrained settings.

As network architecture becomes complex and the user requirement gets diverse, the role of efficient network resource management becomes more important. However, existing throughput-optimal scheduling algorithms such as the max-weight algorithm suffer from poor delay performance. In this paper, we present reinforcement learning-based network scheduling algorithms for a single-hop downlink scenario which achieve throughput-optimality and converge to minimal delay. To this end, we first formulate the network optimization problem as a Markov decision process (MDP) problem. Then, we introduce a new state-action value function called Q+-function and develop a reinforcement learning algorithm called Q+-learning with UCB (Upper Confidence Bound) exploration which guarantees small performance loss during a learning process. We also derive an upper bound of the sample complexity in our algorithm, which is more efficient than the best known bound from Q-learning with UCB exploration by a factor of γ2where γ is the discount factor of the MDP problem. Finally, via simulation, we verify that our algorithm shows a delay reduction of up to 40.8% compared to the max-weight algorithm over various scenarios. We also show that the Q+-learning with UCB exploration converges to an ε-optimal policy 10 times faster than Q-learning with UCB.

We begin this paper by asking a simple question: All beams can be simultaneously activated thanks to the ignorable inter-beam interference and sharp beam shape in mmWave networks? This paper provides a counter-intuitive observation that interference between one-hop adjacent beams still significantly affects the network performance in mmWave networks. Leveraging this observation, we revisit an optimization of interbeam scheduling problem in a network-wide mmWave system on top of a physical layer precoding technique and suggest practical and low-complex beam on/off scheduling and corresponding user scheduling algorithms. Finally, via simulations in a real mmWave network environment, we reveal that the proposed algorithm attains close to the performance of an optimal policy which has much higher computational complexity.

In order to handle a high traffic demand, dense wireless local area networks (WLANs) have been deployed rapidly in the past years. However, dense WLANs cause two critical issues: wastage of energy and severe interference. To address these issues, the centralized management of dense WLANs has been emerged as a powerful paradigm for improving energy efficiency as well as avoiding severe interference. In this paper, we study the joint optimization problem of power-operation modes in access points (APs), channel selections and user-AP associations for improving energy efficiency and avoiding interference without sacrificing users' demands. To this end, we first formulate it as a mixed-integer programming using the popular Lyapunov approach, but it turns out to be computationally intractable, i.e., NP-hard. To address the issue, we propose a polynomial-time approximation algorithm and prove that it achieves a constant-factor approximation guarantee under mild assumptions. The main novelty underlying our algorithm design is based on a linear programming relaxation combining with two different greedy rounding schemes, where each achieves a constant-factor approximation in different regimes of parameters. We verify the performance of the proposed algorithm via extensive simulations and also demonstrate its practicability by implementing it at commercial APs using a Software-defined Networking framework. Results from our experiments show that it reduces the wasted energy significantly while maintaining even higher throughput.

As network architecture becomes complex and the user requirement gets diverse, the role of efficient network resource management becomes more important. However, existing network scheduling algorithms such as the max-weight algorithm suffer from poor delay performance. In this paper, we present a reinforcement learning-based network scheduling algorithm that achieves both optimal throughput and low delay. To this end, we first formulate the network optimization problem as an MDP problem. Then we introduce a new state-action value function called W-function and develop a reinforcement learning algorithm called W-Learning that guarantees little performance loss during a learning process. Finally, via simulation, we verify that our algorithm shows delay reduction of up to 40.8% compared to the max-weight algorithm over various scenarios.

Modern wireless systems are evolving toward a heterogeneous environment where multiple radio access technologies (RATs) coexist. Most of the RATs in current use operate independently of each other, however, there is an increasing demand for coordination among different RATs in order to support exponentially growing wireless traffic. Our goal in this paper is to design a super-MAC that integrates multiple RATs in a tightly coupled manner. To this end, we propose an architecture for super-MAC, and develop an algorithm that splits IP traffic into multiple RATs and controls each RAT to exploit multi-RAT diversity. We prove the asymptotic optimality of the super-MAC algorithm by introducing a novel reference system that enables the analysis of the multi-RAT system where there is a mixture of slotted (such as cellular) and unslotted (such as WiFi) RATs. Through extensive simulations we show that the super-MAC algorithm can enhance the quality of service including throughput, energy efficiency, and fairness.

A fundamental question in the study of location-based mobile sensing is how much energy can be saved while still guaranteeing the reliable localization accuracy. In this paper, we analyze key features of human proximity and find a motivation which implies that the energy-efficient and accurate localization is possible by sharing the locations of nearby mobile devices. From the location-based collaborative sensing idea, we formulate an optimization problem which aims to minimize the total number of location measurements for a given fairness criterion. Then, we propose a practical and distributed location sharing (DLS) protocol and an optimal parameter control algorithm (OWD) which makes the DLS protocol attain an asymptotic optimal performance. Via extensive simulations under various environments including real mobility traces, we verify that the proposed DLS+OWD policy significantly reduces the average power consumption of mobile devices with a higher fairness compared to the existing algorithms.

Mobile computation offloading is emerging as a promising technology to enhance the computation power of mobile devices by borrowing processing resources from the cloud. However, using cloud resource is a double-edged sword because of the potentially enormous network energy consumption of mobile devices. In this paper, we study the mobile device resource management problem for application throughput fairness and energy efficiency in computation offloading environment. Our problem seeks to optimize task arrival rates, scheduling for local processing and offloading, CPU clock speed, and network interface selection, so as to maximize the energy-utility efficiency defined as achievable utility per unit energy consumption. The efficiency metric has a fractional form that is hard to deal with in general. To address this difficulty, we modify a general Lyapunov optimization technique and derive a series of short-term problems that change over time with respect to an unknown objective parameter. Then, we derive an offloading algorithm and prove that the algorithm maximizes the long-term energy-utility efficiency. Trace-driven simulations demonstrate that our algorithm achieves high-energy efficiency while maintaining throughput fairness among applications running on a mobile device.

Network function virtualization (NFV) and Computation offloading (CO) are state-of-the-art technologies for flexible utilization of networking and processing resources. These two technologies are closely related in that they enable multiple physical entities to process a function provided in a service, and the service (or end host) chooses which resources to use. In this paper, we propose a generalized dual-resource system, which unifies NFV service and CO service frameworks, and formulate a multi-path problem for choosing resources to use in NFV and CO services. The problem is reformulated as a variational inequality by using Lagrange dual theory and saddle point theory. Based on this formulation, we propose an extragradient-based algorithm that controls and splits the sending rate of a service. We prove that the algorithm converges to an optimal point where system cost minus service utility is minimized. Simulations under diverse scenarios demonstrate that our algorithm achieves high quality of service while reducing the system cost by jointly considering dual-resource coupling and service characteristics.

We consider energy efficient base station (BS) sleeping and clustering problems in cooperative cellular networks, where clusters of base stations jointly transmit to users. Our key idea of energy saving is to exploit spatio-temporal fluctuation of traffic demand, and use minimal energy to provide achievable data rate only slightly greater than varying traffic demand. However, it is highly challenging to design traffic-aware algorithms without the future traffic demand information. To overcome this difficulty, we develop joint BS sleeping and clustering algorithms using queue instead of the future traffic information. The queue length information captures spatio-temporal mismatch between traffic demand and offered data rate. For BS clustering problem, we propose an optimal algorithm under given BS sleep mode state that has polynomial complexity. We integrate the optimal clustering solution into the sleeping problem, which is a complex combinatorial problem, and develop a joint optimal clustering and sleeping algorithm with reduced complexity compared to the exhaustive search. We also develop a greedy algorithm that finds a near-optimal clustering and sleeping solution with polynomial complexity. Through extensive simulations, we show that the proposed algorithms can save significant energy when traffic load is low.

Most existing content caching designs require accurate estimation of content popularity, which can be challenging in the dynamic mobile network environment. Moreover, emerging hierarchical network architecture enables us to enhance the content caching performance by opportunistically exploiting both cloud-centric and edge-centric caching. In this paper, we propose a hybrid content caching design that does not require the knowledge of content popularity. Specifically, our design optimizes the content caching locations, which can be original content servers, central cloud units (CUs) and base stations (BSs) where the design objective is to support as high average requested content data rates as possible subject to the finite service latency. We fulfill this design by employing the Lyapunov optimization approach to tackle an NP-hard caching control problem with the tight coupling between CU caching and BS caching control decisions. Toward this end, we propose algorithms in three specific caching scenarios by exploiting the submodularity property of the sum-weight objective function and the hierarchical caching structure. Moreover, we prove the proposed algorithms can achieve finite content service delay for all arrival rates within the constant fraction of capacity region using Lyapunov optimization technique. Furthermore, we propose practical and heuristic CU/BS caching algorithms to address a general caching scenario by inheriting the design rationale of the aforementioned performance-guaranteed algorithms. Trace-driven simulation demonstrates that our proposed hybrid CU/BS caching algorithms outperform the general popularity based caching algorithm and the independent caching algorithm in terms of average end-to-end service latency and backhaul/fronthaul load reduction ratios.

In this paper, we consider the content caching design without requiring historical content access information or content popularity profiles in a hierarchical cellular network architecture. Our design aims to dynamically select caching locations for different contents where caching locations can be content servers, cloud units (CUs), and base stations (BSs). Our design objective is to support as high content request rates as possible while maintaining the finite service time. To tackle this design problem, we employ the Lyapunov optimization method where the caching algorithm is developed by minimizing the Lyapunov drift of a quadratic Lyapunov function of virtual queue backlogs. This solution approach requires to solve a max-weight problem, which is an NP-hard and difficult problem to solve due to the coupling between CU caching and BS caching decisions. By exploiting the submodularity of the objective function, we propose a hybrid caching algorithm which achieves the constant approximation ratio to the optimal performance. Trace-driven simulation results demonstrate that the proposed joint CU/BS caching algorithm achieves almost the same performance with the exhaustive search and outperforms the independent caching algorithm and heuristic joint caching algorithms in terms of average end-to-end latency and backhaul load reduction ratio.

In this paper, we study a joint beam and user scheduling problem in a cooperative cellular network utilizing orthogonal random beamforming technique. This paper aims to minimize total base stations' average energy expenditure while ensuring finite service time for all traffic arrivals in a given set. We leverage Lyapunov optimization technique to transform original long-term problem into short-term modified max-weight problem without knowledge of future network states such as traffic arrivals. We introduce a parameter which manipulates energy-delay tradeoff in our system as well. Since provided short-term problem is combinatorial and nonlinear optimization problem, we are inspired by a greedy algorithm to design near-optimal joint beam and user scheduling policy, namely BEANS. We prove that proposed BEANS (i) ensures finite service time for all traffic arrival rates within close to 1/2 capacity region and all (energy-delay) tradeoff parameters thanks to submodular characteristics of the objective function, and (ii) attains finite upper bounds of average energy consumption and average queue backlog for all traffic arrival rates within close to 1/4 capacity region and all tradeoff parameters. Finally, via extensive simulations, we compare the capacity region and energy-queue backlog tradeoff of BEANS with optimal and existing algorithms, and show that BEANS attains 43% of energy saving for the same average queue backlog compared to the algorithms which do not take traffic dynamics and energy consumption into considerations.

Energy consumption for cellular communication is increasingly gaining importance in smartphone battery lifetime as the bandwidth of wireless communication and the demand for mobile traffic increase. For energy-efficient cellular communication, we tackle two energy characteristics of cellular networks: (1) transmission energy highly varies upon channel condition, and (2) transmission of a packet accompanies unnecessary tail energy waste. Under the objective of transmitting packets when the best channel is provided as well as a number of packets are accumulated, we propose a new mobile collaboration framework “CarrierMix” that aggregates smart devices across multiple heterogeneous cellular carriers. Compared to the standalone operation, even without a buffering delay, CarrierMix allows better channel and reduces more tail energy in a statistical point of view. To maximize the energy benefit while maintaining the fairness among the nodes in collaboration, we further develop a dynamic programming framework providing the optimal algorithm of CarrierMix and its approximated heuristic. Trace-driven simulations on our experimental HSPA/EVDO/LTE network traces show that CarrierMix of five devices achieves up to 42 percent of energy reduction.

Delay-tolerant Wi-Fi offloading is known to improve overall mobile network bandwidth at low delay and low cost. Yet, in reality, we rarely find mobile apps that fully support opportunistic Wi-Fi access. This is mainly because it is still challenging to develop delay-tolerant mobile apps due to the complexity of handling network disruptions and delays. In this paper, we present Cedos, a practical delay-tolerant mobile network access architecture in which one can easily build a mobile app. Cedos consists of three components. First, it provides a familiar socket API whose semantics conforms to TCP, while the underlying protocol, D2TP, transparently handles network disruptions and delays in mobility. Second, Cedos allows the developers to explicitly exploit delays in mobile apps. App developers can express maximum user-specified delays in content download or use the API for real-time buffer management at opportunistic Wi-Fi usage. Third, for backward compatibility to existing TCP-based servers, Cedos provides D2Prox, a protocol-translation Web proxy. D2Prox allows intermittent connections on the mobile device side, but correctly translates Web transactions with traditional TCP servers. We demonstrate the practicality of Cedos by porting mobile Firefox and VLC video streaming client to using the API. We also implement delay/disruption-tolerant podcast client and run a field study with 50 people for eight weeks. We find that up to 92.4% of the podcast traffic is offloaded to Wi-Fi, and one can watch a streaming video in a moving train while offloading 48% of the content to Wi-Fi without a single pause.

In the past years, the centralized management of dense wireless local area networks has been emerged as a powerful paradigm for improving energy efficiency as well as avoiding severe interference. In this paper, we study the joint optimization on power-operation modes in access points (APs), channel selections and user-AP associations for improving energy efficiency and avoiding interference without sacrificing users' demands. To this end, we first formulate it as a mixed-integer programming using the popular Lyapunov approach, but it turns out to be computationally intractable, i.e., NP-hard. To address the issue, we propose a polynomial-time approximation algorithm and prove that it achieves a constant-factor approximation guarantee under mild assumptions. The main novelty underlying our algorithm design is based on a linear programming relaxation combining with two different greedy rounding schemes, where each achieves a constant-factor approximation in different regimes of parameters. We verify the performance of the proposed algorithm via extensive simulations and also demonstrate its practicability by implementing it at commercial APs using a Software-defined Networking framework, which shows that it reduces the wasted energy significantly while maintaining even higher throughput.

Mobility predictions are becoming more valuable in various applications with the rise of mobile devices. Given that existing prediction techniques are composed of two key procedures: 1) profiling past mobility trajectories as sequences of discrete atomic states (e.g., grid locations, semantic locations) and capturing them with an appropriate statistical model, 2) making a prediction on the next state using the statistical model, TravelMiner tackles the former with paths utilized as the atomic states for the first time, where the paths are defined as sub-trajectories with no branches. Comparing to available location-based predictors, TravelMiner makes a fundamental difference in that it is able to predict the sequence of paths rather than locations, which is far more detailed in the perspective of knowing the exact route to follow. TravelMiner enables this benefit by extracting disjoint paths from GPS trajectories via a similarity metric for curves, called Frechet distance and keeping the sequences of such paths in a statistical model, called probabilistic radix tree. Our extensive simulations over the GPS trajectories of 124 users reveal that TravelMiner outperforms other predictors in diverse popular performance metrics including predictability, prediction accuracy and prediction resolution.

From the advancements of mobile display and network infrastructure, mobile users can enjoy high quality mobile video streaming anywhere, anytime. However, most mobile users are still reluctant to use high quality video streaming when they are mobile due to costly cellular data and high energy consumption. In this work, we develop scheduling algorithms for resource-efficient mobile video streaming, which minimize the weighted sum objective of cellular cost and energy consumption. We first model the scheduling problem as a Markov decision process and propose an optimal scheduling algorithm based on dynamic programming. Then, we derive a heuristic algorithm that approximates the optimal algorithm. To evaluate the performance of proposed algorithms, we run simulation over YouTube video traces with audience retention graphs and mobility/connectivity traces in public transportation (e.g., commuting). Through extensive simulations, we show that our proposed scheduling algorithm has negligible performance loss compared to the optimal scheduling algorithm, where it saves 59% of cellular cost and 41% of energy compared to the YouTube default scheduler. We also implement our scheduling algorithm on an Android platform, and experimentally evaluate the performance compared to existing streaming policies.

An essential condition precedent to the success of mobile applications based on Wi-Fi (e.g., iCloud) is an energy-efficient Wi-Fi sensing. Clearly, a good Wi-Fi sensing policy should factor in both inter-access point (AP) arrival time (IAT) and contact duration time (CDT) distributions of each individual. However, prior work focuses on limited cases of those two distributions (e.g., exponential) or proposes heuristic approaches such as Additive Increase (AI). In this paper, we first formulate a generalized functional optimization problem on Wi-Fi sensing under general inter-AP and contact duration distributions and investigate how each individual should sense Wi-Fi APs to strike a good balance between energy efficiency and performance, which is in turn intricately linked with users mobility patterns. We then derive a generic optimal condition that sheds insights into the aging property, underpinning energy-aware Wi-Fi sensing polices. In harnessing our analytical findings and the implications thereof, we develop a new sensing algorithm, called Wi-Fi Sensing with AGing (WiSAG), and demonstrate that WiSAG outperforms the existing sensing algorithms up to 37% through extensive trace-driven simulations for which real mobility traces gathered from hundreds of smartphones is used.

Many smartphone applications, e.g., file backup, are intrinsically delay-tolerant so that data processing and transfer can be delayed to reduce smartphone battery usage. In the literature, these energy-delay tradeoff issues have been addressed independently in the forms of Dynamic Voltage and Frequency Scaling (DVFS) problems and network selection problems when smartphones have multiple wireless interfaces. In this paper, we jointly optimize the CPU speed and network speed to determine how much more energy can be saved through the joint optimization when applications can tolerate delays. We propose a dynamic speed scaling scheme called SpeedControl that jointly adjusts the processing and networking speeds using four controls: application scheduling, CPU speed control, wireless interface selection, and transmit power control. Through invoking the “Lyapunov drift-plus-penalty” technique, the scheme is demonstrated to be near optimal because it substantially reduces energy consumption for a given delay constraint. This paper is the first to reveal the energy-delay tradeoff relationship from a holistic perspective for smartphones with multiple wireless interfaces, DVFS, and multitasking capabilities. The trace-driven simulations based on real measurements of CPU power, network power, WiFi/3G throughput, and CPU workload demonstrate that SpeedControl can reduce battery usage by more than 42% through trading a 10 minutes delay when compared with the same delay in existing schemes; moreover, this energy conservation level increases as the WiFi coverage extends.

This paper proposes a new protocol called Optimal DCF (O-DCF). O-DCF modifies the rule of adapting CSMA parameters, such as backoff time and transmission length, based on a function of the demand-supply differential of link capacity captured by the local queue length. O-DCF is fully compatible with 802.11 hardware, so that it can be easily implemented only with a simple device driver update. O-DCF is inspired by the recent analytical studies proven to be optimal under assumptions, which often generates a big gap between theory and practice. O-DCF effectively bridges such a gap, which is implemented in off-the-shelf 802.11 chipset. Through extensive simulations and real experiments with a 16-node wireless network testbed, we evaluate the performance of O-DCF and show that it achieves near-optimality in terms of throughput and fairness and outperforms other competitive ones, such as 802.11 DCF, optimal CSMA, and DiffQ for various scenarios. Also, we consider the coexistence of O-DCF and 802.11 DCF and show that O-DCF fairly shares the medium with 802.11 via its parameter control.

Delay-tolerant Wi-Fi offloading is known to improve overall mobile network bandwidth at low delay and low cost. Yet, in reality, we rarely find mobile apps that fully support opportunistic Wi-Fi access. This is mainly because it is still challenging to develop delay-tolerant mobile apps due to the complexity of handling network disruptions and delays.

Mobile cloud computing (MCC) has been proposed to offload heavy computing jobs of mobile devices to cloud servers managed by cloud service provider (CSP), which enables the mobile devices to save energy and processing delay. Heretofore, cloud offloading policies in mobile devices and pricing/scheduling in CSP have been independently addressed. This paper is first to jointly account for both sides of mobile users and CSP in a unified mobile cloud computing framework. By invoking “Lyapunov drift-plus-penalty” technique, we propose dual-side control algorithms for the mobile users and CSP in two different scenarios: (i) In non-cooperation scenario, we propose a NC-UC algorithm for the mobile users and a NC-CC algorithm for the CSP to minimize each cost for given delay constraints. (ii) In cooperation scenario, we suggest a CP-JC algorithm for both cloud users and CSP to minimize the sum costs of them for given delay constraints. Trace-driven simulations demonstrate that NC-UC saves minimum 63% of cost by trading 8MB of average queue lengths when compared with the existing algorithms, and NC-CC achieves 71% of profit gain when compared with the same delay of existing scheme; moreover, the cooperation enables them to save additional costs and delays.

We consider energy efficient base station sleeping and clustering problems in cooperative cellular networks where clusters of base stations jointly transmit to users. Our key idea of energy saving is to exploit a spatio-temporal fluctuation of traffic demand, which is to use minimal energy to provide capacity only slightly greater than varying traffic demand. Then, energy saving is possible without capacity loss. However, it is highly challenging to design traffic-aware algorithms without the future traffic demand information. To overcome this, we develop algorithms using queue instead of the future traffic information. For BS clustering problem, we propose an optimal algorithm that has polynomial complexity. For BS sleeping problem, which is a complex combinatorial problem, we propose two algorithms; One finds an optimal solution with reduced complexity compared to the exhaustive search, and the other finds a near-optimal solution with polynomial complexity. Through extensive simulations we show that the proposed algorithms can save significant energy when traffic load is low.

To cope with increasing energy consumption in mobile devices, the mobile cloud offloading has received considerable attention from its ability to offload processing tasks of mobile devices to cloud servers, and previous studies have focused on single type tasks in fixed network environments. However, real network environments are spatio-temporally varying, and typical mobile devices have not only various types of tasks, e.g., network traffic, cloud offloadable/nonoffloadable workloads but also capabilities of CPU frequency scaling and network interface selection between WiFi and cellular. In this paper, we first jointly consider the following three dynamic problems in real mobile environments: 1) cloud offloading policy, i.e., determining to use local CPU resources or cloud resources; 2) allocation of tasks to transmit through networks and to process in local CPU; and 3) CPU clock speed and network interface controls. We propose a DREAM algorithm by invoking the Lyapunov optimization and mathematically prove that it minimizes CPU and network energy for given delay constraints. Trace-driven simulation based on real measurements demonstrates that DREAM can save over 35% of total energy than existing algorithms with the same delay. We also design DREAM architecture and demonstrate the applicability of DREAM in practice.

In this paper, a joint optimization of link scheduling, routing and replication for delay-tolerant networks (DTNs) has been studied. The optimization problems for resource allocation in DTNs are typically solved using dynamic programming which requires knowledge of future events such as meeting schedules and durations. This paper defines a new notion of approximation to the optimality for DTNs, called snapshot approximation where nodes are not clairvoyant, i.e., not looking ahead into future events, and thus decisions are made using only contemporarily available knowledges. Unfortunately, the snapshot approximation still requires solving an NP-hard problem of maximum weighted independent set (MWIS) and a global knowledge of who currently owns a copy and what their delivery probabilities are. This paper proposes an algorithm, Max-Contribution (MC) that approximates MWIS problem with a greedy method and its distributed online approximation algorithm, Distributed Max-Contribution (DMC) that performs scheduling, routing and replication based only on locally and contemporarily available information. Through extensive simulations based on real GPS traces tracking over 4,000 taxies and 500 taxies for about 30 days and 25 days in two different large cities, DMC is verified to perform closely to MC and outperform existing heuristically engineered resource allocation algorithms for DTNs.

We consider the problem of providing inter-access-point (AP) fairness guarantee in dense AP deployments where starvation can occur. In particular, we develop a framework for providing robust minimum throughput guarantee for each AP under the uncertainty of user distributions. Our framework consists of an AP throughput provisioning scheme and a distributed CSMA algorithm. The throughput provisioning scheme computes a robust feasible minimum AP throughput vector based on a random AP-level conflict graph and chance-constrained optimization. By incorporating the minimum throughput vector, we develop a distributed CSMA algorithm that fulfills the minimum requirement for each AP and is compatible with the IEEE 802.11 standard. We show through extensive simulations that our framework addresses the AP starvation problem by guaranteeing minimum throughput for each AP.

Energy-delay tradeoffs in smartphone applications have been studied independently in dynamic voltage and frequency scaling (DVFS) problem and network interface selection problem. We optimize the two problems jointly to quantify how much energy can be saved further and propose a scheme called SpeedControl which jointly manages application scheduling, CPU speed control and wireless interface selection. The scheme is shown to be near-optimal in that it tends to minimize energy consumption for given delay constraints. This paper is the first to reveal energy-delay tradeoffs in a holistic view considering multiple wireless interfaces, DVFS and multitasking in smartphone. We perform real measurements on WiFi/3G coverage and throughput, power consumption of CPU and WiFi/3G interfaces, and CPU workloads. Trace-driven simulations based on the measurements demonstrate that SpeedControl can save over 30% of battery by trading 10 min delay as compared to existing schemes when WiFi temporal coverage is 65%, moreover, the saving tendency increases as WiFi coverage increases.

Energy consumption for cellular communication is increasingly gaining importance in smartphone battery lifetime as the bandwidth of wireless communication and the demand for mobile traffic increase. For energy-efficient cellular communication, we tackle two energy characteristics of cellular networks: (1) transmission energy highly varies upon channel condition, and (2) transmission of a packet accompanies unnecessary tail energy waste. Under the objective of transmitting packets when the best channel is provided as well as a number of packets are accumulated, we propose a new mobile collaboration framework “PhonePool” that aggregates smart devices across multiple cellular providers. Compared to the standalone operation, even without a buffering delay, PhonePool allows better channel and reduces more tail energy in a statistical point of view. To maximize the energy benefit while maintaining the fairness among the nodes in collaboration, we further develop a dynamic programming framework providing the optimal algorithm of PhonePool and its approximated heuristic. Trace-driven simulations on our experimental HSPA/EVDO/LTE network traces show that PhonePool of 5 devices achieves up to 42% of energy reduction.

We study the coordinated transmission problem in cooperative cellular networks where a cluster of base stations forms a virtual cell to serve a mobile station (MS). The performance of such an MS-centric virtual cell network is dictated by the beamformer that enables to suppress interference; however, designing a beamformer is highly challenging due to the coupled nature of interference and desired signals under arbitrarily formed virtual cells. We develop a new formulation of the beamforming problem for sum-rate maximization in virtual cell networks and analyze the structure of its optimal solutions. Based on this analysis, we develop a beamforming algorithm that can balance between desired signal maximization and interference minimization, so as to maximize the sum-rate. We show through extensive simulations that our balanced beamforming algorithm mitigates edge user effect and outperforms existing algorithms in various scenarios where virtual cells are allowed to overlap.

Cellular networks are facing severe traffic overloads due to the proliferation of smart handheld devices and traffic-hungry applications. A cost-effective and practical solution is to offload cellular data through WiFi. Recent theoretical and experimental studies show that a scheme, referred to as delayed WiFi offloading, can significantly save the cellular capacity by delaying users' data and exploiting mobility and thus increasing chance of meeting WiFi APs (Access Points). Despite a huge potential of WiFi offloading in alleviating mobile data explosion, its success largely depends on the economic incentives provided to users and operators to deploy and use delayed offloading. In this paper, we study how much economic benefits can be generated due to delayed WiFi offloading, by modeling the interaction between a single provider and users based on a two-stage sequential game. We first analytically prove that WiFi offloading is economically beneficial for both the provider and users. Also, we conduct trace-driven numerical analysis to quantify the practical gain, where the increase ranges from 21% to 152% in the providers revenue, and from 73% to 319% in the users surplus.

An essential condition precedent to the success of mobile applications based on Wi-Fi (e.g., iCloud) is an energy-efficient Wi-Fi sensing. From a user's perspective, a good WiFi sensing policy should depend on both inter-AP arrival and contact duration time distributions. Prior work focuses on limited cases of those two distributions (e.g., exponential) or introduces heuristic approaches such as AI (Additive Increase). In this paper, we formulate a functional optimization problem on Wi-Fi sensing under general inter-AP and contact duration distributions, and propose how each user should sense Wi-Fi APs to strike a balance between energy efficiency and performance, depending on the users' mobility pattern. To that end, we derive an optimal condition which sheds insights into the aging property, the key feature required by efficient Wi-Fi sensing polices. Guided by the analytical studies and the implications, we develop a new sensing algorithm, called WiSAG (Wi-Fi Sensing with AGing), which is demonstrated to outperform the existing sensing algorithms up to 34% through extensive trace-driven simulations using the real mobility traces gathered from smartphones.

Cellular networks are facing severe traffic overloads due to the proliferation of smart handheld devices and traffichungry applications. A cost-effective and practical solution is to offload cellular data through WiFi. Recent theoretical and experimental studies show that a scheme, referred to as delayed WiFi offloading, can significantly save the cellular capacity by delaying users' data and exploiting mobility and thus increasing chance of meeting WiFi APs (Access Points). Despite a huge potential of WiFi offloading in alleviating mobile data explosion, its success largely depends on the economic incentives provided to users and network providers to deploy and use delayed offloading. In this paper, we study how much economic benefits can be generated due to delayed WiFi offloading, by modeling the interaction between a single provider and users based on a two-stage sequential game. We first analytically prove that WiFi offloading is economically beneficial for both the provider and users. Also, we conduct trace-driven numerical analysis to quantify the practical gain, where the increase ranges from 21 to 152% in the provider's revenue, and from 73 to 319% in the users' surplus.

This paper proposes a new wireless MAC protocol called Optimal DCF (O-DCF). O-DCF modifies the rule of adapting CSMA parameters, such as backoff time and transmission length, based on a function of the supply-demand differential captured by the local queue length. O-DCF is fully compatible with 802.11 hardware, so that it can be easily implemented only with a simple device driver update. O-DCF is inspired by the recent theoretical studies on queue-based CSMA for high throughput and fairness. O-DCF effectively bridges the gap between theory and practice, implemented and tested in an off-the-shelf 802.11 chipset. Through extensive simulations and real experiments with a 16-node wireless network testbed, we evaluate the performance of O-DCF and show that it outperforms other competitive ones, such as 802.11 DCF, optimal CSMA, and DiffQ for various scenarios.

Delay-capacity tradeoffs for mobile networks have been analyzed through a number of research works. However, Lévy mobility known to closely capture human movement patterns has not been adopted in such work. Understanding the delay-capacity tradeoff for a network with Lévy mobility can provide important insights into understanding the performance of real mobile networks governed by human mobility. This paper analytically derives an important point in the delay-capacity tradeoff for Lévy mobility, known as the critical delay. The critical delay is the minimum delay required to achieve greater throughput than what conventional static networks can possibly achieve (i.e., O(1/√n) per node in a network with n nodes). The Lévy mobility includes Lévy flight and Lévy walk whose step-size distributions parametrized by α ∈ (0,2] are both heavy-tailed while their times taken for the same step size are different. Our proposed technique involves: 1) analyzing the joint spatio-temporal probability density function of a time-varying location of a node for Lévy flight, and 2) characterizing an embedded Markov process in Lévy walk, which is a semi-Markov process. The results indicate that in Lévy walk, there is a phase transition such that for α ∈ (0,1), the critical delay is always Θ(n[1/2]), and for α ∈ [1,2] it is Θ(n[(α)/2]). In contrast, Lévy flight has the critical delay Θ(n[(α)/2]) for α ∈ (0,2].

This paper presents a quantitative study on the performance of 3G mobile data offloading through WiFi networks. We recruited 97 iPhone users from metropolitan areas and collected statistics on their WiFi connectivity during a two-and-a-half-week period in February 2010. Our trace-driven simulation using the acquired whole-day traces indicates that WiFi already offloads about 65% of the total mobile data traffic and saves 55% of battery power without using any delayed transmission. If data transfers can be delayed with some deadline until users enter a WiFi zone, substantial gains can be achieved only when the deadline is fairly larger than tens of minutes. With 100-s delays, the achievable gain is less than only 2%-3%, whereas with 1 h or longer deadlines, traffic and energy saving gains increase beyond 29% and 20%, respectively. These results are in contrast to the substantial gain (20%-33%) reported by the existing work even for 100-s delayed transmission using traces taken from transit buses or war-driving. In addition, a distribution model-based simulator and a theoretical framework that enable analytical studies of the average performance of offloading are proposed. These tools are useful for network providers to obtain a rough estimate on the average performance of offloading for a given WiFi deployment condition.

Many empirical studies of human walks have reported that there exist fundamental statistical features commonly appearing in mobility traces taken in various mobility settings. These include: 1) heavy-tail flight and pause-time distributions; 2) heterogeneously bounded mobility areas of individuals; and 3) truncated power-law intercontact times. This paper reports two additional such features: a) The destinations of people (or we say waypoints) are dispersed in a self-similar manner; and b) people are more likely to choose a destination closer to its current waypoint. These features are known to be influential to the performance of human-assisted mobility networks. The main contribution of this paper is to present a mobility model called Self-similar Least-Action Walk (SLAW) that can produce synthetic mobility traces containing all the five statistical features in various mobility settings including user-created virtual ones for which no empirical information is available. Creating synthetic traces for virtual environments is important for the performance evaluation of mobile networks as network designers test their networks in many diverse network settings. A performance study of mobile routing protocols on top of synthetic traces created by SLAW shows that SLAW brings out the unique performance features of various routing protocols.

Greening effect in interference management (IM), a way of enhancing spectrum sharing via intelligent transmit power control, can be achieved by the fact that as BSs moderately reduce their transmit powers, the performance degradation decreases slower than linearly, yet a considerable overall energy saving is expected due to transmit powers' exerting influence on operational power. This paper investigates the impact of different spatial and/or temporal power sharing policies for a given system-wide power budget in IM schemes. We develop an optimization-theoretic IM framework on cellular network greening, from which we first develop four IM schemes governed by different power sharing: no sharing, only temporal sharing, only spatial sharing, and both spatial and temporal sharing. Through extensive simulations, including a real BS deployment in Manchester city, United Kingdom, we obtain the following interesting observations: (i) the gains both from performance and power saving are obtained by adopting the spatial and/or temporal power sharing policies, (ii) tighter greening regulation (i.e., smaller total power budget) leads to higher spatio-temporal power sharing gain than IM gain, (iii) spatial power sharing significantly excels temporal one in terms of power saving, and (iv) higher greening efficiency can be achieved as the cell size becomes smaller.

This paper analytically derives the delay-capacity tradeoffs for Lévy mobility: Lévy walks and Lévy flights. Lévy mobility is a random walk with a power-law flight distribution. α is the power-law slope of the distribution and 01/2) and for 1 ≤ α ≤ 2, is Θ(nα/2). In contrast, Lévy flight has critical delay Θ(nα/2) for 0 <; α ≤ 2.

By `optimal CSMA' we denote a promising approach to maximize throughput-based utility in wireless networks without message passing or synchronization among nodes. Despite the theoretical guarantees on the performance of these protocols, their evaluation in real networking scenarios has been preliminary. In this paper, we propose a methodical approach for the first comprehensive evaluation of optimal CSMA, via experimentation with a custom implementation. Example findings include; 1) hidden terminals with symmetric channels can drive the protocol to a state of extreme contention aggressiveness due to the low service received by flows. Since increasing aggressiveness does not mitigate collisions but actually aggravates them, optimal CSMA enters a positive-feedback loop eventually reaching a deadlock state of total flow starvation; 2) however, the use of RTS/CTS in such scenarios can reduce collisions to lower levels, restoring throughput and preventing an excessive contention aggressiveness by optimal CSMA flows; 3) in practical hidden terminal scenarios with physical layer capture optimal CSMA reduces the aggressiveness of dominant flows, but the contention window sizes used by such adaptation mechanism are not long enough to solve competing flows' starvation when carrier sensing fails; 4) topologies with a “flow-in-the-middle” yield starvation in traditional CSMA but fairness in optimal CSMA, because its contention aggressiveness adaptation creates frequent transmission opportunities for the central (otherwise starved) flow; 5) optimal CSMA excessively prioritizes links with low channel quality, due to queue-based control that does not otherwise incorporate channel conditions; 6) in its current design, optimal CSMA conflicts with window-based end-to-end congestion control, and leads to a efficiency-fairness tradeoff in TCP performance. This study deepens our understanding of optimal CSMA and the general adaptation philosophy behind its design, and the derived insights suggest enhancements to optimal CSMA theory.

Greening effect in interference management (IM), which is a technology to enhance spectrum sharing via intelligent BS transmit power control, can be achieved by the fact that even small reduction in BS transmit powers enables considerable saving in overall energy consumption due to their exerting influence on operational powers. In this paper, we study the impact of power sharing policies in IM schemes on cellular network greening, where different spatio-temporal power sharing policies are considered for a fixed system-wide power budget. This study is of great importance in that the pressure on the CO2emission limit per nation increases, e.g., by Kyoto protocol, which will ultimately affect the power budget of a wireless service provider. We propose optimization theoretic IM frameworks with greening, from which we first develop four IM schemes with different power sharing policies. Through extensive simulations under various configurations, including a real BS deployment in Manchester city, United Kingdom, we obtain the following interesting observations: (i) tighter greening regulation (i.e., the smaller total power budget) leads to higher spatio-temporal power sharing gain than IM gain, (ii) spatial power sharing significantly excels temporal one, and (iii) more greening gain can be achieved as the cell size becomes smaller.

Due to the increasing demand of capacity in wireless cellular networks, the small cells such as pico and femto cells are becoming more popular to enjoy a spatial reuse gain, and thus cells with different sizes are expected to coexist in a complex manner. In such a heterogeneous environment, the role of interference management (IM) becomes of more importance, but technical challenges also increase, since the number of cell-edge users, suffering from severe interference from the neighboring cells, will naturally grow. In order to overcome low performance and/or high complexity of existing static and other dynamic IM algorithms, we propose a novel low-complex and fully distributed IM scheme, called REFIM (REFerence based Interference Management), in the downlink of heterogeneous multi-cell networks. We first formulate a general optimization problem that turns out to require intractable computation complexity for global optimality. To have a practical solution with low computational and signaling overhead, which is crucial for low-cost small-cell solutions, e.g., femto cells, in REFIM, we decompose it into per-BS (base station) problems based on the notion of reference user and reduce feedback overhead over backhauls both temporally and spatially. We evaluate REFIM through extensive simulations under various configurations, including the scenarios from a real deployment of BSs. We show that, compared to the schemes without IM, REFIM can yield more than 40% throughput improvement of cell-edge users while increasing the overall performance by 10~107%. This is equal to about 95% performance of the existing centralized IM algorithm (MC-IIWF) that is known to be near-optimal but hard to implement in practice due to prohibitive complexity. We also present that as long as interference is managed well, the spectrum sharing policy can outperform the best spectrum splitting policy where the number of subchannels is optimally divided between macro and femto cells.

We report that human walk patterns contain statistically similar features observed in Levy walks. These features include heavy-tail flight and pause-time distributions and the super-diffusive nature of mobility. Human walks are not random walks, but it is surprising that the patterns of human walks and Levy walks contain some statistical similarity. Our study is based on 226 daily GPS traces collected from 101 volunteers in five different outdoor sites. The heavy-tail flight distribution of human mobility induces the super-diffusivity of travel, but up to 30 min to 1 h due to the boundary effect of people's daily movement, which is caused by the tendency of people to move within a predefined (also confined) area of daily activities. These tendencies are not captured in common mobility models such as random way point (RWP). To evaluate the impact of these tendencies on the performance of mobile networks, we construct a simple truncated Levy walk mobility (TLW) model that emulates the statistical features observed in our analysis and under which we measure the performance of routing protocols in delay-tolerant networks (DTNs) and mobile ad hoc networks (MANETs). The results indicate the following. Higher diffusivity induces shorter intercontact times in DTN and shorter path durations with higher success probability in MANET. The diffusivity of TLW is in between those of RWP and Brownian motion (BM). Therefore, the routing performance under RWP as commonly used in mobile network studies and tends to be overestimated for DTNs and underestimated for MANETs compared to the performance under TLW.

Achieving sufficient spatial capacity gain through the use of small cells requires careful consideration of inter-cell interference (ICI) management via BS power coordination coupled with user scheduling inside cells. Optimal algorithms are known to be difficult to implement due to high computation and signaling overhead. This study proposes joint pattern-based ICI management and user scheduling algorithms that are practically implementable. The key idea is to decompose the original problem into two sub-problems in which ICI management is run at a slower time scale than user scheduling. We empirically show that even with such a slow tracking of system dynamics at the ICI management part, the decomposed approach achieves a considerable performance increase compared to conventional universal reuse schemes.

This paper presents a quantitative study on the performance of 3G mobile data offloading through WiFi networks. We recruited about 100 iPhone users from metropolitan areas and collected statistics on their WiFi connectivity during about a two and half week period in February 2010. Our trace-driven simulation using the acquired traces indicates that WiFi already offloads about 65% of the total mobile data traffic and saves 55% of battery power without using any delayed transmission. If data transfers can be delayed with some deadline until users enter a WiFi zone, substantial gains can be achieved only when the deadline is fairly larger than tens of minutes. With 100 second delays, the achievable gain is less than only 2--3%. But with 1 hour or longer deadline, traffic and energy saving gains increase beyond 29% and 20%, respectively. These results are in stark contrast to the substantial gain (20 to 33%) reported by the existing work even for 100 second delayed transmission using traces taken from transit buses or war-driving. The major performance difference comes from traces: while bus and war-driving traces contain much shorter connection and inter-connection times, our traces reflects the daily mobility patterns of average users more accurately.

This paper investigates power allocation algorithms for OFDM-based cognitive radio systems, where the intra-system channel state information (CSI) of the secondary user (SU) is perfectly known. However, due to loose cooperation between the SU and the primary user (PU), the inter-system CSI is only partially available to the SU transmitter. Two types of PUs are considered to have different capabilities. One is a dumb (Peak Interference-Power tolerable) system that can tolerate a certain amount of peak interference at each subchannel. The other is a more sophisticated (Average Interference-Power tolerable) system that can tolerate the interference from the SU as long as the average interference over all subchannels is within a certain threshold. Accordingly, we introduce an interference power outage constraint, with which the outage is maintained within a target level. The outage is here defined as the probability that peak or average interference power to the PU is greater than a given threshold. With both this interference-power outage constraint along with a transmit-power constraint, we propose optimal and suboptimal algorithms to maximize the capacity of the SU. We evaluate the spectral efficiency through extensive simulations and show that the SU can achieve higher performance (up to two times) with the more sophisticated PU than with the dumb PU.

This is by far the first paper considering joint optimization of link scheduling, routing and replication for disruption-tolerant networks (DTNs). The optimization problems for resource allocation in DTNs are typically solved using dynamic programming which requires knowledge of future events such as meeting schedules and durations. This paper defines a new notion of optimality for DTNs, called snapshot optimality where nodes are not clairvoyant, i.e., cannot look ahead into future events, and thus decisions are made using only contemporarily available knowledge. Unfortunately, the optimal solution for snapshot optimality still requires solving an NP-hard problem of maximum weight independent set and a global knowledge of who currently owns a copy and what their delivery probabilities are. This paper presents a new efficient approximation algorithm, called Distributed Max-Contribution (DMC) that performs greedy scheduling, routing and replication based only on locally and contemporarily available information. Through a simulation study based on real GPS traces tracking over 4000 taxies for about 30 days in a large city, DMC outperforms existing heuristically engineered resource allocation algorithms for DTNs.

This is a quantitative study on the performance of 3G mobile data offloading through WiFi networks. We recruited about 100 iPhone users from a metropolitan area and collected statistics on their WiFi connectivity during about a two and half week period in February 2010. We find that a user is in WiFi coverage for 70% of the time on average and the distributions of WiFi connection and disconnection times have a strong heavy-tail tendency with means around 2 hours and 40 minutes, respectively. Using the acquired traces, we run trace-driven simulation to measure offloading efficiency under diverse conditions e.g. traffic types, deadlines and WiFi deployment scenarios. The results indicate that if users can tolerate a two hour delay in data transfer (e.g, video and image up-loads), the network can offload 70% of the total 3G data traffic on average. We also develop a theoretical framework that permits an analytical study of the average performance of offloading. This tool is useful for network providers to obtain a rough estimate on the average performance of offloading for a given inputWiFi deployment condition.

In this paper, we propose a scheduling framework for heterogeneous traffic in OFDMA-based wireless systems. The proposed scheduling algorithm not only satisfies the QoS requirements of the real-time traffic but also maximizes the utility of the non real-time traffic. Step-by-step approach is used to achieve these two objectives simultaneously with low complexity and traffic class prioritization. A well-known bipartite matching algorithm and a standard gradient scheduling algorithm are adopted for the QoS scheduling of the real-time traffic and for the utility maximization scheduling of the non real-time traffic, respectively. Moreover, a noble beta deadline parameter is introduced to control the balance between the QoS provisioning and the diversity gain. Extensive simulation results in various scenarios are provided to demonstrate the good features of our scheduling framework.

We propose a method for detecting Distributed Denial of Service (DDoS) traffic in real-time inside the network. For this purpose, we borrow the concepts of Moving Average Convergence Divergence, Rate of Change, and Relative Strength Index, which are used for technical analysis in the stock market. Due to the fact that the method is based on a quantitative, rather than a heuristic, detection level, DDoS traffic can be detected with greater accuracy (by reducing the false alarm ratio). Through detection algorithm and simulation results, we show how the detection level is determined and demonstrate the degree to which the accuracy of detection is enhanced.

Simulating human mobility is important in mobile networks because many mobile devices are either attached to or controlled by humans and it is very hard to deploy real mobile networks whose size is controllably scalable for performance evaluation. Lately various measurement studies of human walk traces have discovered several significant statistical patterns of human mobility. Namely these include truncated power-law distributions of flights, pause-times and inter-contact times, fractal way-points, and heterogeneously defined areas of individual mobility. Unfortunately, none of existing mobility models effectively captures all of these features. This paper presents a new mobility model called SLAW (self-similar least action walk) that can produce synthetic walk traces containing all these features. This is by far the first such model. Our performance study using using SLAW generated traces indicates that SLAW is effective in representing social contexts present among people sharing common interests or those in a single community such as university campus, companies and theme parks. The social contexts are typically common gathering places where most people visit during their daily lives such as student unions, dormitory, street malls and restaurants. SLAW expresses the mobility patterns involving these contexts by fractal way points and heavy-tail flights on top of the way points. We verify through simulation that SLAW brings out the unique performance features of various mobile network routing protocols.

Underlay transmission in cognitive radio enables a secondary (unlicensed) system to utilize a frequency band of primary (licensed) system as long as the unlicensee interferes less than a certain threshold with the licensee. The secondary system needs to carefully consider not only its own channel to achieve a capacity gain by this sharing spectrum in multi- carrier systems, but also the interference channel to reduce interference at the primary receiver. In this paper, we formulate a capacity maximization problem of the secondary system under an interference-power constraint as well as a conventional transmit- power constraint, and propose an optimal power allocation policy in which we exploit a two-dimensional frequency-selectivity on both channels. Through extensive simulations, we compare the performance of optimal power allocation policy with that of equal power allocation policy and further investigate the effect of the primary's power allocation policy on the performance of the secondary system. Numerical results show that the optimal power allocation policy can achieve a higher capacity in more frequency- selective channels, compared to an equal power allocation policy. Interestingly, a water-filling policy for the primary system also gives additional opportunities to the secondary system than the equal power allocation policy.

Welcome to Seoul and welcome to the Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), the intellectual hub and melting pot of ideas from researchers and ractitioners interested in all aspects of modeling and optimization of wireless communication, ad hoc and mobile networking.

Achieving sufficient spatial capacity gain by having small cells requires careful treatment of inter-cell interference (ICI) management via BS power coordination coupled with user scheduling inside cells. Optimal algorithms have been known to be hard to implement due to high computation and signaling overheads. We propose joint pattern-based ICI management and user scheduling algorithms that are practically implementable. The basic idea is to decompose the original problem into two sub-problems, where we run ICI management at a slower time scale than user scheduling. We empirically show that even with such a slow tracking of system dynamics at the ICI management part, the decomposed approach achieves high performance increase, compared to a conventional universal reuse scheme.

We present a unified analytical framework that maximizes generalized utilities of a wireless network by network-wide opportunistic scheduling and power control. That is, base stations in the network jointly decide mobile stations to be served at the same time as the transmission powers of base stations are coordinated to mitigate the mutually interfering effect. Although the maximization at the first glance appears to be a mixed, twofold and nonlinear optimization requiring excessive computational complexity, we show that the maximization can be transformed into a pure binary optimization with much lower complexity. To be exact, it is proven that binary power control of base stations is necessary and sufficient for maximizing the network-wide utilities under a physical layer regime where the channel capacity is linear in the signal-to-interference-noise ratio. To further reduce the complexity of the problem, a distributed heuristic algorithm is proposed that performs much better than existing opportunistic algorithms. Through extensive simulations, it becomes clear that network-wide opportunistic scheduling and power control is most suitable for fairness-oriented networks and under loaded networks. We believe that our work will serve as a cornerstone for network-wide scheduling approaches from theoretical and practical standpoints.

Next-generation cellular networks will provide higher cell capacity by adopting advanced physical layer techniques and broader bandwidth. Even in such networks, boundary users would suffer from low throughput due to severe intercell interference and unbalanced user distributions among cells, unless additional schemes to mitigate this problem are employed. In this paper, we tackle this problem by jointly optimizing partial frequency reuse and load-balancing schemes in a multicell network. We formulate this problem as a network-wide utility maximization problem and propose optimal offline and practical online algorithms to solve this. Our online algorithm turns out to be a simple mixture of inter- and intra-cell handover mechanisms for existing users and user association control and cell-site selection mechanisms for newly arriving users. A remarkable feature of the proposed algorithm is that it uses a notion of expected throughput as the decision making metric, as opposed to signal strength in conventional systems. Extensive simulations demonstrate that our online algorithm can not only closely approximate network-wide proportional fairness but also provide two types of gain, interference avoidance gain and load balancing gain, which yield 20∼100% throughput improvement of boundary users (depending on traffic load distribution), while not penalizing total system throughput.We also demonstrate that this improvement cannot be achieved by conventional systems using universal frequency reuse and signal strength as the decision making metric.

The introduction of relays into legacy cellular networks is gaining more of an interest in the 4th generation (4G) wireless systems. In the presence of relays, simultaneous transmission of both base stations (BS) and relay stations (RS) on the same resources is possible, and consequently much higher throughput can be achieved. However, determining the set of links which will be turned on at the same time is usually considered a NP-complete combinatorial problem. Moreover, it requires cooperation between BSs and RSs of independent cells. In such context, we briefly address the difficulties of spatial resource reuse from the graph-theoretical perspective. Next, our focus shifts to developing a simple but efficient radio resource management algorithm which enables the spatial resource reuse, the pricing- based radio resource management (PRRM) strategy. The PRRM performs spatial reuse for interference-free users operating in the high signal-to-interference-and-noise ratio (SINR) region, while guaranteeing the signal quality of interference-susceptible users usually located near the coverage boundary. By applying the PRRM, we evaluate the potential benefits of the spatial resource reuse.

We present an online distributed traffic engineering method for ISP networks with multi-path routing. The method is based on edge-to-edge aggregate flow control that balances load and makes the network congestion-free in real time, responding to actual traffic demands whether they are underload or overloaded. Moreover, it allows ISPs to apply various bandwidth-sharing policies to edge-to-edge flows, as desired. Our simulations confirm that the proposed method works as designed for TCP sources that have their own end-to-end congestion control mechanism and enhance the performance and the efficiency of the the network.

We report that human walks performed in outdoor settings of tens of kilometers resemble a truncated form of Levy walks commonly observed in animals such as monkeys, birds and jackals. Our study is based on about one thousand hours of GPS traces involving 44 volunteers in various outdoor settings including two different college campuses, a metropolitan area, a theme park and a state fair. This paper shows that many statistical features of human walks follow truncated power-law, showing evidence of scale-freedom and do not conform to the central limit theorem. These traits are similar to those of Levy walks. It is conjectured that the truncation, which makes the mobility deviate from pure Levy walks, comes from geographical constraints including walk boundary, physical obstructions and traffic. None of commonly used mobility models for mobile networks captures these properties. Based on these findings, we construct a simple Levy walk mobility model which is versatile enough in emulating diverse statistical patterns of human walks observed in our traces. The model is also used to recreate similar power-law inter-contact time distributions observed in previous human mobility studies. Our network simulation indicates that the Levy walk features are important in characterizing the performance of mobile network routing performance.

This paper revisits equal power allocation from the viewpoint of asymptotic network utility maximization (NUM) problem in multi-carrier systems. It is a well-known fact that the equal power allocation is near optimal to the sum capacity maximization problem in high SNR (signal-to-noise ratio) regime, i.e., optimal water-filling approximates to equal power allocation in that case. Due to this property together with its simplicity, the equal power allocation has been adopted in several researches, but its performance in other problems has not been clearly understood. We evaluate the suitability of equal power allocation in NUM problem which turns into various resource sharing policies according to utility functions. Namely, our conclusion is that in frequency selective channels, the equal power allocation is near optimal for efficiency-oriented resource sharing policy, but when fairness is emphasized, its performance is severely degraded and thus frequency-selective power allocation is necessary. For this, we develop a suboptimal subcarrier and frequency-selective power allocation algorithm for asymptotic NUM problem using the gradient-based scheduling theory and compare the performance of equal power allocation and the developed algorithm. Extensive simulation results are presented to verify our arguments.

This paper revisits burst contention resolution problems in optical burst switching (OBS) networks from the viewpoint of network utility maximization. Burst collision occurs when two or more bursts access the same wavelength simultaneously, and the occurrence becomes more frequent as the offered load increases. In particular, when the network is overloaded, no contention resolution scheme would effectively avoid the collision without the help of congestion control. We formulate a joint optimization problem where two variables, the length and the time at which each burst is injected into the network, are jointly optimized in order to maximize aggregate utility while minimizing burst loss. A distributed algorithm is also developed, which explicitly reveals how burst contention resolution and congestion control must interact. The simulation results show that the joint control decouples throughput performance from burst loss performance so that burst loss ratio does not increase as network throughput increases. This is not the case in conventional contention resolution schemes where burst loss ratio increases as network throughput increases so that achievable network throughput is limited. Our work is the first attempt to the joint design of congestion and contention control and might lead to an interesting development in OBS research.

A wireless mesh network (WMN) is being considered for commercial use in spite of several unaddressed issues. In this paper we focus on one of the most critical issues: the impact of ambient motion of entities like people on the channel characteristics and on the WMN performance. A human body in an electro-magnetic (EM) field acts as an scatterer that absorbs 60% of incident EM energy, thereby shadowing the receiver. This human body model along with the human mobility behavior gives rise to a black body (a group movement) effect that traps the incident EM wave with repetitive internal reflections. The black body theory is verified by simulating the WiSEMesh testbed in picoKAIST, a tool based on deterministic ray tube method. Experimental results show each link exhibiting a unique channel variation pattern in presence of the black body. Based on the pattern we provide several insights in WMN deployment and protocol design.

In this paper, we study how the cooperative relaying can improve both capacity and fairness in cellular network. The capacity and fairness have a trade-off relationship, so increasing cell throughput deteriorates fairness and vice versa. First, we show that the achievable average throughput region can be enlarged by using the cooperative relaying. This enlarged region means that capacity and fairness can be improved at the same time with an adequate scheduling algorithm. Thus, secondly we propose a generalized scheduling algorithm for cooperative relaying. The proposed scheduling algorithm can improve both capacity and fairness at the expense of cooperation among users. From simulations, we show that the trade-off relationship can be surpassed and the unfairness problem in the heterogeneous channel condition can be solved by the opportunistic relaying.

Most of up-to-date wireless data systems are based on the OFDM technology and employ the opportunistic scheduling to exploit channel itself fully. Thus, feedback reduction in multiuser multi-carrier systems becomes more of an issue due to the large amount of feedback required to pass to the base station. In this paper, we propose a novel feedback reduction scheme preserving the essential of multi-user diversity. In our proposed scheme, active users determine their feedback amount based on the feedback efficiency factor in a distributed manner. The objective is to reduce the feedback load remarkably while achieving almost the same performance to the full feedback condition. Our proposed scheme offers several advantages over existing ones. First, it does not distort the property of the scheduling policies. Second, total feedback load can be explicitly controlled to a target level regardless of the number of users in a system by adjusting each user's feedback load adaptively.

A scheduling problem is considered in the cellular network where there exist CBR (constant bit rate) users requiring exact minimum average throughput and delay guarantee, and EMG (elastic with minimum guarantee) users requiring minimum average throughput and delay guarantee and more throughput if possible. We first define a new utility function of average queue length. Based on the new queue utility function and the throughput utility function proposed before, we design a 2-dimensional weight function that will be used in our scheduling algorithm, and suggest a source control algorithm that can work with the scheduling algorithm. We show through simulations that the proposed algorithm guarantees the QoS (quality of service) requirements of CBR and EMG users.

We present a unified analytical framework that maximizes generalized utilities of a wireless network by network-wide opportunistic scheduling and power control. That is, base stations in the network jointly decide mobile stations to be served at the same time as the transmission powers of base stations are coordinated to mitigate the mutually interfering effect. Although the maximization at the first glance appears to be a mixed, twofold and nonlinear optimization requiring excessive computational complexity, we show that the maximization can be transformed into a pure binary optimization with much lower complexity. To be exact, it is proven that binary power control of base stations is necessary and sufficient for maximizing the network-wide utilities under a physical layer regime where the channel capacity is linear in the signal-to-interference-noise ratio. To further reduce the complexity of the problem, a distributed heuristic algorithm is proposed that performs much better than existing opportunistic algorithms. Through extensive simulations, it becomes clear that network-wide opportunistic scheduling and power control is most suitable for fairness-oriented networks and underloaded networks.

In this paper, dynamic subcarrier and power allocation problem is considered in the context of asymptotic utility maximization in multi-carrier systems. Using gradient-based resource allocation, we formulate an optimization problem involving subcarrier and transmit power allocation for each time slot, and propose an optimal algorithm solving the problem. Since the optimal algorithm is impractical due to its complexity, a simple suboptimal algorithm is also proposed based on generalized Benders decomposition. Furthermore, we identify the performance of equal power allocation policy by showing that equal power allocation is not always near optimal in general utility maximization problem and characterizing the optimality condition of equal power allocation. This result not only justifies the use of our dynamic power allocation, but also generalizes the performance of equal power allocation, which is well-known to be approximately optimal to the sum capacity maximization problem in high SNR (signal-to-noise ratio) regime. Our algorithms and analysis are verified through extensive simulations.

We present a network architecture for the distributed utility max-min flow control of elastic and nonelastic flows where utility values of users (rather than data rates of users) are enforced to achieve max-min fairness. The proposed link algorithm converges to utility max-min fair bandwidth allocation in the presence of round-trip delays without using the information of users' utility functions. To show that the proposed algorithm can be stabilized not locally but globally, we found that the use of nonlinear control theory is inevitable. Even though we use a distributed flow-control algorithm, it is shown that any kind of utility function can be used as long as the minimum slopes of the functions are greater than a certain positive value. Though our analysis is limited to the single-bottleneck and homogeneous-delay case, we believe that the proposed algorithm is the first to achieve utility max-min fairness with guaranteed stability in a distributed manner

In this paper, a scheduling problem is considered in the cellular network where there exist CBR (constant bit rate) users requiring exact minimum average throughput guarantee, and EMG (elastic with minimum guarantee) users requiring minimum average throughput guarantee and more if possible. We propose a combined scheduling and call admission control algorithm that exactly guarantees the minimum requirements of CBR and EMG users, and then allocates the leftover capacity to EMG users. The proposed algorithm is developed using utility maximization problem without minimum throughput constraints and newly defined utility functions. In the algorithm, it is easy to give priority to particular users so that their requirements are guaranteed prior to any other user. Moreover, the priority structure enables the proposed measurement-based call admission control algorithm to perform admission trial without affecting the minimum required throughput of ongoing users. We verify the performance of our algorithm through mathematical analysis and simulations.

This paper examines burst contention resolution problems in optical burst switching (OBS) networks. Since burst contentions take place (i) when the network is congested by increased input traffic, or (ii) two or more bursts demand the same wavelength exactly at the same time even though there is no congestion. From these insights, we present two novel methods that make higher throughputs and lower burst losses in the OBS network. First, from the viewpoint of flow control, we propose a burst flow control algorithm that controls the length of a burst based on the congestion price on its path. With the proposed flow control algorithm, the OBS network achieves improved efficiency and fairness compared to the case where a burst contention resolution scheme is solely used. Next, we develop an edge delay method which decreases burst losses especially when two or more bursts are overlapped in the core nodes. When some bursts need buffering to avoid contentions at core nodes, the proposed method makes them be delayed for the required buffering time at its ingress edge instead. Through extensive simulations, we demonstrate its performance.

This work was supported by the Ministry of Information and Communication, Korea, under the grant for BrOMA-ITRC program supervised by IITA.

In this paper, a scheduling problem in wireless networks is considered when there simultaneously exist CBR (constant bit rate) users requiring exact minimum average throughput guarantee and EMG (elastic with minimum guarantee) users requiring minimum average throughput guarantee and more if possible. By exploiting utility maximization problem without minimum throughput constraint and newly defined utility functions, we propose a combined scheduling and call admission control scheme that exactly guarantees the minimum requirements of CBR and EMG users and then allocates the leftover capacity to EMG users. In the proposed scheme, it is easy to give priority to particular users so that they are guaranteed their requirements prior to any other user. Moreover, the priority structure enables the proposed measurement-based call admission control algorithm to perform admission trial without affecting the minimum performance of existing users. We show through mathematical analysis and simulations that our scheme works as designed.

We present a network architecture for the distributed utility max-min flow control of elastic and non-elastic flows where utility values of users (rather than data rates of users) are enforced to achieve max-min fairness. We provide a distributed link algorithm that does not use the information of users' utility functions. To show that the proposed algorithm can be stabilized not locally but globally, we found that the use of nonlinear control theory is inevitable. Even though we use a distributed flow control algorithm, it is shown that any kind of utility function can be used as long as the minimum slopes of the functions are greater than a certain positive value. We believe that the proposed algorithm is the first to achieve utility max-min fairness with guaranteed stability in a distributed manner.

This paper focuses on low-power usages of mobile devices in WLAN (wireless local area network) environments. Recently, the researchers have been concentrating on power issues for long battery life. However, many of them consider only the MAC (medium access control) protocol. In this paper, we develop a resource allocation algorithm for low-power consumption without considering lower layer protocol. This algorithm provides fairness, efficiency and stability by using an optimization framework in mobile stations. We verify the efficiency of our algorithm by simulation using Intel Centrino/sup /spl trade// parameters, which shows the efficiency of our algorithm.

In most of research works on the wireless ad-hoc network, it is often assumed that all nodes in the network are cooperative to relay packets. However, it is natural for nodes to be reluctant to cooperate by force due to the consumption of resources. Thus, a concept of noncooperative ad-hoc networks is being widely accepted in the latest research works. For the noncooperative ad-hoc networks, a framework which stimulates nodes to mutually cooperate was proposed by W. Yuen. It was shown that the framework utilizes more net capacity of the network than the multi-hop cooperative ad-hoc network does by exploiting data diversity and eliminating redundant bandwidth wastes for the multi-hop packet relays. In this paper, we suggest a content dissemination protocol which adopts currency and we show that adopting currency outperforms the previously proposed one through extensive simulations

A fair allocation of utility (application-layer performance) is essential in providing QoS (quality of service) guarantee. However, there have been few researches in the literature of utility-fair network resource allocation scheme. In this paper, we propose a distributed utility max-min flow control algorithm which accommodates application diversity in that it does not require the concavity of utility functions, and is scalable in that it does not require any per-flow operation in the network. The algorithm is proved to be convergent under the assumption that there exists a single congested node and the communication delay between any two nodes in the network is bounded. Although the convergence of the algorithm is analyzed for the case of a single congested node, we show through simulations that the proposed algorithm works as designed for the case of multiple congested nodes.

This paper describes an analytical framework for the weighted max-min flow control of elastic flows in packet networks using PID and PII/sup 2/ controllers when flows experience heterogeneous round-trip delays (HRTD). Our algorithms are scalable in that routers do not need to store any per-flow information and they use a simple first come first serve (FCFS) discipline, and stable in that the stability is proven rigorously when there are flows with HRTD. We first suggest two closed-loop system models that approximate our flow control algorithms in the continuous-time domain where the purpose of the first algorithm is to achieve the target queue length and that of the second is to achieve the target utilization. The slow convergence of source rates traversing routers with empty buffers, which is inherent in many flow control algorithms, can be resolved by the second algorithm. Based on these models, we find the conditions for controller gains that stabilize the closed-loop systems when round-trip delays are equal and extend this result to the case of HRTD with the help of the zero exclusion theorem.

We present a distributed algorithm to compute the bandwidth max-min fair rates in a multi-rate multicast network. The significance of the algorithm, compared to previous algorithms (Sakar, S. and Tassiulas L., 1999, 2000; Kar, K. et al., 2001), is that it is more scalable (it does not require each link to maintain the saturation status of all sessions and virtual sessions travelling through it) it is more stable (it converges asymptotically to the desired equilibrium, satisfying the minimum plus max-min fairness, even in the presence of heterogeneous round-trip delays) and it has explicit link buffer control (the buffer occupancy of every bottlenecked link in the network asymptotically converges to the pre-defined value). In addition, we propose an efficient feedback consolidation algorithm which is computationally simpler than its hard-synchronization based counterpart and eliminates unnecessary consolidation delay by preventing it from awaiting backward control packets (BCPs) that do not directly contribute to the session rate. Through simulations, we verify the performance of the proposed multi-rate multicast flow control scheme based on these two algorithms.

Routers process packets and forward them to appropriate output ports. There are two resources that packets contest to acquire within a router; processing resource and bandwidth resource. Processing resource includes parsing the contents of a packet/header and do classification, lookup, checksum etc. Bandwidth resource indicates output bandwidth of a router. These two contested resources make up the two-dimensional resource allocation problem, which our MAX-MIN flow control algorithm addresses. We propose an intelligent explicit rate (ER) allocation algorithm based on the control-theoretic ER allocation algorithm. In the router model with two distinct resource constraints, at a given time, either one or both resources can be scarce. Depending on the scenario, our MAX-MIN flow control algorithm intelligently allocates resources using different adaptive operations for each steady state. The algorithm maintains per-flow state making it simple and scalable. At steady state, input flow rates and queue lengths asymptotically converge to a unique and fair equilibrium point. The fairness and intelligent adaptation is verified through simulation in the Intel IXP1200 Software Development Environment.

In this paper, conventional bandwidth allocation schemes in ethernet passive optical network (EPON) are shown to suffer from poor utilization under the nonuniform traffic, particularly as the number of ONUs, guard time and round-trip time increase. To resolve this problem, we propose a new scheme which intelligently allocates a timeslot in consideration of other ONUs' queue occupancy, instead of strictly enforcing maximum timeslot size. The analysis and simulation results show that the proposed scheme can provide significantly higher utilization than the conventional schemes and support max-min fairness under the nonuniform traffic.

In a wireless network, packet losses can be caused not only by network congestion but also by unreliable error-prone wireless links. Therefore, flow control schemes which use packet loss as a congestion measure cannot be directly applicable to a wireless network because congestion losses cannot be distinguished from wireless losses. We extend a so-called TCP-friendly flow control scheme, which was developed for the control of multimedia flows carried over UDP in the presence of TCP flows, to a wireless environment by using ECN (explicit congestion notification) marking capability with RED (random early detection) routers. By detecting congestion early, explicitly informing multimedia sources of congestion using ECN marking and calculating a TCP-friendly rate based on ECN-marked packet probability instead of packet loss probability, we are able effectively to separate the effect of wireless losses from flow control and thus prevent throughput degradation of multimedia flows traveling through wireless links. Also, we refine a well-known TCP throughput model developed for TCP-friendliness of multimedia flows such that the refined model provides more accurate estimate of TCP flows' throughput when both ECN marking and RED queue management are used. By simulation, we show that the proposed scheme does improve the quality of the delivered video significantly while maintaining TCP-friendliness for the case of wireless MPEG-4 video.

We present a novel control-theoretic explicit rate (ER) allocation algorithm for the max-min flow control of elastic traffic services with minimum rate guarantee in the context of the ATM ABR service. The proposed ER algorithm is simple in that the number of operations required to compute it at a switch is minimized, scalable in that per-VC (virtual circuit) operations including per-VC queueing, per-VC accounting and per-VC state management are virtually removed, and stable in that by employing it the user transmission rates and the network queues are asymptotically stabilized at a unique equilibrium point at which max-min fairness with minimum rate guarantee and target queue lengths are achieved respectively. To improve the speed of convergence we normalize the controller gains of the algorithm by the estimate of the number of locally-bottlenecked VCs. The estimation scheme is also computationally simple and scalable since it does not require per-VC accounting either. We analyze the theoretical performance of the proposed algorithm and verify its agreement with the practical performance through simulations in the case of multiple bottleneck nodes. We believe that the proposed algorithm will serve as an encouraging solution to the max-min flow control not only in the context of ATM ABR service but also in general elastic traffic services.

We present a novel service discipline, called linear service discipline, to serve multiple QoS queues sharing a resource and analyze its properties. The linear server makes the output traffic and the queueing dynamics of individual queues as a linear function of its input traffic. In particular, if input traffic is Gaussian, the distributions of queue length and output traffic are also Gaussian with their mean and variance being a function of input mean and input power spectrum (equivalently, autocorrelation function of input). Important QoS measures including buffer overflow probability and queueing delay distribution are also expressed as a function of input mean and input power spectrum. This study explores a new direction for networkwide traffic management based on linear system theories by letting us view the queueing process at each node as a linear filter.

We present a novel control-theoretic explicit rate (ER) allocation algorithm for the max-min flow control of elastic traffic services with minimum rate guarantee in the setting of the ATM available bit rate (ABR) service. The proposed ER algorithm is simple in that the number of operations required to compute it at a switch is minimized, scalable in that per-virtual-circuit (VC) operations including per-VC queueing, per-VC accounting, and per-VC state management are virtually removed, and stable in that by employing it, the user transmission rates and the network queues are asymptotically stabilized at a unique equilibrium point at which max-min fairness with minimum rate guarantee and target queue lengths are achieved, respectively. To improve the speed of convergence, we normalize the controller gains of the algorithm by the estimate of the number of locally bottlenecked VCs. The estimation scheme is also computationally simple and scalable since it does not require per-VC accounting either. We analyze the theoretical performance of the proposed algorithm and verify its agreement with the practical performance through simulations in the case of multiple bottleneck nodes. We believe that the proposed algorithm will serve as an encouraging solution to the max-min flow control of elastic traffic services, the deployment of which has been debated long due to their lack of theoretical foundation and implementation complexity.

Recently, a number of empirical studies have demonstrated the existence of long-range dependence (LRD) or self-similarity in VBR video traffic. Since previous LRD models cannot capture all short- and long-term correlation and rate-distribution while still retaining mathematical tractability, there exist many doubts on the importance of SRD, LED, and rate-distribution on traffic engineering. In this paper, we present a video traffic model based on the shifting-level (SL) process with an accurate parameter matching algorithm for video traffic. The SL process captures all those key statistics of an empirical video trace. Also, we devised a queueing analysis method of SL/D/1/K, where the system size at every embedded point is quantized into a fixed set of values, thus the name quantization reduction method. This method is different from previous LRD queueing results in that it provides queueing results over all range not just an asymptotic solution. Further, this method provides not only the approximation but also the bounds of the approximation for the system states and thus guarantees the accuracy of the analysis. We found that for most available traces their ACF can be accurately modeled by a compound correlation (SLCC): an exponential function in short range and a hyperbolic function in long range. Comparing the queueing performances with C-DAR(1), the SLCC, and real video traces identify the effects of SRD and LRD in VBR video traffic on queueing performance.

In this paper we present a method to establish real-time connections with guaranteed quality of service (QOS), based on a per-session probabilistic burstiness curve (PBC). Under two distinctive service disciplines, role proportional processor sharing and fixed rate processor sharing, we derive useful probabilistic bounds on per-session end-to-end loss which is caused by either buffer overflow in the path or excessive delay to the destination. One remarkable feature of the bounding solutions is that they are solely determined by the PBC of each session itself, independent of the network environment and other connections. To improve network resource utilization, our method is extended to allow statistical sharing of buffer resources. The admission control scheme presented in this paper has a great flexibility in connection management since bandwidth and buffer allocations can be adaptively adjusted among incoming and existing sessions according to present network resource availability. We also present a novel method to compute the PBC of multimedia traffic based on the measurement of two important statistics (rate histogram and power spectrum). Our study of MPEG/JPEG video sequences reveals the fundamental interrelationship among the PBC, the traffic statistics, and the QOS guarantee, and also provides many engineering aspects of the PBC approach to real-time multimedia services in ATM networks.

This paper presents a novel approach to dynamic transmission bandwidth allocation for transport of real-time variable-bit-rate video in ATM networks. Video traffic statistics are measured in the frequency domain. The low-frequency signal captures the slow time-variation of consecutive scene changes while the high-frequency signal exhibits the feature of strong frame autocorrelation. Our queueing study indicates that the video transmission bandwidth in a finite-buffer system is essentially characterized by the low-frequency signal. We further observe in typical JPEG/MPEG video sequences that the time scale of video scene changes is in the range of a second or longer, which localizes the low-frequency video signal in a well-defined low-frequency band. Hence, in a network design it is feasible to implement dynamic allocation of video transmission bandwidth using on-line observation and prediction of scene changes. Two prediction schemes are examined: recursive least square method and time delay neural network method. A time delay neural network with low-complexity high-order architecture, called "pi-sigma network," is successfully used to predict scene changes. The overall dynamic bandwidth-allocation scheme presented is shown to be promising and practically feasible in obtaining efficient transmission of real-time video traffic.>

We study link capacity allocation for a finite buffer system to transmit multimedia traffic. The queueing process is simulated with real video traffic. Two key concepts are explored in this study. First, the link capacity requirement at each node is essentially captured by its low-frequency input traffic (filtered at a properly selected cut-off frequency). Second, the low-frequency traffic stays intact as it travels through a finite-buffer system without significant loss. Hence, one may overlook the queueing process at each node for network-wide traffic flow in the low-frequency band. We propose a simple, effective method for link capacity allocation and network control using on-line observation of traffic flow in the low-frequency band. The study explores a new direction for measurement-based traffic control in high-speed networks.>

The paper presents a novel approach to dynamic transmission bandwidth allocation for transport of real-time variable-bit-rate video in ATM networks. The authors describe video traffic in the frequency domain: the low frequency signal captures the slow time-variation of consecutive scene changes; the high frequency signal exhibits the feature of strong frame autocorrelation. The study indicates that the video transmission bandwidth in a finite-buffer system is essentially characterized by the low, frequency signal. Since the time scale of scene changes is usually in the range of a second or longer, the low frequency video signal is defined in a well-founded low frequency band. Hence, it is feasible to implement dynamic allocation of video transmission bandwidth using on-line observation and prediction of scene changes. Two prediction schemes are examined: the recursive least square method vs. the time delay neural network method. A time delay neural network with low-complexity high-order architecture, called a "pi-sigma network", is successfully used to predict scene changes. The proposed dynamic bandwidth allocation scheme is shown to be promising and practically feasible in obtaining efficient transmission of real-time video traffic with guaranteed quality of services.>

The fundamental limits of input rate control by specific analysis in the frequency domain are explored. Both deterministic and stochastic analyses are developed. The simple deterministic analysis helps provide knowledge about the performance tradeoff for input rate control in a high-speed network.>