基于流量預測的雙層衛星網絡動態路由算法

閻冬 汪路元

（北京空間飛行器總體設計部，北京 100094）

基于流量預測的雙層衛星網絡動態路由算法

閻冬 汪路元

（北京空間飛行器總體設計部，北京 100094）

衛星網絡具有覆蓋廣泛、接入簡單等優點，被認為是下一代互聯網的重要組成部分。文章提出了一種基于流量預測的雙層衛星網絡動態路由技術，拓撲采用LEO層和GEO層雙層衛星網絡結構，能夠支持衛星網絡新節點的動態加入。針對衛星網絡管理員節點在執行網絡任務時可能造成高負載導致高丟包率，從而影響網絡性能的缺點，提出衛星網絡管理員節點調整策略，根據流量預測算法對超過閾值的衛星網絡管理員節點進行更換。最后，文章通過仿真試驗對算法性能進行了驗證，證明此算法在端到端時延和管理員節點丟包率方面具有優勢。

雙層衛星網絡；動態接入；流量預測

1 引言

隨著全球一體化進程的加快，人們對于網絡技術的依賴程度越來越高。傳統網絡主要依靠地面的鏈路和設備傳輸信息，難以覆蓋高山、海洋、沙漠等地形復雜的區域，并且一旦網絡鏈路發生故障，則會造成長時間的網絡服務中斷，給國家經濟和建設造成巨大損失［1］。衛星網絡具有全球覆蓋、接入簡單、支持多種業務等諸多優點，在氣象預測、環境與災害監測、資源探測等領域得到廣泛應用，被認為是下一代互聯網的重要組成部分。

由衛星通信技術和組網技術的發展可以看出，衛星網絡逐步由單層組網方式發展為多層組網方式。雖然單層組網方式實現較為簡單，但卻不夠靈活，不便于實現網絡管理；多層組網方式雖然實現較單層組網方式復雜，并且組網層數越多實現越復雜，但卻能很方便地實現網絡管理，能夠提供包括實時業務、非實時業務等多種類型的網絡服務。當前我國正在開展的導航網絡建設，就是一種多層拓撲結構的網絡，也因為它良好的覆蓋性、較高的數據傳輸能力等，被諸多研究者認為是未來空間網絡的重要組成部分。因此，本文研究多層衛星網絡的路由機制對未來衛星網絡建設有極強的現實意義。

目前，國內外研究人員已經針對多層衛星組網的路由策略進行了一定的研究，并且提出了多種方案。這些方案主要有虛擬節點策略和虛擬拓撲策略［2-6］，大多只對相對固定網絡拓撲進行了研究，雖然可以在不同的時間或空間切換路由表，但卻無法對臨時新加入網絡的節點進行網絡服務。除此之外，這些方案將拓撲中的某些節點作為網絡的管理員節點，并沒有關注到這些節點本身的負載狀況。在實際情況中，由于衛星的高成本因素，這些管理節點往往并不只是起到網絡作用，還要完成其它常規任務。因此，一旦這些管理節點的負載過重，不僅影響它的常規任務的執行，而且會使整個網絡性能急劇下降，甚至崩潰。針對這些問題，并且綜合考慮了系統實現的復雜程度，本文提出了一種基于流量預測的雙層衛星網絡動態路由算法（Traffic Prediction Based Dynamic Routing，TPDR），可以支持網絡節點的動態加入，又能夠避免網絡中的管理員節點負載過重而影響網絡性能。

2 基于流量預測的雙層衛星網絡動態路由方法

針對當前多層衛星網絡路由方法只能對固定網絡結構中的節點進行數據路由和網絡服務，無法解決臨時性節點加入衛星網絡實現正常網絡服務，并且沒有考慮衛星網絡管理員節點的負載情況，可能導致路由信息發送失敗，使網絡性能下降，甚至崩潰的問題，本文擬從以下幾個方面進行改進：首先，提出一種支持臨時性節點動態加入并正常實現網絡服務的雙層衛星網絡模型；其次，提出基于流量預測的網絡節點負載控制方法，可以有效避免衛星網絡“管理員”節點負載過高而影響網絡性能。

2.1 定義

在對TPDR方法進行詳細介紹之前，需要對其中的一些概念加以定義。①衛星網絡：由在軌航天器組成的通信網絡，可以支持子網內節點間、不同子網節點間、節點到地面等通信方式，本文主要討論前兩種天基方式的通信。②子網（SN）：每個LEO層軌道面上的衛星組成一個子網。③區域（AREA）：每個GEO衛星視距范圍內的LEO層衛星組成一個區域。④網絡節點（NODE）：衛星網絡中的節點由衛星或者航天器組成，包括LEO層衛星和GEO層衛星，由于其特殊性，具有處理能力有限，難以補充處理資源的特點。網絡節點可以使用邏輯地址Lij來描述，Lij=｛（i，j），0≤i≤NL-1，0≤j≤NS-1｝，i表示子網編號，j表示LEO衛星在本子網內的編號，NL表示子網數量，NS表示子網內LEO衛星數量。如果j=0，則表示該網絡節點為GEO衛星節點。⑤管理員節點（MANAGER）：每個區域的一個子網內LEO衛星都存在一個管理員。它維護本區域節點信息，包括節點連接關系和健康數據，任務是將接收方不屬于本子網的數據包發送給GEO衛星。⑥鏈路LINK：每個子網內的LEO衛星按照各自位置依次由子網內鏈路（Inner Sub-network Link，ISL）相連接，LEO層管理員則通過層間鏈路（Inter Orbit Link，IOL）與GEO衛星相連接。

2.2 TPDR網絡模型

TPDR網絡是由LEO層衛星節點和GEO衛星節點組成的雙層網絡，TPDR網絡模型示意圖如圖1所示。

圖1 TPDR網絡模型示意圖Eig.1 TPDR topology

圖1中，每個子網內的LEO衛星節點依次與相鄰的LEO衛星節點有鏈路鏈接，而GEO衛星節點只與子網內的管理員有鏈路相連。TPDR中節點的連接關系如圖2所示。

TPDR中，每個LEO衛星節點掌握著本子網的拓撲信息，在子網內LEO衛星節點可以用定義④中的邏輯地址來表示，LEO衛星節點可以根據自己當前的物理位置信息（可以使用經度和緯度來表示），結合本子網的運動軌跡，推斷出本子網其它節點目前的物理位置。當有新節點要加入到子網中時，需要首先向本子網的管理員節點將自己的信息注冊，然后管理員節點向其所屬的GEO衛星報告新節點信息。當管理員節點接收到GEO衛星的確認信息后，向新節點發送確認加入子網信息，并更新本子網成員信息表后在全子網廣播。GEO衛星掌握著視距范圍內所有子網的拓撲結構和成員信息，以及其他GEO衛星所覆蓋的子網范圍。如圖2中，每個GEO衛星視距范圍內包含多個子網，可以覆蓋從南緯70°到北緯70°之間的區域，GEO會與每個子網內的管理員建立連接，并進行數據傳輸。首先，GEO衛星會指定每個子網內一個LEO衛星節點作為本子網的管理員節點，該LEO衛星節點是本子網在GEO衛星視距范圍飛行時間最長的網絡節點，這樣可以盡量減少管理員切換的次數。在圖2中，假設LEO衛星由南向北飛行，G1在SN1中選擇L14作為本子網的管理員。當L14即將飛出G1的視距范圍時，會給G1發送管理員切換請求。G1收到請求后會重新選擇新的管理員，向新管理員發送管理員執行命令并與其建立連接，同時給L14發送管理員切換確認，并斷開與其的連接。新的管理員收到管理員執行請求后，向G1發送管理員執行確認，并在本子網廣播管理員身份信息，并收集本子網所有成員的健康信息。管理員也會定期向其所屬的GEO衛星節點匯報自己的健康狀況信息。

圖2 TPDR節點的連接關系Eig.2 Nodes connection relation

