We assume a set of cognitive relay nodes that assists both primary and secondary transmissions in a time-slotted cognitive radio networks. To regulate the channel access of the various nodes in the network, we propose an overlapped spectrum sensing strategy for channel sensing, where the secondary source node senses the channel from the beginning of the time slot and the cognitive relay nodes sense the channel for double the sensing time used by the secondary source node to detect the activities of both the primary and secondary source nodes. Hence, the secondary source node has an intrinsic priority over the relay nodes. The relay nodes help both the primary user and the secondary user to deliver their unsuccessfully decoded packets at their destinations. In a given time slot, the scheduled relay node for data transmission starts its transmission when both the primary and secondary users are sensed to be inactive (i.e. have no data to transmit). We propose two optimization-based formulations with quality-of-service (QoS) constraints involving average queueing delay and average service rate requirements. We investigate both cases of perfect and imperfect spectrum sensing. To further enhance the users' QoS requirements, we propose three packet decoding strategies at the relay nodes and compare their performance. We derive an upper bound on the secondary queue average service rate to determine which decoding strategy can achieve that bound. Our numerical results show the benefits of relaying and its ability to enhance the performance of both the primary and secondary users. Moreover, the performance of the proposed schemes is close to the derived upper bound.