基于多屬性決策的空間DTN網(wǎng)絡(luò)路由算法研究

從立鋼，楊華民，王楊惠，底曉強(qiáng)

（1.長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022；2.長(zhǎng)春理工大學(xué) 化學(xué)與環(huán)境工程學(xué)院，長(zhǎng)春 130022）

空間信息網(wǎng)絡(luò)在移動(dòng)通信、導(dǎo)航定位、遙感遙測(cè)、深空探索、軍事應(yīng)用等領(lǐng)域所發(fā)揮的作用越來(lái)越重要，尤其是低軌衛(wèi)星網(wǎng)絡(luò)，以其時(shí)延短、帶寬高、用戶(hù)終端小、功耗低等優(yōu)點(diǎn)日益被人們重視，低軌衛(wèi)星網(wǎng)絡(luò)已經(jīng)成為當(dāng)前信息網(wǎng)絡(luò)研究領(lǐng)域的熱點(diǎn)之一。

低軌衛(wèi)星網(wǎng)絡(luò)一般由多顆低軌道衛(wèi)星組成，其軌道高度為500～2000km之間，一般運(yùn)行速度為20000km/h，繞地球一周約2小時(shí)［6］，由于低軌衛(wèi)星網(wǎng)絡(luò)衛(wèi)星數(shù)目較多，且在運(yùn)行過(guò)程中需要頻繁切換鏈路和改變拓?fù)浣Y(jié)構(gòu)，因此構(gòu)建可靠、高效的路由機(jī)制就變成了一個(gè)急需解決的問(wèn)題。

延遲容忍網(wǎng)絡(luò)（簡(jiǎn)稱(chēng)DTN）是針對(duì)時(shí)延大、中斷頻繁的特殊網(wǎng)絡(luò)環(huán)境而產(chǎn)生的，因此，其在解決低軌衛(wèi)星網(wǎng)絡(luò)路由問(wèn)題方面具有得天獨(dú)厚的優(yōu)勢(shì)。目前，主流的DTN路由包括以下幾種：傳染路由（Epidemic Routing）［7］、基于概率的路由（Prophet Routing）算法［8］、散發(fā)等待（Spray-and-Wait）路由算法［9］等，以上路由算法應(yīng)用廣泛。但是以上路由算法不能直接應(yīng)用于衛(wèi)星網(wǎng)絡(luò)之中，原因在于其沒(méi)有考慮衛(wèi)星網(wǎng)絡(luò)的自身特點(diǎn)，盲目應(yīng)用將會(huì)影響衛(wèi)星網(wǎng)絡(luò)性能的發(fā)揮。

本文以低軌衛(wèi)星網(wǎng)絡(luò)規(guī)律為出發(fā)點(diǎn)，針對(duì)現(xiàn)有算法存在的適應(yīng)性問(wèn)題，提出了一種基于多屬性決策理論的低軌衛(wèi)星DTN網(wǎng)絡(luò)路由算法，該算法既能解決衛(wèi)星網(wǎng)絡(luò)的路由問(wèn)題，同時(shí)對(duì)于不同類(lèi)型的網(wǎng)絡(luò)任務(wù)也具有良好的適應(yīng)性。

1 網(wǎng)絡(luò)系統(tǒng)模型

本文所研究的低軌衛(wèi)星網(wǎng)絡(luò)采用傾斜軌道，與極地軌道遞歸衛(wèi)星星座相比，具有時(shí)延小、地面覆蓋均勻等優(yōu)勢(shì)。

1.1 LEO網(wǎng)絡(luò)拓?fù)淠Ｐ投x

與傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)不同，低軌衛(wèi)星網(wǎng)絡(luò)中的節(jié)點(diǎn)是運(yùn)動(dòng)的，其拓?fù)浣Y(jié)構(gòu)是時(shí)刻變化的，但是，衛(wèi)星是嚴(yán)格按照軌道運(yùn)行的，因此，其變化方式具有明顯的周期性和可預(yù)測(cè)性?；谶@一特點(diǎn)，一般進(jìn)行衛(wèi)星網(wǎng)絡(luò)路由研究的時(shí)候研究者會(huì)利用相關(guān)策略屏蔽網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)性，利用抽象的靜態(tài)模型開(kāi)展研究。目前，相關(guān)策略主要有虛擬拓?fù)洳呗?、虛擬節(jié)點(diǎn)策略和覆蓋域劃分法等，本文采用虛擬拓?fù)洳呗浴?/p>

