基于梯度和模糊神經(jīng)網(wǎng)絡(luò)的容遲網(wǎng)絡(luò)路由算法*

張文柱 趙貝

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室，陜西西安710071)

容遲網(wǎng)絡(luò)(DTN)是一種新型無線網(wǎng)絡(luò)體系結(jié)構(gòu)［1］．它泛指無線網(wǎng)絡(luò)節(jié)點間鏈路頻繁中斷、傳輸延遲巨大、可靠通信與端到端連接不能保證的一類網(wǎng)絡(luò)，包括星際網(wǎng)絡(luò)﹑戰(zhàn)爭網(wǎng)絡(luò)﹑移動Ad hoc網(wǎng)絡(luò)(MANET)和無線傳感網(wǎng)絡(luò)等．為DTN網(wǎng)絡(luò)提供一定質(zhì)量的網(wǎng)絡(luò)服務(wù)，已經(jīng)成為國內(nèi)外研究的重點．

DTN網(wǎng)絡(luò)的路由問題，以容遲、容斷為前提，以鏈路狀態(tài)及網(wǎng)絡(luò)拓?fù)涿枋鰹榛A(chǔ)，以路由決策為核心，實現(xiàn)分組高效轉(zhuǎn)發(fā)，達(dá)到提高網(wǎng)絡(luò)吞吐量的目標(biāo)［2］．為此，人們提出了多種基于泛洪和委托轉(zhuǎn)發(fā)思想的路由算法．文獻(xiàn)［3］中利用傳染泛洪算法有效地解決了鏈路通斷導(dǎo)致的拓?fù)渥兓瘑栴};文獻(xiàn)［2，4］中分別以鏈路的平均延遲和預(yù)測延遲為網(wǎng)絡(luò)量度來描述網(wǎng)絡(luò)拓?fù)?，引?dǎo)單一分組轉(zhuǎn)發(fā);文獻(xiàn)［5］中提出了一種基于概率和新鮮度的梯度路由算法，以避免網(wǎng)絡(luò)資源的浪費;文獻(xiàn)［6］中用多分量來描述網(wǎng)絡(luò)環(huán)境，可反映網(wǎng)絡(luò)拓?fù)涞淖兓?，通過加權(quán)綜合各分量得到傳輸成功概率，并將其作為分組轉(zhuǎn)發(fā)的依據(jù)．但這些算法存在占用大量網(wǎng)絡(luò)資源、網(wǎng)絡(luò)拓?fù)涿枋鰡我磺也粔蚓_﹑多分量網(wǎng)絡(luò)描述下的綜合算法不具有智能性、分組轉(zhuǎn)發(fā)策略效率低等缺點．

為此，文中提出了基于梯度和模糊神經(jīng)網(wǎng)絡(luò)決策的容遲網(wǎng)絡(luò)路由算法(RBGFNN)．首先，采用節(jié)點信息及節(jié)點間鏈路狀態(tài)信息來描述網(wǎng)絡(luò)，以改進(jìn)網(wǎng)絡(luò)描述向量［7-8］;接著，采用有限歷史信息的動態(tài)平均結(jié)合精確預(yù)測的方式來自適應(yīng)維護(hù)網(wǎng)絡(luò)描述向量的各分量，以提供更準(zhǔn)確的網(wǎng)絡(luò)量度;然后，采用具有豐富的邏輯規(guī)則庫和強化學(xué)習(xí)能力的模糊徑向基函數(shù)(RBF)神經(jīng)網(wǎng)絡(luò)進(jìn)行路由決策，以實現(xiàn)路由決策過程的智能化;最后，以節(jié)點間多跳傳輸成功概率為依據(jù)引導(dǎo)分組沿梯度方向轉(zhuǎn)發(fā)，以提高分組轉(zhuǎn)發(fā)效率，進(jìn)而實現(xiàn)提高全網(wǎng)整體吞吐量．

1 網(wǎng)絡(luò)狀態(tài)模式識別算法

