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

An optimal cluster-based routing algorithm for lifetime maximization of Internet of Things

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2021年 156卷 7-24页

作者： Yarinezhad, Ramin Sabaei, Masoud Amirkabir Univ Technol Dept Comp Engn & Informat Technol Tehran Iran

Edge computing for Internet of Things (IoT) is a promising framework that can help small devices such as low-powered sensor nodes to accomplish complex computational tasks. The limited power supply of sensor nodes is one of their major limitations. A successful approach to improve the network lifetime and the overall scalability of the IoT supported wireless sensor networks (WSNs) is clustering. However, in a clustered IoT supported WSNs, some of the Cluster Heads (CHs) bear more traffic load than the others and therefore die sooner leading to decrease the network lifetime. To overcome this problem and maximize the network lifetime, the load of the CHs must be balanced. This research work suggests a new clustering method to balance the traffic load imposed on the cluster heads in IoT supported WSNs. The proposed clustering method uses a 1.2-approximation algorithm. In addition, we introduce an energy-aware routing algorithm for transmitting data packets from the CHs to their destination. The proposed routing algorithm distributes the communication load of the data packets among more nodes near the destination by a proper segmentation of the area. The simulation results show that the proposed clustering and routing algorithms in addition to being practical for large-scale IoT supported WSNs, cause the network to have a better performance compared to other similar algorithms. (c) 2021 Elsevier Inc. All rights reserved.

关键词： Internet of Things Routing protocol approximation algorithm Energy balance

来源：评论

学校读者我要写书评

暂无评论

Continuous Profit Maximization: A Study of Unconstrained Dr-Submodular Maximization

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2021年第3期8卷 768-779页

作者： Guo, Jianxiong Wu, Weili Univ Texas Dallas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Richardson TX 75080 USA

Profit maximization (PM) is to select a subset of users as seeds for viral marketing in online social networks, which balances between the cost and the profit from influence spread. We extend PM to formulate a continuous PM under the general marketing strategies (CPM-MS) problem, whose domain is on integer lattices. The objective function of our CPM-MS is dr-submodular, but nonmonotone. It is a typical case of unconstrained dr-submodular maximization (UDSM) problem, and taking it as a starting point, we study UDSM systematically in this article, which is very different from those studied by existing researchers. First, we introduce the lattice-based double greedy algorithm, which can obtain a constant approximation guarantee. However, there is a strict and unrealistic condition that requiring the objective value is nonnegative on the whole domain or else no theoretical bounds. Thus, we propose a lattice-based iterative pruning technique. It can shrink the search space effectively, thereby greatly increasing the possibility of satisfying the nonnegative objective function on this smaller domain without losing approximation ratio. Then, to overcome the difficulty to estimate the objective value of CPM-MS, we adopt reverse sampling strategies and combine it with lattice-based double greedy, including pruning, without losing its performance but reducing its running time. The entire process can be considered as a general framework to solve the UDSM problem, especially for applying to social networks. Finally, we conduct experiments on several real data sets to evaluate the effectiveness and efficiency of our proposed algorithms.

关键词： approximation algorithms Social networking (online) Linear programming Lattices Greedy algorithms Time complexity Search problems approximation algorithm continuous profit maximization (PM) dr-submodular maximization integer lattice sampling strategies social networks

来源：评论

学校读者我要写书评

暂无评论

Minimizing energy on homogeneous processors with shared memory

引用

THEORETICAL COMPUTER SCIENCE 2021年 866卷 160-170页

作者： Chau, Vincent Fong, Chi Kit Ken Liu, Shengxin Wang, Elaine Yinling Zhang, Yong Southeast Univ Sch Comp Sci & Engn Nanjing Peoples R China Chu Hai Coll Higher Educ Hong Kong Peoples R China Harbin Inst Technol Sch Comp Sci & Technol Shenzhen Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Peoples R China Dalian Univ Technol Sch Math Sci Dalian Peoples R China

Energy efficiency is a crucial desideratum in the design of computer systems, from small-sized mobile devices with limited battery to large scale data centers. In such computing systems, processors and memory are considered as two major power consumers among all the system components. One recent trend to reduce power consumption is using shared memory in multi-core systems, such architecture has become ubiquitous nowadays. However, implementing the energy-efficient methods to the multi-core processor and the shared memory separately is not trivial. In this work, we consider the energy-efficient task scheduling problem, which coordinates the power consumption of both the multi-core processor and the shared memory, especially focus on the general situation in which the number of tasks is more than the number of cores. We devise an approximation algorithm with guaranteed performance in the multiple cores system. We tackle the problem by first presenting an optimal algorithm when the assignment of tasks to cores is given. Then we propose an approximation assignment for the general task scheduling. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Energy Scheduling Shared memory approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Constructing d-Robust Connected Dominating Sets in Wireless Sensor Networks With Unstable Transmission Ranges

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第1期69卷 398-415页

作者： Liang, Xinyu Liang, Jiarong Zhang, Weiguang Guangxi Univ Sch Elect Engn Nanning 530004 Peoples R China Guangxi Univ Sch Comp Elect & Informat Nanning 530004 Peoples R China Guangxi Univ Guangxi Key Lab Multimedia Commun & Network Techn Nanning 530004 Peoples R China

virtual backbone (VB) in a wireless sensor network (WSN). The overhead in a WSN is usually determined by the size of the corresponding VB. However, the construction of minimum CDSs (MCDSs) has been proven to be an NP-hard problem. Thus, most researchers use approximation algorithms to find smaller CDSs. In certain applications, the transmission radii of some nodes in the network are unstable due to certain environmental factors such as obstacles, signal interference and node movement. Thus, the robustness of VBs in WSNs should be considered. In this paper, we propose the concept of a d-robust CDS and corresponding algorithms to construct d-robust CDSs in WSNs with unstable transmission ranges. We propose algorithms for a d-robust CDS that is bounded by [40.68/(1 - d)(2) + 10.17] . opt + [31.32/(1 - d)(2) + 7.83], where opt is the size of the MCDS and d is an element of [0, 1). Through simulations, we show the relationship between the size of the d-robust CDS and the value of d and compare our algorithms with existing algorithms in terms of the robustness degree of the CDS. The results show that the CDSs produced by our algorithms exhibit better robustness.

关键词： Wireless sensor network robustness approximation algorithm unstable transmission ranges connected dominating set

来源：评论

学校读者我要写书评

暂无评论

Stream Computation of 3D Approximate Convex Hulls with an FPGA 2022

Stream Computation of 3D Approximate Convex Hulls with an FP...

引用

12th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies (HEART)

作者： Mori, Tatsuma Motoyoshi, Keigo Ikehara, Haruto Manabe, Taito Shibata, Yuichiro Ueno, Tomohiro Sano, Kentaro Nagasaki Univ Nagasaki Japan Riken R CCS Kobe Hyogo Japan

ISBN: (纸本)9781450396608

The convex hull is the minimum convex set which encloses a given point set. A problem to find convex hulls is not only one of the most fundamental algorithms in computer geometry, but also has a wide variety of practical applications such as robotics and geographic informatics. This paper proposes and evaluates an efficient pipelined FPGA implementation of approximate convex hull computing for 3D points. The proposed architecture does not require the input points to be sorted in advance, and can execute the algorithm in a pipelined manner without storing all the points in memory. We implemented the architecture on an Intel Stratix 10 FPGA to reveal the tradeoff relationship among its performance, resource usage, and approximation accuracy. As a result, we demonstrated 9 to 115 times faster performance compared to the convex hull software library Qhull, which was run on the Intel Core i9-9900K. The accuracy assessment revealed that the approximation error normalized to the diameters of point sets was only 0.037% to 3.173%, which was acceptably small for practical use cases.

关键词： FPGA convex hull hardware algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Parallel algorithm for Minimum Cost Submodular Cover Problem with Lower Adaptive Complexity

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2024年第6期41卷

