This paper studies the noncausal relay channel, also known as the relay channel with unlimited look ahead, introduced by by El Gamal, Hassanpour, and Mammen. Unlike the standard relay channel model, where the relay encodes its signal based on the previous received output symbols, the relay in the noncausal relay channel encodes its signal as a function of the entire received sequence. In the existing coding schemes, the relay uses this noncausal information solely to recover the transmitted message or part of it and then cooperates with the sender to communicate this message to the receiver. However, it is shown in this paper that by applying the Gelfand-Pinsker coding scheme, the relay can take further advantage of the noncausally available information and achieve rates strictly higher than those of the existing coding schemes. This paper also provides a new upper bound on the capacity of the noncausal relay channel that strictly improves upon the existing cutset bound. These new lower and upper bounds on the capacity coincide for the class of degraded noncausal relay channels and establish the capacity for this class.

We consider the problem of routing packets across a multi-hop network consisting of multiple sources of traffic and wireless links while ensuring bounded expected delay. Each packet transmission can be overheard by a random subset of receiver nodes among which the next relay is selected opportunistically. The main challenge in the design of minimum-delay routing policies is balancing the trade-off between routing the packets along the shortest paths to the destination and distributing the traffic according to the maximum backpressure. Combining important aspects of shortest path and backpressure routing, this paper provides a systematic development of a distributed opportunistic routing policy with congestion diversity (D-ORCD). D-ORCD uses a measure of draining time to opportunistically identify and route packets along the paths with an expected low overall congestion. D-ORCD with single destination is proved to ensure a bounded expected delay for all networks and under any admissible traffic, so long as the rate of computations is sufficiently fast relative to traffic statistics. Furthermore, this paper proposes a practical implementation of D-ORCD which empirically optimizes critical algorithm parameters and their effects on delay as well as protocol overhead. Realistic QualNet simulations for 802.11-based networks demonstrate a significant improvement in the average delay over comparable solutions in the literature.

We consider the problem of noisy Bayesian active learning where we are given a finite set of functions H, a sample space X , and a label set £. One of the functions in H assigns labels to samples in X . The goal is to identify the function that generates the labels even though the result of a label query on a sample is corrupted by independent noise. More precisely, the objective is to declare one of the functions in H as the true label generating function with high confidence using as a few label queries as possible, by selecting the queries adaptively and in a strategic manner. Previous work in Bayesian active learning considers generalized binary search and its variants for the noisy case, and analyzes the number of queries required by these sampling strategies. In this paper, we show that these schemes are, in general, suboptimal. Instead we propose and analyze an alternative strategy for sample collection. Our sampling strategy is motivated by a connection between Bayesian active learning and active hypothesis testing, and is based on querying the label of a sample, which maximizes the extrinsic Jensen-Shannon divergence at each step. We provide upper and lower bounds on the performance of this sampling strategy, and show that these bounds are better than the previous bounds in the literature.

This paper considers the problem of variable-length coding over a discrete memoryless channel with noiseless feedback. This paper provides a stochastic control view of the problem whose solution is analyzed via a newly proposed symmetrized divergence, termed extrinsic Jensen-Shannon (EJS) divergence. It is shown that strictly positive lower bounds on EJS divergence provide nonasymptotic upper bounds on the expected code length. This paper presents strictly positive lower bounds on EJS divergence, and hence nonasymptotic upper bounds on the expected code length, for the following two coding schemes: 1) variable-length posterior matching and 2) MaxEJS coding scheme that is based on a greedy maximization of the EJS divergence. As an asymptotic corollary of the main results, this paper also provides a rate-reliability test. Variable-length coding schemes that satisfy the condition(s) of the test for parameters R and E are guaranteed to achieve a rate R and an error exponent E. The results are specialized for posterior matching and MaxEJS to obtain deterministic one-phase coding schemes achieving capacity and optimal error exponent. For the special case of symmetric binary-input channels, simpler deterministic schemes of optimal performance are proposed and analyzed.

Consider the problem of sequentially searching for a single target in an image. Let the image be divided into M × M equal sized segments where M determines the resolution of the search. The goal is to find the segment that contains the target quickly and accurately. In each step, the player can visually inspect an allowable combination of the segments, and the outcome of the inspection is noisy. In this paper, a lower bound on the optimal total cost is derived. Furthermore, two heuristic policies are considered: A policy that visually inspects a segment with the highest probability of having the target; and a policy that in each step inspects a combination that maximizes the Extrinsic Jensen- Shannon divergence. Via numerical and asymptotic analysis, the performance of the above policies are investigated.

Consider a decision maker who is responsible to dynamically collect observations so as to enhance his information in a speedy manner about an underlying phenomena of interest while accounting for the penalty of wrong declarations. In this paper, Extrinsic Jensen-Shannon (EJS) divergence is introduced as a measure of information. Using EJS as an information utility, a heuristic policy for selecting actions is proposed. Via numerical and asymptotic optimality analysis, the performance of the proposed policy, hence the applicability of the EJS divergence in the context of the active hypothesis testing is investigated.

This paper considers the problem of variable-length coding over a binary-input channel with noiseless feedback. A deterministic sequential coding scheme is proposed and shown to attain the optimal error exponent for any binary-input channel whose capacity is achieved by the uniform input distribution. The proposed scheme is deterministic and has only one phase of operation, in contrast to all previous coding schemes that achieve the optimal error exponent.

