Files in this item
Files  Description  Format 

application/pdf Sreeram_Kannan.pdf (1MB)  (no description provided) 
Description
Title:  Layering principles for wireless networks 
Author(s):  Kannan, Sreeram 
Director of Research:  Viswanath, Pramod 
Doctoral Committee Chair(s):  Viswanath, Pramod 
Doctoral Committee Member(s):  Chekuri, Chandra S.; Hajek, Bruce; Kumar, P.R.; Medard, Muriel; Srikant, Rayadurgam 
Department / Program:  Electrical & Computer Eng 
Discipline:  Electrical & Computer Engr 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Polymatroidal networks
flowcut gaps capacity wireless networks information theory approximation algorithms Information Flow local physical layer global routing network coding layering fading channels function computation Steiner packing duality. 
Abstract:  The need to deliver increasing amounts of data over a fixed bandwidth in wireless networks necessitates the engineering of communication schemes with everincreasing efficiencies. In this context, it is imperative to obtain a fundamental understanding of wireless networks and the engineering architectures that can achieve optimal performance. Accordingly, understanding the capacity, i.e., the maximum information rate supported by wireless networks, is a central aim in the field of information theory. This understanding has been successfully obtained for the case of small canonical networks (called channels, for example, broadcast, multipleaccess and interference channels) and for networks under restricted traffic models (for example, unicast, multicast and broadcast). In this thesis, the main goal is to understand the capacity of general wireless networks under a general traffic model, i.e., multipleunicast, in which there are multiple sources intending to communicate independent information with multiple destinations. A classical result in undirected wireline networks is the near optimality of routing (flow) for multipleunicast traffic: the mincut upper bound is within a logarithmic factor of the number of sources of the maxflow. This establishes the approximate capacity of multipleunicast in wireline networks. In this thesis, we ``extend'' this wireline result to the wireless context. In order to accomplish this, we propose a new model for wireless networks, namely, the polymatroidal network model. In a standard wireline network, the rate of information flow on each edge is constrained by its capacity; in the polymatroidal network model, the capacity of edges that meet at a node are further jointly constrained by a submodular function. While a maxflow mincut theorem for unicast traffic is known for polymatroidal networks, multipleunicast traffic has not been studied prior to this work. A key technical contribution of this thesis is an approximate maxflow mincut theorem for multipleunicast in undirected polymatroidal networks (the approximation has a multiplicative logarithmic gap). Our key tools are the formulation and analysis of the dual of the flow relaxations via continuous extensions of submodular functions, in particular the Lovasz extension, and the use of metric embeddings into the real line with low average distortion. In order to translate these results from polymatroidal networks to wireless networks, we propose a natural layered architecture in which informationtheoretic schemes are employed at the local level (termed as local physicallayer schemes) and routing is employed at the global level. We show that the feedback and symmetry inherent in wireless networks plays a crucial role in enabling this separation, by demonstrating that the layered architecture is approximately optimal. This result is formally demonstrated for wireless networks under a variety of channel models for which capacity results are known for the corresponding local physicallayer channels. Thus our main result can be viewed as a metatheorem: if there are ``good'' physicallayer schemes for a certain channel, then, for multipleunicast in a network composed of such channels, a layered architecture is approximately cutset achieving. Finally, we turn our attention to the more general problem of function computation. In the function computation problem, certain nodes of an undirected graph have access to independent data, while some other nodes of the graph require certain functions of the data; this model is motivated by sensor networks and cloud computing. We study the maximum rates at which function computation is possible on a capacitated graph; the capacities on the edges of the graph impose constraints on the communication rate. We consider a simple class of computation strategies based on Steinertree packing (socalled computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, the performance of computation trees is known to be optimal when the underlying graph is itself a directed tree, but can be arbitrarily poor in general directed graphs. Our main result is that computation trees are near optimal for several classes of function computation requirements even at multiple terminals in undirected graphs. The key technical contribution here involves connecting prior work in approximation algorithms for Steiner cuts in undirected graphs to the function computation problem. We also demonstrate a certain ``duality'' between the function computation problem and a communication problem involving multiple multicasts. 
Issue Date:  20130203 
URI:  http://hdl.handle.net/2142/42398 
Rights Information:  Copyright 2012 Sreeram Kannan 
Date Available in IDEALS:  20130203 
Date Deposited:  201212 
This item appears in the following Collection(s)

Dissertations and Theses  Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois