Enabling short fragments for uncoordinated spread spectrum communication

Uncoordinated spread spectrum (USS) protocols have been proposed for anti-jamming communication in wireless settings without shared secrets. The existing USS protocols assume that fragments of hundreds of bits can be transmitted on different channels in order to identify fragments that belong to the same message. However, such long transmissions are susceptible to reactive jamming. To address this problem, we present a protocol that allows the use of short fragments of a few bits only. This makes our scheme resilient to a large class of reactive jammers. We prove that reassembling the fragmented message is not only feasible but also efficient: it can be completed in polynomial time in the size of the message, even if the jammer is computationally resourceful. We demonstrate the protocol efficiency by simulating the reassembly process at the link layer under different design parameters.