基于频谱感知的认知Ad hoc网络分簇算法*

齐 全 王可人 杜奕航

(国防科技大学电子对抗学院， 合肥， 230037)

引 言

随着无线通信技术的快速发展，无线频谱资源成为日益短缺的重要资源。美国联邦通信委员会(Federal communications commission,FCC)调查结果指出[1]，目前无线频谱短缺问题主要是由资源利用不平衡导致，即现有的固定频谱分配政策不能满足日益增长的对无线频谱的需求。1999年，瑞典皇家理工学院的Joseph Mitola III博士提出了认知无线电(Cognitive radio，CR)[2]概念。CR采用灵活动态的频谱管理方式，可以有效提高频谱利用效率，成为未来无线通信领域技术发展的重要方向。频谱感知是CR的关键技术之一。为了提高频谱感知的准确程度，认知无线网络当中通常采用协作频谱感知(Cooperative spectrum sensing，CSS)方法，通过结合多个次用户(Secondary user，SU)的感知结果检测主用户(Primary user，PU)的工作状态[3,4]。在认知无线电的若干组网模式当中，认知Ad hoc网络由于其无中心、自组织的特点在军事、救灾与临时组网等领域有良好的应用前景，但也由于没有固定的融合中心，使得认知Ad hoc网络的CSS问题变得更为复杂[5-7]。

一直以来，对认知Ad hoc网络基于共识算法[8,9]对节点的频谱感知结果进行融合，这种方法在网络规模较大时往往具有效率低下、错误率高等缺点。为了解决这类问题，近年来不少研究文献采用分簇方法对网络用户节点进行划分，做到针对不同的地理区域与不同的频段指定不同的认知用户进行感知，从而达到提高感知准确率，缩短感知时间的目的[10-12]。目前，对认知Ad hoc网络的分簇方法大致可以分为以下几类。根据地理位置分簇：代表有Smitha等在文献[13]中提出的分簇算法。通过各个节点上报地理位置信息对各个参与频谱感知的节点进行筛选，从而减少对一个频谱的感知节点数目，达到分簇目的。根据地理位置分簇的最大问题是不容易获得PU的具体位置，没有考虑复杂的阴影衰落、多径效应等，且很难应用于移动网络当中。根据感知结果相似程度分簇：代表有文献[14]提出的根据感知结果的相关性，对感知节点进行分簇的算法；文献[15]提出的吸引子传播算法，通过网络中相邻节点间的消息交互和更新，在相邻节点最多的信道上以可用信道最多的节点为簇首建立簇结构。根据感知结果对节点进行划分，克服了PU位置难以获取的缺点，同时也能够避免阴影衰落、多径效应造成分簇正确性的下降。优化簇规模与检测任务的分簇：在分簇算法中，往往要综合考虑簇内包含的SU节点数目与簇需要检测的PU信道数目之间的关系。簇内检测的PU信道越多，簇内可用的频谱接入机会和吞吐量越大，但同时所得到的分簇越小，这会使SU之间的合作频谱感知效果变差。此外，簇内包含太多的所需要感知的信道也会使感知时间分散，效果也更差。文献[16，17] 采用最大权重单边二部图(Maximum-weight one-sided biclique，MWB)模型优化簇规模与簇检测任务，实现对SU节点的分簇。

结合以上几种方法的优缺点，本文提出一种基于频谱感知与二部图模型的认知Ad hoc网络用户分簇算法。首先，引入检测因子(Detection factor, DF)概念，根据各个SU节点的接受信噪比，计算得到每个节点对各个PU信号的检测因子。通过检测因子将认知Ad hoc网络中的SU节点与需要检测的PU信道建模为二部图模型，使得分簇问题简化为最大权边完全二部图分解(Constraint maximum-weight edge biclique, C-MWEB)问题。最后设计一种贪婪算法，对C-MWEB问题进行有条件约束的求解。

1 数学模型

1.1 网络模型

在本文探讨的认知Ad hoc 网络模型当中，各个节点均采用全向天线进行信号收发，综合考虑地理位置、障碍物遮蔽和阴影衰落等因素对感知结果的影响，用信噪比来描述SU节点的感知效果。

考虑一个包含N个认知用户(Secondary user， SU)，m个主用户(Primary user， PU)的网络感知模型。SU保持对PU信道的实时监测，当PU未占用信道时，SU可对信道实施机会频谱接入。目前，大多数合作频谱感知方面的研究都假设PU信号可以覆盖整个认知无线网络(Cognitive radio network,CRN)网络，但实际情况中，很多PU信号功率较小，覆盖面积有限(例如手提电话信号功率只有10～50 mW[18]，传输距离只有100 m～1 km)，往往并不能覆盖整个CRN，而只能覆盖其中的小部分SU。很多距离PU发射机很远的SU设备只能检测到噪声。用检测距离RD来描述PU信号的覆盖范围，如果SU在PU的检测范围内，则可以检测到PU的活动；反之，其在相应的信道上只能检测到噪声。如果再考虑多个PU覆盖范围相互交叠的情况，以及障碍物遮蔽、阴影衰落等因素的影响，问题会变得更为复杂，如图1所示。

在图1所示的网络模型中，拥有10个SU的认知Ad hoc网络被4个PU信号覆盖，出现覆盖区域相互交叠的状况，且对于节点SU2与SU6而言，需要考虑阴影遮蔽因素对感知结果的影响。在这种情况下，传统的共识算法[8,9]将全部网络纳入感知与分配过程中，不仅耗时耗力，且效率很低，感知结果错误的可能性很大。

图2 检测时间模型 Fig.2 Detection time model

1.2 感知模型

本文默认认知Ad hoc网络各个节点同步运行，时间分为初始化阶段(主要负责初始分簇)、运行阶段与簇维护阶段。其中在系统运行的初期对网络进行初始化与分簇，而后每隔一段时间对分簇结果进行维护。运行阶段划分成若干个帧，每一帧分别包含感知阶段与信息传输阶段，在进行感知时，所有节点静默，以提高感知准确率。其原理如图2所示。

单个SU的频谱感知结果是CSS的基础。因此，先建立单个SU的频谱感知模型。本文假设采样频谱为fs，则第i个认知用户Si对信道j的感知结果为

(1)

(2)

采用能量感知，则感知检测量

(3)

虚警概率Pf,(i,j)为

(4)

式中第i个SU的检测阈值为εi，Q(x)为

(5)

若被检测信号为PSK调制时，检测概率Pd,(i,j)为

(6)

本文采用OR规则融合SU的感知结果，则合作检测概率与合作虚警概率分别为

(7)

(8)

1.3 检测因子

为了有效地保护PU通信不受干扰，要求认知网络频谱感知的检测概率要高于一个门限。即Qd,j≥Qth。由此，可以得到

(9)

由于采用OR准则进行感知结果融合，式(9)存在乘法运算。为了简化算法复杂程度，本文引入检测因子(Detection factor，DF)概念。

定义1SUi对PUj的检测因子为θij，其表示为

θij=-log(1-Pd,(i,j))

(10)

将式(10)代入式(9)，可以得到

(11)

式中θth=-log(1-Qth)为检测因子门限。

1.4 二部图模型

定义2G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集，即当i∈A时，必有j∈B。则称图G为一个二分图。可以将一个二部图表示成G(A∪B,ξ)，其中，每条边ε都连接着点集X与点集Y中的一个点，如图3所示。

定义3完全二部图(Biclique)是一种特殊的二部图，可以把图中的顶点分成两个集合，使得第1个集合中的所有顶点都与第2个集合中的所有顶点相连。因此，完全二部图只需要其两个点集就可确定，可以表示为G(S,C)，如图4所示。

