## 4 Proposed Scheme
### Exploiting Overhearing  
Since the wireless channel is a shared medium, every transmission is in fact a broadcast. For a node with a close by transmitter, there is a chance of overhearing the transmitted packet even though the node is not the intended receiver. Overhearing is useful since such opportunity is obtained without contention, however a sensor can suppress transmission of unnecessary data. The scheme operates as follows. Similar to selective forwarding every sensor stores the maximum score up to current frame. Let us denote the maximum among all the score received/forwarded at Sensor \(i\) up to time \(t\in\mathbb{Z}_{+}\) again by \(z_{i}(t)\). If Sensor \(i\) overhears data \(z\) that is greater than \(z_{i}(t)\) at frame \(s\), the sensor can _update_\(z_{i}(s)\) to \(z\). Note such update increases \(z_{i}(\cdot)\), which increases the chance of discard unnecessary data using selective forwarding. Thus exploiting overhearing is a _complementary_ scheme to selective forwarding. Figure 4: Procedure for selective forwarding. The data (score) of the received packet is denoted by \(z\). Figure 5: An example of selective forwarding. Overhearing may not be always possible even though there is ongoing transmission by a neighboring sensor. The overhearing opportunity is affected by concurrent transmissions of other neighboring sensors, interference, _etc._ Given a set of transmitting sensors in the network, the set of nodes which can successfully overhear nearby transmission varies with the interference model used. The following is the condition under which overhearing is allowed in our node-exclusive interference model. Consider a transmitting sensor \(i\) and the set of neighboring sensors denoted by \(N(i)\). Any \(v\in N(i)\) can overhear \(i\)'s transmission if \(v\) is neither transmitting nor receiving at the same frame. The condition is from the limitation that in node-exclusive interference model, nodes cannot transmit and receive simultaneously. Note in other interference models such as two-hop interference model which is suitable for modeling IEEE 802.11 DCF (Distributed Coordination Function), one can find similar conditions for overhearing. Figure 6 illustrates an example of overhearing. There are four sensors with ID 1,2,3 and 4. The packet contains data with a format \((i,y_{i})\) where \(i\) is sensor ID and \(y_{i}\) is the score. At frame \(k\), Sensors 2 and 3 contended for transmission to Sensor 1, and Sensor 3 won frame \(k\). Thus Sensor 3 transmitted the packet with data \((3,0.9)\) to Sensor 1, while Sensor 2 waits for the next frame. At frame \(k+1\), Sensor 1 forwards the data \((3,0.9)\) to its parent, Sensor 4. Sensors 2 and 3 are assumed to be idle, _i.e._, neither transmitting or receiving at frame \(k+1\), which means they are eligible for overhearing the packet containing \((3,0.9)\) transmitted by Sensor 1. Having overheard data that is greater than the current data to transmit, Sensor 2 updates \(z_{2}(k+1)\) to 0.9. Since there is no need to forward (2,0.7) to Sensor 1, Sensor 2 remains idle at frame \(k+2\). Now suppose Sensor 2 had a child node. If Sensor 2 had been receiving data from its child sensor at frame \(k+1\), it would not have been able to overhear Sensor 1's transmission, e.g., see the rightmost of Figure 6. In that case Sensor 2 might have transmitted at frame \(k+2\). In general the graph describing the data gathering tree may not be the same as the node adjacency graph. Namely there can be a node adjacency graph \(\hat{\mathcal{G}}\) such that the data gathering tree \(\mathcal{G}\) is a subgraph of \(\hat{\mathcal{G}}\). This implies that there may be further possible overhearing opportunity in the network other than that resulting from data gathering tree. For example, in Figure 6, Sensors 2 and 3 may be adjacent nodes in \(\hat{\mathcal{G}}\), although such relation is not specified in the forwarding graph \(\mathcal{G}\). When the node adjacency graph is dense the network is a rich environment for overhearing.