Due to advances in nanotechnology, miniaturized, low-cost, low-power devices - referred to as sensors, integrating sensing, computing, and wireless communications capabilities have become reality. The main goal of a wireless sensor networks (WSN) is to produce meaningful information from raw local data collected by individual sensors. This goal must be achieved while ensuring that the WSN continues to provide, for extended periods, timely and accurate information in the face of security attacks and hardware failures. Indeed, this article introduces a simple and natural general-purpose virtual infrastructure for WSNs consisting of massive deployment of anonymous sensors. The second main contribution of this article is to show that several protocols ranging from routing to data aggregation to security can leverage this virtual infrastructure. A companion paper shows that the virtual infrastructure can be established in a lightweight fashion and is highly dynamic, adapting to changing network conditions.