# An Efficient Relayed Broadcasting Based on the Duplication Estimation Model for IoT Applications
## 2 Statement of the Problem  
### Motivation and Challenges  
First, we make the following assumptions about flooding considered in this study; (i) there does not exist any central node that collects global information about the network topology and controls the relay operation of nodes, (ii) each node is unaware of the locations of its adjacent nodes and it does not maintain a list of adjacent nodes, (iii) any control frames including an acknowledgment (ACK) frame are not advertised to or exchanged between adjacent nodes. Figure 2 illustrates several problems that can arise in flooding: redundancy, unreliability, collisions, and interference. The node \(g_{i}\) is defined as a node that can receive frames from a source node \(s\) and is denoted as a _1-hop node_. The area \(G_{i}\) is defined as the transmission coverage of node \(g_{i}\) where the frames can be propagated via the relaying of \(g_{i}\) to the adjacent nodes (denoted as _2-hop nodes_) that cannot directly receive frames from the source node. First, Figure 2a shows two cases: _non-overlap_ and _full-overlap_. In the former case, \(G_{1}\) and \(G_{2}\) do not overlap at all, i.e., any 2-hop node located in \(G_{1}\) or \(G_{2}\) does not receive a duplicate frame even though both \(g_{1}\) and \(g_{2}\) broadcast the same frame. Subsequently, it is necessary not to restrict the transmissions of \(g_{1}\) and \(g_{2}\). On the other hand, in the full-overlap case where \(G_{3}\) and \(G_{4}\) overlap entirely and regardless of which node (i.e., \(g_{3}\) or \(g_{4}\)) first transmits, any subsequent transmission will result in the unnecessarily duplicate reception at all of the 2-hop nodes in \(G_{3}=G_{4}\). The problem in this case can be easily avoided by restricting the redundant transmission of the node detecting the transmission of the same frame. Figure 2: The broadcast storm problem under various network statuses: (**a**) non-overlap and full-overlap, (**b**) partial overlap (two nodes), (**c**) partial overlap (three nodes), and (**d**) collisions and interference. However, the problem is not easy to deal with in the case of _partial-overlap_ where \(G_{1}\) and \(G_{2}\) partially overlap (Figure 2b) because of a trade-off between redundancy and reliability. For example, if \(g_{2}\) abandons its transmission after detecting the transmission of the duplicate frame by \(g_{1}\), none of the 2-hop nodes in the area of \(G_{2}-(G_{1}\cap G_{2})\) can receive the frame. Otherwise, if both nodes attempt to transmit an identical frame, all of the 2-hop nodes in the area \(G_{1}\cap G_{2}\) will receive the duplicate frame. Consequently, the suppression of redundant transmission leads to the degradation of reliability in the traffic dissemination, conversely the reliability cannot be improved without the cost of redundancy. This problem becomes more complex as the number of nodes involved in the partial-overlap increases, which typically occurs in flooding. As shown in Figure 2c, \(g_{1}\), \(g_{2}\), and \(g_{3}\) are closely located, which then makes it difficult to determine which node should be allowed or blocked to transmit a frame in a distributed manner. For example, if \((G_{1}\cup G_{3})\supset G_{2}\), it is desirable to allow \(g_{1}\) and \(g_{3}\) to transmit the frame but to restrict the transmission of \(g_{2}\). However, this approach requires the location estimation of the nodes and a signaling mechanism between them, which is difficult to implement without centralized control and incurs a large overhead. Other serious issues of flooding are collisions and interference due to excessive channel accessing. As shown in Figure 2d, a frame transmitted by the source node \(s\) may collide with other frames transmitted concurrently by 1-hop nodes (e.g., \(g_{1},\cdots,g_{4}\)).