基于用户等待时间和带宽需求的改进CSGC算法

徐金玉，柳 平

(1.揭阳职业技术学院，广东揭阳 522000;2.汕头大学，广东汕头 515000)

0 引言

随着无线移动通信的快速发展，无线频谱资源的利用显得越来越紧张，人们对无线宽带通信技术的应用提出了更高的要求，频谱资源利用问题成为人们关注的热点。为了满足用户对系统服务质量(quality of service，QoS)的要求，当前无线网络管理模式都采用固定频谱分配制度，即特定的通信业务享有频谱管理部门所授权的特定频谱。通过文献［1－4］分析得出目前频谱的使用现状:大量时间里，许多频谱处于空闲状态，还有许多频谱只获得了部分使用，剩下的少量频谱使用十分拥挤。从而文献［3］提出了“频谱空洞”的概念:分配给主用户，在特定时间段和空间地理位置并不使用的频谱。文献［5］和［6］研讨了探测频谱空洞的方法，文献［7］研究了如何合理地使用频谱空洞为人类带来新的效益。认知无线电的产生为无线通信领域的可持续发展开启了新的篇章。当前大部分研究主要集中在利用动态频谱分配算法解决无线频谱利用率低的问题。Ian F.Akyildiz和LeeWon－Yeo在文献［8］中列举了无线频谱共享技术面临的巨大挑战，其一在于如何探测用户对频谱的需求，文献［9］提出了协作模式下的频谱感知方法，文献［10］提出了一种检测频谱感知效率的标准;其二在于如何建立一个有效的中央控制系统管理频谱分配，而其中关键就在于分配算法。

随着认知无线电的深入研究，基于图论着色理论的认知无线电网络的频谱分配算法已经有了不少成果，提出了图论着色(list coloring，LC)频谱分配算法［11］，颜色敏感的图论着色(color sensitive graph coloring，CSGC)频谱分配算法［12］及 2 种改进算法［13－14］，分布式局部议价频谱分配算法［15］，并行频谱分配算法［16］。List－Coloring 算法比较类似于传统蜂窝小区的小区间的频率规划，目标是最大化复用因子，但是List－Coloring算法未考虑认知无线电系统频谱分配中频谱效益的差异性和干扰的频谱差异性。CSGC算法则考虑这两种差异性，并给出复合图的带权重的List－Coloring算法，然而CSGC算法存在运算量过大的问题，并随着用户数和频谱数的增加成非线性增加，而且不考虑用户的实际需求，导致频谱分配的实际效率不高。分布式局部议价的分配方法假设初始分配是全局最优，之后的每次分配利用前一次分配的信息，只对局部变动的拓扑进行议价分配以达到最优，从而减少运算开销。并行频谱分配算法降低了分配的时间开销，适应了认知无线电空闲频谱快速时变的特点。基于需求的改进算法更好地满足了系统的需求，但是该算法仅限于一个循环周期，当频谱资源不足时，即使某用户等待时间很长，该算法仍无法满足此用户的需求。基于用户等待时间的频谱分配改进算法使用户有趋于均衡的机会使用频谱，保证了系统的公平性，但是忽略了用户的实际要求，可能出现带宽需求很小的用户却分配到很大带宽的情况，造成频谱资源浪费，降低了频谱的利用率。

本文提出基于用户等待时间和带宽需求的改进CSGC算法，从认知用户的利益出发，兼顾用户等待时间和带宽需求。一方面保证等待时间长的用户使用频谱的优先权和弱势用户的分配权，提高了系统的公平性;另一方面，在主用户释放频谱资源充足的情况下，使分配结果最大化满足用户带宽需求，提高系统的频谱利用率，而在频谱资源匮乏时，适当牺牲部分系统效益，加速分配过程，扩大分配用户数，达到效益和公平性的平衡。

1 基于用户等待时间和带宽需求的改进CSGC算法

1.1 频谱分配数学模型

为了便于量化分析，建立图论着色数学模型［11］，我们定义以下数量关系:其中 i表示用户，j表示频谱。

