深空通信中LTP協議選窗概率優化

王燕,程子敬,金亮,田小路,郝曉強,王鵬宇

航天恒星科技有限公司,北京 100191

1 引言

在深空通信延遲/容忍網絡DTN(delay/disruption tolerant network,DTN)中傳輸的數據有圖像、視頻、文本等多種不同數據類型、用戶對接收不同類型的數據準確性有不同的要求,對如圖像、視頻等類型的數據誤差率要求比較高,在接收端能以較高的成功率恢復出原有信息,對如文本等非重要數據允許在傳輸中有一定程度的誤碼率,但是非重要數據不可缺少。

針對深空通信中[1-3]數據差異傳輸的要求,很多學者將擴展窗不等差噴泉編碼思想引入到深空通信匯聚層文件傳輸LTP協議(licklider transmission protocol,LTP)中,并對LTP中的數據傳輸進行了研究[4-6]。

擴展窗不等差噴泉編碼思想是將待傳輸文件數據包按重要程度不同放置于不同窗口,并采用無需反饋、無固定碼速率方式進行傳輸,當深空中通信鏈路通暢的時候,信息在發送方像噴泉一樣進行發射,接收方接收一定數量的數據包后就能大概率還原出原數據包。

LTP協議對這些數據進行封裝傳輸時,高等級的重要數據應得到高可靠的傳輸,相對不重要的數據允許有一定程度丟包和誤碼,這樣在同等誤碼率、同等數量數據包情況下能更大程度上保障重要數據的傳輸成功率[1,7-9]。

為提高通信傳輸中不等差數據的傳輸效率,有很多針對LTP協議中擴展窗不等差噴泉編碼的選窗概率函數進行的研究優化設計,文獻[10]中對度分布函數進行重新設計,提出了一種以最大化平均恢復概率為目標的優化方法,但實現過程繁瑣。文獻[11]中采用傳統的遺傳算法對其進行優化,傳統的遺傳算法收斂迅速,能以較快的時間得到結果,但是選窗概率函數的精確度較低,由此影響了傳輸數據包的整體誤碼率較高、不同重要級別的傳輸數據的誤碼率差異性不明顯。文獻[8]中提出了用蟻群算法對選窗概率進行優化設計,在同等的傳輸數據包的情況下,蟻群算法的收斂速度比較慢,需要較長時間來尋找出最優解空間。

針對上述情況,在文獻[8,11-13]的研究基礎上,提出了一種新的選窗概率優化方法,對協議中的關鍵影響因素選窗概率函數進行優化,兼顧重要等級的數據被大概率選中不重要數據也不能被忽略遺漏的傳輸要求,能在較短時間內獲得較高的總數據包的精確度和重要數據的低誤碼率,不重要數據的誤碼率在接受范圍內,提高通信鏈路資源利用率,滿足差異化信息傳輸要求

2 LTP協議在深空通信中的應用

信道誤碼率高、傳輸距離遠、反向的和前向信道上數據傳輸存在有較大的帶寬不對稱性、空間鏈路不連續、損耗大,深空通信的上述特點使得深空通信和地面通信體制有很大的不同和差別。

深空通信特有的傳輸特點導致在地面上運行性良好能且具有廣泛適用性的TCP/IP協議,在深空通信環境下無法正常工作。一種新的網絡體系機構和體制DTN網絡和LTP協議由此應用而生,以此滿足深空通信的應用需求[11]。

LTP協議摒棄TCP/IP協議三次握手機制,采用存儲轉發的模式將可靠和不可靠傳輸兩種傳輸服務整合在一個數據塊進行以適應深空通信中長時延、鏈路不連續的通信特質。LTP協議中以紅色數據代表重要數據(MIB),綠色數據代表不重要數據(LIB)(下文統一簡稱“紅綠數據”),對于紅色數據對其進行可靠傳輸,基于ARQ自動重傳機制需要校驗和重傳;而對于綠色數據進行不可靠傳輸,無論其是否發生丟棄或損壞,都無需校驗和重傳。但LTP文件傳輸中的ARQ反饋多輪重傳等機制往返延遲大,為更好的適應深空通信,提高通信效率,在LTP文件傳輸時借鑒了擴展窗不等差噴泉碼的思想,以此減少其在深空通信中數據重傳的問題,適應深空通信中不同權重的數據差異化傳輸的需求。

3 LTP協議中的擴展窗不等差噴泉碼

在刪除信道環境下,擴展窗不等差噴泉編碼(expanding window unequal protection,EXUP)將需要傳輸的文件劃分為N個數據包,將其中所有M個MIB數據包放在窗1中(M

(1)

選窗概率函數是和度(d)分布函數相關聯的一個指數函數。其中A和B是兩個常數,A的取值范圍為(0

(2)

式中:度(d)的取值范圍為1到N,τ(d)和ΩISD(d)以及和β具體函數定義如下公式(3)、(4)、(5)所示:

τ(d)函數中的定義如下所示:

(3)

其中公式(2)中ΩISD(d)定義為如下的函數,式(4)所示:

(4)

公式(2)中的β函數為ΩISD(d)和τ(d)的和,β函數定義如下函數(5)所示:

(5)

選窗概率很大程度上決定了MIB數據和LIB數據被選中的次數和發送數據包中MIB和LIB的占比,同時也間接影響了MIB和LIB數據在解包過程中誤碼率的高低。選窗概率是LTP協議傳輸中關鍵影響因素,決定了深空通信中數據傳輸的準確程度,是LTP協議中信息差異傳輸的關鍵所在。

4 基于自適應遺傳算法的選窗概率優化設計

選窗概率函數是非線性函數,其解空間是一組離散的數值序列組合,解的取值空間比較寬泛,很難用傳統計算方法獲得解空間的精確值。來源于自然界生物進化論的自適應遺傳算法是一種具有多參數、多組合的全局優化方法,能從紅綠數據誤碼率的集合中,逐步找到紅綠誤碼率的最優組合,大幅降低重要數據傳輸中的重傳次數,體現LTP協議中的差異傳輸需求,提高數據傳輸性能[6]。

傳統的遺傳算法(genetic algorithms,GA)在優化種群時,會由于算法中的交叉、變異等參數設置固定化,無法適應種群中不同個體動態變化需求,從而導致種群收斂速度過快,在求最優解的過程中容易陷入局部最優而引起種群提前老化的問題,進而影響種群中進化個體的精度。

自適應遺傳算法(adaptive genetic algorithms,AGA)在傳統遺傳算法的基礎上能根據自適應方式,自動調整交叉和變異因子,解決因交叉、變異概率固定而引起的無法求解種群中的最優解以及種群中產生的子代不如父代的問題。自適應遺傳算法盡量使產生的子代效果得到最大化進化,從而在很大程度上提高了算法的收斂精度。

自適應遺傳算法的選窗概率優化設計由編碼方式、適應度函數、選擇操作、交叉函數、變異函數與優化步驟六個部分組成。在基于自適應遺傳算法的選窗概率函數優化算法中,設定要優化的選窗概率函數的精度為0.0001,選窗概率函數的取值范圍為[0.0000,0.9999];設定實際傳輸發送數據包個數為k,并從1～k依次定義為各發送數據包選窗概率函數度(d)的取值。選窗概率的優化問題轉化為對不同度(d)值對應的選窗概率函數θ值的優化,得到其關于度(d)的最佳分布為最終優化的結果導向。

4.1 編碼方式

設定種群(解空間)中個體數為num個,每個個體(單個解)代表一組d從1到k對應的選窗概率值。對每個個體進行二維矩陣編碼,矩陣的列定義為選窗概率函數θ值,矩陣的行定義為度d值。選窗概率函數的精度為0.0001,二維編碼矩陣中共有10000行,對應的θ值從0.0000至0.9999;實際發送數據包個數為k個,二維編碼矩陣中共有k列,有k個度(d)值,依次為1至k;對矩陣中每個元素的值θ(d)進行初始化,根據選窗概率函數中θ是隨度(d)的增加而下降的定義,θ(d)初始化條件約束如下:d從1開始取值,當d取值為n時(1

4.2 適應度函數

適應度函數在選窗概率中作為對種群中個體優劣的判據指標,直觀的反應種群中個體進化適應情況。種群中的個體根據適應度函數計算出來的值,作為判斷個體是否優異于父代的依據。誤碼率能精準直觀快速的反應出通信中數據包傳輸的優劣情況,本優化算法中選用紅綠數據的誤碼率作為適應度函數。

擴展窗不等差噴泉的譯碼(解包)采用的是與或樹的方法,該方法能夠依據二分圖中葉子節點與根節點之間的關系,根據經過l次迭代得到紅綠數據的誤碼率公式。其中MIB紅窗數據和LIB綠窗中數據的誤碼率,見式(6):

(6)

式中:l為迭代次數;yl,M為紅數據的誤碼率;yl,L為綠數據的誤碼率;k為輸數據包數量;公式中的p1=θ1/(a1×k)+θ2/k;p2=θ2/k;q1=θ1+θ2×a1;ε為編碼冗余;ε=N/k;此處的N為收端收到的數據包的數量;u為編碼包的平均度數;θ1為紅窗的選窗概率值;θ2為綠窗的選窗概率值。a1是紅數據占總數據包的比率,同理a2是綠數據的占比率。

假定MIB和LIB數據的誤碼率分別用PM和PL表示,自適應遺傳算法將PM和PL作為適應度函數,通過自適應遺傳算法中的操作設計,在下一代種群中(下一次解的優化范圍中)保留PM值比父代高,但是PL的值在預期范圍內的個體。PM值的提高保障了重要數據傳輸的可靠性和正確率,同時將PL的值控制在可接受的范圍內,保障綠數據也能被正常選中并進行傳輸。因PM和PL的結果為負指數函數,為了計算和對比能更加直觀表現最后的實驗結果,優化設計取PM和PL的對數值負數的值,即取-lg(PM)和-lg(PL)進行計算,將其結果轉換為正數后進行對比。得到本優化算法中的最終適應度函數表達式為式(7)所示:

fitness=-lg(PM)-|-lg(PL)-(-lg(P0))|

(7)

式中:P0為綠色誤碼率預期值,適應度fitness的值越大,表明種群中該個體的不等差的差異性越好,個體的優異性更佳,在下一代的進化中被種群中的個體被選中或者是被遺傳的概率會更大。

4.3 選擇操作

選擇操作在交叉變異操作之前進行,是交叉變異操作的前提和基礎。選擇操作是從種群中保持父代部分個體的同時又選擇一部分優勝父代的子代個體,重新組成新的種群過程。它是一個作用于整個群體的參數。假定選擇算子Ps參數設定的值為0.4,那么這個種群中有60%的個體直接繼承自父代,40%的個體要經過選擇,進入到下一代的種群中。選擇的依據是將每個個體fitness的大小作為輪盤賭篩選算法中的分子(分母是所有個體fitness的和)作為被選中種群下一代優異個體的概率值。fitness值越大,被選中的概率值也就越大。經過選擇操作后,種群淘汰了部分優異性差的個體,保留了更多優異性高的個體,經選擇后形成的新種群中的個體沒有變異發生,只是父代種群中優異個體的數量有所增加。

4.4 自適應交叉函數

經過選擇操作后形成的新種群,進入到優化設計的交叉操作中。假定交叉因子為Pc,不同于傳統的遺傳算法交叉算子是對種群中的每個個體都是相同的固定值,自適應的交叉算子是根據種群中每個個體自身情況不同,有不同的交叉因子,以便交叉出更優秀的種群后代,其中的變異算子Pc的公式(8)如下:

(8)

式中:fmax是種群中最大的個體適應度值,即種群中fitness值最大的個體;f′是兩個要交叉的個體中適應度值較大的個體的適應度值;favg是種群中所有個體的平均適應度值;就是種群中所有個體fitness的平均值,而pk1,pk2是0和1之間的常數,設定pk1,pk2的值后,交叉概率就可以根據自身fitness情況的不同進行自適應地進行調整。通過自適應交叉函數可以看出,種群中fitness值越小的個體進行兩兩個體交叉的概率就會越大,反之fitness值大的個體,兩兩交叉的概率會減小甚至為零。從上述公式中可以得出如下結論,自適應交叉函數督促個體適應度值低的個體,提高向更好方向進化的概率。經過交叉自適應調整操作,種群中fitness值低的個體,獲得更高的向優異個體進化的可能,自適應交叉操作使得群體中不同fitness個體的差異性進行進化,避免解空間提前老化。交叉操作后得到有num個個體的新種群。

4.5 自適應變異函數

變異函數作用于交叉操作后的種群,假定變異算子為Pm,變異算子使種群中個體不借助群體中個體間的交叉操作,只靠自身的變異向性能更好的方向進化(向最優解靠近),為種群個體的進化提供另外一種進化的方式。自適應變異操作一定程度限制了種群陷入局部最優。其中變異算子Pm的公式為:

(9)

式中:f是要變異的個體的適應度值;pk3,pk4是0和1之間的常數,設定pk3,pk4之后,變異概率就可以個體自己的的fitness值的具體情況計算得到。從式(9)可以看出,fitness值越大的個體,自身變異的概率越小,反之個體自身變異的概率就越大,變異算子保證了適應度值低的個體,有較高的變異概率,促使其變異出更優質的個體,防止種群過早地進入局部最優解與解空間的提前老化。經過變異操作后,形成了有交叉和變異后組成的全新種群,種群的個體數為num個。

4.6 選窗概率優化步驟

1)種群個體數為num,即解空間數量為num個,根據上述中的編碼設計方法對種群進行編碼,隨機產生初代種群,形成num個二維編碼矩陣。

2)根據適應度函數計算每個個體的適應度fitness。

3)根據選擇算子、交叉函數、變異函數,計算出每個個體的自適應交叉算子、自適應變異算子,根據自適應遺傳的進化順序,依次進行選擇操作、交叉操作、變異操作,產生新種群(新的解空間)。

4)記錄每一代種群中fitness值最大個體的MIB、LIB的誤碼率值以及選窗概率的值(及其對應的度的值)。

5)判斷是否達到迭代次數。

重復2)～5)步,得到最優選窗概率函數的集合,即最優解的集合。

5 實驗結果分析

通過MATLAB對LTP協議中紅綠窗中選窗概率優化進行仿真,并根據經驗值對仿真中所用到的參數進行賦值。設定實際傳輸發送的數據包數k=500,冗余度為ε=1.3,公式(3)中的選窗概率函數τ(d)中的參量值c=0.1,δ=0.05,MIB數據占比a1=0.4,LIB數據占比a2=0.6,即紅色MIB數據包個數為200,綠色LIB數據包個數300。綠色數據的預期誤碼率為-lg(p0)=2.5。自適應遺傳算法種群個體數量為num=30,選擇算子Ps=0.4、自適應交叉和變異中的常量pk1、pk2、pk3、pk4的取值分別為pk1=1、pk2=1、pk3=0.6,pk4=0.6,交叉算子Pc和變異算子Pm根據每個個體的不同而自適應的進行調整,迭代次數l=30。

在傳統遺傳算法中,除交叉算子的取值為固定值Pc=0.6,變異算子的取值為固定值Pm=0.6外,其余的發送數據包、冗余度、選窗概率中的參量值、紅綠誤碼率的期望值、迭代次數等參數的取值和自適應遺傳算法的賦值是相同的。上述取值相同,是為了讓自適應遺傳算法和傳統遺傳算法在初始數據上盡可能接近相同。

