基于最小生成树的分簇协作频谱感知改进算法*

邱恭安，封 森

（南通大学 电子信息学院，江苏 南通 226019）

基于最小生成树的分簇协作频谱感知改进算法*

邱恭安＊＊，封 森

（南通大学 电子信息学院，江苏 南通 226019）

为减少分簇过程中的时延，基于最小生成树的单向比较优势提出簇首快速推举方法，并提出改进的分簇协作频谱感知算法，分析了算法的时间复杂度。算法首先基于最小划分对所有次用户节点进行分簇，簇内节点根据设置的评价条件进行性能比较，推举簇首。由簇首进行本地簇内频谱检测，并上传检测结果，最后融合中心在簇首间实现协作的频谱检测。在瑞利信道条件下，仿真显示在大信噪比时，融合中心应用AND规则，系统具有较小的虚警率，所提算法检测性能优;小信噪比时，应用OR规则能扩展系统的有效检测区间，所提算法在满足系统要求的前提下检测性能较差，但簇内信道效率提高了n－1倍。

认知无线电;频谱检测;协作频谱感知;最小生成树;分簇

1 引言

分簇协作频谱感知将分布式认知节点分成独立簇，每个簇推举综合性能好的节点为簇首，仅由簇首进行频谱感知并向融合中心上传感知结果，最后由融合中心做出全局判决，以提高系统信道效率，降低融合中心计算负担，减小簇内节点能量消耗和动态性［1］。

分簇协作频谱感知算法中，簇首推举主要有最小能量消耗型的功率感知算法、最大范围的高连通算法、基于簇大小和簇首稳定性等要素加权的簇首推举算法［2］。文献［3］针对多载波系统对频谱的划分，提出根据子载波信道状态应用基于分簇的差异化能量检测算法，避免恶劣信道节点出现在同一个簇内，以提高系统检测性能。文献［4］根据次用户节点共性分簇，并推举可信度最大节点为簇首，但可信度计算为多次加权，计算复杂，簇首推举时延大。文献［5］应用多门限检测算法，对信道增益、与融合中心距离、邻居节点数和与邻居节点间的平均距离4个参数进行加权，选最优者为簇首，但算法存在计算量和开销大问题。文献［6］研究了噪声不确定性信道中分簇协作算法，推举报告信道波动性最小的节点为簇首，该方法具有较强的针对性。文献［7］利用位置信息进行分簇，并推举簇内中心节点为簇首，该算法过度依赖位置信息。

目前分簇协作算法存在计算复杂、无线信道开销大或簇稳定性较差等不足。本文利用最小生成树的单向比较优势提出快速簇首推举方法，减小簇首推举时间。基于此提出的分簇协作频谱感知算法与传统分簇算法不同的是并不追求最佳的系统检测性能，而是在满足系统要求的检测性能下，扩展系统检测区间或提高系统稳定性，减小时延，降低节点能耗，探索综合性能优的可行性算法。

2 生成树理论基础

认知无线网络由主用户（Primary User，PU）和次用户（Secondary User，SU）组成，设所有次用户节点构成网络顶点集合V，相互之间连线构成边集合E，节点间的属性参量为权值，共同构成赋权连通图G=（V，E）。

定义1:对于连通图G=（V，E），其中V为顶点集合，E为边集合，其任意两个顶点之间存在一条路径，称无圈（环）的连通图为树（Tree）。

定义2:对于连通图G的所有树T，称包含了图G中所有顶点的树为生成树，即有V（T）=V（G）。

给定图 G=（V，E），其生成树算法如下［8］:

3 分簇协作频谱感知

分簇协作频谱感知模型如图1所示，主要包括节点簇建立、簇首推举和协作融合判决三部分。

借代跟汉语常用词相互关联也有两方面的表现:一是借代影响汉语的造词;二是借代影响汉语词义的变化发展,是引起词的义项增加的一种重要方式。

图1 分簇协作频谱感知模型Fig.1 Clustering cooperative spectrum sensing model

3.1 基于最小划分的节点簇

节点簇是一序列在某种属性上相关联节点的集合，能够减小簇内节点拓扑范围和动态性，主要要素包括簇的连通性、簇大小和簇首稳定性。考虑频谱检测节点的能量、连通性和集中度，采用最小划分算法建立节点簇［9］。

定义3:设网络图G中节点集合V，存在最小正整数q使得节点集合V的划分S={V1，V2，…，Vq}满足每个Vi都是一个完整子图，且对所有的i=1，2，…，q 均有 Vi≠，∪qi=1Vi=V，Vi∩Vj= ，则称 S为最小划分。

对于G的最小划S，具有如下两条性质:

性质1:被划分的节点只能属于某一个簇;

性质2:每个被划分的簇应该是极大簇。

算法关键是分布式地寻找公共邻居节点来更新所属簇的维数，其中公共邻居指簇内所有节点的共同邻居节点。每个节点需维护一个簇列表和一个邻节点列表，算法根据输入拓扑图进行划分，并输出每个节点所属的簇，实现簇的建立。

3.2 基于最小生成树的簇首推举

簇首的产生需要快速，一旦产生则需要稳定，保证协作频谱检测的实时性和可靠性。设簇内节点缓存自身相关权值，包括信噪比、剩余能量、与融合中心距离等参量，且相邻节点间能相互通信。

设簇内节点数为N，簇内节点与数据融合中心距离为D，并根据D大小对节点进行排序。首先最小D节点声称为簇首H，随后与次小D节点进行权值比较，推举性能优者为新候选簇首，同时向对方发送“member”信息，接收其为簇员节点，簇员节点回复“head”消息进行确认。若次用户节点收到“member”信息，则不再与任何节点比较，直到系统再次初始化。重复节点间的性能比较，则经过N－1次计算后产生簇首H，推举流程如图2所示。

图2 簇首推举流程图Fig.2 Diagram of cluster head election

3.3 基于协作的全局判决

设簇内节点应用能量检测算法对主用户状态进行本地检测，能量检测算法不需要预知主用户信号特征，将接收信号总能量的判决值与判决门值比较判断主用户信号存在与否。因此，转化为二元假设检验:

式中，x（t）为次用户接收到的信号，s（t）为主用户发射信号，h（t）为主用户信号的信道增益，n（t）为噪声信号，H1和H0分别表示主用户存在和不存在两种状态。

在全局协作的数据融合中，融合中心可应用硬判决AND或OR规则进行数据融合。设认知无线网络中有M个次用户节点，其中第i个簇簇首的本地检测概率和虚警概率分别为Pdi、Pfi，则采用 OR准则融合后系统全局检测概率和虚警概率为

分簇协作中仅由推举的簇首代表簇内节点检测并上传主用户状态数据，因此，簇首须具有本地最优的性能，如最大信噪比。而数据融合中心则应用配置融合准则对簇首上传结果进行融合计算，作出系统全局判决，随后将全局判决结果回传给簇首，由簇首在簇内广播全局判决。

3.4 时间复杂度分析

次用户节点分布状态改变时，节点需要重新分簇，当节点簇稳定后系统进行协作频谱检测，因此，簇生成时延直接影响频谱检测性能。该时延包括分簇建立时间和簇首推举过程时间。

若系统次用户节点总数为M，则按最小划分建立分簇时间复杂度约为O（M），各分簇并行运算簇首推举算法［9］。设簇内平均节点数为N，则按Prim算法各节点对间权值排序时间复杂度为o（N lg N）［10］。随后，推举簇内接收信噪比最大节点为簇首过程需要（N－1）次比较。因此，一个周期内，系统总时间复杂度为o（M+N lg N）。

若系统按次用户节点位置进行分簇，并根据报告信道状态推举簇首［6］，则其簇建立时间复杂度约为O（M）。仍然设簇内平均节点数为N，则簇内节点两两进行报告信道状态交叉比较，其时间复杂度为o（N2）。若先从M个节点中推举簇首，然后由簇首添加其他节点作为簇员（如经典LEACH算法），则其时间复杂度为o（N2lg N）。可见，所提算法簇生成时延较小。

4 性能仿真与分析

在瑞利衰落信道中，基于Matlab对所提算法的频谱检测性能进行了仿真比较。考虑次用户节点实际有限能量、单个簇内节点数上限为9的要求，仿真取时间带宽积为5，随机生成15个次用户节点，划分为3个簇，簇平均节点数为5。在实际应用环境中，单个簇内所有节点出现相等或近似信噪比（此时仅需配置简单的全节点频谱检测算法）的可能性小，因此，大信噪比时，设簇节点信噪比取值范围为［1，10］dB;小信噪比时，设簇节点信噪比取值范围为［－10，－1］dB，推举簇首的性能指标为节点接收信噪比SNR。

在不同信道状态条件下，对数据融合中心应用AND规则和OR规则时，分簇协作频谱感知算法的系统检测性能进行了仿真计算，分别如图3（簇首SNR=9 dB）和图4（簇首SNR=－1 dB）所示。

图4 小信噪比全局检测性能Fig.4 Global performance under low SNR

在大信噪比时，如图3所示，两种融合规则下的算法检测性能均能达到系统工作要求，即检测概率大于0.9，同时虚警率小于0.1，其中OR融合规则系统检测概率略大，但虚警率也略大。在小信噪比时，如图4所示，AND融合规则下算法检测性能已不能满足系统工作要求，但OR融合规则下系统检测性能较好，且存在一定的检测区间。

综上所述，在大信噪比状态时，融合中心选用AND规则能够减小系统虚警率，而在小信噪比状态时，选用OR规则能够提高系统检测概率，扩大系统有效检测区间。

针对融合规则与信道状态间的关系，与传统全节点协作频谱感知算法［11］进行了系统检测性能比较。大信噪比AND规则时，系统检测性能如图5所示;小信噪比 OR规则时，系统检测性能如图6所示。

图6 小信噪比OR规则算法性能Fig.6 Proposed algorithm performance under low SNR and OR rule

由图5可知，由于全部节点中存在信噪比低的次用户节点，其本地检测结果正确率不高，在严格的AND融合规则下导致传统全节点协作频谱感知检测概率下降，而仅选择信道条件好的簇首进行协作频谱检测概率，其系统检测性能较好，体现出选择高信噪比节点检测频谱的可靠性。

由图6可知，在小信噪比OR规则中，传统全节点协作模式的检测概率优于簇首协作模式，但其信道效率则仅为簇首协作的1/n（n为簇内节点数），同时全节点协作虚警率也大于簇首协作模式。

5 总结

传统分簇协作频谱感知算法分簇计算复杂，容易产生死循环，导致较大时延和簇不稳定。本文所提算法利用最小生成树的开环特征避免簇首推举比较中的重复性，各分簇并行运行，减小了时间复杂度，降低了节点计算能耗。随后，仅簇首间进行协作频谱检测，由数据融合中心作出系统全局判决。仿真显示所提算法在大信噪比AND规则下，能够满足系统性能要求而传统算法已处于失效状态;在小信噪比OR规则下，所提算法在系统有效检测区间内，较全节点协作算法检测概率差，但信道效率高，虚警率也略低。因此，所提算法在满足系统检测性能要求前提下，具有时延小、信道效率高的优势。

在实际应用中，融合中心可以同时配置多种融合规则，但是估计簇首节点的实时状态，并根据不同簇首状态独立选择合适切换时间需要深入探讨。

［1］Wang L，Wang J L，Ding G R，et al.A survey of clusterbased cooperative spectrum sensing in cognitive radio networks［C］//Proceedings of 2011 Cross Strait Quad－Regional Radio Science and Wireless Technology Conference.Harbin:IEEE，2011:247 －251.

［2］Hussain S，Fernando X.Approach for cluster－ based spectrum sensing over band－limited reporting channels［J］.IET Communications，2012，11（6）:1466 －1474.

［3］Cheraghi P，Ma Y，Tafazolli R，et al.Cluster－ based differential energy detection for spectrum sensing in multicarrier systems［J］.IEEE Transactions on Signal Processing，2012，60（12）:6450 －6464.

［4］Wu Q H，Ding G R，Wang J L，et al.Consensus－ based decentralized clustering for cooperative spectrum sensing in cognitive radio networks［J］.Chinese Science Bulletin，2012，57（28 －29）:3677 －3683.

［5］Peng K Z，Liu Z Y，Tu L.Weighted －clustering cooperative spectrum sensing algorithm［C］//Proceedings of 7th International Symposium on Wireless and Pervasive Computing（ISWPC）.Dalian:IEEE，2012:1 －5.

