基于流量的車載網絡路邊單元RSU部署方案

奎曉燕，杜華坤，肖雪峰，李勇

（1. 中南大學 信息科學與工程學院，湖南 長沙，410083；2. 中南大學 地球科學與信息物理學院，湖南 長沙，410083；3. 清華大學 電子工程系，北京，100084）

基于流量的車載網絡路邊單元RSU部署方案

奎曉燕1，杜華坤2，肖雪峰1，李勇3

（1. 中南大學 信息科學與工程學院，湖南 長沙，410083；2. 中南大學 地球科學與信息物理學院，湖南 長沙，410083；3. 清華大學 電子工程系，北京，100084）

針對目前車載移動容遲網絡中的路邊單元（RSU）部署問題，提出一種基于車流量的車載網絡路邊單元RSU部署方案，該方案通過對車載網中路口的車流量的統計行為進行分析，在城市重要交通樞紐和交叉路口部署路邊單元RSU來進行輔助通信，從而有效提高車載移動網絡的通信效率。根據北京和上海兩地實際的車載移動數據，進一步對所提方案進行分析和評估。研究結果表明：在輔助車輛與車載之間的通信時，密集部署 RSU可以創造連續的通信機會，從而有效提高網絡性能。

車載網絡；路邊單元；RSU部署

科學的交通流量規劃，最優化利用道路資源和合理調度交通系統已成為交通、信息等領域的重要研究課題。車載移動網絡（vehicular ad hoc networks，VANET），作為下一代智能交通系統的重要組成部分正吸引越來越多研究者的關注［1］。在全球移動數據量迅猛增長的趨勢下，很難通過增加蜂窩網基礎設施來滿足用戶不斷增長的需求，因此，需要利用其他連接方式例如 Wi-Fi、移動自組織網絡、容遲網絡等方式來緩解移動網絡的壓力［2］。車載移動網絡作為其中的一種形式，能夠有效緩解移動數據對現有網絡造成的巨大壓力［3］。車載移動網絡主要有2種通信方式：車與車之間的通信和車與路邊單元間的通信［4］。路邊通信單元（road side units，RSU）是車載容遲網絡中部署在路邊進行輔助通信的設施，它與骨干網直接相連，并且可以與車輛進行無線通信。相比車載容遲網絡中的車輛，RSU具有更好的通信能力、覆蓋范圍和傳輸速度，而且可以同時與多輛車輛進行通信。此外，RSU還有較大的存儲空間，可以存儲信息，提高通信概率。因此，通過在道路交通系統中部署相關的RSU，一方面能有效地解決現有車載的互聯網接入問題，另一方面，也能極大地增加車載之間的通信機會，通過RSU緩存消息，實現車與車之間消息的高效傳遞。因此，研究基于城市環境的路邊單元 RSU輔助的車載網絡通信機制至關重要［5-6］。在RSU輔助的車載網絡中，1個最為重要的問題是如何部署RSU路邊單元，以實現車載網絡的性能最大化。在實際網絡和系統中，由于部署RSU會帶來一定的經濟開銷，因此，可以部署的RSU數量受到一定的限制。在RSU數量受限的條件下，如何選擇最優的位置來部署RSU，提高車載移動網絡的消息傳輸效率，包括提高消息傳送概率，降低消息傳送延遲等成為1個重要問題。針對車載移動容遲網絡中的RSU部署問題，本文作者提出了一種基于車流量的車載網絡路邊單元RSU部署方案。

1 相關工作

