This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts

for publication in the IEEE INFOCOM 2008 proceedings.

Efficient Broadcast in MANETs Using Network

Coding and Directional Antennas
Shuhui Yang Jie Wu and Mihaela Cardei
Department of Computer Science Department of Computer Science and Engineering
Rensselaer Polytechnic Institute Florida Atlantic University
Troy, NY 12180 Boca Raton, FL 33431

Abstract—In this paper, we consider the issue of efficient the number of transmissions, focusing on reducing the number
broadcasting in mobile ad hoc networks (MANETs) using net- of transmissions each forwarding node performs. Network
work coding and directional antennas. Network coding-based coding [5] is defined as allowing intermediate nodes to process
broadcasting focuses on reducing the number of transmissions
each forwarding node performs in the multiple source/multiple the incoming information flows. When a forwarding node,
message broadcast application, where each forwarding node decided by a certain approach, needs to forward several
combines some of the received messages for transmission. With messages to all of its neighbors while some neighbors already
the help of network coding, the total number of transmissions have some of the messages, this node can combine some of
can be reduced compared to broadcasting using the same for- the messages to reduce the number of forwardings, and each
warding nodes without coding. We exploit the usage of directional
antennas to network coding-based broadcasting to further reduce neighbor can still get every message via decoding.
energy consumption. A node equipped with directional antennas For instance, node c gets two messages from nodes a and b
can divide the omnidirectional transmission range into several respectively. In order to let a and b have each other’s message,
sectors and turns some of them on for transmission. In the c needs to forward both the messages as a traditional forward-
proposed scheme using a directional antenna, forwarding nodes ing node. With network coding, c only needs to forward one
selected locally only need to transmit broadcast messages, original
or coded, to restricted sectors. We also study two extensions. coded message containing both original messages through the
The first extension applies network coding to both dynamic XOR operation, and a and b can decode the message with the
and static forwarding node selection approaches. In the second help of their own messages through the XOR operation. Note
extension, we design two approaches for the single source/single that the network coding works only when there are multiple
message issue in the network coding-based broadcast application. messages broadcast at the same time in the network.
Performance analysis via simulations on the proposed algorithms
using a custom simulator is presented. In [18], Yang, Wu, and Dai focused on reducing the total
number of forwarding directions/sectors of forwarding nodes.
I. I NTRODUCTION Using directional antennas, the omnidirectional transmission
Broadcasting is the most frequently used operation in mo- range of each node can be divided into several sectors and the
bile ad hoc networks (MANETs) for the dissemination of data transmission can be performed only in selected sectors. There-
and control messages in many applications. Usually, a network fore, by reducing the total number of transmission sectors of
backbone is constructed for efficient broadcasting to avoid the forwarding nodes in the network, the interference can be
the broadcast storm problem caused by simple blind flooding, alleviated as well as the energy consumption.
where only selected nodes, called forwarding nodes, that form In this paper, we try to combine the efficiency of both
the virtual backbone, forward data to the entire network. network coding and directional antennas to achieve efficiency
In MANETs, the forwarding node set for broadcast is in broadcasting. We analyze the performance of these two
usually selected in a localized manner, where each node deter- methods and design an algorithm — Efficient Broadcast using
mines its own status of forwarding or non-forwarding based Network Coding and Directional Antennas (EBCD), where
on local information [16], or the status of a node is designated each node decides its forwarding status using only local infor-
by its neighbors [7]. A smaller-sized forwarding node set is mation and limited piggybacked broadcast state information.
considered to be more efficient due to the reduced number The proposed design is not simply the combination of the two
of transmissions in the network, which helps to alleviate existing methods. We take the advantage of the interactional
the interference and also conserves energy. The connected effects of them to achieve an even better performance. Addi-
dominating set (CDS) as a virtual backbone has been widely tionally, we modify the existing directional antenna method
studied [10], where each node is either a forwarding node or to a dynamic mode. As shown in Figure 1 (a), there are
a neighbor to a forwarding node in the set, and the set is four messages, A, B, C, and D generated from nodes a,
connected. Finding a minimum CDS is NP-complete. b, c, and d, respectively. We assume that node e is selected
In [6], Li et al. exploited network coding in the broadcast for forwarding using a forwarding node selection method.
application. They applied coding methods to deterministic Therefore, e needs to forward all four messages, costing
forwarding node selection approaches to gain a reduction in 4 transmissions totally. In network coding-based broadcasts,

978-1-4244-2026-1/08/$25.00 © 2008 IEEE 2171

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.

d A B C D P1 P2 application; the pipeline-based approach (PB) and the spread-

a II e I a 1 1 0 0
out approach (SO). We also discuss the detailed implemen-
111
000
000
111 b 1 1 1 0
I 1 1
000IV
111
III II 1 1 tation techniques in the proposed EBCD algorithm, such as
c 0 1 1 1
III 0 1 the timing issue and the neighborhood information discovery
d 0 0 1 1
c e 1 1 1 1
IV 1 0 issue.
b
The contributions of this paper are the following:
(a) (b) (c)
1) We present the advantages of the combination of the
network coding and directional antenna approaches for
Fig. 1. (a) A sample network, (b) neighbor reception table of node e, and efficient broadcast and develop the EBCD algorithm.
(c) transmission table of node e using coding and directional antennas.
2) We extend the EBCD algorithm to a static forwarding
node/edge selection version to study the performance
variation.
based on 2-hop neighborhood information, e can construct a 3) We propose two approaches for the single source with
neighbor reception table as in (b) to record the broadcast state single broadcast message application.
information of the received messages. For instance, when a 4) We discuss some implementation techniques in EBCD
sends out message A, not only e, but also b gets it. Therefore, and conduct performance analysis through simulations
b is a “covered” node of message A and there is a “1” in the on the proposed algorithms.
grid at line b, column A. Based on the table, e then codes
these four messages into two combined messages to forward, II. R ELATED W ORKS AND P RELIMINARIES
P1 (= A ⊕ C) and P2 (= B ⊕ D) (⊕ is the XOR operation)
A. Broadcast in MANETs
using some network coding algorithms. Obviously, every other
node can decode these two combined messages together with Both probabilistic [15] and deterministic [7], [13], [16]
the messages it already has in order to gain all four of the approaches have been proposed for efficient broadcast. Prob-
original messages. For instance, node b has message A, B, abilistic approaches use limited neighborhood information
and C. When b receives P2 , it can use P2 ⊕ B to extract (local information) and require relatively high broadcast redun-
message D. a can use P1 ⊕ A and P2 ⊕ B to obtain C and dancy to maintain an acceptable delivery ratio. Deterministic
D. approaches select a few forwarding nodes to achieve full
With the help of directional antennas, the omnidirectional delivery and most are localized, where each node determines
transmission range of e can be divided into K sectors (K is 4 its status (forwarding or non-forwarding) based on its h-hop
in this example), as the dashed lines show in (a). Then e can neighborhood information (for small values of h, such as 2
restrict the transmissions of the two combined messages in or 3). The decision of forwarding nodes can be made under
only some of the sectors, as shown in table (c). For instance, both static and dynamic local views. In the static approaches,
P1 only needs to be transmitted in sectors I, II, and IV . If we only topology information is considered, whereas in dynamic
let the consumption of the transmission of one message in one ones, broadcast state information of the neighborhood is also
sector be the unit energy consumption, traditional broadcasting piggybacked.
where e transmits all four messages omnidirectionally, costs The CDS concept can be applied for broadcasting. Wu
16. Broadcasting with network coding costs 8. The broadcast and Li [17] proposed the first localized solution for CDS
with network coding and directional antennas costs 6. Other constuction. Peng and Lu [8] presented a scalable broadcast
than the forwarding nodes, the source nodes can also restrict algorithm where the status of a forwarding node is computed
the transmissions to selected sectors to further reduce the on-the-fly. In [13], Stojmenovic et al. extended [17] to a
total energy consumption as long as the message can reach dynamic version. Sucec and Marsic [14] developed a dynamic
a forwarding node. approach without using a backoff delay. Lou and Wu [7]
Although the forwarding node/edge selection and the further devised a total/partial dominant pruning (TDP/PDP) method
network coding procedures are independent, we show that based on 2-hop topology and broadcast state information.
different underlying forwarding node selection approaches Wu and Dai [16] further proposed a generic CDS formation
affect the efficiency of network coding significantly. In EBCD, approach, which can be performed in both dynamic and static
we design the dynamic version of the underlying forwarding modes.
node/edge selection approach. We then use a static version
without piggybacked information for it to analyze the perfor- B. Network Coding
mance and tradeoffs. We find out that the energy conservation Network coding [1], [5] can be used to allow the interme-
of the dynamic and static versions are comparable, although diate nodes to combine packets before forwarding. Therefore,
the dynamic one is slightly better. However, since the static network coding can be used for efficient broadcasting by
version has less overhead, it is more practical. Also, the reducing the total number of transmissions. In [3], Fragouli
network coding-based broadcast approach [6] works only et al. quantified the energy savings that network coding has
when there are multiple sources with multiple messages in the potential to offer in broadcasting. They also proposed an
the network. We propose two approaches as another extension implementable method for performing the network coding,
to EBCD to deal with the single source with single message addressing some practical issues such as setting the forwarding

2172
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.

factor and managing generations. In [9], a proactive com- as a directed graph. Then in a broadcast initiated from any
pensation packet is periodically broadcast, constructed from source node, the source uses ominidirectional transmission (or
unforwarded messages using network coding to improve the directional transmission if it detects a forwarding node in that
delivery ratio of the probabilistic broadcast approach. direction) to send the message to a neighboring forwarding
In [6], Li et al. applied network coding to a determin- node. Then forwarding nodes forward the message towards
istic broadcast approach called partial dominating pruning only their corresponding forwarding edges, and the entire
(PDP) [7] in a multiple-source broadcast application. They network gets the message. The DCDS is a directional network
proved that using only XOR operation, the coding algorithm is backbone assuming that K is infinite, and each outgoing edge
NP-complete and developed a greedy XOR-based approach for is a transmission sector. When K is finite, the sectors that
simplicity. The Reed-Solomon code was exploited to design contain selected forwarding edges are simply switched on for
an optimal Reed-Solomon code-based algorithm. transmission to get a directional network backbone. Note that
when K is 1, the DCDS problem turns into the CDS problem.
C. Directional Antennas
A minimum DCDS problem is to find a DCDS with the
The most popular directional antenna model is ideally least forwarding edges which is proved to be NP-complete.
sectorized, as in [4], where the effective transmission range of If the energy consumption of transmission in any direction is
each node is equally divided into K non-overlapping sectors, fixed, reducing the number of forwarding edges guarantees the
where one or more such sectors can be switched on for smallest energy consumption in the application of broadcasting
transmission or reception. The channel capacity when using using directional antennas.
directional antennas can be improved, and the interference can The node/edge coverage condition proposed in [18] con-
be reduced. Some probabilistic approaches for broadcasting structs a DCDS for a given network locally at each node
using directional antennas are proposed in [4], [11], [12]. in a static manner. The constructed DCDS is for any source
In [2], Dai and Wu proposed a localized broadcast protocol node in the network. After the exchange of “Hello” messages,
using directional antennas, which is source-based. In [18], each node makes a decision based on only local topology
Yang, Wu, and Dai put forward the directional network back- information in the initialization phase before the broadcast
bone for efficient broadcasting using the directional antenna application starts. Here, we extend this method to a dynamic
model in a static manner where the backbone is suitable for version, where each node makes a decision based not only
any source node in the network. They designed the concept of on topology information but also broadcast state information
a directional connected dominating set (DCDS) for the con- piggybacked in received broadcast messages. It decides its
struction of a directional network backbone. DCDS extended forwarding status and corresponding forwarding edges for each
the CDS approach for broadcast with the help of directional received broadcast message.
antennas. The minimum DCDS problem is proved to be NP- In our proposed dynamic node/edge coverage condition,
complete. Using DCDS, not only forwarding nodes but also each broadcast message piggybacks with it the information
forwarding edges of each forwarding node are designated. of its q most-recently visited nodes (q is a small number such
The total energy consumption is reduced, as well as the as 2 or 3). A visited node for a message is a node that has
interference. They developed the node and edge coverage forwarded the message. Correspondingly, a visited edge for
condition for the DCDS problem. All of the above schemes a message is an edge that has forwarded the message. Then,
assume an omnidirectional reception mode. when a node applies the coverage condition to determine its
III. B ROADCAST WITH N ETWORK C ODING AND status for a received message, it considers the information of
D IRECTIONAL A NTENNAS visited nodes/edges of this message as well as local topology
information. The dynamic version of the node and edge cov-
In this section, we first extend the approach developed erage conditions resemble the static ones [18] except that the
in [18] to construct the directional connected dominating set node and edge priorities are updated based on the piggybacked
(DCDS) to a dynamic version, where the constructed DCDS broadcast state information. Note that the updated new priority
is source-based. We then combine the network coding with is only valid for the corresponding message. Therefore, a node
the dynamic DCDS to develop the EBCD. may have a different status (visited or not, forwarding or
A. Dynamic Directional Connected Dominating Set (DDCDS) not) and priorities for different messages. In the following,
an unmarked status represents a non-forwarding status. A
In [18], the concept of using a directional network backbone
dominating neighbor means that there is an incoming edge
for efficient broadcast in conjunction with directional antennas
from that neighbor. A absorbant neighbor means that there is
was proposed. The omnidirectional transmission range of each
an outgoing edge to that neighbor. Note that each node v has
node is divided into K sectors and each forwarding node
a priority p(v) and such a priority is totally ordered within
only needs to switch on several sectors for transmission
its h-hop neighborhood, which could be the node ID, node
while the entire network gets the broadcast message. The
degree, or energy level based on different applications.
directional connected dominating set (DCDS) is proposed for
the construction of a directional network backbone, where Dynamic Node Coverage Condition. Node v is unmarked
each node determines locally not only its status of forwarding if, for any two dominating and absorbant neighbors, u and
or non-forwarding, but also its forwarding outgoing edges if w, a directed replacement path exists connecting u to w such
it is a forwarding node. Note that the network is modeled that (1) each intermediate node on the replacement path has

2173
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.

t x s s
x
u
c c
111
000 f
b11
00 f
b11
00
00
11 000
111 00
11 111
000
000
111
11
00 000
111 11
00 000
111
u
w 00
11 000
111 00
11

w d e d e
v
v
(a) (b) (a) (b)

Fig. 2. Directed replacement paths in (a) node coverage, and (b) edge Fig. 3. (a) Forward nodes, (b) forwarding nodes and forwarding edges.
coverage with visited nodes.

exists, and s is a visited node and (s → b) is a visited edge.

a higher priority than v (including visited nodes), and (2) u
Therefore, the priorities of edges (b → s) and (s → c) are
has a higher priority than v if there is no intermediate node.
both higher than that of (b → c). The same is true for edge
(c → b). Then if K is finite, only the sectors that contain the
Edge Priority Assignment. For each edge (v → w), the
bold arrows need to be switched on for transmission, much
priority of this edge is P (v → w) = (P (v), P (w)).
like the grey sectors in (b).
The priority of an edge is a tuple based on the lexigraphic
order. The first element is the priority of the start node of B. Efficient Broadcasting Using Network Coding and Direc-
this edge and the second one is the priority of the end node. tional Antennas (EBCD)
Therefore, there is a total order for all the edges. For example, In this subsection, we combine the network coding and
P (x → y) > P (w → v), if and only if, (P (x) > P (w)) or directional antenna approaches into the broadcast application,
(P (x) = P (w) and P (y) > P (v)). exploiting the advantages of both of them.
Dynamic Edge Coverage Condition. Edge (v → w) is Algorithm 1 describes EBCD executed on a node. Before
unmarked if a directed replacement path exists connecting v the broadcast starts, each node exchanges “Hello” information
to w via several intermediate edges with higher priorities than with neighbors for h rounds to get the h-hop local topology
(v → w) or visited edges. information. Upon the arrival of the first message, a timer
is setup and the piggybacked information in each received
As shown in Figure 2, v is the current node and black nodes message is recorded to update the node priorities. When
are visited ones. Assume the priority is based on the alphabetic the timer expires, for each received message, the node/edge
order, i.e., P (a) > P (b). (a) shows two types of directed coverage conditions are applied based on the topology and
replacement paths from u to w using the node coverage broadcast state information (new priorities), and forwarding
condition. When u is directly connected to w, P (u) > P (v) is status and edges of the node are determined. We use the
necessary. Otherwise, when there are intermediate nodes t and example in Figure 4 to illustrate the procedure. This is the
x, then P (t) > P (v) and P (x) > P (v) since x is visited. (b) same example as in Figure 1. (a) is the result of DDCDS after
shows the directed replacement path for edge (v → w). In this step 4 of Algorithm 1. Node e is the forwarding node for
case, both the intermediate edges ((v → u) and (u → x)) have messages A, B, C, and D from nodes a, b, c, and d based
higher priorities than the edge (v → w). Since edge (x → w) on the dynamic node coverage condition. Edge (e → a) is a
is visited, the edge (v → w) can be unmarked. The difference forwarding edge for messages C and D. Edge (e → b) is a
between dynamic and static node/edge coverage conditions is forwarding edge for message D. Edge (e → c) is a forwarding
that a visited node/edge has a higher priority node/edge. Note edge for message A. Edge (e → d) is a forwarding edge for
that the dynamic node/edge coverage conditions need h-hop message A and B.
information which means h-hop local topology information In step 5, when the timer expires, node e circumgyrates
and q-hop piggybacked visited node/edge information in each its directional antennas to let the edge of a sector align to
received message. For example, as in Figure 1 (a), if h = 2, each forwarding edge. There are at most f layouts when the
node a knows all the edges in the network except the edge number of selected forwarding edges is f . In each sector of
between nodes c and d. each layout, network coding is applied to determine the final
Theorem 1: Given a directed graph G = (V, E), V
and E
transmissions. The layout with the fewest total transmissions is
generated by the dynamic node and edge coverage conditions then selected for use. The node then executes the forwarding.
in a broadcast guarantee the full delivery. In the algorithm, we assume that steps 4, 5, and 6 can be
The proof of Theorem 1 is in the Appendix. The example completed before the arrival of the next message.
in Figure 3 shows a source-based CDS (a) in shaded nodes In EBCD, network coding is applied in each sector of a lay-
(s is the source), (b) is the result after applying the dynamic out instead of the entire node as in [6]. We use the XOR-based
node/edge coverage condition. Nodes b and c are also forward- algorithm from [6]. Assuming m1 , m2 , . . . , ml are messages
ing nodes. b selects edge (b → d) as forwarding edge and c received in order in this sector. P1 , P2 , . . . , Pt are the final
selects edges (c → e) and (c → f ). The edge (b → c) can be forwarded messages (original or coded). P1 = m1 ⊕. . .⊕mi1 ,
unmarked because a replacement path connecting b to c via s P2 = mi1 +1 ⊕ . . . ⊕ mi2 , . . ., Pt = mit +1 ⊕ . . . ⊕ ml , where

2174
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.

Algorithm 1 EBCD algorithm at node v. d d

P1 P 2
a C111 a
Before broadcast: 000
D e
111A B
000 11e
00
000
111 00
11
00
11
1. Exchange “Hello” messages to update local topology. 000
111
A
Upon reception of the first message (before the timer setup): D
2. Setup the timer.
c c
3. Update neighborhood node priorities based on each received b b
message. (a) (b)
d
4. When timer expires, apply dynamic node/edge coverage d
conditions for each message. P1 P 2
a C eA
a 111
000
e
000
111
5. If v is a forwarding node for some messages, 111B
000 000
111
000
111
D
000
111 000
111
(1) align the edge of a sector to each forwarding edge, P3
(2) determine coded messages in each sector using coding,
(3) select the position with the fewest total transmissions. c b
c
b
6. Forward coded messages.
(d)
(c)
d d

P1P 2 a
11
00
00
11
P1 P 2 e
a 11
00
e
00
11 00
11
P 1P 211
00 P P2
each neighbor can decode from P1 to Pt to get any missing
message from m1 to ml . A greedy approach can be used. For
00
11
D 11
00A 00
11 00 1
11
P3

the received messages in a queue, the algorithm tries to have

c
the maximum number of messages starting from m1 to create b
c b
P1 , then to create P2 and so on. For example, in Figure 4 (f)
(b), assuming that the broadcast messages arrive in the order (e)
of A, C, B, and D at node e. P1 is A at first, then e tries
to make P1 = A ⊕ C. Node a needs message C and nodes Fig. 4. (a) DDCDS, (b) coding, (c) and (d) K = 2, (e) and (f) K = 4.
d and c need message A. With P1 , all of them can decode.
Therefore P1 = A ⊕ C is a correct coding. Then e can try
P1 = A⊕C ⊕B. Since node d needs message B, and it cannot The source nodes in the network can simply use omnidi-
decode P1 to get B, this is not a correct coding. P1 remains rectional transmission to send out the broadcast messages. In
as A ⊕ C. Using the same procedure, we can get P2 = B ⊕ D. order to further reduce the total energy consumption, source
Figure 4 (b) is the result using only network coding, where nodes can only switch on sectors in which there are neighbors
e is the forwarding node and forwards the combined message for transmission. In this case, the message can arrive at at
P1 (= A ⊕ C) and P2 (= B ⊕ D) omnidirectionally. (c) is least one forwarding node as well as other non-forwarding
one layout of EBCD using K = 2. Then e needs to transmit neighbors, which helps with the potential network coding
C and D in the left sector and A and B in the right sector. conducted later on. As shown in Figure 4 (f), source nodes a,
(d) is another layout for K = 2, where e transmits P1 and b, c, and d select some sectors to switch on for transmission,
P2 to the upper sector and P3 (= A ⊕ D) to the lower sector. shown in the light grey sectors.
(e) and (f) show the case where K is 4 with different layouts.
IV. E XTENSIONS OF EBCD
If we assume that the transmission of one message in a 90◦
sector costs one unit of energy, the energy consumption in the A. Static vs. Dynamic Forward Node Selection
figures from (b) to (f) are 8, 8, 6, 6, and 5. We can see that As mentioned above, in [6], Li et al. applied network
the combination of network coding and directional antennas coding to a dynamic forwarding node selection approach,
can improve broadcasting performance significantly in terms the PDP-based approach, and stated that the coding can be
of energy consumption. Note that the forwarding of node e directly applied to other localized deterministic approaches
without network coding or directional antennas costs 16. for broadcasting. The previously proposed EBCD also uses
The entire procedure can also be illustrated using Figure 5 a dynamic forwarding status approach. Here, we extend the
(a), where m1 to m6 are received messages and D1 to D6 are proposed EBCD to a static forwarding node selection approach
the corresponding forwarding nodes/edges decisions for them to analyze their overall performance.
based on topology and priority information. U means to update In the static version of EBCD, we apply the coding to the
the priority information based on the piggybacked information static forwarding node/edge selection, the node/edge coverage
in the received message and Dc is the final transmission conditions in [18], as shown in Algorithm 2. We will compare
decision for several received messages using network coding in the performance and tradeoffs of these two algorithms in the
a valid timer. Note that the duplicated reception of a processed simulation section. As in Algorithm 2, in the initialization
message is simply discarded such as m5 received after it has phase before the broadcast starts, local information is col-
been processed and forwarded. As shown in the figure, the lected via the exchange of “Hello” messages. Then the node
arrival of m5 after timer 2 expires will not intrigue a new determines its forwarding status. This status is for all of the
timer or a new updating during the timer 3 period. following received messages. Then a timer is setup when the

2175
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.

m1 m2 m1 m3 m3 m4 m5 m5 m6 m5
Algorithm 2 Static EBCD algorithm at node v.
time Before broadcast:
Hello timer 1 timer 2 timer 3 1. Step 1 of Algorithm 1.
U U U U U U U 2. Determine forwarding status. Exit if it is non-forwarding.
D1/D2/Dc D3/D4/D5/Dc D6/Dc Upon reception of the first message (before setup the timer):
(a) Dynamic EBCD 3. Step 2 of Algorithm 1.
m1 m2 m1 m3 m3 m4 m5 m5 m6 m5
4. When timer expires, follow Step 5 (1), (2), and (3) of
Algorithm 1.
time 5. Step 6 of Algorithm 1.
Hello timer 1 timer 2 timer 3

Ds Dc Dc Dc
(b) Static EBCD source node divides the message into k segments and sends
each segment as a single broadcast message, and broadcasts
Fig. 5. Illustration of execution procedure of dynamic/static EBCD. them one-by-one in the pipelined manner. In this way, the
single source/single message problem turns into single source
with multiple message broadcast. In the area near the source
first message arrives. When the timer expires, network coding node, the effect of network coding is not significant since all
is applied in each sector of each layout, and the best one is the segments tend to come from one direction. However, in
selected for use. the farther area, the effect is expected to be significant. As
The entire procedure is illustrated in Figure 5 (b). After shown in Figure 6 (a), s divides the broadcast message into k
the exchange of “Hello” messages, Ds determines the status segments and sends them out via k broadcasting. Therefore,
of the node and also the selected forwarding edges if it is a the neighbors of source node s get the first broadcast message
forwarding node for all the following received messages. Then S1 , then the second one S2 in order from s.
upon the reception of the first message, a timer is setup. When 2) Spread-Out Approach (SO): In order to enhance the
the timer expires, coding is applied to all received messages effect of network coding in the single source/multiple message
to determine the final coded messages for transmission. broadcast using the message segmentation method, we can
The size of the forwarding node set selected using a further apply the message spread method to first spread the
dynamic manner is smaller than or equal to the one by a static segments out into the entire network. After the source node
manner, since in the former one the information of visited divides the outgoing message into k segments, it uses random
nodes helps to increase the probability of the node being an walk to spread the k − 1 of these segments. Some kind of
non-forwarding node. However, redundant transmissions by TTL control can be used to make sure the segments randomly
the extra forwarding nodes in the static manner may help scatter out into the network. Upon arriving at a destination, a
to increase the potential network coding in the later phase segment is broadcast by the destination node. The source itself
and hence the overall performance, which will be verified via keeps a segment for later broadcast. As shown in Figure 6 (b),
simulation. The obvious advantage of the static EBCD is less the k−1 segments are spread in the entire network. In this way,
overhead. The broadcast messages do not need to piggyback the application turns into the multiple source with multiple
the broadcast state information. Also, as shown in Figure 5 messages broadcast. Although the unicast in the preprocessing
(b), fewer forwarding nodes/edges decisions need to be made. phase costs extra overhead, the transmission reduction earned
from network coding in the entire network is expected to be
B. Single Source/Single Message Broadcast more significant. Note that the nodes on the unicast routes can
As mentioned above, broadcasting using the network coding mark themselves as visited nodes for the bypassing segments,
method [6] is designed for the application of multiple sources which helps to potentially reduce transmission.
with multiple broadcast messages, where a forwarding node
has the potential of combining some of the messages to reduce V. I MPLEMENTATION I SSUES
the number of transmissions. In the application of a single In this section, we discuss some implementation techniques
source, only when the rate of the generation of messages is in the above proposed algorithms.
large enough, the network coding may work in nodes relatively
far away from the source node. A. Neighborhood and Piggybacked Information Collection
We design two approaches for the single source/single Note that no GPS assistance is necessary in the proposed
message broadcast issue. We assume a single source in the algorithm. In Algorithm 1, each node sends out “Hello”
broadcast and the rate of the generation of messages is large messages K times to the K directions and accomplishes
enough that it can be viewed as single message application. the directional neighborhood discovery. In this case, after h
The basic idea is to divide the single message into several seg- rounds of the message exchange, each node knows its h-
ments and treat each segment as a single broadcast message. hop neighborhood information, which includes both neighbors
1) Pipeline-Based Approach (PB): When there is only one and in which sectors are these neighbors. According to this
source node in the network broadcasting one message, the information, each node can create the neighbor reception table.

2176
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.

6000 4500
EBCD EBCD
S1 Coding 4000 Coding
S2 S1 5000 CDS CDS

Number of Transmissions

Number of Transmissions
S 3500
4000
Sk S3 S 3000

3000 2500
S2 S1 2000
2000
1500
S2 S1 1000
1000

Sk 0
20 30 40 50 60 70 80 90 100
500
20 30 40 50 60 70 80 90 100
Number of Nodes Number of Nodes

(a) Dense network (d = 18) (b) Sparse network (d = 6)

(a) Pipeline-based approach (b) Spread-out approach
Fig. 7. Comparison of EBCD, Coding, and CDS in number of transmissions.
Fig. 6. Single source/single message broadcast.

of the two approaches for the single source/single message

After a node determines its status together with the forward- broadcast application is evaluated, the pipeline-based approach
ing edges, it piggybacks this information in the broadcast mes- (PB) and the spread-out approach (SO).
sage as part of the q most recently visited node information.
A. Simulation Environment
The node that receives this broadcast message can extract the
“visited nodes/edges” information from it. The simulations are conducted on a custom simulator. In
the simulation, n nodes are randomly placed in a restricted
B. Timer in EBCD 100 × 100 area. The tunable parameters in the simulation are
A timer is set for each node to collect several broadcast as follows. (1) The number of nodes n. We vary the number of
messages. In the static version of EBCD, it helps with the deployed nodes from 20 to 100 to check the scalability of the
potential network coding. In the dynamic version, it also helps algorithms. (2) The average node degree d which represents
to collect more broadcast state information piggybacked by the density of the network. We use 6 and 18 as the values
these messages to determine the status of the node. The timer of d to generate sparse and dense networks. (3) The number
selection presents the performance tradeoff between energy of sectors of the antenna pattern K. We use 4 and 6 as the
consumption and delay. When the timer is set to 0, the effect values of K. (4) The number of broadcast sessions b, i.e.,
of network coding almost reduces to 0. When the timer is large the number of generated broadcasting messages. b has a fixed
enough to counteract the difference of initial time among the value of 20 in the simulation. Therefore, when n is different,
broadcast messages in the network, the network coding can be we can simulate various data loads in the network. The source
utilized thoroughly. After the forwarding, the timer is reset for nodes are randomly selected. (5) The number of segments k
the next session. The value of the timer can be set in both a in the PB and SO extensions. k is 10 and 20 in the network.
proactive and a reactive way. In the former method, the timer We do not consider node mobility and signal interference in
of a node can be set based on the number of neighbors of this the following simulations.
node and the diameter of the network. In the latter one, a node The following metrics are compared: (1) the number of
can adjust the value of the timer on-the-fly according to the transmissions in the application. We assume that the transmis-
message arrival rate at this node. sion of a message (original or coded) following a transmission
edge is one transmission, and (2) the average energy consump-
VI. S IMULATION tion for a broadcast message. We assume that one transmission
In this section, we evaluate the performance of the proposed (of a original broadcast message or a coded message) in each
EBCD algorithm, as result of the average of 100 simulation sector consumes one unit of energy.
trials, by comparing the total energy consumption in terms
of the number of message transmissions in the network and B. Simulation Results
also the size of sectors that the message was transmitted. We Figure 7 is the comparison of EBCD, Coding, and CDS
compare EBCD with two algorithms. (1) the algorithm without in the number of transmissions in both dense and sparse
network coding or directional antennas (CDS). We simply call networks. (a) is the dense network where the average node
it algorithm CDS since the forwarding node set selected by degree is 18. We can see that Coding can reduce the number
this method is a source-based CDS, which means together of message transmissions, and the reduction rate is around 1.2.
with the source node, the forwarding node set forms a CDS EBCD can further reduce it significantly. When the number of
for the network. We use a dynamic node coverage condition as nodes increases, the number of transmissions in EBCD tends
used in our EBCD. (2) the algorithm with network coding but to be stable. (b) is when the average node degree is 6. EBCD
without directional antennas (Coding). This is the approach can still reduce the number of transmissions compared with
proposed in [6], but in order to make a fair comparison, CDS or Coding. But the reduction rate is lower than that in
the underlying forwarding node selection approach we use in the dense network.
Coding is also the dynamic node coverage condition. We also Figure 8 is the comparison of EBCD, Coding, and CDS
compare EBCD with the proposed static EBCD (S-EBCD) in terms of energy consumption when K is 4 and 6. (a)
to check the performance variation. Finally, the performance and (b) are in dense networks. We can see that EBCD can

2177
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.

1400 2000 50 20
EBCD EBCD EBCD EBCD
Coding 1800 Coding 45 S-EBCD 18 S-EBCD

Number of Forwording Nodes

Number of Forwording Nodes

1200 CDS CDS
1600 40 16
Number of Sectors

Number of Sectors
1000 1400
35 14
800 1200
30 12
1000
600 25 10
800
20 8
400 600
400 15 6
200
200 10 4
0 0 5 2
20 30 40 50 60 70 80 90 100 20 30 40 50 60 70 80 90 100 20 30 40 50 60 70 80 90 100 20 30 40 50 60 70 80 90 100
Number of Nodes Number of Nodes Number of Nodes Number of Nodes

(a) Dense network (K = 4) (b) Dense network (K = 6) (a) Forwarding nodes (d = 18) (b) Forwarding nodes (d = 6)
3000 4500 1800 1800
EBCD EBCD EBCD EBCD
Coding 4000 Coding S-EBCD S-EBCD
2500 CDS CDS 1600 1600

Number of Transmissions

Number of Transmissions
3500
Number of Sectors

Number of Sectors
1400
2000 1400
3000
1200
1500 2500 1200
1000
2000
1000 1000
800
1500
500 600 800
1000

0 500 400 600

20 30 40 50 60 70 80 90 100 20 30 40 50 60 70 80 90 100 20 30 40 50 60 70 80 90 100 20 30 40 50 60 70 80 90 100
Number of Nodes Number of Nodes Number of Nodes Number of Nodes

(c) Sparse network (K = 4) (d) Sparse network (K = 6) (c) Number of transmissions (d = 18) (d) Number of transmissions (d = 6)

Fig. 8. Comparison of EBCD, Coding, and CDS in energy consumption. Fig. 9. Comparison of EBCD and S-EBCD.

further reduce the number of switched on sectors compared 10, SO is better than PB. When k is 20, PB is even better
with CDS and Coding in which all sectors of a forwarding than SO. This is because the initial phase of SO costs a lot
node need to be switched on for transmission. When K is of overhead in the case of larger k and smaller transmission
larger, the reduction rate of EBCD over CDS and Coding is range, which leads to more hops to spread out the segments.
more significant since a larger forwarding area can be pruned. The simulation results can be summarized as follows.
(c) and (d) are in the sparse networks. EBCD also reduces the 1) EBCD has significant performance improvement in
number of switched on sectors significantly. The larger the terms of the number of transmissions compared with
value of K, the larger the reduction rate. CDS and Coding, especially in relatively dense net-
Figure 9 is the comparison of EBCD and S-EBCD in terms works.
of the number of forwarding nodes and transmissions in both 2) EBCD has better performance than CDS and Coding
dense and sparse networks. We can see that although the in terms of the number of switched on sectors which
number of forwarding nodes selected in the static method corresponds to the energy consumption. The larger the
should be larger than that in the dynamic one, as shown value of K, the larger the reduction rate of EBCD over
in (a) and (b), the final numbers of transmissions in EBCD the other two methods.
and S-EBCD are very close, especially when the network is 3) S-EBCD has very close performance to EBCD, espe-
relatively dense. This is because more forwarding nodes to cially when the network is relatively dense. Therefore,
forward increases the probability of network coding, which due to its other advantage, such as less overhead, S-
makes up for the larger forwarding node set. The forwarding EBCD is another option.
node set of S-EBCD is around 1.3 times larger than that of 4) SO has better performance than PB when the network is
EBCD while the final number of transmissions is 1.03 times relatively dense and the number of segments a message
higher. The advantage of S-EBCD is that it only calculates is divided into is small. When in sparse networks with
the status of each node once for any broadcast message from large k, PB even has a better performance than SO.
any source. It is also unnecessary to piggyback the broadcast
state information. Therefore, if the network is dense, S-EBCD VII. C ONCLUSIONS
is preferred since the overhead of it is smaller while the Network coding has been exploited for efficient broadcast-
performance is comparative. ing to further reduce the number of transmissions in the mul-
Figure 10 shows the performance evaluations of the two tiple source broadcast application. In this paper, we combine
extensions of EBCD, PB and SO with different segment the network coding-based broadcast approach with broadcast-
numbers k = 10, 20. We can see that in (a) when the network ing using directional antennas for a more efficient broadcast
is dense, which means the transmission range is larger, SO has strategy, developing efficient broadcasting using network cod-
better performance than PB. Smaller k makes the advantage ing and directional antenna algorithm (EBCD). We extend
of SO over PB more significant. When k is 20, SO is very existing broadcasting using the directional antenna approach
close to PB. Because the number of transmissions is larger to a dynamic mode. Although the coding-based approach
with larger number of segments in the initial phase of SO. In is independent of the underlying forwarding node selection
(b), the results in the sparse network are shown. When k is procedure, we show that different forwarding node selections

2178
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.

3500
PB(k=10)
3000
PB(k=10)
W
SO(k=10) 2800 SO(k=10)
3000 PB(k=20) 2600 PB(k=20)
Number of Transmissions

Number of Transmissions
SO(k=20)
2400
SO(k=20) u
2500
2200
2000
2000
1800
1600
1500
1400 s f u d
1000 1200
1000 u
500 800
20 30 40 50 60 70 80 90 100 20 30 40 50 60 70 80 90 100
Number of Nodes Number of Nodes

(a) Dense network (d = 18) (b) Sparse network (d = 6)

Fig. 11. Proof of dynamic node/edge coverage conditions.
Fig. 10. Comparison of PB and SO in number of transmissions.

affect the overall performance significantly. We also discuss [14] J. Sucec and I. Marsic. An efficient distributed network-wide broadcast
algorithm for mobile ad hoc networks. In CAIP Technical Report 248,
the single source/single message application and design two 2000.
approaches as the extension of the proposed algorithm for [15] Y. C. Tseng, S. Y. Ni, Y. S. Chen, and J. P. Sheu. The broadcast storm
it. Performance analysis is conducted through simulations. problem in a mobile ad hoc network. Wireless Networks, (2-3):153C167,
2002.
The proposed EBCD approach has better performance than [16] J. Wu and F. Dai. A generic distributed broadcast scheme in ad hoc
traditional CDS-based broadcast and the existing network wireless networks. IEEE Transactions on Computers, (10):1343–1354,
coding-based broadcast in terms of energy consumption. Also, 2004.
[17] J. Wu and H. Li. On calculating connected dominating sets for efficient
the static version of EBCD has comparative performance in routing in ad hoc wireless networks. In Proc. of ACM DIALM, 1999.
energy conservation with smaller overhead. In the future, we [18] S. Yang, J. Wu, and F. Dai. Efficient backbone construction methods in
will improve the robustness for mobility and MAC layer MANETs using directional antennas. In Proc. of IEEE ICDCS, 2007.
interference of the proposed approaches and perform more VIII. A PPENDIX
comprehensive simulation considering a mobile environment.
Proof of Theorem 1. If we can prove that, given source
ACKNOWLEDGEMENT node s, for any node d in the network, there is a path with
This work was supported in part by NSF grants CCR all intermediate nodes and edges designated to forward, we
0329741, CNS 0422762, CNS 0434533, CNS 0531410, CCF prove that a full delivery is achieved. We assume that all of
0545488, and CNS 0626240. Email: [email protected]. d’s neighbors form a ring area as an “outer rim” of node d, like
the gray area W in Figure 11. Note that W is not empty. We
R EFERENCES
assume that node u is of the highest priority in area W . If we
[1] R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network information can prove that either u is a forwarding node and (u → d) is a
flow. IEEE Transactions on Information Theory, (4):1204–1216, 2000.
[2] F. Dai and J. Wu. Efficient broadcasting in ad hoc wireless networks us- forwarding edge, or one of d’s neighbors is a visited node and
ing directional antennas. IEEE Transactions on Parallel and Distributed it forwards the message to d, we contradict the assumption that
Systems, (4):1–13, 2006. d cannot be reached from s. We make the two assumptions
[3] C. Fragouli, J. Widmer, and J.-Y L. Boudec. A network coding approach
to energy efficient broadcasting: from theory to practice. In Proc. of that either u is not a forwarding node or u is a forwarding
IEEE INFOCOM, 2006. node but edge (u → d) is not a forwarding edge. We find
[4] C. Hu, Y. Hong, and J. Hou. On mitigating the broadcast storm problem contradictions for these two cases.
with directional antennas. In Proc. of IEEE ICC, 2003.
[5] S. Katti, D. Katabi, W. Hu, H. Rahul, and M. Medard. The importance of Case 1: u is not a forwarding node. Therefore, for a neighbor
being opportunistic: Practical network coding for wireless environments. f of u, according to the dynamic node coverage condition,
In Proc. of ACM SIGCOMM, 2006. either (a) there is a replacement path connecting f to d with at
[6] L. Li, R. Ramjee, M. Buddhikot, and S. Miller. Network coding-based
broadcast in mobile ad hoc networks. In Proc. of IEEE INFOCOM, least one intermediate node on it, u
, or (b) f directly connects
2007. to d, and the priority of f is higher than that of u. u
cannot
[7] W. Lou and J. Wu. On reducing broadcast redundancy in ad hoc wireless have a higher priority than u since u is the neighbor of d with
networks. IEEE Transactions on Mobile Computing, (2):111–122, 2002.
[8] W. Peng and X. Lu. On the reduction of broadcast redundancy in mobile the highest priority. If u
is a visited node, d can be covered
ad hoc networks. In Proc. of ACM MobiHoc, 2000. by u. For b, if f is also neighbor of d, it cannot have higher
[9] S. Pleisch, M. Balakrishnan, K. Birman, and R. Renesse. MISTRAL: priority than u.
Efficient flooding in mobile ad-hoc networks. In Proc. of ACM MobiHoc,
2006. Case 2: u is a forwarding node but edge (u → d) is not a
[10] A. Qayyum, L. Viennot, and A. Laouiti. Multipoint relaying for flooding forwarding edge (an “×” is on the edge). A path connecting u
broadcast message in mobile wireless networks. In Proc. of 35th Hawaii to d must exist, with all the edges with higher priorities than
Int’l Conf. on System Sciences (HICSS-35), 2002.
[11] C. C. Shen, Z. Huang, and C. Jaikaeo. Directional broadcast for ad (u → d) or visited. Since u is the highest priority node, u

on
hoc networks with percolation theory, Technical report, Computer and the path cannot be higher and has to be a visited node with a
Information Sciences, University of Delaware. 2004. forwarding outgoing edge connecting to d. In that case, d can
[12] D. Simplot-Ryl, J. Cartigny, and I. Stojmenovic. An adaptive localized
scheme for energy efficient broadcasting in ad hoc networks with be covered.
directional antennas. In Proc. of 9th IFIP PWC, 2004. All of the contradictions above show that d can be reached
[13] I. Stojmenovic, M. Seddigh, and J. Zunic. Dominating sets and neighbor from the source node s. 2
elimination based broadcasting algorithms in wireless networks. IEEE
Transactions on Parallel and Distributed Systems, (1):14C25, 2002.

2179