自組織網絡中的智能容錯導航算法研究

方天宇，張佳琳

(1.哈爾濱廣播電視大學，黑龍江 哈爾濱 150001； 2.哈爾濱商業大學，黑龍江 哈爾濱 150076)

自組織網絡中的智能容錯導航算法研究

方天宇1，張佳琳2

(1.哈爾濱廣播電視大學，黑龍江 哈爾濱 150001； 2.哈爾濱商業大學，黑龍江 哈爾濱 150076)

導航中的通信中斷等災難性故障是現代導航系統的障礙之一。為了實現車載導航系統的有效容錯，提出了基于自組織網絡智能節點的容錯導航算法；給出了該算法的主要方案、數據結構和程序流程；提出了多路徑選擇的導航方案。實驗仿真結果證明，該算法響應速度較快，能充分利用自組織網絡中的殘留數據。

導航；容錯；自組織網絡；智能

一 研發需求

GPS(Global Positioning System)是目前使用范圍最廣的高精度的衛星導航系統；該系統能夠與移動電子地圖配合，實現實時定位與自動導航功能。隨著高速無線通信與計算智能技術的不斷進步，廣域范圍內的自組織網絡算法在諸多領域體現出其重要價值，[1]如：美軍研制的新一代數據鏈路Link16系統，能夠使GPS的定位導航協作在海陸空天各區域中的作戰單位中實現共享最大化；而美國陸軍新近研發的“大狗”軍用機器人可以將其通過的路徑進行GPS描點，生成道路信息與其他節點共享，以加速整個“狗群”的道路選擇過程。在“大狗”等分布式系統的研發過程中，美國科研人員總結了分布式導航系統必備的四要素：智能節電、交互協議、信息共享與協同機制、路徑識別和感知。其中，第三、第四要素是當前各國研究的重點和熱點。

盡管，GPS導航定位應用極為廣泛，但在實際生產生活中也暴露出一些問題。首先，由于GPS系統的應用受政治等非自然因素影響較大，伊拉克戰爭中伊軍導航系統失控即是明證；[1]此外，導航系統受載體所在外界環境影響較大，當載體處在通信干擾環境中時(例如：海底、涵洞、地道等)，GPS系統的應用會受到極大干擾。因此，當GPS系統在復雜交通環境(例如：戰場)中受到強干擾導致衛星通信中斷時，地面系統中的眾多結點應如何利用和共享自身導航系統中的存留信息進行下一步的容錯尋路和導航活動，已成為目前分布式導航的研究熱點之一。基于上述種種，本文提出了一種新型的基于自組織網絡(車載)的智能容錯導航算法。

二 問題分析與解決方案

早期的GPS容錯導航算法主要依賴于電子地圖中殘留的坐標、方向等導航信息，但由于信息量較少，因此此類研究很少有成功案例。近期有研究人員研發了基于信息共享的容錯導航算法，但由于這些算法需要節點獲取其他節點中的全局數據，因此導致算法的時間復雜度較高，過多占用系統計算和存儲資源，導致這些算法難以實用化。

針對上述問題，本模型進行了三方面的創新：

首先是導航殘留數據的共享方式改進：由于車載系統中，各節點相對運動速度快，彼此通信時間短暫，信息交互量少，如強制要求信息量的完整，則將會導致收集到的信息很少。因此，本算法在各節點交互時，采用“盡可能交付”方式，即：(1)在車輛等導航系統載具的通信范圍內，盡可能地向盡可能多的其他節點發布消息，并從其他節點中獲取消息；(2)采取盡可能簡潔的消息報文格式，和具有自明性的報文內導航描述“塊”，以便在接到不完整報文時，仍能從其中獲取有用的信息。

其次是導航定位方式的改進：GPS導航系統中使用的是動態數據，而車載電子地圖中存留的是相對靜態的數據；因此，電子地圖上同一路徑中的節點接到的定位信息也不會完全相同。而GPS不能進行定位操作時，容錯算法只能根據電子地圖中的既有數據，以載具當時的坐標和車輛前進方向、速度等參數，進行計算當前坐標，以替代GPS定位導航。

最后是由于道路預測；由于現代交通系統中的道路呈現高度的動態性質，因此，描述道路的模型構成形態空間如果過于復雜，則無法用普通的數值方法求解；因此本算法中采用了蒙特卡羅算法進行相似路徑識別；具體描述參見下文。

三 算法描述

