network coding

network coding

Network Coding中文譯名為網路編碼,是2000年Ahlswede等人在IEEE Transactions on Information Theory上發表的論文《Network Information Flow》最先提出來的。Network Coding主要用於多播網路中,在節點進行編碼以提高信息傳輸速率。按傳統方案,節點一般是使用“存儲-轉發”機制的路由器,由於傳統觀點認為“在中間節點上對數據進行加工不會帶來收益”,所以路由器不對信息本身進行處理。網路編碼則在節點上對數據進行處理,從而提高了信息的傳輸率。

基本介紹

  • 中文名網路編碼
  • 外文名:network coding
  • 出自:《Network Information Flow》
  • 主要用於:多播網路中
簡介,主要創始人,Rudolf Ahlswede,Ning Cai,Shuo-Yen Robert Li,Raymond W. Yeung,主要研究文獻,相關研究情況,發展歷史,相關學術會議,The IEEE International Symposium,中國電子學會資訊理論分會主辦,其它會議,國內主要研究情況和進展,

簡介

用編碼器取代傳統的路由器,傳送的是有關信息的證據而不是信息本身,到達接收端後,信息被重新組裝。對於多播網路,一個源給多個接收者傳送信息,為了達到最大流量,提高網路資源的利用率,有必要在節點上對信息進行編碼。
如右圖,考慮一個源(Source)要同時傳送A,B兩條信息給兩個接收者(Receivers),如果使用傳統的路由器,中間一條鏈路同一時間只能傳送A或者B,所以,在一個單位時間內,只有一個Receiver能拿到完整的A和B,另一個接收者只能再等下一個單位時間。
若採用圖中的方法,在中間第一個節點裡,收到A和B後,先求A⊕B(異或),由於A和B具有相同的長度,則,A⊕B後,長度與A或者B長度相同,所以,傳送A+B只需要一個單位時間。所以,兩個Receiver可以同時拿到A,A⊕B,或者B,A⊕B,然後,求A⊕(A⊕B),即可得到B,求B⊕(A⊕B)得到A,相當於兩個Receivers同時拿到了A和B。
這樣一來,通信容量達到了原頻寬的兩倍了!

主要創始人

Rudolf Ahlswede

Prof. Rudolf Ahlswede, 男,1938年出生於德國,德國University of Bielefeld大學教授.
 1966年獲德國哥廷根大學(Göttingen,導師是Konrad Jacobs)數學博士學位(Dr.rer.nat. degree in mathematics from the University of Gottingen, Germany, in 1966. ), 論文標題為"Contributions to the Shannon information theory in case of non-stationary channels"(對於數學專業來說,這樣的選擇十分大膽);
network coding
1967年美國美國俄亥俄州立大學數學系(the faculty of the Department of Mathematics, Ohio State University, Columbus)1972年獲教授,1970-1971,1974-1975年分別擔任過康奈大學(Cornell University, Ithaca, NY)、德國海德堡大學(the University of Heidelberg, Heidelberg, Germany)、義大利國家娣阿爾塔數學研究所(the Instituto Nazionale di Alta Mathematica, Rome, Italy)、 史丹福大學(Stanford University, Stanford, CA)、和中國的南開大學(Nankai University, Tianjin, China.) 等大學和研究機構的訪問學者或客座教授。
現任德國比勒費爾德大學(the University of Bielefeld, Bielefeld, Germany)教授. 研究方向包括:資訊理論(information theory), 組合數學(combinatorics),,機率論(probability theory),數理統計(statistics), 和數論(number theory)等.
1977年,加入德國University of Bielefeld大學任教授(2004年後不再招生),培養博士生30多人,其中有很多是國際知名的資訊理論、編碼學方面的專家;
1988年,Prof. Rudolf Ahlswede與Imre Csiszar合作的論文(in the area of the hypothesis testing)獲IEEE Information Theory Society最佳論文獎;1990年,Prof. Rudolf Ahlswede與Gunter Dueck(是Ahlswede1977年招收的研究生)合作的論文(a new theory of message identification)再次獲獎,他成為了為數極少的兩次獲此獎項的學者。
2006年,Prof. Rudolf Ahlswede獲得了由the IEEE information Theory Society頒發的Claude Elwood Shannon Award(克勞德?艾爾伍德?香農獎),是當時獲此獎項的僅有的五位非美國人之一。

Ning Cai

蔡寧 Ning Cai
男,博士,博導,西安電子科技大學通信工程學院教授.
1947年10月出生,1986年就讀於德國比勒費爾德大學(the University of Bielefeld, Bielefeld, Germany)師從資訊理論領域國際最著名的學者之一Alhswede教授,並於1988年獲得數學博士學位。之後,在德國從事資訊理論和組合數學領域的研究工作達17年,其間曾應邀先後到在香港中文大學、新加坡國立大學等高校作訪問學者,並進行學術訪問。編輯出版專著1部,在國外學術雜誌和國際會議上發表論文50餘篇,其中有17篇發表在IEEE Trans. Information Theory上。2000年,蔡寧教授在與他人合作的論文中首次提出了網路編碼的理論,徹底推翻了傳統網路理論中認為的中間節點所進行的數據處理對數據傳輸過程本身不會帶來任何好處的結論。目前該理論已得到了學術界的廣泛認可和回響。合作論文“Linear Network Coding”榮獲2005年IEEE Information Theory 協會最佳論文獎。2006年8月受聘擔任西安電子科技大學通信工程學院特聘教授及博士生導師。

Shuo-Yen Robert Li

李碩彥Shuo-Yen Robert Li (有時也寫為Bob Li
理學士(台大BS (Nat'l Taiwan U.));PhD (University of California, Berkeley, 06/1974); FHKIE; FIEEE; 香港中文大學訊息工程學講座教授〔聯合書院〕 2008.05-今:西安電子科技大學名譽教授;
network coding
2008-2012:教育部 “111學術大師;
2008.1-2011.12:台灣國立清華大學榮譽講座教授;
2006-2009:北京大學深圳研究生院講座教授;
2005-2008:北京郵電大學客座教授(Advisory Professor, Beijing University of Posts and Telecommunications (BUPT ))
右圖中:王煜教授(後排左)、王鈞教授(後排右)、李碩彥教授(前排左)及張元亭教授(前排右)。
他們是Centre for Innovation and Technology(CINTEC)的重要研究員!

Raymond W. Yeung

楊偉豪教授於1984年畢業於美國康乃爾大學,主修電機工程學,並留校進修,分別於1985及1988年獲得碩士及博士學位。之後他曾在AT&T貝爾實驗所工作三年。他於1991年加入香港中文大學,現時是香港中文大學訊息工程學講座教授及網際網路工程學課程的課程主任。楊教授於2002年出版《A First Course in Information Theory》一書,該書已為美國著名學府如哥倫比亞、康乃爾、麻省理工、斯坦福等所採用,是信息理論的重要教材。他的主要研究為信息理論及網路編碼。
楊教授曾於1999-2001年出任IEEE信息理論學會常務理事,亦曾任多個信息理論研討會的委員,現為數份國際期刊編輯委員會成員。他曾獲得2000/01年度裘槎基金會的最優秀科研學者獎、2004 International Conference on Communications, Circuits and System最優秀通信理論論文獎,以及2005年IEEE電機及電子工程師學會信息理論學會論文獎。他是IEEE院士及香港工程師學會院士。

主要研究文獻

[1] R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, “Network information flow,” IEEE Trans. on Information Theory, vol. 46, pp. 1204-1216, 2000.
[2]R. Koetter, M. Médard, “Beyond Routing: An Algebraic Approach to Network Coding”, INFOCOM, 2002.
[3]S.-Y. R. Li, R. W. Yeung, and N. Cai. “Linear network coding”. IEEE Transactions on Information Theory , February, 2003.
[4] R. Koetter, M. Medard, “An Algebraic Approach to Network Coding”, Transactions on Networking, October 2003
[5] T. Ho, M. Medard, R. Koetter, “A coding view of network recovery and managment for single receiver communication”, CISS 2002 PDF
[6] Ning Cai and Raymond W. Yeung, “Network Coding and Error Correction”, ITW2002 Bangalore
[7] Ning Cai and Raymond. W. Yeung, “Secure Network Coding,” ISIT 2002.
[8] S. Katti, D. Katabi, Wenjun Hu, and Rahul Hariharan . “The Importance of Being Opportunistic: Practical Network Coding For Wireless Environments”, In Proc. 43rd Allerton Conference on Communication, Control, and Computing, Monticello, IL, Sep. 2005.
[9] 熊志強 黃佳慶 無線網路編碼綜述 計算機科學 2007
[10]楊義先 網路編碼理論與技術 國防工業出版社 2009.8
[11] Shuo-Yen Robert Li,Guangyue Han and Yixian Yang, PRIME FACTORIZATION THEORY OF NETWORKS. National Defense Industry Press, 2011.7

相關研究情況

網路編碼徹底改變了通信網路中信息處理和傳輸的方式,是信息理論研究領域的重大突破,已經引起學術界廣泛關注和高度重視。國外許多著名大學和研究機構都在積極開展對網路編碼理論和套用的研究。與此同時,網路編碼也逐漸引起了國內學術界的關注和重視。網路編碼的一個研究重點是網路編碼的構造方式。當前主要有兩種方式:一種是網路編碼的代數構造方式;另一種是實現網路編碼的多項式時間算法。前者是在已知整個網路拓撲信息的情況下,用一個系統轉移矩陣來描述信源輸入信息和信宿接收信息之間的關係,並通過構造符合要求的系統轉移矩陣來實現網路編碼;後者進一步簡化了網路編碼的構造,它也是在已知拓撲的情況下,首先通過最大流-最小割算法找到完成組播所需的路徑集合,然後在找出的這個子圖中自上而下地確定各節點所需進行的操作,從而可以將網路編碼構造的複雜度從指數級降低到多項式級。這兩種方法都要求已知網路拓撲信息,但也可以採用不需網路拓撲信息的分散式網路編碼和隨機網路編碼。分散式網路編碼的實現是通過在網路中傳輸的每個數據報上預先留出一些位置,以記載此數據包在前面各編碼節點上所採取的操作,然後接收節點可以根據收到的數據包直接譯出信源所傳送的信息。這種方法可以在不知網路拓撲信息的情況下實現網路編碼,但會增加網路負載。對於隨機網路編碼,中間編碼節點對接收到的信息會在一個有限域內隨機選擇一個元素作為組合的係數。研究表明,只要有限域足夠大,隨機網路編碼的成功率就很高。
此外,關於無線網路中網路編碼的研究正在成為一個新的研究熱點。由於無線網路自身的一些獨特特性,網路編碼套用於無線網路可以提高網路的傳輸容量和降低能耗等。另外,網路編碼可以與其他技術相結合:如網路編碼和糾錯碼的結合、網路編碼和路由協定及調度算法的結合、網路編碼和協同通信以及網路編碼和加密機制的結合等等。
儘管學術界已經對網路編碼理論和套用進行了廣泛的研究,並從理論模型上證實了運用網路編碼能提升網路的性能,但驗證的步驟或模擬的環境大多基於若干假設或理想化的模型,與實際的套用環境還有一定的差距,由此得出的某些結論尚存局限性。此外,研究過程大多基於理論上定性的分析,缺乏定量的研究。因此,將網路編碼套用於實際,構建基於網路編碼的實用系統,還有待更嚴格、更深入、更廣泛的研究與實踐。

發展歷史

(待詳)

相關學術會議

The IEEE International Symposium

The IEEE International Symposium on Network Coding, 一年一次
2005:April 7, 2005, Riva del Garda, Italy.
2006:Boston, USA.
2007:Monday, January 29, 2007, San Diego, California
2008:The Chinese University of Hong Kong.
2009:Monday, June 15, 2009 to Tuesday, June 16, 2009 at the Ecole Polytechnic Federale Lausanne (EPFL), in Lausanne, Switzerland.
2010: Toronto, Canada, June 9 — 11, 2010.
2011:beijing university of posts and telecommunications(BUPT), July 25th to 27th, 2011 in Beijing, China.

中國電子學會資訊理論分會主辦

1. 第十五屆資訊理論學術年會暨全國首屆網路編碼學術研討會:2008年7月29日至30日在青島, 青島科技大學;
2. 全國第二屆網路編碼學術研討會學術研討會,與2009年中國高校通信類院系學術研討會合併舉行 廣西大學,計算機與電子信息學院承辦。 2009年9月。
3. 第三屆網路編碼學術研討會學術研討會,西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室、現代無線信息網路基礎理論與技術學科“111”創新引智基地和計算機網路與信息安全教育部重點實驗室聯合承辦。2010年10月16日-10月17日。

其它會議

1. 信息安全與網路編碼研討會(HWISNC2009),黑龍江省計算機學會主辦、哈爾濱工程大學計算機學院承辦,2009-8-4.
2.

國內主要研究情況和進展

國內關於Network Coding的研究,主要集中在北京大學深圳研究生院,西安電子科技大學,復旦大學,華中科技大學,中南大學,南京理工大學,北京郵電大學,清華大學,南京大學,哈爾濱工業大學等高校。(待詳)

相關詞條

熱門詞條

聯絡我們