1 )空闲矩阵L。L=(li，j)代表空闲矩阵，即用户可使用的频谱矩阵。当li，j=1，表示频谱j对用户i是可用的;否则，li，j=0，表示频谱j对用户i是不可用的。

2 )效益矩阵B。B=(bi，j)代表效益矩阵。即用户i使用频谱j给系统带来的效益，实际研究过程中，用实际效益矩阵 LB=(li，j·bi，j)，代表实际情况下频谱j对用户i的效益，即频谱j对用户i可用则产生效益为bi，j，否则，即频谱 j对用户 i不可用时产生的效益为0。

3 )用户带宽需求矩阵Λ。Λ =(λi)代表用户带宽需求矩阵，即用户i需要的带宽是λi。用户需求是指用户的长期需求。

10 )用户等待次数。在某个用户从系统开始分配直到其带宽需求获得满足或者分配结束这一时间段内系统分配的次数，它表示此用户为了获得足够带宽需要等待时间的长度。

1.2 算法分配目标

本算法的目的:在频谱资源比较充分时，对频谱进行有效分配，使系统总效益最大化;当频谱资源比较紧张时，在保持系统总效益损失不大的情况下，使所有认知用户未获得满足的带宽需求总和最小化，两种情况的分配均保证以下2个要求。

1 )弱势用户在付出较长的等待时间后将会获得分配机会。

2 )当认知用户的带宽需求获得满足后系统不再对其进行分配。从而系统将在满足当前用户的带宽需求的前提下，尽量预备更多空闲频谱用以分配给新加入系统的用户。定义I表示认知用户总数，J表示可用频谱总数，数学描述如下。

在频谱资源充分的情况下有

1.3 算法思想及步骤

尽管认知用户伺机地使用主用户所释放的频谱资源，但是，在保证主用户的权益的前提下，认知用户的接入提高了系统的频谱利用率。所以，作为认知无线电系统中的一种特定的用户，我们有必要考虑认知用户的利益。基于用户等待时间和带宽需求的改进CSGC算法就是从考虑用户的等待时间公平性和频谱需求的实际出发的。

算法设计过程中，以等待时间为切入点，频谱分配的整体思想是尽量保证等待时间更长的用户的优先权。

以频谱需求为切入点，我们考虑3种情况。

1 )当频谱满足用户的需求时，用户退出分配。

3 )当用户未获得任何频谱资源时，等待时间加1。如此循环，通过更新节点，检测新用户的到来。保证等待时间长的用户优先获得频谱，而且最终使用户的频谱需求获得满足。

我们定义扫描周期T代表2次扫描之间的间隔时间，程序执行时间t代表从上一次更新节点信息到当前时刻的间隔时间，用户等级矩阵GR中等级最高的顶点，其对应等级为gm。初始化系统后，算法步骤如下。

步骤1 更新节点信息，检测新用户，建立图论着色数学模型［11］以及相关矩阵和变量。

步骤2 判断图G［11］是否为空，若为空，等待时间t=T，即等待下一个扫描周期;若非空，进入步骤3。

步骤3 搜索用户等级矩阵GR中等级最高的顶点，其对应等级为gm。并按照分配准则计算其标签值以及可用颜色。

步骤4 搜索标签值最大的顶点i。

步骤5 判断标签值最大的顶点i是否唯一。若唯一，对其分配相应的颜色j，即效益不等按效益分配;否则，随机选择一个顶点对其分配相应的颜色j，即效益相等随机分配。

步骤6 更新顶点i需求，重新赋值计算用户i获得分配后的带宽需求 λi= λi－wi，j。

步骤7 拓扑更新。

①将j色从与顶点i以j色边相连的顶点的关联频谱列表中删除，并删除图G中这些顶点的j色边，即删除此次分配出的频谱并且更新干扰情况。

②更新此用户i的等待时间为

③删除λi≤0的顶点，即删除带宽需求得到满足的用户。

④其余顶点的等待时间递增1

步骤8 判断是否需要进行节点更新。若需要，转步骤1，否则，判断图G是否为空。若为空，转步骤 1;否则，转步骤3。算法流程图如图1。

