关于Network Coding的开创性工作

April 24, 2010

马上要去CUHK了,这几天在翻IE DEPARTMENT@CUHK里面FACULTY信息,有幸看到了一些真正里程碑式的工作,其中有些很有意思的东西,与大家分享一例。

Robert Li与Raymond Yeung两位教授在00年提出了Network Coding的概念,其本质相当简洁,体现出了数学之美。经典的例子如下面的蝶形网络:A传输2bytes信息x,y到B,C。传统方法,M节点是不编码的,故过来的x,y要通过M节点需要依次排队(即有2bytes的信息需要通过M下面的通道)。现在的方法是,如果M节点对x,y进行简单的编码,向下传递的是XOR(x,y),这样通道就只需要通过1byte的信息。这不仅节省了带宽,也使得延时可以避免。

下面即是关于这个简单定则的论文:Rudolf一作执笔的是从信号传输和图论的角度出发,与他信号处理的背景有关。而Bob Li的文章则是从建立线性向量空间来分析这个问题,虽然自己还没完全读懂,但个人感觉模型相当漂亮,将一个信号传输的问题嵌入到向量计算空间去分析,使得问题能很好的well-formulated。这与BOB LI在Berkeley的纯数学背景有关。

Network Information Flow [2000]
Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Senior Member, IEEE, and Raymond W. Yeung, Senior Member, IEEE trans on Information Theory

Linear Network Coding [2003]
Shuo-Yen Robert Li, Senior Member, IEEE, Raymond W. Yeung, Fellow,
, and Ning Cai,IEEE trans on Information Theory

值得一提的是,第一篇2000年发表的文章在07年的时候引用率只有67(据一个热心网友的07年的博客文章记录),而现在的引用率是1982,我对此表示相当震惊。第二篇文章的引用率也有987。两篇文章均属开创性工作,而且均是本土工作,实属不易。

关于这个Network coding定则的偶然发现,Bob Li还写了篇科普,发在科学美国人上(http://sa.ylib.com/read/readshow.asp?FDocNo=1041&DocNo=1638),读来也别有滋味。

随后follow-up的工作就相当的多了,这个定则渐渐体现出广大应用前景。举一例,MIT的博士Sachin Katti(现在读完直接到Stanford做Assistant Professor), 其一个重要工作就是把这个定则用在了wireless network上,发表论文 XORs  in the air: Practical Wireless Network Coding,IEEE TRANS ON NETWORKING,08年才出来的工作,目前为止引用率已达562。。。

再八卦一下:遗憾的是开山鼻祖CUHK的Prof. Bob Li和Prof. Raymond Yeung在发表这个理论工作之后没有很好地继续做下去。被美国人搞热后才发现其中的诸多工程应用前景,于是于09年9月,两人牵头到港政府搞了个大项目,经费HKD 100,000,000 。。。ORZ

——————————

近期CVPR2010 paper on web出来了,大致扫了扫,一如既往的热闹。但在这热闹和喧嚣的背后,多少能是真正学术上和工程上的贡献呢?不说了,老实读书做题推公式才是王道。。。

2 Responses to “关于Network Coding的开创性工作”

  1. Go said

    上面的让我想起算法里面的XOR swap。

  2. Bubble said

    To 猛兄的确,XOR不同于+,-等线性operator,用得好有化腐朽为神奇之功效。XOR swap用它节约了一个临时变量,其实network coding最核心的也就是这个XOR,用它节约了带宽!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: