喻喜平,范文林

1.武漢鐵路職業(yè)技術(shù)學(xué)院,湖北 武漢430012

2.華中師范大學(xué)經(jīng)濟(jì)學(xué)院,湖北 武漢430079

車輛交通是現(xiàn)代城市的主要問題之一，應(yīng)用智能計算方法，可以高效解決交通安全、環(huán)境等相關(guān)問題。因此，智能城市[1]的概念逐漸成為現(xiàn)代城市建設(shè)的關(guān)鍵點(diǎn)。很多智能城市解決方案以智能交通系統(tǒng)[2]（ITS）為基礎(chǔ)。在整個解決方案中，車載自組織網(wǎng)絡(luò)[3]（VANET）支持車輛（配備車載單元（OBU））間的數(shù)據(jù)通信。車輛還可以通過“直接短距離通信”（DSRC）與“路邊單元”（RSU）通信[3,4]。其中，RSU 擁有一個網(wǎng)絡(luò)接口，通過DSRC 與其他VANET 節(jié)點(diǎn)進(jìn)行信息交換。由于RSU的作用最為重要。因此，在ITS 中，在道路沿線部署RSU 基礎(chǔ)設(shè)施至關(guān)重要，這將有助于緩解現(xiàn)代城市所面對的嚴(yán)重道路交通問題。

針對RSU 部署及相關(guān)問題，一些研究者提出了啟發(fā)式方法。文獻(xiàn)[5]研究了RSU 部署問題的一個變體，將交通網(wǎng)絡(luò)考慮為帶加權(quán)鏈路的圖。根據(jù)道路交通和移動性參數(shù)，例如道路交通密度和平均速度等，來計算鏈路的權(quán)值。然后應(yīng)用兩個不同方法來計算RSU 的所有可能解。文獻(xiàn)[6]提出一種基于連接時長的部署方案，在保障通信連接時長的前提下，最大化服務(wù)車輛數(shù)量，解決了部署最大覆蓋問題，可提供持續(xù)網(wǎng)絡(luò)服務(wù)。文獻(xiàn)[7]提出了基于流量的車載網(wǎng)絡(luò)路邊單元RSU 部署方案。在城市重要交通樞紐和交叉路口部署RSU，在北京和上海的實(shí)地評估表明，在輔助車輛與車輛進(jìn)行通信時，密集部署RSU 可以創(chuàng)造連續(xù)通信的機(jī)會，可以提高網(wǎng)絡(luò)性能。

VANET 部署RSU 基礎(chǔ)設(shè)施的難點(diǎn)在于：網(wǎng)絡(luò)設(shè)計者必須確定RSU 的數(shù)量、類型和位置，最大限度增加VANET 的服務(wù)質(zhì)量（QoS），同時實(shí)現(xiàn)部署成本最小化。以上方案盡支持某幾種屬性，因此，本文研究了RSU 部署問題的多目標(biāo)形式，即網(wǎng)絡(luò)QoS 最大化和部署成本最小化。其主要工作如下：1）在QoS 評價中，除了考慮每個RSU 類型的有效通訊范圍，還考慮了給定RSU 類型可以同時處理的最大車輛數(shù)；2）采用兩個啟發(fā)式方法（確定性和隨機(jī)性）求解該問題，降低了成本，在QoS 方面也有所提升。

1 用于RSU 的NSGA-II 方法

元啟發(fā)式是定義算法框架的策略，通過高效技術(shù)得到搜索、優(yōu)化和學(xué)習(xí)問題的近似解。本文應(yīng)用了多目標(biāo)進(jìn)化元啟發(fā)式方法來求解RSU-DP。其中，多目標(biāo)進(jìn)化算法（MOEA）[8]是特定的進(jìn)化優(yōu)化方法，針對多個相互沖突的目標(biāo)函數(shù)問題而設(shè)計。本文應(yīng)用了一種先進(jìn)的MOEA——NSGA-II（非支配排序遺傳算法，版本II）。NSGA-II 的進(jìn)化搜索，利用帶精英策略的非支配排序，降低了支配性檢查的復(fù)雜度，使用擁擠技術(shù)保留了多樣性，并在適應(yīng)度分配中考慮到擁擠距離數(shù)值。

1.1 函數(shù)定義

在城市場景中的RSU 集合R={R1,R2,…,Rq}，本文在VNAET 上使用應(yīng)用集合A={A1,A2,…,Au}。每個應(yīng)用均有其特定的QoS 要求，由函數(shù)Q:A→?+×?+給出。Q(Ah)為包含兩個元素的向量，表示應(yīng)用Ah的數(shù)據(jù)包投遞率（PDR）和端到端延遲的QoS 要求。在給定場景中，Q(Ah)用于定義每個RSU所能夠服務(wù)的最大用戶數(shù)量，其函數(shù)為MU:R×A→?+。

