In cognitive radio cellular networks (CogCells), primary users (PUs) rarely utilize all the assigned frequency bands at a certain time and a location. The spectral inefficiency caused by the spectrum holes motivated cognitive radio technology (CR) that presents unlicensed secondary users (SUs) an opportunity for using spectrum holes. CR makes the SUs to find and use the spectrum holes without interrupting the operation of PUs. The SUs are allowed to access the channel licensed to the PUs which consist of primary transmitters (PTs) and primary receivers (PRs) when the interference to the PRs is less than acceptable value (i.e., predefined system threshold), and the quality of service (QoS) required by PTs are also guaranteed. According to different levels of QoS required by SUs, the network operator can achieve different secondary revenues by providing different QoS levels to SUs. Due to the high density, the mobility of SUs, the interference limitation at PRs and the QoS requirements from PTs, not all SUs can be supported. The problem we investigated in this paper is to select the maximum subset of SUs to maximize the total secondary revenue of the CogCell, meanwhile the QoS requirements from both PTs and admitted SUs must be guaranteed. Moreover, the interference caused by the admitted SUs and the PTs at the PRs (due to access the same channel) has to be less than the predefined system threshold. In this paper, we formulate such a joint QoS-aware admission control, channel assignment, and power allocation scheme as a non-linear NP-hard optimization problem. This is a very challenging problem and the NP-hardness has been shown in the literature even for the single-channel scenario. In this paper, we propose a new polynomial-time joint QoS-aware admission control, channel assignment and power allocation scheme which has a approximation guarantee, e.g., the total secondary revenue achieved by our algorithm is at least of the optimum, where nr p is the number of PRs and nw is the number of available channels in the CogCell. Note that Our algorithm also significantly improves the current best known solution with a approximation guarantee for the single-channel scenario [11]. In this paper, we also propose a greedy heuristic approximation algorithm and an exact solution. The simulation results show that the approximation algorithms we proposed can achieve significantly higher secondary revenue than the currently best known approximation approach for this problem, an extension of the minimal SINR removal algorithm in [15]. Indeed, quite surprisingly, the simulation results also demonstrate that the secondary revenue achieved by our approximation approaches is very close to the optimum in practice, specially for the approximation algorithm.