Mobility Based Clusterhead & Gateway Selection Algorithm in MANET

Mobility Based Clusterhead & Gateway Selection Algorithm in MANET

Sapna Pal, S. P. Singh

Madan Mohan Malaviya Engineering College, Gorakhpur, India

Abstract

Mobile computing has achieved lots of attention in recent times as a variety of mobile terminals & convenient wireless connections are available. A Mobile Ad Hoc Network (MANET) is a collection of mobile nodes which interact over bandwidth confined. Because of this the network topology can change quickly and uncertain over time, each node must united within a communication routing protocol that make easier network discovery, assures message delivery, and detects failed message delivery attempts. The movement of the mobile nodes in MANET is arbitrary and hence the topology of the network may change rapidly and randomly at unpredictable times which in result may contain both unidirectional as well as bidirectional links. This unpredictable behavior of nodes causes the instability in the cluster life. The most of the clustering schemes assume low mobility which cannot reflect the distinct dynamic character of MANETs. Mobility is a crucial characteristic of a cluster in the mobile ad hoc network especially at the time of cluster formation and clusterhead election.

1. Introduction

   All manuscripts must be in English. These guidelines include complete descriptions of the fonts, spacing, and related information for producing your proceedings manuscripts. Mobile ad hoc networks consist of mobile nodes which can communicate with each other in a peer to peer fashion without any fixed infrastructure such as access point or base station. Clustering is an approach for assemble mobile nodes in some groups for effective data forwarding. Most of the clustering approaches proposed in the literature primarily focus on the algorithmic aspects of clustering without considering the practical implementation issues. In this paper, a framework for mobility aware clustering in Ad hoc mobile networks has been proposed. This approach addresses the problem of clustering in a medium access control framework and enables proactive and energy efficient clustering by exploiting the node mobility information. A node with lower mobility is assigned higher weight value. Choosing

   low mobile nodes to act as cluster heads ensure better cluster stability as head nodes rarely move. A node having the lowest mobility among its neighbors becomes the cluster head. Selection of low mobile nodes as the cluster heads ensures better cluster stability.

   Routing is challenging in Mobile Ad hoc Network due to the dynamic nature of the network topology because of mobility characteristics of nodes. There is a well-known method to reduce the amount of routing data exchanges and accordingly, to save the communication bandwidth and energy that method is clustering. Most clustering approaches for mobile ad hoc networks select a subset of nodes in order to form a network backbone that supports control functions. A set of the selected nodes are called clusterheads and each node in the network is associated with one. Clusterheads are connected with one another directly or through gateway nodes. The union of gateway nodes and clusterheads form a connected backbone. This connected backbone helps simplify functions such as channel access, bandwidth allocation, routing power control and virtual-circuit support.

   Clustering is the process of dividing the nodes of a network into a few organized partitions called clusters. Clustering creates a backbone network of nodes, providing scalability for large networks, and stability for dynamic networks [22].

   The objectives of clustering are to minimize the total transmission power aggregated over the nodes in the selected path, and to balance the load among the nodes for prolonging the network lifetime. Clustering is a sample of layered protocols in which a network is composed of several clusters of mobile nodes.

   In a cluster-based environment, there are some nodes in the network called cluster-heads which have high processing speed and battery power than the other nodes. These cluster-heads are responsible for cluster management and maintenance of the network.

   A cluster-head allocates the resources to all the nodes that belong to its cluster. In addition to controlling and managing its own cluster, it also communicates with other clusters. It maintains the information about every node within its cluster. Therefore, choosing the appropriate number of cluster-heads that can use the network resources

   efficiently and adapt to the changing network conditions in MANETs is a challenging task. Clustering is a method of organizing things into meaningful groups with respect to their similarities. Elements in a group are similar to each other but are different from other groups.

   Nodes are mobile and can be connected dynamically in an arbitrary manner. Links of the network vary timely and are based on the proximity of one node to another node. The movement of the mobile nodes in MANET is arbitrary and hence the topology of the network may change rapidly and randomly at unpredictable times which in result may contain both unidirectional as well as bidirectional links. This unpredictable behavior of nodes causes the instability in the cluster life.

   The most of the clustering schemes assume low mobility which cannot reflect the distinct dynamic character of MANETs. Mobility is characterized as an inherent phenomenon of MANETs; hence, discussing clustering algorithms by assuming low mobility becomes meaningless. The mobility characteristic of node in MANET is considered as a metric for cluster construction. In mobility aware clustering, cluster architecture is determined by the mobility behavior of mobile nodes. Mobility of nodes in mobile Ad hoc network is one of important issues that are considered in the proposed work.

   Due to mobility of the network, the nodes can go outside the transmission range of their cluster- head and move into another cluster thus changing their neighborhood. This can change the number of clusters and number of nodes in a cluster but this does not result in a change of the dominant set at all. Clustering of nodes in MANETs is one of the biggest challenges. Finding the optimal number of clusters that cover the entire network becomes essential and an active area of research. Although, several authors have proposed different techniques to find the optimal number of clusters, none of them addresses all the parameters of a mobile ad hoc network. Clustering has several advantages in MANETs. The system performance can be improved by allowing the reuse of resources due to clustering because each group of nodes can communicate with each other without affecting the other groups. Secondly, it optimally manages the network topology by dividing the task among specified nodes called cluster-heads, which is very useful for network management and routing.

   There are some requirements of clustering in MANETs. The clustering algorithm must be distributed, since every node in the network has only local knowledge and communicates outside its group only through its cluster-head as in case of cluster-based routing. The algorithm should be robust as the network size increases or decreases; it

   should be able to adapt to all the changes. The clusters should be reasonably efficient i.e. the selected clusterheads should cover a large number of nodes as much as possible.

   Nodes in a cluster must be one of the following types [23]:

   1. Clusterhead (CH): An elected node that acts as the local controller for the cluster. The clusterhead's responsibilities may include: routing, relaying of inter-cluster traffic from cluster members, scheduling of intra-cluster traffic, and channel assignment for cluster members.

   2. Cluster Member: A normal node belonging to a cluster. Cluster members usually do not participate in routing, and they are not involved in inter-cluster communication.

   3. Gateway Node (CG): Cluster Gateway is a border node which is used to convey the routing information from one cluster to another. The clusterheads and gateway nodes form the backbone network. Gateway nodes selected among the border nodes. A border node is a mobile node which has at least one neighbor belonging to a different cluster. Border nodes are at the perimeter of the clusters. Gateway nodes are those nodes in a non- clusterhead state located at the periphery of a cluster. These types of nodes are called gateways because they are able to listen to transmissions from another node which belongs to a different cluster. To accomplish this, a gateway node must have at least one neighbor that is a member of another cluster.

2. Proposed Algorithm

   All printed material, including text, illustrations, and charts, must be kept within a print area of 6-1/2 inches (16.51 cm) wide by 8-7/8 inches (22.51 cm) high. Do not write or print anything outside the print area. All text must be in a two-column format. Columns are to be 3-1/16 inches (7.85 cm) wide, with a 3/8 inch (0.81 cm) space between them. Text must be fully justified.

   A format sheet with the margins and placement guides is available as both Word and PDF files as

   <format.doc> and <format.pdf>. It contains lines and boxes showing the margins and print areas. If you hold it and your printed page up to the light, you can easily check your margins to see if your print area fits within the space allowed. Various algorithms for clustering have been proposed in the literature for stable and mobile networks. The variety of the algorithm for a particular network type strongly depends on the dynamic character of the network. Whereas in fixed networks a centrally structured and rather static network organization is sufficient, in highly dynamic ad hoc networks a completely distributed and adaptive clustering protocol is essential.

   The previous clustering algorithms have a common assumption that during the set up time nodes do not move they are being grouped into cluster. In this paper, mobility of nodes in MANET is considered as a basic metric. So nodes are assumed mobile at every time even during the set up time they are being grouped into cluster. In the proposed algorithm, selection process of clusterhead and gateway will improve the stability of cluster and avoid reclustering. The clusterhead selection algorithm is only invoked based on node mobility.

   The proposed solution is an enhancement in Distributed Group Mobility Adaptive (DGMA) Clustering Algorithm. This Enhanced Distributed Group Mobility Adaptive (EDGMA) Clustering Algorithm is combined approach of clusterhead selection algorithm that is same as present in DGMA clustering algorithm and gateway selection algorithm that is designed to help in forming a prolong cluster. This EDGMA clustering algorithm is abbreviated as Mobility based Clusterhead and Gateway selection (MCHGS) Algorithm. In the next chapter, a comparison between DGMA and MCHGS algorithm is drawn against various aspects. This comparison is showing the enhanced performance of MCHGS over DGMA.

   spatial dependency (SD) is followed here. Spatial dependency captures the similarity of the velocities between two nodes that are within their communication range. This metric is used to extract the characteristics of group mobility in MANETs. It has been observed that nodes which belong to the same group are more likely to move within the same region in the network over a period of time to complete their tasks or routing. When nodes are moving within a stationary region, the group of mobile nodes is considered to have no movement.

   Hence, at time t, location of a node is compared with the most recent record in the history cache such that a nodes micro movement route within the diameter of Dthr will not trigger any updating of the movement. Based on above, each node will periodically check its own mobility information at every time interval T0. If its linear distance D is greater than Dthr, it updates its mobility history information correspondingly. Based on the information in the history cache, a node calculates its total spatial dependency (TSD) with the following steps:

   1. It exchanges its history information speed Si and direction i as presented in paper [1] with its directly connected neighbors.

   2. A node calculates its relative direction (RD) and speed ratio (SR) with each of its directly connected neighbors. For example, for nodes i and j, the RD of these two nodes is the cosine of the angle between i and j at time t,

      RD(i,j,t)= cos(i(t)-jt)

      and the SR between two nodes i and j is given

      Figure 1 An ad hoc network with nodes moving in different directions and speeds

      This paper is inspired by Distributed Group Mobility Adaptive Clustering Algorithm. The selection of clusterhead from a group of mobile nodes in which every node is moving in different direction with different speed is done using the concept of Distributed Group Mobility Adaptive Clustering Algorithm. After selecting the clusterhead selection of gateway node is started. The selection of gateway node is useful to perform effective routing of data from source to destination. Gateway nodes are border node of a cluster that is significantly helpful for intra-cluster routing as well as inter cluster routing. Therefore this paper is divided into two parts. First is the clusterhead selection on the basis of mobility speed and direction of mobile node and second is the gateway selection algorithm that chooses a gateway for inter-cluster and intra-cluster data forwarding.

      First of all for selection of clusterhead mobility metric is used. The concept of the mobility metric,

      by

      SR(i,j,t) = min(Si(t),Sj(t))

      max(Si(t),Sj(t))

   3. Calculate the Spatial Dependency, SD(i,j,t)= RD(i,j,t)*SR(i,j,t)

   4. Assuming the number of its directly connected neighbors is n, after exchanging the SD with each neighboring node, the node takes the summation of all SD it has and gets the Total Spatial Dependency (TSD) by

