胡正偉，謝志遠(yuǎn)，謝榮圓

（華北電力大學(xué) 電子與通信工程系，河北 保定 071003）

0 引言

智能電網(wǎng)“智能化”的實現(xiàn)是以實時準(zhǔn)確的信息為基礎(chǔ)，即通信系統(tǒng)是智能電網(wǎng)的一個重要核心組成部分。電力線通信（PLC）技術(shù)作為智能電網(wǎng)的通信技術(shù)之一，在一些場合（如遠(yuǎn)程智能抄表、路燈控制等領(lǐng)域）有著重要的應(yīng)用價值［1］。

隨著智能電網(wǎng)技術(shù)的發(fā)展，配電網(wǎng)通信業(yè)務(wù)大量涌入，對數(shù)據(jù)業(yè)務(wù)的可靠性和有效性等指標(biāo)提出了更高的要求?；陔娏€通信方式進(jìn)行配電網(wǎng)通信業(yè)務(wù)的傳輸可以實現(xiàn)業(yè)務(wù)分流，在一定程度上解決了業(yè)務(wù)量激增的問題。但由于電力線信道的物理特征［2-4］及噪聲［5-9］等因素的影響，如何保障業(yè)務(wù)傳輸?shù)目煽啃院陀行允且粋€亟需解決的問題。

服務(wù)質(zhì)量（QoS）是衡量通信網(wǎng)絡(luò)業(yè)務(wù)傳輸能力優(yōu)劣的標(biāo)準(zhǔn)之一。因此，可以通過判斷電力線信道特性是否滿足業(yè)務(wù)的QoS參數(shù)要求來評價其是否支持某配電網(wǎng)業(yè)務(wù)的傳輸。鑒于電力線信道的惡劣環(huán)境，一般采用中繼路由［10-16］來實現(xiàn)遠(yuǎn)程數(shù)據(jù)傳輸。為了支持配電網(wǎng)業(yè)務(wù)的遠(yuǎn)距離傳輸，同樣通過中繼路由來實現(xiàn)遠(yuǎn)程業(yè)務(wù)傳輸。因此需要有效的路由算法來選擇中繼路由，以達(dá)到滿足業(yè)務(wù)QoS參數(shù)需求的目標(biāo)。由于業(yè)務(wù)傳輸一般需要滿足多個QoS參數(shù)條件，因此這就屬于多條件約束下的路由搜索問題。

目前在電力線通信領(lǐng)域，很多文獻(xiàn)提出了面向單一約束條件的路由搜索算法，如距離、信噪比、抗毀性等。文獻(xiàn)［16］采用蟻群算法實現(xiàn)了時延和誤碼率這2個約束條件下的電力線通信路由搜索算法。

由于遺傳算法不需要復(fù)雜的數(shù)學(xué)計算，而且具有很強(qiáng)的魯棒性，因此在實際工程技術(shù)領(lǐng)域得到了廣泛的應(yīng)用。在電力線通信應(yīng)用領(lǐng)域，文獻(xiàn)［17］采用遺傳算法實現(xiàn)了以跳數(shù)為單一約束條件的路由搜索方法；文獻(xiàn)［18］采用量子遺傳算法實現(xiàn)了電力線通信中的資源分配問題；文獻(xiàn)［19］采用遺傳算法進(jìn)行了網(wǎng)絡(luò)狀態(tài)信息的獲?。晃墨I(xiàn)［20］采用遺傳算法對電力線噪聲的提取和分析進(jìn)行了相關(guān)研究。但采用遺傳算法實現(xiàn)多QoS參數(shù)約束條件下的路由搜索算法尚未有相關(guān)文獻(xiàn)報道。

為了實現(xiàn)多QoS參數(shù)約束條件下的路由選擇，本文提出了一種基于遺傳算法的多QoS參數(shù)約束條件下的電力線通信路由搜索方法。主要特點有：使用亂序染色體編碼方法不僅實現(xiàn)了搜索空間的完備性，而且可用定長染色體表示不同跳數(shù)的路由；采用最佳保留選擇機(jī)制，保證了最終得到的結(jié)果為歷代出現(xiàn)過的具有最高適應(yīng)度的路徑；源節(jié)點和目的節(jié)點均不參與亂序編碼、交叉和變異，可以有效避免無效染色體的生成，提高了搜索效率；采用適應(yīng)函數(shù)的懲罰機(jī)制引入了Best Effort工作模式，當(dāng)不存在滿足QoS參數(shù)約束條件的路由時，系統(tǒng)可暫時工作在不滿足QoS參數(shù)約束條件的工況下；算法應(yīng)用的前提是電力線信道的QoS參數(shù)已經(jīng)獲得。

1 多QoS參數(shù)約束條件

QoS參數(shù)可以根據(jù)不同配電網(wǎng)業(yè)務(wù)的需求選擇帶寬、誤碼率、時延、時延抖動等參數(shù)中的一個或一組來定義。當(dāng)選擇一組參數(shù)來定義QoS參數(shù)時，稱其為多QoS參數(shù)約束條件，即網(wǎng)絡(luò)需要滿足多個QoS參數(shù)的需求。

本文定義的QoS參數(shù)包括：帶寬約束B0、誤碼率約束E0、時延約束D0、時延抖動約束J0。

圖1為一條多跳路由示意圖，共n跳。若B（hi）、E（hi）、D（hi）、J（hi）是跳數(shù)為hi的 4 個 QoS 參數(shù)，則整條路由的多QoS參數(shù)約束條件可描述為式（1）—（4）。

其中，p為某跳路由。

圖1 多跳路由Fig.1 Multi-hop routing

當(dāng)同時滿足約束條件式（1）—（4）時，才認(rèn)為滿足QoS參數(shù)需求。遺傳算法以式（1）—（4）作為約束條件進(jìn)行路由搜索。

2 遺傳算法原理與實現(xiàn)方案

將遺傳算法應(yīng)用于路由搜索，首先需要建立遺傳算法術(shù)語與路由搜索術(shù)語之間的對應(yīng)關(guān)系。表1描述了與算法實現(xiàn)相關(guān)部分的對應(yīng)關(guān)系。

表1 遺傳算法術(shù)語與路由搜索術(shù)語的對應(yīng)關(guān)系Table 1 Genetic algorithm terms and corresponding routing search terms

2.1 種群初始化

種群初始化需要完成2個任務(wù)：一是確定種群的數(shù)量，即染色體的數(shù)量，即確定每代的搜索空間；二是對染色體進(jìn)行編碼。

2.1.1 種群數(shù)量的確定

大種群數(shù)量可以含有較多的路由通路，為遺傳算法提供了較大的搜索空間，可以改進(jìn)搜索質(zhì)量，防止陷入局部最優(yōu)，但是會增加個體適應(yīng)性評價的工作量，從而使收斂速度降低。一般情況下種群數(shù)量建議取值為20～200。

局部最優(yōu)是任何啟發(fā)式算法需盡可能避免的問題之一。因此，當(dāng)節(jié)點數(shù)目較多時，在滿足收斂速度的前提下，可以通過適當(dāng)增加種群數(shù)量來防止陷入局部最優(yōu)問題的發(fā)生。

2.1.2 染色體編碼

（1）染色體編碼原理。

長度為L 的染色體 A=｛A1，A2，A3，…，Ai，…，AL｝含有 L 個基因。Ai=｛ai1，ai2，…，aij，…，aiki｝（i=1，2，…，L；j=1，2，…，ki）為染色體 A 的第i位上的基因，其中aij為第i位基因Ai的第j個等位基因的取值，ki為第i位基因Ai的等位基因的數(shù)量。等位基因表示基因的特征值，即相同基因位的基因取值。染色體編碼原理如圖2所示。

圖2 染色體編碼原理Fig.2 Principle of chromosome encoding

（2）亂序染色體編碼方案。

為了能夠使用遺傳算法進(jìn)行路由搜索，搜索空間必須能夠包含所有路由通路，且不能重復(fù)，即編碼具有完備性和非冗余性。

鑒于不同路由通路具有如下特征：跳數(shù)不同，即路由通路經(jīng)過的節(jié)點數(shù)量不同；跳數(shù)相同，但通路中的節(jié)點身份標(biāo)識（ID）不同；跳數(shù)相同，節(jié)點ID相同，但節(jié)點順序不同。因此，本文在亂序編碼［21］方法的基礎(chǔ)上，固定源節(jié)點和目的節(jié)點以實現(xiàn)基因編碼。該編碼方法不僅能夠?qū)崿F(xiàn)對除源節(jié)點和目的節(jié)點之外的其他節(jié)點的數(shù)量和順序進(jìn)行隨機(jī)排列組合，而且可以排除不包含源節(jié)點和目的節(jié)點的無效路由通路，降低搜索空間，提高搜索效率。

文獻(xiàn)［21］采用的亂序編碼對原始染色體的每一位基因增加一個取值為整數(shù)的等位基因，并將該等位基因作為基因的標(biāo)號，根據(jù)標(biāo)號對基因進(jìn)行亂序排列，從而調(diào)整基因之間的距離，降低了被交叉算子破壞的概率。而本文采用亂序編碼是為了實現(xiàn)編碼空間的完備性。

本文根據(jù)節(jié)點數(shù)量確定染色體長度，使染色體長度等于節(jié)點數(shù)量。染色體中的基因代表節(jié)點。為了能夠表示節(jié)點ID及其是否存在于該染色體代表的路由中，選取每個基因由2個等位基因構(gòu)成。該方案可以實現(xiàn)用等長的染色體表示具有不同跳數(shù)的路由。圖3表示了本文采用的染色體編碼方案。

圖3 中，L 為節(jié)點的數(shù)量；Ai（i=1，2，…，L）為排序序號為i的節(jié)點；等位基因ai1表示節(jié)點是否存在于該染色體所代表的鏈路中，若ai1=0則表示該節(jié)點不在該鏈路中，若ai1=1則表示該節(jié)點在該鏈路中；等位基因 ai2表示節(jié)點的ID，取值范圍為［1，L］。

圖3 染色體編碼方案Fig.3 Chromosome encoding scheme

源節(jié)點和目的節(jié)點：由于路由搜索的目的是尋找源節(jié)點與目的節(jié)點的可用路徑，因此要求源節(jié)點和目的節(jié)點必須存在于該染色體代表的鏈路中，即要求a11=1，aL1=1，a12=IDS，aL2=IDD，IDS和 IDD分別為源節(jié)點ID和目的節(jié)點ID。

其余節(jié)點：設(shè)置每條染色體 ai1（i?［2，L-1］）以隨機(jī)概率取值為0或者1，并對L-2個節(jié)點的節(jié)點ID按任意順序進(jìn)行排列組合，按排列后的先后順序依次賦值給ai2。由于節(jié)點ID采用亂序排列，因此i（i?［2，L-1］）與 ai2沒有特定聯(lián)系。

通過對染色體編碼進(jìn)行分析，首先剔除ai1=0的節(jié)點，然后將剩余節(jié)點按i的大小順序依次連接ai2即可得到實際路由通路。

2.2 適應(yīng)函數(shù)選擇

遺傳算法為了執(zhí)行適者生存的原則，必須對染色體個體的適應(yīng)性進(jìn)行評價。一般而言，好的染色體具有較高的適應(yīng)函數(shù)值，即可以獲得較高的評價，具有較強(qiáng)的生存能力。由于適應(yīng)值是群體中個體生存機(jī)會選擇的唯一確定性指標(biāo)，所以適應(yīng)函數(shù)直接決定著群體的進(jìn)化行為。

根據(jù)適應(yīng)函數(shù)中的度量參數(shù)是否聯(lián)合，可以將適應(yīng)函數(shù)分為單混合度量適應(yīng)函數(shù)和多混合度量適應(yīng)函數(shù)。單混合度量適應(yīng)函數(shù)是將多個度量參數(shù)通過一個線性或非線性函數(shù)表示成一個度量值；而多混合度量適應(yīng)函數(shù)是指獨立的看待每個度量參數(shù)，即多個適應(yīng)函數(shù)的集合。

本文采用由式（5）定義的單混合度量適應(yīng)函數(shù)。

其中，F(xiàn)B、FE、FD、FJ分別為帶寬、誤碼率、時延和時延抖動在適應(yīng)函數(shù)中所占的比重，四者之和滿足式（10）；fB、fE、fD、fJ分別為帶寬、誤碼率、時延、時延抖動的加權(quán)系數(shù)，可以根據(jù)具體的配電網(wǎng)業(yè)務(wù)需求進(jìn)行設(shè)置；fc為網(wǎng)絡(luò)資源消耗函數(shù)，表示為延時、帶寬以及跳數(shù)I的乘積。

該適應(yīng)函數(shù)的特點為：耗費資源越多，S值就越小；冗余比例即 B（p）/B0、E（p）/E0、D（p）/D0、J（p） /J0越大的參數(shù)在最優(yōu)函數(shù)中所占的比例就越大。

2.3 遺傳操作設(shè)計

