CISTER Seminar Series (Spring 2009)

Spring 2009 Presentation Schedule for CISTER Seminar Series

Biweekly meetings were held Wednesdays, 12PM.



February 11 - Arvind Easwaran, ISEP, Portugal - Hierarchical Scheduling Theory (Efforts at the University of Pennsylvania)

Talk abstract: Component-based engineering is a popular design strategy for multi-functional and complex real-time systems; it decomposes the system into simpler components and then composes them using interfaces that hide internal complexities. Since components also have time-constrained resource demand, this design leads to hierarchical real-time systems that share resources under a scheduling hierarchy. Due to resource-constrained operating environments, schedulability analysis of such hierarchical systems is an important problem that must be addressed in the design phase. Additionally, to preserve the principles of component-based engineering, this analysis must be compositional, i.e., system schedulability must be determined by composing interfaces that abstractly represent component resource requirements. In this talk, we present research efforts at the University of Pennsylvania, USA, on compositional schedulability analysis. We discuss two component interface models that were developed for this purpose; periodic and explicit deadline periodic (EDP) resource models.



Papers: Periodic Resource Model (pdf), EDP Resource Model (pdf)
Talk slides: pdf





February 25 - K. Bletsas, ISEP, Portugal - «Notional Processors: an approach for multiprocessor scheduling»

Talk abstract: Consider the problem of designing an algorithm with a high utilisation bound for scheduling sporadic tasks with implicit deadlines on identical processors. A task is characterised by its minimum interarrival time and its execution time. Task preemption and migration is permitted. Still, low preemption and migration counts are desirable. We formulate an algorithm with a utilisation bound no less than 66.6%, characterised by worst-case preemption counts comparing favorably against the state-of-the-art.

Paper: (in PDF format)





March 11 - Ricardo Severino, ISEP, Portugal - On the use of IEEE 802.15.4/ZigBee for Time-Sensitive Wireless Sensor Network Applications

Talk abstract: The work carried out in the Thesis focuses on the use of standard protocols (IEEE 802.15.4 and ZigBee) over commercial-off-the-shelf hardware (e.g. MICAz, TelosB, FLEX motes) and operating systems (TinyOS, ERIKA) for improving the Quality-of-Service (QoS) properties in Wireless Sensor Networks. It aims at closing the gap between theoretical/simulation work and the real world by performing a series of implementations, comparisons and validations based on analytical, simulation and experimental models on topics such as: (1) evaluation of the network performance of the IEEE 802.15.4 Slotted CSMA/CA mechanism; (2) validation of a mechanism to mitigate the hidden-terminal problem and its demonstration in a real application scenario; (3) experimental validation of a methodology for modeling cluster-tree WSNs and computing the worst-case end-to-end delays, buffering and bandwidth requirements. This Thesis also identifies a number of technological constrains, namely related to hardware/software and to the open-ZB IEEE 802.15.4/ZigBee protocol stack implementation in the TinyOS operating system, which triggered its migration to the ERIKA real-time operating system.

Thesis: pdf





April 8 - Nuno Pereira, ISEP, Portugal - WiDom - The Wireless Dominance Protocol and its Applications

The Wireless Dominance Protocol (WiDom), is a novel medium access control protocol designed for wireless systems to efficiently schedule sporadic message streams with real-time requirements. This protocol gives the wireless channel a similar behavior as a Controller Area Network (CAN) bus. It is prioritized and this can be achieved even without having the ability to listen and transmit simultaneously. WiDom is useful not only to provide timeliness guarantees, but it can also be a building block for certain distributed calculations. This is a crucial asset for addressing problems in future Large-Scale Cyber-Physical Systems.
Recently, it was demonstrated that highly scalable aggregate computations in wireless networks are possible by exploiting WiDom. This was achieved by (i) building a new wireless hardware platform with appropriate characteristics to make wireless dominance-based MAC protocols efficient, (ii) implementing dominance-based MAC protocols on this platform, (iii) implementing distributed algorithms for aggregate computations (MIN,MAX, Interpolation) using the new implementation of the dominance-based MAC protocol and (iv) performing experiments that prove that such highly scalable aggregate computations in wireless networks are possible.

Papers: pdf, pdf, pdf, pdf, pdf.
Talk slides:pdf





April 29 - Stefan M. Petters, ISEP, Portugal - Real Power Management

