基于预售机制的动态频谱分配算法研究

刘觉夫，陈 晓

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

0 引 言

无线业务的迅速增长及高速化和宽带化的需求使得无线频谱资源变得日益紧张，甚至成为制约其发展的瓶颈之一［1］。然而，已分配给用户的频谱资源却在时间或空间上存在不同程度的闲置，导致大量 “频谱空洞”存在。认知无线网络被认为是下一代无线网络的核心架构之一，该网络能解决日益增长的频谱使用需求和低下的频谱使用率之间的矛盾［2］。通过伺机接入临时可用频谱资源，大幅度提高频谱利用率。频谱资源分配是影响频谱资源利用率的关键，因此如何合理高效地管理和分配频率资源成为一项艰巨而又紧迫的任务。

传统的静态频谱分配（FSM）方法简单，干扰性小，但频谱利用效率低，难以满足日益壮大的无线用户的各种需求，于是动态频谱分配（DSM）成为国内外的专家学者的研究重点并提出了多种具体分配模型和算法，例如，Cao等人基于定价拍卖模型，采用公平的业务保证机制并提出了本地议价算法，提高了频谱分配的公平性，降低了系统的复杂性［3］；zheng等人提出使系统的性能、复杂度和通信成本取得折衷的基于规则的频谱管理方案［4］；陈杰、张平等人提出的基于讨价还价博弈的动态频谱管理方案等［5］。本文基于认知无线网络的架构，在动态频谱分配中引入了经济活动中的预售机制，提出基于预售机制的动态频谱管理（PS－DSM Presell－DSM）方案，该机制充分利用了不同网络在不同时间和空间维度上对频谱需求的差异及在网络通信时的闲置计算能力，以提高频谱资源利用效率。仿真结果表明，该种分配算法能够减少分配延迟、提高分配效率和频谱利用率。

1 PS－DSM系统模型

1.1 PS－DSM 架构

PS－DSM的基本架构包括逻辑频谱交易市场、交易双方和信息交互信道，其中，频谱交易市场来源频谱池［6］的概念并可根据交易对象性质划分为三级，最高级为不同运营商之间进行频谱交易的顶级市场（top market，TM），中级为单运营商多个RAT（无线接入网）进行频谱交易的中级市场（middle market，MM）。第三级为同构网络内部进行频谱交易的基础市场（basic market，BM）。三级市场之间的关系如图1所示。若某个RAN或网内用户的频谱资源在满足自身业务需求后仍有剩余，则它可以作为 “频谱出租者（SL）”在频谱市场上出租额外的空闲频谱以最大化频谱利用率和自身利润；若某个RAN或网内用户因业务的增长而缺少频谱资源，它将成为频谱市场的消费者，即作为“频谱租借者（SR）”从其频谱出租者中租用频谱以继续自身需求。

图1 三级市场关系

此外，交易双方需要了解一些必要的交易信息，如频谱租借者需要了解当前或下个周期内正在出租的可用频谱及这些频谱的质量参数，频谱出租者需要根据多个周期内的频谱交易量及其均价来制定预售价格等。作为公共信道，认知导频信道（CPC）［7］可被用来通知相关的交易信息。

PS－DSM是一种周期和前摄的频谱管理操作，不同等级的频谱市场采用不同粒度的时间量做周期单位。基础市场是本架构的基础，因此本文主要讨论基础市场中的频谱交易，其交易周期一般设为秒／分钟级，而中级和顶级频谱交易的周期则为小时级甚至天级。用τ表示交易周期，则对于集合T＝｛1，2，3，4……｝，时刻t和t＋1（t∈T）的时间间隔为τ，表示频谱出租和租用的最大周期为τ，需强调的是，t时刻的DSM对应t＋1时刻各用户提供的业务是必要的。

1.2 交易角色及其职能与收益

