带优先权的时间片多任务分配新算法

本文讨论了实时控制系统的几种常见多任务实时性分配算法的优缺点,并提出一种能满足多任务实时性分配的新算法—用带优先权的时间片分配多任务的算法。

基于相继干扰消除的无线传感网低时延广播算法

近年来,传感器技术、嵌入式计算技术与通信技术迅猛发展且日益成熟,因此传感器节点日益小型化和智能化,促进了无线传感网在战场监视、智能交通、精准农业、建筑结构健康状况监测、灾难恢复、环境监控、医疗监护等军用和民用领域的广泛应用.广播的目的是将数据从源节点分发给网络中的所有节点,在无线传感网中主要用于路由发现和重要通知的发布等.无线传感网应用于战场情报获取或火灾监控等时延敏感领域时,需要将数据快速地从源节点广播给全网所有传感器节点,因此,设计一种低时延的广播算法具有非常重要的理论研究意义和实际应用价值.但是,由于无线信号传输的广播特性,节点的信号传输会对其干扰范围内所有节点的数据接收产生干扰,而信号干扰是影响广播时延的重要因素.在信号干扰约束下的最低时延广播问题是NP(Non-Polynomial)难问题,因此难以设计出多项式时间的最优化算法.现有研究工作通常通过干扰避免调度方法来设计低时延的广播算法,虽然能避免信号之间的干扰,但是不能增加可并发传输的广播链路数目,进而有效地降低广播时延.为了有效地解决该问题,本文首先设计了一种贪婪广播算法GreedyB.该算法通过构造宽度优先搜索树来实现网络节点的分层,依据覆盖节点数最多优先选为父节点的规则来构造广播树,最后采用逐层调度和干扰避免调度的方式来分配广播链路的传输时间片.在贪婪广播算法GreedyB的基础上,本文结合相继干扰消除技术设计了另一种广播算法SICB,致力于进一步降低广播时延.与GreedyB算法不同,SICB算法在分配传输时间片时,分析广播链路之间是否满足相继干扰消除的条件,条件满足时安排在同一时间片,不满足时进行干扰避免调度.本文通过理论分析证明了,GreedyB和SICB两种算法都能提供正确的无信号干扰的广播调度方案,并且两种算法时间复杂度和空间复杂度都是多项式时间的.本文通过大量的仿真实验对所提算法进行了性能分析.仿真实验结果表明,GreedyB和SICB两种算法在不同网络规模、最大传输距离、信号传输功率、噪声功率等网络参数下的广播时延都要低于现有的广播算法,性能优化率最高分别可达43.5%和52.7%.

采用RTNET协议栈的交换式以太网时延测试

主要研究交换式以太网的介质访问控制方式的优化方法,以期降低网络时延,将交换式以太网应用于高实时性控制领域。为了研究终端设备采用时分多址接入技术的访问控制方式,搭建了一个基于RTNET协议栈的交换式以太网测试网段,在Linux内核实时性改造的基础上完成了RTNET实时以太网协议栈的移植,并针对时分多址机制的特性设计了多个测试方案,进行不同的时间片分配。通过对测试结果的分析,总结了优化分配时间片的方法。实验结果表明,在时间片的优化分配下,数据帧在交换机的排队时延大为降低,采用RTNET协议栈比采用TCP/IP协议的网络端到端时延降低了30%。