曾 瑛，蔣康明，楊 嬌，李 彬

（1．廣東電網(wǎng)公司 電力調(diào)度控制中心，廣州510600；2．華北電力大學(xué) 電氣與電子工程學(xué)院，北京102206）

電力市場(chǎng)改革的深化和電力行業(yè)信息化程度的提高使電力業(yè)務(wù)種類和數(shù)量迅速增加［1］，對(duì)通信指標(biāo)的需求多樣化，為了確保服務(wù)質(zhì)量（QoS），路由選擇不再僅僅將“可達(dá)”和“最短路徑”作為衡量標(biāo)準(zhǔn)，而是希望考慮電力業(yè)務(wù)具體通信需求和網(wǎng)絡(luò)的動(dòng)態(tài)特性等要求。因此，如何滿足電力業(yè)務(wù)通信需求、加速算法的收斂速度等問(wèn)題成為設(shè)計(jì)面向電力業(yè)務(wù)路由協(xié)議時(shí)重點(diǎn)考慮的問(wèn)題。文獻(xiàn)［2］介紹了在路由算法參數(shù)中建立一個(gè)乘性QoS約束參數(shù)，在傳統(tǒng)的路由算法基礎(chǔ)上加入可用性參數(shù)來(lái)搜索可靠性最佳路徑的方法；文獻(xiàn)［3］提出了一種考慮負(fù)載均衡的新型聯(lián)合路由算法，具有負(fù)載均衡、優(yōu)化網(wǎng)絡(luò)資源和降低端到端時(shí)延等優(yōu)點(diǎn)；文獻(xiàn)［4－8］對(duì)電力通信網(wǎng)絡(luò)的可靠性、風(fēng)險(xiǎn)評(píng)估、部分網(wǎng)絡(luò)失效后的自愈方法等內(nèi)容進(jìn)行了研究，但尚未研究電力通信網(wǎng)絡(luò)在帶寬、時(shí)延和丟包率等多約束條件下路徑查找問(wèn)題，也未建立面向電力業(yè)務(wù)的路由算法。

針對(duì)多約束路由問(wèn)題的求解，一般采用啟發(fā)式算法求解，如遺傳算法（genetic algorithm，GA）、蟻群算法（ant colony optimization，ACO）、模擬退火算法和粒子群算法等。但是由于這些算法本身存在一些缺點(diǎn)，如遺傳算法很難得到最優(yōu)解，一般是計(jì)算得到較優(yōu)解，在較優(yōu)解的基礎(chǔ)上計(jì)算得到最優(yōu)解，所需要的時(shí)間將成倍增加；蟻群算法求解多約束路由時(shí)速度慢，容易出現(xiàn)早熟收斂和停滯現(xiàn)象。針對(duì)遺傳算法和蟻群算法的不足，國(guó)內(nèi)外學(xué)者從不同角度提出了改進(jìn)算法［9－12］，在一定程度上提高了算法的全局搜索能力和收斂速度。量子遺傳算法［10］（quantum genetic algorithm，QGA）是將遺傳算法與量子計(jì)算理論相結(jié)合而發(fā)展起來(lái)的一種新遺傳算法，具有種群規(guī)模小而不影響算法性能、同時(shí)具有開發(fā)和探索能力、收斂速度快等特點(diǎn)，在求解組合優(yōu)化問(wèn)題時(shí)與遺傳算法相比表現(xiàn)出優(yōu)勢(shì)。

針對(duì)以上分析，筆者基于量子遺傳算法的基本原理，提出一種面向電力業(yè)務(wù)的路由算法。該算法根據(jù)電力業(yè)務(wù)對(duì)通信指標(biāo)的不同要求，對(duì)其進(jìn)行劃分類別，明確業(yè)務(wù)對(duì)通信指標(biāo)的要求；路由起始節(jié)點(diǎn)根據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)和電力業(yè)務(wù)類別調(diào)用相應(yīng)的適應(yīng)度函數(shù)，利用量子遺傳算法進(jìn)行路由選擇。該算法一方面考慮了傳統(tǒng)技術(shù)中的通信指標(biāo)對(duì)路由鏈路的影響，另一方面構(gòu)建了適應(yīng)度函數(shù)，對(duì)電力系統(tǒng)的各種業(yè)務(wù)按照其權(quán)重值進(jìn)行考慮。綜合考慮最短路徑和針對(duì)電力業(yè)務(wù)特點(diǎn)的約束條件，尋出滿足電力業(yè)務(wù)特性的最優(yōu)路徑，仿真結(jié)果表明了該算法的有效性。

