高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种大规模传感器网络节点分布式定位算法

蒋俊正 李杨剑 赵海兵 欧阳缮

蒋俊正, 李杨剑, 赵海兵, 欧阳缮. 一种大规模传感器网络节点分布式定位算法[J]. 电子与信息学报, 2019, 41(12): 3022-3028. doi: 10.11999/JEIT181101
引用本文: 蒋俊正, 李杨剑, 赵海兵, 欧阳缮. 一种大规模传感器网络节点分布式定位算法[J]. 电子与信息学报, 2019, 41(12): 3022-3028. doi: 10.11999/JEIT181101
Junzheng JIANG, Yangjian LI, Haibing ZHAO, Shan OUYANG. A Distributed Node Localization Algorithm for Large Scale Sensor Networks[J]. Journal of Electronics & Information Technology, 2019, 41(12): 3022-3028. doi: 10.11999/JEIT181101
Citation: Junzheng JIANG, Yangjian LI, Haibing ZHAO, Shan OUYANG. A Distributed Node Localization Algorithm for Large Scale Sensor Networks[J]. Journal of Electronics & Information Technology, 2019, 41(12): 3022-3028. doi: 10.11999/JEIT181101

一种大规模传感器网络节点分布式定位算法

doi: 10.11999/JEIT181101
基金项目: 国家自然科学基金(61761011, 61871425),广西自然科学基金(2017GXNSFAA198173)
详细信息
    作者简介:

    蒋俊正:男,1983年生,教授,博士生导师,研究方向为图信号处理理论与算法、分布式信号处理理论与算法、大规模传感器网络数据处理

    李杨剑:男,1993年生,硕士生,研究方向为无线传感器网络节点定位算法

    赵海兵:男,1990年生,硕士生,研究方向为传感器网络定位算法

    欧阳缮:男,1960年生,教授,博士生导师,研究方向为雷达信号处理、通信信号处理

    通讯作者:

    蒋俊正 jzjiang@guet.edu.cn

  • 中图分类号: TP393

A Distributed Node Localization Algorithm for Large Scale Sensor Networks

