Computational Game Theory Model for Adhoc Networks

Abstract

Given a distribution of pebbles on the vertices of a connected graph G, the
pebbling move consists of removal of two pebbles from a vertex and placing one pebble
on its adjacent vertex, discarding the other pebble. Effective data transmission with
considerable packet loss is an important factor of concern in any adhoc network. For a
Vehicular Adhoc Network (VANET), the inter-vehicular communication considers
packet loss such as time, fuel and dissemination of information. This problem can be
visualized in pebbling terminology where the packet loss refers to the loss of pebbles
and pebbling move refers to the transmission of information from one vehicle to another
vehicle. Further, to reduce the packet loss during message transmission in any adhoc
network we have proposed a new variation of pebbling called generalized optimal cover
pebbling. It deals with the determination of generalized optimal cover pebbling number
( ) 0 G
?
?
which provides solution to the above scenario. The generalized optimal cover
pebbling number of a graph G, ( ) 0 G
?
?
is the least positive number of pebbles required to
be placed on a set of vertices in such a way that after a pebbling move all the vertices of
G will have same number of pebbles in one unit of time.
In this paper, a new variation of pebbling called generalized optimal cover pebbling is proposed
and
( ) 0 G
?
?
are determined for certain classes of graphs. Further, an upper bound for the Cartesian
product of two graphs are also obtained and proved for paths, cycles, stars and complete bipartite
graphs.