Resource Optimization for Moving Target Tracking and Remote Sensing Using Minimum Flow Algorithm and Identifying Codes

27 Jul

Arunabha Sen, Professor at Arizona State University

External Presentation (External Speaker)

In this talk, we will discuss two resource optimization problems, one in the domain of moving target tracking with mobile trackers (e.g., drones) and the other in the domain of remote sensing using satellites as sensors. Target tracking problems have been studied extensively by researchers in the last few years. However, the problem of continuous tracking of a set of mobile targets using the fewest number of mobile trackers, even when the trajectories of all the targets are known in advance, has received little attention. In this talk, we discuss this problem, where the goal is to find the fewest number of trackers needed to track all the targets for the entire period of observation. Specifically, given a set of targets moving in different (known) trajectories in a two (or three) dimensional space, the objective is to find the fewest number of velocity-bounded trackers (e.g., UAVs) and their trajectories, so that all the targets are tracked during the entire period of observation. We formulate the problem as a network flow problem and find the solution utilizing the minimum flow computation technique. We present both analytical and simulation results for our solution technique.

In the second part of the talk, we discuss a monitoring (remote sensing) problem on the surface of the earth for significant environmental, social/political, and extreme events using satellites as sensors. We assume that the surface of the earth is divided into a set of regions, where a region may be a continent, a country, or a set of neighboring countries. We also assume that the impact of a significant event spills into neighboring regions and there will be corresponding indicators of such events. Careful deployment of sensors, utilizing Identifying Codes, can ensure that even though the number of deployed sensors is fewer than the number of regions, it may be possible to uniquely identify the region where the event has taken place. We assume that an event is confined to a region. As Earth is almost a sphere, we use a soccer ball (a sphere) as a model. In this model, there are 32 regions, corresponding to 32 patches that make up a soccer ball. From the model, we construct a Soccer Ball Graph (SBG), and show that the SBG has at least 26 sets of Identifying Codes of cardinality 10, implying that there are at least 26 different ways to deploy 10 satellites to uniquely monitor the 32 regions of the model Earth. It may be noted that 10 is both the upper and the lower bound of the number of satellites needed to uniquely monitor 32 regions. Finally, we discuss several different extensions of the Identifying Codes in a multitude of domains.

About Arunabha Sen

Arunabha (Arun) Sen is a Professor of Computer Science and Engineering at the School of Computing and Augmented Intelligence at Arizona State University ( He received his bachelor’s degree in Electronics and Telecommunication Engineering from Jadavpur University in Kolkata, India, and PhD degree in Computer Science from the University of South Carolina, Columbia, South Carolina, USA. He served as the Associate Chairman of the Computer Science and Engineering department of Arizona State University responsible for Graduate Programs and Research from 2001-7. As a Visiting Faculty, he spent sabbaticals at the University of California, San Diego, University of California, Berkeley, Columbia University, Wroclaw University of Science and Technology in Poland, INRIA, Lille, France, and the National University of Singapore.

His research interests are in resource optimization problems in a variety of networks, such as wireless, optical, sensor, electric power-grid, and social networks. He primarily studies the algorithmic issues related to the problems in these domains utilizing graph theoretic, game theoretic, and combinatorial optimization techniques. He has published over one hundred research papers in peer-reviewed journals and conferences on these topics. He has served as an Associate Editor of IEEE Transactions on Mobile Computing. His research is/was sponsored by various U.S. Government agencies, such as the National Science Foundation, U.S. Army Research Office, Air Force Office of Scientific Research, Defense Threat Reduction Agency, Office of Naval Research and the U.S. Department of Health and Human Services. He started the IEEE International Workshop on Network Science for Communication Networks (NetSciCom) in 2009, ACM International Workshop on Critical Infrastructure Network Security (CINS) in 2017 and IEEE International Workshop on Network Science for Quantum Communication Networks (NetSciQCom) in 2022.

This event will be conducted in English

  • Location: MR-A1 [Ramón] & MR-A2 [Cajal], IMDEA Networks Institute, Avda. del Mar Mediterráneo 22, 28918 Leganés – Madrid
  • Organization: NETCOM Research Group (Telematics Engineering Department, UC3M); IMDEA Networks Institute
  • Time: 12:00
  • Add to Calendar: iCalendar Outlook Google