10-08-2012, 02:59 PM
Survey of clustering algorithms for MANET
ABSTRACT
Many clustering schemes have been proposed for ad hoc networks. A systematic classification of these clustering schemes enables one to better understand and make improvements. In mobile ad hoc networks, the movement of the network nodes may quickly change the topology resulting in the increase of the overhead message in topology maintenance. Protocols try to keep the number of nodes in a cluster around a pre-defined threshold to facilitate the optimal operation of the medium access control protocol. The cluster head election is invoked on-demand, and is aimed to reduce the computation and communication costs. A large variety of approaches for ad hoc clustering have been developed by researchers which focus on different performance metrics.
Advantages:
• It is known that a cluster-based MANET has many important issues to examine, such as the cluster structure stability, the control overhead of cluster construction and maintenance, the energy consumption of mobile nodes with different cluster-related status, the traffic load distribution in clusters, and the fairness of serving as cluster heads for a mobile node.
Disadvantages:
• Simulation results of each algorithm was not included
EXISTING SYSTEM:
Existing clustering approaches are as follows. Low-Maintenance Clustering approach provides a stable cluster structure incurring less maintenance cost. In Lowest-ID, elect the node as a cluster head that has the lowest ID relative to its neighbors. Maximum Connectivity Clustering (MCC) approach uses the degree of connectivity instead of the node ID in the cluster head election. Mobility-Based Clustering: approach considers mobility feature of the mobile nodes for cluster formation. It achieves maximum cluster stability by grouping mobile nodes of similar patterns into a single cluster. a) MOBIC: uses the mobility metric as a basis of cluster formation and cluster head selection. Existing key management techniques are as follows. In CGKD, there exists a central entity (i.e. a group controller (GC)) which is responsible for generating, distributing, and updating the group key e.g. Logical Key Hierarchy (LKH) and One Way Function (OFT). The DGKM approach involves splitting a large group into small subgroups. Each subgroup has a subgroup controller which is responsible for the key management of its subgroup .e.g. IOLUS.
PROPOSED SYSTEM:
The combination of Weight based Clustering and RSA algorithm for secure multicast key distribution is applied, in which source node uses Ad hoc On-Demand Distance Vector (AODV) routing protocol to reach its destination. The Cluster Head is responsible for cluster management, membership maintenance and Group Key Distribution and updations. Initially, all the nodes are assigned an id, its private key and public key. Cluster Head is selected based on Weight Based Algorithm by using various metrics. The Weight based clustering approach is based on combined weight metric that takes into account of several system parameters like the degree difference of the node, transmission range, battery power and mobility of the node. Re keying is done by Cluster Head whenever any node joins or leaves the network to ensure backward secrecy (i.e., a new member should not know the previous information that was exchanged) and forward secrecy (i.e., an existing member should not receive the information exchanged after it eaves the network) Key management is an essential cryptographic primitive upon which other security primitives such as privacy, authenticity and integrity are built.. Distributed/Contributory group Key Agreement (CGKA) approach is used for establishing the group key by the contribution of cluster members.
INTRODUCTION:
Wireless Mobile Ad hoc Networks (WMANETs) are deployed in difficult environments where interruption of connectivity is consistent occurrences. Wireless Mobile Ad hoc Networks (WMANETs) are infrastructure less, multi-hop, dynamic networks for a collection of heterogeneous mobile nodes. It consists of autonomous nodes that communicate with each other, most frequently using a multi-hop wireless network. Nodes do not necessarily know each other and come together to form an ad hoc group. Key management is a basic part of any secure communication. Secure group communication (SGC) is defined as the process by which members in a group can securely communicate with each other and the information being shared is inaccessible to outside members. In such a scenario, a group key is established among all the participating members and this key is used to encrypt all the messages destined to the group. As a result, only the group members can decrypt the messages. Due to dynamic behavior of the MANET, secret key used for communication is need to be updated whenever any node joins or leaves the network in order to maintain the forward and backward secrecy with in the network. If the network is large and the mobility is higher, key updating is a frequent phenomenon. It also consumes more battery power. In order to manage the energy utilization, a network is divided into clusters by using Weight based Clustering and the keys are generated.
Weight computation:
Initially each node is assigned a random ID value. It broadcasts its ID value to its neighbors and builds its neighborhood table. Each node calculates its own weight based on the following factors like Node degree difference, Energy remaining, Mobility, distance from all other neighboring nodes. The distance between nodes and mobility is considered to keep the balance between clusters. The weight computation W for all the weights is based on Degree Difference of node, Energy in each node represented by Joules, Mobility of each node. (Less mobility nodes have more probability to become a CH), Distance from all other neighboring nodes.
Wn=W1*dn+W2*En-W3*Mn+W4*Dn
The co-efficient used in weight calculations 0.5, 0.35, 0.05, 0.1 the sum of these co-efficient is 1. The factors degree difference and energy are given more importance and assumed higher co-efficient values 0.5 and 0.35. The combined weight is calculated by using the parameters of. After finding its own weight, each node broadcasts its weight to its neighbors based on neighborhood table. The neighborhood table consists of one hop reachable nodes; its weights. It is maintained by the CH. Degree difference is defined as the difference between the cluster size N and the actual number of neighbors n d. In order to find the Degree n d of the node ‘n’ by counting its neighbors. Energy in each node represented by Joules. It is represented by n E - Energy (Battery Power) of node ‘n’. Energy n E is calculated as n E = E0 - residual E. E0 and residual E are initial and remaining energy of node ‘n’ Less mobility nodes have more probability to become a CH. Mobility is based on the co-ordinate positions of node ‘n’ at time t and t-1, T= cumulative time. Distance from all other neighboring nodes is represented by n D is calculated as the sum of the distance between member nodes and its neighbors
Cluster head election and cluster formation
After calculation of weight each node broadcast its weight value and its Id to all its Neighboring nodes and the neighborhood table updated with weight value. Cluster Head (CH) and Secondary Cluster Head (SCH) elected based on the weight value If the Node have with highest weight value then it is elected as a CH The Node with next highest weight is elected as a SCH. Ordinary nodes send Join Request to CH. SCH monitor the battery level of CH for every 30s. If the battery level of CH is less than Minimum Threshold Level) SCH will become New CH and it sends CH_LIFE DOWN Msg to all member nodes. Election procedure initiated to find new SCH.
Group key generation and distribution:
After Weight Computation and cluster formation, members in the clusters will send its id and public key. Cluster Head receive the message and initiate the group key calculation by using RSA. CH gets public keys of all nodes present in the cluster. CH calculate group key using prime number, primitive root of p, secret Key of cluster head, public Keys of individual nodes within the cluster, secret random value generated every time while re-keying. The distribution of group key is done using RSA algorithm. Cluster head having (e, n) public key and every node maintains (d, n) private key. CH encrypts the group key using (e, n) public key and sends to each node in the cluster. Each node decrypts the key using its private key pair. When ever any new node joins into the cluster, Cluster Head calculates new group key and multicast to already existing nodes. Cluster Head unicast the group key to new node along with private key using RSA algorithm.
Performance Evaluation:
The total energy consumption and Packet Delivery Ratio of total network are compared between without and with clusters. Data Packet Delivery Ratio can be calculated as the ratio between the number of data packets that are sent by the source and the number of data packets that are received by Destination. The difference in the delivery ratios increases as the network’s size increases, which shows the performance gained because of Weight based Clustering scheme. In the case of energy consumption, initially both the protocols consuming energy almost the same but after some simulation time, there is a change in energy consumption of two protocols. So, the proposed protocol weighted Clustering algorithm which can save more energy better than other Clustering algorithms.
CONCLUSION:
Weight based Clustered Key Management scheme using RSA for Wireless Mobile Ad hoc Networks has bees proposed. This approach is based on combined weight metric that takes into account of several system parameters like the degree difference of the node, transmission range, battery power and mobility of the sensor node. Since energy utilization is the most important criteria in cluster based routing schemes, our protocol provides better results than existing Lowest-id, WCA algorithm and LEACH algorithm. Performance metrics like network size with Packet delivery Ratio, Energy Consumption have been evaluated between with clustering and without clustering.