物联网环境下基于演化博弈的动态频谱分配算法

黎宝华

摘 要：研究物联网环境下垄断频谱市场中两个有限理性的服务提供商基于需求响应的价格竞争。服务提供商购买频谱拥有者提供的频谱，相互动态竞争提供给次用户使用以谋求自身利益的最大化。引入动态频谱接入，同时考虑次用户对价格的反应，将服务提供商的动态价格策略选择建模为演化博弈模型。通过复制动态，提出的算法收敛到演化稳定均衡（ESS）。仿真结果表明所该算法是收敛的，可以达到ESS，分析结果验证了演化博弈算法的稳定性和有效性。

关键词：动态频谱接入;有限理性;演化稳定均衡;复制动态

中图分类号：TP277          文献标识码：A            文章编号：2095-1302（2015）01-00-03

0  引  言

在通信技术与计算机技术飞速发展的今天，智能化以超出想象的速度发展迅猛，使得信息技术对人的支撑扩展到了对物体的支撑，实现了物与物之间的通信与协作，物联网就是在互联网的基础上，将其用户端延伸和扩展到任何物品，进行信息交换和通信的一种网络[1]。目前业界普遍认为，物联网将会在未来得到更大规模的应用，将会引起继计算机、Internet之后，世界信息产业的第三次浪潮。物联网将物体携带信息实时采集上来，并进行信息共享和交互，实现时时、处处的“物物相连”[2，3]。物联网最早起源于1999年美国MIT“自动识别中心”提出的“万物皆可通过网络进行互联”的观念[4]。2005年， 国际电信联盟（ITU）在当年的ITU互联网报告中正式对物联网做出了定义[5]。随后，各个国家与地区都相继开启了物联网的发展之路，其中包括IBM“智慧地球”的理念，日本的“u-Japan”战略、韩国为期十年的“u-Korea”战略规划以及中国的“感知中国”等，成为各国国家级发展规划中的重要一环[6]。

在物联网存在与发展的诸多资源要素中，无线电频谱是当之无愧的基础性支撑资源[7-9]。认知无线电是一种提高无线通信频谱利用率的技术，为解决物联网频谱资源短缺与频谱需求旺盛之间的矛盾提供了有效的解决途径。由于涉及竞争问题，物联网的频谱资源管理属于策略的对抗，运用博弈论来解决是一种非常奏效的办法。借助博弈论，物联网和现有的无线系统之间的频谱共享在提高频谱利用率的同时也为现有的无线系统获得了更高的收益[10]。

本文考虑物联网环境下两个有限理性的无线网络服务提供商和次用户之间的动态频谱接入。无线网络服务提供商向频谱拥有者（如美国联邦通讯委员会FCC）租借频谱，再将未使用的频谱提供给次用户共享以最大化自己的利益[11]。我们假设这两个服务提供商可以通过价格策略动态竞争潜在的次用户。次用户的响应通过接受概率建模，反应其购买服务商提供的服务的意愿。同时引入演化稳定策略从动态的角度研究服务提供商的价格选择过程，并且考虑了次用户的响应;此外，有限理性的服务提供商可以根据我们提出的演化算法动态调整他们的策略达到演化稳定均衡。

1  系统模型

考虑含有两个有限理性认知移动服务提供商的垄断无线通信系统，两个服务提供商向同一个频谱拥有者租借频谱，并且在有限区域内相互进行价格竞争提供服务给终端的次用户。假设次用户都具有认知功能，模型如图1所示。在竞争过程中，两个服务提供商都最大化各自的收益，因而两者是非合作博弈。此外，假设次用户可以自由选择任一个虚拟服务提供商。

图 1  系统模型

考虑次用户对服务提供商定价策略的反应十分重要。因此，引入接受概率B（v，p），其中v为次用户的效用函数，p是服务提供商公布的价格。接受概率应具有以下属性：即随效用的增加或价格的减少而增加[12]：

（1）

因此，次用户的接受概率可以定义如下：

（2）

其中β为次用户对价格的敏感度， γ表示次用户对效用的敏感度， α是常数。

而次用户的效用函数定义为：

（3）

其中R为服务提供商提供的速率，p是服务提供商发布给次用户的价格，K，ε和δ是确定上述效用函数精确形状的正常数。

为了便于分析，我们假设α=1，β=γ=4，ε=10和δ=12。所以，接受概率可以改写为：

B（v，p）=e-p/v                                                     （4）

对应次用户的效用函数为：

（5）

2  基于价格的演化博弈算法和策略分析

我们假设两个有限理性服务提供商同时宣布他们的价格，并且互相不知道对方的价格。具有较高的接受概率的服务提供商将获得利润，而另一个服务提供商将没有利润。此外，如果两个供应商的接受概率是相同的，则他们都能获得利润。因此，服务提供商的效用函数定义为：

（6）

其中：Ci是服务提供商产生的固定成本。

在这个动态频谱接入的过程中， 每一个服务提供商都有两种价格策略的选择：高价策略ph或者低价策略pl。由于接受概率是价格的减函数，因此低价策略的接受概率Bl的值高于高价策略的接受概率Bh的值。

根据式（6）计算出的不同价格策略的收益，上述对称的博弈过程可由表1的2×2矩阵来表示。其中Bh是服务提供商选择高价策略ph的接受概率，Bl是服务提供商选择低价策略pl的接受概率，C是服务提供商产生的固定成本。

表 1  服务提供商的收益矩阵

服务提供商 2

服务提供商 1 ph pl

ph 1/2（ph-C）Bh，1/2（ph-C）Bh 0， （pl-C）Bl

pl （pl-C）Bl，0 1/2（pl-C）Bl，

1/2（pl-C）Bl

如表1所示，若两个服务提供商都选择高价策略ph，他们获得的收益为1/2（ph-C）Bh，否则，若同时选择低价策略pl，他们将分别获得收益1/2（pl-C）Bl;若一方服务提供商选择低价策略，而另一方选择高价策略，则选择低价策略的服务提供商将获得收益（pl-C）Bl，选择高价策略的服务提供商将获得零收益，反之亦然。

3  演化稳定均衡解

在动态频谱接入的竞争博弈中，博弈双方都以最大化自己的利益为目标，每个博弈者的均衡策略都是为了达到自己期望收益的最大值，与此同时，其他所有博弈者也遵循这样的策略，则这样的策略组合被称为纳什均衡[13]。

定义服务提供商选择高价策略ph的概率为x（0≤x≤1），则选择低价策略pl的概率为1-x。利用上述演化博弈模型，服务提供商选择高价策略和低价策略的期望收益分别为：

v（ph，x）=vh=1/2x（ph-C）Bh                                     （7）

v（pl，l-x）=vl=1/2（1+x）（pl-C）Bl                      （8）

因此服务提供商的平均收益为：

（9）

根据vh=vl，即式（7）等于式（8），可以得到完全理性条件下的纳什均衡解：

（10）

然而在有限理性条件下，如果选择高价策略的收益高于平均收益，则根据复制动态定义，选择高价策略的概率x将会增长。所以依照复制动态方程，有限理性的服务提供商选择高价策略的变化率可以表示为：

（11）

基于复制动态，演化均衡定义为复制动态稳定的不动点集。演化均衡是演化博弈的理想解，因为博弈者的种群随着时间的演化会收敛到演化均衡。此外，当博弈者的收益等于平均收益，他们都不会再改变自己的策略，从而达到演化均衡时。

令式（11）等于0，从而可以得到稳定均衡点：

x=0，x=1或              （12）

其中x=0表示服务提供商在博弈中最终会选择低价策略， x=1表示服务提供商在博弈中最终会选择高价策略，而是动态频谱接入博弈的混合策略均衡，即按一定的比例选择高价策略和低价策略。

有限理性服务提供商的策略是根据他们的当前收益和平均收益进行选择的。所以基于演化博弈的动态频谱接入算法可以描述如下：

（1）有限理性服务提供商随机地选择高价策略和低价策略。

（2）迭代： t = 1， 2， 3， ……

①服务提供商根据式（1）在时刻t计算选择策略后所获得的收益v（ph，x）以及平均收益

