检索结果-内蒙古大学图书馆

Emerging Trends in Communication, Control and Computing (ICONC3), International Conference on

作者： Ajay Kumar V. K. Jain P. P. Bhattacharya Computer Science and Engineering School of Engineering and Technology Mody University of Science and Technology Lakshmangarh India

ISBN: (数字)9781728114200

ISBN: (纸本)9781728114217

Internet of Things have gained the interest of researchers and other academic communities due to their applications in various fields. Determining the location of a sensor node within the specified area consisting of number of sensors and smart devices is very crucial, which requires association between the devices and the sensor nodes[1]. Localization is the basic requirement for other services of any smart network like communication, clustering, distribution, routing etc. Multidimensional scaling is one of the approach used effectively for the sensor node localization. In this approach the process to obtain the minimum distance path between the pair of sensors are used which helps in estimating the relative positions of the nodes. This paper includes the explanation and comparison of different types shortest path algorithms. Then, we discuss about the use of multidimensional scaling process to obtain the absolute positions of nodes with reduced error cumulation in a smart network. It is mandatory to have a efficient, economic and scalable sensor node position estimation process for a wireless sensor network and hence for internet of Things. The results obtained experimentally proves the efficiency and effectiveness of the methods discussed for use in Internet of Things with various routing, topology and area.

关键词： Global Positioning System Internet of Things Multidimensional Scaling shortest path Wireless Sensor Networks Internet of things Multi dimensional scaling Wireless sensor networks shortest path Global Positioning Systems Sensors shortest path algorithms Thing Internets minimum distance DESIGNATED AREA

来源：评论

学校读者我要写书评

暂无评论

Comparative Analysis of Parallelised shortest path algorithms using Open MP 3

Comparative Analysis of Parallelised Shortest Path Algorithm...

引用

3rd IEEE International Conference on Sensing, Signal Processing and Security (ICSSS)

作者： Uditi Arun, M. VIT Univ Elect & Commun Engn Vellore Tamil Nadu India VIT Univ Embedded Syst Vellore Tamil Nadu India

ISBN: (纸本)9781509049295

this paper presents parallel implementations and includes performance analysis of three prominent graph algorithms (i.e., Bellman Ford, Floyd-Warshall and Dijkstra) used for finding the all-pairs of shortest paths. The algorithm implementations were parallelized using Open MP (Open Multi-Processing). Their performances were measured on 4 different configurations i.e. dual core i3, quad core i5, quad core i7 and 8 core processors. This paper also presents a comparative study of serial and parallel implementations of these algorithms keeping execution time and number of graph nodes as the parameter. Finally, the results show that, execution time can be reduced using parallel implementation for larger number of graph nodes. Also, the conclusions are drawn for the best algorithm to be used which works for all the graph nodes with less execution time.

关键词： shortest path algorithms Open MP Parallel computing execution time

来源：评论

学校读者我要写书评

暂无评论

shortest path algorithms for functional environments

引用

DISCRETE OPTIMIZATION 2015年 18卷 217-251页

作者： Boguchwal, Louis

This research generalises classic shortest path algorithms to network environments in which arc-costs are governed by functions, rather than fixed weights. We show that the asymptotic efficiency of our algorithms is identical to their classic counterparts. Previous results, since Knuth in 1976, require several restrictive assumptions on the functions permitted in the network. In contrast, our algorithms require only monotonicity. We present examples illustrating that this is the largest class of functions to which classic algorithms can be generalised. Applications of this work include critical path extensions to solve sequential decision-problems, and generalised network flow with nonlinear gain functions. (C) 2015 Elsevier B.V. All rights reserved.

关键词： shortest path algorithms Combinatorial optimisation Networks Sequential decision-problems Generalised flow

来源：评论

学校读者我要写书评

暂无评论

Critical Review of Time-Dependent shortest path algorithms: A Multimodal Trip Planner Perspective

引用

TRANSPORT REVIEWS 2014年第4期34卷 522-539页

作者： Casey, Bradley Bhaskar, Ashish Guo, Hao Chung, Edward Queensland Univ Technol Fac Built Environm & Engn Smart Transport Res Ctr Brisbane Australia Queensland Univ Technol Smart Transport Res Ctr Fac Built Environm & Engn Brisbane Qld 4001 Australia

