前言：中文期刊網精心挑選了路徑規劃典型算法范文供你參考和學習，希望我們的參考范文能激發你的文章創作靈感，歡迎閱讀。
路徑規劃典型算法范文1
中圖分類號：TP306文獻標識碼：A文章編號：1009-3044(2008)21-30523-02
An Algorithm Based on Improved A* Restrictions on the Path to Search Regional Planning Approach
XU Zhan-peng, LIN Kai
(Qingdao Technical College Information Institute of Qingdao,Qingdao 266555,China)
Abstract: According to A* algorithm has been given an improved optimal path planning method, this algorithm in accordance with the actual situation of the road network of layered LO at the same time, according to the actual network topology of the region to search for reasonable Restrictions experiment proved that the algorithm in the path planning saving time
Key words: Path planning; Search region; A* algorithm
1 引言
路徑規劃是在車輛行駛前或行駛過程中尋找車輛從起始點到達目的地的最佳行車路線的過程[1], 它屬于智能交通
系統中的最短路徑問題的一個具體應用。
最短路徑規劃產生的路徑分為兩種：距離最短的路徑和時間最短路徑,其中前者相對比較易于實現，但是它容易忽略路徑的具體情況和行車實際環境以及人為因素。因為在實際車輛行駛中要求不但在此路徑上行車距離盡可能短，而且路徑的行車環境盡可能好，即盡量走道路較寬、路面質量較好、紅綠燈較少、紅綠燈設置間隔較大、車流量較小的路徑，避免走行車環境太差的路徑。作者針對最短路徑規劃存在的不足之處 ,根據已有A*算法，給出了一種改進的最優路徑規劃算法，此算法在根據道路的實際情況對路網進行分層的同時，根據實際路網的拓撲特性對搜索區域進行合理的限制。
2 A*算法
A*算法是人工智能中一種典型的啟發式搜索算法．也是路徑規劃算法中的常用算法，它通過選擇合適的估計函數，指導搜索朝著最有希望的方向前進．以期求得最優解限制搜索區域的多層最優路徑規劃算法，A*算法評價函數的定義為[2]：
f(n)=g(n)+h(n) （1）
f(n)是從初始點通過節點n 到達目標點的估價函數；
g(n)是在狀態空間中從初始節點到n節點的實際代價；
h(n)是從節點n到目標節點最佳路徑的估計代價。它決定了搜索的效率和可采納性。對于幾何路網來說，可以取兩點間歐氏距離（直線距離）作為估價值，即
其中，(xd,yd)、(xn,yn)分別為節點n 和目標節點在數字地圖中的坐標。由于估價值h(n)≤n 到目標節點的距離實際值，算法具有可采納性，能得到最優解。[3]
3 改進的A*算法球最短路徑
本文在三個方面對傳統的A*算法進行了更改：1)A*算法提到的權值會根據用戶的不同查詢條件來調用相對應的計算權值的公式；2) 添加了一個判斷過程。當查詢下一個臨近邊的時候首先查詢交通控制策略，判斷是否有管制信息并將相映的點從v中刪除；3) 減少路徑搜索的范圍，以出發點與目的地點連線的中間點為圓心，以兩點之間直線距離的二分之一再加上幾公里為半徑畫圓，在圓范圍內的路徑參加搜索，在圓范圍之外的路徑不參加搜索。
具體實現如下：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點，設各個點的權值（也稱為費用值）為g。遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,計算X的估價值[4]。
1)初始的OPEN表僅包含原節點．其費用值g為0，令CLOSED為空表，設其他節點的費用為∞ 。
2)若OPEN表為空．則宣告失?。悍駝t，選取OPEN表中所有的節點移至CLOSED表，將此CLOSED表作為新的OPEN表。重復第二步，直到深度達到4。
3)對第二步在深度4時形成的OPEN表進行操作，若OPEN表為空．則宣告失?。悍駝t，選取OPEN表中具有最小權值的節點，并叫做最佳節點NEXT．把NEXT從OPEN表移至CLOSED表．判斷此NEXT是否是一目標節點。若NEXT為目標節點．轉步驟3，若NEXT不是目標節點。則根據地圖數據庫包含的聯接路段屬性擴展并生成NEXT的后繼節點。對于每一個后繼節點n，進行下列過程：
①計算節點n的費用：g(n)= NEXT費用+從NEXT到n的費用
②如果n與OPEN表上的任一節點相同．判斷n是否具有最小的g值。若是最低的g值，用n的費用代替OPEN表中相同的節點費用。且建立匹配節點的后向指針指向NEXT
③如果n在CLOSED表中與一節點相匹配。檢查節點n是否具有最小的g值，如果n具有最小的g值，則用節點n的費用代替匹配節點的費用。并把匹配節點的后向指針指向NEXT。并把該匹配節點移到OPEN表
④如果n不在OPEN表。也不在CLOSED表上，則把n的后向指針指向NEXT。井把n放入OPEN表中。計算節點n的估價函數：f(n)=g(n)+h(n)
例如圖1，為帶權的有向圖。
根據步驟三，針對圖1，算法的具體實現如圖2。
4)重復第三步：
若在深度為7的搜索中找到目標結點且僅有一條路徑，則該路徑為最終路徑，返回；
若在若在深度為7的搜索中找到目標結點并且有多條路徑則回朔，比較找到的路徑費用，取權值最小的作為最終路徑；
若在在深度為7的搜索中未找到任何目標點則跳轉到第五步。
5)從深度為7的搜索中的所有的NEXT節點回朔，即從NEXT的后向指針一直到原節點遍歷節點，最后報告若干條路徑，比較個路徑費用，取費用最小的前100條路徑繼續重復第三步、第四步。由于h函數在滿足h下限得條件下，愈趨近于h效率愈高，因此實際應用中，我們取的是節點到目的點的直線距離保證滿足下限的情況下，盡可能的趨近h。
4 結語
實踐表明基于改進A*算法的限制搜索區域的路徑規劃方法不僅在進行路徑規劃時節省了時間，而且規劃后的路徑大部分道路位于高層路網上，路徑長度與最短路徑長度之比小于1.1,可以被人接受，是行車意義上的最優路徑。
參考文獻：
[1] 付夢印.限制搜索區域的距離最短路徑規劃算法[J].北京理工大學學報,2004(10).
[2] 趙亦林.車輛定位與導航系統[M].北京:電子工業出版社,1999:1-7.
[3] 王亞文.智能交通系統中路徑規劃算法研究與系統設計[D].陜西師范大學,2007.
路徑規劃典型算法范文2
關鍵詞:移動多智能體;全局規劃;局部規劃
中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2010)16-4487-03
Research on Path Planning for Mobile Multi-Agent
CHEN Cui-li, GAO Zhen-wei
(Henan Normal University, Xinxiang 453007,China)
Abstract: A path planning method based on both the benefits of global and local path planners is proposed for mobile Multi-Agent path planning in dynamic and unstructured environments. The global path planner uses A*algorithm to generate a series of sub-goal nodes to the target node, and the local path planner adopts an improved potential field method to smooth and optimize the path between the adjacent sub goal nodes. Taking into full consideration the kinematical constraints of the mobile robot, this method cannot only effectively generate a global optimal path using the known information, but also handle the stochastic obstacle information in time. and is simulated on simulation platform developed by using Visual Studio 2005 software, simulation result presents the validity and utility of the algorithm.
Key words: mobile Multi-Agent; global path; local path
在移動智能體相關技術研究中,路徑規劃技術是一個重要研究領域。移動智能體路徑規劃問題是指在有障礙的環境中,尋找一條智能體從起始點到目標點的運動路徑,使智能體在運動過程中安全、無碰撞地繞過所有的障礙物。這不同于用動態規劃等方法求得最短路徑,而是指移動智能體能對靜態及動態環境下做出綜合性判斷,進行智能決策。在以往的研究中,移動智能體路徑規劃方法大體上可以分為三種類型:其一是基于環境模型的路徑規劃,它能處理完全已知的環境下的路路徑規劃。而當環境變化時(出現移動障礙物)時,此方法效果較差,具體方法有:A*方法、可視圖法、柵格化和拓撲圖法等;其二是基于傳感器信息的局部路徑規劃方法,其具體的方法有:人工勢場法、模糊邏輯法和遺傳算法等;其三是基于行為的導航行為單元,如跟蹤和避碰等,這些單元彼此協調工作,完成總體導航任務。隨著計算機、傳感器及控制技術的發展,特別是各種新算法不斷涌現,移動機器人路徑規劃技術已經取得了豐碩研究成果。
一個好的路徑規劃方法需要滿足如下性能[1]:合理性、完備性、最優性、適時、環境變化適應性和滿足約束。有些方法沒有高深的理論,但計算簡單,實時性、安全性好,就有存在的空間。如何使性能指標更好是各種算法研究的一個重要方向。
在未知的(或部分已知的),動態的非結構的環境下,多智能體利用傳統的路徑規劃方法很難滿足前面的性能要求,本文提出了一種將全局路徑規劃方法和局部規劃方法相結合,將基于反應的行為規劃和基于慎思的行為規劃相結合的路徑規劃方法,其思路如下:多智能體分別采用A*算法進行全局路徑規劃,各自生成到達目標點的子目錄節點序列,同時采用改進的人工勢能對子目錄節點序列中相鄰節點進行路徑的平滑和優化處理,該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規劃的性能。
1 路徑規劃方法
1.1 相關研究
1) A*算法
在最佳優先搜索的研究中,最廣范圍應有的方法為A*搜索,其基本思想[2]是:它把到達節點的代價g(n)和從該節點到目標節點的代價h(n)結合起來對節點進行評價:f(n) = g(n) + h(n)(1)。A*算法用于移動多智能體的路徑規劃時,多智能體分別按照已知的地圖規劃出一條路徑,然后沿著這條生成路徑運動,但智能體傳感探測到的環境信息和原來的環境信息不一致時,智能體重新規劃從當前位置到目標點的路徑。如此循環直至智能體到達目標點或者發現目標點不可達[3]。重新規劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且由于采用A*方法規劃出的最優路徑并沒有考慮到機器人的運動學約束,即使機器人可以采用A*方法規劃出一條最優路徑,機器人也未必可以沿著這條路徑運動。
2) 人工勢能法
人工勢能法由 Khatib 提出的一種虛擬力法[4]。人工勢場方法結構簡單,便于低層的實時控制,在實時避障和平滑的軌跡控制方面得到了廣泛的應用,但根據人工勢場方法原理可知,引力勢場的范圍比較大,而斥力的作用范圍只能局部的,當智能體和障礙物超過障礙物影響范圍的時候,智能體就不受來自障礙物引起的排斥勢場的影響。所以,勢場法只能解決局部空間的避障問題,他缺乏所在的全局信息,,這樣就造成產生局部最優解不能進行整體規劃,智能于局部最小點的時候,智能體容易產生振蕩和停滯不前。
1.2 路徑規劃方法描述
鑒于A*算法全局路徑搜索的全局性與改進人工勢場算法局部路徑搜索的靈活性,通過一定的方法把兩者結合起來,其思路如下:多智能體分別采用A*算法進行全局路徑規劃,各自生成到達目標點的子目錄節點序列,同時采用改進的人工勢能對子目錄節點序列中相鄰節點進行路徑的平滑和優化處理,該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規劃的性能。由于A*方法采用柵格表示地圖,柵格粒度越小,障礙物的表示也就越精確,但是同時算法搜索的范圍會按指數增加。采用改進人工勢場的局部路徑規劃方法對A*方法進行優化,可以有效增大A*方法的柵格粒度,達到降低A*方法運算量的目的。
2 環境構造
目前主要有三種比較典型的環境建模方法:構型空間法、自由空間法和柵格法,本文仿真實驗采用的環境建模方法是柵格法,柵格法將機器人路徑規劃的環境劃分成二維網格,每格為一個單元,并假設障礙的位置和大小已知,且在機器人運動過程中不會發生變化。柵格法中的網格單元共有三種類型,即障礙網格、自由網格和機器人所在網格。目前常用的柵格表示方法有兩種,即直角坐標法和序號法。這兩種表示方法本質上是一樣的,每個單元格都與(x, y)一一對應。本文采用序號法表示柵格,設柵格的中心點坐標為柵格的直角坐標,則每個柵格編號都與其直角坐標一一對應,地圖中任意一點(x,y)與柵格編號N的映射關系為:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x軸的取值范圍,Gs表示柵格尺寸的大小,INT函數表示取整,而柵格中心點的坐標為(xG,yG),它與柵格編號N之間的關系為:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符號%表示取余操作。本文中根據機器人的尺寸來確定柵格的粒度,假設一個柵格能容納一個智能體,這里選擇柵格的大小為40cm×40cm[5]。本文的仿真環境為800cm×800cm,柵格號N=0~399,機器人的初始位置的柵格號為N=42,目標位置的柵格號為N=314。在Visual Studio 2005中進行仿真,仿真結果如圖1所示,長方形和橢圓圖形代表障礙物柵格,小圓圈所代表的柵格為機器人的起始柵格和目標柵格,剩下的是自由柵格。在路徑規劃中機器人可以選擇自由柵格作為它的路徑點。
建立柵格后,對柵格進行初始化。設置變量G_Obstacle為0表示自由柵格,G_Obstacle為1表示障礙網格包括機器人柵格。若障礙物或智能體占當前位置柵格面積大于1/3則設置變量G_Obstacle為1.
3 數據的采集
對于簡單地形,我們將實際地形就行考察并進行測量、量化,轉化為平面坐標數據最后轉換相應的柵格編號。對于復雜地形在沒有航攝資料的情況下,本實驗以地圖為數據源的DTM數據獲取方法在,可利用已有的地形圖采集地形數據,用手扶跟蹤式數字化儀將平面圖形轉化為平面坐標數據,最后轉換相應的柵格編號。
4 實現過程
第1步:對環境信息進行數據采集并轉化成相應的平面坐標數據。
第2步:確定各個智能體的初始位置和目標位置。
第3步:建立柵格,對柵格進行初始化。
第4步:智能體S(i)首先根據已知信息規劃出各自的一條目標序列S(i)n。
第5步:智能體S(i)利用測試傳感器探測到臨界危險區L范圍內的信息與原有信息是否一致,當智能體利用傳感器探測到臨界危險區L范圍內的信息與原有信息一致時,利用改進后的人工勢能算法搜索相鄰目標點之間的軌跡,否則智能體搜索從當前序列點S(i)n到S(i)n+4路徑。定義臨界危險區L、目標序列點S(i)n(n>=1)。
第6步:智能體一旦移動到達目標柵格,則程序終止;否則返回第5步。系統的工作流程如圖2所示。
5 仿真結果及結論
在Visual Studio 2005平臺上進行了仿真,,首先根據已知環境信息,進行數據采集量化并進行柵格化處理,設置障礙和智能體的大小及位置(為了簡單化,本實驗所有障礙都設置為圓形),再進行初始化操作,采用0、1二元信息數組存儲柵格化的地形。
智能體運用A*算法進行全局路徑規劃,圖3顯示兩個智能體的運動過程,顯然兩個智能體的路徑相交可能會發生碰撞,智能體為了避免碰撞應重新規劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且顯然只用A*算法規劃出二維路徑點序列,相鄰兩點之間的夾角一定是π/4的整倍數,機器人很難按照所生成的序列點運動。智能體采用改進后的人工勢場進行目標序列點之間的局部路徑規劃,圖4顯示智能體的運動過程。顯然智能體的整條運動軌跡顯得比較平滑同時又實現實時避障的目的。
6 總結
本文對多智能體在動態環境下路徑規劃技術進行了研究探索,提出了一種能夠將全局路徑規劃方法和局部路徑規劃方法相結合,通過仿真取得了很好的結果,證明A*和人工勢場算法的結合可行。
參考文獻:
[1] 劉華軍,楊靜宇,陸建峰,等.移動機器人運動規劃研究綜述[J].中國工程科學,2006,8(1):85-94.
[2] Nilsson N J. Princip les of Artificial Intelligence[M].Berlin, Ger2 many: Sp ringer,1980.
路徑規劃典型算法范文3
關鍵詞： B樣條曲線； 無人車； 路徑規劃； 碰撞檢測； 最大曲率約束； 最優路徑
中圖分類號：TP181 文獻標識碼：A 文章編號：1009-3044（2016）26-0235-03
B-spline Curve based Trajectory Planning for Autonomous Vehicles
QU Pan-rang，LI Lin ， REN Xiao-kun ，JING Li-xiong
（Institute of Aeronautics Computing Technique Research， Xi’an 710065， China）
Abstract：Path planning is an important research topic in the field of the unmanned vehicle motion planning， and it directly affects the performance of unmanned vehicles in a complex traffic environment. Taking the requirement for smoothness into account， this paper proposed a method based on B-spline curve and built a planning model which can be divided into four steps， including path clusters， constraint of maximal curvature， collision detection and optimal path. This method works efficiently and simulation results show efficiency of the method.
Key words：B-spline curve； autonomous vehicle； path planning； collide detection； constraint of maximal curvature
1 引言
近年來，無人駕駛技術備受關注，各大研究機構和企業爭相推出各自的無人駕駛平臺。無人車作為未來智能交通的主要主體也逐漸融入到我們的日常生活中，比如自主巡航[1]和自動泊車等等。然而，為了使其更好地服務于我們，需要進一步提高其智能化水平，而路徑規劃作為連接環境感知和運動規劃的橋梁，是無人車智能化水平的重要體現[2]。
由于受到自身動力學和運動學模型的約束，車輛的路徑規劃問題除過要嚴格滿足端點狀態約束之外，還要求其中間狀態滿足運動系統的微分約束。由于實現簡單，并且高階多項式曲線能夠很好地滿足運動系統的微分約束，生成高階平滑的路徑，所以很多路徑規劃系統選擇使用基于多項式曲線的方法生成路徑。B樣條曲線是一種典型的多項式曲線，且因為其所有的中間狀態均是由控制點加權生成，所以其能夠完全滿足端點狀態約束。綜合考慮無人車路徑規劃的要求和實現復雜度，在僅已知初始位姿和目標位姿的情況下，本文選擇B樣條曲線生成路徑，重點講述分步規劃模型，即路徑簇生成、最大曲率約束、碰撞檢測以及最優評價四個過程，并通過Matlab仿真對本文方法進行了驗證。
2 問題描述
本節分別描述了無人車路徑規劃問題和B樣條曲線。
2.1 路徑規劃問題描述
路徑規劃得到的是一條從初始位置到目標位置的路徑，即二維平面內一條從初始位置點到目標位置點的曲線，曲線上的每一個點表示車在行駛過程中的一個狀態?？紤]到實現方便，本文將路徑描述成離散點序列[Sstart，S1，???，Sn，Sgoal]，如圖1所示，序列中每一個點[Si（xi，yi，θi）]表示車的一個狀態，其中[（xi，yi）]表示此時刻車輛的位置，[θi]表示車輛的航向，[Sstart]和[Sgoal]分別表示車輛的初始狀態和目標狀態。圖1中的圓[（xobs1，yobs1，robs1）]表示環境中的障礙物，[（xobs1，yobs1）]表示障礙物的位置信息，[robs1]表示障礙物的半徑。
2.2 B樣條曲線
如果給定[m+n+1]個控制點[Pi（i=0，1，???，m+n）]，就可以構造[m+1]段[n]次B樣條曲線，其可以表示為公式1：
[Pi，n（t）=k=0nPi+k?Fk，n（t） ，t∈[0，1]Fk，n（t）=1n！j=0n-k（-1）j?Cjn+1?（t+n-k-j）n ， t∈[0，1] ， k∈0，1，???，n] （1）
其中，[Pi，n（t）]表示第[i]個[n]次B樣條曲線片段，[n]表示B樣條曲線的次數，[t]為控制參數，其取值范圍為[[0，1]]，[Pi+k]為控制點，[Fk，n（t）]為B樣條基。依次連接全部[n]階B樣條曲線段就組成了整條B樣條曲線。
3 本文算法
本節重點講述基于B樣條曲線的路徑規劃方法和基于該方法生成路徑的過程。
3.1 基于B樣條曲線的路徑規劃方法
選擇三階B樣條曲線生成幾何路徑，即每四個控制點生成一個路徑片段，然后通過片段的拼接就可以實現從初始狀態到目標狀態的路徑規劃，下面著重講述基于六控制點的三階B樣條曲線生成滿足車輛端點位姿約束路徑的方法，如圖2所示。
l 依據初始狀態選擇控制點[P0，P1，P2]。當[P0，P1，P2]三個控制點共線，并且[P1]為線段[P0P2]的中點時，生成的B樣條曲線與線段[P0P2]相切于點[P1]。所以選擇無人車的初始位置為控制點[P1]，將控制點[P0]和[P2]選在初始航向角[θstart]所在直線上，并關于控制點[P1]對稱。如是，即能滿足車輛的初始位姿約束；
l 依據目標狀態選擇控制點[P3，P4，P5]。當[P3，P4，P5]三個控制點共線，并且[P4]為線段[P3P5]的中點時，生成的B樣條曲線與線段[P3P5]相切與點[P4]。所以選擇無人車的目標位置為控制點[P3]，將控制點[P3]和[P5]選在目標航向角[θgoal]所在的直線上，并關于控制點[P3]對稱。如是，即能滿足車輛的目標位姿約束。
（a） 路徑簇
（b） 最大曲率約束
（c） 碰撞檢測
3.2 分步路徑規劃
本小節將以圖3所給定的場景為例，講述最優路徑生成的過程。
3.2.1 路徑簇生成
在選定控制點[P1]和[P4]之后，通過選擇不同的控制點[P2]和[P3]，從而得到多組控制點，進而得到多條路徑。將控制點選擇的極限定為線段[P1P2]、[P3P4]與[P1P4]相等，但是[P1P2]和[P3P4]不能出現交叉。將這個范圍等間隔量化，各取四個點，共組成16組控制點，得到16條路徑，如圖3（a）中的藍色曲線所示。
3.2.3 最大曲率約束
理論上，車輛的最小轉彎半徑[Rmin=Lsin（θmax）]是其本身屬性[3]，只取決于車輛的軸距[L]和最大前輪轉角[θmax]。那么，車輛可行駛路徑的最大曲率[κmax=1Rmin]也是固定的，假設無人車可行駛路徑的最大曲率[κmax=16]，以此為約束條件，在路徑簇中選擇滿足最大曲率約束的路徑，如圖3（b）所示，圖中綠色曲線表示不滿足最大曲率約束的路徑。
3.2.4 碰撞檢測
碰撞檢測的目的是保證車輛在規劃路徑上行駛而不與障礙物發生碰撞。采取的碰撞檢測的方法很簡單，因為環境中的障礙物采用圓來描述，所以只要判斷路徑上每一點到圓心的距離與障礙物半徑的關系，就能確定其是否發生碰撞。由兩點間距離公式：
[d=（x1-x2）2+（y1-y2）2] （2）
如果[d]大于障礙物半徑，則不發生碰撞；如果[d]小于障礙物半徑，則發生碰撞。圖3（c）中的藍色曲線表示既滿足最大曲率約束，又不與障礙物碰撞的路徑。
3.2.2 最優路徑
路徑要求的側重點不同，優化的目標函數也可以有多種選擇，常用的目標函數有最短和最平滑等。其中，路徑最短可以抽象成優化問題：
[traoptimal=arg mintraids] （3）
路徑最平滑可以抽象成優化問題：
[traoptimal=arg mintraiκ2] （4）
式中，[traoptimal]為最優路徑，[traids]為第[i]條路徑的長度，[traiκ2]為第[i]條路徑上所有點處的曲率平方之和。圖3（d）中的紅色曲線即為得到的最短可行駛路徑。
如是，就能得到滿足車輛運動學約束，并且無碰撞的最優路徑。
4 結論
本文選擇使用B樣條曲線解決無人車路徑規劃問題，并建立了基于B樣條曲線的分步規劃模型。仿真結果表明，使用基于B樣條曲線的路徑規劃方法能夠很好地解決簡單障礙物場景中無人車的路徑規劃問題，并且因為路徑生成過程簡單，所以該方法常常表現得十分高效，能夠完全滿足無人車路徑規劃系統對算法實時性的要求。
參考文獻：
[1] Vahidi A， Eskandarian A. Research advances in intelligent collision avoidance and adaptive cruise control [J]. IEEE Transactions on Intelligent Transportation Systems， 2003， 4（3）：143-153.
路徑規劃典型算法范文4
中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2012)12-2708-03
當下，隨著我國互聯網業務開展的類型越來越多樣化，互聯網應用的規模也隨之擴大，因此互聯網技術需要不斷地發展變化才能適應新興互聯網業務發展的需要。以往的網絡運營與建設模式將逐漸不能夠滿足新形勢下網絡融合的需求，新的應用模式與網絡協議不斷出現，網絡虛擬化就是在這種形勢下產生的。網絡虛擬化主要通過抽象、分配及隔離機制實現在一個物理網絡上獨立運營多個虛擬網絡，以有選擇性地開展資源的調度與分配，從而實現物理網絡資源利用率的最大化，同時提高網絡服務的質量并降低維護與運營成本。該文就網絡虛擬化技術中的虛擬網映射問題及其研究現狀問題主要介紹了以下幾個方面的內容。
1網絡虛擬化及分層服務提供模型概述
作為一種有效應對克服當下互聯網剛性問題的方法及技術手段，網絡虛擬化技術可以被看作是互聯網這幾年發展與革新的主要趨勢。網絡虛擬化思想主要是將互聯網劃分成多個虛擬網絡，實現互聯網架構的多樣化，每個虛擬網絡都可以享用同樣底層的物理網絡資源，但能夠實現不同的服務、應用于架構，這樣就能達到多樣化技術的應用與部署的目的。虛擬網絡由虛鏈路連接的虛節點組成，并且虛節點與虛鏈路都處于物理網絡的映射中。虛擬網絡映射通過為不同需求的虛擬網絡分配對應的物理資源來實現網絡虛擬化，虛擬網絡映射作為虛擬網絡的基礎還包括鏈路資源與節點資源。合理科學的映射算法既可以實現虛擬網的高效映射，也可以使物理網承載更多的虛擬網。
在網絡虛擬化的服務環境中，主要應用分層的模式，通過建構虛擬網來實現各種業務服務。分層模型主要有三層，即應用層模式、服務層模式和資源層模式三層。在三層模式下，每一層的結構與功能彼此影響。SP（服務提供商）主要通過InP（基礎設施提供商）提供的借口來管理虛擬網，并能夠接入終端用戶的虛擬網。在網絡虛擬化的服務環境中，終端用戶及傳統的互聯網終端用戶一樣，只是在虛擬化服務的環境中，每一個終端用戶可以通過映射的方式來和多個SP同時建立不同的連接，從而來實現隨不同的業務需求獲得不同服務的目的。網絡虛擬化分層服務所提供的模型如下（圖1）所示。
2虛擬網映射問題與研究現狀分析
作為構建虛擬網的一個比較重要的過程，虛擬網映射是映射較核心的功能。虛擬網映射主要依據SP的構建需求結合InP的資源狀況，通過一定的映射算法在網絡資源與構建需求間進行匹配，獲取較科學合理的分配方案以進行嵌入，從而形成虛擬網。所以，在虛擬網映射過程中，映射主要實現的三大功能分別是接受并描述InP的資源信息、SP的虛擬網構建請求以及執行映射算法。在此，筆者就虛擬網映射與研究現狀問題主要分析了以下幾點內容。
1）網絡資源概述。對InP的網絡信息資源一般能夠通過INSADL、NDI、NML等來描述。在對網絡資源的描述過程中，任一網絡元素就可以代表一個基本組件，例如鏈路、路徑、節點和接口等。每一網絡元素還有一個與之相對應的標示符、功能性或者非功能性屬性、可用性參數。功能屬性主要決定其屬性、特征和網絡元素的具體功能，非功能屬性則主要決定了在虛擬網絡中各個網絡元素的限制及應滿足的標準。節點可分為虛擬節點與物理節點兩種，物理節點包含多個虛擬節點，同時一個物理或者虛擬節點可以擁有多個物理或者虛擬接口。其中接口的類型主要包括ATM接口、以太網接口及無線接口等。由于一個物理鏈路就可以支持一個或多個虛擬鏈路，因此每一個物理鏈路包含QoS參數及連接類型兩個附加特征。
2）虛擬網的構建需求描述。虛擬網的構建需求與物理網絡規劃的需求很相似，主要關注的是網絡拓撲結構、虛鏈路的帶寬、虛節點的位置、路徑的跳數限制、端口的類型以及QoS參數的配置等。虛擬網的構建與拆除，實質上主要是依據業務的需求對物理網絡資源進行動態的分配和釋放的過程。因此，虛擬網運行的生命周期也是虛擬網在構建需求上的主要參數。
3）虛擬網映射問題模型的描述。對于虛擬網的構建需求中操作系統OS及端口port類型等需求完全可以通過在映射前預先篩選InP所提供的各類資源。虛擬網映射問題的難點是怎樣最大程度地實現InP利益。因為虛擬網映射要滿足虛擬網構建需求中各個鏈路和節點資源的要求，而且還要充分地、高效地應用物理網絡資源，達到在有限的物理網絡資源上形成更多虛擬網，最大程度實現InP利益的目標。但是，虛擬網的物理網絡資源有一自身的局限性、虛擬網的構建必須要求呈現出多樣化的個性特征和虛擬網的構建請求動態化、即時處理化等特征。這樣，虛擬網的映射問題實際的應用中還面對很對急需解決的問題與挑戰。
4）映射算法中的各項評價指標。虛擬網映射算法要通過有效地采用提供商所提供的物理網絡資源來滿足服務提供商提出的構建要求。同時，映射算法的各項評價指標必須要通過網絡資源利用率及虛擬網映射成功率等指標的計算來科學衡量。虛擬網映射的成功率是在構建申請中映射成功的虛擬網數，提高虛擬網的映射成功率就是要提高映射成功的虛擬網數。而提高物理網絡資源利用率，關鍵在于如何在滿足當下構建需求的前提下，更合理地為后續的虛擬網構建提供資源分布空間，為后續虛擬網的構建提供便利。
5）映射算法研究現狀。目前來看，資源分布相對較均衡的物理網絡逐漸成為虛擬網映射問題研究的方向。因為這樣的物理網絡可以提高網絡資源的利用率和虛擬網構建的成功率。所以，當下對于映射算法的研究現狀主要有以下幾種情況：（1）Yong Zhu等研究人員把互聯網資源假定為無限的，因此在構建虛擬網時，要綜合考慮滿足各個構建的具體要求，以便最大化的實現預定目標以最小化的鏈路承受最大量的負荷。（2）Robert Ricci等研究人員則通過避開物理網絡中的各種瓶頸鏈路的方式來映射虛鏈路，不斷提高虛擬網構建的成功率。（3）Jens Lischka等研究人員利用子圖同構檢測和回溯的技術把虛鏈路及虛節點同步映射到物理網絡中，以此來提高構建虛擬網的成功率。（4）在虛擬網的映射中，一種W szeto基于多商品流問題而提出的對資源進行預分配的方法技術逐漸被提出來，該方式采用線性規劃的方法來對映射問題進行建模求解。這種基于多商品流問題的模型很好地地解決了映射中資源分布均衡性的問題。（5）另外，MinlanYu等人提出了多徑映射來提高網絡資源的利用率。通過多徑映射將虛擬鏈路映射到多條物理路徑上，以此來提高物理網絡的負載均衡，并利用多商品流問題的形式建模進行求解。多徑映射法與多商品流問題模型的并用可以有效地解決映射中資源分布不均衡的問題，但是難以達到路徑跳數的限制，所以一般只能通過單徑映射的辦法滿足業務要求并有延時約束的構建需求。
3虛擬網絡映射算法PBMC
1）PBMC算法的設計思路。眾所周知，基于多商品流問題模型的虛擬網映射方法不能夠解決路徑跳數的約束要求問題，因此在多徑映射時，虛鏈路的帶寬很難通過路徑的路徑跳數來確定分配比。因此，在此基礎上該文提出PBMC算法，即基于路徑集多商品流問題模型的虛擬網映射算法。這種算法主要采用基于有效路徑集的多商品流問題模型來規劃和求解虛擬網映射問題的。在PBMC算法中，首先要結合各個物理鏈路的帶寬需求和路徑跳數的限制條件來計算出有效的物理路徑集合。其次將路徑的可用帶寬視為決策變量，在符合虛鏈路帶寬要求的前提下，運用多徑映射的思想建立相應的數學規劃，同時采用啟發式的算法進行建模求解，最后實現鏈路的最大負載強度最小化。
2）建立數學規劃。鏈路負載強度是鏈路上已占用帶寬與鏈路帶寬容量之比。PBMC算法的規劃目標是建立鏈路的最大負載強度最小化。PBMC算法的約束條件有三個，分別為物理鏈路帶寬容量約束、虛鏈路帶寬需求約束及帶寬占用的正則性要求約束等。
3）模型求解。在PBMC算法中，主要通過采用設計啟發式的算法來求得近似最優解的方式進行求解。算法主要分為部分，首先要求證出初始的可行解；其次，對初始可行解迭代從而求解出近似最優解。在這種算法中，更多的考慮了局部的均衡問題，沒有對整個虛擬網映射范圍進行綜合考慮，因此還需要做進一步的優化工作，對初始可行解進行優化。優化的思想主要是找出最大負載強度的鏈路，將該鏈路路徑上的虛擬網遷移到其他的路徑上，以此來降低鏈路的負載強度。
4）仿真實驗。為了很好地與基于單徑映射多商品流問題模型算法對比，可以采用基于Matlab的方式對PBMC算法進行仿真與模擬實驗。在實驗中，對虛擬網鏈路的帶寬、構建請求的虛節點數、虛鏈路的帶寬需求、跳數的限制、虛擬網申請的時間間隔均值以及生命周期均值等進行適當的設置。仿真實驗中，要對比和分析的指標除了有構建成功率、資源、利用率外，還含有運營商收益及資源分布的均衡性兩個指標。
5）仿真結果分析。
仿真實驗中，將物理網絡鏈路負荷的標準差、虛擬網構建的成功率、網絡資源的利用率、物理網絡運營商所收取的收益等進行綜合分析，我們可以發現：基于單徑映射多商品流問題模型算法，通過PBMC算法可以使得物理網絡上各鏈路負載強度的標準差更小，因此物理網絡資源的分布均衡性將得到更好的優化與實現。并且，通過更高的資源利用率及構建成功率，物理網絡運營商才可以獲得更多的收益。所以，本次仿真實驗結果也說明相對于基于單徑映射多商品流問題模型算法來說，PBMC算法不僅可以滿足帶路徑跳數限制約束的虛擬網構建需求，還可以最大程度的優化網絡資源分布的均衡性問題，不斷提高網絡資源的利用率。
4結束語
目前，網絡虛擬化技術已經成為解決當下互聯網僵化等問題的有效技術途徑。在網絡虛擬化技術中，虛擬網的映射實現網絡虛擬化的基礎。雖然對于網絡虛擬化技術中的虛擬網映射問題國內外已經有了很大的突破，取得了較大的成績，但在實際的運用過程中，仍然會出現這樣那樣的問題。因此，我們還需要不斷引進新技術新方法，不斷研究新的技術手段，更好地實現物理網絡資源分布的均衡性，進一步提高網絡資源的使用效率。
參考文獻：
[1]汪斌強,鄔江興.下一代互聯網的發展趨勢及相應對策分析[J].信息工程大學學報,2009（10）.
[2]李文,吳春明,陳鍵,平玲娣.節點可重復映射和鏈路可分流的虛擬網映射算法[J].研究與開發.2010（7）.
[3]呂博.網絡虛擬化資源管理架構與映射算法研究[D].北京郵電大學,2011.
路徑規劃典型算法范文5
【關鍵詞】Dijkstra算法 矩陣迭代算法 交通 阻抗
1 引言
隨著我國經濟發展越來越快，城市交通運輸路徑也日趨緊張，在我國大中型城市中，普遍存在公共交通結構的不合理狀況[1-4]。城市公共交通網絡由眾多路徑及網絡節點構成。由于城市人口和城市規模的不斷增長，優化交通運輸路徑，解決交通出行者出行時間最小、服務最大化、線網效率最大等，方便居民出行[5-7]。在城市交通嚴重堵塞時，要使交通出行者出行便利，則必須對最短交通路徑及交通狀態信息進行實時全面了解；在一定程度上，這種信息誘導作用能對重點道路的擁堵起到緩解作用[8]。最短路徑的算法有多種，對各種算法進行分析、理解、應用，比較這些算法的在實際應用效率，具有非常重要的實用意義[9-11]。通常情況下，典型最短路徑問題算法有兩種，分別為矩陣迭代算法、Dijkstra算法。本文基于這兩種典型算法，對兩者在最短路徑問題中的差異性進行了對比，方便交通出行者對交通運輸路徑的選擇。
2 最短路徑及路網阻抗
在交通流分配中，最基本的算法就是最短路徑算法。最短路徑是指在一個網絡中，已知相鄰節點間的線路長度，要在某一起點到某一終點間找出一條長度最短的路線。在交通領域，最短路徑研究較多，在路網中，因受道路條件、道路繞行距離、交通條件影響，使得不同交通路徑，所需交通費用有一定的差異。在廣義上，交通費用包括道路通行時間、通行距離、燃料的使用等；在狹義上，道路通行時間是阻抗，或將影響出行的其它因素進行折算，轉化成通行時間，將其作為道路網交通阻抗，交通阻抗最小的路徑就是最短路徑。圖1為路網的阻抗，表1為道路的可用阻抗矩陣。
3 Dijkstra算法和矩陣迭代算法
3.1 Dijkstra算法
最短路徑使用最廣泛、最基本的算法就是Dijkstra算法，在求網絡中某一節點到其他各節點的最短路徑時，網絡中的節點被Dijkstra算法分成三部分，分別為最短路徑節點、臨時標記節點、未標記節點。在算法開始時，源點經初始化，轉為最短路徑節點，其他節點則為未標記節點。在執行算法時，從最短路徑節點擴展到相鄰節點，非最短路徑節點的相鄰節點每次都要修改為臨時標記節點，對權值是否更新進行判斷，權值最小節點從全部的臨時標記節點中提取，在修改為最短路徑節點后，將其作為下次擴展源，重復前面步驟，在全部的節點做過擴展源后，結束算法。
Dijkstra算法屬于比較經典的最短路徑算法，它可對一點到網絡內所有節點最小阻抗進行計算，并將相應最短路徑推算出。Dijkstra算法計算步驟共5步，第一步是將Dijkstra算法起始點進行標號，記為P，且P（o）=0，其余節點標號為T，且除T（0）外，其余節點的T（i）=∞；第二步是將o點相鄰點向量r找出，即dor（i）≠∞，對所有標號為T的值進行比較，找出最小值，即P（k），T最小時所在的點為k點；第三步是按照第二步方法，將k作為起始點，滿足T（r（j））=minT（r（j）），P（k）+dkr（i），將最小值所在點k/找出，記P（k/）；第四步是迭代第三步，在全部節點被標志為P后，則求出了o點到其余節點的最小阻抗；第五步是根據所需，對目標點進行查詢，以目標點d為起始點，將滿足式P（j）=dij+P（i）的i點找出，最短路徑中j的前一點就是i點，對i點之前的點進行繼續搜索，同樣根據P（j）=dij+P（i），直到搜索起點o，圖2為Dijkstra算法程序流程圖。
3.2 矩陣迭代算法
矩陣迭代算法首先要構造距離矩陣，在矩陣中，給出了節點間經過一步到達某一點的距離，見圖3，通過距離矩陣的迭代運算，兩步到達某一點的最短距離就得到了。因此，使用矩陣迭代算法研究最短路徑問題時，各出行節點間最短路線要知道。
在D（4）=D（3）時，具有最短距離矩陣，通過矩陣，可將最短距離計算出。通過反向追蹤，對相應最短路線進行確定。
矩陣迭代法指的是從路徑集合中進行挑選，將最短路徑分步選出來，完成矩陣迭代，則表明可計算出每一對od點間的最短路徑。迭代矩陣算法思想類似于Dijkstra，不同的是其采用矩陣形式對最短路徑問題的進行思考，也就是在od兩點間，嘗試性選擇中間路徑，計算每個可能的中間路徑，并將最小節點選出，并進行迭代計算，得出到達該最短路徑是要經過幾個中間節點。當所有節點最短路徑迭代全部求出后，矩陣迭代結果保持穩定，不再變化，這時表明迭代結束。
矩陣迭代算法的計算步驟共4步，第一步是給定od，其阻抗方陣為D，D1=D，按照公式dij（2）=min（di1（1）+d1j，di2（1）+d2j，…，din（1）+dnj），n表示矩陣階數n，i=1～n，j=1～n。根據此公式，將兩步到達目的地最小阻抗計算出，D2為得到的新矩陣。當dik+dkj達到最小時，將k值記為k（1），也就是最短路徑中的一點；第二步是根據公式dij（3）=min（di1（2）+d1j，di2（2）+d2j，…，din（2）+dnj），n表示矩陣階數n，i=1～n，j=1～n，得到D3。最小值對應點記為k（2）；第三步則依次類推，dij（m）=min（di1（m-1）+d1j，di2（m-1）+d2j，…，din（m-1）+dnj），n表示矩陣階數n，i=1～n，j=1～n，得到Dm，最小值對應點記為k（m-1），直到Dm=Dm-1；第四步是對目標最小阻抗od即dodm進行搜索，i、j兩點間最小阻抗表示為dijm。在標志點o，k（1），k（2），…，k（m-1），d中，x取最短路徑，為避免某些點會出現重復，按照didm=dik+dkdm的路徑順序原則進行確定，i起始于o點，根據標志點順序，依次進行檢驗，最短路徑就是符合要求的點向量。圖4為矩陣迭代算法程序流程圖。
4 兩種算法的比較
通過MatLab平臺，進行矩陣迭代算法、Dijkstra算法的編程，MatLab能將計算過程及結果顯示出來，通過profiler功能，能將計算時間顯示出來。
4.1 最短路徑收斂性
矩陣迭代算法、Dijkstra算法的收斂特性由路阻矩陣及計算思路特點決定。因此，使用用計算機計算是可行的。在相鄰節點，Dijkstra尋找過程中，向目標節點步步靠近，當最后的終止條件滿足后，達到查詢終點，起始點到其他點的最小路徑能計算出。因路阻矩陣特殊性，在矩陣迭代算法中，矩陣對角線位置元素均為零，目標節點就是最終收斂點，矩陣收斂的充要條件是對角線上的零元素。
4.2 兩種方法異同點
相比于矩陣迭代算法而言，使用Dijkstra算法，可將一點到其他各點的最小阻抗一次性求得，根據最短路徑，最短路徑經過的節點可依次得到，在進行最短路徑的計算時，需要反復進行，同時不能顛倒起始點到其他各點最小阻抗的計算順序，按照步驟嚴格進行，因而，Dijkstra算法計算效率低，收斂速度較慢。相比于Dijkstra算法而言，矩陣迭代算法則非常簡潔，要求不苛刻，矩陣迭代計算效率提高的方法有三個比較可行。第1個是在矩陣迭代算法中，每一步只要遵循dij（m）=min（di1（m-1）+d1j，di2（m-1）+d2j，…，din（m-1）+dnj），n表示矩陣階數n，i=1～n，j=1～n原則，在i，j間，其迭代順序限制不嚴格，可并行進行計算，這樣就可使計算速度大大提高；第2個是可以同時設計程序，使計算值避免出現∞數據，只對非∞數據與其下標策略進行存取，這樣內存空間就得到節約，從而使計算效率得到提高；第3個由于阻抗矩陣屬于對稱矩陣，在不斷進行迭代后，阻抗矩陣仍屬于對稱矩陣，根據這一特征，每次迭代的計算量可減少。若道路阻抗是負數，則可能Dijkstra算法會出現無效，在矩陣迭代算法中，道路阻抗可為負數，圖5為矩陣迭代算法中的道路阻抗。
4.3 計算效率比較
在計算程序中，MatLab內含的程序測試器profiler，具有一定的優越性，因此本研究采用MatLab平臺進行Dijkstra算法、矩陣迭代算法的編程，并計算同一路網，在得到相同結果時，對各個計算效率指標進行比較，在計算效率方面，顯示Dijkstra算法、矩陣迭代算法的不同。在重慶市路網上隨機選取8個終點及起點，對起始點1點到8點的最短路徑及阻抗進行計算。在程序算法分析里，時間復雜度是非常重要的內容，時間復雜度通常是指算法中執行基本運算的次數，影響時間復雜度的因素較多，本研究主要對影響時間復雜度的重要因素進行分析，比較Dijkstra算法、矩陣迭代算法的時間復雜度，表2為兩種方法計算時間，表3為Dijkstra算法的計算結果，表 4為矩陣迭代算法計算結果。
對起始1點到8點的最小路阻采用Dijkstra算法進行計算，結果為P（8）=5，其相應的最短路徑為14568。對起始1點到8點的最小路阻采用迭代矩陣算法進行計算，結果為D1（1，8）=5，其相應的最短路徑為14568，結果相同。但Dijkstra算法和迭代矩陣算法的計算效率有一定的差距，從表2可以看出，Dijkstra算法所用時間為0.673s，迭代矩陣算法所用時間為0.501s，矩陣迭代算法的計算速度更快。矩陣迭代法可全部算出路網中兩點間的最小阻抗，Dijkstra算法僅能算出起始點到其他各點間的最小路阻；路網中的節點遠比8多很多，采用Dijkstra算法要進行上萬次的循環，使計算速度大幅降低，使用迭代矩陣算法，則迭代次數遠比節點數小，因此，迭代矩陣算法優勢更大，同時對于路阻為負的路網，可通過矩陣迭代進行計算，即對于更廣泛的最短路徑，迭代矩陣算法能適合其計算要求。
基本運算次數與運算所需時間的乘積即就是算法執行時間，為進一步比較Dijkstra算法和迭代矩陣算法的計算效率，本研究將兩程序對中取出4×4、6×6、8×8共3個矩陣進行計算，對運算時間進行比較，分別對交通運輸路網中任意2點間的最小阻抗進行計算，表5為計算時間參數數據。
從表5可以看出，在矩陣4×4、6×6、8×8中，矩陣迭代算法的運算時間均比Dijkstra算法的運算時間要小，其迭代次數次數也遠遠小于Dijkstra算法的迭代次數，這進一步表明，矩陣迭代算法的計算效率要比Dijkstra算法的計算效率高。
5 結論
本文基于矩陣迭代算法及Dijkstra算法，對兩者在最短路徑問題中的差異性進行了對比，得出以下結論：
（1）通過Dijkstra算法，對于一點到其他各點的最小阻抗可一次求得，最短路徑經過的節點可依次得到，該算法在進行最短路徑的計算時，需要對相點進行反復搜尋，計算效率較低，收斂速度較慢。
（2）矩陣迭代算法是元素間比較、數列間相加的過程，特點是簡單快捷。矩陣迭代算法沒有嚴格路徑次序限制迭代順序，可實現算法并行計算，計算速度較高。在阻抗矩陣為對稱矩陣時，在經過迭代后，得到的矩陣仍為對稱矩陣，這樣可使每次迭代的計算量得到減少。
（3）通過在重慶市路網上隨機選取8個終點及起點，對起始點1點到8點的最短路徑及阻抗進行計算表明，Dijkstra算法所用時間為0.673s，迭代矩陣算法所用時間為0.501s，矩陣迭代算法的計算速度更快。在矩陣4×4、6×6、8×8中，矩陣迭代算法的運算時間均比Dijkstra算法的運算時間要小，其迭代次數次數也遠遠小于Dijkstra算法的迭代次數，這進一步表明，矩陣迭代算法的計算效率要比Dijkstra算法的計算效率高。
參考文獻
[1]張美玉，簡b峰，侯向輝，等.Dikstra算法在多約束農產品配送最優路徑中的研究應用[J]，浙江工業大學學報，2012，40（03）：321-326.
[2]Niehols，Jolin M.A major urban earthquake： planning for arma-geddon[J]，Landscape and Urban， 2005，73，2：136-154.
[3]劉洪麗，顧銘.矩陣迭代法在物流中心選址中的應用分析[J]，現代商貿工業，2013（20）：64-67.
[4]丁浩，萇道方.基于Dijkstra算法的快遞車輛配送路徑優化[J]，價值工程，2014（03）：15-18.
[5]郭瑞軍，王晚香.基于矩陣迭代法的出租車合乘最短路徑選擇[J]，大連交通大學學報，2011，32（04）：28-32.
[6]任鵬飛，秦貴和，董勁男，等.具有交通規則約束的改進Dijkstra算法[J]，計算機應用，2015，35（09）：2503-2507.
[7]王樹西.改進的Dijkstra最短路徑算法及其應用研究[J]，計算機科學，2012，39（05）：223-228.
[8]劉春年，鄧青菁.應急決策信息系統最優路徑研究-基于路阻函數理論及Dijkstra算法[J]，災害學，2014（03）：7.
[9]潘若愚，褚偉，楊善林.基于Dijkstra-PD-ACO算法的大城市公交線路優化與評價方法研究[J]，中國管理科學，2015，23（09）：106-116.
[10]王佳，符卓.綜合客運樞紐接運公交線路優化設計[J]，系統工程，2012，30（05）：101-106.
[11]高明霞.基于雙層規劃的交通疏散中車輛出發與交通控制綜合優化[J]，中國管理科學，2014，22（12）：65-71.
作者簡介
肖鵬（1980-），男，江蘇省鎮江市人。碩士學位?，F為江蘇城鄉建設職業學院基礎部講師。研究方向為應用數學。
路徑規劃典型算法范文6
關鍵詞：蟻群算法；無線網絡；路由協議；路徑選擇；性能優化
DOIDOI：10.11907/rjdk.161913
中圖分類號：TP393
文獻標識碼：A文章編號：16727800（2016）010017604
0引言
由于社會發展的需要，傳統有線網絡無法滿足用戶更多類型的應用需求，公眾對無線通信領域的應用標準不斷提高，面向無線通信網絡的應用加劇了提升通信效率方面的開發幅度和性能要求，受限的無線媒介與實際應用的需求矛盾逐漸凸顯[12]。路由協議是運行于網絡層的信息轉發策略，性能優越的路由協議能夠使消息的傳遞過程更加順暢，使通信客戶端可以通過最優的路徑將信息傳遞給其它客戶端，有效提升了網絡的整體性能。無線通信協議的路徑選擇示意如圖1所示，目前針對路由協議的開發僅僅局限在網絡層本身，并沒有將其與實際的數據應用相結合，通過信息手段將當前網絡狀況與實際協議開發相結合是目前行業發展的新趨勢[34]。
目前，很多專家學者針對無線環境下的路由協議進行了研究。為了解決分布式編碼感知路由協議中可能出現的吞吐量降低的問題，王春雨等[5]設計了一個能夠進行網絡編碼的無線通信路由協議，達到了提升系統吞吐量的目的。IP數據包廣泛應用于分布式通信網絡，迫切需要網絡具有自組織能力。由于單通道單一接口模型不滿足復雜系統的需求，Jin等[6]建立了一個面向軍事應用的分布式網絡拓撲結構，并實現了基于ZRP 的多渠道M-ZRP路由協議。仿真結果表明，M-ZRP具有更好的性能。
蟻群算法（Ant Colony Optimization，ACO）是根據螞蟻群落采集食物的原理被提出和模擬而來，已被應用于諸多領域。與基于梯度的性能優化算法原理不同，蟻群算法通過概率搜索算法來完成[78]。雖然概率搜索算法一般需要采用價函數，但是與傳統的梯度演化算法相比，其有諸多比較顯著的性能，集中表現在以下方面[911]：①無集中控制約束，不會因個別個體的故障影響整個系統問題的求解，確保了系統更強更穩定的魯棒性；②以非直接通信形式保證系統的可擴展性；③采用并行分布算法模型和多處理器運行模式；④定義問題的連續性沒有限制；⑤算法實現相對比較簡單。
OPNET Modeler中的WLAN 、MANET等無線通信節點模型提供了多種成熟的路由協議，包括按需距離向量路由（Ad hoc On Demand Distance Vector，AODV）、動態源路由（Dynamic Source Routing，DSR）、地理路由（Geographic Routing Protocol，GRP）等[1213]。
針對無線網絡中存在的問題，本文提出了基于TSP蟻群算法的無線通信路由協議優化設計方法，此優化設計將TSP基本蟻群算法的基本原理和通信路由選擇相結合，通過建立系統模型，依靠螞蟻信息素含量及距離競爭機制為節點選擇最優通信路徑。同時，本文通過在OPNET Modeler通信仿真軟件中建立仿真場景及完成模型構建，對基于TSP蟻群算法的無線通信路由協議進行測試驗證，并與其它典型無線路由協議進行對比分析，主要分析指標是傳輸延時及吞吐量。
1基于TSP蟻群算法的路由協議優化設計
1.1TSP蟻群算法模型
式中，Q為常數，表示螞蟻尋找路徑過程中所釋放信息素總量，它在一定程度上影響算法的收斂速度，本文中的Q值通過仿真獲得。本文采用的AntCycle模型，其利用的是系統全局信息，此信息更新策略能夠使較短路徑上對應的信息素逐步增大，保證了算法中整體范圍下較短路徑的生存能力，提升了信息正反饋性能，加快了系統搜索路徑的效率。同時，AntCycle模型的更新規則能夠保證殘留信息不造成無限積累，如果某條路徑沒有被選中，則對應節點的信息素含量會隨著時間的推移漸漸消失，使節點具備逐步淘汰劣質路徑的能力，即使某條路徑經常被訪問也不至于因為τij（t）的積累，而出現τij≥ηij的情況，使得期望值的作用無法體現。因而，本文的蟻群算法采用AntCycle模型。
1.4路由協議設計與實現
針對求解TSP問題的蟻群算法模型，對此模型進行修改，同時結合無線自組織網絡信息傳輸的特點，完成基于蟻群算法的路由協議設計，簡稱ACAB（ Ant Colony Algorithm Based）路由協議，具體實現步驟如下：Step1：初始化各通信節點間的距離。此操作通過節點廣播信息完成，每個節點被分配不同的ID，作為其在此過程中的唯一標識，廣播的數據幀格式如圖2所示，包括節點ID屬性，當前位置坐標（x，y），是否為源節點或目的節點，如果有數據發送需求，源節點屬性值賦值為1，同時將目的節點的ID進行賦值，并對發送序列進行編號，如果沒有數據發送需求，則置為0。
Step2：將若干螞蟻放在不同的通信節點中，每個通信節點維護自身的信息素列表，表中描述了當前節點的信息素含量和此刻與其它節點間的距離。信息列表的具體信息如圖4所示。當節點位置移動后，此表中的數據也進行更新。Step3：每只螞蟻根據各節點至目的節點的距離d和信息素水平τij（t），選擇下一通信節點，同時修改禁忌表。Step4：所有螞蟻完成周游后，更新信息列表中的信息素水平和節點位置信息。Step5：返回Step2，迭代次數d=d+1，直至尋找到源節點與目的節點間的最優路徑或者滿足結束條件，最優路徑的判定標準是路程最短min（Road），摒棄不必要的路徑信息。
2仿真實現及分析
通過在OPNET Modeler中建立仿真對比場景，對提出的基于TSP蟻群算法的無線通信路由協議與典型的AODV、DSR路由協議進行對比驗證，分析其在傳輸延時及吞吐量方面的性能表現。
2.1仿真場景建立及模型實現
OPNET Modeler采用離散事件驅動的模擬機理，通過事件驅動器以先進先出的機制對事件列表和事件時間列表進行維護管理[15]。本文設計的仿真場景中包含的通信節點由WLAN節點組成，可以通過設置其屬性對其進行控制。仿真范圍為1 000m2，仿真時間為30min。仿真過程中通信節點可以隨機移動，物理層與數據鏈路層均采用基本IEEE 802.11協議，通信節點總數初步設為100，數據發送間隔為100ms，基本數據幀大小為100字節，仿真場景如圖3所示。
同時，WLAN節點包含完整的OSI協議模型，本文的路由協議設計在IP層自定義完成。通信信息從WLAN收信機進入，依次經過MAC層、數據鏈路層、IP層、UDP層、路由層、應用層，完成整個消息的通信流程[16]。對消息的處理過程由traf_src進程模型完成，負責應用層相關事務。
2.2基于TSP蟻群算法的路由協議測試驗證
為了驗證優化后路由協議的通信性能，本文將基于TSP蟻群算法的路由協議優化設計方法與傳統的AODV及DSR路由協議進行了對比仿真。在仿真的20分鐘內，節點的信息素逐步累積，不同的數據請求序列針對不同的信息素標識，完成數據傳輸后，對應此路徑的信息素被清除，以節省系統容量。由于節點均為隨機移動，各節點的平均信息素水平基本相同，體現了本協議優化方法的公平性。
為了更直觀地體現通信性能的變化，本文通過傳輸延時和吞吐量對網絡性能進行描述分析。
為了體現系統整體性能，本文統計平均傳輸延時，假設成功發送N組數據，則計算如下：
=1N?∑Ni=1D（i）（10）
式（10）中，D（i）表示第i個分組的傳輸延時。網絡的吞吐量TH是指在正常情況下系統在單位時間內所有節點正確接收的信息量，單位是bit/s或是M/s。吞吐量描述了網絡可以完成通信任務的程度，是衡量自組織網絡通信質量的重要指標。
Th（i）m=ΔRp（i，m）ΔT（i，m） （11）
ΔRp（i，m）是指數據分組i到數據分組m被目的節點接收時系統已傳輸的信息總量，ΔT（i，m）是數據分組i到數據分組m被接收時兩者的時間差。若i>m，表示計算從第m個分組到第i個分組的吞吐量，若m=1，則結果是平均吞吐量。
圖4的仿真結果表明，在傳輸延時方面，提出的優化路由協議較AODV協議、DSR協議分別減少了7.5%和9.8%；在吞吐量方面，提出的優化路由協議較AODV協議、DSR協議分別提高了8.4%和7.8%。信息素含量如圖5所示，仿真過程中信息素含量基本維持在110單位左右，較穩定。這表明本文設計的基于TSP蟻群算法的無線通信路由協議較經典的協議效果有所改進。優化協議性能突出的原因是通過螞蟻信息素對路徑進行規劃和最優化選擇，使得劣質路徑在選擇的過程中被淘汰，但是需要指出的是，前期為了螞蟻尋找路徑而廣播的信息也加大了系統負擔，隱含在一部分吞吐量數據中，對仿真結果也產生了一定的影響。但總體而言，本文設計的ACAB路由協議效果較為突出。
3結語
通過分析無線網絡傳輸的基本原理及蟻群算法的運算過程，本文提出了基于TSP蟻群算法的無線通信路由協議優化設計方法。此優化設計將TSP基本蟻群算法的基本原理和通信路由選擇相結合，通過建立系統模型，依靠螞蟻信息素含量及距離競爭機制為通信節點選擇最優的通信路徑。同時，本文在OPNET Modeler通信仿真軟件中建立仿真場景并完成模型構建，對基于TSP蟻群算法的無線通信路由協議進行測試驗證，并與其它典型無線路由協議進行對比分析。仿真結果表明，在傳輸延時方面，提出的優化路由協議較AODV協議、DSR協議分別減少了7.5%和9.8%；在吞吐量方面，提出的優化路由協議較AODV協議、DSR協議分別提高了8.4%和7.8%。總之，本文設計的基于TSP蟻群算法的無線通信路由協議優化設計方法效果突出。
同時，本文也存在一定的弊端，例如，蟻群算法必然會增加諸如信息素之類信息維護的額外成本，并且關于模型實現會影響底層協議的運行。筆者將在今后的工作中著重對以上不足之處進行研究改進。
參考文獻參考文獻：
[1]LOVE D J，HEATH R W，LAU V K N，et al.An overview of limited feedback in wireless communication systems[J]. IEEE Journal on Selected Areas in Communications，2008，26（8）：13411365.
[2]XIE L L，KUMAR P R.A network information theory for wireless communication： scaling laws and optimal operation[J].IEEE Transactions on Information Theory，2004， 50（5）：748767.
[3]SURHONE L M，TENNOE M T，HENSSONOW S F，et al. Wireless routing protocol[M].Betascript Publishing，2010.
[4]王磊，施榮華.無線傳感器路由算法中的仿真研究[J].計算機仿真，2011，28（3）：170173.
[5]王春雨，張曦煌.Ad Hoc網絡中基于網絡編碼的無線路由協議研究[J].計算機工程與設計，2013，34（5）：15631567.
[6]JIN H，REN L，DING Y.A hierarchical wireless routing protocol for multichannel multiinterface ad hoc networks[C].2011 7th International Conference on Wireless Communications，Networking and Mobile Computing （WiCOM），2011：14.
[7]SBESTER A，FORRESTER A I J.Ant colony optimization[J].Alpha script Publishing， 2010，28（3）：11551173.
[8]MARTENS D，BACKER M D，HAESEN R，et al.Classification with ant colony optimization[J].IEEE Transactions on Evolutionary Computation，2007，11（5）：651665.
[9]ASIM M，DUNYUE L，MICHAEL C.Analysis and synthesis of an ant colony optimization technique for image edge detection[C].2012 International Conference on Computing Sciences，2012：127131.
[10]BLUM C，DORIGO M.The hypercube framework for ant colony optimization[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics a Publication of the IEEE Systems Man & Cybernetics Society，2004，34（2）：11611172.
[11]YI W，KUMAR A.Ant colony optimization for disaster relief operations[J].Transportation Research Part E Logistics & Transportation Review，2007，43（6）：660672.
[12]任敬安，涂亞慶.基于蟻群優化的AdHoc網絡路由協議實現[J].計算機工程，2012，38（21）：114118.
[13]ZAPATA M G，ASOKAN N.Securing ad hoc routing protocols[C].Proceedings of the 1st ACM workshop on Wireless security. ACM，2002：110.
[14]YU B，YANG Z Z，YAO B.An improved ant colony optimization for vehicle routing problem[J]. European Journal of Operational Research，2009，196（1）：171176.
