劉冠男++傅寧

摘 要：本文首先分析了多層衛(wèi)星路由研究的現(xiàn)狀，指出當前環(huán)境下多層衛(wèi)星路由算法研究的重點在路由的層次化和分層處理。針對現(xiàn)有路由算法在QoS（Quality of Service）性能上的局限，在此基礎上提出了基于流量工程的最小鏈路代價多層衛(wèi)星路由算法TE-MSP（Traffic Engineering-Minimizing Sum of Path-cost），建立了流量模型和鏈路代價公式，并通過仿真驗證了該算法能在繁忙時起到12%的分流效果、并減少23%的鏈路花費。

關鍵詞：多層衛(wèi)星；路由；流量模型；代價函數(shù)

中圖分類號：TN915.09 文獻標識碼：A DOI： 10.3969/j.issn.1003-6970.2015.10.020

引言

傳統(tǒng)衛(wèi)星和地面網(wǎng)關以微波作為信息傳輸媒介，受到頻率限制，僅能工作在每秒百兆比特量級的傳輸速率上，勉強能實現(xiàn)星上業(yè)務的存儲轉(zhuǎn)發(fā)功能。

近幾十年來，衛(wèi)星激光技術和節(jié)點處理能力方面的提高，使衛(wèi)星網(wǎng)絡的通信能力提升至一個新的水平。衛(wèi)星節(jié)點已從早期的信號接收處理的中繼站，轉(zhuǎn)變?yōu)榫哂行巧咸幚砟芰εc存儲能力、能夠進行自主計算，使衛(wèi)星節(jié)點間組網(wǎng)的成為可能。

目前國內(nèi)外已投入使用的衛(wèi)星網(wǎng)絡多是單層衛(wèi)星，同時借助地面站來完成中轉(zhuǎn)和監(jiān)控任務，不僅不能充分利用衛(wèi)星網(wǎng)絡的資源和結(jié)構(gòu)，同時地面站會受到地理環(huán)境因素的限制而難以完美建立。因此，具有星間鏈路，由多軌道衛(wèi)星組成的網(wǎng)絡成為衛(wèi)星通信發(fā)展的趨勢。同時針對多層衛(wèi)星路由的研究仍是當前的熱點。在未來空天地一體化信息網(wǎng)絡融合的發(fā)展背景下，衛(wèi)星網(wǎng)絡因為在其中的重要組成和銜接部分功能正逐漸成為重視和青睞的對象，而國內(nèi)外對衛(wèi)星網(wǎng)絡的研究仍不成熟，很多關鍵技術和核心問題尚待解決。由最初的同步軌道衛(wèi)星發(fā)展到現(xiàn)在的多層協(xié)作衛(wèi)星網(wǎng)絡，利用衛(wèi)星實現(xiàn)全球、應急以及軍事等特殊環(huán)境下的通信優(yōu)勢越來越明顯。已有的多層衛(wèi)星網(wǎng)絡路由協(xié)議包括HSRP （hierarchical satellite routing protocl），MLSR （multilayered satellite routing）， TDRP （tune-slot division QoS routing protocol等。

國內(nèi)外學者對路由性能和衛(wèi)星鏈路建模兩方面的研究有很多的經(jīng)驗，但將路由技術應用到多層衛(wèi)星場景中是一個新的領域。衛(wèi)星通信網(wǎng)絡作為解決傳統(tǒng)網(wǎng)絡局限性和滿足通信需求的關鍵，成為國內(nèi)外社會研究的熱點。

國外方面，2000年，韓國的Jae-Wook Lee等人提出了星上星系統(tǒng)，利用多層網(wǎng)絡解決星間長距離傳輸問題，并提出了HSRP算法。2010年，土耳其的A.AIGhamdi等人提出了一種基于虛擬區(qū)域的最小帶寬算法。該算法根據(jù)衛(wèi)星網(wǎng)絡的數(shù)據(jù)流量選擇最短路徑，具有較好的復雜度和QoS性能但局限于單層衛(wèi)星。2011年，日本的Noriki Uchida等人基于衛(wèi)星網(wǎng)絡研究多路徑冗余方案以應對災難場景，利用鏈路存活檢測和多路徑概率傳輸?shù)燃夹g手段保證數(shù)據(jù)的安全性，但沒有關注網(wǎng)絡的QoS性能。

