满足业务实时性要求的路由设计*

侯 华,任艳娜,周武旸

(1.河北工程大学信息与电气工程学院,河北 邯郸 056038;2.中国科学技术大学电子工程与信息科学系,合肥 23000)



满足业务实时性要求的路由设计*

侯 华1*,任艳娜1,周武旸2

(1.河北工程大学信息与电气工程学院,河北 邯郸 056038;2.中国科学技术大学电子工程与信息科学系,合肥 23000)

针对无线传感器网络数据传输实时性问题,基于非均匀分簇网络模型提出了一种路由方法。其主要思想是为收集的数据设定截止期,通过链路时延估计,综合考虑截止期和链路时延等影响接收端接收数据的有效性的因素,提出了一种可以满足多种业务时延要求的路由方法。仿真实验结果表明,该路由方法能够保证信息的有效性。

无线传感器网络;路由;延迟;截止期错失率;非均匀分簇

随着实时应用需求的逐渐增多,如何在无线传感器网络中为这类业务提供满意的服务受到了越来越广泛的关注。例如,在重病监护室内,患者身上安放的传感器节点会采集该患者身体的血压、体温等数据,并将这些信息实时地传送给监护人员,如果数据显示有异常情况发生,那么监护人员会立即接到相应的报警信息并通过阅读监测信息得知异常数据源的具体情况并及时采取相应的急救措施。实时服务与传统的尽力(Best-Effort)服务模型的区别在于前者对数据包的传输截止期有更为严格的要求。若实时业务的数据包时延超过了截止期,往往代表这部分数据已经失效,而失效数据的传输有可能会带来严重的后果。因此,为了支持逐渐增多的实时应用,在无线传感器网络中提供有保障的服务质量QoS(Quality of Service)显得尤为重要。

1 相关工作

文献[1-4]在非分簇网络中,通过计算转发节点到汇聚节点的距离,将数据的截止期要求转化为相应的传输速率要求,然后选择满足速率要求的节点作为下一跳转发节点,以满足数据的实时性要求,降低数据截止期错失率。由于上述4篇文献均未考虑数据融合技术,因此节点转发数据将消耗较多的能量。文献[5-7]采用非均匀分簇网络模型,将整个网络分为大小不同的簇,路由方法也分为簇内路由和簇间路由两部分。簇内节点将数据转发给其簇首,簇首将采集到的信息进行数据融合后,转发给符合要求的下一跳簇首,通过多跳方式将数据转发给汇聚节点。这种数据转发方法,能降低节点的能量消耗,可惜的是没有考虑到信息的实时性要求,信息截止期错失率较高。文献[8-9]在路由选择时考虑信息的实时性要求,将信息分类为实时性数据和非实时性数据。实时性数据转发时,选择最短路径转发,用以降低数据转发时延。文献[8]中的非实时性数据转发时,综合考虑数据传输的可靠性和能量消耗。而文献[9]中的非实时性数据转发时,则综合考虑邻居节点的剩余能量和缓冲队列占空比,选择总体代价最小的节点作为下一跳转发节点。这类方法可以粗略地将数据分类为实时性数据和非实时性数据,并不能满足多种类型业务中每一种业务的特定时延要求。

本文考虑分簇网络模型下的路由策略。簇首节点首先根据每个数据各自的截止期和估计的链路时延,将信息分批次放入不同的队列中,在各队列的信息被发送出去之前,队列内的信息首先进行数据融合处理。这样做,既可以满足不同信息的实时性要求,又可以降低簇首节点的能量消耗,有利于保障整个系统的稳定性。

2 路由方法设计

本文路由方法的设计目标是满足多业务传输时各类业务的时延要求,降低信息截止期错失率。

2.1 网络拓扑模型

本文采用文献[5]中介绍的非均匀分簇网络模型。

传感器节点部署在均匀间隔的同心圆网络中,Sink节点在网络正中心,圆环间的间隔为δ。若节点i与Sink节点间的近似距离为di,节点i根据di判定自己所在的环k。若di满足如下关系:

(k-1)δ≤di≤kδ

