一种基于SATA的无线传感器网络定位算法*

梁森 王志宏 唐王龙 李昌镐 张明



一种基于SATA的无线传感器网络定位算法*

梁森1王志宏1唐王龙1李昌镐2张明3

（1.中建四局第一建筑工程有限公司 2.中山大学 3.广东邮电职业技术学院）

在无线传感器网络中，将节点定位看作一种地球物理反演问题，即一种求全局最优解问题，并将原子寻求最稳定状态的跃迁过程，应用于求解节点的最优位置过程，提出一种无线传感器节点定位算法——模拟原子跃迁定位算法。针对不同噪声环境进行仿真实验，实验结果表明：与模拟退火算法对比，本文提出的算法在定位精度和定位效率上有更好表现。

无线传感器网络；定位；物理反演问题；模拟原子跃迁算法

0 　引言

近年来，无线传感器网络受到越来越多的关注。随着微机电技术的快速发展，无线传感器网络的节点终端更加智能、轻便、低能耗，且具有测量、感知和收集外界环境信息等功能[1]。无线传感器网络在国防科技、智能家居、共享经济和防火救灾等领域有较大的实用价值[2]，并被认为是继互联网之后，二十一世纪最重要的技术之一[3]。

无线传感器网络中的节点定位实际上也是在区域范围内寻求最优坐标点问题，故可当作物理反演问题来处理。王家映[4-5]等提出一种模拟原子跃迁算法（simulated atomic transition algorithm, SATA），用于解决地球物理反演问题中的非线性最优化问题，并通过理论及实验分析证明了此算法的可用性。文献[6]根据蒙特卡洛算法（Monte Carlo algorithm, MCA）提出一种移动设备的定位算法。文献[7]提出一种基于模拟退火算法（simulated annealing algorithm, SAA）。文献[8]提出一种基于模拟植物生长的定位算法。这些定位算法在理想情况下能得到较好的定位效果，但存在噪声时，可能得到局部最优值，而非全局最优值。

本文把未知节点定位当作是求全局最优解问题考虑。基于SATA，提出一种无线传感器网络定位算法——模拟原子跃迁定位算法。通过未知节点的定位问题与原子跃迁过程的类比分析，定义目标函数；然后运用SATA求取此目标函数的最优解，即未知节点的位置坐标；最后通过与SAA比较，分析本文提出的模拟原子跃迁定位算法的定位性能。

1　SATA

根据原子量化模型理论，当原子处于平衡稳定状态时，核外电子在各个能级轨道上的分布服从玻尔兹曼（Boltzmann）分布[9]。电子在不同能级之间跃迁概率公式为

原子的各个能级可通过式(2)计算得到：

原子能量函数、原子能级图如图1、图2所示。

图1 　原子能量函数

图2　 原子能级图

图3　 原子跃迁过程

上述跃迁可能仅使原子处于能级较低的状态，并非是能量最低的稳定基态，即所得结果是局部最优解。为了能利用上一次跃迁的信息，可在前一次跃迁的基础上进行粒子轰击得到新的跃迁参数。粒子轰击可按式(3)添加一随机数进行扰动，即

如此反复跃迁，直至达到设定条件，所得结果即为最优解。

模拟原子跃迁求取全局最优解的具体步骤：

1）基于目标问题构建目标能量函数，随机给定目标问题的初始参数值群体；

2）求各个参数值对应的目标能级，如果目标能级小于给定的阈值，则直接跳转到步骤5），否则继续执行步骤3）；

3）根据目标能级比较和跃迁概率计算的结果，进行原子跃迁；

4）进行随机粒子轰击，以便产生新的参数值群体，跳转到步骤2），开始进行新一轮跃迁；

5）当满足跃迁结果条件（跃迁至最低能级或者达到最大迭代次数）时，输出最优解。

2　模拟原子跃迁定位算法

在无线传感器网络中，根据节点位置是否已知，可将节点分为2大类：一类是位置坐标已知的节点，称之为信标节点；另一类是待确认位置的未知节点。其中信标节点主要用于通过一定算法来估算未知节点的位置信息。

根据模拟原子跃迁定位算法，未知节点定位的目标函数设为

未知节点定位过程与原子跃迁过程的对应关系如表1所示。

