| |
Strategy-Proof Routing in Wireless Ad Hoc Networks
by Paolo Santi
Research at CNR Institute for Informatics and Telematics (IIT) in Pisa studies an application of Game Theory to the problem of preventing strategic behaviors when routing messages in wireless ad hoc networks.
Ad hoc networks (multi-hop wireless networks) are expected to revolutionize wireless communications in the next few years by complementing more traditional networking paradigms (Internet, cellular networks, satellite communications); they can be considered as the technological counterpart of the concept of 'ubiquitous computing'. However, in order for this scenario to become reality, several issues must be adequately addressed. One of these issues is how to stimulate cooperation among the network nodes. In fact, the nodes of an ad hoc network are usually owned by different authorities (private users, professionals, companies, and so on), and a voluntary and 'unselfish' participation of the nodes in the execution of a certain network-wide task cannot be taken for granted. Concepts borrowed from the theory of Mechanism Design can be used to tackle this problem. Mechanism Design is the branch of Game Theory that studies how to design protocols that stimulate players (in our case, network nodes) to behave 'unselfishly', cooperating to the achievement of a global goal. A distributed protocol with this feature is called strategy-proof.
One of the fundamental tasks any ad hoc network must perform is routing. Since the network is in general multi-hop, a routing protocol is needed in order to discover and maintain routes between far away nodes, allowing them to communicate along multi-hop paths. Unless carefully designed, routing protocols are doomed to perform poorly in presence of 'selfish' node behaviour. In general, a network node has no interest in forwarding a packet on behalf of another node, since this action would only have the effect of consuming its resources (energy, and available bandwidth). Thus, if many of the nodes act selfishly (as may well be the case when nodes are owned by different authorities), only a few multi-hop communications will take place, and the network functionality is compromised. Thus, the definition of strategy-proof routing protocols for ad hoc networks is of fundamental importance.
In our research, which is a joint activity with Stephan Eidenbenz at Los Alamos National Labs, USA, we have developed and studied a protocol for strategy-proof route discovery and packet forwarding in ad hoc networks. In particular, we have considered a reference application scenario in which the network is used to provide a certain wireless service (eg, internet access). In principle, ad hoc networking could be used to increase the service coverage: instead of requiring each customer to be directly connected to the base station, customers could be allowed to reach the base station along multi-hop paths, using the wireless devices (laptop, PDA, and so on) of other customers as intermediate nodes (see Figure). This way, the area in which the service is available could be much larger than the radio coverage area of the base station.
 |
| A multi-hop wireless network for internet access. The base station provides internet access to the network nodes through multi-hop wireless paths (red lines). |
In order to implement such an ad hoc network successfully, intermediate nodes must be motivated to act 'unselfishly', relaying packets on behalf of others. Typically, intermediate nodes receive compensation in the form of monetary payment for their "unselfish" behavior, which at least covers the cost that a node incurs by forwarding packets.
Our proposal is to use a protocol that implements a fully distributed, reverse, second-price single-item auction with reserve price. The basic idea is simple: when new customers want to access the service, they issue a 'connection request', stating the maximum amount that they are willing to pay (the reserve price). The connection request represents maximum commitment of the customer: if the connection actually takes place for less than the declared price, the customer only pays this amount. In this way, the customer has full control of the maximum amount of money that he will have to pay in order to send the packets. By using a second price auction mechanism (second-price auctions are necessary to ensure strategy-proofness), the minimum path to the destination is identified and, if the amount of money the sender should pay is below the reserve price, the transaction takes place.
After having formally investigated and proved that our protocol is strategy-proof, we are now working on its implementation and simulation. We are also investigating the overall economic efficiency and feasibility of our incentive-based system.
Besides the activity described here, our research group collaborates in the field of ad hoc networking protocols with the University of Modena and Reggio Emilia, Italy, and the School of Electrical and Computer Engineering, Georgia Tech., USA. In the field of combinatorial auctions theory, we have ongoing activities with the Department of Computer Science, Carnegie Mellon University, USA, and the Department of Economics, University of Siena.
Please contact:
Paolo Santi, IIT-CNR
Tel: +39 050 3152411
E-mail: paolo.santi iit.cnr.it
|
