An Enhanced Distributed Weighted Clustering Algorithm for Intra and Inter Cluster Routing in MANET

Abstract

Especially MANETs deployed in hostile environments where hackers will try to disturb the secure data transfer and drain the valuable network resources. Since MANET is a battery operated network, preserving the network resource is necessary one. For resource constrained computation, efficient routing and to increase the network stability, the network is divided into smaller groups called clusters. The clustering architecture consists of Cluster Head(CH), ordinary node and gateway. CH election is a prominent research area and many more algorithms are developed using many metrics. To nominate efficient CH, an Enhanced Distributed Weighted Clustering Algorithm (EDWCA) has been proposed. The CH with longer life sustains network lifetime, for this purpose Secondary Cluster Head(SCH) also elected. This approach considers metrics like distance, battery power, degree difference and speed of the node for CH election. The proficiency of proposed one is evaluated and compared with existing algorithm Distributed Weighted Clustering Algorithm(DWCA) using Network Simulator(NS-2).

Keywords

MANET, EDWCA, Clustering, Cluster head, Secondary cluster head

INTRODUCTION

The MANET is a self-directed , short-lived association of mobile nodes that communicate with each other via wireless channel and by using intermediate nodes. It form the networks without any fixed infrastructure or centralized administration. Networking these mobile nodes are expected to have significant impact on the efficiency of many military, emergency, commercial, educational, entertainment and civil applications. Since the nodes are energy constrained, links are bandwidth constrained and the topology changes in unpredictable manner, the routing in MANET is a tedious task.

The routing can be done in two ways either by using flat structure or by using hierarchical structure. the flat structure routing is more suitable for smaller and stable network and here all the nodes take same role and responsibility. the hierarchical structure routing well suitable for larger and dynamic network like MANET and here nodes assigned with different role and they take different responsibilities.

The Clustering is the process of dividing the network into smaller groups( geographically close nodes) in hierarchical manner is known as cluster. This type of routing reduces the control traffic exchanged between the nodes. Each cluster consists of three different types of nodes, they are one cluster head, one or two gateway node and many ordinary nodes. CH manages all activities associated with its cluster member. Gateway is a intermediate node that exchanges information between the clusters. Ordinary nodes are simple nodes for data gathering.

Recently many clustering algorithms are proposed by the researchers and our algorithm is enhanced version of distributed weighted clustering algorithm. If in case entire battery drains in the CH, that leads to life down of CH and that particular cluster becomes isolated.[1] This critical situation is handled by our proposed Enhanced Distributed Weighted Clustering Algorithm (EDWCA) by having Secondary Cluster Head(SCH) and Gateway nodes. SCH will take the role of CH , and manages cluster activities.

In our work Cluster Head is elected based on the metrics like distance, battery power, degree difference and speed of mobile node. The Clustering Architecture of Mobile nodes are given in the Fig. 1.

The remainder of this paper is organized as follows. Section 2 presents related work done in cluster formation and cluster head election mechanisms. Section 3 presents the proposed data transmission architecture and routing schemes in both intra cluster and inter cluster. Section 4 presents performance evaluation and finally, Section 5 presents conclusions and future work.

II. REVIEW OF LITERATURE: WEIGHTED CLUSTERING ALGORITHMS

 Naveen Chauhan et. al,[2] proposed A Distributed Weighted Cluster Based Routing Protocol for MANETs, in this CH selected based on combined weight metrics that takes several system parameters like the node degree, transmission range, energy and mobility. CH is responsible routing among clusters. In this algorithm if in case of CH sudden death there is no alternate for handling the situation.

 Wojciech Bednarczyk,Piotr Gajewskil [3] proposed An enhanced Algorithm for MANET clustering based on Weighted parameters, in this approach CH election considers Degree of the node, received power level, stationary factor and remaining battery level. This algorithm is applicable for different scenarios by changing the weight factors.

 Sahar Adabi et al,[4] proposed "A Novel Distributed Clustering Algorithm for Mobile Adhoc Network",in this(DSBCA) each node calculate its score by linear algorithm, based on battery remaining, number of neighbours, number of members and stability. The node's neighbors are notified about the score value. The scores compared and the node with highest score elected as CH.

 Rani V. G and Punithavalli M.[5] proposed MPBCA: Mobility Prediction based Clustering Algorithm for MANET, in this approach node with smallest weight elected as CH based on distance,Mobility, Remaining Battery power and transmission range.In this slow moving nodes are identified and those will take the role of CH.

 Dahene Amne et.al[6] proposed, Energy Efficient and safe weighted clustering algorithm for Mobile sensor Networks, in this approach CH elected based on five metrics and they are behavior level, mobility, distance of a node from its neighbor, residual energy and degree of connectivity. In this approach behavior level(BL) is the key metric used for election. the BL calculated by using anomaly detection algorithm and misbehavior nodes are keep away from cluster.

 Muthuramalingam. S[7] et al proposed A Dynamic clustering Algorithm for MANETs by modifying Weighted clustering Weighted Clustering Algorithm with Mobility prediction, in this approach traditional WCA is used for CH election, but for cluster maintenance the mobility of the node is predicted by using linear auto regression. The mobility of the is predicted based on previous locations it visited.

 Tzung-Pei Hong and Cheng-Hsi[8] Wu proposed An Improved Weighted Clustering Algorithm for Determination of Application nodes in Heterogeneous Sensor Networks, in this paper an improved algorithm(IWCA) based on weighted clustering algorithm is proposed. Five factors are considered for electing CH, they are distance, degree difference, Mobility, Cumulative time (it act as CH) and new factor characteristic of the node. The node with minimum weight elected as CH.

