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

levels of successive transmissions between a pair of nodes is

used to compute the relative mobility between neighboring nodes, which determines the ALM of each node.

All of the above algorithms create two-hop clusters in MANETs. They are more suitable for dense MANETs in which most of the nodes are within direct transmission range of clusterheads. However, these algorithms may form a large number of clusters in relatively large and sparse MANETs. Therefore, two-hop clusters may not be able to achieve effective topology aggregation. . Amis et al. generalized the clustering heuristics so that an ordinary node can be at most d hops away from its clusterhead[9]. This algorithm allows more control and flexibility in the determination of clusterhead density. However, clusters are formed heuristically without taking node mobility

and their mobility pattern into consideration. McDonald and Znati[2] designed a (α,t)-clustering algorithm that adaptively

changes its clustering criteria based on the current node mobility. This algorithm determines cluster membership according to a cluster’s internal path availability between all cluster members over time. 3.Mobility-based d-hop Clustering Algorithm

A successful dynamic clustering algorithm should achieve a stable cluster topology with minimal communications overhead and computational complexity [2]. The efficiency of the algorithm is also measured by the number of clusters formed [11]. Therefore, the main design goals of our clustering algorithm are as follows:

1. The algorithm minimizes the number of clusters by considering group mobility pattern. 2. The algorithm must be distributed and executed asynchronously. 3. The algorithm must incur minimal clustering overhead, be it

cluster formation or maintenance overhead. 4. Network-wide flooding must be avoided.

5. Optimal clustering may not be achieved, but the algorithm must be able to form stable clusters should any exists. Before introducing MobDHop, we first make a few

assumptions on the network:

1. Two nodes are connected by bi-directional link (symmetric

transmission).

2. The network is not partitioned.

3. Each node can measure its received signal strength.

Through periodic beaconing or hello messages used in some routing protocols, a mobile node can estimate its distance to its neighbor based on the measured received signal strength from that particular neighbor. In the Friss transmission equation, the received power over a point-to-point radio link is given by: 2

Pλr=Pt*Gt*Gr* (4*π*d)2

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