Abstract/Details

On joint coding and combinatorial optimization in communication networks


2007 2008

Other formats: Order a copy

Abstract (summary)

Traditionally, information flows in communication networks are treated as commodity flows. Network coding is a new technique that allows nodes to manipulate the information content arbitrarily inside the network. Essentially, it raises a new joint coding and routing optimization question that needs to be addressed by exploiting both information theory and network combinatorics. This work focuses on the joint coding/routing optimization for throughput, energy consumption, and robustness of wired and wireless networks.

We study three sub-problems within this general setup: minimize communication cost of collecting correlated data through a network at a sink; maximize the throughput of multi-pair independent unicast traffic in wireless networks; and maximize the data utility in random, unreliable wireless data collection networks. For the correlated data gathering problem, we introduce an original concept called distance entropy that characterizes the spatial distribution of information at networked sources and shows that it is a meaningful metric as the tight lower bound of the minimum communication cost for collecting the sources at a single sink. We also propose a practical coding/routing algorithm called Hierarchical Difference Broadcasting (HDB) that achieves an order optimal performance yet simple to implement. For the second multi-pair unicast problem, we characterize the throughput capacity order and show coding combined with wireless broadcasting provides no order difference improvement. We also derive tighter bounds for the constant factor. For the third problem, we model the scheduling problem into a Multi-Armed Bandit (MAB) problem and derive the optimal solution using Gittins Indices.

Indexing (details)


Subject
Electrical engineering;
Information systems;
Computer science
Classification
0544: Electrical engineering
0723: Information systems
0984: Computer science
Identifier / keyword
Communication and the arts, Applied sciences, Communication networks, Distance entropy, Joint coding and scheduling, Minimum cost, Multipair unicast throughput, Network coding, Source coding
Title
On joint coding and combinatorial optimization in communication networks
Author
Liu, Junning
Number of pages
158
Publication year
2007
Degree date
2008
School code
0118
Source
DAI-B 69/07, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
9780549663997
Advisor
Adler, Micah; Towsley, Donald
Committee member
Adler, Micah; Goeckel, Dennis L.; Kurose, James; Towsley, Donald; Xia, Cathy H.
University/institution
University of Massachusetts Amherst
Department
Computer Science
University location
United States -- Massachusetts
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
3315519
ProQuest document ID
304847613
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/304847613
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.