基于满意度的动态频谱分配问题研究＊

李晓月，戴 冬

（河南机电高等专科学校计算机科学与技术系，河南新乡453000）

基于满意度的动态频谱分配问题研究＊

李晓月，戴 冬

（河南机电高等专科学校计算机科学与技术系，河南新乡453000）

针对频谱资源的有效利用问题，提出了利用动态调整频宽技术建立频谱分配模型，通过降低服务等级的方式服务所有的次用户。考虑到物理层协议的重要性，为多个次用户组成的集中认知无线网络设计了一个MAC协议，以满足异构频宽的需求，并来验证动态频谱分配模型。实验结果表明，该模型和固定频宽模型相比，频谱利用率提高了38%，公平度是90%。

认知无线网络；动态频谱分配；频宽；满意度模型；MAC协议

2002年FCC（美国联邦通讯委员会）发布授权频谱报告后［1］，频谱利用率问题得到了越来越多学者的关注。认知无线网络被认为是一个解决有限频谱资源和越来越多无线应用之间矛盾的有效方法。通过伊利诺斯学者的评测［2］和发现［3］［4］可知，在当前的频谱管理策略下，频谱并不能得到有效的利用。

为了提高频谱利用率，很多学者研究动态频谱接入问题，其大致可以分为两类：一类是次用户可以利用授权的频宽，即使是在主用户（Primary Users，PUs）存在的情况下，前提是能保证当前的授权终端数量不超过预设的阀值［5］。另一类是机会频谱接入，例如，次用户（Secondary Users，SUs）不在同地或同时利用与主用户相同的频率，两者必须等待时机，在不同的时间或频率间来回跳动。文献［6］和［7］分别用贪婪算法来提高频谱利用率，两者主要的缺点是过于简化了二态干扰模型，简单地把基站的重叠归于重叠或者不重叠两类。文献［8］通过信号与干扰加噪声比（Signal to Interference plus Noise Ratio，SINR）而不是用标准图色方法，但是没有考虑到SUs的公平性。文献［9］创建了一个模型用来最大化SUs的传输率，以及对PUs的功率限制，文献中还引入了SUs的中断概率和主用户的干扰限制违反概率。文献［10］在文献［9］的基础上定义了一个新的概念满意度模型（等同于SINR和期望值的比率），以研究SINR的平衡问题。文献［10］［11］中的频谱分配算法采用需求大的频宽终端接入优先，而不是下一个适合优先，但这种方法在不同目标优化的情况下，并不一定比下一个适合优先算法更优。文献［12］把频谱分配当作一个多重背包问题，提出了一个低复杂度的贪婪算法，来解决所有SUs的传输率最大化问题。对于集中认知无线网络问题，本文选择调整频宽而不是选择调整功率，其原因主要有以下两方面：首先，功率的变化会干扰其他的PUs和SUs，使通信协议变得非常复杂。其次，根据香农定理，频宽和容量之间有相近的关系。通过建立一个新的动态频谱分配模型（Satisfaction Degree Model，SDM），分配给所有需求节点一定数量的频宽比例，以满足终端的需求，保证所有SUs的公平性。最后，设计MAC协议来验证SDM。

1 系统描述

本文研究的系统模型是由一些认知节点组成的集中认知网络，这些节点包括一个中央控制节点（Central Control Node，CCN）和SUs。不同的SUs之间要互相通信，比如通话、文件共享和视频传输，其场景如同移动蜂窝网络。在第三代移动网络应用中，异步数据传输率与频宽有很大的关系。因此，在一个基站允许的范围内，接入用户数越多越好，因为越多的用户意味着越多的利润。

图1中的CCN拥有两个无线频道：一个用来对普通SUs广播控制信息，并收集SUs在固定的控制信道下发起的频宽需求数据；另外一个用来感知频道的宽度。对所有的SUs而言，一个无线频道就可以发送需求和等待分配结果。如果有需要的话，可调至另外一个信道进行数据传输。CCN负责查找可以利用的频率，并将这些资源分配给SUs。

图1 网络应用情景

本文的系统模型中，SUs中间有很多通信节点对，每一对都有不同的频宽需求。由于SUs之间会相互干扰，每个SU得到的频宽不能重叠。因此，就可以避免同波道干扰，SINR也就可以简化为SNR。现在出现了一个问题：如果信道的宽度是变化的，它对SNR的影响以及传输范围又如何呢？下面的公式能够回答这个问题。）

公式（1）中的Eb代表传递一位信息所需要的能量，n0代表噪音的PSD（功率谱密度），Rb代表信息传输位率。因为功率在频率上是PSD的积分，所以同一个地方整个频谱的噪音PSD是一个常量。这样，既可以增加功率，也可以降低信道宽度来保证SNR比预定的阀值高。本文选择在固定功率的情况下调整信道宽度，而非调整功率，是因为功率的波动会提高影响其他潜在通信节点的概率。

为了方便描述，需要形式化动态频谱分配问题。在指定的一段时间内，Ld表示频宽需求队列，Ls表示频谱资源队列，他们的长度分别是N和 M。每次需求i属于Ldi＝1，2，3……N，有相应的需求频宽Wi，每个频谱宽度k属于Lsk＝1，2，3……M的初始容量为Ck。每次请求既可被CN N节点允许，也可在资源紧缺的情况下拒绝，如果被拒绝，SUs必须再次发送请求。目的是找到Ld的一个分区，以确定允许集A和拒绝集R。基于频谱感应结果来获得频宽需求，主要的问题是用什么样的方式来利用频宽，才是最好的方式。

2 动态频谱分配

给大量的SUs分配多段频谱可以看作是装箱问题，其与经典的装箱问题唯一的不同点是：不是找到最少的箱子数来装所有的物品，而是考虑更实际的拟合问题。

上述问题，当前普遍认同的两种最优模型是基于频谱利用率和数据传输率。频谱利用率由分配和可用的频谱资源来衡量，文献［6］［10］［13］［14］尝试寻找在一定约束下的最优值。本文不太认同文献［8］［9］［12］根据所有SUs数据传输率或者SINR来分配频谱资源的做法，因为数据传输率不仅仅和频宽有关，还与调制方式有关，不同的SUs采用不同的调制方式。

2.1 满意度模型

本文提出一个新的基于异构频宽需求的满意度模型，此模型可以按照一定比例服务于所有SUs的需求。本文的满意度可以理解为折扣，其等于实际获得的频宽和需求之间的比率。与文献［9］相比，该模型中的满意度由频宽衡量而不是通过SINR，对所有的SUs均是唯一的，并从整个网络的角度来计算。

公式（2）中参数γ属于［0，1］范围内的优化目标，第一和第二约束分别由每个SU的角度和频谱宽度来构造。约束（3）保证只有一个箱子存储项目i，并保证每个i都被装箱。约束（4）保证分配给该箱子的总权重不会超过其容量界限。布尔类型的变量ak，i标识频宽（箱子）k存储了需求频宽（项目）i。

2.2 频谱分配算法

装箱问题是一个NP问题，学者们寻求更有效的启发式算法来获得满意结果，多数情况下结果良好，但有可能不是最优解。这些算法包括首次适应（First－Fit，FF）、下次适应（Next－Fit，NF）、最佳适应（Best－Fit，BF）、最差适应（Worst－Fit，WF）和几乎最差适应（Almost－Worst－Fit，AWF）算法［15］。

为了方便问题描述，上述启发式算法简介如下：FF算法可以快速获得结果，但不是最优解；NF算法是在当前箱子尚有空间但容量不足的情况下，打开一个新的箱子；BF算法遍历所有打开的箱子，将当前物品放进最合适的箱子，最合适指的是在所有打开的箱子里面装下该物品后剩余空间最小的箱子，如果没有合适的箱子，就会打开一个新的箱子；降序首次适应算法（MFFD）是另一种非常重要的改进算法。文献［16］中表明FFD算法的有效界限是11／9OPT＋6／9（OPT是最优解的箱子的数量），文献［17］MFFD算法的有效界限不超过71／60OPT＋1。文献［18］把此问题简化为n背包问题，并提出了多项式时间近似算法。因该方案对请求被拒绝的情况下有惩罚因子，本文不会借用此算法。

本文用二分查找适应度算法应用于SDM，重点放在用装箱问题来解决频谱分配问题，而不是进行理论分析。

输入：当前阶段的SUs的频宽需求队列为Ld，可用的频谱资源队列为Ls，Ld的长度｜Ld｜＝N，Ls的长度｜Ls｜＝M，对每个i∈Ldi＝1，2……N都有相应的权重Wi，对每个频宽k∈Ls k＝1，2……M有初始空间Ck。

输出：适应度γ是Ld中的需求i和LS中频宽k之间的匹配关系。

步骤1：初始化γlow＝0，γhigh＝1。全局迭代变量iter初始化值为itermax。没有装箱队列L－not Packed＝Ld。

步骤2：γ＝（γlow＋γhigh）／2；

步骤3： whileγlow≤γhighand iter＞0 do iter＝iter－1；

For Ld中的每个i，Wi＝Wi＊γ

从集合｛FF；NF；BF；MFF｝选择一个算法and

return没有装箱的到列表

if L－not Packed不为空then

γhigh＝γ；

return to步骤2。

else

γlow＝γ；

return to步骤2。

end if

end while

if L－not Packed不为空then

return－1；｛在一定的迭代范围内没有合适的γ可以满足所有的装箱需求｝

else

returnγ；

end if

该算法把二分搜索和装箱算法组合到一起，返回最大的参数γ，系统可以接受所有的请求，并给每个请求节点一定比例数量的资源以满足需求。

3 动态频谱接入

本文系统模型由一个CCN和多个普通认知节点组成，下面对不同类型的节点进行状态和时槽划分定义。

3.1 状态定义

CCN拥有两个无线频道：一个用来对普通SUs广播控制信息，并收集由SUs在固定的控制信道下发起的需求频宽数据；另外一个用来感知频道的宽度。换句话说，就是CCN同时用不同的无线频道来接受请求和分配频谱资源。因此，命名此状态为Wait（等待），另外一个重要状态为Process（处理），CCN根据一定的算法来分配频谱资源，完成分配后CCN节点Send（发送）分配结果到SUs。

每个允许接入的SU节点（活动节点）有四种状态，Communicate（通信），Sense（感知），Request（请求）和Wait（等待）。然而，由于某种原因，活动节点有可能收不到CCN的广播信息，这样的节点或者是首次接入的SU只有Request和Wait两个状态。各类节点的状态机如图2所示。

图2 状态转换进程

从图2（a）中可以清楚地看出，对每个CCN有三种可能的状态，起初是Wait状态，等待想要进行通信的SUs的请求，接到请求后CCN转换到Process状态，用另外一个频道分配频宽，最后利用控制信道把处理结果Send到SUs。

如图2（b）所示，如果网络中活动节点的请求得到CCN允许，就可以更改传输参数，将其传送给目标频率，并与想要进行数据传输的节点进行数据交换。当传输完成或者超时，发送节点转换到感知状态，接着打包新的频宽需求，并把感知结果打包到另外一个请求信息中。为了节省感知时间，活动节点只能感知到先前分配给它们的频宽。非活动节点包括：与CCN之间失去联系的活动节点；在先前的时间槽内发出请求信息但被拒绝的节点；新接入到网络中的节点。非活动节点的状态空间仅仅包含两个状态，如图2（b）中的虚线部分所示。非活动节点在Request和Wait之间进行状态转换，直到被CNN分配一定的频宽后才允许接入。

3.2 时槽划分

根据上述的状态机，本文每类节点的时槽划分如图3所示。

图3 各类节点的时槽划分

图3的时槽划分需要注意以下两点：第一，当CCN处于Sensing状态，其扫描的不是整个频宽，只是上个时槽中未分配资源，以及获取潜在的可用频谱资源，目的是能快速感应需求信息。活动节点协助CCN感知未分配频谱资源，每个活动节点只感知上次传输所用的频率。第二，每一个时槽的监听（感知）期是预定义和不变的，等于活动节点的通信、感知、发送请求时间的总和。然而，由于请求的数量和资源要求不确定，CCN的处理时间也不确定，CCN完成处理后立即通过控制信道将分配结果发送出去。

3.3 MAC协议设计

为了便于理解，并与802.11协议组保持一致，本文依旧采用术语请求发送（Request To Send，RTS）。对活动节点来讲，RTS包含需求频宽和当前频谱感知报告两部分；对非活动节点来讲，只包含需求频宽部分。CCN广播到SUs的信息包含哪些节点将工作在什么频宽、什么时间开始传输数据、MAC地址和其他信息。因此，任何包含目标接受地址的节点都可以监听到此信息。那些被允许接入并分配一定数量资源的SUs，在等待广播信息预设时间后，立即开始和目标节点进行数据通信，而那些没有被接受的节点，必须等待下次机会再次发送请求。最坏的情况是，那些由于干扰等原因，在前一时槽内没有接收到广播信息，必须等到超时后进行和新接入结点一样的操作。

这里强调两点：第一，在CCN监听阶段，各类SU可以像传统无线网络一样，利用二元指数后退算法来发送请求，考虑到效率问题，CCN不会发送收到信息到SUs。第二，没有必要对CCN设计同步策略和传输节点对，因为在数据传输开始之前，发送端和接收端等待时间和预设时间相同。对那些非连接节点，CCN只需把他们当作新加入节点即可。因为同步操作会消耗大量的资源（如频宽和时间），导致整个系统的性能下降。

4 实验结果

本文实验包含以下几个部分：参数和度量标准描述；可变频宽与传统定宽的详细比较；本文优化模型与几种不同装箱算法的分析对比。

4.1 配置

参数选择：假设物体数量、箱子数量和每个箱子容量参数遵循均匀分布原则，此类假设和文献［10］［11］中的类似。试验中，物体的数量以及箱子的数量分别遵循均匀分布原则U（20，40）和U（5，8），物体尺寸和箱子容量分别遵循均匀分布原则U（2，6）和U（8，15），固定的频宽是5MHz。

度量标准：频宽供求率是X轴，此度量标准反映了资源稀缺，其他度量标准详细的描述可以参看表1。

表1 度量标准描述

4.2 变频

本文利用可变频宽分配频谱资源代替当前流行的固定频宽方法，在此基础上实施了Variable－FF、Fixed Expand－FF和FixedIgnore－FF三种频谱资源应用模式。三种模式均采用FF算法，唯一不同的是频谱分配实现方面。Variable－FF利用可变频宽，而Fixed Expand－FF和FixedIgnore－FF把可用的频谱资源分配成预先定义好的频宽。更明确地讲，在每一个频谱分配进程中，Fixed Expand－FF把多个频道分配给那些需求大于设定值的SUs。然而FixedIgnore－FF忽略那些需求大于预设频宽的SUs，仅把频谱分配给那些需求频宽小的SUs。

SUs请求服务率随频宽供求率的变化情况如图4（a）表示。从图中可以看出，不管哪种算法，SUs请求服务率均随频宽供求率的增加而降低，所以增加频宽是无效的。这是因为频谱资源和处理率的限制，定宽方法比变宽方法的表现更差。对同样数量的频谱和相等数量的请求，与Fixed Expand－FF和FixedIgnore－FF算法相比，Variable－FF算法能服务更多的SUs，数量超过20%。从图4（b）中可以看出，Variable－FF算法的利用率比传统的定宽算法平均要高38%，而Fixed Expand－FF和FixedIgnore－FF算法的利用率几乎一致。

出现以上结果的原因主要有以下两点：第一，这三种算法在FF开始之前都没有预处理程序，因此Fixed Expand－FF算法顺序服务SUs，直到没有频谱剩余。那些频宽需求大的SUs会占用多个信道，很容易产生频谱碎片。FixedIgnore－FF算法忽略了那些对频宽需求大的SUs仅服务于需求小的SUs，因此无论需求大的SUs何时发出请求都不会响应。然而，变频可以提供更灵活的空间，即使现在的频宽满足不了需求，也可以把SU分配到其他的频宽中。第二，在传统的定宽技术中，每一个频道只能一个SU独占，而本文的变化频宽方法是连续地进行分配，可以避免产生频谱碎片。

图4 变化频宽方法的优势

4.3 满意度和公平度

为了获得最大的满意度，本文没有固定装箱算法，每次只是选择其一执行，执行结果对比如图5所示。

随着越来越多的SUs加入网络，频宽需求率随频谱资源的缺乏率上升而上升，必须用降低服务质量来满足所有的SUs，图5中的走势证明了此种猜测。几种不同算法的比较表明，FF和BF算法的性能相近，而NF算法最差。原因是BF算法总是把物品装进所有剩余空间最小的箱子里，而NF算法只比较当前有剩余空间的箱子（一个经济另一个浪费），从而导致满意度有所不同。图中FF和MFF算法之所以与本文第三部分的分析结果不符，是因为本文没有在装箱前进行预处理，而MFF算法事先对SUs频宽需求进行了降序排列。

图5 不同算法间的满意度对比

图6是不同算法间的公平度对比，Satisfaction Degree－FF表示在SDM中利用FF装箱算法，FF、MFF、BF和NF则是其他装箱算法。公平指数通过公式来计算，其中Ci表示每个SUs获得的频宽。显而易见，Satisfaction Degree－FF是最公平的算法，因为所有SUs的请求都可以获得一定的频谱资源，与FF、MFF、BF和NF算法相比，分别提高了36.4%、46.3%、44.9%和45.5%。最重要的是，其他几个算法的公平系数随着频宽供求率的提高迅速下降，而本文的公平度一直维持在90%左右。

图6 不同算法间的公平度对比

5 结语

本文采用调整通信频道宽度而非改变功率的方法分配频谱资源，可以降低影响潜在通信的概率。提出的动态频谱分配模型SDM服务于集中认知无线网络，通过降低服务等级的方法，响应所有通信请求，并保证各个SUs之间的公平性。在此基础上，设计的通信协议用来验证SDM。实验结果表明，与固定频宽模型相比，本文模型在频率利用率方面提高了38%，公平度是90%。

对于动态频谱分配问题，本文只是做了初步研究。怎样把需求频宽大的SUs分到几个不同频宽中，如同OFDM，在几个频宽中同时通信。如何把SUs划分成不同的组，并分配不同的满意度也是很棘手的问题。

（责任编辑 吕春红）

［1］F.C.C.S.P.T.Force.Report of the spectrum efficiency working group.Federal Communications Commision［R］，Technical Report，2002.

［2］D.A.Roberson.Structural support for cognitive radio system deploy－ment［C］.In Proceedings.of International Conference on Cognitive Radio Oriented Wireless Networks and Communications（CROWNCOM），Orlando，FL，USA，2007.

［3］Qian Zhang Mingyan Liu Shufang Li Dawei Chen，Sixing Yin.Mining spectrum usage data：a large－scale spectrum measurement study［C］.In Proceedings of the ACM MobiCom，2009.

［4］姚富强，等.动态频谱的发展现状及应对策略分析［J］.电波科学学报，2013，28（4）.

［5］T.C.Clancy.Formalizing the interference temperature model［J］.Wireless Communications and Mobile Computing，2007，7（9）.

［6］W.Wang and X.Liu.List－coloring based channel allocation for open－spectrum wireless networks［C］.In IEEE Vehicular Technology Conference，Citeseer，2005，volume 62.

［7］H.Zheng and C.Peng.Collaboration and fairness in opportunistic spectrum access.In Proceedings of IEEE International Conference on Communications（ICC），Citeseer，2005.

［8］D.I.Kim，L.B.Le，and E.Hossain.Joint rate and power allocation for cognitive radios in dynamic spectrum access environment［J］.IEEE Transactions on Wireless Communications，2008，7（12）.

［9］L.Zhang，Y.Liang，and Y.Xin.Joint beam forming and power allocation for multiple access channels in cognitive radio networks［J］.IEEE Journal on Selected Areas in Communications，2008，26（1）.

［10］J.Chen，L.Gong，and Y.Yang.Two Bandwidth packing algorithms for a centralized wireless network and their average－case analysis［C］.In Information，Communications and Signal Processing，Fifth International Conference on Communication，2005.

［11］J.X.Chen，P.Zeng，Y.Yang，and H Zhu.A bounded item bin packing problem over discrete distribution［C］.In Theory and Applications of Models of Computation（TAMC 2006），3rd International Conference on Communication，2006.

［12］Y.Zhang and C.Leung.Resource allocation in an OFDM－Based cognitive radio system［J］.IEEE Transactions on Communications，2009，57（7）.

［13］R.Chandra，R.Mahajan，T.Moscibroda，R.Raghavendra，and P.Bahl.A case for adapting channel width in wireless networks［C］.In Proceedings of the ACM SIGCOMM 2008 conference on Data communication，2008.

［14］陈剑，吴建平.基于用户分配和负载的频谱分配算法［J］.软件学报，2013，24（7）.

［15］Chaitanya Swamy.Approximation algorithms for bin packing［D］.Ithaca：Graduate School of Cornell University，2004.

［16］G.Dosa.The tight bound of first fit decreasing binpacking algorithm Is.In Combinatorics，Algorithms，Probabilistic and Experi－mental Methodologies［C］.First International Symposium，ESCAPE 2007，Hangzhou，China，April 7－9，2007.

［17］M.Yue and L.Zhang.A simple proof of the inequality MFFD（L）！＝71／60 OPT（L）＋1，L for the MFFD bin－packing algorithm［J］.Acta Mathematicae Applicatae Sinica－English Series，1995，11（3）.

［18］郑志刚.认知无线电中频谱分配模型及算法研究［D］.南京：南京邮电大学，2013.

Research on Dynamic Spectrum Allocation based on Satisfaction Degree

LI Xiao－yue，et al

（Henan Mechanical and Electrical Engineering College，Xinxiang 453000，China）

In this paper，we propose to use variable instead of predetermined width channel for communication and present a novel dynamic spectrum allocation model，which can serve all SUs by means of degrading service.We also design a MAC protocol for centralized cognitive radio network consisted of many SUs with heterogeneous bandwidth demands，experimental results show that variable channel width method increases spectrum utilization more than 38%compared with predetermined channel width method，and fairness index of SUs is about 90%in our model.

cognitive radio network；bandwidth；dynamic spectrum allocation；satisfaction degree model；MAC protocol

TP393.0

A

1008－2093（2015）01－0026－07

2014－11－20

李晓月（1982－），男，河南滑县人，讲师，硕士，主要从事计算机网络、图形图像以及人工智能研究。