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 is4 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 initi￾ates 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 tem￾porary 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