In this paper, we model the problem of link rate selection in wireless channels as a multi-armed bandit problem with correlated arms. A success/failure in a wireless transmission for a given choice of modulation and coding scheme (MCS, an arm) permits us to efficiently predict (upper bound) the outcome of the transmission for other choice of MCS (other arms). For such a correlated arm scenario, we propose an adaptation to the upper confidence bound (UCB) bandit algorithm to minimize the expected cumulative regret. We propose Min-UCB algorithm that leverages the correlations in the rewards of the different arms to define a better estimate of the upper confidence bound for an arm by suitably combining the observed rewards of other arms. We prove that the proposed Min-UCB algorithm performs better in terms of expected cumulative regret than vanilla UCB and many variants proposed for the correlated arms scenario. We also propose a generalization, called Min-Bandit, for other MAB models, evaluate the proposed algorithm numerically and compare the performance with state-of-the-art bandit agents in a variety of scenarios. We show that the Min-Bandit algorithms achieve a better competitive advantage on the cumulative regret than prior works.

We study a completely uncoupled resource allocation algorithm for a heterogeneous network with the objective of maximizing the sum of the utilities (on the average pay-off) of users. We consider a state-dependent network, where the pay-off achieved by the users are a function of their actions as well as the state of the system. We consider four different scenarios depending on the state evolution and the users’ knowledge of the system state. In this context, we present completely uncoupled algorithms for utility maximization, where the users’ action is entirely a function of its past actions and its received pay-off. In particular, the user is oblivious to the actions of the other users in the network. Using the theory of perturbed Markov chains, we show the optimality of our algorithms under appropriate scenarios.

We study a problem of covert communication over binary symmetric channels (BSC) in an asynchronous setup. Here, Alice seeks to communicate to Bob over a BSC while trying to be covert with respect to Willie, who observes any communication through possibly a different BSC. When Alice communicates, she transmits a message (using a codeword of length n) at a random time uniformly distributed in a window of size Awslots. We assume that Bob has side information about the time of transmission leading to a reduced uncertainty of Abslots for Bob, where $A_{b}\lt A_{w}$. In this setup, we seek to characterize the limits of covert communication as a function of the timing advantage. When Awis increasing exponentially in n, we characterize the covert capacity as a function of Awand Ab. When Awis increasing sub-exponentially in n, we characterize lower and upper bounds on achievable covert bits and show that positive covert rates are not feasible irrespective of timing advantage. Using numerical work, we illustrate our results for different network scenarios, and also highlight a tradeoff between timing advantage and channel advantage (between Bob and Willie).

SimRank is a widely studied link-based similarity measure that is known for its simple, yet powerful philosophy that two nodes are similar if they are referenced by similar nodes. While this philosophy has been the basis of several improvements, there is another useful, albeit less frequently discussed interpretation for SimRank known as the Random Surfer-Pair Model. In this work, we show that other well known measures related to SimRank can also be reinterpreted using Random Surfer-Pair Models, and establish a mathematically sound, general and unifying framework for several link-based similarity measures. This also serves to provide new insights into their functioning and allows for using these measures in a Monte Carlo framework, which provides several computational benefits. As an illustration of its utility in designing measures, we develop a new measure based on two existing measures under this framework, and empirically demonstrate its efficacy.

In this paper, we present two completely uncoupled algorithms for utility maximization. In the first part, we present an algorithm that can be applied for general non-concave utilities. We show that this algorithm induces a perturbed (by ε ) Markov chain, whose stochastically stable states are the set of actions that maximize the sum utility. In the second part, we present an approximate sub-gradient algorithm for concave utilities, which is considerably faster and requires lesser memory. We study the performance of the sub-gradient algorithm for decreasing and fixed step sizes. We show that, for decreasing step sizes, the Cesaro averages of the utilities converges to a neighborhood of the optimal sum utility. For constant step size, we show that the time average utility converges to a neighborhood of the optimal sum utility. Our main contribution is the expansion of the achievable rate region, which has not been considered in the previous paper on completely uncoupled algorithms for utility maximization. This expansion aids in allocating a fair share of resources to the nodes, which is important in applications like channel selection, user association, and power control.

We study one shot frame synchronization in a discrete memoryless channel where, a sync frame of known length Nvsymbols is transmitted at a random time v. For a random misalignment 7 between the transmitter clock and the receiver clock, we seek to characterize the sync frame (length) necessary for error-free frame synchronization. We assume that the random times v and 7 are independent and have a general distribution. Using a variable length sync word and a multi-stage sequential decoder for the setup, we derive necessary and sufficient scaling of the average sync frame length for asymptotic error-free frame synchronization. In particular, we show that the average sync frame length must scale with the entropy of v and/or logarithm of cardinality of the sample space of 7. We illustrate our results for the AWGN channel and also derive the scaling needed of the sync frame energy for the asynchronous setup.

We study the problem of frame synchronization over a discrete memoryless channel (DMC) in an asynchronous setup. A sync frame is transmitted at a random time V with a known distribution {αv} and entropy H. We seek to characterize the minimum average length or energy of the sync frame necessary for error-free frame synchronization, as H tends to infinity. We present a variable length sync frame, where the length of the sync frame is adapted based on H and {αv}, for the general arrival distribution and show error-free frame synchronization when the average sync frame length Ñ scales as Ω((H/α(Q)), where α(Q) is the synchronization threshold of the DMC. We then generalize the framework and study a tradeoff between Ñ and α(Q) for optimal frame synchronization and characterize the scaling needed of both Ñ and α(Q) with H. We illustrate our results with the AWGN channel and discuss the adapting sync frame length and symbol power for optimal frame synchronization. Finally, using numerical work and simulations, we evaluate the results under relaxed assumptions, including the imperfect knowledge of arrival distribution and symbol timing error.

We study a problem of sequential frame detection over a finite state Markov channel (FSMC). We consider an asynchronous framework where a sync frame of length N symbols is transmitted uniformly over a large interval of known size A slots. In this setup, we study the scaling needed of the sync frame length N with the asynchronism interval length A for error-free frame synchronization. We study the problem when channel state information (CSI) is known at the transmitter and the receiver, and compute a synchronization threshold, α, that relates the average sync frame length N and A as N > log2(A)/α for asymptotic frame synchronization. Our discussion includes the description of a variable length and adaptive code word for FSMC that achieves the optimal delay performance.

We study a distributed user association algorithm for a heterogeneous wireless network with the objective of maximizing the sum of the utilities (on the received throughput)of wireless users. We consider a state-dependent wireless network where the rate achieved by the users are a function of their user associations as well as the state of the system. Also, we model the network to adapt its state based on the user associations. In this context, we present a completely uncoupled user association algorithm for utility maximization where the user's association is entirely a function of its past associations and its received throughput. In particular, the user is oblivious to the network state (and its evolution) as well as the association of the other users in the network. Using the theory of perturbed Markov chains [1], we show the optimality of our algorithm under appropriate scenarios.

We consider a dense, ad hoc wireless network, confined to a small region. The wireless network is operated as a single cell, i.e., only one successful transmission is supported at a time. Data packets are sent between source-destination pairs by multihop relaying. We assume that nodes self-organize into a multihop network such that all hops are of length d meters, where d is a design parameter. There is a contention-based multiaccess scheme, and it is assumed that every node always has data to send, either originated from it or a transit packet (saturation assumption). In this scenario, we seek to maximize a measure of the transport capacity of the network (measured in bit-meters per second) over power controls (in a fading environment) and over the hop distance d, subject to an average power constraint. We first motivate that for a dense collection of nodes confined to a small region, single cell operation is efficient for single user decoding transceivers. Then, operating the dense ad hoc wireless network (described above) as a single cell, we study the hop length and power control that maximizes the transport capacity for a given network power constraint. More specifically, for a fading channel and for a fixed transmission time strategy (akin to the IEEE 802.11 TXOP), we find that there exists an intrinsic aggregate bit rate (\Theta_{opt} bits per second, depending on the contention mechanism and the channel fading characteristics) carried by the network, when operating at the optimal hop length and power control. The optimal transport capacity is of the form d_{opt}(\bar{P_t}) \times \Theta_{opt} with d_{opt} scaling as \bar{P_t}^{{1\over \eta}}, where \bar{P_t} is the available time average transmit power and \eta is the path loss exponent. Under certain conditions on the fading distribution, we then provide a simple characterization of the optimal operating point. Simulation results are provided comparing the performance of the optimal strategy derived here with some simple strategies for operating the network.

We study the problem of scheduling in OFDMA-based relay networks with emphasis on IEEE 802.16j based WiMAX relay networks. In such networks, in addition to a base station, multiple relay stations are used for enhancing the throughput, and/or improving the range of the base station. We solve the problem of MAC scheduling in such networks so as to serve the mobiles in a fair manner while exploiting the multiuser diversity, as well as the frequency selectivity of the wireless channel. The scheduling resources consist of tiles in a two-dimensional scheduling frame with time slots along one axis, and frequency bands or sub-channels along the other axis. The resource allocation problem has to be solved once every scheduling frame which is about 5 - 10 ms long. While the original scheduling problem is computationally complex, we provide an easy-to-compute upper bound on the optimum. We also propose three fast heuristic algorithms that perform close to the optimum (within 99.5%), and outperform other algorithms such as OFDM2A proposed in the past. Through extensive simulation results, we demonstrate the benefits of relaying in throughput enhancement (an improvement in the median throughput of about 25%), and feasibility of range extension (for e.g., 7 relays can be used to extend the cell-radius by 60% but mean throughput reduces by 36%). Our algorithms are easy to implement, and have an average running time of less than 0.05 ms making them appropriate for WiMAX relay networks.

We consider a dense ad hoc wireless network comprising n nodes confined to a given two dimensional region of fixed area. For the Gupta-Kumar random traffic model and a realistic interference and path loss model (i.e., the channel power gains are bounded above, and are bounded below by a strictly positive number), we study the scaling of the aggregate end-to-end throughput with respect to the network average power constraint, P macr, and the number of nodes, n. The network power constraint P macr is related to the per node power constraint, P macr, as P macr = np. For large P, we show that the throughput saturates as Theta(log(P macr)), irrespective of the number of nodes in the network. For moderate P, which can accommodate spatial reuse to improve end-to-end throughput, we observe that the amount of spatial reuse feasible in the network is limited by the diameter of the network. In fact, we observe that the end-to-end path loss in the network and the amount of spatial reuse feasible in the network are inversely proportional. This puts a restriction on the gains achievable using the cooperative communication techniques studied in and, as these rely on direct long distance communication over the network.

In a dense multi-hop network of mobile nodes capable of applying adaptive power control, we consider the problem of finding the optimal hop distance that maximizes a certain throughput measure in bit-metres/sec, subject to average network power constraints. The mobility of nodes is restricted to a circular periphery area centered at the nominal location of nodes. We incorporate only randomly varying path-loss characteristics of channel gain due to the random motion of nodes, excluding any multi-path fading or shadowing effects. Computation of the throughput metric in such a scenario leads us to compute the probability density function of random distance between points in two circles. Using numerical analysis we discover that choosing the nearest node as next hop is not always optimal. Optimal throughput performance is also attained at non-trivial hop distances depending on the available average network power.

We consider the vector fixed point equations arising out of the analysis of the saturation throughput of a single cell IEEE 802.11e wireless local area network with nodes that have different back-off parameters, including different Arbitration InterFrame Space (AIFS) values. We consider balanced and unbalanced solutions of the fixed point equations arising in homogeneous and nonhomogeneous networks. We are concerned, in particular, with (i) whether the fixed point is balanced within a class, and (ii) whether the fixed point is unique. Our simulations show that when multiple unbalanced fixed points exist in a homogeneous system then the time behaviour of the system demonstrates severe short term unfairness (or multistability). Implications for the use of the fixed point formulation for performance analysis are also discussed. We provide a condition for the fixed point solution to be balanced within a class, and also a condition for uniqueness. We then provide an extension of our general fixed point analysis to capture AIFS based differentiation; again a condition for uniqueness is established. An asymptotic analysis of the fixed point is provided for the case in which packets are never abandoned, and the number of nodes goes to ∞. Finally the fixed point equations are used to obtain insights into the throughput differentiation provided by different initial back-offs, persistence factors, and AIFS, for finite number of nodes, and for differentiation parameter values similar to those in the standard.