An Improved Data Collection Algorithm for Wireless Sensor Networks

An Improved Data Collection Algorithm for Wireless Sensor Networks

Vemula Manohar Reddy (Sam Houston State University, Huntsville, USA), Min Kyung An (Sam Houston State University, Huntsville, USA) and Hyuk Cho (Sam Houston State University, Huntsville, USA)
DOI: 10.4018/IJITN.2019040102

Abstract

This article studies the minimum latency collection scheduling (MLCS) problem in wireless sensor networks (WSNs). The MLCS problem targets to compute a schedule with minimum number of timeslots that guarantees to collect data from all nodes to a sink node without any collision. Several scheduling algorithms have been proposed for the NP-hard problem, and they assign timeslots based on hop distances among nodes. The proposed algorithm not only uses hop distances, but also partitions a network into square cells and assign timeslots based on cell distances among nodes. The latency performance of the proposed algorithm is compared with an existing algorithm whose approximation ratio is currently the best, and the simulations show that the proposed algorithm performs better.
Article Preview
Top

1. Introduction

A Wireless Sensor Network (WSN) is a distributed system comprised of a large number of sensor nodes which are small battery-powered devices. Nodes sense and collect nearby data, and the information gathered at each node is to be collected to a designated destination called a sink node. This process of data transfer from all nodes to a sink is commonly known as data collection, and it is one of the crucial applications of WSNs.

As nodes with limited energy have be utilized effectively for data collection, many researchers proposed various techniques to prolong the network lifetime by conserving the energy. During a data collection, collision can occur if a node receives data from more than one node at a given point of time. In such a case, the data should be retransmitted, which results in draining the energy of the node and also delaying the collection process. An interesting approach to avoid such collisions is to assign timeslots to each node. With a complete schedule with timeslots, nodes assigned the same timeslot can send data without any collisions, and thus unnecessary retransmission of data can be avoided. As the data collection is a periodic effort, obtaining a schedule with minimum latency, i.e., a schedule with a minimum number of timeslots, has been a fundamental issue.

To address the data collection problem, several approximation algorithms have been proposed. Assuming all nodes have a uniform transmission power level IJITN.2019040102.m01 which is equal to one unit (i.e., IJITN.2019040102.m02, for every node IJITN.2019040102.m03), Florens & McEliece (2003) designed a 3-approximation algorithm for tree networks, and Bonifaci, Korteweg, Marchetti-Spaccamela & Stougie (2006) also proposed a IJITN.2019040102.m04-approximation algorithm for general topologies. Then, Bermond, Galtier, Klasing, Morales & Perennes (2006) showed the NP-hardness result and proposed a IJITN.2019040102.m05-approximation algorithm. Later, Ergen & Varaiya (2010) showed its NP-completeness and introduced two heuristic algorithms. Bermond, Li, Nisse, Rivano & Yu (2013b) proposed a 3-approximation algorithm in grid networks. Bermond, Klasing, Morales, Pérennes & Reyes (2013a) addressed the problem in linear topologies and proposed an optimal algorithm when IJITN.2019040102.m06, IJITN.2019040102.m07, and IJITN.2019040102.m08. Kowalski, Nussbaum, Segal & Milyeykovski (2014) also studied the problem in linear topologies and proposed a IJITN.2019040102.m09-approximation algorithm. Note that the results in Florens & McEliece (2003), Bermond et al. (2006), Bonifaci et al. (2006), Ergen & Varaiya (2010), Bermond et al. (2013a, 2013b), and Kowalski et al. (2014), however, apply to special topologies or general graphs only where the distance between two nodes on a given communication graph is defined as the length (i.e., the number of edges) of a shortest path connecting them (An & Cho, 2015). Recently, An & Cho (2015) proposed a IJITN.2019040102.m10-approximation algorithm on communication graphs where the distance between two nodes is considered to be the Euclidean distance. Its approximation ratio of IJITN.2019040102.m11 is currently the best, to our knowledge.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 12: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing