車載網(wǎng)(Vehicular Ad hoc Network，VANET)是利用無線連接所形成的車輛通信的集合。在車與車(Vehicle-to-Vehicle，V2V)通信過程中，通過多跳轉(zhuǎn)發(fā)，可在廣泛距離內(nèi)傳遞數(shù)據(jù)包[1]。在VANET中，廣播技術(shù)常用于發(fā)送安全消息、交通信息及娛樂信息等。在設(shè)計(jì)廣播策略時(shí)，應(yīng)考慮無線信道的特性、節(jié)點(diǎn)的快速移動(dòng)性以及網(wǎng)絡(luò)密度信息。每個(gè)節(jié)點(diǎn)依據(jù)自己所處的環(huán)境自主決定是否轉(zhuǎn)發(fā)數(shù)據(jù)包。在高密度網(wǎng)絡(luò)，過多節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包會(huì)導(dǎo)致數(shù)據(jù)包碰撞的概率、提高了傳輸時(shí)延。然而，在低密度網(wǎng)絡(luò)，若沒有充分的節(jié)點(diǎn)參與數(shù)據(jù)包轉(zhuǎn)發(fā)，消息就不能廣泛地傳播。除了考慮網(wǎng)絡(luò)密度外，消息的優(yōu)先級(jí)也是必須考慮的信息之一。例如，緊急消息，如事故預(yù)警，應(yīng)最快地在源節(jié)點(diǎn)的通信范圍內(nèi)傳播。相反，如果是天氣消息，可以容忍大的傳輸時(shí)延。

　　自組織網(wǎng)絡(luò)(Ad hoc)廣播策略主要分為兩類：確定性和隨機(jī)性廣播策略。所謂確定性方案是指在廣播過程中，每個(gè)節(jié)點(diǎn)的行為是可預(yù)測(cè)的。最簡(jiǎn)單的廣播策略就是簡(jiǎn)單泛洪(Simple flooding)。每個(gè)數(shù)據(jù)包僅被每個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)一次。這種方案的不足之處在于可能會(huì)產(chǎn)生過多無用的冗余數(shù)據(jù)包。另一確定性方案就是基于鄰居列表協(xié)議，一跳鄰居列表用于分布式車輛廣播(Distributed Vehicular Broadcast，DV-CAST)，二跳鄰居列表用于可擴(kuò)展廣播算法(Scalable Broadcast Algorithm，SBA)[2]。

　　文獻(xiàn)[3]提出的智能洪泛(Smart-flooding)屬于概率性協(xié)議，每個(gè)節(jié)點(diǎn)包含一些參數(shù)，包括重傳概率和消息重復(fù)的次數(shù)。這類方案是假設(shè)在VANET的稀疏場(chǎng)景，當(dāng)需要發(fā)送數(shù)據(jù)包時(shí)，車輛可能沒有鄰居。因此需要多次發(fā)送數(shù)據(jù)包，并且可利用遺傳算法優(yōu)化這些參數(shù)。

　　為此，針對(duì)VANET的廣播問題，提出新的廣播策略。該廣播策略允許每個(gè)節(jié)點(diǎn)依據(jù)消息的優(yōu)先級(jí)和網(wǎng)絡(luò)密度自主決定是否轉(zhuǎn)發(fā)數(shù)據(jù)包，其目的在于充分、有效地利用無線資源。

1 多路廣播問題

　　在VANET中，廣播問題被認(rèn)為是NP問題。一個(gè)有效的廣播策略不但需要滿足多個(gè)性能指標(biāo)，而且這些性能指標(biāo)是相互抵觸的：(1)將消息傳輸?shù)奖M量多的節(jié)點(diǎn)，并且避免信道的過度使用；(2)盡量高速傳遞數(shù)據(jù)包，并且該速度不影響無線干擾。簡(jiǎn)而言之，處理廣播問題策略是一個(gè)多目標(biāo)優(yōu)化問題。廣播策略需要使用的參數(shù)[4-6]：(1)P：數(shù)據(jù)包的轉(zhuǎn)發(fā)概率。一旦收到廣播數(shù)據(jù)包，每個(gè)節(jié)點(diǎn)依據(jù)轉(zhuǎn)發(fā)概率P決定是否轉(zhuǎn)發(fā)數(shù)據(jù)包；(2)Nr：每個(gè)數(shù)據(jù)包被重復(fù)轉(zhuǎn)發(fā)的次數(shù)。當(dāng)節(jié)點(diǎn)發(fā)送了一個(gè)數(shù)據(jù)包，若在低密度網(wǎng)絡(luò)，覆蓋區(qū)域內(nèi)可能沒有鄰居節(jié)點(diǎn)，因此，需要多次轉(zhuǎn)發(fā)數(shù)據(jù)包[7]；(3)Dr：連續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)包的時(shí)間間隔，且Dr>1。若Dr很短，可能會(huì)導(dǎo)致多個(gè)干擾；若很長(zhǎng)，可能延緩了廣播過程，降低了傳輸效率。因此需要謹(jǐn)慎選擇參數(shù)Dr；(4)TTL：每個(gè)數(shù)據(jù)包的有效期或傳輸?shù)淖畲筇鴶?shù)。用于限制數(shù)據(jù)包的轉(zhuǎn)發(fā)區(qū)域，避免已過期的數(shù)據(jù)包在網(wǎng)絡(luò)中傳輸。

　　1.1 廣播策略的性能評(píng)估指標(biāo)

　　(1)平均碰撞次數(shù)ANC(Average number of collisions)；

　　(2)傳播時(shí)間PT(Propagation Time)。PT是指數(shù)據(jù)包發(fā)送時(shí)刻t1與被接收時(shí)間t2的間隔，即PT=t2-t1；

　　(3)每個(gè)數(shù)據(jù)包被接收的次數(shù)R(Repetitions)；

　　(4)數(shù)據(jù)包接收率FRR(Full Reception Ratio)。FRR用于評(píng)估數(shù)據(jù)包是否被所有節(jié)點(diǎn)接收。

　　據(jù)上述可知，設(shè)計(jì)有效的廣播策略應(yīng)是多目標(biāo)優(yōu)化問題，目的在于求即：

　　1.2 優(yōu)化問題

　　針對(duì)式(1)的優(yōu)化問題，本文利用基于擴(kuò)展算法和仿真的混合優(yōu)化(Hybrid Optimization Platform using Evolu-

　　tionary Algorithm and Simulations，HOPES)平臺(tái)對(duì)參數(shù)P、Nr、Dr、TTL進(jìn)行優(yōu)化。HOPES平臺(tái)由優(yōu)化模塊、網(wǎng)絡(luò)仿真模塊和跟蹤模塊組成[8]，如圖1所示。

　　采用aGAME(adaptive Genetic Algorithm with Multiple parEto sets)[9]作為優(yōu)化工具。在HOPES平臺(tái)中，首先利用aGAME產(chǎn)生可能方案集，然后再將這些方案?jìng)鬏數(shù)骄W(wǎng)絡(luò)仿真模塊內(nèi)，再結(jié)合其他參數(shù)，網(wǎng)絡(luò)仿真模塊產(chǎn)生真實(shí)網(wǎng)絡(luò)的信息。通過仿真，產(chǎn)生跟蹤文件，并將這些跟蹤文件傳輸?shù)礁櫡治瞿K。然后，從跟蹤文件提取信息，并計(jì)算目標(biāo)參量值，形成輸出文件。最后，將跟蹤分析模塊的輸出文件作為優(yōu)化模塊的輸入，進(jìn)而優(yōu)化求解區(qū)域。經(jīng)過多次循環(huán)，直到滿足條件才終止。

　　HOPES整體優(yōu)化過程產(chǎn)生求解方案集，并與不同密度層次網(wǎng)絡(luò)匹配的不同廣播策略，并改變網(wǎng)絡(luò)仿真模塊中參數(shù)以及密度不斷優(yōu)化。值得注意的是，這是一個(gè)離線優(yōu)化過程?？蓪?yōu)化的輸出數(shù)據(jù)建立一個(gè)知識(shí)庫，從而建立了密度層次與廣播策略的連接關(guān)系。因此，每個(gè)車輛依據(jù)網(wǎng)絡(luò)的密度層次選擇合適的廣播策略。

2 自適應(yīng)的魯棒廣播方案

　　2.1 體系結(jié)構(gòu)

　　采用自我管理策略提高Smart flooding的魯棒性。每個(gè)節(jié)點(diǎn)依據(jù)環(huán)境變化自主決定廣播方案。環(huán)境變化包括網(wǎng)絡(luò)的密度層次和消息優(yōu)先級(jí)。為了獲取這些目標(biāo)，提出自治管理的MAPE-K(Monitor Analyze Plan Execute Knowledge)循環(huán)控制結(jié)構(gòu)，如圖2所示。

　　在VANET中，每個(gè)節(jié)點(diǎn)具有關(guān)于網(wǎng)絡(luò)流量信息的監(jiān)控函數(shù)Monitor。在提出的ADM協(xié)議中，Monitor決定接收的數(shù)據(jù)包是否廣播。如果廣播，Monitor提供分析函數(shù)Analyze。Analyze從數(shù)據(jù)包的頭部提取消息的優(yōu)先級(jí)，并且獲取密度層次值，隨后，策劃函數(shù)Plan 利用密度、優(yōu)先級(jí)值，從知識(shí)庫Knowledge 找到相匹配的廣播策略，并產(chǎn)生執(zhí)行函數(shù)Execute，函數(shù)Execute結(jié)合廣播參數(shù)P、Nr、Dr、TTL進(jìn)去修正移動(dòng)節(jié)點(diǎn)的行為。

　　2.2 密度層次估計(jì)

　　在ADM中，節(jié)點(diǎn)依據(jù)所接收的數(shù)據(jù)包的鄰居數(shù)估計(jì)局部密度。在通信過程中，每個(gè)節(jié)點(diǎn)建立鄰居觀察表view。而view依賴于鄰居列表list，鄰居列表list由發(fā)送過或轉(zhuǎn)發(fā)過數(shù)據(jù)包的節(jié)點(diǎn)組成。同時(shí)，每個(gè)節(jié)點(diǎn)保存一個(gè)歷史記錄，該記錄與發(fā)送過或轉(zhuǎn)發(fā)過數(shù)據(jù)包的節(jié)點(diǎn)相聯(lián)系。一旦收到數(shù)據(jù)包的第一次復(fù)本Copy，將節(jié)點(diǎn)的身份以及源節(jié)點(diǎn)的地址信息保存在表內(nèi)的知識(shí)庫，該表被稱為局部view。當(dāng)收到冗余復(fù)本，則將發(fā)送節(jié)點(diǎn)的身份作為列表地址L的下標(biāo)。L被存于局部view表中。每個(gè)地址對(duì)一數(shù)據(jù)只記錄一次。因此，節(jié)點(diǎn)i的節(jié)點(diǎn)鄰居數(shù)Ni等于在L中所有數(shù)據(jù)包被傳輸?shù)钠骄螖?shù)，如式(2)所示。

　　其中，n是數(shù)據(jù)包的個(gè)數(shù)，|L(i)|表示發(fā)送和轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點(diǎn)數(shù)。

　　2.3 優(yōu)先級(jí)

　　在VANET中，不同的消息具有不同的優(yōu)先級(jí)。因此，常在廣播消息中引入優(yōu)先級(jí)[10]。

　　本文將廣播消息分為三級(jí)優(yōu)先級(jí)，并且針對(duì)每級(jí)優(yōu)先級(jí)消息采用不同的廣播策略。

　　(1)最高優(yōu)先級(jí)HPL(High-Priority Level)消息，如安全消息或事故檢測(cè)。這類消息需要快速地傳遞。為此，針對(duì)這些消息，提出的協(xié)議要盡量縮短傳播時(shí)延，并最大化接收率FRR。

　　(2)中度優(yōu)先級(jí)MPL(Medium-priority Level)消息，如道路流量報(bào)告，這些消息不涉及到安全問題。因此，這類消息應(yīng)廣泛在網(wǎng)絡(luò)內(nèi)覆蓋，并減少碰撞次數(shù)。

　　(3)低級(jí)優(yōu)先級(jí)LPL(Low-Priority Level)，如天氣信息、旅游景點(diǎn)廣告等。這類消息為可選消息，優(yōu)先級(jí)最低。

3 仿真以及結(jié)果分析

　　3.1 仿真場(chǎng)景及參數(shù)

　　考慮雙向雙車道路的高速公路，134輛車輛在公路長(zhǎng)為10 km上行駛，車輛間的距離為75 m。這就保證每個(gè)車輛平均有20鄰居。采用NS 2.34作為網(wǎng)絡(luò)仿真工具，并選用Shadowing Pattern Propagation模型。

　　為了分析提出的ADM針對(duì)每個(gè)優(yōu)先級(jí)所對(duì)應(yīng)的參數(shù)P、Nr、Dr、TTL，使用HOPES平臺(tái)。(1)若發(fā)送HPL消息，應(yīng)盡可能快速傳遞消息，并保證網(wǎng)絡(luò)內(nèi)多數(shù)節(jié)點(diǎn)能收到HPL消息；(2)若發(fā)送MPL消息，首先考慮消息到達(dá)率FRR，確保FRR近似為100%；(3)若發(fā)送LPL消息，只有消息能到達(dá)，并且在信道最空閑時(shí)傳輸，相對(duì)應(yīng)的參數(shù)為NC和R。依據(jù)上述原則，針對(duì)每個(gè)優(yōu)先級(jí)所選擇的參數(shù)P、Nr、Dr、TTL，如表1所示。

　　從表1可知，優(yōu)先級(jí)高的HPL消息轉(zhuǎn)發(fā)概率比較大，設(shè)置為0.776，而相應(yīng)地MPL、LPL消息的概率設(shè)置為0.519和0.219。為了避免數(shù)據(jù)包碰撞，提高傳輸效率，將HPL、MPL、LPL消息的Nr分別設(shè)置為1、2、2。相應(yīng)地，HPL消息的Dr為空，因?yàn)槠銷r=1，不存在重傳。MPL、LPL消息的Dr分別為0.951和0.276。而針對(duì)參數(shù)TTL，優(yōu)先級(jí)高的消息有效期應(yīng)該較長(zhǎng)，為此HPL、MPL、LPL消息TTL為26、16、27。之所以LPL消息設(shè)為27，是因?yàn)長(zhǎng)PL消息多數(shù)為娛樂、天氣信息，具有長(zhǎng)的有效期且能使更多人共享。通過仿真獲取了目標(biāo)函數(shù)值，如表2所示，其與表1是相對(duì)應(yīng)的。

　　3.2 性能評(píng)估

　　設(shè)計(jì)ADM方案的目的在于實(shí)現(xiàn)三個(gè)目標(biāo)：(1)快速(Swiftness)，盡可能快速傳遞HPL消息；(2)最大化網(wǎng)絡(luò)覆蓋(Network Coverage)，最大范圍傳遞MPL消息；(3)效率最大化，有效地利用無線信道傳遞LPL消息。即使在交通負(fù)荷增加時(shí)，也應(yīng)滿足上述目標(biāo)。為了更好分析，將提出的ADM與簡(jiǎn)單泛洪(Simple flooding)、智能泛洪(Smart flooding)進(jìn)行比較。

　　在仿真過程中，將源節(jié)點(diǎn)數(shù)目從5變化至30。在10 km的公路上有30個(gè)源節(jié)點(diǎn)意味著消息只需傳遞330 m?？紤]到節(jié)點(diǎn)通信范圍(針對(duì)WiFi廣播消息)，每個(gè)節(jié)點(diǎn)在其信號(hào)覆蓋范圍內(nèi)具有4或5個(gè)鄰居節(jié)點(diǎn)。

　　考慮到傳輸時(shí)間，ADM的目的在于盡可能地快速傳遞HPL消息，即傳播時(shí)間最短。從圖3可知，ADM實(shí)現(xiàn)了此目標(biāo)。與Simple flooding、Smart flooding相比，ADM的傳播時(shí)間短，并且隨源節(jié)點(diǎn)數(shù)目變化的波動(dòng)小。即使30個(gè)源節(jié)點(diǎn)，傳輸HPL消息的平均時(shí)延也小于250 ms，這是可以接受的。因?yàn)樾旭傉咴谑盏骄o急信號(hào)的反應(yīng)時(shí)間為700 ms[11]。

　　從圖4可知，MPL消息的數(shù)據(jù)包傳遞率達(dá)到近100%，極大地降低了數(shù)據(jù)重傳的概率，也減少了干擾。提出的ADM的數(shù)據(jù)包傳遞率優(yōu)于Simple flooding。

