程青青, 陳戈珩

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

0 引 言

0.1 VANET網(wǎng)絡(luò)架構(gòu)

VANET經(jīng)典體系架構(gòu)中包含車載單元(On Board Unit， OBU)節(jié)點(diǎn)和路邊單元(Road Side Unit， RSU)節(jié)點(diǎn)兩種設(shè)備類型。網(wǎng)絡(luò)中的車與車之間、車與路側(cè)單元節(jié)點(diǎn)通過無線技術(shù)通信，而車與基站之間通過蜂窩網(wǎng)技術(shù)通信。一般情況下，由于道路的約束，VANET中OBU節(jié)點(diǎn)會(huì)按照一定規(guī)則方式運(yùn)動(dòng)。而RSU等固定節(jié)點(diǎn)則負(fù)責(zé)在定點(diǎn)位置與車載節(jié)點(diǎn)通信，提供短距離范圍內(nèi)V2I和V2V通信服務(wù)或長距離范圍的外部網(wǎng)絡(luò)通信服務(wù)[1]。典型的VANET架構(gòu)如圖1所示。

0.2 問題分析

近年來，針對(duì)車載自組織網(wǎng)絡(luò)中的緊急消息如何快速、可靠地傳播到相關(guān)區(qū)域內(nèi)所有車輛的特性，研究者提出了多種多跳廣播方案。這種多跳廣播方案解決了單跳廣播覆蓋區(qū)域不夠大的問題，可以保證目標(biāo)區(qū)域內(nèi)每個(gè)車輛都能夠成功地接收消息。

圖1 VANET網(wǎng)絡(luò)架構(gòu)

最早提出的廣播方式是簡單泛洪[2]，要求網(wǎng)絡(luò)中的每一個(gè)接收到廣播包節(jié)點(diǎn)都要無條件轉(zhuǎn)發(fā)，當(dāng)網(wǎng)絡(luò)密度達(dá)到一定程度時(shí)，網(wǎng)絡(luò)中的消息副本將會(huì)迅速增加，造成廣播風(fēng)暴問題[3]。因此，如何根據(jù)VANET的特性設(shè)計(jì)出一種能夠有效抑制廣播風(fēng)暴，并且具有高穩(wěn)定性、低延遲的多跳廣播方案，是目前VANET研究的重點(diǎn)和難點(diǎn)。

0.3 算法研究

現(xiàn)有的多跳廣播方案主要可以分為兩類：基于發(fā)送者的多跳廣播協(xié)議和基于接收者的多跳廣播協(xié)議。

基于發(fā)送者的多跳廣播是指由發(fā)送者確定下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的一類多跳廣播策略，這一類算法通常需要不斷地交互一些本地信息，用于篩選下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。例如基于地理位置的多跳廣播、基于優(yōu)先級(jí)的多跳廣播等。文獻(xiàn)[4]提出了一種基于優(yōu)先級(jí)的多跳廣播策略AVED，轉(zhuǎn)發(fā)節(jié)點(diǎn)先根據(jù)收集到的鄰居節(jié)點(diǎn)的信息計(jì)算鄰居節(jié)點(diǎn)的優(yōu)先級(jí)，然后將優(yōu)先級(jí)信息封裝到廣播數(shù)據(jù)包中一并廣播出去，鄰居節(jié)點(diǎn)接收到廣播數(shù)據(jù)包之后判斷是否應(yīng)當(dāng)進(jìn)行轉(zhuǎn)發(fā)。文獻(xiàn)[5]提出的基于模糊邏輯的智能廣播策略，以及文獻(xiàn)[6-7]提出的基于距離的多跳廣播策略，都屬于基于發(fā)送者的多跳廣播方案。

基于接收者的多跳廣播是指由接收者自己判斷是否應(yīng)該轉(zhuǎn)發(fā)數(shù)據(jù)包的一類多跳廣播策略。例如基于概率的多跳廣播、基于計(jì)數(shù)器的多跳廣播。文獻(xiàn)[8-9]提出的基于模糊邏輯的多跳廣播策略FLB和BEFLAB，文獻(xiàn)[10]提出的智能混合自適應(yīng)廣播策略IHAB，以及文獻(xiàn)[11]中提出的基于計(jì)數(shù)的多跳廣播方案CBBM都屬于基于接收者的多跳廣播策略。

