第三章 个体移动预测

1、个体移动过程中终端切换技术研究随着新型业务与应用的不断出现，异构网络下的终端融合已成为信息与通信技术发展的必然趋势，是支撑现代服务业应用与发展的前提与基础。根据多接入、多终端环境的要求，如何构建智能终端，实现虚拟终端系统内终端的有效预测切换，减小切换失败概率和分组丢失率，成为亟待解决的关键问题。有关异构网络选择和切换的研究目前已经非常广泛，并已取得了不少成果。文献8提出基于Elman神经网络的自适应网络选择算法，其将用户数量、带宽成本、用户的移动速度作为代价函数，选择最佳的接入方式访问当前的网络。文献9提出了基于模糊逻辑的网络选择算法，其考虑的因素包括接收信号强度、用户移动速度和网络吞吐量等，

2、但面临网络参数全面性、模糊数据配置量大、需要较长的学习过程等问题。选最好的网络实际上是一个典型的多目标决策过程。通常采用多属性决策（Multiple Attribute Decision Making，MADM）方法，例如SAW10、GRA11、ELECTRE12、TOPSIS13、AHP14、WMC15等。采用多属性决策理论计算网络参数的权重，然后从多个可用的网络中选择最优网络。然而每个接入网络所有属性不可能同时达到最优，一个无线网络的所有属性可以通过权重设置来达到目标的总体性能最优的状态。已有算法针对单个终端穿越多个网络时，选择一个最佳的网络用于垂直切换。（开题报告）但是终端选择切换的研究

3、还相对较少，因为大部分的异构网络环境假设用户只有一个终端。现有的研究多考虑基于终端位置或电池供电的终端接口选择问题。文献16提出了一个终端切换的方案，即其解决的是异构网络环境中不同用户终端的选择问题，而不是单个用户的多终端管理。文献17提出一种基于端到端的可重构系统的动态阈值的联合负载控制方法，但方案的选择是实现小区内或网络内用户终端的选择。（开题）文献293031都对切换触发时间选择问题进行了研究，然而它们只考虑了用户终端接收到当前服务网络信号强度的影响，在网络覆盖状况变化的环境下，它们并不能实现为用户选择最佳切换触发时间的目的。本文中，我们综合考虑用户多终端接收到当前服务网络和切换目标网络

4、的信号强度，在采用马尔科夫模型预测的基础上，提出了一种基于马尔科夫模型移动预测的切换触发时间选择方法。（Y-M）场景描述与系统架构场景描述根据实际情况，我们构建这样一个场景（如图3.1所示）：用户随身携带几台终端，如Pad、移动电话、照相机等，用户要体验某种在线业务，并且用户处于低速移动状态，当用户位置变化时，各终端的所接收到的信号强度也在变化，如果能够提前预测用户移动信息，选择最佳触发切换时间，那么将会大大减小切换失败率和丢包率，为用户提供更好的服务。图3.1 单个用户多个终端组成虚拟终端系统示意图系统模型为了使研究简单化，我们假设GSM是网络1，WiMAX是网络2，用户携带两个终端，也就是

5、该虚拟终端系统有两个单模终端组成，终端TG接入GSM网络，终端TW接入WiMAX网络。用户以恒定的速度v离开BS1点向BS2点移动，系统模型架构如图3.2所示。图3.2 用户移动过程中终端接收网络信号强度示意图在个体用户移动过程中，各个终端所在网络覆盖状况在不停地变化，终端之间往往需要进行切换来保证个体用户正在进行业务的连续性。此外，当用户的需求发生变化时，终端之间也需要进行相应的切换。与接入网络选择不同，切换机制的研究主要解决切换目标网络选择和切换触发时间选择等问题，即如何在保证成功切换的前提下使用户业务的分组丢失最小化。因此，我们对切换触发时间选择做最优化建模：min Pploss(t)

6、（3.1）s.t. Phft=0（3.2）其中，Pploss(t)是用户业务在t时刻触发切换时的分组丢失率，Phft是在t时刻触发切换时切换失败的概率。假设用户在t时刻与BS1的距离为d1，与BS2的距离为d2，BS1和BS2之间距离为l，则d2=l-d1，此外，为了评估切换算法性能，应该考虑信道模型和移动模型。在分析架构中，采用典型的Log-linear路径损耗模型。终端TG和TW接收到2个网络的信号强度值RSS（dB）分别为 RSSgt=Pgd1+fg,1=Pgvt+fg,1 （3.3）RSSwt=Pwd2+fw,2=Pwl-vt+fw,2 （3.4）其中，Pgd1为终端TG与BS1距离为

