基于改進(jìn)Dijkstra算法的配用電通信網(wǎng)流量調(diào)度策略

向 敏，陳 誠(chéng)

(重慶郵電大學(xué)自動(dòng)化學(xué)院，重慶400065)(*通信作者電子郵箱804652105@qq.com)

0 引言

隨著智能電網(wǎng)的發(fā)展，允許用戶(hù)積極參與到用電管理和故障報(bào)告中，以提高電網(wǎng)的自愈能力、即插即用能力和互操作性［1］。配用電通信網(wǎng)包含多層體系結(jié)構(gòu)，為了確保電網(wǎng)的安全可靠運(yùn)行，建立一個(gè)高效、可靠、安全的實(shí)時(shí)電力數(shù)據(jù)采集雙向通信系統(tǒng)將成為支撐智能電網(wǎng)快速發(fā)展的關(guān)鍵技術(shù)之一［2－3］。

有線和無(wú)線相結(jié)合是現(xiàn)有電力數(shù)據(jù)采集使用最廣泛的通信方式，由于現(xiàn)有業(yè)務(wù)量的大量增加，已無(wú)法滿(mǎn)足配用電通信網(wǎng)的發(fā)展要求［4］。無(wú)線通信技術(shù)的發(fā)展使配用電通信網(wǎng)具備了靈活、易接入、低成本等優(yōu)勢(shì)，已逐漸成為配用電網(wǎng)通信基礎(chǔ)設(shè)施的首選。為了實(shí)現(xiàn)配用電通信網(wǎng)對(duì)用戶(hù)區(qū)域無(wú)縫覆蓋，無(wú)線多跳通信具有網(wǎng)絡(luò)自組織、自愈性以及可靠性等性能，相較于單跳長(zhǎng)距離傳輸更能滿(mǎn)足智能電網(wǎng)通信需求［5－6］。

基于無(wú)線mesh網(wǎng)絡(luò)的智能電網(wǎng)數(shù)據(jù)采集網(wǎng)絡(luò)，安裝集成無(wú)線通信模塊且具有路由和一定緩存功能的中繼節(jié)點(diǎn)，可以視為一個(gè)mesh節(jié)點(diǎn)［7］。對(duì)于居民區(qū)按照一定數(shù)據(jù)采集規(guī)模分為多個(gè)子網(wǎng)區(qū)域，每個(gè)子網(wǎng)區(qū)域存在一個(gè)子網(wǎng)網(wǎng)關(guān)，最后所有數(shù)據(jù)匯聚到主網(wǎng)關(guān)并與遠(yuǎn)程數(shù)據(jù)管理中心通信。該網(wǎng)絡(luò)架構(gòu)下不僅要考慮物理層、多路訪問(wèn)控制(Multi-Access Protocol，MAC)協(xié)議等滿(mǎn)足智能電網(wǎng)通信網(wǎng)絡(luò)需求，還應(yīng)考慮應(yīng)用層時(shí)變的數(shù)據(jù)流量對(duì)網(wǎng)絡(luò)性能的影響［4］。例如，電力故障情況下，大量故障信息的產(chǎn)生和傳輸導(dǎo)致網(wǎng)絡(luò)數(shù)據(jù)流量負(fù)載迅速增大，這樣就可能造成某些中繼節(jié)點(diǎn)數(shù)據(jù)量增大，極有可能產(chǎn)生擁塞，導(dǎo)致網(wǎng)絡(luò)吞吐量下降，影響數(shù)據(jù)通信的實(shí)時(shí)性和可靠性。

由于智能電網(wǎng)的數(shù)據(jù)均與電網(wǎng)業(yè)務(wù)相關(guān)，是電網(wǎng)決策和數(shù)據(jù)分析的基礎(chǔ)，因而智能電網(wǎng)通信網(wǎng)需要具有良好的實(shí)時(shí)性、準(zhǔn)確性和可靠性。文獻(xiàn)［7］對(duì)多網(wǎng)關(guān)聯(lián)合網(wǎng)絡(luò)進(jìn)行了分析，以節(jié)點(diǎn)隊(duì)列長(zhǎng)度為主要指標(biāo)，采用隊(duì)列加權(quán)的方法提出了流量調(diào)度算法。文獻(xiàn)［8］提出了一種多網(wǎng)關(guān)mesh結(jié)構(gòu)，將多個(gè)局域mesh子網(wǎng)聯(lián)合成為一個(gè)有主網(wǎng)關(guān)進(jìn)行管理的多網(wǎng)關(guān)網(wǎng)絡(luò)，任意智能電表既是數(shù)據(jù)源節(jié)點(diǎn)也是中繼節(jié)點(diǎn)，且所有電表可以向任一子網(wǎng)關(guān)傳輸數(shù)據(jù)。文獻(xiàn)［9］提出了用于智能電網(wǎng)認(rèn)知無(wú)線電通信基礎(chǔ)設(shè)施基于優(yōu)先級(jí)的流量調(diào)度方法，考慮了智能電網(wǎng)業(yè)務(wù)流量的異構(gòu)性，將數(shù)據(jù)流量分為了三個(gè)優(yōu)先類(lèi)別。文獻(xiàn)［10］分析了傳統(tǒng)背壓算法在數(shù)據(jù)流量負(fù)載較大的情況下不能有效減少端到端時(shí)延的缺點(diǎn)，提出與最短路徑相結(jié)合的背壓算法，通過(guò)最小化源節(jié)點(diǎn)和目的節(jié)點(diǎn)的間路徑長(zhǎng)度以減少時(shí)延。文獻(xiàn)［11］綜合考慮跳數(shù)和mesh節(jié)點(diǎn)隊(duì)列長(zhǎng)度，提出了多網(wǎng)關(guān)單級(jí)背壓調(diào)度算法。文獻(xiàn)［12］提出了隨機(jī)切換流量調(diào)度算法，以緩解緊急狀況數(shù)據(jù)流量增大時(shí)某些處于關(guān)鍵位置智能電表的數(shù)據(jù)擁塞。文獻(xiàn)［13］提出了一種貪婪背壓路由算法，通過(guò)節(jié)點(diǎn)到達(dá)最近網(wǎng)關(guān)的跳數(shù)和流量負(fù)載計(jì)算獲得貪婪背壓度量值，根據(jù)最陡梯度方向路由數(shù)據(jù)包。文獻(xiàn)［14］提出一種確定性路由和機(jī)會(huì)性路由相結(jié)合的路由協(xié)議，各節(jié)點(diǎn)從其鄰居節(jié)點(diǎn)中選擇出候選節(jié)點(diǎn)集傳輸數(shù)據(jù)，以避免瓶頸節(jié)點(diǎn)的產(chǎn)生。

隨著智能電網(wǎng)業(yè)務(wù)的不斷增加，配用電通信網(wǎng)數(shù)據(jù)采集網(wǎng)絡(luò)將面臨極大的數(shù)據(jù)流量壓力，為緩解智能電網(wǎng)數(shù)據(jù)流量突增造成擁塞并均衡網(wǎng)絡(luò)流量分布，本文提出一種基于改進(jìn)Dijkstra的路由算法——DDTA(Data-balance and improved Dijkstra Traffic-scheduling Algorithm)，以跳數(shù)、流量負(fù)載率和鏈路利用率作為路徑選擇的綜合指標(biāo)，優(yōu)化配用電通信網(wǎng)絡(luò)中的下一跳節(jié)點(diǎn)選擇。構(gòu)建業(yè)務(wù)調(diào)度模型，對(duì)重度擁塞節(jié)點(diǎn)進(jìn)行業(yè)務(wù)調(diào)度，以保證高優(yōu)先級(jí)業(yè)務(wù)的服務(wù)質(zhì)量。

1 配用電通信網(wǎng)絡(luò)流量調(diào)度模型

考慮到對(duì)用戶(hù)區(qū)域的無(wú)縫覆蓋，基于無(wú)線多跳網(wǎng)絡(luò)的配用電數(shù)據(jù)采集網(wǎng)絡(luò)能夠有效提高用戶(hù)電力數(shù)據(jù)采集和傳輸?shù)膶?shí)時(shí)性、完整性和可靠性。每個(gè)鄰域網(wǎng)(Neighborhood Area Network，NAN)由多個(gè)mesh子網(wǎng)組成，每個(gè)mesh節(jié)點(diǎn)表示每個(gè)子網(wǎng)中可以接入本地網(wǎng)關(guān)的數(shù)據(jù)采集點(diǎn)。數(shù)據(jù)聚合點(diǎn)即為通過(guò)有線或無(wú)線鏈路與主網(wǎng)關(guān)進(jìn)行通信的子網(wǎng)關(guān)。為了簡(jiǎn)化配用電通信網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)鋱D以及便于節(jié)點(diǎn)管理，依據(jù)源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的最少跳數(shù)對(duì)節(jié)點(diǎn)進(jìn)行分層。由于越靠近網(wǎng)關(guān)的節(jié)點(diǎn)其負(fù)載越重，根據(jù)節(jié)點(diǎn)當(dāng)前狀態(tài)劃分節(jié)點(diǎn)擁塞程度，對(duì)于重度擁塞節(jié)點(diǎn)進(jìn)行業(yè)務(wù)調(diào)度盡可能避免高優(yōu)先級(jí)業(yè)務(wù)的丟失。

