扩展有限状态机（精选7篇）
扩展有限状态机 第1篇
软件测试在软件开发过程中占有重要的地位，它是保证软件质量，提高软件可靠性的重要手段。为此，提高软件测试数据自动生成的效率，降低软件测试在软件开发过程中的开销，有着十分重要的理论意义和实际应用价值。扩展有限状态机EFSM是目前常用的一种软件描述模型，它在有限状态机FSM(Finite State Machine)的基础上增加了变量、操作以及状态迁移的前置条件，可以更加精确地刻画软件系统的动态行为，已被国际标准化组织(ISO)作为通信协议形式化描述技术的底层模型，广泛应用于通信协议软件、嵌入式系统和面向对象反应系统的开发中[1,2]。
EFSM模型中，状态迁移和变量相互关联，迁移之间因变量和操作而交互作用，因此现有的针对FSM模型的测试用例生成方法不适用于EFSM模型。目前，已有一些研究人员对EFSM模型测试数据自动生成方法进行了研究[3,4]。随着启发式搜索算法在软件测试数据生成中的广泛应用，爬山法、模拟退火算法、禁忌搜索算法、遗传算法(GA)等也在EFSM模型测试数据生成中得以应用。文献[5]应用分散搜索算法实现了EFSM模型测试数据自动生成，其测试数据生成效率优于随机算法，但分散搜索算法在搜索过程中需要维护一个参考集，如果维护参考集的策略不合理，则会降低解的多样性。文献[6]提出了一种基于禁忌搜索算法的EFSM模型测试数据生成，但是禁忌搜索算法在搜索的过程中需要确定合适的禁忌长度和禁忌表，否则会影响测试数据生成的效率。相对于分散搜索算法和禁忌搜索算法，GA在搜索过程中不需要复杂的操作，而且具有较好的随机性。文献[7]在EFSM模型可执行路径上应用GA进行测试数据生成，并分析了影响测试数据生成的关键因素。但是，随着软件规模逐渐增大，被测软件的搜索空间变得越来越复杂，GA在复杂的搜索空间下，易于过早收敛，陷入局部最优，搜索效率不高[8,9]。多种群遗传算法MPGA是一种较新的搜索算法，采用多个种群同时进化，种群之间进行个体迁移的策略，可以避免过早收敛，能够提高算法的搜索效率[10,11]。
本文研究如何将MPGA应用于EFSM模型的测试数据生成中，并将其测试数据生成与应用GA的测试数据生成进行比较。实验表明:MPGA可以实现EFSM模型测试数据的自动生成，并且其测试数据生成效率明显优于GA的测试生成效率。同时，本文对影响MPGA测试数据生成效率的种群数量、迁移间隔、迁移率、迁移策略等相关参数进行了实验分析，得出了一种较优的参数组合，为后续进一步探讨基于MPGA的测试数据自动生成奠定了基础。
1 可扩展的有限状态机
EFSM模型可用一个六元组(S,S0,I,V,O,T)表示，其中S为状态集合，S0为初始状态，I为输入信息集合，V是变量集合，O是输出消息集合，T是一个状态迁移集合，T中每个元素t又可以表示成一个五元组<source(t),target(t),event(t),condition(t),action(t)>，其中source(t)是迁移t的源状态;target(t)是其目标状态;event(t)为迁移t上的激励事件，由若干个输入变量组成或为空;condition(t)是t能够执行的前置条件或为空，action(t)是迁移t引起的操作，由一系列的变量赋值语句或输出语句组成或为空。当EFSM处于某个迁移t的源状态source(t)，接收到激励事件event(t)且迁移的前置条件condition(t)为True时，执行该迁移的action(t)操作，并将状态由source(t)转换到目标状态target(t)。
图1为一个自动取款机(ATM)的EFSM模型，{START,S1,S2,S3,S4,S5,S6,S7,EXIT}构成其状态集合S,START为初始状态，EXIT为终止状态。T1～T23为状态迁移的集合。在EFSM模型中，由初始状态迁移到终止状态所经过的若干个状态迁移称为EFSM模型的一条迁移路径TP(Transition Path)。如:TP=['T1','T4','T6','T23']为ATM的一条迁移路径，其中T1=<START,S1,Card(pin,sb,cb),NULL,write(″Enter PIN″)、attempts=0>，表示在初始状态START时，若激励事件event(t)为Card(pin,sb,cb)，前置条件condition为空，则执行write(″Enter PIN″)和attempts=0操作，并将状态由初始状态STAER迁移到状态S1,S1经过T4迁移到S2,S2经过T6迁移到S3,S3经过T23迁移到终止状态EXIT。
2 多种群遗传算法
多种群遗传算法是遗传算法的一个扩展，它在传统遗传算法的基础上，设置了多个种群，每个种群称为一个子种群，利用并行遗传算法的思想，分别对每个子种群进行遗传进化操作，每隔一定的进化代数，从每个子种群中选择出一些个体，替代相邻子种群中的一些个体，即发生个体迁移。选取多少个体、什么样的个体进行替换、如何替换与种群数量、迁移间隔、迁移率和迁移策略有关。种群数量是指子种群数量和子种群中个体数量之积。迁移间隔是指子种群之间发生个体迁移的代数间隔，它决定了子种群之间发生个体迁移的频率。迁移率是指发生迁移的个体数量占子种群中个体数量的百分比，它与子种群中个体的数量决定了发生迁移的个体数量。迁移策略是指实施个体迁移的方法，常用的迁移策略有:选择最优的一些个体替代相邻子种群中最差的一些个体，随机选择一些个体替代相邻子种群中最差的一些个体等。
本文将多种群遗传进化中，所有子种群依次独立地进行一次遗传操作称为一代。图2给出了一个MPGA的基本实现框架，(1)随机生成若干个子种群，每个子种群中含有若干个个体;(2)计算每个子种群中个体的适应度值，如果找到最优解(适应度值为0)或者达到预设的最大迭代次数，则算法结束;(3)如果子种群进化达到一定的代数(满足迁移间隔)，则由迁移率和子种群中个体的数量计算出进行迁移的个体的数量，并根据迁移策略与相邻子种群发生个体迁移;(4)分别对每个子种群独立地进行一次遗传操作，形成新的种群，然后执行步骤(2)。
3 基于MPGA的EFSM模型测试数据生成
面向EFSM路径的测试数据生成，是指生成给定路径迁移上event中变量的值，使其满足路径上所有迁移的condition条件。
MPGA通过引入多个子种群并行进化，增加了搜索过程中个体的多样性，同时子种群之间的个体迁移促进了种群的进化，可以提高搜索效率。因此，本文探讨如何将MPGA应用于EF-SM模型的测试数据自动生成中，即针对EFSM模型一条给定的迁移路径，利用MPGA实现其测试数据自动生成。具体过程如下:对于EFSM模型的一条给定迁移路径，根据其event中变量的数量及类型，构造遗传操作的染色体;随机生成若干个子种群，每个子种群包含若干个个体;将每个个体作为输入运行被测的EFSM，并计算每个个体的适应度值，如果存在一个个体的执行路径与给定路径相同，则测试数据生成成功，算法结束;否则，每个子种群依次按照GA独立进行一次遗传进化;如果子种群进化达到一定的代数，则子种群之间发生个体迁移，从每个子种群中选择出最优的一些个体取代相邻子种群中最差的一些个体;如此重复直至生成满足给定路径执行要求的测试输入，或达到预定的迭代次数即测试生成失败。
3.1 适应度值计算
适应度函数的确定是MPGA实现的关键，它指导搜索朝着目标解的方向逼近。一般，适应度值越小，表明个体越优。本文基于MPGA的EFSM测试数据自动生成采用面向路径测试数据生成中常用的适应度函数[12]，具体计算公式如下:
其中，exec＿path表示实际执行路径，target＿path表示目标路径，Approach Level反映了实际执行路径与目标路径的距离，BranchDistance为实际执行路径不同于目标路径的第一个分支节点从真(假)分支到假(真)分支的距离，Normalize(d)将分支距离标准化为(0,1)之间的小数。
3.2 基于MPGA的EFSM测试数据生成算法描述
利用MPGA实现EFSM测试数据自动生成中，子种群之间采用单向环形结构，迁移策略采用最优个体替代相邻子种群最差个体的策略。具体实现算法的伪代码如下:
步骤1)初始化迁移间隔interval、迁移率rate和进化代数generation，并随机生成初始种群curr Solu[m,n]，其中m表示子种群数，n为每个子种群含有的个体数，个体采用实数编码;步骤2)由迁移率和子种群中个体的数量，计算出发生迁移的个体数量;步骤5～8)以当前个体为输入执行EFSM模型，并计算个体的适应度值，步骤9)如果适应度值等于0，则测试生成成功，输出测试用例;步骤11～15)如果子种群进化达到一定的迁移间隔，则子种群之间发生个体迁移，即根据适应度值从子种群i中选择出k个最好的个体，替代子种群i+1中最差的k个体，形成新的子种群i+1;步骤16～19)依次对每个子种群独立地进行遗传操作，即选择出参加进化的个体，对其进行交叉、变异操作;步骤20)运用精英策略，生成新的子种群;重复步骤4～20)，直到测试数据生成成功或达到设定的最大迭代次数，算法结束。
4 实验结果及分析
将上述MPGA应用于EFSM模型目标路径测试数据自动生成，并与文献[7]应用GA的EFSM测试数据生成效率进行了实验比较分析，结果表明，MPGA可以成功实现EFSM模型的测试数据自动生成，并且其测试数据生成效率明显优于GA。针对MPGA的多个参数，即:种群数量、迁移间隔interval、迁移率rate和迁移策略，本文采用控制单一变量法，即改变一个参数的取值而保持其它参数不变的策略，进行了大量的EFSM测试数据生成实验。在此基础上，分析了MPGA不同参数组合对测试数据生成效率的影响，确定了一个最优的参数组合，可以有效地提高EFSM模型测试数据生成效率。
本文以三个常用的EFSM模型为例，进行测试数据生成实验，每个模型的基本信息、目标路径的条数和路径长度如表1所示。实验设置MPGA和GA的种群规模为480个个体，交叉概率为0.7、变异概率为0.08，运用轮盘赌选择参加进化的个体，最大迭代次数设为106。程序在3.1GHz Intel Core i5-2400、4G内存、64位Windows 7的计算机上运行。
4.1 基于MPGA的EFSM测试数据生成
针对上述三个EFSM模型上的各条目标路径，应用MPGA生成测试数据时，相关参数按照文献经验值设置，即子种群数取6，则每个子种群含有80个个体(种群规模为480)，迁移间隔interval为5，迁移率rate为0.2，迁移策略采用最优个体替代相邻子种群最差个体的策略。对EFSM模型的每条目标路径生成10次测试数据，计算每条目标路径生成测试数据所需的平均迭代次数。
应用MPGA和GA两种算法生成三个EFSM模型所有目标路径的测试数据所需的平均迭代次数如图3所示。可以看出，利用MPGA可以成功实现EFSM测试数据自动生成，而且其测试数据生成效率明显优于GA。表2给出了运用MPGA和GA生成EFSM模型目标路径测试数据所需迭代次数的统计情况。对于三个EFSM模型，利用MPGA生成目标路径测试数据所需的最大迭代次数为6588，而GA则为9492，可见利用MPGA生成EFSM测试数据所需的迭代次数小于GA的迭代次数，并且其标准差在7.22～595.57之间变化。而GA测试生成的标准差在17.05～930.48之间变化，说明利用MPGA生成EFSM测试数据的稳定性好。因此，应用MPGA可以提高EFSM测试数据生成的效率。
4.2 不同参数对EFSM测试数据生成效率的影响
为了进一步提升MPGA测试数据自动生成的效率，本文对影响MPGA的主要参数进行了实验研究，分析不同参数对EF-SM测试数据生成效率的影响，以确定一个优异的参数组合。
1)不同子种群数对测试数据生成效率的影响
在种群规模(480)不变的情况下，实验设置了8组不同的子种群数的组合，即:A=24×20(子种群数为24，每个子种群中含20个个体)、B=16×30、C=12×40、D=8×60、E=6×80、F=4×120、G=2×240和H=1×480,H实为单种群即传统GA,MPGA的其他参数按照经验值设置，即迁移间隔interval为5，迁移率rate为0.2，迁移策略采用最优个体替代相邻子种群中最差个体策略。
针对不同的子种群数，应用MPGA生成EFSM目标路径测试数据所需的平均迭代次数如图4所示。从A～G组可以看出，随着子种群数减少，测试数据生成所需的平均迭代次数逐渐减小，当子种群数为2时，测试数据生成所需的平均迭代次数最小，但当子种群数为1，即传统GA时，测试数据生成所需迭代次数与MPGA相比反而增加，这可能是GA在一个种群上进化，其个体多样性不如MPGA的个体多样性所致。表3给出了三个EFSM模型在不同子种群时生成测试数据所需迭代次数的统计情况。由表3可知，当子种群为2时，三个EFSM模型测试数据生成所需的最大迭代次数为3791(Cashier模型)，远小于其它子种群数时Cashier模型测试数据生成所需的最大迭代次数18 402、8291、8276、7193、6588、6157和9492，并且当子种群为2时，三个EFSM模型测试生成的标准差分别为6.43、160.99、200。而其他子种群数时，三个EFSM模型测试生成的最小标准差分别为7.22、555.14、233.24，说明当子种群为2时，应用MP-GA生成EFSM模型测试数据的稳定性最好。综上所述，子种群为2时，MPGA生成EFSM测试数据的效率最好。
2)不同迁移间隔对测试数据生成效率的影响
迁移间隔是指子种群之间发生个体迁移所间隔的代数，它决定了子种群发生迁移的频率。根据1)的分析结果，MPGA取子种群数为2，迁移率rate仍取经验值0.2，迁移策略仍选择最优个体替代最差个体的策略，分析讨论迁移间隔interval分别为1、3、5、7和10时，对EFSM测试数据生成效率的影响。
三个EFSM模型在不同迁移间隔时生成目标路径测试数据所需的平均迭代次数如图5所示。可以看出，迁移间隔越小，测试数据生成所需的迭代次数越小，当迁移间隔为1时，测试数据生成所需的平均迭代次数最小，这可能是因为迁移间隔越小，子种群之间的进化信息交流得越频繁，越能促进种群的进化。表4给出了三个EFSM模型在不同迁移间隔时生成目标路径测试数据所需迭代次数的统计情况。当迁移间隔为1时，三个EFSM模型生成测试数据所需的最大迭代次数分别为492(Cashier模型)，远小于其他迁移间隔时Cashier模型测试数据生成所需的最大迭代次数1210、3971、1620、4143。并且迁移间隔为1时，三个EFSM模型测试生成的标准差分别为1.79、87.68、50.86，而其他迁移间隔时，三个EFSM模型测试生成的最小标准差分别为4.57、90.67、117.63，说明当迁移间隔为1时，测试数据生成的效率最稳定。所以建议MPGA应用于EFSM模型测试数据生成时，迁移间隔取1。
3)不同迁移率对测试数据生成效率的影响
迁移率是指发生迁移的个体数量占子种群中个体数量的百分比，它与子种群中个体的数量决定了发生迁移的个体数量。在1)和2)分析的基础之上，MPGA取子种群数为2，迁移间隔interval为1，仍采用最优个体替代最差个体的迁移策略，分析讨论迁移率rate分别为0.2、0.4、0.6和0.8时，对EFSM测试数据生成效率的影响。
图6所示是三个EFSM模型在不同迁移率时生成目标路径测试数据所需的平均迭代次数。可以看出，当迁移率为0.8时，测试数据生成所需的平均迭代次数最小，可能的原因是迁移率较高时，相对较优的一些个体能够传播到其它子种群，促进了其他子种群的进化。表5给出了三个EFSM模型在不同迁移率时生成目标路径测试数据所需迭代次数的统计情况。当迁移率为0.8时，三个EFSM模型生成测试数据所需的最大迭代次数为348(Cashier模型)，小于其他迁移率时所需的最大迭代次数492、2481和725。并且迁移率为0.8时，三个EFSM模型测试生成的标准差分别为1.79、58.85和49.84，而其他迁移率时，其最小标准差分别为1.79、87.68和50.51，说明当迁移率为0.8时，测试数据生成的效率最稳定。因此将MPGA应用于EFSM模型测试数据生成时，迁移率取0.8为佳。
4)不同迁移策略对测试数据生成效率的影响
迁移策略决定了迁移个体的选取与替换。在上述1)、2)和3)分析的基础上，MPGA取子种群数为2，每个子种群含240个个体，迁移间隔interval为1，迁移率rate为0.8，分析讨论在不同迁移策略，即随机选择个体替代相邻子种群中最差个体(简称随机选择)和选择最优个体替代相邻子种群中最差个体(简称选择最优)时，对EFSM测试数据生成效率的影响。
三个EFSM模型在不同迁移策略时生成目标路径测试数据所需的平均迭代次数如图7所示。由图可知，随机选择迁移策略在测试生成时的效率优于选择最优个体迁移策略，原因可能是选择最优个体替代最差个体的迁移策略，会较快地淘汰最差的个体，降低了整体种群的个体多样性。表6为三个EFSM模型在不同迁移策略时生成目标路径测试数据所需迭代次数的统计情况。采用选择最优个体作为迁移个体的迁移策略时，生成测试数据所需的最大迭代次数为348，大于随机选择迁移个体时的最大迭代次数288。并且选择最优个体作为迁移个体时，三个EFSM模型测试生成的标准差分别为1.79、58.85、49.84，而随机选择迁移个体时测试生成的标准差分别为1.76、28.32、41.51，说明随机选择迁移个体的测试生成效率较稳定。综合以上情况，说明采用随机选择个体替代相邻子种群中最差个体的迁移策略，有利于EFSM模型的测试数据生成。
4.3 基于最优参数组合的MPGA测试数据生成
在4.2实验研究的基础上，可以得出MPGA在EFSM测试数据生成时的最优参数组合，即在种群规模不变的情况下，子种群数为2、迁移间隔interval为1、迁移率rate为0.8、采用随机选择个体替代最差个体的迁移策略时，生成EFSM目标路径测试数据的效率最高。为进一步分析对比EFSM模型测试生成的效率，将MPGA参数取经验值(子种群数为6、迁移间隔为5、迁移率为0.2、选择最优个体替代相邻子种群中最差个体的迁移策略)和最优参数组合时的测试生成效率进行了比较。
图8给出了MPGA参数在经验值和最优参数组合时MPGA测试数据生成所需的平均迭代次数。可以看出，MPGA最优参数组合时测试数据生成的效率较好，其测试数据生成所需的平均迭代次数远小于MPGA参数取经验值时所需的平均迭代次数。表7给出了MPGA参数在经验值和最优组合时测试数据生成所需迭代次数的统计情况。三个模型在最优参数组合时测试数据生成所需的最大迭代次数9、288、194，而经验值所需的最大迭代次数分别为60、6 588、1 300，并且MPGA取最优参数组合时，三个EFSM模型生成测试数据的标准差分别为1.76、28.32、41.51，而取经验值时生成测试数据的标准差分别为7.22、595.57、263.57，说明MPGA采用最优参数组合时生成测试数据的效率较稳定。综上所述，MPGA在最优参数组合时，即子种群数为2、迁移间隔取1、迁移率为0.8、采用随机选择个体替代相邻子种群中最差个体的迁移策略时，生成EFSM模型的路径测试数据效率较好。
5 结语
本文提出了一种基于MPGA的EFSM路径测试数据生成方法，并与常用GA的测试数据生成方法进行了分析对比，实验结果表明，MPGA可以提高EFSM测试数据生成的效率。在此基础上，分析了MPGA不同参数组合对EFSM测试数据生成效率的影响，得出当子种群数为2，迁移间隔为1，迁移率为0.8，采用随机选择个体替代相邻子种群中最差个体的迁移策略，可以获得较好的EFSM测试数据生成效率，为后续进一步探讨基于MPGA的测试数据生成研究奠定了基础。未来工作拟分析比较并行搜索算法(如MPGA、蚁群算法等)和串行搜索算法(如分散搜索、禁忌搜索、模拟退火搜索等)对种群个体多样性的影响以及对EFSM测试生成效率的影响。
参考文献
[1]尤娟,李俊全,夏松.基于分支界限搜索的EFSM协议测试序列生成算法[J].计算机应用研究,2013,30(5):1349-1352.
[2]舒挺,刘良桂,徐伟强,等.自适应EFSM可执行测试序列生成[J].计算机研究与发展,2012,49(6):1211-1219.
[3]Androutsopoulos K,Clark D,Harman M,et al.Amorphous slicing of extended finite state machines[J].Software Engineering,IEEE Transactions on,2013,39(7):892-909.
[4]Lu G,Miao H.Feasibility Analysis of the EFSM Transition Path Combining Slicing with Theorem Proving[C]//Theoretical Aspects of Software Engineering(TASE),2013 International Symposium on.IEEE,2013:153-156.
[5]Zhang J,Yang R,Chen Z,et al.Automated EFSM-based test case generation with scatter search[C]//Automation of Software Test(AST),2012 7th International Workshop on.IEEE,2012:76-82.
[6]任君,赵瑞莲,李征.基于禁忌搜索算法的可扩展有限状态机模型测试数据自动生成[J].计算机应用,2011,31(9):2440-2443.
[7]Zhao R,Haman M,Li Z.Empirical study on the efficiency of search based test generation for EFSM models[C]//ICSTW:Software Testing,Verification and Validation Workshops.Washington,DC:IEEE Computer Society,2010:222-231.
[8]Lin S C,Punch Ⅲ W F,Goodman E D.Coarse-grain parallel genetic algorithms:Categorization and new approach[C]//Parallel and Distributed Processing,1994.Proceedings.Sixth IEEE Symposium on.IEEE,1994:28-37.
[9]Jin Y C.Evolutionary optimization in uncertain environments-a survey[J].IEEE Transaction on Evolution Computation,2005,9(3):303-317.
[10]Toledo C F M,De Oliveira R R R,Morelato França P.A hybrid multi-population genetic algorithm applied to solve the multi-level capacitated lot sizing problem with backlogging[J].Computers&Operations Research,2013,40(4):910-919.
[11]Dorronsoro B,Bouvry P.Improving classical and decentralized differential evolution with new mutation operator and population topologies[J].Evolutionary Computation,IEEE Transactions on,2011,15(1):67-98.
基于有限状态机的按键检测 第2篇
1 节拍控制实现对程序的事件处理和并行时序分配
通过状态机检测按键,必须使用节拍控制。状态机不是连续的时间单位,它是以事件为中心的编程思想。因此必须把检测按键变成事件来处理,而节拍控制是单片机实现多任务处理最好的方式,因此按键检测就可以融合到节拍控制中。Main.c文件内部while(1){……}采用一个定时中断来产生节拍,例如AT89S52的16位定时器T2,设置T2为自动重装,然后每5ms产生一个节拍。这样在程序前台[1]有一个节拍来控制任务的执行。见下面程序:
1) 定义节拍char beat[3]=0; //全局节拍的个数由并行模块的数量决定
2) 设置节拍
3) 中断方式激活节拍void _T2(void) interrupt 5
4) 控制并行模块while(1)
节拍控制要占用一个定时器产生节拍,定时器设置为低级。通过节拍的并行模式不是一个真正的并行结构。单片机指令执行是串行的,但宏观上节拍的引入,使事件或任务的发生仅仅出现在时间轴的点上,任务就类似并行序列。
2 按键的检测
传统按键检测就是加延时去掉抖动。类似这样的:if(kex)delay(xxx);if(key){……}}。状态机检测按键是要求利用节拍来检测,节拍如果5ms一次。那么当检测到按键的第一次数值进行保存,当第二次节拍到来时候,再去检测。比较前后两次的键值,如果相同则进入任务执行。因为这时候的去抖动是靠节拍的间隔来是实现的,中间这段时间别空闲给CPU利用。对于按键来说,是通过状态机方式来运行的状态机检测方式,具体运行模式见状态机结构图1:
举例说明具有四个键检测的程序清单如下:
程序使用状态机检测,同时引入了按键连击检测和按键复用的功能。这样有限的键可以实现无限的按键的使用。
3 结束语
按键检测是智能仪表最常用的,在快速响应的场合按键的检测需要浪费10~20ms的时间,如果按键很多,势必造成大量无用的延时。该文从状态机编程思想出发,介绍在节拍控制下如何组织和检测按键,使用了并行程序设计中的状态机思想。其中要点是建立状态机函数,这种组织形式为类似的程序处理也提供了参考。
参考文献
基于有限状态机的呼叫中心平台设计 第3篇
呼叫中心是一种充分利用电话网和因特网多项集成功能的技术, 将计算机技术应用到电话系统中, 并与数据库连为一体的完整的综合信息服务系统, 可以完成传统人工电话所无法进行的多种增值服务。它能为客户提供交互式的服务, 呼叫中心通过电话、传真等形式为客户提供准确、迅速的咨询信息, 以及业务受理和投诉等服务, 从而最大限度地提高客户的满意度, 同时增强企业竞争力。随着呼叫中心的广泛应用, 其稳定性和可靠性受到严重的考验。由于采用了稳定可靠的语音卡和通用计算机, 呼叫中心面临的最大问题是如何能设计出稳定可靠、高效运行, 并且可扩展的软件系统来实现语音卡和通用计算机的完美结合。
介绍一种基于有限状态机的呼叫中心平台的设计方案, 用有限状态机来解决呼叫处理部分的问题, 在状态机的状态转换和动作执行方面, 提出动作码的概念, 结合着事件代码, 将状态机从繁杂的事件和动作处理中分离出来, 专注于核心控制。另外在平台设计上, 放弃现有的VoiceXML解析器OpenVXI, 开发了平台专用的VoiceXML解析器。
1系统结构
平台采用业界最新的VoiceXML技术, 在集成东进D 081A语音卡的基础上实现了语音合成TTS, 语音识别ASR, 录音、放音、电话控制等功能[1]。
系统的总体结构是由电话网络、语音卡、各种服务器以及因特网构成。电话经由PSTN网络通过语音卡与服务器进行交互, 语音卡安装在应用服务器, 应用服务器通过网络协调VoiceXML文档服务器和语音文件服务器完成整个呼叫业务过程[2]。
应用服务器:是一个以呼叫处理模块为核心的有限状态机模型, 主要负责完成呼叫业务流程的规范与定义、呼叫业务请求和处理调度, 把系统的一系列平台和应用分开, 使应用服务器只处理呼叫业务逻辑与调度, 具体的实现由隐藏在应用服务器之后的其他系统来处理。
VoiceXML服务器:是一个数据服务器, 主要存储VoiceXML文档, 根据其他服务器的请求, 分析请求信息, 查询出相应的VoiceXML文档。然后将请求文档输入给VoiceXML解析器, VoiceXML解析器分析文档, 根据文档定义的流程, 语音信息等, 解析成一定的函数调用关系或者文本内容, 产生相应的数据或动作命令, 然后再返还给相应的服务器来引导和控制用户与执行平台之间的交互作用。
语音文件服务器:是一个语音服务分析统计服务器, 根据存储在服务器上的话务员录音及其附带信息, 统计分析话务员的通话时长、服务质量以及客户反映等情况。一方面该结果能作为系统话务分配的主要参数, 使系统的话务均衡地分配到各个话务员;另一方面, 这也是对话务员工作的监督, 是论功行赏的量化标准, 同时也是防止服务纠纷的仲裁依据。
电话及语音卡:电话是用户与语音平台进行交互的工具, 而语音卡则是连接电话网络和计算机网络的桥梁。语音卡将用户的输入信息传递给呼叫中心, 并将系统的输出结果反馈给用户。平台中所用的语音卡为东进161A模拟电话语音处理卡, 提供16路通道。还可以通过卡间的级联提供更多的呼入通道, 满足多条外线的并发呼入。
2 有限状态机和系统状态
如上所述, 系统中将同时存在多个呼叫, 每个呼叫从开始到结束要经历多个状态的转换, 多个呼叫的处理流程异步进行, 相互交织在一起。为了保证相应控制软件能够有清晰的控制结构和简洁的程序代码, 对问题进行形式化描述和建模是十分必要的。
有限状态机一般被用来描述具有有限个状态的系统, 该系统在输入的驱动下从一个状态转换到另一个状态, 并产生必要的输出。作为一种基本的形式化方法, 它在计算机相关领域得到了广泛的应用, 如形式语言的定义、网络协议的描述等。在呼叫中心系统中, 每次呼叫的处理过程都是在外部事件的驱动下经历若干状态的转换, 因此可以用有限状态机来描述这一状态转换过程。
一个有限状态机是一个五元组, M= (Q, Σ, f, S, Z) 。其中, Q是一个有限的状态集合, 它的每个元素称为“状态”;Σ表示该系统能接收的所有事件的集合, 它的每个元素称为一个“事件”;f是状态转换函数, 是Q×Σ→Q上的映射;S是系统的一个特殊状态, 一般是系统启动时的初始状态;Z是Q的一个子集, 是一个终态集。
具体定义如下:
Q={0, 1, 2, 3};
Σ={待机监听, 获得主叫, 成功打入, 播放录音, 播放完毕, 挂机};
f:在系统中对其进行扩充, 具体见下文及表1。
S={0};
Z={}。
状态转换函数只包括系统状态的变迁情况, 在本系统中加入动作码, 在状态变迁的同时准确方便地进行相关事务的处理。其形式化描述如下:
struct _StatusTable {
int nCurrentStatus;
/*系统的当前状态*/
int nTokenNo;
/*由事件而产生的状态变迁码*/
int nNewStatus;
/*系统变迁后的新状态*/
int nAction;
/*由于系统变迁而需要执行的动作码*/
}
其状态表见表1。
采用动作码, 是为了将状态机的状态转换和平台的动作处理结合起来, 同时又避免了与动作处理的过分交叉, 使得状态机更加高效和稳定, 程序代码简洁明了、结构清晰。状态变迁产生动作码后, 状态机就将处理工作交给了ActionHandle () 函数, 由其根据动作码执行相应的操作, 自己可以专心地等待状态的下一次变迁。
由于系统支持多条外线同时呼叫, 各条线路的呼叫处理过程都是异步进行的, 因此, 系统需要维护多个有限状态机, 每个有限状态机通过特殊的标识符相互区别。
3 系统状态实现的关键技术
3.1 队列管理器
作为一个呼叫中心, 系统同时存在着各种呼叫, 多个呼叫的处理流程异步进行, 相互交织在一起, 为了保证信息传递的准确性和稳定性, 系统采用队列管理器对于这些数据和信息的传递进行专门管理。
队列管理器用来识别和响应同时在多个通道上发生的行为。它就象一个管道, 多个来源的事件流进同一管道。队列管理器为每一个事件提供一个独特的标识, 同时还保存最近发生事件的历史记录, 从而允许应用程序处理同时发生在多个通道上的事件。
队列管理器中包括事件队列和命令队列, 分别用来传输其他服务器产生的各种事件和应用服务器下达的各种命令。详情见图2。
事件激发程序通过AppendInEvent () 函数将产生的事件添加到队列管理器中, 并添加相应的附加信息。应用程序通过AppendOutEvent () 函数取出事件, 比对其中的附加信息, 如果是给自己发送的则接收并进行处理, 否则抛弃。取事件函数处于一个实时的大循环中, 不停地监测可能产生的事件, 以保证响应的实时性和有效性。
3.2 VoiceXML服务器
VoiceXML是W3C定义的一种应用于语音浏览的可扩展标记语言, 用于开发语音应用程序。可以使不同系统集成、开发人员在统一的语言基础上进行业务流程定义。它定义了一系列的语音应用标签, 元素及相关操作, 能够播放音频文件, 输出文本语音, 录制和识别语音, 定义了用户与语音系统的交互过程。
VoiceXML服务器中存储着根据业务流程建模的VoiceXML文档。VoiceXML服务器根据不同的业务流程调用相应的VoiceXML文档, 通过VoiceXML Parser进行文档解析, 返回系统可以识别的数据结构, 从而指导系统的业务流程。
计算机无法直接对VoiceXML文档进行操作来实现解析功能, 必须把VoiceXML文档转换成易识别、易操作的数据结构。其中OpenVXI就是一种开源的VoiceXML解析器, OpenVXI在设计上有很多优点, 在此基础上开发能减少开发的时间, 不过要使用别人的代码, 必须去阅读openVXI本身的代码。因为OpenVXI本身是个没有完成的项目, 如果有些地方不清楚, 可能会在开发中带来灾难性的后果[2]。作为一个创新点, 也是为了语音平台能高效稳定地运行, 本系统设计了专门的VoiceXML解析器, 并建立相应的VoiceXML信息树, 给语音平台提供方便高效的接口函数, 完成VoiceXML文件解析工作。
解析工作主要由LoadVxml模块完成。LoadVxml模块的两个主要功能是解析VoiceXML文件、建立VoiceXML对象树。即对VoiceXML语法文件和VoiceXML业务描述文档进行语法解析、信息提取, 将标签中的属性、值记录下来。然后根据提取的文件信息, 在内存中建立信息树以便查询。
LoadVxml模块为了正确解析VoiceXML文件, 首先进行解析系统初始化, 内建了VoiceXML标签库信息。然后递归地将VoiceXML中的标签“各就其位”解析以区分哪些是属性, 哪些是父标签, 哪些是子标签, 以及各自的数量和对应的value。该过程采用了递归方法来实现。建立VoiceXML对象树后, 模块将返回一个_Document, 记录下所有VoiceXML文件中的节点信息、属性值。
3.3 语音卡集成
系统中集成东进D161A语音卡, D161A板上有8个模块插槽, 可插入8个模块, 提供十六个通道处理能力, 如果系统处理任务多, 可以级联语音卡。完成与电话用户交互, 系统语音信息播放。
语音卡是计算机系统与电话系统的连接的桥梁, 主要有信号音检测、摘挂机、振铃、放音、录音、接收用户DTMF码、检测通道状态、语音合成以及自动语音识别等功能。语音卡在系统中是集成在应用服务器上的。硬件卡主要负责处理、实现各种API功能, 将其转化为语音信号。语音卡API包含了语音卡能提供的所有功能。为了方便平台对语音卡的使用, 系统对语音卡进行了多层封装。系统在语音卡提供的API之上封装了一层, 作为中间组件。组件封装的是语音卡的相关功能函数函数, 其它接口只要调用相关组件就能控制语音卡了, 这样在上层接口与语音卡之间构架了一个抽象层, 对上层接口而言语音卡是不可见的, 实现了组件, 就可以在系统集成不同型号、厂家的语音卡。在中间组件之上还封装了一层与VoiceXML解析器交互的接口, 这样VoiceXML文档被解析后的内容就能够方便准确地传送到语音卡, 指导相应的操作。
3.4 呼叫处理模块
呼叫处理模块是应用服务器的核心部分, 直接与语音卡进行交互, 由它来调用语音卡的封装函数实现电话网与互联网的融合, 它伴随着外线呼叫的整个过程, 譬如振铃、接通、播放语音、通话以及挂机等。它的成败直接关系到整个呼叫中心的效率和质量。
作为一个呼叫中心, 必然会存在多条外线同时呼入的情况。为了能够快速、准确和稳定地进行呼叫处理, 系统使用有限状态机来实现状态的变迁。
系统根据开通的外线数量, 维护同等数量的状态机。每来一路外线呼入, 系统提供一个状态机, 并通过通道号将两者联系起来。程序使用GetToken (&Token) 从队列管理器提供的事件代码EventCode来获取变迁码Token, 之所以不直接采用事件代码, 是因为通过从EventCode到Token的转换, 能把一些简单的相关事务先处理了, 只把最关键的核心部分交给状态机处理, 这样能减轻状态机的负担, 使其能高效快速地运转, 适应繁忙的语音呼叫业务。状态机根据当前状态和变迁码, 变迁到新的状态, 并产生相应的动作代码, 由ActionHandle () 函数执行相应的动作, 推动进程的运转。
4 结束语
本文介绍一种呼叫中心平台的设计方案, 其核心程序基于有限状态机设计而成的, 由于在状态机实现的时候加入了动作码, 并开发了平台专用的VoiceXML解析器, 因此整个平台的效率和稳定性有了一定程度的提高。具有控制流程简明清晰、平台运行稳定高效的特点。利用上述设计方法我们开发了一个电子商务综合服务平台, 建立“一部热线电话联系、一个网站展示、一个平台运作”的新型社区服务模式, 并已经成功的运用于社区服务实践中。
摘要：介绍了一种面向社区服务的呼叫中心平台, 其核心模块是基于有限状态机设计而成, 具有流程控制简明清晰、运行平台稳定可靠的特点。在此基础上, 给出了有限状态机的定义以及其在呼叫中心平台中的具体实现, 并对队列管理器的工作原理以及VoiceXML的相关技术进行了分析介绍。
关键词：呼叫中心,有限状态机,动作码,VoiceXML解析器
参考文献
[1]朱瑞贤.VoiceXML解析器的研究与实现.北京:北京邮电大学, 2008
[2]张振州, 王丽芳, 蒋泽军.基于VoiceXML的呼叫中心平台的设计与实现.航空计算技术, 2008;38 (6) :58—60
扩展有限状态机 第4篇
关键词：路由协议,BGP,有限状态机
1 BGP路由协议概述
路由协议作为TCP/IP协议簇中重要成员之一，其选路过程实现的好坏会影响整个Internet网络的效率。按照应用范围的不同，协议也有内外之分。运行在不同自治系统之间的路由协议称为外部网关协议（Exterior Gateway Protocol，EGP），BGP就是一种典型的EGP，本文中所提到的BGP均指目前正在使用的BGP版本4。作为一种标准的外部网关协议，BGP设计之初就是为解决大型互联网的路由选择问题的，目前已被广泛地用于各大通信运营商之间的网际互连，IETF先后为BGP制定了多个建议，分别为：RFC1771——当前正使用的BGP协议版本，称之为BGP-4；RFC1654——BGP-4协议的第一个规范；RFC1105、RFC 1163、RFC1267——BGP-4之前的BGP版本。
广电数据平台与ISP运营商之间的协议就是采用BGP4，作为主要的网际之间选路和策略控制的手段。
2 BGP特性
GP使用传输控制协议（TCP）作为它的传输层协议，这样可以提供面向连接的可靠传输。通过这种方式，BGP认为它的通信是可靠的，因此BGP本身的通讯机制中不再附加任何重传或故障恢复机制。BGP使用TCP端口179。采用BGP的两台路由器相互间建立一条TCP连接，并交换消息以打开和确认连接参数，这两台路由器被称为BGP对等体。
BGP连接建立起来以后，将交换全路由表。因为BGP认为它的通信是可靠的，所以在可靠的链路上也不需要定期路由更新。BGP不是每次都广播所有的路由信息，而是在初始化全部路由信息后只发送路由的变化量（增量）。这样保证了BGP和对端的最小通信量，但同时增加了BGP的复杂程度。因为对于IGP，本地路由协议只需发送当时所知的全部路由，而不保存任何已发送信息，路由选择的工作由对端来完成；而BGP必须为每个BGP对端保存已经发送的路由信息，以便发送一条新路由前确认其是否真的应该发送。
为了减小路由表的体积和发送路由的通信量，BGP还支持CIDR（Classless InterDomain Routing）。它使用带有较短的掩码（相对于自然掩码）的路由来在一条路由中表达更多的路由信息。如从211．156．1．0/24-211．156．254．0/24可以使用202．112．0．0/16表示，从而减小了路由表的体积和发送路由信息时的网络流量。同时，作为AS自治区域间的路由协议，由于政治的、经济的等原因，BGP需要按照不同的路由属性来控制路由的发送和引入。
BGP路由器交换网络层可达信息，被称为路径矢量，由路径属性组成，包括路由到达目的地所应该通过的全路径（BGP AS编号）列表等。这个路径信息被用于构建无环路自治系统图。该路径是无环路的，因为运行BGP的路由器将不接受在路径表中包含其自身AS编号的路由更新，含有其自身的AS编号将意味着该更新已经通过了这个AS，如果再接受它会导致路由环路。
3 BGP协议中消息的应用
BGP使用TCP建立连接。和TCP建立一样，BGP连接的建立也要经过一系列的对话和握手。TCP通过握手协商通告其端口参数等，BGP的握手协商的参数有：BGP版本，BGP连接保持时间，本地的路由器标识（Router ID），授权信息等。这些信息都在OPEN消息中体现。在BGP协议中主要有OPEN、UPDATE、KEEPLIVE、NOTIFICATION四种消息包。
BGP连接建立后，如果有路由需要发送则发送UPDATE消息通告对端路由信息。UPDATE消息主要用来通告路由信息，包括失效（退出）路由。
UPDATE消息发布路由时，还要指定此路由的路由属性，用以帮助对端BGP协议选择最佳的路由。需要注意的是，由UPDATE消息的格式可以看出每个UPDATE消息只可以发布一种路由属性，本地BGP如果有路由属性完全相同的路由（只有信宿地址不同），则可以由一条UPDATE消息发布，否则只能使用不同的UPDATE消息发布。
关于路由属性在BGP选择路由时的应用，参见BGP协议路由属性的应用部分。在本地BGP路由变化时，也使用UPDATE消息修正对端BGP的路由表。
经过一段时间的路由信息交换后，本地BGP和对端BGP都无新路由通告，趋于稳定了。此时要定时发送KEEPALIVE消息以保持BGP连接的有效性。对于本地BGP，如果在超过保持时间的时间内，还未收到任何对端BGP消息，就认为此BGP连接已经无效，将此BGP连接断开。当本地BGP在运行中发现错误时，要发送NOTIFICATION消息通告BGP对端。如对端BGP版本本地不支持，本地BGP收到了结构非法的UPDATE消息等。本地BGP退出BGP连接时也要发送NOTIFY消息。BGP收到NOTI-FICATION消息后，要作相应处理。
4 BGP伙伴的有限状态机（FSM)
BGP从发起到建立连接经过了复杂的状态转换。研究BGP的内部的异常情况，只有熟知它在不同的工作状态所具有的特性才能很快的找到问题的结症，并作出相应的处理。BGP有6种相应的状态和13种事件，在每一种状态下都有相应的事件可能发生，为了简单明了的分析BGP状态和事件之间的联系，BGP使用了有限状态机的概念，动态地描述了BGP的工作过程。
BGP有限状态机有6种状态：
文中涉及到的BGP事件：
一个BGP对等体之间比较典型的建立连接的过程为：Idle（启动消息）->Connect（TCP连接成功，发OPEN）->Opensent（收到OPEN消息，协商成功）->Openconfirm（收到KEE-PALIVE消息）->Established（TCP连接关闭，有错误，或处理UPDATE消息失败，或收到NOTIFICATION消息）->Idle。
BGP对等体磋商在建立连接关系之前关系之前要经历不同的阶段。下面就不同阶段的状态转化做详细的探讨。
4.1 空闲状态（Idle)
这是BGP启动连接的第一个状态。在这个状态里BGP等待一个一般是由操作员或管理员引发的启动事件（start），在这个状态里BGP拒绝进入任何的BGP连接，不为对端分配任何资源。启动事件一般是通过管理员设置路由器配置建立BGP的对话或者使已经存在的BGP对话复位来触发。启动事件被触发后，本地系统初始化所有的BGP资源、复位连接重试计数器（ConnectRetry用做建立TCP连接的计时器）、启动一个TCP连接到BGP的对端、监听来自远端BGP对等体的连接（TCP）请求，TCP连接成功后改变状态到连接状态（Connect）。ConnectRetry计数器的值由本地设置，一般要足够大来满足TCP的初始化的要求。
如果BGP发言者检测到错误，就会关闭连接状态，转换到Idle状态。只有产生start事件才能把BGP发言者的状态从Idle转变成Connect。需要注意的是，如果start事件是自动产生的，那么连续的BGP错误就会导致该BGP发言者的状态抖动。所以，我们建议由于BGP错误而转到Idle状态的BGP发言者的对等体端的start事件不应该连续短时间间隔地产生。
Idle状态下除了start事件外所有的任何事件都被忽略。
4.2 Connect状态
这个状态是BGP对等体之间进行会话的前期初始化状态，它的完成与否直接与网络的物理连通性和链路状况相关，如果对等体之间的物理链路中断或者链路拥塞严重或线路误码过多都会使对等体之间的TCP连接建立失败，从而导致对等体之间的BGP协议无法建立。
在该状态下，BGP发言者等待传输协议（TCP）连接建立的完成。
如果TCP传输协议连接成功，那么本地系统重新启动ConnectRetry计时器，完成初始化并发送OPEN消息到BGP对端，从连接状态转变为Opensent。
如果传输协议连接失败则状态转送到Actived。
如果连接重试计时器ConnectRetry超时（产生一个ConnectRetry计时器溢出事件），那么本地系统重新启动ConnectRetry计时器，开始启动新的BGP对等体之间的传输连接，并继续监听远端BGP对等体的初始化连接信息，状态不变。
如果发生由系统或操作员启动的事件则本地系统释放所有被连接占有的资源，回到状态adle。
Start事件在Connect状态被忽略。
4.3 Actived状态
这是在传输协议连接失败后的一个补偿状态，在这个状态下BGP对等体之间会继续尝试建立传输协议（TCP）连接。
如果传输协议连接成功，本地系统清除ConnectRetry计时器，完成初始化，然后发送OPEN消息到它的BGP对等体，并给保持计时器（hold timer，存在于OPEN消息的包头之中，建议是四分钟）一个大的值，把状态改变为Opensent。
如果ConnectRetry计时器溢出（也就是触发了ConnectRetry计时器溢出事件），本地的BGP系统重新启动ConnectRetry计时器，初始化传输协议到BGP的对等体，同时继续监听可能来自远端BGP对等体所发起的连接，连接建立后改变状态到Connect。
需要注意的是，如果本地系统检测到一个IP地址不是自身希望的远端BGP对等体试图和自己建立连接，本地系统会拒绝对方的连接企图，重新启动ConnectRetry计时器，同时继续监听可能来自远端BGP对等体所发起的连接，状态保持不变（Actived）。这个认证机制是BGP安全性的一个保障机制，可以在一定程度上制止非法BGP连接请求。
在Actived状态，start事件被忽略。
作为对其他任何因系统获操作员引发的事件，本地系统都会释放所有与该连接相关的BGP资源，改变状态到Idle。
4.4 Opensent状态
进入到Opensent状态说明BGP对等体之间的TCP连接已经建立，双方已经开始就BGP协议的具体参数进行协商。
在这个状态下，BGP等待一个来自它的对等体的OPEN消息。当接到一个OPEN消息是，它的所有的域都要做正确性检查。如果对BGP消息头或OPEN消息头的检查发现一个错误或者有连接冲突出现，那么本地系统就发出一个NOTIFICATION消息并且改变状态到Idle。
如果在OPEN消息中没有错误出现，BGP就发送一个KEEPLIVE消息并设置KEEPLIVE计时器。最初被设置较大的保持计时器（hold timer）的值被经过磋商确定的保持时间所替代。如果磋商的保持时间值为零，那么保持时间计时器和KEEPLIVE计时器就不被启动。如果自治系统域的值计时本地的自治系统号，那么这个BGP的连接被称之为内部连接，否则称之为外部连接（这将影响到UPDATE消息的处理）。最后状态改变为Openconfirm。
如果接到一个从下层的传输协议发来的断开连接的通知，本地系统就会关闭BGP连接，重新启动连接重试计时器（ConnectRetry timer），同时继续监听可能来自BGP远端对等体发起的连接请求，转换到Actived状态。
如果保持计时器溢出，本地系统会发出一个NOTIFICATION消息，其中携带有保持计时器溢出的错误代码，改变状态为Idle。
作为对由于系统或操作员所发起的stop事件的响应，本地系统会发出一个携带错误代码“cease”的NOTIFICATION消息，状态改变为Idle。
在Opensent状态，start事件被忽略。
作为对其他任何事件的响应，本地系统会发出一个携带有“有限状态机错误”的错误代码的NOTIFICA-TION消息，并改变状态为Idle。
不论什么时候，BGP从Opensent状态改变为Idle状态，它都会关闭BGP连接（包括传输层的TCP连接），释放所有的与连接相关的资源。
如果在该状态过后，无法转入下一Openconfirm状态，一般来说应该是对等体双方的协商过程出现问题，即双方的配置参数协商不成功，需要重点关注具体协商内容，并做出相应调整。
4.5 Openconfirm状态
在这个状态下，BGP等待一个KEEPLIVE或NOTIFICATION消息。
如果本地系统接到了一个KEEPLIVE消息，那么改变状态为Established。
如果保持时间计时器在收到KEEPLIVE消息包之前超时，本地系统会发出一个携带有“保持计时器超时”的错误代码的NOTIFICATION消息，并改变状态为Idle。
如果本地系统收到了一个NOTI-FICATION消息则改变状态为Idle。
如果KEEPLIVE计时器超时，本地系统就会发送一个KEEPLIVE消息，并重新启动KEEPLIVE计时器。
如果接到一个从下层的传输协议发出的断开连接的通知，本地系统改变状态为Idle。
作为对由于系统或操作员所发起的stop事件的响应，本地系统会发出一个携带错误代码“cease”的NOTIFICATION消息，状态改变为Idle。
在Openconfirm状态，start事件被忽略。
作为对其他任何事件的响应，本地系统会发出一个携带有“有限状态机错误”的错误代码的NOTIFICA-TION消息，并改变状态为Idle。
4.6 Established状态
在Establiash状态，BGP与它的对等体交换UPDATE、NOTIFICA-TION和KEEPLIVE消息包。
如果本地系统收到一个UPDATE或KEEPLIVE消息包，当磋商的保持时间值不为零时，BGP将重新启动它的保持计时器。
如果本地系统收到一个NOTIFI-CATION消息包，状态改变为Idle状态。
如果本地系统收到一个UPDATE消息包并且UPDATE消息的错误检测操作程序发现一个错误，本地系统将发送一个NOTIFICATION消息包，改变状态为Idle。
如果接到一个从下层的传输协议发出的断开连接的通知，本地系统改变状态为Idle。
如果保持计时器溢出，本地系统会发出一个NOTIFICATION消息，其中携带有“保持计时器溢出”的错误代码，改变状态为Idle。
如果KEEPLIVE计时器超时，本地系统就会发送一个KEEPLIVE消息，并重新启动KEEPLIVE计时器。
每次本地系统发送一个KEEPLIVE或UPDATE消息包时，它都重新启动自己的KEEPLIVE计时器，除非磋商的保持时间值为零。
作为对由于系统或操作员所发起的stop事件的响应，本地系统会发出一个携带错误代码“cease”的NOTIFICATION消息，状态改变为Idle。
在Established状态，start事件被忽略。
按照以上描述的BGP协议状态之间的转化，为了更好的理解有限状态机，图1给出了一个简化了的图例，有助于理解BGP协议的工作过程。
这里的BGP有限状态机图是一个简化的限状态机图，在BGP协议的具体实现中还有很多中间状态需要考虑。
5 结语
扩展有限状态机 第5篇
1 二乘二取二安全计算机结构
二乘二取二制式计算机联锁系统由联锁机、电子单元模块、控显机和联锁总线等几个部分组成, 其中联锁机是二乘二取二容错技术的关键, 它由两套 (工作、备用联锁机) 组成, 单套联锁机中包含两个CPU单元, 这两套4个CPU组成了二乘二取二容错结构 (如图1) , 2套计算机系统各有两个CPU, 所有的结构和配件完全相同。在联锁机正常工作时, 单系的两个CPU单元进行独立的联锁运算, 并且在每个联锁周期内通过双CPU通信通道比较相同的联锁输出结果一致后, 才由工作机主CPU负责将正确的结果用来驱动物理设备。而两套联锁机之间同样进行信息交换, 即工作、备用两套联锁机系统采用二重比较和双机热备自动和手动切换的工作方式, 只有当二乘二取二的输出结果一致时, 才能保证系统的安全性。
2 有限状态机原理
有限状态机 (Finite State Machine, FSM) 是一种表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。美国国家标准研究所在算法与数据结构词典 (Dictionaryof Algorithms and Data Structures) 中将FSM的定义为:包含一组状态集 (States) , 一个起始状态 (Start State) , 一组输入符号集 (Alphabet) , 一个映射输入符号和当前状态到下一状态的转换函数 (Transition Function) 的计算模型。有限状态机是一个包含某对象所有独立状态集合的系统。状态机描述了某对象的所有状态及其转换的过程。状态机中对象的每个状态 (State) 都是独立的, 且各不相同。对象的状态转换是由事件 (Event) 来触发的, 对象收到外部事件 (Event) 并且满足特定条件时, 由当前状态转换到一个新状态, 也可能会保持原先的状态不变, 状态之间由转换 (Transition) 连接[1]。状态机模型如图2所示。
FSM经常用来模型化反应式系统。反应式系统对外部消息和内部事件作出反应, 属于外部消息和内部事件驱动系统。在确定性的反应式系统中, 输入消息和内部事件的顺序和决定了系统响应的顺序和数值。
像联锁系统这种分布式多机通信系统是一种典型的反应式系统, 其他模块的输入信息或者其他主机的同步信息可以用来模型化反应式系统。反应式系统对外部消息和内部事件作出反应, 属于外部消息和内部事件驱动系统。其他模块的输入信息 (如控显机的操作命令、安全电子模块的状态信息、其他主机的同步信息) 都是决定系统下部状态的变迁。基于计算机科学将具体每一个CPU对象抽象化的思想, 把每一次固定的联锁运算执行过程定义为一个典型的联锁周期。从系统初始化到接受状态数据, 命令操作, 然后执行联锁运算并最终输出联锁运算结果到执行电子模块命令这整个过程经历若干状态的变化, 把每个联锁周期划分为若干个状态, 每个状态都在等待一条或几条指定的消息 (或事件) 。消息到达后, 进程处理这些消息, 从而进入另一个状态。简单地说, 就是在消息。消息到达后, 进程处理这些消息, 从而进入另一个状态。简单地说, 就是在消息 (或事件) 的驱动下, 进程从一个状态转移到另一个状态。
3 双机任务同步设计
在联锁安全控制平台中, 需要双机在每个联锁周期都运算结果一致, 保证双机同步运行。同步方案一般有2种:任务同步和时钟同步。由于时钟同步对系统比较结构、故障检测结构和系统的整体硬件结构提出了更高的要求, 实现起来难度大。现在的髙性能CPU本身存在封闭缓存的问题, 时钟同步的方式对其无能为力[2], 相反髙性能CPU其强大的处理能力能对任务同步带来的系统开销可有效地弥补, 所以本文的安全控制平台采用任务同步方式。
任务同步就是在每个联锁周期任务中设立一个或多个比较、表决点对双机采集信息、驱动命令、用户程序运算结果等关键数据进行比较, 以完成对双机工作一致性的检查。如果不一致, 则进行故障处理。整个同步过程, 基于通信来实现。根据对整个联锁运算过程的分析, 需要在每个联锁周期内进行三次运算数据同步。
(1) 新周期开始信息的同步, 确保双机联锁周期开始时间一致, 防止因采集时机不一致导致获取的外部输入数据 (外部输入数据包括从外部电子设备模块接受的设备状态数据以及控显机的人工操作命令等) 的不一致引起的容错机制。
(2) 运算输入数据的同步, 防止因双机输入数据不一致引起的双机输出不同步, 造成严重安全故障, 降低系统的可用性。
(3) 运算输出结果数据的同步 (双机均进行联锁运算, 然后比较输出结果数据的一致性) 。
主从CPU同步的实现过程如下:逻辑处理单元中主CPU模块发送比较点状态数据, 在收到从CPU模块传递的状态数据进行同步比较。同样从CPU模块也发送自身的状态数据, 并在收到主CPU板的比较点状态数据后进行同步比较。主CPU控制整个同步节奏。CPU之间的数据传递及同步通过双口RAM和中断操作完成。参照FSM要素标准设针对每一个过程设计一对状态机[3], 如图3所示。
系间同步用于在主系和备系之间建立由主系指向备系的单向通道, 完成从主系到备系的数据传输, 以便在进行主备切换时, 备系应用程序的状态与主系保持一致。主备系同步比较的实现过程如下:系间的同步过程是由两系的主CPU之间完成的, 主系主CPU控制整个同步节奏, 主系主CPU主系发送比较点状态数据, 备系主CPU收到状态数据后进行同步比较。双系之间的数据传递及同步采用光纤通信和中断操作完成。
4 基于有限状态机的主/备/从任务同步模型
根据以上设计双机任务同步机制, 结合联锁机系统中不同CPU对象的分工, 可以将联锁平台软件中的数据流和时序任务控制分别由不同的FSM描述[5], 以把系统的4个CPU对象用三类状态机FSM来分别描述为FSM_PM (主系主CPU) FSM_SS (主/备系从CPU) , FSM_SM (备系主CPU) , 消息和控制命令在这三类有限状态机之间传输[6]。在每个周期时间轴上都有若干个同步点, 他们要进行时钟的同步以及联锁输入数据和输出数据的一致性同步, 这样的话, FSM既控制了下一个动作的起始, 也同时实现了数据的同步。用状态机描述如图4所示。
二乘二取二联锁系统的主/备/从并行任务同步模型在系统运行过程中也是可以互相转化的, 具体表现在, 当系统自检测或互诊断发现故障, 将会自启动或者进行主备切换以保证系统的正常安全运行。如图5所示。
当系统第一次启动时, 将根据启动快慢抢占主备系和主从CPU。因此, 系统第一次初始化, 将根据不同的对象角色运行不同的状态机, 如果发现主系发生故障, 当联锁主系自检测发现自身有故障时, 进行主备系切换, 那么原来运行主系状态机的CPU就会转化为运行备系状态机, 原来运行备系状态机的CPU就会转化为运行备系状态机。具体的状态机转化如表1。
5 任务状态机的形式化描述
通过面向对象的状态机结构化描述方法[7], 为不同的CPU对象建立状态模型, 方便对象“状态的切换”, 模型的类描述如下。
6 测试
在状态机中每个同步状态机的进入和跳转出去时向监测机发送网络信息, 然后用监测软件绘制出每次数据同步所需要的时间, 测试任务状态机模型同步的稳定性, 测出双CPU和双系之间的的同步通信稳定性测试结果如图6和图7所示。
实验结果表明, 按照本文设计的任务同步状态机模型运行, 二乘二取二联锁系统任务同步操作执行流畅, 各个数据同步过程稳定, 整个联锁周期可控。
7 结语
本文提出了基于有限状态机的联锁平台任务同步模型, 将二乘二取二系统中的不同CPU在联锁周期内任务流刻画成不同的有限状态机, 加强对不同角色CPU任务权限隔离, 既提高系统的安全性, 也简化复杂的双系切换过程, 并且引入状态对双系和双CPU的任务同步过程加以控制, 保证了同步的可靠性。
参考文献
[1]杜鹏, 白树仁.基于多层状态机的安全工作流模型[J].计算机工程与科学, 2005, 27 (9) :81-84..
[2]谢刚.城市轨道交通车载二取二平台关键技术的研究[D].成都:西南交通大学, 2013.
[3]张菁.基于有限状态机的UDP传输设计[J].计算机工程, 2011, 37 (17) :52-54.
[4]周夏芳.基于二乘二取二平台的通信设计[J].铁路通信信号工程技术 (RSCE) , 2014, 11 (1) :59-61.
[5]李健俊, 蒋一翔, 钱杰, 等.基于有限状态机的用户权限隔离模型[J].计算机应用, 2013, 33 (1) :149-152.
[6]董军.基于有限状态机的多媒体同步通信对象模型[J].计算机工程, 2002, 26 (8) :73-74
扩展有限状态机 第6篇
关键词：配置管理,有限状态机,统一配置,可视化配置
随着计算机网络的快速发展,企业内部网络也逐渐扩大,一般公司或者企事业单位的计算机组成局域网络进行内部交流,对网络管理系统的要求也更高。网络配置管理是管理网络内部众多厂家生产的软硬件平台[1]。不同厂家、不同种类、不同型号的交换机或者路由器等设备的配置命令集往往是不同的,如何快速、高效、可靠地配置网络设备是网络配置管理研究的目标。
现有的网络配置管理系统兼容性、灵活性、集中性、快捷性比较差,达不到用户的满意程度。本文依据传统的网络配置管理系统的模型,结合有限状态机、Telent和SNMP等技术,实现了扩展性、灵活性、适应性较强的网络配置管理系统。
1 相关技术
1.1 有限状态机
有限状态机(Finite State Machine,FSM)表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型[2]。
(1)状态是对象的生命周期中满足某种条件、执行某些动作或等待某些事情发生的一个阶段,能持续一段时间。
(2)转移:从一个状态节点转移到另一个状态节点的移动,发生状态转移时对象会执行相应的操作。
(3)动作:对象再进行状态转移时所做的一系列处理操作。
(4)事件:在一个时空中显示出现的特定现象,它可以出发状态转移。事件可以来自外部也可以来自内部。
1.2 Telnet
Telnet协议是由Arpanet开发的,主要用于Internet会话,允许用户登录进入远程主机系统。Telnet协议是TCP/IP协议族中的一员,是Internet远程登陆服务的标准协议和重要的信息服务和获取方式。
1.3 SNMP
根据ISO的网络管理模型,SNMP网络管理模型包括4个关键元素[3]:管理站,管理代理,网络管理协议和管理信息库。
2 系统设计
(1)统一配置命令集。
网络设备种类的繁多,系统设置一套命令集来对设备进行统一配置,系统自动识别命令,转换为设备对应的配置命令,对命令集进行扩充,提高系统的灵活性。
(2)命令转换规则。
通常设备型号中都包含有设备的一些详细信息,不同厂家不同型号的设备配置命令集一般不同。当网络中有新设备加入时,需要根据其型号进行转换。
(3)可视化配置。
可视化配置实现了对交换机、路由器、代理的配置以及操作,方便用户使用,不需要使用繁琐的输入输出命令。
系统总体设计框架如图1所示。
3 Telnet配置管理
本系统采用基于Java通信,用到了一个commons-net-2.0.jar包,它是一个有关Java通讯协议的实例和所需的jar包。
3.1 统一配置模块
命令转换模块对输入的命令进行转换。输入命令是统一配置命令集中的一条命令,来自用户终端输入,也可由其它系统自动生成并输入。而转换后的命令则是能在待配置的网络设备中可执行的命令。
(1)事件格式扩展插件。
定义及实现一些必需的类和功能接口函数,定义的类有命令类、命令事件类及回复事件类。
每个厂商的命令翻译规则写在以厂商名称命名的.properties文件中,需要提前定义好,表现为 “key=value”这种名值对的形式。其中,key为自定义命令;value为翻译后的原始命令组,在参数应出现的位置用占位符代替。
(2)命令事件采集插件。
负责接收终端输入信息,并判断其是否有实质内容,符合规定的格式,判断其是否包含待配置设备的ID和配置命令两项,然后封装配置命令,最终生成对应的命令事件。
命令事件采集插件流程:线程时刻监听用户的输入,当有输入到来时,启动命令翻译模块,从该设备厂商的配置文件中寻找能与该命令匹配的翻译规则,得到原始命令组,并将原始命令组发送给网络设备,如图2所示。
(3)场景分析插件。
整个场景分析的过程大致为:当命令事件产生时,判断输入的命令是否能被转换为可在待配置设备中执行的命令,如果能,则触发响应插件,进行命令的转换及发送;否则,报错并继续接收下一个输入命令。
在本文介绍的系统的场景分析插件中,场景原型包含了3个状态:初始状态(state_s0)、发送状态(state_send)、最终状态(state_final)。其中,后两个状态各有一个对应的回调函数。
场景原型中包含了5种转移条件:命令不正确(trans_IncorrectCmd)、命令正确(trans_CorrectCmd)、超出极限值(trans_ThreshExceeded)、回复信息匹配(trans_Reply)、计时器超时(trans_tmr_Timer Expiry)。
图4展示了上述5种转移条件各自都与3种状态中的一种或两种关联。
(4)事件采集插件。
接收来自代理端的回复信息,生成对应的回复事件,或是在等待回复信息超时后,生成空的回复事件。
回复事件采集插件也开启采集信息的线程池,当从代理端收到回复信息时,开启一个线程进行处理,最后传递到场景分析插件做一下步处理,如图4所示。
(5)响应插件。
将输入的命令进行转换,并将转换后的命令连同其他必要的附加信息发送至代理端。有限状态机的结构就是对输入命令的转换,由初始的状态进过命令转换模块的转换就变成可以执行的配置命令,配置系统。
3.2 命令转换规则
要实现统一配置,就必须设计出一套统一配置命令集,而这个命令集中的命令最终是要被转换成各网络设备中的真实命令被执行,因此必须有一个将统一命令转换为真实命令的规则。
统一命令的语法规则为:
operation-configitem parameter1 parameter2...parametern
"operation"为命令的动作含义,如set,use等。"configitem"为命令的客体对象,如ip-addr,rip-2等。
在对网络设备进行某一项配置时,往往需要使用若干条命令。现在希望将一些常用的配置操作进行打包封装,通过一条命令完成原本需要多条命令来完成的功能。
例如接口信息统一配置命令:set-ip-addr 接口名 IP地址 子网掩码。
在存储命令转换规则的信息时,参数的位置是由占位符来代替的。当系统接收到一条命令时,到配置文件中查找是否存在相应的转换规则,若不存在,则将输入的命令作为真实命令执行;若存在,则将匹配后的真实命令取出,并用输入的各参数来取代原命令中的各占位符,再将命令执行。
4 SNMP配置管理
4.1 可视化面板
由于互联网行业网络设备制造商众多,每个厂商的面板完全不同,并且同种设备的型号又不尽相同。
系统采用工厂模式设计可视化面板的调用,用户选择一台设备,调用工厂类,工厂类根据设备的厂商信息,具体调用DevicePanel的实现,从而实现对具体设备面板的展示。
系统首先定义一个抽象类:
public abstract class DevicePanel
{ public abstract layout();
public abstract addPort();
public abstract createMenu();}
系统定义了华为、思科、中兴、北电4个厂商设备类,它们统一继承DevicePanel类,实现了抽象方法,如图5所示。
可视化面板执行流程:
(1)用户双击网络拓扑图上一个设备。
(2)系统自动检测到设备的响应,根据这个设备的厂商和型号确定一个设备对象,通过工厂模式调用这个设备对象的面板。
(3)系统检测到用户对面板的操作,执行响应模块,操作和控制对象。
4.2 可视化配置
基于SNMP可视化配置主要通过网络拓扑结构展示网络设备及其相连关系,通过网络拓扑显示面板,用户可以选择查看任何一台设备,对设备参数进行查看和配置。
系统对网络设备配置,要开启SNMP服务,系统定义了统一配置命令,例如启动SNMP Agent服务snmp-agent。
系统利用实现SNMP协议实现用户对设备的配置操作,即通过获取网络设备中MIB信息来实现用户的请求功能,可以查看设备配置信息,配置端口开启和关闭等。
SNMP可视化配置包括3个步骤,如图6所示。
(1)用户选择一台设备,查看某个对象信息,向设备发送SNMP请求报文,报文中具体指定设备IP端口信息对应的OID。
(2)设备代理接收到报文,获取本地MIB信息库的OID对象值,返回给管理站。
(3)管理站对接收到的MIB对象属性进行动态加载,通过网页显示具体信息。
5 系统运行与测试
在文本框内输入规定好的命令,通过Telnet统一命令远程配置设备。
例如,用户通过系统配置交换机10.150.1.36端口信息,可视化界面如图7所示。
系统对网络设备进行统一配置的反馈信息,如图8所示。
6 结束语
本文搭建系统测试环境,设计测试方案对整个工程进行功能评估,结果表明该系统很好地满足了设计要求,实时获取、检测网络上监视设备的静态和动态信息,具有较强识别和配置能力,能有效配置管理网络。
参考文献
[1]雷明剑.Java Applet技术在网络管理中的研究及应用[D].重庆:重庆大学,2007.
[2]孙维堂,刘永贤,张禹,等.有限状态机在开放式数控系统中的应用[J].东北大学学报:自然科学版,2007,28(8):1174-1177.
扩展有限状态机 第7篇
UCC/EAN-128条码[1]是一种可同时描述字母、数字的高密度条码,该条码的每个字符由3条和3空组成,总宽度为11个基本宽度单位,每个条或空的宽度由字符的编码决定。UCC/EAN-128条码有3种字符集,根据条码的具体内容特点,可以采样合适的字符集,从而获得最短长度编码。同一条码允许有多个字符集组成,最小码长只有3位、最长码长可达48位,为非定长条码;条码前几位(2~4位)称为标识位,指示后续的数据长度和所代表的含义;可同时标识多组数据,中间用功能符分隔,检验码统一计算;同一信息可以有3种不同编码格式;相比其它一维条码,它能标识更多的字符,蕴含的信息量更大;在物流[2]和医院信息管理[3,4,5,6]等领域获得广泛应用。
GB/T15425-2002标准附录A声明了UCC/EAN-128条码符号长度最小原则和对字符串编码时起始符、切换符和转换字符与原始信息的组合方法。目前的文献资料中鲜见关于UCC/EAN-128条码生成算法,大多讨论EAN-13码[7]、Code39码[8,9],贾海生[10]等讨论了EAN-128码纯数字的编程实现,没有考虑数字、字符和控制码混合的条码编程情况。本文利用有限状态机的基本原理和GB/T15425-2002标准附录A中声明的最小原则,设定状态转换条件,通过对原始编码信息扫描,确定每个字符编码时的状态,从而实现条码的最短编码。
1 UCC/EAN-128条码
UCC/EAN-128条码由起始码、功能码、信息码、停止码、校验码组成[1],见图1。该条码有3个字符集,分别为字符集A、B和C,每种字符集有不同的编码方式。字符集A包括所有标准的大写英文字母、数字字符、控制字符、特殊字符及辅助字符;字符集B包括所有标准的大写和小写英文字母、数字字符、特殊字符及辅助字符;字符集C包括00~99的100个数字以及辅助字符。因为字符集C中的1个条码字符表示2个数字字符,因此使用该字符集表示数字信息可以比其它字符集信息量增加1倍,适合描述连续的数字符号。A、B、C 3个字符集可以交替使用,也可以用SHIFT功能对一个字符进行字符集之间的转换。
2 有限状态机
有限状态机是有限个状态以及在这些状态之间的迁移和动作等行为的数学模型,通常由状态、迁移、事件、动作和条件等几个基本要素构成。状态是从系统开始到现在时刻的行为所产生的综合结果,具有暂时稳定性,在外部或内部条件的影响下,系统可以从一种状态迁移到另一种状态,系统状态迁移图指示其变化情况;事件是在特定时空发生的对系统有意义的改变,一般会引起状态迁移,它既可以来自外部也可由内部生成;动作是在给定时刻对要进行的活动描述。有限状态机系统用动作来响应内外部事件,响应结果与系统当前状态和外部条件有关。
基于事件驱动的有限状态机思想在软件工程中主要应用于多分支选择结构中,它能采取多种操作来响应不同的事件。计算机中正在运行的程序可以看成是一种离散系统,在各个时刻都具有特定状态,该状态可用程序中所有变量的值和程序堆栈指针来确定。
在对UCC/EAN-128条码进行编码时,首先需要确定当前使用的字符集类型,然后根据后续要编码字符串特点,决定是否继续使用当前字符集或者切换到其它字符集,UCC/EAN-128条码编码特征适合用有限状态机模型进行处理。
3 UCC/EAN-128条码编码原则
在UCC/EAN-128条码符号中,通过使用不同的起始、切换和转换字符的组合,可以对相同的数据有不同的表示,下述内容为状态迁移的条件和动作[1]。
(1)如果数据以4位或4位以上的数字型数据符开始,则使用起始符C;如果数据中在小写字母字符之前出现ASCII控制字符,则使用起始符A;其他情况,使用起始符B。
(2)如果使用起始符C,并且数字个数为奇数,则在最后一位数字前插入字符集A或字符集B。
(3)如果在字符集A或字符集B中同时出现4位或4位以上的数字字符,且数字型数据字符的个数为偶数,则在第一个数字之前插入CODE C字符将字符集转换为字符集C,若数字型数据字符的个数为奇数,则在第一个数字之后插入CODE C字符将字符集转换为字符集C。
(4)当使用字符集B,并且数据中出现ASCII控制字符时,如果在该控制字符之后,在另一个控制字符之前出现一个小写字母字符,则该此控制字符之前插入转换字符;否则,在控制字符之前插入CODE A将字符集转换为字符集A。
(5)当使用字符集A,并且数据中出现小写字母字符时,如果在该小写字母字符之后,在另一个小写字母字符之前出现一个控制字符,则在该小写字母字符之前插入转换字符;否则,在小写字母字符之前插入CODE B将字符集转换为字符集B。
(6)如果在字符集C中出现一个非数字字符,则在该非数字字符之前插入CODE A或CODE B。
按照上述规则,UCC/EAN-128条码编码状态迁移图,见图2[11],序号(1)~(7)代表状态迁移条件,例如序号(7)代表从字符集B编码模式迁移到字符集C编码模式,触发条件是后续编码的字符串中至少有4个连续的数字字符。
4 编码实现
按照UCC/EAN-128条码的组成规则,在确定需要生产的条码信息字符串后,先生产左边空格编码,然后扫描信息字符串,确定开始使用的字符集,明确当前状态,再以后续要编码的字符为输入条件,结合当前状态,确定是否继续维持使用当前字符集,循环进行处理直至要编码信息字符串结尾[12,13]。
在处理中有状态迁移行为发生,最后的编码字符串与编码信息字符串不一致,它中间可能包含一些控制码,在计算校验码时,所有编码字符串均要参与运算,其权值与所在位置相关,最后的编码字符集决定校验码的归属。为方便计算校验码和生成条码图案,可采用一个链表结构,保存编码字符串,每个节点保存一个编码字符,新增节点加在链表尾部。从链表头开始遍历,可以很方便计算校验码,亦可按此顺序生成条码图案,见图3。
例如,输出条码集Abc D12345E,经过上述编码算法处理,得到的UCC/EAN-128编码集如下:Start B,FUNC1,A,b,c,D,Code C,12,34,Code B,5,E,校验码,Stop;每个字符集的状态分别是:2,2,2,2,3,3,2,2,最后校验码使用Code B字符集,状态为2。生成的条码,见图4。
4 结语
本文基于有限状态机的原理,结合UCC/EAN-128条码的最小编码要求,分析了该条码的三种字符编码转换条件,实现了从信息字符串到编码字符串的处理过程。设计了一种链表结构,存储包含控制码的编码信息,通过对链表进行遍历,实现了校验码计算和条码图案生成。整个模块已经应用在医院临床用血管理系统中,获得了较好效果。
摘要：本文采用有限状态机理论,讨论了UCC/EAN-128条码3种字符集的使用条件,3种编码方式互相转换的流程,展示了从信息字符串转变成编码字符串的处理过程,设计了一种链表结构存储编码字符串,实现了条码的最小编码,为后续检验码计算和图案生成提供了方便。整个模块已经应用在医院临床用血管理系统中并获得了良好效果。