In an offload-capable Long Term Evolution (LTE)Wireless Fidelity (WiFi) Heterogeneous Network (HetNet), we consider the problem of maximization of the total system throughput under voice user blocking probability constraint. The optimal policy is threshold in nature. However, computation of optimal policy requires the knowledge of the statistics of system dynamics, viz., arrival processes of voice and data users, which may be difficult to obtain in reality. Motivated by the Post-Decision State (PDS) framework to learn the optimal policy under unknown statistics of system dynamics, we propose, in this paper, an online Radio Access Technology (RAT) selection algorithm using Relative Value Iteration Algorithm (RVIA). However, the convergence speed of this algorithm can be further improved if the underlying threshold structure of the optimal policy can be exploited. To this end, we propose a novel structureaware online RAT selection algorithm which reduces the feasible policy space, thereby offering lesser storage and computational complexity and faster convergence. This algorithm provides a novel framework for designing online learning algorithms for other problems and hence is of independent interest. We prove that both the algorithms converge to the optimal policy. Simulation results demonstrate that the proposed algorithms converge faster than a traditional scheme. Also, the proposed schemes perform better than other benchmark algorithms under realistic network scenarios.

We revisit the problem of inferring the overall ranking among entities in the framework of Bradley-Terry-Luce (BTL) model, based on available empirical data on pairwise preferences. By a simple transformation, we can cast the problem as that of solving a noisy linear system, for which a ready algorithm is available in the form of the randomized Kaczmarz method. This scheme is provably convergent and has excellent empirical performance. Convergence, convergence rate, and error analysis of the proposed algorithm are presented and several numerical experiments are conducted whose results validate our theoretical findings.

We consider the team formation problem where the goal is to find a team of experts for a specific project. In the past, several attempts have been made to formulate this problem and each formulation focuses only on a subset of design criteria such as skill coverage, social compatibility, economy, skill redundancy, etc. In this paper, for the first time, we show that most of the important design criteria for this problem can be fully modeled within one single formulation as an unconstrained submodular function maximization problem. In our formulation, the submodular function turns out to be non-negative and non-monotone. The maximization of this class of submodular function is much less explored than its monotone constrained counterpart. A few recent works [7] [4] have come up with a simulated annealing based randomized approximation scheme for this problem with an approximation ratio of 0.41. In this paper, we customize this algorithm to our formulation and conduct an extensive set of experiments to show its efficacy. Our proposed formulation offers several advantageous features over the existing formulations including skill cover softening, better team communication, and connectivity relaxation. Unlike previous formulations, the skill cover softening feature allows a designer to specify Must Have and Should Have skills. Similarly, through better team communication, we avoid the restriction that all the communication among team members should pass through only the team members and not the outsiders. Finally, connectivity relaxation feature alleviates the constraint of whole team being connected and thereby, lowering the cost.

Epidemics dynamics can describe the dissemination of information in delay tolerant networks, in peer to peer networks and in content delivery networks. The control of such dynamics has thus gained a central role in all of these areas. However, a major difficulty in this context is that the objective functions to be optimized are often not additive in time but are rather multiplicative. The classical objective function in DTNs, i.e., the successful delivery probability of a message within a given deadline, falls precisely in this category, because it takes often the form of the expectation of the exponent of some integral cost. So far, models involving such costs have been solved by interchanging the order of expectation and the exponential function. While reducing the problem to a standard optimal control problem, this interchange is only tight in the mean field limit obtained as the population tends to infinity. In this paper we identify a general framework from optimal control in finance, known as risk sensitive control, which let us handle the original (multiplicative) cost and obtain solutions to several novel control problems in DTNs. In particular, we can derive the structure of state-dependent controls that optimize transmission power at the source node. Further, we can account for the propagation loss factor of the wireless medium while obtaining these controls, and, finally, we address power control at the destination node, resulting in a novel threshold optimal activation policy. Combined optimal power control at source and destination nodes is also obtained.

We consider a mobile connected to a base station, and study how to optimally schedule shutting off its transceiver. First, we study the model from optimal control perspective. We consider off-times (periods of inactivity) of (controlled) duration. We study the question of scheduling "waking up" instants in which the mobile communicates with the base station and checks whether the inactivity period is over. There is a cost proportional to the delay from the moment the off-time ends until the mobile discovers it, a (small) running cost while the mobile is sleeping and a cost for waking up. We present conditions for optimal sleep periods to be constant and derive the optimal period. For the case that the conditions do not hold, we obtain suboptimal solutions which perform strictly better than the optimal constant one. We then investigate optimality restricted to classes of policies with specific constraints. We adopt the parametric optimization approach which entails cost minimization for a given parameterized policy and selection of the best policy among a class. We then compare the performance of optimal policies, of the proposed suboptimal policies as well as that of standard policies like IEEE 802.16e.

