INDEX TERMS 
Wireless networking, approximation algorithms, broadcast algorithms, wireless scheduling. 
INTRODUCTION 
NETWORKWIDE broadcasting is a fundamental operation in wireless networks, in which a message needs to be
transmitted from its source to all the other nodes in the network. There may be multiple messages to be broadcasted from
multiple sources. Given that key applications of multihop wireless networks include prompt object detection using sensors,
the design of lowlatency broadcasting scheme is essential to meet stringent endtoend delay requirements for higherlevel
applications. Interference is a fundamental limiting factor in wireless networks. When two or more nodes transmit a
message to a common neighbor at the same time, the common node will not receive any of these messages. In such a case,
we say that collision has occurred at the common node. Interference range may be even larger than the transmission range,
in which case a node may not receive a message from its transmitter if it is within the interference range of another node
sending a message. Approximation algorithms are algorithms used to find approximate solutions to optimization problems.
Approximation algorithms are often associated with NPhard problems, since it is unlikely that there can ever be efficient
polynomialtime exact algorithms solving NPhard problems. One of the earliest broadcast mechanisms proposed in the
literature is flooding [1], [2], where every node in the network transmits a message to its neighbors after receiving it.
Although flooding is extremely simple and easy to implement, Ni et al. [3] show that flooding can be very costly and can
lead to serious redundancy, bandwidth contention, and collision: a situation known as broadcast storm. 
A. Our Contributions 
We present algorithms for ONETOALL and ALLTOALL broadcasting problems. In onetoall broadcast, there is a
source that sends a message to all other nodes in the network. In alltoall broadcast each node sends its own message to all
other nodes. Even the onetoall broadcasting problem is known to be NPcomplete [4]. For both problems, we develop
approximation algorithms, which improve the previous results. For ONETOALL BROADCAST problem, we present a
simple approximation algorithm that achieves a 12approximate solution, thereby improving the approximation guarantee
of 16. Our algorithm is based on the algorithm of Gandhi et al. [4] and incorporates the following two ideas that lead to the
improvement: 1) processing the nodes greedily—in non increasing order of the number of receivers, and 2) allowing nodes
to transmit more than once. For the ALLTOALL BROADCAST problem we present two algorithms (called CDA and
ICDA) with approximation guarantees of 20 and 34, respectively, thereby improving the approximation guarantee of 27. In
ICDA, all nodes are scheduled to participate in transmissions as early as possible. Our algorithms achieve up to 37 percent
improvement on endtoend latency over existing schemes. 
RELATED WORKS 
Several techniques have been proposed for broadcasting in wireless networks. In order to reduce the broadcast
redundancy and contentions, they make use of nodes’ neighborhood information and determine whether a particular node
needs to transmit a message [5], [6]. There has been some work on latencyconstrained broadcasting in wired networks [7]
and some results do exist for radio networks whose models are essentially the same as ours. This result does not directly
extend to ad hoc networks which are modeled by a restricted class of geometric graphs called disk graphs.
Gandhi et al. [4] show that minimizing broadcast latency in wireless networks is NPcomplete and then present an
approximation algorithm for onetoall broadcasting. 
A. Network Model 
When the interference range and the transmission range are identical, a wireless network can be modeled as a unit disk
graph (UDG), G(V,E). The nodes in V are embedded in the plane. Each node u has a unit transmission range. Let uj; vj
denote the Euclidean distance between u and v. We assume that time is discrete. We assume that every message
transmission occupies a unit time slot: i.e., the latency of a single successful transmission is one unit of time. We say that
there is a collision at node w, if w hears a message from two transmitters at the same time. In such a case, we also say that
the two transmissions interfere at w. A node w receives a message collision free iff w hears the message without any
collision. 
B. Problem Statement: 
Disk graph G= (V, E) and a set of messages M=(m1; m2; . . .;mn).A set of sources for these messages are taken as
sources: (sjsj is the source of message j). A node can transmit message j only after it receives message j collision free. A
schedule specifies, for each message j and each node i, the time at which node i receives message j collision free and the
time at which it transmits message j. If a node does not transmit a message then its transmit time for that message is 0. The
latency of the broadcast schedule is the first time at which every node receives all messages. The number of transmissions
is the total number of times every node transmits any message. The goal is to compute a schedule in which the latency is
minimized. For that onetoall and manytoall broadcasting is used. Onetoall broadcasting is the operation where there is
one source node s which has a message to send all other nodes. In alltoall broadcasting each node v has its own message
m to send all other nodes. 
ONETOALL BROADCAST ALGORITHM 
This algorithm takes the input and a source node s. If a node u is parent node of the node w then u is responsible
for transmitting the message to w without any collision. This algorithm leads to significantly improved approximation guarantee are 1. Processing node in a greedy manner 2. Allowing a node to transmit more than once. It leads to guarantee
that receiver node will receive the message collision free by overcoming broadcast problem. This algorithm first constructs
BFS Tree. In BFS the non increasing order of nodes are the primary nodes. The children of the primary nodes are secondary
nodes. In ONETOALL BROADCAST, the transmissions are scheduled in two phases. In Phase 1, the algorithm
schedules transmissions only to the nodes in set X which contains all primary nodes and non leaf secondary nodes in the
tree. In Phase 2, transmissions are scheduled to send the message to all other nodes. In Phase 1, nodes are considered one
level at a time starting from Level 0. Only those primary nodes that have a child will transmit the message in this phase.
The Primary nodes that doesn’t have child will transmit in the phase 2. 
ALLTOALL BROADCAST ALGORITHM 
In all to all broadcast, every node in the network will transmits the message to every other node in the network. To
overcome problem we change the value in approximation ratio as 20 and 34 using Collect and Distributed Algorithm(CDA)
and Interleaved Collect and Distribute Algorithm(ICDA). In terms of transmission overhead, our algorithm shows that both
CDA and ICDA consistently use fewer transmissions than existing one. 
A. CollectandDistribute Algorithm (CDA) 
The algorithm consists of 2 phases. In phase 1, source node collects all the packets by performing upward transmissions.
In the Phase 2, source node broadcasts all the n packets to all other nodes via downward transmissions. 
Phase 1. The source node collects all messages. The algorithm is as follows: first construct a BFS tree from s, and sort
messages in non decreasing order of the level in the BFS tree. That is, messages that are closer to s appear first in the sorted
list. Let us assume that message j be the jth message in the sorted order. The latency of the collection algorithm is at most
reduced. 
Phase 2. We construct a broadcast tree. Next, we describe transmission scheduling algorithm. In the algorithm by Gandhi et
al. [4], the root node collects all messages and performs onetoall broadcasting for each message. The root node needs to
wait until the previous message reaches the level before initiating a broadcast for another message to make sure there are no
collisions in their algorithm. In this algorithm, we find a schedule by a vertex coloring, which makes sure that all the nodes
with the same color can broadcast a message without collision, and show that 17 colors are enough to obtain a collisionfree
schedule. Then computing the broadcast tree and let k1,k2 be the number of colors. We define a superstep for k time slots.
In each superstep, the first k1 slots are for scheduling transmissions from primaries, and the remaining k2 slots will be for
secondaries. Each primary with color i is only allowed to transmit in the ith slot of a primary slot in a superstep. Each
secondary receiving a packet in a superstep transmits the received packet in the corresponding secondary slot in the same
superstep. 
B. Interleaved CollectandDistribute Algorithm (ICDA) 
In the early stages of the algorithm, until s receives all the messages and starts propagating them, most nodes are idle,
thus increasing the broadcast time significantly. Thus it describes an algorithm in which all nodes participate in
broadcasting as soon as possible so as to minimize the broadcast time. A node v receives a message m forwarded
originally from its descendant x in the broadcast tree and relays it to its parent to deliver the message to the root node s.The
children of v can also receive the message when v broadcasts it. Using the broadcast tree constructed as in CDA, we
schedule transmissions for each node as follows: as in CDA, we define a superstep but in a slightly different way. That is,
in each superstep, every node transmits at most one message (either upward or downward). Instead of finishing all upward
transmissions first, we mix upward or downward transmissions in each superstep with preferences given to upward
transmissions. 
C. Results for OnetoAll Broadcast 
While we have experimented with various settings, we only report a set of representative results in the rest of this
section. In Fig. 2, we present the average approximation ratios when we vary the number of nodes within a fixedsize
square 1000 m _ 1000 m. Our proposed algorithm consistently outperforms existing schemes by 1240 percent.
Specifically, in the 400node scenario, the average approximation ratio of our algorithm is 1.74, which is around 21 percent
smaller than that of GPM (2.22) and PBS (2.21) and 40 percent smaller than that of EBS (2.92). Approximation ratio of our
scheme goes up slightly, but the performance improvement over existing schemes is similar or larger. 
In Fig. 3, we present the average values of actual latency for broadcast algorithms as well as the height of BFS tree (i.e.,
lower bound). It varies both the number of nodes and the square size, so that the average number of neighbors is maintained
similar. Observe that the proposed algorithm consistently outperforms existing schemes by 1137 percent. D. Results for
AlltoAll Broadcast 
In Fig. 4, we present the average approximation ratio of our alltoall broadcast schemes (CDA and ICDA), MSB and
IGA that vary the number of nodes and the square size. Observe that the performance of CDA and ICDA in practice is
much better than the analytical bound (20 and 34). CDA performs well when the network size is small However, the
performance difference between CDA and MSB becomes smaller in larger Networks. 
CONCLUSION 
Thus an approximation algorithm for broadcasting in wireless networks was implemented. Our algorithm for ONETOALL
BROADCASTING gives a 12approximate Solution and the algorithms for ALLTOALL BROADCASTING give
approximation ratios of 20 and 34. But it is not enough for very large multihop networks, so in future it can be implemented
for very large multihop networks in efficient manner to reduce latency and collisionfree and to find the latency time in
wireless networks. 
Figures at a glance 




