Distributed constraint optimisation for resource limited sensor networks

This paper addresses the problem of self-organisation and coordination within Wireless Sensor Networks. It advocates the use of a multi-agent system and specifically the use of multi-agent distributed constraint optimisation algorithms. Developing agent-based software for low powered sensing devices introduces several problems to be addressed; the most obvious being the limited computational and energy resources available. This paper details the Constrained Limited Device Configuration (CLDC) implementation of two pre-existing algorithms for distributed constraint optimisation, namely Adopt and the Max–Sum algorithm. We discuss (1) a novel algorithm for bounded function mergers that reduces the communication overhead and the number of cycles in the factor graph of the Max–Sum algorithm and (2) how the footprint of Adopt has been reduced from the reference implementation. This work is evaluated through the use of the canonical multi-agent coordination problem, namely graph colouring.

► We discuss the application of Adopt and the Max–Sum algorithm to sensor networks. ► The bounded function mergers algorithm is introduced to improve performance. ► Performance gains of up to 58% are achieved using this approach.