Research On QoS Routing Approximation Algorithm For Internet Of Things

With the rapid development of Internet of Things(IoT),people put forward higher requirements for quality of service(QoS)of their business quality and networking technology.At present,how to guarantee QoS for better IoT becomes the key to the development and expansion of IoT industry.It is not only the current focus of international home appliances,IT manufacturers and other industry,but also the hot topic of academic research.According to the QoS requirements proposed by different service types and the resource allocation of the network environment,it is one of the practical and feasible schemes to study the efficient and feasible QoS routing algorithm and the effective operation of QoS routing mechanism.In the hot research of QoS algorithm such as intelligent algorithm and deterministic algorithm,the approximate algorithm has some advantages in engineering practice business application because of its high efficiency,reasonable and feasible characteristics in different network environments of IoT.This dissertation takes "the QoS routing algorithm for IoT" as the main line,and discusses several key problems such as multi-constrained QoS routing,multicast QoS routing,multicast multi-constrained QoS routing and QoS routing in Wireless Mesh Network(WMN)in business practice.Moreover,this dissertation finds out the solution of the current performance from the approximate point of view,and discusses its rationality in the application of different network environment.The main contents and contributions of this dissertation are as follows:(1)By studying the unicast multi-constrained QoS optimal routing problem,two efficient and feasible routing algorithms are proposed for different network environments respectively.Firstly,a routing algorithm with reasonable time and high approximate rate is proposed,aiming at the stable and reliable network environment and combining with the fastest deterministic algorithm.Then the optimal path is found by approximating all the QoS constraints from the approximate perspective.Secondly,a fast and feasible routing algorithm is proposed,aiming at the time-varying and unreliable network environment.By finding out the most important metric on each edge,the optimal path from the approximate perspective can be discovered and the QoS constraints can be tackled.The time complexity and approximation rate of the two algorithms are analyzed and proved,and the superiority of the performance is verified by simulation.In engineering practice,they are reasonable and efficient solution schemes in stable and reliable network and time-varying fault-tolerant network environment respectively.(2)By studying the problem of multicast spanning tree in the network,two efficient and feasible routing algorithms are proposed considering the number of multicast nodes and the state of distribution.In the case of more multicast destination nodes whose distribution is more concentrated,the total cost of multicast spanning tree can be reduced when it is joined with the multicast destination nodes according to the priority order through the combination of the best performance multicast tree algorithm and the basis of the idea of multicast path sharing.Finally,an efficient and feasible approximation algorithm is proposed.In another case of a small number of multicast nodes whose distribution is more decentralized,the priority value of the multicast node is adjusted and an improved and feasible approximation algorithm is proposed according to the distance between the destination node and the current spanning tree.The time complexity and approximation rate of the two algorithms are consistent with the best performance of the multicast spanning tree,which is proved by the theoretical analysis.The advantages of the two algorithms in different situations are verified by simulation.They are reasonable and feasible solutions in different numbers of destination nodes with different distributions in the multicast routing service.(3)By studying the optimal routing problem of multicast multi-constrained QoS,two efficient and feasible multicast tree algorithms are proposed for different network environments respectively.Firstly,the optimal multicast spanning tree is found by approximating all the QoS constraints from the approximate perspective and combining with the fastest deterministic algorithm with the rounding and scaling techniques,aiming at the stable and reliable network environment and based on the best-performing multicast tree algorithm.Consequently a routing algorithm with reasonable time and high approximate rate is proposed.Secondly,aiming at the time-varying and unreliable network environment,a fast and feasible routing algorithm is proposed by finding out the most important metric on each edge and the optimal multicast spanning tree which satisfies the QoS constraint from the approximate perspective.The time complexity and approximation rate of the two algorithms are analyzed and proved,and the superiority of the performance is verified by simulation.They are reasonable and efficient solutions for different network environments in engineering practice respectively.(4)By studying the Anypath routing in WMN network,an efficient and feasible Any path routing algorithm is proposed for WMN network with strong time-varying and fault-tolerant capability.According to the business application in engineering practice,a new Anypath routing problem is proposed and a mathematical model is established.According to the expected weight of Anypath routing,a specific QoS constraint is forced to approximate the other QoS constraints at the same time,and the Anypath route optimal path is found in the shortest time from the approximate perspective.An Anypath routing algorithm is proposed with the reasonable approximation rate and a time complexity consistent with the classical Dijkstra algorithm.The algorithm has good compatibility with the existing Anypath routing protocol.The time complexity and approximation rate of the algorithms are analyzed and proved,and the superiority of the performance is verified by simulation.It is a reasonable and efficient solution for WMN network environment in engineering practice.