Method and system for routing packets through a network by employing geographical position data

• US 7,307,978 B2
• Filed: 05/01/2001
• Issued: 12/11/2007
• Est. Priority Date: 05/01/2001
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP (Singapore) PTE Limited (Broadcom, Inc.)
• Inventors: Carlson, Greg
• Primary Examiner(s): PHAM, BRENDA H
• Application Number:
  US09/847,765
• Publication Number:
  US 20020163912A1
• Time in Patent Office: 2,415 Days
• Field of Search: 370/235, 370/238, 370/248, 370/253, 370/255, 370/310, 370/310.1, 370/310.2, 370/328, 370/338, 370/386, 370/389, 370/392, 370/349, 370/400, 370/401, 370/402, 370/316, 370/411, 370/395.31, 370/395.32, 370/351, 370/410, 342/458, 455/456, 709/227, 709/228, 709/237
• US Class Current: 370/349
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A geographic position dependent routing method and system for ad hoc networks, where are least one of the nodes of the ad hoc network can change its location. A position determination module is provided for determining the position of the current node. A communication mechanism is provided for communicating messages with other nodes in the ad hoc network. A geographic position dependent routing mechanism is coupled to the position determination module and communication mechanism for receiving messages, the position of the current node, and based thereon for one of transmitting the message and discarding the message.

Claims

1. A method for routing messages in an ad hoc network having a plurality of nodes, where each node has a location, where at least one node can change its location, the method comprising:

a) receiving a message;

b) determining whether the received message has been encountered recently;

c) when the received message has been encountered recently, discarding the message;

d) when the received message has not been encountered recently, determining whether the current node is the destination of the message;

e) when the current node is the destination of the message, processing the message; and

f) when the current node is not the destination of the message, selectively forwarding the message to another node in an intelligent manner that employs a geographic position data of the current node;

wherein the step of when the current node is not the destination of the message, selectively forwarding the message to another node in an intelligent manner that employs the geographic position data of the current node includes;

f_—

1) determining whether the current node is closer in proximity to the destination node than the last node is from the destination node;

f_—

2) when the current node is closer in proximity to the destination node than the last node is close to the destination node, then updating the message with the location of the current node;

writing the location of the current node in a last position field in the message; and

f_—

3) forwarding the updated message to a next node in the network including transmitting the updated message in a broadcast fashion to nodes that are in communication range of the current node.

2. The method of claim 1 wherein the step of receiving a message includes

a_—

1) determining whether a message has been received;

a_—

2) when a message has not been received, the processing continues at step (a) to wait for the arrival of a message; and

a_—

3) when a message has been received, proceeding to step (b).

3. The method of claim 1 wherein the step of determining whether the received message has been encountered recently includes

b_—

1) determining whether the destination field of the received message matches with the destination field of previously received messages;

b_—

2), determining whether the source field of the received message matches with the source field of previously received messages; and

b_—

3) determining whether the message identifier field of the received message matches with the message identifier field of previously received messages.

4. The method of claim 1 wherein the step of determining whether the received message has been encountered recently includes

b_—

1) storing the destination field, the source field, and message identifier field of the received message for use in future processing of step (b).

5. The method of claim 1 wherein the step of when the received message has not been encountered recently, determining whether the current node is the destination of the message includes

d_—

1) comparing a unique address field in the received message with an address of the current node.

6. The method of claim 1 wherein the step of when the current node is not the destination of the message, selectively forwarding the message to another node in an intelligent manner that employs the geographic position data of the current node further includes

f_—

4) when the current node is not closer in proximity to the destination node than the last node is close to the destination node, a determination is made whether the depth count is in a predetermined relationship with a maximum depth count;

f_—

5) when the depth count is in a predetermined relationship with the maximum depth count, forwarding the message to a next node;

f_—

6) when the depth count is not in a predetermined relationship with the maximum depth count, discarding the message.

7. The method of claim 6 wherein the step of when the depth count is in a predetermined relationship with the maximum depth count, forwarding the message to a next node includes

updating the message with the location of current node;

transmitting the message in a broadcast fashion; and

proceeding to processing step (a).

8. The method of claim 1 wherein the step of when the current node is not the destination of the message, selectively forwarding the message to another node in an intelligent manner that employs the geographic position data of the current node further includes

f_—

7) determining whether the current node is closer to the destination node than the source node is from the destination;

f_—

8) when the current node is closer to the destination node than the source node is from the destination, forwarding the message to a next node; and

f_—

9) when the current node is further from the destination node than the source node is from the destination, then discarding the message.

9. The method of claim 8 wherein the step of when the current node is closer to the destination node than the source node is from the destination, forwarding the message to a next node includes

updating the message with the location of current node;

transmitting the message in a broadcast fashion; and

proceeding to receiving the message.

10. The method of claim 1 wherein the step of determining whether the received message has been encountered recently includes utilizing one of the destination field, the source field, and the message identifier field of the received message to make the determination of whether the received message has been encountered recently.

11. A routing system comprising:

a) a position determination module for determining the position of the current node;

b) a communication mechanism for communicating messages with other nodes;

c) a geographic position dependent routing mechanism coupled to the position determination module and communication mechanism for receiving messages, the position of the current node, and based thereon for one of transmitting the message and discarding the message; and

d) a message processing application coupled to the geographic position dependent routing mechanism for receiving messages and processing the messages for a particular application that can include a cellular telephone communication application.

12. The routing system of claim 11 wherein the geographic position dependent routing mechanism further includes

a recent message determination facility for receiving a message and determining whether the received message has been encountered recently.

13. The routing system of claim 12 wherein each message includes a destination field, a source field, and a message identifier field;

and

wherein the recent message determination facility further determines whether a destination field of the received message matches with the destination field of previously received messages;

whether a source field of the received message matches with the source field of previously received messages; and

whether a message identifier field of the received message matches with the message identifier field of previously received messages.

14. The routing system of claim 12 wherein the recent message determination facility further includes a recent message buffer for storing the destination field, the source field, and message identifier field of the received message for use in future processing.

15. The routing system of claim 12 wherein the geographic position dependent routing mechanism further includes

a destination checker coupled to the recent message determination facility for comparing a unique address field in the received message with an address of the current node to determine whether the current node is the destination of the received message.

16. The routing system of claim 15 wherein the geographic position dependent routing mechanism further includes

a last node distance comparator coupled to the destination checker for determining whether the current node is closer in proximity to the destination node than the last node is from the destination node;

when the current node is closer in proximity to the destination node than the last node is close to the destination node, the last node distance comparator updates the message with the location of the current node and forwards the updated message to a next node in the network.

17. The routing system of claim 16 wherein the geographic position dependent routing mechanism further includes

a depth count facility coupled to the last node comparator for determining whether a depth count is in a predetermined relationship with a maximum depth count;

when the depth count is in a predetermined relationship with the maximum depth count, the depth count facility forwards the message to a next node; and

when the depth count is not in a predetermined relationship with the maximum depth count, depth count facility discards the message.

18. The routing system of claim 11 wherein the geographic position dependent routing mechanism further includes

a source distance evaluation facility for determining whether the current node is closer to the destination node than the source node is from the destination;

when the current node is closer to the destination node than the source node is from the destination, the source distance evaluation facility forwards the message to a next node; and

when the current node is further from the destination node than the source node is from the destination, the source distance evaluation facility discards the message.