基于改進的Dijkstra算法躲避衛(wèi)星偵查的路線選擇

章胤　李瑞敏　郝茂林　王嘉瑜　孫鵬越　高琪

摘 要：由于衛(wèi)星在軍事領(lǐng)域的應(yīng)用，衛(wèi)星偵察下的軍事運輸路線選擇得到廣泛關(guān)注。本文通過分析衛(wèi)星在其星下點的軌跡，并生成道路緩沖區(qū)，借助地理信息系統(tǒng)（GIS）和改進的Dijkstra算法，為衛(wèi)星偵察下的最優(yōu)路徑選擇提供了更優(yōu)途徑。將該方法應(yīng)用于實際問題中，程序運行所用時間為7.44秒，而經(jīng)典Dijkstra算法運行時間為16.83秒，改進后的Dijkstra算法相比經(jīng)典算法節(jié)約了近10秒，一定程度上能使相關(guān)最優(yōu)選擇問題的效率得到提高。

關(guān)鍵詞：衛(wèi)星運動；公路運輸；路線選擇；GIS；Dijkstra算法

中圖分類號：TP301.6 文獻標(biāo)識碼：A

1 引言（Introduction）

隨著空間軍事化的高速發(fā)展，衛(wèi)星偵察因其可以獲得全天候、大范圍、近實時的戰(zhàn)場信息，被認(rèn)為是從外層空間采集地理信息的強有力的手段。為了保護國家機密，在軍事運輸過程中必須要躲避航天衛(wèi)星的偵察并要在規(guī)定時間內(nèi)盡快到達目的地。因此，快速生成安全的最短運輸路線，躲避衛(wèi)星偵查，實現(xiàn)安全運輸顯得尤為重要。

國內(nèi)外對軍事運輸路線選擇的研討處于發(fā)展完善階段。Rui Neves-Silva等人提出利用擴展的Dijkstra算法計算災(zāi)害中撤離人員的替代路線[1]。Akshay Kumar Guruji等人利用在碰撞階段之前確定啟發(fā)式函數(shù)的值來代替初始化的一種路徑規(guī)劃算法，以尋找機器人工作時的無碰撞路徑，該算法減少了問題處理時間[2]。Xiu Li Gao等人研究改進的Dijkstra算法解決動態(tài)路徑選擇問題[3]。在國內(nèi)，王輝等人提出利用Dijkstra算法和改進的蟻群算法解決泊車系統(tǒng)的路徑規(guī)劃問題[4]。沈睿等人使用GIS數(shù)據(jù)模型和改進的Dijkstra算法，縮短了智能交通系統(tǒng)尋求最短路徑的搜索時間[5]。姚志敏提出了將Dijkstra算法總計算步數(shù)由原來的步減少為不到步的方法[6]。

本文結(jié)合衛(wèi)星的運行軌跡和覆蓋范圍，以經(jīng)典Dijkstra算法為基礎(chǔ)，對算法進行一定的改進，提高了在衛(wèi)星影響下躲避衛(wèi)星偵察的最優(yōu)公路運輸路線選擇的效率和準(zhǔn)確性，并借助GIS系統(tǒng)進行模擬。

2 基于Dijkstra算法的路徑選擇模型（The path

selection model based on Dijkstra algorithm）

2.1 地理信息系統(tǒng)

地理信息系統(tǒng)（Geographic Information System，GIS）是用于不同層次的規(guī)劃、管理與決策所需要的信息粒度與空間信息的圖像表達（可視化）。GIS起源于專題地圖，但又高于專題制圖。在數(shù)字環(huán)境下，地圖信息成為GIS的基礎(chǔ)信息與專題信息的載體，一方面是為了通過圖形信息壓縮來保證地圖的可讀性，而更重要的是還負(fù)擔(dān)著生成GIS多尺度數(shù)據(jù)庫的新使命。對于以道路網(wǎng)為代表的人工線狀物體集合，利用賦權(quán)圖原理和結(jié)點度的信息使其結(jié)構(gòu)化，進而對其進行全局性評價[7]。在地理信息系統(tǒng)中，道路交叉點和道路分別構(gòu)成道路交通網(wǎng)絡(luò)中的點集合和邊集合。其中，通過收集點矢量要素和邊矢量要素的屬性字段，來創(chuàng)建邊和點之間的權(quán)重屬性。如道路的長度、道路的類型、道路的寬度等都可以轉(zhuǎn)換為道路權(quán)重。該模型以對道路復(fù)雜性適應(yīng)度高的Dijkstra算法為基礎(chǔ)。

2.2 衛(wèi)星軌道和星下點軌跡

