混合式認(rèn)知無(wú)線電網(wǎng)絡(luò)路由算法研究

王 嬌，黃玉清，江 虹，周云輝

(西南科技大學(xué)信息工程學(xué)院，四川 綿陽(yáng) 621010)

責(zé)任編輯:許 盈

認(rèn)知無(wú)線電技術(shù)作為緩解無(wú)線頻譜資源緊張局面的有效方法，已成為通信領(lǐng)域的研究熱點(diǎn)［1］。由于認(rèn)知無(wú)線電網(wǎng)絡(luò)(Cognitive Radio Networks，CRN)中機(jī)會(huì)頻譜的動(dòng)態(tài)性，使得傳統(tǒng)路由算法不能完全適用于CRN［2］。目前對(duì)CRN頻譜分配與路由跨層算法的研究主要集中在分布式認(rèn)知無(wú)線網(wǎng)絡(luò)［3－4］，針對(duì)具有基礎(chǔ)設(shè)施的混合式CRN，文獻(xiàn)［5］提出了一種基于著色圖模型的跨層路由設(shè)計(jì)，該設(shè)計(jì)在一定干擾限制條件下選擇具有最短路徑的路由;文獻(xiàn)［6］提出了將跳數(shù)最少、魯棒性強(qiáng)和路由安全等級(jí)高作為路由選擇標(biāo)準(zhǔn);文獻(xiàn)［7］利用馬爾可夫鏈建模，提出了一種基于動(dòng)態(tài)分層圖模型的路由策略與頻譜接口分配策略。

本文采用模型簡(jiǎn)單且適用性較好的著色圖模型分析設(shè)計(jì)混合式CRN網(wǎng)絡(luò)的信道分配和路由算法［8］。針對(duì)文獻(xiàn)［5］沒(méi)有考慮到交叉節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)通信性能影響的不足，提出了信道分配和路徑選擇改進(jìn)算法(ICARS)，通過(guò)定義認(rèn)知用戶在某一時(shí)刻只能用于一條數(shù)據(jù)流數(shù)據(jù)的發(fā)送或接收，從而可以避免多條數(shù)據(jù)流形成交叉節(jié)點(diǎn)在不同信道間來(lái)回切換，避免“耳聾”效應(yīng)的發(fā)生，降低端到端時(shí)延。ICARS算法采用貪婪搜索算法獲得端到端最短路徑路由，使得接入授權(quán)信道的認(rèn)知用戶盡快完成通信，一方面保障了該認(rèn)知用戶端到端傳輸?shù)馁|(zhì)量，另一方面可盡快讓出授權(quán)信道供其他認(rèn)知用戶使用，從而進(jìn)一步提高頻譜利用率，增加網(wǎng)絡(luò)吞吐量。

1 系統(tǒng)模型

本文研究的混合式CRN網(wǎng)絡(luò)模型如圖1所示，由主用戶網(wǎng)絡(luò)和認(rèn)知用戶網(wǎng)絡(luò)組成。其中，主用戶網(wǎng)絡(luò)由具有授權(quán)頻段的M個(gè)主用戶組成，包括Mact個(gè)活躍主用戶(正在進(jìn)行通信的主用戶)和M－Mact非活躍主用戶(處于空閑狀態(tài)的主用戶)。用PU表示主用戶集合，PUact表示活躍主用戶集合，則PUact?PU，fk表示主用戶k的授權(quán)信道，Rinf為主用戶的干擾半徑。

認(rèn)知用戶網(wǎng)絡(luò)由N個(gè)認(rèn)知用戶和1個(gè)認(rèn)知基站組成，用SU表示認(rèn)知用戶集合。認(rèn)知用戶是具有頻譜感知、頻譜切換等認(rèn)知能力的移動(dòng)終端，通過(guò)擇機(jī)的方式接入主用戶的授權(quán)信道，其通信半徑為Rcom，SOPi表示認(rèn)知用戶節(jié)點(diǎn)i可使用的信道集合，也稱機(jī)會(huì)頻譜。認(rèn)知基站可以是類似于蜂窩網(wǎng)的基站或WLAN的接入點(diǎn)，除了具有傳統(tǒng)基站的功能外，還要負(fù)責(zé)檢測(cè)周圍無(wú)線頻譜環(huán)境，獲得認(rèn)知用戶和主用戶的位置信息，分析可用頻譜信息，識(shí)別主用戶行為，決策其覆蓋范圍內(nèi)的端到端路由等功能。

圖1 混合式CRN網(wǎng)絡(luò)模型

2 基于著色圖模型的混合CRN路由算法

為了更加有效地描述算法，文中用rij表示認(rèn)知用戶i與j之間的路徑長(zhǎng)度，定義為兩節(jié)點(diǎn)之間的跳數(shù)，如式(1)所示。

式中:dij表示認(rèn)知用戶之間的距離。式(1)表示:當(dāng)且僅當(dāng)用戶i與j之間的距離小于其通信半徑Rcom，且它們至少共享一條可用信道時(shí)，兩個(gè)認(rèn)知用戶才能彼此直接通信，也稱節(jié)點(diǎn)i和節(jié)點(diǎn)j互為鄰居節(jié)點(diǎn)。

用xij表示認(rèn)知用戶鏈路(i，j)當(dāng)前的狀態(tài)，如果鏈路中的節(jié)點(diǎn)當(dāng)前正在轉(zhuǎn)發(fā)或處理數(shù)據(jù)，則狀態(tài)為忙，否則處于空閑狀態(tài)，可表示為

本文路由算法除了考慮路由長(zhǎng)度外，為避免多條數(shù)據(jù)流形成交叉節(jié)點(diǎn)在不同信道間來(lái)回切換，避免“耳聾”效應(yīng)的發(fā)生，從而降低端到端時(shí)延，文中用wij表示認(rèn)知用戶鏈路(i，j)的權(quán)重，定義為鏈路的跳數(shù)與鏈路狀態(tài)的加權(quán)和，作為路由選擇標(biāo)準(zhǔn)，具體表達(dá)式為

式中:α ∈［0，1］，β∈［0，1］，且α + β =1。

此外，文中用e(f)表示從源節(jié)點(diǎn)S到節(jié)點(diǎn)n的最短路徑上具有相同顏色連續(xù)邊(信道)的條數(shù)。

本文基于著色圖模型，考慮數(shù)據(jù)交叉節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)通信性能的影響，通過(guò)改進(jìn)文獻(xiàn)［5］的CARS算法，為認(rèn)知用戶數(shù)據(jù)流(源節(jié)點(diǎn)S，目的節(jié)點(diǎn)D)決策具有最小干擾的最短路由ICARS算法流程如下:

1)設(shè)路徑從源節(jié)點(diǎn)S開(kāi)始，用path=［S］表示。首先，計(jì)算CRN中各個(gè)認(rèn)知用戶節(jié)點(diǎn)的SOP，即?i∈SU，SOPi=SOPi∪{fk1}∪{fk2}，其中，k1∈PU －PUact，k2∈PUact且di，k2＞Rinf;再根據(jù)各節(jié)點(diǎn)的位置信息和SOP信息，生成網(wǎng)絡(luò)的著色圖 G，并計(jì)算連通矩陣matrix(i，j)=wij，?i，j∈ SU 。

2)在圖G中，針對(duì)路由上的節(jié)點(diǎn)i，i∈path，為其尋找轉(zhuǎn)發(fā)節(jié)點(diǎn)j，需滿足，并為節(jié)點(diǎn)j分配具有最小e(f)值的信道f，且f∈SOPj。如果信道f已被其他數(shù)據(jù)流使用，則必須保證節(jié)點(diǎn)j處于使用信道f的其他節(jié)點(diǎn)的干擾半徑Rinf之外，設(shè)置path=path∪{j}，channel=channel∪{f}，轉(zhuǎn)步驟3);如果這樣的信道不存在，則設(shè)置wij=inf，更新著色圖G，轉(zhuǎn)步驟2)。

3)如果D?path，轉(zhuǎn)步驟2);如果D∈path，則算法結(jié)束。

3 仿真實(shí)驗(yàn)

3.1 網(wǎng)絡(luò)場(chǎng)景與仿真參數(shù)

