基于霧計算的路網(wǎng)- 野區(qū)路徑規(guī)劃研究

王 礫，岳東峰，劉嚴巖，畢竹清

（北方信息控制研究院集團有限公司，南京 211153）

0 引言

隨著智能設(shè)備的普及、可穿戴計算設(shè)備的發(fā)展，網(wǎng)絡(luò)發(fā)展呈現(xiàn)出兩種明顯的趨勢：基于云計算的架構(gòu)普及以及持續(xù)激增的移動智能設(shè)備。智能設(shè)備的小型化、輕量化與高性能之間存在一定的矛盾，為了解決這類矛盾，云計算框架的快速發(fā)展，已經(jīng)成為現(xiàn)在互聯(lián)網(wǎng)的關(guān)鍵基礎(chǔ)設(shè)施之一。并且隨著智能手表、智能眼鏡的逐步普及，移動智能設(shè)備的需求會進一步激增，對云計算的負載能力、實時響應(yīng)能力和安全保密能力提出了更高的要求［1-2］。為了應(yīng)對該類挑戰(zhàn)，霧計算技術(shù)近些年發(fā)展較為迅猛，霧計算是分布式部署于網(wǎng)絡(luò)邊緣的小型云計算系統(tǒng)，能夠?qū)壿嬌相徑囊苿釉O(shè)備提供有效的云服務(wù)，同時降低了大型云端的負載壓力，霧計算結(jié)合了移動互聯(lián)網(wǎng)與云計算技術(shù)，同時具有網(wǎng)絡(luò)拓撲的彈性縮放能力與云平臺的分布計算能力。能夠根據(jù)用戶需求的變化，實時調(diào)整網(wǎng)絡(luò)節(jié)點的接入策略，通過虛擬化技術(shù)，整合不同硬件平臺的計算、存儲等資源，合理分配網(wǎng)絡(luò)資源。

路徑規(guī)劃技術(shù)是目前日常生活中較為普及的技術(shù)之一，除了能夠提供快速、實時的路徑規(guī)劃功能以外，現(xiàn)有移動端應(yīng)用程序已經(jīng)能夠提供較為全面的地理信息服務(wù)，包括周圍商業(yè)設(shè)施的搜索、擁堵區(qū)域提示等信息?，F(xiàn)有路徑規(guī)劃技術(shù)的核心分為兩部分：第1 部分是對地圖的處理，將矢量地圖進行預(yù)處理，形成可用于路徑規(guī)劃拓撲圖；第2 部分是路徑尋優(yōu)算法，根據(jù)起始點、關(guān)鍵點、終止點的信息，規(guī)劃出合理的路線。根據(jù)獲取的地圖信息范圍，可以將路徑規(guī)劃方法分為：基于先驗全地圖信息的全局路徑規(guī)劃，以及基于實時地圖信息的局部路徑規(guī)劃。局部路徑規(guī)劃算法有人工勢場法、遺傳類算法等。全局路徑規(guī)劃常見的路徑尋優(yōu)算法有：適用于柵格路徑尋優(yōu)的Dijkstra 算法［3-4］、A*算法［5-6］與適用于可視圖的Voronoi 圖法［7］等。

本文提出了基于霧計算框架的野區(qū)路徑規(guī)劃服務(wù)設(shè)計方法。在霧計算平臺提供的計算、存儲等資源的基礎(chǔ)上，綜合考慮野區(qū)的地質(zhì)信息、水域信息、建筑群信息、道路信息以及高程信息等，結(jié)合霧計算平臺收集的實時信息，包括橋梁被毀、道路堵塞等，并以柵格類算法中的A*算法作為野區(qū)環(huán)境下的路徑尋優(yōu)方法，構(gòu)建適用于野區(qū)的路徑規(guī)劃服務(wù)，提出實時的道路-野地無縫連接的路徑規(guī)劃方法。

1 云計算與霧計算介紹

1.1 云計算介紹

軍用增強現(xiàn)實電子沙盤以高精度三維地形數(shù)據(jù)為基礎(chǔ)。現(xiàn)在較為廣泛接受的云計算定義是美國國家標準與技術(shù)研究院（NIST）提出的，定位為：云計算是一種按使用量付費的模式，這種模式提供可用、便捷、按需的網(wǎng)絡(luò)訪問，提供可配置的計算資源共享池（資源包括網(wǎng)絡(luò)、服務(wù)器、存儲設(shè)備、應(yīng)用軟件、服務(wù)等），這些資源能夠被快速提供、只需要很少的管理工作，或與服務(wù)供應(yīng)商進行很少的交互［8］。

