城市環(huán)境車聯(lián)網(wǎng)中基于近似算法的RSU部署方案

朱鈞宇，黃傳河，范茜瑩，覃匡宇，付斌

?

城市環(huán)境車聯(lián)網(wǎng)中基于近似算法的RSU部署方案

朱鈞宇1，黃傳河1，范茜瑩1，覃匡宇1，付斌2

（1. 武漢大學(xué)計算機學(xué)院，湖北 武漢 430072；2. 美國得克薩斯里奧格蘭德河谷大學(xué)，得克薩斯 愛丁堡 78539）

為了使用盡可能少的RSU實現(xiàn)對目標區(qū)域的有效覆蓋，設(shè)計街道模型，將對區(qū)域的覆蓋轉(zhuǎn)化為對區(qū)域內(nèi)街道的覆蓋，然后，在該模型下提出基于貪心策略的多項式（GBP, greedy-based polynomial）時間近似算法，得到RSU的部署方案以解決覆蓋問題。針對城市中一些地形復(fù)雜的區(qū)域，設(shè)計Cue模型（complex urban environment model），將目標區(qū)域劃分為子區(qū)域，然后提出基于shifting策略的多項式時間近似算法，并對算法的近似比率和時間復(fù)雜度進行了理論分析與證明。仿真結(jié)果表明，算法GBP能夠有效地解決城市環(huán)境車聯(lián)網(wǎng)中的區(qū)域覆蓋問題。

車聯(lián)網(wǎng)；RSU部署；區(qū)域覆蓋；近似算法

1 引言

車輛自組織網(wǎng)絡(luò)（VANET, vehicular ad hoc network）作為現(xiàn)代智能交通系統(tǒng)（ITS, intelligent transportation system）的重要組成部分，主要通過無線通信技術(shù)來提高道路安全和交通運營效率，在輔助安全駕駛的同時提供多方面的娛樂服務(wù)信息，來提升駕駛員和乘客的交通體驗[1]。VANET主要由車輛節(jié)點和路邊節(jié)點（RSU, road side unit）組成，其主要通信方式分為2種：車輛與車輛（V2V, vehicle-to-vehicle）之間的通信以及車輛與RSU（V2R, vehicle-to-RSU）之間的通信，V2V使車輛可以與相鄰車輛節(jié)點共享信息，V2R使RSU能夠與其通信范圍內(nèi)的車輛節(jié)點進行信息交互[2]。

作為VANET的輔助通信設(shè)施，RSU可以應(yīng)對VANET中因節(jié)點的快速移動引起的動態(tài)拓撲變化，能有效地解決VANET的接入問題以及改善車輛節(jié)點之間的通信質(zhì)量[3]。另外，在VANET中部署RSU實現(xiàn)對道路區(qū)域的覆蓋，有助于緊急交通信息在網(wǎng)絡(luò)中的實時可靠傳輸[4]。然而，大量部署RSU不但會帶來較高的安裝和維護成本，還有以下難點：1) RSU的部署受車輛移動的影響，而車輛的實際運動軌跡是很難提前獲取的；2) RSU的候選部署點集合很大，從中選取最優(yōu)RSU部署點的過程比較復(fù)雜；3) RSU的部署受到很多因素的影響，如交通特征、可部署RSU的數(shù)量以及道路網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和地理特征[5,6]。因此，在RSU數(shù)量受限的條件下，如何選擇最優(yōu)的位置來部署RSU，實現(xiàn)區(qū)域的覆蓋以增強網(wǎng)絡(luò)連通性，成為一個重要的問題。

本文主要研究了VANET中RSU的部署方案，實現(xiàn)目標區(qū)域的覆蓋以保證其網(wǎng)絡(luò)連通性，更好地為VANET中信息的實時可靠傳輸提供服務(wù)。為此，提出以下問題：假設(shè)城市環(huán)境中存在若干RSU候選點可供選擇，如何進行RSU的部署，能夠使用最少的RSU實現(xiàn)目標區(qū)域的覆蓋。針對上述問題，本文首先提出了街道模型，該模型中RSU最多覆蓋條街道并且僅覆蓋每條街道的一部分。在此模型下，設(shè)計了采用基于貪心策略的多項式（GBP, greedy-based polynomial）時間近似算法來獲取RSU的部署方案，通過將區(qū)域覆蓋問題轉(zhuǎn)化為區(qū)域內(nèi)街道的覆蓋問題，首先，得到覆蓋每條街道的RSU集合，然后，求得所有街道的RSU集合，取并集就是覆蓋目標區(qū)域所需的RSU集合。本文主要考慮RSU的部署問題，其中，假定RSU擁有足夠的信號強度，同時具備足夠的處理能力和帶寬，能夠滿足服務(wù)質(zhì)量和通信容量等需求。

另外，由于城市環(huán)境中某些地形比較復(fù)雜，街道信息難以獲取，不宜采用街道模型來解決區(qū)域覆蓋問題。因此，針對一些地形復(fù)雜的城市區(qū)域，本文設(shè)計了Cue模型，結(jié)合Hochbaum等[7]提出的shifting策略，提出了一種多項式時間近似算法。算法將目標區(qū)域劃分為不同分區(qū)，然后，得到每個分區(qū)的RSU部署方案，選擇使用RSU最少的方案，即近似最優(yōu)RSU部署方案。通過理論分析可知，該算法能夠取得較高的近似精度。

綜上所述，本文的主要貢獻包括以下3個方面。

1) 本文提出了街道模型，在該模型中，每個RSU至多覆蓋條街道且僅覆蓋每條街道上的一個區(qū)間?；谠撃Ｐ?，將區(qū)域覆蓋問題轉(zhuǎn)化為對區(qū)域內(nèi)街道的覆蓋問題，然后，設(shè)計了多項式時間近似因子為的近似算法GBP。

3) 針對城市環(huán)境中一些地形復(fù)雜的區(qū)域，由于街道信息難以收集，采用街道模型的效果不是很理想。本文提出了Cue模型，然后，設(shè)計了基于shifting策略的多項式時間近似算法，通過將目標區(qū)域劃分為子區(qū)域，找出子區(qū)域的覆蓋方案，進而得到目標區(qū)域的覆蓋方案。最后，對算法進行了相應(yīng)的理論分析與證明。

2 相關(guān)工作

通常用以下幾個因素來衡量VANET中RSU部署方案的性能，如區(qū)域的覆蓋率[8]、安裝和維護設(shè)施的成本以及RSU輔助下信息傳輸?shù)臅r延[9]。現(xiàn)有的工作主要研究如何平衡這些因素以實現(xiàn)理想的網(wǎng)絡(luò)性能和通信質(zhì)量[10]。

Omar等[11]提出了新的網(wǎng)關(guān)部署策略，在最小化網(wǎng)關(guān)安裝成本的同時保證了車輛和網(wǎng)關(guān)通信的概率大于預(yù)先定義的閾值，同時最大化提出的目標函數(shù)值，所提算法假設(shè)道路上車輛的數(shù)目以及車輛在城市的每個地點相遇的概率為已知信息。然而，道路上車輛的數(shù)目以及車輛的相遇概率等信息不僅涉及用戶的隱私，在實際情況下也是很難收集的。

Trullols等[12]針對DP（dissemination point）的部署問題，討論了3種不同的區(qū)域覆蓋問題形式，包括最大覆蓋率問題（MCP, maximum coverage problem）、背包問題（KP, knapsack problem）以及與時間閾值相關(guān)的最大覆蓋問題（MCTTP, maximum coverage with time threshold problem）。為了能夠讓DP在目標區(qū)域內(nèi)覆蓋更多的車輛，本文主要研究MCP，提出了簡單的啟發(fā)式算法，提高車輛和DP之間的通信性能，同時優(yōu)化傳輸時延。該啟發(fā)式算法能夠在較大規(guī)模的環(huán)境下得到近似最優(yōu)的方案，但是只有在獲取車輛移動特征的前提下才能實現(xiàn)對移動用戶的近似最優(yōu)覆蓋。

基于Trullols等[12]的研究，Cavalcante等[13]提出了一種基因算法（GA）用來解決MCTTP。Lin等[14]提出了一種車載骨干網(wǎng)絡(luò)協(xié)議來動態(tài)支持從RSU到沿著高速公路行駛的車輛的信息流，然后提出了一種分析模型，以精確表征在規(guī)定的中斷概率約束下可達到的最大吞吐率。根據(jù)OGM （overlap based greedy method），Rizk等[15]提出了在城市和鄉(xiāng)村地區(qū)基于貪心算法的RSU部署方案，且主要考慮RSU的覆蓋范圍和重復(fù)覆蓋率，實現(xiàn)了較好的目標區(qū)域覆蓋效果。

為了最小化RSU的部署數(shù)目，Yan等[16]提出了在交叉路口安裝AP（access point）的問題，分別討論了如何使用最少的AP來保證區(qū)域內(nèi)的車輛均在網(wǎng)絡(luò)覆蓋內(nèi)以及在有限的預(yù)算下部署AP才能最大化網(wǎng)絡(luò)可覆蓋的車輛比例，然后，提出了多項式時間啟發(fā)式算法（ABS, adapted-bipartite-based heuristics），通過使用ABS，證明了在普通平面圖中的NP-hard問題均可在二分圖中多項式時間內(nèi)解決。Zhu等[17]研究基站可最大限度地延長城市覆蓋范圍的關(guān)鍵問題，然后，提出了最大化預(yù)期感測覆蓋范圍的新目標，同時考慮到了車輛的隨機移動性和車輛行駛的規(guī)律。Cheng等[18]采用背包斯坦納樹（KCST, knapsack constrained Steiner tree）模型來描述特定區(qū)域的覆蓋問題，然后，利用拉格朗日分解方法來求近似最優(yōu)方案，同時考慮了安裝預(yù)算和網(wǎng)絡(luò)覆蓋率。

Wang等[19]分析了VANET在RSU輔助下的信息傳輸時延，并提出了數(shù)學(xué)模型來描述道路信息傳輸?shù)钠骄鶗r延和鄰居RSU之間距離的關(guān)系，該結(jié)果為時延要求較高的交通應(yīng)用提供了一種可參考的RSU部署距離。Zhang等[20]設(shè)計了一種通用的系統(tǒng)架構(gòu)來優(yōu)化車聯(lián)網(wǎng)的性能，分別針對實時交通和時延容忍交通2種情況進行分析，得到了2種不同情況下獲得的吞吐量，并對時延容忍交通的時延界限作了說明，最后，提出了AP部署算法，在滿足服務(wù)質(zhì)量的同時部署最少的AP。

Kim等[21]將不同狀態(tài)的RSU部署方案相結(jié)合，分別在固定地點部署RSU、利用公共交通和政府擁有的可完全控制的車輛，提出了新的RSU部署框架，在控制預(yù)算的同時實現(xiàn)時空覆蓋的最大化。Liu等[22]分析了VANET高速公路情況下緊急信息廣播的總時延，進而得到了RSU最優(yōu)部署數(shù)目和道路距離的關(guān)系。Jalooli等[23]以最小傳輸時延為目標，提出了基于安全應(yīng)用的RSU部署算法。Mukherjee等[24]首次考慮了事件傳輸時RSU的成本開銷以及其容量。Li等[25]同時考慮了VANET中車輛的多樣性，數(shù)據(jù)的不同種類、大小和時間敏感性以及RSU的有限容量，提出了上下文感知的優(yōu)化問題，并設(shè)計了相應(yīng)的解決方案。為了實現(xiàn)特定區(qū)域內(nèi)信息傳輸?shù)某杀咀钚?，Li等[26]設(shè)計了四叉樹模型來表示區(qū)域的層次分解，然后選擇最優(yōu)的RSU將信息轉(zhuǎn)發(fā)到目標區(qū)域。

Sun等[27]提出了一種高成本效益的RSU部署方案，以保證任何地方的OBU（on board unit）能夠在一定的駕駛時間內(nèi)與RSU進行通信，并且調(diào)整路由來更新短期證書的額外時間開銷是很小的?？鼤匝嗟萚28]根據(jù)真實的車輛行駛數(shù)據(jù)提出了綜合考慮中心性和均勻性的RSU部署算法，以優(yōu)化網(wǎng)絡(luò)整體性能。劉明等[29]對隨機部署方式下的覆蓋問題進行了研究，并且提出了一個數(shù)學(xué)模型，只要已知監(jiān)測范圍和節(jié)點感知半徑的比值，就可以計算出達到服務(wù)質(zhì)量期望所需要的節(jié)點數(shù)量。黃曉等[30]針對在實際應(yīng)用中，節(jié)點隨機部署可能出現(xiàn)與基站不能正常通信的問題，提出了一種使用與基站連通的節(jié)點作為代理解決基站不可達節(jié)點的方案，并根據(jù)節(jié)點存儲的路由信息給出了一種節(jié)點連通性的判定算法。謝永等[31]提出了一種面向高速公路場景的無間隙協(xié)助下載方法，充分利用車輛和AP的交互，進一步提高協(xié)助下載的穩(wěn)定性。

大多數(shù)工作著重于研究通過優(yōu)化RSU的部署來提高網(wǎng)絡(luò)吞吐量、降低消息傳輸時延以及RSU的安裝維護開銷，而本文針對不同的城市環(huán)境，將對目標區(qū)域的覆蓋分別轉(zhuǎn)化為對區(qū)域內(nèi)街道的覆蓋以及子區(qū)域的覆蓋，然后在已有的RSU候選放置點中找出對應(yīng)的近似最優(yōu)RSU部署方案，能夠有效地實現(xiàn)對目標區(qū)域的網(wǎng)絡(luò)覆蓋，有助于網(wǎng)絡(luò)內(nèi)信息的實時可靠傳輸。

3 網(wǎng)絡(luò)場景和覆蓋問題描述

假定目標區(qū)域內(nèi)所有街道均在一個平面圖上，將交叉路口看作圖中的節(jié)點。地理區(qū)域示意如圖1所示，其中，虛線圓圈內(nèi)的區(qū)域即所要覆蓋的目標區(qū)域，RSU設(shè)施表示可供選擇的RSU部署候選點。假定目標區(qū)域中有一系列隨機分布的RSU部署候選點，本文的目標是從候選點中選擇最少數(shù)目的位置點來部署RSU，從而實現(xiàn)區(qū)域的最大覆蓋。

圖1 地理區(qū)域示意

綜上所述，本文將目標區(qū)域的覆蓋問題轉(zhuǎn)化為該區(qū)域內(nèi)街道集合的覆蓋問題，然后找出能夠覆蓋街道集合的最小RSU集合，實現(xiàn)區(qū)域覆蓋的最大化。本文所用到的參數(shù)及其含義如表1所示。