1 電力通信網(wǎng)路由問(wèn)題的網(wǎng)絡(luò)模型

針對(duì)電力通信網(wǎng)的物理結(jié)構(gòu)和業(yè)務(wù)需求情況，應(yīng)該合理選擇路由，滿足業(yè)務(wù)的QoS要求，同時(shí)提高電力通信網(wǎng)的服務(wù)質(zhì)量，平衡網(wǎng)絡(luò)負(fù)載。電力通信網(wǎng)中，時(shí)延、帶寬和丟包率是三個(gè)重要的參數(shù)，各電力業(yè)務(wù)對(duì)三者的要求也不盡相同。根據(jù)對(duì)通信指標(biāo)的不同要求，將電力系統(tǒng)現(xiàn)有業(yè)務(wù)劃分為五種類別，具體為：

1）高可靠寬帶實(shí)時(shí)業(yè)務(wù)，包括電力市場(chǎng)營(yíng)銷、電能質(zhì)量監(jiān)測(cè)系統(tǒng)等；

2）高可靠窄帶實(shí)時(shí)業(yè)務(wù)，包括繼電保護(hù)和安穩(wěn)系統(tǒng)；

3）可靠寬帶實(shí)時(shí)業(yè)務(wù)，包括視頻會(huì)議；

4）可靠窄帶實(shí)時(shí)業(yè)務(wù)，包括調(diào)度自動(dòng)化和電能計(jì)量；

5）低可靠窄帶非實(shí)時(shí)業(yè)務(wù)，包括辦公自動(dòng)化、管理信息業(yè)務(wù)和調(diào)度管理信息系統(tǒng)。

在研究路由問(wèn)題時(shí)，電力通信網(wǎng)可表示為一個(gè)加權(quán)圖G（V，E），其中V表示節(jié)點(diǎn)集，E表示連接節(jié)點(diǎn)的通信鏈路集，即G是由一組點(diǎn)V＝｛1，2，…，N｝和一組連接V中節(jié)點(diǎn)的邊E＝V×V組成。設(shè)s和d分別表示源節(jié)點(diǎn)和目的節(jié)點(diǎn)，任意一條路徑x＝｛s，i，…，j，d｝表示源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑。

針對(duì)電力業(yè)務(wù)對(duì)通信指標(biāo)要求的不同，在為其進(jìn)行路徑選擇時(shí)應(yīng)考慮各類電力業(yè)務(wù)的具體通信需要，根據(jù)業(yè)務(wù)對(duì)時(shí)延、帶寬和丟包率的要求構(gòu)造相應(yīng)的目標(biāo)函數(shù)，用以獲得符合業(yè)務(wù)通信特性的傳輸路徑。假設(shè)x為第i類業(yè)務(wù)的一條可用路徑，i∈｛1，2，…，5｝，則x滿足：

式中：FiD（x），F(xiàn)iB（x）和FiL（x）為目標(biāo)函數(shù)；D（x）為路徑x的時(shí)延，Dmax為網(wǎng)絡(luò)中第i類電力業(yè)務(wù)可容忍的時(shí)延最大值；B為網(wǎng)絡(luò)中第i類電力業(yè)務(wù)要求的帶寬，B（x）為路徑x的可用帶寬，Bmax為可行解中的可用帶寬最大值，Bmin為可行解中的可用帶寬最小值；L（x）為路徑x的丟包率，Lmax為網(wǎng)絡(luò)中第i類電力業(yè)務(wù)可容忍的丟包率最大值。

該問(wèn)題屬于多目標(biāo)多約束優(yōu)化問(wèn)題，在多數(shù)條件下，無(wú)法保證FiD（x），F(xiàn)iB（x）和FiL（x）均取得最大值，因此構(gòu)造第i（i＝1，2，…，5）類電力業(yè)務(wù)優(yōu)化目標(biāo)函數(shù)為：

