Page History: Publications

Björn Andersson, Nuno Pereira and Eduardo Tovar
12th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA'07) - To Appear
[pdf]

Consider a network where all nodes share a single broadcast domain such as a wired broadcast network. Nodes take sensor readings but individual sensor readings are not the most important pieces of data in the system. Instead, we are interested in aggregated quantities of the sensor readings such as minimum and maximum values, the number of nodes and the median among a set of sensor readings on different nodes. In this paper we show that a prioritized medium access control (MAC) protocol may advantageously be exploited to efficiently compute aggregated quantities of sensor readings. In this context, we propose a distributed algorithm that has a very low time and message-complexity for computing certain aggregated quantities. Importantly, we show that if every sensor node knows its geographical location, then sensor data can be interpolated with our novel distributed algorithm, and the message-complexity of the algorithm is independent of the number of nodes. Such an interpolation of sensor data can be used to compute any desired function; for example the temperature gradient in a room (e.g., industrial plant) densely populated with sensor nodes, or the gas concentration gradient within a pipeline or traffic tunnel.

Björn Andersson, Nuno Pereira and Eduardo Tovar
12th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA'07) - To Appear
[pdf]

Consider the problem of deciding whether a set of n sporadic message streams meet deadlines on a Controller Area Network (CAN) bus for a specified priority assignment. It is assumed that message streams have implicit deadlines and no release jitter. An algorithm to solve this problem is well known but unfortunately it time complexity is non-polynomial. We present an algorithm with polynomial time-complexity for computing an upper bound on the response times. Clearly, if the upper bound on the response time does not exceed the deadline then all deadlines are met. The pessimism of our approach is proven: if the upper bound of the response time exceeds the deadline then the response time exceeds the deadline as well for a CAN network with half the speed.

Björn Andersson, Nuno Pereira and Eduardo Tovar
IPP-HURRAY Technical Report - TR-061102
[pdf]

Consider a wireless sensor network where all nodes share a single broadcast domain. Sensor nodes take sensor readings but individual sensor readings are not very important. It is important however to compute aggregated quantities of these sensor readings. We show that a prioritized medium access control (MAC) protocol for wireless broadcast is useful for efficiently computing aggregated quantities. We present algorithms for computing aggregated quantities with a time complexity that is independent of the number of sensor nodes. We present algorithms for computing MIN and MAX and propose approximation algorithms for COUNT and MEDIAN. We show that if every sensor node knows its geographical position, then sensor data can be interpolated and the time complexity of this interpolation algorithm does not depend on the number of sensor nodes. Such an interpolation of sensor data can be used to compute any function desired; for example, the temperature gradient in a room densely populated with sensor nodes.