The inherent properties of ad hoc networks such as limited energy, short transmission range and absence of routers along with node mobility, node failures and link failures make routing a challenging task. In order to facilitate routing, virtual backbone has been proposed as a viable solution in the literature. Optimize Link State Routing (OLSR) protocol, a proactive routing protocol, uses Multipoint Relay (MPR) set to construct virtual backbone. Prior research has, however, identified various issues with the MPR selection scheme that needs improvement. One of the alternatives that could be used to construct virtual backbone is Connected Dominating Set (CDS). Although CDS generates a smaller virtual backbone, its 1-connected 1-domination nature may render a virtual backbone obsolete in case of networks which witness frequent node mobility, node failures and link failures. To overcome this, k-Connected m-Dominating CDS (kmCDS) could be used to construct fault- tolerant virtual backbone structure. In this direction, the present paper proposes a Fault-Tolerant Improved Optimized Link State Routing (FT-IOLSR) protocol that uses kmCDS to form fault-tolerant virtual backbone, effectively replacing the MPR set of OLSR protocol. Simulations are carried out to assess the performance of the FT-IOLSR protocol in relation to the OLSR protocol, with respect to various node speed and pause time combinations, and varying network size. The results show that the FT-IOLSR protocol is better in terms of packet delivery ratio under varying mobility and varying network size. Also it has been observed that, with increase in k-connectivity and m-domination factor, there is improvement in the performance of the protocol.