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

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

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

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

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

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

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

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

1.1 LEO網(wǎng)絡拓撲模型定義

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

虛擬拓撲策略是將衛(wèi)星網(wǎng)絡節(jié)點的動態(tài)拓撲關系離散化，將一個完整的衛(wèi)星網(wǎng)絡運行周期分割為若干時間片［t0，t1］、［t1，t2］、［t2，t3］、［t3，t4］，……，［tn，tn-1］，衛(wèi)星網(wǎng)絡拓撲在時間片內是相對固定的，僅在t1，t2，t3，……，tn等時間節(jié)點處發(fā)生變化。

1.2 路由問題定義

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

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

2.1 多屬性決策要素

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

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

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

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

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

2.2 決策模型

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

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

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

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

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

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

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

2.3 權重計算

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

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

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

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

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

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

2.4 路由算法

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

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

算法具體流程：

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

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

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

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

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

3 算法分析及仿真

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

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

3.1 路由算法分析

（1）無偏好路由選擇

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

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

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

3.2 性能仿真分析

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

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

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

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

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

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

4 結論

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