車載容遲網絡中的數據轉發和路由算法設計問題非常重要［5-15］。為了實現更高效和更快速的數據傳輸，ZHAO等［7-8］對車載容遲網絡中的數據傳輸算法進行了研究，主要涉及如何選擇數據傳輸對象。NEKOUI等［9］研究了利用路邊設施輔助通信時車輛間多跳傳輸的性能。以上工作存在的不足之處在于：由于車輛的密度分布不均勻和高移動特性，使得車輛之間無法形成穩定的多跳傳輸路徑來進行數據傳輸。DING等［10］在設計轉發算法時加入容遲特性并在路口設置固定節點來輔助通信，并證明了在車輛較稀少的情況下利用RSU可以有效地提高信息成功傳輸的概率。LU等［11］提出了在車載容遲網絡的 RSU中加入基于車輛關系的保護隱私的數據轉發算法。WANG等［12］對于一般車載網絡下的RSU部署方式進行了研究，然而，該文的RSU通信服務的對象是以中繼通信為基礎的車載自組織網絡，其主要研究目的是實現部署RSU時如何有效保障用戶的隱私，因此，與本文所提出的基于交通流量的 RSU部署來增強車載容遲網絡通信能力的思路并不相同。一般來說，部署RSU需要一定的設備和部署成本，因此，如何合理地將RSU部署到道路上的適當位置成為 1個十分重要的研究問題。KCHICHE等［13］提出了1種把RSU部署在道路交叉路口的策略。通過對每個路口定義相關參數來描述各個路口的繁忙程度，通過把RSU路邊單元部署在較為中心的交叉路口來減少數據傳輸延時。此外，LOCHERT等［14］也提出了相關算法，通過考慮車載網絡高度分割的特性來挑選城市中適合部署RSU的位置，并提出了相關的優化算法。然而，該算法僅考慮了車輛密度較低的情況，不適用于大城市環境下車輛密集的區域。LEE等［15］提出了通過部署 RSU來提高車載網絡的連通性和減少網絡間斷時間的方案，該方案可以有效地將網絡間斷時間控制和減少到10 s以內，并將網絡的連通概率提高到 72.5%左右。本文作者將研究基于真實環境車載流量的RSU部署方案，從而實現基于RSU的輔助通信，增強車載容遲網絡的通信能力。

2 基于車流量的RSU部署方案

2.1 問題定義

定義2-1 接觸間隔

RSU r與車輛u的接觸間隔CI，ru定義為該車輛從上一次離開該RSU通信范圍時刻t0直到再次進入此范圍的時間間隔，即

以上問題表述即為GSM、傳感器以及網狀網絡當中著名的覆蓋問題，然而，這些領域中提出的模型也無法直接應用于本文的環境，相比全覆蓋要求，本文環境可以只提供有限的覆蓋比例。

2.2 RSU部署方案

如前所述，考慮到車流量對于增強車載容遲網絡通信能力具有重要影響的因素，提出了基于車流量的RSU部署方案。首先對城市的車流量進行統計，將城市區域范圍內每一個區域車流量達到速率記為λ。對以下3種選擇部署策略進行研究：隨機選擇路口位置，選擇λ最大的路口和考慮λ分布的均勻部署。在考慮λ分布的均勻部署時，手動選取路口部署RSU，路口選擇的主要原則包括：選擇交通繁忙的路口，組成路口的兩條路交通流量均較大和空間上均勻分布這3個要素。

由于部署RSU的花費較高，而且在研究的初期階段在所有路口部署RSU是不現實的，因此主要研究針對RSU的選擇性部署。選擇北京和上海2個城市的真實數據展開研究工作。北京和上海兩地研究的路口數分別為213個和193個，在RSU的選擇性部署中，研究在其中63 和54個路口部署RSU的情況，具體部署情況如圖1～4所示。此外，在研究過程中，將session定義為車輛在網絡內移動時的一段連續的時間。當車輛進入RSU網絡覆蓋范圍時，即車輛與某個RSU相遇時，session開始，當車輛離開RSU網絡一段時間后，session終止。在1個session內，車輛一直處在運行狀態，其GPS記錄在時間上應當是連續的。當1輛車的GPS軌跡在時間上出現一定的中斷時，認為車輛在前后兩段時間的軌跡是獨立的，需要分開進行處理。考慮到連續的 GPS記錄在時間上的分布間隔最大為128 s，并且允許單獨1次記錄的丟失，所以，中斷時間的最小長度應該大于2×128=256 s。另外，考慮到車輛的運行速度較快，為保證數據處理盡量準確，將軌跡中斷的最小時間間隔設為5 min，即車輛的連續2個GPS數據間的時間差超過5 min就認為前、后2段時間的運動彼此獨立。本文主要研究車輛在網絡中的2個指標，第1個指標是車輛在1個session內平均經過的路口數；第2個指標是1個session的平均持續時間。

圖1 北京均勻部署RSU位置圖Fig.1 Uniform deployments of RSU in Beijing

圖2 北京最繁忙路口部署和隨機部署圖Fig.2 Busiest junctions deployment and random deployment in Beijing

圖3 上海均勻部署RSU位置圖Fig.3 Uniform deployments of RSU in Shanghai

圖4 上海最繁忙路口部署和隨機部署圖Fig.4 Busiest junctions deployment and random deployment in Shanghai