图1 基于用户等待时间和带宽需求的改进CSGC算法Fig.1 Improved CSGC algorithm based on waiting time and bandwidth requirement

2 算法仿真分析

下面通过本文算法、CSGC算法以及2种改进CSGC算法，分别对频谱资源充足和匮乏进行仿真。参考IEEE 802.22的认知无线电区域网提案，用带宽速率表示效益和需求。仿真参数如表1所示。

表1 仿真参数设置Tab.1 Simulation parameters

用户的个数可以代表频谱资源的紧张程度。10个用户意味着频谱资源空闲，40个用户则反之。

为了方便比较，本文算法只设置了一个周期内的仿真。通过反复实验，得到用户等待时间(首次获得分配的等待时间和总等待时间)，系统总带宽以及未满足需求总量的累积分布函数。下面是在协作模式下，根据频谱资源的充分与否，对结果的分析。

2.1 弱势用户获得首次分配的等待次数

当系统中存在效益很小的认知用户，如果采用系统效益最大化准则，可能造成此用户始终不能获得分配。实际上，系统的用户是不断更新变化的，如果不能尽快对弱势用户进行分配，一旦用户信息更新，弱势用户可能仍然处在分配的弱势地位，那么在下个分配周期中他可能仍然不能获得分配机会。因此，文献［14］提出，弱势用户获得首次分配机会而付出的等待时间(waiting times for the first assignment，WFA)是衡量分配效果的重要指标。通过以下的仿真分析可知，如果采用CSGC算法，或者2种改进算法，均有较大可能出现弱势用户不能获得分配的情况，但是本文算法基本可以避免此类情形的发生。仿真时，设置10个用户，其中一个弱势用户，20个频带，每个频带对弱势用户的效益都是最低效益3 025 bit/period。

如图2所示，在资源充足时，将系统分配次数限制在20次以内，则本文算法在此时间段内将频谱分配给弱势用户使用概率是75%，退出改进算法的概率是35%，基于用户等待时间的改进CSGC算法(时间改进算法)的概率是30%，而CSGC算法则不到10%。如果将系统分配次数限制在25次以内，CSGC算法的概率增加到10%以上，时间改进算法接近50%，退出改进算法增加到70%，而本文算法则增加到95%，基本能保证弱势用户获得分配。同时发现，即使资源充足，时间改进算法和CSGC算法也不能保证弱势用户的分配权。

图2 频谱资源充足时4种算法关于弱势用户获得首次分配的等待次数的累积分布Fig.2 Cumulative distribution ofweak user's WFA with adequate bands

如图3所示，在资源紧张时，时间改进算法只有不到30%的概率可以保证弱势用户的分配权，CSGC算法为60%，退出改进算法为75%，但是本文算法则有95%以上的几率保证对弱势用户进行分配，而且只需要用较短时间就可以办到。如果将系统分配次数限制在100次以内，另外3种算法在此时间段内将频谱分配给弱势用户使用概率都不超过20%，但是本文算法则接近60%，如果将次数提高到110次，则其余算法的分配效果略有提高，不超过50%，但是本文算法达到95%。

图3 频谱资源不足时4种算法关于弱势用户获得首次分配的等待次数的累积分布Fig.3 Cumulative distribution of weak user's WFA with inadequate bands

2.2 未满足需求总量的累积分布比较

图4表示了未满足需求总量(total dnsatisfied demand，TU)的分布概率。具体地说，CSGC算法使未满足需求总量，即TU小于10 kbit/period的可能性约为20%，小于30 kbit/period的可能性约为60%，而本文算法使TU小于10 kbit/period的可能性约为45%，小于30 kbit/period的可能性约为80%，以此类推。以纵轴为目标，在等概率的条件下，本文算法在满足用户需求的性能方面与CSGC算法相比有显著的提高，而基于用户等待时间的改进算法但是和2种改进算法相比，在未满足需求总量小于10 kbit/period时分配效果较差，高于20 kbit/period后差距不大。