虛擬拓?fù)洳呗允菍⑿l(wèi)星網(wǎng)絡(luò)節(jié)點(diǎn)的動(dòng)態(tài)拓?fù)潢P(guān)系離散化，將一個(gè)完整的衛(wèi)星網(wǎng)絡(luò)運(yùn)行周期分割為若干時(shí)間片［t0，t1］、［t1，t2］、［t2，t3］、［t3，t4］，……，［tn，tn-1］，衛(wèi)星網(wǎng)絡(luò)拓?fù)湓跁r(shí)間片內(nèi)是相對(duì)固定的，僅在t1，t2，t3，……，tn等時(shí)間節(jié)點(diǎn)處發(fā)生變化。

1.2 路由問(wèn)題定義

DTN網(wǎng)絡(luò)路由的基本模式為“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”，因此，路由問(wèn)題可以轉(zhuǎn)化為尋找合適“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”節(jié)點(diǎn)的問(wèn)題。在低軌衛(wèi)星網(wǎng)絡(luò)中，當(dāng)某一節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)并需要發(fā)送給目標(biāo)節(jié)點(diǎn)時(shí)，往往會(huì)有多條路徑可供選擇，那么選擇路徑的第一步就是在多個(gè)鄰居節(jié)點(diǎn)間選擇一個(gè)合適的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，衡量低軌衛(wèi)星網(wǎng)絡(luò)通信性能的參數(shù)有很多，不同業(yè)務(wù)對(duì)于網(wǎng)絡(luò)性能也有不同的要求，因此可以將組合參數(shù)作為尋找適合數(shù)據(jù)轉(zhuǎn)發(fā)點(diǎn)的重要依據(jù)。本文所提出的路由算法正是根據(jù)這一想法，利用網(wǎng)絡(luò)多屬性聯(lián)合決策尋找適合數(shù)據(jù)轉(zhuǎn)發(fā)點(diǎn)，這樣既可以完成網(wǎng)絡(luò)路由任務(wù)，同時(shí)還能在一定程度上提高網(wǎng)絡(luò)性能。

2 基于多屬性決策的LEO網(wǎng)絡(luò)路由模型

2.1 多屬性決策要素

本算法所選擇的屬性包括鏈路帶寬（B）、鏈路建立時(shí)延（D）、節(jié)點(diǎn)剩余存儲(chǔ)空間（S）和節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)率（V）四個(gè)。

屬性一：鏈路帶寬（B）。星間鏈路帶寬是衡量鏈路性能的重要屬性，低軌衛(wèi)星網(wǎng)絡(luò)要進(jìn)行頻繁的數(shù)據(jù)傳輸，鏈路帶寬的大小直接影響到網(wǎng)絡(luò)性能。

屬性二：鏈路建立時(shí)延（D）。鏈路建立時(shí)延是指衛(wèi)星間構(gòu)建通信鏈路所耗費(fèi)的時(shí)間，期間要經(jīng)歷天線跟蹤瞄準(zhǔn)、同步捕獲、協(xié)議握手三個(gè)過(guò)程。

屬性三：剩余存儲(chǔ)空間（S）。本文所研究的低軌衛(wèi)星網(wǎng)絡(luò)以DTN為基礎(chǔ)，DTN路由的基本模式是“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”，轉(zhuǎn)發(fā)節(jié)點(diǎn)的剩余存儲(chǔ)空間對(duì)于路由過(guò)程的順利實(shí)現(xiàn)十分重要，因此將剩余存儲(chǔ)空間作為屬性之一。

