Average-Case Analysis of Greedy Matching for Large-Scale D2D Resource Sharing
- 22 May 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 23 (5) , 3707-3721
Abstract
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.Keywords
All Related Versions
Funding Information
- Ministry of Education - Singapore (MOE-T2EP20121-0001)
This publication has 30 references indexed in Scilit:
- Adaptive Capacity Task Offloading in Multi-Hop D2D-Based Social Industrial IoTIEEE Transactions on Network Science and Engineering, 2022
- REMOS-IoT-A Relay and Mobility Scheme for Improved IoT Communication PerformanceIEEE Access, 2021
- Peer-to-peer energy sharing in mobile networks: Applications, challenges, and open problemsAd Hoc Networks, 2020
- Social-Aware Incentive Mechanisms for D2D Resource Sharing in IIoTIEEE Transactions on Industrial Informatics, 2019
- Collaborative Caching and Matching for D2D Content SharingIEEE Wireless Communications, 2018
- Delay-Constrained Utility Maximization for Video Ads Push in Mobile Opportunistic D2D NetworksIEEE Internet of Things Journal, 2018
- Exploiting Massive D2D Collaboration for Energy-Efficient Mobile Edge ComputingIEEE Wireless Communications, 2017
- Minimum-Cost Crowdsourcing with Coverage Guarantee in Mobile Opportunistic D2D NetworksIEEE Transactions on Mobile Computing, 2017
- D2D Fogging: An Energy-Efficient and Incentive-Aware Task Offloading Framework via Network-assisted D2D CollaborationIEEE Journal on Selected Areas in Communications, 2016
- Cooperative Local Caching under Heterogeneous File PreferencesIEEE Transactions on Communications, 2016