衛(wèi)星網(wǎng)絡(luò)動(dòng)態(tài)資源圖多QoS約束路由算法

梁超，楊力，潘成勝，，戚耀文

1．大連大學(xué) 通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，大連 116622

2．南京理工大學(xué) 自動(dòng)化學(xué)院，南京 210094

近年來(lái)，全球高中低軌衛(wèi)星通信，尤其是巨型低軌星座系統(tǒng)進(jìn)入井噴式發(fā)展階段［1］，衛(wèi)星的計(jì)算能力、存儲(chǔ)能力也逐漸變強(qiáng)，同時(shí)，基于衛(wèi)星網(wǎng)絡(luò)的應(yīng)用也越來(lái)越多并朝著多樣化的方向發(fā)展。路由技術(shù)作為衛(wèi)星網(wǎng)絡(luò)中的關(guān)鍵技術(shù)仍面臨很多問題，例如高動(dòng)態(tài)、高時(shí)延、局部擁塞等。因此，設(shè)計(jì)高效可靠的路由算法至關(guān)重要。

文獻(xiàn)［2］指出，路由協(xié)議有許多是為特定網(wǎng)絡(luò)設(shè)計(jì)的，呈現(xiàn)出不同的特性，因此，在研究路由算法時(shí)，需要考慮不同網(wǎng)絡(luò)環(huán)境所產(chǎn)生的影響。當(dāng)前衛(wèi)星網(wǎng)絡(luò)路由主要基于2種網(wǎng)絡(luò)模型，一種是基于離散時(shí)間片的虛擬拓?fù)淠Ｐ?，文獻(xiàn)［3］提出基于時(shí)間片分割的拓?fù)渖蓛?yōu)化算法得到抗毀性良好的拓?fù)浣Y(jié)構(gòu)，但當(dāng)有大量衛(wèi)星時(shí)，這種模式不可擴(kuò)展；另一種是基于虛擬節(jié)點(diǎn)的模型，該機(jī)制屏蔽了網(wǎng)絡(luò)的動(dòng)態(tài)性，同時(shí)簡(jiǎn)化了路由機(jī)制。基于虛擬節(jié)點(diǎn)的路由策略雖然能夠規(guī)避衛(wèi)星網(wǎng)絡(luò)的高動(dòng)態(tài)性問題，但這種方式忽略了虛擬節(jié)點(diǎn)與物理節(jié)點(diǎn)切換時(shí)所帶來(lái)的路徑失效問題。

路由問題是一個(gè)多目標(biāo)優(yōu)化問題，在網(wǎng)絡(luò)性能優(yōu)化方面，主要是以端到端時(shí)延、網(wǎng)絡(luò)吞吐量和數(shù)據(jù)包交付成功率等指標(biāo)為優(yōu)化目標(biāo)，研究者針對(duì)不同的優(yōu)化目標(biāo)提出了大量可行方案。文獻(xiàn)［4］提出了一種新穎的時(shí)間網(wǎng)絡(luò)模型來(lái)描繪大規(guī)模小型衛(wèi)星網(wǎng)絡(luò)的時(shí)變拓?fù)洳⑻岢隽艘环N高效的基于網(wǎng)格的最短路徑路由算法。文獻(xiàn)［5］提出了一種基于計(jì)劃拓?fù)涞难舆t約束路由機(jī)制算法，該算法基于預(yù)測(cè)的拓?fù)浣⒙酚杀聿⒁詴r(shí)延為約束條件進(jìn)行路由計(jì)算。文獻(xiàn)［6］提出了一種基于服務(wù)概率和有限副本的算法，基于轉(zhuǎn)發(fā)概率和衛(wèi)星剩余緩存選擇路徑。文獻(xiàn)［7］提出了一種基于星間鏈路狀態(tài)信息的路由算法，衛(wèi)星根據(jù)與相鄰衛(wèi)星的鏈路狀態(tài)信息和網(wǎng)絡(luò)拓?fù)錇槊恳惶龀雎酚蓻Q策。文獻(xiàn)［8］提出了一個(gè)聯(lián)合的時(shí)空路由算法框架，設(shè)計(jì)了一種多路徑路由算法。文獻(xiàn)［9］提出了一種基于網(wǎng)絡(luò)編碼的多徑協(xié)作路由協(xié)議，該方案采用非停止等待機(jī)制完成數(shù)據(jù)包的分批次傳輸。能量感知路由算法從能量的角度“驗(yàn)證”和“確認(rèn)”節(jié)點(diǎn)的有效性，并基于此設(shè)計(jì)了一種解決路由無(wú)效問題并繞過敏感節(jié)點(diǎn)的路由方案［10-11］。以上方案在縮短網(wǎng)絡(luò)傳輸時(shí)延，降低網(wǎng)絡(luò)控制開銷，提高網(wǎng)絡(luò)性能方面發(fā)揮了重要作用，但在流量突發(fā)情況下，網(wǎng)絡(luò)會(huì)發(fā)生擁塞，難以保障通信服務(wù)質(zhì)量（Quality of Service，QoS）。

為了緩解網(wǎng)絡(luò)擁塞，文獻(xiàn)［12］提出了一種隊(duì)列調(diào)度的虛擬拓?fù)溲舆t容忍網(wǎng)絡(luò)路由算法，該算法能夠較好地平衡空間通信網(wǎng)絡(luò)拓?fù)涓潞唾Y源消耗的影響。文獻(xiàn)［13］針對(duì)低軌衛(wèi)星網(wǎng)絡(luò)，提出了基于分段路由的負(fù)載均衡路由算法，基于擁塞指數(shù)在輕載區(qū)和重載區(qū)采用不同的方案計(jì)算路由。以上方案在負(fù)載均衡方面均體現(xiàn)了較好的性能，但當(dāng)網(wǎng)絡(luò)負(fù)載很高時(shí)在時(shí)延方面略有劣勢(shì)。文獻(xiàn)［14］提出了一種基于存儲(chǔ)時(shí)間聚合圖的多流最大化路由方案以保證任務(wù)的QoS。采用蟻群算法求解路由，并將QoS約束應(yīng)用于改進(jìn)啟發(fā)式算法，能夠滿足網(wǎng)絡(luò)業(yè)務(wù)的QoS需求［15-16］，文獻(xiàn)［17］討論了蟻群算法在路由問題中的應(yīng)用，并針對(duì)應(yīng)用中的問題提出了3種改進(jìn)策略。上述算法均在某些方面保證了通信的QoS需求，但忽略了網(wǎng)絡(luò)動(dòng)態(tài)切換帶來(lái)的影響。

針對(duì)拓?fù)渥兓瘜?dǎo)致的網(wǎng)絡(luò)更新期間可用路徑失效問題，文獻(xiàn)［18］提出的適應(yīng)拓?fù)渥兓膿砣钚』W(wǎng)絡(luò)更新策略降低了網(wǎng)絡(luò)擁塞。文獻(xiàn)［19］明確指出了低軌衛(wèi)星的切換問題，分析了衛(wèi)星運(yùn)行所引起的鏈路切換對(duì)路由計(jì)算的影響，表明接入衛(wèi)星的頻繁切換，必然導(dǎo)致原有轉(zhuǎn)發(fā)路徑失效，繼續(xù)在其上傳輸業(yè)務(wù)時(shí)將產(chǎn)生嚴(yán)重的數(shù)據(jù)包丟失現(xiàn)象，此時(shí)需要重新計(jì)算衛(wèi)星通信網(wǎng)絡(luò)的拓?fù)浜吐酚?。因此，將路由?jì)算和衛(wèi)星鏈路切換結(jié)合起來(lái)可以降低重路由所帶來(lái)的開銷。

綜上所述，雖然研究者為提高衛(wèi)星網(wǎng)絡(luò)QoS、緩解網(wǎng)絡(luò)擁塞做了大量研究，但在路由計(jì)算時(shí)均未考慮衛(wèi)星動(dòng)態(tài)切換造成的路徑失效問題。因此，本文基于虛擬節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)?，?gòu)建動(dòng)態(tài)資源圖，提出了一種虛擬節(jié)點(diǎn)動(dòng)態(tài)資源圖多QoS約束路由算法（Multi-QoS Constraints Routing Algorithm based on Dynamic Resource Graph of Virtual Nodes，DRGVN-QR），從而達(dá)到緩解網(wǎng)絡(luò)擁塞，提高網(wǎng)絡(luò)QoS的目的。首先，建立虛擬節(jié)點(diǎn)動(dòng)態(tài)資源圖和多目標(biāo)優(yōu)化模型，該模型同時(shí)考慮了節(jié)點(diǎn)的切換狀態(tài)、緩存以及鏈路的剩余帶寬、時(shí)延等信息；其次，利用蟻群算法建立多QoS約束計(jì)算模型求解目標(biāo)函數(shù)，為每個(gè)連接請(qǐng)求找到一段時(shí)間內(nèi)符合QoS約束的多條路徑，并討論了信息素?fù)]發(fā)系數(shù)的取值問題；最后，設(shè)計(jì)一種冪數(shù)加權(quán)公式選出一段時(shí)間范圍內(nèi)的最優(yōu)路徑。

1 系統(tǒng)模型

1.1 軟件定義衛(wèi)星網(wǎng)絡(luò)模型

將軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）應(yīng)用于衛(wèi)星網(wǎng)絡(luò)可以有效緩解星上資源有限、管理困難的問題。因此，本文將SDN應(yīng)用于低軌（Low Earth Orbit，LEO）衛(wèi)星網(wǎng)絡(luò)，SDN控制器部署在3顆地球靜止軌道（Geostationary Earth Orbit，GEO）衛(wèi)星和對(duì)應(yīng)的地面站，位于GEO的控制器負(fù)責(zé)收集其覆蓋區(qū)域的LEO衛(wèi)星節(jié)點(diǎn)的狀態(tài)信息，3個(gè)控制器協(xié)同工作獲取全局視圖，地面控制器與GEO控制器進(jìn)行信息交互并負(fù)責(zé)路由計(jì)算，圖1展示了由衛(wèi)星和地球站組成系統(tǒng)架構(gòu)，GEO層和地面站作為控制層，LEO層作為數(shù)據(jù)轉(zhuǎn)發(fā)層。

本文采用類銥星星座［20］作為衛(wèi)星網(wǎng)絡(luò)模型，假設(shè)星座中共有N個(gè)軌道平面，每個(gè)軌道M顆衛(wèi)星，則衛(wèi)星集群可表示為S=｛1，2…，n，n+1，…，2n，…，（m－1）n+1，…，mn｝，其中n代表軌道編號(hào)，m表示衛(wèi)星在軌道中的編號(hào)。星座的網(wǎng)絡(luò)拓?fù)溆尚情g鏈路（Inter-Satellite Link，ISL）構(gòu)成，除了位于反向縫的衛(wèi)星外，每顆衛(wèi)星均有4個(gè)ISL，即2個(gè)軌內(nèi)ISL和2個(gè)軌間ISL；而位于反向縫的衛(wèi)星只有1個(gè)軌間ISL，因此只有3個(gè)ISL。

圖1 系統(tǒng)架構(gòu)Fig. 1 System architecture

軌間ISLs長(zhǎng)度的計(jì)算公式為

式中：R為衛(wèi)星的軌道半徑。

軌內(nèi)ISLs長(zhǎng)度Lh的計(jì)算公式為

式中：lat為指軌內(nèi)ISLs所在的緯度。

為了適應(yīng)LEO衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化，本文采用基于虛擬節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浞绞剑鶕?jù)LEO衛(wèi)星網(wǎng)絡(luò)的初始狀態(tài)，將地球表面根據(jù)衛(wèi)星星座進(jìn)行區(qū)域劃分，每個(gè)區(qū)域?qū)?yīng)一顆衛(wèi)星，然后給每個(gè)區(qū)域分配一個(gè)邏輯地址〈o，s〉，o代表衛(wèi)星軌道編號(hào)，s代表軌道上的衛(wèi)星編號(hào)，然后根據(jù)邏輯地址生成網(wǎng)絡(luò)拓?fù)洌酚捎?jì)算總是基于此拓?fù)溥M(jìn)行。

1.2 虛擬節(jié)點(diǎn)動(dòng)態(tài)資源圖模型

基于虛擬節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)溥壿嫷刂冯m然固定，但物理節(jié)點(diǎn)時(shí)刻變化，在某一時(shí)刻邏輯節(jié)點(diǎn)與物理節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系需要進(jìn)行切換，這會(huì)導(dǎo)致虛擬節(jié)點(diǎn)和邏輯鏈路出現(xiàn)短暫甚至長(zhǎng)時(shí)間的中斷現(xiàn)象，如果在切換時(shí)刻進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)請(qǐng)求將無(wú)法按規(guī)劃路徑到達(dá)，并且切換后的虛擬節(jié)點(diǎn)資源情況變化很大，如果仍按原路徑進(jìn)行轉(zhuǎn)發(fā)將無(wú)法保障QoS需求。虛擬節(jié)點(diǎn)與物理節(jié)點(diǎn)的切換對(duì)轉(zhuǎn)發(fā)過程的影響如圖2所示，在圖2（a）中，t時(shí)刻源站向目的站發(fā)送業(yè)務(wù)請(qǐng)求，如果按t時(shí)刻計(jì)算路由，虛擬節(jié)點(diǎn)路徑為A→B→C，對(duì)應(yīng)的物理節(jié)點(diǎn)為1→2→3，在圖2（b）中，t+1時(shí)刻業(yè)務(wù)到達(dá)節(jié)點(diǎn)B即2號(hào)衛(wèi)星，此時(shí)虛擬節(jié)點(diǎn)與物理節(jié)點(diǎn)發(fā)生切換，虛擬節(jié)點(diǎn)C對(duì)應(yīng)衛(wèi)星2，此時(shí)如果仍進(jìn)行B→C的轉(zhuǎn)發(fā)，那么將無(wú)法到達(dá)目的站，而可以由2號(hào)衛(wèi)星直接交付給目的站。

