2011 · 33 citations · 28 references
ComputingComputer ScienceComputer SystemsComputer NetworksDistributed SystemsWireless CommunicationsMesh NetworksNetwork ReliabilityRoutingRouting AlgorithmsRouting ProtocolsWireless NetworksAdaptive Routing In Mesh NetworksMarkov Decision ModelsMulticast CommunicationMulticast RoutingMulticast TransmissionReliable MulticastTransmission DiversityWireless Mesh Networks
We propose a routing metric for enabling high-throughput reliable multicast in multi-rate wireless mesh networks. This new multicast routing metric, called expected multicast transmission time (EMTT), captures the combined effects of 1) MAC-layer retransmission-based reliability, 2) transmission rate diversity, 3) wireless broadcast advantage, and 4) link quality awareness. The EMTT of one-hop transmission of a multicast packet minimizes the amount of expected transmission time (including that required for retransmissions). This is achieved by allowing the sender to adapt its bit-rate for each ongoing transmission/retransmission, optimized exclusively for its next-hop receivers that have not yet received the multicast packet. We model the rate adaptation process as a Markov decision process (MDP) and derive an efficient procedure for computing EMTT from the theory of MDP. We present receiver-initiated algorithms and describe protocol implementation for the EMTT-based multicast routing problem. Numerical results are presented to demonstrate the accuracy of the proposed algorithms against optimal solutions to the multicast routing problem. Simulation experiments confirm that, in comparison with single-rate multicast, multi-rate multicast using the EMTT metric effectively reduces the overall multicast transmission time while yielding higher packet delivery ratio and lower end-to-end latency.
28
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
A high-throughput path metric for multi-hop wireless routing
Douglas S. J. De Couto, Daniel Aguayo, John Bicket et al. · 2003 · 3.4K citations
A threshold of ln <i>n</i> for approximating set cover
Uriel Feige · Journal of the ACM · 1998 · 3.1K citations · Full text
Routing in multi-radio, multi-hop wireless mesh networks
Richard Draves, Jitendra Padhye, Brian Zill · 2004 · 2.5K citations