I. INTRODUCTION
Broadcasting is an inevitable operation in networks. Broadcasting is the process of transmitting packets that will be received by every device on the network. Many types of antennas are used for broadcasting. One such type is omni-directional antennas. Omni-directional antennas are capable of wide angle signal transmission. Compared to omni-directional antennas, its successor directional antennas have come up with significant advantages of reducing packet redundancy and interference by gaining higher signal-to-noise ratio. An older technique for broadcasting is flooding, where every node in the network transmits messages to its next hop after receiving it, which is considered to be an expensive operation that can tremendously have an adverse impact on networks leading to interference and packet flooding. As proposed by Hrishikesh [Reference Gossain, Joshi, De Morais and Agarwal1], in such a case if directional antennas are used, they form a beam toward the destination [Reference Ramanathan2], thereby reducing power consumption and redundancy. There are many issues regarding directional routing approaches. One solution is using an approximation algorithm which finds optimal solution for broadcast problems. Approximate directional routing protocol (ADRP) is a powerful routing protocol, a combo effect of directional routing protocol (DRP) and approximation algorithm that reduces interference and collision to the core and maximizes throughput.
From Fig. 1, suppose source node S wishes to send packets to a destination node D. Since both nodes S and D have their own notions of orientation, if source S sends packets in four orthogonal directions and destination D does the same thing, these packets will eventually intersect at at least two points. By forwarding packets to the forwarding node R, node S ensures connectivity with D while maintaining very little state. Without a location discovery scheme (which as we mentioned incurs rather large overhead), making no assumptions on node orientation (both nodes S and D have their own concept of “north”), geographical position (nodes S and D have their own perception of where they are physically), and position to address mapping, traditional geography-based routing protocols would be at a loss how to perform the task, ADRP reconciles this issue by utilizing an inherent property of Euclidean planes: that two unparalleled lines intersect, and build the routing scheme based off the intersection point.
Approximate directional routing protocol.
II. PROBLEM ANALYSIS
• Blind flooding is a fundamental operation in broadcasting, which can also lead to broadcast storm. Broadcast storm leads to bandwidth contention, redundancy, and collision problems. When switches are interconnected for redundancy, a broadcast originating from a node connected to any switch can cause circulation of broadcasts around the network and can saturate the network, consuming all available bandwidth known as BROADCAST STORM (as said by Rajiv Gandhi [Reference Gandhi, Kim, Lee, Ryu and Wan3], Chunyu hu [Reference Hu, Hong and Hou4]) a serious network problem and can shutdown the entire network in seconds.
• Interference is a major threat to networking. If two or more nodes send a message to a common neighbor, the common node will not receive any of the messages which means there exists collision at the common node.
• Sweeping is done frequently in networks. In order to perform a broadcast a transmitting node may carry out multiple transmissions from the antenna beams around it to cover the entire area of the network. There may be “n” number of transmissions equal to the number of beams which causes Route Request (RREQ) packets to flood the network and results in data redundancy and collision in the network causing the entire system to shut down.
A) ALL-TO-ALL problem
In all-to-all broadcast also known as gossip total exchange, every node in the network will transmit the message to every other node in the network. During this process a large amount of redundant data will flood the network (Fig. 2).
All-to-all broadcast (34 approximation algorithm).
III. SOLUTIONS
There is an algorithm which could solve all-to-all broadcast problems.
• ICDA – Interleaved Collect and Distribute Algorithm.
Every node in the network abruptly participates in broadcasting to minimize the latency. The main idea is: consider that a node receives a message forwarded originally from its descendants in the broadcast tree and relays it to its parent to deliver message to its root node. Parallel broadcasting is possible without waiting for the root node. We also define “super step” – collection of k time slots. In each super step, every node transmits almost one message. Both upward and downward transmissions are combined, giving priority to the upward transmission, first scheduling is carried out by the following set of guidelines.
(1) All terminal nodes send messages to their parents first.
(2) In each super step, primaries are scheduled before secondaries.
(3) Transmissions from primaries are scheduled based on vertex coloring.
(4) Each node can receive at most one upward message from its children. Therefore, a node can perform an upward transmission only if its parent has not received an upward message in the super step. Otherwise, it performs a downward transmission.
(5) For the secondaries, the nodes are considered in the same order as the broadcast tree is constructed. Upward transmissions are scheduled before downward transmissions.
(6) Once all upward transmissions for nodes are scheduled, the remaining nodes perform downward transmissions if there is any message to be sent.
A) Interleaved gossiping algorithm
As proposed by Huang et al. [Reference Huang, wan, Jia, Du and shang5], interleaved gossiping algorithm (IGA) works similar to collect and distribute algorithm (CDA). The algorithm works as follows: transmissions may be upward or downward. There are two phases involved in it, they are:
In the first phase, a simplified data collection algorithm is followed. A node “a” collects all messages using data collection algorithm. A breadth first search (BFS) tree is constructed from “a” and messages are sorted in non-decreasing order. Messages close to “a” are sorted first.
In the second phase, we first construct a broadcast tree and describe a transmission scheduling algorithm. For each message, the root node collects all messages and performs one-to-all broadcasting. To make the scheduling collision free, we propose vertex coloring technique, such that nodes with same color can broadcast a message without collision. Results show that 17 colors are enough to obtain collision free schedule.
The scheduling for a graph can be computed using vertex coloring. Let h1 and h2 be the graphs. If Vertex coloring is done for h1 then K1 be the number of colors needed. If vertex coloring is done for h2 then k 2 be the number of colors needed. k = k1 + k2, a group of consecutive time slots k is called a super step. Depending on the BFS levels, secondary nodes are divided into three sets. Each set is divided into four non-interfering groups.
B) Multi-source broadcast algorithm
As proposed by Rajiv Gandhi [Reference Gandhi, Mishra and Parthasarathy6], each node creates its own broadcasts tree and schedule transmissions greedily. In this algorithm, each source s of the message computes a broadcast tree rooted at itself. Message i is broadcast along tree rooted at s. Message i1 gets priority over i2 iff i1 < i2. This priority is enforced by scheduling i1 before i2.
IV. COMPARING IGA VERSUS MULTI SOURCE BROADCASTING (MSB)
In our experiments, we compare our proposed algorithm with existing schemes. Gandhi et al. [Reference Gandhi, Mishra and Parthasarathy6] present all-to-all algorithm called MSB. In MSB, each node creates its own broadcast tree and schedule transmission greedily. We compare our proposed algorithm MSB with that of IGA proposed by Huang et al. [Reference Huang, wan, Jia, Du and shang5].
We present the average approximation for our all-to-all broadcast schemes (CDA and ICDA), MSB and IGA by varying the number of nodes and square sizes. We now compare the performance of CDA and ICDA. Of all the algorithms so far we have seen that the ratio increases as the network size increases. There is an excellent performance by CDA when the network size is smaller.
A) All-to-all broadcasting module
In all-to-all broadcasting strategies, an all-to-all algorithm called IGA is proposed, which works similar to CDA except for the transmission schedule of secondary nodes. In IGA, secondary nodes are divided by three sets depending on their BFS level. Then, each set is divided into four non-interfering groups by running Iterative Minimal Covering algorithm [Reference Huang, Du and Park7], which results in the bound of 12 time slots for secondary nodes. Gandhi et al. present an all-to-all algorithm (which we call MSB). In MSB, each node creates its own broadcast tree and schedules transmissions greedily in this technique; we consider two algorithms, namely “Multi-Source Broadcasting and Collect and Distribute Algorithm”. Topology with more number of nodes from 25, 50, 75, 100, and transmission is performed using all-to-all technique implemented using CDA and MSB technique.
B) Comparison between one-to-all and all-to-all strategies in terms of approximation ratios
An approximation ratio is developed and based on that comparison is made between one-to-all and all-to-all algorithms to choose a best algorithm that finds optimal solutions to the problems we considered. Topology with more number of nodes from 25, 50, 75, and 100, and transmission is performed by a new proposed method of APPROXIMATION SCHEME to improve one-to-all and all-to-all technique considering the parameters: delay, throughput, latency, and approximation ratio.
C) Approximation technique overlapped onto directional routing protocol
Topology with more number of nodes from 25, 50, 75, and 100, and transmission is performed by a new proposed method of APPROXIMATION SCHEME to compare with DRP, considering the parameters: delay, throughput, latency, and approximation ratio.
The best algorithm chosen above is overlapped onto DRP, which works similar to Dynamic Source Routing. There are two essential tables maintained in DRP which are directional neighbor table (DNT) and directional routing table (DRT).
V. EVALUATION AND SIMULATION
A) Graphs: approximation ratio
1) THE SIMULATIONS ARE ENTIRELY CARRIED OUT IN NS-2
In Fig. 3, performance difference between CDA and MSB became smaller in larger networks. This is because both schemes first send all packets to the root before distributing them, and the initial latency increases with the network size growth. Except for the 100-node case, we observe that our all-to-all schemes achieve significant performance improvement over IGA. Specifically, CDA consistently outperforms IGA by 20–33%. Even though IGA works in a way similar to CDA, IGA uses three times more time slots for secondary nodes than CDA and thus takes longer time to complete all-to-all broadcasting.
Approximation ratio of CDA and ICDA.
The performance gap between ICDA and MSB becomes larger as the network size increases, which clearly shows the benefits of interleaved transmissions. The performance gap between ICDA and IGA grows. Results show that both CDA and ICDA consistently use fewer transmissions than MSB. The trans mission overhead of IGA and CDA is almost the same although IGA uses slightly more transmission.
B) Performance evaluation of IGA and MSB
In Fig. 4, performance evaluation between IGA and MSB is plotted by taking number of nodes in the X-axis and approximation ratio in the Y-axis. By taking the metrics as packet delivery ratio, routing overhead per received packet, average end-to-end delay packets, and power consumption the graph is plotted.
Performance evaluation of IGA and MSB.
C) Performance evaluation of CDA, ICDA, MSB, and IGA
In Fig. 5, performance comparison between CDA, ICDA, MSB, and IGA are compared based on the metrics: packet delivery ratio, routing overhead per received packet, average end-to-end delay packets, and power consumption.
Performance evaluation of CDA, ICDA, MSB, and IGA.
D) Initialization phase
In Fig. 6, the above NAM demonstrates flat grid topology screen constructed with an area of 1000 × 1000 m2 area. Here, 27 nodes build with a distance of 450 m2 for each node. All the nodes build their neighbors table during the initialization phase.
Initialization phase.
E) Data transfer
In Fig. 7, node 1 initiates and starts data transfer to the 25th node. It updates routing table information and finds the forwarding node and passes the data to that node. Finally, it will reach the destination.
Data transfer.
VI. CONCLUSION AND FUTURE WORK
In this paper, an approximation algorithm for broadcasting in a multi hop wireless network is proposed. The algorithms for all-to-all broadcasting give approximation ratios of 20 and 34. The proposed schemes perform much better than the theoretical bound and achieve higher percent latency performance improvement over the existing schemes. I have successfully implemented ADRP protocol in the network simulator. Assure that ADRP considerably reduces packet latency and delay and thus the result is represented in the form of graphs.
In future, propose an ADRP algorithm that finds optimal solution for all broadcast problems by implementing approximation algorithms using the DRP protocol in wireless networks. ADRP provides connectivity under lessened global information (close to 98% reachability in most general cases) and utilizes the medium more efficiently (due to directionality of communications).
ACKNOWLEDGEMENT
The author thanks Dr V. Palanisamy, Principal, Info Institute of Engineering for rendering all sorts of guidance and putting me on the right track for the paper's progress.
Mrs Sathya Sathiskumar received her BE degree in Computer Science and Engineering from Syed Ammal Engineering College in 2006 from Anna University Chennai, her M. Tech degree from Anna University Coimbatore, and is doing her research in Anna University Coimbatore as a full time scholar. Her research interest includes routing protocols, Network topologies, and wireless networks.
