聶淑珍 李正權(quán)，2*

1(江南大學(xué)江蘇省模式識(shí)別與計(jì)算智能工程實(shí)驗(yàn)室 江蘇 無錫 214122)2(東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 江蘇 南京 210096)

0 引 言

車載自組織網(wǎng)絡(luò)(Vehicular Ad hoc NETwork,VANET)也稱車聯(lián)網(wǎng)，作為智能交通系統(tǒng)里的關(guān)鍵技術(shù)，通過開啟車輛與車輛之間的通信(Vehicle-to-Vehicle,V2V)以及車輛與基礎(chǔ)設(shè)施之間的通信(Vehicle-to-Infrastructure,V2I)[1-2]，使得車輛能夠感知道路環(huán)境，包括車輛、行人、障礙物、基礎(chǔ)設(shè)施，從而實(shí)現(xiàn)緊急事故預(yù)警，規(guī)避危險(xiǎn)，增強(qiáng)道路安全[3]。

在車聯(lián)網(wǎng)中，媒體訪問控制(Medium Access Control,MAC)層主要規(guī)范移動(dòng)車輛節(jié)點(diǎn)對(duì)共享信道的訪問。節(jié)點(diǎn)訪問信道的形式包括單播和廣播。目前，針對(duì)MAC層的研究主要集中在IEEE 802.11協(xié)議簇中單播方式下載波監(jiān)聽多點(diǎn)接入/沖突避免(Carrier Sense Multiple Access with Collision Avoidance,CSMA/CA)機(jī)制及其采用的二進(jìn)制退避規(guī)則上[4-6]。而在實(shí)際應(yīng)用場(chǎng)景中，安全信息(車輛的位置、速度、加速度、行駛方向等)的傳輸以及大多數(shù)網(wǎng)絡(luò)服務(wù)(動(dòng)態(tài)主機(jī)配置、地址解析等)均基于廣播方式工作[7-8]。研究表明[9-10]，廣播方式下較易出現(xiàn)連續(xù)凍結(jié)過程(consecutive freeze process,CFP)，且爭(zhēng)用信道的競(jìng)爭(zhēng)窗口值越小，CFP現(xiàn)象發(fā)生地越頻繁。而目前，針對(duì)廣播方式下的MAC層性能分析的研究成果還較少，且多使用簡(jiǎn)單的一維馬爾科夫模型。該模型忽略了CFP現(xiàn)象,僅通過刪減Bianchi提出的單播方式下二維馬爾科夫模型的重傳階得到[11-13],故當(dāng)節(jié)點(diǎn)爭(zhēng)用信道的競(jìng)爭(zhēng)窗口值較小時(shí)，該模型預(yù)測(cè)節(jié)點(diǎn)的性能指標(biāo)的能力較差。因此，有必要建立一個(gè)可靠的廣播性能分析模型，為基于IEEE 802.11廣播方式工作的應(yīng)用提供理論分析與優(yōu)化依據(jù)。針對(duì)此問題，本文提出了一種二維馬爾科夫分析模型，該二維馬爾科夫模型將CFP現(xiàn)象映射為連續(xù)發(fā)送分組過程與連續(xù)退避凍結(jié)過程進(jìn)行分析，得出飽和狀態(tài)下車聯(lián)網(wǎng)中節(jié)點(diǎn)在廣播方式下分組傳輸?shù)钠骄鶗r(shí)延、吞吐量以及成功接收率，并通過仿真實(shí)驗(yàn)驗(yàn)證。

1 IEEE 802.11廣播協(xié)議概述

1.1 DCF機(jī)制

同一通信范圍內(nèi)的各車輛節(jié)點(diǎn)均采用IEEE 802.11 MAC層協(xié)議下的分布式協(xié)調(diào)功能(Distributed Coordination Function，DCF)訪問共享信道，該模式采用CSMA/CA機(jī)制。當(dāng)節(jié)點(diǎn)有待發(fā)送的數(shù)據(jù)分組時(shí)，會(huì)在等待分布式幀間間隔(Distributed Inter-Frame Spacing,DIFS)時(shí)間后，隨機(jī)從[0,CW-1]里選擇一個(gè)整數(shù)作為退避計(jì)數(shù)器的初始值，其中，CW是競(jìng)爭(zhēng)窗口值。每經(jīng)過一個(gè)時(shí)隙的時(shí)間間隔，節(jié)點(diǎn)會(huì)檢測(cè)信道。若信道被檢測(cè)為空閑，則退避計(jì)數(shù)器的值減1；否則，退避計(jì)數(shù)器被凍結(jié)，直到信道再次被檢測(cè)為空閑且在DIFS時(shí)間段內(nèi)連續(xù)空閑。若退避計(jì)數(shù)器的值遞減到0，節(jié)點(diǎn)將占用信道廣播該分組。與單播方式下不同的是，廣播機(jī)制下的分組中不包含控制幀，分組在傳輸過程中發(fā)生沖突后不會(huì)被檢測(cè)到傳輸失敗而重傳。因此，無論分組是否被成功傳輸，其競(jìng)爭(zhēng)窗口值均保持不變[14-15]。

1.2 連續(xù)凍結(jié)過程(CFP)

廣播機(jī)制中，當(dāng)所有節(jié)點(diǎn)均處于飽和狀態(tài)時(shí)，即任一時(shí)刻節(jié)點(diǎn)的發(fā)送隊(duì)列中均有分組在等待發(fā)送，若某一節(jié)點(diǎn)在退避為0，且發(fā)送完一個(gè)分組之后，從[0,CW-1]里選擇一個(gè)整數(shù)作為退避計(jì)數(shù)器的初始值時(shí)恰好選擇了0，再次獲得信道訪問資格，則該節(jié)點(diǎn)會(huì)連續(xù)發(fā)送兩個(gè)分組。與此同時(shí)，若其他節(jié)點(diǎn)中，有在該節(jié)點(diǎn)發(fā)送第一個(gè)分組時(shí)退避計(jì)數(shù)器的值不等于0的，則會(huì)被連續(xù)凍結(jié)兩個(gè)分組傳輸時(shí)占用信道的時(shí)間長(zhǎng)度。這種現(xiàn)象被稱為CFP。

本文將CFP映射為連續(xù)發(fā)送分組過程和連續(xù)退避凍結(jié)過程分析。圖1簡(jiǎn)單描述了這兩種過程。在t0時(shí)刻，信道空閑，節(jié)點(diǎn)A恰好退避到0，因此節(jié)點(diǎn)A獲得信道訪問資格并接入共享無線信道廣播分組。待其分組傳輸完畢后，節(jié)點(diǎn)A釋放信道資源，信道再次空閑，在等待一個(gè)DIFS時(shí)間后的t1時(shí)刻，節(jié)點(diǎn)A重新從[0,CW-1]里隨機(jī)選取一個(gè)值作為退避計(jì)數(shù)器的值，此時(shí)恰好選擇了0(概率為1/CW),節(jié)點(diǎn)A再次獲得信道訪問資格、繼續(xù)廣播下一個(gè)分組。t2時(shí)刻，第二個(gè)數(shù)據(jù)分組發(fā)送完畢。對(duì)于節(jié)點(diǎn)B,在t0時(shí)刻，其退避到x1(x1≠0)，由于信道被節(jié)點(diǎn)A占用，節(jié)點(diǎn)B會(huì)檢測(cè)到信道繁忙，因而進(jìn)入到退避凍結(jié)狀態(tài)，凍結(jié)時(shí)間為節(jié)點(diǎn)在信道中廣播一個(gè)分組的時(shí)間。在節(jié)點(diǎn)A發(fā)送完分組后，節(jié)點(diǎn)B凍結(jié)過程結(jié)束，信道空閑。同樣地，在等待一個(gè)DIFS時(shí)間之后的t1時(shí)刻，由于信道再次被節(jié)點(diǎn)A占用，節(jié)點(diǎn)B又一次檢測(cè)到信道繁忙，此時(shí)，節(jié)點(diǎn)B的退避計(jì)數(shù)器的值并沒有減一，而是保持退避計(jì)數(shù)器的值為x1并再次進(jìn)入退避凍結(jié)狀態(tài)。

圖1 連續(xù)凍結(jié)過程

可以觀察到，在[t0，t2]時(shí)間段內(nèi)，節(jié)點(diǎn)A連續(xù)廣播了兩個(gè)分組，本文將此過程稱為連續(xù)發(fā)送分組過程；而節(jié)點(diǎn)B在此時(shí)間段內(nèi)退避計(jì)數(shù)器的值連續(xù)凍結(jié)了兩個(gè)分組傳輸?shù)臅r(shí)間長(zhǎng)度，本文將此過程稱為連續(xù)退避凍結(jié)過程。

特別地，節(jié)點(diǎn)的連續(xù)發(fā)送分組過程又可以歸納為兩種情形：完全發(fā)送分組和部分時(shí)間發(fā)送分組。如圖2所示，假設(shè)整個(gè)連續(xù)發(fā)送分組過程為l個(gè)分組連續(xù)被廣播的過程。節(jié)點(diǎn)A和節(jié)點(diǎn)C在t3時(shí)刻均退避到0，同時(shí)進(jìn)入連續(xù)發(fā)送分組過程，緊接著，在每發(fā)送完一個(gè)分組之后，節(jié)點(diǎn)A的退避計(jì)數(shù)器均恰好選擇了0，連續(xù)廣播多個(gè)分組，直至廣播完第l個(gè)分組之后的t5時(shí)刻，退避計(jì)數(shù)器選擇了x0(x0≠0)作為初始值，整個(gè)連續(xù)發(fā)送分組過程結(jié)束。而節(jié)點(diǎn)C在某次發(fā)送完一個(gè)分組之后的t4時(shí)刻，因?yàn)檫x擇了x3(x3≠0)作為退避計(jì)數(shù)器的值，而在這個(gè)連續(xù)發(fā)送分組過程中的后段時(shí)間里處于凍結(jié)狀態(tài)，直至該連續(xù)發(fā)送分組過程結(jié)束?？梢杂^察到，在[t3,t5]時(shí)間段內(nèi)，節(jié)點(diǎn)A在這個(gè)連續(xù)發(fā)送分組過程中一直在發(fā)送分組，為完全發(fā)送分組；而節(jié)點(diǎn)C在這個(gè)過程中只有在[t3,t4]時(shí)間段內(nèi)在發(fā)送分組，在[t4,t5]時(shí)間段內(nèi)處于凍結(jié)狀態(tài)，故為部分時(shí)間發(fā)送分組。

圖2 連續(xù)發(fā)送分組過程

2 分析模型

為了更準(zhǔn)確地分析飽和狀態(tài)下802.11 DCF廣播的性能，本文將連續(xù)凍結(jié)過程分為連續(xù)發(fā)送分組過程和連續(xù)退避凍結(jié)過程考慮，并規(guī)定連續(xù)發(fā)送分組過程中節(jié)點(diǎn)發(fā)送的分組個(gè)數(shù)可等于1。類似地，連續(xù)退避凍結(jié)過程中節(jié)點(diǎn)被凍結(jié)的次數(shù)也可等于1。分析其狀態(tài)轉(zhuǎn)換過程，建立二維馬爾科夫狀態(tài)轉(zhuǎn)移鏈，如圖3所示。

圖3 二維馬爾科夫鏈模型

其中：W0=CW為爭(zhēng)用信道的競(jìng)爭(zhēng)窗口值；pb為處于退避過程中的節(jié)點(diǎn)檢測(cè)到信道繁忙的概率。設(shè){b(t),s(t)}為馬爾科夫鏈中的隨機(jī)狀態(tài)。其中，b(t)為t時(shí)刻節(jié)點(diǎn)所處的退避階數(shù)，b(t)=0表示節(jié)點(diǎn)處于連續(xù)發(fā)送分組過程剛結(jié)束的狀態(tài)。b(t)=1時(shí)表示節(jié)點(diǎn)處于常規(guī)退避過程中的狀態(tài)；b(t)=2表示節(jié)點(diǎn)處于連續(xù)凍結(jié)過程剛結(jié)束的狀態(tài)。s(t)為t時(shí)刻節(jié)點(diǎn)退避計(jì)數(shù)器的值。當(dāng)節(jié)點(diǎn)處于{1,0}狀態(tài)時(shí)，代表其退避計(jì)數(shù)器的值為0，節(jié)點(diǎn)將占用信道并開始廣播分組。根據(jù)該二維馬爾科夫狀態(tài)鏈，可得到以下狀態(tài)轉(zhuǎn)移概率：

P{0,k|1,0}=1/(W0-1)k∈[1,W0-1]

(1)

P{1,k-1|0,k}=1k∈[1,W0-1]

(2)

P{1,k-1|1,k}=1-pbk∈[1,W0-1)

(3)

P{2,k|1,k}=pbk∈[1,W0-1)

(4)

P{1,k-1|2,k}=1k∈[1,W0-1)

(5)

式(1)是節(jié)點(diǎn)在連續(xù)發(fā)送分組過程結(jié)束之后隨機(jī)選擇退避計(jì)數(shù)器值的概率。本文將完全廣播分組過程和部分時(shí)間廣播分組過程均視作連續(xù)發(fā)送分組過程，并將整個(gè)連續(xù)發(fā)送分組過程看作一個(gè)整體，故連續(xù)發(fā)送分組過程結(jié)束時(shí)退避計(jì)數(shù)器的取值范圍為[1,W0-1]，其轉(zhuǎn)移概率為1/(W0-1)。式(2)是節(jié)點(diǎn)結(jié)束連續(xù)發(fā)送分組過程后的下一個(gè)時(shí)隙，信道被檢測(cè)到空閑，退避計(jì)數(shù)器減一的概率。節(jié)點(diǎn)處于{0，k}(0

令bi,k表示節(jié)點(diǎn)處于{i,k}狀態(tài)的概率，(0≤k

(6)

聯(lián)合式(1)-式(5)，可得：

(7)

根據(jù)式(4)、式(7)，可得：

(8)

節(jié)點(diǎn)處于圖中狀態(tài)的總概率和為1，因此：

(9)

將式(6)-式(8)代入式(9)，可求得節(jié)點(diǎn)處于{1,0}狀態(tài)的概率：

(10)

假設(shè)在同一個(gè)通信范圍內(nèi)，有n個(gè)車輛節(jié)點(diǎn)共享一個(gè)無線信道，則pb為其他n-1個(gè)同處于常規(guī)退避過程中的節(jié)點(diǎn)至少有一個(gè)處于b1,0狀態(tài)的概率：

(11)

2.1 平均時(shí)延

將分組從源節(jié)點(diǎn)發(fā)送到目的節(jié)點(diǎn)所消耗的總時(shí)間即為時(shí)延，主要包括信道訪問時(shí)延(信道空閑退避減一的時(shí)延、退避過程中凍結(jié)時(shí)延以及等待DIFS的總時(shí)延)和傳輸時(shí)延?？紤]連續(xù)凍結(jié)過程，設(shè)節(jié)點(diǎn)每次連續(xù)退避凍結(jié)的平均時(shí)間為len1個(gè)分組被連續(xù)廣播占用信道的總時(shí)間。

(12)

式中：ni為其他n-1個(gè)節(jié)點(diǎn)中連續(xù)發(fā)送i個(gè)分組的節(jié)點(diǎn)總個(gè)數(shù)：

(13)

記連續(xù)發(fā)送分組過程每次平均占用的時(shí)間為len2個(gè)分組被連續(xù)廣播的時(shí)間。

(14)

(15)

式中：mi為連續(xù)發(fā)送i個(gè)分組的節(jié)點(diǎn)個(gè)數(shù)。

根據(jù)二維馬爾科夫狀態(tài)轉(zhuǎn)移鏈，可計(jì)算出每一次連續(xù)發(fā)送分組的總時(shí)延：

Pb×(E[F]+σ))×i)=

(16)

E[F]=len1×(EP+DIFS)

(17)

E[L]=len2×(EP+DIFS)

(18)

式中：σ為一個(gè)時(shí)隙的時(shí)間，E[F]為節(jié)點(diǎn)每次由于連續(xù)退避凍結(jié)所消耗的平均時(shí)間，E[L]為每次連續(xù)發(fā)送分組過程消耗的平均時(shí)間,EP為廣播一個(gè)分組占用信道的時(shí)間。

