2. 96617部队, 四川 泸州 646000;
3. 西安航天精密机电研究所, 陕西 西安 710072
水下无线传感器网络(UWSN)在海洋探索、水下环境监测、水下航行目标监测与跟中、辅助导航等领域将扮演越来越重要的角色。在水下传感器网络的实际应用中, 传感器节点的位置是其所提供信息有效的基础[1]。由于水下通信的特殊性, 一般仅有少部分节点可以进行精确定位[2], 如AUV、潜艇、洋面浮标和水下固定信标等。在网络中, 这些已定位节点称为锚节点, 其他普通节点则以锚节点作为定位基准进行通信定位。由于布置困难, 水下锚节点数量一般较少, 这将增大普通节点定位误差。同时, 水下传感器网络拓扑由于水流或节点故障等问题都很有可能导致网络出现空洞, 空洞的出现严重影响对传感器网络节点位置信息的估计。
近些年来, 研究者针对水下传感器网络节点定位提出了很多算法[2-4]。多维定标(MDS)是一种在心理分析、经济与市场研究上应用的数据分析技术[5]。该方法可以有效对大量高维数据进行降维, 在二维或三维空间以点的形式重构出各个维度的数据, 并将两点之间距离与数据的相似性相关联, 若数据越相似则距离越近, 反之则越远。在无线传感器网络中, 该方法可在仅知道节点间距离的情况下对节点进行定位。以节点间的量测距离作为算法的输入, MDS方法在二维或三维空间将节点的分布重新构造出来, 并使点与点之间的距离尽可能接近真实节点间的距离, 那么二维或三维空间中点的位置即为节点的相对坐标。在知道部分节点绝对坐标的情况下, 可将相对坐标转换为绝对坐标。以MDS为基础的无线传感器网络定位算法称为MDS-MAP算法[6], 该方法的特点是需要锚节点较少, 定位精度高于一般算法。MDS-MAP算法在二维平面中仅需要3个锚节点、三维空间仅需要4个锚节点即可实现网络全部节点的定位, 符合水下传感器网络的应用特征, 与其他算法相比具有明显优势。但该算法需使用节点间真实距离信息, 处于非连通范围的节点距离信息使用最短路径代替。现有研究大多集中在分布式MDS-MAP算法地图数据融合和优化节点距离矩阵上[7-8], 当网络非均匀分布或内部出现空洞时, 最短路径将严重偏离节点间真实距离, 导致较大定位误差, 现有的距离优化方法并不能消除网络结构对节点距离的影响。
针对网络拓扑严重影响MDS-MAP定位精度的问题, 本文提出了一种基于粒子群算法的RQ-PSO定位优化方法。在使用MDS-MAP对网络节点完成初定位后, 该方法引入鲁棒四边形规则并利用粒子群算法对MDS-MAP算法解算出的位置信息进行优化。该方法弥补了MDS-MAP算法定位精度受网络构型影响较大的不足, 定位精度要高于单一使用粒子群算法和MDS-MAP算法, 且收敛速度和计算开销要小于经典粒子群算法, 并表现出了较强的鲁棒性。
1 MDS-MAP算法过程设空间中有n个位置未知的点, 令矩阵Xn×p为所有节点相对坐标, p代表维数, MDS-MAP算法包括以下3个步骤[9-10]:
1) 生成一个n×n的距离矩阵D, 元素dij表示节点i和j之间的量测距离。若i=j, 则有dij=0, 对于任意的i与j, dij=dji。在实际应用中, 若i点与j点非直接连通, dij可由Floyd或Dijkstra算法求得的最短路径代替。
2) 对距离矩阵执行经典的MDS算法, 求解节点相对位置坐标。二次中心化矩阵D2(X), 即在D2(X)左右同乘以H, 如下所示
|
(1) |
|
(2) |
式中, H为中心矩阵[11], In×n为n阶单位矩阵, e=[1, 1, …, 1]1×n, 对B进行特征值分解可得
|
(3) |
式中, A是从大到小排列的特征值组成的对角阵A=diag(λ1, λ2, …, λn), U=[p1 p2…pn]为对应的特征向量组成的正交矩阵。则相对坐标矩阵可写为
|
(4) |
若保留前k个最大特征值及相应的特征向量(k≤p)，则可以得到k维空间下的节点相对坐标。例如, 在二维网络中, 选择前2个最大特征值及对应的特征向量重构相对坐标; 相应的, 在三维网络中则选择前3个最大特征值及对应特征向量得到相对坐标。
3) 根据锚节点将相对坐标变换为全局坐标。
2 经过改进优化的RQ-PSO算法 2.1 经典粒子群算法粒子群优化算法是对简化群智能体模型的模拟, 该算法能够使粒子飞向解空间, 并在最优解处降落得到最优解。PSO算法选择n个初始化随机粒子, 每个粒子都代表一个解。每个粒子具有位置和速度信息, 同时具有一个由目标函数决定的适应值来评判粒子优劣。假设第i()个粒子的绝对位置坐标为Xi=[xi1, xi2, …, xip], 速度为Vi=[vi1, vi2, …, vip]。在每一次迭代中粒子通过跟踪个体最优解pbest和全局最优值gbest来更新自己。当找到这2个最优值后, 粒子根据如下公式来更新自己的速度与位置。
|
(5) |
|
(6) |
|
(7) |
式中, ω为惯性权重, iter为迭代次数, 参考文献[12]提出的公式(7) 更新ω, 可知当迭代的次数增加时, 惯性权重将逐渐降低, 可得到更好的全局解。c1与c2为学习因子, r1与r2为0至1中间任意的随机数。
2.2 结合粒子群算法的RQ-PSO算法1) 粒子群初始范围
利用MDS-MAP粗定位信息限制粒子群初始种群位置。如图 1所示, o1、o2、o3为3个与未知节点连接的锚节点。点pes表示通过MDS-MAP算法计算得到的节点位置, 点ptrue为节点真实位置, 两点连线为真实位置与初始计算位置的误差, 记锚节点与点pes位置最大距离为lmax。以lmax为半径、以o1、o2、o3为圆心绘制3个圆形区域。并以圆形区域边界为限, 在垂直方向上和水平方向上延伸拓展为一个矩形。从图中可知, 未知节点的真实位置应在以o1、o2、o3为圆心以lmax为半径的3个圆的并集当中, 为保证种群多样性兼顾算法收敛速度, 取该矩形作为粒子群初始种群范围。
|
| 图 1 粒子群种群初始范围 |
本文假设所有节点带有深度传感器, 将三维网络映射到二维平面, 在平面上简化问题。取粒子群算法适应度函数为(8) 式, n为待定位节点周围锚节点数量, di为粒子到第i个锚节点的距离, 优化目标为使适应度函数最小化。
|
(8) |
2) 迭代优化过程
从初始锚节点周围的普通节点开始优化。若某一节点周围有3个及以上已优化节点或初始锚节点, 则可实现该节点的定位优化。当一个节点被定位优化后, 则转化为已定位锚节点参与其他节点的定位优化。依此过程, 迭代进行, 直至所有点全部完成优化, 或未被优化数量不再增加。若周围锚节点未超过3个, 则不能被优化。待其余所有节点被定位优化后, 重新检测未优化节点周围的已优化节点数量, 若有3个及上则按上述方法定位, 少于三个无法定位。
3) 鲁棒四边形规则
在使用PSO算法选取3个节点进行迭代优化时, 当距离测量存在噪声时, 有可能出现一个比实际误差更小的解, 称为定位的翻转歧义[13]。特别是当选取的3个锚节点处于共线位置或者接近共线位置时, 发生翻转歧义的概率将大大增加。如图 2所示, 图 2a)为节点的真实位置, 而通过寻优的方法得到图 2b)解的误差更小。
|
| 图 2 翻转歧义 |
Moore等人[14]针对含噪声距离测量引起的翻转歧义, 提出了使用“鲁棒四边形”而不是任意的四边形来定位节点。如图 3所示, 在鲁棒四边形中由同一顶点相邻两边组成的三角形共有4个(如ΔABC等)。在任意一个三角形中应满足如下关系:
|
| 图 3 鲁棒四边形 |
|
(9) |
式中, b是三角形中最短边的长度, α是三角形内最小夹角, dmin是根据测量误差预设的常数。该方法的思想是确保被定位节点与3个锚节点不存在三点共线或接近共线的情况。通过合理设置dmin可有效过滤歧义的四边形, 保证点定位的唯一性。当有多个鲁棒四边形时, 优先选用含有较多初始锚节点鲁棒四边形。整个RQ-PSO算法的流程如图 4所示。
|
| 图 4 RQ-PSO算法流程 |
由于C型网络两侧节点无法测量到另一侧节点的距离, 使用MDS-MAP算法将产生较大误差, 因此该网络构型可以更好地检验算法的定位精度; 本文采用随机分布于1 000 m×1 000 m范围的100个节点内的C型网络, 其节点分布图如图 6所示, 节点连通图图 7所示。
|
| 图 6 C型网络分布图(初始锚节点比例0.15) |
|
| 图 7 C型网路节点联通图 |
本仿真实验采用Matlab软件, 仿真参数设置如下:普通节点通信半径R为130 m, 锚节点通信半径是普通节点的1.5倍; RQ-PSO与经典PSO粒子群算法粒子种群大小为30, c1、c2的值分别为1.2、0.12, 权重ω初值为0.9。以节点定位误差和粒子群算法总迭代次数作为为算法评价标准。节点定位平均误差定义为
|
(10) |
式中, Num为已定位节点的数量, (xi, yi)为节点的已知真实位置, (
|
(11) |
|
(12) |
|
(13) |
式中, dij可由(11) 式计算得到, 假设所有节点时间都是同步的, Tij为水下声信号由i点传播到j点经过的时间, vs表示声信号在水下的传播速度, P是水温, s是水的盐度, h是水的深度。Tr是j点接收到信号的时间, Ts是i点发送信号的时间, delay是时间延迟。
3.2 仿真结果分析1) 初始锚节点比例不同对定位的影响
在不同初始锚节点比例下, 分别使用MDS-MAP算法、经典PSO算法和RQ-PSO算法进行仿真, 初始锚节点比例设置为0.15至0.45, 间隔0.05。设置2种粒子算法限定误差小于10 m, 即当适应度小于10 m时计算结束。
3种算法的平均定位误差如图 8所示。
|
| 图 8 锚节点比例对定位误差的影响 |
可以看出, 由于是100个节点随机分布在C型区域时, 定位误差虽然有所波动但是随着节点比例增加, 3种定位算法平均误差都是下降趋势, 但是RQ-PSO算法有更低的误差, 而且算法对节点分布随机分布具有更强的适应性。
图 9为锚节点比例为0.25时, 由3种算法分别估计得到的节点位置与实际位置误差, 从图中可以看出MDS-MAP算法的单个节点定位误差最大为560 m左右, 经典PSO算法的最大定位误差为480 m左右, 而RQ-PSO算法单个节点定位误差最大仅100 m, 体现了算法在寻优和鲁棒性上的优势。
|
| 图 9 节点估计位置与真实位置误差 |
2) 2种PSO算法定位误差比较
为检验RQ-PSO算法的定位性能, 还应与经典PSO算法在相同仿真条件下进行比较。图 10为2种粒子群算法在粒子数为30、迭代次数为50不同锚节点比例的同等条件下定位误差曲线。从图中可以看出, 随着节点比例的增加, 2种定位算法的定位误差都有明显下降的趋势, 但是RQ-PSO算法定位误差更低, 比传统PSO算法定位误差降低了约50%左右, 拥有更高的定位精度。
|
| 图 10 同等迭代次数下2种粒子群算法定位误差 |
图 11与图 12为初始锚节点比例0.3时, 同等条件下RQ-PSO算法与经典PSO算法的定位误差图, 从图中可明显看出RQ-PSO算法定位误差更低。其主要原因是本文提出的算法引入了鲁棒四边形规则, 避免了定位歧义性出现, 同时缩小了种群范围, 限制了误差的上限。
|
| 图 11 经典PSO定位算法定位效果(黑线表示估计位置与实际位置的误差, 节点比例0.3) |
|
| 图 12 RQ-PSO算法定位误差图(黑线表示估计位置与实际位置的误差, 节点比例0.3) |
|
| 图 13 2种粒子群算法在不同比例下迭代次数 |
3) 不同锚节点比例下2种PSO收敛速度比较
除比较同等条件下2种PSO算法的定位误差, 仍需对比在同一适应度条件下, 两种算法的收敛速度。取限定误差值即适应度为10 m, 不同初始锚节点比例下2种算法的总迭代次数如图 12所示。从图中可以看出, 随着锚节点的增加, 2种粒子群算法的迭代次数都在减少。由于种群粒子的分布由粗定位限制初始, 且具有随机性, 故本文提出的算法迭代次数虽有波动, 但是总迭代次数仍少传统PSO算法, 证明了算法拥有更好的收敛性和更低的计算开销。
4 结语水下无线传感器网络在应用MDS-MAP算法时, 网络构型严重影响节点之间的距离矩阵精度, 将导致定位误差较大。针对此不足, 本文通过结合粒子群算法, 并引进鲁棒四边形规则, 提出了一种RQ-PSO算法对未知节点进行定位。仿真实验表明, 本文提出的算法可弥补MDS-MAP算法由于距离矩阵不精确而定位误差较大的不足, 并且有效解决了定位歧义性问题, 在平均定位误差和个体定位误差方面均优于MDS-MAP算法和传统PSO算法, 且算法拥有更快的收敛性能和更低计算能量消耗, 在未来工程应用当中具有广泛的应用前景。
| [1] |
何明, 陈秋丽, 叶旭光, 等. 水下声学传感器网络研究[J]. 电信科学, 2013, 29(11): 72-76.
He Ming, Chen Qiuli, Ye Xuguang, et al. Study on Underwater Acoustic Sensor Network[J]. Telecommunications Science, 2013, 29(11): 72-76. DOI:10.3969/j.issn.1000-0801.2013.11.012 (in Chinese) |
| [2] |
姚西. 水下无线传感器网络定位技术综述[J]. 现代电子技术, 2013(7): 11-15.
Yao Xi. Summary of Localization Technologies for Underwater Wireless Sensor Networks[J]. Modern Electronics Technique, 2013(7): 11-15. (in Chinese) |
| [3] | Abdi A, Huanihai G. A New Compact Multichannel Receiver for Underwater Wireless Communication Networks[J]. IEEE T Wirel Commun, 2009, 8(7): 3326-3329. DOI:10.1109/TWC.2009.070566 |
| [4] | ROL M. AUV-Aided Localization for Underwater Sensor Net-Works[C]//International Conference on Wireless Algorithms, 2007:44-54 |
| [5] | Wang J. Geometric Structure of High-Dimensional Data and Dimensionality Reduction[M]. Beijing, Higher Education Press, 2012 |
| [6] | Shang Y, Ruml W, Zhang Y, et al. Localization from Mere Connectivity[C]//Proceedings of the Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2003: 201-212 |
| [7] | Chen H B, Wang D Q, Yuan F, et al. A MDS-Based Localization Algorithm for Underwater Wireless Sensor Network[C]//Oceans IEEE, 2013: 1-5 |
| [8] |
温龙飞, 崔灵果, 张百海, 金雪. 不均匀布置传感器网络定位优化算法[J]. 兵工学报, 2013, 34(5): 639-643.
Wen Longfei, Cui Lingguo, Zhang Baihai, Jin Xue. Research on Location Algorithm for Nonuniformly Deployed Sensor Networks[J]. Acta Armamentarii, 2013, 34(5): 639-643. (in Chinese) |
| [9] | Shang Y, Ruml W. Improved MDS-Based Localization[C]//Joint Conference of the IEEE Computer and Communications Societies, 2004: 2640-2651 |
| [10] |
马振华. 现代应用数学手册:概率统计与随机过程卷[M]. 北京: 清华大学出版社, 2000.
Ma Zhenhua. Current Handbook of Applied Mathematics: Probability, Statistics and Stochastic Processes[M]. Beijing: Tsinghua University Press, 2000. (in Chinese) |
| [11] |
张贤达. 矩阵分析与应用[M]. 北京: 清华大学出版社, 2013.
Zhang Xianda. Matrix Analysis and Applications[M]. Beijing: Tsinghua University Press, 2013. (in Chinese) |
| [12] | Shi Yuhui, Russell C. Eberhart. Parameter Selection in Particle Swarm Optimization[C]//Proceeding of the 7th International Conference on Evolutionary Programming Ⅶ. Springer-Verlag, London, UK, 1998:591-600 |
| [13] |
杨铮, 吴陈沭, 刘云浩. 位置计算:无线网络定位与可定位性[M]. 北京: 清华大学出版社, 2014.
Yang Zheng, Wu Chenshu, Liu Yunhao. Location-Based Computing: Localization and Localizability of Wireless Networks[M]. Beijing: Tsinghua University Press, 2014. (in Chinese) |
| [14] | Moore D, Leonard J, Rus D, et al. Robust Distributed Network Localization with Noisy Range Measurements[C]//Proceedings of ACM SenSys, 2004:50-61 |
2. 96617 Unit PLA, Luzhou 646000, China;
3. Xi'an Aerosspace Precision Mechatronric Institute, Xi'an 710072, China
