楊懷德, 陳俞強, 駱劍鋒

(東莞職業(yè)技術(shù)學(xué)院 計算機工程系,廣東 東莞 523808)

?

基于鏈路可用時間的認知無線網(wǎng)絡(luò)路由算法

楊懷德, 陳俞強, 駱劍鋒

(東莞職業(yè)技術(shù)學(xué)院 計算機工程系,廣東 東莞 523808)

文章針對認知無線網(wǎng)絡(luò)路由性能易受認知節(jié)點移動、主用戶干擾、節(jié)點剩余能量影響的問題,提出一種基于鏈路可用時間的路由算法。該算法對節(jié)點間的鏈路可用時間進行預(yù)測,自適應(yīng)地選取重路由操作少、可用時間長的路徑進行通信。仿真實驗表明,該算法能簡化網(wǎng)絡(luò)的拓撲,提高認知無線網(wǎng)絡(luò)的吞吐量,降低網(wǎng)絡(luò)的傳輸時延。

認知無線網(wǎng)絡(luò);鏈路可用時間;預(yù)測;剩余能量;路由算法

0 引 言

認知無線電技術(shù)是為解決無線頻譜資源日益匱乏的問題而提出的一種新型無線網(wǎng)絡(luò),其核心思想是允許認知用戶動態(tài)擇機地使用已分配給主用戶而主用戶當(dāng)前并未使用的頻段,使得頻譜資源的利用率得到了極大的提升,從而解決了無線網(wǎng)絡(luò)頻譜資源不夠用的問題[1-3]。然而,認知無線電技術(shù)對無線網(wǎng)絡(luò)的性能特別是路由性能也有著巨大的影響，與傳統(tǒng)的無線網(wǎng)絡(luò)相比,認知無線網(wǎng)絡(luò)的路由不僅需要考慮節(jié)點的移動性和節(jié)點剩余能量的影響,還需要考慮來自主用戶的干擾。因此,傳統(tǒng)的無線自組網(wǎng)的路由算法并不適用于頻譜動態(tài)變化的認知無線網(wǎng)絡(luò)。為此,國內(nèi)外很多學(xué)者都展開了對認知無線網(wǎng)絡(luò)的路由算法的研究,并且已經(jīng)取得了許多研究成果。文獻[4]提出了一種基于連通性的路由算法,在選取路徑時淘汰效率低的、不穩(wěn)定的瓶頸鏈路,但沒給出具體的算法實現(xiàn);文獻[5]針對主用戶的干擾問題,提出了一種多路徑的路由算法,該算法通過引入路由接近度的概念,在路徑選取時選取接近度低的節(jié)點作為下一跳,雖然降低了主用戶的干擾對于路由性能的影響,但是增大了網(wǎng)絡(luò)傳輸時延、增加了網(wǎng)絡(luò)的能耗;文獻[6]針對前向避免區(qū)域頻繁信道切換造成的路由不穩(wěn)定問題提出了一種基于地理位置和前向反饋的認知路由算法,該算法解決了SEARCH路由算法的不穩(wěn)定問題,降低了網(wǎng)絡(luò)的能耗和端到端的時延;文獻[7]提出了一種基于位置信息的協(xié)作路由算法,該算法首先計算鏈路的能耗代價,然后基于節(jié)點的位置信息選擇合適的中繼節(jié)點建立協(xié)作路由,在理想的條件下能延長網(wǎng)絡(luò)的生命周期。

上述文獻雖然考慮了認知無線網(wǎng)絡(luò)的頻譜動態(tài)性和主用戶的干擾,卻沒有考慮節(jié)點的剩余能量對于路由性能的影響。本文綜合考慮節(jié)點移動性、主用戶的干擾和節(jié)點剩余能量對于鏈路可用時間的影響,沿用無線自組網(wǎng)按需平面距離向量路由協(xié)議(ad-hoc on-demand distance vector routing,AODV)基本流程,提出了一種基于鏈路可用時間的認知無線網(wǎng)絡(luò)路由算法,并給出了算法的具體實現(xiàn)。

1 系統(tǒng)模型及鏈路可用時間計算方法

1.1 系統(tǒng)網(wǎng)絡(luò)模型

隨機分布在二維區(qū)域的1個主用戶PU和5個認知用戶CU共存的通信網(wǎng)絡(luò)如圖1所示,PU的干擾半徑為R,CU的信號覆蓋半徑為r。每個節(jié)點都采用全向天線通信模式,并且都配置定位模塊,可以獲得自己當(dāng)前時刻的坐標、運動速度和運動方向。節(jié)點的移動軌跡由目前廣泛使用的隨機實體移動模型產(chǎn)生[8],由于該模型能保持平穩(wěn)速度分布和均勻的節(jié)點分布,便于實現(xiàn)和進行理論上的研究。

由于關(guān)注的是路由和鏈路,本文假定認知無線網(wǎng)絡(luò)鏈路可用時間僅由節(jié)點的移動性、主用戶干擾和節(jié)點的剩余能量決定,信號衰落等其他因素引發(fā)的問題可由低層的技術(shù)來處理。

圖1 系統(tǒng)網(wǎng)絡(luò)模型

為了說明認知無線網(wǎng)絡(luò)的路由性能和鏈路可用時間的關(guān)系,下面將通過一個具體的情境來進行描述。假定圖1中通信的源節(jié)點為CU1,目的節(jié)點為CU5，CU2和CU3都在進行遠離PU的運動,而CU4正向PU移動;CU2的剩余能量為5%,CU3的剩余能量為60%。

(1) 如果采用傳統(tǒng)的路由算法按照最短路徑準則,會選取CU4作為下一跳。然而在認知無線網(wǎng)絡(luò)中,當(dāng)CU4運動到足夠接近PU的區(qū)域時,CU1與CU4之間的鏈路會因為受PU的干擾而變得不可用,需要重新發(fā)起路由請求以尋找其他可用路由。如果在之前的路由發(fā)現(xiàn)階段選擇正遠離PU的CU2或者CU3作為下一跳,上述因PU干擾而引起的路由失效的現(xiàn)象就不會發(fā)生。

(2) 進一步,假定選取的下一跳為距離更近的CU2,由于CU2的剩余能量即將耗盡,可能在通信階段CU2會因為能量耗盡導(dǎo)致鏈路不可用,進行影響網(wǎng)絡(luò)的能耗和吞吐量;而如果選取能量更充足的CU3作為下一跳,那么上述因節(jié)點能量耗盡而引起的路由失效的現(xiàn)象也不會發(fā)生。

因此,認知無線網(wǎng)絡(luò)的鏈路可用時間對路由性能起著重要的作用,而鏈路可用時間由節(jié)點的移動性、主用戶的干擾和節(jié)點剩余能量決定。

1.2 鏈路可用時間計算方法

在不考慮節(jié)點剩余能量的前提下,將時間劃分出多個隨機時間片,認知節(jié)點在每個隨機的時間片內(nèi)以概率Pt保持速度不變運動[9],為了方便計算,先假定Pt=1,則可得:

d2=at2+βt+γ

(1)

其中,d為兩節(jié)點間的距離;γ、β、γ為常量；t為時間間隔。常量γ、β、γ可以通過3個時間點進行(t0,d0)、(t1,d1)、(t2,d2)測量計算求解[10]，即

(2)

(1) 在只考慮節(jié)點移動因素的情況下,只要兩節(jié)點間的距離滿足(3)式,則認為鏈路可用。

d≤r

(3)

綜合(1)式和(3)式即可得到在節(jié)點保持速度不變的前提下,兩認知節(jié)點保持在對方信號覆蓋區(qū)域的時間TCC為：

(4)

(2) 在只考慮主用戶干擾的情況下,假定節(jié)點初始位置位于主用戶干擾區(qū)域之外,節(jié)點間的距離滿足(5)式,則認為鏈路可用。

d≤R

(5)

綜合(1)式和(5)式即可得到在節(jié)點保持速度不變的前提下,認知節(jié)點保持在主用戶干擾區(qū)域之外的時間TCP為：

(6)

在實際的網(wǎng)絡(luò)環(huán)境中,Pt的值是一個隨機變化的值,因此,在只考慮節(jié)點的移動性和主用戶干擾下的鏈路可用時間TM-I的值如下:

TM-I=min{PtTCC,PtTCP}

(7)

Pt的值采用文獻[11]中給出了鏈路可用下的概率估算(6)式的計算方法,進而可以得出只考慮節(jié)點的移動性和主用戶的干擾下的鏈路可用時間TM-I為：

(8)

其中,τ-1為平均時間間隔;θ、ε為待定參量,可以通過線下測量獲取。

1.3 基于剩余能量的鏈路可用時間計算方法

在能量受限的認知無線網(wǎng)絡(luò)中,鏈路的生存期不僅需要考慮節(jié)點的移動性和授權(quán)用戶的干擾,還應(yīng)該考慮通信節(jié)點剩余能量狀況。當(dāng)通信對象或者中繼節(jié)點剩余能量即將耗盡時,即便對方仍處于發(fā)送方的信號覆蓋區(qū)域,并且沒有受到授權(quán)用戶的干擾,雙方通信的鏈路都隨時可能變得不可用。

在只考慮通信雙方剩余能量的條件下,節(jié)點間的鏈路維持時間由節(jié)點的剩余能量和功率決定,令TE1、TE2分別為節(jié)點CU1、CU2的能量維持時間,則在只考慮能量維持時間的情形下,兩節(jié)點間鏈路可用時間的計算公式如下：

TE=min{TE1,TE2}

(9)

其中,TE1的值為:

(10)

其中,E1為節(jié)點CU1的剩余能量,其值可以從相關(guān)硬件寄存器中獲取;P1為CU1的傳輸功率,其值可由文獻[12]中(12)式獲取。

TE2的計算方法與TE1的計算方法一致。

綜上所述,CU1與CU2間鏈路可用時間Tavl的計算公式為：

Tavl=min{TM-I,TE}

(11)

2 基于鏈路可用時間的路由算法

基于上述分析,在設(shè)計認知無線網(wǎng)絡(luò)路由算法時綜合考慮主用戶干擾、節(jié)點的移動性和節(jié)點剩余能量,設(shè)計一種基于鏈路可用時間的AODV(link available time AODV，LAT-AODV)。

2.1 路由發(fā)現(xiàn)

兩認知節(jié)點通信的第1階段就是路由發(fā)現(xiàn),檢查路由表中是否有能夠達到目的節(jié)點的路由,若沒有則構(gòu)造路由請求報文RREQ并通過控制信道廣播出去,RREQ中除了包含標準AODV需要的信息外,還需要添加自身的可用頻譜集合、剩余能量信息、路徑可用時間[13-14],如圖2所示。

012345678901234567890123456789012345678901類型JRGU保留字段跳數(shù)目的IP目的SN源IP源SN可用頻譜剩余能量路徑可用時間

圖2 修改后的RREQ報文格式

中繼節(jié)點收到該請求報文后的處理過程需要在AODV協(xié)議的基礎(chǔ)上進行修改,其具體處理步驟如圖3所示。

圖3 RREQ報文處理流程

通過(11)式計算出與上一節(jié)點之間的鏈路可用時間并更新RREQ報文的Path available time 字段,然后還需要檢查自身的頻譜是否與上一節(jié)點存在頻譜交集,沒有則丟棄。最后更新路由表,建立去往源節(jié)點的反向路由,轉(zhuǎn)發(fā)RREQ報文。

2.2 路由應(yīng)答

當(dāng)RREQ報文經(jīng)過轉(zhuǎn)發(fā)過程最終到達目的節(jié)點后,目的節(jié)點利用路由應(yīng)答功能來進行如下相應(yīng)處理。

(1) 啟動接收定時器,只接收規(guī)定時間內(nèi)到達的后續(xù)RREQ報文。

(2) 定時到期后,對有效時間到達的RREQ進行分析,選取跳數(shù)少、路徑可用時間長的路徑建立路由。

(3) 按照之前建立的反向路徑發(fā)送路由響應(yīng)報文。

2.3 路由維護

認知無線網(wǎng)絡(luò)的路由會因為節(jié)點的移動、主用戶的干擾和節(jié)點本身能量耗盡而導(dǎo)致路由不可用,進而影響網(wǎng)絡(luò)的性能。因此,需要認知無線網(wǎng)絡(luò)的路由需要有認知的功能,能前瞻性地感知路徑的可用性,在路徑失效前作出相應(yīng)的措施。在LAT-AODV中,路由維護是依靠節(jié)點間鏈路可用時間來決定是否提前啟動路由修復(fù)功能來實現(xiàn)。如果中間節(jié)點監(jiān)測到其與下一跳節(jié)點的鏈路可用時間小于鏈路危險時間Th,那么節(jié)點就立即構(gòu)造RREQ報文來尋找新的可用路徑,以免影響正常的數(shù)據(jù)傳輸。

3 仿真分析

使用Matlab進行仿真實驗,仿真場景如下:在800×800 m2的區(qū)域內(nèi)隨機部署50個CU節(jié)點和一個PU節(jié)點,CU節(jié)點的最大通信距離為200 m,PU的干擾范圍R=120 m。節(jié)點的運動速度均勻分布在[0,25]m/s,節(jié)點的運動方向均勻分布在[0,2π],Th取值為2 s,節(jié)點的剩余能量在區(qū)間[0,50]J上隨機分布。

從拓撲的結(jié)構(gòu)、網(wǎng)絡(luò)吞吐量和端到端時延3個方面進行實驗仿真,仿真結(jié)果分別如圖4～圖6所示。

圖4中的星號表示主用戶節(jié)點,其他均為認知用戶節(jié)點,圓型節(jié)點代表的是剩余能量不足的認知用戶節(jié)點。

從圖4可以看出,LAT-AODV算法能感知到PU節(jié)點的存在,并主動斷開PU附近節(jié)點間的鏈路,而原始拓撲則無法感知PU節(jié)點的存在。此外，LAT-AODV算法在構(gòu)建鏈路階段前瞻性地斷開剩余能量較低的節(jié)點間的鏈路，降低節(jié)點的度，從而簡化網(wǎng)絡(luò)的拓撲。

圖4 不同算法生成的拓撲比較圖

圖5 端到端時延對比實驗圖

從圖5中可以看出,LAT-AODV路由相對于AODV路由和SEARCH路由算法具有更短的傳輸時延。

圖6 網(wǎng)絡(luò)吞吐量對比實驗圖

從圖6中可以看出，改進后的LAT-AODV協(xié)議相對于AODV路由和SEARCH路由有著更高的吞吐量,這是由于LAT-AODV協(xié)議在路由建立過程中充分考慮了路徑的可用時間,在路由維護過程中對可能斷開的路徑能進行提前修復(fù),使得路由更穩(wěn)定和高效。

此外,從圖5、圖6還可以看出,節(jié)點運動速度越快,2種路由協(xié)議的傳輸時延都明顯增大,而吞吐量都顯著下降,這是由于節(jié)點運動速度越快,網(wǎng)絡(luò)拓撲變化更頻繁,從而導(dǎo)致路由性能的明顯下降。

4 結(jié) 論

本文針對認知無線網(wǎng)絡(luò)的路由優(yōu)化問題,綜合考慮節(jié)點的移動、主用戶的干擾和節(jié)點剩余能量的影響,在AODV路由協(xié)議基礎(chǔ)上提出了一種新的路由算法。仿真實驗表明,新的路由算法能前瞻性地預(yù)測路由可用時間,動態(tài)地自適應(yīng)變化的環(huán)境,簡化了網(wǎng)絡(luò)的拓撲,提升了網(wǎng)絡(luò)的吞吐量,降低了網(wǎng)絡(luò)的傳輸時延,從而改善了認知無線網(wǎng)絡(luò)的性能。

