[發明專利]分布式網絡中的編碼資源自適應調度算法

無效

• 申請號: 200910242995.1
• 申請日: 2009-12-23
• 公開（公告）號: CN101764675A
• 公開（公告）日: 2010-06-30
• 發明（設計）人: 柏琳;王肖玲
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04L1/00
• 分類號: H04L1/00;H04W4/06;H04W72/04;H04W72/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明設計的是組播網絡中的編碼資源的自適應調度算法，主要 采用資源調度的思想對網絡編碼組播網絡中各個子域的編碼資源進行 調度，以實現編碼資源的優化配置。

背景技術

網絡編碼是一個新興起的技術，它的提出適應了現代網絡中的這種 需求，其理論和應用已成為通信領域研究的新熱點。和傳統的存儲轉發 機制不同的是，網絡編碼融合了編碼和路由兩個概念，通過允許中間節 點對接收到的多個數據包進行編碼組合，增加單次傳輸的信息量，在網 絡中維持著最大的信息流量，從而提高網絡整體性能，滿足不斷增長的業 務傳輸的需求。

目前，網絡編碼的研究領域已經觸及到了網絡信息論、多信源網絡 編碼、網絡隨機編碼、網絡卷積編碼、網絡糾錯編碼以及網絡安全編碼 等領域，其研究潛力十分巨大。

在網絡編碼中，節點之間(或邊上)的編碼順序是非常重要的。在編 碼過程中，需要保證在進行編碼之前收到了所有輸入邊的信息，否則就 會失敗。同樣，在目的端進行解碼時，也需要保證在解碼之前收到了所 需要的全部信息才可以正確解碼。

目前對于網絡編碼技術的研究主要集中在確定拓撲網絡中的編解碼 算法以及分布式網絡中的編解碼算法的研究。

確定拓撲網絡中的編解碼算法的研究最早由R.Ahlswede等人提出 了網絡最大流可由網絡編碼實現以后，李碩彥等人又提出了網絡編碼的 具體實現方法。之后R.Kotter和M.Medard從代數構造角度實現了線 性網絡編碼的全局編碼向量所需條件。這種編碼構造算法把從編碼結點 的輸入到輸出的過程描述為經過一個矩陣相乘的運算。它把全局編碼向 量通過局部編碼向量來表示，在信息傳播過程中將各個節點處的編碼向 量的信息逐級傳遞下來，與輸出和輸入隨機過程一起構造出最終傳輸矩 陣。后來P.Sanders和S.Egner從信息流角度對最早提出編碼方法進行 了簡化，把算法的時間復雜度從指數級簡化到多項式時間級。此算法首 先為每個接收結點找到若干個互不相交的路徑，再為每個路徑找到相互 獨立的全局向量，使其張成整個信息空間，這樣才使得信宿可以恢復出 信源發出的所有信息。

雖然多項式時間算法能夠有效地構造編碼向量，確保信宿節點成功 譯碼，但由于它是集中式算法，需對網絡拓撲結構有全面的了解.因此，從 實用的角度來看，多項式時間算法對拓撲結構動態變化或規模很大的網 絡，實用性并不強.P.A.Chou，Y.Wu提出了適合在未知網絡拓撲的情況下 的分布式網絡編碼。Ying?Zhu，Baochun?Li等介紹了分布式網絡編碼對 于多播網絡中在應用層的實現。首先自動找到適合網絡編碼的拓撲結構 (其中包含一些最優化選擇)，原則是使其可以恢復出原數據，然后在確 定哪些結點需要進行編碼，哪些結點只需進行普通的接收轉發操作，然 后進行數據傳輸。此算法也包含了一些應付動態變化情況。分布式網絡 中的編解碼算法不同于確定拓撲網絡中的編解碼算法的特點在于：編碼 向量的分配和網絡中數據的傳輸同時進行，在數據包的包頭記錄并隨時 更新全局編碼向量，而在需要編碼的節點隨機地在某一個有限域中選取 元素作為局部編碼向量。目的節點根據接收到的數據包提取包頭中的全 局編碼向量進行解碼。這種方法也存在其不可避免的局限性，即編碼資 源大量消耗以及目的節點解碼困難。

現有的分布式網絡中的編解碼算法，由于編碼向量字母表的限制不 能完全保證目的節點所接收到的全局編碼向量的線性不相關性，從而不 能百分百地保證目的節點能夠成功解碼，而且還不能動態地適應網絡拓 撲的變化，有一定的實用局限性。

因此，在分布式網絡中進行編解碼運算，需要考慮編碼資源的實時 分配和調度，從而保證編碼資源的有效利用以及編解碼過程的成功完成。

本發明涉及的是一種組播網絡中的編碼資源自適應調度算法，就是 先把需要進行編碼組播的網絡拓撲進行子域的劃分，然后根據目的節點 的不同需求，采用調度算法對網絡資源特別是編碼向量資源進行實時的 調度和配置。這種方法可以實現網絡編碼資源按需配置，并且可以使目 的端可以以最快的速度收到所需的編碼信息，并及時解碼。另外允許節 點隨時加入或者退出組播組，實現分布式的網絡編碼組播。

發明內容