衛(wèi)星軌道是衛(wèi)星在獲得某一初始水平速度后，可以環(huán)繞地球飛行的運行軌跡。根據(jù)開普勒第一定律，衛(wèi)星運轉(zhuǎn)軌道的平面，是一個以地心為其中的一個焦點的橢圓。決定衛(wèi)星運行軌道的參數(shù)主要有六種[8]，分別是長軸a、偏心率e、軌道傾角i、升交點赤經(jīng)、近地點幅角和過近地點時刻t。衛(wèi)星的星下點是指衛(wèi)星和地心的連線與地面的交點。星下點軌跡是因衛(wèi)星運動與地球的自轉(zhuǎn)使得星下點在地球表面進行移動所形成的軌跡。由于地球自轉(zhuǎn)，衛(wèi)星星下點軌跡的前一圈與后一圈一般不重合。當(dāng)考慮地球自轉(zhuǎn)時，衛(wèi)星的星下點軌跡計算公式[9]為：

上述公式中：表示地心緯度、表示地心經(jīng)度、表示衛(wèi)星平均角速度、i表示軌道傾角、表示衛(wèi)星升交點相對經(jīng)度零點的西退速率、表示衛(wèi)星經(jīng)過升交點時的經(jīng)度、表示衛(wèi)星經(jīng)過升交點以后經(jīng)歷的時間。

2.3 衛(wèi)星覆蓋范圍

以衛(wèi)星在當(dāng)前時刻下，在地面上所有能觀察到衛(wèi)星的點的集合，作為衛(wèi)星的地面覆蓋區(qū)域。從理論上來說，如圖1所示，衛(wèi)星到地球表面的兩條切線、之間的部分便是衛(wèi)星的地面覆蓋區(qū)域。但由于最小觀察角的因素，實際的衛(wèi)星覆蓋規(guī)模會稍有縮?。磮D1中、以內(nèi)的位置）。同該區(qū)域，也就是以衛(wèi)星 在當(dāng)前時刻下，所要研究的緩沖區(qū)（對應(yīng)的星下點 為中心，以所對應(yīng)弧長為半徑的地面區(qū)域）。在實際地理應(yīng)用中，將地球視為圓球，單顆衛(wèi)星的覆蓋范圍視為是以星下點軌跡為中心，寬度為的條形域。

2.4 影響因素簡化

影響運輸因素有很多，例如運載工具的種類、道路的交通狀況（如紅綠燈個數(shù)、堵塞程度）、道路上的障礙（如壕溝、涵洞和橋梁）、部隊行駛時的指揮人員和駕駛?cè)藛T的技能，以及當(dāng)時的氣象條件等都是影響軍事運輸?shù)囊蛩?。本文對上述因素不予考慮，僅考慮衛(wèi)星偵察對道路選擇的影響。僅考慮高速公路、縣道、省道和國道這四種類型的道路。

2.5 經(jīng)典Dijkstra算法的主要原理

經(jīng)典Dijkstra算法是一種通過比較再添加的模型，也稱雙標(biāo)記法[10]。并且該算法只適用于邊權(quán)重均非負(fù)的賦權(quán)圖。對于圖，其中V表示頂點集，E表示邊集，W表示權(quán)集。對圖G中的每一點進行標(biāo)號，其中是從源點s開始到第i個節(jié)點的最短路徑長度，是第i個節(jié)點的直接前趨。其基本思路如下：

（1）對參數(shù)進行初始化。令，并標(biāo)記s點。其他為，均為空。

（2）對于任意未標(biāo)記的節(jié)點j，求。其中表示已標(biāo)記的節(jié)點k到源點s的距離，表示從節(jié)點k到節(jié)點j的距離。

（3）標(biāo)記i節(jié)點，使得，并取。

（4）重復(fù)（2）（3）步，直到所有點的已標(biāo)記，算法運行完畢。

2.6 Dijkstra算法理解與改進

從2.3中的算法過程中可以看出，每個節(jié)點要標(biāo)記，需要比較其所連接的所有邊的最小值，并且最終要標(biāo)記所有的節(jié)點，算法才可以結(jié)束。也就是說，對于一張圖來說，圖中的節(jié)點越多，運行算法的時間越長。而對于實際道路中，因地理因素的影響，兩地之間的最短距離，往往不包括以兩點距離為直徑的圓以外的點，并且對于圖中邊的權(quán)值與實際道路長度成正相關(guān)，即對于所考慮節(jié)點距離較遠的節(jié)點，顯然沒必要考慮。所以對于算法遍歷的點的數(shù)量，可以選擇性遍歷，在以源點與所求節(jié)點歐氏距離為直徑的圓內(nèi)遍歷，可進一步減少了循環(huán)比較的次數(shù)，從而提高算法的運行效率。

