Routing In The Wireless Sensor Network And An Approximation Algorithm For The Influential Nodes In Social Network

In the study of wireless sensor network routing problems, people want to find a routing protocol to make the information efficiently and effectively low mutual trans-fer。At present, there are two main methods in the studying of wireless sensor network routing problems:the first is to find the virtual backbone in sensor networks to assist information transfer; the second is to propose some routing protocols routing etc. to realize routing. We know that CDS in undirected graph can play a virtual backbone role, while the corresponding SCDAS in directed graph also can play the same role. In this paper, for a directed graph we give an5α+optDAS approximation algorithm of SCDAS problem. where a is the approximation ratio of DAS in the directed graph. For the routing protocol, this paper presents a routing algorithm by the auxiliary graph, and using local structural information to ensure efficient virtual coordinate information transmission in sensor networks.We can divide the social network influence set problems into one step and multiple steps effect。For the selection problem of one step effect set there is almost no approxi-mation algorithm, and for the selection problem of multiple steps effect set, people have proved that there is no trivial approximation algorithm. In this paper, for the selection problem of one step effect set we give an approximation algorithm whose approximation ratio is αl(Δ+1)/δ+1by using the relationship between the maximal independent set and the influence sets.This paper is divided into four chapters。The first chapter introduces the main re-search background, research current status and the main methods of research. The sec-ond chapter mainly introduces a kind of routing, which is a kind of extension of GLIDER method in in undirected graph. First we extend Voronoi cell and Delaunay graph from non directed graph into digraph, and obtain some properties of directed graph. And then in the second and third chapters we use local information to define new virtual coordi-nate type to guarantee the success rate of the information transmission is one hundred percent. In the third chapter, for strongly connected directed graph control absorbing set we give an approximation algorithm whose approximation ratio is5α+optDAS, where α is the approximation ratio of DAS of the directed graph In the fourth chapter we design an approximate algorithm for social networks influence set, and obtain its approximation ratio which is αl(Δ+1)/δ+1,where Δ,δ and αl are respectively the maximum and minimum degree and local independent number.