Resource management for distributed real -time systems
Recent advances in embedded sensor systems and wireless technologies have made it possible to conceive a new type of real-time application---distributed real-time sensor systems. Examples of such systems include surveillance applications, distributed industrial control systems, disaster response systems and robotic applications, just to name a few. In addition to the requirements of providing temporal guarantees, these distributed embedded systems are normally associated with extreme resource constraints, both in computation and communication.
In this dissertation, we investigate some of the fundamental resource management problems that arise in the design and development of distributed real-time sensor systems. We consider a scenario in which a team of robots collaborating with each other to rescue people from a building on fire. The coordinated behavior is achieved by assigning a set of control tasks, or strategies, to robots in a team. At each step, the application may have many functionally equivalent strategies, though some of them may not be feasible, given limited resource and time availability. In order to accomplish dynamic feasibility checking and improve system performance, we propose efficient resource allocation mechanisms. Our approaches not only minimize the communication cost, but also minimize and balance the workload of each processor, resulting in good performance with regards to system schedulability and feasibility.
With respect to real-time communication in sensor applications, each message will traverse multiple hops from the source to the destination with an end-to-end deadline. In order to provide timeliness guarantees, a key challenge is to bound the delay and prioritize per-hop transmission. However, existing wireless protocols such as 802.11 families may suffer from unpredictable delays, due to collision, back-off and false blocking problems. In this study, after showing that the problem of scheduling all wireless transmissions to meet deadlines is NP-hard, we derive effective deadline for each per-hop transmission and schedule the most urgent message. We develop novel algorithms to parallelize message transmissions. By carefully exploiting spatial reuse property and avoiding collisions, the deadline misses are minimized. Extensive simulations demonstrate the effectiveness of our approaches, especially under high channel contention environments.