没有合适的资源?快使用搜索试试~ 我知道了~
首页2基于Stackelberg博弈的虚拟网络资源分配研究.doc
资源详情
资源评论
资源推荐
基于 Stackelberg 博弈的虚拟网络资源分配研究
摘要:针对网络虚拟化环境中的资源分配问题,结合 Stackelberg 博弈模型,提出了一种
同时满足底层网络和虚拟网络效用最大的资源分配方案。首先设计了一种基于收益
(revenue)和花费(cost)的虚拟网络效用函数,并证明在底层网络的价格确定后,效用函
数(utility function)满足凹函数的条件,保证了虚拟网络间非合作博弈的纳什均衡点存在。
为了获取虚拟网络的最优带宽策略和底层网络的最优价格策略,提出了一种分布式迭代算
法。最后通过数值仿真实验验证了该算法的有效性,取得了参与者的最优策略和子博弈完
美纳什均衡。
关键词:网络虚拟化;Stackelberg 博弈;纳什均衡;资源分配
1 引言
The Internet has been a great success in the past few decades and has provided a whole new
way to access and exchange information. Its success has stimulated enormous growth and wide
deployment of network technology and applications. However, the growth and deployment itself
is now creating obstacles to future innovations. Specifically, due to the multi-provider nature of
the Internet, adopting a new network architecture require not only changes in individual routers
and hosts, but also joint agreements among ISPs. The size and scale of today’s Internet make the
introduction and deployment of new network technology difficult [1] [2] .
Network virtualization provides a promising way for addressing the ossification of the
Internet [1] 。网络虚拟化[3] 指的是在保留现有互联网架构的前提下,通过在现有网络上构
建虚拟网络(virtual network,VN)来满足多样化应用的需求。网络虚拟化是对网络设备
的虚拟化,即对传统的路由器、交换机等设备进行增强,使其可以支持大量的可扩展的应
用,同一网络设备可以运行多个虚拟的网络设备,例如防火墙、VoIP、移动业务等。由于
网路虚拟化屏蔽了底层基础设施资源的很多信息,使用起来更加方便。
目前 ,网络 虚拟 化技 术已 经被公 认为 是解决 互联 网僵 化问题的有 效手段。 In a
virtualized network infrastructure, diverse virtual networks share a common physical substrate
consisting of both links and flexible network platforms capable of hosting multiple virtual
routers[4] 。网络虚拟化的核心思想是将现有的 ISP 拆分为两个相互独立的实体底层网络提
供商(InP)和虚拟网络服务提供商(SP)[5] 。InP 负责建设和管理底层的物理网络,将网
络资源租赁给虚拟网络,并根据资源数量收取费用。SP 从一个或者多个 InP 中租用底层网
络资源构建和运营网络,通过向用户出售网络服务获得收益。底层网络提供商(一下简称
底层网络)之间存在着竞争关系,底层网络通过制定合适的价格来吸引更多的虚拟网络服
务提供商购买资源以收回成本;同时虚拟网络服务提供商之间也存在竞争关系,其目标是
确定从底层网络租用的资源数量以最大化自己的收益,虚拟网络在确定租用的资源数量时
必须考虑到竞争对手的策略。底层网络和虚拟网络之间的交互是一个 Stackelberg 博弈问题。
在网络虚拟化环境中,虚拟网络对底层网络的资源选择是目前研究的重点。文献 [6]
[7] [8] 是基于静态的资源分配算法,该算法较简单,部署花销较小,但是需要限定特殊情
况,比如不考虑用户需求的动态变化、忽略底层网络节点的有限能力以及底层物理节点与
链路的当前状况等,因此静态资源分配算法在保证虚拟网络间的资源均衡方面不具有优越
性。文献[9]
提出的虚拟网络映射算法分为两个阶段,先采用贪婪算法将虚拟节点映射到底层资源最大
的节点,然后利用 K 最短路径算法以及多商品流算法将虚拟链路映射物理路径上。文献
[10] 采用混合整数规划的方法,提出了确定型的虚拟网映射(D-VINE)和随机虚拟网映射
(R-VINE)算法。上述虚拟网络资源分配算法都是以最大化底层网络的收益为前提,没有
考虑虚拟网络的需求。文献[11] 提出了一种非合作博弈的虚拟网络资源分配模型,分析了
纳什均衡点的存在性,并通过一个迭代算法,验证了虚拟网络各条链路中的带宽最终能够
收敛到稳定的最优解。
本文针对网络虚拟化环境中的资源定价和分配问题,结合 Stackelberg 博弈模型,提出
了一种同时满足底层网络和虚拟网络收益最大的资源定价和分配方案。在网络虚拟化环境
下,采用 Stackelberg 博弈机制,将底层网络作为博弈的领导者,虚拟网络作为博弈的跟随
者,底层网络根据市场信息率先做出定价策略,虚拟网络在得到底层网络的决策后确定自
己的资源需求,通过动态交互使二者收益达到最大。
2 相关知识
2.1 博弈论基本概念
博弈论[12] (game theory)研究的是参与者之间互相影响时各自的决策过程以及最终
决策的均衡问题,也就是某个参与者选择策略时会考虑其他参与者的策略选择情况,同时
该参与者选择的策略有会影响到其他参与者的策略选择。一般地,博弈包括参与者
(player),策略空间( strategy space)和参与者收益(pay off structure)三个要素。
参与者:在博弈中,通过合理选择自己的行动,以期取得最大化收益的决策主体。一
般用 i=1,2…n 表示参与者。
战略空间:在博弈中,参与者可选择的行动方案称为战略,通常用 s
i
表示参与者 i 的一
个特定战略,用 S
i
={s
i
}表示参与者 i 的所有可选择的战略集合(又称为参与者 i 的战略空
间)。如果 n 个参与者每人选择一个战略,那么 n 维向量 s=(s
1
,s
2
,……s
n
)就称为一个战略组
合,其中 s
i
是参与者 i 选择的战略。
收益函数:在博弈论中,收益是在一个特定的战略组合下参与者得到的确定的效用或
期望效用。博弈论的一个基本特征是参与者的收益不仅仅取决于自己的战略选择,而且取
决于所有参与者的战略选择。或者说,收益是所有参与者各自选定一个战略所形成的战略
组合的函数。通常用 u
i
表示参与者 i 的收益,如果一个战略组合是(s
1
,……,s
n
),那么
每个参与者的收益可表示为 u
i
=u
i
(s
1
,……,s
n
), i=1,2,……,n。
2.2 纳什均衡
博弈论最基本的均衡是纳什均衡[12] 。纳什均衡(Nash equilibrium)指博弈的参与者
处于一种“稳定的”状态,在这种状态下,任何一个参与者都不会再更改自身的策略,因为
更改策略并不会获得比当前策略更高的收益。在博弈中,当任何一个参与者改变自身策略
可以获得更大收益时,会马上更改已经选择的策略,这也就会使得其他参与者重新改变自
身的策略选择,当然,博弈也就没有达到均衡状态。
剩余13页未读,继续阅读
lightday_1988
- 粉丝: 2
- 资源: 23
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
- MW全能培训汽轮机调节保安系统PPT教学课件.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0