基于博弈论的软件动态调控策略的研究与实现

摘　要：

关键词：

1.研究的背景与意义
　　近年来，软件的监控和管理问题引起了越来越多的关注。这主要有二个原因：首先，随着计算机网络的高速发展，诸如电子商务，社交网络以及各行各业的专业应用等等，这些在国民经济与个人生活中的作用日益突出。其次，各种在线系统、网络系统以及其他分布式系统的结构变得庞大，功能变得复杂，对稳定性、安全性和友好性有着极高的要求。这种对传统软件的扩展，打破了原有软件结构静态、封闭的局限。另外，由于需求多样，软件必须要在长周期内使用，需要不断的演化和持续。因此，对于现代软件，不能按照传统的软件的思路即事后管理维护、监控运行等，而是要进行动态监控与调控，实现可信性控制。
2.动态调控策略
　　调控技术是软件系统调整和控制的重要手段，包括静态调控和动态调控技术。目前动态、开放的环境导致软件系统的规模越来越大、功能越来越复杂，仅仅由管理人员手动在线调控已经变得非常困难，软件系统需要在开放的运行环境中“把握”和“调整”，因此引入策略来帮助软件系统来完成在线动态调控。策略是行动明确的目标，过程式方法的指导，以及现在和未来的决定，是用来做出决定和指导行动的一种声明性表达。策略是调控的基础，是引导系统行为的手段，可以辅助管理人员调控复杂的软件系统，也是软件系统自我调控的依据。
　　
3.博弈论概述
　　博弈论(game theory)又称对策论，起源于本世纪初。近30年来博弈论作为分析解决冲突与合作的工具，在管理科学、国际政治、生态学等领域得到了广泛的应用。在经济学领域中，博弈论经常用来解决实体之间的冲突和矛盾，它是研究决策主体的行为发生直接相互作用时的决策以及这种决策的均衡问题。针对动态调控中策略内发生冲突的现象，本文探讨引入经济学中的博弈论来解决此问题。
4.基于博弈论的调控策略的选取
　　对于复杂的软件系统而言，调控策略之间的关系是非常复杂的。调控策略之间除了一个策略的执行引发另一个策略的简单关系之外，还可能存在策略之间的冲突。策略冲突一般具有以下两种类型的策略冲突：（1）策略内冲突，两条或两条以上策略同时满足策略触发条件，并且每条策略动作不能与其它策略动作同时执行；（2）策略间的冲突，两条或两条以上策略同时应用于相同目标对象时发生冲突，如策略P1给agentl访问数据库的权利，而策略P2策略禁止agent2访问数据库。在所有满足条件的策略当中，有些策略可能在执行的代价方面比其它策略要优越，有些策略可能在执行的有效性方面具有优势，因此可以把触发一条最优策略看成是不同策略之间博弈的结果。利用博弈的效用评估函数计算每条策略的期望收益，通过比较每条策略的期望收益来决定具体触发哪条策略。本文设计出以下模型：
　　（1）博弈模型
　　博弈论模型的基本要素如下：参与者：Pi, Pj表示博弈过程的参与者;双方的战略空间：执行与不执行;
　　博弈的次序：博弈的双方是同时进行的，不存在先后顺序;得益：Upi, Upj表示博弈双方在一次博弈结束后的收益。
　　根据以上建立如表1所示的博弈模型。
　　表1软件调控策略的博弈模型

　　其中Pi、 Pj为同一策略事件触发的两条不同的调控策略，各自拥有两种行动方式执行和不执行。Ri表示在执行Pj策略的情况下执行Pi策略给Pi策略带来的收益，Rj表示在执行Pi策略的情况下执行Pj策略给Pj策略带来的收益；Ki表示在不执行Pj策略的情况下执行Pi给Pi策略带来的收益，Kj表示在执行Pi策略的情况下不执行Pj策略给Pj策略带来的损失；Li表示在执行Pj策略的情况下不执行Pi策略给Pi策略带来的损失，Lj表示在不执行Pi策略的情况下执行Pj策略给Pj策略带来的收益；Ci, Cj表示两者都不执行的情况下给Pi、Pj带来的损失。通过简单的画线法可以看出该博弈模型存在混和策略纳什均衡。现假定Pi策略执行的概率为x，则不执行的概率为1-x，Pj策略执行的概率为Y，则不执行的概率为1-y。可以求得Pi策略的期望收益为：

　　对公式4-1求偏导数可得：
　　
　　从而可以解得：
　　
　　同理可求得Pj策略的期望收益为：
　　
　　综合以上步骤，可以得出：
　　Pi策略执行的混和策略的概率为：
　　Pj策略执行的混和策略的概率为：
　　以上计算仅仅解决了调控策略以什么的样概率执行的问题，由于调控策略的可信等级的高低程度会影响着策略的执行，策略每次执行时的具体决策还需要考虑策略本身的信任等级和对方策略的执行概率。因此在策略执行之前必须预测调策略在各信任等级的概率，设p1、p2、p3、p4调控策略信任等级落在非常信任、比较信任、基本信任、不信任等级的概率，调控策略Pi在信任等级为k时选择执行的期望收益为：
　　
　　同理可以求得Pj在信任等级为k时选择执行的期望收益为：
　　
　　上式求得的是策略Pi在信任等级为k时的收益情况，若想得到策略Pi总体获利情况，需要对策略所有信任等级进行加权求和，Pi的总体收益如下：
　　
　　同理可求得Pj总体收益为：
　　
　　当E(Pi) > 0, E(Pj) < 0时，即Pi调控策略的期望收益大于零，Pj调控策略的期望收益小于零，则执行Pi；
　　当E(Pj) > 0, E(Pi) < 0时，即Pj调控策略的期望收益大于零，Pi调控策略的期望收益小于零，则执行Pj；
　　当E(Pi) > 0, E(Pj) > 0时，即两者的期望收益都大于零，则比较E(Pi)和E( Pj)的大小，若E(Pi) > E(Pj)，则执行Pi，否则执行Pj。
　　(2)举例：
　　下面以一个简单的应用实例来说明模型的具体应用。在软件动态调控中，策略执行的时间越长，对系统的影响越大，策略执行成功机率就越小，对系统产生的负面影响也越大，调控策略的时效性和有效性在动态调控中是最受关注的两个特性。假设调控策略Pi、Pj一条在时效性方面具有优势，另一条在有效性方面具有优势，执行他们的损益情况如表2所示:
　　表2策略损益表

　　设Pi、 Pj策略信任等级落在非常信任、比较信任、基本信任和不信任等级的概率如下表3所示。
　　表3策略信任等级概率

　　由可以求得Pi的在信任等级非常信任时的期望收益E(Pi, 1)为6. 89，Pj在信任等级为非常信任时的期望收益E( Pj,1)为7. 20，即Pi、Pj都非常信任等级时E(Pi,1) < E(Pj,1)，则执行Pj策略。
5.实验介绍
　　本文所设计的软件原型系统在实际工作时，至少分别部署在网络的五个节点上，节点间全互连。在系统的各节点分布在一个由10台通过10 0MB/s快速以太网连接的应用服务器构成的局域网上。为了评估动态调控的效果，针对前文所描述的情形分别做出以下简单的模拟实验。实验中使用性能测试工具LoadRunner模拟多个并发用户进行订单中请，随着用户的增多，系统的响应时间会延长。针对前文所涉及的情形，采用两种不同的调控方案进行动态调控。方案I表示采取事件—规则—动作的动态调控机制，即系统产生的事件触发相应的调整规则，对系统进行动态调整。方案II表示采取本文提出的基于策略的动态调控机制，在策略执行前对策略进行可信预评估，选取一条最优策略响应策略事件，在策略执行后对策略执行的调控效果进行评估，根据策略评估的结果对策略进行不断的优化。在完成相同调控任务的情况下，实验结果如图所示，随着执行次数的增多，方案I执行调控的成功率明显低于方案II，方案I调整成功的平均概率为67. 58%，方案II调整成功的平均概率达到75. 46%。
　　
　　图 不同策略执行成功次数对比
　　本文主要探讨了基于博弈论的软件调控策略。随着计算机网络技术的不断发展，在当前开放、动态的环境中，软件呈现出规模庞大、松散聚合、行为复杂的特点，提出了基于策略的动态调控方法，设计了适合软件动态调控的策略表示、策略部署框架，针对两种不同的应用情形，制定出不同的调控策略，对不同策略的调控效果进行评估，调控策略实现预期的调控目标。与其它调控方案进行了比较，本文的方案取得了比较好的调控效果。