基于改進Bellman-Ford的電網數據采集路由算法

田 園 馬 文 原 野 張 梅 羅施章

1(云南電網有限責任公司信息中心 云南 昆明 650500)2(昆明能訊科技有限責任公司 云南 昆明 650021)

0 引 言

隨著工農業、城鎮生活等各領域用電需求量急劇上升,智能電網[1]中用戶業務數據總量增加,數據傳輸規模加大,因此需對智能電網的數據采集[2]過程進行優化改進,以滿足數據采集過程中對整個電網數據傳輸吞吐量、數據傳輸穩定性及可靠性、數據傳輸效率及時效性等方面的需求,為降低電網建設成本,提升其靈活性及抗干擾能力,常采用mesh結構進行電網數據采集,而使用該多跳結構會導致數據傳輸距離較長、所采集數據的傳輸延時較高,從而無法保證電網數據傳輸[3]的時效性。

為降低上述電網數據的傳輸時延,常將傳統Bellman-Ford(又稱最短路徑樹)算法應用至無線多跳mesh網絡中進行電網數據采集,該算法以每條路徑傳輸跳數作為鏈路權重構建度量值,以度量值最小作為每一拓撲節點從其鄰居節點中選擇下一跳傳輸節點的決策指標,從而使得所采集的電網數據均通過跳數較少的路徑傳輸至主網關數據接入點(Access Point,AP)節點,降低電網數據的傳輸時延。

傳統Bellman-Ford算法雖通過減少數據傳輸路徑跳數降低了電網數據的傳輸時延[4],但會導致各網絡節點為降低傳輸時延均選擇跳數較少的路徑上的節點作為所采集電網數據的下一跳傳輸節點,從而使得數據傳輸任務過于集中在較短路徑上,易造成路徑中關鍵節點出現擁塞,形成網絡傳輸瓶頸,加大數據傳輸丟包率,同時會導致部分數據進入重傳機制,增加了自身的傳輸時延。

針對傳統Bellman-Ford算法[5]在電網數據采集過程中存在的上述問題,本文提出一種基于改進Bellman-Ford的電網數據采集路由算法,該算法結合路徑跳數與節點剩余傳輸容量構建綜合度量值,作為電網數據傳輸子節點與父節點選擇的決策指標,采用DSDV路由協議建立并更新各節點路由信息表[6],并通過時間復用與功率控制消除傳輸過程中存在的“隱藏終端”與“暴露終端”現象,從而平衡各節點數據流量以及減少數據在網絡中傳輸的時間。

1 傳統Bellman-Ford電網數據采集算法

1.1 算法描述

為降低電網數據采集過程中的傳輸時延,保證數據傳輸的時效性及采集效率,采用傳統Bellman-Ford電網數據采集算法進行數據采集,該算法首先結合無線多跳mesh網絡結構抽象出電網數據采集及傳輸過程的網絡模型,并通過構建數學模型對該網絡模型進行具體數據采集模擬,然后根據路徑傳輸跳數[7]構建決策度量值開始數據流量傳輸路由過程,最后根據路由協議建立各節點路由信息表,并設定其更新方式,具體如下:

(1) 構建網絡模型:電網數據采集網絡中至少包含一個AP主網關節點[8],以及若干個子網網關無線路由器(Wireless Router,WR)節點和分布各層的數據采集節點及傳輸子節點,各子節點均具備數據采集、接收、傳輸功能,如圖1所示。

圖1 電網數據采集網絡拓撲結構

圖1中網絡模型在電網數據采集過程中采取單WR網關結構,各數據采集子節點通過分層結構分布在WR節點以下,各子節點必須通過一條傳輸路徑先將所采集電網數據傳輸至自身所在區域子網WR節點,然后通過該WR節點將數據傳輸至主網關AP節點,至此完成整個電網數據采集過程。

(2) 構建數學模型:假設電網數據采集網絡中某單WR采集網絡中包含a個子節點,表述為Ni(i=1,2,…,a),其鄰居節點為NBi,網絡中各鏈路表示為e(Ni,Nk),SG為子網網關WR節點,N為所有數據采集點集合,即N={SG,N1,N2,…,Nn},h(Ni)為節點Ni到子網網關的最短路徑[8]傳輸跳數,若令h(Ni)的最大值為H,即H=h(Ni)max,則H可代表單WR采集網絡中數據采集點數,則:Ni∈N(h),h=0,1,…,H,其中SG∈N(0)。

(3) 構建決策度量值及路由信息表:在構建源節點S到目的節點D的決策度量值[9]Metric(S,D)過程中,以節點間最小傳輸跳數構建鏈路權重及決策度量值,以兩子節點Ni、Nk間鏈路e(Ni,Nk)是否屬可直接連通鏈路l,計算兩點間邊的權重w(Ni,Nk),即:

