鄭偉軍，徐 宏，王 征，唐錦江，胡景博，朱重希，姚繼明

1.國網(wǎng)浙江省電力有限公司嘉興供電公司，浙江 嘉興 314000

2.國網(wǎng)浙江省電力有限公司桐鄉(xiāng)市供電公司，浙江 桐鄉(xiāng) 314506

3.全球能源互聯(lián)網(wǎng)研究院有限公司，北京 102200

隨著智能電網(wǎng)的快速發(fā)展與能源互聯(lián)網(wǎng)的興起，電網(wǎng)規(guī)模不斷擴大，電力業(yè)務(wù)種類不斷增多，電力業(yè)務(wù)類別可分為控制類、采集類和移動應(yīng)用類，其中控制類業(yè)務(wù)涉及到核心生產(chǎn)控制的業(yè)務(wù)流程，對通信網(wǎng)絡(luò)的要求十分嚴格。如配網(wǎng)差動保護業(yè)務(wù)，時延要求在15 ms范圍內(nèi)，時延抖動在±50 μs，可靠性要求99.999%，對于精準負荷控制業(yè)務(wù)，時延要求在50 ms范圍內(nèi)，可靠性要求99.999%［1］。

聚焦到智能配用電環(huán)節(jié)，5G技術(shù)為配電通信網(wǎng)“最后一公里”無線接入通信覆蓋提供了一種更優(yōu)的解決方案，配網(wǎng)差動保護、精準負荷控制、高級計量、分布式能源接入等業(yè)務(wù)可借力5G技術(shù)實現(xiàn)更優(yōu)的業(yè)務(wù)承載。在使用同一5G網(wǎng)絡(luò)承載多種電力業(yè)務(wù)的應(yīng)用場景下，如何保障電力控制類等重要業(yè)務(wù)的時延和可靠性要求，是實現(xiàn)5G在電力系統(tǒng)中的規(guī)?；瘧?yīng)用的重要條件。

虛擬化節(jié)點和鏈路資源的分配問題被稱為虛擬網(wǎng)絡(luò)嵌入（Virtual Network Embedded，VNE）［2］，目前，許多研究都著眼于提高物理基礎(chǔ)設(shè)施的收入和減少虛擬網(wǎng)絡(luò)映射時間的問題［3］，而帶有約束條件的映射［3］被證明是 NP?hard 問題［4］。

現(xiàn)有的大多數(shù)映射算法［5］將給定的虛擬網(wǎng)絡(luò)（Virtual Network，VN）映射分為兩個獨立有序的階段：虛擬節(jié)點映射階段和虛擬鏈路映射階段。這種映射策略不能保證每個虛擬網(wǎng)絡(luò)的最優(yōu)或次優(yōu)嵌入分配。文獻［6］中作者采用節(jié)點度、節(jié)點強度和Markov Random Walk模型迭代計算所有節(jié)點優(yōu)先級。文獻［7］中作者考慮了不同拓撲屬性的7個特征：“度”、“強度”、“距離中心性”、“接近中心性”、“介數(shù)中心性”、“特征向量中心性”和“卡茨中心性”，通過拓撲感知啟發(fā)式算法，求解計算節(jié)點的相對重要性。文獻［8］針對虛擬網(wǎng)絡(luò)功能鏈對性能與可用性需求，以最大化資源利用率為目標，形式化定義了高可用虛擬網(wǎng)絡(luò)功能鏈部署問題，證明了該問題是NP難問題，提出了基于路徑擴展的虛擬網(wǎng)絡(luò)功能部署算法，并采用備份共享的思路，提出基于概率空間劃分的虛擬網(wǎng)絡(luò)功能備份策略。文獻［9］采用一致的優(yōu)化模型綜合分析網(wǎng)絡(luò)資源分配的現(xiàn)有技術(shù)方法，包括成本優(yōu)化、收益優(yōu)化、剩余資源優(yōu)化和網(wǎng)絡(luò)能耗優(yōu)化。進一步針對電信級運營，分析了業(yè)務(wù)等級違約最小化、跨網(wǎng)絡(luò)分域部署策略和博弈機制設(shè)計方案，論述了動態(tài)拓撲適應(yīng)、接納和可靠性控制的方法，以及采用比例計算節(jié)能的優(yōu)化問題建模。文獻［10］提出的節(jié)點排序算法考慮了4種節(jié)點鏈路約束因素：節(jié)點位置、節(jié)點容量、鏈路帶寬和鏈路傳播延遲，以保證時延敏感業(yè)務(wù)的時延需求。但是，以上啟發(fā)式映射算法都將節(jié)點映射階段與鏈路映射階段完全分離，均未考慮全局屬性，忽略了鏈路映射結(jié)果對物理節(jié)點排名的影響，這可能會導(dǎo)致更高的映射成本和虛擬節(jié)點在底層網(wǎng)絡(luò)上的分布式分布帶來的負載不均衡問題。