为完成频谱交易，每个市场中设置一个频谱服务中介站（spectrum agent，SA）。SA的主要职责为确定交易时钟并划分交易周期，在交易过程中，借助CPC广播本周期及下个周期内正在招租的频谱信息及其质量参数等，确保交易双方能够了解交易信息。SA在交易过程中起中介协调的作用。交易过程中的所涉及角色及其职能、收益计算见表1。

表1 交易角色职能收益

2 PS－DSM方案实现

PS－DSM采用周期运行方式，在频谱等级划分确定的基础上，每个周期内，方案实现主要有4个关键环节：SL频谱定价、SA价格调整、SR博弈选择、SR评价反馈。

2.1 频谱等级划分

SL上报出租的频谱质量和适用业务状况各不相同，为减小SR频谱选择复杂度，SA将招租频谱根据其业务参数进行等级划并按其质量由高到底排序，为简化计算，本文将频谱设为4个等级：A1、A2、B1、B2，其中A代表实时性业务，B代表非实时性业务，1代表高质量层，2代表低质量层，例如A2代表适合实时性业务中质量要求稍低的频谱，如语音业务。频谱等级划定后，SR只需计算适合自身业务的频谱，从而减小了计算范围，节省时间，提高分配效率。

2.2 SL 频谱定价

SL将自身的空闲频谱信息上报至SA进行招租，其中包括描述频谱质量的各项关键参数与频谱价格c／单位，其制定是影响SL收益的关键因素，因此需进行多方面的考虑。根据供求价值规律，SR的频谱需求量越大，则c值应越高，需求量越少，则c值应越低，否则难以进行成功出租获取收益。SL进行频谱定价过程如下：首先收听SA广播3条记录信息：①前一周期的频谱出租比率Srpre及成功交易的平均价格ACpre；②当前周期已出租频谱的比率Srnow及成功交易平均价格ACnow，③SA基于时间序列预测算法的所得下一周期的频谱需求量Qnext；SL根据所收听的信息，使用定价函数进行频谱定价。

下一周期的频谱定价函数如下

式（1）由三部分组成，其中G（Qnext）代表SL自身的对频谱需求量Qnext的反应价格，不同的SL反应价格不同，c′为SL基于时间序列推测算法得出的推测价格，α和β为调节参数，利用其权重值对反应价格和预测价格进行调和，且α＋β＝1。ε为自定义常数，其取值由SL参考Srpre，ACpre，Srnow，ACnow和自身频谱质量进行频谱价格的上调或下降，其取值范围不超过前两项之和的百分之十

f（Srpre，ACpre，Srnow，ACnow，θ）（θ为信道质量标值）函数为ε的增函数，其参数值越大，ε的可选范围越大，代表频谱市场行情越好，SL可制定高质量的频谱价格。同时，令w代表SL对出租频谱的成本衡量，故而，必须保证cnext＞w条件成立，以保证SL频谱出租的可行性和积极性。

2.3 SA价格调整

频谱价格对SL收益计算起关键作用，定价c越高，则SL收益越大，从博弈论的角度出发，每个活动参与者都是理性的，即以最大化自身收益为目标，如此则会出现SL垄断市场并肆意制定过高价格的危险，为保证SR的利益和交易公平，SL基于自身判断制定频谱价格c，上报到SA中广播招租，在该信息被广播前，SA读取数据库中该用户招租信道的评信息进行价格调整。信息评价数据库设计见表2。

表2 频谱评价

为方便计算，评价采用百分制，在租用周期结束后，认知用户对租用信道进行评分并发送给SA，然后，SA更新该信道评价均值及评价次数ni。SA对SL的频谱出价c的调整策略如下：（ci表示第i条信道的频谱定价）

由上式可得出，若存在SL为扩大自身利益为故意提高价格或价格与信道质量不相符的情况，SR使用后给予信道真实评价，评价越低，则评价均值越低，SA根据数据进行调整后的价格越低，如此的评价机制和调整机制能更好的保证SR利益和SL的频谱价格真实合理，维持良好的交易秩序。

值得指出的是，c＊i为下一周期的频谱i的价格，下一周期开始后，下一周期频谱招租表自动转换为当前周期频谱招租表，若表内仍含有未出租的频谱，则SA自动将此些频谱价格提高，由于此时进行招租的频谱量定会小于等于其作为下一周期进行招租的频谱量，SR出于自身需求，选择在本周期内租用频谱，遵循价值规律，SA将频谱价格提高3%，并收取2%作为自身收益，如此也保证了SL的收益。

2.4 SR 博弈选择

PS－DSM方案实现的关键环节是SR频谱选择，即详细频谱分配问题，目前，常见的频谱分配模型有图论着色模型、竞价拍卖模型和博弈论模型，与其他模型相比，博弈论模型更加适合研究复杂度高，动态变化的分布式认知无线网络频谱分配策略选择问题，其应用严格的数学模型来研究参与者之间利益相互制约下的互动决策。国内外的众多学者也采用多种博弈方法对频谱分配问题做了大量的研究，如Neel等人首先提出使用博弈理论来研究认知无线电相关问题的基本模型和方法，并使用这些模型分析了频谱分配、功率控制、呼叫准入控制和干扰避免［8］。其他学者又提出了基于伯川德模型［9］、古诺模型、部分可观察马氏链决策博弈［10］的频谱分配模型等。本文首先运用分治思想，让SR根据自身需求与能力，选择对口频谱等级，将整体博弈转换为4个子博弈，结合公平性，求解子博弈纳什均衡。分而治之，加快收敛速度，得出最优选择。（考虑基础市场）针对子博弈，设计了基于超模博弈的频谱分配算法，该算法以最大化系统吞吐量为目标，设计效用函数。详细内容参加下文 “4基于超模博弈的频谱分配算法”。

2.5 SR与SL沟通

SR结合自身业务需求及支付能力，从A1、A2、B1、B2这4种频谱等级的队列中选择相符度最高的一列进行排队，同时收听广播，若自己的最优选择已被他人租用，则立即改变策略，选择下一最优策略，若在自身得到沟通机会前，可选队列已空，则退出，重新计算并构建可选队列后，再次排队。

在排队过程中，设优先级，为当前周期排队的SR属于Level 1，为租用下一周期频谱排队的SR属于Level 2，Level 1高于Level 2，SR针对自身需求在各自的队列基于优先级排队，后到来的高优先级者自动插入到低优先级者前面，同级SR则按照时间顺序进行排队，整个队列按照优先级由高到低有序排好，保证算法正常进行。

2.6 SR 评价反馈

在交易结束后，由SR对所租用的频谱进行评价打分，并反馈至SA，SA计算后更新数据库记录和ni。

2.7 PS－DSM 方案执行步骤

本文提出的基于预售机制的动态频谱分配算法具体执行步骤如下：

步骤1 SA确定交易周期τ并广播，当SL与SR（如无线认知设备）开启时，接收SA广播信息，调节自身交易时钟并确定当前所处的周期，确保与SA时钟同步。这是进行频谱交易的第一前提。

步骤2 在于SA时钟同步的前提下，SL自己对当前及下一周期内的空闲频谱进行定价，并将该频谱的相关信息上报至SA进行挂牌招租。

步骤3 SA读取数据库中评价信息，对新上报的频谱价格进行价格调整，然后将该条招租记录添加至 “招租信息表”并广播。 “招租信息表”包括 “当前周期招租信息表”和 “下一周期招租信息表”，其设计结构相同，具体如表3所示。

步骤4 SR接收SA广播信息，根据 “招租信息表”中的数据计算得最优选择，并选出3个可选SL按最优性由高到低组建自身候选队列。

步骤5 SR根据频谱等级排队竞争公共控制信道，与SL进行沟通。在排队的同时监听 “招租信息表”中自身最优选择的状态，若该条记录被其他用户租用，则立即改变沟通策略，从自身候选队列中选择次优策略进行沟通，若在自己得到沟通机会前，自身候选队列已空，则退出队列，重新计算并组建新候选队列后继续排队。

