Efficient neighbour discovery and route request flooding schemes for ad hoc networks with directional antennas.

Abstract

The use of directional antennas in ad hoc networks gains more popularity in recent years. Directional antenna provides a node with the ability to transmit over longer distance with a transmission beam that is narrowly focused in one particular direction. When used properly, directional antennas offer the potential of increasing the network connectivity and the network bandwidth, while reducing the number of hops and the interference region.

Neighbor discovery plays a significant role in ad hoc networks with directional antennas. To efficiently use the directional antenna, a node needs to know the direction of the intended recepient to where it will form the transmission beam. To fully benefit from the longer transmission range of the directional antenna, the neighbor discovery scheme should be able to provide the node with the information about the neighbors beyond the omnidirectional transmission range.

In this thesis, an efficient distributed neighbor discovery scheme for ad hoc networks with directional antennas is proposed. The proposed scheme aims to discover neighbors beyond the omnidirectional transmission range by querying a small subset of the neighbors in the omnidirectional transmission range. It provides a fast neighbor discovery for a node that is joining an existing system. The use of high power broadcast is not required in the discovery process.

The information provided by the neighbor discovery scheme can also be exploited by higher layer protocols for other purposes such as for making a better routing decision. In ad hoc networks, many reactive routing protocols perform the route discovery by flooding the route request packets throughout the network. This flooding process usually consumes the network bandwidth considerably and involves a lot of nodes within certain hops from the source node.

In this thesis, an efficient scheme for flooding the route request packets in ad hoc networks with directional antennas is also proposed. The scheme exploits the local neighbor information provided by the neighbor discovery scheme at the lower layer. In the proposed scheme, route request packets are forwarded only to selected representative neighbors using directional transmissions instead of being broadcast to all neighbors. Two strategies are proposed to effectively select the representative neighbors. The fixed branching strategy selects one representative neighbor in each predefined forwarding direction, while the honeycomb strategy selects the representative neighbors to create a hexagonal tiling pattern. Both strategies are able to achieve a high route discovery success rate while keeping the number of involved nodes and the number of transmissions low.