《1 引言》

1 引言

因特网中采用移动IP协议[1]支持主机的移动,但移动IP缺乏快速的移动切换支持,切换时会引起较多的分组丢失,难以满足未来网络和应用的需求。为此提出了层次移动的概念,将移动主机(MH)的移动行为分为宏观移动和微观移动,MH在域间的移动称为宏观移动,由移动IP支持;在域内的移动称为微观移动,由微观移动协议支持。目前提出的微观移动协议有移动IP区域性注册协议(MIP-RR)[2],MMP协议[3],蜂窝IP协议(CIP)[4]和HAWAII协议[5]等。

切换(handoff)是微观移动协议研究的重要内容,它是当MH的位置发生改变时,与其他主机间的当前连接从一个接入点转移到另一个接入点的机制和过程,切换对移动网络的性能和服务质量提供具有至关重要的影响。笔者在分析微观移动协议现有切换机制缺点的基础上,提出一种基于移动预测的主动切换机制并进行性能评价。

《2 现有切换机制的缺点》

2 现有切换机制的缺点

通常情况下微观移动协议使用基本切换机制完成切换工作,其过程如下:MH切换时,首先断开与旧基站(BS)的连接,然后与新BS建立连接,并通过新BS发送路径更新报文,更新网络中有关该MH的路由信息。采用基本切换机制,从MH离开旧BS到新路径建立完成这段时间内,发往MH的分组将被错误地发送到MH的旧位置从而引起分组丢失,严重影响应用的性能。

为了改善切换性能,标些协议引人了平滑切换机制。目前采用的平滑切换机制有2类:一是存储转发方法,该方法在路径优化移动IP[6]中提出,并为MIP-RR和HAWAII协议所采用,切换发生后,MH通过新BS向旧BS发送通知报文,告知MH已移动,旧BS缓存最近收到的发往MH的分组,并通过新BS转发给MH,从而减少切换时的分组丢失;二是预先注册方法,MMP协议中的预先注册和CIP协议中的半软切换都属于预先注册方法,它利用在某些无线网络中一段时间内MH能同时与2个或多个BS通信的特点,在切换发生前通过新BS发送控制报文预先建立新路径,当切换真正发生时发往MH的分组已经到达新BS。研究表明,使用存储转发方法切换时分组所遭受的额外时延较大,影响实时应用,甚至不能满足实时的需要,而预先注册方法只能在特定的无线网络中使用,缺乏通用性,因此需要研究新的切换机制。

《3 基于移动预测的主动切换机制》

3 基于移动预测的主动切换机制

主动切换机制与预先注册平滑切换机制思想类似,也是试图在切换真正发生前为MH预先建立新路径,等到切换发生后MH可以立即通过新BS收发数据;不过不同于预先注册方法中利用某些无线网络中MH在一段时间内能同时通过2个或多个BS收发数据的特性,主动切换机制使用基于移动预测的方法预测MH将要切换的下一蜂窝以及切换发生的时刻,并通过精心设计的协议交互完成新路径的建立。

《3.1 SBPA移动预测算法》

3.1 SBPA移动预测算法

移动预测是指根据MH的移动历史信息、当前状态信息以及一些外在约束信息预测MH的未来状态,移动预测技术一般应用于移动网络的移动管理和资源管理等方面[7]。笔者针对主动切换机制的需要提出了一种基于状态的移动顽测算法(SBPA)。SBPA算法根据MH的当前位置、运动速度和运动方向预测MH将要切换的下一蜂窝和切换发生的大致时刻。算法的网络模型如图1所示。蜂窝形状为正六边形(半径为r),每个蜂窝有6个相邻的蜂窝;每个蜂窝中设置一BS,BS位于蜂窝的中央;蜂窝0中BS的位置坐标为(x0,y0);MH当前处于蜂窝0中,其位置坐标为(x,y),运动速度为ν,运动方向为θ。

《图1》

图1 SBPA算法的网络模型

Fig.1 Network model of SBPA algorithm

SBPA算法如图2所示,它由两部分组成,第一部分是周期性估算MH在当前蜂窝的剩余逗留时间(Step1至Step4),假设MH的当前运动速度ν和运动方向θ在一段时间内保持不变或变化很小,当MH运动到与当前蜂窝的BS距离为r时,表明MH正离开当前蜂窝,设MH在当前蜂窝的

剩佘逗留时间为Td,则有

\(r=\sqrt{\left(x+v T_{\mathrm{d}} \cos \theta-x_{0}\right)^{2}+\left(y+v T_{\mathrm{d}} \sin \theta-y_{0}\right)^{2}}\)    (1)

由式(1)可以求出T的值为

\(\begin{array}{l}T_{\mathrm{d}}=\frac{-\left[\cos \theta\left(x-x_{0}\right)+\sin \theta\left(y-y_{0}\right)\right]}{v}+ \\\frac{\sqrt{r^{2}-\left[\cos \theta\left(y-y_{0}\right)-\sin \theta\left(x-x_{0}\right)\right]^{2}}}{v}\end{array}\)  (2)

《图2》

图2 SBPA移动预测算法

Fig.2 SBPA mobility prediction algorithm

算法的第二部分是下一蜂窝预测(Step6至Step12),首先根据几何关系求出MH的当前位置与所在蜂窝各顶点之间的距离矢量角θ1,θ2,θ3,θ4,θ5和θ5(图1b),再根据MH的当前运动方向θ与θ(;=1,2,..,6)之间的关系来预测MH将要切换的下一蜂窝(算法中用变量NC表示)。

算法中启动主动切换的时刻是精心选择的,通过Step5设置定时器值为Td-Tabo,其中Td为最新预测的MH在当前蜂窝的剩余逗留时间,Tabo为位算的主动切换时延,如此选择启动主动切换的时刻可以确保预先路径更新完成后立即进行真正的切换。

《3.2 主动切换机制》

3.2 主动切换机制

主动切换机制的协议过程如图3所示,图中GW为网关,CBS为当前BS,PBS为预测的下一蜂窝BS,MRA为移动路由代理,交叉MRA为从CBS至GW与从PBS至GW路径上的最低层公共MRA。

《图3》

图3 主动切换机制的协议过程

Fig.3 Protocol procedure of active hand off mechanism

主动切换机制的协议过程如下

1) MH在当前蜂窝内执行SBPA移动预测算法,预测结果为:在t时刻启动主动切换,MH将要切换到的下一蜂窝为PBS所在蜂窝;

2) 在时刻,MH向CBS发出主动切换通知报文,并且将MH和PBS的地址包含在通知报文中发送给CBS;

3) CBS收到通知报文后,根据报文中的PBS地址将通知报文转发给PBS;

4) PBS收到通知报文后,执行预先路径更新,向GW方向逐层发送预先路径更新报文(包含MH的地址),预先路径更新报文终止于交叉MRA:

5) PBS与交叉MRA之间路径上的MRA(包指交叉MRA)收到预先路径更新报文后在位置数据库中增加MH的临时路由选项(指向下层MRA),临时路由选项与通过正常的路径更新报文建立的正常路由选项相比唯一的区别是设置的超时时间值较小;

6) 当交叉MRA上的临时路由选项建立完毕后,就完成了预先路径更新,这时发往该MH的分组从交叉MRA开始将沿着2条路径(分别通向CBS和PBS)发往MH;

7) 当切换真正发生时,MH根据正常的过程执行切换,它通过新BS向GW方向发送路径更新报文进行路径更新,如果新BS为PBS,表示预测结果正确,MH可以立即从新BS接收分组从而冶少切换时的分组丢失,同时路径更新报文将相关MRA上的临时路由选项刷新为正常路由选项如果新BS与PBS不同,表示预测结果错误,相关

MRA上由预先路径更新报文建立起来的临时路由选项将在较短时间内由于超时被删除,不影响协议的其他操作。

《3.3 分组丢失和重复避免》

3.3 分组丢失和重复避免

在主动切换过程中由于MH的当前路径与预测新路径之间的分组传输是不同步的,即使在预测结果正确的情况下也会导致少量的分组重复或丢失。如果预测新路径分组传输比当前路径慢,则MH会收到重复分组,如预测新路径分组传输比当前路径快,则部分分组会丢失。

主动切换机制中采用“PBS缓存法“来避免由于当前路径与预测新路径分组传输不同步而引起的分组丢失。在该方法中,每个BS的位置数据库中增加是否缓存的属性列,正常情况下MH的路由选项中该属性为0,表示不需要缓存,直接将分组转发给MH:当PBS收到从CBS发来的主动切换通知报文后,在位置数据库中为MH建立的临时路由选项中将该属性置为1,表示分组在PBS中缓存而不将分组转发给MHi当切换真正发生时,PBS将缓存中的分组转发给MH,同时将PBS位置数据库中MH的临时路由选项刷新为正常路由选项(是否缓存属性置0)。

