9294393
Decentralized control of discrete event systems with specializations to local control and concurrent systems
The decentralized supervisory control problem of discrete event systems under partial observation is studied in this paper. The main result of the paper is a necessary and sufficient condition for the existence of decentralized supervisors for ensuring. That the controlled behavior of the system lies in a given range. The contribution of the paper is (1) our setting of decentralized control generalizes the prior ones; (2) we present an alternative approach for solving the decentralized control problem, which leads to computational saving for concurrent systems and certain other systems; and (3) our generalized formulation and its solution lets us extend several of the existing results reported previously. The results of our paper are illustrated by an example of a simple manufacturing system.
6842097
Automated control synthesis for an assembly line using discrete event system control theory
The design of logic controllers for event-driven systems continue to rely largely on intuitive methods rather than on formal techniques. This approach results in a control code that requires extensive verification, is hard to maintain and modify, and may even fail at times. Supervisory control theory (SCT) provides a formal approach to logic control synthesis. In order to demonstrate the usefulness of the supervisory control theory in manufacturing systems, an educational test-bed that simulates an automated car assembly line has been built using LEGO/spl reg/ blocks. Finite state machines (FSMs) are used for modeling operations of the assembly line, and for the specifications that accomplish the task of successfully completing the assembly repeatedly. Using the technique of SCT, we derive a supervisor that enforces the specifications while offering the maximum flexibility of assembly. Subsequently a controller is extracted from the maximally permissive supervisor for the purpose of implementing the control by selecting, when possible, at most one controllable event from among the ones allowed by the supervisor. Testing to check the correctness of the control code is reduced, since the controller is guaranteed to enforce the specifications.
13974246
Decentralized failure diagnosis of discrete event systems
By decentralized diagnosis we mean diagnosis using multiple diagnosers, each possessing its own set of sensors, without involving any communication among diagnosers or to any coordinators. The notion of decentralized diagnosis is formalized by introducing the notion of codiagnosability that requires that a failure be detected by one of the diagnosers within a bounded delay. Algorithms of complexity polynomial in the size of the system and the nonfault specification are provided for: 1) testing codiagnosability, 2) computing the bound in delay of diagnosis, 3) offline synthesis of individual diagnosers, and 4) online diagnosis using them. The notion of codiagnosability and the above algorithms are initially presented in a setting of a specification language (violation of which represents a fault) and are later specialized to the case where faults are modeled as the occurrences of certain events. The notion of strong codiagnosability is also introduced to capture the ability of being certain about both the failure as well as the nonfailure conditions in a system within a bounded delay.
2162080
Harbor: software-based memory protection for sensor nodes
Many sensor nodes contain resource constrained microcontrollers where user level applications, operating system components, and device drivers share a single address space with no form of hardware memory protection. Programming errors in one application can easily corrupt the state of the operating system or other applications. In this paper, we propose Harbor, a memory protection system that prevents many forms of memory corruption. We use software based fault isolation ("sandboxing") to restrict application memory accesses and control flow to protection domains within the address space. A flexible and efficient memory map data structure records ownership and layout information for memory regions; writes are validated using the memory map. Control flow integrity is preserved by maintaining a safe stack that stores return addresses in a protected memory region. Run-time checks validate computed control flow instructions. Cross domain calls perform low-overhead control transfers between domains. Checks are introduced by rewriting an application's compiled binary. The sand-boxed result is verified on the sensor node before it is admitted for execution. Harbor's fault isolation properties depend only on the correctness of this verifier and the Harbor runtime. We have implemented and tested Harbor on the SOS operating system. Harbor detected and prevented memory corruption caused by programming errors in application modules that had been in use for several months. Harbor's overhead, though high, is less than that of application-specific virtual machines, and reasonable for typical sensor workloads.
34096561
Distributed Evolutionary Algorithm Search for Multiobjective Spanning Tree Problem
The problem of computing spanning trees along with specific constraints is mostly NP-hard. Many approximation and stochastic algorithms which yield a single solution, have been proposed. Essentially, the problem is multi-objective in nature, and a major challenge to solve the problem is to capture possibly all the (representative) equivalent and diverse solutions at convergence. In this paper, we formulate the generic multi-objective spanning tree (MOST) problem, and attempt to solve, in a novel way, with evolutionary algorithm (EA). We consider, without loss of generality, edge-cost and diameter as the two objectives. Since the problem is hard, and the Pareto-front is unknown, the main issue in such problem-instances is how to assess the convergence. We use a multiobjective evolutionary algorithm (MOEA) that produces diverse solutions without needing a priori knowledge of the solution space. We employ a distributed version of the algorithm and generate solutions from multiple tribes in order to have some approximation of the movement of the solution front. Since no experimental results are available for MOST, we consider two well known diameter-constrained spanning tree algorithms and modify them, for fair comparison, to yield a near-optimal solution-front. We observe that EA could provide superior solutions in the entire-range of the Pareto-front, which none of the existing algorithms could do.
1384171
Efficient Hybrid Security Mechanisms for Heterogeneous Sensor Networks
Many applications that make use of sensor networks require secure communication. Because asymmetric-key solutions are difficult to implement in such a resource-constrained environment, symmetric-key methods coupled with a priori key distribution schemes have been proposed to achieve the goals of data secrecy and integrity. These approaches typically assume that all nodes are similar in terms of capabilities and, hence, deploy the same number of keys in all sensors in a network to provide the aforementioned protections. In this paper, we demonstrate that a probabilistic unbalanced distribution of keys throughout the network that leverages the existence of a small percentage of more capable sensor nodes can not only provide an equal level of security, but also reduce the consequences of node compromise. To fully characterize the effects of the unbalanced key management system, we design, implement, and measure the performance of a complementary suite of key establishment protocols known as LIGER. Using their predeployed keys, nodes operating in isolation from external networks can securely and efficiently establish keys with each other. Should resources such as a backhaul link to a key distribution center (KDC) become available, networks implementing LIGER automatically incorporate and benefit from such facilities. Detailed experiments demonstrate that the unbalanced distribution in combination with the multimodal LIGER suite offers a robust and practical solution to the security needs in sensor networks
22550674
Timing-sync protocol for sensor networks
Wireless ad-hoc sensor networks have emerged as an interesting and important research area in the last few years. The applications envisioned for such networks require collaborative execution of a distributed task amongst a large set of sensor nodes. This is realized by exchanging messages that are time-stamped using the local clocks on the nodes. Therefore, time synchronization becomes an indispensable piece of infrastructure in such systems. For years, protocols such as NTP have kept the clocks of networked systems in perfect synchrony. However, this new class of networks has a large density of nodes and very limited energy resource at every node; this leads to scalability requirements while limiting the resources that can be used to achieve them. A new approach to time synchronization is needed for sensor networks.In this paper, we present Timing-sync Protocol for Sensor Networks (TPSN) that aims at providing network-wide time synchronization in a sensor network. The algorithm works in two steps. In the first step, a hierarchical structure is established in the network and then a pair wise synchronization is performed along the edges of this structure to establish a global timescale throughout the network. Eventually all nodes in the network synchronize their clocks to a reference node. We implement our algorithm on Berkeley motes and show that it can synchronize a pair of neighboring motes to an average accuracy of less than 20ms. We argue that TPSN roughly gives a 2x better performance as compared to Reference Broadcast Synchronization (RBS) and verify this by implementing RBS on motes. We also show the performance of TPSN over small multihop networks of motes and use simulations to verify its accuracy over large-scale networks. We show that the synchronization accuracy does not degrade significantly with the increase in number of nodes being deployed, making TPSN completely scalable.
10455339
Pollution in P2P file sharing systems
One way to combat P2P file sharing of copyrighted content is to deposit into the file sharing systems large volumes of polluted files. Without taking sides in the file sharing debate, in this paper we undertake a measurement study of the nature and magnitude of pollution in the FastTrack P2P network, currently the most popular P2P file sharing system. We develop a crawling platform which crawls the majority of the FastTrack Network's 20,000+ supernodes in less than 60 minutes. From the raw data gathered by the crawler for popular audio content, we obtain statistics on the number of unique versions and copies available in a 24-hour period. We develop an automated procedure to detect whether a given version is polluted or not, and we show that the probabilities of false positives and negatives of the detection procedure are very small. We use the data from the crawler and our pollution detection algorithm to determine the fraction of versions and fraction of copies that are polluted for several recent and old songs. We observe that pollution is pervasive for recent popular songs. We also identify and describe a number of anti-pollution mechanisms.