MAC调度算法

MAC调度算法（共5篇）

MAC调度算法 篇1

1 LTE-B的目前进展[1,2,5]

LTE-Beyond(LTE-B)是对LTE-A的进一步增强,它主要包括增强的物理下行控制信道(ePDCCH)、新型载波(NCT;以前的名称是ACT)、软小区(Soft Cell)等。这些技术都有可能成为未来的R12主流技术。

LTE-B的研究开始于2012年6月11日12日。未来的R12和R13都属于LTE-B(更为遥远的R14和R15都属于LTE-C)。

2 LTE-B在未来可能的关键技术

3这些可能的关键技术对MAC调度算法的影响

3.1 ePDCCH

这个对现有方案的影响较大,不能使用现有的PDCCH分配算法,也不能使用现有的R-PDCCH分配算法。

3.1.1 ePDCCH的频域资源确定及ePDCCH的ICIC

类似于R-PDCCH,各个UE的ePDCCH的频域资源(PRB位置)是由基站的RRC单独配置的。各个UE的ePDCCH的频域资源可以相同也可以不同,还可以部分相同(部分重叠)。

分配给ePDCCH的PRB如果没有被ePDCCH占用,可以给PDSCH使用。

相邻小区的ePDCCH的PRB最好错开。特别地,针对小区边缘的UE(信号质量差的UE),相邻小区的ePDCCH的PRB需要错开。这对ePDCCH的CoM P操作来说是较好的。如图2所示。

3.1.2 ePDCCH的可用RE数(编码速率)的确定

当ePDCCH碰到CRS/PSS/SSS/PBCH等的时候,ePDCCH需要把它们占用的资源避让开来。

一般来说,ePDCCH的编码速率不应太高(例如,不应超过3/4)。

3.1.3 ePDCCH的信道状况的确定

可以UE上报的宽带CQ(I或子带CQI)来确定,也可通过RSRQ和RSRP来确定。

3.1.4 ePDCCH的eCCE数量(集合度、聚合度)的确定应指出的是:在分配ePDCCH时,不能单纯地使用集合度,还应考虑实际的编码速率,因为可能碰上CRS等信号/信道。

一般地,可先根据信道状况(如,CQI)来初步定一个聚合度,然后在此基础上根据码率上调一级或多级聚合度(如,从Level 2上调到Level 6)。

3.1.5 ePDCCH的发射方式的确定

对于信道稳定的部署场景(如,室内、郊区、大草原等),建议使用集中式发射(相当于LVRB;这种方法也简单而实用)。对于信道变化大场合,建议使用分布式发射(相当于DVRB;复杂而不太实用)。

3.2 NCT

这个对现有方案的影响较大。

P DSCH可用符号(码率)计算需要修改;

CQI→MCS的映射表需要修改;

CQI→PRB数量的映射表需要修改;

如何利用eP DCCH未占用的RE;

CoM P在小区间的协调下如何调度。

另外,NCT可能有多种形式(例如,带宽不同、CRS密度和位置不同、CP不同等等)。

3.3 Soft Cell

这个对现有方案的影响相当大。基本上,颠覆了现有构架。

3.3.1控制信道(ePDCCH)与数据信道(PDSCH/PUSCH)分离

控制信道由宏站发射,而数据信道由微站发射。宏站与微站可以同频(还可以做成超级小区),也可异频(跨载波调度)。存在以下问题:

什么时候需要分离?

针对什么样的信道状况?

怎样分配ePDCCH?

并行调度?串行调度?

如何在宏站预留ePDCCH的资源?

3.3.2控制面(RRC)与用户面(PDCP/RLC/MAC)分离

一般地,这主要针对处于微站覆盖边缘的UE来进行操作。

控制面与用户面的耦合性需要降低。控制面的MAC调度器(调度UE的DCCH/SRB)和用户面的MAC调度器(调度UE的DTCH/DRB)分别在2个小区上(也可能在2个载波上),它们的操作相对独立。

一般地,在上行方向控制面与用户面(SRB/DRB;DCCH/DTCH)难于分离。

定时操作需要独立维护。

参考文献

[1]NTT.RWS-120010-Requirements,Candidate Solutions AND Technology Roadmap for LTE Rel-12 Onward.3GPP Workshop on Release 12 and onwards,Ljubljana,Slovenia,June 11-12,2012.

[2]Ericsson.RWS-120003-LTE Release 12 and Beyond.3GPP Workshop on Release 12 and onwards,Ljubljana,Slovenia,June11-12,2012.

[3]ALU.RP-120856-Way Forward on Rel-11 completion in RAN1.3GPP TSG-RAN Meeting#56,Ljubljana,Slovenia,13-15 June2012.

MAC调度算法 篇2

这些退避算法各具优势, 但在负载波动变化急剧、数据复杂的中高速无线传感器网络环境中, 网络性能则大幅下降。因此, 本文在深入研究PTTL退避算法的基础上, 提出一种密度预测与服务分级的MAC退避算法DP-SC (Density Prediction and Service Classification) , 以达到提高网络信道利用率与网络吞吐量的目的。

1 PTTL退避算法介绍与分析

PTTL退避算法主要思想是:流量分级与转发优先。即节点通过侦听信道状态来判断当前网络流量级别, 并对转发节点赋予较小竞争窗口而增大其信道接入概率。PTTL退避算法描述如下:

(1) 空闲状态, CW=max (CWmin, CW-i3) , 其中i是连续侦听到空闲时隙数, CWmin是窗口最小值。

(2) 发送成功, CW=max (CWmin, CW-s2) , 其中s是连续成功竞争信道并发送报文成功次数。

(3) 发送失败, 竞争窗口CW为:

其中C是连续竞争信道失败次数, Cmax是最大退避次数, CWmax是窗口最大值。

(4) 节点是转发节点, 则CW=CWmin。

总的来说, PTTL退避算法简便易行, 在网络负载较重的网络环境中性能良好。但PTTL退避算法并没有服务分级, 即不同业务类型数据以相同的机会接入信道, 造成关键数据延迟, 不能反映实际需求。且节点是转发节点, 则CW将无条件降低到CWmin, 虽然这样能够在一定程度上提高转发能力并保证数据转发优先, 但是当网络负载严重时, 不区分服务类型的无条件降至最小值CWmin, 会造成碰撞概率急剧增加, 反而与尽快将数据发送出去的初衷相反。因此关键类型数据应该具有接入信道优先权, 提高优先级数据的传输率, 减少关键类型数据时延来满足应用实时性需求。

2 DPSC退避算法设计

为了提高网络负载重且负载波动急剧的中高速无线传感器网络性能, 基于PTTL退避算法提出密度预测与服务分级MAC退避算法DPSC。主要创新点如下:

(1) 网络节点数目进行加权递推平滑预测。节点密度与邻近节点数目是一一映射关系, 即某节点的邻近节点越多, 此节点区域的节点密度越大。假设网络自适应占空比p∈[0, 1], 即节点每周期处于活动状态概率为p。在每个估算周期i∈[1, n], 利用竞争窗口来实现计算邻近节点, 且计算节点数是指除开周期1～i-1中已计算的所有醒来邻近节点。在估算周期i中, 询问节点发送询问包REQ。接收到询问包REQ且未有回答的醒来节点时, 在M个时隙中随机选择一个时隙回复一个装载唯一身份ID的回复包ANS。询问节点在第i窗口成功收集分组Gi数目并记录ID。由伯利努试验二项分布可知占空比为p、实际邻近节点数目为N且发生k次的概率为:

现定义L (N, G1, …, Gn, p) 为在周期1, 2…, n中邻近节点数为G1, k2, …, Gn的概率, 由二项分布公式[7]可知,

则实际邻近节点数目N的最大似然估算值N*为:

由于是高阶运算而直接计算式 (2) 得出最大值十分困难。事实上, L (N, G1, …, Gn, p) 一定存在一个整数最大值N^≈N*, 当N′不等于N^时,

当式 (4) 接近1时, 最大似然估算值N*必定在区间[N′, N^]即区间[N-1, N]中, 则

即

则由式 (5) 可得最大似然估算值N*为:

N*= (仪ni=Σ1Gi) / (1- (1-p) n) 仪 (6)

定义Nc为当前邻近节点数目, Nj为第j个最大似然估算值, 则对节点数目最大似然估算值进行加权递推平滑估算可得当前邻近节点数目Nc为:

其中l是平滑因子, l值越大则估算值越平滑, 适应节点密度变化能力越差, 这里取中间值l=5;Cj是权重值, Cj越大表示相对应的Nj*权重越大。C1

(2) 引入服务分级因子δ∈[0, 1]。基于服务分级思想, 优先级别越高的类型数据对应的δ越大, 反之亦然。为了能进行服务质量区分, 应对复杂数据进行数据分类。数据分类原理是, 把所有数据分成m优先等级, 并且每个节点中有m个数据类型缓冲数据队列, 缓冲数据队列容量总数分别为Q1、Q2、Q3…Qm, 当前数据队列数分别为q1、q2、q3…qm。可得节点的服务因子δ为:

即δ= (K1×δ1+K2×δ2+…+Km×δm) / (K1+K2+…+Km) , 其中Ki是i类型数据的缓冲数据队列比率, 且Ki=qi/Qi。

(3) 引入负载分级因子κ∈[0, 1]。负载分级因子κ越大, 则表明网络负载越重, 应该尽快把数据发送出去, 减轻节点数据积压。负载分级因子κ为:

(4) 引入多跳传发优先因子μ。数据传输中经过跳数越大, 相应数据时延也越大。关键数据往往经过多跳传输后实时性得不到满足。因此同等级数据的跳数越多则越应该优先转发, 减小发送时延。具体实现是数据捎带多跳总跳数Jn与当前跳数Ji, 则多跳传发优先因子为:

根据以上思路, 提出了一种密度预测与服务分级的MAC退避算法:DPSC。具体实现步骤如下。

(1) DPSC退避算法先对每个节点i竞争窗口设定最小值CWmin×log (Nci) 和最大值CWmax×log (Nci) , 初始退避窗口设置为CWmin。同时为区分当前网络负载情况, 设置一个退避窗口分隔阈值CWm×log (Nci) 。其中CWm×log (Nci) 把竞争窗口区间分隔成如图1所示。

(2) 空闲状态, 即当检测到连续的信道空闲时隙数大于2×CWmin×log (Nci) 时, 根据式 (6) 、式 (7) 更新节点i的当前网络邻居节点数Nci, CW更新为:

其中Z代表取整。MAX表示取最大值。

(3) 发送成功时,

(4) 发送失败未超过最大退避次数阈值Fth时,

其中Fcourt是连续竞争信道失败次数, F表示规定失败次数, Jn是数据传输多跳总次数。

(5) 发送失败超过规定次数阈值Fth时,

(6) 负载分级因子κ超过包队列容忍阀值κth时,

其中, 容忍阈值κth= (1-δ) ×κ′, κ′表示规定的数据包队列数容忍值。

(7) 接收到RTS包时, 进行服务分级优先转发,

3 仿真与实验分析

本文采用NS2仿真平台, 为了评估新退避算法在实际应用场景的性能, 采用节点随机分布的网络拓扑。节点数目随机分布在80 m×80 m的范围内, 各节点都处于相互通信范围内, 节点的通信距离为120 m。

3.1 节点密度预测分析

邻近节点数目的最大似然估算值N*与节点占空比p有关, 占空比p的大小决定N*的估算精确度。当前网络邻居节点数Nc与平滑因子l、权重系数Cj相关, 此处取l=5, C1=0.2, C2=0.4, C3=0.6, C4=0.8, C=1.0。其中相对误差e=|Nc-N|/N, Nc是当前邻近节点数目加权递推平滑预测值, N是当前邻近节点数目真实值。

从图2可知, 邻近节点数目越多, 占空比p越大, 则当前邻近节点数目加权递推平滑预测值与真实值相对误差e越小, 即平滑预测值越接近真实值, 估算精确度越高。同理, 对于节点密度大的区域节点可以设置较低的占空比p进行估算而得到可靠的邻近节点数目估算值, 且减少估算周期侦听所消耗的能量。

3.2 系统时延分析

从图3可知, 节点数目较少时各算法端到端时延基本相同, 但节点数目较多时的时延相差甚远。DPSC算法时延增加速率最小, 因为能够根据邻近节目数目动态地修改竞争窗口, 减少碰撞概率与重发次数, 从而减少端到端时延, 能够适应不同节点数目的网络环境。

3.3 系统吞吐量分析

从图4可知, 随着节点密度增大吞吐量都有所下降, 在节点数目小于10时吞吐量大致相同, 之后出现大幅度差距。因为随着节点数目的增加, 节点冲突概率将会增大, 所以各种算法吞吐量都有所下降。其中DPSC算法下降速度最慢是由于邻近节点数目能自适应竞争窗口, 从而有效地提高信道利用率, 相对PTTL算法平均提高15%。其余三种算法都不太适应于高节点密度的网络环境, 特别是BEB算法吞吐量下降最快。

3.4 系统能耗分析

从图5可知, 各退避算法成功发送每比特数据的平均能耗随着系统网络节点数目的增加而增加。在邻近节点少的网络系统中, 其他三种算法能耗低于DPSC算法, 因为密度低而竞争信道的冲突少, 数据发送成功率高, 而DPSC算法却因节点估算预测的周期侦听耗能略高。但高密度时DPSC算法因为根据节点数目动态地改变竞争窗口而降低冲突概率, 减少重传次数, 所以平均能耗明显低于其他三种算法, 相对于PTTL算法平均下降5%。

本文退避算法DPSC通过二项分布概率模式对邻近节点数目进行最大似然估算并进行加权递推平滑预测, 精准地估算出邻近节点数目, 实现竞争窗口自适应节点密度的目的;根据服务分级思想, 引入服务分级因子δ实现服务级别高的数据能优先发送;引入负载分级因子κ表示负载级别并赋予数据积压的节点优先发送权;引入多跳传发优先因子μ实现数据前传的连续性与减少时延, 满足关键数据多跳传输实时性要求。DPSC退避算法与其他三种算法在节点低密度与低负载情况下网络性能差别不大, 但在节点高密度与高负载情况下则表现出优越的网络性能。进一步的工作将采用无线传感器硬件平台CC2430对DPSC退避算法进行实际性能测试。

参考文献

[1]王越超, 程良伦.中高速传感器网络中基于服务区分的QoS路由算法研究[J].计算机应用与软件, 2010 (8) :152-158.

[2]CHIA W C, CHEW L W, ANG L M, et al.Low memory image stitching and compression for WMSN using stripbased processing[J].International journal of sensor net work, 2012, 11 (1) :22-32.

[3]PANTAZI A, ANTONAKOPOULOS T.Equilibrium point analysis of the binary exponential backoff algorithm[J].Computer Communications, 2001, 24 (18) :1759-1768.

[4]Zhang Yi, PIUNOVSKIY A, AYESTA U, et al.Convergence of trajectories and optimal buffer sizing for MIMD congestion control[J].Computer Communications, 2010, 33 (2) :149-159.

[5]奎晓燕, 杜华坤.CIMLD:多跳Ad Hoc网络中一种自适应的MAC退避算法[J].小型微型计算机系统, 2009, 30 (4) :679-682.

[6]余庆春, 谭狮.一种基于转发优先及流量分级的无线传感器网络退避算法[J].计算机应用研究, 2012, 29 (5) :1846-1849.

短作业优先调度算法 篇3

姓名：陈凯

学号：541413430202

地点：四教楼301

指导老师：张旭

专业班级：嵌入式软件14-02

实验名称：短作业优先调度算法

一、实验目的：

测试数据可以随即输入或从文件中读入。必须要考虑到作业的到达时间

最终能够计算每一个作业的周转时间。

二、实验内容：

模拟实现短作业调度算法，具体如下：

设置作业体：作业名，作业的到达时间，服务时间，作业间的链接指针 进程初始化：由用户输入作业名、作业的到达时间和服务时间进行初始化。显示函数：

1、显示当前调度的是哪个作业，后备队列中有哪些作业

2、最终显示每个作业的作业名、到达时间、服务时间、完成时间和周转时间

排序函数：对就已到达的作业按照服务时间进行排序。注意考虑到达时间 调度函数：每次从已到达的作业队列队首调度优一个作业执行。删除函数：作业结束后撤销。

三、实验代码

#include structsjf //定义进程的结构体 {

char name[10];//进程名

floatarrivetime;//到达时间

floatservicetime;//服务时间

floatstarttime;

//开始时间

floatfinishtime;//完成时间 floatzztime;//周转时间 floatdqzztime;

//带权周转时间 };

sjf b[100];

//定义短作业优先算法进程的最大数量 voidSinput(sjf *p,int N)

//输入函数 { int i;

printf(“输入进程的名称、到达时间、服务时间:n”);for(i=0;i<=N-1;i++){

printf(“输入第%d进程的名称、到达时间、服务时间:”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} }

//输出函数 voidSPrint(sjf *p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,int N){ int k;

printf(“n执行顺序:n”);printf(“%s”,p[0].name);

for(k=1;k

{

printf(“-%s”,p[k].name);}

printf(“n进程名tarrivetservicetstarttfinishtzztdqzzn”);

for(k=0;k<=N-1;k++)

{

printf(“%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftnn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);

} }

voidSsort(sjf *p,int N)

//按短作业优先算法排序 {

for(int i=1;i<=N-1;i++)for(int j=1;j<=i;j++)

