Abstract: In Wireless Sensor Networks which consist of tiny
wireless sensor nodes with limited battery power, one of the most
fundamental applications is data aggregation which collects nearby
environmental conditions and aggregates the data to a designated
destination, called a sink node. Important issues concerning the
data aggregation are time efficiency and energy consumption due
to its limited energy, and therefore, the related problem, named
Minimum Latency Aggregation Scheduling (MLAS), has been the
focus of many researchers. Its objective is to compute the minimum
latency schedule, that is, to compute a schedule with the minimum
number of timeslots, such that the sink node can receive the
aggregated data from all the other nodes without any collision or
interference. For the problem, the two interference models, the graph
model and the more realistic physical interference model known as
Signal-to-Interference-Noise-Ratio (SINR), have been adopted with
different power models, uniform-power and non-uniform power (with
power control or without power control), and different antenna
models, omni-directional antenna and directional antenna models.
In this survey article, as the problem has proven to be NP-hard,
we present and compare several state-of-the-art approximation
algorithms in various models on the basis of latency as its
performance measure.
Abstract: In this paper, we study the Minimum Latency Broadcast
Scheduling (MLBS) problem in wireless sensor networks (WSNs).
The main issue of the MLBS problem is to compute schedules
with the minimum number of timeslots such that a base station can
broadcast data to all other sensor nodes with no collisions. Unlike
existing works that utilize the traditional omni-directional WSNs,
we target the directional WSNs where nodes can collaboratively
determine and orientate their antenna directions. We first develop
a 7-approximation algorithm, adopting directional WSNs. Our ratio
is currently the best, to the best of our knowledge. We then validate
the performance of the proposed algorithm through simulation.
Abstract: In this paper, we study the data collection problem in
Wireless Sensor Networks (WSNs) adopting the two interference
models: The graph model and the more realistic physical interference
model known as Signal-to-Interference-Noise-Ratio (SINR). The
main issue of the problem is to compute schedules with the minimum
number of timeslots, that is, to compute the minimum latency
schedules, such that data from every node can be collected without
any collision or interference to a sink node. While existing works
studied the problem with unit-sized and unbounded-sized message
models, we investigate the problem with the bounded-sized message
model, and introduce a constant factor approximation algorithm.
To the best known of our knowledge, our result is the first result
of the data collection problem with bounded-sized model in both
interference models.