论文部分内容阅读
节点定位问题是无线传感器网络(wireless sensor network,WSN)应用的基础。传统的定位技术主要有距离无关和距离相关两大类。距离无关算法虽然对硬件要求不高,但定位精度较低;而距离相关算法则虽有较高的定位精度,却易受测距误差的影响。随着应用环境的多样化和复杂化,大量的限制条件使得传统的定位技术面临越来越大的挑战。对此,陆续有学者提出了基于各种智能优化算法的定位技术,如遗传算法和模拟退火算法等。这些智能优化定位算法结构简单通用,而且常常能够求解出可令人满意的定位结果,现已逐渐成为WSN定位技术研究领域的新热点。
分布估计算法(Estimation of Distribution Algorithm,EDA)是一种结合了统计学习理论和遗传算法原理的新型智能优化算法,它通过对概率模型的更新和采样操作来实现种群的进化。与其他智能优化算法相比,EDA的最大不同是用概率模型来捕捉问题空间的可行区域,这种更具有统计意义的进化方式使其在求解高维复杂的问题时能获得较优秀稳定的性能。WSN定位问题不但维数高(即待定位的节点多),而且应用环境复杂(受噪音的影响大),因此采用EDA来求解WSN定位问题是一个很有意义的尝试。本文根据现实应用的高精度和高鲁棒性要求,提出了一种基于直方图分布估计算法(Histogram Based EstimatedDistribution Algorithm,HEDA)的无线传感器网络定位技术,其核心是带自适应局部优化的直方图分布估计算法(HEDA/L)。HEDA/L设定每个个体由对所有未知节点的估计坐标组成,算法流程主要包括初始化、模型采样、模型更新和自适应局部优化四个过程。第一步的初始化过程首先将整个监测区域均匀离散化成若干个小区域,然后根据已知的测量距离近似估计出每个未知节点分布在各小区域的概率,并为每个未知节点构建一个对应的直方图模型来描述其分布在各小区域的概率。第二步的采样过程是在已建立的直方图模型上,通过逐一采样所有未知节点的估计位置来生成一个新个体,进而产生新一代的种群。第三步的模型更新过程则先在当前种群选择部分优秀个体,然后统计已选个体中每个未知节点落入各小区域的频率,并以此更新相应的直方图模型。第四步的自适应局部优化过程为局部优化解的质量,在当前最优个体的一定半径范围内进行重复探索,并根据每代的优化效果来自适应调整探索半径的缩放。后面三个过程按序循环进行,从而实现了种群的迭代进化。
仿真实验设计了多种不同场景下的测试案例,并将HEDA/L与Biswas提出的半定规划(Semi-Definite Programming,SDP)算法进行比较。实验结果表明,HEDA/L在测距误差较大的环境中依然能够获取比SDP算法有更高精度的定位结果,从而验证了本文所提出算法的有效性。我们还对HEDA/L算法的主要参数对其性能的影响进行分析,实验结果验证了HEDA/L的鲁棒性。