Source author record

Ye Xia

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

ResearcherUnclaimed source record

Networking and Internet Architecture cs.CY Information Theory math.IT Social and Information Networks

Catalog footprint

What is connected

4works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2020arXiv

How to Return to Normalcy: Fast and Comprehensive Contact Tracing of COVID-19 through Proximity Sensing Using Mobile Devices

We outline a contact-tracing strategy based on proximity sensing using mobile devices. We discuss what an ideal system should look like and what it can do. We show that, when adopted sufficiently broadly, such a contact-tracing strategy can bring COVID-19 under complete control, end the need of social distancing, and return the society to full normalcy. We also review some of the challenges faced by the current generation of proximity-sensing technologies, including Bluetooth Low Energy used by phones, and consider both interim and longer-term solutions. Our main contribution is that we reason through why such a contact-tracing strategy is likely to achieve the stated goal of returning to full normalcy. Using probabilistic models, we show that universal adoption is not necessary to achieve the stated goal, thus there is some room for exceptions; however, the adoption rate needs to be very high, e.g., above $95\%$ depending on the disease parameters. With more vigilance in disease surveillance to detect mild cases earlier, the number may be brought down to about $90\%$. The results call for deployment effort to be led by public authorities at the state or federal level so that the required adoption rate can be reached and the tracing coverage is wide enough to be relevant for disease control.

preprint2013arXiv

Algorithms and Stability Analysis for Content Distribution over Multiple Multicast Trees

The paper investigates theoretical issues in applying the universal swarming technique to efficient content distribution. In a swarming session, a file is distributed to all the receivers by having all the nodes in the session exchange file chunks. By universal swarming, not only all the nodes in the session, but also some nodes outside the session may participate in the chunk exchange to improve the distribution performance. We present a universal swarming model where the chunks are distributed along different Steiner trees rooted at the source and covering all the receivers. We assume chunks arrive dynamically at the sources and focus on finding stable universal swarming algorithms. To achieve the throughput region, universal swarming usually involves a tree-selection subproblem of finding a min-cost Steiner tree, which is NP-hard. We propose a universal swarming scheme that employs an approximate tree-selection algorithm. We show that it achieves network stability for a reduced throughput region, where the reduction ratio is no more than the approximation ratio of the tree-selection algorithm. We propose a second universal swarming scheme that employs a randomized tree-selection algorithm. It achieves the throughput region, but with a weaker stability result. The proposed schemes and their variants are expected to be useful for infrastructure-based content distribution networks with massive content and relatively stable network environment.

preprint2013arXiv

Content Distribution by Multiple Multicast Trees and Intersession Cooperation: Optimal Algorithms and Approximations

In traditional massive content distribution with multiple sessions, the sessions form separate overlay networks and operate independently, where some sessions may suffer from insufficient resources even though other sessions have excessive resources. To cope with this problem, we consider the universal swarming approach, which allows multiple sessions to cooperate with each other. We formulate the problem of finding the optimal resource allocation to maximize the sum of the session utilities and present a subgradient algorithm which converges to the optimal solution in the time-average sense. The solution involves an NP-hard subproblem of finding a minimum-cost Steiner tree. We cope with this difficulty by using a column generation method, which reduces the number of Steiner-tree computations. Furthermore, we allow the use of approximate solutions to the Steiner-tree subproblem. We show that the approximation ratio to the overall problem turns out to be no less than the reciprocal of the approximation ratio to the Steiner-tree subproblem. Simulation results demonstrate that universal swarming improves the performance of resource-poor sessions with negligible impact to resource-rich sessions. The proposed approach and algorithm are expected to be useful for infrastructure-based content distribution networks with long-lasting sessions and relatively stable network environment.

preprint2011arXiv

Performance Guarantee under Longest-Queue-First Schedule in Wireless Networks

Efficient link scheduling in a wireless network is challenging. Typical optimal algorithms require solving an NP-hard sub-problem. To meet the challenge, one stream of research focuses on finding simpler sub-optimal algorithms that have low complexity but high efficiency in practice. In this paper, we study the performance guarantee of one such scheduling algorithm, the Longest-Queue-First (LQF) algorithm. It is known that the LQF algorithm achieves the full capacity region, $Λ$, when the interference graph satisfies the so-called local pooling condition. For a general graph $G$, LQF achieves (i.e., stabilizes) a part of the capacity region, $σ^*(G) Λ$, where $σ^*(G)$ is the overall local pooling factor of the interference graph $G$ and $σ^*(G) \leq 1$. It has been shown later that LQF achieves a larger rate region, $Σ^*(G) Λ$, where $Σ^ (G)$ is a diagonal matrix. The contribution of this paper is to describe three new achievable rate regions, which are larger than the previously-known regions. In particular, the new regions include all the extreme points of the capacity region and are not convex in general. We also discover a counter-intuitive phenomenon in which increasing the arrival rate may sometime help to stabilize the network. This phenomenon can be well explained using the theory developed in the paper.