An online non-convex optimization problem is considered where the goal is to minimize the flow time (total delay) of a set of jobs by modulating the number of active servers, but with a switching cost associated with changing the number of active servers over time. Each job can be processed by at most one fixed speed server at any time. Compared to the usual online convex optimization (OCO) problem with switching cost, the objective function considered is non-convex and more importantly, at each time, it depends on all past decisions and not just the present one. Competitive algorithms are derived for the worst-case inputs.

The problem of online scheduling of multi-server jobs is considered, where there are a total of K servers, and each job requires concurrent service from multiple servers for it to be processed. Each job on its arrival reveals its processing time, the number of servers from which it needs concurrent service, and an online algorithm has to make scheduling decisions at each time using only information revealed so far with the goal of minimizing the response/flow time. The worst case input model is considered and the performance metric is the competitive ratio. For the case when all job processing time (sizes) are the same, we show that the competitive ratio of any deterministic/randomized algorithm is at least Ω(K) and propose an online algorithm whose competitive ratio is at most K + 1. With unequal job sizes, we propose an online algorithm whose competitive ratio is at most 2K log(Kwmax), where wmax is the maximum size of any job. With equal job sizes, we also consider the resource augmentation regime where an online algorithm has access to more servers than an optimal offline algorithm. With resource augmentation, we propose a simple online algorithm and show that it has a competitive ratio of 1 when provided with 2K servers with respect to an optimal offline algorithm with K servers.

A well-studied generalization of the standard online convex optimization (OCO) framework is constrained online convex optimization (COCO). In COCO, on every round, a convex cost function and a convex constraint function are revealed to the learner after it chooses the action for that round. The objective is to design an online learning policy that simultaneously achieves a small regret while ensuring a small cumulative constraint violation (CCV) against an adaptive adversary interacting over a horizon of length $T$. A long-standing open question in COCO is whether an online policy can simultaneously achieve $O(\sqrt{T})$ regret and $\tilde{O}(\sqrt{T})$ CCV without any restrictive assumptions. For the first time, we answer this in the affirmative and show that a simple first-order policy can simultaneously achieve these bounds. Furthermore, in the case of strongly convex cost and convex constraint functions, the regret guarantee can be improved to $O(\log T)$ while keeping the CCV bound the same as above. We establish these results by effectively combining adaptive OCO policies as a blackbox with Lyapunov optimization - a classic tool from control theory. Surprisingly, the analysis is short and elegant.

The classic online facility location problem deals with finding the optimal set of facilities in an online fashion when demand requests arrive one at a time and facilities need to be opened to service these requests. In this work, we study two variants of the online facility location problem; (1) weighted requests and (2) congestion. Both of these variants are motivated by their applications to real life scenarios and the previously known results on online facility location cannot be directly adapted to analyse them. Weighted requests: In this variant, each demand request is a pair $(x,w)$ where $x$ is the standard location of the demand while $w$ is the corresponding weight of the request. The cost of servicing request $(x,w)$ at facility $F$ is $w\cdot d(x,F)$. For this variant, given $n$ requests, we present an online algorithm attaining a competitive ratio of $\mathcal{O}(\log n)$ in the secretarial model for the weighted requests and show that it is optimal. Congestion: The congestion variant considers the case when there is an additional congestion cost that grows with the number of requests served by each facility. For this variant, when the congestion cost is a monomial, we show that there exists an algorithm attaining a constant competitive ratio. This constant is a function of the exponent of the monomial and the facility opening cost but independent of the number of requests.

We consider a continuous time multi-arm bandit problem (CTMAB), where the learner can sample arms any number of times in a given interval and obtain a random reward from each sample, however, increasing the frequency of sampling incurs an additive penalty/cost. Thus, there is a tradeoff between obtaining large reward and incurring sampling cost as a function of the sampling frequency. The goal is to design a learning algorithm that minimizes the regret. We establish lower bounds on the regret achievable with any algorithm, and propose algorithms that achieve the lower bound up to logarithmic factors. For the single arm case, we show that the lower bound on the regret is$\Omega(1/\mu)$, and an upper bound with regret$O((\log(T/\lambda))^{2}/\mu)$, where$\mu$is the mean of the arm,$T$is the time horizon, and$\lambda$is the tradeoff parameter between the reward and the sampling cost. With$K$arms, we show that the lower bound on the regret is$\Omega(K\mu[1]/\Delta^{2})$, and an upper bound$O(K(\log(T/\lambda))^{2}\mu[1]/\Delta^{2})$where$\mu$[1] now represents the mean of the best arm, and$\Delta$is the difference of the mean of the best and the second-best arm.

Finding an optimal/near-optimal scheduling algorithm to minimize the age of information (AoI) in a multi-source G/G/1 system is well-known to be a hard problem. In this paper, we consider this problem for the non-preemptive setting, where an algorithm is free to choose which update to transmit, but an update under transmission is not allowed to be preempted. For this problem, we propose a novel randomized scheduling algorithm and show that its competitive ratio is at most 3 plus the maximum of the ratio of the variance and the mean of the inter-arrival time distribution of sources. Notably, the competitive ratio is independent of the number of sources, or their service time distributions. For several common inter-arrival time distributions such as exponential, uniform and Rayleigh, the competitive ratio is at most 4.

A constrained version of the online convex optimization (OCO) problem is considered. With slotted time, for each slot, first an action is chosen. Subsequently the loss function and the constraint violation penalty evaluated at the chosen action point is revealed. For each slot, both the loss function as well as the function defining the constraint set is assumed to be smooth and strongly convex. In addition, once an action is chosen, local information about a feasible set within a small neighborhood of the current action is also revealed. An algorithm is allowed to compute at most one gradient at its point of choice given the described feedback to choose the next action. The goal of an algorithm is to simultaneously minimize the dynamic regret (loss incurred compared to the oracle’s loss) and the constraint violation penalty (penalty accrued compared to the oracle’s penalty). We propose an algorithm that follows projected gradient descent over a suitably chosen set around the current action. We show that both the dynamic regret and the constraint violation is order-wise bounded by the path-length, the sum of the distances between the consecutive optimal actions. Moreover, we show that the derived bounds are the best possible.

With multiple identical unit speed servers, the online problem of scheduling jobs that migrate between two phases, limitedly parallelizable or completely sequential, and choosing their respective speeds to minimize the total flow time is considered. In the limited parallelizable regime, allocating k servers to a job, the speed extracted is $k^{1/\alpha},\ \alpha$ > 1, a sub-linear, concave speedup function, while in the sequential phase, a job can be processed by at most one server with a maximum speed of unity. A LCFS based algorithm is proposed for scheduling jobs which always assigns equal speed to the jobs that are in the same phase (limitedly parallelizable/sequential), and is shown to have a constant (dependent only on $\alpha$ > 1) competitive ratio. For the special case when all jobs are available beforehand, improved competitive ratio is obtained.

A two-sided matching system is considered, where servers are assumed to arrive at a fixed rate, while the arrival rate of customers is modulated via a price-control mechanism. We analyse a loss model, wherein customers who are not served immediately upon arrival get blocked, as well as a queueing model, wherein customers wait in a queue until they receive service. The objective is to maximize the platform profit generated from matching servers and customers, subject to quality of service constraints, such as the expected wait time of servers in the loss system model, and the stability of the customer queue in the queuing model. For the loss system, subject to a certain relaxation, we show that the optimal policy has a bang-bang structure. We also derive approximation guarantees for simple pricing policies. For the queueing system, we propose a simple bimodal matching strategy and show that it achieves near optimal profit.

A multiple server setting is considered, where each server has tunable speed, and increasing the speed incurs an energy cost. Jobs arrive to a single queue, and each job has two types of sub-tasks, map and reduce, and aprecedenceconstraint among them: any reduce task of a job can only be processed once all the map tasks of the job have been completed. In addition to the scheduling problem, i.e., which task to execute on which server, with tunable speed, an additional decision variable is the choice of speed for each server, so as to minimize a linear combination of the sum of the flow times of jobs/tasks and the total energy cost. The precedence constraints present new challenges for the speed scaling problem with multiple servers, namely that the number of tasks that can be executed at any time may be small but the total number of outstanding tasks might be quite large. We present simple speed scaling algorithms that are shown to have competitive ratios, that depend on the power cost function, and/or the ratio of the size of the largest task and the shortest reduce task, but not on the number of jobs, or the number of servers.

We consider a node-monitor pair, where updates are generated stochastically (according to a known distribution) at the node that it wishes to send to the monitor. The node is assumed to incur a fixed cost for each transmission, and the objective of the node is to find the update instants so as to minimize a linear combination of AoI of information and average transmission cost. First, we consider the Poisson arrivals case, where updates have an exponential inter-arrival time for which we derive an explicit optimal online policy. Next, for arbitrary distributions of inter-arrival time of updates, we propose a simple randomized algorithm that transmits any newly arrived update with a fixed probability (that depends on the distribution) or never transmits that update. The competitive ratio of the proposed algorithm is shown to be a function of the variance and the mean of the inter-arrival time distribution. For some of the commonly considered distributions such as exponential, uniform, and Rayleigh, the competitive ratio bound is shown to be 2.

We consider a source that sends freshness-sensitive status updates about an auto-regressive Markov process to a monitor, in a time-slotted system. The source samples the random process at the start of every slot and decides whether to transmit the sample or not. The transmission of a sample incurs a fixed cost. When a monitor receives a sample, its information about the source is perfect. However, when no samples are received, it estimates the realization of the process based on previously received samples. We adopt a metric referred to as the age of incorrect estimates (AoIE), defined as the product of an estimation error, E, and, v, the time elapsed since the latest time at which the monitor had a sufficiently correct estimate. We formulate an optimization problem to decide when a source must transmit a packet for minimizing the long-term average expected weighted sum of the AoIE and the transmission cost. We cast this problem as a Markov decision process and prove that the optimal policy is a threshold-type policy, in which, for a fixed v, there exists a threshold on E beyond which it is optimal to transmit, and vice versa. Using numerical simulations, we illustrate this threshold structure of the optimal policy. We also consider a simple periodic policy in which the information packets are transmitted periodically, after every fixed number of slots, irrespective of the realizations of E and v, and numerically show that its performance is significantly worse than that of the optimal threshold-type policy.

We consider a node where packets of fixed size are generated at arbitrary intervals. The node is required to maintain the peak age of information (AoI) at the monitor below a threshold by transmitting potentially only a subset of the generated packets. At any time, depending on packet availability and current AoI, the node can choose the packet to transmit, and its transmission speed. We consider a power function (rate of energy consumption) that is increasing and convex in transmission speed, and the objective is to minimize the energy consumption so as to satisfy the peak AoI constraint at all times. For this problem, we propose a (customized) greedy policy and derive an upper bound on its competitive ratio (CR) that depends on the power function, but is independent of the packet generation times as well as the time horizon. We also derive a lower bound on the CR of all causal policies, and show that the dependence of the CR of the proposed greedy policy on the system parameters (such as packet size, peak AoI and power function) is similar to that of an optimal causal policy.

Freshness of information is an important requirement in many real-time applications. It is measured by a metric called the age of information (AoI), defined as the time elapsed since the generation of the last successful update received by the destination. We consider M sources (users) updating their statuses to a base station (BS) over a block-fading multiple access channel (MAC). At the start of each fading block, the BS acquires perfect information about channel power gain realizations of all the users in the block. Using this information, a centralized scheduling policy at the BS decides, for each block, which users should transmit and with what powers. The objective is to minimize a long-term weighted average AoI across all users subject to a long-term average power constraint at each user. Under this setting, we first consider a simple time-division multiple access (TDMA) strategy, in which at most one user can transmit in a slot, and propose a simple age-independent stationary randomized policy (AI-SRP). The AI-SRP makes transmission decisions based on the channel power gain realizations, without considering the AoIs. We then consider a more general non-orthogonal multiple access (NOMA) strategy, in which any number of users can transmit in a slot subject to capacity constraints of the MAC and propose an AI-SRP. The AI-SRPs we propose are optimal solutions to appropriate optimization problems. We show that the minimum achievable weighted average AoIs across the users under the proposed AI-SRPs are at most two times those of the respective optimal policies under TDMA and NOMA strategies.

A versatile scheduling problem to model a three-way tradeoff between age of information (AoI), quality/distortion, and energy is considered. The considered problem called the age and quality of information (AQI) is to select which packets to transmit at each time slot to minimize a linear combination of the utility driven by quality, the AoI, and the energy transmission cost in an online fashion. AQI problem combines tradeoffs from some important distinct problems, such as AoI with multiple sources, the remote sampling problem with sampling constraint, the classical speed scaling problem among others. The arbitrary/adversarial case input model is considered in the online setting, where the performance metric is the competitive ratio. A greedy algorithm is proposed that is shown to be 2-competitive, independent of all parameters of the problem. For the special case of AQI problem, a maximum weight matching based algorithm is also shown to be 2-competitive.

We consider a distributed IoT network, where each node wants to minimize its own age of information and there is a cost to make any transmission. A collision model is considered, where any transmission is successful from a node to a common monitor if no other node transmits in the same slot. Nodes cannot coordinate their transmission, and can learn about the network only via binary collision information. Under this distributed competition model, the objective of this paper is to find a distributed transmission strategy for each node that converges to an equilibrium that only depends on the past observations seen by each node and does not require network information, e.g., the number of other nodes, or their strategies. A simple update strategy is shown to converge to an equilibrium for any number of nodes that are unknown to the update strategy. The equilibrium achieved is in fact a Nash equilibrium for a suitable utility function, that captures all the right tradeoffs for each node.

The use of channel state information (CSI) at the transmitter significantly enhances the performance of wireless communication systems. However, the requirement of CSI feedback places an undue burden on the reverse link, especially in links that employ multiple-input multiple-output (MIMO) and orthogonal frequency division multiplexing (OFDM), where CSI takes the form of a precoding matrix (precoder) for each subcarrier. Typical deployments use quantization and feedback of CSI at certain subcarriers, with interpolation to fill in missing CSI at the transmitter. Past work has used the orthogonal structure of precoders with Flag manifolds for quantization and interpolation of CSI, although interpolation is complicated due to the absence of analytic expressions for geodesics on Flag manifolds. Other approaches have involved the parameterization of the precoder into scalar parameters that are amenable to quantization and interpolation. In this paper, we present efficient methods to quantize and interpolate on Flag manifolds, using both optimal algorithms as well as simplified suboptimal algorithms. Further, we unify these with the parameterization based approaches and show that these translate directly to low-complexity quantization and interpolation on Flag manifolds. Simulations reveal that the proposed precoder quantization and interpolation effectively enhance achievable rates with limited complexity.

Can the popular shortest remaining processing time (SRPT) algorithm achieve a constant competitive ratio on multiple servers when server speeds are adjustable (speed scaling) with respect to the flow time plus energy consumption metric? This question has remained open for a while, where a negative result in the absence of speed scaling is well known. The main result of this paper is to show that multi-server SRPT with speed scaling can be constant competitive, with a competitive ratio that only depends on the power-usage function of the servers, but not on the number of jobs/servers or the job sizes (unlike when speed scaling is not allowed). When all job sizes are unity, we show that round-robin routing is optimal and can achieve the same competitive ratio as the best known algorithm for the single server problem. Finally, we show that a class of greedy dispatch policies, including policies that route to the least loaded or the shortest queue, do not admit a constant competitive ratio. When job arrivals are stochastic, with Poisson arrivals and i.i.d. job sizes, we show that random routing and a simple gated-static speed scaling algorithm achieves a constant competitive ratio.

In energy harvesting (EH) communications, it is customary to use a battery to temporarily store harvested energy prior to using it for communication. In practice, these batteries suffer from degradation in the usable capacity when they are repeatedly charged after being partially discharged and vice versa. The capacity can be recovered by imposing the full-cycle constraint, which says that a battery must be charged only after it is fully discharged and vice versa. Further, practical batteries cannot be charged and discharged simultaneously. With the above constraints, we consider and compare EH communication systems under two cases: (a) the single-battery case and (b) the dual-battery case, in which the transmitters are equipped with a single battery of capacity 2B joules and two batteries, each having capacity of B joules, respectively. Under (a) and (b), our goal is to obtain the long-term average throughputs and throughput regions in a point-to-point (P2P) channel and a multiple access channel (MAC), respectively. For the P2P channel, we derive the optimal solution in the single-battery case, and propose optimal and suboptimal power allocation policies for the dual-battery case, assuming Bernoulli energy arrivals. Based on these policies, we obtain long-term average achievable throughput regions in MACs by jointly allocating rates and powers. From numerical simulations, we find that the optimal throughput in the dual-battery case is significantly higher than that in the single-battery case, although the total storage capacity in both cases is 2B joules.

Precoding transmissions in wireless MIMO systems is essential to enable optimal utilization of the spatial degrees of freedom. However, communicating the precoding matrices from the receiver is challenging, owing to large feedback requirements. Past work has shown that predictive quantization in time, as well as interpolation over frequency can be used to reconstruct the precoders over a wide band, although these techniques have not been used jointly. We propose both a predictive quantization as well as a joint time-frequency interpolation strategy for precoding matrices over the Stiefel manifold. The key insight that we use is that local tangent spaces in the manifold permit effective combination of both temporal and frequency domain information for more accurate precoder reconstruction. Simulations reveal that we obtain a significant improvement in achievable rate as well as BER reduction when compared to existing strategies.

A distributed sampling strategy for multiple (N) agents is considered that minimizes the sample complexity and regret of acquiring the best subset of size N among total K ≥ N channels in a cognitive radio access setup. Agents cannot directly communicate with each other, and no central coordination is possible. Each agent can transmit on one channel at a time, and if multiple agents transmit on the same channel at the same time, a collision occurs, and no agent gets any information about the channel gain or how many other agents transmitted on the same channel. If no collision occurs, the agent observes a reward (or gain) sample drawn from an underlying distribution associated with the channel. An algorithm to minimize the sample complexity and regret is proposed. One important property of our algorithm that distinguishes it from the prior work (that do not assume knowledge of N) is that it requires no information about the difference of the means of the channel gains of the K channels. Our approach results in fewer collisions with improved regret performance compared to the state-of-the-art algorithms. We validate our theoretical guarantees with experiments.

The objective of this paper is to design a power control policy that maximizes the long-term time-averaged sum throughput of a Gaussian multiple access channel (MAC), where the transmitters as well as the access point (AP) are energy harvesting nodes (EHNs). In addition, the policy is required to facilitate uncoordinated operation of the network. That is, in each slot, the transmitting nodes and the AP need to independently take their actions, e.g., the amount of energy to be used for transmission or whether to turn on and receive the data. First, in order to benchmark the performance of any policy, we derive an upper bound on the throughput achievable, by analyzing a centralized genie-aided system where the nodes have infinite capacity batteries and can freely share the available energy among themselves. In addition, the genie-aided system has non-causal knowledge of the energy arrivals at all the nodes. Next, we show that, surprisingly, a simple time sharing based online policy which requires no coordination among the transmitters and uses time-dilation at the receiver achieves the upper bound asymptotically in the battery size. We also present a policy that requires an occasional one-bit feedback from the AP about its battery state, and show that it requires a smaller sized battery at the receiver compared to a policy which operates without any feedback from the AP, to achieve the same performance. We use Monte Carlo simulations to validate our theoretical results and illustrate the performance of the proposed policies.

In this paper, a tractable model of cellular wireless networks is considered, where both the basestation (BS) and mobile user (MU) locations are distributed as independent Poisson point processes, and each MU connects to its nearest BS. Each packet from the BS is transmitted using an automatic-repeat-request strategy until the signal-to-interference-plus-noise ratio (SINR) is larger than a threshold, and the packet delay is equal to the expected number of retransmissions required for successful reception. We define the network capacity as the product of the BS density and the reciprocal of the packet delay, maximized over all BS strategies. This definition of capacity, while being natural, is non-trivial to analyses because of the temporal correlations of SINRs and arbitrary BS strategies. An exact characterization (non-asymptotic) of this natural capacity metric is derived, which shows that the capacity increases polynomially with the BS density in the low BS density regime and then scales inverse exponentially with the increasing BS density.

A speed scaling problem is considered, where time is divided into slots, and jobs with payoff v arrive at the beginning of the slot with associated deadlines d. Each job takes one slot to be processed, and multiple jobs can be processed by the server in each slot with energy cost g(k) for processing k jobs in one slot. The payoff is accrued by the algorithm only if the job is processed by its deadline. We consider a robust version of this speed scaling problem, where a job on its arrival reveals its payoff v, however, the deadline is hidden to the online algorithm, which could potentially be chosen adversarially and known to the optimal offline algorithm. The objective is to derive a robust (to deadlines) and optimal online algorithm that achieves the best competitive ratio. We propose an algorithm (called min-LCR) and show that it is an optimal online algorithm for any convex energy cost function g(.). We do so without actually evaluating the optimal competitive ratio, and give a general proof that works for any convex g, which is rather novel. For the popular choice of energy cost function g(k) = k^alpha, alpha >= 2, we give concrete bounds on the competitive ratio of the algorithm, which ranges between 2.618 and 3 depending on the value of alpha. The best known online algorithm for the same problem, but where deadlines are revealed to the online algorithm has competitive ratio of 2 and a lower bound of sqrt{2}. Thus, importantly, lack of deadline knowledge does not make the problem degenerate, and the effect of deadline information on the optimal competitive ratio is limited.

