REAct: Resource-Efficient Accountability for Node Misbehavior in Ad Hoc Networks based on Random Audits

Wireless ad hoc networks rely on multi-hop routes to trans-port data from source to destination. The routing function is implemented in a collaborative manner, with each node re-sponsible for relaying traffic to the destination. However, an increasingly sophisticated pool of users with easy access to commercial wireless devices, combined with the poor phys-ical and software security of the devices, can lead to node misconfiguration or misbehavior. A misbehaving node may refuse to forward packets in order to conserve its energy (selfishness), or simply degrade network performance (mali-ciousness). In this paper, we investigate the problem of uniquely iden-tifying the set of misbehaving nodes who refuse to forward packets. We propose a novel misbehavior identification sche-me called REAct that provides resource-efficient account-ability for node misbehavior. REAct identifies misbehaving nodes based on a series of random audits triggered upon a performance drop. We show that a source-destination pair using REAct can identify any number of independently misbehaving nodes based on behavioral proofs provided by nodes. Proofs are constructed using Bloom filters which are storage-efficient membership structures, thus significantly reducing the communication overhead for misbehavior de-tection