Multiple sink deployment in multi-hop wireless sensor networks to enhance lifetime

For single sink multi-hop wireless sensor networks, the nodes close to the sink node forward the total network traffic to the sink. Hence, they exhaust their energy faster and energy-holes are formed near the sink node that reduces the lifetime of the network. To enhance the network lifetime and to reduce the packet delay, multiple sink node deployment strategies are proposed for better load balancing, where the network is partitioned into a number of subgraphs or clusters around unique sinks to gather data. For a large WSN, network lifetime is inversely proportional to the cluster diameter in terms of number of hops and the cost is directly proportional to the number of clusters i.e. the number of sinks. In this paper, a novel multi-sink deployment technique is proposed to optimize both the number of clusters and the cluster diameter, following a graph theoretic approach. Based on the classical random graph decomposition theorem [13], given a bound D on the cluster diameter, we propose a distributed greedy cluster-formation algorithm on randomly generated networks to generate a predefined number of clusters. Extensive simulation studies show that, the proposed algorithm generates clusters and the cluster diameter remains close to the bound D, in most of the cases.