BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ness B. Shroff

Ness B. Shroff appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITNetworking and Internet ArchitectureSystems and Controlmath.OCMachine LearningPerformanceCryptography and SecurityDistributed, Parallel, and Cluster Computingeess.SYArtificial IntelligenceComputer Science and Game Theorymath.STSocial and Information NetworksStatistics Theory

Catalog footprint

What is connected

44works
15topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

44 published item(s)

preprint2023arXiv

DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization

Decentralized bilevel optimization has received increasing attention recently due to its foundational role in many emerging multi-agent learning paradigms (e.g., multi-agent meta-learning and multi-agent reinforcement learning) over peer-to-peer edge networks. However, to work with the limited computation and communication capabilities of edge networks, a major challenge in developing decentralized bilevel optimization techniques is to lower sample and communication complexities. This motivates us to develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale stochastic approximation with momentum and gradient-tracking). The contributions of this paper are as follows: i) our DIAMOND algorithm adopts a single-loop structure rather than following the natural double-loop structure of bilevel optimization, which offers low computation and implementation complexity; ii) compared to existing approaches, the DIAMOND algorithm does not require any full gradient evaluations, which further reduces both sample and computational complexities; iii) through a careful integration of momentum information and gradient tracking techniques, we show that the DIAMOND algorithm enjoys $\mathcal{O}(ε^{-3/2})$ in sample and communication complexities for achieving an $ε$-stationary solution, both of which are independent of the dataset sizes and significantly outperform existing works. Extensive experiments also verify our theoretical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Incentive Design and Profit Sharing in Multi-modal Transportation Network

We consider the situation where multiple transportation service providers cooperate to offer an integrated multi-modal platform to enhance the convenience to the passengers through ease in multi-modal journey planning, payment, and first and last mile connectivity. This market structure allows the multi-modal platform to coordinate profits across modes and also provide incentives to the passengers. Accordingly, in this paper, we use cooperative game theory coupled with the hyperpath-based stochastic user equilibrium framework to study such a market. We assume that the platform sets incentives (price discount or excess charge on passengers) along every edge in the transportation network. We derive the continuity and monotonicity properties of the equilibrium flow with respect to the incentives along every edge. The optimal incentives that maximize the profit of the platform are obtained through a two time-scale stochastic approximation algorithm. We use the asymmetric Nash bargaining solution to design a fair profit sharing scheme among the service providers. We show that the profit for each service provider increases after cooperation on such a platform. Finally, we complement the theoretical results through two numerical simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Interference Constrained Beam Alignment for Time-Varying Channels via Kernelized Bandits

To fully utilize the abundant spectrum resources in millimeter wave (mmWave), Beam Alignment (BA) is necessary for large antenna arrays to achieve large array gains. In practical dynamic wireless environments, channel modeling is challenging due to time-varying and multipath effects. In this paper, we formulate the beam alignment problem as a non-stationary online learning problem with the objective to maximize the received signal strength under interference constraint. In particular, we employ the non-stationary kernelized bandit to leverage the correlation among beams and model the complex beamforming and multipath channel functions. Furthermore, to mitigate interference to other user equipment, we leverage the primal-dual method to design a constrained UCB-type kernelized bandit algorithm. Our theoretical analysis indicates that the proposed algorithm can adaptively adjust the beam in time-varying environments, such that both the cumulative regret of the received signal and constraint violations have sublinear bounds with respect to time. This result is of independent interest for applications such as adaptive pricing and news ranking. In addition, the algorithm assumes the channel is a black-box function and does not require any prior knowledge for dynamic channel modeling, and thus is applicable in a variety of scenarios. We further show that if the information about the channel variation is known, the algorithm will have better theoretical guarantees and performance. Finally, we conduct simulations to highlight the effectiveness of the proposed algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Generalization Power of the Overfitted Three-Layer Neural Tangent Kernel Model

In this paper, we study the generalization performance of overparameterized 3-layer NTK models. We show that, for a specific set of ground-truth functions (which we refer to as the "learnable set"), the test error of the overfitted 3-layer NTK is upper bounded by an expression that decreases with the number of neurons of the two hidden layers. Different from 2-layer NTK where there exists only one hidden-layer, the 3-layer NTK involves interactions between two hidden-layers. Our upper bound reveals that, between the two hidden-layers, the test error descends faster with respect to the number of neurons in the second hidden-layer (the one closer to the output) than with respect to that in the first hidden-layer (the one closer to the input). We also show that the learnable set of 3-layer NTK without bias is no smaller than that of 2-layer NTK models with various choices of bias in the neurons. However, in terms of the actual generalization performance, our results suggest that 3-layer NTK is much less sensitive to the choices of bias than 2-layer NTK, especially when the input dimension is large.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Sampling for Data Freshness: Unreliable Transmissions with Random Two-way Delay

In this paper, we aim to design an optimal sampler for a system in which fresh samples of a signal (source) are sent through an unreliable channel to a remote estimator, and acknowledgments are sent back over a feedback channel. Both the forward and feedback channels could have random transmission times due to time varying channel conditions. Motivated by distributed sensing, the estimator can estimate the real-time value of the source signal by combining the signal samples received through the channel and the noisy signal observations collected from a local sensor. We prove that the estimation error is a non-decreasing function of the Age of Information (AoI) for the received signal samples and design an optimal sampling strategy that minimizes the long-term average estimation error subject to a sampling rate constraint. The sampling strategy is also optimal for minimizing the long-term average of general non-decreasing functions of the AoI. The optimal sampler design follows a randomized threshold strategy: If the last transmission was successful, the source waits until the expected estimation error upon delivery exceeds a threshold and then sends out a new sample. If the last transmission fails, the source immediately sends out a new sample without waiting. The threshold is the root of a fixed-point equation and can be solved with low complexity (e.g., by bisection search). The optimal sampling strategy holds for general transmission time distributions of the forward and feedback channels. Numerical simulations are provided to compare different sampling policies.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Age-Optimal Low-Power Status Update over Time-Correlated Fading Channel

In this paper, we consider transmission scheduling in a status update system, where updates are generated periodically and transmitted over a Gilbert-Elliott fading channel. The goal is to minimize the long-run average age of information (AoI) at the destination under an average energy constraint. We consider two practical cases to obtain channel state information (CSI): (i) \emph{without channel sensing} and (ii) \emph{with delayed channel sensing}. For case (i), the channel state is revealed when an ACK/NACK is received at the transmitter following a transmission, but when no transmission occurs, the channel state is not revealed. Thus, we have to design schemes that balance tradeoffs across energy, AoI, channel exploration, and channel exploitation. The problem is formulated as a constrained partially observable Markov decision process problem (POMDP). To reduce algorithm complexity, we show that the optimal policy is a randomized mixture of no more than two stationary deterministic policies each of which is of a threshold-type in the belief on the channel. For case (ii), (delayed) CSI is available at the transmitter via channel sensing. In this case, the tradeoff is only between the AoI and energy consumption and the problem is formulated as a constrained MDP. The optimal policy is shown to have a similar structure as in case (i) but with an AoI associated threshold. Finally, the performance of the proposed structure-aware algorithms is evaluated numerically and compared with a Greedy policy.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Low-Power Status Updates via Sleep-Wake Scheduling

We consider the problem of optimizing the freshness of status updates that are sent from a large number of low-power sources to a common access point. The source nodes utilize carrier sensing to reduce collisions and adopt an asynchronized sleep-wake scheduling strategy to achieve a target network lifetime (e.g., 10 years). We use age of information (AoI) to measure the freshness of status updates, and design sleep-wake parameters for minimizing the weighted-sum peak AoI of the sources, subject to per-source battery lifetime constraints. When the sensing time (i.e., the time duration of carrier sensing) is zero, this sleep-wake design problem can be solved by resorting to a two-layer nested convex optimization procedure; however, for positive sensing times, the problem is non-convex. We devise a low-complexity solution to solve this problem and prove that, for practical sensing times that are short, the solution is within a small gap from the optimum AoI performance. When the mean transmission time of status-update packets is unknown, we devise a reinforcement learning algorithm that adaptively performs the following two tasks in an ``efficient way'': a) it learns the unknown parameter, b) it also generates efficient controls that make channel access decisions. We analyze its performance by quantifying its ``regret'', i.e., the sub-optimality gap between its average performance and the average performance of a controller that knows the mean transmission time. Our numerical and NS-3 simulation results show that our solution can indeed elongate the batteries lifetime of information sources, while providing a competitive AoI performance.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Partially Observable MDP Approach for Sequential Testing for Infectious Diseases such as COVID-19

The outbreak of the novel coronavirus (COVID-19) is unfolding as a major international crisis whose influence extends to every aspect of our daily lives. Effective testing allows infected individuals to be quarantined, thus reducing the spread of COVID-19, saving countless lives, and helping to restart the economy safely and securely. Developing a good testing strategy can be greatly aided by contact tracing that provides health care providers information about the whereabouts of infected patients in order to determine whom to test. Countries that have been more successful in corralling the virus typically use a ``test, treat, trace, test'' strategy that begins with testing individuals with symptoms, traces contacts of positively tested individuals via a combinations of patient memory, apps, WiFi, GPS, etc., followed by testing their contacts, and repeating this procedure. The problem is that such strategies are myopic and do not efficiently use the testing resources. This is especially the case with COVID-19, where symptoms may show up several days after the infection (or not at all, there is evidence to suggest that many COVID-19 carriers are asymptotic, but may spread the virus). Such greedy strategies, miss out population areas where the virus may be dormant and flare up in the future. In this paper, we show that the testing problem can be cast as a sequential learning-based resource allocation problem with constraints, where the input to the problem is provided by a time-varying social contact graph obtained through various contact tracing tools. We then develop efficient learning strategies that minimize the number of infected individuals. These strategies are based on policy iteration and look-ahead rules. We investigate fundamental performance bounds, and ensure that our solution is robust to errors in the input graph as well as in the tests themselves.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Battle between Rate and Error in Minimizing Age of Information

In this paper, we consider a status update system, in which update packets are sent to the destination via a wireless medium that allows for multiple rates, where a higher rate also naturally corresponds to a higher error probability. The data freshness is measured using age of information, which is defined as the age of the recent update at the destination. A packet that is transmitted with a higher rate, will encounter a shorter delay and a higher error probability. Thus, the choice of the transmission rate affects the age at the destination. In this paper, we design a low-complexity scheduler that selects between two different transmission rate and error probability pairs to be used at each transmission epoch. This problem can be cast as a Markov Decision Process. We show that there exists a threshold-type policy that is age-optimal. More importantly, we show that the objective function is quasi-convex or non-decreasing in the threshold, based on to the system parameters values. This enables us to devise a \emph{low-complexity algorithm} to minimize the age. These results reveal an interesting phenomenon: While choosing the rate with minimum mean delay is delay-optimal, this does not necessarily minimize the age.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fleet Sizing and Charger Allocation in Electric Vehicle Sharing Systems

In this paper, we propose a closed queueing network model for performance analysis of electric vehicle sharing systems with a certain number of chargers in each neighborhood. Depending on the demand distribution, we devise algorithms to compute the optimal fleet size and number of chargers required to maximize profit while maintaining a certain quality of service. We show that the profit is concave with respect to the fleet size and the number of chargers at each charging point. If more chargers are installed within the city, we show that it can not only reduce the fleet size, but it also improves the availability of vehicles at all the points within a city. We further show through simulation that two slow chargers may outperform one fast charger when the variance of charging time becomes relatively large in comparison to the mean charging time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multi-Armed Bandits with Local Differential Privacy