if(p[i].servicetime

sjf temp;temp=p[i];

p[i]=p[j];

p[j]=temp;} }

//运行结果 voidSdeal(sjf *p, float arrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,int N){

int k;

for(k=0;k<=N-1;k++)

{

if(k==0){

p[k].starttime=p[k].arrivetime;

p[k].finishtime=p[k].arrivetime+p[k].servicetime;

} else {

p[k].starttime=p[k-1].finishtime;//开始时间=前一个进程的完成时间

p[k].finishtime=p[k-1].finishtime+p[k].servicetime;

//结束时间=前一个进程的完成时间+现在进程的服务时间 }

}

for(k=0;k<=N-1;k++){

p[k].zztime=p[k].finishtime-p[k].arrivetime;

//周转时间=完成时间-到达时间

p[k].dqzztime=p[k].zztime/p[k].servicetime;

//带权周转时间=周转时间/服务时间 } }

void SJF(sjf *p,int N){

float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;

Ssort(p,N);

Sdeal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);

SPrint(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);}

void main()//主函数 { int M;printf(“------------短作业优先调度算法-----------n”);printf(“输入作业数:”);scanf(“%d”,&M);

Sinput(b,M);SJF(b,M);}

四、实验结果

五、实验总结

MAC调度算法 篇4

关键词：无线传感器网络,MAC,自适应

0 引言

作为无线传感器网络协议栈重要基础架构的MAC协议, 决定着无线信道的使用方式, 负责为节点分配无线通信资源, 直接影响网络整体性能, 成为无线传感器网络协议研究的重中之重。到目前为止, 己有大量针对无线传感器网络的不同特点和具有应用的MAC协议相继提出[1]。

1 S-MAC协议性能简析

S-MAC协议是一种改进后的MAC协议, 它主要使用三种新技术来减少能量消耗和支持:节点周期性的睡眠, 邻居节点形成虚拟簇在睡眠制度上自同步, 以及利用消息传递机制来发送长包, 减少竞争反应时间。

S-MAC协议需要一些时间同步, 但它不同于TDMA需要建立庞大的时间表。S-MAC有两个重要的限定性因素:一个是总的帧时间受限于时延需求和缓存空间;另一个是尽管S-MAC协议比802.n节省更多的能量, 但是它不能很好的适应网络流量的变化, 因为对于选定了某种周期监听/睡眠调度机制的传感器节点而言, 它具有一个固定的占空比。

S-MAC协议达到了能量节省的目的, 但是相应的减小了吞吐量和增大了时延。整个协议本质上用吞吐量和反应时间作代价来换取能量的高效率。吞吐量减少是因为只有帧的活跃部分才会用于通信。反应时间的增加是因为睡眠时间内到达的数据只能在下一个活跃时间才能发送。

目前已有多种关于S-MAC的改进方案[2,3,4], 如T-MAC在S-MAC的基础上, 通过进一步的减少空闲侦听来节省更多的能量, 它比S-MAC更节能, 但吞吐率不如S-MAC;自适应侦听的S-MAC用来减轻S-MAC协议中的延迟问题, 但同时自适应侦听也导致一些节点不能进行正常的睡眠, 降低了能量效率;WiseMAC虽然在节能上对S-MAC作了改进, 但由于节点的唤醒不同步, 应用于多跳传输时会导致冲突, 当负载较重时性能也会急剧下降。可见, S-MAC以及一些改进方案是针对轻负载或较简单的无线传感器网络设计的, 当负载变重或网络状态不稳定时, 这些协议均难以保证系统的能量效率和吞吐率。

2 改进型自适应A-MAC协议

2.1 协议改进的内容

为了获得更好的能量效率、时延和吞吐量性能, 尤其要适应网络负载的动态变化, 研究了自适应的MAC协议 (A-MAC) 。协议主要分为3部分。

①收发节点间的耦合

在没有数据流的情况下, 节点随机唤醒, 唤醒周期取最大值Tw, max当节点有数据发送时, 如图1所示, 经过媒体监听 (CS) 后, 在数据包前添加交替出现的发送 (T) 和接收状态 (R) 。在T状态时, 节点发送携带目的地址的信息, 随之进入R状态, 准备接收目的节点的返回信息。邻节点如果发现发节点发送的前导信息中的目的地址指向自己, 则回送确认信息, 否则进入休眠。若发节点接收到确认信息, 即停止发送T和R序列, 开始发送数据。如果T和R序列长度达到节点可能的最大唤醒周期Tmax仍没有收到确认信息, 则停止发送并且报错。

