基于加权队列的无线智能电网通信网采集数据流量调度算法

邵苏杰 郭少勇 邱雪松 孟洛明



基于加权队列的无线智能电网通信网采集数据流量调度算法

邵苏杰*郭少勇 邱雪松 孟洛明

(北京邮电大学网络与交换技术国家重点实验室 北京 100876)

智能电网的关键技术之一是为电力数据采集提供一个高效、可靠、安全的双向通信系统。使用具有通信能力的先进电力计量设备(智能电表)组成无线mesh网络采集数据，存在应用层数据流量对网络通信性能的挑战，当大量数据流量突发时，与本地局域网关较近的智能电表将面临较大的通信压力，可能产生严重的数据拥塞。为此，该文基于多网关联合的思想，提出一个新的基于加权队列的流量调度算法以缓解拥塞。首先，对多网关联合网络进行分析，确定影响网络性能的主要因素。其次采用队列加权的方法，提出新的流量调度算法。最后进行网络仿真，相对其它算法，该文所提算法能够极大缓解数据突发时刻的系统拥塞，有效地降低时延，同时在系统各网关吞吐量之间取得良好的平衡，能够提高采集网络的通信性能。

智能电网通信网；智能电表；流量调度；无线mesh网络；多跳通信

1 引言

随着新能源的广泛使用和智能交互用电方式的提出，智能电网将是一个以用户为中心的高度灵活，高效率，易接入和可靠的系统[1]。智能电网将用户和各种分布式能源纳入到智能发电、输电、配电和用电环节，允许用户积极参与到用电管理和故障报告中来，期望高效地利用各种分布式能源，提高电网的自愈能力，降低电力风险，同时提升电网的即插即用能力和互操作性[2,3]。实现这些功能需要完整而准确的用电数据，因此智能电网的关键技术之一是为数据采集提供一个高效、可靠、安全的双向通信系统[4,5]。

现有的电力数据采集系统广泛采用总线采集和公网GPRS无线传输相结合的方式，很难为智能电网提供上述功能所需的通信能力。PLC(Power Line Communication)以其与电力系统的紧密结合和经济性等特点成为合适的有线通信选择之一[6,7]。但PLC存在严重缺陷，电力传输和数据通信采用同一条物理路径，一旦发生故障，数据通信将会中断，无法保证实时性、完整性和准确性。其它电力有线通信技术面临着同样的风险。相对地，无线通信技术能够在满足智能电网数据采集所需带宽等传输能力的同时，解决上述问题，兼顾灵活性、易接入、低成本、易于控制等优势，得到了广泛的应用。因此，无线通信技术应成为智能电网数据采集系统通信基础设施的首选[5,8,9]。考虑到对居民区的无缝覆盖，多跳通信技术将大大优于长距离单跳通信，其不但在长距离抗信号衰减方面具有优势，还能高度确保网络的自组织、自愈性和可靠性。因此采用无线mesh网络采集智能电力数据是一个理想的选择[6,10]。

基于无线mesh网络的智能电网数据采集系统中，每个家庭用户安装集成无线通信模块且具有路由功能的智能电表，看作一个mesh结点。对居民区按一定的采集规模分成多个区域，每个区域存在一个本地局域网关(数据集中器)，本区域所有智能电表数据通过该网关与远程采集数据管理系统(数据中心)通信[11]。该网络架构下虽然能够依靠物理层，MAC协议等方面满足智能电网数据采集系统的通信需求，但是还必须解决应用层数据流量对网络通信性能的挑战。紧急状况下产生的时变数据流量将对智能电网通信网的通信可靠性提出极大的挑战，人口密集区域尤为突出[12]。例如，在断电和灾害等情况下，大量断电等故障信息的产生和交换传输将极大增加网络数据流量，与本地局域网关距离较近的智能电表(最后一跳结点)将面临较大的通信压力，极其可能产生严重的数据拥塞，导致网络吞吐量下降，严重影响数据采集的实时性、完整性和准确性。

相对于传统的无线mesh通信网络，智能电网中的无线多跳数据采集mesh网络对网络性能诸如带宽、时延的要求更高。由于采集数据与智能电网业务相关，为智能用电决策和数据分析提供支持，对实时性、完整性和准确性的敏感度更高，需要网络保证良好的吞吐量和时延。数据拥塞问题制约着智能电网业务的开展，必须及时有效地解决。为解决该问题，文献[11]利用mesh结点可以作为中继结点的特性，让所有智能电表参与到数据路由中，采用多区域联合的方法，将多个本地局域网合并成一个大的多网关网络，实现所有智能电表与任何一个局域网关的通信。

假设合适的路由协议设计完成，局域网关到远程采集数据管理系统出口的带宽足够，则只需研究如何在多个局域网关间平衡调度数据流量，进而降低拥塞。多跳网络的流量调度算法最先由文献[13]提出，但其没有考虑数据流量传输路径的结点跳数关系，且结点需要维护多种数据队列，算法复杂，时延较高。文献[14]在其基础上提出最短路径算法，但数据流归属地明确，对网络动态变化的适应性较低，不适用于多网关联合网络。文献[15]假设数据类型单一，兼顾跳数关系和结点队列关系，采用多网关联合方法提出了更优越的联合背压调度算法，但对二者之间的关系考虑比较简单，且忽略网络的即时状态，网络吞吐量随着数据速率的快速增大明显下降。这些问题都有待解决。

