Reliable Broadcasting in Mobile Ad-Hoc Networks

Reliable Broadcasting in Mobile Ad-Hoc Networks

Phaneesh Kuppahalli

Department of Computer Science

The University of Texas at Dallas, Texas

pxk039000@utdallas.edu

ABSTRACT

In a mobile ad-hoc network, providing a reliable broadcast is one of the most important requirements. In broadcasting, a source node sends a message to all the other nodes in the network. Broadcasting operation is expected to be executed more frequently in mobile ad-hoc networks MANETs. So the number of retransmissions in the broadcast has to be minimized. The reliable broadcast service ensures that all the hosts in the network deliver the same set of messages to the upper layer. The protocols that are used in wired networks are unsuitable for deployment on MANETs, as these do not take into account the node mobility, network load and congestion. There have been a lot of protocols which are proposed for reliable broadcasting in MANETs. A straight forward way is by Simple Flooding [1, 2] which is very costly and very inefficient. The other protocols are Probability based methods [3], Area Based Methods [3] and Neighbor Knowledge Methods [4, 5, 6 and 7]. Also, efficiency and reliability conflict with each other. Hence it is hard to achieve both at a time with just one scheme. This paper will aim at proposing improvements for reliable broadcasting in MANETs.

1. INTRODUCTION

The drastic improvements in the wireless communications and portable wireless devices have made mobile computing a reality. Recently, Mobile Ad Hoc Networks (MANETs) has attracted a lot of attention and research. MANETs are made of a group of independent mobile hosts which communicate with each other. A mobile host may not be able to communicate directly with all the other hosts. So, the packets traverse various intermediate nodes before reaching the destination. All the nodes in the network assist in routing. The ad-hoc networks are created dynamically on the fly. The hosts are allowed to move around in the network. Routing protocols in ad-hoc networks should provide means to deliver packets to destination nodes given these dynamic topologies.

Applications of MANETs occur in battle-fields, major disaster and some business environments where networks need to be deployed immediately without any base stations or fixed networks.

Broadcasting is process by which a source node sends a message to all the other nodes in the entire network. Broadcasting operation is expected to be executed more frequently in mobile ad-hoc networks MANETs. Ad hoc On-Demand Distance Vector (AODV) [10] and Dynamic Source Routing (DSR) [9] are the two most widely studied unicast on-demand ad-hoc routing protocols which use broadcasting. These broadcasts use flooding which is inefficient and very costly. The other protocols that use broadcasting are Probability based methods [3], Area Based Methods [3] and Neighbor Knowledge Methods [4, 5, 6 and 7]. Since broadcasting is the most basic operation in ad-hoc networks, the reliability of the broadcast is one of the most important requirements. This paper discusses the some of the existing reliable broadcast protocols and also proposes improvements for reliable broadcasting in MANETs.

The rest of the paper is organized as follows. In section 2, the broadcast storm[12] and implosion[13] problems are discussed. In section 3, the related work is discussed. In section 4, the comparison of some of the existing protocols and improvements for the reliable broadcast in mobile ad-hoc networks are described. In section 5, the conclusion is given.

2. PRELIMINARIES

A MANET consists of a set of mobile hosts that may communicate with one another from time to time. No base stations are supported. Each host is equipped with a CSMA/CA (carrier sense multiple access with collision avoidance) [11] transceiver. In such environment, a host may communicate with another directly or indirectly. In indirect communication, the packet is transmitted between sender and receiver through intermediate nodes. The broadcast problem refers to the sending of a message to all other hosts in the network. In such environments, any of the nodes can issue a broadcast message at any time so it can experience repetitive collisions. Acknowledgements may cause serious medium contention (and thus, another "storm") surrounding the sender.

Broadcast storm caused by flooding

A straight-forward approach to achieve reliable broadcast is by simple flooding. A host, on receiving a broadcast message for the first time, has to rebroadcast the message. Clearly, this costs n transmissions in a network of n hosts. In a CSMA/CA network, drawbacks of flooding include:

* Redundant rebroadcasts. When a mobile host decides to rebroadcast a broadcast message to its neighbors, all its neighbors already have the message.

* Contention. After a mobile host broadcasts a message, if many of its neighbors decide to rebroadcast the message, these transmissions (which are all from nearby hosts) may severely contend with each other.

* Collision. Because of the deficiency of back-off mechanism, the lack of RTS/CTS dialogue, and the absence of CD, collisions are more likely to occur and cause more damage.

Collectively, the above phenomenon is referred to as the broadcast storm problem [12].

Acknowledgement implosion problem

The high transmission contention and congestion in MANETs will result in high transmission error rate. So providing a reliable broadcast under dynamic MANETs is a major challenge. As pointed out by other researchers, achieving total reliability for broadcasting in MANETs is impractical. Acknowledgements are the usual way to ensure broadcast delivery. The requirement for all the receivers to send ACKs in response to a packet reception may become a bottleneck. This is called the ACK implosion problem [13].

2 RELATED WORK

The broadcast protocols can be divided into various categories like Simple Flooding; Probability based methods, Area Based Methods and Neighbor Knowledge Methods. In the following section the basic broadcast protocols are described.

Simple Flooding

The algorithm for Simple Flooding [1, 2] starts with a source node broadcasting a packet to all neighbors. Now each of the neighbors that receive this packet will