Reliable Route Selection for Wireless Sensor Networks with Connection Failure Uncertainties

For wireless sensor networks (WSN) with connection failure uncertainties, traditional minimum spanning trees are no longer a feasible option for selecting routes. Reliability should come first before cost since no one wants a network that cannot work most of the time. First, reliable route selection for WSNs with connection failure uncertainties is formulated by considering the top-k most reliable spanning trees (RST) from graphs with structural uncertainties. The reliable spanning trees are defined as a set of spanning trees with top reliabilities and limited tree weights based on the possible world model. Second, two tree-filtering algorithms are proposed: the k minimum spanning tree (KMST) based tree-filtering algorithm and the depth-first search (DFS) based tree-filtering algorithm. Tree-filtering strategy filters the candidate RSTs generated by tree enumeration with explicit weight thresholds and implicit reliability thresholds. Third, an innovative edge-filtering method is presented in which edge combinations that act as upper bounds for RST reliabilities are utilized to filter the RST candidates and to prune search spaces. Optimization strategies are also proposed for improving pruning capabilities further and for enhancing computations. Extensive experiments are conducted to show the effectiveness and efficiency of the proposed algorithms.