量子遗传算法用于认知无线电频谱分配的应用研究 第12页
的邻居个数称之为“连接度数。不同节点的频段度数和连接度数可能不同。有向图根据如下原则建立:图中边的方向是从高频段度数的顶点指向低频段度数的顶点，即低的频段度数的顶点为边的收端;若频段度数相同，则边从高连接度数的顶点指向低连接度数的顶点;如果连接度数也相同，则边从随机数高的顶点指向随机数低的顶点。由此产生一个无循环有向图。如果某顶点没有出边，则该顶点被称之为sink顶点;如果某顶点没有入边，则该顶点称之为源顶点。无循环有向图中可能有多个源顶点和sink顶点。
步骤 2: 分配频谱。
频段 (颜 色)的分配从sink节点开始，一个分配循环中每个项点最多分配一
个频段。先选择sink顶点，然后选取频段，原则是:选取所有邻接顶点的关联频
段列表中出现次数最少的频段。sunk顶点选取频段之后，对所有邻接顶点发布信息，通知其邻接顶点从它们的关联频段列表中移出了刚才选取的频段。然后该sink顶点本次循环的分配完毕，退出分配，并且删除与其相连的入边。具体措施是发一个set-Color标志给邻接顶点。
如果一个非sink顶点从它所有的下游邻接顶点得到set-Color标志，则表明这个顶点的出边全部被删除，该顶点将变成sink顶点，然后重复相同的步骤，直到图中不再有sink顶点。通过多轮的反复，算法逐步实现从sink顶点到源顶点频段选择。
步骤 3: 当图中不再有sink顶点，若还有节点拥有可用频段，则返回步骤1，
开始下一轮选择流程。
该步骤通过一个重置过程实现。在源节点产生一个重置标志发给每个邻接顶
点。如果某顶点从自己的上游顶点收到重置标志，则继续将重置标志发给自己所
有的下游邻接顶点。直到所有顶点收到重置标志，系统重启，带着还剩余的频段
返回到步骤I。如果顶点没有可用信道，它将退出操作。当所有顶点均没有可用频段时，算法流程结束。
(2)颜色敏感的图论着色(CSGC)算法
在列表着色算法中并未考虑分配中频谱效益的差异性和干扰频谱差异性，但
是在实际的认知无线电系统中，因为用户所处的环境不同，所使用的调制编码技术也可能不一样，不同用户在同一可用频段上获得的效益是不一样的，效益矩阵B表示了它们的效益。而且两个不同用户同时使用相同频段时是否存在干扰只与发射端用户之间的距离和发射功率有关，与频率本身并无关。在考虑频率选择性衰落的情况下，用户节点之间是否存在干扰还需要考虑小尺度的衰落，干扰矩阵与频率相关，由此可以得到一个干扰矩阵集合，每个频率对应一个干扰矩阵。
针对列表着色算法的不足，Haitao Zheng和Chunyi Peng等人提出了CSGC算法，它充分考虑了频谱分配中的频谱效益的差异性和干扰频谱的差异性，并分析了在协作式和非协作式条件下频谱分配算法的差异。
CSGC算法是一种基于标签机制的启发式的集中式的分配算法，运行该算法可获得一个近似的最优解，它能够明显的减少干扰，提高网络的吞吐量。CSGC算法是以一个最优化的效益函数为分配目标的，按照某个分配准则对频段进行标签，选择最大的标签频段分配给用户使用的。
1.目标函数
一般来说，一个资源分配问题可以用效益函数形式来表示。对于实际的应用，
我们可以通过现场测量来获取其效益函数，或者通过网络设计出一个接近实际的
虚拟环境来测量验证。在频谱资源分配相关的问题中，我们通常需要解决的是最
优化问题。由于引入了每个频段的效益，可以得到以最大化频谱效益为目标的最优分配准则的表达式，相应地系统达到最大频谱效益的数学表达式叫做最大带宽总和(Max-Sum-Bandwidth，MSB):
其中 。
表达式的物理含义是频谱分配为系统带来的最大带宽总和，效益矩阵口代表
了认知无线电用户在各个频带上所能获得的带宽， 表示所有满足条件的无干扰分配矩阵A的集合。
为了比较不同算法的公平性，算法还引入了有关信道分配公平性的度量准则，即最大比例公平性度量(Max-Proportional-Fair，MPF)，其目标是最大化受限用户
(bottleneck user)的频谱利用，其表达式为：
表达式给出了有关信道分配公平性的度量准则，可以比较不同算法的公平性，式中各变量代表的含义与最大带宽总和表达式中的各变量含义相同。
2.分配准则
最优分配需要根据所要求达到的分配目标来选择顶点标号规则(labelingru le),标号大小表征了分配目标和效益权重共同决定的顶点的“价值”，越有“价值”的顶点标号越大。每个标号对应一种颜色，着色的算法设计就是先选择最有价值的顶点进行着色。为了实现不同的预期目标，对于不同的效用函数，算法将采用不同的标号方法去满足效用函数的需求。
当算法目标是最大化频谱利用率时，在协作（非协作不在本文描述）方式下，相应的标号准则为：
协作式最大总带宽(Collaborative-Max-Sum-Bandwidth.CMSB)准则：
该准则与MSB效益函数相对应。当用户i分配到了频带j，，则与i在j上有干扰的用户将不能使用这个频带，于是它对系统总带宽的贡献为 ， 为干扰限制矩阵中不能与用户i同时使用频带j的用户个数。节点标号和颜色表达式为：
CMSB规则是在综合考虑了整个系统利用率和对邻居的冲突后的折中，由于考虑了对邻居的影响，所以该规则是协作式的。
众所周知，采用比例公平的方法，系统通常会把资源分配给有着最高的 的用户，其中 代表的是当前的待分配频段能给用户带来的效益，而 表示的是用户k在过去得到的平均效益。因此当算法主要考虑比例公平性时，相应的标号准则在协作式下变为如下表示形式:
协作式最大比例公平(Collaborative-Max-Proportional-Fair.CMPF)准则：
由表达式看出，标号描述了将一频段分配给某一用户时对系统总带宽的贡献与过去分配的带宽累积和之间的比例关系。
3.算法流程
CSGC的着色方法与PMNF(ProgressiveM inimumN eighborFirst)算法相似，
不同的是CSGC算法的目标是实现系统带宽的最大利用或者最大比例公平性。因
此，每次分配时系统选取对目标贡献最大的顶点，即每次获得最大标号的顶点。
算法考虑了每个顶点由于顶点位置不同而产生的干扰约束条件、关联频段列表和
频段效益的差异性，通过多次迭代完成对颜色的分配。
每次分配时算法通过某种标号方法将顶点标上标号(label)，每一个标号都与一个频段相对应。算法的每次迭代将选取拥有最高标号值的顶点，并将相关的颜色(频谱)分配给该顶点。然后进行拓扑更新，从得到颜色的顶点以及这个顶点的所有冲突受限相邻顶点的颜色列表中删除已经分配的颜色，并删除这些顶点间以该颜色相连的边，若某个顶点的颜色列表为空，则将该顶点从图中删除。
进行拓扑更新的同时，图中每个顶点的邻居顶点将发生改变，顶点的冲突限制条件也不断改变，同时由于拓扑结构的改变，相关顶点的标号也将发生变化，所以该算法需要对整个系统的各种信息进行快速动态地更新.当所有顶点的关联频段列表为空集时算法结束。
CSGC算法分配过程主要分4个步骤完成，如下：
Setup 1：计算标号，根据分配准则将每个节点的标号(1abel)和对应的颜色(color)计算出来。
Setup 2：着色，选取标号最大的节点，为其分配对应的颜色。
Setup 3：更新拓扑，主要对整个系统的各种信息进行更新，包括从节点的颜色集中删除已分配的颜色和从与该节点有冲突的节点的颜色集中删除该被分配的颜色。
<< 上一页 [11] [12] [13] [14] [15] [16] [17] 下一页
量子遗传算法用于认知无线电频谱分配的应用研究 第12页下载如图片无法显示或论文不完整，请联系qq752018766
