We design and build SkyHaul, the first large-scale, self-organizing network of Unmanned Aerial Vehicles (UAVs) that are connected using a mm Wave wireless mesh backhaul. While the use of a mmWave backhaul paves the way for a new class of bandwidth-intensive, latency-sensitive cooperative applications (e.g. LTE coverage during disasters), the network of UAVs allows these applications to be executed at operating ranges that are far beyond the line-of-sight distances that limit individual UAVs today.

RFID applications for taking inventory and processing transactions in point-of-sale (POS) systems improve operational efficiency but are not designed to provide insights about customers' interactions with products. We bridge this gap by solving the proximity grouping problem to identify groups of RFID tags that stay in close proximity to each other over time. We design DeepTrack, a framework that uses deep learning to automatically track the group of items carried by a customer during her shopping journey. This unearths hidden purchase behaviors helping retailers make better business decisions and paves the way for innovative shopping experiences such as seamless checkout (`a la Amazon Go). DeepTrack employs a recurrent neural network (RNN) with the attention mechanism, to solve the proximity grouping problem in noisy settings without explicitly localizing tags. We tailor DeepTrack's design to track not only mobile groups (products carried by customers) but also flexibly identify stationary tag groups (products on shelves). The key attribute of DeepTrack is that it only uses readily available tag data from commercial off-the-shelf RFID equipment. Our experiments demonstrate that, with only two hours training data, DeepTrack achieves a grouping accuracy of 98.18% (99.79%) when tracking eight mobile (stationary) groups.

Retailers are aiming to enhance customer experience by automating the checkout process. The key impediment here is the effort to manually align the product barcode with the scanner, requiring sequential handling of items without blocking the line-of-sight of the laser beam. While recent systems such as Amazon Go eliminate human involvement using an extensive array of cameras, we propose a privacy-preserving alternative, RFGo, that identifies products using passive RFID tags. Foregoing continuous monitoring of customers throughout the store, RFGo scans the products in a dedicated checkout area that is large enough for customers to simply walk in and stand until the scan is complete (in two seconds). Achieving such low-latency checkout is not possible with traditional RFID readers, which decode tags using one antenna at a time. To overcome this, RFGo includes a custom-built RFID reader that simultaneously decodes a tag's response from multiple carrier-level synchronized antennas enabling a large set of tag observations in a very short time. RFGo then feeds these observations to a neural network that accurately distinguishes the products within the checkout area from those that are outside. We build a prototype of RFGo and evaluate its performance in challenging scenarios. Our experiments show that RFGo is extremely accurate, fast and well-suited for practical deployment in apparel stores.

The recent innovation of frequency-shifted (FS) backscatter allows for backscattering with commodity devices, which are inherently half-duplex. However, their reliance on oscillators for generating the frequency-shifting signal on the tag, forces them to incur the transient phase of the oscillator before steady-state operation. We show how the oscillator's transient phase can pose a fundamental limitation for battery-less tags, resulting in significantly low bandwidth efficiencies, thereby limiting their practical usage.

We envision a flexible, dynamic airborne LTE infrastructure built upon Unmanned Autonomous Vehicles (UAVs) that will provide on-demand, on-time, network access, anywhere. In this paper, we design, implement and evaluate SkyRAN, a self-organizing UAV-based LTE RAN (Radio Access Network) that is a key component of this UAV LTE infrastructure network. SkyRAN determines the UAV's operating position in 3D airspace so as to optimize connectivity to all the UEs on the ground. It realizes this by overcoming various challenges in constructing and maintaining radio environment maps to UEs that guide the UAV's position in real-time. SkyRAN is designed to be scalable in that it can be quickly deployed to provide efficient connectivity even over a larger area. It is adaptive in that it reacts to changes in the terrain and UE mobility, to maximize LTE coverage performance while minimizing operating overhead. We implement SkyRAN on a DJI Matrice 600 Pro drone and evaluate it over a 90 000 m2 operating area. Our testbed results indicate that SkyRAN can place the UAV in the optimal location with about 30 secs of a measurement flight. On an average, SkyRAN achieves a throughput of 0.9 - 0.95X of optimal, which is about 1.5 - 2X over other popular baseline schemes.

The advent of LTE into the unlicensed spectrum has necessitated the understanding of its operational efficiency when sharing spectrum with different radio access technologies. Our study reveals that LTE, owing to its inherent transmission characteristics, suffers significant performance degradation in the presence of interference caused by hidden terminals. This motivates the need for interference-awareness in LTE's channel access in unlicensed spectrum. To address this problem, we propose ELI. ELI's three-pronged solution equips the LTE base station with novel techniques to: (a) accurately detect and measure interference caused by hidden terminals, (b) collect interference statistics from clients across different channels with affordable overhead, and (c) leverage interference-awareness to improve its channel access performance. Our evaluations show that ELI can achieve 1.5-2x throughput gains over baseline schemes. Finally, ELI is LTE-LAA/MulteFire-standard compliant and can be deployed over the existing LTE-LAA implementation without any modifications.

The advances in unmanned aerial vehicle (UAV) technology have empowered mobile operators to deploy LTE base stations (BSs) on UAVs, and provide on-demand, adaptive connectivity to hotspot venues as well as emergency scenarios. However, today's evolved packet core (EPC) that orchestrates the LTE RAN faces fundamental limitations in catering to such a challenging, wireless and mobile UAV environment, particularly in the presence of multiple BSs (UAVs). In this work, we argue for and propose an alternate, radical edge EPC design, called SkyCore that pushes the EPC functionality to the extreme edge of the core network - collapses the EPC into a single, light-weight, self-contained entity that is co-located with each of the UAV BS. SkyCore incorporates elements that are designed to address the unique challenges facing such a distributed design in the UAV environment, namely the resource-constraints of UAV platforms, and the distributed management of pronounced UAV and UE mobility. We build and deploy a fully functional version of SkyCore on a two-UAV LTE network and showcase its (i) ability to interoperate with commercial LTE BSs as well as smartphones, (ii) support for both hotspot and standalone multi-UAV deployments, and (iii) superior control and data plane performance compared to other EPC variants in this environment.

Deploying LTE networks in unlicensed spectrum requires us to move beyond coexistence mechanisms and understand the suitability of LTE's synchronous operation in a spectrum that is governed by asynchronous access principles. Our study reveals a fundamental conflict in LTE uplink access that arises between the scheduled nature of LTE's multi-user transmissions -- critical for leveraging the diversity (OFDMA) and multiplexing (multi-user MIMO) gains -- and the asynchronous nature of interference on the clients. The result is a significant loss in spectrum utilization and throughput that scales with the number of interfering terminals.

In this paper we formulate a general link packing problem for mmWave networks. Each link is a 4-tuple determined by the choice of receiving user, transmitting access point, transmit beamforming vector and receive beamforming vector. The problem seeks to optimize the weighted sum over active links, where each link is allowed to have any arbitrarily chosen weight or priority and an active link must satisfy a minimum link quality threshold. Our formulation models a practical scenario in which blockages due to arbitrarily placed obstacles in the propagation environment are allowed to occur, where we note that mmWave transmissions are extremely susceptible to blockages. This is a key departure from the classical link packing problem where only the signal attenuation based on propagation distance is modeled. We exploit the sparsity induced by the directional nature of propagation due to beamforming, limited diffraction and the significant signal attenuation due to high path, penetration losses. We propose a novel technique that exploits this sparsity and considers an alternate formulation which is a column-sparse binary packing problem. This alternate formulation is in general conservative and we derive sufficient conditions under which it is equivalent to the original problem. We construct an efficient iterative algorithm and show that it outperforms other heuristics and guarantees a constant factor approximation for input instances that are likely to occur in mmWave networks.

Evolved-Multimedia Broadcast Multicast Services (eMBMS) is a set of features in LTE networks to deliver bandwidth-intensive multimedia content on a point-to-multipoint basis to subscribers. The notion of a Single Frequency Network (SFN) in eMBMS allows base stations to synchronize and transmit signals in a coordinated fashion across the same frequency-time radio resources using a common modulation rate. While SFN boosts the channel quality of users via transmit diversity gain, the use of a common rate across base stations results in reduced utilization for those that can individually support much higher data rates for their users, even without the notion of an SFN. Excluding such base stations from the SFN helps them utilize their resources better by not being constrained by the common rate, but creates additional inter-cell interference from their independent transmissions. Striking a balance between SFN cooperation and resource utilization is crucial for efficiently delivering broadcast content as well as other unicast flows. We design BoLTE, which carefully addresses this tradeoff and evaluate it using a prototype implementation over an SFN testbed, realized over a cloud-based radio access network system, as well as large-scale NS3 simulations. We show that BoLTE improves overall system throughput by around 40%.

In this paper, we design and develop RIO, a novel battery-free touch sensing user interface (UI) primitive for future IoT and smart spaces. RIO enables UIs to be constructed using off-the-shelf RFID readers and tags, and provides a unique approach to designing smart IoT spaces. With RIO, any surface can be turned into a touch-aware surface by simply attaching RFID tags to them. RIO also supports custom-designed RFID tags, and thus allows specially customized UIs to be easily deployed into a real-world environment. RIO is built using the technique of impedance tracking: when a human finger touches the surface of an RFID tag, the impedance of the antenna changes. This change manifests as a change in the phase of the RFID backscattered signal, and is used by RIO to track fine-grained touch movement over both off-the shelf and custom built tags. We study this impedance behavior in-depth and show how RIO is a reliable UI primitive that is robust even within a multi-tag environment. We leverage this primitive to build a prototype of RIO that can continuously locate a finger during a swipe movement to within 3 mm of its actual position. We also show how custom-design RFID tags can be built and used with RIO, and provide two example applications that demonstrate its real-world use.

Growing demand for data and increasing number of devices are drastically changing the scale of operation in mobile networks. Future services and business models require efficient provisioning with enhanced traffic management. It is hard to meet these requirements on today's mobile networks that are deployed over specialized hardware. While operators are keen to adopt NFV (Network Function Virtualization) to virtualize their networks, virtualized mobile network deployments face a few technical barriers. To address these challenges, we design SCOPE that effectively applies concepts from SDN and distributed systems to realize NFV-based LTE core networks. Using centralized allocation, SCOPE effectively manages the resources across multiple telecom data-centers in a way to meet the traffic requirements. To enforce the computed al- locations, SCOPE includes flexible and efficient mechanisms to configure the data-plane. With full compliance to 3GPP- based protocols, SCOPE ensures faster and cost-effective deployments. The efficacy of SCOPE is shown using a prototype implementation and large-scale simulations.

We consider network utility maximization problems over heterogeneous cellular networks (HetNets) that permit dual connectivity. Dual connectivity (DC) is a feature that targets emerging practical HetNet deployments that will comprise of non-ideal (higher latency) connections between transmission nodes, and has been recently introduced to the LTE-Advanced standard. DC allows for a user to be simultaneously served by a macro node as well as one other (typically micro or pico) node and requires relatively coarser level coordination among serving nodes. For such a DC enabled HetNet we comprehensively analyze the problem of determining an optimal user association that maximizes the weighted sum rate system utility subject to per-user rate constraints, over all feasible associations. Here, in any feasible association each user can be associated with (i.e., configured to receive data from) any one macro node (in a given set of macro nodes) and any one pico node that lies in the chosen macro node's coverage area. We show that, remarkably, this problem can be cast as a non-monotone submodular set function maximization problem, which allows us to construct a constant-factor approximation algorithm. We then consider the proportional fairness (PF) system utility and characterize the PF optimal resource allocation. This enables us to construct an efficient algorithm to determine an association that is optimal up-to an additive constant. We then validate the performance of our algorithms via numerical results.

The proliferation of smartphones and tablet devices is changing the landscape of user connectivity and data access from predominantly static users to a mix of static and mobile users. While significant advances have been made in wireless transmission strategies (e.g., beamforming and network MIMO) to meet the increased demand for capacity, such strategies primarily cater to static users. To cope with growing heterogeneity in data access, it is critical to identify and optimize strategies that can cater to users of various profiles to maximize system performance and more importantly, improve users' quality of experience. Toward this goal, we first show that users can be profiled into three distinct categories based on their data access (mobility) and channel coherence characteristics. Then, with real-world experiments, we show that the strategy that best serves users in these categories varies distinctly from one profile to another and belongs to the class of strategies that emphasize either multiplexing (e.g., network MIMO), diversity (e.g., distributed antenna systems) or reuse (e.g., conventional CSMA). Two key challenges remain in translating these inferences to a practical system, namely: 1) how to profile users and 2) how to combine strategies to communicate with users of different profiles simultaneously. In addressing these challenges, we present the design of TRINITY-a practical system that effectively caters to a heterogeneous set of users. We implement and evaluate a prototype of TRINITY on our WARP radio testbed. Our extensive experiments show that TRINITY's intelligent combining of transmission strategies improves the total network rate by 50%-150%, satisfies the QoS requirements of thrice as many users, and improves PSNR for video traffic by 10 dB compared with individual transmission strategies.

There is widespread agreement that future continuous interactive (CI) applications will require edge computing capabilities from mobile networks. There is also widespread expectation that the emerging 5G network architecture, with its constituent technology components, will be the context in which this will be realized. Indeed many of the components that will be part of such an environment have been studied in standalone manner. However, the question of whether an end-to-end combination of these components would satisfy application requirements, or indeed, how these components would be combined into service offerings by mobile network providers, have not been meaningfully addressed. Towards addressing these challenges, we propose ACACIA - a service abstraction framework that enables CI applications on edge clouds in mobile networks. Evaluation of our prototype implementation shows that our holistic approach provides a 70% end-to-end application level latency reduction when compared with existing cloud and mobile solutions.

The static capacity provisioning in traditional WiFi networks (WLANs) cannot cope with the high spatiotemporal traffic variations in high-density venues such as conference centers, stadiums etc. To guarantee reliable performance, venue owners are forced to over-provision their WLANs based on worst-case traffic demand estimations, increasing capital and operational expenses. We propose AmorFi, a radically new way of deploying WLANs to handle peak traffic demands with average-case provisioning. Our key idea is to decouple baseband processing from RF transmission (inspired by the cloud-RAN concept in cellular networks) and introduce software programmability to flexibly allocate WiFi capacity in real time based on varying traffic demands. We implement AmorFi using off-the-shelf WiFi APs over a RF-over-fiber cloud-RAN testbed. Our experiments and simulations demonstrate that the software-defined capacity allocation enabled with AmorFi delivers more than $2x$ throughput than traditional WLANs.

We consider the problem of downlink scheduling in an LTE network powered by energy harvesting devices. We formulate optimization problems that seek to optimize two popular energy efficiency metrics subject to mandatory LTE network constraints along with energy harvesting causality constraints. We identify a key sub-problem pertaining to maximizing the weighted sum rate that is common for both optimization problems, and is also of independent interest. We show that the latter sub-problem can be reformulated as a constrained submodular set function maximization problem. This enables us to design constant-factor approximation algorithms for maximizing the weighted sum rate as well as the two energy efficiency metrics over an energy harvesting LTE downlink. Our proposed algorithms are simple to implement and offer superior performance.

