贝耶斯网络模型(精选6篇)
贝耶斯网络模型 篇1
贝叶斯方法是从传统的概率理论中分离出来,是以概率理论为基础的,专门用于处理统计学中的不确定性问题,继而成为探索、处理不确定性知识领域有力的工具。贝叶斯网络则是贝叶斯理论中一颗璀璨的明珠。
1 贝叶斯网络模型的描述
贝叶斯网络(BN),又称为信度网,由一个有向无环图(Directed Acylic Graph,DAG)和条件概率表(Conditional Probability Table,CPT)组成[1]。
贝叶斯网络分类模型(BNC)的形式化的描述如下:
n元随机变量X={X1,X2,…Xn}的贝叶斯网络模型是一个二元组B=(Bs,Bp)。Bs=(X,E)是一有向无环图(directed acrylic graph,DAG),其中X={X1,X2,…Xn}为结点集,每个结点可看成取离散或连续值的变量(本文限定其只取离散值);E是有向边的集合,每条边表示两结点间依赖关系,依赖程度由条件概率参数决定。称Bs为BN模型网络结构。Bp={P(Xi/∏Xi),Xi∈X}是贝叶斯网络模型的一组条件概率分布的集合。在各结点取离散值的情况下,BP为一组条件概率表(conditional probability tables,CPTs)的集合。∏Xi是在Bs中Xi所有父结点的集合,表示结点Xi在其父结点某一取值组合状态下的条件概率分布。这说明,在贝叶斯网络模型中,结点的取值依赖于其父结点的取值状态。
这里,学习贝叶斯网络的问题描述为:给定Xi中的一组实例构成的训练集合D=X={X1,X2,…Xn},找到一个与D匹配最好的网络B。这样,学习贝叶斯网络的问题转化为优化问题。这时类变量和属性变量不加区别。
实际处理这个问题的方法是在可能的网络构成的空间中进行启发式搜索。搜索成功的关键是确定一个合理的评分函数,评价网络对训练数据的匹配程度,以指导搜索。
有两种主要的评分函数[2]:贝叶斯评分函数和最小描述长度原理(MDL:minimal description length)评分函数。它们是渐进正确的,即随着样本数目的增加,得分最高的网络将任意逼近样本的概率分布。
2 构造贝叶斯网络的方式
一般情况下,构造贝叶斯网有三种不同的方式:
(1)由领域专家确定贝叶斯网的变量(有时也称为影响因子)节点,然后通过专家的知识来确定贝叶斯网络的结构,并指定它的分布参数。这种方式构造的贝叶斯网完全在专家的指导下进行,由于人类获得知识的有限性,导致构建的网络与实践中积累下的数据具有很大的偏差。
(2)由领域专家确定贝叶斯网络的节点,通过大量的训练数据,来学习贝叶斯网的结构和参数。这种方式完全是一种数据驱动的方法,具有很强的适应性,而且随着人工智能、数据挖掘和机器学习的不断发展,使得这种方法成为可能。如何从数据中学习贝叶斯网的结构和参数,已经成为贝叶斯网络研究的热点。
(3)由领域专家确定贝叶斯网络的节点,通过专家的知识来指定网络的结构,而通过机器学习的方法从数据中学习网络的参数。这种方式实际上是前两种方式的折衷,当领域中变量之间的关系较明显的情况下,这种方法能大大提高学习的效率。
可以看出,在由领域专家确定贝叶斯网络的节点后,构造贝叶斯网的主要任务就是学习它的结构和参数。很显然,学习结构和参数不是完全独立的。一方面节点的条件概率很大程度上依赖于网络的拓朴结构;另一方面,网络的拓朴结构直接由联合概率分布的函数来决定。
然而,一般情况下,我们还是把这两个方面分开来进行。这是因为,带有太多连接的复杂网络结构所需观测的参数较多,而为使获得这些参数达到某种信任程度所需的数据量随着参数数目的增加而迅速增长,并且复杂的结构需要太大的存储空间及冗长繁琐的计算过程才能产生预测和解释。因此,为使贝叶斯网作为知识模型是可用的,在学习过程中致力于寻找一种最简单的网络结构是非常必要的,这种简单的结构模型称之为稀疏网络,它含有最少可能的参数及最少可能的依赖关系。
根据构成贝叶斯网络的结点变量是离散的变量且取有限个值或是连续的变量或是既有连续变量又有离散变量三种不同情况,贝叶斯网络的类型可以分为离散型、连续型、混合型三种[3]。
近年来,关于贝叶斯网络的理论研究重点集中于贝叶斯网络的结构学习和参数学习方面。结构学习是指对于每一特征节点找到除根节点之外的所有父节点,参数学习是指在己知结构的基础上获得上述参数的估计。
当我们在贝叶斯网络中把其中代表类别变量的节点作为根节点,其余所有变量都作为它的子节点时,贝叶斯网络就变成了分类器[4]。
3 贝叶斯网络模型的优点
通过提供图形化的方法来表示和运算概率知识,贝叶斯网络克服了基于规则的系统所具有的许多概念上和计算上的困难。贝叶斯网络与统计技术相结合,使得其在数据分析方面拥有了许多优点,与规划挖掘、决策树、人工神经网络、密度估计、分类、回归和聚类等方法相比,贝叶斯网络的优点主要体现在:
(1)贝叶斯网络使用图形的方法描述数据间的相互关系,语义清晰,易于理解。图形化的知识表示方法使得保持概率知识库的一致性和完整性变得容易,可以方便地针对条件的改变进行网络模块的重新配置。
(2)贝叶斯网络易于处理不完备数据集。对于传统标准的监督学习算法而言必须知道所有可能的数据输入,如果缺少其中的某一输入就会对建立的模型产生偏差,贝叶斯网络的方法反映的是整个数据库中数据间的概率关系模型,缺少某一数据变量仍然可以建立精确的模型。
(3)贝叶斯网络允许学习变量间的因果关系。在以往的数据分析中,一个问题的因果关系在干扰较多时,系统就无法做出精确的预测。而这种因果关系己经包含在贝叶斯网络模型中。贝叶斯方法具有因果和概率性语义,可以用来学习数据中的因果关系,并根据因果关系进行学习。
(4)贝叶斯网络与贝叶斯统计相结合能够充分利用领域知识和样本数据的信息。贝叶斯网络用弧表示变量间的依赖关系,用概率分布表来表示依赖关系的强弱,将先验信息与样本知识有机结合起来,促进了先验知识和数据的集成,这在样本数据稀疏或数据较难获得的时候特别有效。
4 小结
贝叶斯推断理论提供一种概率手段,为数据建模提供了一个统一的框架,而且它为算法的分析提供了理论基础。尽管关于贝叶斯网的理论研究还很不完善,应用研究还处于起步阶段,但在许多领域中已显现出令人瞩目的效果,可以预见随着技术的进步,贝叶斯网模型将发挥越来越重要的作用。
参考文献
[1]张少中,王秀坤,孙莹光.贝叶斯网络及其在决策支持系统中的应用[J].计算机工程,2004.30(10):1-3.
[2]胡玉胜,涂序彦,崔晓瑜,程乾生.基于贝叶斯网络的不确定性知识的推理方法[J].计算机集成制造系统.2001.7(12):65-68.
[3]林士敏,田凤占,陆玉昌.贝叶斯网络的建造及其在数据采掘中的应用[J].清华大学学报(自然科学版).2001.41(1):49-52.
[4]周颜军,王双成,王辉.基于贝叶斯网络的分类器研究[J].东北师大学报自然科学版.2003.35(2):21-27.
基于贝叶斯网络的信息检索模型 篇2
(一) 推理网络模型
推理网络模型采用的是信息检索认识论的观点[4]。该模型中文档节点用dj表示, 术语节点用ki表示, 查询节点用q表示。文档节点、术语节点、查询节点均与用相同符号表示的二进制随机变量相关。U={k 1, k 2, ..., k t}表示t维的向量空间, 变量k1, k 2, ..., kt为U定义了2t种状态, u表示其中一种状态。
根据查询q对文档dj进行排序, 其结果可以用来度量dj的观测值为查询q提供了多少证据支持。在推理网络中, 文献dj的排序可用P (q|d j) 来计算[2], 其计算方法如下:
其中α是一个常数因子, 因为没有对任何文档给出特定的先验概率, 所以一般采用一个统一的先验概率分布, 在有关推理网络的早期著作[1,5]中, 规定观测一篇文档dj的先验概率为, N为系统中的文献总数, 因而:
利用基本条件及贝叶斯定理, 公式 (1) 可变为下式:
具体定义方法参考文献[4]。
(二) 信念网络模型
信念网络模型也是基于概率认识论描述的, 但是这种模型采用的是一个明确定义的样本空间, 因而产生了一种不同于推理网络的网络拓扑, 即将网络中的文档和查询分离开来。
在信念网络中, 术语集合U={k 1, k 2, ..., k t}是一个论域 (discourse) , 同时为信念网络模型定义了样本空间。u⊂U是U的一个子集, 且g i (u) =1⇔ki∈u。每个索引术语被看作是一个基本概念, 因此U被看作是一个概念空间, 概念u是U的子集。文档和用户查询用概念空间U中的概念表示。
定义在样本空间U上的概率分布P如下所示, c是空间U中的一个概念, 表示一篇文档或一个用户查询:
公式 (5) 将p (c) 定义为空间U中c的覆盖度 (degree of coverage) , 公式 (5) 表示概念空间中的所有概念均是等概率发生的。
与给定查询q相关的文档dj的排序被理解为一种概念匹配关系, 它反映了概念q提供给概念dj的覆盖度。因此在信念网络中用p (dj|q) 计算文档dj关于查询q的排序。根据条件概率、公式 (5) 及贝叶斯定理可得:
其中η为规范化因子, 对概率P (d j|u) , P (q|u) 的不同定义可使信念网络检索模型包括由各种经典信息检索模型 (布尔模型、矢量模型、概率模型) 产生的排序策略。具体定义方法参考文献[2]。本文提出的扩展模型就是以基本信念网络模型为框架的。
(三) 简单贝叶斯网络检索模型
简单贝叶斯网络检索模型中的变量由两个不同的集合组成, V=T∪D:集合T={T1, T2, ..., TM}, 集合D={D1, ..., DN}, T和D中的变量均是二值的。变量Dj取值集合为, 其中和dj分别表示在给定查询下文档Dj不相关和相关。变量Ti取值集合为, 其中分别表示术语不相关和相关。
网络拓扑结构的建立基于以下三个假设:
1. 如果术语Ti属于文档Dj, 则术语节点Ti和文档节点Dj之间有弧。这反映了文档和其索引术语之间的依赖关系;
2. 文档节点之间没有弧, 也就是说文档节点之间的关系只是通过索引它们的术语表示出来;
3. 已知文档Dj中索引术语是否相关的情况下, 文档Dj和其它任何文档Dk是条件独立的, 也就是说文档Dj是否相关只受索引它的术语的影响, 而不受其它文档的影响。在网络中表现为弧的指向是由术语节点指向文档节点。
由这三个假设最终确定网络的拓扑结构。网络包括两个子网:术语子网和文档子网, 弧是由第一个子网中的节点指向第二个子网中的节点。该模型与推理网络模型和信念网络模型最大的区别是在网络中没有包含查询节点, 也就是说该模型是查询独立的, 查询只是作为证据在网络中传播。
BNR模型各类节点中存储的条件概率计算如下:
(2) 对于文档节点需要估计条件概率分布p (dj|π (Dj) ) , 其中π (Dj) 是Dj的父节点集Π (D j) 取值后的任意一种组合。因为文档节点可能有大量的父节点, 所以需要估计和存储的条件概率的数目是很巨大的。因此, 简单贝叶斯网络检索模型采用了专门的正则模型来表示条件概率:
其中R (π (Dj) ) 是π (Dj) 中相关术语的集合, 权重wij满足wij≥0且。这样在π (Dj) 中的相关术语越多, Dj的相关概率越大。
简单贝叶斯网络中节点的数目通常比较大, 节点之间的连接也是多路经的, 每个节点也可能包含大量的父节点, 所以考虑到检索的效率问题, 一般的推理算法是不能使用的。因此, 简单贝叶斯网络检索模型设计了特殊的推理过程可以非常有效地计算需要的概率, 并且证明了得到的结果和在整个网络中实施精确推理得到的结果是一样的:
根据术语子网的拓扑结构, 则当Ti∈Q时p (ti|Q) =1, 当Ti∉Q时p (ti|Q) =1/M, 这时公式 (8) 可改写为:
权重wij有多种计算方法, 可参考有关文献。
参考文献
[1]Howard Robert Turtle, W.Bruce Croft.Inference networks for document retrieval.Proceedings of the13th ACM-SIGIR Conference, 1990:1-24.
[2]Berthier Ribeiro-Neto, Richard Muntz.A belief network model for IR.Proceedings of the19th ACM-SIGIR Conference, 1996:253-260.
[3]Ricardo Baeza-Yates, Berthier Ribeiro-Neto.现代信息检索.北京:机械工业出版, 2005:24-42.
[4]Howard Robert Turtle, W.Bruce Croft.Evaluation of an inference network-based retrieval model.ACM Transactions on information systems, 1991, 9 (3) :187-222.
贝耶斯网络模型 篇3
独立审计准则要求审计师在财务报表审计时使用现代风险导向审计方法, 深入了解被审计单位及其环境, 识别和评估财务报表层次和认定层次可能存在的重大错报风险, 并以此为审计起点, 采取有针对性的风险应对措施, 设计和执行控制测试和实质性测试程序, 将整体审计风险降至可接受的水平。能否正确识别并合理量化被审计单位财务报表的重大错报风险, 成为评价注册会计师专业胜任能力的决定性因素, 但是审计准则中并没有明确审计风险的定量评估方法。为了将审计过程中审计师的因果推理判断经验表达出来, 本文尝试应用贝叶斯网络建立审计风险管理模型, 对风险导向审计过程进行解释。
二、贝叶斯网络理论及审计风险管理模型构建步骤
(一) 贝叶斯网络理论
贝叶斯网络 (Bayesian Networks) 1988年由Pearl提出, 它使用网络图来表示不确定性知识, 将知识经验图解可视化对风险管理建模, 其能根据已知的网络拓扑模型对不确定性事件进行概率推理, 因此也被称为因果推理网络。目前广泛用于人工智能、工程管理、医疗诊断等领域。贝叶斯网络由两部分构成: (1) 具有N个结点的有向无环图 (Directed Acyclic Graph) , 图中圆圈结点是对现实事件特征状态的描述, 弧表示事件结点之间的因果依赖关系。 (2) 条件概率表 (Conditional Probabilities Table) 集合, 条件概率表用来表示该节点同其父节点的相关程度。如图1所示, X1、X2、X3、X4表示相互之间存在着一定因果关系的不同风险事件, P (X3|X1) 表示事件X3在事件X1发生时的概率, 所有节点对应发生的概率组成条件概率表集合。贝叶斯网络包括两个独立假设:一是任一节点在给定它的父节点时条件独立于它的非后代节点集;二是给定一个节点的马尔可夫覆盖, 这个节点和网络中的所有其他节点是条件独立的。贝叶斯网络把复杂的联合概率分布分解成一系列相对简单的模块, 能有效减少概率推理的复杂程度, 降低事件之间条件概率获取的难度, 使得概率推理在复杂问题中得以广泛应用。
(二) 贝叶斯网络审计风险管理模型构建步骤
贝叶斯网络可以利用历史数据信息和专家经验知识来构造模型。利用历史数据信息建立贝叶斯网络又分为参数学习和结构学习两种方式: (1) 参数学习是假设已知变量之间的关系而估计变量发生的概率, 常常使用贝叶斯统计和最大似然估计两种方法。基于贝叶斯统计的方法是利用先验知识将参数做为随机变量来估计发生概率, 而最大似然估计没有考虑先验知识因素, 而是将参数视为未知固定变量来估计。 (2) 结构学习是指通过过去的各个结点发生概率信息的历史数据, 学习生成网络结构, 如果过去的经验数据充足, 构建的网络结构图就很稳定。这种方式能发现事物间的因果关系, 获得结构模型, 因而也称为因果挖掘。对于风险管理系统来说, 如果不存在充分的历史训练数据, 也可利用专家经验确定出贝叶斯网络的结构及每个节点的条件概率。本文借鉴Van Troun Luu在风险管理中贝叶斯网络的方法步骤以及周国华在京沪铁路建设项目中应用贝叶斯网络进行质量风险管理的方法, 提出四步应用贝叶斯网络的审计风险管理步骤: (1) 对导致审计风险产生的因素进行分类确认, 通过审计准则、审计报告、审计专家意见等方式评价出重要风险因素。 (2) 审计专家分析风险因素的因果关系, 构造贝叶斯网络。 (3) 进行审计风险因素度量, 利用参数学习方法来确定贝叶斯网络中的结点参数概率值, 再通过敏感性分析找出审计风险的关键风险因素。 (4) 随着审计项目的进展, 审计风险数据得到更新, 审计师利用贝叶斯网络对其进行再评估。
三、基于贝叶斯网络的审计风险模型构建
(一) 财务报表重大错报风险因素的识别
现代风险导向审计的核心是审计师研究企业是否存在导致经营失败的风险, 在此基础上关注被审计单位可能存在财务报表重大错报的风险。财务报表错报风险识别可以通过分析审计准则、审计报告、审计专家意见等方式来确定重要风险因素。本文首先通过分析审计准则中导致重大错报风险的产生因素, 再根据审计专家意见确定重要风险因素。独立审计准则中1211号规定了注册会计师应当关注被审计单位存在重大错报风险的事项, 表1将其分成三个层次列示。风险因素B1是被审计单位的外部环境, B2、B3、B4以及B6是企业的内部风险因素, B5同时包括内部因素和外部因素。各种风险因素之间存在相互影响的因果关系, 如企业的目标战略、相关经营风险可能受到行业状况、法律环境与监管环境等其他外部因素的影响, 而会计政策选用、内部控制制度设计和执行则受到企业的性质、目标战略等风险因素的影响。根据审计项目的实际情况, 通过审计专家对风险因素进行分析整理, 考虑风险因素发生的可能性和风险的严重程度, 合并筛选表1中的风险因素, 得到主要风险因素, 并根据专家经验, 确定主要风险因素之间的因果关系, 为建立贝叶斯网络结构做准备。
(二) 贝叶斯网络结构的建立
贝叶斯网络的构建过程中有大量复杂计算, 使用专业软件GeNIe2.0建立模型能提高效率。该软件能进行模型的自我推理作用, 减少手工计算量, 提高审计推理判断效率。根据表1中的风险因素, 参考审计专家的意见确定各风险因素之间的因果关系, 最终建立的模型如图2所示。图中指向经营风险的弧表明, 它的概率分布受行业状况和监管法律环境以及企业战略、所有权结构等风险因素的制约。
(三) 贝叶斯网络的参数学习
在完成风险因素识别后, 对审计项目各因素收集整理量化数据。即对每项审计风险产生因素进行风险度量, 将风险发生的可能性分为“高、中、低”三个等级 (分别以R1、R2、R3表示) , 确定审计风险相关因素的风险等级, 表2是具体的一个企业在审计时风险评估数据。为了实现建立的贝叶斯网络结构的参数学习, 需要获得多个企业风险等级数据, 通过企业历史数据采用最大似然法结合网络结构图中节点间关系进行概率估计, 计算各节点的先验条件概率表。GeNIe2.0能够很方便的实现导入历史数据对节点取值进行匹配, 进行参数学习。使用历史数据回归分析来找到结点间的条件概率分布也是一种确定量化数据的方便办法。最后由专家对这些参数进行再一次检查, 并进行局部的数据修整。在建立贝叶斯网络后, 可以通过敏感性分析确定关键风险因素, 敏感性分析是计算某变量对其他变量分布的影响程度, 图3为Ge NIe2.0中进行贝叶斯网络敏感性分析结果, 其中限影节点是审计师应重点关注被审计单位的敏感性因素。
(四) 审计风险管理
模型应用在贝叶斯网络模型建立以后, 审计师把已知条件作为证据输入进行推理, 最后以直观的信息输出, 审计师能根据这些信息快捷灵活的确定审计风险大小。现代风险审计包括风险识别、风险评估、风险应对措施等步骤, 其过程如图4所示。因此贝叶斯网络主要可以应用在以下两方面: (1) 审计计划时预先利用先验概率估计可能的财务报表错报风险进行审计资源分配; (2) 在审计过程中利用后验概率来推断最终的审计风险, 以减少审计成本。在审计过程中的可以对贝叶斯网络进一步细化分解, 建立具体项目审计风险贝叶斯网络, 图5是在销售收款循环中建立的贝叶斯网络, 审计师通过函证、抽查等审计程序, 收集到的审计证据可以推断出销售循环的风险大小。
四、贝叶斯网络审计模型的特点
(一) 灵活的审计师经验学习机制
贝叶斯网络能通过有向图直观地表示审计师所拥有的专业知识经验, 同时也能以事件发生的条件概率的形式把将实际审计项目中的审计风险数据融入模型。因此贝叶斯网络能充分利用审计人员的知识经验和审计项目中的客观数据, 与神经网络等其它风险管理模型相比, 它能更直观的处理定量信息。
(二) 清晰的审计推理过程
贝叶斯网络能方便的表达风险推理过程, 在某节点的父节点或各子节点条件状态已知情况下, 该节点的发生概率能以贝叶斯概率理论估计计算出, 推理过程简单直观, 这样能充分保证审计风险评估可靠程度。再者, 在审计实务中往往能根据各审计程序历史经验和与这些程序相关的审计项目收集的风险数据, 计算出未审计项目在不同情况下的风险概率, 有效节约审计时间, 降低审计成本。
(三) 新增审计证据
贝叶斯网络另一个重要的功能是允许审计师灵活添加在审计过程新发现的定性或定量信息作为证据用到模型中, 根据新的证据推论审计风险大小。加入证据的常见方式是使用审计人员在审计过程中对变量的判断更新这些变量状态概率分配。例如, 如果审计人员对某一个审计项目预期有信心, 其可以更新审计项目分配的指定状态的概率。这样, 重新计算模型导致的相关条件概率, 报表层次审计风险大小可以立即更新得到, 而不用对模型进行修正。
(四) 需要建立风险数据库
贝叶斯网络能不能准确描述审计风险依赖于风险信息数据库的完整程度。目前国内很多事务所对行业风险和企业经营风险缺乏了解, 数据积累不足, 达不到现代风险导向审计的要求。会计师事务所必须建立功能强大的风险数据库, 包含经营环境、行业状况、客户不同的风险领域, 客户的具体风险信息等。由专业人员组织实施评价, 定期把客户风险评价的结果输入风险数据库来支撑贝叶斯网络的更新。
五、结论
本文探讨了在审计过程中利用贝叶斯网络进行风险管理, 通过举例说明了建立贝叶斯网络的四个步骤。基于贝叶斯网络的审计风险管理模型能方便的表达审计师的经验知识, 推理过程清楚直观, 不足之处是需要建立审计项目风险评价数据库来支撑贝叶斯网络的更新。
参考文献
[1]王桂兰:《基于案例推理的审计重大错报风险评估研究》, 《审计与经济研究》2007年第6期。
[2]王会金:《模糊综合评价法在重大错报风险评估中的运用》, 《会计研究》2011年第9期。
贝耶斯网络模型 篇4
温控系统是飞机发动机关键系统之一。主要是由防喘调节器、温度控制放大器和温度限制器、燃油流量调节器等部件组成, 其主要功能是防止超温和喘振等。由于温控系统部件之间相互关联多, 控制关系复杂, 导致了部队对发动机温控系统的故障机理诊断不准确, 从而严重的阻碍了部队战斗力生成。而贝叶斯网络恰好具有处理各种复杂信息的能力, 本文则是根据发动机温控系统功能、结构和故障等信息, 同时融合系统外部运作环境和专家经验, 构建出了温控系统健康评估模型。
1 温控系统健康评估模型
温控系统性能指标和外在影响指标包括7个一级指标, 8个二级指标和它们分别对应的专家评估 (本文采用三位专家的意见) , 根据上述重要指标构建温控系统健康状态评估的贝叶斯网络模型, 如图 (a) 所示。本文所使用的是美国匹兹堡大学研究的GeNIe软件, 通过程序自动生成DSL格式的贝叶斯网络文件。
2 贝叶斯网络中各节点的条件概率
在对温控系统健康状态进行评估时, 我们将目标值设为其发生故障的概率P, 则根据各个指标的关系, 便可以确定在此贝叶斯网络中各个节点的条件概率表。
从上图已知, 对应贝叶斯网络中“noisy-or门”关系的发动机转速、失速警告、T6温度、防喘警告、管理维护、运行、维护这7个1级指标, 即:若这其中某些指标导致故障的概率很低, 但其它指标很高, 则这个温控系统的健康状态水平也不会很高。另外, 由于一些无法预料的因素, 即便是这7个一级指标中没有一个发生故障, 此温控系统还是有可能发生故障, 这种状况便可用贝叶斯网络的“带leak的noisy-or门”来表示, 同时贝叶斯网络中的条件概率表可将其表达出来。在上面给出的模型所有2级指标间的逻辑关系也可用“带leak的noisy-or门”来表达, 同时也可用贝叶斯网络中的条件概率表表达出来。所以图 (a) 贝叶斯网络模型中的每一个非根节点的条件概率表可用此方法得出。而类似于机务能力指标这种根节点的条件概率, 我们关注的是计算后的的值而非是其初始值。这些指标我们可以假设其在温控系统中是等概率事件, 即取它们的初始值为0.5。
3 模型节点条件概率的更新
专家E2根据自己的经验及判断对于机务能力与温控系统故障的关系定出了以下准则:
当用“好”“中”“差”做为评估机务能力的指标时, 温控系统出现故障的概率分别为0.1, 0.2, 0.5,
同理, 根据式 (1) 便可以计算出指标S1落入各准则时温控系统故障时的概率分别为:
4 结束语
健康状态评估不仅关系到系统的正常运行, 而且对部队的快速反应能力、出动强度和持续战斗能力起着决定性的作用。通过对温控系统的工作状态进行评估, 可使我们充分了解系统性能, 便于有针对性地采取维修措施及时解决系统问题, 对维修保障人员及时高效的排除故障, 防止危害性事故发生, 提高维修保障能力具有重要意义。
摘要:本文根据某型发动机温控系统结构功能特点及外界影响因素, 利用贝叶斯网络建模方法, 建立了温控系统健康评估模型。利用温控系统可靠性信息、故障信息及专家经验等信息, 确定了系统诊断模型的条件概率分布, 并融合某团飞机发动机温控系统故障信息以及多位专家经验对评估模型的条件概率进行了更新, 进而利用贝叶斯网络确定了其边缘概率。
关键词:温控系统,专家经验,贝叶斯网络
参考文献
[1]杨多和, 安伟光, 李铁钧.基于人工神经网络的结构可靠性分析[J].兵工学报, 2007, 28 (4) :495-496.
[2]Joanne Bechta Dugan, Savatore J.Bavuso, Mark A.Boyd.Dynamic Fault Tree Models for Fault Tolerant Computer Systems[J].IEEE Transactions on Reliability, 1992, 41 (3) :363-377.
[3]Liudong Xing, Leila Meshkat.Reliability Analysis of Hierarchical Computer-based Systems Subject to Common-cause Failure[J].Reliability Engineering System Safety, 2006, 92 (3) :351-359.
[4]董立岩.贝叶斯网络应用基础研究[D].长春:吉林大学, 2007.
[5]Chin-Yu huang, Yung-Ruei Chang.An improved decomposition scheme for assessing the reliability of embedded systems by using dynamic fault trees[J].Reliability Engineering System Safety, 2007 92 (10) :1403-1412.
[6]David Heckerman, Abe Mamdani, and Michael P.Wellman.Real word applications of Bayesian networks[C].Communications of the ACM, 1995, 38 (3) :24~26.
[7]邵继业, 王日新, 徐敏强.贝叶斯网络在模型诊断中的应用[J].吉林大学学报 (工学版) , 2010, 40 (1) :234~235.
[8]Tariq Assf, Joanne Bechta Dugan.Diagnostic Expert Systems from Dynamic Fault Trees[C].IEEE Annual Reliability and Maintainability Symposium, 2004:444-450.
[9]董立岩.贝叶斯网络应用基础研究[D].吉林大学博士学位论文.2007:16.
贝耶斯网络模型 篇5
无线多跳网络(例如无线传感器网络、无线mesh网络等)[1][2]常常应用于无人监管区域,由于条件的特殊性使得网络中的节点不仅需要传输数据,还应自主管理网络。无线多跳网络中任何无线设备节点都可能同时作为接入点AP (Access Point)或路由器与一个或者多个对等节点进行直接通信,实现拥塞时数据能够自动重新路由到邻近节点进行传输,从而减轻或消除网络拥塞状况。然而,实际的无线多跳网络并不像理论分析中的那样遵循预定的机制进行通信,而是存在许多自私节点。这些自私节点为了保存自己的能量或者延长自己的工作寿命而不积极参与网络的转发甚至是路由的发现和维持,从而导致个别节点成为"热点"以至于过早耗尽能量失效,造成整个网络的寿命下降。
针对无线多跳网络中的节点自私性,基于信誉度加强网络节点的协作性是一个有效的方法。[3][4]本文提出了基于贝叶斯网络模型的激励机制。新的模型以及激励机制通过采用等级服务激励网络节点参与网络的数据转发,实现自私节点的减少;同时,通过对节点信誉度的动态更新,及时的反应目前网络中节点的可信度与安全状态,实现对恶意结点的识别与隔离。
2. 贝叶斯网络
贝叶斯网络 (BN:Bayesian Network) 是一个有向无环图[5],有时也称为因果网,它由代表变量的节点及连接这些节点的有向边构成,图1给出了一个简单的6个节点的贝叶斯网络示例(未包含条件概率分布)。
一个具有N个节点的贝叶斯网络可以用N=<<V, E>P>来表示,其中包括2个部分:
1)<V, E>表示一个具有N个节点的有向无环图G。图中的节点V={V1, …, VN}代表变量,节点见的有向边E代表了变量见的关联关系。节点变量可以是任何问题的抽象。通常认为有向边表达了一种因果关系,因而贝叶斯网络也称为因果网。对于有向边 (Vi, Vj) ,Vi成为Vj的父节点,
而Vj称为Vi的子节点。Vi的父节点集合和非后代节点集合分别用pa (Vi) 和A (Vi) 来表示。有向图<V, E>蕴含了条件土地性假设,即在给定pa (Vi) 下,Vi与A (Vi) 条件独立:P (Vi|pa (Vi) , A (Vi) ) =P (Vi|pa (Vi) ) 。
2) P表示一个与每个节点相关的条件概率分布。由贝叶斯网络的条件独立性假设可知,条件概率分布可以用P (Vi|pa (Vi) 来描述,它表达了节点与其父节点的关联(因果)关系。如果给定根节点先验概率分布和非根节点条件概率分布,可以得到包含所有节点的联合概率分布,在图1中,包含全部节点的联合概率分布函数为:
3. 信誉度评价体系
鉴于无线多跳网中可能存在的自私节点将导致个别节点成为热点以至于过早耗尽能量失效,造成整个网络的寿命下降。如果这些自私节点正好是网络的关键节点,则可能造成整个网络的彻底瘫痪。通过网络让信誉度高的节点具有高优先级,即能够得到高优先级的服务,因此如何评判一个节点的信誉度就成为了关键问题。本文将合理地利用贝叶斯网络用于计算节点间的信誉度。
(1)对于网络中的每个节点Si,都维护一个直接通信成功概率表P (Sj) ,如表1所示;以及一个信誉度表N (Sj) ,如表2所示。其中,P (Sj) 为节点Si与节点Sj成功通信的次数除以通信的总次数。
(2)节点Si关于节点Sj的信誉度的计算分为以下3种情况:
情况1:当邻节点Sj与Si有实际接触时,例如邻节点Sj为Si转发路由请求,路由回复或数据包,Si就将其信誉度表中Nj的值改为目前成功通信的次数除以总的通信的次数,即成功通信的概率。不同节点对信息的转发情况不同,因此同一节点的信誉度在不同的节点中是不同的。
情况2:Sj没有与Si实际接触过,即Sj没有为Si转发过路由请求,路由回复或数据包,此时Si对Sj的信誉度就要从其他与Sj接触过的节点中获得。可以理解为,通过一个中间人,根据中间人对我们想要了解的节点的评价,来大体得出我们想要了解的节点的信誉度。因为每个节点要想从其他节点那里得到服务,是需要看他的信誉度的高低的,所以信誉度的计算十分重要。例如,节点S1想与S2通信,S2此时比较繁忙,S2要根据S1的信誉度的高低决定与不与他通信,但S2并没有关于S1的信誉度,那要如何求S1的信誉度呢,我们这里就采用贝叶斯网络的方法来计算。
如图2,我们要求S1关于S3的信誉度,但是,S1没有与S3实际接触过,这里我们就通过一个中间节点S2,通过中间节点S2对S3的评价,来得出S1关于S3的信誉度。节点S2与S3通信过,所以他有与S3成功通信的概率,表示为P (S2, S3) (本人中的概率P (Si, Sj) 表示节点Si的直接通信成功概率表中的P (Sj) ,可理解为在相信Si的前提下对Sj的信任度),而S1对于P (S2, S3) 值的信任度多高就取决于S1对于S2的信任度;即S1与S2成功通信的概率P (S2) ,那么S1关于S3的信誉度N13可以看成S1与S3通信成功的概率,(以下所有的Nij皆表示节点Si关于节点Sj的信誉度)可由公式(1)求得:
如图3所示,当有多个中间节点存在时,设S1与S2成功通信的概率为P (S2) ,S2与S3的成功通信的概率为P (S2, S3) ,S3与S4的成功通信的概率为P (S3, S4) ,则S1关于S4的信誉度N14为:
如图4所示,当Si与Sj共同接触的中间节点有多个时,可以做如下处理:先求的S1与S2通信成功的概率占3个节点通信成功的总数的比例为P (S2) / (P (S2) +P (S3) +P (S4) ) ,再求得S1与S3通信成功的概率占与3个节点通信成功的总数的比例为P (S3) / (P (S2) +P (S3) +P (S4) ) ,再求得S1与S3通信成功的概率占与3个节点通信成功的总数的比例为P (S4) / (P (S2) +P (S3) +P (S4) ) ,最后根据全概率公式求得S1关于S5的信誉度:
情况3:节点Si与节点Sj既有直接接触,Si又可以从其他节点处获得关于Sj的评价,如图4,此时就要综合两个信息,给出关于Sj的信誉度的值。这样Si就可以更快、更灵敏的得知Sj节点信誉度的变化,避免了某些节点的恶意攻击。
即S1关于S4的信誉度取决于以往通信成功的概率和从其他节点处获得的评价,以往通信成功的概率为通信成功的次数/总的通信次数,用P (S4) 表示,从其他节点处获得的评价为 (P (S2) *P (S2, S4) +P (S3) *P (S3, S4) ) / (P (S2) +P (S3) ) ,则S1关于S4的信誉度为:
上式中a表示直接通信成功的权重,(1-a)表示从其他节点处获得的评价的权重,因此一个节点关于另一个节点的信誉度可有以下公式给出:
其中Sz为有与Sj实际接触过的节点,P (Sz) 为Si的概率表中Sz节点的值,P (Sz, Sj) 为Sz表中关于Sj节点的值。特别的,当a=1时,即为情况1;当a=0时,即为情况2。
以图5为例,取a=0.5, S1与S4直接通信成功的概率为0.94, S1与S2直接通信成功的概率为0.94, S1与S3直接通信成功的概率为0.96, S2与S4直接通信成功的概率为0.5, S3与S4直接通信成功的概率为0.5。那么,在没有添加S2、S3两个节点的参数前,S1对于S4的信誉度为0.94。在添加S2、S3节点的参数后,根据上面的公式求得:
结果表明计算得出的信誉度比原来单纯的依据统计数据得出的概率小,也就是当其他节点发现某一节点的信誉度降低后,它能够通过这一方式向周围的其他节点获得这一节点信誉度的变化,从而更加敏锐的做出反应。而不用等到他与这一节点实际接触后才能得出。
4.仿真实验
本文采用使用Matlab软件[6]编程对本文提出的模型以及激励机制进行仿真验证,网络仿真结构如图6所示。其中S1作为根节点,Ps表示S1节点关于S4节点的信誉度直接通信成功的概率,N表示S1获得评价的间接节点的个数,V (N) 表示在间接节点个数为N时S1关于S4的信誉度。仿真将根据式(5),对S1关于S4节点的信誉度进行计算,参数的初始化如表3所示。
算法流程如图7所示:
仿真结果如图8和图9所示。其中图8中,x轴方向表示间接节点的个数,y轴方向表示S1关于S4的信誉度。从上图结果可以看出,在200个节点以内时,信誉度的值抖动比较大,但是增加到200个节点以上,信誉度的值就逐渐接近于某个固定的值。即在网络中节点数小于200的情况下,根据式(5)计算出的信誉度能较好反应某个节点信誉度的真实情况;但如果节点增加至200以上时,公式(-5)就无法很好的反应某个节点信誉度的变化。更改参数:当a取0.3,得到的结果如图9所示。
可以看出最后趋向的值由原来的0.6降为了0.56左右,但是信誉度的变化同样随着网络节点的增多呈现越来越平稳的趋势,说明不论a值的取值如何变化,当网络节点增加时信誉度的值就越来越不能准确反映节点的真实信誉。
通过以上的仿真结果可以看出本文所提出的信誉度的机制可以在一定程度上识别出恶意节点,使得网络更加安全,但是当网络过于庞大时,也就是从其他节点获得的评价太多时,反而会导致信誉度的计算值趋于一个固定值而不能很好的真实的反应出信誉度的变化,所以可以考虑在间接节点过多时只挑选从信誉度高的节点处获得评价,一来可以提高信誉度的准确性,二来可以减少计算时间和代价。最终的间接节点的数目的决定还留待做进一步的研究。
5. 总结
随着无线多跳网络在实际应用中的需求越来越广,无线多跳网络相应的信任机制需要给出合理构建方案,将贝叶斯网络应用到无线多跳网络中,在路由时引进节点信誉度的方法,可以有效地降低网络中的恶意节点。本文仅给出了在信誉度的计算公式,并且通过证明当网络节点数小于200时可以较好的发现某些恶意节点。但仍然存在当网络太大时,信誉度就不能很好的反映节点的真实情况的问题,针对这一问题仍需要进一步研究并给出更好的解决方法。
摘要:随着无线多跳网络在实际应用中的需求越来越广, 对网络的信任机制要求也逐步提高。通过引入贝叶斯网络的关联性机理, 基于节点信誉度来构建合理的信任机制, 可以有效地降低网络中的恶意节点, 提高网络性能。文章中通过模拟实验得出在中小规模的无线多跳网络中采用论文提出的机制可以很好的确定节点的信用度。
关键词:无线多跳网络,贝叶斯网络,信誉度
参考文献
[1]Ian F.Akyildiz and Xudong Wang.A Survey on Wireless MeshNetworks[J].IEEE Communication Magazine, September 2005:23-30.
[2]许力著, 无线传感器网络的安全和优化[M], 电子工业出版社, 2010, ISBN 978-7-121-10380-3.
[3]Li Xu, Yihui Zhang."A New Reputation-based Trust Man-agement Strategy for Clustered Ad Hoc Networks, "2009 Interna-tional Conference on Networks Security, Wireless Communicationsand Trusted Computing (NSWCTC 2009) .April, 2009.pp.116-119.
[4]王立, 吴蒙, 常莉, 移动Adhoc网络基于信誉系统的节点协作方案, 计算机技术与发展, 2010, 20 (3) , 32-35。
[5]张连文, 郭海鹏著, 贝叶斯网引论[M], 科学出版社, 2006, ISNB 7-03-018170-0.
贝耶斯网络模型 篇6
由于无线电频谱的限制,通信网络面临频谱资源稀缺的问题,另一方面,许多许可频谱仍然长时间[1]未被占用。认知无线电(CR)可提高频谱资源利用率,在CRs中,部分用户可以智能地监控环境并在分配的频段都处于闲置状态时能够与许可用户共享频谱,通过许可用户(PUs即主用户)和未经许可的用户(SUs即次级用户)[2]之间的频谱共享实现CR网络频谱利用率的增加。
本文提出了一种基于双向拍卖融合贝叶斯推理模型的频谱共享算法,假设主用户和次级用户是自相关博弈玩家,他们为了达到最大化收益的目的而做出决策。本文算法自适应地响应不断变化的系统环境和玩家数量,具有良好的可扩展性,为了达成有效拍卖共识,本文算法适用于现实世界CR系统的操作,同时能尽可能高的保持频谱效率。
1 相关研究
学者们提出了许多用于CRs中有效频谱共享的拍卖博弈模型[3],可更为有效地解决有限稀有资源分配问题。拍卖博弈模型通过减少未分配的频段数量可以提供更好的频谱共享,提高了整体资源利用率[4]。
文献[5]中的战略型频谱拍卖(SPSA)方案是一种真实且计算高效的频谱拍卖,支持类似e Bay的动态频谱市场,该方案允许无线用户获取并根据要求支付频谱。此外,SPSA方案通过分配频谱给最重视它的投标人能使频谱所有者利润最大化。然而,SPSA方案仅考虑购买者的单向频谱拍卖,该SPSA方案可直接扩展为真实双向频谱拍卖(TDSA)方案[6],TDSA方案支持真实双向频谱拍卖,其中多方可根据个性化需求交易频谱,该方案运用一种新的赢家确定和定价机制选择获胜买家和卖家,然而TDSA方案只假定简单的频谱需求/请求格式。文献[7]中重复拍卖贝叶斯学习(RABL)方案建模为一个重复拍卖博弈,该方案研究了由监控成本和访问成本构成的认知无线电系统的频谱接入问题。因此,重复拍卖模式已用于最大限度地权衡访问频段的收益和成本。此外,为了设计一种具有不完整信息的方案,构建了基于狄利克雷过程的非参数信念更新算法。文献[8]中的自适应拍卖频谱共享(AASS)方案是一种基于非合作博弈模型描述PUs和SUs之间竞争力的拍卖,该方案采用Hackner效用函数定义二次用户的频谱出价。此外,AASS方案为每个PU的成本函数提出了一种动态更新算法,这有助于在动态频谱共享博弈的每个阶段PUs从SUs实现更多的要求。文献[9]中的基于双向拍卖频谱共享(DASS)方案是一种基于动态频谱共享方案的双向拍卖,该方案允许免费频段在运营商之间交易,以提高频谱利用率,DASS方案使用自适应调节投标/询问策略研究实际的无线通信模型。
上述方案存在的主要问题有:首先,这些方案依赖于高复杂性和额外开销,无法在现实的系统操作中实施,因此仅限于较小的网络模型;其次,现有的方案不能自适应估计当前网络条件,在动态网络环境中可能造成潜在的错误决策;再次,这些方案有一些固定的系统参数操作网络系统,而在动态的网络环境中,操作现实世界的网络系统是不恰当的方法。受到上述讨论的启发,本文提出了一种新的CR频谱共享方案,将其设计为一个重复贝叶斯拍卖博弈。
2 提出的频谱共享算法
2.1 博弈模型
博弈理论在无线网络中可应用于资源分配[10],然而传统的博弈模型假设任意玩家需要的所有信息都完全已知,这并不符合现实情况。基于此,传统博弈模型不能直接应用于实际网络运营,文献[11]引入了贝叶斯博弈模型,该模型放宽了所有信息完全已知的假设,可以用于预测不确定性结果。
本文采用贝叶斯博弈方法解决CR系统中频谱共享问题,贝叶斯模型由一组玩家、一组动作、玩家类型和每个玩家的效用函数等组成[12],提出的贝叶斯拍卖博弈如下:
玩家:CR系统中PUs和SUs,N={1,2,...,N}和M={1,2,...,M}分别表示PU集合和SU集合,PUi∈N运行在频带Bi上,其与PUs其他的频带不重叠,即Bi∩Bk=Ø,∀i,k∈N。
动作集:任何PUi都具有所有可能报价的集合,是预计出售Bi频段的价格。任何SUj都具有所有可能出价的集合,这是SUi可以支付的价格。
玩家类型:玩家的类型是一个概率分布,用来表达有关博弈玩家不确定或未知信息的概念,类型独立且在重复拍卖阶段动态变化,每个玩家完全知道自己的类型,而不知道其他玩家的类型,因此概率分布用于假设其他玩家的类型。
效用函数:效用函数可量化玩家从特定结果获得的满意度,PUs的效用函数代表货币收益(即频谱交易收入),对于SUs,拍卖价格越高,效益越低,因此SUs的效用函数定义为PUs的保留效用,如果PUs或SUs频段交易失败,该收益将保持0。
本文算法可归结为一种重复博弈[13],该算法将时间轴划分为等长度间隔time_period(即Pt,t=0,1,2,⋯)。
2.2 双向拍卖协议
传统的拍卖主要涉及一个拍卖商(卖方)和多个投标人(买家),该结构称为单向拍卖,而在频谱共享的拍卖场景中,存在几个买家和卖家对频段进行投标(即愿意支付的价格)及报价(即预期的销售价格)的情况,该情况下的拍卖模式设计为多对多的双向拍卖结构。
模型中的系统操作员定义为拍卖商,负责定价和交易频段。N中PUs可以是卖方,卖家可以报价给拍卖商,以显示其在价格上的偏好,M中SUs可以是投标人,投标人投标购买频段。每个time_period,玩家之间的频谱拍卖(即PUs和SUs)周期性运行,对于每个拍卖阶段,买卖双方基于其效用函数估计频段价值,当所有的报价和出价送到拍卖商之后,拍卖商设置频谱共享交易价格,并决定哪个投标人从哪个卖家获得频段。采用普雷斯顿⁃迈克菲双向拍卖(Preston⁃Mc Afee Double Auction,PMDA)协议的基本概念决定商品价格,在每一轮拍卖结束后,拍卖商收集所有有关报价和出价的信息,并通过分类和匹配技术[14]决定交易价格,然后拍卖商对所有玩家宣布决定的商品价格,因此,玩家学习CR系统中当前频谱共享条件,SUs(即投标人)获得所需频段,在接下来的一轮拍卖不会提交新出价,如果一些SUs竞标频段失败,他们将提交新的出价给拍卖商,同时,如果一些PUs没有售出自己的频段,他们在下次拍卖时也将提交新的报价。因此,在每一轮拍卖中,剩下的玩家自适应地调整自己的价格,这种动态的拍卖程序依次重复每一个time_period(即串行拍卖),以达成有效拍卖共识。
2.3 贝叶斯推理和学习
贝叶斯博弈模型中,玩家学习修改自己的先验知识并自适应地调整策略。该方法并不假定玩家总是根据完整信息作出最佳决策,贝叶斯博弈的过程中,玩家有机会重新考虑目前的策略和应对以最大化期望收益,因此它提供了真实世界环境下更现实的模型。
玩家对频谱交易的渴望度强烈影响玩家的出价方案,通常情况下,玩家不知道其他玩家的愿望,但它实际上隐藏在每一轮拍卖中拍卖商的交易价格中。为了提交新的买价和卖价,买卖双方推断出下一轮交易价,这称为拍卖商类型。在每一轮拍卖中,玩家可以通过拍卖商的建议了解到别人的出价信息,基于该推论,每个玩家都可以为下一次拍卖做出更好的价格决策。
贝叶斯学习方法用来推断他人的渴望水平,根据贝叶斯定理和更新规则,贝叶斯推理公式[13]如下所示:
基于贝叶斯学习方法,开发每个玩家的价格调整过程,为了推断出下一轮交易价格,定义两个参数:拍卖商的让步比CRa和渴望水平η,它们用于贝叶斯推理公式中的假说,CRa估算如下:
式中:TP[t],TP[t-1]分别表示第t次和第(t-1)次博弈阶段的交易价格,如果CRa(t)是负值,则意味着拍卖商增加了交易价格。拍卖商第t个博弈阶段的渴望水平表示为η(t),η(t)值越高,对应于进行光谱段交易的愿望越强烈。假定η值范围固定在-0.5~0.5之间,且均匀地分成10个间隔,η值是离散集合的一个元素,即η∈{η0=-0.5,η1=-0.4,...,η9=0.4,η10=0.5}。
P(CRa(t)|ηi(t))为给定拍卖商渴望水平ηi(t)下拍卖商的让步比,P(CRa(t)|ηi(t))越高,在给定期望值η(t)时,拍卖商的让步比更可能是CRa(t)。本文假设概率密度函数P(CRa(t)|ηi(t))服从正态分布[15]:
式中:θ=(1-CRp(t))×ηi(t),CRp(t)为玩家自己的拍卖让步比,平均值μ和标准差σ产生不同的正态密度曲线,每个玩家有不同的μ值和σ值,使用式(3)定义另一个条件概率P(ηk(t)|CRa(t)),拍卖商在给定CRa(t)条件下的渴望水平ηk(t),根据贝叶斯更新规则,该P(ηk(t)|CRa(t))值如下:
基于Pt(ηk(t)|CRa(t)),Pt(ηk(t))值为:
式中:ηk={η0,η1,η2,...,η10}。
根据Pt(ηk(t))概率分布更新,当前拍卖人的愿望水平ηe可估计如下:
为了获得更精确的ηe值,贝叶斯推理过程重复迭代每一time_period,玩家持续监视当前的拍卖情况,以分布式方式决定自己的策略,最后,卖家和投标人可为下一轮拍卖调整自己的报价(Oft+1)和投标(Bit+1):
式中T_Pt为已公布的当前拍卖的交易价格(即第t个博弈阶段)。
2.4 本文算法的主要步骤
通过使用贝叶斯博弈模型为CR系统设计了一个新的频谱共享方案。提出的方案中,PUs和SUs(即博弈玩家)自适应地选择自己的拍卖价格分享频段。基于反馈学习过程,玩家可以捕捉如何调整自己的价格策略,为达成共识,该过程制定为重复拍卖模型。每一轮拍卖结束后,玩家定期检查目前的交易价格,并以完全分布式的方式迭代调整价格,因此玩家的数量增加时计算复杂度不会显著增加,这种交互式反馈过程持续进行,直到达成共识。提出的频谱共享算法的流程图如图1所示,主要步骤如下:
步骤1:初始迭代(t=0),每个拍卖商渴望水平Pt(ηk)的初始概率为均匀分布(Pt(ηk)=1/|L|,∀i,其中|L|是η时间间隔的总数)。
步骤2:每次拍卖阶段,频谱卖家i∈N={1,2,...,N}和频谱买家j∈M={1,2,...,M}发送报价oi和出价bj给拍卖商。
步骤3:拍卖商收集所有报价{o1,o2,...,on}和出价{b1,b2,...,bm},然后按递减排序报价,按升序排序出价。
式中π和σ为上述定义的顺序统计排列。
步骤4:拍卖商发现k,使得bπ(k)≥oσ(k)且bπ(k+1)<oσ(k+1),如果bπ(1)<oσ(1),继续执行步骤(5),否则拍卖商确定当前交易价格(T_P)。
步骤5:卖家提供的价格比T_P低,买家出价高于T_P,以T_P价格成功交易频段。
步骤6:拍卖商宣布目前T_P,并发送拒绝消息给当前一轮拍卖交易频段都不成功的卖家和投标人。
步骤7:以分布式方式,交易失败的卖家和投标人通过式(2)~式(7)动态调整拍卖价格。
步骤8:如果至少有一个卖方、一个投标人提交新的报价和出价,则转到步骤3进行下一轮拍卖,该迭代反馈过程一直持续到卖家和投标人达成共识,否则,进入终止步骤。
终止:拍卖博弈处理时间暂时结束,而CR系统持续自我监控,当新的频谱共享要求(即报价和出价)到达,它可以重新触发频谱共享算法。
3 仿真实验
进行仿真实验评估本文算法的性能,将本文算法与其他现有方案的性能做比较,并确认了本文算法的性能优势,为了确保该模型充分通用且在真实世界有效,假设如下:
(1)新的应用程序请求服务生成过程服从速率为λ(服务/秒)的泊松分布,提供的负载变化范围从0~3.0;
(2)CR系统的总频谱容量为5 Mb/s;
(3)基于50次模拟运行获得的结果,系统性能测量值绘制为每秒提供负载的函数;
(4)N中PU总数为30,M中SU总数为15;
(5)通过模拟获得的性能标准为PUs的收益、交易成功概率、频谱利用率、系统吞吐量、SUs请求阻塞概率、平均每轮拍卖次数等;
(6)频谱利用率定义为归一化的频谱效率,该值基于网络传输数据量进行测量;
(7)PUs的收益为频谱共享总价格;
(8)网络吞吐量为归一化值,为成功提供服务数据量与总数据量比值;
(9)为了表示各种多媒体应用,假设有四个不同的通信类型,基于连接的持续时间、频谱需求和Qo S要求,它们以相同的概率生成;
(10)对于不同的多媒体运用,应用程序服务的持续时间服从不同均值的指数分布。
对于多个应用程序,每个服务具有不同的流量特性,为了模拟真实的网络并进行公平的比较,本文使用现实模拟模型中给定的应用类型、特性和系统参数。表1为模拟中使用的多媒体应用程序类型和系统参数。
将本文算法与三个现有方案:RABL方案[1],AASS方案[6],DASS方案[7]的性能进行比较。
图2显示了所有方案的PUs总收益,从主用户角度看,收益是一个非常重要的因素,结果表明,应用程序请求率非常低(k<0.4)时,所有方案收入几乎相同。而当请求速率增加时,本文算法的PUs收益比其他方案更好。
图3给出了SUs服务阻塞率方面的性能比较,从次级用户的角度来看,服务阻塞概率是一个关键问题。由于适应性共享机制,本文提出的方案可避免频谱浪费,在各种流量负荷强度下,本文提出的方案可以提供比其他方案更低的服务阻塞率,这在实际网络运营中非常有用。
图4是系统吞吐量的比较,一旦应用程序服务完成,该服务的总传输速率即为系统的吞吐量。在服务连接中间没有增益累计的拒绝或终止服务,当服务请求速率增加时,拒绝服务的数量增加,则CR系统的吞吐量降低。基于自适应频谱共享策略,本文算法比其他方案更好地提高了系统的吞吐量。
图5显示了各种方案的频谱利用率,为了最大化系统性能,频谱利用率是一个重要的性能指标,所有的方案都有类似的趋势,而在各种请求速率下,本文提出的方案的频谱利用率比其他方案更好。
图6比较了各种方案中交易成功概率方面的性能。在不同系统负载情况下,本文算法比其他方案具有更好的成功概率,这确保本文算法能够提供一个有效的拍卖机制以共享频谱资源。
图7给出了各种方案平均拍卖轮数,拍卖轮数是指每轮拍卖频谱交易的平均数量,所有方案趋势类似,然而,基于贝叶斯学习过程的智能方法可以使拍卖模式更加适应当前的系统状况,因此本文算法可以比其他方案保持较低的拍卖轮数。
从图2~图7的模拟结果可以看出,在一般情况下,本文算法在多样化系统负荷强度下比其他现有算法更好。本文算法始终监视当前系统状态,且灵活度高、适应性强,能够感应到动态变化的系统环境,有显著的性能改进和更好的系统收益。因此,本文算法可以保持均衡的系统性能。
4 结语
本文提出了一种新的频谱共享算法,将其设计为一种重复贝叶斯拍卖博弈,在不具有完整信息的情况下,PUs和SUs通过贝叶斯学习过程自适应决定报价或出价。拍卖过程周期性进行,直到达成共识。由于自相关特性,价格调整决策以完全分布式方式进行,在现实世界系统操作中,该分布式控制方式是最终实现的适应方法。本文算法具有较好的适应性、可行性和有效性,能平衡系统的性能。仿真结果表明,本文算法在PU受益、交易成功率、频谱利用率、网络吞吐量等方面显著优于现有方案。