一種改進(jìn)的認(rèn)知無(wú)線網(wǎng)絡(luò)路由算法

趙建立，苑津莎，韓東升

(華北電力大學(xué)，河北保定071003)

無(wú)線通信的迅速發(fā)展使得人們對(duì)無(wú)線頻譜資源的需求量日益增大，無(wú)線頻譜資源的匱乏問(wèn)題顯得越來(lái)越嚴(yán)重。然而，來(lái)自美國(guó)聯(lián)邦通信委員會(huì)(FCC)的一份頻譜占用調(diào)查報(bào)告顯示，稀缺的頻譜資源平均使用率只有15%，大部分授權(quán)頻段經(jīng)常處于空閑狀態(tài)［1－3］。認(rèn)知無(wú)線電(Cognitive Radio，CR)技術(shù)［4－5］的提出使非授權(quán)用戶(Secondary User，SU)能夠感知、識(shí)別及接入當(dāng)前空閑的授權(quán)用戶(Primary User，PU)頻段，從而大幅提高頻譜利用率。

由于傳統(tǒng)的路由算法不能直接應(yīng)用到認(rèn)知無(wú)線電網(wǎng)絡(luò)中［6］。近來(lái)，將CR技術(shù)應(yīng)用在移動(dòng)Ad Hoc中的研究越來(lái)越多［7］。文獻(xiàn)［5］提出一種基于貪婪地理位置、最小延遲的SEARCH路由協(xié)議。當(dāng)路徑中不存在前向避免區(qū)域時(shí)，SEARCH路由選擇算法可以得到端到端延遲最小的最短路徑。但是，文獻(xiàn)［8］中沒(méi)有考慮路由節(jié)點(diǎn)在業(yè)務(wù)量較大的時(shí)候，中間節(jié)點(diǎn)由于超負(fù)荷會(huì)造成隊(duì)列延遲和頻繁的頻譜切換問(wèn)題。文獻(xiàn)［9］提出一種SAMER認(rèn)知路由選擇協(xié)議。SAMER協(xié)議在長(zhǎng)期路由穩(wěn)定和短期接入機(jī)會(huì)之間取得平衡，從而提高網(wǎng)絡(luò)的壽命。文獻(xiàn)［10］給出了Ad Hoc網(wǎng)絡(luò)中CR路由選擇的度量。

本文在現(xiàn)有文獻(xiàn)的基礎(chǔ)上，提出一種基于聯(lián)合地理位置和前向反饋的認(rèn)知路由選擇算法。在考慮最佳位置轉(zhuǎn)發(fā)候選節(jié)點(diǎn)時(shí)，也考慮了節(jié)點(diǎn)的業(yè)務(wù)量;同時(shí)通過(guò)前向反饋，使全局路由為最佳，避免路由進(jìn)入前向避免區(qū)域，給路徑帶來(lái)拓?fù)洳环€(wěn)定和增加延遲的影響［11］。仿真結(jié)果表明，本文提出的路由選擇算法要優(yōu)于文獻(xiàn)［8］中的SEARCH路由方案，同時(shí)減小了端到端的延遲和能量消耗。

1 認(rèn)知路由的挑戰(zhàn)

多跳認(rèn)知Ad Hoc網(wǎng)絡(luò)中的路由選擇，嚴(yán)重影響著網(wǎng)絡(luò)的全局性能，認(rèn)知路由選擇的性能受多種因素的影響。

1.1 頻譜切換導(dǎo)致的延遲

文獻(xiàn)［9］指出，在CR網(wǎng)絡(luò)中，路由從一個(gè)頻段切換到另一個(gè)頻段對(duì)SU數(shù)據(jù)傳輸帶來(lái)極大的影響，造成頻譜切換延遲。頻譜切換延遲計(jì)算公式為

式中:k為常數(shù)，通常取10 ms/10 MHz;M為可用的頻帶數(shù)目。

1.2 隊(duì)列延遲

文獻(xiàn)［10］分析當(dāng)最佳前向轉(zhuǎn)發(fā)路由處于超負(fù)荷狀態(tài)時(shí)，會(huì)對(duì)數(shù)據(jù)包的轉(zhuǎn)發(fā)帶來(lái)嚴(yán)重的隊(duì)列延遲。隊(duì)列延遲的計(jì)算公式為

式中:Pn為數(shù)據(jù)包的大小;Bi為Bandi的帶寬;Numi為對(duì)帶寬Bandi總共的競(jìng)爭(zhēng)用戶數(shù)。

1.3 信道感知與選擇延遲

在中間節(jié)點(diǎn)進(jìn)行頻譜切換，路由就要執(zhí)行相應(yīng)的頻譜感知，選擇候選信道［8］。信道感知與選擇延遲滿足

式中:Tsens為CR信道感知時(shí)間。

2 基于位置和前向反饋的認(rèn)知路由選擇算法

為了提高Ad Hoc網(wǎng)絡(luò)中路由的穩(wěn)定性，同時(shí)降低對(duì)PU的干擾，以及降低端到端的延遲，本文提出一種基于位置和前向反饋的認(rèn)知路由選擇算法。

2.1 位置區(qū)分析

潛在區(qū)域(Potential Region，PR):由于Tx的發(fā)射功率有限，不能直接和Rx建立通信鏈路，那么Tx就必須選擇潛在轉(zhuǎn)發(fā)路由節(jié)點(diǎn)PR。潛在區(qū)域存在于圖1的陰影區(qū)域，其定義為

圖1 最佳轉(zhuǎn)發(fā)區(qū)域

從圖1可以看出，位于潛在區(qū)域中Tx的前向轉(zhuǎn)發(fā)節(jié)點(diǎn)PR不處于PU接受功率范圍之內(nèi)。當(dāng)PU突然出現(xiàn)，也不會(huì)對(duì)前向路由帶來(lái)影響。

最佳轉(zhuǎn)發(fā)區(qū)域(Best Forward Region，BF Region):根據(jù)兩點(diǎn)之間直線最短定理，以及三角形兩邊之和大于第三邊定理可以得到在PR中存在一個(gè)最佳轉(zhuǎn)發(fā)扇形區(qū)域。該區(qū)域以Tx和Rx兩點(diǎn)連線lTx－Rx為角平分線，夾角為2θmax的扇形區(qū)域。圖1中路由節(jié)點(diǎn)a、b、c和d處于最佳轉(zhuǎn)發(fā)區(qū)域中。

最佳轉(zhuǎn)發(fā)路由(Best Forward Router，BFR):將最佳轉(zhuǎn)發(fā)區(qū)域中的M個(gè)候選節(jié)點(diǎn)標(biāo)記為candi_routei，i∈［1，M］。將Tx到candi_routei的方向矢量表示為Vi，Tx到Rx的方向矢量表示為Ui。為了減小轉(zhuǎn)發(fā)路由偏離接收端的角度，最佳轉(zhuǎn)發(fā)路由candi_routei應(yīng)滿足如下優(yōu)化條件

根據(jù)式(5)，在圖1中路由節(jié)點(diǎn)c為Tx的最佳轉(zhuǎn)發(fā)路由BFR。

前向避免區(qū)域(Forward Avoidance Region，F(xiàn)A Region):在路由路徑中，當(dāng)前轉(zhuǎn)發(fā)路由Forward Router(FR)的BFR位于PU頻段使用范圍內(nèi)，或者FR的最佳轉(zhuǎn)發(fā)路由處于超負(fù)荷狀態(tài)，或者位于最佳轉(zhuǎn)發(fā)區(qū)域中的路由節(jié)點(diǎn)不愿意給FR轉(zhuǎn)發(fā)數(shù)據(jù)包，那么此時(shí)FR位于前向避免區(qū)域，如圖2所示。根據(jù)最佳轉(zhuǎn)發(fā)區(qū)域定義可以知道:路由節(jié)點(diǎn)e，f，g處于最佳轉(zhuǎn)發(fā)區(qū)域之內(nèi)，同時(shí)路由f為BFR節(jié)點(diǎn)。各類情況分析如下。

圖2 前向避免區(qū)域

FR選擇f:由于路由f處于PU頻帶使用范圍之內(nèi)，也就是說(shuō)，由FR到路由f的PU頻段不可以用。如果FR選擇f作為前向轉(zhuǎn)發(fā)節(jié)點(diǎn)，那么在f處就必須進(jìn)行頻譜切換，從而造成切換延遲。為此，在最佳轉(zhuǎn)發(fā)區(qū)域中，路由f不是最佳節(jié)點(diǎn)。SEARCH協(xié)議沒(méi)有考慮頻譜切換造成的頻譜切換延遲，僅僅考慮了信道選擇延遲，所以其選擇在f處需進(jìn)行信道切換。

FR選擇e:若此時(shí)路由e處于超負(fù)荷狀態(tài)，選擇e會(huì)造成嚴(yán)重的數(shù)據(jù)包隊(duì)列延遲。為此，在最佳轉(zhuǎn)發(fā)區(qū)域中，路由e也不是最佳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

FR選擇g:若此時(shí)路由g由于自身的能耗限制或者g不愿意給FR轉(zhuǎn)發(fā)數(shù)據(jù)包，所以FR也不能通過(guò)g轉(zhuǎn)發(fā)數(shù)據(jù)。

則FR的最佳轉(zhuǎn)發(fā)區(qū)域中沒(méi)有候選路由。

在這4種情況下，認(rèn)為FR處于前向避免區(qū)域。這4種類型的路由定義為FA Region路由。如圖2所示，F(xiàn)R位于前向避免區(qū)域。

2.2 前向避免區(qū)域中SEARCH路由的缺陷

如果FR位于前向避免區(qū)域，那么在FR處就必須進(jìn)行優(yōu)化。SEARCH路由算法沒(méi)有考慮路由業(yè)務(wù)量的大小對(duì)延遲的影響。如果前向避免區(qū)域中的BFR處于超負(fù)荷狀態(tài)，由于貪婪地理位置準(zhǔn)則可以滿足最短路由路徑，F(xiàn)R依然選擇BFR作為下一跳。但其忽略了隊(duì)列延遲;如果前向避免區(qū)域由PU出現(xiàn)引起，則不選擇BFR進(jìn)行轉(zhuǎn)發(fā)，而是繞過(guò)前向避免區(qū)域，選擇下一跳路由(Next Router，NR)。如圖3所示。

圖3 存在前向避免區(qū)域的SEARCH路由

同時(shí)SEARCH考慮了從信道k切換到k'的切換開(kāi)銷δk。其選擇的最佳NR滿足如下優(yōu)化條件

式中:m'表示切換了信道之后，從NR到Rx的路由跳數(shù);NRk'表示NR使用信道k';Ddisse表示數(shù)據(jù)從FP到達(dá)NR的傳播時(shí)間。如圖3所示，鏈路FR→a→b→c→d，很好地繞過(guò)了前向避免區(qū)域，但是造成極大的切換開(kāi)銷，同時(shí)忽略了10 ms數(shù)量級(jí)的頻譜切換延遲。

從圖3中可以看出，SEARCH對(duì)前向避免區(qū)域采用了繞行方法對(duì)數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，顯然，由Previous－FR(Pre－FR)到a經(jīng)過(guò)了FR，即:Pre－FR→FR→a，從而導(dǎo)致了整體路由的非最優(yōu)選擇。

2.3 基于位置的前向反饋算法

分析圖3可以發(fā)現(xiàn)，出現(xiàn)在FR進(jìn)行信道切換的問(wèn)題，不是由FR造成的，而是Pre－FR下一跳節(jié)點(diǎn)選擇的問(wèn)題。如果，Pre－FR在選擇下一跳時(shí)不是貪婪地選取最佳路由，就不會(huì)造成在下一跳出現(xiàn)這種尷尬的局面。為此，Pre－FR在選擇下一跳路由FR時(shí)，有必要確定FR有沒(méi)有比較好的下一跳路由為其轉(zhuǎn)發(fā)數(shù)據(jù)。為解決這一問(wèn)題，本文采用前向反饋的方法，對(duì)前向避免區(qū)域進(jìn)行優(yōu)化。具體算法策略如下:

1)Pre－FR將所有存在于最佳轉(zhuǎn)發(fā)區(qū)域中非FA Region路由，按照式(5)中的arccos(·)，由小到大進(jìn)行排序，并將排序好的候選節(jié)點(diǎn)全部存放在Pre－FR的FR_node緩存中。

2)如果FR_node為空，則執(zhí)行步驟5)，否則執(zhí)行步驟3)。

3)執(zhí)行循環(huán)。對(duì)FR_node中的所有節(jié)點(diǎn)，依次進(jìn)行下一跳路由分析。假設(shè)當(dāng)前分析節(jié)點(diǎn)為FR_nodei。如果FR_nodei的下一跳中不存在FA Region路由，則FR_nodei可以作為Pre－FR的FR，同時(shí)將可以作為轉(zhuǎn)發(fā)節(jié)點(diǎn)的信息反饋給Pre－FR，退出FR_node循環(huán)，執(zhí)行步驟5);若FR_nodei位于前向避免區(qū)域，對(duì)FR_nodei+1進(jìn)行步驟3)。

4)如果FR_node中的所有節(jié)點(diǎn)均位于前向避免區(qū)域，即沒(méi)有可以執(zhí)行下一跳的路由，那么執(zhí)行步驟5)。

5)在Pre－FR處進(jìn)行頻譜切換?？紤]轉(zhuǎn)發(fā)節(jié)點(diǎn)的隊(duì)列長(zhǎng)度，對(duì)SEARCH路由算法做進(jìn)一步優(yōu)化，選擇下一跳節(jié)點(diǎn)的優(yōu)化算法如下

式中:Dbackoff為退避延遲。

3 性能評(píng)估

3.1 端到端的延遲

認(rèn)知無(wú)線電通信網(wǎng)絡(luò)中對(duì)路由算法的性能分析，需考慮其從端到端的延遲、路徑中總的跳數(shù)以及鏈路中總的能量消耗。對(duì)路徑中總的跳數(shù)可以通過(guò)式(7)進(jìn)行優(yōu)化。下面就端到端的延遲進(jìn)行理論分析。

在分析的時(shí)候考慮5種延遲:頻譜切換延遲、隊(duì)列延遲、退避延遲、信道檢測(cè)和選擇延遲以及傳播延遲。其中頻譜切換延遲、隊(duì)列延遲及信道檢測(cè)和選擇延遲如上文所述。退避延遲的計(jì)算公式如下

式中:pc表示一個(gè)競(jìng)爭(zhēng)節(jié)點(diǎn)經(jīng)歷碰撞的概率;W0表示最小競(jìng)爭(zhēng)窗口大?。?1］。所以，端到端的延遲Ddelay為

3.2 端到端能量消耗

無(wú)線設(shè)備發(fā)送和接收以及信號(hào)放大均需要消耗能量。文獻(xiàn)［15］給出了無(wú)線設(shè)備能量消耗特性，見(jiàn)表1。

表1 無(wú)線設(shè)備能量消耗特性

為了方便，令ETx－elec=ERx－elec=Eelec。若一個(gè)功率覆蓋半徑為d(m)的無(wú)線設(shè)備要傳輸k(bit)的數(shù)據(jù)包，所需消耗的能量模型表示如下

類似地，要接收k(bit)的數(shù)據(jù)包，所需消耗的能量模型為假設(shè)Ad Hoc網(wǎng)絡(luò)中無(wú)線設(shè)備發(fā)送功率相同，信號(hào)所能覆蓋的半徑相同，則端到端的能量消耗為

式中:hops為路徑中總的路由跳數(shù)。

4 性能仿真和分析

4.1 仿真環(huán)境描述

仿真模型如圖4所示，假設(shè)400個(gè)無(wú)線節(jié)點(diǎn)存在于1 000 m×1 000 m的區(qū)域內(nèi)，CR收、發(fā)用戶的傳輸覆蓋半徑為120 m，用黑色的小方框表示Tx和Rx，其中Tx位于(400 m，600 m)處，Rx位于(800 m，200 m)處。網(wǎng)絡(luò)中小圓點(diǎn)表示無(wú)線路由，所有的路由節(jié)點(diǎn)均具有頻譜檢測(cè)功能;PU的覆蓋范圍為200 m，用小方框表示，PU位于(300 m，700 m)處;網(wǎng)絡(luò)中淺色的小點(diǎn)表示該路由已經(jīng)處于業(yè)務(wù)量飽和狀態(tài)，不能再接受其他用戶的轉(zhuǎn)發(fā)請(qǐng)求;而深色的小點(diǎn)表示可以作為轉(zhuǎn)發(fā)節(jié)點(diǎn)的路由。

圖4 存在前向避免區(qū)域，兩種路由協(xié)議性能

4.2 不同條件下兩種算法的路由選擇性能

圖4給出了兩種路由選擇算法的性能比較。其中深色的路徑為本文算法路由路徑，另一條為SEARCH方案的路徑。分析圖4可以看出，SEARCH的第一跳路由為Tx的BFR。但BFR處于前向避免區(qū)域，BFR選擇切換到其他信道的方法進(jìn)行轉(zhuǎn)發(fā)，繞過(guò)了前向避免區(qū)域，仿真與理論分析吻合。其中淺色路徑為所繞路徑。

與SEARCH相比，本文提出算法的路由路徑要短很多。從圖中可以看出，Tx的第一跳路由處于前向避免區(qū)域，通過(guò)反饋，將信息反饋給Tx，Tx從FR_node中選擇次優(yōu)路由進(jìn)行判斷;從而避免了SEARCH因貪婪的最佳路由選擇，造成的路由不穩(wěn)定。

此時(shí)SEARCH總共需要9跳才能將Tx的數(shù)據(jù)包轉(zhuǎn)發(fā)給Rx，而本文提出的算法只需要6跳路由就可以成功遞交數(shù)據(jù)包。當(dāng)路徑中不存在FA Region時(shí)，圖5給出了此種場(chǎng)景下兩種路由協(xié)議性能對(duì)比。在此種場(chǎng)景下，兩種算法選擇的路徑重合在一起，且均是最短路徑。

圖5 不存在前向避免區(qū)域時(shí)兩種路由協(xié)議性能

4.3 兩種路由算法的數(shù)據(jù)傳輸延時(shí)性能分析

假設(shè)pc=0.1，Numi=5，Bi=1MHz，Tsens=50 μs。SEARCH在前向避免區(qū)域處由中心頻道900 MHz切換到中心頻率為915 MHz的信道上。圖6給出了圖4場(chǎng)景下端到端延遲隨數(shù)據(jù)包的大小變化曲線圖。

圖6 端到端延遲比較

兩種算法的端到端延遲均隨著轉(zhuǎn)發(fā)數(shù)據(jù)包的大小變化而變化，且包越長(zhǎng)，端到端延遲越大。從圖6中可以很清楚地看出，本文提出的算法要明顯優(yōu)于SEARCH方案。這表明加入反饋之后，可以很好地在前向避免區(qū)域處進(jìn)行優(yōu)化，減小了路由跳數(shù)，降低了傳播延遲。

4.4 兩種路由算法的節(jié)點(diǎn)能量消耗性能分析

圖7給出了圖4場(chǎng)景下，兩種路由選擇算法造成的端到端設(shè)備能量消耗隨數(shù)據(jù)包大小的變化。從圖7中可以很清楚地看出，當(dāng)路徑存在前向避免區(qū)域時(shí)，本文提出的路由算法可以降低端到端的能量消耗，隨著數(shù)據(jù)包變大，效果越明顯。從而節(jié)約了網(wǎng)絡(luò)的全局能量消耗。

圖7 端到端能量消耗比較

5 結(jié)論

