双向拍卖结合贝叶斯模型的认知无线电网络频谱共享方案

戴　冬，王　果，王　磊

（1.河南工学院 计算机科学与技术系，河南 新乡　453003；2.西南财经大学 经济信息工程学院，四川 成都　610074）

双向拍卖结合贝叶斯模型的认知无线电网络频谱共享方案

戴冬1，王果1，王磊2

（1.河南工学院 计算机科学与技术系，河南 新乡453003；2.西南财经大学 经济信息工程学院，四川 成都610074）

针对无线电网络中频谱资源有限且利用率较低的问题，提出了基于双向拍卖结合贝叶斯推理模型的频谱共享算法。首先，主用户和次用户自适应地选择拍卖价格分享频段；然后，玩家基于反馈学习过程捕捉调整价格的策略；最后，进行重复拍卖过程直到达成共识。该算法采用了贝叶斯推理技术，能够自适应地响应不断变化的系统环境和玩家数量，具有良好的可扩展性。仿真结果表明，该算法在PU受益、交易成功率、频谱利用率、网络吞吐量等方面显著优于其他几种较新的频谱共享算法。

贝叶斯模型；分布式方式；双向拍卖；认知无线电网络；频谱共享

0　引　言

由于无线电频谱的限制，通信网络面临频谱资源稀缺的问题，另一方面，许多许可频谱仍然长时间［1］未被占用。认知无线电（CR）可提高频谱资源利用率，在CRs中，部分用户可以智能地监控环境并在分配的频段都处于闲置状态时能够与许可用户共享频谱，通过许可用户（PUs即主用户）和未经许可的用户（SUs即次级用户）［2］之间的频谱共享实现CR网络频谱利用率的增加。

本文提出了一种基于双向拍卖融合贝叶斯推理模型的频谱共享算法，假设主用户和次级用户是自相关博弈玩家，他们为了达到最大化收益的目的而做出决策。本文算法自适应地响应不断变化的系统环境和玩家数量，具有良好的可扩展性，为了达成有效拍卖共识，本文算法适用于现实世界CR系统的操作，同时能尽可能高的保持频谱效率。

1　相关研究

学者们提出了许多用于CRs中有效频谱共享的拍卖博弈模型［3］，可更为有效地解决有限稀有资源分配问题。拍卖博弈模型通过减少未分配的频段数量可以提供更好的频谱共享，提高了整体资源利用率［4］。

文献［5］中的战略型频谱拍卖（SPSA）方案是一种真实且计算高效的频谱拍卖，支持类似eBay的动态频谱市场，该方案允许无线用户获取并根据要求支付频谱。此外，SPSA方案通过分配频谱给最重视它的投标人能使频谱所有者利润最大化。然而，SPSA方案仅考虑购买者的单向频谱拍卖，该SPSA方案可直接扩展为真实双向频谱拍卖（TDSA）方案［6］，TDSA方案支持真实双向频谱拍卖，其中多方可根据个性化需求交易频谱，该方案运用一种新的赢家确定和定价机制选择获胜买家和卖家，然而TDSA方案只假定简单的频谱需求/请求格式。文献［7］中重复拍卖贝叶斯学习（RABL）方案建模为一个重复拍卖博弈，该方案研究了由监控成本和访问成本构成的认知无线电系统的频谱接入问题。因此，重复拍卖模式已用于最大限度地权衡访问频段的收益和成本。此外，为了设计一种具有不完整信息的方案，构建了基于狄利克雷过程的非参数信念更新算法。文献［8］中的自适应拍卖频谱共享（AASS）方案是一种基于非合作博弈模型描述PUs和SUs之间竞争力的拍卖，该方案采用Hackner效用函数定义二次用户的频谱出价。此外，AASS方案为每个PU的成本函数提出了一种动态更新算法，这有助于在动态频谱共享博弈的每个阶段PUs 从SUs实现更多的要求。文献［9］中的基于双向拍卖频谱共享（DASS）方案是一种基于动态频谱共享方案的双向拍卖，该方案允许免费频段在运营商之间交易，以提高频谱利用率，DASS方案使用自适应调节投标/询问策略研究实际的无线通信模型。

上述方案存在的主要问题有：首先，这些方案依赖于高复杂性和额外开销，无法在现实的系统操作中实施，因此仅限于较小的网络模型；其次，现有的方案不能自适应估计当前网络条件，在动态网络环境中可能造成潜在的错误决策；再次，这些方案有一些固定的系统参数操作网络系统，而在动态的网络环境中，操作现实世界的网络系统是不恰当的方法。受到上述讨论的启发，本文提出了一种新的CR频谱共享方案，将其设计为一个重复贝叶斯拍卖博弈。

