2 Its theoretical properties and distributive nature render apply the MST algorithm locally for routing [8].Dijkstra- it suitable for sensor network architecture and protocol based Localized Energy-Efficient Multicast Algorithm (DLE- design for performance improvement. MA)finds energy shortest paths leading through nodes with The rest of paper is organized as follows.Section II states maximal geographical advance towards desired destinations related work.In Section III,we introduce our network model. [9].Hierarchical geographic multicast routing (HGMR)tries In Section IV,we present our Toward Source Tree Algorithm to combine the advantages of geographic multicast routing to construct a multicast tree.In Section V,VI and VII. (GMR)and hierarchical rendezvous point multicast (HRPM) we evaluate the performance of our algorithm mainly from [1O].It achieves transmission times close to GMR,encoding three aspects:multicast tree length,running time and energy overhead close to HRPM,and good packet delivery ratio efficiency separately.In Section VIl,we use extensive simu- in simulations.Our concern for delay and the running time lations to further evaluate the performance and also illustrate of multicast tree construciton is orthogonal to the evaluation how to apply our TST algorithm to practical applications.We metrics in HGMR.In summary,few works have considered conclude this paper and present discussions of future works minimizing the distance of multicast routing or providing in Section IX. comprehensive quantitative analysis theoretically on the per- formance of routing policies. II.RELATED WORK Approximate Steiner Tree.Shortest Path Heuristic(SPH)and We review related works in three categories:the application Kruskal Shortest Path Heuristic (KSPH)add new nodes to of minimum multicast tree,multicast routing and the approx- existing subtrees through the shortest path [15].Average Dis- imate Steiner tree. tance Heuristic (ADH)joins subtrees that contain receivers by Minimum-length Multicast Tree.The most significant ad- a path passing non-receivers with minimal average distance to vantage of minimum multicast tree in wireless sensor networks existing subtrees [16].Santos et al.pushed forward distributed is energy efficiency.As sensor nodes are often powered by dual ascent (DA)algorithm,achieving good performance in batteries that drain rather fast and are difficult to replace, practice [17].The comparison of these algorithms with our energy conserving is extremely crucial in sensor networks. TST algorithm is shown in Table 2.1.These algorithms Furthermore,nodes in sensor network consume most of its were proposed for point-to-point networks.In this paper, energy in communication [18].Hence,minimum multicast we consider the Steiner Tree Problem in wireless sensor tree-based routing is desirable in many cases.Specifically,it networks that are broadcast in nature.In addition,each node is extensively used in the following two applications in sensor has limited computation and storage capability.Devices are networks-user query and data aggregation. usually battery-powered,therefore energy-efficiency is of great As wireless sensor networks are mostly data centric [19], importance.Due to these specific features and requirements, users have to query for information and disseminate it in the existing algorithms for P2P are not suitable for WSN. network.To spread the query in a network as energy-efficient To sum up,there have been extensive existing works focus- as possible,we need to build a minimum multicast tree and ing on multicast tree construction or the approximate Steiner route the data following the trees topology [20].To achieve tree problems,but we have not found a perfect adoption of this,some existing works apply a Steiner tree-based approach Steiner tree into constructing multicast trees. [21]. Data aggregation is to integrate the data from different sources III.NETWORK MODEL and route for eliminating redundancy.It saves energy by reducing the number of transmissions [22].Minimum-length Let us first use mathematical model to capture a wireless tree topology is a widely used technique to solve the implosion sensor network.We assume the network consists of n nodes problems in data centric routing [20].In data aggregation,the in total (or we call the network size is n),distributed indepen- routing pattern of a sensor network is similar to a reverse dently and identically in a unit square.Each node is assigned multicast tree [20].Achieving the optimal data aggregation, with a unique identifier to be distinguished from others.Each i.e.,constructing the minimum multicast tree,is also treated time when a source needs to transmit messages,it chooses m as a Steiner tree problem [22]. receivers randomly.In other words,m is the number of nodes Besides improve energy efficiency and extending network life- that participate in a multicast transmission,or we call it the time,routing on a minimum multicast tree also has underlying multicast group size.For our statistical analysis,we focus on merits,such as indirectly reducing network delay [23].Since the dense network and large multicast group where m and n the total length of tree is minimized,it is obvious that the path are both very large,and m<n.This is particularly suitable won't be too long between the source and any destination. to describe a wireless sensor network. Multicase tree construction.Many studies focus on multicast The geographical distribution of nodes is described by a routing in wireless networks,and useful techniques for routing density function f(x)where x is the position vector.Here we have been proposed in WSN.Sanchez et al.proposed Geo-allow x to be of any dimension;in the rest of this paper we let graphic Multicast Routing (GMR),a heuristic neighborhood it be a two-dimensional vector for ease of presentation,but it selection algorithm based on local geographic information does not hurt any generality.We assume f(x)is independent [7].Later Park et al.[24]combined distributed geographic of n and m.We also assume that 0 <e1 f(x)<e2 multicasting with beaconless routing.In Localized Energy- where e and e2 are both constants,i.e.,a node has a positive Efficient Multicast Algorithm (LEMA),forwarding elements probability to be located in any region of this area.2 • Its theoretical properties and distributive nature render it suitable for sensor network architecture and protocol design for performance improvement. The rest of paper is organized as follows. Section II states related work. In Section III, we introduce our network model. In Section IV, we present our Toward Source Tree Algorithm to construct a multicast tree. In Section V, VI and VII, we evaluate the performance of our algorithm mainly from three aspects: multicast tree length, running time and energy efficiency separately. In Section VIII, we use extensive simu￾lations to further evaluate the performance and also illustrate how to apply our TST algorithm to practical applications. We conclude this paper and present discussions of future works in Section IX. II. RELATED WORK We review related works in three categories: the application of minimum multicast tree, multicast routing and the approx￾imate Steiner tree. Minimum-length Multicast Tree. The most significant ad￾vantage of minimum multicast tree in wireless sensor networks is energy efficiency. As sensor nodes are often powered by batteries that drain rather fast and are difficult to replace, energy conserving is extremely crucial in sensor networks. Furthermore, nodes in sensor network consume most of its energy in communication [18]. Hence, minimum multicast tree-based routing is desirable in many cases. Specifically, it is extensively used in the following two applications in sensor networks - user query and data aggregation. As wireless sensor networks are mostly data centric [19], users have to query for information and disseminate it in the network. To spread the query in a network as energy-efficient as possible, we need to build a minimum multicast tree and route the data following the trees topology [20]. To achieve this, some existing works apply a Steiner tree-based approach [21]. Data aggregation is to integrate the data from different sources and route for eliminating redundancy. It saves energy by reducing the number of transmissions [22]. Minimum-length tree topology is a widely used technique to solve the implosion problems in data centric routing [20]. In data aggregation, the routing pattern of a sensor network is similar to a reverse multicast tree [20]. Achieving the optimal data aggregation, i.e., constructing the minimum multicast tree, is also treated as a Steiner tree problem [22]. Besides improve energy efficiency and extending network life￾time, routing on a minimum multicast tree also has underlying merits, such as indirectly reducing network delay [23]. Since the total length of tree is minimized, it is obvious that the path won’t be too long between the source and any destination. Multicase tree construction. Many studies focus on multicast routing in wireless networks, and useful techniques for routing have been proposed in WSN. Sanchez et al. proposed Geo￾graphic Multicast Routing (GMR), a heuristic neighborhood selection algorithm based on local geographic information [7]. Later Park et al. [24] combined distributed geographic multicasting with beaconless routing. In Localized Energy￾Efficient Multicast Algorithm (LEMA), forwarding elements apply the MST algorithm locally for routing [8]. Dijkstra￾based Localized Energy-Efficient Multicast Algorithm (DLE￾MA) finds energy shortest paths leading through nodes with maximal geographical advance towards desired destinations [9]. Hierarchical geographic multicast routing (HGMR) tries to combine the advantages of geographic multicast routing (GMR) and hierarchical rendezvous point multicast (HRPM) [10]. It achieves transmission times close to GMR, encoding overhead close to HRPM, and good packet delivery ratio in simulations. Our concern for delay and the running time of multicast tree construciton is orthogonal to the evaluation metrics in HGMR. In summary, few works have considered minimizing the distance of multicast routing or providing comprehensive quantitative analysis theoretically on the per￾formance of routing policies. Approximate Steiner Tree. Shortest Path Heuristic (SPH) and Kruskal Shortest Path Heuristic (KSPH) add new nodes to existing subtrees through the shortest path [15]. Average Dis￾tance Heuristic (ADH) joins subtrees that contain receivers by a path passing non-receivers with minimal average distance to existing subtrees [16]. Santos et al. pushed forward distributed dual ascent (DA) algorithm, achieving good performance in practice [17]. The comparison of these algorithms with our TST algorithm is shown in Table 2.1. These algorithms were proposed for point-to-point networks. In this paper, we consider the Steiner Tree Problem in wireless sensor networks that are broadcast in nature. In addition, each node has limited computation and storage capability. Devices are usually battery-powered, therefore energy-efficiency is of great importance. Due to these specific features and requirements, existing algorithms for P2P are not suitable for WSN. To sum up, there have been extensive existing works focus￾ing on multicast tree construction or the approximate Steiner tree problems, but we have not found a perfect adoption of Steiner tree into constructing multicast trees. III. NETWORK MODEL Let us first use mathematical model to capture a wireless sensor network. We assume the network consists of n nodes in total (or we call the network size is n), distributed indepen￾dently and identically in a unit square. Each node is assigned with a unique identifier to be distinguished from others. Each time when a source needs to transmit messages, it chooses m receivers randomly. In other words, m is the number of nodes that participate in a multicast transmission, or we call it the multicast group size. For our statistical analysis, we focus on the dense network and large multicast group where m and n are both very large, and m ≤ n. This is particularly suitable to describe a wireless sensor network. The geographical distribution of nodes is described by a density function f(x) where x is the position vector. Here we allow x to be of any dimension; in the rest of this paper we let it be a two-dimensional vector for ease of presentation, but it does not hurt any generality. We assume f(x) is independent of n and m. We also assume that 0 < 1 ≤ f(x) ≤ 2 where 1 and 2 are both constants, i.e., a node has a positive probability to be located in any region of this area