對于車載容遲網絡的通信能力，將按以下方法計算。在系統內部署RSU對信息進行緩存的情況下，車輛間通信頻率將發生變化。考慮2輛車c1和c2之間的相遇，假設2輛車在路口i部署有RSUi，且c1在t1時刻與 RSUi相遇，c2在 t2時刻與 RSUi相遇，假設t1＜t2，則在t1時刻c1將希望傳輸的內容存儲在RSUi內，而在t2時刻c2可以從RSUi處獲取c1希望傳輸的內容，本文認為c1和c2在t2完成了1次通信。考慮到信息傳輸的時效性和RSU中存儲空間的限制，信息在RSU中的存在時間設定了1個時間上限TRSU，信息在RSU中存儲時間超過TRSU則被丟棄。在這種情況下，若t2-t2＜TRSU，則2車借助RSU的通信可以發生，反之則由于信息被刪除，造成車輛間的通信無法完成。

3 性能評估與仿真分析

3.1 仿真環境與數據處理

這里采用北京和上海這2個中國最大城市的車載移動數據對性能進行評估。上海的數據記錄了 2 058輛出租車在2012-02內的車載移動數據。車載數據點記錄的規則為：若車上有乘客，每15 s進行1次數據記錄；否則，每1 min記錄1次移動數據。北京的數據采用同樣的方法在2013-05對27 000輛出租車進行移動位置記錄。鑒于通過GPS獲得的位置數據在記錄頻率上并不統一和具有不準確性，并且會有噪聲的影響，因此需要對數據進行預處理。首先根據北京和上海地圖上的道路坐標標注，對坐標記錄數據進行修正；其次通過線性回歸的方法進行地理位置插值，使得所記錄的位置數據按照每15 s的時間間隔來記錄節點的位置。

為了選擇部署RSU路邊單元的地點，根據重要的交通樞紐和十字路口對整個城市進行識別［16］。通過利用Voronoi算法［17-18］，按照車流量粒度由大到小進行分區。分區示例圖如圖5所示。根據所分區域，通過在區域的中心位置部署 RSU路邊單元來仿真車載網絡的運行情況。通過仿真來對比本文提出的不同的車載移動網絡RSU部署策略的性能，算法在執行過程中考慮的參數主要包括通信時間間隔、平均相遇時間等［19-20］。

3.2 仿真結果分析

圖5 Voronio區域劃分方法圖Fig.5 Voronio diagram for zoning method

表1 北京不同部署方式下V2V通信頻率的變化Table 1 Variation of V2V communication frequency under different deployment schemes in Beijing

表2 上海不同部署方式下V2V通信頻率的變化Table 2 Variation of V2V communication frequency under different deployment schemes in Shanghai

設定TRSU=60 min以保證RSU能夠有效地幫助車輛之間進行通信。仿真中用完全部署作為最優情況來作為參照，同時也與V2V通信模式的相遇間隔時間進行對比。表1和表2所示分別為北京和上海RSU部分部署時，任意兩輛車之間平均相遇時間間隔的統計結果。與預期不同，兩輛車之間的平均相遇時間并沒有因為選擇性地部署RSU而減少。主要原因在于，在均勻部署中，部署RSU間距比較大，而在隨機部署中，存在一個范圍內密集部署多個RSU的情況；在RSU比較密集的地區，車輛更有可能連續地遇到多個存有目標車輛信息的RSU，使得相遇間隔更小。在最繁忙部署中，同樣有多個RSU距離很近的現象，但是，平均相遇時間間隔比隨機部署的大。因此，在比較繁忙的路線上，由于車輛的行進路線比較固定而且路線很少，兩輛車依靠RSU進行連續多次通信主要在兩輛車都沿同一路線行進時發生，從而使得通信總次數比隨機部署的小，相應的相遇間隔更大。

從表1和表2可以看出：在車輛與車輛之間的通信中，在一定的地域密集部署RSU可以有效增加車輛間的通信次數，多次相遇可能集中在1個時段中，因此，有效利用連續的通信機會需要RSU間的良好協作和有效的信息分配。研究部署策略時的另一個指標為車輛接受 RSU網絡服務的時間特性。選取的指標包括：在網絡內的1個session內遇到的RSU數目，session持續時間，與RSU的平均相遇時間間隔以及車輛與整個RSU網絡的平均相遇時間間隔。在以上4個指標中，在1個session內遇到的RSU數目和session的持續時間體現的是車輛在運行的過程中能夠從 RSU中獲取信息的多少，而與RSU的平均相遇時間間隔和車輛與網絡的平均相遇時間間隔體現的是 RSU覆蓋服務的范圍。

表3和表4所示分別為北京和上海不同部署方案對車輛與RSU相遇的影響。從表3和表4可以看出：在最繁忙的路口部署RSU能夠使車輛與RSU的總相遇次數最多，車輛在網絡中移動時可以遇到更多的RSU，并且通信的總時間更長。在均勻部署情況下，由于部署相對稀疏，因此，車輛在網絡中移動時遇到的RSU數目相對變少，但是均勻部署的覆蓋面更大，車輛進入RSU網絡的概率更高。在完全部署時，車輛與網絡相遇的間隔時間更大，可以解釋為，在完全部署時，車輛更多的情況下是一直在網絡內移動，進出網絡的次數減少造成相遇間隔增加。

3.3 部署策略總結

通過上述對不同部署策略的研究，可以得出以下結論：

1） 在RSU輔助車輛之間的消息傳播方面：密集部署RSU能夠創造連續的通信機會，充分利用這些機會能夠在兩車之間傳輸比較大的信息。

2） 在車輛從RSU獲取信息方面：在繁忙的交通路口部署 RSU可以保證車輛在網絡內移動時可以遇到更多的路口，從而獲取更多的信息。參照路口分布和車輛到達速率λ的均勻部署策略，可以保證更大的覆蓋面，從而使得車輛進入 RSU覆蓋范圍的概率增大。因此，當希望通過RSU獲得大量的信息時，在繁忙路口部署RSU可以增大與RSU的總通信時間，獲取更多的信息。當希望用少量的RSU滿足更多車輛的需求，并且車輛從RSU中并不需要獲取特別多的信息時，均勻部署有更好的效果。需要注意的是：繁忙路口處車輛非常集中，可能造成車輛與RSU通信速率的下降，此時為保證網絡整體性能，在繁忙地區可能需要部署更多的RSU。

表3 北京不同部署方案對車輛與RSU相遇的影響Table 3 Effect of vehicles encounter with RSU under different deployment schemes in Beijing

表4 上海不同部署方案對車輛與RSU相遇的影響Table 4 Effect of vehicles encounter with RSU under different deployment schemes in Shanghai

4 結論

1） 在輔助車載通信時，密集部署RSU可以創造連續的通信機會。在繁忙路口部署和均勻部署時，由于RSU間距較大，更適合于輔助V2V通信中傳輸較小數據的情況。

2） 在車輛利用RSU獲取外部信息時，在繁忙路口部署可以保證在車輛進入網絡后，可以與更多的RSU相遇，并且通信時間更長，而均勻部署可以使車輛更頻繁地與RSU網絡接觸，更好保證獲取信息的及時性。

3） 根據實際城市交通流量得到的結論對于在真實車載網絡中部署RSU具有較大的實際指導意義。

［1］ ALSULTAN S， ALDOORI M M， ALBAYATTI A H， et al. A comprehensive survey on vehicular ad hoc network［J］. Journal of Network and Computer Applications， 2014， 37（1）： 380-392.

［2］ DU Rong， CHEN Cailian， YANG Bo， et al. Effective urban traffic monitoring by vehicular sensor networks［J］. IEEE Transactions on Vehicular Technology， 2015， 64（1）： 273-286.

［3］ ZHANG Rongqing， CHENG Xiang， YANG Liuqing， et al. A novel centralized TDMA-based scheduling protocol for vehicular networks［J］. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（1）： 411-416.

［4］ 李晉國， 林亞平， 李睿， 等. 車載自組織網絡中基于橢圓曲線零知識證明的匿名安全認證機制［J］. 通信學報， 2013， 34（5）：52-61. LI Jinguo， LIN Yaping， LI Rui， et al. Secure anonymous authentication scheme based on ellipticcurve and zeroknowledge proof in VANET［J］. Journal on Communications，2013， 34（5）： 52-61.

［5］ 何鵬， 閻保平， 李志， 等. CM-MAC：一種基于分簇的多信道車載網 MAC協議［J］. 計算機研究與發展， 2014， 51（3）：502-510. HE Peng， YAN Baoping， LI Zhi， et al. CM-MAC： A cluster-based multi-channel MAC protocol for VANET［J］. Journal of Computer Research and Development， 2014， 51（3）：502-510.

［6］ 姜海濤， 張宏， 李千目. 車載時延容忍網絡路由協議研究［J］.通信學報， 2013， 34（3）： 76-84. JIANG Haitao， ZHANG Hong， LI Qianmu. Research on routing protocol of vehicular delay-tolerant networks［J］. Journal on Communications， 2013， 34（3）： 76-84.

［7］ ZHAO Jing， CAO Guohong. VADD： vehicle-assisted data delivery in vehicular ad hoc networks［J］. IEEE Transactions onVehicular Technology， 2006， 57（3）： 1910-1922.

［8］ SONG C， LIU M， WEN Y， et al. Buffer and switch： an efficient road-to-road routing scheme for VANETs［C］// IEEE International Conference on Mobile Ad-hoc and Sensor Networks. Beijing， 2011： 310-317.

