Systems and methods for creating wireless small world networks

• US 7,139,262 B1
• Filed: 05/18/2000
• Issued: 11/21/2006
• Est. Priority Date: 05/18/2000
• Status: Expired due to Fees

• Current Assignee: Raytheon BBN Technologies Corp. (Rtx Corporation)
• Original Assignee: BBN Technologies (Rtx Corporation)
• Inventors: Elliott, Brig Barnum
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/573,860
• Time in Patent Office: 2,378 Days
• Field of Search: 370338-346, 370/300, 370/351, 370/401, 370/436, 370/449, 370/349, 370/252, 370/254, 370/238, 370/331, 370/342, 370/458, 370352-353, 370/335, 370/509, 370/316, 370/390, 370/394, 370/255, 455450-456, 455/524, 455/427, 455/500, 455/422.1, 455/518, 455/431, 455/515, 455/552.1, 455/512, 455/456.1, 455/422, 375350-356, 342/457, 342/450, 709/238, 709/241
• US Class Current: 370/351
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04W 4/08 User group management
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 84/10 Small scale networks; Flat hierarchical networks

Abstract

A system (510) routes packets in a network (200) having multiple nodes. The system identifies a group (500) of the nodes (520–550) and determines routing distances to each of them. The system (510) then selects a set of the nodes from the group (500) based on the determined routing distances and updates a routing table based on the selection. The system (510) routes packets through the network (200) using the updated routing table.

Claims

1. A first node in a network having a plurality of second nodes, at least some of the second nodes including an omni-directional antenna, the first node comprising:

a directional antenna configured to communicate with a group of the second nodes;

a memory configured to store a routing table used for transmitting packets through the network; and

a processor configured to identify the group of second nodes using the directional antenna, select a set of the second nodes from the group of second nodes based on routing distances to the second nodes, update the routing table based on the selected set of second nodes, and route packets through the network using the updated routing table.

2. The first node of claim 1, wherein the directional antenna includes:

a steerable directional antenna configured to be positioned in a plurality of directions.

3. The first node of claim 2, further comprising:

a steering mechanism configured to position the steerable directional antenna in each of the plurality of directions.

4. The first node of claim 2, wherein the processor is further configured to determine a best direction from the plurality of directions to point the steerable directional antenna.

5. The first node of claim 4, wherein the processor is configured to point the steerable directional antenna in each of the plurality of directions and identify ones of the second nodes present in each of the plurality of directions.

6. The first node of claim 5, wherein the processor is configured to receive beacons from ones of the second nodes in each of the plurality of directions to identify the second nodes present in each of the plurality of directions.

7. The first node of claim 5, wherein the processor is configured to determine a routing distance to each of the identified second nodes, select one of the identified second nodes with a largest routing distance, and point the steerable directional antenna in a direction of the selected second node.

8. The first node of claim 7, wherein the processor is configured to locate each of the identified second nodes in the routing table and extract the routing distance for each of the identified second nodes from the routing table.

9. The first node of claim 1, further comprising:

an omni-directional antenna configured to communicate with another group of the second nodes.

10. The first node of claim 1, wherein the processor is configured to transmit beacons to the second nodes and receive beacons from the second nodes.

11. The first node of claim 10, wherein the processor is configured to identify each of the nodes in the group of second nodes using the received beacons.

12. The first node of claim 1, wherein the processor is configured to determine a routing distance to each of the nodes in the group of second nodes, select one of the nodes in the group of second nodes with a largest routing distance, and include the selected second node in the set of second nodes.

13. The first node of claim 12, wherein the processor is configured to update the routing table based on the selected second node and select another one of the nodes in the group of second nodes using the updated routing table.

14. The first node of claim 13, wherein the processor is configured to determine a routing distance to each of the nodes in the group of second nodes based on the updated routing table, identify one of the nodes in the group of second nodes with a largest routing distance, and use the identified second node as the selected other second node.

15. The first node of claim 13, wherein the processor is configured to transmit an update signal to all of the second nodes, the update signal instructing the second nodes to update routing tables associated with the second nodes, wait a predetermined period of time for the second nodes to update the routing tables, and select the other second node after the predetermined period of time elapses.

16. The first node of claim 1, wherein the set of second nodes includes all of the group of second nodes.

17. A method for routing packets by a first node in a network having a plurality of second nodes, at least some of the second nodes including an omni-directional antenna, the first node including a steerable directional antenna, the method comprising:

storing a routing table for use in transmitting packets through the network;

identifying a group of the second nodes using the steerable directional antenna;

selecting a set of the second nodes from the group of second nodes based on routing distances to the second nodes;

updating the routing table based on the selected set of second nodes; and

routing packets through the network using the updated routing table.

18. The method of claim 17,

wherein the identifying includes:

determining a best direction from the plurality of directions to point the steerable directional antenna.

19. The method of claim 18, wherein the determining includes:

pointing the steerable directional antenna in each of the plurality of directions, and

identifying ones of the second nodes present in each of the plurality of directions.

20. The method of claim 19, wherein the identifying ones of the second nodes includes:

exchanging beacons with ones of the second nodes in each of the plurality of directions to identify the second nodes present in each of the plurality of directions.

21. The method of claim 19, wherein the determining further includes:

determining a routing distance to each of the identified second nodes,