云計算的定義中，強調(diào)了云計算是根據(jù)用戶的需求提供計算服務(wù)，能夠聚合網(wǎng)絡(luò)帶寬、數(shù)據(jù)儲存、應(yīng)用服務(wù)等資源，對外提供整合后的虛擬化資源池，并且該資源池能夠根據(jù)應(yīng)用場景的需求進行配置，即提供資源的彈性擴展能力。同時采用統(tǒng)一的網(wǎng)絡(luò)訪問方式，提供標準的、與平臺無關(guān)的服務(wù)訪問接口，屏蔽了“云”內(nèi)部結(jié)構(gòu)的差異。

1.2 霧計算介紹

霧計算是云計算的延伸概念，能夠?qū)⒃品?wù)擴展至網(wǎng)絡(luò)邊緣。霧計算是地理上分布式計算架構(gòu)，由大量泛在的、相互連接的、異構(gòu)的設(shè)備共同組成資源池。霧計算與云計算可以相互協(xié)作，但不依賴云計算，為用戶群提供彈性的計算、存儲、通信與服務(wù)等資源［9-10］。

霧計算的特點［11］包括：1）霧計算與網(wǎng)絡(luò)邊緣的用戶組距離較近，從而在網(wǎng)絡(luò)邊緣提供對時延敏感的服務(wù)；2）霧計算提供區(qū)域感知能力，在地理上分布的各個霧節(jié)點（網(wǎng)絡(luò)邊緣的服務(wù)器）能夠推斷出自身的位置，并跟蹤用戶組的運動狀態(tài)，從而提供更加切合當前環(huán)境的計算服務(wù)；3）在大數(shù)據(jù)的時代，霧計算可以支持邊緣分析與流數(shù)據(jù)挖掘，在數(shù)據(jù)收集的早期階段對數(shù)據(jù)進行降維，從而降低數(shù)據(jù)延遲與節(jié)省帶寬消耗。

1.3 云計算與霧計算的關(guān)系

霧計算與云計算是相輔相成的關(guān)系，霧計算是云計算在網(wǎng)絡(luò)邊緣的延伸，更加貼近各類移動終端，霧計算與云計算的關(guān)系如圖1 所示。

圖1 霧計算與云計算的關(guān)系圖

通過云計算，聚合各類服務(wù)器群的計算能力、存儲能力以及相應(yīng)的網(wǎng)絡(luò)資源，并將各類資源虛擬化后形成資源池，對各類服務(wù)的運行提供基礎(chǔ)支撐。霧計算通過整合不同霧節(jié)點的資源，形成局部的資源池，并對所屬的各類用戶群提供服務(wù)支撐。云計算可以為霧計算提供更多的計算能力、存儲能力以及更多的服務(wù)類型。對于用戶而言，無需知道服務(wù)所處的實際位置，只需要采用統(tǒng)一的訪問接口，即可向“霧”/“云”請求服務(wù)。

2 霧計算平臺上的野區(qū)路徑規(guī)劃應(yīng)用場景分析

2.1 野區(qū)路徑規(guī)劃功能介紹

野區(qū)路徑服務(wù)能夠結(jié)合具體的道路信息、河流信息、湖泊信息、居民區(qū)信息等，自動識別出可通行的野地范圍，并在路徑規(guī)劃過程中，無縫銜接道路，在有道路的情況下，優(yōu)先選擇道路，在道路繞遠或無道路情況下，生成合適的野地路徑規(guī)劃方案。

野區(qū)路徑規(guī)劃分為預(yù)處理模塊與路徑規(guī)劃模塊兩部分，預(yù)處理模塊是將矢量類型的地圖信息柵格化，提取每個柵格中的地理信息并保持至相應(yīng)的矩陣中，并分析柵格本身的屬性，包括是否可通行、是否代表河流等信息以及柵格與柵格之間的關(guān)系，包括下一個柵格是否某障礙區(qū)域的邊界等。執(zhí)行預(yù)處理模塊的耗時長、內(nèi)存占用大、計算結(jié)果占用磁盤空間多。路徑規(guī)劃模塊是在預(yù)處理模塊的基礎(chǔ)上，根據(jù)預(yù)處理生成的結(jié)果，采用合適的尋路方法，如A*算法、蟻群算法等方式，選擇合適的路線。

2.2 野區(qū)路徑規(guī)劃應(yīng)用場景分析

根據(jù)上節(jié)介紹的野區(qū)路徑規(guī)劃模塊描述，野區(qū)路徑規(guī)劃在“霧”計算平臺上的應(yīng)用場景如圖2所示。