［9］ NEKOUI M， ESLAMI A， PISHRO-NIK H. The capacity of vehicular ad hoc networks with infrastructure［C］// IEEE 6th International Symposium on Modeling and Optimization in Mobile， Ad Hoc， and Wireless Networks and Workshops. Berlin，Germany， 2008： 267-272.

［10］ DING Yong， LI Xiao. SADV： static-node-assisted adaptive data dissemination in vehicular networks［J］. IEEE Transactions on Vehicular Technology， 2010， 59（5）： 2445-2455.

［11］ LU Rongxing， LIN Xiaodong， SHEN Xuemin. SPRING： a social-based privacy- preserving packet forwarding protocol for vehicular delay tolerant networks［C］// 29th IEEE International Conference on Computer Communications （INFOCOM 2010）. San Diego， USA， 2010： 1-9.

［12］ WANG Shengwei， CHANG Mengyi. Roadside units allocation algorithms for certificate update in VANET environments［C］// 17th IEEE Asia-Pacific Conference on Communications （APCC）. Sabah， Malaysia， 2011： 472-477.

［13］ KCHICHE A， KAMOUN F. Centrality-based access-points deployment for vehicular networks［C］// IEEE International Conference on Telecommunications（ICC）. Cape Town， South Africa， 2010： 700-706.

［14］ LOCHERT C， SCHEUERMANN B， WEWETZER C， et al. Data aggregation and roadside unit placement for a vanet traffic information system［C］// Vanet Proceedings of the Fifth ACM International Workshop on Vehicular Inter-networking. San Francisco， California， USA： ACM， 2008： 58-65.

［15］ LEE J， KIM C M. A roadside unit placement scheme for vehicular telematics networks［J］. Advances in Computer Science and Information Technology， 2010， 6059（1）： 196-202.

［16］ RAW R S， DAS S. Performance analysis of P-GEDIR protocol for vehicular ad hoc network in urban traffic environments［J］. Wireless Personal Communications， 2013， 68（1）： 65-78

［17］ DEZA M M， DEZA E. Voronoi diagram distances［M］. Berlin，Heidelberg： Springer， 2013： 339-347.

［18］ AMMARI H M， DAS S K. Promoting heterogeneity， mobility，and energy-aware voronoi diagram in wireless sensor networks［J］. IEEE Transactions on Parallel and Distributed Systems， 2008， 19（7）： 995-1008.

［19］ ZHANG Rongqing， CHENG Xiang， YANG Liuqing， et al. A novel centralized TDMA-based scheduling protocol for vehicular networks［J］. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（1）： 411-416.

［20］ KUMAR N， LEE J H， RODRIGUES J J P C. Intelligent mobile video surveillance system as a bayesian coalition game in vehicular sensor networks： learning automata approach［J］. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（3）：1148-1161.

（編輯 楊幼平）

Traffic amount based road side unit deployment scheme for vehicular network

KUI Xiaoyan1， DU Huakun2， XIAO Xuefeng1， LI Yong3

（1. School of Information Science and Engineering， Central South University， Changsha 410083， China；2. School of Geosciences and Info-Physics， Central South University， Changsha 410083， China；3. Department of Electronic Engineering， Tsinghua University， Beijing 100084， China）

The road side unit （RSU） deployment issues were investigated. Based on the network traffic volume， the RSU into the network was deployed. The scheme analyzed the size of the statistical behavior of traffic flow through the junction in the vehicle network， and deployed the RSU to assist communication in the major transportation hub and intersections of the city， which can effectively improve the communication efficiency of the vehicle delay tolerant network. With the two actual vehicle traces of Beijing and Shanghai， analysis and evaluation of the proposed scheme were carried out. The results demonstrate that the dense deployments of the RSU can create continuous communication opportunities in the communication between the auxiliary vehicle and the vehicle， and can effectively improve the network performance.

vehicular networks； road side unit； RSU deployment

TP393.0

A

1672-7207（2016）05-1573-07

10.11817/j.issn.1672-7207.2016.05.017

2015-05-14；

2015-07-25

國家自然科學基金資助項目（61502540，61502057，61572530，61402542）；國家留學基金資助項目（2015［3012］）；湖南省自然科學基金資助項目（2015JJ4077） （Projects（61502540， 61502057， 61572530， 61402542） supported by the National Natural Science Foundation of China； Project（2015［3012］ supported by China Scholarship Council； Project（2015JJ4077） supported by the National Science Foundation of Hunan Province， China）

杜華坤，博士，講師，從事信號處理研究；E-mail： hkdu2008@126.com