DTN是一個包含多種傳統(tǒng)網(wǎng)絡(luò)形態(tài)的綜合概念，單純一種路由算法很難有效解決網(wǎng)絡(luò)在所有狀態(tài)下的路由問題．因此，應(yīng)該在網(wǎng)絡(luò)狀態(tài)模式識別的基礎(chǔ)上選擇使用不同的路由算法．

文中采用模糊邏輯對網(wǎng)絡(luò)狀態(tài)進(jìn)行識別．定義兩個邏輯輸入:(1)δ=/d，δ反映網(wǎng)絡(luò)內(nèi)各鏈路狀態(tài)變化的方差，v為節(jié)點運動速度，d為節(jié)點間距離;(2)各鏈路連接的平均時長反映了網(wǎng)絡(luò)內(nèi)各鏈路狀態(tài)的平均值．定義模糊規(guī)則如表1所示．以預(yù)測性能極強及預(yù)測性極差的典型網(wǎng)絡(luò)(如MANET和低軌通信)的δ/為標(biāo)準(zhǔn)點，將邏輯輸入劃分 L、M、H模糊類，如圖1所示．將DTN網(wǎng)絡(luò)分為3種可識別網(wǎng)絡(luò)狀態(tài)模式:頻繁移動預(yù)測性能極差(ER)﹑移動規(guī)律預(yù)測性能極強(PR)﹑運動復(fù)雜預(yù)測性能適中(UR)．根據(jù)識別結(jié)果，ER模式應(yīng)采用泛洪類算法，PR模式應(yīng)采用預(yù)測性算法，而文中算法適用于UR模式，如圖2所示．

表1 模糊邏輯規(guī)則Table 1 Fuzzy logic rules

圖1 模糊類的劃分Fig．1 Division of fuzzy class

圖2 網(wǎng)絡(luò)狀態(tài)模式Fig．2 Model of network status

2 描述網(wǎng)絡(luò)狀態(tài)變化的多維向量

在DTN中，鏈路常常處于斷開狀態(tài)，并且鏈路狀態(tài)經(jīng)常變化．單一的網(wǎng)絡(luò)狀態(tài)參數(shù)(如鏈路通斷、延遲大小、隊列長短等)不能精確描述DTN的狀態(tài)．為全面描述DTN的拓?fù)?，為路由決策提供精確的量度，應(yīng)該使用新的網(wǎng)絡(luò)描述方法．在機會網(wǎng)絡(luò)思想［6］的基礎(chǔ)上，文中將DTN看成一個全連通網(wǎng)絡(luò)，利用一個能反映節(jié)點及鏈路整體特性的多維向量來描述各節(jié)點間的連通特性，并構(gòu)建一個虛擬拓?fù)洌撏負(fù)淠苡行Х从掣麈溌纷兓械恼w統(tǒng)計特性和應(yīng)對在動態(tài)網(wǎng)絡(luò)中路由決策的需求．文中假設(shè)各節(jié)點具有電量感知能力并能提供相應(yīng)參數(shù)采集．

2．1 各分量的設(shè)計

存儲分量為RB=Brem/Btotal，其中Brem為剩余存儲空間，Btotal為總存儲空間．將能夠反映全網(wǎng)分組生存性的節(jié)點存儲空間作為描述網(wǎng)絡(luò)拓?fù)涞姆至恐?，可有效解決繁忙的優(yōu)秀節(jié)點因存儲空間溢出而出現(xiàn)網(wǎng)絡(luò)分組生存性下降的問題．

電量分量為RP=Prem/Ptotal，其中Prem為剩余電量，Ptotal為總電量．為避免網(wǎng)絡(luò)中那些具有優(yōu)異的委托轉(zhuǎn)發(fā)性能的節(jié)點因過度繁忙而攜帶著大量待轉(zhuǎn)發(fā)分組“死亡”，電量也是一項有效描述網(wǎng)絡(luò)、保證網(wǎng)絡(luò)整體性能的重要分量．

