Layering principles for wireless networks

Kannan, Sreeram

Permalink

https://hdl.handle.net/2142/42398 Copy

Description

Title

Layering principles for wireless networks

Author(s)

Kannan, Sreeram

Issue Date

2013-02-03T19:37:23Z

Director of Research (if dissertation) or Advisor (if thesis)

Viswanath, Pramod

Doctoral Committee Chair(s)

Viswanath, Pramod

Committee Member(s)

• Chekuri, Chandra S.
• Hajek, Bruce
• Kumar, P.R.
• Medard, Muriel
• Srikant, Rayadurgam

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Polymatroidal networks
• flow-cut 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 ever-increasing 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, multiple-access 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., multiple-unicast, 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 multiple-unicast traffic: the min-cut upper bound is within a logarithmic factor of the number of sources of the max-flow. This establishes the approximate capacity of multiple-unicast 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 max-flow min-cut theorem for unicast traffic is known for polymatroidal networks, multiple-unicast traffic has not been studied prior to this work. A key technical contribution of this thesis is an approximate max-flow min-cut theorem for multiple-unicast 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 information-theoretic schemes are employed at the local level (termed as local physical-layer 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 physical-layer channels. Thus our main result can be viewed as a meta-theorem: if there are ``good'' physical-layer schemes for a certain channel, then, for multiple-unicast in a network composed of such channels, a layered architecture is approximately cut-set 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 Steiner-tree packing (so-called 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.

Graduation Semester

2012-12

Permalink

http://hdl.handle.net/2142/42398

Copyright and License Information

Copyright 2012 Sreeram Kannan

Owning Collections