基于隨機(jī)圖的CR Ad Hoc網(wǎng)絡(luò)頻譜管理方案＊

周 健，余永紅，孫麗艷

（1.安徽財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，安徽 蚌埠 233041；2.北京科技大學(xué)計(jì)算機(jī)與通信工程學(xué)院，北京 100083；3.北京郵電大學(xué)計(jì)算機(jī)學(xué)院，北京 100083）

1 引言

隨著無線通信業(yè)務(wù)需求的快速增長，可用頻譜資源變得越來越稀缺，雖然鏈路自適應(yīng)、多天線等技術(shù)提高了頻譜使用效率，卻增加了成本和干擾，限制了通信系統(tǒng)的容量和靈活性。認(rèn)知無線電CR（Cognitive Radio）[1]作為一種更智能的頻譜共享技術(shù)能夠依靠人工智能技術(shù)，感知無線通信環(huán)境，根據(jù)學(xué)習(xí)和決策算法實(shí)時(shí)自適應(yīng)地改變系統(tǒng)工作參數(shù)[2]，動(dòng)態(tài)地檢測和有效地利用空閑頻譜，在時(shí)間、頻率以及空間上進(jìn)行多維的頻譜復(fù)用，大大降低頻譜和帶寬限制對無線技術(shù)發(fā)展的束縛。因此，這一技術(shù)被預(yù)言為未來最熱門的無線技術(shù)[3，4]。由于認(rèn)知無線電技術(shù)在頻譜管理上的優(yōu)越性，它也被引入Ad Hoc網(wǎng)絡(luò)，稱為認(rèn)知無線電Ad Hoc網(wǎng)絡(luò)CRAHN（Cognitive Radio Ad Hoc Networks）[5]。然而CRAHN與普通Ad Hoc網(wǎng)絡(luò)一樣沒有基站支持，即沒有頻譜管理中心提供服務(wù)，單個(gè)節(jié)點(diǎn)無法完成全網(wǎng)絡(luò)的頻譜分配任務(wù)，因此如何有效地管理和使用頻譜資源是認(rèn)知無線電Ad Hoc網(wǎng)絡(luò)亟需解決的重要問題[6～8]。

2 CRAHN 頻譜管理

CRAHN 采用動(dòng)態(tài)頻譜策略[9]，現(xiàn)有研究成果基于頻譜使用規(guī)模分為三種形式：（1）單一頻段。文獻(xiàn)[10]提出所有成員使用相同頻段，當(dāng)出現(xiàn)主用戶時(shí)切換到另一個(gè)頻段，該方案管理簡單，但不適合較大規(guī)模的網(wǎng)絡(luò)，且易受到干擾。文獻(xiàn)[11]為了解決頻譜沖突問題，提出使用著色圖為節(jié)點(diǎn)分配固定的某一頻段，使得相鄰節(jié)點(diǎn)間的頻譜不沖突。但是，該方案不適合節(jié)點(diǎn)移動(dòng)的Ad Hoc場景，感知全網(wǎng)絡(luò)頻譜環(huán)境和執(zhí)行著色圖算法需要基站支持。（2）共享多個(gè)頻段。文獻(xiàn)[12]提出網(wǎng)絡(luò)成員具有相同的多個(gè)可以同時(shí)使用的頻段，節(jié)點(diǎn)根據(jù)自身局部頻譜環(huán)境從中選擇一個(gè)頻段作為所有通信鏈路的通信頻段。由于用戶在每個(gè)頻段上的使用機(jī)會(huì)是均等的，因此某些用戶希望占據(jù)較多的頻譜資源，以期望獲得最大的通信優(yōu)勢，所以也會(huì)保留具有通信優(yōu)勢的頻段，進(jìn)而影響頻譜資源使用的公平性[13，14]和較多的頻譜使用沖突[15]。（3）頻譜池方案。文獻(xiàn)[16～19]引入頻譜池概念，用戶加入網(wǎng)絡(luò)前從頻譜池中選擇多個(gè)頻段，通信雙方具有相同的頻段，由于頻段數(shù)量有限，可有效減少頻譜沖突。但是，過少的備選頻段將會(huì)導(dǎo)致鄰居節(jié)點(diǎn)間不存在相同的頻段，導(dǎo)致鏈路建立失敗，增加通信節(jié)點(diǎn)間的跳數(shù)，降低通信效率。目前這三類方案都難以滿足大規(guī)模CRAHN 的快速、靈活和較少?zèng)_突的頻譜管理需求。

3 基于隨機(jī)圖的頻譜管理

本文研究頻譜池模式下，在維持較低的頻譜使用沖突的條件下，節(jié)點(diǎn)至少選擇多少頻段才能保證網(wǎng)絡(luò)通信的有效性。

3.1 網(wǎng)絡(luò)模型

設(shè)網(wǎng)絡(luò)為G，網(wǎng)絡(luò)規(guī)模N＝｜G｜，節(jié)點(diǎn)隨機(jī)移動(dòng)，節(jié)點(diǎn)相遇是偶然的，滿足獨(dú)立分布。設(shè)相遇概率為ρ，節(jié)點(diǎn)度為d＝ρ（N-1）。網(wǎng)絡(luò)具有一個(gè)頻譜池S，包括所有可用頻譜資源，規(guī)模為K＝｜S｜，成員i在加入網(wǎng)絡(luò)前，預(yù)先從頻譜池S 隨機(jī)選擇多個(gè)頻段存儲(chǔ)，這些頻段組成用戶i的備選頻譜集合si（?S），規(guī)模為ki＝｜si｜。網(wǎng)絡(luò)成員i和j 能夠通信必須滿足兩個(gè)條件：（1）節(jié)點(diǎn)間的距離小于節(jié)點(diǎn)的最大傳播距離；（2）通信雙方的備選頻譜集合的交集不為空，即si∩sj≠?。后文實(shí)驗(yàn)中，滿足條件（1）的為場景1，滿足兩個(gè)條件的為場景2。場景2中成員i一跳內(nèi)可通信的節(jié)點(diǎn)數(shù)量ti滿足關(guān)系ti≤d，如果ki＝K，則必然ti＝d。所以，選擇較大的k 值可以減少任意節(jié)點(diǎn)間的傳輸距離。然而選擇較大的k值，也會(huì)引發(fā)頻譜使用的沖突問題。為了保證網(wǎng)絡(luò)中的任意節(jié)點(diǎn)間都具有可達(dá)路徑，網(wǎng)絡(luò)任意兩節(jié)點(diǎn)間至少存在一條路徑l，li為路徑l所包含的節(jié)點(diǎn)，且該路徑上的所有節(jié)點(diǎn)滿足如下公式：

3.2 頻譜沖突

當(dāng)節(jié)點(diǎn)和其多個(gè)鄰居節(jié)點(diǎn)共同占有相同的頻段時(shí)，則節(jié)點(diǎn)通信中將會(huì)發(fā)生沖突。如圖1所示，節(jié)點(diǎn)A、B、E 共同占有頻段fa，則鏈路AB 和AE就有可能發(fā)生通信干擾。同理，節(jié)點(diǎn)A、D、G，F(xiàn) 共同占有頻段fb，則鏈路AD、AG、AF 之間可能發(fā)生通信干擾。相反，鏈路AC 中只可以使用的頻段fc，節(jié)點(diǎn)A 的鄰居節(jié)點(diǎn)都不占有fc，因此鏈路AC不會(huì)受到鄰居節(jié)點(diǎn)的通信干擾。下面給出備選頻譜使用沖突的定義。

定義1 （備選頻譜使用沖突）如果節(jié)點(diǎn)A 和B 是節(jié)點(diǎn)O 的鄰居，則它們的備選頻譜集合滿足條件sA∩sB∩sC≠?，則鏈路AO 和BO 存在備選頻譜使用沖突。備選頻譜使用沖突可能會(huì)導(dǎo)致頻譜使用沖突，但不一定就會(huì)導(dǎo)致頻譜使用沖突。

Figure 1 Spectrum confliction（fis frequency in spectrum pool，whose subscript is the name of node）圖1 頻譜使用沖突（f 為頻段，下標(biāo)為節(jié)點(diǎn)名稱）

考察相鄰節(jié)點(diǎn)間的頻譜使用沖突問題，設(shè)可選的頻譜數(shù)量為k，節(jié)點(diǎn)的度為d，選擇相同頻譜的鄰居節(jié)點(diǎn)數(shù)量為λ，則可能使用相同頻譜的概率為：

其中，k和λ 值越大，則ρc值越小，而d 值越大，則ρc值越大。當(dāng)λ＝1，k＝10000，d＝40時(shí)，ρc ＜0.0001；當(dāng)λ＝2時(shí)，ρc ＜10-8，可見恰當(dāng)?shù)剡x擇k、d 的值就可以減少網(wǎng)絡(luò)中的頻譜使用沖突概率。

考察任意節(jié)點(diǎn)和V 個(gè)節(jié)點(diǎn)間存在相同頻段的概率為：

其中，K 為頻譜池?cái)?shù)量。公式（3）表明隨著V 值增加沖突概率增加，在一跳范圍內(nèi)V＝d，在兩跳范圍內(nèi)V＝d2，跳數(shù)越多則沖突的機(jī)會(huì)越大，因此減少節(jié)點(diǎn)鄰域內(nèi)節(jié)點(diǎn)的數(shù)量可以有效減少頻譜使用沖突。

3.3 備選頻譜集規(guī)模

由上述推導(dǎo)可知，通過減少鄰居節(jié)點(diǎn)數(shù)可減少頻譜沖突的概率，然而維持適當(dāng)鄰居節(jié)點(diǎn)數(shù)是合理的。網(wǎng)絡(luò)通信中的連通性是一個(gè)基本要求，即任意節(jié)點(diǎn)間至少有一條可達(dá)路徑。根據(jù)隨機(jī)圖理論[20，2.]，網(wǎng)絡(luò)如果要保證連通性，則鏈路的連接概率滿足如下公式：

其中，c是一個(gè)常數(shù)，取決于網(wǎng)絡(luò)屬性，通常為1。若節(jié)點(diǎn)度滿足如下公式，則網(wǎng)絡(luò)可保證連通性。

節(jié)點(diǎn)i與節(jié)點(diǎn)j 之間具有相同頻段的概率如下公式所示：

從圖2可以看出，集合si越大，ρ′的值越大，如果從頻譜池中選擇恰當(dāng)規(guī)模的備選頻譜，則節(jié)點(diǎn)間具有相同頻譜這一事件能夠保持較高的概率。

Figure 2 Probability of same frequency when members selects kspare frequency from spectrum pool whose scale is K圖2 節(jié)點(diǎn)從頻譜池K 中選擇k 個(gè)備選頻譜具有相同頻段的概率

如圖2所示，在K＝500，k＝50時(shí)，ρ′≈1，則備選頻譜占所有頻譜資源的比例為10%；當(dāng)頻譜資源的規(guī)模擴(kuò)大，K＝4000，k＝100時(shí)，ρ′≈1，則備選頻譜占所有頻譜資源的比例為2.5%。由此可見，盡管頻譜資源規(guī)模擴(kuò)大8倍，只需要將備選頻譜數(shù)量擴(kuò)大一倍，就可以保證節(jié)點(diǎn)間具有較高的共享頻譜概率?？梢姡诒ＷC相同的共享頻譜的概率條件下，備選頻譜規(guī)模k的增加速度小于頻譜資源規(guī)模K 的擴(kuò)大速度，則根據(jù)上述公式，得到K和k 的關(guān)系（如公式（7）所示），使得公式（2）滿足。