因此，本文利用SDN控制器收集網(wǎng)絡(luò)的所有狀態(tài)信息，然后將節(jié)點(diǎn)切換時(shí)間和動(dòng)態(tài)變化的資源情況刻畫在各虛擬節(jié)點(diǎn)和邏輯鏈路上，其中虛擬節(jié)點(diǎn)與物理節(jié)點(diǎn)的切換時(shí)間可預(yù)測(cè)，同時(shí)假設(shè)節(jié)點(diǎn)和鏈路的其他資源信息也已經(jīng)通過預(yù)測(cè)獲得。基于此構(gòu)建出虛擬節(jié)點(diǎn)動(dòng)態(tài)資源圖（Dynamic Resource Graph of Virtual Nodes，DRGVN），即

圖2 節(jié)點(diǎn)切換過程Fig. 2 Node switching process

式中：V表示節(jié)點(diǎn) 集合；E表示星 間鏈路；T表示時(shí)間范圍；Sv(t)表示虛擬節(jié)點(diǎn)v與物理節(jié)點(diǎn)的切換狀態(tài)；Bu，v(t)表示鏈路(u，v)剩余帶寬；Dpu，v(t)表示鏈路(u，v)的傳輸時(shí)延；Bufv表示節(jié)點(diǎn)v的緩存大??；Uv(t)表示節(jié)點(diǎn)v在t時(shí)刻的緩存占用情況。虛擬節(jié)點(diǎn)動(dòng)態(tài)資源圖采用表1的形式存儲(chǔ)。

表1 動(dòng)態(tài)資源信息Table 1 Dynamic resource information

1.3 路徑代價(jià)優(yōu)化模型

本節(jié)利用上文中建立的虛擬節(jié)點(diǎn)動(dòng)態(tài)資源圖約束路徑的選取并計(jì)算路徑代價(jià)。路徑代價(jià)的計(jì)算主要考慮3個(gè)指標(biāo)，即跳數(shù)、傳播時(shí)延和總端到端時(shí)延［21］。本文考慮衛(wèi)星網(wǎng)絡(luò)的高動(dòng)態(tài)性因素和數(shù)據(jù)包在逐跳轉(zhuǎn)發(fā)過程中易發(fā)生不可預(yù)知的情況，在保證鏈路代價(jià)優(yōu)的前提下應(yīng)盡量選擇節(jié)點(diǎn)數(shù)量少的路徑，因此路徑代價(jià)通過端到端時(shí)延和跳數(shù)共同來(lái)計(jì)算，即

式中：Ps，d(t)表 示t時(shí) 刻 源 節(jié) 點(diǎn)s到目的節(jié)點(diǎn)d的路徑代價(jià)；ω1、ω2分別表示鏈路代價(jià)和路徑包含節(jié)點(diǎn)數(shù)的權(quán)值；hs，d表示路徑所包含的節(jié)點(diǎn)跳數(shù)；Ii，j(t)表 示 節(jié) 點(diǎn)i到 節(jié) 點(diǎn)j的 單 鏈 路 代 價(jià)，本 文 僅考 慮 傳 輸 時(shí) 延與 排 隊(duì) 時(shí) 延對(duì) 鏈 路代價(jià)的影響，即

式 中：Li，j表 示 路 徑 長(zhǎng) 度；c表 示 電 磁 波 傳 播 速 度；Qi，j表示隊(duì)列 長(zhǎng)度；rout表示 出隊(duì)速度。

本文用fi，j(t)表示t時(shí)刻節(jié)點(diǎn)i到節(jié)點(diǎn)j的流量，虛擬節(jié)點(diǎn)v與物理節(jié)點(diǎn)的切換狀態(tài)Sv(t)=1時(shí)表示未切換，Sv(t)=0時(shí)表示發(fā)生切換。在時(shí)延、切換狀態(tài)、帶寬和緩存的約束下，設(shè)計(jì)了多QoS目標(biāo)優(yōu)化模型，該模型的目標(biāo)是為每個(gè)源到目的的連接請(qǐng)求尋找一條路徑代價(jià)最小的路徑。因此，建立優(yōu)化模型的目標(biāo)函數(shù)為

約束條件

為約束（11）表示t時(shí)刻鏈路的可行流量需小于鏈路的剩余帶寬，約束（12）表示節(jié)點(diǎn)實(shí)際緩存需小于節(jié)點(diǎn)最大緩存；約束（13）表示t時(shí)刻節(jié)點(diǎn)不應(yīng)處于切換狀態(tài)。上述模型是一個(gè)多目標(biāo)優(yōu)化問題，這通常是一個(gè)NP難問題，第2節(jié)將對(duì)該模型進(jìn)行求解。

2 算法設(shè)計(jì)

蟻群優(yōu)化（Ant Colony Optimization， ACO）被用于為每個(gè)連接請(qǐng)求尋找最佳路徑，因?yàn)锳CO不僅具有獲得組合優(yōu)化問題最優(yōu)解的強(qiáng)大能力，而且已經(jīng)成功地應(yīng)用于解決LEO衛(wèi)星網(wǎng)絡(luò)中的路由問題。因此，本文使用ACO算法求解1.3節(jié)的目標(biāo)函數(shù)，求出一段時(shí)間內(nèi)多個(gè)時(shí)刻的最優(yōu)路徑集合，最后選出該時(shí)段路徑質(zhì)量最高的路徑。

2.1 基于動(dòng)態(tài)資源圖的節(jié)點(diǎn)集優(yōu)化

根據(jù)優(yōu)化目標(biāo)模型約束，不符合約束條件的節(jié)點(diǎn)和鏈路不能作為備選節(jié)點(diǎn)，因此本文基于DRGVN實(shí)現(xiàn)一種縮小螞蟻下一步節(jié)點(diǎn)集allowedk的算法，提前去除負(fù)載過重的鏈路實(shí)現(xiàn)負(fù)載均衡并提高算法收斂速度。具體實(shí)現(xiàn)方法如下：

首先，基于虛擬節(jié)點(diǎn)的邏輯拓?fù)鋱D生成拓?fù)渚仃嘒

式中：aij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離，當(dāng)aij=?1時(shí)，表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間無(wú)法建立直接的ISL；節(jié)點(diǎn)邏輯地址的求解為然后，根據(jù)拓?fù)渚仃嚺袛噫溌仿?lián)通狀態(tài)，根據(jù)DRGVN判斷節(jié)點(diǎn)切換狀態(tài)和QoS約束條件，將滿足條件的節(jié)點(diǎn)加入allowedk集合中。其中節(jié)點(diǎn)i到節(jié)點(diǎn)j的QoS約束為

式中：Imax表示單條鏈路所允許的最大代價(jià)。

優(yōu)化allowedk集合的具體實(shí)現(xiàn)如算法1所示。

2.2 動(dòng)態(tài)路徑選取

為使算法選取的路徑在滿足QoS約束的基礎(chǔ)上實(shí)現(xiàn)路徑代價(jià)最小的優(yōu)化目標(biāo)，基于文獻(xiàn)［17］的蟻群算法數(shù)學(xué)模型，本文將鏈路的剩余帶寬Bi，j(t)和鏈路代價(jià)Ii，j(t)作為計(jì)算選擇下一步節(jié)點(diǎn)概率的2個(gè)約束條件，則螞蟻k由當(dāng)前節(jié)點(diǎn)i轉(zhuǎn)移到下一節(jié)點(diǎn)j的概率對(duì)應(yīng)的啟發(fā)函數(shù)為

算法1 優(yōu)化allowedk集合算法

式中：ηij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j鏈路的能見度；λ1、λ2、λ3分別表示剩余帶寬、鏈路代價(jià)和節(jié)點(diǎn)剩余緩存的重要程度；Tij代表節(jié)點(diǎn)i到節(jié)點(diǎn)j邊上的信息素值；α表示信息素的相對(duì)權(quán)重；β表示能見度的相對(duì)重要性。

當(dāng)所有螞蟻都完成了一次迭代，需要更新路徑上的信息素值，信息素更新公式為

式中：ρ為 信息素 揮發(fā)系數(shù)；1?ρ為信 息素持 久程度表示螞蟻k從節(jié)點(diǎn)i到節(jié)點(diǎn)j留下的信息素增量；P為一個(gè)固定值，表示一只螞蟻一次尋路的信息素總量；Lk表示螞蟻k經(jīng)過的路徑長(zhǎng)度。

2.3 基于時(shí)延系數(shù)的信息素?fù)]發(fā)速度選取