②if v（ph，x）<

if rand （ ） < [-v（ph，x）] /

选择低价策略

end

end

③结束。选择低价策略的比例达到稳定，即进化均衡。其中rand（）∈[0，1]在这里表示一个随机数。

4  仿真结果

考虑动态频谱共享的认知无线系统包含两个有限理性移动虚拟服务提供商，其中仿真参数设置如下：服务提供商的固定成本为0.1，提供的速率为20 Mb/s，参数K为5×106。为了不失一般性，服务提供商的高价和低价分别假设为5和1。

本算法在不同初始策略选择概率条件下的收敛情况如图2所示。可以看出，本文所提出的演化算法是收敛的，并且最终收敛到0，这表示服务提供商最终选择低价策略，即不论初始选择低价策略还是高价策略，随着时间的迭代，有限理性的服务提供商最终会选择低价策略以吸引潜在的次用户，所以低价策略是收敛点。

图2  策略选择的收敛过程

图3给出了不同初始策略选择概率条件下服务提供商的收益演化情况。服务提供商选择低价策略的收益等于平均收益，此时博弈达到演化均衡，一旦达到演化均衡，博弈者都不会再改变此时的选择，而选择高价策略的服务提供商最终将会获得零收益。这表示服务提供商在初始公布的价格越低，次用户的接受概率则越高，即更多的次用户会选择低价策略的服务提供商，因此服务提供商获得的收益更多;相反，选择高价策略的服务提供商最终不会获得收益。

6  结  语

本文研究了物联网环境下双寡头垄断市场中两个有限理性的服务提供商的需求响应价格竞争。为了实现利益最大化，服务提供商动态的相互竞争以吸引次用户。我们提出了演化博弈理论来建模服务提供商的动态价格策略选择，利用接受概率B（v，p）映射次用户对服务提供商提供服务和公布价格的反应，通过复制动态，算法达到演化均衡。仿真结果表明，本文所提出的算法是收敛的，并且可以达到演化均衡，这可能为物联网环境下的无线网络供应商提供一些见解。

图3  服务提供商的收益演化过程

参考文献

[1] 李会平. 物联网：实现中国飞跃的一次机会[J]. 创新科技， 2010（5）：10-12

[2] 刘爱军. 物联网技术现状及应用前景展望[J]. 物联网技术，2012，2（1）：69-73.

[3] 杨博雄，倪玉华，刘琨，等. 现代物联网体系架构中核心技术标准及其发展应用研究[J]. 物联网技术， 2013，3（1）：71-76.

[4] Gershenfeld N，Krikorian R，Cohen D. The Internet of Things[J]. Scientific American， 2004（4）：76-81.

[5] International Telecommunication Union. ITU Internet Reports 2005： The Internet of Things[R]. 2005.

[6] 刘强，崔莉，陈海明. 物联网关键技术与应用[J]. 计算机科学，2010， 37（6）：1-4.

[7] Akyildiz I F，Su W，Sankars Y.Wireless sensor networks： a survey[J].Computer Networks，2002，38（ 4） ： 393-422.

[8] 孙其博，刘杰，黎羴.物联网： 概念、架构与关键技术研究综述[J].北京邮电大学学报，2010，33（ 3） ：43-47.

[9] 姚海鹏，张智江.异构环境下物联网频谱规划研究[J].电信科学，2012， 35（ 3） ： 81-85.

[10] Lin Fuhong，Liu Qian，Zhou Xianwei，et al.Cooperative differential game for model energy-bandwidth efficiency tradeoff in the internet of things[J]. China Communications，2014（1）：92-102.

[11] S. Sengupta， M. Chatterjee. An economic framework for dynamic spectrum access and service pricing[J]. IEEE/ACM Trans. on Networking， 2009， 17（4）： 1200-1213.

[12] L. Badia， M. Lindstrom， J. Zander， et al. Demand and pricing effects on the radio resource allocation of multimedia communication systems[J]. IEEE Globecom，2003（7）： 4116-4121.

[13] 朱·弗登博格，让·梯若尔.博弈论[M].北京：中国人民大学出版社，1996.