Network protocol for wireless devices utilizing location information

• US 20030117966A1
• Filed: 12/21/2001
• Published: 06/26/2003
• Est. Priority Date: 12/21/2001
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Chen, Priscilla
• Granted Patent: US 6,744,740 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• 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
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A system and method for establishing a network within a plurality of interconnected and randomly geographically located nodes, such as wireless devices. One or more cluster heads are selected within the nodes and selectively communicate with the other cluster heads and nodes. The cluster head can be a wireless device or a specific dedicated device such as a router. Each cluster head determines the geographical location of that cluster head and the data-dependent nodes of the cluster head, and selectively receives and stores location information of the other cluster heads and dependent nodes to create an optimal data-routing network within the plurality of nodes.

Claims

1. A system for establishing a network within a plurality of interconnected and randomly geographically located nodes, comprising one or more cluster heads selected in a predefined manner from the plurality of nodes and selectively communicating with other cluster heads and nodes, and each cluster head determining the geographical location of that cluster head and all nodes within its own cluster, and the cluster head selectively receiving and storing location information of the other cluster heads and dependent nodes, thereby creating an optimal network within the plurality of nodes.

2. The system of claim 1, wherein the plurality of nodes are each a wireless device, and at least one cluster head is a dedicated device.

3. The system of claim 1, wherein each cluster head collectively stores a database of the location of the nodes within its own cluster.

4. The system of claim 1, wherein the nodes are interconnected through packet exchange, and each packet is transmitted from an source node, through one or more nodes of the network, and received at a destination node.

5. The system of claim 4, wherein, upon a packet reaching a first node in the plurality of nodes and the packet is unable to locate a path to the destination node, the first node transmitting a path discovery packet to the destination node, and the destination node transmitting a path update packet back to the first node, thereby providing the first node, along with all other nodes along the return path that are unable to locate a path to the destination node, with the optimal path for the packet.

6. The system of claim 4, wherein, upon a first node receiving a packet from a source node that transmitted the packet to the first node, and the first node noticing that the location of the destination node is wrong, the first node transmitting a wrong location packet to the source node.

7. The system of claim 4, wherein a multicast packet is selectively sent to the one or more nodes within a geographical region using a Coverage Map along a tree sturcture.

8. The system of claim 4, wherein, after the one or more cluster heads have created an optimal network within the plurality of nodes, each node has a resident zone routing table stored thereupon wherein the zone routing table identifies the next optimal node to relay a packet based upon the destination node of the packet.

9. A method for establishing a network within a plurality of interconnected and randomly geographically located nodes, comprising the steps of:

designating one or more cluster heads within the plurality of nodes, each cluster head selected in a predefined manner and selectively communicating with other cluster heads and nodes;

determining the geographical location of each cluster head;

determining nodes dependent from each cluster head within the plurality of nodes;

selectively receiving and storing at each cluster head the location information of other cluster heads and the dependent nodes of that cluster head; and

creating an optimal network within the plurality of nodes based upon the stored location information within the one or more cluster heads.

10. The method of claim 9, wherein each cluster head collectively stores a database of the location of the nodes.

11. The method of claim 9, wherein the nodes are interconnected through packet exchange, and further comprising the steps of:

selectively transmitting one or more packets from a source node, through one or more of the plurality of nodes of the network; and

receiving each transmitted packet at a destination node.

12. The method of claim 11, further comprising the steps of:

upon a packet reaching a first node in the plurality of nodes and the packet is unable to locate a path to the destination node, transmitting from the first node a path discovery packet to the destination node; and

transmitting from the destination node along a return path a path update packet back to the first node, and any other node in the return path that is unable to locate a path to the destination node, thereby providing the first node and other nodes with the optimal path for the packet.

13. The method of claim 11, further comprising, upon a first node receiving a packet from a source node that transmitted the packet to the first node, and the first node should have the location of the destination node within its Routing Zone but the node is not listed in its Zone Routing Table, the first node concludes that the location of the destination node is wrong, transmits from the first node a wrong location packet to the source node and to the source node'"'"'s Cluster Head, and the first node attempting to find the missing node with a local flooding

14. The method of claim 11, further comprising the steps of:

selectively sending a multicast packet to the one or more nodes within a geographical region, using the Coverage Maps of the nodes along an established logical tree structure.

15. The method of claim 11, further comprising the step of storing a resident zone routing table upon each node wherein the zone routing table identifies the next optimal node to relay a packet based upon the destination node of the packet.

16. A system for establishing a network within a plurality of interconnected and randomly geographically located nodes, comprising networking node means for selectively creating an optimal network within the plurality of nodes, the networking node means selected in a predefined manner from the plurality of nodes and selectively communicating with other nodes, and the networking node means determining the geographical location of the networking node means and determining nodes dependent from the networking node means, and the networking node means selectively receiving and storing location information of dependent nodes.

17. The system of claim 16, wherein the networking mode means is a data routing device.

18. The system of claim 16, wherein the networking node means stores a database of the location of all or selected nodes in the plurality of nodes.

19. The system of claim 16, wherein the nodes are interconnected through packet exchange, and a multicast packet is selectively sent to one or more networking node means for selective transmission to all nodes interconnected to the networking node means.

20. The system of claim 19, wherein, after the networking node means has created an optimal network within the plurality of nodes, each node has a resident zone routing table stored thereupon wherein the zone routing table identifies the next optimal node to relay a packet based upon the destination node of the packet.