面向輸電線故障信息傳輸的多播路由

陳 巖，李曉卉+，丁月民，劉振興

(1.武漢科技大學 信息科學與工程學院，湖北 武漢 430081；2.天津理工大學 計算機科學與工程學院，天津 300384)

0 引 言

作為電力系統的重要組成部分，智能電網(smart grid，SG)輸電線路故障發生后需將故障信息實時發送給巡檢區域內所有巡檢人員，以便巡檢人員及時處理。多播作為一點對多點的通信，是提高因特網多媒體信息傳輸實時性和節省網絡帶寬的有效方法之一[1]。然而，與多媒體信息實時多播不同，智能電網應用下的信息多播通信不僅要具有實時性，更需要可靠性和經濟高效等特點[2]。因此，因特網的多播路由算法不能直接應用于智能電網通信。

近幾年來，不少學者結合智能電網應用背景對多播路由技術進行改進，并取得了顯著效果。文獻[3]分析了支持多播路由的智能電網中潛在的網絡安全問題，針對電網網絡安全和用戶隱私提出了一種安全、高效的多播路由協議。文獻[4]為多跳mesh網絡中PMU通信提出了一種自適應分布式多播路由方法，以提高電力通信系統的魯棒性。文獻[5]提出了一種基于需求響應能力約束的多播路由算法，該算法將時延和目的節點需求響應能力作為約束條件構造多播樹，穩定電網頻率，保證電網的可靠性。為滿足智能電網廣域控制(WAC)通信的實時性要求，最大限度減少帶寬約束下廣域網(WAN)的端到端時延，文獻[6]提出了一種適用智能電網WAC的多播路由約束優化方法。目前，大多數多播技術集中在智能電網需求響應、網絡安全和廣域控制等方面的應用，而有關多播技術應用于輸電線路故障信息傳輸的研究相對較少。

在智能電網中，通常采用無線傳感器網絡(wireless sensor network，WSN)對輸電線路上的信息進行傳輸[7]。然而，WSN應用于輸電線路故障信息傳輸中存在以下問題：①故障發生時，巡檢區域內各巡檢人員位置不一，人為設置多播樹時延上限不能保證故障信息傳輸的實時性；②輸電線路通信量大，無線節點能量和內存受限，過高的通信代價會給WSN帶來負擔[8]。

為了解決上述問題，本文提出了一種輸電線路故障傳輸多播路由算法(multicast routing algorithm for the transmission of fault information on power transmission line，MRFT)。該算法①為了保證實時性，以時延最短路徑樹(SPT)的最大端到端時延作為多播樹時延上限；②為了減小多播樹通信代價，基于最小代價啟發函數連接剩余葉子節點，保證在滿足時延約束下使通信代價達到最小。

1 網絡模型及多播問題描述

1.1 網絡描述

一般輸電線路故障信息傳輸WSN網絡模型如圖1所示。輸電線上均勻部署著用于監控輸電線路狀態的WSN靜態節點，巡檢人員在輸電線路的兩邊進行巡檢作業，并攜帶WSN節點用于WSN通信。輸電線路上的WSN靜態節點和巡檢人員攜帶的WSN低速移動節點共同構成了WSN網絡。

圖1 輸電線路故障信息傳輸的WSN網絡模型

故障發生后，故障源節點向巡檢區域內的所有巡檢人員發送故障信息。假設每個巡檢人員都以正常步行速度進行巡檢作業，且無特殊情況發生。忽略信息在無線鏈路上的轉發和排隊時延，重點考慮傳播時延，由于信息在WSN中的傳播速率為20 kbps～250 kbps[9]，遠遠超過常人的步行速度，巡檢人員是低速移動節點，相對于傳播時延，低速移動后的位置所造成的時延可以忽略不計。因此可以將故障信息WSN傳輸網絡當作靜態網絡進行分析。

1.2 問題描述

本文中所使用的主要符號見表1。

表1 符號

定義1 輸電線路故障信息實時傳輸網絡可以用一個無向的權重圖G(V,E)表示，其中V表示無線節點集，E表示通信范圍內相鄰節點間的通信鏈路集。c(e) 表示鏈路e上的代價，d(e) 表示鏈路e上的傳播時延。

定義2 設L(v,w) 表示從節點v到節點w的路徑，v,w∈V。T(s,D) 表示多播樹，故障源節點s∈V為多播樹的源節點，巡檢人員集合D∈V為該多播樹的葉子節點集，d∈D為葉子節點。

定義3 設R為正實數集，對于任意鏈路e∈E，時延函數d(e):E→R，代價函數c(e):E→R。

定義4 設T(s,D) 表示一棵多播樹，則式(1)表示路徑L(s,d) 的端到端時延，式(2)表示多播樹T(s,D) 的代價

(1)

(2)

定義5 多播樹時延上限問題：

