Efficient Aggregate Computations in Large-Scale Dense Wireless Sensor Networks
Ref: HURRAY-TR-100905 Publication Date: 10, Sep, 2010
Efficient Aggregate Computations in Large-Scale Dense Wireless Sensor Networks
Ref: HURRAY-TR-100905 Publication Date: 10, Sep, 2010Abstract:
Assuming a world where we can be surrounded by hundreds or even thousands of inexpensive
computing nodes densely deployed, each one with sensing and wireless communication
capabilities, the problem of efficiently dealing with the enormous amount of information
generated by those nodes emerges as a major challenge. The research in this dissertation
addresses this challenge.
This research work proves that it is possible to obtain aggregate quantities with a timecomplexity
that is independent of the number of nodes, or grows very slowly as the number
of nodes increases. This is achieved by co-designing the distributed algorithms for obtaining
aggregate quantities and the underlying communication system. This work describes (i) the
design and implementation of a prioritized medium access control (MAC) protocol which
enforces strict priorities over wireless channels and (ii) the algorithms that allow exploiting
this MAC protocol to obtain the minimum (MIN), maximum (MAX) and interpolation of
sensor values with a time-complexity that is independent of the number of nodes deployed,
whereas other state-of-the-art approaches have a time-complexity that is dependent on the
number of nodes. These techniques also enable to efficiently obtain estimates of the number
of nodes (COUNT) and the median of the sensor values (MEDIAN).
The novel approach proposed to efficiently obtain aggregate quantities in large-scale,
dense wireless sensor networks (WSN) is based on the adaptation to wireless media of a MAC
protocol, known as dominance/binary countdown, which existed previously only for wired
media, and design algorithms that exploit this MAC protocol for efficient data aggregation.
Designing and implementing such MAC protocol for wireless media is not trivial. For this
reason, a substantial part of this work is focused on the development and implementation
of WiDom (short for Wireless Dominance) - a wireless MAC protocol that enables efficient
data aggregation in large-scale, dense WSN.
An implementation of WiDom is first proposed under the assumption of a fully connected
network (a network with a single broadcast domain). This implementation can be
exploited to efficiently obtain aggregated quantities. WiDom can also implement static priority
scheduling over wireless media. Therefore, a schedulability analysis for WiDom is also
proposed. WiDom is then extended to operate in sensor networks where a single transmission
cannot reach all nodes, in a network with multiple broadcast domains.
These results are significant because often networks of nodes that take sensor readings
are designed to be large scale, dense networks and it is exactly for such scenarios that the
proposed distributed algorithms for obtaining aggregate quantities excel. The implementation
and test of these distributed algorithms in a hardware platform developed shows that
aggregate quantities in large-scale, dense wireless sensor systems can be obtained efficientlly.
Document:
PhD Thesis, Universidade do Minho.
Braga, Portugal.
Record Date: 10, Sep, 2010