Home | Business News | Browse by Publication | I | IIE Transactions

A context tree method for multistage fault detection and isolation with applications to commercial video broadcasting systems.

Article Excerpt
1. Introduction

An embedded system is a special-purpose computer system designed to perform one or a few dedicated functions (Noergaard, 2005), sometimes with real-time computing constraints. It is usually embedded as part of a complete device including hardware and mechanical parts. Many complex embedded systems have their functionalities distributed among several autonomous components. A simple and popular case of such distributed functionality systems is the multistage serial system where the components are assembled in successive stages with the output of one stage serving as the input for the subsequent stage. These systems are found in a variety of sectors. For example, in the manufacturing sector, a product may be assembled by successive subassembly stations which rely on a combination of software and hardware capabilities to fulfill their purpose (Ding et al., 2000). Similarly, in the area of telecommunication, data or signals typically need to travel through several subsystems for a service to be provisioned or delivered. Other such embedded systems--in multistage or compact forms--are found in applications as diverse as automotive systems, avionics, automatic monitoring and control systems and broadcasting systems.

Complex embedded systems often generate huge amounts of data in the form of system logs with complex contents and structures. Analyzing these logs and interaction data is typically very labor intensive and time-consuming. Methods that take advantage of the available data for Fault Detection and Isolation (FDI) hold the potential of lowering the cost of maintaining and fixing defects (bugs) in these systems tremendously. Effective models require the use of Finite State Machines (FSMs) (Lee and Yannakakis, 1996) to capture their non-linear and context-dependent characteristics. This paper addresses the problem of fault detection and isolation in multistage embedded systems that exhibit context-dependent behavior. Faults in such systems may be due to actual hardware failures (e.g., power supply failures), subtle software bugs or hardware and software performance problems that become apparent when statistical patterns of input and output variables at different stages shift from nominal behaviors associated with particular contexts. Unfortunately, although such software-intensive systems generate tremendous data in field deployments, data associated with them is often a mixture of context-specific categorical and numerical information, which limits the use of many predictive models that have been developed for FDI.

Consider for example a Commercial Video Broadcasting (CVB) system as the one depicted in Fig. 1, which constitutes a multistage system where each of the video processing components represents a processing stage:

[FIGURE 1 OMITTED]

Stage 1: Images enter the system at the encoder and are encoded for transmission using a format such as MPEG2 (ISO/IEC, 2000).

Stage 2: The encoded images are transmitted by a broadcasting system made up typically of an earth transmitter, a satellite transceiver and an earth receiver.

Stage 3: The images received through the broadcasting channel are delivered to a transcoder. The transcoder converts the image stream to a format suitable for delivery through a coaxial cable network and forwards this stream to such a cable network.

Stage 4: The cable network delivers the stream to a decoder.

Stage 5: The decoder decodes the image stream for delivery to TV sets.

This CVB system shares the characteristics of generic multistage systems. Similar to a manufacturing system where parts are assembled and transferred from stage to stage into a finished product, image streams are transformed and transferred from stage to stage into a viewable program. For a car assembly system, Jin and Shi (1999) modeled part variation at one (current) stage as the linear function of part variations at the previous stage, part locating errors at the current stage and part reorientation errors accumulated up to the previous stage. The matrices representing different terms of this linear function can then be analyzed to determine the stage where part variations exceed design tolerances. In a generic context-specific multistage system such as the CVB system described above, accumulated stream variation at a stage is also a function of accumulated variations at previous stages and variations introduced by the current stage. However, in general, it is not practical to express this function as a linear combination of previous variations. This paper proposes the use of the Context Tree (CT) method--also known as the Variable Order Markov (VOM) model--to represent the dependence relationship between stages for prediction and diagnosis purposes. The VOM model is a more tractable variant of the Markov chain model. It provides more flexibility than a fixed-order Markov model where the longest dependency sequence is necessary to characterize all states and transitions in the system.

For the CVB system, a viewer may often experience certain impaired images such as intermittent picture freeze, picture tiling, missing picture blocks and other visual blemishes. When impaired images are delivered to TV sets, it is the result of stream distortion accumulated through different stages. For example, as the coded picture stream travels through the stages illustrated in Fig. 1, the output of the encoder may contain timing violations, processing delays or compression artifacts. The stream may be further distorted after the satellite communication subsystem due to transmission errors. Additional timing and processing delay distortions may occur at the transcoder. Further transmission error distortions may accumulate at the output of the cable distribution plant. Finally the decoder may introduce its own deviations due to its own processing delays and decoding artifacts. This paper will present a generic model for modeling stream variation from stage to stage.

Significant statistical deviations from established patterns may indicate that some hardware faults have occurred. However, the most challenging situations are present when new hardware, software or configuration settings are introduced in some part of the system and the new addition affects performance of the whole in unexpected ways. The effect of these deviations tends to be context-specific. For example, a particular timing variation may be barely noticeable in a particular sequence and show severe viewing defects when seen in a picture frame following a sequence of pictures with rapid scene changes. Similarly, the quality experienced when viewing a picture with certain display characteristics may be different depending on the sequence in which it is included.

The sheer complexity of these systems coupled with the fact that different components may be under the jurisdiction of different organizational entities makes it difficult to develop detailed knowledge of the internals of each component. As the pace of deployment of such complex hardware-software systems accelerates, the need for generic unsupervised models that simplify the task of FDI increases. This paper makes several contributions to the field of FDI in multistage systems.

1. It expands the scope of application of the CT method to FDI problems in context-dependent multistage systems such as the one described above.

2. It shows how a model-generic industrial statistical process control method can be applied to detect and isolate hardware and software faults in multistage systems.

3. It introduces a variant of the CT method that leverages cross-stage dependencies in such systems.

4. Unlike most other multistage FDI techniques in the literature, this method can accommodate mixed-value systems where the variables associated with the system include a mixture of categorical and numerical data.

5. Finally, considering FDI methods beyond the scope of multistage systems, the proposal compares favorably to other non-linear methods such as those described in Section 2, since the proposed technique is unsupervised and does not require a priori knowledge of fault modes.

The remainder of this paper is organized as follows. Section 2 provides a brief review of FDI methods for complex systems. We discuss a few techniques that have been proposed for multistage systems as well as other prominent methods used for non-linear systems. Section 3 describes the CT method and its use to characterize multistage systems. Section 4 discusses the application of this method to FDI problems in multistage systems. Section 5 discusses symbol coding and mapping for software-intensive mixed-value systems using a clustering algorithm. Section 6 contains an example where the CT-based FDI procedure is applied to the CVB system. Section 7 concludes the paper and discusses future work. The online Appendix briefly lays out algorithms used to learn context trees from data.

2. Review of FDI techniques

There is a vast literature on FDI methods for complex systems. In this section, we will briefly discuss FDI methods that are applicable to general complex systems....

View this article FREE - Now for a Limited Time, try Goliath Business News
Free for 3 Days!