基于軟件定義網絡和移動邊緣計算的車聯網高效任務卸載方案

摘 要：隨著車聯網（IoV）中車輛和智能應用數目的增加使計算密集型任務激增，傳統架構難以滿足用戶需求。為解決車聯網計算資源不足且分配不均勻、應用時延需求無法滿足、任務能耗成本較高的問題，結合移動邊緣計算（MEC）和軟件定義網絡（SDN），設計了一種從宏基站到MEC服務器到車輛的車聯網架構中的高效任務卸載方案，并提出一種改進的低復雜度非支配排序遺傳算法，優化任務卸載成本和MEC服務器的負載均衡率。實驗仿真結果表明，相比于隨機卸載，NO-MEC卸載，NO-I卸載，傳統NSGA、NSGA-Ⅱ卸載，GA卸載，Q-learning卸載，DQN卸載方案，所提方案有著更低的卸載成本，更優的負載均衡率，得到近似最高的系統效用，能夠給車聯網中的車輛用戶帶來更優質的網絡服務。

關鍵詞：車聯網；移動邊緣計算；軟件定義網絡；任務卸載；非支配排序遺傳算法

中圖分類號：TP393 文獻標志碼：A

文章編號：1001-3695（2023）06-035-1817-08

doi：10.19734/j.issn.1001-3695.2022.10.0630

Efficient task offloading scheme of Internet of Vehicles based on software defined network and mobile edge computing

Wei Rui Zhu Changhong Wang Yi Huang Yeheng Tang Yuxing Xiong Zekai Qin Tuanfa

（a.School of Computer amp; Electronics Information，b.Guangxi Key Laboratory of Multimedia Communications amp; Network Technology，Guangxi University，Nanning 530004，China）

Abstract：With the increase in the number of vehicles and intelligent applications in the IoV，computing intensive tasks have proliferated，and the traditional architecture is difficult to meet user needs. To solve the problems of insufficient and uneven allocation of computing resources in the IoV，insatiable application delay requirements，and high task energy consumption costs，this paper combined MEC and SDN to design an efficient task offloading scheme in the network of vehicles architecture from macro station to MEC server to vehicle，and proposed an improved low-complexity non-dominated sorting genetic algorithm to optimize the task offloading cost and the load balancing rate of MEC server. The experimental simulation results show that the proposed scheme compared with random offloading，NO-MEC offloading，NO-I offloading，traditional NSGA，NSGA-Ⅱ offloa-ding，GA offloading，Q-learning offloading，DQN offloading，has lower offloading cost，better load balancing rate，and approximately the highest system utility，which brings better network services to vehicle users in the IoV.

Key words：Internet of Vehicles（IoV）；mobile edge computing（MEC）；software defined network（SDN）；task offloading；non-dominated sorting genetic algorithm（NSGA-Ⅱ）

0 引言

隨著5G時代到來，車聯網（IoV）成為改善城市交通的關鍵技術。通信、控制以及嵌入式技術的發展，讓車輛內置強大的傳感器，即車載單元（on board unit，OBU）。OBU從人、智能移動設備、車輛、路邊單元（road side unit，RSU）以及云中心［1］獲取信息。類似物聯網，IoV具備通信、存儲、學習能力等功能，但車輛數目的激增帶來海量高資源、低時延需求性任務以及車輛應用（自動駕駛、路徑規劃等），意味著資源消耗型任務與IoV節點資源（處理、存儲）的矛盾尤為突出，傳統的車聯網模型難以繼續使用［1～3］。5G中軟件定義網絡（software defined network，SDN）技術、網絡功能虛擬化（network functions virtuali-zation，NFV）技術以及移動邊緣計算（mobile edge computing，MEC）技術給這一問題帶來轉機［4～8］，文獻［9］提出了基于SDN、NFV技術條件下的高速移動車輛與MEC服務器連接的支持以及高速移動車輛間的連接支持，任務卸載中的車輛互聯（vehicle to vehicle，V2V）和車路互聯（vehicle to infrastructure，V2I）問題得到理論支撐，圖1展示了車聯網與SDN技術結合組成軟件定義車聯網（software defined vehicular network，SDVN），NFV將車聯網模塊分層為交通層和數據層，SDN控制器將車聯網中的車輛任務卸載信息提取并分配計算資源以及網絡接口，適配MEC的強大算力，足以滿足車輛數字軟件應用的毫秒級時延任務的需要。

任務卸載方面的MEC研究，文獻［10，11］都利用了粒子群優化算法，文獻［11］在文獻［10］的基礎上引入模擬退火算法的壓縮因子，優化車聯網任務卸載的時延和能耗，但僅僅考慮了V2V交互效率較低，車載單元本身算力不強。文獻［12］利用遺傳算法來權衡MEC中任務卸載的任務時延、MEC服務器的負載，將問題轉換為一個雙目標優化。這些研究建模了車輛任務卸載至MEC服務器、V2V卸載，但車輛用戶出現在沒有MEC服務器覆蓋、車輛較少的區域將無法得到計算服務，同時對于任務卸載指標的考慮沒有兼顧卸載成本（時延、能耗）以及服務器負載。本研究模型為車輛用戶提供本地卸載、MEC服務器卸載、宏基站服務器卸載、V2V卸載，充分利用車聯網計算資源優化卸載成本以及服務器負載均衡率。

文獻［13］將卸載任務分類成了全部卸載和部分卸載，二進制卸載（全部卸載）采用改進的置信上界算法，部分卸載任務采用Q-learning尋優，卸載策略優化了時延以及能耗；文獻［14］中計算資源不足的車輛將任務全部卸載到MEC服務器，車輛卸載能耗最小，部分卸載采用凸優化方法得到最優卸載數據量和傳輸功率。其共同點是將任務進行分割處理，卸載方案與本文算法相比復雜度更高，卸載成本（時延、能耗、吞吐量）、負載均衡率和資源利用率等抽象問題沒有具象出來進行多目標優化，因此本文提出多目標優化算法權衡卸載成本以及負載均衡率是有意義的。

文獻［15］提出一種三層架構的車聯網模型，提出一種低復雜度的基于最大值密度的啟發式資源分配算法；文獻［16］同樣建立三層車聯網架構模型，利用K近鄰算法將用戶進行分類，再用強化學習手段解決資源分配的問題，優化任務卸載時延。這些研究拓寬了車聯網的架構，多層架構的車聯網網絡能夠更好地利用車聯網中的計算資源。

在上述研究啟發之下，本文考慮一種邊緣計算背景下軟件定義車聯網的任務卸載模型，構建一種基于SDN的宏基站—邊緣服務器基站—車輛架構。本文的主要貢獻有：

a）建立基于SDN和移動邊緣計算的宏基站—邊緣服務器—車輛的車聯網場景，利用SDN技術、NFV技術完成場景中任務卸載信息、卸載命令的統一管理，充分地利用車聯網中的計算資源以節約任務卸載成本（時延、能耗），優化MEC基站的負載均衡率；

b）將任務卸載問題建模成多目標優化問題（multi-objective optimization problem，MOP），提出一種改進帶有精英保留策略的快速非支配排序遺傳算法（NSGA-Ⅱ）的低復雜度算法，權衡任務卸載成本（時延、能耗）以及MEC服務器的負載均衡，通過簡單加權法（simple additive weighting，SAW）、多屬性決策（multi criteria decision making，MCDM）選擇本地卸載、MEC卸載、宏基站卸載以及V2V卸載中近似最優的任務卸載方案；

c）仿真實驗證明了改進的NNSGA算法相比優先選擇宏基站卸載方案（NO-MEC）、優先選擇MEC服務器卸載方案（NO-I）、隨機卸載算法（random offload，RO）、貪婪算法卸載（greedy algorithm，GA）、傳統NSGA、NSGA-Ⅱ卸載算法、Q-learning卸載算法、DQN-base algorithm，DQN卸載算法具有更低的卸載成本，更為優秀的MEC服務器負載均衡率和更高的系統效用。

1 系統模型和目標優化

1.1 系統模型

1.2 通信模型

1.3 負載均衡計算模型

1.4 卸載成本計算模型

1.4.1 本地卸載計算模型

1.4.2 卸載至MEC計算模型

1.4.3 卸載至宏基站計算模型

1.4.4 V2V卸載計算模型

1.5 優化目標

1.5.1 卸載成本

1.5.2 建立優化目標

2 改進遺傳算法的目標優化

在第一代遺傳算法的基礎上，Deb等人［19］提出了NSGA-Ⅱ算法，相較于NSGA算法，精英保留策略改進了每一代進化都要構造的非支配集問題，將復雜度從O（MN3）降低為O（MN2），同時相比于目前流行的機器學習類算法也有著復雜度低、收斂快的優勢。另外相較于NSGA-Ⅲ，NSGA-Ⅱ編寫更為規范，開發過程中架構清晰、操作簡單，本文中二維的優化問題，NSGA-Ⅱ更容易尋找到種群中的優秀解，同樣體現了收斂速度的優越性。

NSGA-Ⅱ算法正廣泛用于解決在線問題［20，21］，且MEC系統的網絡規模本就小于傳統網絡，減少了問題的解決空間。本文將時延與能耗結合成卸載成本并聯合優化負載均衡，輔以改進的系統效用選擇方案使得用戶在不同的情況下可以靈活切換卸載成本權重以及卸載成本與負載均衡之間的偏好，并根據需求獲得最優秀的卸載方案，因此任務卸載問題適合利用NSGA-Ⅱ算法解決。

2.1 改進的快速精英非支配排序遺傳算法

2.2 改進的NNSGA解的評價與選擇

算法1用于評價、選擇解集中的最優，依據MCDM中歸一化的思想，評價解集中成本以及負載均衡率的值，再利用SAW將成本與負載均衡率進行加權求和得出該解的系統效用，選擇最為優越的卸載方案。兩種選擇思想在處理大量的迭代數據結果中具有十分明顯的優勢，相比于傳統NSGA-Ⅱ算法將會更快找到解的支配關系進而收斂，優化NNSGA所產生的解，從而幫助SDN處理器調度最優卸載策略，一定程度上解決了NSGA-Ⅱ存在的解集難以互相支配、無法尋出最優解集的問題。

3 仿真實驗與分析

3.1 仿真環境設置

3.2 系統仿真分析

3.3 系統實驗對比分析

1）時延對比分析

圖10展示了NNSGA的時延成本與其他卸載算法的仿真對比，本文NNSGA總的來說在時延方面沒有占據很大的優勢，與自身模塊相比，NO-I在車輛數目少（20、40臺）時有著最優的表現，因為算力最強的MEC服務器作為優選，且車輛數目小的時候MEC的服務閾值并未超出，隨著車輛數目的增加，NNSGA恒優于NO-I以及NO-MEC。與其他卸載方案相比，由于豐富了選擇的機制，車輛數目少時NNSGA在時延上并不占據優勢，但隨著車輛數目的增加可以看出NNSGA改善了傳統遺傳算法解集帕累托等級難以互相支配的問題，時延表現優于NSGA、NSGA-Ⅱ同時略微優于DQN算法，有著最優的時延表現，證明了本文算法是有意義的，在車輛數目較低且偏好時延指標的情況下用戶可以選擇NO-I方案。

2）能耗對比分析

圖11展示了所有方案關于能耗成本指標的仿真結果。隨著車輛數目的不斷增加，系統的能耗指數也在不斷升高，但NNSGA卸載方案的能耗成本恒優于其他方案。相比于自身模塊方案NO-I，由于車輛數目的增加MEC處理能力很快達到閾值，車輛所選卸載方式會更為耗能。而NO-MEC方案使得車輛用戶需要耗費更大的傳輸能耗成本交互宏基站，同時在宏基站計算能力到達極限時也需要選擇更為耗能的卸載方案，能耗表現不佳。相比于傳統遺傳算法，NNSGA有著較為顯著的提升，同時也略優于DQN算法，說明NNSGA與其他卸載算法相比更充分地利用了本文提出的基于SDN的宏基站—MEC—車輛模型中的計算資源，對于能耗的優化是有效的。