經過自適應遺傳算法、傳統遺傳算法對選窗概率函數優化后得到紅綠數據誤碼率與迭代次數的關系如圖1,圖2所示。

圖1 自適應遺傳算法紅窗數據誤碼率

圖2 自適應遺傳算法綠窗數據誤碼率

從圖1、圖2中的自適應遺傳算法優化后的實驗結果上看,隨著迭代次數的增加,種群的紅色數據的誤碼率在逐步的降低,迭代到18次時候,紅綠窗中的數據誤碼率趨于穩定一致。由紅綠數據的最優誤碼率圖(圖1、圖2)的曲線中可以看出種群中的紅窗的誤碼率從10-9.7755下降至10-16.3862,綠窗的誤碼率由10-4.4469上升為10-2.8765。MIB的誤碼率下降幅度較大,LIB誤碼率上升較緩,MIB的誤碼率顯著低于LIB的誤碼率。

自適應遺傳算法通過對種群的30個個體的第一次迭代和優化后的紅綠總誤碼率統計對比(藍色線為第一次迭代種群總誤碼率,橙色線為優化后種群總的誤碼率),得到如圖3所示種群總誤碼率的對比圖。

圖3 自適應遺傳算法總誤碼率對比圖

從上圖3總誤碼率對比圖可以看出,種群總誤碼率從初始化的10-12.2934,經過迭代優化后總誤碼率下降為10-18.6212,將數據總誤碼率降低了106.3278個數量級,整體上提高了數據傳輸的有效性。