The goal in this paper is to design an optimal scheduling and power control policy that maximizes the long-term time-averaged sum throughput of a Gaussian multiple access channel (MAC) with energy harvesting (EH) nodes, and \emph{facilitates uncoordinated operation} of the nodes. In order to benchmark the performance of any policy, we derive an upper bound on the sum throughput by considering a genie-aided system where the nodes have infinite capacity batteries and can freely share the available energy between them. Next, we design a time-sharing based power control policy for the EH MAC, which operates in an uncoordinated fashion. We show that, surprisingly, the sum throughput obtained by the proposed policy achieves the genie-aided upper bound asymptotically in the battery size at each node. Simulation results validate the theoretical findings and illustrate the relative impact of various system parameters (e.g., the battery size required to achieve the upper bound) on the number of nodes and the variation in the harvesting rates across the nodes.

Online knapsack problem is considered, where items arrive in a sequential fashion that have two attributes; value and weight. Each arriving item has to be accepted or rejected on its arrival irrevocably. The objective is to maximize the sum of the value of the accepted items such that the sum of their weights is below a budget/capacity. Conventionally a hard budget/capacity constraint is considered, for which variety of results are available. In modern applications, e.g., in wireless networks, data centres, cloud computing, etc., enforcing the capacity constraint in expectation is sufficient. With this motivation, we consider the knapsack problem with an expected capacity constraint. For the special case of knapsack problem, called the secretary problem, where the weight of each item is unity, we propose an algorithm whose probability of selecting any one of the optimal items is equal to 1 -1/e and provide a matching lower bound. For the general knapsack problem, we propose an algorithm whose competitive ratio is shown to be 1/4e that is significantly better than the best known competitive ratio of 1/10e for the knapsack problem with the hard capacity constraint.

A single server with variable speed and a finite buffer is considered under a maximum packet drop probability constraint. The cost of processing by the server is a convex function of the speed of the server. If a packet arrives when the buffer is full, it is dropped instantaneously. Given the finite server buffer, the objective is to find the optimal dynamic server speed to minimize the overall cost subject to the maximum packet drop probability constraint. Finding the exact optimal solution is known to be hard, and hence algorithms with provable approximation bounds are considered. We show that if the buffer size is large enough, the proposed algorithm achieves the optimal performance. For arbitrary buffer sizes, constant approximation guarantees are derived for a large class of packet arrival distributions such as Bernoulli, Exponential, Poisson etc.

Two related online problems: knapsack and truthful bipartite matching are considered. For these two problems, the common theme is how to `match' an arriving left vertex in an online fashion with any of the available right vertices, if at all, so as to maximize the sum of the value of the matched edges, subject to satisfying a sum-weight constraint on the matched left vertices. Assuming that the left vertices arrive in an uniformly random order (secretary model), two almost similar algorithms are proposed for the two problems, that are 2e competitive and 24 competitive, respectively. The proposed online bipartite matching algorithm is also shown to be truthful: there is no incentive for any left vertex to misreport its bid/weight. Direct applications of these problems include job allocation with load balancing, generalized adwords, crowdsourcing auctions, and matching wireless users to cooperative relays in device-to-device communication enabled cellular network.

A two-way half-duplex communication model is considered, where two nodes want to exchange a fixed number of bits with each other, and both nodes are powered by energy harvesting (EH) sources. The problem of minimizing the sum of the time required to send the required bits in both the directions is considered. The model also includes the processing cost at each node, that models the power needed for nodes to stay powered on during transmission. In the offline setting, where the EH arrival profile is known non-causally, an iterative algorithm based on alternating maximization is shown to be optimal. In the more realistic setting of causal knowledge of the EH arrival profile, an online algorithm is shown to be optimal in terms of the competitive ratio and the optimal competitive ratio is shown to be 2.

In this paper, we consider a point-to-point link between an energy harvesting transmitter and receiver, where neither node has the information about the battery state or energy availability at the other node. We consider a model where data is successfully delivered only in slots where both nodes are active. Energy loss occurs whenever one node turns on while the other node is in sleep mode. In each slot, based on their own energy availability, the transmitter and receiver need to independently decide whether or not to turn on, with the aim of maximizing the long-term time-average throughput. We present an upper bound on the throughput achievable by analyzing a genie-aided system that has noncausal knowledge of the energy arrivals at both the nodes. Next, we propose an online policy requiring an occasional one-bit feedback whose throughput is within one bit of the upper bound, asymptotically in the battery size. In order to further reduce the feedback required, we propose a time-dilated version of the online policy. As the time dilation gets large, this policy does not require any feedback and achieves the upper bound asymptotically in the battery size. Inspired by this, we also propose a near-optimal fully uncoordinated policy. We use Monte Carlo simulations to validate our theoretical results and illustrate the performance of the proposed policies.

Motivated by applications in competitive WiFi sensing, and competition to grab user attention in social networks, the problem of when to arrive at/sample a shared resource/server platform with multiple players is considered. Server activity is intermittent, with the server switching between ON and OFF periods alternatively. Each player spends a certain cost to sample the server state, and the per-player payoff is inversely proportional to the number of simultaneously connected/arrived players. The objective of each player is to arrive/sample the server as soon as any ON period begins while incurring minimal sensing cost and to avoid having many other players overlap in time with itself. For this competition model, we propose a distributed randomized learning algorithm (strategy to sample the server) for each player, which is shown to converge to a unique non-trivial fixed point. The fixed point is moreover shown to be a Nash equilibrium of a game, where each player's utility function is demonstrated to possess all the required selfish tradeoffs.

In cellular networks, under ARQ and SINR model of transmission, the effective downlink rate of packet transmission is the reciprocal of the expected delay (number of retransmissions needed till success). We define the cellular network capacity as the ratio of the basestation (BS) density and the expected delay. Exact characterization of this natural and practical but non-trivial (because of SINR temporal correlations) capacity metric is derived. The capacity is shown to first increase polynomially with the BS density and then scale inverse exponentially with the increasing BS density. Two distinct upper bounds are derived that are relevant for the low and the high BS density regimes. A single power control strategy is shown to achieve the upper bounds in both the regimes up to constants. Our result is fundamentally different than the transport and transmission capacity for ad hoc networks that scale as the square root of the (high) BS density. Our results show that the strong temporal correlations of SINRs with PPP distributed BS locations model for cellular networks is limiting, and the realizable capacity is much smaller than previously thought.

We address a classical problem concerning energy efficiency in sensor networks. In particular, we consider the problem of maximizing the lifetime of coverage of targets in a wireless sensor network with battery-limited sensors. We first show that the problem cannot be approximated within a factor less than lnn by any polynomial time algorithm, where n is the number of targets. This provides closure to the long-standing open problem of showing optimality of previously known lnn approximation algorithms. We also derive a new ln n approximation to the problem by showing the lnn approximation to the related maximum disjoint set cover problem. We show that this approach has many advantages over algorithms in the literature, including a simple and optimal extension that solves the problem with multiple coverage constraints. For the 1-D network topology, where sensors can monitor contiguous line segments of possibly different lengths, we show that the optimal coverage lifetime can be found in polynomial time. Finally, for the 2-D topology in which coverage regions are unit squares, we combine the existing results to derive a 1 + € approximation algorithm for the problem. Extensive simulation experiments validate our theoretical results, showing that our algorithms not only have optimal worst case guarantees but also match the performance of the existing algorithms on special network topologies. In addition, our algorithms sometimes run orders of magnitude faster than the existing state of the art.

We study an online assignment problem where the offline servers have capacities, and the objective is to obtain a maximum-weight assignment of requests that arrive online. The weight of edges incident to any server can be at most the server capacity. Our problem is related to the adwords problem, where the assignment to a server is allowed to exceed its capacity. In many applications, however, server capacities are strict and partially-served requests are of no use, motivating the problem we study. While no deterministic algorithm can be competitive in general for this problem, we give an algorithm with competitive ratio that depends on the ratio of maximum weight of any edge to the capacity of the server it is incident to. If this ratio is 1/2, our algorithm is tight. Further, we give a randomized algorithm that is 6-competitive in expectation for the general problem. Most previous work on the problem and its variants assumes that the edge weights are much smaller than server capacities. Our guarantee, in contrast, does not require any assumptions about job weights. We also give improved lower bounds for both deterministic and randomized algorithms. For the special case of parallel servers, we show that a load-balancing algorithm is tight and near-optimal.

The problem of online packet scheduling to minimize the required energy for transmitting a fixed number of packets given a common deadline is considered. The total number of packets arriving within the deadline is known, but the packet arrival times are unknown, and can be arbitrary. The proposed algorithm tries to finish the transmission of each packet assuming all future packets are going to arrive at equal time intervals within the left-over time. The proposed online algorithm is shown to have competitive ratio that is logarithmic in the number of packet arrivals.

Modern content delivery networks consist of one or more "back-end" servers which store the entire content catalog, assisted by multiple "front-end" servers with limited storage and service capacities located near the end-users. Appropriate replication of content on the front-end servers is key to maximize the fraction of requests served by the front-end servers. Motivated by this, a multiple cache variant of the classical single cache paging problem is studied, which is referred to as the Multiple Cache Paging (MCP) problem. In each time-slot, a batch of content requests arrive that have to be served by a bank of caches, and each cache can serve exactly one request. If a content is not found in the bank, it is fetched from the back-end server, and one currently stored content is ejected, and counted as `fault'. As in the classical paging problem, the goal is to minimize the total number of faults. The competitive ratio of any online algorithm for the MCP problem is shown to be unbounded for arbitrary input, thus concluding that the MCP problem is fundamentally different from the classical paging problem. Consequently, stochastic arrivals setting is considered, where requests arrive according to a known/unknown stochastic process. It is shown that near optimal performance can be achieved with simple policies that require no co-ordination across the caches.

