唐曉嵐 頊 堯 陳文龍

(首都師范大學信息工程學院 北京 100048)

在城市車聯(lián)網(wǎng)(vehicular ad hoc networks, VANETs)[1-3]中，裝載有智能感知設備的車輛能夠獲取車輛速度、加速度、與周邊車輛的距離、超車預警等信息.在行駛過程中通過車輛與車輛(vehicle to vehicle, V2V)通信[4-5]以及車輛與路邊基礎設施(vehicle to infrastructure, V2I)通信[6]，將感知到的信息傳輸給周圍的其他車輛或者路邊單元，實現(xiàn)車輛之間的互聯(lián)互通，進而支持各種智慧交通應用，例如事故預警、路況廣播、廣告推送和資源分享等，提高駕駛的安全性、舒適性和便捷性[7].國際上V2V和V2I通信標準主要有美國提出的專用短程通信標準(dedicated short range communications, DSRC)[8]，近年來我國正在加速發(fā)展LTE-V2X(vehicle to everything)技術[9].

車聯(lián)網(wǎng)的應用大致分為安全類應用和非安全類應用，不同種類的應用對服務質量的要求不同[10].安全類應用與交通安全密切相關，包括事故預警、車輛輔助控制等，這類應用對數(shù)據(jù)的實時性要求較高，對時延較為敏感.非安全類應用主要用于交通疏導和信息共享服務，包括路況信息擴散、多媒體資源分享等，這類應用對數(shù)據(jù)實時性要求相對較小，能夠接受一定的時延.本文關注于非安全類應用，通過公交車的存儲轉發(fā)，實現(xiàn)城市車聯(lián)網(wǎng)的數(shù)據(jù)傳輸.

城市交通狀況的復雜多變和私家車駕駛行為難以預測等特點導致車車通信的間歇性連接，網(wǎng)絡拓撲結構高度動態(tài)，通信鏈路不穩(wěn)定，進而影響了車聯(lián)網(wǎng)的數(shù)據(jù)傳輸性能[11].一些研究人員通過部署路邊基礎設施，提供較車載設備更為強大的通信能力和數(shù)據(jù)處理能力，從而改善數(shù)據(jù)轉發(fā)[12-14]；還有一些學者利用路邊停放的車輛來協(xié)助數(shù)據(jù)轉發(fā)[15-16].但是，在城市內大規(guī)模部署路邊基礎設施成本高昂，實施難度大，從市政規(guī)劃到投入使用的預期時間長；而路邊停放的車輛數(shù)量有限，且車輛狀態(tài)在停止和行駛之間的頻繁切換會影響這些方案的性能.相較而言，公交車作為重要的城市公共交通設施，其路線涵蓋了城市中大部分主要道路，并且公交線路固定、發(fā)車時間規(guī)律，有助于按照預期路徑傳輸車聯(lián)網(wǎng)數(shù)據(jù)[17].因此，如何利用已有公交線路有效地轉發(fā)數(shù)據(jù)是城市車聯(lián)網(wǎng)數(shù)據(jù)傳輸?shù)闹匾芯空n題.

本文提出公交數(shù)據(jù)驅動的城市車聯(lián)網(wǎng)轉發(fā)機制，稱為BUF(bus-data driven forwarding scheme).首先構建公交站點拓撲圖，以目標場景中所有公交站點為頂點，依據(jù)是否有公交線路連續(xù)經(jīng)過2個站點決定頂點之間是否連邊，綜合相鄰站點之間的預期公交車數(shù)量和距離計算邊的權值.然后使用迪杰斯特拉算法計算從源站點到目標站點之間權值最小的路徑.當數(shù)據(jù)沿該路徑傳輸時，依據(jù)鄰居公交與最優(yōu)路徑的后續(xù)站點重合度，優(yōu)先選擇重合度高的公交做為骨干公交，實現(xiàn)數(shù)據(jù)轉發(fā).當不存在骨干公交時，選擇后續(xù)將經(jīng)過最優(yōu)路徑上的下一站點的公交做為候補公交，完成數(shù)據(jù)轉發(fā).若骨干公交和候補公交都不存在，則通過私家車建立多跳鏈路找到合適的公交轉發(fā)節(jié)點.

本文的主要貢獻有3個方面:

1) 構建公交站點拓撲圖，邊權值的計算綜合考慮相鄰站點之間的預期公交車數(shù)量和距離，公交車越多、距離越短，則數(shù)據(jù)傳輸成功率越高、時延越短，即邊權值越小，傳輸性能越好，進而通過迪杰斯特拉算法計算從源站點到目的站點的最優(yōu)傳輸路徑；

2) 設計數(shù)據(jù)轉發(fā)策略，依據(jù)后續(xù)站點重合度，優(yōu)先選擇骨干公交轉發(fā)數(shù)據(jù)，其次選擇未來經(jīng)過下一站點的候補公交，再次使用私家車建立多跳鏈路尋找合適的公交節(jié)點，該策略保證了快速且穩(wěn)定地沿最優(yōu)路徑轉發(fā)數(shù)據(jù)；

