1 Distributed Multicast Tree Construction in Wireless Sensor Networks Hongyu Gong',Luoyi Fu2,Xinzhe Fu2,Lutian Zhao3,Kainan Wang2,and Xinbing Wang Dept.of Electronic Engineering,Shanghai Jiao Tong University,China.Email:{ann,xwang8@sjtu.edu.cn. 2Dept.of Computer Science,Shanghai Jiao Tong University,China. Email:yiluofu,fxz0114,sunnywkn @sjtu.edu.cn 3Dept.of Mathematics,Shanghai Jiao Tong University,China.Email:golbez@sjtu.edu.cn. Abstract-Multicast tree is a key structure for data dissemina- causing more energy consumption as well as more serious tion from one source to multiple receivers in wireless networks. interference to neighboring nodes.Besides,as the transmission Minimum length multica modeled as the Steiner Tree Problem, and is proven to be NP-hard.In this paper,we explore how distance increases,the messages suffer from higher probability to efficiently generate minimum length mult wireless sensor of transmission failure. networks (WSNs),where only limited knowledge of network Recently,GEographic Multicast(GEM),inspired by Eu- topology is available at each node.We design and analyze a clidean Steiner Tree,was proposed for routing in dense simple algorithm,which we call Toward Source Tree (TST),to wireless networks [11].Formally,given a network G=(V,E), build multicast trees in WSNs.We show three metrics of TST the weight of each edges,and a set of terminals S C V. algorithm,i.e.,running and energy efficiency.We prove that its running time is O(Vn log n),the best among all existing solutions the Steiner Tree Problem is to find a tree in G that spans S to our best knowledge.We prove that TST tree length is in the with the minimum total weight [13].This problem has been same order as Steiner tree,give a theoretical upper bound and proven to be NP-hard [14],and has not been visited for a use simulations to show the ratio be only 1.114 when nodes are long time.Former forms of its approximate implementation uniformly distributed.We evaluate energy efficiency in terms of message complexity and the number of forwardin prove that were not appropriate for constructing multicast trees in WSNs they are both order-optimal.We give an efficient way to construct for various reasons (details will be discussed in the following multicast tree in support of transmission of voluminous data. section.)In GEM,the authors took the first step to utilize the Steiner tree for constructing multicast trees in WSNs, achieving routing scalability and efficiency.This approach can I.INTRODUCTION potentially reduce the tree length,but this very simple form Wireless Sensor Network (WSN)is a network of wireless of utilization only considers the hop count in an unweighted sensor nodes into which sensing,computation and commu- graph,but not the total length of the multicast tree in a nication functions are integrated.Sensors are self-organizing weighted graph.Further,as for the performance analysis,the and deployed over a geographical region [2].Multicasting, statistical properties were all under the assumption that all i.e.,one-to-many message transmission,is one of the most nodes are uniformly distributed,making it difficult to tell its common data transmission patterns in WSNs.Tree is the topol- efficiency under a realistic network environment. ogy for non-redundant data transmission.To enable efficient In this paper,inspired by taking the advantage of the multicast,multicast tree has been proposed and widely used. Steiner tree property,we design a novel distributed algorithm It has not only been used for multicast capacity analysis in to construct an approximate minimum-length multicast tree wireless networks [3]-[5],but in practice,multicast supports for wireless sensor networks,aiming at achieving energy a wide range of applications like distance education,military efficiency,ease of implementation and low computational command and intelligent system [6]. complexity,at an affordable cost on the sub-optimality of tree Many researchers have been working on constructing ef length.In what follows,we call our design Toward Source ficient multicast trees [7],[12].They have proposed a Tree Algorithm,or TST for short.We quantitatively evaluate number of algorithms so as to minimize the routing complexity TST algorithm performance under general node distribution, as well as achieve the time and energy efficiency (for details,and show that TST has the following satisfactory metrics: please refer to the next section),but most of them did not Its running time is O(vn log n).the best among all focus on an important performance measure:the tree length. existing solutions for large multicast groups. This is a critical metric since larger tree length clearly results Its tree length is in the same order as Steiner tree,and in longer delay.To enable the messages to be forwarded simulation shows the constant ratio between them is only farther,sensors have to increase their transmission power, 1.114 with uniformly distributed nodes. Its message complexity (which we will formally define Part of this work was reported in the MobiHoc 2015 [1] later)and the number of nodes that participate in for- Copyright (c)2014 IEEE.Personal use of this material is permitted. However,permission to use this material for any other purposes must be warding are both order-optimal,yielding high energy obtained from the IEEE by sending a request to pubs-permissions@ieee.org. efficiency for sensor networks
1 Distributed Multicast Tree Construction in Wireless Sensor Networks Hongyu Gong1 , Luoyi Fu2 , Xinzhe Fu2 , Lutian Zhao3 , Kainan Wang2 , and Xinbing Wang 1 1Dept. of Electronic Engineering, Shanghai Jiao Tong University, China. Email:{ann, xwang8}@sjtu.edu.cn. 2Dept. of Computer Science, Shanghai Jiao Tong University, China. Email:{yiluofu, fxz0114, sunnywkn}@sjtu.edu.cn 3Dept. of Mathematics, Shanghai Jiao Tong University, China. Email: golbez@sjtu.edu.cn. Abstract—Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multica modeled as the Steiner Tree Problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length mult wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple algorithm, which we call Toward Source Tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running and energy efficiency. We prove that its running time is O( √ n log n), the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, give a theoretical upper bound and use simulations to show the ratio be only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of message complexity and the number of forwardin prove that they are both order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data. I. INTRODUCTION Wireless Sensor Network (WSN) is a network of wireless sensor nodes into which sensing, computation and communication functions are integrated. Sensors are self-organizing and deployed over a geographical region [2]. Multicasting, i.e., one-to-many message transmission, is one of the most common data transmission patterns in WSNs. Tree is the topology for non-redundant data transmission. To enable efficient multicast, multicast tree has been proposed and widely used. It has not only been used for multicast capacity analysis in wireless networks [3]–[5], but in practice, multicast supports a wide range of applications like distance education, military command and intelligent system [6]. Many researchers have been working on constructing ef- ficient multicast trees [7]–[9], [12]. They have proposed a number of algorithms so as to minimize the routing complexity as well as achieve the time and energy efficiency (for details, please refer to the next section), but most of them did not focus on an important performance measure: the tree length. This is a critical metric since larger tree length clearly results in longer delay. To enable the messages to be forwarded farther, sensors have to increase their transmission power, Part of this work was reported in the MobiHoc 2015 [1] Copyright (c) 2014 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org. causing more energy consumption as well as more serious interference to neighboring nodes. Besides, as the transmission distance increases, the messages suffer from higher probability of transmission failure. Recently, GEographic Multicast (GEM), inspired by Euclidean Steiner Tree, was proposed for routing in dense wireless networks [11]. Formally, given a network G = (V, E), the weight of each edges, and a set of terminals S ⊆ V , the Steiner Tree Problem is to find a tree in G that spans S with the minimum total weight [13]. This problem has been proven to be NP-hard [14], and has not been visited for a long time. Former forms of its approximate implementation were not appropriate for constructing multicast trees in WSNs for various reasons (details will be discussed in the following section.) In GEM, the authors took the first step to utilize the Steiner tree for constructing multicast trees in WSNs, achieving routing scalability and efficiency. This approach can potentially reduce the tree length, but this very simple form of utilization only considers the hop count in an unweighted graph, but not the total length of the multicast tree in a weighted graph. Further, as for the performance analysis, the statistical properties were all under the assumption that all nodes are uniformly distributed, making it difficult to tell its efficiency under a realistic network environment. In this paper, inspired by taking the advantage of the Steiner tree property, we design a novel distributed algorithm to construct an approximate minimum-length multicast tree for wireless sensor networks, aiming at achieving energy efficiency, ease of implementation and low computational complexity, at an affordable cost on the sub-optimality of tree length. In what follows, we call our design Toward Source Tree Algorithm, or TST for short. We quantitatively evaluate TST algorithm performance under general node distribution, and show that TST has the following satisfactory metrics: • Its running time is O( √ n log n), the best among all existing solutions for large multicast groups. • Its tree length is in the same order as Steiner tree, and simulation shows the constant ratio between them is only 1.114 with uniformly distributed nodes. • Its message complexity (which we will formally define later) and the number of nodes that participate in forwarding are both order-optimal, yielding high energy efficiency for sensor networks
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 simulations 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 approximate Steiner tree. Minimum-length Multicast Tree. The most significant advantage 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 lifetime, 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 Geographic 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 EnergyEfficient Multicast Algorithm (LEMA), forwarding elements apply the MST algorithm locally for routing [8]. Dijkstrabased Localized Energy-Efficient Multicast Algorithm (DLEMA) 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 performance 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 Distance 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 focusing 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 independently 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
TABLE 2.1:Comparison of Distributed Algorithm for Approximate Steiner Construction Algorithm Expected tree length Expected time Expected messages Assumptions SPH [15] 2-approximation O(m logn 72 O(mn) Known shortest KSPG [15] Steiner tree. O(m/logn O(mn) paths;Point- ADH[I6可 O(m) to-point network. O(m1ogn n O(nlogn+mn) Unknown shortest DA[17] O(m 0(n2) 0(mn2) paths;Applied in Point-to-point network. Unknown shortest TST O(√m) O(vn logn) 0(m) paths;Applied in Wireless network. To ensure the connectivity of the whole network,we set Algorithm 1 Neighbor Request from Multicast Members the transmission ranger[25].For all nodes, 1:for all receiver R in a multicast group do r is the same and fixed.We assume that two nodes u and 2: the number of request session:0 v can communicate with each other directly if and only if 3: coverage range:re←r the Euclidean distance between them,duv,is no larger than 4: time out interval::To←日(2 klog n） r.Every node can obtain its own geographical location,e.g. 5: set the node sequence as {R via the Global Position System (GPS).However,nodes do 6: total hop:H←0 not know the exact location of other nodes until they receive 7: path length:p←0 messages containing that piece of information. 8: forward the request message to its neighborhood 9 while no response is received when time is out for the TABLE 3.1:System Parameter threquest session do 10: k←k+1 number of all nodes in the network 11 re←2r m number of receivers 12: Tk+1←2Tk transmission range 13: set the node sequence as {R 14: H←0 Te search coverage range 15: p←0 Lv length of temporary tree 16: forward the request message to its neighborhood LM length of multicast tree 17: end while 18:end for IV.ALGORITHM In this section,we describe our Toward Source Tree algo- rithm in detail.This algorithm consists of three phases.In the a message containing all receivers'identifiers is sent from the first phase,the source broadcasts a message and wakes up all source so that all nodes in the network can be aware whether receivers it chooses.In the second phase,every receiver choos- they are receivers.Upon receiving this message,receivers then es the closest neighboring receiver that has shorter Euclidean wake up,label themselves with"R"and be ready to participate distances to the source node than the receiver node itself.and in the multicast routing.The source will also specify its own then a"temporary tree"can be established among all receivers. location in this message. However"temporary tree"is a virtual topology since multicast This step is necessary for multicast routing since no one group members may not be connected directly to each other except the source knows which nodes the messages are desti- given limited transmission range.We select appropriate relays nated for.In this phase,the broadcast information will notify to keep these members connected while controlling the tree the nodes who are selected into the multicast group,and all length.However,till the end of this stage cycles might exist. receivers will be awakened. Hence we eliminate these cycles to further reduce tree length and avoid redundant transmissions in the third phase.In what follows we describe the process in detail,and we will use an B.Phase 2:Connecting All Receivers example to illustrate how to generate such a tree at the end of In this phase,we first build a"temporary tree"consisting of this section. only the multicast group members,and then find the minimum- hop shortest path between each pair of members that are A.Phase 1:Identifying Receivers directly connected in the "temporary tree".All multicast group Each node has a label indicating its role in the multicast tree: members will be connected with the newly added relays. “S”stands for the source and“R”for receivers.in this phase, Step 1:Searching Receivers in the Neighorhood
3 TABLE 2.1: Comparison of Distributed Algorithm for Approximate Steiner Construction Algorithm Expected tree length Expected time Expected messages Assumptions SP H [15] 2-approximation Steiner tree, O( √ m) O(m ➮ n log n ) O(mn) Known shortest paths; Pointto-point network. KSP G [15] O(m ➮ n log n ) O(mn) ADH [16] O(m ➮ n log n ) O(n log n + mn) DA [17] O( √ m) O(n 2 ) O(mn2 ) Unknown shortest paths; Applied in Point-to-point network. T ST O( √ m) O( √ n log n) O(n) Unknown shortest paths; Applied in Wireless network. To ensure the connectivity of the whole network, we set the transmission range r = Θ ✏➮log n n ✑ [25]. For all nodes, r is the same and fixed. We assume that two nodes u and v can communicate with each other directly if and only if the Euclidean distance between them, duv, is no larger than r. Every node can obtain its own geographical location, e.g., via the Global Position System (GPS). However, nodes do not know the exact location of other nodes until they receive messages containing that piece of information. TABLE 3.1: System Parameter n number of all nodes in the network m number of receivers r transmission range rc search coverage range LV length of temporary tree LM length of multicast tree IV. ALGORITHM In this section, we describe our Toward Source Tree algorithm in detail. This algorithm consists of three phases. In the first phase, the source broadcasts a message and wakes up all receivers it chooses. In the second phase, every receiver chooses the closest neighboring receiver that has shorter Euclidean distances to the source node than the receiver node itself, and then a “temporary tree” can be established among all receivers. However “temporary tree” is a virtual topology since multicast group members may not be connected directly to each other given limited transmission range. We select appropriate relays to keep these members connected while controlling the tree length. However, till the end of this stage cycles might exist. Hence we eliminate these cycles to further reduce tree length and avoid redundant transmissions in the third phase. In what follows we describe the process in detail, and we will use an example to illustrate how to generate such a tree at the end of this section. A. Phase 1: Identifying Receivers Each node has a label indicating its role in the multicast tree: “S” stands for the source and “R” for receivers. In this phase, Algorithm 1 Neighbor Request from Multicast Members 1: for all receiver R in a multicast group do 2: the number of request session: k ← 0 3: coverage range: rc ← r 4: time out interval: T0 ← Θ ⑨ 2 k log n ❾ 5: set the node sequence as {R} 6: total hop: H ← 0 7: path length: p ← 0 8: forward the request message to its neighborhood 9: while no response is received when time is out for the k th request session do 10: k ← k + 1 11: rc ← 2 k r 12: Tk+1 ← 2Tk 13: set the node sequence as {R} 14: H ← 0 15: p ← 0 16: forward the request message to its neighborhood 17: end while 18: end for a message containing all receivers’ identifiers is sent from the source so that all nodes in the network can be aware whether they are receivers. Upon receiving this message, receivers then wake up, label themselves with “R” and be ready to participate in the multicast routing. The source will also specify its own location in this message. This step is necessary for multicast routing since no one except the source knows which nodes the messages are destinated for. In this phase, the broadcast information will notify the nodes who are selected into the multicast group, and all receivers will be awakened. B. Phase 2: Connecting All Receivers In this phase, we first build a “temporary tree” consisting of only the multicast group members, and then find the minimumhop shortest path between each pair of members that are directly connected in the “temporary tree”. All multicast group members will be connected with the newly added relays. Step 1: Searching Receivers in the Neighorhood
In this step,each multicast member chooses an appropriate the multicast group.At the same time,all relay nodes on neighbor to connect to.The neighboring member selection the minimum-hop shortest path record this pair of members, criteria is:each member chooses the closest one from the set previous hop and the next hop on the path.When all receivers of members that have shorter Euclidean distances to the source send the connect message,a "temporary tree"among all node than this node itself.If no such neighboring member can mutlicast group members including the source is constructed. be found,then this multicast member directly connects to the source. Algorithm 2 Request Forwarding When a member tries to contact its neighbor members. 1:for all node u receiving request message do it is regarded as the sender that sends request message.Its 2: dist location of u-sender location form is:<sender id,sender location,location of previous 3: if dist <re then hop,coverage range re.node sequence,total hop H,path 4 add u to node sequence length p>.Sender id is used to identify the multicast members 5 H←H+1 sending the request message,and path length can be updated 6: newDist =location of u-location of previous hop with the location of previous hop and current hop.The coverage range re sets the range within which the multicast 7: p←-p+newDist member searches for its neighboring members.The Euclidean 果 forward the request message to its neighborhood distance between the sender and current node can be calculated if u is in the multicast group then with sender location,and messages will be discarded if the 10: nodeSourceDist =location of u-source location distance is larger than r.Node sequence records in order the nodes through which this message has passed,which acts as 11: senderSourceDist =sender location-source a guide for response from neighboring receivers so that the location response can be routed via the available path.The hop count 12: if nodeSourceDist i senderSourceDist then H is the number of hops the message has passed through,and 13: send respond message back to the sender p is the path length the message have been through when it 14: end if reaches the current node. 15: end if In each search session,the member broadcasts the request 16: end if message within search coverage range.The sender sets an 17:end for appropriate timeout interval.Once the sender receives replies from neighboring nodes,the search session terminates.Then it enters step 2.However,if time runs out and no reply is C.Phase 3:Eliminating Cycles obtained,it means that no appropriate neighboring members are found.The sender then doubles its search range and initi- In Phase 2,we construct a "temporary tree"made up of multicast group members.However,when other nodes are ates another search.In Algorithm 1,we show how a multicast group member connects to their neighboring members or the added to it as relays,cycles might be formed.In particular, when paths connecting different pairs of multicast members source. A node may receive more than one request message from share the same relay nodes,such node may receive redundant information,which indicates that cycles come into being the same sender.If it is within coverage range,it will choose Therefore,we check the existence of cycles in this phase and the one with the fewest hops among all the messages.If the eliminate them if any. numbers of hops are the same,it picks out the message with the shortest path length.Then it modifies this message.It adds Suppose a node u acts as a relay for k (>1)pairs of nodes itself to the node sequence,increases the hop count by 1 and in the multicast group,which are directly connected in the tem- calculates new path length given the location of the previous porary tree,denoted as (R11,R12).(R21,R22).....(Rk1,Rk2). Let us assume that in each pair,Ri is closer to source than hop.With these information updated,it forwards the message. Algorithm 2 describes how nodes deal with request messages Ri2 (1<i<k).A relay stores its previous and the next hop of the path from Ri to Ri2,and they are denoted as PHi in detail. When a multicast member finds it closer to the source than and NH;respectively.Then it chooses one pair randomly,say, the sender of the request message,it might be chosen as the (Rj1,Rj2)and keeps the information:(Rj1,Rj2.PHj,NHj). neighbor by the sender.Therefore,this member will choose For other pairs(Ri,Ri2)where Ri Rj1,the relay modifies a path to the sender and respond with the respond message. their information as(Rj1,Ri2.PHj,NH:).Define a set Q, The form of the respond message is:<sender id,respondent where Q={g|q=<R1,R2,PH:>,廿R1≠R1.Last, id,node sequence,total hop H,path length p>.The respond it sends "Eliminate message "and its previous hops delete message can be routed with the path information provided by unnecessary edges accordingly.In Algorithm 3,we show how to wipe out the cycles. the node sequence. Step 2:Connecting to the Nearest Neighbor With respond messages,every member selects the closest D.Proof of Tree Topology neighbor.Once a neighbor is chosen,the connect message is The previous subsections describe how we can connect forwarded via the minimum-hop shortest path.The connect mutlicast group members using our TST algorithm.Now let message is used to establish a connection between nodes in us prove that the topology constructed by TST algorithm is
4 In this step, each multicast member chooses an appropriate neighbor to connect to. The neighboring member selection criteria is: each member chooses the closest one from the set of members that have shorter Euclidean distances to the source node than this node itself. If no such neighboring member can be found, then this multicast member directly connects to the source. When a member tries to contact its neighbor members, it is regarded as the sender that sends request message. Its form is: <sender id, sender location, location of previous hop, coverage range rc, node sequence, total hop H, path length p>. Sender id is used to identify the multicast members sending the request message, and path length can be updated with the location of previous hop and current hop. The coverage range rc sets the range within which the multicast member searches for its neighboring members. The Euclidean distance between the sender and current node can be calculated with sender location, and messages will be discarded if the distance is larger than rc. Node sequence records in order the nodes through which this message has passed, which acts as a guide for response from neighboring receivers so that the response can be routed via the available path. The hop count H is the number of hops the message has passed through, and p is the path length the message have been through when it reaches the current node. In each search session, the member broadcasts the request message within search coverage range. The sender sets an appropriate timeout interval. Once the sender receives replies from neighboring nodes, the search session terminates. Then it enters step 2. However, if time runs out and no reply is obtained, it means that no appropriate neighboring members are found. The sender then doubles its search range and initiates another search. In Algorithm 1, we show how a multicast group member connects to their neighboring members or the source. A node may receive more than one request message from the same sender. If it is within coverage range, it will choose the one with the fewest hops among all the messages. If the numbers of hops are the same, it picks out the message with the shortest path length. Then it modifies this message. It adds itself to the node sequence, increases the hop count by 1 and calculates new path length given the location of the previous hop. With these information updated, it forwards the message. Algorithm 2 describes how nodes deal with request messages in detail. When a multicast member finds it closer to the source than the sender of the request message, it might be chosen as the neighbor by the sender. Therefore, this member will choose a path to the sender and respond with the respond message. The form of the respond message is: <sender id, respondent id, node sequence, total hop H, path length p>. The respond message can be routed with the path information provided by the node sequence. Step 2: Connecting to the Nearest Neighbor With respond messages, every member selects the closest neighbor. Once a neighbor is chosen, the connect message is forwarded via the minimum-hop shortest path. The connect message is used to establish a connection between nodes in the multicast group. At the same time, all relay nodes on the minimum-hop shortest path record this pair of members, previous hop and the next hop on the path. When all receivers send the connect message, a “temporary tree” among all mutlicast group members including the source is constructed. Algorithm 2 Request Forwarding 1: for all node u receiving request message do 2: dist = k location of u - sender location k 3: if dist < rc then 4: add u to node sequence 5: H ← H + 1 6: newDist = klocation of u - location of previous hopk 7: p ← p + newDist 8: forward the request message to its neighborhood 9: if u is in the multicast group then 10: nodeSourceDist = k location of u - source location k 11: senderSourceDist = k sender location - source location k 12: if nodeSourceDist ¡ senderSourceDist then 13: send respond message back to the sender 14: end if 15: end if 16: end if 17: end for C. Phase 3: Eliminating Cycles In Phase 2, we construct a “temporary tree” made up of multicast group members. However, when other nodes are added to it as relays, cycles might be formed. In particular, when paths connecting different pairs of multicast members share the same relay nodes, such node may receive redundant information, which indicates that cycles come into being. Therefore, we check the existence of cycles in this phase and eliminate them if any. Suppose a node u acts as a relay for k (k > 1) pairs of nodes in the multicast group, which are directly connected in the temporary tree, denoted as (R11, R12), (R21, R22),..., (Rk1, Rk2). Let us assume that in each pair, Ri1 is closer to source than Ri2 (1 ≤ i ≤ k). A relay stores its previous and the next hop of the path from Ri1 to Ri2, and they are denoted as P Hi and NHi respectively. Then it chooses one pair randomly, say, (Rj1, Rj2) and keeps the information: (Rj1, Rj2, P Hj , NHj ). For other pairs (Ri1, Ri2) where Ri1 6= Rj1, the relay modifies their information as (Rj1, Ri2, P Hj , NHi). Define a set Q, where Q = {q | q =< Ri1, Ri2, P Hi >, ∀ Ri1 6= Rj1}. Last, it sends “Eliminate message Q” and its previous hops delete unnecessary edges accordingly. In Algorithm 3, we show how to wipe out the cycles. D. Proof of Tree Topology The previous subsections describe how we can connect mutlicast group members using our TST algorithm. Now let us prove that the topology constructed by TST algorithm is
exactly a tree.We first show that temporary tree formed in 1(a).Solid nodes represent source nodes labeled by "S",or the second phase has a tree topology in Lemma 1.But relays multicast members labeled by "R".The hollow nodes can are added into the temporary tree to connect receivers,which be chosen as relays.The first step is to build a temporary might result in the existence of cycles.In Lemma 2 we show tree spanning all multicast members.The dashed lines denote that cycle elimination can in fact guarantee the tree topology. virtual connections between two members.Then nodes on the minimal-hop shortest path are engaged as relays between two Lemma 1:The temporary tree connecting m receivers has neighboring members.They form the topology as shown in a tree topology. Figure 1(b).Note that there exists a cycle marked with dotted Proof:Assume that each wireless node is identified with rectangular box.The last step is to eliminate unnecessary a unique label ni.We order these nodes based on their edges as is done in Figure 1(c).Finally we obtain the multicast distance from the source node,and we have an ordered set: tree as is shown in Figure 1(d). (n1,n2,...,nm}such that nj is closer to the source than ni for 1 <j<i.It is easy to show that ni can only connect to node in the set [n1,...,ni-1 according to our construc- tion algorithm.Such ordering guarantees that the generated 0 topology is acyclic.Besides,every multicast member tries to connect to another member that is closer to source,so every R member can find a path to the source.Naturally the generated topology is also connected.A connected and acyclic graph is a tree. 凤。 Algorithm 3 Cycle Elimination 1:for all node u engaged in paths between k pairs of (a)Building a temporary tree span- (b)Adding relay nodes members do ning multicast group members 2: choose an integer j such that 1≤j≤k 3: for all i such that 1≤i≤kand i≠jdo 4 forward Eliminate message Qi=<Ri1,Ri2,PHi> 5:end for 6:end for 7:for all node w receiving "Eliminate message Qi"do 8: if w is exactly PH;then 9: if w is not in the multicast group then 10: PHi+previous hop of w on path (Ri1,Ri2) 11: forward the modified Qi to the previous hop 12: eliminate information:(Ri,Ri2,PHi,NHi) 13: end if (c)Eliminating redundant edges and (d)Constructing the multicast tree 14 end if maintaining the topology of tree with relays added 15:end for Fig.4.1:Steps of the TST algorithm Based on Lemma 1,we have the following lemma: Lemma 2:The topology connecting nodes generated by TST V.LENGTH ANALYSIS algorithm is a tree that spans all multicast group members. The previous section described our Toward Source Tree Proof:The existence of cycles means that some nodes in algorithm.In the next three sections,we will discuss its the multicast tree may receive redundant messages,i.e.,some performance in terms of tree length,time complexity,and nodes have more than one previous hop.For these nodes,they energy efficiency.In this section,we discuss the length of TST. send "Eliminate messages"and ensure that they have only one We first obtain the length of temporary tree,first assuming previous hop.When all nodes in the multicast tree have only uniform distribution nodes and then extending to a general one previous hop,no cycle exists. setting.Next we explore the length of minimal-hop path that Multiple previous hops also indicate that multiple paths connects two receivers.Combining the length of temporary may exist between two nodes.Once some previous hops tree and the path,we can derive the upper bound for the are unnecessary,the paths involving these hops can also be multicast tree length. eliminated.Thus Algorithm 3 can eliminate these unnecessary paths,and this completes our proof. A.Temporary Tree in Uniform Distribution We start by discussing the tree length of the temporary tree. Lemma 3:Assume nodes are uniformly distributed in a unit E.Illustration square.The expected length of the temporary tree spanning m We use an example to illustrate our TST algorithm in Figure receivers is upper bounded by cvm,where c=5.622. 4.1.Nodes are distributed in the unit square as shown in Figure Proof:See Appendix A
5 exactly a tree. We first show that temporary tree formed in the second phase has a tree topology in Lemma 1. But relays are added into the temporary tree to connect receivers, which might result in the existence of cycles. In Lemma 2 we show that cycle elimination can in fact guarantee the tree topology. Lemma 1: The temporary tree connecting m receivers has a tree topology. Proof: Assume that each wireless node is identified with a unique label ni . We order these nodes based on their distance from the source node, and we have an ordered set: {n1, n2, ..., nm} such that nj is closer to the source than ni for 1 ≤ j < i. It is easy to show that ni can only connect to node in the set {n1, ..., ni−1} according to our construction algorithm. Such ordering guarantees that the generated topology is acyclic. Besides, every multicast member tries to connect to another member that is closer to source, so every member can find a path to the source. Naturally the generated topology is also connected. A connected and acyclic graph is a tree. Algorithm 3 Cycle Elimination 1: for all node u engaged in paths between k pairs of members do 2: choose an integer j such that 1 ≤ j ≤ k 3: for all i such that 1 ≤ i ≤ k and i 6= j do 4: forward Eliminate message Qi =< Ri1, Ri2, P Hi > 5: end for 6: end for 7: for all node w receiving “Eliminate message Qi” do 8: if w is exactly P Hi then 9: if w is not in the multicast group then 10: P Hi ← previous hop of w on path (Ri1, Ri2) 11: forward the modified Qi to the previous hop 12: eliminate information: (Ri1, Ri2, P Hi , NHi) 13: end if 14: end if 15: end for Based on Lemma 1, we have the following lemma: Lemma 2: The topology connecting nodes generated by TST algorithm is a tree that spans all multicast group members. Proof: The existence of cycles means that some nodes in the multicast tree may receive redundant messages, i.e., some nodes have more than one previous hop. For these nodes, they send “Eliminate messages” and ensure that they have only one previous hop. When all nodes in the multicast tree have only one previous hop, no cycle exists. Multiple previous hops also indicate that multiple paths may exist between two nodes. Once some previous hops are unnecessary, the paths involving these hops can also be eliminated. Thus Algorithm 3 can eliminate these unnecessary paths, and this completes our proof. E. Illustration We use an example to illustrate our TST algorithm in Figure 4.1. Nodes are distributed in the unit square as shown in Figure 1(a). Solid nodes represent source nodes labeled by “S”, or multicast members labeled by “R”. The hollow nodes can be chosen as relays. The first step is to build a temporary tree spanning all multicast members. The dashed lines denote virtual connections between two members. Then nodes on the minimal-hop shortest path are engaged as relays between two neighboring members. They form the topology as shown in Figure 1(b). Note that there exists a cycle marked with dotted rectangular box. The last step is to eliminate unnecessary edges as is done in Figure 1(c). Finally we obtain the multicast tree as is shown in Figure 1(d). R R R R R R R R R S (a) Building a temporary tree spanning multicast group members (b) Adding relay nodes (c) Eliminating redundant edges and maintaining the topology of tree (d) Constructing the multicast tree with relays added Fig. 4.1: Steps of the TST algorithm V. LENGTH ANALYSIS The previous section described our Toward Source Tree algorithm. In the next three sections, we will discuss its performance in terms of tree length, time complexity, and energy efficiency. In this section, we discuss the length of TST. We first obtain the length of temporary tree, first assuming uniform distribution nodes and then extending to a general setting. Next we explore the length of minimal-hop path that connects two receivers. Combining the length of temporary tree and the path, we can derive the upper bound for the multicast tree length. A. Temporary Tree in Uniform Distribution We start by discussing the tree length of the temporary tree. Lemma 3: Assume nodes are uniformly distributed in a unit square. The expected length of the temporary tree spanning m receivers is upper bounded by c √ m, where c = 5.622. Proof: See Appendix A