基于遗传算法和加权质心算法的无线传感器网络定位算法.pdfVIP

第25卷第6期 百 色 学 院 学 报 2012年 11月 Vo1．25一No．6 JOURNAL 0F BAISE UNIVERSITY NOV．2O12 基于遗传算法和加权质心算法 的无线传感器网络定位算法 程丽玲 ，谭 军 (百色学院 数学与计算机信息工程系，广西百色 533099) 摘 要： 文章通过研究质心算法的基本原理及定位算法的数学模型，对质心算法中的平均误差 值进行研究，再利用遗传算法对改进的模型进行优化。通过Matlab仿真 ，结果显示：使用遗传算法优 化无线传感器网络的定位问题 ，可以在较短的时间内得到精度较高的未知节点位置。 关键词 ： 无线传感器网络，节点 自定位 ，质心算法，遗传算法 中国分类号 ： TP393 文献标识码 ： A 文章编号：1673—8233(2012)O6一OO97一O7 1 引言 节点自定位技术是WSN很多应用的基础。定位问题本质上是一个基于不同距离或路径测量值的优化问 题，优化算法是解决优化问题的有力工具，遗传算法作为普遍使用的优化算法，近年来 已有国内外学者提出利 用其改进定位算法的性能。 遗传算法(GeneticAlgorithm)E卜是一类借鉴生物界的进化规律(适者生存，优胜劣汰遗传机制)演化而 来的随机化有哪些信誉好的足球投注网站方法，本质上其仍是一种有哪些信誉好的足球投注网站算法，依据生物进化原理，模拟基因重组与进化的自然过程，把待 解决问题的参数编成二或十进制编码(基因)，若干基因再组成一个个体，许多个体经过类似于 自然选择、配对 交叉和变异运算 ，经过世代遗传得到最优解 。 2 定位算法的数学模型 卜] 假设二维空间的网络中含有M个锚节点和1个未知节点。使用向量 一[ ，。，…，ZM]代表传感器网络中 锚节点的初始坐标。定位问题就是给定以上 M个锚节点的坐标，求与它们有通信约束关系的未知节点的坐 标 。假设未知节点坐标为(，3，)，测得锚节点与未知节点的距离分别为 d，d：，…，dM，则求解未知节点的位置 就是求解下面的方程 ： =i = = = 干 — 。 (z—zM) + ( —YM) =dM 由于环境或硬件因素，实际应用中距离测量值总是存在误差，因此定位运算的实质就是使式(2)的值最小， 收稿 日期 ： 2O12一lO一15 基金项 目： 百色学院科研项 目(2011KBo6)。 作者简介： 程丽玲 (1979～ )，女，壮族，广西平果县人，百色学院数学与计算机工程系讲师，主要研究方向为无线传感器 网络}谭军 (1979~ )，男 ，广西合浦县人，百色学院数学与计算机工程系讲师。 97 《百色学院学报}2012年第 6期 也即求该式的极小值点。可以利用遗传算法的随机有哪些信誉好的足球投注网站特性，按照一定的编码规则 ，建立以未知节点位置为参 数的定位优化模型，然后再使用遗传算法对优化模型进行求解参数 ，所得结果即为未知节点的估计位置。 M ． f(x，)一 l 下 一fI (2) 3 加权质心算法 。 质心定位算法L61](Centroid)是南加州大学的NirupamaBulusu等学者提出的一种仅基于网络连通性的 室外定位算法 。多边形的几何中心称为质心，多边形顶点坐标的平均值就是质心节点的坐标。该算法的核心 思想是：未知节点以所有在其通信范围内的锚节点的几何质心作为该未知节点的位置 。 假设这些坐标分别为(z ，。)、( ，Y)、…、(z ， )，