其中，權(quán)重值wi1，wi2，wi3是正實(shí)數(shù)，具體數(shù)值取決于每類電力業(yè)務(wù)對(duì)時(shí)延、帶寬和可靠性的不同要求，且滿足wi1＋wi2＋wi3＝1。

2 量子遺傳算法的基本原理

2．1 量子比特編碼

區(qū)別與二進(jìn)制編碼、實(shí)數(shù)編碼和樹形編碼等已有的GA編碼方式，QGA采用一種基于量子比特（qubit）的編碼方式［10］，即用qubit來(lái)存儲(chǔ)和表達(dá)一個(gè)基因，量子比特可以處于0和1兩個(gè)本征態(tài)或兩個(gè)狀態(tài)的任意疊加，其狀態(tài)表示為：

其中，｜α｜2，｜β｜2分別表示量子比特處于“0”態(tài)和“1”態(tài)的概率且滿足｜α｜2＋｜β｜2＝1。

一個(gè)由n個(gè)qubit構(gòu)成的量子染色體可以描述為：

其中，｜αr｜2＋｜βr｜2＝1（r＝1，2，…，n），該染色體可同時(shí)表達(dá)2n個(gè)態(tài)的信息，保證了種群的多樣性，隨著量子比特概率幅趨于1或0，染色體收斂到單一態(tài)，種群多樣性呈逐漸減小趨勢(shì)，算法收斂。

在對(duì)電力通信網(wǎng)路由問(wèn)題進(jìn)行求解時(shí)，量子染色體的量子比特?cái)?shù)由電力通信網(wǎng)節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)中最大鄰接點(diǎn)數(shù)共同確定。例如在一個(gè)N個(gè)節(jié)點(diǎn)組成的電力通信網(wǎng)，設(shè)節(jié)點(diǎn)的最大鄰接點(diǎn)數(shù)為l，求解k使得2k－1≤l≤2k，則編碼時(shí)量子染色體的量子比特?cái)?shù)為n＝N×k。

2．2 量子測(cè)量

通過(guò)量子編碼得到量子比特概率幅表示的染色體，對(duì)編碼的染色體實(shí)施量子測(cè)量操作，從而得到長(zhǎng)度為n的二進(jìn)制字符串p＝｛x1，…，xr，…，xn｝，xr為二進(jìn)制字符0或1。具體測(cè)量過(guò)程為：隨機(jī)產(chǎn)生一個(gè)數(shù)字R（R∈［0，1］），若R 大于｜αr｜2（r＝1，2，…n），xr取1，反之取0。

2．3 量子比特譯碼

為了計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值，需對(duì)編碼染色體實(shí)施量子比特譯碼［13］操作，將二進(jìn)制的個(gè)體轉(zhuǎn)換為十進(jìn)制，得到具體路徑。首先生成N×l矩陣H，其中H（i，j）表示第i個(gè)節(jié)點(diǎn)的第j個(gè)相鄰節(jié)點(diǎn)，若與i相鄰的節(jié)點(diǎn)數(shù)小于j，則H（i，j）＝0。譯碼時(shí)，將測(cè)量得到的二進(jìn)制字符串p＝｛x1，…，xr，…，xn｝分為N 組，每組量子比特?cái)?shù)為k，把第i組的量子比特?cái)?shù)視為一個(gè)二進(jìn)制字符串，并將其轉(zhuǎn)換為十進(jìn)制數(shù)j，表示第i個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為H（i，j＋1），并尋找節(jié)點(diǎn) H（i，j＋1）的下一個(gè)節(jié)點(diǎn)，直到找到終點(diǎn)N，譯碼過(guò)程需刪除無(wú)效路徑。

2．4 量子變異

為了加快算法收斂，需對(duì)種群進(jìn)行變異操作，在量子理論中，量子比特狀態(tài)的轉(zhuǎn)換是通過(guò)量子門實(shí)現(xiàn)的，常用的量子門有：非門、異或門、受控異或門和旋轉(zhuǎn)門。量子旋轉(zhuǎn)門用旋轉(zhuǎn)角來(lái)表征染色體變異，并在變異過(guò)程中加入當(dāng)前最優(yōu)個(gè)體信息，達(dá)到加速算法收斂的目的。由于量子旋轉(zhuǎn)門的參數(shù)具有可調(diào)整性，通用性強(qiáng)，故采用量子旋轉(zhuǎn)門來(lái)實(shí)現(xiàn)染色體的變異。量子旋轉(zhuǎn)門為2×2的矩陣，具體表示為其中，量子門的旋轉(zhuǎn)角θ＝f（xr，br）×Δθ，f（xr，br）為旋轉(zhuǎn)門方向取值為1，－1或0。xr表示當(dāng)前染色體的第r位，br表示當(dāng)前最優(yōu)染色體的第r位，Δθ為旋轉(zhuǎn)角大小，用以控制算法的收斂速度，太大可能導(dǎo)致算法運(yùn)行結(jié)果發(fā)散或早熟得到局部最優(yōu)解。

3 電力通信網(wǎng)路由選擇策略

在為電力業(yè)務(wù)選擇路由時(shí)，首先根據(jù)業(yè)務(wù)對(duì)通信指標(biāo)的需求判定所屬類別，確定目標(biāo)函數(shù)及可容忍時(shí)延最大值、最小可用帶寬和可容忍丟包率最大值約束條件。根據(jù)網(wǎng)絡(luò)中時(shí)延、帶寬和節(jié)點(diǎn)的丟包率大小選擇滿足QoS約束條件的路徑，利用量子遺傳算法尋找符合業(yè)務(wù)通信指標(biāo)要求的最佳路徑，具體步驟如下。

1）初始化。遺傳代數(shù)t＝0，種群Q（t）＝Q（0），種群規(guī)模為K，并對(duì)種群進(jìn)行量子遺傳編碼；經(jīng)過(guò)編碼后可得Q（t）＝｛qt1，qt2，…qtK｝，其中，

初始化時(shí)，Q（0）的全部染色體的所有基因的概率幅被初始化為

2）對(duì)Q（t）的所有個(gè)體實(shí)施一次測(cè)量得到P（t），含有K個(gè)確定的個(gè)體，即

3）對(duì)P（t）進(jìn)行譯碼得到具體路徑，將路徑信息（包括時(shí)延、可用帶寬和丟包率）代入式（3），進(jìn)行適應(yīng)度評(píng)估；

4）選擇并保存最優(yōu)個(gè)體及其適應(yīng)度值，作為該種群個(gè)體下一步進(jìn)化的目標(biāo)值；

5）驗(yàn)證得到的最優(yōu)個(gè)體是否滿足最佳路由條件，若是，則結(jié)束并輸出當(dāng)前最優(yōu)個(gè)體，否則繼續(xù)；

6）量子變異操作，采用量子旋轉(zhuǎn)門變異操作更新Q（t），得到下一代種群Q（t＋1）；

7）t＝t＋1，轉(zhuǎn)回2）。

4 仿真實(shí)驗(yàn)與分析

為驗(yàn)證所提算法的有效性，筆者使用 Matlab2010Ra仿真平臺(tái)對(duì)ACO和本文算法進(jìn)行仿真對(duì)比分析。設(shè)定網(wǎng)絡(luò)仿真拓?fù)浣Y(jié)構(gòu)，包含隨機(jī)生成的20個(gè)節(jié)點(diǎn)（V1～V20），49條邊及隨機(jī)生成的各鏈路時(shí)延、帶寬和節(jié)點(diǎn)丟包率，其中（D，B）表示鏈路上的時(shí)延（D／ms）和帶寬（B／MHz）。在仿真實(shí)驗(yàn)中算法具體參數(shù)設(shè)定為：QGA算法最大迭代次數(shù)為200，種群大小為40，節(jié)點(diǎn)的最大鄰接點(diǎn)數(shù)為7，編碼時(shí)量子染色體的量子比特?cái)?shù)為60，量子旋轉(zhuǎn)門參數(shù)的設(shè)置參考文獻(xiàn)［10］；ACO算法最大迭代次數(shù)為200，螞蟻數(shù)量為40，第t代螞蟻m從i節(jié)點(diǎn)轉(zhuǎn)移到j(luò)節(jié)點(diǎn)的概率為

其中ηij（t）為啟發(fā)函數(shù)，

