Research On Algorithms For Event Monitoring In Wireless Sensor Networks

With the capabilities of sensing, computation and communication, cheap sensor nodes organize themselves as wireless sensor networks(WSNs) by wireless communication. Wireless sensor networks aim at monitoring the event of user interest by collaboratively collecting, sensing and analyzing environment information. Firstly, sensor nodes collect sensed data from physical objects, which are sampled by sensing components.Then sensed data are exchanged with computing devices through wireless communication in networks. WSNs achieve e?cient information collection and they build the connection between physical world and virtual computing world. The self-organization and collaboration of WSNs open up the potential of wide applications. And WSNs are widely applied in space exploration, electric monitoring system, medical care, intelligent transportation system, green building, smart home and disaster-prevention and early-warning system. In the event monitoring applications based on WSNs, accurate and real-time event information is helpful for correct decision making and analysis. However, wireless sensor networks exhibit resource constraints and design limitations. Resource constraints include short communication range, limited energy, low bandwidth and restricted capability of computation and storage. Design limitations are that the design of WSNs relies on the application and the monitored environment. Facing up to the challenges, researching on e?ective, lightweight, energy-e?cient and distributed event monitoring algorithms and real-time data delivery strategy is critical. The research issues and contributions of this thesis are summarized as follows.(1) This thesis investigates the problem of Top-k monitoring. The results returned by the Top-k queries provide k largest or smallest sensed values and their locations, which are practical and very useful for detecting abnormal events happened in the monitored region. However, existing algorithms concentrate on returning either exact results or approximate results, which bring about higher communication consumption. To overcome the shortcomings of the existing Top-k monitoring algorithms and improve the energy e?ciency, this thesis focuses on the research of filter based Top-k monitoring algorithm.Filter based Top-k Monitoring algorithm is proposed in this thesis, which aims at minimizing the expectation of communication overhead. Communication overhead model is presented and physical significance is analyzed. The formal definition of filter robustnessis given. Based on the essence of expectation and sensed data correlation, the probability of filter failure is derived. Minimizing the expectation of communication overhead as an optimization objective, optimal filter threshold is proved and Filter based Top-k Monitoring algorithm(FTM) is proposed. Real dataset based experiments are carried out to evaluate the e?ciency and e?ectiveness of the proposed algorithm. The theoretical analysis and performance evaluation demonstrate the accuracy and energy e?ciency of the proposed algorithm.(2) This thesis investigates the problem of double threshold based event monitoring.Errors, imprecise readings, and uncertainty are present in sensed data, due to hazardous conditions and inherent low sensitivity of sensors. Noise and inherent low sensitivity result in the deviation between sensed data and actual occasion, which incurs higher false alarm rate for Single Threshold based Monitoring(STM) methods. To overcome the deficiencies of STM based methods, this thesis focuses on monitoring strategies with probability guarantee in WSNs. Lightweight and distributed(α, τ)-monitoring schemes are provided. The main idea of(α, τ)-monitoring scheme is as follows. For given monitored threshold α and probability threshold τ, sensor node computes the upper bound of the probability of sensed data being larger than α, and it checks whether the upper bound crosses τ.(α, τ)-monitoring of critical point is proposed and the tight upper bound of the probability is proved.(α, τ)-monitoring algorithm for critical point with time complexity O(1) is proposed. Moreover, the thesis studies(α, τ)-monitoring of area. Mathematical methods for computing the tight upper bound of the probability that the aggregation result of monitored area is larger than the specified threshold are provided.(α, τ)-monitoring algorithm for area with time complexity O(n) is given. The problem of approximate continuous(α, τ)-monitoring is proposed. The semantics is that if the estimated probability for triggering an alarm satisfying the precision requirement is larger than the probability threshold τ, an alarm is generated. An optimal sample size is derived and a sampling based approximate(α, τ)-monitoring algorithm is provided. Theoretical analysis and simulation experiments demonstrate the e?ectiveness of proposed algorithms.(3) This thesis investigates the problem of rare event detection. A fundamental problem for detecting rare event or small probability event is to generate the description for the tail probability distribution of the underlying sensed data. For given small number τ,τ-quantile can e?ectively describe the corresponding tail probability distribution. However, the existing works focus on the computation of quantile summaries and they do notconsider the e?cient computation for the tail quantile. Small amount of the collected data in traditional strategy is useful for calculating the tail quantile, which is ine?cient in term of communication overhead. The(ε, δ)-estimator of τ-quantile is proposed in this thesis.A mathematical method to determine an optimal sample size based on the given precision requirement ε, δ and τ is provided. According to the above mathematical method, an optimized sampling based algorithm for calculating approximate τ-quantile is proposed,such that the approximate τ-quantile result can be propagated by an aggregation manner with small communication cost. Moreover, the theoretical analysis of the algorithm performance is conducted. It is proved that for given τ and ε, the upper bound of sample size is log order of magnitude of the sensed data set, and then the provided algorithm is more communication e?cient in theory. Simulation experiments based on real dataset are conducted to show the e?ectiveness and high accuracy of the proposed algorithms.(4) This thesis investigates the problem of finding optimal retransmission thresholds for relay nodes along a delivery path. Retransmission threshold in wireless sensor networks is critical to the latency of data delivery in the networks. However, existing works on data transmission in sensor networks did not consider the optimization of the retransmission threshold, and they simply set the same retransmission threshold for all sensor nodes in advance. The method did not take link quality and delay requirement into account, which decreases the probability of a packet passing its delivery path within given deadline. The problem of finding optimal retransmission thresholds for each node along a delivery path is defined, and is formalized as an integer optimization problem. A dynamic programming based distributed algorithm(DPDA) for solving the problem above is proposed, the correctness of the algorithm is proved, and its time and space complexity are analyzed, i.e. O(n? · max1≤i≤n{ui}) and O(n? · max1≤i≤n{ui}). In case of the delivery delay? being greater than polynomial, a linear programming based(1 + pmin)-approximation algorithm(LPAA) is proposed. Furthermore, in case of the ranges of the upper and lower bounds of the retransmission thresholds being big enough, a lagrange multiplier based distributed approximation algorithm(LMDAA) with time complexity O(1) is proposed.Theoretical analysis and simulation results show that the proposed algorithms have better performance for real-time data delivery.