Cooperative Games, Phase Transitions on Graphs and Distributed Trust in MANET
Date: December 14 - December 17, 2004
Mobile ad-hoc networks (MANET) provide a relative new paradigm of wireless networking, which poses several formidable challenges for control, monitoring and management, due to the basically “infrastructureless” nature of these networks. Security is viewed in this paper as part of the control-operations-management functionality of MANET. An important and critical part of security is trust establishment and maintenance. We provide a description of distributed trust within the MANET framework that consists of two major components: (a) trust document distribution; and (b) distributed trust computation. Within (a) we summarize our earlier work on swarm-intelligence based trust document distribution schemes, including their major advantages as compared to other schemes as well as their performance. This paper is primarily addressing our new results within (b). Here we show that under a variety of schemes for distributed trust computation and establishment we have established strong connections with various components of the theory of random graphs. In this context we demonstrate how phase transitions (in this case they mean node transitions from nontrusted to trusted) can appear within a MANET. We link the existence and analysis of such phase transitions to dynamic cooperative games. We demonstrate that dynamic cooperative games provide a natural framework for analyzing several problems for MANET. We also demonstrate the fundamental influence of the topology of the MANET on these phase transitions. Finally we conclude with a preliminary description of results that describe the effects of mobility and topology change on these trust establishment schemes.