高级搜索

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

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

引用本文: 蒋俊正, 李杨剑, 赵海兵, 欧阳缮. 一种大规模传感器网络节点分布式定位算法[J]. 电子与信息学报, 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, 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]. Proceedings of 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, 8. 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, 8. 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]. Proceedings of 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]

      何灏, 易卫东, 陈永锐, 王喆. 基于无迹卡尔曼滤波估计的无线传感器网络时钟分辨率优化. 电子与信息学报,

    2. [2]

      徐保庆, 赵永波, 庞晓娇. 基于实值处理的联合波束域双基地MIMO雷达测角算法. 电子与信息学报,

    3. [3]

      吕增威, 魏振春, 韩江洪, 孙仁浩, 夏成凯. 基于多目标优化的无线传感器网络移动充电及数据收集算法. 电子与信息学报,

    4. [4]

      秦宁宁, 金磊, 许健, 徐帆, 杨乐. 邻近信息约束下的随机异构无线传感器网络节点调度算法. 电子与信息学报,

    5. [5]

      张艳, 陈建华, 唐猛. 多层中继网络上的分布式LT码. 电子与信息学报,

    6. [6]

      史久根, 王继, 张径, 徐皓. 软件定义网络中基于流量管理的分布式防火墙策略. 电子与信息学报,

    7. [7]

      逯志宇, 王建辉, 秦天柱, 巴斌. 基于对称旋转不变性的非圆相干分布源直接定位算法. 电子与信息学报,

    8. [8]

      冯维, 徐永鑫, 刘浩, 许晓荣, 姚英彪. 无线多跳网络快速跨层资源优化分配算法. 电子与信息学报,

    9. [9]

      陆潞, 高梅国. 分布式阵列雷达基线位置和相位误差的卫星标校方法. 电子与信息学报,

    10. [10]

      刘毅, 马莹, 刘轩. 快衰落瑞利信道下分布式线性卷积空时码的分集增益. 电子与信息学报,

    11. [11]

      蒋莹, 王冰切, 韩俊, 何翼. 基于分布式压缩感知的宽带欠定信号DOA估计. 电子与信息学报,

    12. [12]

      黄一才, 李森森, 鲍博武, 郁滨. 面向ZigBee网络节点安全定位的消息签名方案. 电子与信息学报,

    13. [13]

      田子建, 贺方圆. 一种基于分布式压缩感知的矿井目标指纹数据库建立方法. 电子与信息学报,

    14. [14]

      庄陵, 关鹃, 马靖怡, 王光宇. 一种基于结构优化的FIR滤波器舍入噪声性能改进方案. 电子与信息学报,

    15. [15]

      周牧, 王烟濛, 袁慧, 田增山. 基于Mann-Whitney秩和检验的无线局域网室内映射与定位方法. 电子与信息学报,

    16. [16]

      刘小龙. 改进多元宇宙算法求解大规模实值优化问题. 电子与信息学报,

    17. [17]

      耿友林, 解成博, 尹川, 郭兰图, 王先义. 基于卡尔曼滤波的接收信号强度指示差值定位算法. 电子与信息学报,

    18. [18]

      余东平, 郭艳, 李宁, 刘杰, 杨思星. 基于多维测量信息的压缩感知多目标无源被动定位算法. 电子与信息学报,

    19. [19]

      王守华, 陆明炽, 孙希延, 纪元法, 胡丁梅. 基于无迹卡尔曼滤波的iBeacon/INS数据融合定位算法. 电子与信息学报,

    20. [20]

      李世宝, 王升志, 刘建航, 黄庭培, 张鑫. 基于接收信号强度非齐性分布特征的半监督学习室内定位指纹库构建. 电子与信息学报,

  • 图 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 = 1e{\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下载量:  33
  • 文章访问数:  334
  • HTML全文浏览量:  268
文章相关
  • 通讯作者:  蒋俊正, jzjiang@guet.edu.cn
  • 收稿日期:  2018-11-28
  • 录用日期:  2019-05-19
  • 网络出版日期:  2019-05-27
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章