徐 寧，張滬寅，王 晶，徐 方，汪志勇

(武漢大學(xué)計算機學(xué)院，湖北武漢 430072)

?

認(rèn)知Ad Hoc網(wǎng)絡(luò)中基于信道相似度的分簇算法研究

徐 寧，張滬寅，王 晶，徐 方，汪志勇

(武漢大學(xué)計算機學(xué)院，湖北武漢 430072)

針對傳統(tǒng)分簇算法無法適用于信道動態(tài)變化的認(rèn)知Ad Hoc網(wǎng)絡(luò)，提出了一種基于信道相似度的分布式分簇算法.首先計算節(jié)點間的信道相似度，利用改進(jìn)的EM算法估計節(jié)點屬于不同簇的概率，再結(jié)合圖的最小割算法取得最優(yōu)的分簇結(jié)果.算法既最大化簇內(nèi)相似度，也最小化簇間相似度.最后，提出了一個協(xié)調(diào)機制，可以同步全局的分簇信息.整個過程完全分布式運行，并且無需依賴公共控制信道.仿真結(jié)果表明，算法能夠根據(jù)信道變化，動態(tài)地調(diào)整分簇結(jié)構(gòu)，提高簇內(nèi)公共信道數(shù)量.與此同時，算法還能有效減少簇間公共信道，降低簇間通信干擾.

認(rèn)知Ad Hoc網(wǎng)絡(luò)；分簇算法；信道相似度

1 引言

近年來，隨著無線設(shè)備的急速增加，ISM開放頻段已經(jīng)變得擁擠不堪，然而許多已分配的授權(quán)頻段卻沒有被充分利用[1].認(rèn)知無線電技術(shù)是提高頻譜效率的有效技術(shù)手段[2].配備認(rèn)知無線電(Cognitive Radio)的次用戶節(jié)點(Secondary User,SU)能夠感知環(huán)境中的頻譜資源，重新配置(Reconfigure)自己的射頻參數(shù)，在不干擾主用戶(Primary User,PU)的前提下，伺機使用PU的授權(quán)頻段進(jìn)行通信，從而提高授權(quán)頻段的使用效率.認(rèn)知Ad Hoc網(wǎng)絡(luò)(Cognitive Radio Ad Hoc Network,CRAHN)因為具有較高的靈活性和拓展性，成為目前研究關(guān)注的焦點[2].

分簇技術(shù)是提高Ad Hoc網(wǎng)絡(luò)效率的有效手段，它可以有效地降低網(wǎng)絡(luò)復(fù)雜度、減小網(wǎng)絡(luò)協(xié)調(diào)開銷、提高網(wǎng)絡(luò)拓展性、延長網(wǎng)絡(luò)時間[3].許多上層協(xié)議，如路由協(xié)議[4,5]、定位算法[6]，都需要借助分簇技術(shù)才能夠適用于Ad Hoc網(wǎng)絡(luò)環(huán)境.

傳統(tǒng)的Ad Hoc網(wǎng)絡(luò)分簇算法需要通過公共控制信道(Common Control Channel)來交換控制信息.但是在CRAHN中，不同SU通過認(rèn)知無線電技術(shù)感知的可用信道也不同，這就會導(dǎo)致SU之間因為沒有公共信道而無法創(chuàng)建交換控制信息.另一方面，即使SU之間能夠找到公共控制信道，但是SU的感知信道是隨時間動態(tài)變化的，因此，沒有辦法保證預(yù)設(shè)的公共控制信道在任何時刻都是可用的.例如，在圖1中，有3個主用戶PU1、PU2和PU3，它們占用的授權(quán)頻段分別為1號信道、5號信道和2號信道.SU1-SU8表示的是八個次用戶，括號內(nèi)是他們各自感知的可用信道集合.從圖中可以看到，對于全體次用戶SU1-SU8而言，它們的可用信道集合交集為空，即不存在公共信道.

