无线资源调度算法

无线资源调度算法（共7篇）

无线资源调度算法 篇1

0 引言

无线HART是第一个开放式的工业无线通信标准,用于满足过程工业应用中可靠、稳定和安全的无线通信的关键需求。 无线HART是一个集中管理的MESH网络,它建立在IEEE 802.15.4 物理层标准上,附加了自有的数据链路层、网络层和应用层协议,在MAC层采用带有跳频的TDMA调度方法,保证系统的可靠性[1]。

无线HART网络在数据链路层采用TDMA机制, 无线HART网络中的通信资源调度成为影响网络通信性能的重要因素。

1 无线HART资源调度策略研究现状

无线HART成为工业标准后, 一些学者提出了一些基于无线HART网络的调度方法。 SAIFULLAH A提出的实时调度算法支持实时反馈闭环控制,但是只完成了仿真工作,并没有实际的应用报告[2];FANG M等提出了一种基于分层思想的调度算法,但时隙的分配中没有考虑节点的数据更新速率[3];ZHANG H等提出了基于时隙数和信道数最优的资源调度算法,但该算法仅仅是针对于线性网络和树状网络[4,5]; 董利达等提出了基于双树结构资源调度策略, 给出了资源添加和删除算法, 但该算法只适合双树结构和层数固定的网络拓扑[6]; 张盛等提出了无线HART网络中的高可靠资源分配策略, 基于资源分配的次序, 降低传输延时, 但该算法没有考虑节点数据传输速率的多变性以及资源类型的差异[7]。 上述算法都没有考虑节点更新速率的不同,同时在时隙的选择中, 采用连续顺序选择的方法( 即第一条路径选择时隙1, 第2 条路径选择时隙2), 通信易受突发干扰的影响。 本文依据现有的研究状况,针对无线HART超帧资源的不同类型和节点数据传输速率不同,提出资源分配算法。 对无线HART网络中同一节点的下一跳路径( 无线HART图路由要求每一个节点都至少有两条下一跳路径) 在超帧中均匀分配时隙, 增强对干扰信号的抗干扰能力。

2 无线HART通信资源和超帧

无线HART网络的通信资源包括以下几种类型: 加入(JOIN)、 广告(ADVERTISE)、 发现(DISCOVERY)、 广播( BROADCAST ) 和通用( NORMAL ) 。 加入和广告包用于节点加入; 发现型资源用于搜索新邻居和保持与时间源设备之间的联系; 广播资源用于广播信息; 通用型资源则用于一般的数据传递。

在无线HART网络中, 通信资源的调度是以超帧为单位, 超帧是一个由若干时隙组成的循环周期。 无线HART规范支持多信道调度即支持16 个信道, 大大提高了通信带宽的利用率。

无线HART的超帧可分为管理超帧和数据超帧, 管理超帧主要负责加入、 广告、 发现和广播类型资源及通用类型中的下行资源,数据超帧负责上行资源。 数据超帧长度由节点通信速率决定, 支持更新速率为2ns,其中n为正整数或负整数, 文中支持的最快更新数率为4 s , 最慢更新数率为16 s ( 慢于16 s按照16 s更新) 。 论文使用一个数据超帧(长度为1 600 个时隙) 和两个管理超帧,一个长度为200 个时隙(加入和广告类型资源),另一个为400 个时隙(广播和下行的通用类型资源)。

3 调度算法及实现

3 . 1 资源调度算法中的冲突

无线HART网络中对时隙和信道的分配存在着两种类型的冲突:显式冲突和隐式冲突。 若一个节点同时存在一个发送链接和一个接收链接, 则属于显式冲突,可以给两种链接分配不同的时隙;而相邻链接之间的干扰属于隐式冲突, 分配同一个时隙不同信道, 如图1 中节点2→1 和9→6 所示, 如果2 和9 同时发送数据,2和6 互为邻居,则2 会对6 造成干扰。 在实际的资源调度算法中, 根据不同的资源类型, 对冲突的解决作了不同的定义。 若通用资源和广播类型资源的起点和终点都不同,则使用同一个时隙不同信道,否则分配不同时隙。若加入资源接收地址不同, 广告类型资源发送地址不同,则使用同一个时隙不同信道,否则分配不同时隙。

3 . 2 资源调度算法软件实现

无线HART的管理超帧( 两种) 和数据超帧的长度不同, 无线HART的资源在这三种超帧上分配, 但是这三种超帧都是在同一时间上运行,因此在资源分配时还要考虑以下两个问题:(1) 在同一个时隙上, 每种超帧既不能与同超帧类型资源冲突, 也不能与其他超帧冲突;( 2 ) 由于三种超帧的更新时间不同, 更新速率快的超帧在处理与更新速率慢的超帧的冲突时,不仅考虑相同时隙的冲突, 还要考虑相应倍数时隙的资源冲突, 如加入资源超帧长度为200 个, 在相对时隙数为10 的位置处考虑与数据超帧的冲突时, 既要考虑时隙数为10 处的资源,还要考虑相对时隙数为210、410、610 等处是否有资源冲突(数据超帧)。 为解决以上问题,文中对于通信资源分配,统一在最长的超帧(数据超帧)上对各种类型的资源分配,之后再分配到对应的超帧中。 下面详述资源调度算法的实现过程。

无线HART资源调度算法的软件实现主要由超帧初始化、节点信息获取、路由算法实现、管理超帧资源调度算法实现和数据超帧资源调度算法实现等部分组成,下面对各部分作详细说明。

( 1 ) 超帧初始化

实现对管理超帧和数据超帧的数据结构初始化, 数据超帧的长度为1 600,管理超帧1 长度为200 个( 加入和广告类型),管理超帧2 长度为400 个(广播和下行数据类型), 在初始化中, 还分配了网络接入点的加入、 广告、发现和广播类型资源。

( 2 ) 节点信息获取

获取节点信息和邻居信息。

(3)路由算法实现

根据节点信息,实现整个网络的图路由和源路由算法,本文采用了文献[8]的算法。

( 4 ) 管理超帧资源调度算法实现

管理超帧资源分配算法过程如下:

①输入资源类型和超帧长度length, 加入和广告类型length=200 ,广播和下行数据类型length=400;

② 下行数据类型资源, 根据源路由得到相应的路径, 对每条路径调用资源搜索子算法, 其他类型资源直接调用资源搜索子算法。

③调用资源分配子算法,设i=1,no=0,△=1。

资源搜索子算法实现步骤如下:

步骤a: 对需要分配资源的节点, 在数据超帧的第i个时隙的16 个信道做资源冲突检测(各类资源冲突检测规则详见3.1 节),如果有冲突,转到步骤d,否则执行步骤b;

步骤b:j=i+length×k(k=1~(1 600/length-1)) , 分别对应不同的j值,在数据超帧的第j个时隙的16 个信道做资源冲突检测,如果有冲突,转到步骤d,否则执行步骤c;

步骤c:在数据超帧的第i个时隙, 检测是否有空闲信道, 有则该节点在i时隙空闲信道分配相应类型资源,在数据超帧第i和j个时隙和相应管理超理超帧(如果是管理超帧分配)第i个时隙中记录发送地址,接收地址和资源类型,退出,资源分配成功,否则转到步骤d;

步骤d:no=no+1;i=i+△,如果no≥length,资源分配失败,退出,否则转到步骤a。

( 5 ) 数据超帧资源调度算法实现

数据超帧分配上行图路由数据, 对于图路由, 源节点及每个中间节点都有两条到下一跳节点的路径,为了增强系统的抗干扰性,文中对于一个节点的两条上行路径,其资源分配的时隙间隔尽量大。 数据超帧资源调度算法实现过程如下:

①根据图路由,计算从源节点到目的节点的经过节点和路径(这部分算法不属于本文范围之内);

②对所有路径和节点分配资源;

③i=1,no=0,△=1,length=T×100(T为数据更新时间,单位s),调用资源搜索子算法,得到第一条路径资源;

④ i = ( L + length /2 ) % length ( L为第一条路径的时隙值),no=0,△=(-1)×no,调用调用资源搜索子算法, 得到第二条路径资源。

3 . 3 算法实例验证

选取图1 所示的无线HART网络, 节点1 为网络接入点,2~11 为现场设备, 数据更新速率为16 s, 应用资源调度算法, 得到整个网络资源分配表, 文中只选取了前20 个时隙的资源分配表, 见表1 和表2, 其中时隙0为全网发现时隙,d表示下行,u表示上行,a表示广告,j表示加入, b表示广播, * 表示多节点。

4 实验分析

4 . 1 建立实验环境

为验证资源调度算法, 搭建无线HART网络实验平台,包括网络管理器、接入点和现场设备。 网络管理者在计算机上Linux环境下完成,AP和现场设备使用飞思卡尔的MC13224 无线模块。

4 . 2 实验结果

( 1 ) 在无干扰情况下, 分别使用5 、 10 、 15 、 20 和25 个现场设备,使用4 s的更新速率和可变速率(从4 s~16 s),应用文中算法, 节点向网关传送数据, 实测端到端的单向数据传送成功率,端对端不设重传,结果如图2 所示,说明在变速率节点数据上传的情况下,算法保证了数据的稳定上传。

( 2 ) 在加干扰情况下, 分别使用5 、 10 、 15 、 20 和25 个现场设备,在时隙分配中一种选择同一节点的上行两条路径的时隙间隔尽量大( 方案1), 另一种顺序选择时隙( 方案2 ) , 数据更新速率都为固定的16 s , 从节点向网关传送数据, 加入干扰信号, 然后实测端到端的单向数据传送成功率, 端对端不设重传, 得到如图3 所示的结果。 从结果可以看出,方案1 的成功率要高于方案2,说明文中使用的算法提高了节点上传数据的抗扰性。

5 结论

目前无线HART网络的资源调度算法研究主要应用于节点更新速率固定的场合,本文提出了一种针对于节点变速率上传数据的资源分配算法,对无线HART网络中同一节点的下一跳路径在超帧中均匀分配时隙,增强对干扰信号的抗干扰能力。 实验结果表明,算法实现了无线HART网络变速率节点的资源分配,并提高了节点数据传输的抗扰性。

参考文献

[1]李继平,凌志浩.无线HART技术及其应用[J].世界仪表与自动化,2008,12(3):63-65.

[2]SAIFULLAH A.Real-time scheduling for Wireless HART networks[C].Real-Time Systems Symposium(RTSS),2010:150-159.

[3]FANG M,LI D,QUAN J.An innovative routing and resource optimization strategy for wireless HART[C].2012 International Conference Technology and Management.Germany:Springer Verlag,2012:353-360.

[4]ZHANG H,SOLDATI P,JOHANSSON M.Operational link scheduling and channel assignment for convergecast in linear Wireless HART networks[C].Proceedings of the Conference on Modeling and Optimization in Mobile,Ad Hoc,and Wireless Net works,Seoul,June 23-27,2009:1-8.

[5]ZHANG H,SOLDATI P,JOHANSSON M.Time and channelefficient link scheduling convergecast in wireless HART networks[C].2011 IEEE 13th International Conference on Communication Technology.United states Institute of Electrical and Electronics Engineers Inc,2011:99-103.

[6]董利达,黄聪,管林波.基于双树结构的无线HART调度策略[J].浙江大学学报,2014,48(3):391-397.

[7]张盛,张国勇,鄢傲.无线HART网络中的高可靠资源分配策略[J].小型微型计算机系统,2014,35(12):2593-2597.

[8]封岸松,王宏.基于通信链路质量的无线HART图路由算法实现[J].电子技术应用,2015,41(4):119-124.

一种改进的无线分组快速调度算法 篇2

常用调度算法性能分析

吞吐量和公平性永远是在无线资源分组调度算法的研究中不可回避的两个重要因素。如何平衡这两个重要因素就是分组调度算法要解决的核心问题。当多个业务分组请求服务时, 必须综合考虑各种因素, 确定合理的优先级次序, 安排用户的服务顺序和服务时间, 以满足各种无线应用的优质性能。下面分析一下三种常用的分组调度算法:PF算法、APF算法和M-LWDF算法。

1 PF算法

PF算法就是正比公平算法, 该算法的基本思想是在长时间的通信过程中, 维护各用户之间吞吐量的基本公平, 同时又考虑到每个用户自身通信环境的变化情况, 以此来确定每个用户的优先级。

该算法的用户优先级定义如下:

式中 (C/I) i (t) 指用户i在t时刻的载干比, 而λi (t) 指该用户i的平均吞吐量。当用户i连续通信时, 其λi (t) 必然不断增大, 从而使该用户的优先级变小, 将信道让给其他用户。该算法是一种公平调度算法, 但其主要缺陷是对实时通信业务的适应能力较弱[3,4]。

2 APF算法

APF算法就是自适应比例公平算法, 该算法的基本思想是:为了弥补PF算法在用户信道快速变化时, 造成的公平性缺失, 在原有PF算法基础上, 增加了更新控制模块。该模块随时追踪用户信道变化情况, 不断更新相应控制参数。

该算法的用户优先级定义如下:

式中, Ri (t) 是用户i在t时刻的瞬时速率, 而λi (t) 是该用户的平均吞吐量, Ci是用户i的控制参数。该算法由于增加了一个控制模块, 虽然弥补了PF算法在公平性的上的不足, 但控制参数的更新需要较长的周期, 这就使得系统的整体吞吐量有所降低[4]。

3 M-LWDF算法:

与上述两种算法不同, M-LWDF算法是针对需要高速率支持的无线实时业务而提出的[3,4]。该该算法的基本思想是将分组数据包的时延和如何有效利用信道信息平衡考虑, 其用户优先级的计算不仅和用户当前的信道质量有关, 还和包的队列时延有关。

该算法的用户优先级定义公式如下:

式中δ是用户i的Qo S参数, Ri (n) 是用户i在第n个TTI内的最大数据速率, 而λi是该用户i的平均吞吐量, Di (n) 是用户i所在分组的队列延时, Ti是用户i能容忍的最大时延。该算法在用户吞吐量和用户等待时延之间做了有效的折衷, 即对信道条件好的用户尽可能的提高信道利用率, 又考虑到信道条件差的用户的等待时延, 随着等待时间的加长, 其调度优先级也随之增加。但是对于某些信道条件较差的用户, 其等待时延可能超过用户的最大容忍时间而被丢弃。

改进的调度算法

为了降低被抛弃的概率, 提高用户间公平性, 需要快速提高等待时间较长的数据分组的优先级, 使得信道条件较差的用户拥有被调度的机会。这时上面公式修正为:

