## Retrieval of the Extreme Values under Deadline Constraints in Wireless Sensor Networks
To deal with such heterogeneity we will introduce a _score_ system which provide a unified measures of the 'urgency' of a data sample. Specifically a score represents how much the associated data sample is _deviated_ from its usual distribution. Thus the objective is in fact to retrieve the data with the maximum _score_, _i.e._, the data sample that exhibits the highest degree of 'abnormality'. The details are explained in Section 3. We consider a network such that data is collected in a multi-hop manner through a tree topology. The sink is located at the root of the tree. The goal for the sink is to retrieve the extreme data through the tree, and the data gathering tree is assumed to be given. The data collection is initiated at an instant which is not known beforehand. Every sensor begins forwarding a data sample to the sink at the instant. Latency is defined to be the time between the initiating instant and the retrieval of the extreme value among data samples at the sink. We want the latency to meet the deadline requirement. Since the sink only needs to compute the extreme value, there can be substantial redundancy in the traffic generated by the network. If every sensor were to forward every generated reading to the sink, it would incur significant latency and energy consumption. As will be detailed later, a certain class of \(f(\cdot)\) allow the data to be combined in the intermediate nodes along the route. For such class of \(f(\cdot)\), max being in the class, intermediate combining of data do not alter the final \(f(\cdot)\) computed at the sink. A collective term for the intermediate aggregation and combining techniques is _in-network aggregation_[2; 3; 4]. A survey on in-network aggregation techniques is provided in [5]. We propose a scheme for latency reduction based on priority-based medium access and data combining. The scheme consists of the following three schemes. The first scheme focuses on the medium access aspects. In our model the sensors contend for channel access in a fully distributed manner. Multiple requests for a single time resource result in a collision. Since the network traffic needs to be aggregated to the sink in a short time, the traffic is bursty in time and space. Thus it is crucial to resolve contention in an efficient way. Intuitively it is preferable to give high priority of channel access to sensors having 'large' data values, since we wish the maximum data to arrive at the sink as early as possible. We propose a scheme to implicitly assign such priority by means of randomized back-off which is controlled based on how 'large' the data value is. We observe that there exists a trade-off between priority assignment and channel contention. If the priority assignment is highly biased towards a certain class of sensors, it may restrict resource for other classes of sensors. In situations where a number of sensors with restricted resource have to compete, a collision can occur with high probability. Conversely if we treat all the nodes equally, the number of collisions can be reduced, however there will be no gains in latency reduction from prioritizing the nodes with large data values. A contention resolution scheme capturing this aspect is proposed in Section 4. The second scheme is called _selective forwarding_, and third scheme is to exploit _overhearing_ other transmission. These schemes attempt to suppress unnecessary traffic by leveraging the property of the objective max function as follows. Suppose a node receives a packet to be forwarded to the next hop. If any of the previous packets this node has forwarded/received contain a data value _greater_ than that of the current packet, the packet is of no use to the sink. Thus this forwarding request can be ignored, which reduces traffic. The overhearing technique exploits the broadcast property of wireless transmission, and the similar principle to that of selective forwarding is applied in order to further decrease traffic. When the three schemes are combined, a synergistic effect in latency reduction is observed.