張滬寅 王 菁 唐 星

1(武漢大學(xué)計(jì)算機(jī)學(xué)院 武漢 430072)2(武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 武漢 430070)

(zhy2536@whu.edu.cn)

認(rèn)知無線車載自組織網(wǎng)絡(luò)中的聯(lián)合路由調(diào)度

張滬寅1王 菁1唐 星2

1(武漢大學(xué)計(jì)算機(jī)學(xué)院 武漢 430072)2(武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 武漢 430070)

(zhy2536@whu.edu.cn)

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

認(rèn)知無線電；車載自組織網(wǎng)絡(luò)；頻譜調(diào)度；路由跳數(shù)；混合啟發(fā)式算法

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

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

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

目前針對CR-VANETs的路由研究相對較少，已有的少數(shù)研究旨在單一優(yōu)化路由的端到端時延或者鏈路持續(xù)時間.然而，在CR-VANETs的路由設(shè)計(jì)中，如何最大效率地利用有限CR頻譜資源，是需要研究的問題之一.而現(xiàn)有的路由研究并未將CR頻譜資源調(diào)度作為衡量通信鏈路質(zhì)量的參數(shù)，用于路由方案的設(shè)計(jì)中.此外，在多跳無線網(wǎng)絡(luò)中，過多的跳數(shù)僅能在“能量有限”的約束環(huán)境中起到一定的作用.因?yàn)榭朔胍羰沁@種網(wǎng)絡(luò)環(huán)境需要關(guān)注的首要問題.而在“帶寬有限”的約束環(huán)境中，當(dāng)信噪比高，由于使用了額外的時隙，過多的跳數(shù)則會降低端到端吞吐量[8].在CR-VANETs中，由于車載供能使得信號發(fā)射能量不再有限制.因此，對于有限的CR頻譜資源，過多的路由跳數(shù)會消耗CR信道切換帶寬，導(dǎo)致頻譜資源浪費(fèi).尤其當(dāng)車輛密度較大可能出現(xiàn)擁塞時，過多的路由跳數(shù)還會使路由開銷增大，進(jìn)一步加重?fù)砣?

在本文中，區(qū)別于現(xiàn)有的CR-VANETs路由研究以及我們前期的研究目標(biāo)[9]，設(shè)計(jì)了一種聯(lián)合路由調(diào)度方案，將CR頻譜資源調(diào)度作為影響通信鏈路質(zhì)量的參數(shù)，同時最大限度地減少網(wǎng)絡(luò)中的路由跳數(shù).本文的主要貢獻(xiàn)有4點(diǎn)：

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

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

3) 針對這個聯(lián)合路由調(diào)度問題，我們提出了一種混合啟發(fā)式算法，結(jié)合了粒子群優(yōu)化算法的快速收斂性和遺傳算法的種群多樣性，在對有限CR頻譜資源調(diào)度的同時進(jìn)行路由跳數(shù)優(yōu)化.

4) 仿真實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的CR-VANETs路由研究比較，我們的優(yōu)化方案有著更優(yōu)的路由跳數(shù)并使其保持在一個相對穩(wěn)定的值.

1 CR-VANETs背景知識

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

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

不同于傳統(tǒng)CR網(wǎng)絡(luò)，車輛的高速移動性使得CR-VANETs網(wǎng)絡(luò)拓?fù)涫且粋€動態(tài)結(jié)構(gòu).而不同于傳統(tǒng)VANETs，在CR-VANETs中頻譜的動態(tài)特性使得頻譜空洞可能在時間和空間上均發(fā)生變化.這些特性使得CR-VANETs中的頻譜感知和頻譜接入問題極具挑戰(zhàn)性.為了解決這些問題，近年來，一些學(xué)者對CR-VANETs中的頻譜感知、接入、管理等問題進(jìn)行了深入研究[15-18].一方面，這些文獻(xiàn)指出高速運(yùn)動的車輛具有較好的時空分集特性.在CR-VANETs中，采用協(xié)作感知的方法能夠獲得更好的頻譜感知參數(shù)，充分利用車輛的時空分集特性能夠獲得更好的頻譜檢測性能.另一方面，這些文獻(xiàn)基于車輛位置預(yù)測和頻譜地理數(shù)據(jù)庫查詢的方法，讓車輛快速和準(zhǔn)確地獲得當(dāng)前位置以及將來位置的可用頻譜信息.這些工作通過理論和仿真實(shí)驗(yàn)論證了在CR-VANETs中，所提方法能夠保證高速運(yùn)動環(huán)境下CR信道檢測的準(zhǔn)確性和及時性.

2 相關(guān)工作

2.1CRAHNs和VANETs中的路由研究

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

然而，上述這些路由協(xié)議無法直接用于CR-VANETs環(huán)境中.一方面是由于車輛的高速移動，使得車對車通信處在一個高速動態(tài)特性的網(wǎng)絡(luò)拓?fù)渲校涣硪环矫?，CR頻譜的可用性不僅會根據(jù)PUs的活動發(fā)生變化，還會根據(jù)SUs的活動呈現(xiàn)持續(xù)變化的特性.本文在設(shè)計(jì)CR-VANETs路由方案時，將車輛間的有效接觸時間以及CR頻譜的可用性均列入了路由設(shè)計(jì)的考慮因素.

2.2CR-VANETs中的路由研究

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

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

然而，上述文獻(xiàn)的路由方案均未從CR頻譜資源調(diào)度方面進(jìn)行考慮，也未針對路由跳數(shù)進(jìn)行研究和優(yōu)化.基于目前還沒有針對CR-VANETs中頻譜調(diào)度和路由跳數(shù)優(yōu)化的研究，本文提出了一種聯(lián)合路由調(diào)度方案，通過混合啟發(fā)式算法，將CR頻譜資源調(diào)度作為影響通信鏈路質(zhì)量的參數(shù)，同時最大限度地減少網(wǎng)絡(luò)中的路由跳數(shù).

3 系統(tǒng)模型及問題描述

3.1網(wǎng)絡(luò)模型

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

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

(1)

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

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

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

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

其中,t和tq是連續(xù)時間變量.

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

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

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

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

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

通過對歷史頻譜感知圖的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，以及對具有相同信道狀態(tài)轉(zhuǎn)移矩陣的信道進(jìn)行先驗(yàn)預(yù)測，車輛Vi在路段Sl里，CR信道可用概率可計(jì)算為[29]

(2)

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

其中，c為反比例常數(shù).

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

3.3聯(lián)合路由調(diào)度問題

在CR-VANETs系統(tǒng)中，有V輛車、S個路段以及k個不同的CR信道狀態(tài).我們優(yōu)化的目標(biāo)為有限CR頻譜資源調(diào)度，同時最小化路由跳數(shù).

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

此外，我們可以將最小化路由跳數(shù)問題視為一個路由選路的問題，即在此系統(tǒng)中，消息盡其可能通過最少的中繼節(jié)點(diǎn)來實(shí)現(xiàn)從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的轉(zhuǎn)發(fā).因此，我們的聯(lián)合路由調(diào)度問題可以轉(zhuǎn)化為：在有限CR頻譜資源約束下，最小化路由跳數(shù)的路由問題.

我們定義節(jié)點(diǎn)Vi的可達(dá)鄰居子圖為Gi(Vi,Ei)，并在其中構(gòu)建最小生成樹.然后，我們用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，其權(quán)值用所有邊權(quán)重的和來表示.我們定義F(xV)為路由跳數(shù)，則我們的優(yōu)化目標(biāo)可被描述為

R*=arg minRF(xV)，

(3)

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

4 混合啟發(fā)式算法

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

4.1粒子群優(yōu)化算法

首先，我們引入帶有慣性權(quán)重的粒子群優(yōu)化算法，其數(shù)學(xué)表達(dá)式為

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維分量.α和β為隨機(jī)數(shù);c1和c2為加速因子;w為慣性權(quán)重.

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

算法1. PRUFER編碼算法.

輸入：生成樹D;

輸出：相應(yīng)PRUFER編碼.

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

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

③else

④forall生成樹D中的葉子節(jié)點(diǎn)do

⑤ 將葉子節(jié)點(diǎn)中標(biāo)號最小的節(jié)點(diǎn)編號標(biāo)

記為σ；

⑥ifμ是與σ相鄰的節(jié)點(diǎn)編號then

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

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

