基于超图的能源互联网最小能量损耗路由算法

曲朝阳，张艺竞,4，辛 鹏，李介夫，胡可为

(1.东北电力大学 信息工程学院，吉林 吉林 132012；2.国网吉林省电力有限公司吉林供电公司，吉林 吉林 132000；3.国网吉林省电力有限公司调控中心，吉林 长春 132021；4.吉林农业科技学院 电气与信息工程学院，吉林 吉林 132000)

基于超图的能源互联网最小能量损耗路由算法

曲朝阳1，张艺竞1,4，辛 鹏2，李介夫2，胡可为3

(1.东北电力大学 信息工程学院，吉林 吉林 132012；2.国网吉林省电力有限公司吉林供电公司，吉林 吉林 132000；3.国网吉林省电力有限公司调控中心，吉林 长春 132021；4.吉林农业科技学院 电气与信息工程学院，吉林 吉林 132000)

针对传统路由策略应用在基于电动汽车的能源互联网分配模型中会造成能源传输损耗问题，提出了一种基于超图的最小能量损耗路由算法。首先，设计了一种基于能量规划的能源超图拓扑建立方法，将传统电力能源拓扑网络抽象成基于能量规划的超图模型；其次，针对超图模型提出最小能量损耗路由策略，计算出能量损耗最小的能源输送路径，实现了对能源传输网络的能耗损失的控制。在超图模型的基础上通过与传统Dijkstra算法进行实验比较分析，证明该方法可以有效缩短能量传输规划时间，减少能源输送过程中的能量损耗。

能量路由；超图；能源互联网；能量输送

21世纪以来，在能源利用效率、节能环保等方面存在着的问题日益突出，节能减排成为世界范围内各国共同关注的一项重点工程[1-2]。利用先进的互联网通信技术构建的能源互联网将是未来能源基础平台[3-5]。各个国家都开始大力推动对能源互联网的研究和应用，但是大体都不能建立有效的模型解决问题。文献[7]介绍了一种基于电动公共汽车充放电的能源互联网接入和传输分配方式，这种能源互联网模型可以让研究人员进行深层次的分析。

文献[7]中，分析了电动公交汽车的运载能力：一辆普通的电动公交汽车(如比亚迪K9)的电池组容量为324度，每100公里消耗电能130度。城市公交路线的往返路程一般都远远小于100公里，这样算下来，如果用电动公交车来传送电能，每辆公交车每次可以传输194度电。文献中一个城市通过这个模型进行电能输送的能力也给出了分析：发达城市(如上海)的机动汽车总量约300万台，如果十分之一是电动汽车，每辆汽车只运送10度电能的话，可以通过这个模型运送300多万度电，相当于全市的五分之一的发电量。但是事实上，每辆车能输送的电能远远大于10度，通过能源互联网模型完全可以传输全市日常所需要的电能。

综上所述，在基于电动汽车传输的能源互联网模型中，理想状态下是不需要传统的电能传输工具，只需通过电动公交汽车日常运行，就可以进行电能的输送[6]。在日常生活中，公交汽车的路线和公交充电站已经确定，经过发电站的公交汽车不会经过每一个充电站，这样就必须通过其他汽车的转运。电能通过充电站从一辆电动公交汽车转给另外一辆电B2动公交汽车，这类似于传统的路由转发算法。对于能量转发算法来说，公交汽车在运行过程中或每次在充电站进行充电放电，都会造成能量损耗。

所以，能量路由算法的作用就是在充电站部署后，寻找从太阳能发电站到每个公交充电站的能量损耗最小的路径。针对能源传输网络跳数不同这一问题，传统路由算法如果想要应用在能源网络中必须把能源拓扑进行重新建立，本文设计了基于能量规划的能源超图拓扑建立方法，并在此基础上提出了一种基于超图的最小能量损耗路由算法。在本文建立的超图模型基础上，应用传统求最短路由路径的Dijkstra算法[10]和本文提出的路由算法进行实验比较，证明基于超图的最小能量损耗路由算法能有效减少能源输送能源损耗，缩短了能量传输规划时间。

1 基于能量规划的道路超图模型

1.1 能量损耗模型

基于电动汽车的能源互联网接入和传输分配模型是通过电动汽车的运行来进行电能的传输[7]。为了进一步讲述能源互联网能量损耗模型，本文假设如下场景，如图1是一个已经部署好充电站的城市公交路线拓扑图[8-9]。这个城市为了节能减排，所以的公交车都是电动公交汽车，并且在城市的偏远区域建立了两个新能源发电站F1、F2。这两个发电站可以为全市的电动公交汽车提供能量。综上所述，能源互联网能量输送过程就是，为了满足城市中所有正在运行的电动公交汽车充电需求，如何将城市的偏远区域的新能源发电站生产出的电能，通过电动公交汽车系统的自运行，输送到城市每个角落的充电站中。图1中部署了4充电站，分别在公交站点B1、B2、B3、B4上，每条公交线路上都有一个充电站，满足了所有公交路线R1-R4的充电需求。基于超图的最小能量损耗路由算法就是在此基础上，寻找合适的能量输送路径，将发电站产生的能量，通过电动公交汽车输送到各个充电站。

图1 公交路线示意图

但是，在现实生活中，没有一条公交路线能够通过所有充电站，如图1所示。B1充电站可以直接接受从发电站F1送出的能量，公交线路R4的电动公交车从F1取能量，到B1充电站释放能量，同样，从B3充电站可以直接接受从发电站F2输送的能量。但是充电站B2、B4就没有直接连通发电站的公交路线，由于能源互联网模型中没有传统的电能传输工具，所以这两个充电站所接受的能量就必须通过B1或B3充电站进行中转，例如R4上的电动公交从B3充电站取出能量，运行到B2，再将能量释放给B2充电站。电动公交汽车每次充放电这个过程，都会造成小部分能量损耗。

能量损失模型如下表示：

(1)

式中：El为从发电站到充电站损失能量百分比；pi为第i次充放电损失能量百分比；n为经过充电站转发次数。

由公式(1)可见，为了减少能量的损失，就要寻找从发电站到终点的最少充放电输送路线，这类似于计算机网络的路由策略。最常用的路由策略最短路径算法有：Dijkstra算法[10]、A*算法[11]、SPFA算法[12]、Floyd-Warshall算法[13]等。但是由于能源互联网能量输送路由又与计算机网络路由不同，导致传统算法不能用于与能源拓扑中。在能源互联网的路由策略中，当一辆携带电能的公交车到达另一个需要电能的充电站释放能量的过程中，会路过许多不需要进行充放电的充电站。在此过程中，该电动公交车只进行了一次充放电，在能源互联网路由策略中，这只能算一跳路由。然而在传统计算机网络路由中，这种情况是多跳路由，所以传统路由策略不适用于新型的能源互联网拓扑结构中。进一步进行解释，例如在图1中线路R6，公交从节点B3充电经过了B2到达节点B1进行放电。这一过程在计算机网络中被认为是2跳路由，但是从充放电方面来讲，电动公交在B3充电到B1放电，这过程充电放电次数为一次，就是一跳路由。这样就导致了城市公交网络转换为简单图模型不能应用于能量输送路由算法的设计。

1.2 基于能量规划的能源超图拓扑建立方法

这里我们引入超图来描述和分析能量输送路由模型。超图的特点是一条边可以包括多个节点，正好与一条公交路线有多个站点的特点相同。超图中每一条代表一条公交路线。每条超边包含多个顶点，也就对应每条公交路线包含多个公交站点。

具体抽象出基于能量规划的道路超图模型(如图2)过程如下：

第一步，根据输入的公交站点集合S和所有公交路线集合R，得到道路超图的结点集OS=R1∪R2∪…∪Rn，OS∈S。

第三步，遍历所有公交路线集合R，根据道路超图的结点集OS，求超道路边集ES={e1，e2，…，em}。si∈R且si∈S，则si∈ESR，在R中去掉si，查看R中下一个si+1。如果si+1∈R且si+1∈S，则si+1∈ESR。如此循环直到R=∅。

第五步，输出道路超图的结点集合OS={o1，o2，…，on}，结点能量权重集合OW={ow1，ow2，…，own}，道路超边集合ES={e1，e2，…，em}，超边能量权重集EW={ew1，ew2，…，ewm}。

图2 公交路线示意图

2 基于超图的最小能量损耗路由算法

在进行基于能量规划的能源超图拓扑建立后，新建立的超图模型上可以运用传统的最短路径算法解决，本文提出一种基于超图的最小能量损耗路由算法，可以明显缩短能量传输路径规划时间。

2.1 能量损耗模型

设某道路超图模型H由一个站点结点集OS={o1，o2，…，on}，结点能量权重集OW={ow1，ow2，…，own}，描述结点群体关系的超边集ES={e1，e2，…，em}及超边能量权重集EW={ew1，ew2，…，ewm}组成。

定义3 结点—超边的关联矩阵B=(bik)n*m可定义为：

(2)

定义4 结点oi(i=1，2，…，n)的关联超边集可定义为：

AES(oi)≡{ek|oi∈ek，k∈{1，2，…，m}}，

(3)

通常，将结点oi所在的超边数目称为oi的关联超边度数，记为|AES(oi)|。

定义5 超边ek(k=1，2，…，m)的结点集可定义为：

EOS(ek)≡{oi|oi∈ek，k∈{1，2，…，n}}，

(4)