屬性四：節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)率（V）。數(shù)據(jù)節(jié)點(diǎn)轉(zhuǎn)發(fā)率是指衛(wèi)星節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包的數(shù)量與其所接收數(shù)據(jù)包和其自身產(chǎn)生數(shù)據(jù)包數(shù)量之和的比值，該屬性是衡量節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)情況的重要參數(shù)，通過(guò)該屬性的引入，可以有效避免在路由過(guò)程中“數(shù)據(jù)黑洞”和“自私”節(jié)點(diǎn)的產(chǎn)生。

2.2 決策模型

假設(shè)在t時(shí)刻，衛(wèi)星節(jié)點(diǎn)s有數(shù)據(jù)轉(zhuǎn)發(fā)需求，此時(shí)有n個(gè)相鄰衛(wèi)星節(jié)點(diǎn)供其選擇，作為數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)，即此時(shí)為數(shù)據(jù)源節(jié)點(diǎn)s提供了n個(gè)數(shù)據(jù)轉(zhuǎn)發(fā)備選方案。每一個(gè)方案有m個(gè)屬性構(gòu)成的屬性集合表示，如A={A1,A2,…，Am}。本文所選擇的屬性包括鏈路帶寬、鏈路建立時(shí)延、存儲(chǔ)空間、網(wǎng)絡(luò)誤碼率和節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)率，則屬性集可以寫(xiě)成A={B,D,S,V}，根據(jù)多屬性決策理論，屬性值越大對(duì)于方案選中越有利的屬性被稱(chēng)為效益屬性，相反，屬性值越小對(duì)方案選中越有利的屬性被稱(chēng)為成本屬性，這五種屬性中鏈路帶寬、存儲(chǔ)空間、節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)率屬于效益屬性，鏈路建立時(shí)延和網(wǎng)絡(luò)誤碼率是成本屬性。

每個(gè)備選方案包含四個(gè)重要屬性，則n個(gè)備選方案可以形成一個(gè)組成一個(gè)n×4的多屬性決策矩陣，該決策矩陣形式如下：

各屬性含義不同、量綱不同，屬性間存在不可公度性，這種差異會(huì)在一定程度上最后的決策結(jié)果，因此為了提高決策的準(zhǔn)確性，可以通過(guò)屬性標(biāo)準(zhǔn)化的方式來(lái)消除數(shù)據(jù)間的差異。

所研究的屬性中同時(shí)包括效益屬性和成本屬性，因此多屬性決策矩陣可以通過(guò)公式（3）進(jìn)行規(guī)范化，即：

其中，xij為原決策矩陣中的元素，為第j列的最小值，rij為規(guī)范化之后的屬性值，規(guī)范化后的多屬性決策矩陣可以表示為R=(rij)n×m。通過(guò)公式（2）可以多決策矩陣進(jìn)行規(guī)范化，解決屬性間的不可公度問(wèn)題，方便系統(tǒng)決策。

系統(tǒng)方案評(píng)價(jià)值的產(chǎn)生不僅需要規(guī)范化矩陣，同時(shí)還需要屬性權(quán)重向量的參與，產(chǎn)生方案評(píng)價(jià)值的公式為：

其中，wj為第j個(gè)屬性的權(quán)重值，權(quán)重值需要滿(mǎn)足條件。當(dāng)屬性權(quán)重確定后，可以通過(guò)公式（3）獲取路由方案綜合評(píng)定值，從而完成低軌衛(wèi)星網(wǎng)絡(luò)路由節(jié)點(diǎn)的選擇。

2.3 權(quán)重計(jì)算

屬性權(quán)值的選擇直接影響到?jīng)Q策的結(jié)果，權(quán)值的選擇應(yīng)與屬性在整個(gè)決策過(guò)程中所起作用成正比，權(quán)重值生成方法的選擇會(huì)直接影響到最終的評(píng)價(jià)結(jié)果。Echenrode對(duì)于權(quán)值決策方案進(jìn)行了分析，并總結(jié)了權(quán)重計(jì)算的經(jīng)典方法方法［4］，本文采用Shannon所提出的信息熵方法［5］確定決策矩陣權(quán)值過(guò)。

對(duì)于一個(gè)決策矩陣D=(xij)n×m，方案對(duì)于屬性j的評(píng)價(jià)pij定義為：