This paper considers the problem of throughput optimal routing/scheduling in a multi-hop constrained queueing network with random connectivity whose special cases include opportunistic multi-hop wireless networks and input-queued switch fabrics. The main challenge in the design of throughput optimal routing policies is closely related to identifying appropriate and universal Lyapunov functions with negative expected drift. The few well-known throughput optimal policies in the literature are constructed using simple quadratic or exponential Lyapunov functions of the queue backlogs and as such they seek to balance the queue backlogs across network independent of the topology. By considering a class of continuous, differentiable, and piece-wise quadratic Lyapunov functions, this paper provides a large class of throughput optimal routing policies. The proposed class of Lyapunov functions allow for the routing policy to control the traffic along short paths for a large portion of state-space while ensuring a negative expected drift. This structure enables the design of a large class of routing policies. In particular, and in addition to recovering the throughput optimality of the well-known backpressure routing policy, an opportunistic routing policy with congestion diversity is proved to be throughput optimal.

A distributed adaptive opportunistic routing scheme for multihop wireless ad hoc networks is proposed. The proposed scheme utilizes a reinforcement learning framework to opportunistically route the packets even in the absence of reliable knowledge about channel statistics and network model. This scheme is shown to be optimal with respect to an expected average per-packet reward criterion. The proposed routing scheme jointly addresses the issues of learning and routing in an opportunistic context, where the network structure is characterized by the transmission success probabilities. In particular, this learning framework leads to a stochastic routing scheme that optimally “explores” and “exploits” the opportunities in the network.

Consider a decision maker who is responsible to dynamically collect observations so as to enhance his information in a speedy manner about an underlying phenomena of interest while accounting for the cost of data collection. Due to the sequential nature of the problem, the decision maker relies on his current information state to adaptively (re-)evaluate the tradeoff between the cost of various sensing actions and the precision of their outcomes. In this paper, using results in dynamic programming, a lower bound for the optimal total cost is established. Moreover, an upper bound is obtained using a heuristic policy for dynamic selection of actions. Using the obtained bounds, the closed loop (feedback) gain is shown to be at least logarithmic in the penalty associated with wrong declarations. Furthermore, it is shown that the proposed heuristic achieves asymptotic optimality in many practically relevant problems such as variable-length coding with feedback and noisy dynamic search.

This paper studies the noncausal relay channel, also known as the relay channel with unlimited lookahead, introduced by El Gamal, Hassanpour, and Mammen. Unlike the standard relay channel model, where the relay encodes its signal based on the previous received output symbols, the relay in the noncausal relay channel encodes its signal as a function of the entire received sequence. In the existing coding schemes, the relay uses this noncausal information solely to recover the transmitted message and then cooperates with the sender to communicate this message to the receiver. However, it is shown in this paper that by applying the Gelfand-Pinsker coding scheme, the relay can take further advantage of the noncausally available information, which can achieve strictly higher rates than existing coding schemes. This paper also provides a new upper bound on the capacity of the noncausal relay that strictly improves upon the cutset bound. These new lower and upper bounds on the capacity coincide for the class of degraded noncausal relay channels and establish the capacity for this class.

This paper considers the problem of routing packets across a multi-hop network consisting of multiple sources of traffic and wireless links with stochastic reliability while ensuring bounded expected delay. Each packet transmission can be overheard by a random subset of receiver nodes among which the next relay is selected opportunistically. The main challenge in the design of minimum-delay routing policies is balancing the trade-off between routing the packets along the shortest paths to the destination and distributing traffic across the network. Opportunistic variants of shortest path routing may, under heavy traffic scenarios, result in severe congestion and unbounded delay. While the opportunistic variants of backpressure, which ensure a bounded expected delay, are known to exhibit poor delay performance at low to medium traffic conditions. Combining important aspects of shortest path routing with those of backpressure routing, this paper provides an opportunistic routing policy with congestion diversity (ORCD). ORCD uses a measure of draining time to opportunistically identify and route packets along the paths with an expected low overall congestion. Previously, ORCD was proved to ensure a bounded expected delay for all networks and under any admissible traffic (without any knowledge of traffic statistics). This paper proposes practical implementations and discusses criticality of various aspects of the algorithm. Furthermore, the expected delay encountered by the packets in the network under ORCD is compared against known existing routing policies via simulations where substantial improvements are observed.

This paper considers a generalized sequential hypothesis testing problem in which a decision maker not only can sequentially trade off the sensing cost with the declaration precision, but also can exert control over the sensed information. Here, the decision maker's action impacts the sensing cost as well as outcome. Numerically solving an appropriate DP, it is shown that the sensing outcome has a dual role: (1) it immediately reduces the uncertainty in the decision maker's belief; and (2) it shapes the future belief via Bayes' rule. This paper focuses on sufficient conditions rendering the optimal sensing actions independent of the current and future belief vector, and reducing the problem to a classical (passive) hypothesis testing problem.

In this paper, an adaptive opportunistic routing scheme for multi-hop wireless ad-hoc networks is proposed. The proposed scheme utilizes a reinforcement learning framework to achieve the optimal performance even in the absence of reliable knowledge about channel statistics and network model. This scheme is shown to be optimal with respect to an expected average per packet cost criterion. The proposed routing scheme jointly addresses the issues of learning and routing in an opportunistic context, where the network structure is characterized by the transmission success probabilities. In particular, this learning framework leads to a stochastic routing scheme which optimally ldquoexploresrdquo and ldquoexploitsrdquo the opportunities in the network.