This paper investigates the problem of regret minimization for multi-armed bandit (MAB) problems with local differential privacy (LDP) guarantee. In stochastic bandit systems, the rewards may refer to the users' activities, which may involve private information and the users may not want the agent to know. However, in many cases, the agent needs to know these activities to provide better services such as recommendations and news feeds. To handle this dilemma, we adopt differential privacy and study the regret upper and lower bounds for MAB algorithms with a given LDP guarantee. In this paper, we prove a lower bound and propose algorithms whose regret upper bounds match the lower bound up to constant factors. Numerical experiments also confirm our conclusions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Achieving Delay Rate-function Optimality in OFDM Downlink with Time-correlated Channels

There have been recent attempts to develop scheduling schemes for downlink transmission in a single cell of a multi-channel (e.g., OFDM-based) cellular network. These works have been quite promising in that they have developed low-complexity index scheduling policies that are delay-optimal (in a large deviation rate-function sense). However, these policies require that the channel is ON or OFF in each time-slot with a fixed probability (i.e., there is no memory in the system), while the reality is that due to channel fading and doppler shift, channels are often time-correlated in these cellular systems. Thus, an important open question is whether one can find simple index scheduling policies that are delay-optimal even when the channels are time-correlated. In this paper, we attempt to answer this question for time-correlated ON/OFF channels. In particular, we show that the class of oldest packets first (OPF) policies that give a higher priority to packets with a large delay is delay rate-function optimal under two conditions: 1) The channel is non-negatively correlated, and 2) The distribution of the OFF period is geometric. We use simulations to further elucidate the theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Delay-Optimal Buffer-Aware Scheduling with Adaptive Transmission

In this work, we aim to obtain the optimal tradeoff between the average delay and the average power consumption in a communication system. In our system, the arrivals occur at each timeslot according to a Bernoulli arrival process and are buffered at the transmitter. The transmitter determines the scheduling policy of how many packets to transmit under an average power constraint. The power is assumed to be an increasing and convex function of the number of packets transmitted in each timeslot to capture the realism in communication systems. We also consider a finite buffer and allow the scheduling decision to depend on the buffer occupancy. This problem is modelled as a Constrained Markov Decision Process (CMDP). We first prove that the optimal policy of the (Lagrangian) relaxation of the CMDP is deterministic and threshold-based. We then show that the optimal delay-power tradeoff curve is convex and piecewise linear, where each of the vertices are obtained by the optimal solution to the relaxed problem. This allows us to show the optimal policies of the CMDP are threshold-based, and hence can be implemented by a proposed efficient algorithm. The theoretical results and the algorithm are validated by Linear Programming and simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Impact of Stealthy Attacks on Smart Grid Performance: Tradeoffs and Implications

The smart grid is envisioned to significantly enhance the efficiency of energy consumption, by utilizing two-way communication channels between consumers and operators. For example, operators can opportunistically leverage the delay tolerance of energy demands in order to balance the energy load over time, and hence, reduce the total operational cost. This opportunity, however, comes with security threats, as the grid becomes more vulnerable to cyber-attacks. In this paper, we study the impact of such malicious cyber-attacks on the energy efficiency of the grid in a simplified setup. More precisely, we consider a simple model where the energy demands of the smart grid consumers are intercepted and altered by an active attacker before they arrive at the operator, who is equipped with limited intrusion detection capabilities. We formulate the resulting optimization problems faced by the operator and the attacker and propose several scheduling and attack strategies for both parties. Interestingly, our results show that, as opposed to facilitating cost reduction in the smart grid, increasing the delay tolerance of the energy demands potentially allows the attacker to force increased costs on the system. This highlights the need for carefully constructed and robust intrusion detection mechanisms at the operator.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

When to Reset Your Keys: Optimal Timing of Security Updates via Learning

Cybersecurity is increasingly threatened by advanced and persistent attacks. As these attacks are often designed to disable a system (or a critical resource, e.g., a user account) repeatedly, it is crucial for the defender to keep updating its security measures to strike a balance between the risk of being compromised and the cost of security updates. Moreover, these decisions often need to be made with limited and delayed feedback due to the stealthy nature of advanced attacks. In addition to targeted attacks, such an optimal timing policy under incomplete information has broad applications in cybersecurity. Examples include key rotation, password change, application of patches, and virtual machine refreshing. However, rigorous studies of optimal timing are rare. Further, existing solutions typically rely on a pre-defined attack model that is known to the defender, which is often not the case in practice. In this work, we make an initial effort towards achieving optimal timing of security updates in the face of unknown stealthy attacks. We consider a variant of the influential FlipIt game model with asymmetric feedback and unknown attack time distribution, which provides a general model to consecutive security updates. The defender's problem is then modeled as a time associative bandit problem with dependent arms. We derive upper confidence bound based learning policies that achieve low regret compared with optimal periodic defense strategies that can only be derived when attack time distributions are known.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Downlink Scheduling over Markovian Fading Channels

We consider the scheduling problem in downlink wireless networks with heterogeneous, Markov-modulated, ON/OFF channels. It is well-known that the performance of scheduling over fading channels relies heavily on the accuracy of the available Channel State Information (CSI), which is costly to acquire. Thus, we consider the CSI acquisition via a practical ARQ-based feedback mechanism whereby channel states are revealed at the end of only scheduled users' transmissions. In the assumed presence of temporally-correlated channel evolutions, the desired scheduler must optimally balance the exploitation-exploration trade-off, whereby it schedules transmissions both to exploit those channels with up-to-date CSI and to explore the current state of those with outdated CSI. In earlier works, Whittle's Index Policy had been suggested as a low-complexity and high-performance solution to this problem. However, analyzing its performance in the typical scenario of statistically heterogeneous channel state processes has remained elusive and challenging, mainly because of the highly-coupled and complex dynamics it possesses. In this work, we overcome these difficulties to rigorously establish the asymptotic optimality properties of Whittle's Index Policy in the limiting regime of many users. More specifically: (1) we prove the local optimality of Whittle's Index Policy, provided that the initial state of the system is within a certain neighborhood of a carefully selected state; (2) we then establish the global optimality of Whittle's Index Policy under a recurrence assumption that is verified numerically for our problem. These results establish that Whittle's Index Policy possesses analytically provable optimality characteristics for scheduling over heterogeneous and temporally-correlated channels.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Low-complexity Optimal Scheduling over Correlated Fading Channels with ARQ Feedback

