Abstract- This paper presents a mobility-based d-hop clustering algorithm (MobDHop), which forms variablediameter clusters based on node mobility pattern in MANETs. We introduce a new metric to measure the variation of distance between nodes over time in o
400
s
egn300
ahC daehr200
etsul Cfo .oN100
4080
120
Transmission Range (m)
Number of Clusterhead Changes
Figure 3. Number of clusterhead changes
50s
ret40
sulC fo r30
ebmuN20
egarevA10
4080
120
Transmission Range (m)
Figure 4. Comparisons between different clustering
algorithms in a 50-node MANET.
5. Conclusions
Clustering can provide large-scale MANETs with a hierarchical network structure to facilitate routing operations. In this paper, we proposed a distributed clustering algorithm which forms variable-diameter clusters that may change its diameter adaptively with respect to mobile nodes’ moving patterns. Inspired by Basu et. al[8], we proposed two mobility metrics based on the relative mobility concept: (1) variation of estimated distance between nodes over time and (2) estimated mean distance for cluster, in order to measure the stability of a cluster. These metrics are used to decide cluster memberships. Therefore, the formation of clusters in MobDHop is determined by the mobility pattern of nodes to ensure maximum cluster stability. To achieve the desired scalability, MobDHop forms variable-diameter clusters, which allows cluster members to be more than two hops away from their clusterhead. The diameter of clusters is dependent on the mobility behavior of nodes in the same cluster. As long as the nodes are moving towards the same direction in a stable behavior, they can be grouped into the same cluster. This is justified by the assumption of group movement, in which members of a group tend to move towards a similar destination in real-life scenarios.
We have simulated MobDHop and presented some preliminary results in Section 4. In conclusion, the performance of MobDHop is comparable to other existing algorithms. It also creates lesser and more stable clusters in order to achieve high scalability. The clusterhead change is relatively low. However, we will perform extensive simulation-based comparisons between existing clustering algorithms and MobDHop to evaluate different aspects of performance such as cluster stability, overhead consumption, latency and others. We may use other mobility models which are more realistic such as RPGM in our simulations. Finally, designing a multicast routing protocol which can work on-top of MobDHop in order to address scalability issues in MANET is part of our ongoing research.
References:
[1] C. R. Lin and M. Gerla. Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications, 15(7):1265-1275, Sept. 1997.
[2] A. B. McDonald and T. F. Znati. A mobility-based framework for adaptive clustering in wireless ad hoc networks. IEEE Journal on Selected Areas in Communications, 17(8):1466-1486, Aug. 1999.
[3] C. E. Perkins, editor. Ad Hoc Networking. Addison-Wesley, 2001.
[4] D. J. Baker and A. Ephremides. The architectural organization of a mobile radio network via a distributed algorithm. IEEE Transactions on Communications, 29(11):1694-1701, 1981. [5] A. Ephremides, J. Wieselthier, and D. Baker. A design concept for reliable mobile radio network with frequency hopping signaling. In Proceedings of IEEE 75, pages 56-73, 1987.
[6] A. K. Parekh. Selecting routers in ad hoc wireless networks. In
ITS, 1994.
[7] C.-C. Chiang, H.-K. Wu, W. Liu, and M. Gerla. Routing in clustered multihop, mobile wireless networks with fading channel. IEEE Singapore International Conference on Networks (SICON), pages 197-211, Apr. 1997.
[8] P. Basu, N. Khan, and T. D. C. Little. Mobility based metric for clustering in mobile ad hoc networks. Workshop on Distributed Computing Systems, pages 413-418, 2001.
[9] A. D. Amis, R. Prakash, T. H. P. Vuong, and D. T. Huynh. Max-min d-cluster formation in wireless ad hoc networks. In Proceedings of IEEE INFOCOM ’00, Vol. 1, pages 32-41, Mar. 2000.
[10] X. Hong, M. Gerla, G. Pei, and C. Chiang. A group mobility model for ad hoc wireless networks. In Proceedings of ACM/IEEE MSWiM, Seattle, WA, Aug.1999.
[11] F. G. Nocetti, J. S. Gonzalez, I. Stojmenovic, "Connectivity based k-hop clustering in wireless networks," Telecommunication Systems 22 (2003) 1-4, 205-220, 2003.
[12] K. Fall, and K. Varadhan, “The ns Manual,” http://www.isi.edu/nsnam/ns/, 2002.