一种基于MN移动轨迹预测的MAP选择算法

何志林，王春红，李向丽

(1.运城学院 数学与信息技术学院，山西 运城 044000；2.郑州大学 信息工程学院，河南 郑州 450001)

0 引 言

移动IPv6也称为MIPv6[1]，作为用于将来IP网络中实施管理的一项高效手段，这种技术手段能够实现异构无线接入，从而实现移动主机可以通过不同的网络互相建立联系。不过这种技术所采用的协议仍然有一定的问题，比如在MN的移动速度过高的情况下，HA与CN之间的信息交流比较大，在长距离的时候可能会出现滞后以及数据丢包的弊端。针对这一问题，目前也采取了一定的措施，如MIPv6采用高速的切换[2]或者是采用多个层次HIPv6[3]等。

HMIPv6主要是采用了一种“域”的思想，这种不同的“域”中都会设定一个移动锚点(MAP)作为其中的一个新的实体，其相当于一个区域内的本地代理，主要用途在于将其中的位子变化的过程进行本体化的操作。通过这种手段能够有效降低信号的传输以及信息的切换迟滞，最终减少节点在移动过程中产生的对域外网络的干扰情况。MAP的选择对MN的通信性能影响极大，如果选择不当将会造成MAP负载过重、通信延时增加及丢包率过高等问题。但是，HMIPv6中默认采用的最远MAP选择算法，即选取距离MN跳数最多的MAP进行注册，导致高层MAP负载过重，低层MAP利用率低，使得网络资源利用不合理。尤其是发生宏切换时，由于距离过远会增加通信开销、切换时延及丢包率。

文中主要是在原有的基础上对MN的运动轨迹进行分析，然后实施判定。结合MN移动特征在时间和空间上的相关性、连贯性及可预判性，通过对MN运动轨迹进行预测，提出一种新的基于MN移动轨迹预测的MAP选择算法(TP-MAP)。通过实验表明，TP-MAP算法具有较好的负载分担性能，能够提高网络资源利用率，减少切换时延和丢包率。

1 相关研究

MAP选择算法是当前国内外都非常关注的热点。目前这种算法大致可分为以下三类：

1.1 基于距离矢量

距离矢量是指MN与MAP之间的路由跳数。最常见的是最大距离矢量MAP选择算法。MN通过路由器通告消息(router advertisements，RA)获取MAP和距离矢量信息，接下来挑选其中距离矢量值最高的一个MAP量进行注册。该方法能够降低MN移动时的宏切换频率，但会使高层MAP负载过大而形成通信瓶颈。

1.2 基于移动速度

这种手段主要是利用了MN中的移动速度来进行判定。但是在实际的操作中，速度并不能很好地进行判定，这种速度是一种抽象的概念。在MAP中对数据点的选取上，针对不同的层次，对其中的不同速度范围分别对应了不同的MN请求。通常层次高，处理就快。该算法能很好地解决负载分担问题。文献[4]提出的MAP选取算法就是典型的基于移动速度的MAP选取算法。

1.3 基于拓扑结构

这类算法主要是利用网络拓扑的方法来实现所需的目的，其实施的操作流程为：第一步，及时地提取每个MN中所对应的网络拓扑数据；第二步针对上一步提取的信息进行处理与整合，然后选取适当的信息。在文献[5-6]中采取的选取算法就是采用了网络拓扑算法。

2 改进方案

文中结合现有的算法进行分析并在此基础上进行改进，提出一种新型选取算法。该算法也是建立在MN移动估计预测基础上的。

2.1 基本思想

改进算法结合了网络拓扑的思想，也综合考虑到MN在运动过程中表现出来的性能以及对应的速度对算法产生的干扰。其中心思想围绕了MN移动呈现出来的特性在空间以及时间上对应的关联性，选取特定时间对这一特性进行分析。

具体的实施流程为：

第一步对测量到的轨迹进行分类整理；第二步对其中的运动速度进行测定，这种测定方法主要是给定一个时间T，然后看轨迹；最后一步是结合前面测量的轨迹，在网络拓扑在结构上达到要求的情况下挑选出新的MAP。其中速度都是通过特定时间里经过的AR的个数来侧面表示的。

选取合适的时间间隔T，能够选取合适的MAP，从而降低分析的负担，提高效率，减少切换时间并在一定程度上降低丢包率。

2.2 AR和MN功能扩展

为了实现该算法，需要对现有接入路由器(access router，AR)和MN功能进行如下扩展。

(1)根据要求制定网络拓扑信息表。

网络拓扑信息表记录了整个网络拓扑中MAP的层次关系以及每个MAP域内下属的所有MAP和AR。该表可通过文献[5]提供的方法获取，图1中的网络拓扑信息表如图2所示。

(2)引入MN移动轨迹记录文档。

MN移动轨迹记录文档记录了MN在原MAP域移动过程中所经过的AR、移动时间t及在前一个MAP域内的移动速度Vm-1。

(3)引入AR距离间隔表。

AR距离间隔是指两个AR之间相隔的最少AR数目，每个AR中设置一份AR距离间隔表，记录其他AR与该AR的距离间隔d。AR距离间隔表可以根据网络拓扑结构手工加入，也可以通过文献[7]中信息学习的方法获取。为了防止该表过大，需设置一个最大距离间隔D。

(4)引入MAP调整计时器。

该计时器所对应的时间间隔为T，在每一个间隔中，利用MN对其运动的轨迹进行分析与处理，并预测下一个间隔T的新移动轨迹，选取新的MAP。如果在间隔T内发生宏切换，将T归零并做轨迹预测。

图1 HMIPv6拓扑结构

图2 网络拓扑信息表

2.3 MN移动轨迹类型归纳

文中将MN移动轨迹分为以下三类[8]：

(1)类直线运动。MN的移动轨迹中不会出现重复的AR记录。如图1，若MN的移动轨迹为{AR1，AR2，AR3，AR5，AR6}，则MN做类直线运动。

(2)局部运动。MN在一定范围内运动，移动轨迹中会出现多次同样的AR记录，称为局部运动，这种情况如轨迹满足{AR1，AR2，AR3，AR4，RA3，AR1}。

(3)其他类运动。不符合类直线运行或局部运动的轨迹运动。

2.4 轨迹预测

预测方法为：首先结合AR的距离间隔表还有对应的MN的轨迹来进行分析，推导获取MN处于最初的MAP域里面的首个AR以及NAR之间的间隔d；接着设定MN在初始的MAP域中停滞的时长为t(0≤t≤T)，则MN在该MAP域内的速度为：

在对测量速度精准性提出要求时，可以根据需求将分析对象前一步的速度Vm-1作为参考，因此引入参数α(0≤α≤1)，令MN第m次宏切换时的移动速度为：

Vm=αVq+(1-α)Vm-1，0≤α≤1

如果MN按照速度Vm移动，可得出在上述时间间隔T内MN移动的最大距离矢量为P=T·Vm。

然后根据NAR中的距离间隔表找出距离间隔d小于等于P的AR集合C。

最后确定预测轨迹需结合MN移动类型的不同选用适当的方法进行。如设定对应的Cpmn作为MN在初始MAP域中所有的轨迹所对应的AR集合，同时设定Cnmn为与之对应的预测的集合。

当满足MN运动类型为类直线型时，对应的MN不会出现在原始的Cpmn中，这种情况为了避免出现过多的数据，则需要对前期信息进行消除,即Cnmn=C-Cpmn。

当满足MN运动类型为局部运动时，这种情况则需要分类考虑，具体操作为：

(1)在时间间隔T归零前产生的宏移动。

这种情况其轨迹有一定几率与之前出现过的重叠，为了避免对应的区域太小影响判定，需要在新的集合加入原有的，即：

Cnmn=C∪Cpmn

(2)在时间间隔归零前未产生的宏移动。

对于这种情况，说明所对应的管理域过大，这种情况则需要挑选出其中比较小的域进行注册，即：

Cnmn=Cpmn

选用上述的合适方法进行处理，后续通过网络拓扑结构，进一步挑选出满足要求的MAP来实施相应的注册。

2.5 算法分析

若MN当前没有注册MAP，则选择距其最近的MAP注册，若有则按如下方法选择。

当MN为类直线或局部运动时，采用如下公式进行MAP调整。

