Soeanu, Andrei, Ray, Sujoy, Berger, Jean and Debbabi, Mourad (2018) Efficient Sensor Network Management for Asset Localization. Computers & Operations Research . ISSN 03050548 (In Press)
Preview |
Text (In press, accepted manuscript) (application/pdf)
1MBsoeanu 2018.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Official URL: http://dx.doi.org/10.1016/j.cor.2018.06.001
Abstract
Asset localization represents an important application over wireless sensor networks (WSN) with a wide area of applicability ranging from network surveillance to search and rescue operations. In this paper, we address a research problem of network management where resource constrained sensors, in terms of capacity, sensing range and energy, are assigned to multiple targets in order to optimally localize assets with minimized error. We consider a heterogeneous network of omnidirectional sensors, each of which has an individual capacity to focus on a number of targets and a specific range to accurately estimate its distances to the targets that it is focusing on. A proper localization of each target requires a minimum of K (typically three) sensors where the target location is estimated using the intersection of the K range circles. We further analyze the problem under the constraint of a globally specified overall WSN energy budget which limits the possible assignments for the capacitated sensors. Restricting the energy budget leads to a trade-off between energy conservation and localization performance. In this context, we propose a heuristic solution approach leveraging evolutionary learning followed by meta-heuristic improvements based on target swapping among sensors. This approach actually minimizes a quantifier that is composed of the total localization area for all targets in addition to a penalty for each target if it is assigned less than minimum sensors. We provide an illustrative case study for the proposed approach and assess its effectiveness experimentally via benchmark results obtained on a data-set derived from known vehicle routing problem instances.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering |
|---|---|
| Item Type: | Article |
| Refereed: | Yes |
| Authors: | Soeanu, Andrei and Ray, Sujoy and Berger, Jean and Debbabi, Mourad |
| Journal or Publication: | Computers & Operations Research |
| Date: | 15 June 2018 |
| Digital Object Identifier (DOI): | 10.1016/j.cor.2018.06.001 |
| Keywords: | Asset Localization; Wireless Sensor Network; Multi-dimensional Assignment, |
| ID Code: | 983971 |
| Deposited By: | Monique Lane |
| Deposited On: | 26 Jun 2018 14:56 |
| Last Modified: | 16 Jun 2021 01:00 |
References:
Y.K. An, S.-M. Yoo, C. An, B.E. Wells Rule-based multiple-target tracking in acoustic wireless sensor networks Computer Communications, 51 (2014), pp. 81–94G. Arslan, J.R. Marden, J.S. Shamma Autonomous vehicle-target assignment: A game-theoretical formulation Journal of Dynamic Systems, Measurement, and Control, 129 (5) (2007), pp. 584–596
P. Augerat, J. Belenguer, E. Benavent, A. Corberan, D. Naddef, G. Rinaldi Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem Technical Report, Universite Joseph Fourier, Grenoble, France (1995)
D. Balakrishnan, A. Nayak An efficient approach for mobile asset tracking using contexts IEEE Transactions on Parallel and Distributed Systems, 23 (2) (2012), pp. 211–218
H.-J. Bandelt, A. Maas, F.C. Spieksma Local search heuristics for multi-index assignment problems with decomposable costs Journal of the Operational Research Society, 55 (7) (2004), pp. 694–704
L. Birnbaum, G. Collins, M. Freed, B. Krulwich Model-based diagnosis of planning failures. AAAI, 90 (1990), pp. 318–323
Bisio, A. Sciarrone, S. Zappatore A new asset tracking architecture integrating RFID, Bluetooth Low Energy tags and ad hoc smartphone applications Pervasive and Mobile Computing, 31 (2016), pp. 79–93
Boutaba, R., Achir, N., St-Hilaire, M., Nakamura, E. F., 2014. Planning and deployment of wireless sensor networks.
R. Burkard, M. Dell’Amico, S. Martello Assignment problems: revised reprint SIAM (2012)
R.E. Burkard, R. Rudolf, G.J. Woeginger Three-dimensional axial assignment problems with decomposable cost coefficients Discrete Applied Mathematics, 65 (1-3) (1996), pp. 123–139
W.-P. Chen, J.C. Hou, L. Sha Dynamic clustering for acoustic target tracking in wireless sensor networks IEEE transactions on mobile computing, 3 (3) (2004), pp. 258–271
J. Cortes, S. Martinez, T. Karatas, F. Bullo Coverage control for mobile sensing networks
IEEE Transactions on robotics and Automation, 20 (2) (2004), pp. 243–255
D. Goossens, S. Polyakovskiy, F.C. Spieksma, G.J. Woeginger The focus of attention problem Algorithmica, 74 (2) (2016), pp. 559–573
F. Gustafsson, F. Gunnarsson Localization in sensor networks based on log range observations Information Fusion, 2007 10th International Conference on, IEEE (2007), pp. 1–8
W.E. Hart, N. Krasnogor, J.E. Smith Memetic evolutionary algorithms Recent advances in memetic algorithms, Springer (2005), pp. 3–27
V. Isler, S. Khanna, J. Spletzer, C.J. Taylor Target tracking with distributed sensors: The focus of attention problem Computer Vision and Image Understanding, 100 (1) (2005), pp. 225–247
X. Jin, S. Sarkar, A. Ray, S. Gupta, T. Damarla Target detection and classification using seismic and pir sensors IEEE Sensors Journal, 12 (6) (2012), pp. 1709–1718
D. Karapetyan, G. Gutin A new approach to population sizing for memetic algorithms: a case study for the multidimensional assignment problem Evolutionary computation, 19 (3) (2011), pp. 345–371
Y. Kuroki, T. Matsui An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors Discrete Applied Mathematics, 157 (9) (2009), pp. 2124–2135
M. Larsen Branch and bound solution of the multidimensional assignment problem formulation of data association Optimization Methods Software, 27 (6) (2012), pp. 1101–1126
S. Li A 1.488 approximation algorithm for the uncapacitated facility location problem
Information and Computation, 222 (2013), pp. 45–58
F. Librino, M. Levorato, M. Zorzi An algorithmic solution for computing circle intersection areas and its applications to wireless communications Wireless Communications and Mobile Computing, 14 (18) (2014), pp. 1672–1690
Murat, G. Laporte, V. Verter A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand Computers & Operations Research, 71 (Supplement C) (2016), pp. 1–15
E.F. Nakamura, A.A.F. Loureiro, A. Boukerche, A.Y. Zomaya Localized algorithms for information fusion in resource constrained networks Information Fusion (15) (2014), pp. 2–4
Oka, L. Lampe Distributed target tracking using signal strength measurements by a wireless sensor network IEEE Journal on Selected Areas in Communications, 28 (7) (2010), pp. 1006–1015
F.A. Özsoy, M. Ç. Pinar An exact algorithm for the capacitated vertex p-center problem
Computers & Operations Research, 33 (5) (2006), pp. 1420–1436
D.W. Pentico Assignment problems: A golden anniversary survey European Journal of Operational Research, 176 (2) (2007), pp. 774–793
W.P. Pierskalla Letter to the editor-the multidimensional assignment problem Operations Research, 16 (2) (1968), pp. 422–431
A.B. Poore, S. Gadaleta Some assignment problems arising from multiple target tracking Mathematical and computer modelling, 43 (9) (2006), pp. 1074–1091
S. Ray, M. Debbabi, M. Allouche, N. Léchevin, M. Bélanger Energy-efficient monitor deployment in collaborative distributed setting IEEE Transactions on Industrial Informatics, 12 (1) (2016), pp. 112–123
J. Salerno, M. Hinman, D. Boulware Building a framework for situation awareness
Technical Report, DTIC Document (2004)
V. Savic, S. Zazo Cooperative localization in mobile networks using nonparametric variants of belief propagation Ad hoc networks, 11 (1) (2013), pp. 138–150
Sobhani, M. Mazzotti, E. Paolini, A. Giorgetti, M. Chiani Multiple target detection and localization in uwb multistatic radars Ultra-WideBand (ICUWB), 2014 IEEE International Conference on, IEEE (2014), pp. 135–140
Soeanu, S. Ray, M. Debbabi, J. Berger, A. Boukhtouta A learning based evolutionary algorithm for distributed multi-depot vrp KES (2012), pp. 49–58
L.-K. Soh, C. Tsatsoulis Reflective negotiating agents for real-time multisensor target tracking International Joint Conference On Artificial Intelligence, 17, LAWRENCE ERLBAUM ASSOCIATES LTD (2001), pp. 1121–1127
E.L. Souza, A. Campos, E.F. Nakamura Tracking targets in quantized areas with wireless sensor networks Local Computer Networks (LCN), 2011 IEEE 36th Conference on, IEEE (2011), pp. 235–238
É.L. Souza, E.F. Nakamura, R.W. Pazzi Target tracking for sensor networks: A survey ACM Computing Surveys (CSUR), 49 (2) (2016), p. 30
P.P. Storms, F.C.R. Spieksma An lp-based algorithm for the data association problem in multitarget tracking Computers & Operations Research, 30 (7) (2003), pp. 1067–1085
Vogiatzis, E.L. Pasiliao, P.M. Pardalos Graph partitions for the multidimensional assignment problem Computational Optimization and Applications, 58 (1) (2014), pp. 205–224
S. Waharte, N. Trigoni Supporting search and rescue operations with UAVs Emerging Security Technologies (EST), 2010 International Conference on, IEEE (2010), pp. 142–147
J.L. Walteros, C. Vogiatzis, E.L. Pasiliao, P.M. Pardalos Integer programming models for the multidimensional assignment problem with star costs European Journal of Operational Research, 235 (3) (2014), pp. 553–568
P. Yang, W. Wu, M. Moniri, C. Chibelushi Efficient object localization using sparsely distributed passive RFID tags IEEE Transactions on Industrial Electronics, 60 (12) (2013), pp. 5914–5924
Y.Z. Zhao, O.P. Gan Distributed design of RFID network for large-scale RFID deployment
2006 IEEE International Conference on Industrial Informatics. Singapore (2006), pp. 44–49
Repository Staff Only: item control page
Download Statistics
Download Statistics