基于链接成本反馈的WiMedia分布式路由协议

何荣毅,王小群,陈楷丰

(山东大学(威海)网络与信息管理中心,山东 威海 264209)

0 概述

近年来,无线通信技术和消费电子的发展,使得在消费电子中的建设网络成为可能,并加速了物联网(Internet of Things,IoT)的快速增长[1-2]。IoT的主要目标是将现实世界中的现有对象或事物与因特网集成,以创建所有对象和机器自动交互的新方法。为向物联网提供更多不同的应用,无线设备须支持比传统无线技术更高的传输速率。超宽带(Ultra Wide Band,UWB)技术是一种应用于高速无线数据传输和长距离定位的无线技术,由于其吞吐量优于Wi-Fi,因此适合于多媒体应用,UWB是市场上出现的较新的无线网络技术,具有高数据速率和低功耗的客观要求,其效率比Wi-Fi高80%～90%[3]。

WiMedia联盟已经为高速WPAN指定了基于UWB的PHY/MAC标准。WPAN的传统标准支持集中式MAC方法并形成微网。在物联网应用中可同时操作微网(SOP),而移动性支持和为同步流提供服务质量(QoS)是核心需求[4-5]。例如,文献[6]为提高WiMedia网络资源的利用率,满足服务速率和服务间隔的要求,提出一种资源分配算法,文献[7]考虑了WiMedia标准中视频流的流量规格和QoS要求,在对最大比特率进行预测的基础上,提出一种估计CBR流和VBR流传输所需资源量的算法,并据此分配资源,文献[8]提出一种考虑信道估计环境的资源预留方案,通过预留大量资源来提高网络性能,文献[9]使用包丢失、吞吐量、平均端到端延迟、平均抖动和路由开销等各种性能指标来评估WiMedia网络路由协议性能。上述算法都是集中式体系结构路由算法,但存在以下问题,首先协调器管理整个微微网,若协调器消失,网络中的设备重新选择新的PNC,浪费了大量的时间和精力,且在协调器的重新选择过程中不能保证QoS,其次当2个或更多微微网彼此重叠时,IEEE 802.15.3协议的效率显著降低(即SOP问题),最后是移动性支持不佳以及扩展WPAN覆盖范围的困难。为解决上述问题,WiMedia MAC协议支持分布式MAC方法,使所有设备具有相同的功能,并提供分布式时间同步方案。此外,WiMedia MAC协议采用分布式体系结构,可消除SOP问题。

近年来,人们针对应用于WiMedia标准的路由协议进行了大量的研究。然而,由于较少考虑信道条件,因此不能为实时应用程序提供完整的QoS。本文设计链接反馈信息元素(IE)结构形式,利用媒体接入时隙的数量和跳数来决定源设备和目的地设备之间的最佳路由。

1 研究背景

1.1 WiMedia标准

WiMedia标准使得所有设备具有相同的功能,并以分布式方式向设备提供诸如信道分配、数据传输和时间同步等功能[10]。WiMedia标准的超帧由信标周期(BP)和数据传输周期(DTP)组成,图1为WiMedia标准的超帧结构。

图1 WiMedia超帧结构

超帧具有固定的时间长度,并且被分成多个时间窗口,称为媒体接入时隙(MAS)。超帧中的MAS数量为256,超帧的长度为65.536 ms。在BP算法中,每个设备选择不与其他设备重叠的信标时隙,并在所选择的信标时隙中广播其信标。因此,为了在没有冲突的情况下广播其信标,所有设备都应该搜索没有被其他设备占用的免费信标时隙。根据多个信息元素,设备可以共享用于网络管理、移动性支持等的各种信息。超帧的起点是信标周期的开始时间,称为信标周期开始时间(BPST)。超帧的其余部分用于传输数据,并且被分成2种类型的MAS块。基于竞争的协议在一个MAS块期间工作,而基于预留的协议在另一个MAS块期间工作。基于竞争的协议称为PCA,对于多个优先级排序的类类似于IEEE 802.11e标准。PCA是基于CSMA/CA的媒体接入,分为4个接入类别(AC),具有不同的优先级,用于异步业务传输。在PCA块中,设备发送属于相应AC的数据帧。

1.2 问题描述

图2给出AODV路由协议的路由选择示例。在图2中,设备A和F超出了通信范围,因此设备A不能直接向设备F发送数据包。然而,由于设备A使用路由协议发现从设备A到设备F的路由路径,因此它可以通过设备B和E向设备F发送数据分组。

图2 AODV协议的路由发现示例

传统AODV路由协议通常能够发现具有最小跳数的路由。因此,它可以选择在源设备和目的地设备之间具有最短路径的路由[11-12]。然而,传统的AODV路由协议不适合基于预约的信道接入方案,并且不考虑用于通信的可用资源和每个链路支持的数据速率。因此,如果所选路由上的中间节点中有低效的可用资源,则整个网络的性能降低。文献[13]为WiMedia标准的DRP提出了新的路由协议,由于它们不考虑链路支持的数据速率,低数据速率的链路会降低网络性能,因此传统的路由协议不能充分利用较高速率的优点。为此,本文提出一个增强的路由协议,通过考虑WiMedia网络中的信道条件来建立有效的路由。

2 链接反馈结构路由协议

本文路由协议可以找到数据速率最高的路由路径,并提出了新的路由发现请求(R-REQ)IE和路由发现响应(R-REP)IE。R-REQ IE包括中间设备的地址、RREQ IE已经通过的链路的成本等。本节在设计链接反馈结构路由协议过程中采用预约机制,提出链接反馈IE结构形式,所有设备都可以获得关于相邻设备使用的链路数据速率的信息,利用源和目的地之间的中间设备计算路由成本以确定最佳路由,并利用媒体接入时隙的数量和跳数来决定源设备和目的地设备之间的最佳路由。

2.1 链路成本和所需资源计算

本文路由协议能够找到由从源到目的地的中间链路支持的具有最高数据速率的路由。源和目的地之间的中间设备通过计算路由成本以确定最佳路由,并且目的地设备选择具有最小链路成本的路由[14-15]。当路由上的设备数量为n时,所选择的路由P表示为P(D1,D2,…,Dn),其中,Dk是路由上的节点。WiMedia标准提供链路反馈IE,其通告关于相邻节点的数据速率和传输功率水平的信息。图3所示为链接反馈IE结构形式。

图3 链接反馈IE结构形式

在图3中,DevAddr字段表示提供反馈的设备的地址。发送功率电平改变字段指示接收方向源设备推荐的发送功率电平的改变,而数据速率字段指示接收方设备向源设备推荐的数据速率。本文提出的路由协议通过考虑链路成本和传输数据包所需的资源来确定路由。设TDRP是发送数据包所需的DRP预留的持续时间,因此得到[16-17]:

(1)

其中,η是链路Li,j的MAC效率,即有效载荷传输的时间比例,PPERij是链路Li,j的相应分组错误率。根据式(2),通过链路Li,j传输数据包所需的MAS数量为[18-19]:

(2)

其中,TMAS是MAS的长度,为256 μs。根据式(3),端到端路由上的所有设备都可以计算所需的端到端数据流时隙数,则MAC效率η可计算如下[20]:

(3)

通过考虑确认(ACK)策略来估计MAC效率η。WiMedia标准提供了无确认(NoACK)、立即确认(Imm-ACK)和块确认(B-ACK)3种ACK策略。No-ACK方案容易受到分组丢失的影响,在Imm-ACK中,每帧在短帧间空间(SIFS)持续时间之后被确认为一个ACK帧,可以提供可靠性。然而,Imm-ACK机制导致确认诸如多媒体流之类的接收业务突发的开销量,在WiMedia标准和IEEE 802.11e标准中已经提出了B-ACK方案,以减轻这种开销。

B-ACK机制允许源设备发送多个帧,并从接收方接收单个确认帧,该确认帧指示接收了哪些帧以及哪些帧需要重传。由于在预留的传输持续时间中仅对所有帧使用一个ACK,因此开销大大降低。因此,可将B-ACK策略应用于本文协议。图4所示为DRP预约块中B-ACK方案的帧事务。

图4 B-ACK策略帧事务示例

总传输时间受链路支持的数据速率的影响,其计算公式如下:

(Nframe-1)×TMISF+2TSIFS+TB-ACK

(4)

其中,Nframe为数据帧号,WHeader和WPSDU分别为WiMedia标准的MAC报头和有效负载的大小,Rmin为WiMedia标准支持的最小数据速率,WPre_S为标准前导码的大小,WPre_B是突发前导码的大小,TMISF和TSIFS是帧间间隔的持续时间,TB-ACK是B-ACK帧的传输时间。TB-ACK可计算为:

