Conflict-free many-to-one data aggregation in multi-channel multi-hop wireless networks
Deying Li, QingHua Zhu, Yuqing Zhu, Hongwei Du, Weili Wu · International Journal of Sensor Networks · 2015
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.