Mobility-based d-Hop Clustering Algorithm for Mobile Ad Hoc

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

Mobility-based d-Hop Clustering Algorithm for Mobile Ad Hoc Networks

Inn Inn ER2,1 Winston K.G. Seah1,2{stuerii, winston}@i2r.a-star.edu.sg

Institute for Infocomm Research

Agency for Science Technology and Research

Singapore

1

2

Department of Computer Science

School of Computing

National University of Singapore

Abstract- This paper presents a mobility-based d-hop clustering algorithm (MobDHop), which forms variable-diameter clusters based on node mobility pattern in MANETs. We introduce a new metric to measure the variation of distance between nodes over time in order to estimate the relative mobility of two nodes. We also estimate the stability of clusters based on relative mobility of cluster members. Unlike other clustering algorithms, the diameter of clusters is not restricted to two hops. Instead, the diameter of clusters is flexible and determined by the stability of clusters. Nodes which have similar moving pattern are grouped into one cluster. The simulation results show that MobDHop has stable performance in randomly generated scenarios. It forms lesser clusters than Lowest-ID and MOBIC algorithm in the same scenario. In conclusion, MobDHop can be used to provide an underlying hierarchical routing structure to address the scalability of routing protocol in large MANETs.

Keywords: cluster, mobility-based clustering, mobile ad hoc networks, MANET, mobility pattern.

1. Introduction

Mobile ad hoc network (MANET) consists of a number of wireless hosts that communicate with each other through multi-hop wireless links in the absence of fixed infrastructure. They can be formed and deformed spontaneously at anytime and anywhere. Some envisioned MANETs, such as mobile military networks or future commercial networks may be relatively large (e.g. hundreds or possibly thousands of nodes per autonomous system). The need to store complete routing details for an entire network topology raises scalability issue. The flat hierarchy adopted by most of the existing MANET routing protocols may not be able to support the routing function efficiently since their routing tables could grow to an immense size if each node had a complete view of the network topology. Therefore, clustering algorithms are proposed in MANETs to address scalability issue by providing a hierarchical network structure for routing.

Clustering algorithms can be performed dynamically to adapt to node mobility[2]. MANET is dynamically organized into groups called clusters to maintain a relatively stable

effective topology [1]. By organizing nodes into clusters, topology information can be aggregated. This is because the number of nodes of a cluster is smaller then the number of nodes of the entire network. Each node only stores fraction of the total network routing information. Therefore, the number of routing entries and the exchanges of routing information between nodes are reduced[3]. Apart from making large networks seem smaller, clustering in MANETs also makes dynamic topology appear less dynamic by considering cluster stability when they form[2]. Based on this criterion, all cluster members that move in a similar pattern remain in the same cluster throughout the entire communication session. By doing this, the topology within a cluster is less dynamic. Hence, the corresponding network state information is less variable[3]. This minimizes link breakage and packet loss.

Clustering algorithm in MANETs should be able to maintain its cluster structure as stable as possible while the topology changes[1]. This is to avoid prohibitive overhead incurred during clusterhead changes. In this paper, we propose a mobility-based d-hop clustering algorithm (MobDHop) that forms d-hop clusters based on a mobility metric suggested by Basu et al.[8]. The formation of clusters is determined by the mobility pattern of nodes to ensure maximum cluster stability. We observe that mobile users in MANET may move in groups. This is known as group mobility[10]. Mobile hosts may be involved in team collaborations or activities. They may have a common mission (save victims that are trapped in collapsed building), perform similar tasks (gather information of threats in a battlefield) or move in the same direction (rescue team designated to move towards east side of disaster struck area). Therefore, our algorithm attempts to capture group mobility and uses this information to form more stable clusters.

MobDHop, a distributed algorithm, dynamically forms stable clusters which can serve as underlying routing architecture. First, MobDHop forms non-overlapping two-hop cluster like other clustering algorithms. Next, these clusters initiate a merging process among each other if they could listen to one another through gateways. The merging process will only be successful if the newly formed cluster achieves a required level of stability. As mentioned, most of the existing clustering algorithms form two-hop clusters which may not be too useful in very large MANETs. Therefore, MobDHop is designed to form

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