　　圖5顯示了通過限制數(shù)據(jù)包重傳的次數(shù)，LPL使用無線信道的情況。從圖5可知，提出的ADM的數(shù)據(jù)包重傳次數(shù)與Smart flooding相近，低于Simple flooding。圖6顯示數(shù)據(jù)包碰撞次數(shù)。從圖6可知，提出的ADM的碰撞次數(shù)顯著低于Smart flooding和Simple flooding。這些數(shù)據(jù)表明提出的ADM能夠有效利用信道資源。

4 總結(jié)

　　VANET經(jīng)常利用廣播傳遞安全、交通、娛樂信息，而每類消息對(duì)廣播策略具有不同的性能要求。為此，本文針對(duì)VANET的廣播問題展開分析。首先依據(jù)消息內(nèi)容的特性，將消息設(shè)為三個(gè)優(yōu)先級(jí)，最高優(yōu)先級(jí)消息、中優(yōu)先級(jí)消息和低優(yōu)先級(jí)消息。然后，將廣播問題看成多目標(biāo)優(yōu)化問題，并采用基于擴(kuò)展算法和仿真的混合優(yōu)化HOPES平臺(tái)優(yōu)化廣播參數(shù)。最后，提出自適應(yīng)的魯棒廣播方案，該方案采用自治管理的MAPE-K循環(huán)控制結(jié)構(gòu)，并根據(jù)網(wǎng)絡(luò)密度和消息的優(yōu)先級(jí)這兩個(gè)參數(shù)選擇廣播策略。仿真結(jié)果表明，與Smart Flooding、Simple Flooding相比，提出的ADM方案表現(xiàn)出良好的性能。

　　參考文獻(xiàn)

　　[1] TONGUZ O K，WISITPONGPHAN N，BAI F.Dv-cast：A distributed vehicular broadcast protocol for vehicular ad hocnetworks[C].IEEE Wireless Commun.，2010，17(2)：47-57.

　　[2] WISITPONGPHAN N，BAI F，MUDALIGE P，et al.Routing  in sparse vehicular ad hoc networks[C].IEEE J.Sel.Areas Commun.，2008，25(8)：43：50.

　　[3] ABDOU W，BLOCH C，CHARLET D，et al.Designing smartadaptive flooding in manet using evolutionary algorithm[C].In 4th Inter. ICST Conf.on MOBILe Wireless Middle WARE，Operating Systems and Applications，2011：71-84.

　　[4] propagation process in multi-lane vehicular ad-hoc networks[C].In Proc.2012 IEEE ICC，2012：708-712.

　　[5] RESTA G，SANTI P，SIMON J.Analysis of multi-hop emer-

　　gency message propagation in vehicular ad hoc networks[C].In Proc.2007 ACM Intl.Symp.Mob.Ad Hoc Netwrk.Comp.，2007：140-149.

　　[6] CAMPOLO C，MOLINARO A，VINEL A，et al.Modeling prioritized broadcasting in multichannel vehicular networks[C].IEEE Trans.Veh.Technol.，2012，61(2)：23-35.

　　[7] VINEL A，CAMPOLO C，PETIT J，et al.Trustworthy broad-casting in IEEE 802.11 p/WAVE vehicular networks: delayanalysis[C].IEEE Commun.Lett.，2011，15(9)：1010-1012.

　　[8] HAN Y，LA R，MAKOWSKI A，et al.Distribution of path durations in mobile ad-hoc networks—Palm’s Theorem to the rescue[C].Computer Networks，2006，50(12)：1887-1900.

　　[9] YOO J，CHOI S，KIM C K.The capacity of epidemic routing in vehicular networks[C].IEEE Commun.Lett.，2009，13(6)：459-461.

　　[10] SUTHAPUTCHAKUN C，GANZ A.Priority based inter-vehicle communication in vehicular ad-hoc networks using ieee 802.11e[C].In VTC Spring.IEEE，2007：2595-2599.

　　[11] MA X，ZHANG J，YIN X，et al.Design and analysis of a robust broadcast scheme for vanet safety-related services[C].IEEE T.Vehicular Technology，2012，61(1)：46-61.