Querying Uncertain Minimum in Wireless Sensor Networks

In this paper, we introduce two types of probabilistic aggregation queries, namely, Probabilistic Minimum Value Queries (PMVQ)s and Probabilistic Minimum Node Queries (PMNQ)s. A PMVQ determines possible minimum values among all imprecise sensed data, while a PMNQ identifies sensor nodes that possibly provide minimum values. However, centralized approaches incur a lot of energy from battery-powered sensor nodes and well-studied in-network aggregation techniques that presume precise sensed data are not practical to inherently imprecise sensed data. Thus, to answer PMVQs and PMNQs energy-efficiently, we devised suites of in-network algorithms. For PMVQs, our in-network minimum value screening algorithm (MVS) filters candidate minimum values; and our in-network minimum value aggregation algorithm (MVA) conducts in-network probability calculation. PMNQs requires possible minimum values to be determined a prior, inevitably consuming more energy to evaluate than PMVQs. Accordingly, our one-phase and two-phase in-network algorithms are devised. We also extend the algorithms to answer PMNQ variants. We evaluate all our proposed approaches through cost analysis and simulations.