基于上述分析，本文采用文献[15]所提出的多网关联合的思路以及相应的网络结构进行深入分析研究。由于智能电力采集数据的特点，可以认为各结点(智能电表)收发数据类型一致，结点都只需维护一种数据队列。进而本文对紧急状态下网络面临的性能问题进行了认真分析，深入研究了结点跳数和队列长度对网络流量调度和性能的影响，分析了不同算法的优缺点，并提出了基于加权队列的流量调度算法。仿真验证了该算法能够在极大地降低数据量突发状况时掉包率的基础上，保证网络吞吐量和时延的有效性。

本文共分5节，第2节从网络性能的两个重要指标掉包率和端到端时延出发，具体分析多网关无线多跳数据采集网络结构下结点跳数和队列长度对网络性能的影响；第3节分析已有数据流量调度算法的优劣，在其基础上提出加权队列调度算法；第4节，仿真数据分析，验证新算法合理性；第5节给出结论。

2 网络性能分析

无线多跳数据采集mesh网络中，如图1所示，智能电表既是数据产生的原始结点，也是中继结点，不但传输自己产生的电力数据，还要中继传输邻居结点的数据。多网关联合网络中，原来作为其负责区域数据唯一出口的网关，现在只是选择之一，所有网关的集合组成了数据的目的集合，到达其中任意一个，数据将成功被传输到远程采集数据管理系统。根据智能电力数据采集的特点，系统每一时刻都可能有一个或多个数据产生进入网络。智能电表产生数据的速率将决定数据量，不失一般性地假设网络内所有智能电表产生数据的速率一致。本文的目标是解决拥塞，同时兼顾时效性，因此主要从掉包率和端到端时延这两个指标进行分析。

图1 智能电力数据采集多网关联合网络结构示意图

2.1 掉包率

2.2 端到端时延

假设传输个数据包，则平均端到端时延可记为

3 流量调度算法

3.1 改进的最佳路径算法

3.2跳数优先算法

3.3 联合背压算法

3.4 加权队列算法

加权队列调度算法核心部分表示为：

(2) (,+)时间区间内，进行流量调度，为一个数据处理周期：

3.5 算法比较

在智能电力数据采集中，准确性和完整性是第1位的，因此掉包率降低是流量调度算法的首要目标，时延次之。

4种算法都需要实时更新结点状态信息，带来额外的网络开销，一定程度导致性能下降。同时，结点间通信均通过无线传输完成，由于无线传输本身的特性如竞争共享无线信道产生的碰撞、信号衰减、噪音干扰等多种因素，导致算法实际性能一定程度低于理论值。

4 仿真结果分析

本节用一个远程采集数据管理系统，与4个本地局域网关相连，120个智能电表随机分布，构成一个多网关无线多跳智能电力数据采集实验系统。仿真过程中，所有结点使用同一种生成数据的速率，数据封装成512字节的UDP包，物理层使用IEEE802.11b标准，数据速率为2 Mbps，假设本地局域网关带宽足够，忽略噪音干扰和重传限制，系统初始状态存在少量最后一跳结点处于拥塞状态。图2，图3分别展示了不同数据产生速率下4种流量调度算法的系统掉包率和平均端到端时延。

图2中加权队列算法掉包率最低，其时延也最低，表明该算法时延受PLR带来的重传时延影响较大。结点产生数据速率较低时，联合背压和加权队列算法掉包率与时延水平相当，一旦数据速率加大，加权队列算法无论在掉包率和平均端到端时延方面都更具优势。因此，加权队列算法具有最优的性能。

图4，图5，图6，图7分别展示了4种算法在不同生成数据速率下4个本地局域网关的流量分布，表1列出了4种算法在不同生成数据速率下4个本地局域网关的流量分布百分比的标准差。表1中联合背压算法和加权队列算法的标准差更低，负载均衡度更高，这显示了它们具有更低掉包率的原因。联合背压算法比加权队列算法的均衡度更高，这因为加权队列算法考虑了网络的即时状态，进行了相应的调整，负载均衡度上付出了代价，但是表1可以清晰地看出，随着数据产生速率的增大，其负载均衡度在变好，说明算法在数据量较大或者拥塞情况下性能是可以信赖的。

表1 4种算法在不同结点生成数据速率下4个本地局域网关的流量分布百分比的标准差

图2 4种算法掉包率示意图

图3 4种算法平均端到端 时延示意图

图4 结点生成数据的速率为4.096 kbps时的不同网关吞吐量对比

图5 结点生成数据的速率为10.24 kbps时的不同网关吞吐量对比

图6 结点生成数据的速率为15.36 kbps时的不同网关吞吐量对比

图7 结点生成数据的速率为40.96 kbps 时的不同网关吞吐量对比

5　结论

无线多跳通信技术可以为智能电网通信网带来自组织性和自愈性，提高数据采集的准确性、完整性和可靠性。但某些突发状况下，大数据量导致无线多跳数据采集通信网络面临传输瓶颈问题，为此，本文提出了一种基于传输跳数和传输结点队列长度的加权队列流量调度算法，在多个单网关合并成一个大的多网关网络的基础上，有效解决了网络突发状况下的瓶颈问题，同时还能有效预防网络瓶颈的产生，提高了网络数据传输的时效性，使数据采集通信更加可靠和高效。仿真实验证明，算法完全能够达到相应的降低掉包率并尽可能降低系统平均端到端时延的目的，提高了无线多跳数据采集系统的通信性能。

[1] Niyato D and Wang Ping. Cooperative transmission for meter data collection in smart grid[J]., 2012, 50(4): 90-97.

[2] Lu Ning, Du Peng-wei, Guo Xin-xin,.. Smart meter data analysis[C]. Transmission and Distribution Conference and Exposition (T&D), 2012 IEEE PES, Orlando, 2012: 1-6.

[4] Li Hu-sheng and Zhang Wei-yi. QoS routing in smart grid[C]. 2010 IEEE Global Telecommunications Conference (GLOBECOM 2010), Miami, 2010: 1-6.

[5] Fan Zhong, Kulkarni P, Gormus S,.. Smart grid communications: overview of research challenges, solutions, and standardization activities[J].&, 2013, 15(1): 21-38.

[6] Gungor V, Sahin D, Kocak T,.. Smart grid technologies: communication technologies and standards[J]., 2011, 7(4): 529-539.

[7] Aalamifar F, Hassanein H, and Takahara G. Valibility of powerline communication for the smart grid[C]. 2012 26th Biennial Symposium on Communications (QBSC), Kingston, 2012: 19-23.

[8] Karimi B and Namboodiri V. Capacity analysis of a wireless backhaul for metering in the smart grid[C]. 2012 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Orlando, 2012: 61-66.

[9] Castellanos G and Khan J. Performance analysis of WiMAX polling service for smart grid meter reading applications[C]. 2012 IEEE Colombian Communications Conference (COLCOM), Cali, 2012: 1-6.

[10] Kulkarni P, Gormus S, Fan Zhong,.. A mesh-radio-based solution for smart metering networks[J]., 2012, 50(7): 86-95.

[11] Gharavi H and Hu Bin. Multigate communication network for smart grid[J]., 2011, 99(6): 1028-1045.

[12] Li Hu-sheng, Lai Li-feng, and Qiu C. Scheduling of wireless metering for power market pricing in smart grid[J]., 2012, 3(4): 1611-1620.

[13] Tassiulas L and Ephremides A. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[J]., 1992, 37(12): 1936-1948.

[14] Ying L, Shakkottai S, and Reddy A. On combining shortest and backpressure routing over multihop wireless networks[C]. Proceedings of the IEEE INFOCOM, Rio de Janeiro, Brazil, 2009: 1674-1682.

[15] Gharavi H and Xu Chong. Distributed application of the traffic scheduling technique for smart grid advanced metering applications using multi-gate mesh networks[C]. 2011 IEEE Golbal Telecommunications Conference (GLOBECOM 2011), Houston, 2011: 1-6.

邵苏杰： 男，1985年生，博士生，研究方向为网络管理与智能电网.

郭少勇： 男，1985年生，博士，研究方向为网络管理、终端管理与智能电网.

邱雪松： 男，1973年生，博士生导师，教授，研究方向为网络与业务管理.

孟洛明： 男，1955年生，博士生导师，教授，研究方向为网络管理和通信软件.

Traffic Scheduling Algorithm Based on Weighted Queue for Meter Data Collection in Wireless Smart Grid Communication Network

Shao Su-jie Guo Shao-yong Qiu Xue-song Meng Luo-ming

(,,100876,)

One of the key technologies in smart grid is an efficient, reliable and secure two-way communication system for meter data collection. Forming wireless mesh network with advanced electricity devices (smart meters), which have the communication capabilities for meter data collection, faces challenge on network communication performance caused by application layer data traffic. When a large number of data occur in emergence, the smart meter near the local LAN gateway faces great communicaton pressure, and it probably leads to extreme data congestion. Therefore, a new traffic scheduling algorithm is proposed based on the idea of the joint of muti-gateway to release the congestion of system. First, the muti-gateway mesh network is analyzed to study the main factors affecting network performance. Second, a new traffic scheduling algorithm is proposed with the idea of weighted queue of node. Simulation data show that compared with other algorithms, the new algorithm can release significantly the congestion of burst data, and it reduces effectively the latency and obtains a good balance among the throughput of the system gateways, which can improve the network communication performance.

Smart grid communication network; Smart meter; Traffic scheduling; Wireless mesh network; Muti-hop communication

TN915

A

1009-5896(2014)05-1209-06

10.3724/SP.J.1146.2013.01050

邵苏杰 buptssj@bupt.edu.cn

2013-07-17收到，2013-11-22改回

国家863计划项目(2011AA05A116)资助课题