（1）染色體評價。

所謂染色體評價就是判斷該染色體所代表路由是否滿足QoS參數(shù)約束條件，即是否滿足式（1）—（4）。因此，需要知道該染色體所代表路由的每一跳即相關(guān)節(jié)點之間信道的QoS參數(shù)信息。本文假設(shè)QoS參數(shù)信息根據(jù)相關(guān)路由協(xié)議已經(jīng)獲得，并以表2（a）所示格式進(jìn)行存儲，每2個節(jié)點之間的QoS參數(shù)信息的內(nèi)容格式如表2（b）所示，表中 B（i，j）、E（i，j）、D（i，j）、J（i，j） 分別為節(jié)點 i與節(jié)點 j之間的帶寬、誤碼率、時延和時延抖動。

表2 QoS參數(shù)信息Table 2 QoS parameter information

依次從種群中選擇一條染色體，根據(jù)表2進(jìn)行適應(yīng)值計算。若當(dāng)前染色體滿足式（1）—（4），則由式（5）計算該染色體所代表路由的適應(yīng)值；若不滿足式（1）—（4）中的任何一個條件，則適應(yīng)值為0。

為了加快路由搜索速度，帶寬和誤碼率的判斷可在每一跳結(jié)束時根據(jù)式（1）和（4）進(jìn)行評價，而不是等所有跳結(jié)束后才進(jìn)行評價。

當(dāng)種群中所有的染色體評價與計算完畢后，按適應(yīng)值的大小進(jìn)行排序，適應(yīng)值最大的染色體代表本代最優(yōu)路由。本文采用最佳保留機(jī)制，將該最優(yōu)路由作為下一代種群中的一條染色體。同時將適應(yīng)值為0的染色體從當(dāng)前種群中剔除，生成滿足QoS參數(shù)約束條件的種群，作為下一代種群進(jìn)行選擇、交叉和變異。

（2）選擇。

選擇是指從當(dāng)前群體中選擇染色體個體用來進(jìn)行交叉、變異以生成新染色體個體的過程。選擇的策略有很多種，包括適應(yīng)值比例選擇、Boltzmann選擇、排序選擇、聯(lián)賽選擇、精英選擇等。本文采用輪盤賭選擇方法，以隨機(jī)概率從上一代生成的滿足QoS參數(shù)約束條件的種群中選擇染色體個體，生成交叉種群。

（3）交叉。

交叉模仿了自然界有性繁殖的基因重組過程，其作用在于將原有的優(yōu)良基因傳給下一代個體，并生成包含更復(fù)雜基因結(jié)構(gòu)的新個體。

本文采用的交叉策略如下：①隨機(jī)從交叉種群中選擇2條染色體組成配對個體；②根據(jù)染色體長度L且考慮源節(jié)點和目的節(jié)點固定，隨機(jī)從［2，L-1］中選取2個整數(shù)g1、g2作為交叉位置；③根據(jù)交叉概率pc（0≤pc≤1）實施交叉操作，配對個體在交叉位置處相互交換各自的部分內(nèi)容，從而形成一對新的染色體個體。

（4）變異。

變異操作模擬自然界生物體進(jìn)化中染色體上某位基因發(fā)生的突變現(xiàn)象。本文的變異策略為：①隨機(jī)從交叉后的群體中選擇染色體個體作為變異染色體；②為了避免變異后得到不含有源節(jié)點和目的節(jié)點的無效染色體，因此以隨機(jī)概率從［2，L-1］中選擇變異點。

（5）下一代初始種群生成。

下一代初始種群主要由三部分染色體構(gòu)成：①最佳保留機(jī)制將本代的最優(yōu)染色體作為下一代初始種群的一個個體；②經(jīng)過選擇、交叉和變異操作后得到的種群；③由于適應(yīng)值評價、選擇等操作可能會導(dǎo)致上述兩部分構(gòu)成的種群中的個體數(shù)量小于規(guī)定的初始種群規(guī)模，此時需要按照種群初始化方法生成種群來填充，以保證每一代的初始種群規(guī)模相同。

3 Best Effort工作模式

考慮到電力線信道的實際工作情況，可能在較長的一段時間內(nèi)不存在滿足QoS參數(shù)約束條件的路由。為了避免由于沒有路由生成而導(dǎo)致無法通信的情況，本文給出了一種進(jìn)入Best Effort工作模式的方法。與Best Effort工作模式相對應(yīng)，滿足QoS參數(shù)約束條件的工作模式為QoS工作模式。

若在規(guī)定的迭代次數(shù)內(nèi)搜索到滿足QoS參數(shù)約束條件的路由，則進(jìn)入QoS工作模式，否則進(jìn)入Best Effort工作模式。

Best Effort工作模式與QoS工作模式的區(qū)別在于染色體評價與適應(yīng)值的計算。當(dāng)某條染色體代表的路由不滿足式（1）—（4）中的任一條件時，不是將適應(yīng)值設(shè)置為0，而是采用懲罰機(jī)制。本文采用的懲罰機(jī)制是通過修改式（5）中的 fB、fE、fD、fJ來實現(xiàn)。懲罰機(jī)制的原理可由式（13）—（16）表示。本文采用的懲罰機(jī)制的特點是當(dāng)超出約束條件越大時，則懲罰越嚴(yán)重，即系數(shù)越小。

4 算法實現(xiàn)與驗證

根據(jù)第2節(jié)介紹的方案，在MATLAB軟件下實現(xiàn)了可應(yīng)用于具有任意節(jié)點數(shù)量的電力線通信網(wǎng)絡(luò)的多QoS參數(shù)約束條件下的遺傳算法。算法流程圖如圖4所示。遺傳算法的參數(shù)設(shè)置如表3所示。

圖4 遺傳算法流程圖Fig.4 Flowchart of genetic algorithm

表3 遺傳算法的參數(shù)設(shè)置Table 3 Parameter settings for genetic algorithm

4.1 算法正確性驗證及性能分析

為了驗證所提方法的正確性，選取一包含10個節(jié)點的電力線網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)如圖5所示。同時以10個節(jié)點中的任意2個節(jié)點為源節(jié)點和目的節(jié)點，設(shè)計了可生成源節(jié)點與目的節(jié)點之間的所有無環(huán)路由的模型，用來窮舉所有路由，從而生成最優(yōu)路由。以窮舉法生成的最優(yōu)路由為標(biāo)準(zhǔn)，判斷本文所提方法能否搜索到該路由。10個節(jié)點的無環(huán)路由條數(shù)可由式（17）計算得到。

其中，lroute_num為無環(huán)路由數(shù)量；M為節(jié)點數(shù)量。當(dāng)M=10 時，lroute_num=109601。

圖5 含10個通信節(jié)點的電力線通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.5 Topology of PLC network with 10 communication nodes

電力線信道的QoS參數(shù)信息：B（hi）滿足均值為70 kbit/s、方差為0.5 的正態(tài)分布，E（hi）是區(qū)間［10-3，2×10-3］內(nèi)的均勻分布，D（hi）是區(qū)間［4，10］s內(nèi)的均勻分布，J（hi）是區(qū)間［1，2］s 內(nèi)的均勻分布。QoS 參數(shù)約束條件為：B0=60 kbit/s，E0=2×10-3，D0=40 s，J0=10 s。上述數(shù)據(jù)只是用來驗證本文遺傳算法的相關(guān)特性。在實際工程中，QoS參數(shù)信息可由實際的電力線業(yè)務(wù)指標(biāo)設(shè)置，QoS參數(shù)約束條件可由硬件設(shè)備通過檢測信道狀態(tài)通過計算獲得［22］。

本文驗證方法的步驟如下。

a.選擇節(jié)點1和節(jié)點10分別作為源節(jié)點和目的節(jié)點，并按上述參數(shù)生成QoS參數(shù)信息。特別地，將B（1，10）設(shè)置為0，這樣可以建立一條特殊的驗證路由，即最優(yōu)路由不會是節(jié)點1和10的直接路由，若最終路由為該路由，則可說明算法有誤。

b.窮舉源節(jié)點與目的節(jié)點之間的所有可能路由，并根據(jù)式（5）計算適應(yīng)值，選擇適應(yīng)值最大的路由作為最優(yōu)路由。

c.在當(dāng)前網(wǎng)絡(luò)條件下，運行100次遺傳算法，每次迭代150代。記錄每次運行搜索到最優(yōu)路由的進(jìn)化代數(shù)。

圖6描述了窮舉節(jié)點1和10之間所有可能路由后得到的每條路由的適應(yīng)值。得到的最優(yōu)路由為1-8-10。

圖7為100次遺傳算法的搜索過程中適應(yīng)值的變化趨勢，可以發(fā)現(xiàn)本文實現(xiàn)的遺傳算法可以經(jīng)過一定次數(shù)的迭代搜索到最優(yōu)路由。

圖8描述了100次仿真運行中，每次搜索到最優(yōu)路由的進(jìn)化代數(shù)，圖9描述了搜索到最優(yōu)路由的進(jìn)化代數(shù)的概率分布，圖10描述了進(jìn)化代數(shù)的累積概率分布。從圖10中可以發(fā)現(xiàn)，搜索到最優(yōu)路徑的進(jìn)化代數(shù)小于30次（搜索次數(shù)為30×40=1200）的概率約為96%，與窮舉算法搜索次數(shù)109601相比，搜索效率大幅提高。

圖6 所有路由的適應(yīng)值Fig.6 Fitness values of all routings

圖7 路由搜索過程中適應(yīng)值變化情況Fig.7 Variation of fitness during routing search

圖8 搜索到最優(yōu)路由的進(jìn)化代數(shù)Fig.8 Iteration turns until optimal routing is found

圖9 圖8中進(jìn)化代數(shù)的概率分布Fig.9 Probability distribution for fig.8

圖10 圖8中進(jìn)化代數(shù)的累積概率分布Fig.10 Cumulative probability distribution for fig.8

4.2 算法的特殊應(yīng)用情形分析

將時延約束條件D0的取值改為10 s，即約束條件比D0=40 s時更加嚴(yán)格。QoS參數(shù)信息仍按4.1節(jié)驗證方法中的步驟a生成。本文在此選擇了2種比較典型的情況。

（1）只有一條路由滿足QoS參數(shù)約束條件。

圖11為滿足QoS參數(shù)約束條件的路由的適應(yīng)值，從圖中可以判斷出只有一條路由適應(yīng)值不為0，此時系統(tǒng)仍處于QoS工作模式。

圖11 滿足QoS參數(shù)約束條件的路由的適應(yīng)值Fig.11 Fitness of routing observing QoS parameter constraints

圖12為滿足QoS參數(shù)約束條件的路由，由于當(dāng)前網(wǎng)絡(luò)中只存在一條滿足條件的路由，因此圖12中的路由即為最優(yōu)路由（1-3-10）。其中，鏈路1-3的帶寬為69.7659 kbit/s，時延為4.26324 s，時延抖動為1.9291 s，誤碼率為0.00161449；鏈路3-10的帶寬為70.6543 kbit/s，時延為4.97712 s，時延抖動為1.34014 s，誤碼率為0.00119864。圖13描述了本次搜索過程中適應(yīng)值的變化情況。在搜索到唯一滿足條件的路由之前適應(yīng)值一直為0，最優(yōu)路由的適應(yīng)值為7.7560。

圖12 搜索過程中的有效路由Fig.12 Effective routing found during search

圖13 路由搜索過程中適應(yīng)值變化情況Fig.13 Variation of fitness during routing search

（2）Best Effort工作模式。

當(dāng)網(wǎng)絡(luò)中的所有路由的適應(yīng)值為0，即不存在滿足QoS參數(shù)約束條件的路由時，系統(tǒng)將進(jìn)入Best Effort工作模式。在Best Effort工作模式下，系統(tǒng)將采用懲罰機(jī)制計算路由的適應(yīng)值函數(shù)。

圖14描述了在搜索過程中每次迭代后得到的路由信息，各條路由的鏈路QoS參數(shù)信息如表4所示，其中迭代至150代時的最優(yōu)路由為（1-6-10）。圖15則描述了在Best Effort工作模式下，搜索過程中路由適應(yīng)值的變化情況。搜索過程中路由變更情況如表5所示。

圖14 搜索過程中的有效路由Fig.14 Effective routings found during search

表4 各條路由的鏈路QoS參數(shù)信息Table 4 QoS parameter information of links for different routings

圖15 路由搜索過程中適應(yīng)值變化情況Fig.15 Variation of fitness during routing search

表5 搜索過程中最優(yōu)路由及其適應(yīng)值變化情況Table 5 Change of optimal routing and its fitness during routing search

5 結(jié)論

本文提出了一種基于遺傳算法的多QoS參數(shù)約束條件下的電力線通信網(wǎng)絡(luò)路由搜索方法。通過與窮舉算法比較驗證了本文所提方法的正確性，并對搜索效率進(jìn)行了分析，驗證了所提方法的有效性。同時針對電力線信道條件存在極端惡劣情況，引入了Best Effort工作模式。