本文采用如圖2所示的混合式CRN網(wǎng)絡(luò)仿真場(chǎng)景，認(rèn)知用戶和主用戶隨機(jī)分布在場(chǎng)景大小為1 000 m×1 000 m的網(wǎng)絡(luò)中。在圖2中，認(rèn)知用戶數(shù)為40，主用戶數(shù)為8，即授權(quán)信道數(shù)為8，其中主用戶1，3，5，8處于通信狀態(tài)，即為活躍主用戶。

圖2 ICARS算法獲得的仿真結(jié)果圖

假設(shè)在圖2所示的隨機(jī)CRN場(chǎng)景中，存在兩條認(rèn)知用戶的數(shù)據(jù)流，其源節(jié)點(diǎn)分別為節(jié)點(diǎn)2和節(jié)點(diǎn)5，目的節(jié)點(diǎn)分別為節(jié)點(diǎn)7和節(jié)點(diǎn)12，分別利用文獻(xiàn)［5］中的CARS算法和本文ICARS算法決策兩條數(shù)據(jù)流的端到端路由及路徑上的信道，并在圖2上標(biāo)識(shí)。

3.2 仿真結(jié)果與分析

為驗(yàn)證本文所提出的ICARS算法的有效性，利用多信道Manual靜態(tài)路由協(xié)議對(duì)算法進(jìn)行網(wǎng)絡(luò)性能仿真，并將其與CARS算法進(jìn)行比較分析。首先，在NS2中建立如圖2所示網(wǎng)絡(luò)場(chǎng)景TCL腳本，設(shè)置網(wǎng)絡(luò)傳播模型為兩徑模型、MAC協(xié)議為多信道IEEE802.11(RTS/CTS)、數(shù)據(jù)流通信模型為CBR、信道帶寬為2 Mbit/s，干擾半徑為550 m，數(shù)據(jù)分組大小512 byte;再根據(jù)圖2的仿真結(jié)果在TCL腳本中設(shè)置兩條數(shù)據(jù)流，即節(jié)點(diǎn)5至節(jié)點(diǎn)12和節(jié)點(diǎn)2至節(jié)點(diǎn)7，以及數(shù)據(jù)流的端到端路由與信道。為了保證認(rèn)知用戶之間的通信半徑為250 m，認(rèn)知用戶節(jié)點(diǎn)采用統(tǒng)一功率0.281 838 15 mW，且數(shù)據(jù)流節(jié)點(diǎn)5至節(jié)點(diǎn)12的數(shù)據(jù)開(kāi)始傳輸時(shí)間為10 s，而數(shù)據(jù)流節(jié)點(diǎn)2至節(jié)點(diǎn)7開(kāi)始進(jìn)行數(shù)據(jù)傳輸?shù)臅r(shí)間為20 s，仿真時(shí)間為100 s。通過(guò)分析Trace文件獲得吞吐量、丟包率和端到端時(shí)延網(wǎng)絡(luò)性能仿真結(jié)果。

圖3為利用CARS算法與ICARS算法獲得的網(wǎng)絡(luò)累積吞吐量。從圖3可以看出，兩種算法隨著仿真時(shí)間的增加，獲得的網(wǎng)絡(luò)累積吞吐量也隨之增加，但增加的程度卻不同。ICARS算法獲得的網(wǎng)絡(luò)累積吞吐量增加程度略高于CARS算法。

圖3 不同算法獲得的網(wǎng)絡(luò)累積吞吐量

圖4統(tǒng)計(jì)了兩種算法隨著數(shù)據(jù)流增加獲得網(wǎng)絡(luò)累積吞吐量的變化情況。從圖4可以看出，隨著數(shù)據(jù)流的增加，ICARS算法獲得的網(wǎng)絡(luò)累積吞吐量增加程度明顯高于CARS算法。可見(jiàn)，ICARS算法可以緩解由于數(shù)據(jù)流增加造成的網(wǎng)絡(luò)擁塞狀況。

圖4 不同算法隨數(shù)據(jù)流變化獲得的網(wǎng)絡(luò)累積吞吐量

上述算法網(wǎng)絡(luò)性能仿真都是在如圖2所示的場(chǎng)景下完成的，其中活躍主用戶數(shù)固定，為了進(jìn)一步驗(yàn)證本文算法的性能，在網(wǎng)絡(luò)場(chǎng)景其他參數(shù)相同的情況下，圖5給出了兩種算法在不同活躍主用戶數(shù)下獲得的網(wǎng)絡(luò)累積吞吐量。

圖5 算法隨著活躍主用戶變化獲得的網(wǎng)絡(luò)累積吞吐量

從圖5中可以看出，隨著活躍主用戶數(shù)的增加，CARS算法與ICARS算法獲得的網(wǎng)絡(luò)平均吞吐量都隨之降低，這是因?yàn)殡S著活躍主用戶數(shù)的增加，認(rèn)知用戶可用信道數(shù)量隨之減少，從而限制了網(wǎng)絡(luò)吞吐量。然而，ICARS算法獲得的累積吞吐量降低程度小于CARS算法。

此外，本文還利用ICARS和CARS算法對(duì)圖2所示網(wǎng)絡(luò)場(chǎng)景的丟包率和端到端時(shí)延進(jìn)行了仿真比較，這里的端到端平均時(shí)延，除了傳輸時(shí)延、排隊(duì)時(shí)延、退避時(shí)延外，還包括信道切換時(shí)延，平均端到端時(shí)延仿真結(jié)果如圖6所示。結(jié)果顯示兩者獲得的網(wǎng)絡(luò)丟包率基本相同，而ICARS算法獲得的端到端平均時(shí)延小于CARS算法，這是由于ICARS算法在CARS算法的基礎(chǔ)上考慮了交叉節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)通信的影響，從而避免不同數(shù)據(jù)流形成交叉節(jié)點(diǎn)，盡量縮短數(shù)據(jù)分組由于交叉節(jié)點(diǎn)造成的排隊(duì)時(shí)延與信道切換時(shí)延，從而驗(yàn)證了該算法具有較高的通信性能。

圖6 不同算法獲得的網(wǎng)絡(luò)端到端平均時(shí)延

4 結(jié)語(yǔ)

本文基于著色圖模型提出了一種信道分配與路由選擇改進(jìn)算法。該算法以著色圖模型為路由分析模型，利用貪婪搜索算法為端到端通信選擇具有最小鏈路狀態(tài)和跳數(shù)加權(quán)和的最短路徑以及路徑上具有最小累積干擾的信道，從而避免了交叉節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)通信性能的影響。仿真結(jié)果表明，在相同仿真場(chǎng)景下，本文算法與已有算法進(jìn)行比較，可以提高網(wǎng)絡(luò)累積吞吐量，還可以降低網(wǎng)絡(luò)端到端通信的平均時(shí)延。

［1］JOSEPH M.Cognitive radio an integrated agent architecture for software defined radio［D］.Sweden:Royal Institute of Technology(KTH)，2000.

［2］CHOWDHURY K R，F(xiàn)ELICE M D.Search:a routing protocol for mobile cognitive radio Ad－h(huán)oc networks［J］.Computer Communications，2009，32(18):1983－1997.

［3］施圣，徐昌彪.基于認(rèn)知超寬帶的頻譜共享技術(shù)研究［J］，電視技術(shù)，2011，35(9):75－78.

［4］WANG Jiao，HUANG Yuqing.A cross－layer design of channel assignment and routing in cognitive radio networks［C］//Proc.3rd IEEE International Conference on Computer Science and Information Technology.［S.l.］:IEEE Press，2010:542－547.

［5］ZHOU X，LIN L，WANG J，et al.Cross－layer routing design in cognitive radio networks by colored multigraph model［J］.Wireless Personal Communications，2009，49(1):123－131.

［6］薛楠，周賢偉，林琳，等.性能優(yōu)化的認(rèn)知無(wú)線電網(wǎng)絡(luò)安全路由選擇算法［J］.系統(tǒng)工程與電子技術(shù)，2009，31(1):2756－2760.

［7］李洋，董育寧，趙海濤.認(rèn)知Mesh網(wǎng)絡(luò)的動(dòng)態(tài)分層圖路由模型及路由策略［J］.電子與信息學(xué)報(bào)，2009，31(8):1975－1979.

［8］KONDAREDDY Y R.A graph based routing algorithm for multi－h(huán)op cognitive radio networks［C］//Proc.WICON.Maui，Hawaii，USA:［s.n.］，2008:17－19.