時延分量為RD=(Dmax－Dreal)/Dmax，其中Dreal為傳輸?shù)膶嶋H時延，Dmax為節(jié)點通信范圍內(nèi)的最大傳輸時延．當(dāng)鏈路處于斷開時，Dreal=Dmax，RD=0．該時延分量是為路由過程提供高效轉(zhuǎn)發(fā)的重要依據(jù)．在其它因素被弱化時，該分量反映的可信鏈路代價，將引導(dǎo)分組沿著代價最小、成功概率最大的方向高效轉(zhuǎn)發(fā)．

距離分量為RL=(Lmax－Lreal)/Lmax，其中 Lreal為節(jié)點間實際距離，Lmax為網(wǎng)絡(luò)中節(jié)點的最大距離．節(jié)點通過自身的全球定位系統(tǒng)(GPS)等傳感器得到的數(shù)據(jù)推導(dǎo)出該分量，對應(yīng)網(wǎng)絡(luò)中預(yù)設(shè)的地理信息，得到其與目的節(jié)點的距離參數(shù)［9］．文中假設(shè)不考慮通信中障礙物的影響，距離越近的節(jié)點通信成功概率越大．因此，在沒有足夠的時延信息情況下，距離分量用于將分組轉(zhuǎn)發(fā)給離目的節(jié)點更近的委托節(jié)點，以實現(xiàn)沿成功概率梯度方向轉(zhuǎn)發(fā)．

2．2 各分量的平均預(yù)測處理

上述各分量的采集均源自網(wǎng)絡(luò)的動態(tài)歷史信息．為得到能應(yīng)對網(wǎng)絡(luò)拓?fù)渥兓奈磥硇畔ⅲ闹刑岢隽艘环N能夠動態(tài)地將有限的歷史信息進(jìn)行平均處理與精確預(yù)測結(jié)果相結(jié)合的措施，以此來平衡預(yù)測的不可靠性和平均處理的不精確性問題．

首先對有限的歷史信息進(jìn)行加窗平均處理，再對歷史信息進(jìn)行卡爾曼預(yù)測處理．為能反映現(xiàn)有數(shù)據(jù)的可預(yù)測性，定義一個結(jié)合系數(shù)

式中:cov(xi(t)，xi(t+k))為分量xi(t)相差k時刻的協(xié)方差，k為采集信息間隔;var(xi(t))為參量xi(t)的方差．最后將歷史平均信息與預(yù)測結(jié)果相結(jié)合，得到

完成以上工作后，多維向量已經(jīng)能夠全面描述DTN的動態(tài)拓?fù)?，該拓?fù)浔碚髁薉TN中決定路由成功的各個因素，并能夠反映網(wǎng)絡(luò)的動態(tài)特性．

3 基于梯度和模糊神經(jīng)網(wǎng)絡(luò)的路由決策

為獲得反映網(wǎng)絡(luò)連通特性的節(jié)點間單跳傳輸成功概率，文中采用5層模糊RBF神經(jīng)網(wǎng)絡(luò)結(jié)合Q學(xué)習(xí)算法［10］對多維向量進(jìn)行綜合處理，獲得各分量的優(yōu)先順序以及在決策過程中所產(chǎn)生的影響．然后，節(jié)點通過迭代得到自身到達(dá)網(wǎng)絡(luò)中其它節(jié)點的多跳傳輸成功概率，并以此為節(jié)點間分組委托轉(zhuǎn)發(fā)的判定門限，引導(dǎo)分組沿梯度方向轉(zhuǎn)發(fā)，實現(xiàn)更加高效的轉(zhuǎn)發(fā)策略．

文中所提算法由網(wǎng)絡(luò)描述和路由決策兩部分組成，如圖3所示．

圖3 RBGFNN功能框圖Fig．3 Functional diagram of RBGFNN

3．1 單跳傳輸成功概率

首先，構(gòu)建5層模糊RBF神經(jīng)網(wǎng)絡(luò)［11］(如圖4所示):

