基于基因选择性遗传的认知无线电频谱分配算法

郭 霖，曾 锋，陈志刚

（中南大学软件学院，长沙 410075）

基于基因选择性遗传的认知无线电频谱分配算法

郭 霖，曾 锋，陈志刚

（中南大学软件学院，长沙 410075）

传统认知无线电频谱分配遗传算法面对认知用户之间的干扰，选择在每次迭代之后进行满足干扰约束的处理，使得携带干扰基因的染色体参与整个遗传优化过程。针对该问题，以在遗传过程中控制干扰为目标，设计染色体中的基因表达规则，提出认知无线电频谱分配算法。依据基因表达规则标记显性基因与隐性基因，在下一代染色体中表达显性基因，抑制隐性基因，从而保证染色体的健康，提高算法效率。仿真结果表明，与遗传算法和量子遗传算法相比，当网络中认知用户较多、频谱资源较紧张时，该算法能获得较高的系统总效益和系统接入率。

认知无线网络；频谱分配；遗传算法；系统效益；系统接入率

DO I：10.3969/j.issn.1000-3428.2015.10.052

1 概述

随着无线通信与多媒体应用的快速发展，无线频谱资源已逐渐无法满足人们的需求。而现有的无线通信系统采用低效率的固定频谱分配方法，更是加剧了频谱资源的匮乏与使用不均衡［1］。认知无线电［2］是一种智能的无线通信系统，其认知用户通过感知周围的频谱环境，能够在不影响授权用户与其他认知用户的情况下动态接入空闲频谱，从而提高了频谱的利用率。因此，如何高效公平地分配可用频谱资源至关重要。

目前已提出的频谱分配模型主要包括博弈论模型［3］、拍卖模型［4］、干扰温度模型［5］和图论模型［6］。其中，图论模型的泛化能力较强，可以根据不同的需求选择不同的目标函数，引起了广泛的研究。文献［6］提出了以最大效益为目标的颜色敏感的图着色算法，优先将频谱资源分配给效益大、干扰度小的认知用户，这样做虽然提高了系统效益，但无法保证

认知用户之间的公平性。文献［7］以最大化网络接入量为目标进行分配频谱资源，在一定程度上避免了某些频谱资源没有认知用户接入而产生饥饿现象。近年来学者们把频谱分配问题转化为智能优化问题，提出了粒子群算法［8-9］、量子蜂群算法［10］，以及遗传克隆算法［11-12］。

文献［13］提出了一种基于遗传算法（Genetic Algorithm，GA）的频谱分配方法。文献［14］在其基础上提出了基于量子遗传算法（Quantum Genetic Algorithm，QGA）的频谱分配方法，但是在处理干扰的问题上采用了与文献［13］相同的手法，都需要在最后进行满足干扰约束的处理，并且都没有考虑系统的接入率以及用户的公平性。针对这些问题，本文通过标记显隐性基因，抑制染色体中干扰基因的出现，并在变异阶段优先考虑分配率较低的用户，提高系统接入率。

2 认知无线电频谱分配模型及矩阵

2.1 认知无线电频谱分配图论模型

认知无线网络频谱分配过程中需要考虑3个方面的问题：认知用户对授权用户的干扰，认知用户之间的干扰，系统的总频谱效益以及认知用户之间的公平性。本文利用图着色模型来描述频谱分配问题。

首先建立拓扑结构模型，假设在一个X×Y的区域中，有I个授权用户P和N个认知用户S随机分布，可以检测到 M个完全正交的可用频谱，认知用户在满足频谱分配的规则下可以同时使用多个频谱资源。对于频谱 m（m=1，2，…，M），授权用户Pi（i=1，2，…，I）与认知用户Sn（n=1，2，…，N）的覆盖区域分别是以自己为圆心，半径为 dPi，m与 dsn，m的圆。当各用户在某一频谱上的覆盖区域相互重叠时即表明存在干扰。

根据上述假设及定义，可以将认知无线网络抽象成一个无向加权图G=（V，E，B）。V是顶点的集合，一个顶点代表一个认知用户；E是边的集合，表示2个认知用户之间的干扰关系，对一个频谱，如果认知用户i与j的覆盖区域相互重叠，则ei，j=1；否则，ei，j=0，表示i与j之间不相连。B代表每个顶点的颜色（可用频谱）集合以及其对应的权重（频谱效益）。

2.2 认知无线电网络频谱分配矩阵