文中提出的基于概率的自適應(yīng)多跳廣播協(xié)議PAMBP是一種基于接收者的多跳廣播策略。文獻(xiàn) [12-16]分別提出了不同的基于概率的多跳廣播方案。文獻(xiàn)[12]針對(duì)不同的網(wǎng)絡(luò)密度提出了一種基于計(jì)數(shù)和概率相結(jié)合的方法CAPP；文獻(xiàn)[13]提出了一種分布式概率廣播的方案DPB；文獻(xiàn)[14]提出了一種基于車輛速度調(diào)節(jié)轉(zhuǎn)發(fā)概率的多跳廣播策略SAPB；文獻(xiàn)[15]考慮了網(wǎng)絡(luò)密度和距離的因素，提出了網(wǎng)絡(luò)平均鄰居數(shù)量Navg的概念，針對(duì)不同的網(wǎng)絡(luò)密度，采用不同的轉(zhuǎn)發(fā)概率計(jì)算公式，提出了AWPP方法；文獻(xiàn)[16]提出了一種基于信號(hào)強(qiáng)度計(jì)算轉(zhuǎn)發(fā)概率的跨層動(dòng)態(tài)概率廣播算法CDPBA，通過路由層和MAC層共享信號(hào)強(qiáng)度，完成路由層轉(zhuǎn)發(fā)概率的計(jì)算。

1 算法模型

文中提出了一種能夠根據(jù)網(wǎng)絡(luò)環(huán)境自動(dòng)調(diào)節(jié)轉(zhuǎn)發(fā)概率的多跳廣播協(xié)議。本協(xié)議在確定轉(zhuǎn)發(fā)概率時(shí)，綜合考慮網(wǎng)絡(luò)密度、相對(duì)距離以及節(jié)點(diǎn)相對(duì)速度三方面的因素，另外，本協(xié)議通過動(dòng)態(tài)調(diào)整不同因素在轉(zhuǎn)發(fā)過程中所占的權(quán)重，以確保本協(xié)議在不同的網(wǎng)絡(luò)環(huán)境中具有良好的適應(yīng)性和穩(wěn)定性。

1.1 網(wǎng)絡(luò)建模

給出假定情景下的網(wǎng)絡(luò)模型：

1)假設(shè)車輛的傳輸范圍為R;

2)假設(shè)一跳范圍內(nèi)最大鄰居節(jié)點(diǎn)數(shù)量為Nmax，兩節(jié)點(diǎn)的最大相對(duì)移動(dòng)速度為Vmax。

3)每輛車都會(huì)配備全球定位系統(tǒng)(GPS)，所以每輛車都可以隨時(shí)隨地知道自己的精準(zhǔn)定位。

交通場景如圖2所示。

圖2 交通場景

圖中，S表示源節(jié)點(diǎn)，R表示源節(jié)點(diǎn)S的通信半徑。變量fi，i∈(1,2,3,…,N)表示源節(jié)點(diǎn)S的鄰居節(jié)點(diǎn)，其中N表示源節(jié)點(diǎn)S通信范圍內(nèi)的鄰居節(jié)點(diǎn)總數(shù)，節(jié)點(diǎn)fi與源節(jié)點(diǎn)S的距離用di表示。當(dāng)遇到緊急情況時(shí)，源節(jié)點(diǎn)S將在第一時(shí)間內(nèi)向傳輸范圍內(nèi)的所有鄰居節(jié)點(diǎn)廣播緊急數(shù)據(jù)包，鄰居節(jié)點(diǎn)收到源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包后開始存儲(chǔ)，但此時(shí)并不計(jì)算轉(zhuǎn)發(fā)概率，鄰居節(jié)點(diǎn)將在退避時(shí)間結(jié)束后開始計(jì)算轉(zhuǎn)發(fā)概率的大小。在計(jì)算轉(zhuǎn)發(fā)概率時(shí)，每個(gè)鄰居節(jié)點(diǎn)首先要根據(jù)當(dāng)前的網(wǎng)絡(luò)狀況確定網(wǎng)絡(luò)密度ρi、距離di,以及相對(duì)速度Vi分別所占的權(quán)重，然后再計(jì)算轉(zhuǎn)發(fā)概率的大小，當(dāng)轉(zhuǎn)發(fā)概率大于隨機(jī)生成的概率時(shí)，該鄰居節(jié)點(diǎn)獲得轉(zhuǎn)發(fā)權(quán)。

