基于改進(jìn)Bellman-Ford的電網(wǎng)數(shù)據(jù)采集路由算法

田 園 馬 文 原 野 張 梅 羅施章

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

0 引 言

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

為降低上述電網(wǎng)數(shù)據(jù)的傳輸時(shí)延,常將傳統(tǒng)Bellman-Ford(又稱最短路徑樹)算法應(yīng)用至無線多跳mesh網(wǎng)絡(luò)中進(jìn)行電網(wǎng)數(shù)據(jù)采集,該算法以每條路徑傳輸跳數(shù)作為鏈路權(quán)重構(gòu)建度量值,以度量值最小作為每一拓?fù)涔?jié)點(diǎn)從其鄰居節(jié)點(diǎn)中選擇下一跳傳輸節(jié)點(diǎn)的決策指標(biāo),從而使得所采集的電網(wǎng)數(shù)據(jù)均通過跳數(shù)較少的路徑傳輸至主網(wǎng)關(guān)數(shù)據(jù)接入點(diǎn)(Access Point,AP)節(jié)點(diǎn),降低電網(wǎng)數(shù)據(jù)的傳輸時(shí)延。

傳統(tǒng)Bellman-Ford算法雖通過減少數(shù)據(jù)傳輸路徑跳數(shù)降低了電網(wǎng)數(shù)據(jù)的傳輸時(shí)延[4],但會導(dǎo)致各網(wǎng)絡(luò)節(jié)點(diǎn)為降低傳輸時(shí)延均選擇跳數(shù)較少的路徑上的節(jié)點(diǎn)作為所采集電網(wǎng)數(shù)據(jù)的下一跳傳輸節(jié)點(diǎn),從而使得數(shù)據(jù)傳輸任務(wù)過于集中在較短路徑上,易造成路徑中關(guān)鍵節(jié)點(diǎn)出現(xiàn)擁塞,形成網(wǎng)絡(luò)傳輸瓶頸,加大數(shù)據(jù)傳輸丟包率,同時(shí)會導(dǎo)致部分?jǐn)?shù)據(jù)進(jìn)入重傳機(jī)制,增加了自身的傳輸時(shí)延。

針對傳統(tǒng)Bellman-Ford算法[5]在電網(wǎng)數(shù)據(jù)采集過程中存在的上述問題,本文提出一種基于改進(jìn)Bellman-Ford的電網(wǎng)數(shù)據(jù)采集路由算法,該算法結(jié)合路徑跳數(shù)與節(jié)點(diǎn)剩余傳輸容量構(gòu)建綜合度量值,作為電網(wǎng)數(shù)據(jù)傳輸子節(jié)點(diǎn)與父節(jié)點(diǎn)選擇的決策指標(biāo),采用DSDV路由協(xié)議建立并更新各節(jié)點(diǎn)路由信息表[6],并通過時(shí)間復(fù)用與功率控制消除傳輸過程中存在的“隱藏終端”與“暴露終端”現(xiàn)象,從而平衡各節(jié)點(diǎn)數(shù)據(jù)流量以及減少數(shù)據(jù)在網(wǎng)絡(luò)中傳輸?shù)臅r(shí)間。

1 傳統(tǒng)Bellman-Ford電網(wǎng)數(shù)據(jù)采集算法

1.1 算法描述

為降低電網(wǎng)數(shù)據(jù)采集過程中的傳輸時(shí)延,保證數(shù)據(jù)傳輸?shù)臅r(shí)效性及采集效率,采用傳統(tǒng)Bellman-Ford電網(wǎng)數(shù)據(jù)采集算法進(jìn)行數(shù)據(jù)采集,該算法首先結(jié)合無線多跳mesh網(wǎng)絡(luò)結(jié)構(gòu)抽象出電網(wǎng)數(shù)據(jù)采集及傳輸過程的網(wǎng)絡(luò)模型,并通過構(gòu)建數(shù)學(xué)模型對該網(wǎng)絡(luò)模型進(jìn)行具體數(shù)據(jù)采集模擬,然后根據(jù)路徑傳輸跳數(shù)[7]構(gòu)建決策度量值開始數(shù)據(jù)流量傳輸路由過程,最后根據(jù)路由協(xié)議建立各節(jié)點(diǎn)路由信息表,并設(shè)定其更新方式,具體如下:

