應用網(wǎng)絡(luò)編碼的空間信息網(wǎng)多徑路由協(xié)議設(shè)計

韓歡 韓笑冬 王睿 安衛(wèi)鈺 張呈

(中國空間技術(shù)研究院通信衛(wèi)星事業(yè)部，北京 100094)

空間信息網(wǎng)[1]是由地面站、衛(wèi)星、空間站和載人飛船等具有空間通信能力的航天器共同組成的互聯(lián)互通的網(wǎng)絡(luò)信息系統(tǒng)，可實現(xiàn)天、空、地之間的通信?？臻g信息網(wǎng)具有覆蓋面大、不受地理限制、組網(wǎng)靈活快速等特點，能為海、陸、空各種任務提供集成的通信服務，具有十分重要的應用價值。

受空天環(huán)境及低軌衛(wèi)星網(wǎng)絡(luò)拓撲動態(tài)變化的影響，空間信息網(wǎng)的誤碼率較高，易發(fā)生丟包現(xiàn)象，且鏈路時延大，時延抖動嚴重，采用傳統(tǒng)的報文傳輸及重傳機制將極大地增加網(wǎng)絡(luò)的傳輸代價，因此，適合空間環(huán)境的路由技術(shù)一直是空間信息網(wǎng)研究的熱點。當前，空間信息網(wǎng)的路由技術(shù)大多針對衛(wèi)星網(wǎng)絡(luò)，研究主要集中于服務質(zhì)量(QoS)路由技術(shù)[2]、負載均衡路由技術(shù)[3]及多服務路由技術(shù)[4]3類，但是這些技術(shù)并未有效地解決空間信息網(wǎng)的長時延、高誤碼率等問題。為此，本文提出一種應用網(wǎng)絡(luò)編碼的空間信息網(wǎng)多徑路由協(xié)議，采用流量分配的機制建立最優(yōu)的3條路徑，同時在數(shù)據(jù)傳輸過程中應用網(wǎng)絡(luò)編碼模式提高傳輸?shù)目煽啃裕酚删S護采用中間節(jié)點重傳機制，可減少傳統(tǒng)端到端重傳的長時延和高開銷。

1 多徑路由建立

應用網(wǎng)絡(luò)編碼的多徑路由協(xié)議，在路由的建立中主要以帶寬時延作為接入限制，以跳數(shù)、誤碼率、路徑可用度和吞吐率等參數(shù)作為重要因子，建立源節(jié)點與目的節(jié)點之間的多徑路由。當源節(jié)點有數(shù)據(jù)需要向目的節(jié)點發(fā)送且沒有到達該目的節(jié)點的路由時，源節(jié)點發(fā)起路由請求，開始路由的建立，具體步驟如下。

(1)源節(jié)點廣播路由請求報文(Route Request，RREQ)，報文包含路徑節(jié)點列表、最大跳數(shù)限制、節(jié)點擁塞度列表、鏈路丟包率、接入帶寬限制等參數(shù)(見表1)，同時將當前時間填入到<發(fā)送時間>中。

表1 RREQ各域定義

(2)中間節(jié)點收到RREQ報文后判斷本節(jié)點的擁塞度、帶寬是否滿足路由請求要求。若不滿足上述兩個條件，則丟棄報文；否則，更新路由并轉(zhuǎn)發(fā)RREQ報文。

(3)目的節(jié)點收到第1個報文后啟動定時器，記錄TD(由目的節(jié)點D根據(jù)傳輸業(yè)務需求確定)時間內(nèi)收到的所有RREQ中的路徑信息，并對多條路徑信息進行評估，根據(jù)路徑可用度選擇最優(yōu)的3條節(jié)點不相交路徑，最后沿著3條路徑的反方向給源節(jié)點發(fā)送應答報文(Route Reply，RREP)。第I條路徑的可用度用RI表示，其表達式為

(1)

(4)中間節(jié)點收到RREP報文后讀取源節(jié)點和目的節(jié)點信息，建立到達目的節(jié)點的動態(tài)前向路由，并向下一跳轉(zhuǎn)發(fā)RREP報文。

(5)源節(jié)點收到RREP報文后，獲取路徑信息，并通過鏈路的擁塞度及可用度對各路經(jīng)進行合理的流量分配，實現(xiàn)負載的均衡，最終完成多徑路由的建立。

