Journal of Robotics, Networking and Artificial Life
Vol. 7(2); September (2020), pp. 111–115
DOI: https://doi.org/10.2991/jrnal.k.200528.008; ISSN 2405-9021; eISSN 2352-6386
https://www.atlantis-press.com/journals/jrnal

Research Article

X-means Clustering for Wireless Sensor Networks
Abdelrahman Radwan1, Nazhatul Kamarudin1, Mahmud Iwan Solihin1, Hungyang Leong1, Mohamed Rizon1,*,
Hazry Desa2, Muhammad Azizi Bin Azizan2
Faculty of Engineering, Technology and Built Environment, UCSI University, Jalan Puncak Menara Gading, Taman Connaught,
Kuala Lumpur 56000, Malaysia
2
Centre of Excellence for Unmanned Aerial Systems (COEUAS), Universiti Malaysia Perlis, Block E, Pusat Perniagaan Pengkalan Jaya,Jalan Kangar – AlorSetar, Kangar, Perlis 01000, Malaysia
1ARTICLE INFOABSTRACT

Article History

K-means clustering algorithms of wireless sensor networks are potential solutions that prolong the network lifetime. However,limitations hamper these algorithms, where they depend on a deterministic K-value and random centroids to cluster theirnetworks. But, a bad choice of the K-value and centroid locations leads to unbalanced clusters, thus unbalanced energy
consumption. This paper proposes X-means algorithm as a new clustering technique that overcomes K-means limitations;clusters constructed using tentative centroids called parents in an initial phase. After that, parent centroids split into a rangeof positions called children, and children compete in a recursive process to construct clusters. Results show that X-means
outperformed the traditional K-means algorithm and optimized the energy consumption.

Received 06 November 2019
Accepted 04 May 2020
Keywords
K-means
X-means
clustering
wirelesssensorsnetworks© 2020 The Authors. Published by Atlantis Press SARL.
This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

1. INTRODUCTION
Machine-to-machine communication and internet of things
require low power communication networks [1]. Wireless Sensor
Network (WSN) is a potential candidate that provides an infrastructure for these technologies. WSN is a group of wireless nodes thatare equipped with sensors and actuators; the network is designed
as an application specific and performs dedicated tasks. Wirelessnodes depend on batteries as a source of energy and the wirelessunit drains nodes batteries [2]; therefore, routing data considered
an expensive and complex task. In the literature, clustering routing
algorithms have shown promising enhancements of the WSN lifetime; classical algorithms such as LEACH [3], HEED [4], and EECS
[5] divide their networks into random clusters, and each clustercomprises a Cluster Head (CH) and wireless nodes. Data collectedfrom surroundings and relayed to CHs; then CHs have to forward
the data after aggregating them to a central unit called Sink. CHs
use long-range communications called backhauling to the sink.
The role of CH is frequently rotated to distribute the energy consumption load among nodes and thus re-clustering initiated every
round of operation. Due to the random clustering of wirelessnodes, classical algorithms suffer from an unbalanced intra-cluster
distance and unbalanced energy consumptions. Another clustering algorithms are K-means algorithms such as Periyasamy et al.
[6], Park et al. [7], Sasikumar and Khara [8], Razzaq et al. [9] andKhan et al. [10]; these algorithms estimate the number of clusters
and their initial centroids. In K-means, wireless nodes assigned toCorresponding author. Email: MohdRizon@ucsiuniversity.edu.my*clusters based on the minimum distance to centroids, then average Euclidean distance to these centroids are determined and centroids repositioned. After that, wireless nodes re-clustered andassigned to the new centroids. Determining the mean distance andre-­clustering the nodes are repeated until centroid positions fixed,and cluster members are static.
Unlike classical algorithms, K-means algorithms balance theintra-cluster distance of clusters; but still these algorithms constructunequal clusters because of random centroid positions; where abad choice of initial centroids leads to unbalanced cluster sizes andunbalanced CHs consumption, thus premature CHs death at theearly stage of the network lifetime. Therefore, this article proposes
to construct initial clusters using K-means, then the X-mean algorithm splits each cluster centroid into multiple positions, and thensearches for the best position and the best number of clusters.
The rest of the article is as follows, in Section 2 the system modelis presented, then in Section 3 we propose X-mean algorithm anddescribe its two operation phases with mathematical equations,after that in Section 4 the simulation results and a discussion on
how the proposed algorithm prolongs WSN lifetime, finally inSection 5, we conclude our work with future recommendations tofurther enhance the X-means algorithm.

2. SYSTEM MODEL
The system model obtained from Ref. [3], and it includes twoparts; a transmitter model and a receiver model, as in Equations (1)A. Radwan et al. / Journal of Robotics, Networking and Artificial Life 7(2) 111–115

112

and (2). The transmitter consumption model of Equation (1) consists of Eelec as the energy required to aggregate and process data,
and the amplification energy required to transmit data (b) over(d) distance. Equation (1) describes two types of the amplificationenergies, where efs describes the amplification energy required totransmit a single bit using the freespace model; and emp describes
the amplification energy required to transmit a single bit using themultipath fading model. d0 is the crossover distance between thefreespace model and the multipath model, and it is described inPark et al. [7]. The total transmission energy (ETx) is proportional
to the distance between a source node and a destination node,
where it corresponds to d2 attenuation when d is less than do andcorresponds to d4 attenuation when d is greater than or equal do.
The Receiving consumption (ERx) includes the energy required toprocess data packet (b) in bits as in Equation (2).
(1)		 ERx = b * Eelec (2)In our previous work [11], X-means had a fixed number of children,
but here the X-means provides a dynamic range of centroids. The
concept of the X-means clustering summarized into two phases; thefirst phase is constructing random clusters with random centroids,
then using K-means, optimize these positions as in Equation (3).
The process repeated recursively until a final copy of centroids isdetermined and the final copy of centroids called parent centroids.
In phase two, parents give birth to multiple children (Cj), the initial
locations of the children determined as in Equation (4); where θ =2π/j and (dm) is the average Euclidean distance between the parent
and nodes in the cluster as in Equation (5).

ìï X j = dm cosq
Cj = í1, 2, 3, ..., j Î Pn ïî y j = dmsinq
S1 ndm = å (x p - xi )2 + ( y p - yi )2 , P Î Pn Sn i =1)

CC nj = Æ(x , y ) +1
ïì n Î 1, 2, 3, ... kbi ( x , y ) íå
Sn i =1
îïi Î 1, 2, 3, ... Sn
S(6)
(7)
(8)

CCnj: final position of child (j) of parent (n).
ADij: average distance to the child (j) and the sink.
ADi: minimum average distance of node (i) to child (j).
dij: node (i) Euclidean distance to child (j).
Disink: node (i) Euclidean distance to the sink.

3. PROPOSED METHOD

