تجزیه و تحلیل شکل گیری ائتلاف و استراتژی های همکاری در شبکه های ad hoc

This paper focuses on the formal assessment of the properties of cooperation enforcement mechanisms used to detect and prevent selfish behavior of nodes forming a mobile ad hoc network. In the first part, we demonstrate the requirement for a cooperation enforcement mechanism using cooperative game theory that allows us to determine a lower bound on the size of coalitions of cooperating nodes. In the second part, using non-cooperative game theory, we compare our cooperation enforcement mechanism CORE to other popular mechanisms. Under the hypothesis of perfect monitoring of node behavior, CORE appears to be equivalent to a wide range of history-based strategies like tit-for-tat. Further, adopting a more realistic assumption taking into account imperfect monitoring due to probable communication errors, the non-cooperative model puts in evidence the superiority of CORE over other history-based schemes.

Cooperation enforcement mechanisms have been developed recently in the attempt to cope with the selfish behavior of nodes in mobile ad hoc networks (MANET). As defined in [5] and [6], a node is considered selfish when it does not participate in the basic network operation in order to save energy. As opposed to maliciousness, selfishness is a passive threat that does not involve any intention to damage the operation of networking functions by active attacks like route subversion, tampering with data, etc. In this paper we present two different approaches to assess the features of our cooperation enforcement mechanism CORE [6] and [7]. Using CORE, every node locally rates its neighbors through a monitoring mechanism. The observations collected by the monitoring mechanism are processed to evaluate a reputation value associated to each neighbor. The reputation value is used by CORE in a step-like cooperation policy: only nodes with a reputation that satisfy the requirement of being greater than a defined threshold are served (i.e. data and routing packets are forwarded), while nodes with low reputation values are gradually isolated from the network.

In this paper we presented two different approaches based on game theory to assess the features of the CORE cooperation enforcement mechanism. Although the two methods described in this paper focus on CORE as a specific mechanism, some conclusions can be drawn from this analysis towards the design of cooperation enforcement mechanisms in general. With the “cooperative approach” we introduced the concept of coalition of cooperating nodes as a subset of the nodes forming the network that exhibit a cooperative behavior. We then demonstrated that when cooperation is enforced through a mechanism like CORE the guaranteed size of a coalition of cooperating nodes is at least half of the size of the network. Furthermore, we were able to infer the necessary conditions for a node to join the coalition of cooperating nodes, as a function of the ERC-types. The main limitation of this approach derives from an intuitive representation of the CORE mechanism in the GT model. However, we believe that the “cooperative games” method is especially suitable to study the dynamics of coalition formation among a large number of nodes thus we plan to further investigate on a faithful representation of the CORE mechanism in this model.