Agent-based decentralised coordination for sensor networks using the max-sum algorithm
OA Location
Author(s)
Farinelli, A
Rogers, A
Jennings, NR
Type
Journal Article
Abstract
In this paper, we consider the generic problem of how a network of physically distributed, computationally constrained devices can make coordinated decisions to maximise the effectiveness of the whole sensor network. In particular, we propose a new agent-based representation of the problem, based on the factor graph, and use state-of-the-art DCOP heuristics (i.e., DSA and the max-sum algorithm) to generate sub-optimal solutions. In more detail, we formally model a specific real-world problem where energy-harvesting sensors are deployed within an urban environment to detect vehicle movements. The sensors coordinate their sense/sleep schedules, maintaining energy neutral operation while maximising vehicle detection probability. We theoretically analyse the performance of the sensor network for various coordination strategies and show that by appropriately coordinating their schedules the sensors can achieve significantly improved system-wide performance, detecting up to 50% of the events that a randomly coordinated network fails to detect. Finally, we deploy our coordination approach in a realistic simulation of our wide area surveillance problem, comparing its performance to a number of benchmarking coordination strategies. In this setting, our approach achieves up to a 57% reduction in the number of missed vehicles (compared to an uncoordinated network). This performance is close to that achieved by a benchmark centralised algorithm (simulated annealing) and to a continuously powered network (which is an unreachable upper bound for any coordination approach).
Date Issued
2014-05
Citation
Journal of Autonomous Agents and Multi-Agent Systems, 2014, 28, pp.337-380
Start Page
337
End Page
380
Journal / Book Title
Journal of Autonomous Agents and Multi-Agent Systems
Volume
28
Identifier
http://eprints.soton.ac.uk/350670/
Subjects
Science & Technology
Technology
Automation & Control Systems
Computer Science, Artificial Intelligence
Computer Science
Decentralised coordination
Max-sum
Wide area surveillance
Sensor networks
GENERALIZED DISTRIBUTIVE LAW
CONSTRAINT OPTIMIZATION
Artificial Intelligence & Image Processing
0801 Artificial Intelligence And Image Processing
1702 Cognitive Science
Notes
The software associated with this paper can be downloaded from: http://profs.scienze.univr.it/\char126farinelli/pubs/sensorcoverage-release.zip
Article Number
3