selecting one of the identified second nodes with a largest routing distance, and

pointing the steerable directional antenna in a direction of the selected second node.

22. The method of claim 21, wherein the determining a routing distance includes:

locating each of the identified second nodes in the routing table, and

extracting the routing distance for each of the identified second nodes from the routing table.

23. The method of claim 17, wherein the identifying includes:

receiving beacons from the second nodes, and

identifying the group of second nodes using the received beacons.

24. The method of claim 17, wherein the selecting includes:

determining a routing distance to each of the nodes in the group of second nodes,

selecting one of the nodes in the group of second nodes with a largest routing distance, and

including the selected second node in the set of second nodes.

25. The method of claim 24, wherein the updating includes:

updating the routing table based on the selected second node, and

selecting another one of the nodes in the group of second nodes using the updated routing table.

26. The method of claim 25, wherein the selecting another one of the group of second nodes includes:

determining a routing distance to each of the nodes in the group of second nodes based on the updated routing table,

identifying one of the nodes in the group of second nodes with a largest routing distance, and

using the identified second node as the selected other second node.

27. The method of claim 25, wherein the updating the routing table includes:

transmitting an update signal to all of the second nodes, the update signal instructing the second nodes to update routing tables associated with the second nodes, and

waiting a predetermined period of time for the second nodes to update the routing tables; and

wherein the selecting another one of the nodes in the group of second nodes includes;

selecting the other second node after the predetermined period of time elapses.

28. The method of claim 17, wherein the selecting includes:

selecting all of the nodes in the group of second nodes as the set of second nodes.

29. A computer-readable medium that stores instructions executable by a first node to perform a method for updating a routing table for routing packets in a network having a plurality of second nodes, at least some of the second nodes including an omni-directional antenna, the first node including a directional antenna and the routing table, the method comprising:

identifying a set of the second nodes using the directional antenna;

determining routing distances to each of the nodes in the set of second nodes;

selecting a subset of the set of second nodes as network neighbors based on the determined routing distances; and

updating the routing table based on the subset of second nodes selected as the network neighbors.

30. A system for selecting neighboring nodes in a network having a plurality of nodes, comprising:

a steerable antenna configured to receive beacons from nodes within a communication area; and

a processor configured to determine a routing distance to each of the nodes in the communication area, select one of the nodes with a largest routing distance, and identify the selected node as a neighboring node with which the system can directly communicate.

31. A computer-readable medium that stores instructions executable by a node to perform a method for selecting neighboring nodes in a network having a plurality of nodes, comprising:

detecting, using a steerable antenna, nodes within a communication area based on beacons received from the nodes;

determining a routing distance to each of the detected nodes;

selecting one of the detected nodes with a largest routing distance; and

classifying the selected node as a neighboring node.

32. A method for selecting a direction for a steerable directional antenna of a wireless node in a network including a plurality of nodes, comprising:

pointing the steerable directional antenna in each of a plurality of directions;

identifying ones of the nodes present in each of the plurality of directions;

determining a routing distance to each of the identified nodes;

selecting one of the identified nodes with a largest routing distance; and

pointing the steerable directional antenna in a direction of the selected node.

33. The method of claim 32, wherein the identifying includes:

exchanging beacons with ones of the nodes in each of the plurality of directions to identify the nodes present in each of the plurality of directions.

34. The method of claim 32, wherein the determining includes:

locating each of the identified nodes in a routing table associated with the wireless node, and

extracting the routing distance for each of the identified nodes from the routing table.

35. A system for selecting a direction for a steerable directional antenna of a wireless node in a network including a plurality of nodes, comprising:

a memory configured to store instructions; and

a processor configured to execute the instructions in the memory to point the steerable directional antenna in each of a plurality of directions, identify ones of the nodes present in each of the plurality of directions, determine a routing distance to each of the identified nodes, select one of the identified nodes with a largest routing distance, and point the steerable directional antenna in a direction of the selected node.

36. A computer-readable medium that stores instructions executable by at least one processor to perform a method for selecting a direction for a steerable directional antenna of a wireless node in a network including a plurality of nodes, comprising:

aiming the steerable directional antenna in each of a plurality of directions;

identifying ones of the nodes present in each of the plurality of directions;

determining a routing distance to each of the identified nodes;

selecting one of the identified nodes with a largest routing distance; and

pointing the steerable directional antenna in a direction of the selected node.

37. A small world network, comprising:

a plurality of first nodes, each of the first nodes including an omni-directional antenna; and

at least one second node, including;

a steerable directional antenna configured to be positioned in a plurality of directions and communicate with a group of the first nodes,

a memory configured to store a routing table used for transmitting packets through the network, and

a processor configured to identify the group of first nodes, determine a routing distance to each node in the group of first nodes, select at least one of the first nodes based on the routing distance, update the routing table based on the selected at least one first node, and route packets through the network using the updated routing table.

38. The network of claim 37, wherein the processor is further configured to determine a best direction from the plurality of directions to point the steerable directional antenna.

39. The network of claim 37, wherein the at least one second node includes a plurality of second nodes, and a number of the second nodes is small in relation to a number of the first nodes.

40. The network of claim 37, further comprising:

at least one third node that includes both a directional antenna and an omni-directional antenna, where the at least one third node is capable of functioning as a first node or a second node.