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.

I. Introduction

IN a multi-hop Wireless Sensor Network (WSN) with continuous traffic, each sensor node introduces a data packet into the network at regular intervals, to send its data the sink node via intermediate nodes using multi-hop paths. Most of the energy of the battery powered sensor nodes is depleted in the process of data communication. When the battery power is exhausted, a node fails to operate and conventionally this ends the lifetime of the network. For a static network, it is obvious that due to the multi-hop sink-centric traffic pattern, nodes nearer to the sink will carry heavier traffic and will deplete their energy faster, creating energy holes [18], [19] around the sink. Hence, in a multi-hop WSN, it is a challenging issue to exploit energy of all the nodes uniformly so that the network lifetime [14], [16], [20] is maximized.