Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Game Theory Based Routing in Wireless Networks


Scott Lye

on 16 November 2009

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Game Theory Based Routing in Wireless Networks

Game Theory Based Routing
in Wireless Networks What is it? analyze strategic interactions between multiple entities
predict expected behaviour using tools
best outcome possible GAME THEORY However, it is NOT Referring to parlour games, like chess.
An absolute solution to interactive situations - conclusions derived does not necessarily represent best outcome. Based on a few assumptions All players are rational, altruistic behaviour is unlikely.
In other words, they want to maximize own payoff.
Players have Preferences.
Finally, based on Laws of Thought/Consistency.
Problem: The increasing number of communication devices Affordable cost of tech. gadgets Demand for connectivity - facebook, twitter Need for Speed Inevitable increase of communication traffic & complexity Solution: ROUTING IN AD HOC NETWORKS Not centralized.
Mobile: Links break and connect.
Perform forwarding for others or send packets for itself - self configuring.
High mobility but limited power Link State Distance Vector Each node maintains a view of complete topology
Periodically broadcast neighbour link costs to other nodes via flooding
Applies shortest path algorithm.
e.g. OSPF, IS-IS Each node only monitors its neighbour links.
Broadcast own table to adjacent links, wait for neighbor to do the same - use info to update.
Computation efficient, easier to implement.
Choosing Routes node A wants to send 4 packets simulaneously to node B. There are two routes to B, via X or Y. the time taken (in ms) to transfer through these links are listed Nash Equilibrilium An Example... Thus, the Nash Equilibrium of Choosing Routes game is the strategy profile with 2 packets taking route X and another 2 taking route Y. From the standpoint of two packets divided to each route. if a packet were to chose X from Y. It would bring a change from 29.9 -> 34. Further analysis of other deviations will also produce such a unwanted situaton. Nash equilibrium: is the strategy profile s* with the property that no player can do better by deviating from s*. Example: Prisoner's Dilemma Two suspects in a major crime are held in separate cells. The police have enough evidence to convict them each of minor crime, but not enough to convict them of the major crime unless one of them acts as an informer against the other. If both of them stay quiet, both will be convicted of minor crime and spend one year in prison. If only either one of them finks, he/she will be freed and used against the other as witness, who will spend four years in prison. If both fink each other, they will spend 3 years in prison. supplement Source: xkcd.com matrix form of Prisoner's Dilemma game Objective To develop a network routing method based on game theory. Rules: Static and Non-cooperative Game Slide 1 Slide 2 Slide 3 The Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 How does all this fit in Ad hoc networks have agents which are independant.
Imagine if they can think one step ahead - make strategic decisions.
Add Behaviour to nodes - collectively aim an objective
utilize game theory to acheive mutual best outcome - even cooperation.
How to acheive it? slide 18 Network Simulator 2 - has the tools to create new protocols - do performance analysis - modelling.
Further study on game theoretic methods - repetitive, mixed games, extensive - realistic.
Understand other wireless protocols.
slide 19 ? Limitations Pervasive computing, sensor networks, mesh networks The payoff functions - challenging to represent preferences.
Networking mechanisms are hard to measure - power consumption, delays, pricing.
Outcome based on reliable model and does not reach tangible product development.
! slide 20
Full transcript