高级搜索

邻近信息约束下的随机异构无线传感器网络节点调度算法

秦宁宁 金磊 许健 徐帆 杨乐

引用本文: 秦宁宁, 金磊, 许健, 徐帆, 杨乐. 邻近信息约束下的随机异构无线传感器网络节点调度算法[J]. 电子与信息学报, 2019, 41(10): 2310-2317. doi: 10.11999/JEIT190094 shu
Citation:  Ningning QIN, Lei JIN, Jian XU, Fan XU, Le YANG. Neighbor Information Constrained Node Scheduling in Stochastic Heterogeneous Wireless Sensor Networks[J]. Journal of Electronics and Information Technology, 2019, 41(10): 2310-2317. doi: 10.11999/JEIT190094 shu

邻近信息约束下的随机异构无线传感器网络节点调度算法

    作者简介: 秦宁宁: 女,1980年生,副教授,硕士生导师,研究方向为无线传感器网络及应用;
    金磊: 男,1993年生,硕士生,研究方向为无线传感器网络覆盖;
    许健: 男,1992年生,硕士生,研究方向为无线传感器网络覆盖;
    徐帆: 男,1988年生,讲师,硕士生导师,研究方向为信号处理与应用;
    杨乐: 男,1979年生,副教授,硕士生导师,研究方向为无线信号统计与应用
    通讯作者: 秦宁宁,ningning801108@163.com
  • 基金项目: 国家自然科学基金项目(61702228),江苏省自然科学基金(BK20170198),雷达成像与微波光子教育部重点实验室开放基金(NJ20170001-7),江苏省博士后科研资助计划(1601012A),江苏省"六大人才高峰"计划(DZXX-026),中央高校基本科研业务费专项资金资助(JUSRP1805XNC)

摘要: 针对高密度部署的随机异构传感器网络内部存在的覆盖冗余问题,该文提出一种随机异构无线传感器网络的节点调度算法(NSSH)。在网络原型拓扑的支撑下构建Delaunary三角剖分,规划出节点进行本地化调度的局部工作子集。通过折中与邻近节点的空外接圆半径,完成对感知半径的独立配置;引入几何线、面概念,利用重叠面积和有效约束圆弧完成对灰、黑色节点的分类识别,使得节点仅依赖本地及邻居信息进行半径调整和冗余休眠。仿真结果表明,NSSH能以低复杂度的代价,近似追平贪婪算法的去冗余性能,并表现出了对网络规模、异构跨度和参数配置的低敏感性。

English

    1. [1]

      SLIJEPCEVIC S and POTKONJAK M. Power efficient organization of wireless sensor networks[C]. Conference Record IEEE International Conference on Communications, Helsinki, Finland, 2001: 472–476.

    2. [2]

      付寅飞, 熊庆旭. 综合路由的无线传感器网络覆盖调度[J]. 北京航空航天大学学报, 2011, 37(7): 801–804, 838. doi: 10.13700/j.bh.1001-5965.2011.07.004
      FU Yinfei and XIONG Qingxu. Coverage-scheduling integrated routing in wireless sensor networks[J]. Journal of Beijing University of Aeronautics and Astronautics, 2011, 37(7): 801–804, 838. doi: 10.13700/j.bh.1001-5965.2011.07.004

    3. [3]

      韩志杰, 吴志斌, 王汝传, 等. 新的无线传感器网络覆盖控制算法[J]. 通信学报, 2011, 32(10): 174–184. doi: 10.3969/j.issn.1000-436X.2011.10.022
      HAN Zhijie, WU Zhibin, WANG Ruchuan, et al. Novel coverage control algorithm for wireless sensor network[J]. Journal on Communications, 2011, 32(10): 174–184. doi: 10.3969/j.issn.1000-436X.2011.10.022

    4. [4]

      党小超, 邵晨光, 郝占军. 半径可调的无线传感器网络三维覆盖算法[J]. 计算机应用, 2018, 38(9): 2581–2586, 2615. doi: 10.11772/j.issn.1001-9081.2018020357
      DANG Xiaochao, SHAO Chenguang, and HAO Zhanjun. 3D-coverage algorithm based on adjustable radius in wireless sensor network[J]. Journal of Computer Applications, 2018, 38(9): 2581–2586, 2615. doi: 10.11772/j.issn.1001-9081.2018020357

    5. [5]

      BHATTACHARJEE M and GUPTA S. Determining redundant nodes in a location unaware wireless sensor network[C]. IEEE International Conference on Advanced Communications, Control and Computing Technologies, Ramanathapuram, India, 2014: 858–862.

    6. [6]

      CHENAIT M, ZEBBANE B, FILALI S, et al. A low-complex coverage eligibility algorithm for wireless sensor networks[C]. International Conference on Intelligent Information Processing, Security and Advanced Communication, Batna, Algeria, 2015: Article No.85. doi: 10.1145/2816839.2816854.

    7. [7]

      CHENAIT M, ZEBBANE B, and BADACHE N. A new k-coverage model to determine redundant sensors in wireless sensor networks[C]. 2018 International Conference on Smart Communications in Network Technologies (SaCoNeT), El Oued, Algeria, 2018: 149–154.

    8. [8]

      刘浩然, 赵赫瑶, 邓玉静, 等. 基于非合作博弈的无线传感器网络覆盖控制算法[J]. 通信学报, 2019, 40(1): 71–78. doi: 10.11959/j.issn.1000-436x.2019006
      LIU Haoran, ZHAO Heyao, DENG Yujing, et al. Coverage control algorithm for wireless sensor networks based on non-cooperative game[J]. Journal on Communications, 2019, 40(1): 71–78. doi: 10.11959/j.issn.1000-436x.2019006

    9. [9]

      贾明伟, 吴敏, 沙超, 等. 节点相邻关系的传感网覆盖优化方法[J]. 电子测量与仪器学报, 2015, 29(11): 1574–1583. doi: 10.13382/j.jemi.2015.11.002
      JIA Mingwei, WU Min, SHA Chao, et al. Coverage optimization algorithm based on adjacent neighbors for sensor networks[J]. Journal of Electronic Measurement and Instrumentation, 2015, 29(11): 1574–1583. doi: 10.13382/j.jemi.2015.11.002

    10. [10]

      孙力娟, 魏静, 郭剑, 等. 面向异构无线传感器网络的节点调度算法[J]. 电子学报, 2014, 42(10): 1907–1912. doi: 10.3969/j.issn.0372-2112.2014.10.006
      SUN Lijuan, WEI Jing, GUO Jian, et al. Node scheduling algorithm for heterogeneous wireless sensor networks[J]. Acta Electronica Sinica, 2014, 42(10): 1907–1912. doi: 10.3969/j.issn.0372-2112.2014.10.006

    11. [11]

      高洁, 吴延红, 白建侠, 等. 无线传感器网络最小覆盖能量优化算法[J]. 传感技术学报, 2016, 29(9): 1435–1440. doi: 10.3969/j.issn.1004-1699.2016.09.024
      GAO Jie, WU Yanhong, BAI Jianxia, et al. The minimum coverage energy optimization algorithms in wireless sensor network[J]. Chinese Journal of Sensors and Actuators, 2016, 29(9): 1435–1440. doi: 10.3969/j.issn.1004-1699.2016.09.024

    12. [12]

      权恩猛, 吴斌. 基于Delaunay三角剖分的有向传感器网络覆盖增强算法[J]. 计算机应用研究, 2018, 35(8): 2447–2449. doi: 10.3969/j.issn.1001-3695.2018.08.052
      QUAN Enmeng and WU Bin. Coverage enhancement algorithm based on delaunay triangulation for directional sensor networks[J]. Application Research of Computers, 2018, 35(8): 2447–2449. doi: 10.3969/j.issn.1001-3695.2018.08.052

    13. [13]

      杜晓玉, 孙力娟, 郭剑, 等. 异构无线传感器网络覆盖优化算法[J]. 电子与信息学报, 2014, 36(3): 696–702. doi: 10.3724/SP.J.1146.2013.00730
      DU Xiaoyu, SUN Lijuan, GUO Jian, et al. Coverage optimization algorithm for heterogeneous WSNs[J]. Journal of Electronics &Information Technology, 2014, 36(3): 696–702. doi: 10.3724/SP.J.1146.2013.00730

    14. [14]

      刁鹏飞, 王艳娇. 基于节点休眠的水下无线传感器网络覆盖保持分簇算法[J]. 电子与信息学报, 2018, 40(5): 1101–1107. doi: 10.11999/JEIT170787
      DIAO Pengfei and WANG Yanjiao. Coverage-preserving clustering algorithm for underwater sensor networks based on the sleeping mechanism[J]. Journal of Electronics &Information Technology, 2018, 40(5): 1101–1107. doi: 10.11999/JEIT170787

    15. [15]

      LI Wei and ZHANG Wei. Coverage hole and boundary nodes detection in wireless sensor networks[J]. Journal of Network and Computer Applications, 2015, 48: 35–48. doi: 10.1016/j.jnca.2014.10.011.

    1. [1]

      蒋俊正, 李杨剑, 赵海兵, 欧阳缮. 一种大规模传感器网络节点分布式定位算法. 电子与信息学报, 2019, 41(0): 1-7.

    2. [2]

      徐公国, 单甘霖, 段修生, 乔成林, 王浩天. 基于马尔科夫决策过程的多传感器协同检测与跟踪调度方法. 电子与信息学报, 2019, 41(9): 2201-2208.

    3. [3]

      王练, 张贺, 张昭, 张勋杨. 基于自适应随机线性网络编码的优先级调度方案. 电子与信息学报, 2019, 41(8): 1861-1868.

    4. [4]

      季新生, 徐水灵, 刘文彦, 仝青, 李凌书. 一种面向安全的虚拟网络功能动态异构调度方法. 电子与信息学报, 2019, 41(10): 2435-2441.

    5. [5]

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

    6. [6]

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

    7. [7]

      黄静琪, 胡琛, 孙山鹏, 高翔, 何兵. 一种基于异步传感器网络的空间目标分布式跟踪方法. 电子与信息学报, 2019, 41(0): 1-8.

    8. [8]

      王辰硕, 何光强, 李玥琪, 赵荣建, 陈贤祥, 杜利东, 赵湛, 方震. 基于涡轮式气体流量传感器的用力呼气容量计算方法. 电子与信息学报, 2019, 41(10): 2396-2401.

    9. [9]

      刘焕淋, 方菲, 陈勇, 向敏, 马跃. 基于无色无向无冲突可重构光分插复用器节点的全光IP组播能效调度. 电子与信息学报, 2019, 41(0): 1-7.

    10. [10]

      张鹤玖, 余宁梅, 吕楠, 刘尕. 一种用于时延积分CMOS图像传感器的10 bit全差分双斜坡模数转换器. 电子与信息学报, 2019, 41(6): 1466-1471.

    11. [11]

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

    12. [12]

      徐少平, 张贵珍, 李崇禧, 刘婷云, 唐祎玲. 基于深度置信网络的随机脉冲噪声快速检测算法. 电子与信息学报, 2019, 41(5): 1130-1136.

    13. [13]

      张瑞, 占友, 钱权. 一种新的基于虚拟队列的无线多播网络编码调度策略. 电子与信息学报, 2019, 41(0): 1-8.

    14. [14]

      张达敏, 张绘娟, 闫威, 陈忠云, 辛梓芸. 异构网络中基于能效优化的D2D资源分配机制. 电子与信息学报, 2019, 41(0): 1-9.

    15. [15]

      马彬, 李尚儒, 谢显中. 异构无线网络中基于人工神经网络的自适应垂直切换算法. 电子与信息学报, 2019, 41(5): 1210-1216.

    16. [16]

      张杰鑫, 庞建民, 张铮, 邰铭, 刘浩. 基于非相似余度架构的网络空间安全系统异构性量化方法. 电子与信息学报, 2019, 41(7): 1594-1600.

    17. [17]

      马彬, 李尚儒, 谢显中. 异构无线网络中基于模糊逻辑的分级垂直切换算法. 电子与信息学报, 2019, 41(0): 1-8.

    18. [18]

      金梁, 蔡奥林, 黄开枝, 钟州, 楼洋明. 基于多随机信号流的密钥生成方案. 电子与信息学报, 2019, 41(6): 1405-1412.

    19. [19]

      郝本建, 王林林, 李赞, 赵越. 面向TDOA被动定位的定位节点选择方法. 电子与信息学报, 2019, 41(2): 462-468.

    20. [20]

      杨善超, 田康生, 刘仁争, 郑玉军. 基于价值优化的相控阵雷达任务调度算法. 电子与信息学报, 2019, 41(0): 1-7.

  • 图 1  节点${s_i}$的有效约束圆弧${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}$

    图 2  节点${s_i}$感知半径${r_i}$调整图

    图 3  节点感知重叠面积求解

    图 4  黑色节点的标识与计算

    图 5  不满足圆心$k$覆盖的节点约束圆弧图

    图 6  目标区域调整效果对比

    图 7  覆盖冗余度随节点个数和半径比变化情况

    图 8  多级异构网络中$\Delta F\;$的变化

    图 9  二级异构网络中$\Delta F\;$的变化

    图 10  同构网络中$\Delta F\;$的变化

    表 1  半径调整算法步骤

     半径调整算法(${T^i},{r_i}$)
     (1) $r_{\rm c}^i = \varnothing $
     (2) for $p = 1:P$
     (3)   calculate the radius $r_{{\rm{cp}}}^i$ of ${T_p}^i$//计算空外接圆半径
     (4)    $r_{\rm c}^i = r_{\rm c}^i \cup r_{ {\rm{cp} } }^i$
     (5) end for
     (6   ${r_i} = \min ({r_i},\max \left( {r_{\rm c}^i} \right))$//若$\max \left( {r_{\rm c}^i} \right) > {r_i}$,则保留原${r_i}$
     (7) return (${r_i}$)
    下载: 导出CSV

    表 2  NSSH算法步骤

     NSSH (${T^i}$,${r_i}$,${\rm{N}}{{\rm{e}}_i}$,${\theta _{{\rm{th}}}}$,${\left| {{\rm{arc}}} \right|_{{\rm{th}}}}$,$k$)
     (1) 初始化:${\rm{s}}{{\rm{t}}_i} = 1$, ${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}=\varnothing$
     (2) ${r_i}$=半径调整算法(${T^i},{r_i}$)
     (3) for $q = 1:Q$
     (4)  ${\rm{if}}({\theta _{i,jq}} > {\theta _{{\rm{th}}}})$) //基于定义5和式(1)判定灰色节点
     (5)   ${\rm{s}}{{\rm{t}}_i} = 0$
     (6)  end if
     (7)  ${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}={\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}} \cup {\stackrel \frown {{\rm{ar}}{{\rm{c}}_{i\_jq}}}}$ //计算有效约束圆弧
     (8) end for
     (9) calculate $\left| {{\rm{ar}}{{\rm{c}}_i}} \right|$ ${k_i}$ //基于式(2)—式(4)计算有效约束圆弧度
    数,统计${s_i}$的覆盖度${k_i}$
     (10) if ($\left| {{\rm{ar}}{{\rm{c}}_i}} \right| \ge {\left| {{\rm{arc}}} \right|_{{\rm{th}}}}{\rm{\& \& }}{k_i} \ge k$)//基于定义6判定黑色节点
     (11)  ${\rm{s}}{{\rm{t}}_i} = 0$
     (12) end if
     (13) return (${\rm{s}}{{\rm{t}}_i}$)
    下载: 导出CSV

    表 3  5种算法参数

    算法节点数目
    $N = {\rm{100}}$, $N = {\rm{150}}$$N = {\rm{200}}$, $N = {\rm{250}}$$N = {\rm{300}}$, $N = {\rm{350}}$$N = {\rm{400}}$, $N = {\rm{450}}$$N = {\rm{500}}$
    NSSH${\theta _{{\rm{th}}}} = 0.82$ ${\left| {{\rm{arc}}} \right|_{{\rm{th}}}} = 1.96{\text{π}} $ $k{\rm{ = 2}}$
    GGA$\mu {\rm{ = 0}}{\rm{.9}}$
    MCLC$\Delta c < 0.05$
    COAN${r_{{\rm{thr}}}} = 4.4$
    ${\eta _{{\rm{thr}}}} = 1.87{\text{π}} $
    ${m_{{\rm{thr}}}} = 11$
    $k = 1$
    ${r_{{\rm{thr}}}} = 4.6$
    ${\eta _{{\rm{thr}}}} = 1.9{\text{π}} $
    ${m_{{\rm{thr}}}} = 12$
    $k = 1$
    ${r_{{\rm{thr}}}} = 4.8$
    ${\eta _{{\rm{thr}}}} = 1.93{\text{π}}$
    ${m_{t{\rm{hr}}}} = 13$
    $k = 1$
    ${r_{{\rm{thr}}}} = 5.2$
    ${\eta _{{\rm{thr}}}} = 1.96{\text{π}} $
    ${m_{{\rm{thr}}}} = 13$
    $k = 1$
    ${r_{{\rm{thr}}}} = 5.4$
    ${\eta _{{\rm{thr}}}} = 1.98{\text{π}} $
    ${m_{{\rm{thr}}}} = 15$
    $k = 1$
    NDBS${k_2}({r_1}/{r_2}) = 4$
    ${k_2}({r_2}/{r_1}) = 7$
    ${k_3}({r_1}/{r_2}) = 7$
    ${k_3}({r_2}/{r_1}) = 16$
    ${k_2}({r_1}/{r_2}) = 4$
    ${k_2}({r_2}/{r_1}) = 8$
    ${k_3}({r_1}/{r_2}) = 8$
    ${k_3}({r_2}/{r_1}) = 16$
    ${k_2}({r_1}/{r_2}) = 4$
    ${k_2}({r_2}/{r_1}) = 7$
    ${k_3}({r_1}/{r_2}) = 8$
    ${k_3}({r_2}/{r_1}){\rm{ = 15}}$
    ${k_2}({r_1}/{r_2}) = 3$
    ${k_2}({r_2}/{r_1}) = 6$
    ${k_3}({r_1}/{r_2}) = 7$
    ${k_3}({r_2}/{r_1}) = 14$
    ${k_2}({r_1}/{r_2}) = 3$
    ${k_2}({r_2}/{r_1}) = 6$
    ${k_3}({r_1}/{r_2}) = 6$
    ${k_3}({r_2}/{r_1}) = 13$
    注:表中参数$\Delta c$代表MCLC算法覆盖子集的约束条件,${r_{{\rm{thr}}}}$, ${\eta _{{\rm{thr}}}}$, ${m_{{\rm{thr}}}}$仅针对COAN算法,${k_2}({r_1}/{r_2})$, ${k_2}({r_2}/{r_1})$, ${k_3}({r_1}/{r_2})$, ${k_3}({r_2}/{r_1})$仅针对NDBS算法,具体参数解释可查阅文献[8,9]。
    下载: 导出CSV
  • 加载中
图(10)表(3)
计量
  • PDF下载量:  25
  • 文章访问数:  468
  • HTML全文浏览量:  267
文章相关
  • 通讯作者:  秦宁宁, ningning801108@163.com
  • 收稿日期:  2019-02-17
  • 录用日期:  2019-06-09
  • 网络出版日期:  2019-06-14
  • 刊出日期:  2019-10-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章