3) 實驗使用北京市真實路網(wǎng)和公交數(shù)據(jù)來建立城市車聯(lián)網(wǎng)場景，結果表明BUF與其他方案相比具有更高的傳輸成功率和更短的時延.

1 相關工作

現(xiàn)有的車聯(lián)網(wǎng)研究主要利用車載節(jié)點的協(xié)作來提升數(shù)據(jù)傳輸性能.Wang等人[18]提出基于車輛之間關聯(lián)性的數(shù)據(jù)轉發(fā)策略，依據(jù)車輛之間關聯(lián)性計算數(shù)據(jù)轉發(fā)概率,確定最優(yōu)數(shù)據(jù)傳輸路徑.Tang等人[19]利用模糊邏輯，綜合車輛的速度變化率、速度優(yōu)先度和信道質量等因素計算傳輸優(yōu)先級，進而在每個路段內選擇骨干節(jié)點來傳輸數(shù)據(jù).針對車載多播傳輸，Hsieh等人[20]構建以源車輛為根的多播路由樹，依據(jù)該路由樹實現(xiàn)源節(jié)點向目的節(jié)點的多播傳輸；Souza等人[21]在MAODV協(xié)議的基礎上，利用車輛的移動信息來構建更加穩(wěn)定的多播樹結構，并利用蟻群算法來優(yōu)化多播樹.文獻[22]根據(jù)當前車流情況和可預測的車輛移動規(guī)律，估算不同道路的車輛密度，選擇具有最短傳輸延遲的道路，沿該道路轉發(fā)數(shù)據(jù).文獻[23]依據(jù)路徑連通壽命、平均鄰居數(shù)和路徑跳數(shù)來計算路徑權值，選擇權值大的可靠路徑傳輸.然而，私家車的行駛路線難以預測，車輛的高速移動和間歇連通導致路徑選擇更新頻繁，維護困難.

部分研究利用固定的路邊基礎設施來優(yōu)化車聯(lián)網(wǎng)的數(shù)據(jù)轉發(fā).文獻[24]令源車輛將數(shù)據(jù)發(fā)送給附近的路邊單元，再利用路邊單元之間的有線網(wǎng)絡將消息轉發(fā)到目的車輛附近的路邊單元,并最終傳遞給目的車輛.該方法的消息傳輸延遲主要取決于車輛在行駛過程中遇到公共的路邊單元的頻率，因此需要密集部署路邊基礎設施.Tang等人[25]將數(shù)據(jù)在路邊單元中的分布式存儲問題轉化為二部圖的穩(wěn)定匹配問題，實現(xiàn)較高的數(shù)據(jù)響應率和較短的傳輸時延.然而，路邊基礎設施的部署成本較高，實施難度較大，影響著相關方案的推廣和落地.

在公交輔助數(shù)據(jù)傳輸?shù)腣ANET體系結構中，公交車不僅是通信節(jié)點，而且是決定數(shù)據(jù)轉發(fā)策略的路由節(jié)點.一些研究通過分析公交路線信息或挖掘公交歷史軌跡，建立公交線路之間的關系，據(jù)此選擇一系列公交節(jié)點將數(shù)據(jù)從源節(jié)點傳輸?shù)侥康墓?jié)點.在文獻[26]中，Zhang等人提出了以公交系統(tǒng)為主干的路由協(xié)議，通過收集和分析公交車實際軌跡，挖掘公交系統(tǒng)的社區(qū)屬性，將聯(lián)系頻繁的公交線路劃分到一個社區(qū)，進而設計社區(qū)內部和社區(qū)之間的路由方案，完成數(shù)據(jù)傳輸.在文獻[27]中Sun等人依據(jù)公交軌跡在街道出現(xiàn)的概率建立路徑圖，計算街道一致性概率和路徑一致性概率2個指標，從而選擇公交密度大且不易偏離方向的數(shù)據(jù)傳輸路徑.在文獻[28]中，Chang等人旨在實現(xiàn)具有隱私保護的公交網(wǎng)絡高效路由，每個報文與一張路由圖關聯(lián)，而非一條具體的路徑，從而使得路由動態(tài)適應城市交通狀況，并對中繼節(jié)點隱藏與用戶和目的地相關的隱私信息.

綜上所述，現(xiàn)有使用公交數(shù)據(jù)的城市車聯(lián)網(wǎng)路由算法主要基于歷史軌跡數(shù)據(jù)或依靠路邊基礎設施的支持，而公交站點和公交線路之間的關系沒有被充分挖掘.因此本文旨在優(yōu)化以公交站點為頂點的路徑選擇，并探索公交車的轉發(fā)策略來提升車聯(lián)網(wǎng)傳輸效率.

2 公交站點拓撲建立和路徑選擇

