邱恭安，封 森

（南通大學(xué) 電子信息學(xué)院，江蘇 南通 226019）

基于最小生成樹的分簇協(xié)作頻譜感知改進算法*

邱恭安＊＊，封 森

（南通大學(xué) 電子信息學(xué)院，江蘇 南通 226019）

為減少分簇過程中的時延，基于最小生成樹的單向比較優(yōu)勢提出簇首快速推舉方法，并提出改進的分簇協(xié)作頻譜感知算法，分析了算法的時間復(fù)雜度。算法首先基于最小劃分對所有次用戶節(jié)點進行分簇，簇內(nèi)節(jié)點根據(jù)設(shè)置的評價條件進行性能比較，推舉簇首。由簇首進行本地簇內(nèi)頻譜檢測，并上傳檢測結(jié)果，最后融合中心在簇首間實現(xiàn)協(xié)作的頻譜檢測。在瑞利信道條件下，仿真顯示在大信噪比時，融合中心應(yīng)用AND規(guī)則，系統(tǒng)具有較小的虛警率，所提算法檢測性能優(yōu);小信噪比時，應(yīng)用OR規(guī)則能擴展系統(tǒng)的有效檢測區(qū)間，所提算法在滿足系統(tǒng)要求的前提下檢測性能較差，但簇內(nèi)信道效率提高了n－1倍。

認知無線電;頻譜檢測;協(xié)作頻譜感知;最小生成樹;分簇

1 引言

分簇協(xié)作頻譜感知將分布式認知節(jié)點分成獨立簇，每個簇推舉綜合性能好的節(jié)點為簇首，僅由簇首進行頻譜感知并向融合中心上傳感知結(jié)果，最后由融合中心做出全局判決，以提高系統(tǒng)信道效率，降低融合中心計算負擔(dān)，減小簇內(nèi)節(jié)點能量消耗和動態(tài)性［1］。

分簇協(xié)作頻譜感知算法中，簇首推舉主要有最小能量消耗型的功率感知算法、最大范圍的高連通算法、基于簇大小和簇首穩(wěn)定性等要素加權(quán)的簇首推舉算法［2］。文獻［3］針對多載波系統(tǒng)對頻譜的劃分，提出根據(jù)子載波信道狀態(tài)應(yīng)用基于分簇的差異化能量檢測算法，避免惡劣信道節(jié)點出現(xiàn)在同一個簇內(nèi)，以提高系統(tǒng)檢測性能。文獻［4］根據(jù)次用戶節(jié)點共性分簇，并推舉可信度最大節(jié)點為簇首，但可信度計算為多次加權(quán)，計算復(fù)雜，簇首推舉時延大。文獻［5］應(yīng)用多門限檢測算法，對信道增益、與融合中心距離、鄰居節(jié)點數(shù)和與鄰居節(jié)點間的平均距離4個參數(shù)進行加權(quán)，選最優(yōu)者為簇首，但算法存在計算量和開銷大問題。文獻［6］研究了噪聲不確定性信道中分簇協(xié)作算法，推舉報告信道波動性最小的節(jié)點為簇首，該方法具有較強的針對性。文獻［7］利用位置信息進行分簇，并推舉簇內(nèi)中心節(jié)點為簇首，該算法過度依賴位置信息。

目前分簇協(xié)作算法存在計算復(fù)雜、無線信道開銷大或簇穩(wěn)定性較差等不足。本文利用最小生成樹的單向比較優(yōu)勢提出快速簇首推舉方法，減小簇首推舉時間?；诖颂岢龅姆执貐f(xié)作頻譜感知算法與傳統(tǒng)分簇算法不同的是并不追求最佳的系統(tǒng)檢測性能，而是在滿足系統(tǒng)要求的檢測性能下，擴展系統(tǒng)檢測區(qū)間或提高系統(tǒng)穩(wěn)定性，減小時延，降低節(jié)點能耗，探索綜合性能優(yōu)的可行性算法。

2 生成樹理論基礎(chǔ)

認知無線網(wǎng)絡(luò)由主用戶（Primary User，PU）和次用戶（Secondary User，SU）組成，設(shè)所有次用戶節(jié)點構(gòu)成網(wǎng)絡(luò)頂點集合V，相互之間連線構(gòu)成邊集合E，節(jié)點間的屬性參量為權(quán)值，共同構(gòu)成賦權(quán)連通圖G=（V，E）。