1 S
ïì n Î 1, 2, 3, ..., kbi ( x , y ) íåSn i =1
îïi Î 1, 2, 3, ..., Sn(æ dij + disink ö
÷ , i Î 1, 2, 3, ..., Sn 
ADij = min çç÷2èøADi = min{ADi1 , ADi 2 , ADi 3 , ..., ADij }, i Î Sn , j Î Pn ∅(x, y): position of the sink.

2
ïì b * Eelec + b * e fs * d , d < do		 ETx = í4ïîb * Eelec + b * e mp * d , d ³ doPn = a n -1 (x , y ) +The X-means algorithm recursively executes Equation (8) untilchildren centroid positions are fixed. The recursive run has threeoutcomes; children form their own clusters and parents collapsed,second some children and parents diminished, and third, children
collapsed, and parents repositioned to best locations.

(3)
(4)

Figure 1 shows an example of the algorithm run in an area of100 × 100, where parents set to three and children to two. The
first generation is parents generated by K-means as in Figure 1a,and the number of generated parents is three, then parents splitand each gives birth to two children as in Figure 1b (marked withtriangle and circles), the total of children and parents becomesnine centroids, finally X-means diminishes the parents, and somechildren, and repositioned the remaining children as in Figure 1c.
Remaining centroids form static clusters of the network. In
X-means, nodes with minimum distance to centroids and highestenergy selected as CHs, then if the CH energy dropped below anenergy threshold, it steps down and the next closest and highest
energy node becomes the CH. In our implementation, the energy
threshold is a predefined value, but this value is not static, whereonce a node energy dropped below the threshold the node determines a new threshold, the new threshold is a step down from theoriginal threshold by (s ) as in Equation (9).
ab(5)

Pn: Parent (n) centroid.
an–1(x, y): x and y position of previous (n − 1) parent centroid.
Sn: Set of nodes assigned to Pn.
bi(x, y): the x and y position of node (i).

cdm: the average distance between parent centroid and nodes in thecluster.
Cj: the location of the child (j) of parent (Pn).
After that, new children Cj are set as cluster centroids, thennodes re-clustered and assigned using a minimization technique,where nodes grouped by the minimum average some of their distance from the sink and children (Cj) as in Equations (6) and (7).

Figure 1 | X-means two phase of centroid generation. (a) Parent centroids
generated after running K-means. (b) Parents give birth to new children
centroids. (c) Remaining centroids after running X-means.

A. Radwan et al. / Journal of Robotics, Networking and Artificial Life 7(2) 111–115		 Eth (n) = Eth (n -1) - (s * Eth(n -1) ) 113

(9)Eth(n): the new energy threshold.
Eth(n − 1): the previous energy threshold.
This step down ensures that all cluster members can participate asCHs until they are depleted.

4. RESULTS AND DISCUSSION
The proposed algorithm simulated with MATLAB and the simulation parameters in Table 1. There are extensive simulations done totest the algorithm. Figure 2 depicts the result of an area 220 × 220
that contains 220 nodes, nodes deployment is random, but nodes
density is uniform. In X-means the number of centroids is notdetermined, but only initial centroids are set. Assuming the maximum allowed clusters is 5% of the total network nodes [3], then thetotal clusters are 11, thus the X-means initialized for two scenarios;
when the number of parents (P) is two and give birth to five children (C), and when P is five and give birth to two C; also, K-means[7] initialized for ten centroids. During the simulation, the adopted
data paradigm is continuous, where CHs always have data to send
to the sink. Results measure the network lifetime in round, where asingle round is a single packet received from CHs at the sink.

Figure 3 | Intra-cluster distance for variations of the network areas.

Results show that X-means prolongs the network life in term of First
Node Death (FND). The positions of centroids minimized nodes
Table 1 | X-means simulation parameters
Parameter

Description

Valued0efsemp
Eelec

Crossover distance87 mFreespace model amplification energy 10 pJ/bit/m²
Multipath amplification energy
0.0013 pJ/bit/m4
Single bit processing energy
Tx or Rx = 50 nJ/bit
Aggregation =5 nJ/bit
Einit
Initial energy
0.5 J
EthEnergy threshold
0.2 J
Eth step down
5%sPacket size
Data size
4.2 Kb/packet
Control packet Packet headers
0.2 Kb/packet

Figure 4 | Average energy consumption for the cluster per round of thesimulation.

consumption per round by reducing the intra-cluster distance. The
result in Figure 2, shows FND enhancement of 39% when P = 2 and
57% when P = 5 over the K-means algorithm. We extended the simulation to include variations of the network areas and combinations ofparents and children, the results depicted in Figure 3. The result showsthat whenever the number of parents is greater than the number ofchildren, X-means achieves a smaller intra-cluster distance. Thisphenomenon occurs because of dividing the area into small search
spaces at phase one of the algorithm, which makes it easier to find thebest position at phase two. During the simulation we also monitored
the average energy consumption as in Figure 4. The result shows that
the X-means in its all variation consumed energy less than K-means.
The highest X-means consumption occurred when the area was
370 × 370, where increasing the area increased the backhaul distanceand thus increased the overall energy consumption of the cluster.

5. CONCLUSION

Figure 2 | X-means simulation when the number of parents is two andfive and children two and five.

In this article we proposed the X-means with multiple children asa solution for K-means shortcomings. The algorithm depends on
the initial values of parents and children. Then parents and children evaluated to generate a final copy of centroids that is less than

A. Radwan et al. / Journal of Robotics, Networking and Artificial Life 7(2) 111–115

114

the maximum number of the allowed network centroids. X-means
selects centroid locations that optimize the intra-cluster distanceand prolong the network lifetime. The simulation scenarios werelimited to 180, 220 and 370 nodes. Thus, the performance is notchecked for large scale deployment such as 1000 nodes.

CONFLICTS OF INTEREST
The authors declare they have no conflicts of interest.

ACKNOWLEDGMENTS
The authors thank UCSI University Trust Fund and Centre ofExcellence for Research, Value Innovation and Entrepreneurship(CERVIE) for supporting this work.

REFERENCES[1] X. Li, D. Li, J. Wan, A.V. Vasilakos, C.F. Lai, S. Wang, A review
of industrial wireless networks in the context of industry 4.0,
Wireless Netw. 23 (2017), 23–41.
[2] J. Yick, B. Mukherjee, D. Ghosal, Wireless sensor network survey,Comput. Netw. 52 (2008), 2292–2330.
[3] W.R. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy-­
efficient communication protocol for wireless microsensor networks, Proceedings of the 33rd Annual Hawaii International
Conference on System Sciences, IEEE, Maui, HI, USA, 2000,
p. 10.

[4] O. Younis, S. Fahmy, HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks, IEEE Trans.
Mob. Comput. 3 (2004), 366–379.
[5] M. Ye, C. Li, G. Chen, J. Wu, EECS: an energy efficient clustering scheme in wireless sensor networks, 24th IEEE International
Performance, Computing, and Communications Conference(PCCC), IEEE, Phoenix, AZ, USA, 2005, pp. 535–540.
[6] S. Periyasamy, S. Khara, S. Thangavelu, Balanced cluster head
selection based on modified k-means in a distributed wirelesssensor network, Int. J. Distrib. Sens. Netw. 2016 (2016), 1–11.
[7] G.Y. Park, H. Kim, H.W. Jeong, H.Y. Youn, A novel cluster head
selection method based on K-means algorithm for energy efficient
wireless sensor network, 2013 27th International Conference on
Advanced Information Networking and Applications Workshops,IEEE, Barcelona, Spain, 2013, pp. 910–915.
[8] P. Sasikumar, S. Khara, K-means clustering in wireless sensor networks, 2012 Fourth International Conference on Computational
Intelligence and Communication Networks, IEEE, Mathura,India, 2012, pp. 140–144.
[9] M. Razzaq, D.D. Ningombam, S. Shin, Energy efficient K-meansclustering-based routing protocol for WSN using optimal packet
size, 2018 International Conference on Information Networking(ICOIN), IEEE, Chiang Mai, Thailand, 2018, pp. 632–635.
[10] A. Khan, I. Tamim, E. Ahmed, M.A. Awal, Multiple Parameter
Based Clustering (MPC): prospective analysis for effective clustering in Wireless Sensor Network (WSN) using K-means algorithm.
Wireless Sens. Netw. 4 (2012), 18–24.
[11] A. Radwan, N.H. Kamarudin, M.I. Solihin, C.K. Ang, H. Leong,M. Rizon, Implementation of the X-means clustering algorithm for
wireless sensor networks, International Conference on Artificial Lifeand Robotics (ICAROB), Beppu, Oita, Japan, 2020, pp. 333–337.

AUTHORS INTRODUCTION
Abdelrahman Radwan
He obtained a BEE (2007) and M.Sc (2009)
from Northumbria University, UK. From2010 to 2016, he worked as a senior wireless development engineer. Currently, he isa PhD student in Engineering Department
at UCSI University, Malaysia. His researchinterests are wireless systems and embedded systems.

Dr. Nazhatul Hafizah Kamarudin
She is currently a lecturer in Departmentof Electrical and Electronic in UCSI
University in Malaysia. She is also theUCSI Internship Coordinator. She
graduated with a bachelor degree andmaster degree in Electrical Engineeringwith honour from Stevens Institute ofTechnology, NJ, USA. She received her PhD in ElectricalEngineering at UiTM Shah Alam, Malaysia. Her research works
focus on Cybersecurity, Wireless Sensor Network and the applications of Artificial Intelligence (AI). Her research on Mobile
E-Health Authentication Scheme for EHEART Application ischosen to be among the top three selected researches in AsiaPacific Economic Cooperation (APEC) Policy Partnership on
Science, Technology and Innovation in 2017.

A. Radwan et al. / Journal of Robotics, Networking and Artificial Life 7(2) 111–115

115

Dr. Mahmud Iwan Solihin

Dr. Hazry Desa

He is an Assistant Professor in Mechatronics
Engineering Department, specializedin applications of artificial intelligence/machine learning, optimizations, control systems, robotics and automation.
His current research interest is mainly on
applications of artificial intelligence (AI)and optimization algorithms in various
field including robotics, control systems,
spectroscopy applications, sensor networks, etc., toward sustainable Engineering development in the future.

He received his Bachelor of MechanicalEngineering from Tokushima University,
Japan. He was a Senior Design MechanicalEngineer in R&D Sony Technology
Malaysia in 1997. In 2001 he was employed
by Tamura Electronics Malaysia. He pursued his PhD at the Artificial Life andRobotics Laboratory, Oita University, Japan in 2003. He is a
Professor, Director of Center of Excellence for Unmanned
Aerial System at University of Perlis. He is a SMIEEE, MIETand registered as Professional Technologist.

Dr. Emily Leong Hung Yang

Dr. Muhammad Azizi Bin Azizan

She is currently a Lecturer in Departmentof Electrical and Electronic in UCSI
University in Malaysia. She is the Honorary
Secretary of IET Malaysia Local Networkfor 2018–2020. She graduated with adegree in Electrical Engineering with firstclass honour from University Malaya andsubsequently received her PhD in Engineering at UNITEN,
Malaysia. Her research works focus on IC microelectronics
enhance packaging, IR 4.0, wireless sensor network and imageprocessing. She also has over 9 years of experience in multinational semiconductor companies before joining academic line.

He is a Lecturer in Faculty of Engineering
Technology at uniMAP. He holds B.Scand M.Sc degree from UiTM. He is amember of (CIOB), (RISM), (MBOT) andcertified trainer of HRDF. His researchand teaching interests are management
issues in built environment/engineering
projects, sustainable and development.
He is Co-Founder of Haas Solutions Sdn
Bhd and holds the equity in Haas Engineering Sdn Bhd andBraintree Scientific Resources where the companies run thetechnology development activities eg. Drones, Data Processing,Data Mining and Laboratory Testing.

Dr. M. Rizon
He graduated Doctor of Engineering atDepartment of Computer Science andIntelligence System in Oita University,
Japan. He was a Professor of Biomedical
Technology in King Saud University,Saudi Arabia in 2010. He served atMIEC, Fuzhou University, China in 2019.
Currently, he is a Professor at Department
of Electrical and Electronics, UCSI University, Malaysia. He is amember of MIET and MIEM.