In this paper, we develop tractable mathematical models and approximate solution algorithms for a class of integer optimization problems with probabilistic and deterministic constraints, with applications to the design of distributed sensor networks that have limited connectivity. For a given deployment region size, we calculate the Pareto frontier of the sensor network utility at the desired probabilities for d-connectivity and k-coverage. As a result of our analysis, we determine (i) the number of sensors of different types to deploy from a sensor pool, which offers a cost vs. performance trade-off for each type of sensor, (ii) the minimum required radio transmission ranges of the sensors to ensure connectivity, and (iii) the lifetime of the sensor network. For generality, we consider randomly deployed sensor networks and formulate constrained optimization techniques in a Bayesian experimental design framework to obtain the best point estimates of a given state-of-nature, represented by a finite number of parameters. The approach is guided and validated using an unattended acoustic sensor network design. Finally, approximations of the complete statistical characterization of the acoustic sensor networks are given, which enable average network performance predictions of any combination of acoustic sensors.