In this paper, we consider the problem of energy-efficient uplink scheduling with delay constraint for a multiuser wireless system. We address this problem within the framework of constrained Markov decision processes (CMDPs) wherein one seeks to minimize one cost (average power) subject to a hard constraint on another (average delay). We do not assume the arrival and channel statistics to be known. To handle state-space explosion and informational constraints, we split the problem into individual CMDPs for the users, coupled through their Lagrange multipliers; and a user selection problem at the base station. To address the issue of unknown channel and arrival statistics, we propose a reinforcement learning algorithm. The users use this learning algorithm to determine the rate at which they wish to transmit in a slot and communicate this to the base station. The base station then schedules the user with the highest rate in a slot. We analyze convergence, stability, and optimality properties of the algorithm. We also demonstrate the efficacy of the algorithm through simulations within IEEE 802.16 system.

Wireless networks are increasingly used to carry applications with QoS constraints. Two problems arise when dealing with traffic with QoS constraints. One is admission control, which consists of determining whether it is possible to fulfill the demands of a set of clients. The other is finding an optimal scheduling policy to meet the demands of all clients. In this paper, we propose a framework for jointly addressing three QoS criteria: delay, delivery ratio, and channel reliability. We analytically prove the necessary and sufficient condition for a set of clients to be feasible with respect to the above three criteria. We then establish an efficient algorithm for admission control to decide whether a set of clients is feasible. We further propose two scheduling policies and prove that they are feasibility optimal in the sense that they can meet the demands of every feasible set of clients. In addition, we show that these policies are easily implementable on the IEEE 802.11 mechanisms. We also present the results of simulation studies that appear to confirm the theoretical studies and suggest that the proposed policies outperform others tested under a variety of settings.

Motivated by the increasing usage of wireless broadcast networks for multicast real-time applications like video, this paper considers a canonical real-time multicast scheduling problem for a wireless broadcast LAN. A wireless access point (AP) has N latency-sensitive flows, each associated with a deadline and a multicast group of receivers that desire to receive all the packets successfully by their corresponding deadlines. We consider periodic and one-shot models of real-time arrivals. The channel from the AP to each receiver is a wireless erasure channel, independent across users and slots. We wish to find a communication strategy that minimizes the total deadlines missed across all receivers, where a receiver counts a miss if it does not receive a packet by its deadline. We cast this problem as a restless bandit in stochastic control. We use Whittle's relaxation framework for restless bandits to establish Whittle-indexability for multicast realtime scheduling under the assumption of complete feedback from all receivers in every slot. For the Whittle relaxation, we show that for each flow, the AP's decision between transmitting in a slot and idling has a threshold structure. For the homogeneous case where the erasure channel to each receiver is identically distributed with parameter p, the Whittle index of a flow is xi(1 - p) , where xiis the number of receivers who have yet to receive the current packet of flow i. For the general heterogeneous case in which the erasure channel to receiver j has loss probability pj, the Whittle index corresponding to each flow is Sigmaj(1- pj), where the sum is over all multicast receivers who are yet to receive the packet. We bound the performance of the optimal Whittle relaxation with respect to the optimal wireless multicast real-time scheduler. The heuristic index policy that schedules the flow with the maximum Whittle index in each slot is simple. To relax the complete feedback assumption, we design a scalable mechanism based on statistical estimation theory that obtains the required feedback from all the receivers using a single ACK per packet transmission. The resultant policy is amenable to low-complexity implementation.

In this paper, we consider the problem of energy efficient scheduling under average delay constraint for a single user fading channel. We propose a new approach for on-line implementation of the optimal packet scheduling algorithm. This approach is based on reformulating the value iteration equation by introducing a virtual state called post-decision state. The resultant value iteration equation becomes amenable to online implementation based on stochastic approximation. This approach has an advantage that an explicit knowledge of the probability distribution of the channel state as well as the arrivals is not required for the implementation. We prove that the on-line algorithm indeed converges to the optimal policy.

We are motivated by the widely studied phenomenon called stochastic resonance, namely that in several sensing systems, both natural and engineered, the introduction of noise can enhance the ability of the system to perceive signals in the environment. We adopt an information theoretic viewpoint, evaluating the quality of sensing via the mutual information rate between the environmental signal and the observations. Viewing what would be considered noise in stochastic resonance as an open loop control and using Markov decision theory techniques, we discuss the problem of optimal choice of this control in order to maximize this mutual information rate. We determine the corresponding dynamic programming recursion: it involves the conditional law of certain conditional laws associated to the dynamics. We prove that the optimal control may be chosen as a deterministic function of this law of laws.