步骤6 针对预售机制，提出了双方安全租借和诚信租借的要求，于是，设计使用交易密钥。SR与SL进行沟通，商定交易密钥。然后SL向SA发送该信道已经出租的消息，SA更改该信道状态为 “已租”，同时接收SR付款。若SR与SL沟通失败，则跳转至步骤4继续执行算法。

步骤7 租用周期开始，SR拿着商定的交易密钥进行“敲门”，SL核定本周期内的交易密钥，然后允许SR使用频谱，保证通信和频谱交易的安全可行。

步骤8 租用周期结束，SR对使用的信道进行评分，反馈至SA，SA更新该信道评价记录并将此次交易款额划拨给SL。

值得指出的是，在步骤6中，同时进行选择的多个SR均与SL成功沟通后，一次博弈结束。后重复过程，直至系统达到纳什均衡。在步骤7中，SR使用频谱进行通信的同时，继续收听广播信息，为自己下个周期的所需频谱资源进行租用计算和沟通。将计算能力充分调用，减少时延，提高频谱利用效率。

表3 招租信息

3 基于超模博弈的频谱分配算法

SR频谱选择是PS－DSM方案实现的关键环节，多个SR以自私地竞争的方式来抢占SL出租的频谱资源，以期最大化自身收益，且其决策时完全独立，因此，可以将多个SR的频谱选择行为描述为的一个结合公平性不完全信息下的博弈模型，博弈的参与者为SR，博弈参与者的策略空间为SR的可选频谱集，寻找博弈纳什均衡解，找出相应分布式的最优解决方案。

3.1 系统模型

仅考虑基础市场的单认知网络，设SL和SR个数分别为M个和N个，且随机分布在D×D的方形区域中。可用信道数为K个，SRi和j在信道K上的发射功率分别为pik和pjk，当k选择信道时，hiik为SRi的发射机到接收机的链路增益，hjik为SRj发射机到SRi的发射机的链路增益，Gimk表示SRi到SLm的链路增益，A（i，k）为信道分配矩阵元素，其个数为N×K个，若信道k被SRi租用，则A（i，k）＝1，否则A（i，k）＝0。n0为背景噪声功率。则第i个SR在信道k上接收机处的信噪比定义为

由香农公式可得，第i个SR在信道k上的吞吐量为

SLm受到信道k上的SR干扰Imk为

3.2 频谱分配博弈模型

频谱分配问题的博弈数学描述一般形式如下

式中：N——博弈参与者的有限集（在本博弈中为N个SR）；Si——博弈者i的可选策略集合，定义S＝×Si，i∈N为策略空间，则Ui：S→R为效用函数集。在博弈Γ中，每个博弈者i的效用函数Ui为Si及其对手S－i的函数。

由于博弈者独立进行决策，并受到其他博弈者决策的影响，则博弈结果分析的一个关键问题即判断该信道选择算法是否存在收敛点，且该收敛点对于任何一个博弈者而言都不会产生偏移，若存在一组策略，S＝｛s1，s2，…sN｝，当且仅 当Ui（si，s－i）≥Ui（si′，s－i），i∈ N，si′∈Si时，该组行动向量就是纳什均衡（NE），一般而言，这个纳什均衡点便是策略最优点。

3.3 效用函数设计

选择一个合适的效用函数将对SR的博弈行为产生本质的影响。在本非合作博弈中，每个SR都是理性参与人，选择对自己收益最大的信道进行选择后租借，其效用与所选择的信道质量相关，以系统总吞吐量作为信道效用值，则效用函数描述如下

由于博弈中的每个用户都是自私的，只关心自身利益的最大化，而不考虑其它用户的需求，这会使获得的纳什均衡可能不是系统的最优点，于是添加代价函数，既真实的反映出SR租借频谱获得收益的同时所付出的代价，也保证了SL的利益，快速找到最优均衡点。SRi在时间段t内的租借信道k的代价函数为

式中：Itotal——SL受到SR的干扰和，α——常量比例系数。——信道k的广播招租价格，为非负常数。定义效用函数时将代价函数考虑在内，对SR进行惩罚，可以防止其一味增大发射功率，减少对其他用户造成干扰，引导其合理利用网络资源。

因此，可得最终效用函数为

3.4 稳态判断

文献［11］提到，对于认知无线网络，设计合适的博弈算法首先要保证网络存在稳态，而且这种稳态应具有好的性能；其次博弈算法能够快速地收敛到性能最优的稳态。对于具有有限行为空间的标准形式博弈，可以通过有限改进路径（FIP）特性及弱有限改进路径（弱FIP）特性来确定其收敛性。稳态即纳什均衡点（NE），在实际中，确认一般标准形式博弈或重复博弈的稳态比较困难，可以使用更高级的博弈模型，如位势博弈和超模博弈，这两种博弈模型可以有效地简化NE确认过程。

所谓超模博弈，是指行为空间组成格子且效用函数具有超模性的博弈模型。通过分析可得，本文所设计的博弈算法属于超模博弈，以下将分两步证明：

（1）行为空间组成格子：设集合X，如果其满足：①X是部分有序集，② min｛x，y｝∈X；max｛x，y｝∈X，x，y∈X；则称X为格子。本文中，SR根据广播的频谱信息进行频谱选择，显然其行为空间可组成格子。

（2）效用函数具有超模性：设函数f：X→，其中X是格子的。如果满足式（14），则称f在X上是超模的

本文所设计的效用函数具有超模性，证明如下：

（1）ui（si）＋ui（si′）＝

（2）ui（si∨si′）＋ui（si∧si′）＝

由上可得：（1）＝（2）即：ui（si）＋ui（si′）＝ui（si∨si′）＋ui（si∧si′）满足超模函数的定义。

证明结束，本博弈为超模博弈。依据超模博弈的性质，任何一个超模博弈必然存在一个纯策略纳什均衡。

3.5 最优发射功率求解

效用函数受到发射功率影响，当发射功率越大对SR本身的效用越大，同时带来的干扰越大，如此无法保证整个网络性能的最优性，因此，需求解一个合适的发射功率，保证SR本身及整个网络性能的最优化，最佳发射功率求解如下：

对效用函数U2一阶求导

SR时时收听广播信息，求解发射功率过程随信道分配矩阵动态变化。

4 仿真实验与性能分析

应用本文基于预测机制的动态频谱分配算法，使用matlab 7.0进行算法仿真。仿真的基础市场认知无线网络场景为：在300m×300m的范围内。周期内随机固定分布50个SR和4个SL。每个SR和SL可看作一个发射—接收点对，不同SR发射机和接收机之间的距离在［50，300］m内随机取值，同SR的发射机和接收机距离在［1，50］m内随机取值，下一周期内招租信道有10个，信道1－信道10。SR所选择信道未被其它用户占用时其初始发射功率为p0＝80mW。不同通信等级的SR竞争使用4个公共控制信道与SL沟通，控制信道不受主用户影响。背景噪声功率n0＝－100dB，链路增益为h＝ω／d4，且ω＝0.097，比例系数α＝200。为方便计算，信道频谱等级初始设定见表4，各SR频谱等级需求初始设定见表5。

表4 信道频谱等级初始设定

表5 SR频谱需求等级初始设定

4.1 算法收敛情况

图2展现出基于超模博弈的频谱分配算法作用下，各SR策略收敛情况。横坐标表示博弈次数，纵坐标表示SR可选择的策略，信道k＝｛k＝1－10｝。可以看出，在算法执行了约45个算法周期后，各SR选择选择信道的策略稳定。系统达到纳什均衡状态，与博弈论的推导结果一致。

4.2 SL所受干扰情况

图3给出了采用效用函数U1和效用函数U2对SL的干扰曲线图，结果表明采用U2作为效用函数时，引入抑制SR自私行为的代价函数，SL所受干扰明显低于采用U1作为效用函数时所受的干扰。

4.3 系统吞吐量比较

在算法仿真过程中，分别对以U1和以U2为效用函数时算法的吞吐量进行测量，验证了本文提出的算法有助于提高系统性能。如图4所示。采用效用函数U2，划分子博弈与没有划分子博弈的吞吐量比较如图5所示，可得，通过子博弈划分，可加快达到均衡速度，且吞吐量略有提高。

5 结束语

本文基于认知无线网络环境，提出并详细阐述了基于预售机制的动态频谱管理（PS－DSM）方案。在本方案中，频谱市场被划分为三级，针对基础市场的频谱分配博弈方法和仿真进行了细节描述。结果表明，本方案虽然增加了算法的复杂度，但是有效的提高了频谱分配效率，减少时延。但是，在分配算法上的细节考虑仍需要进一步的完善，以及高级市场的分配算法成为亦下一步的研究重点。

图5 系统吞吐量（2）

［1］LI Wenbian，LIN Yuewei，WANG Xiaomeng，et al.A microeconomics based dynamic spectrum management algorithm for cognitive wireless networks［J］.Journal of Electronics ＆ Information Technology，2009，31（4）：897－902（in Chinese）.［黎文边，林粤伟，王小猛，等.认知无线网络中基于微观经济学的动态频谱管理算法［J］.电子与信息学报，2009，31（4）：897－902.］

［2］FENG Zhiyong，ZHANG Ping，LANG Baozhen，et al.Cognitive wireless network theory and key technology［M］.Beijing：Posts ＆ Telecom Press，2011（in Chinese）.［冯志勇，张平，郎保真，等.认知无线网络理论与关键技术［M］.北京：人民邮电出版社，2011.］

［3］Cao L.Distributed spectrum allocation via local bargaining［C］／／IEEE Sensor and Ad Hoc Communications and Networks.Santa Clara，USA：IEEE Press，2005：475－486.

［4］Peng Chunyi，Zheng Haitao，Ben Y Zhao.Utilization and fairness in spectrum assignment for opportunistic spectrum access［J］.Mobile Networks and Applications，2006，11（4）：555－576.

［5］CHEN Jie，ZHANG Ping.A game－based dynamic spectrum management for heterogeneous wireless system［J］.Radio Engineering，2008，38（3）：9－12（in Chinese）.［陈杰，张平.异构无线系统中基于博弈的动态频谱管理［J］.无线电工程，2008，38（3）：9－12.］

［6］JIANG Lie，GAO Yuehong，ZHANG Xin，et al.Spectrum pooling in the cognitive radio［J］.Modern Science ＆ Technology of Telecommunications，2011，4（4）：42－45.（in Chinese）.［江磊，高月红，张欣，等.频谱池在认知无线电中的应用［J］.现代电信科技，2011，4（4）：42－45.］

［7］CORDIER.P.E2Rcognitive pilot channel concept［C］／／IST Summit.Mykonos，2006：22－26.

［8］Nie N，Comaniciu C.Adaptive channel allocation spectrum etiquette for cognitive radio networks［C］／／Proceedings of the 1st IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks.Baltimore，MD，USA.Piscataway，NJ，USA：IEEE，2005：269－278.

［9］ZHAO Q，TONG L.Decentralized cognitive MAC for opportunistic spectrum access in ad－hoc networks：a POM DP framework［J］.IEEE Journal on Selected Areas in Communications.2007.25（3）：589－600.

［10］Huang J，Beery R，Hong M，Auction－based sharing［J］.Mobile Networks and Applications，2006，11（3）：405－408.

［11］WANG Jinlong，WU Qihui，GONG Yuping，et al.Cognitive wireless networks［M］.Beijing：China Machine Press，2010（in Chinese）.［王金龙，吴启辉，龚玉萍，等.认知无线网络［M］.北京：机械工业出版社，2010.］