黃身增 王金龍 曲 加

（1. 國網(wǎng)福建省電力有限公司漳州供電公司，福州 353000； 2. 國網(wǎng)西藏電力有限公司那曲供電公司，西藏 那曲 852000）

0 引言

低壓電力線通信（low voltage power line communication, LVPLC）具有覆蓋面廣、成本低及運行維護方便等特點，已被廣泛應用于遠程抄表、樓宇控制等領(lǐng)域[1]，但低壓電力線具有噪聲干擾[2]、阻抗不匹配[3]等信道問題，導致低壓電力線通信可靠性偏低，限制其進一步大規(guī)模應用于其他電力通信領(lǐng)域，因此如何提高低壓電力線通信可靠性是低壓電力線通信領(lǐng)域的一大研究熱點。

目前提高低壓電力線通信可靠性的研究主要分為兩個方面：①從物理層出發(fā)，在濾波設(shè)計[4]和調(diào)制解調(diào)方式[5-6]上進行改進；②從網(wǎng)絡層出發(fā)，提出更優(yōu)的動態(tài)路由組網(wǎng)算法，對如何快速組網(wǎng)、選擇路由中繼及出現(xiàn)故障時如何快速恢復等方面進行研究。目前在動態(tài)路由組網(wǎng)算法領(lǐng)域有較多研究，已經(jīng)取得了大量有效的成果，但也存在一定的不足 之處。

文獻[7]提出了先通過非交疊分簇對低壓電力線進行組網(wǎng)，然后利用節(jié)點間通信信道質(zhì)量動態(tài)建立節(jié)點間通信路由，具有一定的自愈能力，但由于采用的非交疊分簇節(jié)點之間僅存在單一路由，一旦路由失效，會頻繁觸發(fā)通信系統(tǒng)網(wǎng)絡重構(gòu)，大大降低網(wǎng)絡通信的實時性，不滿足低壓電力線通信實時性的要求。

文獻[8-9]利用蟻群算法、變異遺傳算法等智能優(yōu)化算法來進行組網(wǎng)，以服務質(zhì)量（quality of service, QoS）為優(yōu)化目標，建立較優(yōu)的網(wǎng)絡結(jié)構(gòu)，但是存在組網(wǎng)速度慢及實時性不足等問題。

文獻[10-13]將低壓電力線網(wǎng)絡分為一個個人工蛛網(wǎng)，并選出蜘網(wǎng)中心，構(gòu)建分級網(wǎng)絡，然后利用改進蟻群算法構(gòu)建每一個蜘網(wǎng)中心的路由通信，相比基本蟻群算法，該算法大大提高了組網(wǎng)效率，從而提高了實時性。基本蟻群算法是指利用蟻群算法對低壓電力線進行組網(wǎng)及路由通信。

文獻[14]采用改進Q學習算法對低壓電力線進行通信組網(wǎng)，并引入蟻群算法建立節(jié)點之間動態(tài)路由，提高低壓電力線通信實時性及可靠性。

本文針對已有文獻中蟻群算法應用于低壓電力線通信存在收斂速度慢、容易陷入局部最優(yōu)等問題，提出一種基于異層交疊分簇組網(wǎng)的低壓電力線蟻群路由方法，詳細說明低壓電力線網(wǎng)絡組網(wǎng)及路由構(gòu)建過程。最后通過仿真與基本蟻群算法、基于分簇蛛網(wǎng)的蟻群路由算法[10-11]進行比較，驗證該算法的有效性和優(yōu)越性。

1 低壓電力線通信網(wǎng)絡模型

低壓電力線網(wǎng)絡從物理結(jié)構(gòu)上看有樹形結(jié)構(gòu)，比如高層電力設(shè)備；有星形結(jié)構(gòu)，比如農(nóng)村一些電力設(shè)備；也有樹形和星形混合結(jié)構(gòu)[7]。典型的低壓電力線通信系統(tǒng)結(jié)構(gòu)如圖1所示，每相節(jié)點通過網(wǎng)關(guān)與集中器進行通信，節(jié)點之間由于受信道強干擾、信號衰減等原因?qū)е峦ㄐ啪嚯x縮短，因此當節(jié)點距離網(wǎng)關(guān)較遠時，必須采用其他節(jié)點作為中繼才能和網(wǎng)關(guān)進行通信，因此如何選擇較優(yōu)中繼路由及快速組網(wǎng)是實現(xiàn)大規(guī)模低壓電力線通信的必要條件。

圖1 低壓電力線通信系統(tǒng)結(jié)構(gòu)

2 異層交疊分簇組網(wǎng)算法原理

2.1 交疊分簇結(jié)構(gòu)

分簇算法是指將網(wǎng)絡依照某種規(guī)則分為一個個的簇，并從簇中選擇一個簇頭，簇內(nèi)其他成員的通信及數(shù)據(jù)傳輸?shù)榷加纱仡^進行管理，簇頭是簇內(nèi)成員與外界通信的代理人。

交疊分簇結(jié)構(gòu)是指加入一個簇的節(jié)點可以再加入另一個簇中，交疊分簇結(jié)構(gòu)如圖2所示，網(wǎng)絡分為兩個邏輯層，其中，節(jié)點3、5、6都加入兩個簇中，網(wǎng)關(guān)節(jié)點到達節(jié)點6有0→4→6和0→7→6這兩條路徑，存在冗余路徑，不存在非交疊分簇結(jié)構(gòu)只具有單一通信鏈路的問題。

圖2 交疊分簇結(jié)構(gòu)

2.2 異層交疊分簇組網(wǎng)算法

基本蟻群算法可以在未知低壓電力線網(wǎng)絡拓撲的情況下，建立整個低壓電力線網(wǎng)絡的通信路由拓撲，該算法由于采用隨機搜索，必然存在收斂速度慢及陷入局部最優(yōu)解等實時性低的問題，故本文提出一種異層交疊分簇組網(wǎng)方法，它通過交疊分簇的方法將全部節(jié)點分為多個簇，簇與簇之間存在層次關(guān)系，消除同一層之間節(jié)點通信，只保留異層通信，解決了基本蟻群算法在同層路徑迭代中可能存在無效搜索，以及在同層中迭代，不能快速地搜索全網(wǎng)絡、收斂速度慢和容易陷入局部最優(yōu)解的問題。

1）算法步驟

異層交疊分簇組網(wǎng)算法的步驟如下：

（1）上電后網(wǎng)關(guān)節(jié)點將節(jié)點所在的邏輯層數(shù)設(shè)置為0，網(wǎng)關(guān)節(jié)點和子節(jié)點的路由表為空。

（2）網(wǎng)關(guān)節(jié)點廣播組網(wǎng)報文，組網(wǎng)報文包括節(jié)點的物理地址及所在的邏輯層數(shù)，子節(jié)點收到網(wǎng)關(guān)的組網(wǎng)報文后，將節(jié)點的邏輯層數(shù)設(shè)為1，并根據(jù)CSMA協(xié)議依次發(fā)送響應報文，響應報文包括節(jié)點的物理地址及所在的邏輯層數(shù)，網(wǎng)關(guān)節(jié)點收到子節(jié)點響應報文后，將子節(jié)點加入網(wǎng)關(guān)路由表中。

（3）已加入邏輯層1的節(jié)點廣播組網(wǎng)報文，此時收到組網(wǎng)報文的節(jié)點分為四類：

①邏輯層數(shù)小于組網(wǎng)報文源節(jié)點（在這里只能是網(wǎng)關(guān)節(jié)點），節(jié)點丟棄該報文，不發(fā)送響應報文。

②邏輯層數(shù)等于組網(wǎng)報文源節(jié)點的，說明與源節(jié)點在同一邏輯層，節(jié)點也丟棄該報文，不發(fā)送響應報文。