III. PROPOSED ALGORITHM

Our proposed work consists of following modules like Initialization phase and Data transmission phase.

A. Initialization Phase

1) Weight computation:

In the beginning mobile node is assigned with unique ID. Each node broadcasts its ID value to its one hop mobile nodes and form a neighborhood table. Every nodes weight calculated based on multiple metrics like distance, Battery power, Node degree difference, and Mobility or speed of the node. The distance between nodes considered one hop in each cluster. The EDWCA performs clustering based on parameters described above and selects the Cluster Head for efficient clustering. The weight(Wn) of node 'n' is calculated by using (1) as follows

Wn = W1*En+W2*Δn –W3*Sn + W4*Dn (1)

En - Energy in node n represented by Joules

Δ n Degree Difference of node 'n'

Sn - Speed of node 'n'

Dn - Distance of node 'n' from its neighbour

W1,W2,W3 ,W4are co-efficient

The values assigned for these co-efficient are 1 0.08, 2 0.6, 3 0.02, 4 0.3 W  W  W  W  .The nodes with almost similar moving pattern are considered, so the speed co-efficient assigned with least value. The degree difference and distance considered most important, so they are assigned with higher values. The sum of these co-efficient is 1. The sum of distance, speed, Energy, degree difference are calculated as per DWCA. After finding its own weight, each node broadcasts its weight to its neighbors based on neighborhood table. The neighborhood table contains ID of one hop reachable nodes and its weights.

2) Cluster head election:

In this phase each and every node send Hello message to neighboring nodes, those are in its transmission range. The Hello message includes node ID and its weight value. When a node receives a predefined number (Np) of Hello packets, it compares all the weights received, the node with highest weight will be announced as a Cluster Head (CH),then the newly elected CH will broadcast a message that “I am a cluster-head (CH) ”. A failed CH may cause a cluster to remain isolated until the next re clustering. Meanwhile, important data from mobile nodes cannot be reported and may be lost. To avoid this problem, a Secondary Cluster Head (SCH) is also elected based on next highest weight. The SCH stores backup routing and cluster information.

3) Cluster formation:

In the Cluster formation, Cluster nodes members send their joining message like “I am Cluster member “to CH within the one- hop distance.CH will maintain the member’s list with member id and role (Ordinary node, SCH, Gateway node, neighbor CH) of the every mobile node. Suppose a node receives more than one CH message from different CH, then that will become a Gate Way node and it is responsible for inter-cluster communication. The flow for Cluster formation and data transmission is shown in Fig. 2.

B. Data Transmission Phase

This phase consists of sub modules like inter cluster and intra cluster communication. In intra cluster TDMA is used in order to avoid the congestion in the cluster heads. In the inter cluster communication, AODV protocol [12] is used in order to get the routes on demand and to minimize the memory usage in nodes.

1) Inter cluster routing:

CH uses a traditional AODV protocol and send RREQ message to search for a destination through a gateway to its neighbor clusters. To reduce the overhead caused by the RREQ flooding packet, only gateways and CHs are involved in forwarding the RREQ. No ordinary nodes are involved in RREQ packets in the inter-cluster communications will send RREP message to the concerned CH and neighborhood table is maintained.

IV. SIMULATION RESULTS AND DISCUSSION

In this paper, the NS-2 simulator [9] is used for the simulation to show the performance of the proposed method EDWCA with existing DWCA. The number of nodes used in the simulation results varies between 100 to 500 node network with randomly distributed nodes in a (750x750) meter area. The simulations were run for 450 seconds. The cluster size was fixed at 15. The simulation settings and parameters are described in Table 1.

 Packet Delivery Ratio (PDR)

Data Packet Delivery Ratio can be calculated as the ratio between the number of data packets that are received by the destination and the number of data packets that are sent by the source. PDR is always high for less traffic whereas when traffic increases the PDR will be decreased. Fig. 3. shows delivery ratio is high even in high traffic for EDWCA, when compared to DWCA.

 Delay:

This is the time taken to deliver the data from source to destination across the network. This depends upon the traffic in the network at the time of transfer. Initially when the simulation starts traffic is less so the delay also minimum and after some time due to the increased traffic the delay also increased in all network. Fig. 4. shows delay in transferring packet from source to destination for existing and proposed method. It shows that delay for EDWCA is lesser than DWCA.

 Total Energy Consumption

Fig. 5. illustrates the energy consumption of network in DWCA and EDWCA. We can see that the consumption energy of network with EDWCA is obviously lower than the DWCA. The mechanism of having SCH handle the situation of sudden death of CH and balance the load of CH.

 Packet drop

A packet drop occurs in various conditions,

 Due to congestion in the medium and broken link.

 Due to excess data in the transmission queue

 Due to lack of energy resources

 Due to the nasty act of a hackers.

Fig. 6. shows in our experiment packet drop is increased due to above reasons but comparing with DWCA packet drop is lesser in EDWCA.

V. CONCLUSION

This paper presents an Enhanced Distributed Weighted Clustering Algorithm(EDWCA) by making some modifications in DWCA . As demonstrated, our algorithm reduces control messages overhead by having SCH and Gateway node thus improving overall performance and reducing energy utilization. our protocol gives better results than existing DWCA in all the performance metrics like energy conservation, packet drop and PDR. In the future, this protocol can be extended to include group key management among clusters to provide secure transmission of collected data. We also intend to extend the clustering architecture to support multi-hop clustering in MANET. Effective utilization of power, Bandwidth, Stable Clusters helps in improving the quality of service in MANET by applying the EDWCA.

Tables at a glance

Table 1

Figures at a glance

Figure 1 Figure 2 Figure 3

Figure 4 Figure 5 Figure 6

References

1. Chia-Wei Wang," A Stable Clustering Algorithm Based on Battery Power for Mobile Ad Hoc Networks" Tamkang Journal of Science and Engineering, Vol. 9, No 3, pp. 233-242, (2006)
2. Naveen Chauhan et al.," A Distributed Weighted Cluster Based routing protocol for MANETs" Journal of Wireless sensor Network", Volume 3, pp 54-60, 2011
3. Wojciech Bednarczyk, Piotr Gajewskil," An enhanced Algorithm for MANET clustering based on Weighted parameters", Universal Journal of Communications and Network, vol 1, Issue 3, pp 88-94, 2013.
4. Sahar Adabi et al, "A Novel Distributed Clustering Algorithm for Mobile Adhoc Network", Journal of computer Science, volume 4, Issue 2, pp: 161-166, 2008.
5. Rani V. G and Punithavalli M. "MPBCA: Mobility Prediction based Clustering Algorithm for MANET"International Journal of Engineering and Technology,Vol 5, No 1, pp:403-409, 2013.
6. Dahane Amne, Berrached Nassreddine and Kechar Bouabdellah, " Energy Efficient and safe weighted clustering algorithm for Mobile sensor Networks", The 9th International Conference on future Networks and Communications(FNC 2014), Precedia Computer Science , pp: 63-70, 2014.
7. Muthuramalingam. S et al, " A Dynamic clustering Algorithm for MANETs by modifying Weighted clustering Weighted Clustering Algorithm with Mobility prediction", International Journal of Computer and Electrical Enginneering, Vol. 2, No. 4, pp 709-714, 2010.
8. Tzung-Pei Hong and Cheng-Hsi Wu, " An Improved Weighted Clustering Algorithm for Determination of Application nodes in Heterogeneous Sensor Networks", Journal of Information hiding and Multimedia Signal Processing, Ubiquitous International, Volume 2, Number 2, pp:173-184, 2011.
9. NS-2 simulator. Available online: http://www.isi.edu/nanam/ns