[發明專利]一種基于網絡編碼的無線傳感網多路徑路由方法

有效

• 申請號: 201310560078.4
• 申請日: 2013-11-12
• 公開（公告）號: CN103561445A
• 公開（公告）日: 2014-02-05
• 發明（設計）人: 王秀娟;鄭康鋒;張冬梅;武斌;査選;周楊;趙曉燕;孫博;伍淳華;高大永
• 申請（專利權）人: 北京工業大學;北京郵電大學
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04L1/00
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 樓艮基

1.一種基于網絡節點編碼的無線傳感網多路徑路由方法，其特征在于：所述網絡編碼是指所述無線傳感網中的各中間節點層中的任何一個中間節點對自己從N條輸入路段上的N個上一跳節點同時輸入的N個原始數據包進行統一編碼，并一次性的通過各自相對應的輸出路段向總共N個下一跳節點輸出經過編碼的內含有N個原始數據包的編碼數據包，依次按以下步驟實現路由優化傳輸：

步驟（1），無線傳感網初始化：

任意選擇至少一個簡稱為節點的無線傳感器定義為源節點S，把所述無線傳感器組成的無線傳感器網簡稱為網絡，再任意選擇至少一個簡稱為節點的至少另一個無線傳感點定義為目的節點D，并對所有節點給予節點號；

步驟（2），系統定義：

編碼優勢節點是指有編碼優勢的中間節點，所述編碼優勢是指對于一個中間節點X而言所能減少的向下一中間節點層中任何一個節點發送編碼數據包的次數的絕對值，對于單輸入單輸出節點，編碼優勢為零，對于雙輸入雙輸出節點，編碼優勢為1，對于N輸入N輸出節點，編碼優勢為N-1，N為有限正整數；

路徑優勢值f(hop,advan)，hop是跳數，advan是編碼優勢，其中：

對于源節點S到中間節點X而言，hop是指從源節點S到所述中間節點X的總跳數，在數值上等于從源節點S到中間節點X這一路徑段上包括源節點S在內的總結點數減1，advan是指所述這一路徑段上的路徑的編碼優勢值，在數值上等于所述這一路徑段上不包括源節點S在內的所有中間節點X的編碼優勢之和；

對于源節點S到目的節點D而言，hop是從源節點S到目的節點D的總跳數，在數值上等于從源節點S到目的節點D這一路徑段上包括源節點S在內的總結點數減1，advan是指所述這一條全路徑上的全路徑的編碼優勢值，在數值上等于所述這一條全路徑上不包括源節點S、目的節點D在內的所有中間節點X的編碼優勢之和；

f(hop,advan)＝-m×hop+(1-m)×advan,

0＜m＜1,

其中，對于中間節點X而言，f(hop,advan)是指路徑段優勢值；

對于目的節點D而言，f(hop,advan)是指全路徑優勢值；

m是對應于跳數的權重，為設定值，反映了在所述無線傳感器網絡中對傳輸速率或降低能耗的傾向性；

路由請求包，來自源節點S并由本節點向下一跳發送，包括：下一跳節點的廣播地址、源節點地址、目的節點地址、路徑域：指數據包從源節點到本節點所經過的所有中間節點的地址，按路徑順序排列、跳數：指源節點S到本節點所經過的總跳數、路徑段的編碼優勢值，所述路徑段是指從源節點S到前一跳中間節點這一段路徑；

反向路由表，儲存在各中間節點，包括：源節點地址、上一跳節點地址、總跳數及路徑段優勢值；

路由回復包，是反向路由回復包，指從任何一個中間節點X或目的節點D出發，反向上傳到下一跳節點或源節點時的一種反向路由回復包，包括：下一跳節點地址、經過的路徑域、源節點地址、目的節點地址、跳數以及路段優勢值；

編碼數據包，包括：下一跳節點地址列表、目的節點地址列表、編碼系數和數據部分；

步驟（3），依次按以下步驟探索由源節點S到目的節點D的L條較優路徑，L為一個有限正整數：

步驟（3.1），源節點S基于自身傳輸半徑向各下行輸出的路段上的下一跳節點層內的節點廣播所述路由申請包；

步驟（3.2），步驟（3.1）中各所述下一跳節點接收到所述路由請求包后，執行以下步驟：

步驟（3.2.1），計算各自的路徑段優勢值f(hop,advan)，其中跳數加1，advan在數值上基于該請求包所經過的路徑段上的路徑的編碼優勢，把自己添加到路徑域之中形成一個更新的路由請求包同時將源節點地址、數據包的上一跳節點地址、跳數、路徑優勢值的信息存入節點的反向路由表中，更新的路由請求包一次性的下行發向下一跳節點層中的每一個節點，初始時，源節點的跳數和路徑段編碼優勢值為零；

步驟（3.2.2），重復步驟（3.2.1）直至到達目的節點為止，路徑優勢值等于全路徑段編碼優勢值，經過的路徑域為路由請求包中經過的路徑域，下一跳節點地址為經過的路徑域中的最后一個節點地址，源節點地址為路由請求包中的的目的地址，目的地址為路由請求包中的源節點地址，跳數為初始跳數即為零，使上述得到的下一跳節點地址、經過的路徑域、源節點地址、目的節點地址、跳數、路徑優勢構成一個路由回復包，反向上傳到路由請求包中的源節點S；

步驟（3.3），中間節點收到路由回復包則更新跳數值，即跳數加1，將路由回復包的包括上一跳節點地址、跳數、路徑優勢在內的信息存入節點路由表中，根據路由回復包中的經過的路徑域，將倒數第二個地址寫入下一跳地址，并將路徑域中自己的地址刪去；