We investigate the downlink scheduling problem under Markovian ON/OFF fading channels, where the instantaneous channel state information is not directly accessible, but is revealed via ARQ-type feedback. The scheduler can exploit the temporal correlation/channel memory inherent in the Markovian channels to improve network performance. However, designing low-complexity and throughput-optimal algorithms under temporal correlation is a challenging problem. In this paper, we find that under an average number of transmissions constraint, a low-complexity index policy is throughput-optimal. The policy uses Whittle's index value, which was previously used to capture opportunistic scheduling under temporally correlated channels. Our results build on the interesting finding that, under the intricate queue length and channel memory evolutions, the importance of scheduling a user is captured by a simple multiplication of its queue length and Whittle's index value. The proposed queue-based index policy has provably low complexity. Numerical results show that significant throughput gains can be realized by exploiting the channel memory using the proposed low-complexity policy.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Provably Delay Efficient Data Retrieving in Storage Clouds

One key requirement for storage clouds is to be able to retrieve data quickly. Recent system measurements have shown that the data retrieving delay in storage clouds is highly variable, which may result in a long latency tail. One crucial idea to improve the delay performance is to retrieve multiple data copies by using parallel downloading threads. However, how to optimally schedule these downloading threads to minimize the data retrieving delay remains to be an important open problem. In this paper, we develop low-complexity thread scheduling policies for several important classes of data downloading time distributions, and prove that these policies are either delay-optimal or within a constant gap from the optimum delay performance. These theoretical results hold for an arbitrary arrival process of read requests that may contain finite or infinite read requests, and for heterogeneous MDS storage codes that can support diverse storage redundancy and reliability requirements for different data files. Our numerical results show that the delay performance of the proposed policies is significantly better than that of First-Come- First-Served (FCFS) policies considered in prior work.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Achieving Optimal Throughput and Near-Optimal Asymptotic Delay Performance in Multi-Channel Wireless Networks with Low Complexity: A Practical Greedy Scheduling Policy

In this paper, we focus on the scheduling problem in multi-channel wireless networks, e.g., the downlink of a single cell in fourth generation (4G) OFDM-based cellular networks. Our goal is to design practical scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a class of $O(n^{2.5} \log n)$-complexity hybrid scheduling policies are recently developed to guarantee both rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in the general non-asymptotic setting), their practical complexity is typically high. To address this issue, we develop a simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with a \lower complexity $2n^2+2n$, and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal asymptotic delay performance. Specifically, we show that the rate-function attained by D-SSG for any delay-violation threshold $b$, is no smaller than the maximum achievable rate-function by any scheduling policy for threshold $b-1$. Thus, we are able to achieve a reduction in complexity (from $O(n^{2.5} \log n)$ of the hybrid policies to $2n^2 + 2n$) with a minimal drop in the delay performance. More importantly, in practice, D-SSG generally has a substantially lower complexity than the hybrid policies that typically have a large constant factor hidden in the $O(\cdot)$ notation. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that D-SSG not only guarantees a near-optimal rate-function, but also empirically is virtually indistinguishable from delay-optimal policies.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Constant Delay and Constant Feedback Moving Window Network Coding for Wireless Multicast: Design and Asymptotic Analysis

A major challenge of wireless multicast is to be able to support a large number of users while simultaneously maintaining low delay and low feedback overhead. In this paper, we develop a joint coding and feedback scheme named Moving Window Network Coding with Anonymous Feedback (MWNC-AF) that successfully addresses this challenge. In particular, we show that our scheme simultaneously achieves both a constant decoding delay and a constant feedback overhead, irrespective of the number of receivers $n$, without sacrificing either throughput or reliability. We explicitly characterize the asymptotic decay rate of the tail of the delay distribution, and prove that transmitting a fixed amount of information bits into the MWNC-AF encoder buffer in each time-slot (called "constant data injection process") achieves the fastest decay rate, thus showing how to obtain delay optimality in a large deviation sense. We then investigate the average decoding delay of MWNC-AF, and show that when the traffic load approaches the capacity, the average decoding delay under the constant injection process is at most one half of that under a Bernoulli injection process. In addition, we prove that the per-packet encoding and decoding complexity of MWNC-AF both scale as $O(\log n)$, with the number of receivers $n$. Our simulations further underscore the performance of our scheme through comparisons with other schemes and show that the delay, encoding and decoding complexity are low even for a large number of receivers, demonstrating the efficiency, scalability, and ease of implementability of MWNC-AF.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Network Control without CSI using Rateless Codes for Downlink Cellular Systems

Wireless network scheduling and control techniques (e.g., opportunistic scheduling) rely heavily on access to Channel State Information (CSI). However, obtaining this information is costly in terms of bandwidth, time, and power, and could result in large overhead. Therefore, a critical question is how to optimally manage network resources in the absence of such information. To that end, we develop a cross-layer solution for downlink cellular systems with imperfect (and possibly no) CSI at the transmitter. We use rateless codes to resolve channel uncertainty. To keep the decoding complexity low, we explicitly incorporate time-average block-size constraints, and aim to maximize the system utility. The block-size of a rateless code is determined by both the network control decisions and the unknown CSI of many time slots. Therefore, unlike standard utility maximization problems, this problem can be viewed as a constrained partial observed Markov decision problem (CPOMDP), which is known to be hard due to the "curse of dimensionality." However, by using a modified Lyapunov drift method, we develop a dynamic network control scheme, which yields a total network utility within O(1/Lav) of utility-optimal point achieved by infinite block-size channel codes, where Lav is the enforced value of the time-average block-size of rateless codes. This opens the door of being able to trade complexity/delay for performance gains in the absence of accurate CSI. Our simulation results show that the proposed scheme improves the network throughput by up to 68% over schemes that use fixed-rate codes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scheduling in Time-correlated Wireless Networks with Imperfect CSI and Stringent Constraint

