Parallel cluster formation for secured communication in wireless ad hoc networks

Routing protocols in wireless ad hoc network are highly insecure and prone to various attacks owing to its inherent characteristics of open medium, dynamically changing topologies and distributed cooperation between the member nodes. Having a secure routing protocol in wireless ad hoc networks appears to be a problem that is not trivial to solve. In this paper we mainly consider the vulnerabilities of cluster based routing protocol (CBRP), which uses formation of clusters with a single cluster head. In CBRP, cluster head has the responsibility of maintaining the cluster member list, routing the packets from the cluster members and can also be a certification authority (CA) for distribution of certificates. However a single cluster head in CBRP can be a single point of failure and can also become malicious or selfish and as a result the whole system can become paralyzed. We propose a scheme and algorithm in which we distribute the cluster head service to a group of cluster heads called council. Each council node will have equal functionality and utilize the (k, n) threshold secret sharing scheme for performing the cluster head functionality. One of the main functionality of council will be key distribution. A certificate will be formed by participation of at least k nodes out of n council member. The cluster head functionality will now be able to work even when more than one (but limited to min {k, n-k+1}) cluster heads are compromised. Simulation results of our proposed algorithm for formation of such council based clusters demonstrates that our scheme is more fault tolerant and efficient than CBRP.