基于VCG 机制的动态频谱分配算法

刘觉夫，朱丙虎，王华锋

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

0 引 言

认知无线网络［1］频谱共享分为两种方式：Underlay频谱共享和Overlay频谱共享［2］。由于认知用户具有自私、理性的特性，在动态频谱分配过程中，认知用户频谱选择策略时总是以最大化自己的收益为目的，导致频谱资源过度占用。

为了解决上述问题，提升无线网络性能，众多学者和专家使用博弈论方法对动态频谱分配问题进行了研究［3］。其中，VCG （vickrey－clarke－groves）机制是有效的，激励相容的，并且还是个人理性的［4］；Kelly－VCG 机制可以保证用户之间分配资源的公平性［5］；文献 ［6］提出了基于VCG 机制的合作博弈模型，用于解决Overlay频谱共享技术下频谱分配问题；文献 ［7］提出一种基于VCG 的非合作博弈模型，用于解决Underlay频谱共享技术下频谱分配问题，但其效用函数较为复杂，而且没有给出频谱分配算法的具体流程。

本文针对Underlay 频谱共享方式下动态频谱分配问题，提出了一种分布式动态频谱分配算法，最大化网络系统效用，同时保证用户的公平性。首先，将频谱分配问题建立成一种非合作博弈模型，并设计其效用函数，然后运用VCG 机制设计收益函数，并提出一种动态频谱分配算法，在满足主用户的数据传输速率需求和误码率限制的条件下，最大化网络系统吞吐量，同时保证认知用户的公平性。

1 系统模型

考虑如下场景：系统中存在N 个认知用户传输进程ST ，M 个主用户传输进程PT ，C个可用信道和一个公共控制信道。每个传输进程都有一个发射端，一个接收端。网络结构如图1所示。所有用户都可以在公共信令信道上广播和接收信息。假定每个主用户传输进程占用一个可用信道，认知用户在对主用户的传输质量不产生干扰的情况下以Underlay方式共享可用信道。不妨假定所有的主用户、认知用户均能够自适应调制，拥有固定的误码率。

图1 网络结构

对于认知用户传输进程STn，n ∈［1，N］，信道c，c∈［1，C］有

对于STn，n∈［1，N］，设计效用函数un，表示认知用户的效用。在本文中，认知用户的效用是其数据传输速率。由于数据传输速率取决于选择的信道，那么效用函数un取决于xn，c。

系统中所有用户的效用之和为

式中：X——xn，c组成的矩阵。

可以将该问题建立成一个非合作博弈模型，其中ST 是参与者，策略为可用信道的选择及其在所选信道上的传输功率。对于每个信道，ST 的传输功率各不相同。那么，就要求每一个参与者选择自己的策略最大化自己的效用同时最大化网络的吞吐量。本文采用VCG 机制解决该问题，其详细介绍见第3节。

2 效用函数设计

主用户、认知用户均能够自适应调制，那么对于QAM（quadrature amplitude modulation）［8］，单输入单输出高斯信道的误码率BER 可通过式 （3）近似表示

式中：kn，c——该调制方式下的频谱利用率，γn，c——STn占用信道c 时的信干噪比 （SINR）。STn的频谱利用率可以表示为

其中，BERtarn表示STn误码率的上限。SINR 对于主用户和认知用户都至关重要，文献 ［9］给出了计算方法如下

其中，n∈［1，N］，c∈［1，C］，m ∈［1，M］，ppt和pst分别对应PT 和ST 的发射功率，Gptmm′c和Gstnn′c分别对应PT 和ST 在信道c 上的增益。

本文中，只考虑简单信道模型，即信道增益仅与距离有关

不失一般性，如果主用户传输进程的数目等于信道的数目 （M ＝C），不妨假定每个主用户使用一个固定信道。如果M ＜C，则假定信道分成两部分：一部分被C 个PT固定占用，另一部分 （M－C 个信道）未被占用。那么可得

因此，STn占用信道c 的香农容量为

式中：Bc——信道c的频谱带宽。

不失一般性，设每个信道的带宽相同，那么STn的效用函数为

3 基于VCG 机制的动态频谱分配

3.1 动态频谱分配模型

在动态频谱分配过程中，每个参与者都是单独参与博弈，总是以最大化自己的收益为目的。那么就要求为每个参与者制定合理的策略最大化自身收益同时最大化网络整体效用。本文采用VCG 机制解决该问题，VCG 机制是有效的，激励相容的，并且是个人理性的。这就意味着采用VCG 机制能够最大化系统效用；在VCG 机制中说真话是一个弱占优策略；个人理性指的是每个知道自己估价的局中人都愿意参与这个VCG 机制。本文中，应用VCG 机制旨在：①针对认知用户的动态频谱分配问题，做公平可靠的社会决策；②计算每个认知用户的转移支付τn。

