基于改進蟻群算法的電纜防盜網(wǎng)絡組網(wǎng)方法

李姣軍，賈智予，張亭亭，曾令果

(1.重慶理工大學 電氣與電子工程學院， 重慶 400054； 2.重慶渝豐電線電纜公司， 重慶 402247)

基于改進蟻群算法的電纜防盜網(wǎng)絡組網(wǎng)方法

李姣軍1，賈智予1，張亭亭1，曾令果2

(1.重慶理工大學 電氣與電子工程學院， 重慶 400054； 2.重慶渝豐電線電纜公司， 重慶 402247)

為了使應用于低壓配電網(wǎng)絡中的電纜防盜系統(tǒng)能夠可靠、快速地實現(xiàn)系統(tǒng)中主從站點間的通信，在分析系統(tǒng)工作方法、主體結(jié)構(gòu)及拓撲變化的前提下，給出一種基于改進蟻群算法的系統(tǒng)組網(wǎng)方法。該方法對蟻群算法中的信息素揮發(fā)系數(shù)進行數(shù)值大小的限制，盡可能地擴大搜索范圍，降低算法陷入局部最優(yōu)的可能性，從而在全局最優(yōu)的情況下獲得算法的最優(yōu)解。仿真結(jié)果表明：改進的蟻群算法在網(wǎng)絡狀態(tài)正常及發(fā)生故障的情況下，都具有更快的尋優(yōu)速度，且完成通信所需的節(jié)點跳數(shù)更少，有效地提高了電纜防盜系統(tǒng)的運行可靠性，從而保障了系統(tǒng)實時監(jiān)控功能的實現(xiàn)。

電纜防盜； 電力線通信； 網(wǎng)絡拓撲； 改進蟻群算法； 可靠性

應用于低壓配電網(wǎng)的電纜防盜系統(tǒng)主要由控制中心、通信主站和通信從站3部分構(gòu)成，其中通信主站與通信從站之間的通信方式即為電力載波通信。在系統(tǒng)中，除控制中心僅有一個外，通信主站與從站皆有多個，且按照單個主站來進行區(qū)域的劃分，每個主站及其下屬的所有從站為一個通信區(qū)域。因此，需要考慮一種合適的組網(wǎng)方式來實現(xiàn)區(qū)域中主、從站點間信息的快速、可靠交互。

文獻[1]對高速公路電線電纜防盜系統(tǒng)進行研究，并采用Dijkstra(迪杰斯特拉)算法對系統(tǒng)進行組網(wǎng)，但該算法只適合規(guī)劃靜態(tài)路徑，對電纜防盜網(wǎng)絡這類動態(tài)組網(wǎng)問題在具體實現(xiàn)上有一定難度和缺陷。文獻[2-3]對類似的路燈控制系統(tǒng)組網(wǎng)方法進行研究，采用基本蟻群算法進行組網(wǎng)，能夠?qū)崿F(xiàn)系統(tǒng)中站點信息的互通，且具有一定的抗毀性，但其收斂速度較慢，容易陷入局部最優(yōu)。文獻[4]對低壓配電網(wǎng)的抄表系統(tǒng)組網(wǎng)方法進行研究，采取免疫-蟻群算法進行組網(wǎng)，在一定程度上改善了局部最優(yōu)化的情況，但其收斂速度仍較慢[1-4]。

本文首先對電纜防盜系統(tǒng)網(wǎng)絡進行分析，根據(jù)其結(jié)構(gòu)和工作特性，討論進行組網(wǎng)操作時需要注意的特點及相應的要求，在此基礎上給出一種改進的蟻群算法，對蟻群系統(tǒng)算法中的信息素揮發(fā)系數(shù)進行改進，設置上下限值，以便擴大搜索范圍，減緩局部收斂的速度，使得防盜系統(tǒng)網(wǎng)絡在正常運行及發(fā)生故障的情況下都能夠快速地找到最優(yōu)路徑，完成組網(wǎng)操作，實現(xiàn)系統(tǒng)監(jiān)控的實時化。該算法操作簡單，能夠為動態(tài)變化的電纜防盜系統(tǒng)網(wǎng)絡提供一種可靠、有效的路由尋找方法。

1 系統(tǒng)網(wǎng)絡模型分析

