Ring-based clustering algorithm for nodes non-uniform deployment

doi:10.11772/j.issn.1001-9081.2017.06.1527

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (6): 1527-1531.DOI: 10.11772/j.issn.1001-9081.2017.06.1527

Previous Articles Next Articles

Ring-based clustering algorithm for nodes non-uniform deployment

SUN Chao¹, PENG Li¹, ZHU Xuefang²

1. Engineering Research Center of Internet of Things Application Technology of the Ministry of Education(Jiangnan University), Wuxi Jiangsu 214122, China;
2. Jiangsu Union Technical Institute, Wuxi Jiangsu 214028, China

Received:2016-12-12 Revised:2017-03-01 Online:2017-06-10 Published:2017-06-14
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61502204), the University Natural Science Research Surface Project of Jiangsu (16KJB510044).

基于环的节点非均匀分布分簇算法

孙超¹, 彭力¹, 朱雪芳²

1. 物联网应用技术教育部工程研究中心(江南大学), 江苏无锡 214122;
2. 江苏省联合职业技术学院, 江苏无锡 214028

通讯作者: 孙超
作者简介:孙超(1991-),男,山东青岛人,硕士研究生,主要研究方向:无线传感器网络;彭力(1967-),男,河北唐山人,教授,博士,主要研究方向:视觉传感器网络、人工智能;朱雪芳(1967-),女,江苏常熟人,副教授,硕士,主要研究方向:通信与控制。
基金资助:
国家自然科学基金资助项目（61502204）；江苏省高校自然科学研究面上项目（16KJB510044）。

Abstract

Abstract: Aiming at the problem of energy hole in the nodes non-uniform deployment network model based on the ring in Wireless Sensor Network (WSN), a Ring-based Clustering Algorithm for Nodes Non-uniform Deployment (RCANND) was proposed. The number of the optimal cluster heads in each ring was calculated by minimizing the energy consumption of each ring in the nodes non-uniform deployment network model. The cluster head selectivity was calculated by using the residual energy of the nodes, the distance from the base station, and the average distance from the neighbor nodes. The cluster head rotation was carried out with the cluster head selection sequence in cluster, and the number of cluster formation phases was reduced to improve the efficiency of network energy utilization. The proposed algorithm was tested in the simulation experiments, the experimental results show that, the average energy consumption fluctuation of nodes under the same radius but different nodes deployment models is very small. The average energy consumption fluctuation of nodes under the same nodes deployment model but different radiuses is not obvious. The network lifetime was defined as the survivability of 50% network nodes. In the case of non-uniform deployment of nodes, the network lifetime of the proposed algorithm is higher than that of Unequal Hybrid Energy Efficient Distributed algorithm (UHEED) by about 18.1% while it is also higher than that of Rotated Unequal Hybrid Energy Efficient Distributed algorithm (RUHEED) by about 11.5%. In the case of uniform deployment of nodes, the network lifetime of the proposed algorithm is higher than that of sub-Ring-based Energy-efficient Clustering Routing for WSN (RECR) by about 6.4%. The proposed algorithm can effectively balance the energy consumption under different nodes deployment models and prolong the network lifetime.

Key words: non-uniform deployment, sub-ring, clustering, energy hole, Wireless Sensor Network (WSN)

摘要： 针对无线传感器网络（WSN）中基于环的节点非均匀分布网络模型下的能量空洞问题，提出了一种基于环的节点非均匀分布分簇算法（RCANND）。该算法在节点非均匀分布的网络模型下，通过每环的能耗最小化，计算每一环的最优簇首数；通过节点剩余能量、距基站距离以及与邻居节点的平均距离计算簇首选择度。在簇内以簇首选择度序列表进行簇首轮转，降低分簇次数，提高网络能量的利用效率。对提出的算法进行仿真对比实验，仿真结果表明，相同半径、不同分布模型下节点的平均能耗波动很小；相同分布模型、不同半径下节点的平均能耗波动也不明显。以网络中50%节点存活作为网络生命周期，在节点非均匀分布情况下，所提算法的网络生命周期比混合能量高效分布式不等分簇算法（UHEED）和轮转的混合能量高效分布式不等分簇算法（RUHEED）分别提高约18.1%和11.5%；在节点均匀分布模型下，所提算法的网络生命周期比基于分环的能量高效无线传感器网络分簇路由（RECR）协议提高约6.4%。所提算法有效均衡了不同分布模型下的能耗，有效延长了网络生命周期。

