time needed for multicast tree construction is O Theorem 4:Let n nodes be independently and identically the region with time complexity smaller than distributed in the unit square.The number of forwarding nodes in the multicast tree is infeasible.Accurate solution to Steiner tree problem achieves the approximation ratio of 1 at the cost of exponential time, and our algorithm achieves the ratio of 10.The approximation (7-1) ratio of other algorithms like those in Table 2.1 approaches 1 Θ(m): m =W but they have larger time costs. When m=O(n/logn),the number of forwarding nodes is order-optimal. Approximation ratio Proof:Let Ty be the virtual tree,ei.j be an edge in the of tree length virtual tree connecting two receivers i and j,and di.j be the Euclidean distance between them.When m is small,relay nodes form the dominant part of the forwarding nodes in our multicast tree.The total number of transmitting nodes,NTsr 10- in the Toward Source Tree is:Nrsr=e \et,i∈Tv -()As m grows larger,receivers are close to each Infeasible other and thus fewer relay nodes are added.Therefore,re- region ceivers are dominant in the multicast tree,Nrsr =e(m). O(c)Complexity We should discuss the number of forwarding nodes in two O(Vn/log n O(Vn log n) cases,and there exists a critical value for m that determines in Fig.6.1:Relationship between tree length and time complexity which case it should be discussed.The critical value satisfies: 6(-)=6(mc),some=6() Denote Nmin as the minimal number of relay nodes that VII.ENERGY EFFICIENCY are engaged in propagating the messages from one source to m receivers.[3]gives the lower bound of Nmin under Energy is a primary consideration in wireless sensor net- the assumption that all nodes are uniformly distributed.Now works since sensors are battery-powered and their energy we use its method and explore Nmin in the case of gen- is limited.We consider the following factors:1)the energy eral distribution.When m is small,the distance between consumed to construct such multicast trees;and 2)the energy two receivers is large compared with the transmission range. needed to send messages along the tree constructed by this Nin.This lower bound is achievable with our algorithm.The former one is usually measured by the amount algorithm.so Nin().When m is very large,there of exchanged messages to run distributed routing algorithms; exist many receivers within the transmission range of one and the latter directly depends on the number of nodes node,so that one transmission can deliver messages to a large participating in the transmission.We focus on both aspects. number of receivers.In this case,we only need to choose a connected dominating set from m receivers,and Nmin is exactly the size of minimum connected dominating set.We A.Message Complexity will give the definitions of both connected dominating set and The following theorem quantifies the message complexity minimum connected dominating set. in TST. Definition I(Connected dominating set):D is the connected Theorem 3:Let n nodes be independently and identically dominating set of a graph G if and only it satisfies two distributed in the unit square.The message complexity of TST properties: algorithm is O(n). Proof:See Appendix A. Remark:Since each node needs a message telling them (a)Any node in D can reach any other node in D by a path whether they are chosen as receivers,the lower bound of that stays entirely within D. message complexity is O(n).Hence TST algorithm is an (b)Every vertex in G either belongs to D or it is adjacent to order-optimal solution in terms of message complexity. a vertex in D. Definition 2 (Minimum connected dominating set):MD is B.Number of Forwarding Nodes the minimum connected dominating set of graph G if MD is Since the transmission range is fixed,the number of trans- the connected dominating set containing the smallest number of nodes. mitters in the tree determines the energy consumption for in- formation propagation.We evaluate the number of forwarding We still need to discuss Nmin in two cases.There also nodes in this subsection. exists a critical value md,and (md)=(m).so ma=9 time needed for multicast tree construction is O ✏➮ n log n ✑ , the region with time complexity smaller than O ✏➮ n log n ✑ is infeasible. Accurate solution to Steiner tree problem achieves the approximation ratio of 1 at the cost of exponential time, and our algorithm achieves the ratio of 10. The approximation ratio of other algorithms like those in Table 2.1 approaches 1 but they have larger time costs. O(√n/log n ) O(√n log n) O(c ) Complexity Approximation ratio of tree length 1 10 { Infeasible region n Fig. 6.1: Relationship between tree length and time complexity VII. ENERGY EFFICIENCY Energy is a primary consideration in wireless sensor net￾works since sensors are battery-powered and their energy is limited. We consider the following factors: 1) the energy consumed to construct such multicast trees; and 2) the energy needed to send messages along the tree constructed by this algorithm. The former one is usually measured by the amount of exchanged messages to run distributed routing algorithms; and the latter directly depends on the number of nodes participating in the transmission. We focus on both aspects. A. Message Complexity The following theorem quantifies the message complexity in TST. Theorem 3: Let n nodes be independently and identically distributed in the unit square. The message complexity of TST algorithm is O(n). Proof: See Appendix A. Remark: Since each node needs a message telling them whether they are chosen as receivers, the lower bound of message complexity is O(n). Hence TST algorithm is an order-optimal solution in terms of message complexity. B. Number of Forwarding Nodes Since the transmission range is fixed, the number of trans￾mitters in the tree determines the energy consumption for in￾formation propagation. We evaluate the number of forwarding nodes in this subsection. Theorem 4: Let n nodes be independently and identically distributed in the unit square. The number of forwarding nodes in the multicast tree is NT ST = ✽ ❁ ✿ Θ ✏➮ mn log n ✑ , m = O ⑨ n log n ❾ ; Θ(m), m = ω ⑨ n log n ❾ . (7-1) When m = O (n/ log n), the number of forwarding nodes is order-optimal. Proof: Let TV be the virtual tree, ei,j be an edge in the virtual tree connecting two receivers i and j, and di,j be the Euclidean distance between them. When m is small, relay nodes form the dominant part of the forwarding nodes in our multicast tree. The total number of transmitting nodes, NT ST in the Toward Source Tree is: NT ST = Θ ❶ P ei,j∈TV dij r ➀ = Θ ⑨ √m r ❾ . As m grows larger, receivers are close to each other and thus fewer relay nodes are added. Therefore, re￾ceivers are dominant in the multicast tree, NT ST = Θ(m). We should discuss the number of forwarding nodes in two cases, and there exists a critical value for m that determines in which case it should be discussed. The critical value satisfies: Θ ⑨ √mc r ❾ = Θ(mc), so mc = Θ ⑨ 1 r 2 ❾ . Denote Nmin as the minimal number of relay nodes that are engaged in propagating the messages from one source to m receivers. [3] gives the lower bound of Nmin under the assumption that all nodes are uniformly distributed. Now we use its method and explore Nmin in the case of gen￾eral distribution. When m is small, the distance between two receivers is large compared with the transmission range. Nmin = Ω ⑨ √m r ❾ . This lower bound is achievable with our algorithm, so Nmin = Θ ⑨ √m r ❾ . When m is very large, there exist many receivers within the transmission range of one node, so that one transmission can deliver messages to a large number of receivers. In this case, we only need to choose a connected dominating set from m receivers, and Nmin is exactly the size of minimum connected dominating set. We will give the definitions of both connected dominating set and minimum connected dominating set. Definition 1 (Connected dominating set): D is the connected dominating set of a graph G if and only it satisfies two properties: (a) Any node in D can reach any other node in D by a path that stays entirely within D. (b) Every vertex in G either belongs to D or it is adjacent to a vertex in D. Definition 2 (Minimum connected dominating set): MD is the minimum connected dominating set of graph G if MD is the connected dominating set containing the smallest number of nodes. We still need to discuss Nmin in two cases. There also exists a critical value md, and Θ(md) = Θ ⑨ √md r ❾ , so md =