認知無線ad hoc網的多尺度跨層路由協議

曹　靜， 武君勝， 楊文超， 王碩晨

(1. 西北工業大學 計算機學院， 陜西 西安 710072;2. 西北工業大學 軟件與微電子學院，陜西 西安 710072)

隨著各種新型無線網絡(無線傳感網、軟件定義網，普適網絡等)的迅速普及，近年來，無線通信的業務量劇增，未來的無線網絡將呈現出高速化、寬帶化、異構化、泛在化等趨勢．認知無線網絡(Cognitive Radio Networks，CRNs)作為5G網絡的核心技術之一，是提高頻譜利用率，解決當前存在的頻譜匱乏、帶寬受限、適應能力不足等問題的有效途徑．CRNs具有認知和自適應特性，各個網絡節點都能夠感知當前的網絡環境，并根據感知結果進行學習和決策，自適應地調整傳輸參數，通過學習推理來改進網絡的端到端性能．認知無線自組網絡(Cognitive Radio Ad Hoc Networks，CRAHNs)是由一組具有認知決策的節點以多跳自治的方式組成的智能網絡，能夠為用戶動態接入物聯網提供基礎通信平臺[1-2]．

在認知環境下，路由設計問題較之傳統的無線自組網更復雜，不僅包括認知用戶(Secondary User，SU)的移動性造成的網絡拓撲動態變化、鏈路不穩定等問題，還包括由主用戶(Primary User，PU)行為的不確定性帶來的頻譜機會(Spectrum OPportunity，SOP)時變問題[3]．近年來，有很多學者針對CRAHNs的路由優化問題進行研究，并提出多種解決方案: 文獻[4]提出一種跨層路由策略，該策略能夠計算出從任一源節點到目的節點的鏈路時延和路徑時延，結合Dijkstra算法可以通過求解最短路徑問題來獲得最佳選路方案．文獻[5]從潛在博弈的角度出發，為多跳CRNs提出二維的信道-路由交換算法．該算法從頻域和空間域兩個角度進行資源管理，在不完全信息博弈下能夠計算出貝葉斯納什均衡點，從而獲得最小資源開銷的方案．文獻[6]對按需距離矢量路由協議(Ad hoc On-demand Distance Vector routing，AODV)協議做了認知性的擴展，提出一種具有服務質量(Quality of Service，QoS)保障的基于認知的AODV協議(Cognitive-based AODV, CAODV); 該協議為CRAHNs中的認知用戶提供了多信道的接入方案，并在一定程度上增加了端到端吞吐量，然而缺乏對信道切換是否會增加時延的分析．在目前的研究中，大部分學者關注于通過有效的資源管理機制來提高頻譜利用率、緩解頻譜擁塞和優化端到端性能．這些方法在一定程度上實現了資源優化配置并提高了路由效率和穩定性，然而隨著移動網絡的發展，多種無線異構業務將共存和相互融合，因此需要在認知路由設計時考慮業務特征和路由尺度的選擇．

綜上所述，筆者提出一種多尺度跨層路由協議(Multi-Metric cognitive Cross-layer AODV，MM-CAODV)．結合物理層的信道參數和功率分配，以及介質訪問控制(Media Access Control，MAC) 層的頻譜信息來制定路由策略，并根據業務類型和QoS需求來為認知用戶選擇適當的路由尺度權重．結合頻譜可用性來避免對PU的業務流造成干擾，并通過頻譜——路由聯合分配來增加吞吐量、改善鏈路的穩定性和減少端到端時延．由于目前大部分業務(尤其是移動多媒體)具有較高的QoS要求，如高速率、時延敏感、高數據投遞率等，針對業務流的網絡性能進行分析，通過時延、吞吐量、數據投遞率等QoS參數對MM-CAODV協議做仿真實驗，從而獲取路由策略的評價指標．

1　網絡模型

文中考慮的認知Ad hoc網絡由N個認知用戶SU、M個可用信道組成，SU之間以多跳的方式通信，各個SU使用PU的空閑頻段進行業務傳輸．為了避免對PU的傳輸造成干擾，SU必須獲得當前的可用頻譜列表，也就是頻譜機會SOP; 由于PU的行為具有不確定性，SU的SOP會隨時間變化，各個用戶的SOP通過周期性的頻譜感知來獲取．當且僅當兩個SU的SOP之間存在交集，并且它們之間的距離在有效傳輸范圍之內時，才可以建立傳輸鏈路．

圖1給出了抽象的網絡拓撲模型，節點S和D分別代表路由的源節點和目的節點，{A，B，C，E，F}代表多跳路由的中間節點， {C1，C2，C3，C4}表示不同的授權頻段．對于各個鏈路，由于信道帶寬、路徑時延、地理位置等差異，傳輸性能也不同，用一個二元組(delay， cost)來表示信道參數，其中delay表示路徑時延，cost表示流量占用網絡帶寬的開銷．受主用戶行為的影響，各個信道在使用中隨時會被主用戶收回而不可用，這種情況下需要進行路由恢復，有兩個解決方法:在中斷的兩個節點間進行信道切換，選擇另外一個共用信道，原路由方案不變;重新進行源節點到目的節點間的路徑選擇．

圖1　CRAHN的路由模型

在圖1(a)中，從源節點S到目的節點D，有如下幾條路徑可以選擇:

(1)S→A→B→D; total delay=7，cost=6;(2)S→C→D; total delay=6，cost=7;

(3)S→C→F→D; total delay=5，cost=10;(4)S→E→F→D; total delay=3，cost=11．

在這4條路徑中，按照不同的尺度標準有多種選路方案:如果數據流是時延敏感型業務(如在線視頻)，則應當選擇(4)，以期望通過最小時延到達目的地;但是成本較高，會消耗較多的帶寬資源．如果是時延容忍型數據業務(如瀏覽頁面、文件傳輸等)，則應當選擇(1)，以占用較少的網絡資源來完成數據流傳輸．如果從節能和鏈路穩定性的角度考慮，則應當選擇(2)，以經過最小跳數到達目的節點．在圖1(b)中，當信道C2被主用戶收回時，S→C的路徑被中斷時，當前可用路徑僅剩(1)和(4)．這時如果剩余路徑的處理能力有限，就要恢復S到C之間的鏈路，通過多徑路由來處理網絡負荷．這時可以選擇從信道C2切換到信道C3來實現鏈路重建．在圖1(c)中， 當S→C之間的信道切換到C3時，從(1)到(4)的路徑全部可用，這時對路徑(3)進行更新，total delay= 3，cost= 10，路徑(3)成為比(4)總體性能更優的路由方案．

2　多尺度優化模型

2.1　路由尺度分析

2.1.1時延

認知Ad hoc網絡是多跳、分布式的無線網絡，由于SOP是動態變化的，SU需要根據PU的行為進行信道切換和選擇，因此，網絡的端到端總時延Dtotal由兩部分組成: 路徑時延Dpath和切換時延Dswitch，可以表示為

Dtotal=Dpath+Dswitch．

(1)

路徑時延是由數據流在多跳節點間的傳輸引起的，當多個數據流競爭同一個信道時會帶來退避時延Dbackoff[7]．因此，路徑時延也分為兩部分：數據流傳輸時延Dtransmission和退避時延Dbackoff．

(2)

其中，Ttraffic表示業務數據流的流量，Nhop表示當前路徑的跳數，Rk表示鏈路k的數據傳輸速率;nc表示競爭同一信道的節點數量，pc為多個節點競爭同一信道而發生碰撞的概率，W0表示最小競爭窗口的大?。袚Q時延是在頻譜發生移動時發生的，與切換過程所發生的頻段差異成正比，因此，節點在信道Cm和Cn之間的切換時延為

Dswitch=K|B(Cm)-B(Cn)|,

(3)

其中，比例系數K是一個常數，表示單位頻率切換的時間消耗．將K設置為 10 ms/ 10 MHz，也就是， 認知節點的收發機在進行頻譜切換時，每調整工作頻率 10 MHz 需要 10 ms 的時延．B(Cm)和B(Cn)表示信道帶寬，綜合式(1)～式(3)就可計算出當前路徑的總時延．

2.1.2業務傳輸速率

在覆蓋式(overlay)的認知網絡中， SU通過頻譜感知來獲得空閑頻譜列表，并通過參與競爭獲取頻譜的使用權．在無線Ad hoc網中，所有的SU節點以自治、多跳的方式組網，在傳輸過程中要通過分布式的功率控制來提高網絡的容量和能效．各個用戶需要根據周圍環境的變化來調整發射功率，來滿足業務傳輸需求．根據香農公式[8]，SU使用信道Cj能夠獲得的傳輸速率為

(4)

2.1.3穩 定 性

為了解決CRNs的資源動態變化問題，一般通過統計學模型來預測PU的活動規律，并通過計算鏈路穩定時間來控制數據分組的傳輸過程．通常把PU對授權信道的占用情況定義為ON-OFF隨機過程，各個信道的ON和OFF狀態相互獨立且在時刻t服從指數分布，對于信道Cj， 對認知用戶可用的概率是

(5)

(6)

2.2　多尺度優化模型

將路由問題建模為多尺度優化模型，在認知用戶能夠獲得所需帶寬的前提下，通過建立目標函數來改進用戶的服務質量，為不同業務類型的用戶尋找高效的路由方案．文中的路由策略中，優化目標是加權的路由尺度，并通過可調整的權值分配來滿足用戶對時延、穩定性、傳輸速率等的特定需求．

在定義域內存在最優解，表示為x*，有 (x-x*)Fx≥ 0．當滿足條件時，可以通過迭代公式xk+1=xk-βFx在k次迭代之后求得x*，并通過比較x*與候選路由中各個參數的相似度來選取最優路徑．

3　MM-CAODV路由協議

根據CRAHN的特點，對CAODV協議的數據包格式做了擴展，增加的內容主要有: 當前節點的SOP、路由尺度標記(有3項: Delay代表時延，Stab代表鏈路穩定性，Rd代表傳輸速率)、路由開銷等．根據多尺度優化模型設計了MM-CAODV路由協議:

步驟1源節點S在可用信道上感知空閑頻譜，并更新SOP．

步驟2S調用addNeighbor過程獲得鄰居節點信息，創建RREQ(Route Request)數據包并廣播給所有的鄰居節點．

步驟3當中間節點收到RREQ數據包之后，首先判斷自己是否已經在已有的路由表中．如果是，則丟棄該數據包; 如果否，判斷自己的SOP列表是否與上一跳節點的SOP之間存在交集．如果交集為空，則丟棄RREQ數據包．如果能夠建立多個鏈路，則通過式(1)～式(6)計算出各個鏈路的時延、穩定性和最大傳輸速率，并將信息更新到路由表對應的標志位上，繼續廣播至下一跳節點．

步驟4當目的節點D開始接收RREQ請求包時，它將等待一個時間周期，在等待時間內會收到來自多個路徑的報文．每個RREQ數據包中包含了一條路徑信息，通過求解目標函數式(7)選擇目標路由．目的節點D根據決策結果將RREP(Route Reply)數據包通過反向路徑發送給源節點S．

步驟5當源節點S收到RREP應答數據包之后，開始在目標路徑上發送數據流至目標節點．

在路由建立之后，需要在鏈路中斷時能通過較小的代價來維護路由．首先考慮通過信道切換來修復原路徑，如果不可行就重建路由．這需要建立一個信道切換(Channel Switch，CS)報文來實現，過程如下:

(1) 發生鏈路中斷的節點根據路由表信息將CS請求報文發送給鄰居節點．

(2) 對方接收到CS報文之后，中止當前正在傳輸的數據流并檢測與中斷節點間是否存在其他的SOP交集．如果是，轉步驟(3)；如果否，轉步驟(5)．

(3) 節點從SOP交集中通過頻譜分配算法選擇另一可用信道，并將選中的信道通過CS回復報文發送給中斷節點．

(4) 中斷節點收到CS回復信息之后，更新路由表信息并切換至此信道繼續進行業務傳輸．

(5) 當節點間的SOP交集為空時，中斷節點將生成RERR(Route Error)數據包并將該數據包沿著反向路徑發送到源節點．源節點在收到RERR數據包之后，立刻停止當前數據傳輸，啟動路由發現過程．

4　仿真實驗

采用NS-2(Network Simulator 2)網絡仿真工具對文中提出的MM-CAODV路由策略進行仿真和評價，具體的仿真參數如表1所示．

表1　仿真參數表

