## 3 Collision-Free Hybrid MAC Protocol Based on Pipeline Parallel Transmission
### Replication Computation  
Because the source and destination nodes will change in each transmission cycle, the optimization result for data packet scheduling should be known by all source nodes. If the optimization algorithm is carried out by one node, additional overhead is required for broadcasting the optimization result to other source nodes. To reduce the control overhead for data packet scheduling, replication computation technique is employed in this paper.  
Replication computation, also known as redundant computing, is a technique that uses unnecessary and redundant computation to reduce the communication and/or execution time in parallel computing. Figure 5 shows an example of replication computation. In this example, the sum of the two inputs needs to be stored in both node A and node B. In Figure 5a, the sum is first calculated by A, and then passed from A to B. In Figure 5b, the two inputs are first broadcasted to A and B, and then the sum is calculated in both A and B simultaneously. The latter method can omit the communication between A and B in the price of repeating the same computation in B.  
There are several conditions that should be met when applying replication computation to an operation in a parallel process:  
* The input of the operation is variable, or else the output of the operation can be calculated in advance and there is no need for replication computation.
* The output of the operation can be planed or predicted.
* Multiple nodes need to know the output of the operation.  
Figure 5: An example of replication computation. (**a**) common method; (**b**) replication computation.  
The operation can produce the same outputs when the inputs are equal.  
The data transmission scheduling in the proposed protocol has well met the requirements of replication computation. First, the nodes needed to transmit data vary in each transmission cycle. Second, the optimal scheduling can be calculated by an algorithm, which means its output is predictable. Third, all source nodes need to know the scheduling results. Forth, when the scheduling algorithm is deterministic, its can ensure that the same inputs result in the same outputs. Figure 6 shows an implementation of the data packet scheduling with and without replication computation. The conventional method without replication computation is shown in Figure 6, where the information of successful handshakes is first collected by node A, and then node A calculates the optimal scheduling result and broadcasts it to the other nodes. Figure 6 shows the scheduling with replication computation, where the information of successful handshakes is collected by all nodes, and then each node calculates the scheduling result using the same deterministic algorithm. Note that in Figure 6, the broadcasting ensures that the scheduling algorithms in all nodes have the same inputs so that they can generate the same outputs, i.e., the same transmission schedules. It can be seen that by using replication computation, the data packet scheduling can be implemented via a two-way handshake, which is the simplest form of the handshaking protocol and has the least overhead.