基于蟻群遺傳混合的載波路由方法研究

楊永，朱俊超，衛(wèi)建均，許炫壕

（1.廣東電網(wǎng)有限責任公司茂名供電局，廣東茂名525000；2.廣東工業(yè)大學自動化學院，廣東廣州510006）

基于蟻群遺傳混合的載波路由方法研究

楊永1，朱俊超2，衛(wèi)建均1，許炫壕2

（1.廣東電網(wǎng)有限責任公司茂名供電局，廣東茂名525000；2.廣東工業(yè)大學自動化學院，廣東廣州510006）

針對集中抄表系統(tǒng)下行載波通信路由算法數(shù)據(jù)傳輸延時和丟包率高的問題，在分析集抄系統(tǒng)載波通信網(wǎng)絡結(jié)構(gòu)的基礎上，提出了一種基于蟻群遺傳混合的載波路由方法。該方法在蟻群算法中引入了遺傳算法，使蟻群算法不至于陷入局部最優(yōu)；對狀態(tài)轉(zhuǎn)移因子進行改進，加快了算法全局最優(yōu)路徑的收斂速度。仿真結(jié)果表明：與蟻群算法相比，該方法在降低數(shù)據(jù)傳輸延時和丟包率方面優(yōu)勢明顯，可大大提高集中抄表系統(tǒng)數(shù)據(jù)采集的實時性和成功率。

電力線載波通信；集中抄表系統(tǒng)；混合路由算法；可靠性

將低壓電力線作為數(shù)據(jù)通信的媒介，可極大地減少成本投資，方便用戶安裝，在電力行業(yè)已被用于集中抄表系統(tǒng)領域［1］。然而電力線設計的目的是傳輸電能而不是進行數(shù)據(jù)信息的傳輸，低壓配電網(wǎng)中大量負載隨機的投入與撤出帶來電力線輸入阻抗變化不確定、噪聲干擾大以及信號選擇性衰減等缺點［2-3］，常會加大電力線載波通信數(shù)據(jù)傳輸時延和丟包率，降低電力線載波通信的可靠性。

1 研究現(xiàn)狀及需要解決的問題

1.1 研究現(xiàn)狀

目前，國內(nèi)外在提高低壓電力線載波通信可靠性問題上，主要是從網(wǎng)絡層自動路由組網(wǎng)技術(shù)方面做了相關(guān)的研究。文獻［4-5］將遺傳算法應用于路由尋址中，保證了路由路徑選擇的多樣性，但搜索到最優(yōu)路由需要花費較長時間。文獻［6］采用蟻群算法構(gòu)建了集中抄表系統(tǒng)的路由算法，仿真結(jié)果表明該算法具有抗毀性強和收斂速度快的優(yōu)點，但是在算法搜索的后期容易陷入局部最優(yōu)。文獻［7］結(jié)合非交疊分簇算法與人工蛛網(wǎng)算法的優(yōu)點提出了一種新型的分簇蛛網(wǎng)混合算法，實驗結(jié)果表明該算法能夠快速有效地實現(xiàn)低壓電力線網(wǎng)絡的組網(wǎng)和重構(gòu)，在提高電力線通信可靠性方面有一定的優(yōu)勢。文獻［8］提出了一種基于蟻群、粒子群算法的混合路由算法，仿真結(jié)果表明該算法能適應電力線通信信道的動態(tài)變化，快速收斂于全局最優(yōu)路徑。

1.2 需要解決的問題

上述研究方法普遍存在以下問題：

（1）通信網(wǎng)絡結(jié)構(gòu)復雜，算法在搜索路由過程中不能根據(jù)實際情況自適應調(diào)整搜索策略，減緩了算法收斂速度，進而加大了數(shù)據(jù)包傳輸時延。

（2）在搜尋最優(yōu)路由路徑時，容易陷入局部最優(yōu)解，將增加數(shù)據(jù)包傳輸時的丟失率。

2 蟻群遺傳混合路由算法

2.1 集抄系統(tǒng)載波通信網(wǎng)絡結(jié)構(gòu)

低壓電力線載波集中抄表系統(tǒng)是一種以低壓電力線作為數(shù)據(jù)傳輸介質(zhì)，集現(xiàn)代計算機軟、硬件技術(shù)，電能計量技術(shù)為一體的用戶用電信息采集與分析處理系統(tǒng)，主要由載波電能表、集中器、主站系統(tǒng)以及連接上述設備的數(shù)據(jù)傳輸通道構(gòu)成［9］。主要包括3層結(jié)構(gòu)：第1層為主站系統(tǒng)，由現(xiàn)場應用服務器、數(shù)據(jù)庫服務器構(gòu)成，負責數(shù)據(jù)存儲和提供人機交互界面；第2層為集中器，負責對主站的命令進行解析，然后下發(fā)給電表，收集電表返回的數(shù)據(jù)，并進行存儲等待主站召測；第3層為載波電表，采集用電數(shù)據(jù)并通過低壓電力線上傳至集中器。其系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 低壓電力線載波集中抄表系統(tǒng)結(jié)構(gòu)

由于低壓電力線的噪聲干擾、信號衰減和負載的投入與撤出等因素常會使信號在電力線上傳輸距離變短，同時也使得通信網(wǎng)絡邏輯拓撲結(jié)構(gòu)發(fā)生動態(tài)變化，從而導致集中器與某些電表節(jié)點不能直接通信。為了保證集中器能采集到所有電表節(jié)點的數(shù)據(jù)，必須先建立起集中器到部分電表節(jié)點的通信路徑，然后再以這些電表節(jié)點作為中繼，進行數(shù)據(jù)的轉(zhuǎn)發(fā)，擴展通信距離，才能使所有的電表節(jié)點都包含在集中抄表系統(tǒng)通信網(wǎng)絡內(nèi)［10］。因此，路由算法的好壞將直接影響集中抄表系統(tǒng)數(shù)據(jù)采集的實時性和成功率。

2.2 混合算法目標函數(shù)設計

低壓電力線載波通信網(wǎng)絡信道具有噪聲干擾大，信號衰減嚴重、時變性強的特點，使得通信網(wǎng)絡拓撲不穩(wěn)定，常常導致路由性能降低。對于集中抄表系統(tǒng)而言要求保證數(shù)據(jù)采集的實時性和成功率，因此為提高低壓電力線載波集中抄表系統(tǒng)通信網(wǎng)絡的路由性能，本文將網(wǎng)絡服務質(zhì)量（Quality of Service，QoS）中的傳輸時延和丟包率列入約束條件，作為數(shù)據(jù)傳輸可靠性的衡量標準［11］。

在電力線載波集中抄表系統(tǒng)通信網(wǎng)絡中，集中器節(jié)點s到目標電表節(jié)點d之間的延時有兩部分：一部分是數(shù)據(jù)包在相鄰兩節(jié)點之間傳輸時所耗費時延總和∑D（Mi，Mj），另一部分是中繼節(jié)點處理數(shù)據(jù)包所耗費的時間∑D（Mi）。集中器節(jié)點到目標電表節(jié)點時延如公式（1）：

由于噪聲干擾、信號衰減、信道變化等原因，導致數(shù)據(jù)包在電力線上傳輸時容易丟失。設路徑上Mi與Mj之間的丟包率為P(Mi，Mj)，集中器節(jié)點s到目標電表節(jié)點d丟包率如公式（2）：

考慮集中抄表系統(tǒng)載波通信網(wǎng)絡對服務質(zhì)量要求的特殊性，將混合算法的目標函數(shù)定義如式（3）：

式中：ν，ω—相應的權(quán)重因子，可以根據(jù)實際需求改變延時和丟包率在目標函數(shù)中所占的比重。

2.3 路由算法原理

2.3.1 蟻群算法原理

