（通信与信息系统专业论文）基于tinyos的无线传感器网络任务调度的研究与改进.pdf

摘要 摘要 随着无线传感器网络的应用场景越来越广泛，无线传感器网络的相关技术受 到了越来越多的关注和研究。由于无线传感器网络的特殊性，如何在资源受限的 情况下实时地完成感知、通信、控制和计算工作是无线传感器网络研究面临的主 要问题。解决这个问题的关键是研究满足无线传感器网络操作系统的任务调度策 略。 本文选择在t i n y o s 操作系统下对调度策略进行研究与改进。通过对无线传感 器网络任务调度机制的研究，确定了改进方向和目标。论文接下来详细分析了 t m y o s 2 x 的任务调度机制，并且指出了其内核调度机制的不足。针对实时性和 吞吐量两个不同方面提出了两种改进算法：不可抢占式e d f ( e a r l i e s td e a d l i n ef i r s t ) 算法和动态优先权算法，并对算法的可调度性进行了分析，最后通过t o s s i m 仿 真器进行仿真实验，验证了这两种改进算法使系统的性能得到了提升。 关键词：调度机制t i n y o s 实时性不可抢占式动态优先权 基于t i n y o s 的无线传感器网络任务凋度的研究与改进 a b s t r a c t a b s t r a c t w i t ht h ea p p l i c a t i o no fw i r e l e s ss e n s o rn e t w o r ki sm o r ea n dm o r ee x t e n s i v e ，t h e r e l e v a n tt e c h n o l o g yo fw i r e l e s ss e n s o rn e t w o r ki sg e t t i n gm o r ea n dm o r ea t t e n t i o na n d r e s e a r c h d u et ot h es p e c i a lc h a r a c t e r i s t i c so fw i r e l e s ss e n s o rn e t w o r k , t h em a i n p r o b l e mf o rw i r e l e s ss e n s o rn e t w o r kt od e a lw i t hi st h a th o wt oc o m p l e t es e n s o r y p r o c e s s ，c o m m u n i c a t i o n , c o n t r o la n dc a l c u l a t i o ni nr e a lt i m ew i 廿ll i m i t e dr e s o u r c e s t h e k e yt os o l v et h i sp r o b l e mi st os t u d yt h es c h e d u l i n gs t r a t e g yc o m p a t i b l ew i t hw i r e l e s s s e n s o rn e t w o r k o p e r a t i n gs y s t e m i nt h i st h e s i s ，s c h e d u l i n gs t r a t e g yi sr e s e a r c h e da n di m p r o v e di nt i n y o so p e r a t i n g s y s t e m t h ed i r e c t i o na n dg o a l sf o ri m p r o v e m e n ta r ed e t e r m i n e dt h r o u g ht h er e s e a r c h o nt h es c h e d u l i n gs t r a t e g yo fw i r e l e s ss e n s o rn e t w o r k t h e nt h es c h e d u l i n gm e c h a n i s m o ft m y o s - 2 xi sa n a l y z e di nd e t a i l ，a n dt h es h o r t c o m i n g so fs c h e d u l i n gm e c h a n i s ma r e p o i n t e do u t n o n - p r e e m p t i v ee d f ( e a r l i e s td e a d l i n ef i r s t ) a l g o r i t h ma n dd y n a m i c p r i o r i t ya l g o r i t h ma l ep u tf o r w a r dt oi m p r o v et h er e a l - t i m ea n dt h r o u g h p u ta n dt h e s c h e d u l a b i l i t yo ft h et w oa l g o r i t h m si sa n a l y z e d f i n a l l y , t h es i m u l a t i o nb yt o s s i m v e r i f i e dt h a tt h ep e r f o r m a n c eo ft h es y s t e mi si m p r o v e di nt h et w oa l g o r i t h m s k e y w o r d s ：s c h e d u l i n gs t r a t e g yt i n y o s r e a l - t i m e n o n - p r e e m p t i v e d y n a m i cp r i o r i t y 基于t i n y o s 的无线传感器网络任务调度的研究与改进 第一章绪论 第一章绪论 1 1 研究背景 随着无线通信和电子信息技术的飞速发展，无线传感器网络表现出越来越广 泛的应用前景，在家庭智能、工农业、环境监测、城市管理、生物医疗、抢险救 灾、军事国防、危险区域探测以及外层空间探索等许多重要领域都有潜在的实用 价值，引起了许多国家学术界和工业界的高度重视。而无线传感器网络是由大量 无处不在的、具有通信和计算能力的微小传感器节点密集布设在无人值守的监控 领域而构成的能够根据环境自主完成指定任务的“智能 网络系统，是一种超大 规模、无人值守、资源严格受限的全分布系统，采用多跳对等通信方式将整个区 域的信息数据发送到远程控制管理节点，其网络拓扑动态变化，具有自组织、自 治、自适应等智能属性【l 】。 由于无线传感器网络的特殊性，需要操作系统能够高效地使用传感器节点的 有限内存、低速低功耗的处理器、传感器、低速通信设备、有限的电源，且能够 对各种特定应用提供最大支持。然而传统通用嵌入式操作系统功能复杂，代码尺 寸相对过大，不满足传感器网络节点的资源限制，不能直接移植到无线传感器网 络节点上。目前出现众多的无线传感器网络操作系统，其中由加州大学伯克利分 校依托s m a r t d u s t 项目开发出来的t i n y o s 使用最广泛。它是一个开源的轻量级嵌入 式操作系统，其特点是体积小、结构高度模块化、基于组件的架构方式、低功耗 等，这使它能够突破传感器节点各种苛刻的限制，可快速实现各种应用，非常适 合w s n 的特点和应用需求，因而被广泛应用于w s n 中，并成为很多系统的参考设 计。 任务调度管理是任何操作系统的核心功能，其工作是通过对任务集合的合理 调度，使各项人物满足各自的时限和性能需求，以增强系统的实时性和可靠性。 操作系统通过一个调度程序( s c h e d u l e r ) 来实现调度功能。调度程序是以函数的形式 存在，用来实现操作系统的调度算法，而调度程序本身并不是一个任务，只是以 函数的形式调用，并且可以在内核的各个部分进行调用。 如何在资源受限的情况下实时地完成感知、通信、控制和计算工作是无线传 感器网络研究面临的主要问题。而解决这个问题的关键是如何在软件上对系统资 源进行合理的分配和管理，即需要研究满足无线传感器网络特殊要求的操作系统 调度策略。 2 基于t i n y o s 的无线传感器网络任务调度的研究与改进 1 2 1 无线传感器网络 1 2 论文相关技术研究现状 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k , w s n ) 是一种目前在国际上备受关 注前沿应用性科学。是指有大量部署在作用区域内、具有无线通信与计算能力的 小传感器节点，通过自组织方式构成，能根据环境自主完成指定任务的分布式智 能化网络系统。w s n 涉及到了m e m s 技术、s o c 技术、计算机技术、传感器技术 和通信技术等学科，是这些学科高度交叉的产物。上世纪九十年代末，随着计算 机技术与微电子技术的突破，使得这项技术真正进入了飞速发展的时期【3 j 。 对传感器网络技术研究最多的国家是美国。美国对传感器网络的高度热情源 于实际应用尤其是军事应用的迫切需求，因为增强军队的感知能力能够迅速提升 军队的战力，而传感器网络就是增加这种感知能力的一种倍增器。仅从1 9 9 9 年起， 美国军方就有c 4 i s r t 计划、s m a r td u s t 项目、s e n s i t 计划、s e a w e b 计划等与无 线传感器网络有关的项目。现在，上述军用项目中产生的成果，已经开始转化， 转向于商业开发方面的应用。 无线传感器网络虽然与一般的无线自组织网络有相似之处，但同时也存在很 大的差别，主要特征如下【l j ： ( 1 ) 硬件资源有限。考虑到节点的实用性和存活率，其体积功耗不能太大，因 此节点的计算能力和内存外存比普通计算机功能要弱很多。 ( 2 ) 节点能量有限。节点的体积微小，所以其电池所携带的能量也非常有限， 再加上节点所处区域环境恶劣，人员不可能去现场更换电池，所以节点基本上是 一次性的。 ( 3 ) 通信能力有限。无线通信的能量消耗与通信距离的关系为：e = k d ”。其中 d 为通信距离，2 ，其任务参数为e l = g o r e s ，西= 2 0 0 m s ， 乞= 6 0 m s ，如= 1 6 0 嬲。当i = l 时，只要t 满足条件r 啤 嘭 = 1 6 0 m s ，则下列 不等式始终成立： 嘞( 志一- ) 8 0 + 一窆州i 。1 - u - j 1 6 0 ， 当i = 2 时，只要f 1 6 0 m s ，则下列不等式也始终成立： ，g ( 志一t 6 0 + ，羲【- 志j 8 。 ， 代表任务集q = 五，五 在不可抢占式e d f 算法下是可调度的。 在n p e d f 调度算法中，s c h e d 组件包括一些重要函数，如 s e h e d u l e r i n i t 0 ，s c h e d u l e r r t m n e x t t a s k 0 ，s c h e d u l e r t a s k l o o p 0 ，p o s t n p e d f t a s k 0 ，p o s t b a s i e t a s k 0 等。其中函数p o s t n p e d f t a s k o 是本算法的核心函数。 p o s t n p e d f t a s k ( u i n t 8 _ ti d ，u n i t 3 2 _ td e a d l i n e ) 函数是n p e d f _ q u e u e 队列投递函 数。该函数实现了不可抢占式e d f 调度策略，其核心思想是通过参考被投递的任 务( 包括实时任务) 相对截止时限来计算绝对时限，并且将其与其队列中等待的 任务的截止时限依次做比较，使得该任务队列总能保持较近运行截止时限的任务 排在队列前面，以便能够被优先调度。如果任务的截i e 时限相同则执行实时任务， 第四章改进策略的研究与实现 3 5 其他任务采取f i f o 调度策略。 n p e d f 调度算法具体算法如图4 1 所示。其中i s n p w a i t i n g 函数的作用是检 测任务是否已经在任务队列中，如果已有该任务的话则不能够再将其投入队列， 如果一个任务想连续执行的话，可以在投递该任务的组件的任务代码末尾处再次 投递该任务。tc u l t ，tp r e v 分别是在查找任务插入位置过程中所设的局部变量， 指向当前任务i d 和前一个任务i d 。l o c a l 变量是指当前时刻的时间值，该值是一 个整型变量。d e a d l i n e 变量作为参数是从上层组件传递进来的，其值代表该被投递 任务的相对截止时限。 基于t i n y o s 的无线传感器网络任务调度的研究与改进 4 1 2n p e d f 算法性能评估 图4 1 n p - e d f 算法流程 实验设置两个节点a ，b ，a 向b 发送不同种类的数据包。为了比较n p e d f 算法与其他算法的性能差异，将本实验中的任务全部设置为实时性任务，每个任 务都有自己的相对截止时限。 第四章改进策略的研究与实现 3 7 表4 1 实时任务参数 任务执行时间m s相对截止时间m s t a s k l1 5 02 3 0 t a s k 21 2 0 2 l o t a s k 39 01 9 0 t a s k 46 01 7 0 t a s k 53 01 5 0 节点a 初始时仅运行发包任务t a s k l ，然后每隔一个固定时间段，通过虚拟 中断触发新的发包任务t a s k n 。不同任务发送的数据包中包含有该任务的时限信息。 通过统计对比节点b 受到的不同种类的超时数据包的个数，比较使用不同算法所 导致的系统实时性的不同。 图4 2e d f ，n p e d f ，f i f o 算法超时包率比较 从图4 2 可以看出，随着启动任务的相对截止时限越来越短，采用f i f o 算法 的系统的超时数据包越来越多，任务完成情况越来越不理想，因为实时性强的任 务被安排在了队尾，需要等到前面的任务全部执行完毕后才能被启动。e d f 算法 3 8 基y - t i n y o s 的无线传感器网络任务调度的研究与改进 的超时数据包最低，但是它充分考虑了任务的执行时间等因素，能更好的保证任 务完成时限，但是e d f 算法过于复杂，会导致代码量增大，加大传感器网络中的 计算开销，这是没有必要的。而n p e d f 算法在计算复杂性和任务的实时性之间 取得了不错的折中，适合实施于无线传感器网络的应用。 4 2 1d p 调度算法思想 4 2d p 算法 当本地处理任务过多时，数据包接收可能被延迟从而导致通信性能下降，尤 其当数据在本地节点汇聚，经过各种处理后再往基站发送的时候，如果数据包接 收处理任务放在任务队列队尾，那么只有等到前面的任务全部处理完后，才能处 理数据接收任务，这样必然会影响到数据包的吞吐量。为此，如果数据接收处理 的任务如队列时，经过优先级地分配处理，对任务队列进行调整，则可能会改善 通信状况。 动态优先级( d y n a m i cp r i 嘶t ，r ) 算法具体实现方法是，给每一个任务都分配一个 优先级，比如按照任务实时性要求的严格程度分为1 3 三级，最严格的任务是3 级，而一般性的任务则默认为l 级。当某个任务a 到来的时候，调度器从就绪队 列的末尾开始，将它的优先级依次和队列中任务的进行比较，直至出现更高优先 级或者相同优先级的任务为止，假设其为任务b ，此时调度器将任务a 插人到任 务b 之后，而队列中原来排在任务b 后面的其他任务依次向后移一位，如果队列 在插入前已经满了，队尾的最后一个任务将被放弃。优先级越高的任务，将在队 列中排得越靠前。另外，优先级的设置可以根据需要进行扩充和调整，比如分级 为4 级甚至更多。上述这种基于优先级的“f i f o 策略和简单的f i f o 策略有明显 的不同，但是调度器在给任务分配处理器的时候还是只分配给就绪队列队首的第 一个任务，而且任务一旦运行起来就不能被其他任务所打断，这些和简单的f i f o 策略是一致的。 调度函数通过增加一个优先级任务链表和任务优先级值数组。从优先级链表 头到表尾，任务的优先级依次下降。如果有高优先级任务被提交，则从链表头开 始比较优先级值，直至找到比其值大的任务并在其前插入任务。用参数化接口实 现优先级调度的重要优点是：每个任务都有自己的位置，不会产生队列满将队列 尾的低优先级任务丢弃的情况。 p o s t d p t a s k ( u i n t 8ti d ，u i n t 8tp d o r i t y ) 函数是d pq u e u e 队列投递函数 t a s k d p p o s t t a s k i d 】的执行主体。e v e n t t i m e r f i r e d o 函数是一个时钟中断事件函数， 该事件是由低层组件h i l t i m e r m i l l i c 组件所定期触发，由s c h c d 组件定义其函数主 体。以上两个函数合作实现了动态优先级任务队列的任务调度策略，其核心思想 第四章改进策略的研究与实现 3 9 是：任务进入就绪队列之前均有一个初始的优先级，在进入该队列之后，通过定 期增加任务队列中等待任务的优先级，以确保先进入队列的任务不会一直被频繁 投递的高优先级任务所阻塞，并将后来投递的任务安插到队列的合适处，使得该 动态优先级任务队列总能保持较高优先级的任务排在队列前面的规则，以便能够 被优先调度。 p o s t d p t a s k 函数使得任务队列能够按照给定优先级的大小进行插入排队，其 具体算法流程与n p e d f 算法不同之处是在搜索任务队列时不是参考的每个任务 的截止时限值n p _ t i m e i d ，而参考的是当前任务优先级的值d p _ p r i o d t y i d 。 t h n e r f i r e d o 事件函数完成定期增加队列中任务优先级( p r i o r i t y ) 的工作。其算法 流程图如图4 3 所示，其中n u m 为任务队列的索引值，m a xp r i 为最高优先级， 并假设优先级越高，其值越大。其主体思想是，设置一个时长为l 的定时中断， 每当定时中断到来后即启动中断处理程序，在中断处理程序中，依次将就绪任务 队列中任务的优先级增加某个常数增量( 本文取1 ) ，如果该优先级值已达最大，则 不再予以增加。 基于t i n y o s 的无线传感器网络任务调度的研究与改进 图4 3t i m e r f i r e d 0 事件函数流程 4 2 2d p 调度算法性能评估 实验设置两个节点a ，b ，包括一个发送节点( s i n k 节点) 和一个接收节点( r e c e i v e 节点) 。在发送节点a 上执行数据包的发送任务和本地任务的处理，接收节点b 上 执行数据包的接收任务，同时负责计算转发数据包的数量。 ( 1 ) 本地任务提交频率对系统的影响 实验假设处理本地数据的任务的频率分别为5 h z ，1 0 1 - 1 z ，1 5 1 - 1 z ，通过观察节 点a 发送数据包的速率比较f i f o 和动态优先级算法的性能。 第四章改进策略的研究与实现 4 l 籁 七 团 咚 籁 缎 怒 念 增 图4 4 本地频率对节点发送数据的影响 从图4 4 可以看出，如果本地没有数据处理任务，动态优先级和f i f o 任务调 度机制发送包的速率相同，表明在整体任务比较少的情况下，动态优先级d p 调度 机制对发送方的发包速率并没有明显的改进。当节点运行5 h z 的本地任务时，发 送包的速率没有太大差别，但是已经表现出稍微的不同，随着本地任务频率的逐 渐增大，d p 算法调度机制的发送包速率明显高于f i f o 调度机制，由此可以看出， 本地任务发生频率比较高的情况下，动态优先级d p 调度机制相比f i f o 显著提高 了系统性能。 ( 2 ) 本地任务执行时间对系统的影响 实验主要验证节点的本地任务执行时间对网络吞吐量的影响。 发送节点a 的本地处理任务的频率保持在1 0 h z ，让1 0 h z 的本地任务所消耗 的时间发生变化，以次来观察不同的执行时间对网络吞吐量的影响。 4 2 基- f ：t i n y o s 的无线传感器网络任务调度的研究与改进 黎 七 固 螺 籁 煳 越 愈 坩 图4 5 本地任务执行时间对发送节点a 的影响 从图4 5 可以看出当本地任务执行时间达到5 0 s 以上时，f i f o 调度算法的发 包率只有2 个秒，而动态优先级d p 调度算法依然可以达到9 个秒，由此可见， 在本地任务执行时间比较长的情况下，动态优先级d p 调度算法依然可以获得不错 的网络吞吐量。 发送节点a 以1 0 h z 的频率发送数据包，接收节点b 接收数据包的同时运行 频率为1 0 h z 的本地任务。同上，让该任务的执行时间发生变化，以此来观察接收 数据包的情况。 第四章改进策略的研究与实现 4 3 籁 牛 圃 嗥 籁 擎 辎 狯 潆 本地执行时间，s 图4 6 本地任务执行时间对接收节点b 的影响 从图4 6 可以看出动态优先级d p 调度算法在接收数据包方面有很大的改善， 在任务没有优先级的情况下，当接收节点任务的执行时间超过6 0 s 的时候，接收节 点b 接收的数据将为0 ，发生过载现象。发生这种现象的主要原因是f i f o 接收包 的任务没有被提交，检测信道的时间之后就再也没有被唤醒。而在动态优先级d p 调度算法下，任务队列中即使全是处理本地数据的任务，接收包的任务因为被给 了更高的优先级，提交任务的时候插在任务队列首部以抢先执行。 4 3 不同算法节点能耗的比较 设置1 5 0 m 1 5 0 m 的仿真平面区域，在该区域内随机散布n 个节点。该区域内 所有节点在规定时间内完成本地数据采集任务和多任务路由转发任务等，在不同 的调度算法支持下，不断的改变节点总数n 的个数，来比较每个节点的平均能耗。 基于t i n y o s 的无线传感器网络任务调度的研究与改进 善 耀 口 m 匠 露 * 图4 7 不同算法下节点的平均能耗 从图4 7 可以看出，在节点个数相同的情况下，f i f o 、d p 、n p e d f 三种算 发的节点平均能耗依次增大，主要是因为d p 算法考虑了优先级，相比f i f o 有了 更多的开销，节点能耗增加，而n p e d f 更注重了系统的实时性，相比来说算法 比前两种复杂，因此系统开销最大。但是经过比较计算，这两种算法相比f i f o 节 点的平均能耗增加比约为6 和8 ，在系统开销的可接受范围。 4 4 改进算法的实现 改进算法的实现实际上是替换调度器的过程。t i n y o s 调度器是以 t i n y s c h e d u l e r c 组件实现的。默认的t m y o s 调度器实现是s c h e d u l e r b a s i c p 模块， 默认的调度器组件是某一配置( c o n f i g u r a t i o n ) ，可连接到s c h e d u l e r b a s i c p 。 因特殊应用要替换调度器，开发者需将t i n y s c h e d u l e r c 配置放入应用程序目 录，这将取代默认。调度器组件提供了配线方法来实现所需的调度方式。所有的 调度器实现必须提供带参数的t a s k b a s i e 接口，像s c h e d u l e r b a s i c p 一样；也要支 持n e s t 中p o s t 语句和任务声明，使能t i n y o s 内核操作。总之，t i n y o s 不用修改 内核代码来实现新的调度方法。所有的调度器实现都要提供调度接口。 在n p e d f 算法中，调度器提供最早截止时间任务，由t a s k n p e d f 接口提供。 i n t e r f a c et a s k n p e d f 第四章改进策略的研究与实现4 5 a s y n cc o m m a n de r r o r tp o s t t a s k ( u i n t s _ ti d ，u n i t 3 2 _ td e a d l i n e ) ； e v e n tv o i dr u n t a s k o ； ) 这个调度器命名为：s c h e d m e r n p e d f p ，并同时提供t a s k b a s i c 和协k n p e d f 二个接口。 m o d u l es c h e d u l e r n p e d f p p r o v i d e si n t e r f a c es c h e d u l e r ； p r o v i d e si n t e r f a c et a s k b a s i c u i n t s _ tt a s k a d ； p r o v i d e si n t e r f a c et a s k n p e d f u i n t s _ _ tt a s k i d