DocumentCode :
167390
Title :
Near-Optimal Location Tracking Using Sensor Networks
Author :
Sharma, G. ; Krishnan, H. ; Busch, C. ; Brandt, S.R.
Author_Institution :
Sch. of Electr. Eng. & Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA
fYear :
2014
fDate :
19-23 May 2014
Firstpage :
737
Lastpage :
746
Abstract :
We consider the problem of tracking mobile objects using a sensor network. We present a distributed tracking algorithm, called Mobile Object Tracking using Sensors MOT, that scales well with the number of sensors and also with the number of mobile objects. MOT maintains a hierarchical structure of detection lists that can efficiently track mobile objects and resolve object queries at any time. MOT guarantees that the cost to update its data structures will be at most O(min{log n, log D}) times the optimal update cost and query cost will be within O(1) of the optimal query cost in the constant-doubling graph model, where n and D, respectively, are the number of nodes and the diameter of the network. Moreover, MOT achieves polylogarithmic approximations for both costs in the general graph model and performs well in practical scenarios. To our best knowledge, MOT is the first algorithm for this problem in a distributed setting that is traffic-oblivious, i.e. agnostic to a priori knowledge of objects movement patterns, mobility and query rate, etc., and is load balanced.
Keywords :
computational complexity; graph theory; object tracking; MOT; constant-doubling graph model; data structures; distributed tracking algorithm; hierarchical structure; mobile object tracking; near-optimal location tracking; optimal update cost; polylogarithmic approximations; query cost; Approximation algorithms; Image edge detection; Maintenance engineering; Mobile communication; Mobile computing; Object tracking; Competitive ratio; Hierarchical structure; Location Tracking; Mobile objects; Sensor networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel & Distributed Processing Symposium Workshops (IPDPSW), 2014 IEEE International
Conference_Location :
Phoenix, AZ
Print_ISBN :
978-1-4799-4117-9
Type :
conf
DOI :
10.1109/IPDPSW.2014.85
Filename :
6969455
Link To Document :
بازگشت