A Distributed Algorithm for DAG-Form Service Composition Over MANET

Service Composition in MANETs may suffer from overburden when computing optimal composition for complex service requirement on one pervasive device. To address this challenge, the paper presents a fully decentralized framework for service composition in MANETs. Firstly, it arranges heterogeneous devices into a hierarchical service overlay network and forms a service graph in proactive manner upon the overlay. Secondly, it distributes processing load for one composition to multiple overlay nodes by splitting and merging request into multiple simpler sub request graph based on heuristic scheme. It can provide balanced load and high scalability when composition requirement is complex, while achieve approximate optimality of the composition result. Experimental results demonstrate that the effectiveness of our solution.