蟻群算法（ant colony algorithm，ACA）［12］是由意大利學者Marco Dorigo提出的一種新的模擬進化算法，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)最佳路徑的生物學行為。螞蟻在尋找食物時會在經(jīng)過的路徑上釋放一種叫信息素的物質(zhì)，這對于后續(xù)的螞蟻有引導作用，偏向于選擇信息素堆積多的路徑。螞蟻從巢穴出發(fā)去覓食，有多條可以選擇的路徑時，整個蟻群追蹤個體產(chǎn)生的信息素軌跡發(fā)現(xiàn)覓食過程中的最短路徑，最后使得所有螞蟻選擇最短路徑去覓食。該算法采用分布式并行計算機制，易與其他方法結(jié)合，具有較強的魯棒性，但搜索時間長、易限入局部最優(yōu)解是其突出的缺點［13-14］。蟻群算法中主要規(guī)則如下：

（1）改進狀態(tài)轉(zhuǎn)移規(guī)則。

在蟻群算法中，位于節(jié)點i的螞蟻k，按照狀態(tài)轉(zhuǎn)移規(guī)則選擇要訪問的下一個節(jié)點j，轉(zhuǎn)移規(guī)則公式如下：

式中：q—0到1之間的隨機數(shù)；

ηij—啟發(fā)式信息；

τij—路徑（i，j）上的信息素的大??；

α—信息啟發(fā)式因子；

β—期望啟發(fā)式因子；若y=f（x），則argmax［y］表示當y取得最大值時x的值，當q≤q0時，按照先驗規(guī)律選擇路徑；當q＞q0時，按公式（6）進行路徑搜索。

NA—當前循環(huán)次數(shù)。在算法執(zhí)行過程中q0值將逐漸增大。在算法早期獲得較小的q0，以確保有更多的螞蟻可以以隨機的方式選擇下一個節(jié)點訪問，有利于全局搜索。相反，在算法后期，q0選擇相對較大的值，有助于算法快速收斂及局部搜索，這樣既可以保證前期搜索路徑的多樣性，又可以在算法后期使搜索集中在最優(yōu)路徑附近。

式中：Gk—第k只螞蟻下一訪問節(jié)點的集合。

（2）局部信息素更新規(guī)則。

采用蟻群系統(tǒng)的局部更新規(guī)則，即螞蟻每經(jīng)過一條邊則馬上按公式（7）更新該邊上的信息素：

式中：τij—路徑（i，j）上的信息素的大小；

ρl—局部信息素揮發(fā)因子；

τ0—初始信息素的含量。

局部更新規(guī)則的引入使螞蟻傾向于選擇沒有走過的路經(jīng)，避免搜索過于集中在同一條線路上，這種更新規(guī)則有利于發(fā)現(xiàn)新路徑［15］。

（3）全局信息素更新規(guī)則。

全局信息素更新是對一次迭代所有螞蟻走過路徑中最優(yōu)的那條載波邏輯鏈路進行信息素的更新。全局信息素更新規(guī)則如公式（8）：

式中：ρg—全局信息素揮發(fā)因子；

Δτij—本次迭代路徑(i,j)上的信息素增量；

Q—信息素總量；

L(s,d)min—是本次循環(huán)最優(yōu)路徑對應的目標函數(shù)值。

2.3.2 遺傳算法原理

遺傳算法（genetic algorithm，GA）是一種仿效生物界生存法則和進化機制的隨機、自適應搜索方法［16］，它是把問題參數(shù)編碼為染色體，然后再利用個體迭代的方式進行適應度評估、選擇、交叉、變異等操作［17］。其中適應度表明個體或解的優(yōu)劣。在個體的適應度評估基礎上進行選擇操作，將當前種群中優(yōu)良的個體選出直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。交叉是兩父代個體在交叉點兩兩交換信息而得到新個體，促使其產(chǎn)生新的優(yōu)良個體。變異是通過改變個體中某些信息而得到新個體，增加群體中解的個數(shù)，擴大搜索范圍有效避免“早熟”。

（1）交叉操作。

交叉操作規(guī)則為：將種群中任意2條路徑編碼從除源節(jié)點外的第一個相同節(jié)點處斷開，然后將斷開處到目標節(jié)點的這段路徑進行交換，重新組合得到2條新的路徑。其中交叉概率為pc，pc能隨著適應度值的變化而變化，公式如式（10）：

式中：fmax—種群中適應度值最大的個體的適應度值；

favg—種群所有個體適應度值的平均值；

f′—交叉的2個個體適應度值中較大的那個值；

pc1、pc2—2個參數(shù)初始化時給定的值。

（2）變異操作。

變異操作規(guī)則為：在個體路徑內(nèi)部隨機選擇1個節(jié)點編碼，將其變?yōu)榕c其相鄰的節(jié)點編碼，然后組成新的路徑。其中變異概率為pm，pm能隨著適應度值的變化而變化，公式如式（11）：

式中：pm1、pm2—2個參數(shù)初始化時給定的值。

2.3.3 混合路由算法

蟻群算法具有分布并行計算、啟發(fā)式搜索等優(yōu)點，但算法后期信息素過于集中在某條路徑，容易導致算法陷入局部最優(yōu)。遺傳算法雖然全局搜索能力強，但對系統(tǒng)中反饋信息利用不夠，在運算迭代的過程中會出現(xiàn)冗余的迭代，求解速度慢。

蟻群遺傳混合算法克服兩種算法各自的缺點，形成優(yōu)勢互補［18］。蟻群算法的正反饋機制能有效克服遺傳算法對系統(tǒng)中反饋信息利用不夠、容易產(chǎn)生多余的迭代、求解效率低的缺點。遺傳算法的選擇、交叉、變異等運算能夠產(chǎn)生新的路徑避免蟻群算法陷入局部最優(yōu)［19］。因此，結(jié)合兩種算法的優(yōu)點將能適應電力線載波通信網(wǎng)絡的動態(tài)變化，快速找到集中器節(jié)點到目標電表節(jié)點的最優(yōu)載波路徑。

混合算法的搜索過程：算法中將特定探測數(shù)據(jù)包看作人工螞蟻，集中器發(fā)出數(shù)據(jù)包看作人工螞蟻的釋放。將集中器發(fā)出數(shù)據(jù)包到目標電表節(jié)點返回確認數(shù)據(jù)幀看作是螞蟻的一次覓食完成。算法首先通過蟻群算法初步搜索產(chǎn)生1組從集中器節(jié)點到目標電表節(jié)點的初始路徑，即得到電力線載波通信網(wǎng)絡的邏輯拓撲，同時各終端通過接受或監(jiān)聽電力線上的載波信號并根據(jù)信號噪聲比計算出其與其他終端的電氣距離，更新其原有電氣距離表［20］。然后將這組路徑作為遺傳算法的初始種群，以目標函數(shù)作為適應度函數(shù)進行適應度評價，接著進行選擇、交叉、變異等操作，產(chǎn)生1組較優(yōu)通信路徑，接著將本次迭代蟻群算法產(chǎn)生的全局最優(yōu)路徑與遺傳算法產(chǎn)生的1組較優(yōu)路徑進行比較，選擇1條較優(yōu)路徑作為本次迭代的全局最優(yōu)，同時進行全局信息素的更新。最后經(jīng)過多次迭代，算法將快速收斂到最優(yōu)路由路徑。

2.4 仿真驗證

2.4.1 仿真環(huán)境與參數(shù)設置

本文采用MATLAB軟件進行仿真，在100×100的區(qū)域內(nèi)取坐標為（50,50）的點為1號點代表集中器節(jié)點，2～50號節(jié)點隨機生成代表電表節(jié)點。

仿真參數(shù)設置：螞蟻數(shù)量m=20；α=1、β=2、ρl=0.2、ρg=0.96、τ0=2、Q=250、ν=2、ω=3；節(jié)點(i,j)間傳輸時延D(Mi，Mj)=節(jié)點(i,j)間的電氣距離×0.1 ms；節(jié)點i的時延D(Mi)=5(ms)；節(jié)點(i,j)間的丟包率P(Mi，Mj)=節(jié)點(i,j)間的電氣距離×0.1%；蟻群迭代最大次數(shù)NA=100；遺傳迭代最大次數(shù)NG=50；pc1=0.8、pc2=0.5、pm1=0.03，pm2=0.01。

2.4.2 仿真結(jié)果

蟻群遺傳混合路由算法與傳統(tǒng)蟻群路由算法在數(shù)據(jù)包傳輸時延、丟包率兩方面進行仿真，結(jié)果如圖2和圖3所示。

圖2 數(shù)據(jù)包傳輸時延

由圖2可看出，混合路由算法的收斂速度明顯快于傳統(tǒng)蟻群路由算法，減少了數(shù)據(jù)傳輸時延；由圖3可知，隨著通信距離的增加，與蟻群路由算法相比混合路由算法的丟包率要更低且變換幅度不大。

圖3 數(shù)據(jù)包丟失率

3 效果評價

將蟻群遺傳混合路由算法與傳統(tǒng)蟻群路由算法在數(shù)據(jù)包傳輸時延、丟包率兩方面進行對比，結(jié)果如表1、表2所示。

表1 2種路由算法數(shù)據(jù)包傳輸時延結(jié)果對比

表2 2種路由算法數(shù)據(jù)包丟失率結(jié)果比較

3.1 數(shù)據(jù)包傳輸時延比較

從表1結(jié)果可以看出，隨著運行時間的推移2種算法的數(shù)據(jù)包傳輸時延前期下降的比較快，最后趨于平緩。從數(shù)據(jù)明顯可以看出運用混合路由算法后的數(shù)據(jù)包傳輸時延在運行時間的各個時刻都比蟻群算法要低大約2～4 ms，當運行時間達到220 s時，混合路由算法的傳輸時延為54 ms，比蟻群路由算法降低了3.5 ms，由此說明混合算法收斂的速度更快，因而混合算法在降低數(shù)據(jù)包傳輸時延方面效果更好。

3.2 數(shù)據(jù)包丟失率比較

2種算法隨著通信距離增加，數(shù)據(jù)包丟失率都逐漸增加。由表2數(shù)據(jù)可以看出，當通信距離每增加60 m，混合路由算法丟包率變化幅度在1%～2%之間，而蟻群算法的變化幅度在2%～5%之間，由此可得，混合算法更能適應網(wǎng)絡的動態(tài)變化減少丟包率；當通信距離為340 m時，運用混合路由算法后的丟包率比蟻群路由算法降低了17%，因此混合算法更適用于降低數(shù)據(jù)包在傳輸過程中的丟失率。

4 結(jié)論

（1）本文提出的混合路由算法可根據(jù)電力線載波通信網(wǎng)絡的實際需求自動調(diào)整路由選擇策略，加快了算法收斂于最優(yōu)路由路徑的速度，降低數(shù)據(jù)傳輸延時。

（2）該混合路由算法可在算法陷入局部最優(yōu)時，通過交叉、變異等運算產(chǎn)生新的路徑，保證算法跳出局部最優(yōu)，直至收斂到全局最優(yōu)路由路徑，降低了數(shù)據(jù)傳輸?shù)膩G包率。

［1］王伊瑾,張文靜,李亞南.低壓電力線載波抄表系統(tǒng)路由算法研究[J].河北農(nóng)業(yè)大學學報,2013(3)∶120-124.

［2］趙永輝,張建偉,李仕林,等.基于低壓電力線載波通信信道特性的分析[J].自動化與儀器儀表,2016(10)∶216-218.

［3］肖勇,房瑩,張捷,黨三磊.低壓電力線載波通信信道特性研究[J].電力系統(tǒng)保護與控制,2012(20)∶20-25.

［4］林景棟,秦玉龍,廖孝勇.電力載波通信動態(tài)組網(wǎng)算法的研究[J].控制工程,2013(5)∶841-843+，848.

［5］朱斌泉.基于改進遺傳算法的電力載波通信動態(tài)組網(wǎng)研究[J].南京工程學院學報(自然科學版),2012(1)∶29-33.

［6］戚佳金,劉曉勝,張良.一種低壓配電網(wǎng)電力線載波通信網(wǎng)絡中繼算法[J].電力系統(tǒng)保護與控制,2010(14)∶73-78.

［7］劉曉勝,李延祥,王娟,等.低壓電力線分簇蛛網(wǎng)混合多徑盲路由算法及通信協(xié)議設計[J].電工技術(shù)學報,2015(S1)∶337-345.

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

［9］樊建學,盛新富.低壓電力線載波集中抄表系統(tǒng)的研究[J].繼電器,2005(17)∶49-52.

［10］C.Ke,Q.Chenxi,Z.Tingtao，et al.Research of automat?ic meter reading system based on broadband carrier in the power line[C].2011 6th IEEE Conference on Indus?trial Electronics and Applications,Beijing,2011∶2763-2767.

［11］劉萍,高飛,楊云.基于遺傳算法和蟻群算法融合的QoS路由算法[J].計算機應用研究,2007(9)∶224-227.

［12］SHTOVBA S D.Ant algorithms∶theory and applications[J].Programming and Computer Software,2005,31(4)∶167-178.

［13］段海濱,王道波,朱家強,等.蟻群算法理論及應用研究的進展[J].控制與決策,2004(12)∶1321-1326+1340.

［14］柳長安,鄢小虎,劉春陽,等.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學報,2011(5)∶1220-1224.

［15］陳可,胡曉光.基于遺傳自適應蟻群系統(tǒng)算法的中繼路由方法[J].中南大學學報(自然科學版),2013,44(2)∶571-579.

［16］劉志,林堅海,金拓.基于改進遺傳算法的必經(jīng)點最短路徑算法[J].信息通信,2017(2)∶46-48.

［17］尹向東.基于遺傳蟻群算法的QoS路由算法研究[J].計算機工程與應用,2009(17)∶113-115.

［18］張曉玲,黃力.融入遺傳算子的蟻群算法求解TSP問題[J].廣西民族大學學報(自然科學版),2009(3)∶81-87.

［19］袁杰.基于蟻群遺傳混合智能算法求解TSP問題[D].長春：長春工業(yè)大學,2014.

［20］冉慶華,吳玉成,祁美娟.低壓電力線載波通信網(wǎng)絡自動組網(wǎng)方法研究[J].電力系統(tǒng)保護與控制,2011(10)∶53-58，63.

A routing algorithm of power line carrier based on ant colony genetic hybridization

YANG Yong1,ZHU Junchao2,WEI Jianjun1，XU Xuanhao2
(1.Maoming Power Supply Bureau of Guangdong Power Grid Co.,Ltd.,Maoming Guangdong 525000,China;2.School of Automation,Guangdong University of Technology,GuangZhou Guangdong 510006,China)

Aiming at the problem of high delay and the high data packet loss rate in the data transmission of carrier routing algorithm for the power meter remote data acquisition system,on the basis of analyzing the carrier communication network structure of the power meter remote data acquisition system,puts forward a carrier routing method based on ant colony genetic hybridization.This method introduces the genetic algorithm in the ant colony algorithm so that the ant colony algorithm does not fall into the local optimum.And this method also improves the state transition factor and accelerates global optimal path convergence velocity of the algorithm.The simulation result shows that∶compared with ant colony algorithm,this method has obvious advantages in reducing the data transmission delay and data packet loss rate,and can improve greatly the real-time and success rate of data acquisition for the power meter remote data acquisition system.

power line carrier communication;the power meter remote data acquisition system;hybrid routing algorithm;reliability

TM714.1

A

1672-3643（2017）04-0052-06

有效訪問地址：http∶//dx.doi.org/10.3969/j.issn.1672-3643.2017.04.010

10.3969/j.issn.1672-3643.2017.04.010

2017-05-12

楊永（1986），男，工程師，主要從事電力系統(tǒng)生產(chǎn)及供電運行管理工作。