图3 二部图模型

Fig.3 Bipartite graph model

图4 完全二部图模型

Fig.4 Biclique graph model

假设二部图G(A∪B,ε)中A={SU1,SU2,SU3,…,SUn}为网络认知节点的集合，B={PU1,PU2,…,PUm}为网络需要感知的PU信道的集合，若认知节点SUi可以感知PUj信道，可用边ξ连接两个点集内相应的两点。这样，网络中SU与所要感知的PU信道的关系可以构建为一个二部图模型。以检测因子θij作为二部图模型边ξ的权值，可将模型转换为一个加权二部图。因此，本文中所研究的分簇问题可以构建为将加权二部图模型分解为若干完全二部图的问题。

2 基于频谱感知的分簇算法

2.1 C-MWEB问题与求解

在研究分簇算法之前，先要对算法所要解决的问题以及所希望达到的目标函数进行建模。本文研究的算法目的是对认知Ad hoc网络中的SU节点与所感知的PU信道进行分簇，使得某一些SU节点负责感知特定的PU信道。其约束条件如下：

(1) 确保对每个PU信道的检测概率大于检测门限，即Qd,j≥Qth，或表示为检测因子θj≥θth。

(2) 在满足(1)的前提下，尽可能增加簇内备选信道的数目，同时减少对PU干扰的可能，即需要最大化簇内检测PU信道检测因子和。

(3) 本文所研究的为非交叠分簇，即每个SU只能隶属于一个簇，每个PU也只被一个簇内的SU检测。

该问题可用数学语言描述为

∀i

(12)

式中XsN×K和XpM×K代表SU与PU的分配矩阵，其中K为系统分簇的数量。

(13)

(14)

G(Sk，Ck)为由原二部图模型分解出的第k个完全二部图，也代表分离的第k个簇。其中，Sk代表第k个簇当中包含的SU节点向量，Ck代表第k个簇检测的PU信道。以检测因子θ为根据为二部图模型加权，即连接SUi节点与PUj节点的边的权值为θij，原问题可以转化为有条件约束的最大权边完全二部图分解(Constrained maximum-weight edge biclique，C-MWEB)问题。由文献[19,20]可知，C-MWEB问题为NP-complete问题。随着SU和PU信道数量的上涨，寻找问题最优解的复杂度呈指数级上升。由于C-MWEB问题为NP-complete问题，故无法在多项式时间内找到最优解，但可以通过设计一种启发式算法去寻找他的次优解。本文设计一种贪婪算法用来解决C-MWEB问题。

算法步骤如下：

(1) 设置A={SU1,SU2,…,SUn}为认知节点SU的集合向量，B={PU1,PU2,…,PUn}为主用户PU信道的集合向量。设定初始值A1=A和B1=B。对于已分配的SU节点与PU信道不再参与下一次的分配，所以对于簇k，Ak为Ak-1除去Sk-1中的点，Bk为Bk-1除去Ck-1中的点。

(2) 首先，Ck为空，Sk为所有SU的集合。在第l次迭代之后，找到具有最大检测因子和的信道bl，要求信道bl属于Bk但不属于本次迭代中的Ck，即在二部图中的度θ(ψbl)最大，其中ψbl为所有可以感知bl的SU节点的集合。

(3) 添加bl到Ck，从Sk中删除那些不能感知通道bl的SU。

(4) 计算检测因子数θsum=∑θ(Sk,Ck)。

(5) 当满足约束条件∑θ(Sk,yl)>θth且Bk剩余的信道数为0时，回到步骤(1)循环。

(6)Sk，Ck即为所要得到的第k分簇的SU与PU信道集合。

2.2 基于感知的分簇算法

基于感知的认知Ad hoc网络用户分簇算法步骤如下：

步骤1在本文中，假定每个SU接收端的噪声功率一定。故每个SU可以根据接收到PU信号的强度计算信噪比γi,j，并根据式(6)与式(10)计算检测概率Pd,(i,j)与检测因子θij。当检测因子值小于门限θth1的时候，认定其在PU覆盖范围外。

步骤2每个SU向其周围的SU广播其所测量到的信息。当每个节点接收到的信息不再更新时，所有的SU可以获得整个网络的拓扑结构与二部图G(A∪B,ε)。

步骤3运用贪婪算法在步骤2得到的二部图中分解出完全二部图，得到分簇结果。

步骤4将网络分簇之后，其中的一个SU将被选为簇头，作为数据的融合中心与网络的管理中心，负责协作频谱感知与信道的分配。簇头的选择方案可以参照移动Ad hoc网络或无线传感器网络中常用的最小标识符(Least identification,LID)方案[21]，即簇内ID值最小的簇向簇内其他成员广播宣布自己成为簇头。簇头选定之后，在每次感知阶段中簇内各个SU分别执行频谱感知并将二元决策结果传送给簇头，簇头根据OR准则进行最后判定，而后向全网广播该信道资源是否可用。

3 实验与仿真

对图1所示网络模型进行仿真。模型中包含10个SU，4个PU信道，PU信号覆盖范围相互交叠。本文只考虑路径损耗与阴影衰落，暂不考虑多径效应所带来的影响。引入路径损耗、阴影衰落之后，接收功率Pr的表达式为

Pr=PtL0L1

(15)

式中L0为自由路径损耗，L1为阴影衰落所带来的功率损耗。

假定各个接受节点端的噪声功率相等，自由空间损耗L0为

(16)

式中：λc为信号波长，d为接收机与发射机距离，Gr为接收天线增益，Gt为发射天线增益。假设SU节点与PU发射机天线均为全向天线，则Gr=Gt=1。

阴影衰落会随着障碍物位置、大小、介电特性、反射面和散射体等情况的变化而变化。在具体情况未知的情况下，通常使用统计模型来描述。阴影衰落L1一般符合对数正态分布。

(17)

式中：μφdB为衰落均值，可以采用实测值或统计值，一般等于路径损耗,φ>0。式(15)已经包含路径损耗，故这里μφdB=0；σφdB为方差，一般取值4～13 dB。

(18)

式中Dij代表节点SUi对PUj发射机的距离，单位为km。

本文中，由于障碍物的遮挡，节点SU2接收PU4的信号，节点SU6接收PU3的信号受到影响，各自对其进行8 dB的衰减，即

(19)

在实际系统中，可根据接收信号功率强度Pr得到接受信噪比。本文的实验则是通过所给定参数，通过式(15)和式(16)计算得到各个节点的信噪比，再通过式(6)得到各个节点的检测概率矩阵。设定用来判定覆盖范围的检测门限Pdth1=0.70，即检测概率小于0.7的SU判定为在该PU覆盖范围之外。模型中SU对所检测的PU信道的检测概率矩阵P为

(20)

式中pij表示节点SUi对第j个PU信道的检测概率。根据矩阵可以画出二部图模型，如图5所示。

在实际系统中，认知无线电要优先保证不影响PU的工作。因此，本文中检测门限设定为Pdth=0.99，相应的检测因子θth=4.6。分别采用传统的感知分簇方法[14]，文献[17]所采用的MWB分簇算法与本文的C-MWEB分簇算法，得到划分的簇如图6～8所示。

图5 Matlab仿真得到矩阵P所表示CRN的二部图模型

Fig.5 Bipartite graph model of matrix P in Matlab simulation

图6 基于感知结果的分簇

Fig.6 Clustering based on spectrum sensing

图7 MWB分簇算法

Fig.7 Clustering based on MWB

图8 本文C-MWEB分簇算法

Fig.8 Clustering based on proposed C-MWEB

可以看出，在多个PU信号交叠的区域，单纯依靠感知结果的分簇算法分簇数目过多，簇规模过小，不利于网络管理与运营。文献[17]提出的MWB分簇算法通过对簇内通信容量与认知用户数目进行限制，得到的分簇数目与规模合理。但由于未考虑感知结果对分簇的影响，对受到阴影衰落影响的SU2与SU6两个点的划分出现失误，地理位置分隔较远的点反而分为一簇，使得分簇出现混乱，簇与簇之间出现相互缠绕的现象。本文采用的C-MWEB分簇算法通过引入检测因子的概念，考虑了每个SU对不同PU信道具有不同的接收信噪比，从而避免了相应问题的发生，使得分簇结果更为合理。

本文所述的C-MWEB分簇算法与文献[17]提出的MWB分簇算法对PU信道的分簇结果如图9,10所示。

图9 MWB分簇算法对PU信道的分簇

Fig.9 Primary user clustering based on MWB

图10 本文C-MWEB分簇算法对PU信道的分簇

Fig.10 Primary user clustering based on proposed C-MWEB

在PU信道分配方面，由于均采用了一个信道只分配给一个簇内节点进行检测的约束条件，本文算法与文献[17]提出的MWB分簇算法所得出的结果类似。文献[17] 的MWB分簇算法中，SU1,SU8,SU9分为簇1，合作检测信道1与信道2；SU2,SU3,SU4,SU5分为簇2，合作检测信道3；SU6,SU7,SU10分为簇3，合作检测信道4；在本文算法中，SU4,SU6,SU9分为簇1，合作检测信道2与信道4；SU1,SU2,SU7,SU8,SU10分为簇2，合作检测信道1；SU3,SU5分为簇3，合作检测信道3。

4 结束语

为了提高认知Ad hoc网络频谱感知效率，解决认知Ad hoc网络分簇问题，本文提出一种基于频谱感知的认知Ad hoc网络分簇算法。该算法通过引入检测因子的概念，综合考虑多个主用户信号交叠、阴影衰落等问题对节点频谱感知结果的影响，将认知Ad hoc网络分簇问题简化为C-MWEB分解问题，并设计了一种贪婪算法对其进行求解。通过计算机仿真，验证了理论推导的结果和相关的结论，比较了本文提出的算法与传统算法的性能，证明在多个主用户信号交叠与阴影衰落并存的情况下，本文算法具有更好的可靠性和有效性。

[1] Leibovitz J S. The great spectrum debate: A commentary on the FCC spectrum policy task force′s report on spectrum rights and responsibilities[J]. Yale Ji & Tech, 2003, 6(4): 391-431.

[2] Mitola J. Cognitive radio: Making software radios more personal[J]. IEEE Personal Communications, 1999, 6(4): 13-18.

[3] 陈兵，胡峰，朱琨. 认知无线电进展[J]. 数据采集与处理, 2016, 31(3):440-451.

Chen Bing, Hu Feng, Zhu Kun. Research progress of cognitive radio[J]. Journal of Data Acquisition and Progressing, 2016, 31(3): 440-451.

[4] 张士兵，宋莲莲，刘燕，等. 基于节点识别的写作频谱检测算法[J]. 数据采集与处理, 2014, 29(5):688-693.

Zhang Shibing, Song Lianlian, Liu Yan， et al. Cooperation spectrum detection algorithm based on node recognition[J]. Journal of Data Acquisition and Progressing, 2014, 29(5):688-693.

[5] Wang B B，Liu K J R，Clancy T C．Evolutionary cooperative spectrum sensing game：How to collaborate [J]. IEEE Trans on Communication，2010，58(3)：890-900.

[6] Saad W，Han Z，Debbah M, et al．Coalitional games for distributed collaborative spectrum sensing in cognitive radio networks[C]// Proceedings of 28th Conference on Computer Communications. Rio de Janeiro, Brazil: IEEE, 2009: 2114-2122.

[7] Li Z Q, Yu F R, Huang M Y．A distributed consensus-based cooperative spectrum sensing scheme in cognitive radios[J]. IEEE Trans Veh Technol, 2010, 59: 383-393.

[8] 吴启晖, 丁国如, 王金龙,等. 认知无线网络中基于共识理论的分布式聚类合作频谱感知研究[J]. 科学通报, 2012, 57(9):776-783.

Wu Qihui, Ding Guoru, Wang Jinlong, et al. Distribute clustering cooperation spectrum sensing based on consensus in cognitive radio network[J]. Science Bulletin, 2012, 57(9):776-783.

[9] 杜智勇, 陈浩楠, 宋绯. 一种基于信噪比加权共识的合作频谱感知算法[J]. 数据采集与处理, 2013,28(2):184-189.

Du Zhiyong, Chen Haonan, Song Fei. SNR based weighted-consensus algorithm for cooperation spectrum sensing[J]. Journal of Data Acquisition and Progressing, 2013,28(2): 184-189.

[10] Alshamrani A. A novel clustering scheme for spectrum sharing in multi-hop ad hoc cognitive radio networks[C]// Electronics, Communications and Photonics Conference (SIECPC). Riyadh, Saudi Arabia: King Abdulaziz City for Science and Technology (KACST),2013:1-6.

[11] Song L, Li L, Zhao C. A novel cluster-based architecture of cognitive wireless ad-hoc networks[C]// Industrial Control and Electronics Engineering (ICICEE), 2012 International Conference on. Xi′an, China: IEEE, 2012: 23-25.

[12] Sisi L, Lazos L, Krunz M. Cluster-based control channel allocation in opportunistic cognitive radio networks[J]. Mobile Computing, IEEE Transactions on, 2012, 11(10):1436-1449.

[13] Smitha K G, Vinod A P. Cluster based cooperative spectrum sensing using location information for cognitive radios under reduced bandwidth[C]// Circuits and Systems (MWSCAS), 2011 IEEE 54th International Midwest Symposium on. Seoul, Korea: IEEE, 2011:7-10.

[14] 孙剑锋, 高锦春, 刘元安,等. 基于频谱感知结果的认知无线电用户分簇方法[J]. 电子与信息学报, 2012(4):782-786.

Sun Jianfeng, Gao Jinchun, Liu Yuanan, et al. Clustering method for cognitive radio user based on the results of spectrum sensing[J]. Journal of Electronic & Information Technology, 2012(4):782-786.

[15] Baddour K E, Ureten O, Willink T J. Efficient clustering of cognitive radio networks using affinity propagation[C]//Computer Communications and Networks, ICCCN 2009 Proceedings of 18th Internatonal Conference on. San Francisco, California: IEEE, 2009, 8:3-6.

[16] Mansoor N, Islam A, Zareei M, et al. Spectrum aware cluster-based architecture for cognitive radio ad-hoc networks[C]//Advances in Electrical Engineering (ICAEE), International Conference on. Bangladesh: IEEE, 2013:19-21.

[17] Zhang Wenjie, Yang Yiqun, Yeo C K. Cluster-based cooperative spectrum sensing assignment strategy for heterogeneous cognitive radio network[J]. IEEE Transactions on Vehicular Technology, 2015, 64(6):2637-2647.

[18] Min A W, Shin X Z K G. Detection of small-scale primary users in cognitive radio networks[J]. IEEE Sel Areas Commun, 2011(2): 349-361.

[19] Dawande M, Keskinocak P, Swaminathan J, et al. On bipartite and multipartite clique problems[J]. Algorithms, 2014, 41(2): 388-403.

[20] Peeters R. The maximum edge biclique problem is NP-complete[J]. Discrete Applied Math, 2003, 131(3): 651-654.

[21] Lin C R, Gerla M. Adaptive clustering for mobile wireless networks[J]. IEEE Journal on Selected Areas in Communications,1997,15(7):1265-1275.