基于连续双向拍卖的频谱分配算法研究

刘觉夫，王华锋，杨 丽

（华东交通大学 信息工程学院，江西 南昌330013）

0 引 言

在无线网络中，由于频谱和带宽等无线网络资源极其有限，根据FCC的频谱策略任务工作报告显示，已经分配频谱的利用率在15%到85%之间波动，存在开放频谱资源匮乏和专用授权频谱利用率低下的矛盾，因此对频谱等网络资源进行高效地分配及管理是解决频谱匮乏问题的重要手段。根据频谱分配的现状，不同区域的部分机构拥有不同带宽的频谱并且为认知用户提供通信服务，因此，对多个频谱服务提供者和多认知用户共存环境下的频谱资源进行简单、高效地分配与管理和提高动态频谱访问的可靠性就成为了一个关键问题。市场机制是解决资源竞争问题的有效方法，多位学者针对频谱分配的市场机制进行了研究，如刘英挺等人应用连续双向拍卖和模糊推理建立了分配制模型［1］，吴琼等人对竞价模型的频谱分配及其应用进行了深入研究［2］。现有认知无线网频谱分配算法中，多个频谱服务提供者和多认知用户环境下都存在用户间关系复杂，算法时间复杂度过高，频谱分配方式不够灵活的问题。针对上述问题利用市场交易机制设计了动态的频谱分配算法。市场交易机制简化了复杂的多对多关系，可以使频谱分配算法实现较低的时间复杂度，加快收敛速度。

1 连续双向拍卖与价格行为

现实世界的各个领域里都存在各种各样的多对多的竞争现象，交易市场就是这种现象的直观例子。连续双向拍卖是交易市场中各方实现其交易行为的一种有效机制。交易市场将各方的竞争行为转化为各自的价格行为，价格信息体现了各方决策行为的结果。根据经济学理论，各方的竞争关系是一种供需关系，解决供需关系的最有效途径就是交易市场。连续双向拍卖作为一个多边的讨价还价过程，能够快速地收敛到竞争均衡，从而产生很高的价格发现效率。在这系统中，参与者在市场中的行为完全体现为其价格行为，所有参与者的价格行为构成市场。参与者的价格行为就是其决策的结果，参与者的决策只需要关心市场价格和自身收益这两方面的因素。

连续双向拍卖的市场交易机制是基于指令流的撮合成交机制，其指令分为限价指令和市价指令，这样在交易市场过程当指令稀少时就有可能产生异常的成交价格。利用连续双向拍卖的进行建模时就要对交易机制进行重新设计，避免产生异常的成交价格，给频谱交易者造成损失。

本文设定：

（1）在建模时频谱提供者为卖方，其收益函数为sell－Pay，频谱使用者为买方，其收益函数用buyerPay表示，交易双方的角色固定；

（2）一个用户 （买方）一次只能访问一条信道，频谱提供者 （卖方）可以同时提供多条信道；

（3）网络中用户之间是互相干扰的；

（4）用户专指在无线网络环境中的一对发射机和接收机，干扰来自其他用户的频谱使用；

（5）信道作为交易的商品被认为是同质的。

2 系统模型

考虑如图1所示的情况：无线网络中存在N个认知结点用户组和M个由不同频谱出售商提供的可用无线频谱带。每个用户均可访问网络中任何一个空闲频谱段，即频谱具有可以交易商品的同质性。

将每个组看作一个整体，在双方之间设置STM （spectrum trade management），这个模型就是简易的频谱交易市场。

可以在多个频谱供应商和多个频谱使用者之间使用的无线频谱访问形式，是一种必然的趋势。用频谱市场的方式来解决这一问题的核心就是交易机制的设计和交易双方的报价策略。

连续双向拍卖交易机制如图2所示。

图1 分布式频谱访问

图2 连续双向拍卖交易机制