其中，N(MAPx∩Cnmn)为所对应的距离矢量，该量表示x所对应的移动锚点管理域中MAPx所对应的所有的AR整体和MN所预测的所有轨迹中包含的AR的数量；NCnmn表示MN中移动轨迹里面所对应的AR的数量；PMAPx表示MAP中针对MN轨迹预测所对应的所有的AR数量。

如果满足P=1，则表示该域可以涵盖所有MN的轨迹；

如果P<1，则表示该域无法涵盖所有MN的轨迹；

在实际情况中始终有条件满足P=1，这个需要充分地寻找对应的区域，找到对应x最小的情况，然后寻找对应的MAP进行注册。最后将T归零处理，并删除原有的记录表，但是要保留对应的Vm，接下来重新开始登记对应的MAP。

当重新登记的轨迹不是原始轨迹，则不需要调整，只需要清理对应的记录表，然后重新开始统计即可。

3 仿真实验及结果分析

3.1 仿真模型

实验使用NS2作为仿真平台，对最大距离矢量(F-MAP)和基于轨迹预测MAP选择方案(PT-MAP)进行模拟[9]，仿真网络拓扑结构如图1所示。设置了1个一层MAP，2个二层MAP，每个二层MAP下又包含了2个三层MAP，MAP最大负载为20。设定每一层只有三个AR，并且覆盖直径为一百米。对应的区间全面覆盖。每个仿真区域选取二十个MN，速度设定为每秒十厘米到二十厘米。这二十种运动形式设定为六个直线，十个局部，剩下的随机[10]。其中统一所有的MN是同种类型的调整计时器，其中时间间隔为一百五十秒，对应的参数α取值0.5。其中CN和对应的UDP连接在一起，MN则和null接收器连接在一起[11]。仿真开始后，CN从第5 s开始向MN发送UDP数据，一直到整个实验结束，总的模拟时间是300 s。

3.2 仿真结果及性能分析

主要围绕着F-MAP、PT-MAP进行对比分析，通过以下三个方向进行[12]。

(1)负载分担。

负载主要是针对特定时间中MAP所包含的MN总的个数，统计频率为25 s。具体可以参照图3。通过该图不难看出各层负载不存在分担的情况，在第一层满了才会往下一层分摊，这种情况会让资源得不到充分利用，采用负载分担以后，每层都可以参与信息的处理，从而达到资源的高效利用。

(2)切换时延。

图4展示的就是两种不同的切换时延的类型。切换时延为切换前接收到最后一个分组的时间与切换后接收到第一个分组的时间的间隔。每25 s统计一次。不难发现，PT-MAP方案切换时延整体小于F-MAP方案的切换时延。由于在PT-MAP方案中MN向其最近的MAP注册，所以前70 s内PT-MAP方案切换时延大于F-MAP，在一开始时会导致宏切换较为频繁，造成时延过大；随着实验的进行，由于MN在MAP选择处于稳定后，PT-MAP方案切换时延逐渐小于F-MAP方案，域间切换是造成切换时延的主要因素，PT-MAP方案中部分MN向距其较近的MAP进行注册，平均时延较小[13]。

图4 不同时刻平均切换时延

(3)丢包率。

丢包率是指在某时刻CN发送的总数据包与MN接收到的数据包之差和发送总数据包的比值。图5比较了两种方案的丢包率，每25 s统计一次。可以看出，PT-MAP方案丢包率整体小于F-MAP方案丢包率。丢包主要是由于切换时会出现通讯中断的情况，这个时候就会容易导致数据包的丢失。采用PT-MAP这套方案，其中的平均时延比较小，因此丢包的情况也会比较少。

图5 不同时刻丢包率

4 结束语

文中提出一种基于MN移动轨迹预测的MAP选择算法，综合考虑了MN的移动特征、移动速度以及网络拓扑结构等因素，为MN选择最合适的MAP进行注册。仿真实验表明，该算法提高了网络资源利用率，实现了MAP负载分担，降低了切换时延和丢包率，更好地满足了实际应用的需求[14]。

算法中关键是选择调整计时时间T，如果T选取过小会导致MN注册MAP管理域过小，从而增大宏切换频率；T选取过大，导致注册MAP管理域过大，底层MAP利用不充分，同时会增加通信时延[15]。因此，下一步需要对T的选择进行研究。