In this work, we explore the potential and impact of unlicensed LTE on WiFi in unlicensed spectrum. Our experiments demonstrate that the large asymmetry in the channel access methodologies employed by WiFi and LTE (carrier sensing/notification in WiFi, energy sensing alone in LTE-U), can result LTE-U completely blocking WiFi transmissions, and causing significant degradation to either technologies from collisions.

We propose Acacia- a service abstraction framework that enables continuous interactive (CI) applications on edge clouds in mobile networks. We will demonstrate the Acacia architecture and illustrate its feasibility by using an augmented reality application as an example use case.

Small cells form a critical component of next generation cellular networks, where spatial reuse is the key to higher spectral efficiencies. Interference management in the spatial domain through beamforming allows for increased reuse without having to sacrifice resources in the time or frequency domain. Existing beamforming techniques for spatial reuse, being coupled with client scheduling, face a key limitation in practical realization, especially with OFDMA small cells. In this context, we argue that for a practical spatial reuse system with beamforming, it is important to decouple beamforming from client scheduling. Further, we show that jointly addressing client association with beamforming is critical to maximizing the reuse potential of beamforming. Towards our goal, we propose ProBeam - a system for multi-cell beamforming and client association in OFDMA small cell networks. ProBeam incorporates two key components - a low complexity, highly accurate SINR estimation module that helps determine interference dependencies for beamforming between small cells; and an efficient, low complexity joint client association and beam selection algorithm for the small cells that accounts for scheduling at the small cells without being coupled with it. We have prototyped ProBeam on a WiMAX-based network of four small cells. Our evaluations reveal the accuracy of our SINR estimation module to be within 1 dB, and the reuse gains from joint client association and beamforming to be as high as 115 percent over baseline approaches.

Beamforming is a signal processing technique with numerous benefits in wireless communication. Unlike traditional omnidirectional communication, it focuses the energy of the transmitted and/or the received signal in a particular direction. Although beamforming has been extensively studied on conventional systems such as WiFi, little is known about its practical impact on performance in orthogonal frequency-domain multiple access (OFDMA) small-cell deployments. Since OFDMA schedules multiple clients (users) in the same frame in contrast to WiFi, designing intelligent scheduling mechanisms and at the same time leveraging beamforming is a challenging task. Unlike downlink, we show that the integration of beamforming with uplink scheduling projects an interesting tradeoff between beamforming gain on the one hand, and the power-pooling gain resulting from joint multiuser scheduling on the other hand. This, in turn, makes the uplink scheduling problem even hard to approximate. To address this, we propose algorithms that are simple to implement, yet provably efficient with a worst-case guarantee of 1/2. We implement our algorithms on a real WiMAX small-cell platform integrated with an eight-element phased-array beamforming antenna. Evaluations from both prototype implementation and trace-driven simulations show that the algorithms deliver throughput gains of over 40% compared to an omnidirectional scheme.

Cloud-based radio access networks (C-RAN) have been proposed as a cost-efficient way of deploying small cells. Unlike conventional RANs, a C-RAN decouples the baseband processing unit (BBU) from the remote radio head (RRH), allowing for centralized operation of BBUs and scalable deployment of light-weight RRHs as small cells. In this work, we argue that the intelligent configuration of the front-haul network between the BBUs and RRHs, is essential in delivering the performance and energy benefits to the RAN and the BBU pool, respectively. We propose FluidNet-a scalable, light-weight framework for realizing the full potential of C-RAN. FluidNet deploys a logically re-configurable front-haul to apply appropriate transmission strategies in different parts of the network and hence cater effectively to both heterogeneous user profiles and dynamic traffic load patterns. FluidNet's algorithms determine configurations that maximize the traffic demand satisfied on the RAN, while simultaneously optimizing the compute resource usage in the BBU pool. We prototype FluidNet on a 6 BBU, 6 RRH WiMAX C-RAN testbed. Prototype evaluations and large-scale simulations reveal that FluidNet's ability to re-configure its front-haul and tailor transmission strategies provides a 50% improvement in satisfying traffic demands, while reducing the compute resource usage in the BBU pool by 50% compared to baseline schemes.

Power line communications (PLC) offer an immediate means of providing high bandwidth connectivity in settings where there is no in-built network infrastructure. While there is recent work on understanding physical and MAC layer artifacts of PLC, its applicability and performance in multi-flow settings is not well understood. We first undertake an extensive measurement study that sheds light on the properties of PLC that significantly affect performance in multi-flow settings. Using the understanding gained, we design BOLT, a framework that adopts a learning-based approach to effectively manage and orchestrate flows in a PLC network. BOLT is flexible and is agnostic to standards; it can be used to implement scheduling algorithms that target different performance goals. We implement BOLT on three different testbeds using off-the-shelf PLC adapters and showcase its ability to effectively manage flows, delivering several folds throughput improvement over state-of-the-art solutions.

In addition to growth of data traffic, mobile networks are bracing for a significant rise in the control-plane signaling. While a complete re-design of the network to overcome inefficiencies may help alleviate the effects of signaling, our goal is to improve the design of the current platform to better manage the signaling. To meet our goal, we combine two key trends. Firstly, mobile operators are keen to transform their networks with the adoption of Network Function Virtualization (NFV) to ensure economies of scales. Secondly, growing popularity of cloud computing has led to advances in distributed systems. In bringing these trends together, we solve several challenges specific to the context of telecom networks. We present SCALE - A framework for effectively virtualizing the MME (Mobility Management Entity), a key control-plane element in LTE. SCALE is fully compatible with the 3GPP protocols, ensuring that it can be readily deployed in today's networks. SCALE enables (i) computational scaling with load and number of devices, and (ii) computational multiplexing across data centers, thereby reducing both, the latencies for control-plane processing, and the VM provisioning costs. Using an LTE prototype implementation and large-scale simulations, we show the efficacy of SCALE.

In recent years, we have experienced many initiatives in developing smart cities across the world. In these densely populated cities, video surveillance will play an integral role to ensure the safety of the citizens. The major challenge will be to transport high volumes of data generated from dense deployment of video cameras throughout the city to a central aggregation facility for analysis and storage. To address this problem, we propose a system solution using existing public bus transit system to collect data from the cameras and physically transport it to the bus terminus, to be uploaded to the data center. The system uses heterogeneous wireless network interfaces, where the camera nodes form a mesh network to route the data to the nearest bus stop for offloading. We utilize high capacity links using mmWave devices at bus stops to offload the data to the buses when they make routine stops. We also propose a novel routing protocol, R2H, to route the data generated from these cameras to a bus stop while minimizing the time to offload the video data to an incoming bus. The protocol is designed to be aware of the various challenges that are specific to this system like bus schedule and video payload. We have evaluated our system using wireless experiments and simulation using actual bus route maps and times from New York city area. Our analysis shows that R2H achieves 60% less end to end delay compared to OLSR under varying video payload and time of the day.

We investigate the open problem of characterizing the multiplexing gain offered by FD in a network of M cells (compared to the gain of two available on a single link). While self-interference cancellation is fundamental in realizing full duplex (FD) capability, the more challenging problem in a network-wide deployment of FD communication is a new form of uplink-downlink interference, namely UDI, caused by transmission of uplink clients on the downlink reception of other clients operating in the same frequency band during FD. We leverage spatial interference alignment (IA) as an effective approach to address UDI and characterize the scalability of the FD's multiplexing gain (in terms of M) by providing a closed-form expression. To the best of our knowledge, this is the first characterization of FD's multiplexing gain in a multi-cell network. We also provide an IA construction that can achieve the best scaling possible. Further, we extend our results to practical settings with limited number of clients and limited information sharing between access points.

Large-scale multiuser MIMO (MU-MIMO) systems have the potential for multi-fold scaling of network capacity. The research community has recognized this theoretical potential and developed architectures [1,2] with large numbers of RF chains. Unfortunately, building the hardware with a large number of RF chains is challenging in practice. CSI data transport and computational overhead of MU-MIMO beamforming can also become prohibitive under large network scale. Furthermore, it is difficult to physically append extra RF chains on existing communication equipments to support such large-scale MU-MIMO architectures.

To handle increased capacity demands, sophisticated MIMO-based transmission strategies, based on transmitter cooperation, have emerged. However, different types of users' channels (e.g., static vs mobile, stable vs dynamic channels) that make up today's enterprises, require different MIMO transmission strategies. With the wrong strategy, a user could even see a degradation in performance. Our overarching goal is to design and implement a framework, TRINITY, that can simultaneously cater to a heterogeneous mix of users, by intelligently combining a plurality of MIMO transmission strategies wherein the transmitters at different nodes can cooperate to deliver significant performance gains. Three key challenges that we address in building TRINITY are: (i) how to categorize users into channel profiles such that a single transmission strategy caters to the users of a profile, (ii) how to combine strategies to communicate with users of different profiles simultaneously, and (iii) what is the granularity of transmitter cooperation needed to balance efficiency with complexity. We implement and evaluate TRINITY on our WARP radio testbed. Our extensive experiments show that TRINITY's intelligent combining of transmission strategies improves the total network rate by 50%-150%, satisfies the QoS requirements of thrice as many users, and improves PSNR for video traffic by 10 dB compared to individual transmission strategies.

We analyze Coordinated Multi-Point (CoMP) transmission and reception over heterogeneous wireless networks (HetNets). Our focus is on the design of a practical algorithm for joint resource allocation (joint scheduling) in each HetNet cluster. We present one such algorithm together with its detailed analysis and evaluation under two different approaches for obtaining and utilizing channel feedback from the users. The considered approaches as well as the evaluation methodology are fully compliant with the 3GPP LTE standard. Our evaluations reveal several important insights that are essential to achieve significant CoMP gains over HetNets.

The growing demand for data has driven the Service Providers (SPs) to provide differential treatment of traffic to generate additional revenue streams from Content Providers (CPs). While SPs currently only provide best-effort services to their CPs, it is plausible to envision a model in near future, where CPs are willing to sponsor quality of service for their content in exchange of sharing a portion of their profit with SPs. In this paper, we introduce the problem of Quality-Sponsored Data (QSD) in cellular networks and study its implications on market entities in various scenarios. The direct coupling between the scarce wireless resources and the market decisions resulting from QSD is taken into account. In our model, SPs make a portion of their resources available for sponsorship by CPs, and price it appropriately to maximize their payoff, which depends on the monetary revenue and the satisfaction of end-users both for the non-sponsored and sponsored content, while CPs generate revenue through advertisement. We analyze the market dynamics and equilibria, and provide strategies for (i) SPs: to determine if and how to price resources, and (ii) CPs: to determine if and what quality to sponsor. We also discuss about the effects of different parameters of the model on market dynamics.

We consider the problem of maximizing the alphafairness utility over the downlink of a heterogeneous wireless network (HetNet) by jointly optimizing the association of users to transmission points (TPs) and the activation fractions of all TPs. Activation fraction of each TP is the fraction of the frame duration for which it is active, and together these fractions influence the interference seen in the network. To address this joint optimization problem we adopt an approach wherein the activation fractions and the user associations are optimized in an alternating manner. The sub-problem of determining the optimal activation fractions is solved using an auxiliary function method that we show is provably convergent and is amenable to distributed implementation. On the other hand, the sub-problem of determining the user association is solved via a simple combinatorial algorithm. Meaningful performance guarantees are derived and a distributed variant offering identical guarantees is also proposed. The significant benefits of using the proposed algorithms are then demonstrated via realistic simulations.

Next generation WLANs (802.11ac) are undergoing a major shift in their communication paradigm with the introduction of multi-user MIMO (MU-MIMO), transitioning from single-user to multi-user communications. We argue that the conventional AP deployment model of co-located antennas as well as their PHY and MAC mechanisms are not designed to realize the complete potential of MU-MIMO. We propose to leverage distributed antenna systems (DAS) to empower next generation 802.11ac networks. We highlight the multitude of benefits that DAS brings to MU-MIMO and 802.11ac in general. However, several challenges arise in the process of realizing these benefits in practice, where avoiding client modifications and making only minimal software modifications to APs is important to enable rapid adoption. Towards addressing these challenges, we present the design and implementation of MIDAS, the Multiple-Input Distributed Antenna System. MIDAS couples a DAS deployment of AP antennas with a suite of novel yet standards-compatible mechanisms at the PHY and MAC layers that best leverage the DAS deployment to maximize 802.11ac performance. Our WARP-based experimental evaluation demonstrates MIDAS's ability to significantly boost the performance of current 802.11ac design, demonstrating throughput gains over 802.11ac MU-MIMO for 100-200%, while remaining amenable to commercial adoption.

We consider the problem of maximizing the proportional fairness (PF) utility over heterogeneous wireless networks (HetNets) by jointly exploiting cell dormancy (cell ON-OFF) - wherein some transmission nodes from a set of interest are made inactive - and load balancing (user association) - wherein users are associated to the active transmission nodes in that set with each user being associated with only one node. We establish that this joint optimization problem which is a discrete optimization problem, is strongly NP-hard. Nevertheless, we prove that the load balancing sub-problem for any given set of active transmission nodes is not NP-hard but instead can be re-formulated as an asymmetric assignment problem and hence can be optimally solved in an efficient manner. In addition, we propose another lower complexity greedy algorithm for the load balancing sub-problem which offers a near-optimal average-case performance and a worst-case performance guarantee. We then propose a low-complexity algorithm for the joint optimization problem. Simulations over an example LTE HetNet topology reveal the superior performance of the proposed algorithms and underscore the significant benefits of jointly exploiting cell dormancy and load balancing.

In this paper, we consider the design of user grouping and scheduling for large-scale multiple-input multiple-output (MIMO) frequency-division-duplexing (FDD) systems. Based on a recently proposed two-stage precoding framework, we first propose an improved K-means user grouping scheme which allocates the users to different pre-beamforming groups using the second-order channel statistics, and then a user grouping scheme that considers both load balancing and precoding design. After user groups are so determined, we present a dynamic user scheduling scheme where second-stage precoding is designed based on instantaneous channel conditions. We demonstrate the efficacy of the proposed schemes through simulations.