由于VNE是為未來動態(tài)網(wǎng)絡(luò)場景而設(shè)計的，因此最大限度地減少映射分配計算時間和保證嵌入質(zhì)量非常重要。對于5G智能電網(wǎng)的端到端NS部署，需要考慮電力業(yè)務(wù)的具體QoS需求。文獻［11］提出了一種基于遺傳算法的容錯虛擬鏈路映射（GFVLM）算法，在映射過程中考慮了負載均衡，避免了“瓶頸節(jié)點”的出現(xiàn)，保證網(wǎng)絡(luò)的容錯和可靠性。文獻［12］提出了一種基于優(yōu)先級和故障概率的主鏈路映射模型，考慮了智能電網(wǎng)的服務(wù)可靠性，為高可靠性鏈路提供高優(yōu)先級的服務(wù)。但是以上智能電網(wǎng)場景下的虛擬網(wǎng)絡(luò)映射算法未考慮電力業(yè)務(wù)在業(yè)務(wù)請求層的時延需求，由于虛擬網(wǎng)絡(luò)請求的優(yōu)先級不僅受業(yè)務(wù)類型不同的影響，還由資源消耗、映射成本、等待時間和持續(xù)時間等綜合因素共同確定。然而以上虛擬網(wǎng)絡(luò)映射算法都忽略了虛擬網(wǎng)絡(luò)請求自身業(yè)務(wù)的差異性和業(yè)務(wù)屬性參數(shù)對請求映射順序的影響，造成虛擬網(wǎng)絡(luò)請求等待時間過長從而可能導(dǎo)致請求接收率降低。而恰當?shù)靥幚聿⒄{(diào)整虛擬網(wǎng)絡(luò)映射的順序，會有效提升虛擬網(wǎng)絡(luò)映射算法的性能，縮短虛擬網(wǎng)絡(luò)請求的等待時間并提高虛擬網(wǎng)絡(luò)請求接收率，支撐更優(yōu)質(zhì)的網(wǎng)絡(luò)承載服務(wù)。

綜上所述，本文針對電力業(yè)務(wù)時延敏感度、節(jié)點的全局資源和業(yè)務(wù)可靠性需求，提出一種基于電力業(yè)務(wù)時延敏感度和服務(wù)可靠性的虛擬網(wǎng)絡(luò)映射方案。首先對請求業(yè)務(wù)排序，縮短虛擬網(wǎng)絡(luò)請求的等待時間并提高虛擬網(wǎng)絡(luò)請求接收率；然后，在節(jié)點映射層，提出一種基于節(jié)點拓撲屬性和相鄰節(jié)點重要性的節(jié)點排序方法；最后，在鏈路映射層，構(gòu)建基于鏈路時延和鏈路負載比方差的可靠性懲罰函數(shù)，提出基于遺傳算法的鏈路映射算法。

1 系統(tǒng)模型

系統(tǒng)模型如圖1所示，虛擬網(wǎng)絡(luò)映射模型包括3層，分別是基礎(chǔ)設(shè)施層、虛擬網(wǎng)絡(luò)提供層和業(yè)務(wù)層。定義E表示虛擬網(wǎng)絡(luò)映射模型中業(yè)務(wù)請求層提出資源請求的集合，e表示這個集合中的一個請求。將虛擬網(wǎng)絡(luò)（VN）提供層的網(wǎng)絡(luò)建模為一個加權(quán)圖GV＝（NV，LV），其中，NV代表節(jié)點ni的集合，LV代表鏈路lx的集合。虛擬節(jié)點的計算能力需求為 cpu（ni），鏈路的帶寬容量需求為BV（lx）。 物理網(wǎng)絡(luò)可以抽象為加權(quán)無向圖GS＝（NS，LS），NS和LS分別為物理網(wǎng)絡(luò)的節(jié)點集合和鏈路集合。每條基礎(chǔ)設(shè)施鏈路都有一個總帶寬容量和剩余帶寬BS（lx）。

圖1 虛擬網(wǎng)絡(luò)映射模型

服務(wù)接收率O（t）定義為時間段T內(nèi)成功映射的虛擬網(wǎng)絡(luò)請求數(shù)量與收到的虛擬網(wǎng)絡(luò)請求數(shù)量的比值，表示式為

式中，Re（t）表示在時刻t成功映射的虛擬網(wǎng)絡(luò)服務(wù)請求數(shù)，Ge（t）表示在時刻t收到的虛擬網(wǎng)絡(luò)服務(wù)請求數(shù)。

2 虛擬網(wǎng)絡(luò)映射算法

本文從電力業(yè)務(wù)的QoS要求出發(fā)，實現(xiàn)5G虛擬化技術(shù)與電力業(yè)務(wù)的動態(tài)需求高度匹配。考慮到電力業(yè)務(wù)時延敏感度、節(jié)點的全局資源、業(yè)務(wù)可靠性需求等因素，以有效提高虛擬網(wǎng)絡(luò)請求接收率和資源利用率，保障業(yè)務(wù)的時延和可靠性需求。

在業(yè)務(wù)請求層根據(jù)業(yè)務(wù)時延敏感度對業(yè)務(wù)請求進行優(yōu)先級排序，高優(yōu)先級的請求優(yōu)先選擇虛擬節(jié)點；在虛擬網(wǎng)絡(luò)提供層根據(jù)拓撲屬性和相鄰節(jié)點重要性對虛擬節(jié)點進行優(yōu)先級排序，實現(xiàn)映射后鏈路的負載均衡，高優(yōu)先級節(jié)點會優(yōu)先映射最優(yōu)鏈路；在基礎(chǔ)設(shè)施層通過遺傳算法求得最優(yōu)鏈路映射方案，以保障業(yè)務(wù)的時延，提高業(yè)務(wù)的可靠性和網(wǎng)絡(luò)資源的利用率。

2.1 業(yè)務(wù)請求優(yōu)先級排序

由于不同業(yè)務(wù)請求的資源需求量和生存周期不同，因此對時延敏感度高且資源需求量大的業(yè)務(wù)請求設(shè)置高優(yōu)先級可以提高后續(xù)請求的映射成功率，提高物理資源利用率。

定義業(yè)務(wù)請求所需資源為

式中，cpu（ni）為請求業(yè)務(wù)所需的cpu計算能力，為剩余鏈路帶寬資源。

定義業(yè)務(wù)請求等待時間和最長等待時限的比值為

式中，tw為業(yè)務(wù)請求等待時間，TW為最長等待時限，該時限取決于電力業(yè)務(wù)的時延敏感度，時延敏感度越高，最長等待時限越短。

定義業(yè)務(wù)請求優(yōu)先級屬性P（GV）為

式中，Tc為業(yè)務(wù)請求持續(xù)時間，P（GV）值越大，優(yōu)先級越高。當請求等待時間超過最大等待時限時，將優(yōu)先級設(shè)為最高等級。

η是一個二分值，定義為

當η為0時，業(yè)務(wù)請求等待時間超過最大等待時限，將其優(yōu)先級調(diào)至最高，即0，以保證業(yè)務(wù)請求的公平性，當時延不敏感的業(yè)務(wù)請求時間過長時，可暫時提高其優(yōu)先級，優(yōu)先發(fā)出請求。因此，業(yè)務(wù)請求的優(yōu)先級p的最高級為0，其次為P（GV）的最大值，最后為P（GV）的最小值，始終優(yōu)先執(zhí)行優(yōu)先級為0的業(yè)務(wù)請求。

2.2 虛擬節(jié)點優(yōu)先級排序

在節(jié)點映射階段通過啟發(fā)式算法對虛擬節(jié)點進行排序，然后進行排序映射。本文將拓撲屬性和相鄰節(jié)點重要性作為排序參數(shù)，對節(jié)點進行排序，以確保映射后鏈路負載均衡。定義單個節(jié)點的拓撲屬性值為

式中，Strength（ni）表示節(jié)點的強度屬性，對于某個節(jié)點ni，其強度屬性表示其相鄰鏈路的強度的權(quán)重之和。在本文中，鏈路帶寬表示鏈路的權(quán)值。也就是說，如果節(jié)點強度越高，節(jié)點就有越多的相鄰資源來映射虛擬網(wǎng)絡(luò)。表示鄰居節(jié)點nbr（ni） 的鏈路帶寬資源B（lij）的總和。 Ratio（ni）為節(jié)點負載率，定義為

式中，cpumax（ni）為節(jié)點最大計算資源；cpuremain（ni）為節(jié)點剩余計算資源，定義為

式中，cpu′（ni）為映射請求業(yè)務(wù)之前的cpu計算能力，cpu（ni）為請求業(yè)務(wù)需要的cpu計算能力。

為了考慮相鄰節(jié)點對節(jié)點屬性值的影響，定義了節(jié)點全局屬性值。節(jié)點全局屬性值SV（ni）表示為

式中，ρ定義為相鄰節(jié)點重要性，表示帶寬資源占總帶寬資源的比例，用來衡量鄰居節(jié)點的相對重要性，定義為

綜上所述，將單個節(jié)點拓撲屬性Rv（ni）和相鄰節(jié)點重要性ρ作為輸入，計算節(jié)點全局拓撲屬性值SV，對節(jié)點進行排序。將滿足業(yè)務(wù)請求計算能力cpu（ni）的節(jié)點放入集合S中，其中高優(yōu)先級的業(yè)務(wù)優(yōu)先選擇屬性值SV高的節(jié)點。算法執(zhí)行流程圖如圖2所示。具體流程如算法1所示。

圖2 虛擬節(jié)點排序算法流程圖

算法1基于屬性值的虛擬節(jié)點映射算法

2.3 基于多條件約束的鏈路映射方法

在虛擬網(wǎng)絡(luò)提供層，根據(jù)拓撲屬性和相鄰節(jié)點重要性對虛擬節(jié)點進行優(yōu)先級排序，實現(xiàn)映射后鏈路的負載均衡。本節(jié)考慮了基礎(chǔ)設(shè)施層的可靠性、負載均衡和鏈路時延因素，構(gòu)建了基于鏈路時延和鏈路負載比方差的可靠性懲罰函數(shù)，構(gòu)建目標函數(shù)為

式中，α為權(quán)重值；DelayS為鏈路時延，其中，定義固定時延為Dfixed，排隊時延為Dq，不對稱時延為Dcd，即有

式中，固定時延Dfixed一般取區(qū)間均值1.57 ms；排隊時延為平均流量到達速率，μr為隊列的分組傳輸速率；不對稱時延當雙向通道延時不相等時，存在一定的時延差，因此設(shè)終端向主站發(fā)送方向通道時延為Td1，主站向終端發(fā)送方向通道時延為Td2，由于發(fā)送時延與接收時延不等造成的同步調(diào)整時間誤差為：ΔTd＝且必須滿足為制動系數(shù)），才能保證保護類業(yè)務(wù)不發(fā)生誤動，即有

基礎(chǔ)架構(gòu)層鏈接的變化Var＿ratio（LS）表示為鏈路負載比方差

式中，δ（lx）是一個二分值，表示映射指標變量，定義為

鏈路負載率定義為

與節(jié)點負載率的定義類似，Bmax（lx）為每條鏈路的總帶寬容量，B（lx）為剩余帶寬資源。

鏈路帶寬限制表示為

式中，φni（x）為業(yè)務(wù)映射指標變量，表示為

因此，最小化相應(yīng)的懲罰函數(shù)，建立鏈路映射模型為

該數(shù)學(xué)模型是一個NP?hard問題，可以通過遺傳優(yōu)化算法求解。本文提出的GLMA算法流程如算法2所示。

算法2基于遺傳算法的鏈路映射算法流程

其中，個體表示一個可行的VN劃分方案，種群表示一組個體形成的集合，基因表示一個虛擬節(jié)點。用長度為I（虛擬節(jié)點個數(shù)）的串表示問題的解，即染色體。基于遺傳算法的鏈路映射方案執(zhí)行過程如下：首先，輸入虛擬網(wǎng)絡(luò)GV＝（NV，LV），物理網(wǎng)絡(luò)GS＝（NS，LS）。 采用自然數(shù)編碼，自然數(shù)在0到z之間排序，不同的排序方式表示不同的路徑選擇，每條染色體都是一種映射方案。其中，為了使初始種群在整個解空間中均勻分布，采用部分隨機方法生成初始種群。在適應(yīng)度函數(shù)方面，染色體的適應(yīng)度越大，其性能越好。因此，將目標函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)