電纜防盜系統(tǒng)是由各主站利用合適的檢測技術(shù)對電纜的通斷狀態(tài)進行監(jiān)測，并使用恰當?shù)耐ㄐ攀侄螌顟B(tài)信息發(fā)送給控制中心。在低壓配電網(wǎng)中，一個區(qū)域變電站通過管轄多個變電器來實現(xiàn)電力的傳輸與控制。根據(jù)這種網(wǎng)絡結(jié)構(gòu)設計的電纜防盜系統(tǒng)由控制中心、通信主站和從站構(gòu)成，如圖1所示。系統(tǒng)僅有一個控制中心，其通過無線GPRS來接收各個主站上報的信息并下發(fā)相關的指令。系統(tǒng)按單個變電站來進行區(qū)域的劃分，區(qū)內(nèi)設置一個主站(即變電站)和若干個從站(即變電站管轄范圍內(nèi)的變電器)，主從站間通過電力載波通信方式進行數(shù)據(jù)的交互，只要電纜未被剪斷，主、從站之間的通信就能夠順利進行。

圖1 電纜防盜系統(tǒng)結(jié)構(gòu)

目前，根據(jù)我國低壓配電網(wǎng)的負荷等級、容量和分布等情況確定其線路接線方式主要有放射式、樹干式和環(huán)形式3種。當在低壓配電網(wǎng)中進行數(shù)據(jù)通信時，其網(wǎng)絡結(jié)構(gòu)通常可看做是以樹形接線方式為基礎的混合拓撲[5]，如圖2所示。以一個變電站控制的區(qū)域為例，節(jié)點1代表系統(tǒng)中的主節(jié)點(主站)，2～40號節(jié)點都為從節(jié)點(從站)。

圖2 電纜防盜系統(tǒng)網(wǎng)絡拓撲圖

2 電纜防盜網(wǎng)絡的PLC組網(wǎng)

2.1 電纜防盜網(wǎng)絡的組網(wǎng)特點

由于低壓配電網(wǎng)的主要功能是傳輸電力，當其作為通信信道進行數(shù)據(jù)傳輸時，具有與專業(yè)通信信道不同的特點。

首先，盡管區(qū)域內(nèi)的配電網(wǎng)線路是固定的，但需要考慮到各電氣設備從網(wǎng)絡中切除以進行定期檢修等其他操作的情況，當有設備接入、切除時，網(wǎng)絡拓撲的結(jié)構(gòu)會隨之發(fā)生相應的改變[6]。

其次，電力網(wǎng)絡中沒有專用的中繼器或交換機，難以實現(xiàn)通信信號的轉(zhuǎn)發(fā)和放大，且電力線信道具有噪聲干擾、阻抗輸入、信號衰減等特性。因此，數(shù)據(jù)信號的傳輸距離會隨著網(wǎng)絡中信道質(zhì)量的變化而發(fā)生改變。

此外，考慮到防盜系統(tǒng)的結(jié)構(gòu)和相關設備部分需要實現(xiàn)的功能，如控制中心需要監(jiān)控整個網(wǎng)絡中的數(shù)據(jù)采集情況，并在發(fā)生故障時下發(fā)相應的操作指令，主站在完成收發(fā)數(shù)據(jù)并上報的任務外還需具備相對復雜的判斷功能等，二者都需具備較強的CPU數(shù)據(jù)處理能力； 而從站僅需完成接收數(shù)據(jù)請求和發(fā)送數(shù)據(jù)應答的簡單操作，其CPU處理能力很弱甚至僅具有執(zhí)行器或數(shù)據(jù)采集器。因此，常用的計算機網(wǎng)絡路由算法不能直接應用于電力網(wǎng)絡組網(wǎng)。

2.2 電纜防盜網(wǎng)絡的組網(wǎng)要求

結(jié)合以上所述的組網(wǎng)特點，所設計的電纜防盜系統(tǒng)網(wǎng)絡組網(wǎng)算法應能滿足以下4個要求[7]：

1) 采用改進蟻群算法對電纜防盜系統(tǒng)網(wǎng)絡進行組網(wǎng)的首要任務是：找到一條可供數(shù)據(jù)從源節(jié)點(主站)傳送到目標節(jié)點(從站)的最優(yōu)路徑。

2) 當通信網(wǎng)絡結(jié)構(gòu)發(fā)生變化，如某些通信節(jié)點損壞或進行其他操作導致節(jié)點退出邏輯網(wǎng)絡，致使部分路徑通信失效時，組網(wǎng)算法能夠重新找到一條數(shù)據(jù)傳送的路徑，從而實現(xiàn)通信網(wǎng)絡的重組。

3) 在網(wǎng)絡進行通信的過程中，任意時刻都只能有一個通信節(jié)點進行數(shù)據(jù)發(fā)送操作?？紤]到系統(tǒng)網(wǎng)絡的盲結(jié)構(gòu)，在組網(wǎng)時，只有主節(jié)點具有所有從節(jié)點的路由表，各從節(jié)點僅知曉向主節(jié)點回復的路徑及附近能夠直接通信的節(jié)點信息。

4) 能夠滿足目標節(jié)點的即插即用功能。網(wǎng)絡中的所有節(jié)點都擁有自己的物理ID來與其他節(jié)點進行區(qū)別，除此之外的通信過程完全相同。當系統(tǒng)網(wǎng)絡發(fā)生變化時，僅需增加或刪除網(wǎng)絡中的節(jié)點即可。

2.3 電纜防盜系統(tǒng)組網(wǎng)過程

正常情況下，電纜防盜系統(tǒng)在每次上電后都會立即開始進行自動組網(wǎng)操作。主節(jié)點會向每一個從節(jié)點發(fā)送廣播數(shù)據(jù)包，并根據(jù)從節(jié)點的數(shù)據(jù)應答幀中的地址信息建立、更新其節(jié)點可通信路由表[8]。

當系統(tǒng)網(wǎng)絡中發(fā)生故障，如低壓電力線上產(chǎn)生的各種衰減、干擾或某些從節(jié)點無規(guī)律地接入、切除時，原有的網(wǎng)絡邏輯拓撲就可能遭到破壞，從而導致通信路徑發(fā)生改變。某次系統(tǒng)網(wǎng)絡的動態(tài)變化如圖3所示：18～24號節(jié)點間的通信鏈路在某一時刻因發(fā)生斷線或強烈噪聲干擾而無法有效傳輸數(shù)據(jù)，這將導致以18號節(jié)點為中繼的24號、25號及其后的節(jié)點在邏輯上退出通信。

圖3 發(fā)生動態(tài)變化的局部網(wǎng)絡拓撲

為了解決以上網(wǎng)絡問題，需要采用自動組網(wǎng)路由算法來進行網(wǎng)絡的動態(tài)重組，使24、25號節(jié)點能夠重新加入網(wǎng)絡并繼續(xù)進行通信工作，實現(xiàn)網(wǎng)絡的自愈。

3 算法原理及實現(xiàn)步驟

3.1 蟻群算法基本原理

蟻群算法(ant colony algorithm,ACA)，也稱為蟻群優(yōu)化算法(ant colony optimization,ACO)，是一種受自然界中螞蟻搜尋食物行為啟發(fā)而得到的優(yōu)化算法[9]。蟻群算法通過信息素更新和啟發(fā)式信息來指導人工螞蟻尋找優(yōu)秀候選解，并通過多次迭代獲得最優(yōu)解。螞蟻在搜尋路徑時會留下信息素，因此較為理想的路徑(如路徑長度較短)能從更多的螞蟻處得到信息素，從而增加了后續(xù)螞蟻經(jīng)過該路徑的可能。同時，路徑上的信息素會按照某一系數(shù)ρ揮發(fā)掉，以此來避免搜索過程的過早停止。最終，能夠找出最優(yōu)解。由算法實現(xiàn)原理可以看出：該種算法是一種性能優(yōu)良的啟發(fā)式隨機優(yōu)化算法，它采用正反饋和負反饋相結(jié)合的方法來實現(xiàn)分布式全局優(yōu)化，通過信息素的釋放和揮發(fā)來獲取搜索路徑的不斷改善，從而使結(jié)果最終收斂于最優(yōu)解[10]。

3.2 蟻群算法實現(xiàn)

