基于多場景和多目標的車載網絡通信NSGA-II 方法

喻喜平,范文林

1.武漢鐵路職業技術學院,湖北 武漢430012

2.華中師范大學經濟學院,湖北 武漢430079

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

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

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

1 用于RSU 的NSGA-II 方法

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

1.1 函數定義

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

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

形式上，將問題定義為兩個目標函數的同時優化：最大化QoS（式1）；最小化成本（式2）。

1.2 解的編碼

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

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

2）路段內RSU 安裝的位置由實數的小數部分給出，將區間[0,1)映射到路段內的點[pj,pi)。

1.3 進化算子

提出的MOEA 應用了進化算子和一個并行模型，以高效求解RSU-DP 問題。

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

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

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

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

1）概率為ΠA，變異算子將所選擇的基因的整數部分數值變為0，將RSU 從相應路段移除（如圖1（a）所示）。

2）概率為ΠB，變異算子將所選擇的基因的整數部分數值變為從[1,k]區間內隨機選擇的另一個不同的整數，由此將RSU 的類型（若不存在RSU，則添加一個RSU）變為一個隨機類型（如圖1（b）所示）。

3）概率為1-ΠA-ΠB，向所選擇的基因數值應用標準偏差為σ的高斯變異，由此改變路段內RSU的位置（如圖1（c）所示）。

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

1.3.5 并行模型 本文應用了啟發式的主從并行模型，以減少對種群中每個個體的目標函數進行評價的執行時間。分解方法允許NSGA-II 高效計算種群中候選解集合的目標函數。

2 實驗與分析

2.1 開發平臺

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

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

2.2 問題實例

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

圖2 本文ERR 的實驗結果Fig.2 The experimental results of ERR in this paper

2.3 數值結果分析

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

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

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

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

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

表1 不同方法實現的相對超容量比較Table 1 Comparisons of relative overcapacity realized by different methods

3 結論與展望

本文研究了一個多目標進化方法的應用，以求解車載網絡的路邊基礎設施的位置安置問題。提出了該問題的多目標表達式，其中考慮到QoS 和成本目標。納入問題相關的編碼和ad-hoc 變異算子，探索可能位置集合，設計了特定的NSGA-II 進化算法。通過Pareto foronts 結果比較，本文NSGA-II方法給出了更好的解，特別是對于數據應用場景。實驗分析還表明，當考慮更具實踐性的場景時，進化方法能夠實現更大的性能提升。未來，本文計劃在問題表達式中加入車載網絡中重要事件信息（例如事故、交通擁堵等），以建立更具實踐性的場景模型。