式中，fc為染色體c的適應(yīng)度。選擇操作采用的是輪盤賭選擇法［13］，適應(yīng)度值越好的個體被選擇概率越大。在利用輪盤賭選擇策略時，首先需要解決的是如何將適應(yīng)度值轉(zhuǎn)化為選擇概率。具體步驟如下：

（1）累加種群的適應(yīng)度值，并將累加值作為分母。

（2）將每個個體的適應(yīng)度值作為分子，得到每個個體被選擇的概率。

（3）制作輪盤，將每個個體所得到的被選擇概率設(shè)定為在圓盤上所占份額。

（4） 隨機產(chǎn)生一個［0，1］區(qū)間內(nèi)的隨機數(shù)，若該隨機數(shù)小于或等于個體的被選擇的概率，則該個體被選擇。

選擇單個個體的概率為

交叉操作采用的是單點交叉算法［14］，在個體染色體中隨機設(shè)置一個交叉點，然后在該點相互交換兩個父母染色體的部分染色體。例如式（22）中兩個相同長度的二進制串。

單點交叉包括選擇一個均勻分布的隨機整數(shù)k∈［1，length（A1）－1］， 在A1和A2間交換k＋1到length（A1）之間的各變量，如果k＝3，則A1和A2變?yōu)?/p>

