Mining sensor and mobility data in cyber-physical systems
A Cyber-Physical System (CPS) is an integration of physical devices with informational resources. Such a system has many promising applications in both military and civil fields, such as missile defense, battlefield awareness, traffic control, neighborhood watch, environment monitoring and wildlife tracking. The objective of this thesis is to advance the data mining techniques in the novel applications of CPS, and complete the tasks of knowledge discovery by integrating the various properties of physical-world with the information components in cyber-world. This thesis introduces the author's studies on sensor and mobility data mining with CPS applications. First, this thesis investigates the problem of discovering intruders' trajectories from noisy sensor data (i.e., mining lines in the sand). With a large number of sensors (sand) deployed in a designated area, the CPS is required to discover all the trajectories (lines) of passing intruders in real time. There are two crucial challenges that need to be addressed: (1) the collected sensor data are not trustworthy; (2) the intruders do not send out any identity information. The system needs to distinguish multiple intruders and track their movements in real time. This study proposes a method called LiSM (Line-in-the-Sand Miner) to discover trajectories from untrustworthy sensor data. LiSM constructs a model of watching network from sensor data and computes the locations of intruder appearances based on the link information of the network. LiSM retrieves a cone-model from the historical trajectories and tracks multiple intruders based on this model. Then the system validates the mining results and updates sensors' reliability scores in a feedback process. In addition, LoRM (Line-on-the-Road Miner) is proposed for trajectory discovery on road network, (i.e., mining lines on the roads). LoRM employs a filtering-and-refinement framework to reduce the distance computational overhead on road network, and uses a shortest-path-measure to track intruders. Next, this thesis studies the problem of discovering object groups that travel together (traveling companions) from streaming trajectories. The key issue of companion discovery is on mining efficiency. This study proposes a data structure termed traveling buddy to facilitate scalable and flexible companion discovery from trajectory streams. The traveling buddies are micro-groups of objects that are tightly bound together. Only storing the object relationships rather than their spatial coordinates, the buddies can be dynamically maintained along trajectory streams with low cost. Based on traveling buddies, the system discovers companions without accessing the object details. The proposed methods are extended to more complicated scenarios with spatial and temporal constraints, such as the road network. The proposed techniques are evaluated with extensive experiments on both real and synthetic datasets. The experimental results show that the proposed methods achieve better efficiency and higher accuracy in data mining tasks.
data mining, cyber-physical system, trajectory mining, sensor network
University of Illinois - Urbana-Champaign
Networked Digital Library of Theses and Dissertations
University of Illinois at Urbana-Champaign