Device-to-device (D2D) communications is being pursued as an important feature in next generation cellular networks. D2D can improve resource utilization in two ways: Offloading cellular traffic to D2D, and Reuse of resources used by conventional cellular transmissions for D2D communication. In this paper, we show that in multi-cell environments that employ FFR (Fractional Frequency Reuse), the benefits from D2D toward reuse are limited. We then propose R2D2- a holistic approach to efficient offloading with D2D traffic. R2D2 leverages the flexible nature of D2D traffic (in using downlink/uplink resources) to cater effectively to the spatial and temporal asymmetry in traffic load both across and within cells. R2D2 incorporates a two time-scale solution: a coarse time-scale dynamic FFR scheme that leverages D2D traffic to determine the FFR patterns for downlink and uplink jointly among interfering sectors; and a fine time-scale scheduling solution that intelligently schedules cellular and D2D traffic jointly across DL (Downlink) and UL (Uplink) resources. We establish the hardness of the scheduling problem and present efficient and low complexity algorithms with approximation guarantees. Through extensive evaluations, we confirm that R2D2 delivers the offloading benefits of D2D, with its proposed algorithms performing very close to the optimal.

We consider the problem of maximizing the proportional fairness (PF) utility over heterogeneous cellular networks (HetNets) by jointly exploiting partial muting-wherein the high power macro transmission node in a set of transmission nodes of interest can be made inactive for a specified fraction of the available time-frequency resource- and load balancing (user association)-wherein each user can be associated to (i.e., configured to receive data from) any one transmission node in that set. This joint problem is a mixed optimization problem in which there are finitely many choices for the muting fraction and the user association, but there are a continuum of ways in which each transmission node can partition the available resource among the users associated to it. While this mixed optimization problem seems intractable, we systematically construct efficient approximation algorithms, one of which is approximately optimal in that it yields a system utility that is no less than the optimal utility minus a constant. In addition, we propose another lower complexity greedy algorithm and proceed to demonstrate the superior performance of the proposed algorithms via simulations over an example LTE HetNet topology.

Mobile operators are leveraging WiFi to relieve the pressure posed on their networks by the surging bandwidth demand of applications. However, operators often lack intelligent mechanisms to control the way users access their WiFi networks. This lack of sophisticated control creates poor network utilization, which in turn degrades the quality of experience (QoE). To meet user traffic demands, it is evident that operators need solutions that optimally balance user traffic across cellular and WiFi networks. Motivated by the lack of practical solutions in this space, we design and implement ATOM - an end-to-end system for adaptive traffic offloading for WiFi-LTE deployments. ATOM has two novel components: (i) A network interface selection algorithm that maps user traffic across WiFi and LTE to optimize user QoE and (ii) an interface switching service that seamlessly re-directs ongoing user sessions in a cost-effective and standards-compatible manner. Our evaluations on a real LTE-WiFi testbed using YouTube traffic reveals that ATOM reduces video stalls by 3-4 times compared to naive solutions.

Enabling wireless full-duplex (from an AP) with multiple half-duplex (HD) clients is key to widespread adoption of full-duplex (FD) in commercial networks. However, enabling FD in such networks is fundamentally challenged by a new form of uplink-downlink interference (UDI), arising between HD clients operating simultaneously in the uplink and downlink directions. In this context, we first show that spatial interference alignment (IA) between clients is an effective and scalable technique to address UDI and hence enable FD in these networks, especially in the presence of MIMO.

With the growing demand for increased spectral efficiencies, there has been renewed interest in enabling full-duplex communications. However, existing approaches to enable full-duplex require a clean-slate approach to address the key challenge in full-duplex, namely self-interference suppression. This serves as a big deterrent to enabling full-duplex in existing cellular networks. Towards our vision of enabling full-duplex in legacy cellular, specifically LTE networks, with no modifications to existing hardware at BS and client as well as technology specific industry standards, we present the design of our experimental system FD-LTE, that incorporates a combination of passive SI cancellation schemes, with legacy LTE half-duplex BS and client devices. We build a prototype of FD-LTE, integrate it with LTE's evolved packet core and conduct over-the-air experiments to explore the feasibility and potential for full-duplex with legacy LTE networks. We report promising experimental results from FD-LTE, which currently applies to scenarios with limited ranges that is typical of small cells.

The classical definition of degrees of freedom (DoF) deals with the degrees of a communication channel or multiple communication channels in the limit of high SNR. This can be interpreted as the number of independent streams that can be sent in each communication channel in the high SNR regime. We introduce the concept of DoF per communication node where at a transmitting node the DoF is the number of independent dimensions that can be used for transmission and at each receiver node the DoF is the number of independent dimensions that can be used for receiving data signals. In general the communication channels or links in a network can be divided into two sets: the interfering channels and the intended channels; hence, the network may be considered as an overlay of two networks, respectively: the interfering network and data-intended network. In the classical form, DoF is defined for channels in the data-intended network. We illustrate a new interpretation of DoF that depends only on the interfering network and can be formalized in full generality based on degrees of freedom per node in the network. While the classical DoF has been studied generally in the context of interference and X-channels, the per node DoF concept generalizes the idea to other possible networks. Using this generalized notion of DoF, this paper provides new results on DoF for different networks and also makes a connection to the classical definition of DoF defined in interference and X-channels.

The articles in this special issue focus on the technology and applications supported by in-band full duplex wireless services.

In-band full-duplex (IBFD) operation has emerged as an attractive solution for increasing the throughput of wireless communication systems and networks. With IBFD, a wireless terminal is allowed to transmit and receive simultaneously in the same frequency band. This tutorial paper reviews the main concepts of IBFD wireless. One of the biggest practical impediments to IBFD operation is the presence of self-interference, i.e., the interference that the modem's transmitter causes to its own receiver. This tutorial surveys a wide range of IBFD self-interference mitigation techniques. Also discussed are numerous other research challenges and opportunities in the design and analysis of IBFD wireless systems.

We consider the problem of maximizing the proportional fairness (PF) system utility over heterogeneous wireless networks (HetNets) by jointly exploiting cell dormancy (cell ON-OFF)-wherein some transmission points from a set of interest can be made inactive-and load balancing (user association)-wherein users are associated to the active transmission points in that set, with each user being associated with only one point. We establish that this joint optimization problem, which is a discrete optimization problem, is NP-hard. Nevertheless, we prove that the load balancing subproblem for any given set of active transmission points is not NP-hard but instead can be reformulated as an asymmetric assignment problem and hence can be optimally solved in an efficient manner. In addition, we show that some generalized load balancing problems that incorporate multiuser diversity gains can also be optimally and efficiently solved. We propose another lower complexity greedy algorithm for the load balancing subproblem that offers a worst-case performance guarantee and describe a simple way to approximately realize a given input user association via biasing factors. We then derive low-complexity algorithms for the joint optimization problem, including one based on a successive approximation method that has hitherto been used for continuous nonconvex optimization problems. Simulations over an example Long-Term Evolution HetNet topology reveal the superior performance of the proposed algorithms and underscore the significant benefits of jointly exploiting cell dormancy and load balancing.

In this paper, we consider resource allocation in the 3GPP Long Term Evolution (LTE) cellular uplink (UL), which will be the most widely deployed next generation cellular uplink. The key features of the 3GPP LTE uplink are that it is based on a modified form of the orthogonal frequency division multiplexing-based multiple access (OFDMA), which enables channel dependent frequency selective scheduling, and that it allows for multiuser (MU) scheduling wherein multiple users can be assigned the same time-frequency resource. In addition to the considerable spectral efficiency improvements that are possible by exploiting these two features, the LTE UL allows for transmit antenna selection together with the possibility to employ advanced receivers at the base-station, which promise further gains. However, several practical constraints that seek to maintain a low signaling overhead are also imposed. In this paper, we show that the resulting resource allocation problem is APX-hard and then propose a local ratio test (LRT)-based constant-factor polynomial-time approximation algorithm. We then propose two enhancements to this algorithm as well as a sequential LRT-based MU scheduling algorithm that offers a constant-factor approximation and is another useful choice in the complexity versus performance tradeoff. Further, user preselection, wherein a smaller pool of good users is preselected and a sophisticated scheduling algorithm is then employed on the selected pool, is also examined. We suggest several such user preselection algorithms, some of which are shown to offer constant-factor approximations to the preselection problem. Detailed evaluations reveal that the proposed algorithms and their enhancements offer significant gains.

The demand for real-time video services coupled with the need for increased spectral efficiencies has brought a lot of attention to video multicasting in next generation OFDMA systems. Layered video provides an efficient solution to address the channel quality variation across users. However, the frequency selectivity across sub-channels introduced by OFDMA serves as a drawback for multicast scheduling. This significantly diminishes the benefits of video layering and can potentially degrade the system performance to worse than that without channel diversity. Layering the PHY with the help of multi-resolution modulation serves as an effective tool to help retain channel diversity and leverage the benefits of layered video. While layering the PHY provides benefits to multicast in general, we show that its benefits are much more significant in a system with channel diversity. The corresponding multicast scheduling problem now becomes all the more challenging with multi-resolution modulation. In addressing this problem, we provide efficient scheduling solutions both for systems with and without channel diversity. Our solutions have provable performance guarantees and are amenable to practical implementation. Further, evaluation in realistic scenarios reveals close to optimal performance of our proposed solutions as well as the large benefits obtained by layering the PHY in OFDMA systems with channel diversity.

With the next-generation cellular networks making a transition toward smaller cells, two-hop orthogonal frequency-division multiple access (OFDMA) relay networks have become a dominant, mandatory component in the 4G standards (WiMAX 802.16j, 3GPP LTE-Adv). While unicast flows have received reasonable attention in two-hop OFDMA relay networks, not much light has been shed on the design of efficient scheduling algorithms for multicast flows. Given the growing importance of multimedia broadcast and multicast services (MBMS) in 4G networks, the latter forms the focus of this paper. We show that while relay cooperation is critical for improving multicast performance, it must be carefully balanced with the ability to multiplex multicast sessions and hence maximize aggregate multicast flow. To this end, we highlight strategies that carefully group relays for cooperation to achieve this balance. We then solve the multicast scheduling problem under two OFDMA subchannelization models. We establish the NP-hardness of the scheduling problem even for the simpler model and provide efficient algorithms with approximation guarantees under both models. Evaluation of the proposed solutions reveals the efficiency of the scheduling algorithms as well as the significant benefits obtained from the multicasting strategy.

Although wireless broadband technologies have evolved significantly over the past decade, they are still insufficient to support the fast-growing mobile traffic, especially due to the increasing popularity of mobile video applications. Wireless multicast, aiming to exploit the wireless broadcast advantage, is a viable approach to bridge the gap between the limited wireless capacity and the ever-increasing mobile video traffic demand. In this paper, we propose MuVi, a Multicast Video delivery scheme through joint optimal resource allocation and adaptive modulation and coding scheme in OFDMA-based 4G cellular networks. MuVi differentiates video frames based on their importance in reconstructing the video and incorporates an efficient radio resource allocation algorithm to optimize the overall video quality across all users in the multicast group. MuVi is a lightweight solution with most of the implementation in the gateway, slight modification in the base station, and no modification at the clients. We implement MuVi on a WiMAX testbed and compare its performance to a Naive wireless multicast scheme that employs the most robust Modulation and Coding Scheme (MCS), and an Adaptive scheme that employs the highest MCS supportable by all clients. Experimental results show that MuVi improves the average video peak signal-to-noise ratio (PSNR) by up to 13 and 7 dB compared to the Naive and the Adaptive schemes, respectively. MuVi does not require modification to the video encoding scheme or the air interface. Thus, it allows speedy deployment in existing systems.

Heterogeneous wireless networks are formed when a set of disparate transmission points serve a multitude of users over an available spectrum. In order to enable efficient resource allocation over such networks, the set of transmission points is partitioned into multiple clusters and each cluster is assigned a set of users that it must serve. Our contribution in this paper is the design of an approximation algorithm for the resource allocation in each cluster. We show that this resource allocation problem is strongly NP-hard and that our algorithm yields a constant factor approximation, for a fixed cluster size. Our evaluations over a realistic heterogeneous network model show that significant gains can be realized by our algorithm, provided the feedback available from the users is fully exploited.

Mobile operators are witnessing a dramatic increase in traffic spurred by a combination of popularity of smartphones, innovative applications and diverse services. As mobile traffic transitions from being voice dominated to video and data dominated, the revenue per byte for the mobile operators is declining at an unhealthy rate. To counter the traffic growth and build cost-effective networks, many operators are now forging alliances for RAN (Radio Access Network) sharing to improve coverage and capacity at reasonable investments and operational costs. This paper presents the design and implementation of NetShare, a network-wide radio resource management framework that provides effective RAN Sharing. NetShare introduces a novel two-level scheduler split between the mobile gateway and the cellular basestations to effectively manage and allocate the wireless resources of the radio access network composed of multiple basestations among multiple different entities (such as operators, content providers, etc.) that share the network. Firstly, NetShare provides performance isolation across entities with a minimum guaranteed resource allocation to each entity across the network. Secondly, NetShare optimally distributes the resources to each entity across the network proportional to the resource demand at each basestation. Through extensive LTE-based system simulations and prototype evaluations on a WiMAX testbed, we show the efficacy of NetShare in (a) providing isolation across entities and (b) efficiently distributing resources for each entity across the network thus achieving high utilization of resources for an entity.

Carrier aggregation (CA) is an important feature of next generation cellular networks (LTE-advanced, LTE-A) that allows its users to aggregate upto 100 MHz of (dis-)contiguous spectral chunks to provide increased data rates. While the conventional approach of allowing LTE-A users to be configured on all component carriers, results in maximum diversity gain for scheduling, it also increases the users' power consumption and processing that scale with the number of component carriers. In light of the growing need to minimize energy consumption on mobile devices, we argue that it is possible to operate the LTE-A users on a small subset of component carriers to reduce their energy consumption, without any appreciable loss to the scheduling gain. A key step in realizing this goal however, is to address the joint problem of component carrier selection as well as scheduling and in turn forms the focus of this work. We highlight the hardness of the joint problem when the number of component carriers that can be activated for an LTE-A user is limited. Towards solving the problem, we consider various models that incorporate both contiguous and dis-contiguous CA as well as backlogged and finite user buffers and propose efficient, greedy algorithms with performance guarantees that are also simple to implement. Our evaluations based on LTE system parameters, reveal that our algorithms help realize 80-90% of the maximum scheduling gain with just half the component carriers and provide a 25% throughput gain over baseline load and signal power based carrier selection schemes.

Small cells have become an integral component in meeting the increased demand for cellular network capacity. Cloud radio access networks (C-RAN) have been proposed as an effective means to harness the capacity benefits of small cells at reduced capital and operational expenses. With the baseband units (BBUs) separated from the radio access units (RAUs) and moved to the cloud for centralized processing, the backhaul between BBUs and RAUs forms a key component of any C-RAN. In this work, we argue that a one-one mapping of BBUs to RAUs is highly sub-optimal, thereby calling for a functional decoupling of the BBU pool from the RAUs. Further, the backhaul architecture must be made re-configurable to allow the mapping between BBUs and RAUs to be flexible and changed dynamically so as to not just optimize RAN performance but also energy consumption in the BBU pool. Towards this end, we design and implement the first OFDMA-based C-RAN test-bed with a reconfigurable backhaul that allows 4 BBUs to connect flexibly with 4 RAUs using radio-over-fiber technology. We demonstrate the feasibility of our system over a 10 km separation between the BBU pool and RAUs. Further, real world experiments with commercial off-the-shelf WiMAX clients reveal the performance benefits of our reconfigurable backhaul in catering effectively to heterogeneous user (static and mobile clients) and traffic profiles, while also delivering energy benefits in the BBU pool.

As the growth of mobile video traffic outpaces that of cellular network speed, industry is adopting HTTP-based adaptive video streaming technology which enables dynamic adaptation of video bit-rates to match changing network conditions. However, recent measurement studies have observed problems in fairness, stability, and efficiency of resource utilization when multiple adaptive video flows compete for bandwidth on a shared wired link. Through experiments and simulations, we confirm that such undesirable behavior manifests itself in cellular networks as well. To overcome these problems, we design an in-network resource management framework, AVIS, that schedules HTTP-based adaptive video flows on cellular networks. AVIS effectively manages the resources of a cellular base station across adaptive video flows. AVIS also provides a framework for mobile operators to achieve a desired balance between optimal resource allocation and user quality of experience. AVIS has three key differentiating features: (1) It optimally computes the bit-rate allocation for each user, (2) It includes a scheduler and per-flow shapers to enforce bit-rate stability of each flow and (3) It leverages the resource virtualization technique to separate resource management of adaptive video flows from regular video flows. We implement a prototype system of AVIS and evaluate it on both a WiMAX network testbed and a LTE system simulator to show its efficacy and scalability.

Cloud-based radio access networks (C-RAN) have been proposed as a cost-efficient way of deploying small cells. Unlike conventional RANs, a C-RAN decouples the baseband processing unit (BBU) from the remote radio head (RRH), allowing for centralized operation of BBUs and scalable deployment of light-weight RRHs as small cells. In this work, we argue that the intelligent configuration of the front-haul network between the BBUs and RRHs, is essential in delivering the performance and energy benefits to the RAN and the BBU pool, respectively. We then propose FluidNet - a scalable, light-weight framework for realizing the full potential of C-RAN. FluidNet deploys a logically re-configurable front-haul to apply appropriate transmission strategies in different parts of the network and hence cater effectively to both heterogeneous user profiles and dynamic traffic load patterns. FluidNet's algorithms determine configurations that maximize the traffic demand satisfied on the RAN, while simultaneously optimizing the compute resource usage in the BBU pool. We prototype FluidNet on a 6 BBU, 6 RRH WiMAX C-RAN testbed. Prototype evaluations and large-scale simulations reveal that FluidNet's ability to re-configure its front-haul and tailor transmission strategies provides a 50% improvement in satisfying traffic demands, while reducing the compute resource usage in the BBU pool by 50% compared to baseline transmission schemes.

Network MIMO (netMIMO) has potential for significantly enhancing the capacity of wireless networks with tight coordination of access points (APs) to serve multiple users concurrently. Existing schemes realize netMIMO by integrating distributed APs into one ``giant'' MIMO but do not scale well owing to their global synchronization requirement and overhead in sharing data between APs. To remedy this limitation, we propose a novel system, NEMOx, that realizes netMIMO downlink transmission for large-scale wireless networks. NEMOx organizes a network into practical-size clusters, each containing multiple distributed APs (dAPs) that opportunistically synchronize with each other for netMIMO downlink transmission. Inter-cluster interference is managed with a decentralized channel-access algorithm, which is designed to balance between the dAPs' cooperation gain and spatial reuse---a unique tradeoff in netMIMO. Within each cluster, NEMOx optimizes the power budgeting among dAPs and the set of users to serve, ensuring fairness and effective cancellation of cross-talk interference. We have implemented and evaluated a prototype of NEMOx in a software radio testbed, demonstrating its throughput scalability and multiple folds of performance gain over current wireless LAN architecture and alternative netMIMO schemes.

Small cells form a critical component of next generation cellular networks, where spatial reuse is the key to higher spectral efficiencies. Interference management in the spatial domain through beamforming allows for increased reuse without having to sacrifice resources in the time or frequency domain. Existing beamforming techniques for spatial reuse, being coupled with client scheduling, face a key limitation in practical realization, especially with OFDMA small cells. In this context, we argue that for a practical spatial reuse system with beamforming, it is important to decouple beamforming from client scheduling. Further, we show that jointly addressing client association with beamforming is critical to maximizing the reuse potential of beamforming.

In this paper, we consider the design of a scheduling algorithm for downlink multiuser systems with a finite-buffer traffic model to reduce average packet delay, while maintaining the stability condition of the networks. We propose a new Buffer-Aware Adaptive (BAA) scheduler which considers both channel state and buffer conditions for resource allocation. The generalized form of the proposed algorithm is also established. Stability considerations of the proposed algorithm are provided, along with the average throughput lower bound and approximation. Both single-link and system-level simulation results demonstrate that the proposed scheduler appears to outperform existing scheduling algorithms in terms of average packet delay.

While conventional cognitive radio (CR) system is striving at providing best possible protections for the usage of primary users (PU), little attention has been given to ensure the quality of service (QoS) of applications of secondary users (SU). When loading real-time applications over such a CR system, we have found that existing spectrum sensing schemes create a major hurdle for real-time traffic delivery of SU. For example, energy detection based sensing, a widely used technique, requires possibly more than 100 ms to detect a PU with weak signals. The delay is intolerable for real-time applications with stringent QoS requirements, such as voice over internet protocol (VoIP) or live video chat. This delay, along with other delays caused by backup channel searching, channel switching, and possible buffer overflow due to the insertion of sensing periods, makes supporting real-time applications over CR system very difficult if not impossible. In this paper, we present the design and implementation of a sensing-based CR system - RECOG, which is able to support realtime communications among SUs. We first redesign the conventional sensing scheme. Without increasing the complexity or trading off the detection performance, we break down a long sensing period into a series of shorter blocks, turning a disruptive long delay into negligible short delays. To enhance the sensing capability as well as better protect the QoS of SU traffic, we also incorporate an on-demand sensing scheme based on MAC layer information. In addition, to ensure a fast and reliable switching when PU returns, we integrate an efficient backup channel scanning and searching component in our system. Finally, to overcome a potential buffer overflow, we propose a CR-aware QoS manager. Our extensive experimental evaluations validate that RECOG can not only support realtime traffic among SUs with high quality, but also improve protections for PUs.

We present the design and implementation of ADAM, the first adaptive beamforming-based multicast system and experimental framework for indoor wireless environments. ADAM addresses the joint problem of adaptive beamformer design at the PHY layer and client scheduling at the MAC layer by proposing efficient algorithms that are amenable to practical implementation. ADAM is implemented on a field programmable gate array (FPGA) platform, and its performance is compared against that of omnidirectional and switched beamforming based multicast. Our experimental results reveal that: 1) switched multicast beamforming has limited gains in indoor multipath environments, whose deficiencies can be effectively overcome by ADAM to yield an average gain of threefold; 2) the higher the dynamic range of the discrete transmission rates employed by the MAC hardware, the higher the gains in ADAM's performance, yielding up to ninefold improvement over omni with the 802.11 rate table; and 3) finally, ADAM's performance is susceptible to channel variations due to user mobility and infrequent channel information feedback. However, we show that training ADAM's signal-to-noise ratio (SNR)-rate mapping to incorporate feedback rate and coherence time significantly increases its robustness to channel dynamics.

We consider Multi-User MIMO (MU-MIMO) scheduling in the 3GPP LTE-Advanced (3GPP LTE-A) cellular uplink. The 3GPP LTE-A uplink allows for precoded multi-stream (precoded MIMO) transmission from each scheduled user and also allows flexible multi-user (MU) scheduling wherein multiple users can be assigned the same time-frequency resource. However, exploiting these features is made challenging by certain practical constraints that have been imposed in order to maintain a low signaling overhead. We show that while the scheduling problem in the 3GPP LTE-A cellular uplink is NP-hard, it can be formulated as the maximization of a submodular set function subject to one matroid and multiple knapsack constraints. We then propose constant-factor polynomial-time approximation algorithms and demonstrate their superior performance via simulations.

This paper investigates the issue of how to balance the tradeoff between sensing performance and sensing costs/rewards for cooperative sensing in a multichannel cognitive radio system. Two cases of practical interest are studied. In the first case, the number of available sensors is assumed to be sufficient for detecting available frequency channels. For this case, we study the problem of selecting appropriate sensors to minimize the cost of detecting all the available channels subject to sensing performance constraints. The problem can be solved by using a branch-and-bound algorithm. In the second case, the number of available sensors is assumed to be insufficient for detecting all the available channels. For this case, we study the problem of selecting appropriate channels to maximize the sensing rewards subject to sensing performance constraints. Since the computational complexity of solving this problem optimally is fairly high, we propose a greedy algorithm as a low complexity solution to the problem. We further validate the effectiveness of the proposed algorithm via Monte-Carlo simulations.

This paper considers the design of linear transmit precoding schemes to minimize the weighted sum delay metric over a K-user multi-antenna multicast channel. Limited by the rank and power constraints, the precoding matrices are designed under two interesting scenarios. The first scenario assumes the availability of pilots that can be precoded, using which the transmitter can convey any choice of transmit precoders to the users. Consequently, the sought transmit precoders can be any complex-valued matrices subject to given rank (dimensionality) and power (norm) constraints. A provably convergent cyclic alternating ascent based algorithm is proposed for a relaxed version of the problem, and is shown to attain at least a stationary point. Assuming that no such pilots are available, the second scenario constrains the transmit precoders to lie in a finite codebook. A concatenation based approach is adopted for constructing higher rank precoding matrices, which can facilitate the precoder search and allow for efficient signaling. A simple deterministic algorithm is proposed which involves maximizing a submodular rate function per step, and yields a worst-case performance guarantee.

The proliferation of smartphones and tablet devices is changing the landscape of user connectivity and data access from predominantly static users to a mix of static and mobile users. While significant advances have been made in wireless transmission strategies (e.g., network MIMO) to meet the increased demand for capacity, such strategies primarily cater to static users. To cope with growing heterogeneity in data access, it is critical to identify and optimize strategies that can cater to users of various profiles to maximize system performance and more importantly, improve users' quality of experience.

In this paper, we consider the downlink (DL) multiuser (MU) multi-input-multi-output (MIMO) scheduling for the fourth generation LTE Advanced (LTE-A) cellular networks. The DL MU-MIMO scheduling can be posed as an optimization problem to maximize the weighted sum rate subject to several practical constraints, such as a per-user rank constraint. Due to these constraints finding the optimal solution becomes an NP-hard problem. Consequently, we propose an efficient albeit sub-optimal rank balancing approach that enforces the peruser rank constraint and present several rank balancing based scheduling algorithms. We show that the proposed algorithms are guaranteed to yield constant-factor approximations. Simulation results demonstrate that the proposed rank balancing based scheduling algorithms outperform other competing schemes over various relevant system scenarios.

Coordinated Multi-Point (CoMP) transmission is emerging as a concept that can substantially suppress interference, thus improving the capacity of multi-cell wireless networks. However, existing CoMP techniques either require sharing of data and channel state information (CSI) for all links in the network, or have limited capability of interference suppression. In this paper, we propose distributed interference alignment and cancellation (DIAC) to overcome these limitations. DIAC builds on a key intuition of interference locality — since each link is interfered with a limited number of neighboring links, it is sufficient to coordinate with those strong interferers and ignore others, in order to bound the overhead in CoMP. DIAC realizes the localized coordination by integrating interference cancellation and distributed interference alignment, and can be applied to both the uplink and downlink of multi-cell wireless networks. We validate DIAC using both model-driven and trace-based simulation where the traces are collected by implementing a MIMO-OFDM channel estimator on a software radio platform. Our experiments show that DIAC can substantially improve the degrees of freedom in multi-cell wireless networks.

In LTE and LTE-Advanced uplink, the interference power in a cell depends on the user scheduling and power assignment in neighboring cells. As a result, it is hard to accurately estimate the signal-to-interference-plus-noise ratio (SINR) values and make the right MCS (Modulation and Coding Scheme) selection. To address this challenge, we propose open-loop and closed-loop power control schemes to reduce both the average and the variance of the interference power in order to improve the system performance. It is shown that compared to the existing fractional power control (FPC) in LTE, the proposed schemes improve the cell-average throughput by 7-8% while maintaining the same cell-edge throughput in networks with low penetration loss, and improve the cell-average throughput by 4-6% and the cell-edge throughput by 15-23% in networks with high penetration loss.

This paper studies the design of linear precoders via instantaneous rate maximization over a K-user multicast channel, wherein multiple antennas are present at the transmitter as well as at all the receivers. We first consider the scenario wherein the linear precoder can be any complex valued matrix subject to rank and power constraints. Recognizing the resulting optimization problem to be NP-hard, we propose a cyclic alternating ascent based algorithm and establish its convergence to a stationary point. Simulation results reveal that our proposed algorithm considerably outperforms known competing solutions. We then consider a scenario in which the linear precoder can be formed by selecting and concatenating codewords from a finite codebook of precoding matrices, subject to rank and power constraints. We show that under this scenario, the instantaneous rate maximization problem is equivalent to a robust submodular maximization problem which is strongly NP-hard. We then propose a deterministic approximation algorithm and show that it yields a bicriteria approximation.

We present the design and implementation of ADAM, the first adaptive beamforming based multicast system and experimental framework for indoor wireless environments. ADAM addresses the joint problem of adaptive beamformer design at the PHY layer and client scheduling at the MAC layer by proposing efficient algorithms that are amenable to practical implementation. ADAM is implemented on an FPGA platform and its performance is compared against that of omni-directional and switched beamforming based multicast. Our experimental results reveal that (i) switched multicast beamforming has limited gains in indoor multi-path environments, whose deficiencies can be effectively overcome by ADAM to yield an average gain of three-fold; (ii) the higher the dynamic range of the discrete transmission rates employed by the MAC hardware, the higher the gains in ADAM's performance, yielding upto nine-fold improvement over omni with the 802.11 rate table; and (iii) finally, ADAM's performance is susceptible to channel variations due to user mobility and infrequent channel information feedback. However, we show that training ADAM's SNR-rate mapping to incorporate feedback rate and coherence time significantly increases its robustness to channel dynamics.

The ability of relay networks to improve capacity and coverage has led to their adoption in next generation wireless broadband networks (WiMAX, LTE-advanced). Unlike conventional cellular networks, there is a multitude of design features that impacts the performance of these relay networks. This has consequently increased the need for efficient scheduling algorithms to optimize such design features. The focus of this work is to improve relay network throughput through adaptive resource usage in the form of two key design features - (i) adaptive frame segmentation, and (ii) spatial reuse - that are allowed by the relay standard. To this end, we design efficient scheduling algorithms that optimize these two features jointly. We provide both algorithms with performance guarantees as well as those with fast running times. Our study reveals that with the help of properly designed scheduling algorithms, adaptive resource usage can (i) boost the network throughput performance by up to 50%; and (ii) optimize network throughput effectively, providing an effect similar to dynamic relay placement.

Scheduling plays a vital role in LTE downlink systems with Multiple Input and Multiple Output (MIMO) antennas. We consider the MIMO downlink scheduling problem at the base station (BS) in LTE networks under several practical constraints mandated by the 3GPP standards. We Define a new construct called transmission mode, which denotes a particular choice of MIMO operational mode, precoding matrix, transmission rank, as well as the modulation and coding schemes (MCSs) of up to two codewords and show that both LTE systems require that each scheduled user be served using only one transmission mode in every subframe. We prove that the resulting scheduling problems are NP-hard under both backlogged and finite queue traffic models, and then develop a unified low-complexity greedy algorithm that yields solutions guaranteed to be within 1/2 of the respective optima. Extensive performance evaluation in realistic settings reveals near-optimal performance of our proposed algorithm and that it significantly outperforms the state of the art, especially under the more practical, finite queue model.

Given that full duplex (FD) and MIMO both employ multiple antenna resources, an important question that arises is how to make the choice between MIMO and FD? We show that optimal performance requires a combination of both to be used. Hence, we present the design and implementation of MIDU, the first MIMO full duplex system for wireless networks. MIDU employs antenna cancellation with symmetric placement of transmit and receive antennas as its primary RF cancellation technique. We show that MIDU's design provides large amounts of self-interference cancellation with several key advantages: (i) It allows for two stages of additive antenna cancellation in tandem, to yield as high as 45 dB self-interference suppression; (ii) It can potentially eliminate the need for other forms of analog cancellation, thereby avoiding the need for variable attenuator and delays; (iii) It easily scales to MIMO systems, therefore enabling the coexistence of MIMO and full duplex. We implemented MIDU on the WARP FPGA platform, and evaluated its performance against half duplex (HD)-MIMO. Our results reveal that, with the same number of RF chains, MIDU can potentially double the throughput achieved by half duplex MIMO in a single link; and provide median gains of at least 20% even in single cell scenarios, where full duplex encounters inter-client interference. Based on key insights from our results, we also highlight how to efficiently enable scheduling for a MIDU node.

Although wireless broadband technologies have evolved significantly over the past decade, they are still insufficient to support the fast-growing mobile traffic, especially due to the increasing popularity of mobile video applications. Wireless multicast, aiming to exploit the wireless broadcast advantage, is a viable approach to bridge the gap between the limited wireless networking capacity and the ever-increasing mobile video traffic demand. In this work, we propose MuVi, a Multicast Video delivery scheme in OFDMA-based 4G wireless networks, to optimize multicast video traffic. MuVi differentiates video frames based on their importance in reconstructing the video and incorporates an efficient radio resource allocation algorithm to optimize the overall video quality across all users in the multicast group. MuVi is a lightweight solution with most of the implementation in the gateway, slight modification in the base-station, and no modification at the clients. We implement MuVi on a WiMAX testbed and compare its performance to a Naive wireless multicast scheme that employs the most robust MCS (Modulation and Coding Scheme), and an Adaptive scheme that employs the highest MCS supportable by all clients. Experimental results show that MuVi improves the average video PSNR (Peak Signal-to-Noise Ratio) by up to 13 and 7 dB compared to the Naive and the Adaptive schemes, respectively. MuVi does not require modification to the video encoding scheme or the air interface. Thus it allows speedy deployment in existing systems.

Beamforming is a signal processing technique with numerous benefits. Unlike with omni-directional communications, it focuses the energy of the transmitted and/or the received signal in a particular direction. Although beamforming has been extensively studied on conventional systems such as WiFi, little is known about its practical impact on OFDMA femtocell deployments. Since OFDMA schedules multiple clients (users) in the same frame (in contrast to WiFi), designing intelligent scheduling mechanisms and at the same time leveraging beamforming, is a challenging task.

Discrete Fourier transform (DFT) based channel estimation (CE) has been widely studied as a practical CE scheme over the OFDM based wireless systems. The conventional DFT-based channel estimation utilizes a transform domain cut-off filter to suppress the noise in the time domain. However, this method can suffer significant performance loss due to the channel impulse response (CIR) energy leakage, especially when the available pilot sub-carriers are confined to a small portion of the system bandwidth. In this paper, we propose an enhanced DFT-based channel estimation technique for the long term evolution (LTE) based cellular uplink. A sinc-null based noise power estimation method in conjunction with a dynamic noise removal technique is proposed to suppress the noise in the time domain and achieve better performance while keeping the complexity in check. Simulation results show that the proposed scheme not only achieves better mean square error (MSE) and block error rate (BLER) performance but also exhibits robustness to timing offsets compared to existing DFT based CE schemes.

In a cognitive radio (CR) network, cooperative spectrum sensing is a viable sensing technique to enhance spectral utilisation efficiency of secondary users (SUs) while ensuring the quality of service (QoS) of primary users (PUs). Intuitively, the more SUs are involved in sensing, the more sensing accuracy the CR can achieve, whereas the more sensing overhead the SUs consume, the less throughput the CR network can achieve. In this study, the authors investigate overhead-throughput trade-off over Rayleigh-fading channels in a cooperative CR network that consists of a number of the SUs employing energy detectors and a single decision fusion centre. Considering the trade-off, the authors prove that there is an optimal set of the sensing length and the number of SUs that maximise the throughput of an SU network. They further extend their analysis to a two-stage cooperative sensing mechanism where the second-stage fine sensing is triggered whenever any SU reports the presence of a PU after the first-stage detection. Numerical results showed that compared with the single-stage sensing, the two-stage sensing scheme achieves higher throughput via a reduction of the false alarm probability.

This paper describes the design and implementation of a network virtualization substrate (NVS) for effective virtualization of wireless resources in cellular networks. Virtualization fosters the realization of several interesting deployment scenarios such as customized virtual networks, virtual services, and wide-area corporate networks, with diverse performance objectives. In virtualizing a base station's uplink and downlink resources into slices, \ssrNVSmeets three key requirements-isolation, customization, and efficient resource utilization-using two novel features: 1)NVSintroduces a provably optimal slice scheduler that allows existence of slices with bandwidth-based and resource-based reservations simultaneously; and 2)NVSincludes a generic framework for efficiently enabling customized flow scheduling within the base station on a per-slice basis. Through a prototype implementation and detailed evaluation on a WiMAX testbed, we demonstrate the efficacy of \ssrNVS. For instance, we show for both downlink and uplink directions that \ssrNVScan run different flow schedulers in different slices, run different slices simultaneously with different types of reservations, and perform slice-specific application optimizations for providing customized services.

Future mobile broadband networks are characterized with high data rate and improved coverage, which will enable real-time video multicast and broadcast services. Scalable video coding (SVC), combined with adaptive modulation and coding schemes (MCS) and wireless multicast, provides an excellent solution for streaming video to heterogeneous wireless devices. By choosing different MCSs for different video layers, SVC can provide good video quality to users in good channel conditions while maintaining basic video quality for users in bad channel conditions. A key issue to apply SVC to wireless multicast streaming is to choose appropriate MCS for each video layer and to determine the optimal resource allocation among multiple video sessions. We formulate this problem as total utility maximization, subject to the constraint of available radio resources. We prove that the formulated problem is NP-hard and propose an optimal, two-step dynamic programming solution with pseudo-polynomial time complexity. Simulation results show that our algorithm offers significant improvement on the video quality over a naive algorithm and an adapted greedy algorithm, especially in the scenarios with multiple real video sequences and limited radio resources.

Using beamforming antennas to improve wireless multicast transmissions has received considerable attention recently. A recent work proposes to partition all single-lobe beams into groups and to form composite multilobe beam patterns to transmit multicast traffic. Depending on how the power is split among the individual beams constituting a composite beam pattern, two power models are considered: 1) equal power split (EQP), and 2) asymmetric power split (ASP). This paper revisits the key challenge-beam partitioning in the beamforming-multicast problem-and makes significant progress in both algorithmic and analytic aspects of the problem. Under EQP, we propose a low-complexity optimal algorithm based on dynamic programming. Under ASP, we prove that it is NP-hard to have (3/2-ϵ)-approximation algorithm for any ϵ >; 0. For discrete rate functions under ASP, we develop an Asymptotic Polynomial-Time Approximation Scheme (APTAS), an asymptotic (3/2+ β)-approximation solution (where β ≥ 0 depends on the wireless technology), and an asymptotic 2-approximation solution to the problem by relating the problem to a generalized version of the bin-packing problem. In retrospect, we also obtain an asymptotic 2-approximation solution for the generalized bin-packing problem, which is of independent interest. For continuous rate functions under ASP, we develop sufficient conditions under which the optimal number of composite beams is 1,K, and arbitrary, respectively, whereKis the total number of single-lobe beams. Both experimental results and simulations based on real-world channel measurements corroborate our analytical results by showing significant improvement compared to state-of-the-art algorithms.

One of the major challenges in cognitive radio networks is to maintain the quality of service (QoS) for secondary transmissions while ensuring the protection of primary users PUs); the latter requirement is normally enabled through inband spectrum sensing. To maintain QoS of secondary traffic, a secondary user (SU) has to quickly switch to another empty spectrum band when a PU returns to its currently occupied spectrum by SU. The issue of how to quickly and accurately identify a free spectrum band when the operating spectrum band becomes unavailable is of practical interest; out-of-band spectrum sensing is a mechanism that can be leveraged for this purpose. In this paper, we propose a novel progressive out-of-band spectrum sensing (PG-Sensing) scheme that consists of two components, 1) progressive scanning which adaptively selects a subset of the available candidate spectrum bands which have a higher chance of being empty, and 2) multiband sequential shifted chi-squared test (SSCT) based searching that searches only the set of selected spectrum bands in the first step. The proposed PGsensing scheme significantly reduces the time to resume secondary transmissions thus allowing SUs to reliably and quickly switch to a free spectrum band when necessary while maintaining good QoS for PUs as well as SUs.

We consider a downlink multi-user multi-input-multi-output (MU-MIMO) fading channel wherein the base station can schedule several user terminals on the same time-frequency resource. A severe practical problem in MU-MIMO is that when computing its feedback report, a user does not have an accurate estimate of the interference it might see (if scheduled) from the signals intended for the other co-scheduled users. This results in a mismatch between the user reported signal-to-interference-plus-noise-ratio (SINR) and the one it actually observes in the aftermath of scheduling. To alleviate this problem we propose to inform each user (in a slow or semi-static manner) about the rank of the precoding matrix that it should report, along with an estimate of the total number of streams that the base station expects to co-schedule on a time-frequency resource. The suggested rank and the expected total number of streams can be user-specific and together convey the expected total number of co-scheduled interfering streams to the intended user. Each user then computes one or more SINRs for all the precoding matrices having the suggested rank and reports its preferred precoding matrix along with the corresponding SINRs. The SINRs are computed after assuming that the co-scheduled interfering streams will be transmitted along vectors isotropically distributed in the orthogonal complement of the range of the precoding matrix being examined. Alternatively, the SINRs can be computed after assuming that the co-scheduled interfering streams will be transmitted along the worst-case choice of mutually orthogonal vectors that lie in the orthogonal complement. We show that the proposed solutions, while requiring negligible additional signalling overhead, mitigate the mismatch problem to a large extent and result in significant improvements in system throughput.

In this paper, we consider resource allocation in the the fourth generation multi antenna (4G MIMO) cellular uplink. In particular, we consider the two 4G standards, IEEE 802.16m and 3GPP LTE-A, that have recently been approved. We show that the uplink resource allocation problems in both 802.16m and LTE-A networks are NP-hard. We then propose constant-factor polynomial-time approximation algorithms for both these problems. We also provide linear programming (LP) based upper bounds to benchmark the performance of our proposed approximation algorithms. Simulations reveal that the proposed algorithms have excellent performance, much superior to their worst-case guarantees.

In this paper, we consider the design of a binary network coding scheme for the wireless broadcast, in which the same packet sequence is broadcasted to multiple receivers. In the proposed coding scheme, a short block code is employed for the coding across the broadcasted packets to generate redundant packets to recover the lost packets for all terminals in the service. In particular, we assume the optimal decoder and consider the design of short block codes with a small number of redundancy. We present a residual graph based code design method and propose an iterative design algorithm with stochastic update. The short block code is then extended with an improved pseudo-random code to achieve the flexibility on redundancy. Numerical results show that the proposed coding scheme provides superior performance over other coding schemes.

Recent works have considered the feasibility of full duplex (FD) wireless communications in practice. While the first FD system by Choi et.al. relied on a specific antenna cancellation technique to achieve a significant portion of self-interference cancellation, the various limitations of this technique prompted latter works to move away from antenna cancellation and rely on analog cancellation achieved through channel estimation. However, the latter systems in turn require the use of variable attenuator and delay elements that need to be automatically tuned to compensate for the self-interference channel. This not only adds complexity to the overall system but also makes the performance sensitive to wide-band channels. More importantly, none of the existing FD schemes can be readily scaled to MIMO systems.

In this paper, an efficient closed-loop link adaption scheme consisting of adaptive modulation and coding as well as adaptive precoding is proposed for the 3GPP LTE-A uplink. The uplink envisaged in the LTE-A cellular network will support precoded multi-rank transmission from the users and have base stations with advanced non-linear receivers. Our proposed scheme considers one such advanced receiver, namely, the turbo successive interference cancelation (Turbo-SIC) receiver. The main difficulty in designing link adaptation schemes for these advanced non-linear receivers is that the soft-outputs of such receivers cannot be simply modeled using a scalar Gaussian channel characterized by a signal-to-interference-plus-noise ratio (SINR). To circumvent this difficulty, we employ SINRs corresponding to an ordered hard-decision SIC receiver, that can be explicitly expressed in closed form. The proposed scheme accurately predicts the turbo SIC performance and results in a perfect match between the predicted and actually simulated performance in terms of block error rate (BLER) and the spectrum efficiency. Realistic and extensive simulations reveal that it provides the highest actual spectrum efficiency compared to other competing schemes.

In this paper we investigate the issue of exploiting switched beamforming antennas to improve multicast transmission in wireless networks. Under the practical assumptions that different beams may have arbitrary overlapping patterns and that each user can receive data at different rates under different beams, we formulate the problem as minimizing the total multicast delay subject to the constraint that all users need to be covered. We prove that the problem is NP-hard and propose a greedy algorithm that achieves log(J) approximation guarantee where J is the number of clients. Measurements in both indoor and outdoor experiments validate our assumptions on the beamforming model. Trace-driven simulations based on these measurements show significant improvement over previous schemes and corroborate our analytical results.

This paper studies the robust weighted-sum rate optimization problem in the presence of channel uncertainty over a K-user Gaussian Interference Channel (GIFC), where multiple antennas are present at all transmitters and receivers. Motivated by recent results on interference alignment that show the optimality of linear precoders and simple receivers in achieving the maximum degrees-of-freedom available in the GIFC, we consider linear transmit precoding and two simple decoding schemes: single-stream decoding and single-user decoding. The resulting precoder design problems are then posed as specific optimization problems. Unfortunately, due to the hardness of these problems, optimal solutions cannot be efficiently obtained. Instead of resorting to ad-hoc algorithms, we show that it is possible to design algorithms using a systematic approach. Towards this end, this paper develops new provably convergent iterative algorithms for precoder design through ingenious sub-problem formulations such that each of these sub-problems can be solved optimally. The sub-problems are solved in closed-form for certain cases and formulated as standard convex problems for the rest. To complement these contributions on achievable schemes, we generalize the genie-MAC outer bounding technique to incorporate channel uncertainty using notions of compound-MAC capacity and then obtain computable outer bounds using an alternating optimization approach. Thus, we introduce one of the first approaches to obtain tighter outer bounds on the capacity region of the GIFC in the presence of channel uncertainty.

Wireless multicast based video delivery is constrained by the user with the lowest channel quality within a multicast group. Beamforming increases the SINR at the clients thereby increasing the minimum channel quality among the users that form the multicast group. Thus it can be utilized to enhance the wireless multicast video transmission. In this paper, we investigate how to exploit switched beamforming antennas to improve wireless multicast based video transmission in indoor environments. The fundamental problem to be solved is the selection and scheduling of beams to be used to cover different subsets of users within the multicast group. We consider both multi-resolution videos and multi-layered videos and formulate the problem as maximizing the total utility of all multicast clients subject to a total delay constraint, where the utility is a general measure of video quality or user-satisfaction. We prove that it is NP-hard to have a (1-1/e+ε)-approximation solution to this problem for any ε >; 0, under both multi-resolution and multi-layered video models. For the multi-resolution video model, we develop a unified approximation algorithm with a parameter k that controls both the algorithm complexity and the approximation factor. For k = 0, 1, 2, 3, we prove that the proposed algorithm achieves an approximation guarantee close to 0.31, 0.38, 0.55, and 0.63, respectively. For the multi-layered video model, we propose a similar heuristic solution. The proposed algorithms are evaluated with both hypothetical video sequences and real video sequences using channel data collected in an indoor wireless testbed. Evaluation results show that the proposed algorithms have much better performance than naive multicast algorithms for scheduling the beams.

Using beamforming antennas to improve wireless multicast transmissions has received considerable attention recently. The work in proposes to partition all single-lobe beams into groups and to form composite multi-lobe beam patterns to transmit multicast traffic. The key challenge left is, how to partition the beams into multiple groups in order to minimize the total multicast delay. This work makes significant progress in both algorithmic and analytic aspects of the problem. We prove that, under the asymmetric power split (ASP) model, it is NP-hard to have (3/2 - ε)-approximation algorithm for any ε >; 0. We then develop an APTAS, an asymptotic (3/2 + β)-approximation solution (where β ≥ 0 depends on the wireless technology), and an asymptotic 2-approximation solution to the problem by relating the problem to a generalized version of the bin-packing problem. Extensive trace-driven simulations based on real-world channel measurements corroborate our analytical results by showing significant improvement compared to state of the art algorithms.

The increasing popularity of applications involving group communications in wireless networks has led to the need for efficient multicasting solutions. The ability of smart antennas to beamform and hence improve the signal quality at the clients has made them especially attractive for multicasting applications. Unfortunately, the problem of multicast beamforming design is a non-convex optimization problem for which only suboptimal solutions has been proposed in the literature. In this work, we uncover a hidden convexity of the problem under certain channel conditions which happens frequently for practical systems with Rayleigh fading channel model. We propose a solution based on this observation which consists of two steps: (1) we solve the dual problem and check for a uniqueness condition; if satisfied, we show that the duality gap is zero and the solution of the primal problem is obtained based on the solution of the dual problem; (2) if the uniqueness condition is not satisfied, we use a gradient descent based approach. Our evaluations reveal that the proposed algorithm significantly improves the multicast performance over state-of-the-art solutions. Simulation results show that in most scenarios of interest the algorithm converges within a required limit in the first step with high probability. We also obtain the performance bounds for the primal problem based on the dual formulation.

The demand for real-time video services coupled with the need for increased spectral efficiencies has brought a lot of attention to video multicasting in next generation OFDMA systems. Layered video provides an efficient solution to address the channel quality variation across users. However, the frequency selectivity across subchannels introduced by OFDMA serves as a drawback for multicast scheduling. This significantly diminishes the benefits of video layering and can potentially degrade the system performance to worse than that without channel diversity.

This paper is motivated by two observations: (1) cellular network operators are actively exploring advertisement delivery as a new means of revenue generation, and (2) cellular basestations perceive intermittent overloads at different times of day. Bringing the two observations together, we design and implement Opal, a novel system for opportunistically aligning advertisement delivery with basestation overload. Such alignment improves the overall perception of network availability for users. To achieve the alignment systematically, Opal builds on an analytical framework for tunable unavailability of network service to users during overload. At the same time, if the network is not overloaded enough during a certain period, Opal schedules enough advertisements to satisfy the advertisement delivery contracts. Opal minimizes the amount of state to be maintained to play advertisements to users uniformly and also maximizes the number of viewers for each advertisement. We implement a prototype of Opal on a Picochip based WiMAX testbed, and demonstrate its efficacy using simulations, analysis and prototype evaluation.

We demonstrate OPAL [2]- a system for opportunistically aligning advertisement delivery with basestation overload periods, which reduces the total number of times network service is unavailable to users. This system is motivated by two trends: Firstly, as networks get dominated by non-elastic traffic such as video, overload management using admission control will be imminent, thereby exposing network unavailability to users. Secondly, as mobile advertising is rapidly growing, mobile network operators are increasingly interested in leveraging its huge revenue potential, and are also better equipped than any other entity in reaching the users.

The proliferation of mobile applications and services involving group communications has increased the need for efficient wireless multicasting solutions in next generation broadband access networks. The availability of antenna arrays at the base stations makes adaptive beamforming especially attractive for multicasting; with beamforming, the received signal strength at the clients can be significantly improved. However, the problem of designing optimal transmit beamformers for multicast applications is challenging, mainly due to its non-convex nature. In this work, we design efficient transmit beamformers for wireless link layer multicasting where instantaneous channel state information is available at the transmitter. In addressing the non-convexity of the problem, we design non-iterative, near-optimal beamforming algorithms based on the optimality conditions derived from its Lagrangian formulation. We show that for real channels, e.g, where Pulse Amplitude Modulation (PAM) is used, the optimal solution can be obtained. To address the effectiveness of the proposed solution for the complex channel, we also derive an upper bound on the multicast rate based on the dual formulation of the problem. Evaluations reveal that our algorithms deliver a performance that is close to the upper bound, while significantly improving the multicast rate over state of the art solutions.

In this paper, we consider a downlink (DL) multiuser (MU) multi-input-multi-output (MIMO) channel with linear precoding where the base station simultaneously schedules several user terminals on the same frequency sub-band. We assume imperfect (or quantized) per-user channel state information at the base station and present two types of channel state information (CSI) reports from user terminals, namely, the CSI report that assumes the single-user (SU) MIMO transmissions and the enhanced CSI feedback report that assumes the MU-MIMO transmissions, and in the latter case we consider both uniform and nonuniform power allocations. To improve the MU-MIMO system performance, we propose signal-to-interference-plus-noise ratio (SINR) approximation techniques that utilize the quantized CSI available at the base station and improve the rate matching. We also introduce user pooling techniques which enable a reduction in feedback signaling overhead via per-user feedback mode selection. The proposed techniques also allow unconstrained user pairing at the base station scheduler and hence enable dynamic switching between SU and MU MIMO transmissions. The simulation results demonstrate the efficiency of the proposed MU-MIMO enhancement techniques.

Inter-cell interference mitigation is a key challenge in the next generation wireless networks which are expected to use an aggressive frequency reuse factor and a high-density base station deployment to improve coverage and spectral efficiency. In this work, we consider the problem of maximizing the weighted sum-rate of a wireless cellular network via coordinated scheduling and discrete power control. We present two distributed iterative algorithms which require limited information exchange and data processing at each base station. Both algorithms provably converge to a solution where no base station can unilaterally modify its status (i.e., transmit power and user selection) to improve the weighted sum-rate of the network. Numerical studies are carried out to assess the performance of the proposed schemes in a realistic system based on the IEEE 802.16m specifications. Simulation results show that the proposed algorithms achieve a significant rate gain over uncoordinated transmission strategies for both cell-edge and inner users.

Multiuser diversity techniques are used in multicarrier data systems to enhance downlink cell throughput. This requires downlink channel information from the users that is opportunistically used by a base station to send data to the users with good channel condition. Channel feedback from the user to the base station incurs high overhead especially when many users are in the cell and each user needs to report channel information over multiple channels, as in OFDMA systems. To reduce the quantity of feedback information without significant throughput degradation, a practical strategy is to deliver feedback on a partial set of channels with the best channel quality. We call it best feedback, and this reporting scheme carried out for best four or five among 24 channels has been already adopted in the IEEE 802.16e standard. Considering real feedback conditions, we investigate the performance of a best feedback scheme and derive the optimal number of channels for which information needs to be fed back to keep the throughput gap (compared to a full feedback scheme) within a target margin. From the optimal condition, we propose an adaptive best feedback algorithm, where the number of reported channels is adjusted to adapt to the number of users in the cell. We also propose an adjusted periodic feedback algorithm, where users are divided into groups and scheduling is carried out group by group, so a user can report feedback information when his group is scheduled, thereby reducing the frequency of feedback transmission. To support differentiated performance, we further propose heterogeneous feedback algorithms where users are divided into heterogeneous groups, each with a different group size or a different feedback period. Numerical results validate our analysis and provide meaningful insights into the design of various channel feedback schemes.

In this paper, we propose a practical and systematic approach to implement the MIMO transmission with rank adaptation for 60 GHz systems. In the 60 GHz system with multiple antennas, the transmit and receive (Tx-Rx) antenna arrays are grouped into a number of subarrays with a predetermined subarray separation based on the derived geometrical criteria of creating high rank MIMO in LoS environments. We first apply an enhanced blind beamforming technique based on a stochastic gradient algorithm (SGA) for the inner-subarray antennas, which does not require channel state information (CSI) at either the transmitter or the receiver. Secondly, the composite MIMO channel, as a joint effect of Tx-Rx beamforming and the channel impulse response, can be estimated with much reduced complexity. Finally, the MIMO transmission with rank adaptation is performed by adaptively selecting the better scheme out of the high-rank spatial multiplexing and the rank-1 beamforming whichever gives higher system throughput. Simulation results show that high-rank spatial multiplexing and rank-1 beamforming outperform each other at different geometrical placements and transmit power settings. The proposed MIMO transmission with rank adaptation offers significant performance gain especially at high signal-to-noise ratio (SNR) regions.

Energy detection is an attractive spectrum sensing method for cognitive radio. The design of energy detection relies on two critical assumptions: 1) noise power is perfectly and {\it a prior} known; and 2) the test statistics in energy detection can be accurately modeled as independent and identically distributed (i.i.d.) Gaussian random variables. In practice, noise power varies from time to time. This renders difficulty in estimating noise power and incurs an inaccuracy in modeling the test statistics. This paper studies how to realize energy detection using software-defined radio in a real environment. The noise power variation in a real environment is investigated. A histogram based method is proposed to determine the threshold of energy detection. Our experimental study shows the effectiveness of the histogram based method.

Scalable video coding (SVC) and Adaptive Modulation and Coding (AMC) are two key techniques for video multicast in broadband wireless networks. They can improve the system performance by enhancing the wireless resource allocation schemes and assigning appropriate modulation and coding schemes (MCS) to different layers of scalable video sequences. We formulate the problem as maximizing the total system utility subject to the total resource constraint, where the utility of each user is a generic non-negative, non-decreasing function of received rate. We then propose a fast intra-session MCS assignment algorithm based on dynamic programming. This algorithm can be integrated with an existing inter-session resource allocation algorithm and applied to multi-session scenarios. Simulation results show that our algorithm achieves significant improvement on the video quality over a naive algorithm and an adapted greedy algorithm, and greatly reduces the running time in both single-session and multi-session scenarios compared to a former optimal algorithm.

Scalable video coding (SVC), together with adaptive modulation and coding (AMC), can improve wireless multicast streaming video by jointly performing radio resource allocation and modulation and coding scheme (MCS) selection. However, the existing schemes in the literature allocate radio resources for different video layers separately, which leads to a waste of radio resources. In this work, we introduce the notion of joint layer resource allocation which allows to jointly allocate resources to multiple video layers that are assigned the same MCS. We formulate this problem and prove it to be NP-hard. Then we develop a pseudo-polynomial algorithm that finds the optimal total system utility. Our algorithm assumes a very generic utility function and flexible video layer rates. To reduce the complexity of the algorithm, we also propose Fully Polynomial Time Approximation Schemes (FPTAS) for the same problem. Simulation results show that our optimal algorithm offers significant improvement on system utility over a previous optimal algorithm and a greedy algorithm both of which do not support joint layer resource allocation. The proposed approximation algorithm provides controllable tradeoff between performance and computational complexity and, with appropriately chosen parameters, it outperforms the greedy algorithm with 40% less running time.

This paper describes the design and implementation of a network virtualization substrate NVS) for effective virtualization of wireless resources in WiMAX networks. Virtualization fosters the realization of several interesting deployment scenarios such as customized virtual networks, virtual services and wide-area corporate networks, with diverse performance objectives. In virtualizing a basestation's uplink and downlink resources into slices, NVS meets three key requirements - isolation, customization, and efficient resource utilization - using two novel features: (1) NVS introduces a provably-optimal slice scheduler that allows existence of slices with bandwidth-based and resource-based reservations simultaneously, and (2) NVS includes a generic framework for efficiently enabling customized flow scheduling within the basestation on a per-slice basis. Through a prototype implementation and detailed evaluation on a WiMAX testbed, we demonstrate the efficacy of NVS. For instance, we show for both downlink and uplink directions that NVS can run different flow schedulers in different slices, run different slices simultaneously with different types of reservations, and perform slice-specific application optimizations for providing customized services.

With the next generation cellular networks making a transition towards smaller cells, two-hop OFDMA relay networks have become a dominant, mandatory component in the 4G standards (WiMAX 802.16j, 3GPP LTE-Adv). While unicast flows have received reasonable attention in two-hop OFDMA relay networks, not much light has been shed on the design of efficient scheduling algorithms for multicast flows, thereby forming the focus of this work. We show that while relay cooperation is critical for improving multicast performance, it must be carefully balanced with the ability to multiplex multicast sessions and hence maximize aggregate multicast flow. To this end, we highlight strategies that carefully group relays for cooperation to achieve this balance. We then solve the multicast scheduling problem under two OFDMA sub-channelization models. We establish the NP-hardness of the scheduling problem even for the simpler model and provide efficient algorithms with approximation guarantees under both models. Evaluation of the proposed solutions reveals the efficiency of the scheduling algorithms as well as the significant benefits obtained from the multicasting strategy.

We present a cross-layer design of transmitting scalable video streams from a base station to multiple clients over a shared fading wireless network by jointly considering the application layer information and the wireless channel conditions. We first design a long-term resource allocation algorithm that determines the optimal wireless scheduling policy in order to maximize the weighted sum of average video quality of all streams. We prove that our algorithm achieves the global optimum even though the problem is not concave in the parameter space. We then devise two on-line scheduling algorithms that utilize the results obtained by the long-term resource allocation algorithm for user and packet scheduling as well as video frame dropping strategy. We compare our schemes with existing video scheduling and buffer management schemes in the literature and simulation results show our proposed schemes significantly outperform existing ones.

Cognitive radio that supports a secondary and opportunistic access to licensed spectrum shows great potential to dramatically improve spectrum utilization. Spectrum sensing performed by secondary users to detect unoccupied spectrum bands, is a key enabling technique for cognitive radio. This paper proposes a truncated sequential spectrum sensing scheme, namely the sequential shifted chi-square test (SSCT). The SSCT has a simple test statistic and does not rely on any deterministic knowledge about primary signals. As figures of merit, the exact false-alarm probability is derived, and the miss-detection probability as well as the average sample number (ASN) are evaluated by using a numerical integration algorithm. Corroborating numerical examples show that, in comparison with fixed-sample size detection schemes such as energy detection, the SSCT delivers considerable reduction on the ASN while maintaining a comparable detection performance.

Future 4G cellular networks are featured with high data rate and improved coverage, which will enable realtime video multicast and broadcast services. Scalable video coding is very appropriate for wireless multicast service because it allows to choose different modulation and coding schemes (MCSs) for different video layers and can provide good video quality to users in good channel conditions while still maintaining reasonable video quality for other users. In order to apply scalable video coding to wireless multicast streaming, it is important to choose appropriate MCS for each video layer and to determine the right resource allocation among multiple video sessions. In this paper we propose a two-step dynamic programming algorithm that finds the optimal total system utility of all users where the system utility can be a generic non-negative, non-decreasing function of received rate. Our algorithm supports variable layer size and thus allows flexibility during the video encoding process. Simulation results show that our algorithm offers significant improvement on the video quality over a naive algorithm and an adapted greedy algorithm, especially in the scenarios with multiple real video sequences and limited radio resources.

WLANs have become an important last-mile technology for providing internet access within homes and enterprises. In such indoor deployments, the wireless channel suffers from significant multipath scattering and fading that degrades performance. Beamforming is a smart antenna technology that adjusts the transmissions at the transmitter to reenforce the signals received through multiple paths at the receiver.

Several research works have argued that adaptive beamforming has the potential to realize the high spectral efficiency requirements of next-generation wireless standards, and is especially well-suited for multipath-rich environments such as indoors. Most works have been limited to theory; few works in literature address the practical benefits and realizability of adaptive beamforming. In this paper, we design and implement the first indoor WLAN beamforming system with multi-element array antennas and software radio platforms, that forms a testbed for exploration of practical benefits of beamforming, and evaluation of algorithms for efficient beamforming in diverse environments. In the process of building the system, we identify and address several challenges with practical beamforming that are often ignored in theoretical works. Most importantly, channel estimation for forming the best beam to a user is hindered by oscillator drifts on the transmitter and receiver side that introduce hard-to-isolate phase and frequency offsets from the estimated channel coefficients. We describe these issues and incorporate novel solutions in our system to address them without requiring hardware modifications. We use the system to demonstrate the realizable benefits of adaptive beamforming in a typical indoor office environment.

We consider the problem of scheduling users with backlogged and finite buffers on the multiple OFDM carriers (channels) over the two hops of the relay-enabled wireless network. Motivated by the recent 802.16j standard, we consider two sub-carrier grouping models (PUSC, AMC). While the extent of diversity gain varies depending on the model, spatial reuse is common to both the models and is crucial in delivering the promised throughput benefits of relays. Hence leveraging spatial reuse forms the prime focus of this work with diversity gains being leveraged when available. We establish the hardness of the problem under these two models and propose efficient approximation algorithms for the scheduling problem considered. Our solutions are simple to implement at the base station, while also providing worst case guarantees. The proposed solutions are evaluated to highlight their benefits in a variety of network conditions.

We consider the problem of efficient link-layer multicasting in wireless networks with switched beamforming antennas. The inherent tradeoff between multicasting and beamforming -- the broadcast advantage of low-gain omni-directional transmissions versus the high-gain but spatially restricted transmissions of beamforming antennas -- makes this problem especially challenging.

Femto cells are a cost-effective means of providing ubiquitous connectivity in future broadband wireless networks. While their primary purpose has been to improve coverage in current solutions, their decreased cell sizes in turn also provide improved cell capacity through increased spatial reuse. The demand for bandwidth-intensive IP services will soon necessitate the need to tap into this improved capacity. However, the lack of direct coordination between the macro and femto cells, and the completely distributed nature of femto cells make this an extremely challenging task. In this work, we address this challenge by providing efficient resource management solutions for OFDMA-based femto cells along with performance guarantees. In the process, we consider two models that tradeoff performance and overhead. We also propose a novel location-based resource management solution for leveraging maximal spatial reuse from femto cells. Our comprehensive evaluations indicate that in addition to providing improved coverage indoors, with carefully designed resource management solutions that leverage spatial reuse, femto cells have a great potential to increase the system performance by two folds.

We design, implement, and evaluate a vehicular communication system that improves uplink connectivity through multi-lobe beam pattern switching on a smart antenna. Directionality and base station-diversity are two well-known, independently developed mechanisms for improving the uplink connectivity of mobile clients. In this paper, we highlight that a system combining both mechanisms can achieve significant improvement in performance with multi-lobe beams that strike a tradeoff between directionality and diversity. This is in contrast to the mere steering of narrow beams used in conventional smart antenna systems. For tractability at vehicular speeds, our R2D2 system searches through a limited set of beam patterns with different numbers of lobes, and includes a two-stage algorithm that uses both runtime adaptation and cached candidate patterns. We design and evaluate several variants of run-time adaptation that tune the number and angle of lobes in the beam, and the bit rate. The design of these algorithms is guided by both analysis and real-world measurements with a smart antenna system mounted on a vehicle. These measurements with our prototype implementation show that R2D2 can achieve an uplink throughput increase of up to 154% over pure beamsteering and 45% over pure basestation diversity.

In a cognitive radio (CR) network, cooperative spectrum sensing plays an important role in ensuring the quality of service (QoS) of primary users (PUs) and improving spectral utilization efficiency. Intuitively, the more secondary users (SUs) are involved in sensing, the more sensing accuracy the CR can achieve, whereas the more sensing overhead the SUs consume, the less throughput the CR network can achieve. In this paper, we investigate overhead-throughput tradeoff over fading channels in a cooperative CR network that consists of a number of the SUs employing energy detectors and a single decision fusion center. We propose a design strategy to maximize the throughput of the SU network by choosing appropriate sensing length and the number of the SUs reporting to a decision fusion center. Moreover, we extend our analysis to a two-stage cooperative sensing mechanism where the second-stage fine sensing is triggered whenever any SU reports the presence of a PU after the first-stage detection. Our numerical results show that compared with the single stage sensing, the two-stage sensing scheme achieves higher throughput via the reduction of the probability of false alarm.

We consider the transmission of multiple scalable video streams from a server to multiple users over a fading wireless channel. We first present a long-term resource allocation algorithm that determines the scheduling policy and the parameters used by the scheduling policy in order to maximize the weighted sum of PSNR of all video streams. We then present an online scheduling algorithm that utilizes the results obtained by the long-term resource allocation algorithm for user and packet scheduling as well as video frame dropping strategy. Simulation results show that our proposed scheduling scheme significantly improves the video quality compared to the best-known scheduling algorithms in the literature.

We consider the problem of maximizing the weighted sum data rate in multi-cell and multi-carrier wireless data systems in the presence of interference. We present a scheme that jointly considers load balancing, user scheduling, and interference mitigation to improve the system performance. Our proposed scheme iteratively applies two processes. The first process solves the sub-problem of load balancing and user scheduling while fixing the power allocation of each BS (and thus fixing the interference). We prove that this sub-problem is NP-hard, and devise a 1/2-approximation algorithm to solve the problem. We also consider an extended model capturing finite queue size and propose a 1/2-approximation algorithm under this model. The second process solves the problem of interference mitigation assuming fixed load balancing and user scheduling. We develop a local-improvement based algorithm to solve this problem. Via simulations, we demonstrate that our joint scheme improves both average system throughput and fairness significantly. Compared to the scheme with fixed user-BS association and 1/3 frequency reuse, the lowest 10% cell-edge users obtain more than 60% performance improvement and 90%of users enjoy more than 30%throughput improvement.

Relay-enabled wireless networks (eg. WIMAX 802.16j) coupled with orthogonal frequency division multiple access (OFDMA) as the air interface technology represent an emerging trend in future wireless infrastructure deployments. While the flexibility of OFDMA allows accommodation of heterogeneous (unicast and multicast) traffic, its combination with relays opens up a multitude of diversity and spatial reuse gains. However, leveraging these benefits to efficiently handle heterogeneous traffic calls for more sophisticated solutions, among which, user scheduling forms a key component. We ask the following specific question in this work: Can unicast and multicast traffic efficiently coexist in an OFDMA-based wireless relay network? We address the question by first identifying the key challenges that make coexistence difficult in the target environment. We show that scheduling of unicast and multicast traffic is tightly coupled even if they are isolated through orthogonal spectral allocations. We also show that the nature of gains that optimize the individual traffic are complementary and hence reveal a fundamental tradeoff in jointly optimizing the system for both unicast and multicast traffic in tandem. Using the insights gained, we propose an integrated scheduling strategy that strikes a good balance in delivering efficient performance to both the unicast and multicast flows. The proposed solution yields gains of over 60% over individual traffic specific strategies.

Deploying and managing wide-area network services is exceptionally challenging. Despite having servers at many locations, a service provider must rely on an underlying best-effort network; a network provider can offer services over its own customized network, but only within limited footprint. In this paper, we propose Cabernet (Connectivity Architecture for Better Network Services), a three-layer network architecture that lowers the barrier for deploying wide-area services. We introduce the connectivity layer, which uses virtual links purchased from infrastructure providers to run virtual networks with the necessary geographic footprint, reliability, and performance for the service providers. As an example, we present a cost-effective way to support IPTV delivery through wide-area IP multicast that runs on top of a reliable virtual network.

We consider the packet scheduling of video frames in the wireless last hop. At the time of network congestion and bad channel conditions, it is necessary to drop some (less important) frames in order to maintain the continuity of the video streaming. The decision on whether to drop and how many frames need to be dropped has to be based on the deadline, size, and importance/utility (in terms of the contribution to the video quality) of each frame. In this paper, we propose an adaptive scheduling algorithm that dynamically decides which frames need to be transmitted and which ones need to be dropped at any transmission opportunity based on the current channel conditions and on the characteristics of each video frame. Simulation results show our scheduling algorithm achieves near optimal performance compared to an optimal offline algorithm that knows the outcome of each transmission opportunity in the future.

Relay-enabled wireless networks (eg. WIMAX 802.16j) represent an emerging trend for the incorporation of multi-hop networking solutions for last-mile broadband access in next generation wireless networks. The adoption of more sophisticated access technologies such as OFDM (orthogonal frequency division multiplexing) coupled with the relay-induced two-hop nature, provides two key benefits to these networks in the form of diversity and spatial reuse gains. However, leveraging these benefits calls for more sophisticated solutions, among which, user scheduling forms a key component.

To support real-time applications such as Voice-over-IP within an 802.11 Wireless LAN, efficient handoff mechanisms are required when a mobile client moves from one Access Point to another. In this paper, we present the design, implementation and performance results of MAC layer (layer-2) handoff algorithms which implement make-before-break mechanisms at the MAC layer unlike current algorithms that are based on break-before-make. As a baseline, we first present an algorithm that uses a single radio card on the client (as is done traditionally), but optimizes MAC layer handoff by periodically probing in the background for Access Points on other channels even when it is already associated with an Access Point and actively sending and receiving data. We then present two novel algorithms that use two radio cards on the client so that when one card is involved in communicating data, the other card can probe for neighboring Access Points. Of these multiple radio algorithms, the first one uses dedicated data and control cards at the client thereby implementing a soft version of make-before-break. The second algorithm uses two cards which can both perform control and data forwarding functions thereby implementing a strict version of make-before-break. Experimental results from a prototype implementation show that the make-before-brake algorithms lead to a significant reduction in MAC layer handoff overhead; the algorithm for the strict version of the make-before-break mechanism leads to sub 10 millisecond hand-off latency.

This paper presents the design and implementation of a low latency layer-3 handoff scheme for 802.11 wireless mobiles roaming between access points that are connected to different IP subnets. Called LIHP (link-layer initiated handoff protocol), the scheme uses link-layer frames (e.g., ARP and 802.11 management frames) as triggers to send route updates to the mobiles and to an access gateway, which serves as the gateway to the Internet for the mobiles. This approach allows for IP packet routing to and from a mobile to begin immediately after the mobile establishes a link-layer association with a new access point. Furthermore, the design does not require any modification to the mobiles. Each mobile is assigned a single IP address and maintains its IP address as it moves from one access point to another, thus preserving TCP connections across hand-offs. The access points (called access routers in LIHP) and the access gateway cooperate to track each mobile and forward packets using IP tunnelling. Experimental results from a prototype implementation show that the scheme can achieve layer-3 handoff latency on the order of a few milliseconds

In current CDMA2000 standard, a packet data serving node (PDSN) acts as an IP gateway to the Internet. Mobile nodes (MN) connect to a PDSN using a point-to-point (PPP) session and IP packets are tunneled over the PPP session from the client to the PDSN which then routes the packets onto a packet network. A CDMA2000 network is a hierarchical network where packets from an MN to the PDSN are transported over a radio-access network (RAN). An MN could move from one RAN to another and still be anchored under the same PDSN; it is also possible that when an MN moves from one RAN to another, the anchor PDSN itself becomes different. In the latter case, there are two ways to handle mobility: (i) tear down the PPP session from the MN to the old PDSN and establish a new PPP session from the MN to the new PDSN, and (ii) use the fast-handoff mechanism as specified in the CDMA2000 standard where a P-P (PDSN to PDSN) tunnel is established to tunnel PPP frames from the old PDSN to the new PDSN and then to the MN. In this paper, we present a better approach to handling mobility than either of the above two techniques. The method is to migrate the PPP state from the old PDSN to the new PDSN transparent to the MN; once the PPP state migration is completed, the new PDSN will serve as the IP gateway to the MN. We have implemented the PPP migration technique and through experimental measurements show its benefits.

A virtual private network (VPN) is an overlay network that uses the public network to carry data traffic between corporate sites and users, maintaining privacy through the use of tunnelling protocols and security procedures. In the network-based model, VPN-aware network elements are placed within the network to set up concatenated tunnels between the user/site and enterprise resources to offer intranet VPN and remote access VPN. This paper identifies the important differences between a traditional VPN and the mobile VPN and proposes a hierarchical network architecture to efficiently realize network-based mobile VPNs. We address the problem of optimally provisioning VPN-aware devices, called IP service gateways (IPSGs), in the hierarchical network architecture for mobile VPNs, while taking into account of (1) the cost of links over which VPN tunnels are established, (2) the cost of provisioning a VPN customer on an IPSG, and (3) redundancy in IPSG provisioning for fault tolerance. We develop generic yet powerful problem formulations for different scenarios described above while considering practical requirements of the network elements and business requirements of the VPN service provider. The formulation becomes a set of integer programming problems. We solve several instances of the problem for a few practical cases and discuss their applications in the overall network design.

In a CDMA2000 network, a mobile node (MN) gets packet data service by establishing a PPP session with a packet data serving node (PDSN). The PDSN acts as the muter for the IP packets transported over the PPP session. A packet control function (PCF) sits between the radio access network and the packet network, selects the PDSN for the MN during session setup, and relays the PPP frames between the MN and the PDSN during the session. The PCF selects a PDSN based on the MN's device identity. Due to this, the data services that a mobile user subscribes become tightly coupled with the device that the user registers with the service provider. Because the PCF selects a PDSN based only on mobile device identity, it is unable to select the "best" PDSN to support the services subscribed by a specific user. This work presents the design and implementation of an entity called radio-packet session redirector (RPSR) that works within the current standard and alleviates this shortcoming. The RPSR intercepts a PPP session, parses the user identity, selects a PDSN based on the user identity, creates a PPP session with the selected PDSN and splices the sessions together so that PPP frames can be seamlessly forwarded between the MN and the PDSN with very little overhead. We identify a number of services that RPSR enables in the network. We describe a prototype stand-alone device implementation of the RPSR in the Linux kernel and present performance results.

Recent observations through experiments that we have performed in current third generation wireless networks have revealed that the achieved throughput over wireless links varies widely depending on the application. In particular, the throughput achieved by file transfer application (FTP) and web browsing application (HTTP) are quite different. The throughput achieved over a HTTP session is much lower than that achieved over an FTP session. The reason for the lower HTTP throughput is that the HTTP protocol is affected by the large Round-Trip Time (RTT) across Wireless links. HTTP transfers require multiple TCP connections and DNS lookups before a HTTP page can be displayed. Each TCP connection requires several RTTs to fully open the TCP send window and each DNS lookup requires several RTTs before resolving the domain name to IP mapping. These TCP/DNS RTTs significantly degrade the performance of HTTP over wireless links. To overcome these problems, we have developed session level optimization techniques to enhance HTTP download mechanisms. These techniques (a) minimize the number of DNS lookups over the wireless link and (b) minimize the number of TCP connections opened by the browser. These optimizations bridge the mismatch caused by wireless links between application-level protocols (such as HTTP) and transportlevel protocols (such as TCP). Our solutions do not require any client-side software and can be deployed transparently on a service provider network to provide 30 50% decrease in end-to-end user perceived latency and 50-100% increase in data throughput across wireless links for HTTP sessions.

A component-based software development approach has become a trend in integrating modern software systems. To ensure the overall reliability of an integrated software system, its software components have to meet certain reliability requirements, subject to some testing schedule and resource constraints. Efficiency improvement of the system-testing can be formulated as a combinatorial optimization problem with known cost, reliability, effort and other attributes of the system components. This paper considers "software component testing resource allocation" for a system with single or multiple applications, each with a pre-specified reliability requirement. The relation between failure rates of components and "cost to decrease this rate" is modeled by various types of reliability-growth curves. Closed-form solutions to the problem for systems with one single application are developed, and then "how to solve the multiple application problem using nonlinear programming techniques" are described. Also examined are the interactions between the system components, and inter-component failure dependencies are included in the modeling formula. In addition to regular systems, the technique is extended to address fault-tolerant systems. A procedure for a systematic approach to the testing resource allocation problem is developed, and its application in a case study of a telecommunications software system is described. This procedure is automated in a reliability allocation tool for an easy specification of the problem and an automatic application of the technique. This methodology gives the basic approach to optimization of testing schedules, subject to reliability constraints. This adds "interesting new optimization opportunities in the software testing phase" to the existing optimization literature that is concerned with structural optimization of the software architecture. Merging these two approaches improves the reliability planning accuracy in component-based software development.

Previously, Rangarajan et al. (see Proc. of the 25th International Symposium on Fault-Tolerant Computing, 1995) presented the design, specification and proof of correctness of a fully distributed location management scheme for PCS networks and argued that fully replicating location information is both appropriate and efficient for small PCS networks. In this paper, we extend our previous work by first analyzing the performance of our scheme. Then, we extend the scheme in a hierarchical environment so as to reduce the overhead and scale to large PCS networks. Through extensive numerical results, we show the superiority of our scheme compared to the current IS-41 standard.

Personal communication networks support the delivery of communication services as the user moves from one region to another. When a mobile user/terminal receives a call, the network has to quickly determine its current location. The existing approach suffers from high delay in locating the mobile as it requires maintaining the current location in a stable storage that has to be always consulted to reach the mobile. To reduce this delay, many proposed schemes rely on caching the locations of mobiles, especially those which do not move too frequently. To measure mobility, the node that originates the call usually measures only those movements that it sees between successive calls to that mobile. In this paper, we present a caching scheme based on fully disseminating the location updates of mobiles to every node so as to increase the chance that the cache entry points to the correct location of the mobile user. We analyze our full dissemination based scheme and compare it to other caching and non-caching based schemes.

Checkpointing and roll-back recovery is a well known technique for recovering from software process failures. Analytical models have been developed for computing the completion time of processes that use various checkpointing strategies such as periodic checkpointing, random checkpointing etc. In this paper, we show that with active replication of processes, a strategy that uses a mechanism we call checkpoints-on-demand will result in an expected completion time smaller than that can be achieved with traditional schemes that use periodic checkpoints. With checkpoints-on-demand, when a process fails, it is recovered from an induced checkpoint taken of a replica of the process. Recovery of persistent server processes through state-transfer from a replica has been proposed in the context of group communication systems and in the process cloning approach of the Delta-4 architecture. But it has not been previously proposed and analyzed as a mechanism for reducing the expected completion time of a long running process.

To ensure an overall reliability of an integrated software system, software components of the system have to meet certain reliability requirements, subject to some testing schedule and resource constraints. The system testing activity can be formulated as a combinatorial optimization problem with known cost, reliability, effort and other attributes of the system components. In this paper, we consider the software component reliability allocation problem for a system with multiple applications. The failure rate of components used to build the applications are related to the testing cost through various types of reliability growth curves. We achieve closed-form solutions to problems where there is one single application in the system. Analytical solutions are not readily available when there are multiple applications; however, numerical solutions can be obtained using a nonlinear programming tool. To ease the specification of the optimization problem, we develop a GUI front-end to existing mathematical software. We present a systematic outline of the problem formulation and solution, and apply this to an example of a telecommunication software system.

Describes the design and analysis of RobustWeb, a scalable and fault-tolerant World Wide Web server cluster that is based on HTTP redirection. The system consists of a set of N back-end document servers and one or more redirection servers which receive the HTTP requests and redirect them to the document servers. A load distribution algorithm is used for initial distribution of the documents on the servers. Given a specific degree of replication k, the distribution algorithm guarantees that at least k replicas of each document are present after document distribution is complete. The redirection servers redirect requests to one of the replicas with a pre-computed redirection probability. When a server fails, the redirection probabilities are recomputed using a novel algorithm based on network flow. Theis enables the load to be approximately balanced among the remaining servers, allowing for graceful degradation of the service in the event of failures. A preliminary prototype of RobustWeb has been implemented.

A k-resilient system with N components can tolerate up to k component failures and still function correctly. We consider k-resilient systems where the number of component failures is a constant fraction of the total number of components, that is k=N/c and c is a constant such that 2/spl les/c

Management of replicated data has received considerable attention in the last few years. Several replica control schemes have been proposed which work in the presence of both node and communication link failures. However, this resiliency to failure inflicts a performance penalty in terms of the communication overhead incurred. Though the issue of performance of these schemes from the standpoint of availability of the system has been well addressed, the issue of message overhead has been limited to the analysis of worst case and best case message bounds. In this paper we derive expressions for computing the average message overhead of several well known replica control protocols and provide a comparative study of the different protocols with respect to both average message overhead and system availabilities.

A distributed algorithm is described for detecting and diagnosing faulty processors in an arbitrary network. Fault free processors perform simple periodic tests on one another; when a fault is detected or a newly repaired processor joins the network, this new information is disseminated in parallel throughout the network. It is formally proven that the algorithm is correct, and it is also shown that the algorithm is optimal in terms of the time required for all of the fault free processors in the network to learn of a new event. Simulation results are given for arbitrary network topologies.>

k-resilient protocols are used in some parallel and distributed system applications for increased availability of resources. A protocol running on an n site system is k resilient if it could tolerate up to k failures and operate correctly. The reliability of such a protocol is defined as the probability that no more than k sites have failed. Such a k-resilient protocol is beneficial only when its reliability is greater than the reliability of a protocol running on a system with a single site. We consider k-resilient protocols and develop a general technique for approximately computing the time until which these protocols have higher reliability than protocols running on single site systems. We call this time the reliability interval. Our general techniques for computing the reliability interval can be used irrespective of the type of failure distribution (with respect to time) of the sites of the system. We use experimental results to validate our technique.>

We examine the tradeoff between message overhead and data availability that arises in the design of fault-tolerant algorithms for replicated data management in distributed systems. We propose a property called asymptotically high resiliency which is useful for evaluating the fault-tolerance of replica control algorithms and distributed mutual exclusion algorithms. We present a new algorithm for replica control that can be tailored (through a design parameter) to achieve the desired balance between low message overhead and high data availability. Further, we show that for a message overhead of O(/spl radic/(Nlog N)), our algorithm can achieve asymptotically high resiliency.

Management of replicated data has received considerable attention in the last few years. Several replica control schemes have been proposed which work in the presence of both node and communication link failures. However, this resiliency to failure inflicts a performance penalty in terms of the communication overhead incurred. Though the issue of performance of these schemes, from the standpoint of availability of the system, has been well addressed, the issue of message overhead has been limited to the analysis of worst-case and best-case message bounds. In this paper, we compare several well-known replica management protocols and control schemes in terms of their average-case message overhead. We also consider the tradeoff between the message overhead and availability, and we define the system model considered. Analytical expressions are derived for five well-known replica control protocols. The results are discussed with numerical examples.>

Data replication is often used to increase the availability of data in a database system. Voting schemes can be used to manage this replicated data. The authors use a simple model to study the capacity of systems using voting schemes for data management. Capacity of a system is defined as the number of operations the system can perform successfully, on an average, per unit time. The capacity of a system using voting is examined and compared with the capacity of a system using a single node. It is shown that the maximum increase in capacity by the use of majority voting is bounded by 1/p, where p is the steady-state probability of a node being alive. It is also shown that for a system employing majority voting, if the reliability of nodes is high, increasing the number of nodes to more than three gives only a marginal increase in capacity. Similar analyses are performed for three other voting schemes.>

The problem of managing replicated copies of data in a distributed database is considered. Quorum consensus methods for managing replicated data require that an operation proceed only if a group of copies form a quorum. For example, in a majority voting scheme, for a write operation to proceed, a majority of the copies have to form a quorum. The authors first introduce a performance measure for measuring the performance of fault-tolerant algorithms for this problem. They then propose a quorum-based method which is highly fault tolerant and has a low message overhead. The algorithm can tradeoff fault tolerance for lower message overhead. The algorithm is compared to existing algorithms.>

A practical model for probabilistic fault diagnosis is presented. Unlike PMC-based models, the model allows testers to conduct multiple tests on the same processor. This allows the design of efficient probabilistic diagnosis algorithms with good asymptotic behavior, with minimal constraints on the connection structure of the multiprocessor system, in contrast to other deterministic and probabilistic approaches. In practical cases, the number of immediate neighbors of any processor need be no greater than two, which implies that the algorithm can be applied to any practical homogeneous parallel architecture. It is also shown how to make efficient use of tests by allowing the number of testing processors, and the number of tests performed by a processor to be traded off in achieving asymptotically accurate diagnosis.>

A probabilistic comparison algorithm is presented which requires O(f log n) bits to be transmitted to identify the corrupt pages in a file (where n is the number of pages and f is the maximum number of pages that could be corrupted), which improves on previous results on the growth of communicated bits as functions of both n and of f. If both copies compared are corrupt, only twice the number of bits is required as for the previous case. Further, if multiple copies are used for comparison, then the product of the number of copies times the number of bits sent from each of these copies to the comparison site grows as O(f log n). A lower bound which establishes the optimality of the algorithm to within a constant factor is provided.>

A probabilistic clock synchronization algorithm is proposed where processors in the system exchange time stamps and synchronize to a common clock value. Most of the previous algorithms for this problem have been based on a master-slave approach where all the slave processors synchronize to the clock value of a master. These algorithms are not distributed in nature and some of the assumptions made in these algorithms may become invalid if a large number of slaves try to synchronize with a master. The only distributed algorithm that is available was earlier proposed by A. Olson and K.G. Shin (1991). It is based on finding a cyclic path connecting the processors in the system and exchanging time stamp messages through this path. For the same level of synchronization accuracy, the proposed algorithm uses a much smaller number of messages.>

Production testing of a digital circuit requires the generation of a sequence of tests and their application to the circuit being tested. Currently, in test application, the output of the circuit under test is compared to a known correct output for each test. The method has some drawbacks likely to become more critical in the near future. In homogeneous systems of identical integrated circuits of silicon wafers, testing can be done in another way, i.e. by applying a common test to several processing elements at once and comparing the results produced by them. The authors analyze such schemes and show that they are inherently as accurate as current methods that use assumed correct results for production testing. Since this approach could allow wafers to be tested for production faults significantly more quickly than by using a probe tester, the results indicate that it can provide an attractive alternative to current methods for production testing of silicon wafers.>