將公式（4）的pij帶入信息熵計(jì)算公式，則方案關(guān)于屬性j的熵值Ej為：

其中，k是一個(gè)常數(shù)為，其值為，該值的引入可以確保熵值的范圍為［0，1］。信息偏差度dj定義為：

如果在決策過(guò)程中沒(méi)有特殊偏好，即在路由過(guò)程中沒(méi)有特殊業(yè)務(wù)需求，則可以認(rèn)為個(gè)屬性同等重要，因此，此時(shí)可以使用類(lèi)似平均權(quán)重的方法生成決策權(quán)重，其公式為：

如果在決策過(guò)程中對(duì)某些屬性有特殊偏好，則可以引入偏好值λ對(duì)權(quán)重進(jìn)行調(diào)整，獲得符合實(shí)際業(yè)務(wù)需求的權(quán)重，相關(guān)計(jì)算法方法為：

2.4 路由算法

本文所描述的低軌衛(wèi)星網(wǎng)絡(luò)采用虛擬拓?fù)洳呗?，即認(rèn)為在每一個(gè)時(shí)間片內(nèi)網(wǎng)絡(luò)結(jié)構(gòu)是相對(duì)固定的，在每一個(gè)時(shí)間片開(kāi)始時(shí)，衛(wèi)星節(jié)點(diǎn)將向其臨界點(diǎn)廣播當(dāng)前衛(wèi)星屬性信息，獲得廣播信息的鄰居節(jié)點(diǎn)將根據(jù)這些信息構(gòu)建自己的鄰節(jié)點(diǎn)屬性信息表，該表形式如表1所示。當(dāng)節(jié)點(diǎn)有數(shù)據(jù)需要發(fā)送時(shí)，就會(huì)根據(jù)當(dāng)前的鄰節(jié)點(diǎn)屬性以及任務(wù)需求調(diào)整屬性偏好，進(jìn)行路由選擇。

表1 鄰節(jié)點(diǎn)屬性表

算法具體流程：

（1）當(dāng)節(jié)點(diǎn)有數(shù)據(jù)傳輸任務(wù)時(shí)，判斷相鄰節(jié)點(diǎn)中是否有目標(biāo)節(jié)點(diǎn)，如果有，直接交付數(shù)據(jù)，路由結(jié)束，否則開(kāi)始步驟（2）；

（2）根據(jù)屬性信息表計(jì)算相鄰節(jié)點(diǎn)屬性權(quán)值，根據(jù)任務(wù)類(lèi)型，調(diào)整屬性偏好；

（3）計(jì)算方案評(píng)價(jià)值，選取最優(yōu)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)；

（4）目標(biāo)節(jié)點(diǎn)收到數(shù)據(jù)后重復(fù)步驟（1）。

需要注意的是，本算法中步驟（2）（3）中參與權(quán)值計(jì)算的節(jié)點(diǎn)不包括之前已經(jīng)完成方案價(jià)值計(jì)算的節(jié)點(diǎn)，這樣的設(shè)計(jì)可以有效避免“路由環(huán)路”的出現(xiàn)。

3 算法分析及仿真

假設(shè)一個(gè)的低軌衛(wèi)星網(wǎng)絡(luò)通信場(chǎng)景，場(chǎng)景中包括衛(wèi)星節(jié)點(diǎn)vs、v1、v2、v3、v4、v5、v6、vd，衛(wèi)星網(wǎng)絡(luò)拓?fù)潢P(guān)系及相關(guān)屬性如表2所示，其中為vs數(shù)據(jù)源節(jié)點(diǎn)，其所要發(fā)送的數(shù)據(jù)量為100M，vd為目的節(jié)點(diǎn)，假設(shè)在［t1，t2］時(shí)間段內(nèi)路由過(guò)程可以完成。

表2 鄰節(jié)點(diǎn)屬性表

3.1 路由算法分析

（1）無(wú)偏好路由選擇

