基于分组拍卖的认知无线电频谱分配算法

陈浩雷，滕子铭，孙汇阳，张华

(1.东北电力大学电气工程学院，吉林 吉林132012；2.吉林大学通信工程学院，吉林 长春 130012；3.北京电子科技学院密码科学与技术系，北京 100070)

随着无线通信技术的发展，频谱资源变得越发紧张，目前无线网络主要采用的是固定频谱分配政策，频谱利用率低[1].如何提高现有频谱的利用率成为了急需解决的问题.在这种背景下，认知无线电技术[2]应运而生，这种技术可以在不影响主用户正常工作的情况下，允许次用户使用空闲频谱，从而提高频谱利用率.目前关于频谱分配主要有三种分别为：在频谱交易[3-5]基础上建立的基于拍卖的频谱分配算法[6]、基于图论的频谱分配算法[7-8]和基于博弈论的频谱分配[9-10].

国内外研究人员在频谱交易基础上构建了基于拍卖的频谱分配算法，其优点是可以提高主用户的经济收益激励主用户出售空闲频谱，同时次用户收益也可以得到保证.但次用户具有自私性，在频谱分配过程中总是以最大化自身收益为目标做出决策，导致频谱利用率低下.Wang等[11]将诚信概念引入频谱分配算法中，同时以最大化频谱利用率为目的进行研究，结果表明该算法提高了频谱利用率，但是没有考虑次用户间的干扰问题，影响了次用户的收益.文献[12]以最大化卖家收益为目的进行研究，提出一种估算求解方法，保证了卖家收益.但该算法未能有效抑制次用户的自私性，导致分配过程中用户存在虚假出价情况，降低了频谱利用率.文献[13]，保证次用户公平性，同时以最大化系统吞吐量进行研究.该算法假设主用户、次用户拥有固定的误码率，在传输速率基础上构建了收益函数，以次用户最大传输速率和为目标进行求解.虽然提高了系统吞吐量，但由于算法复杂度较高，需要经过较长周期才能达到纳什均衡.

本文针对频谱分配过程中用户自私性、次用户收益和频谱利用率的问题，提出一种在基于分组拍卖的频谱分配算法，有效抑制了频谱分配过程中次用户的自私性，同时提高了次用户收益和频谱利用率.

1 基于频谱拍卖的分组机制

当次用户需要使用频谱时，以买家的身份向次级服务商上传自己的“竞拍信息”.当主用户有空闲频谱时，以卖家身份向次级服务商上传自己的“拍卖信息”，包括：频谱信息和竞拍底价.次级服务商收到买卖双方的交易信息时开始组织拍卖.与传统拍卖组织方法不同，分组拍卖不再是将全部买家和卖家整合在一起进行拍卖，而是按照规则，将满足一定条件的买家和卖家将按照区间规则被分配到对应的分拍卖场进行拍卖交易.

假设在某一个区域内次用户数目为N，主用户数目为M，频谱数目为S，在拍卖过程中次用户作为买家，主用户作为卖家，将买家和卖家各自的价格按升序排列，具体规则为

(1)

传统的拍卖中，所有的买家和卖家都集中在同一个拍卖系统中，在拍卖过程中买家需要等待符合自己需求的商品出现时才会参与竞拍，等待的过程于买家来说都属于“无效竞拍”，这会对拍卖效率有较大影响.

2 频谱拍卖机制

2.1 频谱拍卖胜出次用户的判定

(1)目标函数

(2)

为所有胜出次用户出价和的最大值，其中b(n)为次用户n的竞拍价格，N表示参加拍卖所有次用户N={1，2，3…}，θ(n)是“0-1”判决函数

(3)

(2)决定用户胜出过程中的约束条件

约束条件的设定主要从两方面考虑——传输过程中用户间产生的干扰和传输过程中的信道吞吐量.

约束条件(1)：在一定距离范围内，当两个用户使用相同频段时会产生同频干扰，影响用户的正常传输.为避免同频干扰设置一个干扰半径[14]为

(4)

当次用户i与j的距离dij大于此干扰半径Rij时，次用户j才可使用频带c，相反，如果次用户i与j间的距离dij小于Rij，两次用户不能使用相同频带c，否则会影响用户i的正常传输.此类用户称为用户i的干扰邻居.用户i的干扰邻居集合Di为

(5)

(6)

为了防止次用户i的任意干扰邻居j都不使用频段c的条件为

(7)

公式中：c为分配的频段；C为可分配频段的集合.

(8)

公式中：Cn为信道容量，根据香农公式可得信道容量为

(9)

公式中：N0为噪声功率谱密度；Wc为频段c的带宽；gn为功率衰减系数[15].

由公式(8)、公式(9)得到的约束条件为

(10)

综上，在一场拍卖中决定次用户胜出的条件为

(11)

公式中：b(n)、θ(n)、Cn分别为次用户n的竞拍价格、判决函数和分配的信道容量.

2.2 次用户竞拍价格函数

本文考虑的传输方式为QAM(Quadrature Amplitude Modulation)[16]，其误码率BER可表示为

(12)

公式中：tn，c为频谱利用率；φn，c为次用户n传输时的信干噪比(SINR).

