无线传感器网络RaSMaLai算法的改进

doi:10.11772/j.issn.1001-9081.2015.09.2436

计算机应用 ›› 2015, Vol. 35 ›› Issue (9): 2436-2439.DOI: 10.11772/j.issn.1001-9081.2015.09.2436

无线传感器网络RaSMaLai算法的改进

孙学梅, 张心中, 王亚宁, 张天元

天津工业大学计算机科学与软件学院, 天津 300000

收稿日期:2015-04-23 修回日期:2015-06-04 出版日期:2015-09-10 发布日期:2015-09-17
通讯作者: 张心中(1988-),男,山东济宁人,硕士研究生,主要研究方向:传感器网络,1446162932@qq.com
作者简介:孙学梅(1971-),女,天津人,副教授,博士,主要研究方向:传感器网络;王亚宁(1990-),男,山东济宁人,硕士研究生,主要研究方向:虚拟机整合;张天元(1988-),男,山西朔州人,硕士研究生,主要研究方向:虚拟机调度。

Improvement on RaSMaLai in wireless sensor networks

SUN Xuemei, ZHANG Xinzhong, WANG Yaning, ZHANG Tianyuan

School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300000, China

Received:2015-04-23 Revised:2015-06-04 Online:2015-09-10 Published:2015-09-17

摘要/Abstract

摘要： 针对RaSMaLai算法有可能进入无效循环和无效等待状态的问题,对RaSMaLai进行了两点改进并提出了一种新的随机转换算法NRaSMaLai:改进一在算法初始化过程中遍历树中节点进行初始化检查,防止树进入无效等待状态;改进二在更新树操作过程中对树中最大负载节点及其所有子孙节点时进行状态检测,防止树进入无效循环状态。NRaSMaLai通过增大最小负载节点及其子孙节点的负载使树平衡。仿真实验表明,使用改进一、二的算法能使树达到平衡状态或更接近预设的平衡状态。当sink节点位于区域中心时,NRaSMaLai使树平衡时所需的迭代步数减小为原来的1/5并很少出现振荡,对使数据收集树快速收敛并延长网络寿命具有重要意义。

关键词: 无线传感器网络, 负载均衡, 数据收集树, 随机算法, 网络寿命

Abstract: Two improvement methods were presented to avoid ineffective circulation and invalid waiting state problems when running algorithm Randomized Switching for Maximizing Lifetime (RaSMaLai) and then a new random switching algorithm New Randomized Switching for Maximizing Lifetime (NRaSMaLai) was put forward: the first improvement was to conduct the initialized inspection in the process of traversing tree nodes in order to prevent the tree from entering into invalid waiting state; the second improvement was to do the state inspection for the maximum load node and all its descendant nodes in the operation process of updating the tree to avoid ineffective circulation. The tree balance was achieved by increasing the load of the minimum node and its descendant nodes with NRaSMaLai. The simulation experiment shows that these two methods can make the tree achieve the balance state or at least get closer to the presupposed state. When the sink node was located in the regional center, the iterative steps which make the tree balanced can be reduced to 1/5 of the original by NRaSMaLai and also it appears little oscillation. This is significant for the data collection tree's rapid convergence and the extension of the network's lifetime.

Key words: Wireless Sensor Network (WSN), load balance, data collection tree, randomized algorithm, network lifetime

中图分类号:

TP393.03

孙学梅, 张心中, 王亚宁, 张天元. 无线传感器网络RaSMaLai算法的改进[J]. 计算机应用, 2015, 35(9): 2436-2439.

SUN Xuemei, ZHANG Xinzhong, WANG Yaning, ZHANG Tianyuan. Improvement on RaSMaLai in wireless sensor networks[J]. Journal of Computer Applications, 2015, 35(9): 2436-2439.

参考文献

