﻿ SAL：无线传感器网络中信号强度辅助的定位算法

# SAL：无线传感器网络中信号强度辅助的定位算法SAL: Signal Strength Assisted Localization in Wireless Sensor Networks

Abstract: To solve the problem of current range-free localization algorithms in failing to balance localization precision and localization cost well, Signal Strength Assisted Localization (SAL) algorithm is proposed. SAL takes advantage of the discipline that radio signal strength (RSS) monotonically decreased qualitatively as physical distance increasing in open outdoor environment. SAL distinguishes 1-hop anchors into sub-hop resolution beyond connectivity and utilizes this heuristic in-formation about which anchor is closer and which is further to associate location estimation of unknown nodes. Without increasing additional hardware and communication cost, the localization precision is improved effectively and network localization coverage ratio is guaranteed to be 100%. Extensive simulations and platform experiment show that, SAL possesses the advantages of simple implementation of centroid algorithm and high localization precision of APIT. Under random deployment, the localization precision of SAL is better than APIT and the computational cost of SAL is less than a quarter of APIT on average.

1. 引言

2. 相关工作

2.1. 测距无关定位算法

APIT定位算法 [11] 是对质心法的改进，首先对邻居锚节点组合进行PIT测试，通过计算满足PIT条件的锚节点三角形的重叠区域，来缩小待定位节点所处的位置范围，最后将重叠区域的质心作为节点的估计位置。APIT的计算复杂度很高，对于某个待定位节点而言，假设其邻居锚节点数为n，APIT算法需要穷尽所有的锚节点组合，复杂度为O(n3)。除此之外，APIT在计算三角形的重叠区域时，需要将整个待定位区域划分为栅格，每计算一个新三角形与当前重叠区域的交集时，需要对栅格进行逐一扫描，扫描复杂度为O(m∙n3)，m是区域划分的栅格数目。因而APIT难以在能量和计算资源严重受限的传感器节点上分布式实现。

MSP [12] 利用声音信号在空间中的传播规律，距离声源越远，信号的到达时间越迟。依据信号接收时间，将一跳范围内的节点进行距离远近的排序，进而确定节点间的相对位置。由于声音信号的发射与接收需要额外的硬件，且当区域范围大、待定位节点数多时，要在区域边界以大功率多次发射声源信号，使之从多个不同方向覆盖整个区域，因而MSP的硬件开销大、能耗高、实现复杂，在实际传感器网络中的应用受限。

2.2. 系统布设开销

3. SAL算法

4. 性能比较

4.1. 仿真分析

4.1.1. 建立仿真模型

${P}_{r}={P}_{t}-Pl\left({d}_{0}\right)-10n{\mathrm{log}}_{10}\left(\frac{d}{{d}_{0}}\right)-{X}_{\sigma }$

d是发送方和接收方之间的距离，d0是一个参考距离，n是路径损耗系数，Xs是一个零均值的高斯分布，标准差为s，表征了阴影效应。在室外环境进行大规模测量，通过曲线拟合的方法，确定上述参数取值如表1 [14] ：

Figure 1. The flow show of algorithm SAL

Table 1. Parameters of wireless channel model

4.1.2. 仿真结果及分析

1) SAL的定位效果

2) ANR对定位误差的影响

Figure 2. Random deployment scenario

Figure 3. The centration of convex algorithm

Figure 4. Localization results of SAL

3) SAL的计算复杂度

APIT算法需要穷尽所有的锚节点组合，计算复杂度为O(n3)。而SAL算法在PIT判断阶段，并不是穷尽所有的锚节点组合，而是从距离最近的锚节点开始进行PIT判断，一旦满足，立即停止，只有在最差情况下才会穷尽所有的锚节点组合。

4.2. 现场实验分析

4.2.1 . 实验设备和场景

4.2.2 . 实验结果

Figure 5. Relationship of localization error and ANR

Figure 6. Computation complexity of APIT and SAL

(a) (b)

Figure 7. (a) USRP platform, (b) Experiment scenario

Figure 8. Experiment topology

Figure 9. Experiment results

5. 结束语

[1] 钱志鸿, 王义君. 面向物联网的无线传感器网络综述[J]. 电子与信息学报, 2013, 35(1): 215-227.

[2] 廖洁, 张磊, 马飒飒. 一种低能耗的WSN覆盖控制优化策略[J]. 计算机工程, 2016, 42(11): 109-113.

[3] 黄庆宇, 刘新华. 基于线性最小二乘估计的传感器网节点三维测距定位算法[J]. 计算机工程, 2016, 42(12): 11- 15.

[4] Priyantha, N.B., Chakraborty, A. and Balakrishnan, H. (2000) The Cricket Location-Support System. International Conference on Mobile Computing & Networking, 4, 32-43.
https://doi.org/10.1145/345910.345917

[5] Whitehouse, K., Karlof, C. and Culler, D. (2006) A Practical Evaluation of Radio Signal Strength for Ranging-Based Localization. ACM, 11, 41-52.

[6] He, T., Huang, C., Lum, B., Stankovic, J. and Adelzaher, T. (2003) Range-free localization schemes for large scale sensor networks. In Proceedings of International Conference on Mobile Computing & Networking, San Diego, 81-95.
https://doi.org/10.1145/938985.938995

[7] Tao, Q.H. and Zhang, L.H. (2016) Enhancement of DV-Hop by Weighted Hop Distance. IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference, Xi'an, 1577-1580.

[8] Jiang, Mi., Li, Y.F., Ge, Y., et al. (2015) An Advanced DV-hop Localization Algorithm in Wireless Sensor Network. International Journal of Control and Automation, 8, 405-422.
https://doi.org/10.14257/ijca.2015.8.3.39

[9] Salama, M. and Kandil, M. (2016) An Improved DV-hop Localization Algorithm Based on Modified Hop-Size. IEEE World Symposium on Computer Applications & Research, 83-86.
https://doi.org/10.1109/WSCAR.2016.11

[10] Fang, X. (2015) Improved DV-Hop Positioning Algorithm Based on Compensation Coefficient. Journal of Software Engineering, 9, 650-657.
https://doi.org/10.3923/jse.2015.650.657

[11] Xiong, Y.F, Wu, N. and Wang, H. (2017) On the Performance Limits of Cooper-ative Localization in Wireless Sensor Networks with Strong Sensor Position Uncertainty. IEEE Communications Letters, 9, 1.
https://doi.org/10.1109/LCOMM.2017.2687869

[12] Zhong, Z.G. and He, T. (2007) MSP: Multi-Sequence Positioning of Wireless Sensor Nodes. International Conference on Embedded Networked Sensor Systems, 15-28.
https://doi.org/10.1145/1322263.1322266

[13] Rappapport, T.S. (1996) Wireless Communications: Principles and Practice. Prentice Hall, Upper Saddle River.

[14] Zuniga, M. and Krishnamachari, B. (2004) Analyzing the Transitional Region in Low Power Wireless Links. IEEE Communications Society Conference on Sensor & Ad Hoc Communications & Networks, 71, 517-526.
https://doi.org/10.1109/SAHCN.2004.1381954

Top