定義1:對于連通圖G=（V，E），其中V為頂點集合，E為邊集合，其任意兩個頂點之間存在一條路徑，稱無圈（環(huán)）的連通圖為樹（Tree）。

定義2:對于連通圖G的所有樹T，稱包含了圖G中所有頂點的樹為生成樹，即有V（T）=V（G）。

給定圖 G=（V，E），其生成樹算法如下［8］:

3 分簇協(xié)作頻譜感知

分簇協(xié)作頻譜感知模型如圖1所示，主要包括節(jié)點簇建立、簇首推舉和協(xié)作融合判決三部分。

借代跟漢語常用詞相互關(guān)聯(lián)也有兩方面的表現(xiàn):一是借代影響漢語的造詞;二是借代影響漢語詞義的變化發(fā)展,是引起詞的義項增加的一種重要方式。

圖1 分簇協(xié)作頻譜感知模型Fig.1 Clustering cooperative spectrum sensing model

3.1 基于最小劃分的節(jié)點簇

節(jié)點簇是一序列在某種屬性上相關(guān)聯(lián)節(jié)點的集合，能夠減小簇內(nèi)節(jié)點拓撲范圍和動態(tài)性，主要要素包括簇的連通性、簇大小和簇首穩(wěn)定性?？紤]頻譜檢測節(jié)點的能量、連通性和集中度，采用最小劃分算法建立節(jié)點簇［9］。

定義3:設(shè)網(wǎng)絡(luò)圖G中節(jié)點集合V，存在最小正整數(shù)q使得節(jié)點集合V的劃分S={V1，V2，…，Vq}滿足每個Vi都是一個完整子圖，且對所有的i=1，2，…，q 均有 Vi≠，∪qi=1Vi=V，Vi∩Vj= ，則稱 S為最小劃分。

對于G的最小劃S，具有如下兩條性質(zhì):

性質(zhì)1:被劃分的節(jié)點只能屬于某一個簇;

性質(zhì)2:每個被劃分的簇應(yīng)該是極大簇。

算法關(guān)鍵是分布式地尋找公共鄰居節(jié)點來更新所屬簇的維數(shù)，其中公共鄰居指簇內(nèi)所有節(jié)點的共同鄰居節(jié)點。每個節(jié)點需維護一個簇列表和一個鄰節(jié)點列表，算法根據(jù)輸入拓撲圖進行劃分，并輸出每個節(jié)點所屬的簇，實現(xiàn)簇的建立。

3.2 基于最小生成樹的簇首推舉

簇首的產(chǎn)生需要快速，一旦產(chǎn)生則需要穩(wěn)定，保證協(xié)作頻譜檢測的實時性和可靠性。設(shè)簇內(nèi)節(jié)點緩存自身相關(guān)權(quán)值，包括信噪比、剩余能量、與融合中心距離等參量，且相鄰節(jié)點間能相互通信。

設(shè)簇內(nèi)節(jié)點數(shù)為N，簇內(nèi)節(jié)點與數(shù)據(jù)融合中心距離為D，并根據(jù)D大小對節(jié)點進行排序。首先最小D節(jié)點聲稱為簇首H，隨后與次小D節(jié)點進行權(quán)值比較，推舉性能優(yōu)者為新候選簇首，同時向?qū)Ψ桨l(fā)送“member”信息，接收其為簇員節(jié)點，簇員節(jié)點回復(fù)“head”消息進行確認。若次用戶節(jié)點收到“member”信息，則不再與任何節(jié)點比較，直到系統(tǒng)再次初始化。重復(fù)節(jié)點間的性能比較，則經(jīng)過N－1次計算后產(chǎn)生簇首H，推舉流程如圖2所示。

圖2 簇首推舉流程圖Fig.2 Diagram of cluster head election

3.3 基于協(xié)作的全局判決

設(shè)簇內(nèi)節(jié)點應(yīng)用能量檢測算法對主用戶狀態(tài)進行本地檢測，能量檢測算法不需要預(yù)知主用戶信號特征，將接收信號總能量的判決值與判決門值比較判斷主用戶信號存在與否。因此，轉(zhuǎn)化為二元假設(shè)檢驗:

式中，x（t）為次用戶接收到的信號，s（t）為主用戶發(fā)射信號，h（t）為主用戶信號的信道增益，n（t）為噪聲信號，H1和H0分別表示主用戶存在和不存在兩種狀態(tài)。

在全局協(xié)作的數(shù)據(jù)融合中，融合中心可應(yīng)用硬判決AND或OR規(guī)則進行數(shù)據(jù)融合。設(shè)認知無線網(wǎng)絡(luò)中有M個次用戶節(jié)點，其中第i個簇簇首的本地檢測概率和虛警概率分別為Pdi、Pfi，則采用 OR準則融合后系統(tǒng)全局檢測概率和虛警概率為

分簇協(xié)作中僅由推舉的簇首代表簇內(nèi)節(jié)點檢測并上傳主用戶狀態(tài)數(shù)據(jù)，因此，簇首須具有本地最優(yōu)的性能，如最大信噪比。而數(shù)據(jù)融合中心則應(yīng)用配置融合準則對簇首上傳結(jié)果進行融合計算，作出系統(tǒng)全局判決，隨后將全局判決結(jié)果回傳給簇首，由簇首在簇內(nèi)廣播全局判決。

3.4 時間復(fù)雜度分析

次用戶節(jié)點分布狀態(tài)改變時，節(jié)點需要重新分簇，當(dāng)節(jié)點簇穩(wěn)定后系統(tǒng)進行協(xié)作頻譜檢測，因此，簇生成時延直接影響頻譜檢測性能。該時延包括分簇建立時間和簇首推舉過程時間。

若系統(tǒng)次用戶節(jié)點總數(shù)為M，則按最小劃分建立分簇時間復(fù)雜度約為O（M），各分簇并行運算簇首推舉算法［9］。設(shè)簇內(nèi)平均節(jié)點數(shù)為N，則按Prim算法各節(jié)點對間權(quán)值排序時間復(fù)雜度為o（N lg N）［10］。隨后，推舉簇內(nèi)接收信噪比最大節(jié)點為簇首過程需要（N－1）次比較。因此，一個周期內(nèi)，系統(tǒng)總時間復(fù)雜度為o（M+N lg N）。

若系統(tǒng)按次用戶節(jié)點位置進行分簇，并根據(jù)報告信道狀態(tài)推舉簇首［6］，則其簇建立時間復(fù)雜度約為O（M）。仍然設(shè)簇內(nèi)平均節(jié)點數(shù)為N，則簇內(nèi)節(jié)點兩兩進行報告信道狀態(tài)交叉比較，其時間復(fù)雜度為o（N2）。若先從M個節(jié)點中推舉簇首，然后由簇首添加其他節(jié)點作為簇員（如經(jīng)典LEACH算法），則其時間復(fù)雜度為o（N2lg N）?？梢?，所提算法簇生成時延較小。

4 性能仿真與分析

在瑞利衰落信道中，基于Matlab對所提算法的頻譜檢測性能進行了仿真比較?？紤]次用戶節(jié)點實際有限能量、單個簇內(nèi)節(jié)點數(shù)上限為9的要求，仿真取時間帶寬積為5，隨機生成15個次用戶節(jié)點，劃分為3個簇，簇平均節(jié)點數(shù)為5。在實際應(yīng)用環(huán)境中，單個簇內(nèi)所有節(jié)點出現(xiàn)相等或近似信噪比（此時僅需配置簡單的全節(jié)點頻譜檢測算法）的可能性小，因此，大信噪比時，設(shè)簇節(jié)點信噪比取值范圍為［1，10］dB;小信噪比時，設(shè)簇節(jié)點信噪比取值范圍為［－10，－1］dB，推舉簇首的性能指標為節(jié)點接收信噪比SNR。

在不同信道狀態(tài)條件下，對數(shù)據(jù)融合中心應(yīng)用AND規(guī)則和OR規(guī)則時，分簇協(xié)作頻譜感知算法的系統(tǒng)檢測性能進行了仿真計算，分別如圖3（簇首SNR=9 dB）和圖4（簇首SNR=－1 dB）所示。

圖4 小信噪比全局檢測性能Fig.4 Global performance under low SNR

在大信噪比時，如圖3所示，兩種融合規(guī)則下的算法檢測性能均能達到系統(tǒng)工作要求，即檢測概率大于0.9，同時虛警率小于0.1，其中OR融合規(guī)則系統(tǒng)檢測概率略大，但虛警率也略大。在小信噪比時，如圖4所示，AND融合規(guī)則下算法檢測性能已不能滿足系統(tǒng)工作要求，但OR融合規(guī)則下系統(tǒng)檢測性能較好，且存在一定的檢測區(qū)間。

綜上所述，在大信噪比狀態(tài)時，融合中心選用AND規(guī)則能夠減小系統(tǒng)虛警率，而在小信噪比狀態(tài)時，選用OR規(guī)則能夠提高系統(tǒng)檢測概率，擴大系統(tǒng)有效檢測區(qū)間。

針對融合規(guī)則與信道狀態(tài)間的關(guān)系，與傳統(tǒng)全節(jié)點協(xié)作頻譜感知算法［11］進行了系統(tǒng)檢測性能比較。大信噪比AND規(guī)則時，系統(tǒng)檢測性能如圖5所示;小信噪比 OR規(guī)則時，系統(tǒng)檢測性能如圖6所示。

圖6 小信噪比OR規(guī)則算法性能Fig.6 Proposed algorithm performance under low SNR and OR rule

由圖5可知，由于全部節(jié)點中存在信噪比低的次用戶節(jié)點，其本地檢測結(jié)果正確率不高，在嚴格的AND融合規(guī)則下導(dǎo)致傳統(tǒng)全節(jié)點協(xié)作頻譜感知檢測概率下降，而僅選擇信道條件好的簇首進行協(xié)作頻譜檢測概率，其系統(tǒng)檢測性能較好，體現(xiàn)出選擇高信噪比節(jié)點檢測頻譜的可靠性。

由圖6可知，在小信噪比OR規(guī)則中，傳統(tǒng)全節(jié)點協(xié)作模式的檢測概率優(yōu)于簇首協(xié)作模式，但其信道效率則僅為簇首協(xié)作的1/n（n為簇內(nèi)節(jié)點數(shù)），同時全節(jié)點協(xié)作虛警率也大于簇首協(xié)作模式。

5 總結(jié)

傳統(tǒng)分簇協(xié)作頻譜感知算法分簇計算復(fù)雜，容易產(chǎn)生死循環(huán)，導(dǎo)致較大時延和簇不穩(wěn)定。本文所提算法利用最小生成樹的開環(huán)特征避免簇首推舉比較中的重復(fù)性，各分簇并行運行，減小了時間復(fù)雜度，降低了節(jié)點計算能耗。隨后，僅簇首間進行協(xié)作頻譜檢測，由數(shù)據(jù)融合中心作出系統(tǒng)全局判決。仿真顯示所提算法在大信噪比AND規(guī)則下，能夠滿足系統(tǒng)性能要求而傳統(tǒng)算法已處于失效狀態(tài);在小信噪比OR規(guī)則下，所提算法在系統(tǒng)有效檢測區(qū)間內(nèi)，較全節(jié)點協(xié)作算法檢測概率差，但信道效率高，虛警率也略低。因此，所提算法在滿足系統(tǒng)檢測性能要求前提下，具有時延小、信道效率高的優(yōu)勢。

在實際應(yīng)用中，融合中心可以同時配置多種融合規(guī)則，但是估計簇首節(jié)點的實時狀態(tài)，并根據(jù)不同簇首狀態(tài)獨立選擇合適切換時間需要深入探討。

［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，F(xiàn)ernando 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］ 徐俊明.圖論及其應(yīng)用［M］.北京:中國科學(xué)技術(shù)大學(xué)出版社，2010.

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

［9］胡罡，徐明，劉麗霞，等.無線認知網(wǎng)絡(luò)中一種團劃分的頻譜感知算法［J］.軟件學(xué)報，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］岳靜文，陳志，鄭寶玉，等.基于可靠次用戶信息的協(xié)作頻譜感知算法研究［J］.電子與信息學(xué)報，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，F(xiàn)ENG 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

邱恭安!，封森.基于最小生成樹的分簇協(xié)作頻譜感知改進算法［J］.電訊技術(shù)，2014，54（5）:564 －568.［QIU Gong －an，F(xiàn)ENG 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

國家自然科學(xué)基金資助項目（61371113）;南通市應(yīng)用研究計劃項目（BK2013052）;南通大學(xué)研究生科技創(chuàng)新計劃項目（YKC13008）

邱恭安（1973—），男，湖北浠水人，博士，副教授，主要研究方向為認知車載網(wǎng)絡(luò)理論與技術(shù);

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—），男，江蘇徐州人，碩士研究生，主要研究方向為認知無線網(wǎng)絡(luò)。

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