有序二叉决策图在防火墙规则库设计中的应用 被引量：4

1

作者 程勇 秦祖福 傅建明 《武汉大学学报（理学版）》 CAS CSCD 北大核心 2006年第1期77-80,共4页

在防火墙规则库的设计中利用有序二叉决策图(ordered binary decision diagram,OBDD)来表示防火墙的访问控制规则集,改变了传统的顺序存储规则的规则库设计方法,以增加预处理时间为代价,有效地提高了规则的匹配速度,从而提高了防火墙的... 在防火墙规则库的设计中利用有序二叉决策图(ordered binary decision diagram,OBDD)来表示防火墙的访问控制规则集,改变了传统的顺序存储规则的规则库设计方法,以增加预处理时间为代价,有效地提高了规则的匹配速度,从而提高了防火墙的性能及其安全性. 展开更多

关键词 布尔函数 有序二叉决策图 防火墙规则库 规则匹配

下载PDF 职称材料

装配序列规划问题的CSP模型及其符号OBDD求解技术 被引量：8

2

作者 徐周波 古天龙 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2010年第5期803-810,共8页

完全、正确的可行装配序列的表示和生成是装配序列评价、优化和选择的前提,为此建立了单调非线性装配意义下的可行装配序列规划问题的约束满足问题(CSP)模型,并给出了基于有序二叉决策图(OBDD)的符号求解算法.首先以装配联接图和移动向... 完全、正确的可行装配序列的表示和生成是装配序列评价、优化和选择的前提,为此建立了单调非线性装配意义下的可行装配序列规划问题的约束满足问题(CSP)模型,并给出了基于有序二叉决策图(OBDD)的符号求解算法.首先以装配联接图和移动向量函数为装配体模型,给出了装配联接图模型的共享二叉决策图(SBDD)表示、移动向量函数的OBDD表示,以及装配序列规划问题的CSP描述;然后将生成所有可行装配序列的问题转化为对CSP求解所有可能解的问题,利用回溯算法对CSP问题进行符号OBDD求解,得到了满足几何可行性约束的所有可行装配序列.最后通过装配体实验验证了基于CSP模型和OBDD推理的装配序列生成技术的正确性和可行性. 展开更多

关键词 装配序列生成 装配联接图 约束满足问题 有序二叉决策图

下载PDF 职称材料

基于OBDD的航空电子网络可靠性分析 被引量：7

3

作者 陈瑶 李峭 +1 位作者 赵长啸 熊颖 《系统工程与电子技术》 EI CSCD 北大核心 2013年第1期230-236,共7页

针对航空电子网络通信任务的实时性需求,建立具有时延约束的面向任务的网络可靠性模型,并从共因失效(common cause failure,CCF)的角度分析了部件故障相关性,提出一种基于有序二叉决策图(ordered bi-nary decision diagram,OBDD)的航空... 针对航空电子网络通信任务的实时性需求,建立具有时延约束的面向任务的网络可靠性模型,并从共因失效(common cause failure,CCF)的角度分析了部件故障相关性,提出一种基于有序二叉决策图(ordered bi-nary decision diagram,OBDD)的航空电子网络可靠性评价方法——时延约束边扩张算法。算法结合时延约束,利用边扩张构建网络OBDD,递归遍历OBDD结构计算部件故障统计独立条件下航空电子网络可靠度,并在此基础上引入CCF分析,利用同一OBDD结构综合评价航空电子网络可靠性。通过实例阐述了算法的原理,实验表明算法能有效评价航空电子网络的可靠性。 展开更多

关键词 航空电子网络 可靠性 有序二叉决策图 实时性 共因失效

下载PDF 职称材料

基于符号有序二叉决策图的装配序列生成技术 被引量：6

4

作者 古天龙 刘华东 《计算机集成制造系统》 EI CSCD 北大核心 2008年第2期321-328,共8页

为提高装配序列规划求解效率和自动化水平,给出了装配体联结图模型、干涉向量和接触向量模型的有序二叉决策图描述,建立了基于符号有序二叉决策图模型及操作的可行装配序列生成技术。结合实例验证了基于有序二叉决策图的装配体模型和可... 为提高装配序列规划求解效率和自动化水平,给出了装配体联结图模型、干涉向量和接触向量模型的有序二叉决策图描述,建立了基于符号有序二叉决策图模型及操作的可行装配序列生成技术。结合实例验证了基于有序二叉决策图的装配体模型和可行装配序列生成技术的正确性和可行性。 展开更多

关键词 装配序列规划 装配体联结图 装配序列生成 有序二叉决策图

下载PDF 职称材料