(1) 構(gòu)建網(wǎng)絡(luò)模型:電網(wǎng)數(shù)據(jù)采集網(wǎng)絡(luò)中至少包含一個(gè)AP主網(wǎng)關(guān)節(jié)點(diǎn)[8],以及若干個(gè)子網(wǎng)網(wǎng)關(guān)無線路由器(Wireless Router,WR)節(jié)點(diǎn)和分布各層的數(shù)據(jù)采集節(jié)點(diǎn)及傳輸子節(jié)點(diǎn),各子節(jié)點(diǎn)均具備數(shù)據(jù)采集、接收、傳輸功能,如圖1所示。

圖1 電網(wǎng)數(shù)據(jù)采集網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

圖1中網(wǎng)絡(luò)模型在電網(wǎng)數(shù)據(jù)采集過程中采取單WR網(wǎng)關(guān)結(jié)構(gòu),各數(shù)據(jù)采集子節(jié)點(diǎn)通過分層結(jié)構(gòu)分布在WR節(jié)點(diǎn)以下,各子節(jié)點(diǎn)必須通過一條傳輸路徑先將所采集電網(wǎng)數(shù)據(jù)傳輸至自身所在區(qū)域子網(wǎng)WR節(jié)點(diǎn),然后通過該WR節(jié)點(diǎn)將數(shù)據(jù)傳輸至主網(wǎng)關(guān)AP節(jié)點(diǎn),至此完成整個(gè)電網(wǎng)數(shù)據(jù)采集過程。

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

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

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

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

根據(jù)DSDV路由協(xié)議構(gòu)建源節(jié)點(diǎn)S到目的節(jié)點(diǎn)D傳輸路徑上各子節(jié)點(diǎn)路由信息表,包含如表1所示的信息表項(xiàng)。

表1 傳統(tǒng)Bellman-Ford算法路由信息表項(xiàng)

表1中目的節(jié)點(diǎn)(Dest)特指網(wǎng)絡(luò)中的WR子網(wǎng)網(wǎng)關(guān)節(jié)點(diǎn),下一跳節(jié)點(diǎn)(Next Hop)指最優(yōu)電網(wǎng)數(shù)據(jù)傳輸路徑上的各子節(jié)點(diǎn)的下一跳節(jié)點(diǎn),度量值(Metric)為源節(jié)點(diǎn)S到目的節(jié)點(diǎn)D的路徑消耗,序列號(Seq.No)代指電網(wǎng)數(shù)據(jù)信息包ID號,用于判斷路由信息是否及時(shí)更新,序列號較大電網(wǎng)數(shù)據(jù)包為最新路由信息。

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

圖2 傳統(tǒng)Bellman-Ford算法路由過程示意圖

1.2 問題描述

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

圖3 “隱藏終端”數(shù)據(jù)碰撞模型

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

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

2 改進(jìn)的Bellman-Ford電網(wǎng)數(shù)據(jù)采集路由算法

2.1 重構(gòu)決策度量值及路由信息表

由各子節(jié)點(diǎn)剩余傳輸容量A(i)以及各數(shù)據(jù)傳輸鏈路e(Ni,Nk)的最小跳數(shù)h(Ni,Nk)構(gòu)建各鏈路權(quán)重w(Ni,Nk):

故可由各鏈路權(quán)重w(Ni,Nk),構(gòu)建源節(jié)點(diǎn)S到目的節(jié)點(diǎn)D的綜合決策度量值Metric(S,D),即:

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

根據(jù)DSDV路由協(xié)議結(jié)合上述綜合決策度量值Metric(S,D)重新構(gòu)建各節(jié)點(diǎn)Ni路由向量信息表,將原本路由表中決策度量值用結(jié)合跳數(shù)與節(jié)點(diǎn)剩余傳輸容量的綜合決策度量值代替原有跳數(shù)權(quán)值,具體各信息表項(xiàng)如表2所示。

表2 經(jīng)改進(jìn)Bellman-Ford算法路由信息表項(xiàng)

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

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

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

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

圖5 周期內(nèi)發(fā)送時(shí)隙分配流程

在發(fā)送時(shí)隙中,有發(fā)送節(jié)點(diǎn)則存在數(shù)據(jù)接收節(jié)點(diǎn),當(dāng)節(jié)點(diǎn)為下一跳節(jié)點(diǎn)時(shí),則進(jìn)行數(shù)據(jù)接收,其剩余傳輸容量不足以接收數(shù)據(jù)包,則丟棄該數(shù)據(jù)包,不確認(rèn)接收成功,由其他層傳輸,若其剩余傳輸容量足以接收數(shù)據(jù)包,則與自身生成數(shù)據(jù)包進(jìn)行聚合排列,開始下一跳傳輸過程,當(dāng)節(jié)點(diǎn)不為下一跳節(jié)點(diǎn)時(shí),則等待下一個(gè)時(shí)隙接收數(shù)據(jù),具體時(shí)隙分配如圖6所示。

圖6 周期內(nèi)接收時(shí)隙分配流程

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

(1) 根據(jù)無線mesh多跳網(wǎng)絡(luò)拓?fù)錁?gòu)建電網(wǎng)數(shù)據(jù)傳輸網(wǎng)絡(luò)模型,含AP主網(wǎng)關(guān)節(jié)點(diǎn)、若干WR子網(wǎng)網(wǎng)關(guān)節(jié)點(diǎn)以及分布廣泛的數(shù)據(jù)采集子節(jié)點(diǎn),傳輸采取單WR子網(wǎng)網(wǎng)關(guān)節(jié)點(diǎn)區(qū)域傳輸模式,各子節(jié)點(diǎn)均需通過各自領(lǐng)域WR子網(wǎng)網(wǎng)關(guān)節(jié)點(diǎn)傳輸至AP節(jié)點(diǎn)。

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

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

3 算法仿真及結(jié)果分析

3.1 評價(jià)指標(biāo)

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

同理,依據(jù)各電網(wǎng)數(shù)據(jù)采集節(jié)點(diǎn)參數(shù)一致,可設(shè)所有節(jié)點(diǎn)每跳傳輸時(shí)間一致為ttra,各節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包時(shí)間一致為tsend,節(jié)點(diǎn)緩沖區(qū)隊(duì)列長度為Li,各WR子網(wǎng)網(wǎng)關(guān)節(jié)點(diǎn)到主網(wǎng)關(guān)AP節(jié)點(diǎn)的時(shí)間一致為T,假設(shè)一數(shù)據(jù)包經(jīng)k跳到達(dá)AP節(jié)點(diǎn),結(jié)合上述電網(wǎng)數(shù)據(jù)采集平均丟包率PLR,被丟棄數(shù)據(jù)包進(jìn)入重傳機(jī)制前所等待時(shí)間tr、重傳數(shù)據(jù)包傳輸跳數(shù)kr,則該數(shù)據(jù)包由子節(jié)點(diǎn)傳輸至AP節(jié)點(diǎn)的時(shí)間t為:

即:

3.2 仿真結(jié)果及分析

圖7 平均丟包率隨節(jié)點(diǎn)數(shù)據(jù)生成速率折線統(tǒng)計(jì)圖

圖8 平均端到端時(shí)延隨節(jié)點(diǎn)數(shù)據(jù)生成速率折線統(tǒng)計(jì)圖

4 結(jié) 語

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