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
where Pr = received power, Pt = transmitted power, Gt = antenna gain of the transmitter, Gr = antenna gain of the receiver, λ = wavelength (c/f), and d = distance.
This shows the familiar inverse square-law dependence of received power with distance, i.e. Pr α 1/d2. Therefore, we derive the estimated distance between two nodes from the above equation based on received signal strength. In real world scenario, it may not be possible to obtain an exact calculation of the physical distance between two nodes from the measured signal strength. However, MobDHop does not depend on accurate estimation of distances between two nodes to operate correctly. Instead, we observe the variation of the estimated distances (in other words, fluctuation of the received signal strength) between two nodes over time. From the series of distance variations, we use statistical testing to predict relative mobility pattern between two nodes. We intuitively conclude that two nodes are stably-connected if the received signal strength between them varies negligibly over time. If two nodes are moving together at a similar speed towards the same direction, the variation of their received signal strength should be very small. This serves as one of the metrics we used to group the nodes into its respective cluster.
Based on the above justification, we will not use complex calculation in MobDHop in order to obtain accurate physical distance. Instead we use the received signal strength measured at the arrival of every packet to estimate the distance from one node to its neighbor node. The stronger the received signal strength, the closer the neighbor node. It is important to know that the “closeness” between two nodes is not necessarily measured by their absolute or physical distance. For example, node A may be very close to node B. However, it runs out of energy and transmits packets at lower power. In this case, it behaves like a distanced node from node A. Therefore, absolute distance may not be useful in predicting link stability in this case.
Figure 1. Relative Mobility
Measured signal strength of successive packets is used to
estimate the relative mobility between two nodes. We calculate the difference of estimated distance from a neighboring node at two successive time moments. The difference indicates the pair-wise relative mobility as shown in Figure 1. If the new distance
is larger than the old distance, the neighboring node is moving
away from the measuring node. We group the nodes into two-hop clusters based on their relative mobility in the first stage. Next, we expand the cluster by merging individual nodes with two-hop clusters or merging two or more two-hop clusters based on the previously described metric, i.e. the variation of estimated distance between gateway nodes. Before introducing MobDHop, we give a brief introduction to different terms and metrics used in MobDHop.
3.1 Preliminary Concepts
A node may become a clusterhead if it is found to be the most stable node among its neighborhood. Otherwise, it is an ordinary member of at most one cluster. When all nodes first enter the network, they are in non-clustered state. A node that is able to listen to transmissions from another node which is in different cluster is known as a gateway. We formally define the following terms: (1) estimated distance between nodes, (2) relative mobility between nodes, (3) stably-connected node pair, (4) local stability, and (5) estimated mean distance.
Definition 1: Estimated distance between node A and B, E[DAB], is calculated as below.Please note that this formula is not aimed to obtain exact physical distance between two nodes. Instead, it is an approximation to show the “closeness” of two nodes.
E[Dk
AB]=
, where k is a constant Pr
Definition 2: Relative mobility between nodes A and B, MrelAB
, indicates whether they are moving away from each other, moving closer to each other or maintain the same distance from each other. To calculate relative mobility, we compute the difference of the distance at time, t and the distance at time, t - 1. Relative mobility at node A with respect to node B at t is calculated as follows:
Mrel[DtDt 1AB=EAB] E[AB]
Definition 3: The variation of E[DAB] over a time period, T, VDAB, is defined as the changes of estimated distances between node A and B over a predefine time period. Let’s consider node A as measuring node. Node A has a series of estimated distance values from node B measured at certain time interval for n times, E[DAB]={E[DAB]t, t = 0, 1, 2, … , n}. Therefore we calculate VDAB as the standard deviation of distance variation as follows:
VDAB=σ(|E[DAB]1 E[DAB]0|,
|E[DAB]2 E[DAB]0|,...,|E[DAB]n E[DAB]0|)
Definition 4: Local stability at node A, StA, represents the degree of stability at node A with respect to all its neighbors. Local