基于单频段多赢家拍卖的动态频谱分配

张文柱，王凌云

（西安电子科技大学 综合业务网理论和关键技术国家重点实验室，陕西 西安 710071）

1 引言

随着科学技术的不断进步以及人们对于通信要求的不断提高，无线通信技术的种类越来越多，使用这些技术进行无线通信的用户也越来越多，使得无线频谱日益成为紧缺的资源。传统的频谱管理体制限定某一频段内的频谱只有该频段的授权用户可以使用，造成某些频段的频谱利用率很低，存在大量频谱空洞[1]。认知无线电技术通过实时感知，在不干扰授权用户正常通信的前提下，允许认知用户动态接入授权用户的空闲频段，有效提高了频谱利用率，已成为当前无线通信领域的研究热点[2]。

基于竞价拍卖的频谱分配模型以其较少的信息需求和良好的分配效果被认为是解决认知无线电网络频谱分配问题的有效方法[3]。该领域已经产生了一系列研究成果，例如，文献[4]提出了一个实时频谱拍卖算法来实现对大规模拍卖的无冲突频谱分配，有效地提高了拍卖收益和频谱利用率；文献[5]运用渐进式博弈的方法，通过观察价格和QoS的变化，研究了授权用户与次级用户的相互影响；文献[6]提出了一个基于拍卖的频谱管理策略框架来同时满足4种拍卖参与者的要求；文献[7]提出了一个基于拍卖的Q学习算法，用于次级用户竞争有限的、时变的频谱机会。

已有的基于竞价拍卖的频谱分配方案在提高频谱分配效率上取得了较好的成效，但是仍然存在一些缺陷亟待解决。首先，多数文献没有重视频谱拍卖与传统的物品拍卖之间的区别。在物品拍卖中，一件物品最终只能被一个赢家所获得；然而频谱资源是干扰受限的，而不是数量受限的，也就是说，如果多个次级用户在地理位置上相距足够远，那么单个频段的频谱就可以同时被多个赢家所共同使用。其次，尽管少数文献，如文献[8]认识到了干扰受限的问题，但该文献所提出的算法复杂度偏高，可行性低，并且没有考虑到次级用户的自私性。

针对上述问题，作者提出了一种基于单频段多赢家拍卖的动态频谱分配算法，区别于传统的单频段单赢家拍卖算法，该算法使得相互之间无干扰或干扰足够小的多个次级用户可以同时使用同一信道进行通信。该算法复杂度低，并且能够获得较高的拍卖收益以及良好的抗共谋性能。

2 系统模型和问题描述

图1 认知无线电网络模型

考虑由一个频谱经纪人和N个次级用户组成的认知无线电网络，如图1所示。其中次级用户可以是任何装备有认知无线电技术的通信设备。授权用户在获得频谱使用权时缴纳了相应的费用，因此频谱的使用具有一定的成本，授权用户希望在成本价格之上以尽可能高的价格出租自己的空闲频段。而次级用户希望在自己的预期收益之下以尽可能低的价格租用空闲频段来满足自己的通信要求。

假设频谱经纪人现有M个单位的互不重叠且不可再分的空闲信道可以用来拍卖，且这些信道的性质（带宽、调制方式等）是完全相同的，即次级用户只关心有没有获得信道而不会关心获得的是哪一条信道。同时，假设每个次级用户在一个拍卖周期内只需使用一个空闲信道。为简便起见，先考虑M=1的情况，在每个拍卖周期T开始时，N个次级用户通过认知能力得到其对于频谱的估价v=[v1, v2,…,vN]，其中，vi为第i个次级用户的估价。然后，向频谱经纪人递交他们的报价b=[b1, b2,…,bN],bi≤vi，其中bi为第i个次级用户的报价。频谱经纪人需要在使系统效用最大化的前提下决定哪些用户竞标成功以及竞标成功用户的实际应付价格，即产生分配向量x=[x1, x2,…,xN],xi∈｛0,1｝和价格向量p=[p1, p2,…,pN],pi≥pc。其中，xi=1表示第i个次级用户竞标成功，反之，则失败；pi为第i个次级用户的实际应付价格，pc为每段频谱的成本价格或保留价格，系统效用定义为

系统效用表示一次拍卖过程中整个拍卖模型获得的总收益。系统效用越高，代表拍卖算法的频谱分配效率越高。