本文提出了一種基于地理位置和前向反饋的認(rèn)知路由選擇算法，以解決認(rèn)知路由算法SEARCH在前向避免區(qū)域頻繁信道切換造成的端到端延遲和路由不穩(wěn)定問(wèn)題。通過(guò)信息反饋，協(xié)調(diào)當(dāng)前路由和下一跳路由，綜合評(píng)估最佳下一跳路由;同時(shí)提出了認(rèn)知網(wǎng)絡(luò)中路由算法的評(píng)估方案。仿真表明，本文提出的路由選擇算法要優(yōu)于SEARCH方案，同時(shí)降低了端到端的延遲和能量消耗。

［1］ FCC.Notice of proposed rule making and order(ET docketno.03－322)［EB/OL］.［2013－08－15］.http://en.wikipedia.org/wiki/Notice_of_proposed_rulemaking.

［2］ SUN H，NALLANATHAN A，WANG C，et al.Wideband spectrum sensing for cognitive radio networks:a survey［J］.IEEEWireless Communications，2013，20(2):74－81.

［3］ WANG J，CHEN J，CABRIC D.Cramer－rao bounds for joint rss/doabased primary－user localization in cognitive radio networks［J］.IEEE Trans.Wireless Communications，2013，12(3):1363－1375.

［4］ XUE D，EKICIE.Cross－layer scheduling for cooperativemulti－h(huán)op cognitive radio networks［J］.IEEE Journal on Selected Areas in Communications，2013，31(3):534－543.

［5］ ZHOU Y，ZHU H，SUN Y，et al.Routing－toward－primary－user attack and belief propagation－based defense in cognitive radio networks［J］.IEEE Trans.Mobile Computing，2013，12(9):1750－1760.

［6］ PARVIN S，F(xiàn)UJIIT.Radio environment aware stable routing scheme for multi－h(huán)op cognitive radio network［J］.IET Networks，2012，1(4):207－216.

［7］ JO M，HAN L，KIM D，etal.Selfish attacks and detection in cognitive radio Ad－Hoc networks［J］.IEEE Network，2013，27(3):46－50.

［8］ CHOWDHURY M.Search:a routing protocol for mobile cognitive radio ad－ hoc networks［J］.Computer Communications，2009，32(18):1983－1997.

［9］ PEFKIANAKIS I，WONG S，LU S.Samer:spectrum awaremesh routing in cognitive radio networks［C］//Proc.IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks(DySPAN'08).Chicago:IEEE Press，2008:1－5.

［10］ CALEFFIM，AKYILDIZ I，PAURA L.Opera:optimal routing metric for cognitive radio ad hoc networks［J］.IEEE Trans.Wireless Communications，2012，11(8):2884－2894.

［11］程賡，李昀照，劉威，等.認(rèn)知無(wú)線電網(wǎng)絡(luò)路由及頻譜分配聯(lián)合策略研究［J］.電子與信息學(xué)報(bào)，2008，30(3):695－698.

［12］ CHENG G，LIY，LIUW，et al.Joint routing and spectrum assignment in cognitive radio networks［J］.Journal of Electronics ＆ Information Technology，2008，30(3):695－698.

［13］ MA X，ZHENG L，LUO Y.Spectrum aware routing formulti－h(huán)op cognitive radio networkswith a single transceiver［C］//Proc.3rd International Conference on Cognitive Radio Oriented Wireless Networks and Communications(CrownCom'08).Singapore:IEEE Press，2008:1－6.

［14］ CHENG G，LIUW，LIY，et al.Joint on－demand routing and spectrum assignment in cognitive radio networks［C］//Proc.IEEE International Conference on Communications(ICC'07).Glasgow:IEEE Press，2007:6499－6503.

［15］ IEEE standard for wireless lan－medium access control and physical layer specification［S］.1999.

［16］ HEINZELMANW，CHANDRAKASAN A，BALAKRISHNAN H.Energyefficient communication protocol forwirelessmicro－sensor networks［C］//Proc.33rd Annual Hawaii International Conference on System Sciences.［S.l.］:IEEE Press，2000:1－10.