图4 频谱资源充足时未满足需求总量的累积分布Fig.4 Cumulative distribution of TU with adequate bands

从图5可以发现，在频谱资源不足时，关于未满足需求总量，相比退出改进算法和CSGC算法，本文算法的效果有所下降，但比时间改进算法有显著提高。这是因为本文算法从公平性的角度考虑，牺牲了部分用户的需求用于满足弱势用户。虽然系统的未满足需求的总量有所增加，但是综合2.1节的分析(弱势用户获得分配的机会很大，意味着其他认知用户也有很大可能获得分配的机会)可知，通过降低通信质量的方法，本文算法可使更多用户可以使用频谱资源。

图5 频谱资源不足时未满足需求总量的累积分布Fig.5 Cumulative distribution of TU with inadequate bands

2.3 系统总带宽的累计分布比较

如图6所示，在资源充足时，本文算法分配出的系统总带宽(total bandwith，TB)显著小于GSGC算法，和退出改进算法比较接近，相比时间改进算法较小，但这并不意味着分配的效果降低。实际上，根据2.2节中对资源充足情形的仿真可知，时间改进算法会造成大量用户不能获得足够带宽，而本文算法则不存在此问题，通过合理选择频谱资源对认知用户进行分配，使用户的需求得到满足。

图6 频谱资源充足时4种算法关于系统总带宽的累积分布Fig.6 Cumulative distribution of TB with adequate bands

如图7所示，与资源充足时的总带宽情况相比，退出改进算法的分配效率相对其余3种算法下降，本文算法则相对提高，时间改进算法和CSGC算法基本不变。

图7 频谱资源不足时4种算法关于系统总带宽的累积分布Fig.7 Cumulative distribution of TB with inadequate bands

2.4 用户等待次数总和

如图8所示，在资源充足时，对于所有用户总的等待次数(total waiting times，TW)，CSGC 算法较差，因为此算法会将频谱分配给带宽需求已经满足的认知用户，退出改进算法和时间改进算法的区别不大，但相比本文算法效果较好。其原因在于:退出算法以满足多数用户的需求为目的，但是在2.1节的仿真分析中我们知道，此算法可能导致弱势用户不能获得分配机会，可以理解为通过牺牲少量弱势用户加速分配;而时间改进算法由于产生总带宽较少，而且大多数用户需求没有获得满足，同样可以认为牺牲较大效益换取分配进程的加快。

图8 频谱资源充足时用户等待次数总和的累积分布Fig.8 Cumulative distribution of TW with adequate bands

通过以上的分析，在频谱资源不足时，本文算法牺牲了部分效益，但在控制用户等待时间方面，本文算法有显著提高。如图9所示，本文算法将用户等待次数限制在2 200以内的概率达到90%以上，而2种改进算法在相同的限制下只能到达60%左右，CSGC算法更是不足10%。由此得出，系统资源不足时，本文算法可以在相对少的时间内完成频谱分配。

图9 频谱资源不足时用户等待次数总和的累积分布Fig.9 Cumulative distribution of TW with inadequate bands

对于频谱资源充足的情况，本文算法在牺牲极小部分用户总带宽需求的情况下，高效分配系统资源，更快捷地把信道更为合理的分配给用户，并且保证等待时间较长的用户的分配优先权，避免出现弱势用户。而对于频谱资源不足的情况，本文算法牺牲部分系统总效益和用户带宽总需求，在相对少的时间内将频谱分配给更多的用户使用，同时弱势用户在付出比较少的等待时间后可以获得部分频谱使用权，有效提高频谱分配的公平性。

3 结论

认知无线电为解决频谱资源二次利用问题提供了一个可行的方案。频谱分配过程中，在主用户利益不受损害的情况下，尽可能多地考虑次用户的实际利益。本文中我们第一次兼顾用户等待时间和实际带宽需求，在算法设计过程中，以用户的等待时间和用户获得分配的情况为参考，通过对用户等待等级赋权的方式保证等待时间长的用户的优先权，保证了弱势用户的分配权;另外，以用户的实际需求为参考，通过积累和退出的机制保证频谱分配的高效性，即利用相对少的总带宽满足相对的多的用户需求，节约频谱资源。最后通过仿真分析，结果表明:本文算法保证了弱势用户的分配权，有效地满足了用户的需求，提升了系统的公平性，提高了频谱利用率。

