Slideshare uses cookies to improve functionality and performance, and to provide you with relevant advertising. If you continue browsing the site, you agree to the use of cookies on this website. See our User Agreement and Privacy Policy. See our Privacy Policy and User Agreement for details. Published on Feb 9,

Author:Moogutaxe Vuk
Language:English (Spanish)
Published (Last):11 December 2004
PDF File Size:15.67 Mb
ePub File Size:9.68 Mb
Price:Free* [*Free Regsitration Required]

The dynamic topology of a mobile ad hoc network poses a real challenge in the design of hierarchical routing protocol, which combines proactive with reactive routing protocols and takes advantages of both. And as an essential technique of hierarchical routing protocol, clustering of nodes provides an efficient method of establishing a hierarchical structure in mobile ad hoc networks. In this paper, we designed a novel clustering algorithm and a corresponding hierarchical routing protocol for large-scale mobile ad hoc networks.

Each cluster is composed of a cluster head, several cluster gateway nodes, several cluster guest nodes, and other cluster members. The proposed routing protocol uses proactive protocol between nodes within individual clusters and reactive protocol between clusters. Simulation results show that the proposed clustering algorithm and hierarchical routing protocol provide superior performance with several advantages over existing clustering algorithm and routing protocol, respectively.

A mobile ad hoc network MANET [ 1 , 2 ] is a wireless communication network, at which nodes use peer-to-peer packets transmission and multihop routes to communication.

It can operate without fixed based station or any wireless backbone infrastructure. Hence, MANETs bear great application potential in these scenarios, including battlefield communications, emergency operation, disaster relief, survival search, and sensor dust. But due to the mobility and constant topology changes of MANETs, designing routing protocols for those networks is a challenging process, especially in the large-scale network.

Routing protocols of MANETs presented currently can be classified into four categories according to the mechanism of updating [ 3 , 4 ]. Proactive table-driven routing: this method requires nodes broadcast routing information periodically to maintain valid routing table at all times, which will cost much bandwidth.

Hence, this mechanism is not suitable for large dynamic networks. Reactive on-demand routing: in this case, nodes in the network do not regularly maintain routing table for all destinations, just only when a node has data packets to send to some given destination; it checks its routing table to determine whether it has an active route to the destination.

If not, the node must perform a route discovery procedure to acquire a route to the destination. Thus, this method does well to large population and high mobility networks. Hybrid routing: it is a better compromise of the first two approaches; namely, it uses reactive proactive routing between nodes within individual clusters and proactive reactive between clusters. It is efficient and scalable, as nodes only keep state for their neighbors and support a fully general any-to-any communication pattern without explicit route establishment.

According to the topology of networks, routing protocols can be classified into flat-based routing and hierarchical-based routing [ 5 , 6 ]. In flat-based routing, all nodes play an equal role and can establish a route by local operation and information feedback among themselves easily. But to large scale networks, the frequent topology detection may invalidate the discovered routes, which would lead to high delay and network spending. This phenomenon can be solved efficiently in hierarchical-based routing network.

In hierarchical-based routing [ 7 — 10 ], all nodes are divided into different clusters zones. Each cluster elects a cluster head according to specific rules. Data exchanging between clusters was relayed by gateway node, disregarding the details of how the relayed data would be transmitted to the destination. In a word, hierarchical-based routing not only plays down the network spending by decreasing the number of nodes which participate in routing maintenance, but also increases the network stability by dividing the network into easily controlled subnets.

ZRP Zone Routing Protocol [ 11 ] is typical hybrid routing, which groups nodes into geographic zones. The ZHLS network is divided into nonoverlapping zones, and aggregating nodes into zones conceals the detail of the network topology. As a result, it will cost much time in routing maintenance. The above three routings have a similar shortcoming; namely, routing maintenance will consume a large portion of bandwidth and even may paralyze the network, when the traffic is too large.

HSR Hierarchical State Routing [ 14 ] and CGSR the Center for Global Security Research [ 15 ] are all using table-driven strategy to establish routing of both intra- and interzone, which is good to decrease routing updating delay, but increase the cost of routing overhead unwillingly. However, its location management is closely tied with the network hierarchical topology, which makes the location updating and location finding quite complex.

In hierarchical routing protocols, superior clustering algorithm can not only reduce the routing overhead, but also increase the scalability of the net. Some have been proposed in literatures [ 17 — 20 ], and most of them are to satisfy the specific demands, such as the lowest ID cluster and the highest connectivity.

The MPBC Mobility Prediction-Based Clustering in [ 22 ] elects the node, which has a low variance of the relative mobility values with respect to its neighbors, taking the cluster head responsibility. Although this method can decrease the possibility of reclustering, but it cannot ensure the elected cluster head is logically centric and more profitable to play the cluster head role and hence to increase the whole network performance.

All of them somewhat ignored the scenario, namely, when a node moves out of its cluster head transmission range but still has a link to another cluster member belonging to any cluster head, whether the initial phrase of clustering will be reestablished or not.

And the conclusion in [ 24 ] reveals that frequent cluster changing consumes lots of network resources and highly overlapped clusters decrease the efficiency of hierarchical structure.

Thus, an efficient clustering algorithm must maintain a more stable and less overlapping structure. The experiments and analysis are given in Section 4. Finally, Section 5 concludes the paper. Each node can acquire their position and time information through GPS and can also broadcast them to their neighbors. The coordinates and are the location information sent by node to at two consecutive times and , respectively. Correspondingly, the coordinates of node are and. For simplicity, we assume that node is fixed and node is moving, but actually they are all moving at all times.

