基于多目標決策的LEO衛星網絡多業務路由算法

楊力，孫晶，潘成勝，鄒啟杰

（1. 大連大學信息工程學院，遼寧 大連 116622；2. 通信與網絡重點實驗室，遼寧 大連 116622）

基于多目標決策的LEO衛星網絡多業務路由算法

楊力1,2，孫晶1,2，潘成勝1，鄒啟杰1,2

（1. 大連大學信息工程學院，遼寧 大連 116622；2. 通信與網絡重點實驗室，遼寧 大連 116622）

針對低軌（LEO, low earth orbit）衛星網絡中，鏈路資源利用不均衡以及差異化業務的服務質量(QoS, quality of service)要求難以滿足，容易導致網絡整體運行效率降低的問題，提出了一種基于多目標決策的路由算法。將LEO衛星網絡傳輸的業務定義為時延敏感、帶寬敏感和可靠性敏感3類，采用本征向量法計算業務權值，并利用一致性比率判定所得權值可被接受，進一步，基于多目標決策理論，結合衛星網絡節點與鏈路的實際狀態與業務的具體要求，計算滿足業務QoS需求的路徑，從而實現LEO衛星網絡的多目標動態優化路由。建立基于銥星網絡系統的仿真實驗平臺，模擬網絡時延、剩余帶寬和誤分組率等不確定特征，為隨機產生的3類業務進行路由規劃，仿真結果表明，算法在滿足QoS約束的同時，能有效地均衡衛星鏈路的業務負載，而且在吞吐量等方面的性能均有較明顯提升。

LEO衛星網絡；QoS路由算法；多目標決策

1 引言

隨著衛星網絡技術的不斷發展，低軌衛星系統已能較好地實現全球移動通信。具有星間鏈路的 LEO衛星網絡能實現全球覆蓋，并且與地球同步軌道(GEO, geosynchronous earth orbit)衛星網絡相比，它能夠有效降低傳輸時延，減少衛星對地面節點的依賴，并能夠更好地支持地面移動終端。但 LEO衛星網絡不同于一般的地面網絡，它具有高誤碼率、長時延等空間通信的特點[1,2]，與此同時，衛星網絡業務類型不同，其對端到端傳輸時延、傳輸帶寬等服務的需求也有所不同，因此，衛星網絡中不僅要滿足不同業務傳輸的QoS參數要求，而且還需盡可能地提高網絡傳輸效率，充分利用網絡資源。而針對 QoS所提出的路由，無論是按需路由還是流量分配路由，大多都是考慮某一種或2種鏈路屬性來決定，從而忽略其他約束條件，這樣容易導致網絡的局部負載過大。因此，路由算法需要在兼顧多約束條件的情況下,盡量平衡地利用網絡資源[3～5]。

2 相關工作

根據衛星網絡動態拓撲可預知性和周期性的特點，路由算法可以采用一些拓撲控制機制來屏蔽其拓撲的變化，本文是采用基于離散化的虛擬拓撲將系統周期劃分時間片，再對靜態的序列計算路由。

目前，有關 LEO衛星網絡的路由算法中考慮鏈路狀態特征的算法有以下幾種。文獻[6]提出一種應用于節點的精確負載均衡(ELB, explicit load balancing)策略，它根據下一跳鏈路的時延，當節點出現鏈路數據擁塞時，發送信號給鄰居節點，鄰節點選擇次優路徑，從而減少網絡擁塞。文獻[7]提出了一種受限最短路徑優先(CSPF, constraints shortest path first)算法，這是一種改進的最短路徑優先算法，它為了避免網絡或節點擁塞，將鏈路帶寬的反比定義鏈路權重，根據業務的特定要求，在鏈路狀態數據庫的基礎上，得到最終最短路徑。多路徑 QoS路由(MPQR, multi-path QoS routing)算法[8]是當衛星收到傳輸請求時，計算同時滿足時延和帶寬限制的最優路徑。