传输次用户n的频谱利用率为

tn，c=log2(1+Knφn，c)，

(13)

(14)

(15)

(16)

3 收费机制

频谱拍卖与实际拍卖存在一定差异，为了抑制拍卖过程中竞拍者虚假出价的行为，本文提出了一种满足真实性的收费机制.

通过求解公式(11)可以得到一次拍卖中胜出的次用户集合N1，其中任意次用户i的出价为b(i)，i∈N1；若此时次用户i不参加拍卖，则通过求解公式(11)可得到一个不包含i的胜出者集合N2，则BN2表示该组胜出者的竞价和为

(17)

上式表示在次用户i不参加拍卖时其他用户的竞价和.

当次用户i参加拍卖，此时其他次用户的竞价和为

(18)

对胜出次用户i的收费是由其他次用户的损失决定ε(i)为

ε(i)=∂(BN2-BN1)，

(19)

公式中：∂为波动系数；ε(i)为对胜出次用户的对其他次用户造成的损失.

在确定出胜出者同时分配给其频谱时，需要收取使用频谱的相关费用，合理的收费机制是保证拍卖真实性关键.传统的拍卖机制一般是将出价高的买家定为胜出者，但这种拍卖机制并不适用于频谱分配，需要做出相应改进.

本文提出了一种满足真实性的收费机制.拍卖的真实性是指参加拍卖的买家都会根据自身的需求进行出价，不会为了获得频谱而出现虚假出价的情况.即每个买家根据自身需求都有一个最大估价，记为b*(i).最终支付的费用为对其他次用户造成的损失ε(i)，那么可以得到该买家在这次拍卖中获得效益u(i)为

(20)

公式中：L(i)为组织一次拍卖所需的成本.

如果一个拍卖机制不满足真实性，那么参加拍卖的买家i为了获得更高的效益，会给出与自身需求不符的竞拍价格，即b*(i)>b(i).拍卖的真实性是指当买家存在虚假出价行为时，不能获得合理的收益.即u(b(i))≥u(b*(i))，这种真实性可以降低买家之间博弈的复杂度，也可将频谱分配给获得最大效益的买家，从而实现频谱利用的最大化.

设胜出次用户的集合为N1，则在一场拍卖中，卖家的效益为

(21)

由公式(20)和公式(21)可得买家和卖家的总体收益函数U*为

(22)

4 仿真结果及分析

仿真设定区域为一个40×40 m2的区域存在30个认知用户，信道数为20个，次用户将需求发送给次级服务商.其中，次用户干扰半径为R=3，频谱负载度K=2，波动系数∂=1.37.次级服务商组织拍卖并由胜出规则得到胜出竞拍者集合N1.仿真进行30次实验并记录结果.

本文算法在判定胜出次用户时引入了干扰半径作为约束条件，防止同频干扰现象的发生，而其它两种算法在频谱分配过程中没有考虑同频干扰问题，导致次用户获得频谱后可能无法进行正常传输，降低了频谱利用率.在频谱利用率方面本文算法明显高于其它两种算法，如图1所示，验证了本文提出约束条件的可行性.

由于频谱资源有限，所以随着次用户增多次用户平均收益逐渐降低，当次用户数目较少时次用户平均收益相差不大，如图2所示.这是由于在次用户数目较少时，本文算法分组数也较少，导致三种算法次用户平均收益没有明显差异，但随着次用户数增加，本文算法的优势逐渐显现，可以看到当次用户数到达30时，本文算法次用户平均收益明显高于其他两种算法.

图1 不同算法的频谱利用率比较图2 不同算法的次用户平均收益

由于本算法的首先根据分组规则将频谱和买家进行了分组，之后在分组的基础上进行卖，提高了拍卖过程中次用户与频谱的匹配程度，降低了拍卖过程中次用户的等待时间，从而能使系统较早的达到稳定状态.系统收益和迭代次数的关系如图3所示，从图3中可以看到，当迭代次数为200时，本文算法到达稳定状态；在迭代次数为300时，其余两种算法到达稳定状态，验证了本文算法分组规则的有效性.

为了避免次用户虚假出价情况，本文在收费机制方面做出了改进.胜出者最终支付的价格与对其他次用户造成的损失相联系，使得次用户作为竞拍者虚假出价时获得较小收益.虚假出价和真实出价的次用户的收益情况如图4所示.从图4中可以看到真实出价的次用户都获得了较大的收益，虚假出价的次用户的收益在一个很小的范围内变化，验证了本算法收费机制的真实性.

图3 不同算法的系统收益与迭代次数关系图4 真实出价和虚假出价收益比较

5 结 论

本文在传统基于拍卖的频谱分配算法基础上做出了一些改进.首先，提出了一种分组机制，运用分组的方法提高了每组中次用户与频谱的匹配程度，降低拍卖过程中次用户的等待时间，提高频谱分配效率.其次，在频谱分配过程中构建了约束条件，防止同频干扰的问题发生提高频谱利用率.最后，构建了满足真实性的收费机制，抑制拍卖过程中次用户虚假出价行为，保证次用户收益.仿真实验结果验证了本文算法的有效性及可行性.