Multi-hop clustering based on neighborhood benchmark in mobile ad-hoc networks

ABSTRACT

Large-scale mobile ad-hoc networks require flexible and stable clustered network structure for efficient data collection and dissemination. In this paper, a scheme is presented to construct multi-hop clusters with balanced sizes, based on the neighborhood benchmark (NB) which quantifies the connectivity and link stability of mobile nodes. By exploiting autonomous clusterhead selection and a specialized handshake process with the clusterheads, the nodes with highest NB scores are selected as clusterheads and all the clusters constructed are connected. The deviation of cluster sizes is kept small using a partial probability-based approach. Our scheme generates highly stable multi-hop clusters with low overhead, and provides the flexibility of controlling the cluster radius adaptively for various network applications.

References

1. E. M. Belding-Royer, "Hierarchical routing in ad-hoc mobile networks", Wireless Communications and Mobile Computing, vol. 2(5), 2002, pp. 515--532.
2. J. Yu and P. Chong, "A survey of clustering schemes for mobile ad hoc networks", IEEE Communication Surveys & Tutorials, vol. 7(1), 2005, pp. 32--48.
3. A. Ephremides, J. E. Wieselthier, and D. J. Baker, "A design concept for reliable mobile radio networks with frequency hopping signaling", Proc. IEEE, vol. 75(1), 1987, pp. 56--73.
4. J. Wu, and H. Li, "On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks", Proc. 3rd Int'l Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M), 1999, pp. 7--14.
5. Y.-Z. Chen, and A. Liestman, "Approximating Minimum Size Weakly- Connected Dominating Sets for Clustering Mobile Ad Hoc Networks", Proc. MobiHoc, 2002, pp. 165--172.
6. C.-C. Chiang, et al., "Routing in Clustered Multihop Mobile Wireless Networks with Fading Channel", Proc. IEEE Singapore International Conference on Networks (SICON), 1997, pp. 197--211.
7. A. D. Amis, et al., "Max-min D-cluster formation in wireless ad hoc networks", Proc. IEEE INFOCOM, 2000, pp. 32--41.
8. J. T. Tsai, and M. Gerla, "Multicluster, Mobile, Multimedia Radio Network", ACM/Kluwer Journal of Wireless Networks, vol. 1(3), 1995, pp. 255--265.
9. M. Chatterjee, S. K. Das and D. Turgut, "WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks", Journal of Cluster Computing, vol. 5(2), 2002, pp. 193--204.
10. L. Ramaswamy, B. Gedik, and L. Liu, "A Distributed Approach to Node Clustering in Decentralized Peer-to-Peer Networks", IEEE Trans. on Parallel and Distributed Systems, vol. 16(9), 2005, pp. 814--829.
11. A. McDonald, and T. Znati, "A mobility-based framework for adaptive clustering in wireless ad hoc networks", IEEE Journal on Selected Areas in Communications, vol. 17(8), 1999, 1466--1487.
12. B. An and S. Papavassiliou, "A Mobility-based Clustering Approach to Support Mobility Management and Multicast Routing in Mobile Ad-hoc Wireless Networks", Int'l Journal of Network Management, vol. 11(6), 2001, pp. 387--395.
13. D. Kim, S. Ha, and Y. Choi, "k-hop cluster-based dynamic source routing in wireless ad-hoc packet radio networks", Proc. IEEE Vehicular Technology Conference (VTC), 1998, pp. 224--228.
14. F. G. Nocetti, J. S. Gonzalez, and I. Stojmenovic, "Connectivity based k-hop clustering in wireless networks", Telecommunication Systems, vol. 22(1--4), 2003, pp. 205--220.
15. J. Wu, and W. Lou, "Forward node set based broadcast in clustered mobile ad hoc networks", Wireless Communications and Mobile Computing, vol. 3(2), 2003, pp. 155--173.

• Networks

  • Network types

• Software and its engineering

  • Software organization and properties

    • Software system structures