宋鑫康, 趙尚弘, 王 翔, 郝少偉

(1. 空軍工程大學信息與導航學院, 陜西 西安 710077;2. 中國人民解放軍93721部隊, 山西 朔州 038300)

0 引 言

傳統(tǒng)航空信息網(wǎng)絡存在網(wǎng)絡服務與專用硬件緊耦合的弊端,使其難以提供敏捷靈活的定制化服務;同時航空平臺有限的設備承載能力,進一步制約了網(wǎng)絡服務水平的提升。而網(wǎng)絡功能虛擬化(network function virtualization,NFV)技術的發(fā)展將有助于改變部署專用設備提供服務的現(xiàn)狀,可基于通用服務器借助軟件實現(xiàn)虛擬網(wǎng)絡功能(virtual network function,VNF),從而實現(xiàn)網(wǎng)絡功能與專有硬件的分離。NFV技術與航空信息網(wǎng)絡的結(jié)合可改變平臺軟硬件緊耦合的現(xiàn)狀,實現(xiàn)對集群資源的細粒度管理和高效聚合。借助VNF可根據(jù)需求在不同位置上進行實例化的優(yōu)勢,按照不同任務的服務功能需求連接相應VNF構(gòu)成服務功能鏈(service function chain, SFC),可充分發(fā)揮集群體系化作戰(zhàn)優(yōu)勢。基于NFV技術的航空平臺可依托通用服務器提供多樣化網(wǎng)絡功能,但作戰(zhàn)任務的部署將面臨所需服務功能邏輯順序及部署位置未知的挑戰(zhàn),因此本文旨在解決根據(jù)作戰(zhàn)任務服務請求構(gòu)建SFC并進行高效映射問題。

SFC的構(gòu)建過程需在保證服務功能間依賴關系的基礎上將作戰(zhàn)任務所需服務功能進行排列,而SFC映射過程需在滿足資源需求條件下將作戰(zhàn)任務請求映射至底層航空信息網(wǎng)絡,因此SFC的構(gòu)建與映射本質(zhì)屬于非確定性多項式難題(non-deterministic polynomial-hard, NP-hard)。作為5G網(wǎng)絡性能提升的關鍵技術,目前相關研究均以地面網(wǎng)絡作為研究對象,文獻[7-8]聚焦于服務鏈映射問題,文獻[6,9-13]綜合考慮了服務鏈構(gòu)建和映射過程。文獻[6]基于改進粒子群算法獲得服務鏈構(gòu)建和映射方案,以服務鏈資源開銷最小作為優(yōu)化目標對構(gòu)建和映射方案混合編碼,可有效降低服務鏈的實際資源映射開銷,但算法的時間復雜度較大。文獻[9]提出了在線SFC聯(lián)合構(gòu)建和映射算法,基于當前節(jié)點不斷選取有限跳數(shù)內(nèi)服務功能以完成帶寬需求最小的服務鏈構(gòu)建,在確定服務功能類型基礎上選擇剩余計算資源最大平臺進行映射。該方法在映射過程中未考慮鏈路負載情況,使得帶寬資源極可能無法滿足任務需求。文獻[10]實現(xiàn)服務鏈構(gòu)建與映射過程的相互協(xié)調(diào),基于當前部署節(jié)點以貪婪策略選取后續(xù)服務功能,提高了成功映射概率,但未考慮底層網(wǎng)絡狀態(tài),導致容易陷入局部最優(yōu)。文獻[11]以帶寬資源最小化為優(yōu)化目標,針對服務功能間3種不同依賴關系設計了相應的服務鏈構(gòu)建和映射方法,但忽略了服務功能邏輯順序的改變對所需資源的影響。文獻[12]提出基于一種非協(xié)調(diào)方法來解決服務鏈構(gòu)建與映射問題,采用啟發(fā)式方法獲得服務鏈構(gòu)建方案,然后將映射問題表述為約束條件下的混合整數(shù)問題,該方法計算量大,適用于小規(guī)模網(wǎng)絡。同時,由于兩階段為獨立求解,所以聯(lián)合結(jié)果沒有得到進一步優(yōu)化。

上述研究針對SFC構(gòu)建和映射方案的求解相對獨立,在構(gòu)建與映射方案匹配關系不斷調(diào)整過程中獲得最優(yōu)解。該方式在實現(xiàn)網(wǎng)絡資源情況與服務鏈構(gòu)建方案的相互協(xié)調(diào)方面時間開銷較大,無法適應航空作戰(zhàn)時延敏感特征。其次,相較于地面網(wǎng)絡,航空領域戰(zhàn)場復雜多變,任務請求得到快速響應的需求更加迫切。針對上述問題,本文提出了一種航空信息網(wǎng)絡服務鏈協(xié)同構(gòu)建與映射策略,區(qū)別于已有算法,所提策略基于映射平臺資源狀況確定服務鏈構(gòu)建方案,極大簡化構(gòu)建和映射方案相互調(diào)整過程,減少了搜索時間開銷,在有限時間內(nèi)可獲得較優(yōu)方案,可實現(xiàn)任務請求的快速響應以及任務請求接受率的提高。所提策略借助啟發(fā)式算法時間復雜度低的優(yōu)勢,基于改進蟻群算法以鏈路負載率為牽引確定服務功能的映射平臺,應用廣度優(yōu)先搜索思想確定最佳服務鏈構(gòu)建方案。

1 系統(tǒng)建模

1.1 網(wǎng)絡模型

1.1.1 航空信息網(wǎng)絡模型

112 作戰(zhàn)任務請求模型

每項作戰(zhàn)任務請求表示為=(,,,),其中和分別表示作戰(zhàn)任務的初始平臺和目的平臺,和僅發(fā)揮數(shù)據(jù)發(fā)送和接收功能,忽略流量對服務模塊計算資源的占用;表示作戰(zhàn)任務所需的服務功能集合;表示初始平臺所發(fā)送數(shù)據(jù)的初始帶寬。

1.2 問題描述

121 SFC構(gòu)建

SFC構(gòu)建過程需在遵循服務功能間依賴關系的基礎上將作戰(zhàn)任務所需服務功能進行排列。由于各服務功能的流量改變率存在差異,不同的排列順序會使得所構(gòu)建SFC對服務模塊計算資源和通信鏈路帶寬資源產(chǎn)生不同需求。如圖1(a)所示作戰(zhàn)任務請求共需5種服務功能類型,同時虛線表示各服務功能間依賴關系,例如類型的運行以完成類型運行為前提;圖1 (b)為基于作戰(zhàn)任務需求得到的所有符合服務功能間依賴關系的SFC構(gòu)建方案。如圖1所示,不同的排列方式使得各服務功能所需計算資源和帶寬資源需求存在差異,初始平臺發(fā)送帶寬需求為30 Mb/s的數(shù)據(jù),由于服務功能的流量改變率為08,所以經(jīng)服務功能后流量帶寬需求轉(zhuǎn)變?yōu)?4 Mb/s。同時,服務功能的資源開銷比為02,則相應服務模塊需提供6 Mb計算資源。以此類推可得SFC1所示排列方式可實現(xiàn)對資源的需求總量達到最小,其對計算資源需求為35.45 Mb,對帶寬資源需求為129.08 Mb/s。

圖1 作戰(zhàn)任務需求及相應的SFCFig.1 Operational mission requirements and corresponding SFC

1.2.2 SFC映射

SFC映射需將作戰(zhàn)任務請求映射至底層航空信息網(wǎng)絡,映射過程需確定SFC中服務功能及鏈路與航空信息網(wǎng)絡中平臺及通信鏈路對應關系,而平臺所承載服務模塊的計算資源和通信鏈路的帶寬資源將直接影響服務鏈能否映射成功。對于服務鏈映射過程,不同服務鏈構(gòu)建方案映射至相同平臺和通信鏈路以及基于同一服務鏈選取不同平臺及通信鏈路,均會影響服務鏈的實際資源占用情況。如圖2所示,基于SFC1構(gòu)建方案采取不同映射方式可能會影響服務鏈的映射成功率,若平臺和間鏈路帶寬無法滿足需求,將導致方案1映射失敗;同時所采取映射方案會影響平臺和鏈路剩余資源,尤其對于關鍵鏈路的資源占用會影響后續(xù)服務鏈的映射成功率。

