A method and system for allocating a channel are provided in a communication system including a plurality of Mobile Stations (MSs) and Base Stations (BSs) for providing a communication service to the plurality of MSs. A BS transmits an average Channel Quality Information (CQI) request to MSs. The MSs measure CQI with respect to their channels in response to the request from the BS, compute average CQI from the measured CQI, and transmit the average CQI to the BS. The BS selects a predefined number of MSs according to the average CQI received from the MSs and sets an MS group. The BS transmits a CQI request to the MS group. The MSs of the MS group transmit the CQI to the BS. The BS receives the CQI from the MS group and allocates a channel according to the CQI.