為了提高節(jié)點(diǎn)和鄰居節(jié)點(diǎn)可通信的概率，可將公式（7）修改為公式（8）：

其中，參數(shù)ε∈[1，d]，d 為節(jié)點(diǎn)度，ε越大，則發(fā)生頻譜使用沖突的概率和連接概率都增加；反之，ε越小，則發(fā)生頻譜使用沖突的概率和連接概率都減少。公式（7）和公式（8）證明備選頻譜池的規(guī)?？梢赃M(jìn)一步縮小。

4 性能分析

通過實(shí)驗(yàn)證明方案的可行性。實(shí)驗(yàn)中，頻譜池規(guī)模為10 000，包括1 000 個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)具有60個(gè)鄰居節(jié)點(diǎn)，每次實(shí)驗(yàn)在不同隨機(jī)種子下重復(fù)運(yùn)行10次，取結(jié)果平均值。

4.1 平均路徑長度

圖3是比較兩種場景模式下的網(wǎng)絡(luò)通信的平均傳輸距離，場景scene11和scene12是使用同一隨機(jī)種子生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，scene12符合場景1，即節(jié)點(diǎn)間的距離小于可達(dá)傳輸距離即可以傳輸；scene11符合場景2，即節(jié)點(diǎn)間能夠傳輸?shù)臈l件不僅包含距離小于最大傳輸距離，而且通信雙方的備選頻譜集合交集不能為空。scene12中節(jié)點(diǎn)間的平均傳輸距離與備選頻譜池的規(guī)模無關(guān)，在網(wǎng)絡(luò)規(guī)模固定的情況下，節(jié)點(diǎn)間平均距離為固定的常數(shù)。scene11中節(jié)點(diǎn)間的平均距離與備選頻譜池的規(guī)模相關(guān)，備選頻譜池的規(guī)模越大，則節(jié)點(diǎn)間的平均距離越接近場景1中的節(jié)點(diǎn)間平均距離，說明提高備選頻譜池的規(guī)模有助于提高通信效率。產(chǎn)生這一問題的原因是：場景2中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合是場景1節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的子集，因此與鄰居節(jié)點(diǎn)的邊可能是最短路徑上的邊，具有上述性質(zhì)的鏈路刪除，導(dǎo)致傳輸距離增加。場景scene21 和scene22是使用不同隨機(jī)種子生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，盡管網(wǎng)絡(luò)的平均傳輸距離增加，但是其趨勢與第一次測試時(shí)一致，即增加備選頻譜規(guī)模將減少CRAHN 的平均傳輸距離。

4.2 鄰居的可達(dá)跳數(shù)

Figure 3 Relationship between spectrum scale and transmission distance圖3 備選頻譜池規(guī)模和節(jié)點(diǎn)間傳輸距離關(guān)系

由于節(jié)點(diǎn)與其鄰居通信需要有相同的頻段，因此在CRAHN 中節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的通信可能一跳無法到達(dá)。圖4考察備選頻譜池規(guī)模和鄰居跳數(shù)關(guān)系（從左到右對豎線順序標(biāo)號(hào)，最左邊為線1，最右邊為線13）。在場景1中，由于節(jié)點(diǎn)鄰居距離小于節(jié)點(diǎn)最大傳輸距離，所以節(jié)點(diǎn)和鄰居的通信只需要一跳，如線1所示。而在場景2中，如果節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)沒有相同的頻段，則它們之間的通信需要進(jìn)行轉(zhuǎn)發(fā)。圖4 中，如果備選頻譜池的規(guī)模為100時(shí)，則將近90%的鄰居可以一跳到達(dá)，如線2所示。然而，當(dāng)備選頻譜規(guī)模減少為75時(shí)，一跳內(nèi)的可達(dá)鄰居數(shù)量減少，而兩跳距離的鄰居增多，如線3和線7；進(jìn)一步減少頻譜池的規(guī)模，可以發(fā)現(xiàn)和鄰居的通信主要集中在兩跳或三跳。因此，適當(dāng)減少備選頻譜規(guī)模，使得絕大部分鄰居節(jié)點(diǎn)仍舊維持在1跳可達(dá)的通信范圍內(nèi)，部分節(jié)點(diǎn)維持在2～3跳可達(dá)的通信范圍內(nèi)，極少量節(jié)點(diǎn)的通信距離較高，這樣的結(jié)果使得限制備選頻譜規(guī)模不會(huì)顯著降低網(wǎng)絡(luò)的通信效率。

Figure 4 Relationship between spectrum scale and neighbor hop圖4 備選頻譜池規(guī)模和鄰居跳數(shù)關(guān)系

4.3 備選頻段沖突率

圖5考察了頻段在網(wǎng)絡(luò)中重復(fù)使用的情況（圖中順序標(biāo)號(hào)與圖4類似），如果一條鏈路占據(jù)一個(gè)頻段，統(tǒng)計(jì)發(fā)現(xiàn)，當(dāng)頻譜規(guī)模分別為10 000、5 000和2 500時(shí)，只有將近一半的頻段被使用，如線1、線2和線3所示，其中將近40%僅僅被單個(gè)鏈路獨(dú)自占用，如線4、線5和線6所示，15%的頻段被兩個(gè)或三個(gè)鏈路同時(shí)占用，如線7到線12，少量頻段被使用于多個(gè)鏈路。根據(jù)公式（2），可得到頻譜使用沖突概率為：

Figure 5 Relationship between spectrum scale and repeating frequency圖5 頻譜使用數(shù)量和被重復(fù)占用之間的關(guān)系

可見頻譜使用的沖突概率很小，能夠?yàn)樾录尤牍?jié)點(diǎn)提供充足的備用頻譜資源使用。

5 結(jié)束語

綜合上述，本文給出一種基于隨機(jī)圖的認(rèn)知無線電Ad Hoc網(wǎng)絡(luò)的頻譜管理方案，解決因頻譜分配數(shù)量過多或過少而導(dǎo)致降低通信效率和增加頻譜使用沖突概率等問題。即使網(wǎng)絡(luò)具有移動(dòng)性，且用戶被限定在部分頻段內(nèi)，但用戶仍舊可以維持高概率事件：在鄰居節(jié)點(diǎn)中找到具有相同共享頻段的用戶。同時(shí)，如果鄰居間不能建立直接的通信連接，也可以通過2～3跳范圍內(nèi)的中間節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。該方案保證在不顯著降低網(wǎng)絡(luò)通信效率的前提下，限制用戶的頻譜使用范圍，減少備選頻譜的沖突概率。該方案操作簡單，無需基站支持，只需要知道網(wǎng)絡(luò)規(guī)模、可用頻譜數(shù)量和節(jié)點(diǎn)的連接概率，就可以實(shí)施該方案，適合環(huán)境復(fù)雜、快速部署和不易維護(hù)的應(yīng)用環(huán)境。

[1]Haykin S.Cognitive radio：Brain-empowered wireless communications[J].IEEE Journal on Selected Areas in Communications，2005，2.（2）：201-220.

[2]Haykin S.Cognitive dynamic systems[C]∥Proc of 2007 IEEE International Conference on Acoustics，Speech，and Signal Processing，2007：1-4.

[3]Vuran M C，Akyildiz I F，Won Y L.Next generation／dynamic spectrum access／cognitive radio wireless networks：a survey[J].Computer Networks，2006，50（13）：2127-2159.

[4]Jovicic A，Viswanath P.Cognitive radio：An information-theoretic perspective[J].IEEE Transactions on Information Theory，2009，55（9）：3945-3958.

[5]Akyildiz I F，Lee W-Y，Chowdhury K R.CRAHNs：Cognitive radio ad hoc networks[J].Ad Hoc Networks，2009，7（5）：810-836.

[6]Akyildiz I F，Lee W Y，Vuran M C.A survey on spectrum management in cognitive radio networks[J].IEEE Communications Magazine，2008，46（4）：40-48.

