The deployment of an adequate number of Relay Stations (RS) at proper sites will improve the network connectivity and energy consumption, which are the major requirements of next-generation networks. In this paper, an efficient four-stage uniform clustering scheme is proposed, which identifies the sites for Base Station (BS) and RS deployment from the available candidate sites. This paper considers uniform clustering based deployment as the base and tries to improve its performance by addressing the solutions to its pitfalls. Uniform clustering based deployment and throughput oriented path selection schemes are combined in this work, which maximizes the reach to destination without compromising the Quality of Service (QoS) even under link overloading conditions. The simulations are repeated for various network dimensions and the results show that the proposed scheme offers improved throughput and coverage ratio performances over the traditional Joint BS and RS placement (JBRP), Adaptive Cost based RS Deployment (ACRD), uniform clustering and fuzzy logic based schemes even under link overloading conditions without demanding additional cost. © School of Engineering, Taylor's University.