Dynamic Algorithms for Efficient and Robust Clustering in Ad hoc Networks
Baras, John S.
MetadataShow full item record
scenarios may appear both in the military and the commercial world. Even though there is much advancement in the area of these networks, the main drawback is that ad hoc networks do not scale well because the existing protocols (e.g., MAC, routing, security) cannot tolerate the dynamics of these networks when their size becomes larger than few decades of nodes(i.e. O(10)). A remedy to this problem is to apply these protocols in hierarchical manner. The hierarchy generation in these dynamic environments can be advantageous since the numerous topological changes can be tolerated easier and the various protocols can perform better when dealing with smaller groups of nodes. This division greatly reduces overall overhead (e.g., routing overhead with n nodes goes from O(n2) to O(nlogn)) and allows protocols to be tuned to more homogenous conditions .On the other hand, hierarchy has to be generated carefully in order to be beneficial for the network otherwise it may harm it, because of the imposed maintenance overhead. Towards this objective we have to take into consideration the network environment and design appropriately the hierarchy generation algorithms. The weakness of the existing network clustering algorithms is that they do not take into consideration the dynamics of the network environment, so in cases of increased mobility their overhead may deteriorate network performance instead of improving it. In this paper we present a new class of clustering algorithms, which includes both a centralized and a distributed algorithm. The basic characteristic of these algorithms is that they take into consideration the network dynamics for the generation of robust and efficient clusters. The centralized algorithm generates optimal clusters but can be applied only in slow mobile networks. The distributed algorithm can be applied in highly mobile networks and even though the quality of clusters is lower than the centralized generated ones, the algorithm still presents better scalability and robustness characteristics from the existing distributed algorithms.