随着便携设备的普及和物联网技术的发展, 移动性管理成为重要的研究领域.一方面, 需要保证携带便携设备的用户在移动过程中与通信网络保持连接; 另一方面, 在物联网中, 无线传感器节点位置移动以及网络中路由器或节点失效等都会导致移动性问题^[1].上述问题都可以借助移动IP技术解决^[2].基于网络的移动IP协议以代理MIPv6(PMIPv6)为代表, 其特点是由移动接入网关(MAG, mobile access gateway)来完成位置更新.由于具有不需要移动节点(MN, mobile node)参与移动性管理信令等优点, 目前PMIPv6已被广泛应用.

MN移动后与MAG建立连接, 并完成其位置更新的过程称为切换.通常切换过程需耗时几百毫秒^[3-4], 在此期间MN无法与外界通信.因此, 移动IP的研究热点主要为降低切换时延和优化性能, 主要方法是对网络层切换操作进行预先处理^[5-7]或在接入路由器间建立指向关系代替向家乡路由器更新位置^[8-10].

上述研究大多只针对单个MN的切换过程进行分析和优化, 而在车站、机场等人员密集的场合, 多个移动用户同时切换的情形非常普遍.

多个MN同时切换的过程与单个MN切换有较大区别, 主要在于：1)多个MN同时切换时, MN获得发送切换信令的机会远小于单个MN切换的情形; 2)多个MN同时切换时, 一个MN发送完成第一组切换信令后不一定仍能获得发送机会, 会受到其他同时切换节点的制约.目前, 多个MN竞争无线信道的问题已有一些相关研究. Bianchi^[11]分析了多个MN在随机选择时隙中发送数据包的概率.蔡圣所等^[12]分析了多个MN切换完成所需时间与竞争窗口的关系, 并分析了最优竞争窗口的取值.但所建立的模型仅考虑了MN发送一组信令即完成链路层切换的情形, 而当每个接入点都配置了MAG时, 在无线链路上至少需要发送2组信令^[3].因此, 需重新建立分析多个MN同时切换场景的模型.

笔者的主要工作和创新如下：建立了刻画多个MN同时切换的数学模型, 通过与已有文献对比和仿真来验证建模的正确性.推导了预测网络性能和保证服务质量的指标, 即给定切换时延限制下MN切换成功的概率和MAG支持的最大MN个数.

1 多个MN同时切换的性能分析 1.1 PMIPv6的切换过程

以目前已经广泛部署的基于IEEE 802.11标准的无线局域网为例, 当MN移动到新的MAG管辖范围后, 需要与MAG建立连接, 即进行链路层的切换.链路层的主要操作包括扫描、认证和关联操作.完成链路层的切换操作之后, MAG向局部移动锚点(LMA, local mobility anchor)发送代理绑定更新消息(PBU, proxy binding update); 在接受PBU之后, LMA向MAG返回代理绑定确认, 至此, 切换过程结束.

考虑到多个MN切换时信道竞争发生在无线链路, 切换时延主要由链路层切换过程导致, 故建模分析只考虑无线链路上的切换操作.当每个接入点都配置了MAG时, 扫描操作完成后, MN只需在无线链路上发送2组信令即可完成链路层的切换操作^[3].这两组信令是重新关联信令和采用开放系统认证方式认证而在MN和MAG间交换的信令^[13].

1.2 应用有限状态吸收马尔可夫链建模

假设同时发起切换的MN为m个, 与Liu等^[14]类似, 笔者采用有限状态吸收马尔可夫链建模多个MN同时切换的过程.将所有同时切换的MN都完成链路层切换的状态定义为吸收状态A, 在此之前的状态都称为暂态, 则暂态可以用二元组(n, j)表示.其中, n表示已经完成链路层切换(成功发送2组链路层切换信令)的MN数目, 0≤n＜m; j表示成功发送第1组信令的MN个数, 0≤j＜m.暂态的状态转移与MN在一个时隙内进行发送切换信令的概率τ有关.这里时隙的定义为一个状态开始到进入新状态之前的时间段.假设状态转换在每个时隙开始时进行, 每个时隙最多成功发送一组信令; 同时假设MN与MAG间的无线信道为理想信道, MN获得发送机会占用信道且不发生冲突则发送成功.暂态之间的状态转移由以下事件触发.