根据以上分析，可将认知无线电网络频谱分配模型用定义1～定义4的矩阵［6］表示，并用定义9［6］的系统总效益作为认知无线电网络频谱分配的目标。同时，在以总效益为目标的基础上考虑了认知

定义3 干扰矩阵 C=｛cn，k，m|cn，k，m∈｛0，1｝｝N×N×M，用来表示网络中存在的干扰。当n=k时，cn，k，m用来表示授权用户与认知用户之间的干扰，若cn，k，m=1，表示认知用户n使用频谱m会对同时使用该频谱的授权用户产生干扰；若cn，k，m=0则表示无干扰。当n≠k时，cn，k，m用来表示认知用户之间的干扰情况，若认知用户 n与 k同时使用频谱 m会产生干扰，则cn，k，m=1，无干扰则cn，k，m=0。

定义4 无干扰分配矩阵 A用来表示最终的频谱分配方案，A=｛an，m|an，m∈｛0，1｝，an，m≤ln，m｝N×M。当 an，m=1时表示把频谱 m分配给了认知用户n，反之如果没有给认知用户n分配频谱m，则an，m=0。同时，矩阵 A必须满足干扰矩阵 C的约束：an，m+an，m≤1，if cn，k，m=1，∀1≤m≤M，1≤n，k≤N，n≠k。

定义5 认知用户可感知频谱个数矩阵K，用来表示认知用户可感知到的频谱个数：K=｛kn|kn=用户之间的公平性问题，期望认知用户最终分配到的频谱个数与自身所能感受到的频谱个数相关，并由此期望定义了认知用户的分配率，如定义7所示。不同于单一以系统总效益为目标的分配方法，在算法的变异阶段让频谱分配率较低的认知用户优先分配到频谱资源，避免了少数频谱收益较高的认知用户占用绝大部分频谱的情况，并与此同时让更多的认知用户接入到系统中，提高了系统的接入率。相关定义如下：

定义1 可用矩阵 L=｛ln，m|ln，m∈｛0，1｝｝N×M，用来表示认知用户n（1≤n≤N）是否可以使用频谱m（1≤m≤M）。若 ln，m=1，则表示可以使用；若ln，m=0，则不可以使用。

定义6 认知用户已分配频谱个数矩阵H，用来表示认知用户已分配频谱个数，如下所示，其中，系统中认知用户n最多被分配kn个频谱：H=｛hn|hn=

定义7 认知用户频谱分配率矩阵E，用来表示认知用户n已分配到的频谱个数占自己可以感知到的频谱个数的比率，E=｛en|en=hn/kn｝N×1。

定义8 系统接入率F用来衡量接入到系统中的认知用户数量占系统中认知用户总数的比例，计算公式如下：

定义9 频谱m实现的效益R。对于无干扰频谱矩阵A，它的每一列表示频谱m对所有用户的分配情况，那么定义频谱m实现的效益为 R，由式（2）计算，并将其定义为染色体的适应度函数：

2.3 染色体编码

由于与矩阵L中值为0的元素位置相对应的频谱分配矩阵A中的元素必定为0，因此仅对ln，m=1的位置进行染色体编码。并将矩阵L的每一列编码为一条原始染色体GAm=｛gam，i|gam，i=1，i=1，2，…，Sm｝，其中，i为基因gam，i在染色体GAm中的位置，对应于矩阵L中m列的第n行位置，且染色体为一行向量；Sm为染色体 m的长度，其值等于矩阵 L对应频谱m中的1元素的个数。最后，把经过遗传进化的变异染色体GDm映射到矩阵A中对应的m列，如图1所示。

认知无线网络频谱分配的目标就是在满足干扰约束的条件下使系统总效益U（R）最大，则可将问题描述为：

图1 染色体编码方式

在频谱m编码的染色体Gm=｛gm，i|gm，i∈（0，1），i=1，2，…，Sm｝中，定义gm，i=1的位置为显性基因，定义gm，i=0的位置为隐性基因。

3 基因选择性遗传的频谱分配算法

3.1 算法设计

本文算法的核心是对遗传、交叉、变异3个步骤进行控制，方法如下：

传统的遗传算法是对适应度较高的染色体进行遗传复制，体现了不同染色体之间的差异性，但却忽略了染色体中每个基因的特性——基因之间的干扰性，即忽略了认知网络中存在不同的认知用户可以分别使用但却不能同时使用某一频谱的情况。相干扰的基因同时表达会产生致病基因组，如果不在遗传变异过程中进行控制，会将携带致病基因组的病态染色体参与整个遗传变异过程，降低了算法的有效性，增加了无效的计算量。所以本文提出的遗传算法是通过标记染色体中优秀基因为显性基因，在遗传变异过程中将显性基因进行表达，同时将会产生干扰的基因标记为隐性基因，使得在进化过程中，遗传、交叉、变异操作都是针对健康的染色体。

由矩阵 L按编码规则生成原始染色体 GAm（m=1，2，…，M），并将GAm克隆遗传生成S个相同的染色体GBm，s（s=1，2，…，S），组成初始种群，并定义GBm，s为遗传染色体。

3.1.1 遗传控制

首先由图1的编码规则，可将染色体GBm，s中的基因gbm，s，i对应到矩阵L中的 ln，m位置，并由此可以得到gbm，s，i对应于矩阵B中的效益值，然后由式（4）可以得到 GBm，s中每个基因 gbm，s，i的遗传概率 Pm，i。为了保证种群的多样性，依据每个基因的遗传概率由轮盘赌选择的方法随机选取GBm，s中的一个基因，那么Pm，i高的基因将会有更高的优先级被遗传到下一代，即对于某一频谱，效益高的认知用户会有更高的优先级被分配到该频谱。最后将该基因标记为显性基因，并将GBm，s中其余的基因标记为隐性基因。

3.1.2 交叉控制

至此，种群中所有的染色体GBm，s只有一个位置为显性基因，及gbm，s，i=1（1≤i≤Sm），而交叉控制的目的就是通过判断2条遗传染色体GBm，s与GBm，t中的显性基因 gbm，s，i，gbm，t，j是否存在干扰，如果没有干扰，则将遗传染色体GBm，s与GBm，t相互交叉合并生成新的染色体，减少重复计算。

记新生成的染色体个数为 U，定义新生成的染色体为交叉染色体 GCm，u（u=1，2，…，U）。交叉合并的操作为将2条遗传染色体GBm，s与GBm，t对应基

因位置相加，可知交叉后的染色体GCm，u中显性遗传基因为gcm，u，i，gcm，u，j。其中，i，j分别为 gbm，s，i，gbm，t，j在GBm，s，GBm，t中对应的显性基因位置。最后，如果GBm，s不能与其他任何遗传染色体交叉合并，则将GBm，s也标记为交叉染色体GCm，u。同时为了控制种群数量，由式（2）计算每条染色体的适应度，选取适应度最大的前s条染色体进行下一步的变异操作。

3.1.3 变异控制

变异控制是将上一步所产生的交叉染色体GCm，s中还没有表达的基因依据变异规则依次变异，由隐性基因变异为显性基因。

变异规则如下，将交叉染色体GCm，s中隐性基因gcm，s，i（1≤i≤Sm）的位置i由图1的方式对应到频谱m中的位置n，从而可以由分配率矩阵E=｛en｝N×1得到隐性基因gcm，s，i对应的认知用户n当前的分配率情况，并将所有隐性基因对应的en组成集合Em，s。然后从小到大依次判断集合Em，s中元素en对应的隐性基因与GCm，s所有显性基因的干扰性，如果没有干扰，则将隐性基因变异为显性基因，并将 en从集合Em，s中去除；如果有干扰，则直接将en从集合Em，s中去除。这样，分配率低的认知用户就会有更高的优先级被分配到该频谱。最后将完成变异的交叉染色体GCm，s标记为变异染色体GDm，s。

3.2 算法流程

综上所述，本文算法的频谱分配过程如下：

Step1 初始化参数：随机生成可用矩阵L，效益矩阵B，干扰矩阵C，以及可感知频谱个数矩阵C。

Step2 染色体编码：将矩阵L的每列按染色体编码规则生成原始染色体GAm，初始化种群数s，设进化代数g=0。

Step3 止条件判断：如果达到最大进化代数gmax，则选择分配方案集合Y中频谱效益最大的矩阵A作为最终的频谱分配方案，转Step9；否则，转Step4。

Step4 遗传控制：由轮盘赌选择方法将初始种群中的每个染色体随机保留一个基因为显性基因，其余的基因标记为隐性基因，生成新的染色体GBm。

Step5 交叉控制：将2条遗传染色体GBm，s与GBm，t合并生成新的染色体GCm，s，最后将无法与任何遗传染色体交叉合并的染色体 GBm，s同样标记为GCm，s。

