SafePredict is a novel meta-algorithm that works with any base prediction algorithm for online data to guarantee an arbitrarily chosen correctness rate, 1-ϵ, by allowing refusals. Allowing refusals means that the meta-algorithm may refuse to emit a prediction produced by the base algorithm so that the error rate on non-refused predictions does not exceed ϵ. The SafePredict error bound does not rely on any assumptions on the data distribution or the base predictor. When the base predictor happens not to exceed the target error rate ϵ, SafePredict refuses only a finite number of times. When the error rate of the base predictor changes through time SafePredict makes use of a weight-shifting heuristic that adapts to these changes without knowing when the changes occur yet still maintains the correctness guarantee. Empirical results show that (i) SafePredict compares favorably with state-of-the-art confidence-based refusal mechanisms which fail to offer robust error guarantees; and (ii) combining SafePredict with such refusal mechanisms can in many cases further reduce the number of refusals. Our software is included in the supplementary material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TPAMI.2019.2932415.

A resource-constrained system monitors a source of information by requesting a finite number of updates subject to random transmission delays. An a priori fixed update request policy is shown to minimize a polynomial penalty function of the age of information over arbitrary time horizons. Partial updates, compressed updates with reduced transmission and information content, in the presented model are shown to incur an age penalty independent of the compression. Finite horizons are shown to have better performance in terms of second order statistic relative to infinite horizons.

Due to abundant frequency resources, millimeter wave (mm-wave) spectrum has drawn much attention as a solution to bandwidth scarcity. However, many characteristics of mm-wave transmissions, such as blockage and reduced coverage, make conventional network architectures very inefficient for use in mm-wave networks. A recently proposed multi-tier mm-wave network architecture allows for relaying around blockages and enlarges the coverage of each base station at an acceptable deployment cost. Nevertheless, this architecture introduces major challenges to the scheduling of each tier. The necessity of both enabling flexible user association and fully exploiting the wireless backhaul requires a cross-tier consideration of the multi-tier mm-wave network. We comprehensively analyze the scheduling problem of a downlink multi-tier mm-wave network by jointly regulating the transmissions in all tiers. The cross-tier optimization problem is NP-hard, but a sub-optimal scheme which iteratively optimizes the schedule in different tiers of the network is proposed with polynomial computational complexity. Simulation results show that our algorithm significantly outperforms the benchmarks in both spectral efficiency and fairness with various user distributions.

Service provision over wireless networks is a key performance criterion, yet an onerous task due to the stochastic nature of channels, transmission overhead, and service delay requirements. This paper considers services differentiated by preference without benefit or penalty for early or delayed completion, instead a benefit exists for maintaining the average delay of completed services below a predefined limit. The average delay is constrained at each network instance via joint optimization of probing order and transmission decisions, resulting in a nonlinear expanding-then-collapsing optimization constraint. A permutation in the transmission order does not impact the sum delay but can impact the average delay. Therefore, finding the optimal order is paramount for proper service provision. A particular greedy ordering is shown to reduce the set of feasible solutions without losing global optimality. Practical solutions are proposed via stochastic programming formulation and an optimal stopping strategy that does not use a priori knowledge. The stopping strategy results in a set of thresholds, which can be practically computed a priori and implemented in a decentralized manner. Simulations show that our proposed Dantzig inspired stopping strategy achieves near optimal sum service value with higher throughput than a stochastic programming formulation.

Migrating to higher frequencies using millimeter wave (mmWave) signaling will expand the networks capacity to satiate the current demand for higher throughput. However, the overhead cost required for a centralized scheduler to function in an mmWave network quickly becomes intractable as user and access point (AP) density increase. Alternatively, a decentralized approach where users in mmWave networks opportunistically transmit may greatly benefit from a higher AP density. Taking advantage of the AP diversity projected for mmWave networks a user may sequentially probe APs before selecting a destination AP for transmission. An opportunistic user in an mmWave network must balance the benefit of AP diversity against the overhead cost. We present an mmWave opportunistic network model encompassing the probability of an AP becoming unavailable and the cost of initial access. Our optimal opportunistic strategy is a set of thresholds, which are computable a priori. Bounds on average overhead, delay and throughput of our strategy are also presented. Via numerical analysis, we show that at finite and relatively small probings our proposed strategy outperforms practical alternatives.

