車載自組織網(wǎng)絡(luò)中基于連接時長的RSU部署方案

丁正超，魏振春,2，馮琳

（1. 合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽 合肥 230009；2. 安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心，安徽 合肥 230009）

車載自組織網(wǎng)絡(luò)中基于連接時長的RSU部署方案

丁正超1，魏振春1,2，馮琳1

（1. 合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽 合肥 230009；2. 安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心，安徽 合肥 230009）

針對目前城市場景下車載自組織網(wǎng)絡(luò)中的RSU部署問題，提出了一種基于連接時長的RSU部署方案。該方案在RSU數(shù)量受限的情況下，以保證通信連接時長為前提，以最大化服務(wù)車輛數(shù)目為目的，將部署問題建模成最大覆蓋問題，設(shè)計了二進制粒子群算法進行求解，并結(jié)合真實的北京市路網(wǎng)地圖和出租車 GPS數(shù)據(jù)進行仿真實驗。仿真結(jié)果表明，該算法是收斂、穩(wěn)定及可行的，相比貪心算法，該算法求得的部署方案能為更多的車輛提供持續(xù)性的網(wǎng)絡(luò)服務(wù)。

車載自組織網(wǎng)絡(luò)；路邊基礎(chǔ)設(shè)施部署；連接時長；二進制粒子群算法

[3]提出了將BEH（balloon expansion heuristic）方法用于最優(yōu)化部署數(shù)量受限的RSU，目標(biāo)最小化事故消息的播報時間。參考文獻[4]將部署問題建模成整數(shù)線性規(guī)劃問題，在RSU數(shù)量受限的條件下，最大化網(wǎng)絡(luò)吞吐量。上述文獻的研究主要考慮的是在高速公路上最優(yōu)化部署RSU，并不適用于拓撲結(jié)構(gòu)復(fù)雜的城市道路。參考文獻[5]提出了基于真實車載移動數(shù)據(jù)的 RSU部署算法，綜合考慮部署位置的均勻性和中心性以優(yōu)化網(wǎng)絡(luò)整體性能。參考文獻[6]提出了基于車流量的路邊單元RSU部署方案，通過對路口的車流量進行統(tǒng)計分析，在城市重要交通樞紐和交叉路口部署RSU，從而提高網(wǎng)絡(luò)通信的效率。參考文獻[7]提出了基于路口權(quán)重的RSU部署方案，由車輛密度、車輛速度、路口危險程度等因素計算路口的權(quán)重值，并根據(jù)路口權(quán)重值最優(yōu)化部署RSU。參考文獻[8]結(jié)合迪杰斯特拉算法和遺傳算法用于最優(yōu)化部署RSU以降低網(wǎng)絡(luò)時延。上述文獻的研究基本都以吞吐量或時延作為RSU部署方案優(yōu)劣的指標(biāo)，并未考慮網(wǎng)絡(luò)連接時長帶來的影響，VANET多數(shù)應(yīng)用要求通信連接具有一定的連續(xù)性，連接時間長短會降低網(wǎng)絡(luò)服務(wù)的質(zhì)量，甚至可能導(dǎo)致車輛與RSU無法建立通信連接。此外，它們只考慮在路口部署RSU，然而對于長路段、危險區(qū)域、點區(qū)域并未考慮?；谏鲜鲅芯康牟蛔?，本文提出了基于連接時長的RSU部署方案，該方案考慮在城市區(qū)域內(nèi)的路口和路段上部署數(shù)量受限的RSU，在保證連接時長的前提下，期望為更多的車輛提供網(wǎng)絡(luò)服務(wù)。

2 RSU部署模型

城市道路網(wǎng)絡(luò)可以被表示為一張由頂點集 I和邊集 E構(gòu)成的無向圖 G，G=(I,E)。每個頂點Ii(Ii∈I)代表一個路口（這里的路口指的是一個連接點，它可以是一個十字路口、一個道路樞紐，還可以是一個環(huán)島）。每條邊 Ei(Ei∈E)代表一個物理路段。假定RSU的通信半徑為r，對物理路段Ei以2r為長度進行劃分，形成若干個邏輯路段Eij，其中Eij∈Ei，此時Ei={Ei1,Ei2,…,Eiu}，路段劃分示意如圖1所示。其中u表示物理路段Ei能劃分的邏輯路段數(shù)量，可通過式（1）計算而得：

圖1 路段劃分示意

由所有路口和邏輯路段的中心構(gòu)成部署RSU的候選位置集 P，P={p1,p2,…,pn}，每個候選位置最多部署一個 RSU。定義 0-1變量yi(1≤i≤n)，如果在候選位置 pi部署 RSU 則yi=1，否則yi=0。

定義車輛集合V，V={v1,v2,…,vm}，定義變量dj(1≤j≤m)，dj＞0表示車輛 vj的行程持續(xù)時長，定義變量 tij(1≤i≤n,1≤j≤m)，tij＞0表示車輛 vj與部署在候選位置 pi上的 RSU之間的連接時長（車輛vj進入該RSU通信范圍的時刻起直至離開該范圍的時間間隔），引入變量 sij(1≤i≤n,1≤j≤m)表示車輛vj經(jīng)過候選位置pi的平均車速，那么tij就可以通過式（2）求得：

考慮不同車輛的行程持續(xù)時長不同，為了統(tǒng)一衡量車輛與RSU之間的連接時長，引入連接時長比cj(1≤j≤m)表示車輛vj與RSU間的連接時長占其行程持續(xù)時長的比例，計算式為：

將式（2）代入式（3），進一步轉(zhuǎn)化為：

定義時長比閾值ε，ε∈(0,1)表示車輛與 RSU間的連接時長與其行程時長應(yīng)滿足的最小比例。定義0-1變量xj(1≤j≤m)，對于任意車輛vj，如果它與RSU間的連接時長和其行程時長的比值大于ε，則xj=1，否則xj=0，如式（5）所示：

令U={vj|xj=1,vj∈V}表示滿足連接時長比要求的車輛集合。本文問題是在RSU部署數(shù)量受限的條件下，如何選擇最優(yōu)的位置來為盡可能多的車輛提供一定連接時長的網(wǎng)絡(luò)服務(wù)，即給定RSU部署數(shù)量k，如何從候選位置集P中選擇k個位置來部署RSU使得|U|最大，進一步表述為：

3 求解算法設(shè)計

本文所建模型為 NP難問題，使用二進制粒子群（binary particle swarm，BPSO）算法進行求解，根據(jù)本文模型設(shè)計了編碼規(guī)則、適應(yīng)度函數(shù)，并在慣性權(quán)重中引入自適應(yīng)擾動機制以克服傳統(tǒng)粒子群算法易早熟的缺點。

3.1 粒子編碼

二進制粒子群算法中粒子維數(shù)對應(yīng)RSU候選位置的個數(shù)，粒子每一維位置的值取1或者0代表各候選位置是否被選中來部署RSU，例如有4個候選位置，則編碼{1,0,0,1}表示候選位置 1和 4被選中來部署RSU。

3.2 初始化

（1）初始化粒子群參數(shù)，包括種群規(guī)模 M、最大迭代次數(shù)tmax、學(xué)習(xí)因子c1和c2、最大慣性權(quán)重ωmax、最小慣性權(quán)重ωmin、最大擾動因子gmax。

（2）初始化粒子的位置和速度，粒子的初始位置為隨機的二進制向量，判斷向量中1的個數(shù)是否小于或等于k（最多部署k個RSU），若滿足則將該粒子保留，否則將其拋棄并隨機產(chǎn)生一個新粒子，直至粒子數(shù)目達到M。

3.3 適應(yīng)度函數(shù)

本文適應(yīng)度函數(shù)設(shè)計為：

其中，m是車輛數(shù)目，n是候選位置數(shù)目，k是待部署RSU數(shù)目，M是懲罰因子為本文目標(biāo)函數(shù)為懲罰函數(shù)。

3.4 粒子的位置和速度更新

二進制粒子群中粒子i的各維速度更新計算式為：

其中，ω為慣性權(quán)重，c1、c2為學(xué)習(xí)因子，rand()為隨機函數(shù)，產(chǎn)生[0,1]之間的隨機數(shù)，t為當(dāng)前代數(shù)，Pij(t)表示第t代時搜索到的歷史最優(yōu)解，Pgj(t)表示第t代時搜索到的全局最優(yōu)解。在慣性權(quán)重ω中引入自適應(yīng)擾動機制[9]，增強粒子群跳出局部最優(yōu)的能力。慣性權(quán)重ω的表達式為：

其中，ωmax為最大慣性權(quán)重，ωmin為最小慣性權(quán)重，t為當(dāng)前的迭代次數(shù)，gmax為最大擾動因子，擾動因子g的取值可表示為：

二進制粒子群中粒子i的各維位置更新計算式為：

3.5 終止條件

