OVSF-CDMA Code Assignment in Wireless Ad Hoc Networks

Orthogonal Variable Spreading Factor (OVSF) CDMA code consists of an infinite number of codewords with variable rates, in contrast to the conventional orthogonal fixed-spreading-factor CDMA code. Thus, it provides a means of supporting of variable rate data service at low hardware cost. However, assigning OVSF-CDMA codes to wireless ad hoc nodes posts a new challenge since not every pair of OVSF-CDMA codewords are orthogonal to each other. In an OVSF-CDMA wireless ad hoc network, a code assignment has to be conflict-free, i.e., two nodes can be assigned the same codeword or two non-orthogonal codewords if and only if their transmission will not interfere with each other. The throughput (resp., bottleneck) of a code assignment is the sum (resp., minimum) of the rates of the assigned codewords. The max-throughput (resp., max-bottleneck) conflict-free code assignment problem seeks a conflict-free code assignment which achieves the maximum throughput (resp., bottleneck). In this paper, we present several efficient methods for conflict-free code assignment in OVSF-CDMA wireless ad hoc networks. Each method is proved to be either a constant-approximation for max-throughput conflict-free code assignment problem, or a constant-approximation for max-bottleneck conflict-free code assignment problem, or constant-approximations for both problems simultaneously. The work of Peng-Jun Wan and Xiang-Yang Li is partially supported by NSF CCR-0311174. The preliminary version of the paper first appeared in ACM DIAL M-POMC 2004, workshop of ACM MobiCom 2004.