陳瀟然，唐曉嵐，陳文龍,柴明璐

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

1 引 言

車(chē)載自組織網(wǎng)絡(luò)(Vehicular Ad hoc NETworks,VANETs)簡(jiǎn)稱(chēng)車(chē)載網(wǎng)絡(luò)，是一種專(zhuān)用于汽車(chē)通信領(lǐng)域的特殊移動(dòng)自組織網(wǎng)絡(luò)，主要是由固定部署的路邊單元(RoadSide Units，RSUs)和安裝有車(chē)載設(shè)備的車(chē)輛節(jié)點(diǎn)構(gòu)成[1]，其特點(diǎn)和挑戰(zhàn)體現(xiàn)在車(chē)輛節(jié)點(diǎn)移動(dòng)速度快，網(wǎng)絡(luò)拓?fù)涓叨葎?dòng)態(tài)以及通信連接頻繁中斷[2]等方面.作為智能交通系統(tǒng)的重要構(gòu)成部分，車(chē)載網(wǎng)絡(luò)通過(guò)具有感知和通信能力的車(chē)載單元，依據(jù)專(zhuān)用短程通信標(biāo)準(zhǔn)實(shí)現(xiàn)車(chē)輛與車(chē)輛通信(Vehicle to Vehicle,V2V)[3]以及車(chē)輛與路邊基礎(chǔ)設(shè)施通信(Vehicle to Infrastructure,V2I)[4]，支持交通相關(guān)數(shù)據(jù)在車(chē)輛之間傳輸，提高車(chē)輛行駛過(guò)程中的安全性[5]、可靠性[6]和道路交通的運(yùn)行效率，同時(shí)減少了交通運(yùn)輸對(duì)環(huán)境的污染，節(jié)約能源，提高了資源利用率[7].

V2I的通信方式改變了傳統(tǒng)交通系統(tǒng)中車(chē)輛和道路之間無(wú)法進(jìn)行實(shí)時(shí)信息交互的現(xiàn)狀，實(shí)現(xiàn)了車(chē)與路的協(xié)同運(yùn)行.作為VANET的路邊基礎(chǔ)設(shè)施，RSU具有較車(chē)載節(jié)點(diǎn)更為強(qiáng)大的計(jì)算、存儲(chǔ)和通信能力[8]，支持遠(yuǎn)程無(wú)線(xiàn)數(shù)據(jù)傳輸和互聯(lián)網(wǎng)接入，在很大程度上緩解了車(chē)載網(wǎng)絡(luò)的拓?fù)浞指钐匦?，通過(guò)與行駛的車(chē)輛進(jìn)行信息交互，輔助車(chē)輛獲取道路交通狀況等信息，同時(shí)加速車(chē)輛的信息發(fā)布，改善車(chē)輛節(jié)點(diǎn)之間的通信質(zhì)量和降低通信延遲.

RSU的部署位置直接影響其對(duì)車(chē)輛通信需求的服務(wù)能力和車(chē)路通信的質(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)車(chē)輛移動(dòng)特性影響RSU部署，當(dāng)車(chē)輛進(jìn)入RSU通信覆蓋范圍內(nèi)時(shí)，RSU能夠?yàn)檐?chē)輛服務(wù)[10]，獲得覆蓋效益；3)RSU部署需考慮成本，大規(guī)模部署帶來(lái)較高的安裝與維護(hù)成本.因此，在復(fù)雜的二維城市路網(wǎng)中，如何選擇最優(yōu)的路邊單元部署位置是車(chē)載網(wǎng)絡(luò)研究的難題.

本文提出基于路口優(yōu)先級(jí)和部署均勻性的路邊單元部署機(jī)制PUD，綜合城市路網(wǎng)拓?fù)浣Y(jié)構(gòu)和車(chē)輛移動(dòng)規(guī)律，依據(jù)車(chē)流密度、連接中心性和公共交通線(xiàn)路數(shù)，計(jì)算交叉路口的部署優(yōu)先級(jí)，優(yōu)先將RSU部署在車(chē)流量大、在路網(wǎng)拓?fù)渲衅鹬匾饔玫慕徊媛房?，從而保證路邊單元在車(chē)載網(wǎng)絡(luò)中的傳輸服務(wù)質(zhì)量.同時(shí)，為了降低部署成本，以均勻部署為目標(biāo)制定約束規(guī)則，包括位置約束、范圍約束、優(yōu)先級(jí)約束和覆蓋約束，符合約束條件的交叉路口優(yōu)先部署路邊單元.使用北京市出租車(chē)軌跡數(shù)據(jù)的車(chē)載網(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ì)算方法綜合考慮車(chē)輛移動(dòng)規(guī)律和路網(wǎng)拓?fù)洌?/p>

3)兼顧部署成本和覆蓋效益兩大目標(biāo)，在選擇RSU部署位置的過(guò)程中，設(shè)置4條部署約束規(guī)則，在保證RSU覆蓋效益的基礎(chǔ)上降低部署成本.

2 相關(guān)工作

在車(chē)載網(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)行分類(lèi).車(chē)載網(wǎng)絡(luò)一般有兩種典型的應(yīng)用場(chǎng)景，即高速公路場(chǎng)景和城市道路場(chǎng)景.高速公路場(chǎng)景較為簡(jiǎn)單，車(chē)輛的移動(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ā)式算法，在滿(mǎn)足一定網(wǎng)絡(luò)性能指標(biāo)的前提下確定RSU的部署間隔，等間隔部署RSU.文獻(xiàn)[12]以整體網(wǎng)絡(luò)吞吐量最大化為目標(biāo)，考慮外界環(huán)境(無(wú)線(xiàn)電干擾等)和道路參數(shù)(如車(chē)輛分布、車(chē)速等)的影響，提出一種高速公路模型下的RSU部署方案，利用整數(shù)線(xiàn)性規(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)景中，車(chē)載網(wǎng)絡(luò)的通信區(qū)域內(nèi)存在建筑物、樹(shù)木等障礙物，且車(chē)輛的行駛路線(xiàn)更加多樣，使得路邊單元的部署比高速公路場(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ù)城市車(chē)流量的分布情況，確定城市中的流量熱點(diǎn)區(qū)域，在熱點(diǎn)區(qū)域之間沿道路部署多個(gè)RSU形成主干鏈路，以連接各個(gè)熱點(diǎn)區(qū)域.文獻(xiàn)[16]研究觀點(diǎn)與一般思路不同，作者認(rèn)為在車(chē)流量大的區(qū)域V2V通信就可以滿(mǎn)足車(chē)輛的通信需求，設(shè)計(jì)與車(chē)流量成反比的參數(shù)計(jì)算來(lái)選擇部署點(diǎn)，在車(chē)流量相對(duì)較低的區(qū)域部署RSU，目的是以低成本獲得高效的系統(tǒng)發(fā)生事故時(shí)的緊急提醒服務(wù).

根據(jù)RSU部署問(wèn)題的目標(biāo)不同，相關(guān)研究可以分為兩類(lèi)，服務(wù)性能最大化的RSU部署和成本最小化的RSU部署.服務(wù)性能最大化的RSU部署通常預(yù)設(shè)部署的總成本，在此條件下計(jì)算服務(wù)性能最優(yōu)的RSU部署方案，此類(lèi)部署包括覆蓋率最大化部署，連通性最大化部署和時(shí)延最小化部署等.覆蓋率最大化部署的側(cè)重點(diǎn)是追求服務(wù)質(zhì)量，在成本一定的情況下，覆蓋率越大，意味著車(chē)輛進(jìn)入RSU覆蓋范圍的概率增大，進(jìn)而使得車(chē)輛能夠最大化地被服務(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)所接收到的車(chē)輛報(bào)告數(shù)來(lái)選擇部署位置.文獻(xiàn)[19]以最小化信息傳播時(shí)延為目標(biāo)，提出一種遺傳算法，能夠針對(duì)車(chē)載網(wǎng)絡(luò)的高度分割特性，為靜態(tài)的RSU部署找到合適的位置.

成本最小化的RSU部署則是在達(dá)到服務(wù)質(zhì)量要求的前進(jìn)下，追求成本最小化.成本限制勢(shì)必導(dǎo)致RSU部署數(shù)量的減少進(jìn)而使RSU的覆蓋范圍變小，但同時(shí)又要滿(mǎn)足特定的網(wǎng)絡(luò)服務(wù)請(qǐng)求.文獻(xiàn)[20]針對(duì)二維車(chē)載網(wǎng)中RSU的部署，采用整數(shù)線(xiàn)性規(guī)劃的方法，證明RSU的需求量和成本之間的非線(xiàn)性關(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ù)雜度.

為了提高車(chē)載網(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)和車(chē)輛移動(dòng)規(guī)律，設(shè)計(jì)優(yōu)化的RSU部署機(jī)制.

3 RSU部署問(wèn)題分析與模型建立

