High availability is one of the important requirements of many end-to-end services in the Internet of Things (IoT). This is a critical issue in network function virtualization (NFV) and NFV-enabled service function chaining (SFC) due to hard- and soft-ware failures. Thus, merely mapping primary VNFs is not enough to ensure high availability, especially for SFCs deployed over fog - core cloud networks due to resource limitations of fogs. As a result, additional protection schemes, like VNF redundancy deployments, are required to improve the availability of SFCs to meet predefined requirements. With limited resources of fog instances, a cost-efficient protection scheme is required. This paper proposes a cost-efficient availability guaranteed deployment scheme for IoT services over fog-core cloud networks based on measuring the improvement potential of VNFs for improving the availability of SFCs. In addition, various techniques for redundancy placement for VNFs at the fog layer are also presented. Obtained analysis and simulation results show that the proposed scheme achieves a significant improvement in terms of the cost efficiency and scalability compared to the state-of-the-art approaches.