圖2 服務鏈映射示意圖Fig.2 Schematic diagram of service chain mapping

1.3 優(yōu)化目標

作戰(zhàn)任務請求的部署可分為SFC構(gòu)建和映射兩個步驟,本文旨在通過合理地構(gòu)建及映射SFC,最大化作戰(zhàn)任務請求的接受率,因此目標函數(shù)定義為

(1)

請求接受率為初始時刻到時刻映射成功的任務請求總數(shù)與到達的任務請求總數(shù)之比,其中num()表示截止時刻映射成功的請求總數(shù),num()表示截止時刻到達的請求總數(shù)。約束條件如下:

(2)

(3)

(4)

(5)

(6)

(7)

C4～C6表示SFC映射過程中資源約束。C4表示服務功能所映射航空平臺的服務模塊需要有足夠的計算資源。C5表示服務功能和間鏈路所映射通信鏈路需要有足夠的帶寬資源保證數(shù)據(jù)流量正常傳輸,在忽略流量分割情況下通信路徑的最小帶寬取決于所經(jīng)過帶寬最小的鏈路。6表示流量傳輸滿足鏈路連通性約束,即除路徑端點外,中間節(jié)點流入鏈路數(shù)量與流出鏈路數(shù)量相等。

1.4 評價指標

對于航空信息網(wǎng)絡SFC協(xié)同構(gòu)建和映射問題,除請求接受率指標外,考慮到作戰(zhàn)任務的時延敏感特點和網(wǎng)絡的資源利用情況,選取請求平均等待時間、資源利用率和映射資源開銷作為評價指標。

1.4.1 請求平均等待時間

航空領域戰(zhàn)場態(tài)勢復雜多變,作戰(zhàn)任務請求的快速響應有助于提高作戰(zhàn)效率,保證作戰(zhàn)任務的順利完成。任務平均等待時間為截止時刻所有到達任務的等待時間之和與到達數(shù)量之比:

(8)

142 資源利用率

資源利用率為各時刻當前網(wǎng)絡占用資源量與網(wǎng)絡資源總量之比,本文從平臺計算資源利用率和鏈路帶寬資源利用率進行評價,如下所示:

(9)

(10)

SFC構(gòu)建和映射方案可通過資源開銷情況進行反映,資源開銷為所占用計算資源與帶寬資源的加權和,如下所示:

(11)

為協(xié)調(diào)計算資源和帶寬資源在資源開銷中影響比重而引入加權參數(shù)?和,其取值分別為1和05。

2 算法設計

SFC構(gòu)建與映射問題屬于NP-hard問題,同時復雜多變的航空戰(zhàn)場對算法的時間復雜度提出了較高要求。蟻群算法兼顧啟發(fā)式算法在較短時間內(nèi)可獲得較優(yōu)解特點的同時,具有魯棒性強、并行分布式計算、全局搜索能力突出的優(yōu)勢,因此本文將蟻群算法用于確定服務功能與航空平臺的映射關系,但考慮到算法存在收斂速度慢、局部搜索能力不強等劣勢,針對其進行了改進以提升算法性能。其次,應用廣度優(yōu)先搜索算法確定當前映射資源條件下最佳服務功能排列順序,即服務鏈構(gòu)建方案,其中選取最短路徑作為各服務功能間通信鏈路。

2.1 算法改進原理

2.1.1 解空間優(yōu)化

轉(zhuǎn)移概率是螞蟻尋路過程中的關鍵指標,時刻螞蟻基于航空平臺到航空平臺的轉(zhuǎn)移概率如下所示：

(12)

