计算机科学与应用  >> Vol. 10 No. 9 (September 2020)

主配网一体化环境下基于拍卖的网络服务商选择算法
Auction-Based Network Service Provider Selection Algorithm in the Main Distribution Network Integration Environment

DOI: 10.12677/CSA.2020.109166, PDF, HTML, XML, 下载: 313  浏览: 434  国家科技经费支持

作者: 谢 可:国网信息通信产业集团有限公司,北京;张筱筠:国网河南能源互联网电力设计院有限公司,河南 郑州;陆继钊:国网河南省电力公司信息通信公司,河南 郑州

关键词: 电力通信网主配网一体化资源分配拍卖VCG机制Power Communication Network Main Distribution Network Integration Resource Allocation Auction VCG Mechanism

摘要: 为解决主配网一体化模式下,网络资源利用率低、资源分配效率低的问题,本文将主配网一体化模式下网络资源分配问题建模为网络资源提供商、网络资源需求商、资源拍卖中心构成的三方博弈问题,提出了一种主配网一体化的资源分配模型。为实现多个网络服务提供商和多个网络资源需求商资源分配的社会效益最大化,提出了基于拍卖的网络服务商选择算法,该算法基于VCG拍卖理论,提出社会福利最大化的网络资源提供商报酬分配策略。仿真实验部分,通过与已有的资源分配算法进行比较可知,本文提出的资源分配算法在网络资源的平均利用率、总效用值方面,都取得了较好的效果。
Abstract: In order to solve the problem of low network resource utilization and low resource allocation effi-ciency in the main distribution network integration environment, this paper models the network resource allocation problem as the three-party game problem, consisting of network resource provider, network resource demander and the resource auction center, and then proposes a resource allocation model. In order to maximize the social benefits of multiple network service providers and multiple network resource demanders, an auction-based network service provider selection algorithm is proposed, which proposes social welfare maximization strategy based on VCG auction theory. In the simulation experiment part, by comparing with the existing resource allocation algorithm, the resource allocation algorithm proposed in this paper achieves good results in terms of the average utilization rate and total utility value of network resources.

文章引用: 谢可, 张筱筠, 陆继钊. 主配网一体化环境下基于拍卖的网络服务商选择算法[J]. 计算机科学与应用, 2020, 10(9): 1580-1587. https://doi.org/10.12677/CSA.2020.109166

1. 引言

在传统的电力系统中,一般都包括主网和配网两部分,主网的功能是输电,即传输110 KV及以上电压的电流,配网的功能是供电,即给配电站和负荷提供35 KV及以下电压的电流。但是,随着智能电网和信息技术的快速发展,为了保证电网可靠性运营的前提下,提升电网公司的工作效率,主配网一体化的通信组网模式被提出 [1] [2]。

为了满足主配网一体化的通信组网模式,需要对现有的主网和配网的传输资源进行整合,从而在指挥中心实现对主网和配网资源的统一管理和资源调度。但是,当前电力系统的光纤覆盖范围较低,而且存在较多租用第三方光纤网络资源的情况。如果要实现主配网一体化的通信组网模式目标,电力公司需要建设或租用更多的网络资源。另外,主网和配网的电力业务类型不同,对网络的QoS需求也不同。在这种背景下,仅仅依靠新建网络,不能为实现主配网一体化的通信组网模式提供充足的网络资源。因此,需要研究如何有效利用电力系统的已有网络资源和第三方网络提供商的网络资源,通过资源互补和共用,实现主配网一体化的通信组网模式。

关于如何提高电力系统的网络资源的使用效率,已有一些研究成果 [3] [4] [5] [6]。文献 [3] 主要解决电力系统自己建设光传输网络的规划问题,并通过改进遗传算法,求解电力光传输网络的最优化建设范围和建设顺序。文献 [4] 主要研究智能电网环境下,通过求解最小建设代价函数,在保障网络可靠性的前提下,实现电力系统建设网络资源的性价比最优化。文献 [5] 分析了智能电网中业务对QoS的需求,将业务分类为多种QoS类型,并提出了一种基于QoS差异化的电力网资源动态优化算法,在保障业务QoS的前提下,提高了电力网资源的高效运营。文献 [6] 基于网络虚拟化技术,将电力无线专网的基础网络进行虚拟化,将底层基础网络服务商划分为底层基础网络服务商和虚拟网络服务商,从而更好的提高电力无线网络的资源利用率。综上所述,已有研究在提升电力通信网的资源利用率方面,已经取得了较好的成果。但是,大部分研究主要解决同一网络基础设施提供商的资源分配问题。在主配网一体化的通信组网模式下,网络资源提供商的参与者包括提供多个第三方光纤公网的网络公司和提供多个自建专网的多个电网公司,网络资源需求商包括承载多种QoS电力业务需求的主网和配网。所以,当前研究缺少对多个网络资源需求商和多个网络资源提供商环境下,电力通信网络的带宽容量、资源成本、资源价格等QoS要素的综合考虑,不能很好的解决电力通信网在主配网一体化环境下面临的问题。