表1　 未知节点定位过程与原子跃迁过程的对应关系表

3　仿真与分析

本文通过Matlab仿真模拟原子跃迁定位算法和SAA，并进行比较。

1）同样误差情况的表现

图4 理想情况下，模拟原子跃迁定位算法仿真结果

图5 理想情况下，SAA 仿真结果

图6 不同噪声时，SAA 与模拟原子跃迁定位算法仿真效果

2）定位时间

4　结论

本文提出一种模拟原子跃迁定位算法。该算法将节点定位看作一种求全局最优解问题。为防止得到局部极小值而非最优值，在模拟原子跃迁过程中，引入粒子轰击，加入随机数。从仿真结果看出，与SAA相比，本文算法不仅可以提高定位精度，还可以提高定位速度。随着无线传感器网络的发展，本算法其定位方面有较好的应用前景。

图7 SAA与模拟原子跃迁定位算法定位性能比较

[1] Darwish A, Hassanien A E. Wearable and implantable wireless sensor network solutions for healthcare monitoring[J]. Sensors, 2011,11(6): 5561-5595.

[2] 傅留虎,胡欣宇.智能传感器中的算法应用[J].物联网技术,2017,7(2):15-17,21.

[3] 彭宇,王丹.无线传感器网络定位技术综述[J].电子测量与仪器学报,2011,25(5):389-399.

[4] 师学明,王家映,易远元,等.一种新的地球物理反演方法——模拟原子跃迁反演法[J].地球物理学报,2007,50(1):305-312.

[5] Dai Yuhong, Kou Caixia. A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search[J]. SIAM Journal on Optimization, 2013,23(1): 296-320.

[6] Wang Jia, Fu Jingqi. Research on APIT and Monte Carlo method of localization algorithm for wireless sensor networks[J]. in Life System Modeling and Intelligent Computing, 2010:128-137.

[7] Pal A. Localization algorithms in wireless sensor networks: current approaches and future challenges[J]. Network Protocols & Algorithms, 2010, 2(1).

[8] Tang, C P, Liu R Q, Ni J Q. A novel wireless sensor network localization approach: localization based on plant growth simulation algorithm[J]. Electronics & Electrical Engineering, 2013,19(8).

[9] 聂承昌.玻尔原子结构理论及其历史中介意义[J].华南师范大学学报(社会科学版),1997(2):9-14.

A SATA-Based Localization Algorithm for Wireless Sensor Network

Liang Sen1Wang Zhihong1Tang Wanglong1Li Changhao2Zhang Ming3

(1.The First Construction Co., Ltd. of China Fourth Construction Bureau 2.Sun Yat-sen University 3.Guangdong Vocational College of Post and Telecom)

In recent years, the application scenarios and scope of IoT technology have become wider and wider. Wireless sensor networks, one of the core technologies of IOT, also play an important role in all walks of life, with high research and economic value. In the field of wireless sensor network technology, how to get the exact location of nodes is a key issue that practitioners in industry and academia pay particular attention to. Based on the in-depth study of node localization problems and physical inversion problems, this paper proposes to regard node localization as a geophysical inverse problem, which is a global optimal solution problem. Through the study of the atomic transition process in physics, this paper applies the "transition" process of atom seeking the most stable state to the optimal position of the solution node, and proposes a new wireless sensor node localization algorithm - Simulated Atomic Transition Algorithm (SATA). Compared with Simulated Annealing Algorithm (SAA) under ideal conditions and different noise conditions, the proposed algorithm has better performance in positioning accuracy and efficiency.

Wireless Sensor Network; Localization; Geophysical Inverse Problem; SATA

梁森，1982年生，男，高级工程师，硕士学历，主要研究方向：项目管理。

王志宏，1990年生，男，助理工程师，硕士学历，主要研究方向：工程建设、技术管理。

唐王龙，1983年生，男，工程师，硕士学历，主要研究方向：建设工程、技术管理。

李昌镐，1995年生，男，研究生，主要研究方向：深度学习、多模态数据融合等。

张明（通信作者），1989年生，男，助教，硕士学历，主要研究方向：边缘智能、数据挖掘等。E-mail: huake_zhming@163.com

广东省自然科学基金（2018A030313797）；广东省科技计划项目（2016B010125001，2016B090918110，2014B090901057）。