Managing the power consumption of computing platforms is a prohibitively complicated problem thanks to a multitude of hardware configuration options and characteristics. Much of the academic research is based on unrealistic assumptions, and has, therefore, seen little practical uptake. This talk will cover research which has been performed during my time at NICTA Ltd, a government funded Australian research institute. We will discuss the challenges and solutions in the general purpose computing and the real-time computing domains, as well as plans for future research at ISEP.

Papers: Accurate on-line prediction of processor and memory energy usage under voltage scaling, Integrating real time and power management in a real system, Koala: A platform for OS-level power management
Talk slides: pdf





May 6 - Shashi Prabh, ISEP, Portugal - Hexagonal Wireless Sensor Networks

The use of wireless sensor networks for real-time applications requires bounded end-to-end communication latency. Packet scheduling methods for multi-hop networks, where nodes exchange messages to construct conflict-free schedules, have been reported previously in the literature. Such methods, however, have been found to be prohibitively expensive for resource constrained wireless sensor networks. In this talk, we present logical hexagonal topology based wireless ad-hoc and sensor networks and discuss its features in the context of real-time applications. We describe a distributed algorithm that forms hexagonal backbone in an arbitrary but sufficiently dense WSN deployment.

Papers: On Scheduling and Real-Time Capacity of Hexagonal Wireless Sensor Networks
Talk slides: NA





May 20 - Mário Alves, ISEP, Portugal - WHYreless Sensor NOTworks? Our 2 cents for pushing the SOTA

Talk abstract: Networked embedded systems (NES) based on standard fieldbus technologies have been around for more than 20 years, particularly for process control, factory automation, domotics and automotive applications. Although the new paradigm of Wireless Sensor Networks was coined over one decade ago and lots of research has been done in this area, real-world WSNs applications are still: 1) of insignificant number; 2) of insignificant scale. To our best knowledge, real (academic-driven and temporary) WSN deployments were only up to a few hundred (e.g. VigilNet) to one thousand nodes (ExScal). In this talk, I try to identify why WSNs are not being massively used yet and what is being done at CISTER to overcome this situation.

Papers:Censor networks: a critique of sensor networks (pdf)
Talk slides: The wireless sensor networks standards and cots landscape: can we get QoS and ”calm technology”? (Tutorial)
More: The ART-WiSe Framework






June 17 - Björn Andersson, ISEP, Portugal - The Utilization Bound of Non-Preemptive Rate-Monotonic Scheduling in Controller Area Networks is 25%

Talk abstract: Consider a distributed computer system comprising many computer nodes, each interconnected with a Controller Area Network (CAN) bus. We prove that if priorities to message streams are assigned using rate-monotonic (RM) and if the requested capacity of the CAN bus does not exceed 25% then all deadlines are met.

Talk slides: pdf





June 26 - Vikarm Gupta, ISEP, Portugal - Syntonistor-Why it Hertz so Good. (A clock Synchronization Approach)

We present a novel low-power hardware module for achieving global clock synchronization by tuning to the electromagnetic energy radiating from existing AC power lines. This signal can be used as a global clock source for battery-operated sensor nodes to eliminate drift between nodes over time even when they are not passing messages. The frequency of the AC voltage is very stable over time and geographic area; and synchronization based on AC signal, in an ideal case will make sure that two nodes in an area under one common power grid may remain in sync for a long duration of time without exchange of any synchronizing message. There are three major issues which we address in the design of this module: 1. Hardware should consume as low power as possible 2. Eliminate Jitter in the received signal 3. Compensate for phase offset across different nodes in the tuned signal


Talk Slides: NA





July 8 - Jinkyu Lee, KAIST, Korea - Robust Optimization Framework for QoS Guarantees in Distributed Soft Real-Time Systems

In distributed soft real-time systems, maximizing the aggregate quality-of-service (QoS) is a typical system-wide goal, and addressing the problem through distributed optimization is challenging. Subtasks are subject to unpredictable failures in many practical environments, and this makes the problem much harder. In this paper, we present a robust optimization framework for maximizing the aggregate QoS in the presence of random failures. We introduce the notion of K-failure to bound the effect of random failures on schedulability. Using this notion we define the concept of K-robustness that quantifies the degree of robustness on QoS guarantee in a probabilistic sense. The parameter K helps to tradeoff achievable QoS versus robustness. The proposed robust framework produces optimal solutions through distributed computations on the basis of Lagrangian duality, and we present some implementation techniques. Our simulation results show that the proposed framework can probabilistically guarantee suboptimal QoS which remains feasible even in the presence of random failures.


Talk Slides: pdf