Target Tracking in Sensor Networks: A Distributed Constraint Satisfaction Approach

In distributed resource allocation a set of agents must assign their resources to a set of tasks. This problem arises in many real-world domains such as distributed sensor networks, disaster rescue, hospital scheduling and others. Despite the variety of approaches proposed for distributed resource allocation, a systematic formalization of the problem, explaining the different sources of difficulties, and a formal explanation of the strengths and limitations of key approaches is missing. We take a step towards this goal by using a formalization of distributed resource allocation that represents both dynamic and distributed aspects of the problem. In this paper we present a new idea for target tracking in sensor networks and compare it with previous approaches. The central contribution of the paper is a generalized mapping from distributed resource allocation to DDCSP. This mapping is proven to correctly perform resource allocation problems of specific difficulty. This theoretical result is verified in practice by a simulation on a realworld distributed sensor network.

• R.Mostafaei
• A.Habiboghli
• M.R.Meybodi

• Distributed CSP
• Target Tracking
• Sensor Network

[1] K.Decker and J. Li. Coordinated hospital patient scheduling. In ICMAS,
1998.
[2] Hiroaki Kitano. Robocup rescue: A grand challenge for multi-agent
systems. In CMAS, 2000.
[3] Sanders. Ecm challenge problem, http://www.sanders.com/ants/ecm.htm.
2001.
[4] M. Yokoo and K. Hirayama. Distributed constraint satisfaction algorithm
for complex local problems. In ICMAS, July 1998.
[5] C. Frei and B. Faltings. Resource allocation in networks using abstraction
and constraint satisfaction techniques. In Proc of Constraint
Programming, 1999.
[6] Pragnesh Jay Modi et all. Dynamic Distributed Resource Allocation: A
Distributed Constraint Satisfaction Approach. University of Southern
California, 2003.