基于有序二叉决策图的装配序列符号表示方法 被引量：4

5

作者 古天龙 杨志飞 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2007年第10期1315-1320,共6页

通过建立装配状态的二进制编码和装配操作的布尔特征函数,给出了装配序列描述的有序二叉决策图(OBDD)方法;建立了从装配序列的与或图模型到OBDD模型的转换规则;并对装配序列表示的与或图模型和OB-DD模型进行了存储效率比较.实验结果表明... 通过建立装配状态的二进制编码和装配操作的布尔特征函数,给出了装配序列描述的有序二叉决策图(OBDD)方法;建立了从装配序列的与或图模型到OBDD模型的转换规则;并对装配序列表示的与或图模型和OB-DD模型进行了存储效率比较.实验结果表明:OBDD方法具有较好的存储性能,可以改善复杂装配体的装配序列表示的存储效率,适合于复杂装配体的可行装配序列的描述. 展开更多

关键词 装配规划 装配序列表示 与或图 有序二叉决策图

下载PDF 职称材料

装配序列生成的有序二叉决策图技术研究 被引量：4

6

作者 钟艳如 黄美发 古天龙 《计算机集成制造系统》 EI CSCD 北大核心 2008年第10期1996-2004,共9页

为提高装配序列规划求解效率,在图论割集法的基础上,引入有序二叉决策图描述装配关联图、装配操作、装配几何可行性和装配稳定性。利用装配优先约束关系,简化装配关联图,设计了基于符号有序二叉决策图技术的装配序列生成算法,分析了该... 为提高装配序列规划求解效率,在图论割集法的基础上,引入有序二叉决策图描述装配关联图、装配操作、装配几何可行性和装配稳定性。利用装配优先约束关系,简化装配关联图,设计了基于符号有序二叉决策图技术的装配序列生成算法,分析了该算法的时间复杂度。在每一次割集分解之后,检验子装配体的几何可行性和稳定性,实现装配序列生成过程中状态空间的隐式表示和搜索。研究实例验证了基于符号有序二叉决策图技术的装配序列生成算法的可行性和有效性。 展开更多

关键词 装配序列生成 有序二叉决策图 布尔函数 几何可行性 稳定性 割集

下载PDF 职称材料

可追踪且可撤销的基于OBDD访问结构的CP-ABE方案 被引量：3

7

作者 汪倩倩 欧毓毅 《计算机应用研究》 CSCD 北大核心 2021年第4期1185-1189,共5页

针对现有属性撤销方案中存在对恶意用户的不可追踪性、用户属性不能即时撤销的问题,提出了一种可追踪且可撤销的,基于有序二叉决策图(OBDD)访问结构的,高效、有表达力、可撤销的密文策略属性基加密(CP-ABE)方案。该方案实现了用户属性... 针对现有属性撤销方案中存在对恶意用户的不可追踪性、用户属性不能即时撤销的问题,提出了一种可追踪且可撤销的,基于有序二叉决策图(OBDD)访问结构的,高效、有表达力、可撤销的密文策略属性基加密(CP-ABE)方案。该方案实现了用户属性的即时撤销,也能对恶意用户进行追踪。同时,所提方案采用基于OBDD的访问结构,该类型的访问结构不仅能表示任何关于属性的布尔表达式,还能同时支持访问策略中属性的正负值。该方案将部分加/解密运算外包给代理服务器,从而降低用户的加/解密计算量。该方案基于DBDH假设,在标准模型下被证明是安全的。 展开更多

关键词 属性撤销 属性基加密 可追踪 有序二叉决策图

下载PDF 职称材料

一类新型抽象数据类型:有序二叉决策图 被引量：3

8

作者 古天龙 《桂林电子科技大学学报》 2010年第5期374-388,共15页

有序二叉决策图OBDD(Ordered Binary Decision Diagram)是布尔函数的一种规范表达形式、一种的新的数据结构。基于OBDD能够完成布尔函数的有效表述和操作运算,可以看作为一类新的抽象数据类型。OBDD在VLSI逻辑综合和验证的成功应用结果... 有序二叉决策图OBDD(Ordered Binary Decision Diagram)是布尔函数的一种规范表达形式、一种的新的数据结构。基于OBDD能够完成布尔函数的有效表述和操作运算,可以看作为一类新的抽象数据类型。OBDD在VLSI逻辑综合和验证的成功应用结果引起了学术界和工业应用界的极大关注。迄今为止,OBDD技术及其工业应用已有了长足的发展、产生了不少的研究结果。本文对OBDD相关技术问题、OBDD扩展形式、OBDD应用等方面的研究现状进行了综述和讨论。 展开更多