在Dijkstra算法運行步驟（2）中，對于遍歷所有未標(biāo)記的節(jié)點，傳統(tǒng)的Dijkstra算法關(guān)于節(jié)點的遍歷是無序的。我們知道算法要對所有點遍歷是不可避免的，但如果圖中節(jié)點有些權(quán)值明顯大于其他權(quán)值而又要先遍歷，到某個節(jié)點的最短路徑加經(jīng)過該節(jié)點邊的直接距離之和中取最小值，在進行最小值判斷的時候，權(quán)值較大的邊會在循環(huán)中比較多次，這會制約算法的效率。如果在計算機運行前得到權(quán)值的排序，利用這樣的排序可以將權(quán)值較小的優(yōu)先比較，那么在與其他邊比較的過程中，可以直接舍去一些權(quán)值較大的邊，從而可以提高算法效率。

引入順序數(shù)組，對節(jié)點數(shù)據(jù)結(jié)構(gòu)加入篩選屬性scr，改進的Dijkstra算法的主要思路如下：

（1）初始化源點數(shù)據(jù)，記scr值為0。對所有邊的權(quán)重匯總升序編號存入數(shù)組中。

（2）在以出發(fā)點到匯點為直徑的圓，將覆蓋到的點。

（3）對圓中未標(biāo)記的節(jié)點j，依數(shù)組D的次序，求。其中表示已標(biāo)記的節(jié)點k到源點s的距離，表示從節(jié)點k到節(jié)點j的距離。

（4）標(biāo)記i節(jié)點，使得，并取。

（5）重復(fù)（2）（3）（4）步，直到全部點的已標(biāo)記，算法運行完畢。

對于增加的衛(wèi)星過頂因素，以衛(wèi)星過頂時的緩沖區(qū)為參考，一方面減少了所遍歷的點的個數(shù)，但另一方面會阻礙原始最短路徑的選擇，并且緩沖區(qū)會隨著時間規(guī)律性移動。

為了解決這些問題，將衛(wèi)星過頂?shù)木彌_區(qū)等效為車輛沿原始最短路行駛下的緩沖區(qū)，將經(jīng)過緩沖區(qū)以后的路段進行二次處理。以重新進入緩沖區(qū)的節(jié)點作為新的源點，重新尋找最短路徑，每找到一個中間點，將該點作為新的源點，再次重新尋找最短路徑，直到離開衛(wèi)星緩沖區(qū)。

3 應(yīng)用與實現(xiàn)（Application and implementation）

在Arcgis 10.2，Orbitron 3.71等軟件中對算法進行實現(xiàn)。利用Orbitron 3.71獲取衛(wèi)星信息，利用Arcgis 10.2獲取地理地圖并對其數(shù)據(jù)庫進行處理，利用Arcgis 10.2中自帶的Python 2.7腳本實現(xiàn)算法。

3.1 衛(wèi)星過頂軌跡

選擇恰當(dāng)?shù)男l(wèi)星，使其星下點軌跡經(jīng)過所研究的道路。由于衛(wèi)星不斷運動，故設(shè)置每1分鐘更新一次衛(wèi)星位置，如圖3所示。通過衛(wèi)星各項參數(shù)，計算出衛(wèi)星掃描范圍，生成緩沖區(qū)。

3.2 最短路徑生成

考慮所選衛(wèi)星經(jīng)過的地理區(qū)域進行試驗，利用Arcgis 10.2繪制河北省秦皇島市—唐山市地圖，地籍?dāng)?shù)據(jù)采集1：10000；經(jīng)過計算，共得到4597個道路交叉點。假設(shè)高速公路行駛時速為勻速100公里/小時，普通公路行駛時速為勻速50公里/小時，不考慮行駛過程中的加、減速時間；假設(shè)衛(wèi)星的覆蓋面帶是以星下點軌跡為中心，寬度為固定值的條帶；假設(shè)A地和B地之間有多條路相連，在運輸過程中如果按未考慮衛(wèi)星影響因素生成的最短路徑在衛(wèi)星的覆蓋范圍內(nèi)，那么依據(jù)衛(wèi)星所在位置和覆蓋范圍在衛(wèi)星覆蓋區(qū)域外尋找路徑或者原地等待。如果經(jīng)過區(qū)域沒有被衛(wèi)星覆蓋，那么依照原路行駛；不考慮車隊長度對避開衛(wèi)星的影響。

