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

StA=σ(VDAB,VDAB,...,VDAB)

1

2

m

the most stable node among its neighborhood. Hence, it has the greatest potential to be a real group leader in real life scenarios.

Definition 5: Estimated Mean Distance (EMD) for cluster, C1, indicates the mean distance from each neighbor to the 3.3 Merging Stage

After the discovery stage, all nodes are covered by two-hop clusters. There are two cases that may initiate a merging process: clusterhead, CH1 of cluster, C1. The EMD is calculated as follows:

EMDC=µ(E[DCH1

N1

],E[DCH1

N2

],...,E[DCH1

Nm

])

1

3.2 Discovery Stage

This is an initial setup stage for two-hop clusters when the network is first initialized. All nodes periodically broadcast Hello messages, including their local stability value (initialized to infinity at the beginning of operation). Each node measures the received signal strength of every received Hello message and estimates the distance with each neighbor. After receiving at least two successive Hello messages, each node calculates relative mobility with its neighbor at time t using equation in Definition 3. After a discovery period, TD, each node assumes that it has the complete knowledge of its neighborhood. Then it computes its local stability value using equation in Definition 4. Then, it broadcasts Hello messages with the computed local stability value. Thus, each node knows the local stability of their neighbors. After an assignment period, TA, each node compares its own local stability value with those of its neighbors. If a node has the lowest value of local stability among all its neighbors, it assumes the status of a clusterhead. Its local stability value becomes group stability (GS).

Then, the clusterhead computes EMD with respect to all cluster members (one-hop neighbors of clusterhead). The EMD is computed to capture another characteristic of the network if the nodes are moving in groups. This characteristic is suggested by Reference Point Group Mobility (RPGM) model[10]. The RPGM model suggested that a group center is used to characterize the movement of its corresponding group members, including their direction, speed, and distance from group center. This is similar to the real life group communication in which group leader guides the movement of its group members. Therefore, group members will not move too far away from the group leader. Their movement area is usually bounded. EMD is used as one of the metrics in the merging process to allow a new cluster member to join the cluster.

If a cluster member is able to hear hello messages from another node from another cluster, it assumes the role of a gateway. Otherwise, it declares itself to be a cluster member. If two neighboring nodes in non-clustered state have the same value of local stability, the clusterhead assignment is deferred for a back-off period. The local stability will be recomputed at the end of back-off period. This is to ensure the clusterhead is

a) A non-clustered node requests to join the neighboring

clusters.

b) Two neighboring gateways request to merge their clusters. In the first case, a non-clustered node initiates the merging process. In the second case, two neighboring gateway nodes, G1 and G2 from C1 and C2 respectively, which are in transmission range of each other, initiate the merging process. Nodes initiating merging process start collecting samples for estimated distance between them. From the samples of estimated distances, they compute mean of estimated distance, E[DG1G2], and variation of distance over time, VDG1G2. Apart from this, they also calculate their relative mobility with respect to each other. To be successfully merged, both gateway nodes must fulfill the following two criteria at the end of sampling period, TS:

1) VDG1G2 ≤ min{StC1, StC2}, and

2) µ(E[DG1G2]) ≤ max{EMDC1, EMDC2}

The first criterion ensures that the variation of estimated distance between two merging nodes is less than or equal to the minimum value of group stability among two clusters. This indicates that the link between two nodes is at least as stable as other links in one of the clusters which is more stable. The second criterion tells us that the distance between two nodes conforms to the distance characteristic of the larger cluster. Therefore both clusters have higher probability to be originated from the same group of real life situation as suggested in RPGM. In most of the group communication applications, members belong to the same group tend to remain in each other transmission ranges over time by maintaining a constant distance from group leader.

3.4 Maintaining Stage

We first consider two cases that may cause topology changes in MANET and thus invoke cluster maintenance stage:

1) A node switches on and joins the network. 2) A node switches off and leaves the network.

When a node switches on, it will initiate the merging process in the same manner as described in Section 3.3. It checks all the links with its neighboring nodes and collects samples for estimated distance from each neighbor. Then it computes the variation of distance over time, VD, with each neighbor. At the end of sampling period, it chooses the neighbor with lowest VD, and joins its cluster. When a node switches off and the node is a clusterhead, this will cause its cluster members to lose the clusterhead and fail to

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 …… 此处隐藏：6746字，全部文档内容请下载后查看。喜欢就下载吧 ……