傳統(tǒng)蟻群算法各可行解設置相同信息素初始值,增強了節(jié)點選取的隨機性,提高了算法的全局搜索能力,但也使得需要花費較長時間以發(fā)揮正反饋機制效果,進而導致了算法初期收斂速度較慢。結(jié)合服務鏈映射問題,在算法中引入鏈路和平臺負載因子,在算法運行初期可縮小可行解搜索范圍,以提高算法收斂速度。

鏈路負載因子:定義鏈路負載矩陣作為全局變量,記錄各時刻航空信息網(wǎng)絡中通信鏈路的負載情況,將有助于避免螞蟻選取鏈路負載較大的通信鏈路。鏈路負載因子定義如下:

樁后土拱處于極限平衡狀態(tài)時，邱子義等[12]、劉小麗等[18]認為土拱沿著K點水平方向發(fā)生破壞，如圖7所示。圖7中樁后均存在三角形受壓區(qū)，左側(cè)拱的樁后受壓區(qū)為EFG，EF的長度t1為樁后土拱的厚度；K為EF的中點，即拱軸線與拱腳截面的交點。

(13)

平臺負載因子:定義平臺負載矩陣作為全局變量,記錄航空平臺各服務模塊的計算資源占用情況,當服務模塊計算資源占用超過所設定80%閾值時,將該服務模塊從可行解空間刪除,從而縮小可行解空間范圍。鏈路和平臺負載因子的設定,將有助于提高算法初期的收斂速度,同時選取資源相對充足的平臺和鏈路利于任務請求的成功映射。

212 信息素更新

所提算法中對航空平臺所承載服務模塊賦予信息素屬性,本文對信息素的更新策略進行改進以提高蟻群算法的收斂速度和算法運行性能。

(14)

(15)

2.2 算法實現(xiàn)

本文提出負載平衡服務鏈構(gòu)建與嵌入(load balancing service chain construction and embedding, LBCE)算法,以鏈路和平臺負載率為牽引,旨在實現(xiàn)SFC構(gòu)建和映射過程中的負載均衡。算法首先以任務請求中初始平臺為起點,綜合考慮其他平臺與初始平臺間鏈路以及服務模塊信息素情況,應用式(12)求解得到滿足任務服務需求的各平臺轉(zhuǎn)移概率,依據(jù)轉(zhuǎn)移概率選擇相應服務功能映射平臺,進而將所選平臺作為起點依次完成后續(xù)平臺的選擇,從而完成蟻群初始化。其次針對各螞蟻基于所選定航空平臺利用廣度優(yōu)先搜索算法,從任務初始平臺出發(fā)以服務功能依賴關系為約束,獲得映射方案中后續(xù)可運行服務功能所對應平臺集合,判斷初始平臺與集合中各平臺間最短通信路徑是否滿足帶寬需求,將滿足需求平臺作為當前平臺以此類推尋找后續(xù)平臺,直至到達目的平臺,從而獲得當前映射關系下滿足功能依賴關系的所有服務鏈構(gòu)建方案,將資源開銷最小的方案作為該螞蟻的行動路徑。當所有螞蟻完成路徑選取后,記錄全局最優(yōu)方案及資源開銷最優(yōu)值,按照式(14)和式(15)完成各螞蟻所選平臺相應服務模塊的信息素濃度更新。最后當蟻群算法循環(huán)滿足迭代次數(shù)終止后,根據(jù)所得全局最優(yōu)方案,更新平臺和鏈路負載因子輔助后續(xù)服務鏈的構(gòu)建與映射。

算法 1 LBCE算法輸入: 航空信息網(wǎng)絡G,作戰(zhàn)任務請求M輸出: 服務鏈構(gòu)建與映射方案1: while n

24:end while25:/*平臺和鏈路負載因子更新*/26:根據(jù)所得最優(yōu)方案更新所選平臺和鏈路負載情況。

3 仿真與分析

3.1 仿真設置