STM充当拍卖人的角色，通过接收并执行双方提供的交易指令，并对其进行撮合成交来完成交易。指令分为4种：限价卖出指令、市价卖出指令、现价买入指令、市价买入指令。市价指令的优先级别高于限价指令，指令薄上的其中一方的没有限价指令时，禁止另一方提交市价指令。撮合成交的具体方式：以买入指令为例，STM维护一份指令薄，对新到达的买入指令进行判断，对于市价指令按照最低卖出价格成交相应数量，如果最低卖出价格指令的数量不够，则向上提高一档，直到提高的档次达到买入指令设置的最大值或买入指令完全成交或者指令薄上的卖出限价指令项目为空。对于限价买入指令，按照价格优先，时间优先的原则进行处理，如果价格高于最低卖出价格，则按照最低卖出价格成交相应数量，如果最低卖出价格的数量不够，则向上提高一档，直到当前指令全部成交或者指令薄上低于当前执行指令价格的限价卖出指令为空；如果撮合成交完成后，仍未完全成交，则剩余部分插入指令薄的限价买入指令的有序队列。

频谱使用者 （买方）的报价策略，频谱使用者通过接收STM广播价格消息结合自身的频谱使用收益进行决策报价，并向STM发送交易指令。频谱提供者 （卖方）的报价策略，频谱提供者通过接收STM广播价格消息结合自身的频谱提供成本进行决策报价，并向STM发送交易指令。

3 基于连续双向拍卖的频谱分配算法

在具体模型中将i个频谱提供者记为集合 M｛m1，m2…mi｝将j个频谱使用者记为集合 N｛n1，n2，nj｝。STM 通过接收并处理两个集合的元素递交的指令，确定集合间元素的关系，这是一种松散，灵活的关系，双方通过这种方式都可以随时递交自己的指令。

3.1 效用函数的设计

报价策略和交易者的效用函数密切相关，选择一个合适的效用函数将对认知用户价格行为产生本质的影响。假定成交价格的分布服从正太分布，频谱提供者i提供频谱k的收益效用函数gi（k，p，t），其中k代表频谱的数量，p表示i对当前要出售频谱的报价，t表示等待的时间，i的收益函数gi（k，p，t）＝f（pi）piki－αki－βt，其中f（pi）＝为报价时p可以成交的概率密度函数，α，β为常数，报价p和预期收益ξ直接相关。频谱使用者j使用频谱k的收益函数其中δ、φ为常数，报价p和预期收益η直接相关。

3.2 算法描述

4 仿真实验与性能分析

应用本文分配算法，使用MatLab 7平台进行仿真。仿真的无线网络环境为：在半径为1km的环境内，均匀分布频谱供应商500个，用户500个，每次交易的频谱为一个单位，用户的需求符合泊松分布。

4.1 算法时间复杂度收敛情况

根据伪代码的描述可以得出算法的时间复杂度为Οn（）1.3。图3为基于连续双向拍卖的频谱分配算法和双向拍卖的算法的收敛情况。横坐标表示时间，纵坐标表示价格，可以看出，在执行了约20个算法周期后，双方的成交价格趋于稳定，系统达到平衡状态，验证了算法的收敛性。

图3 算法的收敛情况

4.2 交易双方的收益情况

如图4所示，频谱供应商的收益和用户的收益呈现一定的负相关性，这符合双方价格竞争的过程。频谱供应商的收益与成交价格以及成交量相关，随价格升高而增加，随成交量的增加而增加，但是成交量和价格之间没有确定的关系。成交价格和成交量是对双方市场行为的记录，市场双方未来的行为和其历史记录并没有必然的关系，只是对当下供需关系的直观反映。频谱用户的收益显然和成交的价格负相关，随着价格的升高，频谱用户收益减少，随着价格的降低频谱用户的收益增加。从仿真图中可以看出，当成交价格收敛到一个稳定范围内时，双方的收益也趋于稳定。

图4 双方的收益情况

4.3 系统吞吐量

如图5所示，系统的吞吐量可以用单位时间内的成交量来表示。用TP来表示吞吐量，本算法中的吞吐量可以表示为其pi代表单位时间内的每一笔的成交数量，n表示时间段内总共成交的笔数。成交量的大小直接反应当前系统的吞吐量，同时成交量也是市场交易活跃度的实际反应，显然成交量大的交易活跃，说明用户需求旺盛，同时资源也充足。成交量小的交易冷清，说明价格不合理、用户需求均较少，或者频谱供应匮乏。

