基于最小生成树的非均匀分簇路由算法

doi:10.3724/SP.J.1087.2012.00787

计算机应用 ›› 2012, Vol. 32 ›› Issue (03): 787-790.DOI: 10.3724/SP.J.1087.2012.00787

基于最小生成树的非均匀分簇路由算法

张明才,薛安荣,王伟

江苏大学计算机科学与通信工程学院,江苏镇江 212013

收稿日期:2011-08-17 修回日期:2011-12-09 发布日期:2012-03-01 出版日期:2012-03-01
通讯作者: 张明才
作者简介:张明才(1986-),男,山东临沂人,硕士研究生,CCF会员,主要研究方向:数据挖掘、无线传感器网络;薛安荣(1964-),男,江苏镇江人,教授,博士,CCF高级会员,主要研究方向:数据库、数据挖掘;王伟(1986-),男,山东滨州人,硕士研究生,CCF会员,主要研究方向:恐怖事件与行为预测。
基金资助:
高校博士点基金资助项目(20093227110005);省科技型企业创新资金资助项目(BC2010172);校高级人才启动基金资助项目(09JDG041)。

Uneven clustering routing algorithm based on minimum spanning tree

ZHANG Ming-cai, XUE An-rong, WANG Wei

School of Computer Science and Telecommunication Engineering, Jiangsu University, Zhenjiang Jiangsu 212013, China

Received:2011-08-17 Revised:2011-12-09 Online:2012-03-01 Published:2012-03-01
Contact: Ming-Cai ZHANG

摘要/Abstract

摘要： 发现现有的针对非均匀分簇路由算法没有充分考虑簇首与基站之间最优路径选择,而导致传输路径上的能量消耗不均衡的问题。为了更好地均衡传输路径上节点能量的消耗,提出了基于最小生成树的非均匀分簇的路由算法。该算法利用节点剩余能量和节点到基站的距离选举簇首,然后通过建立最小生成树搜寻最优传输路径,这样可以减少传输路径上的能量消耗,有效地解决能耗不均衡问题。理论分析和实验结果均表明,该算法无论在存活节点个数还是在能量消耗上都明显优于EEUC算法和EBCA。

关键词: 簇首, 非均匀分簇, 不均衡, 剩余能量, 最小生成树

Abstract: The existing uneven clustering routing algorithms do not consider the optimal path selection between cluster heads and base station, which leads to unbalanced energy consumption. In order to balance energy consumption of transmission paths, this paper proposed an uneven clustering routing algorithm based on minimum spanning tree. The algorithm utilized residual energy of nodes and the distance between nodes and base station to select cluster heads, and then generated minimum spanning tree to search the optimal transmission paths, which reduced energy consumption on the transmission paths and effectively solved unbalanced energy consumption. The theoretical analysis and experimental results show that the algorithm is better than the existing Energy Efficient Uneven Clustering (EEUC) and Energy Balancing Clustering Algorithm (EBCA) in terms of the number of live nodes and energy consumption.

Key words: cluster head, uneven clustering, unbalanced, residual energy, minimum spanning tree

中图分类号:

TP393

张明才薛安荣王伟. 基于最小生成树的非均匀分簇路由算法[J]. 计算机应用, 2012, 32(03): 787-790.

ZHANG Ming-cai XUE An-rong WANG Wei. Uneven clustering routing algorithm based on minimum spanning tree[J]. Journal of Computer Applications, 2012, 32(03): 787-790.

参考文献

[1]HENZELMAN W, CHANDRAKSAN A, BALAKRISHNAN H. Energy efficient communication protocol for wireless microsensor net-works[C]// Proceedings of the 33rd Hawaii International Conference on System Sciences. Washington, DC, IEEE Computer Society, 2000: 3005-3014.

[2]李成法,陈贵海.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,30(1):27-36.

[3]LIAO WEN-HWA, KAO YUCHENG, WU RU-TING. Ant colony optimization based sensor deployment protocol for wireless sensor networks [J]. Expert Systems with Applications, 2011, 38(6):6599-6605.

[4]李志宇,史浩山.一种负载均衡的无线传感器网络自适应分簇算法[J].西北工业大学学报, 2009, 27(6):822-826.

[5]HE YONGGANG, XU TINGRONG. An improved uneven clustering routing algorithm for sensor networks[C]// The International Symposium on Computer Networks and Multimedia Technology. Piscataway, NJ: IEEE Press, 2009:1-5.

[6]彭铎, 张秋余, 贾科军. 能量高效的无线传感器网络分簇路由协议 [J]. 计算机工程, 2009, 35(17):123-125.

[7]MIHAYLOV S R, JACOB M, LVES Z G, et al. Dynamic join optimization in multi-hop wireless sensor networks [J]. Proceedings of the VLDB Endowment, 2010, 3(1/2):1279-1290.