The problem of online packet scheduling to minimize the required conventional grid energy for transmitting a fixed number of packets given a common deadline is considered. The total number of packets arriving within the deadline is known, but the packet arrival times are unknown, and can be arbitrary. The proposed algorithm tries to finish the transmission of each packet assuming that all future packets are going to arrive at equal time intervals within the left-over time. The proposed online algorithm is shown to have competitive ratio that is logarithmic in the number of packet arrivals. The hybrid energy paradigm is also considered, where in addition to grid energy, energy is also available via extraction from renewable sources. The objective here is to minimize the grid energy use. A suitably modified version of the previous algorithm is also shown to have competitive ratio that is logarithmic in the number of packet arrivals.

A joint transmitter-receiver energy harvesting model is considered, where both the transmitter and the receiver are powered by random (renewable) energy source. Given a fixed number of bits, the problem is to find the optimal transmission power profile at the transmitter and ON-OFF profile at the receiver to minimize the transmission time. With infinite capacity at both the transmitter and the receiver, the optimal offline and optimal online policies are derived. The optimal online policy is shown to be two-competitive in the arbitrary input case. With finite battery capacities at both ends, only random energy arrival sequence with given distribution is considered, for which an online policy with bounded expected competitive ratio is proposed.

We show that the maximum mutual information (capacity) of parallel Gaussian channels obtained by the optimal water-filling algorithm for power allocation under a sum-power constraint is submodular. For a given power allocation, mutual information is known to be submodular. However, establishing the submodularity of the capacity, which additionally involves maximization of the mutual information over the power allocation, is challenging. Capacity of parallel Gaussian channels is equivalent to the maximum log-utility function used in resource allocation problems. Using this correspondence and the submodularity of the capacity, we find provable guarantees on multiple combinatorial resource allocation problems in wireless networks. In particular, we show that greedy algorithms give a 2-approximation for uplink OFDMA power and subcarrier allocation, FDMA capacity, downlink base-station association, with honest as well as strategic users who may or may not report their channel gains truthfully.

Transmitter-receiver energy harvesting model is assumed, where both the transmitter and receiver are powered by random energy source. Given a fixed number of bits, the problem is to find the optimal transmission power profile at the transmitter and ON-OFF profile at the receiver to minimize the transmission time. Structure of the optimal offline strategy is derived together with an optimal offline policy. An online policy with competitive ratio of strictly less than two is also derived.

Given a universe U of n elements and a collection of subsets S of U, the maximum disjoint set cover problem (DSCP) is to partition S into as many set covers as possible, where a set cover is defined as a collection of subsets whose union is U. We consider the online DSCP, in which the subsets arrive one by one (possibly in an order chosen by an adversary), and must be irrevocably assigned to some partition on arrival with the objective of minimizing the competitive ratio. The competitive ratio of an online DSCP algorithm A is defined as the maximum ratio of the number of disjoint set covers obtained by the optimal offline algorithm to the number of disjoint set covers obtained by A across all inputs. We propose an online algorithm for solving the DSCP with competitive ratio ln n. We then show a lower bound of Ω(√ln n) on the competitive ratio for any online DSCP algorithm. The online disjoint set cover problem has wide ranging applications in practice, including the online crowd-sourcing problem, the online coverage lifetime maximization problem in WSNs, and in online resource allocation problems.

In wireless networks, where each node transmits independently of other nodes in the network (the ALOHA protocol), the expected delay experienced by a packet until it is successfully received at any other node is known to be infinite for the signal-to-interference-plus-noise-ratio (SINR) model with node locations distributed according to a Poisson point process. Consequently, the information velocity, defined as the limit of the ratio of the distance to the destination and the time taken for a packet to successfully reach the destination over multiple hops, is zero, as the distance tends to infinity. A nearest neighbor distance based power control policy is proposed to show that the expected delay required for a packet to be successfully received at the nearest neighbor can be made finite. Moreover, the information velocity is also shown to be non-zero with the proposed power control policy. The condition under which these results hold does not depend on the intensity of the underlying Poisson point process.

The problem of finding an optimal sensing schedule for a mobile device that encounters an intermittent WiFi access opportunity is considered. At any given time, the WiFi is in any of the two modes, ON or OFF, and the mobile's incentive is to connect to the WiFi in the ON mode as soon as possible, while spending as little sensing energy. We introduce a dynamic programming framework which enables the characterization of an explicit solution for several models, particularly suitable when the OFF periods are exponentially distributed. While the problem for non-exponential OFF periods is ill-posed in general, a usual workaround in literature is to make the mobile device aware if one ON period is completely missed. In this restricted setting, using the DP framework, the deterministic nature of the optimal sensing policy is established, and value iterations are shown to converge to the optimal solution. Finally, we address the blind situation where the distributions of ON and OFF periods are unknown. A continuous bandit based learning algorithm that has vanishing regret (loss compared to the optimal strategy with the knowledge of distributions) is presented, and comparisons with the optimal schemes are provided for exponential ON and OFF periods.

In this paper, we consider the problem of online incentive mechanism design for smart-phone crowd-sourcing. We consider the online setting where users arrive in a sequence and each user participating in crowd-sourcing submits a set of tasks it can accomplish and its corresponding bid. The platform then selects the users and their payments to maximize its utility while ensuring truthfulness, individual rationality, profitability, and polynomial algorithm complexity. The decision whether to accept or reject each user is made instantaneously, with no revocation. We propose an algorithm and show that it satisfies all the four desired properties of an efficient auction. Through extensive simulations, we evaluate the performance of our online algorithm.

In this paper, we derive optimal transmission policies for energy harvesting sensors to maximize the utility obtained over a finite horizon. First, we consider a single energy harvesting sensor, with discrete energy arrival process, and a discrete energy consumption policy. Under this model, we show that the optimal finite horizon policy is a threshold policy, and explicitly characterize the thresholds, and the thresholds can be precomputed using a recursion. Next, we address the case of multiple sensors, with only one of them allowed to transmit at any given time to avoid interference, and derive an explicit optimal policy for this scenario as well.

Given a large dimensional input and output space, even simple regression is prohibitively costly. Dimensionality reduction in the output space is important for efficient learning and prediction as modern paradigms, e.g. Topic modelling, image classification, etc., have extremely large output spaces. In contrast to input dimensionality reduction, dimension reduction in output side is complicated. We propose, mutual information based output dimensionality reduction, that takes into account the relationship between the input and the output which is essential for regression and classification problems. Our method selects those labels to form the compressed label space that typically have the maximum mutual information with the input. Selecting the best subset is computationally hard, but we provide a polynomial time algorithm with provable approximation guarantee. We conduct experiments on seven multi-label classification datasets. Results show our method performs better than existing methods on some datasets.

Connectivity in an information-theoretically secure graph is considered where both the legitimate and the eavesdropper nodes are distributed as Poisson point processes. To allow concurrent transmissions from multiple legitimate nodes, a signal-to-interference plus noise ratio secure graph is introduced, and its percolation (having an unbounded connected component) properties are studied. It is shown that for a fixed eavesdropper node density, percolation happens for large enough (but finite) legitimate node density and small enough interference suppression parameter of the legitimate nodes. Conversely, a concrete bound is obtained that shows that if the legitimate node density is below a fixed threshold, then the probability of percolation is zero.

The design of online algorithms for maximizing the achievable rate in a wireless communication channel between a source and a destination over a fixed number of slots is considered. The source is assumed to be powered by a natural renewable source, and the most general case of arbitrarily varying energy arrivals is considered, where neither the future energy arrival instants or amount nor their distribution is known. The fading coefficients are also assumed to be arbitrarily varying over time, with only causal information available at the source. For a maximization problem, the utility of an online algorithm is tested by finding its competitive ratio or competitiveness that is defined to be the maximum of the ratio of the gain of the optimal offline algorithm and the gain of the online algorithm over all input sequences. We show that the lower bound on the optimal competitive ratio for maximizing the achievable rate is arbitrarily close to the number of slots. Conversely, we propose a simple strategy that invests available energy uniformly over all remaining slots until the next energy arrival, and show that its competitive ratio is equal to the number of slots, to conclude that it is an optimal online algorithm.

Large-scale blockages such as buildings affect the performance of urban cellular networks, especially at higher frequencies. Unfortunately, such blockage effects are either neglected or characterized by oversimplified models in the analysis of cellular networks. Leveraging concepts from random shape theory, this paper proposes a mathematical framework to model random blockages and analyze their impact on cellular network performance. Random buildings are modeled as a process of rectangles with random sizes and orientations whose centers form a Poisson point process on the plane. The distribution of the number of blockages in a link is proven to be a Poisson random variable with parameter dependent on the length of the link. Our analysis shows that the probability that a link is not intersected by any blockages decays exponentially with the link length. A path loss model that incorporates the blockage effects is also proposed, which matches experimental trends observed in prior work. The model is applied to analyze the performance of cellular networks in urban areas with the presence of buildings, in terms of connectivity, coverage probability, and average rate. Our results show that the base station density should scale superlinearly with the blockage density to maintain the network connectivity. Our analyses also show that while buildings may block the desired signal, they may still have a positive impact on the SIR coverage probability and achievable rate since they can block significantly more interference.

Design of online algorithms for assigning mobile users to basestations is considered with the objective of maximizing the sum-rate, when all users associated to any one basestation equally share each basestation's resources. Each user on its arrival reveals the rates it can obtain if connected to each of the basestations, and the problem is to assign each user to any one basestation irrevocably and without delay so that the sum-rate is maximized at the end of all user arrivals. In online algorithms, at each user arrival, the rates of future users are assumed to be unknown, and no assumptions are made about their statistics. Online algorithms with constant factor loss in comparison to offline algorithms (that know both the user arrival and user rates profile in advance) are derived. The proposed online algorithms are motivated from the famous online k-secretary problem and online maximum weight matching problem.

The design of online algorithms for minimizing packet transmission time is considered for single-user Gaussian channel and two-user Gaussian multiple access channel (GMAC) powered by natural renewable sources. The most general case of arbitrary energy arrivals is considered where neither the future energy arrival instants or amount, nor their distribution is known. The online algorithm adaptively changes the transmission rate according to the causal energy arrival information, so as to minimize the packet transmission time. For a minimization problem, the utility of an online algorithm is tested by finding its competitive ratio or competitiveness that is the maximum of the ratio of the gain of the online algorithm and the optimal offline algorithm over all input sequences. We derive a lower bound that shows that competitive ratio of any online algorithm is at least 1.38 for single-user Gaussian channel and 1.356 for GMAC. A `lazy' transmission policy that chooses its transmission power to minimize the transmission time assuming that no further energy arrivals are going to occur in future is shown to be strictly two-competitive for both the single-user Gaussian channel and the GMAC.

The design of online algorithms for maximizing the achievable rate in a cognitive radio (CR) over a fixed number of slots under a sum-power constraint is considered. CR is allowed to transmit in slots unoccupied by the primary transmitter (PT), however, no information about future PT slot occupancy is known at the CR. The fading coefficients are also assumed to be arbitrarily varying over time, with only causal information available at the CR. For a maximization problem, the utility of an online algorithm is tested by finding its competitive ratio or competitiveness that is defined to be the maximum of the ratio of the gain of the optimal offline algorithm and the gain of the online algorithm over all input sequences. We show that the lower bound on the optimal competitive ratio for maximizing the achievable CR rate is arbitrarily close to the number of slots. Conversely, we propose a simple strategy that invests available power uniformly assuming all the future slots are going to be unoccupied, and show that its competitive ratio is equal to the number of slots, to conclude that it is an optimal online algorithm.

A wireless communication network is considered where any two nodes are connected if the signal-to-interference ratio (SIR) between them is greater than a threshold. Assuming that the nodes of the wireless network are distributed as a Poisson point process (PPP), percolation (formation of an unbounded connected cluster) on the resulting SIR graph is studied as a function of the density of the PPP. It is shown that for a small enough threshold, there exists a closed interval of densities for which percolation happens with non-zero probability. Conversely, it is shown that for a large enough threshold, there exists a closed interval of densities for which the probability of percolation is zero. Connectivity properties of the SIR graph are also studied by restricting all the nodes to lie in a bounded area. Assigning separate frequency bands or time-slots proportional to the logarithm of the number of nodes to different nodes for transmission/reception is shown to be necessary and sufficient for guaranteeing connectivity in the SIR graph.

The transmission capacity of an ad-hoc network is the maximum density of active transmitters per unit area, given an outage constraint at each receiver for a fixed rate of transmission. Assuming that the transmitter locations are distributed as a Poisson point process, this paper derives upper and lower bounds on the transmission capacity of an ad-hoc network when each node is equipped with multiple antennas. The transmitter either uses eigen multi-mode beamforming or a subset of its antennas without channel information to transmit multiple data streams, while the receiver uses partial zero forcing to cancel certain interferers using some of its spatial receive degrees of freedom (SRDOF). The receiver either cancels the nearest interferers or those interferers that maximize the post-cancellation signal-to-interference ratio. Using the obtained bounds, the optimal number of data streams to transmit, and the optimal SRDOF to use for interference cancellation are derived that provide the best scaling of the transmission capacity with the number of antennas. With beamforming, single data stream transmission together with using all but one SRDOF for interference cancellation is optimal, while without beamforming, single data stream transmission together with using a fraction of the total SRDOF for interference cancellation is optimal.

Two coexisting ad-hoc networks, one primary and other cognitive, are considered, where each node of the primary network has a single antenna, while each node of the cognitive network is equipped with multiple antennas. Using multiple antennas, each cognitive transmitter uses some of its spatial transmit degrees of freedom (STDOF) to null its interference towards the primary receivers, while each cognitive receiver employs interference cancelation using some of its spatial receive degrees of freedom (SRDOF). This paper derives the optimal STDOF for nulling, and SRDOF for interference cancelation, that maximize the scaling of the transmission capacity of the cognitive network with respect to the number of antennas, when the cognitive network operates under an outage constraint at the primary receivers. With a single receive antenna, using a fraction of the total STDOF for nulling at each cognitive transmitter maximizes the transmission capacity of the cognitive network. With multiple transmit and receive antennas and fixing all but one STDOF for nulling, using a fraction of the total SRDOF to cancel the nearest interferers maximizes the transmission capacity of the cognitive network.

In a two-way relay channel, two sources use one or more relay nodes to exchange data with each other. This paper considers a multiple input multiple output (MIMO) two-way relay channel, where each relay node has one or more antennas. Optimal relay transmission strategies for the two-way relay channel are derived to maximize the achievable rate with amplify and forward (AF) at each relay and to achieve the optimal diversity-multiplexing tradeoff (DM-tradeoff). To maximize the achievable rate with AF, an iterative algorithm is proposed which solves a power minimization problem subject to minimum signal-to-interference-and-noise ratio constraints at every step. The power minimization problem is nonconvex. The Karush Kuhn Tucker conditions, however, are shown to be sufficient for optimality. Capacity scaling law of the two-way relay channel with increasing number of relays is also established by deriving a lower and upper bound on the capacity region of the two-way relay channel. To achieve the optimal DM-tradeoff, a compress and forward strategy is proposed and its DM-tradeoff is derived. For the full-duplex two-way relay channel, the proposed strategy achieves the optimal DM-tradeoff, while for the half-duplex case the proposed strategy is shown to achieve the optimal DM-tradeoff under some conditions.

Delay-reliability (D-R), and throughput-delay-reliability (T-D-R) tradeoffs in an ad hoc network are derived for single hop and multi-hop transmission with automatic repeat request (ARQ) on each hop. The delay constraint is modeled by assuming that each packet is allowed at most D retransmissions end-to-end, and the reliability is defined as the probability that the packet is successfully decoded in at most D retransmissions. The throughput of the ad hoc network is characterized by the transmission capacity, where the transmission capacity is defined to be the maximum density of spatial transmissions that can be simultaneously supported in an ad hoc network under quality of service (QoS) constraints (maximum retransmissions and reliability). The transmission capacity captures the T-D-R tradeoff as it incorporates the dependence between the throughput, the maximum delay, and the reliability. Given an end-to-end retransmission constraint of D, the optimal allocation of the number of retransmissions allowed at each hop is derived that maximizes a lower bound on the transmission capacity. Optimizing over the number of hops, single hop transmission is shown to be optimal for maximizing a lower bound on the transmission capacity in the sparse network regime.

Two coexisting ad hoc networks, primary and secondary, are considered, where each node of the primary network has a single antenna, while each node of the secondary network is equipped with multiple antennas. Using multiple antennas, each secondary transmitter uses some of its spatial transmit degrees of freedom (STDOF) to null its interference towards the primary receivers, while each secondary receiver employs interference cancelation using some of its spatial receive degrees of freedom (SRDOF). This paper derives the optimal STDOF for nulling and SRDOF for interference cancelation that maximize the scaling of the transmission capacity of the secondary network with respect to the number of antennas, when the secondary network operates under an outage constraint at the primary receivers. With a single receive antenna, using a fraction of the total STDOF for nulling at each secondary transmitter maximizes the transmission capacity. With multiple transmit and receive antennas and fixing all but one STDOF for nulling, using a fraction of the total SRDOF to cancel the nearest interferers maximizes the transmission capacity of the secondary network.

The transmission capacity of an ad-hoc network is the maximum density of active transmitters per unit area, given an outage constraint at each receiver for a fixed rate of transmission. Most prior work on finding the transmission capacity of ad-hoc networks has focused only on one-way communication where a source communicates with a destination and no data is sent from the destination to the source. In practice, however, two-way or bidirectional data transmission is required to support control functions like packet acknowledgements and channel feedback. This paper extends the concept of transmission capacity to two-way wireless ad-hoc networks by incorporating the concept of a two-way outage with different rate requirements in both directions. Tight upper and lower bounds on the two-way transmission capacity are derived for frequency division duplexing. The obtained bounds are used to derive the optimal solution for bidirectional bandwidth allocation that maximizes the two-way transmission capacity, which is shown to perform better than allocating bandwidth proportional to the desired rate in both directions. Using the proposed two-way transmission capacity framework, a lower bound on the two-way transmission capacity with transmit beamforming using limited feedback is derived as a function of bandwidth and the number of bits allocated for feedback.

The transmission capacity of an ad-hoc network is the maximum density of active transmitters in a unit area, given an outage constraint at each receiver for a fixed rate of transmission. Most prior work on finding the transmission capacity of ad-hoc networks has focused only on one-way communication where a source communicates with destination and no data is sent from destination to the source. In practice, however, two-way or bidirectional data transmission is required to support control functions like packet acknowledgements and channel feedback. This paper develops the concept of transmission capacity for two-way wireless ad-hoc networks, by incorporating the concept of a two-way outage with different rate requirements in both directions. Upper and lower bounds on the two-way transmission capacity are derived for frequency division duplexing, under the assumption that the channel coefficients are independent on different carrier frequencies. The derived bounds are used to derive the optimal solution for bidirectional bandwidth allocation that maximizes the two-way transmission capacity, which is shown to perform better than allocating bandwidth proportional to the desired rate in both directions.

An iterative algorithm is proposed to achieve the optimal rate region in a two-way relay channel, where two nodes want to exchange data with each other using multiple relays, and each relay employs an amplify and forward strategy. The iterative algorithm solves a power minimization problem at every step, subject to minimum signal-to-interference-and-noise ratio constraints, which is non-convex, however, for which the Karush Kuhn Tucker conditions are sufficient for optimality. Using simulations, the achievable rate region of the iterative algorithm is compared with the cut-set upper bound; the gap is shown to be quite small for most cases.

Distributed space-time block coding is a diversity technique to mitigate the effects of fading in multi-hop wireless networks, where multiple relay stages are used by a source to communicate with its destination. This paper proposes a new distributed space-time block code called the cascaded orthogonal space-time block code (COSTBC) for the case where the source and destination are equipped with multiple antennas and each relay stage has one or more single antenna relays. Each relay stage is assumed to have receive channel state information (CSI) for all the channels from the source to itself, while the destination is assumed to have receive CSI for all the channels. To construct COSTBC, multiple orthogonal space-time block codes are used in cascade by the source and each relay stage. COSTBC is shown to achieve the maximum diversity gain in a multi-hop wireless network with flat Rayleigh fading channels. An explicit construction of COSTBCs is also provided. It is also shown that COSTBC requires minimum decoding complexity thanks to the connection to orthogonal space-time block codes.

This paper considers capacity scaling in the recently proposed two-way MIMO (multiple input multiple output) relay channel. In the two-way relay channel, two nodes use a relay for exchanging data with each other. Under the assumption that each node has perfect receive channel state information and all nodes work only in half duplex mode, this paper shows that the sum capacity scales linearly with the number of transmit antennas and logarithmically with the number of relays, as the number of relays grows large. This result shows that with two- way relay channels it is possible to asymptotically (in the number of relays) obtain full-duplex performance while using only half-duplex nodes.

Multiple antennas can be used for increasing the amount of diversity (diversity gain) or increasing the data rate (the number of degrees of freedom or spatial multiplexing gain) in wireless communication. As quantified by Zheng and Tse [1], given a Multiple Input Multiple Output (MIMO) channel, both gains can, in fact, be simultaneously obtained, but there is a fundamental tradeoff (called the Diversity-Multiplexing Gain (DM-G) tradeoff) between how much of each type of gain, any coding scheme can extract. Space-time codes (STC's) can be employed to make use of these advantages offered by multiple antennas. STC's can be broadly classified in two categories; namely space-time block codes (STBC) and space-time trellis codes (STTC). STTCs are known to have better bit error rate performance than STBCs, but with a penalty in decoding complexity. Also, for STTCs, the frame length is assumed to be finite and hence zeros are forced towards the end of the frame (called the trailing zeros), inducing rate loss. In this paper, we derive an upper bound on the DM-G tradeoff of full-rate STTCs with non-vanishing determinant (NVD). Also, we show that the full-rate STTCs with NVD are optimal under the DM-G tradeoff for any number of transmit and receive antennas, neglecting the rate loss due to trailing zeros. Next we give a explicit generalized full-rate STTC construction for any number of states of the trellis, which achieves the optimal DM-G tradeoff for any number of transmit and receive antennas, neglecting the rate loss due to trailing zeros.

Multiple antennas can be used for increasing the amount of diversity (diversity gain) or increasing the data rate (the number of degrees of freedom or spatial multiplexing gain) in wireless communication. As quantified by Zheng and Tse, given a multiple-input-multiple-output (MIMO) channel, both gains can, in fact, be simultaneously obtained, but there is a fundamental tradeoff (called the Diversity-Multiplexing Gain (DM-G) tradeoff) between how much of each type of gain, any coding scheme can extract. Space-time codes (STCs) can be employed to make use of these advantages offered by multiple antennas. Space-Time Trellis Codes (STTCs) are known to have better bit error rate performance than Space-Time Block Codes (STBCs), but with a penalty in decoding complexity. Also, for STTCs, the frame length is assumed to be finite and hence zeros are forced towards the end of the frame (called the trailing zeros), inducing rate loss. In this correspondence, we derive an upper bound on the DM-G tradeoff of full-rate STTCs with nonvanishing determinant (NVD). Also, we show that the full-rate STTCs with NVD are optimal under the DM-G tradeoff for any number of transmit and receive antennas, neglecting the rate loss due to trailing zeros. Next, we give an explicit generalized full-rate STTC construction for any number of states of the trellis, which achieves the optimal DM-G tradeoff for any number of transmit and receive antennas, neglecting the rate loss due to trailing zeros

Multiple antennas can be used for increasing the amount of diversity (diversity gain) or increasing the data rate (the number of degrees of freedom or spatial multiplexing gain) in wireless communication. As quantified by Zheng and Tse, given a multiple input multiple output (MIMO) channel, both gains can, in fact, be simultaneously obtained, but there is a fundamental tradeoff (called the diversity-multiplexing tradeoff) between how much of each type of gain any coding scheme can extract. It is well known that space-time trellis codes (STTC) can be used to achieve full-diversity and better coding gain than space-time block codes (STBC). There have many STBC constructions, which achieve the diversity-multiplexing tradeoff, but to the best of our knowledge no such construction is proposed for the case of STTC. A delay diversity scheme used to construct STTC introduced in Tarokh et al. (2002) is known to achieve full-diversity, for any number of transmit antennas. In this paper, we show that the delay diversity scheme can achieve the optimal diversity-multiplexing tradeoff, only for one receive antenna. Then we propose a generalized construction of a high-rate generalized coded delay diversity scheme (HRGCDD). We show that the HRGCDD scheme meets both the extreme points (corresponding to zero diversity gain and zero multiplexing gain) of the optimal diversity-multiplexing tradeoff curve for any number of transmit and receive antennas. Also by using the HRGCDD scheme we construct STTC for 2 transmit antennas. Furthermore we also show that the new proposed STTC achieves the optimal diversity-multiplexing tradeoff for 2 transmit and 2 receive antennas by simulation.

For the case of a quasi-static fading channel, high rate space-time trellis codes have already been constructed by concatenating multiple trellis coded modulation (MTCM) and space-time block codes (STBC), called the STBC-MTCM scheme. The focus in all these constructions was to increase the rate of transmission by using more than one orthogonal design while retaining the diversity advantage, and little attention was paid to increasing the coding gain advantage. We present a systematic approach by which STTCs can be constructed by the STBC-MTCM scheme, which achieve high rate, full diversity and increased coding gain advantage over the existing codes under certain conditions. Also we a present a systematic approach, to construct STTCs by STBC-MTCM codes which can achieve any given diversity for the case of block-fading channel. The codes constructed for block-fading channels trade-off the rate of transmission and the number of states of the trellis.