无线传感器网络节点基于时间相关性的缓冲管理算法

李 迅,杨稳竞

(国防科技大学机电工程与自动化学院,长沙 410073)

无线传感器网络[1-2]由大量的低成本的节点构成,有着广泛的应用前景[3-4]。在无线传感器网络的应用中,研究主要集中在节点协同[3,5]和能量节约[3]等关键技术上,但在一些应用中,如活动目标跟踪[5],仅考虑这些方面是不够的,还必须考虑感知数据的实时性。无线传感器节点有一定的缓冲空间,可以处理短时间的数据传输过载。但节点主要采用低功耗单片机实现,单片机资源有限,如 MICA系列节点采用了 ATMEL128L[6]AVR单片机,其内存只有有限的 4 kbyte,除数据缓冲外,还要分配一定的空间用于程序运行,因此缓冲资源非常有限。缓冲资源的限制可能造成有用报文的丢失,产生一个极大的时延,即使数据没有丢失,过多地缓冲一些冗余信息数据,也会造成较大的时延。

信息传输延迟由单个节点的延迟累加构成,单个子节点延迟主要由 MAC层的传输延迟和网络层的缓冲延迟构成,是动态变化的。无线传感器网络的 MAC协议分为低占空比协议、基于竞争的协议和基于时间表的协议。其中,基于时间表的协议采用TDMA技术,如文献[7]所述,文献[7]采用分簇结构,簇头为簇内节点分配时槽,发射机和接收机严格遵守时隙的要求,避免在时间上互相重叠,从而避免冲突。对动态目标跟踪这类实时性要求较高的应用,基于时间表的协议可以提供确定性的时延,是一种较好的选择。MAC层采用基于时间表的协议,节点信息传输延迟的动态性由节点缓冲的动态性而体现,尤其对实现转发功能的节点,其缓冲的动态变化更加明显。

传输延迟的影响在文献[8]中进行了详细分析。该文献从时空误差的角度分析了分布式测量跟踪系统中,由于时间传输延迟的存在,使得执行节点获得目标的目标信息产生滞后,而在对目标当前位置进行推测时,由于时间延迟造成推测的空间误差。假定平面坐标系内目标在 t0时刻位置为 →r0,速度为→v0,信息传输延迟为 Tt,则执行节点在 t=t0+Tt得到探测数据,此时目标已移动到位置 →r(t)：

执行节点需要对 t时刻的目标位置进行推测,推测时取目标运动模型为 CV模型[9],则

则推测误差：

从上面可以看到,时间延迟的存在和推测误差的大小密切相关,而且时间延迟的存在也造成了执行节点不能及时响应,这就需要对延迟进行控制。

1 时间相关主动缓冲队列管理算法

在无线传感器网络环境中,节点周期性的感知目标,感知信息存在时间上的相关性[10],时间接近的感知数据,从信息角度看是冗余的。在缓冲队列中,有选择的丢弃冗余的信息,就能够有效地避免丢弃有用的信息,降低有用信息的缓冲延迟时间。当前的缓冲管理采用主动缓冲队列管理,主动缓冲管理算法的研究基本集中在 RED[11]算法及其改进上。RED算法根据平均队列长度和预先设定的阀值以一定的概率主动丢弃分组,这就有效地避免了缓冲区满的情况。在无线传感器网络条件下,单纯以平均队列长度来判定分组的丢弃,不能保证丢弃的是冗余数据。为解决这一问题,下面设计一个基于时间相关判定的主动队列缓冲管理算法 -TRED(Time-based RED)。

无线传感器网络节点用时戳来标识感知信息的时间[12]。记缓冲区中最后到达报文的时戳为 Tlast。推算允许最大延迟时间Tmax,到达数据时戳和 Tlast差如果超过 Tmax,则报文没有意义。将 Tmax划分为Γ(Γ≥1)级,[0,σ)、[σ,2σ)…[(Γ-1)σ,Γσ),报文i时戳为ti,Δti=|Tlast-ti|,则定义报文 i在时间度量上的丢弃概率如下：

从上述定义看,时间相关性越高的报文,报文的丢弃概率越高。

除了时间因素,缓冲管理还必须考虑数据缓冲情况。RED算法设定参数 thmin、thmax分别代表总的缓冲队列的最小和最大阀值。缓冲队列的占用情况用平均队列来表示,当报文 i到达或离开时,平均队列长度按下式计算：

(i＞=1,0≤wq≤1),L(i)为报文 i到达或离开时缓冲队列长度,分别计算如下：

这里,P(i)为到达或离开的报文的长度,平均队列长度、缓冲队列长度和报文长度均按照字节为单位计算。报文 i丢弃概率如下：

上式中,Pmax为一个相对较小的值,控制报文的丢弃概率。综合缓冲队列长度和时间相关性,报文 i最终丢弃概率：

TRED算法可以实现基于时间和缓冲队列长度判定的缓冲管理,时间相关因子的引入保证了时间相关性大的数据其丢弃概率要比时间相关性小的数据的丢弃概率高,即 ：∀i,j,如果 Δti≤Δtj＜Tmax,在相同缓冲条件约束下,Pi≥Pj。

2 算法仿真验证

仿真实验假定 5个感知节点向一个转发节点转发数据,拓扑结构如下图。

图1 仿真拓扑结构

在图 1中,节点 1～5周期性感知数据,并将其发送到转发节点 6,其数据产生周期 1ms,MAC层采用 TDMA算法,时槽分配周期 12 ms,每个时槽2 ms,每个时槽可以发送一个完整的报文,并且每个节点的报文长度固定,每个节点发送 50个感知数据。节点 6数据缓冲 2 kbyte。缓冲管理采用 TRED算法,相关参数配置为：thmin=256 B,thmax=1 536 B,w=0.1,Pmax=0.8,Tmax=6ms,Γ=5,则时间相关区间分别为 [0.0,1.2)、[1.2,2.4)、[2.4,3.6)、[3.6,4.8)、[4.8,6.0)。节点探测到目标的起始时间分别为：(t0+0)ms,(t0+1)ms,(t0+3)ms,(t0+6)ms,(t0+10)ms。图 2和图 3显示了在此参数设置下的仿真结果。

图2 不同时间区域丢弃比率

不同节点产生的探测数据在到达转发节点时,其数据可以归于不同的时间相关区间。从仿真结果图 2可以看出,时间区间[0.0,1.2)的报文丢弃最多,而[4.8,6.0)区间在这一情况下报文没有丢弃。这一结果体现了在丢弃概率计算过程时间相关判定因子的作用。图 3给出了时间缓冲队列和平均队列的变化,可以看出平均队列对实际缓冲队列进行了平滑。

图3 实际队列和平均队列

3 结论

无线传感器网络节点,由于连续的探测数据并进行传输,使得同一节点或相近节点产生的数据存在时间上的相关性,数据之间时间相隔越小,数据的时间相关性越强,信息冗余度越高,丢弃时间相关数据,可以有效的降低节点对数据的缓冲延迟。TRED算法通过时间相关判定因子的引入,改进了主动队列缓冲管理算法,在根据平均队列长度丢弃报文时,强化丢弃时间相关的数据报文,这样就能够尽可能丢弃时间相关性越强的数据,即信息冗余的数据,保留汇聚节点进行推断时有用的数据信息,提高了推断的准确性。

[1]Akyidiz I F,Su W,Sankasubramaniam Y,et al.Wireless Sensor Networks：A Survey[J].Computer Networks,2002,38：393-422.

[2]孙立民,李健中,陈渝,等.无线传感器网络[M].北京：清华大学出版社,2005.

[3]ZHAO F,Shin J,Reich J.Information-D riven Dynamic Sensor Collaboration for Tracking Application[J].IEEE Signal Processing Magazine,2002,19(2)：61-62.

[4]Wai-Leong Yeow,Chen-Khong Tham,Wai-ChoongWong.Energy Efficient Multiple Target Tracking Wireless Sensor Networks[J].IEEE Transactions on Vehicular Technology,2007,56(2)：918-928.

[5]王永才.传感器网络目标跟踪系统协同设计理论研究与应用[D].清华大学,2006.

[6]Atmel,8-bit Microcontroller with 128K Bytes In-System Programmable Flash ATmega128/ATmega128L Preliminary[M].Rev 2467J-AVR-12/03.

[7]Arisha K A,Youssef M A,Younis M F.Energy-Aware TDMABASED MAC for Sensor Networks[C]//Proc IEEE Workshop on Integrated Management of Power Aware Communication,Computing and Networking,New York,2002.

[8]Technical report,Sensitivity of Track Accuracy to Navigation,Sensor,and Time Errors Within a Distributed System[R].Joint Single Integrated Air Picture System Engineering Organization Analysis Branch.2004,7.2.6.3_TR(4-002)_1.0_JSSEO_040407.

[9]范小军,刘锋.一种新的机动目标跟踪的多模型算法[J].电子与信息学报,2007,29(3)：532-535.

[10]Vuran C,Akan B,Akyildiz F.Spatio-Temporal Correlation：Theory and Applications for Wireless Sensor Networks[J].Computer Networks,2004,45：245-259.

[11]Lin D,Morris R.Dynam ics of Random Early Detection[J].In Proc of SIGCOMM,Cabbesm France,1997,137-145.

[12]崔逊学,左从菊.无线传感器网络简明教程[M].北京：清华大学出版社,2009.