ACADEMIC RESEARCH 学术研究
基于蚁群理论的车载移动自组织网络容错导航算法研究
◆ 张佳琳 方天宇 王 征
摘要：论文针对当前对等节点分布式导航系统存在的容错问题，提出了基于蚁群算法的新型导航算法思路，设计了车载移动自主组织网络容错导航算法的功能模块、总体流程以及算法核心。对比仿真实验证明，该算法具有良好的应用效果，能够节省系统开销，并提高容错效率，具有一定的实用价值。
关键词：容错导航；车载移动自组织网络；蚁群理论；算法
一、前言
意大利生物学家M.Dorigo和V.Maniezzo通过研究蚂蚁觅食的习惯规律，初步提出蚁群算法。目前已经在部分路径规划、路径导航等领域得以应用，例如：龙栋材等人采用模糊推理方法和蚁群算法相互结合的方式，提出了一种模糊蚁群混合优化算法，能够处理分布式交通导航系统中所产生的各类模糊信息，而且能够综合利用多种导航系统中的信息，求解最优导航路径[1]。通过实验验证可知，此算法不仅可以迅速融合导航系统中的各类模糊信息，而且能够减少求解最优路径的时间复杂度。温惠英等研究人员对蚁群算法进行了改进，并将其应用于煤矿挖掘车辆的车载定位系统中，实现了行驶路径的最优化[2]。该算法的思想是先通过蚁群算法处理定位数据，再从获得的路径中找出最短路径，最终将最优化的导航服务提供给煤矿挖掘车辆驾驶员。陆骏、王小平等人为了在全局范围内实现动态车辆最优行驶路线的规划，通过仿真模拟蚁群行为，提出一种基于蚁群算法的地面车辆导航模拟系统模型[3]。基于上述前人研究方向和成果，本文将采用蚁群算法对大规模的、复杂的分布式导航中的应用问题进行求解。
二、算法架构
本文将基于蚁群的算法结构设计的相对简单，旨在提高嵌入式系统中的运行效率，如图1所示，本算法模型组成包括4个处理单元模块和一个二重嵌套链表：
1.车载模块：该模块的主要功能是通信和存储。用于从通信区域内的蚁群节点（即车载电子地图）中采集导航定位数据，形成蚁群节点路径“残迹”队列，并对应构建道路标志数据和“残迹”队列的存储单元。
2.容灾导航模块：该模块用于处理现在位置和目的地之间的多条道路的“残迹”，采用蚁群方法获取尽可能多的系统内残留信息，从而保证容灾的实现。
3.电子地图接口模块：主要功能是接收和管理尚未经过处理的道路标志数据和“残迹”队列，并可将其提供给后续的各蚁群节点使用。人机接口模块限于篇幅在此省略介绍。
本算法通过定义嵌套链表数据结构，存储GPS残迹队列数据以及道路标志数据等相关信息，实现在GPS信号发生故障时预测可通行路 径以及评估路径可通行程度。该数据结构存储的主要方式是首先将蚁群节点道路标志数据存储于嵌套
142
信息系统工程 │ 2019.12.20
链表结点中，以容灾导航模块提供的信息交互序列和交互车辆的蚁群节点ID为主从索引构建主干链表；然后，在主干链表的每一个结点下，以GPS定位的时间信息、坐标信息为主从索引再构建一个新链表，用于存储该道路上的蚁群节点“残迹”队列数据，形成嵌套链表，如图1：
图1算法结构与模型
三、算法核心
首先，给出本算法的基本概念及其定义：容错载具（下文中简称载具）定义为Ad hoc通信网络中，存在N个载具（其中的每个载具运行唯一的容错软件），因此本系统的进程与载具可以视同为一个对象。载具（Point）记为：{Pi | N-1≥i≥0}。其中，假设算法中涉及的一切进程均与其所在的载具一起生灭；载具间可以彼此双向通信，因而形成全向通信网络，在有效通信范围之内，任意两个载具可以彼此进行双向双工通信，但由于这是一个典型的分布式系统，因此载具之间并不存在同步时钟也没有共享设备。此外，为符合Adhoc网络的实际需求，本算法允许载具自动分组，能够彼此互联（最大允许5跳的P2P路由通信），分组号由分组中最小的载具ID决定。
Adhoc载具系统中的有效通信可以表述为：整个Adhoc网络中，所有的载具以报文接收/发送形式实施载具间通信，无法直接进行互联的节点最多可通过5跳路由进行通信，否则通信无效；报文转发与直接互联过程中，采用先进先出(FIFO)模式。其中的通信报文，必须在最大跳和最长延迟之前结束传输，否则将自动清除，其中的报文规范为：请求报文：{Ri | Max-1≥i≥0}，回应报文：{RYi | Max-1≥i≥0}，定
义里Max是最大的传递次数。最终，算法核心的基本步骤如下：
Step1：对于载具中已存在的可行路径，本算法采用n维矢量X={x1,x2,...xn}来表述，n代表路径的组成元素数，矢量里
的n个对象对应已知可行道路的属性，A1，A2，…An对应的
n个测度。
Step2：将接入系统的所有载具共有的m条路线特征进行聚类，有C1，C2，…Cm。此时，如果存在一个没有进行路线特征归类的路径X，将通过朴素贝叶斯分类器对其进行处理，从而将这个样本划归后验概率值最高的对应的路线类，其分配公式可以表述为：
P(CiX)>P(CjX),1≤j≤m,j≠i基于上述公式，对P(CiX)进行极大化处理；而P(CiX)值
选择出其中最大的一个Ci划分，就是后验假设概率最大。上述计算均可以通过朴素贝叶斯算法进行处理，有：
P(CiX)=P(XCi)P(Ci)P(X)其中，P（X）对于所有的划分来说，都是一个常数，因此需要对P(XCi)P(Ci)进行极大化求解。本算法通过研究发现，当前路径以及相关可行路径很多情况下是其他载具传导过来的，因此在本载具中并没有的到其先验概率，只能假设其可通行性为P（C1）=P（C2）=…=P（Cm）；进一步进行极值化处理P(XCi)；或对P(XCi)P(Ci)进行极大化处理。如系统中的
路径均是自身生成，则可以通过P(Ci)=sis进行计算，其中si是路径类Ci中的训练样本数，而s是训练样本总数，建立该公式的前提是电子地图中的路径类型已有较好的训练样本。
Step3:根据本研究的测算，本算法中P(XCi)极大化的处
理开销很高，而载具中的嵌入式系统往往计算资源有限。因此，为降低P(XCi)的资源损耗，本算法假设路径的相关属性彼此不相关，有：P(XC)ni=∏p(xkkCi)=1此时P(X1Ci)，P(X2Ci)，…P(XnCi)将通过已知路径进行拟
合估计，此时将进行分类处理，有：
首先，如果Ak是分类数据类型时，可以通过下列进行归类：
；sik是Ak集合中的xk路线Ci类之值，
其中的si为Ci类中的相关路径数量。
其次，如果Ak是数值型数据类型时，可以通过高斯计算对整个过程进行化简，即：
其中，相关Ci类有上述Ak的特性，也就是说：
g(xk,µCi,σCi)是Ak所属的高斯密度函数；而其他参数是相关
路径的可通行均值以及道路参数的标准差。
最终，其它载具传递来的X将在当前载具中进行路线类型聚类，相关的已知线路Ci可以通过P(XCi)P(Ci)进行求解；而X划分Ci类需要满足下列条件，即：
P(XCi)P(Ci)>P(XCj)P(Cj),1≤j≤m,j≠i其中的X是P(XCi)P(Ci)的极大化类型Ci。就可以将其定义为当前的最佳容错路线，并向驾驶人员提供决策参考。
ACADEMIC RESEARCH 学术研究
四、算法性能测试
为了验证新算法的实际效能，与旧算法进行了联合对比仿真实验，该实验采用联想2520服务器，为保证并行对比，采用了2.4GHzX4处理器，RAM容量为8G。系统采用了Win2008 Server以及OpenNet仿真工具，其中群组仿真模拟了50辆机动车，在定位导航系统失效的情况下，分别采用新旧算法脱困的情景。参考国际通用的HCP5303容错设备检验标准，仿真过程中规定两台车辆的直接通信距离为400米，车辆间通信速率为K/s；车辆的行驶速度控制在10Km-60Km/h，仿真车辆将根据虚拟环境中的地形以及路况进行随机配速（系统中设定了7类可通行道路或地形，每种的最大通行速度与通用通行速度不同），为了尽可能模拟实际环境，系统中还将30%的地形与道路设为不可通行。最后，所有的车辆中均预设6条已经通过或者通过交换获得的可通行路径。仿真实验结果如表1所示，其中新算法的总体效能与各项子
表1 新旧算法的效能对比
效能指标新算法旧算法容错成功率79.35%55.87%容错有效率94.21%72.09%收敛速度43s117s响应速度31s92s容错覆盖度97.37%51.75%导航准确度91.50%
69.88%
指标均较为良好，可用性较高。H参考文献
[1] 龙栋材, 李斌兵. 蚂蚁算法在导航系统中的应用研究[J]. 陕西师范大学学报( 自然科学版),2006,34(6):13-16p.
[2] 温惠英, 徐建闽. 基于改进型蚁群算法的车辆导航路径规划研究[J]. 公路交通科技,2009,26(1):125-129p.
[3] 陆骏, 王小平, 曹立明. 一种基于蚁群算法的车辆导航系统模拟模型[J]. 计算机应用与软件,2005,22(4):17-19p.
（基金项目：黑龙江省教育厅科技项目（12531161）
资助）
（作者单位：张佳琳，哈尔滨商业大学；方天宇，哈尔滨广播电视大学；王征，西南财经大学）
信息系统工程 │ 2019.12.20
143
