戴翠琴，李 劍，唐 煌

(重慶郵電大學(xué) 移動通信技術(shù)重點實驗室，重慶 400065)

衛(wèi)星時變網(wǎng)絡(luò)中基于連接計劃的最短路徑優(yōu)化算法

戴翠琴，李 劍，唐 煌

(重慶郵電大學(xué) 移動通信技術(shù)重點實驗室，重慶 400065)

在衛(wèi)星時變拓?fù)渚W(wǎng)絡(luò)中，針對Dijkstra最短路徑算法不能時刻保證路徑最優(yōu)的問題，結(jié)合衛(wèi)星節(jié)點運(yùn)動規(guī)律的確定性，研究分析了衛(wèi)星網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化的周期性特征，提出了一種基于連接計劃(contact plan, CP)的最短路徑算法(CP-Dijkstra)。在低軌 (low earth orbit, LEO) 衛(wèi)星系統(tǒng)中，首先根據(jù)不同時刻星間鏈路的時變連接情況形成動態(tài)CP，然后根據(jù)CP是否發(fā)生改變對信息進(jìn)行不同的處理：當(dāng)節(jié)點檢查到CP未改變，則根據(jù)之前計算的最短路徑進(jìn)行轉(zhuǎn)發(fā)；反之，則根據(jù)當(dāng)前最新的CP重新計算到達(dá)目的節(jié)點的最短路徑，直至信息成功轉(zhuǎn)發(fā)到目的節(jié)點，從而確保信息經(jīng)過的一系列路徑序列為最短路徑。仿真結(jié)果表明，與衛(wèi)星時變網(wǎng)絡(luò)中常用的動態(tài)虛擬拓?fù)渎酚?dynamic virtual topology routing, DVTR)算法相比，CP-Dijkstra算法不僅能夠較好地提升網(wǎng)絡(luò)吞吐量，而且可以有效地降低網(wǎng)絡(luò)平均時延和丟包率。

衛(wèi)星時變網(wǎng)絡(luò)；最短路徑算法；連接計劃；吞吐量；丟包率

0 引 言

與地面通信網(wǎng)絡(luò)相比，衛(wèi)星通信網(wǎng)絡(luò)能夠?qū)崿F(xiàn)遠(yuǎn)距離大容量的空間信息傳輸，但是空間節(jié)點有限的存儲和處理能力，以及周期性的動態(tài)軌道運(yùn)動，使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和鏈路權(quán)值隨著衛(wèi)星運(yùn)行時間變化而呈現(xiàn)周期性變化，因此傳統(tǒng)地面網(wǎng)絡(luò)中的路由算法不能直接應(yīng)用到衛(wèi)星網(wǎng)絡(luò)中。近年來，隨著人們對空間寬帶通信的需求與日俱增，具有星間鏈路(inter-satellite link, ISL)及星上處理能力的新一代寬帶衛(wèi)星通信網(wǎng)絡(luò)中的關(guān)鍵技術(shù)，尤其是路由算法研究受到了人們廣泛的關(guān)注[1-2]。

目前，針對衛(wèi)星網(wǎng)絡(luò)拓?fù)鋭討B(tài)時變的特性，已有的研究[3-7]通常采用虛擬拓?fù)淇刂撇呗詠砥帘瓮負(fù)涞膭討B(tài)性，進(jìn)而針對靜態(tài)的拓?fù)湫蛄羞M(jìn)行路由優(yōu)化計算。虛擬拓?fù)淇刂撇呗裕阂粋€系統(tǒng)周期T被劃分為若干個時間片[t0,t1],[t1,t2],[t2,t3],…，[tn-1,tn]，ISL的變化僅在時間點t1,t2,…,tn發(fā)生，且假定每個時間片[ti,ti+1]內(nèi)的衛(wèi)星網(wǎng)絡(luò)拓?fù)洳蛔?，從而將衛(wèi)星網(wǎng)絡(luò)的動態(tài)拓?fù)潆x散化為若干個靜態(tài)拓?fù)?。文獻(xiàn)[3] 在低軌(low earth orbit, LEO) 衛(wèi)星通信網(wǎng)絡(luò)中，提出了一種基于虛擬拓?fù)洳呗缘碾x散時間動態(tài)虛擬拓?fù)渎酚?discrete-time dynamic virtual topology routing, DT-DVTR) 算法。文獻(xiàn)[4]將LEO衛(wèi)星模擬成有限狀態(tài)自動機(jī)，每個狀態(tài)對應(yīng)于LEO衛(wèi)星網(wǎng)絡(luò)系統(tǒng)周期中的一個等長度時間間隔，從而將LEO衛(wèi)星網(wǎng)絡(luò)的動態(tài)鏈路分配問題等效成一組靜態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下的固定鏈路分配和路由優(yōu)化問題。文獻(xiàn)[5]第一次提出了快照(snapshot)的概念，一旦任意ISL臨時斷開或重新連接，一個不同于先前的快照就形成了，每一個快照對應(yīng)一個特定時刻的衛(wèi)星網(wǎng)絡(luò)拓?fù)?；在此基礎(chǔ)上，針對衛(wèi)星存儲能力有限問題，提出了一種程序存儲模型來存儲必要的路由表，從而節(jié)省了衛(wèi)星的存儲空間。為了描述衛(wèi)星網(wǎng)絡(luò)快照的變化規(guī)律，Wang等人[6]給出了LEO衛(wèi)星網(wǎng)絡(luò)快照數(shù)目與快照長度的理論計算公式，F(xiàn)ischer等[7]完成了快照概念的形式化描述。然而，以上研究主要針對特定衛(wèi)星網(wǎng)絡(luò)中的特定問題，沒有對諸如網(wǎng)絡(luò)最短路徑、哈密頓(Hamilton)回路、最大流等基礎(chǔ)問題進(jìn)行分析, 因此不能將上述研究中得到的結(jié)論直接應(yīng)用到所有衛(wèi)星網(wǎng)絡(luò)中。

在傳統(tǒng)地面網(wǎng)絡(luò)中，基于時變拓?fù)涞淖疃搪窂絾栴}已得到一定程度的關(guān)注[8]，并提出了一些基于圖論優(yōu)化理論求解最短路徑問題的方法和算法[9-11]。然而，已有研究雖然考慮了網(wǎng)絡(luò)拓?fù)浜玩溌窓?quán)值的時變性，但均是針對地面中不同類型的時變網(wǎng)絡(luò)，不能完全應(yīng)用到衛(wèi)星時變拓?fù)渚W(wǎng)絡(luò)中，如：文獻(xiàn)[9]主要解決的是隨機(jī)時變神經(jīng)網(wǎng)絡(luò)中的最短路徑問題，文獻(xiàn)[10-11]主要研究了城市交通時變網(wǎng)絡(luò)中的最短路徑問題。目前，對于衛(wèi)星網(wǎng)絡(luò)中的最短路徑問題的研究較少，文獻(xiàn)[12]通過將衛(wèi)星時變拓?fù)渚W(wǎng)絡(luò)模型離散化，利用離散衛(wèi)星網(wǎng)絡(luò)模型來解決傳統(tǒng)迪杰斯特拉(Dijkstra)算法在衛(wèi)星時變網(wǎng)絡(luò)中不能直接應(yīng)用的問題；文獻(xiàn)[13]將LEO時變衛(wèi)星網(wǎng)絡(luò)分為T/Δt個靜止子網(wǎng)，在每一個固定不變的子網(wǎng)中計算源節(jié)點衛(wèi)星到其他節(jié)點衛(wèi)星的最短路徑，從而得到[T·n(n-1)]/2Δt條最短路徑，然后將這些最短路徑分成n張路由表，再將這些路由表通過移動代理分發(fā)到n個衛(wèi)星中。但是，在鏈路頻繁切換的衛(wèi)星網(wǎng)絡(luò)中，離散時間片大小的選取直接影響到路由的計算量和路由的有效性，以致當(dāng)拓?fù)浣Y(jié)構(gòu)發(fā)生改變時，路由算法不能及時地做出相應(yīng)的處理，在衛(wèi)星失效的情況下，網(wǎng)絡(luò)不能正確傳輸處理信息，從而造成信息丟失。

針對以上問題，本文基于LEO衛(wèi)星時變網(wǎng)絡(luò)，通過引入連接計劃(contact plan, CP)[14-15]的概念完成了衛(wèi)星網(wǎng)絡(luò)時變拓?fù)涞亩棵枋?，進(jìn)而提出了一種基于CP的最短路徑算法(CP-Dijkstra)。與傳統(tǒng)基于虛擬拓?fù)洳呗缘男l(wèi)星網(wǎng)絡(luò)路由算法不同的是，本文引入了CP來代替衛(wèi)星離散化模型進(jìn)行最短路徑的優(yōu)化設(shè)計和計算。節(jié)點在發(fā)送信息前，會檢查當(dāng)前時刻的CP 是否發(fā)生改變，如果沒改變，則直接用信息中保存的最短路徑繼續(xù)轉(zhuǎn)發(fā)；如果檢查到CP發(fā)生改變，則在此節(jié)點重新計算信息到目的節(jié)點的最短路徑，并覆蓋信息中保存的最短路徑，利用新的路徑進(jìn)行轉(zhuǎn)發(fā)，直至到達(dá)目的節(jié)點。從而，保證了CP-Dijkstra算法在衛(wèi)星鏈路發(fā)生切換時，也能正確計算最短路徑，改善了衛(wèi)星網(wǎng)絡(luò)的性能。

1 系統(tǒng)模型

LEO衛(wèi)星網(wǎng)絡(luò)模型如圖1所示，該系統(tǒng)由N×M顆衛(wèi)星組成，其中N是衛(wèi)星軌道數(shù)目，M是每個軌道中衛(wèi)星的數(shù)目，衛(wèi)星的運(yùn)行周期為T，星間鏈路連通情況和鏈路長度隨著衛(wèi)星運(yùn)行時間的變化而周期性變化。

衛(wèi)星時變拓?fù)渚W(wǎng)絡(luò)是一個無向圖，其鏈路權(quán)值是以時間為變量的周期函數(shù)，其數(shù)學(xué)模型可表示為

(1)

(1)式中：V是衛(wèi)星節(jié)點的有窮非空集合；A是衛(wèi)星節(jié)點間的有限邊集；W表示衛(wèi)星節(jié)點vi和vj間的鏈路權(quán)值，可以用鏈路距離、時延或其他費(fèi)用來表示。

圖1 LEO衛(wèi)星網(wǎng)絡(luò)模型Fig.1 LEO satellite network model

假設(shè)P={v0,v1,…,vd|v0,v1,…,vd∈V}是在衛(wèi)星網(wǎng)絡(luò)中從源節(jié)點v0到目的節(jié)點vd的其中一條路徑，則路徑P的權(quán)值由 (2) 式得到，

(2)

定義1 如果P是從衛(wèi)星源節(jié)點S到目的節(jié)點D的其中一條路徑，并且網(wǎng)絡(luò)中其他從S到D的所有路徑中沒有權(quán)值比P的權(quán)值更小的路徑，則P是衛(wèi)星節(jié)點S到D的最短路徑。

隨著衛(wèi)星運(yùn)行的時間變化，不同時刻星間鏈路連接情況A(t)可以描述為

(3)

(3)式中：ai,j(t)表示衛(wèi)星網(wǎng)絡(luò)中任意2顆衛(wèi)星vi和衛(wèi)星vj間的鏈路通斷情況，可由(4)式計算得到。

(4)

(4)式中，(Ni,Nj)∈N,(Mi,Mj)∈M。

同時，W(t)的值隨著衛(wèi)星運(yùn)行時間變化呈現(xiàn)周期性的變化，本文中W(t)代表星間鏈路距離，可表示為

(5)

圖2 星間鏈路變化情況Fig.2 Variation of ISLs

2 CP-Dijkstra算法

2.1 問題描述

在地面固定拓?fù)渚W(wǎng)絡(luò)中，節(jié)點間的鏈路發(fā)生切換的概率較低，最短路徑算法的計算結(jié)果準(zhǔn)確度較高。但是，在衛(wèi)星時變拓?fù)渚W(wǎng)絡(luò)中，由于衛(wèi)星移動速度快，導(dǎo)致星間鏈路會頻繁切換，如果直接應(yīng)用傳統(tǒng)的最短路徑算法，在一些情況下不能計算得到正確的最短路徑，從而導(dǎo)致信息不能正確轉(zhuǎn)發(fā)到目的節(jié)點，使得網(wǎng)絡(luò)性能大幅下降。

圖3給出了衛(wèi)星時變網(wǎng)絡(luò)中Dijkstra算法的問題分析，當(dāng)信息要從源節(jié)點S傳輸?shù)侥康墓?jié)點D，節(jié)點b和節(jié)點c間的鏈路在t2時刻會發(fā)生切換，節(jié)點b的鄰居節(jié)點由c變?yōu)閒，此時，Lb,c=∞，節(jié)點a在t1時刻會有一條直接鏈路到達(dá)e，La,e

1)當(dāng)信息在t2時刻到達(dá)節(jié)點b時，由于星間鏈路的切換導(dǎo)致Lb,c=∞，此時，信息無法轉(zhuǎn)發(fā)到目的節(jié)點，造成信息丟失；

2)當(dāng)信息在t1時刻到達(dá)節(jié)點a時，星間鏈路的切換導(dǎo)致節(jié)點a與節(jié)點e之間存在直接鏈路，并且La,e

因此，傳統(tǒng)最短路徑Dijkstra算法應(yīng)用在衛(wèi)星時變拓?fù)渚W(wǎng)絡(luò)中時，會出現(xiàn)因星間鏈路頻繁切換導(dǎo)致無法時刻保證路徑最優(yōu)的問題。

圖3 衛(wèi)星時變網(wǎng)絡(luò)中Dijkstra算法問題分析Fig.3 Problem analysis of Dijkstra algorithm in satellite time-varying network

2.2 衛(wèi)星時變網(wǎng)絡(luò)中的連接計劃

由以上問題分析描述可知：由于衛(wèi)星網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化，造成星間鏈路的頻繁切換，進(jìn)而導(dǎo)致Dijkstra算法計算得到的結(jié)果不能保證是最優(yōu)解。通過研究分析衛(wèi)星確定的運(yùn)動規(guī)律，假設(shè)連接機(jī)會是計劃好或者規(guī)劃好的，而不是通過預(yù)測或者發(fā)現(xiàn)的[16]，那么利用衛(wèi)星連接信息和距離信息可以生成一條連接計劃，所有的連接計劃構(gòu)成一張連接計劃表，將衛(wèi)星時變網(wǎng)絡(luò)拓?fù)溆靡粡堖B接計劃表來描述。每一條連接計劃包括連接的源節(jié)點、目的節(jié)點、起始時間、結(jié)束時間以及通信距離等。

例如，圖4描述了一個簡單的衛(wèi)星網(wǎng)絡(luò)拓?fù)洌嬖?條連接：衛(wèi)星節(jié)點S1和S2在t1到t4時間段內(nèi)的一條連接；衛(wèi)星節(jié)點S2和S3在t2到t5時間段內(nèi)的一條連接；衛(wèi)星節(jié)點S3和S4在t3到t6時間段內(nèi)的一條連接。首先，通過連接表可以得到衛(wèi)星在每一個時刻的連接計劃，即：當(dāng)前時刻的衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及權(quán)值等。然后，通過當(dāng)前時刻的連接計劃，利用Dijkstra算法可以計算得到當(dāng)前時刻的最短路徑，進(jìn)而進(jìn)行信息轉(zhuǎn)發(fā)。

在路由算法開始計算前，連接表會提前分發(fā)到各個衛(wèi)星節(jié)點中。由于衛(wèi)星網(wǎng)絡(luò)中，衛(wèi)星節(jié)點只跟鄰居節(jié)點有鏈路連接，與其他節(jié)點均沒有直連鏈路，因此根據(jù)連接表可以計算得到每個節(jié)點在每個時刻的鄰居節(jié)點集，利用鄰居節(jié)點集來進(jìn)行Dijkstra路由算法計算，可以降低衛(wèi)星有限的計算能力和節(jié)省衛(wèi)星中有限的存儲空間。

圖4 衛(wèi)星時變網(wǎng)絡(luò)中的連接計劃示例Fig.4 Example of contact plan in satellite time-varying network

2.3 基于連接計劃的最短路徑優(yōu)化算法步驟

在信息發(fā)送之前，根據(jù)當(dāng)前時刻連接計劃，利用Dijkstra算法計算出從源節(jié)點S到目的節(jié)點D的一條最短路徑，連接計劃隨著時間的變化會不斷更新，因此信息在不同時刻的轉(zhuǎn)發(fā)路徑也會不一樣，不能用過去存在的連接來轉(zhuǎn)發(fā)信息，因此當(dāng)信息轉(zhuǎn)發(fā)到下一跳節(jié)點時，下一跳節(jié)點會判斷節(jié)點間的連接計劃是否發(fā)生改變，如果連接計劃沒有改變，則根據(jù)上一節(jié)點計算出的最短路徑繼續(xù)轉(zhuǎn)發(fā)到后面的節(jié)點，反之，如果在下一跳節(jié)點檢查到連接計劃發(fā)生改變，則在下一跳節(jié)點根據(jù)當(dāng)前的連接計劃重新計算一條新的到達(dá)目的節(jié)點的最短路徑，直到信息到達(dá)目的節(jié)點。通過這一系列的路徑序列，從而可以組成源節(jié)點到目的節(jié)點的最短路徑。具體算法流程如下：

步驟1 由于衛(wèi)星的運(yùn)動規(guī)律具有確定性的特點，因此在路由算法計算之前，首先根據(jù)連接信息(連接起始時間、連接結(jié)束時間、發(fā)送節(jié)點、接收節(jié)點、通信速率)和距離信息(連接起始時間、連接結(jié)束時間、發(fā)送節(jié)點、接收節(jié)點、通信距離)生成連接計劃表，并提前分發(fā)給衛(wèi)星網(wǎng)絡(luò)中所有的節(jié)點。

步驟2 通過連接計劃表計算出節(jié)點在每一時刻的鄰居節(jié)點集。當(dāng)t時刻源節(jié)點S產(chǎn)生信息m時，節(jié)點S根據(jù)t時刻的連接計劃，利用節(jié)點的鄰居節(jié)點集來進(jìn)行Dijkstra算法計算，生成一條到達(dá)目的節(jié)點D的最短路徑，并保存在信息m中進(jìn)行轉(zhuǎn)發(fā)。

步驟3 當(dāng)信息根據(jù)源節(jié)點計算的最短路徑從源節(jié)點轉(zhuǎn)發(fā)到下一跳節(jié)點A時，此時節(jié)點A會根據(jù)連接計劃是否發(fā)生改變對信息做如下2種處理：

①如果節(jié)點A檢查到連接計劃沒有發(fā)生改變，則按照信息中保存的最短路徑繼續(xù)轉(zhuǎn)發(fā)到下一跳節(jié)點；

②如果節(jié)點A檢查到連接計劃已發(fā)生了改變，則在節(jié)點A根據(jù)當(dāng)前連接計劃重新計算一條新的到達(dá)目的節(jié)點D的最短路徑，并覆蓋原來保存的最短路徑，按照新的最短路徑進(jìn)行信息轉(zhuǎn)發(fā)到下一跳節(jié)點。

步驟4 在后面的節(jié)點中重復(fù)步驟3的操作，直到信息m到達(dá)目的節(jié)點D，此時信息m所經(jīng)過的一系列路徑序列即可組成其最短路徑。

3 仿真分析

為了驗證CP-Dijkstra算法性能，本文使用衛(wèi)星工具包 (satellite tool kit, STK)和MATLAB仿真軟件進(jìn)行了聯(lián)合仿真。仿真中設(shè)置了2種不同負(fù)載業(yè)務(wù)流的網(wǎng)絡(luò)場景：輕負(fù)載業(yè)務(wù)流網(wǎng)絡(luò)場景和重負(fù)載業(yè)務(wù)流網(wǎng)絡(luò)場景。在2種不同的網(wǎng)絡(luò)場景下，令發(fā)包速率分別為5 packets/min和10 packets/min，通過與衛(wèi)星網(wǎng)絡(luò)中普遍采用的動態(tài)虛擬拓?fù)渎酚伤惴?dynamic virtual topology routing, DVTR) 在吞吐量、丟包率和平均時延等性能方面的對比分析，比較2種算法在衛(wèi)星時變網(wǎng)絡(luò)中的準(zhǔn)確性、有效性等。DVTR算法的基本思想是：首先，將衛(wèi)星周期等分為若干個時間片，每一個時間片對應(yīng)一個靜態(tài)拓?fù)?；然后，在靜態(tài)拓?fù)渲杏嬎阕疃搪窂健?/p>

表1 仿真參數(shù)設(shè)置

