To mimic the operations in fixed infrastructures and to solve the routing scalability problem in large Mobile Ad Hoc Networks (MANET), forming clusters of nodes has been proven to be a promising approach. However, when existing weighted clustering algorithms calculate each node’s weight, they either consider only one metric or rely on some metrics collected from extra devices. This often leads to a higher rate of re-clustering. This chapter presents a robust weighted clustering algorithm, called PMW (Power, Mobility and Workload), to form and maintain more stable clusters. In PMW, the weight of each node is calculated by its power, mobility and workload, which can be easily collected and computed locally and cover the major factors that cause re-clustering. Clustering overhead of PMW is analyzed. The simulation results confirm that PMW prolongs lifetime of MANETs and has a lower cluster head change rate and re-affiliation rate than other existing algorithms.
TopIntroduction
A mobile ad hoc network (MANET) is a collection of battery-powered mobile nodes (or hosts) connected by relatively lower bandwidth wireless links. Each node has an area of influence called cell, only within which others can receive its transmissions. Due to no fixed infrastructures, all nodes can move freely, the network topology may change rapidly and unpredictably over time, and nodes have to form their own cooperative infrastructures. Thus, each node operates as an autonomous end system and a router for others in the network.
A MANET is of interest because there is no prior investment for fixed infrastructures, it can be easily deployed in a short time, and end users can access and manipulate data anytime and anywhere. Examples of MANET applications (Chlamtac et al., 2003) include law enforcement operations, automated battlefield applications, natural disaster recovery situations where the communication infrastructures have been destroyed, self-organizing sensor networks for data collecting, interactive lectures or conferences for data exchanging without pre-installed infrastructures. However, these MANET applications cannot be realized without efficient routing protocols. Current routing protocols over the flat network structure, in which each node participates as a peer, acts as a router and maintains individual routes to other nodes (Shiflet et al., 2004), are either proactive or reactive. Proactive routing protocols store route information in tables and update them periodically, while reactive routing ones search the routes on demand by flooding neighbors with the route requests. However, when the network size is large or the mobility of nodes is high, both the routing protocols over the flat network structure cannot work efficiently (Hong et al., 2002).
One promising way that can solve the routing scalability problem is to divide a MANET into clusters first, and then develop a routing protocol on top of the clustered MANET. A clustered MANET consists of cluster heads and cluster members, where a cluster head (like a mobile support station in a cellular mobile network) manages its clusters, coordinates intra/inter-cluster communication and so on. A cluster member is a node that belongs to a cluster and is not a cluster head.
Many weighted clustering algorithms have been proposed to elect cluster heads, form clusters and maintain clusters (Basagni, 1999; Basu et al., 2001; Chatterjee et al., 2002; Kim, 2006; Liu et al., 2005; Sheu & Wang, 2006). However, when calculating the weight utilized to determine whether a node is eligible to be a cluster head, these algorithms either consider only one metric (like mobility or power of nodes) (Basu et al., 2001; Kim, 2006; Sheu and Wang, 2006) or rely on some metrics collected from extra devices (such as locations of nodes read from Global Positioning Systems) (Chatterjee et al., 2002). This often leads to a higher possibility of re-clustering and, consequently, quality of service cannot be provided.
This chapter presents a robust weighted clustering algorithm, called PMW (Power, Mobility, Power), to form and maintain more stable clusters in MANETs. In PMW, in order to take into account the major factors that frequently cause re-clustering and in order to avoid being dependent on any extra device, the weight of a node is calculated by three parameters: power, mobility and workload. The results of our simulation show that PMW balances the power usage, prolongs the lifetime of clustered MANETs and has a lower cluster head change rate and re-affiliation rate than MOBIC (Basu et al., 2001). The rest of this chapter is organized as follows. Section 2 reviews the related background. Section 3 presents our approach to build stable clusters based on power, mobility and workload. Section 4 analyzes the message overhead and time complexity of PMW. Section 5 evaluates PMW and MOBIC by using the NS-2 simulator. Section 6 discusses some direction of future research. Finally, Section 7 concludes the chapter.