室內(nèi)離散格網(wǎng)空間Dijkstra最短路徑算法優(yōu)化

張愛國，鄔群勇，鄧 健，欒海軍，陳潤靜

(1.廈門理工學院計算機與信息工程學院，福建 廈門 361024；2.福州大學福建省空間信息工程研究中心，福建 福州 350003)

近年來，城市中涌現(xiàn)了越來越多的城市綜合體，其活動空間大都為室內(nèi)環(huán)境，比如萬達廣場、火車站地下商場等。這些巨大的商業(yè)綜合體給人們帶來購物樂趣和生活方便的同時，也為顧客尋找商家、查找車位和尋找走失的家人朋友帶來了困難。同時，在此種情境下，當有災難發(fā)生時，大多數(shù)顧客往往難于快速找到安全出口，從而錯過逃離的最佳時間段。綜合體在為顧客提供享受生活樂趣平臺的同時，也需要保障顧客的安全，因此，有必要提供一個容易獲取的特定點之間的最短路徑指引。綜合起來看，手機APP是一個很好的途徑。目前，各類智能傳感器已逐漸成為了手機的標配，比如Wi-Fi、加速度器和GNSS芯片等，這些都為手機實現(xiàn)室內(nèi)定位與導航提供了基礎[1-5]。

由于室內(nèi)環(huán)境復雜，其路徑規(guī)劃問題也逐漸引起了許多國內(nèi)外學者的重視，包括Dijkstra最短路徑算法、蟻群算法、深度優(yōu)先算法和人工蜂群算法等[6-11]。其中最常見的處理方式為：將室內(nèi)建筑結(jié)構(gòu)繪制成平面圖，建立地圖數(shù)據(jù)的空間拓撲關(guān)系，然后，直接采用Dijkstra算法，計算一條最短路徑，并展示該導航地圖。由于未對Dijkstra算法做優(yōu)化改進，當建筑物較為復雜時，其處理的網(wǎng)絡節(jié)點、連接邊等的數(shù)據(jù)量十分巨大。在計算最短路徑時，也耗費內(nèi)存，降低了效率。針對這些問題，有學者嘗試在網(wǎng)絡節(jié)點屬性、幾何數(shù)據(jù)的存儲結(jié)構(gòu)等方面做調(diào)整，取得了一定的優(yōu)化效果，但在數(shù)據(jù)存儲、計算復雜度等方面還有提高的空間[12-13]。

室內(nèi)最短路徑導航設計的通常是在室內(nèi)地圖環(huán)境下，使用者依據(jù)室內(nèi)實時定位成果到達目標地理位置的最短路徑，為此，實時定位數(shù)據(jù)的獲取與地理位置的地圖展示是前提。近年來，隨著Wi-Fi網(wǎng)絡的廣泛使用，也促使了Wi-Fi室內(nèi)定位的快速發(fā)展，其中基于離散格網(wǎng)的Wi-Fi RSSI(received signal strength indicator，接收信號強度指示)定位技術(shù)得到較多的重視[14-19]。以離散格網(wǎng)展示地圖和顯示路徑導航的方式，可實現(xiàn)該地圖導航成果與基于離散網(wǎng)絡的Wi-Fi RSSI定位的無縫連接。為此，本文針對室內(nèi)場所的路徑尋址，在室內(nèi)離散格網(wǎng)空間環(huán)境下對Dijkstra 算法進行分析與改進，提出一種優(yōu)化的Dijkstra最短路徑算法。

1 Dijkstra最短路徑算法的優(yōu)化

Dijkstra算法是典型的圖最短路徑算法，用于計算圖中一個節(jié)點到其他所有節(jié)點的最短路徑[15]。目前經(jīng)過眾多計算機專家對17種比較具有代表性的最短路徑算法進行測試評估，Dijkstra算法被認為是解決非負權(quán)值圖中兩點間最短路徑路徑搜索最合適的的算法之一。然而，在離散格網(wǎng)空間條件下，直接使用Dijkstra算法，將要存儲每個網(wǎng)格的位置數(shù)據(jù)，則產(chǎn)生較大的數(shù)據(jù)冗余。為此，本文分析并優(yōu)化設計了離散格網(wǎng)環(huán)境下Dijkstra最短路徑算法。優(yōu)化過程主要包括將次區(qū)域間與區(qū)域內(nèi)最短路徑分開處理，在起終點次區(qū)域內(nèi)尋找其與最短路徑的交點，并用之代替次區(qū)域內(nèi)的網(wǎng)絡節(jié)點。

1.1 次區(qū)域內(nèi)網(wǎng)絡節(jié)點到起終點最短路徑的確定

次區(qū)域中有唯一的網(wǎng)絡節(jié)點，起終點分別所在的次區(qū)域之間的最短路徑計算即轉(zhuǎn)化為兩個次區(qū)域網(wǎng)絡節(jié)點之間的最短路徑運算。所有的網(wǎng)絡節(jié)點都存儲在空間數(shù)據(jù)庫中，為此，可以直接運用Dijkstra算法得到他們之間的最短路徑及路徑長度。

面向區(qū)域的最短路徑首尾兩條邊分別會與包含起終點的次區(qū)域相交，假設交點分別為PZS、PZT，則包含起點或終點次區(qū)域的最短路徑如圖1所示。依據(jù)次區(qū)域的創(chuàng)建法則，區(qū)域內(nèi)任意兩點存在直連或1次轉(zhuǎn)折后的連接，為此，在以區(qū)域網(wǎng)絡節(jié)點Z0101、起點S和PZS構(gòu)成的三角形中，三角邊起點S-PZS的邊長總會小于另外兩條邊長之和，所以，起點區(qū)域內(nèi)的最短路徑為起點S-PZS的邊。因此，該最短路徑邊的計算為直接對應行列相減，并取絕對值后相加。假設次區(qū)域與面向區(qū)域的最短路徑的交點坐標為PZS(XPZS,YPZS)，起點坐標為S(XS,YS)，則最短路徑長度用公式表示為：D=|XPZS-XS|+|YPZS-YS|，最短路徑為： (XS,YS) → (XPZS,YS) → (XPZS,YPZS)。該處理過程也適合終點T對應的區(qū)域最短路徑情況。

圖1 包含起點或終點次區(qū)域的最短路徑

綜合以上3部分的最短路徑，從起點S至終點T的最短路徑可以歸結(jié)為首尾次區(qū)域內(nèi)起終點到其相應交點的路徑的兩部分，再加上兩個交點之間的最短路徑，用上圖圖形表示為：起點S→PZS→PSVS→PSVT→PZT→終點T，有了最短路徑，則可以根據(jù)網(wǎng)格數(shù)目得到其最短路徑長度。

1.2 優(yōu)化后的Dijkstra算法流程

在給定起終點的位置，通常為行列編碼后，將首先確定起點、終點所在的次區(qū)域，然后以兩個次區(qū)域內(nèi)的關(guān)鍵節(jié)點為面向區(qū)域的起、終網(wǎng)絡節(jié)點進行Dijkstra最短路徑計算，并得到相應的路徑和路徑長度，接著，在起、終點區(qū)域內(nèi)計算各自到其次區(qū)域內(nèi)關(guān)鍵節(jié)點的最短路徑，3段路徑的綜合即為最終的最短路徑規(guī)劃結(jié)果，為此，室內(nèi)離散格網(wǎng)空間Dijkstra算法流程如圖2所示。

圖2 優(yōu)化后的室內(nèi)離散格網(wǎng)空間Dijkstra算法流程圖

2 實驗結(jié)果與分析

采用PostgreSQL+PostGIS+pgRouting的空間數(shù)據(jù)庫工具，并用離散格網(wǎng)環(huán)境下的實驗數(shù)據(jù)分別測試了優(yōu)化的Dijkstra算法、原生的Dijkstra算法以及A*算法在最短路徑規(guī)劃運算中的數(shù)據(jù)存儲和運算復雜度等方面的效率。

2.1 實驗區(qū)室內(nèi)離散格網(wǎng)空間地理編碼