當需要考察網(wǎng)絡的通信效果時，可以采用路徑長度、信道帶寬、丟包率、平均通信量和時延等作為優(yōu)化目標。本文中將主節(jié)點到目標從節(jié)點所需要的“跳數(shù)”作為優(yōu)化目標，以“通信距離”作為約束條件。“跳數(shù)”在本文中是指數(shù)據(jù)由主節(jié)點向目標從節(jié)點發(fā)送時需要被轉(zhuǎn)發(fā)的次數(shù)。例如兩個可以直接進行通信的節(jié)點，二者間發(fā)送數(shù)據(jù)時的跳數(shù)為0； 若需要一個中繼節(jié)點進行轉(zhuǎn)發(fā)才能夠到達目標節(jié)點，則跳數(shù)為1?！巴ㄐ啪嚯x”在本文中指兩個可以直接進行通信的節(jié)點所跨過的節(jié)點數(shù)加1，以圖3中的部分網(wǎng)絡為例，2號節(jié)點能跨過5號節(jié)點與11號節(jié)點直接通信而無需中轉(zhuǎn)，二者通信距離為2。

3.2.1 全局更新規(guī)則

算法中的人工螞蟻個數(shù)需根據(jù)網(wǎng)絡的復雜程度來進行選擇，考慮到圖2中每條支路的長度有限，因此選擇每批螞蟻為10只。在進行全局信息素更新時，選用最大最小蟻群算法的更新規(guī)則，對信息素的大小進行限制，設置信息素數(shù)值的上限和下限[11]，以此來防止算法的過早停滯和陷入局部最優(yōu)。由于電纜防盜系統(tǒng)組網(wǎng)僅需建立中心節(jié)點到各從節(jié)點的路由，因此將人工螞蟻均放在中心。每完成一次迭代，就按式(1)進行全局信息素更新：

τij(t+1)=ρτij(t)+Δτbestij

(1)

其中：ρ為當前次迭代中全局信息素的揮發(fā)系數(shù)； Δτbestij為在當前次迭代中獲得的最優(yōu)路徑上的信息素增量，可根據(jù)式(2)獲得。

(2)

其中：Lib表示當前次迭代中的最優(yōu)解，K為系數(shù)，它與ρ值的選擇都可以調(diào)整迭代最優(yōu)路徑信息素的增長速度。算法在進行過程中僅對迭代最優(yōu)線路進行信息素的增加，對其他路徑上的信息素作揮發(fā)處理，這可以使搜索過程更具指導性，能夠使螞蟻的搜索主要集中在迭代最優(yōu)路線的周圍。

3.2.2 局部更新規(guī)則

本算法采用蟻群系統(tǒng)算法(ACS)中的局部信息素更新規(guī)則，對每只螞蟻走過的路徑都進行更新，當前一批螞蟻完成路徑尋找后，更新途經(jīng)路徑上的信息素，以此來影響后續(xù)螞蟻的尋優(yōu)行為，使它們有更大的可能找到較好(即信息素較多)的路徑。

局部信息素按式(3)進行更新：

τ(r,s)=(1-ξ)·τ(r,s)+ξ·τ(0)

(3)

其中：ξ(0<ξ<1)為局部更新時的信息素揮發(fā)系數(shù)。τ(0)為局部信息素的初始值，若兩個節(jié)點間能直接通信，則該條線路上的信息素初值為τ(0)=10。ξ越大，搜索范圍越大，但算法的收斂效果會變差。

3.2.3 路徑轉(zhuǎn)移

某一時刻，一只位于節(jié)點r的螞蟻根據(jù)式(4)中給出的規(guī)則選擇下一個要經(jīng)過的城市u。

(4)

其中：q0為算法中設置的參數(shù)，q為(0,1)范圍內(nèi)的一隨機數(shù)。當q≤q0時，螞蟻將根據(jù)信息素濃度τ(r,u)和啟發(fā)式信息η(r,u)選擇下一節(jié)點u，啟發(fā)式信息η(r,u)為城市r、u之間距離的倒數(shù)； 當不需根據(jù)先驗知識進行路徑選擇時，路徑選擇概率按式(5)獲得：

(5)

在式(5)中：α、β分別為信息素和啟發(fā)式信息的重要度參數(shù)，二者的取值大小分別表明了信息素濃度和啟發(fā)式信息對路徑選擇的重要性。

4 算法仿真驗證

