Energy Balance Based Clustering Algorithm

Abstract: According to the shortcomings of clustering algorithms commonly seen in Ad Hoc Network, energy balance based clustering algorithm is proposed in this paper. Through the establishment of the clustering algorithm, the times of information interaction are reduced as much as possible, and the node with the largest energy is selected as cluster head for achieving energy conservation and keeping the cluster structure unchanging for the longest time.

Key words: Clustering Algorithm; Energy Balance; Mobile Ad Hoc Networks; Ad Hoc1. Introduction

Mobile Ad Hoc Network is also called as Ad Hoc network, which is composed by several wireless terminals that serve not only as the functions of a router and also as the functions of nodes. It features self-organization, multi-hop, and no support from backbone network. The structure of the first mobile AD hoc network is planar, in which all nodes are equivalent. That is, each node is with the functions of both router and terminal. The biggest advantage of this way is implementing to multiple paths between source nodes and destination nodes and reducing congestion. However, because Ad Hoc network has dynamic topology (random movement of nodes results in network access or exit), limited energy (power supply relies on batteries) and limited bandwidth, the problems such as large routing overhead, poor extendibility and complex mobile management can be caused when the number of nodes increases. Thus, the plane structure is only applicable to the Ad Hoc network with a few nodes, and relevant clustering algorithm is used for composing the hierarchical topological structure of the Ad Hoc network with great numbers of nodes. Through the clustering algorithm, a cluster is composed by a group of adjacent nodes. The nodes in the cluster own three identities (cluster head, cluster gateway, and cluster members). The communication between the members of the same cluster proceeds through cluster head; the communication between clusters is forwarded through gateway nodes. Compared with the plane structure, hierarchical topology owns many advantages such as powerful extendibility, cost reduction and control, easy-to-manage, and optimized bandwidth.

2. Commonly-seen Clustering Algorithms and Their Shortcomings

The goal of clustering algorithms is to establish a set of clusters by using simple and efficient algorithms as far as possible for covering the entire network. It is necessary for these clusters to possess good stability and anti-destroying ability, and simultaneously the number of the nodes of cluster head should be as less as possible under the allowable link capacity condition. The early typical clustering algorithms mainly included lowest-ID priority algorithm [1] and Max-Degree priority algorithm [2]. Both of them use a single factor in AD hoc network as the condition of selecting cluster head. If the ID with a small value is used by Lowest-ID priority algorithm as cluster head and the node with the maximum connection degree is used by Max-Degree priority algorithm as cluster head, the ultimate result will be that network performance is poor and also lacks fairness. Afterwards, these two basic algorithms are improved by researchers, such as the weight based distributed clustering algorithm (DCA) [3]. In DCA, it is assumed that each node only has a weight, the factors such as node connection degree and ID are comprehensively considered by the weight, and finally the node with the maximum weight among the neighbors is taken as cluster head. However, unfortunately, the calculation of the weight was not discussed in depth. In addition, there are some algorithms such as node location prediction based clustering algorithm [4], node mobility based clustering algorithm, link stability based clustering algorithm, pattern recognition based clustering algorithm, in which the selection of their cluster heads has no tie with ID or the maximum connection degree. However, for many reasons such as necessary extra equipment, higher requirements on application environment, extremely- complex implementation, ideal effects have not been achieved by these algorithms. Therefore, it is necessary to further improve these algorithms.