ABSTRACT
In many cyber-physical systems, the physical system is monitored continuously, and data streams are transmitted in a network environment. Due to limited communication bandwidths and other resource constraints, a critical and practical demand is to compress data streams online continuously with quality guarantee. Although many data compression and digital signal processing methods have been developed to reduce data volume, their superlinear time and more-than-constant
space complexity prevent them from being applied directly on data streams, particularly over resource-constrained cyber-physical systems. This chapter presents methods to tackle the problem of online quality-guaranteed compression of data streams using fast linear approximation (i.e., using line segments to approximate a time series). Technically, two versions of the problem are investigated to explore quality guarantees in different forms. Online algorithms with linear time complexity and constant cost in space are introduced. The presented algorithms are optimal in the sense that they generate the minimum number of segments that approximate a time series with the required quality guarantee. To meet the resource constraints, a fast algorithm is developed that creates connected segments with very simple computation. The low-cost nature of the methods in this chapter results in a unique practical advantage in the applications of massive streaming environment, lowbandwidth networks, and heavily constrained nodes in computational power (e.g., tiny sensor nodes). The algorithms are implemented and evaluated in a real-world test bed and with real-world trace data.
A CPS [24] is an engineered system that monitors, coordinates, and controls the physical system with sensing, computing, and communication technologies. A CPS normally consists of three core tightly integrated functional modules: communication, computation, and control. Embedded sensors monitor the physical system and communicate the sensing data to the computation module, often via wireless networks; the computation module makes control decisions and sends back signals to the control module to control the physical system. Feedback loops are formed, as changes in physical processes in turn affect the computation. Clearly, information, that is, sensing data and control signals, is the key to smoothly orchestrate the three functional modules. It is critical to guarantee the quality of information for the success of any CPS.
