基于IFOA优化DV—distance算法的无线传感器网络定位研究
庞先伟+左仁淑+王婷婷+李学军
摘 要： 对无线传感器网络节点定位问题进行研究，提出一种基于IFOA优化DV?distance算法的WSNs定位方法。针对DV?distance算法定位精度低、噪声影响大，受限于网络拓扑结构等问题，将改进的果蝇优化算法（IFOA）引入到DV?distance设计中，实现了节点位置的精确定位，为进一步提高算法定位的精度，引入動态加权修正因子，并给出动态误差修正策略，最后对WSNs节点定位问题进行实验仿真，仿真结果表明，基于IFOA优化的DV?distance定位算法较DV?distance和传统定位算法在定位精度上有明显改善。
关键词： 无线传感器网络； 节点定位； 果蝇优化算法； DV?distance
中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）13?0022?04
Abstract： The node localization problem for wireless sensor networks （WSNs） is studied. A DV?distance algorithm based on fruit fly optimization algorithm for WANs localization is proposed. Since the DV?distance localization algorithm has the defect of low localization precision， is influenced by noise easily， and restricted to the network topology structure， an improved fruit fly optimization algorithm （IFOA） is introduced into the DV?distance algorithm to realize the accurate localization of the node position. In order to improve the algorithm localization accuracy further， the dynamic weighted correction factor is introduced into the algorithm， and the dynamic error correction strategy is given. The simulation experiment was performed for WSNs node loca?lization. The simulation results show that the positioning accuracy of the improved DV?distance localization algorithm is significantly improved than that of the DV?distance and traditional localization algorithms.
Keywords： wireless sensor network； node localization； fruit fly optimization algorithm； DV?distance
0 引 言
随着无线通信技术的不断发展，无线传感器网络（WSNs）在火灾、潮汐、环境监控、空间探索等领域得到了广泛应用[1]。传感器节点位置定位作为WSNs关键技术之一[2]，具有十分重要的研究意义。常见的定位方法可以分为基于测距（range?based）的定位技术和无须测距（range?free）的定位技术两大类[3]。RSSI（Received Signal Strength Indication）是典型的基于测距定位算法[4]，由于具有硬件成本低、容易获取等特点，得到了广泛应用，但是定位精度低、能耗相对较大。而无须测距定位算法应用较为广泛的是DV?Hop算法[5]，其属于自组织定位系统（Ad Hoc Positioning System，APS）范畴，具有算法简单，易于实现等特点，但是对节点性能要求相对较高，精度受网络拓扑结构影响较大[6]。
Badri Nath等学者在DV?Hop算法基础上提出了 DV?Distance节点定位算法，其通过计算未知节点与信标节点间最小跳数路段距离的最大似然估计来实现节点位置定位，具有良好的扩展性，但是该算法对距离误差比较敏感[7]，因此提高算法鲁棒性和抗干扰性是当前研究的热点之一。果蝇优化算法（Fruit Fly Optimization Algorithm，FOA）是一种新的演化式算法[8]，具有计算简单、参数少、易于理解等优点，得到了越来越多学者的关注，然而对FOA在WSNs节点定位方面的研究相对较少。
本文将改进的果蝇优化算法（IFOA）应用到DV?distance节点定位过程，并引入动态加权修正因子，给出动态误差修正策略，最后对WSNs节点定位问题进行实验仿真，以验证基于IFOA优化DV?distance算法的有效性。
1 DV?distance算法描述
设定存在如图1所示的无线传感器网络，其中，由个信标节点组成的集合为；个未知节点组成的集合为。
DV?Distance算法定位过程可以描述为：
Step1： 获取未知节点到信标节点之间的跳段距离。
依据距离矢量交换协议[9]，信标节点向邻居节点广播包含跳段和累计跳段距离（初始化均为0）的自身位置信息分组，接收节点在比较同一信标节点跳数值后，保留具有最小跳数的分组，同时更新跳段和累计跳段距离信息，并转发给其他邻居节点。通过该方法，所有未知节点获取了到每个信标节点的最小跳数和路径信息。如图1所示，未知节点到信标节点，，，的最小跳数分别为2，1，2，3；对应的累计跳段距离可以表示为：
Step2： 未知节点位置确定。
当未知节点获取到所有信标节点间的累计跳段距离后，可以利用最大似然估计或三边定位方法来确定未知节点的位置信息。
通过分析DV?Distance定位过程，可以看出其存在的缺点主要有：
（1） 由于相邻节点间的距离是通过RSSI测得，而RSSI测距技术受距离和环境影响较大，因此导致节点间距离测量精度存在较大误差。
（2） DV?Distance采用未知节点与信标节点间的累计跳段距离替代欧式距离，随着跳段数的不断增加，导致与存在较大差距，从而导致算法定位精度并不高。
2 改进果蝇优化算法（IFOA）描述
2.1 基本果蝇优化算法（FOA）
果蝇优化算法基于模拟果蝇觅食生物学现象，通过动态调整嗅觉和视觉信息，实现向食物聚拢。FOA基本原理可以描述为：
Step1： 参数初始化。随机生成规模为的果蝇种群，设置种群初始位置，算法最大迭代次数以及算法终止条件。
Step2： 嗅觉搜寻。根据式（1）初始化果蝇搜寻食物的方向和距离，即得到果蝇个体位置：
式中为随机数。
Step3： 味道浓度判定值计算。根据式（2）计算果蝇的味道浓度判定值：
Step4： 味道浓度计算。根据式（3）计算果蝇的味道浓度：
式中为目标函数。
Step5： 视觉搜寻。保留种群历史最佳味道浓度值其他果蝇个体利用视觉向具有最佳味道浓度值的位置飞去，即。
Step6： 终止条件判断。重复执行Step2～Step5，直到满足终止条件。
2.2 多子族群改进果蝇优化算法
FOA在迭代进化过程中，只保留历史最佳个体相关信息，导致算法容易陷入局部最优，出现“早熟”现象，其根本原因在于群体样本多样性较差。为提高种群多样性，提出子族群概念，果蝇种群按照一定规则划分成规模相同的子族群，果蝇个体先在子族群进行局部搜索，然后将子族群最优信息在种群范围内进行信息交流，最后再次进行子族群划分，如此往复，从而有效地增加了种群样本多样性，避免了算法陷入局部最优。子族群划分规则可以描述为：果蝇个体按照味道浓度依次排列，将种群划分为规模相同的个子族群，第1个果蝇个体分入第1个子族群，第2个果蝇个体分入第2个子族群，第个果蝇个体分入第个子族群，第个果蝇个体分入第1个子族群，依次类推，直至子族群划分完毕。
3 基于IFOA优化DV?distance算法实现
3.1 动态误差修正策略
用累计跳段距离替代欧式距离是DV?Distance定位算法定位精度不高的主要原因之一，为此，采用式（4）对累计跳段距离进行动态修正[7]。
式中：为修正后累计跳段距离；为动态加权修正因子；表示未知节点到信标节点的跳数；表示未知节点到信标节点的总跳数；分别表示信标节点之间的欧式距离和累计跳段距离。
式（4）充分考虑了未知节点到信标节点，以及所有信标节点之间累计跳段距离和欧式距离比值对定位精度的影响，并根据跳数大小动态调整误差修正比值。显然，未知节点到信标节点跳数越多，带来的误差也就越大，使得修正比例也就越大；未知节点到信标节点跳数占信标节点间总跳数比值越大时，累计跳段距离误差也就越大，其分配的比例权重也就越小。
3.2 基于IFOA优化DV?distance算法实现流程
目标函数：定义IFOA适应度函数为：
式中为信标节点的位置坐标。
从式（5）可以看出，IFOA最优解为到所有信标节点误差最小的点，即定位测距误差越小，定位就越精确。
基于IFOA优化DV?distance算法节点定位过程如图2所示。
4 实验仿真
在Matlab仿真平台进行实验仿真，设节点随机分布在200 m×200 m的网络中，未知节点和信标节点位置信息随机产生，每个节点具有相同的通信半径。IFOA参数设置如下：。本文在文献[10]的基础上给出归一化平均定位误差评价指标：
式中：为仿真实验次数；为节点通信半径（取）；为可定位节点数；，分別为位置节点真实坐标和算法求解所得坐标。
4.1 平均定位误差与算法迭代次数的关系
为验证基于IFOA优化DV?distance算法（IFOADV?distance）的有效性，设网络中共有100个节点，信标节点比例为10%，分别取FOADV?distance，IFOADV?distance和文献[11]提出的HABC算法进行仿真，图3给出了三种算法平均定位误差与算法迭代次数的关系。
从图3可以看出，随着迭代次数的不断增加，三种算法定位误差都接近于0，但是IFOADV?distance收敛速度明显优于其他两种定位算法，表明该算法具有很强的稳定性，在迭代次数大于40次时，该算法的归一化平均定位误差基本保持不变，而且具有很高的定位精度。
4.2 信标节点个数、网络节点个数对算法定位精度的影响
为进一步分析算法定位精度与信标节点个数和网络节点个数之间的关系，分别采取FOADV?distance算法，IFOADV?distance算法和HABC算法进行试验，网络节点总数为200个。图4给出了信标节点个数与之间的关系，图5给出了节点个数与之间的关系。
从图4可以看出，在网络节点数保持不变的情况下，三种算法的定位误差随着信标节点比例不断提高而减小，并逐渐趋于稳定，而且IFOADV?distance算法的定位误差要明显优于其他两种算法。从图5可以看出，在信标节点数保持不变的情况下，三种算法的定位误差随着网络节点数量的不断提高而减小，并逐渐趋于稳定。同样，IFOADV?distance算法的定位误差要明显优于其他两种算法。仿真实验结果证明了基于IFOA优化DV?distance算法的有效性，并且该算法在定位精度和计算时间上要优于传统定位算法。
5 结 语
本文在改进基本果蝇优化算法的基础上，针对传统DV?distance算法定位精度低、噪声影响大，受限于网络拓扑结构等问题，将改进的果蝇优化算法引入到DV?distance设计中，提出一种基于IFOA优化DV?distance算法的WSNs定位方法。为进一步提高算法定位精度，引入动态加权修正因子概念，并给出了动态误差修正策略，最后对WSNs节点定位问题进行实验仿真。仿真结果表明，基于IFOA优化DV?distance定位算法有效提高了节点定位精度。
参考文献
[1] 刘志新，刘强，袁亚洲，等.基于贝叶斯估计与虚拟力导向混合遗传算法的无线传感网络定位方案[J].控制与决策，2013，28（6）：899?903.
[2] 王换招，孟凡治，李增智.高效节能的无线传感器网络覆盖保持协议[J].软件学报，2010，21（12）：3124?3127.
[3] 高鹏，石为人.基于测距定向的WSNs分步求精定位算法[J].仪器仪表学报，2012，33（5）：976?984.
[4] AKSU H， AKSOY D， KORPEOGLU I. A study of localization metrics： evaluation of position errors in wireless sensor networks [J]. Computer networks， 2011， 55（15）： 3562?3577.
[5] NICULESCU D， NATH B. DV based positioning in Ad Hoc networks [J]. Telecommunication systems modeling， analysis， design and management， 2003， 22 （1）： 267?280.
[6] 马庆功，刘冉冉.基于DV?Distance的无线传感器网络定位算法研究[J].吉林师范大学学报（自然科学版），2014，24（1）：66?70.
[7] 石欣，冉启可，范敏，等.无线传感器网络动态加权DV?Distance算法[J].仪器仪表学报，2013，34（9）：1975?1981.
[8] PAN W T. A new fruit fly optimization algorithm： taking the financial distress model as an example [J]. Knowledge?based systems， 2012， 26（2）： 69?74.
[9] PAVAI K， SIBAGAMIA， SRIDHARAN D. Study of routing protocols in wireless sensor networks [C]// Proceedings of 2009 IEEE International Conference on Advances in Computing Control and Telecommunication Technologies. Trivandrum： IEEE， 2009： 522?525.
[10] 李牧东，熊伟，郭龙.基于人工蜂群算法的DV?Hop定位改进[J].计算机科学，2013，40（1）：33?36.
[11] 江涛.基于混合人工蜂群策略的改进DV?Hop定位算法[J].电子器件，2014，37（5）：912?916.
摘 要： 对无线传感器网络节点定位问题进行研究，提出一种基于IFOA优化DV?distance算法的WSNs定位方法。针对DV?distance算法定位精度低、噪声影响大，受限于网络拓扑结构等问题，将改进的果蝇优化算法（IFOA）引入到DV?distance设计中，实现了节点位置的精确定位，为进一步提高算法定位的精度，引入動态加权修正因子，并给出动态误差修正策略，最后对WSNs节点定位问题进行实验仿真，仿真结果表明，基于IFOA优化的DV?distance定位算法较DV?distance和传统定位算法在定位精度上有明显改善。
关键词： 无线传感器网络； 节点定位； 果蝇优化算法； DV?distance
中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）13?0022?04
Abstract： The node localization problem for wireless sensor networks （WSNs） is studied. A DV?distance algorithm based on fruit fly optimization algorithm for WANs localization is proposed. Since the DV?distance localization algorithm has the defect of low localization precision， is influenced by noise easily， and restricted to the network topology structure， an improved fruit fly optimization algorithm （IFOA） is introduced into the DV?distance algorithm to realize the accurate localization of the node position. In order to improve the algorithm localization accuracy further， the dynamic weighted correction factor is introduced into the algorithm， and the dynamic error correction strategy is given. The simulation experiment was performed for WSNs node loca?lization. The simulation results show that the positioning accuracy of the improved DV?distance localization algorithm is significantly improved than that of the DV?distance and traditional localization algorithms.
Keywords： wireless sensor network； node localization； fruit fly optimization algorithm； DV?distance
0 引 言
随着无线通信技术的不断发展，无线传感器网络（WSNs）在火灾、潮汐、环境监控、空间探索等领域得到了广泛应用[1]。传感器节点位置定位作为WSNs关键技术之一[2]，具有十分重要的研究意义。常见的定位方法可以分为基于测距（range?based）的定位技术和无须测距（range?free）的定位技术两大类[3]。RSSI（Received Signal Strength Indication）是典型的基于测距定位算法[4]，由于具有硬件成本低、容易获取等特点，得到了广泛应用，但是定位精度低、能耗相对较大。而无须测距定位算法应用较为广泛的是DV?Hop算法[5]，其属于自组织定位系统（Ad Hoc Positioning System，APS）范畴，具有算法简单，易于实现等特点，但是对节点性能要求相对较高，精度受网络拓扑结构影响较大[6]。
Badri Nath等学者在DV?Hop算法基础上提出了 DV?Distance节点定位算法，其通过计算未知节点与信标节点间最小跳数路段距离的最大似然估计来实现节点位置定位，具有良好的扩展性，但是该算法对距离误差比较敏感[7]，因此提高算法鲁棒性和抗干扰性是当前研究的热点之一。果蝇优化算法（Fruit Fly Optimization Algorithm，FOA）是一种新的演化式算法[8]，具有计算简单、参数少、易于理解等优点，得到了越来越多学者的关注，然而对FOA在WSNs节点定位方面的研究相对较少。
本文将改进的果蝇优化算法（IFOA）应用到DV?distance节点定位过程，并引入动态加权修正因子，给出动态误差修正策略，最后对WSNs节点定位问题进行实验仿真，以验证基于IFOA优化DV?distance算法的有效性。
1 DV?distance算法描述
设定存在如图1所示的无线传感器网络，其中，由个信标节点组成的集合为；个未知节点组成的集合为。
DV?Distance算法定位过程可以描述为：
Step1： 获取未知节点到信标节点之间的跳段距离。
依据距离矢量交换协议[9]，信标节点向邻居节点广播包含跳段和累计跳段距离（初始化均为0）的自身位置信息分组，接收节点在比较同一信标节点跳数值后，保留具有最小跳数的分组，同时更新跳段和累计跳段距离信息，并转发给其他邻居节点。通过该方法，所有未知节点获取了到每个信标节点的最小跳数和路径信息。如图1所示，未知节点到信标节点，，，的最小跳数分别为2，1，2，3；对应的累计跳段距离可以表示为：
Step2： 未知节点位置确定。
当未知节点获取到所有信标节点间的累计跳段距离后，可以利用最大似然估计或三边定位方法来确定未知节点的位置信息。
通过分析DV?Distance定位过程，可以看出其存在的缺点主要有：
（1） 由于相邻节点间的距离是通过RSSI测得，而RSSI测距技术受距离和环境影响较大，因此导致节点间距离测量精度存在较大误差。
（2） DV?Distance采用未知节点与信标节点间的累计跳段距离替代欧式距离，随着跳段数的不断增加，导致与存在较大差距，从而导致算法定位精度并不高。
2 改进果蝇优化算法（IFOA）描述
2.1 基本果蝇优化算法（FOA）
果蝇优化算法基于模拟果蝇觅食生物学现象，通过动态调整嗅觉和视觉信息，实现向食物聚拢。FOA基本原理可以描述为：
Step1： 参数初始化。随机生成规模为的果蝇种群，设置种群初始位置，算法最大迭代次数以及算法终止条件。
Step2： 嗅觉搜寻。根据式（1）初始化果蝇搜寻食物的方向和距离，即得到果蝇个体位置：
式中为随机数。
Step3： 味道浓度判定值计算。根据式（2）计算果蝇的味道浓度判定值：
Step4： 味道浓度计算。根据式（3）计算果蝇的味道浓度：
式中为目标函数。
Step5： 视觉搜寻。保留种群历史最佳味道浓度值其他果蝇个体利用视觉向具有最佳味道浓度值的位置飞去，即。
Step6： 终止条件判断。重复执行Step2～Step5，直到满足终止条件。
2.2 多子族群改进果蝇优化算法
FOA在迭代进化过程中，只保留历史最佳个体相关信息，导致算法容易陷入局部最优，出现“早熟”现象，其根本原因在于群体样本多样性较差。为提高种群多样性，提出子族群概念，果蝇种群按照一定规则划分成规模相同的子族群，果蝇个体先在子族群进行局部搜索，然后将子族群最优信息在种群范围内进行信息交流，最后再次进行子族群划分，如此往复，从而有效地增加了种群样本多样性，避免了算法陷入局部最优。子族群划分规则可以描述为：果蝇个体按照味道浓度依次排列，将种群划分为规模相同的个子族群，第1个果蝇个体分入第1个子族群，第2个果蝇个体分入第2个子族群，第个果蝇个体分入第个子族群，第个果蝇个体分入第1个子族群，依次类推，直至子族群划分完毕。
3 基于IFOA优化DV?distance算法实现
3.1 动态误差修正策略
用累计跳段距离替代欧式距离是DV?Distance定位算法定位精度不高的主要原因之一，为此，采用式（4）对累计跳段距离进行动态修正[7]。
式中：为修正后累计跳段距离；为动态加权修正因子；表示未知节点到信标节点的跳数；表示未知节点到信标节点的总跳数；分别表示信标节点之间的欧式距离和累计跳段距离。
式（4）充分考虑了未知节点到信标节点，以及所有信标节点之间累计跳段距离和欧式距离比值对定位精度的影响，并根据跳数大小动态调整误差修正比值。显然，未知节点到信标节点跳数越多，带来的误差也就越大，使得修正比例也就越大；未知节点到信标节点跳数占信标节点间总跳数比值越大时，累计跳段距离误差也就越大，其分配的比例权重也就越小。
3.2 基于IFOA优化DV?distance算法实现流程
目标函数：定义IFOA适应度函数为：
式中为信标节点的位置坐标。
从式（5）可以看出，IFOA最优解为到所有信标节点误差最小的点，即定位测距误差越小，定位就越精确。
基于IFOA优化DV?distance算法节点定位过程如图2所示。
4 实验仿真
在Matlab仿真平台进行实验仿真，设节点随机分布在200 m×200 m的网络中，未知节点和信标节点位置信息随机产生，每个节点具有相同的通信半径。IFOA参数设置如下：。本文在文献[10]的基础上给出归一化平均定位误差评价指标：
式中：为仿真实验次数；为节点通信半径（取）；为可定位节点数；，分別为位置节点真实坐标和算法求解所得坐标。
4.1 平均定位误差与算法迭代次数的关系
为验证基于IFOA优化DV?distance算法（IFOADV?distance）的有效性，设网络中共有100个节点，信标节点比例为10%，分别取FOADV?distance，IFOADV?distance和文献[11]提出的HABC算法进行仿真，图3给出了三种算法平均定位误差与算法迭代次数的关系。
从图3可以看出，随着迭代次数的不断增加，三种算法定位误差都接近于0，但是IFOADV?distance收敛速度明显优于其他两种定位算法，表明该算法具有很强的稳定性，在迭代次数大于40次时，该算法的归一化平均定位误差基本保持不变，而且具有很高的定位精度。
4.2 信标节点个数、网络节点个数对算法定位精度的影响
为进一步分析算法定位精度与信标节点个数和网络节点个数之间的关系，分别采取FOADV?distance算法，IFOADV?distance算法和HABC算法进行试验，网络节点总数为200个。图4给出了信标节点个数与之间的关系，图5给出了节点个数与之间的关系。
从图4可以看出，在网络节点数保持不变的情况下，三种算法的定位误差随着信标节点比例不断提高而减小，并逐渐趋于稳定，而且IFOADV?distance算法的定位误差要明显优于其他两种算法。从图5可以看出，在信标节点数保持不变的情况下，三种算法的定位误差随着网络节点数量的不断提高而减小，并逐渐趋于稳定。同样，IFOADV?distance算法的定位误差要明显优于其他两种算法。仿真实验结果证明了基于IFOA优化DV?distance算法的有效性，并且该算法在定位精度和计算时间上要优于传统定位算法。
5 结 语
本文在改进基本果蝇优化算法的基础上，针对传统DV?distance算法定位精度低、噪声影响大，受限于网络拓扑结构等问题，将改进的果蝇优化算法引入到DV?distance设计中，提出一种基于IFOA优化DV?distance算法的WSNs定位方法。为进一步提高算法定位精度，引入动态加权修正因子概念，并给出了动态误差修正策略，最后对WSNs节点定位问题进行实验仿真。仿真结果表明，基于IFOA优化DV?distance定位算法有效提高了节点定位精度。
参考文献
[1] 刘志新，刘强，袁亚洲，等.基于贝叶斯估计与虚拟力导向混合遗传算法的无线传感网络定位方案[J].控制与决策，2013，28（6）：899?903.
[2] 王换招，孟凡治，李增智.高效节能的无线传感器网络覆盖保持协议[J].软件学报，2010，21（12）：3124?3127.
[3] 高鹏，石为人.基于测距定向的WSNs分步求精定位算法[J].仪器仪表学报，2012，33（5）：976?984.
[4] AKSU H， AKSOY D， KORPEOGLU I. A study of localization metrics： evaluation of position errors in wireless sensor networks [J]. Computer networks， 2011， 55（15）： 3562?3577.
[5] NICULESCU D， NATH B. DV based positioning in Ad Hoc networks [J]. Telecommunication systems modeling， analysis， design and management， 2003， 22 （1）： 267?280.
[6] 马庆功，刘冉冉.基于DV?Distance的无线传感器网络定位算法研究[J].吉林师范大学学报（自然科学版），2014，24（1）：66?70.
[7] 石欣，冉启可，范敏，等.无线传感器网络动态加权DV?Distance算法[J].仪器仪表学报，2013，34（9）：1975?1981.
[8] PAN W T. A new fruit fly optimization algorithm： taking the financial distress model as an example [J]. Knowledge?based systems， 2012， 26（2）： 69?74.
[9] PAVAI K， SIBAGAMIA， SRIDHARAN D. Study of routing protocols in wireless sensor networks [C]// Proceedings of 2009 IEEE International Conference on Advances in Computing Control and Telecommunication Technologies. Trivandrum： IEEE， 2009： 522?525.
[10] 李牧东，熊伟，郭龙.基于人工蜂群算法的DV?Hop定位改进[J].计算机科学，2013，40（1）：33?36.
[11] 江涛.基于混合人工蜂群策略的改进DV?Hop定位算法[J].电子器件，2014，37（5）：912?916.
