認知無線車載自組織網絡中的聯合路由調度

張滬寅 王 菁 唐 星

1(武漢大學計算機學院 武漢 430072)2(武漢理工大學計算機科學與技術學院 武漢 430070)

(zhy2536@whu.edu.cn)

認知無線車載自組織網絡中的聯合路由調度

張滬寅1王 菁1唐 星2

1(武漢大學計算機學院 武漢 430072)2(武漢理工大學計算機科學與技術學院 武漢 430070)

(zhy2536@whu.edu.cn)

通過將認知無線電(cognitive radio, CR)技術應用到車載自組織網絡(vehicular ad hoc networks, VANETs)(也稱車聯網)中，認知無線車載自組織網絡(CR-VANETs)可以緩解頻譜資源稀缺問題，有效提高車對車通信的頻譜資源利用率.由于車輛的高速移動性以及認知無線電頻譜資源的動態特性，使得傳統的認知無線電網絡或車載自組織網絡中的路由協議無法直接應用到CR-VANETs中.目前，針對CR-VANETs的路由研究相對較少，如何最大效率地利用有限的頻譜資源，同時降低跳數過多帶來的頻譜資源浪費，仍然是一個有待解決的問題.為此，提出了一種CR-VANETs中聯合路由調度方案，結合了有限頻譜資源調度研究與最小化路由跳數的優化目標.首先，建立了CR-VANETs中的網絡模型和基于車對車通信的頻譜感知模型，預測車輛間有效接觸時間和頻譜可用概率.其次，通過這些參數定義出通信鏈路消耗，并由此得出權衡鏈路質量的權重因子.通過分析優化目標，將其轉化為有限頻譜資源約束下的最小化路由跳數問題，并證明該問題為NP難問題.然后，針對這個聯合路由調度問題提出一種混合啟發式算法，結合了粒子群優化算法的快速收斂性和遺傳算法的種群多樣性，對有限頻譜資源進行調度，同時優化路由跳數.最后仿真實驗結果表明，與現有的CR-VANETs路由研究比較，有著更優的路由跳數并使其保持在一個相對穩定的值.

認知無線電；車載自組織網絡；頻譜調度；路由跳數；混合啟發式算法

車載自組織網絡(vehicular ad hoc networks, VANETs)(也稱車聯網)是一種特殊的自組織網絡.在這個網絡中，車輛都配備了無線通信設備，使得車輛之間可以“彼此交談”，信息共享[1].通過將無線通信技術和信息技術應用到交通系統中，VANETs被廣泛應用于保障交通安全以及車輛信息的傳輸與交互式通信中[2-3].然而，VANETs面臨著頻譜資源稀缺的問題，主要原因有2個：1)不斷增長的信息娛樂應用，例如高質量的視頻流，需要消耗大量的頻譜資源，這使得現有的專用信道帶寬很難保障通信服務質量；2)在城市環境中，一些區域的車輛密度比普通區域高得多，從而導致了頻譜資源稀缺問題更為嚴重[4].

認知無線電(cognitive radio, CR)技術是解決頻譜資源稀缺問題的一種有效方法.次級用戶(secondary users, SUs)采用動態頻譜接入技術，在不對授權用戶(primary users, PUs)造成干擾的前提下，機會地捕捉和利用當前時空中可用的授權CR頻譜空洞，顯著提高了頻譜利用率[5].將CR技術與VANETs相結合構成了認知無線車載自組織網絡(CR-VANETs)，即配備了CR頻譜感知設備的車輛可以機會地接入其他系統中一些被授權的頻帶，如電視白頻譜，可以有效提高頻譜的使用效率，緩解頻譜資源稀缺問題，從而提高車輛的通信效率[6].

雖然針對認知無線自組織網絡(cognitive radio ad hoc networks, CRAHNs)以及VANETs的路由研究較多，但這些路由研究都無法直接應用到CR-VANETs中.這是因為，獨特的車載環境如車輛的高速移動性和車對車(vehicle to vehicle, V2V)的通信鏈路質量都需要被考慮到CR-VANETs的路由設計中.此外，不同于靜態CR場景，CR-VANETs中CR頻譜資源的動態接入特性導致了信道的有效性不僅僅依賴于授權用戶對頻譜的使用情況，還依賴于車輛的移動性.頻譜接入信息過時、無法找到中繼節點、路由跳數過多，這些因素都給CR-VANETs路由設計帶來了巨大的挑戰[7].

目前針對CR-VANETs的路由研究相對較少，已有的少數研究旨在單一優化路由的端到端時延或者鏈路持續時間.然而，在CR-VANETs的路由設計中，如何最大效率地利用有限CR頻譜資源，是需要研究的問題之一.而現有的路由研究并未將CR頻譜資源調度作為衡量通信鏈路質量的參數，用于路由方案的設計中.此外，在多跳無線網絡中，過多的跳數僅能在“能量有限”的約束環境中起到一定的作用.因為克服噪音是這種網絡環境需要關注的首要問題.而在“帶寬有限”的約束環境中，當信噪比高，由于使用了額外的時隙，過多的跳數則會降低端到端吞吐量[8].在CR-VANETs中，由于車載供能使得信號發射能量不再有限制.因此，對于有限的CR頻譜資源，過多的路由跳數會消耗CR信道切換帶寬，導致頻譜資源浪費.尤其當車輛密度較大可能出現擁塞時，過多的路由跳數還會使路由開銷增大，進一步加重擁塞.

在本文中，區別于現有的CR-VANETs路由研究以及我們前期的研究目標[9]，設計了一種聯合路由調度方案，將CR頻譜資源調度作為影響通信鏈路質量的參數，同時最大限度地減少網絡中的路由跳數.本文的主要貢獻有4點：

1) 我們建立了一個CR-VANETs中的網絡模型，預測車輛移動并定義出車輛間有效接觸時間.

2) 我們建立了一個基于V2V通信的CR頻譜模型，得出CR頻譜可用概率.通過建模得出的參數，定義出V2V通信鏈路的鏈路消耗，將其作為權衡鏈路質量的權重因子，并通過這個權重因子來進行CR頻譜資源調度.同時分析了優化目標，將其轉化為有限CR頻譜資源約束下的最小化路由跳數問題，并證明該問題為NP難問題.

3) 針對這個聯合路由調度問題，我們提出了一種混合啟發式算法，結合了粒子群優化算法的快速收斂性和遺傳算法的種群多樣性，在對有限CR頻譜資源調度的同時進行路由跳數優化.

4) 仿真實驗結果表明，與現有的CR-VANETs路由研究比較，我們的優化方案有著更優的路由跳數并使其保持在一個相對穩定的值.

1 CR-VANETs背景知識

1999年美國聯邦通信委員會(the US Federal Communications Commission, FCC)分配了75 MHz無線頻譜(5.850～5.925 GHz)帶寬給專用短程通信(dedicated short range communications, DSRC)，用于智能交通系統(intelligent transportation systems, ITS)服務[10].根據FCC的規定，這樣的頻段分為7個信道，包括1個控制信道和6個服務信道，控制信道被分配用于傳輸信標或基本安全消息[11].每個車輛周期性地在控制信道上廣播交通信息，包括車速、坐標和車輛的下一個坐標.此信息有助于車輛實時地發現所有相鄰車輛[12].然而，在城市環境中，車輛的增多伴隨著車輛間通信需求的增加，引發了通信頻帶的擁擠，導致了車輛間通信效率的下降[13].此外，車內信息娛樂應用也越來越多，包括對帶寬要求高的多媒體應用將會導致網絡的擁塞[14].

隨著認知無線電技術和動態頻譜接入技術的出現，為了提高頻譜使用效率，FCC放開了授權頻譜的使用權，使得空閑的授權頻譜(也被稱為“頻譜空洞”)可以機會地被未授權用戶使用.為了解決頻譜稀缺問題，VANETs與CR技術聯合在一起，形成了CR-VANETs.即裝載了CR通信裝置的車輛可以方便地接入DSRC信道以及其他檢測到的空閑信道.當DSRC信道的傳輸負載較重，CR將檢測和使用其他的空閑信道.在這種情況下，配備了CR通信設備的車輛是未授權用戶，也稱為SUs.

不同于傳統CR網絡，車輛的高速移動性使得CR-VANETs網絡拓撲是一個動態結構.而不同于傳統VANETs，在CR-VANETs中頻譜的動態特性使得頻譜空洞可能在時間和空間上均發生變化.這些特性使得CR-VANETs中的頻譜感知和頻譜接入問題極具挑戰性.為了解決這些問題，近年來，一些學者對CR-VANETs中的頻譜感知、接入、管理等問題進行了深入研究[15-18].一方面，這些文獻指出高速運動的車輛具有較好的時空分集特性.在CR-VANETs中，采用協作感知的方法能夠獲得更好的頻譜感知參數，充分利用車輛的時空分集特性能夠獲得更好的頻譜檢測性能.另一方面，這些文獻基于車輛位置預測和頻譜地理數據庫查詢的方法，讓車輛快速和準確地獲得當前位置以及將來位置的可用頻譜信息.這些工作通過理論和仿真實驗論證了在CR-VANETs中，所提方法能夠保證高速運動環境下CR信道檢測的準確性和及時性.

2 相關工作

2.1CRAHNs和VANETs中的路由研究

CRAHNs和VANETs是與CR-VANETs有相似點但又完全不同的2種網絡.目前針對CRAHNs和VANETs中路由協議的研究較多.文獻[19]提出了一種CRAHNs中基于頻譜聚合的協同路由方案，這個路由方案由2種不同類別的路由協議組成，一種用于提高能源效率和吞吐量，另一種則用于減少端到端的延時.文獻[20]的作者針對大規模CRAHNs的無線網絡衰落信道，提出了一種基于頻譜授權圖的機會路由協議，并采用協同網絡調度來實現多徑傳輸方案.在文獻[21-22]中，CRAHNs中的路由路徑被分割為數個機會轉發段，數據包通過這些轉發段來實現一步接一步的轉發.文獻[23]提出了一種VANETs中基于協同傳輸方案的跨層路由協議.通過衡量路由決策的鏈路成本，更好地實現傳輸功耗和端到端可靠性之間的權衡關系.文獻[24]基于變化的拓撲結構設計了一個VANETs中鏈路持續時間的度量值，并通過捕捉鏈路剩余時間來判斷該鏈路是否可以用于有效通信，以達到優化路由結構的目的.在文獻[25]中，一種稱為骨干輔助的方案被用于提供交叉路口的連接狀態.基于這種連接狀態，作者提出了一種基于貪心策略的路由調度方案，使得在城市VANETs環境中，路由的中間節點數目最小.

然而，上述這些路由協議無法直接用于CR-VANETs環境中.一方面是由于車輛的高速移動，使得車對車通信處在一個高速動態特性的網絡拓撲中；另一方面，CR頻譜的可用性不僅會根據PUs的活動發生變化，還會根據SUs的活動呈現持續變化的特性.本文在設計CR-VANETs路由方案時，將車輛間的有效接觸時間以及CR頻譜的可用性均列入了路由設計的考慮因素.

2.2CR-VANETs中的路由研究

目前已有若干針對CR-VANETs的路由方案研究.有的考慮到了CR頻譜的干擾性及車輛的移動性，還有一些考慮到了PUs的活動特性、地理位置及信道切換時延等.

文獻[26]提出了一種任意路徑的路由協議，利用地理位置信息和感知到的信道進行多速率路由調度.這個任意路徑路由的特性是，選擇在地理位置上更接近目的地的節點為轉發節點，路由路徑隨著轉發節點的改變而改變，從而達到優化路由傳輸時延的目的.文獻[27]的作者通過可用頻譜狀態，選擇了一條安全路徑使得PUs和SUs能同時保持通信，并使用移動參數和頻譜感知信息來避免路由開銷過大.在這個路由方案中，節點僅僅需要知道自己的頻譜信息就可以選路，而不需要將自己的頻譜信息告訴鄰居節點.在文獻[28]中，作者通過將PUs的活動特性考慮到頻譜變化參數中，提出了一種路徑持續時間最大化的路由算法，實現從源節點到目的節點之間的路由有最大路徑持續時間.在前期的研究中[9]，我們針對時延要求不高的應用場景，采用存儲轉發策略，提出了一種時延容忍的路由策略來最大化路由投包率.

然而，上述文獻的路由方案均未從CR頻譜資源調度方面進行考慮，也未針對路由跳數進行研究和優化.基于目前還沒有針對CR-VANETs中頻譜調度和路由跳數優化的研究，本文提出了一種聯合路由調度方案，通過混合啟發式算法，將CR頻譜資源調度作為影響通信鏈路質量的參數，同時最大限度地減少網絡中的路由跳數.

3 系統模型及問題描述

3.1網絡模型

我們假設有V={V1,V2,…,Vn}輛車，每一輛車都配備了CR頻譜感知設備和GPS設備.我們可以通過GPS來獲取車輛的位置信息和速度信息，然后計算出車輛與車輛間的相對速度.考慮到一般性，我們定義車輛Vi,Vj∈V，分別以速度vi和vj在極坐標(vi,θi)和(vj,θj)中行駛，定義車輛Vi和車輛Vj之間的相對速度為vi j，則相對速度vi j可以計算為

vi j=g(vi,vj,θi,θj)=

(1)

其中，g(vi,vj,θi,θj)依賴于隨機變量vi,vj,θi和θj，并且這些變量之間相互獨立.此外，我們認為vi j=vj i.

我們假設每個CR節點的通信范圍為Ω∈r2.如圖1所示，如果在時間間隔Δt內，車輛Vi和Vj沒有改變它們的行駛速度，相對于車輛Vj來說，車輛Vi可視為相對靜止在一個固定的位置，此時車輛Vj以相對速度vi j移動.設車輛Vi的有效通信覆蓋區半徑為rTX，當車輛Vj在這個有效通信的覆蓋區域內，車輛Vi和Vj之間能夠進行有效通信.當車輛Vj移出圖1中的這個陰影區域，則車輛Vi和Vj之間無法進行有效通信.

Fig. 1 V2V communication region圖1 車對車通信范圍

在實際應用中，我們還需要考慮不同車輛之間的接觸時間.因此我們定義車輛Vi和車輛Vj之間的有效接觸時間如下：

其中,t和tq是連續時間變量.

這個網絡模型可以被抽象為一個二維平面內的有向圖G(V,E).其中，節點集V為之前描述的所有車輛節點的集合V={V1,V2,…,Vn}，E表示網絡中車輛節點之間的無線鏈接.如果車輛Vj在車輛Vi的通信范圍之內，則邊(Vi,Vj)∈E.

3.2基于V2V通信的CR頻譜模型

在下墊式CR頻譜系統中，一個基于V2V通信的CR頻譜模型如圖2所示.我們假設每個車輛根據GPS地圖將道路分割成S={S1,S2,…,Sm}個路段.與車輛的高速移動性相比，PUs在道路上處于一個相對固定的位置，并工作在一個授權信道上.車輛行駛在相同的道路上，會經歷相同的CR信道可用性統計數據圖.通過這些歷史感知統計數據，可以由馬爾可夫模型計算出相同信道的狀態轉移矩陣，推導出反映信道可用性的潛在規律[29].

Fig. 2 CR spectrum model based on V2V圖2 基于V2V通信的CR頻譜模型

IEEE 802.22標準中規定，協作頻譜的感知操作會消耗幾個毫秒(通常小于200 ms)，CR在空閑信道上傳輸的時間需要幾秒(通常為2 s).因此，我們假設2 s為CR傳輸檢測周期，即在下一個2 s中的信道可用性與當前頻譜決策結果不同.如果路段的長度分割合理，我們假設同一路段內的信道狀態相同，每條路段都屬于多種CR信道狀態之一.該做法的目的是預測在下一個路段的信道可用性，即CR信道狀態將在下一個周期(如2 s)轉變.因此只要CR信道狀態在該路段內保持不變，路段的長度就不影響CR信道可用概率的預測.

通過對歷史頻譜感知圖的統計數據進行數據挖掘，以及對具有相同信道狀態轉移矩陣的信道進行先驗預測，車輛Vi在路段Sl里，CR信道可用概率可計算為[29]

(2)

在CR-VANETs中，由于CR頻譜帶寬資源有限，我們需要計算不同車輛之間通信鏈路對頻譜資源的消耗，以權衡中繼節點的頻譜效用.如果車輛Vi和Vj出現在通信鏈路中，我們定義車輛Vi與車輛Vj之間的通信鏈路消耗如下：

其中，c為反比例常數.

將通信鏈路消耗作為鏈路權重因子，能夠有效地衡量車輛Vi與車輛Vj通信的頻譜資源效用以及車輛間通信鏈路質量.在這個系統中，我們假設信道分配狀態消息是通過公共控制信道來交換的.這在CR-VANETs中，可以通過使用專用授權頻帶來實現.

3.3聯合路由調度問題

在CR-VANETs系統中，有V輛車、S個路段以及k個不同的CR信道狀態.我們優化的目標為有限CR頻譜資源調度，同時最小化路由跳數.

我們可以將有限CR頻譜資源調度問題，視為提高CR頻譜資源效用的問題.在3.2節中，我們定義了通信鏈路消耗參數W(Vi,Vj)，并將其作為鏈路權重因子.由于W與車輛的CR可用信道概率成反比，同時與車輛的有效接觸時間成反比.當權重因子最小，即通信鏈路消耗參數W取最小值時，CR可用信道概率與車輛的有效接觸時間同時有最大值，此時CR頻譜資源效用最大，通信鏈路質量最好，即頻譜資源調度最優.在3.1節中，我們將CR-VANETs網絡模型抽象為一個二維平面內的有向圖G(V,E)，這個問題則轉化為：如何將有向圖中鏈路總消耗W(Vi,Vj)的總和降到最低，這可以等同于一個最小生成樹問題.

此外，我們可以將最小化路由跳數問題視為一個路由選路的問題，即在此系統中，消息盡其可能通過最少的中繼節點來實現從源節點到目的節點的轉發.因此，我們的聯合路由調度問題可以轉化為：在有限CR頻譜資源約束下，最小化路由跳數的路由問題.

我們定義節點Vi的可達鄰居子圖為Gi(Vi,Ei)，并在其中構建最小生成樹.然后，我們用Ei={ε1,2,ε1,3,…,εi,j,…,εn-1,n}記錄Gi中的邊，如果邊(Vi,Vj)∈Ei，則εi,j=1，否則εi,j=0.我們用Di={δ1,2,δ1,3,…,δi,j,…,δn-1,n}表示圖Gi的一棵生成樹.如果εi,j=1，且邊(Vi,Vj)被選為生成樹的邊，則δi,j=1，否則δi,j=0.對于任何一棵生成樹D，其權值用所有邊權重的和來表示.我們定義F(xV)為路由跳數，則我們的優化目標可被描述為

R*=arg minRF(xV)，

(3)

當最小生成樹問題被賦予了新的約束條件，即轉化為節點約束最小生成樹問題，則該問題是一個典型的NP難問題[30].因此，CR-VANETs中，基于有限CR頻譜資源約束下的最小化路由跳數問題也是一個NP難問題.

4 混合啟發式算法

由于節點約束最小生成樹問題屬于多維優化問題，因此本文提出了一種混合啟發式(hybrid two heuristic, HTH)算法來解決這個聯合路由調度問題.這個混合啟發式算法結合了具有快速收斂特性的粒子群優化算法和具有良好全局收斂特性的遺傳算法，增加了種群多樣性，提高了搜索效率.通過這個混合啟發式算法，我們首先找出CR頻譜資源效用大的路由路徑，然后基于這個給定備選路徑選出跳數最少的路由方案.

4.1粒子群優化算法

首先，我們引入帶有慣性權重的粒子群優化算法，其數學表達式為

vi d(t+1)=wvi d(t)+c1α(Pi d(t)-xi d(t))+
c2β(Pg d(t)-xi d(t)),

(4)

xi d(t+1)=xi d(t)+vi d(t+1),

(5)

其中，vi d(t)為第i個粒子第t次迭代中飛行速度的第d維分量;xi d(t)為第i個粒子第t次迭代中位置的第d維分量;Pi d為粒子i最好位置Pi的第d維分量;Pg d為群體最好位置Pg的第d維分量.α和β為隨機數;c1和c2為加速因子;w為慣性權重.

粒子群優化算法中每個粒子可以用于表示問題的一個候選解，不同的問題通常采用不同的粒子編碼方式.本文在算法設計時，采用Prufer數的染色體編碼機制[31]來表示生成樹的解空間.Prufer數給出了n個節點的生成樹與長度為n-2的數字串之間的一一對應關系，能夠保證解空間的完備性.Prufer編碼和解碼算法的偽代碼描述如下：

算法1. PRUFER編碼算法.

輸入：生成樹D;

輸出：相應PRUFER編碼.

①if樹D中只剩下一條邊then

② 輸出此時得到的編碼串，即為樹D的PRUFER編碼；

③else

④forall生成樹D中的葉子節點do

⑤ 將葉子節點中標號最小的節點編號標

記為σ；

⑥ifμ是與σ相鄰的節點編號then

⑦ 在編碼串的最右端加入μ；

⑧ 在樹D中，把σ以及連接σ和μ的邊都刪除；