关键词 有序二叉决策图 抽象数据类型 数据结构 符号技术 布尔函数

下载PDF 职称材料

柔性制造系统中生产调度问题求解的一种符号算法 被引量：2

9

作者 古天龙 熊太平 赵岭忠 《计算机集成制造系统》 EI CSCD 北大核心 2007年第2期338-344,共7页

讨论了基于有序二叉决策图的有界Petri网符号分析,给出了其中镜像计算的一种新算法,进而建立了柔性制造系统生产调度问题的符号有序二叉决策图求解算法。该算法在求解过程中通过对状态空间及其搜索过程中相关数据的有序二叉决策图表示,... 讨论了基于有序二叉决策图的有界Petri网符号分析,给出了其中镜像计算的一种新算法,进而建立了柔性制造系统生产调度问题的符号有序二叉决策图求解算法。该算法在求解过程中通过对状态空间及其搜索过程中相关数据的有序二叉决策图表示,避免了状态和搜索的显示枚举,实现了隐式高效操作,进而改善了算法的计算性能。仿真实验表明了算法的有效性。 展开更多

关键词 赋时PETRI网 柔性制造系统调度 有序二叉决策图 符号算法

下载PDF 职称材料

基于二叉决策图的状态组合爆炸问题并行求解方法 被引量：2

10

作者 叶雄 杨皓栋 《电子技术与软件工程》 2018年第17期184-185,186,共3页

布尔函数的可满足性和等价性等问题的NP完备性所导致的状态组合爆炸问题严重地限制了大规模、甚至工业小规模问题的解决。然而在实际问题的处理中,对布尔函数采取恰当的描述并建立相应描述下的操作算法,可以有效地减缓甚至避免问题处理... 布尔函数的可满足性和等价性等问题的NP完备性所导致的状态组合爆炸问题严重地限制了大规模、甚至工业小规模问题的解决。然而在实际问题的处理中,对布尔函数采取恰当的描述并建立相应描述下的操作算法,可以有效地减缓甚至避免问题处理过程中的状态组合复杂性。而本文就是利用了OBDD来建立布尔函数模型并求解实际问题,结果在效率上较传统方法有很大提升。 展开更多

关键词 组合优化 布尔函数 有序二叉决策图

下载PDF 职称材料

基于OBDD的无线传感器网络可用度算法 被引量：2

11

作者 张晓花 董荣胜 《桂林电子科技大学学报》 2016年第3期210-214,共5页

为降低传感器节点的能量消耗,提高无线传感器网络可用度,构建了可用度评估的离散概率模型,提出了一种符号A_OBDD算法。该算法利用马尔科夫链描述节点状态转移过程,实现了对节点可用度的动态评估,引入有序二叉决策图,有效缓解了"组... 为降低传感器节点的能量消耗,提高无线传感器网络可用度,构建了可用度评估的离散概率模型,提出了一种符号A_OBDD算法。该算法利用马尔科夫链描述节点状态转移过程,实现了对节点可用度的动态评估,引入有序二叉决策图,有效缓解了"组合爆炸"。实验结果表明,WSN节点状态转移概率对可用度有较大影响,验证了A_OBDD算法可以有效评估WSN可用度。 展开更多

关键词 无线传感器网络 可用度 能量约束 马尔科夫链 有序二叉决策图

下载PDF 职称材料

一种基于OBDD的WSN可靠性评估方法 被引量：2

12

作者 闫宗帅 董荣胜 《桂林电子科技大学学报》 2014年第5期411-416,共6页

为评估组播下WSN可靠性,基于有序二叉决策图(OBDD)提出符号OBDD_Multicast算法。该算法在WSN符号OBDD表示的基础上,对WSN的节点变量进行排序,通过节点扩展,利用OBDD的"与"和"或"操作构建组播下WSN可靠性函数的OBDD... 为评估组播下WSN可靠性,基于有序二叉决策图(OBDD)提出符号OBDD_Multicast算法。该算法在WSN符号OBDD表示的基础上,对WSN的节点变量进行排序,通过节点扩展,利用OBDD的"与"和"或"操作构建组播下WSN可靠性函数的OBDD。OBDD_Multicast算法通过识别相邻节点冗余路径和s-t非连通冗余路径,避免冗余扩展,减少扩展过程中中间子网的数目,有效降低了可靠性分析的复杂性。实验结果表明,针对3×N型网络,OBDD_Multicast算法比Shrestha的OBDD算法耗时少、效率高。 展开更多

关键词 可靠性 无线传感器网络 有序二叉决策图 组播 节点扩展

下载PDF 职称材料

