Thwart selfish behavior in wireless networksOn Designing Incentive-Compatible Routing and Forwarding Protocols in Wireless Ad-Hoc Networks An Integrated Approach Using Game Theoretical and Cryptographic TechniquesAd-hoc networks with Selfish NodesSelfish nodes actionsSlide 5Game Theory as approachA Model of Ad-Hoc GamesSlide 8DominanceResultsWhy forwarding-dominant protocol does not exist?A New Solution Concept: Cooperation- Optimal ProtocolRouting StageVCG Payment: Private TypeVCG Payment: Mutually Dependent TypesPrevent Downstream node from CheatingRouting ProtocolForwarding StageForwarding protocolForwarding-Optimal ProtocolSlide 21Forwarding-Optimal Protocol (Cont’d)EvaluationCredit Balance and Energy ConsumptionImpact of CheatingConclusion and Future Work1Thwart selfish behavior in wireless networksselfishness at MAC layer (CSMA/CA)selfishness in packet routing & forwardingselfishness in shared spectrumOn Designing Incentive-Compatible Routing and Forwarding Protocols in Wireless Ad-Hoc NetworksAn Integrated Approach Using Game Theoretical and Cryptographic Techniques(presentation by Pietro Cassarà University of Palermo,based on Y. R. Yang’s slides)Sheng Zhong, Li (Erran) Li, Yanbin Grace Liu, Yang Richard Yang3Ad-hoc networks with Selfish NodesIn the wireless networks each node is active member in the routing and it must be able to forwarding the traffic.With the increasing number of wireless devices, it is inevitable that certain ad-hoc networks will consistof selfish nodes. nodes have their own individual goals nodes may not be obedient4Selfish nodes actionsSelfish nodes could cheat about link costsSelfish nodes could drop packets they should forward5Ad-hoc networks with Selfish NodesA problem is to find a protocol that by means of an incentive, “persuade” the nodes to route and forward the other’s traffic.How can we resolve this problem?A natural tool is the Game theory and the study of rational behavior in competitive, collaborative setting.6Game Theory as approachUsing the game theory we can model our problem as a game, but there are some problems: The game could have no solutionThe game could have many Nash equilibriums The game could not converge to the equilibrium that we want(To resolve these problems we must choose our model protocol carefully)7A Model of Ad-Hoc GamesAd-hoc network model:N nodes, each with a discrete set of transmission power levelsMinimal power for i to reach j: PijLowest cost (power) path routingAd-hoc games:Each player participates in routing and forwardingAction space: an action ai can be send/withhold/replace a message required by a protocolCheat -> replace a routing messageDrop -> withold a packeta-i is the set of actions taken by all nodes except ia is the set of all the actions taken by nodes8A Model of Ad-Hoc GamesThe utility of a node i is ui= -ci + pi ci is the cost of transmissionpi is the payment the node receives from the systemwhen it forwards the traffic Ignore cost of control packetsIf i transmits with power level l the cost is l αi , αi is the cost-of-energy parameter(If the node does not make any action ci=pi=0otherwise ci≠pi ≠ 0)9Dominancei.e. ai dominates all the other actionsStronger concept than best response (“for a-i“)It would lead to a single equilibrium (dominance principle in GT)A dominant action of a player maximizes its utility no matter what actions other players chooseui(ai, a-i)  ui(a’i, a-i) for any a’i  ai and any a-iAn ideal protocol would be routing&forward dominant protocol, i.e.“Say the truth” about link costs is a dominant action (routing dominant protocol)“Forward” is a dominant action (forwarding dominant protocol)10ResultsThere is a routing dominant protocolThere is no forwarding dominant protocolbut we can fall back to a good Nash Equilibrium where all the nodes forward the packetsi.e. forwarding is the best response to other nodes forwarding11Why forwarding-dominant protocol does not exist?Assume no one can overhear i and j’s transmissionAll nodes except i and j follow the protocol j always follows the protocol except dropping the first packet of a sessionActions of iai: follow the protocola’i : follow the protocol except dropping the first packet of a session Contradicts the definition of dominant action!j DSCiProof by contradiction:System can not distinguish ai from a’i , pi(ai , a-i) = pi(a’i , a-i)ai has greater cost than a’i, ci(ai , a-i) > ci(a’i , a-i)Therefore, pi(ai , a-i)- ci(ai , a-i)< pi(a’i , a-i)- ci(a’i , a-i) which is ui(ai , a-i) < ui(a’I , a-i)12A New Solution Concept: Cooperation- Optimal ProtocolDivide the ad-hoc game into two stages: routing stage and forwarding stageEach node’s action consists of routing subaction and forwarding subactionRouting stage: routing-dominant protocol following the protocol is a dominant subactionForwarding stage: forwarding-optimal protocol under routing decision, all packets are forwarded following the protocol is a subgame perfect Nash equilibriumCooperation-optimal protocol: a routing-dominant protocol and a forwarding optimal protocol under routing decision13Routing StagePrevent cheating in link costs using cryptographic techniquesRouting Protocol14VCG Payment: Private TypePayment pi=cost(LCP(S,D;-i))-cost(LCP(S,D)-{i})LCP(S,D;-i): min cost path without node iLCP((S,D)-{i}): min cost path with link starting at node i removedPrivate type = Each node knows the cost of downstream linkUnder the VCG payment mechanism, a player has no incentive to lie about its true cost15VCG Payment: Mutually Dependent TypesLink transmission cost is determined by two playersSender i sends with PemitReceiver j feeds back RR=Precv/Precvmin =Pemit/Pmin_emitEstimated min power Pij=Pemit/R Cost of transmission: cost(ij)= PijAB DSC664? 4Pemit=5, R = 5True cost of AB: 1 Truthfully helping A to report the cost is not a dominant routing subaction of B! Nobody lies:cost(LCP(S,D;-B))=6+6=12cost(LCP(S,D)-{B})=4+1=5pB=12-5=7, uB=7-4=3A cheats only (6x cost): cost(AB)=(5*6)/5=6LCP is through C, so pB=0B also cheats (3x feedback): cost(AB)=(5*6)/15=2cost(LCP(S,D))-{B}=4+2=6pB=12-6=6, uB=6-4=2 > 0!16Prevent Downstream node from CheatingCheating is not beneficial by increasing PijLess likely to be on LCP