In a wireless network, the efficiency of scheduling algorithms over time-varying channels depends heavily on the accuracy of the Channel State Information (CSI), which is usually quite ``costly'' in terms of consuming network resources. Scheduling in such systems is also subject to stringent constraints such as power and bandwidth, which limit the maximum number of simultaneous transmissions. In the meanwhile, communication channels in wireless systems typically fluctuate in a time-correlated manner. We hence design schedulers to exploit the temporal-correlation inherent in channels with memory and ARQ-styled feedback from the users for better channel state knowledge, under the assumption of Markovian channels and the stringent constraint on the maximum number of simultaneously active users. We model this problem under the framework of a Partially Observable Markov Decision Processes. In recent work, a low-complexity optimal solution was developed for this problem under a long-term time-average resource constraint. However, in real systems with instantaneous resource constraints, how to optimally exploit the temporal correlation and satisfy realistic stringent constraint on the instantaneous service remains elusive. In this work, we incorporate a stringent constraint on the simultaneously scheduled users and propose a low-complexity scheduling algorithm that dynamically implements user scheduling and dummy packet broadcasting. We show that the throughput region of the optimal policy under the long-term average resource constraint can be asymptotically achieved in the stringent constrained scenario by the proposed algorithm, in the many users limiting regime.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scheduling of Multicast and Unicast Services under Limited Feedback by using Rateless Codes

Many opportunistic scheduling techniques are impractical because they require accurate channel state information (CSI) at the transmitter. In this paper, we investigate the scheduling of unicast and multicast services in a downlink network with a very limited amount of feedback information. Specifically, unicast users send imperfect (or no) CSI and infrequent acknowledgements (ACKs) to a base station, and multicast users only report infrequent ACKs to avoid feedback implosion. We consider the use of physical-layer rateless codes, which not only combats channel uncertainty, but also reduces the overhead of ACK feedback. A joint scheduling and power allocation scheme is developed to realize multiuser diversity gain for unicast service and multicast gain for multicast service. We prove that our scheme achieves a near-optimal throughput region. Our simulation results show that our scheme significantly improves the network throughput over schemes employing fixed-rate codes or using only unicast communications.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

When Queueing Meets Coding: Optimal-Latency Data Retrieving Scheme in Storage Clouds

In this paper, we study the problem of reducing the delay of downloading data from cloud storage systems by leveraging multiple parallel threads, assuming that the data has been encoded and stored in the clouds using fixed rate forward error correction (FEC) codes with parameters (n, k). That is, each file is divided into k equal-sized chunks, which are then expanded into n chunks such that any k chunks out of the n are sufficient to successfully restore the original file. The model can be depicted as a multiple-server queue with arrivals of data retrieving requests and a server corresponding to a thread. However, this is not a typical queueing model because a server can terminate its operation, depending on when other servers complete their service (due to the redundancy that is spread across the threads). Hence, to the best of our knowledge, the analysis of this queueing model remains quite uncharted. Recent traces from Amazon S3 show that the time to retrieve a fixed size chunk is random and can be approximated as a constant delay plus an i.i.d. exponentially distributed random variable. For the tractability of the theoretical analysis, we assume that the chunk downloading time is i.i.d. exponentially distributed. Under this assumption, we show that any work-conserving scheme is delay-optimal among all on-line scheduling schemes when k = 1. When k > 1, we find that a simple greedy scheme, which allocates all available threads to the head of line request, is delay optimal among all on-line scheduling schemes. We also provide some numerical results that point to the limitations of the exponential assumption, and suggest further research directions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Capacity of Compound MIMO Gaussian Channels with Additive Uncertainty

This paper considers reliable communications over a multiple-input multiple-output (MIMO) Gaussian channel, where the channel matrix is within a bounded channel uncertainty region around a nominal channel matrix, i.e., an instance of the compound MIMO Gaussian channel. We study the optimal transmit covariance matrix design to achieve the capacity of compound MIMO Gaussian channels, where the channel uncertainty region is characterized by the spectral norm. This design problem is a challenging non-convex optimization problem. However, in this paper, we reveal that this problem has a hidden convexity property, which can be exploited to map the problem into a convex optimization problem. We first prove that the optimal transmit design is to diagonalize the nominal channel, and then show that the duality gap between the capacity of the compound MIMO Gaussian channel and the min-max channel capacity is zero, which proves the conjecture of Loyka and Charalambous (IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2048-2063, 2012). The key tools for showing these results are a new matrix determinant inequality and some unitarily invariant properties.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed Cross-Layer Optimization in Wireless Networks: A Second-Order Approach

Due to the rapidly growing scale and heterogeneity of wireless networks, the design of distributed cross-layer optimization algorithms have received significant interest from the networking research community. So far, the standard distributed cross-layer approach in the literature is based on first-order Lagrangian dual decomposition and the subgradient method, which suffers a slow convergence rate. In this paper, we make the first known attempt to develop a distributed Newton's method, which is second-order and enjoys a quadratic convergence rate. However, due to interference in wireless networks, the Hessian matrix of the cross-layer problem has an non-separable structure. As a result, developing a distributed second-order algorithm is far more challenging than its counterpart for wireline networks. Our main results in this paper are two-fold: i) For a special network setting where all links mutually interfere, we derive decentralized closed-form expressions to compute the Hessian inverse; ii) For general wireless networks where the interference relationships are arbitrary, we propose a distributed iterative matrix splitting scheme for the Hessian inverse. These results successfully lead to a new theoretical framework for cross-layer optimization in wireless networks. More importantly, our work contributes to an exciting second-order paradigm shift in wireless networks optimization theory.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed Power Allocation for Coordinated Multipoint Transmissions in Distributed Antenna Systems

This paper investigates the distributed power allocation problem for coordinated multipoint (CoMP) transmissions in distributed antenna systems (DAS). Traditional duality based optimization techniques cannot be directly applied to this problem, because the non-strict concavity of the CoMP transmission's achievable rate with respect to the transmission power induces that the local power allocation subproblems have non-unique optimum solutions. We propose a distributed power allocation algorithm to resolve this non-strict concavity difficulty. This algorithm only requires local information exchange among neighboring base stations serving the same user, and is thus scalable as the network size grows. The step-size parameters of this algorithm are determined by only local user access relationship (i.e., the number of users served by each antenna), but do not rely on channel coefficients. Therefore, the convergence speed of this algorithm is quite robust to different channel fading coefficients. We rigorously prove that this algorithm converges to an optimum solution of the power allocation problem. Simulation results are presented to demonstrate the effectiveness of the proposed power allocation algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Graph-Theoretic Characterization of The Feasibility of The Precoding-Based 3-Unicast Interference Alignment Scheme

A new precoding-based intersession network coding (NC) scheme has recently been proposed, which applies the interference alignment technique, originally devised for wireless interference channels, to the 3-unicast problem of directed acyclic networks. The main result of this work is a graph-theoretic characterization of the feasibility of the 3-unicast interference alignment scheme. To that end, we first investigate several key relationships between the point-to-point network channel gains and the underlying graph structure. Such relationships turn out to be critical when characterizing graph-theoretically the feasibility of precoding-based solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Life-Add: Lifetime Adjustable Design for WiFi Networks with Heterogeneous Energy Supplies

WiFi usage significantly reduces the battery lifetime of handheld devices such as smartphones and tablets, due to its high energy consumption. In this paper, we propose "Life-Add": a Lifetime Adjustable design for WiFi networks, where the devices are powered by battery, electric power, and/or renewable energy. In Life-Add, a device turns off its radio to save energy when the channel is sensed to be busy, and sleeps for a random time period before sensing the channel again. Life-Add carefully controls the devices' average sleep periods to improve their throughput while satisfying their operation time requirement. It is proven that Life-Add achieves near-optimal proportional-fair utility performance for single access point (AP) scenarios. Moreover, Life-Add alleviates the near-far effect and hidden terminal problem in general multiple AP scenarios. Our ns-3 simulations show that Life-Add simultaneously improves the lifetime, throughput, and fairness performance of WiFi networks, and coexists harmoniously with IEEE 802.11.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Low-Complexity Scheduling Policies for Achieving Throughput and Asymptotic Delay Optimality in Multi-Channel Wireless Networks

In this paper, we study the scheduling problem for downlink transmission in a multi-channel (e.g., OFDM-based) wireless network. We focus on a single cell, with the aim of developing a unifying framework for designing low-complexity scheduling policies that can provide optimal performance in terms of both throughput and delay. We develop new easy-to-verify sufficient conditions for rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in general non-asymptotic setting), respectively. The sufficient conditions allow us to prove rate-function delay optimality for a class of Oldest Packets First (OPF) policies and throughput optimality for a large class of Maximum Weight in the Fluid limit (MWF) policies, respectively. By exploiting the special features of our carefully chosen sufficient conditions and intelligently combining policies from the classes of OPF and MWF policies, we design hybrid policies that are both rate-function delay-optimal and throughput-optimal with a complexity of $O(n^{2.5} \log n)$, where $n$ is the number of channels or users. Our sufficient condition is also used to show that a previously proposed policy called Delay Weighted Matching (DWM) is rate-function delay-optimal. However, DWM incurs a high complexity of $O(n^5)$. Thus, our approach yields significantly lower complexity than the only previously designed delay and throughput optimal scheduling policy. We also conduct numerical experiments to validate our theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Optimal Distributed Resource Allocation for Decode-and-Forward Relay Networks

This paper presents a distributed resource allocation algorithm to jointly optimize the power allocation, channel allocation and relay selection for decode-and-forward (DF) relay networks with a large number of sources, relays, and destinations. The well-known dual decomposition technique cannot directly be applied to resolve this problem, because the achievable data rate of DF relaying is not strictly concave, and thus the local resource allocation subproblem may have non-unique solutions. We resolve this non-strict concavity problem by using the idea of the proximal point method, which adds quadratic terms to make the objective function strictly concave. However, the proximal solution adds an extra layer of iterations over typical duality based approaches, which can significantly slow down the speed of convergence. To address this key weakness, we devise a fast algorithm without the need for this additional layer of iterations, which converges to the optimal solution. Our algorithm only needs local information exchange, and can easily adapt to variations of network size and topology. We prove that our distributed resource allocation algorithm converges to the optimal solution. A channel resource adjustment method is further developed to provide more channel resources to the bottleneck links and realize traffic load balance. Numerical results are provided to illustrate the benefits of our algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Providing Probabilistic Guarantees on the Time of Information Spread in Opportunistic Networks

A variety of mathematical tools have been developed for predicting the spreading patterns in a number of varied environments including infectious diseases, computer viruses, and urgent messages broadcast to mobile agent (e.g., humans, vehicles, and mobile devices). These tools have mainly focused on estimating the average time for the spread to reach a fraction (e.g., $α$) of the agents, i.e., the so-called average completion time $E(T_α)$. We claim that providing probabilistic guarantee on the time for the spread $T_α$ rather than only its average gives a much better understanding of the spread, and hence could be used to design improved methods to prevent epidemics or devise accelerated methods for distributing data. To demonstrate the benefits, we introduce a new metric $G_{α, β}$ that denotes the time required to guarantee $α$ completion with probability $β$, and develop a new framework to characterize the distribution of $T_α$ for various spread parameters such as number of seeds, level of contact rates, and heterogeneity in contact rates. We apply our technique to an experimental mobility trace of taxies in Shanghai and show that our framework enables us to allocate resources (i.e., to control spread parameters) for acceleration of spread in a far more efficient way than the state-of-the-art.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