由式（21）可知，螞蟻k未經(jīng)過的路徑上的信息素以一定速度ρ減少。ρ的數(shù)值如果太大，信息素?fù)]發(fā)速度過快，導(dǎo)致算法收斂速度慢，路徑選擇的時(shí)效性較低；ρ的數(shù)值如果太小，信息素?fù)]發(fā)速度慢，容易過早陷入停滯狀態(tài)，無(wú)法選出最優(yōu)路徑。因此，根據(jù)路由的時(shí)延QoS需求選擇合適的ρ值，有利于提升路徑質(zhì)量。

傳統(tǒng)蟻群算法的ρ值是一個(gè)固定值，不能根據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)進(jìn)行調(diào)節(jié)，無(wú)法保證路徑質(zhì)量。本文基于軟件定義衛(wèi)星網(wǎng)絡(luò)架構(gòu)，利用SDN控制器實(shí)時(shí)動(dòng)態(tài)調(diào)整ρ值，使算法選擇出的路徑時(shí)刻處于較優(yōu)狀態(tài)。設(shè)置Tmax代表路徑上信息素的閾值，Dmax代表時(shí)延閾值，則ρ的取值為

式中：Tsd代表算法選出的最優(yōu)路徑的信息素值；Dsd代表源節(jié)點(diǎn)到目的節(jié)點(diǎn)的時(shí)延；s1、s2、s3、s4為常數(shù)閾值，并滿足不等式（25）。當(dāng)路徑上的信息素Dmax時(shí)，ρ應(yīng)該增大，在保證一定收斂速度的同時(shí)可以緩解網(wǎng)絡(luò)擁塞；當(dāng)路徑上的信息素>Tmax但時(shí)延Tmax且時(shí)延>Dmax時(shí)，ρ應(yīng)該選取較大值，因?yàn)榇藭r(shí)已經(jīng)接近擁塞邊緣，需要快速選取新路徑。

2.4 DRGVN-QR算法步驟

為了將衛(wèi)星網(wǎng)絡(luò)的動(dòng)態(tài)變化考慮在路徑選擇過程中，本文綜合考慮一段時(shí)間范圍內(nèi)的網(wǎng)絡(luò)狀態(tài)及所選路徑在該時(shí)間范圍內(nèi)的代價(jià)，從而選出全局最優(yōu)路徑。因此，本文基于DRGVN，采用ACO算法并發(fā)在每一個(gè)時(shí)間間隔內(nèi)選擇出一條路徑放入Pareto集合中，然后對(duì)Pareto集合中路徑的代價(jià)在時(shí)間T范圍內(nèi)進(jìn)行冪數(shù)加權(quán)求和，最終選出該時(shí)間范圍內(nèi)質(zhì)量最優(yōu)的路徑。該方案充分利用網(wǎng)絡(luò)的狀態(tài)和資源情況進(jìn)行路徑規(guī)劃，能夠有效緩解局部擁塞，提高網(wǎng)絡(luò)整體的服務(wù)質(zhì)量。

路徑代價(jià)的冪數(shù)加權(quán)求和公式為

DRGVN-QR算法的實(shí)現(xiàn)流程如圖3所示。具體實(shí)現(xiàn)流程為：

輸入動(dòng)態(tài)資源圖DRGVN={V，E，T，Sv(t)，Bu，v(t)，Dpu，v(t)，Bufv，Uv(t)}，隨機(jī)生成的源目的節(jié)點(diǎn)對(duì)，給定的業(yè)務(wù)請(qǐng)求M。

輸出源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的路徑path（M），滿足M的傳輸需求且具有多QoS保障。

步驟1根據(jù)衛(wèi)星網(wǎng)絡(luò)虛擬節(jié)點(diǎn)生成拓?fù)渚仃嘒，初 始 化 參 數(shù)：α、β、ω1、ω2、λ1、λ2、μ、Tmax、Dmax、Bmax等。

步驟2將代表不同時(shí)刻的螞蟻kt放到源節(jié)點(diǎn)，并將源節(jié)點(diǎn)標(biāo)記為已經(jīng)訪問。

步驟3使用算法1計(jì)算優(yōu)化后的下一步節(jié)點(diǎn)集allowedkt。

圖3 算法流程圖Fig. 3 Algorithm process

步驟4螞蟻根據(jù)式（18）計(jì)算出的概率在allowedk中選擇下一個(gè)節(jié)點(diǎn)，并將節(jié)點(diǎn)標(biāo)記為已經(jīng)訪問。

步驟5判斷當(dāng)前節(jié)點(diǎn)，如果不是目的節(jié)點(diǎn)則繼續(xù)執(zhí)行步驟6，如果是目的節(jié)點(diǎn)則執(zhí)行步驟8。

步驟6判斷allowedk集合是否為空，如果為空則該螞蟻尋路失敗返回執(zhí)行步驟2，如果不為空則執(zhí)行步驟4。

步驟7SDN控制器根據(jù)式（24）選取ρ值，然后使用式（21）更新信息素。

步驟8迭代結(jié)束后，將路徑放入Pareto集合。

步驟9使用式（26）對(duì)Pareto集合中路徑進(jìn)行質(zhì)量計(jì)算，輸出最優(yōu)解。

3 仿真實(shí)驗(yàn)

3.1 仿真場(chǎng)景及參數(shù)設(shè)置

本文使用STK進(jìn)行類銥星星座仿真，星座共有6個(gè)軌道平面，每個(gè)軌道11顆衛(wèi)星，共66顆衛(wèi)星均勻分布，軌道高度780 km，軌道傾角86.4°。使用MATLAB進(jìn)行算法仿真，算法詳細(xì)步驟見2.4節(jié)。

文獻(xiàn)［22］對(duì)蟻群的算法重要參數(shù)進(jìn)行了大量實(shí)驗(yàn)分析，確定了使算法收斂速度和求解性能均達(dá)到最優(yōu)的參數(shù)，本文選取α=1、β=5。螞蟻數(shù)量一般與問題規(guī)模一致，一般認(rèn)為節(jié)點(diǎn)數(shù)量的2/3是最優(yōu)螞蟻數(shù)量，因此選取m=40。信息素總量在500以內(nèi)時(shí)，問題規(guī)模對(duì)于信息素總量的選擇影響較小，本文選取信息素總量P=20。以上參數(shù)的設(shè)置能夠保證算法性能最優(yōu)。

設(shè)置單條路徑信息素最大值Tmax=200，單條鏈路最大時(shí)延Dmax=1 000 ms，根據(jù)本文的優(yōu)化目標(biāo)，確定各性能指標(biāo)的重要程度，選取ω1=0.8，ω2=0.2；λ1=0.2，λ2=0.4，λ3=0.4。仿真過程模擬連續(xù)發(fā)包1 500次，鏈路可用帶寬Bmax=200 Mbps［23］，每次隨機(jī)選擇源和目的節(jié)點(diǎn)對(duì)。并 通 過 實(shí) 驗(yàn) 對(duì) 幾 組s1、s2、s3、s4取 值 進(jìn) 行 驗(yàn)證，其網(wǎng)絡(luò)平均吞吐量如圖4示。

圖4 網(wǎng)絡(luò)平均吞吐量Fig. 4 Average throughout of network

實(shí)驗(yàn)結(jié)果表明當(dāng)s1=s2=s3=s4=0.5時(shí)，仿真后期網(wǎng)絡(luò)吞吐量出現(xiàn)大幅度波動(dòng)，因?yàn)棣阎倒潭?，算法初期表現(xiàn)較好，但后期沒有及時(shí)調(diào)整路徑信息素濃度，出現(xiàn)了緩存隊(duì)列排隊(duì)較長(zhǎng)的現(xiàn)象，吞吐量無(wú)法提升。當(dāng)s1=0.1、s2=0.3、s3=0.5、s4=0.7時(shí)，網(wǎng)絡(luò)吞吐量整體上明顯提高，且比較穩(wěn)定，但仍有輕微波動(dòng)，當(dāng)s1=0.2、s2=0.4、s3=0.6、s4=0.8時(shí)，整個(gè)網(wǎng)絡(luò)的吞吐量達(dá)到較優(yōu)狀態(tài)，且能夠保持穩(wěn)定。根據(jù)上述現(xiàn)象，本文選取s1=0.2、s2=0.4、s3=0.6、s4=0.8。

3.2 仿真結(jié)果分析

本文在相同實(shí)驗(yàn)環(huán)境下，將所提出的算法與經(jīng)典Dijkstra算法和基于多QoS約束的蟻群優(yōu)化路由算法（QoS-ACO）［16］，以及基于SDN的最短路徑算法（SDN-SPF）［20］進(jìn)行比較。

算法的平均求解時(shí)間如圖5所示，該指標(biāo)體現(xiàn)了算法的收斂性。以Dijkstra算法的表現(xiàn)為基準(zhǔn)，縱坐標(biāo)表示所對(duì)比算法的求解時(shí)間與Dijkstra算法的求解時(shí)間的比值。從圖中可以看出，SDN-SPF算法在仿真初期求解時(shí)間相對(duì)較快，但隨著仿真的進(jìn)行，為了緩解網(wǎng)絡(luò)擁塞該算法的求解時(shí)間逐漸增大。本文DRGVN-QR算法在仿真初期就獲得了較好的收斂速度，隨著仿真的進(jìn)行，由于本文算法動(dòng)態(tài)調(diào)整信息素?fù)]發(fā)系數(shù)，求解時(shí)間出現(xiàn)波動(dòng)現(xiàn)象，但整體上優(yōu)于其他算法。因?yàn)榧尤肓藘?yōu)化allowedk的算法，DRGVN-QR算法的收斂速度有所提升。

圖5 平均求解時(shí)間Fig. 5 Average solving time

算法的平均端到端時(shí)延如圖6所示。在仿真前半段，時(shí)延變化平緩，幾種算法的時(shí)延差別不明顯。但隨著數(shù)據(jù)包的不斷發(fā)送，本文所提DRGVN-QR算法的平均時(shí)延最低，與其他算法相比網(wǎng)絡(luò)端到端時(shí)延最大降低了7.8%，且明顯優(yōu)于其他算法。這是因?yàn)楸疚脑贏CO的啟發(fā)函數(shù)中引入了時(shí)延作為重要參考因素，并且揮發(fā)系數(shù)ρ的值隨著網(wǎng)絡(luò)的變化而動(dòng)態(tài)改變。在選取路徑時(shí)，本文考慮了一個(gè)時(shí)間段內(nèi)的路徑代價(jià)從而緩解網(wǎng)絡(luò)擁塞，因此所選路徑具有較好的時(shí)延性能和帶寬優(yōu)勢(shì)。

算法的平均丟包率如圖7所示，可以看出，隨著請(qǐng)求數(shù)量的增加網(wǎng)絡(luò)負(fù)載逐漸變大，時(shí)延和丟包率也隨之增大，與其他算法相比本文所提DRGVN-QR算法的丟包率最低，最大降低了8.6%，且增長(zhǎng)趨勢(shì)越來(lái)越小，最終能夠保持一個(gè)相對(duì)穩(wěn)定狀態(tài)。這是因?yàn)楸疚谋苊饬寺窂角袚Q帶來(lái)的丟包問題，時(shí)延降低的同時(shí)也能降低丟包率。

算法的平均時(shí)延抖動(dòng)如圖8所示?？梢钥闯?，在仿真前期，各算法的時(shí)延抖動(dòng)沒有太大差距，但隨著請(qǐng)求數(shù)量的增加，其他算法的平均時(shí)延抖動(dòng)明顯增加，DRGVN-QR算法的平均時(shí)延抖動(dòng)整體低于其他算法，最大降低了9.2%，且這種優(yōu)勢(shì)愈加明顯，最后逐漸趨于穩(wěn)定。仿真表明，DRGVN-QR算法在網(wǎng)絡(luò)平均時(shí)延抖動(dòng)方面表現(xiàn)良好，能夠有效地提升了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)姆€(wěn)定性。

綜合考慮以上因素，本文算法通過與其他算法進(jìn)行對(duì)比，體現(xiàn)了良好的性能。

圖6 平均端到端時(shí)延Fig. 6 Average end-to-end delay

圖7 平均丟包率Fig. 7 Average packet loss rate

圖8 平均時(shí)延抖動(dòng)Fig. 8 Average delay jitter

4 結(jié) 論

本文針對(duì)衛(wèi)星網(wǎng)絡(luò)特性，首先，建立一種虛擬節(jié)點(diǎn)動(dòng)態(tài)資源圖模型刻畫節(jié)點(diǎn)切換和資源的動(dòng)態(tài)性，基于此建立最小路徑代價(jià)多目標(biāo)優(yōu)化模型，該模型同時(shí)考慮了節(jié)點(diǎn)的切換狀態(tài)、緩存以及鏈路的剩余帶寬、時(shí)延等信息。其次，利用蟻群算法求解滿足多QoS約束的最小代價(jià)路徑集合，并討論蟻群算法信息素?fù)]發(fā)系數(shù)的選取問題。最后，設(shè)計(jì)一種冪指加權(quán)公式選出最優(yōu)路徑，保證數(shù)據(jù)傳輸?shù)目煽啃浴Ｍㄟ^仿真驗(yàn)證：

1） 在銥星星座仿真環(huán)境中，本文所提DRGVN-QR算 法 與SDN-SPF和QoS-ACO算法相比，網(wǎng)絡(luò)端到端時(shí)延最大降低了7.8%。

2） 同時(shí)平均丟包率最大降低了8.6%，提高了交付成功率。

3） 平均時(shí)延抖動(dòng)最大降低了9.2%，網(wǎng)絡(luò)穩(wěn)定性得到顯著提升。