[1] SUN L, LI J, CHEN Y, et al. Wireless sensor network [M]. Beijing: Tsinghua University Press, 2005:135-155.(孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005:135-155.)
[2] IMON S K A, KHAN A, DI FRANCESCO M, et al. Energy-efficient randomized switching for maximizing lifetime in tree-based wireless sensor networks [J]. IEEE/ACM Transactions on Networking, 2014,PP(99):1.
[3] LUO D, ZHU X, WU X, et al. Maximizing lifetime for the shortest path aggregation tree in wireless sensor networks [C]//Proceedings of the 2011 International Conference on Computer Communications. Piscataway: IEEE, 2011:1566-1574.
[4] WU Y, FAHMY S, SHROFF N B. On the construction of a maximum-lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm [C]//Proceedings of the 2008 International Conference on Computer Communications. Piscataway: IEEE, 2008:356-360.
[5] XUE Y, CUI Y, NAHRSTEDT K. Maximizing lifetime for data aggregation in wireless sensor networks [J]. Mobile Networks and Applications, 2005,10(6):853-864.
[6] XU X, LI X, MAO X, et al. A delay-efficient algorithm for data aggregation in multihop wireless sensor networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2011,22(1):163-175.
[7] DAI H, HAN R. A node-centric load balancing algorithm for wireless sensor networks [C]//Proceedings of the 2003 Global Telecommunications Conference. Piscataway: IEEE. 2003:548-552.
[8] DEHGHANI A, JAMSHIDI K, MIRSHAMS S, et al. A routing metric for load balancing considering energy and delay constraints in wireless sensor network[C]//Proceedings of the 2008 International Symposium on Telecommunications. Piscataway:IEEE, 2008:745-750.
[9] TOUMPIS S, GITZENIS S. Load balancing in wireless sensor networks using Kirchhoff's voltage law [C]//Proceedings of the 2009 International Conference on Computer Communications. Piscataway: IEEE, 2009:1656-1664.
[10] LIANG J, WANG J, CAO J, et al. An efficient algorithm for constructing maximum lifetime tree for data gathering without aggregation in wireless sensor networks [C]//Proceedings of the 2010 International Conference on Computer Communications. Piscataway: IEEE, 2010:1-5.
[11] BURAOHAIN C, AGRAWAL D, SURI S. Power aware routing for sensor databases [C]//Proceedings of the 2005 International Conference on Computer Communications. Piscataway: IEEE, 2005:1747-1757.
[12] WANG Y, WANG Y, TAN H, et al. Maximizing network lifetime online by localized probabilistic load balancing [C]//Proceedings of the 10th International Conference on Ad-Hoc, Mobile, and Wireless Networks. Berlin: Springer, 2011:332-345.

[1]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[2]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[3]	孙环, 陈宏滨. 基于萤火虫算法的无线传感器网络节点重部署策略[J]. 计算机应用, 2021, 41(2): 492-497.
[4]	胡润彦, 李翠然. 基于模糊控制的自供能无线传感器网络分簇算法[J]. 计算机应用, 2020, 40(9): 2691-2697.
[5]	韩雨涝, 房鼎益. 基于链路交点相对位置信息的轻量级覆盖空洞检测算法[J]. 计算机应用, 2020, 40(9): 2698-2705.
[6]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.
[7]	卢光跃, 周亮, 吕少卿, 施聪, 苏可可. 基于图信号处理的无线传感器网络异常节点检测算法[J]. 计算机应用, 2020, 40(3): 783-787.
[8]	李翠, 陈庆奎. 基于DPDK并行通信的动态监控模型[J]. 计算机应用, 2020, 40(2): 335-341.
[9]	任秀丽, 陈洋. 无线传感网中数据传输延时优化的路由协议[J]. 计算机应用, 2020, 40(1): 196-201.
[10]	吴三柱, 李鹏, 吴三斌. 移动无线传感器网络中抑制病毒传播模型[J]. 计算机应用, 2020, 40(1): 129-135.
[11]	董发志, 丁洪伟, 杨志军, 熊成彪, 张颖婕. 基于遗传算法和模糊C均值聚类的WSN分簇路由算法[J]. 计算机应用, 2019, 39(8): 2359-2365.
[12]	何庆, 徐钦帅, 魏康园. 基于改进正弦余弦算法的无线传感器节点部署优化[J]. 计算机应用, 2019, 39(7): 2035-2043.
[13]	李祝红, 赵灿明, 闫龙, 张信明. 智能电网中电力线通信网络负载均衡的机会路由协议[J]. 计算机应用, 2019, 39(3): 812-816.
[14]	钱开国, 卜春芬, 王玉见, 申时凯. 基于可靠信标和节点度估计距离的无线传感器网络定位算法[J]. 计算机应用, 2019, 39(3): 817-823.
[15]	任晓奎, 李锋, 程琳. 基于动态损耗因子和权重的改进质心定位算法[J]. 计算机应用, 2019, 39(3): 824-828.

无线传感器网络RaSMaLai算法的改进

Improvement on RaSMaLai in wireless sensor networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics