Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Truthful Auction for Graph Job Allocation in Vehicular Cloud-assisted Networks
92
0
0.0
(
0
)
Added by
Minghui LiWang
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Vehicular cloud computing has emerged as a promising solution to fulfill users demands on processing computation-intensive applications in modern driving environments. Such applications are commonly represented by graphs consisting of components and edges. However, encouraging vehicles to share resources poses significant challenges owing to users selfishness. In this paper, an auction-based graph job allocation problem is studied in vehicular cloud-assisted networks considering resource reutilization. Our goal is to map each buyer (component) to a feasible seller (virtual machine) while maximizing the buyers utility-of-service, which concerns the execution time and commission cost. First, we formulate the auction-based graph job allocation as an integer programming (IP) problem. Then, a Vickrey-Clarke-Groves based payment rule is proposed which satisfies the desired economical properties, truthfulness and individual rationality. We face two challenges: 1) the above-mentioned IP problem is NP-hard; 2) one constraint associated with the IP problem poses addressing the subgraph isomorphism problem. Thus, obtaining the optimal solution is practically infeasible in large-scale networks. Motivated by which, we develop a structure-preserved matching algorithm by maximizing the utility-of-service-gain, and the corresponding payment rule which offers economical properties and low computation complexity. Extensive simulations demonstrate that the proposed algorithm outperforms the benchmark methods considering various problem sizes.
rate research
Read More
The software defined air-ground integrated vehicular (SD-AGV) networks have emerged as a promising paradigm, which realize the flexible on-ground resource sharing to support innovative applications for UAVs with heavy computational overhead. In this paper, we investigate a vehicular cloud-assisted graph job allocation problem in SD-AGV networks, where the computation-intensive jobs carried by UAVs, and the vehicular cloud are modeled as graphs. To map each component of the graph jobs to a feasible vehicle, while achieving the trade-off among minimizing UAVs job completion time, energy consumption, and the data exchange cost among vehicles, we formulate the problem as a mixed-integer non-linear programming problem, which is Np-hard. Moreover, the constraint associated with preserving job structures poses addressing the subgraph isomorphism problem, that further complicates the algorithm design. Motivated by which, we propose an efficient decoupled approach by separating the template (feasible mappings between components and vehicles) searching from the transmission power allocation. For the former, we present an efficient algorithm of searching for all the subgraph isomorphisms with low computation complexity. For the latter, we introduce a power allocation algorithm by applying convex optimization techniques. Extensive simulations demonstrate that the proposed approach outperforms the benchmark methods considering various problem sizes.
Software-defined internet of vehicles (SDIoV) has emerged as a promising paradigm to realize flexible and comprehensive resource management, for next generation automobile transportation systems. In this paper, a vehicular cloud computing-based SDIoV framework is studied wherein the joint allocation of transmission power and graph job is formulated as a nonlinear integer programming problem. To effectively address the problem, a structure-preservation-based two-stage allocation scheme is proposed that decouples template searching from power allocation. Specifically, a hierarchical tree-based random subgraph isomorphism mechanism is applied in the first stage by identifying potential mappings (templates) between the components of graph jobs and service providers. A structure-preserving simulated annealing-based power allocation algorithm is adopted in the second stage to achieve the trade-off between the job completion time and energy consumption. Extensive simulations are conducted to verify the performance of the proposed algorithms.
In the era of big-data, the jobs submitted to the clouds exhibit complicated structures represented by graphs, where the nodes denote the sub-tasks each of which can be accommodated at a slot in a server, while the edges indicate the communication constraints among the sub-tasks. We develop a framework for efficient allocation of graph jobs in geo-distributed cloud networks (GDCNs), explicitly considering the power consumption of the datacenters (DCs). We address the following two challenges arising in graph job allocation: i) the allocation problem belongs to NP-hard nonlinear integer programming; ii) the allocation requires solving the NP-complete sub-graph isomorphism problem, which is particularly cumbersome in large-scale GDCNs. We develop a suite of efficient solutions for GDCNs of various scales. For small-scale GDCNs, we propose an analytical approach based on convex programming. For medium-scale GDCNs, we develop a distributed allocation algorithm exploiting the processing power of DCs in parallel. Afterward, we provide a novel low-complexity (decentralized) sub-graph extraction method, based on which we introduce cloud crawlers aiming to extract allocations of good potentials for large-scale GDCNs. Given these suggested strategies, we further investigate strategy selection under both fixed and adaptive DC pricing schemes, and propose an online learning algorithm for each.
Artificial Intelligence (AI) and Internet of Things (IoT) applications are rapidly growing in todays world where they are continuously connected to the internet and process, store and exchange information among the devices and the environment. The cloud and edge platform is very crucial to these applications due to their inherent compute-intensive and resource-constrained nature. One of the foremost challenges in cloud and edge resource allocation is the efficient management of computation and communication resources to meet the performance and latency guarantees of the applications. The heterogeneity of cloud resources (processors, memory, storage, bandwidth), variable cost structure and unpredictable workload patterns make the design of resource allocation techniques complex. Numerous research studies have been carried out to address this intricate problem. In this paper, the current state-of-the-art resource allocation techniques for the cloud continuum, in particular those that consider time-sensitive applications, are reviewed. Furthermore, we present the key challenges in the resource allocation problem for the cloud continuum, a taxonomy to classify the existing literature and the potential research gaps.
Autonomous driving (auto-driving) has been becoming a killer technology for next generation vehicles, whereas some fatal accidents grow concerns about its safety. A fundamental function for safer auto-driving is to recognize the vehicles locations, termed vehicular positioning. The state-of-the-art vehicular positioning is to rely on anchors that are stationary objects whose locations are known, i.e. satellites for GPS and base stations for cellular positioning. It is important for reliable positioning to install anchors densely, helping find enough anchors nearby. For the deployment to be cost-effective, there are some trials to use backscatter tags as alternative anchors by deploying them on a road surface, but its gain is limited by several reasons such as short contact time and difficulties in maintenance. Instead, we propose a new backscatter-tag assisted vehicular positioning system where tags are deployed along a roadside, which enables the extension of contact duration and facilitates the maintenance. On the other hand, there is a location mismatch between the vehicle and the tag, calling for developing a new backscatter transmission to estimate their relative position. To this end, we design a novel waveform called joint frequency-and-phase modulation (JFPM) for backscatter-tag assisted vehicular positioning where a transmit frequency is modulated for the distance estimation assuming that the relevant signal is clearly differentiable from the others while the phase modulation helps the differentiation. The JFPM waveform leads to exploiting the maximum Degree-of-Freedoms (DoFs) of backscatter channel in which multiple-access and broadcasting channels coexist, leading to more accurate positioning verified by extensive simulations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