[1] 唐龍,伍爵博.一種新型的認知無線電網(wǎng)絡(luò)架構(gòu)[J].計算機科學(xué),2011，38(10A):326-330.

[2] 劉龍飛.認知無線電頻譜感知的智能算法研究[D].北京：北京郵電大學(xué),2015.

[3] 劉洋.認知無線網(wǎng)絡(luò)中頻譜感知關(guān)鍵技術(shù)的研究[D].南京: 南京郵電大學(xué),2013.

[4] ABBAGNALE A,CUOMO F.Connectivity-driven routing for cognitive radio ad-hoc networks[C]//Proceedings of the 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON).[S.l.:S.n.]，2010:1-9.

[5] BELTAGY I,YOUSSEF M,EL-DERINI M.A new routing metric and protocol for multipath routing in cognitive networks[C]//Wireless Communications and Networking Conference (WCNC),2011 IEEE.[S.l.]:IEEE,2011:974-979.

[6] 趙建立,苑津莎,韓東升.一種改進的認知無線網(wǎng)絡(luò)路由算法[J].電視技術(shù),2014,38(7):140-144.

[7] 周雷,蘇紅,唐昊,等.基于位置信息的無線網(wǎng)絡(luò)協(xié)作路由算法[J].電子測量與儀器學(xué)報,2015(5):708-716.

[8] 林晉福,柏鵬,林志國,等.基于鏈路保持時間的認知無線網(wǎng)絡(luò)拓撲算法[J].系統(tǒng)工程與電子技術(shù),2014(4):746-751.

[9] 官權(quán)升.移動自組織網(wǎng)絡(luò)的拓撲控制及網(wǎng)絡(luò)性能研究[D].廣州:華南理工大學(xué),2011.

[10] JIANG S,HE D,RAO J.A prediction-based link availability estimation for routing metrics in MANETs[J].IEEE/ACM Transactions on Networking,2006,13(6):1302-1312.

[11] 許炳昆,李艷萍.移動Ad Hoc中基于位置輔助的鏈路穩(wěn)定性預(yù)測算法[J].計算機測量與控制,2015,23(2):500-503.

[12] 陳軍,肖明波.基于非合作博弈的改進型認知無線電功控算法[J].計算機工程與應(yīng)用,2014(18):220-225.

[13] 周膠,田杰,戴晨鋮,等.戰(zhàn)術(shù)MANET中基于鏈路可用時間的AODV路由協(xié)議研究[J].計算機工程與科學(xué),2013,35(12):96-101.

[14] 韓志杰,黃劉生,王汝傳,等.一種基于位置和拓撲控制的無線傳感器網(wǎng)絡(luò)路由算法[J].計算機研究與發(fā)展,2010,47(增刊2):128-132.

(責(zé)任編輯 張 镅)

Routing algorithm based on link available time for cognitive radio network

YANG Huaide, CHEN Yuqiang, LUO Jianfeng

(Dept. of Computer Engineering, Dongguan Polytechnic, Dongguan 523808, China)

A link available time based routing algorithm is proposed to improve the performance of routing for cognitive radio networks, whose performance is affected by node mobility, interference from primary users, residual energy of secondary users. The proposed algorithm first forecasts the link available time, and then adaptively selects the routes with less rerouting operations and longer available time. Simulation results show that the proposed algorithm can simplify the network topology, improve the throughput and reduce the transmission delay in cognitive radio networks.

cognitive radio network; link available time; prediction; residual energy; routing algorithm

2016-07-20；

2016-09-22

廣東省科技計劃資助項目(2014A010103002);廣東省優(yōu)秀青年教師人才培養(yǎng)計劃資助項目(2015S02)和東莞職業(yè)技術(shù)學(xué)院科研資助項目(2016A08;政201712)

楊懷德(1983-),男,湖北黃岡人,東莞職業(yè)技術(shù)學(xué)院工程師; 陳俞強(1980-),男,廣東茂名人,博士,東莞職業(yè)技術(shù)學(xué)院教授.

10.3969/j.issn.1003-5060.2017.07.010

TP393

A

1003-5060(2017)07-0912-05