The physical number of sensor nodes constitutes a major cost factor for Wireless Sensor Networks (WSN) deployments. Hence, a natural goal is to minimize the number of sensor nodes to be deployed, while still maintaining the desired properties of the WSN. However, sparse networks even while connected, usually suffer from topology irregularities that negatively impact the network lifetime and responsiveness, i.e., sensor data delivery reliability and latency. In addition, sensor node failures easily complicate/enforce/aggravate these irregularities. Valuable efforts have been conducted to discover topology specific anomalies such as coverage holes or critical/bottleneck nodes. Unfortunately, these efforts suffer from at least one of the following drawbacks: (a) They are centralized and consequently inefficient in large-scale networks, (b) they are tailored to one class of anomalies, or (c) do not propose how to remedy the identified anomaly. In this paper, we focus on sparse WSN which usually show varied topology irregularities and propose an in-network and localized strategy that efficiently (i) discovers generic topology irregularities, and (ii) identifies locations for minimal number of new augmented sensor deployments to remedy topology irregularities and sustain the desired operational requirements. We show the effectiveness and efficiency of the solution through a set of extensive simulations. © 2011 IEEE.