Article Preview
Top1. 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 
which is equal to one unit (i.e., 
, for every node 
), Florens & McEliece (2003) designed a 3-approximation algorithm for tree networks, and Bonifaci, Korteweg, Marchetti-Spaccamela & Stougie (2006) also proposed a 
-approximation algorithm for general topologies. Then, Bermond, Galtier, Klasing, Morales & Perennes (2006) showed the NP-hardness result and proposed a 
-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 
, 
, and 
. Kowalski, Nussbaum, Segal & Milyeykovski (2014) also studied the problem in linear topologies and proposed a 
-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 
-approximation algorithm on communication graphs where the distance between two nodes is considered to be the Euclidean distance. Its approximation ratio of 
is currently the best, to our knowledge.