戴翠琴，李 劍，唐 煌

(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

戴翠琴，李 劍，唐 煌

(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

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

0 引 言

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

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

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

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

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

(1)

(1)式中：V是衛(wèi)星節(jié)點(diǎn)的有窮非空集合；A是衛(wèi)星節(jié)點(diǎn)間的有限邊集；W表示衛(wèi)星節(jié)點(diǎn)vi和vj間的鏈路權(quán)值，可以用鏈路距離、時(shí)延或其他費(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é)點(diǎn)v0到目的節(jié)點(diǎn)vd的其中一條路徑，則路徑P的權(quán)值由 (2) 式得到，

(2)

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

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

(3)

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

(4)

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

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

(5)

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

2 CP-Dijkstra算法

2.1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真分析

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

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

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

圖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ò)場(chǎng)景中的吞吐量性能都增大，CP-Dijkstra算法稍為明顯，這是由于在衛(wèi)星節(jié)點(diǎn)高速移動(dòng)的情況下，即網(wǎng)絡(luò)拓?fù)漕l繁變化時(shí)，DVTR算法路由計(jì)算不一定準(zhǔn)確，且在短時(shí)間內(nèi)不能及時(shí)建立新的有效路由，從而導(dǎo)致在同一時(shí)刻，采用CP-Dijkstra算法的網(wǎng)絡(luò)在重負(fù)載情況下收到的信息數(shù)更多。同時(shí)，圖7和圖8也分別顯示了隨著衛(wèi)星運(yùn)行時(shí)間的變化，DVTR算法和CP-Dijkstra算法的吞吐量的變化情況。如圖所示，在同一時(shí)刻，DVTR算法的吞吐量性能總是低于CP-Dijkstra算法。這是由于DVTR算法采用的是靜態(tài)拓?fù)渎酚捎?jì)算方法，該方法不能準(zhǔn)確的處理鏈路切換問題，最短路徑算法在鏈路的連接發(fā)生變化后的計(jì)算結(jié)果不能完全適用，導(dǎo)致信息在轉(zhuǎn)發(fā)過程中不能通過計(jì)算得到的最短路徑轉(zhuǎn)發(fā)到下一跳而丟失，從而目的節(jié)點(diǎn)不能收到發(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種算法的平均時(shí)延性能，由圖9和圖10可知，在重負(fù)載網(wǎng)絡(luò)中，兩種算法的平均時(shí)延均有所增大，而DVTR算法的平均時(shí)延性能表現(xiàn)的更差，這是因?yàn)榫哂懈咚僖苿?dòng)特性的衛(wèi)星節(jié)點(diǎn)會(huì)導(dǎo)致鏈路的頻繁中斷，DVTR算法不能保證所有信息的轉(zhuǎn)發(fā)路徑在不同時(shí)刻一定處于連通狀態(tài)，從而使得源節(jié)點(diǎn)重新計(jì)算路由，導(dǎo)致部分節(jié)點(diǎn)不能及時(shí)處理消息，使得節(jié)點(diǎn)負(fù)載過重而丟棄信息造成更大的時(shí)延。圖9和圖10分別對(duì)DVTR算法和CP-Dijkstra算法的平均時(shí)延進(jìn)行了比較。當(dāng)運(yùn)行時(shí)間為0時(shí)，衛(wèi)星網(wǎng)絡(luò)中沒有產(chǎn)生任何信息，因此平均時(shí)延為0；隨著運(yùn)行時(shí)間的變化，網(wǎng)絡(luò)中信息數(shù)量會(huì)不斷增加，兩種算法的網(wǎng)絡(luò)的平均時(shí)延變化均穩(wěn)定在一定范圍內(nèi)。如圖所示，由于DVTR算法在星間鏈路頻繁切換時(shí)，計(jì)算的最短路徑不一定正確或是最優(yōu)，當(dāng)計(jì)算得到的最短路徑中的鏈路發(fā)生切換，信息不能及時(shí)轉(zhuǎn)發(fā)到下一跳，從而需要等待至少一個(gè)周期之后，才能將信息轉(zhuǎn)發(fā)到最短路徑中的下一跳節(jié)點(diǎn)，因此導(dǎo)致其平均時(shí)延要高于CP-Dijkstra算法。

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

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

4 結(jié)束語

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

[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ī)時(shí)變神經(jīng)網(wǎng)絡(luò)最短路徑算法[J].天津理工大學(xué)學(xué)報(bào),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)星時(shí)變拓?fù)渚W(wǎng)絡(luò)最短路徑算法研究[J]. 計(jì)算機(jī)學(xué)報(bào), 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);長(zhǎng)江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃(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-)，女，寧夏固原人，副教授，主要研究方向?yàn)閷拵o線通信網(wǎng)絡(luò)關(guān)鍵技術(shù)。E-mail 地址：daicq@cqupt.edu.cn

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

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