[發明專利]一種采用空間網絡編碼的網絡傳輸方法

有效

• 申請號: 201310282663.2
• 申請日: 2013-07-05
• 公開（公告）號: CN103368694A
• 公開（公告）日: 2013-10-23
• 發明（設計）人: 黃佳慶;李宗鵬
• 申請（專利權）人: 華中科技大學
• 主分類號: H04L1/00
• 分類號: H04L1/00
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 方放

技術領域

本發明屬于網絡信息傳輸方法，尤其涉及一種采用空間網絡編碼的網絡傳輸方法。

背景技術

網絡編碼(Network?Coding)是網絡信息論的重要突破，該概念于2000年正式誕生，其基本思想是允許網絡中間節點參與編碼，其典型優勢是可提升吞吐量、提高帶寬利用率和降低算法復雜度。網絡編碼的重要理論價值在于揭示出信息流(Information?Flow)與商品流(Commodity?Flow)存在本質的差別，所以網絡編碼也稱為網絡信息流，(見S.Y.R.Li，R.W.Yeung，N.Cai.Linear?Network?Coding.IEEE?Transactions?on?Information?Theory.2003，49(2)：371-381和見R.W.Yeung，S.R.Li，N.Cai，Z.Zhang.Network?Coding?Theory.Foundation?and?Trends?in?Communications?and?Information?Theory.2005，2(4-5)：241-381)。

Li等人于2011年首次提出空間網絡編碼(Space?Network?Coding)，研究的是空間中的網絡編碼，所以也稱為空間信息流。空間信息流與前述網絡信息流的差別是，前者允許加入額外的中繼點及其相連鏈路，而后者則不允許。空間網絡編碼的典型優勢是在空間中采用網絡編碼的代價可嚴格小于空間中采用路由的代價，(見Z.Li，C.Wu.Space?Information?Flow：Multiple?Unicast.IEEE?ISIT.2012和見X.Yin，Y.Wang，X.Wang，X.Xue，Z.Li.Min-Cost?Multicast?Network?in?Euclidean?Space.IEEE?ISIT.2012)：在空間中采用多播路由，相當于歐幾里得斯坦納最小樹(Euclidean?Steiner?Minimal?Tree，ESMT)問題，已經證明ESMT問題是非確定性多項式困難(NP-Hard)問題，解決該問題的方法復雜度較高，(見MP.Winter，M.Zachariasen.Euclidean?Steiner?Minimum?Trees：An?Improved?Exact?Algorithm.Networks.1997，30(3)：149-166)；在空間中采用網絡編碼，其代價可嚴格小于空間中的最優多播路由的代價，典型實例是五角星網絡，(見黃佳慶，楊春風，金振坤，ZongpengLi，二維歐氏空間中網絡編碼的研究，重慶郵電大學學報(自然科學版)，2012，24(5)：521-529)。可見，空間網絡編碼與空間路由存在本質差別，說明研究空間網絡編碼的重要性和必要性。

考慮給定歐幾里得空間中采用空間網絡編碼的網絡傳輸問題：對于任意給定終端點集合，并允許添加額外的中繼點，要求實現具有最小代價的多播網絡通信目標。Huang等人提出一種基于線性劃分的空間網絡編碼的網絡傳輸方法，其基本內容包括對給定終端點所形成的約束矩形進行線性劃分得到矩形格子，取每個矩形格子中心作為中繼點，針對所有終端點和中繼點構建完全圖，然后構建基于信息流的線性規劃數學模型并求最優解；逐步增大線性劃分的數量，所求拓撲逼近最優拓撲，最后采用力學平衡的方法求解中繼點的最優位置，(見J.Huang，X.Yin，X.Zhang，X.Du，Z.Li.On?Space?Information?Flow：Single?Multicast.NetCod.2013)。但該方法存在如下不足：當給定終端點存在分簇現象時，即某些終端點之間的歐幾里得距離較小，而其他終端點之間的歐幾里得距離較大，此時采用線性劃分后矩形格子數值可能非常大，在構建完全圖時鏈路總數也非常大，導致線性規劃求解時計算量陡增。

為清楚闡述本發明，對本發明涉及的有關概念作以下說明：

終端點：指網絡通信中位置固定的節點，包括一個信源節點和至少一個信宿節點，分別稱為信源終端點和信宿終端點。

中繼點：為達到具有最小代價的網絡通信目標所增加的通信節點，其個數和位置是任意的。為達到具有最小代價的網絡傳輸，中繼點的位置范圍應在終端點所確定的凸包內(包括凸包邊界)。

簡單圖：指既不存在有環鏈路也不存在多重鏈路的圖。

完全圖：指任意兩點間都有一條鏈路的簡單圖稱為完全圖，節點的鄰接鏈路指以該節點為始點或終點的鏈路集合，(見高隨祥，圖論與網絡流理論，北京：高等教育出版社，2009)。