陳 巖,李曉卉+,丁月民,劉振興
(1.武漢科技大學(xué) 信息科學(xué)與工程學(xué)院,湖北 武漢 430081;2.天津理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,天津 300384)
作為電力系統(tǒng)的重要組成部分,智能電網(wǎng)(smart grid,SG)輸電線路故障發(fā)生后需將故障信息實(shí)時(shí)發(fā)送給巡檢區(qū)域內(nèi)所有巡檢人員,以便巡檢人員及時(shí)處理。多播作為一點(diǎn)對(duì)多點(diǎn)的通信,是提高因特網(wǎng)多媒體信息傳輸實(shí)時(shí)性和節(jié)省網(wǎng)絡(luò)帶寬的有效方法之一[1]。然而,與多媒體信息實(shí)時(shí)多播不同,智能電網(wǎng)應(yīng)用下的信息多播通信不僅要具有實(shí)時(shí)性,更需要可靠性和經(jīng)濟(jì)高效等特點(diǎn)[2]。因此,因特網(wǎng)的多播路由算法不能直接應(yīng)用于智能電網(wǎng)通信。
近幾年來,不少學(xué)者結(jié)合智能電網(wǎng)應(yīng)用背景對(duì)多播路由技術(shù)進(jìn)行改進(jìn),并取得了顯著效果。文獻(xiàn)[3]分析了支持多播路由的智能電網(wǎng)中潛在的網(wǎng)絡(luò)安全問題,針對(duì)電網(wǎng)網(wǎng)絡(luò)安全和用戶隱私提出了一種安全、高效的多播路由協(xié)議。文獻(xiàn)[4]為多跳mesh網(wǎng)絡(luò)中PMU通信提出了一種自適應(yīng)分布式多播路由方法,以提高電力通信系統(tǒng)的魯棒性。文獻(xiàn)[5]提出了一種基于需求響應(yīng)能力約束的多播路由算法,該算法將時(shí)延和目的節(jié)點(diǎn)需求響應(yīng)能力作為約束條件構(gòu)造多播樹,穩(wěn)定電網(wǎng)頻率,保證電網(wǎng)的可靠性。為滿足智能電網(wǎng)廣域控制(WAC)通信的實(shí)時(shí)性要求,最大限度減少帶寬約束下廣域網(wǎng)(WAN)的端到端時(shí)延,文獻(xiàn)[6]提出了一種適用智能電網(wǎng)WAC的多播路由約束優(yōu)化方法。目前,大多數(shù)多播技術(shù)集中在智能電網(wǎng)需求響應(yīng)、網(wǎng)絡(luò)安全和廣域控制等方面的應(yīng)用,而有關(guān)多播技術(shù)應(yīng)用于輸電線路故障信息傳輸?shù)难芯肯鄬?duì)較少。
在智能電網(wǎng)中,通常采用無線傳感器網(wǎng)絡(luò)(wireless sensor network,WSN)對(duì)輸電線路上的信息進(jìn)行傳輸[7]。然而,WSN應(yīng)用于輸電線路故障信息傳輸中存在以下問題:①故障發(fā)生時(shí),巡檢區(qū)域內(nèi)各巡檢人員位置不一,人為設(shè)置多播樹時(shí)延上限不能保證故障信息傳輸?shù)膶?shí)時(shí)性;②輸電線路通信量大,無線節(jié)點(diǎn)能量和內(nèi)存受限,過高的通信代價(jià)會(huì)給WSN帶來負(fù)擔(dān)[8]。
為了解決上述問題,本文提出了一種輸電線路故障傳輸多播路由算法(multicast routing algorithm for the transmission of fault information on power transmission line,MRFT)。該算法①為了保證實(shí)時(shí)性,以時(shí)延最短路徑樹(SPT)的最大端到端時(shí)延作為多播樹時(shí)延上限;②為了減小多播樹通信代價(jià),基于最小代價(jià)啟發(fā)函數(shù)連接剩余葉子節(jié)點(diǎn),保證在滿足時(shí)延約束下使通信代價(jià)達(dá)到最小。
一般輸電線路故障信息傳輸WSN網(wǎng)絡(luò)模型如圖1所示。輸電線上均勻部署著用于監(jiān)控輸電線路狀態(tài)的WSN靜態(tài)節(jié)點(diǎn),巡檢人員在輸電線路的兩邊進(jìn)行巡檢作業(yè),并攜帶WSN節(jié)點(diǎn)用于WSN通信。輸電線路上的WSN靜態(tài)節(jié)點(diǎn)和巡檢人員攜帶的WSN低速移動(dòng)節(jié)點(diǎn)共同構(gòu)成了WSN網(wǎng)絡(luò)。
圖1 輸電線路故障信息傳輸?shù)腤SN網(wǎng)絡(luò)模型
故障發(fā)生后,故障源節(jié)點(diǎn)向巡檢區(qū)域內(nèi)的所有巡檢人員發(fā)送故障信息。假設(shè)每個(gè)巡檢人員都以正常步行速度進(jìn)行巡檢作業(yè),且無特殊情況發(fā)生。忽略信息在無線鏈路上的轉(zhuǎn)發(fā)和排隊(duì)時(shí)延,重點(diǎn)考慮傳播時(shí)延,由于信息在WSN中的傳播速率為20 kbps~250 kbps[9],遠(yuǎn)遠(yuǎn)超過常人的步行速度,巡檢人員是低速移動(dòng)節(jié)點(diǎn),相對(duì)于傳播時(shí)延,低速移動(dòng)后的位置所造成的時(shí)延可以忽略不計(jì)。因此可以將故障信息WSN傳輸網(wǎng)絡(luò)當(dāng)作靜態(tài)網(wǎng)絡(luò)進(jìn)行分析。
本文中所使用的主要符號(hào)見表1。
表1 符號(hào)
定義1 輸電線路故障信息實(shí)時(shí)傳輸網(wǎng)絡(luò)可以用一個(gè)無向的權(quán)重圖G(V,E)表示,其中V表示無線節(jié)點(diǎn)集,E表示通信范圍內(nèi)相鄰節(jié)點(diǎn)間的通信鏈路集。c(e) 表示鏈路e上的代價(jià),d(e) 表示鏈路e上的傳播時(shí)延。
定義2 設(shè)L(v,w) 表示從節(jié)點(diǎn)v到節(jié)點(diǎn)w的路徑,v,w∈V。T(s,D) 表示多播樹,故障源節(jié)點(diǎn)s∈V為多播樹的源節(jié)點(diǎn),巡檢人員集合D∈V為該多播樹的葉子節(jié)點(diǎn)集,d∈D為葉子節(jié)點(diǎn)。
定義3 設(shè)R為正實(shí)數(shù)集,對(duì)于任意鏈路e∈E,時(shí)延函數(shù)d(e):E→R,代價(jià)函數(shù)c(e):E→R。
定義4 設(shè)T(s,D) 表示一棵多播樹,則式(1)表示路徑L(s,d) 的端到端時(shí)延,式(2)表示多播樹T(s,D) 的代價(jià)
(1)
(2)
定義5 多播樹時(shí)延上限問題:
一棵多播樹的時(shí)延通常由這棵樹中端到端時(shí)延的最大值決定。由于所有多播樹的最短時(shí)延不會(huì)比最短時(shí)延多播樹的時(shí)延還小,設(shè)Lspd(s,D) 為源節(jié)點(diǎn)s到葉子節(jié)點(diǎn)集D的最短時(shí)延路徑集合,則多播樹時(shí)延上限定義為
δ=max(d(Lspd(s,D)))
(3)
假設(shè)路徑Lx(s,dx)∈Lspd(s,D) 為滿足條件路徑,記Lx(s,dx) 為時(shí)延上限路徑,節(jié)點(diǎn)dx為時(shí)延上限節(jié)點(diǎn)。
定義6 輸電線路故障信息多播路由問題:
輸電線路故障信息多播路由問題就是要找到一棵滿足時(shí)延約束δ下的最小代價(jià)樹,即找到一棵多播樹T(s,D) 滿足
min(c(T(s,D)))
s.t.d(L(s,d))≤δ,?d∈D
(4)
式(4)是一個(gè)帶約束條件的斯坦納樹問題,已經(jīng)證明是一個(gè)NP完全問題,通常采用啟發(fā)式方法求解[10]。為了使巡檢區(qū)域內(nèi)所有巡檢人員能實(shí)時(shí)接收故障信息、降低通信代價(jià),本文提出了一種基于最小代價(jià)啟發(fā)函數(shù)的輸電線路故障傳輸多播路由算法(MRFT)。為了提高實(shí)時(shí)性,該算法通過式(3)確定多播樹時(shí)延上限。為了在滿足時(shí)延約束的情況下減小通信代價(jià),當(dāng)時(shí)延上限路徑接入多播樹后,算法采用一個(gè)最小代價(jià)啟發(fā)函數(shù)連接剩余葉子節(jié)點(diǎn)。MRFT算法主要包括4個(gè)步驟:①源節(jié)點(diǎn)監(jiān)測到故障事件后,將葉子節(jié)點(diǎn)集加入到網(wǎng)絡(luò);②求解多播樹時(shí)延上限;③判斷MST是否滿足時(shí)延約束,若不滿足執(zhí)行步驟④;④將時(shí)延上限路徑接入多播樹,基于最小代價(jià)啟發(fā)函數(shù)連接剩余葉子節(jié)點(diǎn)。
設(shè)集合K={dx,k1,k2,…,kn,s} 為時(shí)延上限路徑Lx(s,dx) 中的節(jié)點(diǎn)集,其中k1是與dx直接相連的節(jié)點(diǎn),n為路徑Lx(s,dx) 中路由節(jié)點(diǎn)個(gè)數(shù)。為了減少通信代價(jià),定義MRFT算法最小代價(jià)路徑選擇啟發(fā)函數(shù)fc(k,du)
(5)
其中,k∈K,du∈{{D}-dx},Lspc(k,du) 為節(jié)點(diǎn)k到葉子節(jié)點(diǎn)du的最小代價(jià)路徑,ε(k) 為多播樹中源節(jié)點(diǎn)s到節(jié)點(diǎn)k的時(shí)延。由于多播樹時(shí)延上限δ已經(jīng)是當(dāng)前情況下的最優(yōu)值,因此,在連接剩余葉子節(jié)點(diǎn)時(shí),啟發(fā)函數(shù)fc并沒有盡可能減小時(shí)延,而是尋找一條滿足時(shí)延約束的最小代價(jià)路徑。
根據(jù)MRFT算法的4個(gè)主要步驟,其偽代碼和具體流程描述如下:
Algorithm:MRFT(G,s,D)
(1)δ←max(d(Lspd(s,D)));T1←Tmst(s,D);
(2)IFmax(d(Lmst(s,D)))≤δthenreturnT1as solution;
(3)T2←Lx(s,dx);
(4)Foralldu∈{{D}-dx}Do
(5)Forallk∈KDo
(6)IFε(k)+d(Lspc(k,du))≤δthen
(7)T2←Lspc(k,du);break;
(8)EndIF
(9)IF((k=s)andd(Lspc(s,du)>δ))then
(10)T2←Lspd(s,du);
(11)EndIF
(12)EndFor
(13)EndFor
(14)returnT2as solution;
步驟1 網(wǎng)絡(luò)模型初始化。在節(jié)點(diǎn)間通信鏈路上添加傳輸代價(jià)和傳輸時(shí)延權(quán)重值。在電網(wǎng)模型中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)s,將多播葉子節(jié)點(diǎn)集D加入到網(wǎng)絡(luò);
步驟2 求出源節(jié)點(diǎn)s到所有葉子節(jié)點(diǎn)的最短時(shí)延路徑集合Lspd(s,D),根據(jù)式(3)求出多播樹時(shí)延上限δ;
步驟3 采用MST計(jì)算最小代價(jià)多播樹Tmst(s,D),若?Lmst(s,d)∈Tmst(s,D) 滿足d(Lmst(s,d))≤δ,則Tmst就是滿足式(4)的多播樹,否則進(jìn)入步驟4;
步驟4 將時(shí)延上限路徑Lx(s,dx) 接入多播樹,將時(shí)延上限節(jié)點(diǎn)dx從葉子節(jié)點(diǎn)集D中刪除。
從葉子節(jié)點(diǎn)集D中任選一個(gè)節(jié)點(diǎn)du作為預(yù)連接節(jié)點(diǎn)。根據(jù)式(5),依次從集合K中選取節(jié)點(diǎn)k,求出節(jié)點(diǎn)k到節(jié)點(diǎn)du的最小代價(jià)路徑Lspc(k,du)。 若ε(k)+d(Lspc(k,du)) 滿足時(shí)延約束,則將路徑Lspc(k,du) 接入多播樹。若當(dāng)k=s時(shí)仍無法滿足時(shí)延約束條件,則將源節(jié)點(diǎn)s到葉子節(jié)點(diǎn)du的最短時(shí)延路徑Lspd(s,du) 接入多播樹。預(yù)連接節(jié)點(diǎn)du接入多播樹后,將其從集合D中刪除,再從集合D中任選一個(gè)節(jié)點(diǎn)作為下一個(gè)預(yù)連接節(jié)點(diǎn),依次循環(huán),直到所有葉子節(jié)點(diǎn)全部接入多播樹。
為了驗(yàn)證MRFT算法在智能電網(wǎng)輸電線路故障信息傳輸中的有效性,在MATLAB 2014a中建立輸電線路故障信息傳輸?shù)腤SN網(wǎng)絡(luò)模型。在相同情況下,將MRFT算法與經(jīng)典時(shí)延受限多播路由算法——KPP算法[10]進(jìn)行對(duì)比,從以下3個(gè)方面進(jìn)行仿真分析:①多播樹時(shí)延;②端到端時(shí)延方差;③多播樹代價(jià)。
輸電線路故障信息傳輸?shù)腤SN仿真場景由輸電線路監(jiān)測場景和巡檢人員巡檢場景兩部分構(gòu)成。對(duì)于輸電線路監(jiān)測場景,仿真區(qū)域?yàn)?000m×100m,4條輸電線分別由4條直線表示:y=80、y=60、y=40和y=20,輸電線上均勻部署著用于傳輸故障信息的傳感器節(jié)點(diǎn)。對(duì)于巡檢人員巡檢場景,巡檢人員有兩個(gè)活動(dòng)區(qū)域,區(qū)域1由函數(shù)y=0,y=10和x=0,x=1000圍成,區(qū)域2由函數(shù)y=90,y=100和x=0,x=1000圍成。網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)間鏈路采用Salama算法[11]生成,節(jié)點(diǎn)間鏈路概率函數(shù)如下
(6)
其中,distance(v,w) 為節(jié)點(diǎn)v、w之間的歐式距離,Len為任意兩點(diǎn)間的最大距離,α用于調(diào)節(jié)短鏈路的密度,β用于調(diào)節(jié)鏈路密度。當(dāng)輸電線上的WSN靜態(tài)節(jié)點(diǎn)總數(shù)分別為40、80、120、160、200時(shí),α相應(yīng)取值為0.12、0.08、0.073、0.068和0.063,β始終為2.2。
設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)間的鏈路代價(jià)為節(jié)點(diǎn)間距離,鏈路時(shí)延為節(jié)點(diǎn)間距離乘以0~1之間的隨機(jī)數(shù)。從輸電線上隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn),葉子節(jié)點(diǎn)在巡檢人員區(qū)域內(nèi)隨機(jī)分布。令KPP算法的時(shí)延上限Δ與MRFT算法的時(shí)延上限δ相同,仿真中每個(gè)數(shù)據(jù)點(diǎn)的值為100次實(shí)驗(yàn)的平均值。
3.2.1 多播樹時(shí)延
由于SPT算法構(gòu)建的多播樹時(shí)延較小,因此仿真以SPT算法作為參照,比較MRFT算法和KPP算法所構(gòu)建多播樹的相對(duì)時(shí)延。相對(duì)時(shí)延函數(shù)表示如下
(7)
分別從以下兩種情況進(jìn)行仿真:①當(dāng)葉子節(jié)點(diǎn)為10,網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)與Edelay的關(guān)系;②當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為40,葉子節(jié)點(diǎn)數(shù)與Edelay的關(guān)系。
如圖2、圖3所示,當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)與葉子節(jié)點(diǎn)較少時(shí),MRFT算法生成的多播樹的時(shí)延性能與KPP算法的時(shí)延性能比較接近。隨著節(jié)點(diǎn)總數(shù)和葉子節(jié)點(diǎn)數(shù)不斷增加,MRFT算法的相對(duì)時(shí)延雖有所波動(dòng),但總體變化趨勢較為穩(wěn)定;而KPP算法的相對(duì)時(shí)延卻隨著網(wǎng)絡(luò)規(guī)模的增大呈上升趨勢,當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)為200時(shí),二者多播樹時(shí)延相差約為50%。
圖2 網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)與Edelay的關(guān)系
圖3 葉子節(jié)點(diǎn)數(shù)與Edelay的關(guān)系
3.2.2 端到端時(shí)延方差
當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為40,端到端相對(duì)時(shí)延方差對(duì)比圖如圖4 所示。時(shí)延方差越小說明時(shí)延數(shù)據(jù)越穩(wěn)定,理想狀態(tài)下,當(dāng)方差為0時(shí),各個(gè)巡檢人員會(huì)同時(shí)收到故障信息。由于有關(guān)優(yōu)化端到端時(shí)延方差的研究較少,考慮到SPT算法在優(yōu)化多播樹時(shí)延上具有較好表現(xiàn),因此,在仿真時(shí)仍然以SPT算法為參考計(jì)算相對(duì)時(shí)延方差。端到端相對(duì)時(shí)延方差函數(shù)表示如下
(8)
如圖4所示,MRFT算法在不同葉子節(jié)點(diǎn)數(shù)下的端到端相對(duì)時(shí)延方差值均為負(fù)值,說明MRFT算法構(gòu)建的多播樹端到端時(shí)延小于SPT算法所構(gòu)建的多播樹的端到端時(shí)延。KPP算法構(gòu)造的多播樹端到端時(shí)延方差比SPT算法平均高出一倍有余,遠(yuǎn)大于MRFT算法。MRFT算法基于最小代價(jià)啟發(fā)函數(shù)連接剩余葉子節(jié)點(diǎn),最小代價(jià)啟發(fā)函數(shù)旨在尋找一條滿足時(shí)延約束的最小代價(jià)路徑,因此,采用MRFT構(gòu)造的多播樹端到端時(shí)延方差較小。
圖4 葉子節(jié)點(diǎn)數(shù)與Evar的關(guān)系
3.2.3 多播樹代價(jià)
由于MST算法不考慮時(shí)延約束,得到的多播樹代價(jià)較小,因此仿真以MST算法作為參照,比較MRFT算法和KPP算法所構(gòu)建多播樹的相對(duì)代價(jià)。相對(duì)代價(jià)函數(shù)表示如下
(9)
分別從以下兩個(gè)方面進(jìn)行仿真:①當(dāng)葉子節(jié)點(diǎn)為10,網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)與Ecost的關(guān)系;②當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為40,葉子節(jié)點(diǎn)數(shù)與Ecost的關(guān)系。
區(qū)域內(nèi)節(jié)點(diǎn)總數(shù)和葉子節(jié)點(diǎn)個(gè)數(shù)對(duì)多播樹代價(jià)的影響分別如圖5、圖6所示。隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和葉子節(jié)點(diǎn)個(gè)數(shù)的增加,多播樹規(guī)模逐漸變大,從而占用更多的資源,因此多播樹代價(jià)逐漸升高。由于MST算法不考慮時(shí)延約束,并且MRFT和KPP算法在構(gòu)造多播樹時(shí)根據(jù)SPT的最大端到端時(shí)延確定多播樹時(shí)延上限,時(shí)延約束比較嚴(yán)格,可選鏈路較少。因此,與MST算法所構(gòu)造的多播樹相比,MRFT和KPP算法構(gòu)造的多播樹代價(jià)相對(duì)較高。盡管如此,本文所提出的MRFT算法在不同葉子節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)下的代價(jià)均優(yōu)于KPP算法。
圖6 葉子節(jié)點(diǎn)數(shù)與Ecost的關(guān)系
3種情況下的仿真結(jié)果表明,本文提出的電網(wǎng)輸電線路故障信息傳輸多播路由算法——MRFT在多播樹時(shí)延、端到端時(shí)延方差和多播樹代價(jià)3個(gè)方面的表現(xiàn)均優(yōu)于KPP算法。盡管相對(duì)MST算法來說,MRFT算法構(gòu)建的多播樹代價(jià)較高,但由于MRFT算法的多播樹時(shí)延與端到端時(shí)延較低,且故障事件發(fā)生的概率較低,因此,短時(shí)間、低頻率的故障信息傳輸行為不會(huì)對(duì)WSN網(wǎng)絡(luò)造成太大負(fù)擔(dān)。
本文提出了一種智能電網(wǎng)輸電線路故障信息傳輸多播路由算法,該算法根據(jù)SPT的最大端到端時(shí)延確定多播樹時(shí)延上限,當(dāng)時(shí)延上限邊接入多播樹后,基于最小代價(jià)啟發(fā)函數(shù)連接剩余葉子節(jié)點(diǎn)。仿真結(jié)果表明,該算法構(gòu)造的多播樹能夠在滿足時(shí)延約束的同時(shí)降低通信代價(jià),確保故障信息能實(shí)時(shí)發(fā)送給巡檢人員。本文的仿真實(shí)驗(yàn)是在靜態(tài)網(wǎng)絡(luò)模型中進(jìn)行的,下一步將結(jié)合巡檢人員速度信息對(duì)該算法進(jìn)行改進(jìn),使其應(yīng)用于半動(dòng)態(tài)輸電線路故障信息傳輸WSN網(wǎng)絡(luò)。