(1)

则表明节点i处于第k环。

在WSN中,节点间发送数据的能耗与跳数和距离相关。若两节点之间的距离为g,由文献[5]可知,g≤87 m时,单跳通信比多跳通信更节省能量,且随着融合率c的增加,单跳通信将比多跳通信节省更多的能量。本文簇内节点采取单跳通信方式,因此将圆环间的间隔δ定为87 m。

各环最优簇首个数由以下公式确定:

(2)

其中,mk是第k环的簇首个数,P是该网络中最大的环数。可见,簇首个数mk与圆环编号k成正比,第k环转发外环数据的能耗由第k环各簇首均衡分担。其中,位于圆环编号为1内的节点直接与汇聚节点通信。

若第k圆环的面积为Sk,把该圆环划分为mk份,则该环内的每个簇首的竞争区域近似为Sk/mk。通过公式:

(3)

竞争半径R随着圆环编号k的增大而减少,形成离Sink节点较近的圆环成簇个数较少、成簇范围较大的非均匀分簇网络。由文献[5]仿真实验验证,建立的非均匀分簇网络可以解决能量空洞问题。

2.2 链路时延估计

(4)

(5)

其中,Packet_size是数据包的尺寸,Ack_size是确认数据的长度,Bandwidth是网络带宽。由式(5)可以看出,网络带宽、确认数据的长度及数据包的尺寸共同决定了Delaytran的大小。

延迟估计器采用TCP协议中的RTT(Round Trip Time)估计法[11-12]:

R←αR+(1-α)M

(6)

(7)

由发送节点获得每个数据包链路延迟测量值M。即发送节点记录发包时间Ts和由ACK包携带的其转发节点收到包的时间Tr。假设ACK包通过一个反向并行的无冲突信道传输,那么Tr和Ts的差可近似作为M的计算值。

2.3 路由方法设计

信息转发包括两部分,第1部分是簇内节点信息的转发,第2部分是簇首节点信息的转发。该部分内容将对两部分信息转发的方法做详细介绍。

2.3.1 簇内信息转发方法设计

在系统中,每一个传感器节点都储存有一个针对于各种类型业务的信息表格,该表格中记录了每一类信息包括截止期在内的各种特征。表格按信息截止期长短对其进行等级划分,截止期越短的信息其等级越高,因为这代表了该数据对实时性的要求越高。

表1 信息表格结构

业务类型占2 bit。用于表示所传输的业务类型,如表2所示。

表2 业务类型域中内容

无线传感器网络中主要是数据的传输,根据具体场合数据传输的实时性要求将实时性要求特别严格的数据业务类型定义为十分紧急;将实时性要求较严格的数据业务类型定义为紧急;将实时性要求不严格的数据业务类型定义为非紧急。

实际的信息截止期是从0到1536 ms,占据11 bit的存储空间。

簇内的每个感知节点按一定的时间间隔采集其感知范围内的信息。节点采集到信息后,将该信息特征与该节点存储的信息等级表的相关内容进行对比,并根据信息等级表设置信息截止期t。即将RTS帧中时延容忍域设为定时器,定时器的值被设置为信息剩余的截止期t,可见t随着时间的推移而递减。RTS帧结构如下:

表3 RTS帧结构

节点之间的通信采用基于竞争的MAC协议,通过RTS/CTS/DATA/ACK的交互方式转发信息。簇首收集的是本簇内所有节点的信息,簇内节点到簇首的链路时延可能会不同。因此,当簇首将本簇内所有节点的信息收集完后,各个节点的信息截止期应变化为t=t-Delaylink max。其中,Delaylink max是一个簇内的所有节点到汇聚节点的链路时延的最大值。簇首节点收集其感知范围内的信息所设定的信息截止期变化,也遵循此规律。

2.3.2 簇首信息的转发方法设计