式中, 我们将Tmin称之为快速调度时限, 将eMi称之为快速调度因子。快速调度因子的变化规律为, 随着等待时间Di (n) 的不断加长而先快后慢的变化。当用户i所在包的队列延时Di (n) ﹤Tmin时, 取对应的Mi=0, 则e Mi的值将等于1, 那么这时用户i的调度有限级将退化为, 在 (0, Tmin) 时间段内, 通信条件好的用户将得到更多的信道资源, 在一定程度上, 保证了系统原有的吞吐量。当用户i所在包的队列延时Di (n) ≧Tmin时, 则对应的, 当用户i所在包的队列延时Di (n逐渐接近用户i所能容忍的最大时延Ti时, 其对应的的值也就趋向于∞, 那么快速调度因子eMi的数值迅速增大, 使得用户i在第n个TTI的优先级也随之迅速增大, 从而迅速获得信道资源, 避免了信道条件较差的用户长期得不到调度的情况, 保证了系统中拥有良好的公平性。从长时间的通信来看, 信道质量好的用户占用信道的总时间会较长, 在很大程度上保证了整个系统的吞吐量, 信道质量差的用户占用信道的总时间会较短。由于该改进算法照顾到信道条件差的用户占用信道的机会, 必然会在一定程度上降低信道条件好的用户对信道资源的利用率。

4 结论

无线信道的时变特性是HSDPA系统的一个重要特性, 只有充分的考虑到系统的时变特性, 充分利用信道的时变信息, 在保证系统吞吐量的同时, 顾及到用户公平性, 才能获得了理想的整体性能。文中先对几种经典算法的性能进行了分析, 并结合HSDPA系统的特性, 对M-LWDF算法做了改进, 引入了快速调度因子, 在保证系统吞吐量的条件下, 迅速分配信道给信道条件差的用户, 防止这些用户在系统中被丢弃务, 从而提高了系统的公平性。

总之, 随着无线应用日益增多, 如何利用最有效的分组调度算法, 实现HDSPA的高性能, 仍有待于进一步研究。

参考文献

[1]孙华, 甄颖.一种增强WCDMA网络性能的技术:HSDPA[J].电信快报, 2004, 3.

[2]ANDREWS M, KUMARAN K.CDMA DATA QoS Scheduling on the Forward Link with Variable Channel Conditions[R].Bell Labs Tech-nical Memo No.10009626000404-05TM, 2000:1-45

[3]SHAKKOTTAI S, STOLYAR A L.Scheduling Algorithms for a Mixture of Real-time and Non-real-time Data in HDR[R].Proc.of17th International Teletraffic Confgress, (ITC-17) , 2001:173-804.

无线资源调度算法 篇3

目前,全球移动数据业务的迅猛发展、对上行链路的数据速率和时延性能都有较高要求的业务应用的不断增加以及HSDPA技术的广泛应用都极大地推动了对HSUPA技术的需求,成为HSUPA技术商用的主要驱动力。虽然目前在TD-SCDMA网络中,需求较大的仍然是以下行为主的业务,HSUPA的具体引入时间点依赖于网络对以上行为主业务的需求,但随着未来网络业务媒体化、多样化的发展,以及对上行业务需求的日趋明显,HSUPA技术必将逐渐引入到网络中,研究TD-SCDMA系统中的HSUPA技术意义重大[1]。

在TD-HSUPA系统中,无线资源管理功能主要由分组调度算法来实现,分组调度算法将成为影响系统性能及保证用户服务质量的关键所在。研究先进的分组调度算法是提高数据业务吞吐量、保证用户间公平性、满足业务QoS的根本。合适的调度可让用户更公平地共享链路带宽,增强用户感知度,还可使网络承载更高的数据服务容量,增强网络建设的有效性。因此,在TD-HSUPA网络平台下,结合TD-HSUPA系统及所承载的多样化业务类型的特点,寻找一种合适的的调度算法很有必要。

2 TD-HSUPA系统的Node B快速调度

TD-HSUPA是TD-SCDMA系统R7版本中引入的增强技术,它可以为上行提供2.2 Mbit/s的峰值速率,这主要得益于TD-HSUPA系统在物理层引入了大量关键技术,如自适应编码调制(AMC)、混合自动重传请求(HARQ)及Node B快速调度等。本文重点介绍的就是Node B快速调度算法。

在TD-HSUPA系统中,基于Node B快速调度的方法是:由Node B代替RNC直接控制UE的传输速率和传输时间。在每个TTI中,UE通过上传调度信息向Node B汇报当前UE缓存中的待发数据量以及可用功率。这样,Node B和UE之间直接进行信令传输,且在TD-HSUPA中还支持5 ms的TTI,这样,这种基于Node B的快速调度大大缩短了调度控制信令和UE的响应时延,从而可以更加精确、快速地控制小区负载,从而获得更大的上行吞吐量,充分利用有限的带宽资源[2]。

UE请求下行调度资源时,Node B快速调度方法使用调度许可来指示UE被允许使用的最大资源。当确定调度许可时,Node B可以使用服务RNC提供的和UE发出的调度请求中的QoS相关信息。

在TD-HSUPA系统中,UE为了请求Node B上行调度资源,UE需要通过E-RUCCH信道传输上行资源请求,其中携带调度信息(SI),其中包括E-RNTI信息。如果UE被许可在E-DCH上发送数据,SI信息可以在MAC-e头中携带。UE为调度提供的内容包括Buffer信息和物理层信息[3]。

基于Node B的快速调度中,Node B在RNC设定E-TFC子集,通过发送L1信令,快速控制UE可选用的E-TFC集合大小,从而实现快速调整UE发送速率。图1给出了调度环境,该图显示分组调度与MAC-e相连。每个HSUPA UE在Node B中有自己的MAC-e实体。MAC-e最重要的功能是HARQ过程中的接收和确认部分。

3 无QoS保证调度算法

调度算法是在动态复杂的无线环境下使多用户更有效地使用无线资源,提高整个小区的吞吐率,与此同时,还要兼顾各个用户等级和公平性。下面介绍了TD-HSUPA中几种比较常用的无QoS保证的调度算法。

3.1 轮循(RR)调度算法

RR调度算法是一种最简单的调度算法,其特点是保证小区内的用户按照某种固定的轮询方式来循环占用有限的无线资源,从而实现数据传输。轮询的方式可分为基于时间的轮循方式和基于流量的轮循方式。基于时间的轮循中,每个用户被依次分配相同的时间,由于不同用户所处环境不同,得到的流量可能并不一致;基于流量的轮循中,每个用户被依次得到相同的流量服务,而不管用户实际信道条件的好坏。

RR算法较简单,并能绝对保证用户的公平性,但没有考虑用户实际无线信道间的差异,因此吞吐量很低。

3.2 最大载干比(Max C/I)调度算法

Max C/I调度算法的特点是追求最大的系统容量和最高的资源利用率,而不考虑用户间的公平性。它在任意时刻总是载干比最高的UE服务。

调度器在优先传输HARQ重传分组后,按照每个用户当前的C/I大小,选择最大C/I用户数据进行服务,用户载干比信息由用户设备测量后通过上行链路报告给Node B,或者Node B根据功率控制信息估计得到[4]。

当系统采用自适应调制编码技术时,采用最大载干比算法的无线系统可获得最大吞吐量,并且最大载干比算法实现简单,算法复杂度低。

但最大载干比算法完全没有考虑到不同用户的公平性要求,这种调度算法会使一些信道条件较差的用户长时间得不到服务。算法复杂度相比RR算法要高,因为需要对用户C/I值进行比较。通常认为最大载干比算法是最不公平的,并且把采用该算法得到的系统吞吐量看作系统吞吐量的上限。

在TD-HSUPA系统中,由于反馈的是0~30的离散整数信道质量指示(CQI)值,代表信道质量,因此调度算法中用CQI值代替载干比,称之为MAX CQI。调度优先级为

式中:i=1,2,…,N;CQIi(t)表示基站最近接收到用户i反馈的CQI值。

3.3 等比公平(PF)算法

PF算法中,每个用户根据信道状况、业务量大小以及服务状况等分配一个优先级,任意时刻小区中优先级最大的用户接受服务。优先级的计算为

式中:k=1,2,…,N;(C/I)k(t)为第k个用户在t时刻的载干比;Tk(t)为该用户在以t为结尾的时间窗口中的吞吐量。

在该调度算法中,每个TTI时间内,计算队列中的每个用户的相对瞬时信道质量,只有当用户具有最好的相对瞬时信道质量时才能得到服务。其中相对瞬时信道质量定义为瞬时信道质量与平均吞吐量的比值。这样,瞬时信道条件较好或者过去得到的吞吐量很低的用户的优先级将会提高。

综上所述,以上分析的3种算法都不具备时延约束条件,不能保证业务的传输时延要求,下面将分析具有时延约束的保证多业务QoS的调度算法。

4 保证多业务QoS的调度算法

4.1 M-LWDF调度算法

M-LWDF算法的优先级表示为

可以看出,该调度算法与前面所提到的3种无调度算法有明显的区别,那就是在优先级表达式中加入了时延相关的约束因子ai,通过ai来提高时延敏感业务的调度优先级;该表达式中的wi是队头时延;rij(n)表示用户在第j个信道上的传输速率,体现了用户的信道状况;Ri(n)表示用户i在第n个TTI内的平均吞吐量,在表达式中处于分母位置,这样可以提高公平性,照顾那些吞吐量低的用户,以防止出现“饿死现象”[5]。

该调度算法考虑了用户信道的状况和用户排队等待队列的时延情况,能够满足对时延要求高的用户需求。但是对于每一种业务种类,这种算法很难找到针对每种业务的理想解决方案,并且在系统负载较大时,这种算法的时延特性会有所下降。

4.2 EXP调度算法

EXP算法的优先级表达式为

式中:变量的定义均与M-LWDF算法中的相同,其中,是所有用户平均的加权包头延时,随着时间而变化,因而EXP调度对时延的敏感程度也是时变的,并且调度优先级与时延的关系呈指数关系。

该调度算法考虑了用户实际信道状况的好坏及不同实时业务的QoS要求,能够满足对时延敏感业务的需求。但该算法中指数运算的算法复杂度较高。

5 基于效用函数的调度算法

5.1 效用函数思想

在无线网络中,效用可以被解释为衡量用户对服务的满意程度。效用函数的基本思想是将系统资源和性能指标作为相应的效用函数的参数,不同的用户可以使用不同的效用函数,系统调度目的是在一定条件下取得最大的效用值[6]。效用函数的特点是,当系统提供的某一参数低于某一值时,效用值几乎为零;而当某一参数高于某一值时,则效用值为最大值1,此时再增加该参数,效用值也不会再增加。

5.2 基于效用函数的调度算法

不同的业务可以使用基于不同性能指标的效用函数,从而使效用函数具有不同的效用值曲线。非实时类业务效用函数的性能指标可以选取“吞吐量”,而时延敏感业务的效用函数可以选取“时延”作为性能指标。设计效用函数表达式的方法有两种:一种是对各种业务做全面的主观满意度调查,从而得出一个总体的效用函数表达式;另一种则是基于业务特性和公平性等因素设计出较合理的效用函数表达式。但是无论用哪种方法,都需要能够反映相应业务的Qo S要求[7]。

如图2所示,话音、数据和多媒体业务的效用函数的形式是不同的。对于话音业务,它必须达到一个固定的QoS指标,才能成功通信;而数据业务则将吞吐量作为性能指标,吞吐量越高用户的效用值也就越高,它的变化趋势可以用一个单调增的凸函数来表示;多媒体业务介于两者之间,可以采用S-型函数(如Sigmoid型函数)来表示。

在实际调度过程中,可根据不同的业务类型,来指定不同性能指标的效用函数,通过基于不同的主要性能指标进行资源分配。在基于效用函数的调度方法中,可分别用一条曲线来表示用户的效用值,该曲线可表示效用函数基于功率、速率、时延等性能指标的效用值[8]。

6 小结

文中讲述的几种无QoS保证的调度算法,算法结构简单,容易实现,但不能保证业务的实时性;保证多业务QoS的M-LWDF调度算法考虑了业务实际的信道状况好坏和排队时延情况,能够满足业务对时延的要求,但在系统负载较大时,这种算法的时延特性会有所下降;EXP调度算法同样考虑了信道状况的好坏及不同业务的QoS要求,能够满足时延敏感业务的需求,但该算法中指数算法的复杂度比较高。

因此,最后引入了基于效用函数的调度算法,将业务的时延、吞吐量等客观属性映射为代表用户满意度的效用值,结合相应业务的QoS要求,设计出合理的效用函数,并将其作为评估用户满意度的依据。这样得出的调度效果更加真实地反应了用户的满意情况,并可作为调度算法改进的依据。基于效用函数思想的调度算法将能大大提高TD-HSUPA系统的调度效果,从而使网络能够承载更高的数据服务容量,提高网络建设的有效性。

参考文献

[1]程军,李鸥,来卫国,等.无线网络信道队列状态感知资源调度算法[J].计算机科学,2009(4):47-49.

[2]常永宇,杨大成.TD-HSPA移动通信技术[M].北京:人民邮电出版社,2008.

[3]郑培超,贾韶军,宋瀚涛,等.LTE系统上行保证服务质量的分组调度算法[J].电子科技大学学报,2009(3):186-189.

[4]范晨,张琳,廉文娟.一种在混合业务中保证流业务QoS的调度算法[J].北京邮电大学学报,2007(6):75-78.

[5]翁英萍,季中恒,彭建华.基于时延的分级多业务调度算法研究[J].计算机工程与设计,2009(6):1311-1315.

[6]牛志升,王兰,段翔.多媒体DS-CDMA系统中基于效用函数的无线资源优化策略[J].电子学报,2004(10):1594-1599.

[7]GUO K,SUN L,JIA S,et al.Dynamic data scheduling and re-source management using max-utility estimation in next generation wireless networks[C]//Proc.First International Conference on Inno-vative Computing,Information and Control.Washington:IEEE Press,2006:433-436.

无线资源调度算法 篇4

关键词：无线传感器网络,节点调度,二进制量子粒子群优化

在无线传感器网络中传感器节点具有不同的感知、信息处理和通信能力,对目标跟踪来说,通过节点调度可以选择出提供最优信息的传感器节点,对目标的位置进行估测,从而完成目标跟踪。由于被监测对象动态变化,且节点受通信能力限制,因此,如何对节点进行合理地调度,使目标与节点之间建立一种关系,满足网络性能与跟踪性能关系的均衡是非常重要的。

1相关工作

对多目标跟踪来说,跟踪精度是衡量WSN节点任务调度是否优劣的首要标准。文献[1]中当传感器分配给目标时,被跟踪目标的信息增量可以用量测前后误差协方差阵的变化来计算求出传感器与目标配对的信息增量。选取最大信息增量所对应的传感器对相应的目标进行一次探测,从而提高目标的准确度。Zoghi,M.R.[2]等综合考虑跟踪准确度和网络能耗提出改进迭代节点选择算法,使用节点到目标之间的欧氏距离来衡量跟踪误差,通过目标跟踪准确度和网络能耗构造性能函数进行节点优化选择。刘美[3]为解决WSN多目标跟踪节点任务分配的竞争冲突问题,建立节点任务分配跟踪精度和能量消耗的综合性能指标,提出一种融合了模糊聚类的多弹性子模自组织神经网络节点任务分配方法实现多目标的精确跟踪。之前作者在文献[4]中重点考虑了通信能耗和定位精度,通过建立任务分配的综合性能指标,利用基于最近邻进行初始化的离散粒子群优化算法,实现有效的任务分配。但若各节点只关注自身行为的优化如各节点以最短路径传输数据而不考虑整体能耗,会导致无法满足能耗约束,另外,节点可能会处于忙碌状态无法接收新任务,因此需要与节点协商任务,优化任务调度方案。

但已有的研究忽视了以下两点:(1)已有调度算法大多采用基于布尔监测模型,而实际应用中,传感器的监测能力是逐步削弱的。(2)已有调度算法没有针对目标周围分布的信标节点不均匀导致估计的节点位置产生较大误差做出改进。因此,本文主要通过建立目标概率监测模型,定义目标监控区域内节点n对目标g的监测概率p(n,g),利用近似三角形内点测试算法(approximate point-in-trian-gulation test,APIT)保证选择的传感器在目标周围均匀分布,有效地改进跟踪精度。并采用具有调整参数少,收敛能力强的二进制量子粒子群优化算法(BQPSO),使得节点调度更容易在整个可行解空间中进行探索寻找全局最优解。

2目标函数设计

2.1目标监测概率

假设WSN中,各节点具有相同的监测范围r和通信范围c。由于监测环境和噪声干扰,节点对目标的监测概率应呈一定特性的概率分布,即节点n(1≤n≤N)对目标监控区域内的任一目标点g的监测概率p(n,g)[5]定义为:

式(1)中,re(0<re<r)是节点监测可靠性参数。α1,α2,β1,β2是与节点有关的测量参数,dmn表示目标m与节点n之间的距离。λ1和λ2为输入参数,定义:λ1=re-r+dmn,λ2=re+r-dmn;通常节点的目标监测概率小于1,这意味着监测过程中需要多个节点同时监测目标,以提高目标监测概率,定义如下:

式(2)中,p(m)为监测目标m(1≤m≤M)所选节点集合的监测概率。设pth为节点监测概率阈值,则目标有效监测条件为min(p(m))≥pth。节点调度任务监测簇获得概率越高,达到的目标越优。

2.2跟踪精度分析

在WSN中,需要多个节点协作才能完成跟踪定位。假设目标M的通信半径内分布着n个坐标为(xi,yi)的节点,其中i=1,2,…,n为节点编号。由于跟踪定位主要根据目标与节点之间的距离信息来得到。设定目标由三个节点负责跟踪,若将n个节点划分为C3n个不同的组合,可根据组合形成内角大小判断组合形成情况。当节点共线或者几乎共线的时候,估计位置误差将会很大,则在节点选择时撤销该组合。设定共线度就是一组节点组成的三角形的内角的cos值的最大值。定义为NC=max{cos A,cos B,cos C}[6]。当NC值等于0.5时,代表节点组成的三角形是等边三角形,此时用这组节点来进行定位,效果最好;当NC值等于1.0时,代表节点组在一条直线上,此时定位效果最差。则为了避免共线度,撤销该组合。确保所选组合形成三角形。

在确定一个或多个三角形组合基础上,采用APIT算法确保目标被包含在被选择的三角形组合内,从而有效地提高算法精度。目标M通过APIT算法对各个三角形进行测试,判断自身是否在三角形内及在哪几个三角形内,若仅存在于一个三角形,则采用加权质心算法计算出此三角形的质心(xj,yj)。若存在于多个三角形,则根据能耗模型选择三角形保证能耗最低。再根据定位算法计算出目标位置。采用加权质心算法实现定位,如式(3)所示:

式(3)中wi表示为每个节点的权值。定义wi等于1/di。设目标真实位置坐标为(xG,yG),通过计算得到t时刻的目标位置为(xtj,ytj),则t时刻总的定位误差ER为:

2.3通信能耗模型

设定节点以密度λ的泊松分布过程分布在2b×2b的正方形空间内,且λ=λ0+λ1。簇头节点密度为λ1,其它节点密度为λ0;节点总个数为n,节点分布在正方形空间中用R表示,则n=λR。文献[7]给出了节点通信能耗模型。将一个l-bit的信息传送距离d,射频电路的发送耗能和接收耗能定义为:

式中:Eelec表示发射装置和接收电路发送或接收单位bit的耗能;εamp表示发射放大器将每bit传送单位平方米所耗的能量;k为传播衰减指数,在建筑物和植被茂密的区域进行远距离传输时,k=3～5。

而簇首需要消耗的能量[8,9]为:

式(4)中,N1为泊松分布随机变量,表示簇内节点个数,dmtoBS为簇首到基站BS的距离。每个簇内节点个数的均值E[N1|N=n]为

其中,λ0=(1-p)λ,λ1=pλ,p=k/n(跟踪簇个数为k)。

假设基站位于区域的中心,则簇首到基站距离的均值E[D1|N=n]为

其中,D1为泊松分布随机变量,表示在(x,y)处簇首到基站的距离,PR是在区域R内的簇首概率密度。代入式(4)得

若将信息处理能耗忽略不计,则簇首能耗主要取决于基站位置。而总能量E主要取决于通信距离,即通信能量消耗最小化可以等效为通信距离之和的最小化。

2.4任务分配函数设计

多目标跟踪过程中,在跟踪簇的覆盖区域发生重叠时,不同任务可能需要相同的节点资源,这时如何通过节点调度避免资源竞争冲突,完成节点与目标的配对是多目标跟踪的核心问题,而任务调度描述直接影响算法的复杂性,主要涉及如何描述参与任务的节点。设定一个节点只能加入一个簇实现对一个目标的跟踪。节点调度描述如式(5)。

式(5)中,在矩阵A中,行数表示目标数;列数表示节点数。amn为0-1变量,amn=1表示第n(n=1,2,…,N)个节点被分配去跟踪目标m(m=1,2,…,M),即第n个节点被分配加入第m个簇中,否则amn=0。

在节点调度中,能耗模型是一个包含多种因素的函数。主要指承担任务的所有跟踪簇节点的能耗之和,能耗模型可以描述为式(6)。

式(6)中,模型主要描述目标与簇内节点之间、簇内节点之间及簇首与基站之间的通信能耗和簇首处理能耗之和,确保簇首之间信息传输可靠性及簇内通信能耗的最小化。(其中,t表示采样次数)。

约束条件:

1)一个节点只能分配跟踪一个目标。这就可以解决跟踪多目标时多个簇对节点资源的竞争冲突问题。表示如式(7):

2)一个目标由三个节点组成的簇对它进行跟踪定位以保证定位精度。表示如式(8):

3)监测目标m的节点集合监测概率p(m)必须满足min(p(m))≥pth。

其中,n是目标数。则节点调度目标函数定义为式(9):

3基于二进制量子粒子群的任务调度算法

粒子群优化算法(PSO)是一种进化计算技术。为了使粒子能够更好地满足全局收敛,2004年Jun Sun等人运用量子理论,将量子进化算法引入到粒子群算法中提出了量子粒子群算法[10]。为了使量子粒子群算法适应实际中离散搜索空间的问题,在量子粒子群算法中引入了二进制编码的概念,采用二进制编码的量子行为粒子群(BQPSO)算法解决无线传感器网络节点任务调度问题。

在BQPSO算法中,设种群规模为M,在进化过程中粒子以一定概率取加或减,更新每个粒子的位置,并生成新的粒子群体,由公式(10)至(12)决定:

式(11)中pbesttid表示粒子i在第t次迭代时在搜索空间中到过的最优位置;gbesttid表示整个粒子群到第t代在搜索空间到过的最优点;M为粒子个数;a为收缩扩张系数,它控制着粒子的收敛速度,当a较大时,粒子以较大的步长搜索可行解空间,当a较小时,搜索步长相应减少。

对于节点调度问题这样的组合优化问题,本文对节点调度问题的编码转换成二进制编码,如式(4)所示,并要求满足约束条件。为降低定位误差,在初始化节点选择时,先选择最近的两个节点后,在可通信范围内,选择第三个节点。设定0.5<NC<1时,避免共线度。根据粒子的位置更新基于式(10)至(13)实现,同时以NC为位置更新约束条件。

粒子在资源分配组合的空间内搜寻最优位置。对应每个粒子的调度方案,都有一个用于衡量粒子优劣的适应度评价粒子优劣,本文直接将式(9)的目标函数用来衡量粒子的质量,通过以上分析,得到基于二进制量子粒子群算法的节点任务调度算法流程图如图1所示。

4 实验仿真

仿真过程中,在100 m×100 m监测区域内,模拟3个目标(T1,T2,T3)作匀速直线运动,目标运动函数分别为:

A:x=5.0t,y=(t-16.5)2+5;

B:x=5.0t-30,y=10t/3+5;

C:x=3.0t,y=-4.0t+120。

实验中将60个节点(S1,S2,…,S60)随机分布于监测区域内,并设定基站坐标为(5 0m,50 m),用BS标注。并保证目标在移动过程中,至少有三个节点可跟踪目标。实验中采用一组参数如下:节点的监测半径R=25 m,通信半径c=3r=75 m。能耗模型中k=4,测量可靠性参数re=0.5r=10 m。概率监测模型参数为α1=1,α2=0,β1 =1,β2=0.5,cth=0.9。采样间隔为1 s;粒子群参数w=1,c1=c2=2,最大迭代次数tmax=100;通过仿真结果如图2、图3所示。

图2为移动目标节点任务调度示意图,算法采用跟踪簇方式对目标进行任务调度完成跟踪。图3为基于BQPSO的节点调度示意图。基于BQPSO的节点调度算法将节点监测概率纳入考虑,采用基于APIT的加权质心算法进行定位跟踪,其中,以跟踪精度为节点选择优先考虑因素,确保目标位置竟可能位于选择节点所形成的三角形中,从而进一步提高了定位精度。并与文献[4]任务分配算法进行比较,算法采用三角形质心算法进行跟踪,并跟踪簇通信距离最短为节点选择准则完成节点调度。

图2和图3分别显示了监测区域目标运动轨迹、节点的分布及某一时刻(12s)节点选择情况。并根据两种考虑,分析了不同方法的能量消耗和定位误差,显示在图4和图5中。由图4所知,采用PSO算法完成所有目标节点选择所需能耗为8 328.3 m,而基于BQPSO的节点调度算法由于考虑目标与节点之间的位置问题,所需能耗有所增加,达到了9 783.2 m,与PSO算法相比增加了17.47%。但从图5所知,正是因为考虑了目标与节点的位置关系,所以,基于BQPSO的节点调度算法使得定位精度误差由原来1 439.8 m降到了1 092.1 m,整体降低了31.84%。同时,根据程序运行可知,基于BQPSO节点调度算法比基于PSO节点调度算法以更快速度达到了最优值。

5 结论

本文在多目标跟踪下,将BQPSO算法应用于WSN节点任务调度,确保目标与适当的节点之间建立一种确定关系,实现合理的节点调度,确保多目标跟踪的精确、可靠,同时尽可能减少能量消耗,延长无线传感器网络寿命。

参考文献

[1]刘先省,周林,杜晓玉.基于目标权重和信息增量的传感器管理方法.电子学报,2005;33(9):1683—1687