2 應用網(wǎng)絡(luò)編碼的多徑數(shù)據(jù)傳輸

2.1 基本思想

網(wǎng)絡(luò)編碼[5-6]的主要思想是網(wǎng)絡(luò)中的各個節(jié)點對收到的數(shù)據(jù)進行線性或者非線性的組合后再轉(zhuǎn)發(fā)，最后在目的節(jié)點解碼恢復出原始的數(shù)據(jù)包。與傳統(tǒng)的路由傳輸方式相比，網(wǎng)絡(luò)編碼可以提高信息傳輸率，節(jié)約傳輸所需能量，增加傳輸?shù)目煽啃院桶踩?，現(xiàn)廣泛應用于Ad hoc等無線網(wǎng)絡(luò)[7-8]。

多徑路由傳輸思想如圖1所示。其中：S為源節(jié)點；Z1，Z2，Z3為中間節(jié)點；Y為編碼后的數(shù)據(jù)包。S采用3條不相交多徑路由向目的節(jié)點D發(fā)送數(shù)據(jù)包A，B，C，對于采用傳統(tǒng)傳輸方式的圖1(a)，鏈路的誤碼率導致數(shù)據(jù)包A和B丟失，源節(jié)點需要重傳丟失的數(shù)據(jù)，增加了信息傳輸?shù)臅r延和網(wǎng)絡(luò)開銷；對于應用網(wǎng)絡(luò)編碼傳輸方式的圖1(b)，由于源節(jié)點和中間節(jié)點對數(shù)據(jù)進行編碼后再傳輸，最后目的節(jié)點接收到的多個數(shù)據(jù)包通過解碼得到數(shù)據(jù)包A，B，C。由此可知，應用網(wǎng)絡(luò)編碼的多徑路由傳輸，通過編碼冗余可提高空間信息網(wǎng)數(shù)據(jù)傳輸?shù)目煽啃?，減少了重傳次數(shù)。

目前，應用網(wǎng)絡(luò)編碼的多徑路由傳輸都是通過增加冗余包的數(shù)量來提高傳輸可靠性，增大了網(wǎng)絡(luò)的開銷，因此如何合理的對數(shù)據(jù)編碼個數(shù)進行選取，在保證數(shù)據(jù)傳輸可靠性的同時又不會引起網(wǎng)絡(luò)開銷過大，是應用網(wǎng)絡(luò)編碼傳輸需要解決的一個難題。針對這一難題，本文提出一種綜合考慮收到的數(shù)據(jù)包及鏈路誤碼率確定最優(yōu)編碼次數(shù)的策略。

圖1 2種多徑路由傳輸方式對比

2.2 數(shù)據(jù)傳輸

2.2.1 源節(jié)點編碼

當源節(jié)點建立多條路徑之后，開始對原始數(shù)據(jù)進行編碼。

(1)對需要傳輸?shù)臄?shù)據(jù)包進行分組。源節(jié)點將N個數(shù)據(jù)包分成一組，記為X1，X2，…，XN，并賦予相同的組標志符(從0開始遞增)；分組后根據(jù)鏈路狀況確定編碼個數(shù)，通過增加冗余來解決空間信息網(wǎng)高誤碼率帶來的丟包問題。M(S)表示源節(jié)點實際要發(fā)送數(shù)據(jù)包的個數(shù)，計算公式為

(2)

式中：P[S,H]為源節(jié)點S與下一跳節(jié)點之間的鏈路傳輸成功率，其值可以通過周期性地向鄰居節(jié)點發(fā)送HELLO包得到；E(S)為源節(jié)點S的所有下一跳節(jié)點集；min(P[S,H])為源節(jié)點S與下一跳節(jié)點鏈路狀況最差值。

(2)選取編碼系數(shù)。從有限域[9]F中隨機選取M(S)組數(shù)，每組數(shù)中又包含N個系數(shù)(ki,1,ki,2,…,ki,N)，對數(shù)據(jù)包進行線性編碼，產(chǎn)生新的數(shù)據(jù)包Yi，編碼公式為

(3)

式中：j=1,2，…，N。

(3)發(fā)送數(shù)據(jù)。將組標志、編碼向量等信息作為包頭加入到生成的數(shù)據(jù)包中，并發(fā)送到網(wǎng)絡(luò)中，如圖2所示。在發(fā)送的過程中，源節(jié)點充分利用多徑路由的優(yōu)勢，根據(jù)每條路徑的路徑可用度分配不同數(shù)目的數(shù)據(jù)包。這種傳輸方式將數(shù)據(jù)包分散到各節(jié)點上，且通過編碼有效地保證了數(shù)據(jù)包的安全性。

圖2 網(wǎng)絡(luò)編碼過程

2.2.2 中間節(jié)點重編碼

中間節(jié)點根據(jù)收到的數(shù)據(jù)包及鏈路誤碼率確定最優(yōu)的編碼策略。當中間節(jié)點p收到第1個新批次的數(shù)據(jù)包時，啟動一個定時器，對時間T內(nèi)收到的數(shù)據(jù)進行重編碼。T要保證下一跳能接收到足夠多的數(shù)據(jù)包，因此T的計算公式為

T=M(u)·(T(p)-T(u))

(4)

式中：M(u)為節(jié)點p的上一跳節(jié)點u發(fā)送數(shù)據(jù)包的個數(shù)；T(p)為第1個數(shù)據(jù)包到達節(jié)點p的時間；T(u)為數(shù)據(jù)包從節(jié)點u出發(fā)的時間。

當計時結(jié)束時，中間節(jié)點就會對T時間內(nèi)收到的數(shù)據(jù)包進行重編碼，重編碼的次數(shù)選取會影響到數(shù)據(jù)傳輸?shù)目煽啃?，選擇合適的編碼個數(shù)可以有效地提高網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)目煽啃?。因此，對于中間節(jié)點，根據(jù)收到的數(shù)據(jù)包及鏈路狀況確定最佳的編碼個數(shù)M(q)，其確定規(guī)則如下。

(1)若N(q)=1，則直接向下一跳節(jié)點轉(zhuǎn)發(fā)，不再進行編碼操作。

(2)若N(q)=2，編碼次數(shù)計算公式為

(5)

(3)若N(q)>2且N(q)

(6)

(4)若N(q)>N/2，編碼次數(shù)計算公式為

(7)

式中：N(q)為中間節(jié)點q在時間T內(nèi)收到的來自上一跳節(jié)點u發(fā)送的具有相同組標志符數(shù)據(jù)包的個數(shù)；r為q的下一跳節(jié)點；P[q,r]為節(jié)點q與節(jié)點r之間的鏈路狀況；W為不相交路徑條數(shù)。

(8)

根據(jù)式(3)和式(8)，可以求出中間節(jié)點編碼后的數(shù)據(jù)包和源節(jié)點發(fā)送的數(shù)據(jù)包之間的關(guān)系，可表示為

(9)

(10)

式中：m=1,2,…,N(q)。

圖3 第M(q)個編碼數(shù)據(jù)包格式

Fig.3 TheM(q)-th coding data packet format

2.2.3 目的節(jié)點解碼

目的節(jié)點收到數(shù)據(jù)包之后先貯存。設(shè)在一定時間內(nèi)收到的數(shù)據(jù)包個數(shù)為N(D)，若N(D)>N，且收到的N(D)個數(shù)據(jù)包的系數(shù)線性無關(guān)，則通過矩陣進行解碼，恢復出原始數(shù)據(jù)包,解碼公式見式(11)；反之，若收到的N(D)個數(shù)據(jù)包的系數(shù)線性相關(guān)，或者N(D)

(11)

2.3 數(shù)據(jù)重傳機制

目前的數(shù)據(jù)重傳機制大多采用端到端、跳到跳的重傳機制，或者停等式重傳機制及選擇性重傳機制。這些機制對數(shù)據(jù)包的處理比較單一，采用數(shù)據(jù)包單個處理的思想，對每一個數(shù)據(jù)包的傳輸、丟失和重傳均逐一處理。而對于網(wǎng)絡(luò)編碼，其傳輸?shù)臄?shù)據(jù)包之間可以相互建立關(guān)系，節(jié)點可以從編碼包中同時獲取多個丟失的數(shù)據(jù)包。因此，可以對重傳機制加以改進。

若采用源節(jié)點重新編碼發(fā)送，則需要經(jīng)歷和原來數(shù)據(jù)包同樣的傳輸過程，這不僅浪費帶寬，也增大了開銷。因此，利用網(wǎng)絡(luò)編碼傳輸機制中各個節(jié)點可以對數(shù)據(jù)包進行處理的特殊性，本文提出一種中間節(jié)點重傳的方案，在使目的節(jié)點獲得足夠多可用于解碼的數(shù)據(jù)包的同時，節(jié)省了網(wǎng)絡(luò)的資源。

圖4是應用網(wǎng)絡(luò)編碼的重傳機制原理示意，源節(jié)點S與目的節(jié)點D間建立3條不相交路徑，3條路徑狀況各不相同，其中S-Z1-D路徑傳輸成功率最高。各節(jié)點采用網(wǎng)絡(luò)編碼對數(shù)據(jù)包進行傳輸，若目的節(jié)點未能收到可供解碼的足夠多的數(shù)據(jù)包，則等待Twait，見式(12)。

圖4 應用網(wǎng)絡(luò)編碼的數(shù)據(jù)重傳機制示意

(12)

Twait=0，表示節(jié)點無丟包，不需要請求重傳。在經(jīng)過Twait時間后，若Nmiss≠0，則生成反饋消息，包括丟失的數(shù)據(jù)包個數(shù)及組標志符。如圖4所示，目的節(jié)點D將反饋信息發(fā)給傳輸成功率較高的Z1節(jié)點。Z1節(jié)點收到反饋信息之后，對緩存內(nèi)的同一組標志符的數(shù)據(jù)包進行重編碼，其編碼次數(shù)ML計算公式為

(13)

式中：Nmiss為缺少的數(shù)據(jù)包個數(shù)；P[Z1,D]為上一跳節(jié)點Z1與目的節(jié)點D之間的鏈路狀況。

3 仿真及性能分析

采用網(wǎng)絡(luò)仿真-2(NS-2)平臺對提出的路由設(shè)計進行仿真。仿真的拓撲模型包括3顆地球同步軌道衛(wèi)星，50顆低軌道衛(wèi)星，組成一個覆蓋全球的衛(wèi)星網(wǎng)絡(luò)。為了有效地比較算法的性能，在仿真中設(shè)帶寬為2 Mbit/s，單跳鏈路報文丟失率為0.1，隨機設(shè)置10條恒定比特率(CBR)數(shù)據(jù)流，數(shù)據(jù)包發(fā)送速率為50 kbit/s，每個報文長度512 byte。通過改變每次的發(fā)包率(仿真中分別采用10包/秒，15包/秒，20包/秒，25包/秒，30包/秒，35包/秒，40包/秒)對應用網(wǎng)絡(luò)編碼的空間信息網(wǎng)多徑路由協(xié)議(SMNC)和傳統(tǒng)按需距離矢量多徑路由協(xié)議(AOMDV)的分組投遞率、路由開銷及端到端的時延進行仿真。2種協(xié)議采用相同的仿真環(huán)境，且對一條鏈路設(shè)置相同的鏈路誤碼率，仿真時間為100 s。

圖5為改變發(fā)包率時2種路由協(xié)議分組投遞率的變化情況。當發(fā)包率較少時，2種路由協(xié)議的分組投遞率都比較高；隨著發(fā)包率的增加，網(wǎng)絡(luò)擁塞現(xiàn)象日益突出，數(shù)據(jù)包丟棄率大大增加，分組投遞率曲線呈下降趨勢。從圖5中可以看出：SMNC的分組投遞率優(yōu)于AOMDV，應用網(wǎng)絡(luò)編碼的路由，數(shù)據(jù)傳輸時通過綜合考慮鏈路誤碼率增加了一定的冗余數(shù)據(jù)，優(yōu)化了網(wǎng)絡(luò)糾錯的能力，提高了數(shù)據(jù)傳輸?shù)某晒β?，減少了數(shù)據(jù)包的重傳，使分組投遞率較好；而AODMV由于網(wǎng)絡(luò)擁塞及鏈路誤碼率等因素導致數(shù)據(jù)包頻繁丟失，需要不停地重傳，從而加重網(wǎng)絡(luò)的負載，因此分組投遞率下降得較快。

圖6是隨著網(wǎng)絡(luò)發(fā)包率增大路由開銷變化曲線。當發(fā)包率較少時，2種協(xié)議的開銷主要來自路由建立時廣播的請求報文；隨著發(fā)包率的不斷增加，網(wǎng)絡(luò)負載也隨之加重，路由開銷曲線開始呈下降趨勢。由圖6可知：AOMDV的開銷大于SMNC的路徑，對于AOMDV來說，數(shù)據(jù)包在傳輸?shù)倪^程受鏈路誤碼率及網(wǎng)絡(luò)擁塞的影響，容易發(fā)生丟包現(xiàn)象，大量地重傳請求增大了網(wǎng)絡(luò)的開銷；對于SMNC來說，采用網(wǎng)絡(luò)編碼的數(shù)據(jù)包傳輸通過冗余數(shù)據(jù)提高了傳輸?shù)目煽啃裕哂喟?、編碼計算雖然增大網(wǎng)絡(luò)的一部分開銷，但與通信的整體能耗相比幾乎可以忽略不計，同時網(wǎng)絡(luò)編碼的傳輸機制減少了數(shù)據(jù)重傳的次數(shù)，從而減少了整個網(wǎng)絡(luò)的開銷，因此路由開銷比AOMDV小。

圖7是隨著網(wǎng)絡(luò)負載增大數(shù)據(jù)傳輸平均時延變化曲線。當網(wǎng)絡(luò)的負載較輕時，2種路由協(xié)議的數(shù)據(jù)包傳輸?shù)某晒Ω怕瘦^大，時延較短；但因受無線信道的影響，AOMDV會有少量丟包，數(shù)據(jù)的重傳會帶來一部分時延，對于SMNC來說，數(shù)據(jù)的編解碼也會帶來一定的時延，因此2種路由協(xié)議的傳輸時延差不多。隨著發(fā)包率的增加、負載的加重，2種協(xié)議的平均延遲曲線均呈上升趨勢。對于AOMDV來說，重擁塞及高誤碼率帶來的丟包，導致不停地從源節(jié)點進行重傳，對于空間信息網(wǎng)來說，其鏈路本身時延就較大，因此重傳更增大了傳輸?shù)臅r延。而SMNC首先通過網(wǎng)絡(luò)編碼增加了一定的冗余數(shù)據(jù)包，加大了傳輸?shù)某晒β剩瑴p少了重傳帶來的時延；同時，應用網(wǎng)絡(luò)編碼的重傳機制通過中間節(jié)點進行重傳，大大縮短了數(shù)據(jù)包的傳輸時延。因此，應用網(wǎng)絡(luò)編碼的多徑路由協(xié)議彌補了傳統(tǒng)多徑路由傳輸中存在的不足，有效地解決了空間信息網(wǎng)路由技術(shù)長時延、高誤碼率等問題，能為空間信息網(wǎng)提供可靠、可信、高效的數(shù)據(jù)傳輸。

圖5 分組投遞率

圖6 路由開銷

圖7 平均時延

4 結(jié)束語

針對空間信息網(wǎng)高誤碼率、長時延等問題，本文提出了一種應用網(wǎng)絡(luò)編碼的空間信息網(wǎng)多徑路由協(xié)議，通過帶寬時延等關(guān)鍵參數(shù)作為路徑可用度建立多條節(jié)點不相交的多徑路由，同時在數(shù)據(jù)傳輸?shù)倪^程中采用網(wǎng)絡(luò)編碼技術(shù)，增加網(wǎng)絡(luò)傳輸?shù)目煽啃裕瑴p少數(shù)據(jù)重傳的次數(shù)。另外，考慮到網(wǎng)絡(luò)編碼的優(yōu)勢，提出應用網(wǎng)絡(luò)編碼的重傳機制，通過中間節(jié)點進行數(shù)據(jù)包的重傳，減少數(shù)據(jù)重傳的時延，改善空間信息網(wǎng)傳輸時延長的問題。應用網(wǎng)絡(luò)編碼的多徑路由協(xié)議雖然提高了空間信息網(wǎng)的傳輸性能，但編碼算法較為單一且計算量較大，加重了CPU的負擔，因此未來需要繼續(xù)進行網(wǎng)絡(luò)編碼的研究，降低網(wǎng)絡(luò)編碼的復雜度，優(yōu)化編碼策略，以最小的代價最大化地提升路由傳輸?shù)哪芰Α?/p>