30-03-2011, 10:08 AM
presented by:
Shuhui Yangyand Jie Wuz
[attachment=11296]
Abstract
In this paper, we consider the issue of efficient broadcasting in mobile ad hoc networks(MANETs) using network coding and directional antennas. Network coding-based broadcastingfocuses on reducing the number of transmissions each forwarding node performs in the multiplesource/multiple message broadcast application, where each forwarding node combines some ofthe received messages for transmission. With the help of network coding, the total number oftransmissions can be reduced compared to broadcasting using the same forwarding nodes without coding. We exploit the usage of directional antennas to network coding-based broadcastingto further reduce energy consumption. A node equipped with directional antennas can dividethe omnidirectional transmission range into several sectors and turns some of them on for transmission. In the proposed scheme using a directional antenna, forwarding nodes selected locallyonly need to transmit broadcast messages, original or coded, to restricted sectors. We also studytwo extensions. The first extension applies network coding to both dynamic and static forwarding node selection approaches. In the second extension, we design two approaches for the single source/single message issue in the network coding-based broadcast application. Performanceanalysis via simulations on the proposed algorithms using a custom simulator and ns2 is presented
Introduction
Broadcasting is the most frequently used operation in mobile ad hoc networks (MANETs) for thedissemination of data and control messages in many applications. Usually, a network backbone isconstructed for efficient broadcasting to avoid the broadcast storm problem caused by simple blindflooding, where only selected nodes that form the virtual backbone, called forwarding nodes, forwarddata to the entire network.In MANETs, the forwarding node set for broadcast is usually selected in a localized manner, whereeach node determines its own status of forwarding or non-forwarding based on local information [31],or the status of a node is designated by its neighbors [16]. A smaller-sized forwarding node set isconsidered to be more efficient due to the reduced number of transmissions in the network, whichhelps to alleviate interference and also conserves energy. The connected dominating set (CDS) asa virtual backbone has been widely studied [21], where each node is either a forwarding node ora neighbor to a forwarding node in the set, and the set is connected. Finding a minimum CDS isNP-complete.In [13], Li et al. exploited network coding in the broadcast application. They applied codingmethods to deterministic forwarding node selection approaches to gain a reduction in the numberof transmissions, focusing on reducing the number of transmissions each forwarding node performs.Network coding [12] is defined as allowing intermediate nodes to process the incoming informationflows. When a forwarding node, chosen by a certain approach, needs to forward several messages toall of its neighbors while some neighbors already have some of the messages, this node can combinesome of the messages to reduce the number of forwardings, and each neighbor can still get everymessage via decoding.For instance, node c gets two messages from nodes a and b respectively. In order to let a and bhave each other’s message, c needs to forward both the messages as a traditional forwarding node.With network coding, c only needs to forward one coded message containing both original messagesthrough the XOR operation, and a and b can decode the message with the help of their own messages through the XOR operation. Note that the network coding works only when there are multiplemessages broadcast at the same time in the network.In [33], Yang, Wu, and Dai focused on reducing the total number of forwarding directions/sectorsof forwarding nodes. Using directional antennas, the omnidirectional transmission range of each2node can be divided into several sectors and the transmission can be performed only in selectedsectors. Therefore, by reducing the total number of transmission sectors of the forwarding nodes inthe network, the interference can be alleviated as well as the energy consumption.In this paper, we try to combine the advantages of both network coding and directional antennasto achieve efficiency in broadcasting. We analyze the performance of these two methods and designan algorithm — Efficient Broadcast using Network Coding and Directional Antennas (EBCD), whereeach node decides its forwarding status using only local information and limited piggybacked broadcast state information. Our proposed design does not simply mix the two existing methods. We takeadvantage of the effects of interaction in both methods in an effort to achieve even better performance.Additionally, we modify the existing directional antenna method to a dynamic mode. As shown inFigure 1 (a), there are four messages, A, B, C, and D generated from nodes a, b, c, and d, respectively.We assume that node e is selected for forwarding using a forwarding node selection method. Therefore, e needs to forward all four messages, costing 4 transmissions totally. In network coding-basedbroadcasts based on 2-hop neighborhood information, e can construct a neighbor reception table as in(b) to record the broadcast state information of the received messages. For instance, when a sends outmessage A, both e and b receive it. Therefore, b is a “covered” node of message A and there is a “1” inthe grid at line b, column A. Based on the table, e then codes these four messages into two combinedmessages to forward, P1 (= A C) and P2 (= B D) (is the XOR operation) using some networkcoding algorithms. Obviously, every other node can decode these two combined messages togetherwith the messages it already has in order to gain all four of the original messages. For instance, nodeb has message A, B, and C. When b receives P2, it can use P2 B to extract message D. a can useP1 A and P2 B to obtain C and D.With the help of directional antennas, the omnidirectional transmission range of e can be dividedinto K sectors (K is 4 in this example), as the dashed lines show in (a). Then e can restrict thetransmissions of the two combined messages in only some of the sectors, as shown in table ©. Forinstance, P1 only needs to be transmitted in sectors I, II, and IV . If we let the consumption of thetransmission of one message in one sector be the unit energy consumption, traditional broadcastingwhere e transmits all four messages omnidirectionally, costs 16. Broadcasting with network coding costs 8. The broadcast with network coding and directional antennas costs 6. Other than the forwarding nodes, the source nodes can also restrict the transmissions to selected sectors to further reduce the total energy consumption as long as the message can reach a forwarding node.