圖5和圖6分別給出了輕、重負(fù)載下2種算法的丟包性能，由圖5、圖6可知重負(fù)載下2種算法的丟包率性能均要高于輕負(fù)載的情況，而DVTR算法的增幅較大，這是因為在重負(fù)載網(wǎng)絡(luò)場景中，包的發(fā)送速率較快，而DVTR算法在鏈路切換時刻計算不準(zhǔn)確時，源節(jié)點計算的路由失效導(dǎo)致信息丟失數(shù)較多。同時，圖5和圖6也分別比較了DVTR算法和CP-Dijkstra算法的丟包率在不同負(fù)載、不同時刻的變化情況。當(dāng)運(yùn)行時間為0時，衛(wèi)星網(wǎng)絡(luò)中沒有信息產(chǎn)生，丟包率為0；隨著衛(wèi)星運(yùn)行時間的增加，2種算法的丟包率均穩(wěn)定在一定的范圍內(nèi)變化。而2種算法的丟包率在不同時刻會起伏變化，這是由于星間鏈路的切換會導(dǎo)致丟包率的變化。如圖5、圖6所示，CP-Dijkstra算法的丟包率在任意時刻均要低于DVTR算法，因為DVTR算法使用固定時間間隔Δt將衛(wèi)星周期離散化，當(dāng)鏈路切換時刻發(fā)生在Δt之外(兩離散間隔之間)時，此時如果信息按照Dijkstra算法計算出的最短路徑進(jìn)行轉(zhuǎn)發(fā)，由于節(jié)點間的鏈路不存在，信息不能轉(zhuǎn)發(fā)到下一跳節(jié)點，從而將會導(dǎo)致信息無法準(zhǔn)確到達(dá)目的節(jié)點，其丟包率會大大增加。

圖5 輕負(fù)載業(yè)務(wù)流網(wǎng)絡(luò)中的丟包率性能Fig.5 Performance of packet loss probability in light load traffic network

圖6 重負(fù)載業(yè)務(wù)流網(wǎng)絡(luò)中的丟包率性能Fig.6 Performance of packet loss probability in heavy load traffic network

圖7、圖8分別給出輕、重負(fù)載下2種算法的吞吐量性能，由圖7和圖8可知，無論是DVTR算法還是CP-Dijkstra算法，在重負(fù)載網(wǎng)絡(luò)場景中的吞吐量性能都增大，CP-Dijkstra算法稍為明顯，這是由于在衛(wèi)星節(jié)點高速移動的情況下，即網(wǎng)絡(luò)拓?fù)漕l繁變化時，DVTR算法路由計算不一定準(zhǔn)確，且在短時間內(nèi)不能及時建立新的有效路由，從而導(dǎo)致在同一時刻，采用CP-Dijkstra算法的網(wǎng)絡(luò)在重負(fù)載情況下收到的信息數(shù)更多。同時，圖7和圖8也分別顯示了隨著衛(wèi)星運(yùn)行時間的變化，DVTR算法和CP-Dijkstra算法的吞吐量的變化情況。如圖所示，在同一時刻，DVTR算法的吞吐量性能總是低于CP-Dijkstra算法。這是由于DVTR算法采用的是靜態(tài)拓?fù)渎酚捎嬎惴椒ǎ摲椒ú荒軠?zhǔn)確的處理鏈路切換問題，最短路徑算法在鏈路的連接發(fā)生變化后的計算結(jié)果不能完全適用，導(dǎo)致信息在轉(zhuǎn)發(fā)過程中不能通過計算得到的最短路徑轉(zhuǎn)發(fā)到下一跳而丟失，從而目的節(jié)點不能收到發(fā)送的信息。因此，相比較于CP-Dijkstra算法，其吞吐量有所降低。

圖7 輕負(fù)載業(yè)務(wù)流網(wǎng)絡(luò)中的吞吐量性能Fig.7 Performance of throughput in light load traffic network

圖8 重負(fù)載業(yè)務(wù)流網(wǎng)絡(luò)中的吞吐量性能Fig.8 Performance of throughput in heavy load traffic network

圖9、圖10分別給出了輕、重負(fù)載下2種算法的平均時延性能，由圖9和圖10可知，在重負(fù)載網(wǎng)絡(luò)中，兩種算法的平均時延均有所增大，而DVTR算法的平均時延性能表現(xiàn)的更差，這是因為具有高速移動特性的衛(wèi)星節(jié)點會導(dǎo)致鏈路的頻繁中斷，DVTR算法不能保證所有信息的轉(zhuǎn)發(fā)路徑在不同時刻一定處于連通狀態(tài)，從而使得源節(jié)點重新計算路由，導(dǎo)致部分節(jié)點不能及時處理消息，使得節(jié)點負(fù)載過重而丟棄信息造成更大的時延。圖9和圖10分別對DVTR算法和CP-Dijkstra算法的平均時延進(jìn)行了比較。當(dāng)運(yùn)行時間為0時，衛(wèi)星網(wǎng)絡(luò)中沒有產(chǎn)生任何信息，因此平均時延為0；隨著運(yùn)行時間的變化，網(wǎng)絡(luò)中信息數(shù)量會不斷增加，兩種算法的網(wǎng)絡(luò)的平均時延變化均穩(wěn)定在一定范圍內(nèi)。如圖所示，由于DVTR算法在星間鏈路頻繁切換時，計算的最短路徑不一定正確或是最優(yōu)，當(dāng)計算得到的最短路徑中的鏈路發(fā)生切換，信息不能及時轉(zhuǎn)發(fā)到下一跳，從而需要等待至少一個周期之后，才能將信息轉(zhuǎn)發(fā)到最短路徑中的下一跳節(jié)點，因此導(dǎo)致其平均時延要高于CP-Dijkstra算法。

