Various criteria have been considered in the literature for selection of optimal sensor networks. Amongst these, maximization of network reliability is an important criterion. While there are several approaches for designing maximum reliability networks, uncertainty in the available sensor reliability data has not been considered in these designs. In this article we present two novel formulations that incorporate robustness to uncertainties in the reliability data. Towards this end the sensor network design problem for maximizing reliability is formulated as explicit-optimization (MINLP) problem using failure rates of sensors which have better scaling properties instead of sensor reliabilities. Constraint programming (CP) has been used for solving the resulting optimization problems. Use of CP also enables easy generation of pareto front characterizing trade-offs between performance, cost and robustness for various uncertainty scenarios. The utility of the proposed approach is demonstrated on a case study taken from the literature. (C) 2008 Elsevier Ltd. All rights reserved.