论文部分内容阅读
分布式系统可以被视为一个连接许多代理的网络。在传统的分布式系统中,代理们被假定为是服从性的,即他们遵循一定的算法。当许多计算机联结成为一个分布式系统时,系统的各个组成部分会有不同的利益关系。这样的分布式系统就可能是策略性的,即系统的不同部分有自己不同的动因。在一个策略性分布式系统中,策略性代理根据各自的利益做出反应。当每个理性而自私的代理只关心自己的私利时,动因问题就成为一个亟待解决的重要问题。在本文中,我们将研究网格和传感器网络中的动因问题,并设计相应的机制保证系统在每个节点Selfish的情况下仍能正常运行。我们首先研究了网格系统中资源的动态分配问题。现存的资源分配算法大都采用静态分配机制,如MinWork机制等。但静态资源分配的效率不高、扩展性差且与实际情况相差较大。针对静态资源分配的这些缺点,我们设计了一个动态资源分配机制。该机制假设所有的任务都遵循一定的概率模型随机产生,任务的规模和发生时间均为随机分布,目标是每个任务都能够在最短时间内完成。我们以二次价格密封拍卖理论为基础,提出了动态任务分配机制,并证明了我们的机制能够提供较高的资源利用率、良好的扩展性而且是Strategyproof的。通过深入研究微软的Sensor Web项目,我们还提出了针对无线传感网络的机制设计问题。该项目希望利用Internet连接全国甚至整个世界的传感器网络,做到信息共享。而且他们还利用了Web 2.0技术,开放了平台的接口,使人们能够自由上传自己的传感器资源。但我们也观察到了一些问题,其中最大的问题就是在相当长的一段时间里,该平台上的传感器资源并没有明显的增长,也就是说很少有人愿意把自己的传感器资源无偿上传。我们认为这正是缺少激励机制造成的后果,因此我们设计了一套激励机制,使人们有动因上传自己的传感器资源。我们首先把该系统抽象成两个博弈方,一方为资源提供者,一方为资源使用者。针对资源提供者,我们抽象出其成本模型。针对资源使用者,我们抽象出其价值模型。然后我们考虑了三种不同的应用场景,一是单资源提供者,多资源使用者,二是多资源提供者,单资源使用者,三是多资源提供者,多资源使用者。随后我们根据这些的场景设计了相应的机制。我们还证明了其中一些机制是Strategyproof的,这是一个很好的特性,保证了博弈各方都能说出自己真实的报价,从而使另一方做出理性判断。