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

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

通信学报 ›› 2016, Vol. 37 ›› Issue (4): 139-148.doi: 10.11959/j.issn.1000-436x.2016081

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

苗春雨^1,²,陈丽娜¹,戴国勇²,杨帆²,陈庆章²

¹ 浙江师范大学数理与信息工程学院，浙江金华321004
² 浙江工业大学计算机科学与技术学院，浙江杭州310023

出版日期:2016-04-25 发布日期:2016-04-26
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;浙江省计算机科学与技术重中之重学科（浙江师范大学）基金资助项目;浙江省科技厅公益性技术应用研究计划基金资助项目

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

Chun-yu MIAO^1,²,Li-na CHEN¹,Guo-yong DAI²,Fan YANG²,Qing-zhang CHEN²

¹ College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, China
² College of Computer,Zhejiang University of Technology, Hangzhou 310023, China

Online:2016-04-25 Published:2016-04-26
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;Opening Fund of Zhejiang Provincial Top Key Discipline of Computer Science and echnology at Zhejiang Normal University;Zhejiang Province Science Technology Department Public Welfare Technology Application Research Project

摘要/Abstract

摘要：

提出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.

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

苗春雨,陈丽娜,戴国勇,杨帆,陈庆章. 面向数量最少化的双层WSN中继节点部署算法[J]. 通信学报, 2016, 37(4): 139-148.

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.

图/表 9

图1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献 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.

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

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 21

相关文章 13

Metrics

推荐阅读 0

[1]	刘帅, 关杰, 胡斌, 马宿东. 基于MILP的轻量级密码算法ACE的差分分析[J]. 通信学报, 2023, 44(1): 39-48.
[2]	聂宏蕊, 李绍胜, 刘勇. 时间敏感网络中基于IEEE 802.1Qch标准的优化调度机制[J]. 通信学报, 2022, 43(9): 12-26.
[3]	陈晶,祁子怡. 基于时序关系的社交网络影响最大化算法研究[J]. 通信学报, 2020, 41(10): 211-221.
[4]	吴宣利,陈旭. 干扰门限与回程容量限制下UDN的能效与谱效联合优化算法[J]. 通信学报, 2019, 40(12): 86-97.
[5]	彭颖,王淖,王高才. 移动社会网络中基于社区的最优能效路由策略研究[J]. 通信学报, 2017, 38(5): 128-144.
[6]	朱强,王慧强,马春光,冯光升,吕宏武. 虚拟网络可生存的启发式可靠映射算法[J]. 通信学报, 2015, 36(7): 109-119.
[7]	曾斌,魏军,姚路. 传感器网络中继节点扩展部署的优化算法研究[J]. 通信学报, 2012, 33(4): 152-162.
[8]	卢为党,吴宣利,沙学军,张乃通. OFDM固定中继系统中单中继多源用户资源分配方案[J]. 通信学报, 2011, 32(9): 26-32.
[9]	唐伟,郭伟. 多基站无线传感器网络中能量高效的基站位置优选算法[J]. 通信学报, 2010, 31(11): 65-72.
[10]	郑国强,李建东,李红艳,周志立. 多跳无线传感器网络的高效中继节点快速选择算法[J]. 通信学报, 2010, 31(11): 158-170.
[11]	戴毅,曹健. 基于模糊控制的启发式工作流引擎负载均衡策略[J]. 通信学报, 2006, 27(11): 84-89.
[12]	付明磊,乐孜纯,陆敏. 基于权重均衡的光网络逻辑拓扑优化算法[J]. 通信学报, 2006, 27(10): 38-43.
[13]	吴家皋,杨音颖,陈益新,叶晓国. 支持延时约束的覆盖多播路由协议的研究[J]. 通信学报, 2005, 26(9): 13-20.