Routing overhead in variable topology networks.

摘要

Mobile ad hoc and sensor networks are examples of variable topology networks. To enable services in such networks, there is the need to gather, maintain and update information about the whole topology or a portion thereof. Two well-known approaches are termed "proactive" and "reactive". The process of maintaining and updating is closely related to routing overhead, and is completed by various routing protocols. This research attempts to study these protocols to discover their fundamental limits and scalability characteristics of both the proactive and reactive routings.;For proactive routing, we derive lower bounds on memory requirements and communication routing overhead. The key is to first find lower bounds on the control message sizes, and then relate this to the rate of exchange through the parameters of mobility model. The minimum complexity of the control message sizes is intuitively a function of the complexity of network. We capture this dependence through the information-theoretic measure called the Minimum Expected Codeword Length as the minimum number of bits required to describe a change. A scalability analysis with respect to the total numbers of nodes and clusters is provided under three different network scaling modes. Finally, practical design issues are studied by providing the optimal numbers of clusters that asymptotically minimize (1) the memory requirement for cluster head; and (2) the total control message routing overhead.;For reactive routing, we present a new mathematical framework for quantifying the routing overhead. We focus on situations where the nodes are stationary but unreliable. We explicitly model the routing-layer traffic in terms of the statistical description of the distance between a source and a destination. Both regular and random network models are analyzed. For each network model, expressions of various components of the routing overhead are derived as functions of the traffic patterns. Results are compared against ns-2 simulations, which corroborate the essential characteristics of the analytical results. One of the key insights that can be drawn from the mathematical results is that it is possible to design infinitely scalable reactive routing protocols by judicious engineering of the traffic patterns to satisfy the conditions presented in this research.