Efficient lightweight information dissemination algorithm for mobile wireless ad hoc networks

• US 7,420,954 B2
• Filed: 01/13/2004
• Issued: 09/02/2008
• Est. Priority Date: 01/13/2004
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: General Motors Corporation (Motors Liquidation Co. GUC Trust)
• Inventors: Andersen, Timothy D., Elbatt, Tamer A.
• Primary Examiner(s): Eng; George
• Assistant Examiner(s): HUYNH, NAM TRUNG
• Application Number:
  US10/756,942
• Publication Number:
  US 20050152318A1
• Time in Patent Office: 1,694 Days
• Field of Search: 455/41.2, 455/507, 370/236, 370/400, 370/238, 370/409, 370/392, 370315-327, 370/338, 370/254, 370/255, 375/132, 375/133
• US Class Current: 370/338
• CPC Class Codes: H04W 4/00 Services specially adapted for wireless communication networks; Facilities therefor
• CPC Class Codes: H04W 4/40 for vehicles, e.g. vehicle-to-pedestrians [V2P]
• CPC Class Codes: H04W 4/46 for vehicle-to-vehicle communication [V2V]
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A system and method for information dissemination in a wireless mobile ad hoc network. A method describes receiving a request to communicate a message from a source node to a destination, identifying each neighbor node of an ad hoc network, invoking a proactive border node broadcast protocol at the source node when the destination is a neighbor node and wherein the number of hops to the destination is less than a predetermined number of hops, invoking an on-demand border node broadcast protocol at the source node when the number of hops from the source node to the destination exceeds the predetermined number, and communicating the message from the source node based on the invoked broadcast protocol. A computer readable medium containing a computer program for information dissemination in a wireless mobile ad hoc network is also provided. Finally, a system for information dissemination in a wireless mobile ad hoc network is described.

Claims

1. A method for information dissemination in a wireless mobile ad hoc network comprising:

receiving a request to communicate information from a source node to a destination;

identifying each neighbor node of the source node in the ad hoc network;

invoking a proactive border node broadcast protocol at the source node when the destination is a neighbor node and wherein the number of hops to the destination is less than a predetermined number of hops;

invoking an on-demand border node broadcast protocol at the source node when the number of hops from the source node to the destination exceeds the predetermined number; and

communicating the information from the source node based on the invoked broadcast protocol by;

selecting at least one neighbor node as a border node based on a geographic location of the neighbor node and geometric criteria by determining at least one neighbor node having both a maximum distance from the source node and a minimum distance to a one of the compass point directions North, South East and West; and

broadcasting the information from the source node, wherein the broadcast information identifies the selected at least one border node and a communication destination.

2. The method of claim 1 wherein identifying each neighbor node comprises:

polling each neighbor node for position information;

receiving position information from each neighbor node responsive to the poll; and

generating a neighbor node table identifying the location of each neighbor node.

3. The method of claim 1 further comprising:

receiving the broadcast information at the selected border node;

invoking a border node broadcast protocol at the border node; and

rebroadcasting the received information from the border node to the destination based on the invoked border node broadcast protocol.

4. The method of claim 1 wherein the predetermined number of hops is selectable.

5. The method of claim 1 wherein at least one border node is selected for each compass point direction North, South, East and West.

6. A method for information dissemination in a wireless mobile ad hoc network comprising:

receiving a request to communicate information from a source node to a destination;

identifying each neighbor node of the source node in the ad hoc network;

invoking an on-demand border node broadcast protocol at the source node after determining that the number of hops from the source node to the destination exceeds the predetermined number; and

communicating the information from the source node based on the invoked broadcast protocol, wherein communicating the information comprises;

generating a destination query message;

selecting at least one neighbor node as a border node based on a geographic location of the neighbor node and geometric criteria by determining at least one neighbor node having both a maximum distance from the source node and a minimum distance to a one of the compass point directions North, South, East and West;

broadcasting the information from the source node;

wherein the information identifies the at least one selected neighbor node and the destination query message.

7. The method of claim 6 wherein the destination query message is a route request message for on-demand topology-based routing protocols.

8. The method of claim 6 wherein at least one border node is selected for each compass point direction North, South, East and West.

9. A computer readable medium storing a computer program comprising:

computer readable code for determining a request to communicate information between a source node and a destination;

computer readable code for identifying each neighbor node of the source node in the ad hoc network;

computer readable code for selecting at least one border node by determining at least one neighbor node having both a maximum distance from the source node and a minimum distance to one of the compass point directions North, South, East and West;

computer readable code for invoking a proactive border node broadcast protocol at the source node when the destination is a neighbor node and wherein the number of hops to the destination is less than a predetermined number of hops;

computer readable code for invoking an on-demand border node broadcast protocol at the source node when the number of hops from the source node to the destination exceeds the predetermined number; and

computer readable code for directing the communication of the message from the source node based on the invoked broadcast protocol.

10. The computer readable medium of claim 9 wherein computer readable code for identifying each neighbor node of an ad hoc network comprises:

computer readable code for polling the local zone for position information for each neighbor node; and

,

computer readable code for generating a neighbor node table identifying the location of each neighbor from position data received from each neighbor node responsive to the poll.

11. The computer readable code of claim 9 wherein code for directing the communication of information from the source node based on the border node broadcast protocol comprises:

computer readable code for selecting at least one neighbor node as a border node based on a geographic location of the neighbor node and geometric criteria;

computer readable code instructing the information to be broadcast from the source node; and

wherein the information identifies the selected at least one border node and a communication destination.

12. The computer readable medium of claim 11 further comprising:

computer readable code for receiving the broadcast information at the selected border node;

computer readable code for invoking a border node broadcast protocol at the border node; and

computer readable code for rebroadcasting the received information from the border node to the destination based on the invoked border node broadcast protocol.

13. A computer readable medium storing a computer program comprising:

computer readable code for determining a request to communicate information between a source node and a destination;

computer readable code for identifying each neighbor node of the source node in the ad hoc network;

computer readable code for selecting at least one border node by determining at least one neighbor node having both a maximum distance from the source node and a minimum distance to a one of the compass point directions North, South, East and West;

computer readable code for invoking an on-demand border node broadcast protocol at the source node when the number of hops from the source node to the destination exceeds the predetermined number, including

computer readable code for generating a destination query message;

computer readable code for selecting at least one neighbor node as a border node based on a geographic location of the neighbor node and geometric criteria; and

computer readable code instructing the information to be broadcast from the source node wherein the information identifies the at least one selected neighbor node and the destination query message; and

computer readable code for directing the communication of the message from the source node based on the invoked broadcast protocol.

14. The computer readable medium of claim 13 further comprising code for selecting at least one border node for each compass point direction North, South, East and West.