Prefix-Free Vertex Coloring for Channel Assignment in OVSF-CDMA Wireless Ad Hoc Networks

正交可变扩频因子（OVSF）码为CDMA无线系统提供了一种以低硬件开销支持可变速率数据业务的方法。在OVSF-CDMA无线自组织网络中，码分配必须是无冲突的，即，当且仅当两个节点都不在另一个节点的传输范围内并且没有其他节点位于它们的传输范围的交叉点时，可以为两个节点分配相同的码字或两个非正交码字。在这个方案中，我们提出了在OVSF-CDMA无线ad hoc网络中无冲突信道分配的各种优化问题，所提出的研究包括最大吞吐量的无冲突信道分配，最大瓶颈速率的无冲突信道分配，以及在所有节点都有指定的传输速率时，最小调度持续时间的传输调度。所有这些优化问题都是NP难的，即使所有的节点都有均匀的传输半径。我们将证明这些问题的NP-困难性和可发展的多项式时间近似算法。这些研究对OVSF-CDMA无线自组网的部署具有理论挑战性和实际意义。此外，由于无线广告网络支持与救灾、公共事件协调以及军事和执法行动相关的应用，因此增加其吞吐量和通信瓶颈具有巨大的社会影响。

Orthogonal variable spreading factor (OVSF) code provides a means ofsupport of variable rate data service at low hardware cost in CDMAwireless systems. In an OVSF-CDMA wireless ad hoc network, a codeassignment has to be conflict-free, i.e., two nodes can be assigned thesame codeword or two non-orthogonal codewords if and only if neither ofthem is within the transmission range of the other and no other node islocated in the intersection of their transmission ranges. In thisproposal, we propose to study various optimization problems onconflict-free channel assignments in OVSF-CDMA wireless ad hoc networks.The proposed studies include conflict-free channel assignment for maximumthroughput, for maximum bottleneck rate, and for both at the same time,and transmission scheduling for minimum schedule duration when all nodeshave specified transmission rate. All these optimization problems areexpected to be NP-hard even when all nodes have the uniform transmissionradii. We will prove the NP-hardness of these problems and developprovably good polynomial-time approximation algorithms. These studies areboth theoretical challenging and practical important for the deployment ofOVSF-CDMA wireless ad hoc networks. Furthermore, since wireless ad hocnetworks support applications related to disaster relief, public eventcoordination, and military and law enforcement operations, increasingtheir throughput and communication bottleneck has vast societal impact.