基于改进Bellman-Ford的电网数据采集路由算法.pdf

第 卷第 期计算机应用与软件 年 月 基于改进 的电网数据采集路由算法田园马文原野张梅罗施章（云南电网有限责任公司信息中心云南 昆明 ）（昆明能讯科技有限责任公司云南 昆明 ）收稿日期：。云南电网有限责任公司信息中心研发基金项目（）。田园，硕士，主研领域：电网信息化。马文，学士。原野，硕士。张梅，硕士。罗施章，硕士生。摘要为解决传统 算法在电网数据采集过程中因数据传输过于集中在各子网网关节点附近的关键节点，从而导致数据传输时延以及丢包率较高的问题，提出一种基于改进 的电网数据采集路由算法。该算法在传统 算法的基础上，结合节点剩余传输容量对上层父节点与下层子节点的选择进行决策，降低数据传输跳数的同时也避免出现因数据传输拥塞从而影响电网数据传输可靠性及吞吐量的现象。实验结果表明，该算法相较传统 算法其数据传输时延及丢包率均有所降低。关键词 数据采集剩余传输容量传输跳数中图分类号 文献标志码 ：（，）（，），引言随着工农业、城镇生活等各领域用电需求量急剧上升，智能电网 中用户业务数据总量增加，数据传输规模加大，因此需对智能电网的数据采集 过程进行优化改进，以满足数据采集过程中对整个电网数据传输吞吐量、数据传输稳定性及可靠性、数据传输效率及时效性等方面的需求，为降低电网建设成本，提升其灵活性及抗干扰能力，常采用 结构进行电网数据采集，而使用该多跳结构会导致数据传输距离较长、所采集数据的传输延时较高，从而无法保证电网数据传输 的时效性。为降低上述电网数据的传输时延，常将传统 计算机应用与软件 年 （又称最短路径树）算法应用至无线多跳 网络中进行电网数据采集，该算法以每条路径传输跳数作为链路权重构建度量值，以度量值最小作为每一拓扑节点从其邻居节点中选择下一跳传输节点的决策指标，从而使得所采集的电网数据均通过跳数较少的路径传输至主网关数据接入点（，）节点，降低电网数据的传输时延。传统 算法虽通过减少数据传输路径跳数降低了电网数据的传输时延 ，但会导致各网络节点为降低传输时延均选择跳数较少的路径上的节点作为所采集电网数据的下一跳传输节点，从而使得数据传输任务过于集中在较短路径上，易造成路径中关键节点出现拥塞，形成网络传输瓶颈，加大数据传输丢包率，同时会导致部分数据进入重传机制，增加了自身的传输时延。针对传统 算法 在电网数据采集过程中存在的上述问题，本文提出一种基于改进 的电网数据采集路由算法，该算法结合路径跳数与节点剩余传输容量构建综合度量值，作为电网数据传输子节点与父节点选择的决策指标，采用 路由协议建立并更新各节点路由信息表 ，并通过时间复用与功率控制消除传输过程中存在的“隐藏终端”与“暴露终端”现象，从而平衡各节点数据流量以及减少数据在网络中传输的时间。传统 电网数据采集算法 算法描述为降低电网数据采集过程中的传输时延，保证数据传输的时效性及采集效率，采用传统 电网数据采集算法进行数据采集，该算法首先结合无线多跳 网络结构抽象出电网数据采集及传输过程的网络模型，并通过构建数学模型对该网络模型进行具体数据采集模拟，然后根据路径传输跳数 构建决策度量值开始数据流量传输路由过程，最后根据路由协议建立各节点路由信息表，并设定其更新方式，具体如下：（）构建网络模型：电网数据采集网络中至少包含一个 主网关节点 ，以及若干个子网网关无线路由器（，）节点和分布各层的数据采集节点及传输子节点，各子节点均具备数据采集、接收、传输功能，如图 所示。图 电网数据采集网络拓扑结构图 中网络模型在电网数据采集过程中采取单网关结构，各数据采集子节点通过分层结构分布在 节点以下，各子节点必须通过一条传输路径先将所采集电网数据传输至自身所在区域子网 节点，然后通过该 节点将数据传输至主网关 节点，至此完成整个电网数据采集过程。（）构建数学模型：假设电网数据采集网络中某单 采集网络中包含 个子节点，表述为（，），其邻居节点为 ，网络中各链路表示为（，），为子网网关 节点，为所有数据采集点集合，即 ，（）为节点到子网网关的最短路径 传输跳数，若令 （）的最大值为 ，即 （），则 可代表单 采集网络中数据采集点数，则：（），其中 （）。根据节点 的邻居节点 位置与其是否位于同层，可将其邻居节点分为三类 （）、（）、，即：（）（）（）（）式中：（）（）；（）表示位于节点 的上一层；（）位于节点 的同一层；（）位于节点的下一层。故节点 可表示为 ，（），（），（），（）。由于数据采集网络中，各子节点到达子网 节点的最小跳数满足 （），故 （）类别邻居节点始终存在，且子节点 进行数据传输时选择位于其上第 期田园，等：基于改进 的电网数据采集路由算法 一层的 （）类邻居节点可使其传输路径跳数最小、传输延时较低，避免产生数据传输回路从而造成故障，因此传统 电网数据采集算法在 （）邻居节点集合中选择其下一跳节点。（）构建决策度量值及路由信息表：在构建源节点 到目的节点 的决策度量值 （，）过程中，以节点间最小传输跳数构建链路权重及决策度量值，以两子节点、间链路 （，）是否属可直接连通链路 ，计算两点间边的权重 （，），即：（，）（，）（，）（，）（）若源节点 到目的节点 的路径集合为 ，各路径度量值 （）为该路径上所有节点间边的权重（、）之和，即：（）（，）（，）（）将集合 中链路度量值 （）最小的链路 （）作为数据传输链路，并选择该链路上的首端节点作为源节点 选择的下一跳节点：（）（）（）（）（）（）根据 路由协议构建源节点 到目的节点 传输路径上各子节点路由信息表，包含如表 所示的信息表项。表 传统 算法路由信息表项 目的节点下一跳节点跳数权值序列号表 中目的节点（）特指网络中的 子网网关节点，下一跳节点（）指最优电网数据传输路径上的各子节点的下一跳节点，度量值（）为源节点 到目的节点 的路径消耗，序列号（）代指电网数据信息包 号，用于判断路由信息是否及时更新，序列号较大电网数据包为最新路由信息。（）路由过程及路由更新 ：采用传统 算法在路径选择过程中，为防止遍历节点过多，影响数据采集效率，结合贪婪算法将所有子节点，分为集合、，其中 （）、（），然后将 集合中的节点按照跳数递增的顺序添加到集合 中，且电网数据传输过程中严格按照路由信息表中度量值（）最小进行下一跳节点选择，并将各项信息记录在路由表中，具体路由过程如图 所示。图 传统 算法路由过程示意图在路由过程中，因无线多跳 网络拓扑结构不会发生变化，从而导致数据传输路径在整个电网数据采集过程中未发生任何变化。而随着节点数据流量的增加，其流量负载 一直加大，若不进行路由更新会造成节点拥塞形成网络瓶颈。传统 算法通常采取时间触发的方式，进行周期性数据传输及路由信息更新。在某一传输周期内因数据序列号与数据到达时间呈正比例关系，故可根据序列号大小判断数据是否过期。若节点新接收到数据包的序列号相较现有数据包较大则进行路由信息更新；否则抛弃该数据包，放弃更新；当两者序列号相同时，则抛弃度量值较大数据包，将度量值较小数据包记入路由信息表。问题描述问题：由于采用传统 算法在进行电网数据传输路径选择过程中，以节点间最小跳数 （，）构建决策度量值在其上层邻居节点 （）集合中选择下一跳节点构建最短传输路径，该度量值只考虑了节点间最小跳数 （，）未合理调度各节点剩余传输容量 ，无法实现数据平衡，从而导致最短路径承载过多流量任务，路径上的节点因其剩余传输容量（）不足，而产生网络瓶颈。问题 ：如图 所示，子节点、均位于彼此通信范围外，从而无法获取对方的数据传输信息，由于位于两者通信范围内，故可同时接收到来自子节点、的数据信息包，而在同一周期内，当 向 发送数据时，由于 位于 通信范围之外，无法检测到节点 正在向节点 传输数据，若此时 也向节点发送数据，则会在数据接收端 处产生数据碰撞 ，从而造成数据包丢失，出现“隐藏终端”现象。计算机应用与软件 年图 “隐藏终端”数据碰撞模型如图 所示，位于 通信范围内，位于 通信范围外，子节点、均位于彼此通信范围内，从而可获取对方数据传输信道在同一时间是否被占用，由于位于两者通信范围内，故可同时接收到来自子节点、的数据信息包，而在同一周期内，当 向 发送数据、向 发送数据时，会检测到 的数据传输信道正在被占用，为避免发生数据碰撞，会延缓自己的数据传输，从而产生不必要的数据传输延时，使得节点传输容量无法合理充分使用，限制整个电网数据流量，出现“隐藏终端”现象。图 “暴露终端”干扰模型 改进的 电网数据采集路由算法 重构决策度量值及路由信息表在重构源节点 到目的节点 的决策度量值 （，）过程中，涉及其节点总容量 （），节点 流量负载，节点 单位时间内剩余传输容量 （），节点 数据生成速率 ，节点 数据接收速率 ，节点 数据速率，在单位时间内满足 ，根据上述节点总容量 （），节点 流量负载，可知其剩余传输容量 （）计算如下：（）（）（）由各子节点剩余传输容量 （）以及各数据传输链路 （，）的最小跳数 （，）构建各链路权重（，）：（，）（，）（）（）由式（）可知，链路权重 （，）与节点剩余容量 （）成反比例关系，故当 （）时，链路权重可取得无穷大值，而此时会因分母为零触发一个错误计算，因此需根据节点总容量 （）与节点 流量负载相对大小关系对 （）取值进行矫正，以保证节点剩余容量为 时，因链路节点权重过大而不会被选作下一跳节点，即：（）（）（）（）（）故可由各链路权重 （，），构建源节点 到目的节点 的综合决策度量值 （，），即：（，）（，）（）上述综合决策度量值 （，），结合了链路最小跳数以及节点剩余可用容量，保证电网数据传输时延较低保证其实时性的同时还避免了网络瓶颈的出现，从而降低了数据丢包率提升数据传输效率，以免其进入数据重传机制加大数据传输延时。根据 路由协议结合上述综合决策度量值 （，）重新构建各节点 路由向量信息表，将原本路由表中决策度量值用结合跳数与节点剩余传输容量的综合决策度量值代替原有跳数权值，具体各信息表项如表 所示。表 经改进 算法路由信息表项 目的节点下一跳节点综合度量值序列号在数据传输过程中采用上述路由信息表，虽然有可能使得无法实现数据传输最短路径，但是可以避免关键节点产生拥塞，从而避免溢出数据包进入重传机制，增加传输时延，节点综合决策度量值更改后参照图进行路由过程。路由更新方式分为时间触发与事件触发两种方式，本文算法采用时间与事件触发相结合的方式进行路由更新，其中时间触发以电网数据传输周期作为其更新周期，事件触发以电网中出现故障警告作为其触发更新的条件。为保证后续节点根据最新节点综合度量值进行路径选择，避免出现网络瓶颈，每一次数据传输完成后首先对节点剩余传输容量进行实时更改，随后才触发路由更新。消除“隐藏终端”及“暴露终端”为避免在同一周期内，两节点同时向同一节点发送数据产生数据碰撞，从而造成数据丢失，通过采取时间复用 的方式，将一个传输周期分为若干个数据传输时隙（时隙数等于发送节点数），各发送节点均可获得相互独立的数据传输时隙，各节点时隙内只允许该节点自身进行数据传输，从而消除“隐藏终端”现象且第 期田园，等：基于改进 的电网数据采集路由算法 同时确定了完成一次数据传输所需最短时间，即传输周期，可通过调度时隙分配方案提升数据传输速率，具体时隙分配如图 所示。图 周期内发送时隙分配流程在发送时隙中，有发送节点则存在数据接收节点，当节点为下一跳节点时，则进行数据接收，其剩余传输容量不足以接收数据包，则丢弃该数据包，不确认接收成功，由其他层传输，若其剩余传输容量足以接收数据包，则与自身生成数据包进行聚合排列，开始下一跳传输过程，当节点不为下一跳节点时，则等待下一个时隙接收数据，具体时隙分配如图 所示。图 周期内接收时隙分配流程为保证综合决策度量值 （，）实时性，需在每一周期结束路由更新前对节点剩余传输容量 （）进行实时更新，按上述时隙分配方案以周期内时隙作为节点剩余传输容量更新周期，本文算法具体步骤如下：（）根据无线 多跳网络拓扑构建电网数据传输网络模型，含 主网关节点、若干 子网网关节点以及分布广泛的数据采集子节点，传输采取单子网网关节点区域传输模式，各子节点均需通过各自领域 子网网关节点传输至 节点。（）根据步骤（）中网络模型构建数学模型，为降低数据传输跳数，各子节点在其上层邻居节点中选择剩余传输容量 （）较大的父节点，上层父节点选择流量负载 较大的下层子节点，使得最大流量负载 子节点连接最大剩余传输容量 （）父节点，即最空闲父节点最繁忙子节点构建父子节点，从而平衡数据传输流量。（）在步骤（）数学模型的基础上，结合各路径传输跳数与路径首端节点剩余传输容量 （）构建综合决策度量值，并根据 路由协议建立各子节点路由信息向量表，以综合决策度量值替代原有以跳数为基础构建的度量值。（）各数据采集子节点以步骤（）中综合决策度量值开始数据传输路由过程，并设置传输周期内各节点传输时隙与接收时隙，以避免“隐藏终端”与“暴露终端”现象，为保证节点路由信息更新实时性，采取时间触发为主、事件触发为辅、数据接收时隙为更新周期的方式进行路由更新过程。算法仿真及结果分析 评价指标为反映各类算法在电网数据采集过程中的数据采集效率、算法性能及传输实时性，本文以各算法中节点采集数据的平均丢包率 、数据传输平均端（各电网数据采集子节点）到端（主网关节点）的时延 作为其数据采集优劣的评价指标。已知节点 总容量为 （），数据生成速率为 ，令其数据传输速率为 ，单位周期内节点共接收到来自其邻居节点的数据包数为 ，则产生网络瓶颈时节点 的数据丢包率 为：（）（）（）式（）表明，由于各数据采集子节点在同一周期内其参数基本不变，故可通过降低拥塞节点其邻居节点在此期间向其发送数据包数 ，以此降低节点丢包率 计算机应用与软件 年，若在发生数据传输拥塞至传输正常期间，共有 个节点发生丢失数据包情况，累计丢包次数为 ，若节点 为第 次数据包丢失节点，该节点此次共计丢失 个数据，则电网数据采集平均丢包率 为：（）（）由于各数据采集节点设备参数一致，故同一电网数据采集业务在各子节点中采集效果一致，可令各子节点总容量 （）、数据生成速率 、数据传输速率 相同，则电网数据采集平均丢包率 为：（）（）同理，依据各电网数据采集节点参数一致，可设所有节点每跳传输时间一致为 ，各节点发送一个数据包时间一致为 ，节点缓冲区队列长度为，各 子网网关节点到主网关 节点的时间一致为 ，假设一数据包经 跳到达 节点，结合上述电网数据采集平均丢包率 ，被丢弃数据包进入重传机制前所等待时间、重传数据包传输跳数，则该数据包由子节点传输至 节点的时间 为：（）（）（）（）若传输数据包数为 ，则数据传输平均端到端时延 为：（）（）（）即：（）（）（）式中：为成功传输数据包平均跳数；为重传成功数据包平均跳数；为成功传输数据包所经平均队列长度；为重传成功数据包所经平均队列长度。当 足够大时，可令 与 近似相等，与 近似相等，故可将式（）简化为：（）由式（）可知，成功传输数据包平均跳数 、成功传输数据包所经平均队列长度 、被丢弃数据包进入重传机制前所等待时间 是数据传输平均端到端时延 的主要影响因素，而随着 值的增加而加大，而 值与 值可决定 值大小，故可通过调整成功传输数据包平均跳数 与成功传输数据包所经平均队列长度 来改变数据传输平均端到端时延 ，即涉及本文算法中根据数据传输最小跳数 （，）与节点剩余传输容量 （）构建的综合决策度量值 （，）。仿真结果及分析仿真环境及参数设置：本文采用 版本进行仿真实验，在正方形区域内随机投放 个智能电网数据采集子节点，区域设置一个 节点、一个 节点模拟单子网网关网络拓扑结构，仿真过程中设定各节点数据生成速率 、数据传输速率 、节点总容量 （）等各项参数一致，数据传输过程中无噪声干扰及重传次数与网络传输带宽的限制。首先通过设置各个节点不同的数据生成速率 ，统计传统 电网数据采集算法、本文经改进的 算法在不同 值下的电网数据采集平均丢包率 ，统计结果如图 所示。图 平均丢包率随节点数据生成速率折线统计图在相同仿真环境及场景下，仿真并统计两种算法分别在不同节点数据生成速率 下的数据传输平均第 期田园，等：基于改进 的电网数据采集路由算法 端到端时延 ，统计结果如图 所示。图 平均端到端时延随节点数据生成速率折线统计图通过上述实验统计结果可知，本文所提基于改进 的电网数据采集路由算法相较传统 电网数据采集算法，其数据传输平均丢包率 与平均端到端时延 均有明显下降。而随着节点数据生成速率 的增加，两种算法 值与 值趋于相等，证明本文算法在数据流量较小时，其对数据传输性能的提升明显，且流量较小时，数据采集平均丢包率较低，从而使得进入数据重传机制的数据包数较少，减少了重传时延，降低了节点平均传输时延。结语本文所提基于改进 的电网数据采集路由算法通过构建综合决策度量值解决了传统 的电网数据采集路由算法在数据采集过程中由于数据传输过于集中于最短路径，从而产生网络瓶颈导致数据传输拥塞的问题，并通过时间复用与功率控制消除了传统 算法在数据采集过程中存在的“隐藏终端”与“暴露终端”现象，并通过仿真实验结果表明：本文算法相较传统算法其对电网数据传输平均丢包率、平均端到端时延数据等各项性能均有明显优化，且本文基于改进 的电网数据采集路由算法在数据流量较小情况下更为适用。参考文献季知祥，邓春宇，吴江宁，等 面向智能电网的数据资产管理系统设计与应用 计算机应用与软件，（）：，（），：郭宝，项薇，罗黎明，等 基于“互联网 ”模式下电网数据采集终端安全接入防护研究 计算机应用与软件，（）：，（），：，（）：，（），：朱晔，姜志博，田浩，等 电网雷电大数据采集系统研发 高压电器，（）：刘波，费聚锋，张恒，等 卫星舱内无线组网传输系统的设计与实现 科学技术与工程，（）：郄朝辉，崔晓丹，李威，等 一种支撑电网故障感知与分析的全景录波平台 中国电力，（）：王文华，贾晓纯，陈兴渝 基于平衡树的智能电网数据采集路由算法 北京邮电大学学报，（）：刘潇潇，田家政，谢鲲，等 基于压缩传感的低开销电力数据采集方法 计算机应用研究，（）：，邵苏杰 面向智能配用电网数据?集的流量调度机制 北京：北京邮电大学，（上接第 页）田书，赵哲林，杜少通 基于改进多目标差分进化算法的节能优化调度 武汉大学学报（工学版），（）：，肖艳丽，李明星 阻尼最小二乘算法研究综述 软件导刊，（）：余航 计算机数学建模中改进遗传算法与最小二乘法应用 电子设计工程，（）：许娣，佃松宜，高钰凯 基于 模糊模型的 系统广义预测控制 自动化与仪表，（）：，：，（）：