## 1 Introduction  
With sensing, computation, and wireless communication capabilities, _wireless sensor networks_ (WSN) enable distributed sensing and processing of natural phenomena applied to areas such as environmental or healthcare monitoring. In a sensor network, a sink node requests data from the sensor nodes by sending queries to them. A query is typically a data-centric operation [1,2] instead of conventional address-centric operations as used in current Internet protocols. For example, a query might be _\"what is the temperature in the geographical region X?\"_ or _\"what is the humidity in region Y?\"_ rather than _\"what is the humidity level at node A?\"_. Nodes with data matching to the query interest will report this information back to the sink node via a multi-hop transmission. However, a query packet may not successfully reach the corresponding sensor nodes that should reply to the query, either due to packet loss in the wireless propagation or sensor nodes being temporarily unavailable. This in turn results in the failure of sensor nodes to report their information correctly to the sink. Since the query does not identify an individual destination node, query loss would lead to the losses of data sources, which may cause a wrong evaluation of the situation in the monitoring region with respect to the query. Many studies on sensor networks assume that the query dissemination process is reliable and focus their discussions on the data collection [3, 4, 5]. This can be a reasonable assumption when the data collection accounts for much more traffic volume than query dissemination or the failures of queries have only little impact on the success of data collection. However, when the queries have a large impact on the network traffic, for example, in case of on-demand queries of sensing data from various end users, retransmission of queries will cause large traffic overhead, and recovering from query losses has an essential impact on the network traffic and energy consumption. The broadcast feature of query message dissemination is a reason that leads to both problems of query losses and the difficulty of their local recovery. Due to the large number of sensor nodes in the network, the broadcast packet collisions cause the loss of query messages. Since a broadcast process does not adopt the confirmation by ACK in the packet delivery in order to avoid ACK storms, it is difficult to enable a local retransmission of query messages at the sensor nodes that lost query messages. There are a number of studies on the improvement of broadcast efficiency with regard to broadcast overhead, energy efficiency, and reliability. These efforts include designing specific structure based broadcast mechanisms including utilizing cluster, tree, or backbone based structures for broadcast [6, 7, 8, 9]. Reducing the redundancy of broadcast has the effect of reducing broadcast collisions. However, these specific structure-based broadcast methods can not completely guarantee to be without loss of broadcast packets, which are caused not only on MAC layer but also on physical layer at small sensor nodes. A further development that does not depend on the network infrastructure is with local queries using NACK at each sensor node [10], leading to distributed and localized discovery of query loss. However,such approaches require the setup of a query sequence. In case the sequence of queries is over a long interval, the discovery and recovery must wait until the new query with a new sequence to judge whether there is a lost sequence number among its received query packets. A straightforward approach is the utilization of the sink node for query loss discovery and recovery since the sink node is the source of the query and also the destination of data collection from the sensors that should respond to that query. To enable sink nodes to detect query losses, they should have the knowledge of which sensor nodes should reply to a query.