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

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

1 引言

天地一體化信息網(wǎng)絡(luò)是科技創(chuàng)新2030 重大工程項目，支持全球時空連續(xù)通信，具有“全球覆蓋、隨遇接入、按需服務(wù)以及安全可信”的特點。除傳統(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)和移動互聯(lián)網(wǎng)聚合而成。其中，天基網(wǎng)絡(luò)鏈路斷續(xù)連通且網(wǎng)絡(luò)業(yè)務(wù)隨機占用，網(wǎng)絡(luò)拓撲和鏈路時變；地面網(wǎng)絡(luò)部分由于網(wǎng)絡(luò)共享，海量業(yè)務(wù)隨機占用，也為鏈路資源時變的網(wǎng)絡(luò)。因此，天地一體化網(wǎng)絡(luò)是典型的時變網(wǎng)絡(luò)。近年來，隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，電氣和電子工程師協(xié)會時間敏感網(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]、第三代合作伙伴計劃（3GPP,3rd Generation Partnership Project）[4]紛紛啟動了時間確定性網(wǎng)絡(luò)的研究工作，如何保障業(yè)務(wù)的確定性時延也成為最近的研究熱點?；诖耍绾螢闀r變的天地一體化網(wǎng)絡(luò)提供時間確定性的通信服務(wù)[5]，已成為空間信息網(wǎng)絡(luò)面臨的又一挑戰(zhàn)。

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

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

圖1 概率圖路徑選擇

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

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

2 問題建模

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

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

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

且需滿足如下約束。

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

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

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

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

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

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

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

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

3 系統(tǒng)模型

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

3.1 拓撲表征圖模型

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

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

圖2 網(wǎng)絡(luò)拓撲圖模型表征

3.2 鏈路資源的隨機性表征

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

圖3 隨機時變圖模型

3.3 問題映射

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

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

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

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

其中，xe∈{0,1}。

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

3.4 問題描述

為清楚地解釋問題式(9)，選取圖3 中的前2 個時段，構(gòu)建了如圖6 所示的簡單網(wǎng)絡(luò)的圖模型。時間范圍T被拆分成了2 個時段且每個小時段長2 min。所有鏈路速率均為60。鏈路上標注的數(shù)字為鏈路可用時間的均值和方差。由于網(wǎng)絡(luò)業(yè)務(wù)的隨機占用，例如圖6 中鏈路標注(100,400)表示鏈路可用時間均值為100 s，方差為400 s2。若節(jié)點S1需要向S4傳輸4 800 單位數(shù)據(jù)，任務(wù)在第一時段產(chǎn)生，且需要在最多4 min 內(nèi)完成。則當(dāng)路徑與路徑中每條傳輸鏈路具有最小80 s 的可用傳輸時間時，可滿足任務(wù)的傳輸需求。但是每條傳輸鏈路可用時間均為隨機變量，且為高斯分布。根據(jù)鏈路速率均值和方差，鏈路能保障任務(wù)的傳輸需求（即提供最小80 s 可用傳輸時間）的最大概率分別為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ù)時延路由算法

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

4.1 路由算法

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

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

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

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

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

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

步驟3當(dāng)S≠V時，尋找S′中P值最大的節(jié)點u=argmax{P(u)|u∈S′}。將節(jié)點u從S′中刪除并將其加入集合S。對于集合S′中節(jié)點u的每個鄰居節(jié)點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é)點，采用集合S記錄所有當(dāng)前節(jié)點中源節(jié)點能夠在最大概率保障時延的情況下到達的節(jié)點。初始時S′節(jié)點集合為集合V。不斷從S′中找出概率值最大的節(jié)點，將該節(jié)點的鄰居節(jié)點進行概率更新操作，并將該節(jié)點從S′中取出加入S中。這種層層更新的策略能夠保障最終得到的路徑為最大概率路徑。

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

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

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

4.2 樣例說明

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

圖7 算法運行樣例

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

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

證明采用歸納法證明。

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

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

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

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

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

5 結(jié)束語

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