在數(shù)據(jù)轉發(fā)機制BUF中，首先建立公交站點拓撲圖，計算從源站點到目的站點的最優(yōu)傳輸路徑；然后沿該路徑，依據(jù)數(shù)據(jù)轉發(fā)策略，選擇合適的公交車輛進行數(shù)據(jù)轉發(fā).本節(jié)將詳細闡述公交站點拓撲圖的建立以及最優(yōu)路徑的選擇過程.本文所使用的主要符號及其意義如表1所示.

Table 1 The Main Symbols and Their Descriptions in This Paper

構建公交站點拓撲圖G=(V,E)，其中頂點表示公交站點，頂點之間的邊表示存在公交線路連續(xù)經(jīng)過這2個站點.換句話說，若存在至少一條公交線路的站點序列Pm滿足〈si,sj〉?Pm，則在si和sj之間連邊.由于絕大多數(shù)公交線路的去程和回程所經(jīng)過的站點相同且站點順序互為逆序，而本文所設計的公交站點拓撲圖為無向圖，因此針對每個公交線路，僅取其一個行駛方向的站點序列來構建公交站點拓撲圖.

(1)

顯然，預期公交數(shù)量越大，在2個站點之間通過公交車轉發(fā)數(shù)據(jù)的成功率越高.此外，站點si和sj之間的道路距離記為Di,j，距離越大，意味著在這2個站點之間的數(shù)據(jù)傳輸時延可能越長.綜合預期公交車數(shù)量和距離的影響，對于公交站點拓撲圖中站點si和sj之間的邊，其權值可計算為

(2)

其中，α是預期公交車數(shù)量的權值且0<α<1，max(F)和min(F)分別表示拓撲圖中所有相鄰站點間的預期公交車數(shù)量F的最大值和最小值，max(D)和min(D)分別表示所有相鄰站點間距離D的最大值和最小值.函數(shù)max()和min()用于對Fi,j和Di,j歸一化，由于Fi,j與Qi,j負相關而Di,j與Qi,j正相關，故其歸一化方法不同.邊權值Qi,j越小，則該路段的傳輸能力越強.

舉例，圖1(a)所示場景中有12個公交站點和7條公交線路，相應的公交站點拓撲圖如圖1(b)所示.拓撲圖中頂點代表12個公交站點，依據(jù)圖1(a)中公交線路所經(jīng)過的站點信息連邊.以公交線路b1為例，其依次經(jīng)過站點s1,s6和s11，因此節(jié)點s1和s6以及s6和s11之間連邊.既經(jīng)過站點s1又經(jīng)過站點s6的公交線路為C1∩C6={b1,b3,b5}∩{b1,b5,b6}={b1,b5}，若b1和b5在單位時間內(例如10 min)發(fā)車頻率均為2，則從站點s1到s6的道路上預期公交車數(shù)量為F1,6=4.進而將F1,6和D1,6歸一化并加權得到邊權值Q1,6.

Fig. 1 An instance of scenario and its bus stop topology圖1 場景和公交站點拓撲圖示例

當任意車載節(jié)點需要傳輸數(shù)據(jù)時，若數(shù)據(jù)的目的地在其通信半徑以內，則直接將數(shù)據(jù)發(fā)送到目的地；否則，將數(shù)據(jù)發(fā)往最近的公交站點.以該站點為源站點，以距離目的地最近的公交站點為目的站點，在公交站點拓撲圖中，使用迪杰斯特拉算法計算從源站點到目的站點的權值最小的路徑R，以該路徑為數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑.接下來依據(jù)數(shù)據(jù)轉發(fā)策略，選擇合適的公交車沿最優(yōu)路徑將數(shù)據(jù)傳輸?shù)侥康牡?針對最優(yōu)路徑的計算，本文將傳輸路徑規(guī)劃問題轉化為公交站點拓撲圖中最小權值路徑計算問題.該問題是圖論中的經(jīng)典問題，能夠通過迪杰斯特拉算法求解.本文暫未對迪杰斯特拉算法做改進和創(chuàng)新，未來的研究工作可以深入探索更為高效的最小權值路徑求解算法.

以圖1(b)為例，從源站點s3到目的站點s10的最優(yōu)路徑為R=〈s3,s6,s9,s10〉，該路徑在圖1(a)中以深色背景道路展示.

從源站點到目的站點的最優(yōu)路徑優(yōu)先使用權值較小的邊，可能導致該邊被多個數(shù)據(jù)流量占用.當傳輸數(shù)據(jù)過多時，算法將流量集中于某些邊，造成擁塞導致傳輸效率下降.為解決該問題，本文設計了擁塞處理機制.當車輛轉發(fā)數(shù)據(jù)失敗時，若兩車仍處于通信范圍內，則攜帶數(shù)據(jù)的車輛再次嘗試轉發(fā)數(shù)據(jù).若3次嘗試均失敗，則判定該路段上產(chǎn)生擁塞，重新為數(shù)據(jù)包規(guī)劃路徑，避開當前擁塞路段.同時將擁塞消息廣播給附近的車輛，其他車輛接收到擁塞消息后只進行一次數(shù)據(jù)傳輸?shù)膰L試，若失敗則立即重新規(guī)劃傳輸路徑.擁塞消息具有一定的有效期，有效期結束則恢復原有的路徑規(guī)劃.擁塞處理機制有助于加速數(shù)據(jù)轉發(fā)和緩解擁塞狀況.

3 公交車的數(shù)據(jù)轉發(fā)策略

3.1 骨干公交和候補公交轉發(fā)

當一個公交車載節(jié)點攜帶數(shù)據(jù)到達站點si時，稱該節(jié)點為當前公交、該站點為當前站點，接下來預期沿著最優(yōu)路徑R將數(shù)據(jù)傳輸?shù)较乱粋€站點sj.

當前公交計算在站點si和sj之間轉發(fā)數(shù)據(jù)的骨干公交集合，即KBi,j={bg|〈si,sj〉?Pg}.由于骨干公交將到達的站點為R中下一個站點sj，因此，相較其他公交，骨干公交能夠以更高的概率和更短的時延沿最優(yōu)路徑傳輸數(shù)據(jù).若當前公交的通信半徑內存在多個骨干公交(稱為鄰居骨干公交)，則計算每個鄰居骨干公交與最優(yōu)路徑的后續(xù)站點重合度:

(3)

后續(xù)站點重合度反映了骨干公交的未來行駛路線和最優(yōu)路徑的重疊程度，重合度越高意味著骨干公交沿最優(yōu)路徑轉發(fā)數(shù)據(jù)的距離越遠，因此當前公交選擇后續(xù)站點重合度最大的鄰居骨干公交轉發(fā)數(shù)據(jù).當存在多個具有最大重合度的骨干公交時，選擇發(fā)車頻率δm最大的節(jié)點做為下一跳.

在圖1(a)場景中，數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑為R=〈s3,s6,s9,s10〉，當前站點是s6時，沿最優(yōu)路徑的下一個站點是s9.經(jīng)過s6的公交線路集為C6={b1,b5,b6}，b1經(jīng)過的站點序列為P1=〈s1,s6,s11〉，b5的站點序列為P5=〈s1,s6,s9,s7,s2〉，b6的站點序列為P6=〈s3,s6,s9,s10〉.從s6到s9的骨干公交集合是KB6,9={b5,b6}.若同時存在b5和b6線路的鄰居骨干公交，則計算Y5=2和Y6=3，故優(yōu)先選擇b6公交轉發(fā)數(shù)據(jù).當數(shù)據(jù)繼續(xù)傳輸至站點s9時，骨干公交集合為KB9,10={b6}，若不存在b6線路的鄰居骨干公交，由于b2也去往預期的下一站點s10，故選擇候補公交SB9,10={b2}來轉發(fā)數(shù)據(jù).

候補公交通常不沿最優(yōu)傳輸路徑行駛，繞行導致傳輸代價升高.為了避免代價過高的轉發(fā)，本文為候補公交設計繞行判定策略.分別計算骨干公交和候補公交傳輸數(shù)據(jù)到最優(yōu)路徑上的下一站點的路徑權值，若候補公交的路徑權值大于骨干公交的ρ倍，則判定繞行代價過高，舍棄該候補公交；否則，可以選擇該候補公交轉發(fā)數(shù)據(jù).ρ的取值依據(jù)公交線路規(guī)劃和服務質量需求分析得到，在本文實驗中，ρ=2.

實際應用中可能不存在候補公交的長距離繞行，例如本文實驗中最多繞行3個站點，這是因為最優(yōu)路徑上2個站點之間有公交連續(xù)經(jīng)過，其路徑距離通常不會過長，而城市公交線路的規(guī)劃避免了長距離的繞路.除短距離繞行外，還有部分候補公交無繞行，這源于快速公交和普通公交的路線重疊，例如：普通公交b1和快速公交b2的行駛路線完全相同，但b1比b2停站多，b1經(jīng)過的站點序列為P1=〈s1,s2,s3〉，b2站點序列為P2=〈s1,s3〉，當數(shù)據(jù)從站點s1發(fā)往s3時，普通公交b1是候補公交，其傳輸過程不存在繞路.

在市中心主干道路上傳輸數(shù)據(jù)時，可能存在不同公交線路的傳輸效率相近的情況.考慮到在分布式車聯(lián)網(wǎng)中，每個攜帶數(shù)據(jù)的車載節(jié)點獨立執(zhí)行轉發(fā)決策，難以在全局層面實現(xiàn)分流控制，因此當存在多個優(yōu)先級相同的公交節(jié)點時，攜帶數(shù)據(jù)的節(jié)點執(zhí)行簡單高效的隨機選擇.

3.2 私家車多跳鏈路傳輸

