VANET中一種基于多目標優化的自適應廣播方案*

胡 亦，王琳娜，朱恭生

(北京電子科技職業學院 電信工程學院，北京100015)

VANET中一種基于多目標優化的自適應廣播方案*

胡 亦，王琳娜，朱恭生

(北京電子科技職業學院 電信工程學院，北京100015)

針對車載網VANET(Vehicular Ad hoc Network)中的廣播策略，提出新穎的自動分發方案(Autonomic Dissemination Method，ADM)。通過ADM傳輸消息，自適應網絡的密度和消息的優先級變化。在實施ADM過程中，采用兩個步驟：離線優化過程和在線適應網絡特性。仿真結果表明，提出的ADM方案在消息傳遞率、傳輸時延和干擾方面得到提高。

廣播；優先級；網絡密度；優化；車載網

0 引言

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

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

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

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

1 多路廣播問題

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

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

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

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

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

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

據上述可知，設計有效的廣播策略應是多目標優化問題，目的在于求解，即：

1.2 優化問題

針對式(1)的優化問題，本文利用基于擴展算法和仿真的混合優化(Hybrid Optimization Platform using Evolutionary Algorithm and Simulations，HOPES)平臺對參數 P、Nr、Dr、TTL進行優化。HOPES平臺由優化模塊、網絡仿真模塊和跟蹤模塊組成[8]，如圖 1所示。

圖1 HOPES流程圖

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

HOPES整體優化過程產生求解方案集，并與不同密度層次網絡匹配的不同廣播策略，并改變網絡仿真模塊中參數以及密度不斷優化。值得注意的是，這是一個離線優化過程?？蓪灮妮敵鰯祿⒁粋€知識庫，從而建立了密度層次與廣播策略的連接關系。因此，每個車輛依據網絡的密度層次選擇合適的廣播策略。

2 自適應的魯棒廣播方案

2.1 體系結構

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

圖2 MAPE-K循環控制結構示意圖

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

2.2 密度層次估計

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

其中，n是數據包的個數，|L(i)|表示發送和轉發數據包的節點數。

2.3 優先級

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

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

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

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

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

3 仿真以及結果分析

3.1 仿真場景及參數

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

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

表1 參數選擇

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

表2 目標函數值

3.2 性能評估

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

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

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

圖3 傳輸時間

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

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

圖4 傳遞率

圖5 重傳的次數

圖6 數據包碰撞的次數

4 總結

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

[1]TONGUZ O K，WISITPONGPHAN N，BAI F.Dv-cast：A distributed vehicular broadcast protocol for vehicular ad hoc networks[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 smart adaptive 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 emergency 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 broadcasting in IEEE 802.11 p/WAVE vehicular networks:delay analysis[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 intervehicle 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.

A multi-objective optimization-based autonomic dissemination method in VANET

Hu Yi，Wang Linna，Zhu Gongsheng
(College of Telecom Engineering，Beijing Polytechnic，Beijing 100015，China)

Aiming at the broadcasting used in Vehicular Ad hoc Network(VANET)，this paper introduces a novel autonomic dissemination method(ADM)which delivers messages in accordance with given priority and density levels.The proposed approach is based on two steps：an offline optimization process and an online adaptation to the network characteristics.Simulation results show that the ADM can increase the efficiency of the broadcasting process in terms of message delivery ratio,latency and interference reduction.

Broadcasting；priority level；network density；optimization；vehicular Ad hoc Networks

TP393

：A

：0258-7998(2015)03-0078-04

10.16157/j.issn.0258-7998.2015.03.020

2014-08-18)

胡亦(1975－)，男，碩士，副教授，主要研究方向：圖像處理。

北京電子科技職業學院科研課題（YZK2013002）

王琳娜(1978－)，女，碩士，講師，主要研究方向：信號分析與處理。

朱恭生(1970－)，男，本科，實驗師，主要研究方向：信號分析與處理。