2　提出的频谱共享算法

2.1博弈模型

博弈理论在无线网络中可应用于资源分配［10］，然而传统的博弈模型假设任意玩家需要的所有信息都完全已知，这并不符合现实情况。基于此，传统博弈模型不能直接应用于实际网络运营，文献［11］引入了贝叶斯博弈模型，该模型放宽了所有信息完全已知的假设，可以用于预测不确定性结果。

本文采用贝叶斯博弈方法解决CR系统中频谱共享问题，贝叶斯模型由一组玩家、一组动作、玩家类型和每个玩家的效用函数等组成［12］，提出的贝叶斯拍卖博弈如下：

玩家：CR系统中PUs和SUs，N=｛1，2，…，N｝和M=｛1，2，…，M｝分别表示PU集合和SU集合，PUi∈N运行在频带 Bi上，其与PUs其他的频带不重叠，即Bi⋂Bk=∅，∀i，k∈N。

动作集：任何PUi都具有所有可能报价的集合，是预计出售Bi频段的价格。任何S Uj都具有所有可能出价的集合，这是SUi可以支付的价格。

玩家类型：玩家的类型是一个概率分布，用来表达有关博弈玩家不确定或未知信息的概念，类型独立且在重复拍卖阶段动态变化，每个玩家完全知道自己的类型，而不知道其他玩家的类型，因此概率分布用于假设其他玩家的类型。

效用函数：效用函数可量化玩家从特定结果获得的满意度，PUs的效用函数代表货币收益（即频谱交易收入），对于SUs，拍卖价格越高，效益越低，因此SUs的效用函数定义为PUs的保留效用，如果PUs或SUs频段交易失败，该收益将保持0。

本文算法可归结为一种重复博弈［13］，该算法将时间轴划分为等长度间隔time_period（即Pt，t=0，1，2，…）。

2.2双向拍卖协议

传统的拍卖主要涉及一个拍卖商（卖方）和多个投标人（买家），该结构称为单向拍卖，而在频谱共享的拍卖场景中，存在几个买家和卖家对频段进行投标（即愿意支付的价格）及报价（即预期的销售价格）的情况，该情况下的拍卖模式设计为多对多的双向拍卖结构。

模型中的系统操作员定义为拍卖商，负责定价和交易频段。N中PUs可以是卖方，卖家可以报价给拍卖商，以显示其在价格上的偏好，M中SUs可以是投标人，投标人投标购买频段。每个time_period，玩家之间的频谱拍卖（即PUs和SUs）周期性运行，对于每个拍卖阶段，买卖双方基于其效用函数估计频段价值，当所有的报价和出价送到拍卖商之后，拍卖商设置频谱共享交易价格，并决定哪个投标人从哪个卖家获得频段。采用普雷斯顿-迈克菲双向拍卖（Preston-McAfee Double Auction，PMDA）协议的基本概念决定商品价格，在每一轮拍卖结束后，拍卖商收集所有有关报价和出价的信息，并通过分类和匹配技术［14］决定交易价格，然后拍卖商对所有玩家宣布决定的商品价格，因此，玩家学习CR系统中当前频谱共享条件，SUs（即投标人）获得所需频段，在接下来的一轮拍卖不会提交新出价，如果一些SUs竞标频段失败，他们将提交新的出价给拍卖商，同时，如果一些PUs没有售出自己的频段，他们在下次拍卖时也将提交新的报价。因此，在每一轮拍卖中，剩下的玩家自适应地调整自己的价格，这种动态的拍卖程序依次重复每一个time_period（即串行拍卖），以达成有效拍卖共识。

2.3贝叶斯推理和学习

贝叶斯博弈模型中，玩家学习修改自己的先验知识并自适应地调整策略。该方法并不假定玩家总是根据完整信息作出最佳决策，贝叶斯博弈的过程中，玩家有机会重新考虑目前的策略和应对以最大化期望收益，因此它提供了真实世界环境下更现实的模型。

玩家对频谱交易的渴望度强烈影响玩家的出价方案，通常情况下，玩家不知道其他玩家的愿望，但它实际上隐藏在每一轮拍卖中拍卖商的交易价格中。为了提交新的买价和卖价，买卖双方推断出下一轮交易价，这称为拍卖商类型。在每一轮拍卖中，玩家可以通过拍卖商的建议了解到别人的出价信息，基于该推论，每个玩家都可以为下一次拍卖做出更好的价格决策。

贝叶斯学习方法用来推断他人的渴望水平，根据贝叶斯定理和更新规则，贝叶斯推理公式［13］如下所示：

基于贝叶斯学习方法，开发每个玩家的价格调整过程，为了推断出下一轮交易价格，定义两个参数：拍卖商的让步比CRa和渴望水平η，它们用于贝叶斯推理公式中的假说，CRa估算如下：

式中：TP［t］，TP［t-1］分别表示第t次和第（t-1）次博弈阶段的交易价格，如果CRa（t）是负值，则意味着拍卖商增加了交易价格。拍卖商第t个博弈阶段的渴望水平表示为η（t），η（t）值越高，对应于进行光谱段交易的愿望越强烈。假定η值范围固定在-0.5～0.5之间，且均匀地分成10个间隔，η值是离散集合的一个元素，即η∈｛η0=-0.5，η1=-0.4，…，η9=0.4，η10=0.5｝。

P（CRa（t）|ηi（t））为给定拍卖商渴望水平ηi（t）下拍卖商的让步比，P（CRa（t）|ηi（t））越高，在给定期望值η（t）时，拍卖商的让步比更可能是CRa（t）。本文假设概率密度函数P（CRa（t）|ηi（t））服从正态分布［15］：

式中：θ=（1-CRp（t））×ηi（t），CRp（t）为玩家自己的拍卖让步比，平均值 μ和标准差σ产生不同的正态密度曲线，每个玩家有不同的 μ值和σ值，使用式（3）定义另一个条件概率P（ηk（t）|CRa（t）），拍卖商在给定CRa（t）条件下的渴望水平ηk（t），根据贝叶斯更新规则，该P（ηk（t）|CRa（t））值如下：

基于Pt（ηk（t）|CRa（t）），Pt（ηk（t））值为：

式中：ηk=｛η0，η1，η2，…，η10｝。

根据Pt（ηk（t））概率分布更新，当前拍卖人的愿望水平ηe可估计如下：

为了获得更精确的ηe值，贝叶斯推理过程重复迭代每一time_period，玩家持续监视当前的拍卖情况，以分布式方式决定自己的策略，最后，卖家和投标人可为下一轮拍卖调整自己的报价（Oft+1）和投标（Bit+1）：

式中T_Pt为已公布的当前拍卖的交易价格（即第t个博弈阶段）。

2.4本文算法的主要步骤

通过使用贝叶斯博弈模型为CR系统设计了一个新的频谱共享方案。提出的方案中，PUs和SUs（即博弈玩家）自适应地选择自己的拍卖价格分享频段。基于反馈学习过程，玩家可以捕捉如何调整自己的价格策略，为达成共识，该过程制定为重复拍卖模型。每一轮拍卖结束后，玩家定期检查目前的交易价格，并以完全分布式的方式迭代调整价格，因此玩家的数量增加时计算复杂度不会显著增加，这种交互式反馈过程持续进行，直到达成共识。提出的频谱共享算法的流程图如图1所示，主要步骤如下：

步骤1：初始迭代（t=0），每个拍卖商渴望水平Pt（ηk）的初始概率为均匀分布（Pt（ηk）=，∀i，其中|L|是η时间间隔的总数）。

步骤2：每次拍卖阶段，频谱卖家i∈N=｛1，2，…，N｝和频谱买家 j∈M=｛1，2，…，M｝发送报价oi和出价bj给拍卖商。

步骤3：拍卖商收集所有报价｛o1，o2，…，on｝和出价｛b1，b2，…，bm｝，然后按递减排序报价，按升序排序出价。

式中π和σ为上述定义的顺序统计排列。

步 骤 4：拍 卖 商 发 现k，使 得bπ（k）≥oσ（k）且bπ（k+1）

步骤5：卖家提供的价格比T_P低，买家出价高于T_P，以T_P价格成功交易频段。

步骤6：拍卖商宣布目前T_P，并发送拒绝消息给当前一轮拍卖交易频段都不成功的卖家和投标人。

步骤7：以分布式方式，交易失败的卖家和投标人通过式（2）～式（7）动态调整拍卖价格。

步骤8：如果至少有一个卖方、一个投标人提交新的报价和出价，则转到步骤3进行下一轮拍卖，该迭代反馈过程一直持续到卖家和投标人达成共识，否则，进入终止步骤。

终止：拍卖博弈处理时间暂时结束，而CR系统持续自我监控，当新的频谱共享要求（即报价和出价）到达，它可以重新触发频谱共享算法。

图1　提出的频谱共享算法的流程图

3　仿真实验

进行仿真实验评估本文算法的性能，将本文算法与其他现有方案的性能做比较，并确认了本文算法的性能优势，为了确保该模型充分通用且在真实世界有效，假设如下：

（1）新的应用程序请求服务生成过程服从速率为λ（服务/秒）的泊松分布，提供的负载变化范围从0～3.0；

（2）CR系统的总频谱容量为5 Mb/s；

（3）基于50次模拟运行获得的结果，系统性能测量值绘制为每秒提供负载的函数；

（4）N中PU总数为30，M中SU总数为15；

（5）通过模拟获得的性能标准为PUs的收益、交易成功概率、频谱利用率、系统吞吐量、SUs请求阻塞概率、平均每轮拍卖次数等；

（6）频谱利用率定义为归一化的频谱效率，该值基于网络传输数据量进行测量；

（7）PUs的收益为频谱共享总价格；

（8）网络吞吐量为归一化值，为成功提供服务数据量与总数据量比值；

（9）为了表示各种多媒体应用，假设有四个不同的通信类型，基于连接的持续时间、频谱需求和QoS要求，它们以相同的概率生成；

（10）对于不同的多媒体运用，应用程序服务的持续时间服从不同均值的指数分布。

对于多个应用程序，每个服务具有不同的流量特性，为了模拟真实的网络并进行公平的比较，本文使用现实模拟模型中给定的应用类型、特性和系统参数。表1为模拟中使用的多媒体应用程序类型和系统参数。

表1　模拟实验中使用的应用程序和系统参数

将本文算法与三个现有方案：RABL方案［1］，AASS方案［6］，DASS方案［7］的性能进行比较。

图2显示了所有方案的PUs总收益，从主用户角度看，收益是一个非常重要的因素，结果表明，应用程序请求率非常低（k<0.4）时，所有方案收入几乎相同。而当请求速率增加时，本文算法的PUs收益比其他方案更好。

图2 PUs的收益

图3给出了SUs服务阻塞率方面的性能比较，从次级用户的角度来看，服务阻塞概率是一个关键问题。由于适应性共享机制，本文提出的方案可避免频谱浪费，在各种流量负荷强度下，本文提出的方案可以提供比其他方案更低的服务阻塞率，这在实际网络运营中非常有用。

图3　SUs服务阻塞概率

图4是系统吞吐量的比较，一旦应用程序服务完成，该服务的总传输速率即为系统的吞吐量。在服务连接中间没有增益累计的拒绝或终止服务，当服务请求速率增加时，拒绝服务的数量增加，则CR系统的吞吐量降低。基于自适应频谱共享策略，本文算法比其他方案更好地提高了系统的吞吐量。

图4　CR系统的吞吐量

图5显示了各种方案的频谱利用率，为了最大化系统性能，频谱利用率是一个重要的性能指标，所有的方案都有类似的趋势，而在各种请求速率下，本文提出的方案的频谱利用率比其他方案更好。

图5　频谱利用率

图6比较了各种方案中交易成功概率方面的性能。在不同系统负载情况下，本文算法比其他方案具有更好的成功概率，这确保本文算法能够提供一个有效的拍卖机制以共享频谱资源。

图6　交易成功概率

图7给出了各种方案平均拍卖轮数，拍卖轮数是指每轮拍卖频谱交易的平均数量，所有方案趋势类似，然而，基于贝叶斯学习过程的智能方法可以使拍卖模式更加适应当前的系统状况，因此本文算法可以比其他方案保持较低的拍卖轮数。

图7　平均拍卖轮数

从图2～图7的模拟结果可以看出，在一般情况下，本文算法在多样化系统负荷强度下比其他现有算法更好。本文算法始终监视当前系统状态，且灵活度高、适应性强，能够感应到动态变化的系统环境，有显著的性能改进和更好的系统收益。因此，本文算法可以保持均衡的系统性能。

4　结　语

本文提出了一种新的频谱共享算法，将其设计为一种重复贝叶斯拍卖博弈，在不具有完整信息的情况下，PUs和SUs通过贝叶斯学习过程自适应决定报价或出价。拍卖过程周期性进行，直到达成共识。由于自相关特性，价格调整决策以完全分布式方式进行，在现实世界系统操作中，该分布式控制方式是最终实现的适应方法。本文算法具有较好的适应性、可行性和有效性，能平衡系统的性能。仿真结果表明，本文算法在PU受益、交易成功率、频谱利用率、网络吞吐量等方面显著优于现有方案。