③未分配邏輯層數(shù)的節(jié)點，將該節(jié)點加入以組網(wǎng)報文源節(jié)點為簇頭的簇中，并將該節(jié)點的邏輯層數(shù)設(shè)為組網(wǎng)報文的邏輯層數(shù)加1，根據(jù)CSMA協(xié)議發(fā)送響應報文。

④邏輯層數(shù)大于組網(wǎng)報文源節(jié)點的，說明該節(jié)點已加入某個簇，為了實現(xiàn)交疊分簇，收到組網(wǎng)報文的節(jié)點發(fā)送響應報文給組網(wǎng)報文源節(jié)點，將節(jié)點加入以組網(wǎng)報文源節(jié)點為簇頭的簇中。發(fā)送組網(wǎng)報文的節(jié)點收到子節(jié)點響應報文后，將該子節(jié)點加入發(fā)送組網(wǎng)報文的節(jié)點的路由表中。

（4）重復步驟（3），直到不存在未分配邏輯層數(shù)的節(jié)點，則組網(wǎng)完成。

按照此算法進行組網(wǎng)，無需知道整個網(wǎng)絡的拓撲結(jié)構(gòu)，實現(xiàn)對未知網(wǎng)絡進行組網(wǎng)，并將組網(wǎng)后的信息保存在路由表中，供下一步蟻群算法尋找最優(yōu)路徑使用。

2）仿真分析

采用Matlab進行仿真研究，在100m×100m區(qū)域隨機分布1個網(wǎng)關(guān)和39個節(jié)點，網(wǎng)關(guān)節(jié)點位于坐標原點，物理ID設(shè)為1，其他節(jié)點的物理ID分別為2, 3, …, 40，節(jié)點之間有效通信距離為30m，則低壓電力線網(wǎng)絡拓撲如圖3所示，根據(jù)異層交疊分簇組網(wǎng)算法，組網(wǎng)結(jié)果如圖4所示，它將網(wǎng)絡分割為具有層次關(guān)系的多個交疊簇，只保留異層通信，網(wǎng)絡結(jié)構(gòu)優(yōu)化，為后續(xù)蟻群算法路由尋優(yōu)創(chuàng)造條件。

圖3 低壓電力線網(wǎng)絡拓撲

圖4 異層交疊分簇組網(wǎng)拓撲

3 基于異層交疊分簇組網(wǎng)的蟻群路由算法

基于異層交疊分簇組網(wǎng)的蟻群路由算法流程如圖5所示。

圖5 基于異層交疊分簇組網(wǎng)的蟻群路由算法流程

1）利用異層交疊分簇組網(wǎng)對低壓電力線網(wǎng)絡進行組網(wǎng)，消除同一層之間節(jié)點通信，只保留異層通信，優(yōu)化網(wǎng)絡路徑。

2）初始化蟻群個數(shù)、迭代次數(shù)、信息素矩陣及禁忌表等參數(shù)。

3）每一只螞蟻從網(wǎng)關(guān)出發(fā)尋找目標節(jié)點，并將網(wǎng)關(guān)節(jié)點加入禁忌表中。

4）計算可以到達的下一跳節(jié)點，并對下一跳節(jié) 點集合進行重排采樣，計算下一跳轉(zhuǎn)移概率，采用輪盤賭方法選擇下一跳。

5）判斷是否到達目標節(jié)點，若沒達到目標節(jié)點，則轉(zhuǎn)到4）；若到達目標節(jié)點，則保存當前螞蟻行走路徑，并清空禁忌表。

6）判斷是否所有螞蟻都到達目標節(jié)點，若沒有，則轉(zhuǎn)到3）；若已全部到達目標節(jié)點，從螞蟻行走路徑選擇一條最優(yōu)路徑，并對最優(yōu)路徑進行全局信息素更新。這里不同于基本蟻群算法，僅更新最優(yōu)路徑的信息素，而不是對螞蟻在此次迭代中的所有路徑進行信息素更新。

7）判斷當前最優(yōu)路徑是否已收斂，若收斂，則得到最優(yōu)路徑，算法結(jié)束；若沒有收斂，將迭代次數(shù)加1，并判斷當前迭代次數(shù)是否已達到最大值，若已達到最大值，則算法結(jié)束；若沒有達到最大值，則轉(zhuǎn)到3）。

4 仿真實驗

4.1 仿真環(huán)境與參數(shù)

采用Matlab進行仿真研究，仿真參數(shù)見表1，在100m×100m內(nèi)的區(qū)域內(nèi)隨機分布著40個節(jié)點，網(wǎng)關(guān)節(jié)點位于坐標原點，物理ID設(shè)為1，其他節(jié)點的物理ID分別為2, 3,…, 40，節(jié)點之間有效通信距離為30m，低壓電力線網(wǎng)絡拓撲如圖3所示。

表1 仿真參數(shù)

分別采用基本蟻群算法、分簇蛛網(wǎng)蟻群路由算法及異層交疊分簇蟻群路由算法搜尋網(wǎng)關(guān)節(jié)點到節(jié)點31之間的最優(yōu)路由，對三種算法的最優(yōu)路徑距離及最優(yōu)路徑節(jié)點個數(shù)這兩個指標進行仿真分析。

4.2 仿真結(jié)果與分析

圖6所示為三種算法迭代次數(shù)、最優(yōu)路徑距離的分析比較。從圖6曲線中可以看出，隨著迭代次數(shù)增加，這三種算法最優(yōu)路徑距離都逐漸下降，最終收斂；基本蟻群算法經(jīng)過12次迭代后，最優(yōu)路徑距離從194m縮短到120.9m，分簇蛛網(wǎng)蟻群路由算法經(jīng)過7次迭代后，最優(yōu)路徑距離從150.4m縮短到133.1m，而異層交疊分簇蟻群路由算法經(jīng)過2次迭代后，最優(yōu)路徑距離從121.6m縮短到120.9m，相比基本蟻群算法、分簇蛛網(wǎng)蟻群路由算法，異層交疊分簇蟻群路由算法優(yōu)化了網(wǎng)絡，收斂速度更快，且最終的最優(yōu)路徑為全局最優(yōu)。

圖6 最優(yōu)路徑距離迭代分析比較

圖7為三種算法最優(yōu)路徑節(jié)點個數(shù)的分析比較，基本蟻群算法與分簇蛛網(wǎng)蟻群路由算法在迭代過程中，最優(yōu)路徑節(jié)點個數(shù)有所變化，但最終收斂，基本蟻群算法經(jīng)過12輪迭代，最優(yōu)路徑節(jié)點個數(shù)收斂于7，分簇蛛網(wǎng)蟻群路由算法經(jīng)過7次迭代，最優(yōu)路徑個數(shù)收斂于8，而異層交疊分簇蟻群路由算法在第一輪迭代最優(yōu)路徑節(jié)點個數(shù)就已收斂于7，充分表明了異層交疊分簇蟻群路由算法收斂速度更快，且最優(yōu)路徑節(jié)點個數(shù)為全局最優(yōu)解。

圖7 最優(yōu)路徑節(jié)點個數(shù)分析比較

5 結(jié)論

針對蟻群算法應用于低壓電力線通信領(lǐng)域存在收斂速度慢、容易陷入局部最優(yōu)等問題，本文提出了一種基于異層交疊分簇組網(wǎng)的蟻群路由算法，該算法通過交疊分簇的方法將全部節(jié)點分為多個簇，消除同一層之間節(jié)點通信，減少了蟻群算法在同層路徑迭代中可能存在無效搜索，以及在同層中迭代，不能快速地搜索全網(wǎng)絡的情況，優(yōu)化了網(wǎng)絡結(jié)構(gòu)。經(jīng)過仿真分析，相比基本蟻群算法及分簇蛛網(wǎng)蟻群路由算法，該算法的收斂速度大幅度提高，且收斂的最優(yōu)路徑為全局最優(yōu)，為蟻群算法進一步應用于低壓電力線領(lǐng)域提供了堅實的基礎(chǔ)，具有一定的實際意義。