基于CSMA/CA改进算法的无线传感器网络OTA优化*

谢志明, 徐 杨

(贵州大学 大数据与信息工程学院,贵州 贵阳 550000)

0 引 言

文献[1]根据ZigBee联盟的相关空中下载(over the air,OTA)标准进行了相关的开发,但对更新效率方面关注度比较少,而且必须要配合相应的软件才能实现升级。文献[2]涉及无线传感器网络(wireless sensor networks,WSNs)空中下载协议,该协议为WSNs提供节点状态控制、程序代码更新等服务,在实际应用中需要进行具体优化。文献[3]提出了点对点的无线下载方案,但数据校验仍不足,可能会导致数据错误。文献[4,5]在研究OTA实现过程的基础上,设计出了一种能够提高更新效率的镜像页请求方法,但要求在理想环境下进行,没有考虑外界因素对结果的影响。

本文针对小规模ZigBee网络的多节点镜像程序的同步更新升级,采用通用架构、多点并发、高效的无线下载解决方案。节点自主向网络覆盖范围内的服务器或者子服务器申请镜像程序,协调器控制OTA升级过程,从而实现多节点并发升级。该方案不仅可以解决镜像数据在网络路径上重复传输的问题,且可以解决ZigBee网络中的数据冗余问题,实现多节点更新升级效率的提高。

1 OTA原理

在OTA技术[6]中,起到作用的是3个概念上的组件：协调器、服务器和客户端。协调器组建网络,通过单播或广播发送镜像升级通知,以及激活验证后的新镜像。OTA服务器通过串行总线连接到PC并下载镜像升级程序。服务器提供了镜像升级文件的来源,其主要负责的OTA客户端镜像程序升级。服务器承担协调器和OTA客户端之间的通信任务,其负责处理由协调器和OTA客户端发送的请求,并将镜像文件发送给由ZigBee网络提供的所有OTA客户端。OTA客户端通过ZigBee网络连接到OTA服务器,主要负责接收和处理OTA 服务器发送的命令和镜像文件数据。

镜像文件传输过程为：当许多OTA客户端同时开始升级镜像时,协调器将发送镜像升级命令到OTA服务器。OTA服务器收到升级命令后,会通过ZigBee网络向所有OTA客户端发送镜像广播升级通知。OTA客户端收到升级通知后,会判断镜像版本是否最新。如果OTA客户端需要升级镜像,则镜像程序将由ZigBee网络从OTA服务器下载。所有OTA客户端的镜像数据都由OTA服务器在网络中发送。在客户端校验镜像文件无误后,还需要协调器端发送命令激活镜像。

2 改进的远程更新

2.1 多节点并发升级

本文结合现有的OTA技术体系结构和P2P技术思想,提出了一种多节点并发升级方案[7],以提高广播升级的效率。OTA服务器在图1中被重命名为主服务器(master server),且所有具有服务器功能的路由器都被重命名为子服务器(subserver)。

图1 多节点并发升级体系结构

当OTA客户端开始广播升级时,升级过程基本类似前述升级过程。所不同的是,所有的OTA客户端都直接将镜像程序数据请求发送给父节点(主服务器或子服务器),并非所有的OTA客户端都将请求发送到OTA服务器。主服务器从协调器接收镜像数据并将镜像数据发送回镜像请求的子服务器和少部分OTA客户端。当子服务器完成镜像数据的接收时,其将收到的镜像数据发送给另一部分OTA客户端。在多节点并发升级方案中,所有OTA客户端完成1个镜像数据传输,且每个父节点(协调者除外)将仅接收镜像程序数据。由于子服务器的功能与主服务器类似,所以子服务器可以重用主服务器的OTA服务代码。该方案解决了镜像数据在网络路径上重复传输的问题,即数据冗余问题。与原始方法相比,本文提出的方案大大减少OTA客户端向OTA主服务器发送镜像请求的数量,从而减少OTA主服务器的工作量。

2.2 时延优化方案

延时就是设备到设备之间完成数据传送所用的时间。在CSMA/CA算法中,后退次数(number of back,NB)：当设备有数据要传送时,发送CCA检测,若检测到信道忙,则会再一次产生倒退时间,此时NB值会加1。后退指数(backoff exponent,BE)：决定节点进行CCA之前随机退避窗口的取值。取值范围由min(min BE,max BE)决定,考虑到BE最小值可以自由变动,如果减小BE值将会缩短退避范围；反之，等待时间可能会增加。本文的改进思路是对min BE和max BE值进行自适应调整[8],提出一种结合网络节点数据传输情况的改进型MAC层BE修改方案。

3 非时隙CSMA/CA算法改进

3.1 算法改进

为了实现对min BE和max BE进行自适应调整,在改进算法中设max_backoff为最大的退避指数[9]。为了实现根据冲突次数而动态改变退避上限自适应变化值,添加一个变量abackoff。

1)若上一次尝试传输的次数大于当前的abackoff,则将退避上限值增加到min{max_backoff,abackoff×2}。

2)若上一次尝试传输的次数小于当前的abackoff,则将退避上限值减少到min{max_backoff/2,abackoff-1}。

这种退避上限值的方法,可以减少在轻负载或者小的网络中的退避时间。

