Mrp-based hybrid routing for mobile ad hoc networks

• US 20020145978A1
• Filed: 04/05/2001
• Published: 10/10/2002
• Est. Priority Date: 04/05/2001
• Status: Abandoned Application

• Current Assignee: Turbowave, Inc.
• Original Assignee: Turbowave, Inc.
• Inventors: Montgomery, Michael, Joe, Inwhee, MacIntyre, Lawrence P., Batsell, Stephen G.
• Application Number:
  US09/825,878
• Publication Number:
  US 20020145978A1
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In a mobile ad hoc network node first exchange their node sets of one-hop neighbors, thereby learning their sets of two-hop neighbors. A one-hop neighbor is a node in direct radio range of a source node. A two-hop neighbor node is one which, while beyond direct radio range of the source node, is in direct range of at least one of the source node'"'"'s one-hop neighbor. Thereafter, each node selects a subset of its one-hop neighbor nodes, called the multi point relay (MPR) set, such that the subset can cover all the two-hop neighbors when forwarding broadcast traffic from that node. Outside the two-hop region, routes are discovered on a demand basis by flooding. However, flooding traffic is reduced because only the subset, instead of all one-hop neighbors, participates in forwarding.

Claims

1. A routing protocol for mobile networks comprising a plurality of mobile nodes, comprising the steps of:

assigning each of a plurality of mobile nodes an identifier (ID);

each of said nodes storing a list of said identifiers of neighboring nodes in a one-hop region to create a one-hop neighbor list;

exchanging said one-hop neighbor list with one-hop neighbors;

creating a two-hop neighbor list from said exchanged one-hop neighbor lists;

selecting a subset of said one-hop neighbors, such that the subset can directly compute a route to all two-hop neighbors when forwarding broadcast traffic;

when forwarding broadcast traffic to a destination node beyond said two-hop neighbors of a source node;

forwarding a search request packet to said one hop neighbors until said destination node is present in said two-hop neighbor list;

storing a reverse path tracking a path of said request packet;

forwarding a route return packet via said reverse path to said source node to compute a path to said destination node.

2. A routing protocol for mobile networks as recited in claim 1 wherein when a node moves to a new neighborhood one of said one-hop neighbors will recognize a link failure and notify its one-hop neighbors to update their respective one-hop neighbor lists.

3. A routing protocol for mobile networks as recited in claim 1 wherein when a node monitors overheard packets for its own destination address to receive said overheard packets early.

4. A method of routing traffic packets through a mobile network comprising a plurality of mobile nodes, comprising the steps of:

each node creating a one-hop node list, where said one-hop node list comprises all other nodes within direct radio range;

exchanging said one-hop node list with each of said other nodes on said one-hop node list to create a two-hop node list;

selecting a subset of nodes on said one-hop list, such that the subset provides a path to all nodes on said two-hop node list;

computing a route between a source node and a destination node directly from said source node'"'"'s one-hop neighbor list and said two-hop neighbor list when said destination node is within two-hops of said source node; and

said source node flooding only said subset nodes when searching for a route to a destination node beyond two-hops of said source node.

5. A method of routing traffic packets through a mobile network comprising a plurality of mobile nodes, comprising the steps of:

assigning each of a plurality of mobile nodes an identifier (ID);

each of said nodes storing a list of said identifiers of neighboring nodes in a one-hop region to create a one-hop neighbor list;

exchanging said one-hop neighbor list with one-hop neighbors;

creating a two-hop neighbor list from said exchanged one-hop neighbor lists; and

selecting a subset of said one-hop neighbors, such that the subset can directly compute a route to all two-hop neighbors when forwarding broadcast traffic.

6. A method of routing traffic packets through a mobile network as recited in claim 5 further comprising the step of discovering outside of said two-hop region by flooding.