转移支付表示STn占用信道传输对其他认知用户所造成影响的补偿。VCG 机制使用每个用户递交的效用函数来决策。在本文中，每个认知用户使用第2节定义的效用函数。社会决策是为了最大化所有认知用户的效用之和即最大化网络吞吐量。

网络系统中的约束条件如下所示：

（1）干扰温度限制；

（2）满足认知用户的速率需求；

（3）认知用户只能选择一个信道；

（4）发射功率限制在一定范围内。

该系统的频谱分配可以由下面的最优化问题来表示

认知用户的功率取决于主用户的传输功率。针对每个PTm满足其速率需求，保证其误码率小于其误码率上限，则在其占用的信道上允许的最大干扰可以表示为

那么，认知用户的发射功率满足

该模型给出了认知用户在可用信道上的频谱分配方案，使得认知用户使用频谱时不对主用户传输产生影响，最大化系统整体效用。

考虑认知用户异步的做决策，定义xoptn为STn的最优策略。定义x－n＝｛x1，…，xn－1，xn＋1，…，xN｝，xi∈［1，C］∪｛0｝，且i≠n。若STn没有分配到频谱，则xoptn＝0。则转移支付的计算方法如下

转移支付表示STn参与频谱分配时对其他用户造成影响的补偿。其中，前一项表示当STn参加博弈达到最优分配时，其他用户的效用之和。后一项表示，STn不参与博弈其他用户达到最优分配时的效用之和。

由于τn≤0，可以定义STn的收益函数如下

当每个认知用户都如实报告自己的需求，则收益函数等于效用函数即vn＝un。那么，对于认知用户在博弈中的占优策略是报告自己真实需求。每个次级用户都尽力减少转移支付的值。理想情况下，τn＝0意味着STn不对其他认知用户的频谱分配收益产生任何影响。因此，可以得出结论STn占优策略是如实报告自己的需求。

综上所述，当每个认知用户报告真实的传输速率需求，最小化转移支付，则系统可以得到最优解即达到纳什均衡，并且是帕累托最优的。

3.2 信令的设计

在上述认知无线网络场景中，没有中心控制节点的存在，在认知用户迭代地调整选择信道和功率的策略的过程中，认知用户之间必须采用信令来传递决策所需的各种参数。本文参考文献 ［10］设计了信令握手协议，设定公共信令信道，并定义START，START ＿CK 和ACK ＿START＿CK 这3种信令消息。

START 信令包含：认知用户在其可用信道上对其他认知用户的增益及对主用户的增益 （由信道状态表和记录的增益矩阵可得），及其下一阶段通信需求 （主要是数据传输速率和最大误码率），及其发射功率限制。START＿CK 信令消息包含：数据传输进程的接收端所选定的信道，及所需的发射功率。ACK ＿START ＿CK 信令消息包含确认信息。

每个认知用户都会维护用户增益矩阵、用户发射功率向量和信道状态表 （CST），记录待选信道上的使用情况。

3.3 算法设计

实用计算纳什均衡的方法是序贯博弈，其中每一个参与者依次选择最大化自身效用的策略而其他参与者的策略不变［11，12］。当设计了效用函数、收益函数等，设计认知用户动态策略调整规则成为动态频谱分配的关键。设计算法流程如下：

4 实验仿真

针对基于VCG 的动态频谱分配算法，本文在matlab7.6环境下，进行实验仿真。认知无线网络场景为：在500m×400m 的范围内，随机分布8个认知用户传输进程，4个主用户传输进程，可用信道数为4个。认知无线网络具体分布如图2所示。不失一般性，假定所有用户的最大误码率相同即BER ＝10－4，背景噪声功率n0＝－3dB 。所有主用户的传输速率需求为0.4bit/s/hz，认知用户的传输速率需求为0.15bit/s/hz。认知用户的最大发射功率为20dB，所有主用户使用同样的发射功率为30dB。

图2 认知无线网络分布

4.1 收敛性分析

图3为基于VCG 的动态频谱分配算法的系统整体效用的收敛情况。横坐标表示迭代次数，纵坐标表示网络系统的效用。可以看出，在执行了约40个算法周期后，系统的吞吐量不再改变，达到纳什均衡状态。

图3 系统效用收敛

图4为基于VCG 的动态频谱分配算法中认知用户策略的收敛情况。横坐标表示迭代次数，纵坐标表示策略即信道的编号。可以看出，在执行了约40个算法周期后，所有认知用户的策略不再改变，整个系统达到纳什均衡状态，验证了算法的收敛性。

图4 认知用户策略收敛

图5为基于VCG 的动态频谱分配算法中每个认知用户的效用收敛情况。横坐标表示迭代次数，纵坐标表示认知用户的效用。可以看出，在执行了约40个算法周期后，每个用户的效用不再改变，整个系统达到纳什均衡状态，验证了算法的收敛性。

图6为基于VCG 的动态频谱分配算法中信道的效用收敛情况。横坐标表示迭代次数，纵坐标表示每个信道的效用。可以看出，在执行了约40个算法周期后，所有信道的效用不再改变，整个系统达到纳什均衡状态，验证了算法的收敛性。

图5 认知用户效用收敛

图6 信道效用收敛

4.2 公平性分析

为了对认知无线网络中频谱资源分配的公平性进行量化，本文采用了Jain公平系数和Gini公平系数［13］，其具体定义如下

图7 为基于VCG 的动态频谱分配算法中认知用户的Jain公平系数和Gini公平系数的收敛情况。横坐标表示迭代次数，纵坐标表示公平系数。可以看出，在执行了约40个算法周期后，公平系数不再改变，系统达到纳什均衡。Jain公平系数达到95%以上，Gini公平系数达到20%以下，可以验证该算法具有较好的公平性。

5 结束语

图7 系统公平系数收敛

本文针对在Underlay频谱共享方式下的认知无线网络动态频谱分配问题，提出了一种分布式动态频谱分配算法，最大化认知无线网络的吞吐量，同时保证公平性。在满足主用户的服务质量 （QoS）的前提下，建立了一种非合作博弈模型，并设计效用函数，在借鉴VCG 机制的基础上，设计相应的收益函数。实验仿真结果表明，在执行了约40个算法周期后，系统吞吐量、用户的策略、用户的效用、信道的效用不再改变，达到纳什均衡，验证算法的收敛性。引入Jain公平系数和Gini公平系数衡量该算法的公平性，实验结果表明，Jain公平系数到95%以上，Gini公平系数达到20%以下，可以验证该频谱分配算法具有良好的公平性。

［1］Badoi C I，Prasad N，Croitoru V，et al.5Gbased on cognitive radio ［J］.Wireless Personal Communications，2011，57 （3）：441－464.

［2］Bansal G，Hossain M J，Bhargava V K，et al.Subcarrier and power allocation for OFDMA－based cognitive radio systems with joint overlay and underlay spectrum access mechanism ［J］.IEEE Transactions on Vehicular Technology，2013，62 （3）：1111－1122.

［3］Ni Qiufen，Zhu Rongbo，Wu Zhenguo，et al.Spectrum allocation based on game theory in cognitive radio networks ［J］.Journal of Networks，2013，8 （3）：712－722.

［4］ZHAO Yaohua，PU Yongjian.Game theory and economic modeling ［M］.Beijing：China Renmin University Press，2010：312－340 （in Chinese）.［赵耀华，蒲勇建.博弈论与经济模型 ［M］.北京：中国人民大学出版社，2010：312－340.］

［5］Jain R.Network market design part I：Bandwidth markets［J］.Communications Magazine，IEEE，2012，50 （11）：78－83.

［6］Rajasekharan J，Eriksson J，Koivunen V.Cooperative gametheoretic approach to spectrum sharing in cognitive radios［J］.arXiv Preprint arXiv，2011：1112.1520.

［7］El Ferkouss O，Ajib W.Game theory based resource allocation for cognitive radio networks ［C］//Global Communications Conference.IEEE，2012：1174－1179.

［8］Xie R，Yu F R，Ji H.Dynamic resource allocation for heterogeneous services in cognitive radio networks with imperfect channel sensing ［J］.IEEE Transactions on Vehicular Technology，2012，61 （2）：770－780.

［9］Attar A，Nakhai M R，Aghvami A H.Cognitive radio game for secondary spectrum access problem ［J］.IEEE Transactions on Wireless Communications，2009，8 （4）：2121－2131.

［10］LI Xiaolin，LIU Haitao.Spectrum allocation algorithm of cognitive radio based on supermodel game ［J］.Journal of Chongqing University of Posts and Telecommunications（Natural Science Edition），2010 （2）：151－155 （in Chinese）.［李校林，柳海涛.基于超模博弈的认知无线电频谱分配算法 ［J］.重庆邮电大学学报 （自然科学版），2010 （2）：151－155.］

［11］SONG Zhiqun，LIU Yutao，WANG Jingning.Cognitive radio technology and its applications ［M］.Beijing：National Defense Industry Press，2012：82－120 （in Chinese）. ［宋志群，刘玉涛，王荆宁.认知无线电技术及其应用 ［M］.北京：机械工业出版社，2012：82－120.］

［12］YANG Guang，JIANG Junmin，SHI Yuanying.Cognitive radio spectrum allocation based on potential game ［J］.Modern Electronics Technique，2011 （13）：41－45 （in Chinese）.［杨光，蒋军敏，施苑英.基于潜在博弈的认知无线电频谱分配研究 ［J］.现代电子技术，2011 （13）：41－45.］

［13］Shi H，Prasad R V，Onur E，et al.Fairness in wireless networks：Issues，measures and challenges ［J］.Communications Surveys ＆Tutorials，IEEE，2014，16 （1）：5－24.