基于A-Star算法的Ad Hoc无线网络最优路由模型研究

刘熙明，魏 旭，窦立刚，覃洪波，杨露溪

（1.贵州航天天马机电科技有限公司，贵州遵义563000；2.贵州大学，贵州贵阳550025）

作为一种去中心化的网络技术，Ad Hoc无线自组织多跳移动通信网络逐渐成为无线通信领域的关键技术。不同于图1所示传统的无线通信网络，Ad Hoc无线网络不需要预先架设固定的通信网络基础设施，这种优势使得Ad Hoc在战场、大型营救现场等没有常规基础设施的情况下能够快速灵活地实现无线通信，拓展了移动通信的应用范围，具有十分广阔的发展前景。

图1 具有固定网络设施的无线通信网络拓扑结构

Ad Hoc网络不需要固定的网络基础设施，每一个网络节点都具有报文收发和路由的功能，节点之间可以构成任意的网络拓扑，同时也可以作为网关接入互联网中。Ad Hoc网络的去中心化使得该网络具有很强的抗毁重组的能力，网络中的部分节点被破坏或者传播条件发生变化时都不会造成整个网络的瘫痪。

当前对于Ad Hoc网络的研究大多数是基于Ad Hoc网络的协议进行仿真分析，运用到实际中的比较少，其中有关于网络分簇算法及Ad Hoc网络安全方面的研究。本文在此基础上，以无线射频传输模块和FPGA为硬件平台，把最优路径算法A-Star算法运用到无线网络模型中，实现去中心化网络的无线路由最优化，提高数据传输速率，有效减少网络的路由开销。

在Ad Hoc网络中所有节点都是对等节点，没有主从之分，网络采用分布式控制，将网络的控制功能分散到多个节点或者全部节点中，如图2所示。节点具有自组织功能，能够在网络的拓扑结构发生变化的时候，选择合适的参数来形成较为合理的拓扑结构。Ad Hoc网络中的所有节点均可形成平面结构，从源节点到目的节点通常存在多条路由，因此实现最为优化的数据链路传输路由则是平面分布的Ad Hoc网络节点所需要研究和解决的重要问题。

图2 Ad Hoc网络拓扑结构

1 算法描述

1.1 A-Star最优化路径算法详解

最短路径问题是指在一个带权值的图中，寻找两个特定节点之间一条有最小权值和路径。假设一个无线网络节点拓扑关系模型可视为数学上的赋权有向图G=（N，A），C（P）=Ca1+Ca2+…+Can为路径的弧长之和。则最短路径问题就转换为在有向图中求解任意两节点的最优化路径的问题。

双向启发式A-Star算法相比较传统的A-Star算法，双向A-Star算法具有时间更短的优点。双向A-Star算法的思想是将搜索过程分解为两个过程，正过程从原节点到目标节点进行搜索，而逆过程则是从目标节点到源节点的搜索过程，正向过程的启发函数基于目标节点计算，逆向过程的启发函数以源节点为基础进行计算。

理论上而言，正向和逆向搜索在源节点目标节点连线的中点相遇，但是在实际的拓扑结构中，由于目标节点和原节点所处网络位置的节点密度等情况不同，会造成不在中点相遇的情况。为了改善这种情况，避免算法在中间部分错过，采用迭代式最佳节点替换法来实现正向和逆向启发式搜索。具体的做法是，同时进行正向和逆向搜索，并同时生成正向和逆向最佳节点，以新生成的最佳节点为目标节点和原节点，再次进行搜索得到二次正向、逆向最佳节点，如此反复迭代，直到相遇为止。

1.2 基于A-Star最优化路由

由图2可知，数据从源节点传输到目标节点，有很多种路径可以选择，而最优化的路径只有一种，此时寻找最优路径的问题就转换为求有向拓扑结构中源节点到目标节点最优路径的问题，即可运用双向A*算法实现最优化路由。

2 仿真与测试

2.1 基于A-Star最优化路由路径仿真

为了验证所设计算法的可行性，在Matlab中建立仿真模型进行仿真。随机分布80个网络节点，模拟去中心化网络。通过Matlab 2012Rb仿真得到结果如图3和4所示。图3为80个节点时的路由最优路径仿真结果，图4为随机撤掉部分节点之后的路由最优路径仿真结果。从图3和图4中可以看出，本研究所使用的算法稳定可靠。

