Poster Abstract:Cooperative Tracking with Binary-Detection Sensor Networks
Kirill Mechitov mechitov@cs.uiuc.edu
Sameer Sundresh sundresh@cs.uiuc.edu
Y oungmin Kwon ykwon4@cs.uiuc.edu
Gul Agha agha@cs.uiuc.edu
Department of Computer Science University of Illinois at Urbana-Champaign Urbana,IL61801,USA
ABSTRACTcooperative
We present a novel method for tracking the movement of people or vehicles in open outdoor environments using sen-sor networks.Unlike other sensor network-based methods, which depend on determining distance to the target or the angle of arrival of the signal,our cooperative tracking ap-proach requires only that a sensor be able to determine if an object is somewhere within the maximum detection range of the sensor.We propose cooperative tracking as a method for tracking moving objects and extrapolating their paths in the short term.By combining data from neighboring sensors, thi
s approach enables tracking with a resolution higher than that of the individual sensors being used.We employ sta-tistical estimation and approximation techniques to further increase the tracking precision,and to enable the system to exploit the tradeoffbetween accuracy and timeliness of the results.We analyze the behavior of the cooperative tracking algorithm through simulation,focusing on the effects of ap-proximation techniques on the quality of estimates achieved. This work focuses on acoustic tracking,however the pre-sented methodology is applicable to any sensing modality where the sensing range is relatively uniform.
Categories and Subject Descriptors
J.m[Computer Applications]:Miscellaneous
General Terms
Algorithms,Performance,Experimentation
Keywords
target tracking,cooperative tracking,sensor networks
1.INTRODUCTION
Sensor networks are built from small,inexpensive devices that provide modest computational capabilities and short-range sensing.The sensors used by these devices account for a substantial portion of their cost,an important metric Copyright is held by the author/owner.
SenSys’03,November5–7,2003,Los Angeles,California,USA..
ACM1-58113-707-9/03/0011.for very large scale sensor networks.Thus it is important to explore the capabilities of sensor networks that provide only the most basic sensing.Such simple sensors have only the ability to detect whether a signal is present within somefixed range of the sensor,providing only single-bit detection result and no additional information.We call such systems binary-detection sensor networks and study the tracking problem in this setting.
Several target tracking algorithms have been proposed for sensor networks where sensors provide distance or angle of arrival [3].Such techniques are inappli-cable in binary-detection sensor networks.While proxim-ity sensors used in these networks do not encounter the types of measurement errors typically present with angle of arrival,distance and signal strength-measuring sensors, the resolution of signal location from these sensors is sig-nificantly lower.Cooperative tracking allows us to improve the precision of tracking by exchanging information among neighboring
sensors to refine the target location estimates. We present a two-level cooperative tracking algorithm that provides tracking precision better than can be achieved by simple averaging of the sensor readings to estimate the tar-get position.
Our simulation studies show that a high degree of preci-sion and scalability is achieved by the algorithm.We val-idate these simulation results with a small-scale prototype implementation of a binary-detection acoustic tracking sys-tem that uses the cooperative tracking approach.
2.COOPERATIVE TRACKING
In cooperative tracking,each sensor detects the presence of the target in their vicinity,and this information is shared among nearby nodes to improve the accuracy of the target location estimate.We introduce a novel two-phase approach to this problem.First,local target position estimates are computed.These estimates are then aggregated and used to compute the path of the object,which produces a more precise estimator for the target location.
In thefirst phase,sensor nodes exchange the times when the target signal is detected and the duration of detection and compute a location estimate for each time point.Ini-tially,it is set to be equal to the location of the sensor. As information from other sensors becomes available,the
position estimate is recomputed as a weighted average of the sensor locations,using the inverse of the estimated per-pendicular distance from the sensor to the target’s path as the weight.The weight for node i is assigned according to Equation1,where R is the maximum detection radius,v is the estimate of the target’s speed,t i is the duration for which the target has been detected by i,and f is the sensor sampling frequency.The weights are then normalized and thefinal location estimate is computed.Due to this weight-ing scheme,sensors that lie closer to the path of the target receive more weight.
w i=1
R2−0.25v2∗(t i−f−1)2
(1)
In the second phase of the algorithm,we compute a piece-wise linear approximation of the path using a line-fitting algorithm on the position estimates obtained in thefirst phase.Since this computation exploits the spatial and tem-poral separation of the detected signals,the target loca-tion derived from the path estimate is actually more precise than the original target position estimates used to compute the path itself.We thus achieve tracking with a resolution higher than that of the individual sensors in
the network. The network continuously aggregates the position esti-mates provided by the sensors,which are used to update and refine the path estimate.By adjusting the number of position estimates used for the computation of each line seg-ment,our algorithm can exploit the tradeoffbetween time-liness and precision of the results to satisfy the needs of the application.The timeliness metric is particularly important for“convergence”applications,where sensing is coupled to real-time control[1].Since the number of position estimates can be adjusted dynamically at run time,early rough esti-mates of the path can be computed for time-critical tasks and then refined later on.
3.RESULTS
We studied the performance of the cooperative tracking algorithm through simulation.The following model is used to represent the sensor network and the tracked object. The object moves through the sensor network at a con-stant speed of1R/s,where R is the nominal maximum de-tection range of the sensors.The actual sensor range varies from0.8R to1.2R according to a uniform distribution.The separation between sensor nodes in the network is1R.Since we express the main parameters,object’s speed and sensor density,in terms of the sensor radius R,the results can be generalized to tracking objects traveling at different speeds by changing the density accordingly.
The two-level tracking approach has relatively high target location error,near1R,when the object isfirst detected or changes course drastically.However the location error falls to below0.2R of the sensing radius within4seconds of initial detection.This increase in precision can be attributed to the refinement of the path and position estimates by the second phase of the algorithm as more spatially-distributed position estimates are gathered.
Prior research indicates that for many sensor network applications,performance is not substantially degraded by node localization error within0.2of node separation dis-tance[2].Our cooperative tracking algorithm provides com-parable precision for the location of the target,thus it can be used under similar conditions.Statistical estimation tech-niques can be employed to further improve the tracking pre-cision.
There is a linear relationship between target movement speed and accuracy.The desired balance between accuracy and timeliness of the results can be achieved by setting the size of position estimate history kept by the sensors,given the sensor density and target speed as parameters.It can also be adjusted dynamically using feedback control.
To validate the simulation results,we created a prototype acoustic tracking system using binary-detec
tion cooperative tracking.The sensor network is composed of16Berkeley motes with standard sensor boards that include a micro-phone.The microphone is used to detect a unique acoustic signature emitted by the tracked object.The average de-tection range of the microphones is scaled down to approx-imately0.5meters,which is the node separation distance in the experiment.The performance of this small-scale ex-perimental system is largely consistent with simulation re-sults.This provides experimental validation of the simu-lation methodology,while simulations of up to1000nodes demonstrate the scalability of the approach.
4.CONCLUSION
Our cooperative tracking algorithm uses only the simplest possible sensors,however it achieves a high degree of pre-cision.The tracking precision is comparable to cooperative tracking approaches that rely on distance or angle of arrival measurements from the sensors.The key to achieving such performance is using the approximation of the path,com-puted cooperatively by the sensors,to refine the position estimates of individual sensors.This result enables sensor network-based tracking with binary-detection sensors,which are much simpler and thus cheaper than distance-measuring sensors or sensor arrays used for determining the angle of ar-rival.
An in-depth discussion of the binary-detection coopera-tive tracking approach,including simulation and experimen-tal results and analysis,is presented in[4].
5.REFERENCES
[1]S.Graham and P.R.Kumar.The convergence of
control,communication,and computation.In
Proceedings of PWC2003:Personal Wireless
Communication,September2003.
[2]T.He,C.Huang,B.Blum,J.A.Stankovic,and
T.Abdelzaher.Range-free localization schemes in large scale sensor networks.In Range-Free Localization
Schemes in Large Scale Sensor Networks,September
2003.
[3]J.Liu,J.Reich,and F.Zhao.Collaborative In-Network
Processing for Target Tracking.EURASIP Journal of Applied Signal Processing,2003(4):378–391,2003. [4]K.Mechitov,S.Sundresh,Y.Kwon,and G.Agha.
Cooperative tracking with binary-detection sensor
networks.Technical Report UIUCDCS-R-2003-2379,
University of Illinois at Urbana-Champaign,September 2003.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。