ISSN ONLINE(2320-9801) PRINT (2320-9798)

A Survey of Clustering In Mobile Ad-Hoc Networks

K.Madhu Pavan1, Dr.syed umar2, P.V.Avinash Reddy3 and Munnangi Chandradeep4
  1. B.Tech Student, Dept of ECE, K L University, vaddeswaram, Guntur, AP, India.
  2. Associate Professor, Dept of CSE, K L University, Vaddeswaram, Guntur, AP, India.
  3. B.Tech Student, Dept of ECE, K L University, vaddeswaram, Guntur, AP, India.
  4. B.Tech Student, Dept of ECE, K L University, vaddeswaram, Guntur, AP, India.
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

An ad-hoc network is used to establish a connection wirelessly in a network without any routers or access points. When there is a large network, the complexity to gather the routing information increases. In such a case, the clustering techniques are much useful in reducing the complexity. This paper discusses the use of clustering and its techniques in mobile ad-hoc networks.

 

Keywords

MANET, clustering, ad-hoc network, load balancing, cluster head

INTRODUCTION

Mobile ad-hoc networks (MANETs) are self-configured networks and are dynamic in nature. They can connect to different networks as they use wireless connections and are mobile. In order to use them effectively, some efficient and reliable routing protocols have been developed. Clustering is one of them. When the network is very large, the nodes will be scattered and obtaining its routing information may get difficult. In such a case, clustering techniques or a cluster based routing is used in which all the nodes of the network are organized dynamically into some groups. These groups are named as clusters. These are again combined into large groups, which provide it with a stable network topology.
Since a MANET is a device with battery powered, the reduction of energy consumption by the nodes is also an important factor. So, a low power and efficient protocol structure is necessary in order to improve the energy efficiency of the network. There are several clustering techniques and protocols based on measures such as packet drop rate, overhead, delays, through-put, etc. Threshold power consumption clustering, mobility based D-hop clustering algorithm, load balancing clustering, cluster based zone allocation method, false node detection algorithm, energy efficient cluster head selection scheme based on FMPDM(fuzzy multiple parameter decision making) are some of them. Load balancing in a network is not an easy task. It is a major problem every that every network suffers from. So many techniques are being developed to overcome this problem in an effective way.

CLUSTERING

The clustering is defined as the division of nodes of a network into small groups. There will be cluster head, gateway, and cluster members in each group. The cluster head is a local coordinator of the group. The gateway is a node which provides communication between two clusters. Cluster members are the remaining nodes of the group. They are also called as ordinary nodes. The nodes perform routing and maintenance of the network. A hierarchical routing is better for large networks. The cluster heads hold the routing information. The main goal of a clustering technique is to achieve high mobility and scalability. It also increases the system capacity and reduces retransmissions. Many clustering methods have been proposed for energy efficiency and load balancing in a network.
There are two types of clustering as active and passive clustering. In active clustering, a cluster head is selected by the mobile hosts, for the periodical exchange of information. Whereas in passive clustering, the procedure is stopped until data traffic commences. In this, the major control overhead is eliminated. The cluster head can use low and high power modes, so that it can use low power mode while communicating with its immediate nodes and it can use high power mode to communicate with other clusters. The size of the cluster should be minimum, so as to minimize the energy or power consumption by each group. It also increases the life time of the routes.

LOAD BALANCING