图3 80节点时的仿真结果

图4 撤去部分节点之后的仿真结果

2.2 软件设计

软件确保整个组网协议具体实现，使用VHDL语言编写。系统上电初始化硬件接口之后，初始化自身节点地址，并把节点地址广播出去，同时获取来自其他节点的地址，把所有接收到的地址数据进行遍历广播，广播完毕之后，所有在网节点之间均能收到其他在网节点的地址数据，所有的在网设备的地址构成拓扑关系进行存储。随后任意节点请求数据发送，先进行路由优化，优化完毕之后传输数据。其流程如图5所示。

图5 软件流程

2.3 外场测试

为了测试所设计算法的可行性，搭建了硬件测试平台。本研究所选用的硬件架构为无线射频终端+FPGA，每个节点外挂一路DS18B20温度传感器，并能显示10路温度值。节点数量为10个，每个节点均能同时实现数据的收发控制，无线射频传输模块的有效传输距离为50 m。传输的数据为实测的环境温度数据。

2.3.1 近距离组网通信测试

开机上电之后，设置8台设备的间离为5 m，测试各节点能够检测到其他设备是否在线，板子上配有8路LED灯，用于指示各网络节点是否成功组网。通过切断电源以及增加间隔距离的方式模拟节点丢失，近距离组网通信测试结果如表1所示。

表1 近距离组网通信测试结果

2.3.2 双跳组网测试

使用3个节点设备，呈直线排列，相邻两节点之间距离45 m，保证相邻两节点之间能实现可靠信号收发。节点1和节点3之间有效距离为90 m，无法直连通信，数据要从节点1传到节点3，只能通过节点2中继传递，实现双跳数据传输。双跳组网测试结果如表2所示。

表2 双跳组网测试结果

从表2可以看出，3个节点能够完成组网，节点1和3之间能够实现数据传输，在超出接收范围的情况下，能通过节点2进行中继传输。

图6 节点排列结果

2.3.3 多跳组网以及路径优化测试

使用8台节点设备，排列形状如图6所示。在保证节点之间距离均小于50 m的情况下，测试其路径最优化算法是否有效实现，8个节点设备在组网成功之后，处于静默状态，等待唤醒，可以通过扫频仪实现去监视8个设备的活动。设置图6中的节点2为原节点，节点7作为目标节点。图6a、6b为两种不同分布方式，而图6c为图6a中丢失节点5后的情况。

由图6a中节点分布可知，从节点2到节点7的数据经过的最优路由为节点2→节点4→节点5→节点7。由此可知，测试结果只有2、4、5、7节点处于活动状态，1、3、6、8节点处于静默状态。

由图6b中节点分布可知，从节点2到节点7的数据经过的最优路由为节点2→节点3→节点4→节点5→节点6→节点7，由此可知，测试结果只有2、3、4、5、6、7节点处于活动状态，1、8节点处于静默状态。

图6c中节点分布可知，从节点2到节点7的数据经过的最优路由为节点2→节点4→节点6→节点7。由此可知，测试结果只有2、4、6、7节点处于活动状态，1、3、8节点处于静默状态。

所有测试结果如表3所示。

表3 多节点测试结果

从表1测试结果可以看出，所设计的组网协议能够基本实现组网功能，单跳、多跳数据传输。在网络中的某一节点丢失之后，网络很快实现路由重构，具备很强的抗毁重组能力。在没有数据传输的情况下，各节点处于静默状态，有效地降低了功耗。

外场试验结果显示，把路径优化算法用于去中心化无线网络中寻找最优化路由的方法是可行的。

3 小结

本文结合Ad Hoc网络的特点，以提高网络中的数据传输速率、降低路由开销和数据传输时延为目标，提出一种基于A-Star最优路径算法的Ad Hoc网络路由最优化和次优化方法。通过数值仿真试验表明，把A-Star最优化路径算法运用到去中心化网络Ad Hoc中寻找最短路由的方法可行。外场实验结果表明，以A-Star最优化路径算法为基础的网络路由优化可行有效，数据传输无误码，能够有效地降低数据传输延迟、网络泛洪以及网络路由的开销，提高网络的抗毁重组能力，具有工程应用价值。