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
receive cluster advertisements for a predefined period. The immediate neighbors of the clusterhead will initiate the neighbors. Therefore, clusters are less dynamic and the number of clusterheads changes also decreases.
discovery process as described in Section 3.2 in which a new clusterhead will be elected. The information of the new clusterhead will then be propagated to other cluster members, which are further away from it. However, during the clusterhead election period, other cluster members which are at least 2 hops away from the old clusterhead may detect the loss of clusterhead and decide to join neighboring cluster if the merging criteria specified in Section 3.3 can be met. If a node found itself in non-clustered state, it will initiate merging with neighboring clusters whenever possible. Otherwise, it will declare itself to be a clusterhead of a one-node cluster. From time to time, it will try to merge with other clusters if possible.
4. Simulation Results and Discussions
The performance of MobDHop is evaluated via simulations using NS-2 with CMU wireless extensions [12]. The scenarios were generated with input parameters as listed in Table 1, such as network size, speed, transmission range, broadcast interval, clusterhead contention interval and simulation time. The movement of mobile nodes is randomly generated and continuous within the whole simulation period. We implemented MobDHop as described in Section 3. The local stability value, group stability value, node status, node clusterhead id, and cluster EMD are added into “Hello” messages. “Hello” messages have been widely used in on-demand routing protocols to maintain neighbor connectivity. Each node broadcasts “Hello” messages at certain broadcast interval to tell the neighbors of its existence. MobDHop does not use additional control packets for information exchange to form or maintain clusters.
Figure 2 and 3 show the performance of MobDHop for MANETs which are different in number of nodes and transmission ranges. The mobile nodes are moving continuously at 20m/sec throughout the entire network simulation period (300 seconds). We note that the average number of clusters is relatively high when the transmission range is small (10 - 20 m). For small ranges, most nodes tend to be out of each other’s transmission range and the network may become disconnected. Therefore, most nodes form one-node cluster, which only consists of itself. Due to our algorithm design, which require one-node clusters to attempt to merge with neighboring clusters whenever possible, clusterhead will switch their status to non-clustered state in order to merge with their neighbors (if any). This causes the high rate of clusterhead changes in disconnected networks. However, we argue that this will not affect network performance as this will only occur when the network is disconnected (A disconnected network is unable to function too). When transmission range increases, more nodes can hear each other. The average number of clusters formed decreases and the clusters become larger in size. Since the transmission range is large, mobile nodes tend to remain in the range of their
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