RB Multicast PROTOCOL Algorithms
Once the RB Multicast module receives packet, it retrieves the group list from its group table and assigns the group nodes to the multicast regions based on their locations. It uses these locations for calculation of “virtual nodes” location for each multicast region. The proposed RB Multicast replicates the packet for each multicast region that consists of one or more multicast members and appends a header consisting of a list of destination nodes (multicast members) in that region. The destination of a replicated packet is the “virtual node” of the corresponding multicast region, which can be determined in different ways e.g., as the geometric mean of the locations of all the multicast members in that multicast region. All packets for all multicast regions are inserted in the lower layer MAC queue, and are then broadcasted to the neighborhood [11].
Candidate selection is done before broadcasting packet to the neighboring nodes. Forwarding candidate is done using the distance of the virtual node and value of the ETX metric of neighboring node. Candidate selection is discussed in next section. The node closest to the virtual node and having low ETX value takes responsibility for forwarding the packet. The procedure for transmitting packets is summarized in pseudo code in Algorithm 1.
Working of RB Multicast PROTOCOL
Figure 1 gives an example of how RB Multicast works. The two multicast regions, the southwest and northwest quadrants, consists only one multicast member each, and thus a packet is sent directly to these multicast members. The northeast multicast region has three destination members, and thus a single packet is sent to the virtual node located at the geometric mean of the locations of the destination members (dotted circle with label 3 in the figure).
i. Multicast Regions: When a node receives a multicast packet it divides the network into multicast regions, and it will splits a copy of the packet to each region that consist of one or more multicast members. We show two possible divisions of the network into multicast regions in below Figures 2a and 2b.
ii. Packet Splitting: In Algorithm 1 and Algorithm 2, we describe the RB Multicast method that splits packets at intermediate nodes for which the multicast destinations exist in different regions [1]. This method is used in the protocol description because of its simplicity. In a variation of this method, namely, RBM-V, the packets are alternately split off at the neighbor nodes of the virtual node, which require extra time for splitting the packets compared to the former method [10].
iii. Virtual Node: Without considering the knowledge of neighbor nodes and no routing tables, it assign a node as virtual node located closer to the destination members by means of geographic information for each multicast region. This node (virtual) is considered as a temporary destination for the multicast packet in that region. The virtual nodes are not necessarily reachable as depicted in Figure 1. The idea behind this is that even if a virtual node does not exist, protocol can still find a route using the pretended receiver-based on the lower layer MAC protocol and uses this information to forward the packet much more closer to the location of the virtual node.
1. Geographic Mean i.e. location of Virtual Node:
- 𝑋= Xi𝑛𝑖=1 = Yi𝑛𝑖=1 (X,Y) Represent the location of virtual node.
- Xi = x coordinate of location of node i. Yi = y coordinate of location of node i.
- n = Total no. of multicast destination in a region.
2. ETX calculation: The proposed method uses the ETX metric for the multicast routing which is proposed by De Couto et al. For a single packet to send across a link, the ETX metric counts the expected number of transmissions required. Let Pf and Pr denote the loss probability of the link in the forward and reverse directions, respectively.
3. Then, the link's ETX [4] metric is calculated as:
ETX = 1/(1-pf).(1-pr) (1)
4. Candidate selection: Before broadcasting a packet to the neighboring nodes, node in the network calculates the ETX metric using above mentioned method. After calculations of the regions and a separate multicast destination lists are generated then candidate selection process is done. In candidate selection process firstly the nodes which are closer to the virtual node and in the range of current forwarding node are selected [14]. These nodes are added to the temporary list TCri , which is the list belonging to the region ri , Now the nodes in the TCri, prioritized according to the closeness of the nodes to the virtual node. Nodes which are closer to the virtual node are given the higher priority. After sorting a list, Nodes are again sorted using their ETX values, Nodes with low ETX value and closer to the destination are given higher priority and nodes with higher ETX are given low priority.
ALGORITHM 3: Candidate selection
Input: Neighboring nodes, ETX.
Output: actual Candidate list ACri.
1: Nlist = neighborlist(); //Get the neighbor list
2: For each i=1 to N //N=number of neighbor nodes
3: DVi = GetDistFrmVN (); // Cal distance from virtual node
4: TCri = TCri Ui; //Add node to temporary list
5: End for;
6: STCri = sort(TCri); //Sort list according to the DVi
7: ACri = sort(STCri); // Sort List according to the ETX values to get actual candidate list