Skip to main content
placeholder image

A belief propagation-based method for task allocation in open and dynamic cloud environments

Journal Article


Abstract


  • © 2016We propose a decentralized belief propagation-based method, PD-LBP, for multi-agent task allocation in open and dynamic grid and cloud environments where both the sets of agents and tasks constantly change. PD-LBP aims at accelerating the online response to, improving the resilience from the unpredicted changing in the environments, and reducing the message passing for task allocation. To do this, PD-LBP devises two phases, pruning and decomposition. The pruning phase focuses on reducing the search space through pruning the resource providers, and the decomposition addresses decomposing the network into multiple independent parts where belief propagation can be operated in parallel. Comparison between PD-LBP and two other state-of-the-art methods, Loopy Belief Propagation-based method and Reduced Binary Loopy Belief Propagation based method, is performed. The evaluation results demonstrate the desirable efficiency of PD-LBP from both the shorter problem solving time and smaller communication requirement of task allocation in dynamic environments.

UOW Authors


  •   Kong, Yan (external author)
  •   Zhang, Minjie
  •   Ye, Dayong (external author)

Publication Date


  • 2017

Citation


  • Kong, Y., Zhang, M. & Ye, D. (2017). A belief propagation-based method for task allocation in open and dynamic cloud environments. Knowledge-Based Systems, 115 (January), 123-132.

Scopus Eid


  • 2-s2.0-84995871772

Number Of Pages


  • 9

Start Page


  • 123

End Page


  • 132

Volume


  • 115

Issue


  • January

Abstract


  • © 2016We propose a decentralized belief propagation-based method, PD-LBP, for multi-agent task allocation in open and dynamic grid and cloud environments where both the sets of agents and tasks constantly change. PD-LBP aims at accelerating the online response to, improving the resilience from the unpredicted changing in the environments, and reducing the message passing for task allocation. To do this, PD-LBP devises two phases, pruning and decomposition. The pruning phase focuses on reducing the search space through pruning the resource providers, and the decomposition addresses decomposing the network into multiple independent parts where belief propagation can be operated in parallel. Comparison between PD-LBP and two other state-of-the-art methods, Loopy Belief Propagation-based method and Reduced Binary Loopy Belief Propagation based method, is performed. The evaluation results demonstrate the desirable efficiency of PD-LBP from both the shorter problem solving time and smaller communication requirement of task allocation in dynamic environments.

UOW Authors


  •   Kong, Yan (external author)
  •   Zhang, Minjie
  •   Ye, Dayong (external author)

Publication Date


  • 2017

Citation


  • Kong, Y., Zhang, M. & Ye, D. (2017). A belief propagation-based method for task allocation in open and dynamic cloud environments. Knowledge-Based Systems, 115 (January), 123-132.

Scopus Eid


  • 2-s2.0-84995871772

Number Of Pages


  • 9

Start Page


  • 123

End Page


  • 132

Volume


  • 115

Issue


  • January