# An Efficient Relayed Broadcasting Based on the Duplication Estimation Model for IoT Applications
## 2 Statement of the Problem
### Related Work
Meanwhile, the broadcast storm problem can be dealt with in a non-probabilistic way. The approach proposed in [26; 27; 28] uses the network topology information (e.g., list of 1-hop or 2-hop neighbor nodes or their locations) to determine an optimal relay node (called _forwarder_). This approach can quickly extend the coverage of flooding while minimizing the redundant transmissions. However, it leads to an inevitable signaling overhead to acquire the topology information, so it is not suitable when the topology changes frequently or the number of node is large. Furthermore, this approach implicitly assumes that the forwarder successfully deliver a frame to all of its adjacent nodes, which is not always valid due to interference by hidden nodes. Most of the existing studies attempted to avoid the broadcast storm problem by suppressing the redundant transmissions. However, the excessive suppression may degrade the reachability or reliability of broadcasting, which was referred to as _early die-out_ or _premature death_[19; 29]. To avoid this problem, it was proposed in [30] that the node relays the frame deterministically (i.e., with the probability of one) as long as the number of adjacent nodes or duplicate frames received is less than a predefined threshold. Another approach was to additionally broadcast the frame after detecting the early die-out. According to [29], if a node does not receive the duplicate frame at least \(m\) times from its adjacent nodes within a reasonable timeout period \(T\), it broadcasts the frame again. The similar idea was proposed in [19]; each node checks whether its adjacent nodes have received the frame by means of _neighbor confirmation_ scheme. If some of them did not receive the frame until a certain amount of time \(T\), the node broadcasts the frame. The critical issues in [19; 29] are that it is hard to determine the optimal values of \(m\) and \(T\) in a distributed way and the neighbor confirmation scheme inevitably increases the signaling overhead. The reliable broadcast propagation (RBP) mechanism proposed in [31] employs the implicit ACK and unicast transmission to improve the reliability of broadcast. In [31], each node considers the overheard transmission from 1-hop adjacent node as an implicit ACK and estimates the fraction of acknowledged adjacent nodes. If this fraction is below a given threshold value, the node attempts to retransmit the frame to a specific unacknowledged node as a unicast transmission. Apart from the flooding mechanisms, many media access control (MAC) protocols for reliable broadcast or multicast in IEEE 802.11 WLANs have been proposed in the literature [32; 33; 34; 35]. They basically exploited the IEEE 802.11 control frames (e.g., ready-to-send (RTS), clear-to-send (CTS), and ACK frames) to improve the reliability. The main issues of these protocols are severe feedback overhead, collision, and the hidden node problem. To reduce the feedback overhead, the negative ACK mechanism was proposed in [32; 34], or only a representative receiver (known as _leader_) or multiple ACK-leaders are allowed to transmit the ACK frame [34; 35]. Moreover, the transmission sequence or probability of control frames was controlled to mitigate the collision [33; 34]. Compared to these existing studies, our one is different due to the following points comprising its advantages:  
* Our flooding mechanism provides a unified solution to the broadcast storm problem and early die-out by combining the duplication suppression scheme and re-queuing scheme. The former discards unnecessary duplicate frames in a proactive way, whereas the latter retransmits selected frames in a reactive way. In both schemes, the novel criterion called the duplication ratio is used. * Unlike the previous flooding mechanisms, the proposed mechanism does not need to tune several control parameters or to determine their optimal values under different network conditions. Therefore, it provides the robust performance to the change of network conditions.