Mobile Crowdsensing leverages the sensing capabilities of multiple mobile devices to execute large-scale sensing tasks by breaking them into smaller tasks for execution on individual mobile devices. taskallocation al...
详细信息
ISBN:
(纸本)9781450369046
Mobile Crowdsensing leverages the sensing capabilities of multiple mobile devices to execute large-scale sensing tasks by breaking them into smaller tasks for execution on individual mobile devices. task allocation algorithms are used to efficiently distribute these smaller sensing tasks to a subset of participants while optimizing system-level goals (such as location accuracy or data quality) for participant selection. The sensing tasks, e.g., collecting GPS tagged data, are often energy-intensive and battery consumption during sensing task execution remains a major concern for participants. So far no in-depth study exists that evaluates the impact of battery consumption on allocationalgorithms. In this work, we conducted an in-depth study on the effects of battery consumption patterns of smartphone users. We studied the impact of battery consumption patterns extracted from a real-world data-set on standard as well as state-of-the-art algorithms to show how different battery usage patterns affect the performance of allocationalgorithms. Our work provides an important insight into factors affecting the performance of allocationalgorithms and advocates incorporating battery usage patterns for the future development of these algorithms.
Pursuit-evasion problems involving multiple pursuers and evaders are studied in this paper. The pursuers and the evaders are all assumed to be identical, and the pursuers are assumed to follow either a constant bearin...
详细信息
Pursuit-evasion problems involving multiple pursuers and evaders are studied in this paper. The pursuers and the evaders are all assumed to be identical, and the pursuers are assumed to follow either a constant bearing or a pure pursuit strategy, giving rise to two distinct cases. The problem is simplified by adopting a dynamic divide and conquer approach, where at every time instant each evader is assigned to a set of pursuers based on the instantaneous positions of all the players. In this regard, the corresponding multi-pursuer single-evader problem is analyzed first. Assuming that the evader knows the positions of all the pursuers and their pursuit strategy, the time-optimal evading strategies are derived for both constant bearing and pure pursuit cases for the pursuers using tools from optimal control theory. In the case of a constant bearing strategy, and assuming that the evader can follow any strategy, a dynamic taskallocation algorithm is proposed for the pursuers. The algorithm is based on the well-known Apollonius circle and allows the pursuers to allocate their resources in an intelligent manner while guaranteeing the capture of the evader in minimum time. For the case of pure pursuit, the algorithm is modified using the counterpart of the Apollonius circle leading to an "Apollonius closed curve." Finally, the proposed algorithms are extended to assign pursuers in the case of a problem with multiple pursuers and multiple evaders. Numerical simulations are included to demonstrate the performance of the proposed algorithms.
Ambient energy harvesting is a solution to mitigate the typical finite energy supply of sensor nodes in wireless sensor networks (WSNs). On the one hand, the uncertainty of energy availability in energy harvesting sys...
详细信息
Ambient energy harvesting is a solution to mitigate the typical finite energy supply of sensor nodes in wireless sensor networks (WSNs). On the one hand, the uncertainty of energy availability in energy harvesting systems makes network protocol design challenging. On the other hand, the fact that energy is continuously replenished opens up avenues for protocol design based on prediction of future energy arrivals. One of the key application scenarios for sensor networks is taskallocation, in which a central entity allocates tasks to a set of geographically distributed sensor nodes to accomplish an overall objective. In this work, we consider a scenario in which the sensor nodes are equipped with devices capable of harvesting ambient energy, e.g., solar panels to harvest the Sun's energy, and focus on energy-aware strategies for adaptive taskallocation. We decompose the static taskallocation problem into two phases: scheduling of the task graph and task mapping to the appropriate sensor nodes. The solution objectives are to minimize the makespan and maximize the fairness in energy-driven task mapping (i.e., energy-balancing), while satisfying the task precedence constraints and energy harvesting causality constraints. We employ a novel energy prediction model which incorporates seasonal changes in solar energy harvesting as well as sudden weather changes. In case of an error in available energy prediction, a dynamic adaptation phase runs to avoid violation of the taskallocation objectives. The performance of our proposed algorithms, in terms of energy-balancing and scheduling length, is evaluated through simulation and compared with other approaches, including a genetic algorithm as a baseline. We achieve more balanced residual energy levels across the network while attaining a near optimum scheduling length. By utilizing the dynamic adaptation phase, for certain runs of simulation, the missing ratio, which is the percentage of times in which the taskallocation f
Enabled by high-speed networking in commercial, scientific, and government settings, the realm of high performance is burgeoning with greater amounts of computational and storage resources. Large-scale systems such as...
详细信息
Enabled by high-speed networking in commercial, scientific, and government settings, the realm of high performance is burgeoning with greater amounts of computational and storage resources. Large-scale systems such as computational grids consume a significant amount of energy due to their massive sizes. The energy and cooling costs of such systems are often comparable to the procurement costs over a year period. In this survey, we will discuss allocation and scheduling algorithms, systems, and software for reducing power and energy dissipation of workflows on the target platforms of single processors, multicore processors, and distributed systems. Furthermore, recent research achievements will be investigated that deal with power and energy efficiency via different power management techniques and application scheduling algorithms. The article provides a comprehensive presentation of the architectural, software, and algorithmic issues for energy-aware scheduling of workflows on single, multicore, and parallel architectures. It also includes a systematic taxonomy of the algorithms developed in the literature based on the overall optimization goals and characteristics of applications.
This paper presents the IQ-ASyMTRe architecture, which is aimed to address both coalition formation and execution for tightly-coupled multirobot tasks in a single framework. Many task allocation algorithms have been p...
详细信息
ISBN:
(纸本)9781424466757
This paper presents the IQ-ASyMTRe architecture, which is aimed to address both coalition formation and execution for tightly-coupled multirobot tasks in a single framework. Many task allocation algorithms have been previously proposed without explicitly enabling the sharing of robot capabilities. Inspired by information invariant theory, ASyMTRe was introduced which enables the sharing of sensory and computational capabilities by allowing information to flow among different robots via communication. However, ASyMTRe does not provide a solution for how a coalition should satisfy sensor constraints introduced by the sharing of capabilities while executing the assigned task. Furthermore, conversions among different information types(1) are hardcoded, which limits the flexibility of ASyMTRe. Moreover, relationships between entities (e. g., robots) and information types are not explicitly captured, which may produce infeasible solutions from the start, as the defined information type may not correspond well to the current environment settings. The new architecture introduces a complete definition of information type to guarantee the feasibility of solutions;it also explicitly models information conversions. Inspired by our previous work, IQ-ASyMTRe uses measures of information quality to guide robot coalitions to satisfy sensor constraints (introduced by capability sharing) while executing tasks, thus providing a complete and general solution. We demonstrate the capability of the approach both in simulation and on physical robots to form and execute coalitions that share sensory information to achieve tightly-coupled tasks.
One of the major issues concerning the efficiency and effectiveness of dynamic load balancing algorithms is their scalability. As the size of the distributed computer system increases, the overheads of a load balancin...
详细信息
One of the major issues concerning the efficiency and effectiveness of dynamic load balancing algorithms is their scalability. As the size of the distributed computer system increases, the overheads of a load balancing algorithm may increase resulting in a poor scalability. In this paper, network partitioning strategies are proposed to reduce the communication overhead of load balancing algorithms in a large distributed system environment. Several host-grouping strategies are suggested to improve the performance of load balancing algorithms. This is achieved by limiting the exchange of load information messages within smaller groups of hosts while restricting the transfer of tasks to long distance remote hosts which involve high communication costs. The group memberships are changed dynamically to adapt the varying load conditions across the entire network. Effectiveness of the proposed strategies is evaluated by simulations.
In this paper, dynamic load balancing algorithms are studied using a queueing theoretic model. For each algorithm, a different load index has been used to estimate the host loads. These estimates are utilized in simpl...
详细信息
In this paper, dynamic load balancing algorithms are studied using a queueing theoretic model. For each algorithm, a different load index has been used to estimate the host loads. These estimates are utilized in simple task placement heuristics to determine the probabilities for transferring tasks between every two hosts in the system. The probabilities determined in this way are used to perform dynamic load balancing in a distributed computer system. Later, these probabilities are adjusted to include the effects of inter-host communication costs. Effectiveness of these algorithms is evaluated by simulations.
In a distributed processing system with the application software partitioned into a set of program modules, allocation of those modules to the processors is an important problem. This paper presents a method for optim...
详细信息
In a distributed processing system with the application software partitioned into a set of program modules, allocation of those modules to the processors is an important problem. This paper presents a method for optimal module allocation that satisfies certain performance constraints. An objective function that includes the intermodule communication (IMC) and accumulative execution time (AET) of each module is proposed. It minimizes the bottleneck-processor utilization—a good principle for taskallocation. Next, the effects of precedence relationship (PR) among program modules on response time are studied. Both simulation and analytical results reveal that the program-size ratio between two consecutive modules plays an important role in task response time. Finally, an algorithm based on PR, AET, and IMC and on the proposed objective function is presented. This algorithm generates better module assignments than those that do not consider the PR effects.
暂无评论