Connectivity based k-hop clustering in wireless networks
Authors:
- F.G. NocettiFNF.G. Nocetti
- J.S. GonzalezJGJ.S. Gonzalez
- I. StojmenovicISI. Stojmenovic
- 1 October 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2450-2459
Abstract
In this paper we describe several new clustering algorithms for nodes in a mobile ad hoc network. We propose to combine two known approaches into a single clustering algorithm which considers connectivity as a primary criterion and lower ID as secondary criterion for selecting cluster heads. The goal is to minimize the number of clusters, which results in dominating sets of smaller sizes (this is important for applications in broadcasting and Bluetooth formation). We also describe algorithms for modifying cluster structure in the presence of topological changes. Next, we generalize the cluster definition so that a cluster contains all nodes that are at a distance of at most k hops from the cluster head. The efficiency of four clustering algorithms (k-lowestID and k-CONID, k=1 and k=2) is tested by measuring the average number of created clusters, the number of border nodes, and the cluster size in random unit graphs. The most interesting experimental result is stability of the ratio of the sum of CHs and border nodes in the set. It was constantly 60-70% for 1-lowestID and 46-56% for 1-ConID, for any value of n (number of nodes) and d (average node degree). Similar conclusions and similar number were obtained for k=2. We also proposed a unified framework for most existing and new clustering algorithms where a properly defined weight at each node is the only difference in the algorithm. Finally, we propose a framework for generating random unit graphs with obstacles.Keywords
This publication has 15 references indexed in Scilit:
- Internal nodes based broadcasting in wireless networks2005
- Distributed and mobility-adaptive clustering for multimedia support in multi-hop wireless networks2005
- A clustering scheme for hierarchical control in multi-hop wireless networks2002
- A access-based clustering protocol for multihop wireless ad hoc networksIEEE Journal on Selected Areas in Communications, 2001
- On calculating connected dominating set for efficient routing in ad hoc wireless networks1999
- Spine routing in ad hoc networksCluster Computing, 1998
- A cluster-based approach for routing in dynamic networksACM SIGCOMM Computer Communication Review, 1997
- An adaptive hierarchical routing protocolIEEE Transactions on Computers, 1989
- Future directions in packet radio architectures and protocolsProceedings of the IEEE, 1987
- A design concept for reliable mobile radio networks with frequency hopping signalingProceedings of the IEEE, 1987