一種多跳-多數據流網絡的網絡編碼控制方法
2023-12-07 04:31:31
專利名稱：一種多跳-多數據流網絡的網絡編碼控制方法
技術領域：
本發明涉及一種網絡編碼控制方法，尤其涉及一種多跳-多數據流網絡的網絡編碼控制方法，網絡中的中間節點根據網絡編碼條件是否得到滿足確定是否需要進行網絡編碼，屬於網絡編碼技術領域。
背景技術：
Ahlsuedu 等學者在 「7萬瓶Info. Theory, 2000, 46 (7) 1204-1216」 上所發表的論文「Network information flow」中以「蝶形」網絡結構為例，指出了網絡編碼方法較傳統的路由方法可以獲得更高的數據吞吐量。但是並不是對於任何網絡拓撲結構，網絡編碼方法都可以較傳統路由方法可以取得更高的數據吞吐量，因而學者們開始關注在何種網絡拓撲結構條件下，網絡編碼方法較傳統路由方法可取得更高的網絡容量。Saschin 等學考在 「IEEE/ACM Tran. Networks, 2008, 16 (3) 497-510」 上發表的論文 「XORs in the air:Practical wireless network coding」中指出了在雙向中繼，「X 形」以及 「+形」 拓撲結構網絡中，網絡編碼方法較傳統路由方法可取得更高的數據吞吐量。Ahlsuedu和 ^schin均考慮的是幾種特殊的網絡拓撲結構，而沒有提出一般網絡拓撲結構條件下的網絡編碼條件。並不是對於任何網絡拓撲結構，網絡編碼方法都可以較傳統路由方法取得更高的數據吞吐量，當網絡編碼後的數據流在信宿節點不能通過網絡解碼恢復出原始數據流時，會導致中斷事件發生，反而會使數據吞吐量下降，並且網絡編碼方法較傳統路由方法計算複雜度高，因而研究適用於一般拓撲結構網絡的網絡編碼條件就顯得至關重要。Jilin 等學者 Hee ICDCS, 2008:462-469」 上發表的論文 「DCAR: Distributed coding-aware mechanism for opportunistic routing in wireless mesh networks」中給出了基於多跳一兩個數據流條件下的網絡編碼適用條件。Bin等學者在 「IEEE Tran. Vehicular TfecAfloA^j，2011，60 ) 1714-1727」上發表的論文「Analysis of general network coding conditions and design of a free-ride-oriented routing metric"中給出了基於多跳一多數據流條件(每對信源-信宿節點間的數據傳輸形成一條數據流，信源發送的數據可以經過多跳到達信宿結點，網絡中可同時存在多條數據流進行數據傳輸)下的網絡編碼條件，即參與本次網絡編碼的各數據流能夠在其下遊數據節點中通過網絡解碼獲得原始數據流(未編碼的數據流)，依照該條件可以獲得較優的網絡編碼機會，但是當數據鏈路較長時，需要對當前節點後的各數據流的下遊節點依次考慮其網絡解碼情況，計算複雜度相對較大，並且當網絡的拓撲結構發生改變時，也會影響當前節點的網絡編碼條件，導致中斷事件產生，因此這種網絡編碼條件也不適用於動態拓撲結構網絡。
發明內容
本發明所要解決的技術問題在於克服現有多跳一多數據流條件下的網絡編碼條件計算複雜度大且不適用於動態拓撲結構網絡的缺陷，提供一種多跳-多數據流網絡的網絡編碼控制方法，該方法在判斷是否滿足網絡編碼條件時，僅考慮局部網絡拓撲結構，從而具有較低的計算複雜度，且適用於動態拓撲結構網絡。本發明具體採用以下技術方案
一種多跳-多數據流網絡的網絡編碼控制方法，接收到多個數據流的網絡中間節點判斷網絡編碼條件是否得到滿足，如是，則對這多個數據流進行網絡編碼，並將編碼後的數據流轉發到參與網絡編碼的各數據流的下遊節點；如否，則分別將這多個數據流轉發至各數據流的下遊節點；所述網絡編碼條件是指對所述多個數據流進行網絡編碼後的數據流在流經參與網絡編碼的各數據流的下遊節點時，能被下遊
I跳範圍內的節點進行網絡解碼恢復出各自編碼前的數據流，其中JV為一預設的有限的整數。本發明的多跳-多數據流網絡的網絡編碼控制方法，既可用於有線網絡也可用於無線網絡，考慮到該方法對於具有動態拓撲結構的網絡也可適用，因此尤其適用於多跳-多數據流無線網絡。本發明通過對多跳-多數據流網絡的網絡編碼條件進行改進，以網絡編碼後的數據流能被下遊有限跳範圍內的節點進行網絡解碼恢復出各自編碼前的數據流作為網絡編碼條件，而非傳統的以參與本次網絡編碼的各數據流能夠在其下遊數據節點中通過網絡解碼獲得原始數據流作為網絡編碼條件。從而克服了現有技術所存在的計算複雜度高的缺陷；且由於僅考慮局部網絡拓撲結構，當該局部網絡拓撲結構外的網絡條件發生改變時，並不影響當前所考慮的網絡編碼條件，因而適用於動態拓撲結構的網絡。根據本發明的思路，還可得到一種多跳-多數據流無線網絡的數據傳輸方法，所述無線網絡中的每個節點能夠偵聽得到其鄰近單跳範圍內其它節點所發送的數據，該無線網絡中各中間節點作為當前節點時，按照以下步驟進行數據處理
步驟1、當前節點判斷是否接收到網絡編碼數據流，如是，則當前節點利用從相鄰節點所偵聽到的數據流對網絡編碼數據流進行網絡解碼後，跳轉至步驟2 ；否則，直接跳轉至步驟2;
步驟2、當前節點判斷是否接收到多個數據流，如果僅接收到單個數據流，則轉發該數據流至其下遊節點，並結束該節點數據處理流程；否則跳轉到步驟3 ；
步驟3、當前節點判斷所接收到的多個數據流中是否有部分或全部數據流滿足網絡編碼條件，如否，則時分轉發所接收各數據流至各自的下遊節點，並結束該節點數據處理流程；否則跳轉到步驟4 ；其中所述網絡編碼條件是指對所述多個數據流進行網絡編碼後的
數據流在流經參與網絡編碼的各數據流的下遊節點時，能被下遊JV跳範圍內的節點進行
網絡解碼恢復出各自編碼前的數據流，其中N為一預設的有限的整數；
步驟4、如有部分數據流滿足編碼條件，則將該部分數據流進行網絡編碼，並將編碼後的數據流和其它數據流時分轉發到各自數據流的下遊節點；如果當前節點所接收到的全部數據流滿足編碼條件，則將所接收到的全部數據流進行網絡編碼，並將編碼後的數據流轉發到參與網絡編碼的各數據流的下遊節點。優選地，步驟1中所述當前節點利用從相鄰節點所偵聽到的數據流對網絡編碼數據流進行網絡解碼，具體是指當前節點利用從相鄰節點所偵聽到的數據流對網絡編碼數據流進行異或運算。從而儘可能消除參與網絡編碼中的其路由線路不經過當前節點的部分數據流。相比現有技術，本發明具有以下優點
本發明在判斷是否需要進行網絡編碼時，僅考慮局部網絡拓撲結構，即在流經當前節點各數據流下遊有限跳範圍內的節點，可相應降低判別當前節點網絡編碼條件的計算複雜度；並且由於僅考慮局部網絡結構來考慮網絡編碼條件，當該局部網絡拓撲結構外的網絡條件發生改變時，並不影響當前所考慮的網絡編碼條件，因而適用於動態拓撲結構網絡。
圖1為具體實施方式
中所述的一個多跳一多數據流拓撲結構的無線網絡模型示例圖2為具體實施方式
中的無線網絡中每個中間節點的數據處理流程圖。
具體實施例方式下面結合附圖對本發明的技術方案進行詳細說明
圖1是一個多跳一多數據流拓撲結構的無線網絡模型示例，該示例中共有如下四個不同的數據流
S1^ R9RmR11-^R12 ^ Ru-^Ru ^ R15 ^ D1 傳輸數據流 P1 ；
524 R7 4 R9 — D2 傳輸數據流P1 ；
53R16 R10 D3 傳輸數據流 P3 ；
S, -^Eil ^Ru ^Ei ^Ri ^R5 ^J^, ^R1 ^D4 傳輸數據流馬。圖中虛線表示兩相鄰節點間能夠相互偵聽對方的數據流，箭頭表示數據流的方向。下面以圖1中的網絡拓撲為例來說明各中間節點的數據處理過程，本具體實施方式
中，跳數限制設為N=Z0如果hi的取值較大，則當前節點需考慮較大範圍內的網絡拓撲結構來判別網絡編碼條件，可以相應創造更多的網絡編碼機會來減少傳輸數據流所需要的時隙數，但同時會增大判別網絡編碼條件的計算複雜度，並且如果Ar跳範圍內網絡拓撲結構發生改變，當前網絡編碼條件也發生改變，故不適用於動態網絡拓撲結構。因此值的設定需考慮各方麵條件進行均衡。該網絡中各中間節點的數據處理過程如圖2所示，包括以下步驟
步驟1、當前節點判斷是否接收到網絡編碼數據流(例如，可根據所接收數據幀的幀頭標識信息進行判斷)，如是，則當前節點利用從相鄰節點所偵聽到的數據流對網絡編碼數據流進行網絡解碼後，跳轉至步驟2 ；否則，直接跳轉至步驟2 ；
步驟2、當前節點判斷是否接收到多個數據流，如果僅接收到單個數據流，則轉發該數據流至其下遊節點，並結束該節點數據處理流程；否則跳轉到步驟3 ；
步驟3、當前節點判斷所接收到的多個數據流中是否有部分或全部數據流滿足網絡編碼條件，如否，則時分轉發所接收各數據流至各自的下遊節點，並結束該節點數據處理流程；否則跳轉到步驟4 ；其中所述網絡編碼條件是指對所述多個數據流進行網絡編碼後的
數據流在流經參與網絡編碼的各數據流的下遊節點時，能被下遊JV跳範圍內的節點進行
網絡解碼恢復出各自編碼前的數據流，其中JV為一預設的有限的整數；
步驟4、如有部分數據流滿足編碼條件，則將該部分數據流進行網絡編碼，並將編碼後的數據流和其它數據流時分轉發到各自數據流的下遊節點；如果當前節點所接收到的全部數據流滿足編碼條件，則將所接收到的全部數據流進行網絡編碼，並將編碼後的數據流轉發到參與網絡編碼的各數據流的下遊節點。下面對如下節點進行重點描述
節點R9 節點巧可從Si接收到未編碼數據流P1，從R1接收到未編碼數據流P2，可將接收的數據流編碼成巧十芍，原因是巧十芍可在數據流召中節點乓2跳後的下遊節點中利用O 芍) 乓恢復出本次編碼前的數據流；(節點可以偵聽節點Si2中的數據流乓),PiBP2可在數據流P2中節點^9 1跳後的下遊節點D2中利用(巧十 恢復出本次編碼前的數據流巧(節點￡)2可以偵聽節點&中的數據流巧)。節點乓可以採用一個時隙將網絡編碼後的數據流巧十巧同時傳輸給節點乓ο和D2。如果不採用網絡編碼，則節點乓需採用兩個時隙分別將數據流P1傳輸給，將數據流P2傳輸給D2。節點乓。節點可從節點Eg接收到網絡編碼後的數據流P1BP2 (但不能利用網絡解碼將因網絡編碼加入的數據流Ij2去除)，從節點^6接收到數據流芍，可將接收的數據流編碼成(巧十P2)十P3,原因是(巧十巧) 芍可在數據流巧中節點^d 2跳後的下遊節點^2中通過數據流間的異或運算消除參與本次編碼的數據流Pi (^2可以偵聽到節點高中的數據流巧)，(巧十P2) P3可在數據流芍中節點Pw 1跳後的下遊節點1 中通過數據流間的異或運算消除參與本次編碼的數據流巧 芍(馬可以偵聽到節點D2中的數據流巧十芍)。節點^0可以採用一個時隙將編碼後的數據流(巧十芍〉 芍同時傳輸給節點乓0ΡΑ。如果不採用網絡編碼，節點需採用兩個時隙分別將數據流巧十巧傳輸給,將數據流巧傳輸給馬。節點節點從節點接收到編碼後的數據流閉十P2) P3，其中數據流 P2和數據流Bi的路由線路均不經過節點。節點可以利用從節點S2中偵聽到的數
據流芍，進行運算((巧十芍) ^) ^ = -P1十馬消除(巧十P2)十芍中參與網絡編碼的數
節點^2 節點E12從節點接收到網絡編碼後的數據流P1十巧，其中數據流 Bi的路由線路不經過節點^2。節點^2可以偵聽到節點S3中的數據流Ri ,進行運算 (巧 P3) P3 = P1消除巧十芍中參與網絡編碼的數據流馬。節點^3 節點從節點Eu接收到數據流P1，從節點R17接收到數據流P4，不能將所接收到的數據流編碼成P1十巧，原因是巧十P4可在數據流P1中節點巧3 2跳後的下遊節點乓5中利用(巧十芍)十芍=巧消除參與本次網絡編碼的數據流P4 (乓5可以偵聽到&中的數據流芍)，但是巧十巧需在數據流芍中節點乓3 7跳後的下遊節點乓中利用(P1IBP4)IP1 = P4消除參與本次網絡編碼的數據流芍(乓可以偵聽到A中的數據流 P1),超過了規定的跳數限制iV= 3。因此節點民3將利用兩個時隙將數據流P1和P、分別轉發給節點乓4和乓。如果不設跳數限制1=3，判別節點乓3的網絡編碼條件時，需逐個依次考慮數據
流巧中節點^3後的所有下遊節點是否可以通過網絡解碼將數據流P4消除，以及逐個依
次考慮流P4中節點^3後的所有下遊節點是否可以通過網絡解碼將數據流P1消除，計算
複雜度相對較高。設跳數限制Af = 3 ,只需逐個依次考慮數據流P1中節點乓3後的下遊節點
^4 , ^5和D1是否可以通過網絡解碼將數據流P4消除，以及逐個依次考慮流巧中節點
^3後的下遊節點 ,和R5是否可以通過網絡解碼將數據流P1消除，因而計算複雜度相應降低(尤其當數據鏈路較長時)。並且，如果不設跳數限制F=3，節點乓3將接收到的數據流編碼成巧十巧，對於動態拓撲結構網絡，當節點S1和節點R1間的無線鏈路變得不可靠時，節點R1不能偵聽到
節點Si1中的數據流巧，則接收節點馬不能獲得所需的數據流巧(僅能接收到芍 巧 )，中斷事件產生；如果設跳數限制況=3，將僅依據局部網絡拓撲結構來判別網絡編碼條件，節點乓3不能將接收到的數據流編碼成，當該局部網絡拓撲結構外的網絡條件發生變化時，並不影響當前網絡編碼判別條件，接收節點A依然能夠獲得所需的數據流 P4。因此本發明方法適用於動態拓撲結構網絡。
權利要求
1.一種多跳-多數據流網絡的網絡編碼控制方法，接收到多個數據流的網絡中間節點判斷網絡編碼條件是否得到滿足，如是，則對這多個數據流進行網絡編碼，並將編碼後的數據流轉發到參與網絡編碼的各數據流的下遊節點；如否，則分別將這多個數據流轉發至各數據流的下遊節點；其特徵在於，所述網絡編碼條件是指對所述多個數據流進行網絡編碼後的數據流在流經參與網絡編碼的各數據流的下遊節點時，能被下遊I跳範圍內的節點進行網絡解碼恢復出各自編碼前的數據流，其中JV為一預設的有限的整數。
2.如權利要求1所述多跳-多數據流網絡的網絡編碼控制方法，其特徵在於，所述多跳-多數據流網絡為多跳-多數據流無線網絡。
3.—種多跳-多數據流無線網絡的數據傳輸方法，所述無線網絡中的每個節點能夠偵聽得到其鄰近單跳範圍內其它節點所發送的數據，其特徵在於，該無線網絡中各中間節點作為當前節點時，按照以下步驟進行數據處理步驟1、當前節點判斷是否接收到網絡編碼數據流，如是，則當前節點利用從相鄰節點所偵聽到的數據流對網絡編碼數據流進行網絡解碼後，跳轉至步驟2 ；否則，直接跳轉至步驟2;步驟2、當前節點判斷是否接收到多個數據流，如果僅接收到單個數據流，則轉發該數據流至其下遊節點，並結束該節點數據處理流程；否則跳轉到步驟3 ；步驟3、當前節點判斷所接收到的多個數據流中是否有部分或全部數據流滿足網絡編碼條件，如否，則時分轉發所接收各數據流至各自的下遊節點，並結束該節點數據處理流程；否則跳轉到步驟4 ；其中所述網絡編碼條件是指對所述多個數據流進行網絡編碼後的數據流在流經參與網絡編碼的各數據流的下遊節點時，能被下遊JV跳範圍內的節點進行網絡解碼恢復出各自編碼前的數據流，其中N為一預設的有限的整數；步驟4、如有部分數據流滿足編碼條件，則將該部分數據流進行網絡編碼，並將編碼後的數據流和其它數據流時分轉發到各自數據流的下遊節點；如果當前節點所接收到的全部數據流滿足編碼條件，則將所接收到的全部數據流進行網絡編碼，並將編碼後的數據流轉發到參與網絡編碼的各數據流的下遊節點。
4.如權利要求3所述多跳-多數據流無線網絡的數據傳輸方法，其特徵在於，步驟1中所述當前節點利用從相鄰節點所偵聽到的數據流對網絡編碼數據流進行網絡解碼，具體是指當前節點利用從相鄰節點所偵聽到的數據流對網絡編碼數據流進行異或運算。
全文摘要
本發明公開了一種多跳-多數據流網絡的網絡編碼控制方法，屬於網絡編碼技術領域。本發明方法通過對多跳-多數據流網絡的網絡編碼條件進行改進，以網絡編碼後的數據流能被下遊有限跳範圍內的節點進行網絡解碼恢復出各自編碼前的數據流作為網絡編碼條件，而非傳統的以參與本次網絡編碼的各數據流能夠在其下遊數據節點中通過網絡解碼獲得原始數據流作為網絡編碼條件。從而克服了現有技術所存在的計算複雜度高的缺陷；且由於僅考慮局部網絡拓撲結構，當該局部網絡拓撲結構外的網絡條件發生改變時，並不影響當前所考慮的網絡編碼條件，因而適用於動態拓撲結構的網絡。本發明還公開了一種多跳-多數據流無線網絡的數據傳輸方法。
文檔編號H04L12/56GK102299771SQ201110264758
公開日2011年12月28日 申請日期2011年9月8日 優先權日2011年9月8日
發明者孔媛媛, 楊震, 梅中輝 申請人:南京郵電大學