表示i節(jié)點(diǎn)轉(zhuǎn)移到j(luò)節(jié)點(diǎn)的期望程度，仿真時(shí)取信息素重要程度因子α＝1，啟發(fā)函數(shù)重要程度因子β＝1，信息素更新公式

取信息素?fù)]發(fā)因子ρ＝0．5，第m只螞蟻從i節(jié)點(diǎn)轉(zhuǎn)移到j(luò)節(jié)點(diǎn)路徑上釋放的信息素濃度

表1 電力業(yè)務(wù)對(duì)通信指標(biāo)的具體要求

假設(shè)業(yè)務(wù)要求帶寬為20MHz，路徑最小時(shí)延控制在100ms以內(nèi)，丟包率不超過(guò)0．3。首先根據(jù)業(yè)務(wù)對(duì)通信指標(biāo)的要求，判定該業(yè)務(wù)為高可靠寬帶實(shí)時(shí)業(yè)務(wù)，對(duì)應(yīng)的目標(biāo)函數(shù)為F1（x）＝0．2F1D（x）＋0．6F1B（x）＋0．2F1L（x）。圖2和圖3分別給出了s＝1，d＝20和s＝2，d＝19時(shí)，QGA與ACO在求解業(yè)務(wù)路由問(wèn)題時(shí)的收斂特性。顯然，QGA種群大小和ACO螞蟻數(shù)目K一樣時(shí)，QGA能更快地收斂到最優(yōu)路徑，并且QGA求得的最優(yōu)路徑要優(yōu)于ACO求得的最優(yōu)路徑。

圖2 s＝1，d＝20時(shí)，QGA與ACO的收斂特性

圖3 s＝2，d＝19時(shí)，QGA與ACO的收斂特性

表2和表3給出了s＝1，d＝20和s＝2，d＝19時(shí)，QGA和ACO求得最優(yōu)路徑P及目標(biāo)函數(shù)F值和路徑時(shí)延、帶寬和丟包率的值。由表中數(shù)據(jù)可知，所提算法不僅可以找到滿足電力業(yè)務(wù)通信要求的路徑，而且最優(yōu)解均優(yōu)于ACO算法求得的最優(yōu)解，且當(dāng)兩算法求得的最優(yōu)解比較相近時(shí)，該算法找到最優(yōu)解的時(shí)延和丟包率均小于ACO算法求得的最優(yōu)解的時(shí)延和丟包率，說(shuō)明該算法在滿足電力業(yè)務(wù)通信要求的條件下，進(jìn)一步達(dá)到了優(yōu)化網(wǎng)絡(luò)資源利用、負(fù)載均衡的目的。

表2 s＝1，d＝20時(shí)QGA和ACO最優(yōu)路徑值對(duì)比

表3 s＝2，d＝19時(shí)QGA和ACO最優(yōu)路徑值對(duì)比

表4給出了滿足業(yè)務(wù)要求，目標(biāo)函數(shù)不同的算法求得的最優(yōu)解。由表中數(shù)據(jù)分析可知，針對(duì)電力業(yè)務(wù)對(duì)通信指標(biāo)具體要求的不同，相同源節(jié)點(diǎn)和目的節(jié)點(diǎn)，相同約束條件下，當(dāng)業(yè)務(wù)類型為可靠寬帶實(shí)時(shí)業(yè)務(wù)時(shí)，對(duì)應(yīng)的目標(biāo)函數(shù)為

F3（x）＝0．3F3D（x）＋0．6F3B（x）＋0．1F3L（x），利用所提算法找到最優(yōu)路徑為（2，1，4，10，19）；而當(dāng)業(yè)務(wù)類型為高可靠窄帶實(shí)時(shí)業(yè)務(wù)時(shí)，對(duì)應(yīng)的目標(biāo)函數(shù)為

F2（x）＝0．8F2D（x）＋0．1F2B（x）＋0．1F2L（x），找到最優(yōu)路徑為（2，3，4，10，19）。當(dāng)不同的業(yè)務(wù)類型，在相同的通信網(wǎng)絡(luò)，并在有QoS約束的條件下，所求最優(yōu)路徑會(huì)隨之改變。因此，有必要針對(duì)電力業(yè)務(wù)對(duì)通信指標(biāo)的不同要求，對(duì)其進(jìn)行劃分類別，根據(jù)類別進(jìn)行路由選擇。

