Orthogonal variable spreading factor (OVSF) code provides a means of support of variable rate data service at low hardware cost in CDMA wireless systems. 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 neither of them is within the transmission range of the other and no other node is located in the intersection of their transmission ranges. In this proposal, we propose to study various optimization problems on conflict-free channel assignments in OVSF-CDMA wireless ad hoc networks. The proposed studies include conflict-free channel assignment for maximum throughput, for maximum bottleneck rate, and for both at the same time, and transmission scheduling for minimum schedule duration when all nodes have specified transmission rate. All these optimization problems are expected to be NP-hard even when all nodes have the uniform transmission radii. We will prove the NP-hardness of these problems and develop provably good polynomial-time approximation algorithms. These studies are both theoretical challenging and practical important for the deployment of OVSF-CDMA wireless ad hoc networks. Furthermore, since wireless ad hoc networks support applications related to disaster relief, public event coordination, and military and law enforcement operations, increasing their throughput and communication bottleneck has vast societal impact.