为了表示次级用户间的干扰情况，构造一个N×N的干扰矩阵C，Cij∈｛0,1｝，Cij=1表示第i个次级用户和第j个次级用户相互之间存在干扰，不能同时使用同一信道，反之，Cij=0则表示相互之间无干扰。

追求系统效用最大化的拍卖算法通过如下目标函数决定分配向量x：

当M＞1时，定义系统效用为

此时拍卖算法有如下目标函数：

其中，xm是第m个信道的分配向量，=1表示第i个次级用户竞标第m个信道成功，反之，则表示竞标失败。

式(4)问题的求解是一个NP-hard问题，用枚举法求解理论上能得到最优解。鉴于枚举法的计算复杂度是指数级的，当问题规模较大时，会因计算量过大而无法实现。因此，需要寻找一种快速简单的赢家判决算法。

另一方面，要求解式(4)的值，需要知道每个次级用户对频谱的真实估价vi，即令bi=vi。但是网络中的次级用户是自私的和理性的[9]，每个用户都设法使自己的利益最大化，如果可以获得更高的利益，它们会选择谎报估价。为了解决这一问题，传统的单频段单赢家拍卖模型中常用VCG(vickeryclarke-grove)机制[10]来进行价格判决。假设赢家判决所求得的最优分配向量为x*，那么其所对应的最优系统效用为=Uv(x*)。假设第i个次级用户竞标成功，定义v-i=[v1, v2,…,vi-1,vi+1,…,vN]，那么该次级用户的实际应付价格为

VCG机制具有占优策略激励兼容特性，最大限度地激励次级用户递交其真实估价，有效地确保了整个系统的公平性。但是对于本模型来说，VCG机制使得频谱经纪人的收益相当低，卖家收益过低会产生相当严重的转租共谋[11]，因此作者提出的拍卖算法对VCG机制进行了改进。

3 单频段多赢家拍卖算法

3.1 赢家判决阶段

贪婪算法是求解NP-hard问题的一种近似算法，它的优点是计算复杂度低、速度快，但是结果的优度不够理想。作者首先给出了综合考虑报价和干扰约束的贪婪准则，然后在原始贪婪算法的基础之上，增加了多重贪婪策略，通过增大解的搜索空间来弥补原始贪婪算法的不足，提高结果的优度。

一个单频段多赢家拍卖市场POBMW由一个七元组构成，POBMW={S, F, v, pc,C,Ri, Ai}，其中变量表示含义如下。

1) S={s1, s2,…,sN}是N个次级用户组成的集合，F={f1,f2,…,fM}是M个待拍卖信道组成的集合。

2) v=[v1, v2,…,vN]是次级用户的估价向量，pc是单个信道的成本价格。

3) C是干扰矩阵，Ri是第i个次级用户的干扰用户集。

4) Ai是第i个次级用户的可用信道集。初始化时，若vi＜pc，Ai=∅；若vi≥pc，Ai=F且所有信道优先级等级设为0。

具体的判决流程如下。

① 频谱经纪人广播出租信息，包括信道数目M、单个信道成本价格cp等。

② 次级用户向频谱经纪人递交竞价信息，包括估价iv、地理位置或邻节点等。

③ 频谱经纪人根据收集到的信息，构造干扰矩阵C，为每个次级用户分配集合iR和iA，并初始化。

④ 按照式(6)从次级用户集S中选出一个赢家ks：

为sk分配Ak中优先级最高的信道fm，若存在多个优先级相同的信道，则选择序号m最小的信道，若Ak=∅，则丢弃sk。

⑤ 更新次级用户集S：S=S-{sk}。

⑥ 更新每个次级用户si的可用信道集Ai：对比干扰矩阵C，若sk是si的干扰用户，则将fm从Ai中删除，若不是，则将Ai中fm的优先级提高一位。

⑦ 返回步骤④，直至S=∅。至此，得到贪婪算法的解：X={x1, x2,…,xM}。

⑧ 多重贪婪：从解X的每一个分量xm中随机选择r%的次级用户，连同被丢弃的次级用户，重新放入集合S中，并将它们上一次竞价成功所获得的信道从各自的可用信道集中删除，再次应用贪婪算法，即重复步骤④～步骤⑦，得到新的解Y。通过式(3)求得解X与Y所对应的系统效用，若新解Y的系统效用更高，则用新解代替原来的解。

⑨ 重复步骤⑧t次，得到最终优化解。

3.2 价格判决阶段

