基于DV-HOP无线传感器的网络节点定位算法

文/胡鹏莎

1 引言

1.1 无线传感器网络概述

无线传感器网络的全称为Wireless Sensor Network，其能够通过目标区域内分布的许多非常小的传感器节点实现研究对象相关信息的感知、采集和处理，这一过程需要得到无线电通信的多跳自组织网络支持，而由于无线传感器体积较小、重量较轻，其也被称为“智能尘埃”，使用者只需要将其散落在目标区域内，无线传感器便能够实时感知物理世界发生的变化。总的来说，无线传感器网络具备密度高、规模大、动态性强、微型化、小型化、成本低、通信能力有限、计算和存储能力有限等特点，这使得其在我国军事、医疗、农业、智能家居等领域具备较高应用潜力。

表1：人工鱼群参数初始值

表2：无线传感器网络参数值

1.2 无线传感器网络节点定位技术研究

无线传感器网络节点定位涉及一系列专业术语，如信标节点、邻居节点、未知节点、跳数、连通度、到达时间、到达时间差、到达角度、接收信号强度、视线关系、非视线关系，跳数统计原理、邻近关系原理则属于该技术涉及的基本原理。长期以来国内外学界均围绕无线传感器网络节点定位技术开展了大量研究，2000年Nimpama Bulusu教授等人提出的质心算法、Tian He在2003年提出的APIT算法、马震在2008年提出的MDS-MAP算法、芦捷飞在2015年提出的RSSI与DV-Hop结合算法均属于其中代表，如何保证无线传感器网络节点定位技术更好为人们服务属于相关研究的最终目的。

图1：人工鱼群算法流程

图2：改进后的人工鱼群算法流程

图3：通信半径20m（左）、25m（右）的网络拓扑图

图4：通信半径20m（左）、25m（右）仿真波形

1.3 经典无线传感器网络定位算法

经典的无线传感器网络定位算法可细分为两类，这种划分以测距和非测距为依据，基于测距的定位算法主要包括RSSI定位算法、TOA定位算法、TDOA定位算法、AOA定位算法，基于非测距的定位算法则主要有质心定位算法、APIT算法、凸规划算法、以及本文研究的DV-Hop算法。DV-Hop算法的定位需要通过已经确定自身位置的节点与无法确定自身位置的节点建立通信联系实现，根据泛洪通信方式，算法需要结合网络中锚节点之间距离估算每跳平均跳距、以及节点获得的与锚节点之间最小跳数，与锚节点之间的距离可通过平均跳距乘以最小跳数求得，坐标的计算则需要使用极大似然值法或三边定位法，这使得其具备成本低廉、应用广泛特点。

1.4 定位算法性能的评价标准

对于无线传感器网络定位算法来说，评价标准主要包括定位精度、节点密度、锚节点密度、覆盖率、代价，定位精度使用定位误差和通信半径表示。假设节点通信半径R为50m、算法的计算误差为10m，定位精度为0.2，单个节点、整体平均定位误差的计算公式如式（1）、式（2）所示，式（1）中的rest、rreal、R分别为测量的位置、实际的位置、通信半径，式（2）中的n、m、分别为节点全部个数、锚节点全部个数、第i个节点测量位置、第i个节点实际位置。

2 基于人工鱼群算法的DV-HOP定位算法

2.1 人工鱼群算法

人工鱼群算法由我国学者李晓磊等人提出 于 2002年，全称为 Artifical Fish Swarm Algorithm，属于一种基于动物行为的群体智能优化算法，一般情况下水域内的鱼聚集在食物含量高的地方属于该算法的基本理念，而通过模仿鱼群的特点，人工云群算法得以具备较高的鲁棒性，且拥有较强的自适应能力、善于突破局部最优解（实现全局最优解），人工鱼群算法的流程如图1所示，该算法涉及的变量包括N、Xi、Yi、dik、Step、delta、Visual、TryNum、gen、Maxgen，分别代表人工鱼群中人工鱼总数量、第i条人工鱼位置、第i条鱼所处食物浓度、第k条与第i条鱼距离、人工鱼游动步长最大值、水域拥挤度、人工鱼目视距离最大值、搜寻食物尝试次数最大值、算法迭代次数、算法迭代最大值。

2.2 基于人工鱼群算法的DV-HOP定位算法

本文开展的DV-HOP定位算法改进研究首先改进了原始算法的三个定位步骤，通过修正最小跳数、未知节点优先节点定位、改进平均跳距，即可将DV-HOP定位算法从解定位问题转化为优化问题，而为了保证人工鱼群算法较好服务于未知节点坐标的求解，必须对该算法进行改进，改进主要围绕人工鱼分段寻优、动态修改参数值、改进觅食行为展开，具体改进内容如下：

（1）人工鱼分段寻优。为提高算法的收敛速度，需要设法淘汰始终在食物浓度较低地方搜寻的人工鱼，设算法前期迭代次数为k且 k<ɑMaxgen，而当 k>ɑMaxgen后，则需要在每次迭代过程中淘汰一条人工鱼，直到k=Maxgen，即可确定最优结果。

（2）动态修改参数值。如Visual值较大，人工鱼视野较广且具备全局搜索能力，同时随机行为和觅食较为频繁，如Step值较大，人工鱼则因视野参数小具备较强的局部搜索能力，同时存在追尾频繁特点。因此，算法前期应保证Visual、Step值较大，并随着寻优的进行不断缩小Visual、Step，因此二者参数需动态设定为式（3）、（4），式中的ɑ、β为常数（均取1/2），Visual0、Step0分别为赋予视野、步长的初值。

（3）觅食行为改进。为防止个体最优解退化，采用最优个体保留机制改进觅食行为，以极小值为例，任意选择某一个地方Xn（视距Visual范围内），如目标函数Yn

2.2.1 改进的算法原理

改进后的人工鱼群算法流程如图2所示，该流程涉及的距离方程、目标函数如下：

2.2.2 改进的算法流程

基于人工鱼群算法的DV-HOP定位算法流程可概括为：“开始→锚节点分别以R、2R/3、R/3向网络中广播信息→锚节点周围邻居节点接收信息→保留最小跳数，R广播完毕后，接收节点转发→未知节点满足优先定位→估算锚节点与未直接点距离→定位满足条件的未知节点→优先定位的未知节点升级为锚节点→锚节点向网络广播信息→其他未知节点接收广播信息→接收过锚节点信息→比较并保存最小跳数信息→广播结束→未知节点收到三个或以上锚节点信息→锚节点计算与其他锚节点距离→锚节点估算平均跳距及误差→未知节点加权处理接收到的各锚节点平均跳距→未知节点估算自己数据分组中各锚节点距离→使用改进人工鱼群算法计算未知节点坐标→结束”，改进人工鱼群算法的应用可有效优化未知节点的位置。

3 仿真结果与分析

3.1 仿真参数设置

使用Matlab2014a软件、经典DV-Hop算法、改进后算法开展仿真，人工鱼群参数的初始值如表1所示，无线传感器网络参数值如表2所示，其中δ为拥挤度初值，采用归一化平均定位误差。

3.2 仿真结果及分析

图3为通信半径20m、25m的网络拓扑图，图4为通信半径20m、25m仿真波形，图5为通信半径30m、35m的网络拓扑图，图6为通信半径30m、35m仿真波形，图7为不同通信半径仿真波形，由此可直观发现改进后算法可有效减少对锚节点数目的依赖，并能够有效减小定位误差，定位的成本也因此大大下降。

图5：通信半径30m（左）、35m（右）的网络拓扑图

图6：通信半径30m（左）、35m（右）仿真波形

图7：不同通信半径仿真波形

图8：改进算法与DV-Hop算法单个节点误差比照图

图8为改进算法与DV-Hop算法单个节点误差比照图，由此可更直观了解改进算法具备的较高实用价值。

4 结论

综上所述，基于人工鱼群算法的DV-HOP定位算法可较好服务于无线传感器网络节点定位，本文求得的仿真结果也能够证明这一认知，而为了更好推动无线传感器网络节点定位算法发展，本文研究的算法的实际应用验证将成为笔者的下一步研究方向。