由于節(jié)點(diǎn)在連續(xù)發(fā)送分組過程中可能只是部分時(shí)間發(fā)送分組，而len2只是每次連續(xù)發(fā)送分組過程中連續(xù)發(fā)送分組個(gè)數(shù)最多的節(jié)點(diǎn)廣播的分組個(gè)數(shù)，即完全發(fā)送分組的節(jié)點(diǎn)廣播的分組個(gè)數(shù)，因此，需要計(jì)算出節(jié)點(diǎn)在每次連續(xù)發(fā)送分組的過程中實(shí)際發(fā)送分組的平均個(gè)數(shù)：

(19)

再根據(jù)式(16)，可得到節(jié)點(diǎn)發(fā)送單個(gè)分組的平均時(shí)延E[X]：

(20)

2.2 吞吐量

根據(jù)分組的平均傳輸時(shí)延E[X]計(jì)算出節(jié)點(diǎn)單位時(shí)間內(nèi)的吞吐量：

(21)

式中：P為每個(gè)分組的長(zhǎng)度。

2.3 成功接收率

(22)

pc,i=1-ps,ii>0

(23)

式中：ps,i為節(jié)點(diǎn)在連續(xù)發(fā)送分組的過程中第i個(gè)分組被成功發(fā)送的概率，pc,i為節(jié)點(diǎn)在連續(xù)發(fā)送分組過程中第i個(gè)分組被發(fā)送失敗的概率。假設(shè)信道為理想信道，則節(jié)點(diǎn)廣播的分組被成功接收到的概率，即成功接收率(Packet Delivery Ratio,PDR)可表示為：

(24)

3 仿真分析

通過MATLAB模擬飽和狀態(tài)下車載自組織網(wǎng)絡(luò)中節(jié)點(diǎn)廣播分組的場(chǎng)景，驗(yàn)證本文提出的二維馬爾科夫分析模型，并與一維馬爾科夫分析模型[12]作對(duì)比。實(shí)驗(yàn)使用的主要參數(shù)見表1。

表1 實(shí)驗(yàn)參數(shù)列表

圖4給出了通信范圍內(nèi)的車輛數(shù)目為20(n=20)和40(n=40)，競(jìng)爭(zhēng)窗口為[4,64]時(shí)，各車輛節(jié)點(diǎn)廣播分組的平均時(shí)延隨競(jìng)爭(zhēng)窗口的變化情況。從圖中可觀察到，忽略了連續(xù)退避凍結(jié)現(xiàn)象的一維分析模型在競(jìng)爭(zhēng)窗口較小時(shí)。其平均時(shí)延的理論值比實(shí)驗(yàn)得到的平均時(shí)延小，且爭(zhēng)用信道的競(jìng)爭(zhēng)窗口值越小，其理論值與仿真值的偏差越大。這是因?yàn)楦?jìng)爭(zhēng)窗口越小，節(jié)點(diǎn)在退避過程中會(huì)頻繁受到其他節(jié)點(diǎn)連續(xù)發(fā)送分組的影響，故而忽略了CFP現(xiàn)象的一維模型與實(shí)際值偏差越大。而本文建立的二維馬爾科夫模型考慮到了連續(xù)退避凍結(jié)現(xiàn)象對(duì)分析模型的影響，準(zhǔn)確地模擬了節(jié)點(diǎn)接入信道的過程，因此根據(jù)該模型推導(dǎo)出的平均時(shí)延與仿真實(shí)驗(yàn)得到的平均時(shí)延值即使在競(jìng)爭(zhēng)窗口較小的情況下，也能具備較高吻合度。

圖4 平均時(shí)延隨競(jìng)爭(zhēng)窗口值的變化

