車聯(lián)網(wǎng)中基于交通流量感知的數(shù)據(jù)路由

孫 列，楊梓晗

（1.西安航空學(xué)院 飛行器學(xué)院，西安 710077；2.湖北工業(yè)大學(xué) 工業(yè)設(shè)計(jì)學(xué)院，武漢 430068）

0 引言

作為現(xiàn)代社會最重要的基礎(chǔ)設(shè)施，交通系統(tǒng)的效率直接影響居民生活質(zhì)量。然而，隨著交通流量的增加以及道路車輛數(shù)的激增，交通事故頻繁發(fā)生[1-2]。因此，如何有效地提高道路安全，是交通系統(tǒng)亟待解決的問題。

車載網(wǎng)絡(luò)（vehicular networks, VNs）已成為智能交通系統(tǒng)（intelligent transportation system, ITS）的重要組成部分，能有效地緩解交通事故的發(fā)生[3]。VNs利用車輛間（vehicle-to-vehicle, V2V）的通信和車輛與基礎(chǔ)設(shè)施（vehicle-to-infrastructure, V2I）的通信，提高道路行駛安全。

然而，由于車輛的高速移動，以及移動方向的變化，車載網(wǎng)絡(luò)存在不穩(wěn)定、低可靠的特性。這使得安全相關(guān)的消息可能不能及時(shí)傳遞至道路上所有車輛。因此，如何有效地將消息傳輸?shù)杰囕v，成為VNs的研究熱點(diǎn)[4]。

由于拓?fù)涞目焖僮兓?，傳統(tǒng)的基于移動自組織網(wǎng)絡(luò)（mobile ad hoc networks, MANETs）的路由，如鏈路狀態(tài)協(xié)議（optimized link state routing, OLSR）[5]、按需距離矢量路由（ad hoc on demand distance vector, AODV）[6]等并不能獲取好的路由性能[7]。研究人員把目光轉(zhuǎn)向地理位置路由。依據(jù)源節(jié)點(diǎn)和目的節(jié)點(diǎn)的位置信息決策路由，如文獻(xiàn)[8]提出的基于位置信息的車聯(lián)網(wǎng)路由，利用全球定位系統(tǒng)（global positioning system, GPS）接收機(jī)提供的行車參數(shù)信息，并利用這些信息恢復(fù)路由；文獻(xiàn)[9]提出基于地理位置改進(jìn)的車聯(lián)網(wǎng)路由，根據(jù)車輛移動方向和速度，預(yù)測車輛運(yùn)動軌跡，并據(jù)此軌跡選擇下一跳轉(zhuǎn)發(fā)路由，進(jìn)而保證路由的可靠性；文獻(xiàn)[10]提出1個混合路由協(xié)議，將貪婪邊界狀態(tài)路由（greedy perimeter stateless routing, GPSR）和層次位置服務(wù)（hierarchical location service, HLS）策略相結(jié)合，通過GPSR策略傳輸數(shù)據(jù)包。當(dāng)目標(biāo)節(jié)點(diǎn)位置不確定時(shí)，就通過HLS策略獲取目標(biāo)節(jié)點(diǎn)的位置。

此外，VNs是依據(jù)道路上的車輛轉(zhuǎn)發(fā)數(shù)據(jù)的，所以如何選擇路段傳輸數(shù)據(jù)是數(shù)據(jù)轉(zhuǎn)發(fā)的關(guān)鍵。為此，研究人員提出基于流量感知的交叉口路由和基于道路的地理位置路由。例如，文獻(xiàn)[11]針對3維城市道路，提出了改進(jìn)的定向路由。該路由采用動態(tài)的傳輸范圍，并采用虛擬鄰居節(jié)點(diǎn)策略選擇可靠路由。然而，該路由并沒有給出如何調(diào)整車輛的傳輸范圍，也未能分析傳輸范圍對路由性能的影響。為此，本文提出交通流量感知的數(shù)據(jù)路由（traffic volume-aware data routing, TVDR）。TVDR路由先將道路劃分為不同的矩形格，并推導(dǎo)基于路段連通的概率，然后選擇連通率最高的路徑傳輸數(shù)據(jù)。

1 約束條件

TVDR路由是依據(jù)路段的連通情況傳輸數(shù)據(jù)的，并通過預(yù)測流量信息估計(jì)每個路段的路徑連通率。引入布爾變量Ci來表示路段i是否為數(shù)據(jù)源參數(shù)，如果Ci大于預(yù)定的閾值，則Ci為1；否則Ci為零。