Future millimeter wave (mmWave) frequency networks leveraging great swaths of unlicensed bandwidth, dense access point deployments, and beamforming may satiate the current demand for higher throughput. In a dense network, a centralized scheduling approach becomes infeasible. Therefore a user may opportunistically transmit to one of the multiple access points (AP) in its vicinity. Leveraging the AP diversity, a user may probe several APs before selecting a destination for the transmission. However, it is possible that the destination AP becomes unavailable or is in blockage when the user decides to transmit due to the density of the network. We present a novel mm Wave opportunistic network model which encompasses the probability of an AP becoming unavailable. Our optimal opportunistic transmission strategy maximizes the throughput of an opportunistic user. Results show that when users are unwilling to bear large delays, our strategy outperforms alternative methods. Additionally, our strategy performs equally to alternatives when users can shoulder the burden of delay.

Wireless networks are evolving to meet the needs of transforming wireless services. The demands of wireless service users should guide the evolution of networks to be service centric, meaning towards greater and more efficient service provisioning capabilities. Users commonly abandon delayed services and many services are rendered useless due to delay. Such delays can be caused by collisions or the stochastic nature of wireless networks. Through scheduling, a wireless network can overcome these obstacles. To meet the need for timely services, we present a service centric scheduling framework aimed at maximizing service payoffs under strict deadlines. We consider three scenarios for the amount of network information available for scheduling: full, local, and statistical. An optimization framework under full network information is presented along with a method for deriving the optimal solution. With local information scenario, which is a more practical consideration than full information, we present a greedy strategy and an approach via optimal stopping theory to derive an optimal threshold to minimize the time to transmission. A fixed scheme and an opportunistic scheme are presented under the assumption that statistical network information is available alongside local information. Our opportunistic scheme maximizes the average service payoff. A complexity reducing technique which potentially decreases the required computations to make the optimal opportunistic decision is also presented. We evaluate the performance of the various schemes via simulations.

Screen-to-camera visible-light communication links are fundamentally limited by inter-symbol interference, in which the camera receives multiple overlapping symbols in a single capture exposure. By determining interference constraints, we are able to decode symbols with multi-bit depth across all three color channels. We present Styrofoam, a coding scheme which optimally satisfies the constraints by inserting blank frames into the transmission pattern. The coding scheme improves upon the state-of-the-art in camera-based visible-light communication by: (1) ensuring a decode with at least half-exposure of colored multi-bit symbols, (2) limiting decode latency to two transmission frames, and (3) transmitting 0.4 bytes per grid block at the slowest camera's frame rate. In doing so, we outperform peer unsynchronized VLC transmission schemes by 2.9x. Our implementation on smartphone displays and cameras achieves 69.1 kbps.

We study a wireless full-duplex network with imperfect interference cancellation and we solve the routing and power allocation problem for a single source to destination pair. Our interference model includes residual self-interference due to operating in full-duplex. We present a procedure to solve for the optimal power allocation of a given route with individual maximum power constraints for each node. The solution to the problem given a route involves finding polynomial roots of equations associated to the achieved rate at each hop. We then propose a modification to Dijkstra's algorithm with a priority metric that cannot be decoupled, but is efficiently solved by our procedure for a given route. The algorithm finds the joint route and power allocation that achieve the maximum throughput among all possible routes and power allocations. Through simulations we show that, even with imperfect interference cancellation, operating in full-duplex achieves a higher throughput than half-duplex or direct transmission for moderate maximum transmission power.

The joint routing and power allocation problem in a wireless full-duplex network with imperfect interference cancellation and a single source destination pair is solved. Our simplified interference model focuses on the effects of full-duplex by including residual self-interference and one hop interference while other interfering signals are assumed to be negligible. First, the optimal power allocation for a fixed route is identified. Then a modification of Dijkstra's algorithm is used to find the joint route and power allocation to maximize throughput. Due to interference, the algorithm proposed has a non decomposable objective function; however, it is efficiently solved for every candidate route. Our solution in a full interference model, that does not ignore any interference, is at most a constant bound away from the optimal solution in the full interference model. Through simulations we evaluate several scenarios and show the behavior of the solution in both interference models.