A Distributed Constraint Optimization Approach to Wireless Network Optimization

Heeten Choxi, Pragnesh Jay Modi

We present a new algorithm called Variable Message Size (VMS) ADOPT for solving Distributed Constraint Optimization Problems (DCOP) which trades off message size and memory usage for running time. The algorithm is applied to a wireless network optimization problem, in which small robots act as wireless routers with the objective of maximizing signal strength in the network by repositioning themselves. Memory and bandwidth are limited resources in this application; our algorithm incorporates features of ADOPT and DPOP and introduces a parameter which controls the memory usage and message size at each agent. Bounded-error approximation can also be used to trade off solution quality for running time.

Subjects: 15.2 Constraint Satisfaction; 7.1 Multi-Agent Systems

Submitted: May 14, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.