⑨ 樹的頂點(diǎn)數(shù)為n-1個；

⑩endif

算法2. PRUFER解碼算法.

輸入：相應(yīng)PRUFER編碼Q;

輸出：生成樹D.

①ifQ=?then

③ 構(gòu)成的樹就是與最初Q所對應(yīng)的生成樹，輸出生成樹；

④else

⑦ 將最小的數(shù)字標(biāo)記為σ，Q中最左端的數(shù)字為μ；

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

⑩ifμ 不再出現(xiàn)在Q中then

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

Fig. 3 Spanning tree and Prufer number圖3 生成樹與對應(yīng)的Prufer數(shù)編碼

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

).

(6)

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

證畢.

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

4.2HTH路由算法

(7)

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

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

(8)

(9)

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

Fig. 4 Two point hybridization of particles圖4 粒子的雙點(diǎn)雜交示意圖

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

(10)

在搜索過程中，為了提高算法的搜索效率，將參數(shù)調(diào)整如下：

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為種群最大的進(jìn)化代數(shù)；mgen為種群當(dāng)前的進(jìn)化代數(shù).

CR-VANETs中的任意節(jié)點(diǎn)Vi根據(jù)局部信息，運(yùn)行HTH算法偽代碼如下：

算法3. HTH算法.

輸入：原始的局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖Gi(Vi,Ei)、節(jié)點(diǎn)的最大通信范圍;

輸出：節(jié)點(diǎn)Vi的本地節(jié)點(diǎn)約束最小生成樹.

① 初始化種群X以及相應(yīng)的參數(shù)，如種群規(guī)模popsize，進(jìn)化代數(shù)gen，w，c1和c2等；

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

③forall種群中的粒子do

④ 進(jìn)行粒子位置的更新；

⑤ifXi不滿足節(jié)點(diǎn)度約束條件then

⑥ 進(jìn)行約束滿足調(diào)整；

⑦endif

⑧ 對粒子的適應(yīng)度進(jìn)行評價；

⑨ 更新粒子自身的最優(yōu)位置pBesti；

⑩ 更新種群的全局最優(yōu)位置gBest；

通過這個混合啟發(fā)式算法，我們采用了最小生成樹的拓?fù)湔{(diào)節(jié)思路，通過對粒子的適應(yīng)度進(jìn)行評價，對加速因子和慣性權(quán)重進(jìn)行調(diào)整，得出問題的全局最優(yōu)解，即選出跳數(shù)最少的路由方案.

5 實(shí)驗(yàn)與結(jié)果

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

5.1仿真設(shè)置

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

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

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

Table 1 Simulation Parameters

5.2仿真結(jié)果

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

圖5顯示了在不同車輛密度下，上述5種路由方案的平均跳數(shù)值.當(dāng)車輛密度增大時，這5種路由方案的平均跳數(shù)值都有所增加.這是因?yàn)椋S著車輛的增多，可以作為中繼節(jié)點(diǎn)的候選車輛節(jié)點(diǎn)數(shù)量也隨之增多，每個包的傳輸機(jī)會隨著車與車的接觸增多也相應(yīng)增大.為了各自的優(yōu)化目標(biāo)，這5種路由方案都會為了完成優(yōu)化目標(biāo)而改變包的傳輸路徑，從而導(dǎo)致了路由跳數(shù)的增加.

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

HTH算法在每個密度點(diǎn)的跳數(shù)均值都優(yōu)于其他路由方案，并且其平均跳數(shù)值保持在一個相對較小的波動范圍內(nèi).在相對密集的網(wǎng)絡(luò)環(huán)境中，SSR路由方案的平均跳數(shù)略有減少，這是由于在其優(yōu)化轉(zhuǎn)發(fā)過程中，為了避免開銷過大會對路由開銷進(jìn)行約束，從而導(dǎo)致了路由跳數(shù)減小.在相對稀疏的網(wǎng)絡(luò)中，EPDM-R路由方案的平均跳數(shù)值也相對較小.但隨著車輛密度的增大，中繼節(jié)點(diǎn)增多，基于從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由持續(xù)時間最大化優(yōu)化目標(biāo)導(dǎo)致了該方案路由跳數(shù)的增加.CoRoute路由方案的平均跳數(shù)值隨車輛節(jié)點(diǎn)的增加而增幅最大.這是因?yàn)樵贑oRoute路由方案中，最小化端到端延時是其優(yōu)化目標(biāo)，當(dāng)出現(xiàn)了路徑更短的中繼節(jié)點(diǎn)時，此節(jié)點(diǎn)便立即成為下一跳目標(biāo).這就導(dǎo)致當(dāng)車輛節(jié)點(diǎn)增多時，候選節(jié)點(diǎn)的增多帶來了路由跳數(shù)的增加.

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

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

在大多數(shù)密度節(jié)點(diǎn)下，HTH路由方案取得了比其他路由方案更高的投包率.這是由于在HTH路由方案中，將CR頻譜資源調(diào)度作為衡量通信鏈路質(zhì)量的參數(shù)，將通信鏈路消耗作為有限頻譜CR頻譜資源約束條件，從而提高了CR頻譜資源效用，獲得了較高的投包率.在車輛密度增長到250節(jié)點(diǎn)后，HTH路由方案的投包率呈現(xiàn)增長平緩的趨勢.這是因?yàn)镠TH路由方案聯(lián)合了最小化路由跳數(shù)的優(yōu)化目標(biāo)，使其在節(jié)點(diǎn)密度大的環(huán)境中，權(quán)衡了優(yōu)化目標(biāo)和約束條件這兩者之間的關(guān)系.在車輛到達(dá)300的最大密度節(jié)點(diǎn)時，由于EPDM-R路由方案的優(yōu)化目標(biāo)為路由持續(xù)時間最大化，因此表現(xiàn)的更佳.

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

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

圖8顯示了在不同車輛密度下HTH路由方案的平均跳數(shù)值.當(dāng)CR信道帶寬較小時，平均路由跳數(shù)相對較大.當(dāng)CR信道帶寬增加到一定值時，平均路由跳數(shù)則不再受到CR信道帶寬的顯著影響.這是因?yàn)椋ㄟ^使用額外的CR信道帶寬，一定程度上降低了DSRC信道擁塞，從而減少了路由跳數(shù).此外，CR信道空閑帶寬越大，其信道可用概率就越高，包傳輸?shù)目煽啃詣t越高.當(dāng)CR信道帶寬超過一定的閾值時，路由平均跳數(shù)受信道帶寬的影響則相對較小.

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

6 結(jié)束語

本文研究了一個CR-VANETs中聯(lián)合CR頻譜資源調(diào)度和最小化路由跳數(shù)的問題.為解決這個問題，我們建立了CR-VANETs中的網(wǎng)絡(luò)模型以及基于V2V通信的CR頻譜模型，用于預(yù)測車輛間有效接觸時間，并得出CR頻譜可用概率.通過這些參數(shù)，我們定義了網(wǎng)絡(luò)拓?fù)渲械耐ㄐ沛溌废?，并將這個鏈路消耗作為CR頻譜資源調(diào)度的權(quán)重因子.我們將這個聯(lián)合路由調(diào)度問題轉(zhuǎn)化為有限CR頻譜資源約束下的路由跳數(shù)優(yōu)化問題，并證明該問題為節(jié)點(diǎn)約束最小生成樹的NP難問題.我們通過粒子群優(yōu)化算法和遺傳算法相結(jié)合的混合啟發(fā)式算法，找出CR頻譜資源效用大的路由路徑，然后基于這個給定備選路徑，我們選出跳數(shù)最少的路由方案.仿真實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的CR-VANETs路由研究比較，我們的方案有著更優(yōu)的路由跳數(shù)并使其保持在一個相對穩(wěn)定的值.

[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)(謝永, 吳黎兵, 張宇波, 等. 面向車聯(lián)網(wǎng)的多服務(wù)器架構(gòu)的匿名雙向認(rèn)證與密鑰協(xié)商協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展, 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)(劉冰藝, 吳黎兵, 賈東耀, 等. 基于移動云服務(wù)的車聯(lián)網(wǎng)數(shù)據(jù)上傳策略[J]. 計(jì)算機(jī)研究與發(fā)展, 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

國家自然科學(xué)基金項(xiàng)目(61772386)；廣東省省級科技計(jì)劃項(xiàng)目(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