基于Android的校園導航系統(tǒng)路徑規(guī)劃的研究與應用

1、基于Android的校園導航系統(tǒng)路徑規(guī)劃的研究與應用摘要：以高校為研究對象，將數(shù)字校園與GPS手機導航系統(tǒng)相結(jié)合，利用移動GIS的先進性，在目前最流行的Android平臺下，結(jié)合ESRI推出的ArcGISAndroidAPI插件，設計了一款校園智能手機導航系統(tǒng)。以中北大學為例，完成了系統(tǒng)的架構設計，介紹了數(shù)據(jù)組織及系統(tǒng)的功能，經(jīng)過對比三種經(jīng)典的最短路徑算法后選擇采用Dijkstra算法來實現(xiàn)校園智能手機導航系統(tǒng)中最短路徑的選擇。該校園智能手機導航系統(tǒng)的實施，為校園新生及校外來訪人員提供了方便、快捷的智能導航服務。關鍵詞：GPS手機導航；移動GIS;ArcGISforAndroid;Dijkst

2、ra算法；最短路徑中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2014)06-1294-05ResearchandApplicationofCampusNavigationSystemPathPlanningBasedonAndroidWUQi1,LINJing1,YANGJiang-tao2,3(1.SchoolofComputerScienceandControlEngineering,NorthUniversityofChina,Taiyuan030051,China;2.ScienceandTechnologyonElectronicTestandMeasurem

3、entLaboratory,NorthUniversityofChina,Taiyuan030051,China;3.KeyLaboratoryofInstrumentationScience&DynamicMeasurementofMinistryofEducation,NorthUniversityofChina,Taiyuan030051,China)Abstract:RegardingcollegesanduniversitiesastheresearchobjectsandcombiningthedigitalcampuswithGPSmobilenavigationsystemas

4、martphonecampusnavigationsystemisdesignedbyusingthemobileGIS,AndroidplatformandESRIsArcGISAndroidAPIplug.TakingthecampusofTheNorthUniversityofChinaasanexample,thepaperrealizesthedesignofsystemarchitecturedescribesdataorganizationandthefunctionofsystem.Aftercomparingthreekindsofclassicalshortestpatha

5、lgorithms,theauthorsselectDijkstraalgorithmtoachievetheshortestpathselectioninthesmartphonecampusnavigationsystem.Theimplementationofthesystemprovidesaconvenient,fastandintelligentnavigationservicesforfreshmenandvisitors.Keywords：GPSmobilenavigation;mobileGIS;ArcGISforAndroid;Dijkstraalgorithm;short

6、estpath隨著高校校園的逐漸擴建以及對外交流的日益增多，來高校參觀、訪問的人也越來越多，但高校面積一般都很大，機構和重要建筑分布錯綜復雜，來訪者要經(jīng)過一番周折才能到達目的地。而且高校一般很少提供紙質(zhì)的地圖向來訪者提供導航服務，因此，建立具有校園信息查詢、智能導航服務等功能的系統(tǒng)，對高校提高人性化服務水平很有必要。目前，國內(nèi)高校對于基于PC的校園智能導航研究得比較多，如清華大學虛擬校園、華中科技大學校園導航系統(tǒng)。相比之下，大部分高校對Android系統(tǒng)上的校園導航都缺少研究，而今Android開發(fā)技術日新月異，將傳統(tǒng)PC機的導航系統(tǒng)用Android技術實現(xiàn)已成為可能。隨著移動通信的發(fā)展，手機

7、已經(jīng)不僅僅是解決通話的問題了，它漸漸成了集通信手持電腦于一體的移動計算工具，人們對手機所賦予的功能也已經(jīng)擴展到分布式計算、移動位置服務等更高端的領域。導航軟件在智能手機中的應用現(xiàn)已成為研究熱點之一，越來越多的互聯(lián)網(wǎng)應用被移植到智能手機中來，不但充分發(fā)揮數(shù)據(jù)業(yè)務運營商的潛力，而且極大的提高了用戶對手機多功能需求的滿意度，給人們的生活帶來了方便。本課題基于這種考慮，設計了一種基于Android的校園智能手機導航系統(tǒng)。采用Dijkstra算法并利用GIS系統(tǒng)的空間數(shù)據(jù)特性，根據(jù)實際情況對任意兩點間最短路徑進行規(guī)劃，在智能手機平臺上實現(xiàn)了優(yōu)化路徑選易于開發(fā)、管理和升既方便了新生和校外來擇，為新生和校外

8、來訪人員提供了非常便捷的服務。本系統(tǒng)實用性強,級，很好地解決了初次來學校的新生和校外來訪人員所遇到的問題，訪人員，又提高了學校的美譽度，具有很好的應用價值1。1系統(tǒng)開發(fā)理論基礎1.1系統(tǒng)背景介紹校園是大學生日?；顒拥闹饕臻g。大學校園通常具有面積大、開放性強、建筑布局分散、各類設施雜亂等特點，校園地理信息相對來說比較復雜。這給校園內(nèi)的每一個人尤其是對大一新生和校外來訪人員帶來諸多不便。因此，開發(fā)出一個為新生和校外來訪人員提供校園信息服務的智能手機導航系統(tǒng)十分必要2,3。1.2移動GIS技術地理信息系統(tǒng)（簡稱GIS）4是一種特定的十分重要的空間信息系統(tǒng)，是在計算機軟、硬件系統(tǒng)支持下，對整個或部分

9、地球表層（包括大氣層）的有關地理分布數(shù)據(jù)進行采集、存儲、管理、運算、分析、顯示和描述的技術系統(tǒng)。移動GIS5是GIS（地理信息系統(tǒng)）從靜態(tài)走向動態(tài)環(huán)境的重大發(fā)展，通過綜合運用GPS的精確定位技術、便攜移動設備（如掌上電腦、智能手機）、移動通信技術和GIS的空間信息處理能力，使野外工作者能夠利用該系統(tǒng)實時地獲取、存儲、更新、處理、分析和顯示地理信息。1.3ArcGISforAndroid介紹ArcGISforAndroid將GIS的適用范圍從辦公室擴展到移動Web。發(fā)布時，ArcGISforAndroid將包括一個應用程序，您將能夠從AndroidMarket應用商店下載這款稱為ArcGIS的應

10、用程序。這個應用程序類似于已經(jīng)發(fā)布的ArcGISforiOS和WindowsPhone應用程序。使用該ArcGIS應用程序，您能夠瀏覽ArcGIS.com或ArcGISServer提供的地圖，并且利用程序中提供的工具進行搜索，識別位置和要素，測量線和面，以及編輯6。2系統(tǒng)設計2.1 系統(tǒng)結(jié)構設計本系統(tǒng)的結(jié)構分為服務器端的搭建和客戶端軟件的開發(fā)。使用ArcGISServer在服務器計算機上搭建一套完整的地圖服務，能夠發(fā)布自己的地圖和隨時對地圖信息進行編輯?？蛻舳塑浖_發(fā)的功能有地圖顯示、地圖定位、位置搜索、選擇圖層、路徑導航等。系統(tǒng)功能結(jié)構圖如圖1所示。圖1系統(tǒng)功能結(jié)構圖2.2 數(shù)據(jù)庫設計1

11、）在圖層中創(chuàng)建一個線要素Road,用于表示地圖中的道路，再給該要素添加屬性，為了方便與最短路徑的計算，添加了道路的長度、限速值、行駛時間、端點信息等屬性，OBJECTID是自動生成的用于唯一標識一個要素，SHAPE是指要素的類型，這里是幾何類型，由于Road是線要素，所以系統(tǒng)也會自動生成SHAPE_LENGTH屬性，默認表示該線段的幾何長度，SpeedLimit和DriveTime都是自己另外添加的屬性，為計算最短路徑功能所用。如表1所示。2）為了實現(xiàn)智能導航系統(tǒng)的選擇圖層功能，再向圖層中添加一些生活常用的信息點，如醫(yī)院、停車場、電影院、美食、銀行、加油站、超市等，所以又添加了11個點要素：F

12、ood、Hospital、Shop、Park、KTV、Movie、Bank、Gas、Medicine、KFC、Mcdonald。每個要素各對應有自己的屬性表，由于他們都類似，下面只列出其中的一個表，如表2所示。表1道路信息表表2醫(yī)院信息表3核心問題和難點問題路徑導航功能是該系統(tǒng)最核心且最有難度的功能，路徑導航就是用戶設定一個起點（或以當前定位點為起點）和一個終點，系統(tǒng)采用一種最短路徑算法來通過計算求出所設起點到終點的最優(yōu)路徑。在空間決策模型中，實現(xiàn)行駛最優(yōu)路徑的規(guī)劃算法是空間決策的核心內(nèi)容。只有構建出最優(yōu)路徑模型，系統(tǒng)終端獲取的地理位置信息才能夠最迅速快捷地用到校園導航路線的選擇和優(yōu)化中。三種

13、最短路徑算法的比較與選擇本系統(tǒng)最核心的算法就是導航功能中的最短路徑選擇算法，為了選擇最適合于本系統(tǒng)的最短路徑算法，對常見的三種最短路徑算法進行分析和比較，歸納出這三種最短路徑算法的對比如表3所示。表3三種最短路徑算法對比表根據(jù)對比可以看出，Dijkstra算法在時間和空間上都是優(yōu)于Floyd算法和Bellman-Ford算法的。不足之處就是Dijkstra算法不能處理含負權邊的圖。但根據(jù)本系統(tǒng)的實際情況，地圖中的道路長度一定為正數(shù)，最短行駛時間也一定為正數(shù)，所以對于本系統(tǒng)來說，Dijkstra算法的這個缺陷可以忽略不計。因此，本系統(tǒng)選用Dijkstra算法來計算導航功能中的最短路徑問題。經(jīng)典D

14、ijkstra算法過程分析Dijkstra算法也是求單源最短路徑的算法，思想就是以源點s為中心，向外層層擴展，直到擴展到終點為止。算法思路如下7:1)初始化：設源點s的diss=0,除源點外的其他點disi=無窮大，同時把所有的結(jié)點的狀態(tài)都設為未擴展狀態(tài)；2)循環(huán)V次：在未擴展的點中取一個dis值最小的點i,把結(jié)點i標記為已擴展的，并對和點i相鄰的每一個點j進行松弛操作，即更新disj的值；3)算法結(jié)束后，對于任意的點i,disi就是源點s到結(jié)點i的最短距離。算法的偽代碼如下：ForeachvCV(G)dodisv=INF;diss=0;把結(jié)點都插入優(yōu)先隊列QwhileQ非空doi=Q.top

15、();把i標記為已擴展Foreachedge(i,j)doIfj未標記anddisjdisi+wi,jthendisjdisi+wi,j如果用普通的鄰接矩陣來存儲圖的結(jié)構，只能在每次循環(huán)里面再用一個循環(huán)來找出dis值最小的結(jié)點，那么時間復雜度將是O(V2)。所以為了優(yōu)化時間，可以使用優(yōu)先隊列來保存所有結(jié)點的dis值，優(yōu)先隊列的內(nèi)部實現(xiàn)一般都是使用二叉堆，所以建立和維護這個優(yōu)先隊列的時間復雜度是O(log|V|),所以Dijkstra算法的總時間復雜度是O(E+V*10gM),空間復雜度是O(V+E)。4系統(tǒng)功能及其實現(xiàn)系統(tǒng)主要功能我們要實現(xiàn)的是校園智能手機導航系統(tǒng)，服務的對象是入學不久的新生和

16、初到校園的校外來訪人員，所以此系統(tǒng)的設計應遵從界面直觀，功能鮮明，使用簡便”的原則，從而為新生和校外來訪人員了解校園環(huán)境提供便捷和幫助。系統(tǒng)具有的功能大致如下：1)數(shù)據(jù)的更改和刪除。由于高校校園逐漸擴建，校園地理環(huán)境不斷變化，對于已經(jīng)建成的校園導航系統(tǒng)，進行及時準確的更新十分必要。系統(tǒng)可以在數(shù)據(jù)庫中對現(xiàn)有的數(shù)據(jù)進行刪除、修改，從而實現(xiàn)對校園地圖和屬性的及時更新。2)數(shù)據(jù)的查詢和顯示。用戶可以通過輸入關鍵詞后在地圖上搜索地點。對于顯示在地圖窗口的地圖可以進行放大、縮小、漫游等操作，用戶還可以根據(jù)自己的需要及興趣點控制各個圖層的顯示，使查詢的信息更加明顯。3）空間分析查詢。打開客戶端軟件時，手機進

17、行實時GPS定位，獲取當前位置后在地圖上顯示位置坐標，并顯示附近的地圖信息?；凇癉ijkstra算法”的最短路徑導航功能還可以對任意兩點可以進行最短路徑的查詢和導航，這是系統(tǒng)最核心的功能，用戶通過輸入起點（或以當前定位點為起點）和終點可以迅速查詢出兩點間最短路徑，為新生和校外來訪人員提供了非常便捷及人性化的服務。性能測試分析GPS定位功能實現(xiàn)。在移動端采用坐標定位的方法，如果手機的GPS定位功能已開啟，地圖會自動定位，獲取到當前的坐標時，地圖控件會自動平移到當前的位置。界面如圖2所示。2）搜索地點功能實現(xiàn)。在搜索框中輸入關鍵詞地名，例如金虎超市”，點擊搜索按鈕，就會向服務器發(fā)送請求，若能找到

18、，則返回它的坐標，然后客戶端就在地圖中顯示一個藍色的點，表示搜索的位置。界面如圖3所示。3）選擇圖層功能實現(xiàn)?；谟脩襞d趣點選擇圖層，其中包含的圖層有：美食、醫(yī)院、超市、停車場、KTV、電影院、銀行、加油站、藥店等。用戶選擇感興趣的圖層后，可以在地圖上顯示對應的圖標。界面如圖4所示。4）路徑導航功能實現(xiàn)。采用Dijkstra算法實現(xiàn)最短路徑的選擇，當用戶設置起點（或以當前定位點為起點）和終點后地圖會在該兩點顯示標記，點擊導航按鈕后，地圖上就會顯示出從起點到終點的一條最優(yōu)路徑。界面如圖5和圖6所示。圖2GPS實時定位界面圖3關鍵詞搜索地點界面圖4興趣點選擇圖層界面圖5最短路徑導航界面（用戶設置起點）圖6最短路徑導航界面（以當前定位點為起點）5結(jié)束語校園智能手機導航系統(tǒng)的建立是校園數(shù)字化的一種體現(xiàn)，為學校日后建立綜合校園管理體系奠定了基礎。利用Dijkstra算法實現(xiàn)了最短路徑的選擇，獲得的最短路徑的屬性數(shù)據(jù)得以顯示，提供了及時且更直觀的校園導航系統(tǒng)的信息。通過測試，本系統(tǒng)起到了為新生報到和校外來訪人員提供指南導航的作用，提供了方便、快捷的智能導航服務信