期刊名称：International Journal of Distributed Sensor Networks
印刷版ISSN：1550-1329
电子版ISSN：1550-1477
出版年度：2011
卷号：2011
DOI：10.1155/2011/895398
出版社：Hindawi Publishing Corporation
摘要：We study game-theoretic mechanisms for routing in wireless ad hoc networks. Our major results include a combination of theoretical bounds and extensive simulations, showing that VCG-based routing in
wireless ad-hoc networks exhibits small frugality ratio with high probability. Game-theoretic mechanisms capture the noncooperative and selfish behavior of nodes in a resource-constrained environment. There have been
some recent proposals to use these mechanisms (in particular VCG) for routing in wireless ad-hoc networks, and some frugality bounds are known when the connectivity graph is essentially complete. We are the
first to show frugality bounds for random geometric graphs, a well-known model for ad-hoc wireless connectivity. In addition, we generalize the model of agent behavior by allowing sets of nodes to form communities
to maximize total profit. We are the first to analyze the performance of VCG under such a community model. While some recent truthful protocols for the traditional (individual) agent model have improved upon the frugality of VCG by selecting paths to minimize not only the cost but the overpayment, we show that extending such protocols to the community model requires solving NP-complete problems which are provably hard
to approximate.