PBS缓存法中PBS处缓存大小的设置不需要太大,因为缓存分组的目的是弥补当前路径和预测新路径之间分组传输时间的差异,而不是为了缓存所有发往MH的分组,所以后到达PBS的分组可以在缓存中取代先到达分组的位置,从而将先到达分组从缓存中删除,这样也避免了由于缓存而导致MH收到大量重复分组的情况。采用PBS缓存法,只要PBS处缓存不是太小,就可以完全避免切换时分组丢失的情况,当然为了保证分组不丢失就可能导致MH收到一些重复分组,可以同时采用下面介绍的分组重复避免方法解决这一问题。

前面提到,由于当前路径与预测新路径之间分组传输的不同步以及PBS缓存分组都可能导致MH收到重复分组,虽然重复分组可以由上层协议处理,但是重复分组的存在带来了两方面的影响:一是浪费了网络的资源,特别是宝贵的无线带宽资源;二是降低了协议的效率,因为MH收到重复分组会产生重复应答,而某些TCP协议实现将重复应答作为网络拥挤的信号从而减小分组发送速率,因此有必要采取一定的机制来避免产生重复分组。

在IP分组头中存在一个标识域,其本来的作用是在IP分片/重组中作为分组的标识,由于在一次连接(如TCP连接)时间内,具有相同的源和目的地址的每个分组的标识域是唯一的,并且是递增的,所以可以在主动切换机制中利用分组的标识域来避免MH收到重复分组。具体机制如下:在MH中设置一定的缓存来存放最后收到分组的〈源地址,标识〉对,每个缓存占6B,所需缓存的数目取决于同时与MH进行通信的主机数目;当切换发生时,MH将这些缓存的〈源地址,标识〉对包含在路径更新报文中发送给新BS,在预测结果正确的情况下,新BS已经缓存了最近收到的发往MH的分组,在转发这些分组前,将分组头中标识域的值与MH发来的对应〈源地址,标识〉对的标识值进行比较,如果前者大则将分组转发给MH,如果后者大表明MH已经接收到该分组所以不再转发,这样就可以避免MH收到重复分组;如果预测结果错误,新BS将忽略这些〈源地址,标识〉对。

《4 主动切换机制的性能评价》

4 主动切换机制的性能评价

《4.1 网络模型》

4.1 网络模型

性能评价基于如下的网络模型,无线访问网络由多个管理域构成,每个管理域通过GW与因特网相连。在管理域内部,以一个蜂窝(第0层蜂窝)为中心向四周发散,依次为第1层,第2层,…,第1层蜂窝数目为5,第i+1层(i=1,2,…)蜂窝数目是第i层蜂窝数目的2倍;每个蜂窝与5个蜂窝相邻,第0层蜂窝与5个第1层蜂窝相邻,第i层(i=1,2,…)蜂窝分别与1个第i-1层、2个第;层和2个第i+1层蜂窝相邻。每个蜂窝中设置一BS,它同时具有MRA的功能,其中处于第0层蜂窝的BS作为整个管理域的GW,所有相邻的BS间通过有线链路连接,它们之间的距离为一跳。管理域内部的网络结构如图4所示。

设一个管理域有R+1层蜂窝,这里R代表了管理域的大小,将它定义为管理域的半径。第;层蜂窝到GW的阶离为5,其数目为

\(N_{i}=\left\{\begin{array}{cc}1 & i=0 \\5 \times 2^{i-1} & i=1,2, \cdots, R\end{array}\right.\)   (3)

因此管理域中蜂窝的总数为\(N=\sum_{i=0}^{R} N_{i}=5 \times 2^{R}-4\)

《图4》

图4 管理域网络结构

Fig.4 Network architecture of administrator domain

设MH等概率地分布在管理域的各个蜂窝中,则MH处于第i层蜂窝范围内的概率为\(p_{i}=N_{i} / N(i=1,2, \cdots, R)\)(5)于是可以计算出MH所在蜂窝与GW之间的平均距离为n

\(D=E[i]=\sum_{i=0}^{R} i p_{i}=5\left[(R-1) 2^{R}+1\right] / N\)  (6)

设MH处于随机移动模式,它向相邻的5个

蜂窝的切换概率相等,则MH从第i层(i=1,2,....., R)蜂窝切换到第j层蜂窝的概率为

\(p_{i, j}=\left\{\begin{array}{cc}1 / 5 & j=i-1, \\2 / 5 & j=i, \\2 / 5 & j=i+1, \\0 & \text { 其他 }\end{array}\right.\)   (7)

《4.2 额外信令开销》

4.2 额外信令开销

使用主动切换机制时,需要发送主动切换通知报文和预先路径更新报文进行预先路径更新,给网络带来了一定的额外信令开销(常规移动管理信令开销之外的开销)。

设信令报文在管理域内有线链路上传输产生的信令开销为报文大小(以字节计)与链路距离(以跳计)之乘积(单位为“跳.B“),在无线链路上传输产生的信令开销为报文大小与链路旺离乘积的α倍(由于无线链路的带宽资源有限),设主动切换通知报文和预先路径更新报文的大小分别为RI和Ru,切换频率为F。另外假设切换前MH处于管理域的第i层蜂窝(i=1,2,…,R-1),MH预测发生切换的3种情况为向第i-1层,第i+1层和第ii层切换,各种情况的切换概率由式(7)描述。

在预测MH由第i层蜂窝向第i-1层蜂窝切换的情况下,交叉MRA为PBS,MH经过CBS向PBS发送主动切换通知报文,不需要发送预先路径更新报文,这种情况下主动切换的额外信令开销为\(C_{(i, i-1)}=(\alpha+1) R_{1} F\)(8)在预测MH由第;层蜂窝向第i+1层蜂窝切换的情况下,交叉MRA为CBS,MH经过CBS向PBS发送主动切换通知报文,PBS向CBS发送预先路径更新报文,故这种情况下主动切换的额外信令开销为\(C_{(i, i+1)}=(\alpha+1) R_{\mathrm{I}} F+R_{\mathrm{U}} F\)(9)在预测MH由第i层蜂窝向第i层蜂窝切换的情况下,设交叉MRA为处于第j层(j=i-1,i-2,......,0)蜂窝的BS,这种情况下MH经过CBS向PBS发送主动切换通知报文,PBS向交叉MRA逐层发送预先路径更新报文,这种情况下主动切换的额外信令开销为\(C_{(i, i) j}=(\alpha+1) R_{\mathrm{I}} F+(i-j) R_{\mathrm{U}} F\)(10)由管理域的网络结构可以求出交叉MRA处于第j层蜂窝的概率为

\(p(i, i) j=\left\{\begin{array}{lc}1 / 2^{i-1} & j=0 \\1 / 2^{i-j} & j=1,2, \cdots, i-1\end{array}\right.\)   (11)

由式(10)和式(11)可以求出在预测MH由第i层蜂窝向第;层蜂窝切换的情况下主动切换的额外信令开销为

\(\begin{array}{c}C_{(i, i)}=\sum_{j=0}^{i-1} C_{(i, i) j} p_{(i, i) j}= \\(\alpha+1) R_{1} F+2\left(1-1 / 2^{i}\right) R_{U} F\end{array}\)    (12)

由式(7)至式(9)和式(12)可以求出当MH处于管理域的第i层蜂窝时主动切换的额外信令开销为

\(\begin{array}{l}C_{(i)}=\frac{1}{5} C_{(i, i-1)}+\frac{2}{5} C_{(i, i+1)}+\frac{2}{5} C_{(i, i)}= \\(\alpha+1) R_{1} F+\left[6 / 5-4 /\left(5 \times 2^{i}\right)\right] R_{\mathrm{U}} F\end{array}\)    (13)

在式(13)中,将;用MH所在蜂窝与GW之间的平均距离D取代,并取a=2,F=0.25次/s,所有的信令报文大小均为60B,计算主动切换的额外信令开销的平均值随管理域半径R的变化,计算结果如图5所示。同时还计算了相同环境下MIP-RR,MMP,CIP和HAWAII协议切换时给网络带来的平均常规信令开销。

从图5中可以观察到,随着管理域半径R的

《图5》

图5 主动切换机制的额外信令开销

Fig.5 Additional signal overhead of active handoff mechanism

增大,尽管各协议的平均常规信令开销的平均值不断增大,但是主动切换机制的额外信令开销的平均值却变化不大。在管理域半径为2时,主动切换机制的额外信令开销为各协议的平均常规信令开销的24%左右;在管理域半径为7时,这一数值降为14%。这表明采用主动切换机制只给网络增加了少量的额外信令开销,并东不随管理域范围的增大而增大。

《4.3 切换性能》

4.3 切换性能

与其他切换机制一样,可以用切换时的分组丢失、切换时分组所遭受的额外时延以及应用层的吞吐量等指标来衡量主动切换机制的切换性能。主动切换机制利用移动预测技术,在预测结果正确的情况下,MH真正切换到新BS时可以立即从新BS接收分组,减少了切换时的分组丢失,在采用“PBS缓存法“的情况下典至可以达到零分组丢失。切换时分组可能遭受的最大额外时延为分组在PBS的缓存时间,不会对实时应用的性能造成影响。

但是任何移动预测算法的预测准确性都不可能达到100%,上述的分析结果在理想情况下才能达到,下面通过仿真的方法研究移动预测算法的预测准确性对主动切换机制性能的影响。仿真基于离敬事件仿真器NS2(V2.1b7)[8],所用的网络拓扑见图4所示的拓扑(取R=3),并让MH只在第3层蜂窝之间移动,在相邻蜂窝的交界处发生切换。将主动切换机制与CIP协议结合在一起并在仿真软件中实现,仿真结果与CIP协议的硬切换机制和半软切换机制进行比较,仿真中的“预测准确率“由程序设定。

首先考察预测准确性对切换时分组丢失的影响,仿真中从CH向MH发送UDP分组(CBR流量),分组的平均大小为200B,分组的发送速率为50分组/s,其他参数取值如下:MH的切换频率为15次/min,BS广播公告报文的周期为100ms,每跳链路时延在1~35ms之间变化。分别仿真了主动切换机制在预测准确率为50%、70%和90%情况下切换时的分组丢失随链路时延的变化,实验4min(发生60次切换)所得结果的平均值如图6所示。

《图6》

图6 切换时的分组丢失

Fig.6 Packet loss at handoff

从图6中可以观察到,随着移动预测算法预测准确率的增大,主动切换机制切换时的分组丢失数逐深减少,当预测准确率达到90%时,主动切换机制切换时的分组丢失接近于零。在正常的链路环境下(每跳链路时延10ms),只要预测准确率达到70%,切换时的平均分组丢失就能控制在1分组以下,完全能够满足音频等实时应用的需要。

对于非实时应用,考察预测准确性对应用吞召量的影响,仿真中MH利用FTP协议从CH下载64MB大小的文件,TCP报文大小为1024B,MH的切换频率在0一40次/min之间变化,每跳链路时延为10ms,其他参数吟上。分别仿真了采用主动切换机制在预测准确率为50%、70%和90%情况下,及采用硬切换机制和半软切换机制时上述应用的吞吐量,仿真结果如图7所示。

从图7中可以观察到,随着移动预测算法预测准确率的增大,采用主动切换机制时应用层吞吐量随MH切换频率增大而下降的幅度逐渐减少。随着MH切换频率的增大,采用半软切换机制时应用层吞吐量几乎没有下降(由于半软切换切换时分组丢失几乎为零),而当预测准确率达到90%时采用主动切换机制时应用层吞吐量的变化曲线接近

《图7》

图7 应用层吞吐量

Fig.7 Throughput of application layer

于采用半软切换机制的情况。当切换频率为10次/min时,采用主动切换机制(准确率为70%和50%)和硬切换机制时的应用层吞吐量分别为最大吞吐量的95%,90%和83%左右;而当切换频率达到30次/min时,相应的吞吐量为最大吞吐量的88%,76%和60%左右。

从上述额外信令开销分析和切换性能仿真结果可以得出如下结论:主动切换机制以相对较小的代价获得了可观的性能改善。

5 结语

针对微观移动协议现有切换机制的缺点,提出了一种基于移动预测的主动切换机制,为了保证主动切换机制的实现,还提出了一个适用于主动切换机制并易于实现的移动预测算法一一SBPA算法,同时还提出了主动切换过程中分组丢失和重复避免方法,最后对主动切换机制进行了性能评价,结果表明主动切换机制以相对较小的代价获得了可观的性能改善。

预测准确性对主动切换机制的性能有很大影响,如何提高预测的准确性是下一步的研究重点。研究工作将从两方面进行:一是改进移动预测算法,包括调整算法中有关参数的值,充分利用移动历史信息和外在约束信息以及对用户的实际移动行为进行精确建模等;二是将主动切换机制推广到更一般的情况,文中仅为MH预先建立了一条新路径,可以推广到根据具体的环境为其建立多条新路径,当然这样会增加相应的开销,需要进行折衷考虑。