## 2 Preliminaries
### Motivation  
A simple flooding (_Flooding_) achieves high reliability in message delivery by allowing a node to have multiple chances of receiving or overhearing a broadcast message; however, it suffers from high-energy consumption. Let \(AAT(X)\) denote the _average active time_ per each node with protocol \(X\). In Flooding, each node remains active for half of the _broadcast period_ (\(BP\)) on average since it goes to sleep immediately after rebroadcasting a received message. Furthermore, when \(len(BS)\) denotes the time length of \(BS\), every node takes \(len(BS)\) approximately for rebroadcasting. Thus, we get:  
\[AAT(Flooding)=\frac{BP}{2}+len(BS)=(1+\frac{H}{2})\times len(BS) \tag{1}\]where \(BP=H\times len(BS)\) when \(H\) is the depth of a tree in a tree-based protocol. Glossy [4] reduced \(BP\) by having a node rebroadcast a message immediately after it receives the message. A reliable slotted broadcast protocol (RSBP) using a tree topology [14] optimizes energy consumption such that every internal node remains active only during two \(BSs\), one to receive and another to rebroadcast a message, and a leaf node remains active for one \(BS\) to receive the message. Suppose that \(r\) denotes the ratio of leaf nodes in a given tree. Then, we get:  
\[AAT(RSBP)=(1-r)\times 2\times len(BS)+r\times len(BS)=(2-r)\times len(BS) \tag{2}\]  
However, the reliability is vulnerable to even the failure of a single link that may occur frequently in harsh industrial environments. For example, the failure of a node to receive a message can cause a chained failure such that all its descendants miss the message. In addition, a slot schedule has to be regenerated with the change of topology. To tackle the weaknesses of Flooding and RSBP, we proposed a _slotted sense multiple access broadcast_ (SSMAb) protocol [16] in which _multiple nodes_ at the same tree level _compete_ for broadcasting within the _broadcast sharable slot_ (\(BSS\)) allocated to the tree level such that a node _senses a channel_ and rebroadcasts a message only if the channel is idle. This approach still suffers from message collision and energy management within \(BSS\). The original SSMAb can be improved by employing the notion of the slotted Aloha [17] since the broadcasting within one \(BSS\) is similar to data transmission in satellite networks except that a node knows its children and can sense the broadcast signal of its neighbors. Thus, as shown in Figure 1, a \(BSS\) is divided into multiple \(BSs\) and a node is allowed to start rebroadcasting only at the boundary of \(BS\). However, the hidden nodes can still be problematic. Figure 1 illustrates two cases for the effect of a hidden node c: Case (a) that the broadcast of node \(a\) overlaps with that of node \(c\) and case (b) that the broadcast of node \(b\) overlaps with that of node \(c\). In case (a), if node \(f\) fails to receive a message due to collision, fortunately it can be covered by node \(b\). In case (b), if nodes \(f\), \(g\), and \(h\) fail to receive the message, nodes \(g\) and \(h\) cannot be covered by another node, \(a\). To resolve this problem, we devised a \(BS\) scheduling algorithm in which _every node allocates a distinct \(BS\) to each of its children_. This implies that if nodes \(b\) and \(c\) have the same parent, they will be assigned different \(BSs\), thereby preventing case (b). However, it is still possible that if two or more hidden nodes have different parents, they can be assigned the same \(BS\). We do not provide a scheme to handle this problem in the \(BS\) scheduling algorithm. If that happens, the nodes that fail to receive a message due to collision have to rely on the possibility of being covered by another node as explained above. Let \(len(BSS)\) be the time length of a \(BSS\). Then, \(AAT(SSMAb)\) is given as follows:  
\[ \begin{array}{ll}AAT(SSMAb)&=\max(\frac{len(BSS)}{2},\ len(BS))+[(1-r)\times len (BS)+r\times 0]\\ &=\max(0.5\times len(BSS),\ len(BS))+(1-r)\times len(BS)\end{array}