第1章 绪论
随着信息技术的发展和日益成熟，特别是新一代无线通信技术、嵌入式计算技术、传感器网络技术和自动控制技术等都取得了巨大地发展和长足地进步，诞生了一种能够将计算过程与物理过程融合的信息物理融合系统(Cyber-Physical System，CPS)。由于其能够协作地实时监测、感知、采集目标域内的各种环境或监测对象信息并及时地给予反馈控制，信息物理融合系统能够很好地将信息世界与物理世界融合在一起。信息物理融合系统应用前景非常广泛，是计算机科学的一个重要研究领域。
1.1课题背景和意义
自上世纪90年代起，无线传感器技术开始走入人们的视野。最早开始研究的是来自于卡内基-梅隆大学的无线传感器网络小组。这种新型的网络利用一种低成本、低功耗、多功能的微型传感器，结合嵌入式计算技术、分布式计算技术和无线通信技术，实时监测、感知、采集监控目标的信息，并且通过随机自组织的无线通信网络以多跳的方式将数据传输到用户手中[1–3]。这种网络的出现，使得人们能够不受时间、空间的约束来观察物理和感知物理世界。特别是对于国防用途，很多高危险的战场环境感知、监控均可以由无线传感器网络来完成。因此，美国的国防和军事部门开始高度关注无线传感器网络技术的研究，并且发布了大量的关于无线传感器网络的研究项目，例如战场环境侦查与监测系统、目标追踪、入侵检测与身份识别系统等[4, 5]。随着传感器技术的进一步发展和传感器节点成本的进一步降低，无线传感器网络在民用领域也展现了巨大的应用潜能，各国也开始相继斥资研究和发展无线传感器网络技术。随着信息技术的发展，人们不再仅仅满足于利用无线传感器网络对物理世界进行观察和感知，而且希望能够通过感知的结果对现实世界进行干预和反馈控制，进一步减少对于人的依赖。因此，一种能够将信息世界与物理世界高度融合的系统，即信息物理融合系统被提了出来。信息物理融合系统集成了新一代无线通信技术、嵌入式计算技术、无线传感器网络技术和自动控制技术，能够实时的监测和感知目标的状态及周围的环境信息，然后再利用自动控制技术实现干预和控制，达到无人化作业的目的[6–8]。信息物理融合系统应用前景非常广泛，可广泛应用于国防军事、环境监测与保护、空气污染治理、交通运输、医疗救助、工业制造、海洋探测、矿物开采等众多领域。特别是工业4.0、智慧城市、智能交通、智能家庭等概念的提出，将信息物理融合系统的研究推向了一个新的高潮[9]。目前针对该系统的研究已经引起了各国政府和学术界的高度关注，成为计算机科学领域中的一个新兴热点。2007年，美国总统科学技术顾问委员会在一篇题为《挑战下的领先——竞争世界中的信息技术研发》的报告中将信息物理融合系统列为8个重大关键技术的首位[10, 11]。美国国家自然科学基金委员会也连续多年将CPS列为科研热点，并且已经资助了多个CPS研究项目。欧洲和日韩等国随后也分别启动了各自的CPS系统研究计划，如智能嵌入式系统先进发展计划(Advanced research andtechnology for embedded intelligence and systems)等项目。其中，欧洲计划投入超过70亿美元以使其成为该领域的领导者之一。在德国，据德国信息产业研究会报告称，信息物理融合系统引领的工业4.0将在2025年的时候为德国贡献超过2670亿欧元的产值[12]。在我国，随着工业化和信息化进程的加速，大力发展CPS已经成为具有国家战略意义的重大决策。在2015年期间，我国物联网产业规模已经达到7500亿元规模，并且在“十二五”期间，其年复合增长率将达到25%[13, 14]。因此，CPS是二十一世纪具有重大影响力的技术。
..........
1.2信息物理融合系统概述
信息物理融合系统（CPS）是集计算、通信、感知和控制等功能为一体的多维复杂系统，可以实现信息世界与物理世界的高度融合和完成对物理世界高效实时、分布协同、安全可靠地感知和控制[8]。一个典型的CPS系统，主要包含若干传感器节点、执行器、计算系统、控制系统，以及一个组合通信网络系统。传感器节点主要负责感知物理世界中的环境信息，并且将感知信息通过自组网的形式将感知信息传递给计算系统和控制系统。计算系统和控制系统负责完成信息世界的计算（例如信号处理和事件识别）和制定相应的反馈和控制命令。执行器则负责根据形成的控制命令执行相应的动作来完成对物理世界的反馈和控制。其中，传感器节点和执行器一般部署于需要监测和控制的目标区域内。计算系统和控制系统则不必部署于现场物理环境中。与现有的智能控制技术相比，信息物理融合系统在结构和性能等方面具有以下几大特点[6–8]：(1)紧密融合。CPS系统通过将计算系统、感知系统、通信系统和控制系统紧密统合，实现了信息世界和物理组件的高度集成。紧密融合是其最基本特征之一。(2)异构多样。CPS是网络化的、异构的大规模分布式系统。由于其在时间和空间上具有多重复杂性，而且构成CPS的通信网络、计算系统、控制系统、以及物理设备都是异构的，具有不同的协议和标准，因此，整个系统具有异构性和多样性。(3)资源有限。CPS系统中物理构件的计算、通信、精确控制、远程协调和自治功能由于CPS系统中传感器节点和执行器能耗和大小的限制都十分有限。(4)不确定性。由于测量误差、环境噪声以及计算模型的不准确和无线通信的不稳定使得CPS系统中的不确定性普遍存在。(5)安全可靠。CPS系统的应用涉及多种重要场景，而且其控制过程能与物理世界直接交互，一旦出现故障，将产生不可估量的后果，所以CPS系统必须还具备安全、可靠和抗毁等特点。
.........
第2章 基于动态切换和扩展活动时间槽的实时路由算法
2.1引言
随着无线通信和传感器技术的发展，信息物理融合系统已经被广泛地应用在社会生活各种领域中，如医疗监护、结构监测、科学探索[110, 111]等等。在这些领域中，许多应用都需要提供长时间的服务，需要网络存活很长一段时间，例如几个月或者几年。然而由于受到成本和体积因素的考虑，传感器节点（如Micaz和Telos等）一般都是能量受限的[112]。为了解决节点的生存周期和能量之间的冲突，目前一种广泛采用的方法是让节点采用一种占空比的工作方式，即节点只在规定的时间醒来而其他大部分时间都处于睡眠状态。另外，随着应用需求的增加和电池容量的缓慢发展，越来越多的占空比网络已经被部署和实施[48, 74]。除了节点的能量受限问题，许多应用还需要实时地数据传输服务，即在数据包从源节点路由到目的节点的过程中不能超过给定延迟阈值的限制。例如在战场上的入侵检测、医疗救助以及污染物检测和预防等系统中，都需要保证监测数据或事故报告在给定的时间内到达基站或监控平台，以便系统能够及时地做出反应，避免发生严重的后果。基于上述考虑，本章与文献[48, 74]一样考虑了一个在占空比（例如5%）网络中的实时路由问题。为了节省能量，在这种网络中节点大部分的时间都处于睡眠状态，只醒来很短的时间完成数据的传输和对周围环境的感知。另外，为了满足覆盖性和连通性的要求，节点都是被异步调度的，通常只有很少的节点在同一时刻能被唤醒。当节点有一个数据包需要发送时，可能需要等待一段时间直到有邻居节点醒来后帮忙转发，其中等待的时间即被称为睡眠延迟（SleepLatency）。通常情况下，节点之间的睡眠延迟是数据传输延迟的几十倍或上百倍。因此传统的基于节点一直醒着的实时路由算法不适用于这种网络。
..........
2.2网络模型及问题定义
在一个多跳的占空比无线传感器网络G = (V, E) 中，其中，|V| = N 表示所有传感器节点的集合，E表示边的集合。每个节点具有2种工作状态：睡眠状态和活动状态。节点只有在活动状态时才可以感知环境、发送或接收数据。这意味着节点只能在其处于活动状态时才能接收数据包。在需要发送数据包时，发送节点可以通过在邻居节点醒来时通过转换到活动状态来完成数据包的发送。由于每个节点醒来的时间不一样，整个网络的连通性也随着时间而变化。用G(t) = (V, E(t))表示整个网络在t时刻的拓扑结构，其中，E(t) 表示 t 时刻边的集合。一条有向边ei j属于E(t)当且仅当：1）节点j处于节点i的通信范围内；2）节点j在t时刻处于活动状态。另外为了表示方便，用T表示节点的一个工作周期，每个工作周期被划分成若干个长度相同的时间槽τ （根据CC2420的标准，τ的长度通常都是非常受限的[113]）。为了维持网络的连通性或覆盖性，每个节点都被分配了一个工作计划，即节点被调度醒来的时间槽集合。
.........
第3章 节能及延迟受限的多播调度算法....... 56
3.1引言....... 56
3.2网络模型........ 57
3.3节能的多播调度算法...... 59
3.3.1问题定义.......... 59
3.3.2辅助图构造...... 61
3.3.3最小能耗多播问题的近似算法.......... 66
3.3.4算法近似比分析....... 70
3.4延时受限的多播调度算法....... 73
3.5模拟实验结果......... 79
3.6本章小结........ 84
第4章 基于非固定结构的实时数据聚集调度算法.......... 86
4.1引言....... 86
4.2网络模型及问题定义...... 88
4.2.1网络模型.......... 88
4.2.2问题定义.......... 90
4.3分布式聚集调度算法...... 91
4.4性能分析........ 100
4.5模拟实验结果......... 102
4.6本章小结........ 107
第5章 基于边结构的实时信标调度算法.......108
5.1引言....... 108
5.2网络模型及问题定义...... 109
5.3协议干扰模型下的信标调度算法..... 112
5.4物理干扰模型下的信标调度算法..... 124
5.6本章小结........ 131
第5章 基于边结构的实时信标调度算法
5.1引言
在多跳的无线网络中,信标调度是很多网络协议的基础，其中每个节点需要在本地将信标包广播给所有的邻居节点[108]。例如,在发现网络拓扑结构、数据聚集算法、构造路由协议等过程中，每个节点均需要首先了解其邻居节点的信息[20, 121, 122]。假设所有的节点均进行了时间同步，并且传输是在具有相等长度的时间槽内进行，则信标延迟被定义为所有节点将信标包无冲突的广播给所有邻居所需要的时间槽的个数。很显然，信标延迟越小，网络性能更好。因此最小信标延迟调度问题(Minimum Latency Beacon Scheduling, MLBS)，即找到一个最小化信标延迟的无冲突调度问题吸引了大量地关注，并且研究者们提出了很多针对节点一直醒着的网络的算法[98–107]。根据文献[101],即使采取最简单的假设：每个节点传输半径为单位1并且干扰半径 ρ = 1，MLBS 问题仍被证明为NP-hard。因此，文献[98–107]中的算法均为近似算法，并且具有不错的性能。然而，对于很多无线网络来说，特别是无线传感器网络，节点能耗非常受限。为了节省能耗，能耗获取技术和占空比工作模式被证明为非常有效。在占空比网络中，每个节点具有两个工作状态，i.e.,活动状态和睡眠状态。在睡眠状态，所有的功能模块将被关闭来节省能耗。
...........
结 论
在信息物理融合系统中，传感器网络通过对物理世界高效实时、分布协同、安全可靠地感知和控制，达到了将信息世界与物理世界高度融合的目的。在这其中，数据的实时传输、聚集以及调度至关重要。然而，传感器节点的占空比工作模式、传输功率过小，链路不可靠等特点，为上述问题带来了巨大挑战。因此，本文将根据传感器节点的上述特点对信息物理融合系统中的实时路由、实时数据聚集与信标调度等方面展开研究。主要研究内容成果如下：
（1）本文研究了占空比传感器网络中的实时数据传输的端到端路由问题。本文提出了一种基于动态切换的实时路由算法（DSRT）。结合动态切换机制，DSRT利用提出的将缓冲队列分类的拥塞避免算法将数据包的延迟降低了2倍以上。更进一步，考虑到无线传输时链路不可靠的特点，本文还提出了一种基于扩展活动时间槽的实时路由算法（RRAD）。利用扩展活动时间槽和ARQ-based传输机制，RRAD将数据包的延迟降低了1倍左右。另外，还提出了一种轻量级的潜在转发节点选择算法。模拟实验结果验证了本文提出的DSRT和RRAD算法能够减小路由延迟和提高传输的可靠性。
（2）本文研究了信息物理融合系统中节能及实时的多播调度问题。本文给出了占空比传感器网络中最小能耗多播问题的形式化定义，并证明了该问题是一个NP-hard问题。本文提出了辅助图的概念以用于构建最小能耗多播树，并提出了构建辅助图的贪心算法。基于上述辅助图，本文提出了一种近似调度与构造算法，并且证明其近似比为4lnK。另一方面，本文还给出了占空比网络中延迟受限多播调度问题的形式化定义。为了解决该问题，本文首次提出了一种动态规划算法来优化所需要增加活动时间槽的个数。模拟实验结果验证了本文提出的近似算法能够减小能量消耗和传输冗余，提出的动态规划算法能够保证多播路由的实时性。
（3）本文研究了信息物理融合系统中最小延迟数据聚集调度问题。本文给出了协议干扰模型下最小延迟数据聚集调度问题的形式化定义，并且证明该问题为NP-hard问题。本文设计了一种在本地避免冲突的机制。基于该机制，首次提出了一种基于非固定结构的分布式聚集调度算法，该算法同时生成聚集树和无冲突的聚集调度计划。
..........
参考文献（略）