基于隨機(jī)時(shí)變圖的時(shí)間確定性網(wǎng)絡(luò)路由算法

王鵬，張修社,2，索龍，史可懿

（1.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2.中國電子科技集團(tuán)公司第二十研究所，陜西 西安 710071)

1 引言

天地一體化信息網(wǎng)絡(luò)是科技創(chuàng)新2030 重大工程項(xiàng)目，支持全球時(shí)空連續(xù)通信，具有“全球覆蓋、隨遇接入、按需服務(wù)以及安全可信”的特點(diǎn)。除傳統(tǒng)通信業(yè)務(wù)外，該網(wǎng)絡(luò)還可對氣象、環(huán)境與災(zāi)害監(jiān)測、資源勘察、地形測繪等空間任務(wù)提供通信服務(wù)，并且可提供覆蓋全球的寬帶接入服務(wù)[1]。天地一體化信息網(wǎng)絡(luò)由天基骨干網(wǎng)、天基接入網(wǎng)以及地面互聯(lián)網(wǎng)和移動(dòng)互聯(lián)網(wǎng)聚合而成。其中，天基網(wǎng)絡(luò)鏈路斷續(xù)連通且網(wǎng)絡(luò)業(yè)務(wù)隨機(jī)占用，網(wǎng)絡(luò)拓?fù)浜玩溌窌r(shí)變；地面網(wǎng)絡(luò)部分由于網(wǎng)絡(luò)共享，海量業(yè)務(wù)隨機(jī)占用，也為鏈路資源時(shí)變的網(wǎng)絡(luò)。因此，天地一體化網(wǎng)絡(luò)是典型的時(shí)變網(wǎng)絡(luò)。近年來，隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，電氣和電子工程師協(xié)會(huì)時(shí)間敏感網(wǎng)絡(luò)工作組（IEEE TSN,Institute of Electrical and Electronics Engineers time-sensitive networking）[2]、國際互聯(lián)網(wǎng)工程任務(wù)組確定性網(wǎng)絡(luò)工作組（IETF DetNet,Internet Engineering Task Force deterministic networking）[3]、第三代合作伙伴計(jì)劃（3GPP,3rd Generation Partnership Project）[4]紛紛啟動(dòng)了時(shí)間確定性網(wǎng)絡(luò)的研究工作，如何保障業(yè)務(wù)的確定性時(shí)延也成為最近的研究熱點(diǎn)。基于此，如何為時(shí)變的天地一體化網(wǎng)絡(luò)提供時(shí)間確定性的通信服務(wù)[5]，已成為空間信息網(wǎng)絡(luò)面臨的又一挑戰(zhàn)。

事實(shí)上，國內(nèi)外學(xué)者提出了許多高效的路由算法來降低業(yè)務(wù)時(shí)延。比如互聯(lián)網(wǎng)開放式最短路徑優(yōu)先協(xié)議中的Dijkstra 路由算法[6]，采用貪心策略獲取網(wǎng)絡(luò)中端到端的最短時(shí)延；國際空間數(shù)據(jù)系統(tǒng)咨詢委員會(huì)（CCSDS,Consultative Committee for Space data Systems）組織提出調(diào)度感知包路由（SABR,schedule aware bundle routing）協(xié)議，其中所采用的連通圖路由（CGR,contact graph routing）策略，可計(jì)算時(shí)變網(wǎng)絡(luò)中業(yè)務(wù)最后1 bit 最早到達(dá)目的節(jié)點(diǎn)的路徑，并且該路由算法已在星上完成了實(shí)驗(yàn)[7]。盡管這2 種算法已被廣泛認(rèn)可，路由表計(jì)算時(shí)未考慮網(wǎng)絡(luò)資源自身的隨機(jī)特性。此外，對于多路徑路由算法，文獻(xiàn)[8]提出了靜態(tài)網(wǎng)絡(luò)中基于增廣路徑方法的端到端最大流算法。與之對應(yīng)，文獻(xiàn)[9]提出了基于存儲時(shí)間聚合圖的時(shí)變網(wǎng)絡(luò)最大流算法，可充分挖掘網(wǎng)絡(luò)的傳輸潛力，求解出網(wǎng)絡(luò)端到端最大流。然而，上述經(jīng)典的路由方法未充分考慮網(wǎng)絡(luò)資源隨機(jī)特性，導(dǎo)致業(yè)務(wù)端到端時(shí)延有長尾效應(yīng)，網(wǎng)絡(luò)時(shí)延保障能力弱。

為充分說明鏈路隨機(jī)性帶來的影響，用一個(gè)簡單的例子來說明。如圖1 所示，給定4 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，鏈路權(quán)重上的2 個(gè)值分別表示鏈路的速率和滿足該速率的最大概率。假設(shè)各鏈路速率的概率分布獨(dú)立，當(dāng)大小為100 的數(shù)據(jù)需從S 傳到D，且需要在3 個(gè)時(shí)間單位內(nèi)完成傳輸時(shí)，Dijkstra/CGR 算法未考慮鏈路的隨機(jī)特性，會(huì)選用容量最大的路徑S→A→D，如圖1(b)所示，則端到端時(shí)延為2 個(gè)單位時(shí)間的概率為0.25。然而，若考慮路徑S→B→D，則路徑以0.81 的概率保障端到端時(shí)延為2.5 個(gè)單位時(shí)間。顯然，若缺乏對S→A→D 隨機(jī)屬性的刻畫，若準(zhǔn)確獲取當(dāng)概率為0.81 時(shí)，選擇哪條路徑具有更優(yōu)的時(shí)延性能。所以對于節(jié)點(diǎn)間鏈路大部分為無線鏈路的空間信息網(wǎng)絡(luò)，如何充分考慮鏈路的隨機(jī)性，求解最大概率的時(shí)延保障，是亟須求解的問題。

圖1 概率圖路徑選擇

實(shí)際上，鏈路的隨機(jī)性在很多場景中都得到了考慮。文獻(xiàn)[10]根據(jù)鏈路對數(shù)據(jù)分組的成功送達(dá)率制定業(yè)務(wù)在當(dāng)前節(jié)點(diǎn)向每個(gè)鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率，并依據(jù)此概率進(jìn)行路由；文獻(xiàn)[11]研究了隨機(jī)網(wǎng)絡(luò)給定源匯節(jié)點(diǎn)間的連通性確定問題，同樣以鏈路的連通概率為依據(jù)進(jìn)行計(jì)算；隨機(jī)車輛路由問題[12]同樣考慮了鏈路的隨機(jī)費(fèi)用特性。上述文獻(xiàn)雖然都對鏈路的隨機(jī)特性有所考慮，但是主要體現(xiàn)在靜態(tài)網(wǎng)絡(luò)鏈路的概率連通上，未充分考慮時(shí)變場景中鏈路資源的隨機(jī)特性。

因此，為解決上述問題，首先將時(shí)變網(wǎng)絡(luò)中最大概率時(shí)延保障路由計(jì)算問題建模為非線性規(guī)劃問題。為解決該問題，提出了隨機(jī)時(shí)變圖模型，對鏈路可用傳輸時(shí)間的隨機(jī)特性進(jìn)行表征。并且，對時(shí)變的網(wǎng)絡(luò)拓?fù)湟约岸嗑S資源進(jìn)行刻畫，支持多維資源的聯(lián)合調(diào)度。在此基礎(chǔ)上，基于段路由（SR,segment routing）可對不同業(yè)務(wù)設(shè)計(jì)不同傳輸路徑的特性，設(shè)計(jì)了面向業(yè)務(wù)需求的多項(xiàng)式時(shí)間的最大概率時(shí)延保障路由算法，給出了樣例，詳細(xì)闡述了該算法的運(yùn)行過程。最后，證明了算法的最優(yōu)性并分析了算法的復(fù)雜度。

2 問題建模

考慮一個(gè)天地一體化網(wǎng)絡(luò)包含衛(wèi)星集合S和地面站集合G，其中，衛(wèi)星集合S={S1,…,SN]包含N顆衛(wèi)星，地面站集合G={G1,…,GP]包含P個(gè)地面站。考慮待傳輸任務(wù)集合M，且M={M1,…,MQ}包含Q個(gè)任務(wù)。特別地，對于任意任務(wù)Mi∈M，采用四元組分別描述生成任務(wù)i的衛(wèi)星Sj、業(yè)務(wù)量vi、任務(wù)釋放時(shí)間ri、任務(wù)截止日期di。由于地面站間被地面高速網(wǎng)絡(luò)連通，因此所有待傳輸任務(wù)的目的地可以為任意地面站。對于任意任務(wù)Mi∈M，目標(biāo)是從ri開始，在任務(wù)截止日期di前將其所有的業(yè)務(wù)量vi從衛(wèi)星Sj借助其他衛(wèi)星的中繼傳輸傳回地面站。

針對衛(wèi)星網(wǎng)絡(luò)的時(shí)變特性，由于衛(wèi)星飛行軌跡確定，衛(wèi)星間以及衛(wèi)星與地面站間的可通信時(shí)間窗可以根據(jù)軌道模型提前獲取。因此，給定時(shí)間范圍T，可將其拆分成h個(gè)小時(shí)間段T={T1,…,Th}，使得在每個(gè)小時(shí)間段內(nèi)，網(wǎng)絡(luò)拓?fù)溥B接不再發(fā)生變化。定義任意小時(shí)段Ti∈T時(shí)長為|Ti|。

事實(shí)上，在任意一個(gè)時(shí)間段Ti∈T內(nèi)，由于業(yè)務(wù)的隨機(jī)占用，鏈路被占用的通信時(shí)間窗長度服從某個(gè)隨機(jī)分布。因此，在該時(shí)段內(nèi)，剩余的可用時(shí)間窗長度同樣服從隨機(jī)分布。假設(shè)網(wǎng)絡(luò)中業(yè)務(wù)數(shù)目足夠多，根據(jù)大數(shù)定律，可假設(shè)鏈路的可用時(shí)間窗服從高斯分布，且不同鏈路之間獨(dú)立分布。因此可將歷史流量信息和路由策略作為輸入，利用神經(jīng)網(wǎng)絡(luò)[13]、深度學(xué)習(xí)[14]等人工智能技術(shù)，預(yù)測未來的鏈路流量占用情況，進(jìn)而獲取鏈路各時(shí)隙的概率信息。當(dāng)前工作主要關(guān)注在鏈路隨機(jī)信息已知的情況下如何構(gòu)建端到端的確定性時(shí)間路由。

且需滿足如下約束。

1) 節(jié)點(diǎn)(Sj≠A,D)流守恒約束

在第一個(gè)時(shí)段，從傳輸鏈路流入Sj的流值的和與從傳輸鏈路和存儲鏈路流出Sj的流值的和相等。在任意一個(gè)時(shí)段（非第一個(gè)或最后一個(gè)時(shí)段），從傳輸鏈路和存儲鏈路流入Sj的流值的和與從傳輸鏈路和存儲鏈路流出Sj的流值的和相等。在最后一個(gè)時(shí)段，從傳輸鏈路和存儲鏈路流入Sj的流值的和與從傳輸鏈路流出Sj的流值相等。因此，將每個(gè)時(shí)段的流守恒公式相加，可得時(shí)間T內(nèi)的流守恒公式為

式(3)為在整個(gè)時(shí)段T內(nèi)，從每個(gè)時(shí)段的傳輸鏈路流入Sj的流值的和與每個(gè)時(shí)段流出Sj的流值的和相等。此外，對于源節(jié)點(diǎn)A 和目的節(jié)點(diǎn)D，在時(shí)間范圍T內(nèi)，有

即從源節(jié)點(diǎn)A 流出的數(shù)據(jù)流應(yīng)與流進(jìn)目的節(jié)點(diǎn)D的流值相等。

3) 業(yè)務(wù)時(shí)延約束

對于任意任務(wù)Mi∈M，其屬性為假設(shè)該任務(wù)所規(guī)劃路徑上的所有鏈路的所處時(shí)段的集合為Δi，且時(shí)段集合Δi中的最早時(shí)段為minΔi，最后一個(gè)時(shí)段為maxΔi。則為該業(yè)務(wù)規(guī)劃的路徑上的流值和應(yīng)該滿足

此外，規(guī)劃路徑的時(shí)間段應(yīng)在其時(shí)延需求范圍內(nèi)。具體地，為任務(wù)Mi規(guī)劃路徑所有鏈路所處的最早時(shí)間不早于任務(wù)的釋放（開始）時(shí)間，路徑中所有鏈路的最晚時(shí)間不能大于任務(wù)的截止時(shí)間，即

由于問題式(1)的優(yōu)化目標(biāo)為非線性約束，而其他約束條件均為線性約束，因此該最大概率保障業(yè)務(wù)時(shí)延的路由問題為非線性規(guī)劃問題。

3 系統(tǒng)模型

本節(jié)為解決該非線性規(guī)劃問題，提出了隨機(jī)時(shí)變圖模型支持將該問題映射為路由問題。首先，對時(shí)變的網(wǎng)絡(luò)拓?fù)溥M(jìn)行了建模。然后，考慮了鏈路資源的隨機(jī)特性，利用一階矩和二階矩對鏈路資源的隨機(jī)性進(jìn)行了建模，構(gòu)建了隨機(jī)時(shí)變圖模型。最后，通過示例對映射后的路由問題進(jìn)行了描述。

3.1 拓?fù)浔碚鲌D模型

考慮一個(gè)網(wǎng)絡(luò)包含衛(wèi)星集合S和地面站集合G，其中，衛(wèi)星集合S={S1,…,SN]包含N顆衛(wèi)星，地面站集合G={G1,…,GP]包含P個(gè)地面站，待傳輸任務(wù)集合M={M1,…,MQ}包含Q個(gè)任務(wù)，可以用快照刻畫出h個(gè)時(shí)段的節(jié)點(diǎn)間連通關(guān)系。另外，一個(gè)時(shí)段的任務(wù)可借助該節(jié)點(diǎn)內(nèi)的存儲在下一時(shí)段進(jìn)行傳輸，從而聯(lián)合利用多時(shí)段的存儲資源。對于任一衛(wèi)星Si∈S，若其屬于第k個(gè)快照，將其定義為。因此，可以將相鄰2 個(gè)快照中同一衛(wèi)星的2 個(gè)節(jié)點(diǎn)用有向鏈路相連，且方向指向時(shí)間增大的方向。網(wǎng)絡(luò)拓?fù)淇梢杂糜邢驁DG=(V,E)來表示，其中點(diǎn)集合V包含了所有時(shí)段的衛(wèi)星節(jié)點(diǎn)，邊集合E包含了所有快照內(nèi)的傳輸鏈路以及快照間的存儲鏈路。

為了更清楚地闡述拓?fù)涞膱D模型表征過程，構(gòu)建一個(gè)簡化的4 無人機(jī)網(wǎng)絡(luò)，如圖2 所示。首先將無人機(jī)網(wǎng)絡(luò)的時(shí)間段T分成3 個(gè)小時(shí)段,使每個(gè)時(shí)段內(nèi)網(wǎng)絡(luò)拓?fù)洳蛔儭o人機(jī)網(wǎng)絡(luò)在3 個(gè)小時(shí)段內(nèi)有不同的拓?fù)洌謩e采用節(jié)點(diǎn)和鏈路刻畫每個(gè)快照的拓?fù)洹Ｗ匀坏兀粺o人機(jī)在相鄰2 個(gè)快照內(nèi)有2 個(gè)節(jié)點(diǎn)，用有向鏈路相連。給定無人機(jī)S3，可將其第一個(gè)快照的節(jié)點(diǎn)與第二個(gè)快照內(nèi)的節(jié)點(diǎn)相連，從而獲得其存儲鏈路。這種表征方式支持存儲攜帶轉(zhuǎn)發(fā)模式，比如將在第二個(gè)時(shí)段將數(shù)據(jù)傳輸給，通過將數(shù)據(jù)緩存給，最終可在第三個(gè)時(shí)段將數(shù)據(jù)傳給

圖2 網(wǎng)絡(luò)拓?fù)鋱D模型表征

3.2 鏈路資源的隨機(jī)性表征

對于網(wǎng)絡(luò)拓?fù)銰=(V,E)，邊集合E中的傳輸鏈路具有傳輸速率、傳播時(shí)延等屬性。而存儲鏈路屬性為節(jié)點(diǎn)的可用存儲空間。事實(shí)上，由于業(yè)務(wù)的隨機(jī)占用，鏈路可用傳輸時(shí)間服從一定概率分布，可根據(jù)鏈路速率的歷史統(tǒng)計(jì)信息，獲取一階原點(diǎn)矩來刻畫在一個(gè)時(shí)間段內(nèi)鏈路可用時(shí)間的均值，計(jì)算二階中心矩來刻畫可用時(shí)間的方差。基于此，假設(shè)鏈路速率分布服從高斯分布，可知鏈路在不同時(shí)段內(nèi)可用時(shí)間的概率分布。具體地，對于任意鏈路表示鏈路在時(shí)段Tk內(nèi)可用時(shí)間隨機(jī)變量，表示鏈路在時(shí)段Tk內(nèi)可用時(shí)間一階原點(diǎn)矩-均值，表示鏈路時(shí)段Tk內(nèi)可用時(shí)間二階中心距-方差。對于任意節(jié)點(diǎn)表示其能從第k個(gè)快照向第k+1 個(gè)快照緩存的容量均值，由于存儲容量為定值，所以其方差為0。因此，對于圖2 所示網(wǎng)絡(luò)，可獲取其隨機(jī)時(shí)變圖模型如圖3所示。

圖3 隨機(jī)時(shí)變圖模型

3.3 問題映射

事實(shí)上，對于任務(wù)?Mi∈M，由于其任務(wù)釋放時(shí)間和截止時(shí)間已給定，可通過加入任務(wù)需求鏈路來表征任務(wù)的時(shí)延需求。例如，任務(wù)M1的釋放時(shí)段是第一個(gè)小時(shí)段，截止時(shí)間是第二個(gè)小時(shí)段，且其源節(jié)點(diǎn)為S1，目的節(jié)點(diǎn)為S4。則可以在第一個(gè)小時(shí)段插入一個(gè)輔助源節(jié)點(diǎn)與相連，作為任務(wù)M1的釋放鏈路。相似地，可以在第二個(gè)小時(shí)段插入一個(gè)輔助目的節(jié)點(diǎn)與相連，作為任務(wù)結(jié)束鏈路。業(yè)務(wù)的時(shí)延需求表征如圖4 所示。因此，任務(wù)M1的時(shí)延保障路徑查找問題可轉(zhuǎn)化為查找源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑。

圖4 業(yè)務(wù)的時(shí)延需求表征

基于圖 5 針對業(yè)務(wù)M1的概率圖模型G=(V,E)，假設(shè)M1需在前h個(gè)時(shí)段內(nèi)完成。問題式(8)的決策變量可由決定每條鏈路的流量大小轉(zhuǎn)變?yōu)槭欠襁x擇該鏈路傳輸。定義鏈路決策變量xe為是否選擇鏈路e∈E的0/1 變量。xe=1 表示選擇鏈路e來進(jìn)行傳輸，xe=0 表示不選擇鏈路e。特別地，對于任意傳輸鏈路和存儲鏈路其鏈路決策變量分別為和。鏈路e滿足任務(wù)需求的概率為Pe，則問題式(1)可轉(zhuǎn)化為

圖5 業(yè)務(wù)M1的概率圖模型

其中，xe∈{0,1}。

此時(shí)，業(yè)務(wù)最大概率時(shí)延保障路由問題可被轉(zhuǎn)化為式(9)，該問題為從所有源節(jié)點(diǎn)到目的節(jié)點(diǎn)滿足傳輸需求的路徑中找出最大概率滿足需求的路徑。所以對于不選擇傳輸?shù)逆溌罚滏溌犯怕蕦ψ罱K結(jié)果沒有影響，將其概率設(shè)為1。此外，因?yàn)橹恍枵乙粭l路徑，所以從源節(jié)點(diǎn)出發(fā)的鏈路中只能選擇一條鏈路，同理，所有指向目的節(jié)點(diǎn)的鏈路中也只能選擇一條。

3.4 問題描述