3）負載均衡對比分析

從圖12可以看出，基于NNSGA的卸載方案負載均衡率與其他方案相比表現更好。NNSGA綜合考量了在車聯網中車輛與節點的距離，卸載任務量所造成的時延、能耗，以及服務節點負載情況后選擇最優的卸載策略，減少了計算資源分配不平衡，改善了系統模型中MEC節點負載過高導致出現資源過載的問題，盡可能避免了服務效果最好的MEC服務器無法參與任務卸載的情況。隨著車輛數目的增加、任務到達率的增加，NNSGA的負載均衡率隨之增高，說明在車輛數目較多或任務較多時負載均衡會更加難以實現。

4）系統效用對比分析

圖13展示了不同卸載方案的系統效用。在服務車輛用戶數量為20、40、60、100時NNSGA卸載方案有較高的系統效用，表明了系統高效地權衡了卸載成本和負載均衡率，而在80臺車輛時不是系統效用表現最好的卸載方案，因此可以根據實際情況更換此時用戶所選擇的卸載方案，例如服務車輛為80臺左右時采取NO-I卸載方案，在車輛數目為20、40、60、100左右時，選擇NNSGA卸載方案，可以帶來最好的移動服務。也可以看到車輛數目為80臺左右時，Q-learning以及DQN卸載方案有更高的系統效益，相比于遺傳算法此時波動不明顯。

4 結束語

本文設計了基于SDN和MEC的宏基站—MEC服務器—車輛車聯網架構，建模成任務卸載方案數學模型，利用提出的低復雜度算法NNSGA權衡卸載成本（時延、能耗）以及負載均衡率，相比于對比算法具有明顯優勢，改善了車聯網架構下車輛任務卸載中服務器負載不均衡的問題，降低了車輛用戶在任務卸載中帶來的能量消耗，盡可能保證任務時延處于較低水平。但是遺傳算法對于車聯網模型中車輛動態卸載和服務節點的動態遷移問題仍難以得到對策，將來需要進一步探討車輛在高速移動時MEC節點的動態遷移問題，以及此時MEC節點的任務卸載服務是否仍能提供穩定的計算服務和可靠的信息安全支持。

參考文獻：

［1］Almilurjman F，Zahmatkesh H，Shahroze R.An overview of security and privacy in smart cities’ IoT communications[J].Trans on Emerging Telecommunications Technologies，2022，33（3）：e3677.

[2]Lin Kai，Li Sichen，Li Yihui，et al.Distributed learning for vehicle routing decision in software defined Internet of Vehicles[J].IEEE Trans on Intelligent Transportation Systems，2020，22（6）：3730-3741.

[3]Peng Kai，Huang Hualong，Liu Peichen，et al.Joint optimization of energy conservation and privacy preservation for intelligent task offloa-ding in MEC-enabled smart cities [J].IEEE Trans on Green Communications and Networking，2022，6（3）：1671-1682.

[4]Mach P，Becvar Z.Mobile edge computing：a survey on architecture and computation offloading [J].IEEE Communications Surveys amp; Tutorials，2017，19（3）：1628-1656.

[5]Liu Hang，Eldarrat F，Alqahtani H，et al.Mobile edge cloud system：architectures，challenges，and approaches[J].IEEE Systems Journal，2018，12（3）：2495-2508.

[6]Zhang Jie，Guo Hongzhi，Liu Jiajia，et al.Task offloading in vehicular edge computing networks：a load-balancing solution [J].IEEE Trans on Vehicular Technology，2020，69（2）：2092-2104.

