A survey of sensory data boundary estimation,covering and tracking techniques using collaborating sensors

Boundary estimation and tracking have important applications in the areas of environmental monitoring and disaster management. A boundary separates two regions of interest in a phenomenon. It can be visualized as an edge if there is a sharp change in the field value between the two regions or alternatively, as a contour with a field value $f=\tau$ separating two regions with field values $f>\tau$ and $f<\tau$. Examples include contours/boundaries of hazardous concentration in a pollutant spill, frontal boundary of a forest fire, isotherms, isohalines etc. Recent advances in the area of embedded sensor devices and robotics have led to deployments of networks of sensors capable of sensing, computing, communication and mobility. They are used to estimate the boundaries of interest in physical phenomena, monitor or track them over time and also in some cases, mitigate the spatial spread of the phenomena. Since these sensors work autonomously in the environment, minimizing the energy consumed while maximizing the accuracy of estimation or tracking is the main challenge for algorithms for boundary estimation and tracking. Several algorithms with these objectives have been proposed in the literature. In this work, we focus on the algorithms that estimate and cover boundaries found in the sensory data in a field and not the topological boundary of the sensor network per se, which is beyond the scope of this paper.Here, our objective is to provide a comprehensive survey of the algorithms for boundary estimation and tracking by providing a taxonomy based on two broad categories — (i) Boundary estimation and tracking, where the sensors estimate the boundary without physically covering the boundary and (ii) Boundary covering — where the sensors not only predict the location and estimate the entire boundary but also physically cover the boundary by surrounding and bounding it. We further classify the techniques based on (a) sensing capabilities —in situ, range or remote sensing (b) movement capabilities — static or mobile sensors and (c) boundary type — static or dynamic and (d) type of estimation — field estimation where the entire field is sampled to search for contours and localized estimation where sampling is done near the boundary and (e) different types of mobility models in the case of mobile sensors. We believe that such a survey has not been performed before. By capturing and classifying the current state-of-the-art and identifying open research problems, we hope to ignite interest and stimulate efforts towards promising solutions for real-world boundary estimation and tracking problems.     

New Algorithms for Resource Reclaiming from Precedence Constrained Tasks in Multiprocessor Real-Time Systems

The scheduling of tasks in multiprocessor real-time systems has attracted many researchers in the recent past. Tasks in these systems have deadlines to be met, and most of the real-time scheduling algorithms use worst case computation times to schedule these tasks. Many resources will be left unused if the tasks are dispatched purely based on the schedule produced by these scheduling algorithms, since most of the tasks will take less time to execute than their respective worst case computation times. Resource reclaiming refers to the problem of reclaiming the resources left unused by a real-time task when it takes less time to execute than its worst case computation time. In this paper, we propose two algorithms to reclaim these resources from real-time tasks that are constrained by precedence relations and resource requirements, in shared memory multiprocessor systems. We introduce a notion called a restriction vector for each task which captures its resource and precedence constraints with other tasks. This will help not only in the efficient implementation of the algorithms, but also in obtaining an improvement in performance over the reclaiming algorithms proposed in earlier work [[2]]. We compare our resource reclaiming algorithms with the earlier algorithms and, by experimental studies, show that they reclaim more resources, thereby increasing the guarantee ratio (the ratio of the number of tasks guaranteed to meet their deadlines to the number of tasks that have arrived), which is the basic requirement of any resource reclaiming algorithm. From our simulation studies, we demonstrate that complex reclaiming algorithms with high reclaiming overheads do not lead to an improvement in the guarantee ratio.     

Priority inheritance in soft real-time databases

Due to resource sharing among tasks, priority inversion can occur during priority-driven preemptive scheduling. In this work, we investigate solutions to the priority inversion problem in a soft real-time database environment where two-phhse locking is employed for concurrency control. We examine two basic schemes for addressing the priority inversion problem, one based on priority inheritance and the other based on priority abort. We also study a new scheme, called conditional priority inheritance, which attempts to capitalize on the advantages of each of the two basic schemes. In contrast with previous results obtained in real-time operating systems, our performance studies, conducted on an actual real-time database testbed, indicate that the basic priority inheritance protocol is inappropriate for solving the priority inversion problem in real-time database systems. We identify the reasons for this performance. We also show that the conditional priority inheritance scheme and the priority abort scheme perform well for a wide range of system workloads.This work was supported by the National Science Foundation under Grant IRI-8908693 and by the U.S. Office of Naval Research under Grant N00014-85-K0398.A previous version of this paper appeared in Real-Time Systems Symposium, Dec. 1991.     

To Schedule or to Execute: Decision Support and Performance Implications

This paper addresses a fundamental trade-off in dynamic scheduling between the cost of scheduling and the quality of the resulting schedules. The time allocated to scheduling must be controlled explicitly, in order to obtain good-quality schedules in reasonable times. As task constraints are relaxed, the algorithms proposed in this paper increase scheduling complexity to optimize longer and obtain high-quality schedules. When task constraints are tightened, the algorithms adjust scheduling complexity to reduce the adverse effect of long scheduling times on the schedule quality. We show that taking into account the scheduling time is crucial for honoring the deadlines of scheduled tasks. We investigate the performance of our algorithms in two scheduling models: one that allows idle-time intervals to exist in the schedule and another that does not. The model with idle-time intervals has important implications for dynamic scheduling which are discussed in the paper. Experimental evaluation of the proposed algorithms shows that our algorithms outperform other candidate algorithms in several parameter configurations.     

Guest Editors' Introduction: Dynamic Information Dissemination

Dissemination and delivery of rapidly changing information to large user communities remains a challenge on the Web. Consequently, we need techniques to disseminate such data as efficiently as possible. To this end, researchers are focusing on new approaches to building efficient, resilient, and scalable content-distribution networks.     

A local area network architecture for communication in distributed real-time systems

Distributed real-time systems of the future will require specialized network architectures that incorporate new classes of services and protocols in order to support time-constrained communication. In this paper, we propose a new local area network architecture for such systems. This four-layered architecture is characterized by new classes of connection-oriented and connectionless services that take into account the timing constraints of messages. We describe various aspects of the logical link control layer of the architecture and various real-time protocols that may be employed at the medium access control layer in order to support the new classes of services. We also describe a homogeneous approach to the implementation of medium access control protocols to support both connection-oriented and connectionless services, based on a uniform window splitting paradigm.     

A taxonomy of correctness criteria in database applications

Whereas serializability captures database consistency requirements and transaction correctness properties via a single notion, recent research has attempted to come up with correctness criteria that view these two types of requirements independently. The search for more flexible correctness criteria is partily motivated by the introduction of new transaction models that extend the traditional atomic transaction model. These extensions came about because the atomic transaction model in conjunction with serializability is found to be very constraining when used in advanced applications (e.g., design databases) that function in distributed, cooperative, and heterogeneous environments. In this article we develop a taxonomy of various correctness criteria that focus on database consistency requirements and transaction correctness properties from the viewpoint of what the different dimensions of these two are. This taxonomy allows us to categorize correctness criteria that have been proposed in the literature. To help in this categorization, we have applied a uniform specification technique, based on ACTA, to express the various criteria. Such a categorization helps shed light on the similarities and differences between different criteria and places them in perspective. Edited by Hector Garcia-Molina. Received September 16, 1993 / Revised June 13, 1994 / Accepted September 17, 1994     

What is predictability for real-time systems?

Conclusion In summary, predictability in real-time systems has been defined in many ways. For static real-time systems we can predict the overall system performance over large time frames (even over the life of the system) as well as predict the performance of individual tasks. If the prediction is that 100% of all tasks over the entire life of the system will meet their deadlines, then the system is predictable without resorting to any stochastic evaluation. In dynamic real-time systems we must resort to a stochastic evaluation for part of the performance evaluation. Predictability for these systems should mean that we are able to satisfy the timing requirements of critical tasks with 100% guarantee over the life of the system, be able to assess overall system performance over various time frames (a stochastic evaluation), and be able to assess individual task and task group performance at different times and as a function of the current system state. If all these assessments meet the timing requirements, then the system is predictable with respect to its timing requirements.This work was supported by ONR under contract N00014-85-K-0389 and NSF under grants DCR-8500332 and IRI-8908693.     

An architecture to support scalable online personalization on the Web

Online personalization is of great interest to e-companies. Virtually all personalization technologies are based on the idea of storing as much historical customer session data as possible, and then querying the data store as customers navigate through a web site. The holy grail of online personalization is an environment where fine-grained, detailed historical session data can be queried based on current online navigation patterns for use in formulating real-time responses. Unfortunately, as more consumers become e-shoppers, the user load and the amount of historical data continue to increase, causing scalability-related problems for almost all current personalization technologies. This paper chronicles the development of a real-time interaction management system through the integration of historical data and online visitation patterns of e-commerce site visitors. It describes the scientific underpinnings of the system as well as its architecture. Experimental evaluation of the system shows that the caching and storage techniques built into the system deliver performance that is orders of magnitude better than those derived from off-the-shelf database components. Received: 30 October 2000 / Accepted: 19 December 2000 Published online: 27 April 2001