原始的VCG机制依次对每一个竞价成功的次级用户使用式(5)计算其应付价格，这种方法不适用于单个频段有多个赢家的拍卖模型。为此，作者将同时获得某一信道使用权的所有次级用户定义为一个虚拟竞价人，此人对信道的估价等于其内部所有次级用户估价的总和。对每个虚拟竞价人使用式(5)求出总的应付价格，再分解到单个次级用户上，即可求出完整的价格向量。映射到本模型中，设W={sn}为信道f1的赢家集合，即∀sn∈W,=1。W就是一个虚拟竞价人，其估价，对于信道f1而言，，代入到式(5)可得W的总的应付价格：

因此，序号为m的信道的价格向量mp可用如下方法求得。

①将前m个信道的所有赢家集合从系统中去除，通过一次赢家判决求出一个赢得拍卖的虚拟竞价人，根据式(7)，这个虚拟竞价人的总估价即为第m个信道的虚拟竞价人的总的应付价格。

②根据比例公平准则，通过式(8)求得第m个信道的每个赢家的实际应付价格ip。

4 性能分析

4.1 算法的复杂度

运用枚举法求式(4)时，由于每个xi都有0、1两种可能解，需要遍历2MN种情况，每种情况需要做MN-1次加法运算以计算对应的系统效用，最后需要做2MN次比较以找到最优的分配向量。所以枚举法总共需要做2MNMN次加法运算，其时间复杂度为Ο(2MNN)。

运用原始贪婪算法求解时，根据步骤④，先要做N次加法运算和N次除法运算得到式(6)中贪婪准则所要比较的值，然后做N-1次比较得到k值，做M次比较为sk分配信道，再由步骤⑦，需要循环求出N个k值，每次循环N的值都减1。所以贪婪算法总共需要做N次除法运算和N( N+1)/2+MN次加法运算，其时间复杂度为Ο(N2)。

运用多重贪婪算法求解时，步骤⑧需要重新求解大约r%×N个k值，循环t次，忽略与M或N无关的常数次运算，可以求得，多重贪婪算法仅比原始贪婪算法多出t×r%×N( r%×N-1)/2+tr%MN次加法运算，其时间复杂度仍为Ο(N2)。

可见，多重贪婪算法的时间复杂度仅略高于原始贪婪算法，但明显低于枚举法的时间复杂度，特别是当M和N较大时，该算法能够节约大量的拍卖交易时间。

4.2 抗共谋性能

本算法在价格判决阶段，对于每一个虚拟竞价人使用VCG机制计算支出，对于单个次级用户遵循比例公平准则分配收益，最大限度地激励虚拟竞价人和单个次级用户均递交其最高报价，即其真实估价，继承了VCG机制占优策略激励兼容特性的同时，避免了直接使用VCG机制时赢家应付价格过低可能会产生的转租共谋。同时，保留价格的设定抑制了共谋团体的低价策略，可以有效防止围标共谋的发生[12]。

5 算法仿真

仿真环境设定：在一个100 100×的矩形区域中，随机分布有一个频谱经纪人和N个次级用户。频谱经纪人拥有5个空闲信道等待拍卖，每个空闲信道的成本价格为15。每个次级用户的覆盖半径均为25，即如果2个次级用户的距离小于50，则认为它们互相干扰，次级用户对频谱的估价均匀分布在[10,30]之间。多重贪婪策略中每次移除50%的次级用户，重复10次。次级用户数N从10逐渐递增到30，在每个次级用户数下进行100轮次仿真。

图2比较了当次级用户数为20时，传统单频段单赢家 (OBOW, one-band one-winner) 算法、原始贪婪 (greedy) 算法及作者提出的单频段多赢家(OBMW, one-band multi-winner)算法3种算法的系统效用，通过50次仿真，模拟了50种网络拓扑结构。可以看出OBOW算法由于赢家数很少，系统效用相当低；OBMW算法的系统效用均要高于greedy算法，并且不会产生某一种网络拓扑环境下系统效用特别低的情况，说明经过优化的OBMW算法能更好地适应各种不同的网络拓扑。

图2 次级用户数为20时系统效用的比较

图3比较了不同次级用户数情况下3种算法的系统效用。可以看出，当次级用户数较少时，greedy算法和OBMW算法都能得到最优解，当用户数逐渐增多，2种算法的差值逐渐增大。实验结果表明，与greedy算法相比，OBMW算法得到的系统效用平均要高8%～12%。

图3 不同次级用户数情况下系统效用的比较

图4比较了不同次级用户数情况下3种算法的频谱分配效率，即实际系统效用与最优值的比值。可以看出，OBMW 算法的分配效率均要高于其他算法，并且分配效率不低于90%。

图4 不同次级用户数情况下频谱分配效率的比较

图5比较了空闲信道数分别为2、3、4，次级用户数分别为10、20的简单网络环境下OBMW算法的频谱分配效率。可以看出，空闲信道数越多，算法的频谱分配效率越高。

图5 不同空闲信道数情况下频谱分配效率的比较

图6比较了不同次级用户数情况下3种价格判决算法对应的频谱经纪人的收益。可以看出，如果直接将 VCG机制用于单频段多赢家拍卖模型中，频谱经纪人收益将特别小，甚至在很多情况下低于OBOW算法，而OBMW算法则能大幅度地提高卖家收益，满足拍卖要求。

图6 频谱经纪人的收益的比较

图7 可被转租的系统效用的比较

图7比较了不同次级用户数情况下可被转租的系统效用占实际系统效用的百分比，其中avg-VCG表示100轮次仿真结果的平均值，max-VCG表示100轮次仿真结果中的最大值。实验结果表明，如果直接将VCG机制用于单频段多赢家拍卖模型中，10%～20%的系统效用可能会被转租，最坏情况下甚至超过50%，而OBMW算法则具有更好的抗共谋性能，平均可转租率均小于10%。

6 结束语

提出了一种适用于认知无线网络的基于单频段多赢家拍卖的动态频谱分配算法。该算法在原始贪婪算法的基础上增加了多重贪婪策略，以较低的计算复杂度得到了优化的解；提出了虚拟竞价人概念，将VCG机制很好地应用于单频段多赢家拍卖模型中，提高了卖家的收益，抑制共谋的发生。仿真结果表明，该算法的频谱分配效率接近最优分配效率，提高了拍卖的经济收益，有效解决了认知无线网络中的动态频谱分配问题。

[1] MITOLA J. Cognitive radio: making software radios more personal[J].IEEE Personal Communications, 1999, 6(4):13-18.

[2] AKYILDIZ I F, LEE W Y, VURAN M C, et al. A survey on spectrum management in cognitive radio networks[J]. IEEE Communications Magazine, 2008,46(4):40-48.

[3] ZHOU X, GANDHI S, SURI S, et al. eBay in the sky: strategy-proof wireless spectrum auctions[A]. Proceedings of the 14th ACM International Conference on Mobile Computing and Networking[C]. New York, USA, 2008. 2-13.

[4] GANDHI S, BURAGOHAIN C, CAO L, et al. A general framework for wireless spectrum auctions[A]. The 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks[C].Dublin, Ireland, 2007. 22-33.

[5] NIYATO D, HOSSAIN E, HAN Z. Dynamics of multiple-seller and multiple-buyer spectrum trading in cognitive radio networks: a game-theoretic modeling approach[J]. IEEE Transactions on Mobile Computing, 2009, 8(8):1009-1022.

[6] CHANG H B, CHEN K C. Auction-based spectrum management of cognitive radio networks[J]. IEEE Transactions on Vehicular Technology, 2010, 59(4):1923-1935.

[7] TENG Y L, ZHANG Y, NIU F. et al. Reinforcement learning based auction algorithm for dynamic spectrum access in cognitive radio networks[A]. 2010 IEEE 72nd Vehicular Technology Conference Fall[C]. Ottawa, Canada, 2010. 1-5.

[8] CHEN L, IELLAMO S, COUPECHOUX M. An auction framework for spectrum allocation with interference constraint in cognitive radio networks[A]. 2010 Proceedings IEEE INFOCOM[C]. San Diego,USA, 2010. 1-9.

[9] 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.

[10] 刘志新, 申妍燕, 关新平. 一种基于 VCG 拍卖的分布式网络资源分配机制[J]. 电子学报, 2010, 38(8):1929-1934.LIU Z X, SHEN Y Y, GUAN X P. A VCG auction based distributed mechanism for network resource allocation[J]. Acta Electronica Sinica,2010, 38(8):1929-1934.

[11] WU Y L, WANG B B, LIU K, et al. A multi-winner cognitive spectrum auction framework with collusion resistant mechanisms[A].DySPAN 2008[C]. Chicago, USA, 2008. 1-9.

[12] HUANG S H, LIU X, DING Z. Optimal sensing-transmission structure for dynamic spectrum access[A]. IEEE INFOCOM 2009[C]. Rio de Janeiro, Brazil, 2009. 2295-2303.