Mobility-based d-Hop Clustering Algorithm for Mobile Ad Hoc(4)

We also compare the performance of MobDHop with the Lowest-ID algorithm and MOBIC in a 50-node MANET under constant mobility (20m/sec). In Figure 4, we note that there is a small difference between Lowest-ID and MOBIC with respect to the average number of clusters formed. This is because both algorithms are variations of a local weight based clustering technique that forms two-hop clusters. MobDHop forms less clusters in the similar scenario since it forms variable-diameter clusters based on node mobility pattern. This is one of the desirable properties in clustering algorithm especially when the scalability is the main concern.

Table 1. Simulation Parameters for MobDHop Value in Simulation

N Number of Nodes 25, 50, 75, 100 m x n Network Size 500 mSpeed 20 m/sec

node movement

Tx Transmission Range 10 m – 125 m PT Pause Time 0 sec TD Discovery Interval BI * 10 TA Assignment Interval BI * 2 TM Merge Interval BI * 5 TC Contention Period

BI * 2 S Simulation Time 300 sec

100

80s

retsulC60

fo .oN 40

gvA20

4080

120

Transmission Range (m)

Figure 2. Average number of clusters

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.