一旦成功传送第1个数据包, 收发节点间建立耦合关系。节点在发送数据包时, 同时告知收节点下次唤醒时间Tw。当这一时间到来时, 收发节点同时醒来。唤醒时间由网络负载大小决定, 下文将给出算法。如果在耦合期间出现唤醒后无包可传的情况, 发节点发送1个填充包, 只包含下次预期唤醒时间。收节点同样要返回确认信息ACK。如果填充包丢失从而发节点没有收到ACK包, 则下次唤醒时间将不变。如果连续发送3个填充包则收发节点解除耦合关系。

②唤醒时间的确定

在发节点发包时, 如果其存储空间中有2个以上的数据包 (包括节点产生和转发的数据包) , 则下个唤醒时间将为可能的最小值Tw, min, Tw, min为保证节点可以无冲突沿链路连续发送的最小时间间隔。

如果节点只有1个数据包发送, 则距下一唤醒时间间隔将由最近数据负载决定。如图2 (a) 所示, 如果节点上出现Tw, min, 表示节点的唤醒频率小于包到达速率, Tw将在原来的值上减少。减少方式包括加性减少和乘性减少等。如果出现图2 (b) 中节点唤醒后无包可发的情况, 则表示节点唤醒频率大于包到来的频率, Tw则会增大, 增大的方式由应用层决定。

③沿链路方向节点唤醒时间的安排

收节点获知下次唤醒时间后, 将在其基础上加上完成一次收发所用的时间, 通知它的下一跳节点, 从而在本跳收发完成后立即转入下一跳的收发。这样, 在数据传送的方向上, 各节点的唤醒时间相互错开, 如图3所示。除第1个数据包存在平均Tmax/2的时延外, 后续包在发送时将如同节点一直唤醒一样, 不存在休眠时延, 在数据传输的链路上, 数据包将快速传送。

在网络中存在多个数据流时, 彼此间存在竞争关系。此时节点通过载波监听 (CS) 竞争信道。即使竞争失败, 按上述算法, 收发节点将在下次唤醒 (时间间隔不变) 时重试。因此, 只是引入了少量时延, 多个数据流可同时进行。

2.2 协议性能分析

由于节点唤醒周期自适应调整, 所以在没有数据或数据较少时, A-MAC唤醒周期可以很大。假设数据流发送周期为Tp, 则当Tp>Tw, max时, Tf的值约为Tw, max。当Tp<Tmax, 有,

$\underset{t\to \infty }{{\displaystyle \lim }}{\rm T}{}_f={\rm T}{}_p(1)$

比较A-MAC、S-MAC的能量效率, 考虑2种MAC协议下的占空比。假定2种情况下节点唤醒时长均为t1, 数据流稳定, 包到达的周期为Tp。S-MAC的帧长为Tf有,

RS-MAC= (t1/Tf) ×100% (2)

无论负载为多少, 节点的能耗为定值。

而A-MAC中, 当Tw, min<Tp<Tw, max时有,

RA-MAC= (t1/Tf) ×100% (3)

当Tp>Tf时, AS-MAC的能量效率要高于S-MAC协议。当Tw, min<Tp<Tf时, A-MAC的能耗增大, 但此时网络承担的负载也增大, 平均每次传输的耗能并未增加。

时延方面, S-MAC中相邻节点的唤醒时间差为1个周期, 因此,

$E[D({\rm N})]{}_{\text{S}-\text{Μ}\text{A}\text{C}}=[{\rm N}-\frac{1}{2}]{\rm T}{}_f+t{}_{cs}+t{}_{tx}(4)$

由休眠造成的时延非常大。

除了第1个包传送时延较大外, 由于各跳节点的唤醒相位相互配合, A-MAC每一跳的相位差为d=tcs+ttx, d的取值使得时延最小, 即,

E[D (N) ]A-MAC=N (tcs+ttx) (5)

类似于节点一直监听的情况, 其由休眠造成的时延非常小。

上述改进协议具有根据负载进行自适应的能力, 即使数据负载很大时, 仍然可以通过调整节点的唤醒周期提高吞吐量。而S-MAC下其吞吐量是固定的。

3 OPNET仿真分析

OPNET是一款界面简洁仿真效果逼真的仿真软件, 优势在于OPNET整个产品线面向网络研发的各个阶段, 既可以完成网络的设计, 也可以作为研究网络性能的依据[5], 所以本论文采用OPNET作为仿真平台。仿真实例中站点数量为20、40、60、80、100, 分别对应曲线test1, test2, test3, test4, test5。

3.1 网络平均吞吐量分析

图4是S-MAC和改进后的自适应A-MAC网络吞吐量性能仿真图。

从仿真的结果图4可以看出, S-MAC协议在活动站点从20增加到100时, 网络吞吐量性能降低了15.9%, 而改进后的A-MAC协议, 吞吐量性能降低了10.4%, 可见在网络活动站点数量增加的情况下, 改进后的协议具有更好的适应性。

这种改进方法是以提高无线局域网的吞吐量为目的, 尤其在网络活动站点增加的情况下可以有效防止网络吞吐性能下降。

3.2 平均网络平均时延分析

图5是S-MAC和改进后的自适应A-MAC网络平均时延仿真图。

从仿真结果可以很明显看出, 当系统从20个站点增加到100个站点后, S-MAC协议平均时延起伏量大于改进后的自适应A-MAC协议平均时延起伏量。可见, 改进后的协议比较稳定, 能够更好地适应时延抖动要求高的场合。

4 结束语

本文对无线传感器网络MAC协议中因为节点休眠而造成的相邻节点的通信协调、时延和吞吐量的问题, 提出了一种新的自适应的协议A-MAC。本协议不需要节点间的周期性同步, 动态调整节点唤醒的周期和相位, 从而可以在两个方向上减少时延和灵活地适应负载变化, 同时具有高能量效率。

参考文献

[1]Akyildiz I F, Su W, Sankarasubramaniam Y, et al.A survey onsensor networks[J].IEEE Communications Magazine, 2002, 40 (8) :102-105.

[2]Xiao X, Zheng B Y, Yan Z Y, et al.Energy efficient TDMA-basedMAC protocol associated with GAF for wireless sensor networks[J].The Journal of China Universities of Posts and Telecommunica-tions, 2007, 14 (1) :6-11.

[3]van Dam T, Langendoen K.An adaptive energy-efficient MAC pro-tocol for wireless sensor networks[C]∥Proc 1st International Con-ference on Embedded Networked Sensor systems (SenSys) .LosAngeles.CA, 2003:171-180.

[4]Ye W, Heidemann J, Estrin D.An energy-efficient MAC protocolfor wireless sensor networks[C]∥Proc 21st International AnnualJoint Conference of the IEEE Computer and Communications Socie-ties (INFOCOM2002) .New York.NY, 2002:1567-1576.

MAC调度算法 篇5

近年来, 随着无线网络的不断改进, 其使用范围迅速扩大, 但其存在一些急待解决的问题, 如当竞争节点数目增加时, 系统吞吐量、公平因子、平均时延等参数恶化, 特别是当两个设备利用一个中心接入点进行连接, 这两个设备都能够“听”到中心接入点的存在, 而互相之间则可能由于障碍或者距离原因无法感知到对方的存在的“隐含终端”问题。

IEEE802.11b是专门为无线局域网 (WLAN) 制定的一个标准, 该标准分别定义了物理层和媒介访问控制的技术规范。而IEEE802.11b的MAC层“分布式访问方式”实现将很好的解决了这些难题, 保证设备之间传输的速率和数据的可靠性, 提高吞吐率, 实现多用户无线媒介共享资源等问题。

2 退避机制分析

2.1 退避时间选取

退避时间选取如下:T=CW*Random () *SlotTime

其中Random () 是随机数, Slot Time是总传播时延, CW是竞争窗口, 它是Slot Time的整数倍。CW在CWmin和CWmax之间选择, 当一帧进入发送缓存时CW初始化为CWmin, 以后每次尝试重传后CW加倍直至CWmax。

2.2 退避规程调用

对于要发送帧的STA而言, 当物理载波或虚拟载波侦听发现媒介忙时, 则该STA将调用退避规程。当发送STA预测一个发送失败后, 也将调用退避规程。

在退避状态下, 检测到信道空闲时退避计时器开始计时, 其间如检测到信道忙, 则退避计时器停止计时, 直至信道空闲时间大于DIFS后计时器恢复计时。在这种机制下当多个站延迟并进入随机退避状态后, 退避值最小的站将在竞争中获得介质访问权;在竞争中失败的站会保持退避状态直到下一个DIFS。这样在下一次竞争中这些站可能会比新进入退避的站有更短的退避时间, 避免了有的站永远不能获得介质访问权的可能。