TSD(i,t)=SD(i,j,t) where j= 1 to n

A higher TSD value implies that node i has a larger neighbor set and it has a similar mobility pattern with its neighbors. The speed and direction may be strongly related to others. Thus, a node with a higher TSD value is entitled to represent and to reflect the mobility pattern of the group.

The terminologies used in MCHGS are

1. T: the duration that two Cluster head are directly connected.

2. n1: used by a red node to show the ratio of the number of one-hop black neighbors to the number of all one hop neighbors. – n1-Input is the input threshold value of n1

3. n2: used by a black node to show the ratio of the number of one-hop black neighbors to the number of all one hop neighbors. – n2-Input is the input threshold value of n2

This clustering has two main processes: the nomination process and the cluster maintenance process. Each node maintains its own status and no centralized entity is responsible for the maintenance of a whole cluster. Clustering begins with the nomination process that has five steps:

1. Each node begins in black.

2. A black node, if not connecting with any red node, broadcasts a request to its directly connected neighbors to nominate a red node.

3. After feedback of individuals TSD from its neighbors, the applicant (node A) compares its TSD with the received TSD values from each of its black neighbors (node B)

   1. If TSD(A, t)< TSD(B, t), nomination process is terminated ad it remains as a black node;

   2. If TSD(A, t)> TSD(B, t), continue until node A has compares with all its neighbors.

