第２５卷 第２期 五邑大学学报（自然科学版） Ｖｂ１．２５ Ｎｏ．２ ２０１１年 ５月 ＪＯＵＲＮＡＬ ＯＦ ＷＵＹｌ ＵＮＩＶＥＲＳＩＴＹ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） Ｍａｙ ２０１ｌ 文章编号：１００６－７３０２（２０１１）０２・００３８－０５ 改进的Ａ水算法在Ａｄ Ｈｏｅ网络中的应用 王仁红，廖惜春，郭洪威 （五邑大学 信息工程学院，广东 江ｒ１ ５２９０２０） 摘要：针对Ａｄ Ｈｏｃ网络拓朴结构频繁变动，已有路由的有效时间短、丢包率高等问题，将改 进的Ａ’算法应用于Ａｄ Ｈｏｅ网络实现路由查找，利用ＮＳ２仿真，将Ａ 算法与传统的ＡＯＤＶ、 ＤＳＲ路由算法在丢包率、传输速率、平均端到端时延、算法开销等４个方面进行性能比较， 仿真结果表明：Ａ 算法在源节点与目的节点问寻找路由的过程中，能够快速而准确地建立路 由。在路由速度、发包成功率等方面有明显的提升． 关键词：Ａｄ Ｈｏｅ网络；Ａ 算法；路由查找；发包成功率 中图分类号：ＴＮ９ｌ５．０４ 文献标志码：Ａ Ａ Ｓｔｕｄｙ ｏｆ ｔｈｅ Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｔｈｅ Ａ Ａｌｇｏｒｉｔｈｍ ｉｎ Ａｄ Ｈｏｅ ＷＡＮＧ Ｒｅｎ－ｈｏｎｇ，ＬＩＡＯ Ｘｉ－ｃｈｕｎ，ＧＵＯ Ｈｏｎｇ－ｗｅｉ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｗｕｙｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｊｉａｎｇｍｅｎ ５２９０２０，Ｃｈｉｎａ） Ａｂｓｔｍｏｔ：Ｉｎ ｌｉｇｈｔ ｏｆ ｔｈｅ ｆｒｅｑｕｅｎｔ ｓｔｒｕｃｔｕｒａｌ ｃｈａｎｇｅｓ ｏｆ ｔｈｅ Ａｄ Ｈｏｃ ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｙ．ｓｈ０ｒｔ ｄｕｒａｔｉｏｎ ｏｆ ｔｈｅ ｅｆｆｅｃｔｉｖｅ ｒｏｕｔｅ ａｎｄ ｔｈｅ ｈｉｇｈ ｐａｃｋｅｔ ｌｏｓｓ ｒａｔｅ，ｗｅ ａｐｐｌｉｅｄ ｔｈｅ ｉｍｐｒｏｖｅｄ Ａ Ａｌｇｏｒｉｔｈｍ ｔｏ ｔｈｅ Ａｄ Ｈｏｅ ｎｅｔｗｏｒｋｓ ｔｏ ａｃｈｉｅｖｅ ｒｏｕｔｉｎｇ ｌｏｏｋｕｐ．Ｗｅ ｃｏｍｐａｒｅｄ ｔｈｅ Ａ Ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ＡＯＤＶ ａｎｄ ｔｈｅ ＤＳＲ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｕｓｉｎｇ ＮＳ２ ｓｉｍｕｌａｔｉｏｎ ｉｎ ｔｈｅ ｆｏｕｒ ａｓｐｅｃｔｓ ｏｆ ａｌｇｏｒｉｔｈｍ ｐｅｒｆｏｒｍａｎｃｅ：ｐａｃｋｅｔ ｌｏｓｓ ｒａｔｅ，ｔｒａｎｓｍｉｓｓｉｏｎ ｒａｔｅ，ａｖｅｒａｇｅ ｅｎｄ ｔｏ ｅｎｄ ｄｅｌａｙ ａｎｄ ａｌｇｏｒｉｔｈｍ ｏｖｅｒｈｅａｄ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ Ａ ａｌｇｏｒｉｔｈｍ Ｃａｌｌ ｑｕｉｃｋｌｙ ａｎｄ ａｃｃｕｒａｔｅｌｙ ｅｓｔａｂｌｉｓｈ ｔｈｅ ｒｏｕｔｅ ｉｎ ｔｈｅ ｒｏｕｔｉｎｇ ｐｒｏｃｅｓｓ ｆｒｏｍ ｓｏｕｒｃｅ ｎｏｄｅ ｔｏ ｄｅｓｔｉｎａｔｉｏｎ ｎｏｄｅ ａｎｄ ｃａｎ ｓｉｇｎｉｆｉｃａｎｔｌｙ ｉｎｃｒｅａｓｅ ｔｈｅ ｒｏｕｔｉｎｇ ｓｐｅｅｄ ａｎｄ ｔｈｅ ＳＵＣＣＥＳＳ ｒａｔｅ ｏｆ ｓｅｎｄｉｎｇ ｐａｃｋｅｔｓ． Ｋｅｙ ｗｏｒｄｓ：Ａｄ Ｈｏｅ ｎｅｔｗｏｒｋ；Ａ ａｌｇｏｒｉｔｈｍ；ｒｏｕｔｉｎｇ ｌｏｏｋｕｐ；ｐａｃｋｅｔ－ｓｅｎｄｉｎｇ ｓｕｃｃｅｓｓ ｒａｔｅｓ Ａｄ Ｈｏｃ网络是由一些移动节点组成的无线通信网络，它的每一个节点都采用全双工通信，网络 没有固定的结构，当两个节点不满足直接通信时需要通过中间节点传输信息，因此，如何在源节点 与目的节点之间找到通信的路径非常重要Ｉ１－３１．传统的Ａｄ Ｈｏｅ网络路由算法主要分为２类【４－５ｌ：一是 动态维护路由表的算法，如目的序列距离矢量路由协议（Ｄｅｓｔｉｎａｔｉｏｎ Ｓｅｑｕｅｎｃｅｄ Ｄｉｓｔａｎｃｅ Ｖｅｃｔｏｒ， ＤＳＤＶ），但该算法需要不断地进行路由更新，不仅占用了大量的带宽，而且容易形成广播风暴【６ ； 二是按需路由算法，其代表是Ａｄ ｈｏｃ按需距离矢量路由协议（Ａｄ ｈｏｃ Ｏｎ Ｄｅｍａｎｄ Ｄｉｓｔａｎｃｅ Ｖｅｃｔｏｒ， 收稿日期：２０１０－１２－１５ 基金项目：广东省科技计划项目（２００９Ｂ０１０８０００１２） 作者简介：王仁红（１９８２一），女，湖南邵阳人，硕士研究生，主要研究无线传感网络及数据处理；廖惜春， 教授，硕士生导师。通信作者，主要研究无线传感网络及数据处理． 第２５卷第２期 王仁红等：改进的Ａ 算法在Ａｄ Ｈｏｅ网络中的应用 ３９ ＡＯＤＶ）、动态源路由协议（Ｄｙｎａｍｉｃ Ｓｏｕｒｃｅ Ｒｏｕｔｉｎｇ，ＤＳＲ），这类算法在需要通信的时候才进行查 找路由的操作，从而避免了广播风暴．ＡＯＤＶ路由算法是应用较多的按需路由算法，该算法的协议 效率不高、通信质量不能保证．本文针对Ａｄ Ｈｏｅ网络的不足，将Ａ・按需路由算法应用于Ａｄ Ｈｏｃ 网络中． １ Ａ木算法的基本原理 Ａ・算法在人工智能中是一种典型的启发式搜索算法【７】．启发式搜索就是在状态空间中对每一个 搜索的位置进行评估，得到最佳位置，再从这个位置进行下一步搜索，直到找到目标．这样可以省 略大量无畏的搜索路径，提高效率．在启发式搜索中，对位置的评估十分重要，采用不同的估价函 数效果不同．本文所采用的启发的估价函数表示为：ｆ（ｎ）＝ｇ（”）＋ （ ）．其中，ｆ（ｎ）是节点 的估价 函数，体现了搜索的启发信息；ｇ（ ）是在状态空间中从初始节点到刀节点的实际代价，是已知的； ＾（”）是从 到目标节点最佳路径的估计代价． Ａ・算法通过ＯＰＥＮ和ＣＬＯＳＥ表选择、保存节点，其中，ＯＰＥＮ表是路由查找过程中的一个链 表，用来保存最终的路由路径，ＣＬＯＳＥ表记录已访问过的节点．首先将起始点 放入ＯＰＥＮ表， ＣＬＯＳＥ表置空，算法开始，其主要思路用ｃ＋＋语言格式表述如下： １）若ＯＰＥＮ表不为空，从表头取一个结点 ，该节点”可能是目标节点，也可能只是当前 Ａｄ Ｈｏｃ网络中的一个普通节点，若ＯＰＥＮ表为空，则失败退出； ２）判断刀是否为目标解，如果是，终止算法；否则进行下一步； ３）将门的所有的后继节点（即Ａｄ Ｈｏｃ中与节点ｎ可以直接通信的节点。源节点除外）展开， 即把与玎直接关联的子节点放在ＯＰＥＮ表中，并把Ｓ放入ＣＬＯＳＥ表，同时计算每一个后继节点的 估价函数．厂（ ）．将ＯＰＥＮ表按．厂（ｘ）排序，最小的放在表头，转到步骤１． ２基于改进Ａ木算法的Ａｄ Ｈｏｅ路由算法 ２．１ 改进的Ａ 算法描述 Ａ・算法广泛应用于有线网络最优路径求解以及一些策略设计中，在无线Ａｄ Ｈｏｃ网络的路由查 找过程中，需要对Ａ・算法做如下改进． ａ）把上述第３步替换为“将 的所有与父节点直接相连的下一层子节点放人ＯＰＥＮ表中（程 序代码为ｐ－＞ｎｏｄｅ＝ｎ），同时把ｎ放人ＣＬＯＳＥ表中，计算启发式函数值，保存在节点信息中，并且 用后向指针指向 的当前节点即父节点，用于从目标点回溯，确定最终的路由，然后返回步骤１”． ｂ）将选定的初始节点保存在ＣＬＯＳＥ表中，然后选择次优节点．从源节点到目的节点的搜索过 程中。算法总是选择估价函数，（ ）值最小的节点作为搜索的节点；并且每一个被验证了的节点不仅 要保存其子节点信息。还要保存次优节点的信息，以便路由寻找过程中保证全局最优，如果有节点 退出，若该节点是表头节点，则将次优节点放人表头，重新往下搜索． ｃ）当搜索一个节点时，若该节点不是目标节点且拥有子节点，则基于Ａ・算法的搜索将其所有 的子节点都放进ＯＰＥＮ表中并根据函数ｆ（ｎ）值按升序排列．在无线Ａｄ Ｈｏｃ网络的路由搜索中，为 了适应网络特征，这些子节点不仅集中保存，而且被各自的父节点单独保存，它们的父节点还保存 源节点到目标节点的路径． 五邑大学学报（自然科学版） ２０１１罐 Ａｄ ＨＯＣ网络中的路由算法归根到底是找出源节点到目的节点之间的路由，实现快捷有效的通 信，改进后Ａ・算法路由算法的路由保存在ＯＰＥＮ表里．本文提出的改进型Ａ・算法主要有２个过程： 一个是从源节点进行广度搜索ｌ ，即从初始状态逐层向下寻找，直到找到目标节点为止，其中删除 了不能扩展的（非目的）节点，以降低算法复杂度；另一个是从目标节点至源节点进行回溯，从而 确定最后的路由．具体步骤如下： １）首先把源节点和与源节点通信范围内的节点放进ＯＰＥＮ表（按节点与源节点之间的估价函 数值升序排列），并清空ＣＬＯＳＥ表，再将源节点放进ＣＬＯＳＥ表中； ２）如果ＯＰＥＮ表为空，则退出算法，查找失败；否则转步骤３）； ３）从表头取一个节点，如果该节点的子节点不在ＯＰＥＮ表中，则把该节点的子节点按照评估 函数值升序排列．该节点，ｌ可能是目标节点，也可能只是当前Ａｄ Ｈｏｃ网络中的一个普通节点，判断 ，ｌ是目标解吗？如果是，终止算法。否则下一步； ４）把节点，，放进ＣＬＯＳＥ表中同时把刀的估价函数值也放进ＣＬＯＳＥ表中，令，ｌ指向“源节点”。 即该节点的前驱节点，循环判断节点，｜的所有子节点，如果是目标节点则退出循环。否则判断是否 是叶子（无子节点的）节点，如果是，则删除该节点，否则转向步骤３）； ５）清空ＯＰＥＮ表，在ＣＬＯＳＥ表中，从目的节点开始，沿着后续节点回溯，直到源节点。把这 条路径中的节点按照顺序放进ＯＰＥＮ表作为最终的路由路径（如果回溯的过程中发现有一节点退出 网络，则选择次优节点进行回溯）． ２．２肩发式函数的选择 启发式函数是依赖启发信息帮助寻找目的节点的数学表达式，其表达方式有很多种。考虑到Ａｄ Ｈｏｃ网络中的节点都是自备电源且处理能力有限等实际情况，本文选择了基于最小跳数的启发式函 数，以从源节点 到目的节点 的最小路由跳数（如图２所示）为例。算法首先从 出发，把 放 进封闭表，同时把 的３个子节点放进开放表，然后检验３个子节点 ｌ，Ｓｎ２ ３．如果以最大通信范 围５００ ｍ作为每一跳的标准，则启发式函数对应 。， ３的代价分别是ＪＩ，（ １）＝ ／５００，ＪＩｌ（ ２）＝ ２／５００和ＪＩＩ（ ３） ３／５００，相应的评估函数的返回值是ｆ（Ｓ １）＝１＋ ｌ／５００，厂（ ２）＝ｌ＋ ２／５００和 ｆ（Ｓ ３）＝１＋ ３／５００． 圈１ 一个最小跳数路由的示意图 ２．３路由选择的数据包格式 改进后的Ａ・算法数据包格式包括：源地址、源位置、目标地址、目标位置、次优节点的信息、 ＣＬＯＳＥ表中全部节点的信息．它比经典算法增加了次优节点信息字段以提高路由速度．次优节点信 息包含节点指示信息、父节点指示信息以及估价函数的代价；ＣＬＯＳＥ表中全部节点的信息包含搜索 节点的指示信息、父节点的指示信息以及估价函数代价；源地址就是源节点的ＩＰ地址；源位置是源 第２５卷第２期 王仁红等：改进的Ａ｝算法在ＡｄＨｏｅ网络中的应用 ４１ 节点的物理位置；目标地址是目标节点的ＩＰ地址；目标位置是指目标节点的物理位置 ３仿真及结果 在Ｗｉｎｄｏｗｓ ＸＰ＋ＣｙｇＷｉｎ＋ＮＳ２．３３软件环境下，对上述改进的Ａ’算法与ＡＯＤＶ、ＤＳＲ算法进行对 比仿真． 实验中的网络拓扑分别由５、１０、２０…１００个节点组成，这些节点随机分布在１ ０００ ｍ ｘ １ ０００ １ＴＩ 区域内，形成Ａｄ Ｈｏｃ网络，链路带宽为Ｉ Ｍｂｉｔ／ｓ，仿真通信采用大小为５１２ ｂｙｔｅ的定长数据包，节 点最大移动速率为ｌ０ ｍ／ｓ，路径的端节点随机选出．实验中，对每组参数都进行了１Ｏ次仿真实验， 并取其平均值作为考察依据． ３．１ 节点数目和对应丢包收包比的关系 不同节点数目下３种算法的丢包 ２０ 收包比的比较如图２所示．从图２可以 看出：随节点数目的增多，３种算法的 ：： １４ 丢包收包比都有所上升，但ＤＳＲ升得 相对快一些；Ａ・考虑了节点的剩余能 量，通过平衡各个节点的能量消耗延 长网络的生存时间，保证了更多的数 ：： ８ 。 ２ 据得以传输；ＡＯＤＶ相对较好一些，但它仅维护一条到目的节点的路由， 在一定程度上影响了成功率． ３．２停留时间对算法性能的影响 ０ 节点数 图２发包成功率随节点数的变化图 不同停留时间各算法的性能比较如图３所示．图３－ａ是不同停留时间下各算法的平均端到端传 输时延，ＤＳＲ的延迟时间较长，Ａ 的传输时延比ＡＯＤＶ要短一些，这是由于Ａ 在路由查找过程中 及时有效地去除了不需要的路由信息（非最优的节点和路径）．不同停留时间下各算法开销如图３－ｂ 所示，３种算法的算法开销随着停留时间的增加相应地减少，最后都趋向平稳，ＤＳＲ算法开销明显 高于ＡＯＤＶ和Ａ・，ＡＯＤＶ与Ａ坝８几乎相同（ＡＯＤＶ稍微高一点）． 芒 ０ 哲 嬗 穰 露 ＝ 擐 懊 蜮 ０ ５０ １００ １ ５０ ２００ ２５０ ３００ ３５０ ４００ ４５０ ５００ 停留时间／０ 停留时间／ｓ ａ．平均端到端时延的比较 ｂ．算法开销的比较 图３停留时间对算法性能的影响 ４２ 五邑大学学报（自然科学版） ２０１１年 ３．３丢包与收包的比率和传输速率之间关系 不同算法的丢包与收包的比率和传输速率的关系如表ｌ所示（表中数据是在节点数为５０的条 件下的仿真结果）。由表Ｉ可知：随着传输速率的增加，Ａ・算法数据包的接收数目迅速增加。当传 输速率大于３００ ｋｂ／ｓ时，丢包与收包的比例也迅速逼近０；ＤＳＲ的丢包收包比下降最为缓慢，在较 高速率（５００ ｋｂ／ｓ及以上）时逼近０． 表１ 不同算法的丢包与收包的比率和传输速率的关系 ４结束语 本文结合Ａ・算法提出了一种自适应的Ａｄ Ｈｏｃ按需路由选择算法，与其他Ａｄ Ｈｏｃ网络路由技 术相比，本算法具有如下优势：１）算法不需要事先知道网络的拓扑结构，利用通信范围能确定所 有的网络节点，且利用启发式搜索发现节点，获得近似最优的路由路径；２）算法有良好的可扩展 性和自适应性，能够完成无线Ａｄ Ｈｏｃ网络的路由选择功能，并进一步能够避免广播风暴；３） 在启发式函数的作用下，算法不仅能够发现最优路径，还避免了贪心算法导致的局部最优问题；４） 算法简单易行，效率高．仿真实验证明，本算法具有良好的路由查找性能、降低了端到端的延迟、 算法开销等，具有良好的可扩展性和自适应性． 参考文献 【Ｉ】ＭＥＲＫＬＥ Ｄ，ＭＩＤＤＥＮＤＯＲＦ Ｍ，ＳＣＨＭＥＣＫ Ｈ．Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ｒｅｓｏｕｒｃｅ－ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｊｅｃｔ ｓｃｈｅｄｕｌｉｎｇ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００２，８（４）：３３３－３４６． 【２】ＺＯＵ Ｌｉａｎｇ，ＸＵ ｌｉａｎｍｉｎ，ＺＨＵ Ｌｉｎｇｘｉａｎｇ．Ｉｍｐｌｅｍｅｎｔ ｏｆ Ａ’ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｐｒｏｂｌｅｍ ｉｎ ｄｙｎａｍｉｃ ｎｅｔｗｏｒｋｓ［Ｊ］：Ｊｏｕｒｎａｌ ｏｆ Ｓｈｅｎｚｈｅｎ Ｕｎｉｖｅｒｓｉｔｙ：Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，２００７，２４（Ｉ）：３２－３６． 【３】沈辉。石冰心。邹玲，等．Ａｄ Ｈｏｃ网中基于熵的长寿分布式ＱｏＳ路由算法【Ｊ】．软件学报。２００５，ｌ６（３）：４４５－４５２． 【４】ＫＯ Ｙ Ｂ，ＶＡＮＤＹＡ Ｎ Ｈ．Ｌｏｃａｔｉｏｎ・ａｉｄｅｄ ｒｏｕｔｉｎｇ ｉｎ ｍｏｂｉｌｅ Ａｄ Ｈｏｃ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｗｉｒｅｌｅｓｎｅｔｗｏｒｋｓ，２０００，６（４）： ３０７．３２１． 【５】ＹＡＮＧ Ｓｕｑｉｏｎｇ。ＬＩＮ Ｂｉｑｉｎ。ＨＥ ｗｅｉ．Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｓｅａｒｃｈ ｆｏｒ ｍａｐ ｐａｔｈ ｂａｓｅｄ ｏｎ Ａ’ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｒａｉｌｗａｙ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎ，２０００，ｌ９（４）：８－１ １． 【６】严蔚敏．数据结构：Ｃ语言版【Ｍ１．北京：清华大学出版社，１９９２． 【７】郭亚军。鲁汉榕．动态环境中的一种实时启发式搜索算法【Ｊ】．空军雷达学院学报，２０００，ｌ４（４）：５８・６０． 【８１谢希仁．计算机网络【Ｍ】．５版．北京：电子工业出版社，２００８．
