Computer Science – Networking and Internet Architecture
Scientific paper
2011-03-30
Computer Science
Networking and Internet Architecture
11 pages, 8 figures. Originally submitted to KTH Royal Institute of Technology Technical Report Database on March 30, 2011
Scientific paper
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.
Balister Paul
Bollobas Bela
Chen Phoebus
Johansson Karl H.
Sastry Shankar S.
No associations
LandOfFree
Multi-path Routing Metrics for Reliable Wireless Mesh Routing Topologies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Multi-path Routing Metrics for Reliable Wireless Mesh Routing Topologies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-path Routing Metrics for Reliable Wireless Mesh Routing Topologies will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-569447