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

正交可变扩频因子(OVSF)码在cdma无线系统中提供了一种以低硬件成本支持可变速率数据业务的手段。在OVSF-CDMA无线自组织网络中，码分配必须是无冲突的，即当且仅当两个节点都不在另一个的传输范围内并且没有其他节点位于它们的传输范围的交点时，两个节点可以被分配相同的码字或两个非正交码字。在该方案中，我们研究了OVSF-CDMA无线自组网中无冲突信道分配的各种优化问题，包括最大吞吐量、最大瓶颈速率和两者同时存在的无冲突信道分配，以及当所有节点都具有指定的传输速率时，针对最小调度持续时间的传输调度。即使当所有节点的传输半径相同时，所有这些优化问题也是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.