對空間地理編碼的方式有矩形行列編碼、坐標位置編碼等[20-21]，考慮到室內(nèi)區(qū)域特征，采用容易理解的矩形行列編碼。根據(jù)不同用途，室內(nèi)空間通常劃分為不同的次區(qū)域，為此最短路徑導航的室內(nèi)空間建模必須依據(jù)室內(nèi)布局進行關(guān)鍵節(jié)點的合理選取，以及節(jié)點控制區(qū)域的劃分，并對它們有效編碼。整個室內(nèi)空間由連續(xù)的大小相等的柵格組成，柵格的面積為1 m2，柵格行列編碼的起點為左下角(1，1)，行數(shù)由下至上、列數(shù)由左至右依次遞增，柵格布滿整個導航區(qū)域。同時，該編碼方式，只要給定左下角的地理坐標以及地圖比例尺，可以按比例投影得到所有網(wǎng)格點的地理坐標，從而與室外的地圖建立無縫連接。

2.1.1 路徑網(wǎng)絡節(jié)點選取及編碼

探討室內(nèi)離散格網(wǎng)空間任意兩個網(wǎng)格點之間的最短路徑規(guī)劃，屬于室內(nèi)精密導航。路徑規(guī)劃中，網(wǎng)絡節(jié)點的選取直接影響算法運行的效率和路徑的精度。為此，網(wǎng)絡節(jié)點的選取既要權(quán)衡布置的密度，也要盡量均勻分布。在保證密度小，提高計算效率的情況下，確保所有的網(wǎng)格點之間能夠通過網(wǎng)絡節(jié)點的串聯(lián)建立起通行路線。室內(nèi)格網(wǎng)空間往往結(jié)構(gòu)復雜，存在墻體、門、走廊和各類障礙物等。為此，網(wǎng)絡節(jié)點的選取也必須從室內(nèi)結(jié)構(gòu)出發(fā)，對于類似辦公室的小空間的門位置處必須設置網(wǎng)絡節(jié)點，走廊的交叉或分支處必須設置網(wǎng)絡節(jié)點，具有障礙物的拐角處必須設置網(wǎng)絡節(jié)點。比如某室內(nèi)格網(wǎng)空間包括隔間、走廊和障礙物的。藍顏色的網(wǎng)格點均為選取的網(wǎng)絡節(jié)點，藍色方塊包括所有的門位置的A、B、C、D、F、G、K、L、M、N、Q、R，走廊的Z0901、Z1401、Z4001，以及各墻體分開的次區(qū)域的Z0101、Z0201、Z0301、…、Z4001。所有的這些網(wǎng)絡節(jié)點，依據(jù)是否影響次區(qū)域的劃分，又可歸為兩類。其中以字母Z開頭的網(wǎng)絡節(jié)點決定后續(xù)的次區(qū)域劃分，并且Z字母后面的數(shù)字表示了次區(qū)域的編號和次區(qū)域中網(wǎng)絡節(jié)點的編號。其余字母開頭的網(wǎng)絡節(jié)點則不影響次區(qū)域的劃分，但占用區(qū)域內(nèi)的一個網(wǎng)格。網(wǎng)絡節(jié)點的地理編碼采用行列號表示，所有的網(wǎng)絡節(jié)點都可以通過行列號在室內(nèi)圖中唯一確定。依據(jù)該規(guī)定其路徑網(wǎng)絡節(jié)點的選取如圖3所示。

圖3 節(jié)點選擇圖

2.1.2 室內(nèi)離散格網(wǎng)空間劃分及編碼

有了任意位置的地理編碼，就可以方便地進行室內(nèi)區(qū)域的空間劃分，這也是本室內(nèi)最短路徑算法設計的重要基礎之一。

室內(nèi)格網(wǎng)空間在功能分割后的次區(qū)域之間往往通過門、走廊等進行連接，為此，在空間劃分時，必須考慮墻體和各類障礙物對通行阻隔的影響。更重要的是，每個區(qū)域需顧及關(guān)鍵節(jié)點的位置，使得控制區(qū)域內(nèi)的任意一點都能通過行或列的1～2次的直連到控制區(qū)域內(nèi)的唯一關(guān)鍵節(jié)點，如圖4所示。

圖4 次區(qū)域劃分規(guī)則

圖4中，綠顏色虛線將該部分格網(wǎng)空間分成了Z01、Z02、Z03、Z04的4個矩形次區(qū)域，任意選取的S1、T1網(wǎng)格點均能通過直線或僅有一次彎曲的折線直連到相應次區(qū)域的唯一網(wǎng)絡節(jié)點Z0301、Z0201。次區(qū)域中允許包含一定的障礙物，但該障礙物必須貼近次區(qū)域的邊界，正如圖4中的墻壁處和中間均有電腦桌，為此，劃分了4個次區(qū)域。

為了不遺漏任意的網(wǎng)格點，將整個室內(nèi)格網(wǎng)空間劃分成包括矩形、線形等的次區(qū)域，次區(qū)域之間不允許重疊。同時，任何的次區(qū)域內(nèi)都不能有具有完全阻斷通行的墻體，如圖1所示。圖1中的綠色虛線把整個導航格網(wǎng)空間劃分成了多個次區(qū)域，次區(qū)域圖形大多數(shù)為矩形，也有線形和集合圖形，比如Z14為兩個矩形構(gòu)成的復合幾何圖形、Z15為線形。次區(qū)域幾何圖形的編碼遵循開放地理空間聯(lián)盟(OGC)的簡單要素規(guī)范，并用WKT(well known text)格式進行表示。WKT是一種文本標記語言，用于表示矢量幾何對象、空間參照系統(tǒng)及空間參照系統(tǒng)之間的轉(zhuǎn)換。它的二進制表示方式WKB(Well Known Binary)則用于在數(shù)據(jù)庫中存儲相同的信息。WKT格式由OGC制定。

2.2 路徑節(jié)點數(shù)據(jù)組織與存儲

室內(nèi)離散格網(wǎng)空間最短路徑導航涉及到網(wǎng)絡節(jié)點、次區(qū)域等空間數(shù)據(jù)的運用，為此，數(shù)據(jù)的組織與存儲直接影響到路徑規(guī)劃的效率與效果。需要組織存儲的數(shù)據(jù)類型包括：區(qū)域空間幾何數(shù)據(jù)、網(wǎng)絡節(jié)點數(shù)據(jù)、直連節(jié)點邊數(shù)據(jù)等。

2.2.1 數(shù)據(jù)的組織與存儲框架

室內(nèi)最短路徑空間數(shù)據(jù)庫是路徑計算的基礎，根據(jù)組織存儲的數(shù)據(jù)類型特點，面向?qū)ο蟮目臻g數(shù)據(jù)庫是最佳的數(shù)據(jù)組織存儲方式。在設計路徑節(jié)點的空間數(shù)據(jù)模型時，需結(jié)合Dijkstra和A*最短路徑算法原理，為此，室內(nèi)格網(wǎng)空間路徑節(jié)點數(shù)據(jù)表結(jié)構(gòu)按照數(shù)據(jù)用途，存儲為3類數(shù)據(jù)：次區(qū)域數(shù)據(jù)、網(wǎng)絡節(jié)點信息數(shù)據(jù)和直連邊信息數(shù)據(jù)，其具體包括的屬性結(jié)構(gòu)和類型結(jié)構(gòu)如表1所示。

表1 數(shù)據(jù)表字段設計

表1中，WKT格式中包括了幾何對象的坐標數(shù)據(jù)，并遵循OGC的簡單幾何要素規(guī)范。x、y坐標分別用網(wǎng)格點的行號、列號表示。cost直連邊邊長的量取為起點至終點需經(jīng)過的網(wǎng)格數(shù)量，也可理解為距離或權(quán)重，如圖2所示，起點S1至終點Z0301的cost值為12，起點T1至終點Z0201的cost值為5。

2.2.2 路徑節(jié)點數(shù)據(jù)的查詢管理