步驟（3.4），重復步驟（3.3）直至到達路由請求包的源節點S為止，將路由回復包中的包括上一跳節點地址、跳數、路徑優勢在內的信息存入節點路由表中；

步驟（3.5），所述源節點S在收到下一跳中間節點層中各中間節點反向上傳的路由回復包后，對所有從相同目的節點D上傳的所述路由回復包中的全路徑段優勢值按從大到小的順序排成序列，選取前L條全路徑作為其優先選取的從所述源節點S到目的節點的全路徑，存入源節點S的優勢路徑段記錄，其中，L是任選的有限正整數，剩下的非優勢路徑段廢棄不用；

步驟（4），在所述無線傳感網中依次按以下步驟傳輸數據：

步驟（4.1），令a＝(a₁，a₂，...，a_K)^T表示源節點S要向下一跳單播的隨機網絡數據包稱為原始數據包，k是所述原始數據包的序號，k＝1，2，...，K，K也是所述原始數據包的總數；

步驟（4.2），按下式對步驟（4.1）中的所述原始數據包的數據部分進行隨機網絡編碼：

α_i＝P_i·a，i＝1，2，...，I，I≥K

P_i是編碼系數向量，P_i＝(P₁，P₂，...，P_K)，編碼系數向量P_i從一個有限正整數域中選取，共有I個且I≥K；

α_i是由K個原始數據經過隨機編碼后生成的編碼數據向量；

步驟（4.3），使步驟（3.5）中所述的L條優勢路徑在數值上等于所述編碼數據包的總數I，L＝I，在每條路徑只傳輸一個編碼數據向量α_i，稱為經過隨機編碼的數據部分，編碼數據包表示為{P_i，α_i}，于是在L條路徑上傳輸I個編碼數據包；

步驟（4.4），對于網絡中只有一個源節點和一個目的節點，多個源節點和一個目的節點，一個源節點和多個目的節點的或者多個源節點和多個目的節點的情況，當發送數據包時，對緩沖隊列隊頭的數據包進行如下處理：

第一種情況：若當該數據包準備發送時，節點緩存隊列中還存在另外一個路徑S→D上的多個編碼包，這些編碼數據包和待發送編碼數據包擁有同一個源節點和目的節點，則這些數據包出列并把這些數據包單獨進行如下處理：

當前編碼優勢節點接收到的編碼包中的編碼系數向量和編碼數據集合為{P_i，α_i}，當前節點A按本節點設定的再次隨機編碼系數向量Q中的各個分量q_q對輸入的各個所述源節點S的編碼數據進行再次編碼對數據再次進行隨機網絡編碼，其中下標q＝i,獲得新的編碼數據新的編碼系數向量向路由表中記錄的下一跳節點發送包含新的編碼數據和編碼系數向量的再次編碼數據包；

第二種情況：若該數據包準備發送時，節點的緩存中存在另一個目的節點的數據包，使得這兩個數據包傳輸的兩條路徑在當前節點具有一種編碼機會，則對這兩個數據包的數據部分進行再次編碼，不妨設這兩個數據包的編碼數據包的數據部分α_m＝P_mα和β_n＝Q_nβ以及相應的編碼系數P_m和Q_n，進行隨機網絡編碼獲得編碼數據部分γ＝pα_m+qβ_n，將編碼后的數據部分γ＝pα_m+qβ_n存在數據包的數據部分，將編碼系數(p,pP_m,q,qQ_n)存在數據包的編碼系數向量部分，并將兩條不同路徑的下一跳節點地址都放到數據包的接收節點的地址位置，將兩條不同路徑的目的節點地址都放到數據包的目的節點的地址位置，將編碼數據包發送出去；

第三種情況：當該數據包準備發送時，若以上兩種情況都不滿足，則直接向下一跳節點發送該數據包；

步驟（4.6）,當接收數據包時，若該數據包的下一跳節點只包含當前節點且當前節點不為目標節點時，則更新數據包下一跳節點信息且放入緩沖隊列等待發送；若到達當前節點的數據包包含不止一個下一跳節點，則首先判斷數據包為步驟（4.5）中所述的第二種情況下產生的再次隨機編碼包，即如果中間節點發現數據包的下一跳節點地址列表除了自己在外還有其他節點，則認為該數據包是步驟（4.5）所述的編碼數據包，按以下步驟進行解碼：

查找目的節點地址列表存在除去本節點要接收的數據包的目的節點D之外的另一個數據包的目的節點D'，隨后在混雜數據存儲區查找該目的節點D'對應的數據包數據部分β_n＝Q_nβ，利用數據包中的編碼系數(p,pP_m,q,qQ_n)將兩者的數據部分γ＝pα_m+qβ_n和β_n＝Q_nβ進行隨機網絡解碼，解碼過程如下：

pα_m＝γ-q·β_n

這樣中間節點獲得本節點所要傳輸的編碼數據pα_m以及相應的編碼系數pP_m，若目的地址為當前節點則接收信息，否則解出來的編碼數據包及其編碼系數打包放入緩存隊列等待傳送；

步驟（4.7），重復步驟（4.4）-步驟（4.6）直至緩存隊列數據包全部傳送成功；

步驟（4.8）,所述目的節點D收到多個編碼數據包，從中任意取出K個編碼系數線性無關的編碼數據包,并獲得編碼數據和系數用所述的編碼數據和系數按下式解碼出原始數據包序列a＝(a₁，a₂，...,a_K)^T：

(αD1,αD2,...,αDK)T=PD1PD2···PDKTa=PDa,]]>

a＝P_D^-1α_D,