系统初始化
信息更新 定点度数 否 是 否 否
顶点已获得 频谱数相同 选择已获得频谱数少的顶点 相同？ 选择度数低的顶点 是
随机选择顶点 分配频谱
所有频谱分配 已进行分配
是
算法结束
图3-2分布式贪婪算法流程图
从分布式公平性算法的流程可见，分布式公平算法通过非循环有向图的建立和从sink节点开始分配，在一定程度上优先为度数高的节点分配频谱，从而改善了分配的公平性。
2、 色敏感的图论着色算法
列表着色算法认为系统中所有的频谱都具有相同的性质，没有考虑不同频谱的差异性，然而认知无线电系统中实际使用的频谱具有频谱效益的差异。频谱效益的差异性指同一个认知用户使用不同的频谱能够获得不同的效益，同一个频谱对不同的认知用户在不同的时段也具有不同的效益。频谱效益的差异主要源于认 知用户在某个频谱上所能够允许使用的发射功率大小，不同频谱的带宽大小，以及所使用频谱的频率影响。频谱效益通常使用用户在某频谱上能够获得的传输速率衡量。
由于频谱效益对频谱分配算法能够获得的系统性能有重大影响。因此，在列表着色算法提出的图论着色模型基础上，增加了表示不同频谱效益差异性的频谱效益矩阵，提出了CSGC算法。然而，CSGC算法使用的频谱效益矩阵中频谱效益的含义仅仅表示了不同频谱的带宽不同，以频谱带宽作为衡量频谱效益的标准。
在CSGC算法中，分别针对最大化频谱效益准则与最大比例公平(Max．Proportional．Fair,MPF)准则，比较了认知用户协作方式与认知用户非协作方式下算法的性能。由于CSGC算法的频谱效益矩阵中频谱效益的大小是以频谱的带宽作为衡量标准，因此，最大化频谱效益准则实际上就是CSGC算法中的最大总带宽(Max．Sum．Bandwidth，MSB)准则。
CSGC算法最大化频谱效益准则的数学表达式如下：
max其中bn,m是引入的频谱效益矩阵B中的元素，表示认知用户n使用频谱m所能够获得的效益，即带宽的大小。在最大化频谱效益准则下，系统以获得最大的效益总和为目标进行频谱分配。
为了比较算法频谱分配的公平性，算法使用了最大比例公平性准则作为衡量 算法分配公平性的度量，其数学表达式如下： maxA??N,MCSGC算法通过对图中节点进行标号(1abel)来进行频谱分配，在某个标号规
Nn?1A??N,M??an?1m?1NMn,m?bn,m （3-3）
?log?a10Mnm, ?bnm, （3-4）
m?1则下，标号的值越大表示了该标号对应的分配具有较高的价值，对既定的频谱分配目标贡献较大，需要优先分配标号值高的频谱给相应节点，因此，标号的值体现了频谱分配的优先级。另外，CSGC算法对于不同的分配目标，不同的认知用户协作方式的分配，使用了不同的标号规则。
CSGC算法的分配流程如图3-3所示：
根据标号规划计
算标号值labeln
满足n?argmax(label) n 否
从节点n与节点n邻居的可用频谱集合中删除已 分配频谱 m
将最大标号对应频谱m分配给节点n 搜索标号值最大的节点n
是
所有节点可用
频谱集合为空？
分配结果
图3-3 CSGC算法分配流程图
3、 SGC联合局部议价的多小区频谱分配算法
对于拓扑结构固定的系统而言，CSGC算法的频谱分配方案可以得到当前拓扑下的最优分配结果，通过用户间的协作，其分配能够达到全局最优。总的来说，CSGC算法的分配是在不考虑本次分配前的频谱分配信息的情况下，独立地为每个认知用户分配频谱。
然而，受到认知用户位置移动、活动情况改变等因素的影响，认知无线电系 统的网络拓扑将动态改变，使用类似CSGC算法的基于固定拓扑的全局最优分配方法，网络需要根据拓扑的每次改变重新计算拓扑，在分布式算法中，信息的传递与复杂的计算过程使得算法的开销庞大。为了减少算法开销，文献[11]提出一种分布式局部议价的频谱分配算法，算法在新的频谱分配过程中考虑上一次频谱分配的信息，根据上一次频谱分配的结果，局部议价算法能够通过有限数量的计算适应拓扑的改变，针对新的拓扑作出接近全局最优的分配决策。
局部议价算法的具体实现比较复杂，本文在此不作叙述，其基本思想是：假 定在每次拓扑改变前频谱分配已经接近全局最优，则本次分配可以通过在受拓扑 改变影响的节点之间的局部议价快速地实现频谱最优化分配。在局部议价期间， 邻节点的集合，即相互间有干扰边相连的各个节点，自组织成为议价小组。每个 小组修改组内的频谱分配以适应拓扑的变化并实现在局部的最优分配，从而获得 整体上接近最优的分配结果，小组内的频谱分配不能影响或者改变组外的任何一 个节点的分配。局部议价算法制定了完善的议价小组组成限制，议价策略以及详 细的议价过程，以保证局部议价的实现。
文献[7]在图论着色模型与局部议价算法基础上，进一步将图论着色模型应用于认知无线电多小区的频谱分配，以图论着色结合局部议价实现认知无线电多小区的频谱分配。算法的目标是在多小区频谱分配中，在避免小区间和小区内认知用户的共道干扰的前提下，最大化系统的频谱利用率，同时保证认知用户问使用频谱的公平性，即频谱分配需要保证每个用户的最小带宽需求。
CSGC联合局部议价的多小区频谱分配算法由三个主要部分组成，分别是系统初始化，资源预分配和认知用户间局部议价。具体如下：
第一阶段：系统初始化，认知系统中各基站收集认知用户的位置和可用频谱
信息，使用公式(3-5)所示的标记方法对每个用户计算ratio值，N表示邻节点数，M表示节点可用度数，ratio值表示了用户在资源预分配阶段获得分配的优先级情况。
ratio?N (3-5) M第二阶段：资源预分配，从位于网络中央的小区开始，逐个小区地分配频谱。在本阶段的资源预分配中，每个认知用户试图获得自己需要的最大频谱带宽。资源预分配阶段使用了与CSGC算法相似的方法，每次选取ratio值最大的用户为其分配频谱，直到所有的用户获得了分配。
第三阶段：认知用户间进行局部议价：由于第二阶段的资源预分配以获得最大化的系统频谱利用率为目标，因而各用户间的频谱分配不平衡，有些用户获得了足够的频谱资源，而其中部分用户获得的频谱资源没有达到其通信所需的最低带宽需求。因此，第三阶段通过认知用户间的局部议价来改善分配的公平性，没有获得足够频谱的用户有权通过局部议价来向自己的邻节点中频谱资源充足的节点借用频谱，通过局部议价达到最低频谱带宽需求。
第三阶段可以看作是对第二阶段的资源预分配的局部调整，通过第三阶段的局部议价，实现频谱分配的公平性。CSGC联合局部议价的多小区频谱分配算法能够以较低的算法复杂性与开销，实现接近最优分配的频谱利用，并能够取得较高的频谱分配公平性，作为基于多小区频谱分配的研究对本文有较强的参考价值。 4、小结
总结了图论着色模型下的现有分配算法，其中列表着色(1istcoloring)算法是对传统移动蜂窝系统小区的图论着色模型进行了修订，增加了在认知无线电系统下的约束条件；颜色敏感的图论着色(Color Sensitive GraphColoring，CSGC)算法则增加了对频谱效益差异性和干扰差异性的考虑，并对频谱分配目标进行了修订；而局部议价的算法则是对CSGC算法的进一步改进，通过成立局部议价小组，减少图论着色模型中的节点数，并利用上一次的分配结果进行局部修改，从而降低分配的开销。
通过分析现有算法的不足，本文提出了基于图论着色模型的并行分配算法，降低了频谱分配的时间开销。并行算法的基本原理是通过对原有着色算法中复合