4. If the black node has the largest TSD among all of its black neighbors, it turns to red.

5. It broadcasts an invitation to its neighbors and the receivers in black change their color to yellow.

Nomination Process

For each node m Adj[]

If .color=black then for each v m

if(for all v where v.color=black and .TSD>v.TSD) .color=red

if .color=red for each v m

if v.color=black

do v.color=yellow

Figure 2. Nomination process

For the maintenance process at a node, it is triggered upon detecting the updates of mobility information. Different maintenance steps will be executed according to a nodes color. The maintenance steps for clusterhead which is red in color are as follows:

1. If two red nodes are connected over a time T, the one with smaller TSD turns into yellow;

2. If more than n1-Input of neighbors are black,

1. n1 >= n1-Input, it turns into black.

   The maintenance steps for member node which is yellow in color are as follows:

   1. If a yellow node has a bigger TSD than any of connected red nodes, it turns itself into black; or

   2. If it fails to find any neighboring red node, it turns into black.

The maintenance steps for free node which is black in color are as follows:

1. If there is a red neighbor that has a larger TSD value than this black nodes, it turns to yellow;

2. Else, if the component of black nodes in the neighbor set is greater than n2-Input, i.e. n2 >= n2- Input, it triggers the cluster Nomination process.

   Maintenance Process

   If .color=red For each v m

   if (for each v.color=red and CT(M,v)>T) if .TSD<v.TSD

   .color=yellow else v.color=yellow

   else if n1>=n1-input

   .color=black if .color=yellow

   for each v m

   if each(v.colorred) .color=black

   else if all v.color=red if (.TSD>v.TSD)

   .color=black if .color=black

   if for each v.color=red and .TSD<v.TSD v.color=yellow

   else if n2>=n2-input

   nomination()

   Figure 3. Maintenance process

   The second proposed algorithm is Gateway selection algorithm. Gateway nodes in this algorithm are selected among the border nodes. A border node is a mobile node which has at least one neighbor belonging to a different cluster. Border nodes are at the perimeter of the clusters.

   Figure 4: Example of border nodes

   In the clustering, nodes are classified into four states such as clusterhead, gateway, member node and free node, and each node maintains a neighbor table (NT) and a cluster adjacency table (CAT).

   Neighbor Table (NT)

   Neighbor node ID

   Neighbor node state

   Next node to neighbor node

   Hop count to the neighbor

   Cluster Adjacent Table (CAT)

   Neighbor Cluster

   Neighbor Cluster (CH) ID

   Gateway ID

   When a source node wants to send packets to the destination, it sends the packets directly to the destination if the destination can be found in its NT; otherwise the routing process is triggered to search the destination. In the routing process the

   routing control packets, RREQ and RREP are employed as in on-demand routing. The source sends the RREQ to its clusterhead. When the clusterhead receives the RREQ it checks if the destination is in the cluster. If not, it will forward the RREQ to the neighboring clusterhead through the gateway nodes. When the destination receives the RREQ, it replies an RREP to the source. Only the nodes in the clusters whose clusterheads helped forwarding the RREQ will forward the RREP. Hence, the flooding traffic in route discovery can be reduced.

   Gateway Selection(u, CAT, NT)

   For all nodes in the cluster

   If NT[NextNode to NeighborNode ID]=CAT[Next Cluster ID]

   Or NT[NextNode ID]=CAT[Next Cluster u.color=green

   u will send Gateway CLAIM to its CH With Next

   Cluster ID CH will send Gateway GRANT to its all Cluster members defining the gateway.

   Figure 5. Gateway selection algorithm

3. Result

This part of paper introduces the experimental results obtained by implementing mobility based clusterhead and gateway node selection algorithm. These algorithms have been simulated using NS2 simulator. The results obtained have been analyzed thoroughly. The analysis thus carried out, shows the use of both algorithms. MCHGS has given better result in term of Mean lifetime of CHs, Mean resident time and Average number of cluster reaffiliation.

Table: Simulation Parameters for simulating mobility Clusterhead selection

Metrics used for Simulation

To study the performance of solution, various contexts are created by varying the number of nodes and node mobility. The metrics used to evaluate the performance of the protocols. The performance metrics are purposely chosen to show the difference in performance among the different routing methods. These metrics are the most crucial and common yardstick to measure the overall

performance of the network routing algorithms. Similar types of metrics were also used in many other comparison related work. The performance metrics are defined as the followings.

The results show that proposed algorithm has a better performance than the Dynamic mobility based clustering algorithm in all investigated aspects, including Mean lifetime of CHs, Mean resident time and Average number of cluster reaffiliation. These performance metrics studied reflect the stability of clusters from different views.

1. The Mean lifetime of CHs, also known as cluster lifetime, is calculated by cumulating the time duration of all nodes being CHs and dividing it by the total number of CHs during a simulation run.

2. The Mean resident time of a node is the average time interval that a node affiliates with a certain cluster.

3. The Average number of cluster reaffiliation is the summation over all nodes on the number of a node joining a cluster and the number of CH formations normalized over the simulation time.

   In this work, simulation and comparison Mobility based clusterhead and gateway selection (MCHGS) algorithm with the DGMA clustering scheme is performed by investigating cluster stability with respect to the nodes transmission range and speed. For MCHGS, the control parameters n1 and n2 are specified and varied from 0.4 and 0.5. The results show that MCHGS has a better performance than the DGMA with control parameters n1=n2=0.5 in all investigated aspects, including Mean lifetime of CHs, Mean resident time and Average number of cluster reaffiliation.

   In this part, all investigated aspects Mean lifetime of CHs, Mean resident time and Average number of cluster reaffiliation are shown by y-axis and the parameters of node like transmission range and speed are represented on x-axis.

   Here the nodes transmission range varies from 100m to 300m with an increment of 50m each time.

   Figure 6. Mean lifetime of CHs. Vs transmission range

   Figure 7. Mean lifetime of CHs vs. Speed

   Figure 8. Mean resident time of custer members vs Transmission range

   The speed of nodes changes from as low as 5m/s to 20m/s for high speed mode.

   Figure 9. Mean lifetime of CHs vs. Speed

   Figure 10. Mean resident time of cluster members vs. Speed

   Figure 11. Average number of cluster reaffiliations per sec. vs. Speed

4. Conclusion

Based on the mobility metric, the proposed algorithm ensures cluster stability with longer cluster lifetime; longer mean residence time for cluster members, and a smaller number of reaffiliation events. The proposed Mobility based Clusterhead and Gateway Selection Algorithm has following features:

1. Increased lifetime of cluster heads,

2. Applicable in highly mobile environment, and

3. Reduce the number of re-clustering.

With the help of results shown in previous chapter, MCHGS clustering is much better to its previous version that is DGMA. As MCHGS is an enhancement of DGMA, it also proves it by results. MCHGS clustering algorithm has a better performance than the DGMA in all investigated aspects, including Mean lifetime of CHs, Mean resident time and Average number of cluster reaffiliations. These performance metrics studied reflect the stability of clusters from different views.

5. References

1. B Yan Zhang, Jim Mee Ng, A Distributed Group Mobility Adaptive Clustering Algorithm for Mobile Ad Hoc Networks, IEEE, page no. 3161-3165, 2008.

2. Reza Purtoosi Hassan Taheri Abbas Mohammadi Foroohar Foroozan, A High Performance Cluster-Based Flooding Algorithm for Wireless Ad Hoc Networks, IEEE 2005.

3. Tsung-Chuan Huang Kuan-Ping Kho Lung Tang, Hybrid Routing Protocol Based on the k-hop Clustering Structure for MANETs, IEEE 2009.

4. Christian Bettstetter and Stefan Konig, On the Message and Time Complexity of a Distributed MobilityAdaptive Clustering Algorithm in Wireless Ad Hoc Networks.

5. Inn Inn ER, Winston K.G. Seah, Mobility-based d- Hop Clustering Algorithm for Mobile Ad Hoc Networks, WCNC / IEEE Communications Society, page no. 2359-2364, 2004.

6. Beongku An and Symeon Papavassiliou, A mobility-based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks, INTERNATIONAL JOURNAL OF NETWORK MANAGEMENT, Int. J. Network Mgmt, page no. 387-395; 2001.

7. Suchismita Chinara, Santanu Kumar Rath, Mobility Based Clustering Algorithm and the Energy Consumption Model of Dynamic Nodes in Mobile Ad Hoc Network, IEEE computer society 2008, page no. 171-176.

8. Yi Xu and Wenye Wang MEACA: Mobility and Energy Aware Clustering Algorithm for Constructing Stable MANETs.

9. Javad Akbari Torkestani, Mohammad Reza Meybodi A mobility-based cluster formation algorithm for wireless mobile ad-hoc networks, Springer 2011.

10. Roberto Carlos Hincapi´e, Blanca Alicia Correa, and Laura Ospina,Survey on Clustering Techniques for Mobile Ad Hoc Networks, 2006.

11. J. M. Ng and Y. Zhang, "A Mobility Model with Group Partitioning for Wireless Ad hoc Networks," Proc. of IEEE International Conference on Information Technology and Applications, ICITA 2005, Sydney, July 2005, pp.289-294.

12. C. Bettstetter and R. Krausser, "Scenario-based stability analysis of the distributed mobility-adaptive clustering (DMAC) algorithm," Proc of the 2nd ACM International Symposium on Mobile Ad hoc Networking & Computing, CA, USA, 2001, pp 232 – 241.

13. M. Chatterjee, S. K. Das, D, Turgut,WCA:A Weighted clustering algorithm for mobile ad hoc networks. Cluster computing. Vol. 5.2002. pp. 193-204.

14. A. D. Amis, R. Prakash, T.H.P Huyuh,Max-Min D- Cluster Formation in Wireless Ad Hoc Networks. Proceedings of IEEE Conference on Computer Communications (INFOCOM). Vol. 1.2000.pp.32-41.

15. Rajesh Pandit, Mobility aware Access Based Clusstering in Mobile AD Hoc Networks, 2004.

16. C. L. Richard and m. Gerla,Adaptive cluctering for mobile wireless networks, IEEE Journal on Selected Areas in Communications, vol.. 15,no.7,pp. 1265-1275, Sept. 1997.

17. Waseem Shahzad, Farrukh Aslam Khan, and Abdul Basit Siddiqui,Weighted Clustering using Comprehensive Learning Particle Swarm Optimization for Mobile Ad Hoc Networks, International Journal of Future Generation Communication and Networking Vol. 3, No. 1,March , 2010.

18. Kusakumar Punnana, Performance analysis of Swarm based Routing Protocols for MANETs June 2010.

19. S. Corson and J. Macker, Mobile ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations, RFC 2501, Jan. 1999.

20. Mobile Ad-hoc Networks (MANET), http://www.ietf.org/html.charters/manetcharter.html (2009-11-12)

21. S. Basagni, Distributed clustering for ad hoc networks, Proceedings of International Symposium on Parallel Architecture, Algorithms and Networks, June 1999.

22. Network Simulator 2, http://www.isi.edu/nsnam

23. R. Fallier and B. Scheers, Clustering in Mobile Ad- hoc Networks.