1.1 配用電數(shù)據(jù)采集網(wǎng)絡(luò)節(jié)點(diǎn)分層模型

采用有向圖模型G(N，L)來(lái)表示整個(gè)配用電通信網(wǎng)的網(wǎng)絡(luò)拓?fù)?，N表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)集，L則表示網(wǎng)絡(luò)中節(jié)點(diǎn)間鏈路集合。lij表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的有向邊，由于網(wǎng)絡(luò)中的鏈路均可雙向傳輸數(shù)據(jù)，則lij∈L，lji∈L。eij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的有向鏈路邊權(quán)值。設(shè)定最大跳數(shù)閾值為H，則可將所有數(shù)據(jù)采集節(jié)點(diǎn)分為H層，以到達(dá)網(wǎng)關(guān)的最少跳數(shù)對(duì)mesh子網(wǎng)中的數(shù)據(jù)采集節(jié)點(diǎn)進(jìn)行分層。

以圖1中mesh網(wǎng)絡(luò)為例，將配用電數(shù)據(jù)采集網(wǎng)絡(luò)中與主網(wǎng)關(guān)直接通信的子網(wǎng)關(guān)0作為第0層節(jié)點(diǎn);只需單跳便可把數(shù)據(jù)傳輸?shù)骄W(wǎng)關(guān)的節(jié)點(diǎn)1、2、3和4作為第1層節(jié)點(diǎn);到達(dá)網(wǎng)關(guān)最少跳數(shù)為2的節(jié)點(diǎn)5、6和7作為第2層節(jié)點(diǎn);到達(dá)網(wǎng)關(guān)最少跳數(shù)為3的節(jié)點(diǎn)8作為第3層節(jié)點(diǎn)。

圖1 數(shù)據(jù)采集網(wǎng)絡(luò)節(jié)點(diǎn)分層結(jié)構(gòu)Fig.1 Node hierarchical structure for data acquisition network

1.2 配用電通信網(wǎng)業(yè)務(wù)調(diào)度模型

配用電通信業(yè)務(wù)的QoS需求主要包含時(shí)延、丟包率和數(shù)據(jù)速率等指標(biāo)。參照《電力系統(tǒng)通信設(shè)計(jì)技術(shù)規(guī)定》將智能電網(wǎng)通信業(yè)務(wù)分為3類(lèi)，分別用P1、P2、和P3標(biāo)識(shí)業(yè)務(wù)等級(jí);P1表示智能電網(wǎng)用于控制、保護(hù)和管理的緊急型業(yè)務(wù)，如縱聯(lián)網(wǎng)絡(luò)保護(hù);P2表示智能電網(wǎng)中對(duì)實(shí)時(shí)性要求較高的關(guān)鍵型業(yè)務(wù)，如高級(jí)量測(cè)體系(Advanced Metering Infrastructure，AMI);P3表示智能電網(wǎng)中允許一定時(shí)延的常規(guī)型業(yè)務(wù)，如用電信息采集。等級(jí)標(biāo)識(shí)越低業(yè)務(wù)優(yōu)先級(jí)越高。三類(lèi)配用電業(yè)務(wù)特性如表1所示。

表1 三類(lèi)配用電業(yè)務(wù)特性Tab.1 Characteristics of three types of power distribution and utilization service

本文通過(guò)預(yù)先設(shè)置數(shù)據(jù)包IP報(bào)文中差分服務(wù)代碼點(diǎn)(Differentiated Service Code Point，DSCP)值以辨識(shí)所劃分的業(yè)務(wù)類(lèi)型以及優(yōu)先級(jí)，IP包頭中區(qū)分服務(wù)字段中的TOS字段中DSCP值設(shè)置如表2所示，DSCP值的前四位表示配用電業(yè)務(wù)的優(yōu)先等級(jí)，后四位用以表示配電點(diǎn)業(yè)務(wù)類(lèi)別。

表2 DSCP值的二進(jìn)制編碼Tab.2 Binary encoding for DSCP

設(shè)節(jié)點(diǎn)i中的緩存隊(duì)列長(zhǎng)度為Qi，節(jié)點(diǎn)i數(shù)據(jù)到達(dá)率為vi，節(jié)點(diǎn)i數(shù)據(jù)生成數(shù)據(jù)為v0i，數(shù)據(jù)轉(zhuǎn)發(fā)率為ui，一個(gè)數(shù)據(jù)處理周期為T(mén)，節(jié)點(diǎn)緩沖區(qū)擁塞閾值為QT;則當(dāng)前時(shí)刻節(jié)點(diǎn)中緩存隊(duì)列長(zhǎng)度為:

