We present novel lower bounds on the mean square error (MSE) of the location estimation of an emitting source via a network where the sensors are deployed randomly. The sensor locations are modeled as a homogenous Poisson point process. In contrast to previous bounds which are a function of the specific locations of all the sensors, we present CRB-type bounds on the expected mean square error; that is, we first derive the CRB on the MSE as a function of the sensors' location, and then take expectation with respect to the distribution of the sensors' location. Thus, these bounds are not a function of a particular sensor configuration, but rather of the sensor statistics. Hence, these novel bounds can be evaluated prior to sensor deployment and provide insights into design issues such as the necessary sensor density, the effect of the channel model, the effect of the signal power, and others. The derived bounds are simple to evaluate and provide a good prediction of the actual network performance.