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 are mainly suitable for static MWNs. In mobile MWNs with highly dynamic topology, neighbor information is often outdated and stateful algorithms always incur a large overhead in acquiring neighbor information, which in turn causes performance degradation.

10.1.2 Stateless Broadcast

The stateless broadcast protocols are especially suitable for resource-limited networks with frequent topology changing. In Heissenbuttel et al. (n.d.), a stateless broadcast algorithm (DDB) is proposed, which allows nodes to make locally optimized forwarding decisions without neighborhood information. The core idea is to let nodes that can cover larger additional areas broadcast first and then suppress other nodes that do not cover an additional area. The only information needed is node location, and the previous hop's location which are embedded in the received packet. The rebroadcast delay of a node is dynamically adjusted according to received packets from neighbors during the timer period. The number of retransmissions and the broadcast delays is are reduced, while the delivery rate under node mobility and traffic congestion remains high.

The DDB algorithm is tolerant of link failure and packet loss as it utilizes the concept of dynamical forwarding delay which is similar to opportunistic forwarding. However, DDB still assumes the UDG model with a fixed transmission range, so it cannot take advantage of the nodes that received a packet but are located outside of the transmission radius. In this sense, DDB is not fully opportunistic. Also, it does not consider the reliability issue in the realistic physical layer model.