面向数量最少化的双层WSN中继节点部署算法

苗春雨; 陈丽娜; 戴国勇; 杨帆; 陈庆章

doi:10.11959/j.issn.1000-436x.2016081

您当前的位置：

首页 >

文章列表页 >

面向数量最少化的双层WSN中继节点部署算法

学术论文 | 更新时间：2024-06-05

- 面向数量最少化的双层WSN中继节点部署算法
- Minimum number oriented relay node deployment algorithm in two-tiered WSN
- 通信学报 2016年37卷第4期页码：139-148
- 作者机构：
  
  1. 浙江师范大学数理与信息工程学院，浙江金华321004
  2. 浙江工业大学计算机科学与技术学院，浙江杭州310023
- 作者简介：
  
  [ "苗春雨（1978-），男，吉林四平人，浙江工业大学博士生，浙江师范大学副教授，主要研究方向为无线网络、无线传感器网络、网络安全等。" ]
  [ "陈丽娜（1978-），女，吉林长春人，博士，浙江师范大学副教授，主要研究方向为室内定位、认知无线电等。" ]
  [ "戴国勇（1983-），男，浙江杭州人，浙江工业大学博士生，主要研究方向为无线传感器网络。" ]
  [ "杨帆（1987-），女，浙江杭州人，浙江工业大学硕士生，主要研究方向为无线传感器网络。" ]
  [ "陈庆章（1955-），男，河南郑州人，博士，浙江工业大学教授、博士生导师，主要研究方向为无线传感器网络、分布式处理与协同计算等。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61379023);国家自然科学基金资助项目(61502431);浙江省计算机科学与技术重中之重学科（浙江师范大学）基金资助项目(ZC323014074);浙江省科技厅公益性技术应用研究计划基金资助项目(2015C33060)
- DOI：10.11959/j.issn.1000-436x.2016081
  中图分类号： TP393.17
- 网络出版日期：2016-04，
  
  纸质出版日期：2016-04-25
- 稿件说明：
移动端阅览
苗春雨, 陈丽娜, 戴国勇, 等. 面向数量最少化的双层WSN中继节点部署算法[J]. 通信学报, 2016,37(4):139-148.

Chun-yu MIAO, Li-na CHEN, Guo-yong DAI, et al. Minimum number oriented relay node deployment algorithm in two-tiered WSN[J]. Journal of communications, 2016, 37(4): 139-148.
苗春雨, 陈丽娜, 戴国勇, 等. 面向数量最少化的双层WSN中继节点部署算法[J]. 通信学报, 2016,37(4):139-148. DOI： 10.11959/j.issn.1000-436x.2016081.

Chun-yu MIAO, Li-na CHEN, Guo-yong DAI, et al. Minimum number oriented relay node deployment algorithm in two-tiered WSN[J]. Journal of communications, 2016, 37(4): 139-148. DOI： 10.11959/j.issn.1000-436x.2016081.

摘要

提出2种算法，目标是在监测区域部署中继节点，以便所有的传感节点都能和至少一个中继节点进行通信，同时保证中继节点数目最小化。整数线性规划最优解算法是对已选择出的 CRegions 通过数学上的整数线性规划的方法找到部署中继节点的最佳区域；传感网络规模较大时，提出启发式算法，将每一次排序后含传感节点个数最多的集合作为部署区域，经过多次循环排序后近似的找到部署中继节点的最佳位置。最后通过与2个同类算法在相同参数环境下进行仿真实验，比较仿真结果证明整数线性规划最优解算法及启发式算法在覆盖所有传感节点的前提下，部署中继节点最小化的性能较好，并且其部署时间也在可以接受的范围之内。

Abstract

Aiming at minimizing the number of relay nodes distributed in the sensing area while keeping the feasible communication with at least one relay node for every sensor node

two algorithms (i.e. the integral linear programming optimal algorithm and the heuristic algorithm) were proposed. First

the integral linear programming optimal algorithm was designed to find the best region of deploying rela nodes within candidate regions through integer linear program-ming. In the large-scale wireless sensor network

the heuristic algorithm was proposed that found the best deployment re-gion through iteratively updating the deployment area luding the most relay nodes. Finally

simulation results show that the two proposed algorithms can minimize the number of relay nodes needed with the guarantee of serving all sensor nodes.

关键词

Keywords

references

ILIEV N , PAPROTNY I . Review and comparison of spatial lization methods for low power wireless sensor networks [J ] . IEEE Sensors Journal , 2015 , 15 ( 10 ): 5971 - 5987 .

KAZMI A H , O'GRADY M J , DELANEY D T , et al . A review of wireless-sensor-network-enabled building energy management systems [J ] . ACM Transactions on Sensor Networks (TOSN), 2014 , 10 ( 4 ): 66 .

BHATTACHARYA A , KUMAR A . A shortest path tree based algorithm for relay placement in a wireless sensor network and its perfor-mance analysis [J ] . Computer Networks , 2014 , 71 : 48 - 62 .

FATHI M , MAIHAMI V . Operational state scheduling of re y nodes in two-tiered wireless sensor networks [J ] . Systems Journal, IEEE , 2015 , 9 ( 3 ): 686 - 693 .

ZHANG W , XUE G , MISRA S . Fault-tolerant relay node placement in wireless sensor networks: problems and algorithm [C ] // Infocom-2007 . c 2007 : 1649 - 1657 .

HAO B , TANG J , XUE G L . Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation [C ] // HPSR'04 . c 2004 : 246 - 250 .

MISRA S , HONG S D , XUE G L , et al . Constrained relay node placement in wireless sensor networks: formulation and approximations [J ] . IEEE/ACM Transaction on Networking , 2010 , 18 ( 2 ): 434 - 447 .

CHANG H Y , HUANG Y H , LIN T L . A novel relay placement algorithm based on puzzle games for indoor wireless sensor networks [C ] // Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2014 Tenth International Conference on. IEEE , c 2014 : 682 - 685 .

NIGAM A , AGARWAL Y K . Optimal relay node placement in lay constrained wireless sensor network design [J ] . European Journal of Operational Research , 2014 , 233 ( 1 ): 220 - 233 .

JENNIFER W , ROOZBEH L J , MIODRAG P . Gateway placement for latency and energy efficient data aggregation [C ] // 29th Annual IEEE International Conference on Local Computer Networks (LCN'04). c 2004 : 490 - 497 .

YANG D J , MISRA S , FANG X . Two-tiered constrained relay node placement in WSNs: efficient approximations [C ] // SECON'10.Boston, United States , c 2010 : 1 - 9 .

ZHANG W , XUE G , MISRA S . Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms [C ] // Proc IEEE INFOCOM . c 2007 : 1649 - 1657 .

NITESH K , JANA P K . Relay node placement algorithm in wireless sensor network [C ] // Advance Computing Conference (IACC), 2014 IEEE International . c 2014 : 220 - 225 .

CHEN G , CUI S . Relay node placement in two-tiered wireless sensor networks with base stations [J ] . Journal of Combinatorial Optimization , 2013 , 26 ( 3 ): 499 - 508 .

FAN T , TENG G , HUO L . A pre-determined nodes deployment strategy of two-tiered wireless sensor networks based on minimizing cost [J ] . International Journal of Wireless Information Networks , 2014 , 21 ( 2 ): 114 - 124 .

LLOYD E L , XUE G . Relay node placement in wireless sensor net-works [J ] . IEEE Transactions on Computers , 2007 , 56 ( 1 ): 134 - 138 .

YANG D , MISRA S , FANG X , et al . Two-tiered constrained relay node placement in wireless sensor networks: computational complexi-ty and efficient approximations [J ] . IEEE Transactions on Mobile Computing , 2012 , 11 ( 8 ): 1399 - 1411 .

ZAFAR B , MIR Z H , SHAMS S M . On improved relay nodes place-ment in two-tiered wireless sensor networks [C ] // IEEE MILCOM 2009. Boston, United States . c 2009 : 1 - 7 .

TANG J , HAO B , ARUNABHA S . Relay node placement in large scale wireless sensor networks [J ] . Computer Communications , 2006 , 29 ( 4 ): 490 - 501 .

CHEN Z K , CHEN C C . Relay node placement in wireless sensor network [C ] // The Fourth Workshop on Wireless Ad Hoc and Sensor Networks . c 2008 : 544 - 553 .

曾斌，魏军，姚路．传感器网络中继节点扩展部署的优化算法研究 [J ] ．通信学报， 2012 , 33 ( 4 ): 152 - 162 .

ZENG B , WEI J , YAO L . Optimal scalable redeployment algorithm of relay nodes in wireless sensor networks [J ] . Journal on Communications , 2012 , 33 ( 4 ): 152 - 162 .

浏览量

690

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

干扰门限与回程容量限制下UDN的能效与谱效联合优化算法

虚拟网络可生存的启发式可靠映射算法

传感器网络中继节点扩展部署的优化算法研究