從立鋼，楊華民，王楊惠，底曉強

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

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

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

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

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

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

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

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

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

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

1.2 路由問題定義

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

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

2.1 多屬性決策要素

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

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

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

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

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

2.2 決策模型

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

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

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

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

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

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

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

2.3 權(quán)重計算

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

對于一個決策矩陣D=(xij)n×m，方案對于屬性j的評價pij定義為：

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

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

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

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

2.4 路由算法

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

表1 鄰節(jié)點屬性表

算法具體流程：

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

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

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

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

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

3 算法分析及仿真

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

表2 鄰節(jié)點屬性表

3.1 路由算法分析

（1）無偏好路由選擇

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

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

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

3.2 性能仿真分析

本文利用DTN仿真軟件ONE，結(jié)合以上場景對算法進行仿真，并將無偏好路由算法、時延偏好路由算法、Epidemic以及PROPHET四種路由算法進行對比，以驗證其性能。

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

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

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

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

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

4 結(jié)論

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