Emerging applications using wireless sensor networks for critical areas such as environmental monitoring and emergency response highlight the urgent need for more powerful algorithms for tracking amorphous events or phenomena with dynamic identities. Several such events may combine into a large whole or one event may disintegrate into several smaller ones. Current efforts in event detection and tracking have mostly assumed that either events remain distinct, never crossing or passing too close together to become indistinguishable, or if they do cross that they were identified prior and nothing new has formed. This project addresses the research challenges in designing and implementing a system that is capable of tracking events with or without well-defined shapes and identities in the presence of stringent energy constraints and unpredictable network failures posed by wireless sensor networks. Specific research objectives include: design and evaluation of algorithms that detect and track any types of events including amorphous phenomena with dynamic signatures and events that possess a static shape with a crisp boundary; design and evaluation of algorithms that form and reform communication structures around events of interest; and development of an integrated system that provides interfaces to high level application tasks to execute on each identified event. Successful completion of this project will result in a rich set of tools that can be used by applications monitoring all different types of events. The tools will be made publicly available via the Internet. This project provides opportunities for recruitment of female students and undergraduate students.
Stringent energy constraints and unpredictable network failures posed by wireless sensor networks present significant challenges for designing and implementing a system that is capable of tracking events with or without well-defined shapes and identities. This project makes significant contributions in detection and tracking amorphous events that may combine into a large whole or one event may disintegrate into several smaller ones. Intellectual merits: (1) We have designed an algorithm called DRAGON that detects and tracks any types of events including amorphous phenomena with dynamic signatures and events that possess a static shape with a crisp boundary. Our idea employs two physics metaphors: event center of mass, to give an approximate location to the event; and node momentum, to guide the detection of event merges and splits. Our theoretical analysis of DRAGON indicates that the algorithm possesses the following features: a) It terminates. b) Its decision predicates are invariant with respect to the range of the mass function. c) Its execution is invariant to node placement, i.e., the decisions that our algorithm makes with respect to event splits and merges are not influenced by local differences in the density of the sensor deployment. d) Our approach's cost grows linearly with the number of events in the network and grows quadratically or better with respect to event coverage. DRAGON was first tested using simulated events. Events used for testing DRAGON are always built up from basic geometric shapes. Region events are modeled with squares and point events have a circular sensing profile. When these simple events are allowed to overlap, not only do we get splits and merges, but we create much more complex and interesting event shapes by compounding simple geometry. Extensive simulation studies of DRAGON have made the following conclusions. a) As event size increases, our approach shows excellent accuracy. Its costs in both time and energy consumption are somewhere between logarithmic and linear. b) As event count increases, DRAGON has a very clear linear growth order for both energy consumption and time complexity. This confirms our theoretical complexity analysis. c) As event speed increases, DRAGON has a very slight linear increase in energy consumption, hence good scalability. d) With varying network density of topology, DRAGON shows great flexibility. We then evaluated the performance of DRAGON using a more realistic event model. Numerical fluid simulation was used to create a more realistic region event, i.e., evolution of contaminants in the subsurface, in a rectangular area of 450 meters by 80 meters where 360 sensor were placed. When DRAGON was used in detection and tracking of subsurface contaminant plumes generated by numeric fluid model, it achieved an average event count difference of 1.47 and an average event similarity of 80%. This shows that DRAGON does work well with various dynamic events. (2) We have designed an algorithm called AWARE that forms and adapts communication structures around events of interest. It is a distributed general-purpose clustering algorithm for WSNs that does not consider all nodes to be equal in importance and provides a communication structure for high level services. AWARE occasionally reclusters the network to rotate cluster head responsibilities among the nodes. However, the frequency of this reclustering is proportional to the amount of event-driven activity observed in the vicinity. The advances that we present in this work are both applied and theoretical in nature. Our approach is not only able to reduce energy consumption for in-network communication, but it is also robust to node failures. In addition to handling node faults, AWARE is also able to operate when nodes have limited movement in, are added to, or removed from the network. This is all accomplished while placing only minimal demands on the network being used, making AWARE useful for a wide array of scenarios. On the theoretical side, we formalized the problem and shown it to be NP-complete. We also showed that AWARE reclusters the network in constant time, forms connected clusters, and will recover from node faults if link quality is accurately estimated. The experimental results demonstrate how AWARE forms a fair number of clusters with reasonable average cluster size, creating very few singleton clusters. More importantly, the short distance between a clusterhead and the Activity Center of Mass validates AWARE’s effectiveness in selecting clusterheads close to the sensed activity. All these benefits contribute to a considerable energy consumption reduction. Moreover, AWARE’s high packet delivery ratio demonstrates its effectiveness for data collection applications. Broader Impacts: Amorphous events with dynamic signatures can be found in many application domains such as oil spill in the ocean, wild fire in the forest, or air pollutant. The ideas developed in this project can be generalized to these different events, hence providing a unique contribution towards solving fundamental problems of monitoring dynamically evolving phenomena in critical areas such as environmental monitoring and emergency response.
