城市車載網(wǎng)絡(luò)的路邊單元部署機(jī)制
2021-03-21 05:11:58陳瀟然唐曉嵐陳文龍柴明璐
小型微型計(jì)算機(jī)系統(tǒng) 2021年3期
陳瀟然，唐曉嵐，陳文龍,柴明璐
(首都師范大學(xué) 信息工程學(xué)院，北京 100048)
1 引 言
車載自組織網(wǎng)絡(luò)(Vehicular Ad hoc NETworks,VANETs)簡(jiǎn)稱車載網(wǎng)絡(luò)，是一種專用于汽車通信領(lǐng)域的特殊移動(dòng)自組織網(wǎng)絡(luò)，主要是由固定部署的路邊單元(RoadSide Units，RSUs)和安裝有車載設(shè)備的車輛節(jié)點(diǎn)構(gòu)成[1]，其特點(diǎn)和挑戰(zhàn)體現(xiàn)在車輛節(jié)點(diǎn)移動(dòng)速度快，網(wǎng)絡(luò)拓?fù)涓叨葎?dòng)態(tài)以及通信連接頻繁中斷[2]等方面.作為智能交通系統(tǒng)的重要構(gòu)成部分，車載網(wǎng)絡(luò)通過(guò)具有感知和通信能力的車載單元，依據(jù)專用短程通信標(biāo)準(zhǔn)實(shí)現(xiàn)車輛與車輛通信(Vehicle to Vehicle,V2V)[3]以及車輛與路邊基礎(chǔ)設(shè)施通信(Vehicle to Infrastructure,V2I)[4]，支持交通相關(guān)數(shù)據(jù)在車輛之間傳輸，提高車輛行駛過(guò)程中的安全性[5]、可靠性[6]和道路交通的運(yùn)行效率，同時(shí)減少了交通運(yùn)輸對(duì)環(huán)境的污染，節(jié)約能源，提高了資源利用率[7].
V2I的通信方式改變了傳統(tǒng)交通系統(tǒng)中車輛和道路之間無(wú)法進(jìn)行實(shí)時(shí)信息交互的現(xiàn)狀，實(shí)現(xiàn)了車與路的協(xié)同運(yùn)行.作為VANET的路邊基礎(chǔ)設(shè)施，RSU具有較車載節(jié)點(diǎn)更為強(qiáng)大的計(jì)算、存儲(chǔ)和通信能力[8]，支持遠(yuǎn)程無(wú)線數(shù)據(jù)傳輸和互聯(lián)網(wǎng)接入，在很大程度上緩解了車載網(wǎng)絡(luò)的拓?fù)浞指钐匦?，通過(guò)與行駛的車輛進(jìn)行信息交互，輔助車輛獲取道路交通狀況等信息，同時(shí)加速車輛的信息發(fā)布，改善車輛節(jié)點(diǎn)之間的通信質(zhì)量和降低通信延遲.
RSU的部署位置直接影響其對(duì)車輛通信需求的服務(wù)能力和車路通信的質(zhì)量，在傳統(tǒng)的智能交通系統(tǒng)中，路邊單元的部署通常采用簡(jiǎn)單易行的均勻或隨機(jī)部署方案，覆蓋效益低，造成資源浪費(fèi).另外，RSU部署受多方面條件約束：1)RSU部署受道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和地理特征的影響[9]，城市場(chǎng)景的路網(wǎng)結(jié)構(gòu)復(fù)雜，沿道路部署RSU的候選部署位置多，選擇最優(yōu)部署位置較為困難；2)車輛移動(dòng)特性影響RSU部署，當(dāng)車輛進(jìn)入RSU通信覆蓋范圍內(nèi)時(shí)，RSU能夠?yàn)檐囕v服務(wù)[10]，獲得覆蓋效益；3)RSU部署需考慮成本，大規(guī)模部署帶來(lái)較高的安裝與維護(hù)成本.因此，在復(fù)雜的二維城市路網(wǎng)中，如何選擇最優(yōu)的路邊單元部署位置是車載網(wǎng)絡(luò)研究的難題.
本文提出基于路口優(yōu)先級(jí)和部署均勻性的路邊單元部署機(jī)制PUD，綜合城市路網(wǎng)拓?fù)浣Y(jié)構(gòu)和車輛移動(dòng)規(guī)律，依據(jù)車流密度、連接中心性和公共交通線路數(shù)，計(jì)算交叉路口的部署優(yōu)先級(jí)，優(yōu)先將RSU部署在車流量大、在路網(wǎng)拓?fù)渲衅鹬匾饔玫慕徊媛房?，從而保證路邊單元在車載網(wǎng)絡(luò)中的傳輸服務(wù)質(zhì)量.同時(shí)，為了降低部署成本，以均勻部署為目標(biāo)制定約束規(guī)則，包括位置約束、范圍約束、優(yōu)先級(jí)約束和覆蓋約束，符合約束條件的交叉路口優(yōu)先部署路邊單元.使用北京市出租車軌跡數(shù)據(jù)的車載網(wǎng)絡(luò)實(shí)驗(yàn)表明，與其他路邊單元部署機(jī)制相比，PUD機(jī)制的部署成本更低，覆蓋率更大.
本文的主要貢獻(xiàn)包括以下3個(gè)方面：
1)設(shè)計(jì)路網(wǎng)模型和覆蓋模型，將RSU部署問(wèn)題轉(zhuǎn)化為對(duì)目標(biāo)區(qū)域內(nèi)交叉路口的覆蓋問(wèn)題；
2)本文設(shè)計(jì)的部署機(jī)制以交叉路口集合作為RSU的候選部署位置，以交叉路口優(yōu)先級(jí)作為部署點(diǎn)選擇的主要依據(jù)，優(yōu)先級(jí)的計(jì)算方法綜合考慮車輛移動(dòng)規(guī)律和路網(wǎng)拓?fù)洌?/p>
3)兼顧部署成本和覆蓋效益兩大目標(biāo)，在選擇RSU部署位置的過(guò)程中，設(shè)置4條部署約束規(guī)則，在保證RSU覆蓋效益的基礎(chǔ)上降低部署成本.
2 相關(guān)工作
在車載網(wǎng)絡(luò)架構(gòu)中，RSU一般被部署在路邊或者交叉路口，用來(lái)提高數(shù)據(jù)的傳輸速率和請(qǐng)求的響應(yīng)率，進(jìn)而提升網(wǎng)絡(luò)的連通性和整體的服務(wù)性能.RSU通常采用靜態(tài)部署，部署位置一旦確定，在整個(gè)服務(wù)期間固定不變，因此前期的部署決策尤為重要.
目前關(guān)于RSU部署的文獻(xiàn)可根據(jù)應(yīng)用場(chǎng)景和部署目標(biāo)進(jìn)行分類.車載網(wǎng)絡(luò)一般有兩種典型的應(yīng)用場(chǎng)景，即高速公路場(chǎng)景和城市道路場(chǎng)景.高速公路場(chǎng)景較為簡(jiǎn)單，車輛的移動(dòng)受限在一維的道路上，路邊單元一般部署在高速公路的路邊，部署側(cè)重于提高網(wǎng)絡(luò)性能或節(jié)約路邊單元能耗，該場(chǎng)景下傳統(tǒng)的部署方案是均勻部署.文獻(xiàn)[11]研究了一維高速公路場(chǎng)景中RSU通信范圍之間的間隔和系統(tǒng)參數(shù)(如數(shù)據(jù)傳輸率、更新間隔和數(shù)據(jù)大小等)之間的關(guān)系，提出一種啟發(fā)式算法，在滿足一定網(wǎng)絡(luò)性能指標(biāo)的前提下確定RSU的部署間隔，等間隔部署RSU.文獻(xiàn)[12]以整體網(wǎng)絡(luò)吞吐量最大化為目標(biāo)，考慮外界環(huán)境(無(wú)線電干擾等)和道路參數(shù)(如車輛分布、車速等)的影響，提出一種高速公路模型下的RSU部署方案，利用整數(shù)線性規(guī)劃模型求解使網(wǎng)絡(luò)吞吐量最大化的最少RSU部署個(gè)數(shù).啟發(fā)式和博弈論的思想也被用于高速公路場(chǎng)景下RSU的部署問(wèn)題上，文獻(xiàn)[13]綜合考慮RSU部署的成本和能耗問(wèn)題，提出一種氣球優(yōu)化方法，將RSU看作氣球，通信范圍為氣球邊界，利用氣球自然膨脹的動(dòng)態(tài)過(guò)程找到部署位置的最佳解決方案.
在城市道路場(chǎng)景中，車載網(wǎng)絡(luò)的通信區(qū)域內(nèi)存在建筑物、樹(shù)木等障礙物，且車輛的行駛路線更加多樣，使得路邊單元的部署比高速公路場(chǎng)景更為復(fù)雜.傳統(tǒng)的隨機(jī)部署和熱點(diǎn)部署的覆蓋效果并不理想，因此一些研究關(guān)注于二維城市場(chǎng)景下RSU部署策略.文獻(xiàn)[14]在部署成本的限制下設(shè)計(jì)RSU的完整部署方案，實(shí)現(xiàn)RSU之間的最大連通性，從而找到城市場(chǎng)景中RSU最佳部署位置使得成本最低.文獻(xiàn)[15]根據(jù)城市車流量的分布情況，確定城市中的流量熱點(diǎn)區(qū)域，在熱點(diǎn)區(qū)域之間沿道路部署多個(gè)RSU形成主干鏈路，以連接各個(gè)熱點(diǎn)區(qū)域.文獻(xiàn)[16]研究觀點(diǎn)與一般思路不同，作者認(rèn)為在車流量大的區(qū)域V2V通信就可以滿足車輛的通信需求，設(shè)計(jì)與車流量成反比的參數(shù)計(jì)算來(lái)選擇部署點(diǎn)，在車流量相對(duì)較低的區(qū)域部署RSU，目的是以低成本獲得高效的系統(tǒng)發(fā)生事故時(shí)的緊急提醒服務(wù).
根據(jù)RSU部署問(wèn)題的目標(biāo)不同，相關(guān)研究可以分為兩類，服務(wù)性能最大化的RSU部署和成本最小化的RSU部署.服務(wù)性能最大化的RSU部署通常預(yù)設(shè)部署的總成本，在此條件下計(jì)算服務(wù)性能最優(yōu)的RSU部署方案，此類部署包括覆蓋率最大化部署，連通性最大化部署和時(shí)延最小化部署等.覆蓋率最大化部署的側(cè)重點(diǎn)是追求服務(wù)質(zhì)量，在成本一定的情況下，覆蓋率越大，意味著車輛進(jìn)入RSU覆蓋范圍的概率增大，進(jìn)而使得車輛能夠最大化地被服務(wù).連通性同樣決定著網(wǎng)絡(luò)的服務(wù)質(zhì)量，連通性最大化部署旨在提高連通性，減少有限數(shù)量RSU的連接斷開(kāi).文獻(xiàn)[17]提出以最大化覆蓋率為目標(biāo)函數(shù)的MCP問(wèn)題，通過(guò)啟發(fā)式的算法解決該問(wèn)題，在給定RSU數(shù)量的基礎(chǔ)上實(shí)現(xiàn)RSU最優(yōu)化部署.文獻(xiàn)[18]以每個(gè)道路的交叉路口作為RSU的候選位置，以提高網(wǎng)絡(luò)連通性并減少斷開(kāi)間隔為目標(biāo)，根據(jù)每個(gè)候選位置通信范圍內(nèi)所接收到的車輛報(bào)告數(shù)來(lái)選擇部署位置.文獻(xiàn)[19]以最小化信息傳播時(shí)延為目標(biāo)，提出一種遺傳算法，能夠針對(duì)車載網(wǎng)絡(luò)的高度分割特性，為靜態(tài)的RSU部署找到合適的位置.
成本最小化的RSU部署則是在達(dá)到服務(wù)質(zhì)量要求的前進(jìn)下，追求成本最小化.成本限制勢(shì)必導(dǎo)致RSU部署數(shù)量的減少進(jìn)而使RSU的覆蓋范圍變小，但同時(shí)又要滿足特定的網(wǎng)絡(luò)服務(wù)請(qǐng)求.文獻(xiàn)[20]針對(duì)二維車載網(wǎng)中RSU的部署，采用整數(shù)線性規(guī)劃的方法，證明RSU的需求量和成本之間的非線性關(guān)系，提出一個(gè)RSU部署的最低成本方案，以最小化部署成本為目標(biāo)進(jìn)行部署.文獻(xiàn)[21]將部署問(wèn)題轉(zhuǎn)化為一個(gè)以最小化部署成本為目標(biāo)函數(shù)，以已部署RSU覆蓋有服務(wù)需求的所有區(qū)域?yàn)榧s束條件的二進(jìn)制整數(shù)規(guī)劃問(wèn)題，通過(guò)分支定界法解決這一問(wèn)題，有效降低了復(fù)雜度.
為了提高車載網(wǎng)絡(luò)的服務(wù)性能，如何在不同場(chǎng)景以及不同的優(yōu)化目標(biāo)下選擇合適的RSU部署位置亟待深入研究.因此，本文在復(fù)雜的二維城市場(chǎng)景下，以降低RSU部署成本并提高網(wǎng)絡(luò)服務(wù)質(zhì)量為目標(biāo)，綜合城市路網(wǎng)拓?fù)浣Y(jié)構(gòu)和車輛移動(dòng)規(guī)律，設(shè)計(jì)優(yōu)化的RSU部署機(jī)制.
3 RSU部署問(wèn)題分析與模型建立
本文假設(shè)所有RSU具有相同的通信半徑，RSU能夠與其通信范圍(也稱覆蓋范圍)內(nèi)的車輛或其他RSU相互通信.與RSU的覆蓋范圍相比，道路的寬度可以忽略不計(jì).為了實(shí)現(xiàn)更大程度地空間覆蓋，RSU通常被部署在一些具有重要空間特點(diǎn)的位置.Dubey B.B.提出，相比于其他位置，將交叉路口作為RSU的部署位置，RSU的覆蓋范圍將增加大約15%[22].因此，本文使用目標(biāo)路網(wǎng)中所有的交叉路口作為RSU候選部署位置集合.
3.1 路網(wǎng)模型
城市道路網(wǎng)絡(luò)是由交叉路口和路口之間的路段組成的復(fù)雜網(wǎng)絡(luò)系統(tǒng)，本文將其抽象成網(wǎng)絡(luò)圖表示，記為G=(V,E).G由頂點(diǎn)集及其之間的邊集構(gòu)成，V是網(wǎng)絡(luò)中交叉路口的集合，記為V={v1,v2,…,vn}，E表示交叉路口之間的位置關(guān)系，當(dāng)兩個(gè)交叉路口vi和vj之間有道路直接相連時(shí)，則生成邊
圖1 城市路網(wǎng)示例及其路網(wǎng)模型Fig.1 Urban road network example and corresponding road network model
3.2 車輛軌跡模型
車輛軌跡模型由沿城市道路行駛的所有車輛節(jié)點(diǎn)在一段時(shí)間內(nèi)的移動(dòng)軌跡組成，某一車輛在目標(biāo)路網(wǎng)中的移動(dòng)過(guò)程形成該車輛的軌跡.車輛軌跡數(shù)據(jù)反應(yīng)了時(shí)間和空間兩維信息，是典型的時(shí)空數(shù)據(jù).在特定時(shí)刻的車輛位置稱為車輛的軌跡點(diǎn)，按時(shí)間順序排列的一系列軌跡點(diǎn)構(gòu)成該車輛的軌跡數(shù)據(jù)，將其形式化描述為：
TS={Tp1,Tp2,Tp3,…Tpi,…}
(1)
其中，TS為某一車輛軌跡數(shù)據(jù)，Tpi={(xi,yi),τi,si,di}為該車輛在τi時(shí)刻的軌跡信息，(xi,yi)為該車輛在τi時(shí)刻的經(jīng)緯度位置信息，si為該車輛在τi時(shí)刻的行駛速度，di為該車輛在τi時(shí)刻的行駛方向.
城市車輛軌跡受城市路網(wǎng)模型的影響，反映了車輛在時(shí)間和空間上的分布特性，且能夠用于計(jì)算路邊單元的覆蓋效益.若車輛節(jié)點(diǎn)位于RSU的通信覆蓋范圍內(nèi)，則能夠與RSU通信.由此，位于RSU覆蓋范圍內(nèi)的車輛節(jié)點(diǎn)個(gè)數(shù)反映了該RSU的覆蓋效益.
3.3 覆蓋模型
RSU部署問(wèn)題用覆蓋模型C(CR,r,m)表示，其中CR表示路網(wǎng)中部署的RSU能夠覆蓋的交叉路口集合，r代表RSU通信半徑，m表示路網(wǎng)中部署的RSU個(gè)數(shù).
(2)
圖2 覆蓋模型Fig.2 Coverage model
4 基于優(yōu)先級(jí)和均勻性的RSU部署機(jī)制
本文提出的基于優(yōu)先級(jí)和均勻性的RSU部署機(jī)制(PUD)針對(duì)城市車載網(wǎng)絡(luò)中的RSU部署，旨在尋找合適的RSU部署位置，使在覆蓋路網(wǎng)所有交叉路口的前提下最小化部署數(shù)量.該方案有兩個(gè)核心的部署原則：1)選擇高優(yōu)先級(jí)的交叉路口部署；2)部署的RSU位置盡可能均勻.
4.1 路口優(yōu)先級(jí)的計(jì)算
PUD機(jī)制依據(jù)路口優(yōu)先級(jí)選擇RSU部署位置，本節(jié)將討論路口優(yōu)先級(jí)計(jì)算的3個(gè)因素：車流密度、連接中心性和公共交通線路數(shù).
4.1.1 車流密度
交叉路口的車流密度是指單位時(shí)間內(nèi)經(jīng)過(guò)該交叉路口的車輛數(shù)目，路口vi的車流密度記為f(vi).在車流密度較大的交叉路口處部署路邊單元能夠獲取更多的覆蓋效益.由于我國(guó)城市道路交通規(guī)劃設(shè)計(jì)規(guī)范(GB50220-95)中規(guī)定了城市道路交叉路口的范圍為140m-180m，實(shí)驗(yàn)中設(shè)置交叉路口范圍為160m.
4.1.2 連接中心性
交叉路口的連接中心性是指與其有道路直接相連的路口個(gè)數(shù)，表征路網(wǎng)中一個(gè)路口與其他路口的相互連接程度，連接中心性越大意味著該路口的連通性越好，交通承載力越大.因此，在連接中心性較大的路口處部署路邊單元，有益于提高路邊單元的覆蓋效益.對(duì)于一個(gè)擁有n個(gè)交叉路口頂點(diǎn)的網(wǎng)絡(luò)圖，交叉路口vi的連接中心性記為c(vi)，計(jì)算公式如下：
(3)
圖3 連接中心性的累計(jì)分布圖Fig.3 CDF of connection centrality
由于不同城市道路在種類、作用和交通功能以及沿線建筑物的服務(wù)功能上有所不同，影響著城市路網(wǎng)結(jié)構(gòu)，對(duì)應(yīng)的交叉路口也承載著不同的車流量.因此，將城市道路的等級(jí)劃分與之前的連接中心性計(jì)算方法相結(jié)合，賦予不同等級(jí)的道路以不同的權(quán)值?.
根據(jù)道路在城市道路系統(tǒng)的地位、性質(zhì)和功能，將城市道路分為3類：主干道、次干道和支路.主干道是城市道路網(wǎng)的骨架，負(fù)責(zé)聯(lián)系市區(qū)各主要地區(qū)、近郊區(qū)和主要的對(duì)外出路，承擔(dān)城市主要客貨運(yùn)交通，具有較大的通行能力；次干道是城市內(nèi)普通的交通干路，負(fù)責(zé)聯(lián)系各區(qū)和配合主干道，分擔(dān)主干道的交通壓力；支路是次干道和街坊路的連接線，以生活性功能為主，承擔(dān)局部區(qū)域內(nèi)部交通的集散和出入，分擔(dān)部分交通流量并彌補(bǔ)主次干道網(wǎng)的缺點(diǎn).
改進(jìn)的連接中心性由相鄰交叉路口個(gè)數(shù)和路口間道路的等級(jí)共同決定，其計(jì)算方法為：
(4)
其中，Ek為路網(wǎng)模型中不同等級(jí)道路的邊集合，k取1、2和3分別對(duì)應(yīng)主干道、次干道和支路；?k為路口vi和vj之間道路的權(quán)值，道路為主干道、次干道和支路時(shí)權(quán)值分別為1、0.75和0.25.
4.1.3 公共交通線路數(shù)
公共交通線路數(shù)是指城市公共交通系統(tǒng)中經(jīng)過(guò)該交叉路口的線路個(gè)數(shù)，這里的公共交通線路主要包括普通公交線、機(jī)場(chǎng)線、直達(dá)快車線和專線等線路.路口vi的公共交通線路數(shù)用l(vi)表示.公共交通線路的規(guī)劃與居民出行和城市空間結(jié)構(gòu)密切相關(guān)，經(jīng)過(guò)路口的公共交通線路數(shù)量在一定程度上反映了該交叉路口的交通熱度.因此,在該值較高的路口部署路邊單元具有更高的覆蓋效益.在本文實(shí)驗(yàn)的目標(biāo)區(qū)域中，包含公共線路304條，其中上行和下行線路視為兩條線路.
在使用交叉路口的車流密度、連接中心性和公共交通線路數(shù)計(jì)算路口優(yōu)先級(jí)時(shí)，為了統(tǒng)一這3個(gè)影響因素的取值范圍使其具有可比性，對(duì)3個(gè)因素的取值進(jìn)行歸一化處理，用fi、ci、li分別表示這3個(gè)影響因素歸一化后的取值.以車流密度f(wàn)(vi)為例，其歸一化計(jì)算方法為：
(5)
其中，函數(shù)min()和max()分別求得所有交叉路口的車流密度的最小值和最大值.同理可得連接中心性和公共交通線路數(shù)的歸一化方法.
綜合交叉路口vi的車流密度f(wàn)i、連接中心性ci和公共交通線路數(shù)li，計(jì)算該路口部署RSU的優(yōu)先級(jí)，即：
pi=wf×fi+wc?×ci+wl×li,
(6)
其中，wf、wc?和wl分別是車流密度、連接中心性和公共交通線路數(shù)的權(quán)重，均取正值且wf+wc?+wf=1.由式(5)可見(jiàn)，這3個(gè)因素均與路口優(yōu)先級(jí)正相關(guān).
4.2 路邊單元部署規(guī)則
為了避免按照優(yōu)先級(jí)依次部署路邊單元造成的部署位置聚集現(xiàn)象，本文制定了指導(dǎo)RSU均勻部署的四條部署規(guī)則.為了清楚地解釋這些部署規(guī)則，首先將交叉路口的部署狀態(tài)分為四種，即已部署狀態(tài)(Deployed)、候選部署狀態(tài)(Candidate)、可替換部署狀態(tài)(Pending)和不部署狀態(tài)(Non-deployed).在部署開(kāi)始之前，所有路口均處于候選部署狀態(tài)；在部署過(guò)程中，受部署規(guī)則約束，路口發(fā)生狀態(tài)轉(zhuǎn)變；在部署結(jié)束時(shí)，所有路口均為已部署狀態(tài)或不部署狀態(tài)，處于已部署狀態(tài)的路口為最終RSU的部署位置.
規(guī)則1.(位置約束)在已部署狀態(tài)的路口覆蓋范圍內(nèi)的其他路口不作為路邊單元的部署位置，變?yōu)椴徊渴馉顟B(tài).
規(guī)則2.(范圍約束)在當(dāng)前候選部署狀態(tài)的路口覆蓋范圍內(nèi)的其他候選部署路口，狀態(tài)調(diào)整為可替換部署狀態(tài).
規(guī)則3.(優(yōu)先級(jí)約束)可替換部署狀態(tài)的路口與被替換的候選部署路口的優(yōu)先級(jí)差值應(yīng)在閾值λ范圍內(nèi).
規(guī)則4.(覆蓋約束)相比于當(dāng)前候選部署狀態(tài)的路口，若可替換部署狀態(tài)路口的覆蓋范圍內(nèi)包含更多的候選部署路口，則選擇可替換部署狀態(tài)的路口為RSU部署位置.
規(guī)則2和規(guī)則3是由候選部署狀態(tài)向可替換部署狀態(tài)轉(zhuǎn)換的約束條件.
4.3 PUD部署機(jī)制
城市道路網(wǎng)絡(luò)中所有的交叉路口V為路邊單元的候選部署位置集合；依據(jù)路網(wǎng)內(nèi)真實(shí)的車輛軌跡數(shù)據(jù)，統(tǒng)計(jì)交叉路口的車流密度；根據(jù)構(gòu)建的路網(wǎng)模型，計(jì)算路口的連接中心性；依據(jù)城市公共交通線路信息，統(tǒng)計(jì)經(jīng)過(guò)路口的公共交通線路數(shù)，進(jìn)而計(jì)算每個(gè)路口的部署優(yōu)先級(jí).初始化所有交叉路口的狀態(tài)為Candidate，接下來(lái)執(zhí)行下面步驟.
Step 1.選擇優(yōu)先級(jí)最高的Candidate路口為當(dāng)前路口，依據(jù)范圍約束和優(yōu)先級(jí)約束，尋找當(dāng)前路口覆蓋范圍內(nèi)的可替換路口，若存在，該路口狀態(tài)變?yōu)镻ending，否則當(dāng)前路口選為部署位置，由Candidate狀態(tài)變?yōu)镈eployed狀態(tài)；
Step 2.對(duì)所有狀態(tài)為Pending的路口，依據(jù)覆蓋約束，判斷覆蓋范圍內(nèi)Candidate路口數(shù)量，并與當(dāng)前路口覆蓋范圍內(nèi)的Candidate路口數(shù)比較；若當(dāng)前路口覆蓋的Candidate路口最多，則當(dāng)前路口選為部署位置，由Candidate狀態(tài)變?yōu)镈eployed狀態(tài)；否則選擇覆蓋范圍內(nèi)路口最多的Pending路口做為部署位置，狀態(tài)變?yōu)镈eployed；若多個(gè)Pending路口覆蓋路口數(shù)最多且相同，則選擇優(yōu)先級(jí)最高的Pending路口做為部署位置，狀態(tài)變?yōu)镈eployed；
Step 3.依據(jù)位置約束，已部署路口覆蓋范圍內(nèi)的其他路口的狀態(tài)轉(zhuǎn)變?yōu)镹on-deployed；
Step 4.重復(fù)Step 1到Step 3，直至所有Candidate路口狀態(tài)轉(zhuǎn)換為Deployed或者Non-deployed.
算法1.RSU Deployment Algorithm PUD
輸入：V,P;
輸出：VR;
1. initialize:VR=?,CR=?;
2. sortVin descending order ofP;
3.whileCR≠Vdo
4. selectvi∈V-CRwith max(pi);
6.vmax=vi;
7.pmax=pi;
9.ifpi-pj≤λthen
11.if|TC|>|TCmax|or(|TC|=|TCmax|andpj>pmax)then
12.TCmax=TC;
13.vmax=vj;
14.pmax=pj;
15.endif
16.endif
17.endfor
18.VR=VR∪{vmax};
19.CR=TCmax;
20.endwhile
21.returnVR;
圖4為圖1路網(wǎng)模型對(duì)應(yīng)的PUD機(jī)制部署過(guò)程，當(dāng)前處于已部署狀態(tài)的路口為a、b、c、i和j.圖中省略了路網(wǎng)結(jié)構(gòu)，圓點(diǎn)所在位置對(duì)應(yīng)交叉路口，周圍的數(shù)字代表該路口的部署優(yōu)先級(jí).實(shí)心點(diǎn)代表已部署狀態(tài)的路口，圓代表覆蓋范圍.按照Step 1，優(yōu)先級(jí)為0.65的路口e為當(dāng)前路口，依據(jù)范圍約束
圖4 圖1場(chǎng)景中的PUD機(jī)制部署過(guò)程Fig.4 PUD deployment results for Fig.1
和優(yōu)先級(jí)約束原則(假設(shè)閾值為0.1)，路口f變?yōu)榭商鎿Q狀態(tài).由于可替換路口f的覆蓋范圍內(nèi)同時(shí)包含候選路口e和k，而當(dāng)前路口e的覆蓋范圍內(nèi)(虛線圓內(nèi))只有候選路口f，符合覆蓋約束，所以最終路口f為RSU部署位置，e和k轉(zhuǎn)變?yōu)椴徊渴馉顟B(tài).故圖1路網(wǎng)模型經(jīng)PUD機(jī)制選擇部署位置為a、b、c、i、j、k，并實(shí)現(xiàn)對(duì)場(chǎng)景中11個(gè)路口的覆蓋.
5 實(shí)驗(yàn)結(jié)果與分析
5.1 實(shí)驗(yàn)環(huán)境設(shè)置
為了構(gòu)建二維的城市車載網(wǎng)絡(luò)場(chǎng)景，本文選取北京市內(nèi)東經(jīng)116°18′～116°23′52″、北緯39°51′42″～39°57′2″之間大約9.05×10km2的矩形區(qū)域作為目標(biāo)區(qū)域，該區(qū)域內(nèi)包含1325個(gè)交叉路口.圖5展示了目標(biāo)區(qū)域的電子地圖和道路網(wǎng)絡(luò)圖.
圖5 目標(biāo)區(qū)域的電子地圖和道路網(wǎng)絡(luò)圖Fig.5 Electronic map and road network map of the target area
本文采用的車輛軌跡數(shù)據(jù)是2015年5月1日-31日期間北京市34,040輛出租車的車輛軌跡數(shù)據(jù)，每個(gè)軌跡點(diǎn)包括車輛的ID、位置、速度、時(shí)間戳和行駛方向等信息，數(shù)據(jù)收集頻率為60秒.本文使用的仿真平臺(tái)基于Python設(shè)計(jì)和實(shí)現(xiàn)，網(wǎng)絡(luò)的具體配置參數(shù)見(jiàn)表1.
表1 實(shí)驗(yàn)參數(shù)配置Table 1 Experimental parameter configuration
為了評(píng)估部署機(jī)制的性能，選擇均勻部署方案UDA(Uniform-based Deployment Approach)[24]和基于中心性的部署方案CDA(Centrality-based Deployment Approach)[25]作為對(duì)比方法.對(duì)于PUD，分別采用連接中心性和改進(jìn)的連接中心性作為路口優(yōu)先級(jí)的計(jì)算指標(biāo)，對(duì)應(yīng)的兩種部署方法分別表示為PUD-c和PUD.實(shí)驗(yàn)評(píng)估了3個(gè)指標(biāo)：部署個(gè)數(shù)、覆蓋率和覆蓋時(shí)間比例.路邊單元的部署個(gè)數(shù)反映了部署所需的成本，需要部署的路邊單元個(gè)數(shù)越多，成本越高.部署效益反映了已部署路邊單元集合的服務(wù)性能，通常用覆蓋率表示，覆蓋率是指位于路邊單元覆蓋范圍內(nèi)的車輛節(jié)點(diǎn)占所有車輛節(jié)點(diǎn)的比例.覆蓋率越高，車輛與RSU的通信機(jī)會(huì)越大，RSU能夠更好地為車輛提供有效及時(shí)的服務(wù).覆蓋時(shí)間比例是車輛節(jié)點(diǎn)在移動(dòng)過(guò)程中覆蓋連續(xù)性的體現(xiàn)，指的是車輛在運(yùn)動(dòng)過(guò)程中位于路邊單元覆蓋范圍的時(shí)間占比.較高的覆蓋時(shí)間比例表明在更多時(shí)間里RSU能夠提供V2I傳輸服務(wù)，因此部署性能較好.
5.2 實(shí)驗(yàn)結(jié)果
4種方法(UDA、CDA、PUD-c、PUD)的對(duì)比實(shí)驗(yàn)在同一場(chǎng)景中進(jìn)行，路邊單元的通信半徑由200m到600m變化，車輛節(jié)點(diǎn)的數(shù)量不變，其中PUD-c和PUD方法的參數(shù)為wf/wc(wc?)/wl=0.4/0.3/0.3和λ=0.15，實(shí)驗(yàn)結(jié)果如圖6所示.
隨著路邊單元通信半徑的增加，4個(gè)方法的部署個(gè)數(shù)都減少、覆蓋率增加，相比于UDA和CDA，PUD的部署個(gè)數(shù)相對(duì)較少并且覆蓋率較高.另外，PUD的部署個(gè)數(shù)和覆蓋率也明顯好于PUD-c.UDA的部署個(gè)數(shù)和部署間隔有關(guān)，因此部署個(gè)數(shù)均勻減少；其部署位置較為均勻地分散在目標(biāo)區(qū)域中，一些部署位置是車流量極少的偏僻路口，因此對(duì)車輛節(jié)點(diǎn)的覆蓋有限.CDA所需部署個(gè)數(shù)最多，這是因?yàn)镃DA基于度中心性選擇部署位置，選擇指標(biāo)單一且有局限性，且其部署位置分布不均勻，存在多個(gè)小區(qū)域內(nèi)選取眾多部署位置的現(xiàn)象，覆蓋區(qū)域間重疊造成一定程度的覆蓋資源浪費(fèi).PUD和PUD-c部署位置的選擇解決了CDA和UDA的問(wèn)題，考慮了部署位置之間的重疊和部署的覆蓋效益，有效避免了部署位置密集的現(xiàn)象.并且隨著路邊單元通信半徑的增加，其覆蓋范圍更大，使得部署的RSU個(gè)數(shù)下降.隨通信半徑每增加100m，PUD機(jī)制部署的路邊單元個(gè)數(shù)占全部路口數(shù)的比例分別是39%、24%、16%、12%、8%，且PUD的平均覆蓋率高于PUD-c約4.2%，證明路口的連接中心性的改進(jìn)計(jì)算是有效的.此外，PUD機(jī)制對(duì)車輛的覆蓋連續(xù)性更好.在CDA方法中，若車輛行駛于中心性較高的區(qū)域，則處于RSU通信范圍內(nèi)的概率較大，而一旦駛離這些區(qū)域后，就與RSU斷開(kāi)連接，導(dǎo)致覆蓋連續(xù)性不強(qiáng).而UDA采用均勻部署機(jī)制，車輛的移動(dòng)特性對(duì)覆蓋連續(xù)性的影響相對(duì)較小.PUD由于部署位置不僅與車流密度有關(guān)，而且結(jié)合道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，因此PUD對(duì)車輛的覆蓋時(shí)間比例相對(duì)較高.
圖6 RSU部署機(jī)制的實(shí)驗(yàn)結(jié)果Fig.6 Experimental results of RSU deployment schemes
綜上所述，與UDA和CDA相比，PUD實(shí)現(xiàn)了較少的部署個(gè)數(shù)和較高的部署覆蓋率，同時(shí)保證了較高的覆蓋時(shí)間比例，完成部署成本低和覆蓋效益高兩大目標(biāo).很明顯在復(fù)雜的城市車載場(chǎng)景中，PUD優(yōu)勢(shì)更顯著，部署結(jié)果更合理.
5.3 參數(shù)分析
考慮到式(5)中影響因素權(quán)重和算法1中優(yōu)先級(jí)閾值影響著PUD和PUD-c的性能，本節(jié)分析了這些參數(shù)對(duì)部署個(gè)數(shù)和覆蓋率兩項(xiàng)主要指標(biāo)的影響.在實(shí)驗(yàn)中，RSU的通信半徑設(shè)置為500m，影響因素權(quán)重wf/wc?/wl分別設(shè)置為0/0.5/0.5、0.2/0.4/0.4、0.4/0.3/0.3、0.6/0.2/0.2、0.8/0.1/0.1和1/0/0，優(yōu)先級(jí)閾值λ設(shè)置為0.15，結(jié)果如圖7(a)、圖7(b)所示.設(shè)置優(yōu)先級(jí)閾值λ從0.05、0.10、0.15、0.20到0.25變化，并且影響因素權(quán)重wf/wc?/wl設(shè)置為0.4/0.3/0.3，結(jié)果如圖7(c)、圖7(d)所示.
當(dāng)wf的值取0時(shí)，f在優(yōu)先級(jí)的計(jì)算中不起作用，由于影響因素l的計(jì)算方式相同，所以連接中心性c在影響因素中起決定性作用，PUD-c部署的RSU個(gè)數(shù)多于PUD.當(dāng)wf取1時(shí)，優(yōu)先級(jí)的計(jì)算完全由路口車流密度決定，因此PUD和PUD-c的部署完全相同，且部署個(gè)數(shù)與CDA接近.wf=0.4是兩個(gè)指標(biāo)的極值點(diǎn)，總體而言，改進(jìn)后的c?要比c計(jì)算方式更加合理，0.4/0.3/0.3是PUD影響因子的權(quán)重wf/wc?/wl的理想選擇.
隨著優(yōu)先級(jí)閾值λ的增大，部署個(gè)數(shù)逐漸減少，原因是λ取值對(duì)Pending路口的選取有很大影響，閾值越大，可供選擇的Pending路口越多.但λ越大、部署個(gè)數(shù)越少，并不意味著部署效果越好，從圖中可以看出，λ在取0.15時(shí)覆蓋率最高，覆蓋效果最好.比較PUD和PUD-c可知，隨著λ的增加，PUD部署個(gè)數(shù)平均減少的幅度小于PUD-c，這說(shuō)明PUD-c的部署受閾值λ的影響較大.進(jìn)一步說(shuō)明，PUD在優(yōu)先級(jí)閾值的選取上穩(wěn)定性更高，性能更好.
圖7 不同參數(shù)影響下的實(shí)驗(yàn)結(jié)果Fig.7 Experimental results with different weights and different λ
總而言之，適當(dāng)?shù)挠绊懸蛩貦?quán)重和合適的優(yōu)先級(jí)閾值會(huì)提升PUD的整體性能.在本章的實(shí)驗(yàn)中，PUD的性能在wf/wc?/wl為0.4/0.3/0.3，λ為0.15時(shí)達(dá)到峰值，在實(shí)際情況下，可以在初步研究階段通過(guò)樣本分析來(lái)選擇合適的參數(shù)取值.
6 總 結(jié)
為了提高車載網(wǎng)絡(luò)中路邊單元的部署效益和減少部署成本，本章提出了基于路口優(yōu)先級(jí)和部署均勻性的路邊單元部署機(jī)制PUD，綜合考慮道路網(wǎng)絡(luò)拓?fù)浜蛙囕v移動(dòng)規(guī)律，選擇合適的交叉路口部署路邊單元.首先利用車流密度、連接中心性和公共交通線路數(shù)計(jì)算路口的優(yōu)先級(jí)，為保證較高的覆蓋率，優(yōu)先級(jí)較高的路口優(yōu)先部署路邊單元.同時(shí)，在部署過(guò)程中執(zhí)行四條約束規(guī)則，即位置約束、范圍約束、優(yōu)先級(jí)約束和覆蓋約束，使部署位置盡可能均勻，從而減少路邊單元覆蓋范圍之間的重疊，進(jìn)而減少部署個(gè)數(shù).實(shí)驗(yàn)表明，相較其他方法，PUD具有更低的部署成本、更高的覆蓋率和車輛覆蓋時(shí)間比例.