設(shè)置最大迭代次數(shù)tmax，每次迭代通過適應(yīng)度函數(shù)時對粒子位置進行優(yōu)劣評定，更新粒子當(dāng)前的個體最優(yōu)位置和全局最優(yōu)位置，循環(huán)更新粒子的速度和位置，達到最大迭代次數(shù)tmax后終止。

4 仿真實驗與分析

4.1 仿真參數(shù)

選取北京市某區(qū)域內(nèi)（東經(jīng) 116.27°至116.35°、北緯39.87°至39.94°）的主干街道作為RSU的部署區(qū)域。RSU采用IEEE 802.11p協(xié)議，通信半徑r=300 m[10]。將長度大于2r（即600 m）的路段進一步劃分成若干短路段，由所有路口和路段中心構(gòu)成部署RSU的162個候選位置，如圖2中圓點所示。并選取集中一周內(nèi)出現(xiàn)在該區(qū)域的200輛北京市出租車的軌跡數(shù)據(jù)來進行仿真。鑒于通過 GPS獲得的位置數(shù)據(jù)在記錄頻率上并不統(tǒng)一，因此需要對數(shù)據(jù)進行預(yù)處理。首先在北京市地圖上繪制車輛軌跡，通過線性回歸的方法進行地理位置插值，保證記錄頻率在15 s左右。

圖2 RSU候選位置

采用 MATLAB對二進制粒子群算法進行仿真，設(shè)置種群大小 M=50，學(xué)習(xí)因子 c1=c2=2.0，最大慣性權(quán)重ωmax=0.9，最小慣性權(quán)重ωmin=0.5，最大擾動因子gmax=10，最大迭代次數(shù)tmax=200。

4.2 結(jié)果與分析

（1）算法的收斂性分析

將二進制粒子群算法程序運行20次，取20次的平均值作為實驗結(jié)果。設(shè)置ε=0.3，k=40，二進制粒子群算法迭代如圖3所示。

由圖3可知，二進制粒子群具有較好的收斂性，前20代快速收斂，在第20代到第80代過程中，多次遇到局部最優(yōu)解，由于在慣性權(quán)重中引入自適應(yīng)擾動機制，算法很快就跳出局部最優(yōu)解，當(dāng)?shù)降?0代左右時，目標(biāo)函數(shù)收斂于96%。

圖3 二進制粒子群算法迭代

當(dāng)ε=0.3、k=40時，運用二進制粒子群算法求得最優(yōu)部署位置，如圖4所示，其中圓點為候選位置，方格為最終的RSU部署位置。

圖4 RSU部署位置（ε=0.3、k=40）

（2）算法的性能分析

為了評價求解算法的性能，引入貪心（Greedy）算法進行對比。貪心算法求解問題時，最為關(guān)鍵的是貪心策略的選擇，為此引入變量 wi表示候選位置pi為車輛提供的累積連接時長，計算式為：

在每次迭代中選擇wi最大的位置作為部署位置，直到所有車輛都滿足連接時長要求或者部署數(shù)量達到k。

本文的優(yōu)化目標(biāo)為最大化服務(wù)車輛數(shù)目，因而使用車輛覆蓋率（滿足連接時長要求的車輛數(shù)目/車輛總數(shù)目）作為算法性能優(yōu)劣的評判依據(jù)。首先研究不同RSU數(shù)量下，兩種算法求得的車輛覆蓋率，將連接時長比閾值ε設(shè)置為0.3，并將RSU部署數(shù)量k分別設(shè)置為{10,15,20,25, 30,35,40}，仿真結(jié)果如圖5所示。

圖5 不同RSU數(shù)量下BPSO和貪心算法求得的車輛覆蓋率

由圖5可知，當(dāng)k=10時，兩種算法求得的車輛覆蓋率都比較低，這是由于在RSU部署數(shù)量較少的情況下，對于多數(shù)車輛很難與RSU相遇，也就難以滿足連接時長的要求。隨著RSU數(shù)量的增加，兩種算法求得的覆蓋率也隨之增加，但二進制粒子群算法的增幅要高于貪心算法。當(dāng)k=20時，二進制粒子群算法求得的覆蓋率甚至比貪心高出21%左右，這是由于貪心算法在部署過程中只考慮單個候選位置的累積連接時長，具有一定局限性，車輛雖然與某個RSU的連接時長很大，但如果它在行駛過程中遇到的RSU數(shù)量很少，它依舊很難達到連接時長比要求。當(dāng)k=40時，兩種算法求得的車輛覆蓋率相近而且增幅變得平緩，說明此時RSU的部署數(shù)量（k=40）相對連接時長比要求（ε=0.3）已接近飽和?？傮w而言，二進制粒子群算法求得的車輛覆蓋率要高于貪心算法。

接著研究在不同連接時長要求下，兩種算法求得的車輛覆蓋率。將k設(shè)置為40，并將ε分別設(shè)置為{0.3,0.35,…,0.85,0.9}，仿真結(jié)果如圖6所示。

圖6 不同連接時長比ε要求下BPSO和貪心算法求得的車輛覆蓋率

由圖 6可知，隨著ε的增加，兩種算法求得的車輛覆蓋率隨之降低，但是二進制粒子群算法求得的覆蓋率始終高于貪心算法，并且覆蓋率的下降趨勢也比貪心算法平緩，這是由于二進制粒子群算法是從全局RSU能服務(wù)的車輛數(shù)目角度進行部署位置的選擇，而不是局限考慮單個位置為車輛提供的連接時長，因而相比貪心算法，二進制粒子群算法求得的車輛覆蓋率受連接時長要求變化的影響相對較小。

上述的仿真結(jié)果說明，二進制粒子群算法具有較好的收斂性，與貪心算法相比，能得到更優(yōu)的RSU部署方案。將此算法應(yīng)用于RSU部署規(guī)劃的實際工作中，可以取得較好的效果。

5 結(jié)束語

針對城市場景下 VANET中路邊基礎(chǔ)設(shè)施的部署問題進行了研究，提出了一種基于連接時長的RSU部署方案，設(shè)計了二進制粒子群算法進行求解，并結(jié)合北京市路網(wǎng)地圖和出租車移動軌跡進行仿真實驗。仿真結(jié)果表明，相比貪心算法，二進制粒子群算法在部署相同數(shù)量的RSU前提下能為更多的車輛提供持續(xù)性的網(wǎng)絡(luò)服務(wù)。目前只考慮在各候選位置部署最多一個RSU，且RSU通信半徑固定?？紤]在各候選位置部署多個RSU及RSU半徑可變的部署方案有待進一步研究。

參考文獻：

[1] CUNHA F D D, BOUKERCHE A, VILLAS L, et al. Data communication in VANETs: a survey, challenges and applications[J]. Journal of Biological Chemistry, 2014, 274(39): 27605-27609.

[2] BEN B M, DRIRA W, FILALI F. Roadside units placement within city-scaled area in vehicular ad-hoc networks[C]// International Conference on Connected Vehicles and Expo, November 3?7, Vienna, Austria. New Jersey: IEEE Press, 2014: 1010-1016.

[3] ASLAM B, ZOU C C. Optimal roadside units placement along highways[C]//Consumer Communications and Networking Conference, January 8?11, Las Vegas, NV, USA. New Jersey: IEEE Press, 2011: 814-815.

[4] WU T J, LIAO W, CHANG C J. A cost-effective strategy for road-side unit placement in vehicular networks[J]. IEEE Transactions on Communications, 2012, 60(8): 2295-2303.

[5] 奎曉燕, 杜華坤, 肖雪峰, 等. 基于真實車載移動數(shù)據(jù)的RSU部署算法[J]. 北京郵電大學(xué)學(xué)報, 2015, 38(1): 114-118. KUI X Y, DU H K, XIAO X F, et al. Realistic vehicular mobility trace driven RSU deployment scheme[J]. Journal of Beijing University of Posts and Telecommunications, 2015, 38(1): 114-118.

[6] 奎曉燕, 杜華坤, 肖雪峰, 等. 基于流量的車載網(wǎng)絡(luò)路邊單元 RSU 部署方案[J]. 中南大學(xué)學(xué)報(自然科學(xué)版), 2016, 47(5): 1573-1579. KUI X Y, DU H K, XIAO X F, et al. Traffic amount based road side unit deployment scheme for vehicular network[J]. Journal of Central South University(Science and Technology), 2016, 47(5): 1573-1579.

[7] CHI J, JO Y, PARK H, et al. Intersection-priority based optimal RSU allocation for VANET[C]// Fifth International Conference on Ubiquitous and Future Networks, July 2?5, Da Nang, Vietnam. New Jersey: IEEE Press, 2013: 350-355.

[8] MEHAR S, SENOUCI S M, KIES A, et al. An optimized roadside units (RSU) placement for delay-sensitive applications in vehicular networks[C]// Consumer Communications and Networking Conference, January 9?12, Las Vegas, NV, USA. New Jersey: IEEE Press, 2015: 121-127.

