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

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

Abstract

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.

Key words: relay nodes, deployment algorithm, integer linear programming, heur ic algorithm, node coverage

Chun-yu MIAO,Li-na CHEN,Guo-yong DAI,Fan YANG,Qing-zhang CHEN. Minimum number oriented relay node deployment algorithm in two-tiered WSN[J]. Journal on Communications, 2016, 37(4): 139-148.

Figures/Tables 9

References 21

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	ZHANG W , XUE G , MISRA S . Fault-tolerant relay node placement in wireless sensor networks: problems and algorithm[C]// Infocom-2007. c2007:1649-1657.
[6]	HAO B , TANG J , XUE G L . Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation[C]// HPSR'04. c2004:246-250.
[7]	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.
[8]	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, c2014:682-685.
[9]	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.
[10]	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). c2004:490-497.
[11]	YANG D J , MISRA S , FANG X . Two-tiered constrained relay node placement in WSNs: efficient approximations[C]// SECON'10.Boston, United States, c2010:1-9.
[12]	ZHANG W , XUE G , MISRA S . Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms[C]// Proc IEEE INFOCOM. c2007:1649-1657.
[13]	NITESH K , JANA P K . Relay node placement algorithm in wireless sensor network[C]// Advance Computing Conference (IACC), 2014 IEEE International. c2014:220-225.
[14]	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.
[15]	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.
[16]	LLOYD E L , XUE G . Relay node placement in wireless sensor net-works[J]. IEEE Transactions on Computers, 2007,56(1):134-138.
[17]	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.
[18]	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. c2009:1-7.
[19]	TANG J , HAO B , ARUNABHA S . Relay node placement in large scale wireless sensor networks[J]. Computer Communications, 2006,29(4):490-501.
[20]	CHEN Z K , CHEN C C . Relay node placement in wireless sensor network[C]// The Fourth Workshop on Wireless Ad Hoc and Sensor Networks. c2008:544-553.
[21]	曾斌，魏军，姚路．传感器网络中继节点扩展部署的优化算法研究[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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 21

Related Articles 5

Metrics

Recommended 0

[1]	Hongrui NIE, Shaosheng LI, Yong LIU. Optimized scheduling mechanism based on IEEE 802.1Qch standard in time-sensitive networking [J]. Journal on Communications, 2022, 43(9): 12-26.
[2]	Xuanli WU,Xu CHEN. Joint energy efficiency and spectral efficiency optimization algorithm for UDN under the restriction of interference threshold and backhaul capacity [J]. Journal on Communications, 2019, 40(12): 86-97.
[3]	Qiang ZHU,Hui-qiang WANG,Chun-guang MA,Guang-sheng FENG,Hong-wu LV. Reliable heuristic mapping method for survivable virtual network [J]. Journal on Communications, 2015, 36(7): 109-119.
[4]	Bin ZENG,Jun WEI,Lu YAO. Optimal scalable redeployment algorithm of relay nodes in wireless sensor networks [J]. Journal on Communications, 2012, 33(4): 152-162.
[5]	Wei TANG,Wei GUO. Energy efficient optimal sink position selection algorithm for multi-sink wireless sensor networks [J]. Journal on Communications, 2010, 31(11): 65-72.