## 4 Localized Query Loss Discovery with Distributed Query Resolution
### Detector Cluster Formation for Localized Query Loss Detection  
The cluster formation algorithm is shown in Algorithm 1.  
```
0: Node ID, attributes, the scope (\(T\)) of random start time
0: Detector cluster
1:\(t\) = current time
2:\(T_{0}=t\)
3: Randomly select a cluster broadcast time \(T_{start}=T_{0}+\textit{Rand}(0-T)\)
4:if\(t=T_{start}\)then
5: Perform 1-hop cluster invitation broadcast with (node ID, location, attributes)
6: Set number of cluster invitation broadcasts = 1
7: Wait {a randomly selected duration, e.g., 10 times of the duration for a round of invitation packet delivery and reply}
8:endif
9:while (the number of replied nodes \(<\) threshold_reply) and (the number of cluster invitation broadcasts \(<\) threshold_invitation) do
10: Receive the neighbor response message of \"join as a detector\", which is sent by unicast from neighbor node with (node ID, location, attributes) information.
11: Increase the number of cluster invitation broadcasts
12: Wait
13:endwhile
14: Perform 1-hop confirmation broadcast with (node ID, cluster size)
```  
**Algorithm 1** Detector Cluster Formation (DCF) Algorithm  
An object node invites its one-hop neighbor node to perform the role of loss detector by broadcasting an invitation message. The broadcast is initiated at a random time to prevent collisions of clustering operations at other object nodes. The nodes that receive the invitation message send a reply of \"join as a detector\" to accept being the object node's detector.  
The invitation message includes node ID, location, and sensing attributes of the object sensor nodes. This message lets neighbor detectors have the information for correlating between a query and the object node. If there are not enough nodes to perform the role of detectors, the object node will initiate the invitation again until there are sufficient detectors or the number of query broadcasts is large enough.  
A cluster of detectors around an object node recognizes the loss of a query at the object node that should respond to it. The query loss is detected based on the judgment of the following two processes:  
1. A detector detects that the query is associated with the object node that it is monitoring. This is realized by a distributed query resolution mechanism at each detector node.
2. The object node does not respond to the query. This information is captured by the detector by receiving or overhearing the wireless transmission of the object node.  
When the above two processes occur, a query loss is detected at a detector.  
**Proposition 1**.: _Sensor nodes can achieve functional fairness with regard to being loss detector and object._  
Proof.: Let a sensor node \(A\) have a set of detectors \(D=\{d_{1},d_{2},\ldots,d_{n}\}\). Since node \(A\) is the neighbor node of each detector \(d_{1},\ldots,d_{n}\), when node \(A\) serves as detector for \(d_{1},d_{2},\ldots,d_{n}\), the function of being detector and object are mutually shared for \(A\) and all nodes in \(D\). In the same way, every sensor node can be a detector of its object and then the network has the functional equality among nodes.  
We summarize the basic procedure of cluster formation as follows. (1) Sensor node \(A\) sends an invitation to its neighbors by broadcast; (2) Neighbor nodes reply with \"join as detector\" by unicast; (3) The node \(A\) sends an ACK to the detectors by broadcast.