图5 系统的吞吐量

5 结束语

本文基于认知无线网络环境，运用连续双向拍卖的撮合成交机制，提出了基于连续双向拍卖的自适应负载频谱分配算法。该算法应用市场供需机制来描述频谱的分配过程，将复杂的分配过程转化成频谱供应商和用户双方的市场行为。通过供需双方价格的有效竞争来完成频谱分配过程，降低了算法的复杂度。仿真结果显示，算法可以在较短的时间内达到均衡，实现频谱的有效分配，并且保证了双方的收益。本文的算法可以有效的进行频谱分配，但是市场化的方法仅仅将频谱看作同质化的商品，没有考虑相同价格条件下，频谱的功率控制、干扰等问题，而现实场景中，发射功率、干扰等因数对网络稳定性、网络吞吐量、通信质量有重要的影响。如何对无价格差异的分配结果进行优化已达合理控制功率，减少干扰需要进一步的研究。

［1］WU Qiong，XIAN Yongju，XU Changbiao.Handover spectrum allocation based on bidding model in cognitive networks［J］.Computer Engineering，2011，37 （12）：71－73 （in Chinese）.［吴琼，鲜永菊，徐昌彪.认知网络中基于竞价模型的切换频谱分配 ［J］.计算机工程，2011，37 （12）：71－73.］

［2］LIU Yingting，CAI Jueping，LI Zan.Dynamic spectrum allocation based on continuous double auctions in cognitive radio networks ［J］.Journal of Xidian University，2009，36 （6）：997－1002 （in Chinese）. ［刘英挺，蔡觉平，李赞.认知网络中基于连续双向拍卖的动态频谱分配 ［J］.西安电子科技大学学报：自然科学版，2009，36 （6）：997－1002.］

［3］WENG Chuliang，LU Xinda.A double auction method for resource allocation on computational grids ［J］.Chinese Journal of Computers，2006，36 （6）：1004－1009 （in Chinese）. ［翁楚良，陆鑫达.一种基于双向拍卖机制的计算网格资源分配方法 ［J］.计算机学报，2006，36 （6）：1004－1009.］

［4］Rosenthal R.A class of games possessing pure－strategy Nash equilibria ［J］.International Journal of Game Theory，1973，2 （1）：65－67.

［5］Fabrikant A，Papadimitriou C，Talwar K.The complexity of pure Nash eauilibria ［C］／／The 36th Annual ACM Symposium on Theory of Computing，2004：604－612.

［6］Chen L.A distributed access point selection algorithm based on no－regret learning for wireless access networks ［C］／／IEEE Vehicular Technology Conference，2010：1－5.

［7］Ercetin O.Association games in IEEE 802.11wireless local area networks ［J］.IEEE Transactions on Wireless Communications，2008，7 （12）：5136－5143.

［8］Altman E，Kumar A，Hayel Y.A potential game approach for uplink resource allocation in a multichannel wireless access network ［C］／／Pisa，Italy：Proceedings of the Fourth International ICST Confere－nce in Performance Evaluation Methodologies and Tools，2009.

［9］Liu Mingyan，Ahmad S H A，Wu Yunnan.Congestion games with resource reuse and applications in spectrum sharing［C ］／／Istanbul， Turkey： Proceedings of International Conference on Game Theory for Networks，2009：171－179.

［10］Sahand Ahmad，Cem Tekin，Liu Mingyan，et al.Spectrum sharing as spatial congestion games ［J］.IEEE Transaction on Networking，2010.

［11］WANG Jinlong，WU Qihui，GONG Yuping，et al.Cognitive wireless networks ［M］.Beijing：China Machine Press，2010：100－120 （in Chinese）. ［王金龙，吴启辉，龚玉萍，等.认知无线网络 ［M］.北京：机械工业出版社，2010：100－120.］

［12］Saraydar C U，Mandayam N B，Goodman D J.Efficient po－wer control via pricing in wireless data networks ［J］.IEEE Transactions on Communications，2002，50 （2）：291－303.