An Analytical Approach to the Adoption of Asymmetric Bidirectional Firewalls: Need for Regulation?

Recent incidents of cybersecurity violations have revealed the importance of having firewalls and other intrusion detection systems to monitor traffic entering and leaving access networks. But the adoption of such security measures is often stymied by `free-riding' effects and `shortsightedness' among Internet service providers (ISPs). In this work, we develop an analytical framework that not only accounts for these issues but also incorporates technological factors, like asymmetries in the performance of bidirectional firewalls. Results on the equilibrium adoption and stability are presented, along with detailed analysis on several policy issues related to social welfare, price of anarchy, and price of shortsightedness.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Delay Asymptotics with Retransmissions and Incremental Redundancy Codes over Erasure Channels

Recent studies have shown that retransmissions can cause heavy-tailed transmission delays even when packet sizes are light-tailed. Moreover, the impact of heavy-tailed delays persists even when packets size are upper bounded. The key question we study in this paper is how the use of coding techniques to transmit information, together with different system configurations, would affect the distribution of delay. To investigate this problem, we model the underlying channel as a Markov modulated binary erasure channel, where transmitted bits are either received successfully or erased. Erasure codes are used to encode information prior to transmission, which ensures that a fixed fraction of the bits in the codeword can lead to successful decoding. We use incremental redundancy codes, where the codeword is divided into codeword trunks and these trunks are transmitted one at a time to provide incremental redundancies to the receiver until the information is recovered. We characterize the distribution of delay under two different scenarios: (I) Decoder uses memory to cache all previously successfully received bits. (II) Decoder does not use memory, where received bits are discarded if the corresponding information cannot be decoded. In both cases, we consider codeword length with infinite and finite support. From a theoretical perspective, our results provide a benchmark to quantify the tradeoff between system complexity and the distribution of delay.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Delay-Based Back-Pressure Scheduling in Multihop Wireless Networks

Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput-optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop.) In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric, and show that the proposed scheme achieves optimal throughput performance. Further, we conduct simulations to support our analytical results, and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Maximizing System Throughput Using Cooperative Sensing in Multi-Channel Cognitive Radio Networks

In Cognitive Radio Networks (CRNs), unlicensed users are allowed to access the licensed spectrum when it is not currently being used by primary users (PUs). In this paper, we study the throughput maximization problem for a multi-channel CRN where each SU can only sense a limited number of channels. We show that this problem is strongly NP-hard, and propose an approximation algorithm with a factor at least $1/2μ$ where $μ\in [1,2]$ is a system parameter reflecting the sensing capability of SUs across channels and their sensing budgets. This performance guarantee is achieved by exploiting a nice structural property of the objective function and constructing a particular matching. Our numerical results demonstrate the advantage of our algorithm compared with both a random and a greedy sensing assignment algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Efficiency-vs-Security Tradeoff in the Smart Grid

The smart grid is envisioned to significantly enhance the efficiency of energy consumption, by utilizing two-way communication channels between consumers and operators. For example, operators can opportunistically leverage the delay tolerance of energy demands in order to balance the energy load over time, and hence, reduce the total operational cost. This opportunity, however, comes with security threats, as the grid becomes more vulnerable to cyber-attacks. In this paper, we study the impact of such malicious cyber-attacks on the energy efficiency of the grid in a simplified setup. More precisely, we consider a simple model where the energy demands of the smart grid consumers are intercepted and altered by an active attacker before they arrive at the operator, who is equipped with limited intrusion detection capabilities. We formulate the resulting optimization problems faced by the operator and the attacker and propose several scheduling and attack strategies for both parties. Interestingly, our results show that, as opposed to facilitating cost reduction in the smart grid, increasing the delay tolerance of the energy demands potentially allows the attacker to force increased costs on the system. This highlights the need for carefully constructed and robust intrusion detection mechanisms at the operator.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Generalized Delay-Capacity Tradeoff of Mobile Networks with Lévy Flight Mobility

In the literature, scaling laws for wireless mobile networks have been characterized under various models of node mobility and several assumptions on how communication occurs between nodes. To improve the realism in the analysis of scaling laws, we propose a new analytical framework. The framework is the first to consider a Lévy flight mobility pattern, which is known to closely mimic human mobility patterns. Also, this is the first work that allows nodes to communicate while being mobile. Under this framework, delays ($\bar{D}$) to obtain various levels of per-node throughput $(λ)$ for Lévy flight are suggested as $\bar{D}(λ) = O(\sqrt{\min (n^{1+α} λ, n^2)})$, where Lévy flight is a random walk of a power-law flight distribution with an exponent $α\in (0,2]$. The same framework presents a new tighter tradeoff $\bar{D}(λ) = O(\sqrt{\max (1,nλ^3)})$ for \textit{i.i.d.} mobility, whose delays are lower than existing results for the same levels of per-node throughput.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Throughput of Rateless Codes over Broadcast Erasure Channels

In this paper, we characterize the throughput of a broadcast network with n receivers using rateless codes with block size K. We assume that the underlying channel is a Markov modulated erasure channel that is i.i.d. across users, but can be correlated in time. We characterize the system throughput asymptotically in n. Specifically, we explicitly show how the throughput behaves for different values of the coding block size K as a function of n, as n approaches infinity. For finite values of K and n, under the more restrictive assumption of Gilbert-Elliott channels, we are able to provide a lower bound on the maximum achievable throughput. Using simulations we show the tightness of the bound with respect to system parameters n and K, and find that its performance is significantly better than the previously known lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Exploiting Channel Memory for Joint Estimation and Scheduling in Downlink Networks