Step6 判断：若m=1，则将矩阵K赋值给矩阵E；否则，转Step7。

Step7 变异控制：依据变异规则将GCm，s中的隐性基因变异成显性基因，生成变异染色体GDm，s。

Step8 映射矩阵：将适应度最大的染色体GDm，s映射到矩阵A中的第m列。更新矩阵K与矩阵E，若此时m=M，则将A加入分配方案集合Y，g=g+1，转Step3；否则m=m+1，转Step4。

Step9 输出频谱方案。

4 仿真及结果分析

本文在Matlab 2012平台进行了仿真测试，实验中网络的拓扑结构由文献［6］产生。为了验证基因选择遗传算法（GIS）的性能，分别以系统的总频谱效益U（R）和系统接入率F两方面作为衡量指标，同时与遗传 算 法 （GA）［13］和量子 遗 传算法（QGA）［14］作了比较。3种算法的进化代数都设定为200，种群大小为30，每次实验中3个算法使用相同的拓扑结构，每组实验运行50次，取平均值。为了体现GIS算法在染色体变异过程中对认知用户频谱分配公平性的控制，在最后展示了3种算法在随机一次频谱分配中每个认知用户的频谱分配率。

图2和图3分别给出了3种算法在频谱数量M=10时不同认知用户数量的系统总频谱效益与其对应的系统接入率。

图2 M=10的系统总效益U（R）

图3 M=10的系统接入率F

从图2中可以看到，GA与QGA的上升速度在认知用户数N=M=10之后有很明显的减缓，从N= 10～N=20所获得平均系统总收益仅为本文算法的64.31%与75.26%。从图3中可以看到，随着认知用户的增加，GIS系统接入率下降的速度在N=M= 10之后有很明显的减缓，从N=10～N=20，GIS算

法的系统接入率只降低了7.89%，而GA与QGA则分别降低了32.43%与41.67%。

这是由于随着区域中认知用户数量不断地增加，而频谱数量不变，导致认知用户之间对频谱的争夺和干扰更加剧烈。传统的遗传算法选择在最后进行干扰约束的处理，受干扰影响较大，而本文算法在过程中控制干扰，降低了干扰的影响。

图4和图5分别给出了3种算法在认知用户数量N=20时不同频谱数量的系统总频谱效益与其对应的系统接入率。从图 4中可以看到，与 GA和QGA相比，GIS从M=10～M=30的平均系统总效益分别提高了83%与64%。从图5中可以看到，与GA和QGA相比，本文算法从M=10～M=30的系统接入率分别提高了19%与53%。

图4 N=20的系统总效益U（R）

图5 N=20的系统接入率F

这其中的原因除了上文所提到的本文算法在进化过程中对干扰的控制，另一个因素是在染色体变异阶段选择变异基因的位置时优先考虑了频谱分配率en较低的认知用户，弱化了最大频谱效益在此阶段的影响，强化了每个认知用户所能感知到的频谱数量和已分配到的频谱数量的重要性。

图6展示了3种算法在认知用户数量N=10，频谱数量M=10时随机一次频谱分配中认知用户的频谱分配率。3种算法对应频谱分配率的标准差，从上至下依次为0.158 1，0.182 4，0.231 7，本文算法对应的频谱分配率的方差最小，从图中也可以看出本文算法相比于其他2种算法更为均匀。

图6 N=10，M=10时的认知用户频谱分配率

5 结束语

本文在综合分析了传统遗传算法在染色体编码以及干扰性的问题后，提出了基因选择性遗传的认知无线电频谱分配算法。算法在以最大效益为目标的基础上考虑了用户的公平性问题，首先在遗传、交叉阶段以最大效益为目标，使用轮盘赌的方法选择遗传基因，然后在变异阶段则优先将分配率最低的认知用户对应的基因进行变异，并于此同时提高了系统的接入率。仿真结果表明，当区域中认知用户数量较大、干扰越激烈时，本文算法在实现系统最大效益以及接入率方面有明显的优势。

［1］ Haykin S.Cognitive Radio：Brain-em powered Wireless Communications［J］.IEEE Journal on Selected Areas in Communications，2005，23（2）：201-220.

［2］ Quan Zhi，Cui Shuguang，Sayed A H.Optimal Linear Cooperation for Spectrum Sensing in Cognitive Radio Networks［J］.IEEE Journal of Selected Topics in Signal Processing，2008，2（1）：28-40.

