Cost-Constrained Resource Selection Game And Its Applications

Today, open network systems, such as Internet, have arguably surpassed the Von Neumann computer as the most important computational artifact. Open network systems are usually public access, dynamical and rapid growth in size.It is a computational artifact that was not created by a single entity, but usually emerged from many autonomous entities.These entities typically do not belong to the same authority and may not pursue common goals.Fully cooperative behaviors cannot be guaranteed. On the contrary, each entity tends to be "selfish" and just wants to maximize its own payoff. Thus, entities have varying relationships of competition with each other in system resource selection and allocation.Up to now, modeling, analysis and effectively control of this kind of competition have been paid much attention and become important research fields in computer science.Game theory is a mathematical theory about modeling and analyzing the strategic interactions among intelligent, rational decision makers.From the aspect of game theory, the phenomenon of entities competing with each other on resource selection and allocation is actually a game.Therefore, there have been a few works applying the game-theoretic approach to address the problem of competitive resource selection and allocation in open network environment. However, with the fast development of varying application of open network systems, some questions still remain unanswered not only about the modeling capability and mathematical properties of resource selection game but also the applications of resource selection game.In this thesis, based on the existed resource selection game, we propose a novel framework of resource selection game:cost-constrained resource selection game and analyze the basic mathematical properties of this game.The main contributions and novelties of this thesis are summarized as follows: ●The framework of cost-constrained resource selection game and its mathematical properties.We propose a novel game-theoretic framework of competitive resource selection:cost-constrained resource selection game (ccRSG). Oriented to the requirement of real application, three kinds of distribution rules of resource utility are proposed:equally distributed utilities rule,the distributed utilities rule with resource sharing incentive,and the distributed utilities rule based on marginal contribution. Each distributed utilities rule defined a specific ccRSG. With regard to each ccRSG, three primary mathematical properties intensively investigated in this thesis:(1)Existence:Do pure Nash equilibra exists in any instance of each ccRSG?(2) Efficiency:If pure Nash equilibria do exist, how efficient are they?(3)Convergence: Whether the game dynamics converge to a pure Nash equilibrium?The results obtained in this thesis effectively extend not only the theory of resource selection game, but also provide the rigid theoretical foundation for real applications in competitive resource selection environment.●A Game-theoretic Approach for Balancing the Tradeoffs between Data Availability and Query Delay in Multi-hop Cellular Networks.The selfish caching problem in multi-hop cellular networks (MCNs) is formulated as a non-cooperative game:data caching game.Towards balancing the tradeoffs between data availability and query delay in MCNs, an incentive mechanism based upon a payment model is set up for data caching game.The data caching game is proved to be a potential game. Thus, for the game, pure Nash equilibra can be obtained and the best response dynamics converge to a pure Nash equilibrium.Moreover, by properly setting the payoff distribution rule, caching proxies have incentive to or not to cache the same data to some extent. Thereby, the performance of data availability and query delay can be tuned in an adjustable-way, which results in a desirable service performance that service provider intends to achieve. ●Distributed Set k-Cover Algorithms for Fusion-based Coverage in Wireless Sensor Networks. For a wireless sensor network of which a lot of sensor nodes are intensively and randomly deployed, it can enhance coverage performance that partitioning sensors into different k covers and activating these covers in a round-robin fashion. This paper investigates a new coverage optimization problem named disjoint set k-cover for fusion-based coverage of WSN where sensor nodes are assumed using a fusion-based collective probabilistic sensor model.First, the problem is formulated as a fusion-based coverage game and then the game is proved as a potential game, such that the optimal solution is a pure Nash equilibrium.Second, we present the conditions that determine the independence of coverage utility among sensor nodes.Furthermore, two distributed algorithms only based on local information are proposed and proven to be convergent to pure Nash equlibria. Finally, via experimental results, we show that Nash equilibria can provide a near-optimal and well-balanced solution to the problem.