Multihop Wireless Networks: Opportunistic Routing

10.1 Related Works on Broadcasts in General MWNs

Broadcast algorithms in general MWNs can be classified into stateful and stateless ones according to (Heissenbuttel et al. n.d.). Stateful algorithms utilize network information, like neighborhood state. In stateless algorithms, nodes make fully localized decisions only using information from themselves and the received packet.

10.1.1 Stateful Broadcast

Stateful broadcast algorithms aim at minimizing redundancy from the global or local point of view. They require neighbor information and need extra overheads for neighbor information exchange.

10.1.1.1 Neighbor-Designating Methods

In neighbor-designating methods, the forwarder is the one who makes the decision about which of its neighbors should relay the packet. Basically, research in this category aims to find approximate algorithms for the minimum connected dominant set (MCDS), which is NP-hard. Typical algorithms include multipoint relaying (MPR) (Qayyum et al. 2002), and the dominant pruning (Lim and Kim 2000; Lou and Wu 2002).

10.1.1.2 Self-Pruning Based Methods

In self-pruning based methods, each node decides its own forwarding status independently and locally. Dai and Wu (2004) proposed a general framework for self-pruning based methods, and pointed out that basic elements for these methods include: 1. Identifying the existence of a replacement path; 2. Identifying the existence of an alternative cover set; 3. The assignment of node priority.

Stateful broadcast algorithms ...