Routing and control mechanisms for dense mobile adhoc networks

Abstract

It is not an exaggeration to mention that mobile devices have become ubiquitous and they are used for variety of purposes ranging from personal communication to disaster management and more. These devices are capable of establishing mobile ad hoc networks (MANETs) for multihop communication without the support of infrastructure. This enables more interesting and useful applications of mobile devices, for example for collaborative leaners in large classrooms, shoppers in crowded shopping malls, spectators in sports stadiums, online gamers and more. MANETs have not sufficiently developed to a deployable level yet. Routing in MANETs is a major problem. It is challenging to devise routing protocols for MANETs due to dynamic topology resulting from mobility, limited battery life and impairments inherent in wireless links. Traditional routing approach is to tweak the existing routing protocols that are designed for wired networks. Therefore, it is common to appoint special nodes to perform routing controls and gather global state information such as routing tables. We identify this approach as the fixed-stateful routing paradigm. Fixed stateful routing does not scale with the density of MANETs because the routes will get obsolete quickly due to the dynamic topology causing frequent routing updates. The overhead for these frequent updates will be unacceptable when the MANETs become dense. For example, the control overhead of routing updates in most of the traditional routing protocols are of magnitude O(N) or O(N2), where N is the number of nodes in the network. We name the routing approach that does not require to maintain global network states and does not appoint key nodes for routing and control as mobile-stateless routing paradigm. We propose a novel concept called endcast that leverages message flooding for end to end communication in MANETs in mobile-stateless manner. However, flooding causes heavy amounts of redundant messages, contention and collisions resulting in a situation known as broadcast storm problem. When flooding is utilized for end to end communication, the messages will flood beyond the destination. We call this situation broadcast flood problem. Repetitive rebroadcasting in simple flooding is analogous to biological cell division in the growth of human organs. Chalone mechanism is a regulatory system to control the growth of the organs. In this mechanism, each biological cell secretes a molecule called chalone and the concentration of chalones in the environment increases when the number of cells increases. When the chalone concentration exceeds a threshold the cells stop dividing themselves. Counter based flooding is one of the efficient flooding schemes, in which a node decides not to rebroadcast a received message if the message is subsequently heard multiple times exceeding a predefined threshold during a iv v random wait period. Inspired by the chalone mechanism in the growth of the organs we selected counter based flooding to unicast messages in a MANET. We proposed an inhibition scheme to stop the propagation of message beyond the destination to mitigate the broadcast flood problem. In this scheme, the destination transmits a smaller size control message that we call inhibitor that also propagates using counter based flooding but with a smaller random wait period than in the case of data message. Furthermore, inhibitors are limited to the region of the MANET covered by data flooding. The proposed endcast scheme outperforms simple flooding in such a way that over 45% of redundant messages are saved in all the network configurations starting from 100-node network in ideal wireless conditions when the nodes were placed on a playground of 600m 400m and each node was configured to have 200m of transmission radius. Similarly, the protocol manages to save over 45% of redundant messages for all node densities ranging from 10 to 300 in realistic wireless conditions simulated by IEEE 802.11g standard wireless MAC implementation with power saving transmission radius of 40m. This saving increases rapidly as networks grow by size in both the ideal and realistic wireless network conditions. The inhibition scheme of the protocol was also found to be effective, for example, redundant messages grow in number at a rate about 8 frames per every 25 nodes added to the network when there is inhibition in operation whereas the growth rate is about 170 frames per every 25 nodes when the protocol operates without inhibition in the simulated network scenario. The major contribution of this research is the analytical model that we developed to design and evaluate endcast schemes. We developed a graph theoretic model to evaluate the propagation of messages in endcast, based on a preliminary model developed by Viswanath and Obraczka [2]. We modified the model by (i) improving its method of estimating the number of new nodes reached by each level of rebroadcast (ii) modeling the impact of node mobility and (iii) incorporating time domain representation to model the flooding schemes that involve random assessment delays (iii) enabling it to represent efficient flooding schemes such as counter based flooding. We present the process of estimating the area covered by the propagation of flooding messages using a geometric method. Time domain is represented by indesing the edges of the flooding graph by time. The counter value and the threshold in counter based flooding are converted into a rebroadcasting probability and estimated using a probability mass function that we constructed by considering the overlapping of radio range circles of the nodes.