Book Description

In mobile ad hoc networks (MANETs)[1], a mobile station (MS) can communicate with nodes outside of its transmission range by employing intermediate nodes as relays. To find a path to a specific destination node, the source node broadcasts route request packets that are forwarded to all other nodes. A simple flooding scheme is employed in AODV[2], where every node rebroadcasts these route request packets even if some of its neighbors have already broadcast the requests and thus the rebroadcasts may reach no additional nodes. In MANETs, broadcasting is extensively used in route discovery, address resolution, and many other network services. The efficiency of broadcasting protocol can dramatically affect the performance of the entire network. Appropriate use of a probabilistic method can reduce the number of rebroadcasting, therefore reduce the chance of contention and collision among neighboring nodes. A good probabilistic broadcast protocol can achieve higher throughput and lower energy consumption, without sacrificing reachability or having any significant degradation. In this research, we study the problem of using probabilistic approaches to improve broadcasting and route discovery performance in wireless ad hoc and sensor networks. Our contributions can be summarized as follows. First, we propose a selfish node based approach. In this approach, we categorize MSs into normal nodes and selfish nodes. Normal nodes forward packets for other nodes while selfish nodes do not. The advantage of using selfish nodes is that the total rebroadcast traffic can be reduced. The disadvantage is that we may miss the optimal route and suffer from a low delivery rate. In this approach, we use a probabilistic method to set up a proper number of selfish nodes. Using a combination of gossiping and dominating set, we can reduce the route discovery cost by minimizing the number of rebroadcasts, while achieving higher delivery rate due to the reduction of rebroadcast traffic, thereby reducing the number of collisions. Second, we propose a leveled probabilistic approach. In this approach, we use a pre-assigned probability model to avoid redundant packet relays. In our protocol, a MS probabilistically sends relay packets (rebroadcasts) according to its neighborhood information. Our approach categorizes MSs into four groups. For each group of nodes, we assign a specified value of rebroadcasting probability. The MSs with more neighbors are given higher rebroadcasting probability. Using this method, we can reduce routing cost by minimizing the number of rebroadcasts in route discovery phase without significantly affecting the network connectivity. Third, we propose a dynamic probabilistic approach. In this approach, we dynamically adjust the rebroadcasting probability as per the node distribution and node movement. This is conducted based on locally available information. In addition, our approach does not require any assistance from accurate distance measurements or exact location determination. This approach can further reduce routing cost by adapting its behavior according to the environment changes. Fourth, we compare MANETs and WSNs (wireless sensor networks). We realize the difference between MANETs and WSNs in terms of the node characteristics, energy consumption, mobility model and the traffic model. We also evaluate sensing coverage and communication coverage for different sensor range or communication range. Fifth, we propose a broadcasting scheme using connecting areas. We assign/select connecting areas during the network start up period. Only the connecting area head node located inside one of the connecting areas is responsible to rebroadcast the packet while the nodes outside the connecting areas do not rebroadcast. By choosing the size of the connecting area and the placement of the connecting areas, we can reduce the rebroadcasting cost while maintaining the reachability. Sixth, we propose a scheme that is based on redundant degree of each sensor. In this approach, we evaluate the redundant degree value of each sensor node and use this value to decide whether to rebroadcast packet or not. The rebroadcast from a node with high degree of redundancy has high possibility to be redundant. We set up a threshold to allow nodes with low enough degree connectivity to rebroadcast packets. In this work, we first describe the details of our protocols, comparing them with AODV and other protocols, and presenting evaluation results in MANETs. Analytical and simulation results show that our approaches outperform the AODV protocol on several metrics in most cases, including the average number of rebroadcasts, average number of packet collisions, end-to-end delay, and the throughput. We propose broadcasting protocols in wireless sensor networks, and explore other methods to further improve the performance of broadcasting and route discovery in MANETs and WSNs.