⑨ 樹的頂點數為n-1個；

⑩endif

算法2. PRUFER解碼算法.

輸入：相應PRUFER編碼Q;

輸出：生成樹D.

①ifQ=?then

③ 構成的樹就是與最初Q所對應的生成樹，輸出生成樹；

④else

⑦ 將最小的數字標記為σ，Q中最左端的數字為μ；

⑧ 在樹中加入連接σ和μ的邊；

⑩ifμ 不再出現在Q中then

例如有一棵生成樹如圖3(a)所示，與之相對應的Prufer數則為圖3(b)所示的編碼.

Fig. 3 Spanning tree and Prufer number圖3 生成樹與對應的Prufer數編碼

我們根據Prufer數的解碼方案計算出生成樹D={δ1,2,δ2,3,…,δi,j,…,δn-1,n}，解碼方案為編碼方案的逆過程.則粒子X的適應度可定義為

).

(6)

命題1. 在同一個路段，對于種群中的任意2個粒子，擁有較小適應度的粒子有更好的解.

證畢.

通過命題1可知，使用式(6)的適應度方程，我們可以選擇出更優的CR頻譜資源效用方案，然后基于這個方案下的備選路徑，選擇跳數最少的路由.

4.2HTH路由算法

(7)

變異算子M的具體操作如下:首先隨機選取粒子X中的一個位置點ξ，令X(ξ)等于{1,2,…,n}中隨機選取的一個值.對于某個節點車輛Vi而言，n為節點Vi的可達鄰居節點數.

此外，我們采用遺傳算法中的交叉算子Cp和Cg來表示粒子群優化算法中的局部最優位置和全局最優位置：

(8)

(9)

雜交算子Cp，Cg均采用的是雙點雜交算子，具體操作如圖4所示：令粒子X的當前位置為Ai，X的自身最優位置為Pi，種群的全局最優位置為G，隨機選取2個位置點h1和h2，則新粒子位置點h1和h2之間的部分由粒子Pi的這部分序列直接復制而來.

Fig. 4 Two point hybridization of particles圖4 粒子的雙點雜交示意圖

粒子與種群的全局最優位置的交叉操作也采取相同的方式.綜上所述，粒子X的位置更新公式為

(10)

在搜索過程中，為了提高算法的搜索效率，將參數調整如下：

w=(wmax-wmin)×(gen-mgen)gen+w,

(11)

c1=1.0-(mgen×1.0)gen,

(12)

c2=1.0-c1,

(13)

其中，wmax和wmin分別為初始化時w的最大值和最小值；gen為種群最大的進化代數；mgen為種群當前的進化代數.

CR-VANETs中的任意節點Vi根據局部信息，運行HTH算法偽代碼如下：

算法3. HTH算法.

輸入：原始的局部網絡拓撲結構圖Gi(Vi,Ei)、節點的最大通信范圍;

輸出：節點Vi的本地節點約束最小生成樹.

① 初始化種群X以及相應的參數，如種群規模popsize，進化代數gen，w，c1和c2等；

②if算法終止條件不滿足then

③forall種群中的粒子do

④ 進行粒子位置的更新；

⑤ifXi不滿足節點度約束條件then

⑥ 進行約束滿足調整；

⑦endif

⑧ 對粒子的適應度進行評價；

⑨ 更新粒子自身的最優位置pBesti；

⑩ 更新種群的全局最優位置gBest；

通過這個混合啟發式算法，我們采用了最小生成樹的拓撲調節思路，通過對粒子的適應度進行評價，對加速因子和慣性權重進行調整，得出問題的全局最優解，即選出跳數最少的路由方案.

5 實驗與結果

我們使用了NS2平臺來評估混合啟發式算法的性能，并同4種路由方案作參數比較：無線自組網按需平面距離向量路由協議(ad hoc on-demand distance vector routing, AODV)、CR-VANETs中的延時優化路由研究(CoRoute)[26]、轉發性能優化路由研究(SSR)[27]以及路由持續時間優化的研究(EPDM-R)[28].

5.1仿真設置

在仿真環境中，我們采用干擾溫度模型來確定接收信號的實際信道狀態[32].授權用戶PUs通過瑞麗信道傳輸信號，并按照自由空間傳播模型衰減.CR頻譜包含10個信道，每一個信道有2 MHz帶寬，每個PU被分配到10個CR信道中的一個信道.此外，我們采用了文獻[33]中對信道概率的設置規則，即每個PU接入授權信道的規則為：p(0/0)=0.95，p(1/0)=0.05，p(0/1)=0.10，p(1/1)=0.90，其中p(1/0)是PU從閑置狀態“0”變化為忙狀態“1”的概率.

依據IEEE 802.22標準中規定的參數，我們假設2 s為一個信道傳輸檢測周期.考慮到車輛移動的最大速度為60 km/h(即16.7m/s)，我們在仿真實驗中設置的路段長度為50 m.

在無線網絡配置方面，我們采用IEEE 802.11p標準作為媒體接入控制(media access control, MAC)層協議.我們設置通信范圍為400 m，數據包大小為512 B.為便于評估性能參數，我們不考慮城市場景中的障礙物遮擋情況.我們假設車輛(即次級用戶SUs)在道路上呈泊松分布，并沿著道路直線行駛.仿真實驗在不同的車輛密度下進行，從50～300輛車，表示相對稀疏和密集的網絡.仿真時間12 h，所有參數均取平均值.實驗參數如表1所示:

Table 1 Simulation Parameters

5.2仿真結果

實驗結果分別從平均路由跳數、投包率以及端到端延時這3個參數來對比了5種路由方案的性能參數，同時比較了不同路由方案在不同車輛密度下的參數值.此外，我們還基于本文提出的路由方案，比較了不同信道帶寬參數對平均路由跳數的影響.

圖5顯示了在不同車輛密度下，上述5種路由方案的平均跳數值.當車輛密度增大時，這5種路由方案的平均跳數值都有所增加.這是因為，隨著車輛的增多，可以作為中繼節點的候選車輛節點數量也隨之增多，每個包的傳輸機會隨著車與車的接觸增多也相應增大.為了各自的優化目標，這5種路由方案都會為了完成優化目標而改變包的傳輸路徑，從而導致了路由跳數的增加.

Fig. 5 Average hop count of different routing algorithms圖5 不同路由方案的平均跳數

HTH算法在每個密度點的跳數均值都優于其他路由方案，并且其平均跳數值保持在一個相對較小的波動范圍內.在相對密集的網絡環境中，SSR路由方案的平均跳數略有減少，這是由于在其優化轉發過程中，為了避免開銷過大會對路由開銷進行約束，從而導致了路由跳數減小.在相對稀疏的網絡中，EPDM-R路由方案的平均跳數值也相對較小.但隨著車輛密度的增大，中繼節點增多，基于從源節點到目的節點的路由持續時間最大化優化目標導致了該方案路由跳數的增加.CoRoute路由方案的平均跳數值隨車輛節點的增加而增幅最大.這是因為在CoRoute路由方案中，最小化端到端延時是其優化目標，當出現了路徑更短的中繼節點時，此節點便立即成為下一跳目標.這就導致當車輛節點增多時，候選節點的增多帶來了路由跳數的增加.

Fig. 6 Packet delivery ratio of different routing algorithms圖6 不同路由方案的投包率

圖6顯示了在不同車輛密度下，上述5種路由方案的數據投包率.其他路由方案的投包率均隨著車輛密度的增大而增加，而AODV路由方案的投包率則明顯下降.導致這種現象的原因之一是：在AODV協議中，當一個節點需要給網絡中的其他節點傳送信息時，如果沒有到達目標節點的路由，則必須先以多播的形式發出路由請求報文.而包開銷的增加會導致網絡負載顯著增加，從而導致更多的數據包被丟棄.

在大多數密度節點下，HTH路由方案取得了比其他路由方案更高的投包率.這是由于在HTH路由方案中，將CR頻譜資源調度作為衡量通信鏈路質量的參數，將通信鏈路消耗作為有限頻譜CR頻譜資源約束條件，從而提高了CR頻譜資源效用，獲得了較高的投包率.在車輛密度增長到250節點后，HTH路由方案的投包率呈現增長平緩的趨勢.這是因為HTH路由方案聯合了最小化路由跳數的優化目標，使其在節點密度大的環境中，權衡了優化目標和約束條件這兩者之間的關系.在車輛到達300的最大密度節點時，由于EPDM-R路由方案的優化目標為路由持續時間最大化，因此表現的更佳.

Fig. 7 End-to-End delay of different routing algorithms圖7 不同路由方案的端到端時延

圖7顯示了在不同車輛密度下，上述5種路由方案的端到端延時.當車輛密度增大時，其他路由方案的端到端延時有所下降，而AODV路由方案的端到端延時則明顯上升.這是因為在AODV路由方案中，一旦發現某一個鏈路斷開，路由中的節點就發送ERROR報文通知那些因鏈路斷開而不可達的節點刪除相應的記錄，或者對已存在的路由進行修復，從而增加了傳輸時延.基于延時優化目標的CoRoute路由方案表現最優.HTH路由方案在端到端延時這個性能上，表現略遜于CoRoute路由方案，但是仍然優于SSR路由方案以及EPDM-R路由方案.在HTH路由方案中，包是按照最佳跳數路由來傳播的，這導致了它會因為路由跳數的優化目標而錯過一些延時較小的中繼節點，或者不會為了選擇更短的幾何距離到達目的節點從而選擇跳數較多的路由.SSR路由方案和EPDM-R路由方案均有相對較高的端到端延時，且在低密度節點SSR路由方案優于EPDM-R路由方案，而在高密度節點則正好相反.這是因為不同的優化目標使得它們在不同的節點密度下表現出不同的優化特性.

圖8顯示了在不同車輛密度下HTH路由方案的平均跳數值.當CR信道帶寬較小時，平均路由跳數相對較大.當CR信道帶寬增加到一定值時，平均路由跳數則不再受到CR信道帶寬的顯著影響.這是因為，通過使用額外的CR信道帶寬，一定程度上降低了DSRC信道擁塞，從而減少了路由跳數.此外，CR信道空閑帶寬越大，其信道可用概率就越高，包傳輸的可靠性則越高.當CR信道帶寬超過一定的閾值時，路由平均跳數受信道帶寬的影響則相對較小.

Fig. 8 Average hop count with different channel bandwidth圖8 不同信道帶寬情況的平均路由跳數

6 結束語

