论文部分内容阅读
当前,以Internet为代表的开放网络无疑已超越冯.诺依曼式计算机成为在未来几十年里最重要的计算环境。开放网络计算环境具有这样一些特性:它一个快速增长的、动态的系统、具有开放的架构,由大量属于不同组织、有着各自利益的自治计算个体构成。在系统资源的选择、分配上,个体之间有着复杂的竞争关系。描述、分析这种竞争关系并进行有效地控制受到了研究者的广泛关注,成为计算机科学领域的重要的研究方向。博弈论是研究多个自治个体决策行为的科学。事实上,从博弈论的角度来看,开放网络中的自治个体的竞争性资源选择行为是一种博弈现象,可以被建模为资源选择博弈。然而,面对开放网络环境实际应用需求的快速发展,各种复杂的资源选择博弈现象不断涌现,已有的资源选择博弈模型无论在模型的描述能力和相关数学性质的理论研究方面,还是在模型的应用研究方面都还存在不足。本文针对已有的资源选择博弈相关研究的现状和不足,基于已有研究所获得的相关成果,提出代价约束的资源选择博弈模型,对其在不同资源效用分配方式下的理论特性开展了深入研究,并以相关的理论研究成果为基础,来解决开放网络环境实际应用问题。本文的主要工作和创新之处总结如下:●代价约束的资源选择博弈模型及其数学性质研究。提出了代价约束的资源选择博弈的基本框架。面向实际应用需求,提出了三种具有不同资源效用分配规则,即基于平均分配的资源效用分配规则、带共同选择激励的资源效用分配规则、以及基于边际效用的资源效用分配规则。对于每一种资源效用分配规则定义的资源选择博弈模型,分析和研究了模型的三种重要的数学性质,即纯策略Nash均衡的存在性、博弈动态过程的收敛性、博弈解的Price of Anarchy。这些研究成果扩展了基本的资源选择博弈模型,获得了一些代价约束下的资源选择博弈新的理论结果,同时,为相关实际应用奠定了坚实的理论基础。多跳蜂窝网络中数据缓存的数据可获得性与查询延迟的折中控制方法研究。针对此问题,首先,将非合作环境下的多跳蜂窝网络数据缓存问题模型化为一种带共同选择激励的资源效用分配规则下的资源选择博弈,称之为数据缓存博弈。其次,以有效地折中非合作多跳蜂窝网络中缓存的数据可获得性(DA)和数据查询延迟(QD)为目标,给出了一个基于带共同选择激励的资源效用分配规则的DA和QD折中控制方法。然后,分析了数据缓存博弈的Price of Anarchy。最后,通过仿真实验验证了我们所提出的方法的有效性。基于融合的无线传感器网络k-集覆盖的分布式算法研究。在节点高密度随机部署的无线传感器网络中,将节点划分为k个互不相交的子集,各个子集轮番激活工作可有效地提高网络的覆盖效能。当节点采用概率感知模型且融合多个节点的数据进行联合感知的情况下,本文提出了一个新的无线传感器网络的覆盖优化问题:基于融合的无线传感器网络k-集覆盖优化问题。首先,将优化问题模型化为一个基于边际效用分配规则的资源选择博弈模型,称之为融合覆盖博弈。融合覆盖博弈具有一些好的数学性质,例如,极值解是纯策略Nash均衡、最优解是纯策略Nash均衡、最优响应动态收敛到纯策略Nash均衡,且在最优响应动态过程中,节点覆盖效用增加蕴含着系统总体的融合覆盖效用增加。其次,给出了节点间融合覆盖效用独立性的判定条件,进而分别提出了同步、异步控制的、基于局部信息的、分布式的覆盖优化算法,证明了算法收敛到纯策略Nash均衡。最后,通过仿真实验结果表明,当算法收敛时,无线传感器网络能达到高的覆盖率且具有好的覆盖稳定性。