TB-ACK=TPre-S+THeader+

(5)

WiMedia标准的数据帧由前导、报头和物理层服务数据单元(PSDU)组成。基于式(4)、式(5),TOverhead和TPSDU可计算为:

TMISF+2TsIFS+TB-ACK

(6)

(7)

链路Li,j的平均PER可计算为:

PPER=1-(1-BBER)8WPSDU

(8)

上述等式意味着路由上的中间设备可以计算传输数据分组所需的MAS数量,计算链路成本以确定最佳路线。总链路成本C是针对路由中的链路计算的数据速率的倒数和,计算公式为:

(9)

其中,n是路径上的链接总数。路由上的所有设备计算链路成本,并在BP中广播包括计算链路成本的RREQ IE。

2.2 路由发现过程

源设备广播包括BP中的RREQ IE的信标帧,以将数据帧发送到超出范围的另一设备。图5给出建议的RREQ IE的格式。在图5中,用户DevAddr字段表示发送RREQ IE的设备的ID。

图5 RREQ IE格式

如果源设备首先广播包括所提RREQ IE的信标帧,则所有者DevAddr字段被设置为源DevAddr字段的值;源DevAddr字段指示首先广播所提RREQ IE设备的地址,Dest DevAddr字段指示目的地设备的地址。服务数据长度字段指示提供服务所需的数据帧长度。

Hop Count字段指示源设备和目的地设备之间的跳数,并且当RREQ IE通过中间节点时,Hop Count字段的值增加1。链接成本文件包含使用式(9)计算的链接成本,DRP分配字段包含关于为多跳通信保留的资源的信息、区域位图和MAS位图的信息。为了便于资源分配,WiMedia标准提出二维超帧结构,将超帧划分为16个区域。每个区域由16个MAS组成,并且对应于16×16超帧矩阵的每个列。图6所示为接收RREQ IE的设备流程。

图6 接收RREQ IE的设备流程

在图6中,首先接收设备接收源设备广播的包括RREQ IE的信标帧,基于接收到的RREQ IE信标帧确定路由目标的DevAddr字段。然后对当前字段的地址与目标DevAddr字段的地址进行对比,如果字段地址不符合,则丢弃该字段RREQ IE信标帧。如果满足字段要求,再判断是否在可用MASs范围内,如果不在范围内则丢弃该字段RREQ IE信标帧。如果满足可用范围条件,则继续执行算法,更新链路消耗,如果目的地设备接收到RREQ IE,则它广播包括所提RREP IE的信标帧。

图7给出所提RREP IE的设备流程。在图7中,源DevAddr字段指示源设备的地址,目标DevAddr字段包含目标设备的地址。用户DevAddr字段指示广播RREP IE的设备地址,而Target DevAddr字段指示已被选择为中继设备的地址。链路Cost字段指示由目的地设备计算的端到端路径的总链路成本。Hop Count字段指示源设备和目标设备之间的跳数。DRP可用位图字段指示关于可用资源的信息,如果相应的MAS可用,则字段中的每个位设置为“1”。如果请求预约的MAS已经被其他设备预约,则字段中的对应位被设置为“0”。如果没有预约冲突,则设备不会更改DRP可用性位图字段的值。

图7 接收RREP IE的设备流程

在图7中,接收RREP IE的设备首先确定目标DevAddr字段。如果目标DevAddr字段的值等于设备的地址,则检查DRP可用位图字段。如果请求资源与设备资源重叠,则创建DRP可用位图字段,否则,设备将用户 DevAddr字段设置为其地址,并选择具有最小链接成本的目标设备,将目标DevAddr字段设置为要向其发送RREP IE的设备的地址。然后,设备广播包括RREP IE的信标帧。如果目标DevAddr字段不等于其地址,则丢弃RREP IE。如果源设备接收到RREP IE,则构建Rconf IE。图8给出了本文Rconf IE格式。

图8 Rconf IE格式

接收RREP IE的源设备将关于保留资源的信息存储到DRP Allocation字段。此外,在将Target DevAddr字段设置为位于路由路径上的下一个设备的地址之后,它将Route Sequence字段设置为1,并广播包括Rconf IE的信标帧,接收Rconf IE的设备确定目标DevAddr字段。如果目标DevAddr字段等于其地址,则将用户DevAddr字段设置为其地址,并将目标DevAddr字段设置为沿路由路径的下一个设备的地址。此外,将DRP分配字段设置为保留资源的信息,并广播包括Rconf IE的信标帧。如果目标DevAddr字段不等于设备的地址,则丢弃接收到的Rconf IE。在广播Rconf IE之后,设备在保留的资源中发送数据帧。

2.3 实例分析

图9为本文路由协议的示例。为简单起见,本文不考虑链路的分组错误率和MAC效率。此外,假设提供服务所需的数据长度是27 KB。

图9 路由协议示例

在图9中,图9(a)显示每个链接支持的数据速率和可用MAS的数量,在图9(b)中,源设备A将包括RREQ IE的信标帧广播到相邻设备B和C,相邻设备B和C在接收到RREQ IE时计算链路成本,设备B计算的链路成本是1/160,设备C计算的链路成本是1/200。图9(c)为设备B和C广播包括新链路成本的RREQ IE(参),设备B接收设备C发送的RREQ IE,并重新计算所接收的RREQ IE的链路成本,即(1/200+1/106.7),由设备B计算的新链路成本大于先前计算的链路成本(1/160)。因此,设备B丢弃从设备C接收的RREQ IE。设备C接收设备B发送的RREQ IE,并重新计算接收的RREQ IE的链路成本,即(1/160+1/106.7),由设备B计算的新链路成本大于先前计算的链路成本(1/200)。因此,设备C也丢弃从设备B接收的RREQ IE。设备E从设备B接收RREQ IE,而设备D从设备B和C接收RREQ IE。设备E在从设备B接收到RREQ IE时计算的链路成本是(1/160+1/106.7),并且由设备D在从设备B接收到RREQ IE时计算的链路成本是(1/160+1/53.3)。

由于设备C的链路成本小于设备B,因此设备D选择设备C作为候选中继设备。在图9(d)中,设备D和E广播RREQ IE。设备E从设备D接收RREQ IE并重新计算链路成本,即(1/200+1/480+1/320)。因为新链路成本小于先前计算的链路成本,所以设备E重新广播包括新链路成本的RREQ IE(见图9(e))。在图9(d)中,设备G从设备E接收RREQ IE,但是它几乎没有足够的资源来传输数据帧,因此,丢弃从设备E接收的RREQ IE。目的地设备F接收具有路由(A、B、E、F)和链路成本(1/160+1/106.7+1/400)、路由的RREQ IE(A、C、D、F)和链路成本(1/200+1/480+1/106.7)、具有路由的RREQ IE(A、C、D、E、F)和链路成本(1/200+1/480+1/320+1/400)。目的地设备F比较所有链路成本并选择具有最小路由的路由,即路由(A、C、D、E、F)。随后,目的地设备F将RREP IE与选择的路由一起发送回源设备A(见图9(f))。源设备A更新其路由表,因此建立从设备A到F的路由(见图9(g))。源设备A广播Rconf IE,包括已建立的路由的信息,当选择的中间设备接收到Rconf IE时,为路由建立预留的资源信息(见图9(h))。之后,路由上的所有设备在保留的MAS中发送数据帧。本文方案发现的路由可以提供比现有路由协议更好的吞吐量。

3 实验结果与分析

3.1 实验设置

使用openWNS模拟器[15]来评估本文方案的性能。openWNS是一个动态事件驱动的仿真平台,包括WiMedia标准的实现。在仿真中,源设备总是向目标设备发送数据帧。WiMedia设备发送的分组有效负载大小为1 024 Byte,源对和目标对之间的业务负载是通过改变每秒的分组数量来生成的。此外,随机地选择源-目的地对作为网络中业务负载,信标帧和ACK帧以53.3 Mb/s的强制速率传输。模拟中使用的参数如表1所示。

表1 仿真参数

此外,考虑具有无线IPTV和个人录像机(PVR)记录相同节目的多媒体应用。在某个时候,用户使用遥控器,命令机顶盒(STB)启动IPTV节目。机顶盒中的PVR同时开始在位于客厅旁边壁橱的无线连接的外部硬盘驱动器上记录相同的程序。设服务提供者的视频源使用实时传输协议(RTP)作为传输生成MPEG-4流,表2显示了业务流的令牌桶TSPEC。

