自组织网络中的智能容错导航算法研究

方天宇，张佳琳

(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