CRISP: collusion-resistant incentive-compatible routing and forwarding in opportunistic networks

In opportunistic environments, tasks such as content sharing and service execution among remote devices are facilitated by relays (devices with short-range wireless connectivity) that receive data, move around, and then forward the data. To achieve high throughput, it is important to secure forwarding and provide incentives for participation by relays. However, it is extremely challenging to monitor the behavior of relays in an opportunistic network due to sparse connectivity. Existing schemes do not work when selfish/malicious relays collude with each other to forge routing metrics, drop useful data, flood the network, or earn extra reward. The credit scheme presented in this paper is the first in which routing as well as forwarding are incentive compatible. To design the scheme, the data transfer and loss in an opportunistic network are modeled as a non-linear generalized flow network. Then, optimality conditions for flow maximization describe the optimal behavior of a relay. This optimal behavior is made incentive compatible by requiring a relay to make a specific payment upon receiving the data and earn reward on forwarding the data. A cryptographic technique is used to make the scheme collusion resistant. Finally, a framework is proposed to implement CRISP in a completely distributed and opportunistic environment. Simulations on real and synthetic mobility traces validate a significant gain in throughput when compared with the existing credit schemes that are not incentive compatible.