圖2 野區(qū)路徑規(guī)劃應(yīng)用場景

根據(jù)云平臺提供的計算以及存儲能力，針對大范圍、多類型車輛進行預(yù)處理操作，提取出基礎(chǔ)的地理信息，包括道路、河流、湖泊、草地等信息，并根據(jù)不同型號車輛的通行能力，包括野地通行速度、涉水深等，結(jié)合矢量地圖與車輛通行參數(shù)，生成柵格數(shù)據(jù)，柵格數(shù)據(jù)中每個柵格點保存了該點及其周圍區(qū)域的地理信息，如該柵格區(qū)域內(nèi)是否為道路、河流或者湖泊，以及該類型車輛是否可以通過該柵格等。將不同區(qū)域、不同車輛的柵格信息持久化保存在云端存儲器中，當某霧平臺需要對外提供野區(qū)路徑規(guī)劃能力時，從云端將指定區(qū)域的柵格數(shù)據(jù)信息下載到特定的霧平臺中，霧平臺采集各個車輛、平板電腦等設(shè)備的實時狀態(tài)信息，結(jié)合具體的用戶需求與“云”端預(yù)處理結(jié)果，進行實時的路徑推送功能。霧平臺可將搜集的地理變化信息，整理后反饋至“云端”，優(yōu)化生成的柵格數(shù)據(jù)。

2.3 基于霧計算平臺的路徑規(guī)劃服務(wù)優(yōu)點分析

基于霧計算平臺的路徑規(guī)劃服務(wù)能夠為用戶提供實時、準確的路徑建議，主要優(yōu)點如下：

1）基于霧計算平臺的路徑規(guī)劃服務(wù)能夠根據(jù)當前道路與野區(qū)的狀況提供低時延的服務(wù)；

2）能夠提供靈敏的斷線重連服務(wù)，當車輛由于環(huán)境變化出現(xiàn)通信中斷并重新連接后，能夠繼續(xù)提供相關(guān)服務(wù)；

3）能夠有效降低終端的計算壓力，能夠提供多種類型的訪問方式，為異構(gòu)的終端提供統(tǒng)一的路徑規(guī)劃服務(wù)；

4）能夠有效降低云計算平臺的訪問量，針對某特定位置，推送地區(qū)相關(guān)性服務(wù)，包括油料補給點、臨時休整區(qū)域等；

5）能夠搜集特定地區(qū)的天氣、水位等信息，實時修改路徑方案；

6）能夠?qū)⒙窂揭?guī)劃的衍生及相關(guān)的信息，如預(yù)計到達時間、前方雷雨等信息，實時推送至用戶；

7）能夠采集匯總路況、野地、水紋、居民區(qū)的變化信息，整理并融合后將變化內(nèi)容上傳至云計算平臺，優(yōu)化地形預(yù)處理結(jié)果。

3 野區(qū)路徑規(guī)劃算法

3.1 單類型車輛野區(qū)路徑規(guī)劃介紹

利用“云”環(huán)境下的計算能力，針對不同類型的車輛，分別對需要進行路徑規(guī)劃的區(qū)域進行地圖預(yù)處理操作。

單類型車輛路網(wǎng)-野區(qū)路徑規(guī)劃問題主要包括兩個部分：1）地圖預(yù)處理；2）針對單一車輛類型的路徑尋優(yōu)。本文假設(shè)已獲取初始地理環(huán)境信息，包括道路橋梁信息、建筑群信息、水域信息、高程信息等。對于突發(fā)的地圖信息，包括橋梁斷裂、新建臨時橋梁等，在霧計算平臺上采用動態(tài)地圖調(diào)整的方式進行路徑調(diào)整。

3.2 地圖預(yù)處理

通過預(yù)先獲取的地理信息，對指定地域的地圖進行柵格化。單個柵格中包含的信息為：道路信息與可通行/不可通行信息，道路信息的優(yōu)先級最高，當該柵格同時有道路和不可通行區(qū)域，如代表橋梁穿過湖泊的柵格，認為該柵格代表道路。不可通行信息包括建筑物或建筑物群信息、湖泊信息、河流信息、高程障礙信息等，同一標示為不可通行區(qū)域。地圖預(yù)處理流程，如圖3 所示。

圖3 地圖預(yù)處理流程圖

3.3 地圖動態(tài)調(diào)整

