一种基于遗传算法的无线传感器网络节点定位技术研究.

1、井冈山大学学报（自然科学版 文章编号：1674-8085（201104-0071-05 一种基于遗传算法的无线传感器网络节点 定位技术研究 廖萍，孔翠香 （井冈山大学电子与信息工程学院,江西，吉安 343009 摘要：本文分析了基于误差的最小二乘估计定位原理，提出一种基于遗传算 法的无线传感器网络节点定位技术。建立所有节点的定位误差之和最小的数学模 型，利用遗传算法求解模型的最优解，从而得到未知节点的最优的估计位置。实验 仿真结果表明该算法对未知节点的定位精度高，条件简单，适合各种规模的无线传 感网络节点的定位。 关键词：无线传感器网络；定位；遗传算法；锚节点 中图分类号：TP393.02 文

2、献标识码：A DOI:10.3969/j.iss n.1674- 8085.2011.04.018 STUDY ON A LOCALIZATION TECHNOLOGY OF WIRELESS SENSOR NETWORK BASED ON GENETIC ALGORITHM LIAO Pi ng， KONG Cui-xia ng (School of Electronic and Information Engineering, Jinggangshan University, Ji Jian gxi 343009,Ch ina Abstract: We an alyze the short

3、co mings of the least squares estimati on localizati on algorithm in Wireless Sen sor an, Network. A no vel localizati on Tech no logy based on gen etic algorithm for Wireless Sen sor Network is proposed. The mathematical model was built with the smallest error for all of no des, and the gen etic al

4、gorithm was used to get the optimal soluti on of the model. Fi nally, we can get the optimal estimate positi on of the unknown no des. The results of the simulation show that the localization accuracy of the algorithm is efficient for the no des of the Wireless Sen sor Network, and its con diti on i

5、s simple so that suitable for all sizes of wireless sen sor n etworks. Key words: wireless sen sor n etwork; localization; genetic algorithm; anchor node 0 引言 无线传感器网络是由部署在检测区域， 具有通信与计算能力的传感器节点组成 的自组织分布式网络系统，其作用是协作式的感知、采集和处理网络监测区域内的 信息并发送给检测者1。传感器节点采集或感知的数据不知道具体的位置信息是 毫无意义的2 ，因此传感器节点定位技术是无线传感器网络应用中的关

6、键技术之一 3-4 。 虽然采用 GPS 定位系统可以精确得到每个节点 的位置，但高昂的成本使 GPS 定位不能广泛应用于传感器节点的定位。现有 的无线传感网络定位算法大多依据少量位置已知的锚节点来估计整个网络中未知节 点的位置。常见的无线传感器网络定位算法可分为基于测距 5的定位算法以及与 距离无关的定位算法。基于测距的定位算法（如 RSSI 6-10、TOA 和 TDOA ）在定位过 程中需要测量节点间的距离或角度信息，该定位算法对节点的硬件要求较高并受测 量环境的影响较大。而无需测距的定位算法在定位过程中无需测量节点间的距离或 角度信息，而是 第 32 卷第 4 期 V 01.32 No

7、.4 井冈山大学学报（自然科学版 2011 年 7 月 July 2011 Journal of Jinggangshan University （Natural Scienee 71 收稿日期：2011-04-18；修改日期：2011-06-10 基金项目：吉安市重点科技计划项目（吉市科技字200940 号 作者简介：*廖萍（1980-，男，湖南衡阳人，讲师，主要从事计算机应用、计 算机网络、无线传感器网络等研究（Email: jxjgsliaopi ; 孔翠香（1978-，女，陕西渭南人，讲师，硕士，主要从事无线传感器网络、 Ad hoc 网络等研究（Email: . 井冈山大学学报（自然

8、科学版 72 采用节点间的估算距离来实现节点的定位，如 Radhika NagpaI 等提出 Amorphous 11定位算法，以 及 Dv Hop 算法，这类定位算法硬件成本低、功耗小、 但定位精度较差。 以上定位算法均具有自身的特点，但它们的定位精度都不够理想，且在定位最 后阶段均采用最小二乘估计定位算法估算未知节点的位置。 1 基于误差的最小二乘估计定位原理 大多数定位算法对未知节点的计算是通过获知三个或三个以上锚节点间的距 离， 运用最小二乘法估计法估计出未知节点的位置。最小二乘估计的定位原理可描 述为：当已知 k 锚节点的位置 ,(11y x ,，,(k k y x 以及它们距离待测

9、节点 ,(y x 之间的距离为 1r ,，k r 时，可得方程组 222 111222 (k k k x x y y r x x y y r ? -+-= ? ? -+-= ? (1) 该方程组为非线性方程组，不便于求解，用(1)式中的前 1k -个方程减去第 k 个方程后，可以得到 Ax B =形式的线性方程组，其中 11112( 2( 2( 2( n n n n n n x x y y A x x y y - ? ? ? ? =? (2) 222222 111222222111k k k k k k k k k x x y y r r B x x y y r r - ? -+-+-1 i

10、i e e B Ax =-=- 取值达到最小来求 x 的估计 ?=? (3) 用最小二乘法估计求未知节点的位置(,x y ,但是由于最小二乘法用前 1k -个方程减去第 k 个方程的思路求解，解的精确程度受最后一个方程误差的限 制，如果最后一个方程误差较大的话，即使前 1k -个方程误差很小，定位结果的 误差也会较大。由此引入误差项，用前 1k -个方程减去第 k 个方程得 1112222221111 11222222111 2( 2( _2( 2( k k k k k k k k k k k k k k k k k k x x x y y y e e x x y y r r x x x y

11、y y e e x x y y r r -+-+-= ? -+-+- ?即：(i Ax e e B +-= 式中(i e e -项为误差项，其为 1k -维随机误差向量，根据最小二乘原理求解 方程使 值，对上式关于 x 求导并令其等于 0,可以求解出未知节点的最小二乘位置估 计 A 1（ T T X A A A B -= （ 4） 该算法依据节点的测距信息进行定位，测距误差的存在可能引起较高的定位误 差。本文从最小二乘估计法出发，引入遗传算法来完成传感器节点定位。 2 基于遗传算法的无线传感网络节 点定位 遗传算法是一种借鉴自然界生物的遗传和进化过程而形成的自适应全局随机搜 索与优化算法。它将

12、问题的所有可能解组成一个种群，将每一个可能解视为种群的 个体，从选定的初始种群（解）出发，在整个种群空间内随机搜索，按照一定的适 应度函数评估每一个体，循环使用选择、交叉、变异三种遗传算子，使问题的解不 断进化，直至搜索到最优解。 文献12在第 1 阶段利用采样方法对节点初始位置进行初步估计，在第 2 阶段 采用遗传算法对节点初始位置进行求精； 文献 13 用遗传算法优化定位参数； 文献 14用遗传算法对无线传感网络节点定位及求取其路径；本文提出一种新的无线传 感网络节点定位算法。 遗传算法完成节点定位的基本步骤如下： （1 个体的编码 编码是把问题的可行解从解空间转换到遗传算法所能处理的搜索

13、空间的转换方 法。目的是为了随机产生一组侯选变量，可以采用多种形式编码（如二进制编码、 符号编码与符点数编码），通常采用二进制形式，即用 0, 1 字符串构成一定长度 的基因链，表示个体变量，从遗传算法解空间转换问题空间称为解码。 本文对个体的编码米用二进制编码。二进制编 井冈山大学学报(自然科学版 73 码中我们将每个个体的基因值用 1,0(区间均匀分布的随机数来表示，个体位 置的纵坐标与横坐标的编码长度均为 10 位。 (2 种群的初始化 假设网络中共有 K 个未知节点，坐标可表示为 11(, , ,(, j j x y x y，(1,2,3, , j K =，第 j 个未知节点的坐标用向

14、量 j X 表示，其 中 N个节点为锚节点，位置 11(, , ,(, i i a b a b，(1,2,3, , i N =。第 i 个锚节点的坐 标用向量 j A表示，j X 可以与 3 个锚节点可以通信，设这三个锚节点坐标分别为 (, i i a b， (1,2,3 i =中的任意三个锚节点，随机产生 100M =个个体 I M (1,2,3, ,100 l =作 为初始种群，每个个体的位置(,I I m c (1,2,3, ,100 I =。 (3 遗传定位算法的适应度函数设置在遗传算法中的适应度函数设为 (,min (K j j j f x y = 叫)， (1,2,3, , j K

15、 =，(1,2,3, , i N =中的任意三个，其中(,j j x y 是第 j 个未知节点的 坐标，(,i i a b 是第 i 个锚节点的坐标, id 是第 i 个未知节点与锚节点的距离。这样就将节点定位问题转化为模型优 化问题， 即上式的最优解即是未知节点的估计位置。 （4 选择算子的选取 选择也称为复制，根据变量集中每个个体变量的适应度值或一定概率值对群体 中的个体进行选择和淘汰，其目的是为了避免基因缺失、提高计算效率和全局收敛 性，产生最优的群体。因此遗传算法中的优良个性可以一直繁殖下去。 选择算子采用基于适应度的赌轮选择法。其基本思想是：每个个体被选中的概 率与其适应度大小成正比

16、，设群体大小为 100M =，个体 i 的适应度为（f i，那么个 体 i 被选中的概率 p ix 可表示为：1 （ （ ix M i f i p f i = E,计算所有个体的适应度值，并对它 们按照从大到小的顺序进行排序。具体的选择方法是依据每个个体的适应度值 进行选择：即适应度值高的个体被遗传至下一代群体中的概率大；适应度 值较低的个体被遗传至下一代群体中概率较小。 （5 交叉率的选取 交叉（也叫重组）是在通过较大概率从群体中选择出来的两个不同的个体变量 之间互换部分代码（交叉运算或基因重组）。遗传算法中交叉概率 p c 的选择是影响遗传算法性能的关键，p c 越大，新个体产生的速度越快

17、，而 pc过大时，遗传算法被破快的可能性也越大，使得具有高适应度的个体结构很快 被破坏，但如果 pc 过小，会使搜索过程缓慢或者停滞不前，因此需要不停的反复 实验来确定合适的 pc 来找到问题的最佳解， 我们选择个体以概率 0.6c p =进行交叉，也就是选择出来新的个体里面的概率为 c p 需要进行基因重 组，经过重新组合产生下一代新个体，在交叉重组的过程中要尽量避免基因代码差 异较小的个体进行交叉，防止 近亲结合”产生不良个体。 假设交叉前两个选择出来的两个较优个体的编码分别为： 交叉前个体 A 的编码：01001011001101010 交叉前个体 B 的编码： 100110100110

18、01101 从第 16 开始到第 20 位的基因值进行基因重组，那么产生新的 个体A 和B，交叉后它们的编码分别为： 交叉后新的下一代个体A 的编码： 01001011001001101 交叉后新的下一代个体B 的编码： 10011010011101010 （6 变异 变异则是从产生新一代的A 和B 个体集合中选择很小一部分的个体（假设变 异概率 0.01m p =，将个体的基因代码的某一位或者某几位值做改变（变异运 算），将个体A第7位与第12位的基因值进行基因变异， 新的个体A变异前后 后它的编码分别为A与” A， 在二进制编码中的实现方法一般是将基因链中的某些位取反而实现。 变异前个体A

19、 的编码： 01001011001001101 变异后形成新的下一代个体A 的 编码： 01001001001101101 进行变异的目的是防止某些个体处于不变的状态而失去一些较有用的基因，来 参加变异的个体 井冈山大学学报(自然科学版 74 的概率应该很小，我们取 p m 迭代次数 孑 40 ill I I I I II 亦 20 _ - 昨 0 10 20 30 40 50 BO 70 30 90 10C 迭代汝数 线 40 ill I I I I II W 帛. . L I I ： 0 10 20 30 40 50 GO 70 30 50 10C 迭代次数 (7 这样循环迭代，直到迭代次

20、数达到预定次数，或者群体的解达到最优时, 停止迭代。 4 仿真实验及算法性能分析 4.1 环境及参数设置 为了更好、更准确的评价遗传算法定位优化的优越性，在 Matlab7.0 环境下进 行仿真，遗传算法的参数取值为：种群规模的初始值为 100,交叉概率设置为 6. 0=c p，变异概率设置为 01.0=m p，最大迭代次数设为 100,编码长度为 10。从 最优值的变化以及定位误差几个方面来观察遗传算法的定位性能。 4.2 仿真与结果分析 I I i i i 10 20 30 40 50 BO 70 80 90 100 迭代次数 4-0 jii ii iii ii i 20丄 Q I I I

21、 】 1 I I I 1 II 0 10 20 30 40 50 60 7Di 80 90 WO 迭代次数 40 加 0 4-0 I i i i i i i i P 20 _ - Q I * I I I I 0 10 20 30 40 50 60 70 80 90 100 迭代次数 40 I I 1 1 I I I P I 20 Qi I I * * I I I 0 10 20 30 40 50 60 70 80 90 100 迭代次数 40 r 20 A 0L 0 10 20 30 40 50 60 70 80 90 100 迭代次数 I I | . . L U 10 20 30 40 50

22、 60 70 80 90 100 迭代次数 40 20 0 迭代次数 40 20 40 i- 20 A 0L 0 5 Pj PI 40r 20 A 0L 0 1 1 1 1 1 I 1 1 1 | 【II 1 1 0 10 20 30 40 50 60 70 B0 90 100 迭代次数 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 GO 70 SO 90 100 0 10 20 30 40 50 60 70 80 90 100 0 迭代次数 40 20 0 注：表示锚节点的位置，G表示未知节点的估计位置，*表示未知节点的实 际位置 图 1

23、 遗传算法的定位结果 Fig.1 The localization result of the Genetic Algorithm 从图 1 可以看出，遗传定位算法的定位误差较小，定位性能很好。 从图 2 可以看出，每个未知节点的最优值随迭代次数的增加而快速衰减，在迭 代次数为 30 之后最优值几乎衰减为零，故迭代次数选择 30 即满足定位误差要求。 图 2 五个未知节点的最优值收敛图 Fig.2 The conv erge nee figure of optimal value for five unknown no des 图 3 五个未知节点的定位误差收敛图 Fig.3 The conv

24、 erge nee figure of localizatio n error for five unknown no des 从图 3 可以看出每个未知节点的定位误差随迭代次数的增加而快速衰减，在迭 代次数为 10 之后，定位误差趋于稳定，且定位误差的值收敛于 10%之下，表明遗 传算法的定位误差很小，定位精度很高，能够满足无线传感器节点的定位要求。 5 结束语 本文以最小二乘估计法为基础，阐述了一种基于遗传算法的无线传感网络改进 定位 算法的设计方案，建立了所有节点的定位误差之和最小的数学模型，利用遗传 算法求解模型的最优解，从而得到未知节点的最优的估计位置。实验仿真结果验证 了算法的有效

25、性，表明该算法对未知节点的定位精度高，因此本算法具有较好的实 用性，适合各种无线 井冈山大学学报（自然科学版 75 传感网络节点的定位。 参考文献： 1 彭爱平,郭晓松.基于二次栅格扫描的无线传感网络定 位算法J.传感技术学报，2009,22 (11:1650-1654. 2 Rabacy J J, Ammer M J, da Silva J r J L, et aJ Picorodio Supports Ad Hoc Ultra-low Power Wireless Networki ng J.Computer, 2000, 33 (7:42-48. 3 KIM S, KO J G, YOO

26、N J, et al . Multiple-objective metric for placi ng multiple base statio ns in wireless sen sor n etworksA.Proc of the 2rd Intern ati onal Symposium on Wireless Pervasive Comput ing. Piscataway, USA, 2007:627-631. 4 李建中,高宏.无线传感器网络的研究进展J.计算机研 究与发展,2008,45(1:1-15. 5 吕睿，阳宪惠.减少无线传感器网络节点定位误差的方 法J.清华大学学报,

27、2008, 48(S2: 1839-1843. 6 X Li , H C Shi, Y Shang. A sorted RSSI quantization based algorithm for sensor network localization The 11th Int l Confern Parallel and Distributed Systems,Japa n,2005. 7 LUTHY K A,E GRANT D,HENDERSON T C. Leverag ing RSSI for robotic repair of disc onn ected wireless sen sor n etworksA.Proceedi ngs of 2007 IEEE Intern ati onal Conference on Robotics