圖9 輕負(fù)載業(yè)務(wù)流網(wǎng)絡(luò)中的平均時延性能Fig.9 Performance of average delay time in light load traffic network

圖10 重負(fù)載業(yè)務(wù)流網(wǎng)絡(luò)中的平均時延性能Fig.10 Performance of average delay time in heavy load traffic network

4 結(jié)束語

本文針對LEO衛(wèi)星時變網(wǎng)絡(luò)，提出了一種基于連接計劃的最短路徑Dijkstra優(yōu)化算法，在信息傳輸前，節(jié)點首先會判斷連接計劃是否發(fā)生改變，如果沒有改變，則利用之前已計算好的最短路徑進(jìn)行信息轉(zhuǎn)發(fā)；否則，節(jié)點會根據(jù)當(dāng)前時刻的連接計劃重新計算一條最短路徑，從而更新之前節(jié)點計算得到的最短路徑，并將其保存到信息中，此時信息將會按照新的最短路徑進(jìn)行轉(zhuǎn)發(fā)，直到信息到達(dá)目的節(jié)點。仿真結(jié)果表明，采用CP-Dijkstra算法不僅提高了網(wǎng)絡(luò)的吞吐量，而且降低了網(wǎng)絡(luò)丟包率和平均時延。

[1] HONG S G, SU C J. ASAP: fast, controllable, and deployable multiple networking system for satellite networks[C]// IEEE Global Communications Conference (GLOBECOM). San Diego, CA: IEEE, 2015:1-7.

[2] WAN Peng, YE Jianshe, SONG Shijie. Study on the telecommunication technology based on the distributed satellite constellation networks[C]// IEEE Aerospace Conference. Big Sky, MT: IEEE, 2014:1-8.

[3] WERNER M. A dynamic routing concept for ATM-based satellite personal communication networks [J]. IEEE Journal on Selected Areas in Communications, 1997, 15(8):1636-1648.

[4] CHANG H S, KIM B W, CHANG L, et al. FSA-based link assignment and routing in low-earth orbit satellite networks [J]. IEEE Transactions on Vehicular Technology, 1998, 47(3):1037-1048.

[5] GOUNDER V V, PRAKASH R, ABU-AMARA H. Routing in LEO-based satellite networks[C]// IEEE Proceedings of Emerging Technologies Symposium, Wireless Communications and Systems. Richardson, TX: IEEE, 1999:22.1-22.6.

[6] WANG Junfeng, LI Lei, ZHOU Mingtian. Topological dynamics characterization for LEO satellite networks [J]. Computer Networks, 2007, 51(1):43-53.

[7] FISCHER D, BASIN D, ECKSTEIN K, et al. Predictable mobile routing for spacecraft networks [J]. IEEE Transactions on Mobile Computing, 2013, 12(6):1174-1187.[8] AHUJA R K, MAGNANTI T L, ORLIN J B. Network flows: theory, algorithms, and applications [M]. Englewood Cliffs, New Jersey: Prentice Hall, 1993.

[9] 閆春望,黃瑋,王勁松.一種隨機(jī)時變神經(jīng)網(wǎng)絡(luò)最短路徑算法[J].天津理工大學(xué)學(xué)報,2016,32(2):40-44. YAN Chunwang, HUANG Wei, WANG Jinsong. A stochastic time-varing neural network shortest path algorithm [J]. Journal of Tianjin University of Technology, 2016, 32(2):40-44.

[10] ROSYIDI L, PRADITYO H P, GUNAWAN D, et al. Time-base dynamic weight for Dijkstra algorithm implementation in route planning software[C]// International Conference on Intelligent Green Building and Smart Grid. Taipei: IEEE, 2014:1-4.