依據(jù)節(jié)點(diǎn)數(shù)據(jù)處理能力和緩存隊(duì)列長(zhǎng)度將節(jié)點(diǎn)擁塞度劃分為3個(gè)等級(jí)，節(jié)點(diǎn)擁塞度等級(jí)劃分規(guī)則如下:

1)若ui≥(vi+)，隨時(shí)間增加節(jié)點(diǎn)緩存隊(duì)列中數(shù)據(jù)包數(shù)量會(huì)逐漸減少，節(jié)點(diǎn)i不易發(fā)生擁塞，其擁塞等級(jí)為Ⅲ。

2)若ui＜(vi+)且Qi(t)＜QT，隨時(shí)間增加節(jié)點(diǎn)緩存隊(duì)列中數(shù)據(jù)量可能增大至擁塞閾值，節(jié)點(diǎn)i可能發(fā)生擁塞，其擁塞等級(jí)為Ⅱ。

3)若ui＜(vi+)且Qi(t)≥QT，隨時(shí)間增加節(jié)點(diǎn)緩存隊(duì)列中數(shù)據(jù)量可能溢出緩存區(qū)，節(jié)點(diǎn)i極易產(chǎn)生擁塞，其擁塞等級(jí)為Ⅰ。

節(jié)點(diǎn)擁塞等級(jí)標(biāo)識(shí)越低則節(jié)點(diǎn)發(fā)生擁塞的可能性越大。

若節(jié)點(diǎn)為擁塞等級(jí)為Ⅰ或Ⅱ時(shí)，則對(duì)該節(jié)點(diǎn)緩存區(qū)中的數(shù)據(jù)包按照業(yè)務(wù)優(yōu)先級(jí)進(jìn)行調(diào)度，盡可能減少緊急型業(yè)務(wù)的丟包率。假設(shè)t時(shí)刻擁塞節(jié)點(diǎn)i緩存隊(duì)列中有6個(gè)(S1，S2，…，S6)不同優(yōu)先級(jí)的數(shù)據(jù)包，按照如圖2所示的方法對(duì)該節(jié)點(diǎn)中的數(shù)據(jù)進(jìn)行調(diào)度。

圖2 擁塞節(jié)點(diǎn)緩存隊(duì)列調(diào)度過(guò)程Fig.2 Scheduling process for cache queue of congestion nodes

對(duì)易產(chǎn)生擁塞節(jié)點(diǎn)中的數(shù)據(jù)緩存隊(duì)列按照業(yè)務(wù)優(yōu)先級(jí)進(jìn)行調(diào)度之后，從隊(duì)尾丟棄優(yōu)先級(jí)較低的業(yè)務(wù)，并發(fā)送消息通知被丟棄業(yè)務(wù)的源節(jié)點(diǎn)重新進(jìn)行路由選擇。同時(shí)對(duì)擁塞節(jié)點(diǎn)的上一跳節(jié)點(diǎn)重新進(jìn)行路由選擇，以避免數(shù)據(jù)的繼續(xù)丟失。由于重新路由選擇要避開(kāi)負(fù)載較重的節(jié)點(diǎn)并選擇出最優(yōu)路徑，本文利用鏈路跳數(shù)、流量負(fù)載率和鏈路利用率求取復(fù)合邊權(quán)值，利用改進(jìn)的Dijkstra算法獲得最優(yōu)路徑。

2 基于復(fù)合邊權(quán)值的流量調(diào)度算法

在智能電網(wǎng)通信網(wǎng)絡(luò)中業(yè)務(wù)流量從終端采集設(shè)備逐漸集中至網(wǎng)關(guān)，越靠近網(wǎng)關(guān)的節(jié)點(diǎn)其業(yè)務(wù)量越大越容易造成數(shù)據(jù)丟失，為避免擁塞節(jié)點(diǎn)的產(chǎn)生并提升網(wǎng)絡(luò)性能，對(duì)于分層網(wǎng)絡(luò)拓?fù)鋱D邊值計(jì)算引入三個(gè)度量值:跳數(shù)指標(biāo)、流量負(fù)載率指標(biāo)和鏈路利用率指標(biāo)，綜合考慮下一跳路徑的選擇。

2.1 跳數(shù)

網(wǎng)絡(luò)中的節(jié)點(diǎn)定期與其周?chē)泥従庸?jié)點(diǎn)交換信息，設(shè)節(jié)點(diǎn)i到達(dá)距其最近的網(wǎng)關(guān)的最少跳數(shù)為。為了簡(jiǎn)化智能電網(wǎng)數(shù)據(jù)采集網(wǎng)絡(luò)模型，規(guī)定任意節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)列表中只包含上層和同層鄰居節(jié)點(diǎn)，即節(jié)點(diǎn)i只能從(－1)層和Hi層的鄰居節(jié)點(diǎn)中選擇下一跳節(jié)點(diǎn);且第一層節(jié)點(diǎn)只能選min擇網(wǎng)關(guān)作為下一跳節(jié)點(diǎn)。本文還利用跳數(shù)來(lái)間接表示節(jié)點(diǎn)間的距離。在此將節(jié)點(diǎn)i和節(jié)點(diǎn)j到達(dá)距其最近目的網(wǎng)關(guān)的最少跳數(shù)之差作為跳數(shù)指標(biāo)，如式(2)所示:

2.2 流量負(fù)載率

根據(jù)文獻(xiàn)［15］利用梯度模擬節(jié)點(diǎn)緩存隊(duì)列，節(jié)點(diǎn)按照最陡梯度感知節(jié)點(diǎn)中的數(shù)據(jù)流量分布，從而在數(shù)據(jù)傳輸過(guò)程中規(guī)避擁塞節(jié)點(diǎn)。本文定義節(jié)點(diǎn)i到節(jié)點(diǎn)j的有向鏈路lij的流量度量為 (lij)，令Qij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的隊(duì)列長(zhǎng)度，Mi為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)數(shù)，且M=max(Mi)。節(jié)點(diǎn)i到節(jié)點(diǎn)j鏈路lij的流量負(fù)載度量如式(3)所示:

式中:NB(j)為節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)集合;w為j的鄰居節(jié)點(diǎn)即w∈NB(j)。節(jié)點(diǎn)i的流量負(fù)載度量如式(4)所示:

式中:max和min分別表示節(jié)點(diǎn)i的輸出鏈路中流量度量值的最大值和最小值。節(jié)點(diǎn)i向j傳輸數(shù)據(jù)的歸一化流量負(fù)載率如(5)所示:

式中:Cij表示鏈路代價(jià)度量值。TM越大則表示節(jié)點(diǎn)i與其鄰居節(jié)點(diǎn)鏈路lij之間流量負(fù)載值差異越大，節(jié)點(diǎn)i向節(jié)點(diǎn)j傳輸數(shù)據(jù)的趨勢(shì)越明顯。

2.3 鏈路利用率

文獻(xiàn)［16］定義鏈路的使用率為鏈路上業(yè)務(wù)流總速率和鏈路的有效傳輸速率的比值。本文采用鏈路上業(yè)務(wù)流總速率與網(wǎng)絡(luò)傳輸速率的比值作為鏈路度量值。GW為網(wǎng)關(guān)集合，P為各業(yè)務(wù)流到達(dá)網(wǎng)關(guān)的路徑集合，F(xiàn)為業(yè)務(wù)流集合，業(yè)務(wù)流f在路徑p上的速率為，則業(yè)務(wù)流f的總速率為x(lij，p)=1 表示鏈路 lij在路徑 p上，否則 x(lij，p)=0。經(jīng)過(guò)鏈路lij的業(yè)務(wù)流總速率為路lij的鏈路度量值，即為鏈路利用率，如式(6)所示:

式中v即為網(wǎng)絡(luò)數(shù)據(jù)傳輸速率。

2.4 復(fù)合邊權(quán)值

有向圖模型G(N，L)中的邊權(quán)值綜合考慮了跳數(shù)、流量負(fù)載率和鏈路利用率，定義網(wǎng)絡(luò)拓?fù)鋱D中節(jié)點(diǎn)i到節(jié)點(diǎn)j的有向邊權(quán)值為eij，如式(7)所示。

式中α、β和γ分別為跳數(shù)、流量負(fù)載率和鏈路利用率指標(biāo)的加權(quán)系數(shù)，取值范圍為［0，1］，且 α + β + γ =1。加權(quán)系數(shù) α、β和γ可以依據(jù)文獻(xiàn)［18］中的多業(yè)務(wù)權(quán)值分配方法，依據(jù)配用電緊急型、關(guān)鍵型和常規(guī)型三類(lèi)業(yè)務(wù)需求偏好求取權(quán)值。

3 算法描述

本文結(jié)合最少跳數(shù)構(gòu)建節(jié)點(diǎn)分層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與Dijkstra算法［17］，利用跳數(shù)、流量負(fù)載率和鏈路利用率綜合求取越大越優(yōu)有向邊權(quán)值，求取所有邊權(quán)值最大的鏈路相鄰的節(jié)點(diǎn)即為下一跳優(yōu)先節(jié)點(diǎn)。最壞情況下需要遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn)以選取最優(yōu)路徑，此時(shí)算法的時(shí)間復(fù)雜度為O(n2)。算法具體步驟如下:

步驟1 網(wǎng)關(guān)收集更新網(wǎng)絡(luò)中所有節(jié)點(diǎn)的信息，并依據(jù)源節(jié)點(diǎn)到達(dá)距網(wǎng)關(guān)的最少跳數(shù)構(gòu)建最短路徑節(jié)點(diǎn)分層模型，刪除信號(hào)強(qiáng)度小于閾值的鄰居節(jié)點(diǎn)。

步驟2 初始時(shí)刻t，各節(jié)點(diǎn)交換狀態(tài)信息，維護(hù)各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)信息表。對(duì)于Ⅰ級(jí)擁塞節(jié)點(diǎn)斷開(kāi)該節(jié)點(diǎn)的所有輸入鏈路，并在(t－T)時(shí)刻向該節(jié)點(diǎn)傳輸數(shù)據(jù)的所有鄰居節(jié)點(diǎn)列表中刪除該擁塞節(jié)點(diǎn);對(duì)于Ⅱ級(jí)擁塞節(jié)點(diǎn)則斷開(kāi)同層節(jié)點(diǎn)的輸入鏈路，并在(t－T)時(shí)刻向該節(jié)點(diǎn)傳輸數(shù)據(jù)的同層鄰居節(jié)點(diǎn)列表中刪除該中度擁塞節(jié)點(diǎn)。T為一個(gè)數(shù)據(jù)處理周期。

步驟3 依據(jù)本節(jié)點(diǎn)信息和獲取的鄰居節(jié)點(diǎn)信息計(jì)算有向邊復(fù)合權(quán)值，并構(gòu)建鏈路邊權(quán)值矩陣Eij，其中的元素eij表示節(jié)點(diǎn)i指向節(jié)點(diǎn)j鏈路邊權(quán)值，若節(jié)點(diǎn)i與j沒(méi)有直接相鄰，則eij=0。

步驟4 使用Dijkstra算法求取從源節(jié)點(diǎn)到達(dá)目的網(wǎng)關(guān)邊權(quán)值之和最大的路徑。

步驟5 網(wǎng)絡(luò)因突發(fā)狀況產(chǎn)生鏈路中斷時(shí)，則在數(shù)據(jù)源節(jié)點(diǎn)與鄰居節(jié)點(diǎn)重新交換信息并更新鄰居節(jié)點(diǎn)列表，重新調(diào)用Dijkstra算法求取新的路徑。

4 仿真結(jié)論與分析

采用Matlab對(duì)本文算法DDTA進(jìn)行仿真測(cè)試，為驗(yàn)證算法優(yōu)越性，在相同條件下與最短路徑(Shortest Path Fast，SPF)算法、貪婪背壓算法(Greedy Backpressure Routing Algorithm，GBRA)的丟包率、端到端平均時(shí)延和網(wǎng)絡(luò)吞吐量進(jìn)行對(duì)比。

本章采用1個(gè)局域網(wǎng)關(guān)及36個(gè)隨機(jī)分布的數(shù)據(jù)采集節(jié)點(diǎn)構(gòu)建多網(wǎng)關(guān)多跳數(shù)據(jù)采集網(wǎng)絡(luò)。仿真過(guò)程中，所有節(jié)點(diǎn)數(shù)據(jù)生成速率相同，假設(shè)網(wǎng)關(guān)不限帶寬。其中α、β和γ的取值參照文獻(xiàn)［18］的權(quán)值求取方法，并經(jīng)過(guò)多次仿真獲取最優(yōu)取值，該系數(shù)可以依據(jù)業(yè)務(wù)需求和網(wǎng)絡(luò)狀態(tài)進(jìn)行相應(yīng)調(diào)整。依據(jù)配用電通信網(wǎng)實(shí)際運(yùn)行過(guò)程中配用電業(yè)務(wù)的數(shù)量設(shè)置緊急型、關(guān)鍵型和常規(guī)型業(yè)務(wù)生成比率。網(wǎng)絡(luò)仿真環(huán)境的相關(guān)參數(shù)設(shè)置如表3所示。

表3 網(wǎng)絡(luò)仿真環(huán)境參數(shù)Tab.3 Network simulation environment parameters

4.1 平均端到端時(shí)延

端到端的時(shí)延主要分為傳輸時(shí)延和等待時(shí)延，傳輸主要與跳數(shù)相關(guān)，而等待時(shí)延即為業(yè)務(wù)流在傳輸路徑中排隊(duì)等待時(shí)間。假設(shè)節(jié)點(diǎn)的數(shù)據(jù)流f到達(dá)網(wǎng)關(guān)所經(jīng)過(guò)的跳數(shù)為h，單跳傳輸時(shí)延為th，節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包的時(shí)延tp，則業(yè)務(wù)流的端到端時(shí)延如下:

對(duì)仿真區(qū)域內(nèi)的所有節(jié)點(diǎn)進(jìn)行時(shí)延性能仿真，仿真結(jié)果如圖3所示，圖3中本文算法端到端時(shí)延為三類(lèi)業(yè)務(wù)從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的平均時(shí)延。當(dāng)節(jié)點(diǎn)數(shù)據(jù)生成速率較小時(shí)，本文算法DDTA與GBRA平均端到端時(shí)延相當(dāng);隨著節(jié)點(diǎn)數(shù)據(jù)生成速率增大，節(jié)點(diǎn)緩存隊(duì)列長(zhǎng)度增加使得平均端到端時(shí)延增大。本文所提算法路由選擇綜合考慮了跳數(shù)和節(jié)點(diǎn)數(shù)據(jù)流量負(fù)載，在一定程度上規(guī)避了向擁塞節(jié)點(diǎn)傳輸數(shù)據(jù)，從而減少了傳輸時(shí)延和等待時(shí)延。隨節(jié)點(diǎn)數(shù)據(jù)生成速率增大，本文所提算法平均端到端時(shí)延小于GBRA和SPF，提高了配用電通信網(wǎng)絡(luò)業(yè)務(wù)傳輸?shù)目煽啃浴?/p>

圖3 不同算法平均端到端時(shí)延對(duì)比Fig.3 Comparison of average end-to-end delay of different algorithms

本文算法仿真環(huán)境下，緊急型業(yè)務(wù)、關(guān)鍵型業(yè)務(wù)和常規(guī)型業(yè)務(wù)的平均端到端時(shí)延對(duì)比如圖4所示。由圖4中可以看出，由于所提算法在擁塞節(jié)點(diǎn)處優(yōu)先傳輸緊急型和關(guān)鍵型業(yè)務(wù)，從而減少了這兩類(lèi)業(yè)務(wù)數(shù)據(jù)包的排隊(duì)時(shí)延，因而傳輸緊急型和關(guān)鍵型業(yè)務(wù)的平均端到端時(shí)延小于常規(guī)型業(yè)務(wù)。隨著節(jié)點(diǎn)數(shù)據(jù)生成速率增大，易擁塞節(jié)點(diǎn)優(yōu)先保障緊急型業(yè)務(wù)的傳輸，其次才是關(guān)鍵型，因而緊急型業(yè)務(wù)的端到端時(shí)延低于關(guān)鍵型。本文的流量調(diào)度策略通過(guò)對(duì)易擁塞節(jié)點(diǎn)進(jìn)行業(yè)務(wù)調(diào)度，保證了配用電通信網(wǎng)中重要業(yè)務(wù)的時(shí)延特性。

圖4 不同業(yè)務(wù)平均端到端時(shí)延對(duì)比Fig.4 Comparison of average end-to-end delay of different services

4.2 丟包率

緊急型、關(guān)鍵型和常規(guī)型三類(lèi)配用電業(yè)務(wù)在本文算法DDTA、最短路徑(SPF)算法和貪婪背壓算法(GBRA)下丟包率仿真結(jié)果如圖5所示。

數(shù)據(jù)生成速率對(duì)緊急型業(yè)務(wù)數(shù)據(jù)包丟失率的影響，仿真結(jié)果如圖5(a)所示。從圖5(a)可知，本文所提算法的緊急型業(yè)務(wù)數(shù)據(jù)包丟失率低于SPF和GBRA。具體而言，在數(shù)據(jù)生成率為80 kb/s時(shí)，本文所提算法的緊急型業(yè)務(wù)丟包率相比SPF和GBRA分別減少了81.3%和67.7%。由于本文研究對(duì)擁塞節(jié)點(diǎn)進(jìn)行了業(yè)務(wù)調(diào)度以保證緊急型業(yè)務(wù)優(yōu)先傳輸，因而隨數(shù)據(jù)生成速率的提高本文所提算法中緊急型業(yè)務(wù)丟包率較小且增長(zhǎng)較緩慢。

圖5(b)為三種算法關(guān)鍵型業(yè)務(wù)丟包率仿真結(jié)果。從圖5(b)中可知，本文所提算法的關(guān)鍵型業(yè)務(wù)丟包率低于SPF和GBRA。當(dāng)節(jié)點(diǎn)數(shù)據(jù)生成速率為80 kb/s時(shí)，本文算法較SPF和GBRA關(guān)鍵型業(yè)務(wù)丟包率分別減少了79%和63.8%。本文算法在易擁塞節(jié)點(diǎn)處優(yōu)先保證緊急型業(yè)務(wù)的傳輸，次之保證關(guān)鍵型業(yè)務(wù)的傳輸，因而隨著節(jié)點(diǎn)數(shù)據(jù)生成速率逐漸提高本文所提算法中關(guān)鍵型業(yè)務(wù)丟包率增長(zhǎng)較其他兩種算法慢。

圖5(c)為三種算法常規(guī)型業(yè)務(wù)丟包率仿真結(jié)果。從圖5(c)中可以看出，本文算法常規(guī)型業(yè)務(wù)丟包率和GBRA相當(dāng)，低于SPF，這是因?yàn)楸疚乃崴惴ǔＲ?guī)型業(yè)務(wù)優(yōu)先級(jí)最低，在易擁塞節(jié)點(diǎn)處以犧牲常規(guī)業(yè)務(wù)而減少緊急型和關(guān)鍵型業(yè)務(wù)丟包可能性。

圖5 不同業(yè)務(wù)丟包率對(duì)比Fig.5 Comparison of packet loss rate of different services

4.3 網(wǎng)絡(luò)吞吐量

網(wǎng)絡(luò)的有效吞吐量為單位時(shí)間內(nèi)目的網(wǎng)關(guān)接收的數(shù)據(jù)量與網(wǎng)絡(luò)中所有節(jié)點(diǎn)數(shù)據(jù)生成量的比值。圖6分析了網(wǎng)絡(luò)中目的網(wǎng)關(guān)有效吞吐量和節(jié)點(diǎn)數(shù)據(jù)生成速率的關(guān)系。隨著數(shù)據(jù)生成速率的增大網(wǎng)絡(luò)逐漸趨于飽和，更多的數(shù)據(jù)滯留在節(jié)點(diǎn)緩存隊(duì)列中或者丟失，使得網(wǎng)絡(luò)的有效吞吐量隨著數(shù)據(jù)生成速率增大而逐漸降低。由于本文所提算法綜合考慮了鏈路負(fù)載和鏈路利用率，因而均衡了配用電通信網(wǎng)絡(luò)的流量分布，并提高了網(wǎng)絡(luò)利用率。

圖6 不同算法有效吞吐量對(duì)比Fig.6 Comparison of effective throughput of different algorithms

5 結(jié)語(yǔ)

針對(duì)智能電網(wǎng)通信網(wǎng)絡(luò)數(shù)據(jù)采集匯聚過(guò)程中，因網(wǎng)絡(luò)中業(yè)務(wù)流量分布不均勻造成某些關(guān)鍵節(jié)點(diǎn)易產(chǎn)生擁塞的問(wèn)題，本文提出了一種基于復(fù)合邊權(quán)值的負(fù)載均衡的Dijkstra路由算法。依據(jù)節(jié)點(diǎn)當(dāng)前狀態(tài)劃分節(jié)點(diǎn)擁塞等級(jí)，對(duì)于中度擁塞節(jié)點(diǎn)進(jìn)行業(yè)務(wù)調(diào)度以保證緊急業(yè)務(wù)優(yōu)先傳輸。綜合考慮鏈路跳數(shù)、流量負(fù)載率和鏈路利用率求取復(fù)合邊權(quán)值，利用改進(jìn)的Dijkstra算法求取最優(yōu)路徑。仿真結(jié)果表明本文所提算法在節(jié)點(diǎn)數(shù)據(jù)速率增大的情況下能有效降低網(wǎng)絡(luò)端到端平均時(shí)延和丟包率，提高網(wǎng)絡(luò)吞吐量，改善了電力通信網(wǎng)數(shù)據(jù)采集網(wǎng)絡(luò)的通信性能。本文仿真是在簡(jiǎn)化的理想模型中進(jìn)行仿真，下一步將結(jié)合實(shí)際的配用電通信網(wǎng)數(shù)據(jù)進(jìn)行仿真，測(cè)試并完善算法。