A multimodal trip planner that produces optimal journeys involving both public transport and private vehicle legs has to solve a number of shortest path problems, both on the road network and the public transport network. The algorithms that are used to solve these shortest path problems have been researched since the late 1950s. However, in order to provide accurate journey plans that can be trusted by the user, the variability of travel times caused by traffic congestion must be taken into consideration. This requires the use of more sophisticated time-dependent shortest path algorithms, which have only been researched in depth over the last two decades, from the mid-1990s. This paper will review and compare nine algorithms that have been proposed in the literature, discussing the advantages and disadvantages of each algorithm on the basis of five important criteria that must be considered when choosing one or more of them to implement in a multimodal trip planner.

关键词： multimodal trip planning time-dependent dynamic shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable Single Source shortest path algorithms for Massively Parallel Systems

Scalable Single Source Shortest Path Algorithms for Massivel...

引用

IEEE 28th International Parallel & Distributed Processing Symposium (IPDPS)

作者： Chakaravarthy, Venkatesan T. Checconi, Fabio Petrini, Fabrizio Sabharwal, Yogish IBM Res India New Delhi India IBM Corp TJ Watson Res Ctr Armonk NY 10504 USA

ISBN: (纸本)9780769552071

In the single-source shortest path (SSSP) problem, we have to find the shortest paths from a source vertex v to all other vertices in a graph. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Delta-stepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. The extensive performance analysis shows that our algorithms work well on scale-free and real-world graphs. In the largest tested configuration, an R-MAT graph with 2(38) vertices and 2(42) edges on 32, 768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.

关键词： BFS Blue Gene/Q Graph algorithms Parallelization SSSP Supercomputer Graph algorithms supercomputer parallelization vertex head shortest path algorithms parallel system BUNDESAMT FUER STRAHLENSCHUTZ Parallel algorithms scale-free shortest path

来源：评论

学校读者我要写书评

暂无评论

Scalable Single Source shortest path algorithms for Massively Parallel Systems

Scalable Single Source Shortest Path Algorithms for Massivel...

引用

IEEE International Parallel and Distributed Processing Symposium

作者： Venkatesan T. Chakaravarthy Fabio Checconi Fabrizio Petrini Yogish Sabharwal IBM Research - India IBM T J Watson Research Center

ISBN: (纸本)9781479938018

In the single-source shortest path (SSSP) problem, we have to find the shortest paths from a source vertex v to all other vertices in a graph. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Delta-stepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. The extensive performance analysis shows that our algorithms work well on scale-free and real-world graphs. In the largest tested configuration, an R-MAT graph with 2~(38) vertices and 2~(42) edges on 32,768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.

关键词： vertex head shortest path algorithms parallel system Parallel algorithms scale-free shortest path Scalability telecommunication traffic

来源：评论

学校读者我要写书评

暂无评论

Multi-scale theta* algorithm for the path planning of unmanned surface vehicle

引用

PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART M-JOURNAL OF ENGINEERING FOR THE MARITIME ENVIRONMENT 2022年第2期236卷 427-435页

作者： Han, Xu Zhang, Xianku Dalian Maritime Univ Lab Marine Simulat & Control Sci HallRoom 310 Dalian 116026 Liaoning Peoples R China

Theta* algorithm is a searching-based path planning algorithm that gives an optimal path with more flexibility on route angle than A* method. The dynamics of USV is characterized by large inertia, so that larger turning angle is preferred. In view of the shortcomings of traditional Theta* algorithm, such as being hard to balance overall situation and details in long-distance planning, and lacking of waypoint replacement scheme when a waypoint is unreachable, it is inappropriate to make long-distance planning through Theta* algorithm directly. In order to ensure safe navigation for unmanned surface vehicle (USV), this paper proposes a multi-scale Theta* algorithm to solve these defects. Simulation result manifests the proposed scheme can provide a path clear of obstacles with several fold reduction in time consumption. The proposed planning method simplifies path planning process and contributes to the development of marine transportation.

关键词： Multi-scale planning shortest path algorithms Theta* algorithm USV

来源：评论

学校读者我要写书评

暂无评论

Agent-Based Modeling of Uncrewed Aircraft System Flight Planning for Airspace Fairness

Agent-Based Modeling of Uncrewed Aircraft System Flight Plan...

引用

AIAA Aviation Forum

作者： Yang, Rebekah Walker, Simone Prebble, Matthew Lesko, Mark Landry, Glen Hales, Shaelynn CNA Corp Ctr Data Management & Analyt Arlington VA 22201 USA

ISBN: (数字)9781624107047

ISBN: (纸本)9781624107047

The number of uncrewed aircraft systems (UAS) and corresponding UAS operations is expected to increase dramatically soon. Regulatory agencies are currently designing and piloting UAS traffic management concepts that rely on federated protocols and a cooperative, community-based approach. As demand increases, the need to ensure fair usage of airspace among operators will be an important challenge. Currently, there are no widely agreed upon definitions or guidelines for UAS airspace fairness. The objective of this work was to evaluate the fairness implications of using a first-filed-first-served protocol for flight planning. We developed UAS Cooperative Airspace Traffic Simulation (UCATS), an agent-based modeling simulation tool, to evaluate different UAS package delivery scenarios using a first-filed-first-served approach to UAS flight planning. We defined key metrics to measure fairness, including average delay, maximum delay, and percentages of flights as planned, replanned, and canceled. Our results showed that a first-filed-first-served approach may cause flights having a departure time later in the day and flights that are filed with less advanced time have a higher probability of experiencing more negative flight outcomes. We also evaluated the sensitivity of fairness metrics to different traffic levels, different flight densities, and the addition of food delivery operations.

关键词： Aircraft Systems Flight Planning Airspace Federal Aviation Administration Air Taxi Conflict Detection and Resolution Department of Transportation shortest path algorithms Air Traffic Management Flight Trajectory

来源：评论

学校读者我要写书评

暂无评论

Efficient Distance Sensitivity oracles for Real-World Graph Data

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2021年第1期33卷 85-99页

作者： Lee, Jong-Ryul Chung, Chin-Wan Korea Adv Inst Sci & Technol Daejeon 34141 South Korea Chongqing Univ Technol CQUT Chongqing Liangjiang KAIST Int Program Chongqing 400054 Peoples R China Korea Adv Inst Sci & Technol KAIST Sch Comp Daejeon 34141 South Korea

A distance sensitivity oracle is a data structure answering queries that ask the shortest distance from a node to another in a network expecting node/edge failures. It has been mainly studied in theory literature, but all the existing oracles for a directed graph suffer from prohibitive preprocessing time and space. Motivated by this, we develop two practical distance sensitivity oracles for directed graphs as variants of Transit Node Routing. The first oracle consists of a novel fault-tolerant index structure, which is used to construct a solution path and to detect and localize the impact of network failures, and an efficient query algorithm for it. The second oracle is made by applying the A* heuristics to the first oracle, which exploits lower bound distances to effectively reduce search space. In addition, we propose additional speed-up techniques to make our oracles faster with a slight loss of accuracy. We conduct extensive experiments with real-life datasets, which demonstrate that our oracles greatly outperform all of competitors in most cases. To the best of our knowledge, our oracles are the first distance sensitivity oracles that handle real-world graph data with million-level nodes.

关键词： Graph algorithms path and circuit problems graphs and networks distance sensitivity oracle distance query shortest distance shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

A Fresh Look at Zones and Octagons

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2021年第3期43卷 1–51页

作者： Gange, Graeme Ma, Zequn Navas, Jorge A. Schachte, Peter Sondergaard, Harald Stuckey, Peter J. Monash Univ Fac IT Clayton Vic 3800 Australia Univ Melbourne Sch Comp & Informat Syst Parkville Vic 3010 Australia SRI Int Comp Sci Lab Menlo Pk CA 94025 USA

Zones and Octagons are popular abstract domains for static program analysis. They enable the automated discovery of simple numerical relations that hold between pairs of program variables. Both domains are well understood mathematically but the detailed implementation of static analyses based on these domains poses many interesting algorithmic challenges. In this article, we study the two abstract domains, their implementation and use. Utilizing improved data structures and algorithms for the manipulation of graphs that represent difference-bound constraints, we present fast implementations of both abstract domains, built around a common infrastructure. We compare the performance of these implementations against alternative approaches offering the same precision. We quantify the differences in performance by measuring their speed and precision on standard benchmarks. We also assess, in the context of software verification, the extent to which the improved precision translates to better verification outcomes. Experiments demonstrate that our new implementations improve the state of the art for both Zones and Octagons significantly.

关键词： Abstract interpretation shortest path algorithms difference-bounds matrix numerical abstract domains program analysis static analysis variable packing weakly relational domains

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：