In OLSR (Optimized Link State Routing Protocol), the multipoint relay mechanism has been introduced to minimize routing overhead for flooding control traffic. In order to achieve as low a routing overhead as possible, the selection of MPRs (multipoint relays) is designed to limit the overall number of such relays in the network. OLSR provides the shortest paths in terms of hops; however, it does not take into account the QoS (quality of service) requirements. Therefore, QOLSR (Quality OLSR), which adds a QoS extension to the OLSR, has been proposed. Although QOLSR provides the best QoS path, its selection process does not consider the number of MPRs, which causes an increase in the routing overhead. In this paper, we focus on the selection process of MPRs in link state QoS routing protocol. We propose three heuristics for high-efficiency selections: MIMS, MQES, and MCIS. The basic approach of these selections is to determine a smaller set of MPRs that provide better QoS paths between any two nodes. The main objective in doing so is to maximize the QoS effect while limiting the routing overhead. In addition, we evaluate the performance of the routing protocols with the proposed selections by simulation. The results indicate that MIMS and MCIS achieve high-efficiency selection; as compared to QOLSR, MIMS reduces the maintenance cost by 30%, while the throughput of the resultant path is decreased by 13%, and MCIS reduces the cost by 21% without any decrease in the throughput.