Analysis and design of ad hoc broadcasting protocols

We summarize in this dissertation our progress on modeling, analyzing and designing efficient broadcasting protocols. The techniques to broadcast packets containing some control information to the whole network have been widely needed in many ad hoc applications, such as searching a route to another host and disseminating warning messages. Three major directions are explored in this thesis. Our attention is first focused on constructing mathematical model of several popular broadcast schemes. We then study the impact of mobility on broadcast schemes and then proceed to a very specific application of ad hoc broadcast: route searching, where a novel idea to reduce broadcast redundancy is proposed.;In contrast to previous work based on simulations or numeric analysis, the primary objective of our theoretical analysis is to obtain close-form formulas of performance metrics for various broadcast schemes. In Chapter II, two popular ad hoc broadcast schemes are modeled and analyzed theoretically in both 1-D and 2-D networks. Close-form formulas have been obtained and compared thoroughly with simulations, which have demonstrated that the obtained theoretical formulas could be used to shorten simulation time and optimally set protocol parameters.;In Chapter III, we focus on designing efficient broadcast algorithms in highly-mobile scenarios. Our design is based on the detailed analysis of all kinds of situations where nodal movement causes packet loss. We deal with each movement pattern with a different mechanism that has greatly enhanced network performance. At the end of this chapter, theoretical results are also provided to quantitatively analyze the performance improvement achieved by the proposed algorithm.;We have also studied broadcasting algorithms within the context of route discovery in Chapter IV. The idea is to send out messages to terminate a broadcast after the destination is found. To achieve this, we use various techniques such as adjusting protocol thresholds and limiting the number of propagating hops. The proposed algorithms can be implemented in on-demand routing protocols to reduce broadcast traffic and improve bandwidth efficiency.;Our conclusions and future directions for research are discussed in Chapter V.