## 3 SSMA Broadcast Protocol
### Broadcast Approaches
#### 3.3.3 Slot-Scheduled Contention-Based Transmission  
**a. Slot scheduling**  
Figure 4: An example of a broadcast process between two neighboring nodes. In SSCBT, a node uses a BS scheduling algorithm that assigns a BS number to each of its children. Suppose that node \(i\) has \(m\) children expressed as \(C(i)=(i_{1},\ i_{2},\ldots,i_{m})\) where \(i_{j}\) indicates the \(j^{th}\) child of node \(i\). Given \(BSS=(BS_{1},\ BS_{2},\ \ldots,\ BS_{N})\), node \(i\) produces a \(BS\) schedule, \(S(i)\) for its children set \(C(i)\) as follows:  
\[S(i)=\big{\{}\big{(}i_{j},\ BS_{k}\big{)}\big{|}j=1..m,\ k\text{ { is selected by a BS scheduling Algorithm}},\ 1\leq k\leq N\big{\}}\]  
The schedule \(S(i)\) implies that node \(i_{j}\) is assigned \(BS_{k}\). Node \(i\) includes \(S(i)\) in a message before rebroadcasting it so that each of its children can know its \(BS\) number. ```
//\(N\) = the number of \(BS\)s to be scheduled //\(m\) = the number of children //\(BSN(i)\) = the \(BS\) number assigned to node \(i\)  If \(i\) is a sink then \(S(i)=\left\{\left(i_{j},BS_{k}\right)\middle|k=(j-1)\ mod\ N+1,\ 1\leq j\leq\frac{m}{2}\right\}\cup\) \(\left\{\left(i_{j},BS_{k}\right)\middle|k=\left(j-\left(\frac{m}{2}+1\right)+ \frac{N}{2}\right)\ mod\ N+1,\frac{m}{2}<j\leq m\right\}\) If \(i\) is an intermediate node then \(S(i)=\left\{\left(i_{j},BS_{k}\right)\middle|\ k=(BSN(i)+j-2)\ mod\ N+1,\ 1\leq j\leq m\right\}\)
```  
**Algorithm 1** A broadcast slot (BS) scheduling algorithm  
The BS scheduling algorithm works as follows. A node assigns a \(BS\) number to each of its children sequentially starting with its own \(BS\) number that was assigned by its parent. If a \(BS\) number to be assigned goes over the last one, it goes back to \(BS_{1}\) and continues. If \(N\) is not smaller than \(m\), every child will be assigned a unique \(BS\). However, a sink that has no parent starts the \(BS\) scheduling with the first \(BS\), \(BS_{1}\). Thus, a sink will assign only some \(BS\)s in front to its children, resulting in the unbalanced \(BS\) assignment. To avoid this situation, a sink generates a \(BS\) schedule such that it schedules the first half of children starting with the first \(BS\) and schedules the second half of children starting from the middle of \(BS\)s. For example, suppose that a sink, say 1, schedules \(BSS=(BS_{1},BS_{2},BS_{3},BS_{4},BS_{5})\) for \(C(1)=(1_{1},1_{2},1_{3})\). Then, it schedules the first half (\(1_{1}\)) of children starting with \(BS_{1}\) and the second half (\(1_{2},1_{3}\)) starting with \(BS_{3}\). \(S(1)\) is given as follows:  
\[S(1)=\{(1_{1},BS_{1})\}\ \cup\ \{(1_{2},BS_{3}),(1_{3},BS_{4})\}.\]  
A detailed \(BS\) scheduling algorithm is given in Algorithm 1. The computational complexity of Algorithm 1 is \(\mathrm{O}(m)\) where \(m\leq M\) and \(M\) is the total number of nodes in the considered network. Let us generate a \(BS\) schedule for the tree in Figure 5. First, node 1 (a sink) has three children 2, 3, and 4. Then, the first half of nodes are \(\{2\}\) and the second half of nodes are \(\{3,4\}\). Thus, it assigns \(BS_{1}\) to node 2 and \(BS_{3}\) and \(BS_{4}\) to nodes 3 and 4, respectively, resulting in \(\mathrm{S}(1)=\{(2,\ BS_{1})\), \((3,\ BS_{3})\), \((4,\ BS_{4})\}\). Next, node 2 has one child 5 and starts slot assignment from its own \(BS_{1}\). Thus, it assigns \(BS_{1}\) to node 5, resulting in \(\mathrm{S}(2)=\{(5,\ BS_{1})\}\). Node 3 starts slot assignment from its own \(BS_{3}\) for its three children, resulting in \(\mathrm{S}(3)=\{(6,\ BS_{3})\), \((7,\ BS_{4})\), \((8,\ BS_{1})\}\). Note that \(BS_{5}\) going over the number of \(BS\)s is replaced by \(BS_{1}\). In this way, we get the \(BS\) schedules as shown in Table 1. Note that at tree level 2, hidden nodes 5 and 8 are assigned the same \(BS_{1}\), and hidden nodes 7 and 9 are assigned the same \(BS_{4}\) because they have different parents.