簇首收集完本簇内节点的信息后,将信息分批、融合发送给汇聚节点。簇首通过计算待转发数据的截止期与簇首到汇聚节点链路的时延差2个数值并将其进行比较,来决定数据发送的批次和时间。若转发数据的截止期与簇首到汇聚节点的链路时延的差大于T,则将该待转发数据定为等待发送数据;反之,将该待转发数据定为立即被发送数据。其中,T是根据实时性数据的时延要求定义的时间间隔。所有的簇首都照此原则选择立即待转发数据,并对其进行数据融合处理。伪代码如下所示:

ifTi>0,i∈{1,2,…,n}

N(1,k)←i,k←k+1

end if

Delaymax←argmax{Delay1,Delay2,…,Delayk-1}

Ti←Ti-Delaymax,i∈N

if(Ti-Delay-link)

Ac=1,M(1,c)←i,c←c+1

else then

Bm=1,Q(1,m)←i,m←m+1

end if

数据分类后,数据转发流程伪代码如下:

ACH=1,BCH=1 then

else then

ACH=1,BCH=0

else then

ACH=0,BCH=1 then

else then

ACH=0,BCH=0

end if

根据数据的截止期将簇首采集的数据分为4类组合:ACH=1,BCH=0,仅有立即转发的数据;ACH=0,BCH=1,全为等待转发的数据;ACH=1,BCH=1,既有立即转发的数据又有等待转发的数据;ACH=0,BCH=0,簇首没有收集到数据。

4种数据类型组合对应的数据转发流程伪代码如下:

caseACH=1,BCH=0

if Channelstate=1 then

Send data to Sink node then

ACH=0,BCH=0

break

else then

t=randn(0,c-1)

backoff t then

return to check the state of channel

end if

caseACH=0,BCH=1

if Channelstate=1 then

Send data to Sink node

BCH=0

break

else then

t=randn(0,m-1)

backoff t then

if(Ti-t)>Ttolerate,i∈Qthen

return to caseACH=0,BCH=1

else then

return to caseACH=1,BCH=1

end if

caseACH=1,BCH=1

if Channelstate=1 then

Send data to Sink then

ACH=0 then

Ti←Ti-twait,i∈Qthen

return to caseACH=0,BCH=1

else then

t←randn(0,c-1)

backoff t

Ti←Ti-t,i∈Mthen

ifTi

discard data then

Tj←Tj-t,j∈Qthen

return to caseACH=0,BCH=1

else then

return to check the state of channel

end if

caseACH=0,BCH=0

break

2.3.3 快速的路由方法设计

本小节是从实际系统运行的角度考虑,主要分析系统解析信息截止期的快慢。

理论上信息截止期是一个具体的数值,如512 ms。在系统中,如果硬件解析512时需要解析9bit的数据,需要很多个时钟周期,势必影响算法的复杂度。在实际的应用系统中,需要简化实际的信息截止期,将信息截止期进行量化,分为若干个区间,系统按信息截止期区间对应的二进制编码进行解析,可以大大缩短解析时间,降低算法复杂度。

表4 x值分段表

参照表4中x值划分的方法将信息截止期0～1536 ms划分为8段,如表5所示。

表5 信息存活时间的量化和编码

由表5可知,信息截止期只占3bit的存储空间,系统解析信息截止期时只需解析3bit的二进制编码,大大降低了算法复杂度,加快了系统的运行速度。

3 仿真及性能分析

本文仿真基于OMNeT++环境,使用NED和C++语言实现网络模型和数据转发方法的仿真,并使用MATLAB软件导出数据,对实验结果进行分析和评估。其中假设采用基于竞争的介质访问控制(MAC,Media Access Control)协议,且忽略无线信道干扰。仿真中εf、节点初始能量E、Ee等参数的取值与文献[14]相同。覆盖区域半径R=400 m,仿真节点个数N=1000、N=2000、N=3000、N=4000。

在传感器网络中,支持实时性QoS要求满足截止期错失率在可以容忍的范围内。严格来说,硬实时应用要求所有的包都满足截止期要求,而软实时应用要求满足截止期的包达到一定的比例。本文路由设计的目标就是尽力提高这一比例,使更多的数据包在截止期内转发给汇聚节点,以满足信息的实时性要求,保证数据的有效性。

