0 引言

　　車(chē)載自組網(wǎng)(VANET)作為智能交通系統(tǒng)(ITS)的重要組成部分引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注[1]。且隨著無(wú)線射頻收發(fā)器硬件成本的降低，采用多射頻多信道的車(chē)載自組織網(wǎng)絡(luò)在未來(lái)具有很大的發(fā)展?jié)摿Α?a class="innerlink" href="http://theprogrammingfactory.com/tags/多接口" title="多接口" target="_blank">多接口VANET中一個(gè)關(guān)鍵問(wèn)題就是頻譜的動(dòng)態(tài)分配。對(duì)于車(chē)載網(wǎng)絡(luò)，美國(guó)聯(lián)邦通信委員會(huì)(FCC)將5.850~5.925 GHz之間75 MHz的頻段用于車(chē)載通信，其被分成7個(gè)子信道[2]。通過(guò)對(duì)車(chē)載自組網(wǎng)中有限的頻譜資源進(jìn)行動(dòng)態(tài)分配，從而降低了車(chē)輛節(jié)點(diǎn)由于競(jìng)爭(zhēng)信道資源而產(chǎn)生的沖突，提高了車(chē)載網(wǎng)絡(luò)的吞吐性能，因此，研究多接口多信道VANET動(dòng)態(tài)頻譜分配算法具有重要意義。

1 相關(guān)工作

　　車(chē)載自組織網(wǎng)絡(luò)拓?fù)漕l繁變化，導(dǎo)致固定頻譜分配技術(shù)不能用于車(chē)載網(wǎng)絡(luò)。于是人們開(kāi)始考慮對(duì)頻譜進(jìn)行動(dòng)態(tài)分配。

　　文獻(xiàn)[3]是一種集中式頻譜分配方案，認(rèn)為頻譜分配問(wèn)題就是尋求在射頻數(shù)目受限的前提條件下最小化網(wǎng)絡(luò)干擾函數(shù)的問(wèn)題，頻譜分配集中控制設(shè)備可能成為計(jì)算瓶頸，且算法復(fù)雜度高，在車(chē)載自組網(wǎng)中難以實(shí)現(xiàn)。文獻(xiàn)[4]是一種集中式頻譜分配方案，提出了CSGC算法。它是一種以最大化系統(tǒng)總帶寬為目標(biāo)的顏色敏感圖論著色算法。但是實(shí)現(xiàn)時(shí)迭代次數(shù)多，且隨著主用戶和次用戶數(shù)目的增多導(dǎo)致系統(tǒng)規(guī)模增大，其分配效率也會(huì)降低。文獻(xiàn)[5]是一種分布式頻譜分配方案，提出了RAND算法。它是一種分布式隨機(jī)化算法。各用戶對(duì)其可用的信道產(chǎn)生一個(gè)隨機(jī)數(shù)，通過(guò)與其他用戶比較隨機(jī)數(shù)大小而決定信道的分配，但是在系統(tǒng)總帶寬性能上，較其他算法差距較大。

　　本文針對(duì)有限的頻譜資源中車(chē)輛用戶抓住機(jī)會(huì)使用空閑信道問(wèn)題，在圖論著色算法模型的基礎(chǔ)上，提出了一種基于信道反饋的動(dòng)態(tài)頻譜分配算法（Channel Feedback Spectrum Allocation，CFSA)，其是一種分布式實(shí)現(xiàn)的算法，有效解決了上述三種方案運(yùn)用在車(chē)載自組網(wǎng)中的不足之處，經(jīng)過(guò)仿真分析，性能明顯優(yōu)于上述方案。

2 模型描述

　　動(dòng)態(tài)頻譜分配問(wèn)題的基本出發(fā)點(diǎn)是：在不影響授權(quán)頻段的正常通信下，具有認(rèn)知功能的無(wú)線通信設(shè)備可以按照某種“機(jī)會(huì)方式”接入授權(quán)的頻段范圍，并動(dòng)態(tài)地利用頻譜。整個(gè)頻譜池又可劃分為若干個(gè)子信道。圖1描述了一個(gè)瞬時(shí)的頻譜池，它反應(yīng)了車(chē)載自組網(wǎng)中車(chē)輛用戶在某一時(shí)段可利用頻譜的特征。

　　多接口車(chē)載自組網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是動(dòng)態(tài)變化的，為方便算法描述，作如下假設(shè)：

　　(1)上述頻譜池中可用頻譜被劃分成K個(gè)可用頻譜帶，即K個(gè)信道。每個(gè)信道的帶寬和傳輸范圍相同，且相互正交。

　　(2)系統(tǒng)中隨機(jī)分布著M個(gè)車(chē)輛節(jié)點(diǎn)，對(duì)?坌m，m∈M配備有不同的射頻數(shù)目，令Mi表示節(jié)點(diǎn)i的射頻數(shù)目，系統(tǒng)中車(chē)輛節(jié)點(diǎn)在滿足信道分配規(guī)則的前提下，可以同時(shí)使用多個(gè)信道K，且滿足Mi≤K。

　　(3)對(duì)于需要通信的車(chē)輛節(jié)點(diǎn)，通信雙方必須各自選擇一個(gè)射頻接口，并且使雙方的射頻接口切換到相同的信道上。

　　(4)本文不考慮功率控制因素，假設(shè)所有的車(chē)輛用戶都使用相同的功率，且每個(gè)車(chē)輛節(jié)點(diǎn)在各個(gè)信道上的干擾半徑相同。

　　由于圖的著色算法已經(jīng)被廣泛地應(yīng)用于頻譜的動(dòng)態(tài)分配上，它是一種成熟的模型。因此圖論著色模型的數(shù)學(xué)定義可以由距離矩陣、空閑矩陣、干擾矩陣、有效分配矩陣表示。

　　矩陣D為距離矩陣，用于描述車(chē)載自組網(wǎng)中車(chē)輛節(jié)點(diǎn)之間的距離，其是一個(gè)M×M矩陣，其定義如式(1)所示：

　　D={dij|dij=||i(xi，yj)-j(xi，yj)||，i，j=1，…M}(1)

　　其中，dij為車(chē)輛節(jié)點(diǎn)i與j之間的距離。

　　矩陣L為空閑矩陣，其是一個(gè)M×K矩陣，表征信道有效性。代表車(chē)輛節(jié)點(diǎn)是否可用該信道，如果車(chē)輛節(jié)點(diǎn)m可以用k信道，則lm，k=1，否則lm，k=0。如式(2)所示：

　　L={lm，k|lm，k∈{0，1}}M×K(2)

　　矩陣B為干擾矩陣，其是一個(gè)M×M×K矩陣，代表車(chē)輛節(jié)點(diǎn)i和車(chē)輛節(jié)點(diǎn)j在信道k上存在干擾。如式(3)所示：

　　B={?姿l，j，k|i，j=1，…，M，k=1，…，K}M×M×K(3)

　　這些干擾是特定的，兩個(gè)車(chē)輛節(jié)點(diǎn)在一個(gè)信道上是否相互干擾取決于它們之間的距離，不代表在另一個(gè)信道上仍受干擾。

　　矩陣S為有效分配矩陣，它是一個(gè)M×K矩陣，如果信道k分配給了車(chē)輛節(jié)點(diǎn)m，則Sm，k=1，否則Sm，k=0。如式(4)所示：

　　S={sm，k|m=1，…，M，k=1，…，K}M×K(4)

　　其中S滿足所有干擾矩陣Λ定義的限制條件，Si，k＋Sj，k≤1，如果?姿i，j，k=1，當(dāng)且僅當(dāng)?坌i，j<M，k<K?？梢灾?，滿足上述條件的S矩陣很多，故令QM×K代表有效頻譜分配矩陣集。

3 動(dòng)態(tài)頻譜分配算法設(shè)計(jì)

　　車(chē)載自組網(wǎng)中車(chē)輛與車(chē)輛之間的拓?fù)渥兓芸?，使得通信鏈路不能及時(shí)建立。而車(chē)輛節(jié)點(diǎn)在選擇可用頻段時(shí)，必須有一個(gè)衡量標(biāo)準(zhǔn)作為選擇的依據(jù)。本文提出的CFSA算法，根據(jù)信道反饋的實(shí)時(shí)性從而實(shí)現(xiàn)頻譜合理有效的分配。

　　3.1 車(chē)輛射頻接口狀態(tài)

　　所有車(chē)輛節(jié)點(diǎn)的射頻數(shù)目是不確定的，為了充分利用頻譜資源，本文首先為射頻接口定義了三種狀態(tài)。

　　(1)忙狀態(tài)。如果該射頻正在發(fā)送業(yè)務(wù)，稱(chēng)該射頻在忙狀態(tài)。

　　(2)空閑狀態(tài)。如果該射頻沒(méi)有發(fā)送業(yè)務(wù)，稱(chēng)該射頻處在空閑狀態(tài)。

　　(3)假空閑狀態(tài)。如果一個(gè)射頻接口正在發(fā)送業(yè)務(wù)，但車(chē)輛節(jié)點(diǎn)通過(guò)空閑時(shí)的監(jiān)測(cè)得知該射頻當(dāng)前工作的信道反饋值小于設(shè)置的信道反饋閾值CFT(Channel Feedback Threshold)，而此時(shí)節(jié)點(diǎn)又沒(méi)有其他空閑的射頻，為了保證通信業(yè)務(wù)的質(zhì)量，假設(shè)該射頻目前處于空閑狀態(tài)。

　　3.2 信道反饋

　　確定了車(chē)輛節(jié)點(diǎn)的射頻接口狀態(tài)，為方便算法描述，建立如下結(jié)構(gòu)。

　　(1)將上述圖論模型的數(shù)學(xué)描述抽象成一個(gè)無(wú)向圖G=(V，E，L1)，如圖2所示。其中，V={vm|m=1，…，M}表示頂點(diǎn)的集合，每個(gè)頂點(diǎn)代表參與信道分配的車(chē)輛用戶，包括車(chē)輛節(jié)點(diǎn)當(dāng)前可用信道的集合；E={eij|i，j=1，…，M}表示邊的集合，代表相鄰兩個(gè)車(chē)輛節(jié)點(diǎn)在某一個(gè)信道k上存在干擾。因已假設(shè)了各車(chē)輛用戶在各個(gè)信道上的干擾半徑相同，若車(chē)輛i，j的干擾范圍不出現(xiàn)重疊，則eij=0，否則eij=1；而L1表示車(chē)輛頂點(diǎn)可選信道顏色的集合，每個(gè)可用信道被看作不同的顏色，可選顏色由信道有效矩陣L決定，當(dāng)且僅當(dāng)lm，k=1時(shí)，車(chē)輛節(jié)點(diǎn)可以使用當(dāng)前被著色的信道。

　　(2)由于信道k在某一時(shí)段可能被不同的車(chē)輛用戶占用，即一個(gè)信道上的車(chē)輛鄰居數(shù)目是不定的，如果按照文獻(xiàn)[3]中CSGC算法進(jìn)行頻譜分配，就會(huì)增加無(wú)線控制信道的流量。因此本文考慮信道反饋因素，定義了信道反饋矩陣，將可用信道分配給吞吐量利用率最大的車(chē)輛用戶。

　　矩陣R為信道反饋矩陣，它是一個(gè)M×K階矩陣，用來(lái)描述各車(chē)輛節(jié)點(diǎn)在給定的頻譜分配條件下，車(chē)輛用戶在可用信道上所獲得的最大通信容量，可以是最大帶寬或者最大吞吐量。其公式如式(5)所示：

　　R={rm，k|m=1，…，M，k=1，…，K}(5)

　　信道反饋矩陣R中各元素的取值采用文獻(xiàn)[6]中的方法進(jìn)行計(jì)算，其目標(biāo)就是最大化信道吞吐量，其公式如式(6)所示：

　　其中bm，k表示車(chē)輛用戶m在信道k上能夠產(chǎn)生的最大帶寬，Cm，k為車(chē)輛用戶m在信道k上的鄰居數(shù)目。根據(jù)信道反饋矩陣的值，當(dāng)信道吞吐量最大時(shí)，其信道k即為當(dāng)前車(chē)輛用戶選擇的最優(yōu)信道。

　　(3)針對(duì)車(chē)載自組網(wǎng)的時(shí)變特性，網(wǎng)絡(luò)拓?fù)浜托诺赖目捎眯跃S著時(shí)間不停地變化著，為了使每個(gè)可用信道的吞吐量達(dá)到最大，在頻譜分配時(shí)定義了最大化帶寬準(zhǔn)則，如式(7)所示：

　　其中sm，k為有效分配矩陣，bm，k為車(chē)輛用戶m在信道k上產(chǎn)生的帶寬。

　　上述算法的主要思想是在滿足干擾條件的前提下，利用現(xiàn)有的圖論著色模型，提出信道反饋的概念，讓車(chē)輛用戶根據(jù)信道反饋的值來(lái)進(jìn)行信道選擇。其目標(biāo)就是使車(chē)輛用戶最大公平地接入信道，獲得最大的帶寬。

