Research On Pursuer-Evader Problem In Wireless Sensor Networks

As a brand new computation paradigm, wireless sensor networks (WSN) employ numerous small-sized sensor nodes which are capable of sensing, computing and communication and distributed in a large area of physical world, which offer an inspiring new way for interaction between human being and the environment. WSN can be applied into various scenarios such as environment monitoring, industry process control, battlefield surveillance, after-disaster rescue, etc.Since sensor nodes can be directly deployed in the physical environment and have a close watch over targets, WSN is especially beneficial to targets tracking problems. Evader-Pursuer problem is an application based on targets tracking, in which a certain number of pursuers aim to capture a set of targets within minimum time. This problem comprises the following four sub-problems: (1) a set of sensor nodes acquire local targets information such as their number and positions through detection and collaborative computation; (2) the pursuers query the network to obtain global targets information; (3) pursuers update and predict the trajectories of targets based on the global targets information; (4) based on the result of the above steps, pursuers choose the optimum scheme to finish the capturing task. The first three sub-problems are studied in this thesis.Enumeration and localization of multi-target is by no means an easy task in wireless sensor networks. And existing researches have not delved into this problem either. A typical solution is to form nodes into uncorrelated clusters around the targets according to their measurements. Each cluster covers one or more targets, self-organizes and counts. The numeration algorithms differ mainly in the methods to form clusters and the way to compute the number of targets. The dilemma is: on the one hand, it is hard to achieve high precision with only binary or intensity-aware nodes when targets crowd; on the other hand, both multi-modal sensor nodes and more complex algorithms will either heighten the construction price of WSN or impose heavy computation and communication burden on WSN. This thesis explores energy attenuation characteristics such as limited influence range, continuous and gradual energy intensity change, etc. and proposes an energy-based target numeration algorithm EBTN. ETBN firstly clusters sensor nodes into groups according to their measurements, which depends much on the distance between sensors and targets, and elects a center node as the leader of the cluster. Then it is the leader's task to fit the energy distribution of its cluster into a polynomial function and integrate to get the total energy of the whole cluster. Dividing the total energy by the unit energy of each target, the cluster leader will obtain the number of targets in its cluster. Based on this information, leader selects a set of nodes with local maximum measurements and uses their positions as the positions of the targets.Information storage and query has already been intensively studied in wireless sensor networks, however, information dissemination for evader-pursuer problems has not yet been investigated. Evader-pursuer problems require timely report of single typed and sketchy target information, while existing distributed data storage methods and systems aim to offer a large amount and multi-typed data, and flexible query interfaces for users, without guaranteeing real time query. Therefore these methods are not suitable for data query in evader-pursuer problems. The thesis is the first to explore the dissemination problem for evader-pursuer problems, and designs a single coverage based target information dissemination algorithms SCUS. Based on the work of EBTN, each cluster distributes the local targets information to a set of selected storage nodes, ensuring that the pursuers can get the global targets information within its communication range regardless of their position. Besides the high query success rate, SCUS makes sure that the nodes are uniformly employed as storage nodes, therefore to maximize the lifetime of network.The computation and prediction of target trajectories is a significant part of target tracking problem. And many methods have been proposed and practiced. However, when targets are of high mobility, high density and low localization precision, traditional methods would employ complex models, resulting in computation burden and long delay. With the help of EBTN and SCUS, a third algorithm DASE is proposed for pursuers to compute the target trajectory and predict new position. DASE focuses on the specific requirement of evader-pursuer problems, and computes the data association probability of imprecise target location with the existing trajectories. Since evaders are always with high mobility, DASE uses only recent history information for a linear least square fitting. Compared with traditionally used data association and state predication methods, DASE distinguishes with its simple computation, real time manner and satisfactory performance. Besides, DASE could handle false alarms and detection failures in target localization, thus meet the requirement of evader-pursuer problem.The above three algorithms have all been simulated on Matlab, and they work together to offer accurate and timely information for decision-making in evader-pursuer application.