Funds: The National Natural Science Foundation of China (61761011, 61371186), The Natural Science Foundation of Guangxi (2017GXNSFAA198173)
  • 摘要: 针对大规模无线传感器网络(WSN)中节点难以定位的问题,该文提出一种基于改进牛顿法的分布式定位算法。该算法包括网络划分和分布式算法。首先,根据节点位置和节点之间直接相连的距离信息,将无线传感器网络划分为若干个重叠的子区域,并将子区域的定位问题归结为无约束优化问题,每个子区域可以独立计算;然后,使用分布式算法估计子区域中的节点位置并进行局部融合。实验结果表明,与已有算法相比,该算法具有良好的扩展性,在大规模网络中定位精度更高,能满足大规模无线传感器网络中节点定位需求。
  • 图  1  融合求平均示意图

    图  2  不同$p$情况下的${\rm{\overline {err}}}$

    图  3  不同$r$情况下的${\rm{\overline{err}}}$

    表  1  子区域定位算法

     输入:使用三边定位方法,粗略获得LU节点的初始值,提取子区域$s$中LU节点的位置${{\text{p}}_k}$,作为初始值。设$k = 0$,表示第$k$次迭代;
     (1) 基于子区域目标函数$f({{\text{p}}_k})$,计算梯度向量$\nabla f({{\text{p}}_k})$和修正后的Hesse矩阵${\nabla ^2}f({{\text{p}}_k})$;
     (2) 计算搜索方向${{\text{q}}_k}$:${{\text{q}}_k} = - {\nabla ^2}f{({{\text{p}}_k})^{ - 1}}\nabla f({{\text{p}}_k})$;
     (3) 更新子区域$s$中LU节点位置,其中,步长设置为单位步长:${{\text{p}}_{k + 1}} = {{\text{p}}_k} + {{\text{q}}_k}$;
     (4) 判断迭代终止条件。如果$\frac{{\left| {f({{\text{p}}_{k + 1}}) - f({{\text{p}}_k})} \right|}}{{1 + \left| {f({{\text{p}}_k})} \right|}} < \delta $($\delta $是一个很小的正数,本文设置为$\delta = 1e{\rm{ - }}9$)或迭代次数$k > 100$,则终止迭代,${{\text{p}}_{k + 1}}$即为
    子区域优化最终结果;否则令$k = k + 1$,返回至第(1)步;
     输出:${{\text{p}}_{k + 1}}$。
    下载: 导出CSV

    表  3  本文算法和文献[1,2,9]算法在不同参数下实验结果对比

    参数设置时间${\rm{\bar e\bar r\bar r}}$
    $N$$r$${\rm{nf}}$本文算法文献[1]文献[9]文献[2]本文算法文献[1]文献[9]文献[2]
    1000.40012.6 s15.1 s9.8 s2.6 s5.7e-40.05830.04896.5e-10
    1000.400.2032.0 s180.6 s27.8 s3.9 s0.01140.09420.07460.0107
    5000.15071.1 s132.1 s393.2 s92.7 s0.00110.01240.00254.0e-4
    5000.150.20176.9 s127.7 s986.3 s91.8 s0.00480.03250.01640.0072
    10000.110309.2 s348.7 s51.0 min*0.00150.00970.0026*
    10000.110.20522.5 s339.3 s2.4 h*0.00430.02490.0121*
    20000.070369.1 s760.5 s*0.00220.0209*
    20000.070.20576.2 s649.5 s*0.00550.0241*
    40000.050555.9 s23.1 min*0.00290.0266*
    40000.050.20840.3 s27.5 min*0.00620.0238*
    100000.03023.3 min1.1 h*0.00340.0172*
    100000.030.2031.6 min1.2 h*0.00640.0147*
    下载: 导出CSV

    表  2  基于改进牛顿法的分布式定位算法

     准备工作:将$N$个传感器随机部署在${[ - 0.5, 0.5]^2}$的单位正方形区域内,区域中有$m$个LU节点,$n$个LA节点,节点的通信半径均为$r$。根据 LU节点位置及与其直接相连的邻居节点,将WSN划分为$m$个重叠子区域,$m$个子区域可以进行分布式计算。设$t = 0$;
     输入:利用三边定位方法获得WSN中LU节点的粗略估计值${\tilde{\text{v}}^{(t)}}$,作为基于单位步长改进牛顿法的初始值;
        (1) 利用表1中子区域定位算法,对$m$个子区域独立优化求解。得到每个子区域$s(s = 1, 2, \cdots , m)$中所有LU节点的估计位置${\text{p}}_s^{(t + 1)}$;
        (2) 收集$m$个子区域中LU节点估计位置${\text{p}}_s^{(t + 1)}(s = 1, 2, \cdots , m)$,对重叠子区域中的LU节点进行融合求平均,作为LU节点的估计位    置${\tilde{\text{v}}^{(t + 1)}}$;
        (3) 判断迭代终止条件。如果${\rm{max}}{\left\| {\tilde {\text{v}}_i^{(t + 1)} - \tilde {\text{v}}_i^{(t)}} \right\|_2} \le \eta $($\eta $是一个小的正数,本文设置为$\eta = 1{\rm e}{\rm{ - } }2$), $i = 1, 2, ·\!·\!· , m$,则终止迭代,${\tilde{\text{v}}^{(t + 1)}}$    即为最终估计出的LU节点位置;否则将${\tilde{\text{v}}^{(t + 1)}}$作为基于单位步长的改进牛顿法的初始值,设$t = t + 1$并返回至(1)继续迭代;
     输出:${\tilde {\text{v}}^{(t + 1)}}$。
    下载: 导出CSV
  • SRIRANGARAJAN S, TEWFIK A H, and LUO Zhiquan. Distributed sensor network localization using SOCP relaxation[J]. IEEE Transactions on Wireless Communications, 2008, 7(12): 4886–4895. doi: 10.1109/T-WC.2008.070241
    BISWAS P, LIANG T C, TOH K C, et al. Semidefinite programming approaches for sensor network localization with noisy distance measurements[J]. IEEE Transactions on Automation Science and Engineering, 2006, 3(4): 360–371. doi: 10.1109/TASE.2006.877401
    PATWARI N, ASH J N, KYPEROUNTAS S, et al. Locating the nodes: cooperative localization in wireless sensor networks[J]. IEEE Signal Processing Magazine, 2005, 22(4): 54–69. doi: 10.1109/MSP.2005.1458287
    VICENTE D, TOMIC S, BEKO M, et al. Performance analysis of a distributed algorithm for target localization in wireless sensor networks using hybrid measurements in a connection failure scenario[C]. 2017 International Young Engineers Forum, Almada, Portugal, 2017: 36–41. doi: 10.1109/YEF-ECE.2017.7935637.
    CHOWDHURY T J S, ELKIN C, DEVABHAKTUNI V, et al. Advances on localization techniques for wireless sensor networks: A survey[J]. Computer Networks, 2016, 110: 284–305. doi: 10.1016/j.comnet.2016.10.006
    SANYAL R, JAISWAL M, and CHAUDHURY K N. On a registration-based approach to sensor network localization[J]. IEEE Transactions on Signal Processing, 2017, 65(20): 5357–5367. doi: 10.1109/TSP.2017.2726990
    吕淑芳. 无线传感器网络节点定位研究综述[J]. 传感器与微系统, 2016, 35(5): 1–3. doi: 10.13873/J.1000-9787(2016)05-0001-03

    LÜ Shufang. Research review on wireless sensor networks node localization[J]. Transducer and Microsystem Technologies, 2016, 35(5): 1–3. doi: 10.13873/J.1000-9787(2016)05-0001-03
    WANG Zizhuo, ZHENG Song, YE Yinyu, et al. Further relaxations of the semidefinite programming approach to sensor network localization[J]. SIAM Journal on Optimization, 2008, 19(2): 655–673. doi: 10.1137/060669395
    SOARES C, XAVIER J, and GOMES J. Simple and fast convex relaxation method for cooperative localization in sensor networks using range measurements[J]. IEEE Transactions on Signal Processing, 2015, 63(17): 4532–4543. doi: 10.1109/TSP.2015.2454853
    BISWAS P, LIAN T C, WANG T C, et al. Semidefinite programming based algorithms for sensor network localization[J]. ACM Transactions on Sensor Networks, 2006, 2(2): 188–220. doi: 10.1145/1149283.1149286
    汪晗, 成昂轩, 王坤, 等. 无线传感器网络分布式迭代定位误差控制算法[J]. 电子与信息学报, 2018, 40(1): 72–78. doi: 10.11999/JEIT170344

    WANG Han, CHENG Angxuan, WANG Kun, et al. Error control algorithm of distributed localization in wireless sensor networks[J]. Journal of Electronics &Information Technology, 2018, 40(1): 72–78. doi: 10.11999/JEIT170344
    TOMIC S, BEKO M, DINIS R, et al. Cooperative localization in wireless sensor networks using combined measurements[C]. The 23rd Telecommunications Forum Telfor, Belgrade, Serbia, 2015: 488–491. doi: 10.1109/TELFOR.2015.7377513.
    CHANG Shengming, LI Youming, WANG Hui, et al. RSS based cooperative localization in wireless sensor networks via second-order cone relaxation[J]. IEEE Access, 2018, 6: 54097–54105. doi: 10.1109/ACCESS.2018.2871600
    王刚. 无线传感器网络中定位与跟踪算法的研究[D]. [博士论文], 西安电子科技大学, 2011.

    WANG Gang. Approaches to localization and tracking in wireless sensor networks[D]. [Ph.D. dissertation], Xidian University, 2011.
    段琼, 戴璟, 乔慧. 一种改进的牛顿法及其在欧式距离选址模型中的应用[J]. 物流技术, 2017, 36(8): 79–82. doi: 10.3969/j.issn.1005-152X.2017.08.019

    DUAN Qiong, DAI Jing, and QIAO Hui. An improved newton method and its application in Euclidean distance based location model[J]. Logistics Technology, 2017, 36(8): 79–82. doi: 10.3969/j.issn.1005-152X.2017.08.019
    蒋俊正. DFT调制滤波器组的设计算法研究[D]. [博士论文], 西安电子科技大学, 2011.

    JIANG Junzheng. Design algorithms of DFT modulated filter banks[D]. [Ph.D. dissertation], Xidian University, 2011.
  • 加载中
图(3) / 表(3)
计量
  • 文章访问数:  3191
  • HTML全文浏览量:  1735
  • PDF下载量:  154
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-11-28
  • 修回日期:  2019-05-19
  • 网络出版日期:  2019-05-27
  • 刊出日期:  2019-12-01

目录

    /

    返回文章
    返回