基于遗传算法的井下无线传感器网络节点定位研究

1、收稿日期:2010-01-08作者简介:陈 坤(1985- , 男, 安徽阜阳人, 2008年毕业于安徽理工大学电气与信息工程学院电子信息工程专业。基于遗传算法的井下无线传感器网络节点定位研究陈 坤, 李 莉, 李继云, 梁美玉(安徽理工大学电气与信息工程学院, 安徽 淮南 232001摘 要:为了进一步提高井下无线传感器网络待测节点定位精度, 文章提出了将节点定位算法和遗传算法结合在一起的基于遗传算法的节点定位算法, 通过迭代寻优, 提高定位精度。该算法是一种基于距离的三边测量定位算法, 根据待测节点到信标节点的距离推测出待测节点的坐标。实验结果表明, 该算法具有更高的定位精度。关键词:无线

2、传感器网络; 节点定位; 遗传算法中图分类号:TD655 文献标识码:A 文章编号:1671-0959(2010 10-0120-03W ireless Sensor Net work Nodes LocalizationM ethodof Underground CoalM ines based on G enetic A lgorith mL I L , i L I J i -yun , CHEN Kun , L I ANG M e i-yu(S chool of E lectrical and I n for m ation Eng i neeri ng , Anhu iUn ivers

3、 i ty of S ci en ce and Technol ogy , H uai n an Anhu i 232001Abstrac t :T o f urther enhance the l ocation prec isi on of unknown nodes i n w ireless sensor net w orks , a locati on m e t hodbased on genetic a l gor it hm i s presented :the comb i nation o fw ire less senso r net wo rk and genetic

4、a l gor ith m 1It can i m provepositi on i ng accuracy t hrough iterative opti m izati on 1T he m et hod is dependent on d i stance , wh i ch can g et the coo rdina tes of the unkno w n node t hrough the d i stance o f unknown node and known node 1F i na ll y, the resu lt is better 1K eywords :W S N

5、 s , N ode l o ca ti on , GA 由于矿井作业工作环境恶劣, 为了确保井下人员的安全, 在出现安全事故时实施及时有效的撤退搜救, 对井下人员的定位无疑成为重要的研究议题。无线传感器网络(W i re l ess Sensor N et wo rks , W S N s 就是由部署在监测区内大量的廉价传感器节点组成的集传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术于一体, 通过传感器与外界交互, 完成数据采集、处理及通信等功能, 具有分布协作性, 测量精度高, 范围广, 操作灵活和智能性的优点1, 2, 而定位作为无线传感器网络的关键技术之一应用于井下人员定

6、位、跟踪, 即在井下人员身上携带有效的传感器节点, 通过对节点的定位确定人员位置, 从而实现对井下作业人员的监控。目前, 低成本、高能效、高精度的距离测量技术已成为节点定位技术的重要研究方向之一。1 井下无线传感器网络节点定位描述根据有限个已知位置的节点来确定部署区中其他位置节点的位置。在部署区内的所有传感器节点分为两类:一类是已知位置的参考节点, 称为信标节点。信标节点的数量很少, 由于信标节点位置既定, 可作为参考节点通过一定的定位算法协助确定未知节点的位置; 另一类则是待测的未知节点。在定位算法中, 根据定位的机制不同一般可分为:基于测距的定位算法和非基于测距的定位算法。非基于定位算法是

7、利用节点的连通性和多跳路由信息交换等方法估算节点的距离或角度, 完成位置估计。该算法虽然成本低效率高但其对节点密度的要求高, 而且定位精度相对较低, 因此本文选择基于测距的定位方法。基于测距的定位算法是通过对节点间的距离或角度的测量信息实现定位, 包括测距和定位两个阶段, 而测距常用的方法有测量到达时间(TOA 、到达时间差(TDOA 、接收信号强度指示器(RSS I 以及相位和编码测量等, 前两种方法定位精度较高, 是利用信号传输的耗时测量信标节点和待测节点的距离。三边测量法2, 3是待测节点接收到3个以上信标节点发送的信息即可获得到各个信标节点之间的距离, 从而实现对自身的定位。该算法实现

8、了基于测距定位的第二个阶段:定位。算法要求部署的定位系统内包含多个已知参考节点,3信息工程 煤 炭 工 程 2010年第10期个节点即可确定待测节点的位置, 如图1a 所示, A 、B 、C 是已知位置的信标节点, 由A 发出的信号可知:待测节点位于以A 为圆心测量距离为半径的圆周上, 同理, 待测节点也应在以B 、C 为圆心测量距离为半径的圆周上, 故理论上3个圆的交点即为待测节点的预测位置。然而实际的定位系统中3个圆并不一定相交于同一点, 进而出现了如图1b 的定位效果, 为了获得更精确的位置定位, 将采用遗传算法应用 于定位算法中缩小阴影区以求获得更精确的定位。图1 三边测量情况综上所述

9、, 为获得较精确的监控井下人员的位置, 以确保事故时井下人员的快速撤离和搜救, 本文选择基于TOA 的测距算法并采用基于遗传算法优化的三边测量法定位获得较精确的待测节点位置。2 遗传优化算法简介遗传算法简称GA (G ene ti c A lgor it h m 是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法4, 5。遗传算法一般由编码、适应值函数、遗传算子、参数控制等四个部分组成。遗传算法首先选取一个由N 个编码过的个体组成的种群, 对种群进行初始化; 种群根据适应度函数选择选择适应度大的个体, 并借助遗传算子进行选择、交叉和变异, 逐代进化以产生新的个体。再反

10、复进化, 得到基因型的最优解。遗传算法中的控制参数:基因编码长度、种群个数、交叉概率、变异概率、最大遗传代数等6。1 基因编码采用二进制或实数编码, 本文选用10位二进制数编码。2 种群个数越多越利于求的全局最优解, 但要兼顾考虑计算效率适当选择。3 交叉概率要大些, 寻优搜索过程主要通过它来实现, 一般选取014019之间。4 变异概率发生的概率比较小, 取01001011之间。遗传算法应用在井下定位的优越性:无线传感器网络节点多, 分布区域广; 井下环境复杂, 节点布设随机, 通信约束多, 由此建立的定位函数将会是多目标的多约束的复杂非线性方程, 而遗传算法的应用条件简单, 与问题无关,

11、并行搜索计算能力强的特点特别适合无线传感器网络节点定位优化函数的求解要求7。3 定位算法实现本文基于TOA 的测距:信号从发送节点传递到接收节点, 而后接收节点回发送信号作为响应, 通过/握手0, 如图2所示, 发送节点即能从时间延迟中推断出距离:(T3-T 0 -(T2-T 1 V 2(1式中, V 代表信号的传递速度。这种测量方法的误差主要来源于信号处理的时间(即T 2-T 1, 所以此方法对硬件的要求较高4 。图2 TOA 测量图三边测量法定位:假设3个信标节点A 、B 、C 分别位于(X A , Y A , (X B ,Y B ,(X C , Y C , 则误差函数如下所示:D x,

12、y=|(x -x A +(y -y A -r A |(x -x B +(y -y B -r B |C C -r C |(2式中, 当误差函数D x, y 取最小值时, 其对应的待测节点(x, y 越接近真实值,r A 、r B 、r C 为信标节点到待测节点的距离。理想的三边测量法可将待测节点定位于一点, 但是实际测量结果却是如图1b 所示的阴影部分, 为了提高定位精度, 尽可能缩小阴影部分甚至于收敛于一点, 采用遗传迭代算法优化误差函数获取误差的最小值, 从而得到待测节点更精确的位置。4 实验仿真为了检验改进后算法的性能, 利用M ATLA B710进行仿真验证。定义3个已知的信标节点A (

13、200, 0 、B (0, 0 、C(0, 200 三点坐标, 将未知节点的位置设在(100,100处, 则r A =14114,r B =14114,r C =14114。遗传算法中参数设定迭代次数n =200, 交叉概率p c =016, 变异概率p m =01001, 算法程序中变量采用10位二进制编码串表示69。同时, 为了提高个体的进化速度, 对遗传优化算法进行了一定的改进, 即采用最优个体保优原则, 将每一代的所有个体按序排列后, 最优的5个个体不再经历交叉、变异运算, 而是直接遗传到下一代, 进而减少了迭代次数, 节省了算法运行时间, 实现更快速的迭代寻优。试验中, 信标节点A

14、、B 、C 均向待测节点发送信号, 记录时间T 0; 待测节点接收信号后分别回发送信号, 待3个信标节点接收到待测节点回发的信号后, 记录时间T 3; 信号处理时间忽略不计。利用式(1 处理计算后获得与待测节点的距离, 然后通过三边测量法计算并由遗传算法优化2010年第10期 煤 炭 工 程 信息工程后得到待测节点的定位位置。对比已设定的待测节点实际位置, 观察基于遗传优化算法的定位精度效果。如图3、4所示为迭代200次的待测节点的x, y 轨迹, 最终循环迭代终止后x =10012933, y =10110753, 与预先设定的坐标(100, 100 比较可知基于遗传算法的节点定位方法具有较

15、好的定位效果。同时, 为了评价算法性能, 给出了误差函数的仿真结果图, 如图5所示, 迭代终止后Dx, y=010468。另外, 为了更好的说明该定位算法的性能, 在不同的测距误差、节点密度条件下进行多次仿真实验。选取二维区域100100内随机设置信标节点和待测节点, 在测距误差分别为5%, 10%, 15%, 20%, 25%, 30%条件下, 测定信标节点密度分别为10%, 20%, 30%时7, 依据数据得出节点的定位误差的变化趋势如图6 所示。图6定位误差分析图5结语本文采用了基于遗传算法的井下无线传感器网络的节点定位算法, 即用遗传算法优化三边测量法, 文中详细说明了优化的理论思想,

16、 给出了MAT LAB710仿真出的定位效果图及误差分析图, 可以看出该定位方法的可靠性和有效性。由于此定位方法是基于TOA 测距的, 一般的方法是采用超声波信号传送, 节点上还需装有超声波发送、接收装置, 且由于井下环境复杂, 而超声波信号易被障碍物阻挡, 以至于会产生较大的误差, 为了更有效的降低误差, 节点可采用射频发送, 射频信号在一定频率下可穿透障碍物, 依据传感器节点功耗低、成本低、体积小等硬件限制条件, 应用中硬件可选用Chipcon 公司的射频收发器CC2430芯片, 该芯片集成有射频发生器, 还有增强型的8051M C U, 具有强大的鲁棒射频和数据处理功能, 其优良的无线接收灵敏度和强大的抗干扰性有利于井下复杂环境的应用。另外, CC2430的休眠模式和主动模式时的短时间有效的降低了功耗, 保证了电池的较长寿命, 从而实现简单、快速、长时间的井下定位方案8。参考文献:1王晓乐, 徐家品. 基于粒子群优化算法的W SN s 节点定位研究J.计算机应用, 2009, 29(2:494499.2王雪. 无线传感网络测量系统M.北京:机械工业出版社, 2007.3熊小华, 何通能, 徐中胜, 等. 无线传感器网络节点定位算法的研究综述J.机电工程, 2009, 26(2:1317. 4陈国良, 王