• 最新论文
  • 山东威海一大学生挥刀自宫:喜欢没有性欲的生活 李幼平院士:三网融合将创造中国全新互联网 叶笃正说自己之所以具有超前的精神 《自然—医学》:加美科学家找到艾滋病新疗法 山东威海一大学生挥刀自宫:喜欢没有性欲的生活 《自然—医学》:加美科学家找到艾滋病新疗法 朱健康小组植物DNA去甲基化调控研究获进展 朱健康小组植物DNA去甲基化调控研究获进展 朱健康小组植物DNA去甲基化调控研究获进展 山东威海一大学生挥刀自宫:喜欢没有性欲的生活 《自然—医学》:加美科学家找到艾滋病新疗法 中国科学报:防灾减灾演练缘何说易行难 复旦校长以世界杯大牌球队遭淘汰警示毕业生
  • 推荐论文
  • 山东威海一大学生挥刀自宫:喜欢没有性欲的生活 李幼平院士:三网融合将创造中国全新互联网 叶笃正说自己之所以具有超前的精神 《自然—医学》:加美科学家找到艾滋病新疗法 山东威海一大学生挥刀自宫:喜欢没有性欲的生活 《自然—医学》:加美科学家找到艾滋病新疗法 朱健康小组植物DNA去甲基化调控研究获进展 朱健康小组植物DNA去甲基化调控研究获进展 朱健康小组植物DNA去甲基化调控研究获进展 山东威海一大学生挥刀自宫:喜欢没有性欲的生活 《自然—医学》:加美科学家找到艾滋病新疗法 中国科学报:防灾减灾演练缘何说易行难 复旦校长以世界杯大牌球队遭淘汰警示毕业生
  • 热门标签
  • 日期归档
  • 基于动态时间片的RM实时调度算法

    来源:www.shuoshisheng.net 发布时间:2019-12-17

    摘要:嵌入式实时操作系统克服了无线抄表系统数据重传多、实时性差、传输效率低等缺点 结合单调速率调度算法和时间片轮换算法的优点,对系统实时调度算法进行了改进,提出了一种基于动态时间片的单调速率实时调度算法,并将该算法应用于无线抄表系统 实验表明,新算法在复杂通信环境下的调度时间接近理想时间,优于传统的实时调度算法。

    关键词:无线抄表系统;嵌入式系统;实时调度算法;动态时间片

    rm基于动态时间片的实时调度算法

    张学军,周浩,阎金通。摘要:嵌入式实时操作系统可以提高无线抄表系统的实用性。新的调度算法主要基于优先级算法,结合了调速调度算法和循环调度算法的优点。实验表明,该算法使复杂通信环境下的调度时间明显接近理想时间,优于传统算法。

    关键词:无线抄表系统;嵌入式系统;实时调度算法;动态时间片

    0简介

    随着城市规划建设水平的提高和城市人口的急剧增加,高层和超高层建筑的数量不断增加,对智能家居提出了更高的要求 作为家庭智能产业链的一部分,智能抄表系统也得到了蓬勃发展。 无线抄表系统作为服务燃气、电力和自来水行业的工具,大大减少了抄表人员的劳动,提高了企业的效率,给居民带来了方便。 然而,传统的无线抄表系统存在数据重传次数多、实时性差、传输效率低等缺点。

    1无线抄表系统

    1.1硬件设计

    无线抄表系统的硬件主要由抄表数据发送器和手持接收器组成。两个系统的硬件结构基本相同,主要由STM32F103系列微控制器芯片、SI4432无线发射芯片、SPI总线等核心部分组成,如图1所示

    图1硬件原理图

    STM32F103微控制器采用ARM Cortex-M3内核,具有强大的中断管理机制,可以为复杂通信环境下的无线抄表系统提供系统级保证,防止数据流过于拥挤和低信噪比造成的数据传输障碍。 此外,其内部SysTick定时器可以提供精确的时钟振荡时序,方便嵌入式系统的移植。

    SI4432无线收发器芯片提供的频率范围为240MHz至930MHz,可调输出功率高达+20dBm。它支持调频和扩频。它还提供自动唤醒定时器、信道强度评估、低功耗检测器、64字节发送/接收、自动数据包处理等功能。它还支持串行接口总线连接。

    1.2 μC/OS-II实时内核的移植

    μC/OS-II内核是一个开源的抢占式内核[1],它包括操作系统的基本特征,如任务调度、任务管理、时间管理、内存管理、定时管理、任务通信和同步[2] 它的优先抢占策略可以保证系统的实时性。 在μC/OS-II内核中,只需要迁移操作系统、操作系统和操作系统文件,大大降低了迁移[3的难度 μC/操作系统的定时中断保证了系统的实时性。每个时钟节拍都会产生一个定时中断。中断后,任务将按计划运行就绪表中优先级最高的任务。 系统架构如图2所示

    图2系统架构

    2实时调度算法

    实时调度算法是实时操作系统的核心。经典的实时调度算法主要包括单调速率调度算法和最早截止时间优先调度算法[4]

    RM调度算法是一种典型的静态优先级调度算法。它根据任务执行周期的长度来确定调度优先级。执行周期短的任务具有更高的优先级 这种调度方法主要适用于周期性任务。对于突发任务,无法提前估计执行时间,这将导致系统执行效率低下。 对于给定的任务集{S1、S2、S3、S4.Sn},调度器的利用率必须满足

    (1)

    其中Cn表示任务Sn的执行时间;Tn代表任务序号的执行周期,而L(n)代表调度器利用率的最低界限 当n→∞时,L(n)→ln2≈ 0.693 当整个任务集的负载小于1(n)时,RM算法调度是可行的[5]

    传统的远程监控实时调度算法,时间越短,任务的优先级越高。但是,由于没有时间片或其他终止策略设置,如果实时任务由于某种自身原因或环境原因而超过其执行时间,并且任务没有完成,则修改后的任务将保持当前的高优先级,直到执行完成 这将推迟到后续任务,形成多米诺效应,导致多个任务超过最后期限。 在实际情况下,特别是当无线通信传输中容易出现过载时,控制器的调度工作大大增加,性能下降。 [6]

    EDF调度算法是一种典型的动态优先级调度算法。它根据就绪队列中每个任务的最后期限分配优先级。截止日期最近的任务具有最高优先级。 主要优点是:任务优先级可以根据需要动态变化,使系统具有更好的适应性。 任务调度优先级定义为di(t)-t,其中di(t)是任务时间限制,t是当前时间,两者之差表示任务的紧迫性

    对于给定的任务集{S1、S2、S3、S4.序号},任务的调度器利用率必须满足以下条件[5]

    (2)

    其中Cn代表任务序号的执行时间;Tn代表任务序号的执行周期,而L(n)代表调度器利用率的最低界限

    结合单调速率调度算法和时间片轮换算法的优点,对系统实时调度算法进行了改进,提出了一种基于动态时间片的速率单调实时调度算法,并将该算法应用于无线抄表系统 实验表明,新算法在复杂通信环境下的调度时间接近理想时间,优于传统的实时调度算法。

    3 RM基于动态时间片的实时调度算法

    3.1算法步骤

    在应用无线抄表系统的实际环境中,如果节点所在环境的信噪比高,则传输时间较短。如果节点所在环境的信噪比较低,传输时间会更长。 因此,每个传输任务都被视为一个任务。如果信噪比高,任务的优先级设置为高,否则优先级设置为低。提出了一种分布式测试系统实时调度算法。算法步骤是:

    register

    当手机进入小区时,首先向小区中的所有设备发送广播帧,提醒每个仪器设备进行注册 手机发送广播后,可能有多个电表同时向手机发送注册帧 为了减少碰撞的发生,我们采用了经典的ALOHA算法。 ALOHA算法是一种随机接入算法[7-8],其工作原理是:手机发送广播帧,仪表接收广播帧生成注册帧,并立即发送到无线信道;如果在指定时间内收到手机的确认响应,则注册成功;否则,执行重传策略,即手机在随机退回几个时间序列之后被发送注册帧,直到注册成功,如图3所示

    图3注册图

    2,数据传输

    (1)建立多个独立的就绪队列,并根据不同的优先级将实时任务分配给多个不同级别的队列

    (3)第一个任务时间片是初始时间片,动态调整队列中剩余每个任务的时间片 如果上一个任务在时间片内完成,下一个任务的时间片将减少0.05秒,依此类推,逐渐减少。 如果某项任务不能在时间片内完成,时间片的设置应每次增加0.05秒,直到任务完成。 如图5所示

    (4)如果队列中的实时任务运行时间超过分配的运行时间,如果它继续运行,可能会导致整个队列延迟,然后放弃该任务并记录其标识

    (5)执行完所有队列后,将根据记录的标识依次对失败的任务进行轮询通信

    图4基于时间片的实时调度算法队列示意图

    图5时间片动态设置示意图

    3.2算法实现

    1,变量设置

    要将改进的实时调度算法应用于实际系统,需要在系统代码中添加队列优先级和任务时间片等变量 在无线抄表系统中,优先级由电表所处的无线环境决定,量化值是信噪比。 由于该系统中使用的无线通信芯片可以测量当前传输环境的信噪比并形成数值,因此可以向仪器的注册帧添加3位信号强度位 000到111被生成为量化标度表,如表1所示

    表1量化等级表

    优先量化等级信号强度(DBMW)

    1,000 (0)-66 ~无穷大

    2,001 (1)-67 ~-70

    3,010 (2)-71 ~-74

    4 011(3)-75 ~-78

    5 100(4)-79 ~-82

    6 101(5)-83 ~-86

    7 110(6)-87 ~-90

    8 111(7)-90 ~无限小

    手机在接收到每个仪器设备的注册帧后,可以根据注册帧中包含的信号强度量化值将所有仪器分成多个就绪队列,其中高信号强度的仪器队列被赋予高优先级,低信号强度的仪器队列被赋予低信号强度

    每个队列的初始时间片T与序列优先级P之间的关系是

    T=kP(k是常数)(3)

    经过大量的实际测试,发现在正常信号强度的情况下,每个任务需要大约0.8s才能完全传输。 如果优先级的值从1到8,那么0.25更适合于k

    2。设置数据帧

    在此调度算法中,一个队列对应多个任务。系统将构造一个结构化的操作系统行来控制队列,这被称为队列控制块。如图6所示,它主要包含以下元素:

    (1)OSPrio:队列的优先级,占3位

    (2)line_Stat:队列的状态。如果队列处于就绪状态,则该变量设置为就绪,占2位。

    (3)计数:当前优先级下包含的任务数,占9位

    (4)Tcount:当前队列的初始切片大小,占3位

    ospiro(3位)line _ stat(2位)count(9位)t count(3位)

    图6队列控制块结构

    当队列被调度并进入中央处理器执行时,任务根据时间片旋转进行调度,同时时间片被动态调整 因此,系统还需要添加一个结构化的操作系统任务来控制任务,称为任务控制块。如图7所示,它主要包含以下元素:

    (1)任务标识:当前任务的标识,占10位

    (2)task_Stat:当前任务的状态。如果状态为就绪,则该变量设置为就绪,占2位。

    (3)task_Tcount:当前任务的时间片大小,占3位

    task _ id (10位)task _ stat (2位)task _ tcount (3位)

    图7 task control block structure

    4 performance analysis and comparison test

    我们多次测试了仪器和手机在不同信噪比环境下成功进行单独通信所需的时间。实验数据如表2所示

    表2不同信噪比下电表和手机之间的通信时间

    信噪比(dB)优先级平均完成时间

    -650.2

    -7320.35

    -8140.6

    从表2可以看出,随着信噪比的降低,通信时间逐渐变长。当信噪比较低时,完成所需的时间突然变得更长。当信噪比接近-100分贝时,就会发生通信故障 因此,选择前三个信噪比环境,并且分别在0.2s、0.35s、0.6s和0.7s数据周围,随机选择6个值来生成24个数据和4个仿真数据队列 为了模拟真实通信环境中的随机通信延迟和干扰,在测试程序中人为添加了干扰延迟。当信噪比较低时,干扰延迟的概率增加,如表3所示。

    表3模拟数据

    队列6任务完成时间

    队列1 0.29 0.24 0.22 0.19 0.24 0.28

    队列2 0.31 0.33 0.36s 0.38 0.40 0.44

    队列3 0.55 0.55 0.66 0.65 0.71 0.53

    队列40.70 0.67 0.66 0.69 0.71

    该测试要求所有任务至少完成12.5秒。 这24个任务被中断形成5个不同的序列方案,这些方案被导入到基于动态时间片的实时调度器和传统的实时调度器中,以模拟所有数据点在实际通信中发起通信的情况。 计算完成所有任务所需的时间5次,并绘制一条曲线,如图8所示。 传统的远程监控实时调度算法分别需要15.50秒、14.80秒、15.15秒、15.30秒、14.98秒进行五次测试,平均时间为15.146秒 基于动态时间片的资源管理调度算法分别需要14.12秒、15.05秒、14.95秒、14.65秒、13.95秒进行5次测试,平均时间为14.544秒,比传统资源管理算法的平均性能高出约4%。 从图8可以看出,基于动态时间片的RM实时调度算法的完成时间对于5个不同的任务序列是不同的,这表明不同的任务序列对完成时间有影响。 然而,在5次测试中,基于动态时间片的实时调度算法的最差完成时间仅比最小时间多2.55秒

    为了模拟实际通信环境中随机出现的通信延时与干扰,在测试程序中人为添加干扰延时,信噪比较低时,干扰延时发生的概率加大。为了对比明显,将第2次测试中的干扰延时出现的次数减少,使之明显低于现实通信环境中的干扰。测试表明,改进的算法未发生作用且由于时间片的设置,用时较长,所以在图8中第2次测试时改进算法用时较传统RM算法略长。在随后的第3、第4、第5次测试中,将干扰延时发生的概率再次调整到正常范围以内。

    实验结果表明,基于动态时间片的RM实时调度算法的性能优于传统RM实时调度算法。传统的RM实时调度程序在运行程序时,虽然在优先级比较高即环境信噪比比较好时性能很高,但一旦遇到低信噪比任务,任务完成很容易超时,导致后续任务不断延期,性能退化快,

    图8模拟测试

    在完成该抄表系统的硬件设计与系统移植后,分别在空旷区域(无干扰)和一幢六层的居民楼(架设同频率的无线电遥控器作为干扰)架设5台仪表终端和一台手持机,做了无线抄表试验,实验结果如表4所示。

    表4现场测试结果

    通信机制 测试环境 完成时间(s)

    轮询 空旷区域 5

    轮询 居民楼 7

    实时调度 空旷区域 3

    实时调度 居民楼 5

    5 结束语

    实际测试表明,在引入了基于动态时间片的RM实时调度算法后,无线抄表系统在全部数据抄送的完成时间上得到了改进。实验证明,该实时调度算法在无线抄表系统中的应用是可行的,值得推广。当然,该系统仍然有可以改进的空间。例如,在对时间片处理上,可以应用更复杂更有效的算法,对不同信号强度下传输时间进行评估,从而可以更高的提高系统效率。微控制器芯片的许多组网功能还可以利用到无线抄表系统中,从而使该系统更加的智能化。

    友情链接: