Energy efficient path selection for mobile sink and data gathering in wireless sensor networks

Abstract

Mobile sink (MS) has drawn significant attention for solving hot spot problem (also known as energy hole problem) that results from multihop data collection using static sink in wireless sensor networks (WSNs). MS is regarded as a potential solution towards this problem as it significantly reduces energy consumption of the sensor nodes and thus enhances network lifetime. In this paper, we first propose an algorithm for designing efficient trajectory for MS, based on rendezvous points (RPs). We next propose another algorithm for the same problem which considers delay bound path formation of the MS. Both the algorithms use k-means clustering and a weight function by considering several network parameters for efficient selection of the RPs by ensuring the coverage of the entire network. We also propose an MS scheduling technique for effective data gathering. The effectiveness of the proposed algorithms is demonstrated through rigorous simulations and comparisons with some of the existing algorithms over several performance metrics.

Introduction

Wireless sensor network (WSN) has been a growing technology in the scientific domain due to its various applications such as environment monitoring, health care, target detection, disaster management and so on [1]. In a WSN, the sensor nodes (SNs) close to the base station (BS) are overburdened as they act as a bridge between the BS and the rest of the network for forwarding data to the BS. This results in rapid energy depletion of these SNs and leads to network partitioning. Such adverse circumstance is termed as hot spot problem [2] also known as sink hole or energy hole problem [3]. Studies [4] have shown that for a large WSN, while the SNs nearby the BS exhaust their energy, the far away SNs retain more than 90% of their energy. To overcome this situation, the concept of mobile sink (MS) has been conceived by the researchers [5], [6], [7]. Many researches have been carried out to design trajectory of the MS in which random [8] and controlled [9] mobility of the MS are considered. The random mobility suffers from buffer overflow and uncontrolled behavior of the MS. In controlled mobility, some researchers have proposed that the MS visits every SN to collect data [10], [11], [12] and thus conserves a considerable amount of SNs’ energy. However, it leads to longer path that the MS traverses and thus increases data delivery latency. The other technique is to allow the MS to visit a limited number of positions called rendezvous points (RPs) [13], [14] and collect data from the SNs using multi-hop communication [14], [15]. A model diagram for an RP based data collection by the MS is presented in Fig. 1.

The RP based trajectory alleviates the problem of longer path of the MS and thus minimizes data delivery latency. However, designing path of the MS is a challenging issue as it has impact on the network coverage, data delivery and network lifetime. For quick data delivery, it is desirable to minimize the path of the MS. To this end, this is worth noting that shorter the path length, larger will be the multi-hop communication, (i.e., higher will be the hop counts and larger will be the multi-hop path lengths). This will result in higher energy consumption of the SNs. On the other hand, larger the tour, lesser will be the hop counts and shorter will the multi-hop path lengths. Therefore, while designing the path of the MS, care must be taken so that there will be a trade-off between the path length of the MS and the multi-hop path lengths.

In this paper, we address this problem and propose two energy efficient algorithms, called reduced k-means (RkM) and delay bound reduced k-means (DBRkM) for RP based trajectory design of the MS. In the proposed methods, we initially create a set of potential positions using k-means clustering [16] over the set of SNs. Then we optimize it to obtain minimum number of RPs by applying certain criterion. However, contrary to RkM, DBRkM considers a delay bound parameter for the selection of RPs. The RkM formulates a path for the MS by minimizing overall hop counts and average hop distance. The DBRkM also determines the path by minimizing the same parameters along with delay bound consideration. We perform generous assessment on the proposed algorithms by comparing the results of RkM with k-means based approach and DBRkM with WRP [17] and CB [18] algorithms. We evaluate and analyze the performance of the proposed algorithms in terms of network lifetime, number of hop counts, average remaining energy and number of active nodes per round.

There exist several works that address the similar problem. However, contrary to the existing techniques, the proposed algorithms use three parameters which are totally different from the existing schemes. The algorithms emphasize to reduce the overall hop counts by selecting RPs nearby the range of most desirable distance and with highest neighboring SNs. They also minimize the total transmission distance by optimizing the average hop distance between the RPs and the SNs. To the best of our knowledge, none of the existing works have considered all such parameters. The work also provides an efficient data gathering scheme which effectively minimizes the buffer overflow problem.