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

点击翻译按钮获取中文摘要

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.