[8]LI L Y, JIANG X L, ZHONG S H, et al. Energy balancing clustering algorithm for wireless sensor networks[C]// NSWCTC'09: International Conference on Networks Security, Wireless Communications and Trusted Computing. Piscataway, NJ: IEEE Press, 2009:61-64.

[9]YUAN HUIYONG, LIU YONGLI, YU JIANGPING. A new energy-efficient unequal clustering algorithm for wireless sensor networks[C]// IEEE International Conference on Computer Science and Automation Engineering. [S.l.]: IEEE, 2011: 431-434.

[10]BAJABER F, AWAN I. Adaptive decentralized re-clustering protocol for wireless sensor networks [J]. Journal of Computer and System Sciences, 2011,77(2):282-292.

[11]李磊,刘海涛. 无线传感器网络节点非均匀分布方法研究 [J]. 小型微型计算机系统, 2010, 31(11):2180-2184.

[12]刘安丰, 阳国军, 陈志刚. 基于不等簇半径转换工作的传感器网络能量空洞避免研究 [J]. 通信学报, 2010, 31(1):1-8.

[13]陈志奎, 倪晶晶, 姜国海. 一种基于剩余能量级别的负载均衡路由协议 [J]. 微电子学与计算机, 2010, 27(12):82-86.

[14]JUNG J W, INGRAM M A. Residual-energy-activated cooperative transmission to avoid the energy hole [C]// Proceedings of IEEE International Conference on Communications Workshops. Piscataway, NJ: IEEE Press, 2010: 1-5.

[15]HEINZELMAN W, CHANDRAKSAN A. An application specific protocol architecture for wireless micro-sensor networks[J]. IEEE Transactions on Wireless Communication, 2002, 1(4): 660-670.

基于最小生成树的非均匀分簇路由算法

Uneven clustering routing algorithm based on minimum spanning tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	杨鲜, 赵计生, 强保华, 米路中, 彭博, 唐成华, 李宝莲. 基于改进的BSMOTE和时序特征的风机故障采样算法[J]. 计算机应用, 2021, 41(6): 1673-1678.
[2]	崔鑫, 徐华, 宿晨. 面向不均衡数据集的过抽样算法[J]. 计算机应用, 2020, 40(6): 1662-1667.
[3]	韩丽, 刘书宁, 于冰, 徐圣斯, 唐棣. 基于最优最小生成树的三维模型形状优化方法[J]. 计算机应用, 2019, 39(3): 858-863.
[4]	李安超, 陈桂芬. 基于奇偶轮成簇和双簇首的非均匀分簇协议[J]. 计算机应用, 2018, 38(7): 1995-2000.
[5]	姚玉坤, 刘江兵, 李小勇. 基于簇父集协作通信的低功耗有损网络路由算法优化[J]. 计算机应用, 2017, 37(5): 1300-1305.
[6]	王林, 郭娜娜. 基于差异度的不均衡电信客户数据分类方法[J]. 计算机应用, 2017, 37(4): 1032-1037.
[7]	李鑫滨, 王贝, 韩松. 基于Stackelberg博弈的双层水下传感器网络功率分配算法[J]. 计算机应用, 2017, 37(3): 730-735.
[8]	李新春, 高佰胜. 基于最优簇数和改进引力搜索的WSN路由算法[J]. 计算机应用, 2017, 37(12): 3374-3380.
[9]	郭浩, 刘磊, 陈俊杰. 基于高阶最小生成树的脑网络分析及对阿兹海默氏症患者的分类[J]. 计算机应用, 2017, 37(11): 3339-3344.
[10]	靳燕, 彭新光. 多子域隔离学习组合决策用于不均衡样本[J]. 计算机应用, 2016, 36(9): 2475-2480.
[11]	刘洋, 彭舰, 刘唐, 王彬. 基于分层的河流水下传感器网络路由算法[J]. 计算机应用, 2016, 36(5): 1183-1187.
[12]	黄廷辉, 伊凯, 崔更申, 王玉良. 基于非均匀分簇的无线传感器网络分层路由协议[J]. 计算机应用, 2016, 36(1): 66-71.
[13]	张茂兴, 王海峰, 向凤红, 毛剑琳, 张传龙. 基于剩余能量动态调整前向角度的路由算法[J]. 计算机应用, 2016, 36(1): 77-80.
[14]	毛文涛, 王金婉, 何玲, 袁培燕. 面向贯序不均衡数据的混合采样极限学习机[J]. 计算机应用, 2015, 35(8): 2221-2226.
[15]	王金婉, 毛文涛, 何玲, 王礼云. 基于不均衡样本重构的加权在线贯序极限学习机[J]. 计算机应用, 2015, 35(6): 1605-1610.