田 园 马 文 原 野 张 梅 罗施章

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的电网数据采集路由算法在数据流量较小情况下更为适用。