Target Tracking in Sensor Networks: A Distributed Constraint Satisfaction Approach

Authors: R.Mostafaei, A.Habiboghli, M.R.Meybodi

Abstract:

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.

Keywords: Distributed CSP, Target Tracking, Sensor Network

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060411

References:

[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.