[7]Zhang Xue-ying，Li Cheng.Constructing secured cognitive wireless networks：Experiences and challenges[J].Wireless Communications and Mobile Computing，2010，10（1）：50-69.

[8]Matteo C，F(xiàn)rancesca C，Eylem E.Routing in cognitive radio networks：Challenges and solutions[J].Ad Hoc Networks，2011，9（3）：228-248.

[9]Akyildiz I F，Lo B F，Balakrishnan R.Cooperative spectrum sensing in cognitive radio networks：A survey[J].Physical Communication，2011，4（1）：40-62.

[10]Bian Kai-gui，Park Jung-min，Chen Rui-liang.Control channel establishment in cognitive radio networks using channel hopping[J].IEEE Journal on Selected Areas in Communications，2011，2.（4）：689-703.

[11]Zhou Xian-wei，Lin Lin，Wang Jian-ping.Cross-layer routing design in cognitive radio networks by colored multigraph model[J].Wireless Person Communication，2009，49（1）：123-131.

[12]Chowdhury K R，F(xiàn)elice M D.Search：A routing protocol for mobile cognitive radio ad-hoc networks[J].Computer Communications，2009，32（18）：1983-1997.

[13]Xue Nan，Zhou Xian-wei，Zhou Jian.Self-behavior problems and security solutions in cognitive radio networks[J].Journal of University of Science and Technology Beijing，2009，31（9）：1207-1212.（in Chinese）

[14]Hu Fei，Dong De-cun，Xiao Yang.Attacks and countermeasures in multi-hop cognitive radio networks[J].International Journal of Security and Networks，2009，4（4）：263-271.

[15]Elhajj W，Guizani M.Survey of security issues in cognitive radio networks[J].Journal of Internet Technology，2011，12（2）：181-198.

[16]Abbagnale A，Cuomo F.Connectivity-driven routing for cognitive radio ad-hoc networks[C]∥Proc of the 7th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks，2010：466-474.

[17]Liu Gan，Zhu Guang-xi.Arbitray order extendable markov model for spectrum sharing in cognitive radio Ad Hoc networks[J].Acta Electronica Sinica，2011，39（12）：2785-2790.（in Chinese）

[18]Wei Ji-bo，Wang Shan，Zhao Hai-tao.Cognitive wireless networks：Key techniques and state of the art[J].Journal of Communications，2011，32（11）：147-159.（in Chinese）

[19]Liu Jing，Ren Pin-yi，Xue Shao-li，et al.Primary-user be-havior based joint routing and channal allocation algorithm in cognitive radio network[J].Journal of Communications，2011，32（11）：183-191.（in Chinese）

[20]Gilbert E N.Random graphs[J].The Annals of Mathematical Statistics，1959，30（4）：1141-1144.

[21]Erd?s P，Rényi A.On random graphs[J].Publications Mathematic，1959（6）：290-297.

附中文參考文獻(xiàn)：

[13]薛楠，周賢偉，周健.認(rèn)知無線電網(wǎng)絡(luò)自私行為問題及安全解決方案[J].北京科技大學(xué)學(xué)報(bào)，2009，31（9）：1027-1212.

[17]劉干，朱光喜.可任意階擴(kuò)展的認(rèn)知無線Ad Hoc網(wǎng)絡(luò)頻譜共享模型[J].電子學(xué)報(bào)，2011，39（12）：2785-2790.

[18]魏急波，王杉，趙海濤.認(rèn)知無線網(wǎng)絡(luò)：關(guān)鍵技術(shù)與研究現(xiàn)狀[J].通信學(xué)報(bào)，2011，32（11）：147-159.

[19]劉婧，任品毅，薛少麗.認(rèn)知無線網(wǎng)絡(luò)中基于主用戶行為的聯(lián)合路由和信道分配算法[J].通信學(xué)報(bào)，2011，32（11）：183-191.