An orthogonal multiple access coding scheme

Consider a collection of unsynchronized, half-duplex wireless nodes, communicating over a shared spectrum with local affine clocks. The clocks are unsynchronized in the sense that they do not tick at the same rate, called skew, and have different offsets. The nodes also do not know each others rates or offsets. In order for this collection of wireless nodes to even begin to perform any coordinated activity the nodes must first have the fundamental capability to communicate reliably in the presence of half-duplex constraints as well as packet collisions which occur when two or more nodes simultaneous transmit to a common receiver. Both scenarios are also known as primary and secondary conflicts, respectively. We present an orthogonal MAC code that allows any pair in this collection to exchange a message of size $W$ within a bounded time, subject only to the restriction that the ratios of skews have a known upper bound. The orthogonal MAC code described and proved to function in this paper is an essential part of a larger protocol suite. The larger protocol suite addresses the problem of enabling a collection of unsynchronized, half-duplex wireless nodes to also form a fully functioning and indeed optimized wireless network even while under attack from any subset of unknown malicious agents.

Full Text (PDF format)

Published 18 March 2013