为简单起见,本文仿真主要将簇头收集的数据分为两批转发给汇聚节点。根据信息的截止期将实时性要求较高的数据定义为第1批转发数据,且在合适的时间转发给汇聚节点。实时性要求不高的数据,等待第1批数据转发完毕,在合适的时间将数据转发给汇聚节点。

图1 全部数据的截止期错失率比较

图1对比了在节点个数不同时,文献[5]采用的路由方法和本文所采用的路由方法及文献[9]采用的路由方法DGEER(Delay-Guaranteed Energy-Efficient Routing)在信息截止期错失率方面的差异。其中,图例中的“本文”表示采用实际的信息截止期,“快速的路由方法”表示采用量化的信息截止期。由图1可以看出,采用本文的快速路由方法与非快速路由方法时,信息截止期错失率基本无差异。由2.3.3小节分析可知,采用量化的信息截止期可以大大降低算法复杂度,故实际系统中应采用量化的信息截止期。且由图1可以看出,采用本文所提的路由方法时,信息截止期错失率明显比采用文献[5]的路由方法及采用DGEER时低,且随着节点个数的增多,本文所提算法的信息截止期错失率增长速度比较慢,这说明本文所提算法可以更好地满足信息的实时性要求,保证信息的有效性。主要在于本文在数据转发时采用类似于排队的方法,实时性要求越严格的数据在较早的时间转发给汇聚节点。且充分考虑全部信息的实时性要求,尽量在信息的截止期内将数据转发给汇聚节点,保证了数据的实时性传输。

图2是在不同节点数量的情况下,实时性要求较高的数据采用3种路由方法时,信息截止期错失率的比较。通过图可以看出,采用本文提出的路由方法时信息截止期错失率最小,表明其实时性更好。主要是因为本文采用的路由方法在转发实时性要求较高的数据时,综合考虑信息的截止期和链路时延,转发顺序优先于实时性要求不高的数据,尽可能在信息的截止期内将数据转发给汇聚节点,满足信息的实时性要求。通过图2还可以看出采用本文的快速路由方法与非快速路由方法时,信息截止期错失率大小基本相同。

图2 实时性要求较高的数据的截止期错失率比较

图3 实时性要求不高的数据的截止期比较

图3给出了在节点个数不同时,实时性要求不高的数据采用3种路由方法时,信息截止期错失率的对比。通过图3可以看出采用本文的快速路由方法与非快速路由方法相比较,信息截止期错失率差异不明显。图中还可以看出,采用本文提出的路由方法时节点的截止期错失率最小。主要在于本文采用的路由方法综合考虑数据的截止期和簇首到汇聚节点的链路时延,数据在最合适的时间转发出去,可以尽量减少簇首对信道的竞争,在保证实时性数据的实时性要求的同时,也实现了非实时性数据传输的实时性。

4 结束语

本文基于非均匀分簇的无线传感器网络模型,对网络中数据的实时转发方法进行了研究。通过对链路时延的估计,分析簇内信息转发时信息截止期的变化,然后结合信息截止期和链路时延,将簇首收集的信息在合理的时间转发给汇聚节点,提高了信息转发的实时性,保证了信息的有效性。设计的快速信息截止期存储方法,可以大大减小存储空间,缩短系统解析信息截止期的时钟周期,降低算法复杂度。仿真实验表明本文提出的数据转发方法能满足信息的实时性要求,在实时性以及数据的整体有效性上优于文献[5]及DGEER。快速的信息截止期存储设计在数据传输实时性的性能上与实际的信息存活时间基本相同。

本文簇首转发信息采用单跳的通信方式,这样势必会比多跳通信消耗的能量多,下一步的工作是在考虑信息截止期和链路时延的前提下,设计簇首之间通过多跳的方式转发信息的方法,在满足信息实时性要求的同时降低能量的消耗。

[1] 李燕君,王智,孙优贤. 传感器网络基于两跳邻居信息的实时路由设计[J]. 软件学报,2009,20(7):1931-1942.

