高级搜索

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

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

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

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

    作者简介: 蒋俊正: 男,1983年生,教授,博士生导师,研究方向为图信号处理理论与算法、分布式信号处理理论与算法、大规模传感器网络数据处理;
    李杨剑: 男,1993年生,硕士生,研究方向为无线传感器网络节点定位算法;
    赵海兵: 男,1990年生,硕士生,研究方向为传感器网络定位算法;
    欧阳缮: 男,1960年生,教授,博士生导师,研究方向为雷达信号处理、通信信号处理
    通讯作者: 蒋俊正,jzjiang@guet.edu.cn
  • 基金项目: 国家自然科学基金(61761011, 61871425),广西自然科学基金(2017GXNSFAA198173)

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

English

    1. [1]

      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

    2. [2]

      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

    3. [3]

      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

    4. [4]

      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.

    5. [5]

      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

    6. [6]

      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

    7. [7]

      吕淑芳. 无线传感器网络节点定位研究综述[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

    8. [8]

      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

    9. [9]

      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

    10. [10]

      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

    11. [11]

      汪晗, 成昂轩, 王坤, 等. 无线传感器网络分布式迭代定位误差控制算法[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

    12. [12]

      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.

    13. [13]

      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

    14. [14]

      王刚. 无线传感器网络中定位与跟踪算法的研究[D]. [博士论文], 西安电子科技大学, 2011.
      WANG Gang. Approaches to localization and tracking in wireless sensor networks[D]. [Ph.D. dissertation], Xidian University, 2011.

    15. [15]

      段琼, 戴璟, 乔慧. 一种改进的牛顿法及其在欧式距离选址模型中的应用[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

    16. [16]

      蒋俊正. DFT调制滤波器组的设计算法研究[D]. [博士论文], 西安电子科技大学, 2011.
      JIANG Junzheng. Design algorithms of DFT modulated filter banks[D]. [Ph.D. dissertation], Xidian University, 2011.

    1. [1]

      田洪亮, 钱志鸿, 王义君, 梁潇. 能量分簇传感器网络距离误差校正MDS-MAP定位算法. 电子与信息学报, 2017, 39(7): 1735-1740.

    2. [2]

      汪晗, 成昂轩, 王坤, 宋树伟. 无线传感器网络分布式迭代定位误差控制算法. 电子与信息学报, 2018, 40(1): 72-78.

    3. [3]

      杜晓玉, 孙力娟, 郭剑, 韩崇. 异构无线传感器网络覆盖优化算法. 电子与信息学报, 2014, 36(3): 696-702.

    4. [4]

      孙保明, 郭艳, 李宁, 钱鹏. 无线传感器网络中基于压缩感知的动态目标定位算法. 电子与信息学报, 2016, 38(8): 1858-1864.

    5. [5]

      孙保明, 郭艳, 李宁, 张星航, 李艾静. 无线传感器网络中面向压缩感知定位的动态字典算法. 电子与信息学报, 2017, 39(10): 2513-2519.

    6. [6]

      易本顺, 陈杰, 肖进胜. 无线传感器网络优化的任务管理算法研究. 电子与信息学报, 2010, 32(11): 2606-2611.

    7. [7]

      罗炬锋, 邱云周, 付耀先, 袁晓兵. 研究片内多径分离技术在基于RSSI定位中的应用. 电子与信息学报, 2011, 33(4): 891-895.

    8. [8]

      蒋俊正, 杨杰, 欧阳缮. 一种新的无线传感器网络中异常节点检测定位算法. 电子与信息学报, 2018, 40(10): 2358-2364.

    9. [9]

      郝晓辰, 巩倩倩, 侯爽, 刘彬, 孙超. 无线传感器网络中支持并行传输的信道与功率联合优化博弈算法. 电子与信息学报, 2014, 36(7): 1720-1727.

    10. [10]

      何风行, 余志军, 刘海涛. 基于压缩感知的无线传感器网络多目标定位算法. 电子与信息学报, 2012, 34(3): 716-721.

    11. [11]

      冯缜, 刘威, 徐侃如, 程文青, 杨宗凯. 无线传感器网络中的鲁棒区域定位算法. 电子与信息学报, 2008, 30(9): 2263-2266.

    12. [12]

      王向阳, 张源. 一种改进的分布式最大权独立集算法. 电子与信息学报, 2012, 34(3): 689-693.

    13. [13]

      蒋鹏, 宋华华. 基于动态分簇路由优化和分布式粒子滤波的传感器网络目标跟踪方法. 电子与信息学报, 2012, 34(9): 2187-2193.

    14. [14]

      施孝盼, 洪涛. 基于凸优化的稀疏阵列方向调制信号综合算法研究. 电子与信息学报, 2017, 39(11): 2563-2570.

    15. [15]

      方斌, 丑武胜, 董明杰, 马鑫, 郭晓旗. 基于概率迭代匹配的水下机器人定位算法. 电子与信息学报, 2014, 36(4): 993-997.

    16. [16]

      沈连丰, 张瑞, 朱亚萍, 吴怡. 面向自动驾驶的车辆精确实时定位算法. 电子与信息学报, 2020, 42(1): 28-35.

    17. [17]

      单志龙, 刘兰辉, 张迎胜, 黄广雄. 一种使用灰度预测模型的强自适应性移动节点定位算法. 电子与信息学报, 2014, 36(6): 1492-1497.

    18. [18]

      程银波, 司菁菁, 候肖兰. 适用于无线传感器网络的层次化分布式压缩感知. 电子与信息学报, 2017, 39(3): 539-545.

    19. [19]

      秦智超, 周正, 赵小川. 一种分簇无线传感器网络中的分布式信源编码算法. 电子与信息学报, 2013, 35(2): 328-334.

    20. [20]

      李立, 刘勇攀, 杨华中, 汪蕙. 无线传感器网络分布式一致时间同步协议的收敛分析及加速设计. 电子与信息学报, 2010, 32(9): 2045-2051.

  • 图 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
  • 加载中
图(3)表(3)
计量
  • PDF下载量:  58
  • 文章访问数:  993
  • HTML全文浏览量:  1008
文章相关
  • 通讯作者:  蒋俊正, jzjiang@guet.edu.cn
  • 收稿日期:  2018-11-28
  • 录用日期:  2019-05-19
  • 网络出版日期:  2019-05-27
  • 刊出日期:  2019-12-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章