表1 參數(shù)定義

4 基于貪心策略的街道區(qū)間覆蓋方案

為了解決區(qū)域覆蓋問題，將對區(qū)域內(nèi)街道的覆蓋問題轉(zhuǎn)化為街道區(qū)間的覆蓋問題。針對該問題，本節(jié)首先提出了街道區(qū)間覆蓋算法，在此基礎(chǔ)上提出了基于貪心策略的多項式時間近似算法，并對算法進行了相關(guān)的理論分析。

4.1 基于貪心策略的多項式時間近似算法

本節(jié)提出了街道模型，在該模型中，每個RSU至多覆蓋條街道且僅覆蓋每條街道上的一個區(qū)間。針對該覆蓋模型，本文提出了基于貪心策略的多項式時間近似算法來解決目標區(qū)域的覆蓋問題。

為了實現(xiàn)目標區(qū)域的有效覆蓋，首先提出了區(qū)間覆蓋算法（interval covering algorithm），如算法1所示。通過該算法得到覆蓋目標區(qū)域內(nèi)每條街道所需的RSU集合，在步驟6)中得到區(qū)間的最左覆蓋I，將I加入目標集合，循環(huán)該過程直到區(qū)間被覆蓋。在此基礎(chǔ)上設(shè)計了基于貪心策略的多項式時間近似算法，如算法2所示，算法2在步驟5)調(diào)用算法1，得到區(qū)域內(nèi)所有街道的覆蓋方案，對所有街道的RSU集合取并集（步驟8)），即覆蓋目標區(qū)域所需要的RSU集合。

算法1 區(qū)間覆蓋算法

2) 令;

3) 令();

4) 令=I∪,∈{1, 2,…,};

5) 重復(fù)以下操作

6) if (∈I&最大)

7)=∪{I};

8)Uncovered= Uncovered ? I;

10) 輸出為區(qū)間覆蓋方案；

11) end

算法2 基于貪心策略的多項式時間近似算法

輸入 路邊單元RSU候選點集合，目標覆蓋街道集合

5) 調(diào)用區(qū)間覆蓋算法（算法1）；

6) 返回街道S的覆蓋方案C；

7) end for

9) end

4.2 路邊節(jié)點對街道區(qū)間的覆蓋

本節(jié)分析了一維街道區(qū)間覆蓋問題的時間復(fù)雜度，并證明了街道模型下提出的多項式時間算法的近似因子。

引理1 對于一維區(qū)間覆蓋問題，存在時間復(fù)雜度為(log)的算法，這里為算法輸入的街道區(qū)間數(shù)目。

證畢。

定理1 在街道模型下，存在用于解決區(qū)域覆蓋問題的近似因子為的多項式時間近似算法。

證畢。

4.3 NP-hard問題

本節(jié)將證明定理2，得到當每個RSU覆蓋3條街道時，區(qū)域覆蓋問題仍然是NP-hard問題。

證畢。

5 基于shifting策略的區(qū)域覆蓋方案

由于一些城市區(qū)域的地形比較復(fù)雜，難以獲取具體街道信息，利用基于街道模型的GBP算法不能有效地解決區(qū)域覆蓋問題。針對這種環(huán)境，本文設(shè)計了相應(yīng)的Cue模型用于解決區(qū)域覆蓋問題，該模型能夠體現(xiàn)更多的城市環(huán)境特性。在該城市模型下，結(jié)合Hochbaum等[7]提出的shifting策略，本文提出了一個解決區(qū)域覆蓋問題的多項式時間近似算法，并對算法進行了相應(yīng)的理論分析和證明。

5.1 Cue模型及相關(guān)參數(shù)定義

基于shifting策略，本文設(shè)計了多項式時間近似算法用來解決區(qū)域覆蓋問題，在該近似算法中，采用了Cue模型。與街道模型相比，該城市模型能體現(xiàn)更多的地理特征。模型中用到的術(shù)語及其含義如下。

定義1 City表示部署有路邊節(jié)點RSU的城市環(huán)境。

1) City的街道圖(,)為一個平面圖，圖中的節(jié)點表示交叉路口，邊(,)為連接節(jié)點和的街道區(qū)間。

圖2 d-star示例

1) 每個RSU的傳輸范圍為。

3) 每個RSU均具有的覆蓋性質(zhì)。

城市模型中的一個特例：當4時，每個RSU覆蓋街道的一個區(qū)間，或交叉路口處的2條街道區(qū)間。

5.2 基于shifting策略的近似算法

本節(jié)首先介紹了近似算法采用的核心思想shifting策略，然后描述了所提出的多項式時間近似算法，并對算法的近似精度和時間復(fù)雜度進行了理論分析和證明。文獻[7]將shifting策略描述為一種統(tǒng)一的方法，用來解決大量的幾何覆蓋和裝箱問題，并且可能適用于超出這些范圍的問題。通過重復(fù)使用shifting策略，選擇一個最有利的解決方案，可以得到分治算法的誤差界。

圖3 shifting策略示例

算法3 基于shifting策略的多項式時間近似算法

輸入 目標區(qū)域，街道區(qū)間集合，RSU集合，局部算法

輸出 能夠覆蓋內(nèi)街道區(qū)間的RSU集合()

5) for,,do

7) end for

8) for,do

10) end for

11) fordo

13) end for

15) end

引理3是正整數(shù)，對于最優(yōu)覆蓋方案C，假設(shè)目標區(qū)域內(nèi)有交叉路口，則C中最多有個RSU覆蓋。

證畢。

證畢。

證畢。

本文的結(jié)果與標準的圓盤覆蓋問題有些不同，在圓盤覆蓋問題中，圓盤的位置并不是固定的。然而，在本文討論的區(qū)域覆蓋問題中，RSU的位置候選點均為隨機生成后輸入算法中的。

6 仿真結(jié)果與分析

在本節(jié)中，首先，介紹仿真環(huán)境；然后，描述了進行比較的算法以及用來評估算法的性能指標；最后，給出了仿真結(jié)果。

仿真考慮城市環(huán)境VANET中，有若干隨機分布的RSU放置候選點可供選擇。將本文提出的基于貪心策略的多項式時間近似算法GBP應(yīng)用于實際的城市環(huán)境，與其他RSU部署方案進行比較，通過仿真來評估算法的性能。

6.1 仿真設(shè)置

綜上所述，在該目標區(qū)域內(nèi)存在若干個可供選擇的RSU放置點，為了評估RSU候選點數(shù)目對算法性能的影響，在仿真中假設(shè)RSU候選點數(shù)目可以在一定范圍內(nèi)進行設(shè)置。RSU的通信范圍為200 m，RSU的放置點通常為交叉路口或沿著道路放置。

本節(jié)通過仿真對提出算法的有效性進行了驗證和討論，將所提出的基于貪心策略的多項式時間近似算法GBP與Yan等[16]提出的Tailor-方案以及Cheng等[18]提出的算法BCC（budgeted continuous coverage）進行比較，用來評估算法的性能。通過比較RSU候選點數(shù)目的變化對區(qū)域覆蓋率（RSU部署方案所覆蓋的區(qū)域與實際區(qū)域的比率）、計算時間以及近似比率（算法得到的RSU部署方案產(chǎn)生的區(qū)域覆蓋與最優(yōu)覆蓋方案產(chǎn)生的區(qū)域覆蓋的比率）等指標的影響，對算法性能進行評估。

6.2 仿真結(jié)果

本節(jié)將討論當RSU候選點數(shù)目變化時，GBP、Tailor-以及BCC算法對應(yīng)的區(qū)域覆蓋率、計算時間以及近似比率的變化情況。

6.2.1 區(qū)域覆蓋率

圖4和圖5分別顯示了城市1和城市2共2種城市環(huán)境下由算法GBP、Tailor-和BCC產(chǎn)生的區(qū)域覆蓋率。仿真結(jié)果反映了各算法的區(qū)域覆蓋率與目標區(qū)域內(nèi)可供選擇的RSU候選點數(shù)目的關(guān)系?？梢钥闯觯?種不同的城市環(huán)境下，GBP算法的區(qū)域覆蓋率優(yōu)于Tailor-方案和BCC算法各自產(chǎn)生的覆蓋率。隨著RSU的部署候選點增多，所有算法的覆蓋效果均有所提高，這是因為當候選點位置增多時，算法選擇用于區(qū)域覆蓋的RSU數(shù)目也隨之增加，從而覆蓋更大的區(qū)域范圍。另外，當城市環(huán)境下的道路拓撲結(jié)構(gòu)變復(fù)雜時，可能會導(dǎo)致相對較低的區(qū)域覆蓋率，特別是在該區(qū)域只有少數(shù)RSU的情況下。

圖4 覆蓋率和RSU候選點的關(guān)系（城市1）

圖5 覆蓋率和RSU候選點的關(guān)系（城市2）

因此，圖4中算法的覆蓋率低于圖5中相應(yīng)算法的覆蓋率。同樣可以看出，在常規(guī)的城市環(huán)境下，少量的RSU在很大概率上足以覆蓋大部分目標區(qū)域。因此，通過在重要位置部署相對較少的RSU，更容易對目標區(qū)域產(chǎn)生較大的覆蓋。

由GBP、Tailor-和BCC這3種算法在2種不同城市環(huán)境中RSU的部署結(jié)果可知，當分別設(shè)定為60和40時，GBP得到的區(qū)域部署方案對區(qū)域的覆蓋效果優(yōu)于Tailor-和BCC，從而反映了GBP算法對不同街道布局良好的適應(yīng)性和可擴展性。

6.2.2 計算時間