执行退避规程的STA用载波侦听机制决定每个退避时隙间媒介是否有活动。如果在某一退避时隙期间没有媒介活动的报告, 则退避规程将退避定时器减去一个时隙时间 (SlotTime) 。

如果在退避时隙期间, 媒介状态为忙, 退避规程将挂起, 退避定时器对该时隙不计数。当媒介空闲时间达到DIFS后, 允许重新开始退避规程。只要定时器为0时, 就可以开始发送。

该规程的结果为:在多个正要延迟发送且进入随机退避的STA之间, 使用随机函数选用最小退避时间的STA将赢得竞争。

3 退避算法的研究与实现

3.1 退避流程分析

站点发送协调子模块在发送数据帧MPDU前必须进入退避 (Backoff_Procedure) 子模块进行退避过程, 而且数据帧MPDU发送失败时, 也必须进行退避过程, 退避过程是为了减少信道发生冲突的概率, 提高网络性能。退避流程如图1所示。

软件实现的关键参数是退避窗口CW的选取, 退避窗口CW数值在最大值Cwmax与最小值Cwmin之间, 并且与发送失败次数N有关。在确定了CW的值以后, 就可以在[0, CW]之间产生一个随机数来初始化退避计数器的值, 具体计算关系式如下:

3.2 退避算法模块分析

退避规程是进行后退回避的, 进程初始化后, 对远程变量m Bk Ip赋值为假, 表示后退回避不在进程中, 状态变迁为No_Backoff, 当Backoff消息到达时, 提取出cnt参数, 这是后退回避的时间值, 状态变迁为Channel_Busy.如果idle消息到达, 状态变迁为Channel_Idle, 只有在这个状态时, 每次到达一个Slot消息, 后退回避时槽数减一, 直到后退回避时槽数减小到为0, 发送Bk Done消息给TX_Coordination进程, 该消息的参数bstate=-2, 表示可以发送Tx Re-quest消息到Transmission模块。

3.3 退避算法模块状态转移图分析

根据Backoff_Procedure模块, 我们可以统计出Backoff_Procedure模块中包含的状态有:No_Backoff、Channel_Busy、Channel_Idle三个状态, 状态之间的转移图如图2所示。

3.4 随机退避算法实现

3.4.1 模块中信号和状态的定义

信号和状态是模块流程中最主要的两大元素。一个系统中各模块之间的交互是通过信号的方式来完成的。模块之间通过交互信号来协调工作, 模块中的进程一般处于是等待信号的状态。当一个模块接收到其他模块传来的信号, 如果这个信号是一个有效信号, 则对该信号进行处理, 处理完成状态转移到另一个状态等待信号的输入;如果接收到的是无效信号, 则丢弃。模块之间实现信号的传递。

3.4.2 信号定义

在程序设计中, 我们采用结构体的表达方式对各个模块之间通信所使用的信号进行定义。

在退避模块中的信号有:初始化信号Reset MAC, 从发送协调模块 (Tx_Coordination_Sta) 发送的退避信号Backoff (cw, cnt) , 发送到Tx_Coordination_Sta模块的带有退避是否结束信息的信号Bk Done, 以及由Reception模块发送的信道状态信号Busy、Idle和Slot。

结构体定义如下:

3.4.3 状态定义

我们采用枚举方式对模块中的状态进行定义。

在Backoff_Proucedure模块中的状态有:无退避进程状态No_Backoff, 信道忙状态Channel_Busy, 信道空闲状态Channel_Idle。

枚举方式定义如下:

3.4.4 退避算法核心代码:

代码设计如下:

4 结论

随着无线局域网技术的日趋成熟, 国内目前无线局域网的应用也比较多, 开发具有自主知识产权的无线网络产品具有重要的现实意义。目前, 我们已经完成了对IEEE802.11无线局域网协议MAC层随机退避算法的研究, 并已在此基础上开始分别用C代码实现, 实现简单的模块功能。

参考文献

[1]黎连业, 郭春芳, 向东明.无线网络及其应用技术[M].北京:清华大学出版社, 2004.

[2]曹秀英, 耿嘉, 沈平.无线局域网安全系统[M].北京:电子工业出版社, 2004.

[3]Mark Ciampa著, 王顺满, 吴长奇, 张岌译, 无线局域网设计与实现[M].北京:科学出版社, 2003.

[4]G.Binachi, Performance Analysis of theIEEE 802.11 Distributed CoordinationFunction, IEEE Journal on Selected Areas inCommu., Vol.18, no.3, Mar, 2000.