為了解決CRAHN中的分簇問題，我們提出了一個基于信道相似度的分簇算法.首先，通過鄰居發(fā)現(xiàn)過程獲取局部的網(wǎng)絡(luò)拓?fù)?然后，根據(jù)這些局部信息，將網(wǎng)絡(luò)節(jié)點的信道相似度信息按照高斯混合模型(Gaussian Mixture Model，GMM)建模，用最大似然法估計每個節(jié)點屬于不同簇的概率.接著，把網(wǎng)絡(luò)分簇問題形式化為圖割問題，通過計算最小割取得最優(yōu)的分簇結(jié)果.算法不僅最大化簇內(nèi)信道相似度，同時也最小化簇間信道相似度.最后，通過一個網(wǎng)絡(luò)協(xié)調(diào)機制，將不同節(jié)點獨立計算的分簇結(jié)果在網(wǎng)絡(luò)中進(jìn)行同步，使得所有節(jié)點擁有一致的網(wǎng)絡(luò)分簇信息.

本文的貢獻(xiàn)主要體現(xiàn)在以下幾個方面：

(1)在無公共控制信道的CRAHN中實現(xiàn)控制報文的交換；

(2)給出了信道相似度的定義，并提出了一個基于信道相似度的分簇算法；

(3)設(shè)計了一個網(wǎng)絡(luò)協(xié)調(diào)機制，僅通過一次廣播就能夠同步所有節(jié)點的分簇結(jié)果.

2 系統(tǒng)模型

我們將CRAHN看作一個帶權(quán)無向圖G(V,E)，其中V代表節(jié)點集合，它代表所有的次用戶，次用戶數(shù)量為N=|V|；E代表所有邊的集合，它代表次用戶間的單跳鏈路.邊的權(quán)值wij表示節(jié)點間的信道相似度，其中i、j分別對應(yīng)邊的兩個端點.

3 鄰居發(fā)現(xiàn)

CRAHN是一個自組織的網(wǎng)絡(luò)，節(jié)點之間都是對等關(guān)系.在CRAHN中，由于沒有預(yù)先分配的公共控制信道，所以簡單的廣播無法適用.為了解決這個問題，我們采用下面的鄰居發(fā)現(xiàn)協(xié)議.

(2)在時隙t內(nèi)，如果第t條信道可用，則SUi廣播自己的鄰居集合Ngbi，并將收到的SUj的鄰居集合Ngbj加入到自身的Ngbi中；如果信道不可用，則在該時隙內(nèi)休眠；

(3)直至遍歷C中所有信道.

需要注意的是，上述鄰居發(fā)現(xiàn)協(xié)議還依賴次用戶之間的時隙同步.通常，我們可以使用信號發(fā)生器，在多條信道同時發(fā)射引導(dǎo)信號，次用戶一旦接收到引導(dǎo)信號便啟動鄰居發(fā)現(xiàn)過程.但是，次用戶之間仍會存在細(xì)小的時隙漂移.因此，為了取得更好的同步效果，應(yīng)適當(dāng)延長網(wǎng)絡(luò)的時隙長度.假設(shè)網(wǎng)絡(luò)的最大廣播時延為δmax，將時隙長度設(shè)置為2δmax就能保證有充分的交互時間.需要注意的是，在整個分簇分簇過程中，我們假設(shè)主用戶的狀態(tài)不發(fā)生改變，即次用戶的可用信道集合不發(fā)生變化.

4 分簇算法

本節(jié)我們提出一個基于信道相似度的分布式分簇算法.一方面，通過最大化簇內(nèi)節(jié)點相似度來取得更多的簇內(nèi)公共信道；另一方面，通過最小化簇間信道相似度來減小簇與簇之間的干擾.

4.1 信道相似度的定義

首先，我們給出節(jié)點間信道相似度的定義.

定義 節(jié)點i與節(jié)點j的信道相似度為

其中ci、cj是節(jié)點i、j的信道向量，RSSIij是節(jié)點間的平均接收信號強度，RSSImin是最小信號接收強度，α是路徑損耗系數(shù)，h是節(jié)點跳數(shù).

通過相似度的計算，我們就將鄰居節(jié)點的信道向量映射為一個(0,1)區(qū)間上的實數(shù).

4.2 圖的分割

假設(shè)執(zhí)行分簇算法的節(jié)點是SUi.分簇算法實際上就是要找到一個最優(yōu)的圖割，使得分割后的兩個子圖之間相似度最小，但它并不能保證子圖內(nèi)部具有較高的相似度.為了解決這個問題，我們需要對圖G進(jìn)行必要的修改.

如圖2所示，在原圖G中，加入兩個輔助節(jié)點S和T，并將所有的節(jié)點與S、T連接.節(jié)點p與S連線的權(quán)值為p、S被劃分到同一子圖的概率，即wpS=Pr(p∈S)；節(jié)點p與T連線的權(quán)值為p、T被劃分到同一子圖的概率，即wpS=Pr(p∈T).它們的具體計算方法將在下文介紹.

引入輔助邊后，圖割Q被分為了兩類，一類是屬于原圖G中邊集E的割邊，它們的權(quán)值之和記為WE；另一類屬于輔助邊集合F的割邊，它們的權(quán)值之和記為WF.可以看出，WE越小，說明相似度權(quán)值低的邊被割斷，子圖間的相似度也就越?。欢鳺F越小，說明隸屬概率較低的節(jié)點被剔除，節(jié)點屬于對應(yīng)子圖的概率就越高.因此，G+的最小割既能保證分割后的兩個子圖之間相似度最低，也能保證子圖內(nèi)部相似度最高.這里，我們采用Boykov、Kolmogorov的Min-Cut/Max-Flow算法[19]，因為它能快速求解圖的最小割.分割后，SUi所在的子圖就是初始的分簇結(jié)果.

下面介紹輔助邊的權(quán)值計算，即估計節(jié)點屬于簇內(nèi)或簇外的概率.

4.3 概率估計

首先，SU計算自己與所有鄰居節(jié)點的相似度，得到一個相似度向量x={x1,x2,…,xn}，其中xi表示SU與節(jié)點i的信道相似度，n是SU鄰居節(jié)點數(shù)量.下面我們用高斯混合模型(GMM)對x進(jìn)行建模.假設(shè)x是由2個高斯分布混合而成的，分別對應(yīng)簇內(nèi)數(shù)據(jù)和簇外數(shù)據(jù)，那么x的概率密度函數(shù)為

p(x)=π0N0(x|μ0,σ0)+π1N1(x|μ1,σ1)

其中Nk(x|μk,σk)(k=0,1)表示期望為μk、標(biāo)準(zhǔn)差為σk的高斯概率密度函數(shù)，πk表示高斯分量在模型中所占的權(quán)重.

令ri=Pr(xi∈N0)(xi∈x)，表示xi由簇內(nèi)分量N0生成的概率，即節(jié)點i屬于簇內(nèi)的概率.那么，每個xi可以看作是由簇內(nèi)高斯分量N0和簇外高斯分量N1混合而成.因此，ri可以由式(1)計算.

(1)

現(xiàn)在，問題就轉(zhuǎn)化為根據(jù)已知數(shù)據(jù)x={x1,x2,…,xn}估計GMM的參數(shù).最大似然法是常用的參數(shù)估計方法，我們定義似然函數(shù)為

(2)

由于式(2)無法通過求導(dǎo)直接計算極值，我們采用EM算法(Expectation Maximization Algorithm)，以迭代的方式來獲取參數(shù)的最大似然估計.算法主要包含四個步驟：

(1)初始化設(shè)置.用Min-Cut/Max-Flow算法對原始圖G進(jìn)行分割，若節(jié)點i與SU同簇，則令ri=1，否則ri=0.

(2)參數(shù)估計.假設(shè)ri是正確的，那么可以根據(jù)式(3)計算GMM的參數(shù).

(3)

其中，n0為N0在所有xi中所占比重的總和，n1為N1在所有xi中所占比重的總和.

(3)更新ri.將步驟(2)中計算的參數(shù)代入式(1)，獲取新的ri值.

(4)重復(fù)步驟(2)(3)，直到參數(shù)收斂，最終的ri即為所求.

5 簇的一致性協(xié)調(diào)與維護(hù)機制

5.1 一致性協(xié)調(diào)

在鄰居發(fā)現(xiàn)階段中，不同節(jié)點有不同的鄰居，因此它們的分簇結(jié)果也會存在差異.下面，我們提出了一套協(xié)調(diào)機制來消除這種不一致性.

將次用戶SUi的分簇結(jié)果記為Di(Xi,Wi).Di是一個二元組，Xi表示簇內(nèi)次用戶集合；Wi表示簇的效用值，由式(4)定義，其中〈Xi,Xi〉表示簇內(nèi)所有非輔助邊的集合.

(4)

首先，SUi將自己的分簇結(jié)果Di通過鄰居發(fā)現(xiàn)協(xié)議進(jìn)行廣播，在4-跳鄰居范圍內(nèi)交換分簇結(jié)果.將收集到的分簇結(jié)果集合記為DSi={D1,D2,…,Dn}，其中n為SUi的鄰居節(jié)點數(shù)量.接下來，SUi順序執(zhí)行下面的兩個操作.

5.2 簇的維護(hù)機制

當(dāng)網(wǎng)絡(luò)簇結(jié)構(gòu)建立之后，一旦PU開始活動，那么將會影響簇內(nèi)的公共可用信道資源.我們可以利用多條備用信道來保持簇結(jié)構(gòu)的穩(wěn)定性，具體的流程如圖3所示.

當(dāng)分簇完成之后，簇內(nèi)節(jié)點就根據(jù)可用信道列表協(xié)商出一個備用信道順序.當(dāng)檢測到有PU活動時，簇內(nèi)節(jié)點根據(jù)事先協(xié)商的順序，在備用信道中進(jìn)行切換操作，同時更新可用信道列表.一旦切換成功，再次進(jìn)行備用信道列表的協(xié)商.這樣就能延長分簇的有效時間，從而保持簇結(jié)構(gòu)的穩(wěn)定狀態(tài).

6 性能評估

本節(jié)我們將通過仿真實驗來評估分簇算法在認(rèn)知Ad Hoc網(wǎng)絡(luò)動態(tài)環(huán)境下的性能.在100×100的區(qū)域內(nèi)，隨機地部署一定數(shù)量的次用戶，次用戶的通信范圍設(shè)置為10.我們通過調(diào)整次用戶數(shù)量和信道總數(shù)來評估算法的各項性能指標(biāo)，所有數(shù)據(jù)都是100次實驗的平均值.

作為參考，我們對比了另外三種協(xié)議，他們分別是：(a)CogMesh[14,15]；(b)SOC[18]；(c)文獻(xiàn)[11]中提出的算法.為了方便下文引用，我們將[11]中的算法稱為VBC(Virtual Backbone Construction)，將本文的算法稱為CAC(Channel-Aware Clustering).

6.1 不同的節(jié)點數(shù)量

在第一組實驗中，我們固定信道總數(shù)(M=20)，不斷增大網(wǎng)絡(luò)節(jié)點數(shù)量，考察其對算法的影響.

圖4(a)展示了網(wǎng)絡(luò)中分簇數(shù)量與次用戶節(jié)點數(shù)量之間的關(guān)系.可以看出，一類是隨著節(jié)點數(shù)量的增加，CogMesh、VBC的分簇數(shù)量基本保持不變，如；CogMesh算法中，每個節(jié)點的通信范圍內(nèi)只存在一個簇首，因此分簇數(shù)量可以近似地表示為區(qū)域面積與節(jié)點的通信覆蓋面積之比.因此，在節(jié)點通信范圍一定的情況下，CogMesh算法的分簇數(shù)量是一個常數(shù).VBC是一個基于地理位置的分簇算法，它先將物理區(qū)域劃分為若干子區(qū)域，然后再子區(qū)域內(nèi)選擇簇首，分簇數(shù)量只與子區(qū)域的數(shù)量有關(guān)，而與網(wǎng)絡(luò)節(jié)點數(shù)量無關(guān).SOC和CAC是根據(jù)節(jié)點間的信道相似度分簇，在主用戶數(shù)量保持不變的情況下，SOC、CAC的分簇數(shù)量與次用戶數(shù)量有關(guān).圖4(a)中，CAC的曲線位置要明顯低于SOC，因此CAC的簇間協(xié)調(diào)開銷要小于SOC.

圖4(b)展示了單節(jié)點簇的分布情況.單節(jié)點簇的形成是由于節(jié)點孤立于其它節(jié)點導(dǎo)致的，主要受網(wǎng)絡(luò)拓?fù)浜蜕漕l范圍的影響.從圖中可以看到，當(dāng)節(jié)點數(shù)量大于200時，單節(jié)點簇基本消失.這是因為網(wǎng)絡(luò)節(jié)點密度增大后，節(jié)點分布更加緊湊，出現(xiàn)孤立節(jié)點的概率降低.當(dāng)節(jié)點數(shù)量小于200時，CAC算法能夠很好的控制單節(jié)點簇的產(chǎn)生.因為算法對最小割進(jìn)行了改進(jìn)，降低了分割單個節(jié)點的概率.

圖4(c)展示了簇內(nèi)公共信道數(shù)與節(jié)點數(shù)量的關(guān)系.可以看到，由于CogMesh、VBC算法都沒有考慮節(jié)點信道的動態(tài)特性，CAC曲線的下降速率要略大于SOC，這是由于SOC采用最大二分圖算法進(jìn)行分簇，可以取得最大的簇內(nèi)公共信道，但是并沒有考慮簇間的干擾問題.而CAC則采用了改進(jìn)的圖最小割算法，不但考慮簇內(nèi)公共信道，還引入了最小化簇間公共信道的優(yōu)化目標(biāo)，這種權(quán)衡導(dǎo)致了CAC在簇內(nèi)公共信道數(shù)量上稍低于SOC.

圖4(d)展示了簇間公共信道數(shù)與節(jié)點數(shù)量的關(guān)系.雖然當(dāng)節(jié)點數(shù)大于200時，簇間信道數(shù)量趨近于0，但節(jié)點數(shù)量在200以內(nèi)時，算法之間仍有比較明顯的差異.從圖中可以看到，CAC的簇間信道數(shù)量最少.

6.2 不同的信道總數(shù)

在第二組實驗中，我們固定節(jié)點數(shù)量不變(N=200)，考察信道總數(shù)對算法的影響.

從圖5(a)可以看出，CogMesh、VBC算法由于對信道變化不敏感，所以它們的分簇數(shù)量基本保持不變.而SOC、CAC算法的分簇數(shù)量，隨著信道數(shù)量地增加會緩緩降低，這是因為信道總數(shù)的增加會導(dǎo)致公共信道的增加.在保證簇內(nèi)公共信道數(shù)量穩(wěn)定的前提下，單個簇能夠容納更多的節(jié)點，所以分簇數(shù)量就會減少.CAC的分簇數(shù)量少于SOC，因此在簇間開銷上存在優(yōu)勢.

圖5(b)展示了單節(jié)點簇的數(shù)量，VBC、CAC算法要遠(yuǎn)低于其它兩種算法.VBC單節(jié)點簇低的原因是子區(qū)域出現(xiàn)孤立節(jié)點的概率降低，而CAC通過最大化簇內(nèi)相似度，降低出現(xiàn)單節(jié)點的圖割的概率.

圖5(c)展示了簇內(nèi)公共信道數(shù)量隨信道總數(shù)的變化情況.所有曲線都呈逐步增長的趨勢，SOC、CAC仍舊在公共信道上取得較大的優(yōu)勢，但隨著信道總數(shù)的增加，這種優(yōu)勢將會逐步的縮小.而事實上，信道資源通常十分有限，不會出現(xiàn)大量的可用信道.因此，SOC、CAC更適合認(rèn)知Ad Hoc網(wǎng)絡(luò).

