Seminar

Routing in Wireless Networks: Random Walks meet Game Theory on Random Geometric Graphs

Gunes Ercal-Ozkaya
Computer Science, UCLA

Friday, March 28, 2008
Troy 2018 . 2:00 p.m. to 3:00 p.m.
Refreshments at 3:30 p.m.

Abstract:

Wireless networks, such as sensor networks or general ad-hoc networks, present special challenges for routing problems due to high energy constraints and node autonomy. As such, traditional methods of constructing and fixing a centralized routing topology and then simply expecting nodes to forward accordingly in the absence of any further incentives to do so suffer reliability drawbacks. We look to modern proposals based on random walks and game-theoretic techniques to deal with these reliability concerns, and our results are theoretical guarantees of soundness and efficiency for these methods. We also find NP-Hardness (or even inapproximability) of further extending these results, showing that the proposed algorithms are in some sense also "as good as it gets" for the question. Several research themes arise, a prominent one being that: While a problem may be costly or hard in arbitrary cases, it may be cheap and feasible for relevant random models. The question of: "How did the graph arise?" becomes critical, leading one to appreciate new sources of answers for this question.

Bio:

More information about the speaker can be found here

Hosted by: Bolek Szymanski (x2714)

Administrative support: Chris Coonrad (x8412)

Last updated: September 7, 2005