## 1 Introduction
Designing QoS provisioning routing protocols that enable multimedia and QoS-demanding applications and services is an emerging field of research. Currently available QoS provisioning routing protocols follow a self-serving approach to find and select an end-to-end routing path that fulfills the QoS requirements of multimedia applications [12].Therefore, in QoS provisioning routing bandwidths, delays, and Packet Loss Ratio (PLR) are not only the multimedia application requirements, but they are also being used as default routing parameters [13]. Moreover, link quality metrics e.g., Expected Transmission Count (ETX), per-hop Round Trip Time (RTT), and per-hop Packet Pair delay (PktPair) are a few better known greedy parameters that also used in QoS provisioning routing. QoS provisioning routing protocols that are based on stated parameters adopt greedy selection mechanisms and create a network resource underutilization problem. In a resource underutilization problem, abundant multimedia traffic flows follows distinct routing paths and network resources (e.g., router buffer, data channel) over those routing paths may not be shared by other multimedia traffic flows. Thus, the allocated bandwidth will not be effectively utilized, which causes a resource wastage problem and results in high network deployment costs. Network congestion in wireless and mesh networks has been studied extensively in the literature [14; 15; 16; 17], however to the best of our knowledge QoS provisioning routing-based resource underutilization has not been addressed. The ideal deployment of WMNs requires conducting detailed site surveys to find the appropriate locations before the actual placement of the Wireless Mesh Routers (WMRs) and communication links. This practice is usually followed in academic test beds, but the practical deployment of WMNs is usually unplanned or random [18; 19]. This makes them easy to deploy and reduces the network administration time, but may lead to the installation of unused physical layer resources (e.g., WMRs, communication links) that cause high deployment and operating costs. For example, if a WMR never routes through one of its neighbors, then that neighbor's link is questionable [20]. For example, if most WMRs are routed through only one or two neighbors, then it might be worth keeping only those neighbors. Although redundancy is one of the core design factors in WMNs, redundancy beyond a specific threshold wastes resources and increases the deployment and operating costs. Moreover, with the increasing bandwidth demands and the scarcity of available frequency spectrum, designing resource-efficient wireless mesh networks is a new challenge [21]. Thus, supporting multimedia applications and services by using minimum physical layer resources with overall low ownership cost is a challenge task. To the best of our knowledge, the resource wastage problem caused by QoS provisioned routing and random deployment of WMNs have not been studied in the literature, hence, it is addressed for the first time in this paper. Our objective is to reconstruct the optimal connected mesh backbone topology with the minimum number of communication links and WMRs that satisfy the given end-to-end QoS demands for multimedia traffic and the identification of extra resources while maintaining redundancy. Designing QoS provisioning routing protocols to support emerging multimedia applications in WMNs is an open issue, and finding a feasible path is an NP-complete problem [22]. To achieve our objective, we first propose an Integer Linear Programming (ILP) based solution to obtain the optimal results; then, we propose a polynomial time heuristic algorithm called Link and Node Removal Considering Residual Capacity and Traffic Demands (LNR-RCTD). The rest of the paper is organized as follows. In Section 2, we discuss an extensive literature survey. Section 3, outlines models, assumptions, and problem formation. The proposed ILP-based solution is presented in Section 4.