1) 仍在原状态.该事件包含2种情形：当前时隙内所有节点都没有发送信令或者有2个及以上节点同时发送而导致冲突.所有节点都没有发送信令的概率与已经完成链路层切换的MN个数n的关系为

$ {p_i}\left( n \right) = {\left( {1 - \tau } \right)^{m - n}} $

(1)

而当前时隙发生碰撞的概率为

$ {p_{\rm{c}}}\left( n \right) = 1 - {\left( {1 - \tau } \right)^{m - n}} - \left( {m - n} \right)\tau {\left( {1 - \tau } \right)^{m - n - 1}} $

(2)

因此, 仍在原状态的概率与已经完成链路层切换的MN个数n的关系为

$ {p_{{\rm{un}}}}\left( n \right) = {p_i}\left( n \right) + {p_{\rm{c}}}\left( n \right) $

(3)

2) 有新节点成功发送第1组信令.指在当前时隙只有一个MN进行发送尝试, 并成功发送第1组信令, 其转移概率为p_sf(n, j), 则

$ {p_{{\rm{sf}}}}\left( {n,j} \right) = \left( {m - n - j} \right)\tau {\left( {1 - \tau } \right)^{m - n - 1}} $

(4)

此时j增加, 并进入下一个暂态.

3) 有新节点完成链路层的切换.该事件是指当前时隙只有1个节点进行发送尝试, 并成功发送第2组信令, 即完成链路层的切换.因为只有成功发送了第1组信令的节点才可能发送第2组信令, 因此, 该事件转移概率与已经成功发送第1组信令的节点数目j有关, 则可得

$ {p_{{\rm{ss}}}}\left( {n,j} \right) = j\tau {\left( {1 - \tau } \right)^{m - n - 1}} $

(5)

此时已经完成链路层切换操作的MN个数, 即n增加, 进入对应的暂态.

显然, p_i(n)+p_c(n)+p_sf(n, j)+p_ss(n, j)=1.根据上述分析, 多个MN切换过程的状态转换可由图 1表示.因此, 在马尔可夫模型中, 暂态的总数与同时切换的MN总数m的关系为

$ \omega \left( m \right) = \sum\limits_{i = 2}^{m + 1} i = \frac{{m\left( {m + 3} \right)}}{2} $

(6)

将这些暂态按从左到右、从上到下的顺序依次标识为1, 2, …, ω(m), 则转移矩阵Q(m)为ω(m)× ω(m)阶矩阵, Q(m)可表示为

$ \mathit{\boldsymbol{Q}}\left( m \right) = \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{Q}}_0}}&{{{\mathit{\boldsymbol{Q'}}}_0}}&{}&{}&{}\\ {}&{{\mathit{\boldsymbol{Q}}_1}}&{{{\mathit{\boldsymbol{Q'}}}_1}}&{}&{}\\ {}&{}& \ddots & \ddots &{}\\ {}&{}&{}&{{\mathit{\boldsymbol{Q}}_{m - 1}}}&{{{\mathit{\boldsymbol{Q'}}}_{m - 1}}}\\ {}&{}&{}&{}&{{\mathit{\boldsymbol{Q}}_m}} \end{array}} \right] $

(7)

其中：Q_k为m-k+1阶方阵, Q′_k为(m－k+1)×(m－k)阶矩阵, k=0, 1, …, m-1, 两者分别表示如下：

$ {\mathit{\boldsymbol{Q}}_k} = \left[ {\begin{array}{*{20}{c}} {{p_{{\rm{un}}}}\left( k \right)}&{{p_{{\rm{sf}}}}\left( {k,0} \right)}&{}&{}\\ {}&{{p_{{\rm{un}}}}\left( k \right)}&{{p_{{\rm{sf}}}}\left( {k,1} \right)}&{}\\ {}&{}& \ddots & \ddots \\ {}&{}&{}&{{p_{{\rm{un}}}}\left( k \right)} \end{array}} \right] $

(8)

$ {{\mathit{\boldsymbol{Q'}}}_k} = \left[ {\begin{array}{*{20}{c}} 0&{}&{}&{}\\ {{p_{{\rm{ss}}}}\left( {k,1} \right)}&0&{}&{}\\ {}&{{p_{{\rm{ss}}}}\left( {k,2} \right)}&0&{}\\ {}&{}& \ddots &0\\ {}&{}&{}&{{p_{{\rm{ss}}}}\left( {k,m - k} \right)} \end{array}} \right] $

(9)

根据马尔可夫链理论, 基本矩阵定义为

$ \mathit{\boldsymbol{N}}\left( m \right) = {\left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{Q}}\left( m \right)} \right)^{ - 1}} $

(10)

其中：I为单位矩阵, N(m)中的元素N_ij(m)表示当同时切换的MN个数为m时, 从第i个暂态出发直到最后到达吸收状态, 需要经过第j个暂态的平均次数^[14].因此, 所有MN都完成链路层切换需要的时间为从第1个状态出发分别经过第u(1≤u≤ω(m))个暂态的次数与进入该暂态时所对应时隙长度的乘积, 故所有MN都完成链路层切换所需的时间为

$ T = \sum\limits_{u = 1}^{\omega \left( m \right)} {\left( {{N_{1u}}\left( m \right){t_{{\rm{slot}}}}\left( {y,u - 1 - \sum\limits_{g = 0}^{y - 1} {\left( {m + 1 - g} \right)} } \right)} \right)} $

(11)

其中：N_1u(m)为从初始状态出发到吸收状态时需经历状态u的次数; t_slot为一个时隙的平均长度, 其参数y表示状态为u时已经完成链路层切换的MN个数; $u - 1 - \sum\limits_{g = 0}^{y - 1} {(m + 1 - g)} $表示状态为u时已经成功发送第1组信令的MN个数, $y = \max \left\{ {k:u - \left. {\sum\limits_{b = 0}^{k - 1} {(m + 1 - b)} > 0} \right\}} \right.$, 表示满足$u - \sum\limits_{b = 0}^{k - 1} ( m + 1 - \mathit{b}{\rm{) > 0}}$的最大k值.当已经完成链路层切换的MN个数和成功发送第1组信令的MN个数分别为n和j时, t_slot(n, j)可表示为

$ \begin{array}{*{20}{c}} {{t_{{\rm{slot}}}}\left( {n,j} \right) = {p_i}\left( n \right)\sigma + {p_{\rm{c}}}\left( n \right){t_{\rm{c}}} + {p_{{\rm{sf}}}}\left( {n,j} \right){t_{{\rm{sf}}}} + }\\ {{p_{{\rm{ss}}}}\left( {n,j} \right){t_{{\rm{ss}}}}} \end{array} $

(12)

其中：σ为空时隙的长度, t_c为因发生碰撞而占用信道的时间, t_sf和t_ss分别为成功发送第1组和第2组信令而占用信道的时间^[11].

2 建模方法的验证及对比

以切换总时间为指标, 分别将所提建模方法与文献[12]的建模方法和仿真结果进行对比.

文献[12]中建模得到的总切换时间为

$ \begin{array}{*{20}{c}} {T = m{T_{\rm{s}}} + \frac{{m\frac{{\left( {1 - \tau } \right)\sigma }}{\tau }}}{{1 + \sum\limits_{i = 2}^m {\frac{1}{{{P_{\rm{s}}}\left( i \right)}}} }} + }\\ {m\sum\limits_{i = 2}^m {\frac{{{{\left( {1 - \tau } \right)}^i}\sigma + {t_{\rm{c}}}\left( {1 - {{\left( {1 - \tau } \right)}^i} - {P_{\rm{s}}}\left( i \right)} \right)}}{{P_{\rm{s}}^2\left( i \right)\left( {1 + \sum\limits_{i = 2}^m {\frac{1}{{{P_{\rm{s}}}\left( i \right)}}} } \right)}}} } \end{array} $

(13)

其中：m为同时切换的节点个数, T_s为成功发送信令占用信道的时间, P_s(i)=iτ(1－τ)^i－1, i∈[2, m].

计算和仿真中使用参数的取值如表 1所示.其中, W为IEEE 802.11物理层采取直接序列扩频时节点采用载波侦听多址接入竞争信道的竞争窗口最小值, N为允许的最大重传次数.根据Bianchi^[11]的结论, MN在给定时隙发送概率τ的变化范围为(2/(W+1), 2/(1+2^NW)), 即τ的变化范围为(0.008, 0.062 5).当物理层采取直接序列扩频时, 空闲时隙长度为σ, t_sf和t_ss均为分布式帧间间隔t_DIFS和相应信令发送时延之和, 式(13)中取T_s=(t_sf+t_ss)/2.信令发送时延由数据包长度和数据率R确定, 表 1中给出了认证请求发送时延t_RAReq、认证确认发送时延t_RARes、重新关联请求发送时延t_AuReq和重新关联请求确认发送时延t_AuRes的取值^[3].发生碰撞时占用信道的时延t_c可近似为发送相应信令的时间^[11].将上述数值代入式(12)可得一个时隙的平均长度, 然后利用式(11)和式(13)得到所提方案和对比方案的切换总时间.

利用Matlab编程可模拟多个MN同时切换时链路层的切换过程.模拟多个MN同时切换时信道竞争的过程如下：产生随机数并与发送概率τ比较, 从而判断一个节点在给定时隙内是否发送信令.轮询所有尚未完成切换的MN, 确定发送信令的MN个数, 从而判断该时隙的状态, 即为空闲或成功发送切换信令或发生碰撞.根据时隙状态确定该时隙的长度, 其中, 空闲时隙长度σ, 帧间隔时间t_SIFS、t_DIFS以及各信令的发送时延均与数值计算时取值一致.重复上述过程, 直至所有节点切换完毕.统计所需时间即可得到所有MN切换完成所需总时间.

将笔者和文献[12]的方法建模得到的切换总时间与仿真得到的结果对比, 如图 2所示.可知, 所提方案在同时切换MN总数和MN在一个时隙内进行发送切换信令的概率变化时均与仿真结果相符, 验证了利用有限吸收马尔可夫链建模的正确性.而文献[12]中的建模方法得到的时间与仿真结果相差非常大, 其原因是在建模时仅考虑了节点发送一组信令即完成切换.

3 实际应用中的重要指标

多个MN同时切换时, 移动用户最关心的问题是在给定时间内能否建立连接, 即切换能否成功.而对网络管理者来说, 为保障服务质量, 则关心MAG能同时服务的MN个数, 即MAG的容量.因此, 需要研究在给定时延限制下MN切换成功的概率和MAG的容量.

3.1 给定时延限制下MN切换成功的概率

假设同时切换的MN有m个, 由图 1可知, 第1个切换成功的MN可能经过前m+1个暂态, 第2个切换成功的MN则可能经过前(m+1)+m个暂态, 第i个切换成功的MN可能经过前(m+1)+m+…+ (m-i+2)个暂态, 因此, 可得第i个完成链路层切换的MN可能需要经过的暂态总数为

$ z = \sum\limits_{h = m - i + 2}^{m + 1} h = \frac{{i\left( {2m - i + 3} \right)}}{2} $

(14)

因此, 类似式(11)的表示方法, 第i个完成链路层切换的节点所需时间可表示为

$ T\left( i \right) = \sum\limits_{u = 1}^z {\left( {{N_{1u}}\left( m \right){t_{{\rm{slot}}}}\left( {y,u - 1 - \sum\limits_{g = 0}^{y - 1} {\left( {m + 1 - g} \right)} } \right)} \right)} $

(15)

其中各参数含义与式(11)参数含义相同.给定链路层切换允许的最大时延ξ, 则而对于任意选定的节点, 其切换成功的概率可近似为

$ p = \frac{1}{m}\sum\limits_{i = 1}^m {M\left( {T\left( i \right)} \right)} $

(16)

$ M\left( x \right) = \left\{ {\begin{array}{*{20}{c}} {1,}&{若\;x \le \xi }\\ {0,}&{若\;x > \xi } \end{array}} \right. $

(17)

3.2 给定时延限制下MAG的容量

定义MAG的容量为给定时延限制ξ的情况下, 能同时切换成功的最大MN个数.利用式(11), MAG的容量可表示为

$ \begin{array}{*{20}{c}} {C = \max \left\{ {m:\sum\limits_{u = 1}^{\omega \left( m \right)} {\left( {{N_{1u}}\left( m \right){t_{{\rm{slot}}}}\left( {y,u - 1 - } \right.} \right.} } \right.}\\ {\left. {\left. {\sum\limits_{g = 0}^{y - 1} {\left( {m + 1 - g} \right)} } \right) < \xi } \right\}} \end{array} $

(18)

其中：各参数含义与式(11)参数含义相同, max函数表示满足切换时延$\sum\limits_{u = 1}^{\omega (m)} {\left( {{N_{1u}}(m){t_{{\rm{slot}}}}\left( {y, u - 1 - \left. {\left. {\sum\limits_{g = 0}^{y - 1} {(m + 1 - g)} } \right)} \right)} \right.} \right.} $小于ξ的最大m值, 即MAG的容量.

将第3节数值计算的取值分别代入式(16)和式(18), 得到切换成功概率和MAG容量的计算结果.在仿真验证切换总时间的基础上, 根据给定时延限制, 统计已经完成切换的节点个数, 得到给定MN切换成功的概率.类似地, 得到给定时延限制下MAG的容量.定义误差函数E=|(c-s)/c|, 其中c和s分别为计算结果和仿真结果.数值计算结果与仿真结果的对比及误差情况分别如图 3和图 4所示.可以看出, 数值计算结果与仿真结果的误差较小.

4 分析讨论

图 5给出了同时切换节点数目变化对切换时延的影响.同时切换的MN数目越大时, 所有MN完成链路层切换的时延越大.当同时切换的MN数为15, τ为0.01时, 仅链路层认证和重新关联所需的时间可高达1.4×10⁴ μs, 此外, 加上切换时扫描信道的时延和在有线链路上交互绑定更新消息的时延, 因此无法应用于时延敏感的应用. 图 6给出MN在时隙内发送切换信令的概率τ对切换时延的影响.可以发现, 随着τ增大, T呈减少趋势, 出现这种现象的原因是：虽然τ越小, 发生碰撞的概率越小, 但等待的空闲时隙也越多, 从而导致T较大.需要指出的是, 在实际应用中, τ可以通过实际测量或经验获得.

图 3给出了给定时延限制下MN切换成功的概率.可以发现, 当同时切换的MN数较小时, 随着时延限制ξ增大, MN切换成功的概率可达1.但在时延限制严格时, 同时切换的MN个数越大, 切换成功的概率越低.因此, 在时延限制严格时, 用户可以根据切换成功的概率决定是否接入网络, 而MAG也可根据切换成功的概率决定是否提供基于网络的移动性管理服务.

图 4给出了不同时延限制下MAG容量.可以看出, 随着ξ增大, MAG的容量也越大.网络管理者可以根据用户可承受最大切换时延, 合理配置MAG服务MN的最大数目, 从而保证相应的服务质量.

5 结束语

多个MN同时切换时, MN的切换过程受其他MN影响.利用吸收马尔可夫链建模分析了多个MN同时切换的过程.推导了所有MN完成链路层切换所需时间的公式, 分析了给定时延限制条件下, MN切换成功的概率和MAG的容量, 为网络管理和配置提供参考.利用仿真和与已有文献对比验证了建模和数值分析的正确性.需要指出的是, 虽然所提方案只考虑了切换时在无线链路上需发送2组信令的情形, 通过扩展, 可以处理MN切换时需在无线链路上发送多于两组信令的情形.