由于高頻信號的穿透性差，假定數(shù)據(jù)包只沿著道路傳輸，另假定道路是雙向的，且每個方向至少有2個車道。只要在源節(jié)點(diǎn)通信范圍cR內(nèi)的車輛，都可作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，如圖1所示。同一方向車輛可以轉(zhuǎn)發(fā)數(shù)據(jù)包，反方向車輛也可轉(zhuǎn)發(fā)數(shù)據(jù)包。數(shù)據(jù)轉(zhuǎn)發(fā)示例如圖2所示。

圖1 數(shù)據(jù)轉(zhuǎn)發(fā)策略

圖2 數(shù)據(jù)轉(zhuǎn)發(fā)示例

將路段照射于矩形格，每個格的長度為r=Rc/2，如圖2（a）所示。假定在矩形格內(nèi)每輛車能夠與鄰近矩形格內(nèi)的其他車輛直接通信。在每個方向上，1輛車至少有2條潛在的轉(zhuǎn)發(fā)鏈路。換而言之，如果在2個矩形格內(nèi)沒有車輛，則表明不存在轉(zhuǎn)發(fā)數(shù)據(jù)的鏈路，如圖2（b）所示。

2 TVDR路由

TVDR路由主要路段連通率估計(jì)和貪婪數(shù)據(jù)轉(zhuǎn)發(fā)2個階段構(gòu)成。

2.1 路段連通率估計(jì)

令V(i)d表示在時(shí)間段[t,t+Δt]內(nèi)通過路段i、t方向d上的總的車輛數(shù)，其也稱為總流量數(shù)。Δt= 15min 。

可依式（1）計(jì)算在時(shí)間段Δt內(nèi)的平均車輛數(shù)單位為每分秒車輛數(shù)，即

式中：d表示方向的布爾變量，其定義如圖3所示。

接下來，推導(dǎo)以下兩種情況下的路段連通情況：1）理想情況。在理想情況下，假定車輛以平均速度均勻行駛在道路上，則在路段i上平均車輛數(shù)為

因此，在每個矩形格內(nèi)的平均車輛數(shù)為

式中cR為車輛的通信半徑。

當(dāng)在矩形格有1輛車，車輛就能夠轉(zhuǎn)發(fā)數(shù)據(jù)。換而言之，當(dāng)路段i上的方向平均車輛數(shù)大于1，則該路段是連通的，因此就能夠通過該路段轉(zhuǎn)發(fā)數(shù)據(jù)。

2）非理想情況。假定在該路段上的車輛仍以均速行駛，但車輛并不服從均勻分布，而是服從泊松分布。令為平均達(dá)到率，則有

因此，在時(shí)間段[t,t+Δt]內(nèi)，路段i方向d上的平均車輛密度為

由于到達(dá)該路段上的車輛服從泊松分布，在每個矩形格內(nèi)的車輛數(shù)服從式（6）所示的概率質(zhì)量函數(shù)（probability mass function, PMF），即

2.2 數(shù)據(jù)轉(zhuǎn)發(fā)策略

為了抑制因數(shù)據(jù)轉(zhuǎn)發(fā)所引起的廣播風(fēng)暴問題，只在路徑搜索區(qū)域內(nèi)傳輸路徑發(fā)現(xiàn)消息。由源車輛和目的車輛的相對移動構(gòu)建路徑搜索區(qū)，如圖4所示。

圖4 路徑搜索區(qū)域示例

具體而言，將源車輛的移動方向作為x軸，由源車輛和目的車輛的移動軌跡構(gòu)建路徑搜索區(qū)域。不失一般性，路徑搜索區(qū)域越大，可選擇的路徑就越多。對路徑搜索區(qū)域進(jìn)行擴(kuò)展，圖4中的斜線陰影部分就是擴(kuò)展后的區(qū)域。

最后，可歸納執(zhí)行TVDR路由的步驟如下：

步驟1：源節(jié)點(diǎn)沿著路段，并在2個方向上傳輸路徑請求消息（path request, PREQ）。PREQ以HELLO消息格式為基礎(chǔ)，并進(jìn)行修改，如圖5所示。

圖5 PREQ消息格式

PREQ消息包括源車輛的速度、目的節(jié)點(diǎn)身份標(biāo)識號（identity, ID）以及路徑搜索區(qū)、轉(zhuǎn)發(fā)路段序列號、路段連通率。TVDR路由采用貪婪方式轉(zhuǎn)發(fā)PREQ，直到PREQ傳輸至位于每個路段交叉口的路邊單位（road side unit, RSU）。

步驟2：當(dāng)RSU接收到PREQ，就進(jìn)入路徑發(fā)現(xiàn)階段。RSU從PREQ消息中提取目的節(jié)點(diǎn)ID，判斷是否在自己覆蓋的范圍內(nèi)。如果目的節(jié)點(diǎn)在自己的覆蓋范圍內(nèi)，RSU就向該目的節(jié)點(diǎn)傳輸PREQ消息；否則，RSU就更新PREQ中路段序列號，并向下1個RSU轉(zhuǎn)發(fā)。

步驟3：目的節(jié)點(diǎn)在預(yù)定的等待時(shí)間Twaiting內(nèi)，可能接收到多條PREQ消息。換而言之，可能存在多條從源節(jié)點(diǎn)至目的節(jié)點(diǎn)路徑。假定存在m條路徑，目的節(jié)點(diǎn)就從中選擇具有最高連通率的路徑傳輸數(shù)據(jù)。然后，沿著該路徑向源節(jié)點(diǎn)回復(fù)確認(rèn)消息ACK。

3 性能分析

3.1 仿真環(huán)境

利用矩陣實(shí)驗(yàn)室（matrix laboratory, MATLAB）軟件建立仿真平臺，分析TVDR路由的性能。引用曼哈頓（Manhattan）移動模型[12]產(chǎn)生車輛的移動軌跡數(shù)據(jù)，如圖6所示。在1 000 m×1 000 m 城市區(qū)域內(nèi)部署100～1 000輛車。每個路段的長度為200 m，車輛相關(guān)的仿真參數(shù)如表1所示。Manhattan為網(wǎng)格場景，場景區(qū)域面積為1 km2，每次實(shí)驗(yàn)獨(dú)立重復(fù)30次，取平均值作為最終的實(shí)驗(yàn)數(shù)據(jù)。

圖6 Manhattan移動模型示例

表1 仿真參數(shù)

為了更好地分析TVDR路由的性能，選擇文獻(xiàn)[6]的AODV路由作為參照，并對比它們的控制開銷和吞吐量性能。

3.2 吞吐量

首先分析理想情況和非理想情況下的吞吐量，分別如圖7（a）、圖7（b）所示。從圖7可知，車輛數(shù)的增加，使平均吞吐量呈上升趨勢，但當(dāng)車輛增加到一定數(shù)量后，吞吐量上升緩慢。原因在于：最初車輛的增加，可大幅地提升數(shù)據(jù)傳輸量；但當(dāng)車輛增加到一定量后，車輛數(shù)的增加會提高網(wǎng)絡(luò)的擁塞率，從而抑制了數(shù)據(jù)傳輸成功率。

圖7 吞吐量

從圖7可知，相比于AODV路由，提出的TVDR路由的吞吐量得到有效提高。這主要是因?yàn)門VDR路由利用路段連通率傳輸數(shù)據(jù)，提高了數(shù)據(jù)傳輸成功率。

3.3 系統(tǒng)開銷

最后，分析理想情況和非理想情況下的系統(tǒng)開銷。系統(tǒng)開銷是指每傳輸1條消息所產(chǎn)生的控制消息數(shù)，分別如圖8（a）、圖8（b）所示。

圖8 系統(tǒng)開銷

從圖8可知，在理想和非理想2種情況下，相比于AODV，TVDR路由能有效地控制系統(tǒng)開銷。例如，在理想情況下，當(dāng)車輛數(shù)為1 000時(shí)，TVDR路由的開銷為13，而AODV路由的開銷達(dá)到約170。原因在于AODV路由采用泛洪策略傳輸控制消息。對比圖8（a）、圖8（b）不難發(fā)現(xiàn)，非理想情況下的TVDR路由的開銷大于理想情況。

4 結(jié)束語

本文對車載網(wǎng)絡(luò)的數(shù)據(jù)傳輸問題進(jìn)行分析，提出交通流量感知的數(shù)據(jù)路由TVDR。TVDR路由從路段角度選擇路徑：先依據(jù)車輛的流量信息，推導(dǎo)路段連通率，再依據(jù)連通率選擇數(shù)據(jù)傳輸?shù)穆窂?。仿真結(jié)果表明，相比于AODV路由，提出的TVDR路由可有效提高系統(tǒng)吞吐量，并能有效減少控制系統(tǒng)開銷。