IN-NETWORK QUERYING AND TRACKING FOR WIRELESS SENSOR NETWORKS

Book excerpt: In contrast to traditional Wireless Sensor Network (WSN) applications that perform only data collection and aggregation, new generations of information-processing applications (such as pursuit-evasion games, tracking, evacuation, and disaster relief applications) require in-network querying and tracking. The resource limitations of WSNs, however, make it challenging to implement in-network querying/tracking in a distributed, lightweight, resilient and energy-efficient manner. Moreover, in a mobile network, querying/tracking protocols need to deal with the mobility of the intermediate nodes that maintain querying/tracking structures. To address these challenges, this dissertation focuses on developing local and resilient services for querying and tracking under static and passively mobile WSNs.^For efficient event querying in static networks, we exploit location information and geometry of the network, and present a Distributed Quad-Tree (DQT) in-network querying framework where a virtual quad-tree structure is overlaid in the target area. DQT achieves distance sensitivity for querying of an event: the cost of answering a query for an event is at most a constant factor of the distance ``d'' to the event. As event-based querying is inherently limited to the anticipated types of inquiries, to achieve complex range-based querying, we develop a multi-resolution algorithm that models the data in a decentralized way. With our model, range queries can be answered with approximate values with different resolutions at various layers of the DQT hierarchy. In-network querying/tracking problem becomes more challenging in the Mobile Ad Hoc Networks (MANets) setting. To this end, we propose the Mobility-enhanced Distributed Quad-Tree (MDQT) framework that adapts DQT to the MANets domain.^MDQT employs a cell abstraction to mask the mobility of the nodes and provides the illusion of a logical static network overlaid on the mobile network. MDQT implements this virtual static layer in a lightweight/communication-free manner by exploiting the soft-state principle and the snooping feature of wireless communication. Both DQT and MDQT framework are structure-based, which need to advertise targets' location periodically. To release the communication overhead in structure-based approaches, we introduce a Probabilistic Model Based Tracking (PMBT) protocol that integrates a gradient model of the target's proximity and an online Markov model. PMBT avoids the need to maintain a hierachical data structure and the need to send update messages periodically about the target's location.^By taking this hybrid approach PMBT significantly outperforms both gradient-based and Markov approaches alone. Lastly, we investigate the Pursuer-Evader Tracking(PET) problem in a realistic (delay- and loss-prone) WSN. PET problem differs from previous tracking services in that the pursuer is also an important role and a dynamic factor to consider. We devise a holistic solution to this problem taking into account the dynamics of the pursuer as well as the limitations of WSNs. Our solution publishes the evader's information directly to the pursuer in each adaptive sampling interval, minimizing the communication overhead while ensuring capture. Our fault-tolerance design ensures a high capture rate even under consecutive message losses.