隨著道路與野區(qū)的環(huán)境發(fā)生變化，初始化的柵格信息無法滿足后續(xù)路徑尋優(yōu)的需求，此時需要設(shè)立動態(tài)地圖調(diào)整圖層，根據(jù)該圖層中的信息進行柵格矩陣的二次調(diào)整。動態(tài)地圖調(diào)整圖層中包括：1）臨時可通行區(qū)域；2）動態(tài)障礙區(qū)域。

臨時可通行區(qū)域：當開拓出新路、新建臨時橋梁等情況下，在動態(tài)圖層中設(shè)置臨時可通行圖元，將對應(yīng)區(qū)域的柵格設(shè)置為可通行區(qū)域。臨時可通行區(qū)域信息優(yōu)先級高于湖泊、河流等初始障礙信息。

動態(tài)障礙區(qū)域：臨時設(shè)置禁入?yún)^(qū)域、道路堵塞等情況下，在動態(tài)圖層中設(shè)置動態(tài)障礙區(qū)域，將對應(yīng)區(qū)域的柵格設(shè)置為障礙區(qū)域，動態(tài)障礙區(qū)域的優(yōu)先級高于原始道路信息。

3.4 野區(qū)路網(wǎng)路徑尋優(yōu)

將地圖映射為柵格矩陣的基礎(chǔ)上，采用A*算法作路徑尋優(yōu)方法。A*算法是一種啟發(fā)式路徑搜索算法，具有較高的搜索效率。A*算法的核心為啟發(fā)函數(shù)，如式（1）所示。

其中，f（n）為第n 個柵格點的啟發(fā)函數(shù)值，g（n）為從起始柵格點到當前柵格點的累計消耗，h（n）為從當前柵格點到終止柵格點的預(yù)計消耗。

野區(qū)路網(wǎng)環(huán)境下需要提供不同的規(guī)劃模式，包括：1）路徑最短模式；2）道路優(yōu)先。路徑最短模式情況下，采用傳統(tǒng)的A*算法的啟發(fā)函數(shù)；時間最短模式下，采用優(yōu)先道路的原則。本節(jié)在結(jié)合地圖預(yù)處理的基礎(chǔ)上，根據(jù)柵格中保存的道路相關(guān)屬性，創(chuàng)新性地提出含有道路損耗的啟發(fā)函數(shù)，在靠近道路的情況下，優(yōu)先使用道路機動，當?shù)缆防@遠時，采取抄近路的方式，進入野地機動，野區(qū)路網(wǎng)的啟發(fā)函數(shù)如式（2）所示。

其中，gi，j為從起始柵格到第i 行、第j 列柵格的累計損耗，hi，j為從第i 行、第j 列柵格到終點柵格的預(yù)計損耗，μLast表示上一柵格點至該柵格點的道路損耗，計算公式如式（3）所示。

其中，r 為接近道路率，r 越大，道路損耗的變化率越快，K 為道路因子的上限值，K 越大遠離道路的消耗越高。θcurr為當前柵格點的道路距離，θLast為上一柵格點的道路距離，θgap為相鄰兩個柵格間最大的道路距離差，在初始化矩陣的過程中，通過式（4）計算得到。

其中，Lot（1，1）表示第1 行、第1 列的經(jīng)度值，Lot（3，3）為第3 行、第3 列的經(jīng)度值，Lat（1，1）表示第1 行、第1 列的緯度值，Lat（3，3）表示第3 行、第3列的緯度值，Lj表示該地區(qū)單位經(jīng)度的實際距離（m），Lw表示該地區(qū)單位緯度的實際距離（m）。

A*算法收斂的充要條件是：對于任意節(jié)點n，都有h（n）≤h'（n），h'（n）是n 到目標的實際最短距離。此時也稱h（n）是可采納的。本文中采用Moore型柵格，路徑尋優(yōu)時，只能向上、下、左、右、左斜上、左斜下、右斜上、右斜下這8 個方向移動，所以，第i行、第j 列的預(yù)計消耗函數(shù)h（i，j）如式（5）所示。

其中，Endi、Endj 是終點的柵格坐標信息，i，j 是當前路徑點的柵格坐標。根據(jù)野區(qū)路網(wǎng)啟發(fā)函數(shù)，結(jié)合A*算法的常見步驟，實現(xiàn)野區(qū)路網(wǎng)的路徑規(guī)劃功能。

4 基于霧計算平臺的路徑規(guī)劃結(jié)果

本次仿真中，首先試驗了路網(wǎng)-野區(qū)的路徑規(guī)劃結(jié)果，預(yù)處理區(qū)域分別涵蓋了居民區(qū)、河流、道路、橋梁、溝渠等常見矢量地理信息，預(yù)處理結(jié)果如圖4 所示。