在TPDR中傳輸的天基范圍內數據包，簡單來說可以分為3種類型。第一種是發送者和接受者在同一個子網SN1中如L11要給L13發送數據包，則只需將數據包在本子網傳輸即可。第二種是發送者L13在子網SN1中，而接受者L22在子網SN2中，并且子網SN1和SN2都在同一個區域中。L13現將數據包發送給本子網的管理員L14，然后L14將數據包發送給G1。G1經過查表后發現接收方在本區域的子網SN2，將數據包發送給SN2的管理員L23。最后，L23在本子網內將數據包發送給L22。第三種是發送者L13在子網SN1中，而接受者L52在子網SN5中，并且子網SN1和SN5不在同一個區域中。L13現將數據包發送給本子網的管理員L14，然后L14將數據包發送給G1。G1經過查表后發現接收方不在本區域，接收方子網屬于G2的覆蓋范圍，則將數據包發送給G2。G2接收到數據包后，發現接收方在子網SN5，然后將數據包發送給SN5的管理員L53。最后，L53在本子網內將數據包發送給L52。

在實際的衛星網絡中，由于衛星節點可能由多種類型的衛星構成，如導航衛星、遙感衛星、通信衛星等，因此需要支持多種類型數據傳輸。TPDR能滿足未來衛星網絡工程中的數據傳輸，支持多種類型的服務質量，既可以支持對實時性要求高的數據，如通信數據，又可以支持實時性要求沒那么高，但是卻對數據完整性要求很高的數據，如數據量較大的多媒體數據。前者的實現主要根據當前時刻子網內節點位置與地面站的位置的相對關系，將數據發送到處于地面站測控范圍內的適合節點上，然后直接發送到地面；后者則是將數據發送到GEO衛星節點中，在確認了數據完整性之后，再通過GEO衛星節點發送到地面。

2.3 基于流量預測的節點負載控制方法

衛星網絡具有動態變化、節點處理資源局限、難以維護等與地面網絡差異很大的特點，決定了對該網絡拓撲結構和節點管理的研究具有極大的挑戰性。在衛星管理中，為了實現對動態網絡的管理，需要有一些節點額外承擔網絡管理的任務。這些衛星網絡管理員節點在網絡管理中起著很重要的作用，但是由于它們還要執行常規任務，在出現數據量很大的網絡任務時可能會導致管理員節點負載過重，影響衛星網絡的正常運行，甚至導致網絡崩潰。

數據包到達率是衡量某一時刻網絡節點流量大小的指標，也是影響空間網絡節點性能的一項關鍵指標。數據包到達率越高，節點為了處理這些數據包所需要的計算量也越大。如果數據包到達率超過了節點的處理閾值，可能導致節點較高的丟包率。由于管理員節點是空間網絡中的關鍵節點，當管理員節點負載較大時，難以在執行常規任務的同時，保證路由表計算、路由信息分發等網絡任務的完成。如果能夠有效預測某一時刻節點流量情況，可以有效地避免節點負載過高，保證空間網絡能夠維持較低的丟包率，提供穩定的數據傳輸能力。

由于管理員節點在雙層衛星網絡中的重要作用，它們的性能往往對整個網絡性能產生較大影響。因此，需要在衛星網絡路由機制中增加管理員節點負載控制策略，保證管理員節點的高性能工作狀態。本節提出了一種基于流量預測的管理員節點負載控制方法。考慮到衛星節點的處理能力的局限性，本文采用計算相對簡單的線性預測技術對數據流量進行分析和預測。它的基本思想是：流量數據的每個取樣值可以用它過去若干個取樣值的加權和來表示，各加權系數的確定原則是使預測誤差的均方值最小。典型的線性預測模型有自回歸模型（Autoregressive，AR）和自回歸滑動模型（Autoregressive Moving Average，ARMA），ARMA模型在計算機網絡和傳感器網絡中的流量預測方面已經有了一定的研究［7-9］。應用ARMA能夠有效分析出平穩數據序列的相關性，比AR模型具有更小的預測方差值。因此，本文選擇ARMA（2p，2p-1）模型對衛星網絡節點的數據流量進行分析。其中p為階數，如果該值過大，將需要很大的計算量，所以本文算法中取常用的ARMA（2，1）模型。

假設某衛星網絡節點的數據流量序列為｛Xn'｝，該序列具有周期性，但可能會存在著一定的非平穩性，需要對其進行取對數運算，得到平穩序列｛Xn｝。隨后使用該平穩序列建立ARMA模型，預測第n+1個流量。

式中：B是后移算子；ai是白噪聲，它是獨立同分布的高斯隨機變量。

式中：φ1，φ2，θ1是估計參數。ARMA矩估計方法主要有最小二乘法，最大似然估計方法，最大熵估計方法等等，考慮到衛星網絡節點的計算處理能力，本文采用最小二乘估計方法求解通過估計參數判斷時間序列的穩定性，其穩定性條件為

如果滿足此條件即為平穩序列，得到ARMA擬合模型為

根據衛星節點的數據處理能力，為它們設置數據處理閾值Tmax，即流量閾值。一方面，在選擇本區域管理員節點時，需要首先對被選擇節點的流量進行預測，如果預測得到的管理員節點流量大小超過該閾值Tmax，則不選擇該節點作為管理員節點；另一方面，當管理員節點在運行過程中，會按照一定的周期對它的流量進行預測和評估，如果其流量大小超過該閾值Tmax，則需要在本區域的本子網內切換管理員節點。考慮到工程實際中衛星節點計算能力有限，需要盡可能使用簡單的切換算法，減少衛星節點的計算量開銷。管理員節點確定和切換算法流程圖見圖3。

3 性能評價

在衛星網絡路由機制的設計中，端到端延遲及丟包率是其中重要的性能指標，直接關系到路由機制是否適用于實際的衛星網絡工程應用。為了驗證TPDR的性能，本節選擇一種經典的SGRP多層衛星網絡路由算法［5，10］，對衛星節點端到端時延和管理節點丟包率進行對比。實驗中各項環境參數，包括軌道高度、角速度、數據包平均長度等，按照典型的導航衛星及遙感衛星的實際參數進行設置，充分貼近實際節點的具體情況，具有更強的說服力及現實意義。對于不同的衛星網絡路由算法，衛星節點端到端時延是一項基本的網絡性能指標，能夠說明網絡路由方法的合理性。管理員節點是多層衛星網絡中的關鍵節點，丟包率反映了它目前的數據轉發和傳輸能力，影響著整個網絡的性能。參照文獻［11］，本節的實驗設置TPDR及SGRP環境參數，具體參數設置見表1。

表1 實驗環境參數設置Table 1 Experiment environment setting

為了保證實驗的真實性和有效性，對不同平均鏈路負載狀況下進行1000次實驗，取平均值。圖4是不同鏈路負載狀況下的端到端平均時延的實驗結果。

圖4 平均端到端時延Eig.4 Average end-to-end delay

在圖4所示的衛星節點平均端到端時延的實驗結果不難看出，TPDR的性能要優于SGRP。可能是出于以下原因：首先，SGRP算法需要將收集的網絡拓撲在MEO層的不同MEO衛星之間進行信息交換，網絡拓撲更新較慢；其次，SGRP的網絡拓撲快照劃分較為瑣碎，鏈路更新過于頻繁，協議時延開銷較大。

除了端到端時延之外，本節要對衛星網絡管理節點的丟包率進行驗證。圖5是衛星網絡管理員節點在不同鏈路負載狀況下丟包率的實驗結果。實驗中假設子網中節點流量的3%發往子網外。

圖5 衛星網絡管理節點丟包率Eig.5 Packet loss rate of manager node

圖5所示的實驗結果可以看出，TPDR在衛星管理節點丟包率方面有著更好的性能。其中一個原因是TPDR衛星管理節點使用流量預測算法，當衛星管理員節點預測到在某一時刻處于某一位置的預測流量造成的負載大于某一個閾值時，將更換子網內的管理員節點，而SGRP中卻沒有管理員節點負載控制策略。本試驗中設置管理員節點切換的負載閾值為30%。另一個原因是SGPR中的管理員節點負責的成員較多，需要轉發的本區域外的數據較多，也會使丟包率有一定的增加。

4 結束語

天地一體化網絡是未來空間數據系統發展的必然趨勢，而衛星網絡則是其中的主要組成部分。當前，從國家到各個研究機構和高校，都將衛星網絡作為一項非常重要的研究內容加以推進。本文結合目前我國已經開展的航天工程布局，針對衛星節點計算能力有限的實際情況，提出一種基于節點流量預測的雙層衛星動態路由算法TPDR。該算法主要由以下幾個部分組成：①TPDR拓撲由LEO層衛星和GEO衛星構成，可以支持多種類型的服務質量，支持新節點動態加入，并且改進了SGRP中拓撲快照切換頻繁的缺點，使端到端平均時延得到了改進。②TPDR管理員節點可以根據某一物理位置和某一時間段內的數據流量的歷史信息，預測下一次的數據流量值，如果該流量造成的節點負載大于設置的閾值，則更換子網的管理員節點，這樣能夠避免子網管理員節點丟包率過高。最后通過仿真驗證的方法證明TPDR在端到端平均時延和子網管理員丟包率方面有較好的性能，能夠對未來空間網絡建設起到指導作用。

（

）

［1］Akyildiz I E，Jeong S.Satellite ATM networks：a survey［J］.IEEE Communication Magazine，1997，35（7）：30-44

［2］Ekici E，Akyildiz I E，Michael D B.Datagram routing algorithm for LEO satellite networks［C］//Proceedings of IEEE Infocom.New York：IEEE，2000：500-508

［3］Werner M.A dynamic routing concept for ATM-based satellite personal communication networks［J］.IEEE Journal on Selected Areas in Communications，1997（8）：1636-1648

［4］Akyildiz I E，Ekici E，Bender M D.MLSR：a novel routing algorithm for multi-layered satellite IP network［J］.IEEE/ACM Transaction on Networking，2002（3）：411-424

［5］Chen C，Ekici E，Akyildiz I E.Satellite grouping and routing protocol for LEO/MEO satellite IP networks［C］//Proceedings of The 5th ACM International Workshop on Wireless Mobile Multimedia.Los Angeles：ACM，2002：109-116

［6］Chen C，Ekici E.A routing protocol for hierarchical LEO/MEO satellite IP networks［J］.ACM Wireless Network Journal，2005，11（4）：507-521

［7］曹曉梅，韓志杰，陳貴海.基于流量預測的傳感器網絡拒絕服務攻擊檢測方案［J］.計算機學報，2007，30（10）：1798-1805 Cao Xiaomei，Han Zhijie，Chen Guihai.DoS attack detection scheme for sensor networks based on traffic prediction［J］.Chinese Journal of Computers，2007：1798-1805（in Chinese）

［8］李捷，劉先省，韓志杰.基于ARMA的無線傳感器網絡流量預測模型的研究［J］.電子與信息學報，2007，29（5）：1224-1227 LiJie，Liu Xianxing，Han Zhijie.Research on the ARMA-based traffic prediction algorithm for wireless sensor network［J］.Journal of Electronics&Information Technology，2007，29（5）：1224-1227（in Chinese）

［9］鄒柏強，劉強.基于ARMA模型的網絡流量預測［J］.計算機研究與發展，2002，39（12）：113-118 Zou Baixian，Liu Qiang.ARMA-based traffic prediction and overload detection of network［J］.Journal of Computer Research and Development，2002，39（12）：113-118（in Chinese）

［10］龍飛.衛星網絡魯棒QoS路由技術研究［M］.北京：國防工業出版社，2010 Long Eei.Research on robust QoS routing for satellite network［J］.Beijing：National Defense Industry Press，2010（in Chinese）

［11］王汝傳，饒元，鄭彥，等.衛星通信網路由技術及其模擬［M］.北京：人民郵電出版社，2010 Wang Ruchuan，Rao Yuan，Zheng Yan，et al.Satellite communication network routing technology and simulation［M］.Beijing：Posts&Telecom Press，2010（in Chinese）

（編輯：張小琳）

Traffic Prediction-based Routing Algorithm for LEO&GEO Satellite Network

YAN Dong WANG Luyuan
（Beijing Institute of Spacecraft System Engineering，Beijing 100094，China）

Satellite network has the advantage of global coverage and simple access，so it is considered to be an important part of next generation Internet.In this paper，we propose a novel traffic prediction based dynamic routing technique for double-layered satellite networks，which is called TPDR.It has a double-layered structure，composed of LEO layer and GEO layer.TPDR supports new nodes to join the network，and prevents the manager nodes from becoming overloaded based on traffic prediction.In the end，the performances of end-to-end delay and loss rate of manager packet are evaluated by simulations.

double-layered satellite networks；dynamic access；traffic prediction

TP393.04

A DOI：10.3969/j.issn.1673-8748.2015.03.012

2015-02-13；

2015-05-05

國家自然科學基金重大研究計劃（91438102）

閻冬，男，博士，工程師，研究方向為星間網絡技術與航天器數據管理技術。Email：yandong200@163.com。