圖5(d)展示了簇間公共信道數(shù)量隨信道總數(shù)的變化情況.CogMesh、SOC的簇間公共信道數(shù)量隨著信道總數(shù)而快速增長.CAC的簇間公共信道數(shù)最小，這有利于降低簇間干擾.

7 總結(jié)與展望

本文研究了認(rèn)知Ad Hoc網(wǎng)絡(luò)的分簇問題.由于認(rèn)知Ad Hoc網(wǎng)絡(luò)中信道隨時間動態(tài)變化，而且不存在預(yù)先分配的公共控制信道，因此傳統(tǒng)的分簇算法很難滿足認(rèn)知Ad Hoc網(wǎng)絡(luò)在性能、效率上的需求.本文提出了一個基于信道相似度的分布式分簇算法，將認(rèn)知網(wǎng)絡(luò)的分簇問題形式化為圖論中的最小圖割問題，既最大化簇內(nèi)節(jié)點的相似度，又最小化簇間節(jié)點的相似度.該算法能夠完全分布式地運行，并且以較低的廣播開銷完成整個分簇過程，可以應(yīng)用于實際的無線網(wǎng)絡(luò)環(huán)境中.

但是，該協(xié)議目前只適用于擬靜態(tài)的網(wǎng)絡(luò)，我們的下一步工作是研究如何將其應(yīng)用于移動環(huán)境中.首先，利用分簇算法執(zhí)行過程中獲得的局部網(wǎng)絡(luò)狀態(tài)，認(rèn)知節(jié)點可以維護(hù)一個鄰簇信息列表.當(dāng)節(jié)點即將脫離分簇時，它可以在鄰簇列表中檢測自己應(yīng)該加入的分簇，然后調(diào)整射頻參數(shù)執(zhí)行切換操作，最終加入新的分簇.這樣，網(wǎng)絡(luò)簇結(jié)構(gòu)就得到了相對穩(wěn)定.此外，還可以將節(jié)點的移動特性融入到分簇問題的約束當(dāng)中，求解新的最優(yōu)化問題，從而構(gòu)造更有利于節(jié)點進(jìn)行移動、切換的簇結(jié)構(gòu).

[1]Akyildiz I F,Lee W-Y,Chowdhury K R.CRAHNs:cognitive radio ad hoc networks[J].Ad Hoc Networks,2009,7(5):810-836.

[2]Akyildiz I F,Lee W-Y,Vuran M C,et al.NeXt generation/dynamic spectrum access/cognitive radio wireless networks:a survey[J].Computer Networks,2006,50(13):2127-2159.

[3]Younis O,Fahmy S.Distributed clustering in ad-hoc sensor networks:a hybrid,energy-efficient approach[A].Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies[C].Hong Kong:IEEE,2004.629-640.

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

[5]Banerjee S,Khuller S.A clustering scheme for hierarchical control in multi-hop wireless networks[A].Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies[C].Alaska:IEEE,2001.1028-1037.

[6]Estrin D,Govindan R,Heidemann J,et al.Next century challenges:scalable coordination in sensor networks[A].Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking[C].Seattle:ACM,1999.263-270.

[7]Zhao J,Zheng H,Yang G-H.Distributed coordination in dynamic spectrum allocation networks[A].2005 First IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks[C].Baltimore:IEEE,2005.259-268.

[8]Cabric D,Mishra S M,Willkomm D,et al.A cognitive radio approach for usage of virtual unlicensed spectrum[A].Proc of 14th IST Mobile Wireless Communications Summit[C].Dresden:IEEE,2005.1-4.

[9]Cabric D,Mishra S M,Brodersen R W.Implementation issues in spectrum sensing for cognitive radios[A].Conference Record of the Thirty-eighth Asilomar Conference on Signals,Systems and Computers[C].Monterey:IEEE,2004.772-776.

[10]Chowdhury K R,Akyldiz I F.OFDM-based common control channel design for cognitive radio ad hoc networks[J].IEEE Transactions on Mobile Computing,2011,10(2):228-238.

[11]Bian K,Park J-M,Chen R.Control channel establishment in cognitive radio networks using channel hopping[J].IEEE Journal on Selected Areas in Communications,2011,29(4):689-703.

[12]Theis N C,Thomas R W,DaSilva L A.Rendezvous for cognitive radios[J].IEEE Transactions on Mobile Computing,2011,10(2):216-227.

[13]Lin Z,Liu H,Chu X,et al.Jump-stay based channel-hopping algorithm with guaranteed rendezvous for cognitive radio networks[A].Proceedings of 2011 IEEE INFOCOM[C].Shanghai:IEEE,2011.2444-2452.

[14]Chen T,Zhang H,Maggio G M,et al.CogMesh:a cluster-based cognitive radio network[A].2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks[C].Dublin:IEEE,2007.168-178.

[15]Chen T,Zhang H,Maggio G M,et al.Topology management in CogMesh:a cluster-based cognitive radio mesh network[A].IEEE International Conference on Communications 2007[C].Glasgow:IEEE,2007.6516-6521.

[16]Dai Y,Wu J,Xin C.Virtual backbone construction for cognitive radio networks without common control channel[A].Proceedings of IEEE INFOCOM 2013[C].Turin:IEEE,2013.1456-1464.

[17]Zhao J,Zheng H,Yang G-H.Spectrum sharing through distributed coordination in dynamic spectrum access networks[J].Wireless Communications and Mobile Computing,2007,7(9):1061-1075.

[18]Lazos L,Liu S,Krunz M.Spectrum opportunity-based control channel assignment in cognitive radio networks[A].6th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks 2009[C].New Orleans:IEEE,2009.1-9.

[19]Boykov Y,Kolmogorov V.An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1124-1137.

徐 寧 男，1989年生于湖北十堰，博士生，主要研究方向為移動無線網(wǎng)絡(luò)、認(rèn)知Ad Hoc網(wǎng)絡(luò)、上下文認(rèn)知計算.

E-mail：davidxn@whu.edu.cn

張滬寅(通信作者) 男，1962年生于江蘇蘇州，教授、博士、博士生導(dǎo)師，主要研究方向為網(wǎng)絡(luò)QoS、計算機網(wǎng)絡(luò)、新一代互聯(lián)網(wǎng)體系結(jié)構(gòu).

E-mail：zhy2536@whu.edu.cn

Channel Similarity Based Clustering Algorithm in Cognitive Ad Hoc Network

XU Ning,ZHANG Hu-yin,WANG Jing,XU Fang,WANG Zhi-yong

(SchoolofComputer,WuhanUniversity,Wuhan,Hubei430072,China)

As the traditional clustering algorithm cannot be applied to the cognitive ad hoc network for dynamic channels,a distributed clustering algorithm based on the similarity of channels has been proposed.Firstly the channel similarity between nodes will be calculated and the probability of a node within the cluster will be estimated using an adapted EM algorithm.Then by using minimum cut algorithm in graph theory,the optimal clustering results will be obtained with maximum similarity within a cluster and minimum similarity between clusters.Finally,a coordination mechanism to synchronize the global clustering information has been proposed.Throughout,these processes are evenly distributed,without relying on a common control channel.The simulation results show that the proposed algorithm can change the cluster structure according to the dynamic nature of channels,increase the intra-cluster common channels,and effectively reduce inter-cluster common channels to lower the interference.

cognitive Ad Hoc network;clustering;channel similarity

2015-02-02;

2015-06-26;責(zé)任編輯：李勇鋒

國家自然科學(xué)基金(No.61272454);高等學(xué)校博士學(xué)科點專項科研基金(No.20130141110022)

TN929.5

A

0372-2112 (2016)10-2323-07

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.006