本文在Matlab仿真環(huán)境下對所提算法進行分析評估。航空信息網(wǎng)絡的參數(shù)設置如下:場景區(qū)域為1 000 km×1 000 km,航空平臺數(shù)量為50架,基于改進的Salam算法隨機生成網(wǎng)絡拓撲,網(wǎng)絡中每條無向邊設置為兩條有向邊,每個方向鏈路帶寬服從[70,80]的均勻分布。借鑒文獻[6],仿真設置如圖3所示4種不同類型作戰(zhàn)任務請求,各任務請求的源平臺和目的平臺隨機產(chǎn)生,任務請求的初始流量服從[30,40]的均勻分布。仿真實驗隨機生成1 000個作戰(zhàn)任務請求,其到達率服從λ=0.7的泊松分布,生存周期和服務周期分別服從μ=10、η=100的指數(shù)分布。為避免隨機因素干擾,仿真實驗共進行10次,取實驗結(jié)果平均值作為最終結(jié)果。

圖3 作戰(zhàn)任務請求類型Fig.3 Combat mission request types

各航空平臺僅可運行部分VNF,因此本文設置每個平臺隨機承載任意2～3種類型服務模塊,各服務模塊參數(shù)設置如表1所示。

表1 服務功能類型及其參數(shù)Table 1 Service function types and their parameters

文獻[6]所提算法可有效降低SFC的資源映射開銷,提高作戰(zhàn)任務的請求接受率。文獻[9]所提算法的時間復雜度較低,可滿足作戰(zhàn)任務快速響應需求。因此,將本文所提LBCE算法與文獻[6]和文獻[9]中算法進行對比,算法具體描述如表2所示。同時,對算法中種群規(guī)模和迭代次數(shù)進行限制以適應航空作戰(zhàn)特點。

表2 算法描述Table 2 Algorithm description

3.2 結(jié)果分析

圖4為不同作戰(zhàn)任務請求數(shù)量下各算法請求接受率對比,相較于文獻[6]算法和LBCE算法,由于文獻[9]算法缺乏對可行解的迭代優(yōu)化以及映射過程中未考慮鏈路負載情況,使得文獻[9]算法映射成功率最低,甚至在仿真初期出現(xiàn)請求接受率直線下降問題。文獻[6]算法由于采用服務鏈構(gòu)建方案與映射方案不斷匹配的方式進行求解,在迭代次數(shù)和種群規(guī)模有限條件下致使構(gòu)建方案與網(wǎng)絡資源的相互協(xié)調(diào)過程不夠充分,無法有效降低所得方案的資源開銷情況,導致映射成功率低于LBCE算法。LBCE算法在選定航空平臺后應用廣度優(yōu)先搜索算法可確定當前資源狀況下最佳服務鏈構(gòu)建方案,從而降低了服務鏈構(gòu)建和映射方案的資源開銷,相比文獻[6]和文獻[9]算法請求接受率分別提高了約12.3%和46.2%。

圖4 不同作戰(zhàn)任務請求數(shù)量下請求接受率Fig.4 Request acceptance rate under different number of combat mission requests

圖5為不同作戰(zhàn)任務請求數(shù)量下各算法任務平均等待時間對比,任務的等待時間主要取決于當前航空信息網(wǎng)絡資源情況,若當前網(wǎng)絡資源狀況可滿足到達任務需求,則任務等待時間為0,否則任務會在生存周期允許范圍內(nèi)等待其他任務釋放網(wǎng)絡資源。文獻[9]算法由于僅建立一種服務鏈構(gòu)建和映射方案使得任務請求接受率較低,致使等待隊列累積任務請求數(shù)量較多,導致其任務平均等待時間最長。文獻[6]算法由于服務鏈構(gòu)建和映射方案資源開銷較大,當正在服務任務到達一定數(shù)量后網(wǎng)絡剩余資源嚴重不足,無法滿足后續(xù)任務需求,增大了任務的平均等待時間。LBCE算法在滿足資源需求的同時可結(jié)合網(wǎng)絡資源情況完成服務鏈構(gòu)建,因此任務的平均等待時間較短,相較文獻[6]和文獻[9]算法任務平均等待時間降低了約12.1%和26.8%,可實現(xiàn)任務請求的快速響應。

圖5 不同作戰(zhàn)任務請求數(shù)量下請求平均等待時間Fig.5 Average waiting time for requests under different number of combat mission requests

圖6和圖7為各作戰(zhàn)任務請求到達時刻航空信息網(wǎng)絡的平臺計算資源和鏈路帶寬資源利用率,仿真初期,隨著作戰(zhàn)任務需求不斷到達計算資源和帶寬資源利用率不斷增大。當網(wǎng)絡服務任務數(shù)量接近飽和時,LBCE算法的平臺計算資源和鏈路帶寬資源利用率基本維持在41.8%和18.7%;文獻[6]算法的平臺計算資源和鏈路帶寬資源利用率基本維持在37.4%和28.9%;文獻[9]算法的平臺計算資源和鏈路帶寬資源利用率基本維持在29.4%和19.7%;LBCE算法由于可滿足較多任務需求,其平臺計算資源利用率較高,同時其以鏈路負載率和通信跳數(shù)為依據(jù)選取平臺,可降低帶寬資源開銷。文獻[6]算法可以滿足較多任務請求,因此平臺計算資源利用率較高,但可能存在所選平臺間通信跳數(shù)過多問題,從而導致對鏈路資源利用率較高。文獻[9]算法由于請求接受率較低導致平臺計算資源和鏈路帶寬資源利用率均不高。

圖6 航空信息網(wǎng)絡平臺計算資源利用率Fig.6 Calculation resource utilization rate of aviation information network platform

圖7 航空信息網(wǎng)絡鏈路帶寬資源利用率Fig.7 Link bandwidth resource utilization of aviation information network

圖8為隨機選取25組3種算法均成功映射的服務鏈,將其資源開銷情況進行對比。由圖8可知,LBCE算法所得服務鏈構(gòu)建和映射方案資源開銷最小,文獻[9]算法由于對平臺間通信跳數(shù)進行限制使得帶寬資源消耗較少,因此大部分映射成功的服務鏈資源開銷僅次于LBCE算法,而文獻[6]算法由于存在平臺間通信路徑過長問題使得映射方案資源開銷較多,少數(shù)情況資源開銷優(yōu)于文獻[9]算法。

圖8 服務鏈映射資源開銷Fig.8 Service chain mapping resource overhead

表3對各算法成功映射服務鏈資源開銷情況進行分析,由表3可知，LBCE算法可實現(xiàn)服務鏈構(gòu)建和映射方案資源開銷最小且穩(wěn)定,文獻[6]算法由于通信路徑長度的隨機性導致資源開銷均方差較大,即資源開銷波動性較大。同時,文獻[9]算法由于搜索過程較為簡單,算法平均時間開銷最小,文獻[6]算法由于涉及種群迭代及交叉、變異操作,算法平均時間開銷最大,LBCE算法僅涉及螞蟻種群迭代過程,平均時間開銷介于兩者之間。

表3 3種算法映射數(shù)據(jù)分析Table 3 Map data analysis of three algorithms

4 結(jié)束語

本文針對航空信息網(wǎng)絡服務鏈構(gòu)建與映射問題,提出了以平臺和鏈路負載率為牽引的服務鏈構(gòu)建和映射策略。研究結(jié)果表明,相比兩種對比算法請求接受率分別提高了約12.3%和46.2%,任務平均等待時間分別降低了約12.1%和26.8%,服務鏈資源開銷分別降低了28.3%和16.7%。算法在時間復雜度較低條件下可有效提高任務請求接受率，并降低服務鏈構(gòu)建和映射方案的資源開銷,實現(xiàn)任務請求的快速響應。然而,作戰(zhàn)任務請求中初始和目的平臺由于具有不確定性,使得服務鏈映射成功率以及各時刻計算資源和帶寬資源的整體水平較低。因此,下一步研究重點考慮服務模塊和已映射服務功能的動態(tài)調(diào)整問題。