etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >
Please use this identifier to cite or link to this item:
|Title: ||Design Of Incentive Compatible Broadcast Protocols For Ad hoc Wireless Networks : A Game Theoretic Approach|
|Authors: ||Narayanam, Ramasuri|
|Advisors: ||Narahari, Y|
|Keywords: ||Wireless Communication Protocols|
Computer Network Protocol
Broadcast Protocols - Compatibility
Dominant Strategy Incentive Compatibility
Bayesian Incentive Compatibility
Incentive Compatible Broadcast
Mechanism Design Theory
Ad hoc Wireless Networks
|Submitted Date: ||Jun-2006|
|Abstract: ||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.|
|Appears in Collections:||Computer Science and Automation (csa)|
Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.