[9] 張國富, 蔣建國, 夏娜, 等. 基于離散粒子群算法求解復(fù)雜聯(lián)盟生成問題[J]. 電子學(xué)報, 2007, 35(2): 323-327. ZHANG G F, JIANG J G, XIA N, et al. Solutions of complicated coalition generation based on discrete particle swarm optimization[J]. Acta Electronica Sinica, 2007, 35(2): 323-327.

[10] 陳娟, 蔡孫增, 朱正航, 等. 基于 IEEE 802.11p的車載無線通信原型系統(tǒng)的實現(xiàn)[J]. 電信科學(xué), 2014, 30(3): 72-79. CHEN J, CAI S Z, ZHU Z H, et al. Realization of WAVE system based on IEEE 802.11p[J]. Telecommunications Science,

2014, 30(3): 72-79.

丁正超（1992?），男，合肥工業(yè)大學(xué)計算機與信息學(xué)院碩士生，主要研究方向為物聯(lián)網(wǎng)、車聯(lián)網(wǎng)。

魏振春（1978?），男，合肥工業(yè)大學(xué)計算機與信息學(xué)院副教授、碩士生導(dǎo)師，主要研究方向為物聯(lián)網(wǎng)、嵌入式系統(tǒng)、分布式控制和離散事件系統(tǒng)。

馮琳（1979?），女，合肥工業(yè)大學(xué)計算機與信息學(xué)院副教授、碩士生導(dǎo)師，主要研究方向為計算機網(wǎng)絡(luò)、無線通信。

Deployment scheme of RSU based on connection time in VANET

DING Zhengchao1, WEI Zhenchun1,2, FENG Lin1
1. School of Computer and Information, Hefei University of Technology, Hefei 230009, China 2. Engineering Research Center of Safety Critical Industry Measure and Control Technology of Ministry of Education, Hefei 230009, China

For the roadside unit (RSU) placement problem in vehicular Ad Hoc network (VANET), the deployment scheme of RSU based on connection time was proposed. The scheme find the optimal positions of RSU for maximizing the number of vehicles while ensuring a certain level of connection time under the limited number of RSU. The problem was modeled as a maximum coverage problem, and a binary particle swarm algorithm was designed to solve it. The simulation experiment was carried out with the real Beijing road network map and taxi GPS data. The simulation results show that the algorithm is convergent, stable and feasible. Compared with the greedy algorithm, the proposed scheme can provide continuous network service for more vehicles.

vehicular Ad Hoc network, roadside unit placement, connection time, BPSO algorithm

TP393

A

10.11959/j.issn.1000?0801.2017080

1 引言

2016?12?13；

2017?03?22

國家自然科學(xué)基金資助項目（No.61502142）；國家國際科技合作專項基金資助項目（No.2014DFB10060）

Foundation Items: The National Natural Science Foundation of China (No.61502142), International S&T Cooperation Program of China (No.2014DFB10060)

車載自組織網(wǎng)絡(luò)（vehicular Ad Hoc network， VANET）是移動自主組織網(wǎng)絡(luò)（mobile Ad Hoc network，MANET）的特殊形式，是智能交通系統(tǒng)（intelligent transportation system，ITS）的重要組成部分。VANET由搭載無線通信設(shè)備（on-board unit，OBU）的車輛和路邊基礎(chǔ)設(shè)施（roadside unit，RSU）構(gòu)成，通過車間（vehicle to vehicle，V2V）通信以及車輛與路邊設(shè)施間（vehicle to infrastructure，V2I）通信，高效地實現(xiàn)了事故預(yù)警、輔助駕駛、道路交通信息查詢以及Internet接入服務(wù)等多種應(yīng)用[1]。由于車輛的快速移動會使得由車輛組成的網(wǎng)絡(luò)拓撲頻繁變化，造成較高的網(wǎng)絡(luò)時延和數(shù)據(jù)分組丟失率，因此車輛與 RSU間的通信對提升網(wǎng)絡(luò)性能有更加重要的作用[2]。若某特定的道路區(qū)域要達到全覆蓋，則需要部署大量的 RSU，然而部署、維護RSU需要高昂的成本，并且可以部署的 RSU的數(shù)量往往會受到一定的限制。在RSU數(shù)量受限的條件下，如何選擇最優(yōu)的位置來部署 RSU、加強網(wǎng)絡(luò)覆蓋、提升網(wǎng)絡(luò)服務(wù)質(zhì)量，成為一個重要的問題。