[11] WEI Mingjun, MENG Yu. Research on the optimal route choice based on improved Dijkstra[C]// IEEE Workshop on Advanced Research and Technology in Industry Applications. Ottawa, ON: IEEE, 2014:303-306.

[12] DONG Xiangjun, SHI Haoshan. A shortest path algorithm based on mobile agent in LEO satellite network[C]// IEEE International Conference on Wireless Communications, Networking and Mobile Computing. Dalian: IEEE, 2008:1-5.[13] 張濤, 柳重堪, 張軍. 衛(wèi)星時變拓?fù)渚W(wǎng)絡(luò)最短路徑算法研究[J]. 計算機(jī)學(xué)報, 2006, 29(03):371-377. ZHANG Tao,LIU Zhongkan,ZHANG Jun.A shortest path algorithm for satellite time-varying topological network [J].Chinese Journal of Computers,2006,29(03):371-377.[14] FRAIRE J A, FINOCHIETTO J M. Design challenges in contact plans for disruption-tolerant satellite networks [J]. IEEE Communications Magazine, 2015, 53(5):163-169.[15] ARANITI G, BEZIRGIANNIDIS N, BIRRANE E, et al. Contact graph routing in DTN space networks: overview, enhancements and performance [J]. IEEE Communications Magazine, 2015, 53(3):38-46.

[16] BURLEIGH S. Contact graph routing, IRTF, Internet-Draft draft-burleigh-dtnrg-cgr-01, Experimental [EB/OL]. (2010-07-08) [2016-07-20]. https://tools.ietf.org/html/draft-burleigh-dtnrg-cgr-01.

(編輯：魏琴芳)

Contact plan based the shortest path optimization algorithm in satellite time-varying networks

DAI Cuiqin, LI Jian, TANG Huang

(Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P. R. China)

Aiming at the problem that Dijkstra shortest path algorithm cannot always ensure the optimal path in satellite time-varying topological network, this paper proposes a shortest path algorithm based on CP (CP-Dijkstra) by considering the determinacy of satellite node movement, researching and analyzing the periodicity dynamic change of satellite network topology. In LEO satellite systems, firstly dynamic CP is formed according to the time-varying connection of inter satellite links at different time. And then, the satellite node checks whether the CP is updated or not to chooses different methods to deal with the message: When the CP is not updated, the message will be forwarded with the shortest path calculated by the previous node; otherwise, the node will calculate a new shortest path to the destination node according to the CP at the present time, until the message is successfully forwarded to the destination node. With this scheme, a series of path where the message has gone through is named the shortest path. Simulation results show that the CP-Dijkstra algorithm can not only improve the throughput of the network, but also effectively reduce the average delay and packet loss probability compared with the commonly used DVTR algorithm in the satellite time-varying network.

satellite time-varying network; the shortest path algorithm; contact plan; throughput; packet loss probability

10.3979/j.issn.1673-825X.2017.01.005

2016-08-02

2016-12-10 通訊作者： 戴翠琴 daicq@cqupt.edu.cn

國家自然科學(xué)基金(61601075);重慶市科委自然科學(xué)基金(cstc2016jcyjA0174);重慶市教委自然科學(xué)基金(KJ1500440);長江學(xué)者和創(chuàng)新團(tuán)隊發(fā)展計劃(IRT16R72)

Foundation Items：The National Natural Science Foundation of China (61601075); The Natural Science Foundation Project of CQ CSTC (cstc2016jcyjA0174); The Scientific and Technological Research Program of Chongqing Municipal Education Commission (KJ1500440); The Program for Changjiang Scholars and Innovative Research Team in University (IRT16R72)

TN929.5

A

1673-825X(2017)01-0029-07

戴翠琴(1976-)，女，寧夏固原人，副教授，主要研究方向為寬帶無線通信網(wǎng)絡(luò)關(guān)鍵技術(shù)。E-mail 地址：daicq@cqupt.edu.cn

李 劍(1992-)，男，安徽安慶人，碩士生，主要研究方向為衛(wèi)星通信中的路由算法。E-mail 地址：562925078@qq.com

唐 煌(1993-)，男，重慶渝北人，碩士生，主要研究方向為衛(wèi)星時變網(wǎng)絡(luò)中的路由算法優(yōu)化。E-mail地址:449325126@qq.com