Figure 1 depicts the approaching and receding scenario of nodes and. The node is fixed in coordinate original , but moves along the vector. We assume that nodes and keep their velocity and direction at the duration, and arrives at point at the moment. In Figure 1 a , there are two equations:.

Through the law of cosines, there exists where. Thus, the relative velocity between nodes and is. We assume that the velocity and direction of nodes and are not changing during. So, node leaves from the transmission range of node need to track the segment. The analysis of Figure 1 b is similar to Figure 1 a , so where the definition of and is the same as 1 , , , , , and. In a MANET of nodes, the degree of node, which is a good indicator of node density, can be easily denoted as where is the distance between nodes and , ,.

When is bigger, node is more nuclear. Thus, the relative node degree of node can be calculated as. When choosing cluster heads, our clustering algorithm absorbs the quintessence of some clustering algorithms i.

Therefore, we make a reasonable compromise based on the actual needs and operation environment to select cluster heads, which can improve overall performance of MANETs. Each node is assigned a weight indicating whether the node is suitable to act as a cluster head. So, the cost metric represented as for simplicity of node can be expressed as where , and are the weight factor of parameters and , respectively, and if the parameter is more important, its weight factor will be greater.

Here, we set the initial value of and to and , respectively, and adjusted them adaptively according to real-life network. Clustering is a mechanism to dynamically group nodes in MANETs into logically separating or nonoverlapping entities, called clusters.

In our scheme, there are five possible states for nodes: NULL, cluster head, cluster member, gateway, and cluster guest. In this paper, we usually consider one-hop clusters, besides the only scenario; namely, when the cluster guest appears, in this case, the guest node is two hops away from the cluster head.

All the nodes in such a cluster are within the range of the cluster head, but not necessarily within range of each other. The HCA algorithm used for the clustering initialization is described in Figure 2.

Prior to the cluster initialization, all nodes are in the state of NULL. Once started, each node in the network broadcasts a HELLO message to have knowledge of its member nodes, which can be used to calculate its cost metric. Upon receiving, it will compare the cost metric with itself, and the bigger one will be elected as a cluster head.

Upon receiving, the neighbors will send RTJ request to join message to the cluster head, and cluster head will send ATJ affirm to join back when agreeing.

After the above process, some clusters will have been formed. But when a cluster member receives more than one ATJ message, this denotes that the node lies in separate clusters but within transmission range of one another; therefore it will be elected as a gateway between these clusters. Once the initial clustering phrase takes place, cluster heads and cluster members must exchange message to maintain the relationship periodically.

And the cluster members of the attached cluster broadcast cluster member node ID, cluster IDs messages back to the cluster head periodically, where the node ID is the identifier of the broadcasting node, and cluster ID is the list of clusters of which the node is a member.

When topology changes, we can deal with it according to the three cases as follows. A cluster member would dissociate from the attached cluster, if it does not hear periodic broadcast from its cluster head. Likewise, the cluster head will remove the cluster member from its list of members, if it does not receive the periodic cluster member broadcasts. When a node, including new coming or dissociated from other clusters, wants to join a cluster, it should send RTJ to a cluster head, and the cluster head will send a ATJ message back only if the requesting node is allowed to join.

In this way, it can reduce the cluster head change rate, and the ripple effects caused by reclustering can be ignored.

Hence the routing overhead will be decreased. Once a cluster head leaves its own cluster or is damaged, the node belonging to this cluster would return to the NULL state. Thus, they should request joining other clusters or establish a new cluster. Note that only when the node receives more than two consecutive RTJ messages from another certain node, should they establish a new cluster.

When a cluster enters the transmission range of another cluster and the variance of cost metric of the two cluster heads is small, which denotes that the two clusters are worth merging. If so, the cluster head which has bigger metric will be reelected as the new cluster head, but the similar one must give up its cluster head role to be a common member of the new cluster.

Otherwise, it denotes that the two clusters just incidentally pass by each other in a short period and it is not worthy of merging. In this way, it can reduce the probability of cluster overlapping. In order to utilize the network resources efficiently, HCA-R absorbs the quintessence of ZRP to use proactive strategy between nodes within individual clusters and reactive strategy between clusters, not like CBRP to use on-demand strategy between nodes of both intracluster and intercluster communication to purely decrease the routing overhead and HSR, CGSR to use table-driven strategy to communicate in both intra- and interzone to decrease average end-to-end delay but increase the cost of routing overhead unwillingly.

In HCA-R, unless necessary, it will not activate the routing update process as far as possible to avoid additional expenses in both intracluster and intercluster communication and route maintenance phrase.

Its flow diagram is described in Figure 3. If the source and destination are in the same cluster, the data packet can be transmitted directly or relayed by cluster head. Namely, when the destination is in the range of source, source and destination can communicate with each other directly or relayed by cluster head.

Otherwise, source and destination must exchange data through cluster head. For example, in Figure 4 , source node 1 and destination 5 are in the same cluster. So node 1 can send data packet to node 5 relayed by the cluster head i. If not, node 1 must send data packet to node 5 relayed by the cluster head i.

If the source and destination are in the different clusters, the source must take the intracluster strategy. Namely, at first, the source sends a REQ request message to its attached cluster head and then the cluster head will broadcast this REQ to its adjacent cluster head through gateway nodes, and the process will continue until the REQ arrives at the cluster which belongs to the destination node.


A Clustering Routing Protocol for Mobile Ad Hoc Networks

Skip to Main Content. A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. Use of this web site signifies your agreement to the terms and conditions. Personal Sign In. For IEEE to continue sending you helpful information on our products and services, please consent to our updated Privacy Policy.


Routing Protocols for Ad Hoc Mobile Wireless Networks


Related Articles