[發(fā)明專利]基于機會式網(wǎng)絡(luò)編碼搜尋最優(yōu)關(guān)聯(lián)包的重傳方法

有效

• 申請?zhí)枺?/td>: 201610098559.1
• 申請日: 2016-02-23
• 公開（公告）號: CN105721119B
• 公開（公告）日: 2019-03-08
• 發(fā)明（設(shè)計）人: 王練;施文哲;梁申虎;陳巧
• 申請（專利權(quán)）人: 重慶郵電大學
• 主分類號: H04L1/18
• 分類號: H04L1/18;H04L1/00
• 代理公司: 重慶市恒信知識產(chǎn)權(quán)代理有限公司 50102
• 代理人: 劉小紅

1.一種機會式網(wǎng)絡(luò)編碼搜尋最優(yōu)關(guān)聯(lián)包的重傳方法，其特征在于，包括以下步驟：

101、初始化，獲取網(wǎng)絡(luò)中用戶的丟包信息，發(fā)送端依據(jù)反饋信息生成丟包矩陣，設(shè)該矩陣有M行N列，其中N列列向量P_i(1≤i≤N)代表數(shù)據(jù)包，M行行向量R_j代表接收端(1≤j≤M)，其中當PLM(i,j)＝1時，表示接收端R_j正確接收到數(shù)據(jù)包P_i，而當PLM(i,j)＝0，表示接收端R_j丟失數(shù)據(jù)包P_i，發(fā)送端記錄每個接收端的狀態(tài)后，進入丟包恢復階段，在丟包矩陣中利用最大團算法搜索可以編碼的關(guān)聯(lián)包，生成編碼包組，找出可以編碼的關(guān)聯(lián)包所在的列，依據(jù)這些列生成鄰接矩陣；

102、在鄰接矩陣中，計算步驟101所述的編碼包組的編碼增益，若編碼包組的編碼增益是編碼包組中最大的則傳輸該編碼包組，則跳轉(zhuǎn)至步驟103；否則返回重新計算尋找最大的編碼增益對應(yīng)的編碼包組；

103、更新丟包對應(yīng)的鄰接矩陣，判斷鄰接矩陣中是否有可以進行編碼的關(guān)聯(lián)包組，若是則返回步驟102重新計算編碼包組的編碼增益，若沒有則發(fā)送端根據(jù)鄰接矩陣進行數(shù)據(jù)包的重傳，結(jié)束。

2.根據(jù)權(quán)利要求1所述的機會式網(wǎng)絡(luò)編碼搜尋最優(yōu)關(guān)聯(lián)包的重傳方法，其特征在于，所述步驟101中最大團算法具體包括以下步驟：

一個無向圖G＝(V，E)，V是點集，E是邊集，取V的一個子集U，若對于U中任意兩個點u和v，有邊(u,v)∈E，那么稱U是G的一個完全子圖，U是一個團當且僅當U不被包含在一個更大的完全子圖中，其中的G即為鄰接矩陣所構(gòu)成，V為原始的數(shù)據(jù)包的頂點，兩包之間存在的關(guān)聯(lián)性映射為無向圖的邊即頂點的無序?qū)Γ@一關(guān)系構(gòu)成了最大團中各個頂點的連接關(guān)系；G的最大團指的是定點數(shù)最多的一個團，計算團數(shù)為(2-4)個的最大團，在2-4個時編碼增益最優(yōu)；

從一個點u開始，把這個點加入集合U中，將編號比它大的且和它相連的點加入集合S1中，為了方便，將集合S1中的點有序，讓他們從小到大排列，進行第一遍DFS；

第一遍DFS：

從S1中選擇一個點u1，遍歷S1中，所有編號比u1大且和u1相連的點，其實也就是排在u1后面，并且和u1相連的點，將它們加入集合S2中；同理，讓S2中的點也按照編號也從小到大排列；將u1加入集合U中進行第二遍DFS；

第二遍DFS：

從S2中選擇一個點u2，遍歷S2中，所有排在u2后面且和u2相連的點，并把它們加入集合S3中，讓S3中的點按照編號從小到大排列，將u2加入集合U中進行第三遍DFS；

第三遍DFS：

從S3中選擇一個點u3，遍歷S3中，所有排在u3后面且和u3相連的點，并把它們加入集合S4中，讓S4中的點按照編號從小到大排列，將u3加入集合U中進行第四遍DFS；

第四遍DFS：

當集合S1或集合S2或集合S3為空時，DFS過程結(jié)束，得到一個只用后面幾個點構(gòu)成的完全子圖，并用它去更新只用后面幾個點構(gòu)成的最大團，退出當前DFS，返回上層DFS，接著找下一個完全子圖，直到找完所有的完全子圖。

3.根據(jù)權(quán)利要求1所述的機會式網(wǎng)絡(luò)編碼搜尋最優(yōu)關(guān)聯(lián)包的重傳方法，其特征在于，所述步驟102中判斷編碼包組的編碼增益是編碼包組中最大的采用逐一比較法，選擇編碼增益E_g最大值所對應(yīng)的編碼包組進行重傳。

4.根據(jù)權(quán)利要求1所述的機會式網(wǎng)絡(luò)編碼搜尋最優(yōu)關(guān)聯(lián)包的重傳方法，其特征在于，所述丟包矩陣采用0-1進行表示，若丟包矩陣中的對應(yīng)列全1表示接收端已成功獲得數(shù)據(jù)包，若有0則表示未成功獲得數(shù)據(jù)包。

5.根據(jù)權(quán)利要求1所述的機會式網(wǎng)絡(luò)編碼搜尋最優(yōu)關(guān)聯(lián)包的重傳方法，其特征在于，所述步驟102中計算編碼包組的編碼增益的計算公式為：

其中E_g為計算出的編碼增益，P_I為對應(yīng)的各個丟失的數(shù)據(jù)包個數(shù)，EP_j(2≤j≤4)為生成的編碼包組的個數(shù)，優(yōu)先計算j＝4時的編碼包組目的在于盡可能多的恢復丟包，選擇E_g最大值所對應(yīng)的編碼包組行重傳。