公交數(shù)據(jù)驅(qū)動(dòng)的城市車(chē)聯(lián)網(wǎng)轉(zhuǎn)發(fā)機(jī)制

唐曉嵐 頊 堯 陳文龍

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

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

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

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

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

本文的主要貢獻(xiàn)有3個(gè)方面:

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

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

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

1 相關(guān)工作

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

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

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

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

2 公交站點(diǎn)拓?fù)浣⒑吐窂竭x擇

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

Table 1 The Main Symbols and Their Descriptions in This Paper

構(gòu)建公交站點(diǎn)拓?fù)鋱DG=(V,E)，其中頂點(diǎn)表示公交站點(diǎn)，頂點(diǎn)之間的邊表示存在公交線(xiàn)路連續(xù)經(jīng)過(guò)這2個(gè)站點(diǎn).換句話(huà)說(shuō)，若存在至少一條公交線(xiàn)路的站點(diǎn)序列Pm滿(mǎn)足〈si,sj〉?Pm，則在si和sj之間連邊.由于絕大多數(shù)公交線(xiàn)路的去程和回程所經(jīng)過(guò)的站點(diǎn)相同且站點(diǎn)順序互為逆序，而本文所設(shè)計(jì)的公交站點(diǎn)拓?fù)鋱D為無(wú)向圖，因此針對(duì)每個(gè)公交線(xiàn)路，僅取其一個(gè)行駛方向的站點(diǎn)序列來(lái)構(gòu)建公交站點(diǎn)拓?fù)鋱D.

(1)

顯然，預(yù)期公交數(shù)量越大，在2個(gè)站點(diǎn)之間通過(guò)公交車(chē)轉(zhuǎn)發(fā)數(shù)據(jù)的成功率越高.此外，站點(diǎn)si和sj之間的道路距離記為Di,j，距離越大，意味著在這2個(gè)站點(diǎn)之間的數(shù)據(jù)傳輸時(shí)延可能越長(zhǎng).綜合預(yù)期公交車(chē)數(shù)量和距離的影響，對(duì)于公交站點(diǎn)拓?fù)鋱D中站點(diǎn)si和sj之間的邊，其權(quán)值可計(jì)算為

(2)

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

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

Fig. 1 An instance of scenario and its bus stop topology圖1 場(chǎng)景和公交站點(diǎn)拓?fù)鋱D示例

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

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

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

3 公交車(chē)的數(shù)據(jù)轉(zhuǎn)發(fā)策略

3.1 骨干公交和候補(bǔ)公交轉(zhuǎn)發(fā)

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

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

(3)

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

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

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

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

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

3.2 私家車(chē)多跳鏈路傳輸

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

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

為了提高多跳鏈路的傳輸性能，在下一跳節(jié)點(diǎn)選擇時(shí)，計(jì)算當(dāng)前車(chē)輛z和鄰居車(chē)輛w之間鏈路的傳輸指標(biāo):

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

(4)

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

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

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

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

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

Table 2 Simulation Environment Configurations

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

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

Fig. 6 The distributions of bus lines and bus stops圖6 公交線(xiàn)路和公交站點(diǎn)的分布情況

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

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

4.2 結(jié)果分析

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

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

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

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

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

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

如圖9所示，較大的通信半徑導(dǎo)致數(shù)據(jù)包到達(dá)目的地所需的傳輸跳數(shù)更少.當(dāng)通信半徑大于500 m時(shí)，BUF的傳輸跳數(shù)大于BTSC和BLER，這是因?yàn)锽UF盡可能利用多跳中繼來(lái)傳遞更多的數(shù)據(jù)包，盡管如此，考慮到BUF具有較高的傳輸成功率和較短的傳輸延遲，相對(duì)較大的傳輸開(kāi)銷(xiāo)是可以接受的.

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

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

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

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

4.3 參數(shù)分析

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

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

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

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

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

2) 權(quán)值的影響

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

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

為進(jìn)一步精確α取值，在第2輪數(shù)據(jù)篩選中，α取值在[0.6,0.8]范圍內(nèi)且以0.025為步進(jìn)長(zhǎng)度，實(shí)驗(yàn)結(jié)果如表3所示.

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

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

5 總 結(jié)

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

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