一種面向配電通信網WSN分簇路由優化算法

楊 佳，段琪玥，許 強，馮 波

(1.重慶理工大學 電氣與電子工程學院， 重慶 400054；2.重慶工商大學 計算機科學與信息工程學院, 重慶 400067；3.重慶市能源互聯網工程技術研究中心， 重慶 400054)

0 引言

隨著近年來電網智能化、數字化水平的不斷提升，以及《國家電網公司具有中國特色國際領先的能源互聯網規劃》的發布和相關產業落地，電力通信網與電網之間的聯系也越來越緊密。作為能源互聯網的關鍵成分，智能配電通信網(distribution communication network，DCN)需要將配電信息系統中的指令快速、準確地下達給遠程智能終端設備。

配電通信組網整體技術框架由光纖通信、載波通信和寬帶無線通信等技術共同支撐起[1-2]。在智能配電網最后一公里，電力寬帶無線專網接入技術的通信覆蓋范圍會受基站位置的影響，具有網絡鋪設便捷、成本低廉、自組網及數據安全性高等特點的無線傳感器網絡(wireless sensor network，WSN)由于不需要特定的基站，更加適合通信節點數量大且位置特殊的配電通信系統。通過網關補充進光纖、載波等其他通信網，鋪就一張完善的配電通信網，直達有線、無線公網等通信方式難以到達的配電區域。其業務按控制對象可分為以配電自動化為代表的電網生產控制業務和以精準負荷控制為代表的管理信息化業務兩大類；從服務質量(quality of service，QoS)來講，配電自動化要求較低的實時性，但要求較高的安全性和可靠性；而精準負荷控制短時內傳輸的數據量較低。相比之下配電自動化業務在特殊位置的配電通信系統中更難穩定，這也使得針對此類業務進行優化改進更具必要性[3]。配電自動化系統結構見圖1。

圖1 配電自動化系統結構框圖

針對節點消耗問題，合理的分配能量、延長網絡壽命是WSN研究的重點。學者們通常從分簇和路由兩方面進行研究[4-14]。分簇路由方面，鄢麗娟等[4]提出了一種基于平均剩余能量的無線傳感器網絡分簇路由算法，但未給出明確的簇頭選舉機制，也未考慮簇頭能耗。朱敏等[5]提出了一種虛擬網格分簇路由算法CRVB，在一定程度上降低了時延和能耗，但簇首選舉僅考慮剩余能量單一指標。陶洋等[6]提出了一種量獲取無線傳感網能耗均衡分簇路由算法，由于未改善簇內節點非均勻分布的問題，使得能耗均衡性表現一般。楊佳等[7]提出了面向用電信息采集的一種新的異構無線傳感器網絡分簇路由協議，該方法很好地均衡了網絡負載，但未考慮QoS指標，且未建立與配電網相對應的拓撲。路由方面，經典群體智能算法之一的蟻群算法(ACO)被廣泛作為基本算法改進，有些學者針對移動自組織網絡，基于ACO提出了多路徑路由算法ARA。該算法使WSN在信息素低于某個值時進入整體休眠模式以延長網絡生命周期，但未考慮節點間不必要的網絡開銷和時延[8]。石鑫等[9]對基本蟻群算法進行改進，對長鏈狀輸電線WSN進行路由優化，有效保障了網絡的QoS，但配電網與輸電線路場景之間仍存在一定區別，該方法并不能較好的適應。王建平等[10]提出一種基于信息可靠性最優并滿足傳輸實時性的路由選擇模型，應用在黃山電網后達到了電網通信指標，但未考慮網絡壽命問題。Rama等[11]提出了基于ACO的WSN路徑尋優和恢復算法，通過改進的啟發函數，將影響節點通信和網絡生命周期的各個因素納入考慮去尋找路徑，但其搜索前期信息素含量較為匱乏，容易出現盲目搜索、局部最優等現象[12-13]。

基于上述問題，提出了一種基于虛擬網格的蟻群的多目標路由(energy and best distribution of ant colony optimization based on virtual grid，EDACO-VG)算法，通過在螞蟻尋路過程中對路徑信息素進行人為干預，在下一跳概率公式啟發因子中考慮節點當前能量來降低低能量節點失效的概率，避免收斂過快，從而使網絡能量消耗達到平衡。同時，在信息素更新公式里綜合考慮帶寬、時延、丟包率等QoS指標來滿足配電自動化業務要求。實驗結果表明，本文算法在延遲、生命周期以及能耗均衡性上有一定優勢。

1 系統模型

1.1 能耗模型

WSN的能量模型中，節點的能耗由發射端和接收端兩部分能耗組成。在傳輸距離d，發送1 bit的信息消耗的能量ETx(l,d)為:

(1)

(2)

由式(1)和(2)可知，在傳輸范圍R超過門限值d時，能量消耗會快速增加，某些節點會極快地消耗掉能量，縮短網絡的生命周期。本算法中限定節點的傳輸范圍R

1.2 網格模型

鑒于本文配電網WSN各節點均勻布置的特點，對其進行邊長為L的虛擬網格劃分，每個網格編號以[GX,GY]表示。假設sink節點位于網格頂點，且其所屬網格坐標為(0,0)。共享同一頂點和同一條邊的網格互為鄰居網格，其坐標如圖2所示，以此類推。

圖2 虛擬網格示意圖

為了確保相鄰網格中的每個節點之間能夠正常通信，網格邊長L需滿足：

(2L)2+(2L)2≤r2

(3)

網格建立完成后，各節點通過式(4)確定其從屬網格。其中?c」表示小于c的最大整數。

GX=?x/L」,GY=?y/L」

(4)

為了實現網絡均衡耗能，在網格邊緣區域建立寬為s的公共區域。在簇頭選舉完成后，公共區域內的普通節點加入離它最近的簇頭節點成簇，而不一定是加入本網格的簇頭。

1.3 QoS多目標模型

通過對配電通信網各業務的通信規范參數分析來介紹常見的配電通信業務需求，明確其具體標準。智能配電通信網代表業務QoS標準見表1。

表1 智能配電通信網代表業務QoS標準

將QoS的各參數根據配電自動化業務需求定義如下:

1) 時延

(5)

式中:Delay(s)代表總延遲，是路徑s所有節點上的延遲Delay(n)和節點間的延遲Delay(e)之和。可知，延遲大小與路徑節點個數成正比。

2) 帶寬

BandWidth(s)=max{BandWidth(e),e∈E(s)}

(6)

帶寬取路徑s上節點間傳輸數據的最大值。

3) 丟包率

(7)

Lost(n)代表s所有鏈路分支上的丟包率；

4) 剩余能量

(8)

(9)

其中：Eremain代表節點的剩余能量；Estart代表節點的初始能量。

2 算法步驟介紹

2.1 簇頭選舉

若采用傳統的LEACH算法，每個網格內可能會產生多個簇頭。為保證簇頭的唯一性，引入三角模算子，綜合節點到基站距離與節點剩余能量2個目標量來選取每個網格的唯一簇頭。

2.1.1目標量隸屬度

節點到基站距離隸屬度函數：由能量模型可知，節點通信耗能與距離之間呈正相關。選用式(10)的高斯函數作為節點到基站距離隸屬度函數

(10)

(11)

式(11)表示距離歸一化過程。d(i)為節點i到基站距離；a是尖峰中心坐標、b是標準方差，皆為常數，其取值可改變函數位置形狀，本文取a=0，b=1。可見，節點到基站距離越近，則υd(i)越大,其隸屬于簇頭的概率也越大。

節點剩余能量隸屬度函數：簇頭節點往往要消耗更多的能量，某節點若頻繁成為簇頭會破壞網絡能耗的均衡性。剩余能量更多的節點擔任簇頭可保證負載均衡，由此選用式(12) 壓縮率的變形函數作為其隸屬度函數。

(12)

(13)

式(13)為剩余能量歸一化過程。E(i)為節點i的剩余能量，Einit為其初始能量。取A值為150，該式表明剩余能量低于一定值時，該節點當選簇頭的概率將大大降低。

2.1.2三角模算子融合判決

三角模融合判決能夠加強同類信息，調和矛盾信息，其表達式為：

(14)

其中υd(i),υe(i)∈(0,1)，加強性表示為：F(υd(i),υe(i))≥max{υd(i),υe(i)},υd(i)≥0.5,υe(i)≥0.5或F(υd(i),υe(i))≤min{υd(i),υe(i)},υd(i)≤0.5,υe(i)≤0.5調和性表示為min(υd(i),υe(i))

2.2 螞蟻準備階段

每只螞蟻在出發尋路之前更新攜帶內存Mk，包含以下信息：① 需傳遞的數據；② 固定值的能量；③ 所有路過的節點、QoS參數(隊列延遲，丟包率，帶寬空間)。

2.3 螞蟻探索階段

當節點i需要發送信息時，首先查看路由表，如果有下一跳節點信息，則直接依照信息將數據發送，重復上述過程，直到轉發至j；如果沒有，則產生螞蟻去尋找通向目的節點的路徑。螞蟻尋徑示意圖見圖3。

圖3 螞蟻尋徑示意圖

螞蟻的具體探索表達式為：

(15)

螞蟻按照式(15)尋找下一跳。其中，ηij(t)是信息啟發函數，表達式為：

(16)

其中Estart是初始能量。

式(15)中的τij(t)是期望啟發函數

(17)

2.4 路徑信息素強度更新規則

ρ(0<ρ<1)是信息素的蒸發率，它可以對已有鏈路和無效路徑上的信息素值進行調節。對ρ進行設計，初始階段ρ保持在較大的范圍內，此時下一跳節點按照先驗規律進行選擇，尋路具有高收斂性和低隨機性；但若一直保持初期的高收斂性，則容易導致算法陷入局部最優解而無法擺脫，此時需減小ρ，使輸出結果趨于穩定。

綜上所述，為使蒸發函數ρ在算法執行的各個階段滿足對收斂速度和隨機搜索能力的要求，對其進行定義:

(18)

其中：Δτij(t)是人為補充的信息素。本文中算法將配電通信網中關鍵的QoS指標如帶寬、丟包率、時延結合在信息素補充式中，確保螞蟻k在傳輸數據的過程中能根據業務需求選擇路徑。綜上，代價函數的定義為：

(19)

本文中，代價函數作為人為補充信息素Δτij(t)影響螞蟻下一跳節點選擇。式(19)中，ω1、ω2、ω3分別為時延、帶寬和丟包率所占權重，同時需滿足ω1+ω2+ω3=1 且ω1，ω2，ω3≥0。

結合式(15)—(19)可知，Δτij(t)越大，j節點被選為下一跳節點的概率就越大；而ω越大，其對應值在Δτij(t)中的權重越小，對其增長的影響就越小。

2.5 信息更新階段

m只螞蟻的前向尋路過程實際是生成了一棵多目標路由樹，當sink節點收到路由信息后，隨即對其按照式(19)進行評估計算。選取最優和次優兩條路徑，當最優路徑失效后，備用路徑頂替工作來保障配電通信正常。算法的具體過程如下：

步驟1times←0(times表示迭代次數或搜索次數)；對每個τij和Δτij進行初始化；將每個螞蟻各自放在待搜索區域的中心位置，待搜索區域的大小根據螞蟻的數量和所占空間大小來確定；

步驟3針對螞蟻周圍的各個路徑信息素濃度的改變，使用更新方程對各個軌跡強度進行更新；

步驟4每只螞蟻k的數據變化:Δτij←0;times←times+1；

步驟5如果times<預期的搜索次數而且沒有退化行為(即搜索到的都是相同解),則轉回步驟2；

步驟6輸出當前的最優解。

3 仿真結果及分析

為了驗證本文算法的性能，在Matlab2016b環境下進行仿真實驗。因文獻[13]中提出的MRFD算法基于螞蟻算法對多步前向區域建立多路由模型，考慮剩余能量、路徑單包傳遞能耗、條數等進行多路徑的選取，并進行精簡，具有相當參考性，故將其和經典蟻群算法(ACO)作為對照組，用于驗證本文算法的可實施行性。

仿真中，節點隨機分布在500×500的范圍內，sink節點布置在(0，0)處，源節點布置在(500，500)處。仿真參數設置如表2所示。

表2 仿真參數設置

