車載自組織網絡中基于連接時長的RSU部署方案

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

（1. 合肥工業大學計算機與信息學院，安徽 合肥 230009；2. 安全關鍵工業測控技術教育部工程研究中心，安徽 合肥 230009）

車載自組織網絡中基于連接時長的RSU部署方案

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

（1. 合肥工業大學計算機與信息學院，安徽 合肥 230009；2. 安全關鍵工業測控技術教育部工程研究中心，安徽 合肥 230009）

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

車載自組織網絡；路邊基礎設施部署；連接時長；二進制粒子群算法

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

2 RSU部署模型

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

圖1 路段劃分示意

由所有路口和邏輯路段的中心構成部署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的行程持續時長，定義變量 tij(1≤i≤n,1≤j≤m)，tij＞0表示車輛 vj與部署在候選位置 pi上的 RSU之間的連接時長（車輛vj進入該RSU通信范圍的時刻起直至離開該范圍的時間間隔），引入變量 sij(1≤i≤n,1≤j≤m)表示車輛vj經過候選位置pi的平均車速，那么tij就可以通過式（2）求得：

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

將式（2）代入式（3），進一步轉化為：

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

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

3 求解算法設計

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

3.1 粒子編碼

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

3.2 初始化

（1）初始化粒子群參數，包括種群規模 M、最大迭代次數tmax、學習因子c1和c2、最大慣性權重ωmax、最小慣性權重ωmin、最大擾動因子gmax。

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

3.3 適應度函數

本文適應度函數設計為：

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

3.4 粒子的位置和速度更新

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

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

其中，ωmax為最大慣性權重，ωmin為最小慣性權重，t為當前的迭代次數，gmax為最大擾動因子，擾動因子g的取值可表示為：

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

3.5 終止條件

設置最大迭代次數tmax，每次迭代通過適應度函數時對粒子位置進行優劣評定，更新粒子當前的個體最優位置和全局最優位置，循環更新粒子的速度和位置，達到最大迭代次數tmax后終止。

4 仿真實驗與分析

4.1 仿真參數

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

圖2 RSU候選位置

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

4.2 結果與分析

（1）算法的收斂性分析

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

由圖3可知，二進制粒子群具有較好的收斂性，前20代快速收斂，在第20代到第80代過程中，多次遇到局部最優解，由于在慣性權重中引入自適應擾動機制，算法很快就跳出局部最優解，當迭代到第80代左右時，目標函數收斂于96%。

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

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

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

（2）算法的性能分析

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

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

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

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

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

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

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

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

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

5 結束語

針對城市場景下 VANET中路邊基礎設施的部署問題進行了研究，提出了一種基于連接時長的RSU部署方案，設計了二進制粒子群算法進行求解，并結合北京市路網地圖和出租車移動軌跡進行仿真實驗。仿真結果表明，相比貪心算法，二進制粒子群算法在部署相同數量的RSU前提下能為更多的車輛提供持續性的網絡服務。目前只考慮在各候選位置部署最多一個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] 奎曉燕, 杜華坤, 肖雪峰, 等. 基于真實車載移動數據的RSU部署算法[J]. 北京郵電大學學報, 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] 奎曉燕, 杜華坤, 肖雪峰, 等. 基于流量的車載網絡路邊單元 RSU 部署方案[J]. 中南大學學報(自然科學版), 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] 張國富, 蔣建國, 夏娜, 等. 基于離散粒子群算法求解復雜聯盟生成問題[J]. 電子學報, 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的車載無線通信原型系統的實現[J]. 電信科學, 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?），男，合肥工業大學計算機與信息學院碩士生，主要研究方向為物聯網、車聯網。

魏振春（1978?），男，合肥工業大學計算機與信息學院副教授、碩士生導師，主要研究方向為物聯網、嵌入式系統、分布式控制和離散事件系統。

馮琳（1979?），女，合肥工業大學計算機與信息學院副教授、碩士生導師，主要研究方向為計算機網絡、無線通信。

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

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

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

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