由于遺傳算法不需要復(fù)雜的數(shù)學(xué)計算，本文所提方法可為應(yīng)用于實際工程的路由搜索方法提供一種技術(shù)參考。在實際工程應(yīng)用時，需要根據(jù)實際的電力線網(wǎng)絡(luò)拓?fù)洹㈦娏€信道參數(shù)、配電網(wǎng)業(yè)務(wù)需求指標(biāo)等因素對遺傳算法進(jìn)行參數(shù)設(shè)置，還需要選擇合適的適應(yīng)值函數(shù)。

此外，本文算法需要進(jìn)一步完善的問題有：

a.本文在遺傳算法的實現(xiàn)過程中采取的選擇、交叉、變異等策略還有改進(jìn)的空間，改進(jìn)后可進(jìn)一步提高搜索效率；

b.研究QoS參數(shù)信息的存儲結(jié)構(gòu)及QoS參數(shù)信息的有效獲取方式；

c.研究使用多混合度量適應(yīng)函數(shù)作為約束條件的遺傳算法的路由搜索特性；

d.研究Best Effort工作模式與QoS工作模式的有效切換方式；

e.結(jié)合實際工程進(jìn)行現(xiàn)場驗證。

參考文獻(xiàn)：

［1］GALLI S，SCAGLIONE A，WANG Z F.For the grid and through the grid：the role of power line communication in the smart grid［J］.Proceedings of the IEEE，2010，99（6）：998-1027.

［2］LIU Siqian，GOU Bei，LI Hongxiang，et al.Power-line communication channel characteristics under transient model［J］.IEEE Transactions on Power Delivery，2014，29（4）：1701-1707.

［3］GUO Jingbo，WANG Zanji，Lü Haifeng，et al.Transmission characteristics of low-voltage distribution networks in China and its model［J］.IEEE Transactions on Power Delivery，2005，20（2）：1341-1348.

［4］PAPADOPOULOS T A，PAPAGIANNIS G K，DOKOPOULOS P S.Low-voltage distribution line performance evaluation for PLC signal transmission［J］.IEEE Transactions on Power Delivery，2008，23（4）：1903-1910.

［5］應(yīng)展烽，吳軍基，郭昊坤，等.含周期性脈沖噪聲的低壓電力線噪聲建模研究［J］.電力自動化設(shè)備，2013，33（9）：58-63.YING Zhanfeng，WU Junji，GUO Haokun，et al.Modeling of lowvoltage power line noise containing periodic pulses［J］.Electric Power Automation Equipment，2013，33（9）：58-63.

［6］蘇嶺東，翟明岳，何欣.基于時頻峰值濾波的電力線通信噪聲消除方法［J］.電力系統(tǒng)保護(hù)與控制，2015，43（1）：15-20.SU Lingdong，ZHAI Mingyue，HE Xin.A new noise mitigation method based on time frequency peak filtering in powerline communication system［J］.Power System Protection and Control，2015，43（1）：15-20.

［7］GIANAROLI F，PANCALDI F，VITETTA G M.The impact of statistical noise modeling on the error-rate performance of OFDM power-line communications［J］.IEEE Transactions on Power Delivery，2014，29（6）：2622-2630.

［8］ANKIT D，MALLIK R K，SCHOBER R.Performance analysis of a multi-hop power line communication system over log-normal fading in presence of impulsive noise［J］.IET Communications，2015，9（1）：1-9.

［9］MILIOUDISA N，SYRANIDISK N，ANDREOU G T，etal.Modeling of medium-voltage power-line communication systems noise levels［J］.IEEE Transactions on Power Delivery，2013，28（4）：2004-2013.

［10］張良，劉曉勝，戚佳金，等.一種低壓電力線通信改進(jìn)分級蟻群路由算法［J］.電工技術(shù)學(xué)報，2014，29（2）：318-324.ZHANG Liang，LIU Xiaosheng，QI Jiajin，et al.Study of improved hierarchical ant colony routing algorithm for low-voltage power line communication［J］.Transactions of China Electrotechnical Society，2014，29（2）：318-324.

［11］劉曉勝，李延祥，王娟，等.低壓電力線分簇蛛網(wǎng)混合多徑盲路由算法及通信協(xié)議設(shè)計［J］.電工技術(shù)學(xué)報，2015，30（增刊 1）：337-345.LIU Xiaosheng，LI Yanxiang，WANG Juan，et al.Clustering-cobweb hybrid multipath blind routing algorithm and communication protocol design for low-voltage power line communication［J］.Transactions of China ElectrotechnicalSociety，2015，30（Supplement 1）：337-345.

［12］胡正偉，謝志遠(yuǎn).中繼與隊列相結(jié)合的電力線通信AMRS的分組傳輸方法［J］.中國電機(jī)工程學(xué)報，2014，34（19）：3240-3248.HU Zhengwei，XIE Zhiyuan.Packet transmission method for powerline communicationAMRSbased oncombinationof relay and queue［J］.Proceedings of the CSEE，2014，34（19）：3240-3248.

［13］胡正偉，謝志遠(yuǎn)，郭以賀，等.基于終端通信質(zhì)量的10 kV電力線通信組網(wǎng)方法［J］.電力自動化設(shè)備，2013，33（9）：144-150.HU Zhengwei，XIE Zhiyuan，GUO Yihe，et al.10 kV power line communication networking based on communication quality between terminals［J］.Electric Power Automation Equipment，2013，33（9）：144-150.

［14］戚佳金，劉曉勝，徐殿國，等.低壓電力線通信分簇路由算法及網(wǎng)絡(luò)重構(gòu)［J］.中國電機(jī)工程學(xué)報，2008，28（4）：65-71.QI Jiajin，LIU Xiaosheng，XU Dianguo，et al.Cluster-based routing algorithm and reconstruction method of power line communication over lower-voltage distribution［J］.Proceedings of the CSEE，2008，28（4）：65-71.

［15］劉曉勝，戚佳金，宋其濤，等.基于蟻群算法的低壓配電網(wǎng)電力線通信組網(wǎng)方法［J］.中國電機(jī)工程學(xué)報，2008，28（1）：71-76.LIU Xiaosheng，QI Jiajin，SONG Qitao，et al.Method of constructing power line communication networks over low-voltage distribution networks based on ant colony optimization［J］.Proceedings of the CSEE，2008，28（1）：71-76.

［16］戚佳金，徐殿國，周巖，等.低壓電力線通信網(wǎng)絡(luò)特性模型與組網(wǎng)算法［J］.中國電機(jī)工程學(xué)報，2009，29（16）：56-62.QI Jiajin，XU Dianguo，ZHOU Yan，et al.Characteristics model and routing algorithm of power-line communications over lowvoltage distributions［J］.Proceedings of the CSEE，2009，29（16）：56-62.

［17］朱斌泉.基于改進(jìn)遺傳算法的電力載波通信動態(tài)組網(wǎng)研究［J］.南京工程學(xué)院學(xué)報（自然科學(xué)版），2012，10（3）：29-33.ZHU Binquan.Research into dynamical network algorithm for power line carrier communication based on an improved genetic algorithm［J］.Journal of Nanjing Institute of Technology（Natural Science Edition），2012，10（3）：29-33

［18］李黃強(qiáng)，孫云蓮.基于量子遺傳算法的寬帶電力線多用戶通信資源分配［J］.電力自動化設(shè)備，2009，29（10）：120-124.LI Huangqiang，SUN Yunlian.Multiuser resource allocation of broadband power line communication based on quantum genetic algorithm［J］.Electric Power Automation Equipment，2009，29（10）：120-124.

［19］ZABALLOS A，VERNET D，SELGA J M.A genetic QoS-aware routing protocol for the smart electricity networks［J］.International Journal of Distributed Sensor Networks，2015，2013（11）：1098-1101.

［20］SEO C K，SU M J，CHUNG D J.A research on the extraction and interpretation of power line communication noise pattern using genetic algorithm［J］.Advanced Engineering Forum，2011（2-3）：645-648.

［21］GOLDBERG D E，DEB K，KARGUPTA H，et al.Rapid accurate optimization of difficult problems using fast messy genetic algorithms［C］∥International Conference on Genetic Algorithms.［S.l.］：Morgan Kaufmann Publishers Inc.，1995：56-64.

［22］胡正偉，謝榮圓，謝志遠(yuǎn).基于QoS參數(shù)的電力線信道狀態(tài)映射方法［J］.電力自動化設(shè)備，2016，36（10）：159-165.HU Zhengwei，XIE Rongyuan，XIE Zhiyuan.Mapping of PLC channel status to QoS parameter［J］.Electric Power Automation Equipment，2016，36（10）：159-165.