［6］Reisi N，Ahmadian M，Jamali V，et al.Cluster－based cooperative spectrum sensing over correlated log－normal channels with noise uncertainty in cognitive radio networks［J］.IET Communications，2012，16（6）:2725 －2733.

［7］Smitha K G，Vinod A P.Cluster based power efficient cooperative spectrum sensing under reduced bandwidth using location information［C］//Proceedings of 2011 IEEE 54th International Midwest Symposium on Circuits and Systems.Seoul:IEEE，2011:1 －4.

［8］ 徐俊明.图论及其应用［M］.北京:中国科学技术大学出版社，2010.

XU Jun － ming.Graph theory and applications［M］.Beijing:University of Science and Technology of China Press，2010.（in Chinese）

［9］胡罡，徐明，刘丽霞，等.无线认知网络中一种团划分的频谱感知算法［J］.软件学报，2011，22（2）:298 －312.

HU Gang，XU Ming，LIU Li－ xia，et al.Spectrum sensing algorithm based on clique partition for wireless cognitive networks［J］.Journal of Software，2011，22（2）:298 －312.（in Chinese）

［10］Hassan M R.An efficient method to solve least－cost minimum spanning tree（LC － MST）problem ［J］.Journal of King Saud University－Computer and Information Sciences，2012，24（2）:101 －105.

［11］岳静文，陈志，郑宝玉，等.基于可靠次用户信息的协作频谱感知算法研究［J］.电子与信息学报，2012，34（5）:1208－1213.

YUE Wen －jing，CHEN Zhi，ZHENG Bao －yu，et al.Cooperative spectrum sensing based on reliable secondary user information［J］.Journal of Electronics＆ Information Technology，2012，34（5）:1208 －1213.（in Chinese）

An Improved Clustering Cooperative Spectrum Sensing Algorithm Based on M inimum Spanning Tree

QIU Gong－an，FENG Sen
（School of Electronics and Information，Nantong University，Nantong 226019，China）

For decreasing the delay of clustering process，a cluster head election scheme is proposed based on the single－direct comparison characteristic of minimum spanning tree.The time complexity of proposed clustering coomperative spectrum sensing algorithm is analyzed based on the fast cluster head election scheme.Here the secondary users are divided into different clusters based on minimum clique partition.A cluster head will be elected to detect the spectrum hole in the cluster according to preset metrics and transmit the sensing result to the fusion center.The global decision will be made by the fusion center according to results from all cluster heads.Simulation results show that the proposed algorithm can achieve the high detecion probability and low false alarm probability by employing the AND rule under high signal－tonoise ratio（SNR）.Moreover，the algorithm can expand the available dectection area and enhance the bandwidth efficiency by employing the OR rule under low SNR.

cognitive radio;spectrum detection;cooperative spectrum sensing;minimum spanning rree;clustering

The National Natural Science Funds of China（No.61371113）;Nantong Applied Research Project（BK2013052）;Graduate Research and Innovation Projects of Nantong University（YKC13008）

＊＊

qiugongan@ntu.edu.cn Corresponding author:qiugongan@ntu.edu.cn

TN92

A

1001－893X（2014）05－0564－05

10.3969/j.issn.1001 －893x.2014.05.007

邱恭安!，封森.基于最小生成树的分簇协作频谱感知改进算法［J］.电讯技术，2014，54（5）:564 －568.［QIU Gong －an，FENG Sen.An Improved Clustering Cooperative Spectrum Sensing Algorithm Based on Minimum Spanning Tree［J］.Telecommunication Engineering，2014，54（5）:564 －568.］

2013－12－27;

2014－03－18

date:2013－12－27;Revised date:2014－03－18

国家自然科学基金资助项目（61371113）;南通市应用研究计划项目（BK2013052）;南通大学研究生科技创新计划项目（YKC13008）

邱恭安（1973—），男，湖北浠水人，博士，副教授，主要研究方向为认知车载网络理论与技术;

QIU Gong － an was born in Xishui，Hubei Province，in 1973.He is now an associate professor with the Ph.D.degree.His research concerns theory and applications in cognitive vehic-ular wireless networks.

Email:qiugongan@ntu.edu.cn

封 森（1988—），男，江苏徐州人，硕士研究生，主要研究方向为认知无线网络。

FENG Sen was born in Xuzhou，Jiangsu Province，in 1988.He is now a graduate student.His research concerns cognitive wireless networks.