基于分布式层次化结构的非均匀聚类负载均衡算法

doi:10.11772/j.issn.1001-9081.2015.02.0332

计算机应用 ›› 2015, Vol. 35 ›› Issue (2): 332-335.DOI: 10.11772/j.issn.1001-9081.2015.02.0332

基于分布式层次化结构的非均匀聚类负载均衡算法

郭晋秦¹, 韩焱²

1. 太原工业学院自动化系, 太原 030008;
2. 电子测试技术国家重点实验室(中北大学), 太原 030051

收稿日期:2014-09-01 修回日期:2014-11-23 出版日期:2015-02-10 发布日期:2015-02-12
通讯作者: 郭晋秦
作者简介:郭晋秦(1975-),女,山西运城人,副教授,硕士,主要研究方向:通信与控制工程、测试计量; 韩焱(1957-),男,山西文水人,教授,博士生导师,主要研究方向:电子信息工程、信息对抗与信息安全、数字图像处理。
基金资助:
国家自然科学基金资助项目(61071193;60772102)。

Load balancing algorithm for non-uniform clustering with distributed hierarchical structure

GUO Jinqin¹, HAN Yan²

1. Department of Automation, Taiyuan Institute of Technology, Taiyuan Shanxi 030008, China;
2. National Key Laboratory for Electronic Measurement Technology (North University of China), Taiyuan Shanxi 030051, China

Received:2014-09-01 Revised:2014-11-23 Online:2015-02-10 Published:2015-02-12

摘要/Abstract

摘要：

考虑到无线传感器网络(WSN)负载不均衡导致节点存活时间较短、能量消耗量较多的问题,提出一种基于分布式层次化结构的非均匀聚类负载均衡算法(DCWSN)。首先,建立了一个WSN的多层分簇的网络拓扑结构,并分析了该网络拓扑的簇内节点运作的能量消耗方式。接着,采用非均匀聚类的负载均衡算法,在簇头的选择上考虑了节点连通密度、节点剩余能量和簇头选择时间,通过竞选出最高权重的节点成为簇头; 在簇的建立阶段,通过簇大小的决定阈值和簇头的更新机制来均衡簇头的能量负载,防止簇头节点过早死亡。通过网络生命周期和网络能量消耗对提出算法的有效性进行验证,并与算法EDDIE、M-TRAC、DDC和EELBC进行比较,结果显示DCWSN算法的节点存活率为37.7%,高于对比算法,且能量效率也高于对比算法。实验结果表明,DCWSN算法对节点负载分配具有良好的均衡性,有效控制了节点负载过量的问题,提高了节点的能量效率。

关键词: 分布式, 层次化结构, 非均衡聚类, 负载均衡, 无线传感器网络

Abstract:

Aiming at the problems such as short survival time and great energy consumption caused by load imbalance in Wireless Sensor Network (WSN), a kind of load balancing algorithm for non-uniform clustering with distributed hierarchical structure named DCWSN was proposed. First, the network topology structure with multilayer clusters for WSN was established, and the energy consumption mode of the nodes in the clusters of it was analyzed.Second, the load balancing algorithm for non-uniform clustering was used to choose the node with highest weight to be cluster head node with considering the node connected density, node residual energy and cluster head choose time. In the establishment of the cluster stage, the energy load of the cluster head was balanced by cluster size decision threshold and the cluster updating mechanism to prevent the premature death of cluster nodes. Comparison experiments on life cycle of the network and the network energy consumption were conducted with EDDIE, M-TRAC, DDC and EELBC to verify the effectiveness of the proposed algorithm, and DCWSN achieved a higher survival rate of node at 37.7% and a higher energy efficiency. The experimental results show that DCWSN has good performance in load balance, effectively controls the overload of node, and also improves the energy efficiency of node.

Key words: distribution, hierarchical structure, non-equilibrium clustering, load balancing, Wireless Sensor Network (WSN)

中图分类号:

TN929.5

郭晋秦, 韩焱. 基于分布式层次化结构的非均匀聚类负载均衡算法[J]. 计算机应用, 2015, 35(2): 332-335.

GUO Jinqin, HAN Yan. Load balancing algorithm for non-uniform clustering with distributed hierarchical structure[J]. Journal of Computer Applications, 2015, 35(2): 332-335.

参考文献

[1] SHU Q, HU Q, ZHENG J, et al. A dependable Slepian-Wolf coding based clustering algorithm for data aggregation in wireless sensor networks [C]//Proceedings of the 2013 International Conference on Wireless Communications & Signal Processing. Piscataway: IEEE, 2013: 1-6.
[2] HACKMANN G, GUO W, YAN G, et al. Cyber-physical codesign of distributed structural health monitoring with wireless sensor networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1): 63-72.
[3] JAIN A, REDDY B V R. Optimal degree centrality based algorithm for cluster head selection in wireless sensor networks [C]//Proceedings of the 2014 Recent Advances in Engineering and Computational Sciences. Piscataway: IEEE, 2014: 1-6.
[4] ZHANG S, ZHANG H,ZHANG S. Multi-hop routing algorithm for wireless sensor networks based on fixed cluster and energy-balance [J]. Transducer and Microsystem Technologies, 2013, 32(8): 117-120. (张世伟, 张海涛, 张士杰. 基于固定分簇和能量均衡的无线传感器网络多跳路由算法[J]. 传感器与微系统, 2013, 32(8): 117-120.)
[5] MAO S, ZHAO C, ZHOU Z, et al. An improved fuzzy unequal clustering algorithm for wireless sensor network [J]. Mobile Networks and Applications, 2013, 18(2): 206-214.
[6] BAGCI H, YAZICI A. An energy aware fuzzy approach to unequal clustering in wireless sensor networks [J]. Applied Soft Computing, 2013, 13(4): 1741-1749.
[7] TRIOATHI R K, SINGH Y N, VERMA N K. Clustering algorithm for non-uniformly distributed nodes in wireless sensor network [J]. Electronics Letters, 2013, 49(4): 299-300.
[8] CHEN G, WANG Y. Optimization time synchronization in cross-layer service for WSNs[J]. Optics and Precision Engineering, 2013, 21(12): 3231-3238. (陈桂芬, 王义君. 无线传感器网络跨层服务优化时间同步机制[J]. 光学精密工程, 2013, 21(12): 3231-3238.)
[9] JAVAID N, QRRESHI T N, KHAN A H, et al. EDDEEC: Enhanced developed distributed energy-efficient clustering for heterogeneous wireless sensor networks [J]. Procedia Computer Science, 2013, 19: 914-919.
[10] SHIVAPRAKASHA K S, KULKARNI M, JOSHI N. Improved network survivability using Multi-Threshold Adaptive Range Clustering (M-TRAC) algorithm for energy balancing in wireless sensor networks[J]. Journal of High Speed Networks, 2013, 19(2): 99-113.
[11] DIN W I S W, YAHYA S, TAIB M N, et al. MAP: the new clustering algorithm based on multitier network topology to prolong the lifetime of wireless sensor network [C]//CSPA 2014: Proceedings of the IEEE 10th International Colloquium on Signal Processing & its Applications. Piscataway: IEEE, 2014: 173-177.
[12] DENG X, HUANG J. Optimal data acquisition scheme about LEACH [J]. Journal of Southeast University: Natural Science Edition, 2012, 42(1): 20-24. (邓夏阳, 黄杰. LEACH算法最优数据采集方案[J]. 东南大学学报: 自然科学版, 2012, 42(1): 20-24.
[13] WNAG J, LIU G. Method of energy saving based on particle swarm optimization clustering for greenhouse wireless sensor netwoks [J]. Transactions of the Chinese Society of Agricultural Engineering, 2012, 28(7): 172-177. (王俊, 刘刚. 基于粒子群优化聚类的温室无线传感器网络节能方法[J]. 农业工程学报, 2012, 28(7): 172-177.)
[14] CHEN D, LIU Z, WANG L, et al. Natural disaster monitoring with wireless sensor networks: a case study of data-intensive applications upon low-cost scalable systems [J]. Mobile Networks and Applications, 2013, 18(5): 651-663.
[15] ADNAN M A, RAZZAQUE M A, AHMED I, et al. Bio-mimic optimization strategies in wireless sensor networks: a survey [J]. Sensors, 2014, 14(1): 299-345.
[16] RIJIN I K, SAKTHIVEL N K, Subasree S. Development of an enhanced efficient secured multi-hop routing technique for wireless sensor networks [J]. International Journal of Innovative Research in Computer and Communication Engineering, 2013, 1(3): 507-512.
[17] SINGH B, LOBIYAl D K. An energy-efficient adaptive clustering algorithm with load balancing for wireless sensor network [J]. International Journal of Sensor Networks, 2012, 12(1): 37-52.
[18] KUILA P, JANA P K. Energy efficient load-balanced clustering algorithm for wireless sensor networks[J]. Procedia Technology, 2012, 6: 771-777.

基于分布式层次化结构的非均匀聚类负载均衡算法

Load balancing algorithm for non-uniform clustering with distributed hierarchical structure

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[2]	赵全, 汤小春, 朱紫钰, 毛安琪, 李战怀. 大规模短时间任务的低延迟集群调度框架[J]. 计算机应用, 2021, 41(8): 2396-2405.
[3]	尹春勇, 张帼杰. 面向分布式漂移数据流的集成分类模型[J]. 计算机应用, 2021, 41(7): 1947-1955.
[4]	卿欣艺, 陈玉玲, 周正强, 涂园超, 李涛. 基于中国剩余定理的区块链存储扩展模型[J]. 计算机应用, 2021, 41(7): 1977-1982.
[5]	王家瑞, 谭国平, 周思源. 高速车联网场景下分簇式无线联邦学习算法[J]. 计算机应用, 2021, 41(6): 1546-1550.
[6]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[7]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[8]	崔双双, 王宏志. 基于日志结构合并树的轻量级分布式索引实现方法[J]. 计算机应用, 2021, 41(3): 630-635.
[9]	孙环, 陈宏滨. 基于萤火虫算法的无线传感器网络节点重部署策略[J]. 计算机应用, 2021, 41(2): 492-497.
[10]	王鹏, 李艳雯, 杨迪, 杨华民. 基于层级控制的宏观基本图交通信号控制模型[J]. 计算机应用, 2021, 41(2): 571-576.
[11]	苟子安, 张晓, 吴东南, 王艳秋. 分布式存储系统中的日志分析与负载特征提取[J]. 计算机应用, 2020, 40(9): 2586-2593.
[12]	韩雨涝, 房鼎益. 基于链路交点相对位置信息的轻量级覆盖空洞检测算法[J]. 计算机应用, 2020, 40(9): 2698-2705.
[13]	胡润彦, 李翠然. 基于模糊控制的自供能无线传感器网络分簇算法[J]. 计算机应用, 2020, 40(9): 2691-2697.
[14]	王波, 任英琦, 黄冬艳. H-Algorand:基于多块输出的公有链共识机制[J]. 计算机应用, 2020, 40(7): 2150-2154.
[15]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.