为提高主配网一体化的通信组网模式下网络资源分配效率、降低资源浪费,基于拍卖算法,本文提出了主配网一体化的资源分配模型,该模型包括网络资源需求商、网络资源提供商、资源拍卖中心。其中,网络服务提供商是指提供公网的多个第三方网络资源公司和自己创建多个专网的电力公司,网络资源需求商是指承载电力业务的多种QoS需求的主网和配网。资源拍卖中心基于拍卖理论实现资源分配的功能,基于此模型,提出了基于拍卖的网络服务商选择算法。通过与已有的资源分配算法进行比较,在网络资源的平均利用率和总效用值方面取得了较好的效果。

2. 问题描述和资源分配模型

为了在尽量满足主网和配网资源需求的前提下,提高网络的利用率和经济收益,本小节首先对问题进行如下形式化描述,之后提出基于拍卖的资源分配模型。

2.1. 问题描述

将主网和配网承载的电力业务作为网络资源需求商(NSD, network service demander)来描述。网络资源需求商根据其承载的电力业务特点申请网络资源。申请网络资源包括带宽、可靠性、延迟、抖动等QoS要求。本文将q个网络资源需求商集合表示为 I NSD = { NSD 1 , NSD 2 , , NSD q }

将提供公网与专网的网络公司作为网络服务提供商(NSP, network service provider)来描述。网络服务提供商对外提供网络资源服务。因为网络的可靠性、延迟、抖动等QoS性能指标取值范围较大,所以,不便于根据具体的QoS性能指标进行网络资源分配和销售。基于此,本文提出将网络资源QoS性能指标进行分类拍卖的策略,从而简化网络资源的拍卖模型。例如,可以根据QoS特性的优劣进行排序,依次分为铂金、金牌、银牌、铜牌四个等级的服务。网络资源服务商和网络资源需求商可以根据电力业务的可靠性、延迟、抖动等QoS要求,对网络资源进行一致性分类。本文将p个网络服务提供商集合表示为 I NSP = { NSP 1 , NSP 2 , , NSP p } ,其中第 i ( 0 < i p ) 个网络服务提供商NSPi提供m种类型的网络资源。设NSPi的第 j ( 0 < j m ) 种网络资源的带宽容量为 c p NSP i j ,第j种网络资源的单位投入为 u NSP i j ,第j种网络资源的固定平均投入为 f NSP i j ,当NSPi市场上的第j种网络资源销售承诺为 y NSP i j 时,NSPi消耗的投入 C NSP i 为公式(1)。

C NSP i = { 0 y NSP i j = 0 j = 1 m ( f NSP i j + y NSP i j × u NSP i j ) 0 < y NSP i j c p NSP i j (1)

2.2. 资源分配模型

为了能够在满足网络需求商对网络资源请求的前提下,提高网络服务提供商的网络资源的利用率,并且实现资源分配的公平性、公正性,本文将基于拍卖算法进行资源分配。在已有研究中,拍卖算法在资源分配中已经取得了较多的研究成果 [7] [8] [9] [10] [11]。文献 [7] 将拍卖算法应用到SDN网络中,提出了基于拍卖算法的NFV体系架构,实现了控制节点对接入节点的高效管理。文献 [8] 通过分析无线网络虚拟化环境下的研究成果可知,拍卖算法是实现无线网络资源高效分配的一种重要理论基础。文献 [9] 将拍卖算法应用到虚拟数据中心的资源分配中。文献 [10] 提出了基于拍卖理论的绿色数据中心资源分配方案。文献 [11] 提出了能量感知的资源分配算法。

综上所述,拍卖算法在网络资源分配的研究中已经取得了较多的研究成果。下面将基于已有研究成果和问题形式化描述部分的分析成果,提出多个网络服务提供商和多个网络资源需求商的资源分配模型(如图1所示)。从图1可知,该模型包括q个网络资源需求商、p个网络资源提供商、1个网络资源拍卖中心。其中,网络服务提供商是指提供公网的多个第三方网络资源公司和自己创建专网的电力公司,网络资源需求商是指承载多种QoS电力业务需求的主网和配网。主配网一体化的通信组网模式下,基于该资源分配模型,可以很好的调动网络资源提供商和网络资源需求商的积极性,从而有效的提高网络资源分配的效率,降低网络资源的浪费。

Figure 1. Resource allocation model

图1. 资源分配模型

3. 资源分配算法

基于上一小节的问题描述和资源分配模型,本小节首先定义了网络利益最大化的资源分配目标函数,其次,基于VCG拍卖理论,对实现该目标函数需要用到的NSP的开销、报酬、惩罚函数、效用函数等变量进行了定义,最后,提出了基于拍卖的网络服务商选择算法。

3.1. 目标函数

为提高主配网一体化环境下网络资源分配效率、降低资源浪费,本文将资源分配算法的网络利益最大化的资源分配的目标函数定义为:多个网络服务提供商和多个网络资源需求商相互协作,在满足网络资源需求商购买能力的前提下,确保所有网络服务提供商投入最小化,从而实现提高网络资源的社会效益的目标,见公式(2)。其中, X = { x 1 , x 2 , , x p } 表示资源分配时,p个NSP的资源销售承诺信息。 X * = { x 1 * , x 2 * , , x p * } 表示最优资源分配情况下NSP的资源销售量信息。公式(3)说明各个NSP的各种资源销售承诺大于0时,才会产生固定投入,式(4)表示各个NSP的各种资源销售承诺都不大于资源的实际能力,式(5)表示全体NSP的各种资源销售承诺等于全体NSD的各种资源购买量。

X * = arg min X i j ( λ j f NSP i j + y NSP i j × u NSP i j ) (2)

λ j = { 1 y NSP i j > 0 0 y NSP i j = 0 (3)

y NSP i j c p NSP i j (4)

k , l y NSD k l = i , j y NSP i j (5)

3.2. NSP的开销

在基于拍卖的网络资源分配过程中,每个NSPi的开销主要包括网络资源的固定投入、网络资源的单位价格和网络资源的数量,所以,本文定义每个NSPi分配网络资源给NSD时的开销为公式(6)。

C i ( x i , θ i ) = ( λ i f CPE i j + y CPE i j × u CPE i j ) (6)

3.3. NSP的报酬

考虑到本文提出的资源分配算法的目标是实现网络资源效用最大化,基于VCG拍卖理论 [12] [13],本文将报酬定义为每个NSPi参加网络资源分配带来的社会福利,见公式(7)。其中,每个NSPi参加网络资源分配带来的社会福利由两个部分相减获得,公式的前部分表示NSPi没有参加网络资源分配,公式的后半部分表示NSPi参加网络资源分配。所以,公式(7)表示NSPi参加网络资源分配前后给总的社会福利

带来的增加值。NSPi最优的网络资源分配策略采用 x t j ^ * 表示。

R i = [ min x y NSP t j c p NSP t j , NSP t I NSP \ i ( α f NSP t j ^ + u NSP t j ^ x t j ) ] [ NSP t I NSP , i ( α * f NSP t j ^ + u NSP t j ^ x t j ^ * ) ] (7)

3.4. NSP的惩罚函数

在进行网络资源分配时,网络资源拍卖中心基于NSD的需求和NSP的资源数量,求解出最优的资源分配策略。对于每一网络服务提供商NSPi的营业净收入是销售网络资源获得的收益减去各种投入。但是,如果NSP为了获得更大的效益,可能会谎报自己的资源总量信息。如果某个NSP谎报了总的资源供给量信息,必将导致网络资源拍卖中心的分配策略受到影响 [14]。在资源分配之后,如果某个NSP因为谎报资源而多获得了NSD的资源需求量,容易导致NSP不能满足NSD的需求,而影响NSD的业务正常运营,给网络资源拍卖中心带来投诉。所以,为了避免此类问题的发生,需要给谎报自己资源供给量信息的NSP进行惩罚 [15]。

创建一个公平的、资源效用最大化的网络资源分配环境,是实现本文资源分配算法目标的重要手段。基于此,本文提出一个合理的惩罚措施,从而督促每个参与网络资源分配的NSPi都能坚守诚信,从而避免资源分配失败,导致资源分配环境混乱。本文对说谎的NSPi进行惩罚的定义为公式(8)。

P i = R i { x i j * x i j ¯ } (8)

3.5. NSP的效用函数

NSP的效用是指NSP将网络销售给NSD时获得的效用。本文定义NSP的效用函数为公式(9),其中, P i 表示NSPi为了多销售网络而作假遭到的惩罚,NSPi上报给网络资源拍卖中心的网络提供量采用 θ i = ( f NSP i j ^ , u NSP i j ^ , c p NSP i j ^ ) 表示。NSPi分配它的 θ i 网络 x i x 给NSD的开销采用 C i ( x i , θ i ) 表示。NSPi销售它的 θ i 网络 x i x 给NSD后获得的报酬采用 R i 表示。

U i ( x i , R i , θ i ) = R i C i ( x i , θ i ) P i (9)

3.6. 基于拍卖的网络服务商选择算法

基于多个网络服务提供商和多个网络资源需求商的资源分配模型,为了实现多个网络服务提供商和多个网络资源需求商资源分配的社会效益最大化,提出的资源分配算法如表1所示。

Table 1. Network service provider selection algorithm based on auction

表1. 基于拍卖的网络服务商选择算法

下面对表1所述的基于拍卖的网络服务商选择算法关键步骤解释说明。第1行~第3行,n个NSPs向网络资源拍卖中心上报网络提供量信息 Θ = { θ 1 , θ 2 , , θ n } 。第4行~第6行,m个NSDs向网络资源拍卖中心提出网络购买量信息 b = { b 1 , b 2 , , b m } 。第7行,网络资源拍卖中心使用公式(2),为每个NSD需求分配资源,得到网络资源分配策略 x ^ * 。第8行~第14行,对每一个NSPi网络资源拍卖中心检测它是否能够为NSD提供符合约定的网络资源,如果不能,则使用NSP的惩罚函数(见式7、式8)对NSPi进行惩罚;其中r表示获得NSPi资源的用户数。第15行~第17行,网络资源拍卖中心使用NSP的效用函数(见式9)计算NSP的效用值。

4. 仿真

4.1. 环境

本实验使用matlab进行仿真,其中包括10个NSPs和10个NSDs在网络资源分配中心进行拍卖,拍卖的资源包括a类型网络、b类型网络两种。NSD的网络资源需求量以300为起始值,并以20为步长进行逐步增加。NSP建设a类型网络、b类型网络的最大销售承诺分别为 c p NSP i a c p NSP i b ,并在10和30之间均匀分布。NSP建设a类型网络、b类型网络的单位投入成本分别为 u NSP i a u NSP i b ,并在1和5之间均匀分布。NSP建设a类型网络、b类型网络的固定投入分别为 f NSP i a f NSP i b ,并在10和30之间均匀分布。

4.2. 评价指标

本文从NSP的资源平均利用率、NSP的总效用值两个维度进行评价。其中,NSP的资源平均利用率定义为已分配的资源总量除以资源总量(见公式10)。NSP的总效用值定义为所有NSP的效用值之和(见公式11)。

R NSP = y NSP i c + y NSP i e c p NSP i c + c p NSP i e (10)

U NSP = i = 1 N U i ( x i , R i , θ i ) (11)

4.3. 验证资源分配算法的有效性

为了验证本文提出的基于拍卖的网络服务商选择算法的有效性,采用NSP谎报资源量来模拟传统的资源分配算法,即在10个NSP中随机选取1到3个NSP,给资源分配交易中心谎报自己的资源容量,从而期望获得较多的利润。多上报的网络资源随机在1到10之间取值。

所有NSP上报自己真实容量和部分NSP谎报自己容量两种情况下总的效用值比较如图2所示。从图2可知,随着NSD资源需求数量的增加,两种情况下NSP的总效用值都在增加,但是所有NSP上报自己真实容量情况下的总效用值较大。所有NSP上报自己真实容量和部分NSP虚假上报自己容量两种情况下网络资源的平均利用率比较如图3所示。从图3可知,随着NSD资源需求数量的增加,两种情况下网络资源的平均利用率都在增加,并且所有NSP上报自己真实容量情况下的网络资源的平均利用率相对较大。所以,本文提出的资源分配算法在网络资源的平均利用率、总效用值方面,都取得了较好的效果。

Figure 2. Comparison of the total utility values

图2. 总效用值的比较

Figure 3. Comparison of the average utilization rate of network resources

图3. 网络资源的平均利用率比较

5. 总结

随着智能电网规模的快速发展,对电网的信息化、智能化要求越来越高。电网公司的电力系统集约化运营是电网企业可持续发展的必要条件。在这种背景下,主配网一体化的通信组网模式被提出。为了实现主配网的一体化运营,当前急需解决的一个关键问题是研究公网与专网的经济性分析模型,得到公网与专网的混合组网模式。为提高主配网一体化模式下,网络资源分配效率、降低资源浪费,本文提出了主配网一体化的资源分配模型,基于此模型,提出了基于拍卖的网络服务商选择算法。仿真实验部分,通过与已有的资源分配算法进行比较,本文提出的算法在网络资源的平均资源利用率和社会总效用方面,都取得了较好的效果。

基金项目

国家电网有限公司总部科技项目资助,项目编码:5700-202041163A-0-0-00。

参考文献

[1] 汪磊, 魏丽芳, 王克谦, 等. 主配网调控一体化图形平台设计[J]. 电力系统及其自动化学报, 2012, 24(1): 142-146.
[2] 曹军威, 万宇鑫, 涂国煜, 等. 智能电网信息系统体系结构研究[J]. 计算机学报, 2013, 36(1): 143-167.
[3] 石悦, 邱雪松, 郭少勇, 等. 基于改进遗传算法的电力光传输网规划方法[J]. 通信学报, 2016, 37(1): 116-122.
[4] Shi, Y., Qiu, X.-S. and Guo, S.Y. (2015) Genetic Algorithm-Based Redundancy Optimization Method for Smart Grid Communication Network. China Communications, 12, 73-84.
https://doi.org/10.1109/CC.2015.7224708
[5] Yu, R., Zhong, W.F., Xie, S.L., Zhang, Y. and Zhang, Y. (2016) QoS Differential Scheduling in Cognitive-Radio- Based Smart Grid Networks: An Adaptive Dynamic Program-ming Approach. IEEE Transactions on Neural Networks and Learning Systems, 27, 435-443.
https://doi.org/10.1109/TNNLS.2015.2411673
[6] 孟洛明, 孙康, 韦磊, 等. 一种面向电力无线专网的虚拟资源优化分配机制[J]. 电子与信息学报, 2017, 39(7): 1711-1718.
[7] Matias, J., Garay, J., Toledo, N., Unzilla, J. and Jacob, E. (2015) Toward an SDN-Enabled NFV Architecture. IEEE Communications Magazine, 53, 187-193.
https://doi.org/10.1109/MCOM.2015.7081093
[8] Liang, C.C. and Yu, F.R. (2015) Wireless Network Virtualization: A Survey, Some Research Issues and Challenges. IEEE Communications Surveys & Tutorials, 17, 358-380.
https://doi.org/10.1109/COMST.2014.2352118
[9] Correa, E.S., Fletscher, L.A. and Botero, J.F. (2015) Virtual Data Center Embedding: A Survey. IEEE Latin America Transactions, 13, 1661-1670.
https://doi.org/10.1109/TLA.2015.7112029
[10] Guan, X.J., Choi, B.Y. and Song, S. (2015) Energy Effi-cient Virtual Network Embedding for Green Data Centers Using Data Center Topology and Future Migration. Computer Communications, 69, 50-59.
https://doi.org/10.1016/j.comcom.2015.05.003
[11] Melo, M. and Sargento, S. (2015) Optimal Virtual Network Embedding: Energy Aware Formulation. Computer Networks, 91, 184-195.
https://doi.org/10.1016/j.comnet.2015.08.011
[12] Vickrey, W.W. (1961) Counter Speculation, Auctions, and Competitive Sealed Tenders. Journal of Finance, 16, 8-36.
https://doi.org/10.1111/j.1540-6261.1961.tb02789.x
[13] Bae, J., Beigman, E., Berry, R.A., Honig, M.L. and Vohra, R. (2008) Sequential Bandwidth and Power Auctions for Distributed Spectrum Sharing. IEEE Journal on Selected Areas in Communications, 26, 1193-1203.
https://doi.org/10.1109/JSAC.2008.080916
[14] Guan, X.J., Choi, B.Y. and Song, S. (2015) Energy Effi-cient Virtual Network Embedding for Green Data Centers Using Data Center Topology and Future Migration. Computer Communications, 69, 50-59.
https://doi.org/10.1016/j.comcom.2015.05.003
[15] Xia, M., Koehler, G.J. and Whinston, A.B. (2004) Pricing Combinatorial Auctions. European Journal of Operational Research, 154, 251-270.
https://doi.org/10.1016/S0377-2217(02)00678-1