配電網自動化業務對實時性要求較低，對帶寬、安全性和可靠性要求較高。因大多業務需要對配電網數據進行監測和檢測，對數據保存的完整度要求高，對丟包率低的要求略高于實時傳輸時對帶寬分配的調整，因而設置ω1、ω2、ω3分別為0.5、0.3和0.2。

將改進的EDACO-VG算法與經典的ACO和MRFD算法相比較。在實驗中，參數見表2，主要從4個方面來對比算法的性能：節點存活輪數、端到端的延遲、能量開銷和帶寬。為了驗證算法的有效性，通過網路范圍內的源節點隨機產生0～1 000 bits的數據包發送到目的節點。節點存活數見圖4。

圖4 節點存活數

ACO算法在90輪附近節點開始出現死亡；MRFD算法在120輪時節點開始出現死亡；本文算法在260輪時節點出現死亡，相較于ACO和MRFD分別延長生命周期約為180%和116.67%。很顯然，在相同的運行時間下，新算法存活節點數更多，究其原因是本文算法在預設的網格中引入三角模算子，綜合節點位置與剩余能量融合判決出最佳簇頭。簇間路由階段又將鄰居節點剩余能量考慮進了下一跳擇路方程中，且量子蟻群算法本身在全局尋優和快速收斂方面更具優勢，網絡能量利用率得以更加平均，網絡壽命得以延長。

在圖5中觀察3種算法源節點到目標節點的平均時延，在節點密度n為100、150、200、250、300時，經過多次實驗得到最短路徑平均時延。可以看出，與ACO算法和MRFD算法相比，本文算法求得的最短路徑平均延時在220～320 ms附近，降低延遲約1/3，能夠滿足居民用電情況監測的 1 s級和負荷控制與管理通信業務的分鐘級延遲要求。

由圖6可知，隨著時延的增加,配電自動化業務的帶寬需求不斷降低,且幅度逐漸趨于平緩[15]。這是因為需要根據業務重要性對帶寬進行合理的權重分配，如極緊急業務(配電失電信息傳輸等)分得同時段較多帶寬量，非緊急業務(輸電裝置常規信息采集等)分得較少帶寬；帶寬的優化效果是否滿足用戶業務需求同樣可以通過時延看出。如果仿真中時延始終要小于預先設定的時延違閾值且波動不大，則可以滿足配電自動化業務的帶寬分配QoS要求。而由圖5可知，3種算法在業務傳輸數據時都能滿足配電自動化業務的時延需求，而本文模型計算的帶寬結果更平緩，更滿足需求。

圖5 源節點到目標節點的延遲

圖6 時延對帶寬需求影響

由圖7可知采用本文算法、經典ACO算法和MRFD算法在發送0～1 000個數據包區間均勻取10個點時，所消耗的能量對比情況。可以看出，本文算法的能量消耗始終少于ACO算法和ARA算法，并且隨著發包數量的增加，與另2種算法的能量消耗差距越來越大。

由圖8可知，由于在人為補充信息素表達式時考慮了配電自動化業務的丟包率要求作為篩選指標，ED-ACO和另外2個算法相比，丟包率明顯更低,更能滿足配電自動化業務對高壓線路的數據監控需求更加準確的特點。

圖8 傳輸過程中節點丟包率

4 結論

所提出的EDACO-VG算法在延遲、生命周期和能耗均衡性上具有優勢，更能滿足通信網中配電自動化業務需求。與經典蟻群算法ACO和MRFD對比，由于EDACO-VG算法在成簇階段首次引入三角模算子融合判決節點位置和剩余能量，根據最大隸屬度原則選舉簇頭，在一定程度上優化了網絡能耗；在下一跳轉移概率信息啟發函數中綜合考慮了節點剩余能量和路徑信息素更新，又在期望啟發函數中考慮了配電自動化業務對丟包率、帶寬、時延等指標等因素，找到了源節點到目標節點之間的最優路徑，提高了全局搜索的能力，使得求出的解比其他2種對比算法更加適用于DCN的配電自動化業務。

由于仿真時對代價函數中ω的劃分較固定，算法整體能滿足需要的指標，但不一定最優。接下來將探索在不同配電網業務下的ω值劃分，對配電通信網中其他業務和不同業務間帶寬分配滿意度進行優化。