Keywords
|
| MANET, clumping, clump head, CCDP, EBCA, BRAP |
INTRODUCTION
|
| Mobile ad hoc network (MANET) is a network that can be established without the need forany centralized administration or fixed infrastructure. Mobile adhoc networks are decentralized networks that develop through selforganization [1]. MANET is formed by a group of nodes that can transmit and receive data and also relay data among themselves. Communication between nodes is made over wireless links. A pair of nodes can establish a wireless link among themselves only if they are within transmission range of each other. An important feature of ad hoc networks is that routes between two hosts may consist of hops through other hosts in the network [2]. When a sender node wants to communicate with a receiver node, it may happen that they are not within communication range of each other. However, they might have the chance to communicate if other hosts that lie in-between are willing to forward packets for them [3]. This characteristic of MANET is known as multihopping. Today wireless bluetooth, personal area networks (PAN), IEEE 802.11 a/b/g, wireless local area networks (WLAN) and HIPERLAN/2, are communication standards that include ad hoc features [4]. Routing in ad hoc networks is different compared to normal wired networks. Topology control deals with the problem of computing and maintaining a connected topology among nodes in ad hoc networks [5]. Topology control covers: power control and hierarchical topology organization. Power control ensures network connectivity by adjusting the power of each node in order to one hop neighbor connectivity [6]. On the other hand, hierarchical topology control is an approach often referred to as clustering [7]. |
| A. CLUMPING IN MANET: |
| Clumping in MANET can be defined as the virtual partitioning of the dynamic nodes into various groups. Groups of the nodes are made with respect to their nearness to other nodes. Two nodes are said to be neighbor of each other when both of them lie within their transmission range and set up a bidirectional link between them. Clumps in MANET can be categorized as overlapping clusters or non overlapping clumps as shown in figure 1. |
| The small circles represent the wireless nodes in the network. The lines joining the nodes denote the connectivity among them. Clump control structure forms the virtual backbone of communication where clump heads are the communication hot spots. The clump head works as the local coordinator for its member nodes and does the resource management among them similar to a base station of cellular architecture. These clump heads are responsible for inter clump and intra clump communication. Inter cluster communication is made possible through the gateway nodes. A gateway node is a node that works as the common or distributed access point for two clump heads. When a node lies within the transmission range of two clump heads and supports inter cluster communication, it is called the ordinary gateway for two corresponding clumps. A node having one clump head as an immediate neighbor in addition to which it can reach a second clump head in two hops is a distributed gateway that is linked to another distributed gateway of other clump. Both of the distributed gateways provide the path for the inter-clump communication as well. The ordinary nodes of the clump are the immediate neighbors of the clump heads. They have the capability of serving as either a head or a gateway whenever selected to do so. Depending on the diameter of the clumps, there exist two kinds of clump control architectures, known as one-hop clumps and multi hop (d-hop) clumps. In one-hop clumps, every member node is at most 1-hop distance away from the central coordinator called as the clump head. Thus, all the member nodes remain at most two hops distance away from each other within a logical clump. But in multi hop clumps, the constraint of immediate neighborhood of members from the head is eliminated by allowing the nodes to be present at most d-hop distance away from each other to form a cluster [8, 9, 10]. The nodes in the MANET can be either in the flat structure or in hierarchical structure. |
| B. CLUMP HEADS: |
| Most clumping approaches for mobile adhoc 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 clump heads and each node in the network is associated with one. Clump heads are connected with one another directly or through gateway nodes. The union of gateway nodes and clump heads form a connected backbone. This connected backbone helps simplify functions such as channel access, bandwidth allocation, routing power control and virtual circuit support [7]. Clump heads are analogous to the base station concept in current cellular systems. They act as local coordinators in resolving channel scheduling and performing power control [11]. However, the difference of a clump head from a conventional base station resides in the fact that a clump head does not have special hardware, it is selected among the set of stations and it presents a dynamic and mobile behavior [8]. Since clump heads must perform extra work with respect to ordinary nodes they can easily become a single point of failure within a cluster. For this reason, the clump head election process should consider for the clump head role, those nodes with a higher degree of relative stability [12]. The main task of a clump head is to calculate the routes for long distance messages and to forward inter-clump packets. A packet from any source node is first directed to its clump head. If the destination is located in the same clump, the clump head just forwards the packet to the destination node. If the destination node is located in a different clump, the clump head of the sending node routes the packet within the substructure of the network, to the clump head of the destination node. Then, this clump head forwards the packet to its final destination [13]. |
| C. CLUSTERING ALGORITHMS IN MANET: |
| In this section we describe following clustering algorithms: |
• Linked Cluster Algorithm(LCA)
|
| The linked cluster algorithm (LCA) performs the job of initial three tasks such as topology sensing, cluster formation and cluster linkage whereas the link activation algorithm (LAA) performs the job of link activation between the nodes in the network. The routing algorithm covers the details of the routing operations for packet communication. The objective of the current work is to focus on the basis of neighborhood detection in changing topology and clusterformation.LCA could not meet certain criteria of the ad hoc network, but could become the base algorithm for other benchmark algorithms. |
• Lowest ID Algorithm(LID)
|
| In this algorithm, every node is assigned with a unique non-negative identification number which is the deciding factor for the status of a node. In a mobile packet radio network, anode has no a priori knowledge of the locations of other nodes as well as the connectivity of the network. So, as a first task when the network comes up, the connectivity among the nodes is discovered by every other node. This is accomplished by every single node that broadcasts its own ID to its neighbors. At the same time it also receives the same from its neighbors. If a node listens to all the IDs that are higher than its own ID, then it declares itself as the cluster head among its immediate neighbors. And the neighbor nodes whose status is not yet decided become the members of the newly selected head. This process is repeated till all the nodes are assigned with the role of ahead or a member of a cluster. |
• Highest Connectivity Algorithm(HC)
|
| This algorithm aims to reduce the number of clusters in the network. In every cluster there exists a cluster head that belongs to the dominating set. In the HC algorithm, a node having highest degree of connectivity is selected as the cluster head. And the adjacent node whose status is not yet decided becomes the member of the selected cluster head. A higher degree of connectivity ensures efficient service to the member nodes by minimizing the number of heads. Here the efficiency means lowering the delay in communication through the head nodes. |
• Mobility Metric Based Algorithm (MOBIC)
|
| The algorithm uses mobility based metric as cluster formation basic and calculation of weights of the nodes in the network. MOBIC works almost same as the Lowest ID algorithm, where the node IDs are replaced by the relative mobility metrics of each node. In MOBIC the need of collecting the relative speed information from the neighbors degrades its performance, because continuous movement of the nodes in MANET may provide inaccurate mobility information during cluster set up time. |
• Distributed Mobility Adaptive Algorithm (DCA, DMAC)
|
| This algorithm is a generic weight based cluster formation algorithm.DCA does not allow the change in network topology during the execution of the algorithm. A node having bigger weight among all its one-hop neighbors is selected as the cluster head. DMAC claims to be the most suitable algorithm for the cluster formation and maintenance in the presence of node mobility. It starts with the assumption that every node knows its own ID, weight and status in the network as well as the same for its one-hop neighbors. This proves that the cluster head is selected only with the knowledge of its local topology. |
• Weighted Clustering Algorithm(WCA)
|
| In WCA re-election takes place with the occurrence of certain events i.e., when there is a demand for it. Node parameters like degree of connectivity, mobility, transmission power and available battery power are considered for selection of a cluster head and are given different weights depending on the network scenario. For example, sensor networks where energy is a major constraint, battery power could be given higher weight. |
RELATED WORK
|
| Haidar Safa et al. [16] designed and implemented a dynamic energy efficient clustering algorithm that increases the network lifetime. They proposed a model that elects first the nodes that have a higher energy and less mobility as cluster-heads, then periodically monitor the cluster-heads energy and locally alter the clusters to reduce the energy consumption of the suffering cluster-heads. They compared the proposed algorithm with weight clustering approach and found that the results outperformed the weight clustering approach in all scenarios. |
| Suchismita Chinara et al. [17] proposed a topology adaptive clustering algorithm for mobile ad hoc network that ensures better cluster stability and enhances the network life time by keeping a record of previous n set of movements of every node to predict their average mobility. To improve the cluster stability a node with lower mobility and higher battery power has been chosen for cluster head. The selection of non-volunteer nodes reduces the number of global reelection complexity and load on individual nodes. |
| Presented by Stefano Basagni [14], two distributed algorithms DCA (Distributed Clustering Algorithm) and DMAC (Distributed and Mobility-Adaptive Clustering) that requires only knowledge of the local topology at each node and allows each ordinary node to have direct access to at least a cluster head, thus guaranteeing fast inter and intra cluster communication between each pair of nodes. A weight based criteria has been introduced for the cluster formation that allows the choice of the cluster heads based on node mobility related parameters. |
| Vincent Bricard et al. [15] proposed a local approach for the cluster heads election in a new distributed Mobility Prediction-based Weighted Clustering Algorithm with Local cluster-heads election (MPWCA-L). They have shown that their algorithm ensures a better stability of the dominant set and a better quality of service than WCA. Results show that their algorithm provides a better stability than WCA while the speed is increasing. |
| Kaouther Drira et al. [18] presented a methodology for building distributed and dynamic virtual topology in ad hoc networks based on the concept of dominating sets. Their network topology can adapt to different mobility scenario without overhead. Their algorithm minimizes the number of exchanged messages and has the advantage of supporting scalability. |
PROPOSED WORK
|
| Simulation based survey is made to study the strengths and weaknesses of existing algorithms that motivated us for the design of energy efficient clumping in MANET for longer network lifetime and reduced maintenance overhead. The protocols and algorithms have been proposed for the efficient design of clumping in MANET and evaluated separately to analyse their performances and compared with the competent results. |
| • Closer Clump Detection Protocol (CCDP): This detection protocol has been designed to help the nodes to probe their immediate neighbours. In this protocol, every node broadcasts its own information to the network, so that it is received by a node that lies within its transmission range. The receiver senses its neighbours and updates its neighbour table from time to time. This protocol is validated through simulation by using Color Petri Nets (CPN) prior to its implementation. |
| • Energy Based Clumping Algorithm (EBCA): This algorithm uses the node mobility and its available battery power for calculating the node weights has been proposed. A node having the highest weight among its immediate neighbours declares itself as the volunteer clump head. As the current head consumes its battery power beyond a threshold, non-volunteer clump heads are selected locally. The algorithm aims to utilize the battery power in a fairly distributed manner so that the total network life time is enhanced with reduced clump maintenance overhead. During the process of clumping, some isolated heads without having any members are formed. This increases the delay in communication as the number of hops in the routing back bone is increased. |
| • Broadcasting Range Adjustment Protocol (BRAP): The broadcasting protocol has been proposed that allows the isolated nodes to adjust their ranges to remain connected with existing clump heads. The results show that, BRAP reduces the delay in communication by reducing the number of clump heads in the network. Validation for the base protocol NDP and algorithm EBCA are made through simulation by using the CPN tools. |
CONCLUSION AND FUTURE SCOPE
|
| In this paper protocols and algorithms are proposed for the efficient design of clumping in MANET.Closer Clump Detection Protocol (CCDP) has been designed to help the nodes to probe their immediate neighbours. Energy Based Clumping Algorithm (EBCA) has been proposed that uses the node mobility and its available battery power for calculating the node weights. The increase in the number of clump heads increases the length of the communication backbone in terms of number of hops. This may increase the end-to-end delay in communication for the packets. The proposed broadcasting range adjustment protocol (BRAP) helps the isolated nodes to get affiliated with existing clump heads instead of becoming new heads. It reduces the end-to-end delay by reducing the number of clump heads in the network. |
| The protocols in this paper mostly deal with the clump formation, clump maintenance and energy consumption that can be extended to some other areas of clumping in future like load balancing among the clump head, fault tolerant clumping or privacy and securityin clumped MANET. |
| |
Figures at a glance
|
 |
| Figure 1 |
|
| |
References
|
- C. Prehofer, C. Bettstetter, “Self organization in communication networks: Principles and design paradigms”, IEEE Communications Magazine,Vol. 43, Issue 7, 2005,pp. 78-85.
- J. Wu, J. Cao, “Connected k-hop clustering in ad hoc networks”, ICPP, 2005, pp 373-380.
- I. Chatzigiannakis, S. Nikoletseas, “Design and analysis of an efficient communication strategy for hierarchical and highly changing ad-hocmobile networks”, Mobile Networks and Applications, Vol. 9, 2004, pp. 319-332.
- M. Frodigh, P. Johansson, P. Larsson, “Wireless Ad Hoc Networking--The Art of Networking without a Network”, Ericsson Review, Vol. 77,2000, pp. 248-263.
- R. Rajaraman, “Topology control and routing in ad hoc networks: a survey”, SIGACT News, Vol. 33, 2002, pp. 60-73.
- V. Kawadia, P. R. Kumar, “Power control and clustering in ad hoc networks”. INFOCOM 2003, Twenty-Second Annual Joint Conference ofthe IEEE Computer and Communications Societies, Vol.1. 2003, pp. 459-469.
- L. Bao, J.J. Garcia-Luna-Aceves, “Topology management in ad hoc networks”, Proceedings of the 4th ACM international symposium onmobile ad hoc networking & computing, Vol. 9, 2003, pp. 129-140.
- C. R. Lin and M. Gerla, Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications, 15(7):1265–1275, sept 1997.
- T. Ohtaaand S. Inoue and Y. Kakuda, An adaptive multi-hop clustering scheme for highly mobile ad hoc networks, In proceedings of sixthinternational symposium on autonomous decentralized systems(ISADS’03), Pisa, Italy, April 2003.
- C. R. Lin and M. Gerla, A distributed control scheme in multi-hop packet radio networks for voice/data traffic support, In Proceedings ofIEEEGLOBECOM, pages 1238–1242, 1995.
- M. Gerla, J. Tsai, “Multicluster, mobile, multimedia radio network”, Wireless networks, Vol 1, 1995, pp. 255-265.
- B. An, S. Papavassiliou, “A mobility-based clustering approach to support mobility management and multicast routing in mobile ad hocwireless networks”, International Journal of Network Management. Vol. 11, 2001,pp. 387-395.
- Y.P. Chen, A. L. Liestman, “A zonal algorithm for clustering ad hoc networks”, International Journal of Foundations of Computer Science,Vol.14, 2003, pp. 305-322.
- Basagni, Stefano, "Distributed clustering for ad hoc networks." Parallel Architectures, Algorithms, and Networks, 1999.(I-SPAN'99)Proceedings, Fourth International Symposium on. IEEE, 1999.
- Bricard-Vieu, Vincent, Nidal Nasser, and Noufissa Mikou, "A Mobility Prediction-based Weighted Clustering Algorithm Using Local ClusterheadsElection for QoS in MANETs." Wireless and Mobile Computing, Networking and Communications, 2006.(WiMob'2006), IEEEInternational Conference on. IEEE, 2006.
- Safa, Haidar, Omar Mirza, and Hassan Artail, "A dynamic energy efficient clustering algorithm for MANETs." Networking andCommunications, 2008, WIMOB'08, IEEE International Conference on Wireless and Mobile Computing, IEEE, 2008.
- Chinara, Suchismita, and Santanu Kumar Rath, "TACA: A topology adaptive clustering algorithm for mobile ad hoc network." The 2009 WorldCongress in Computer Science Computer Engineering and Applied Computing, July 13-16, Las Vegas, USA. Bentham Science Publishers,2009.
- Drira, Kaouther, and Hamamache Kheddouci, "A new clustering algorithm for MANETs." Telecommunications Network Strategy andPlanning Symposium (NETWORKS), 2010 14th International, IEEE, 2010.
|
Menu