Browsing by Subject "Wireless networks"
Now showing 1 - 20 of 20
Results Per Page
Sort Options
Item Applications of Game Theory to Multi-Agent Coordination Problems in Communication Networks(2013-08-28) Ramaswamy Pillai, VinodRecent years there has been a growing interest in the study of distributed control mechanisms for use in communication networks. A fundamental assumption in these models is that the participants in the network are willing to cooperate with the system. However, there are many instances where the incentives to cooperate is missing. Then, the agents may seek to achieve their own private interests by behaving strategically. Often, such selfish choices lead to inefficient equilibrium state of the system, commonly known as the tragedy of commons in Economics terminology. Now, one may ask the following question: how can the system be led to the socially optimal state in spite of selfish behaviors of its participants? The traditional control design framework fails to provide an answer as it does not take into account of selfish and strategic behavior of the agents. The use of game theoretical methods to achieve coordination in such network systems is appealing, as it naturally captures the idea of rational agents taking locally optimal decisions. In this thesis, we explore several instances of coordination problems in communication networks that can be analyzed using game theoretical methods. We study one coordination problem each, from each layer of TCP/IP reference model - the network model used in the current Internet architecture. First, we consider societal agents taking decisions on whether to obtain content legally or illegally, and tie their behavior to questions of performance of content distribution networks. We show that revenue sharing with peers promote performance and revenue extraction from content distribution networks. Next, we consider a transport layer problem where applications compete against each other to meet their performance objectives by selfishly picking congestion controllers. We establish that tolling schemes that incentivize applications to choose one of several different virtual networks catering to particular needs yields higher system value. Hence, we propose the adoption of such virtual networks. We address a network layer question in third problem. How do the sources in a wireless network split their traffic over the available set of paths to attain the lowest possible number of transmissions per unit time? We develop a two level distributed controller that attains the optimal traffic split. Finally, we study mobile applications competing for channel access in a cellular network. We show that the mechanism where base station conducting sequence of second price auctions and providing channel access to the winner achieves the benefits of the state of art solution, Largest Queue First policy.Item Bandwidth and power efficient wireless spectrum sensing networks(2011-05) Kim, Jaeweon; Andrews, Jeffrey G.; Vishwanath, Sriram; Arapostathis, Aristotle; Vikalo, Haris; Barr, Ronald E.Opportunistic spectrum reuse is a promising solution to the two main causes of spectrum scarcity: most of the radio frequency (RF) bands are allocated by static licensing, and many of them are underutilized. Frequency spectrum can be more efficiently utilized by allowing communication systems to find out unoccupied spectrum and to use it harmlessly to the licensed users. Reliable sensing of these spectral opportunities is perhaps the most essential element of this technology. Despite significant work on spectrum sensing, further performance improvement is needed to approach its full potential. In this dissertation, wireless spectrum sensing networks (WSSNs) are investigated for reliable detection of the primary (licensed) users, that enables efficient spectrum utilization and minimal power consumption in communications. Reliable spectrum sensing is studied in depth in two parts: a single sensor algorithm and then cooperative sensing are proposed based on a spectral covariance sensing (SCS). The first novel contribution uses different statistical correlations of the received signal and noise in the frequency domain. This detector is analyzed theoretically and verified through realistic simulations using actual digital television signals captured in the US. The proposed SCS detector achieves significant improvement over the existing solutions in terms of sensitivity and also robustness to noise uncertainty. Second, SCS is extended to a distributed WSSN architecture to allow cooperation between 2 or more sensors. Theoretical limits of cooperative white space sensing under correlated shadowing are investigated. We analyze the probability of a false alarm when each node in the WSSN detects the white space using the SCS detection and the base station combines individual results to make the final decision. The detection performance compared with that of the cooperative energy detector is improved and fewer sensor nodes are needed to achieve the same sensitivity. Third, we propose a low power source coding and modulation scheme for power efficient communication between the sensor nodes in WSSN. Complete analysis shows that the proposed scheme not only minimizes total power consumption in the network but also improves bit error rate (BER).Item Congestion control and routing over challenged networks(2011-12) Ryu, Jung Ho; Shakkottai, Sanjay; de Veciana, Gustavo; Vishwanath, Sriram; Julien, Christine; Hasenbein, JohnThis dissertation is a study on the design and analysis of novel, optimal routing and rate control algorithms in wireless, mobile communication networks. Congestion control and routing algorithms upto now have been designed and optimized for wired or wireless mesh networks. In those networks, optimal algorithms (optimal in the sense that either the throughput is maximized or delay is minimized, or the network operation cost is minimized) can be engineered based on the classic time scale decomposition assumption that the dynamics of the network are either fast enough so that these algorithms essentially see the average or slow enough that any changes can be tracked to allow the algorithms to adapt over time. However, as technological advancements enable integration of ever more mobile nodes into communication networks, any rate control or routing algorithms based, for example, on averaging out the capacity of the wireless mobile link or tracking the instantaneous capacity will perform poorly. The common element in our solution to engineering efficient routing and rate control algorithms for mobile wireless networks is to make the wireless mobile links seem as if they are wired or wireless links to all but few nodes that directly see the mobile links (either the mobiles or nodes that can transmit to or receive from the mobiles) through an appropriate use of queuing structures at these selected nodes. This approach allows us to design end-to-end rate control or routing algorithms for wireless mobile networks so that neither averaging nor instantaneous tracking is necessary, as we have done in the following three networks. A network where we can easily demonstrate the poor performance of a rate control algorithm based on either averaging or tracking is a simple wireless downlink network where a mobile node moves but stays within the coverage cell of a single base station. In such a scenario, the time scale of the variations of the quality of the wireless channel between the mobile user and the base station can be such that the TCP-like congestion control algorithm at the source can not track the variation and is therefore unable to adjust the instantaneous coding rate at which the data stream can be encoded, i.e., the channel variation time scale is matched to the TCP round trip time scale. On the other hand, setting the coding rate for the average case will still result in low throughput due to the high sensitivity of the TCP rate control algorithm to packet loss and the fact that below average channel conditions occur frequently. In this dissertation, we will propose modifications to the TCP congestion control algorithm for this simple wireless mobile downlink network that will improve the throughput without the need for any tracking of the wireless channel. Intermittently connected network (ICN) is another network where the classic assumption of time scale decomposition is no longer relevant. An intermittently connected network is composed of multiple clusters of nodes that are geographically separated. Each cluster is connected wirelessly internally, but inter-cluster communication between two nodes in different clusters must rely on mobile carrier nodes to transport data between clusters. For instance, a mobile would make contact with a cluster and pick up data from that cluster, then move to a different cluster and drop off data into the second cluster. On contact, a large amount of data can be transferred between a cluster and a mobile, but the time duration between successive mobile-cluster contacts can be relatively long. In this network, an inter-cluster rate controller based on instantaneously tracking the mobile-cluster contacts can lead to under utilization of the network resources; if it is based on using long term average achievable rate of the mobile-cluster contacts, this can lead to large buffer requirements within the clusters. We will design and analyze throughput optimal routing and rate control algorithm for ICNs with minimum delay based on a back-pressure algorithm that is neither based on averaging out or tracking the contacts. The last type of network we study is networks with stationary nodes that are far apart from each other that rely on mobile nodes to communicate with each other. Each mobile transport node can be on one of several fixed routes, and these mobiles drop off or pick up data to and from the stationaries that are on that route. Each route has an associated cost that much be paid by the mobiles to be on (a longer route would have larger cost since it would require the mobile to expend more fuel) and stationaries pay different costs to have a packet picked up by the mobiles on different routes. The challenge in this type of network is to design a distributed route selection algorithm for the mobiles and for the stationaries to stabilize the network and minimize the total network operation cost. The sum cost minimization algorithm based on average source rates and mobility movement pattern would require global knowledge of the rates and movement pattern available at all stationaries and mobiles, rendering such algorithm centralized and weak in the presence of network disruptions. Algorithms based on instantaneous contact, on the contrary, would make them impractical as the mobile-stationary contacts are extremely short and infrequent.Item Designing MIMO interference alignment networks(2012-08) Nosrat Makouei, Behrang; Heath, Robert W., Ph. D.; Andrews, Jeffrey G.; Evans, Brian L.; Hasenbein, John; Nettles, Scott; Vishwanath, SriramWireless networks are increasingly interference-limited, which motivates the development of sophisticated interference management techniques. One recently discovered approach is interference alignment, which attains the maximum sum rate scaling (with signal-to-noise ratio) in many network configurations. Interference alignment is not yet well understood from an engineering perspective. Such design considerations include (i) partial rather than complete knowledge of channel state information, (ii) correlated channels, (iii) bursty packet-based network traffic that requires the frequent setup and tear down of sessions, and (iv) the spatial distribution and interaction of transmit/receive pairs. This dissertation aims to establish the benefits and limitations of interference alignment under these four considerations. The first contribution of this dissertation considers an isolated group of transmit/receiver pairs (a cluster) cooperating through interference alignment and derives the signal-to-interference-plus-noise ratio distribution at each receiver for each stream. This distribution is used to compare interference alignment to beamforming and spatial multiplexing (as examples of common transmission techniques) in terms of sum rate to identify potential switching points between them. This dissertation identifies such switching points and provides design recommendations based on severity of the correlation or the channel state information uncertainty. The second contribution considers transmitters that are not associated with any interference alignment cooperating group but want to use the channel. The goal is to retain the benefits of interference alignment amid interference from the out-of-cluster transmitters. This dissertation shows that when the out-of-cluster transmitters have enough antennas, they can access the channel without changing the performance of the interference alignment receivers. Furthermore, optimum transmit filters maximizing the sum rate of the out-of-cluster transmit/receive pairs are derived. When insufficient antennas exist at the out-of-cluster transmitters, several transmit filters that trade off complexity and sum rate performance are presented. The last contribution, in contrast to the first two, takes into account the impact of large scale fading and the spatial distribution of the transmit/receive pairs on interference alignment by deriving the transmission capacity in a decentralized clustered interference alignment network. Channel state information uncertainty and feedback overhead are considered and the optimum training period is derived. Transmission capacity of interference alignment is compared to spatial multiplexing to highlight the tradeoff between channel estimation accuracy and the inter-cluster interference; the closer the nodes to each other, the higher the channel estimation accuracy and the inter-cluster interference.Item Exploiting temporal stability and low-rank structure for localization in mobile networks(2010-08) Rallapalli, Swati; Zhang, Yin, doctor of computer science; Qiu, Lili, Ph. D.Localization is a fundamental operation for many wireless networks. While GPS is widely used for location determination, it is unavailable in many environments either due to its high cost or the lack of line of sight to the satellites (e.g., indoors, under the ground, or in a downtown canyon). The limitations of GPS have motivated researchers to develop many localization schemes to infer locations based on measured wireless signals. However, most of these existing schemes focus on localization in static wireless networks. As many wireless networks are mobile (e.g., mobile sensor networks, disaster recovery networks, and vehicular networks), we focus on localization in mobile networks in this thesis. We analyze real mobility traces and find that they exhibit temporal stability and low-rank structure. Motivated by this observation, we develop three novel localization schemes to accurately determine locations in mobile networks: 1. Low Rank based Localization (LRL), which exploits the low-rank structure in mobility. 2. Temporal Stability based Localization (TSL), which leverages the temporal stability. 3. Temporal Stability and Low Rank based Localization (TSLRL), which incorporates both the temporal stability and the low-rank structure. These localization schemes are general and can leverage either mere connectivity (i.e., range-free localization) or distance estimation between neighbors (i.e., range-based localization). Using extensive simulations and testbed experiments, we show that our new schemes significantly outperform state-of-the-art localization schemes under a wide range of scenarios and are robust to measurement errors.Item Exploring tradeoffs in wireless networks under flow-level traffic: energy, capacity and QoS(2009-12) Kim, Hongseok; De Veciana, GustavoWireless resources are scarce, shared and time-varying making resource allocation mechanisms, e.g., scheduling, a key and challenging element of wireless system design. In designing good schedulers, we consider three types of performance metrics: system capacity, quality of service (QoS) seen by users, and the energy expenditures (battery lifetimes) incurred by mobile terminals. In this dissertation we investigate the impact of scheduling policies on these performance metrics, their interactions, and/or tradeoffs, and we specifically focus on flow-level performance under stochastic traffic loads. In the first part of the dissertation we evaluate interactions among flow-level performance metrics when integrating QoS and best effort flows in a wireless system using opportunistic scheduling. We introduce a simple flow-level model capturing the salient features of bandwidth sharing for an opportunistic scheduler which ensures a mean throughput to each QoS stream on every time slot. We show that the integration of QoS and best effort flows results in a loss of opportunism, which in turn results in a reduction of the stability region, degradation in system capacity, and increased file transfer delay. In the second part of the dissertation we study several ways in which mobile terminals can backoff on their uplink transmit power (thus slow down their transmissions) in order to extend battery lifetimes. This is particularly effective when a wireless system is underloaded, so the degradation in the users' perceived performance can be negligible. The challenge, however, is developing a mechanism that achieves a good tradeoff among transmit power, idling/circuit power, and the performance customers will see. We consider systems with flow-level dynamics supporting either real-time or best effort (e.g., file transfers) sessions. We show that significant energy savings can be achieved by leveraging dynamic spare capacity. We then extend our study to the case where mobile terminals have multiple transmit antennas. In the third part of the dissertation we develop a framework for user association in infrastructure-based wireless networks, specifically focused on adaptively balancing flow loads given spatially inhomogeneous traffic distributions. Our work encompasses several possible user association objective functions resulting in rate-optimal, throughput-optimal, delay-optimal, and load-equalizing policy, which we collectively denote [alpha]-optimal user association. We prove that the optimal load vector that minimizes this function is the fixed point of a certain mapping. Based on this mapping we propose an iterative distributed user association policy and prove that it converges to the globally optimal decision in steady state. In addition we address admission control policies for the case where the system cannot be stabilized.Item Fundamentals of distributed transmission in wireless networks : a transmission-capacity perspective(2011-05) Liu, Chun-Hung; Andrews, Jeffrey G.; Shakkottai, Sanjay; Arapostathis, Ari; Morton, David; Vishwanath, SriramInterference is a defining feature of a wireless network. How to optimally deal with it is one of the most critical and least understood aspects of decentralized multiuser communication. This dissertation focuses on distributed transmission strategies that a transmitter can follow to achieve reliability while reducing the impact of interference. The problem is investigated from three directions : distributed opportunistic scheduling, multicast outage and transmission capacity, and ergodic transmission capacity, which study distributed transmission in different scenarios from a transmission-capacity perspective. Transmission capacity is spatial throughput metric in a large-scale wireless network with outage constraints. To understand the fundamental limits of distributed transmission, these three directions are investigated from the underlying tradeoffs in different transmission scenarios. All analytic results regarding the three directions are rigorously derived and proved under the framework of transmission capacity. For the first direction, three distributed opportunistic scheduling schemes -- distributed channel-aware, interferer-aware and interferer-channel-aware scheduling are proposed. The main idea of the three schemes is to avoid transmitting in a deep fading and/or sever interfering context. Theoretical analysis and simulations show that the three schemes are able to achieve high transmission capacity and reliability. The second direction focuses on the study of the transmission capacity problem in a distributed multicast transmission scenario. Multicast transmission, wherein the same packet must be delivered to multiple receivers, has several distinctive traits as opposed to more commonly studied unicast transmission. The general expression for the scaling law of multicast transmission capacity is found and it can provide some insight on how to do distributed single-hop and multi-hop retransmissions. In the third direction, the transmission capacity problem is investigated for Markovain fading channels with temporal and spatial ergodicity. The scaling law of the ergodic transmission capacity is derived and it can indicate a long-term distributed transmission and interference management policy for enhancing transmission capacity.Item High-performance scheduling algorithms for wireless networks(2010-12) Bodas, Shreeshankar Ravishankar; Vishwanath, Sriram; Shakkottai, Sanjay; Caramanis, Constantine; de Veciana, Gustavo; Hasenbein, John; Srikant, R.The problem of designing scheduling algorithm for multi-channel (e.g., OFDM-based) wireless downlink networks is considered, where the system has a large bandwidth and proportionally large number of users to serve. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, it is shown that it has zero rate function in our setting). To address this, a class of algorithms called iHLQF (iterated Heaviest matching with Longest Queues First) is proposed. The algorithms in this class are shown to be throughput-optimal for a general class of arrival/channel processes, and also rate-function optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes, where the channel-rates are 0 or 1 packets per timeslot. iHLQF however has higher computational complexity than MaxWeight (n⁴ vs. n² computations per timeslot respectively). To overcome this issue, a new algorithm called SSG (Server-Side Greedy) is proposed. It is shown that SSG is throughput-optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n²) that is comparable to the MaxWeight algorithm. Thus, it provides a nice trade-off between buffer-overflow performance and computational complexity. For multi-rate channel processes, where the channels can serve multiple packets per timeslot, new Markov chain-based coupling arguments are used to derive rate-function positivity results for the SSG algorithm. Finally, an algorithm called DMEQ is proposed and shown to be rate-function optimal for certain multi-rate channel scenarios, whose definition characterizes the sufficient conditions for rate-function optimality in this regime. These results are validated by both analysis and simulations.Item Improving performance and incentives in disruption-tolerant networks(2010-08) Shevade, Upendra; Zhang, Yin, doctor of computer science; Browne, James; Mok, Aloysius; Qiu, Lili; Vin, HarrickThe recent proliferation of personal wireless devices has led to the emergence of disruption-tolerant networks (DTNs), which are characterized by intermittent connectivity among some or all participating nodes and a consequent lack of contemporaneous end-to-end paths between the source and consumer of information. However, the success of DTNs as a communication paradigm is critically dependent on the following challenges being addressed: (1) How to enable popular but demanding applications, such as video-on-demand, to operate in such constrained network settings, and (2) How to incentivize individual devices to cooperate when network operation is only possible under, or greatly benefits from cooperation. In this dissertation, we present a novel set of protocols and develop real systems that effectively meet the above challenges. We make the following contributions: First, we design and implement a novel system for enabling high bandwidth content distribution in vehicular DTNs by leveraging infrastructure access points (APs). We predict which APs will soon be visited by a vehicular node and then proactively push content-of-interest to those APs. Our replication schemes optimize content delivery by exploiting Internet connectivity, local wireless connectivity, node relay connectivity and mesh connectivity among APs. We demonstrate the effectiveness of our system through trace-driven simulation and Emulab emulation using real taxi and bus traces. We further deploy our system in two vehicular networks: a fourteen AP 802.11b network and a four AP 802.11n network with smartphones and laptops as clients. Second, we propose an incentive-aware routing protocol for DTNs. In DTNs, routing takes place in a store-and-forward fashion with the help of relay nodes. If the nodes in a DTN are controlled by rational entities, such as people or organizations, the nodes can be expected to behave selfishly by attempting to maximize their utilities and conserve their resources. Since routing is inherently a cooperative activity, system operation will be critically impaired unless cooperation is incentivized. We propose the use of pair-wise tit-for-tat (TFT) as a simple, robust and practical incentive mechanism for DTNs. We then develop an incentive-aware routing protocol that allows selfish nodes to maximize their own performance while conforming to TFT constraints.Item Improving the performance and efficiency of wireless networks using rate adaptation(2015-12) Khan, Muhammad Owais; Vishwanath, Sriram; Qiu, Lili, Ph. D.; de Veciana, Gustavo; Julien, Christine; Gouda, MohamedRecent years have seen a staggering increase in the deployment and utilization of wireless networks. More and more devices are being equipped with Wireless LAN (WLAN) cards to take advantage of the omnipresence of WLAN networks. Therefore, it has become necessary that the protocols used by WLANs are efficient and provide good performance. Rate Adaptation protocols are an important mechanism employed by WLANs to improve network performance. This dissertation develops three complementary techniques, which use rate adaptation to optimize and improve performance by i) performing rate adaptation to optimize energy consumption, ii) developing a more accurate technique to predict the frame delivery ratio that is used by rate adaptation protocols, and iii) jointly optimizing rate adaptation with data retransmission to maximize throughput. More specifically, in i), we use extensive measurements to develop a simple yet accurate energy consumption model for 802.11n wireless cards. We use the model to drive the design of an energy aware rate adaptation scheme. A major benefit of a model-based rate adaptation is that applying a model allows us to eliminate frequent probes required in many existing rate adaptation schemes. In ii), we find that the accuracy of existing delivery ratio calculation techniques is still limited due to bursty errors inherent to the wireless channel. We develop a new method for computing packet delivery rate that captures the burstiness of errors. Furthermore, we propose a new data interleaving technique, which leverages our framework to reduce the burstiness of errors, thereby improving frame delivery ratio. Finally, in iii), we address the susceptibility of wireless networks to transmission failures due to dynamic channel conditions and unpredictable interference. To efficiently recover from failures, we propose a retransmission scheme where the receiver combines information received from multiple failed transmissions associated with the same frame. The protocol has two distinguishing features. First, it simultaneously supports partial retransmission and combines bits with low confidence. Second, it jointly optimizes the data rate of the retransmission and the information to be retransmitted to maximize throughput.Item Improving the performance of wireless networks using frame aggregation and rate adaptation(2010-12) Kim, Won Soo, 1975-; Nettles, Scott M.; de Veciana, Gustavo; Heath, Robert W.; Julien, Christine; Qiu, LiliAs the data rates supported by the physical layer increase, overheads increasingly dominate the throughput of wireless networks. A promising approach for reducing overheads is to group a number of frames together into one transmission. This can reduce the impact of overheads by sharing headers and the time spent waiting to gain access to the transmission floor. Traditional aggregation schemes require that frames that are aggregated all be destined to the same receiver. These approaches neglect the fact that transmissions are broadcast and a single transmission will potentially be received by many receivers. Thus, by taking advantage of the broadcast nature of wireless transmissions, overheads can be amortized over more data and achieve more performance gain. To show this, we design a series of MAC-based aggregation protocols that take advantage of rate adaptation and the broadcast nature of wireless transmissions. We first show the design of a system that can aggregate both unicast and broadcast frames. Further, the system can classify TCP ACK segments so that they can be aggregated with TCP data flowing in the opposite direction. Second, we develop a rate-adaptive frame aggregation scheme that allows us to find the best aggregation size by tracking the size based on received data frames and the data rate chosen by rate adaptation. Third, we develop a multi-destination frame aggregation scheme to aggregate broadcast frames and unicast frames that are destined for different receivers using delayed ACKs. Using a delayed ACK scheme allows multiple receivers to control transmission time of the ACKs. Finally, we extend multi-destination rate-adaptive frame aggregation to allow piggybacking of various types of metadata with user packets. This promises to lower the impact of metadata-based control protocols on data transport. A novel aspect of our work is that we implement and validate the designs not through simulation, but rather using our wireless node prototype, Hydra, which supports a high performance PHY based on 802.11n. To validate our designs, we conduct extensive experiments both on real and emulator-based channels and measure system performance.Item Interference management with limited channel state information in wireless networks(2014-12) Lee, Namyoon; Heath, Robert W., Ph. D.; Baccelli, F. (François), 1954-Interference creates a fundamental barrier in attempting to improve throughput in wireless networks, especially when multiple concurrent transmissions share the wireless medium. In recent years, significant progress has been made on characterizing the capacity limits of wireless networks under the premise of global and instantaneous channel state information at transmitter (CSIT). In practice, however, the acquisition of such instantaneous and global CSIT as a means toward cooperation is highly challenging due to the distributed nature of transmitters and dynamic wireless propagation environments. In many limited CSIT scenarios, the promising gains from interference management strategies using instantaneous and global CSIT disappear, often providing the same result as cases where there is no CSIT. Is it possible to obtain substantial performance gains with limited CSIT in wireless networks, given previous evidence that there is marginal or no gain over the case with no CSIT? To shed light on the answer to this question, in this dissertation, I present several achievable sum of degrees of freedom (sum-DoF) characterizations of wireless networks. The sum-DoF is a coarse sum-capacity approximation of the networks, deemphasizing noise effects. These characterizations rely on a set of proposed and existing interference management strategies that exploit limited CSIT. I begin with the classical multi-user multiple-input-single-output (MISO) broadcast channel with delayed CSIT and show how CSI feedback delays change sum-capacity scaling law by proposing an innovative interference alignment technique called space-time interference alignment. Next, I consider interference networks with distributed and delayed CSIT and show how to optimally use distributed and moderately-delayed CSIT to yield the same sum-DoF as instantaneous and global CSIT using the idea of distributed space-time interference alignment. I also consider a two-hop layered multiple-input-multiple-output (MIMO) interference channel, where I show that two cascaded interfering links can be decomposed into two independent parallel relay channels without using CSIT at source nodes through the proposed interference-free relaying technique. Then I go beyond one-way and layered to multi-way and fully-connected wireless networks where I characterize the achievable sum-DoF of networks where no CSIT is available at source nodes using the proposed space-time physical-layer network coding. Lastly, I characterize analytical expressions for the sum spectral efficiency in a large-scale single-input-multiple- output (SIMO) interference network where the spatial locations of nodes are modeled by means of stochastic geometry. I derive analytical expressions for the ergodic sum spectral efficiency and the scaling laws as functions of relevant system parameters depending on different channel knowledge assumptions at receivers.Item Low-overhead cooperation to mitigate interference in wireless networks(2013-05) Peters, Steven Wayne; Heath, Robert W., Ph. D.Wireless cellular networks, which serve a large area by geographically partitioning users, suffer from interference from adjacent cells transmitting in the same frequency band. This interference can theoretically be completely mitigated via transceiver cooperation in both the uplink and downlink. Optimally, base stations serving the users can utilize high-capacity backbones. to jointly transmit and receive all the data in the network across all the base stations. In reality, the backbone connecting the base stations is of finite capacity, limiting joint processing to localized clusters. Even with joint processing on a small scale, the overhead involved in sharing data between multiple base stations is large and time-sensitive. Other forms of cooperation have been shown to require less overhead while exhibiting much of the performance benefit from interference mitigation. One particular strategy, called interference alignment (IA), has been shown to exploit all the spatial degrees of freedom in the channel provided data cannot be shared among base stations. Interference alignment was developed for the multi-user interference channel to exploit independent channel observations when all of the links in the network have high signal-to-noise ratio, and assumes all the nodes utilizing the physical resources are participating in the cooperative protocol. When some or all of the links are at moderate signal-to-noise ratio, or when there are non-cooperating users, IA is suboptimal. In this dissertation, I take three approaches to addressing the drawbacks of IA. First, I develop cooperative transmission strategies that outperform IA in various operationg regimes, including at low-to-moderate SNR and in the presence of non-cooperating users. These strategies have the same complexity and overhead as IA. I then develop algorithms for network partitioning by directly considering the overhead of cooperative strategies. Partitioning balances the capacity gains of cooperation with the overhead required to achieve them. Finally, I develop the shared relaying model, which is equivalent to the interference channel but with a single multi-antenna relay mediating communications between transceivers. The shared relay requires less overhead and cooperation than interference alignment but requires added infrastructure. It is shown to outperform conventional relaying strategies in cellular networks with a fixed number of total relay antennas.Item On distributed scheduling for wireless networks with time-varying channels(2013-05) Reddy, Akula Aneesh; Shakkottai, SanjayWireless scheduling is a fundamental problem in wireless networks that involves scheduling transmissions of multiple users in order to support data flows with as high rates as possible. This problem was first addressed by Tassuilas and Ephremides, resulting in the celebrated Back-Pressure network scheduling algorithm. This algorithm schedules network links to maximize throughput in an opportunistic fashion using instantaneous network state information (NSI), i.e., queue and channel state knowledge across the entire network. However, the Back-Pressure (BP) algorithm suffers from various drawbacks - (a) it requires knowledge of instantaneous NSI from the whole network, i.e. feedback about time-varying channel and queue states from all links of the network, (b) the algorithm requires solving a global optimization problem at each time to determine the schedule, making it highly centralized. Further, Back-pressure algorithm was originally designed for wireless networks where interference is modeled using protocol interference model. As recent break-throughs in full-duplex communications and interference cancelation techniques provide greatly increased capacity and scheduling flexibility, it is not clear how BP algorithm can be modified to improve the data rates and reduce the delay. In this thesis, we address the drawbacks of Back-Pressure algorithm to some extent. In particular, our first work provides a new scheduling algorithm (similar to BP) that allows users to make individual decisions (distributed) based on heterogeneously delayed network state information (NSI). Regarding the complexity issue, in our second work, we analyze the performance of the greedy version of BP algorithm, known as Greedy Maximal Scheduling (GMS) and understand the effect of channel variations on the performance of GMS. In particular, we characterize the efficiency ratio of GMS in wireless networks with fading. In our third and fourth work, we propose and analyze new scheduling algorithms that can benefit from new advancements in interference cancelation techniques.Item Resource allocation in large-scale multi-server systems(2014-12) Moharir, Sharayu Arun; Shakkottai, Sanjay; Sanghavi, Sujay Rajendra, 1979-The focus of this dissertation is the task of resource allocation in multi- server systems arising from two applications – multi-channel wireless com- munication networks and large-scale content delivery networks. The unifying theme behind all the problems studied in this dissertation is the large-scale nature of the underlying networks, which necessitate the design of algorithms which are simple/greedy and therefore scalable, and yet, have good perfor- mance guarantees. For the multi-channel multi-hop wireless communication networks we consider, the goal is to design scalable routing and scheduling policies which stabilize the system and perform well from a queue-length and end-to-end delay perspective. We first focus on relay assisted downlink networks where it is well understood that the BackPressure algorithm is stabilizing, but, its delay performance can be poor. We propose an alternative algorithm - an iterative MaxWeight algorithm and show that it stabilizes the system and outperforms the BackPressure algorithm. Next, we focus on wireless networks which serve mobile users via a wide-area base-station and multiple densely deployed short- range access nodes (e.g., small cells). We show that traditional algorithms that forward each packet at most once, either to a single access node or a mobile user, do not have good delay performance and propose an algorithm (a distributed scheduler - DIST) and show that it can stabilize the system and performs well from a queue-length/delay perspective. In content delivery networks, each arriving job can only be served by servers storing the requested content piece. Motivated by this, we consider two settings. In the first setting, each job, on arrival, reveals a deadline and a subset of servers that can serve it and the goal is to maximize the fraction of jobs that are served before their deadlines. We propose an online load balanc- ing algorithm which uses correlated randomness and prove its optimality. In the second setting, we study content placement in a content delivery network where a large number of servers, serve a correspondingly large volume of con- tent requests arriving according to an unknown stochastic process. The main takeaway from our results for this setting is that separating the estimation of demands and the subsequent use of the estimations to design optimal content placement policies (learn-and-optimize approach) is suboptimal. In addition, we study two simple adaptive content replication policies and show that they outperform all learning-based static storage policies.Item Robust optimization and machine learning tools for adaptive transmission in wireless networks(2011-12) Yun, Sung-Ho; Caramanis, Constantine; de Veciana, Gustavo; Ghosh, Joydeep; Heath, Robert W.; Qiu, LiliCurrent and emerging wireless systems require adaptive transmissions to improve their throughput, to meet the QoS requirements or to maintain robust performance. However finding the optimal transmit parameters is getting more difficult due to the growing number of wireless devices that share the wireless medium and the increasing dimensions of transmit parameters, e.g., frequency, time and spatial domain. The performance of adaptive transmission policies derived from given measurements degrade when the environment changes. The policies need to either build up protection against those changes or tune themselves accordingly. Also, an adaptation for systems that take advantages of transmit diversity with finer granularity of resource allocation is hard to come up with due to the prohibitively large number of explicit and implicit environmental variables to take into account. The solutions to the simplified problems often fail due to incorrect assumptions and approximations. In this dissertation, we suggest two tools for adaptive transmission in changing complex environments. We show that adjustable robust optimization builds up protection upon the adaptive resource allocation in interference limited cellular broadband systems, yet maintains the flexibility to tune it according to temporally changing demand. Another tool we propose is based on a data driven approach called Support Vectors. We develop adaptive transmission policies to select the right set of transmit parameters in MIMO-OFDM wireless systems. While we don't explicitly consider all the related parameters, learning based algorithms implicitly take them all into account and result in the adaptation policies that fit optimally to the given environment. We extend the result to multicast traffic and show that the distributed algorithm combined with a data driven approach increases the system performance while keeping the required overhead for information exchange bounded.Item Self organizing networks : building traffic and environment aware wireless systems(2009-08) Rengarajan, Balaji; de Veciana, GustavoThis dissertation investigates how to optimize flow-level performance in interference dominated wireless networks serving dynamic traffic loads. The schemes presented in this dissertation adapt to long-term (hours) spatial load variations, and the main metrics of interest are the file transfer delay or average flow throughput and the mean power expended by the transmitters. The first part presents a system level approach to interference management in an infrastructure based wireless network with full frequency reuse. The key idea is to use loose base station coordination that is tailored to the spatial load distribution and the propagation environment to exploit the diversity in a user population's sensitivity to interference. System architecture and abstractions to enable such coordination are developed for both the downlink and the uplink cases, which present differing interference characteristics. The basis for the approach is clustering and aggregation of traffic loads into classes of users with similar interference sensitivities that enable coarse grained information exchange among base stations with greatly reduced communication overheads. The dissertation explores ways to model and optimize the system under dynamic traffic loads where users come and go resulting in interference induced performance coupling across base stations. Based on extensive system-level simulations, I demonstrate load-dependent reductions in file transfer delay ranging from 20-80% as compared to a simple baseline not unlike systems used in the field today, while simultaneously providing more uniform coverage. Average savings in user power consumption of up to 75% are achieved. Performance results under heterogeneous spatial loads illustrate the importance of being traffic and environment aware. The second part studies the impact of policies to associate users with base stations/access points on flow-level performance in interference limited wireless networks. Most research in this area has used static interference models (i.e., neighboring base stations are always active) and resorted to intuitive objectives such as load balancing. In this dissertation, it is shown that this can be counter productive, and that asymmetries in load can lead to significantly better performance in the presence of dynamic interference which couples the transmission rates experienced by users at various base stations. A methodology that can be used to optimize the performance of a class of coupled systems is proposed, and applied to study the user association problem. It is demonstrated that by properly inducing load asymmetries, substantial performance gains can be achieved relative to a load balancing policy (e.g., 15 times reduction in mean delay). A novel measurement based, interference-aware association policy is presented that infers the degree of interference induced coupling and adapts to it. Systematic simulations establish that both the optimized static and interference-sensitive, adaptive association policies substantially outperform various proposed dynamic policies and that these results are robust to changes in file size distributions, channel parameters, and spatial load distributions.Item Smart RTS/CTS Adaptation(2009-12) Chung, Eui Kyung; Qiu, Lili, 1959-; Zhang, YinHidden terminals are a key reason for performance degradation in wireless networks. When transmitting nodes cannot carrier sense each other, their packets can collide at receiving nodes, causing packet loss. In the IEEE 802.11 protocol, the RTS/CTS mechanism was introduced to combat the hidden terminal problem. While RTS/CTS can help improve network performance when hidden terminals exist, it can decrease the performance in the absence of hidden terminals due to the overhead of sending additional control traffic. For this reason, RTS/CTS is usually disabled in default driver settings. In this thesis, we present an algorithm for dynamically adjusting the use of RTS/CTS. The algorithm, called SmartRTS, continuously monitors traffic feedback in order to decide whether RTS/CTS should be used. The goal is to enable RTS/CTS in the face of hidden terminals and disable RTS/CTS when hidden terminals do not exist. We find SmartRTS to be effective and easily employed. With extensive simulations using both simple and random topologies, we demonstrate the effectiveness of SmartRTS, especially over static RTS/CTS configurations (ie- RTS/CTS enabled or RTS/CTS disabled). SmartRTS can adapt to the appearance and disappearance of hidden terminals and substantially improve overall network throughput by as much as 11-35%.Item Spatial spectrum reuse in wireless networks design and performance(2011-05) Kim, Yuchul; De Veciana, Gustavo; Andrews, Jeffrey G.; Qiu, Lili; Shakkottai, Sanjay; Sanghavi, SujayThis dissertation considers the design, evaluation and optimization of algorithms/ techniques/ system parameters for distributed wireless networks specifically ad-hoc and cognitive wireless networks. In the first part of the dissertation, we consider ad-hoc networks using opportunistic carrier sense multiple access (CSMA) protocols. The key challenge in optimizing the performance of such systems is to find a good compromise among three interdependent quantities: the density and channel quality of the scheduled transmitters, and the resulting interference seen at receivers. We propose two new channel-aware slotted CSMA protocols and study the tradeoffs they achieve amongst these quantities. In particular, we show that when properly optimized these protocols offer substantial improvements relative to regular CSMA -- particularly when the density of nodes is moderate to high. Moreover, we show that a simple quantile based opportunistic CSMA protocol can achieve robust performance gains without requiring careful parameter optimization. In the second part of the dissertation, we study a cognitive wireless network where licensed (primary) users and unlicensed 'cognitive' (secondary) users coexist on shared spectrum. In this context, many system design parameters affect the joint performance, e.g., outage and capacity, seen by the two user types. We explore the performance dependencies between primary and secondary users from a spatial reuse perspective, in particular, in terms of the outage probability, node density and joint network capacity. From the design perspective the key system parameters determining the joint transmission capacity, and tradeoffs, are the detection radius (detection signal to interference and noise power ratio (SINR) threshold) and decoding SINR threshold. We show how the joint network capacity region can be optimized by varying these parameters. In the third part of the dissertation, we consider a cognitive network in a heterogeneous environment, including indoor and outdoor transmissions. We characterize the joint network capacity region under three different spectrum (white space) detection techniques which have different degrees of radio frequency (RF) - environment awareness. We show that cognitive devices relying only on the classical signal energy detection method perform poorly due to limitations on detecting primary transmitters in environments with indoor shadowing. This can be circumvented through direct use (e.g., database access) of location information on primary transmitters, or better yet, on that of primary receivers. We also show that if cognitive devices have positioning information, then the secondary network's capacity increases monotonically with increased indoor shadowing in the environment. This dissertation extends the recent efforts in using stochastic geometric models to capture large scale performance characteristics of wireless systems. It demonstrates the usefulness of these models towards understanding the impact of physical /medium access (MAC) layer parameters and how they might be optimized.Item Transmission strategies for multiple antenna wireless ad-hoc and relay networks(2009-12) Vaze, Rahul; Heath, Robert W.Wireless devices have become an integral part of our everyday lives. Cell-phones, PDA's, Wi-Fi enabled laptops, smart homes and appliances, and automated highway systems are some of the examples of wireless devices and networks in common use. More and more applications and functionalities are constantly being added to these devices, and to support these new applications high data rate communication is required between the wireless devices. Achieving high data rates with wireless communication is impeded by severe fluctuations in the received signal strength (called fading) due to mobility, the exponential attenuation of signal power with distance (called path loss), and interference due to simultaneous transmissions by different users at the same time or over same frequency band. Two of the promising techniques to mitigate the effects of fading, path loss, and interference are: using multiple antennas at the transmitter and receiver, and employing extra nodes (called relays) in between the transmitter and its receiver to relay the transmitter's message to its receiver. This dissertation identifies the optimal transmit and receive strategy with multiple antennas that maximizes the transmission capacity of an ad-hoc wireless network. The transmission capacity is defined as the maximum number of transmitter-receiver pairs that can simultaneously communicate under a per transmission quality of service constraint. This dissertation also presents novel relay transmission strategies for multiple antenna equipped relay based communication that achieve near optimal performance, with Shannon capacity and diversity-multiplexing tradeoff (DMT) as the performance metrics. The Shannon capacity is defined as the maximum rate of reliable communication, while the DMT characterizes the maximum diversity gain for a given value of multiplexing gain in a multiple antenna system. DMT is used as the benchmark, since transmission strategies that meet the DMT are guaranteed to leverage both the advantages of multiple antenna systems.