A General Nash Equilibrium Semantic Cache Algorithm in a Sensor Grid Database - Data Management in Cloud, Grid and P2P Systems - page 13

A General Nash Equilibrium Semantic Cache
Algorithm in a Sensor Grid Database
Qingfeng Fan and Karine Zeitouni
University of Versailles-Saint-Quentin Laboratory PRISM,
78035 Versailles Cedex, France
[e-mail]
Abstract. Sensor grid databases are powerful, distributed, self-
organizing systems that allow in-network query processing and offer a
user friendly SQL-like application development. We propose an adap-
tation of a well-known cache-based optimization and cache replacement
policy to this context. Since the data are distributed and the sensor nodes
are mobile, the cost model is more complicated than in traditional query
optimization, because it should account for several factors, including the
semantics, location and time. Therefore, we need a trade-off between
those constraints. Our approach is based on a theoretical foundation for
the game and balance problem. In summary, we propose an approach
that (i) Based on the Nash Equilibrium scheme, an application of three
scalar coe cients is proposed in term of the analysis of the relationship
among semantic, time and location factors. (ii) After that, we specialize
and summarize the general Nash Equilibrium scheme utilizing the equal
correlation coe cient among the new and old vectors to find the point
of Nash equilibrium and resolves the scalar coe cients. (iii) It uses these
scalar coe cient to attain an optimum cost model of the semantic cache,
for query optimization in the context of distributed query processing.
(iv) We emphasize that this method can extend to any finite-dimension,
which are other schemes cannot do. Extended simulation results indicate
that our scheme outperforms existing approaches in terms of both the
response time and the cache hit ratio.
Keywords: Sensor Grid Database, Semantic Cache, Location Depen-
dent Query, Query Optimization, Nash Equilibrium.
1 Introduction
A Sensor Grid is a grid that gathers, distributes, and acts on information about
the behavior of all participants including suppliers and consumers. In mobile
sensor applications, users who carry portable devices such as mobile phones can
issue local queries i.e, queries that are dependent on the user's location, to learn
about their geographic surroundings [6]. However, those query operations are
usually frequent, whereas the resources of the sensor grid are limited. Therefore,
an optimal approach to handle local queries is needed. However, those Location
Dependent Queries become expensive in this environment, due to the sensor
nodes's resource limitations and the mobile communications cost. Hence, we