此外，考慮QoS業務分類的算法有以下幾種。根據業務分類，文獻[9]提出一種多服務按需路由(MOR, multiservice on-demand routing)協議，它單獨對各類服務流量進行路由。文獻[3]提出一種多業務類QoS路由 (MQoSR, multi-class QoS routing)算法，該算法根據時延和帶寬將業務分為2類，利用相對空閑鏈路來減少鏈路擁塞。由于這些算法有的只考慮鏈路狀態信息，有的只考慮到業務分類，而沒有將這兩者結合起來，沒有針對當前業務和實時的鏈路狀態為業務選擇合適的路徑，這樣很難保證衛星網絡資源整體利用率。

針對上述問題，本文提出一種基于多目標決策的 LEO衛星網絡多業務路由算法。該算法評價了各鏈路的通信屬性：時延、剩余帶寬、誤分組率，計算了不同業務的通信屬性權重；利用多目標優化決策模型，選擇適合業務特征的通信節點作為路由目標對象；最后，本文對該路由算法進行了性能的仿真實驗。

3 相關概念

3.1 QoS介紹

QoS的定義最早是由國際電信聯盟（ITU,International Telecommunication Union）提出的，即服務性能的綜合體現，它所反映的是網絡對用戶所能提供的端到端服務的各種參數描述[10]。由此可知，為業務提供可靠的端到端服務相關的質量保證是 QoS的目標，而這意味著不同業務具有不同的性能需求，即QoS指標。

常用的網絡通信鏈路和路徑的基本 QoS指標有帶寬、時延抖動、分組丟失率等，它們度量函數的特征可以分為：凹性參數、可加性參數和可乘性參數。為便于描述，用w( e)表示鏈路的某個QoS指標值，w( p)表示路徑的相應某個QoS指標值，則QoS的相關度量參數分類和計算規則如表1所示。

表1QoS參數分類和計算規則

3.2 LEO衛星網絡模型

LEO衛星網絡的高速運動導致拓撲不斷變化，相比地面網絡，其路由機制將面臨如下限制：1) 隨著業務增多，多種業務的數據分組難免經過相同的衛星節點，從而對網絡時延和吞吐量等性能產生影響；2) 星上處理和存儲資源十分受限，充分利用資源勢在必行。同時，LEO衛星網絡也有可預知性、周期性、恒定性等。基于上述特點設計路由算法時，建立 LEO衛星網絡模型既要描述通信節點之間的關系，又要能夠計算各節點的流量。

定義 1用G( V, E)來表示衛星網絡拓撲基本模型。其中，V=M×N表示在星座中共有分布于M條衛星軌道，每條軌道有N顆衛星，E代表衛星之間的星間鏈路（ISL），用Ek表示節點i到j的邊集，其中，i, j∈V。

定義 2用ws,d表示網絡中所有可能的源、目的（SD）節點對，則代表一條路徑序列，是SD節點之間通過K條鏈路連接。

為了表示單個鏈路上的流量，令鏈路包含函數為

其中，若路徑經過鏈路Ek則取1，反之取0。用C表示每個節點向其他節點發送的數據分組數量，則某個路徑上的流量計算式為

3.3 多目標決策問題

多目標決策問題是指在一定數量的備選方案上進行偏好決策，如選擇、排序、評價等，并且其決策過程考慮多個具有矛盾性且衡量標準不統一的目標的評價。此類問題由可行方案、目標集、偏好信息、權重以及決策單元組成。

由yij構成決策矩陣，選擇適合的多目標決策方案，獲得當前最優解x′，滿足偏好序

可見，衛星網絡多業務路由問題就是一個多目標決策問題，它適合采用多目標決策理論優化路由過程。

4 算法描述

本文算法的基本思想是：針對衛星網絡拓撲結構動態特性，考慮不同業務的 QoS要求，根據鏈路的時延、剩余帶寬和誤分組率定義計算不同的權值系數，并建立多目標優化模型，對約束條件和目標函數進行確定，通過求解與理想鏈路最接近的鏈路得到最優路徑。

4.1 問題定義

