Design Of Incentive Compatible Broadcast Protocols For Ad hoc Wireless Networks : A Game Theoretic Approach
MetadataShow full item record
An ad hoc wireless network is an infrastructure-less, autonomous system of nodes connected through wireless links. In many current applications of ad hoc wireless networks, individual wireless nodes are autonomous, rational, and intelligent and are often referred to as selﬁsh nodes, following game theoretic terminology. In an ad hoc wireless network, a typical node may be an intermediate node of a route from a source node to a destination node and therefore is often required to forward packets so as to enable communication to be established. Selﬁsh nodes may not always forward the packets since the forwarding activity consumes the node’s own resources. Such behavior by individual nodes may lead to suboptimal situations where nodes, through their actions, lead to a state that is undesirable from an overall network viewpoint. To counter this, there is a need to stimulate cooperation through methods such as providing appropriate incentives. In this thesis, our interest is in designing rigorous incentive based methods for stimulating cooperation among wireless nodes, in the speciﬁc context of broadcast. In particular, we address the Incentive Compatible Broadcast problem: how do we design broadcast protocols that induce truth revelation by the individual wireless nodes? We do this using a game theory and mechanism design framework. Incentive compatibility of broadcast protocols could manifest in two forms: (1) Dominant Strategy Incentive Compatibility (DSIC) (also called strategy-proofness) and (2) Bayesian incentive compatibility (BIC). A DSIC broadcast protocol is one which makes it a best response for every wireless node to reveal its true type, regardless of what the other nodes reveal. A BIC broadcast protocol is one which makes truth revelation a best response for a node, given that the other nodes are truthful. The DSIC property is stronger and more desirable but more diﬃcult to achieve. On the other hand, the BIC property is much weaker and easier to achieve. In this thesis, we ﬁrst design a DSIC broadcast protocol for ad hoc networks using the well known VCG (Vickrey-Clarke-Groves) mechanisms and investigate its properties and performance. Next, we design a BIC broadcast protocol, investigate its properties, and compare its performance with that of the DSIC broadcast protocol. Both the protocols developed in this thesis provide an elegant solution to the incentive compatible broadcast problem in ad hoc networks with selﬁsh nodes and help stimulate cooperation among the selﬁsh wireless nodes.
Showing items related by title, author, creator and subject.
Pranavadatta, DN (2018-07-28)A large software system is built by composing multiple programs, possibly developed independently. The component programs communicate by sharing data. Data sharing involves creation of instances of the shared data by one ...
A Mechanism Design Approach To Resource Procurement In Computational Grids With Rational Resource Providers Prakash, Hastagiri (2009-07-08)A computational grid is a hardware and software infrastructure that provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities. In the presence of grid users who are autonomous, ...
Subbian, Karthik (2009-05-28)Software Maintenance is becoming more and more challenging due to rapidly changing customer needs, technologies and need for highly skilled labor. Many problems that existed a decade ago continue to exist or have even ...