一種基于異層交疊分簇組網(wǎng)的 低壓電力線蟻群路由方法

黃身增 王金龍 曲 加

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

0 引言

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

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

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

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

文獻(xiàn)[10-13]將低壓電力線網(wǎng)絡(luò)分為一個(gè)個(gè)人工蛛網(wǎng)，并選出蜘網(wǎng)中心，構(gòu)建分級(jí)網(wǎng)絡(luò)，然后利用改進(jìn)蟻群算法構(gòu)建每一個(gè)蜘網(wǎng)中心的路由通信，相比基本蟻群算法，該算法大大提高了組網(wǎng)效率，從而提高了實(shí)時(shí)性?；鞠伻核惴ㄊ侵咐孟伻核惴▽?duì)低壓電力線進(jìn)行組網(wǎng)及路由通信。

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

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

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

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

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

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

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

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

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

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

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

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

1）算法步驟

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

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

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

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

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

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

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

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

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

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

2）仿真分析

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

圖3 低壓電力線網(wǎng)絡(luò)拓?fù)?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 仿真參數(shù)

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

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)絡(luò)，收斂速度更快，且最終的最優(yōu)路徑為全局最優(yōu)。

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

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

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

5 結(jié)論

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