×

Spatial and temporal robustness for scheduling a target tracking mission using wireless sensor networks. (English) Zbl 1511.90169

Summary: Robust scheduling for target tracking with a wireless sensor network (WSN), focuses on the deployment of a WSN in a remote area to monitor a set of moving targets. Each sensor operates on a battery and is able to communicate with reachable sensors in the network. The targets are typically moving vehicles (planes, trains, cars,…) passing through the area. In order to monitor the targets, an activation schedule is sought such that the sensor network is continuously collecting data about the targets. Additionally, the transfer of the data collected to a base station deployed near the network also has to be planned. In this work, we consider that the trajectories of the targets are estimated. i.e., during the mission, at each time instant \(t\), there is a given position where the target is expected. However, such estimations are inaccurate and deviations can occur. In this work, we formulate the problem of spatial robust scheduling. The aim is to produce an activation schedule for the sensors such that the targets are covered as long as they remain no farther from their estimated positions than a maximized value, called the spatial stability radius of the schedule. Afterwards, we formulate the spatio-temporal robustness problem. It is a bi-objective problem, with a spatial stability radius and a temporal stability radius for covering delays and advances. Two algorithms are proposed to solve these problems, and we show their efficiency through several numerical experiments.

MSC:

90B35 Deterministic scheduling theory in operations research
90C05 Linear programming
90C17 Robustness in mathematical programming

Software:

CPLEX; PaGMO

References:

[1] Akyildiz, Ian F.; Weilian, Su; Sankarasubramaniam, Yogesh; Cayirci, Erdal, A survey on sensor networks, IEEE Communications Magazine, 40, 8, 102-114 (2002)
[2] Benini, Luca; Castelli, Giuliano; Macii, Alberto; Macii, Enrico; Poncino, Massimo; Scarsi, Riccardo, A discrete-time battery model for high-level power estimation, (Proceedings of the conference on design, automation and test in Europe (2000), ACM), 35-41
[3] Beume, Nicola; Fonseca, Carlos M.; López-Ibáñez, Manuel; Paquete, Luís; Vahrenhold, Jan, On the complexity of computing the hypervolume indicator, IEEE Transactions on Evolutionary Computation, 13, 5, 1075-1082 (2009)
[4] Biscani, Francesco; Izzo, Dario, A parallel global multiobjective framework for optimization: pagmo, Journal of Open Source Software, 5, 53, 2338 (2020)
[5] Castaño, Fabian; Bourreau, Éric; Rossi, André; Sevaux, Marc; Velasco, Nubia, Partial target coverage to extend the lifetime in wireless multi-role sensor networks, Networks, 68, 1, 34-53 (2016), URL: https://hal.archives-ouvertes.fr/hal-01328424
[6] Chu, Qi; Ouyang, Wanli; Li, Hongsheng; Wang, Xiaogang; Liu, Bin; Yu, Nenghai, Online multi-object tracking using cnn-based single object tracker with spatial-temporal attention mechanism, (Proceedings of the IEEE international conference on computer vision (2017)), 4836-4845
[7] Cplex optimiser. https://www.ibm.com/analytics/cplex-optimizer. Accessed: 13-07-2020.
[8] Delavernhe, Florian, Lersteau, Charly, Rossi, André, & Sevaux, Marc (2020). Robust scheduling for target tracking using wireless sensor networks. Computers & Operations Research (p. 104873). · Zbl 1458.90190
[9] Durišić, Milica Pejanović; Tafa, Zhilbert; Dimić, Goran; Milutinović, Veljko, A survey of military applications of wireless sensor networks, (2012 Mediterranean conference on embedded computing (MECO) (2012), IEEE), 196-199
[10] Hornsby, Kathleen; Egenhofer, Max J., Modeling moving objects over multiple granularities, Annals of Mathematics and Artificial Intelligence, 36, 1-2, 177-194 (2002) · Zbl 1001.68135
[11] Jeung, Hoyoung; Liu, Qing; Tao Shen, Heng; Zhou, Xiaofang, A hybrid prediction model for moving objects, (2008 IEEE 24th international conference on data engineering (2008), IEEE), 70-79
[12] Kuo, Cheng-Hao; Huang, Chang; Nevatia, Ramakant, Multi-target tracking by on-line learned discriminative appearance models, (2010 IEEE computer society conference on computer vision and pattern recognition (2010), IEEE), 685-692
[13] Laumanns, Marco; Thiele, Lothar; Zitzler, Eckart, An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method, European Journal of Operational Research, 169, 3, 932-942 (2006) · Zbl 1079.90122
[14] Lersteau, Charly; Rossi, André; Sevaux, Marc, Robust scheduling of wireless sensor networks for target tracking under uncertainty, European Journal of Operational Research, 252, 2, 407-417 (2016) · Zbl 1346.90365
[15] Lin, Haitao; Yang, Xiaopeng, Dichotomy algorithm for solving weighted min-max programming problem with addition-min fuzzy relation inequalities constraint, Computers & Industrial Engineering, 146, Article 106537 pp. (2020)
[16] Liu, Yuzhen; Liang, Weifa, Approximate coverage in wireless sensor networks, (The IEEE conference on local computer networks, 2005. 30th Anniversary (2005), IEEE), 68-75
[17] Ralf Hartmut; Schneider, Markus, Moving objects databases (2005), Elsevier
[18] Sotskov, Yuri N.; Tanaev, Vyacheslav S.; Werner, Frank, Stability radius of an optimal schedule: A survey and recent developments, (Industrial applications of combinatorial optimization (1998), Springer), 72-108 · Zbl 0936.90030
[19] Tao, Yufei; Faloutsos, Christos; Papadias, Dimitris; Liu, Bin, Prediction and indexing of moving objects with unknown motion patterns, (Proceedings of the 2004 ACM SIGMOD international conference on management of data (2004)), 611-622
[20] Trajcevski, Goce, Uncertainty in spatial trajectories, (Computing with spatial trajectories (2011), Springer), 63-107
[21] Trajcevski, Goce; Wolfson, Ouri; Hinrichs, Klaus; Chamberlain, Sam, Managing uncertainty in moving objects databases, ACM Transactions on Database Systems (TODS), 29, 3, 463-507 (2004)
[22] Yick, Jennifer; Mukherjee, Biswanath; Ghosal, Dipak, Wireless sensor network survey, Computer Networks, 52, 12, 2292-2330 (2008)
[23] Yu, Qian; Medioni, Gérard; Cohen, Isaac, Multiple target tracking using spatio-temporal markov chain monte carlo data association, (2007 IEEE conference on computer vision and pattern recognition (2007), IEEE), 1-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.