关键词: 非均匀分布, 分环, 分簇, 能量空洞, 无线传感器网络

CLC Number:

TP393.0

SUN Chao, PENG Li, ZHU Xuefang. Ring-based clustering algorithm for nodes non-uniform deployment[J]. Journal of Computer Applications, 2017, 37(6): 1527-1531.

孙超, 彭力, 朱雪芳. 基于环的节点非均匀分布分簇算法[J]. 计算机应用, 2017, 37(6): 1527-1531.

References

[1] RAWAT P, SINGH K D, CHAOUCHI H, et al. Wireless sensor networks:a survey on recent developments and potential synergies[J]. The Journal of Supercomputing, 2014, 68(1):1-48.
[2] LIU X X. A survey on clustering routing protocols in wireless sensor networks[J]. Sensors, 2012, 12(8):11113-11153.
[3] PANTAZIS N A, NIKOLIDAKIS S A, VERGADOS D D. Energy-efficient routing protocols in wireless sensor networks:a survey[J]. IEEE Communications Surveys & Tutorials, 2013, 15(2):551-591.
[4] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNANET H. Energy-efficient communication protocol for wireless microsensor networks[C]//HICSS'00:Proceedings of the 33rd Hawaii International Conference on System Sciences. Washington, DC:IEEE Computer Society, 2000:8020.
[5] EVER E, LUCHMUN R, MOSTARDA L, et al. UHEED:an unequal clustering algorithm for wireless sensor networks[EB/OL].[2016-11-10]. https://core.ac.uk/download/pdf/17301738.pdf.
[6] YOUNIS O, FAHMY S. HEED:a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[J]. IEEE Transactions on Mobile Computing, 2004, 3(4):366-379.
[7] 李成法,陈贵海,叶懋,等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,30(1):27-36.(LI C F, CHEN G H, YE M, et al. An uneven cluster-based routing protocol for wireless sensor networks[J]. Chinese Journal of Computers, 2007, 30(1):27-36.)
[8] AIERKEN N, GAGLIARDI R, MOSTARDA L, et al. RUHEED-rotated unequal clustering algorithm for wireless sensor networks[C]//Proceedings of the 2015 IEEE 29th International Conference on Advanced Information Networking and Applications Workshops. Piscataway, NJ:IEEE, 2015:170-174.
[9] OLARIU S, STOJMENOVIC I. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C]//INFOCOM 2006:Proceedings of the 2006 25th IEEE International Conference on Computer Communications. Piscataway, NJ:IEEE, 2006:1-12.
[10] 任丽婕,郭忠文,唐瑞春.无线传感器网络中基于能量平衡的部署算法[J].中国海洋大学学报(自然科学版),2008,38(5):841-844.(REN L J, GUO Z W, TANG R C. A node placement strategy based on energy-balance for wireless sensor networks[J]. Periodical of Ocean University of China, 2008, 38(5):841-844.)
[11] 刘震,郭航.基于同心环分簇网络模型的WSN能量空洞避免方法研究[J].计算机科学,2013,40(12):147-151.(LIU Z, GUO H. Study on concentric-ring and cluster-based energy hole avoiding method in wireless sensor networks[J]. Computer Science, 2013, 40(12):147-151.)
[12] 吴玉成,李伟琪, 胡真,等.一种基于分环的能量高效无线传感器网络分簇路由协议[J].传感器与微系统,2015,34(5):8-11.(WU Y C, LI W Q, HU Z, et al. A sub-ring-based clustering routing protocol for energy-efficient WSNs[J]. Transducer and Microsystem Technologies, 2015, 34(5):8-11.)
[13] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4):660-670.
[14] TRIPATHI R K, SINGH Y N, VERMA N K. Two-tiered wireless sensor networks-base station optimal positioning case study[J]. IET Wireless Sensor Systems, 2012, 2(4):351-360.

[1]	CHEN Hengheng, NI Zhiwei, ZHU Xuhui, JIN Yuanyuan, CHEN Qian. Differential privacy high-dimensional data publishing method via clustering analysis [J]. Journal of Computer Applications, 2021, 41(9): 2578-2585.
[2]	ZENG Xiangyin, ZHENG Bochuan, LIU Dan. Detection of left and right railway tracks based on deep convolutional neural network and clustering [J]. Journal of Computer Applications, 2021, 41(8): 2324-2329.
[3]	ZHU Cheng, ZHAO Xiaoqi, ZHAO Liping, JIAO Yuhong, ZHU Yafei, CHENG Jianying, ZHOU Wei, TAN Ying. Classification of functional magnetic resonance imaging data based on semi-supervised feature selection by spectral clustering [J]. Journal of Computer Applications, 2021, 41(8): 2288-2293.
[4]	WANG Jiarui, TAN Guoping, ZHOU Siyuan. Clustered wireless federated learning algorithm in high-speed internet of vehicles scenes [J]. Journal of Computer Applications, 2021, 41(6): 1546-1550.
[5]	DAI Yanran, DAI Guoqing, YUAN Yubo. Multi-face foreground extraction method based on skin color learning [J]. Journal of Computer Applications, 2021, 41(6): 1659-1666.
[6]	MA Jianhong, CAO Wenbin, LIU Yuangang, XIA Shuang. Patent clustering method based on functional effect [J]. Journal of Computer Applications, 2021, 41(5): 1361-1366.
[7]	LI Guorong, YE Jimin, ZHEN Yuanting. Time series clustering based on new robust similarity measure [J]. Journal of Computer Applications, 2021, 41(5): 1343-1347.
[8]	WANG Zhihe, CHANG Xiaoqing, DU Hui. Adaptive affinity propagation clustering algorithm based on universal gravitation [J]. Journal of Computer Applications, 2021, 41(5): 1337-1342.
[9]	LONG Chaoqi, JIANG Yu, XIE Yu. Improved wavelet clustering algorithm based on peak grid [J]. Journal of Computer Applications, 2021, 41(4): 1122-1127.
[10]	LI Xingfeng, HUANG Yuqing, REN Zhenwen, LI Yihong. Robust multi-view clustering algorithm based on adaptive neighborhood [J]. Journal of Computer Applications, 2021, 41(4): 1093-1099.
[11]	ZOU Zhiwen, QIN Cheng. Method of dynamically constructing spatial topic R-tree based on k-means++ [J]. Journal of Computer Applications, 2021, 41(3): 733-737.
[12]	GUO Jia, HAN Litao, SUN Xianlong, ZHOU Lijuan. Comparative density peaks clustering algorithm with automatic determination of clustering center [J]. Journal of Computer Applications, 2021, 41(3): 738-744.
[13]	LYU Jia, XIAN Yan. Co-training algorithm combining improved density peak clustering and shared subspace [J]. Journal of Computer Applications, 2021, 41(3): 686-693.
[14]	ZHANG En, LI Huimin, CHANG Jian. Verifiable k-means clustering scheme with privacy-preserving [J]. Journal of Computer Applications, 2021, 41(2): 413-421.
[15]	SUN Huan, CHEN Hongbin. Node redeployment strategy based on firefly algorithm for wireless sensor network [J]. Journal of Computer Applications, 2021, 41(2): 492-497.

Ring-based clustering algorithm for nodes non-uniform deployment

基于环的节点非均匀分布分簇算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics