Mobility-based d-Hop Clustering Algorithm for Mobile Ad Hoc(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

d-hop clusters that are more flexible in cluster diameter. The diameter of clusters is adaptive to the mobility pattern of network nodes. MobDHop is simple and incurs as low overhead as possible. Information exchange during the formation of clusters, clusterhead changes and clusterhead handovers are kept to minimum. The remainder of this paper is organized as follows: We present an overview of clustering algorithms proposed for MANETs in Section 2. Next, details of MobDHop are presented in Section 3. Section 4 discusses our simulation results and analysis. Finally, we conclude in Section 5.

2. Related Work

A number of clustering algorithms have been proposed in literature such as Linked Cluster Algorithm (LCA)[4], Lowest-ID Algorithm (L-ID)[5], Maximum Connectivity Clustering (MCC)[6], Least Clusterhead Change Algorithm (LCC)[7], and MOBIC[8]. LCA[4] was developed for packet radio networks and intended to be used with small networks of less than 100 nodes. LCA organizes nodes into clusters on the basis of node proximity. Each cluster has a clusterhead, and all nodes

within a cluster are within direct transmission range of the

clusterhead. Gateways are nodes that are located in the overlapping region between clusters. Two clusters communicate with each other via gateways. Pair of nodes can act as gateways if there are no nodes in the overlapping region. LCA was later revised[5] to reduce the number of clusterheads. In the revised version of LCA, a node is said to be covered if it is in the 1-hop neighborhood of a node that has declared itself as clusterhead. A

node declares itself to be a clusterhead if it has the lowest id

among the non-covered nodes in its 1-hop neighborhood, known

as Lowest-ID algorithm.

Parekh suggested MCC in which the clusterhead election is based on degree of connectivity instead of node id[6]. A node is

elected as a clusterhead if it is the highest connected node in all of the uncovered neighboring nodes. This algorithm suffers from

dynamic network topology, which triggers frequent changes of

clusterheads. Frequent cluster reconfiguration and clusterhead

reselection incur prohibitive overhead.

LCC[7] is designed to minimize clusterhead changes. A

clusterhead change occurs when two clusterheads come within

range of each other, or a node becomes disconnected from any

cluster. When two clusterheads come into direct contact, one of

the clusterheads will give up its role. Some of the nodes in one cluster may not be members of the other clusterhead’s cluster. Therefore, one or more of those nodes must become a clusterhead. Such changes propagate across the network, causing a rippling effect of clusterhead changes. Basu et al.[8] propose a weight-based clustering algorithm, MOBIC, which is similar to L-ID. Instead of node ID, MOBIC uses a new mobility metric, Aggregate Local Mobility (ALM), to elect a clusterhead. The ratio between the received power

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库Mobility-based d-Hop Clustering Algorithm for Mobile Ad Hoc(2)在线全文阅读。