變異操作采用的是反轉(zhuǎn)變異算子［15］，在父代中隨機選擇兩個點，然后反轉(zhuǎn)之間的部分，則交叉后的A1和A2變?yōu)?/p>

變異后轉(zhuǎn)向個體適應(yīng)度評價，若迭代次數(shù)未達到最大值，則開始新的循環(huán)，最終得到懲罰函數(shù)的近似最優(yōu)解。

3 仿真與分析

本文使用Matlab對所提的基于遺傳算法的鏈路映 射 算 法 （Genetic?algorithm based Mapping Algorithm，GLMA）進行仿真，并在服務(wù)接收率、可靠性、時延等方面與負載均衡隨機映射算法（Load?balancing Random Mapping Algorithm，LRMA）［16］和貪婪資源映射算法（Greedy?based Resource Mapping Algorithm，GRMA）［17］進行比較。 其中，LRMA 算法通過最優(yōu)化網(wǎng)絡(luò)負載均衡，選擇最短路徑進行鏈路映射，GRMA算法是一種經(jīng)典的虛擬網(wǎng)絡(luò)映射算法，通過貪婪算法選擇最高可靠性鏈路進行虛擬網(wǎng)絡(luò)映射。

仿真場景是模擬我國江蘇省智能電網(wǎng)通信網(wǎng)絡(luò)。根據(jù)智能電網(wǎng)差異化的業(yè)務(wù)需求，本文將電力業(yè)務(wù)根據(jù)時延敏感度分為5類（見表1）：電網(wǎng)控制和保護類業(yè)務(wù)、配電自動化、分布式能源、交互式音頻和視頻、用電信息采集。利用 GT?ITM（Georgia Tech Internetwork Topology Models）工具生成參數(shù)如表2和表3所示，其中，虛擬網(wǎng)絡(luò)有8個節(jié)點和15條鏈路，虛擬網(wǎng)路的到達時間為Poisson分布，生存周期為指數(shù)分布，最長等待時限在0.1～1之間均勻分布。本文分別對5類業(yè)務(wù)進行了模擬，業(yè)務(wù)請求數(shù)量分別設(shè)為 5，10，15，20，25，30，35。 為保證實驗的準確性，進行10次實驗，取結(jié)果的平均值。

表1 電力業(yè)務(wù)指標

表2 節(jié)點資源參數(shù)表

表3 鏈路資源參數(shù)表

圖3為3種算法服務(wù)接收率的比較，其中基于GLMA的服務(wù)接收率最高。其次是LRMA。GRMA由于沒有考慮基礎(chǔ)設(shè)施網(wǎng)絡(luò)的負載均衡，導(dǎo)致服務(wù)接收率較低，LRMA算法沒有對流量進行優(yōu)先級排序，不能保證服務(wù)獲得高可靠性鏈路，業(yè)務(wù)接收失敗率較高。而本文的GLMA結(jié)合了LRMA和GRMA的優(yōu)點，針對業(yè)務(wù)的不同優(yōu)先級提供不同的鏈路，根據(jù)業(yè)務(wù)不同屬性參數(shù)分配不同可靠性的鏈路，在業(yè)務(wù)接收率方面具有優(yōu)異的性能。

圖3 服務(wù)接收率的比較

圖4為3種算法的懲罰函數(shù)比較，其中基于GLMA的懲罰函數(shù)最小，其次是LRMA，GRMA的懲罰函數(shù)值最大。這是因為GRMA沒有考慮到負載均衡問題，導(dǎo)致懲罰函數(shù)中的負載率過大；而LRMA由于沒有進行優(yōu)先級排序，導(dǎo)致懲罰函數(shù)中的時延過大。本文的GLMA充分考慮到了業(yè)務(wù)的時延敏感特性，在業(yè)務(wù)請求層和鏈路映射層都加入了時延屬性，同時也將負載率納入主要影響因素之中。已知懲罰函數(shù)越小，服務(wù)可靠性越高，因此，GLMA具有最高的服務(wù)可靠性。

圖4 懲罰函數(shù)比較

圖5為3種算法平均時延對比，其中基于GLMA的平均時延最小，且隨著請求的不斷增加，平均時延的增長幅度也較小，而其他兩種算法的平均時延增加較為明顯。這是因為GLMA算法考慮了窗口中待映射請求的等待時間屬性參數(shù)和時延敏感度，對等待時間較長的請求優(yōu)先映射，同時，考慮了鏈路映射過程中的時延問題，而其他兩種算法則未考慮時延因素。因此，GLMA算法在平均時延方面明顯優(yōu)于其他兩種算法。

圖5 平均時延對比

4 結(jié)束語

本文提出了基于電力業(yè)務(wù)時延敏感度和服務(wù)可靠性的虛擬網(wǎng)絡(luò)映射方案，從電力業(yè)務(wù)的時延需求出發(fā)，提出了基于時延敏感度的業(yè)務(wù)請求排序，縮短虛擬網(wǎng)絡(luò)請求的等待時間并提高虛擬網(wǎng)絡(luò)請求接收率；然后，將拓撲屬性和相鄰節(jié)點重要性作為排序參數(shù)，對節(jié)點進行排序；最后，在鏈路映射層，構(gòu)建了基于鏈路時延和鏈路負載比方差的可靠性懲罰函數(shù)，提出了基于遺傳算法的鏈路映射算法，得到最優(yōu)映射鏈路。仿真結(jié)果表明，所提方法保障了電力業(yè)務(wù)的時延和可靠性需求，同時有效提高了虛擬映射請求接收率。