一种面向智能电网数据采集的传感器聚合布局构造算法

邱雪松 蔺艳斐 邵苏杰 郭少勇 于 军



一种面向智能电网数据采集的传感器聚合布局构造算法

邱雪松 蔺艳斐*邵苏杰 郭少勇 于 军

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

智能电网中分布着大量的无线传感器用于监测智能电网设备和用户的运营状态信息，原始监测数据都采集到数据处理中心会给数据采集通信网络带来极大的数据流量压力。采用在数据采集过程中进行数据聚合的策略，将极大地缩减数据流量，降低通信网络的开销。因此聚合节点的选择以及聚合拓扑的构造成为智能电网数据采集的关键问题。该文提出一种基于层次聚类的异步分布式聚合布局构造算法。该算法首先按照层次聚类把所有节点按照距离的远近聚合构造出一棵采集树。随后计算出最佳分组数，按照该分组数进行分组。然后按照异步分布式策略进行最佳聚合节点的选择以及最佳传输拓扑的构造。仿真实验表明，该算法可以快速找到具有最小开销的数据聚合方式，提高智能电网数据采集网络的效率。

智能电网；数据采集；聚合布局；层次聚类；最佳聚合节点

1 引言

智能电网中分布着大量的无线传感器用于监测一定范围内的用户状态，数据处理中心需要采集这些数据进行分析处理，并作相应的供电调度。随着电网的建设和发展，智能电网的规模逐渐增大，通信设备种类数量繁多、网络结构越来越复杂，使得反映智能电网各层节点资源和设备运行状态以及相关业务的信息数据随之大幅度增加。原始监测数据都转发到数据处理中心，会给数据采集通信网络带来极大的数据流量压力。采用在数据采集过程中进行数据聚合的策略，将极大地缩减数据流量，降低通信网络的开销。因此聚合节点的选择以及聚合拓扑的构造成为智能电网数据采集的关键问题。

由于智能电网数据采集网络中的传感器设备分布密集，距离近的节点采集到的数据存在相关性[10,11]。文献[12]提出了一种基于最小生成树的数据聚合思想，在数据采集过程中可以进行数据聚合，从而降低链路开销。但是聚合节点的不同选择以及不同拓扑构造会带来不同的开销结果。因此，如何快速地进行聚合节点的选择以及如何进行聚合拓扑的构造是智能电网数据采集的关键问题。该问题包含3个关键部分，首先是分组数目的确定，其次是聚合节点的确定，最后是聚合拓扑的构造。

文献[13]提出了一种基于蚁群优化算法的传感器网络聚合思想，通过称为“蚂蚁”的人工代理探寻数据自源节点至汇聚节点的最优路径。该聚合策略在路径构造过程中需要大量链路开销。文献[14]提到的算法给每一个节点设置一个时间参数，节点时间参数变为零时，该节点发送链路信息给时间参数不为零的节点。该方法可以用最小开销寻找最佳聚合拓扑，但是在整个网络中只存在一个聚合节点，不适用于大规模的网络。文献[12]的算法，首先构造一棵最小生成树，然后删除最小生成树中超过一定阈值的边，这样最小生成树变成森林，在森林中一棵树就是一个分组。该算法可以完成网络中节点的分组，但是算法在构造最小生成树时的效率很低，且不能保证所选链路是最小开销的链路。文献[15]中的算法首先计算出组内节点之间距离的平均值和组间节点之间距离的平均值，然后把这两个平均值之和作为评测指标，选出最佳分组数。但是所有节点之间距离的平均值可能因为某个特殊的点造成较大的偏差，因此这样选出的最佳分组数并不是最优的。

基于上述分析，本文在文献[14]提出的异步分布式思想的基础上，引入层次划分的概念，对智能电网数据采集中节点分组，聚合节点选择，拓扑构造问题进行深入研究。首先进行采集树的构造，求出两组中任意两个点之间距离的平均值，选择该值最小的两个组合并，直到所有的节点合并为一个组，完成一棵二叉树的构造。之后按照最佳分组数评测指标，确定出最佳分组数，根据之前构造出的采集树和该最佳分组数进行分组。最后针对组内节点，考虑分别以各节点作为聚合节点，给其它每个节点设置一个时间参数，该参数与链路开销成比例，随着时间的推移，该时间参数逐渐减小，当某节点的时间参数减小到零时，该节点发送信息包到时间参数不为零的节点。按照这种方法可以用尽可能少的算法开销找到具有最小链路开销的聚合节点。

为此，本文提出一种基于层次聚类的异步分布式聚合布局构造算法。该算法首先利用层次聚类完成采集树的构造，随后根据最佳分组数评测指标，计算出最佳分组数进行分组，最后在每个组内用异步分布式采集策略进行聚合节点的选择、数据聚合服务布局的构造以及链路总开销的计算。仿真实验验证了该算法可以快速找到具有最小开销的数据聚合方式，提高智能电网数据采集网络的效率。

本文第2节是问题模型，把智能电网数据采集网络抽象化，介绍算法要解决的主要问题。第3节详细介绍基于层次聚类的异步分布式聚合布局构造算法。第4节实验仿真，验证算法的有效性。第5节给出结论。

2 问题描述

智能电网数据采集无线传感器网络如图1所示，该网络主要由若干个传感器和数据处理中心组成。所有传感器的数据都需要汇聚到数据处理中心，用于分析智能电网设备和用户的状态信息。但是随着智能电网规模的逐渐增大，把原始监测数据都转发到数据处理中心，会给数据采集网络带来较大的数据传输压力，因此需要在数据采集过程中进行数据聚合处理。本文数据采集聚合的思路是：传感器首先按照层次聚类分为多个组，在每个组中选取一个传感器作为数据聚合节点；此时若聚合节点数目较大，不能满足最佳分组数评测指标，则对聚合节点继续进行分组，直到聚合节点数目满足该评测指标；最后按照该分组聚合过程将网络中所有传感器的数据聚合到数据处理中心。在数据聚合过程中存在两个主要问题需要解决。

第1个问题是如何对数据采集系统中的传感器进行分组。首先是智能电网数据采集树的构造，根据层次聚类构造出一棵二叉采集树。然后根据该采集树确定最佳分组数进行分组。精确的分组数关系到网络链路开销的大小，分组内的节点数目较多，则组内链路开销较大，组间链路开销较少。反之，则组内链路开销较小，组间链路开销较大。因此，最佳的分组方式为分组后组间和组内开销之和最小。本文采用最佳分组数评测指标对分组性能进行评价，该评测指标在组内分离度和组间分离度两个因素之间取得平衡点，即可解决最佳分组数目确定问题。

图1 智能电网数据采集无线传感器网络

第2个问题是组内聚合节点的选择和数据传输拓扑的构造。所选择的聚合节点和构造的数据传输拓扑需要满足组内其它节点沿着该拓扑向聚合节点发送数据时，所需要的链路开销之和最小。本文采用异步分布式聚合策略进行聚合节点的选择和最佳聚合拓扑的构造，该策略分别把组内每一个节点作为聚合节点，计算出数据聚合时所需要的最小开销，选择这些最小开销中数值最小的节点作为聚合节点，并以该节点最小开销的计算过程产生的组内数据转发链路作为最佳聚合拓扑。为了以尽可能少的算法开销找到具有最小链路开销的聚合节点，在组内拓扑确定过程中，优先确定链路开销最小的节点的转发拓扑，降低聚合节点最小开销的计算复杂度。

为了解决以上两个问题，本文提出了智能电网数据采集无线传感器网络中基于层次聚类的异步分布式算法，具体见第3节。

图2 采集树的构造流程图

3 基于层次聚类的异步分布式算法

3.1 节点分组

3.1.1采集树构造 本节采用层次聚类的方法构造智能电网数据采集树，构造方法如图2所示。将网络中的每一个传感器看作一类，针对这个类，依据距离最近的原则，逐一进行分层聚合。

在构造二叉树时，新产生的类号是在原类号的基础上递增的。假设初始有7个类，距离最近的两个类是，则把合并后新产生的类是8，如图3(a)所示。之后新产生类9。按照这种方式最终构造出的采集树如图3(c)所示。

图3 采集树构造过程

3.1.2分组数确定 由于本文的目的是找到一个数据聚合的最佳布局，使得数据沿着该布局聚合传输时，所用的开销最小。当分组数目较多时，组内的开销减小，而组间的开销会增多；分组数目较少时，组内开销增加，组间开销减少。如何确定一个最佳分组数，使得组内和组间的开销之和最小，是本节要解决的主要问题。

为解决该问题，本节提出影响分组效果的两个因素，组内分离度和组间分离度。具体地，假设网络中共有个传感器节点，分成组，第组的组内节点数目用表示，则组传感器可以表示为集合，其中表示第个传感器组。表示同一组中任意两个节点之间的距离开销。

组内两两节点之间开销的方差为

3.1.3分组方式 在前两节中已经完成了采集树的构造和分组数的确定。图3(c)是构造出的采集树，分组过程是采集树构造过程的逆过程，本节以图3(c)构造出的采集树为例，介绍分组的具体方式。

由图3可知，距离越近的类越优先合并，合并时产生的类号越小，因此分组时节点号越大，越优先去掉。如图4(a)所示，去掉节点13，采集树变为有两棵树的森林，一棵树中的叶结点是一组，传感器分为2组；如图4(b)所示，进一步去掉节点12，传感器分为3组；如图4(c)所示，进一步去掉节点11，传感器分为4组。按照这种分组方式，假设采集树中有个传感器(即采集树中叶结点的数目)，要分为组，则去掉采集树中节点号最大的个节点即可得到最佳分组方式。

图4 分组过程

3.2聚合策略

3.2.1聚合流程 本节主要是针对组内的所有节点，进行聚合节点的选择和聚合拓扑的构造。算法分别把组内每一个节点作为聚合节点，计算出数据聚合时所需要的最小开销，选择这些最小开销中数值最小的节点作为聚合节点，并以该节点最小开销的计算过程产生的组内数据转发链路作为最佳聚合拓扑。在计算每一个节点作为聚合节点时的最小开销时，由于给每一个非聚合节点设置一个时间参数，可以优先确定链路开销最小的节点的转发拓扑，且一旦该节点的拓扑确定即时间参数变为零以后，不再有关于链路信息的数据包发送到该节点，因此可以降低算法的链路开销。算法流程如图5所示。

图5 异步分布式聚合策略流程图

3.2.2聚合实例 选择某一节点作为聚合节点以后，其它节点转发数据到聚合节点的链路开销计算过程如图6所示。图中字母表示节点号，以作为聚合节点，边上的数字表示链路开销，中表示链路开销，表示时间参数，表示下一跳转发节点。

如图6(b)所示，在=0时，初始化各节点的时间参数和链路开销均为直接发送数据到节点所需开销。图6(c)显示在=1时刻，节点的时间参数变为0，其链路开销确定。发送自己的开销到节点，节点计算从节点转发的开销都比原来的小，所以转发链路都要经过节点。如图6(d)所示，在=3时刻，节点的时间参数变为0，其链路开销确定。发送数据到唯一时间参数不为0的节点,计算从转发的开销与原开销相同，不操作。如图6(e)所示，在=5时刻，所有节点的时间参数均变为0，此时各节点发送数据到节点的最佳拓扑以及最小开销确定。节点直接发送数据到节点，节点和的数据经过节点转发后到达节点，此时的最小链路开销为6。

图6 异步分布式聚合实例

4 仿真结果分析

4.1 仿真结果

4.1.1采集点分组 本文以随机分布的传感器节点和一个数据处理中心构成智能电网数据采集仿真网络，数据中心位于网络的中心位置。分别以50, 100, 150个传感器节点为例，引入和后，其随分组数目的变化情况分别如图7和图8所示。

图7显示，对随机分布的传感器节点进行分组时，组内分离度随着分组数目的增多而减少，然而无限增加分组数，即增加用于聚合的传感器节点是不合理的。因为频繁的数据聚合会降低数据转发的效率，同时具有聚合功能的传感器节点需要更高的开销。图8显示，传感器节点分别为50,100,150时，组间分离度最大的分组数分别为7,12,15。图7显示在分组数目分别大于7,12,15以后，组内分离度的变化已经很小，因此分别选择7,12,15作为节点数目为50,100,150时的最佳分组数。

