Abstract

In this study we propose an efficient clustering protocol called AMHC used for resource discovery in large scale Mobile Ad hoc Networks (MANETs). AMHC is an Adaptive Multi-Hop Clustering generating several non-overlapping network localities (clusters) with explicit elected cluster-heads. Every cluster member is on average d hops away from its cluster-head, where d is an integer parameter for the protocol. The generated set of clusters are highly stable and has low restructuring frequency that takes into consideration the dynamic network topology due to nodes mobility and depleted energy. The head election process is a distributed process based on a node’s weight formula calculated by every node independently. The node’s weight involves the current energy level, the current neighborhood degree and distance (in number of hops) between the nominated head and the voting node. The cluster-head is responsible of coordinating intra-cluster and inter-cluster resource discovery activities. Inter-cluster communication is handled through gateway nodes which hear from more than one cluster and able to connect clusters with each other. The aim of AMHC is to identify all the possible gateways for creating highly fault-tolerant architecture. AMHC is an asynchronous, scalable and robust architecture capable of handling large amount of resource queries with high degree of power and communication efficiency. We conducted a comparative study using simulation to demonstrate AMHC’s efficiency and superiority against other recently proposed clustering algorithms in the literature. The comparison is based on: number of generated clusters, average cluster size, cluster stability and nodes re-affiliation. These results show a lot of promise for AMHC as efficient, energy-aware, load-balance and fault tolerant resource discovery architecture for large-scale MANETs.

Keywords:

Distributed algorithms, head-based non-overlapping clustering, mobile ad hoc networks, multi-hop clustering, network resource discovery,

References

1. Al-Ahmadi, S., A. Al-Dhelaan and N. Al-Hosini, 2011. New data gathering scheme for large scale wireless sensor networks. Proceeding of the 15th WSEAS International Conference on Computers, pp: 111-117.
   
2. Amis, A.D., R. Prakash, T.H.P. Vuong and D.T. Huynh, 2000. Max-min d-cluster formation in wireless ad hoc networks. Proceeding of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM, 2000). Tel Aviv, Israel, Mar. 26-30, pp: 32-41.
   CrossRef    
3. Baker, D. and A. Ephremides, 1981. The architectural organization of a mobile radio network via a distributed algorithm. IEEE T. Commun., 29(11): 1694-1701.
   CrossRef    
4. Basu, P., N. Khan and T.D.C. Little, 2001. A mobility based metric for clustering in mobile ad hoc networks. Proceedings of the 21st International Conference on Distributed Computing Systems (ICDCS 2001). Phoenix, Arizona, USA, pp: 413-418.
   CrossRef    
5. Chen, Y.P., A.L. Liestman and J. Liu, 2004. Clustering algorithms for ad hoc wireless networks. In: Pan, Y. and Y. Xiao (Eds.), Ad Hoc and Sensor Networks. Nova Science Publishers, Vol. 28.
   
6. Cheng, L., 2002. Service advertisement and discovery in mobile ad hoc networks. Proceeding of thestudyshop on Ad hoc Communications and Collaboration in Ubiquitous Computing Environments (CSCW 2002). New Orleans, Louisiana, USA, Nov. 16-20.
   
7. Das, B. and V. Bharghavan, 1997. Routing in ad-hoc networks using minimum connected dominating sets. Proceeding of the IEEE International Conference on Communications (ICC'97), Towards the Knowledge Millennium. Montreal, Que, June 8-12, pp: 376-380.
   CrossRef    
8. Edwards, W.K., 2006. Discovery systems in ubiquitous computing. IEEE Pervas. Comput., 5(2): 70-77.
   CrossRef    
9. Ephremides, A., J.E. Wieselthier and D.J. Baker, 1987. A design concept for reliable mobile radio networks with frequency hopping signaling. Proc. IEEE, 75(1): 56-73.
   CrossRef    
10. Er, I.I. and W.K.G. Seah, 2006. Performance analysis of mobility-based d-hop (MobDHop) clustering algorithm for mobile ad hoc networks. Comput. Networks, 50(17): 3375-3399.
    CrossRef    
11. Kawadia, V. and P. Kumar, 2003. Power control and clustering in ad hoc networks. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications, IEEE Societies (INFOCOM 2003). San Francisco California, USA, 30 March-3 April, pp: 459-469.
    
12. Lenders, V., M. May and B. Plattner, 2005. Service discovery in mobile ad hoc networks: A field theoretic approach. Perv. Mob. Comput., 1(3): 343-370.
    CrossRef    
13. Lin, C.R. and M. Gerla, 1997. Adaptive clustering for mobile wireless networks. IEEE J. Sel. Area. Comm., 15(7): 1265-1275.
    CrossRef    
14. Mian, A.N., R. Baldoni and R. Beraldi, 2009. A survey of service discovery protocols in multihop mobile ad hoc networks. IEEE Pervas. Comput., 8(1): 66-74.
    CrossRef    
15. Parekh, A.K., 1994. Selecting routers in ad-hoc wireless networks. Proceedings of the SBT/IEEE Intl Telecommunications Symposium, pp: 420-424.
    
16. Sailhan, F. and V. Issarny, 2005. Scalable service discovery for MANET. Proceeding of the 3rd IEEE International Conference on Pervasive Computing and Communications (PerCom, 2005), pp: 235-24.
    CrossRef    
17. Varshavsky, A., B. Reid and E. De Lara, 2005. A cross-layer approach to service discovery and selection in MANETs. Proceeding of the IEEE International Conference on Mobile Ad hoc and Sensor Systems Conference, pp: 446-454.
    CrossRef    
18. Wan, P.J., K.M. Alzoubi and O. Frieder, 2002. Distributed construction of connected dominating set in wireless ad hoc networks. Proceeding of the IEEE 21st Annual Joint Conference of the IEEE Computer and Communications Societies, (INFOCOM 2002), 3: 1597-1604.
    
19. Xu, K., X. Hong and M. Gerla, 2002. An ad hoc network with mobile backbones. Proceeding of the IEEE International Conference on Communications (ICC, 2002), 5: 3138-3143.
    
20. Yu, J.Y. and P.H.J. Chong, 2005. A survey of clustering schemes for mobile ad hoc networks. IEEE Commun. Surv. Tutorials, 7(1): 32-48.
    CrossRef    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.