表4 s＝2，d＝19時(shí)不同業(yè)務(wù)類型的最優(yōu)路徑值

5 結(jié)論

本研究提出了一種基于量子遺傳算法的電力通信網(wǎng)絡(luò)路由選擇策略，一方面考慮了傳統(tǒng)技術(shù)中的通信指標(biāo)對(duì)路由鏈路的影響，另一方面根據(jù)電力業(yè)務(wù)對(duì)通信指標(biāo)要求程度構(gòu)建目標(biāo)函數(shù)。綜合考慮最短路徑和針對(duì)電力業(yè)務(wù)特點(diǎn)的QoS約束條件，利用量子遺傳算法尋出滿足電力業(yè)務(wù)特性的最優(yōu)路徑。從實(shí)驗(yàn)結(jié)果可以看出，按照對(duì)通信指標(biāo)的不同需求，對(duì)電力業(yè)務(wù)劃分類別進(jìn)行路由選擇，能夠?qū)こ鰸M足電力業(yè)務(wù)特性的最佳路徑，且算法的收斂性比較理想，能夠在較短的時(shí)間內(nèi)收斂到最優(yōu)解。

［1］ 王勇，利韶聰，陳寶仁．電力通信業(yè)務(wù)應(yīng)用及發(fā)展分析［J］．電力系統(tǒng)通信，2010，31（217）：44－47．

［2］ 王宇，李樂(lè)民．基于可用性的 QoS選路研究［J］．計(jì)算機(jī)應(yīng)用研究，2009，26（5）：1844－1846．

［3］ 李培源，龔涌濤，顧畹儀．WDM 網(wǎng)絡(luò)路由計(jì)算中的平衡最短路算法［J］．北京郵電大學(xué)學(xué)報(bào)，2004，27（2）：14－18．

［4］ 王慶鑄，卓秀者，劉逢清．電力光纖通信網(wǎng)絡(luò)的最佳路徑選擇［J］．電力系統(tǒng)通信，2012，33（231）：18－22．

［5］ 吳潤(rùn)澤，汪波濤，唐良瑞，等．新型ICT網(wǎng)絡(luò)中的一種動(dòng)態(tài)路由波長(zhǎng)分配算法［J］．電力系統(tǒng)保護(hù)與控制，2010，38（22）：48－51．

［6］ 吳潤(rùn)澤，祁宏鵬，唐良瑞．新一代電力ICT網(wǎng)絡(luò)中基于DiR保護(hù)環(huán)的生存性路由算法［J］．電力系統(tǒng)保護(hù)與控制，2011，39（16）：25－29．

［7］ 龔鋼軍，韓軍偉，朱娟溪，等．配電無(wú)線傳感網(wǎng)功率控制路由優(yōu)化算法［J］．電力系統(tǒng)保護(hù)與控制，2012，40（22）：129－134．

［8］ 熊小伏，吳玲燕，陳星田．滿足廣域保護(hù)通信可靠性和時(shí)延要求的路由選擇方法［J］．電力系統(tǒng)自動(dòng)化，2011，35（3）：44－48．

［9］ Tang Kezong，Sun Tingkai，Yang Jingyu．An improved genetic algorithm based on a novel selection strategy for nonlinear programming problems［J］．Computers and Chemical Engineering，2011，35（4）：615－621．

［10］ 楊淑嬡，劉芳，焦李成．一種基于量子染色體的遺傳算法［J］．西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)報(bào)），2004，31（1）：76－81．

［11］ Yang Jingan，Zhuang Yanbin．An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem ［J］．Applied Soft Computing，2010，10（2）：653－660．

［12］ Twomey C，Stutzle T，Dorigo M．An analysis of communication policies for homogeneous multi－colony ACO algorithms［J］．Information Sciences，2010，180（12）：2390－2404．

［13］ 劉欣，李飛，鄭寶玉．基于量子遺傳算法的多約束 QoS路由選擇算法［J］．南京郵電大學(xué)學(xué)報(bào)（自然科學(xué)報(bào)），2011，31（2）：31－35．