一种改进的认知无线电频谱接入策略

徐德艳，李 勇，程 伟

（西北工业大学 电子信息学院，陕西 西安 710100）

随着无线通信服务需求的快速增长，频谱已变的越来越拥挤。现有的频谱分配政策表明，几乎所有的可用频谱都已被占用。但是，被授权的频谱不会在任何时候都被主用户占用，在被占用的授权频谱中寻求可供次用户使用的频谱机会（即所谓的“频谱空洞”），是一种有效的解决频谱资源稀缺的办法。1999年，Joseph Mitola博士提出了认知无线电[1]（Cognitive Radio）的概念，其核心就是：CR用户（次用户）具有学习能力，能与周围环境交互信息，以感知和利用在该空间的可用频谱，并限制和降低冲突的发生。当认知用户检测到可用频谱时，需要即时进行接入。然而，如何接入、以怎样的方式接入，这是一个极具挑战性的问题。为解决这个问题，DAPRA XG研究小组提出了机会频谱接入（Opportunity Spectrum Access，OSA）的概念。

目前，已有不少学者研究了认知无线电频谱接入问题，文献[2]中作者提出了一种基于硬件约束的信道接入算法，该算法采用停时过程对感知信道数进行优化，从优化后的信道数中选择可用的信道。文献[3]中作者提出一种经典的频谱接入算法——VAC接入算法，认知用户随机感知信道，发现信道空闲时则进行数据发送并在发送完后等待，若检测到繁忙则直接等待一段时间后再感知。但上述算法中都未涉及利用主用户历史使用概率及信道统计特性来对主用户的行为进行预测。为此，文献[4]中提出一种基于部分可观测马尔科夫过程 （Partially Observable Markov Decision Process ，POMDP）的机会频谱接入算法，该算法的设计思想是：充分利用频谱检测的先验知识和信道统计特性，使得每个次用户动态的搜寻频谱机会，最大化自身奖励，提高系统的吞吐量和频谱利用率。然而，文献[4]中作者又指出，POMDP算法在信道数较多且频谱环境变化复杂的情况下其计算的复杂度将超出次用户可以承受的范围。因此，该文又提出一种基于贪婪算法的次优接入策略，该算法为了降低计算复杂度，不从整体最优上加以考虑，而只考虑信道当前时隙的最大奖励值，无法得到问题的最优解，但在解的优化程度和算法复杂度上是一个很好的折中。然而，贪婪算法的自私性是其最大的不足，由于其只关注当前时隙的瞬时奖励，最大奖励值相同的信道会出现多个，在该情形下次用户只能随机选择信道接入。此时，贪婪算法相对于直接使用随机接入策略的优越性就无法体现。

针对上述问题，本文提出一种新的信道接入策略，该算法对利用贪婪算法检测出的多个信道具有相同最大奖励值的情形进行改进。改进的方法是：当检测出多个具有相同最大奖励值的信道时，给该信道当前时隙的奖励值再加入下个时隙的奖励后重新选择奖励值最大的信道，可多次重复直至次用户选择出奖励值最大的一条信道。该算法相比于贪婪算法增加了一些计算复杂度，但有效的提高了系统的吞吐量。

1 基于POMDP的最优频谱接入算法

1.1 系统模型

本文的系统模型引用文献[4]中的模型，假设整个认知网络中有 N 条信道，每条信道的带宽为 Bi（i=1，2，……，N），这N条信道都是授权给主用户使用的信道。文中以时隙为单位讨论网络中信道的状态，在时隙结构中，首先检测信道是否可用，然后是在检测到的可用信道上传输数据，最后是回复确认信息。在一个时隙内N个信道的占用情况可以看成一个共有（M=2N）种状态的离散马尔科夫过程，若N=2，则状态转移图如图1所示。

图1 N=2时信道状态转移图Fig.1 Channel state transition diagram When N=2