通常，将超边ek所含的结点数目称为ek的关联点度数，记为|EOS(ek)|。

定义6 结点oi(i=1，2，…，n)的关联结点集可定义为：

(5)

通常，将与结点oi共享过超边的结点数目称为oi的直连点度数，记为|AOS(oi)|。

定义7 结点oi(i=1，2，…，n)在任一个结点扩展树中的结点代价函数f(oi)可定义为：当oi是根结点时，设f(oi)=0当oi不是根结点时，设f(oi)=f(parent(oi))+EW(MinEdge(parent(oi)，oi))显然，这是一个递归式定义函数。parent(oi)是结点oi的父结点，MinEdge(parent(oi)，oi)是包含结点parent(oi)与oi的超边集中取最小权重的超边，EW(MinEdge(parent(oi)，oi))是超边MinEdge(parent(oi)，oi)的权重值。

2.2 能量损耗模型

基于超图的最小能量损耗路由算法的基本思路，其输入输出为：输入结点集OS={o1，o2，…，on}，超边集ES={e1，e2，…，em}，超边能量权重集EW={ew1，ew2，…，ewm}及结点—超边的关联矩阵B=(bik)n*m。输出则为不同结点间的最短路径及其长度。

具体算法步骤如下：

第一步，根据结点—超边的关联矩阵B=(bik)n*m及定义4、定义6，为结点集OS中的每个结点oi(i=1，2，…，n)构造它的关联超边集AES(oi)和关联结点集AOS(oi)。根据结点—超边的关联矩阵B及定义5，为超边集ES中的每条超边ek(k=1，2，…，m)构造它的结点集EOS(ek)。

每个结点oi(i=1，2，…，n)的关联超边集AES(oi)和每条超边ek(k=1，2，…，m)的结点集EOS(ek)很容易由结点—超边的关联矩阵B构造出来。每个结点oi(i=1，2，…，n)的关联结点集AOS(oi)需要由AES(oi)和EOS(ek)构造出来。

第二步，当结点oi(i=1，2，…，n)的关联结点集AOS(oi)非空时，为其设计一个能存储oi与它的关联结点的取最小权重的超边及其权重值的结构体数组AssMEW(oi)。

例如，设结点oj是结点oi的一关联结点集AOS(oi)，采用基于最小代价优先的树结点扩展策略，为结个关联结点，则存储结点oi与其关联结点oj的最小超边信息可以设计为一个三元结构体：AssMEW(oi)[j]=〈oj，MinEdge(oi，oj)，EW(MinEdge(oi，oj))〉，MinEdge(oi，oj)是包含两个关联结点oi与oj的超边集中取最小权重的超边，EW(MinEdge(oi，oj))则为超边MinEdge(oi，oj)的权重值。

第三步，根据每个结点oi(i=1，2，…，n)的点oi构造一个以它为根结点的分支树。在构造分支树的过程中，以定义7来计算每个结点的代价函数。

第四步，输出构造的分支树即为超图模型中不同结点间的最短路径及其长度。

3 实验及结果分析

3.1 实验环境

实验的硬件配置为Inter(R)Core(TM) i7- 4710MQ 2.50GHzCPU，8GB RAM，软件配置为Microsoft Windows7旗舰版64位SP1下的Myeclipse开发环境下采用Java语言(JDK6.0)来进行仿真实验验证，并用Matlab2010b绘图。

3.2 实验数据集

本实验采用的测试数据集一美国纽约城市公交系统真实路线和运行数据，其公交数据包括所有的公交路线、公交站点、运行班次、时间等都在网络上公开发布，可以下载其数据来测试分析。本实验提取曼哈顿的城市公交路线图和运行数据，形成测试实验数据，该测试集大小为1G，包括41条公交路线，463个公交车站。

表1 实验数据表

3.3 实验结果及分析

M表示道路拓扑图中节点的个数，N表示道路拓扑图中超边的个数，T1表示基于超图的最小能量损耗路由算法的时间损失，T2表示Dijkstra算法的时间损耗，EL1表示应用基于超图的最小能量损耗路由算法后所对应的能量损失，EL2表示应用Dijkstra算法后所对应的能量损失。表2是应用基于超图的最小能量损耗路由算法后所对应的时间损耗和能量损失，表3是应用Dijkstra算法后所对应的时间损耗和能量损失。

表2 应用基于超图的最小能量损耗路由算法后对应的时间损耗和能量损失

表3 应用Dijkstra算法后所对应的时间损耗和能量损失

时间损耗对比，如图3所示，其中Dijkstra算法在能源传输路线规划这一步骤要花大量的搜索时间，而本算法时间开销较小。

用本文提到的能量损耗公式分别计算两种算法的能量损耗。能量损失对比，如图4所示，其中本算法在节点和边数变化的时候，有效进行能源传输路线规划，减少了能源损耗。

图3 时间损耗对比图4 能量损失对比

4 结 论

本文分析了现有的路由策略的最短路径算法不能有效应用在新型能源拓扑中这一问题，并针对基于电动汽车的能源互联网传输分配模型的特性进行研究，引入超图来描述和分析能量输送最短路径，设计了一种普通公交拓扑抽象成基于能量规划的道路超图模型的建立方法，在此基础上，提出了一种基于超图的最小能量损耗路由算法。通过实验验证，其结果表明提出的算法在能求出能量损耗最小的能量输送路径的同时，还可以有效缩短能量传输规划时间，减少能源输送过程中的能量损耗。

[1] 曲朝阳，陈帅，杨帆，等.基于双层次分析的智能变电站数据分类方法[J].东北电力大学学报，2014，34(2)：61-65.

[2] 曲朝阳，张率，刘洪涛.基于用电影响因素回归的小区用电预测模型[J].东北电力大学学报，2015，35(1)：73-77.

[3] 董朝阳，赵俊华，文福拴，等.从智能电网到能源互联网：基本概念与研究框架[J].电力系统自动化，2014，38(15)：1-11.

[4] G.Adomavicius，A.Tuzhilin.Toward the next generation of recommender systems：a survey of the state-of-the-art and possible extensions[J].Knowledge and Data Engineering，IEEE Transactions on，2005，17(6)：734-749.

[5] 李刚，刘继春，赵岩，等.能源互联网环境下数据中心能耗优化管理技术研究[J].电测与仪表，2016，53(10)：1-7.

[6] 章鹿华，王思彤，易忠林，等.面向智能用电的家庭综合能源管理系统的设计与实现[J].电测与仪表，2010，47(9)：39-42.

[7] P.Yi，T.Zhu，B.Jiang，et al.Deploying energy router in an energy internet based electric vehicles[J].IEEE Transactions on Vehicular Technology，2016，65(6)：4714-4725.

[8] 查亚兵，张涛，黄卓，等.能源互联网关键技术分析[J].中国科学：信息科学，2014，44(6)：702-713.

[9] Q.Sun，R.Han，H.Zhang，et al.A multiagent-based consensus algorithm for distributed coordinated control of distributed generators in the energy internet[J].Smart Grid，IEEE Transactions on Smart Grid，2015，6(6)：3006-3019.

[10] 王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学，2014，41(6)：217-224.

[11] 奚峥皓，李洪波，刘贺平，等.基于A*算法优化的多目标跟踪[J].清华大学学报：自然科学，2014，54(12)：1549-1554.

[12] 沈海澜，王玉斌，陈再良，等.一种基于分层图的改进SPFA算法[J].计算机工程，2012，38(13)：251-253.

[13] L.Ridi，J.Torrini，E.Vicario.Developing a scheduler with difference-bound matrices and the floyd-warshall algorithm[J].IEEE Software，2012，29(1)：76-83.

AnEnergyInternetRoutingAlgorithmonHypergraphBasedMinimum-EnergyLoss

QuZhaoyang1，ZhangYijing1，4，XinPeng2，LiJiefu2，HuKewei3

(1.School of Information Engineering，Northeast Electric Power University，Jilin Jilin 132012；2.State Grid Jilin Electric Power Co.，Ltd.Jilin Power Supply Company，Jilin Jilin 132000；3.State Grid Jilin Province Electric Power Co.，Ltd.Control Center，Changchun Jilin 132021；4.School of Electrical and Information Engineering，Jilin Agriculture Science And Technology College，Jilin Jilin 132000)

This paper involved a problem that the traditional routing strategy applied to energy internet distribution model of electric vehicle can bring energy transmission loss，and proposed a routing algorithm on Hypergraph-Based minimum-energy loss.First，it designs an establishment method energy topological graph and the electric network topology of traditional power is abstracted hypergraph model based on energy planning；secondly，it succeeds in controlling power loss on energy transmission network by proposing the hypergraph model of minimum energy loss routing and calculating energy transport path of minimum energy loss.Through an analyzing between calculation and test with Dijkstra algorithm widely used，this method can effectively shorten energy transfer planning time，reduce energy consumption during energy transfer process.

Energy routing；Hypergraph；Energy internet；Energy transfer

2017-02-28

国家自然科学基金项目(51277023)；吉林省科技计划重点转化项目(20140307008GX)

曲朝阳(1964-)，男，博士，教授，主要研究方向：智能信息处理等.

电子邮箱：qzywww@neepu.edu.cn(曲朝阳)；332856891@qq.com(张艺竞)；1406989666@qq.com(辛鹏)；frqkycg@163.com(李介夫)；qzynedu@qq.com(胡可为)

1005-2992(2017)06-0093-07

TM72；TK01

A