Load balancing is a necessary factor to balance the loads among the clusters. Because of the frequent topology change of a MANET, the maintenance of reliable data transfer is a challenging task. When a huge load is imposed on the nodes of any network than its capability, the completion of the task in time becomes complex. There may be some idle nodes and some working nodes. So an approach in which the load on the network can be balanced in a best way is to be identified and used. There are many approaches based on load balancing factor and we can use them as desired.
Some protocols like DLAR (Dynamic Load-Aware Routing) protocol where this protocol have intermediate nodes to bear load and those nodes are selected in such a way that intermediate nodes are selected during the route selection process and these will monitors the congestion status of active routes to construct the route when any failure in the node occurs or overloaded then the node will chooses the alternate path for the packet delivery. A new protocol to enhance path reliability and realize load balancing in MANETS. These goals are achieved through fully exploiting the presence of multiple paths in MANETS in order to jointly attack the problems of frequent route failures and load balancing. The system assumes the use of the on demand routing protocol and the basis of the system is lightweight path monitoring mechanism for handling route failures proactively. The protocol introduced is a multipath routing protocol with a load balance policy. From this we knew that there will be improvement in terms of throughput and end to end delay and the theoretical analysis says relative difference of tracing the routing path in single path and the multi path routing with route balance mechanism in the MANETS.
Many of the researchers after their research says the routing path of multi path causes effects on balancing the load and the routing path is large where more number of nodes which will be not used and it is more cost effective. The load distribution is almost less effect on the single path routing. Cluster Based Enhanced Routing
Protocols
It is the query of theory model where among metrics involved (within a cluster) includes number of load in the cluster, number of load for each node in the cluster, number of packets in service, and the time taken for each task in queue within a cluster. Packets arrived will be in the process of Random Arrival Pattern or Poisson Arrival Process. Generally it maintains the queue method at each cluster. If any node is full by receiving the packets then it send the command that send the packet to other node as present node is full. The sender understands it sends the packets to the other node likewise it continues and shows clearly in figure 2.
Design Requirements for Associativity based Routing Protocols in CBE
To design the any cluster based routing protocols we have main issues to consider. They are as follows
a. Selection of cluster head
Before the creating the cluster form the cluster head should be selected such that it will acts the main or control node for that particular cluster. The whole information regarding the nodes will be at the cluster head like id of the nodes etc details will be there
b. Neighborhood discovery
The neighbor node discovery is the main phase because by this we can know the node is in active sate or at sleep mode. If the nodes are in active maintain we can route and next hop can de defined easily.
c. Balancing the loads within the clusters
As delivering the packets from one node to other the load should be balanced to avoid the congestion at the nodes. By this the packet delivery will be fast without any delay. And the load is spread on the nodes
d. Route maintenance
After the route discovery the route should be maintained such that should avoid the node failure and effective communication should be there from one node to other.
Some other assumptions should be there:
a. Every node in the network has a unique ID. If a node shares more than 1 cluster, it would still use one ID for all the clusters it is a member of.
b. A message sent by a node is received correctly within a finite time by all it’s 1-hop neighbors. After this allocated time, the message will be timed out and a new request will be broadcast within the network (be it new broadcast or a local repair broadcast).
c. Network topology maintains the same- no increase or decrease of network size during the algorithm execution.
However, nodes leaving and entering the network is allowed as long as the network size maintains the same. There is a max nodes number within the network, in which, exceeding this number is not allowed.
The main reason to design the ABR protocol in CBE is to achieve two objectives. They are 1. To achieve an efficient and stable cluster topology. 2. To achieve it with minimum cost overhead and minimal complexity.
In Route Maintenance Phase This mainly concern with the local route reconstruction mechanism to introduce the ABR protocol. To this Cluster based protocol is used for the local route repair.
The backtracking procedure and the local route reconstruction methods proposed by previous work will be modified in order to achieve better overhead and overall reliability and efficiency. Instead of repairing node by node, this suggested scheme would repair local clusters instead. In the event that an affected node moves out of the cluster, then, another node within the cluster would be selected. This scheme also employs the multipath route selection method.
Advantages of the CBE- ABR
Unlike the other Cluster based protocols it has many advantages like below
a. Easy Recovery from the route failure
b. Most Robust
c. More Reliable and Efficient
d. Reduces the route discoveries
e. Less end to end delay

Conclusion

In this paper we discussed about the cluster based routing protocols in MANETS. Various Cluster based protocols are discussed briefly about their advantages and drawbacks, how they overcome in other protocol. To achieve mainly two objectives are to achieve an efficient and stable cluster topology with minimum cost overhead and minimal complexity. To gain these two goals we propose a protocol called ABR which can benefit a lot of mobile networking enthusiasts into implanting the protocol in their field of interest. It is expected that IABR would be both efficient and effective compared to the existing ABR protocol and would cover a wider range of possibilities in terms of its routing metrics. It is expected to give a higher route establishment rate with lesser route breakage. It is also expected to balance the load in the mobile network thus producing higher throughput and better overall performance

Figures at a glance

Figure 1 Figure 2 Figure 3 Figure 4
Figure 1 Figure 2 Figure 3 Figure 4
Figure 1 Figure 2 Figure 3
Figure 5 Figure 6 Figure 7
 

References


  1. R.K.Ghosh, V. Garg, M.S. Meitei, S.Raman, A.Kumar, N.Tewari, (2006) “Dense Cluster Gateway Based Routing Protocol for MultihopMobile Ad Hoc Networks”, Ad Hoc Networks Journals, vol. 4 issue 2, pp 168-185.

  2. Y.Choi, D.Park, (2002) “Associativity Based Clustering and Query Stride for On Demand Routing Protocols in Ad Hoc Networks,” Journal ofCommunications and Networks (KICS), vol. 4 issue 1, pp 4-13

  3. C. R. Lin, M.Gerla,(1997) “ Adaptive Clustering for Mobile Wireless Networks,” IEEE Journals on Selected Areas in Communications, Vol 15Issue 7, pp 1265-1275

  4. A.B.McDonald, T.F.Znati, (1999) “A Mobility-Based Framework for Adaptive Clustering in Wireless Ad Hoc Networks,” IEEE Journal onSelected Areas of Communications, Vol.17 Issue 8, pp 1466-1487

  5. Sung-Ju Lee, Mario Gerla,(2000) “Dynamic Load-Aware Routing in Ad Hoc Networks,” Proceedings of The Third IEEE Symposium onApplication-Specific Systems and Software Engineering Technology.

  6. AntoniosArgyriou, Vijay Madisetti, (2006) “Using a new protocol to enhance path reliability and realise load balancing in mobile ad hocnetworks,” Journal of the Ad Hoc Networks, vol.4 Issue 1,pp: 60-74.

  7. Peter P.Sham, Sylvie Perreau, (2004) “Increasing the network performance using multi-path routing mechanism with load balance,” Journal ofthe Ad Hoc Networks, vol.2 issue 4, pp: 433- 459.

  8. YasharGanjali, AbtinKeshavarzian, (2004) “Load Balancing in Ad Hoc Networks: Single-path Routing vs. Multi-path Routing,” INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 2, pp. 1120-1125.