Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Search Results

Now showing 1 - 10 of 104

Development of a Framework for CPS Open Standards and Platforms
(2013-11-08) Baras, John S.; Austin, Mark A.
This technical report describes a Framework we have developed through our research and investigations in this project, with the goal to facilitate creation of Open Standards and Platforms for CPS; a task that addresses a critical mission for NIST. The rapid development of information technology (in terms of processing power, embedded hardware and software systems, comprehensive IT management systems, networking and Internet growth, system design environments) is producing an increasing number of applications and opening new doors. In addition over the last decade we entered a new era where systems complexity has increased dramatically. Complexity is increased both by the number of components that are included in each system as well as by the dependencies between those components. Increasingly, systems tend to be more software dependent and that is a major challenge that engineers involved in the development of such systems face. The challenge is even greater when a safety critical system is considered, like an airplane or a passenger car. Software-intensive systems and devices have become everyday consumables. There is a need for development of software that is provably error-free. Thanks to their multifaceted support for networking and inclusion of data and services from global networks, systems are evolving to form integrated, overarching solutions that are increasingly penetrating all areas of life and work. When software dependent systems interact with the physical environment then we have the class of cyber-physical systems (CPS) [1, 2]. The challenge in CPS is to incorporate the inputs (and their characteristics and constraints) from the physical components in the logic of the cyber components (hardware and software). CPS are engineered systems constructed as networked interactions of physical and computational (cyber) components. In CPS, computations and communication are deeply embedded in and interacting with physical processes, and add new capabilities to physical systems. Competitive pressure and societal needs drive industry to design and deploy airplanes and cars that are more energy efficient and safe, medical devices and systems that are more dependable, defense systems that are more autonomous and secure. Whole industrial sectors are transformed by new product lines that are CPS-based. Modern CPSs are not simply the connection of two different kinds of components engineered by means of distinct design technology, but rather, a new system category that is both physical and computational [1, 2]. Current industrial experience tells us that, in fact, we have reached the limits of our knowledge of how to combine computers and physical systems. The shortcomings range from technical limitations in the foundations of cyber-physical systems to the way we organize our industries and educate engineers and scientists that support cyber-physical system design. If we continue to build systems using our very limited methods and tools but lack the science and technology foundations, we will create significant risks, produce failures and lead to loss of market. Nowadays, with increasing frequency we observe systems that cooperate to achieve a common goal, even though there were not built for that reason. These are called systems of systems. For example, the Global Positioning System (GPS) is a system by itself. However, it needs to cooperate with other systems when the air traffic control system of systems is under 3 consideration. The analysis and development of such systems should be done carefully because of the emergent behavior that systems exhibit when they are coupled with other systems. However, apart from the increasing complexity and the other technical challenges, there is a need to decrease time-to-market for new systems as well as the associated costs. This specific trend and associated requirements, which are an outcome of global competitiveness, are expected to continue and become even more stringent. If a successful contribution is to be made in shaping this change, the revolutionary potential of CPS must be recognized and incorporated into internal development processes at an early stage. For that Interoperability and Integratability of CPS is critical. In this Task we have developed a Framework to facilitate interoperability and integratability of CPS via Open Standards and Platforms. The purpose of this technical report is to introduce this Framework and its critical components, to provide various instantiations of it, and to describe initial successful applications of it in various important classes of CPS. An additional goal of publishing this technical report is to solicit feedback on the proposed Framework, and to catalyze discussions and interactions in the broader CPS technical community towards improving and strengthening this Framework. CPS integrate data and services from different systems which were developed independently and with disparate objectives, thereby enabling new functionalities and benefits. Currently there is a lack of well-defined interfaces that on the one hand define the standards for the form and content of the data being exchanged, but on the other hand take account of non-functional aspects of this data, such as differing levels of data quality or reliability. A similar situation exists with respect to tools and synthesis environments, although some work has been initiated in the latter. The technological prerequisite for the design of the aforementioned various functions and value added services of CPS is the interoperability and integratability of these systems as well as their capability to be adapted flexibly and application-specifically as well as extended at the different levels of abstraction. Dependent on the objective and scope of the application, it may be necessary to integrate component functions (Embedded Systems (ES), System of Systems (SoS), CPS), to establish communication and interfaces, and to ensure the required level of quality of interaction and also of the overall system behavior. This requires cross-domain concepts for architecture, communication and compatibility at all levels. The effects of these factors on existing or yet undeveloped systems and architectures represent a major challenge. Investigation into these factors is the objective of current national and international studies and research projects. CPS create core technological challenges for traditional system architectures, especially because of their high degree of connectivity. This is because CPS are not constructed for one specific purpose or function, but rather are open for many different services and processes, and must therefore be adaptable. In view of their evolutionary nature, they are only controllable to a limited extent. This creates new demands for greater interoperability and communication within CPS that cannot be met by current closed systems. In particular, the differences in the characteristics of embedded systems in relation to IT systems and services and data in networks lead to outstanding questions in relation to the form of architectures, the definition of system and communication interfaces and requirements for underlying CPS platforms with basic services and parallel architectures at different levels of abstraction. 4 The technological developments underlying CPS evolution require the development of standards in the individual application domains, as well as basic infrastructure investments that cannot be borne by individual companies alone. This is particularly significant for SMEs. The development and operation of uniform platforms to migrate individual services and products will therefore be as much of a challenge as joint specification standards. The creation of such quasi standards, less in the traditional mold of classic industry norms and standards and more in the sense of de facto standards that become established on the basis of technological and market dominance, will become an essential part of technological and market leadership. To summarize and emphasize, the complexity of the subject in terms of the required technologies and capabilities of CPS, as well as the capabilities and competences required to develop, control and design/ create innovative, usable CPS applications, demand fundamentally integrated action, interdisciplinarity (research and development, economy and society) and vertical and horizontal efforts in:  The creation of open, cross-domain platforms with fundamental services (communication, networking, interoperability) and architectures (including domainspecific architectures);  The complementary expansion and integration of application fields and environments with vertical experimentation platforms and correspondingly integrated interdisciplinary efforts;  The systematic enhancement with respect to methods and technologies across all involved disciplines to create innovative CPS. The aim of our research and investigations under this Task of the project, was precisely to clarify these objectives and systematically develop detailed recommendations for action. Our research and investigations have identified the following essential and fundamental challenges for the modeling, design, synthesis and manufacturing of CPS: (i) The creation and demonstration of a framework for developing cross-domain integrated modeling hubs for CPS. (ii) The creation and demonstration of a framework for linking the integrated CPS modeling hub of (i) with powerful and diverse tradeoff analysis methods and tools for design exploration for CPS. (iii) The creation of a framework of linking the integrated CPS synthesis environment of (i) and (ii) with databases of modular component and process (manufacturing) models, backwards compatible with earlier legacy systems; (iv)The creation of a framework for translating textual requirements to mathematical representations as constraints, rules and metrics involving both logical and numerical variables and the automatic (at least to 75%) allocation of the resulting specifications to components of the CPS and of processes, in a way that allows traceability. 5 These challenges have been listed here in the order of increasing difficulty both conceptually and in terms of arriving at implementable solutions. The order also reflects the extent to which the current state of affairs has made progress towards developing at least some initial instantiations of the desired frameworks. In this context, it is useful to compare with the advanced state of development of similar frameworks and their instantiations for synthesis and manufacturing of complex microelectronic VLSI chips including distributed ones, which have been available as integrated tools by several vendors for at least a decade. Regarding challenge (i) we have performed extensive work and research in this project towards developing model-based systems engineering (MBSE) procedures for the design, integration, testing and operational management of cyber-physical systems, that is, physical systems with cyber potentially embedded in every physical component. Thus in the Framework, described in this report, for standards for integrated modeling hubs for CPS, MBSE methods and tools are prominent. Regarding the search for a framework for standards for CPS this selection has the additional advantage that it is also emerging as an accepted framework for systems engineering by all industry sectors with substantial interest in CPS [3, 7]. Regarding challenge (ii) we have performed extensive work and research in this project towards developing the foundations for such an integration, and we have developed and demonstrated the first ever integration of a powerful tradeoff analysis tool (and methodology) with our SysMLIntegrated system modeling environments for CPS synthesis [3, 7]. Primary applications of interest that we have instantiated this framework are: microgrids and power grids, wireless sensor networks (WSN) and applications to Smart Grid, energy efficient buildings, microrobotics and collaborative robotics, and the overarching (for all these applications) security and trust issues including our pioneering and innovative work on compositional security systems. A key concept here is the integration of multi-criteria, multi constraint optimization with constrained based reasoning. Regarding challenge (iii) we have only developed the conceptual Framework, as any required instantiations will require substantial commercial grade software development beyond the scope of this project. It is clear however that object-relational databases and database mediators (for both data and semantics) will have to be employed. Regarding challenge (iv) we have developed a Framework for checking and validating specifications, after they have been translated to their mathematical representations as constraints and metrics with logical and numerical variables. Various multi-criteria optimization, constrained based reasoning, model checking and automatic theorem proving tools will have to be combined. The automatic annotation of the system blocks with requirements and parameter specifications remains an open challenge.
Modeling the Impact of Protocols on Traffic Burstiness At Large Timescales in Wireless Multi-Hop Networks
(2013-04) Jain, Kaustubh; Baras, John S.
We investigate the impact of the protocol stack on traffic burstiness at large time-scales in wireless multi-hop network traffic. Origins of traffic burstiness at large scales (like its LRD nature) have been mostly attributed to the heavy-tails in traffic sources. In wired networks, protocol dynamics have little impact on large time-scale dynamics. However, given the nature of wireless networks, the MAC and routing layers together can lead to route flapping or oscillations even in a static network. Hence, we explore whether these dynamics can lead to traffic burstiness and LRD. Using network simulations, we analyze traffic for two MANET routing protocols - OLSR and AODV. By varying the routing protocol parameters, we analyze their role in inducing or preventing route oscillations, and study their impact on traffic LRD. We find that, losses in OLSR control packets, due to congestion at the MAC, can lead to route oscillations and traffic burstiness at large timescales. By tuning the parameters, route oscillations and traffic LRD can be avoided. AODV dynamics show little evidence for traffic LRD, even though we cannot rule out this possibility. We also show that the route oscillations can have heavier body and tail than exponential distribution, and that the Markovian framework for route oscillations is inadequate to explain the observed traffic scaling. Lastly, we give a model that captures the MAC and OLSR routing protocol interactions and depending upon chosen protocol parameters and input load, correctly predicts the presence of traffic LRD. Thus, we use this model to design appropriate choice of protocol parameters to mitigate traffic burstiness at large-timescales.
Studying Real-time Traffic in Multi-hop Networks Using the EMANE Emulator: Capabilities and Limitations
(2011) Jain, Kaustubh; Roy-Choudhary, Ayan; Somasundaram, Kiran K.; Wang, Baobing; Baras, John S.
In this paper, we study the fidelity of an open-source software emulator to provide reliable estimation of performance for real-time traffic in mobile ad-hoc networks. We emulate the IEEE 802.11 MAC/PHY (DCF) using the EMANE software emulator deployed on a cluster and run experiments for different multi-hop wireless scenarios with the Optimized Link State Routing (OLSR) protocol. As an instance of real-world usage scenario, we study the performance of real-time streaming media over a mesh network supported by OLSR. In particular, we study the effect of mobility and background traffic on carried load, delay and jitter. As another application, we analyze the impact of the wireless network on the self-similarity of aggregate traffic. Using traffic source models with high variability, we show that the aggregate traffic in the wireless network is self-similar and hence preserves its burstiness at larger time scales. The results are consistent with those obtained from high-fidelity simulation within some limitations of the emulator.
Stochastic Average Consensus Filter for Distributed HMM Filtering: Almost Sure Convergence
(2010-05-03) Ghasemi, Nader; Dey, Subhrakanti; Baras, John S.; Baras, John S.
This paper studies almost sure convergence of a dynamic average consensus algorithm which allows distributed computation of the product of $n$ time-varying conditional probability density functions, known as beliefs, corresponding to $n$ different nodes within a sensor network. The network topology is modeled as an undirected graph. The average consensus algorithm is used in a distributed hidden Markov model (HMM) filter. We use the ordinary differential equation (ODE) technique to analyze the convergence of the stochastic approximation type algorithm for average consensus with constant step size which allows each node to track the time varying average of the likelihood of the beliefs belong to different nodes in the network. It is shown that, for a connected graph, under mild assumptions on the first and second moments of the observation probability distributions and a geometric ergodicity condition on an extended Markov chain, the consensus filter state of each individual sensor converges ${\mathbb{P}\mbox{--a.s. }}$ to the true average of the likelihood of the beliefs of all the sensors. In order to prove convergence, we introduce a perturbed stochastic Lyapunov function to show that the error between the consensus filter state at each node and the true average visits some compact set infinitely often ${\mathbb{P}\mbox{--w.p.}1}$ and from that it is shown that the error process is bounded ${\mathbb{P}\mbox{--w.p.}1}$.
Distributed Topology Control for Stable Path Routing in Mobile Ad Hoc Networks
(2009-12-09) Somasundaram, Kiran K.; Jain, Kaustubh; Tabatabaee, Vahid; Baras, John S.
In this paper, we introduce the stable path topology control problem for routing in Mobile Ad Hoc Networks (MANETs). We formulate the problem as a constrained multiagent optimization problem with only local neighborhood information. We develop and prove local pruning strategies that solve this problem. We also introduce the notion of distorted pruning, which offers a systematic method to trade path stability off against the hop count metric. Finally, we quantify the performance of our pruning algorithms using several simulation scenarios.
Component Based Performance Modelling of the Wireless Routing Protocols
(2008) Tabatabaee, Vahid; Baras, John S.; Purkayastha, Punyaslok; Somasundaram, Kiran
In this paper, we propose a component based methodology for modelling and design of wireless routing protocols. Componentization is a standard methodology for analysis and synthesis of complex systems. Throughout the paper, we use Optimized Link State Routing (OLSR) protocol as a case study to demonstrate effectiveness of our methodology. We focus on modelling of three main components: neighborhood discovery, selector of topology information to disseminate, and the path selection components. For each component, we identify the inputs, outputs, and a generic methodology for modelling. Using the neighborhood discovery component, we will present our design methodology and design a modified enhanced version of the OLSR NDC, and compare its performance to the neighborhood discovery component of the OLSR protocol.
Performance Metric Sensitivity Computation for Optimization and Trade-off Analysis in Wireless Networks
(2008-02-26) Baras, John S.; Tabatabaee, Vahid; Papageorgiou, George; Rentz, Nicolas
We develop and evaluate a new method for estimating and optimizing various performance metrics for multi-hop wireless networks, including MANETs. We introduce an approximate (throughput) loss model that couples the physical, MAC and routing layers effects. The model provides quantitative statistical relations between the loss parameters that are used to characterize multiuser interference and physical path conditions on the one hand and the traffic rates between origin-destination pairs on the other. The model takes into account effects of the hidden nodes, scheduling algorithms, IEEE 802.11 MAC and PHY layer transmission failures and finite packet transmission retries at the MAC layer in arbitrary network topologies where multiple paths share nodes. We apply Automatic Differentiation (AD) to these implicit performance models, and develop a methodology for sensitivity analysis, parameter optimization and trade-off analysis for key wireless protocols. Finally, we provide simulation experiments to evaluate the effectiveness and performance estimation accuracy of the proposed models and methodologies.
Convergence Results for Ant Routing Algorithms via Stochastic Approximation and Optimization
(2007) Purkayastha, Punyaslok; Baras, John S.
``Ant algorithms'' have been proposed to solve a variety of problems arising in optimization and distributed control. They form a subset of the larger class of ``Swarm Intelligence'' algorithms. The central idea is that a "swarm" of relatively simple agents can interact through simple mechanisms and collectively solve complex problems. Instances that exemplify the above idea abound in nature. The abilities of ant colonies to collectively accomplish complex tasks have served as sources of inspiration for the design of ``Ant algorithms''. Examples of ``Ant algorithms'' are the set of ``Ant Routing'' algorithms that have been proposed for communication networks. We analyze in this paper Ant Routing Algorithms for packet-switched wireline networks. The algorithm retains most of the salient and attractive features of Ant Routing Algorithms. The scheme is a multiple path probabilistic routing scheme, that is fully adaptive and distributed. Using methods from adaptive algorithms and stochastic approximation, we show that the evolution of the link delay estimates can be closely tracked by a deterministic ODE system. A study of the equilibrium points of the ODE gives us the equilibrium behavior of the routing algorithm, in particular, the equilibrium routing probabilities, and mean delays in the links under equilibrium. We also show that the fixed-point equations that the equilibrium routing probabilities satisfy are actually the necessary and sufficient conditions of an appropriate optimization problem. Simulations supporting the analytical results are provided.
Sensor scheduling using smart sensors
(2007) Hovareshti, Pedram; Gupta, Vijay; Baras, John S.
The sensor selection problem arises when multiple sensors are jointly trying to estimate a process but only a subset of them can take and/or use measurements at any time step. In a networked estimation situation, sensors are typically equipped with some memory and processing capabilities. We illustrate that utilization of these capabilities can lead to significant performance gains in the sensor selection problem for improved inference. Further, it also leads to significant pruning of the search tree that yields the optimum sensor schedule. We also present a periodicity result for the case where the decision is whether the sensor should transmit or not.
Optimal Output Feedback Control Using Two Remote Sensors over Erasure Channels
(2007) Gupta, Vijay; Martins, Nuno C.; Baras, John S.; Martins, Nuno C.; ISR

Institute for Systems Research Technical Reports

Browse

Filters

Settings

Sort By

Results per page

Search Results