Due to their inherent limitations in computational and battery power, storage and available bandwidth, mobile devices have not yet been widely integrated into grid computing platforms. However, millions of laptops, PDAs and other portable devices remain unused most of the time, and this huge repository of resources can be potentially utilized, leading to what is called a mobile grid environment. In this paper, we propose a game theoretic pricing strategy for efficient job allocation in mobile grids. By drawing upon the Nash bargaining solution, we show how to derive a unified framework for addressing such issues as network efficiency, fairness, utility maximization, and pricing. In particular, we characterize a two-player, non-cooperative, alternating-offer bargaining game between the Wireless Access Point Server and the mobile devices to determine a fair pricing strategy which is then used to effectively allocate jobs to the mobile devices with a goal to maximize the revenue for the grid users. Simulation results show that the proposed job allocation strategy is comparable to other task allocation schemes in terms of the overall system response time.
Grid computing provides a distributed computing infrastructure for solving large-scale advanced scientific and engineering problems through sharing of resources, usually over high-speed communication networks [8,9]. Computational grids typically have a conglomeration of various
resources with different owners at geographically different sites. Several Grid systems including Globus [7] have addressed many of these issues with the exception of resource trading and quality of service (QoS)-based scheduling. The GRACE [2] architecture leverages existing technologies such as Globus, and provides new services that are essential for resource trading and aggregation, depending on their
availability, capability, cost, and users’ QoS requirements.
An important issue of such grid computing systems is the efficient assignment of jobs and utilization of resources of unused devices, commonly referred to as the load balancing or job scheduling problem. This problem is often formulated in the context of a system model, an abstraction of the underlying
resources, that provides information to the job allocator regarding the availability and properties of resources at any point in time. The job allocator then allocates jobs to the available resources and attempts to optimize specified performance metrics, such as time deadline or revenue
maximization.
Given that millions of laptops, PDAs and other portable devices remain unused most of the time, the grid architecture is recently extended in [21] leading to what is called a mobile grid environment. The goal is to potentially utilize the huge repository of resources of mobile devices to provide a seamless source of computational power and storage capacity. However, this concept offers significant challenges mainly due to the inherent limitations in processing, memory, battery power and wireless communications capabilities of mobile devices. In a mobile grid, a more important performance
metric is system throughput where the resources are distributively owned. In this environment, a resource owner has the right to define a very sophisticated usage policy, e.g., a job can run on a mobile device only if it generates a certain minimum revenue. Distributed ownership requires
a scheduling paradigm that can operate in an environment where resource owners (i.e., mobile devices) and resource users (i.e., wireless access points servers) dynamically define
their own policies and models. Job scheduling in mobile grid computing thus demands
for a decentralized algorithm with a robust system model. We also need to consider an economic pricing model that will govern the cost benefits of mobile device owners to allow complex computational jobs to be performed at those devices. Due to the conflict of interest between the players, namely the mobile device and the wireless access point server (WAPS), this pricing model can be more realistically formulated using a non-cooperative bargaining theory [20]
framework. Although Game Theoretic approaches have been proposed to develop economic models for resource management and scheduling in grid computing [3], they suffer from precise
lack of formulation in the sense that the actual mapping of the problem into a game between two players has not been shown, nor are stated analytical modeling and results. Also, mobile grid computing is a completely new paradigm for which only a very crude economic model has been specified
in [21]. We envision that potentially there are many mobile devices distributed in the network, which will be competing to share the jobs originated by the grid community. There arise several challenging issues such as: (1) efficient job allocation to different mobile devices taking into account various performance requirements; (2) handling fairness in pricing the job allocation; (3) the ability to implement the allocation scheme in a distributed manner with minimum communication overheads;
(4) maximizing the network efficiency, i.e., minimizing the response time.
With the increasing demand for internet-connected wireless mobile devices and for the resource hungry computational grid, it is natural to propose efficient techniques to 0 2 4 6 8 10 12 14 16 18 20
0.4
0.5
0.6
0.7
0.8
0.9
1
Max Speed/Min Speed
Fairness
Ascending
Descending
Random
Fig. 19. Fairness vs. speed skewness.
harness the processing power of millions of wireless devices. Till now various approaches like SETI@Home, Legion, GRACE, Globus and commercial ventures such as Parabon, Entropia have been proposed in normal grid environment. But no work has been done in mobile grid computing.
We have designed an economic model and algorithmic framework so that resource hungry computational grids can buy and the mobile device can sell their computing power.
Because of the inherent limitations in storage capacity and bandwidth availability of wireless devices, we have to motivate the skeptical device owners to contribute their mobile devices during off period. This potential restriction leads to the design of our pricing model in such a way that it maximizes
the utility of both the grid community and all mobile users depending upon their respective strategies. In this paper, we have considered only two player games (one WAP server and one mobile device) for the time being. Multiplayer games will be more challenging due to the interaction between the mobile users under one WAP server. We plan to extend our work to model a (n+1)-player game between
the WAP Server and the n mobile devices within its range to give a better approximation of the interactions between the players. Finally, the job allocation strategy can also be improved by considering a complex cost function that characterizes the mobile grid scenario in a better fashion.