In this paper, we propose a power optimal opportunistic scheduling scheme for a multiuser single hop time division multiple access (TDMA) system. We formulate the problem of minimizing average transmission power with different minimum information theoretic rate constraints for individual users. We suggest a stochastic approximation based scheme to implement the policy and argue the convergence of this algorithm. Finally, we extend the power optimal scheduling algorithm for providing temporal fairness among users.

We study the problem of long-run average cost control of Markov chains conditioned on a rare event. In a related recent work, a simulation based algorithm for estimating performance measures associated with a Markov chain conditioned on a rare event has been developed. We extend ideas from this work and develop an adaptive algorithm for obtaining, online, optimal control policies conditioned on a rare event. Our algorithm uses three timescales or step-size schedules. On the slowest timescale, a gradient search algorithm for policy updates that is based on one-simulation simultaneous perturbation stochastic approximation (SPSA) type estimates is used. Deterministic perturbation sequences obtained from appropriate normalized Hadamard matrices are used here. The fast timescale recursions compute the conditional transition probabilities of an associated chain by obtaining solutions to the multiplicative Poisson equation (for a given policy estimate). Further, the risk parameter associated with the value function for a given policy estimate is updated on a timescale that lies in between the two scales above. We briefly sketch the convergence analysis of our algorithm and present a numerical application in the setting of routing multiple flows in communication networks.

We study a decision problem faced by an energy limited wireless device that operates in discrete time. There is some external arrival to the device's transmit buffer. The possible decisions are: a) to serve some of the buffer content; b) to reorder a new battery after serving the maximum possible amount that it can; or c) to remain idle so that the battery charge can increase owing to diffusion process (which is possible in some commercially available batteries). We look at open and closed-loop controls of the system. The closed-loop control problem is a using the framework of Markov decision processes. We address both finite and infinite horizon discounted costs as well as average cost minimization problems. Without using any second order characteristics, we obtain results that include i) optimality of bang-bang control, ii) the optimality of threshold based policies, iii) parametric monotonicity of the threshold, and iv) uniqueness of the threshold. For the open-loop control setting we use recent advances in application of multimodular functions to establish optimality of bracket sequence based control.

We propose and analyze a distributed control law that maintains the prescribed local properties of a wireless ad hoc network in the presence of node mobility, MAC layer power control and link fades. The control law uses a simple and intuitive power adaptation mechanism. We consider as an example the topology requirement of maintaining the out degrees of each node at prescribed values and keeping the in degree close to the out degree. The topology objective is achieved by adapting the transmission power based only on local information. This power adaptation algorithm is analyzed using the o.d.e. approach to stochastic approximation. Simulation results verify the analysis and demonstrate its effectiveness. We also study the ability of the proposed objective to maintain connectivity. Although many heuristics are described in the literature to maintain local topological properties, the algorithm proposed in this paper is the first one that has proven convergence properties.

We consider a random access network in which the nodes need to optimize their channel access rates. The nodes are assumed to be rational and interested in their performance seen as a transmitter as well as a receiver. By casting this problem as a non-cooperative game, we derive conditions for the Nash equilibrium. We also show the existence of a Nash equilibrium when the nodes are constrained by their battery power (for this case, the constraints on the access rates of the nodes become coupled). For the special case where all nodes are each other's neighbors, we find that the equilibrium is given by the solution of a system of linear equations. An adaptive distributed scheme is then proposed for learning this equilibrium and its convergence is studied numerically.

We consider a system of identical parallel queues served by a single server and distinguished only by the price charged at entry. A Poisson stream of customers joins the queue by a greedy policy that minimizes a 'disutility' that combines price and congestion. A special case of linear disutility is analyzed for which it is shown that the individually optimal greedy queue join policy is nearly socially optimal. For this queueing system, a Markov decision theoretic framework is formulated for dynamic pricing in the general case. This queueing system has application in the pricing of Internet services.

We consider the problem of learning the dependence of one random variable on another, from a finite string of independently identically distributed (i.i.d.) copies of the pair. The problem is first converted to that of learning a function of the latter random variable and an independent random variable uniformly distributed on the unit interval. However, this cannot be achieved using the usual function learning techniques because the samples of the uniformly distributed random variables are not available. We propose a novel loss function, the minimizer of which results in an approximation to the needed function. Through successive approximation results (suggested by the proposed loss function), a suitable class of functions represented by combination feedforward neural networks is selected as the class to learn from. These results are also extended for countable as well as continuous state-space Markov chains. The effectiveness of the proposed method is indicated through simulation studies.

A reversible, ergodic, Markov process taking values in the space of polygonally segmented images is constructed. The stationary distribution of this process can be made to correspond to a Gibbs-type distribution for polygonal random fields as introduced by Arak and Surgailis (1989) and a few variants thereof, such as those arising in Bayesian analysis of random fields. Extensions to generalized polygonal random fields are presented where the segmentation boundaries are not necessarily straight line segments.