根據數據語音視頻等多樣化的業務的 QoS要求，本文把業務劃分成3種：A類是實時業務，即時延敏感業務，如對時間要求高的指令語音等；B類是可允許一定時延，即帶寬敏感業務，例如對地觀測業務；C類是可靠性敏感業務，主要體現在對誤分組率要求較為苛刻的業務上[11]。在此基礎上對業務的優先級進一步規定，本文暫且定義 A類業務高于B類業務，B類業務高于C類業務。

因此鏈路的總時延

剩余帶寬

誤分組率

定義 3多業務路由的多目標決策問題 P，是指在可行鏈路域中，根據當前鏈路狀態以及業務QoS要求，如何獲得最優鏈路v′。即

圖1網絡拓撲及其抽象

4.2 基于業務特征的權值計算

解決多目標決策問題各目標之間矛盾性的關鍵在于權值系數的確定，本文算法運用本征向量法。由決策人把n個屬性的重要性成對比較，把第p個屬性對第q個屬性的相對重要性記為αpq，并認為它就是屬性p的權wp和屬性q的權wq之比的近似值，個目標成對比較的結果形成矩陣A。

定義4基于業務特征的權重是指把第1個屬性時延的權w1和第 2個屬性剩余帶寬的權w2之比記為α12，第2個屬性剩余帶寬的權w2和第3個屬性誤分組率的權w3之比記為α23，以此類推，構成決策矩陣。則

其中，Ι是單位矩陣，若矩陣Α中的值估計準確，上式嚴格等于 0，若估計不夠準確，則Α中元素的小的攝動代表本征值的小的攝動，于是有

其中，λmax是矩陣Α的最大本征值。可以根據該式求得本征向量即權向量

為了判定矩陣Α在此方法中的科學性，引入一致性比率[12](CR, consistence rate)的概念，它用一致性指標(CI, consistence index)與隨機指標(RI,random index)的比值來表示，可以用來判定矩陣Α是否被接受。其中，，對于階數為n的矩陣對應的RI值如表2所示。

若 CR＞0.1，說明各元素αpq的估計一致性太差，應重新估計；若CR＜0.1，可認為αpq的估計基本一致，可用式(3)求得w。

表2階數為n的矩陣對應的RI值

4.3 求解

在路由選擇的開始階段，首先根據衛星網絡的拓撲結構進行時間片劃分，針對不同的業務分類計算權值系數，對可行鏈路運用優選法[13]對鏈路集合進行篩選，淘汰一些處于劣勢的鏈路方案，得到篩選后的鏈路集合在路由過程中，對可行鏈路進行針對不同業務的矩陣評估，然后求出目標函數的理想鏈路，在路徑集中找出最接近理想鏈路的路徑從而得到問題的帕累托最優解。

對于 LEO衛星網絡多業務路由決策問題的求解基于以下定義。

定義 5業務需求下的理想鏈路，是指可行鏈路域V′中，鏈路 v*的各項屬性滿足或，其中，，則稱 v*為理想鏈路。

假設這個多目標決策問題有很多條鏈路可選，作為可行鏈路域，在約束條件內，根據不同的業務類型，對于 A類業務，有鏈路，分別都滿足時延、剩余帶寬和誤分組率的要求，則稱為多目標絕對最優鏈路，絕對最優鏈路構成鏈路集合，鏈路集存在一個理想鏈路，滿足

定義 6實際通信鏈路的性能與理想鏈路性能的差異是指2條鏈路屬性向量的加權歐氏距離。

其中，w1, w2,…,wn即為n個目標函數的權值，滿足

本文算法的約束條件是確保某2個節點之間有且只有一條路徑，表示為

本文算法具體流程如下。

Step1衛星 s接收到數據傳輸要求，目的節點為d。

Step2獲取拓撲結構時間片，業務需求時延為a1，帶寬為a2，誤分組率為 a3。

Step3篩選可行鏈路集合V，得V′，根據業務分類建立鏈路評價矩陣Α。

Step4判斷理想鏈路*v是否存在，如果存在求解結束。

Step5如果理想鏈路不存在，求最接近理想鏈路的路徑vi，作為下一個通信鏈路。

為能夠進一步清晰描述負載均衡能力，引入負載分布指數[11]

其中，n為LEO衛星鏈路總數；xi表示經過第i條鏈路的數據分組數量； f∈[0,1]，表示網絡中的流量均衡情況，f值越大表明負載越均衡。

本文算法的時間復雜度分析如下。由于針對每個節點需計算 3個屬性值，時間復雜度O( kn)，k=3；同時還要計算鏈路的加權歐氏距離，即O( n2)；因而時間復雜度為O( n2+kn)，其中，k是需要評價的節點屬性數量，最終算法時間復雜度為O( n2)。

5 仿真結果和性能分析

5.1 仿真設置

為了驗證所提出路由算法，仿真以 Iridium星座建立網絡模型，即用66顆LEO衛星和8個地面站構建網絡拓撲。考慮到衛星空間環境的復雜性，為了保證選擇數據的多樣，在每個軌道面上選擇4顆衛星，并且滿足處于同一軌道的2顆衛星之間間隔一顆衛星，做到均勻分布，記錄這 24顆衛星的帶寬、時延等相關參數，從而提高仿真的可靠性，網絡模型參數如表3所示。本文算法運行于星上，在仿真中所有帶寬請求將在5對源—目的節點對之間隨機產生。地面站隨機產生業務，每個地面站發送數據的速率為1.5 Mbit/s，對于3種業務約束條件具體參數指標如表4所示。由于仿真實驗的隨機性，對源、目的節點之間的數據傳輸進行了10次實驗，以下每個仿真的數據都是10次實驗結果的平均值。

表3LEO衛星網絡參數

表4QoS參數

總的帶寬請求次數從100到1000之間遞增。

在仿真中，定義時延權值為w1，剩余帶寬權值為w2，誤分組率權值為w3，通過比較 A類、B類和C類業務中不同屬性的重要性，根據本征向量法求得的權向量如表5所示。

表5仿真屬性權值設置

根據 3種屬性權值設置計算得：CRA=0.07，CRB=0.03，CRC=0.05，均小于0.1，因此權向量估計可被接受。

5.2 不同QoS業務路由性能對比

當網絡中 A、B、C 3類業務同時存在時，在源節點和目的節點相同的情況下，3類業務的傳輸效率對比如表6所示。

表6業務傳輸效率參數

從表6可看出，同樣的鏈路狀態下，3類業務會根據需求不同選擇不同路由線路，A類業務時延最短，B類業務平均帶寬最大，C類業務誤分組率最低。

5.3 多目標業務路由性能分析

選擇2個現有先進的典型路由算法與本文提出的算法進行比較，一個是 2014年提出的只考慮鏈路狀態特征的ELB算法，一個是2009年提出的只考慮 QoS業務分類的 MOR算法，比較從路由開銷、負載分布指數和吞吐量3個性能方面進行。

圖2所示為當負載狀態不一樣時，不同路由算法產生的路由開銷。

圖2網絡的路由開銷

如圖2所示，這3種路由算法的路由開銷都隨著負載的增加而增大。但是，隨著負載的加重，本文算法的路由開銷比其他2種路由算法低，最多低3%。其原因在于當處于高負載時，其他2種路由產生了數據分組的簇擁和集聚，導致部分擁塞，所以需要消耗更多的數據分組。而本文算法中最優化模型綜合考慮了時延、剩余帶寬和誤分組率3個因素，可以達到均衡網絡負載的目的，并且節省了路由開銷。

圖3所示為隨著負載狀態的增加，不同路由算法的負載分布指數情況。

圖3負載分布指數

如圖 3所示，本文算法的負載分布指數與MOR算法和ELB算法相比更高一些，這是因為本文在考慮當前鏈路特征的同時對業務進行分類，將二者結合起來，能夠有效避免擁塞，仿真結果進一步驗證了本文算法有利于均衡網絡負載。

圖4所示為本文路由算法與MOR和ELB算法在吞吐量上的性能比較。

圖4網絡的吞吐量

就網絡吞吐量性能而言，由圖4可以看出，在帶寬請求次數為100到400之間時，本文算法略優于MOR算法，優于ELB算法。當帶寬請求次數在400到1000之間時，本文算法與MOR和ELB算法相比有較大優勢，并且隨著帶寬請求次數的增加，吞吐量也在持續增加，并且請求次數在800到1000之間，本文策略的吞吐量趨向平穩，相比MOR算法吞吐量增加了 16%。綜上所述，本文策略在吞吐量上都要優于MOR和ELB算法。

5.4 與其他現有算法比對結果分析

下面是本文路由算法與WSP算法[15]、CSPF算法等其他路由算法的性能比較。

圖 5是 4種路由算法的負載分布指數變化情況，隨著負載的加重，本文算法的負載分布指數一直保持較高的狀態，這是因為當負載狀態變化時，本文的最優化模型能夠將更多的鏈路作為路徑選擇，不會將路徑局限在某些節點上，所以它的負載分布指數最優。

圖5負載分布指數

圖6是4種路由算法的網絡吞吐量結果。可以看出，在帶寬請求次數為100到200之間時，4種算法的吞吐量都比較接近，且本文算法略優于其他算法，隨著帶寬請求次數的增加，WSP算法相比其他算法性能較好，但整體相比，本文算法吞吐量始終最大，說明本文提出的算法在吞吐量指標上具有較明顯提升。

圖6網絡的吞吐量

通過仿真可知，與ELB、MOR算法相比，本文算法將鏈路特征狀態和業務QoS分類二者結合起來，在負載增多的情況下，負載分布指數提高了近 10%，路由開銷小，吞吐量增加了 16%，與WSP、CSPF、MQoSR算法相比，負載分布指數和吞吐量都相對較高，使衛星網絡整體性能得到提高。

6 結束語

本文針對 LEO衛星網絡中，鏈路資源利用不均衡、不同業務與其對應的服務質量要求匹配性考慮不足的問題，提出一種基于多目標決策的業務路由算法。該路由算法建立可行鏈路集合的多目標決策模型，利用 QoS需求設置不同鏈路屬性的權重集合，進而通過理想點法求解多目標決策問題，最終獲得適合業務需求的路由節點。

仿真實驗結果表明，本算法較其他典型算法路由開銷更小，并且在高負載情況下，負載分布指數以及吞吐量方面均有明顯的優勢。從而，本算法解決了QoS業務需求與LEO衛星鏈路屬性相結合的業務路由問題。

[1]FATIH A, OMER K, ABBAS J. Exploring the routing strategies in next-generation satellite networks[J]. IEEE Wireless Communications,2007,14(3):79-88.

[2]LI J, YE G Q, ZHANG J, et al. A routing algorithm satisfied ground station distribution constraint for satellite constellation network[C]//Science and Information Conference (SAI). 2015.

[3]WU Z, HU G, JIN F, et al. Agent-based dynamic routing in the packetswitched LEO satellite networks[C]// Wireless Communications amp; Signal Processing (WCSP), 2015 International Conference. IEEE, 2015.

[4]JIANG W J, ZONG P. QoS routing algorithm based on traffic classification in LEO satellite networks[C]//Paris: Eighth International Conference on Wireless and Optical Communication Networks (WOCN).2011.

[5]LU Y, ZHAO Y J, SUN F C ,et al. Routing techniques on satellite networks[J]. Journal of Software, 2014,25(5): 1085-1100.

[6]QUAN L, NGO-QUYNH T, MAGEDANZ T. RPL-based multipath routing protocols for internet of things on wireless sensor networks[C]//Advanced Technologies for Communications (ATC), 2014 International Conference. IEEE, 2014.

[7]JAUHARI A S, KISTIJANTORO A I. INET framework modifications in OMNeT++ simulator for MPLS traffic engineering[C]//Advanced Informatics: Concept, Theory and Application (ICAICTA), 2014 International Conference. IEEE, 2014: 87-92.

[8]RAO Y, WANG R C. Performance of QoS routing using genetic algorithm for Polar-orbit LEO satellite networks[J]. AEU-Int’l Journal of Electronics and Communications, 2011,65(6):530-538.

[9]PAPAPETROU E, KARAPANTAZIS S, PAVLIDOU F N. Multiservice on-demand routing in LEO satellite networks[J]. IEEE Trans. on Wireless Communications,2007,8(1):107-112.

[10]代志勇. 業務分類體系下的 QoS路由研究[D]. 南京: 南京郵電大學, 2013.DAI Z Y. Research on QoS routing in service classification system[D].Nanjing: Nanjing University of Posts and Telecommunications, 2013.

[11]TALEB T, MASHIMO D, JAMALIPOUR A, et al. Explicit load balancing technique for NGEO satellite IP network with on-board processing capabilities[J]. IEEE/ACM Transactions on Networking, 2009,17(l):281-293.

[12]岳超源. 決策理論與方法[M]. 科學出版社, 2003.YUE C Y. Decision making theory and methods[M]. Sciences Press,2003.

[13]郭得科. 基于Kautz圖和Bloom濾波的對等網絡研究[D]. 長沙: 國防科學技術大學, 2008.GUO D K. Research on peer-to-peer networks based on Kautz digraph and bloom filters[D]. Changsha: National University of Defense Technology, 2008.

[14]KINSY M A, CHO M H, SHIM K S, et al. Optimal and heuristic application-aware oblivious routing[J]. IEEE Transactions on Computers, 2013, 62(1): 59-73.

[15]劉暐. 一種新的雙層衛星網絡路由算法性能仿真研究[J]. 計算機仿真, 2014, 31(4): 118-122.LIU W. Research on performance simulation of novel routing algorithm for double - layered satellite networks[J]. Computer Simulation,2014, 31(4): 118-122.

LEO multi-service routing algorithm based on multi-objective decision making

YANG Li1,2, SUN Jing1,2, PAN Cheng-sheng1, ZOU Qi-jie1,2
(1. Information and Engineering College, Dalian University, Dalian 116622, China;2. Communication and Networks Key Laboratory, Dalian 116622, China)

In low earth orbit(LEO) satellite networks, in view of the unbalanced link resource, it's difficult to meet differentiated quality of service(QoS) requirements and easily lead to reduce the efficiency of the whole network. A routing algorithm based on multi-objective decision making was proposed which defined LEO satellite network transmission service as the delay sensitive, sensitive bandwidth and reliability sensitive three categories. It used the eigenvector method to calculate service weights, and used the consistency ratio to determine whether it can be accepted. Based on the multi-objective decision making theory, it combined with the actual state of satellite network nodes and links and the specific requirements of the business, calculating the path that meets the QoS requirements of the service, so as to realize the LEO satellite network multi objective dynamic routing optimization. Established simulation platform based on the iridium network system simulated network delay, the uncertain characteristics like the residual bandwidth and packet error rate, route planning for the randomly generated three classes of business. The simulation results show that, the algorithm not only satisfies the QoS constrain while balancing the traffic load of the satellite link effectively, but also improves the performance on the throughput.

LEO satellite network, QoS routing algorithm, multi-objective decision making

The National Natural Science Foundation of China (No.61301151, No.91338104)

TP393

A

10.11959/j.issn.1000-436x.2016192

2016-01-30；

2016-09-03

國家自然科學基金資助項目（No.61301151, No.91338104）

楊力（1982-），女，黑龍江哈爾濱人，博士，大連大學教授，主要研究方向為空間信息網絡傳輸技術、無線通信網絡協議理論與方法。

孫晶（1991-），女，山西臨汾人，大連大學碩士生，主要研究方向為衛星通信網絡路由算法等。

潘成勝（1962-），男，江蘇宜興人，博士，大連大學教授、博士生導師，主要研究方向為一體化網絡體系與網絡協議研究、一體化指控系統網絡理論與技術。

鄒啟杰（1978-），女，黑龍江佳木斯人，博士，大連大學副教授，主要研究方向為智能規劃、智能決策以及機器學習等。