Title: Conflict-free many-to-one data aggregation in multi-channel multi-hop wireless networks

Authors: Deying Li; Qinghua Zhu; Yuqing Zhu; Hongwei Du; Weili Wu

Addresses: Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China), MOE, School of Information, Renmin University of China, Beijing 100872, China ' Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China), MOE, School of Information, Renmin University of China, Beijing 100872, China ' Department of Computer Science, California State University, Los Angeles, CA 90032, USA ' Department of Computer Science and Technology and Shenzhen Key Laboratory of Internet Information Collaboration, Harbin Institute of Technology Shenzhen Graduate School, HIT Campus, Shenzhen 518055, China ' Department of Computer Science, University of Texas at Dallas, Richardson TX 75080, USA

Abstract: In this paper, we study the minimum latency conflict-free many-to-one data aggregation scheduling problem in multi-channel multi-hop wireless sensor networks: given a set of sensor nodes along with a base station, and a subset of this set as the source nodes, find a schedule with the minimal latency, in which the data from all source nodes can be transmitted to the base station and no conflict happens. We assign each sensor three parameters: the transmission range r, the interference range αr and the carrier sensing range βr, where α, and β are constants. λ ≥ 1 channels are available for communication. We design a centralised algorithm with latency bound as (⌈a/λ⌉ + 11⌈b/λ⌉)R + (Δ − 23)⌈b/λ⌉ − ⌈a/λ⌉ + 12, where a and b are two integer constants derived from α and β, Δ is the maximum degree of the network, and R is the latency's trivial lower bound. Our algorithm has an approximation ratio (⌈a/λ⌉ + 11⌈b/λ⌉). When λ=1, the performance ratio is a + 11b, which improves the result in Zhu et al. (2009). We evaluate our algorithm's performance through extensive simulations.

Keywords: conflict-free data aggregation; many-to-one data aggregation; minimum latency; multi-channel WSNs; wireless sensor networks; multi-hop WSNs; approximation algorithm; scheduling; transmission range; interference range; carrier sensing range; simulation.

DOI: 10.1504/IJSNET.2015.071382

International Journal of Sensor Networks, 2015 Vol.19 No.1, pp.1 - 10

Received: 19 Jan 2013
Accepted: 30 Mar 2013
Published online: 24 Aug 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article