國內(nèi)，2012年，哈爾濱工程大學的楊春秀提出并設計了優(yōu)化的路由協(xié)議NMLSR （New Multi-LayeredSatellite Routing），該路由協(xié)議相對于MLSR（Multi-Layered Satellite Routing）協(xié)議具有較小的路由開銷，較低的丟包率。但適用的場景受到限制。2012年浙江大學的鄧德鑫提出了基于MPLS的多層衛(wèi)星網(wǎng)絡路由算法，采用信息采集的路由策略，針對時延敏感和業(yè)務需求進行了問題建模，缺少對因素的綜合考慮。2014年，西安電子科技大學的陳競提出了一種適用于雙層衛(wèi)星網(wǎng)的非對稱路由協(xié)議-A-SGRP （Asymmetric-Satellite Grouping and Routing Protocol）路由協(xié)議主要從最短路徑計算、路由表優(yōu)化和特殊鏈路情況處理方案這三方面對SGRP （SatelliteGrouping and Routing Protocol）協(xié)議進行了改進及優(yōu)化。但還有全局路由定期更新效率低的問題。

目前對多層衛(wèi)星路由算法的研究主要是單一的時延丟包率等因素，沒有對時延、帶寬等鏈路因素進行綜合考率，同時許多算法采用分組思想，選擇覆蓋時間長的波束進行接入，限制了衛(wèi)星的選擇并需要地面站屆入。因此本文提出基于流量工程的最小鏈路代價多層衛(wèi)星路由算法TE-MSP（Tratric Engineer-ing-Minimizing Sum of Path-cost）設計流量模型，控制流量分配減少擁堵提出鏈路代價函數(shù)，綜合考慮QoS因素影響，以時延帶寬作為公式因子，既保證了QoS性能，同時避免了對接入控制的限制。

1 基于流量工程的最小鏈路代價多層衛(wèi)星路由算法

為了減輕網(wǎng)絡擁塞，對整個網(wǎng)絡的流量進行合理控制，因此提出基于流量工程的最小鏈路代價多層衛(wèi)星路由算法TE-MSP （Tratllc Engineering-MinimizingSum of Path-cost），本算法借助流量工程中設計流量模型，提出鏈路代價函數(shù)，綜合考慮多QoS因素的影響，從而選擇出適應大容量、復雜網(wǎng)絡的衛(wèi)星轉(zhuǎn)發(fā)路徑，在特定情況下具有更好的時延和鏈路條件，具有一定的擁塞控制能力。應用該算法的網(wǎng)絡結(jié)構(gòu)圖如圖l所示。

圖l所述的衛(wèi)星網(wǎng)絡由LEO/MEO兩層衛(wèi)星組成。層內(nèi)衛(wèi)星由層內(nèi)鏈路連接，兩層衛(wèi)星間由層間鏈路連接。MEO對低層衛(wèi)星具有數(shù)據(jù)收集管理功能，因此層間鏈路具有充足的帶寬。

1.1 流量工程

流量工程指通過路由選擇均衡網(wǎng)絡流量，使數(shù)據(jù)均勻分布，減少網(wǎng)絡擁堵的技術。在大規(guī)模網(wǎng)絡中，大量用戶和業(yè)務存在，網(wǎng)絡中存在大量數(shù)據(jù)，如果采用RIP （Routing Information Protocol）、OSPF （OpenShortest Path First）等最短路徑協(xié)議，會導致某些節(jié)點具有大量數(shù)據(jù)排隊，增加整個網(wǎng)絡時延，降低全網(wǎng)節(jié)點的利用率。

流量工程中的指標有鏈路級別，即：帶寬、時延、利用率：還有流量請求級別，即：最小化路徑時延（路徑上所有鏈路時延之和）、路徑最大鏈路利用率和路徑最大可用帶寬。本文借助流量工程，設計雙層衛(wèi)星的物理拓撲映射規(guī)則，提出流量分配公式，從而優(yōu)化流量工程指標。

流量通過映射分布到網(wǎng)絡的各鏈路中，映射方式可以表示為不同節(jié)點間的轉(zhuǎn)移概率。轉(zhuǎn)移概率的計算過程需要獲取全局的拓撲信息。首先多層衛(wèi)星網(wǎng)絡采用RIP算法，衛(wèi)星節(jié)點向相鄰節(jié)點發(fā)送數(shù)據(jù)包，各節(jié)點通過包里的ST table逐漸修改完善拓撲信息，其包格式設計如下圖2所示。

ST table中記錄了節(jié)點s，t之間的跳數(shù)H，（i，j）∈E的時延delay（i，j）。ιij表示鏈路的流量，ci，j表示最大容量，則對于i，j都屬于LEO節(jié)點時，公式（1）表示（i，j）的轉(zhuǎn)移概率。

在公式（1）中，表示利用率的倒數(shù)，與轉(zhuǎn)移概率之間是負指數(shù)關系，這是為了強調(diào)利用率對轉(zhuǎn)移概率的負反饋作用。H、T表示時延越短，跳數(shù)越小的路徑上的鏈路轉(zhuǎn)移概率越大。

對于i，j中存在MEO節(jié)點的情況不能簡單的使用公式（1），使用MEO時應該考慮MEO衛(wèi)星承載著核心管理功能，不能考慮線性的使用概率。同時MEO衛(wèi)星的帶寬充足，主要考慮發(fā)生流量碰撞造成的影響。

MEO的下行端口數(shù)為M，已使用的端口為數(shù)N，為了避免流量較大時發(fā)生碰撞，從而使下行鏈路時延增加，LEO丟包率增大，MEO選擇的概率公式如公式（2）。w1、W2是調(diào)整MEO選擇概率的權值，改變它們將改變曲線的平緩和尖銳區(qū)間并能控制其轉(zhuǎn)變閾值，從而使MEO的使用方式靈活自由。通過仿真驗證，w1取值為1，w2取值0.6時，接入MEO的概率幾乎不受影響且發(fā)生碰撞的概率較小。

拓撲計算后的R表示在節(jié)點s，t間的轉(zhuǎn)移概率，網(wǎng)絡中的流量矩陣用D表示，它代表網(wǎng)絡中節(jié)點s，t之間的流量請求值，物理拓撲與流量矩陣的乘積就是網(wǎng)絡流量分布L。在一個有向圖G （V，E）中，L是具有E個元素的向量，R是DxE的矩陣.如公式（3）所示，其中rde，o≤rde≤1，d∈{（s，t）|s，t∈V），e∈E。

鏈路的負載L=DxR表示s，t之間的流量之和。說明流量的輸出由轉(zhuǎn)移概率矩陣和網(wǎng)絡流量決定，以概率公式的方法可以優(yōu)化網(wǎng)絡。

在解決實際問題時需要引入約束條件，如帶寬、時延等因素，并通過定義路徑的選擇方式得到優(yōu)化路由。如果以￠i，j表示鏈路（i，j）上的路由代價，則鏈路代價約束的公式如下式（4）

鏈路代價的具體內(nèi)容在下一節(jié)。

1.2 鏈路代價模型

星上星系統(tǒng)是一種連接LEO及其上層衛(wèi)星的架構(gòu)，該系統(tǒng)的轉(zhuǎn)發(fā)標準是短距離使用LEO發(fā)送，長距離使用MEO進行轉(zhuǎn)發(fā)。在數(shù)據(jù)量較大的情況下，會造成ISL堵塞，影響通信質(zhì)量。引入QoS指標，進行時延受限下的負載均衡，從而實現(xiàn)流量工程對數(shù)據(jù)流量進行規(guī)劃分配的目的。本算法的模型建立在該系統(tǒng)之上。

QoS是本模型關注的重點，針對QoS的度量因素有凹形受限、路徑最優(yōu)等思路。在衛(wèi)星網(wǎng)絡中關注QoS因素，主要是針對時延、帶寬、吞吐量、丟包率等因素，通過選擇鏈路條件，限制不穩(wěn)定的連接情況，對節(jié)點的屬性進行考慮而獲得QoS性能提升。本文綜合考慮多層衛(wèi)星網(wǎng)絡的特點，以節(jié)點帶寬作為衡量節(jié)點忙碌的因素，以鏈路的代價衡量鏈路的繁忙和優(yōu)劣性，建立QoS模型。

分析路由算法時，將多層衛(wèi)星網(wǎng)絡看做簡單帶權無向連通圖G= （V，E）。V是圖中所有交點的集合，E是圖中所有邊的集合。針對圖化網(wǎng)絡的元素度量方案如邊長度、邊權值、節(jié)點獨立屬性、節(jié)點網(wǎng)絡屬性及結(jié)合式等。本文選擇邊和節(jié)點結(jié)合的方式度量網(wǎng)絡。設每條邊的權值代表鏈路的代價，函數(shù)表示為cost （e）。設時延函數(shù)為delay （e），帶寬函數(shù)為bandwidth （e），各參數(shù)的計算公式如下。

其中D表示從源節(jié)點R到目的節(jié)點S的一條可行路徑，公式（5）（6）（7）中的D （p）、C（p）、B（p）分別表示該路徑的時延、代價、最小帶寬。時延的約束條件為D，帶寬的約束條件為B。

當所選鏈路使用較少時時延短、丟包率低，但出于相對偏遠位置，會導致時延較長：而過于關注時延，如使用最短路徑等可能造成大量的數(shù)據(jù)堆積，嚴重損壞鏈路帶寬和丟包率。因此引入鏈路代價函數(shù)，鏈路的代價綜合考慮所選鏈路的帶寬和鏈路長度，由時延、帶寬組成代價函數(shù)，由系數(shù)wl和w2調(diào)節(jié)時延和帶寬的敏感程度，wl+w2=1，通常各取0.5。時延相對于帶寬很小，對帶寬進行歸一化處理。所選鏈路綜合考慮帶寬、丟包率，代價最小的情況下保證了帶寬、時延處于平衡狀態(tài)，其代價函數(shù)如公式（8）。

cost（e）=w1·delay（e）+w2·bind（e），e∈p

（8）

對于整條路徑來說，通過不同狀態(tài)下鏈路的平均長度估算鏈路的花費比較簡單易行。對于walker星座來說，單層衛(wèi)星內(nèi)結(jié)構(gòu)相對固定，不同軌道的衛(wèi)星的分布具有規(guī)律性，因此針對固定的星座在大量通信的情況下對路徑采用統(tǒng)計平均的方式是可行的。設所有可行路徑的集合P={Ps，d （n）|n=1，2…N}，針對路徑的花費函數(shù)公式見公式（9）。

時延主要由發(fā)送時延、傳播時延、排隊時延組成。在多層衛(wèi)星網(wǎng)絡中，傳播時延是主要的影響因素。而排隊時延由網(wǎng)絡繁忙度U和節(jié)點傳輸速率T和包的平均大小P決定，排隊時延D的計算公式如下。

公式中的S表示報文的處理速度，A表示衛(wèi)星路由的處理速度，U表示節(jié)點繁忙度。較小的數(shù)據(jù)報文傳輸時，發(fā)送時延很短，可以忽略不計，因此總體時延T為傳播時延與排隊時延之和，如公式（11）。傳播時延公式參數(shù)有鏈路長度L和傳輸速度V。

本文提出的算法是基于流量工程的最小鏈路代價算法，路徑帶寬受限而鏈路代價最小，在網(wǎng)絡繁忙時流量不會過于集中，時延帶寬和丟包率形成的代價花費最小，其模型如公式（12）。

該模型屬于QoS常用的雙度量參數(shù)——路徑最優(yōu)參數(shù)模型，即帶寬受限約束，鏈路代價代價最小，該問題是線性規(guī)劃問題。在兩層網(wǎng)絡中，上層網(wǎng)絡對LEO的完全控制，管理全局信息，具有較大的帶寬，因此可將模型計算過程分為TE-MSP算法啟用前和啟用后兩種情況。

1.3 多層衛(wèi)星路由方案

MEO和LEO每時每刻都在運動，兩層網(wǎng)絡的拓撲結(jié)構(gòu)會隨時變化，因此建立的路由策略必須考慮星間鏈路的改變。當衛(wèi)星移動到鏈路邊緣時發(fā)生斷裂，此時會影響數(shù)據(jù)正常傳輸，建立路由時也需要考慮。

（1） LEO發(fā)送拓撲探測信息，獲取流量矩陣

（2） MEO匯聚流量信息計算概率轉(zhuǎn)移矩陣

（3） LEO接收到用戶請求，將呼叫請求發(fā)給MEO，MEO根據(jù)流量公式和鏈路代價模型計算路徑程，建立路由表項

（4） MEO將路由表項分發(fā)給LEO，LEO傳給用戶作為封裝的包頭

（5）用戶開始傳輸數(shù)據(jù)

2 仿真結(jié)果分析

為了證明流量工程的流量管理功能，先設計如下仿真。對某次接入MEO的請求，當前端口的使用情況與請求響應的概率。其數(shù)據(jù)見圖3。

如圖3所示，當端口使用率小于0.5時，MEO的采用率下降平緩，峰值大于0.6，增加了MEO接入使用的機會。當端口使用率大于0.5時，MEO的接入概率下降速度加快，使用概率0.7時請求響應概率僅0.25，從而減少碰撞的發(fā)生。

為了驗證本算法在LEO衛(wèi)星間的流量管理功能，設計仿真如下，對某節(jié)點的鏈路使用OSPF算法和TE-MSP算法在一段時間內(nèi)處理擁塞的情況。OSPF是典型的隨機取路算法。其結(jié)果如圖4。

如圖4所示，在O.lmin處，OSPF算法的流量為30Mbps，而本算法為50Mbps。在流量較低的時候，OSPF算法按照概率取路，對本節(jié)點的時延、跳數(shù)等因素考慮不足，分配流量數(shù)低于本算法，對節(jié)點的利用效果不好。在時間為0.4min時，OSPF流量達到了90Mbps，而本算法的流量為80Mbps。而時間為0.6min時，OSPF算法的流量為98Mbps，TE-MSP算法流量為86Mbps。說明當流量增加造成擁堵時，OSPF算法任然隨機分配流量，導致節(jié)點流量不減少，丟包率增加，通信性能不好。而TE-MSP算法通過轉(zhuǎn)移概率公式調(diào)節(jié)流量，取得了12%的分流效果，減少了擁堵。

為了證明鏈路代價模型的先進性，本文對OSPF算法和TE-MSP算法在不同的鏈路利用率的時延進行了仿真對比。仿真結(jié)果如圖5。為了進行仿真，需要對網(wǎng)絡中的路徑長度進行平均估算。OSPF算法所選擇的路徑總是最短，雖然傳播時延較短，但是在網(wǎng)絡繁忙的情況下，相對的排隊時延會變長，從而影響路徑的時延因素。在該網(wǎng)絡場景中，OSPF算法只會經(jīng)過LEO衛(wèi)星傳輸數(shù)據(jù)。對6*6矩陣的LEO衛(wèi)星來說，可以將路徑的跳數(shù)進行平均估算。在本場景中，LEO的到最遠節(jié)點的最近跳數(shù)是6，繁忙度超過50%后每增加10%需要增加一條冗余，因此最大跳數(shù)HOPmax是9，而最小跳數(shù)HOPmin為1。因此在計算傳播時延時，以平均跳數(shù)5作為傳播跳數(shù)。

圖5為使用OSPF算法和TE-MSP算法的時延情況。當鏈路利用率在0.4-0.75之間，此時鏈路的傳播時延起著更大的效果。OSPF算法的較短路徑具有更少的時延。但隨著利用率增加，超過0.75后，排隊時延急劇增加，導致OSPF算法的整個時延已經(jīng)大于TE MSP算法時延。說明場景處于繁忙狀態(tài)時，TE-MSP算法的平均時延較短。

為了得出TE-MSP算法在不同環(huán)境條件下的鏈路花費，并驗證該算法具有較小的鏈路代價，對OSPF算法和本算法在不同的鏈路利用率下進行了仿真。結(jié)果如圖6。

鏈路利用率低于0.4時，兩種算法區(qū)別不大。因此對利用率在0.4以后的情況進行分析。如圖5所示，當利用率高于0.4后，TE-MSP算法把擁塞鏈路的數(shù)據(jù)通過MEO進行傳輸。在利用率為0.4-0.65之間，此時多余的數(shù)據(jù)不消耗太多的排隊時延，此時傳輸時延占據(jù)鏈路代價的大部分，可以看到此時鏈路代價略高于最短路徑算法。但隨著利用率增加，TE-MSP算法把帶寬控制在lOOOkhz左右，并通過轉(zhuǎn)移數(shù)據(jù)減少排隊時延，因此傳播時延變長的對代價的影響減弱，當鏈路利用率>0.65時，TE-MSP算法的代價已經(jīng)小于繼續(xù)按照最短路徑算法選路的代價。隨著繁忙度增加，TE-MSP算法的效果增加，在峰值處代價減少23%。

本文首先對MEO端口使用率與請求響應情況的關系進行了仿真，以及LEO衛(wèi)星在遇到大流量時本算法與OSPF算法的對比仿真，證明了本算法提出的流量公式的分流作用；然后仿真對比了本算法和OSPF算法在不同鏈路利用率的時延曲線，可以看出本算法在繁忙場景中控制時延增長的效果；最后仿真對比了兩種算法的鏈路代價，證明了本算法在控制鏈路花費上的優(yōu)越性。

3 總結(jié)

本文針對多層衛(wèi)星網(wǎng)絡的路由算法提出了基于流量工程的最小鏈路代價算法，本算法綜合考慮QoS因素，比傳統(tǒng)算法更合理，以時延、帶寬形成鏈路代價函數(shù)，借助流量工程思想，通過流量轉(zhuǎn)移概率限制鏈路使用率，從而使數(shù)據(jù)的傳輸代價降低，網(wǎng)絡擁塞情況減小。通過仿真結(jié)果可知，在復雜的多層衛(wèi)星網(wǎng)絡環(huán)境中，本算法可以有效應對網(wǎng)絡繁忙的情況，具有可靠的流量調(diào)節(jié)功能，減少網(wǎng)絡時延，提高帶寬利用率，滿足業(yè)務的QoS需求。