ＩＳＳＮ １００９－３０４４ Ｅ—ｍａｉｌ：ｉｎｆｏ＠ｃｃｃｃ．ｎｅｔ．ｅｌｌ ｈｔｔｐ：／／ｗｗｗ．ｄｎｚｓ．ｎｅｔ．ｃｎ Ｔｅｌ：＋８６—５５ ｌ一５６９０９６３ ５６９０９６４ Ｃｏｍｐｕｔｅｒ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ电瞎知识与技术 Ｖｏ１．７，Ｎｏ．４，Ｆｅｂｒｕａｒｙ ２０１ １，ＰＰ．７７５—７７６ １种基于优化算法的无线传感器网络定位算法 王晓丽．陈天煌 （武汉理丁大学计算机科学与技术学院，湖北武汉４３００６３） 摘要：该文提出一种基于遗传模拟退火算法的定位算法。在现有的定位算法ｑ－，ＤＶ—Ｈｏｐ算法的硬件开销小，但定位精度不高，当网 络中节点的跳数大于或等于２时，未知节点与锚节点之间的估计距离会产生较大的误差，为此本文将遗传模拟退火算法用于ＤＶ— Ｈｏｐ算法中，以提高节点间的平均每跳通信距离估计精度，进一步提高定位精度。仿真结果与分析表明，新算法的定位精度有一定 的提高。 关键词：定位算法；遗传算法；模拟退火；ＤＶ—Ｈｏｐ 中图分类号：ＴＰ３１１ 文献标识码：Ａ 文章编号：１００９—３０４４（２０１１）０４—０７７５—０２ 无线传感器网络（Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ，ＷＳＮ）是由大量的廉价微型传感器节点通过无线通信方式形成的一个多跳的自组织网 络系统，而定位是ＷＳＮ的一个关键问题。节点准确地进行自身定位在无线传感器网络的应用中非常重要。首先，传感器节点采集到 的数据必须结合其位置信息才有意义，否则，如果不知道数据所对应的地理位置，数据就失去意义。其次，无线传感器网络节点自身 定位还可以在外部目标的定位和追踪以及提高路由效率等方面发挥作用。因此，实现节点的自身定位对无线传感器网络有着重要 的意义。 现有的ＷＳＮ定位算法是根据少量的位置已知的节点（锚节点）以及它们与其他节点的通信信息来估算整个网络中每个节点的 位置。ＷＳＮ定位算法可分为基于距离信息（Ｒａｎｇｅ—Ｂａｓｅｄ）和不基于距离信息（Ｒａｎｇｅ—Ｆｒｅｅ）两类，前者是根据节点间的距离或角度等 信息定位，后者仅仅根据节点间的连通信息实现节点定位。本文主要是对不基于距离信息的定位算法ＤＶ—Ｈｏｐ进行研究并改进。 ｌ ＤＶ—Ｈｏｐ算法 １．１ ＤＶ－Ｈｏｐ算法 ＤＶ—Ｈｏｐ算法由 个阶段组成。 第一阶段，使用典型的距离矢量交换协议，使网络中所有未知节点获得距初始锚节点的跳数； 第二阶段，在获得其他锚节点位置（Ｘ。，Ｙ．）和相隔跳数后，各锚节点（ Ｙｊ）利用所收集的信息按式（１）计算平均跳距： ＾。 一 ＿｛∑ ∑√（ 一 ） ＋ｌ Ｊ＝ｌ ＝ｌ ） 式中ｓ．是锚节点ｉ的平均每跳距离，ｈ 为节点ｉ和节点ｊ之间的跳数；然后将平均每跳距离作为一个校正值广播至网络中。校正 值采用可控洪泛法在网络中传播，这意味着一个节点仅接收获得的第一个校正值，而丢弃所有后来者，这个策略确保了绝大多数节 点可以从最近的锚节点接收校正值。在大型网络中，可通过为数据包设置一个１丫ｒＬ域来减少通信量。当接收到校正值之后，节点根 据跳数计算与锚节点之间的距离。 第三阶段，在二维空间中，一旦一个未知节点获得与３个或更多锚节 点的距离后，执行三边测量法或最大似然估计法计算自身的位置。 如图１所示，已知信标节点Ｌ。与 ，Ｌ 之间的距离和跳数。Ｌ：计算得 到校正值（即平均每跳距离）（４０＋７５），（２＋５）＝ｌ６．４２。假设Ａ从 获得校正 值，则它与３个信标节点之间ｄｌ＝３￣１６．４２，ｄ２＝２ｘ１６．４２，ｄ３＝３ｘ１６．４２，然后使 用三边测量法确定节点Ａ的位置。 １．２ ＤＶ—Ｈｏｐ算法中锚节点平均每跳距离现有的改进方法 原ＤＶ—Ｈｏｐ算法的主要误差在于计算未知节点与锚节点之间的估计 距离时，是用跳数乘以平均每跳距离来表示，而当网络中的跳数大于或等 于２跳时．未知节点与锚节点之间的实际距离与跳数乘以平均每跳距离所 图１ ＤＶ—Ｈｏｐ算法示意图 得的值．存在较大的误差，因此如何提高锚节点的平均每跳距离的估计精度是本文改进的出发点。 文献ｆ２１中对算法改进的思想为： 当所有的节点获得每跳距离后，使用公式Ｈｏｐｓｉ：ｅｏ．￣ ∑Ｈｏｐｓｉ：ｅ￣’”（其中Ｈｏｐｓｉｚｅｉ为单个节点的每跳距离，ｎ为锚节点个数）计算 全网平均每跳距离，并将该值用于ｄｌ＿ｈｏｐｓ Ｈｏｐｓｉｚｅ 中，计算未知节点与锚节点之间的距离。 文献【３１中对算法改进的思想为： 未知节点在接收多个锚节点的平均每跳距离后，对各锚节点估计的平均每跳距离作归一化加权处理．离未知节点越近的锚节 收稿日期：２０１０—１２—１２ 作者简介：王晓丽（１９８５一），女，山西忻州人，武汉理工大学计算机学院在读研究生，主要研究方向为计算机网络与数据库技术。 本栏目责任编辑：冯蕾 Ｃｏｍｐｕｔｅｒ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ电脑知识与技术 点的权俯越大 第７卷第４期（２０１１年２月） 锚节点ｉ估计的平均每跳距离为Ｓ 、未知节点距锚节点ｉ的跳数为Ｎ．，其中ｉ＿ｌ，２…。设未知节点共收到ｋ个锚节点的信息， 每个铺节点的平均每跳距离的加权值为Ｗ ，则取『厂 （— １（∑Ａ ）～，即锚节点ｉ的权值等于未知节点到锚节点ｉ的跳数的倒数除 一 』 ｌ 盘 Ｉ 三 ．以陔术知 点到各铺竹点的跳数的倒数和。南各锚节点估计的平均每跳距离，可得未知节点的平均跳距为－ ∑， ，即未知节 点的平均每跳估汁等于各锚节点估计的平均每跳距离的加权和。 文献【６］中埘算法的改进思想为： 为＿ｒ充分利用各锚节点的信息，未知节点不仅仅记录接受到的第一个平均每跳距离，而是记录所有锚节点的平均每跳距离，然 后进行加权平均。考虑到各锚节点距离未知节点的远近不同，对不同锚节点的平均每跳距离赋予不同的权值，权值取决于未知节点 与锚节点之间的跳数值，按跳数值大小的反序分配。举例说明，未知节点Ａ收到Ｌｌ，Ｌ２，Ｌ３的平均每跳距离分别为Ｄ１，Ｄ２，Ｄ３。Ａ到 Ｌ１，Ｌ２，Ｌ３的跳数分别为ｌ，２，３。则Ａ分配给Ｄｌ，Ｄ２，Ｄ３的权值分别为３，２，１，用公式为（Ｄｌ＊３＋Ｄ２＊２＋Ｄ１ １）／（１＋２＋３）进行加权平 均 ２基于遗传模拟退火算法的定位算法 遗传算法（ＧＡ）和使拟退火算法（ＳＡ）是使用较为广泛的优化算法。遗传算法是一种全局高效的搜索算法，它是通过模拟自然界 的牛物进化机制而发展起来的随机优化方法。它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程 以求得最优解，但它却容易陷人局部最小解。相反，模拟退火算法如果初始温度较高，降温速率较低，可以克服局部最小解。因此本 文提出遗传模拟退火算法将全局搜索的ＧＡ和局部搜索的ＳＡ相结合，以得到性能更好的算法。 遗传模拟退火算法混合策略是一个两层并行搜索结构。内部层次上，混合算法在各温度下串行的依次进行遗传算法和模拟退 火算法搜索，是一种两层串行结构。其中，模拟退火算法的初始解来自遗传算法的进化结果，模拟退火算法经Ｍｅｔｒｏｐｏｌｉｓ抽样过程得 到的解又成为遗传算法进一步进化的父代种群。外部层次上，遗传算法提供了并行搜索结构，使模拟退火算法转化成为并行模拟退 火算法，因此混合算法始终进行种群并行优化。 改进的ＧＡＳＡ算法中根据交叉和变异概率．对初始种群进行交叉、变异操作，进而对得到的新种群利用模拟退火算法中的 Ｍｅｔｒｏｐｏｌｉｓ准则决定它们是否进入下一代种群，然后把这个种群又作为父代种群继续下一代的遗传操作，整个过程反复、迭代，直到 达到终止条件 ＧＡＳＡ的个体编码 针对ＷＳＮ节点数目较多。计算量大，且二进制编码不能直接反映所求问题的结构特征，本文的定位算法采用实数编码，这便于 与模拟退火算法的结合．并且可以改善算法的汁算复杂度．提高运算效葺墨。 ＧＡＳＡ的适应度函数 本文中，遗传模拟退火算法的适应度丽数定义如下： ∑ｌ ＝ｔ ０一√（ 一ｘｊ｝ ＋（１ 一１‘Ｊ１ １ １ 其巾，Ｈｏｐｓｉｚｅ 是锚节点的平均每跳距离，ｎ 是锚节点ｉ与锚节点ｊ之间的跳数，ｘ…ｙ）是锚节点的坐标位置，（ｘｊ，ｙ＿）是锚节点Ｊ的 坐标位置。 ＧＡＳＡ的算子设计 选择算子采用ＳＡ的Ｍｅｔｒｏｐｏｌｉｓ接受准则；交叉算子采用算术交叉算子；变异算子采用保优，均匀变异。 ＧＡＳＡ的终止条件 当迭代次数达到预定次数或者群体的成熟度满足一定条件时，停止迭代。 本文中拟采用ＧＡＳＡ算法来求锚节点平均每跳距离的最优解，以使ＤＶ—Ｈｏｐ算法的定位精度有所提高。 ３结束语 节点定位是无线传感器网络的一项关键技术，无需测距定位算法将是定位算法的主流。本文对无需测距的定位算法ＤＶ—Ｈｏｐ 进行分析，针对它存平均每跳距离可能产生的误差，提出了一种改进的方案，以提高节点定位精度。 参考文献： ［１１郭永红，万江文，于宁，等．基于跳数的无线传感器网络定位求精算法【Ｊ】．计算机Ｔ程，２００９（３）． ［２１ ＣＨＥＮ ＨＯＮＧ—ＹＡＮＧ，ＳＥＺＡＫＩ Ｋ，ＤＥＮＧ ＰＩＮＧ，ｅｔ ａ１．Ａｎ ｉｍｐｒｏｖｅｍｅｎｔ ＤＶ—ＨＯＰ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｚ］． ｆ３１刘锋，张翰，畅骥．一种基于加权处理的无线传感器网络平均跳距离估计算法『ｌｌ】．电子与信息学报，２００８，３５（５）：１２２１一ｌ２２４． 【４１张佳，吴延海， 峰，等．摹于ＤＶ—ＨＯＰ的无线传感器网络定位算法『Ｊ１．计算机应用，２０１０，３０（２） ［５］唐鹭，洪月华，伍华健．无线传感器网络节点定位综合算法［Ｊ］．计算机工程与应用，２０１０，４６（４）． 【６］刘明，包亚萍，刘汉义．无线传感器网络巾一种改进的ＤＶ—Ｈｏｐ算法ｌＪ】．微计算机信息，２００９． ７７６网络通讯及安全 本栏目责任编辑：冯蕾