## 1 Introduction  
In the last decade, wireless sensor networks (WSNs) have been growing rapidly in various applications. Significant effort has been made in both academia and industry to meet the vision of a sensor-rich world [1-4]. Wireless sensor nodes equipped with sensing, computing, and communication capacities are now available. Typical examples include UC Berkeley's Telos and Mica family, CMU's FireFly, Intel's IMote2, Sun's SPOT, UCLA's Medusa, and MIT's \(\mu\)AMPS. Commercial sensor node products and solutions are also offered by many vendors, e.g., Crossbow, Rockwell, MicroStrain, Ember, Sentilla, and Dust Networks. While their physical sizes continue to decrease, these sensor node products are becoming cheaper and more powerful than ever. The availability of these products makes it possible to deploy WSNs at a large scale and a low cost that were impractical or even unimaginable just a few years ago. WSNs are typically used for information gathering in applications like habitat monitoring, military surveillance, agriculture and environmental sensing, and health monitoring. The primary functionality of a WSN is to sense and monitor the state of the physical world. In most cases, they are unable to affect the physical environment. However, in many applications, observing the state of the physical system is not sufficient, it is also expected to respond to the sensed events/data by performing corresponding actions on the system. This stimulates the emergence of wireless sensor/actuator networks (WSANs) [5,6]. Featuring coexistence of sensors and actuators, WSANs enable the application systems to sense, interact, and change the physical world. They can be deployed in lots of applications such as disaster relief, planet exploration, intelligent building, home automation, industrial control, smart spaces, pervasive computing systems, and cyber-physical systems. Real-world WSAN applications have their requirements on the quality of service (QoS). For instance, in a fire handling system built upon a WSAN, sensors need to report the occurrence of a fire to actuators in a timely and reliable fashion; then, the actuators equipped with water sprinklers will react by a certain deadline so that the situation will not become uncontrollable. Both delay in transmitting data from sensors to actuators and packet loss occurring during the course of transmission may potentially deteriorate control performance of the system, and may not be allowed in some situations where the systems are safety-critical. In a smart home, although there is no hard real-time constraint, actuators should turn on the lights in a timely fashion once receiving a report from sensors when someone enters or will enter a room where all lights are off; people would get unsatisfied if kept staying in dark for a long time waiting for lighting. In practice, QoS requirements differ from one application to another; however, they can be specified in terms of reliability, timeliness, robustness, trustworthiness, and adaptability, among others. Some QoS metrics may be used to measure the degree of satisfaction of these services. Technically, QoS can usually be characterized by, e.g., delay and jitter, packet loss, deadline miss ratio, and/or network utilization (or throughput) in the context of WSANs. Meeting QoS requirements in WSANs is difficult [2,7]. Some major challenges are described as follows. 1. WSANs are normally resource constrained. Sensor nodes are usually low-cost, low-power, small devices equipped with limited data processing capability, transmission rate, energy, and memory. Due to the limitation in transmission power, the available bandwidth and the radio range of the wireless channel are also limited. For instance, the MICAz more from Crossbow,one of the most widely-used sensor nodes, supports a data rate up to 250 kbps, which is among the highest data rates available today.