Autonomous Clustering Scheme for Removing the Effects of Heterogeneous Node Degrees in Ad Hoc Networks

Ryosuke Morita, Chisa Takano, Masaki Aida


In large scale mobile ad hoc networks (MANETs), it is effective to reduce the load of routing by introducing hierarchical routing, and it is conducted by clustering of nodes.
A clustering mechanism based on the diffusion equation is a typical autonomous clustering in MANETs, and gives appropriate clustering if all the node degrees are uniform.
However, node degrees in MANETs are heterogeneous in general, the fact causes the difference in the strength of diffusion effect.
This difference causes that the position of cluster head tends to be around the boundary of networks and degrade battery efficiency of nodes.
In this paper, by introducing an asymmetric diffusion depending on node degree, we propose a new clustering method independent of heterogeneity of node degrees.
We show that the proposed method has efficient characteristics for battery consumption.
In addition, we show the comparison of the proposed method with the conventional method with respect to the efficiency of routing.


Belding-Royer, E. M. (2002). Hierarchical routing in ad hoc mobile networks. Wireless Communications and Mobile Computing, 2(5), 515–532

Clark, B.N., Colbourn, C.J., Johnson, D.S. (1990). Unit disk graphs. Discrete mathematics, 86(1-3), 165–177

Clausen, T., Jacquet, P. (2003). Optimized link state routing protocol (OLSR) (No. RFC 3626)

Distributed Control and Hierarchical Structure in Information Networks. (2015). Corona Publishing Co. Ltd. (in Japanese)

Kakuda, Y., Ohta, T., Fujimoto, M., Oda, R. (2004). A Class of Hierarchical Routing Protocols Based on Autonomous Clustering for Large Mobile Ad Hoc Networks. IEICE transactions on communications, 87(9), 2500

Morita, R., Takano, C., Aida, M.(2016). Autonomous clustering scheme for removing the effects of heterogeneous node degree in ad hoc networks. IEICE Information and Communication Technology Forum

Ohta, T., Fujimoto, M., Inoue, S., Kakuda, Y. (2002). Hi-TORA: a hierarchical routing protocol in ad hoc networks. In High Assurance Systems Engineering, 2002. Proceedings. 7th IEEE International Symposium on (pp. 143–148). IEEE

Perkins, C.E. (2001). Ad hoc networking (Vol. 1). Reading: Addison-wesley

Perkins, C., Belding-Royer, E., Das, S. (2003). Ad hoc on-demand distance vector (AODV) routing (No. RFC 3561)

Takano, C., Masaki, A.I.D.A., Murata, M., Imase, M. (2012). Proposal for autonomous decentralized structure formation based on local interaction and back-diffusion potential. IEICE transactions on communications, 95(5), 1529–1538


  • There are currently no refbacks.