基于有限状态机的自动切换机制的设计与实现

许 辉，高德云，魏海涛

(北京交通大学 电子信息工程学院，北京 100044)

无线通信环境中，用户对终端移动性的需求越来越高。切换技术作为移动无线的一项重要特性，其优劣直接影响到移动用户的体验。如今切换技术包括传统的低速切换和高速列车等情景下的高速切换[1]，传统单一网络中的无线切换和异构网之间的切换[2]，异构网作为辅助的无缝切换[3]。

为了应对复杂的无线切换要求，提高不同环境下切换系统的稳定性，一方面要增强代码的健壮性，另一方面则需要设计一个自动切换控制机制，能够灵活设置各种参数和针对各种可预见的事件进行处理，并尽可能地接入无线网络。例如已经在地铁线路中应用的基于无线传输的列车自动控制系统(CBTC）的无线传输子系统，其漫游与切换功能已具备了较高的自动化与智能化的特性[4]。但现有的切换技术的性能还需要进一步完善，在切换过程中引入有限状态机为解决乒乓效应、快速切换和异构网切换等问题提供了一种新的灵活有效的解决方法。

本文提出了一种将有限状态机引入到切换过程的控制机制，并在WLAN环境中利用Wi-Fi终端进行了基于有限状态机的自动切换控制机制的设计与实现。移动终端在WLAN中的切换过程包括几种不同的阶段[5~6]，可以按照具体的阶段划分出几种不同的工作状态，并将这些工作状态组合成一个具体的有限状态机。因此，当终端的切换过程引入了有限状态机的概念后，对切换过程的控制就变成了对不同状态转移条件的控制。从而增强了系统的灵活性和稳定性以及自动控制能力，对于软件系统的健壮性和可控性都有显著的提高。

有限状态机在计算机科学与信息科学等许多学科领域得到了广泛的应用，例如通信系统、自动控制系统、游戏设计等。

1 基于有限状态机的切换机制设计与实现

一个动态的AP列表[15]。当触发切换的条件满足时，系统将不再执行扫描步骤，而直接在AP列表中选取一个最佳的AP进行接入。当触发扫描的条件满足时，系统将利用冗余信道单独扫描周边的AP并获取周边AP的详细信息，最后更新该列表。由于系统在每次切换前已经进行过扫描，也称为预扫描切换算法。

触发AP扫描的方式有2种，定时触发与信道强度判别触发。定时触发是指周期性的扫描周边的AP信息并更新AP列表。信道强度判别触发则需要设置扫描和切换两种阈值。其中，扫描阈值应稍高于切换阈值。切换中，信道水平在低于阈值时将触发冗余信道进行AP的扫描并更新AP列表。信道水平低于阈值时，系统在所维护的AP列表中选取最佳的AP进行切换。本文采用的是信道强度判别触发扫描的方式。

这种方案的缺点是可能引起接口间的互相干扰，而且一个接口只用来扫描有些浪费。优点是扫描过程与切换过程分离，切换过程不包括扫描过程产生的时延，大大减少了切换需要的时间。图1为切换流程图。

1.1 有限状态机的基本理论

有限状态机（Finite State Machine，FSM）又称有穷状态自动机（Finite Automation，FA），对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，它都能根据事先给定的转移函数转移到下一个状态[7]。

有限状态机的数学模型：

M=(Q, ∑, δ, q0, F)

Q是状态的非空有穷集合，q称为M的一个状态(state)。q0是M的开始状态(initial state)。∑为输入字母表(Input alphabet)，输入字符串都是∑上的字符串。δ是状态转移函数(transition function)，F是M的终止状态(final state)集合。

一个完整的有限状态机的设计，应该包括3元素的设计：状态，事件，动作。一个FSM包含有限个状态，系统在任一给定的时刻只能处于其中的一个状态。状态变化由事件所驱动。事件可以是系统内部或外部输入信号。系统在当前状态下接收到事件，执行相应的动作，即状态转移函数(transition function)，又称为状态转换函数或者移动函数。有限状态机的表述包括状态转移图和状态转移表。

1.2 终端切换流程分析

Wi-Fi终端在WLAN网络中通过判断信号是否低于某一阈值决定是否执行切换过程。这个阈值一般是指信号的强度（Received Signal Strength）或者是接收的功率[8~10]，也可以是某种改进方案，参照文献[11]。切换流程可以分为无线链路切换，接入路由器切换和重新认证3个步骤。我们将切换判别、触发、扫描周边无线接入点以及选择最佳接入点都归为无线链路切换并依此编写和修改终端上的切换程序。下面可将接入路由器简写为AR（Access Router），对无线接入点简写为AP（Access Point）。

为了减小切换时延与提高实验的切换效果，本文采用的切换算法参考了一种使用双网络接口卡切换的双链路方案[12~14]。其中，通信链路用于与通信对端进行通信，冗余链路用于对AP进行扫描，从而节省切换中扫描阶段的时延。为了把扫描过程和切换过程完全分离开，在程序中单独维护

经改进后的切换流程描述如下：

（1）周期性监测无线链路信号质量。（2）扫描触发条件满足，扫描AP并更新AP列表。（3）切换触发条件满足，选择最佳AP切换。（4）获取AR通告报文。（5）切换AR。（6）网络认证。（7）周期性发送认证更新报文。（8）重复步骤（1）。

基于有限状态机的终端自动切换控制机制采用事件驱动状态模型，将自动切换流程中每一步操作的结果作为事件输入，引起当前状态的变化和下一步动作的执行。切换过程如图2。横轴为状态机的所有状态，分别为空闲、扫描、接收通告、认证和监测等状态，纵轴表示状态机可以收到的所有事件，状态转移表的每一个成员为一个状态转移函数的指针。当接收到事件时，状态机根据状态转移表的当前状态与接收事件进入相应的处理函数。

图1 切换流程图

图2 状态转移表

1.3 基于有限状态机的切换机制的设计与实现

通过分析，切换流程可以分为5个状态。每一个状态是切换流程一个阶段的行为总和的反映，代表了切换流程的进度，如表1。

表1 切换流程中的状态分类

空闲状态是FSM初始化或者切换停止后处于的状态，Wi-Fi终端将等待切换开始事件或者手动切换事件。扫描状态是指Wi-Fi终端开始扫描周边AP，并更新AP拓扑结构图。只有当Wi-Fi终端第一次接入AR时处于该状态。接收通告状态是指Wi-Fi终端已经接入AP，开始等待接收来自AR的通告消息。认证状态是指Wi-Fi终端已经解析了AR的地址，开始了认证过程。监测状态是最重要的状态，表示Wi-Fi终端已经通过认证，开始监测信号的质量。程序中还加入了一些定时器来实现切换过程中的定时操作。

自动切换有限状态机中的事件按其对程序运行的作用可以分为正常事件和冲击事件。按照改进了的切换流程，程序中设计了16个事件。每一个事件都代表了一系列相关动作执行的结果，包括正常结果和异常结果。又根据事件类型，详细分类如下：（1）外部触发事件：切换开始、手动接入、切换停止。（2）正确流程触发事件：得到正确的扫描结果、认证通过等。（3）定时器超时触发事件：AR通告接收定时器超时、认证通过定时器超时、监测定时器超时、认证保活定时器超时、扫描限制定时器超时。（4）监测过程触发事件：信号质量低于阈值。（5）异常事件：得到错误扫描结果、接收到同一AR的通告以及异常。

事件触发引起状态机进行相应的处理，产生输出并向下一个状态迁移。并根据具体的输出和当前状态进入相应的状态转移函数入口进行处理。状态转移函数按照在状态机中的作用可分为正常转移函数和健壮性处理过程中的转移函数。每一个状态转移函数关联一次状态转移过程。本文中设计的状态转移过程如图3。

图3 状态转移图

状态转移图是切换过程的有限状态机模型设计的最后结果，是编写控制程序的依据。我们在Wi-Fi终端上完成终端自动切换程序的设计。为了满足使用和测试需求，程序采用Linux GTK图形库来实现用户界面，为用户提供操作接口以及状态显示等功能。用户通过图形界面能够实时的了解当前切换状态等信息，并在切换前根据实际网络情况灵活的调节各种参数，包括切换阈值、监测间隔、定时器时限等。采用默认设置或自定义设置如图4，图片中数值单位为毫秒。

图4 默认参数配置图

对于各种不同的无线通信环境，引入了有限状态机的切换机制还可以针对各种不同的可预见事件制定相对的策略并设计相应的切换程序，这样能够更好的契合实际应用情况。

2 实验与分析

实验用的Wi-Fi终端为DELL LATITUDE D500型号笔记本，安装Fedora Core 8操作系统，内置Intel 2100无线网卡，外置Cisco Aironet 350系列网卡。测试网络由分别位于两个不同信道的支持802.11b的AP构成，网络拓扑如图5。可通过Wi-Fi终端上的GTK图形控制界面控制切换过程并监测当前的状态。

图5 测试网络拓扑

为了获得最佳的切换效果，终端用户可以根据具体的网络情况灵活调节各项参数。移动终端与通信对端采用“ping”的方式来检测切换过程对通信的影响，通过检测移动终端从通信对端收到的数据包，完成切换程序在有限状态机控制下的功能测试。

通过多次实验，手动切换时延的统计数据如图6。由于本实验方案中移动终端采用了双网络接口的预扫描算法，参考图1的切换流程图，当终端发生切换时直接选择列表中最佳AP切换，发生手动切换时终端同样从选择最佳AP步骤开始进行切换。因此手动切换的时延与自动切换的时延非常接近，可以作为参考。由切换时延的统计情况可以看到，切换过程对正常通信产生的时延仅为几百毫秒。

此外，实验中还使用HTTP连接音视频服务器在Wi-Fi终端上进行播放。结果显示，在切换过程中低码率网络视频和音频的播放是非常流畅的，可以满足一般的实时性业务的要求。

同时，可以从界面了解到切换流程中的状态变化都遵从了状态转移图所示轨迹，对于所有可预测的事件都按图2由相应的状态转移函数进行了处理。 对于冲击事件的处理示例如图7。

从实验结果可以看出，基于有限状态机的移动终端自动切换能够实现正常的切换功能而且成功的对切换中的冲击事件做出了相应的处理，与以前只是单纯的将切换流程中各步骤简单罗列的切换方法相比，可提高切换程序的健壮性和可控性。证明了本文采用有限状态机对切换进行自动控制的方法是科学的和正确可行的。

图6 强制手动切换统计平均时间

图7 对冲击事件的处理示例

同时，该方案也有其缺陷和局限性。对于终端来说，同时配备两块网络接口卡是对硬件资源的浪费，提高了移动终端的造价和能耗，还可能引起相互间的信道干扰从而影响到通信的质量。移动终端上的程序设计是基于状态机控制机制重新设计的，并不适用于接入点处于不同局域网的情形。

3 结束语

本文介绍了一种基于有限状态机的Wi-Fi终端自动切换的方案，有效的将无线环境中接入与切换的整个过程结合起来，能够处理各种可预见的异常情况并根据不同的网络情况灵活的调节各种参数。为解决乒乓效应、快速切换、异构网切换等问题提供了一种新的灵活有效的解决方法，有效的避免频繁切换引起的服务质量下降的问题。类似于高速铁路中高速切换的环境，可针对可预知的高速环境制定一定的切换策略，并根据当前状态与参考事件提早进行切换，减少切换时延，避免高速运行中切换时延接近切换间隔的问题。

从实验中的切换效果来看，采用有限状态机机制来控制终端的切换过程具有控制灵活、程序稳定、处理科学的特点。本文实现的WLAN中Wi-Fi终端的切换过程并不十分复杂，但考虑到多种无线网络之间切换等复杂切换过程，有限状态机的引入将是非常有意义的。

因此，采用有限状态机来对移动终端的切换过程进行控制是一种灵活有效的方法。

[1] 杨志松. 高速铁路信号覆盖于分析[J].重庆科技学院学报，2008（8）.

[2] 李常茗，李承恕. 一种异构无线通信系统垂直切换分析方法[J]. 铁道学报，2009（10）.

[3] 延志伟，周华春，关建凤. 一种在CDMA辅助下实现WLAN无缝切换的机制[J]. 北京交通大学学报，2009（4）.

[4] 王红光. 浅谈基于CBTC的列车漫游于切换功能[J].中国科技博览，2009（23）.

[5] S. Shin, A. G. Forte, A. S. Rawat, H. Schulzrinne. Reducing MAC layer handoff latency in IEEE 802.11 wireless LANs[C]. New York, NY, USA: ACM Press, 2004.

[6] C. Perkins. IP mobility support for IPv4[S]. IETF RFC 3344,2002.

[7] J. Gurp, J. Bosch．On the implementation of finite state machines：Proceedings of the 3rd Annual IASTED International Conference on Software Engineering and Applications. Scottsdale, Arizona, USA, Oct.1999[C]. Arizona，1999

[8] J. LI, Y. Pan, X. Jia. Analysis of dynamic location management for PCS networks[J]. IEEE Transactions on Vehicular Technology, 2002, 51(5):1109-1119

[9] P. Gregory, Pollini. Trends in handover design[J]. IEEE Communications Magazine, 1996, 34(3): 82-90.

[10] R. Caceres，L. Iftode．Improving the performance of reliable transport protocols in mobile computing environment[J]. IEEE Journal on Selected Areas in Communication, 1995, 13(5): 850-857.

[11] S. Seo, J .Song, HT .Wu, et al. Achievable throughput-based MAC layer handoff in IEEE 802.11 wireless local area networks[J]. EURASIP Journal on Wireless Communications and Networking. 2009.

[12] Sangho Shin，G. Andrea. Seamless layer-2 handoff using two radios in IEEE 802.11 wireless networks[J/OL]. Columbia,2006. http://mice.cs.columbia.edu.

[13] 韩礼红，王晓明，田玉河，李 健．VxWorks下双网卡冗余备份及智能切换技术[J]. 技术纵横，2008（6）：20-25.

[14] 张大伟，夏寅贲，田 霖，谭 敏. 移动IP中一种基于双链路的切换协议 [J]. 计算机工程，2006，32（8）.

[15] 倪维国，董永强，张 聪. 基于动态Cache的无线局域网快速切换算法[J]. 计算机工程，2009，35（2）：89-91.