圖4 路網(wǎng)-野區(qū)預(yù)處理結(jié)果

其中，圖4（a）表示原始地圖情況，圖4（b）表示預(yù)處理后的結(jié)果，其中標號①標簽表示識別該區(qū)域為居民區(qū)障礙；②號標簽表示識別該區(qū)域為面狀湖泊障礙；③號標簽表示識別出河流障礙；④號標簽表示識別該區(qū)域為道路。其余未標示為可通行野地區(qū)域。

圖4（c）與（d）分別表示當預(yù)處理的車輛爬坡度為30°與45°時，識別出該區(qū)域的坡度障礙，紅色區(qū)域表示高程障礙區(qū)域。爬坡度為45°相比于車輛爬坡度為30°的情況，高程障礙明顯減少，只有零星區(qū)域為高程障礙。

在完成地圖柵格化的基礎(chǔ)上，考慮了時間最短模式與路徑最短模式，在時間最短模式中，設(shè)置優(yōu)先接近道路，假設(shè)車輛在道路上的行駛速度是野地上行駛速度的一倍，兩種路徑尋優(yōu)結(jié)果如圖5所示。

圖5 靜態(tài)雙模式路徑尋優(yōu)結(jié)果

圖5 中，標號①表示時間最短模式，標號②表示路徑最短模式，在時間最短模式中，從起始點出發(fā)后，優(yōu)先考慮在道路上行駛，當靠近終點時，脫離道路進入野地行駛，在路徑最短模式中，以快速接近終點為最優(yōu)目標，在靠近重點的過程中，通過道路跨越水系障礙物。

通過模擬器向霧計算平臺發(fā)送橋梁被毀以及新建臨時橋梁的模擬數(shù)據(jù)，并執(zhí)行動態(tài)路徑調(diào)整功能，仿真結(jié)果如圖6 所示。

圖6 地圖動態(tài)調(diào)整路徑規(guī)劃仿真

圖6 中①號標簽指向地圖為動態(tài)調(diào)整之前規(guī)劃的路徑；②號標簽指向地圖動態(tài)調(diào)整之后規(guī)劃的路徑；③號標簽指向障礙信息，該障礙區(qū)域覆蓋在原圖層中跨越河流的橋梁上；④號標簽指向臨時可通行區(qū)域，表示在該區(qū)域建立一座新的橋梁，提供跨越水系的通行能力。仿真的順序為：1）先設(shè)定起始點與終止點并進行路徑規(guī)劃，生成①號標簽指向的路徑；2）模擬器向霧計算平臺發(fā)送橋梁被毀信息，如③號標簽所示，此時進行路徑規(guī)劃，顯示為“未找到合適路徑”；3）模擬器向霧計算平臺發(fā)送新建橋梁信息，如④號標簽所示；4）重新進行路徑規(guī)劃，生成動態(tài)調(diào)整后的路徑，如②號標簽所示。

選取高層區(qū)域，設(shè)定車輛的爬坡度為30°，并進行預(yù)處理，通過模擬器向霧計算平臺發(fā)送高程變化數(shù)據(jù)，并執(zhí)行動態(tài)路徑調(diào)整功能，仿真結(jié)果如圖7所示。

圖7 高程變化動態(tài)仿真

圖7 中，（a）圖表示針對爬坡度為30°的車輛，進行預(yù)處理后，霧計算平臺的路徑規(guī)劃服務(wù)識別出的不可通信區(qū)域，如①號標簽指向的紅色區(qū)域；（b）圖表示高程變化后的動態(tài)路徑規(guī)劃效果，③號標簽指向高程平滑區(qū)域，如通過炸裂山體等方式將坡度過高的地方移除后，重新進行路徑規(guī)劃，規(guī)劃結(jié)果如④號標簽所示，霧計算平臺的路徑規(guī)劃服務(wù)識別出新的可通信區(qū)域，并采用新開辟出的通路作為規(guī)劃結(jié)果。

5 結(jié)論

本文提出了基于霧計算環(huán)境下的道路- 野區(qū)路網(wǎng)的路徑規(guī)劃的方法，分別闡述了路徑規(guī)劃服務(wù)在霧計算平臺下的應(yīng)用模式。并從地圖預(yù)處理、地圖動態(tài)調(diào)整、路徑尋優(yōu)這3 個方面，闡述了單類型車輛的路徑規(guī)劃方法。今后的研究過程中，在路徑規(guī)劃時要考慮更多的約束信息，如某通道的流量約束，并將單類型車輛的路徑規(guī)劃擴展至包含不同類型車輛隊伍的聯(lián)合路徑規(guī)劃。