作者： Nguyen, Hue T. Ha, Dung T. K. Pham, Canh V. Grad Univ Sci & Technol Vietnam Acad Sci & Technol VAST Hanoi Vietnam Hanoi Architecture Univ Fac Informat Technol Hanoi Vietnam Vietnam Natl Univ Univ Engn & Technol Fac Informat Technol 144 Xuan Thuy St Hanoi 10000 Vietnam Phenikaa Univ Yen Nghia Ward Fac Comp Sci ORLab Hanoi 12116 Vietnam

In this paper, we study the Minimum Cost Submodular Cover (MCSC) problem over the ground set of size n, which aims at finding a subset with the minimal cost required so that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of operations research and artificial intelligence. However, the existing algorithms for this problem may not be effectively parallelized because of their costly adaptive complexity. This paper proposes an efficient parallel algorithm that returns a (1 - lambda, (1 + epsilon)(1 +log 1/lambda))-bicriteria approximation solution within O(log n) adaptive complexity, where lambda, epsilon are fixed parameters. Our algorithm requires O(n(2) log(2) n) query complexity, however, it can reduce to O(n log(3) n) instead while retaining a low adaptive complexity of O(log(2)n). Therefore, our algorithm not only achieves the same approximation guarantees as the state of the art but also significantly improves the best-known low adaptive complexity algorithm for the above problem.

关键词： Submodular cover approximation algorithm parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast Streaming algorithms for k-Submodular Maximization under a Knapsack Constraint 9

Fast Streaming Algorithms for k-Submodular Maximization unde...

引用

9th IEEE International Conference on Data Science and Advanced Analytics (DSAA)

作者： Pham, Canh V. Ha, Dung K. T. Hoang, Huan X. Tran, Tan D. Phenikaa Univ ORLab Fac Comp Sci Hanoi Vietnam VNU Univ Engn & Technol Fac Informat Technol Hanoi Vietnam Halong Univ Fac Informat Technol Quang Ninh Vietnam Peoples Secur Acad Hanoi Vietnam

ISBN: (纸本)9781665473309

This paper proposes two fast streaming algorithms for the problem of k-submodular maximization over the ground set of n elements under the knapsack constraint which is important and popular in combinatorial optimization and machine learning. Our algorithms are the first ones that provide constantapproximation ratios within O(nk) query complexity. The first algorithm is a single-pass streaming algorithm that returns a 1/10-approximation solution, the second one is a multi-pass streaming algorithm and improves the approximation ratio to nearly 1/4. Although these ratios are simply near to the stateof-the-art algorithms yet the number of queries can diminish by a large factor. We further investigate the performance of our algorithms by directing several experiments on instances of the issue: Influence Maximization and Sensor Placement. The outcomes confirm that our algorithms not only methodology in the quality arrangement of the cutting edge techniques including streaming and non-streaming algorithms yet in addition significantly reduce the number of queries.

关键词： approximation algorithm k-submodular maximization knapsack constraint streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

The Multi-vehicle Ride-Sharing Problem 22

The Multi-vehicle Ride-Sharing Problem

引用

15th ACM International Conference on Web Search and Data Mining (WSDM)

作者： Luo, Kelin Agarwal, Chaitanya Das, Syamantak Guo, Xiangyu Eindhoven Univ Technol Eindhoven Netherlands Univ Bonn Bonn Germany NYU New York NY USA Indraprastha Inst Informat Technol Delhi IIIT Del Delhi India Univ Buffalo Buffalo NY USA

ISBN: (纸本)9781450391320

Ride-sharing is one of the most popular models of economical and eco-friendly transportation in modern smart cities, especially when riding hybrid and electric vehicles. Usually multiple passengers with similar itineraries are grouped together, which significantly reduces travel cost (or time), road congestion, and traffic emissions. In this paper, we study the ride-sharing problem where each vehicle is shared by exactly lambda riders for any fixed lambda > 0, and the goal is to minimize the total travel distance. The min-cost ride-sharing problem is intractable even in the case of exactly two riders sharing a vehicle [2], and hence we can only hope for an approximate solution. We propose a novel two-phase algorithm: a hierarchical grouping phase that partitions requests into disjoint groups of fixed size, followed by an assignment of request groups to individual vehicles and planning a feasible route for each vehicle. This is the first non-trivial approximation algorithm for the ride-sharing problem with vehicle capacity larger than two. We verify the efficacy of our algorithm on both synthetic and realworld datasets. Our experiments show that, the ride-sharing scheme produced by our algorithm not only has small total travel distance compared to state-of-the-art baselines, but also enjoys a small makespan and total latency, which crucially relate to each single rider's traveling time. This suggests that our algorithm also enhances rider experience while being energy-efficient.

