טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDrabkin Anna
SubjectMaximum lifetime Equilibrium in topology control games in
ad hoc networks
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Ariel Orda
Mr. Amir Ronen
Full Thesis textFull thesis text - English Version


Abstract

This thesis addresses a problem at the nexus of networking and game theory: how self interested nodes construct network topologies in wireless communication networks? Through a unified utility-based framework, we study topology control problems in distributed wireless networks.


We consider the following network topology game: Given is a wireless communications network shared by n selfish nodes, each with a limited energy supply (battery). Each node aims to be connected to all the other nodes in the network for a maximal amount of time. The welfare of the system is the maximal period in which all nodes are connected. Each node chooses its own transmission power and thus its lifetime.


We prove that every such game admits a pure Nash equilibrium. While at the worst case the price of anarchy of connectivity games can be Θ(nα), where α is the path loss factor and n is the number of nodes, we show that a game with randomly distributed nodes and battery fading affect has a price of anarchy of 1. Additionally, we show that every network with only one base station admits a pure Nash equilibrium with optimal welfare. Yet, these properties are not preserved when nodes need to broadcast to only subsets of the other nodes.