信息物理融合系统中实时数据传输与调度算法研究

发布时间：2018-03-06 00:21

  本文选题：信息物理融合系统　切入点：占空比传感器网络　出处：《哈尔滨工业大学》2017年博士论文　论文类型：学位论文

【摘要】：信息物理融合系统是一种集计算、通信、感知和控制等功能为一体的大规模分布式异构系统,主要由传感器网络、执行组件、控制器和网关设备等构成。由于其能够对物理世界高效实时、分布协同、安全可靠地感知和控制,实现信息世界与物理世界的高度融合,目前已经在国防军事和社会生活中得到了广泛地应用。在信息物理融合系统中,传感器网络通过协作地采集、感知和计算之后将采集到的信息以多跳传输方式发送给用户和终端,然后用户和终端根据采集到的信息生成相应的反馈控制命令。在这其中,感知数据的实时传输和调度至关重要。例如,在战场上的目标探测与追踪、医疗救护以及化学放射性元素检测和预防等系统中,控制信息或关键数据必须在限制的时间内到达用户和终端,以便系统及时作出反应从而避免灾难性的后果。另一方面,当传感器节点要求工作在占空比模式来节省能耗和延长网络生存周期时,数据传输的延迟将会急剧增加。在这种网络中,实时数据传输与调度问题变得更为复杂,但是目前此类问题研究较少。因此,本文将主要对占空比网络中的实时数据传输与调度等问题展开研究。首先,本文研究了信息物理融合系统中实时端到端数据传输的路由算法设计问题。实时路由是信息物理融合系统中非常重要的一个服务,是很多应用的基础。为了实现占空比传感器网络中任意端到端之间的实时数据传输,本文提出了一种基于动态切换的实时路由算法(DSRT)。针对占空比网络中睡眠延迟太大的特点,DSRT首先利用2跳邻居信息提出了一种可达速度的概念来帮助发现延迟更优的路径(实验证明该方法至少能够发现20%左右延迟更优的路径)。另外,本文首次发现在占空比网络中节点的拥塞程度不仅与缓冲队列中数据包的个数有关,而且与数据包的目的节点有关。然而传统的方法无法区分此类拥塞,因此DSRT利用动态切换机制提出了一种通过将缓冲队列分类的拥塞避免算法。另外,考虑到传感器节点在无线传输时链路非常不可靠的特点,本文还提出了一种基于扩展活动时间槽的实时路由算法(RRAD)。在RRAD算法中,本文利用扩展活动时间槽和ARQ-based传输机制将数据包的延迟降低了1倍以上。另外,RRAD针对占空比网络中节点异步醒来的特点,提出了一种轻量级的潜在转发节点选择算法。该算法能够给节点提供一次额外的转发机会。大量的模拟实验验证了本文提出的DSRT和RRAD算法在路由延迟和可靠性方面的高效性能。其次,本文研究了信息物理融合系统中节能及延迟受限的多播调度问题。在信息物理融合系统中,多播路由是提供一对多通信的一种基本服务,即源节点同时将数据包发送到多个目的节点。然而,当传感器节点工作在占空比模式时,发送节点需要传输多次以将相同的消息广播给一组相邻的节点,这使得最小能耗多播问题变得异常复杂。因此,本文研究了占空比传感器网络中的最小能耗多播问题,并证明了该问题是一个NP-hard问题。为了解决这一问题,本文提出了辅助图的概念用于统一调度节点发射功率和发送时间槽以及构建最小能耗多播树,并提出了构建辅助图的贪心算法。基于上述辅助图,本文提出了近似比为4lnK的近似调度与构造算法,其中K是目标节点的数目。另一方面,由于占空比网络中节点只能够在其处于活动状态时接收数据包,导致多播延迟异常高。但是,目前现有的算法均没有考虑如何减小多播延迟,使其处于用户预期之内。因此,本文还研究了延迟受限的多播调度算法,通过在网络中增加最少个数的活动时间槽来使得多播延迟小于用户给定的延迟阈值。为了解决该问题,本文提出了一种动态规划算法来优化所需要增加活动时间槽的个数。理论分析和实验结果验证了本文提出的算法在减小能量消耗和传输冗余以及保证实时性方面的有效性。第三,本文研究了信息物理融合系统中最小延迟数据聚集调度问题。在信息物理融合系统中,数据聚集可以方便sink节点获取整个网络的摘要信息。而最小延迟数据聚集调度问题(MLAS),即寻求一个最快无冲突的聚集调度计划,已经受到了学者们的广泛关注。但是当节点工作在占空比模式时,节点只能在活动状态时接收数据包。在这种网络中,利用网络中有限的活动时间槽来减少延迟极为重要。但是现有的算法很少考虑这个问题,并且大都假设在聚集过程中采用固定的结构来生成聚集树,这无疑极大地限制了活动时间槽的利用率。因此,本文考虑了基于非固定结构的MLAS问题。本文首次给出了占空比网络中分布式聚集调度算法,该算法同时生成聚集树和无冲突的聚集调度计划。接着,本文理论证明了该算法的聚集延迟上界为(?),其中C表示占空比,ξ=|2π/arccos(1+1/ε)|,ε是[0.05,1]中的一个实数,R表示网络的半径,?表示最大的度数。大量的模拟实验证明本文提出的算法能够将活动时间槽的利用率和聚集延迟改善1倍以上。最后,本文研究了信息物理融合系统中最小延迟信标调度问题。在信息物理融合系统中,信标调度要求每个节点在本地将信标包广播给所有的邻居节点。然而,在占空比网络中,最小延迟信标调度问题缺乏研究。已有的工作均有非常强的假设,即每个节点在一个工作周期内只能醒来一次。为了适应更普遍的情况,本文研究了占空比网络中最小延迟信标调度问题,其中每个节点在一个工作周期内可醒来多次,该问题被称为MLBSDCA问题。本文首先提出了一种基于边的调度框架。基于该框架提出了一种启发式的调度算法来解决协议干扰模型下的MLBSDCA问题。接着,提出了一个具有(ρ+1)2·||近似比的近似算法来进一步降低信标延迟,其中ρ表示干扰半径,|W|表示一个工作周期内最多可允许活动时间槽的个数。当ρ和|W|等于1时,该算法的近似比为4,优于以往算法的近似比10。另外,针对物理干扰模型下的MLBSDCA问题,本文提出了两种近似算法,并且证明了其近似比。大量的模拟实验证明本文提出的算法能够将信标延迟降低2倍以上。
[Abstract]:......
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP212.9;TP301.6
，

本文编号：1572542