若源節點S到目的節點D的路徑集合為p,各路徑度量值Metric(p)為該路徑上所有節點間邊的權重w(Ni、Nk)之和,即:

將集合p中鏈路度量值Metric(p)最小的鏈路p(v)作為數據傳輸鏈路,并選擇該鏈路上的首端節點作為源節點S選擇的下一跳節點:

根據DSDV路由協議構建源節點S到目的節點D傳輸路徑上各子節點路由信息表,包含如表1所示的信息表項。

表1 傳統Bellman-Ford算法路由信息表項

表1中目的節點(Dest)特指網絡中的WR子網網關節點,下一跳節點(Next Hop)指最優電網數據傳輸路徑上的各子節點的下一跳節點,度量值(Metric)為源節點S到目的節點D的路徑消耗,序列號(Seq.No)代指電網數據信息包ID號,用于判斷路由信息是否及時更新,序列號較大電網數據包為最新路由信息。

(4) 路由過程及路由更新[10]:采用傳統Bellman-Ford算法在路徑選擇過程中,為防止遍歷節點過多,影響數據采集效率,結合貪婪算法將所有子節點Ni,分為集合T1、T2,其中T1∈p(v)、T2?p(v),然后將T2集合中的節點按照跳數遞增的順序添加到集合T1中,且電網數據傳輸過程中嚴格按照路由信息表中度量值(Metric)最小進行下一跳節點選擇,并將各項信息記錄在路由表中,具體路由過程如圖2所示。

圖2 傳統Bellman-Ford算法路由過程示意圖

1.2 問題描述

問題2:如圖3所示,子節點N1、N2均位于彼此通信范圍外,從而無法獲取對方的數據傳輸信息,由于N3位于兩者通信范圍內,故可同時接收到來自子節點N1、N2的數據信息包,而在同一周期內,當N1向N3發送數據時,由于N2位于N1通信范圍之外,無法檢測到節點N1正在向節點N3傳輸數據,若此時N2也向節點N3發送數據,則會在數據接收端N3處產生數據碰撞[12],從而造成數據包丟失,出現“隱藏終端”現象。

圖3 “隱藏終端”數據碰撞模型

如圖4所示,N3位于N2通信范圍內,位于N1通信范圍外,子節點N1、N2均位于彼此通信范圍內,從而可獲取對方數據傳輸信道在同一時間是否被占用,由于N3位于兩者通信范圍內,故可同時接收到來自子節點N1、N2的數據信息包,而在同一周期內,當N1向N3發送數據、N2向N4發送數據時,N1會檢測到N2的數據傳輸信道正在被占用,為避免發生數據碰撞,N1會延緩自己的數據傳輸,從而產生不必要的數據傳輸延時,使得節點傳輸容量無法合理充分使用,限制整個電網數據流量,出現“隱藏終端”現象。

圖4 “暴露終端”干擾模型

2 改進的Bellman-Ford電網數據采集路由算法

2.1 重構決策度量值及路由信息表

由各子節點剩余傳輸容量A(i)以及各數據傳輸鏈路e(Ni,Nk)的最小跳數h(Ni,Nk)構建各鏈路權重w(Ni,Nk):

故可由各鏈路權重w(Ni,Nk),構建源節點S到目的節點D的綜合決策度量值Metric(S,D),即:

上述綜合決策度量值Metric(S,D),結合了鏈路最小跳數以及節點剩余可用容量,保證電網數據傳輸時延較低保證其實時性的同時還避免了網絡瓶頸的出現,從而降低了數據丟包率提升數據傳輸效率,以免其進入數據重傳機制加大數據傳輸延時。

根據DSDV路由協議結合上述綜合決策度量值Metric(S,D)重新構建各節點Ni路由向量信息表,將原本路由表中決策度量值用結合跳數與節點剩余傳輸容量的綜合決策度量值代替原有跳數權值,具體各信息表項如表2所示。

表2 經改進Bellman-Ford算法路由信息表項

在數據傳輸過程中采用上述路由信息表,雖然有可能使得無法實現數據傳輸最短路徑,但是可以避免關鍵節點產生擁塞,從而避免溢出數據包進入重傳機制,增加傳輸時延,節點綜合決策度量值更改后參照圖2進行路由過程。

路由更新方式分為時間觸發與事件觸發兩種方式,本文算法采用時間與事件觸發相結合的方式進行路由更新,其中時間觸發以電網數據傳輸周期作為其更新周期,事件觸發以電網中出現故障警告作為其觸發更新的條件。為保證后續節點根據最新節點綜合度量值進行路徑選擇,避免出現網絡瓶頸,每一次數據傳輸完成后首先對節點剩余傳輸容量進行實時更改,隨后才觸發路由更新。

2.2 消除“隱藏終端”及“暴露終端”

為避免在同一周期內,兩節點同時向同一節點發送數據產生數據碰撞,從而造成數據丟失,通過采取時間復用[14]的方式,將一個傳輸周期分為若干個數據傳輸時隙(時隙數等于發送節點數),各發送節點均可獲得相互獨立的數據傳輸時隙,各節點時隙內只允許該節點自身進行數據傳輸,從而消除“隱藏終端”現象且同時確定了完成一次數據傳輸所需最短時間,即傳輸周期,可通過調度時隙分配方案提升數據傳輸速率,具體時隙分配如圖5所示。

圖5 周期內發送時隙分配流程

在發送時隙中,有發送節點則存在數據接收節點,當節點為下一跳節點時,則進行數據接收,其剩余傳輸容量不足以接收數據包,則丟棄該數據包,不確認接收成功,由其他層傳輸,若其剩余傳輸容量足以接收數據包,則與自身生成數據包進行聚合排列,開始下一跳傳輸過程,當節點不為下一跳節點時,則等待下一個時隙接收數據,具體時隙分配如圖6所示。

圖6 周期內接收時隙分配流程

為保證綜合決策度量值Metric(S,D)實時性,需在每一周期結束路由更新前對節點剩余傳輸容量A(i)進行實時更新,按上述時隙分配方案以周期內時隙作為節點剩余傳輸容量更新周期,本文算法具體步驟如下:

(1) 根據無線mesh多跳網絡拓撲構建電網數據傳輸網絡模型,含AP主網關節點、若干WR子網網關節點以及分布廣泛的數據采集子節點,傳輸采取單WR子網網關節點區域傳輸模式,各子節點均需通過各自領域WR子網網關節點傳輸至AP節點。

(3) 在步驟(2)數學模型的基礎上,結合各路徑傳輸跳數與路徑首端節點剩余傳輸容量A(i)構建綜合決策度量值,并根據DSDV路由協議建立各子節點路由信息向量表,以綜合決策度量值替代原有以跳數為基礎構建的度量值。

(4) 各數據采集子節點以步驟(3)中綜合決策度量值開始數據傳輸路由過程,并設置傳輸周期內各節點傳輸時隙與接收時隙,以避免“隱藏終端”與“暴露終端”現象,為保證節點路由信息更新實時性,采取時間觸發為主、事件觸發為輔、數據接收時隙為更新周期的方式進行路由更新過程。

3 算法仿真及結果分析

3.1 評價指標

式(9)表明,由于各數據采集子節點在同一周期內其參數基本不變,故可通過降低擁塞節點其鄰居節點在此期間向其發送數據包數v,以此降低節點丟包率PLRi,若在發生數據傳輸擁塞至傳輸正常期間,共有k個節點發生丟失數據包情況,累計丟包次數為p,若節點Nim為第m次數據包丟失節點,該節點此次共計丟失bm個數據,則電網數據采集平均丟包率PLR為:

同理,依據各電網數據采集節點參數一致,可設所有節點每跳傳輸時間一致為ttra,各節點發送一個數據包時間一致為tsend,節點緩沖區隊列長度為Li,各WR子網網關節點到主網關AP節點的時間一致為T,假設一數據包經k跳到達AP節點,結合上述電網數據采集平均丟包率PLR,被丟棄數據包進入重傳機制前所等待時間tr、重傳數據包傳輸跳數kr,則該數據包由子節點傳輸至AP節點的時間t為:

即:

3.2 仿真結果及分析

圖7 平均丟包率隨節點數據生成速率折線統計圖

圖8 平均端到端時延隨節點數據生成速率折線統計圖

4 結 語

本文所提基于改進Bellman-Ford的電網數據采集路由算法通過構建綜合決策度量值解決了傳統Bellman-Ford的電網數據采集路由算法在數據采集過程中由于數據傳輸過于集中于最短路徑,從而產生網絡瓶頸導致數據傳輸擁塞的問題,并通過時間復用與功率控制消除了傳統Bellman-Ford算法在數據采集過程中存在的“隱藏終端”與“暴露終端”現象,并通過仿真實驗結果表明:本文算法相較傳統算法其對電網數據傳輸平均丟包率、平均端到端時延數據等各項性能均有明顯優化,且本文基于改進Bellman-Ford的電網數據采集路由算法在數據流量較小情況下更為適用。