论文部分内容阅读
联盟问题是多代理系统研究领域的一个重要课题。动态联盟问题是这一课题的一个重要分支。在多代理系统中关于联盟的研究主要集中在静态联盟的领域:Talal Rahwan提出了一种静态联盟收益算法(DCVC算法);Jennings,张新良等提出了静态联盟结构生成的各种任意时间算法。但是现实环境很多问题属于动态联盟问题,需要进一步对这一类问题进行研究。Klush和Gerber从经济学的角度概述了动态联盟问题;Ebden和Jennings以时间为环境变量,研究了宏观的动态联盟问题;本文从代理成员发生动态变化的角度,对动态联盟的收益计算,结构生成以及实际应用三个方面进行研究。
在动态联盟收益计算问题中,本文首先介绍了一种静态联盟收益算法(DCVC算法)。现实环境中整个系统和个别代理都是动态的,因此本文的主要工作是对DCVC算法解决动态联盟收益计算问题进行了扩展,提出了动态DCVC算法,解决了运用静态DCVC算法处理在联盟收益计算进程中加入和离开个别代理的情况存在冗余计算的问题,进而验证了动态DCVC算法可减少原DCVC算法处理动态联盟问题时所存在的冗余计算,使得动态DCVC算法的冗余计算量为0。
在动态联盟结构生成问题中,本文首先介绍了动态联盟结构生成的概念和环境。其次研究了动态环境下联盟结构生成的机制,并对已有的DCF-s框架的应用作了深入的探讨。动态规划算法(DP算法)是一种能在O(3n)时间复杂度内找到最优解的算法,但是作为非任意时间算法DP不能处理动态联盟的问题,因此本文最后以DP作为研究对象,从DP算法运行周期内和联盟结构生成后两个时间段进行了研究,应用动态的DP算法解决了简单的动态联盟问题。
在动态联盟的应用问题中,本文以多传感器网络作为应用对象,使用动态DCVC算法减少了在传感器状态周期变更时所产生的冗余计算,并在VC环境下模拟了随着传感器个数的增长动态DCVC算法与原DCVC算法关于联盟收益计算个数的比较,验证了其适应动态环境的特点。在多传感器网络中也对动态DP算法进行了模拟,得出在处理动态事件时动态DP算法可以显著降低对f1和f2表的存储量的结论。