為源節點定義了3種類型的業務數據流(類型1是高傳輸速率型，類型2是普通業務，類型3為低路由開銷型)，并通過控制報文的路由尺度域和累計開銷域傳遞給接收節點．實驗結果如圖2～圖4所示．在圖2的實驗結果中，各個節點按照隨機路點模型運動，移動速度控制在 2～ 20 m/s 范圍內;共有10個可用信道供用戶使用進行業務傳輸．將文中提出的MM - CAODV與文獻 [6] 中的QoS - CAODV協議分別進行實現，當SU數量從10個遞增到50個時，測試和計算QoS關鍵參數(累計時延、吞吐量和數據投遞率(Processing Data Rate，PDR)．從圖2(a)～(c)的比較中可以看到，文中提出的MM-CAODV協議與QoS-CAODV協議相比，具有較小的累計時延、更大的吞吐量和更高的PDR，總體性能得到改進．在SU節點數量從10增加至40的過程中，隨著節點的增加，有越來越多的數據流需要進行傳輸，吞吐量持續增長; 同時，由于平均跳數的增加，時延也有所增長．但是，在節點數量從40到50時，跳數的繼續增加會降低路由的穩定性，這時一些不滿足式(9)的約束的數據流將暫時退出對資源的競爭; 同時，一些高帶寬的業務將難以獲得滿意的傳輸速率，因此吞吐量有一定程度的減少．在圖2(a)中，文中的策略不會導致額外的時間開銷，具有更低的時延; 在圖2(b)中，MM-CAODV策略能夠充分利用空閑頻譜進行業務傳輸，吞吐量有了平均47%的增長．在圖3的實驗中，將認知用戶數量固定為50，節點的運動模式采用馬爾科夫模型; 比較可見，文中的MM-CAODV策略在絕大多數時間點具有更好的端到端性能．從圖4中可見，在文中的路由策略中，3種不同類型的業務根據特定的資源需求，分別獲得了不同的傳輸速率．

圖2　不同節點數量的QoS參數

圖3　不同時間的QoS參數

圖4　3種業務的傳輸速率

為了評估路由的穩定性，進行了路由持續時間和開銷測試．圖5中，隨著節點數量的增加，路由持續時間呈下降趨勢;改進的協議都具有對無線環境的適應性，能夠修復干擾引起的鏈路失效．MM-CAODV首選通過信道切換的方式對路徑進行維護，避免了不必要的路由重建，改善了路由的持續時間，因此整體穩定性方面略高于QoS-CAODV．從圖6中可見，QoS-CAODV和MM-CAODV協議在路由開銷方面都略高于CAODV協議， 然而能夠以相當小的開銷代價換來明顯的端到端性能改進．MM-CAODV協議結合用戶的業務類型來分配資源，當節點數量較多時具有較明顯的優勢．

圖5 平均持續時間圖6 路由開銷

5　結 束 語

筆者針對認知無線自組網提出一種多尺度路由協議MM-CAODV，該策略根據業務流的特征來定義路由尺度的權值;提出了信道-路由聯合分配的解決方案，并實現了網絡層-物理層的跨層優化．結合頻譜信息為認知用戶提供了適用于不同類型業務的路由方案;針對時延、路由穩定性、網絡開銷等參數進行分析并提出了多尺度優化模型，根據模型設計了具體的路由協議．通過實驗表明，MM-CAODV協議能夠一定程度上優化無線傳輸的QoS性能，為不同的業務類型分配合適的資源，在時延、吞吐量和數據投遞率等方面，都具有一定程度的改進．

參考文獻：

[1] KAMRUZZAMAN S M, FERNANDO X, JASEEMUDDIN M. Energy Aware Multipath Routing Protocol for Cognitive Radio Ad Hoc Networks[J]. International Journal of Communication Networks and Information Security, 2016, 8(3): 186-196.

[2]楊雙懋, 郭偉, 唐偉. 一種最大化網絡吞吐量的認知無線Ad Hoc網絡跨層優化算法[J]. 計算機學報, 2012, 35(3): 491-503.

YANG Shuangmao, GUO Wei, TANG Wei. A Cross Layer Throughput Maximization Algorithm for Cognitive Wireless Ad Hoc Networks[J]. Chinese Journal of Computers, 2012, 35(3): 491-503.

[3]SINGHAL D, GARIMELLA R M. Cognitive Cross-layer Multipath Probabilistic Routing for Cognitive Networks[J]. Wireless Networks, 2015, 21(4): 1181-1192.

[4]ZAREEI M, MOHAMED E M, ANISI M H, et al. On-demand Hybrid Routing for Cognitive Radio Ad-hoc Network[J]. IEEE Access, 2016, 4: 8294-8302.

[5]LIANG Q K, WANG X B, TIAN X H, et al. Two-dimensional Route Switching in Cognitive Radio Networks: a Game-theoretical Framework[J]. IEEE/ACM Transactions on Networking, 2015, 23(4): 1053-1066.

[6]MALLAT Y, AYARI A, AYADI M, et al. Performance Evaluation of QoS-CAODV, CAODV Routing Protocol in Cognitive Radio Ad-hoc Network[C]//Proceedings of the 2015 23rd International Conference on Software, Telecommunications and Computer Networks. Piscataway: IEEE, 2015: 195-199.

[7]YANG Z K, CHENG G, LIU W, et al. Local Coordination Based Routing and Spectrum Assignment in Multi-hop Cognitive Radio Networks[J]. Mobile Networks and Applications, 2008, 13(1/2): 67-81.

[8]龍彥, 李紅艷. 認知無線網絡中視頻傳輸的資源分配方案[J]. 西安電子科技大學學報, 2016, 43(2): 6-12.

LONG Yan, LI Hongyan. Resource Allocation Scheme for Video Transmissions in Cognitive Radio Networks[J]. Journal of Xidian University, 2016, 43(2): 6-12.

[9]闊永紅, 賀冰濤, 陳健. 攜能通信協作認知網絡穩態吞吐量分析和優化[J]. 西安電子科技大學學報, 2016, 43(6): 1-7.

KUO Yonghong, HE Bintao, CHEN Jian. Stable Throughput Analysis and Optimization of Cooperative CRNs Based on Information and Energy Cooperation[J]. Journal of Xidian University, 2016, 43(6): 1-7.

[10]CAO J, WU J S, YANG W C. Spectrum Allocation Strategy for Heterogeneous Wireless Service Based on Bidding Game[J]. KSII Transactions on Internet and Information Systems, 2017, 11(3): 1336-1356.