SGShuqin Gao

Shuqin Gao

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Shuqin Gao has a total of 5 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Average-Case Analysis of Greedy Matching for Large-Scale D2D Resource Sharing

    by Shuqin Gao, Costas A. Courcoubetis, Lingjie Duan

    Given the proximity of many wireless users and their diversity in consuming local resources (e.g., data-plans, computation and energy resources), device-to-device (D2D) resource sharing is a promising approach towards realizing a sharing economy. This paper adopts an easy-to-implement greedy matching algorithm with distributed fashion and only sub-linear $O(\log n)$ parallel complexity (in user number $n$ ) for large-scale D2D sharing. Practical cases indicate that the greedy matching's average performance is far better than the worst-case approximation ratio 50% as compared to the optimum. However, there is no rigorous average-case analysis in the literature to back up such encouraging findings and this paper is the first to present such analysis for multiple representative classes of graphs. For 1D linear networks, we prove that our greedy algorithm performs better than 86.5% of the optimum. For 2D grids, though dynamic programming cannot be directly applied, we still prove this average performance ratio to be above 76%. For the more challenging Erdos-Rényi random graphs, we equivalently reduce to the asymptotic analysis of random trees and successfully prove a ratio up to 79%. Finally, we conduct experiments using real data to simulate realistic D2D networks, and show that our analytical performance measure approximates well practical cases.


  • Distributed Double Auction Mechanisms for Large-Scale Device-to-Device Resource Trading

    by Shuqin Gao, Costas A. Courcoubetis, Lingjie Duan

    While some mobile users in wireless networks may experience temporal scarcity of wireless network resources such as data plan, computation capacity and energy storage, some others may leave them underutilized. If the appropriate market existed, users connected locally with D2D links could exchange such resources with low communication cost and realize significant efficiency gains by reducing waste and achieving resource pooling. This paper proposes such a D2D trading market that scales for large numbers of users. Contrary to traditional resource allocation solutions that are mostly centralized, our double auction mechanism exploits local D2D connectivity and uses distributed computation to achieve near-optimal allocative efficiency. The final prices for each matched pair of buyer and seller are adjusted in a way to induce incentive compatibility and depend on their own declarations in terms of quantity and valuation. We prove that the overall mechanism has significant social welfare gains compared to other widely-used distributed pricing mechanisms. It is also individually rational, ex-ante budget balanced using a subscription fee, and robust to perturbations of the model parameters. To render the system fully manipulation-proof, we further propose a distributed auditing scheme that prevents users from altering the decentralized computation to increase their profits. Finally, we model the repeated execution of the mechanism and determine the best trading frequency by taking into account the arrivals and departures of new participants.