本文研究了一個CR-VANETs中聯合CR頻譜資源調度和最小化路由跳數的問題.為解決這個問題，我們建立了CR-VANETs中的網絡模型以及基于V2V通信的CR頻譜模型，用于預測車輛間有效接觸時間，并得出CR頻譜可用概率.通過這些參數，我們定義了網絡拓撲中的通信鏈路消耗，并將這個鏈路消耗作為CR頻譜資源調度的權重因子.我們將這個聯合路由調度問題轉化為有限CR頻譜資源約束下的路由跳數優化問題，并證明該問題為節點約束最小生成樹的NP難問題.我們通過粒子群優化算法和遺傳算法相結合的混合啟發式算法，找出CR頻譜資源效用大的路由路徑，然后基于這個給定備選路徑，我們選出跳數最少的路由方案.仿真實驗結果表明，與現有的CR-VANETs路由研究比較，我們的方案有著更優的路由跳數并使其保持在一個相對穩定的值.

[1]Drabkin V, Friedman R, Kliot G, et al. On reliable dissemination in wireless ad hoc networks[J]. IEEE Trans on Dependable amp; Secure Computing, 2011, 8(6): 866-882

[2]Xie Yong, Wu Libing, Zhang Yubo, et al. Anonymous mutual authentication and key agreement protocol in multi-server architecture for VANETs[J]. Journal of Computer Research and Development, 2016, 53(10): 2323-2333 (in Chinese)(謝永, 吳黎兵, 張宇波, 等. 面向車聯網的多服務器架構的匿名雙向認證與密鑰協商協議[J]. 計算機研究與發展, 2016, 53(10): 2323-2333)

[3]Liu Bingyi, Wu Libing, Jia Dongyao, et al. Data uplink strategy in mobile cloud service based vehicular ad hoc network[J]. Journal of Computer Research and Development, 2016, 53(4): 811-823 (in Chinese)(劉冰藝, 吳黎兵, 賈東耀, 等. 基于移動云服務的車聯網數據上傳策略[J]. 計算機研究與發展, 2016, 53(4): 811-823)

[4]Lu Ning, Luan T, Wang Miao, et al. Capacity and delay analysis for social-proximity urban vehicular networks[C]Proc of IEEE INFOCOM’2012. Piscataway, NJ: IEEE, 2012: 1476-1484

[5]Tsukamoto K, Koba S, Tsuru M, et al. Cognitive radio-aware transport protocol for mobile ad hoc networks[J]. IEEE Trans on Mobile Computing, 2013, 14(2): 288-301

[6]Han You, Ekici E, Kremo H, et al. Throughput-efficient channel allocation algorithms in multi-channel cognitive vehicular networks[J]. IEEE Trans on Wireless Communications, 2017, 16(2): 757-770

[7]Singh K D, Rawat P, Bonnin J M. Cognitive radio for vehicular ad hoc networks (CR-VANETs): Approaches and challenges[J]. EURASIP Journal on Wireless Communications and Networking, 2014, 2014(1): 49

[8]Andrews J G, Weber S, Kountouris M, et al. Random access transport capacity[J]. IEEE Trans on Wireless Communications, 2010, 9(6): 2101-2111

[9]Wang Jing, Zhang Huyin, Tang Xing. Delay tolerant routing for cognitive radio vehicular ad hoc networks[C]Proc of the 22nd IEEE Int Conf on Parallel and Distributed Systems. Piscataway, NJ: IEEE, 2017: 24-31

[10]Regan M A, Oxley J A, Godley S T, et al. Intelligent transport systems: Safety and human factors issues[J]. Report, 2001, No.0101

[11]Kenney J B. Dedicated short-range communications (DSRC) standards in the United States[J]. Proceedings of the IEEE, 2011, 99(7): 1162-1182

[12]Ma Xiaomin, Zhang Jinsong, Wu Tong. Reliability analysis of one-hop safety-critical broadcast services in VANETs[J]. IEEE Trans on Vehicular Technology, 2011, 60(8): 3933-3946

[13]Cheng S T, Horng G J, Chou C L. Adaptive vehicle to vehicle heterogeneous transmission in cooperative cognitive network VANETs[J]. International Journal of Innovative Computing Information amp; Control, 2012, 8(2): 1263-1274

[14]Ghandour A J, Fawaz K, Artail H. Data delivery guarantees in congested vehicular ad hoc networks using cognitive networks[C]Proc of the 7th Int Wireless Communications and Mobile Computing Conf. Piscataway, NJ: IEEE, 2011: 871-876

[15]Niyato D, Hossain E, Wang Ping. Optimal channel access management with QoS support for cognitive vehicular networks[J]. IEEE Trans on Mobile Computing, 2011, 10(4): 573-591

