【作者】 高静；

【导师】 李建中；

【作者基本信息】 哈尔滨工业大学 ， 计算机软件与理论， 2015， 博士

【摘要】 信息物理融合系统是由传感器、执行器、控制器和网络设备组成的大规模、分布式的异构系统,它将计算过程与物理过程紧密融合,其理论研究和关键技术具有重要的实际应用价值,已经引起了学术界和商业界的高度重视和广泛关注。正确、全面地观察和理解物理世界是信息物理融合系统应用中的一个核心问题。信息物理融合系统通过感知部件产生的数据来获得物理世界的信息。由于信息物理融合系统是由多种异构网络(例如无线传感器网络、3G、蓝牙等)互联而成,其网络设备涉及多种不同的感知器和不同的执行器。不同感知设备会产生不同类型的数据。在信息物理融合系统的研究中,如何有效的融合这些多模态数据进而正确的反映物理世界的状态是十分重要的研究课题。事件能够有效的反映物理世界的状态,本文研究信息物理融合系统中的事件监测问题,并从基于多模态数据的事件模型、基于多模态数据的事件覆盖、基于多模态数据的事件检测以及基于多模态数据的事件调度等方面展开研究。首先,为了抽象和描述信息物理融合系统中的事件,本文研究了基于多模态数据的事件模型问题。在信息物理融合系统中,通过部署在系统区域内的传感器节点来获得物理世界的信息。信息物理融合系统通常包含若干个异构的无线传感器网络。这些异构网络包含不同类型的传感器节点,这些节点具有不同的感知、计算和通信能力。将异构的传感器节点获得的不同类型的感知数据融合是一个十分重要并亟待解决的问题。在本文中,我们首先提出了基于多模态数据的事件模型,以事件为载体将多种不同模态的数据融合计算。文中描述并定义了信息物理融合系统中的事件,给出了基本事件和复合事件的定义,并提出了事件的合成规则。我们还提出带有置信度的基于多模态数据的事件模型。能够反应物理世界状态或者对象信息的最小的数据看做基本事件,并且仅涉及单一模态的数据,基本事件通过一系列的合成规则不断地合成复合事件。这些由多模态的数据组成的复合事件能够帮助我们更好地理解物理世界。在事件模型中,我们引入了置信度,每一个基本事件的置信度表示其对复合事件发生的支持程度。进而使模型能够提供灵活、有效的事件的近似处理。其次,为了保证事件能够被正确、全面的监测,本文研究了信息物理融合系统基于多模态数据的事件的覆盖问题。事件覆盖是事件监测的基础和关键。覆盖质量反映了事件或者网络区域被监控的效果。传统的覆盖问题中考虑基本事件,这些基本事件仅涉及单一模态的数据并且仅描述某一侧面的性质。然而,监测的对象通常都十分复杂,并且不能被单一模态的数据简单判定。因此,我们首次提出并研究监测系统中复合事件的覆盖问题,其中复合事件是由多模态数据生成的基本事件复合而成的。复合事件覆盖问题的目标是确定最佳的代价分配方案,既确定每类节点需要部署的数量,进而保证监测系统在代价约束的条件下获得最佳的事件监测效果。本文形式化的定义了复合事件的最优覆盖问题,并分析了问题的复杂性。提出了两个精确算法和一个近似算法来解决最优覆盖质量问题。精确算法适用于节点类别较少或者需要精确结果的应用。近似算法适用于规模较大的应用中。另外,本文对精确算法的效率和近似算法的近似比都进行了分析。然后,为了快速的获得事件的信息,本文研究了基于多模态数据的事件检测问题。事件检测是监测系统的基本任务之一。不同类型的数据之间的复杂关系使得复合事件检测成为一个艰巨的任务。传统的事件检测方法需要收集所有的事件数据,无疑会造成巨大的能量开销。然而,组成复合事件的多模态数据之间并不是完全独立的,每一种模态的数据从不同的侧面描述复合事件的信息,并为复合事件的发生提供支持。因此利用了模态数据之间的关系,可以使用部分感知数据来近似地检测复杂的事件。本文研究带有置信度阈值的复合事件近似检测问题。为了减少能量消耗,我们形式化定义了最优传输模式问题,该问题的目标是尽量减少传输到基站的数量,在保证基站获得的数据能够有效的判定复合事件的同时,使传输消耗的能量达到最小值。我们分析了最优传输模式问题的复杂性,并针对不同情景给出了基于动态规划的精确算法和基于贪心策略的近似算法来解决该问题。最后,为了延长事件监测的服务周期,本文研究了基于多模态数据的事件调度问题。传感器节点通常是由电池供电的,因此在保证系统的监测质量的同时,尽可能的减少能耗,延长系统的生命周期是十分重要的问题。节点调度利用了感知数据的冗余性,为解决系统能量瓶颈问题提供了有效的方法。在近似事件检测的基础上,本文研究基于多模态数据的事件调度,该问题的目标是在满足事件的近似监测效果的同时,制定最优的节点调度策略,尽可能的降低节点的能量消耗,最大化系统的生命周期,进而保证事件监测的可持续性。本文分析了节点调度问题的复杂性,并证明其属于NP-完全问题,并设计了近似算法来解决节点调度问题,证明了近似算法的近似比。更多还原

【Abstract】 Cyber-Physical System(CPS)is a large-scale, heterogeneous and distributive systemcollaborating sensors, actuators, controllers and network components. Computation pro-cess and physical world are tightly integrated in cyber-physical systems. The research incyber-physical system which has caused extensive concern by the attentions of academicand the business community is becoming more and more important in real-world appli-cations. The key issue of applying cyber-physical systems is to observe and cognize thephysical world accurately and comprehensively. CPS obtains the information of physicalworld by analyzing the data generated by sensors. CPS is an integration of heterogeneousnetworks(such as wireless sensor networks, 3G, bluetooth, etc.). Various types of data aregenerated by different sensor components from heterogeneous networks. In the researchof cyber-physical systems, it is important to study the methods of fusion multi-modal da-ta to accurately describe the state of the physical world. The event can effectively reflectthe state condition of the physical world. This dissertation will study the event monitor-ing problem in the cyber-physical systems in the multi-modal data based event model,multi-modal data based event coverage problem, multi-modal data based event detection,multi-modal data based event scheduling and so on.First, in order to abstract and describe the event in cyber-physical systems, this thesisstudies the problem of multi-modal data based event model. In CPS, the informationabout physical world is obtained by sensors deployed in the system area. Generally, aCPS is composed by several heterogeneous wireless sensor networks. Heterogeneoussensor nodes in these networks have different capabilities in terms of sensing, computingand communication. Jointly processing the multi-modal data generated by heterogeneoussensors is an important problem. This dissertation proposes multi-modal data based eventmodel, which interstates multi-modal data by events. The definitions and descriptions ofatomic event and composite event, the composition rules of the event are proposed in thisdissertation. The multi-modal data based event model with confidence is also devised.The minimum amount of data describing a state of the physical world or the informationof an object is defined as an atomic event, with only one type of data involved. Severalatomic events can be composed into a composite event using predefined combinationrules. The composite event generated by multi-modal data is beneficial to comprehendthe physical world. The confidence which indicates the support rating for the occurrenceof the composite event is introduce in the event model. Thus the model can provideflexible and e?cient approximate event processing service.Second, in order to ensure the accuracy and the integrity of the event monitoring, thisthesis studies the problem of multi-modal data based event coverage in Cyber-PhysicalSystems. Event coverage is an essential requirement for event monitoring and is the keyto success of accurate and rapid event detection. The quality of coverage reflects how wella system is monitored. An atomic event only involving single-mode data for a specificproperty is the primary focus of traditional converge problems. However, the monitoredphenomena is always complicated and the occurrence of an event cannot be determinedpurely based on single-mode raw data. Thus, the composite event coverage problem isfirstly formulated and studied in this thesis, where a composite event is a combination ofseveral atomic events and its occurrence is jointly determined by many atomic events ormulti-modal data. The goal of composite event coverage is to determine the best budgetallocation policy to specify the amount of different types of nodes so that the monitoringsystem achieves the optimal event monitoring performance under the budget constraint.The optimal coverage quality problem is formulated and the complexity is analyzed. Twoexact algorithms and an approximate algorithm are proposed to solve the coverage qualityoptimization problem. The exact algorithms are applicable to the applications with smallnumber of types or demanding more accurate results. The approximate algorithm is suit-able for the applications with large number of types and numerous nodes. Moreover, thee?ciency of the exact algorithms and the approximate ratio of the approximate algorithmare also studied.Third, in order to collect event information rapidly, this thesis studies the problem ofmulti-modal data based event detection. Event detection is one of the fundamental tasksin monitoring systems. The complex relations among different types of data make com-posite event detection a tough task. Traditional methods need to collect all the event data,which causes huge energy consumption. However, the multi-modal data of the compositeevent are not totally independent. The occurrence of each atomic event provides supportor can be seen as the evidence for the occurrence of a composite event. By exploiting thecorrelations between different types of data, the complex composite event can be detectedapproximately by partial data. In order to reduce the energy consumption, we formu-late the optimal transmitting scheme problem and the goal of which is to decide whichtypes of atomic event should be transmitted to the base station such that the confidenceof the composite event by merging all the received atomic events satisfies the confidencethreshold at the same time the total transmitting cost is minimized. The complexity ofthe optimal transmitting scheme problem is analyzed and a dynamic programming basedalgorithm as well as a greedy based algorithm are proposed to solve this problem fordifferent scenarios.Forth, In order to extend the service cycle of event monitoring, this thesis studiesthe scheduling problem for multi-modal data based event. The sensor nodes are usuallypowered by a battery. Thus, it is essential to reduce the energy consumption and prolongthe lifetime of the system as well as guarantee the monitoring quality. By exploiting theredundancy of the sensing data, node scheduling provides an effective method for solvingthe energy bottleneck problem. On the basis of the approximate event detection, multi-modal data based event scheduling problem is proposed which aims at developing optimalnode scheduling policy to reduce the energy consumption and maximize the lifetime of thesystem to ensure the sustainability of event monitoring. The complexity of the schedulingproblem is studied in this thesis, and the problem is proved to be NP-complete. Theapproximate algorithm is devised to solve event scheduling problem and the performanceguarantee is proved.更多还原