On network-coded rateless transmission: Protocol design, clustering and cooperator assignment

We propose a new transmission protocol for two-hop transmission employing rateless coding in the first hop and rateless-network coding in the second hop. In this protocol, communicating pairs (CP) and also relays are partitioned into small clusters; afterwards, each CP-cluster is assigned one relay cluster to improve data transmission. This scheme increases the diversity order (in comparison to the case where each CP exploits its own relay resources with no cooperation), without increasing the transmission cost (such as delay or energy), provided that the clustering-assignment form is optimized. We show that finding the optimal clustering-assignment (in the sense of cost minimization) boils down to the cascade of two graph-theoretic problems, namely graph partitioning and weighted matching, which can be solved efficiently. Moreover, we model the delay as cost, and analyze the expected transmission time. Numerical analysis demonstrates the effectiveness of our approach.