Method of broadcasting packets in ad-hoc network

• US 7,889,691 B2
• Filed: 11/13/2007
• Issued: 02/15/2011
• Est. Priority Date: 11/13/2007
• Status: Active Grant

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson), Toyota Infotechnology Center USA, Inc. (Toyota Motor Corporation)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson), Toyota Infotechnology Center USA, Inc. (Toyota Motor Corporation)
• Inventors: Demers, Stephanie, Lee, John, Pang, Marcus, Hikita, Toshiro, Onishi, Ryokichi, Chen, Wai
• Primary Examiner(s): Pezzlo; John
• Application Number:
  US11/983,829
• Publication Number:
  US 20090122738A1
• Time in Patent Office: 1,190 Days
• Field of Search: 370/252, 370/278, 370/315, 370/328, 370/329, 370/401
• US Class Current: 370/315
• CPC Class Codes: H04H 20/08 among terminal devices
• CPC Class Codes: H04H 20/57 for mobile receivers
• CPC Class Codes: H04H 60/50 of broadcast or relay stations
• CPC Class Codes: H04H 60/53 of destinations
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04W 40/20 based on geographic position or location

Abstract

A method for distributing a packet to a plurality of moving nodes comprising receiving a packet containing at least a message, a sender identifier, a location of a sender, an identifier for a relay node and distance from the sender and the relay node, determining if a node receiving the packet is the relay node and immediately distributing the packet to a plurality of moving nodes if the receiving node is the relay node. If the receiving node is not the relay node, the method further comprises steps of waiting a set period of time, determining if a packet is received from a different sender containing the same message, within the period of time and distributing the packet to a plurality of moving nodes if a packet containing the same message is not received within the period of time. The distributed packet includes an identifier for a successive relay node.

Claims

1. A method for distributing a broadcast data packet to a plurality of moving nodes comprising the steps of:

receiving a broadcast data packet containing at least a message, a sender identifier, a location of a sender, an identifier for a relay node and distance from the sender and the relay node;

determining if a node receiving the broadcast data packet is the relay node; and

distributing immediately the broadcast data packet to a plurality of moving nodes if the receiving node is the relay node, the broadcast data packet that is distributed includes an identifier for a successive relay node;

wherein if the receiving node is determined not to be the relay node, the method further comprising;

waiting a period of time;

determining if a broadcast data packet is received from a different sender containing the same message, within the period of time; and

distributing the broadcast data packet to a plurality of moving nodes if a broadcast data packet containing the same message is not received within the period of time, the broadcast data packet that is distributed includes an identifier for a successive relay node.

2. The method for distributing a broadcast data packet according to claim 1, further comprising the step of storing the message, the sender identifier, the location of the sender, and distance from the sender and the relay node.

3. The method for distributing a broadcast data packet according to claim 2, further comprising the steps of:

determining a location of the receiving node;

calculating a distance between the sending node and the receiving node based upon the location of the sender and the determined location of the receiving node;

retrieving the distance from the sender and the relay node; and

calculating the period of time at least based on the calculated distance and the distance from the sender and the relay node.

4. The method for distributing a broadcast data packet according to claim 3, further comprising the step of setting a wait timer with the calculated period of time.

5. The method for distributing a broadcast data packet according to claim 3, wherein the period of time Wt=−

(MaxWT/Range)*min{d,Range}+MaxWT, MaxWt is a default maximum wait time, range is the distance between the sending node and the relay node, and d is the calculated distance between the sending node and the receiving node.

6. The method for distributing a broadcast data packet according to claim 1, further comprising the step of:

selecting the relay node.

7. The method for distributing a broadcast data packet according to claim 6, wherein the step of selecting the relay node comprises the sub-steps of:

retrieving for each neighboring node, the neighboring node'"'"'s identifier and position information;

calculating for each neighboring node, a distance from the sending node and the neighboring node; and

determining one node from all neighboring nodes that is the furthest from the sending node;

wherein the neighboring node that is the furthest is selected as the relay node.

8. The method for distributing a broadcast data packet according to claim 1, further comprising the step of:

broadcasting periodically an information data packet, the information data packet contains at least the broadcasting node'"'"'s identifier and its location.

9. The method for distributing a broadcast data packet according to claim 8, further comprising the steps of:

receiving from a plurality of neighboring nodes the periodic information data packet; and

storing the node'"'"'s identifier and location in a forwarding table, wherein the location of each neighboring node is stored for at least two consecutive periods.

10. The method for distributing a broadcast data packet according to claim 6, further comprising the steps of:

determining a direction of movement of the sender;

determining a location of the sender;

calculating, for each neighboring node, a distance from the sender;

determining, for each neighboring node, a relative location with respect to the direction of movement of the sender; and

comparing, for each neighboring node, the determined direction of movement with the relative location,

wherein a neighboring node that is the furthest node having a relative location in an opposite direction of movement of the sender is selected as the relay node.

11. The method for distributing a broadcast data packet according to claim 6, further comprising the steps of:

determining, periodically, a location of each node; and

storing, the determined location of each node,

wherein each node maintains its location in storage for at least two consecutive periods.

12. The method for distributing a broadcast data packet according to claim 11, wherein the direction of movement for each node is determined based upon a current location of a node and a location of the node from a previous period.

13. A method for distributing a broadcast data packet to a plurality of moving nodes comprising the steps of:

receiving a broadcast data packet containing at least a message, a sender identifier, a location of a sender, an identifier for a first and second relay node and distance from the sender and each of the first and second relay nodes;

determining if a node receiving the broadcast data packet is either the first or second relay node; and

distributing immediately the broadcast data packet to a plurality of moving nodes if the receiving node is the first or second relay node, the broadcast data packet that is distributed includes an identifier for a successive relay node;

wherein the receiving node is determined not to be the first or second relay node, the method further comprising;

waiting a set period of time;

determining if a broadcast data packet is received from a different sender containing a same message within the period of time; and

distributing the broadcast data packet to a plurality of moving nodes if a broadcast data packet containing the same message is not received within the period of time, the broadcast data packet that is distributed includes an identifier for a successive relay node.

14. The method for distributing a broadcast data packet according to claim 13, further comprising the step of selecting the first and second relay nodes.

15. The method for distributing a broadcast data packet according to claim 14, wherein a neighboring node that is the furthest node having a relative location behind the direction of movement of the sender is selected as the first relay node.

16. The method for distributing a broadcast data packet according to claim 14, wherein a neighboring node that is the furthest node having a relative location ahead of the direction of movement of the sender is selected as the second relay node.

17. The method for distributing a broadcast data packet according to claim 13, wherein the forwarding steps include the sub-step of:

selecting a successive relay node from the plurality of moving nodes.

18. The method for distributing a broadcast data packet according to claim 17, wherein the selecting of the successive relay node comprising the steps of:

retrieving for each neighboring node of the relay node, the neighboring node'"'"'s identifier and position information;

calculating for each neighboring node of the relay node, a distance from the relay node and the neighboring node; and

determining one node from all neighboring nodes that is the farthest from the relay node,

wherein the neighboring node that is the furthest from the relay node is selected as the successive relay node.

19. The method for distributing a broadcast data packet according to claim 17, further comprising the steps of:

determining a direction of movement of the data packet;

determining a location of the relay node;

calculating, for each neighboring node, a distance from the relay node;

determining, for each neighboring node, a relative position of the neighboring node and the relay node; and

comparing, for each neighboring node the determined direction of movement of the data packet with the relative position of the neighboring node,

wherein a neighboring node that is the furthest node having a relative location in a direction opposite to the direction from which the data packet is received is selected as the successive relay node.