[7]胡恒，金鳳林，郎思琪.移動邊緣計算環境中的計算卸載技術研究綜述 [J].計算機工程與應用，2021，57（14）：60-74.（Hu Heng，Jin Fenglin，Lang Siqi.Survey of research on computation offloading technology in mobile edge computing environment [J].Computer Engineering and Applications，2021，57（14）：60-74.）

[8]Gerla M，Lee E K，Pau G，et al.Internet of Vehicles：from intelligent grid to autonomous cars and vehicular clouds [C]//Proc of World Forum on Internet of Things.Washington DC：IEEE Computer Society，2014：241-246.

[9]Kim Y，An N，Park J，et al.Mobility support for vehicular cloud radio-access-networks with edge computing [C]//Proc of the 7th International Conference on Cloud Networking.Piscataway，NJ：IEEE Press，2018：1-4.

[10]Keshari N，Gupta S T，Singh D.Particle swarm optimization based task offloading in vehicular edge computing [C]//Proc of the 18th IEEE India Council International Conference.Piscataway，NJ：IEEE Press，2021：1-8.

[11]繆裕青，徐伊，張萬楨，等.車聯網中改進粒子群算法的任務卸載策略 [J].計算機應用研究，2021，38（7）：2050-2055.（Miu Yuqing，Xu Yi，Zhang Wanzhen，et al.Improved particle swarm algorithm for task offloading in vehicular networks[J].Application Research of Computers，2021，38（7）：2050-2055.）

[12]Xu Xiaolong，Xue Yuan，Li Xiang，et al.A computation offloading method for edge computing with vehicle-to-everything [J].IEEE Access，2019，7：131068-131077.

[13]Liu Jun，Wang Shoubin，Liu Chang，et al.A task oriented computation offloading algorithm for intelligent vehicle network with mobile edge computing[J].IEEE Access，2019，7：180491-180502.

[14]Ren Chunli，Zhang Guo’an，Gu Xiaohui，et al.Computing offloading in vehicular edge computing networks：full or partial offloading？ [C]//Proc of the 6th Information Technology and Mechatronics Engineering Conference.Piscataway，NJ：IEEE Press，2022：693-698.

[15]Li Xin，Dang Yifan，Aazam M，et al.Energy-efficient computation offloading in vehicular edge cloud computing [J].IEEE Access，2020，8：37632-37644.

[16]Cui Yaping，Liang Yingjie，Wang Ruyan.Intelligent task offloading algorithm for mobile edge computing in vehicular networks [C]//Proc of the 91st Vehicular Technology Conference.Piscataway，NJ：IEEE Press，2020：1-5.

[17]Chen Min，Hao Yixue.Task offloading for mobile edge computing in software defined ultra-dense network[J].IEEE Journal on Selected Areas in Communications，2018，36（3）：587-597.

[18]Jain R，Paul S.Network virtualization and software defined networking for cloud computing：a survey[J].IEEE Communications Magazine，2013，51（11）：24-31.

[19]Deb K，Pratap A，Agarwal S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ[J].IEEE Trans on Evolutionary Computation，2002，6（2）：182-197.

[20]Niu Xiaoxiao，Wang Hechun，Hu Song，et al.Multi-objective online optimization of a marine diesel engine using NSGA-Ⅱ coupled with enhancing trained support vector machine[J].Applied Thermal Engineering，2018，137（6）：218-227.

[21]Miriyala S S，Subramanian V R，Mitra K.Transform-ANN for online optimization of complex industrial processes：casting process as case study[J].European Journal of Operational Research，2018，264（1）：294-309.

[22]Mnih V，Kacukcuolu K，Silver D，et al.Human-level control through deep reinforcement learning[J].Nature，2015，518（7540）：529-533.

[23]Xu Xiaolong，Shen Bowen，Ding Sheng，et al.Service offloading with deep Q-network for digital twinning-empowered Internet of Vehicles in edge computing[J].IEEE Trans on Industrial Informatics，2020，18（2）：1414-1423.