We address the problem of opportunistic multiuser scheduling in downlink networks with Markov-modeled outage channels. We consider the scenario in which the scheduler does not have full knowledge of the channel state information, but instead estimates the channel state information by exploiting the memory inherent in the Markov channels along with ARQ-styled feedback from the scheduled users. Opportunistic scheduling is optimized in two stages: (1) Channel estimation and rate adaptation to maximize the expected immediate rate of the scheduled user; (2) User scheduling, based on the optimized immediate rate, to maximize the overall long term sum-throughput of the downlink. The scheduling problem is a partially observable Markov decision process with the classic 'exploitation vs exploration' trade-off that is difficult to quantify. We therefore study the problem in the framework of Restless Multi-armed Bandit Processes (RMBP) and perform a Whittle's indexability analysis. Whittle's indexability is traditionally known to be hard to establish and the index policy derived based on Whittle's indexability is known to have optimality properties in various settings. We show that the problem of downlink scheduling under imperfect channel state information is Whittle indexable and derive the Whittle's index policy in closed form. Via extensive numerical experiments, we show that the index policy has near-optimal performance. Our work reveals that, under incomplete channel state information, exploiting channel memory for opportunistic scheduling can result in significant performance gains and that almost all of these gains can be realized using an easy-to-implement index policy.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Multiuser Scheduling in a Markov-modeled Downlink using Randomly Delayed ARQ Feedback

We focus on the downlink of a cellular system, which corresponds to the bulk of the data transfer in such wireless systems. We address the problem of opportunistic multiuser scheduling under imperfect channel state information, by exploiting the memory inherent in the channel. In our setting, the channel between the base station and each user is modeled by a two-state Markov chain and the scheduled user sends back an ARQ feedback signal that arrives at the scheduler with a random delay that is i.i.d across users and time. The scheduler indirectly estimates the channel via accumulated delayed-ARQ feedback and uses this information to make scheduling decisions. We formulate a throughput maximization problem as a partially observable Markov decision process (POMDP). For the case of two users in the system, we show that a greedy policy is sum throughput optimal for any distribution on the ARQ feedback delay. For the case of more than two users, we prove that the greedy policy is suboptimal and demonstrate, via numerical studies, that it has near optimal performance. We show that the greedy policy can be implemented by a simple algorithm that does not require the statistics of the underlying Markov channel or the ARQ feedback delay, thus making it robust against errors in system parameter estimation. Establishing an equivalence between the two-user system and a genie-aided system, we obtain a simple closed form expression for the sum capacity of the Markov-modeled downlink. We further derive inner and outer bounds on the capacity region of the Markov-modeled downlink and tighten these bounds for special cases of the system parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Secrecy Outage Capacity of Fading Channels

This paper considers point to point secure communication over flat fading channels under an outage constraint. More specifically, we extend the definition of outage capacity to account for the secrecy constraint and obtain sharp characterizations of the corresponding fundamental limits under two different assumptions on the transmitter CSI (Channel state information). First, we find the outage secrecy capacity assuming that the transmitter has perfect knowledge of the legitimate and eavesdropper channel gains. In this scenario, the capacity achieving scheme relies on opportunistically exchanging private keys between the legitimate nodes. These keys are stored in a key buffer and later used to secure delay sensitive data using the Vernam's one time pad technique. We then extend our results to the more practical scenario where the transmitter is assumed to know only the legitimate channel gain. Here, our achievability arguments rely on privacy amplification techniques to generate secret key bits. In the two cases, we also characterize the optimal power control policies which, interestingly, turn out to be a judicious combination of channel inversion and the optimal ergodic strategy. Finally, we analyze the effect of key buffer overflow on the overall outage probability.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Throughput-Delay Analysis of Random Linear Network Coding for Wireless Broadcasting

In an unreliable single-hop broadcast network setting, we investigate the throughput and decoding-delay performance of random linear network coding as a function of the coding window size and the network size. Our model consists of a source transmitting packets of a single flow to a set of $n$ users over independent erasure channels. The source performs random linear network coding (RLNC) over $k$ (coding window size) packets and broadcasts them to the users. We note that the broadcast throughput of RLNC must vanish with increasing $n$, for any fixed $k.$ Hence, in contrast to other works in the literature, we investigate how the coding window size $k$ must scale for increasing $n$. Our analysis reveals that the coding window size of $Θ(\ln(n))$ represents a phase transition rate, below which the throughput converges to zero, and above which it converges to the broadcast capacity. Further, we characterize the asymptotic distribution of decoding delay and provide approximate expressions for the mean and variance of decoding delay for the scaling regime of $k=ω(\ln(n)).$ These asymptotic expressions reveal the impact of channel correlations on the throughput and delay performance of RLNC. We also show how our analysis can be extended to other rateless block coding schemes such as the LT codes. Finally, we comment on the extension of our results to the cases of dependent channels across users and asymmetric channel model.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Scheduling with Rate Adaptation under Incomplete Knowledge of Channel/Estimator Statistics

In time-varying wireless networks, the states of the communication channels are subject to random variations, and hence need to be estimated for efficient rate adaptation and scheduling. The estimation mechanism possesses inaccuracies that need to be tackled in a probabilistic framework. In this work, we study scheduling with rate adaptation in single-hop queueing networks under two levels of channel uncertainty: when the channel estimates are inaccurate but complete knowledge of the channel/estimator joint statistics is available at the scheduler; and when the knowledge of the joint statistics is incomplete. In the former case, we characterize the network stability region and show that a maximum-weight type scheduling policy is throughput-optimal. In the latter case, we propose a joint channel statistics learning - scheduling policy. With an associated trade-off in average packet delay and convergence time, the proposed policy has a stability region arbitrarily close to the stability region of the network under full knowledge of channel/estimator joint statistics.

0 citations0 reviewsNo code linkedOpen access