當不存在骨干公交或候補公交時，當前公交利用數(shù)量相對較多的私家車建立多跳鏈路來尋找合適的公交節(jié)點.在圖2場景中，當數(shù)據(jù)傳輸至站點s9時，當前公交的通信范圍內不存在骨干公交或候補公交，此時以該車為起始節(jié)點通過私家車建立多跳鏈路，經(jīng)過探尋在三跳內找到合適的公交轉發(fā)節(jié)點，成功建立多跳鏈路實現(xiàn)數(shù)據(jù)傳輸.

Fig. 2 Establishment of a multi-hop link to find a backbone or supplement bus圖2 構建多跳鏈路尋找骨干公交或候補公交

為了提高多跳鏈路的傳輸性能，在下一跳節(jié)點選擇時，計算當前車輛z和鄰居車輛w之間鏈路的傳輸指標:

NRz,w=(RVz,w+1)×RDz,w×RLz,w，

(4)

其中，RVz,w表示車輛z和車輛w的相對速度值，RVz,w≥0；RDz,w表示車輛z和車輛w的相對行駛方向，同向行駛RDz,w=1，反向行駛RDz,w=0；RLz,w表示車輛z和車輛w的相對位置，若w位于z的前方，則RLz,w=1，否則RLz,w=0.

在多跳鏈路建立過程中，當前車輛總是選擇NRz,w取最小正值的鄰居車輛來轉發(fā)數(shù)據(jù).NRz,w>0保證數(shù)據(jù)只向同向行駛的前方車輛傳遞(排除RDz,w=0或RLz,w=0的情況).當有多個NRz,w為正值的鄰居車輛時，考慮到相對速度小的車輛之間通信鏈路的穩(wěn)定性好，所以優(yōu)先選擇NRz,w較小的車輛轉發(fā)數(shù)據(jù).注意：式(4)使用RVz,w+1是為了避免RVz,w=0的節(jié)點不能被優(yōu)先選擇.

多跳鏈路的建立過程如算法1所示.

當前車輛(攜帶數(shù)據(jù)的公交節(jié)點)發(fā)送HELLO報文來收集鄰居車輛(在其通信范圍內的私家車)的速度和位置信息；據(jù)此計算鄰居車輛的傳輸指標NR，選擇NR取最小正值的車輛作為中繼節(jié)點.當前公交向中繼節(jié)點發(fā)送路徑請求報文ROUTE_REQ，該中繼作為新的當前車輛檢查是否存在鄰居骨干公交，若是則向后續(xù)站點重合度最高的骨干公交發(fā)送ROUTE_REQ報文，骨干公交返回ROUTE_REPLY報文(其中記錄發(fā)送節(jié)點的ID)，當前節(jié)點向上一跳返回ROUTE_REPLY報文；否則，當前車輛檢查是否存在鄰居候補公交，若是，則向任意一個候補公交發(fā)送ROUTE_REQ報文，該候補公交返回ROUTE_REPLY報文，當前節(jié)點向上一跳返回ROUTE_REPLY報文；否則，即不存在合適的鄰居公交，當前車輛重復上述過程，選擇中繼節(jié)點.在多跳鏈路構建的時間閾值內，若起始節(jié)點收到ROUTE_REPLY報文，表示找到了去往公交轉發(fā)節(jié)點的多跳鏈路，則依據(jù)ROUTE_REPLY報文中記錄的沿途各個車載節(jié)點ID，將數(shù)據(jù)發(fā)送到公交節(jié)點.

當數(shù)據(jù)沿最優(yōu)路徑轉發(fā)，通過以上策略無法找到合適的轉發(fā)節(jié)點時，數(shù)據(jù)將由當前公交繼續(xù)攜帶到下一站點.此時數(shù)據(jù)傳輸軌跡偏離了預期的最優(yōu)路徑，因此當前公交以下一站點為源站點，重新計算最優(yōu)路徑，數(shù)據(jù)沿新路徑向目的站點傳輸.在圖1(b)中，當數(shù)據(jù)在源站點s3處被b7公交車攜帶且周圍沒有合適的轉發(fā)節(jié)點時，數(shù)據(jù)被攜帶至下一站點s4，此時偏離了最優(yōu)路徑，因此以s4為源站點重新計算最優(yōu)路徑R=〈s4,s7,s10〉，沿該路徑傳輸數(shù)據(jù).

4 實驗結果與分析

4.1 實驗環(huán)境設置

車聯(lián)網(wǎng)研究最終需要在真實的車輛上安裝車載單元(on-board unit, OBU)來實現(xiàn)車內信息采集和車輛之間通信，并通過對車載單元底層傳輸模塊的重新編碼來支持所提出的傳輸算法，從而實現(xiàn)對算法性能的評估.考慮到車載單元安裝與車內總線等硬件相關，車輛改裝成本高、難度大，且車載單元價格昂貴(大約幾萬元/個)，目前難以實現(xiàn)大規(guī)模部署實驗，因此科研人員一般采用仿真實驗來評估算法性能.本文使用北京市真實路網(wǎng)和公交線路，并選擇合適的網(wǎng)絡參數(shù)，使得仿真實驗的設計盡可能接近真實水平.將來隨著車聯(lián)網(wǎng)的發(fā)展和普及，真實實驗的部署環(huán)境逐步成熟，我們將嘗試真實實驗來驗證算法性能.

實驗場景選自北京市東二環(huán)周圍5 km×4 km的區(qū)域，城市路網(wǎng)信息來自開放的地圖協(xié)作平臺OpenStreetMap[29].場景中包含859個交叉路口、1 989條街道(如圖3所示)、198個公交站點(如圖4所示)以及68條公交線路[30](部分線路如圖4所示).公交發(fā)車間隔為300 s，在3 000 s的仿真時間內公交車總數(shù)為680輛.公交車沿各自固定的公交線路行駛，私家車隨機分布并行駛在道路上.使用道路交通模擬器SUMO 0.30.0[31]生成公交車和私家車的行駛軌跡.依據(jù)2015年北京市交通運行報告[32]，早晚高峰期間全路網(wǎng)車輛平均速度分別為28.1 km/h和25.1 km/h，同時參考相關工作的實驗設計，本文實驗中將車輛速度的區(qū)間范圍設置為10～40 km/h，增加車輛速度的隨機性，以檢驗算法的魯棒性.仿真環(huán)境配置見表2.

Fig. 3 The scenario around the East Second Ring Road in Beijing圖3 北京市東二環(huán)附近的場景

Fig. 4 The road map, the bus stops and a part of bus lines in the scenario圖4 場景中的路網(wǎng)、公交站點和部分公交線路

Table 2 Simulation Environment Configurations

Fig. 5 Distribution of bus lines on main streets圖5 主干街道公交線路分布情況

為了驗證所選場景的可用性，對所有長度大于150 m的主干街道統(tǒng)計其公交線路分布情況，如圖5所示.在710條主干街道中，609條有公交線路經(jīng)過，其中404條街道的公交線路不少于2條，而公交線路不少于5條的街道(即公交密集型街道)有198條，約占街道總數(shù)的28%.圖6(a)展示了途經(jīng)若干個公交站點(x軸)的公交線路數(shù)量(y軸)，反映了公交線路長度的分布情況，可見途經(jīng)3～6個站點的公交線路較多.圖6(b)展示了有若干個公交線路(x軸)通過的公交站點數(shù)量(y軸)，反映了公交站點熱度的分布情況，可見有2～6條線路通過的公交站點較多.

Fig. 6 The distributions of bus lines and bus stops圖6 公交線路和公交站點的分布情況

為了驗證本文提出的數(shù)據(jù)轉發(fā)機制BUF的性能，選擇VANETs中2種公交路由算法BTSC[27]和BLER[33]作為對比方法.在以街道為中心的BTSC算法中，數(shù)據(jù)沿著公交密度高的街道轉發(fā)，2個公交之間的多跳鏈路使用蟻群算法建立.在BLER算法中，以公交線路為頂點，在具有通信機會的不同線路之間連邊，構建無向圖，并根據(jù)通信機會大小，計算每條邊的權值，數(shù)據(jù)傳輸路徑即是無向圖中源點到目的點的最大權值路徑.為了分析骨干公交、候補公交和私家車對BUF轉發(fā)決策的影響，實驗對比分析了BUF的2個變體，分別為BUF-B和BUF-BS.在BUF-B中，僅使用骨干公交轉發(fā)數(shù)據(jù)，未使用候補公交和私家車；在BUF-BS中，使用骨干公交和候補公交轉發(fā)數(shù)據(jù)，未使用私家車.對比BUF和BUF-B能夠分析骨干節(jié)點的作用，對比BUF-B和BUF-BS能夠分析候補公交的影響，對比BUF和BUF-BS能夠看到私家車多跳鏈路的效果.

實驗分析了3個性能指標，包括數(shù)據(jù)包傳輸成功率、平均傳輸時延和平均傳輸跳數(shù).傳輸成功率是指在數(shù)據(jù)包生命期內到達目的地的數(shù)據(jù)包占所有生成數(shù)據(jù)包的比率，傳輸成功率越大表明網(wǎng)絡性能越好.平均傳輸時延是指成功傳輸?shù)臄?shù)據(jù)包從源點到目的地花費的平均時間，傳輸時延越短表明網(wǎng)絡的數(shù)據(jù)傳輸速度快、效率高.平均傳輸跳數(shù)是指成功傳輸?shù)臄?shù)據(jù)包從源點到目的地的平均轉發(fā)次數(shù)，跳數(shù)越少表明網(wǎng)絡的傳輸開銷越小.

4.2 結果分析

當車載節(jié)點的通信半徑取自100 m到800 m時，5種對比方法的傳輸成功率、平均傳輸時延和平均傳輸跳數(shù)分別如圖7～9所示.為了保證實驗結果的可靠性，開展20次獨立重復實驗，計算所有實驗結果的平均值和四分位距(interquartile range, IQR).同時，為了避免在相同橫坐標處不同方法的標記重疊而影響清晰度，在結果圖中將部分標記的位置略做偏移.

Fig. 7 Delivery ratio with different communication radii圖7 傳輸成功率隨通信半徑的變化

如圖7所示，所有方法的傳輸成功率有相同的變化趨勢.隨著通信半徑的增大，數(shù)據(jù)傳輸?shù)某晒β手饾u升高.相較其他方法，本文提出的BUF機制在各種通信半徑下所達到的傳輸成功率最高.由于缺少其他社會車輛的參與，BUF-BS的傳輸成功率低于BUF，可見私家車優(yōu)化傳輸效果明顯.根據(jù)2015年北京市交通運行分析報告[32]，實驗選用的東二環(huán)附近車流量達到每天19萬輛，7:00—22:00平均車流量可達每小時4 500輛，可見實際道路上的私家車密度較大，能夠輔助數(shù)據(jù)傳輸.同時BUF-B的傳輸成功率略低于BUF-BS，說明候補公交有一定的輔助作用.BUF-BS較BUF-B無明顯優(yōu)化效果是因為候補公交的傳輸機會較少，一方面候補公交的優(yōu)先級低于骨干公交，只有不存在骨干公交時才會選擇候補公交；另一方面候補公交通常不沿最優(yōu)路徑行駛，攜帶數(shù)據(jù)的車輛與候補公交的相遇概率小.在BTSC中，通過蟻群算法構建多跳鏈路，該算法的收斂需要一定時間，導致部分多跳鏈路建立失敗，影響了數(shù)據(jù)傳輸.BTSC算法未達到文獻[27]中展示的效果，是因為文獻[27]的實驗場景中公交線路是模擬的，公交車輛密度大且分布均勻，而本文實驗使用真實公交線路，車輛密度小且分布不均勻，算法性能下降.

Fig. 8 Average delivery latency with different communication radii圖8 平均傳輸時延隨通信半徑的變化

Fig. 9 Average number of hops with different radii圖9 平均傳輸跳數(shù)隨通信半徑的變化

在圖8中，隨著通信半徑增加，各個算法的數(shù)據(jù)傳輸時延都明顯縮短.在5個對比算法中，本文提出的BUF機制在不同通信半徑下都達到了最短的傳輸時延.BUF-B和BUF-BS由于缺少私家車建立的多跳鏈路的輔助，傳輸時延比BUF長.

如圖9所示，較大的通信半徑導致數(shù)據(jù)包到達目的地所需的傳輸跳數(shù)更少.當通信半徑大于500 m時，BUF的傳輸跳數(shù)大于BTSC和BLER，這是因為BUF盡可能利用多跳中繼來傳遞更多的數(shù)據(jù)包，盡管如此，考慮到BUF具有較高的傳輸成功率和較短的傳輸延遲，相對較大的傳輸開銷是可以接受的.

綜上所述，本文提出的BUF機制的傳輸成功率相較BTSC和BLER分別提高了約16%和33%，平均傳輸時延比BTSC降低7%，比BLER降低9%，傳輸跳數(shù)略大于對比算法.

為了驗證擁塞處理機制的性能，開展一組對比實驗，統(tǒng)計BUF算法(加入擁塞控制)和BUF-C算法(未加入擁塞控制)的數(shù)據(jù)傳輸成功率，結果如圖10所示：

Fig. 10 The effect of congestion handling scheme on delivery ratio圖10 擁塞處理機制對傳輸成功率的影響

由圖10可知：當網(wǎng)絡中數(shù)據(jù)包較少時，2個算法性能相差不大，BUF的傳輸成功率略高于BUF-C.但隨著發(fā)包數(shù)量的增加，網(wǎng)絡擁塞加重，2個算法的差距不斷增大，BUF較BUF-C傳輸了更多的數(shù)據(jù)包.該實驗說明擁塞處理機制有助于提升數(shù)據(jù)傳輸質量，特別是在網(wǎng)絡流量較大時，該機制能夠降低擁塞對傳輸性能的影響.

4.3 參數(shù)分析

1) 發(fā)車間隔的影響

Fig. 11 The effect of bus departure interval on data transmission圖11 公交發(fā)車間隔對數(shù)據(jù)傳輸?shù)挠绊?/p>

公交車的發(fā)車間隔影響著場景中的公交車規(guī)模，進而影響著車聯(lián)網(wǎng)數(shù)據(jù)傳輸性能.為了進一步研究發(fā)車間隔對本文提出的BUF方案及其變體BUF-B和BUF-BS的影響，將公交發(fā)車間隔分別設置為120 s,240 s,360 s,480 s和600 s，3種機制的數(shù)據(jù)傳輸成功率、平均傳輸時延和平均傳輸跳數(shù)如圖11所示.

Fig. 12 The effect of the value of α on data transmission for BUF圖12 BUF中α取值對數(shù)據(jù)傳輸?shù)挠绊?/p>

如圖11(a)所示，隨著公交發(fā)車間隔的增大，3個方案的傳輸成功率均下降，其中BUF-B和BUF-BS受到的影響較大，這是由于發(fā)車間隔增大導致道路上的公交車密度減小，數(shù)據(jù)轉發(fā)機會減少.同理，在圖11(b)中，當發(fā)車間隔變大，數(shù)據(jù)缺少合適的下一跳轉發(fā)公交，因此被攜帶的時間更長，BUF-B和BUF-BS的傳輸時延變長，而BUF機制通過私家車建立多跳鏈路更快地找到下一跳轉發(fā)公交，因此受發(fā)車間隔影響而導致時延增加的幅度較小.如圖11(c)所示，當發(fā)車間隔較短時，數(shù)據(jù)傳輸?shù)钠骄鴶?shù)較小，這是由于公交節(jié)點的密度較大，使得當前車輛有機會在大量鄰居公交節(jié)點中選擇更合適的下一跳節(jié)點；隨著發(fā)車間隔的增大，當前節(jié)點不得不選擇優(yōu)先度較低的轉發(fā)節(jié)點，導致傳輸跳數(shù)增加.

2) 權值的影響

在式(2)中，預期公交車數(shù)量和站點間距離的權重(α和1-α)的取值直接影響了邊權值的計算，進而影響最優(yōu)路徑的選擇.針對不同應用的服務質量需求，對α的測量執(zhí)行多輪篩選，逐步縮小取值范圍，直到α取值滿足精度要求.本文實驗對α的測量使用2輪篩選，初次篩選為粗篩，將α的取值范圍設為0.1～0.9遞增變化，間隔0.1，相應地，距離的權值1-α從0.9到0.1遞減變化，此時BUF機制的實驗結果見圖12.

由圖12(a)可見，當α取值較小(α<0.7)時，傳輸成功率隨著α變大逐步上升，直到達到峰值(約90%)，表明預期公交車數(shù)量是邊權值計算中的主要因素.當α過大(α=0.8或α=0.9)時，傳輸成功率下降，表明距離因素在轉發(fā)節(jié)點選擇中具有一定的影響.在圖12(b)中，隨著α取值逐漸增大，數(shù)據(jù)傳輸時延逐漸減小.當α=0.7時，傳輸時延達到最小值(約150 s)；當α值繼續(xù)增大時，傳輸時延出現(xiàn)了增大的情形.由圖12(c)可見，當α=0.7時，數(shù)據(jù)傳輸所用跳數(shù)達到最小值(約14跳).因此，該場景的實驗中，α的最佳取值靠近0.7.

為進一步精確α取值，在第2輪數(shù)據(jù)篩選中，α取值在[0.6,0.8]范圍內且以0.025為步進長度，實驗結果如表3所示.

由表3可見，當α=0.725時傳輸成功率最大，當α=0.675時傳輸時延最短，當α=0.7時傳輸跳數(shù)最少.根據(jù)不同的服務質量需求，選取最終的α值，例如以最大化傳輸成功率為目標時，α=0.725.該實驗表明，α值太大或太小都會降低BUF機制的性能，證明了預期公交車數(shù)量和站點間距離對數(shù)據(jù)傳輸?shù)挠绊?，而針對具體應用的理論分析和采樣實驗是選擇合適α值的有效方法.

Table 3 Effect of α in the Range of [0.6,0.8] on Data Transmission

5 總 結

本文提出公交數(shù)據(jù)驅動的城市車聯(lián)網(wǎng)轉發(fā)機制(BUF)，旨在利用公交站點和公交線路等信息選擇傳輸路徑和轉發(fā)節(jié)點，從而提升車聯(lián)網(wǎng)數(shù)據(jù)傳輸性能.首先構造公交站點拓撲圖，以公交站點為頂點，依據(jù)公交線路經(jīng)過的站點序列，在頂點之間連邊，并根據(jù)預期公交車數(shù)量和站點間距離計算邊權值，進而由迪杰斯特拉算法計算權值最小的路徑做為最優(yōu)路徑.為了保證數(shù)據(jù)沿最優(yōu)路徑傳輸，優(yōu)先選擇后續(xù)站點重合度最高的骨干公交轉發(fā)數(shù)據(jù)；當沒有骨干公交時，后續(xù)將經(jīng)過期望的下一站點的候補公交做為轉發(fā)節(jié)點；當骨干公交和候補公交都不存在時，由私家車建立多跳鏈路來尋找合適的公交轉發(fā)節(jié)點.該轉發(fā)策略增加了數(shù)據(jù)快速沿最優(yōu)路徑傳輸?shù)臋C會.使用北京市真實路網(wǎng)和公交線路的仿真結果表明，與其他算法相比，BUF機制具有較高的傳輸成功率和較短的傳輸時延.

將公交線路數(shù)據(jù)與車輛軌跡大數(shù)據(jù)結合，有望進一步優(yōu)化車聯(lián)網(wǎng)數(shù)據(jù)轉發(fā)，未來的研究工作可以探索利用人工智能方法來解決該問題.