Broadcasting in Moblie Ad Hoc Networks
Sang‐Woo Lee, Chae-Woo Lee · InTech eBooks · 2011
Mobile ad hoc networks (MANETs) are self-organizing and the constituent mobile nodes communicate with each other as autonomous hosts in the absence of a fixed infrastructure.Recently, MANETs are deployed to places where the network is required to be promptly established such as military operations and disaster relief.However, the mobile nodes merely operate with limited resources such as processing, communication, and energy.The nodes further have the characteristic of high mobility.Thus, MANET has the properties of frequently route breakage and unpredictable topology changes.Clearly, these properties make the transmission methods widely used in fixed infrastructures inappropriate for MANET.Broadcasting is an alternative which is a one-toall transmission method, namely a packet or a message generated by a node, called the source, is sent to all other nodes in the network.Moreover, broadcasting is an important operation in applications performing route discovery (Johnson & Maltz, 1996;Park & Corson, 1997; Pearlman & Haas, 1999;Perkins & Royer, 1999), updating the network knowledge, or sending an alarm signal.However, it seems greedy and excessive in aspect of resource limitation, especially energy which is a major concern in MANET, since the nodes transmit packets in a multi-hop communication manner.Therefore, the energy cost of broadcast packet transmission (i.e., the number of transmissions) should be minimized to conserve the energy of the mobile nodes.Blind flooding is the most straightforward approach to broadcasting.Specifically, every node in the network forwards the broadcast packet exactly once.It ensures the full coverage of all the network: all the nodes in the network are guaranteed to receive the broadcast packet in case that the network is static and the occurrence of collision and error is not considered during propagation.However, flooding may generate excessive redundant transmissions which cause a critical problem, referred to as the broadcast storm problem (Ni et al., 1999), introducing communication contention and collision due to sharing wireless resources and overlapping coverage areas among nodes.The broadcast storm problem can be readily avoided by reducing the number of retransmissions.In order to alleviate the broadcast storm problem, probability-based, areabased, and neighbor knowledge approaches control the amount of traffic, that is, each node determines whether or not to retransmit the broadcast packet.The probability-based approach controls message flood with a predefined probability or received packet count.Obviously, it resembles blind flooding when the probability that a node retransmits the www.intechopen.comMobile Ad-Hoc Networks: Protocol Design 580 broadcast packet equals to one.In the area-based approach, each node determines whether or not to rebroadcast the packet with evaluation of its additional coverage area by rebroadcasting.If the additional coverage is less than the threshold, the node abandons retransmitting.This method relies on location or distance information of nodes to determine rebroadcasting.The neighbor knowledge approach utilizes one or two hop neighbor information obtained via periodical hello packets to reduce redundant rebroadcasting.This approach allows retransmitting only when it results in any additional neighbor to be reached.According to the methods controlling message flood, network overhead can be significantly reduced.However, some problems can occur such as end-to-end delay or latency and unreliability.Each node requires a certain waiting time to examine whether or not to rebroadcast a packet.In the area-based approach, for example, a node sets a random waiting time when a previously unseen packet arrives and it observes the duplicate packet arriving during the waiting time.Since nodes hold a packet for waiting times, the time spent on propagation from the packet origination to reach a node, namely end-to-end delay, increases.Reliability is considered in a network that nodes are fully connected to others in a single-or multi-hop fashion and the network is static.When a node determines to discard a packet with an examination of the necessity of rebroadcasting, some one-hop neighbors may not receive the packet.Furthermore, the packet is unreachable to nodes which have the sole connection through the neighbors.More precisely, a perfectly reliable broadcasting with minimizing redundancy is defined as a problem finding the minimum connected dominating set (MCDS) where a connected dominating set states that each node either belongs to the set or has a neighbor which belong to the set and is fully connected to others.Unfortunately, the problem of finding the MCDS is classified as NP-complete even if the global topology information is given (Lim & Kim, 2001;Lou & Wu, 2002).Some broadcasting schemes form a conjunction of area-based and neighbor knowledge approaches, called hybrid broadcasting schemes, to efficiently resolve redundant transmission, unreliability, and latency.Based on that outer nodes from the sender are prone to have more additional coverage than inner nodes (i.e., area-based approach), the outer takes higher priority of retransmission t h a n t h e i n n e r : w h e n a n o d e r e c e i v e s a previously unseen packet, it first sets a waiting time determined in inverse proportion to the distance to the sender.Instead of computation of additional coverage to make a determination of packet drop, each node examines whether all its neighbors receive the packet (i.e., neighbor knowledge) to resolve a potential unreliability.The remainder of this chapter is organized as follows.Section 2 introduces issues in broadcasting.Section 3 reviews previously published broadcasting methods.Section 4 describes hybrid broadcasting schemes.Section 5 concludes this chapter and gives some possible future works. Issues in broadcasting 2.1 The broadcast stormAs mentioned above, flooding is the simplest solution to broadcasting.The fundamental idea behind flooding is that every node participates in transmission of a packet exactly once www.intechopen.com