問題解的定義為放置在城市路段上的RSU 集合，表示sol={R1,R2,…,Rl}，其中l(wèi)為解sol（l≤n）中的RSU 數(shù)量（#RSU）。將每個RSU 安裝在路段Si內(nèi)的某個特定坐標(biāo)。函數(shù)cov:R?S表示一個RSU 所覆蓋的路段，而RSURj所覆蓋的路段Sk的一部分則由函數(shù)cp:R×S→[0,1]給出。RSU-DP 的多目標(biāo)形式要求得到一個位置集合以及在每個位置上部署的RSU 類型，從而能夠最大限度增加整個RSU 基礎(chǔ)設(shè)施提供的服務(wù)時間，并且實(shí)現(xiàn)部署總成本最小化。服務(wù)時間度量與提供給VANET 用戶的QoS 相關(guān)。該度量與RSU 覆蓋的車輛數(shù)、這些車輛接受服務(wù)的時長以及場景中的應(yīng)用類型相關(guān)。

形式上，將問題定義為兩個目標(biāo)函數(shù)的同時優(yōu)化：最大化QoS（式1）；最小化成本（式2）。

1.2 解的編碼

在提出的NSGA-II 中，解一般表示為實(shí)數(shù)的向量，長度為n=#S（即：路段集合S中的元素數(shù)量）。向量上的每個位置均包含將要安裝在相應(yīng)路段上的RSU 的相關(guān)信息：

1）RSU 類型由實(shí)數(shù)的整數(shù)部分給出（0 表示該路段中沒有RSU，整數(shù)1…k則分別表示類型kt1…tk）；

2）路段內(nèi)RSU 安裝的位置由實(shí)數(shù)的小數(shù)部分給出，將區(qū)間[0,1)映射到路段內(nèi)的點(diǎn)[pj,pi)。

1.3 進(jìn)化算子

提出的MOEA 應(yīng)用了進(jìn)化算子和一個并行模型，以高效求解RSU-DP 問題。

1.3.1 初始化 本文沒有從一組隨機(jī)解開始，而是利用啟發(fā)式計算出的解作為初始種群。由此在質(zhì)量較好的解的子空間上進(jìn)行進(jìn)化搜索。具體來說，本文采用了包含較高數(shù)量的RSU 的解，從而避免探索Pareto front 中QoS 數(shù)值過小的區(qū)域[9]，因?yàn)檫@部分解在現(xiàn)實(shí)場景中不具有實(shí)踐意義。

1.3.2 選擇 本文使用的選擇算子是原始NSGA-II 算法的選擇算子[10]，大小為兩個個體，適應(yīng)度最高的個體存活。

1.3.3 開發(fā)，重組 本文使用的重組算子為雙點(diǎn)交叉（2PX）算子，通過交換父代染色體中，落在兩個隨機(jī)選擇的切割點(diǎn)之間的基因來生成子代。

1.3.4 探索，變異 本文設(shè)計了一個ad-hoc 變異算子，為搜索提供足夠的多樣性，避免NSGA-II 陷入Pareto front 的某個特定區(qū)域。變異算子應(yīng)用三種變化：

1）概率為ΠA，變異算子將所選擇的基因的整數(shù)部分?jǐn)?shù)值變?yōu)?，將RSU 從相應(yīng)路段移除（如圖1（a）所示）。

2）概率為ΠB，變異算子將所選擇的基因的整數(shù)部分?jǐn)?shù)值變?yōu)閺腫1,k]區(qū)間內(nèi)隨機(jī)選擇的另一個不同的整數(shù)，由此將RSU 的類型（若不存在RSU，則添加一個RSU）變?yōu)橐粋€隨機(jī)類型（如圖1（b）所示）。

3）概率為1-ΠA-ΠB，向所選擇的基因數(shù)值應(yīng)用標(biāo)準(zhǔn)偏差為σ的高斯變異，由此改變路段內(nèi)RSU的位置（如圖1（c）所示）。

圖1 三種不同變異算子的變化圖Fig.1 Change graphs of three different variation operators

1.3.5 并行模型 本文應(yīng)用了啟發(fā)式的主從并行模型，以減少對種群中每個個體的目標(biāo)函數(shù)進(jìn)行評價的執(zhí)行時間。分解方法允許NSGA-II 高效計算種群中候選解集合的目標(biāo)函數(shù)。

2 實(shí)驗(yàn)與分析

2.1 開發(fā)平臺

提出的MOEA 使用ECJ 庫實(shí)施[11]，ECJ 包括易于修改的類用于使用NSGA-II 算法求解多目標(biāo)優(yōu)化問題。分析平臺使用AMD Opteron 6172 2.10 GHz 服務(wù)器，其中包括24 個核心和24 GB RAM。

由于個體適應(yīng)度的計算是高度CPU 密集型任務(wù)，因此使用24 個并行Java 線程進(jìn)行種群評價，每個線程評價種群的3 個個體。對于每個問題實(shí)例（地圖、交通和應(yīng)用），將提出的MOEA 分別執(zhí)行30 次。本文共執(zhí)行了1080 次NSGA-II 和279 次啟發(fā)式算法（包括參數(shù)設(shè)定和驗(yàn)證實(shí)驗(yàn)）。

2.2 問題實(shí)例

為了評價所提MOEA，本文定義了一個場景，納入了眾多元素信息，包括上海市的地圖，道路交通數(shù)據(jù)，RSU 網(wǎng)絡(luò)接口/天線，以及在VANET 上執(zhí)行的真實(shí)應(yīng)用。有效無線電范圍（ERR）是定義RSU 的主要特征之一。ERR 表示RSU 與車輛交換數(shù)據(jù)包的最遠(yuǎn)距離，該度量關(guān)系到VANET 基礎(chǔ)設(shè)施的通信性能評價。圖2 給出了模擬實(shí)驗(yàn)結(jié)果中每類RSU 的ERR。根據(jù)定義的PDR 閾值，RSU類型1、2、3 的ERR 分別為243.12 m、338.70 m 和503.93 m。

圖2 本文ERR 的實(shí)驗(yàn)結(jié)果Fig.2 The experimental results of ERR in this paper

2.3 數(shù)值結(jié)果分析

本文使用RHV 度量進(jìn)行結(jié)果比較，RHV 指標(biāo)能夠較好表明向理想Pareto front 的收斂性以及非支配解集合中的多樣性。為了比較每種方法得到相對超容量（Relative Hyper Volume,RHV）值，本文使用了兩個統(tǒng)計測試。首先執(zhí)行Shapiro-Wilk 測試，以評估每個方法在每個問題實(shí)例上得到的RVH值的正態(tài)性。使用Friedman 秩檢驗(yàn)評估結(jié)果之間的優(yōu)劣。

表1 給出了3 種不同方法在9 個問題實(shí)例上得到的RHV 數(shù)值。表中S-W 表示Shapiro-Wilk 測試得到的p-value，Rank 表示Friedman 檢驗(yàn)得到的rank。

如表1 所示，本文NSGA-II 的RHV 數(shù)值顯著優(yōu)于其他兩個方法。Friedman 秩檢驗(yàn)表明本文NSGA-II 在所有問題實(shí)例上均優(yōu)于（具有統(tǒng)計置信度）文獻(xiàn)[5,6]（所有比較中p-value＜10-6）。這表明本文NSGA-II 準(zhǔn)確計算出向著理想Pareto front 收斂的fronts，同時保持了非支配解集合的多樣性。

表2 給出了與其他兩種方法相比，本文NSGA-II 實(shí)現(xiàn)的提升之處。其中每個方法分別使用固定成本計算QoS 值，和使用固定QoS 值計算成本。同時，比較各自方法計算出的結(jié)果，以評估提出的方法在每個問題目標(biāo)的性能改善。

提出的方法以多目標(biāo)方法求解問題，因此最終的實(shí)施方案由決策制定者來決定，從非支配解集合中選擇出最適合的實(shí)施方案。表2 結(jié)果證明本文NSGA-II 在所有場景中均優(yōu)于其他兩種方法。這主要得益于本文方法在QoS 評價中，除了考慮每個RSU 類型的有效通訊范圍，還考慮了給定RSU類型可以同時處理的最大車輛數(shù)，在求解問題過程中，降低了成本，提升了QoS。

表1 不同方法實(shí)現(xiàn)的相對超容量比較Table 1 Comparisons of relative overcapacity realized by different methods

3 結(jié)論與展望

本文研究了一個多目標(biāo)進(jìn)化方法的應(yīng)用，以求解車載網(wǎng)絡(luò)的路邊基礎(chǔ)設(shè)施的位置安置問題。提出了該問題的多目標(biāo)表達(dá)式，其中考慮到QoS 和成本目標(biāo)。納入問題相關(guān)的編碼和ad-hoc 變異算子，探索可能位置集合，設(shè)計了特定的NSGA-II 進(jìn)化算法。通過Pareto foronts 結(jié)果比較，本文NSGA-II方法給出了更好的解，特別是對于數(shù)據(jù)應(yīng)用場景。實(shí)驗(yàn)分析還表明，當(dāng)考慮更具實(shí)踐性的場景時，進(jìn)化方法能夠?qū)崿F(xiàn)更大的性能提升。未來，本文計劃在問題表達(dá)式中加入車載網(wǎng)絡(luò)中重要事件信息（例如事故、交通擁堵等），以建立更具實(shí)踐性的場景模型。