王仁红，廖惜春，郭洪威



改进的A*算法在Ad Hoc网络中的应用

王仁红，廖惜春，郭洪威

（五邑大学 信息工程学院，广东 江门 529020）

针对Ad Hoc网络拓扑结构频繁变动，已有路由的有效时间短、丢包率高等问题，将改进的A*算法应用于Ad Hoc网络实现路由查找，利用NS2仿真，将A*算法与传统的AODV、DSR路由算法在丢包率、传输速率、平均端到端时延、算法开销等4个方面进行性能比较，仿真结果表明：A*算法在源节点与目的节点间寻找路由的过程中，能够快速而准确地建立路由，在路由速度、发包成功率等方面有明显的提升.

Ad Hoc网络；A*算法；路由查找；发包成功率

1 A*算法的基本原理

A*算法通过OPEN和CLOSE表选择、保存节点，其中，OPEN表是路由查找过程中的一个链表，用来保存最终的路由路径，CLOSE表记录已访问过的节点. 首先将起始点放入OPEN表，CLOSE表置空，算法开始，其主要思路用C++语言格式表述如下：

1）若OPEN表不为空，从表头取一个结点，该节点可能是目标节点，也可能只是当前Ad Hoc网络中的一个普通节点，若OPEN表为空，则失败退出；

2）判断是否为目标解，如果是，终止算法；否则进行下一步；

2 基于改进A*算法的Ad Hoc路由算法

2.1 改进的A*算法描述

A*算法广泛应用于有线网络最优路径求解以及一些策略设计中，在无线Ad Hoc网络的路由查找过程中，需要对A*算法做如下改进.

a）把上述第3步替换为“将的所有与父节点直接相连的下一层子节点放入OPEN表中（程序代码为p->node=），同时把放入CLOSE表中，计算启发式函数值，保存在节点信息中，并且用后向指针指向的当前节点即父节点，用于从目标点回溯，确定最终的路由，然后返回步骤1”.