基于多屬性決策的空間DTN網絡路由算法研究

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

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

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

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

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

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

1 網絡系統模型

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

1.1 LEO網絡拓撲模型定義

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

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

1.2 路由問題定義

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

2 基于多屬性決策的LEO網絡路由模型

2.1 多屬性決策要素

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

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

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

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

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

2.2 決策模型

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

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

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

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

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

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

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

2.3 權重計算

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

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

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

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

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

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

2.4 路由算法

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

表1 鄰節點屬性表

算法具體流程：

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

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

（3）計算方案評價值，選取最優節點進行數據轉發；

（4）目標節點收到數據后重復步驟（1）。

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

3 算法分析及仿真

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

表2 鄰節點屬性表

3.1 路由算法分析

（1）無偏好路由選擇

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

（2）偏好網絡時延

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

3.2 性能仿真分析

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

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

圖1 網絡傳輸成功率

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

圖2 網絡平均時延

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

4 結論

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