基于位置信息的仓储容迟网络路由算法

仓储物联网络需要满足出入库、盘点数据等准实时性需求[1],有海量数据传输和苛刻的时限要求。金属制的集装箱、仓库层板对信号的屏蔽性较强,难以保证网络连通性,移动IP、NEMO[2]、SIP等基于网络连通性的移动网络接入方案在此种环境下性能不佳[3]。容迟网络(delay toleran network,DTN)协议可以使用渡轮(ferry)收集和上传数据,从而避免盲区,解决了这一问题。目前,有关DTN渡轮的研究不少[4],但一般只考虑计划性移动,没考虑时间的概率不确定性,而时间的概率不确定性会导致所有基于路径可预测的先验知识的计算复杂[5]。

若以空间函数表示该先验知识,则路径可预测条件下移动网络空间的路由在每一点都是确定的,从而避免引入时间的概率不确定性,可以将DTN的路由问题转化为资源分配问题[6],而资源分配问题在2010年底已经解决[7]。本文先以接入基站参数矩阵计算先验知识的空间函数,引入广义k任播(k-anycast)以缓解仓储网络共用的公共Internet资源接入流量爆炸问题,最终使用效用最大化模型为满足广义k任播条件的接入路由器(AR)集合分配带宽资源。从一般只考虑某一时刻的路由和资源分配,转而考虑在整个许可空间上对一组路由器进行路由和资源分配,可以实现在仓储网络的多处对多个目的地传送数据分组,加大了带宽;由于路径增加,还增加了路由的顽健性。

根据渡轮计划性移动可建立基于时空变化的接入基站参数矩阵[8]。一般把链路容量函数表达为一个通用的带宽函数B(t),本文进一步表示为渡轮位置(x,y)的函数B(t(x,y))。由于渡轮接入网络的期望带宽与时间无关,只与地点有关,因此可直接用B(k)=B’(x,y)表示。如果已知基站k的位置(x0(k),y0(k))和半径R(k),则根据渡轮穿越轨迹与半径的交点,可以求出渡轮开始接入和结束接入的坐标:(xs(k),ys(k))和(xf(k),yf(k))。将先验知识直接表示为接入基站k的信息,即矩阵R=(AP1,AP2,…,APk,…,APn),其中APk=(a(k),B(k),xs(k),ys(k),(xf(k),yf(k))T,a(k)为接入基站识别号。为简化问题,将仓储移动网络AR所辖AP或基站范围看作AR范围,考虑接入公平性,在覆盖半径R(k)内可以认为B’(x,y)=B(k),有:

这样,计算渡轮相关链路容量时只需考虑地点位置变化,矩阵R事先算出,与拓扑结构有关,与时间无关。除非网络变更等拓扑结构变化,不然无需维护和更新,因此开销不大,而且实时性计算要求不高。对于渡轮而言,拓扑结构的变化是由自身引起的,如果空间路线固定,则只需要计算一次,存入表中以备索引。如要估计下一个AR的接入时间,只要广播渡轮当前位置P(x,y)和当前车载网络速度V即可,沿途AR据此进行修改。广播的更新周期T应小于接入路由器未覆盖的最小间距与渡轮最大移动速度Vmax之比,即:

得到接入基站参数矩阵以后,就可根据覆盖半径确定路由器的k任播候选集。k任播用于发送者与通信组中任意k个成员之间的通信[9],是以某一阈值为界限,访问候选组(集合)中距源主机某一尺度最小或最大的k个成员(1≤k≤n),先在MANET中得到试用,后扩展到无线传感器网络或IPv6等[10]。

在仓储物联网中,对应数据中心形成的k任播的候选集合,其组成是随时间周期性变化的。如果划分得宜,一个时间区段中的候选集合数n(T)要远远小于总数n,则k选播路由的计算量会大为减少。因此要采用广义k任播,并将n重新定义为周期变化的变量n(T)。具体说明如下。

·广义k任播在任意地点或时间,渡轮所面临的候选集合数n(T)已知,可由查表或函数得到。

·成员之间的通信可以同时或者接力,可以根据负载情况或一定函数决定通信量和通信次序;分配的资源可以是部分的也可以是整份的;多个目的地的信息分组合并后大于或等于一份完整的信息。

·根据距离、时延、跳数等不同的尺度距离(本文使用效用来综合度量服务QoS,这一尺度随需求变化)选取其中k个成员(1≤k≤n),一般是最大或者最小的前几个;组中成员的效用函数U满足g(U)≤f(U)≤G(U),g和G分别为最小和最大约束函数;函数f将U转换为恰当的形式,如取U的倒数或负数,则求U的最大值就变为求f(U)的最小值,从而避免最短路径算法可能出现的死循环。

·成员不但接收和响应请求,还能作为代理获得带宽、时延等服务参数,以计算和分配资源;并自动查找满足效用最大化条件的成员,协作提供服务。对于DTN来说,成员接受群元组,实现群元组到名元组的转换,名元组作为群元组的成员加入广义k任播集,实现模糊匹配,响应同一个任播地址。

由上可知,广义k任播不同于多播,多个目的地的信息分组不一定重复;不同于任播,可以传递到多个目的地;不同于k任播,n(T)随时间变化而且资源可以部分分配传输。在DTN覆盖层上使用k任播,可以避免路由聚合问题,目的地址也不受限于路由器;可以对任播进行改造,使之可同时进行选定节点的传输;不需要在IP层的路由器上增加功能。因此,广义k任播不但适用于IPv6,还可以支持IPv4。

目前先验知识已知的DTN路由算法主要通过修改Dijkstra或Ford算法中的路由代价得来[5],如代价在MED中改为平均链接时延,在ED中改为指定时刻的链路时延w(e,t),在EDLQ、EDAQ、LP中是改变代价的函数表示式。本文引入时延中断统一效用函数U(b(i))[7]来综合表示中断、时延、带宽对路由服务满意度的影响:

其中,j为业务种类,对于不同业务,其参数β、α不同;dAVE为平均时延,dT为当前时延;B(i)为请求的传输总量;g(j)表征函数的倾斜系数;b(i)对于实时性业务表示连接i的带宽,对于非实时性业务表示当前传输量,用式(4)计算:

其中,S为移动网络接入路由器的所辖范围,v是渡轮移动速度,下标T表示周期,BT(x,y)就是B’(x,y),计算同式(1),避开了时间参数,消去了时间的对数正态分布。

由于式(3)突出了中断和时延对效用的影响,而仓储物联网以数据为主,对中断和时延的要求没有那么苛刻,更集中关注效用较小时的变化率(这对应着数据的传输带宽),因此本文以U(b(i))的倒数作为代价,可以对效用较小时的变化率做出灵敏反应。

本文以(b(i))作为代价表达式,结合接入基站参数矩阵提出仓储容迟网络路由算法。

将仓储容迟网络抽象为连通图G(V,E),V表示数据中心或路由器的顶点集合,E为包括仓储容迟网络的有线或无线的线路集合,S表示渡轮。具体到边e的代价则为w(e,1/U(b(i))),可描述边e随渡轮位置变化而改变的代价权值,L(u)为S到顶点u的最小代价和,从而可得到基于效用的位置DTN路由算法,具体算法如下。

这一算法是针对DTN的束层数据的。由于k任播集合中的元素有限,则算法的时间复杂度与ED一致,都是O(n),所需要的先验知识也没有增加。然而计算中只用到渡轮的位置信息而不是时间,从而避免了时间概率不确定性带来的计算复杂度。

根据DTNrg工作组在dtnrg.org提供的DTN的协议框架和相关实现代码,借用其接纳和控制LTP部分,自行翻译并植入NS2,再添加本文算法,得到本次试验的平台。

设拓扑结构为两个长宽各为100 km的正交十字型道路,以Wi-Fi热区(带宽54 Mbit/s)沿途不完全覆盖。渡轮速度v=350 km/h,每10 km停车1 min采集数据,沿着道路周期性逆时针运行。设带宽3.84 Mbit/s的蜂窝网络普遍存在,各类业务的到达时间服从泊松分布,到达相互独立,请求业务tp精确到0.1 s,参数λ=500。不同的业务组合及占比分别为:0类,物流数据;1类,数据信息,占比75%;2类,交互式通信,占比10%;3类,可变速率业务,占比5%;4类,不变速率业务,占比5%(即通信带宽取固定值12.0 kbit/s[11]);5类,DTN信令,占比5%。

对车辆速度引入随机变量V=ξ+Vmax,ξ服从正态分布,即ξ～N(0.1×Vmax,1)。

截至2012年5月,没有与仓储物联网场景相近的有关移动DTN研究的文献可供比较,只能使用2009年Santiago提出的一种普适性DTN多播算法[12]做对比试验。参考文献[12]中的方案不区分具体业务,下文简称San;而本文方案简称Warehouse,数据点各取10次的平均值。

先从各业务的角度进行对比评价。

Warehouse方案的设计是按参考文献[8]的思想以业务分类决定优先级,牺牲较低类来换取较高类业务的QoS。对于下载总时延,0类业务在业务量超过20 erl时,Warehouse方案要比San方案好,如图1所示。这是因为Warehouse方案针对0类业务的效用函数做了优化,在业务繁忙时可以在k个相关路由器进行多路保管传输,只要局部无线网络的带宽没有消耗完,就可以继续增加流量;而San方案未按效用计算路径,对各类业务不加区分,在时间估计方面也引入误差,从而有可能导致保管传输不能在一次性上传之前完成,此时尽管San方案有足够的带宽,但仍然受制于之前较小的网络业务量。同理,Warehouse方案的分组丢失率较优,仿真结果如图2所示。

1类和2类业务两者与0类业务相差不大,图从略。

3类VBR类业务,其热点快速传输特性对提前上下文切换有帮助,加上限制了视频传输的优先级,从而减少了拥塞的可能,总切换掉话率明显要好,见图3;这两方面对实时性服务的影响刚好相反,相互抵消,因此和San方案相比时延没有多少区别,图从略。在业务量为22～24 erl时,随着业务量的增长,掉话率反而有小幅度的增加,这可能是随机数据中连续通信时间的增加引起的,因为连续的通信量中含中断系数的效用函数,可以判断出中断带来的效用下降程度更大,从而优先保证这一类服务的通信质量。

4类CBR类实时话音通信和5类信令类通信,因为效用函数的系数较大,优先级较高,Warehouse方案的各项指标都优于San方案,如图4、图5所示。从图3～图5还可以看出,在业务量22 erl以下,也就是LAN业务未达到繁忙时期时,掉话率和时延基本保持不变;业务量大于22 erl之后,情况明显变坏。

有效带宽利用率定义为总传输的数据与总流量之比,仿真结果如图6所示。当业务量小于20 erl时,两种方案相差不大,说明DTN束层数据和Warehouse信令虽然增加了部分开销,但占总流量的比例不大;在业务量大于20～22 erl之后,Warehouse方案明显优于San方案,这是因为广义k任播充分利用了不同路线的空闲时段和空闲路段,而这部分空闲时段/路段是一个完整的任务无法利用的。这说明本文方案的引入能够缓解网络阻塞的问题,对于流量爆炸场景的控制较好。

吞吐量之比如图7所示。业务量在16～20 erl区间时,吞吐量相差不大,而在业务量加大到20～22 erl后发生比较剧烈的变化,再加大,由于Warehouse方案本身也受到业务量的影响而降低,两者的差距又再次减小。

综上可见,本文Warehouse方案整体优于San方案。

基于位置信息的仓储容迟网络路由算法计算简单,容易实现,消去了先验知识在仓储移动网络环境下的概率不确定性;广义k任播的引入使得同时对周期性可变路由器集合进行多点传输成为可能,增加了传输路径;使用效用作为路由选择的代价,可以灵活地支持开放式网络拓扑结构的变化,适用于负载繁忙的开放式无线网络。下一步将研究本文Warehouse方案在负载均衡及提高网络顽健性方面的具体效果。