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

黃身增 王金龍 曲 加

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

0 引言

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

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

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

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

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

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

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

1 低壓電力線通信網絡模型

低壓電力線網絡從物理結構上看有樹形結構，比如高層電力設備；有星形結構，比如農村一些電力設備；也有樹形和星形混合結構[7]。典型的低壓電力線通信系統結構如圖1所示，每相節點通過網關與集中器進行通信，節點之間由于受信道強干擾、信號衰減等原因導致通信距離縮短，因此當節點距離網關較遠時，必須采用其他節點作為中繼才能和網關進行通信，因此如何選擇較優中繼路由及快速組網是實現大規模低壓電力線通信的必要條件。

圖1 低壓電力線通信系統結構

2 異層交疊分簇組網算法原理

2.1 交疊分簇結構

分簇算法是指將網絡依照某種規則分為一個個的簇，并從簇中選擇一個簇頭，簇內其他成員的通信及數據傳輸等都由簇頭進行管理，簇頭是簇內成員與外界通信的代理人。

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

圖2 交疊分簇結構

2.2 異層交疊分簇組網算法

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

1）算法步驟

異層交疊分簇組網算法的步驟如下：

（1）上電后網關節點將節點所在的邏輯層數設置為0，網關節點和子節點的路由表為空。

（2）網關節點廣播組網報文，組網報文包括節點的物理地址及所在的邏輯層數，子節點收到網關的組網報文后，將節點的邏輯層數設為1，并根據CSMA協議依次發送響應報文，響應報文包括節點的物理地址及所在的邏輯層數，網關節點收到子節點響應報文后，將子節點加入網關路由表中。

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

①邏輯層數小于組網報文源節點（在這里只能是網關節點），節點丟棄該報文，不發送響應報文。

②邏輯層數等于組網報文源節點的，說明與源節點在同一邏輯層，節點也丟棄該報文，不發送響應報文。

③未分配邏輯層數的節點，將該節點加入以組網報文源節點為簇頭的簇中，并將該節點的邏輯層數設為組網報文的邏輯層數加1，根據CSMA協議發送響應報文。

④邏輯層數大于組網報文源節點的，說明該節點已加入某個簇，為了實現交疊分簇，收到組網報文的節點發送響應報文給組網報文源節點，將節點加入以組網報文源節點為簇頭的簇中。發送組網報文的節點收到子節點響應報文后，將該子節點加入發送組網報文的節點的路由表中。

（4）重復步驟（3），直到不存在未分配邏輯層數的節點，則組網完成。

按照此算法進行組網，無需知道整個網絡的拓撲結構，實現對未知網絡進行組網，并將組網后的信息保存在路由表中，供下一步蟻群算法尋找最優路徑使用。

2）仿真分析

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

圖3 低壓電力線網絡拓撲

圖4 異層交疊分簇組網拓撲

3 基于異層交疊分簇組網的蟻群路由算法

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

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

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

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

3）每一只螞蟻從網關出發尋找目標節點，并將網關節點加入禁忌表中。

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

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

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

7）判斷當前最優路徑是否已收斂，若收斂，則得到最優路徑，算法結束；若沒有收斂，將迭代次數加1，并判斷當前迭代次數是否已達到最大值，若已達到最大值，則算法結束；若沒有達到最大值，則轉到3）。

4 仿真實驗

4.1 仿真環境與參數

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

表1 仿真參數

分別采用基本蟻群算法、分簇蛛網蟻群路由算法及異層交疊分簇蟻群路由算法搜尋網關節點到節點31之間的最優路由，對三種算法的最優路徑距離及最優路徑節點個數這兩個指標進行仿真分析。

4.2 仿真結果與分析

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

圖6 最優路徑距離迭代分析比較

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

圖7 最優路徑節點個數分析比較

5 結論

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