Johns Hopkins EN 600 647 - Incentive Compatible Cost- and Stability-Based Routing in Ad Hoc Networks

Unformatted text preview:

Incentive Compatible Cost- and Stability-Based Routing in Ad HocNetworksMingming Lu, Feng Li, and Jie Wu∗Department of Computer Science and EngineeringFlorida Atlantic UniversityBoca Raton, FL 33431AbstractIn this paper, we embed an incentive-compatible, ef-ficient, and individual rational payment scheme into ourcost- and stability-based routing protocol in ad hoc net-works which consist of selfish nodes. Unlike traditionalrouting protocols in ad hoc networks, which only elicitcost information from selfish nodes, our protocol moti-vates selfish nodes to report truthfully both their stabilityand cost information.Keywords: Ad hoc networks, routing, incentive-compatibility, payment, stability, VCG mechanism.1 IntroductionTwo prominent characteristics of ad hoc networks arepower scarcity and instability. Existing routing proto-cols address these two problems either separately or sim-ply combinatorially. Our previous work [5] proposes anew metric to evaluate the efficiency of a routing schemeby integrating link cost and link stability into a singlemetric and designs an optimal r outing algorithm, MaxU-tility. In [5], we assume our algorithm has full controlof nodes and has priori knowledge of cost and stabil-ity information. However, the assumptions are not truein ad hoc networks consisting of selfish nodes. In thispaper, we relax the assumptions and design a two-stagerouting protocol, which satisfies incentive-compatibility,efficiency, and individual rationality.In our model, a source intends to buy a path to trans-mit its packets to a destination and receives a benefit foreach successfully delivered packet. Although there ex-ists packet loss due to unstable links (nodes), the sourcestill accepts the partial delivery of packets if the sum ofbenefits are larger than the sum of transmission costs.Assuming that intermediate nodes are selfish and ra-tional but they do not collude and that each node has a∗This work was supported in part by NSF grants ANI 0073736,EIA 0130806, CCR 0329741, CNS 0422762, CNS 0434533, and CNS0531410. Email: {mlu2@, fli4@, jie@cse.}fau.edupriori knowledge about its node stability and the costsof links, where it is an endpoint, our goal is to use in-centive methods to motivate intermediate nodes to re-port true cost and stability information. We use socialwelfare[6], which is defined as the total utility of all thenodes, as the metric to define our goal. Here, the utilityof the source is its benefit minus the total payments tothe intermediate nodes. A intermediate node’s utility isdefined as its payment from the source minus its cost.Most existing works adopt the Vickrey-Clarke-Groves (VCG) mechanism [6] to elicit truthful informa-tion from intermediate nodes in order to find the optimalroute. The idea behind the VCG mechanism is utilizingthe payment to determine intermediate nodes’ utility sothat each intermediate node’s utility is consistent withthe social welfare. Therefore, each intermediate nodehas to tell the truth in order to ma ximize its utility.However, the traditional VCG payment scheme [1, 3,7] adopted in ad hoc networks applies only to the caseof successful packet delivery, therefore, the VCG mech-anism cannot be directly applied to our problem due topartial packet delivery. If we do not pay intermediatenodes in case of delivery failure, it v iolates the individ-ual rationality principle [6]. This principle points outthat each forwarding node should not be worse than anon-forwarding node, i.e. a node should not get negativeutility by forwarding a packet. To ensure fairness to in-termediate nodes, we design a partial payment scheme,in which a node will get paid for each packet that it helpsforward, no matter if the packet reaches the destinationor not.Because the incentive method alone cannot stimulateintermediate nodes to report stabilities truthfully, we d i-vide our ad hoc routing protocol into two stages: theroute discovery stage and the packet forwarding stage.We postpone the payment calculation after the packetforwarding stage b ecause the true stability can be ob-served by neighbor nodes during the packet forwardingstage but is unknown in the route discovery stage.In the route discovery stage, the source collects thecosts and stabilities reported by intermediate nodes.1A cryptographic technique is integrated to prevent theneighbors from tampering with the reported cost andstability when they forward a route discovery m essage.In the packet forwarding stage, a neighborhood surveil-lance mechanism is integrated into our VCG-based pay-ment scheme.We utilize an incentive method to motivate neighborsto overhear the actual p acket forwarding of intermed iatenodes, and to report such information to a trusted creditcenter (TCC). TCC will count the number of packet col-lected by each node, calculate the stabilities of interme-diate nodes, and inform the destination of the stabili-ties. We also use a cryptography technique to preventthe neighbors from fabricating the information it obtainsduring the surveillance.To avoid intractable analysis, we make some as-sumptions about the behavior of the intermediate nodes,which make the model simple enough but neverthelesslead to useful models. (1) The source and d estinationare assumed not to be selfish. Although we can re-move this assumption by introducing multiple source-destination pairs b ecause competition among source-destination pairs can enforce truthfulness, for the sakeof presentation, we consider only one source-destinationpair and thus assume both source and destination areobedient. (2) The network is bi-connected. This as-sumption can suppress the overpayment problem [2], butthe overpayment problem cannot be totally removed un-less the topology control method [3] is adopted. (3) Weassume there is a secure and stable chann el, as illustratedin [9], between TCC and each node. The implement ofTCC can be either a centralized or distributed implemen-tation.2 Preliminaries and Related Work2.1 The related workAnderegg and Eidenbenz [1] first apply the VCGmechanism to routing protocols in ad hoc networks.They adopted the energy cost of nodes as private infor-mation, used the lowest energy cost model to study thead hoc routing problem. They also presented a reason-able way to estimate a node’s cost, whose drawback waspointed out by [10].Zhong, Li, Liu, and Yang [10] used a two-stage rout-ing protocol to model the ad hoc routing problem. Theyintegrated a novel cryptographic technique into the


View Full Document

Johns Hopkins EN 600 647 - Incentive Compatible Cost- and Stability-Based Routing in Ad Hoc Networks

Documents in this Course
Mobile IP

Mobile IP

33 pages

WiMAX

WiMAX

31 pages

Load more
Download Incentive Compatible Cost- and Stability-Based Routing in Ad Hoc Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Incentive Compatible Cost- and Stability-Based Routing in Ad Hoc Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Incentive Compatible Cost- and Stability-Based Routing in Ad Hoc Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?