《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > VANET中一種基于多目標(biāo)優(yōu)化的自適應(yīng)廣播方案
VANET中一種基于多目標(biāo)優(yōu)化的自適應(yīng)廣播方案
2015年電子技術(shù)應(yīng)用第2期
胡 亦,王琳娜,朱恭生
北京電子科技職業(yè)學(xué)院 電信工程學(xué)院,北京
摘要: 針對(duì)車載網(wǎng)VANET(Vehicular Ad hoc Network) 中的廣播策略,提出新穎的自動(dòng)分發(fā)方案(Autonomic Dissemination Method,ADM)。通過ADM傳輸消息,自適應(yīng)網(wǎng)絡(luò)的密度和消息的優(yōu)先級(jí)變化。在實(shí)施ADM過程中,采用兩個(gè)步驟:離線優(yōu)化過程和在線適應(yīng)網(wǎng)絡(luò)特性。仿真結(jié)果表明,提出的ADM方案在消息傳遞率、傳輸時(shí)延和干擾方面得到提高。
中圖分類號(hào): TP393
文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2015)03-0078-04
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
Abstract: 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.
Key words : Broadcasting;priority level;network density;optimization;vehicular Ad hoc Networks


  車載網(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)化問題,目的在于求即:

  LSDMY5N6BU3V2L9VVMGUYVW.png

  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所示。

001.jpg

  采用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所示。

002.jpg

  在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)所示。

  8D@SCK257[CIC4Q]V$QU2E6.png

  其中,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所示。

007.jpg

  從表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)的。

008.jpg

  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)。

003.jpg

  考慮到傳輸時(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]。

004.jpg

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

005.jpg

006.jpg

  圖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.


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。