圖4 模糊RBF神經(jīng)網(wǎng)絡(luò)Fig．4 Fuzzy RBF neural network

(1)第1 層為輸入層，第 i(i=1，2，3，4)個節(jié)點代表第i個分量x'i的清晰值．

(2)第2層為隸屬度函數(shù)層，該層的每個節(jié)點對應(yīng)某一分量的某一模糊類．節(jié)點的輸入為某分量的清晰值，輸出為清晰值在相應(yīng)模糊類中的隸屬度．每個模糊類的隸屬度函數(shù)為可微的高斯函數(shù)，即其中 mij和 σij分別為第 i個分量xi的第j個模糊類對應(yīng)的隸屬度函數(shù)的中心和寬度．

(3)第3層為適應(yīng)度計算層，該層的每個節(jié)點對應(yīng)一條邏輯規(guī)則，節(jié)點的輸入為規(guī)則的前件，輸出為各邏輯前件隸屬度確定條件下規(guī)則邏輯輸出的適應(yīng)度，即

(4)第4層為規(guī)則內(nèi)部離散概率競爭層，該層節(jié)點對應(yīng)每條邏輯規(guī)則的后件．節(jié)點根據(jù)規(guī)則所對應(yīng)的輸出模糊類的評價Q值分布，競爭得到規(guī)則局部最優(yōu)概率，如pr=max()，表示第r條規(guī)則所對應(yīng)Q值最大的概率，n為輸出模糊類中各清晰概率點的序號．

將各分量的清晰輸入定義為模糊類(如圖5所示);然后為整個綜合過程設(shè)計邏輯規(guī)則庫［12］(如表2所示)，將輸出的概率值劃分為離散模糊類，并初始化其Q值，如圖6所示．

圖5 各分量的離散模糊類Fig．5 Discrete fuzzy classes of each component

表2 邏輯規(guī)則庫Table 2 Database of logic rule

圖6 輸出的概率值與離散模糊類Fig．6 Output probability values and discrete fuzzy classes

3．2 參數(shù)學(xué)習(xí)

函數(shù)．定義TD誤差為

式中:γ為折扣因子，0≤γ≤1;Rt+1為狀態(tài)與輸出的強化信號函數(shù)，Rt+1=RD(t+1)－RD(t)，即t+1與t時刻的時延分量差．

根據(jù)TD誤差，利用直接梯度下降算法來調(diào)整邏輯后件中離散概率對應(yīng)的Q值

式中，βm與βσ分別為隸屬度函數(shù)的中心與寬度的學(xué)習(xí)率．

3．3 基于多跳傳輸成功概率的轉(zhuǎn)發(fā)策略

每個節(jié)點擁有自身到達(dá)網(wǎng)絡(luò)內(nèi)其它節(jié)點的單跳傳輸成功概率后，就可以通過交換各自的網(wǎng)絡(luò)連通信息來得到以單跳傳輸成功概率描述的全連通網(wǎng)絡(luò)拓?fù)鋱D．

當(dāng)有節(jié)點進(jìn)入一個參考節(jié)點的通信范圍內(nèi)時，參考節(jié)點首先判斷對方是否為待發(fā)分組的目的節(jié)點，如果是則直接發(fā)送該分組，否則比較自身及對方到達(dá)待發(fā)分組的目的節(jié)點的多跳傳輸成功概率．如果自身值大于對方值，則參考點不發(fā)送該分組;如果對方值大于自身值，則參考點委托該節(jié)點轉(zhuǎn)發(fā)該分組．按此轉(zhuǎn)發(fā)策略引導(dǎo)分組轉(zhuǎn)發(fā)到目的節(jié)點．

4 仿真與結(jié)果分析

為評估文中算法的性能，采用網(wǎng)絡(luò)仿真軟件OPNET對文中算法﹑Epidemic算法及典型梯度路由(CAR)算法進(jìn)行仿真，并對其分組遞交率及轉(zhuǎn)發(fā)分組數(shù)進(jìn)行了比較．

首先建立一個邊長為3km的正方形仿真平面，并劃分出9個直徑為100 m的虛擬區(qū)域，每個區(qū)域內(nèi)初始化20個DTN節(jié)點(其中19個節(jié)點以1～2m/s的速度隨機移動，1個節(jié)點固定在區(qū)域的中心)．另外，10個節(jié)點以仿真平面中心為圓心，以等間距的半徑做5～10 m/s的同心圓運動．節(jié)點通信范圍為50m，信息傳輸速率為250 kB/s，分組大小為10～100kB．

在各分量維護(hù)中，信息采集間隔k=1 s;Q學(xué)習(xí)算法的學(xué)習(xí)率β=0．8，折扣率γ=0．9，TD誤差0=0．1;多跳成功概率迭代中，p0i=1．

然后，考察在節(jié)點電量不受限制、存儲空間受限情況下的網(wǎng)絡(luò)性能，仿真結(jié)果如圖7所示．從圖7可以看出，在這種情況下，轉(zhuǎn)發(fā)缺乏目的性的Epidemic算法性能受到嚴(yán)重的影響，遞交率低于CAR和RBGFNN算法，而后兩種梯度路由算法均表現(xiàn)出穩(wěn)定的性能;RBGFNN算法保持了經(jīng)典梯度路由算法的特點，在低轉(zhuǎn)發(fā)分組數(shù)下保證較穩(wěn)定的分組遞交率，性能優(yōu)于CAR算法．

圖7 存儲空間受限時的分組遞交率和節(jié)點轉(zhuǎn)發(fā)分組數(shù)Fig．7 Packet delivery ratio and forwarding packet number of node in limited storage space

接著考察節(jié)點存儲空間固定為60 MB、節(jié)點電量是確定有限值情況下的網(wǎng)絡(luò)性能，仿真結(jié)果如圖8所示．從圖8可以看出，在這種相對復(fù)雜的網(wǎng)絡(luò)條件下，隨著分組生存時間的變化，各算法的分組遞交率都有所升高;由于RBGFNN算法改進(jìn)了CAR算法的網(wǎng)絡(luò)描述和路由決策方式，因而轉(zhuǎn)發(fā)更精確，獲得了接近Epidemic算法的遞交率，還保持著與CAR算法幾乎相同水平的轉(zhuǎn)發(fā)分組數(shù)．這說明RBGFNN算法在繼承傳統(tǒng)梯度路由算法優(yōu)點的情況下，還明顯提高了其分組遞交率．

圖8 復(fù)雜網(wǎng)絡(luò)條件下的分組遞交率和節(jié)點轉(zhuǎn)發(fā)分組數(shù)Fig．8 Packet delivery ratio and forwarding packet number of node in complex network

最后，考察節(jié)點存儲空間固定為10 MB、電量為前一場景確定有限值的50%﹑分組生存時間為2 h且業(yè)務(wù)量較重情況下的網(wǎng)絡(luò)性能，仿真結(jié)果如圖9所示．在這種更為苛刻的網(wǎng)絡(luò)條件下，隨著業(yè)務(wù)量的增加，各算法的分組遞交率急劇下降，分組平均延遲明顯增加，但RBGFNN算法有效避免了分組的盲目轉(zhuǎn)發(fā)，及時更新了在資源受限情況下的路由決策原則，因而提高了分組的生存性，獲得了較其它兩種算法更高的分組遞交率和更低的分組延遲．

綜上所述，文中提出的RBGFNN算法采用了CAR算法的基本框架，因此保持了分組轉(zhuǎn)發(fā)的低代價、高效率特性．同時，RBGFNN算法以預(yù)測與平均相結(jié)合的方式來維護(hù)網(wǎng)絡(luò)拓?fù)涞拿枋龇至?，提高了網(wǎng)絡(luò)模型的精確度;以模糊神經(jīng)網(wǎng)絡(luò)對各分量進(jìn)行動態(tài)智能綜合決策，提高了路由決策的靈活度;因而，RBGFNN算法的網(wǎng)絡(luò)性能優(yōu)于CAR算法．

