Use of Eigenvector Centrality for Mobile Target Tracking

Use of Eigenvector Centrality for Mobile Target Tracking

DOI: 10.4018/978-1-5225-3802-8.ch006


The author proposes an eigenvector centrality (EVC)-based tracking algorithm to trace the trajectory of a mobile radioactive dispersal device (RDD) in a wireless sensor network. They propose that the sensor nodes simply sum up the strengths of the signals (including those emanating from a RDD) sensed in the neighborhood over a sampling time period and forward the sum of the signals to a control center (called sink). For every sampling time period, the sink constructs an adjacency matrix in which the entry for edge (i, j) is the sum of the signal strengths reported by sensor nodes i and j, and uses this adjacency matrix as the basis to determine the principal eigenvector whose entries represents the EVCs of the vertices with respect to the radioactive signals sensed in the neighborhood. The author proposes that the arithmetic mean (calculated by the sink) of the X and Y coordinates of the suspect sensor nodes (those with higher EVCs) be considered as the predicted location of the RDD at a time instant corresponding to the middle of the sampling time period.
Chapter Preview

1. Introduction

Wireless sensor networks (WSNs) are useful for several environment monitoring applications, including those require target tracking. In this chapter, we focus on a specific target tracking application wherein the target is a radioactive device (shortly referred to as RDD for the rest of the chapter) that emanates radiations (as signals) in the neighborhood and the sensors deployed in the area of monitoring sense these signals as well as quantify the strength of these signals. The radiation signal strength is expected to be larger in the neighborhood through which the RDD moves and we seek to trace the path of the RDD (the trajectory) through a data gathering mechanism. We construct a data gathering (DG) tree as a rooted spanning tree connecting all the sensor nodes, with the root node randomly chosen by the control center (sink) at the time of constructing the DG tree. Compared to other communication topologies (like mesh, clusters, etc), the use of a DG tree minimizes the energy consumption and the redundancy in the information being propagated. Several efficient data gathering algorithms have been proposed in the literature (see Meghanathan, 2012 for a survey and comparative analysis) of wireless sensor networks.

We assume the sensor nodes to operate within a sensing range that is half their transmission range. Since discerning the radioactive signals from the background signals would be a hard and even erroneous, we let the sensor nodes to transmit the cumulative strength of the signals sensed as the data along the DG tree. The sink node is assumed to know the entire topology (two nodes are connected if they are within the transmission range per node) and hence could fill up an adjacency matrix based on the signal strength data received from the individual sensor nodes along the DG tree. An entry (i, j) in the adjacency matrix contains the sum of the signal strengths reported by nodes i and j that have an edge between them in the network. If the RDD is in the vicinity of a sensor node s, then the entries for node s and its neighbors are expected to be relatively much larger in the adjacency matrix at the sink. We use this idea as the basis and propose to determine the principal eigenvector of the adjacency matrix and the top x number of nodes with the largest values for the eigenvector centrality (EVC), corresponding to the entries in the principal eigenvector, are considered for predicting the location of the RDD. Since the sensor nodes are static, the sink is assumed to have learnt the locations of the sensor nodes a priori (as part of the network initialization) and could predict the location of the RDD as the average of the X and Y coordinates of the top x nodes that had the largest EVC values for the adjacency matrix at the particular time. We repeat this process throughout the duration of the simulation and build a trajectory for the mobile RDD. We evaluate the effectiveness of the tracking mechanism by computing the difference between the predicted location and the actual location of the RDD across all the sampling time instants and determine the median of the prediction error (Euclidean distance between the actual and predicted locations). We conduct the simulations under both energy-unconstrained and energy-constrained scenarios. Under the energy-constrained scenarios, we observe the prediction error to increase with depletion of sensor nodes and the resulting loss of coverage.

The rest of the chapter is organized as follows: Section 2 presents the system model and an algorithm to determine energy-efficient minimum distance spanning trees-based data gathering trees for wireless sensor networks. Section 3 presents an example to illustrate the computation procedure of the EVCs of the sensor nodes based on the signal strengths reported to the sink node. Section 4 presents the procedures adopted at the individual sensor nodes for target tracking. Section 5 presents the simulation models and the results of the tracking algorithm with respect to various operating parameters. Section 6 reviews related work on mobile target tracking using sensor networks. Section 7 concludes the chapter and Section 8 discusses future research directions.

Complete Chapter List

Search this Book: