{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:39Z","timestamp":1750308819431,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,8,1]],"date-time":"2011-08-01T00:00:00Z","timestamp":1312156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2011,8]]},"abstract":"<jats:p>\n            Let consider a set of anonymous moving objects to be tracked in a binary sensor network. This article studies the problem of associating deterministically a track revealed by the sensor network with the trajectory of an unique anonymous object, namely the\n            <jats:italic>multiple object tracking and identification<\/jats:italic>\n            (MOTI) problem. In our model, the network is represented by a sparse connected graph where each vertex represents a binary sensor and there is an edge between two sensors if an object can pass from one sensed region to another one without activating any other sensor. The difficulty of MOTI lies in the fact that the trajectories of two or more objects can be so close that the corresponding tracks on the sensor network can no longer be distinguished (track merging), thus confusing the deterministic association between an object trajectory and a track.\n          <\/jats:p>\n          <jats:p>The article presents several results. We first show that MOTI cannot be solved on a general graph of ideal binary sensors even by an omniscient external observer if all the objects can freely move on the graph. Then we describe restrictions that can be imposed a priori either on the graph, on the object movements, or on both, to make the MOTI problem always solvable. In the absence of an omniscient observer, we show how our results can lead to the definition of distributed algorithms that are able to detect when the system is in a state where MOTI becomes unsolvable.<\/jats:p>","DOI":"10.1145\/1993042.1993050","type":"journal-article","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:30:18Z","timestamp":1314711018000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Analysis of Deterministic Tracking of Multiple Objects Using a Binary Sensor Network"],"prefix":"10.1145","volume":"8","author":[{"given":"Yann","family":"Busnel","sequence":"first","affiliation":[{"name":"LINA\/Universit\u00e9 de Nantes"}]},{"given":"Leonardo","family":"Querzoni","sequence":"additional","affiliation":[{"name":"MIDLAB\/Universit\u00e0 di Roma \u201cLa Sapienza\u201d"}]},{"given":"Roberto","family":"Baldoni","sequence":"additional","affiliation":[{"name":"MIDLAB\/Universit\u00e0 di Roma \u201cLa Sapienza\u201d"}]},{"given":"Marin","family":"Bertier","sequence":"additional","affiliation":[{"name":"IRISA\/INSA Rennes"}]},{"given":"Anne-Marie","family":"Kermarrec","sequence":"additional","affiliation":[{"name":"INRIA Rennes-Bretagne Atlantique"}]}],"member":"320","published-online":{"date-parts":[[2011,8]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/958491.958509"},{"volume-title":"Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensor). 32--44","author":"Aspnes J.","unstructured":"Aspnes , J. , Goldengerg , D. , and Yang , Y. R . 2004. On the computational complexity of sensor network localization . In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensor). 32--44 . Aspnes, J., Goldengerg, D., and Yang, Y. R. 2004. On the computational complexity of sensor network localization. In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensor). 32--44.","key":"e_1_2_1_2_1"},{"volume-title":"Proceedings of the 2nd International Conference on Computer Vision Theory and Applications (VISAPP). 549--556","author":"Bloisi D.","unstructured":"Bloisi , D. , Iocchi , L. , Leone , G. R. , Pigliacampo , R. , Tombolini , L. , and Novelli , L . 2007. A distributed vision system for boat traffic monitoring in the venice grand canal . In Proceedings of the 2nd International Conference on Computer Vision Theory and Applications (VISAPP). 549--556 . Bloisi, D., Iocchi, L., Leone, G. R., Pigliacampo, R., Tombolini, L., and Novelli, L. 2007. A distributed vision system for boat traffic monitoring in the venice grand canal. In Proceedings of the 2nd International Conference on Computer Vision Theory and Applications (VISAPP). 549--556.","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/978-3-540-69170-9_4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1362542.1362547"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/367766.368168"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/1023720.1023734"},{"volume-title":"Proceedings of the 4th IEEE Conference on Computer Vision and Pattern Recognition (CVPR). I--864--I--871","author":"Han M.","unstructured":"Han , M. , Xu , W. , Tao , H. , and Gong , Y . 2004. An algorithm for multiple object trajectory tracking . In Proceedings of the 4th IEEE Conference on Computer Vision and Pattern Recognition (CVPR). I--864--I--871 . Han, M., Xu, W., Tao, H., and Gong, Y. 2004. An algorithm for multiple object trajectory tracking. In Proceedings of the 4th IEEE Conference on Computer Vision and Pattern Recognition (CVPR). I--864--I--871.","key":"e_1_2_1_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/1498915.1498921"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1498915.1498924"},{"volume-title":"Proceedings of the 2nd ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN). 113--128","author":"Liu J.","unstructured":"Liu , J. , Liu , J. , Reich , J. , Cheung , P. , and Zhao , F . 2003. Distributed group management for track initiation and maintenance in target localization applications . In Proceedings of the 2nd ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN). 113--128 . Liu, J., Liu, J., Reich, J., Cheung, P., and Zhao, F. 2003. Distributed group management for track initiation and maintenance in target localization applications. In Proceedings of the 2nd ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN). 113--128.","key":"e_1_2_1_11_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/1644038.1644078"},{"volume-title":"Proceedings of the 4th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN). 195--202","author":"Oh S.","unstructured":"Oh , S. and Sastry , S . 2005. Tracking on a graph . In Proceedings of the 4th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN). 195--202 . Oh, S. and Sastry, S. 2005. Tracking on a graph. In Proceedings of the 4th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN). 195--202.","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1109\/TAC.1979.1102177"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/1614379.1614382"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1236360.1236427"},{"volume-title":"Proceedings of the IEEE Antennas and Propagation Society International Symposium (APSURSI). 1--4.","author":"Viani F.","unstructured":"Viani , F. , Martinelli , M. , Ioriatti , L. , Lizzi , L. , Oliveri , G. , Rocca , P. , and Massa , A . 2009. Real-time indoor localization and tracking of passive targets by means of wireless sensor networks . In Proceedings of the IEEE Antennas and Propagation Society International Symposium (APSURSI). 1--4. Viani, F., Martinelli, M., Ioriatti, L., Lizzi, L., Oliveri, G., Rocca, P., and Massa, A. 2009. Real-time indoor localization and tracking of passive targets by means of wireless sensor networks. In Proceedings of the IEEE Antennas and Propagation Society International Symposium (APSURSI). 1--4.","key":"e_1_2_1_17_1"},{"volume-title":"Proceedings of the 2nd Annual Conference of the International Technology Alliance. 307--308","author":"Wang Z.","unstructured":"Wang , Z. , Bulut , E. , and Szymanski , B. K . 2008. Distributed target tracking with imperfect binary sensor networks . In Proceedings of the 2nd Annual Conference of the International Technology Alliance. 307--308 . Wang, Z., Bulut, E., and Szymanski, B. K. 2008. Distributed target tracking with imperfect binary sensor networks. In Proceedings of the 2nd Annual Conference of the International Technology Alliance. 307--308.","key":"e_1_2_1_18_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/321105.321107"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993042.1993050","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993042.1993050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:39Z","timestamp":1750278399000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993042.1993050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["10.1145\/1993042.1993050"],"URL":"https:\/\/doi.org\/10.1145\/1993042.1993050","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2011,8]]},"assertion":[{"value":"2008-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}