[2] Zoghi M R,Kahaei M H.Electr eng efficient sensor selection basedon spatial correlation in wireless sensor networks.Iran Univ.of Sci.&Technol.,CSICC 14th International CSI,2009:627—632

[3]刘美,黄道平.WSN中传感器节点的弹性神经网络任务分配方法.华南理工大学学报,2010;38(6):66—72

[4]徐小玲,刘美.面向多目标跟踪的无线传感器网络任务分配.计算机应用研究,2010;27(12):4755—4757

[5]王晟,王雪,毕道伟.无线传感器网络动态节点选择优化策略.计算机研究与发展,2008;45(1):188—195

[6]吴凌飞,孟庆虎,梁华为.一种基于共线度的无线传感器网络定位算法.传感技术学报,2009;22(5):722—723

[7]沈艳,郭兵,丁杰雄,等.无线传感器网络节能动态任务分配.四川大学学报,2008;40(4):143—147

[8]孙超,赵路路.无线传感器网络分簇拓扑的覆盖区域节点调度优化算法研究.传感技术学报,2010;23(1):116—121

[9]郝晓辰,房艳.一种无线传感器网络的簇数目优化方法.传感技术学报,2008;21(8):1433—1436

无线资源调度算法 篇5

无线传感器网络(WSNs)[1]是由随机分布的集成了传感器、数据处理单元和通信单元的微小节点通过自组织方式构成的,在战场、医疗、智能交通和环境监测等领域有着广泛的应用前景。传感器节点能量一般非常有限,且难以补充。因此,在保证数据准确性的前提下,减少节点能量消耗,延长整个网络的工作时间是无线传感器网络设计时需要考虑的重要因素之一[2]。如何构建高准确性、低功耗的无线传感器网络节点调度算法成为近年来国内外研究热点和难点。调度算法的目的在于合理调度节点休眠和唤醒,实现网络中节点分时协调工作,让休眠节点节约能量,延长网络的生存时间。

目前,国内外学者提出多种调度算法,其中节点随机休眠算法是最早的节点调度算法之一,其基本思想是每个节点以概率P睡眠,以1-P的概率保持工作状态。这方面的研究集中在节点睡眠概率和节点感知半径、网络区域大小的关系方面[3],此类算法运算简单,求解快速,但难以应对环境的动态变化。文献[4]提出了一种根据邻居节点覆盖范围决定节点是否休眠的调度算法,该算法利用节点物理拓扑关系建模达到降低能耗的目的,但难以保证数据的准确性。文献[5]提出了无线传感器网络节点自适应调度算法,在LEACH协议分簇方法的基础上,通过调整数据融合窗口来增加簇头节点的睡眠时间,有效地增加了网络生存时间。文献[6]使用空时相关模型来研究数据采集的准确性和短时的能量消耗情况,但无法保证长时间内的最优调度效果。 文献[7]利用传感器收集到信息的子模块性,提出一种贪婪调度算法,可以保证长时间内的能量消耗最少,虽然使无线传感器网络具有最大生存时间,但是无法保证数据采集的准确性。以上算法均无法同时满足数据准确性要求和网络最大生存时间要求。

无线传感器网络中,由于传感器误差、环境影响、传输线路冲突等问题,传感器节点获得的信息仅是对环境信息的部分观察。因此,无线传感器网络动态调度算法可以看作一个动态不确定环境下的决策问题。可分解部分可观察马尔可夫决策过程(FPOMDP)是针对Agent在部分可观察随机环境下进行决策的数学模型,它可以将实际传感器网络调度问题转化为数学模型求取最优策略。在构造模型的过程中,对传感器数据获取存在误差、数据传输受噪声影响、空时模型精度有限等不确定因素进行充分考虑,有效地保证调度算法的通用性和鲁棒性。

本文提出一种基于FPOMDP的无线传感器网络动态调度算法,使用观察函数和信念状态空间描述环境中的不确定因素,利用环境信息数据和传感器节点能量消耗的条件独立关系,构建状态转移模型,并将两者的加权值作为奖赏函数指标,利用值迭代策略求解算法考虑当前策略的长期影响,实现数据采集的准确性和网络生存时间的动态调节。

1 FPOMDP模型及求解算法

1.1 FPOMDP模型

部分可观察马尔可夫决策过程(POMDP)[8]是针对Agent在部分可观察随机环境下进行决策建立的数学模型,如图1所示。

