Energy-efficient Multiple Targets Tracking in Wireless Sensor Networks using Minimal Contours
1.0Introduction
A Low Cost Localization Scheme in a Mobile Sensor Network
Sensor network has been one of the newer and highly active research areas of Computer Science and Telecommunications. Originally motivated by military applications, such as battlefield surveillance and intelligence data acquisition, the use of sensor network has covered many civilian and industrial application areas now-a-days. However, regardless of its diversified applications, the primary tasks of sensor networks remain the same. These include target detection, classification, localization, data acquisition, tracking and transmission of data over multi-hop networks. Tracking of moving targets is an essential capability required in many practical applications of sensor network. In tracking applications, sensors actively probe for occurrence of phenomena that is, in most cases, intrusion of target entities into the coverage region of the sensor network. Once such activity is detected, the sensors locally gather information to determine the target’s spatial location. The information is conveyed to some remote stations where data arrives from all active sensors. The collected information over a particular time frame is fused together to obtain the global information regarding the location of the target.
Target tracking, being a well studied research problem, has been expressed and solved by many from different perspectives from time to time. However, the performance of a tracking method largely depends on the application of the sensor network. Since different applications consist of different set of target entities, sensing models and environmental models; target tracking models are driven by specific goals and scenarios. Amidst different desirable qualities and performance goals of a sensor network, energy awareness is one of the key research challenges for sensor network protocol design. Almost all of the sensing and routing devices of sensor networks are equipped with limited power sources. Therefore, tracking of targets must be performed with energy conserving strategies in order to obtain the optimal performance and life-time of sensor network.
1.1 Multiple Targets Tracking
The multiple-target tracking problem deals with the correct and simultaneous tracking of several targets in a sensor network. Compared to the tracking of a single target, tracking multiple targets is significantly more sophisticated and challenging because of difficulties in data association and identity management of targets. In this thesis, we study and find the solutions of energy-efficient multiple targets tracking in large scale sensor networks; the type of sensor network typically used for border surveillance. Border surveillance systems are required to monitor and detect different and possibly concurrent phenomena like trespassing, smuggling, human trafficking as well as enemy movements in warlike situations. Since these phenomena often involve moving and interaction of more than one target entity present in the sensing region independently or in groups; multiple targets tracking is an essentially required feature in such applications. We consider tracking all possible target entities including battlefield entities (human, tracked, wheeled vehicles). In scenarios like the one stated above, the task of target tracking is heavily dependent on proper detection and classification of targets. Therefore, we also propose algorithms for target detection and define appropriate features and classifiers for classification of targets.
1.2 Outline of the Thesis
We look to achieve an energy-efficient multiple target tracking algorithm by using cluster based sensor activation strategy. We do so by adopting a minimal contour based target tracking algorithm which previously, was modelled by Tian He et al. [11] to track only a single target at a time. The tracking method described in [11] is based on simple assumptions and therefore, it is unable to emulate the complex scenarios arisen while tracking multiple targets in a realistic environment. In this method, the sensing region of each individual target in restricted to a contour of interest, on the basis of its kinematics. To incorporate the support of different types of target entities in a sensor network, we introduce classification of target entities according to their sensing signatures. The use of target classification enables us to restrict the sensing region for targets according to the class they belong to. In addition, we are the first to introduce the concept of overlapping of the contours of interest which could take place while tracking multiple targets simultaneously. In such cases, we devise appropriate heuristics to ensure the correct association of sensing data with target contours. To perform such operations, a cluster based distributed tracking method is preferable to centralized tracking. Also, due to realistic considerations, the formation of clusters in the sensor network needs to be done dynamically for which, we propose using Voronoi cells to form the bounded region of the sensor network dynamically. We also discuss various target detection strategies and their viability in the scope of our problem.
The rest of the thesis is organized as follows. In Chapter 2, we discuss the related research work in the field of target tracking in sensor networks. Then in Chapter 3, we discuss the preliminaries and issues related to the problem domain. In Chapter 4, we describe the problem domain in details. In the same chapter, we give the solution also. In the next chapter, we report the experimental results and empirical analysis in the form of tables and graphs. Finally, Chapter 6 concludes the thesis with a summary discussion and proposals for future developments.
Related Works
In this chapter, we study some of the major research works related to target tracking, especially multiple targets tracking in wireless sensor networks. To do so, we classify the existing tracking methods in some broad classes and discuss the advantages, disadvantages and trade-offs present in those classes.
The problem of tracking targets using sensor networks has received attention from various perspectives. Based on the network architecture over which the algorithms are incorporated, these tracking algorithms can be classified into the following two broad categories:
- Centralized tracking
- Decentralized/Distributed tracking
2.1 Centralized Tracking
The simplest approach to track targets is to task each sensor to transmit their sensing information towards a processing node where a central processor fuses the report collected by all other sensing nodes; then performs long distance transmissions towards the base station. Therefore, the workloads of sensor tasking and data gathering concentrate to a single point in the network. While this approach is more invulnerable to noises and erroneous reports, it has numerous drawbacks. Sending time series data through the network introduces latency and synchronization issues. It also consumes energy and network bandwidth, while potentially introducing a single point of failure. It becomes ambiguous when sensors have overlapping ranges, disagree, or when multiple targets are present. Yaakov Bar-Shalom et al. [2] discussed such centralized tracking scheme along with a centralized data association method for sensors.
Figure 2.1 : Centralized tracking approach
2.2 Distributed Tracking
In a distributed network, no central processor is required as the member nodes gather sensing information directly by sensing as well as by gathering sensing information from its neighbouring nodes. That is, target tracking is achieved through collaboration of active sensors located near the target. Since there is no central entity to coordinate the tracking process; the operations of the sensor network are decided using locally gathered information or in many cases, using partially aggregated data of a set of collaborating sensors which of often called a ‘cluster’. In a tracking application, only a set of sensors near the target remain active at a time and it is their job to choose which other sensors on the network need to be activated for proper tracking of targets and which of the active ones need to be deactivated or put asleep when not in use. Because of the use of local information, distributed systems may temporarily result ambiguous or inconsistent information in different parts of the network. However, distributive approaches provide much more flexibility for the number and orientation of sensors which provides scalability to the network. In most of the sensor network applications scalability remains an essential requirement. Therefore, distributive algorithms are of better match for tracking applications than the centralized ones and most of the recent research works have been focused on the development of distributed tracking algorithms. These algorithms can be further categorized as follows:
i) Tree based approach
ii) Prediction based approach
iii) Cluster based approach
2.2.1 Tree based Approach
In [27], the authors provided a tree based target tracking algorithm named DCTC; where the sensors taking part in tracking targets form a tree structure called a ‘convoy tree’. As the target moves along its trajectory, the tree is continually reconfigured by adding some nodes along the predicted path and pruning the ones not required any more. Compared to a completely distributed algorithm, DCTC needs less redundant calculations and thus it is more energy-efficient. On the other hand the construction of the convoy tree puts an additional computational overhead over the sensor nodes that makes it difficult to implement. The DAT algorithm provided in [14] uses tree structures to facilitate in network processing while in [12], tree structure is used to employ hierarchy based data propagation in the sensor network.
(a) (b)
|
2.2.2 Prediction based Approach
In Prediction algorithms, a sensor can predict the future movement of moving object using control sensor’s state (i.e. active mode, sleep mode etc.). Like the tracking process itself, prediction based algorithms provide methods for monitoring targets as well as for reporting, For monitoring, various number of prediction models have been used. Some use Hierarchical Markov models [8, 25] or Kalman filters [5], while [24] used a linear prediction model that performs prediction based on the previous two observations. Similarly, higher order predictions (using up to n-1 observations to perform the nth prediction) are also possible. In [8], the active sensor nodes transfer their sensing data to their cluster head. The cluster head uses the data from its member nodes to predict the object movement. When the object moves out of a sensor node’s sensing area, the sensor sends the object movement information to the cluster head for further prediction computation. And the cluster sends the latest prediction data to the next sensor node that the target approaches. Like most other distributed algorithms, it exploits the use of local, short range data transmission while only the cluster heads communicate in long range. In [24], a similar cluster based reporting algorithm was proposed. However, for tracking, they relied on predictive approaches; as stated previously.
|
2.2.3 Cluster based approach
Cluster based target tracking is one of the more widely used tracking approaches in recent works. In this approach, a set or ‘cluster’ of sensors are dynamically activated/deactivated at a time. Each cluster consists of a number of active working nodes along with a designated sensor node which is often referred to as cluster head (CH). All the members in a cluster take part in target monitoring while the designated one aggregates and summarizes the data and transmits towards the sink. As a result, the cluster head dissipates more power than other nodes and therefore is expected to have a shorter lifetime if all sensors are assumed to have the same amount of initial energy.
|
LEACH[10] is one of famous cluster-based routing protocols in wireless sensor network. In LEACH, cluster head is elected randomly and periodically. Therefore, energy consumption is distributed evenly. However, because cluster head is randomly elected, LEACH is not fit for moving object tracking scenario. A more efficient approach is to elect the cluster head according to the energy profiles of the members of a cluster. This again, comes with an extra information exchange overhead which is acceptable comparing to the expected benefit of increased system lifetime. [4] incorporates an event-triggered dynamic cluster head election where the head is selected automatically by the detection event itself. This requires a heterogeneous sensor network where cluster heads have more computational power and more battery capacity than others. This also results a scalable hierarchical architecture which makes a good candidate for large scale sensor networks. However [4] emphasized on the details of the network architecture rather than the tracking algorithm itself. This leaves room for further improvement in accuracy and energy efficiency for tracking in heterogeneous hierarchical sensor networks.
Preliminary Issues
A wireless sensor network is a system of small, wirelessly communicating nodes in which each node is equipped with multiple components. In particular, each node has a computation engine; communication and storage subsystems; a battery supply; and sensing and, in some cases, actuating devices. Such a network is envisioned to integrate the physical world with the Internet and computations. The power supply on each node is relatively limited, and frequent replacement of the batteries is often not practical because of the large number of nodes in the network. Therefore, energy is the most constraining factor on the functionality of these networks. In order to save energy, nodes use multi-hop short-range communications, which have been proven to consume much less energy than a single-hop long-range communication of the same distrance[28]. The sensor nodes form an ad-hoc network where each node, in addition to transmitting or receiving its own data; also forwards data originated from other nodes towards the destination. Therefore, long range data transmission between two nodes or between a node and the base station can be done in multiple hops, instead of using the more expensive single hop long range transmissions.
3.1 Foundational Aspects of Sensor Network
Efficient and fault-tolerant network architectures play a very important role in successful implementations of sensor networks. Apart from the timeliness and complexity of information transmission, interconnection topology has a significant impact on the computational aspects of data routing and sensor deployment schemes discussed in later sections. Therefore, the overall performance of a sensor network is critically dependent on its network architecture.
3.1.1 Sensor Characteristics
A sensor network can consist of either homogenous or heterogeneous entities. In a homogenous sensor networks, all the consisting sensor nodes have the same sensing modalities and range although they might have different role of operation, depending on the architecture and Application services used. On the other hand, a heterogeneous sensor network may consist of a mixture of motes with different models, battery power, sensing modality and sensing and transmission range. In mobile agent based sensor networks, some or all of the entities could also have mobility features providing capacity to move throughout the sensor network region. Such features are useful in evader-pursuer type applications; while ill suited for other applications due to the size, energy consumption and expense of the nodes.
3.1.2 Communication Model
The communication model of a sensor network is different from the traditional client-server model. Sensor networks are more like distributed systems where the communication flow is omnidirected and evenly distributed. As stated previously, most of the communications that take place in a sensor network are of short range; which are used to share local information among the sensors. Therefore, sensor networks require different, specialized MAC layer protocols to incorporate effective communication. Standard CSMA based protocols suffer from hidden station problem as well as from high collision rates for which new variants such as S-MAC,B-MAC etc are proposed[17].
3.1.3 Energy Model
Energymodels, as well as battery models are required to predict the lifetime of a sensor network and compare the quality of different algorithms and protocols. As stated earlier a node performs various kinds of operation such as computation, sensing, data transmission and receiving etc. All of these actions dissipate energy at different rates. While power dissipation rate for sensing, computation as well as being idle are specific and subject to the model of sensor nodes models; the transmission power is proportional to the range of communication . That is:
For a sensor whose subunits can be turns on or off independently, the combination of such on/off states can be assigned as an energy state for the node. For a sensor network consisting of n sensors, each with m distinct states with per-state energy dissipation vector R[1:m] and per-state activity duration vector T[1:m], the total dissipated energy can be formulated as:
3.1.4 Data Integration Methods
In many applications, sensors are typically deployed in hazardous on harsh environments where the sensor operations and data communications are not as reliable as the communications are prone to various kinds noises. The other possible sources of unreliability are faulty sensor, false alarms, localization failure etc. Therefore, fault tolerance is an indispensable property of data integration algorithms. The measurements collected by sensors are usually processed into interval-valued estimates serving as the inputs of an overlap function, whose redundancy may be used to provide error tolerance.
Colouqueur et al. [6] introduced and compared two methods for fault tolerant data fusion, namely value fusion and decision fusion. In value fusion, the sensors in the network exchange their local data values and fuse them by finding the average. The final decision is made by comparing this final value to a threshold. On the other hand in decision fusion, the sensors in the network make a local decision by comparing their own measurement to a local threshold. Then they exchange their local decision and fuse them by averaging. The final decision is made by comparing this fused decision to another threshold.
3.2 Sensor Deployment
The sensor nodes of a sensor network are can be deployed both statically and dynamically. In applications like traffic surveillance or industrial monitoring, sensor nodes could be deployed in a fixed orientation. However, in many other applications such as battlefield surveillance, hazardous environment monitoring etc., fixed deployment is not possible. In that case sensor nodes are usually scattered or air-dropped over the region. Dynamic deployment requires the sensor nodes to ‘learn’ their overall or partial topology once they are deployed. Between the two methods of deployment, dynamic deployment provides more versatility and fault tolerance as deployment is much easier in this manner. In cases of air dropping of a large number of sensors, their deployment is considered to be spatially uniform in the network region.
3.3 Event detection
Even in a homogenous sensor network, different sensors may play different roles. The sensor nodes those are located near the boundary of the sensing region perform the additional task of event detection. Events could be of different types in different applications. For example an increase in industrial waste flow could be considered as an eventwhile in surveillance systems, intrusion of target entities into the sensing region is considered as an event. The performance goal in event detection is to find a distinct feature that can be sensed cheaply (energy-wise) and that can reliably detect a target.
3.4 Network Partitioning
As shown in [4], A hierarchically structured sensor network is composed of (a) a static backbone of sparsely placed high-capability sensors called cluster heads; and (b) moderately to densely populated low-end sensors whose function is to provide sensing information to their corresponding dynamically associated cluster heads upon requests. That is, a hierarchical sensor network is partitioned into a number of autonomous regions or cells where the low end sensors of each cell are tasked and controlled by its designated cluster head. By implementing such two level or possibly multiple level hierarchy, the transmission range for the low end sensors can be reduced significantly while the cluster heads perform the long range communication among the partitions. Again, as the low-end sensors outnumber the cluster heads, overall we obtain decrease of energy consumed in data transmission and receiving. By this way, cellular/hierarchical structures provide energy efficiency while maintain the distributive characteristics to a sensor network. The cells could be formed in predefined shapes such as squares and hexagons. Alternatively, dynamic clustering methods such as voronoi diagrams can be usedto provide scalability and support random sensor deployment in the sensor network.
(a)
|
(b)
Chapter 4
Problem Formulation
In this section, we present our methodology to ensure energy-efficient multiple target tracking in sensor networks used in a typical surveillance system. To do so, we describe the problem domain using practical assumptions and related definitions. Later we discuss algorithms and methods for tracking multiple targets as well as for target detection and classification.
4.1 Assumptions
We use the following assumptions on the sensor network to formulate the border surveillance problem:
§ A homogeneous sensor network, which implies a sensor network consisting of only a single kind of sensor, will be used to perform detection and tracking.
§ The network entities of interest are annotated in three categories :
o Computational Sensor Node (CN)
o Working Sensor Node (WN)
o Boundary Sensor Node (BN)
- All the sensors have a sensing range of a uniform disk with a radius of r, as all the sensors are of the same category [11].
- Communication radius is adjustable [11].
- CN has high computational power and it will perform the necessary calculations for detection, classification, tracking, evaluation of possible kinematics and waking or making the sensors of interest sleep.
Figure 4.1: An Illustrative Example of the Deployment Scenario
Furthermore, we assume the following propositions as attributes of the proposed system architecture:
§ Target can enter into the sensing field from any point on the boundary.
§ The tracking area is divided into cells. Each cell contains a CN which collects data from the WNs and the BNs associated to that specific CN. Deployment of the CNs in each individual cell is dynamic, the commonly deployment technique in surveillance applications. The cells, possessing non-uniform size, are created by these CNs dynamically using Voronoi diagram. We prefer the algorithm in [1], for implementing Voronoi diagrams, as it is harmonious to our assumptions and also has an auxiliary advantage of performing better than other algorithms given by Zhao et al. [29]. In [29], the provided algorithm uses only one sensor for calculating Voronoi diagrams.
§ The CNs, deployed all over the tracking field, is high powered nodes performing computation jobs.
§ WNs are deployed over the whole sensing area sparsely, possibly by air-dropping from aerial vehicle.
§ Each CN is capable to relay target information to the base station or to other computation nodes.
§ We assume all the distributions of transmitting and receiving signals between the nodes, used in this proposal to be Gaussian .Gaussian distributions have an important capability to work with second-order statistics and estimate mean vector and covariance matrices [3].
§ To detect the kinematic properties of the targets and transfer them to the corresponding CN, we consider the number of active WNs in a contour of interest to be six.
§ We consider, each cell, to consist at most four targets of any type tracked, wheeled or animal, in order to track the targets of interest properly, considering the kinematic properties followed in the problem formulation part.
4.2 Definitions
We define the following terms related to our work:
Definition A. Refresh Time
The longevity of the tracking area is defined as refresh time which also implies that the old tracking area is replaced with the new tracking according to the target’s movement every refresh time.
Definition B. Circle of Interest
Circle of Interest is the tracking area where the target can visit for its current position and speed during refresh time .The radius of the Circle of Interest is obtained by multiplying the target’s speed and refresh time.
Definition C. Contour of Interest
Contour of Interest is the tracking area where target can visit for its current position, speed and direction during refresh time. By applying vehicular kinematics and other practical assumptions, we can find the area portion of a Circle of Interest where the target is unlikely to visit. Omitting the unnecessary area from the Circle of Interest results the Contour of Interest for a particular refresh time.
Definition D. Overlapping Contour Region:
The common region covered by two or more overlapping contours of interest is defined as Overlapped Contour Region. This situation occurs when more than one targets come close to each other by such margin that the boundary area covered by contours of interest detecting and tracking the targets cross each other.
4.3 Elaboration of Our Approach
The main objective of our research will be looking for policies which will minimize the energy consumption of the sensors implying increased lifetime of the sensor network. Initially, the BNs wait for target appearance while all the other sensors remain asleep. The idea of deploying BNs is introduced to increase network longevity. He et al [11] were inclined to the idea of keeping all sensors awake and eventually directing all of them to sensing as well as tracking. We have already introduced the new concept of BN which is helpful for reducing power cost of the overall network as they are deployed only to perform the simple task of detecting the presence of a target. Low powered threshold based sensor nodes are expected to perform the job of detection sufficiently.
Unfortunately, an interesting issue arises when nearly all the nodes die, which is literally referred as single point of failure [3]. If all the BNs become dead near about the same time the target presence will not be detected and failure rate will increase. Two layer deployments of BNs can be an option where alternatively the two layer sensors will be awake and asleep, but unfortunately this strategy leads to increasing deployment cost. Therefore, a trade-off should be made in deploying BNs in a single or multiple layers. Focusing on the energy preserving issue we will stick to the one layer deployment scheme.
After detecting a target by any of the boundary sensors, corresponding detection information will be reported to the nearest CN. The CN will examine the received signal and provide relevant decision, using appropriate computations described in the next section in detail.
In accordance to our assumption we consider the incoming signal, x which has a mean µ1 when there is no external signal present, and µ2 when there the external signal is present. Since we have assumed the distributions are Gaussian having same variance but different means, the distribution incoming signal tends to,
p (x| ?i) ~ N(µi , ?2).
The dynamic detection algorithm illustrated by Colloquer et al. [6] will be the core concept to detect targets in case of our research effort.
In our research process there will be multiple biological and mechanical targets and so the contour of interest will differ with respect to target. In case of considering a biological target for a battlefield scenario, for example , a human entity or an animal, application of kinematics will not make any kind of improvements in pruning the contour of interest of the biological entities and also at the same time ensuring proper tracking .So relevant kinematics provide a Circle of Interest ,where the circle’s centre is defined by, p = (x , y) where x and y are co-ordinates in a two-dimensional coordinate system ,with a radius of r which we can express as r = vt where t = refresh time and
v = velocity of the target (human or animal). Let b = (v, ?) be the motion process of the human target. Here, v = target speed and ? = target’s direction in the corresponding two-dimensional co-ordinate system.
Four wheeled vehicles are used in a typical surveillance field for supply and surveillance. In this case we can prune out the most unlikely area that this type of target cannot visit. The formulation is specified according to Tian He et al. , that the tracking area will be a polygon of cone-shape, The four-wheeled target’s position will be expressed as, p = (x , y); where x is the X-coordinate and y is Y-coordinate and also the wheeled target’s motion can be expressed using the same particulars, b=(v , ?) .As mentioned before , v = target speed and ? = target’s direction in the corresponding two-dimensional co-ordinate system.
The position in a two-dimensional co-ordinate system of a tracked vehicle will be depicted in the same way as the human target and the wheeled vehicle. The motion process is, b = (v, ?) where as mentioned before, v = target speed and ? = target’s direction in the corresponding two-dimensional co-ordinate system .The direction of the tracked vehicle is related to its axis movement angle .The relationship is illustrated in the next section. The tracked target’s position will be expressed as, p = (x, y), where x is the X-coordinate and y is Y-coordinate.
4.3.1 Design Goals
We perform our modelling keeping the following objectives in mind:
§ Detecting true occurrence of target (single/multiple) entrance efficiently
§ Classifying the target or targets properly
§ Minimizing the overall sensor energy cost by efficient sleep-wake mechanism based on contour of interest by the CN.
§ Detecting the overlapping of contours of interest and taking appropriate decisions for ensuring first efficient target tracking then energy minimization.
The refresh time, will be needed in determining the Contour of Interest and also the Circle of Interest; smaller refresh time will lead to smaller Contour of Interest and also smaller Circle of Interest. This selection of an optimal refresh time will be dependent on communication and sensing cost; and not computation cost unlike Tian He et al. [11], as the WNs will not do the complex job of computation.
4.3.2 Target Detection and Classification
In this section we illustrate our attempts to detect and classify multiple targets and establishing them to fulfil achieve our objective with concreteness. We will start with the detection mechanism of multiple targets in the tracking field.
4.3.2.1 The Detection Algorithm:
Researchers have relied on threshold based strategies in detecting targets in different scenarios. Gu, Jia, Yan, He and others proposed auto-adaptive threshold based sensing strategies to detect events generating acoustic signature [22] .Others like Sayeed et al [3], also used techniques completely based on threshold. They exploit time series segment extracted from the time period when the event occurs.To ensure maximum fault tolerance we can follow the ‘decision value’ algorithm as found out by Colouqueur et al [6], they also show that ‘value fusion’ algorithm works well when the necessity of fault tolerance is low. Faults so happen during event detection in real time environment and improper dealing leads to disastrous results .So we will precede our work using the ‘decision fusion’ algorithm to minimize faults in event detection.
4.3.2.2 Illustration of the Classifier:
As we have stated before classifiers can be described as a set of discriminant functions. But these choosing a suitable discriminant functions is challenging. To ensure minimum error rate classification our effort will eventually will lead to a simple calculation and we start with the following form,
gi(x) = ln p( x |?i) + ln P (?i) (4.1)
Where,
x = feature vector of the observation,
?i Î { ?1, ? 2, ? 3,.., ? c} a finite set of c classes where c is a natural number .
P (?i) = a priory probability for the class ?i .
As previously mentioned, the Gaussian distribution is followed and hence the posterior probability, p(x | ?i) stands, for multivariate density in d dimensions,
p(x | ? i) = (4.2)
Now, in our case as the acoustic features do possess continuous univariate normal distribution , with a mean of µi and variance of ?2i ,for each class ?i .We assume the variances of all the classes will be same and thus ?2i = ?2 as the features will inherit acoustic information, from same quality of acoustic sensors having same attributes .
Thus our posterior probability density function becomes,
p(x | ?i) = (4.3)
Inserting this form in equation (4.1), we get,
gi(x) = ln [( ] + ln P (?i) (4.4)
It can be shown that, this form of equation will eventually reduce to a linear classifier and leads the classifier to,
gi(x) = (4.5)
Where, ,
And, = – + ln P(?i).
We can call wi0 the threshold or bias the ith category and term this classifier as a ‘linear machine’ which can solve the classification job at a linear cost.
Speed, velocity and position of target can be obtained by the target localization scheme proposed in [9], [13] and used in [11].The dynamic cell creation will be done by the distributed approach proposed in [1].To wake and sleep up the sensors we will use algorithms similar to Ray-Crossings [16] which is an efficient approach to find a point within the polygon. We will use our linear classifier to classify targets and assign a unique identity for them.
4.3.3 Illustrating the Multiple Targets Tracking Algorithm:
After performing target detection and classification as stated previously, CN initiates the tracking which controls the activation of WNs of that cell. The targets which we consider for tracking can be divided into three broad classes. One such class is wheeled vehicle. In border and battlefield surveillance systems, four- wheeled vehicles dominate the domain of wheeled vehicle and therefore, primarily 4 wheeled vehicles are taken into consideration. Other wheeled vehicles like 2 wheeled or three wheeled, can be modelled as four-wheeled ones, even though their presence in the tracking field is negligible.
4.3.3.1 Contour Tracking of Wheeled Vehicles:
Tian He, in his work [11], defined the vehicle motion on the basis of vehicular kinematics and proved that his modelling leads to a minimized shape of contour. He used the wheel base of the four wheeled vehicle and related the steering angle to the direction of rotation of the target vehicle. Tian He dignified the notion of the four wheeled vehicle as a random vector, having different states. At the beginning of tracking, there is an initial state and driving process that determines the vehicle motion. As its efficiency is proven, we follow the same approach. In this specific case of a four wheeled vehicle target, we model the vehicle motion by a random vector A = (X, Y, a, b, v, a) where (X, Y) is the position of the vehicle, a denotes direction, b is the steering angle, v is the velocity and a is the acceleration of the vehicle. The initial state can be defined as A0 =(X0, Y0, a0, b0, v0, a0). The process that determines the vehicle motion can be expressed as (b,a) where both a and b are Gaussian. Following the concept of He, we get the stochastic update equations as follows:
Xd+Dt= Xd+ d cos as dt (4.6)
Yd+Dt= Yd+ d sin as dt (4.7)
Then, d ß d + Dt
Here, d = the time already passed before the first detection.
Dt = refresh time
We also assume the driving processes (b,a) to be Gaussian, in accordance with He’s approach.
4.3.3.2 Contour Tracking of Tracked Vehicles:
The other class of targets we emphasize on this thesis is the tracked vehicle class. Tracked vehicles make up significant portions of target entities in battlefield scenarios. Compared to wheeled vehicles, they have a very different type of acoustic signature for which their presence and location can be distinguished from other entities. The two target classes also use different kinematic principles to manoeuvre. Track vehicles steer using the principle of ‘skid steering’ that is, applying different velocities to its two tracks to produce steering with the desired direction. And there is no ‘steering angle’ measure in such steering. Therefore, the modelling of kinematics behaviour of track vehicles needs a different approach than the one performed previously for the wheeled ones.
Kinematic Modelling of tracked vehicles was studied in a number of previous works such as [15], [20], [19]. In [19], the equation of motion of a tracked vehicle was formulated in terms of vehicle mass and the moment of inertia around the mass centre. It is evident that such modelling is not feasible in sensor networks since most of the parameters cannot be measured from typical distantly located sensors. J. L. Martínez et al. in [15], established a kinematic similarity between tracked and wheeled traction. He proposed using genetic algorithm on experimental data (in this case, sensed data) to identify optimized constant values of track parameters for a given condition. The problem with this approach is that the parameters require several iterations within a period of refresh time before they are optimized. Each iteration is expensive, both in terms of time and processing power. Therefore, the ‘experimental identification’ process fails to deliver sufficient energy-efficiency as well as real-time performance. In [20], the authors provided mathematical model for the entire skid steering system of 4 wheeled electric vehicles which is somewhat similar to our requirements. Therefore we use [20] as a reference along with other necessary formulations to model the tracking vehicle kinematics.
Figure 4.2: Kinematic Modelling Of a Tracked Vehicle
As mentioned before, the principle of tracked vehicle steering is referred as ‘skid steering’. The skid steering vehicle is turned by generating differential velocity at the opposite sides of the vehicle. This could be done in three different ways: braking/deceleration of the inner track, simultaneous speeding up the outer track and slowing down the inner track or by increasing velocity at the outer track. The motion of a tracked vehicle is dependent on a number of parameters such as mass, track acceleration, track velocity, normal force, moment of inertia about normal direction, slip ratios, track-soil friction coefficient as well as other frictional forces etc. Naturally, the complete modelling of tracked vehicle motion would be highly complex and therefore, computationally expensive. In its simplest form, the motion of tracked vehicle is modelled by a random vector A = (X, Y,q, v, vdiff) where (X, Y) is the position of the vehicle, q denotes its direction with reference to global coordinate axes, vis the velocity of vehicle and vdiff is the differential velocity between the tracks. The initial state can be defined as A0 = (X, Y, q, v0, 0); Let R be the instantaneous turning radius of the vehicle and f the displacement angle made by the vehicle about the instantaneous centre of radius during the interval of one refresh time, Dt. Also, let the distance between the left and the right track be denoted with d. When there is no steering involved, both tracks of the vehicles have the same velocity, that is, vdiff =0. At the moment skid steering is performed, outer track will have a greater velocity than that of the inner track to produce the same angular displacement around the instantaneous centre of radius. If the outer track velocity is increased by Dv, the following equations are obtained at the end of a refresh time:
For outer track: (v +Dv) Dt = (R +) f (4.8)
And, for inner track: v Dt = (R – ) f (4.9)
Solving equations (4.5) and (4.6) implies –
R = + (4.10)
And, f = (4.11)
Therefore, by varying the differential velocity Dv in the above equations, we can derive the corresponding turning radius and we can also measure the angular displacement along the steering path at any given time. The combination of such trajectories provides us the limit of region manoeuvrable by the vehicle at a given time and by sequentially connecting the end-points of those trajectories, our desired contour is formed.
After each refresh time, the modelling vector for the motion of the vector is updates with the followings:
qt+Dt= qt + f (4.12)
Xt+Dt= Xt + v cos(qt + f) (4.13)
Yt+Dt = Yt + v sin (qt + f) (4.14)
Figure 4.3: Paths Followed By a Tracked Vehicle
Therefore, at the end of every refresh time, the current contour of interest will be replaced by a new one using the updated parameters and the sensors those fall inside the contour, will be activated; putting any other active nodes into sleep mode.
4.3.3.3 Contour Based Tracking for Multiple Targets (CBTMT)
Let , ?ibe the ith CN ,acting as the head of cell ?i , in a surveillance field ?, where , ?i ? ? , the set of CNs in the surveillance field, ? and ?i? ? ,the set of cells formed in surveillance field , ?.
We are also assuming , ?ij as the jth WN for ith cell, ?i, in the surveillance field ? ; where ?ij ? ?i ,the set of the WNs in ith cell , ?i and true for all i=1..n in ? .
Also, let k be the total number of contours of interest present in the ith cell, ?i, at time t.
Here, n is the total number of active cells in the surveillance field ?, as the number of active cells will be as same as the number of computational nodes in the surveillance field ?.
Let, ?tpbe the corresponding contour of target p at any time t, in surveillance field ? along with µtp, the corresponding area covered by contour ?tpat time t.
_____________________________________________________________________
Algorithm 1: Contour_Based_Tracking_for_Multiple_Targets (surveillance_info)
______________________________________________________________________
1: for each computational node, ?i in ?
2: ?i =know self cell (?i)
{This module will partition the whole surveillance field into n active cells dynamically}
3: performDetectionJob(detection signal from BNs);
{Will differentiate between a false alarm and a real target appearance.}
4 classificationJob (detection features from BNs);
{Using the proposed linear machine the classifier will classify the targets present in the cell ?i }
5: ?i =know the WNs in the cell (?i);
6: getKinamaticsInfo(?i)
{Speed, velocity, time for sampling, angle respect to the co ordinate system will be obtained from this procedure}
7: t = get Optimal Refresh Time(v);
8: ?tp = form Contour of Interest ( X, Y, t , q, v);
9: Assign Worker The Id (?i, ?tp);
10: ?: = find total (?i , ?tp )
{Determines the total number of contour of interests in the cell}
11: Overlap (t, ?);
12: go to 6;
13: End for
As the algorithm clearly states that the WNs will be activated on the basis of the contour of interest formed by the CN. The contour of interest will be created on the basis of the vehicular kinematics of wheeled and tracked vehicles and will significantly contribute to energy minimization. The location of the neighbouring sensor nodes within the area formed by the CN is known by itself and using efficient sleep-wake policy the activation of the WNs is possible.
______________________________________________________________________
Algorithm 2: Assign Worker the Id (?i , ?tp) ______________________________________________________________________
1: for each ?ij ? ?i
2: if (check inclusion (?ij , ?tp ))
Activate (?ij);
Assign identity (?ij , ?tp );
Else
Skip
End if
3: end for
__________________________________________________________________
Algorithm 3: Overlap (t, ?) ______________________________________________________________________
1: For p=1 to k
2: If (p < ?)
3: l=p+1;
4: Check overlap (?tp , ?tl );
5: Overlap action (?tp , ?tl );
6: End if
7: If (p+1 < ?)
8: l=p+2;
9: Check overlap (?tp , ?tl );
10: Overlap action (?tp , ?tl );
11: End if
12: If (p+2 < ?)
13: l=p+3;
14: Check overlap (?tp , ?tl );
15: Overlap action (?tp , ?tl );
16: End if
17: End for
The number of active WNs in contour of interest ?tp is ?tp, for target p, in surveillance field ?. We also call µtp,k the overlapped area of interest between µtp and µtk ,which corresponds to the contours of interest , ?tpand ?tk respectively.
____________________________________________________________________
Algorithm 4: Overlap Action (?tp , ?tl) ______________________________________________________________________
1: Get the overlapped area, µtp,l from µtp and µtl .
2: Update µtl using µtl = µtl – µtp,l and ?tl accordingly
3: If ?tl < 1
4: ?t`p= ceiling ( ?tp / 2 ); (4.15)
5: Else if ?tl= > 1 && ?tl < = 5
6: ?t`p= floor (?tp/ 3) ; (4.16)
7: End if
8: Update ?tp such that ?tp= ?tp – ?t`p ;
9: Update ?tl such that ?tl= ?tl + ?t`l ;
10: End.
We would like to consider, the technique followed in (4.15) as, ‘The Mitosis Technique’, in conformance with the cell division technique, Mitosis [18], particularly observed in flora and fauna cells, where, the size and properties of the newly created cells are roughly the same. On the other hand, the technique described in (4.16) is considered by us as ‘the Amitosis Technique’. The two new cells created in the Amitosis [18] process, vivid in unicellular microscopic organisms like Bacteria, Yeast, are unequal in size and properties.
When there will be insufficient number of WNs (one to four) in an updated contour of interest during overlapping action, we plan to take a few WNs from a contour of interest having good number of WNs (five to six) and give it to the updated one. However, if the updated contour of interest contains less than one WN then we divide the number of WNs of the fixed contour of interest into two and assign half of the WNs to the updated one.
Simulation Result
In the previous chapters we have described the architecture and algorithm of the proposed energy efficient contour tracking approach for sensor network along with heuristics for multiple target tracking. In this chapter we describe the simulation results of multiple target minimal contours tracking in a sensor network. Through simulation we study the behavior of our approach and evaluate its performance based on some performance metrics. We also compare the simulation results of the proposed scheme with conventional prediction based algorithms provided in [24].
5.1 Simulation Settings
We simulate contour tracking using OMNeT++, an open-source, component-based simulation package designed for modelling communication networks and other distributed systems. Our main objective is to understand the impact of various parameters on the performance issues of the proposed system. We also simulate one of the more conventional predictive tracking algorithms to make a comparison between our approach and that conventional tracking on various metrics.
To set up a simulation environment, at first we need to specify various settings for the construction of the base sensor network. These settings are to be kept the same for both simulations: ours’ and the conventional one so that we can evaluate the performance metrics under the same condition and therefore, obtain a fair, unbiased comparison between the tracking methods. In Table 5.1, the general simulation settings are listed.
Table 5.1 : Simulation Settings
| Parameter | Value |
| General settings | |
| Network dimension | 1000 1000 meter |
| Number of Worker Nodes(WN) | 500 |
| Number of Computational Nodes(CN) | 1 to 10 |
| Number of Boundary Nodes(BN) | 40 |
| Deployment of nodes | Uniform random |
| Link types | 1. BN to CN: unidirectional, short range
2. WN to CN: bidirectional, short range. 3. CN to CN: bidirectional, long range. |
| Event settings | |
| Simulation type | Discrete-event driven |
| Target intrusion point | User defined |
| Inter-arrival time for targets | Static |
| Target mobility type | Brownian motion |
| Simulation time | 2500 STU |
| Faul | |