基于OBDD的拆卸几何可行性判别方法研究 被引量：2

13

作者 梁勇强 钟艳如 《计算机工程与设计》 CSCD 北大核心 2007年第14期3302-3305,3309,共5页

在基于割集的拆卸序列生成算法中,对拆卸操作的几何可行性进行判别是频繁的操作。引进有序二叉决策图OBDD合理表示拆卸约束,设计了基于OBDD的几何可行性判别算法,比较了基于OBDD的判别算法与基于移动函数的判别算法的时间复杂度,结果表... 在基于割集的拆卸序列生成算法中,对拆卸操作的几何可行性进行判别是频繁的操作。引进有序二叉决策图OBDD合理表示拆卸约束,设计了基于OBDD的几何可行性判别算法,比较了基于OBDD的判别算法与基于移动函数的判别算法的时间复杂度,结果表明基于OBDD的几何可行性判别算法比基于移动函数的判别算法具有更高的判别效率。 展开更多

关键词 拆卸 几何可行性 割集 有序二叉决策图 时间复杂度

下载PDF 职称材料

基于SAT和BDD的频繁序列挖掘技术 被引量：1

14

作者 戴瑀君 徐周波 《广西科学院学报》 2018年第2期137-142,150,共7页

【目的】研究模式挖掘领域中的频繁序列挖掘技术,由于序列模式挖掘存在指数级的搜索空间,且传统的SAT求解算法无法高效求解大规模数据集的缺点,因此研究符号表示和操作技术,用来避免冗余计算。【方法】提出基于SAT的频繁序列挖掘的符号O... 【目的】研究模式挖掘领域中的频繁序列挖掘技术,由于序列模式挖掘存在指数级的搜索空间,且传统的SAT求解算法无法高效求解大规模数据集的缺点,因此研究符号表示和操作技术,用来避免冗余计算。【方法】提出基于SAT的频繁序列挖掘的符号OBDD算法,基于深度优先算法的思想,首先将频繁序列挖掘问题构建为SAT模型,其次对变量进行排序并将约束子句分类后分别描述为OBDD,利用OBDD的"与"操作得到满足SAT的所有频繁序列模式。【结果】实例结果表明,该方法准确可行。【结论】该方法能有效缩减搜索空间,提高求解效率。 展开更多

关键词 布尔可满足性 有序二叉决策图 频繁序列挖掘

下载PDF 职称材料

产生式知识的有序二叉决策图表示及其推理 被引量：1

15

作者 侯杰 王喜成 《计算机应用与软件》 CSCD 2010年第9期240-242,共3页

为了更完整地表示产生式规则构成的知识库及更有效地进行知识推理,给出了基于有序二叉决策图OBDD(Ordered Bi-nary Decision Diagram)的产生式知识表示模型。在此基础上实现了基于OBDD的知识推理规则及相关算法,并结合实例对OBDD模型及... 为了更完整地表示产生式规则构成的知识库及更有效地进行知识推理,给出了基于有序二叉决策图OBDD(Ordered Bi-nary Decision Diagram)的产生式知识表示模型。在此基础上实现了基于OBDD的知识推理规则及相关算法,并结合实例对OBDD模型及其推理规则的可行性进行了分析。 展开更多

关键词 有序二叉决策图 产生式规则 推理

下载PDF 职称材料

基于符号OBDD的子图同构约束求解算法 被引量：1

16

作者 刘桂珍 徐周波 《桂林电子科技大学学报》 2019年第5期357-362,共6页

针对求解子图同构问题计算复杂性较高的问题,提出了一种基于符号OBDD的子图同构约束求解算法(OBDD-SI)。该算法对子图同构进行CSP建模,采用OBDD对该模型进行隐式表示和刻画。结合OBDD符号操作技术和回溯算法进行求解,执行弧一致性技术... 针对求解子图同构问题计算复杂性较高的问题,提出了一种基于符号OBDD的子图同构约束求解算法(OBDD-SI)。该算法对子图同构进行CSP建模,采用OBDD对该模型进行隐式表示和刻画。结合OBDD符号操作技术和回溯算法进行求解,执行弧一致性技术对不满足约束的值进行过滤,从而得到子图同构的所有解。实验结果表明,本算法具有良好的求解性能。 展开更多

关键词 子图同构 约束满足问题 有序二叉决策图 弧一致性

下载PDF 职称材料

基于雾计算的权重OBDD访问结构属性密码体制研究 被引量：1

17

作者 赖霖汉 缪祥华 《电视技术》 2021年第8期95-101,共7页

基于密文策略的属性密码体制在云存储中对于实现数据的安全分享和细粒度访问控制起到了关键性的作用,但基于密文策略的属性密码体制存在效率低、访问策略不灵活以及单一属性授权中心带来的单点失效威胁问题。对此,提出基于雾计算的权重... 基于密文策略的属性密码体制在云存储中对于实现数据的安全分享和细粒度访问控制起到了关键性的作用,但基于密文策略的属性密码体制存在效率低、访问策略不灵活以及单一属性授权中心带来的单点失效威胁问题。对此,提出基于雾计算的权重有序二叉决策图(Ordered Binary Decision Diagram,OBDD)访问结构的属性密码体制。首先,所提方案把大部分运算外包给雾节点,有效地降低了用户端的计算开销;其次,采用多属性授权中心的方式以防止单点失效威胁;最后,所提方案采用基于权重的OBDD访问结构,不仅能由权重设置阈值以表达任何的布尔函数值,还能同时支持访问结构中属性的正负值的表达。安全性分析和性能分析结果表明,所提方案在判定性双线性Diffie-Hellman(DBDH)问题下满足选择明文安全,并且比其他方案更高效,具有使用价值。 展开更多

关键词 基于属性的密码体制 外包计算 权重 有序二叉决策图

下载PDF 职称材料

基于OBDD的描述逻辑εL循环术语集推理 被引量：1

18

作者 古天龙 吕思菁 +1 位作者 常亮 徐周波 《软件学报》 EI CSCD 北大核心 2014年第1期64-77,共14页

循环术语集推理是描述逻辑研究中面临的难点问题,尚未得到很好的解决.有序二叉决策图(ordered binary decision diagram,简称OBDD)是一种对布尔函数进行紧凑表示和高效操作的数据结构,适用于表示和处理大规模问题.将OBDD应用于描述逻辑... 循环术语集推理是描述逻辑研究中面临的难点问题,尚未得到很好的解决.有序二叉决策图(ordered binary decision diagram,简称OBDD)是一种对布尔函数进行紧凑表示和高效操作的数据结构,适用于表示和处理大规模问题.将OBDD应用于描述逻辑循环术语集的推理.首先,针对描述逻辑εL中的循环术语集,给出了描述图上关于最大模拟关系的重要性质,并借助集合表示和集合运算对该性质进行了表述和证明.在此基础上,应用布尔函数对描述图进行编码,给出了基于OBDD求解最大模拟关系的方法,进而给出了最大不动点语义下基于OBDD对概念包含关系进行判定的算法;接下来,基于OBDD给出了求解描述图中可以到达循环路径的所有结点的方法,进而给出了最小不动点语义下基于OBDD对概念包含关系进行判定的算法;最后,对算法的正确性、复杂度等进行了分析和证明,并对算法进行了编程实现,给出了关于计算性能的实验结果.该工作为循环术语集的推理提供了一条有效途径,也为OBDD在逻辑推理中的应用提供了新的案例. 展开更多

关键词 描述逻辑εL 循环术语集 有序二叉决策图 概念包含关系 不动点语义

下载PDF 职称材料

基于OBDD的SMC反例生成研究 被引量：1

19

作者 姚全珠 苗永军 《计算机工程与应用》 CSCD 2012年第10期54-58,145,共6页

针对传统的符号模型检测反例生成算法在生成反例时会产生大量的无关变量,使得反例难以理解。提出一种改进的反例生成算法,将反例中的状态扩展为一个状态集,使用零压缩二叉决策图(Zero-Suppressed Binary Decision Diagrams,ZBDD)来存储... 针对传统的符号模型检测反例生成算法在生成反例时会产生大量的无关变量,使得反例难以理解。提出一种改进的反例生成算法,将反例中的状态扩展为一个状态集,使用零压缩二叉决策图(Zero-Suppressed Binary Decision Diagrams,ZBDD)来存储所求出的状态集。删除了系统中的无关变量,仅保留了相关的变量,实验表明该算法能有效地减少状态的变量数,减少存储反例所需的空间。 展开更多

关键词 有序二叉决策图 模型检测 计算树逻辑(CTL) 反例生成

下载PDF 职称材料

基于OBDD的含圈与或图搜索算法研究

20

作者 赵岭忠 王雪松 《计算机应用研究》 CSCD 北大核心 2011年第4期1325-1329,共5页

在含圈与或图理论框架基础上,给出了基于OBDD的含圈与或图符号表示方法,并提出了一种求解含圈与或图最小代价解图的符号搜索算法。实验结果表明,该算法在处理大规模含圈与或图时具有明显优势。

关键词 含圈与或图 最大可扩展子图 最小代价解图 有序二叉决策图

下载PDF 职称材料