［1］Federal Communications Commission.Spectrum Policy Task Force［EB/OL］.(2002－12－03)［2009－01－15］.http://www.fcc.gov/sptf/files/SEWGFinaleport_1.pdf.

［2］MITOLA J.Cognitive radio for flexible mobilemultimedia Communications［EB/OL］.(1999－11－15)［2008－12－11］.http://ieeexplore. ieee. org/stamp/stamp. jsp?tp =＆arnumber=819467＆tag=1.

［3］NEEL J，REED J，GLLESR.Convergence of cognitive radio networks［C］//Proceedings of IEEE Wireless Communications and Networking Conference，2004.［s.l.］:IEEE Press，2004，4:2250－2255.

［4］STAPLE G，WERBACH K.The end of spectrum scarcity［J］.IEEE Spectrum，2004，41(3):48－52.

［5］HAYKIN S.Cognitive radio:brain－empowered wireless communications［J］.IEEE Journal on Selected Areas in Communications，2005，23(2):201－220.

［6］CABRICD，MISHRA S，BRODERSEN R.Implementation issues in spectrum sensing for cognitive radios［C］//Proceeding of the 38th Asilomar Conference Record on Singnals，Systems and Computers，Berkeley:［s.n.］，2004:772－776.

［7］KRISHNAMURTHY S，THOPPIAN M，VENKATESAN S，et al.Control channel based MAC－Layer configuration，routing and situation awareness for cognitive radio networks［C］//IEEE Military Communications Conference，2005，Dallas:［s.n.］，2005:455－460.

［8］IAN A，AKYILDIZ F，LEEW.Survey on spectrum management in cognitive radio networks［J］.Cognitive radio Communications and Networks，2008，46(4):40－57.

［9］ZHENG H，PENG C.Collaboration and fairness in opportunistic access［C］//Proceeding of the 40th Annual IEEE International Conference on Communications(ICC)，Seoul:［s.n.］，2005:3131－3138.

［10］缪殿飞，郑宝玉.协作频谱感知在认知网络中的应用［J］.重庆邮电大学学报:自然科学版，2008，20(6):663－666.

MIAO Dian－fei，ZHENG Bao－yu.Cooperative spectrum sensing in cognitive radio network［J］. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2008，20(6):663－666.

［11］WANGW，LIU X.List－Coloring based channelallocation for open－spectrum wireless networks［C］//The 62nd IEEE vehicular technology conference(VTC).2005，Dallas:［s.n.］，2005:690－694.

［12］PENG C，ZHENG H，ZHAO B.Utilization and fairness inpectrum assignment for opportunistic spectrum access［J］.ACM mobile networks and applications(MONET)，2006，11(4):554－576.

［13］廖楚林.认知无线电系统的频谱分配算法研究［D］.成都:电子科技大学，2007:58－76.

LIAO Chu－lin.Research of spectrum allocation in cognitive radio network［D］.Chengdu:University of Electronic Science and Technology of China，2007:58－76.

［14］柳平，张敏.基于用户等待时间的频谱分配改进算法［J］. 广东通信技术，2009，11(6):17－20.

LIU Pin，ZHANG Min.Research of spectrum allocation based on user waiting time in cognitive radio network［J］.Guangdong Communication Technology，2009，11(6):17－20.

［15］莫文承.认知无线电频谱分配算法研究［D］.西安:西安电子科技大学，2008:40－62.

MO Wen－cheng.Research of spectrum allocation algorithm in cognitive radio［D］.Xi'an:Xidian university，2008:40－62.

［16］CHEN X，BIE Z，WUW.Detection efficiency of cooperative spectrum sensing in cognitive radio network［J］.Journal of China Universities of Posts and Telecommunications，2008，15(3):1－7.

(编辑:田海江)