表2 业务流的令牌桶TSPEC特性

在该模拟中,假设所有设备随机分布在100 m×100 m的正方形区域。给定网络拓扑,随机选择源-目标对。将节点的通信半径设为10 m,在仿真中评估了不同信道编码参数对算法性能的影响,包括业务负载、节点数目和信噪比。在本文仿真中,将本文方案与WiMedia标准以及WiMedia网络中的QoS路由协议进行了比较。

3.2 不同业务负载的实验

在不同业务负载下,每50 s添加新的业务流,并且业务流的数量随时间单调地增加。经过一定时间后,计算在整个网络中传输的业务流的数量,并将其总和除以整个网络饱和的业务流的数量,得到的数字被当作网络的平均负载,设备的数量固定在40个。图10为WiMedia标准、QoS路由和本文方案的吞吐量仿真结果。

图10 3种协议的吞吐量仿真结果比较

在轻量业务下(发送的分组数较小情况下),本文算法的端到端吞吐量实验结果非常接近选取的WiMedia标准和QoS路由2种协议。当流量增加时,WiMedia标准的DRP协议的缺点较为明显,其端到端的吞吐量指标下降较多,主要原因是算法的效率低,导致数据传输过程中存在较为严重的数据拥堵问题。而QoS路由协议因为将数据传输服务质量(QoS)作为主要的评价指标,端到端的吞吐量作为QoS路由协议的主要考量指标,其具有相对较优的性能表现。本文协议相对于QoS路由协议的优势在于,本文协议采用了预约机制的链接反馈IE结构形式,这种协议结构的优点在于其可有效避免无效数据的处理,从而节省了网络资源和带宽资源,具有相对较好的数据传输性能表现。因此,所提出的路由协议优于2个传统协议。

图11通过比较WiMedia标准、QoS路由和在各种业务负载下提出的路由协议,显示了平均端到端延迟的仿真结果。在轻流量下,文献[15]提出的QoS路由协议所经历的分组端到端延迟结果与WiMedia标准的结果类似。随着网络流量的增加,本文路由协议逐渐优于WiMedia标准,因为网络中的每个链路变得负载过重,所以WiMedia标准会出现网络拥堵的情形,导致分组延迟情形的增加。而QoS路由协议是一种带宽感知路由,它能够确保在该路径上保留足够的带宽。另外,由于QoS路由协议允许路由路径上的所有设备使用预留的资源无争用地发送数据帧,因此QoS路由协议可以减少拥塞。然而,QoS路由协议只考虑可用资源,选择最短路径,因此它不能获得速率自适应调整,反映在实验结果中就是本文算法在端到端延迟指标上的性能表现要显著优于QoS路由协议。由于本文路由协议考虑了链路质量和每个链路支持的数据速率,因此可以选择数据速率最高的路由路径。因此,本文提出的路由协议优于2个传统协议的端到端延迟性能。

图11 3种协议的端到端延迟仿真结果比较

3.3 能源消耗实验

图12为每个协议中最小剩余能量的比较。本文协议和QoS路由的生命期比WiMedia标准要长,因为它们可以无竞争地发送数据帧。使用WiMedia标准的设备必须与相邻设备进行数据传输。随着网络流量的增加,传输数据帧的争用变得更加激烈,并且增加了冲突造成的数据丢失。因此,在WiMedia标准中,通过争用和冲突进行重传会增加能耗。然而,由于所提出的路由协议和QoS路由协议可以无竞争地发送数据帧,因此它们的性能优于WiMedia标准。然而,QoS路由协议只考虑可用资源,只选择最短路径,无法选择最优的路由路径。本文提出的路由协议考虑了每个链路所支持的数据速率,从而可以选择数据速率最高的路由路径。因此,本文路由协议比传统的2种协议具有更好的节能性能。

图12 最小剩余能量比较

4 结束语

本文提出一种考虑WiMedia网络信道条件的多跳路由协议。该协议通过可用资源与每个链路的数据速率配置多跳通信的最佳路由路径,是一种完全分布式的协议,其不依赖于网络中设备之间的全局时间同步。在网络栈的操作中,MAC层由路由层决定,不需要额外的控制分组建立路由,并提供路由协议来保证实时业务的QoS。仿真结果表明,与传统WiMedia协议相比,本文路由协议可提高分组的传输率,明显改善平均的端到端分组延迟。