POMDP可以用一个六元组<S,A,T,R,Z,O>表示:状态集S,表示Agent所有可能状态的集合;动作集A,表示Agent所有可执行动作的集合:状态转移函数T(s,a,s'),表示在状态s下执行动作a,状态变为s′的概率;奖赏值函数R(s,a),表示在状态s下执行动作a获得的奖赏;观察集Z,表示Agent所有可能观察的集合;观察函数O(s′,a,z),表示执行动作a变为状态s′得到观察z的概率。

在POMDP中,为保证模型的马尔可夫特性,引入信念状态空间B,表示Agent所处状态在真实状态集中的概率分布,b(s)表示Agent处于状态s的概率。

FPOMDP[9]针对多状态POMDP模型求解困难的问题,利用变量间的条件独立关系和动态贝叶斯理论基础,对状态集进行分解,通过分解后状态集对应的最优策略,降低算法计算维度,获得最优策略。

1.2 值迭代求解算法

FPOMDP算法求解目标即根据信念状态空间寻找策略π,使得奖赏值函数获取最大值,以值迭代求解算法应用最为广泛。t时刻的奖赏值函数可以通过信念状态空间分布,奖赏值函数,状态转移函数、观察函数以及t-1时刻的奖赏值求取,如式(1)所示。

$V{}_t^{*}(b)=\underset{a}{{\displaystyle \max }}[{\displaystyle \sum _{s\in S}b}(s)R(s,a)+\gamma {\displaystyle \sum _{z\in {\rm Z}}{\rm P}}(z|b,a)V{}_{t-1}^{*}(b)](1)$

迭代结束条件如式(2)所示。

$\parallel V{}_t(b^{\prime })-V{}_{t-1}(b)\parallel <\frac{\xi (1-\gamma )}{2\gamma }(2)$

迭代结束后,通过式(3)求解策略。

$\pi {}_V^{*}(b^{\prime })=\underset{a}{{\displaystyle \text{a}\text{r}\text{g}\text{m}\text{a}\text{x}}}[{\displaystyle \sum _{s\in S}b}(s)R(s,a)+\gamma {\displaystyle \sum _{z\in {\rm Z}}{\rm P}}(z|b,a)V{}_{t-1}^{*}(b)](3)$

其中,折扣因子γ∈(0,1]用来实现未来奖赏值在当前奖赏值上的映射,其目标为令期望值有界。

2 基于FPOMDP的动态调度算法

基于FPOMDP的动态调度算法核心思想利用传感器的空时相关性,只用部分传感器节点执行数据获取动作,其它节点保持休眠状态以节约能量,休眠节点的信息由基站BS,通过空时相关模型[10]求取,以增加整个网络的信息量和信息准确性。

基于FPOMDP的动态调度算法可以实现传感器网络获取信息准确性和传感器能量之间的平衡,在保证获取数据准确性的情况下有效地减少网络的能耗,延长网络的生存时间,算法包括三个步骤:

(1) 建立传感器节点间的空时相关模型。空时相关模型描述了节点与自身历史数据,以及与相邻节点之间的关系。BS可以利用该模型通过活跃节点上传数据求取休眠节点数据。

(2) 对传感器网络节点进行FPOMDP形式化描述,包括状态集、状态转移函数、动作集、观察集、观察函数和奖赏函数的定义和参数学习。

(3) 利用FPOMDP值迭代策略求解算法求取最优调度策略。

2.1 节点空时相关模型

在由基站(BS)和大量传感器节点组成的无线传感器网络中,由于单独一个传感器的感知范围和可靠性问题,为了更准确地获得某个区域的数据,往往在该区域布置一定密度的传感器,距离相近的传感器的感知范围可能会重叠,造成一定的数据冗余,即多传感器的感知数据存在空间相关性;同一传感器所感知的数据在一段时间内可能不会发生变化或变化不大,即时间相关性。

设BS共获取n个传感器位置的属性,用n维向量表示X=(X1,X2,…,Xn),可以使用一个n维正态分布N(μ,∑)表示相关模型,即:

$\begin{array}{l}p(X)=f(X{}_1,X{}_2,\cdots ,X{}_n)\\ =\frac{\exp \{-\frac{1}{2}(X-\mu ){}^{{\rm T}}\Sigma {}^{-1}(X-\mu )\}}{(2\pi ){}^{n/2}(\det \Sigma ){}^{1/2}}(4)\end{array}$

其中, μ为均值向量,∑为协方差矩阵,即:

$\mu =\left(\begin{array}{c}\mu {}_1\\ \mu {}_2\\ ⋮\\ \mu {}_n\end{array}\right){\displaystyle \sum =}\left(\begin{array}{ccc}\sigma {}_{11}& \cdots & \sigma {}_{1n}\\ ⋮& \ddots & ⋮\\ \sigma {}_{n1}& \cdots & \sigma {}_{nn}\end{array}\right)(5)$

2.2 FPOMDP动态调度算法

将每个传感器作为一个Agent,则无线传感器网络动态调度算法需要根据当前状态,求取一个最优调度策略,其本质是一个多Agent的最优决策问题,首要任务是建立FPOMDP的形式化描述模型。

(1) 状态集S包含Sinfo和Senergy,S=Sinfo×Senergy。其中,Sinfo表示客观环境的真实状态,是无线传感器网络监测的对象,如追踪系统中的被追踪物体的真实位置,温度监测系统中的环境温度等;Senergy表示传感器节点的剩余能量。设客观环境共有n个属性,则Sinfo=(S_I1,S_I2,…,S_In),其中S_In表示客观环境第n个属性的状态集。设每个属性取值为m个,则状态子空间Sinfo用一个mn维向量表示,如式(6)所示。

$S{}_{info}=(S\_{\rm I}{}_1,S\_{\rm I}{}_2,\cdots ,S\_{\rm I}{}_n)=\left(\begin{array}{l}s\_i{}_{11}\\ ⋮\\ s\_i{}_{1m}\end{array}\right)\times \cdots \times \left(\begin{array}{l}s\_i{}_{n1}\\ ⋮\\ s\_i{}_{nm}\end{array}\right)(6)$

设无线传感器网络共有n个传感器节点,s_ei表示第i个传感器节点的实际剩余能量,则Senergy为一个n维向量,如式(7)所示。

Senergy=(s_e1,s_e2,…,s_en) (7)

在给定传感器节点休眠调度策略下,被监测对象状态和传感器节点能量剩余值条件独立,因此在求解最优策略时,对S的两个子空间Sinfo和Senergy进行独立考虑。

(2) 动作集A为传感器节点可能采取的策略集合,即$A=\left(a{}_1,\cdots ,a{}_i,\cdots ,a{}_n\right)$。按照传感器节点休眠、唤醒两种动作,可定义an的取值为:

$a{}_i=\{\begin{array}{l}0\text{节}\text{点}\text{休}\text{眠}‚BS\text{从}\text{相}\text{关}\text{模}\text{型}\text{计}\text{算}\text{数}\text{据}\\ 1\text{节}\text{点}\text{唤}\text{醒}‚BS\text{从}\text{节}\text{点}\text{读}\text{取}\text{数}\text{据}\\ \end{array}(8)$

(3) 状态转移函数T表示无线传感器网络在当前状态执行当前动作转移到下一状态的概率。按照可分解的思想,对Sinfo和Senergy分别构建状态转移函数Tinfo和Tenergy。对于Tinfo,由于环境状态变化不受传感器节点唤醒/休眠影响,只与环境变化的客观规律相关,可得Tinfo:

Tinfo(s_i,a,s_i′)=P(s_i,s_i′) (9)

对于Tenergy,节点被唤醒则存在能量消耗,s_e′i相对s_ei减小的概率较大;反之节点休眠,不存在能量消耗,s_e′i相对s_ei不变的概率较大,对应的Tenergy定义如表1所示,其中δ为非负数,取值为传感器平均一次收发的能量消耗值,Tenergy取值为参考值,可根据实际模型进行调节。

(4) 奖赏函数R;节点调度算法的目标是实现数据准确性和网络生存时间的动态调节,因此,本算法采用数据准确性和节点能量两个指标的加权综合指作为模型的奖赏函数。

$R(s,a)=\alpha R{}_{info}+(1-\alpha )R{}_{energy}=\alpha {\displaystyle \sum _{i=1}^{n}r}\_i{}_i+(1-\alpha ){\displaystyle \sum _{i=1}^{n}r}\_e{}_i(10)$

式(10)中,α∈[0,1],通过调节α的取值,动态设定数据准确性和节点能量在策略选取中所占的权重。

状态子集Sinfo对应的奖赏函数Rinfo,取值与系统状态无关,BS从传感器节点直接读取信息数据,数据准确性较高,从空时相关模型计算数据,数据准确性较低。对应的,节点唤醒的奖赏值较高,节点休眠的奖赏值较低。状态子集Senergy对应的奖赏函数Renergy,奖赏与动作无关,与传感器节点的剩余能量成正比,剩余能量越高的状态,奖赏值越高,反之奖赏值越低。具体定义如式(11)和式(12)所示。

其中,η为奖赏调整参数,可以根据实际应用的不同对Renergy进行调节。

(5) 观察集Z包含Zinfo和Zenergy,其中Zinfo为无线传感器网络对被观察对象的描述包括传感器节点上传的读数,和BS根据相关模型求取的数据,其表述形式与Sinfo类似。Zenergy为传感器节点上报的剩余能量值,表述形式与Senergy类似,不再重复。

(6)观察函数O:传感器节点受周围环境影响,或者传输网络冲突等原因,造成BS不论是从节点实际获取,还是从空时相关模型求取的数据,与真实环境数据之间会存在一定的偏差,观察函数O即用来描述不同状态下,执行不同的策略得到对应观察的概率。对Sinfo和Senergy分别构建状态转移函数Oinfo和Oenergy。Oinfo实质上表示了无线传感器网络对被观察对象的描述相对于实际对象真实状态中偏差,需要通过实验获取或根据经验设定。对于Oenergy,当节点上传数据时,观察数据与实际节点能量剩余值更接近,反之,可能存在一定的偏差,即:节点唤醒时,状态值与观察值接近的概率较大,反之,节点休眠时,状态值与观察值接近的概率相对减小,得到Oenergy定义如表2所示, Oenergy取值为参考值,可根据实际模型进行调节。

2.3 算法流程

算法流程包括离线值迭代和在线策略求解两部分。离线值迭代主要通过迭代的方式求得贪婪值函数,算法如下。

算法1 离线值迭代算法

① 初始化Sinfo、Senergy、A、Tinfo、Tenergy、Rinfo、Renergy、Zinfo、Zenergy、Oinfo、Oenergy,根据Sinfo和Senergy定义binfo和benergy;

② 计算V${}_{info}^{*}$(binfo):

在线策略求解主要根据当前信念状态选择奖赏最高动作,根据此动作进行节点唤醒与休眠选择,算法如下。

算法2 在线策略求解算法

① 初始化binfo和benergy;

② 策略求解:

③ 执行π,得到观察z_i和z_e;

④ 更新binfo和benergy

$b^{\prime }{}_{info}(s\_i^{\prime })=\frac{{\rm O}(s\_i^{\prime },\pi ,z\_i){\displaystyle \sum _{s\_i\in s{}_{info}}{\rm T}}{}_{info}(s\_i,\pi ,s\_i^{\prime })b{}_{info}(s\_i)}{{\rm P}(z\_i|b{}_{info},\pi )}$

$b^{\prime }{}_{energy}(s\_e^{\prime })=\frac{{\rm O}(s\_e^{\prime },\pi ,z\_e){\displaystyle \sum _{s\_e\in s{}_{energy}}{\rm T}}{}_{energy}(s\_e,\pi ,s\_e^{\prime })b{}_{energy}(s\_e)}{{\rm P}(z\_e|b{}_{energy},\pi )}$

⑤ 返回步骤②。

3 仿真实验与结果分析

3.1 实验环境

使用MATLAB仿真实验平台,实验系统由BS和20个传感器节点组成,传感器节点感知信息为温度。实验环境为Windows XP,CPU 3.00GHz,内存2GB。

实验中将温度读数与节点能量进行离散化,温度离散化为[0,25]和(25,50]两个子集,分别用0和1表示,即Sinfo={0,1},初始信念分布binfo={0.5,0.5}。节点能量按照数据获取与传输所消耗的最少能量进行离散化。动作集A={a0,a1}={0,1}。折扣因子γ=0.95,相关模型使用正态分布N(20,6.25)表示。Tinfo设置如表3所示。

Renergy调节因子η=0.8。观察函数体现了系统的不确定性,表4设定了Zinfo子集下包括3种观察,其中第一种设定不确定性最低,每次都可以从传感器和相关模型得到较为准确的观察,第三种设定不确定性最高。

3.2 结果分析

将本文算法与随机调度算法(RSA)、传感器全开算法(AlwaysON)、文献[7]中的EEDC算法进行比较。每种算法在每一种观察下,模拟运行100次,对结果进行平均比较。从获取数据准确性和能量消耗两个指标进行比较。

图2表示了四种算法在表4的三种不同观察下的数据准确率比较。不管在任何观察下,AlwaysON算法准确率最高。RSA算法随环境不确定性变化较大,当环境不确定性较高时,RSA准确性较差。EEDC与本文算法在环境不确定性较高时,仍能保持较高的数据准确率,本文算法较EEDC准确性更高,而且环境不确定性越大,本文算法优势越明显。

图3表示四种算法在表2的三种不同观察下能量消耗情况。AlwaysON算法能量消耗最大,EEDC算法能量消耗次之,本文算法能量消耗最少,本文算法的平均能耗比EEDC低20%左右。图4表示本文算法在表4的三种不同观察下,随机进行50次实验的能量消耗比较。本文算法能耗与相关模型的准确性关系密切,相关模型越准确,本文算法的能耗越低。

4 结 语

通过对现有无线传感器网络调度算法的分析,提出一种基于FPOMDP模型的动态调度算法,通过引入相关模型增加了网络信息量,利用FPOMDP策略求解算法完成节点的动态调度。该算法可以在保证数据准确性的基础上,减少网络能量消耗,延长网络生存时间,通过实验,验证了所提出算法的有效性和优越性。

摘要：针对无线传感器网络节点能量有限、数据采集易受环境影响的问题,提出一种基于可分解部分可观察Markov决策过程FPOMDP(Factored Partially Observable Markov Decision Process)的节点休眠调度算法。通过节点空时相关模型求取休眠节点数据,利用网络数据准确性和节点能量间的条件独立关系,构造状态转移函数、观察函数和奖赏函数,采用值迭代求解算法求取最优策略,实现节点动态调度。仿真结果表明,该算法能够在保证数据准确性的前提下,有效降低节点能量消耗,延长网络生存时间。

关键词：无线传感器网络,可分解部分可观察Markov决策过程,空时相关模型

参考文献

[1]Holger Karl,Andreas Willig.Protocols and Architectures for Wireless Sensor Networks[M],丘天爽,等译,北京:电子工业出版社,2007.

[2]王淑华,陈国定,赵国炳.一种无线传感器网络能耗模型及有效性分析[J].计算机应用与软件,2011,28(2):215-217.

[3]Dam T,Langendoen K.An adaptive Energy-efficient MAC Protocol for Wireless Sensor Networks[C]//First International Conference on Em-bedded Networked Sensor Systems,2003:171-180.

[4]Akyildiz I F,Su W,Sankarasubramaniam Y,et al.Wireless Sensor Networks:A Survey[J].Computer Networks,2002,38(4):393-422.

[5]刘嵩,仲崇权,藤弘飞,等.睡眠调度算法NASS的研究与实现[J].传感技术学报,2008,21(10):1755-1759.

[6]Liu C,Wu K,Pei J.An Energy-Efficient Data Collection Framework for Wireless Sensor Networks by Exploiting Spatiotemporal Correlation[J].IEEE Transactions on Parallel and Distributed Systems,2007:1010-1023.

[7]Meliou A,Krause A,Guestrin C.et al.Nonmyopic informative path planning in spatio-temporal models[C]//Proceedings of the22nd Conference on Artificial Intelligence,2007:602-607.

[8]Littman M L.A tutorial on Partially Observable Markov Decision Processes[J].Journal of Mathematical Psychology,2009,53(3):119-125.

[9]Williams J D,Poupart P,Young S.Factored Partially Observable Markov Decision Processes for Dialogue Management[C]//Proceedings of the4th IJCAI Workshop on Knowledge and Reasoning in Practical Dialog Systems,Edinburgh,Scotland,2005.

无线资源调度算法 篇6

随着网络技术的发展和应用,用户对网络的移动性和可靠性要求越来越高,基于IEEE 802.11系列标准的无线Mesh网络[1,2]近年来得到了快速、广泛的应用。随着网络应用的不断发展,特别是音频、视频等多媒体业务的广泛应用,这就要求无线网络不仅能支持传统的数据业务,还必须提供对带宽和延迟要求较高的音频视频业务的支持,同时还得保证各类业务间的业务区分。

无线Mesh网络为实现不同业务间的区分,IEEE802.11e在数据链路层提出了EDCA(增强分布式信道接入)机制。EDCA将不同的业务流分为4个不同的优先等级AC(Access Categories),每一个AC对应一个队列,通过设置仲裁帧间间隔(AIFS)、最小竞争窗口值CWmin、最大竞争窗口CWmax和传输机会(TXOP)4个参数设置不同的值实现不同业务流间的业务区分。很多研究[3,4,5]表明,由于无线网络状况的移动性和复杂性,EDCA算法中4个参数的静态设置并不能使无线网络的性能实现最优,特别在高负载或突发业务量较大的状况下,由于无线网络中有较高的冲突概率,EDCA的网络性能急剧下降,无法满足网络用户的要求。

而在有线网络环境下,由于网络环境的可靠性,一般在网络层通过采用不同的调度算法以实现各类业务的服务质量[6,7,8](Qo S)保证和各类业务间的业务区分。现有的调度算法包括:FIFO(first-in-first-out)、PQ(Priority Queuing)、FQ(Fair Queuing)和WRR(Weighted Round-Robin)。但由于无线Mesh网络本身的特性,这些算法用于无线Mesh网络中的分组调度时,由于无法根据网络流量及网络实际状态做出及时的调整,因而无法最大限度地利用无线Mesh网络的网络资源。

基于此,本文提出了一种用于无线Mesh网络中的自适应队列调度策略(AQSM)。该策略的基本思想是通过实时监控网络流量和无线链路的实际状态,动态地调整加权轮询WRR算法中的权值,以期达到变化的分组调度策略,最终实现充分的利用无线Mesh网络中的网络资源、提高网络性能及Qo S保证的目的。并通过仿真验证该策略对网络性能的提高及各类业务流间的业务区分。

1 WRR算法

在有线网络中为实现各类业务间的业务区分,一般采用WRR算法。WRR算法的基本思想是网络中的路由器给不同类型的业务流分配不用的子队列(在IP DiffS erv中共分为3大类子队列:BE(尽力而为:Best-Effort)、AF(确保转发:Assured-Forwarding)、EF(快速转发:Explicit-Forwarding),同时为每一个子队列分配一个对应的权值。在路由器调度数据时,按照轮询的方式调度,某一子队列包含的分组数大于或等于分配的权值,则该子队列调度对应权值个分组后进行下一队列的调度,若某一子队列包含的分组数小于分配的权值,则把队列中的分组全部调度完毕后进入下一子队列,如此轮询调度。对于WRR调度算法而言,如果每一个分组的大小一致则可以提供很好的公平性;但如果分组的大小有区别就会对较小分组的子队列造成不公平。

WRR算法的权值固定分配,在有线网络环境下能提供很好的网络性能和业务流间的业务区分。但在无线Mesh网络中,由于网络链路本身的不稳定性和数据到达的突发性,使得在某一时刻即使调度成功但无法正确传输数据(而按照MAC层的工作原理该数据将重传),造成网络资源的浪费。为充分利用无线Mesh网络的网络资源,同时保证各类业务的业务区分,在无线Mesh网络中采用动态的WRR调度算法是完全必要和可行的。

2 AQSM算法实现

基于权值固定分配的特性,WRR算法不能根据无线网络的链路状态和网络流量的实际情况,动态地调整各子队列的权值。AQSM算法就是希望通过无线Mesh网络的网络链路和网络流量的实际状态动态调整各对应子队列的权值IWi。其功能框图如图1所示。

图1 AQSM功能框图(参见右栏)

2.1 变量说明

Ratei:子队列i实际数据到达速率;

Raterefi:子队列i数据到达的参考速率,可由系统管理员自行设定。为实现各业务流间的业务区分一般建议高优先级的参考速率值较小,即Rateref[高]

RFi:速率因子,表示达到子队列i分组到达速率对ΔWi的影响大小,RFi=max(Rate[i]/Rateref[i],1);

SLWB:标准链路带宽,也就是理想链路带宽,由网络设备及采用的物理层传输技术决定,其为一固定值;

ALWB:有效链路带宽,通过链路状态监视器测得的实际可用的链路带宽;

LSFi:链路状态因子,表示在调度子队列i时链路状态对ΔWi的影响大小,其大小为LSFi=ai×ALWB/SLWB,其中ai为子队列i的影响因子。

SWi:子队列i初始化权值,其值是在采用WRR调度算法的网络设备初始化时给子队列i分配的固定权值;

ΔWimax:表明子队列i允许的最大权值增量,用以保证即使各种外界情况变化极端的情况下,各类业务间维持基本的业务平衡,不至于出现“饥饿”现象。

ΔWi:表明子队列i相对于SWi的增量,其值通过计量器和链路监视器的结果共同获得,ΔWi =RF×LSFi×ΔWimax;

IWi:子队列i对应的实际权值,IWi=SWi+ΔWi 。

2.2 IWi的确定

如图1所示,某一分组到达时,分类器根据IP分组的特性对其进行分类,然后测量该分组所属的子队列i分组到达速率Ratei。调度器在按WRR算法调度分组时,当调度器调度到某一子队列i时,首先根据判决器获得的链路状态信息和计量器获得的数据到达速率相关信息决定本轮调度子队列i所对应的权值IWi,也就是本次可调度子队列i中的最多分组个数。其中

3 仿真分析

为了验证AQSM算法性能,通过网络仿真工具NS2实现该算法和WRR算法的性能比较。仿真所采用的拓扑结构如图2,仿真时物理层采用802.11b,物理带宽设为11Mb/s,8个移动终端,每一移动终端节点分别发送BE、AF、EF等3种业务流,这3种业务流占总负载的比例为1:2:4,各业务BE、AF、EF的初始化权值SWi分别为2、4、8。分别对AQSM、WRR算法的各类业务的丢包率及系统的吞吐量进行了仿真,仿真结果如图3、4、5所示。

从图3、图4的仿真结果可以看出,AQSM算法能降低各类业务的丢包率,特别是高优先级EF的丢包率降低更为明显,从而提高了无线信道利用率;同时从图3中可以看出AQSM算法能实现业务类型BE、AF、EF间的业务区分;从图5仿真结果可以看出AQSM算法能增加移动节点AP的吞吐量,特别是在网络负载比较高的情况下,从而提高了网络的QoS。

4结论

无线资源调度算法 篇7

近年来,无线个域网已经成为人们关注的热点问题。无线个域网除了需要提供尽可能高的数据传输能力之外,还必须有灵活有效的控制管理方法,在保证服务质量的前提下,提高资源的利用效率。因此,作为协调QoS和无线系统资源使用的关键,调度机制的设计是系统设计的重要组成部分。

已有的一些无线通信系统,其调度算法多是从网络的传输能力、网络QoS出发来设计的。文献[1]、[2]考虑了系统的吞吐量,但是这些系统在吞吐量增加的同时无法确保网络的公平性和业务QoS;部分调度算法[3,4]将用户的业务流类型考虑进来,可以有效的提高系统的吞吐量,同时保证QoS,但是对于信道变化无法做出相应的调整;文献[5]中提出一种具体预约资源的新方案,但是同样也没有考虑到通信的信道环境。其他的一些如文献[6]是基于信噪比门限值的检测,将系统的吞吐量和业务QoS结合起来考虑,但其吞吐量的提高并不明显,而且调度策略的调整不灵活。因此,设计一种灵活的调度机制,能自适应无线信道,同时兼顾业务QoS,是十分必要的。

与上述工作不同,本文考虑的是基于超帧结构的高速宽带无线个域网时隙调度策略问题,将通信信道状况和业务QoS结合起来考虑。利用MAC的交互信息,各个链路能够获知当前信道的状况,从而获得一个实时最优链路帧长;同时中心节点也能够从交互信息中获知各个链路的业务QoS需求,为算法提供依据。在调度算法上,从协议层面上真正的将上述两者结合起来,同时通过控制参数k可以决定优先考虑的是哪一方面。通过调整k,信道条件恶劣时可在保证通信质量基础上提高系统的吞吐量;而信道质量良好的环境中,优先考虑网络QoS需求,使得各个链路的实际发送数据与满足服务曲线的要求偏差最小。从而达到在保证网络QoS的基础上提高系统吞吐量,同时又能灵活有效地调度资源。

本文剩余部分组织如下:第二节介绍系统模型,包括网络结构、MAC协议以及QoS模型;第三节介绍算法原理,第四节给出仿真结果和分析,最后是结论以及下一步工作方向。

2 系统模型

个域网中有多个节点,其中一个充当中心节点,负责网络控制信息的处理,但是在业务数据的处理上,各个节点都是平等的,节点之间的数据传输并不需要中心节点进行转发。

采用的MAC协议是基于IEEE 802.15.3a的超帧框架[7],见图 1。超帧中有M个大的传输时隙,每个大时隙又包含多个小时隙,我们称小时隙为时间片,时间片的大小固定,同时每个大时隙内传输的数据帧数目K固定。超帧长度就仅仅与每个时隙长度有关,而时隙是分配给各个的链路使用,因此最终整个超帧长度是与链路的数据帧长度有关。

考虑到网络中链路的QoS需求 ,采用基于"服务曲线"的控制模型[6,8]。

设Si(t)是非递减时间函数,如果在任意时刻t2,当会话i有分组滞留时,都存在一个时刻t1(t1< t2),t1是会话i的滞留期的起始时刻使得下面的式子成立:

$S{}_i(t{}_2-t{}_1)\le W{}_i(t{}_2-t{}_1)(1)$

其中Wi(t2-t1)是会话i在时间间隔(t1,t2)内实际接收的服务。那么我们说会话i被保证了服务曲线Si(t)。

可以采用下面的算法来保证服务曲线:给定服务曲线Si(t),可以计算底限曲线Di(t):

$D{}_i(t)=\underset{u\in B{}_j(s)}{{\displaystyle \min }}(S{}_i(t-u)+W{}_i(0,u))(2)$

式中,Bj(s)是所有不大于s的滞留期的起始时刻集合。底限曲线Di(t)表示为保证服务曲线Si(t)在时间间隔[0,t]内最少应该接收的服务数量。Di(t)可以通过以下的迭代算法进行计算:

在会话第一次有分组滞留时,Di(t)初始化为服务曲线Si(t),之后在第n次有分组滞留的起始时刻a${}_i^n$,Di(t)由下面的式子更新:

$D{}_i(a{}_i^n;t)=\min \{D{}_i(a{}_i^{n-1};t),S{}_i(t-a{}_i^n)+W{}_i(0,a{}_i^n)\}(3)$

假定网络内有N条链路,每条链路的QoS要求用相应的服务曲线进行描述。Di(t)和 Si(t)分别表示链路的底限曲线和服务曲线,Wi(t)是链路在时间(0,t)内实际发送的业务量。由于信道的变化,使得链路发送的业务量不能始终满足服务曲线的要求。定义t时刻的偏差量为:

$V{}_i(t)=\max \{D{}_i(t)-W{}_i(t),0\}(4)$

系统的偏差量为:

$D(t)={\displaystyle \sum _{i=1}^{{\rm N}}V}{}_i(t)(5)$

由上面的式子可以看出,当链路发送的业务量超过底限曲线的需求时,偏差为0;否则偏差等于底限曲线与实际发送业务量之差。

3 算法原理

在无线环境下,调度机制仅通过"服务曲线"模型来考虑QoS是不够的。因为在无线信道发生变化的时候,调度机制无法作出相应的调整;由于QoS优先保证,网络的其他性能如吞吐量等必然恶化。因此本文引进最优帧长,用于自适应信道变化。

3.1 最优帧长及网络吞吐量

给定链路Li,可以得出归一化有效数据吞吐量[9]:

$\frac{G{}_{WL}}{R{}_C}=\frac{L}{L+{\rm H}+{\rm O}}(1-{\rm P}{}_b){}^{L+{\rm H}}(6)$

其中L为用户数据帧长;H为MAC控制信息;O为物理层控制信息;RC为信道比特流数据率;Pb为信道的误比特率;GWL为用户的有用数据。H、O、RC固定,给定一个Pb ,GWL是L的函数,这样就可以得到链路的最优帧长L0(Pb),当数据帧长度为L0(Pb)时,链路能正确传输最多的比特数。同时随着信道状况的变化,Pb也是一直变化的,不同时刻L0(Pb)也是不同的。在时刻t,对于一个存在N条链路的网络而言,每条链路都可以根据当前的信道状况选择一个最优的链路帧长,分别为Li(t),i=1,2……N。

网络的吞吐量V,链路以相同的速率V0进行传输,记$Q={\rm K}{\displaystyle \sum _{n=1}^{{\rm M}}L}{}_n^{*}‚L{}_n^{*}$为使用第n个时隙进行传输的链路最优数据帧长,LSF为超帧的长度,则有:

$V=\frac{{\rm K}{\displaystyle \sum _{n=1}^{{\rm M}}L}{}_n^{*}}{L{}_{SF}/V{}_0}=\frac{QV{}_0}{{\rm H}+Q}(7)$

为了使网络的吞吐量最大,Q应取到最大值。 而Q的取值与最优帧长有密切的关系。从N个最优链路帧长中选取最大的M个即可以满足Q取到最大值,即选取N个链路中信道质量最优的M个进行传输;对于协议而言,链路状况能够通过CAP帧发送到中心节点,中心节点实时更新这些链路状况表,并根据此信息计算各个链路的最优数据帧长,广播通知各个链路。各链路最优帧长信息可用于调度算法从而实现资源调配自适应信道状况的变化,有效提高系统吞吐量。

3.2 调度算法

新算法需要平衡网络QoS的需求和提高系统吞吐量。因为,满足用户QoS要求的调度算法与满足吞吐量最大所要求的调度算法通常不一致。如为了达到吞吐量最大化的目标往往将时隙分配给信道质量最好的链路,而为了满足所有链路QoS的需求,必须将时隙分配给业务滞后最多的链路。如果滞后量大的链路所处的信道质量恶劣,那么它占用更多的时隙直到数据被正确接收为止,这就使得分配给其他链路的时间片减少,降低了系统的吞吐量。因此,算法将最优帧长和网络QoS模型结合起来考虑。

对于链路i,在时刻t的最优帧长为Li(t),为满足服务曲线要求的传输时隙长度Ti(t),Ti(t)的计算如下:

$\begin{array}{l}{\rm T}{}_i(t)=\frac{V{}_i(t)}{R}\\ =\{\begin{array}{l}\frac{D{}_i(t)-W{}_i(t)}{R}D{}_i(t)\ge W{}_i(t)\\ 0D{}_i(t)＜W{}_i(t)\end{array}(8)\end{array}$

记Li(t) 和Ti(t)为L、T。定义选择因子λ:

$\lambda =\frac{L+k\cdot {\rm T}}{L+{\rm T}}=\frac{(L/{\rm T})+k}{(L/{\rm T})+1}(9)$

其中k(k>0,且不等于1)为控制参数,当k>1时优先考虑网络的QoS,当k<1时优先考虑的是网络的传输能力。L/T反应了链路信道质量和数据滞后量的关系。

时隙的分配:当M<N,即时隙数少于链路数,选择λ最大的M条链路;当M≥N,即时隙数多余链路数,选择λ最大的N条链路,将剩余的(M-N)个时隙按之前的算法重新分配。

4 仿真结果

为了估计调度算法的性能,从网络的公平性和吞吐量(纯业务数据)来比较以下三种调度算法。算法一只考虑链路质量,即最优帧长,而算法二只考虑网络QoS,算法三同时兼顾前面两者,也就是本文的调度算法。

仿真过程中,节点的个数4,链路速率100Mbit/s,物理层的净荷数据率75%,各个链路业务数据10Mbit/s,控制参数k=1.5。

图 2表示归一化网络吞吐量与超帧中时隙个数的关系,用网络最大的吞吐量(100M)作归一化。图中三条曲线分别表示:算法一(L曲线),算法二(Q曲线),算法三(LQ曲线)。可以看出,算法一的网络吞吐量最大,算法二的网络吞吐量最小,算法三的网络吞吐量介于二者之间。随着超帧中时隙数的增加,各个算法的网络吞吐量也在增加,这是因为时隙数越多,每个超帧中纯业务数据在该超帧中占有的比例将越来越大。同时从图中还可以看出,时隙数M越大,LQ曲线越趋近于L曲线,越能显示出改调度算法的优越性。图 3表示三种调度算法下,网络中各个链路分配到时隙的比例,用于衡量网络的公平性。可以看出在算法二和算法三下,网络拥有较好的公平性,而算法一的各个链路获得时隙分配的比例相差很大,无法照顾到各个链路。

我们可以得出算法三在考虑QoS前提下,能有效的提高网络的吞吐量。图 4给出算法二和算法三的链路偏差量,用最大链路偏差量对两种算法的的偏差量作归一化处理。由于在算法三(LQ曲线)中引入最优帧长,和算法二(Q曲线)相比,只是在一定的程度上保障网络QoS,造成各个链路的偏差量较大。图 5给出当逐渐增大k值时,归一化偏差量曲线会越来越向Q曲线靠近,在k取无穷大的时候和Q曲线重合。

图 6给出网络吞吐量与k值的关系。0<k<1时,调度算法优先考虑链路质量,随着k的减小,网络吞吐量逐渐增大;当k>1时算法优先考虑QoS,随着k的增大吞吐量逐渐下降。但无论k取何值,调度算法都同时考虑了链路质量和QoS,只是偏重的程度不一样。

5 结论

本文研究了基于超帧的无线网络时隙调度问题,提出一种结合信道质量和链路业务QoS需求的时隙分配算法。仿真结果表明,结合"服务曲线控制模型"和"链路最优帧长"的调度算法能够保证在无线信道质量发生变化的情况下,实际发送的业务数据与曲线要求的偏差最小,同时能提高4%左右的系统容量。

基于链路选择因子的时隙调度算法虽然能够兼顾链路质量和业务QoS需求,获得性能上的提升,但是选择因子的建模仅考虑了L/T和控制参数k,因此还存在改进的空间;同时k的调整和信道质量的关系也还需要进一步的研究。

参考文献

[1]Bender P,et al.CDMA/HDR:A bandwidth efficienthigh speed data service for nomadic users[J].IEEECommunication Magazine,2000.38(7):70.

[2]Sung Kyung Kim,Dae Soon Cho,Dong Seung Kwon:Anapproach to the packet scheduling with multi-users diver-sity in wireless CDMA systems[A].Personal MobileCommunications Conference,2003[C].5th European(Conf.Publ.No.492),pp.220-224

[3]Murtaza Zafer and Eytan Modian,Joint Scheduling ofRate-guaranteed and Best-effort Services over WirelessChannel[A].Proceedings of the 44th IEEE Conferenceon Decision and Control,and the European Control Con-ference 2005[C],pp.6022-6027.

[4]Hsi-Lu Chao,Wanjiun Liao,Credit-Based Slot Allo-cation for Multimedia Mobile Ad Hoc Networks[J].IEEEjournal on selected areas in communications,VOL.21,NO.10,December 2003.pp.1642-1651.

[5]Abdelhakim Hafid,Abdelilah Maach,A Novel ResourcesProvisioning Scheme in Time Slotted Optical Networks[A].Communications,2005.ICC 2005.2005 IEEE In-ternational Conference[C],pp.1641-1645.

[6]邱晶等.基于服务曲线的TDMA无线网络上行信道时隙调度算法[J].高技术通信,2005,15(6):14-18.

[7]IEEE Std 802.15.3TM-2003,The Institute of Electricaland Electronics Engineers[S],Inc.3 Park Avenue,NewYork,NY 10016-5997,USA.

[8]Stoica I,Zhang H,Ng TS E.A hierarchical fair servicecurve algorithm for link-sharing,real-time,and priori-ty services[J].IEEE/ACM Trans on Networking,2000,pp.185-199.