［3］ Wang Beibei，Wu Yongle，Liu K J R.Game Theory for Cognitive Radio Networks：An Overview［J］.Computer Networks，2010，54（14）：2537-2561.

［4］ Wang Xinbing，Li Zheng，Xu Pengchao，et al.Spectrum Sharing in Cognitive Radio Networks——An Auctionbased Approach［J］.IEEE Transactions on System s，Man，and Cybernetics，Part B：Cybernetics，2010，40（3）：587-596.

［5］ Gözüpek D，Alagöz F.Genetic Algorithm-based Scheduling in Cognitive Radio Networks Under Interference Temperature Constraints［J］.International Journal of Communication System s，2011，24（2）：239-257.［6］ Peng Chunyi，Zheng Haitao，Zhao Ben.Utilization and Fairness in Spectrum Assignment for Opportunistic Spectrum Access［J］.Mobile Networks and Applications，2006，11（4）：555-576.

［7］ Jia Jie.A Spectrum Allocation Algorithm to Maximize the System Access Amount in Cognitive Radio System［C］//Pro-ceedings of the 3rd International Conference on Com-munication Software and Networks. Washington D.C.，USA：IEEE Press，2011：251-255.

［8］ 邝祝芳，陈志刚.认知无线Mesh网络中一种有效的多目标优化频谱分配算法［J］.中南大学学报：自然科学版，2013，44（6）：73-75.

［9］ 张丽影，曾志文，陈志刚，等.认知无线网络中基于约束算子的二进制粒子群频谱分配算法［J］.小型微型计算机系统，2013，34（6）：1226-1229.

［10］ 高洪元，曹金龙.量子蜂群算法及其在认知频谱分配中的应用［J］.中南大学学报：自然科学版，2012，43（12）：4743-4749.

［11］ 王晓飞.基于免疫克隆选择的认知无线网络频谱分配研究［J］.电子与信息学报，2011，33（7）：1561-1567.

［12］ 刘 升，陈志刚，邝祝芳.认知无线电中结合差异性的免疫克隆优化频谱分配算法［J］.计算机工程与科学，2014，36（9）：1672-1677.

［13］ El-Nainay，Mustafa Y.Island Genetic Algorithm-based Cognitive Networks［D］.Blacksburg，USA：Virginia Polytechnic Institute and State University，2009.

［14］ 赵知劲.基于量子遗传算法的认知无线电频谱分配［J］.物理学报，2009，58（2）：1358-1363.

编辑 顾逸斐

Cognitive Radio Spectrum Allocation Algorithm Based on Gene Selective Inheriting

GUO Lin，ZENG Feng，CHEN Zhigang
（School of Software，Central South University，Changsha 410075，China）

Traditional genetic algorithm is used in cognitive radio spectrum allocation chosen in the last step to solve the interference issue in the face of interference between cognitive users，resulting in the problem that the chromosome of carrying interference gene takes part in the whole genetic process.According to this problem，this paper targets the control of interference in the genetic process，designs rules of gene expression in the chromosome，proposes cognitive radio spectrum allocation algorithm of gene selective inheriting.It marks the dominant and recessive genes by the regulation of gene expression，and expresses the dominant genes and inhibits the recessive gene in the next generation of chromosomes，thereby ensuring the health of the chromosome，improving the efficiency of the algorithm.Simulation results show that the algorithm has better total benefit and higher access ratio com pared with Genetic Algorithm（GA）and Quantum Genetic Algorithm（QGA）when more cognitive users and fewer spectrum resources are in the system.

cognitive radio network；spectrum allocation；Genetic Algorithm（GA）；system benefit；system access ratio

郭 霖，曾 锋，陈志刚.基因选择性遗传的认知无线电频谱分配算法［J］.计算机工程，2015，41（10）：275-279，285.

英文引用格式：Guo Lin，Zeng Feng，Chen Zhigang.Cognitive Radio Spectrum Allocation Algorithm Based on Gene Selective Inheriting［J］.Computer Engineering，2015，41（10）：275-279，285.

1000-3428（2015）10-0275-05

A

TP301.6

国家自然科学基金资助项目（61103202）；高等学校博士学科点专项科研基金资助项目（20110162120046）；中南大学中央高校基本科研业务费专项基金资助项目（2015zzts232）。

郭 霖（1990-），男，硕士研究生，主研方向：认知无线网络；曾 锋，副教授、博士；陈志刚，教授、博士。

2014-10-30

2014-11-29E-mail：guolincsu@163.com