本文假設(shè)所有RSU具有相同的通信半徑，RSU能夠與其通信范圍(也稱(chēng)覆蓋范圍)內(nèi)的車(chē)輛或其他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í)，則生成邊.路網(wǎng)模型圖利用原始圖法(Primal Graph)[23]將路網(wǎng)中的元素抽象，即頂點(diǎn)是目標(biāo)區(qū)域路網(wǎng)內(nèi)的交叉路口，頂點(diǎn)之間的邊是交叉路口之間的路段.圖1(a)展示的是城市路網(wǎng)示例圖，有11個(gè)交叉路口，分別用a-k表示.圖1(b)是場(chǎng)景對(duì)應(yīng)的路網(wǎng)模型，頂點(diǎn)對(duì)應(yīng)圖1(a)中的交叉路口，邊對(duì)應(yīng)交叉路口之間的路段，其中虛線(xiàn)邊為場(chǎng)景之外的路段連接.

圖1 城市路網(wǎng)示例及其路網(wǎng)模型Fig.1 Urban road network example and corresponding road network model

3.2 車(chē)輛軌跡模型

車(chē)輛軌跡模型由沿城市道路行駛的所有車(chē)輛節(jié)點(diǎn)在一段時(shí)間內(nèi)的移動(dòng)軌跡組成，某一車(chē)輛在目標(biāo)路網(wǎng)中的移動(dòng)過(guò)程形成該車(chē)輛的軌跡.車(chē)輛軌跡數(shù)據(jù)反應(yīng)了時(shí)間和空間兩維信息，是典型的時(shí)空數(shù)據(jù).在特定時(shí)刻的車(chē)輛位置稱(chēng)為車(chē)輛的軌跡點(diǎn)，按時(shí)間順序排列的一系列軌跡點(diǎn)構(gòu)成該車(chē)輛的軌跡數(shù)據(jù)，將其形式化描述為：

TS={Tp1,Tp2,Tp3,…Tpi,…}

(1)

其中，TS為某一車(chē)輛軌跡數(shù)據(jù)，Tpi={(xi,yi),τi,si,di}為該車(chē)輛在τi時(shí)刻的軌跡信息，(xi,yi)為該車(chē)輛在τi時(shí)刻的經(jīng)緯度位置信息，si為該車(chē)輛在τi時(shí)刻的行駛速度，di為該車(chē)輛在τi時(shí)刻的行駛方向.

城市車(chē)輛軌跡受城市路網(wǎng)模型的影響，反映了車(chē)輛在時(shí)間和空間上的分布特性，且能夠用于計(jì)算路邊單元的覆蓋效益.若車(chē)輛節(jié)點(diǎn)位于RSU的通信覆蓋范圍內(nèi)，則能夠與RSU通信.由此，位于RSU覆蓋范圍內(nèi)的車(chē)輛節(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ì)城市車(chē)載網(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è)因素：車(chē)流密度、連接中心性和公共交通線(xiàn)路數(shù).

4.1.1 車(chē)流密度

交叉路口的車(chē)流密度是指單位時(shí)間內(nèi)經(jīng)過(guò)該交叉路口的車(chē)輛數(shù)目，路口vi的車(chē)流密度記為f(vi).在車(chē)流密度較大的交叉路口處部署路邊單元能夠獲取更多的覆蓋效益.由于我國(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

由于不同城市道路在種類(lèi)、作用和交通功能以及沿線(xiàn)建筑物的服務(wù)功能上有所不同，影響著城市路網(wǎng)結(jié)構(gòu)，對(duì)應(yīng)的交叉路口也承載著不同的車(chē)流量.因此，將城市道路的等級(jí)劃分與之前的連接中心性計(jì)算方法相結(jié)合，賦予不同等級(jí)的道路以不同的權(quán)值?.

根據(jù)道路在城市道路系統(tǒng)的地位、性質(zhì)和功能，將城市道路分為3類(lèi)：主干道、次干道和支路.主干道是城市道路網(wǎng)的骨架，負(fù)責(zé)聯(lián)系市區(qū)各主要地區(qū)、近郊區(qū)和主要的對(duì)外出路，承擔(dān)城市主要客貨運(yùn)交通，具有較大的通行能力；次干道是城市內(nèi)普通的交通干路，負(fù)責(zé)聯(lián)系各區(qū)和配合主干道，分擔(dān)主干道的交通壓力；支路是次干道和街坊路的連接線(xià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 公共交通線(xiàn)路數(shù)

公共交通線(xiàn)路數(shù)是指城市公共交通系統(tǒng)中經(jīng)過(guò)該交叉路口的線(xiàn)路個(gè)數(shù)，這里的公共交通線(xiàn)路主要包括普通公交線(xiàn)、機(jī)場(chǎng)線(xiàn)、直達(dá)快車(chē)線(xiàn)和專(zhuān)線(xiàn)等線(xiàn)路.路口vi的公共交通線(xiàn)路數(shù)用l(vi)表示.公共交通線(xiàn)路的規(guī)劃與居民出行和城市空間結(jié)構(gòu)密切相關(guān)，經(jīng)過(guò)路口的公共交通線(xiàn)路數(shù)量在一定程度上反映了該交叉路口的交通熱度.因此,在該值較高的路口部署路邊單元具有更高的覆蓋效益.在本文實(shí)驗(yàn)的目標(biāo)區(qū)域中，包含公共線(xiàn)路304條，其中上行和下行線(xiàn)路視為兩條線(xiàn)路.

在使用交叉路口的車(chē)流密度、連接中心性和公共交通線(xiàn)路數(shù)計(jì)算路口優(yōu)先級(jí)時(shí)，為了統(tǒng)一這3個(gè)影響因素的取值范圍使其具有可比性，對(duì)3個(gè)因素的取值進(jìn)行歸一化處理，用fi、ci、li分別表示這3個(gè)影響因素歸一化后的取值.以車(chē)流密度f(wàn)(vi)為例，其歸一化計(jì)算方法為：

(5)

其中，函數(shù)min()和max()分別求得所有交叉路口的車(chē)流密度的最小值和最大值.同理可得連接中心性和公共交通線(xiàn)路數(shù)的歸一化方法.

綜合交叉路口vi的車(chē)流密度f(wàn)i、連接中心性ci和公共交通線(xiàn)路數(shù)li，計(jì)算該路口部署RSU的優(yōu)先級(jí)，即：

pi=wf×fi+wc?×ci+wl×li,

(6)

其中，wf、wc?和wl分別是車(chē)流密度、連接中心性和公共交通線(xiàn)路數(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í)的車(chē)輛軌跡數(shù)據(jù)，統(tǒng)計(jì)交叉路口的車(chē)流密度；根據(jù)構(gòu)建的路網(wǎng)模型，計(jì)算路口的連接中心性；依據(jù)城市公共交通線(xiàn)路信息，統(tǒng)計(jì)經(jīng)過(guò)路口的公共交通線(xiàn)路數(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)交叉路口，周?chē)臄?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)(虛線(xiàn)圓內(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)建二維的城市車(chē)載網(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

本文采用的車(chē)輛軌跡數(shù)據(jù)是2015年5月1日-31日期間北京市34,040輛出租車(chē)的車(chē)輛軌跡數(shù)據(jù)，每個(gè)軌跡點(diǎn)包括車(chē)輛的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)的車(chē)輛節(jié)點(diǎn)占所有車(chē)輛節(jié)點(diǎn)的比例.覆蓋率越高，車(chē)輛與RSU的通信機(jī)會(huì)越大，RSU能夠更好地為車(chē)輛提供有效及時(shí)的服務(wù).覆蓋時(shí)間比例是車(chē)輛節(jié)點(diǎn)在移動(dòng)過(guò)程中覆蓋連續(xù)性的體現(xiàn)，指的是車(chē)輛在運(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變化，車(chē)輛節(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ū)域中，一些部署位置是車(chē)流量極少的偏僻路口，因此對(duì)車(chē)輛節(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ì)車(chē)輛的覆蓋連續(xù)性更好.在CDA方法中，若車(chē)輛行駛于中心性較高的區(qū)域，則處于RSU通信范圍內(nèi)的概率較大，而一旦駛離這些區(qū)域后，就與RSU斷開(kāi)連接，導(dǎo)致覆蓋連續(xù)性不強(qiáng).而UDA采用均勻部署機(jī)制，車(chē)輛的移動(dòng)特性對(duì)覆蓋連續(xù)性的影響相對(duì)較小.PUD由于部署位置不僅與車(chē)流密度有關(guān)，而且結(jié)合道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，因此PUD對(duì)車(chē)輛的覆蓋時(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ē)載場(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ì)算完全由路口車(chē)流密度決定，因此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é)

為了提高車(chē)載網(wǎng)絡(luò)中路邊單元的部署效益和減少部署成本，本章提出了基于路口優(yōu)先級(jí)和部署均勻性的路邊單元部署機(jī)制PUD，綜合考慮道路網(wǎng)絡(luò)拓?fù)浜蛙?chē)輛移動(dòng)規(guī)律，選擇合適的交叉路口部署路邊單元.首先利用車(chē)流密度、連接中心性和公共交通線(xiàn)路數(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具有更低的部署成本、更高的覆蓋率和車(chē)輛覆蓋時(shí)間比例.