  Several emerging classes of applications that run over wireless networks have
a need for mathematical models and tools to systematically characterize the
reliability of the network. We propose two metrics for measuring the
reliability of wireless mesh routing topologies, one for flooding and one for
unicast routing. The Flooding Path Probability (FPP) metric measures the
end-to-end packet delivery probability when each node broadcasts a packet after
hearing from all its upstream neighbors. The Unicast Retransmission Flow (URF)
metric measures the end-to-end packet delivery probability when a relay node
retransmits a unicast packet on its outgoing links until it receives an
acknowledgement or it tries all the links. Both metrics rely on specific packet
forwarding models, rather than heuristics, to derive explicit expressions of
the end-to-end packet delivery probability from individual link probabilities
and the underlying connectivity graph.
  We also propose a distributed, greedy algorithm that uses the URF metric to
construct a reliable routing topology. This algorithm constructs a Directed
Acyclic Graph (DAG) from a weighted, undirected connectivity graph, where each
link is weighted by its success probability. The algorithm uses a vector of
decreasing reliability thresholds to coordinate when nodes can join the routing
topology. Simulations demonstrate that, on average, this algorithm constructs a
more reliable topology than the usual minimum hop DAG.