圖4、圖5是傳統遺傳算法下種群迭代30次后的紅綠誤碼率的結果圖,從實驗結果的曲線圖中可以看出,傳統遺傳算法在迭代第6次的時候紅綠窗戶的數據趨于穩定一致,由紅綠窗數據最優誤碼率曲線中可以看出,傳統遺傳算法中的紅窗中數據的誤碼率從10-10.0847下降至10-11.1298,綠窗中數據的誤碼率由10-4.3631上升為10-4.0846。MIB的誤碼率下降幅度緩慢,LIB誤碼率上升較緩,MIB和LIB誤碼率對比差異不明顯。

圖4 傳統遺傳算法紅窗數據誤碼率

圖5 傳統遺傳算法綠窗數據誤碼率

傳統遺傳算法對種群的30個個體的第一次迭代和優化后綠窗總誤碼率統計對比(藍線為第一次迭代種群總誤碼率,橙線為優化后種群總的誤碼率),得到如下圖6所示的種群的總誤碼率對比圖。

圖6 傳統遺傳算法總誤碼率對比圖

從圖6傳統遺傳算法總誤碼率折線圖可以看出,種群總誤碼率從初始化的10-12.3677,經過30次迭代優化后總誤碼率為10-15.2148,數據總誤碼率降低了102.8471個數量級。

對比上述自適應遺傳算法(AGA)和傳統遺傳算法(GA)的紅綠窗實驗結果表明,自適應遺傳算法比傳統的遺傳算法更能滿足深空通信中不同權重數據對誤碼率不同的傳輸要求。通過對選窗概率函數的優化,在保障綠窗數據誤碼率在可接受范圍內的前提下,自適應遺傳算法比傳統遺傳算法在紅窗、紅綠數據總誤碼率方面能極大降低紅數據的誤碼率,紅綠數據包整體的總誤碼率,優化后的算法收斂迅速,精度較高。

在上述圖1、圖2紅綠數據的誤碼率的情況下,自適應遺傳算法優化后的選窗概率的分布曲線如下圖7所示。

圖7 自適應遺傳算法選窗概率圖

圖7中選窗概率的仿真結果可知在預期誤碼率為10-2.5時,優化后的紅窗(窗1)的選窗概率函數θ1的取值為:

θ1= 0.9451d1+ 0.9133d2+ 0.8600d3+ 0.7504d4+ 0.6929d5+0.0295d6+0.0027d7+0.0013d8+0.0013d9+ 0.0005d10+ 0.0001d11。

上述結果中的dn代表度為n,即選取n個數據包組成發送包,dn的系數表示每次選取數據包時從窗1選擇一個數據包的概率。

6 結論

深空通信DTN網絡LTP協議層中存在傳輸距離遠、空間鏈路不穩定、信息差異傳輸糾錯代價高的實際情況,現有算法對協議傳輸中的選窗概率函數進行優化時存在收斂速度、總誤碼率的精確度、差異傳輸精確度較低、差異化不明顯的問題。本文分析了深空通信差異傳輸的應用需求,通過編碼方式、自適應度變異函數、自適應交叉函數、選擇操作等步驟對LTP傳輸協議中選窗概率函數進行優化設計,獲得了自適應遺傳算法的模型和優化流程。借助Maltlab對其進行仿真,實驗的結果驗證了該優化設計的有效性。此優化設計保障重要數據傳輸的正確率和降低總體信道誤碼率,減少因重要信息誤碼率高而導致的信息重傳,能更好地滿足深空通信差異傳輸的需求。

為進一步提高數據傳輸的正確率,在信息封裝時能精準的選擇符合預期的數據,下一步將深入分析適應度函數中的紅綠數據預期值的關系與權重,精煉簡化適應度函數,同時優化設計流程的步驟,使其能更好的適用于深空通信中。