圖5給出了通信范圍內(nèi)的車輛數(shù)目為20(n=20)和40(n=40)，競(jìng)爭(zhēng)窗口為[4,64]時(shí)，各節(jié)點(diǎn)單位時(shí)間的吞吐量隨競(jìng)爭(zhēng)窗口的變化情況。從圖中可以看出，車輛數(shù)目為20和40時(shí)，無論競(jìng)爭(zhēng)窗口取何值，二維馬爾科夫分析模型均能很好地預(yù)測(cè)節(jié)點(diǎn)的吞吐量，其理論吞吐量的值與仿真實(shí)驗(yàn)下的吞吐量值都很接近。而一維模型預(yù)測(cè)的吞吐量?jī)H在W0>20時(shí)與仿真實(shí)驗(yàn)下的吞吐量較接近，這是由于競(jìng)爭(zhēng)窗口較大時(shí)，CFP現(xiàn)象發(fā)生地概率較小，忽略了CFP現(xiàn)象的一維模型可粗略模擬該情況下的接入信道過程；而當(dāng)W0<20時(shí)，CFP現(xiàn)象對(duì)節(jié)點(diǎn)的性能影響較大，故此種情況下，一維模型與實(shí)際情況偏差較大，預(yù)測(cè)結(jié)果較不理想。另外，一維模型下的吞吐量理論值在W0<20時(shí)比仿真實(shí)驗(yàn)下的吞吐量大，這是由于一維馬爾科夫分析模型忽略了連續(xù)退避凍結(jié)現(xiàn)象。該模型下的節(jié)點(diǎn)在退避過程中任一時(shí)隙都有退避減一的機(jī)會(huì)，故節(jié)點(diǎn)在任一時(shí)隙都有發(fā)送分組的可能，而實(shí)際上，節(jié)點(diǎn)可能由于其他節(jié)點(diǎn)連續(xù)發(fā)送分組而處于連續(xù)退避凍結(jié)狀態(tài)，沒有機(jī)會(huì)遞減退避計(jì)數(shù)器的值。

圖5 吞吐量隨競(jìng)爭(zhēng)窗口值的變化

圖6給出了通信范圍內(nèi)的車輛數(shù)目為20(n=20)和40(n=40)，競(jìng)爭(zhēng)窗口為[4,64]時(shí)，節(jié)點(diǎn)廣播分組的成功接收率隨競(jìng)爭(zhēng)窗口的變化情況。從圖中可以觀察到，當(dāng)n=20、W0>20或n=40、W0>30，即競(jìng)爭(zhēng)窗口較大時(shí)，一維馬爾科夫模型與二維馬爾科夫模型均能很好地預(yù)測(cè)節(jié)點(diǎn)廣播分組的成功接收率。而當(dāng)n=20、W0<20時(shí)或n=40、W0<30，即競(jìng)爭(zhēng)窗口偏小時(shí)，一維馬爾科夫分析模型下分組的成功接收率理論值與仿真實(shí)驗(yàn)值相比偏低。原因是不考慮連續(xù)發(fā)送分組現(xiàn)象時(shí)，所有分組產(chǎn)生沖突的概率被簡(jiǎn)單地視為第一個(gè)分組發(fā)生沖突的概率。而在實(shí)際情況中，由于存在連續(xù)發(fā)送分組現(xiàn)象，節(jié)點(diǎn)在發(fā)送第i(i>1)個(gè)分組時(shí)產(chǎn)生沖突的概率比發(fā)送第i-1個(gè)分組時(shí)產(chǎn)生沖突的概率小，故實(shí)際情況下分組在發(fā)送時(shí)產(chǎn)生沖突的概率較小，成功接收率較大。相比較而言，即使是在小競(jìng)爭(zhēng)窗口的情況下，增加考慮了連續(xù)凍結(jié)過程的二維馬爾科夫分析模型也能較準(zhǔn)確地預(yù)測(cè)節(jié)點(diǎn)廣播分組的成功接收率。

圖6 成功接收率隨競(jìng)爭(zhēng)窗口值的變化

4 結(jié) 語

本文通過建立一個(gè)考慮了連續(xù)凍結(jié)現(xiàn)象的二維馬爾科夫模型來分析飽和狀態(tài)下IEEE 802.11廣播機(jī)制在MAC層的性能。將該模型考慮到的連續(xù)凍結(jié)現(xiàn)象分為連續(xù)發(fā)送分組和連續(xù)退避凍結(jié)兩個(gè)過程進(jìn)行分析，構(gòu)建節(jié)點(diǎn)廣播分組的平均時(shí)延、吞吐量以及成功接收率的理論分析表達(dá)式。仿真結(jié)果顯示，本文建立的二維馬爾科夫模型能準(zhǔn)確地預(yù)測(cè)廣播機(jī)制下的性能指標(biāo)。后續(xù)的研究將主要針對(duì)車輛速度、隱藏終端、非飽和狀態(tài)等影響車載自組織網(wǎng)絡(luò)媒體控制接入層性能的因素展開。