状态空间分析总结

状态空间分析总结（共6篇）

1.状态空间分析总结 篇一

编队卫星空间状态参数估计量对ATI测速精度影响

基于对影响沿航向干涉(ATI)测速精度的.特征量分析,建立了卫星空间状态参数估计量与ATI测速精度特征量,特征量与测速的关联数学模型.仿真给出了不同场景设置下的特征量精度、误差传播矩阵和测量误差传递关系的精度影响因子,以及最终空间状态参数估计量对测速精度的影响.

作 者：王之元 易东云 姚静 Wang Zhiyuan Yi Dongyun Yao Jing 作者单位：国防科学技术大学理学院,长沙410073刊 名：中国空间科学技术 ISTIC PKU英文刊名：CHINESE SPACE SCIENCE AND TECHNOLOGY年，卷(期)：200626(5)分类号：V4关键词：空间状态参数 合成孔径雷达 干涉测量 精度分析 编队飞行 卫星

2.状态空间分析总结 篇二

随着城镇道路建设发展和交通工具的普及, 既带来了城乡交流的便利也使流窜犯罪作案的态势高发。为进一步扼制城镇街面犯罪率, 有效和快速地围堵城市道路肇事车辆及街面抢劫犯罪嫌疑人已成为公安部门在城市管理中的重要任务。针对城市街面犯罪事件及根据事发区域道路情况, 研究快速计算对犯罪嫌疑人的围堵路径、有效调配警力和构成最小范围布控圈, 是当前打击街面犯罪的首选课题。

目前, 公安系统打击街面违法犯罪活动的常用方法是110电话接处警和基础防围堵等。对于这类街面围堵问题, 基本围堵方案模型是以案发点为初始状态, 首先确定追捕对象可能逃逸的路口节点;其次确定追捕对象逃逸范围与警力围堵布控点的追逃时间博弈;然后依据现场警力及移动速度可形成何种形态的动态封闭圈, 最终实现追捕目标。

有关街面围堵计算策略, 文献[1]提出了确定最优布控圈的计算方法;文献[2]采用Floyd算法进行最优布控圈的计算。笔者认为上述文献在寻找布控点上的假设条件过于理想, 与实际情况有一定程度的差距。文献[1, 2]中提出的算法都是对可能形成封闭布控圈的每个道口进行逐个计算, 而采用逐点计算法的时间复杂度为O (N3) , 空间复杂度为O (N2) 。对于街面围堵指挥而言, 过大的复杂度导致每一秒延滞都会带来不可预见的后果, 尤其是在发生街面暴力犯罪行为时, 更需准确和及时地布控。

为解决上述问题和基于实战对计算效率的要求, 本文提出了基于状态空间分析的街面围堵凸包算法与方案。

1 凸包算法研究

1.1 凸包问题

在一个实数向量空间V中, 对于给定集合P, 所有包含p的凸集的交集S被称为P的凸包。

即

图1为凸包示意图。P的凸包可以用P内点 (p1, p2, …, pj, …, pn) 的线性组合来构造。

在二维Euclidean Space (欧几里得空间) 中, 凸包可想象为一条刚好包裹着所有点的弹性绳索。

1.2 凸包求解算法的基本思路

凸包属计算几何范畴, 是平面域中处理离散点集的一种算法。求解凸包问题的算法可分为增量法和分治法。而最常用的凸包算法是葛立恒 (Graham) 扫描法和Jarvis步进法, 还有包裹法、分治法河和快包法等。

Graham扫描法是基于堆栈的最精简算法, 其通过设置一个关于候选点的堆栈p来解决。输入集合S中的每一个点都被压入栈一次, 非S的凸包中的顶点的点最终将被弹出堆栈, 当算法终止时, 堆栈P中仅包含S的凸包中的顶点, 其顺序为各顶点在边界上出现的逆时针方向排列的顺序。

Graham凸包算法可直接在原数据上进行运算, 因此, 其空间复杂度为O (1) 。但如果将凸包的结果存储到另一数组中, 则可能在代码级别进行优化。而在扫描凸包前要进行排序, 故其时间复杂度至少为快速排序的O (NLg N) , 其扫描过程复杂度为O (N) , 则整个算法的复杂度为O (NLg N) 。

2 围堵凸包算法研究

2.1 街面围堵问题分析

为满足最优的时空间复杂度问题和基于实战对计算效率的要求, 本文提出了基于状态空间分析的街面围堵凸包算法与方案, 基本思路为:1) 初始估算案发到接报警时嫌犯可能到达的范围;2) 估算从接报警时刻起嫌犯到达各路口所需要的时间;3) 估算最近距离的警力到达各有效布控点需要的时间, 有效节点是指警力到达时间小于或等于犯罪嫌疑人到达该节点的时间;4) 每个有效节点的连线组成一封闭多边形, 确保嫌疑人不会逃出包围圈。方案示意如图2所示。

本文的算法方案与文献[1, 2]的区别是:后者需要将布控范围内的所有交叉路口或称布控节点都列入计算范围, 并判断警车是否先于嫌犯到达这些点。如果警车更快到达则属于布控点, 否则放弃。笔者认为街面围堵布控方案能否应用于实战取决于算法的效率。针对上述算法的局限性, 本文将问题做一简化。基于案发时警力分布情况, 只需考虑布控圈周边的点, 若警力能够先于嫌犯控制所有这些点并连接成一个封闭环, 则该封闭环上的每一个节点就是需要找的布控点。由于减少了所需计算的布控点数, 由此降低了复杂度, 算法的时间复杂度为O (N×Lg N) , 空间复杂度为O (N) , 与上述文献介绍的方法相比较节约了计算时间, 为提高打击街面犯罪提供了有效的技术支撑。

2.2 街面围堵问题求解

在图2中的实线圆表示的是嫌犯理想状态下的逃逸圆, 而现实围堵路口如图3所示。

实际追逃布控圈的博弈转化为给定平面 (可能逃逸圆) 范围内的一个有限点集合 (各逃逸路口) , 如果给定其边界上或内部的任意多个点, 连接这些任意点的所形成的线段, 可将该范围内的所有点都被包含在该多边形的边界上或内部, 则该多边形为凸多边形, 也称凸包。图3即为凸包实例。

由于只要计算凸包最外层形成封闭路口的子集合, 避免了对圈内所有路口的遍历, 由此降低了时间复杂度。动态规划法的复杂度为O (N3) , 而凸包算法的复杂度为O (NLg N) 。相比较其他算法, 本文提出的算法效率是以几何级数提升。

街面围堵问题求解可看成在二维平面中凸包问题的求解, 可通过设置一个关于候选点的堆栈来解决。基本思路是将给定范围内N点都入栈, 非凸包顶点的点最终被弹出栈, 算法终止时, 栈中仅留下凸包的顶点, 并将边界上各顶点按逆时针方向排序。

具体方法是首先找到给定范围内N点, 设这些点为P (0) …P (n-1) , 第一步:找到最下最左边的点P (0) , 选n个点中Y坐标最小的点 (最下面) , 若坐标值相同, 则找X坐标最小的点 (最左边) , 其时间复杂度为O (N) , 第二步:将所有的点N相对于P (0) 进行极角排序 (时间复杂度为O (Nlg N) , 第三步:建凸包栈, 以保存当前的凸包点, 对排序后队列中的点, 如果当前点与栈顶的两个点不是“向左转”, 表明当前栈顶的点不在凸包上, 将其弹出栈, 重复这一个过程直到正在考虑的点与栈顶的两个点是“向左转”的。

所谓的极角排序其实只需计算两个向量的叉积 (向量积) 结果来判断两个向量的相对位置, 假设三个点分别是P (1) P (2) P (3) , 则它们的有向面积为式 (1) :

若其结果为0, 这三个点为共线, 若结果为正, 这三个点是左手系的, 反之为右手系。

3 追踪与逃逸问题分析

街面围堵实质是经典的追踪与逃逸问题, 通常以现代控制理论的状态空间分析为基础, 采用各种算法得到状态方程的解。状态空间分析法解该问题也称为微分博弈, 为此需对此问题建立一般的状态方程, 如式 (2) :

式 (2) 中的L'=F (P, V, T) 是嫌犯和布控区域内各警力的状态向量, 包括位置、速度和时间等变量的状态, L'是对移动距离L的时间微分为围堵布控点的相关位置向量;V为嫌犯与警力的速度向量;T为时间变量;T0为嫌犯作案逃窜时间;T1为接报警时刻。为简化起见, 本文采用T1为状态方程的初始时点;L'0=V0为嫌犯的移动速度;L'n=Vn, n=1, 2, …, N为区域内N个警力的移动速度。式 (2) 的初始条件Ln (t1) '=Vn (t1) , n=0, 1, 2, …, N是嫌犯案发点和区域内各警力接报警后的初始速度。

本方案封闭布控路口节点的目标集为式 (3) :

S是嫌犯及区域内各警力接报警后期望到达i个围堵布控圈各路口节点Pi的集合, 其中, i=1, 2, 3, …, I;当i=0时, P0 (t1) 为接报警T1时刻的嫌犯可能位置, P0n (t1) 为布控区域内各警力的初始位置。

性能指标是实现最优目标意义的评价函数, 在追踪与逃逸过程中, 嫌犯希望最短时间内离事发点的距离越远越安全, 这属于末值性指标, 亦即期望逃逸距离最大化的性能指标, 可用式 (4) 表达。

而警察则期望封闭布控圈离事发点的范围越小越好, 用围堵圈的面积最小作为指标, 属于积分型性能指标, 用式 (5) 来表达, 亦即追求性能指标为最小。

由于积分型指标计算较为繁杂, 为此可以将积分型指标转化成末值型指标。首先, 由于面积大小与该面积的周长成正比, 故式 (5) 性能指标J由面积积分型性能转化为周长型性能指标式 (6) 。

其次, 将性能指标的周长转化为速度与时间的乘积, 由此式 (6) 性能指标Jn可写成末值型指标式 (7) :

性能指标式 (3) 是实现最短时间内逃逸的距离最远, 而性能指标式 (7) 是实现最短时间内布控圈的周长最短, 两个性能指标均为末值型, 且均与距离和时间变量相关, 上述推导为下一步的实际应用提供基础计算依据。

在实际围堵问题应用中需要对上述一般状态方程进行实例化:设案发地为Pt 0, 案发时间为T0, 犯罪嫌疑人的逃逸速度为V0。警务指挥中心在案发T1分钟后接到报警, 该T1时刻的各警力位置为P01 (t1) , P02 (t1) , …P0n (t1) , n=1, 2, …, N。案发后的T分钟后, 嫌犯可能出现在离P0 (t0) 点为P0i (t1) 、位置处, i=1, 2, …, I。当IN时, 说明警力可实现封闭布控, 否则为非封闭布控。

由上述分析可知, 案发后T时刻的嫌犯位置不是一个点, 而是一个可能达到的范围圈, 因此, 指挥中心在布置警力时的首要条件是实现IN的警力配置, 而最小配置为I=N, 以下计算以此为据。

将式 (2) 实例化, 则嫌犯和警察的状态方程为式 (8) 和式 (9) :

式 (8, 9) 中P0i=P (X0i, Y0i) 是接报警t1时刻嫌犯和各警力的初始位置, Vi为嫌犯和警力的移动速度, i=0, 1, 2, …, N, Vi可为定常或可变速度, 为计算简单起见, 一般情况下可设Vi为定常。封闭路口目标集S中的每个目标位置P如式 (10) :

若设性能指标J为嫌犯从接报警时刻到封闭路口集S中的每个Pi时间都小于等于警察达到该Pi的时间, 则性能评估指标J可写成式 (11) :

式 (11) 的评估指标J表明了布控节点的计算方法:只要依据嫌犯的逃逸速度, 即可估算出嫌犯可能逃逸的最远距离。同理, 依据接报警时刻各警力所在位置和移动速度, 可计算出各警力的最大移动范围。

为直观说明追踪围堵问题需进行简化, 从图2中可看到, 最内圈是接报警时刻嫌犯可能离开案发原点的距离圈, 最外圈是实现封闭围堵所需警力圈, 各警力的可管辖范围分布是用虚实线标注的小圈, 中间用实现标注的是警力与嫌犯之间的追逃博弈圈或称布控圈。

对于一般的微分博弈解需要按极大值原理构造哈密顿函数来找到其鞍点, 而在此则可作简化。能否封闭布控圈决定于最远的警力到达任务点的时间, 该时间是嫌犯可能逃逸的最远距离, 而该距离又涉及到需要调集的警力位置。因此, 该追逃博弈问题的解是在多长时间内所调度的警力以形成封闭圈, 而在相同时间内嫌犯可能逃逸的范围。

4 围堵算法的实现

在实际围堵布控应用中, 在给定时间条件下嫌犯可能逃逸的范围可用上节提出的凸包算法求出。为便于推导起见, 先假定系统以定常速度计算, 且不考虑路径曲折情况, 将其直线化。则嫌犯从案发地Pt 0到凸包各节点Pi所费时间T0i可用线性函数式 (12) 来表达:

同理, 各警力从各自岗位Pj到达Pi位置所需时间为式 (13) :

对于式 (12) 和式 (13) 理论上和实际中同样可推广到非定常速度和多折段道路情况。依据性能评估指标J (式 (11) ) , 各警力的移动速度是已知的, 嫌犯可按其最大可能逃逸速度估算, 且嫌犯与警力的t∈[t1, T]时间是相等的, 因此要使评估指标J达到最小的问题简化为:速度与时间乘积数最大的警力到达指定布控节点与嫌犯到达该节点相等, 可用式 (14) 表达。

图3是逃堵博弈示意图, 嫌犯计有12个出逃路口, 有4个警力集结点, 需要派出12组警力实施围堵。实际围堵情况并非如图3理想, 可能存在各集结点警力非均匀分布, 因此理论上需要计算每个警力集合点对每个布控路口的距离和时间, 如图4所示。

以图4为实例, 案发原点为P (0) , 警力集结点有4个, 嫌犯和警力的目标集为12个节点, 假定4个集结点都能满足到达12个目标集的警力, 则依据式 (12) 和式 (13) 可计算出到达嫌犯和警力到目标集的如下时间矩阵T。

由于本文对于嫌犯的逃逸范围采用凸包算法即可得出目标集Pi, 因此对上述时间矩阵T不需要进行全遍历算法, 其具体计算步骤如下:

第一步, 设定期望在什么管辖范围内抓捕住嫌犯;第二步, 采用Graham算法建栈计算此范围内嫌疑可能到达的封闭节点数H;第三步, 依据对嫌犯逃逸速度的估算以得出到各节点Hi所需时间t0, i;第四步, 依据各集结点警力数, 对Graham栈内各节点Hi进行匹配计算, 凡满足性能评估式 (11) 的节点出栈, 由此可知其时间复杂度为O (H×Lg H) , 空间复杂度为O (H) , 综合复杂度为O (H×Lg H) 。通过以上步骤实现围堵时间最短和警力调度最少的封闭布控圈计算。

5“一键布控”的应用实例

本文提出的基于状态空间分析的街面围堵博弈算法在上海市公安局应急指挥系统中得到了应用。对于应急现场指挥人员并不需要了解具体算法及原理, 为实现更直观的用户体验, 采用“一键布控”方式, 操作人员只需在警用地理信息系统 (PGIS) 中用鼠标以案发原点标注一下, 系统自动产生“雷达图”和对应的扩散凸包圈各节点, 以及现场各警力所在位置的覆盖范围和通信方式, 以提供辅助指挥决策。

“一键布控”作为PGIS的应用模块, 自动实现如下功能:当鼠标点击案件发生位置时, 查询以此点为圆心的各道路路口的空间位置信息, 采用Graham扫描算法得到逐层凸包。并叠加计算警力对各凸包节点的覆盖范围。由于各警力和移动速度是已知的, 只要输入估算的嫌犯移动速度, 系统自动计算各警力能形成各层封闭布控圈所需时间。以每层布控圈为单元, 按每个包围圈的路口上至少有一个警力及各警力当前位置到节点距离尽量短为分配原则, 形成警力分配预案, 以上预案是基于嫌犯随机移动位置还未发现时状况。若在某个位置发现了嫌犯, 则重新标注原点, 防止嫌犯返回逃窜, 系统再次重复上述功能并记录各预案轨迹。

6 结语

本文对公安领域信息化建设中新技术的应用提出了一些设想:社会经济发展导致的大规模人员流动, 由此带来的街面犯罪率高发对社会治安带来的负面影响不可忽视。公安部门作为治安管理主体具有义不容辞的责任, 如何利用高科技手段, 实现快速、准确、高效打击和动态防范是新形势下的课题。本文提出基于状态空间分析的街面围堵凸包算法模型是一种尝试, 由于通常的动态规划或Floyd贪心算法其复杂度太高, 实用性较弱, 为此采用时空复杂度均更优的Graham算法, 并在实践中得到应用, 满足了现场指挥辅助决策过程不大于10秒的性能指标。

在实际应用中, 纯凸包算法也并不是最优的, 因为该算法完全是在点的层面计算, 而凸边形上的节点并不是全部都用作围堵路口, 且有些凹型节点存在可能更合理。本文提出的围堵闭集的计算方法, 完全是基于路口、路段的几何关系, 但鉴于城市道路的复杂性, 道路间的完全连通性是未知的, 即并不能预先知道犯罪嫌犯是否仅通过凸边形内部的路口到达围堵节点。对于这种冗余, 可认为是不可预知冗余。故本文研究的算法虽然不影响对嫌犯实施封闭围堵, 但可能导致最终计算的围堵方案中会存在实际不可预知的冗余路口。下一阶段我们将研究如何去除这些不可预知的冗余, 尝试改进该算法在街面围堵方面的应用。

尽管有冗余等问题的存在, 基于状态空间分析的凸包算法其计算理论具有体系化, 对围堵模型的建立有相当大作用, 在实际应用中发挥了重要作用。

参考文献

[1]陈仁爱, 刘婷, 冯贤财, 等.基于优化模型的街面逃逸犯罪嫌疑人的围堵方案探讨[J].科技信息, 2012 (3) :65-66.

[2]杨敏, 牟廉明, 吴亚军, 等.基于闭集的犯罪嫌疑人快速围堵算法[J].计算机工程与应用, 2012 (29) :234-238.

[3]郦志灿.交巡警合一新体制的实践与思考[J].浙江公安高等专科学校学报, 2011 (2) :51-52.

[4]杨俊峰.广州高发性街面犯罪的特点、成因与对策分析[J].广州广播电视大学学报, 2010 (2) :101-112.

[5]朱浩, 张玉.基于改进的Floyd算法求节点间所有最短路径[J].电声技术, 2011 (12) :65-67.

[6]刘宏兵, 邬长安, 周文勇.基于二维凸包的TSP算法[J].计算机工程与设计, 2009 (8) :140-142, 186.

[7]程三友, 李英杰.一种新的最小凸包算法及其应用[J].地理与地理信息科学, 2009 (5) :47-49.

3.状态空间分析总结 篇三

摘 要：针对城市公共交通系统中公交优化调度问题的具体特征，提出一种基于状态空间模型的实数编码智能优化算法（SIA）。SIA引入遗传算法（GA）的基本理念。通过构造状态进化矩阵来指导算法的搜索方向，再通过选种池的优胜劣汰的选择机理来实现算法朝最优解逼近。将该算法与GA分别应用到公交优化调度问题中，考虑发车时间间隔的约束，建立以企业和乘客的利益最大化为目标的数学模型。实例仿真结果表明，SIA在寻优精度和计算量方面优于GA，验证了该算法的有效性。

关键词：公交调度；时间间隔；状态空间模型；状态进化矩阵；选种池

中图分类号：U491.2TP18 文献标识码：A

Abstract：An intelligent optimization algorithm with real strings based on state space model （SIA） was presented to solve bus dispatching problem in urban public transport system. The basic idea of genetic algorithm （GA） was introduced to SIA. The state evolution matrix was constructed to guide the search direction of the algorithm， then through the selection mechanism of selection pool to approach optimal solution. This algorithm and GA were applied to the public transport optimization dispatching problem. Mathematical model was set up by considering the time interval，and the benefit maximization of enterprises and passengers. The results of example simulation show that SIA is better than GA in optimization accuracy and amount of calculation.

Key words：pubic transport dispatching；time interval；state space model；state evolution matrix； selection pool

1 引 言

随着现实世界中交通拥堵情况日趋严重，调节城市公共交通运营工作成为舒缓交通状况、改善城区生活质量的重要手段之一。城市公共交通运营工作可以转化为公交优化调度问题进行处理，而本文以公交线路发车间隔的设定来进行公交优化，即要求在一个调度周期（公交线路一天的运营时间）内，根据车流情况，在满足整体社会效益和经济效益的情况下，优化各时段的发车时间间隔，以使得公交公司和乘客花费成本最低。随着对公交优化调度问题研究的不断深入，国内外许多学者提出了大量方法来解决该问题，取得了一定的成果。如Qing和Han[1-2]等人从发车间隔对公交系统的影响出发，提出用遗传算法进行公交车发车时间间隔优化；Gong和Cheng[3-5]等人了改进型遗传算法用以优化发车频率问题；文献[6]通过两种算法融合，采用优势互补的特点为优化公交调度问题提供了一种有效途径；文献[7-9]则分别介绍了不同算法在求解公交调度问题最优解过程中的方法。

以上所提及的优化方法对于本文进行优化公交车调度问题具有重要的指导意义。本文提出一种基于离散系统状态空间模型的实数编码智能优化算法[10]。由于状态空间模型的引入不仅能把种群信息以最小信息形式描述出来，而且还能清楚显示算法迭代寻优过程中个体的状态变化，因而该模型可以将问题的求解过程表示为动力学求解过程。基于此，该算法通过构造一个状态进化矩阵来替代遗传算法中的交叉与变异算子功能来产生一组进化解。通过选种池的选择作用产生较优解。相比于遗传算法易陷入早熟停滞、计算量大和局部搜索能力差等缺点[11]，本文提出的算法具有计算量较小、计算精度较高、计算速度较快等特点。最后给出一个公交车发车时间间隔优化实例，仿真结果验证了这种算法的有效性。

2 基于状态空间模型的智能优化算法

2.1 概述

近年来，国内外有不少学者热衷于用不同的方法来解决公交调度优化问题。其中，遗传算法成为人们寻求解决优化问题的重要途径，它通过迭代执行选择、交叉、变异三个遗传算子的遗传操作，使问题的解逐步向最优解方向靠近。本文提出的基于状态空间模型的实数编码智能优化算法是一种以离散系统状态空间模型为基础，引入遗传算法理念的优化算法。它将实数编码问题的解方便地以状态空间模型的方式表示，使得问题的求解过程更直观、高效。

基于状态空间模型的智能优化算法将问题的求解过程表示为离散系统的动力学求解过程，即X′（k+1）=GX（k）（1）其中，状态向量X（k）表示为第k代群体，它是一个N×M矩阵（N表示为种群中个体总数量，M为每个个体包含的变量数）。G为状态进化矩阵（N×N方阵），G的构造是本算法研究的核心内容，可以依照遗传算法的基本思想构造。本文以遗传算法的基本理念构造G，此矩阵替代了在遗传算法中起交叉、变异的遗传操作。本算法采用在约束范围内随机生成的方式来产生初始群体X（0），再通过G矩阵生成群体X′（1），即种群X（k）通过G矩阵生成新的种群X′（k+1）（k=0，1，….）。在种群X′（k+1）中判断其个体是否满足算法约束条件，若不满足，则需进行约束处理，再将包含X（k）与X′（k+1）的共2N个投入选种池。选种池是依照遗传算法中优胜劣汰的思想启发而设计，通过计算2N个个体适应度函数值选择适应度值较大的N个个体组成新一代群体X（k+1），再置X（k+1）为X（k），如此循环迭代，直到满足停机条件后结束，如图1所示。

3 SIA用于公交优化调度

3.1 公交优化调度问题的数学描述

1）模型假设条件

公交发车时间间隔模型的建立要考虑到多种因素的影响，如公交公司满意度、乘客满意度、运行环境等。在同一时段内，若发车间隔较短，公交公司发车次数较多，平均每辆车的载客量减少，环境污染指数升高，不利于公交公司的经济效益和社会效益；若发车间隔较长，乘客平均等待时间较长，乘客的时间损失较大，会影响乘客的情绪，车内人流拥挤，也会影响乘客的舒适度，从而进一步影响乘客一天的生活和工作质量，乘客损失费用较高；若公交车运行环境拥挤，平均每辆车走完全程耗时相对较多，影响公交公司和乘客的整体利益，应适当的调整发车间隔，以舒缓城市交通环境。综上所述，本文对此模型作如下假设：

（1）公车各时段运行环境良好，且营运期间无特殊状况发生；

（2）公车运行期间为恒速行驶；

（3）公车额定载客人数相同；

（4）公车运营一趟的成本为固定值；

（5）同一时段公车发车频率相同；

（6）各时段内到达站点的乘客服从均匀分布；

（7）将乘客上下车时间算入等车时间；

（8）全程实行统一票价，票价2元/人。

2）数学模型的建立

从以上仿真结果可以看出，在α=0.7的情况下，即充分考虑公交公司利益时，发车间隔明显比其他两种情况大；α=0.3时，充分考虑乘客利益，发车间隔明显比其他两种情况小，符合现实情况。同时，根据表2中的客流情况可以看出，时段1和时段4的客流量相对较大，在仿真结果中，这两个时段的发车间隔整体较其他时段小，达到了根据客流合理分配发车间隔的目的。对比GA和SIA优化的发车间隔及其对应的目标函数，可以看出SIA的优化结果明显优于GA，SIA有效性得到验证。

相较于传统遗传算法，SIA的优势在于，通过状态空间模型中矩阵的乘法操作来搜索可行域区间，替代了GA的交叉和变异操作，也在一定程度上减小了算法的计算量。同时，SIA采用实数编码，虽然需要对连续的可行域区间进行离散化，但离散化的计算量较小。而一般情况下，GA采用二进制编码，编码长度决定了算法的寻优精度，精度要求越高，算法编码越长，过长的二进制编码在解码的过程中大大增加了算法的计算量，影响算法效率。故在对寻优精度要求更高的情况下，SIA的优势更加突出。

5 结 论

本文针对公交车调度优化中传统智能算法的不足，提出了一种基于离散系统状态空间模型的实数编码智能优化算法。主要分析了SIA相较于GA在寻优精度和计算量方面的优势。仿真结果表明，在相同的算法条件下，SIA的优化结果明显优于GA，验证了SIA的有效性。参考文献

[1] 韩印.基于遗传算法的智能公交发车频率优化研究[J].计算机工程与应用，2008，44（33）：243-245.

[2] 覃运梅，王玲玲.基于遗传算法的公交发车间隔模型[J].交通标准化，2009，（2）：190-192.

[3] 龚成清.改进遗传算法在公交调度优化中的应用[J].微型电脑应用，2012，28（10）：48-51.

[4] 陈玲玲，苏勇.改进遗传算法在公交车优化调度中的应用[J].科学技术与工程，2009，9（12）：3567-3569.

[5] Jinling Du， Chunxiao Wang， Feng Zhang. Multi-objective Optimization of Bus Dispatching Based on Improved Genetic Algorithm[C]//2011 Seventh International Conference on Computational Intelligence and Security.China：IEEE，2011.

[6] Minan TANG， Enen REN， Chunyan ZHAO. Route Optimization for Bus Dispatching Based on Genetic Algorithm-Ant Colony Algorithm[C]//2009 International Conference on Information Management， Innovation Management and Industrial Engineering.China：IEEE，2009.

[7] 付阿利，雷秀娟.粒子群优化算法在公交车智能调度中的应用[J].计算机工程与应用，2008，44（15）：239-241.

[8] 王敏.免疫克隆算法求解公交发车频率问题[J].计算机应用研究，2010，27（12）：4483-4485.

[9] 白子健.快速公交线路组合频率优化的禁忌模拟退火算法仿真[J].计算机应用研究，2008，25（2）：355-358.

[10]李茂军，贾玲. 一种基于状态空间模型的进化算法[J]. 计算技术与自动化. 2014，33（2）：85-88.

4.状态空间分析总结 篇四

一、指标选取和数据来源

1、指标选取

(1) 金融发展指标。金融发展指标选用金融发展规模、金融发展效率、股票市场发展水平、保险市场发展水平4个指标来反映。第一, 金融发展规模指标用G oldsm ith (1969) 提出的金融相关率指标表示, 等于金融资产总量与名义G D P之比。由于湖北省数据的缺乏, 同时存贷款余额之和占金融资产的大部分, 参照周立 (2002) 的做法, 选取存贷款余额之和代替金融资产总量。第二, 金融发展效率指标, 有很多关于衡量金融发展效率的表示方法, 我们选用金融机构贷款余额与存款余额的比值来表示。第三, 股票市场的发展水平, 一般用股票市场的筹资额与G D P之比来代表。由于无法收集到山东省股票市场的直接统计数据, 放弃该指标。第四, 保险市场的发展水平指标用保费收入与G D P之比表示。

(2) 经济开放度指标。经济开放度反映了一国对外开放的程度, 涉及贸易、资本、劳动力等多方面, 因此对于经济开放度指标的度量存在许多不同见解。通常认为经济开放度指标的选取应当以经济发展阶段、贸易发展水平和对外开放的特点为依据和原则, 同时也要考虑测度指标数据的可得性及实用性。因此, 本文选取外贸依存度和外资依存度之和作为经济对外开放度的指标。这样选取有两个原因:第一, 对外贸易是山东省外向型经济发展的主要形式, 可以用外贸依存度来衡量;第二, 引进外资是山东省对外开放的重要体现, 可以用外资依存度来衡量。

金融发展规模、金融发展效率和保险市场发展水平分别用X 1、X 2、X 3来表示。经济开放度用Y来表示。

2、数据来源及说明

所有数据均来自《山东省统计年鉴》各期的数据, 以及中国人民银行网站, 并在此基础上通过整理计算而得, 使用Eview s5.0软件进行数据分析和处理。

由于无法收集到山东省1997年之前保费收入的统计数据, 本文通过SPSS17.0软件进行了缺失值的弥补。

二、实证分析

状态空间模型起源于平稳时间序列分析。如果是非平稳的时间序列, 则要求变量之间具有协整关系, 否则所建立的模型将是伪回归。因此, 首先要对变量进行平稳性检验, 如果非平稳, 还应进行协整检验。

1、平稳性检验

下面采用最常用的A D F检验对X 1、X 2、X 3和Y进行平稳性检验, 检验结果如表1所示。从表1可以看出, 这四个变量的A D F值都小于10%显著性水平下的临界值, 即都是平稳的时间序列, 不需再进行协整检验。虽然为平稳的时间序列, 可以用经典的回归分析方法建立因果关系回归模型, 但是具体的因果关系还不确定。因此, 需要进一步检验变量之间的因果关系。

2、格兰杰因果关系检验

采用格兰杰因果关系检验法检验山东省金融发展与经济对外开放度之间的因果关系, 以确定状态空间模型中变量之间的因果关系, 检验结果如表2所示。

从表2可以看出, 在10%的显著性水平下, 只有金融发展规模是经济对外开放度的格兰杰原因;从经济对外开放度对金融发展的影响来看, 它并不是金融发展规模、金融发展效率、保险市场发展水平的格兰杰原因。

3、状态空间模型的估计结果分析

研究金融发展与经济对外开放度之间关系的传统方法, 一般是使用静态的固定参数模型, 但是当时间跨度较大时, 固定参数模型无法反映出由于不可观测原因对两者相关程度带来的变化, 所以估计出来的结果可能存在较大偏差。在计量经济学中, 动态系统的状态空间模型可以反映相关程度的变化, 主要有两点好处:第一, 状态空间模型将不可观测的状态变量并入可观测模型并与其一起得到估计结果;第二, 状态空间模型求解算法的核心是K alm an滤波, K alm an滤波是在时刻t基于所有可得到的信息计算状态向量的最理想递推过程。

通过上述分析, 可以建立如下的状态空间模型:

量测方程:Yt=c+αtX 1+μt

状态方程:αt=c1αt-1+νt

上式中, Yt和X 1是可观测变量。可变参数αt是随时间改变的, 体现了解释变量对被解释变量影响关系的改变, 称为状态向量, 是不可观测变量, 是待估计的。上述模型假设状态向量为A R (1) 过程, 也可以假设状态向量为其他过程, 但检验结果表明A R (1) 过程拟合效果最佳, 因此选用这种形式。

使用Eview s5.0软件估计结果为:

量测方程:Yt=0.572508+αtX 1

状态方程:αt=0.996236αt-1

变参数αt的曲线图如图1所示, 可以看出, 1988年以来, 山东省金融发展规模对经济对外开放度的影响变化比较大, 且1988—2009年, 金融发展规模对经济对外开放度一直呈现负面影响。1989年, 金融发展规模的乘数下降最大, 在此以后, 金融发展规模的乘数在-0.30946到-0.10802之间;1989年以后, 金融发展规模的乘数基本上呈上升趋势, 虽仍呈负面影响, 但这种影响正在逐渐减弱。

三、结论与建议

由上述实证分析的格兰杰因果关系检验可知, 选取的3个金融发展指标中有2个, 即金融发展规模是经济对外开放度的格兰杰原因;经济对外开放度并不是3个金融发展指标的格兰杰原因。这说明山东省的金融发展给经济开放带来了发展动力, 有积极的促进作用;然而, 经济对外开放的发展并没有促进金融发展规模的扩大和效率的提高, 也没有带动保险市场的发展。

从状态空间模型的结果来看, 1989年后, 金融发展规模对经济对外开放度的影响基本上呈上升趋势, 但截至2009年, 这种影响还是负面影响, 一直未呈现正面影响。但负面影响在逐渐减弱, 有望在将来呈现正面影响, 并逐渐加强。

山东省是我国的经济强省之一, 伴随着经济的快速增长, 金融业也得到了较快的发展, 但缺乏一个与经济增长相匹配的金融发展水平, 且山东省的金融结构是银行主导型的, 相对于股票市场而言, 银行体系在经济发展中发挥着更重要的作用。因此, 促进金融发展对山东省的金融部门和对外贸易部门都有着非常重要的意义。金融发展可以为外资企业提供更有效的融资渠道, 提高在国际分工和国际竞争中的地位, 从而促进经济对外开放的进一步深入发展。目前, 山东省应该努力提高商业银行的资产质量, 从微观上改善经营机制, 从宏观上营造良好的竞争环境, 从内外两方面推动商业银行真正按市场规律进行资金配置, 改变金融中介资源配置效率偏低的状况;同时应该发展多元化金融机构体系, 大力发展非国有金融机构和非银行金融机构, 满足各种各样的需求, 促进金融机构的良性竞争, 提高效率;加快建立并完善多层次的金融市场, 促进资本市场、货币市场和保险市场的有效结合, 建立起与产业结构相适应的金融体系和大型的金融控股集团, 解决股权分散、优势不集中的问题, 发挥金融控股集团在多元化金融服务、分散和防范风险、平衡现金流、金融创新等方面的作用。推动证券市场发展, 为企业提供更有效的直接融资渠道, 满足企业对外发展时对金融支持的多样化需求, 从而实现金融发展与经济对外开放的协调发展。

参考文献

[1]兰宜生:对外经济开放度与地区经济增长的实证分析[J].经济研究, 2002 (2) .

[2]沈能:金融发展与国际贸易的动态演进分析——基于中国的经验数据[J].世界经济研究, 2006 (6) .

[3]曲建忠、张战梅:我国金融发展与国际贸易的关系——基于1991—2005年数据的实证研究[J].国际贸易问题, 2008 (1) .

[4]赵曦、刘耀林:湖北省经济对外开放度研究[J].地域研究与发展, 2005 (3) .

[5]胡金焱、朱明星:山东省金融发展与经济增长相关性的实证研究[J].山东社会科学, 2005 (1) .

[6]耿颢:山东省金融深度和金融宽度实证分析[J].金融发展研究, 2009 (10) .

5.状态空间分析总结 篇五

关键词：MATLAB,图形用户界面,现代控制理论,仿真

0引言

MATLAB是矩阵实验室(Matrix Laboratory)的简称,是由美国MathWorks公司发布的一套主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。其应用范围非常广,包括数值分析、工程与科学绘图、控制系统的设计与仿真、数字图像处理技术、数字信号处理技术和通讯设计与仿真等。本文主要应用了MATLAB的GUI图形用户界面来实现《现代控制理论》主要内容的仿真。

1现代控制理论与GUI

1.1 现代控制理论

现代控制理论是对古典控制理论的进一步发展,它包括线性系统理论、最优控制、现代系统辨识及自适应控制等多个分支。对现代控制理论做出重大贡献的有苏联科学家JI.C庞特里亚金提出的名为极大值原理的综合控制系统的新方法、美国贝尔曼(Bellman)的动态规划和匈牙利卡尔曼(Kalman)的滤波、能控性与能观性理论。这些研究成果解决了空间技术中出现的复杂控制问题,并开拓了控制理论中最优控制理论这一新的领域。这些就构成了后来被称为现代控制理论的发展起点和基础[1]。现代控制理论以线性代数和微分方程为主要的数学工具,以状态空间法为基础,分析与设计控制系统。

状态空间法对揭示和认识控制系统的许多重要特性具有关键作用。其中能控性和能观性尤为重要,成为控制理论的两个基本概念。现代控制理论在其诞生的近50年来,不论在理论还是应用方面一直处于十分活跃的状态,不仅在航空航天领域取得了惊人的成就,而且在自然科学和社会科学领域都得到了广泛的应用[2]。

1.2 用户界面

用户界面(或接口)是指用户与计算机信息交换的硬件、软件部分。图形用户界面(Graphical User Interfaces ,GUI)是指采用图形方式显示的计算机操作用户界面,是指由窗口、菜单、对话框等各种图形对象组成的用户界面。在这种用户界面下,用户必须对功能对象进行界面布局和编程,从而使用户在激活GUI 的功能对象时能够执行相应的行为。

MATLAB提供了一个可视化的图形界面开发环境GUIDE(Graphic User Interface Development Environment)。 GUIDE是一个界面设计工具,且所有GUI的控件都集成在这个环境中并提供界面属性、外观和行为响应方式的设置方法。GUIDE将程序员设计好的GUI界面保存在一个FIG文件中,同时还自动生成一个M文件。这个M文件为实现回调函数提供一个参考框架,这样既简化了GUI应用程序的创建工作,程序员又可以直接使用这个框架来编写自己的函数代码[3,4]。

GUIDE可在布局GUI的同时生成以下两个文件:①FIG文件,该文件包括GUI的图像窗口和所有子对象(包括用户控件和坐标轴)的完全描述以及所有对象的属性值;②M文件,该文件包括用户用来发布和控制界面和回调函数(这里作为子函数)的各种函数。该文件中不包含任何组件的布置信息[5]。

2用MATLAB的Control Toolbox完成软件设计

2.1 设计的步骤

设计步骤具体如下:①打开MATLAB,新建一个GUI;②在GUI界面中加入能完成实验的相应控件,如pushbutton(按钮)、static text(静态文本)、edit text(可编辑文本)、panel(面)、axes(坐标轴)等;③把相同类型的按钮放在同一个panel中,并布局好整个界面,使其看起来整洁美观;④修改各个控件的属性,以便在界面上观察其具体作用;⑤对各个按钮进行回调函数的编写,使其达到它的功能,这是设计GUI中最关键的一步;⑥对整个界面进行运行,就会得到相应的结果。

2.2 设计出的人机交互界面

设计出的人机交互界面见图1。

2.3 人机交互界面中控件的回调函数

(1)状态空间模型转换为传递函数模型的回调函数:

function pushbutton1_Callback(hObject, eventdata, handles)

h=handles.edit1;

ss=str2num(char(get(h,'String')));

A=ss

h=handles.edit2;

ss=str2num(char(get(h,'String')));

B=ss

h=handles.edit3;

ss=str2num(char(get(h,'String')));

C=ss

h=handles.edit4;

ss=str2num(char(get(h,'String')));

D=ss

[num,den]=ss2tf(A,B,C,D);

num=num2str(num);den=num2str(den);

set(handles.listbox1,'String',char('num=',num,'den=',den))

(2) 能控标准型的回调函数:

function pushbutton3_Callback(hObject, eventdata, handles)

h=handles.edit1;

ss=str2num(char(get(h,'String')));

A=ss

h=handles.edit2;

ss=str2num(char(get(h,'String')));

B=ss

h=handles.edit3;

ss=str2num(char(get(h,'String')));

C=ss

h=handles.edit4;

ss=str2num(char(get(h,'String')));

D=ss

[Ab,Bb,Cb,T,K]=ctrbf(A,B,C)

Ab=num2str(Ab);Bb=num2str(Bb);Cb=num2str(Cb);

set(handles.listbox1,'String',char('Ab=',Ab,'Bb=',Bb,'Cb=',Cb))

(3)回调函数的脉冲响应:

function pushbutton5_Callback(hObject, eventdata, handles)

h=handles.edit1;

A=str2num(char(get(h,'String')));

h=handles.edit2;

B=str2num(char(get(h,'String')));

h=handles.edit3;

C=str2num(char(get(h,'String')));

h=handles.edit4;

D=str2num(char(get(h,'String')));

sys=ss(A,B,C,D)

%axes(handles.axes1);

impulse(sys)

grid on

3结论

本文提出了用MATLAB的GUI设计图形用户界面,该方法将《现代控制理论》的知识点都体现在GUI中,实现了《现代控制理论》中主要的计算过程,且界面简洁,操作方便。

参考文献

[1]袁德成.现代控制理论[M].北京:清华大学出版社,2007.

[2]刘豹.现代控制理论[M].北京:机械工业出版社,1988.

[3]柴瑞娟.基于MATLAB GUI的线性控制系统教学仿真软件的设计[J].计算机与现代化,2003(9):68-70.

[4]李显宏.MATLAB7界面设计与编程技巧[M].北京:电子工业出版社,2006.

6.基于偏序归约的状态空间约简算法 篇六

安全协议的形式化方法大致可分为三类:形式逻辑方法、模型检测方法和定理证明方法。其中,模型检测方法[1]由于其自动化程度高、发现协议缺陷后能给出攻击路径等特点,得到了工业界和学术界的广泛关注。然而,该方法有一个致命缺陷,那就是状态爆炸问题[2]。此问题导致状态空间无限,协议的安全性问题成为一个半可判定问题。因此,如何有效缓解状态爆炸是模型检测能被广泛使用的一个重要前提,在这方面已有一些重要的方法被相继提出,包括有序二叉判定图技术、偏序归约技术以及符号化技术等。

偏序归约技术[3] 通过消除迹中的冗余变迁序列来对状态可达图进行化简,主要有顽固集技术、睡眠集技术和完备集技术。然而,该技术被提出后,大量相关研究集中于自动验证并发系统,而现有的针对安全协议分析的偏序归约算法较为复杂,不易实现自动化。

本文采用偏序归约的思想,提出了一种诚实主体会话中逆序结点的约简算法以及一种迹等价迁移冗余后继结点的约简算法,并通过相应的实例,验证这两种简单的算法,有效地约简了安全协议的状态空间。

1 相关研究

在过去的二十多年中,许多研究者对偏序约简算法在模型检测中的应用做了大量的工作,并从两方面对该算法进行改进,一方面是对算法本身加以改进;另一方面是与其他技术相结合进行改进。但是这些改进大都针对并发系统研究理论层面的定义和证明。

文献[4]等人首次形式化地提出一个偏序归约算法来判定安全协议的安全属性。该算法最初应用于模型检测器BRUTUS中检测安全协议。但由于该算法假设安全协议是没有分支的,也就是说每一个协议的参与者在任意状态最多能够执行一个动作,而在实际应用中认证协议及公平交换协议都存在分支,所以该算法无法用来检验此类分支安全协议。文献[5]等人提出一个偏序归约算法分析安全协议。与Clarke等人相比,该算法更加有效地约简了状态空间,但是仅能检验一类有限的安全属性。且由于该算法极其依赖深度优先搜索策略,无法轻松地嵌入广度优先搜索算法中,限制了其适用范围。文献[6]扩展文献[4]提出的偏序归约算法,使其能够检测分支安全协议。但存在的不足之处是算法较为复杂,不易实现。

我国学者对偏序归约技术的研究亦非常重视。文献[7]提出“束动作变迁”的概念。这种处理进程变迁的方式不同于基于迹理论采用偏序归约以减少并发模型状态数目的方法,而是将完全并发的动作看成一个“大动作”,但是他们仅提出了理论层面的定义和证明。文献[8]将偏序归约应用于进程代数模型,给出了进程代数模型的偏序简化算法,并且提出验证安全性的方法,但是他们未给出相关的实验结论。

从上面的情况可知,当前偏序归约技术研究主要集中于自动验证并发系统,而针对安全协议分析的偏序算法尚未考虑过约简诚实主体会话中的逆序结点。

2 状态空间约简算法

对状态迁移空间的分析可以看出,在协议的状态空间中存在着大量冗余状态。主要有两方面的问题,一方面有些状态迁移的序是与实际情况不符的;另一方面是有些迹等价的迁移关系,它们的后继结点中存在着大量相似的结点。本文以简化的Needham-Schroeder公钥认证协议为例,分析状态空间中发现的两类冗余状态。

2.1 基本概念

偏序归约是一种基于迹的状态化简技术,它通过消除迹中的冗余变迁序列来对状态可达图进行化简,以减少模型检测过程需要被搜索的状态数,提高检测效率。其基本思想如下:选取一个代表元代替所有迹等价的迁移关系组成的等价类,约简等价类中的其它关系。下面简单介绍迹等价涉及的基本概念。

定义1 在状态空间的一条路径π=s1→s2→…上,将状态迁移关系s1→s2定义为α,s2→s3定义为β,则该路径可以表示为$\pi =s{}_1\stackrel{\alpha }{\to }s{}_2\stackrel{\beta }{\to }\cdots ‚s{}_1\stackrel{\alpha }{\to }s{}_2$也写作α(s1,s2),也可记作s2=α(s1)。

定义2 如果两个迁移关系α、β对于任意可作用的状态s都有α(β(s))=β(α(s)),则称α、β相互独立。即对于状态s而言,对其先应用迁移关系α再应用迁移关系β和先应用迁移关系β再应用迁移关系α得到相同的状态,$s\stackrel{\alpha \beta }{\to }t$且$s\stackrel{\beta \alpha }{\to }t$。

定义3 对于相互独立的两个迁移关系α、β,组合关系αβ和βα就称为迹等价的。

2.2 诚实主体会话中的逆序约简

为了模拟安全协议中的攻击行为,将参与协议的主体分为两类:诚实主体和攻击者。诚实主体严格按照协议规范正常运行协议,如果收到与协议规范不一致的消息,则认为与自己无关,不做响应;另一类主体为攻击者(Intruder),也称为敌手,企图利用协议的缺陷获得非法利益。模型中一般只有一个攻击者,通过攻击者模型描述在实际情况中所有攻击者的能力。

状态空间中,某状态所有可能的后继状态集合是该状态应用规则集中所有单条规则的并集,而并未对会话顺序做任何限制。因此,诚实主体间的会话可能由于攻击者具备在任意时刻随意构造并发送消息的能力,存在着逆序现象。但实际上诚实主体会严格按照协议规范运行协议,因此诚实主体运行协议的逆序是无意义的,逆序结点是可以安全删除的。

以NSPK协议为例,介绍诚实主体间的会话存在的逆序现象。

例1:假设初始情况下有三个主体参与协议:a、b和i,其中,a、b表示诚实主体,i表示攻击者。则a与b的会话中存在以下运行路径:

1:i→b:{(x105,a)}kbm1

1′:b→i:{(x105,nb1)}kam′1

2:i→a:startm2

2′:a→i:{(na1,a)}kbm′2

其中,x105是攻击者i为随机数NA赋的值,我们不关心其具体取值,以x105代替。

在上述会话中,诚实主体b发送消息{(x105,nb1)}ka后,a发送消息{(na1,a)}kb。但在协议的正常运行顺序中,a发送消息{(NA,A)}KB后,b才能发送消息{(NA,NB)}KA。因此,该运行路径违反了NSPK协议的正常运行顺序,属于状态空间中的逆序现象。

针对上述情况,本文根据偏序归约的思想,将诚实主体所有可能的交互顺序,作为一个等价类,选取按照协议规定顺序的序作为代表元,从而约简其它序及相关的中间状态。具体实现时,在协议规范中加入步骤标识的字段,应用规则时,对于诚实主体之间的会话,只有在符合步骤标识顺序的情况下才进行状态迁移,否则不迁移。

具体算法如下:

该算法输出为空,后继状态的列表存储在pSuccessors中,以指针的形式传递。其中,状态state中的MaxStep用来存储会话1的最大步骤号,也就是诚实主体间的会话的最大步骤号。每一个状态事实s中的session用来表示该状态事实所在的会话号;而s中的step用来表示该状态事实的步骤号。

规则的具体形式为:{P,N}⇒{P′,N′,SP},表示状态中的某主体收到消息N时,首先将状态内的状态事实P由P′代替,然后发出消息N′,最后将SP的安全属性描述添加到状态的安全属性描述中去。规则r中的lpFact表示状态事实P。

该算法在求解某状态应用单条迁移规则而产生的后继状态集合的过程中,若迁移属于会话1,则判断状态事实s中的step是否大于等于MaxStepBuf。若为True,则继续求解。否则跳出循环。

2.3 迹等价迁移的冗余后继约简

文献[4]指出:不同会话间的迁移关系是互相独立的。因此,对于状态s而言,对其先应用某一会话中的迁移关系α再应用另一会话中的迁移关系β和先应用迁移关系β再应用迁移关系α得到相同的状态,$s\stackrel{\alpha \beta }{\to }t$且$s\stackrel{\beta \alpha }{\to }t$。也就是说,s应用迹等价的迁移关系得到相同的后继结点,因此协议的状态空间中存在着大量由迹等价迁移引起的冗余结点。

理论上,我们既可以删除s应用αβ生成的后继结点,保留s应用βα生成的后继结点,也可以删除s应用βα生成的后继结点,保留s应用αβ生成的后继结点。但是,当安全协议的状态迁移系统中引入符号化技术时,一个迁移关系可能代表一组基础状态迁移的集合,因此,s应用迹等价的迁移关系得到的后继结点不完全相同。在某种特殊情况下,我们可以选择性地删除部分后继结点。

以状态s的迹等价迁移为例,解释状态空间中存在的冗余结点。状态s的状态迁移关系如图1所示。

假设m′1和m′2属于不同的会话,所以,状态s先发送消息m′1再发送消息m′2和s先发送消息m′2再发送消息m′1到达相同的协议状态,即p2=p4∧n2=n4∧ik2=ik4∧sp2=sp4。但是由于m′1和m′2的不同发送顺序,s2和s4中的约束集不同,无法任意删除s2或者s4。

通过分析s2和s4中的约束集,发现在m1⊆ik的情况下,s2约束集中的gen(m1,ik)可以约掉,s2的约束集c2=gen(m2,ik∪m′1)。同样地,由于m1⊆ik,则m1⊆{ik∪m′2},所以s4约束集中gen(m1,ik∪m′2)可以约掉,s4的约束集c4=gen(m2,ik)。显然c2≥c4,所以,s4为冗余状态,可以安全删除。

具体算法如下:

其中,某一状态state的Father用来表示该状态结点的父结点;Father.ik用来存储父结点的攻击者知识集;RecvMesg用来表示父结点向该结点发送的消息;RecvMesg.session用来表示父结点向该结点发送消息所在的会话。

该算法判断父结点向状态state发送的消息是否与状态事实s不在同一个会话中,同时父结点向状态state发送的消息不属于父结点的攻击者知识集,且状态state向其后继结点sucState发送的消息属于state的父结点的攻击者知识集。若为真,则在state后继状态的列表中删除状态结点sucState。

3 实验结果

对状态迁移空间的分析,需要有模型检测工具的支持才能实现。但利用通用模型检测器检测安全协议时,描述复杂且检测效率不高。因此,对比几种用于分析安全协议的专用模型检测工具后,本文选择安全协议自动化分析系统SPFA[9](Security Protocol Formal Analyzer)作为检测工具对安全协议进行验证。该工具具有如下优点:可以在仅限制协议并行会话数的前提下自动分析安全协议的保密性、弱认证性、强认证性、公平性和非否认性的安全目标,可正确检测类型缺陷、重放攻击。

在专用模型检测工具SPFA应用诚实主体会话中逆序结点的约简算法Successor1(),以及迹等价迁移冗余后继结点的约简算法Successor2(),对NSPK协议进行测试,结果如表1所示。

该表分别列出了采用算法Successor1()前后NSPK协议的状态数,以及在逆序约简的基础上,采用算法Successor2()前后NSPK协议的状态数。可以看出,上述两种算法基本思想都非常简单,但约简的冗余结点数都随着会话的增多而增加,可以有效地约简状态空间,具有广泛的应用前景。

4 结 语

当前,偏序归约技术大多针对并发系统研究理论层面的定义和证明,而针对安全协议分析的偏序归约算法不仅较为复杂,不易实现,限制了其适用范围,且未考虑约简诚实主体会话中的逆序结点。针对上述情况,本文采用偏序归约的思想,提出了一种诚实主体会话中逆序结点的约简算法,以及一种迹等价迁移冗余后继结点的约简算法,并通过相应的实例,验证这两种简单的算法,有效地约简了安全协议的状态空间。

尽管本文引入的约简算法已经对状态空间起到一定的化简效果,但是状态空间约简技术仍有许多值得深入探讨和研究的问题。如引入束动作偏序归约技术[7]是本文进一步研究的一个主要方向。

摘要：目前,针对安全协议分析的偏序归约算法较为复杂且不易实现,限制了其适用范围,未考虑约简诚实主体会话中的逆序结点。针对该问题,采用偏序归约的思想,提出一种诚实主体会话中逆序结点的约简算法以及一种迹等价迁移冗余后继结点的约简算法。两种算法思想简单,易于实现。实例表明,这两种算法有效地约简了安全协议的状态空间。

关键词：模型检测,偏序归约,逆序,迹等价

参考文献

[1]锐薛,冯登国.安全协议的形式化分析技术与方法[J].计算机学报,2006,29(1):1-20.

[2]Pelánek R.Fighting state space explosion:Review and evaluation[C]//FMICS’09,Springer-Berlin/Heidelberg,2009,5596:37-52.

[3]Laroussinie F.Principles of Model Checking[J].The Computer Jour-nal,2009.

[4]Clarke E,Jha S,Marrero W.Partial order reductions for security proto-col verification[C]//TACAS’00,2000,1785:503-518.

[5]Cremers C,MauwS.Checking secrecy by means of partial order reduc-tion[C]//SAM’04,Springer,2005,3319:177-194.

[6]Fokkink W,Torabi Dashti M,AWijs.Partial order reduction for branch-ing security protocols[C]//ACSD’10,IEEE Computer Society,2010:191-200.

[7]王永祥,吴尽昭,蒋健民.进程代数—对称与动作细化[M].北京:科学出版社,2007.

[8]王婷,罗养霞,房鼎益,等.基于偏序简化的并发系统验证[J].计算机应用与软件,2008,25(6):63-67.