Figure 1 
Figure 2 
Figure 3 
Figure 4 


References 
 C. Ho, K. Obraczka, G. Tsudik, and K. Viswanath, “Flooding for Reliable Multicast in MultiHop Ad Hoc Networks,” Proc. Third Int’l Workshop Discrete and Algorithms Methods for Mobile Computing And Comm., pp. 6471, 1999.
 J. Jetcheva, Y. Hu, D. Maltz, and D. Johnson, “A Simple Protocol for Multicast and Broadcast in Mobile Ad Hoc Networks,” IETF Internet draft, July 2001.
 S.Y. Ni, Y.C. Tseng, Y.S. Chen, and J.P. Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” Proc. ACM/IEEE MobiCom, pp. 151162, 1999.
 R. Gandhi, A. Mishra, and S. Parthasarathy, “Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks,” IEEE/ACM Trans. Networking, vol. 16, no. 4, pp. 840851, Aug. 2008.
 W. Peng and X. Lu, “AHBP: An Efficient Broadcast Protocol for Mobile Adhoc Networks,” J. Science and Technology, vol. 16, pp. 114125, 2000.
 J. Sucec and I. Marsic, “An Efficient Distributed NetworkWide Broadcast Algorithm for Mobile Adhoc Networks,” technical report, Rutgers Univ., 2000.