1.2 PAMBP系統(tǒng)模型

1.2.1 轉(zhuǎn)發(fā)概率

文中在現(xiàn)有的基于概率的多跳轉(zhuǎn)發(fā)方案的基礎(chǔ)上進(jìn)行改進(jìn)，給出了新的轉(zhuǎn)發(fā)概率計(jì)算公式，定義如下：

(1)

(2)

式中：α+β+γ=1；

N----本節(jié)點(diǎn)傳輸范圍內(nèi)的鄰居節(jié)點(diǎn)數(shù)量；

d----本節(jié)點(diǎn)與上一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)相對(duì)距離；

V----本節(jié)點(diǎn)與上一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的相對(duì)速度。

1.2.2 本地信息交互

網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)通過周期性的廣播Hello數(shù)據(jù)包進(jìn)行本地信息的交互，Hello數(shù)據(jù)包攜帶的本地信息包括節(jié)點(diǎn)的MAC地址、經(jīng)緯度坐標(biāo)、速度和行駛方向。鄰居節(jié)點(diǎn)接收到Hello數(shù)據(jù)包后，會(huì)更新自己的鄰居列表。

鄰居節(jié)點(diǎn)接收到Hello數(shù)據(jù)包后，根據(jù)數(shù)據(jù)包中攜帶的信息和下式分別計(jì)算兩節(jié)點(diǎn)的相對(duì)距離d和相對(duì)速度V，更新自己的鄰居列表信息。

(3)

式中：x1，x2，y1，y2----通過經(jīng)緯度轉(zhuǎn)換得到的兩節(jié)點(diǎn)的位置坐標(biāo)。

(4)

式中：V1，V2----分別為兩節(jié)點(diǎn)的速度矢量；

c----真空下的光速。

1.2.3 權(quán)重調(diào)整

式(1)在計(jì)算轉(zhuǎn)發(fā)概率時(shí)，不同的因素所占的權(quán)重是不同的，因此在計(jì)算轉(zhuǎn)發(fā)概率之前，首先要確定不同因素所占的權(quán)重大小。權(quán)重的調(diào)整受當(dāng)前鄰居節(jié)點(diǎn)個(gè)數(shù)N,以及退避時(shí)間結(jié)束時(shí)節(jié)點(diǎn)收到的消息副本的數(shù)量C兩方面的因素影響，并且，引入?yún)?shù)消息副本閾值Cthreshold作為確定權(quán)重調(diào)整大小的依據(jù)。具體權(quán)重調(diào)整算法如下。

首先判斷條件Cthreshold

(5)

當(dāng)節(jié)點(diǎn)接收到的消息副本的數(shù)量小于消息副本閾值時(shí)，說明網(wǎng)絡(luò)中只有極少部分的節(jié)點(diǎn)完成了轉(zhuǎn)發(fā)，此時(shí)，轉(zhuǎn)發(fā)概率將會(huì)增大，反之，轉(zhuǎn)發(fā)概率將會(huì)被抑制。

若條件不成立，說明當(dāng)前網(wǎng)絡(luò)密度較小，為了確保協(xié)議的穩(wěn)定性，此時(shí)采用概率為“1”轉(zhuǎn)發(fā)模式[17]，對(duì)報(bào)文進(jìn)行無條件轉(zhuǎn)發(fā)。

1.2.4 PAMBP協(xié)議

當(dāng)車輛遭遇緊急情況時(shí)，需要以最快的速度向周圍車輛廣播緊急消息。為了提高廣播的可靠性和穩(wěn)定性，文中設(shè)計(jì)了一種基于概率的自適應(yīng)多跳廣播協(xié)議PAMBP，協(xié)議中涉及的變量及其初始值見表1。

表1 PAMBP協(xié)議變量

具體協(xié)議流程如下

(CWmax-CWmin)+CWmin。

(6)