3.2 基于马尔可夫链的CSMA/CA改进算法分析

假设有n台设备竞争信道,每台设备1次只有1个数据包,数据包发送后,若MAC子层没有收到正确应答则重新发送数据,直到收到正确应答。

根据非时隙CSMA/CA机制流程,其马尔可夫过程的状态转移如图2所示。图中每个圈代表1个状态,Tx代表发送状态,其他常量变量定义如下：idle为发送后设备处于空闲的状态；(i,j)为节点进入退避算法后的退避计数状态；s(t)和b(t)分别为i,j的状态。Pidle为数据包到达MAC层的概率；PTx为数据包发送等待的概率；α为执行第一次CCA时信道为忙的概率；β为执行第一次CCA时信道空闲的前提下,第二次执行CCA时信道忙的概率；Wi为第i次退避时的窗口；s(t)为退避次数计数值,其取值范围为[-1,Wi-1],当s(t)=-1时,代表第一次执行CCA时信道为空的概率；b(t)为随机退避时,退避周期计数值。πi,j为处于(i,j) 状态的稳态概率,定义为πi,j=limP(s(t)=i,b(t)=j)。

根据IEEE 802.15.4的定义当j≤N时,Wj=2jW0,当j>N时,Wj=WN(W0=2BE),那么当有2个CCA检时计数器就减少到0。则在t时刻可以定义函数π(t)

(1)

则π(t)是图3所构建的具有单步转移概率分布的离散马尔可夫链。

图2 非时隙CSMA/CA马尔可夫链

根据以上条件可将概率α,β和数据传送成功的概率Ps用πi,j,πTx,πidle表示。因为一个在执行CCA1的空闲概率1-α等于其他n-1个处于除Tx状态之外的状态时的概率。所以α可以表示为

α=1-(1-πTx)n-1

(2)

β为一个条件概率,其要求在CCA1时信道是空闲的条件下CCA2信道是忙状态,即

(3)

数据传送成功的概率PS为2次CCA信道均空闲条件下数据发送成功,可用式(4)计算

(4)

根据上面定义和马尔可夫链规则,在该马尔可夫链模型中πi,j,πTx,πidle公式可以表示如下

若1≤i≤M,则

πi,0=(α+β-αβ)iπ0,0

(5)

若0≤i≤M,则

πi,-1=(1-α)πi,0

(6)

若0≤i≤M,则

π0,i=π0,0-((1-PTs)(1-Ps))πi,0Tx+

(1-Pidleπidle)

(7)

若1≤i≤M,1≤j≤Wi-1,则

(8)

(9)

(10)

在这个马尔可夫链模型中所有稳态概率都能由π0,0表示。由以上公式,可以计算出一个数据包发送的平均延时。

4 算法仿真验证与结果分析

仿真实验所采取的模式是遵循IEEE 802.15.4 MAC层所定义的非时隙CSMA/CA算法为基础设计的。网络模型参数设置如表1。

表1 网络模型参数

设每个镜像数据分组的长度为b,由OTA服务器送入OTA客户端的总镜像数据到达率为T个/s分组,其中成功接收率为t个/s分组,则总数据量为g=b×T(bit/s),而网络的平均吞吐量为s=b×t(bit/s),若网络容量(最大传输速率)为R(bit/s),则可定义归一化总数据量为G=g/R,归一化吞吐量为S=s/R。由以上定义可看出归一化吞吐量其实就是信道容量利用率。仿真结果如图3所示。

图3 仿真结果

由图3(a)可见,随着G增大,两者的信道利用率也逐渐增大,直至某一点后由于碰撞大量增加而开始下降。在信道流量G=1.5左右时,吞吐量最大值由0.3增加到0.58。可见,在提高网络吞吐量,提高网络的更新效率上,采取了改进算法CSMA_Pro更有优势。

从图3(b)中可以看出,算法改进后的时延比改进前要好的多,由原来的0.029 s减少到现在的0.024 s,最后随着时间的增加趋于一致,并且基本上消除了时延抖动。在IEEE 802.15.4的MAC层中规定所有节点的初始指数BE的默认值在不同网络中不一定是最佳值,而BE变化范围由minBE和maxBE值决定,当该算法的其它参数不变的情况下,这两个值决定退避时隙的范围大小。而改进算法CSMA_Pro实现了根据冲突次数而动态改变退避值上限,从而增大退避时隙(0～2BE-1)的范围,减小数据碰撞的概率,减小网络时延,对网络更新效率有明显提升。

从图4(c)中可以看出算法改进后,网络负载随着时间的增加有了明显增长,当节点的网络负载较小时,竞争信道的节点比较少,数据不易产生冲突,网络传输速率增大。随着仿真时间的增加,发送数据的节点增多,网络负载变大,到了15 s时趋于平稳,增加了1 000 bps。

5 结 论

经过仿真实验,确认本文方法使得网络吞吐量增加,加快网络中镜像程序的传输,同时相比原始网络而言减少时延,从而改善无线传感网络空中下载节点更新效率低的问题。通过对无线传感器中节点镜像程序更新的分析仿真和验证,为进一步改进节点镜像更新性能提供了思路和方法,有利于更好地应用无线传感网络。