Research And Implementation Of Physarum-based Multicast Routing Algorithm In Dense Wireless Networks

With the emergence and development in 5G cellular systems and ultra dense networks,recent years have witnessed a surge of interest in Dense Wireless Sensor Network(DWSN)in academia and industry.Traditional problems like multicast tree building,topology design,etc,could be abstracted as Steiner tree problem(STP)in graph.Although many existing works have explored the STP in WSN scenarios,new challenges in DWSN introduced by growing node number and redundant links receive much less attention yet.Existing algorithms that could find optimal solutions usually have exponential running time factor on the terminal set’s scale,other approximate algorithms with lower time complexity cause too much performance loss.Few algorithms can balance the running time and performance loss of STP in DWSN properly.In this paper:(1)First,we propose a centralized physarum-based accelerating algorithm called PBA for boosting up traditional algorithms.The proposed algorithm could select crucial edges and vertices quickly,and eliminate edges and vertices irrelevant to the optimal solution by 80%and 50%in the original graph,respectively.The proposed algorithm can shorten the original algorithm’s running time by one to two orders of magnitude with less than 5%performance loss in general.(2)Secondly,we discuss the feasibility of completely random initializing and the communication mechanism between neighboring vertices,and propose a distributed version of PBA(DPBA)which could solve STP of DWSN in a distributed way.This proposed distributed algorithm could solve STP with much larger terminal set scale.DPBA could obtain the same simplified topology when giving the same input as PBA,while DPBA could distribute the computing task on each vertex evenly without global topology information.(3)Thirdly,we explore the relationship between empirical parameters and iterating times and how edge-cutting schema influences the final minimum Steiner tree.We try to reveal the internal relationship between empirical parameters in terms of performance and running time,which could show the direction of optimization in STP.The proposed physarum-based algorithms could simplify complex topologies and solve STP in DWSN scenario effectively.The proposed algorithms overcame shortcomings of poor performance or running time which exist in previous works,and increased the application possibility of STP in DWSN topology.This could result in performance enhancement in real world networks.