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

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

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

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

1 多路廣播問題

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

　　1.1 廣播策略的性能評估指標

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

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

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

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

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

　　1.2 優(yōu)化問題

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

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

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

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

2 自適應的魯棒廣播方案

　　2.1 體系結構

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

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

　　2.2 密度層次估計

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

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

　　2.3 優(yōu)先級

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

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

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

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

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

3 仿真以及結果分析

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

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

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

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

　　3.2 性能評估

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

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

　　考慮到傳輸時間，ADM的目的在于盡可能地快速傳遞HPL消息，即傳播時間最短。從圖3可知，ADM實現(xiàn)了此目標。與Simple flooding、Smart flooding相比，ADM的傳播時間短，并且隨源節(jié)點數(shù)目變化的波動小。即使30個源節(jié)點，傳輸HPL消息的平均時延也小于250 ms，這是可以接受的。因為行駛者在收到緊急信號的反應時間為700 ms[11]。

　　從圖4可知，MPL消息的數(shù)據(jù)包傳遞率達到近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 總結

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