圖9 苛刻網(wǎng)絡(luò)條件下的分組遞交率和分組平均時延Fig．9 Packet delivery ratio and average delay in bad network

5 結(jié)語

文中提出了基于梯度和模糊神經(jīng)網(wǎng)絡(luò)決策的容遲網(wǎng)絡(luò)路由算法RBGFNN．該算法使用歷史信息的動態(tài)平均與精確預(yù)測相結(jié)合的多維向量來描述網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化;采用智能的模糊神經(jīng)網(wǎng)絡(luò)來實現(xiàn)路由決策的智能化;依據(jù)多跳傳輸成功概率引導(dǎo)分組沿梯度方向轉(zhuǎn)發(fā)以提高分組轉(zhuǎn)發(fā)的效率．該算法能夠適應(yīng)DTN的拓?fù)渥兓哂袕娀瘜W(xué)習(xí)功能，可實現(xiàn)對DTN中分組的高效低代價轉(zhuǎn)發(fā)，獲得了良好的網(wǎng)絡(luò)性能．

［1］ Cerf V，Burleigh V，Hooke A，et al．Delay-tolerant networking architecture［R/OL］．(2007-04-30)［2010-09-10］．http:∥www．rfc-editor．org/rfc/rfc4838．txt．

［2］ Jones Evan P C，Li Lily，Schmidtke Jakub K，et al．Practical routing in delay-tolerant networks［J］．IEEE Transactions on Mobile Computing，2007，6(8):943-959．

［3］ Lu Xiaofeng，Hui Pan．An energy-efficient n-epidemic routing protocol for delay tolerant networks［C］∥Proceedings of the 5th IEEE International Conference on Networking，Architecture，and Storage．Macau:IEEE，2010:341-347．

［4］ Yuan Q，Cardei I，Wu J．An effiicient prediction-based routing in disruption-tolerant networks［J］．IEEE Transactions on Parallel and Distributed Systems，2012，23(1):19-31．

［5］ 段鵬瑞，馬華東，羅紅．基于梯度的 DTN路由算法［J］．北京郵電大學(xué)學(xué)報，2011，34(2):63-66．Duan Peng-rui，Ma Hua-dong，Luo Hong．A gradient based routing algorithm for delay tolerant networks［J］．Journal of Beijing University of Posts and Telecommunications，2011，34(2):63-66．

［6］ Huang T K，Lee C K，Chen L J．PRoPHET+:an adaptive PRoPHET-based routing protocol for opportunistic network［C］∥Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications．Perth:IEEE，2010:112-119．

［7］ Musolesi M，Hailes S，Mascolo C．Adaptive routing for intermittently connected mobile ad hoc networks［C］∥Proceedings of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks．Taormina:IEEE，2005:183-189．

［8］ Poor D．Gradient routing in ad hoc networks［R/OL］．(2000-12-31)［2011-02-28］．http:∥www．media．mit．edu/pia/Research/ESP/texts/poorieeepaper．pdf．

［9］ Yasmeen F，Urushidani S，Yamada S．A probabilistic position-based routing scheme for delay-tolerant networks［C］∥Proceedings of the 12th International Conference on Computers and Information Technology．Dhaka:IEEE，2009:88-93．

［10］ 張吉禮．模糊－神經(jīng)網(wǎng)絡(luò)控制原理與工程應(yīng)用［M］．哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2004:24-59．

［11］ Fan Yuan-yuan，Sang Ying-jun．The research of nonlinear control based on fuzzy neural network［C］∥Proceedings of International Conference on Electrical and Control Engineering．Wuhan:IEEE，2010:2417-2420．

［12］ Zuo J，Ng S X，Hanzo L．Fuzzy logic aided dynamic source routing in cross-layer operation assisted ad hoc networks［C］∥Proceedings of IEEE the 72nd Vehicular Technology Conference Fall．Ottawa:IEEE，2010:1-5．