关键词： ride-sharing approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Spatio-Temporal Mobile Cooperative Charging for Low-Power Wireless Rechargeable Devices 19

Spatio-Temporal Mobile Cooperative Charging for Low-Power Wi...

引用

19th IEEE International Conference on Mobile Ad Hoc and Smart Systems (MASS)

作者： Xu, Lijie Sha, Haodong Da, Mingxiang Xu, Jia Dai, Haipeng Nanjing Univ Posts & Telecommun Jiangsu Key Lab Big Data Secur & Intelligent Proc Nanjing 210023 Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China

ISBN: (数字)9781665471800

ISBN: (纸本)9781665471800

By deploying or scheduling wireless chargers, Wireless Rechargeable Sensor Networks (WRSNs) can provide continuous energy supply for the rechargeable devices. Recently, a novel cooperative charging service model was proposed for WRSNs, which provides a business framework of on-demand wireless charging service. Based on such model, the existing work mainly considered the spatially cooperative charging scheduling problem but ignored the cooperation in temporal dimension. In practice, we can find that the QoS requirement of applications often requires an upper bound constraint on the out-of-service time for each device, which implies the charging service cost can benefit from the temporal cooperation of the devices. In this paper, we focus on the device-initiated mobile cooperative charging problem in both spatial and temporal dimensions. Our objective is to find a spatio-temporal cooperative charging scheduling strategy to minimize the total charging service cost, subject to the constraints that the out-of-service time of each device does not exceed a given upper bound. We first prove the NP-hardness of our target problem, and then devise a greedy-based Charging Service Cost Optimization algorithm, which can achieve an approximation ratio of ln n+1 in most of real situations. The extensive simulation results reveal that our solution always outperforms the other solutions in terms of charging service cost.

关键词： wireless rechargeable sensor networks cooperative charging service model charging service cost spatio-temporal approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A balance-first sequence-last algorithm to design RMS: a matheuristic with performance guaranty to balance reconfigurable manufacturing systems

引用

JOURNAL OF HEURISTICS 2021年第1-2期27卷 107-132页

作者： Lahrichi, Youssef Deroussi, Laurent Grangeon, Nathalie Norre, Sylvie Univ Clermont Auvergne CNRS LIMOS F-63000 Clermont Ferrand France Univ Clermont Auvergne CNRS IUT Allier LIMOS F-63000 Clermont Ferrand France

The Reconfigurable Transfer Line Balancing Problem (RTLB) is considered in this paper. This problem is quite recent and motivated by the growing need of reconfigurability in the new industry 4.0 context. The problem consists into allocating a set of operations necessary to machine a single part to different workstations placed into a serial line. Each workstation can contain multiple machines operating in parallel and the tasks allocated to a workstation should be sequenced since sequence-dependent setup times between operations are needed to perform tool changes. Besides, precedence constraints, inclusion, exclusion and accessibility constraints between operations are considered. In this article we propose an efficient matheuristic of type Balance First, Sequence Last (BFSL). This method is a two-step heuristic with a constructive phase and an improvement phase. It contains several components from exact methods (linear programming, constraint generation and dynamic programming) and metaheuristics (simulated annealing). In addition, we show that the constructive algorithm approximates the optimal solution when the setup times are bounded by the processing times and give an approximation ratio. The obtained results show the effectiveness of the proposed approach. The matheuristic clearly outperforms a genetic algorithm from literature on quite large benchmark instances.

关键词： RTLB Line balancing Constraint generation Simulated annealing Matheuristic approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：