本算法由3個模塊及對應的數據結構組成，如圖1所示：

圖1

首先是節點交互協議模塊：該模塊和其他算法中的交互模塊類似，主要用于容錯數據的發送和接收。但其具有兩個顯著不同之處：(1)由于自組織網絡中節點眾多，且隨時活動，因此難以獲得整個網絡的全局視圖，無法采用節點輪詢等通信方式，所以本模塊采用“觸發”執行方式，即：當其他節點進入本節點的通信范圍之內時，該模塊自動被執行，與相關節點交換導航信息；(2)自組織網絡的節點的通信距離有限，較多情況下，交互數據尚未處理完畢，雙方節點即超過通信距離，即通信中斷，雙方節點將提取殘缺數據報中的有用信息，以支持算法的運行。

其次是路徑選擇模塊：該模塊用于將蒙特卡羅算法用于路徑選擇與評估；其中，設r表示路徑的當前狀態到最佳狀態的向量距離；而g(r)函數為當前道路狀態到r級別時，算法賦予其的評估分數，f(r)函數為路徑屬性參數的分布密度函數(路徑的實際可通行程度)；基于上述因素：

其中，lt;ggt;是g(r)的數學期望值；首先，設當前節點進行過N次道路預測和評估，獲取的道路狀況依次為r1，r2，…，rN；有：

該平均值代表了該路徑的可通行程度。蒙特卡洛法將預測路徑變量X的有限樣本集合X1，X2，…，XN的算術平均值作為所求解的近似值(lt;ggt;)。通過大數中心定律，若X1，X2，…是獨立同分布的，則其有限期望值(E(X)lt;∞)為：

即路徑的通行情況隨子樣數N變化，當其足夠多時，概率1收斂于其期望值E(X)。

最后是人機接口模塊，主要用于道路提示與人工干預。

四 仿真實驗與分析

算法在聯想R150服務器上進行了仿真；模擬了三個

車隊，共計50臺車GPS致盲的情況下的容錯導航情況。仿真中設定節點間通信距離為200米，節點間使用全雙工通信，速率為64K/s。節點行進速度為10公里/小時到50公里/小時隨機變速。三個車隊分散在6條路徑上，通往不同的2個目的地。從仿真實驗結果來看(如圖2所示)，本算法更能夠高效地使節點從GPS故障中恢復，效率較高。

圖2

[1]Yannis Marinakis, Magdalene Marinaki, Georgios Dounias. A hybrid particle swarm optimization algorithm for the vehicle routing problem [J].Engineering Applications of Artificial Intelligence. 2010.23(4):463-472.

[2]Aboelmagd Noureldin, Ahmed El-Shafie, Mohamed Bayoumi. GPS/INS integration utilizing dynamic neural networks for vehicular navigation [J].Information Fusion,2011.12(1):48-57.

[3]Ching-Torng Lin, Hsin-Chieh Wu, Ting-Yen Chien. Effects of e-map format and sub-windows on driving performance and glance behavior when using an in-vehicle navigation system[J].International Journal of Industrial Ergonomics，2010，40(3):330-336.

[4]張亞崇,陸志東,雷宏杰.實時分布式容錯綜合導航仿真系統技術研究[J].彈箭與制導學報，2009，29(6):25-28.

[5]張強,孫堯,萬磊,等.低成本GPS/DR容錯組合導航系統設計[J].中國慣性技術學報，2010，18(4):455-461.

[6]李富榮,丁宏升.組合導航系統的容錯技術發展綜述[J].航空計算技術，2011，41(1):131-134.

ClassNo.:TP393DocumentMark：A

(責任編輯：鄭英玲)

AnIntelligentFault-tolerantNavigationAlgorithmBasedonAdHocNetworks

Fang Tianyu，Zhang Jialing

Communication stoppage is a problem in modern navigation systems. In order to deal with it, a novel intelligent navigation algorithm is proposed with Ad hoc network nodes. And its system models, data structures and key sub-algorithms are proposed as following. Further, a multi-path algorithm is utilized to check and choose the passable roads. Simulation results show that the algorithm has better faster response delays and greater efficiency than the old does.

navigation；fault-tolerant；Ad hoc network；intelligent

方天宇，碩士，講師，哈爾濱廣播電視大學。

張佳琳：博士，講師，哈爾濱商業大學。

國家自然科學基金項目(編號：60974104)資助

1672-6758(2012)06-0057-2

TP393

A