[16]Pan Miao, Li Pan, Fang Yuguang. Cooperative communication aware link scheduling for cognitive vehicular networks[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(4): 760-768

[17]Felice M D, Doost-Mohammady R, Chowdhury K R, et al. Smart radios for smart vehicles: Cognitive vehicular networks[J]. IEEE Vehicular Technology Magazine, 2012, 7(2): 26-33

[18]Cheng Nan, Zhang Ning, Lu Ning, et al. Opportunistic spectrum access for CR-VANETs: A game-theoretic approach[J]. IEEE Trans on Vehicular Technology, 2014, 63(1): 237-251

[19]Ping S, Aijaz A, Holland O, et al. SACRP: A spectrum aggregation-based cooperative routing protocol for cognitive radio ad-hoc networks[J]. IEEE Trans on Communications, 2015, 63(6): 2015-2030

[20]Lin S C, Chen K C. Spectrum-map-empowered opportunistic routing for cognitive radio ad hoc networks[J]. IEEE Trans on Vehicular Technology, 2014, 63(6): 2848-2861

[21]Tang Xing, Chang Yanan, Zhou Kunxiao. Geographical opportunistic routing in dynamic multi-hop cognitive radio networks[C]Proc of 2012 Computing, Communications and Applications Conf. Piscataway, NJ: IEEE, 2012: 256-261

[22]Tang Xing, Liu Qin. Network coding based geographical opportunistic routing for ad hoc cognitive radio networks[C]Proc of 2012 IEEE GLOBECOM Workshops. Piscataway, NJ: IEEE, 2013: 503-507

[23]Ding Zhiguo, Leung K K. Cross-layer routing using cooperative transmission in vehicular ad-hoc networks[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(3): 571-581

[24]Sofra N, Gkelias A, Leung K K. Route construction for long lifetime in vanets[J]. IEEE Trans on Vehicular Technology, 2011, 60(7): 3450-3461

[25]Sahu P K, Wu E H, Sahoo J, et al. BAHG: Back-bone-assisted hop greedy routing for VANET’s city environments[J]. IEEE Trans on Intelligent Transportation Systems, 2013, 14(1): 199-213

[26]Kim W, Gerla M, Oh S Y, et al. CoRoute: A new cognitive anypath vehicular routing protocol[J]. Wireless Communications amp; Mobile Computing, 2011, 11(12): 1588-1602

[27]Abedi O, Bemaninejad S. Soft and stable routing protocol for cognitive radio VANETs considering cognitive users mobility[C]Proc of the 11th Int Conf on Innovations in Information Technology. Piscataway, NJ: IEEE, 2015: 116-121

[28]Liu Jing, Ren Pinyi, Xue Shaoli, et al. Expected path duration maximized routing algorithm in CR-VANETs[C]Proc of the 1st IEEE Int Conf on Communications in China. Piscataway, NJ: IEEE, 2012: 659-663

[29]Huang Xinlin, Wu Jun, Li Wenfeng, et al. Historical spectrum sensing data mining for cognitive radio enabled vehicular ad-hoc networks[J]. IEEE Trans on Dependable amp; Secure Computing, 2016, 13(1): 59-70

[30]Mitsuo G, Cheng Runwei. Genetic Algorithms and Engineering Optimization[M]. Beijing: Tsinghua University Press, 2004

[31]Gottlieb J, Julstrom B A. Prufer numbers: A poor representation of spanning trees for evolutionary search[J]. Cheminform, 2002, 36(7): 2386-2390

[32]Federal Communications Commission (FCC). Notice of inquiry and notice of proposed rulemaking[R]. Washington, DC: Technical Report ET Docket 03-237, 2003

[33]Huang Xinlin, Wang Gang, Hu Fei. Multitask spectrum sensing in cognitive radio networks via spatiotemporal data mining[J]. IEEE Trans on Vehicular Technology, 2013, 62(2): 809-823

ZhangHuyin, born in 1962. Professor and PhD supervisor. His main research interests include network QoS, next generation network architecture, and ad hoc networks.

WangJing, born in 1983. PhD candidate. Her main research interests include wireless networks and mobile ad hoc networks (wangjing100717@whu.edu.cn).

JointRoutingandSchedulinginCognitiveRadioVehicularAdHocNetworks

Zhang Huyin1, Wang Jing1, and Tang Xing2

1(School of Computer Science, Wuhan University, Wuhan 430072)2(School of Computer Science and Technology, Wuhan University of Technology, Wuhan 430070)

Cognitive radio vehicular ad hoc networks (CR-VANETs) have been envisioned to solve the problem of spectrum scarcity and improved spectrum resource efficiency in vehicle-to-vehicle communication by exploiting cognitive radio into the vehicular ad hoc networks. Most existing routing protocols for cognitive radio networks or vehicular ad hoc networks cannot be applied to CR-VANETs directly due to the high-speed mobility of vehicles and dynamically changing availability of cognitive radio channels. At present, the routing research for CR-VANETs is relatively few. How to utilize the spectrum resources effectively and moreover reduce the spectrum band consumption caused by routing hops is still a pending problem. Aspiring to meet these demands and challenges, this paper presents a joint routing and scheduling, which combines the scheduling of spectrum resources and the goal of minimizing routing hops in CR-VANETs. To achieve this goal, we first establish a network model and a CR spectrum model to predict the contact duration between vehicles and the probability of spectrum availability. We define the communication link consumption and the weight of channel according to these parameters. Then we transform the optimization objective into a routing scheme with minimizing hop count, subject to constraint on the scheduling of spectrum resource, and moreover prove this routing scheme is NP-hard. To tackle this issue, a hybrid heuristic algorithm is composed by a particle swarm optimization with fast convergence and a genetic algorithm with population diversity. Simulation results demonstrate that our proposal provides better routing hop counts compared with other CR-VANETs protocols.

cognitive radio (CR); vehicular ad hoc networks (VANETs); spectrum scheduling; routing hops; hybrid heuristic algorithm

his PhD degree in computer science from City University of Hong Kong in 2015. Lecturer. His main research interests include distributed systems and wireless networks (tangxing@whut.edu.cn).

2017-06-01；

2017-09-14

國家自然科學基金項目(61772386)；廣東省省級科技計劃項目(2015B010131007)

This work was supported by the National Natural Science Foundation of China (61772386) and the Science and Technology Planning Project of Guangdong Province (2015B010131007).

TP393