Minimum number oriented relay node deployment algorithm in two-tiered WSN

Chun-yu MIAO; Li-na CHEN; Guo-yong DAI; Fan YANG; Qing-zhang CHEN

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

您当前的位置：

首页 >

文章列表页 >

Minimum number oriented relay node deployment algorithm in two-tiered WSN

academic paper | 更新时间：2024-06-05

- Minimum number oriented relay node deployment algorithm in two-tiered WSN
- Journal of Communications Vol. 37, Issue 4, Pages: 139-148(2016)
- 作者机构：
  
  1. 浙江师范大学数理与信息工程学院，浙江金华321004
  2. 浙江工业大学计算机科学与技术学院，浙江杭州310023
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61379023);The National Natural Science Foundation of China(61502431);Opening Fund of Zhejiang Provincial Top Key Discipline of Computer Science and echnology at Zhejiang Normal University(ZC323014074);Zhejiang Province Science Technology Department Public Welfare Technology Application Research Project(2015C33060)
- DOI：10.11959/j.issn.1000-436x.2016081
  CLC： TP393.17
- Online First：2016-04，
  
  Published：25 April 2016
- 稿件说明：
移动端阅览
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：

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 .

Views

1874

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Joint energy efficiency and spectral efficiency optimization algorithm for UDN under the restriction of interference threshold and backhaul capacity

Reliable heuristic mapping method for survivable virtual network

Optimal scalable redeployment algorithm of relay nodes in wireless sensor networks

Related Author

Xuanli WU

Xu CHEN

Qiang ZHU

Hui-qiang WANG

Chun-guang MA

Guang-sheng FENG

Hong-wu LV

Bin ZENG

Related Institution

Communication Research Center,Harbin Institute of Technology

College of Computer Science and Technology, Harbin Engineering University

Research Center of Information Management,Naval University of Engineering

AI问答

⁰