若采用經(jīng)典Dijkstra算法腳本運行，因經(jīng)過緩沖區(qū)以后，緩沖區(qū)之內(nèi)的點再次加入，節(jié)點最短路徑得到更新，所以最終得到的路徑并不是在緩沖區(qū)影響下的最短路徑。采用改進的方法，所生成的道路并不是起點到終點的最短路，而是最短路的近似。其原因在于緩沖區(qū)是動態(tài)移動的，如按原始選擇的道路行駛將會與緩沖區(qū)相遇。于是選擇更換道路，在衛(wèi)星無法偵察到的其余道路中選擇最短路。

選擇以河北省秦皇島市（119.714°E，39.946°N）為起點，以唐山市（118.172°E，39.615°N）為終點，經(jīng)過G1高速，楊柏路，再到唐古路，最終到達目的地，途中紅色標(biāo)線即為躲避衛(wèi)星偵察的最短路徑。通過對比發(fā)現(xiàn)，利用改進后的算法，根據(jù)衛(wèi)星進入的時刻，重新記錄新起點，程序運行所用時間為7.44秒，而經(jīng)典算法所運行時間為16.83秒，相比經(jīng)典算法節(jié)約了近10秒，一定程度上縮短了路徑選擇時間。

4 結(jié)論（Conclusion）

本文基于衛(wèi)星星下點軌跡、衛(wèi)星覆蓋范圍和Dijkstra算法的特點，并借助地理信息系統(tǒng)，建立了基于改進的Dijkstra算法躲避衛(wèi)星偵察的路線選擇模型，并通過軟件進行了實現(xiàn)，滿足了軍事運輸過程中對隱蔽性和快速性的要求。但本文在對道路進行選擇時，僅考慮了常見的道路類型。算法效率雖然得到提高，但也減少了道路選擇，使得所求得的距離與實際最短路仍有差距。同時，由于道路限制等其他復(fù)雜原因，無法求得真正意義上的最短路徑，只能最大程度的接近，也是接下來進一步研究的重點。

參考文獻（References）

[1] Rui Neves-Silva，George A.Tshirintzis，Vladimir Uskov，et al.An Extended Dijkstra's Algorithm for Calculating Alternative Routes for Evacuee Agents in Disaster Simulation[J].Frontiers in Artificial Intelligence and Applications，2014：262.

[2] Akshay Kumar Guruji，Himansh Agarwal，D.K.Parsediya.Time-efficient A*Algorithm for Robot Path Planning[J].Procedia Technology，2016：23.

[3] Xiu Li Gao，Tian Jun Hu，Jia Zheng.Research on Dynamic Path Selection Improved Dijkstra Algorithm[J].Advanced Materials Research，2014（1006）：3382.

[4] 王輝，朱龍彪，王景良，等.基于Dijkstra-蟻群算法的泊車系統(tǒng)路徑規(guī)劃研究[J].工程設(shè)計學(xué)報，2016，23（05）：489-496.

[5] 沈睿，朱學(xué)君.基于GIS的最優(yōu)路徑選擇的設(shè)計與實現(xiàn)[J].工業(yè)儀表與自動化裝置，2016（02）：102-105.

[6] 姚志敏.最短路徑問題Dijkstra算法的改進[J].數(shù)字技術(shù)與應(yīng)用，2016（11）：133.

[7] 任偉建，左方晨，黃麗杰.基于GIS的Dijkstra算法改進研究[J].控制工程，2018，25（02）：188-191.

[8] 韓建昌.我國通用航空文化建設(shè)研究[D].西北工業(yè)大學(xué)，2016.

[9] 張三彬，張永生，近圓.軌逍遙感衛(wèi)星星下點軌跡的計算[J].測繪學(xué)院學(xué)報，2001，18（4）：257-259.

[10] 王樹西，李安渝.Dijkstra算法中的多鄰接點與多條最短路徑問題[J].計算機科學(xué)，2014，41（06）：217-224.

作者簡介：

章 胤（1978-），男，碩士，講師.研究領(lǐng)域：微分方程數(shù)值解，數(shù)學(xué)建模.

李瑞敏（1996-），女，本科生.研究領(lǐng)域：統(tǒng)計學(xué).

郝茂林（1995-），男，本科生.研究領(lǐng)域：信息與計算科學(xué).

王嘉瑜（1996-），女，本科生.研究領(lǐng)域：統(tǒng)計學(xué).

孫鵬越（1998-），男，本科生.研究領(lǐng)域：統(tǒng)計學(xué).

高 琪（1997-），女，本科生.研究領(lǐng)域：會計.