1)源節(jié)點(diǎn)廣播數(shù)據(jù)包，同時(shí)將數(shù)據(jù)包備份，并啟動(dòng)重播定時(shí)器(重播定時(shí)器的值設(shè)置為最大競爭窗口值CWmax)。

2)若重播定時(shí)器結(jié)束前，源節(jié)點(diǎn)仍沒有接收到鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)包，則判斷最大重播次數(shù)RBmax是否為零，若RBmax≠0，源節(jié)點(diǎn)將重播數(shù)據(jù)包，重新設(shè)置重播定時(shí)器，并將RBmax減一，否則，源節(jié)點(diǎn)不再重播，并將備份數(shù)據(jù)包刪除，算法結(jié)束；若重播定時(shí)器結(jié)束前，源節(jié)點(diǎn)收到了鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)包，則不再重播，并將備份數(shù)據(jù)包刪除。

3)鄰居節(jié)點(diǎn)接收到廣播數(shù)據(jù)包后，判斷是否是首次接收到此數(shù)據(jù)包，若是，則執(zhí)行下一步；若不是，則丟棄數(shù)據(jù)包。

4)計(jì)算退避時(shí)間，為了減少信道競爭和消息碰撞的概率，鄰居節(jié)點(diǎn)采用式(6)計(jì)算自己的退避時(shí)間，并啟動(dòng)退避定時(shí)器。

5)執(zhí)行權(quán)重調(diào)節(jié)算法，計(jì)算wadjust，退避時(shí)間結(jié)束后，根據(jù)式(5)計(jì)算wadjust，調(diào)整對(duì)應(yīng)權(quán)重，并根據(jù)式(1)計(jì)算節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率p。

6)轉(zhuǎn)發(fā)數(shù)據(jù)包，節(jié)點(diǎn)會(huì)生成一個(gè)隨機(jī)概率P，若p≥P，則節(jié)點(diǎn)立即轉(zhuǎn)發(fā)數(shù)據(jù)包，否則放棄轉(zhuǎn)發(fā)。

2 仿真驗(yàn)證

2.1 實(shí)驗(yàn)環(huán)境

使用NS-3網(wǎng)絡(luò)仿真模擬器來驗(yàn)證PAMBP的性能[18]，與SPAB和AWPP兩種同樣基于概率的算法作了比較。實(shí)驗(yàn)時(shí)，車輛節(jié)點(diǎn)隨機(jī)分布在覆蓋范圍為2 km×2 km的車聯(lián)網(wǎng)環(huán)境中，單跳范圍內(nèi)的節(jié)點(diǎn)數(shù)量在0～300之間，車輛速度在0～100 km/h之間。其他一些仿真參數(shù)設(shè)置見表2[19-20]。

表2 仿真參數(shù)設(shè)置

2.2 性能指標(biāo)

2.2.1 平均副本數(shù)量

平均副本數(shù)量可以在很大程度上反應(yīng)網(wǎng)絡(luò)中的數(shù)據(jù)包冗余度，其定義如下

(7)

式中：PCi----i個(gè)節(jié)點(diǎn)接收到數(shù)據(jù)包的概率。

2.2.2 平均時(shí)延

標(biāo)準(zhǔn)IEEE802.11的修訂版本中指出，VANET網(wǎng)絡(luò)在PHY和MAC層采用IEEE802.11p無線協(xié)議，IEEE802.11p是基于分布式協(xié)調(diào)函數(shù)(DCF)的廣播協(xié)議，DCF采用帶有沖突避免的載波監(jiān)聽多路訪問(CSMA/CA)機(jī)制來爭奪信道。為了減少?zèng)_突，DCF采用信道感知來檢測信道活動(dòng)，并且利用截?cái)喽M(jìn)制指數(shù)退避方法隨機(jī)化分組傳輸?shù)拈_始時(shí)間[20-21]。一跳平均時(shí)延可以表示為

(8)

其中

(9)

T0=Theader+Tdata+AIFSN,

(10)

式中：PC----每個(gè)時(shí)隙時(shí)間內(nèi)沖突發(fā)生的概率;

T0----成功發(fā)送數(shù)據(jù)包占用的信道時(shí)間;

Ts----一個(gè)時(shí)隙;

q----最大退避指數(shù)。

3)平均消息可達(dá)率。消息可達(dá)率體現(xiàn)了協(xié)議的信息傳播效率和可靠性，其定義如下

(11)

式中：Nr----成功接收的數(shù)據(jù)包數(shù)量；

Ns----發(fā)送的數(shù)據(jù)包總數(shù)。

2.3 仿真結(jié)果分析

為了確定系統(tǒng)參數(shù)的初始值，我們進(jìn)行了多次實(shí)際測試，最終確定以下組合，能夠確保本協(xié)議在不同的VANET環(huán)境中都具有良好的性能,見表3。

表3 系統(tǒng)參數(shù)

另外，前面提到本協(xié)議中轉(zhuǎn)發(fā)概率的計(jì)算受到網(wǎng)絡(luò)密度、相對(duì)距離以及相對(duì)速度三個(gè)因素的影響，但是由式(1)可知，這三種因素在對(duì)轉(zhuǎn)發(fā)概率的影響方面是平行關(guān)系，不同的僅僅是影響程度。因此，在接下來的仿真結(jié)果分析中，只分析網(wǎng)絡(luò)密度對(duì)協(xié)議性能的影響，車輛速度設(shè)置為60km/h。

網(wǎng)絡(luò)密度對(duì)消息副本數(shù)量的影響如圖3所示。

圖3 平均副本數(shù)量

從圖中可以看出，本協(xié)議的平均副本數(shù)量不會(huì)隨著網(wǎng)絡(luò)密度的增加而顯著增大，平均副本數(shù)量維持在3個(gè)左右。這是因?yàn)槲闹刑岢龅臋?quán)重調(diào)節(jié)算法考慮到了消息副本的影響，當(dāng)節(jié)點(diǎn)接收到的消息副本增加時(shí)，其轉(zhuǎn)發(fā)概率就會(huì)降低，從而抑制消息副本的數(shù)量。相比CDPAB算法，本算法具有較大優(yōu)勢，平均副本數(shù)量低2個(gè)左右，而DPB、SPAB和AWPP算法隨著網(wǎng)絡(luò)密度的增加，平均副本數(shù)量增長較大，其中AWPP算法由于沒有考慮網(wǎng)絡(luò)密度的因素，其平均副本數(shù)量的增長趨勢最為明顯。

平均一跳延遲時(shí)間的仿真結(jié)果如圖4所示。

圖4 平均延遲時(shí)間

本協(xié)議的平均一跳延遲時(shí)間相對(duì)較低，并且隨著網(wǎng)絡(luò)密度的增大，逐漸趨于穩(wěn)定。這是因?yàn)楸緟f(xié)議提出了相應(yīng)的退避等待規(guī)則，鄰居節(jié)點(diǎn)根據(jù)自己與轉(zhuǎn)發(fā)節(jié)點(diǎn)的相對(duì)距離和相對(duì)速度確定自己的等待時(shí)間，從而降低了信道沖突的概率。

網(wǎng)絡(luò)密度對(duì)平均消息可達(dá)率的影響如圖5所示。

圖5 平均消息可達(dá)率

從圖中可以看出，本協(xié)議的PDR始終保持在95%以上，并且不會(huì)隨著網(wǎng)絡(luò)密度的變化而顯著改變。這是因?yàn)樵诒緟f(xié)議中，當(dāng)節(jié)點(diǎn)接收到的消息副本數(shù)量低于消息副本閾值Cthreshold時(shí)，節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率會(huì)顯著增大，從而在一定程度上確保了消息的有效傳播。

3 結(jié) 語

通過仿真實(shí)驗(yàn)，比較了本協(xié)議與DPB、SPAB、AWPP和CDPAB四種算法在平均副本數(shù)量、平均時(shí)延以及平均消息可達(dá)率三個(gè)方面的性能，可以看出，本協(xié)議在消息副本數(shù)量、時(shí)延以及消息可達(dá)率方面都有良好的表現(xiàn)，并且消息副本的數(shù)量不會(huì)隨著車輛密度的增大而顯著增加。另外，平均消息可達(dá)率始終保持著較高的水平，說明本協(xié)議在不同網(wǎng)絡(luò)環(huán)境中都具有良好的穩(wěn)定性。