Flooding in wireless ad hoc networks

✍ Scribed by H Lim; C Kim

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 265 KB
• Volume: 24
• Category: Article
• ISSN: 0140-3664
• DOI: 10.1016/s0140-3664(00)00233-4

✦ Synopsis

In an ad hoc network, each host assumes the role of a router and relays packets toward ®nal destinations. This paper studies ef®cient routing mechanisms for packet ¯ooding in ad hoc wireless networks. Because a packet is broadcast to all neighboring nodes, the optimality criteria of wireless network routing are different from that of the wired network routing. We show that the minimum cost ¯ooding tree problem is similar to MCDS (Minimum Connected Dominating Set) problem and prove the NP-completeness of the minimum cost ¯ooding tree problem. Then, we propose two ¯ooding methods: self-pruning and dominant pruning. Both methods utilize the neighbor information to reduce redundant transmissions. Performance analysis shows that both methods perform signi®cantly better than the blind ¯ooding. Especially, dominant pruning performs close to the practically achievable best performance limit.