與Tailor-方案以及BCC算法相比，GBP主要根據(jù)區(qū)域街道的布局來求解RSU的部署方案，并不需要收集城市的交通信息和車輛的運動軌跡等信息，因此，GBP節(jié)省了計算交通信息以及車輛軌跡的時間。為了評估GBP、Tailor-以及BCC算法的計算復(fù)雜性，將城市1和城市2共2種環(huán)境下3種算法的計算時間分別表示為圖6和圖7。

圖6 計算時間和RSU候選點的關(guān)系（城市1）

圖7 計算時間和RSU候選點的關(guān)系（城市2）

仿真結(jié)果描述了各算法的計算時間與目標區(qū)域內(nèi)可供選擇的RSU數(shù)目的關(guān)系。當RSU候選點增加時，Tailor-和BCC計算時間增幅較大，而本文提出的GBP的計算時間增幅較小，并且Tailor-和BCC算法所消耗的時間均高于GBP算法。另外，比較圖6和圖7發(fā)現(xiàn)，由于城市1道路比城市2復(fù)雜，并且交叉路口較多，各算法在城市2中求解部署方案的計算時間明顯比城市1有所降低。在GBP中，當候選點數(shù)量為15時，城市1得到部署方案的計算時間大約為27 min，在相同條件下，城市2的計算時間也不超過20 min，而BCC在2個城市區(qū)域的求解時間分別為47 min和35 min，Tailor-算法的花費時間則高于GBP同時低于BCC。當候選點數(shù)目分別增加到60和40時，BCC方案的計算時間差距隨之變大，GBP和Tailor-的計算時間增幅較小。另外，如圖6和圖7所示，GBP計算時間變化不大，這是因為GBP計算時間主要與街道數(shù)目相關(guān)，同時也說明了GBP對不同的街道布局的適應(yīng)性優(yōu)于Tailor-和BCC算法。

6.2.3 近似比率

在2種城市環(huán)境下運行GBP、Tailor-和BCC這3種算法，得到各自的RSU部署方案。圖8和圖9分別描述了在城市1和城市2中RSU候選點數(shù)目變化的情況下得到部署方案的近似比率。由圖8和圖9可知，GBP和Tailor-算法的近似比率總是高于BCC算法，這是因為BCC算法產(chǎn)生的區(qū)域覆蓋率較低，導(dǎo)致其近似比率較低。隨著可供選擇的RSU部署點數(shù)量增加，3種算法的近似比率均有所增長，而GBP算法得到的近似比率則明顯高于Tailor-和BCC。值得注意的是，在圖8和圖9中，各算法得到的近似比率之間的差距越來越小，這是因為隨著RSU部署數(shù)量的增加，系統(tǒng)開銷也越來越大，因此，即使部署更多的RSU，算法帶來的邊際收益也不會得到顯著提升，這從一定程度上說明了選擇少量RSU進行合理的部署也會獲得良好的網(wǎng)絡(luò)性能。

圖8 近似比率和RSU候選點的關(guān)系（城市1）

圖9 近似比率和RSU候選點的關(guān)系（城市2）

7 結(jié)束語

針對城市中地形比較復(fù)雜的區(qū)域，由于街道信息難以收集導(dǎo)致在該類環(huán)境下GBP算法不能有效地解決區(qū)域覆蓋問題。針對該問題，結(jié)合VANET城市環(huán)境的特性，設(shè)計了能夠表現(xiàn)更多地理特征的Cue模型，然后，提出了基于shifting策略的多項式時間近似算法，并對算法進行理論分析得到了算法的近似比率。最后，仿真實現(xiàn)了本文提出的采用貪心策略的多項式時間算法GBP，與其他相關(guān)算法進行比較并提供了仿真結(jié)果。仿真結(jié)果表明了該算法的有效性，能夠在RSU候選點中合理部署RSU，給區(qū)域提供最大覆蓋，同時降低了RSU部署的開銷。

基于shifting策略的多項式時間近似算法中，使用了局部算法來求解分區(qū)的部署方案，未來擬研究比枚舉法更好的局部最優(yōu)算法或可求局部解的啟發(fā)式近似算法，結(jié)合shifting策略以產(chǎn)生更有效的全局近似算法。

[1] 常促宇, 向勇, 史美林. 車載自組網(wǎng)的現(xiàn)狀與發(fā)展[J]. 通信學(xué)報, 2007, 28(11): 116-126.

CHANG C Y, XIANG Y, SHI M L. Development and status of vehicular ad hoc networks[J]. Journal on Communications, 2007, 28(11): 116-126.

[2] 李麗君, 劉鴻飛, 楊祖元, 等. 車用自組網(wǎng)信息廣播[J]. 軟件學(xué)報, 2010, 21(7): 1620-1634.

LI L J, LIU H F, YANG Z Y, et al. Broadcasting methods in vehicular ad hoc networks[J]. Journal of Software, 2010, 21(7): 1620-1634.

[3] ENGLUND C, CHEN L, VINEL A, et al. Future applications of VANETs[M]// Vehicular Ad Hoc Networks. Switzerland: Springer, 2015: 524-544.

[4] XING M, HE J, CAI L. Utility maximization for multimedia data dissemination in large-scale VANETs[J]. IEEE Transactions on Mobile Computing, 2017, 16(4): 1188-1198.

[5] 陳立家, 江昊, 吳靜, 等. 車用自組織網(wǎng)絡(luò)傳輸控制研究[J]. 軟件學(xué)報, 2007, 18(6): 1477-1490.

CHEN L J, JIANG H, WU J, et al. Research on transmission control on vehicle ad-hoc network[J]. Journal of Software, 2007, 18(6): 1477-1490.

[6] 姜海濤, 張宏, 李千目. 車載時延容忍網(wǎng)絡(luò)路由協(xié)議研究[J]. 通信學(xué)報, 2013, 34(3): 76-84.

JIANG H T, ZHANG H, LI Q M. Research on routing protocol of vehicular delay-tolerant networks[J]. Journal on Communications, 2013, 34(3): 76-84.

[7] HOCHBAUM D S, MAASS W. Approximation schemes for covering and packing problems in image processing and VLSI[J]. Journal of ACM, 1985, 32(1): 130-136.

[8] LUO Z, GAN X, WANG X, et al. Optimal throughput-delay trade-off in manets with supportive infrastructure using random linear coding[J]. IEEE Transactions on Vehicular Technology, 2016, 65(9): 7543-7558.

[9] LU N, ZHANG N, CHENG N, et al. Vehicles meet infrastructure: towards capacity-cost tradeoffs for vehicular access networks[J]. IEEE Transaction on Intelligent Transportation System, 2013, 14(3): 1266-1277.

[10] HAJLAOUI R, GUYENNET H, MOULAHI T. A survey on heuristic-based routing methods in vehicular ad hoc network: technical challenges and future trends[J]. IEEE Sensors Journal, 2016, 16(17): 6782-6792.

[11] OMAR H, ZHUANG W, LI L. Gateway placement and packet routing for multihop in-vehicle Internet access[J]. IEEE Transactions on Emerging Topics in Computing, 2015, 3(3): 335-351.

[12] TRULLOLS O, FIORE M, CASETTI C, et al. Planning roadside infrastructure for information dissemination in intelligent transportation systems[J]. Computer Communications, 2010, 33(4): 432-442.

[13] CAVALCANTE E, AQUINO A, PAPPA G, et al. Roadside unit deployment for information dissemination in a VANET: an evolutionary approach[C]//The 14th Annual Conference Companion on Genetic and Evolutionary Computation. 2012: 27-34.

[14] LIN Y Y, RUBIN I. Throughput maximization under guaranteed dissemination coverage for VANET systems[C]//Information Theory and Applications Workshop. 2015:313-318.

[15] RIZK R, DAHER R, MAKKAWI A. RSUs placement using overlap based greedy method for urban and rural roads[C]//International Workshop on Communication Technologies for Vehicles. 2015: 12-18.

[16] YAN T, ZHANG W S, WANG G L, et al. Access points planning in urban area for data dissemination to drivers[J]. IEEE Transactions on Vehicular Technology, 2014, 63(1): 390-402.

[17] ZHU Y M, BAO Y C, LI B. On maximizing delay-constrained coverage of urban vehicular networks [J]. IEEE Journal on Selected Areas in Communications, 2012, 30 (4): 804-817.

[18] CHENG H, FEI X, ALMULLA M, et al. A knapsack constrained steiner tree model for continuous coverage over urban VANETs[C]//IEEE International Conference on Communications. 2014: 130-135.

[19] WANG Y, ZHENG J, MITTON N. Delivery delay analysis for roadside unit deployment in vehicular ad hoc networks with intermittent connectivity[J]. IEEE Transactions on Vehicular Technology, 2016, 65(10): 8591-8602.

[20] ZHANG B, JIA X, YANG K, et al. Design of analytical model and algorithm for optimal roadside AP placement in VANETs[J]. IEEE Transactions on Vehicular Technology, 2016, 65(9): 7708-7718.

[21] KIM D, VELASCO Y, WANG W, et al. A new comprehensive RSU installation strategy for cost-efficient VANET deployment[J]. IEEE Transactions on Vehicular Technology, 2017, 66(5): 4200-4211.

[22] LIU C, HUANG H, DU H. Optimal RSUs deployment with delay bound along highways in VANET[J]. Journal of Combinatorial Optimization, 2017, 33(4): 1168-1182.

[23] JALOOLI A, SONG M, XU X. Delay efficient disconnected RSU placement algorithm for VANET safety applications[C]//IEEE Wireless Communications and Networking Conference. 2017: 1558-2612.

[24] MUKHERJEE J C, GUPTA A, SREENIVAS R C. Event notification in VANET with capacitated roadside units[J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(7): 1867-1879.

[25] LI Y, JIN D, HUI P. Contact-aware data replication in roadside unit aided vehicular delay tolerant networks[J]. IEEE Transactions on Mobile Computing, 2016, 15(2): 306-321.

[26] LI P, ZHANG T, HUANG C, et al. RSU-assisted Geocast in vehicular ad hoc networks[J]. IEEE Wireless Communications, 2017, 24(1): 53-59.

[27] SUN Y P, LIN X D, LU R X, et al. Roadside units deployment for efficient short-time certificate updating in VANETs[C]//IEEE International Conference on Communications (ICC). 2010: 1-5.

[28] 奎曉燕, 杜華坤, 肖雪峰, 等. 基于真實車載移動數(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.

[29] 劉明, 曹建農(nóng), 鄭源, 等. 無線傳感器網(wǎng)絡(luò)多重覆蓋問題分析[J]. 軟件學(xué)報, 2007, 18(1): 127-136.

LIU M, CAO J N, ZHENG Y, et al. Analysis for multi-coverage problem in wireless sensor networks[J]. Journal of Software, 2007, 18(1): 127-136.

[30] 黃曉, 程宏兵, 楊庚. 無線傳感器網(wǎng)絡(luò)覆蓋連通性研究[J]. 通信學(xué)報, 2009, 30(2): 129-135.

HUANG X, CHENG H B, YANG G. Research of connectivity for wireless sensor networks[J]. Journal on Communications, 2009, 30(2): 129-135.

[31] 謝永, 吳黎兵, 何炎祥, 等. 無間隙的車聯(lián)網(wǎng)協(xié)助下載方法[J]. 通信學(xué)報, 2016, 37(1):180-190.

XIE Y, WU L B, HE Y X, et al. Non-intermittent cooperative downloading approach for VANET[J]. Journal on Communications, 2016, 37(1): 180-190.

[32] KARP R M. Reducibility among combinatorial problems[M]// New York: Springer, 1972: 85-103.

[33] HAKLAY M, WEBER P. OpenStreetMap: user-generated street maps[J]. IEEE Pervasive Computing, 2008, 7(4): 12-18.

[34] KRAJZEWICZ D. Traffic simulation with SUMO-simulation of urban mobility[M]//New York: Springer, 2010: 269-293.

RSU deployment planning based on approximation algorithm in urban VANET

ZHU Junyu1, HUANG Chuanhe1, FAN Xiying1, QIN Kuangyu1, FU Bin2

1. Computer School, Wuhan University, Wuhan 430072, China 2. The University of Texas Rio Grande Valley, Edinburg 78539, USA

To minimize the number of RSU deployed to cover a specific area, astreet model transforming the area covering problem to streets covering problem was designed, and a greedy-based polynomial (GBP) time approximation algorithm was developed to obtain the optimal RSU deployment for area coverage. For complex urban environments, a Cuemodel (complex urban environments model) was proposed. In this model, the target area was divided into different partitions. Then, based on shifting strategy, a polynomial time approximation scheme was designed. Theoretical analysis that include the approximation ratio and time complexity of the proposed algorithm were also presented. Simulation results show that GBP can efficiently solve the coverage problem in urban VANET.

VANET, RSU deployment, covering problem, approximation algorithm

TP393

A

10.11959/j.issn.1000-436x.2018008

朱鈞宇（1987-），男，河南周口人，武漢大學(xué)博士生，主要研究方向為物聯(lián)網(wǎng)、無線網(wǎng)絡(luò)、車載自組織網(wǎng)絡(luò)等。

黃傳河（1963-），男，湖北隨州人，武漢大學(xué)教授、博士生導(dǎo)師，主要研究方向為計算機網(wǎng)絡(luò)（移動互聯(lián)網(wǎng)、移動ad hoc網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)、未來互聯(lián)網(wǎng)）、物聯(lián)網(wǎng)、網(wǎng)絡(luò)安全、高性能計算等。

范茜瑩（1990-），女，河南駐馬店人，武漢大學(xué)博士生，主要研究方向為無線網(wǎng)絡(luò)、算法設(shè)計與分析、車載自組織網(wǎng)絡(luò)等。

覃匡宇（1974-），男，壯族，廣西馬山人，武漢大學(xué)博士生，主要研究方向為軟件定義網(wǎng)絡(luò)（SDN）、網(wǎng)絡(luò)管理。

付斌（1964-），男，美國得克薩斯州人，美國得克薩斯里奧格蘭德河谷大學(xué)終身教授，主要研究方向為算法設(shè)計與分析、生物信息、計算復(fù)雜性理論、無線網(wǎng)絡(luò)等。

2017-08-11；

2017-12-25

黃傳河，huangch@whu.edu.cn

國家自然科學(xué)基金資助項目（No.61772385, No.61373040, No.61572370）；美國國家科學(xué)基金會基金資助項目（No.0845376）

: The National Natural Science Foundation of China (No.61772385, No.61373040, No.61572370), The National Science Foundation Early Career Award of USA (No.0845376)