Broadcast Algorithms for Mobile Ad hoc Networks based on Depth-first Traversal
Koushik Sinha, Pradip K. Srimani · 2004
Two deterministic broadcast algorithms are presented for mobile ad hoc networks where the mobile nodes possess collision detection capabilities. The first algorithm, based on a depth-first traversal of the nodes, accomplishes broadcast in O(n log n) time in the worst case. The second algorithm is mobility resilient even when the topology changes very frequently, with O(∆·n log n+n· |M |) time to broadcast in the worst case, where |M | is the length of the message to be broadcasted and ∆ is the maximum node degree.