　　3.3 算法實(shí)現(xiàn)流程

　　算法的初次分配流程與文獻(xiàn)[3]中CSGC算法類(lèi)似，算法每次迭代將選出擁有最大信道反饋值的車(chē)輛用戶，其算法流程圖如圖3所示。

　　CFSA頻譜分配算法流程圖如圖3所示，核心思想就是優(yōu)先選出最有價(jià)值的信道分配給車(chē)輛節(jié)點(diǎn)，即讓吞吐量利用率最大的車(chē)輛用戶接入該信道。

4 仿真與分析

　　為了驗(yàn)證算法的有效性，本文利用MATLAB對(duì)算法進(jìn)行仿真，并針對(duì)VANET網(wǎng)絡(luò)中頻譜分配算法的時(shí)間開(kāi)銷(xiāo)、系統(tǒng)最大收益和其他常用算法進(jìn)行比較。

　　4.1 仿真場(chǎng)景

　　本文的模擬場(chǎng)景是在800 m×800 m的矩形區(qū)域中隨機(jī)分布5~40個(gè)車(chē)輛節(jié)點(diǎn)，車(chē)輛節(jié)點(diǎn)均配備8個(gè)射頻接口，信道數(shù)為20，車(chē)輛通信半徑為100 m，干擾半徑為300 m，具體仿真參數(shù)如表1所示。

　　4.2 性能比較與結(jié)果分析

　　圖4可以看出，當(dāng)頻譜數(shù)量固定時(shí)，取k=20，可以看出CSGC的時(shí)間開(kāi)銷(xiāo)最大，并且隨著車(chē)輛節(jié)點(diǎn)數(shù)量的增多，本文提出的CFSA算法在時(shí)間開(kāi)銷(xiāo)上明顯小于CSGC算法和RAND算法。由于本文提出的算法是在CSGC算法初次分配的基礎(chǔ)之上繼續(xù)分配，以兼顧系統(tǒng)最大吞吐量換取了時(shí)間開(kāi)銷(xiāo)的減少，圖5表示CFSA算法在系統(tǒng)總收益上明顯高于CSGC算法和RAND算法。

5 結(jié)束語(yǔ)

　　本文提出的一種基于信道反饋的動(dòng)態(tài)頻譜分配算法CFSA，讓車(chē)輛用戶根據(jù)反饋矩陣的值來(lái)最優(yōu)選擇信道，解決了CSGC分配算法只是針對(duì)靜態(tài)網(wǎng)絡(luò)的問(wèn)題，最后對(duì)CFSA算法進(jìn)行了仿真和分析。仿真結(jié)果表明，CFSA算法在兼顧系統(tǒng)總收益的基礎(chǔ)上減少了時(shí)間開(kāi)銷(xiāo)，降低了算法運(yùn)行的迭代次數(shù)，顯著提高了網(wǎng)絡(luò)的性能。

　　參考文獻(xiàn)

　　[1] 羅濤，王昊.車(chē)載無(wú)線通信網(wǎng)絡(luò)及其應(yīng)用[J].中興通訊技術(shù)，2011，17(3)：1-7.

　　[2] KAKARLA J，SATHYA S S.A survey and qualitative anal-ysis of multi-channel MAC protocols for VANET[J].Inter-national Journal of Computer Applications，2012，38(6)：38-42.

　　[3] SUBRAMANIAN A P，GUPTA H，DAS S.Minimum interfer-ence channel assignment in multi-radio wireless mesh net-woks[EB/OL].(2008-06-18)[2013-06-12].http：//www.cs.sunysb.edu/~hgupta/ps/channel.pdf.

　　[4] Zheng Haitao，Peng Chunyi.Utilization and fairness in oppor-tunistic spectrum access[C].IEEE International Conference on Communications(ICC)，2006，11：555-576.

　　[5] WANG W，LIU X.List-Coloring based channel allocation for open-spectrum wireless networks[C].IEEE Communica-tions Society Press，2005：690-694.

　　[6] ZHENG H，PENG C.Collaboration and fairness in opportunistic spectrum access[C].IEEE Communications Society Press，2005：3132-3136.

　　[7] 陳劼，李少謙，廖楚林.認(rèn)知無(wú)線電網(wǎng)絡(luò)中基于需求的頻譜資源分配算法研究[J].計(jì)算機(jī)應(yīng)用，2008，28(9)：2188-2191.