仿真實驗模擬電纜防盜系統(tǒng)網(wǎng)絡的拓撲結(jié)構(gòu)，利用Matlab仿真軟件在一個100×100的范圍內(nèi)隨機產(chǎn)生40個節(jié)點，依次給節(jié)點編號。1號節(jié)點作為載波主節(jié)點，表示防盜系統(tǒng)網(wǎng)絡中的通信主站； 2～40號節(jié)點作為普通載波從節(jié)點，表示防盜系統(tǒng)網(wǎng)絡中的通信從站。假設：網(wǎng)絡中的任意兩個相鄰節(jié)點可以進行可靠的數(shù)據(jù)通信； 通信的邏輯拓撲圖為無向圖； 每個節(jié)點都有其唯一的地址編碼。仿真實驗中參數(shù)值的設置如表1中所示。

表1 仿真參數(shù)設置

采用基本蟻群算法和改進蟻群算法進行組網(wǎng)操作時的跳數(shù)對比，如圖4、5所示。圖4為網(wǎng)絡正常情況下由源節(jié)點至目標節(jié)點35所需的跳數(shù)對比； 圖5為網(wǎng)絡中節(jié)點19因故退出通信時所需的跳數(shù)對比。

圖4 搜索35號節(jié)點所需跳數(shù)對比

圖5 節(jié)點19退出通信時所需跳數(shù)對比

4.1 算法收斂性比較

收斂性是評價算法性能優(yōu)劣的基本指標。在圖4由源節(jié)點到達單一目標節(jié)點35的跳數(shù)對比圖中能夠看出：采用基本蟻群算法時，常會陷入局部最優(yōu)，使搜索一度陷入停滯，導致進程較慢，取得最優(yōu)解所需的次數(shù)為39次，遠多于改進蟻群算法的18次。相比之下，采用改進蟻群算法進行路徑尋優(yōu)時，由于改進了信息素的更新原則，使搜索的范圍更為全面，不容易陷入局部最優(yōu)，因此搜索過程幾乎無停滯，并且更早地搜索到最優(yōu)路徑，有效提高了路由組網(wǎng)的效率，能夠更好地進行電纜防盜系統(tǒng)中的組網(wǎng)與通信。

4.2 算法抗毀性比較

由于電纜防盜系統(tǒng)是基于低壓配電網(wǎng)建立的，因此低壓電力線信道的時變、噪聲等特性都會影響電纜防盜網(wǎng)絡的拓撲結(jié)構(gòu)。這就要求電纜防盜系統(tǒng)能夠在網(wǎng)絡狀態(tài)發(fā)生變化時迅速地進行網(wǎng)絡重組，以減小網(wǎng)絡動態(tài)變化對通信可靠性的影響。因此，算法的抗毀性也是評價算法性能的一項重要指標。

仿真采用與正常情況相同的基本網(wǎng)絡條件，令節(jié)點19因故退出網(wǎng)絡，分別采用基本蟻群算法與改進蟻群算法對電纜防盜系統(tǒng)網(wǎng)絡進行通信路線的重建，所需跳數(shù)的對比如圖5所示。從圖中能夠看出：基本蟻群算法需25次搜索到最優(yōu)路徑，改進蟻群算法僅需10次即可搜索到最優(yōu)路徑。改進蟻群算法在搜索速度上明顯優(yōu)于普通蟻群算法，且搜索空間較廣，能夠在電纜防盜系統(tǒng)網(wǎng)絡拓撲發(fā)生變化時實現(xiàn)網(wǎng)絡的動態(tài)重組，使網(wǎng)絡具有一定的抗毀性，進而保證網(wǎng)絡在發(fā)生故障時，依舊能較快地找到新的通信路徑以保證數(shù)據(jù)的可靠傳輸。

5 結(jié)束語

基于低壓配電網(wǎng)建立的電纜防盜系統(tǒng)，根據(jù)其網(wǎng)絡的特點需要采用動態(tài)組網(wǎng)方式來保證系統(tǒng)的正常通信。本文中采用改進的蟻群算法對電纜防盜系統(tǒng)網(wǎng)絡進行組網(wǎng)的仿真操作，其結(jié)果表明：該算法能夠有效改善基本蟻群算法進行組網(wǎng)操作時易陷入局部最優(yōu)、搜索易停滯及搜索速度較慢的缺點，并使該系統(tǒng)在網(wǎng)絡狀態(tài)發(fā)生變化時具有一定的抗毀性和重組能力，能夠較好地保障電纜防盜系統(tǒng)的可靠運行，為實現(xiàn)電纜防盜的實時監(jiān)控提供了一種有效的技術(shù)方案。

[1] 唐妍.高速公路電力電纜、電力設備的智能監(jiān)測防盜系統(tǒng)研究[D].重慶：重慶大學，2011.

[2] 劉曉勝,戚佳金,宋其濤,等.基于蟻群算法的低壓配電網(wǎng)電力線通信組網(wǎng)方法[J].中國電機工程學報,2008,28(1)：71-76.

[3] 劉曉勝,周巖,戚佳金.電力線載波通信的自動路由方法研究[J].中國電機工程學報,2006,26(21):76-81.

[4] 高慶,呂霞付.基于免疫-蟻群算法的電力線載波抄表動態(tài)路由方法[J].自動化與儀器儀表,2014(1):108-111.

[5] 野瑩瑩,付麗君,程立英.基于MATLAB的蟻群算法仿真研究[J].裝備制造技術(shù),2008(11):13-14.

[6] 宋濤,蔣偉,趙勤學.低壓配電網(wǎng)電力線載波通信路由算法研究[J].科學技術(shù)與工程,2016,16(2):169-173.

[7] 吳兆平,楊俊杰,高聰慧,等.低壓電力線載波通信路由算法研究[J].電測與儀表,2015,52(15):108-112.

[8] 徐東明,李育澤.低壓電力線通信的雙種群遺傳蟻群路由算法[J].西安郵電大學學報,2017,22(1):23-27.

[9] VLACHOU C,BANCHS A,HERZEN J,et al.How CSMA/CA with deferral affects performance and dynamics in power-line communications[J].IEEE/ACM Transactions on Networking,2017,PP(99):1-14.

[10] TSOKALO I,RADEKE R,LEHNERT R.Enhancement of backoff algorithm in CSMA/CA protocols for broadband PLC[C]//IEEE International Symposium on Power Line Communications and ITS Applications.[S.l.],IEEE,2013:47-52.

[11] 陳曉娟,耿雪瑩.低壓電力線載波通信的動態(tài)路由算法[J].黑龍江電力,2013,35(1):6-8.

NetworkConstructionMethodofCableAnti-TheftNetworkBasedonImprovedAntColonyAlgorithm

LI Jiaojun1, JIA Zhiyu1, ZHANG Tingting1, ZENG Lingguo2

(1.College of Electrical and Electronic Engineering, Chongqing University of Technology, Chongqing 400065, China; 2.Chongqing Yufeng Wire & Cable Company, Chongqing 402247, China)

Under the premise of analyzing the working method, main structure and topology of the system, it gave a network construction method based on improved ant colony algorithm, in order to make the cable anti-theft system applied in low voltage distribution network quickly and reliably realize the communication between the master and slave sites in system. This method limits the size of parameter which represents the volatilize speed of pheromone, and expands the searching scope as far as possible, and reduces the possibility of falling into local optimum, and finally obtains the global optimal solution of the algorithm. The simulation results of algorithm show that the improved ant colony algorithm has faster optimization speed in the case of normal and unnormal network state, and the number of nodes required to complete the communication is less. This algorithm effectively improved the reliability of cable anti-theft system, and ensure the realization of real-time monitoring function.

cable anti-theft; power line communication; network topology; improved ant colony algorithm; reliability

2017-06-20

重慶市科委基礎與前沿研究一般項目(cstc2014jcyjA40003)

賈智予(1993—)，女，江蘇無錫人，碩士研究生，主要從事電力線載波通信研究，E-mail：505534432@qq.com。

李姣軍，賈智予，張亭亭，等.基于改進蟻群算法的電纜防盜網(wǎng)絡組網(wǎng)方法[J].重慶理工大學學報(自然科學)，2017(12):160-165.

formatLI Jiaojun, JIA Zhiyu, ZHANG Tingting, et al.Network Construction Method of Cable Anti-Theft Network Based on Improved Ant Colony Algorithm[J].Journal of Chongqing University of Technology(Natural Science)，2017(12):160-165.

10.3969/j.issn.1674-8425(z).2017.12.028

TM76

A

1674-8425(2017)12-0160-06

(責任編輯陳 艷)