為清楚地解釋問題式(9)，選取圖3 中的前2 個(gè)時(shí)段，構(gòu)建了如圖6 所示的簡單網(wǎng)絡(luò)的圖模型。時(shí)間范圍T被拆分成了2 個(gè)時(shí)段且每個(gè)小時(shí)段長2 min。所有鏈路速率均為60。鏈路上標(biāo)注的數(shù)字為鏈路可用時(shí)間的均值和方差。由于網(wǎng)絡(luò)業(yè)務(wù)的隨機(jī)占用，例如圖6 中鏈路標(biāo)注(100,400)表示鏈路可用時(shí)間均值為100 s，方差為400 s2。若節(jié)點(diǎn)S1需要向S4傳輸4 800 單位數(shù)據(jù)，任務(wù)在第一時(shí)段產(chǎn)生，且需要在最多4 min 內(nèi)完成。則當(dāng)路徑與路徑中每條傳輸鏈路具有最小80 s 的可用傳輸時(shí)間時(shí)，可滿足任務(wù)的傳輸需求。但是每條傳輸鏈路可用時(shí)間均為隨機(jī)變量，且為高斯分布。根據(jù)鏈路速率均值和方差，鏈路能保障任務(wù)的傳輸需求（即提供最小80 s 可用傳輸時(shí)間）的最大概率分別為0.84、0.84、0.98、0.98。存儲鏈路方差為0，概率為1。則路徑與路徑能滿足業(yè)務(wù)傳輸需求的最大概率分別為0.84×1×0.84≈0.71 和0.98×1× 0.98≈0.96。顯然，雖然具有更高的確定性傳輸?shù)臄?shù)學(xué)期望，由于其方差較大，不能以大概率滿足業(yè)務(wù)傳輸需求。

圖6 簡單網(wǎng)絡(luò)的圖模型

4 最大概率保障業(yè)務(wù)時(shí)延路由算法

本節(jié)首先給出了最大概率業(yè)務(wù)時(shí)延保障路由算法，然后使用樣例解釋了算法的運(yùn)行步驟，最后證明了算法的最優(yōu)性并分析了算法的復(fù)雜度。

4.1 路由算法

為求解問題式(9)，給出了基于圖論的最大概率業(yè)務(wù)時(shí)延保障路由算法，如算法1 所示。

算法1最大概率業(yè)務(wù)時(shí)延保障路由算法

輸入任務(wù)Mi概率圖模型G=(V,E)，存儲鏈路與任務(wù)釋放鏈路和結(jié)束鏈路權(quán)重標(biāo)注為概率1，其他任務(wù)鏈路的權(quán)重為，源節(jié)點(diǎn)目的節(jié)點(diǎn)

輸出源節(jié)點(diǎn)到目的節(jié)點(diǎn)概率最大（權(quán)重積）最大的路徑

步驟1每個(gè)節(jié)點(diǎn)u∈V設(shè)置2 個(gè)參數(shù)，一個(gè)參數(shù)概率變量P(u) 表示從源節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑中能夠滿足業(yè)務(wù)Mi時(shí)延需求的最大概率，另一個(gè)參數(shù)F(u) 表示節(jié)點(diǎn)u∈V的最大概率路徑的前一跳節(jié)點(diǎn)。初始時(shí)，=1，且P(u)=0,u∈V,u≠此外，源節(jié)點(diǎn)前一跳節(jié)點(diǎn)為其本身，其他節(jié)點(diǎn)前一跳節(jié)點(diǎn)為空。

步驟2設(shè)置 2 個(gè)點(diǎn)集集合S和S′，且S∪S′=V。初始時(shí)S=?，S′=V。

步驟3當(dāng)S≠V時(shí)，尋找S′中P值最大的節(jié)點(diǎn)u=argmax{P(u)|u∈S′}。將節(jié)點(diǎn)u從S′中刪除并將其加入集合S。對于集合S′中節(jié)點(diǎn)u的每個(gè)鄰居節(jié)點(diǎn)v，若有P(v)＜P(u)Pu,v，則P(v)=P(u)Pu,v且F(v)=u。重復(fù)該步驟直到S=V。其中，Pu,v表示鏈路速率大于滿足業(yè)務(wù)傳輸需求的最小速率的概率。

算法1 的核心思想是采用貪心策略，利用集合S′記錄當(dāng)前節(jié)點(diǎn)，采用集合S記錄所有當(dāng)前節(jié)點(diǎn)中源節(jié)點(diǎn)能夠在最大概率保障時(shí)延的情況下到達(dá)的節(jié)點(diǎn)。初始時(shí)S′節(jié)點(diǎn)集合為集合V。不斷從S′中找出概率值最大的節(jié)點(diǎn)，將該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行概率更新操作，并將該節(jié)點(diǎn)從S′中取出加入S中。這種層層更新的策略能夠保障最終得到的路徑為最大概率路徑。

所提路由算法由SR 協(xié)議實(shí)現(xiàn)，該協(xié)議只有路由源節(jié)點(diǎn)需要獲取網(wǎng)絡(luò)的全局信息進(jìn)行路由計(jì)算，其他節(jié)點(diǎn)只需知曉網(wǎng)絡(luò)的基本連通關(guān)系即可。由于衛(wèi)星沿固定軌跡運(yùn)動(dòng)，每顆衛(wèi)星知曉所有網(wǎng)絡(luò)中衛(wèi)星的軌跡參數(shù)，因此每顆衛(wèi)星可計(jì)算出任意時(shí)刻任意2 顆衛(wèi)星間可否進(jìn)行通信（即2 顆衛(wèi)星間的鏈路是否連通）。此外，對于網(wǎng)絡(luò)狀態(tài)信息，地面測控中心可實(shí)時(shí)監(jiān)控網(wǎng)絡(luò)鏈路狀態(tài)信息，可根據(jù)歷史鏈路信息與路由策略，預(yù)測出未來時(shí)段的鏈路狀態(tài)信息，并可通過地面測控網(wǎng)絡(luò)將該信息上注給SR 協(xié)議中有限個(gè)路由源節(jié)點(diǎn)。

根據(jù)網(wǎng)絡(luò)中鏈路權(quán)重類型的不同，路徑可分為不同類型。當(dāng)鏈路權(quán)重為時(shí)延、費(fèi)用、代價(jià)等時(shí)，所求路徑為加性權(quán)重最小路徑，即所求路徑滿足在所有源到目的節(jié)點(diǎn)的路徑中鏈路權(quán)重和最小，Dijkstra 算法可直接求解該類路徑；當(dāng)鏈路權(quán)重為本文中的成功概率、誤碼率等時(shí)，所求路徑為乘性最大路徑，即所有路徑中鏈路權(quán)重積最大的路徑。Dijkstra 算法無法直接求解該類路徑，可通過將每條鏈路的權(quán)重轉(zhuǎn)化為，再利用Dijkstra 算法求解。當(dāng)鏈路權(quán)重為帶寬（即鏈路速率）時(shí)，所求路徑為凹性最大路徑，即所有路徑中鏈路最小權(quán)重值最大的路徑。Dijkstra 算法無法直接求解乘性與凹性最大路徑。

本文所提算法可直接求解乘性最大路徑，不需要進(jìn)行權(quán)重轉(zhuǎn)換與計(jì)算，可節(jié)省路由協(xié)議的計(jì)算和存儲開銷。此外，對于凹性最大路徑的求解，僅需將所提算法步驟 3 中的判斷操作變?yōu)槿鬚(v) ＜min{P(u),Pu,v]，則有P(v)=min{P(u),Pu,v]，即可實(shí)現(xiàn)凹性最大路徑的求解，其中P(u) 為源節(jié)點(diǎn)到節(jié)點(diǎn)u所有路徑中的最大凹性權(quán)重值（如最大帶寬），Pu,v為鏈路(u,v)的權(quán)重值，且該凹性路徑求解具有最優(yōu)性。所提變形Dijkstra 算法彌補(bǔ)了原始Dijkstra 算法計(jì)算乘性和凹性路徑的空白。

4.2 樣例說明

為了清晰地闡述算法的運(yùn)行過程，圖7 給出了算法的運(yùn)行樣例。首先，圖7(a)刻畫了簡單的網(wǎng)絡(luò)拓?fù)洌瑯I(yè)務(wù)M1需要從節(jié)點(diǎn)S1傳輸?shù)焦?jié)點(diǎn)S4，該傳輸任務(wù)需要在2 個(gè)時(shí)段內(nèi)完成。為保證算法求出的路徑滿足業(yè)務(wù)時(shí)延需求。在第一個(gè)時(shí)段插入了業(yè)務(wù)釋放鏈路，并在第二個(gè)時(shí)段插入了業(yè)務(wù)結(jié)束鏈路。算法的目標(biāo)為尋找到的路徑中最大概率保障業(yè)務(wù)時(shí)延的路徑。

圖7 算法運(yùn)行樣例

4.3 最優(yōu)性證明和復(fù)雜度分析

引理1算法1 運(yùn)行時(shí)，S′中每個(gè)節(jié)點(diǎn)加入S時(shí)都已找到最大概率路徑，且該最大概率值為節(jié)點(diǎn)概率值。該路徑可由每個(gè)節(jié)點(diǎn)的上一跳節(jié)點(diǎn)屬性獲取。

證明采用歸納法證明。

第一次從S′向S中加入節(jié)點(diǎn)時(shí)所加節(jié)點(diǎn)為源節(jié)點(diǎn)本身，引理成立。

假設(shè)前k次從S′向S中加入節(jié)點(diǎn)時(shí)引理均成立，則在第k+1 次從S′向S中加入節(jié)點(diǎn)時(shí)引理仍成立。定義第k+1 次從S′加入S中的節(jié)點(diǎn)為u，則節(jié)點(diǎn)u為集合S′中概率值最大的節(jié)點(diǎn)。用反證法證明。假設(shè)存在一條從源節(jié)點(diǎn)到節(jié)點(diǎn)u的概率值更大的路徑l，該路徑的概率值Pl大于節(jié)點(diǎn)u的概率值P(u)。路徑l包含除節(jié)點(diǎn)u外至少一個(gè)在S′中的節(jié)點(diǎn)。定義該節(jié)點(diǎn)為節(jié)點(diǎn)x，且節(jié)點(diǎn)x的上一跳節(jié)點(diǎn)為y。節(jié)點(diǎn)u的路徑情況如圖8 所示，由源節(jié)點(diǎn)經(jīng)由F(u)到達(dá)節(jié)點(diǎn)u的路徑為算法所找路徑。由源節(jié)點(diǎn)經(jīng)由節(jié)點(diǎn)y和節(jié)點(diǎn)x到達(dá)節(jié)點(diǎn)u的路徑為假設(shè)存在的概率更高路徑，即路徑l。根據(jù)算法1 可知，在第k+1 次從集合S′中之所以選擇節(jié)點(diǎn)u，是因?yàn)榧蟂′的所有節(jié)點(diǎn)中u概率值最大。所以有P(u)≥P(x)。由于x到u的路徑概率，因此路徑l概率為，與假設(shè)矛盾，故引理得證。

圖8 節(jié)點(diǎn)u 的路徑情況

引理2對于n個(gè)節(jié)點(diǎn)、m條邊的隨機(jī)圖模型，算法1 的時(shí)間復(fù)雜度在網(wǎng)絡(luò)稀疏時(shí)為O(n2)，在網(wǎng)絡(luò)稠密時(shí)為O(m)。

證明算法1 執(zhí)行過程主要分為2 個(gè)步驟：1)集合V中的n個(gè)節(jié)點(diǎn)都要從集合S'中被挑選出來；2) 每個(gè)節(jié)點(diǎn)被挑選完后要判斷是否對節(jié)點(diǎn)的鄰居節(jié)點(diǎn)概率值進(jìn)行更新。針對步驟1)，每次挑選都要從S'中選出概率值最大的節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)。選擇了n次，復(fù)雜度為O(n2)。對于步驟2)，每個(gè)節(jié)點(diǎn)都會(huì)判斷其鄰居節(jié)點(diǎn)是否需要概率值更新，即圖中所有的邊都被執(zhí)行了判斷操作，所以總共執(zhí)行了O(m)次；因此算法復(fù)雜度為O(n2+m)。易知，在網(wǎng)絡(luò)稀疏時(shí)，有n2＞＞m，所以復(fù)雜度為O(n2)；在網(wǎng)絡(luò)稠密時(shí)，m=n(n-1)/2，此時(shí)算法復(fù)雜度為O(m)。證畢。

5 結(jié)束語

本文針對現(xiàn)有路由算法未考慮鏈路傳輸時(shí)間的隨機(jī)特征，提出了時(shí)變場景中表征鏈路隨機(jī)特性隨機(jī)時(shí)變圖模型。基于該圖模型，將最大概率保障業(yè)務(wù)時(shí)延的路徑選擇問題建模成非線性規(guī)劃問題，并且提出了最優(yōu)的多項(xiàng)式時(shí)間圖論解法。在未來工作中，將增加多業(yè)務(wù)隨機(jī)特性的表征，考慮如何最大概率地保障多業(yè)務(wù)的時(shí)間確定性路由問題。