本文算法可在无线开放存取研究平台上对资源利用率要求较高的网络应用程序进行测试，未来工作可通过研究噪声控制信道中的误差修正技术提高认知无线电网络的系统性能。

［1］邱晶，周正.认知无线电网络中的分布式动态频谱共享［J］.北京邮电大学学报，2009，32（1）：69-72.

［2］LID，XU Y，LIU J，et al.A market game for dynamic multiband sharing in cognitive radio networks［C］//2010 IEEE International Conference on Communications.Cape Town：IEEE，2010：1-5.

［3］王钦辉，叶保留，田宇，等.认知无线电网络中频谱分配算法［J］.电子学报，2012，40（1）：147-154.

［4］刘甲.认知无线传感器网络中频谱共享技术的研究［D］.北京：北京邮电大学，2013.

［5］WU F，VAIDYA N.A strategy-proof radio spectrum auction mechanism in noncooperative wireless networks［J］.IEEE transactions on mobile computing，2013，12（5）：885-894.

［6］黄河，孙玉娥，陈志立，等.完全竞争均衡的频谱双向拍卖机制研究［J］.计算机研究与发展，2014，51（3）：479-490.

［7］张丽影，曾志文，陈志刚，等.认知无线网络中基于约束算子的二进制粒子群频谱分配算法［J］.小型微型计算机系统，2013，34（6）：1226-1229.

［8］LOUIE R H Y，MCKAY M R，CHEN Y.Multiple-antenna signal detection in cognitive radio networks with multiple primary user signals［C］//2014 IEEE International Conference on Communications.Sydney：IEEE，2014：4951-4956.

［9］WANG S G，XU P，XU X H，et al.TODA：truthful online double auction for spectrumallocation in wireless networks ［C］//2010 IEEE Symposium on New Frontiers in Dynamic Spectrum.Singapore：IEEE，2010：1-10.

［10］齐丽娜，房志强.一种改进的基于动态贝叶斯博弈的主用户频谱策略［J］.南京邮电大学学报（自然科学版），2013，33（5）：1-6.

［11］王臣昊，杨震，肖小潮.基于优化贝叶斯压缩感知算法的频谱检测［J］.信号处理，2012，28（5）：750-756.

［12］HAN Z，ZHENG R，POOR H V.Repeated auctions with Bayesian nonparametric learning for spectrum access in cognitive radio networks［J］.IEEE transactions on wireless communications，2011，10（3）：890-900.

［13］AKKARAJITSAKUL K，HOSSAIN E，NIYATO D.Distributed resource allocation in wireless networks under uncertainty and application of Bayesian game［J］.IEEE communications magazine，2011，49（8）：120-127.

［14］李士涛.认知无线电网络中的动态信道分配技术研究［D］.重庆：重庆大学，2014.

［15］GARG S K，VENUGOPAL S，BROBERG J，et al.Double auction-inspired meta-scheduling of parallel applications on global grids［J］.Journal of parallel and distributed computing，2013，73（4）：450-464.

Cognitive radio network spectrum sharing schem e for doub le auction com bining Bayesian m odel

DAIDong1，WANG Guo1，WANG Lei2
（1.Department of Computer Science and Technology，Henan Institute of Technology，Xinxiang 453003，China；
2.College of Economic Information Engineering，Southwestern University of Finance and Economics，Chengdu 610074，China）

Since the spectrum resource in radio networks is lim ited and its utilization is low，a spectrum sharing algorithm for double auction combining Bayesian inferencemodel is proposed.Firstly，the primary users and the secondary users adaptively select their auction prices to share the spectrum bands.And then，based on feedback learning process，the players capture their adjustable price strategies.Finally，the auction process is repeated until the consensus is reached.The algorithm adopts Bayesian inference technique，which can adaptively response to the constantly changing system environment and players′quantity.It has better scalability.The simulation results show that the proposed algorithm is superior to several other advanced spectrum sharing algorithms in the aspects of PU benefit，trade success rate，spectrum efficiency and network throughput.

Bayesian model；distributed mode；double auction；cognitive radio network；spectrum sharing

TN926-34；TP393

A

1004-373X（2016）11-0024-06

10.16652/j.issn.1004-373x.2016.11.007

2015-09-18

国家自然科学基金重大项目（91218301）；河南省高等学校重点科研项目（16A520048）

戴冬（1978—），女，河南信阳人，硕士，讲师。研究方向为无线网络、智能算法等。

王果（1977—），男，河南南阳人，硕士，副教授。研究方向为无线网络、智能算法等。

王磊（1978—），男，河南信阳人，博士，硕士生导师，副教授。研究方向为无线网络、智能算法等。