為了提高最短路徑規(guī)劃的計算效率，初始路徑查找為面向起終點對應區(qū)域的最短路徑規(guī)劃，為此，必須先由網(wǎng)格點確定相應的次區(qū)域，這就涉及到網(wǎng)絡節(jié)點與區(qū)域的查詢管理。一般來說，空間數(shù)據(jù)庫管理系統(tǒng)提供了豐富的幾何對象之間的關(guān)系查詢函數(shù)，比如PostGIS數(shù)據(jù)庫管理系統(tǒng)的包含關(guān)系、空間索引創(chuàng)建功能等。為此，可根據(jù)vertexinfo數(shù)據(jù)表的controlzone字段，按照R樹索引建立最短路徑規(guī)劃的索引關(guān)系。從而在每次最短路徑計算中，先根據(jù)起、終點分別確定其對應的controlzone區(qū)域，然后，圍繞區(qū)域的關(guān)鍵節(jié)點進行最短路徑計算。

在起終點區(qū)域內(nèi)部的最短路徑數(shù)據(jù)查詢，則只需依據(jù)行列號對應連接即可。

2.3 實驗過程及結(jié)果

實驗區(qū)域為某校園建筑的第二層樓，室內(nèi)地圖構(gòu)造如圖3所示。為了表達該圖形，并能用于后續(xù)實驗，構(gòu)建了3種類型的數(shù)據(jù)表數(shù)據(jù)：節(jié)點表、連接線表和次區(qū)域表。其中，節(jié)點表和次區(qū)域表均有40條記錄，另外為了分別試驗Dijkstra和A*算法，建立了兩個連接線表，即Dijkstra連接線表的153條記錄和A*連接線表的1 818條記錄。主要的實驗步驟及結(jié)果如下。

2.3.1 實驗數(shù)據(jù)構(gòu)建

(1)非空間屬性數(shù)據(jù)存入數(shù)據(jù)庫表：屬性數(shù)據(jù)通過xsl電子表格，轉(zhuǎn)存為csv格式，最后通過PostgreSQL數(shù)據(jù)庫的import方式導入。

(2)空間數(shù)據(jù)采用PostGIS的空間操作更新函數(shù)存入數(shù)據(jù)庫表。

SQL語句:UPDATEedgeinfo SET geom = st—makeline(st—point(x1,y1),st—point(x2,y2));

(3)為了能夠進行最短路徑計算，必須用pgRouting的拓撲函數(shù)創(chuàng)建拓撲關(guān)系。

SQL語句:SELECT pgr—createTopology(’edgeinfo’,0.001);

2.3.2 Dijkstra最短路徑優(yōu)化算法實現(xiàn)

(1)給定任意起始點(15,5)和終點(5,35)，首先判斷它們分別所在的初始區(qū)域、結(jié)束區(qū)域。

SQL語句:select name from controlzone where st—covers(shape,st—makepoint(15,5));

結(jié)果:Z37

SQL語句:select name from controlzone where st—covers(shape,st—makepoint(5,35));

結(jié)果:Z13

(2)確定包含起點的次區(qū)域的初始節(jié)點和包含終點的次區(qū)域的結(jié)束節(jié)點

SQL語句:select id from vertexinfo where controlzone =’Z37’;

結(jié)果:1204或 (12,04)

SQL語句:select id from vertexinfo where controlzone =’Z13’;

結(jié)果:335或(3,35)

(3)初始節(jié)點與結(jié)束節(jié)點之間最短路徑(輔助路徑)的Dijkstra算法實現(xiàn)

SQL語句:SELECT* FROM pgr—dijkstra(’SELECT id,source,target,cost,reversecost FROM edgeinfo’,1204,335,FALSE);

輔助路徑要素結(jié)果如表2所示。

表2 輔助路徑要素結(jié)果

(4)確定起終點區(qū)域與輔助路徑的交點

起點所在的區(qū)域為Z37，與起點對應的連接線id為116；終點所在的區(qū)域為Z13，與終點對應的連接線id為37。同時，多邊形與線相交，結(jié)果會出現(xiàn)3種情況：(1)POINT，交點為正確結(jié)果；(2) MULTIPOINT，包含兩個交點，除去起終點的另一個結(jié)果；(3)LINGSTRING，一條線段，線段的開始結(jié)束點中除去起終點的另一個點。

SQL語句:select ST—AsText(ST—Intersection(ST—Intersection(e.geom,c.shape),ST—Difference(e.geom,c.shape))) from controlzone as c,edgeinfo as e where c.name=’Z37’ and e.id=116;

結(jié)果:POINT (15 4)

SQL語句:select ST—AsText(ST—Intersection(e.geom,ST—Boundary(c.shape) )) from controlzone as c,edgeinfo as ewhere c.name=’Z13’ and e.id=37;

結(jié)果:MULTIPOINT (1 34,3 35)

(5)最終得到1 505起點和535終點之間最短路徑結(jié)果，用WKT表示為LINESTRING (15 5,15 4,19 4,19 8,9 08,9 33,1 33,1 35,5 35)。其結(jié)果如表3和圖5所示。

表3 起點與終點之間的最短路徑結(jié)果

2.3.3 A*算法與未優(yōu)化的Dijkstra算法的最短路徑實現(xiàn)

(1)未優(yōu)化的Dijkstra算法最短路徑結(jié)果如圖5所示。

SQL語句:SELECT* FROM pgr—dijkstra (’SELECT id,source,target,cost,reversecost FROM edgeinfoall’,1505,535,FALSE)。

(2)A*算法的最短路徑結(jié)果如圖5所示。

圖5 3種算法的最短路徑結(jié)果

SQL語句:SELECT* FROM pgr—astar (’SELECT id,source,target,cost,reversecost,x1,y1,x2,y2 FROM edgeinfoall’,1505,535,directed:= false,heuristic:=2)。

在選定相同的網(wǎng)絡節(jié)點數(shù)、直連邊數(shù)條件下，Dijkstra優(yōu)化算法能夠靈活地得到精確的離散網(wǎng)格點之間的最短路徑，A*和原生的Dijkstra算法只能找到起終點對應區(qū)域的網(wǎng)絡節(jié)點間的最短路徑，路徑規(guī)劃的位置精度有限。若要使得A*和原生的Dijkstra算法得到起終網(wǎng)格點之間的最短路徑，則必須在其對應的起終點區(qū)域建立起所有鄰接網(wǎng)格的直連邊數(shù)據(jù)。由于起終點所處區(qū)域的不確定性，為此，實際上必須存儲整個定位區(qū)域的鄰接網(wǎng)格直連邊數(shù)據(jù)，這必將增加較大的數(shù)據(jù)量，這也極大地加大了存儲、增加耗時和最短路徑的計算復雜度，如表4所示。表中V為節(jié)點數(shù)，E為連接邊數(shù)。

表4 不同算法的計算復雜度表

從實驗結(jié)果可以看出，在用Dell Inspiron 13 7000 Series電腦計算條件下，相對于未優(yōu)化的Dijkstra算法與A*算法，優(yōu)化Dijkstra算法在室內(nèi)離散空間環(huán)境下對數(shù)據(jù)存儲和運算效率方面都有約90%的提升。

3 結(jié)語

近年來，室內(nèi)應用越來越廣泛，相應地，室內(nèi)定位與導航也愈發(fā)重要。本文針對室內(nèi)離散格網(wǎng)環(huán)境下的最短路徑規(guī)劃問題，依據(jù)室內(nèi)空間布局和障礙物分布，對定位區(qū)域進行次區(qū)域的劃分和地理編碼、網(wǎng)絡節(jié)點選擇等。通過對這些區(qū)域、節(jié)點等空間數(shù)據(jù)的有效組織管理，針對室內(nèi)離散格網(wǎng)空間環(huán)境下Dijkstra最短路徑算法進行了優(yōu)化設計。將次區(qū)域間與區(qū)域內(nèi)最短路徑分開處理，特別是起終點次區(qū)域內(nèi)尋找其與最短路徑的交點來代替次區(qū)域內(nèi)的網(wǎng)絡節(jié)點，最終得到一條綜合最優(yōu)的最短路徑。通過實驗數(shù)據(jù)顯示，優(yōu)化后的方法不僅可以得出正確的結(jié)果，而且還在空間數(shù)據(jù)存儲與計算復雜度方面有約90%的效率提升。由于現(xiàn)在還沒有辦法做到節(jié)點的自動識別提取，所以預設的環(huán)境比較規(guī)則，網(wǎng)絡節(jié)點的自動識別提取是后續(xù)努力探索的方向。