7、d1时接收到网络1的平均功率；Pwd2为终端TW与BS2距离为d2时接收到网络2的平均功率；fg,1和fw,2为零均值，标准方差分别为1和2的高斯随机变量，代表阴影衰落。我们定义接收灵敏度为终端在该网络下可以接收到并仍能正常工作的最低信号强度，它是一个功率电平，通常用dBm表示。假设终端TG在GSM中的接收灵敏度为Pgth,终端TW在WiMAX中的接收灵敏度为Pwth， 两个终端执行切换所需要的时间为Th。如果不考虑阴影衰落等因素造成的接收信号强度波动，即fg,1=fw,2=0。那么RSSgt为单调递减函数，RSSwt为单调递增函数。又上图可知，为了避免终端之间切换失败，终端TG和TW必须在T

8、1=TLG-Th和T2=TLW-Th之间触发切换，其中，TLG为终端TW接收到网络2的信号强度值恰好上升到Pwth的时间，TLW为终端接收到网络1的信号强度值恰好下降到Pgth的时间。即切换触发时间t必须满足T1tT2 （3.5）用户业务的分组丢失是由于终端接收到网络的信号强度小于终端的接收灵敏度所导致的。在网络1中，终端TG接收到的信号强度值为RSSgt=Pgvt+fg,1，由于fg,1服从均值为0、标准方差为1的正态分布，因此RSSgt<Pgth的概率为PRSSgt<Pgth=-Pgth-Pgvte-x221212dx （3.6）同理有PRSSwt<Pwth=-Pwth-

9、Pwl-vte-x222222dx （3.7）为了保证成功切换，两个终端需要在T1,T2之间触发切换，此时用户业务丢失由两部分组成：网络1中切换完成前的分组丢失和网络2中切换完成后的分组丢失。假设终端TG和TW在t时刻触发切换，用户的分组丢失概率可以表示为：Pplosst=T1t+Th-Pgth-Pgvye-x221212dxdy+ t+ThT2-Pwth-Pwl-vye-x222222dxdy T2-T1（3.8）所建立的最优化模型可转化为min Pplosst=T1t+Th-Pgth-Pgvye-x221212dxdy+ t+ThT2-Pwth-Pwl-vye-x222222dxdy T2

10、-T1（3.9）s.t. tT1 （3.10）tT2 （3.11）算法设计将目标函数对t求导可得：dPplosstdt=1T2-T1×-Pgth-Pgvt+The-x221212dx -Pwth-Pwl-vt+The-x222222dx （3.12）继续对t求导可得：d2Pplosstdt2=1T2-T1e-Pgth-Pgvt+Th221212-dPgvt+Thdt-1T2-T1e-Pwth-Pwl-vt+Th222222-dPwl-vt+Thdt （3.13）由于已假设用户速度v是恒定的，所以Pgvt+Th是关于t的单调递减函数，Pwl-vt+Th是关于t的单调递增函数，在上述式子

11、中，dPgvt+Thdt<0，dPwl-vt+Thdt>0，那么d2Pplosstdt2>0恒成立。由凸优化理论可知上述最优化问题是一个凸问题。那么我们令dPplosstdtt=ttri=0，其中ttri为理论上最佳切换触发时间，则根据式（3.12）可得：-Pgth-Pgvttri+The-x221212dx =-Pwth-Pwl-vttri+The-x222222dx 此外，考虑到网络1和网络2是相邻网络，那么地理环境对它们影响也基本相同，终端TG和TW分别接收到其对应网络基站信号强度受到阴影衰落影响基本相同，故可以假设认为1=2，可得Pgth-Pgvttri+Th=Pwt

12、h-Pwl-vttri+Th（3.15）由图3.2可知，终端TW在TLU时刻接收到网络2的信号强度值恰好上升到Pwth，也恰好是该网络的接收灵敏度，那么有Pwl-vTLU=Pwth，而此时终端TG还在网络1的覆盖范围内，同理有PgvTLUPgth。因为Pgvt是t的单调递减函数，Pwl-vt是t的单调递增函数，综合式（3.15）可以证明ttri+ThTLU，同理，可以得到ttri+ThTLW，又因为TLU=T1+Th，TLW=T2+Th，结合以上三式可得T1ttriT2。那么满足原优化问题（3.9）、（3.10）、（3.11）的最佳触发切换时间ttri必定满足下式：Pgvttri+Th-Pwl

13、-vttri+Th=Pgth-Pwth （3.16）在实际无线泛在网络环境中，终端接收到的网络信号强度受到阴影衰落和路径损耗影响，上述式子可转化为如下的最优化条件：RSSgttri+Th-RSSwttri+Th-Pgth-Pwth （3.17）其中，是一个很小的正数。根据以上的分析，为了能够准确的预测最佳切换触发时间，首先我们需要计算出终端切换所需要的时间Th，然后采用马尔科夫预测模型对两个终端接收到的相应网络的信号强度分别进行预测， 如果预测值满足式（3.18），那么t时刻就是最佳的切换触发时间预测值，即ttri=t。RSSgt+Th-RSSwt+Th-Pgth-Pwth （3.18）其中，

14、RSSgt+Th为终端TG在t时刻预测其在t+Th时刻接收到网络1信号强度值，RSSwt+Th为终端TW在t时刻预测其在t+Th时刻接收到网络2信号强度值。切换时延分析无线泛在网络环境中切换耗时分析网络架构及切换类型的差异导致不同类型的切换所需的时间各不相同，同时不同业务类型对切换时延的敏感度也不一致 因此，为了能够及时有效的产生 LGD信号，保证用户实现无缝切换，就必须对用户的切换耗时进行估计，在文献27的基础上，结合无线泛在网络下虚拟终端系统框架，我们对异构网络环境下的切换耗时进行分析（闫）。异构网络环境切换耗时在异构网络环境切换过程中，两个终端分别使用不同的网络接口进行通信，因此当终端T

15、W在与新网络基站建立链路的过程中，终端TU继续使用与原网络基站之间的链路进行数据传输，当终端TW缓冲好了以后，再将业务传输给TU。异构网络终端切换的耗时可以分为原接口耗时（Thp）、新接口耗时（Thn）和终端之间建立连接耗时（Thc）。原接口耗时由以下几部分组成：链路层获取目标网络信息时间（Thp-nbr）、切换告知时间（Thp-ind）和网络层切换时间（TFH），从而可得：Thp=Thp-nbr+Thp-ind+TFH （3.19）新接口耗时包括：扫描目标网络时间（Thn-scn）、切换执行时间（T*），从而有：Thn=Thn-scn+T* （3.20）对于不同的网络，切换步骤不同，切换执行

16、时间T*也各不相同，例如WiMAX 切换执行包括搜索和同步、关键信息交互和授权、注册；WLAN 切换执行包括鉴权和连接时间；GSM 切换执行则包括时间频率同步、鉴权、位置注册。各网络切换执行时间如下：T*=Trng+Tcap+Tkey+Treg ，for WiMAX Tauth+Tassc ，for WLANTsyn+Tauth+Treg ，for GSM （3.21）其中，Trng、Tcap、Tkey和Treg分别为WiMAX 网络的同步和搜索、基本能力协商、关键信息交互和鉴权、注册时间；Tauth和Tassc分别为WLAN网络的鉴权和连接时间；Tsyn、Tauth和Treg分别为GSM网络

17、的时间频率同步、鉴权、位置注册时间。蓝牙终端发现延时主要包括以下方面：查询扫描时由于主从设备不在同一频率产生的扫描延时、从设备扫描到查询信号产生的随机延时以及从设备扫描主设备发出的呼叫信号产生的延时。由于扫描延时和呼叫延时产生原因均是由于主从设备不在同一频率上，因此我们假定该两种延时时间相同，称为频率同步延时(FSD: frequency synchronization delay)，从设备随机产生的延时称为随机向后延时（RBD: Random Back-off Delay）。对于寻呼阶段，由于已经获得了需要连接的设备的时钟和ID信息，所以寻呼设备直接以被寻呼设备的频率发送寻呼包，寻呼扫描设备

