BU CS 580S - A Survey of Target Tracking Algorithms for Sensor Networks

Unformatted text preview:

A Survey of Target Tracking Algorithms for Sensor NetworksKelly R. MeredithUniversity of [email protected] a target as it moves through a sensor network has become an increasingly important application for sensor networks. This paper examines some of the target tracking algorithms in use today. An overview of each algorithm type is presented along with an analysis of i’s problems, benefits and possible improvements. Key design characteristics and a list of poor design assumptions to make in the design of a tracking algorithm are also presented as a result of the survey of these algorithms.1.0 IntroductionAs the development of sensor networks has become more advanced the realm of application possibilities for their use has increased. One such emerging application area is using sensor networks to perform intelligent surveillance or monitoring of an area [1]. Since sensor nodes are all ready being deployed to monitor and capture data in certain areas, it is only natural that their use be expanded to includetracking objects in addition to detecting and classifying them. The purpose of this paper is to introduce, summarize and compare some of the target tracking algorithms currently used in sensor networks. Although detection and classification algorithms are equally interesting, they are not covered in this paper and the reader is referred toreference [2] for detection algorithms and [3] for classification algorithms.2.0 BackgroundTarget tracking algorithms usually focus on the aspect of the sensor nodes’ interaction with a target after the target has all ready been detected within the area the sensor nodes cover. Once the object has been detected, the nodes collect information and then use one of many different types of algorithms to calculate the current location of the object relative to the sensor nodes’ locations. From here it is the goal of the sensor network to track the object as it moves through the network. This may or may not involve predicting the next location the object will move to in order to forewarn those nodes it will be heading towards to prepare to capture data [1].The application possibilities for target tracking techniques using a sensor network of sensor nodes is only limited by the imagination of the network designer. Sensor networks are currentlybeing used in the field of tracking for surveillance, search and rescue, disaster response, evasion games, spatial-temporal data collection and many other localization based applications [4].2.0 Tracking AlgorithmsWhile researching this topic it became apparent that they are too many types of tracking algorithms to mention and analyze within the scope of one paper. To keep this paper manageable, this paper is limited to discussing those tracking algorithms that are most commonly used at this point in time.2.1 Simple TriangulationThis algorithm is presented in that it has an extremely simple design and implementation andserves as an ideal algorithm to use as the foundation for explaining other more complex tracking algorithms.As stated above, the whole goal of this algorithmas presented by Samir R. Das in [1] is to provide a simple algorithm that uses simple computation in order to detect an object, calculate its current location, predict where it is headed and notify those nodes near the predicted next location of the object [1]. This algorithm first assumes that all nodes in the network are localized to a common reference point and can detect and estimate the distance to a target using signal strength [1]. When a node detects an object within its range it broadcasts a TargetDetected message [1]. This messagecontains the location of the sensor node and the distance to the target [1]. All nodes that hear thismessage store its data in their local memory. When a node that has detected the target hears two other TargetDetected messages from two other nodes it performs triangulation on the threecoordinates to calculate the location of the target [1]. (Note that this means that more than one node may perform this calculation for the same target at the same time.) This node then continues on to project the trajectory of the target. When the estimated target trajectory has been calculated, all nodes that are within some distance d perpendicular to the target’s trajectory are sent a Warning message to alert them that thetarget is headed towards them [1]. These newly awoken nodes then track the object as it enters their area and repeat the TargetDetected and Warning message sending process [1].3.2 ClustersThe cluster target tracking algorithm was widely discussed through many research papers. The basic idea of target tracking using clusters is discussed, followed by an overview of the variances in each of the different cluster algorithm research papers.3.2.1 Basic Cluster AlgorithmThe basic algorithm for tracking an object using clusters is as follows:- Some (or all) of the nodes in a cluster detect the object and report their data to a cluster head. Note that a cluster only has one cluster head node [5].- The cluster head node then uses all the target detection information from the sensor nodes to estimate the target’s location [5].- The cluster head then uses the calculated target location and past locations of the target to predict the nextlocation of the target [5].- Those sensors around the predicted location are then woken up to form a new cluster (if not already in one) to detect the target [5].- When the target is detected in this new cluster, the previous cluster’s nodes are all put into a sleep state. This new cluster then continues the cluster tracking algorithm [5].3.2.2 Hierarchical Supernodes This algorithm deviates from the basic algorithm in that the cluster heads (called supernodes) havea higher communication range and more computational power [6]. These “supernodes” are distributed throughout the network and the otherwise normal nodes are assigned to supernodes. Clusters are not dynamically generated in this algorithm. Interestingly enough, supernodes do share target location information among each other, whereas regular sensor nodes do not.3.2.3 Dynamic ClusteringLike the supernode algorithm implementation this algorithm also assumes that cluster head nodes have more power than normal sensor nodes. However, sensor nodes are not assigned to clusters in this algorithm. Instead, they are invited to join a cluster by the cluster head.


View Full Document

BU CS 580S - A Survey of Target Tracking Algorithms for Sensor Networks

Download A Survey of Target Tracking Algorithms for Sensor Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A Survey of Target Tracking Algorithms for Sensor Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Survey of Target Tracking Algorithms for Sensor Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?