A network coding approach to cross-layer design for data multicast in ad hoc wireless networks

Speaker:	Prof. S.Y. Kung
		Electrical Engineering Department
		Princeton University

Title:		"A network coding approach to cross-layer design for data
		multicast in ad hoc wireless networks"

Date:		Tuesday, 28 Dec 2004

Time:		4-5pm

Venue:		Room 3006 (Phase I, via lift no.3)
		HKUST

Abstract:

Whereas routing is the prevailing technology in the Internet, network
coding has recently emerged as a promising generalization by allowing
nodes to mix and then forward information received on its incoming links.
For example, network coding (but not routing) can achieve the maximum
throughput for multicasting data from one source to multiple destinations
(Ahlswede et al. ). On the other hand, coding is more costly than routing.
In a fundamental graph theorem, Edmonds showed routing alone is sufficient
(and therefore more cost-effective) to achieve the capacity, if the source
is to broadcast data to all other nodes.  It is therefore natural to pose
a question on how to achieve the best of both worlds, namely reaching the
maximum throughput with minimum complexity. The answer hinges upon a new
discovery that the optimal capacity can still be achieved under the
restriction that coding is used only on links entering relay nodes. This
important finding is cast as a unified theor em which includes the
above-mentioned main theorems on network coding and routing as special
cases.

In the second part of the talk, I will address optimal cross-layer designs
of wireless networks. Using bit-rate resources as the currency, the
physical and medium access layers are modeled as the supply side and the
network layer is modeled as the demand side. To facilitate the joint
optimization of the supply and demand, he reduced the supply side into a
graph coloring problem and the demand side into a network coding problem,
both expressible in linear inequalities. This approach explicitly reveals
the balance between the supply and demand and moreover, optimally exploits
the rich design freedom inherent in a wireless network. Under this model,
the minimum-energy multicast problem in mobile ad hoc networks can now be
formulated as a linear optimization problem. The advantages over the
conventional routing approach are two-fold: (1) better energy-efficiency,
and (2) polynomial solvability instead of NP-hardness.


******************
Biography:

Professor S.Y. Kung received his Ph.D. Degree in Electrical Engineering
from Stanford University. In 1974, he was an Associate Engineer of Amdahl
Corporation, Sunnyvale, CA. From 1977 to 1987, he was a Professor of
Electrical Engineering-Systems of the University of Southern California,
L.A. Since 1987, he has been a Professor of Electrical Engineering at the
Princeton University. In addition, he held a Visiting Professorship at the
Stanford University (1984);  and a Visiting Professorship at the Delft
University of Technology (1984); a Toshiba Chair Professorship at the
Waseda University, Japan (1984); an Honorary Professorship at the Central
China University of Science and Technology (1994);  and a Distinguished
Chair Professorship at the Hong Kong Polytechnic University since 2001.
His research interests include VLSI array processors, system modelling and
identification, neural networks, wireless communication, sensor array
processing, multimedia signal processing, bioinformatic data mining and
biometric authentication.

Professor Kung is a Fellow of IEEE since 1988.  Since 1990, he has been
the Editor-In-Chief of the Springer's Journal of VLSI Signal Processing
Systems. He was a recipient of IEEE Signal Processing Society's Technical
Achievement Award for his contributions on "parallel processing and neural
network algorithms for signal processing" (1992);  a Distinguished
Lecturer of IEEE Signal Processing Society (1994); a recipient of IEEE
Signal Processing Society's Best Paper Award for his publication on
principal component neural networks (1996); and a recipient of the IEEE
Third Millennium Medal (2000). Professor Kung has co-authored more than
400 technical publications and numerous textbooks including "VLSI and
Modern Signal Processing," with Russian translation, Prentice-Hall (1985),
"VLSI Array Processors", with Russian and Chinese translations,
Prentice-Hall (1988); "Digital Neural Networks", Prentice-Hall (1993);
"Principal Component Neural Networks", John-Wiley (1996); and
"Biometric Authentication: A Machine Learning and Neural Network
Approach", Prentice-Hall (2004).