18、收到后立即响应，因此寻呼阶段延迟相对固定而且非常小34，从而我们以查询阶段的延迟来估计整个连接过程的延迟。（湖大）故终端之间建立连接耗时包括：频率同步延时（Thc-fsd）和随机向后延时（Thc-rbd），从而有：Thc=2*Thc-fsd+Thc-rbd （3.22）由于虚拟终端系统中有多个终端，在执行切换过程中，多个终端网络接口可以同时工作，所以总的切换时延是：Th=Thp-nbr+Thn-scn+maxThp-ind+TFH，T*+Thc （3.23）如下图所示，用户从GSM网络向WiMAX网络切换过程中，各部分耗时估计值分别为：Thp-nbr=2(+HNN+) （3.24）Thp-in

19、d=2(+HMR+) （3.25）Thn-scn=2() （3.26）T*=Trng+Tcap+Tkey+Treg （3.27）其中，表示无线链路中可能存在传输碰撞等导致的时间开销，表示单位信息在相邻物理实体之间的传输延迟，表示相邻功能实体间的传输时延。HNN表示管理两个网络的网络重构管理器（NRM）之间的跳数，HMR表示GSM网络的移动交换中心（MSC）与WiMAX网络路由之间的跳数，其中网络层切换时延TFH要根据所采用的具体切换协议而定，蓝牙设备发现时间延迟Thc也要根据所采用的具体连接延时算法而定。Markov预测模型获得了切换耗时估计结果以后，我们采用混合Markov预测模型分别对终端

20、TG接收到当前网络信号强度和TW接收到切换目标网络的信号强度进行预测，终端以Tsamp为间隔对其接收到的网络的信号强度进行采样，将得到采样值X=xn,xn-1,x(n-p+1)作为输入的历史信息。由于终端在短时间间隔内采样得到的信号强度会有比较大的波动，为预测带来一定的难度，因此采用加权平滑（WMPM）12方法对采样得到的信号强度进行处理，具体如下：an=an-1+1-x(n)其中，(01)为平滑系数，an为加权平滑后的信号强度值。在移动预测问题上，多阶Markov模型和以多阶Markov模型为基础的回退模型已经被验证是比较符合移动用户的移动规律、预测比较准确的一种方法。下面简要介绍混合马尔科

21、夫移动预测模型。马尔可夫过程1马尔可夫过程的定义马尔可夫过程31是具有以下特性的随机过程：当过程在时刻 tk所处的状态为已知的条件下，过程在时刻 t（t>tk）的状态只与过程在tk时刻的状态有关，而与过程在时刻tk以前所处的状态无关。或者说，马尔可夫过程的“将来”只与“现在”有关，而与“过去”无关。这种特性称为“无后效性”或称为“马尔可夫性”。定义：设Xt,t0,+)是一个随机过程，如果对于任意n，0<t1<t2<<tnT，过程Xt，t0,+)在t1，t2，tn-1的取值分别为x1，x2，xn-1并且一下概率等式成立：PXtnxnXt1=x1,Xt2=x2,Xtn

22、-1=xn-1=PXtnxn|Xtn-1=xn-1则称随机过程Xt,t0,+)为马尔科夫过程。2.连续时间马氏链如果马尔可夫过程Xt,tT的状态空间S是离散的，则这个马尔可夫过程称为马尔可夫链。根据时间的连续与否，马尔可夫链可进一步分类为“连续时间马尔科夫链”和“离散时间马尔科夫链”。定义：设Xt，t0,+)是时间连续状态分散的随机过程，状态空间S=0,1,2,，如果对任意正整数n和t1<t2<<tn<tn+10,+)，有r1,r2,rn,jS，使得： PXtn+1=jXt1=r1,Xt2=r2,Xtn=rn=PXtn+1=j|Xtn=rn则称Xt，t0,+)为状态空间

23、S上的连续时间马尔科夫链。条件概率PXt+s=jXs=i,t>0,s0称为连续时间马尔科夫链在s时刻从状态i进入到状态j的转移概率函数，记为Pij(s,s+t)。二阶的 Markov 预测器二阶Markov预测器假定移动用户的位置变量X是一个随机变量，且随机变量序列Xi（1in1）构成一个时齐Markov过程。对于二阶Markov预测器，即要求随机变量序列Xi满足以下要求：PXn+1=aX1,n=L=PXn+1XnXn-1=anan-1PXn+1=aXnXn-1=anan-1=PXk+1=aXkXk-1=anan-1式中ak代表抽样的一个网络信号强度的采样值，L=a1a2an代表了网络信

24、号采样序列。二阶Markov预测器的目的是根据终端当前的RSS采样值以及上一个RSS采样值去预测下一个可能的RSS值，从而根据各个终端的RSS值判断是否需要切换以及选择最佳切换触发时刻，它的核心是建立转移概率矩阵M 。该矩阵的行元素表示长度为2的RSS上下文，列元素表示下一个RSS值，矩阵元素表示行元素代表的当前状态下，终端接收到信号列元素代表的RSS的概率。二阶Markov预测器的应用就是根据用户当前状态找到M中的相应行，该行中最大的元素值对应的列所代表的RSS即为预测结果，用公式表示如下Xp=MaxXn+1(P(Xn+1|C)其中Xp表示预测结果，C表示当前RSS上下文。但是，多阶 Mar

25、kov 模型，尤其是高阶 Markov 模型，在算法的复杂度方面存在较大问题。它的状态空间随着采样值的数目增加而呈爆炸式增长，给模型的实际应用造成比较大的困难。针对上述状态空间膨胀问题，虽然研究人员提出了一些新的解决方案，但是效果并不明显。针对这个问题，通过对数据集M中大量用户的跟踪文件的分析发现，在很多情况下，用RSSpre的信息来预测RSSnext也能达到一个比较好的效果。根据本章实际需要，我们提出一个二步 Markov 模型预测器。二步 Markov 模型在假定用户移动模式满足式（2.1）、（2.2）的前提下，有下面两式成立：PXn+1=aX(1,n)=L=PXn+1=aXn-1=an-

26、1PXn+1=aXn-1=b=PXk+1=aXk-1=bX(1,n)以及L的定义同上面相同。二步Markov预测器的核心任务是建立一个与一阶Markov预测器的转移概率矩阵同规模的转移概率矩阵。矩阵的行元素代表RSSpre，矩阵的列元素代表RSSnext。通过该矩阵就可以根据移动用户上一个的RSS采样值来预测其下一步即将接收的RSS值。一阶和二步Markov预测器，相对于二阶Markov预测器而言，各自缺失了一些信息，其预测性能比二阶Markov预测器差是必然的。所以联合一阶和二步Markov预测器，用比二阶Markov预测器小得多的代价获得与二阶Markov预测器相近的性能是不错的选择。混合

27、 Markov 预测器模型一阶和二步马尔科夫预测器的转移概率矩阵根据大数定律计算得到，但是在预测时，终端接收到的下一个可能RSS预测值不再仅仅取决于一阶转移概率矩阵或二步转移概率矩阵，而是综合两个转移概率矩阵的信息选择最有可能RSS预测值。具体的模型如下： pan+1anan-1=1pan+1an+2pan+1an-11+2=1 （1）式（1）中的1和2分别为一阶模型和二步模型的混合系数。混合模型的关键就是根据极大似然定理求出1和2。参数求解过程：模型的似然函数如下：L1,2=j=2n-1paj+1ajaj-1 （2）其对应的对数似然函数为：L1,2=j=2n-1logpaj+1ajaj-1

28、（3）式(2)和式（3）中的 n 均表示选取用来求极大似然的连续一段终端的历史 RSS采样值信息D的长度。把式（1）代入式（3）得到：L1,2=j=2n-1logpaj+1ajaj-1=j=2j=n-1log1paj+1aj+2paj+1aj-1 (4)要根据式（4）直接来求1和2是困难的。这里我们在模型中引入了隐变量，即把式（1）看作一个含隐变量Zj=Z1j,Z2j的模型，其中Zij0,1，且Z1j+Z2j=1。Z1j=1表示在第 j 步混合时取一阶模型作为预测器； Z2j=1表示在第 j 步混合时取二步模型作为预测器。因此，式（4）可改写为：Lc1,2=i=12j=2n-1zijlogi+C （5）式（5）中的 C 为与1和2无关的常量。通过引入隐变量 Zj，可以在式（4）采用 EM 算法来求解1和2。为描述方便，取向量=1,2。具体的求解算法如下：1、 给向量=1,2赋任意初值，即给向量0赋值；2、 Zijk=EkZijD=PkZij=1D，又PkZij=1D=PkDZij=1×PkZij=1PkD记p1j=paj+1aj 、p2j=paj+1aj-1，则有PkZij=1D=ikpij1kp1j+2kp2j Zijk=ikpij1kp1j+2kp2j3、 根据上述1k、2k以及