方天宇，張佳琳

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

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

方天宇1，張佳琳2

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

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

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

一 研發(fā)需求

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

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

二 問題分析與解決方案

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

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

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

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

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

三 算法描述

本算法由3個模塊及對應(yīng)的數(shù)據(jù)結(jié)構(gòu)組成，如圖1所示：

圖1

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

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

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

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

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

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

四 仿真實驗與分析

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

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

圖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]張亞崇,陸志東,雷宏杰.實時分布式容錯綜合導(dǎo)航仿真系統(tǒng)技術(shù)研究[J].彈箭與制導(dǎo)學(xué)報，2009，29(6):25-28.

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

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

ClassNo.:TP393DocumentMark：A

(責(zé)任編輯：鄭英玲)

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

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

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

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

1672-6758(2012)06-0057-2

TP393

A