Benchmarks and Tradeoffs for Minimum Hop, Minimum Edge and Maximum Lifetime per Multicast Tree in Mobile Ad hoc Networks

摘要

per source-receiver path, minimum number of edges per tree and maximum tree lifetime for multicast routing in mobile ad hoc networks (MANETs) and explore the tradeoffs between these three metrics. Accordingly, we consider three categories of algorithms – Breadth First Search (for minimum hop trees), minimum Steiner tree heuristic (for minimum edge trees) and the recently proposed OptTreeTrans algorithm (for maximum lifetime trees). Extensive simulations of the above three algorithms on centralized snapshots of the MANET topology, sampled for every 0.25 seconds, have been conducted for 1000 seconds under two different conditions of network density and three different multicast group sizes. Simulation results illustrate that minimum edge trees have 20-160% larger lifetime than the minimum hop trees; but still, the minimum edge trees have only 6-14% of the maximum tree lifetime possible. The tradeoff is that the minimum edge trees and maximum lifetime trees respectively have 20-100% and 28-86% larger hop count per source-receiver path compared to the minimum hop trees. Similarly, the minimum hop trees and maximum lifetime trees respectively have 13-35% and 35-68% more edges than the minimum edge trees. Thus, the above three performance metrics cannot be simultaneously optimized and MANET multicast routing can be envisioned to have at least three mutually contrasting categories of protocols.