【作者】 张毅；

【导师】 伍民友；

【作者基本信息】 上海交通大学 ， 计算机系统结构， 2009， 硕士

【摘要】 当今计算机网络发展迅速,网络的行为方式也越来越社会化,即网络中分布的个体根据各自的策略来决定自己的行为,这种策略性分布式系统随着网络服务模式的改革而变得越来越重要,其研究主要包括动因(incentive)和机制设计(mechanism design)。系统的动因是一个困扰着许多科学家和管理者们的重要问题;而一个新的机制设计方法能够保证服务提供者的报价反映出服务的真实成本。机制设计从经济学和博弈论中得到的概念能够描述策略性的代理,提供代理的动因,因而个别自私的代理的利润最大化将会导致全局系统的最优化。在这项研究中,我们把机制设计用于各种策略性分布式系统。我们将解决一个悬而未决的重要理论问题,即服务覆盖网中有限能力代理的行为方式问题。我们也将应用机制设计于若干实际应用包括为代理服务设计的分布式覆盖网的任务分配,Web 2.0上的资源拍卖,认知无线电网络中结点的频段选择。研究结果将可被用于计算机和网络资源分配以最大化社会效益。首先我们研究服务覆盖网中资源管理的机制设计问题,该网络中的服务由策略性(strategic)代理提供。分布式系统中的资源通常是有限的,而现有的机制设计并不考虑代理的能力。一般情况下,Vickrey-Clarke-Groves(VCG)机制是唯一的这样一个协议设计方法,它使得每个策略性代理为自身利益而遵守协议,以使其效用最大化,我们指出当代理能力有限时,VCG机制不再是真实可信的(truthful)。所以,我们基于非统一价格设计了一套新的有限能力机制,它对服务代理提供补贴使得每个代理真实地申明其成本时最大化利润。我们对两个泛用的价格模型设计并评估我们的机制。接着我们研究认知无线电(CR)网络中频谱共享的机制设计问题,该问题是使用开放频谱的主要课题之一。进而,博弈论被用来分析和设计CR频谱接入机制,然而,大部分现有的设计把用户的协作行为作为前提,因为非合作的频谱共享会导致较差的性能。本文中我们专门研究如何在利己的CR无线网络中进行有效的分布式信道分配,我们假设每个二级用户会为共享一级用户的信道而产生成本,我们修改并运用著名的VCG机制来解决该问题。我们的贡献包含两个方面,一是对于博弈论,我们指出基于VCG的机制对于CR频谱共享问题是完全适用的,就像它被成功地运用于最优路由选择问题;二是对于CR无线网络,我们提出了一个有效的、产生较好性能的算法。我们给出了相关的分析和讨论。更多还原

【Abstract】 Computer networks have developed rapidly in recent years coupled with the socialization of their behavioral patterns, i.e. distributed individuals in networks decide on their own actions based on their strategies. Such strategic distributed systems become more and more important as network service model reforms. Incentive and mechanism design are two primary research topics of this field. The incentive of a system is an important problem which perplexes many scientists as well as supervisors. Meanwhile, a new methodology of mechanism design can ensure that the price quoted by the service provider reflects the real cost of the service. Mechanism design borrows ideas from economics and game theory in order to describe the strategic agents and provide incentives to them, leading to optimization of the whole system generated from maximization of each selfish agent’s profit in the system. In this research, we apply mechanism design to varieties of strategic distributed systems. We aim to solve an important but pendent theoretical problem, viz. behavioral pattern of capacity-aware agents in service overlay networks. We also design mechanisms for some practical applications, including task allocation in distributed service overlay designed for service agents, resource auction on web 2.0, Spectrum selection of nodes in cognitive radio network. The results are applicable to resource allocation in computer networks to maximize social benefit.We first study mechanism designs of resource management in service overlay, where services are provided by strategic agents. Usually, resources in distributed systems are limited. However, the current mechanism design does not take the capacity of agents into consideration. Traditionally, the Vickrey-Clarke-Groves (VCG) mechanism has been the only method to design protocols so that each strategic agent will follow the protocols for its own interest to maximize its benefit. We show that the VCG mechanism is not truthful anymore when the capacity of agents is limited. Thus, we have designed, based on non-uniform prices, a new capacity-aware mechanism which subsidizes the service agents so that each agent maximizes its profit if it truthfully reports its cost. Mechanisms for two widely used pricing models are designed and evaluated.Then, we turn to mechanism designs of spectrum sharing in cognitive radio (CR) wireless networks, which is one of the main challenges of open spectrum usage. Therefore, Game theory has been exploited for analysis and design of CR spectrum access schemes. However, most of the current designs make the assumption of cooperative behaviors among all the users, because non-cooperative spectrum sharing will lead to worse performance. In this paper, we specifically study how to conduct efficient distributed channel allocation in selfish CR wireless networks. We assume that each secondary user will incur a cost for sharing the channel which serves for primary users. We adapt and apply the famous VCG mechanism to this problem. The main contributions of ours are two-folds. First, for game theory, we show that the VCG based mechanism can be fully applicable for CR spectrum sharing problem just as it is successfully deployed for routing optimization problem. Second, for CR wireless networks, we present an efficient algorithm which will lead to a better performance. Analysis and discussion are provided.更多还原