Embodiments of a base station and methods for allocating uplink bandwidth using SDMA are generally described herein. In some embodiments, uplink bandwidth request messages are received on a bandwidth request contention channel from one or more subscriber stations. The uplink bandwidth request messages are generated by the subscriber stations by modulating pilot subcarriers of a randomly selected disjoint pilot pattern with a randomly selected orthogonal sequence. The base station allocates uplink bandwidth to the subscriber stations when the uplink bandwidth request messages are successfully detected and decoded. The base station uses an SDMA technique to determine channel responses based on the orthogonal sequences to detect and decode the uplink bandwidth request messages.