Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAverage-Case Analysis of Greedy Matching for D2D Resource Sharing
83
0
0.0
(
0
)
Added by
Shuqin Gao
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given the proximity of many wireless users and their diversity in consuming local resources (e.g., data-plans, computation and even energy resources), device-to-device (D2D) resource sharing is a promising approach towards realizing a sharing economy. In the resulting networked economy, $n$ users segment themselves into sellers and buyers that need to be efficiently matched locally. This paper adopts an easy-to-implement greedy matching algorithm with distributed fashion and only sub-linear $O(log n)$ parallel complexity, which offers a great advantage compared to the optimal but computational-expensive centralized matching. But is it efficient compared to the optimal matching? Extensive simulations indicate that in a large number of practical cases the average loss is no more than $10%$, a far better result than the $50%$ loss bound in the worst case. However, there is no rigorous average-case analysis in the literature to back up such encouraging findings, which is a fundamental step towards supporting the practical use of greedy matching in D2D sharing. This paper is the first to present the rigorous average analysis of certain representative classes of graphs with random parameters, by proposing a new asymptotic methodology. For typical 2D grids with random matching weights we rigorously prove that our greedy algorithm performs better than $84.9%$ of the optimal, while for typical Erdos-Renyi random graphs we prove a lower bound of $79%$ when the graph is neither dense nor sparse. Finally, we use realistic data to show that our random graph models approximate well D2D sharing networks encountered in practice.
rate research
Read More
The sixth generation (6G) network must provide performance superior to previous generations in order to meet the requirements of emerging services and applications, such as multi-gigabit transmission rate, even higher reliability, sub 1 millisecond latency and ubiquitous connection for Internet of Everything. However, with the scarcity of spectrum resources, efficient resource management and sharing is crucial to achieve all these ambitious requirements. One possible technology to enable all of this is blockchain, which has recently gained significance and will be of paramount importance to 6G networks and beyond due to its inherent properties. In particular, the integration of blockchain in 6G will enable the network to monitor and manage resource utilization and sharing efficiently. Hence, in this article, we discuss the potentials of blockchain for resource management and sharing in 6G using multiple application scenarios namely, Internet of things, device-to-device communications, network slicing, and inter-domain blockchain ecosystems.
Small-scale clouds (SCs) often suffer from resource under-provisioning during peak demand, leading to inability to satisfy service level agreements (SLAs) and consequent loss of customers. One approach to address this problem is for a set of autonomous SCs to share resources among themselves in a cost-induced cooperative fashion, thereby increasing their individual capacities (when needed) without having to significantly invest in more resources. A central problem (in this context) is how to properly share resources (for a price) to achieve profitable service while maintaining customer SLAs. To address this problem, in this paper, we propose the SC-Share framework that utilizes two interacting models: (i) a stochastic performance model that estimates the achieved performance characteristics under given SLA requirements, and (ii) a market-based game-theoretic model that (as shown empirically) converges to efficient resource sharing decisions at market equilibrium. Our results include extensive evaluations that illustrate the utility of the proposed framework.
Selecting optimal resources for submitting jobs on a computational Grid or accessing data from a data grid is one of the most important tasks of any Grid middleware. Most modern Grid software today satisfies this responsibility and gives a best-effort performance to solve this problem. Almost all decisions regarding scheduling and data access are made by the software automatically, giving users little or no control over the entire process. To solve this problem, a more interactive set of services and middleware is desired that provides users more information about Grid weather, and gives them more control over the decision making process. This paper presents a set of services that have been developed to provide more interactive resource management capabilities within the Grid Analysis Environment (GAE) being developed collaboratively by Caltech, NUST and several other institutes. These include a steering service, a job monitoring service and an estimator service that have been designed and written using a common Grid-enabled Web Services framework named Clarens. The paper also presents a performance analysis of the developed services to show that they have indeed resulted in a more interactive and powerful system for user-centric Grid-enabled physics analysis.
Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of online topological ordering algorithms. We prove an expected runtime of O(n^2 polylog(n)) under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (SODA, 1990), Katriel and Bodlaender (TALG, 2006), and Pearce and Kelly (JEA, 2006). This is much less than the best known worst-case bound O(n^{2.75}) for this problem.
In this paper, we study the resource allocation problem for a cooperative device-to-device (D2D)-enabled wireless caching network, where each user randomly caches popular contents to its memory and shares the contents with nearby users through D2D links. To enhance the throughput of spectrum sharing D2D links, which may be severely limited by the interference among D2D links, we enable the cooperation among some of the D2D links to eliminate the interference among them. We formulate a joint link scheduling and power allocation problem to maximize the overall throughput of cooperative D2D links (CDLs) and non-cooperative D2D links (NDLs), which is NP-hard. To solve the problem, we decompose it into two subproblems that maximize the sum rates of the CDLs and the NDLs, respectively. For CDL optimization, we propose a semi-orthogonal-based algorithm for joint user scheduling and power allocation. For NDL optimization, we propose a novel low-complexity algorithm to perform link scheduling and develop a Difference of Convex functions (D.C.) programming method to solve the non-convex power allocation problem. Simulation results show that the cooperative transmission can significantly increase both the number of served users and the overall system throughput.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