當(dāng)路由選擇無(wú)業(yè)務(wù)偏好時(shí)，假設(shè)節(jié)點(diǎn)的剩余空間均滿(mǎn)足數(shù)據(jù)要求，將上文所述的場(chǎng)景使用多屬性決策路由算法進(jìn)行路由選擇。經(jīng)過(guò)計(jì)算，此時(shí)選擇的路徑為vs--＞v2--＞v5--＞vd。

（2）偏好網(wǎng)絡(luò)時(shí)延

如果當(dāng)前的業(yè)務(wù)對(duì)于特定屬性要求較高，可以通過(guò)引入偏好值來(lái)引入屬性偏好值來(lái)改變路由策略，從而提高網(wǎng)絡(luò)在該方面的性能，更好的支持當(dāng)前業(yè)務(wù)。鏈路網(wǎng)絡(luò)時(shí)延較高，可以在路由選擇過(guò)程中引入對(duì)時(shí)延有利的偏好值λ對(duì)權(quán)重進(jìn)行調(diào)整，在進(jìn)行路由選擇過(guò)程中會(huì)對(duì)路徑進(jìn)行重新調(diào)整，這里設(shè)置偏好值λ=（0.1，0.6，0.1，0.1，0.1），此時(shí)選擇的路徑為vs--＞v2--＞v6--＞vd。，與無(wú)偏好情況相比，路徑發(fā)生了改變，這里用鏈路建立時(shí)間較短的節(jié)點(diǎn)v6替換了節(jié)點(diǎn)v5，在兼顧網(wǎng)絡(luò)其他性能的同時(shí)最大程度的降低了網(wǎng)絡(luò)整體時(shí)延。

3.2 性能仿真分析

本文利用DTN仿真軟件ONE，結(jié)合以上場(chǎng)景對(duì)算法進(jìn)行仿真，并將無(wú)偏好路由算法、時(shí)延偏好路由算法、Epidemic以及PROPHET四種路由算法進(jìn)行對(duì)比，以驗(yàn)證其性能。

如圖1所示，在四種路由算法中，Epidemic路由算法的傳輸成功率最低，無(wú)偏好的路由算法的成功率明顯高于Epidemic和PROPHET路由算法，而轉(zhuǎn)發(fā)率偏好路由算法的傳輸成功率又高于無(wú)偏好多屬性路由算法。

圖1 網(wǎng)絡(luò)傳輸成功率

如圖2所示，說(shuō)明了三種路由算法在假定場(chǎng)景下的平均時(shí)延情況，可見(jiàn)對(duì)于同一任務(wù)，多屬性路由算法的平均時(shí)延均低于Epidemic和PROPHET路由算法，而時(shí)延偏好多屬性路由算法的平均網(wǎng)絡(luò)實(shí)驗(yàn)又略低于無(wú)偏好多屬性路由算法。

圖2 網(wǎng)絡(luò)平均時(shí)延

通過(guò)以上仿真結(jié)果分析，可見(jiàn)多屬性決策路由算法的性能要明顯優(yōu)于常見(jiàn)的Epidemic路由算法，而且當(dāng)業(yè)務(wù)對(duì)于某一屬性有特殊需求時(shí)，使用偏好多屬性決策路由算法又會(huì)在相關(guān)屬性上有進(jìn)一步提高。

4 結(jié)論

本文提出了一種基于多屬性決策理論的空間DTN網(wǎng)絡(luò)路由算法，通過(guò)選擇鏈路帶寬、鏈路建立時(shí)延、節(jié)點(diǎn)剩余存儲(chǔ)空間、誤碼率、節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)率五種重要屬性作為決策基礎(chǔ)，引入多屬性決策理論構(gòu)建路由模型，該算法可以針對(duì)不同業(yè)務(wù)需求對(duì)路由算法進(jìn)行動(dòng)態(tài)調(diào)整。仿真結(jié)果表明：該算法與Epidemic、PROPHET兩種路由算法相比較，在性能上確實(shí)有一定提高，而且能夠按照業(yè)務(wù)偏好提高相關(guān)性能，為空間網(wǎng)絡(luò)不同業(yè)務(wù)需求提供靈活可靠的網(wǎng)絡(luò)路由服務(wù)。