[2]Lin K,Ge H G,Xiong N X,et al. Energy Efficiency QoS Assurance Routing in Wireless Multimedia Sensor Networks[J]. Systems Journal,IEEE,2011,5(4):495-505.

[3]Deng X,Yang Y Y. Online Adaptive Compression in Delay Sensitive Wireless Sensor Networks[J]. IEEE Transactions on Computer,2012,61(10):1429-1442.

[4]Deng X,Yang Y Y. Communicati on Synchronization in Cluster-Based Sensor Networks for Cyber-Physical Systems[J]. IEEE Transactions on Emerging Topics in Computing,2013,1(1):98-110.

[5]侯华,刘超,周武旸. 能量高效均衡的动态分簇路由设计[J]. 北京邮电大学学报,2013,36(3):54-59.

[6]乔学工,王哲,王华倩,等. 基于权值的非均匀分簇路由算法[J]. 传感技术学报,2014,27(1):107-112.

[7]蒋畅江,石为人,唐贤伦. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报,2012,23(5):1222-1232.

[8]Alam R,Abdur M. Energy-Aware QoS Provisioning for Wireless Sensor Networks:Analysis and Protocol[J]. Journal of Choong Seon Communications and Networks,2009,11(4):390-405.

[9]梁庆伟,姚道远,巩思亮. 一种保障时延能量高效的无线传感器网络路由协议[J]. 西安交通大学学报,2012,46(6):48-52.

[10]李燕君,王智,孙优贤. 无线传感器网络的链路分析与建模[J]. 传感技术学报,2007,20(8):1846-1851.

[11]Chipara O,He Z,Guo L X,et al. Real-Time Power-Aware Routing in Sensor Networks[J]. 14th IEEE International Workshop on Quality of Service,2006:83-92.

[12]Rajendran V,Obraczkal K,Garcia-Luna-Aceves J J. Energy Efficient Collision Free Medium Access Control for Wireless Sensor Networks[J]. Wireless Networks,2006,12(1):63-78.

[13]樊昌信,张甫翊,徐炳祥,等. 通信原理[M]. 北京:国防工业出版社,2001.

[14]Mao S,Zhao C L,Zheng Z,et al. An Improved Fuzzy Unequal Clustering Algorithm for Wireless Sensor Network[J]. Mobile Networks and Applications,2012,11(6):45-250.

侯华(1980-),女,博士,副教授,研究生导师,2003年毕业于西南科技大学电子信息工程专业,2008年获中国科学技术大学通信与信息系统专业博士学位,现任教于河北工程大学,研究方向为移动通信技术、认知无线电技术、无线传感器网络,hbhouhua@163.com;

任艳娜(1987-),女,硕士研究生,现就读于河北工程大学信息与电气工程学院,研究方向为无线传感器网络;

周武旸(1972-),男,中国科学技术大学电子工程与信息科学系教授、博士生导师。1993年和1996年在西安电子科技大学获学士和硕士学位,2000年在中国科学技术大学获博士学位。研究方向为中继与协作通信、无线资源管理、无线组网技术。

DesignofRoutingBasedonMeetingServiceReal-TimeRequirements*

HOUHua1*,RENYanna1,ZHOUWuyang2

(1.School of Information and Electrical Engineering,Hebei University of Engineering,Handan Hebei 056038,China;2.Department of Electronic Engineering and Information Science,University of Science and Technology of China,Hefei 23000,China)

For wireless sensor networks of real-time data transmission phenomenon,a new routing method is proposed based on the uneven cluster network model. Through setting deadline for collecting data,estimating link delay and considering the factors influencing the validity of receiver’s receiving data such as the deadline of information,link delay,etc,a new routing method fit for multi-service delay requirements is proposed. Simulation results show that the routing method can ensure the validity of the information.

wireless sensor network;routing;delay;deadline miss ratio;uneven clustering

项目来源:河北省自然科学基金项目(F2012402046);河北省高等学校科学技术研究重点项目(ZH2011222)

2014-04-03修改日期:2014-07-12

10.3969/j.issn.1004-1699.2014.09.021

TP393

:A

:1004-1699(2014)09-1275-06