一棵多播樹的時延通常由這棵樹中端到端時延的最大值決定。由于所有多播樹的最短時延不會比最短時延多播樹的時延還小，設Lspd(s,D) 為源節點s到葉子節點集D的最短時延路徑集合，則多播樹時延上限定義為

δ=max(d(Lspd(s,D)))

(3)

假設路徑Lx(s,dx)∈Lspd(s,D) 為滿足條件路徑，記Lx(s,dx) 為時延上限路徑，節點dx為時延上限節點。

定義6 輸電線路故障信息多播路由問題：

輸電線路故障信息多播路由問題就是要找到一棵滿足時延約束δ下的最小代價樹，即找到一棵多播樹T(s,D) 滿足

min(c(T(s,D)))
s.t.d(L(s,d))≤δ,?d∈D

(4)

2 MRFT算法

式(4)是一個帶約束條件的斯坦納樹問題，已經證明是一個NP完全問題，通常采用啟發式方法求解[10]。為了使巡檢區域內所有巡檢人員能實時接收故障信息、降低通信代價，本文提出了一種基于最小代價啟發函數的輸電線路故障傳輸多播路由算法(MRFT)。為了提高實時性，該算法通過式(3)確定多播樹時延上限。為了在滿足時延約束的情況下減小通信代價，當時延上限路徑接入多播樹后，算法采用一個最小代價啟發函數連接剩余葉子節點。MRFT算法主要包括4個步驟：①源節點監測到故障事件后，將葉子節點集加入到網絡；②求解多播樹時延上限；③判斷MST是否滿足時延約束，若不滿足執行步驟④；④將時延上限路徑接入多播樹，基于最小代價啟發函數連接剩余葉子節點。

2.1 最小代價啟發函數

設集合K={dx,k1,k2,…,kn,s} 為時延上限路徑Lx(s,dx) 中的節點集，其中k1是與dx直接相連的節點，n為路徑Lx(s,dx) 中路由節點個數。為了減少通信代價，定義MRFT算法最小代價路徑選擇啟發函數fc(k,du)

(5)

其中，k∈K，du∈{{D}-dx}，Lspc(k,du) 為節點k到葉子節點du的最小代價路徑，ε(k) 為多播樹中源節點s到節點k的時延。由于多播樹時延上限δ已經是當前情況下的最優值，因此，在連接剩余葉子節點時，啟發函數fc并沒有盡可能減小時延，而是尋找一條滿足時延約束的最小代價路徑。

2.2 MRFT算法流程

根據MRFT算法的4個主要步驟，其偽代碼和具體流程描述如下：

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 網絡模型初始化。在節點間通信鏈路上添加傳輸代價和傳輸時延權重值。在電網模型中隨機選擇一個節點作為源節點s，將多播葉子節點集D加入到網絡;

步驟2 求出源節點s到所有葉子節點的最短時延路徑集合Lspd(s,D)，根據式(3)求出多播樹時延上限δ;

步驟3 采用MST計算最小代價多播樹Tmst(s,D)，若?Lmst(s,d)∈Tmst(s,D) 滿足d(Lmst(s,d))≤δ，則Tmst就是滿足式(4)的多播樹，否則進入步驟4;

步驟4 將時延上限路徑Lx(s,dx) 接入多播樹，將時延上限節點dx從葉子節點集D中刪除。

從葉子節點集D中任選一個節點du作為預連接節點。根據式(5)，依次從集合K中選取節點k，求出節點k到節點du的最小代價路徑Lspc(k,du)。 若ε(k)+d(Lspc(k,du)) 滿足時延約束，則將路徑Lspc(k,du) 接入多播樹。若當k=s時仍無法滿足時延約束條件，則將源節點s到葉子節點du的最短時延路徑Lspd(s,du) 接入多播樹。預連接節點du接入多播樹后，將其從集合D中刪除，再從集合D中任選一個節點作為下一個預連接節點，依次循環，直到所有葉子節點全部接入多播樹。

3 仿真結果分析

為了驗證MRFT算法在智能電網輸電線路故障信息傳輸中的有效性，在MATLAB 2014a中建立輸電線路故障信息傳輸的WSN網絡模型。在相同情況下，將MRFT算法與經典時延受限多播路由算法——KPP算法[10]進行對比，從以下3個方面進行仿真分析：①多播樹時延；②端到端時延方差；③多播樹代價。

3.1 仿真場景及參數

輸電線路故障信息傳輸的WSN仿真場景由輸電線路監測場景和巡檢人員巡檢場景兩部分構成。對于輸電線路監測場景，仿真區域為1000m×100m，4條輸電線分別由4條直線表示：y=80、y=60、y=40和y=20，輸電線上均勻部署著用于傳輸故障信息的傳感器節點。對于巡檢人員巡檢場景，巡檢人員有兩個活動區域，區域1由函數y=0，y=10和x=0，x=1000圍成，區域2由函數y=90，y=100和x=0，x=1000圍成。網絡內節點間鏈路采用Salama算法[11]生成，節點間鏈路概率函數如下

(6)

其中，distance(v,w) 為節點v、w之間的歐式距離，Len為任意兩點間的最大距離，α用于調節短鏈路的密度，β用于調節鏈路密度。當輸電線上的WSN靜態節點總數分別為40、80、120、160、200時，α相應取值為0.12、0.08、0.073、0.068和0.063，β始終為2.2。

設網絡中節點間的鏈路代價為節點間距離，鏈路時延為節點間距離乘以0～1之間的隨機數。從輸電線上隨機選擇一個節點作為源節點，葉子節點在巡檢人員區域內隨機分布。令KPP算法的時延上限Δ與MRFT算法的時延上限δ相同，仿真中每個數據點的值為100次實驗的平均值。

3.2 仿真結果分析

3.2.1 多播樹時延

由于SPT算法構建的多播樹時延較小，因此仿真以SPT算法作為參照，比較MRFT算法和KPP算法所構建多播樹的相對時延。相對時延函數表示如下

(7)

分別從以下兩種情況進行仿真：①當葉子節點為10，網絡節點數與Edelay的關系；②當網絡節點數為40，葉子節點數與Edelay的關系。

如圖2、圖3所示，當網絡中節點數與葉子節點較少時，MRFT算法生成的多播樹的時延性能與KPP算法的時延性能比較接近。隨著節點總數和葉子節點數不斷增加，MRFT算法的相對時延雖有所波動，但總體變化趨勢較為穩定；而KPP算法的相對時延卻隨著網絡規模的增大呈上升趨勢，當網絡節點為200時，二者多播樹時延相差約為50%。

圖2 網絡節點數與Edelay的關系

圖3 葉子節點數與Edelay的關系

3.2.2 端到端時延方差

當網絡節點數為40，端到端相對時延方差對比圖如圖4 所示。時延方差越小說明時延數據越穩定，理想狀態下，當方差為0時，各個巡檢人員會同時收到故障信息。由于有關優化端到端時延方差的研究較少，考慮到SPT算法在優化多播樹時延上具有較好表現，因此，在仿真時仍然以SPT算法為參考計算相對時延方差。端到端相對時延方差函數表示如下

(8)

如圖4所示，MRFT算法在不同葉子節點數下的端到端相對時延方差值均為負值，說明MRFT算法構建的多播樹端到端時延小于SPT算法所構建的多播樹的端到端時延。KPP算法構造的多播樹端到端時延方差比SPT算法平均高出一倍有余，遠大于MRFT算法。MRFT算法基于最小代價啟發函數連接剩余葉子節點，最小代價啟發函數旨在尋找一條滿足時延約束的最小代價路徑，因此，采用MRFT構造的多播樹端到端時延方差較小。

圖4 葉子節點數與Evar的關系

3.2.3 多播樹代價

由于MST算法不考慮時延約束，得到的多播樹代價較小，因此仿真以MST算法作為參照，比較MRFT算法和KPP算法所構建多播樹的相對代價。相對代價函數表示如下

(9)

分別從以下兩個方面進行仿真：①當葉子節點為10，網絡節點數與Ecost的關系；②當網絡節點數為40，葉子節點數與Ecost的關系。

區域內節點總數和葉子節點個數對多播樹代價的影響分別如圖5、圖6所示。隨著網絡節點數和葉子節點個數的增加，多播樹規模逐漸變大，從而占用更多的資源，因此多播樹代價逐漸升高。由于MST算法不考慮時延約束，并且MRFT和KPP算法在構造多播樹時根據SPT的最大端到端時延確定多播樹時延上限，時延約束比較嚴格，可選鏈路較少。因此，與MST算法所構造的多播樹相比，MRFT和KPP算法構造的多播樹代價相對較高。盡管如此，本文所提出的MRFT算法在不同葉子節點數和網絡節點數下的代價均優于KPP算法。

圖6 葉子節點數與Ecost的關系

3種情況下的仿真結果表明，本文提出的電網輸電線路故障信息傳輸多播路由算法——MRFT在多播樹時延、端到端時延方差和多播樹代價3個方面的表現均優于KPP算法。盡管相對MST算法來說，MRFT算法構建的多播樹代價較高，但由于MRFT算法的多播樹時延與端到端時延較低，且故障事件發生的概率較低，因此，短時間、低頻率的故障信息傳輸行為不會對WSN網絡造成太大負擔。

4 結束語

本文提出了一種智能電網輸電線路故障信息傳輸多播路由算法，該算法根據SPT的最大端到端時延確定多播樹時延上限，當時延上限邊接入多播樹后，基于最小代價啟發函數連接剩余葉子節點。仿真結果表明，該算法構造的多播樹能夠在滿足時延約束的同時降低通信代價，確保故障信息能實時發送給巡檢人員。本文的仿真實驗是在靜態網絡模型中進行的，下一步將結合巡檢人員速度信息對該算法進行改進，使其應用于半動態輸電線路故障信息傳輸WSN網絡。