方天宇，張佳琳

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

自組織網(wǎng)絡中的智能容錯導航算法研究

方天宇1，張佳琳2

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

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

導航；容錯；自組織網(wǎng)絡；智能

一 研發(fā)需求

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

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

二 問題分析與解決方案

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

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

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

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

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

三 算法描述

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

圖1

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

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

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

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

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

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

四 仿真實驗與分析

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

車隊，共計50臺車GPS致盲的情況下的容錯導航情況。仿真中設定節(jié)點間通信距離為200米，節(jié)點間使用全雙工通信，速率為64K/s。節(jié)點行進速度為10公里/小時到50公里/小時隨機變速。三個車隊分散在6條路徑上，通往不同的2個目的地。從仿真實驗結果來看(如圖2所示)，本算法更能夠高效地使節(jié)點從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]張亞崇,陸志東,雷宏杰.實時分布式容錯綜合導航仿真系統(tǒng)技術研究[J].彈箭與制導學報，2009，29(6):25-28.

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

[6]李富榮,丁宏升.組合導航系統(tǒng)的容錯技術發(fā)展綜述[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

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

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

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

1672-6758(2012)06-0057-2

TP393

A