4.1.2组内数据聚合 为了模拟具有300个传感器节点的网络，在100 m100 m的范围内，随机取300个点，根据异步分布式聚合策略产生的网络转发拓扑图如图9所示，完成数据聚合所需要的最小开销为10788。

4.2评测指标

为了比较异步分布式聚合策略(Async)，基于最小生成树的聚合策略(MST)，基于蚁群优化算法的聚合策略(ACAR)的性能，下面从最小开销和算法执行时间两个方面加以分析。

图10显示，与基于最小生成树的聚合策略和基于蚁群优化算法的聚合策略相比，异步分布式聚合策略所找到的最小开销值分别减小了10%~40%和0%~10%。这是因为异步分布式聚合策略寻找的数据转发拓扑可以保证每一个节点到聚合节点的链路开销最小，因此总开销是最小的。图11显示，异步分布式聚合策略所用时间随节点数目的变化很缓慢，而基于蚁群优化算法的聚合策略和基于最小生成树的聚合策略所用时间随着节点数目的增加，以接近于指数的速度增长。异步分布式聚合策略的高效性是因为该聚合策略优先确定距离近的节点的转发拓扑，且转发拓扑已确定的节点不再参与后续转发拓扑构造过程。因此异步分布式聚合策略可以明显提高智能电网数据聚合的效率，网络规模增大时，其效率提高更加明显，更适用于大规模网络。

            图7 CI随分组数目的变化             图8 CE随分组数目的变化             图9 异步分布式聚合策略产生的树

图10 两种策略计算的最小开销随节点数目的变化            图11 两种策略所用时间随节点数目的变化

5 结束语

智能电网中分布着大量的无线传感器用于监测一定范围内的用户状态，数据处理中心需要采集这些数据进行分析处理。为了提高数据采集的效率，需要在数据传输过程中进行聚合，因此需要设计一个高效的算法寻找数据聚合的最佳布局。为此，本文提出了基于层次聚类的异步分布式算法，该算法可以按照最佳分组数和传感器节点的位置对传感器节点进行分组，在组内利用异步分布式聚合策略进行最佳聚合节点的选择以及最佳聚合拓扑的构造。仿真实验表明，与基于蚁群优化算法的聚合策略和基于最小生成树的聚合策略相比，该算法可以以更高的速率找到具有最小链路开销的数据传输方式，适用于大规模智能电网聚合网络。

[1] Chang Chih-yung, Lin Chih-yu, and Kuo Chin-hwa. EBDC: an energy-balanced data collection mechanism using a mobile data collector in WSNs[J]., 2012, 12(5): 5850-5871.

[2] 钱志鸿, 王义君. 面向物联网的无线传感器网络综述[J]. 电子与信息学报, 2013, 35(1): 215-227.

Qian Zhi-hong and Wang Yi-jun. Internet of things-oriented wireless sensor networks review[J].&, 2013, 35(1): 215-227.

[3] 付乔. 移动无线传感器网络数据采集算法设计[D]. [硕士论文], 清华大学, 2013.

[4] 叶宁, 王汝传. 传感器网络中一种基于估计代价的数据聚合树生成算法[J]. 电子学报, 2007, 35(5): 806-810.

Ye Ning and Wang Ru-chuan.A tree formation algorithm for data aggregation based on estimate cost in sensor networks[J]., 2007, 35(5): 806-810.

[5] 李宏, 于宏毅, 李林海, 等. 对无线传感器网络区域数据聚合有效性的研究[J]. 计算机应用, 2007, 27(9): 2218-2226.

Li Hong, Yu Hong-yi, Li Lin-hai,..Efficiency of area- based data aggregation in wireless sensor networks[J]., 2007, 27(9): 2218-2226.

[6] 张强, 卢潇, 崔晓臣. 基于分簇的无线传感器网络数据聚合方案研究[J]. 传感器技术学报, 2010, 23(12): 1778-1782.

Zhang Qiang, Lu Xiao, and Cui Xiao-chen. Research on the scheme of data aggregation based on clustering for wireless sensor network[J]., 2010, 23(12): 1778-1782.

[7] 陈杰. 无线传感器网络中基于数据聚合路由协议研究[D]. [硕士论文], 西安电子科技大学, 2013.

[8] 张军, 杨子晨. 多传感器数据采集系统中的数据融合研究[J]. 传感器与微系统, 2014, 33(3): 52-57.

Zhang Jun, and Yang Zi-chen. Study on data fusion of multi-sensor data acquisition system[J]., 2014, 33(3): 52-57.

[9] 吉佳, 温巧燕, 张华. 无线传感器网络中基于分簇的数据聚合机制[J]. 传感器与微系统, 2015, 34(1): 17-20.

Ji Jia, Wen Qiao-yan, and Zhang Hua. Cluster-based data aggregation scheme in wireless sensor networks[J]., 2015, 34(1): 17-20.

[10] 陈凤超. 无线传感器网络路由及汇聚节点选址算法研究[D]. [博士论文], 华南理工大学, 2011.

[11] 吴坚, 张伟. 基于无线传感器网络的数据采集实验设计[J]. 实验室研究与探索, 2013, 32(6): 271-286.

Wu Jian and Zhang Wei. Design of an experiment for data acquisition based on wireless sensor network[J]., 2013, 32(6): 271-286.

[12] 徐晨凯, 高茂庭. 改进的最小生成树自适应分层聚类算法[J]. 计算机工程与应用, 2014, 50(22): 149-153.

Xu Chen-kai and Gao Mao-ting. Improved adaptive hierarchical clustering algorithm based on minimum spanning tree[J]., 2014, 50(22): 149-153.

[13] 叶宁, 王汝传. 基于蚁群算法的无线传感器网络数据聚合路由算法[J]. 南京邮电大学学报(自然科学版), 2008, 28(2): 63-68.

Ye Ning, and Wang Ru-chuan.A routing algorithm for data aggregation based on ACA in wireless sensor networks[J].(), 2008, 28(2): 63-68.

[14] Lu Zong-qing and Wen Yong-gang. Distributed algorithm for tree-structured data aggregation service placement in smart grid[J]., 2014, 8(2): 553-561.

[15] 陈黎飞, 姜青山, 王声瑞. 基于层次划分的最佳聚类数确定方法[J]. 软件学报, 2008, 19(1): 62-72.

Chen Li-fei, Jiang Qing-shan, and Wang Sheng-rui. A hierarchical method for determining the number of clusters[J]., 2008, 19(1): 62-72.

Sensor Aggregation Distribution Construction Algorithm for Smart Grid Data Collection System

Qiu Xue-song Lin Yan-fei Shao Su-jie Guo Shao-yong Yu Jun

(,,100876,)

Large-scale of wireless sensors are distributed to monitor smart grid equipment and user,s operating status information in smart grid. The original monitoring data are all collected to data processing center. And it brings huge data traffic pressure for communication network. Thus it is necessary to use data aggregation strategy in the process of data collection to reduce data traffic greatly, and reduce the overhead of communication network. This paper proposes asynchronous distributed aggregation layout construction algorithm based on hierarchical clustering. Firstly, a collection tree is constructed with the distance of all the nodes based on hierarchical clustering. Then the optimal numbers of clusters and group are calculated. And then, this paper selects the optimal aggregation nodes and constructs the best transmit topology with asynchronous distributed strategy. Finally, the simulation experiment shows that the algorithm could find the data aggregation mode of minimum cost quickly, and improve the efficiency for data collection in smart grid.

Smart grid; Data collection; Aggregation distribution; Hierarchical clustering; Optimal aggregation node

TP393

A

1009-5896(2015)10-2411-07

10.11999/JEIT150231

2015-02-09；改回日期：2015-05-14；

2015-06-29

蔺艳斐 907389726@qq.com

国家支撑计划(2015BAG10B01)和国家自然科学基金(61372108)

The National Key Technology Support Program (2015BAG10B01); The National Natural Science Foundation of China (61372108)

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

蔺艳斐： 女，1992年生，硕士生，研究方向为智能电网、网络与业务管理.

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

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

于 军： 男，1964年生，高级工程师，研究方向为通信网络管理.