Sensor fusion and virtual sensors have been extensively used in applications requiring the use of high-level abstract information derived from multiple sensory inputs, ranging from defence systems to intelligent environments. In this paper, we present distributed mechanisms for enabling virtual sensors in intelligent environments using service oriented sensor networks (SOSNs). A SOSN brings the concept of service-oriented architecture (SOA) into the sensor network domain, where each sensor is represented as a software service. A SOSN enhances the programmability of sensor networks by decoupling sensor deployment from application development and allows applications to dynamically discover, access and compose sensor services. In our previous work, we had proposed a framework model running inside the service layer of a SOSN for querying virtual data and on-demand creation of virtual sensors. However, the service layer of a SOSN is centralized and this leads to scalability and latency issues in large scale deployments. In this paper, we address the issues of scalability and latency and propose distributed algorithms for in-network creation and execution of virtual sensors. We also present mechanisms for monitoring data quality and provide fault tolerance techniques utilizing sensor-based approximation for coping with the loss of multiple physical sensors. These algorithms not only allow us to reap the benefits of SOSNs but also prevent potential scalability and latency issues. We also show through simulation experiments that our mechanisms require minimal involvement of the service layer and result in significantly lower latency and energy consumption as compared to the centralized stream-based approach.