整个认知网络中每条信道都有两个工作状态{0（占用），1（空闲）}，每个时隙 t的信道状态由向量[s1（t），s2（t），s3（t），…，sN（t）]表示，其中 si（t）∈{0，1}。 假设 T 个时隙内，信道的统计特性α，β不变，信道的状态转移概率{pi，j}已知。如图2所示，信道概率以α从0转移到状态1，以概率β保持在状态1。

依照马尔科夫链的空闲和占用状态，次用户观测当前信道是否可用，在避免对主用户造成干扰的情况下，实现主用户与次用户之间的频谱共享。频谱的占用或空闲示例如图3所示，传输时长为相同时间长度的T个时隙。

图2 马尔科夫信道模型Fig.2 Markov channel model

图3 频谱占用情况Fig.3 Spectrum occupancy

受限于硬件条件和认知用户的传输功率等因素，次用户无法检测到网络中所有的信道。故假设每个时隙内，次用户选择 M1（M1≤N）条信道检测，最多接入 M2（M2≤M1）条信道。次用户在每个时隙开始时选择M1条信道进行检测，用Rj，M2∈{0（可用），1（不可用）}来表示检测到的信道的可用性，时隙内操作流程如图4所示。

图4 一个时隙内的操作流程Fig.4 The operation process in one time slot

综上所述，问题简化为每个时隙内的检测和接入策略为{M1，M2}，为便于研究，将检测信道和接入信道的数目均设为1，即M1=M2=1，则每个时隙内便只检测N条信道中的一条信道 a∈{1，…，N}，a若可用就接入。 定义接入策略 ΘM∈{0（接入），1（不接入）}，在时隙结束时将收到 ACK信号 KM2，这里KM2∈{0（成功），1（失败）}。 我们定义，当信道状态 Si（t）=1，检测结果Rj，M1=1，接入策略ΘM=1的3个前提条件都成立时。MM2=1 此时，奖励值由 rj，M1，M2来决定。POMDP 最优策略的目的就是在每一个次用户独立寻找频谱接入的情况下最大化自身的奖励值（即系统的最大吞吐量），同时充分利用历史累积的频谱检测先验知识以及信道统计特性，来限制或减少次用户自身对主用户的干扰。

1.2 最优频谱接入算法

对部分可观测马尔科夫而言，其内部状态是完全未知的，在第t个时隙，基于历史的决策信息和观测先验知识，信道内部的状态可用一个置信矢量 Λ（t）=[λ1（t），…，λM（t）]来表示，这里的λj（t）是条件概率，它表示了历史决策和观测先验知识以及信道状态转移概率下，第t个时隙的信道状态为j的概率。根据文献[5]：对于任意的t，在第t个时隙的置信矢量Λ （t）都是最佳接入策略 {M1，M2}的充分统计量。因此，在POMDP 模型下给出一种策略 Ω=[μ1，μ2，…，μT]，其中 μT:Λ（t）∈[0，]M→{M1（t），M2（t）}，该式将频谱检测与接入策略转变为有限时域上的一种POMDP算法。由于POMDP算法的设计是MAC层和物理层的混合，所以用带宽来表示其奖励值，奖励值与带宽成正比，计算式为：

其中 Si（t）∈{0，1}是信道 i在第 t个时隙的状态。

考虑次用户网络的实际情况，由于硬件条件及次用户自身功率等因素的限制，频谱检测错误是可能存在的，但本文仅讨论一种理想情况，即次用户频谱检测无差错，检测结果真实的反应了信道的状态。我们只需要关注次用户如何选择每个时隙内检测到的信道，使得在所有时隙内的奖励值总和最大。因此，定义 Vt（Λ（t））为在当前置信矢量为 Λ（t）时，自第 t个时隙开始之后系统所获得的最大奖励值。计算公式如下：

从该式可以看出，自第t个时隙开始之后系统所能获得的最大奖励值包括两个部分：1）第t个时隙的瞬时奖励值θBa；2）第 t+1 个时隙之后系统的未来奖励值 Vt+1（Γ（Λ（t）|a，θ））。最优策略就是在获得瞬时奖励和未来奖励的信息这两者间寻求一种平衡。 其中 Λ（t+1）=Γ（Λ（t）|a，Rj，a是综合了第 t个时隙检测与接入的历史经验后更新的关于未来第t+1个时隙的信道状态知识。式中的置信矢量的更新使用贝叶斯准则，即

2 基于贪婪算法的次优接入策略及改进算法

由于POMDP的计算复杂度较高，在信道数少时，信道状态数M（M=2N）比较小，最优算法比较适用，但是当信道数较多且频谱占用的统计特性频繁变化时，基于POMDP的最优算法不再适用。因此，需要寻求一种计算复杂度相对较低的次优解决算法——贪婪算法。

基于贪婪算法的接入策略将不考虑奖励值中的未来奖励部分，而只关注当前时隙t的最大瞬时奖励值。贪婪算法将信道状态数由M（M=2N）减少为N，以每个信道的置信矢量来代替整个网络状态算法的置信矢量，故以r=[ω1，…，ωN]来表示，式中ωi为当前时隙t信道i是否被占用的概率。已经证明当N条信道相互独立时，γ（t）是最优接入策略的充分统计量[6]。利用可以得到基于贪婪算法的次优策略以最大化每个时隙的吞吐量，由于信道相互独立，根据图1的马尔科夫信道模型，在给定信道状态先验知识为γ（t）的条件下，第t个时隙选择信道 a 所获得的奖励值为（ωa（t）βa+（1+ωa（t））αa）Ba，它表示的是第t个时隙选择的信道a可用的概率。故贪婪算法的信道选择策略可依据以下公式计算：

在t时隙结束时，置信矢量可以根据以下公式更新。

此时，如果主用户信道未被次用户检测到，那么其可用概率根据马尔科夫过程更新，如果检测到，其可用概率将以次用户检测的结果为准。文献[7]中给出了贪婪算法的计算复杂度，并且具体阐述了如何在系统性能和计算复杂度之间互换权衡。

由于贪婪算法只关注每个时隙当前的奖励值，并不关心未来时隙信道的奖励值，这是其不足之处，即具有自私性。在每个时隙开始时，各个信道具有相同的初始置信矢量，若只关注瞬时奖励值，被检测的信道出现相同奖励值的可能性就会很大。假设网络中有N条信道，若出现了N-2个相同最大奖励值的信道，在文献[5]中作者指出，该情形下次用户会在N-2个信道中随机选择，此时在N-2个信道中的随机选择与直接使用随机算法结果很相似。另外，在多个次用户同时存在时，可能出现多个次用户同时选择了相同的信道接入，那么碰撞将不可避免的发生。针对上述情形，我们提出一种改进的算法，算法的中心思想是：假设出现了条具有相同最大奖励值的信道，则在瞬时奖励值的基础上加上这M条信道下个时隙的奖励值并依据最大奖励值公式重新计算最大奖励值。重新选择信道 b 所获得的奖励值为（ωb（t）βb+（1-ωb（t））αb）Bb，这里b∈{1，2，…，M}，此时最佳接入策略将依据下式进行选择，

在t时隙结束时，置信矢量的更新同样依据下面的公式：

该算法实际上是一个迭代累加的过程，如果在M条信道中依据公式 （6）计算出的信道的最大瞬时奖励依然有大部分相同，则再累加信道下一个时隙的奖励值，直到选出最优的信道。

3 计算机仿真

设置信道数N=10，带宽B=1，信道状态转移概率{α=0.2，β=0.8}，信息到达率 λ：λ 从 0.02到 0.2，每隔 0.02取一个点，仿真总次数为200次，时隙总数T=100。首先，在单次用户时对贪婪算法和改进算法中最大奖励值相同的信道出现的个数进行统计对比，如图5所示，从图5中可以看出，改进后的算法明显降低了最大奖励值相同的信道出现的个数。最后，为不失一般性，仿真将分别设置为单次用户、两次用户、三次用户的情景，并对随机算法、贪婪算法、改进算法进行仿真，仿真结果如图6~图8所示。

图5 单次用户时贪婪算法和改进算法出现最大奖励值相同的信道数的统计对比图Fig.5 The number of channel which has the maximum reward of the greedy algorithm and improved algorithm

图6 单次用户时3种算法的次用户吞吐量Fig.6 The throughput of three algorithms when single user

从仿真结果中可以看出，贪婪算法始终优于随机算法，而改进的算法在单次用户时吞吐量有较大的提升，并且始终优于随机算法和贪婪算法。在两次用户时提升幅度又有所下降，当信息到达率约为0.13时次用户吞吐量与贪婪算法的相同，但之后又开始上升。在三次用户时吞吐量的提升幅度变的更小，有多处与贪婪算法相同，甚至在信息到达率低于0.06时其性能不及贪婪算法。这是因为：假设信道数目不变时，随着次用户数的增加，多个次用户竞争接入信道，这将导致一定的冲突，从而造成系统性能的下降。

图7 两次用户时3种算法的次用户吞吐量Fig.7 The throughput of three algorithms when two users

图8 3次用户时3种算法的次用户吞吐量Fig.8 The throughput of three algorithms when three users

4 结 论

文中首先分析了基于POMDP的最优频谱接入策略，POMDP算法利用历史累积的频谱检测信息和信道统计状态作为先验知识来选择信道，明显提升了系统的吞吐量，但POMDP算法对硬件的要求较高，在信道数较多或频谱环境较复杂时算法的复杂程度不可估量。故在POMDP算法的基础上考虑了贪婪算法，但贪婪算法又具有自私性，因此文章针对其自私性做了改进，使得接入策略更优化。改进的算法相比于贪婪算法增加了一些计算复杂度，却有效提升了系统的吞吐量，具有一定的适用性。然而，从仿真结果图中可以看到，当次用户数增多时，由于多个次用户将竞争接入信道而造成一定的冲突，这使得算法的性能有所下降，后续的工作需要深入研究该问题以找到解决的方法。卫星群组网中，每颗卫星都配备认知无线电终端，不同的卫星根据处理的业务的主次不同、重要程度不同被定义为主用户和次用户。因此，本文提出的算法也可考虑用于卫星组网MAC协议设计中的信道接入算法。

[1]Mitola Joseph，Maguire，G Q.， Jr.， Cognitive radio:making software radios more personal[J].Personal Communications，IEEE，1999，6（4）:13，18.

[2]Cormio C.A survey on MAC protocols for cognitive radio networks[J].Ad Hoc Netw，2009，7（7）:1315-1329.

[3]HUANGSen-hua，LIUXin，DINGZhi.Opportunistic spectrum access in cognitive radio networks[J].IEEE INFOCOM 2008 Proceedings，2008:2101-2109.

[4]ZHAO Qing，LANG TONG，Swami A，et al.Decentralized cognitive MAC for opportunistic spectrum access in ad hoc networks:A POMDP framework [J].Selected Areas in Communications， IEEE Journal on，2007，25（3）:589-600.

[5]Richard D，Smallwood，Edward J.Sondik.The optimal control of partially observable Markov processes over a finite horizon[J].Operations Research，1971:1071-1088.

[6]Zhao Q，wami A，Chen Y.Decentralized Medium Access Control Protocols for Dynamic Spectrum Access:Decision Theoretic Framework[J].2006:284-286.

[7]CHEN Yunxia，ZHAO Qing，Swami A.Distributed cognitive MACfor energy-constrained opportunistic spectrum access[J].Military Communications Conference，2006.MILCOM 2006.IEEE，2006（7）:23-25.