Network protocol for wireless devices utilizing location information

• US 6,744,740 B2
• Filed: 12/21/2001
• Issued: 06/01/2004
• 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
• Primary Examiner(s): Pezzlo, John
• Assistant Examiner(s): ODLAND, DAVID E
• Application Number:
  US10/036,553
• Publication Number:
  US 20030117966A1
• Time in Patent Office: 893 Days
• Field of Search: 370/229, 370/230, 370/235, 370/238, 370/254-256, 370/310--31, 370/328, 370/389-393, 370/432, 455/403, 455/422, 455/427-430, 455/432-440, 455/445, 455/456, 455/457
• 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, comprises:

one or more cluster heads of the plurality of nodes wherein each cluster head is coupled to a corresponding one or more dependent nodes of the plurality of nodes and thereby forms a cluster, wherein each cluster head is operable to communicate with other cluster heads of the one or more cluster heads and said cluster heads one or more dependent nodes;

each cluster head uses a first location function to determine its geographical location;

each node of the plurality of nodes uses a second location function to determine relative distances to a plurality of neighboring nodes;

each cluster head of the one or more cluster heads selectively receives and stores location information received from the other cluster heads and said cluster heads'"'"' one or more dependent nodes; and

each cluster head of the one or more cluster heads selectively communicates its location information to its one or more dependent nodes thereby allowing each node of the plurality of nodes to also determine its location with respect to a corresponding cluster head of the one or more cluster heads.

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

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

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

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

6. The system of claim 4, wherein a first node of the plurality of nodes receives a packet from a source node that transmitted the packet to the first node, and the first node notices that the location of the destination node is wrong, the first node transmits a wrong location packet to one or more of the source node and the cluster head of the destination 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 Coverage Maps of the one or more nodes, wherein the one or more nodes have a tree structure.

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

9. The system of claim 1, wherein the second location function is one or more of triangulation, manual input, global positioning system (GPS) location, received signal strength (RSS), timing from direct sequence spread spectrum (DSSS) signals, ultra wide band signals, and use of a nodes random ID.

10. The system of claim 1, wherein the one or more cluster heads are determined by executing an algorithm designed to rank the cluster heads according to one or more performance measures.

11. The system of claim 10, wherein the one or more performance measures include one or more of processing power, processing speed, latency, bandwidth, utilization, reliability, and cost.

12. The system of claim 1, wherein the first location function is one or more of triangulation, manual input, global positioning system (GPS), and received signal strength (RSS).

13. The system of claim 12, wherein for each cluster head at least two other nodes of the plurality of nodes in data transmission range of said cluster head use a third location function to determine their locations independently and provide this information to the cluster head.

14. The system of claim 1, wherein after the network is created, facilitating the transmission of a packet from a source node of the plurality of nodes to a destination node of the plurality of nodes comprises:

an intermediate node of the plurality of nodes checks if the destination address is in a zone routing table of the intermediate node;

the intermediate node forwards the packet if the destination address is in the zone routing table of the intermediate node;

if the destination address is not in the zone routing table of the intermediate node, the intermediate node requests a path to the destination node from a cluster head of the intermediate node using a logical ID of the destination node;

if the cluster head of the intermediate node has the path to the destination node based upon the logical ID, then the packet is so forwarded; and

if the cluster head of the intermediate node does not have the path to the destination node, the cluster head of the intermediate node queries other cluster heads listed in a cluster table of the cluster head of the intermediate node.

15. The system of claim 14, further comprising:

if no cluster heads in the cluster table of the cluster head of the intermediate node have a path to the destination, the intermediate node transmits a path discovery packet to a plurality of neighbors closest to the logical ID of the destination node;

if the destination node responds with a path update providing an optimal path for the packet, then the packet is forwarded to the destination using this optimal path; and

if the destination node does not respond, then the packet is not transmitted to the destination node and an error packet is sent to the source node.

16. The system of claim 1, wherein each node of the plurality of nodes has a logical ID, and said logical ID specifies its nodes location relative to other nodes in the network.

17. The system of claim 16, wherein the logical ID comprises a cluster ID and a node ID.

18. The system of claim 16, wherein a node of the plurality of nodes that forwards a logical ID to a neighbor updates the nodes coverage map, said coverage map defined to be a union of all coverage areas of said nodes dependent nodes.

19. The system of claim 1, wherein the plurality of nodes are organized into a plurality of layers said layers being logically organized so that a node of a first layer is operable to store its location with respect to a common reference and said node of the first layer is further operable to send network invitation messages to nodes of a second layer, thereby allowing nodes of the second layer to be added to the network.

20. The system of claim 19, wherein first layer comprises those nodes that are neighbors of a cluster head, and wherein subsequent layers comprise those nodes that are one hop distance from a previous layer.

21. The system of claim 19, wherein upon nodes of the second layer being invited to join the network, these nodes provide their relative distance information to the first layer, first layer then relaying this relative distance information to the cluster heads, wherein the cluster heads then use this relative distance information to calculate location of nodes of the second layer and assign location ID'"'"'s to the nodes of the second layer.

22. The system of claim 21, wherein a node of the second layer selects a node of the first layer to act as a parent node, wherein the parent node is operable to relay network information between the network and the node of the second layer.

23. The system of claim 22, wherein the parent node is selected using one or more of the following metrics:

least depth to a cluster head, parent node signal strength, and a load parameter.

24. The system of claim 19, wherein a node of the first layer updates its coverage map whenever a cluster head calculates a location of a node of the second layer.

25. The system of claim 1, wherein one or more of the plurality of nodes are designated as gateway nodes, said gateway nodes having neighbors from more than one cluster.

26. The system of claim 25, wherein the gateway nodes communicate their gateway status to their respective cluster heads, thereby allowing each cluster head in the network to communicate via the gateway nodes with other cluster heads and build a cluster table containing ID'"'"'s of other cluster heads within the network.

27. The system of claim 26, wherein each cluster head obtains the contents of cluster tables of non-neighboring cluster heads by a periodic exchange of cluster table information with neighboring cluster heads and a comparison of exchanged cluster table information with stored cluster table information.

28. The system of claim 27, wherein the cluster tables reduce the protocol overhead by acting as distributed databases of node location information.

29. The system of claim 1, wherein after the network has been established each node of the plurality of nodes possesses a routing zone table that indicates a number of hops to other nodes within the network.

30. The system of claim 29, wherein a transmission range of the node and a hop distance X to a given node within the routing zone satisfy the following equation:

31. The system of claim 1, wherein each cluster head of the one or more cluster heads selectively communicating its location information to its one or more dependent nodes further comprises the one or more dependent nodes determining their location in the network relative to said cluster head.

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

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

determining the geographical location of each cluster head using a first location function;

determining relative distances from a node of the plurality of nodes to each neighbor of that node using a second location function;

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

each cluster head of the one or more cluster heads selectively communicating its location information to its one or more dependent nodes thereby allowing each node of the plurality of nodes to also determine its location with respect to a cluster head of the one or more cluster heads.

33. The method of claim 32, wherein each cluster head of the one or more cluster heads stores a database of the location of its nodes and other cluster heads.

34. The method of claim 32, wherein the plurality of nodes are interconnected through packet exchange, and further comprising:

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

receiving each transmitted packet at a destination node of the plurality of nodes.

35. The method of claim 34, further comprising:

upon a packet reaching a first node in the plurality of nodes and the first node 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 one or more nodes in the return path that is unable to locate a path to the destination node, thereby providing the first node and the one or more nodes with an optimal path for the packet.

36. The method of claim 34, further comprising:

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

37. The method of claim 34, further comprising storing a resident zone routing table upon each node of the plurality of nodes wherein the zone routing table identifies the next optimal node to relay a packet based upon the destination node of the packet.

38. The method of claim 37, further comprising, upon a first node of the plurality of nodes receiving a packet from the source node that transmitted the packet to the first node, and wherein the first node should have the location of the destination node within its Routing Zone Table but the node is not listed in its Zone Routing Table, the first node transmits 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 packet flooding process.

39. The method of claim 37, wherein nodes of the one or more nodes that are neighbors exchange zone routing table information.

40. The method of claim 32, wherein creating the network within the plurality of nodes based upon the stored location information within the one or more cluster heads further comprises:

identifying one or more gateway nodes, wherein each gateway node has neighbor nodes belonging to more than one cluster head;

each cluster head communicating with other cluster heads using a gateway node of the one or more gateway nodes so that a cluster table containing ID'"'"'s, locations and coverage maps of other cluster heads is created; and

each cluster head using the cluster table as a distributed database of node location and routing information of the network.

41. The method of claim 32, wherein each cluster head obtains the contents of cluster tables of non-neighboring cluster heads by a periodic exchange of cluster table information with neighboring cluster heads and a comparison of exchanged cluster table information with stored cluster table information.

42. The method of claim 32, wherein after the network is created, a node receiving a packet to be forwarded, and forwarding this packet using one of:

one or more nodes within a transmission range of said node;

location based routing, wherein the node determines a destination logical ID and destination location for the packet and forwards the packet to a node closest to the destination location;

path discovery routing, wherein said node transmits a plurality of path discovery messages to a plurality of nodes that are close to a destination location of said packet, and the plurality of nodes attempt to communicate with destination location to provide said node with a path to the destination location of the packet; and

location discovery routing, wherein said node determines that destination location of the packet is incorrect and communicates with its neighbors to potentially locate the missing node.

43. The method of claim 32, wherein the first location function is one or more of triangulation, manual input, global positioning system (GPS), and received signal strength (RSS).

44. The method of claim 32, wherein the second location function is one or more of triangulation, manual input, global positioning system (GPS) location, received signal strength (RSS), timing from direct sequence spread spectrum (DSSS) signals, ultra wide band signals, and use of a nodes random ID.

45. The method of claim 32, wherein the plurality of nodes are each a wireless device, and at least one cluster head is a dedicated device.

46. The method of claim 32, wherein for each cluster head at least two other nodes in data transmission range of said cluster head also determine their location independently using a third location function and provide this information to the cluster head.

47. The method of claim 32, wherein the process of assigning one or more cluster heads further comprises:

executing an algorithm designed to rank the cluster heads according to one or more performance measures.

48. The method of claim 47, wherein the one or more performance measures include one or more of processing power, processing speed, latency, bandwidth, utilization, reliability, and cost.

49. The method of claim 32, wherein selectively receiving and storing at each cluster head the location information of other cluster heads and dependent nodes of that cluster head further comprises:

each cluster head informing neighboring nodes of its presence;

the neighboring nodes responding with their relative location information;

each cluster head updating its database with the position of its neighboring nodes based upon the relative location information received from its neighboring nodes;

each cluster head assigning logical IDs to its neighboring nodes; and

each node with a logical ID continuing this process of inviting its neighbors to join the network, forwarding relative location information to the cluster head, sending logical lD'"'"'s assigned by the cluster head to neighboring nodes, until all nodes are in the network and each cluster head contains relative location information of nodes within its cluster.

50. The method of claim 49, wherein a logical ID is formed from a MAC address of a device of each cluster head.

51. The method of claim 49, wherein a logical ID comprises a cluster ID and a node ID.

52. The method of claim 49, wherein each node also maintains a zone routing table comprising the number of hops to nodes within its cluster.

53. The method of claim 49 wherein each node that forwards a logical ID to a neighbor updates a coverage map of that node.

54. The method of claim 53, wherein the coverage map is defined to be a union of all dependent nodes coverage areas.

55. The method of claim 32, wherein after the network is created, facilitating the transmission of a packet from a source node to a destination node comprises:

an intermediate node checking if the destination address is in a zone routing table of the intermediate node;

delivering the packet if the destination address is in the zone routing table of the intermediate node;

requesting the path to the destination from a cluster head of the intermediate node using the logical ID of the destination node;

if the cluster head of the intermediate node has the path to the destination node based upon the logical ID, then the packet is so forwarded; and

if the cluster head of the intermediate node does not have the path to the destination node, the cluster head of the intermediate node queries other cluster heads listed in a cluster table of the cluster head of the intermediate node.

57. The method of claim 32, wherein determining nodes dependent from each cluster head within the plurality of nodes further comprises:

each cluster head determining those neighbor nodes of the plurality of nodes that are within a transmission range of said cluster head;

said cluster head communicating with these neighbor nodes to invite one or more of these neighbor nodes to perform network communications via said cluster head;

a subset of the one or more of the neighbor nodes accepting the invitation of said cluster head and providing their relative location with respect to their neighbors; and

said cluster head sending location information relative to said cluster head and assigning logical IDs to the subset of the one or more of the neighbor nodes.

58. The method of claim 32, wherein each cluster head of the one or more cluster heads selectively communicating its location information to its one or more dependent nodes further comprises the one or more dependent nodes determining their location in the network relative to said cluster head.

56. The method of claim further comprising:

if no cluster heads in the cluster table of the cluster head of the intermediate node have a path to the destination, transmitting a path discovery packet to a plurality of neighbors closest to the logical ID of the destination node;

if the destination node responds with a path update providing an optimal path for the packet, then the packet is forwarded to the destination using this optimal path; and

if the destination node does not respond, then the packet is not transmitted to the destination node and an error packet is sent to the source node.

59. A method for creating and maintaining a network, wherein

during a network setup phase further comprising:

assigning one or more cluster heads within a plurality of interconnected and randomly geographically located nodes, each cluster head selectively communicating with other cluster heads and nodes;

assigning logical IDs to the one or more cluster heads;

determining the geographical location of each cluster head using a first location determination function;

determining relative distances from a node to each neighbor of that node using a second location determination function, thereby enabling a coverage map for each node to be created;

during a cluster communication phase, further comprising;

identifying one or more gateway nodes, said gateway nodes having neighbors from more than one cluster;

the one or more gateway nodes communicating cluster head IDs of neighboring clusters to the cluster heads;

each cluster head creating a cluster table, said cluster table representing location, cluster ID, and coverage maps of other cluster heads with which said cluster head is able to communicate;

each cluster head updating its cluster table to include cluster heads that are reachable via communication with current entries in the cluster table;

during a node routing creation phase, further comprising each node communicating with its neighboring nodes to identify all nodes that are within transmission range of said node; and

during a network maintenance phase, further comprising;

a node receiving a packet to be forwarded, and forwarding this packet using one of;

said nodes list of nodes within the transmission range of said node;

location based routing, wherein the node determines a destination logical ID and destination location for the packet and forwards the packet to a node closest to the destination location;

path discovery routing, wherein said node transmits a plurality of path discovery messages to a plurality of nodes that are close to a destination location of said packet, and the plurality of nodes attempt to communicate with destination location to provide said node with a path to the destination location of the packet; and

location discovery routing, wherein said node determines that destination location of the packet is incorrect and communicates with its neighbors to potentially locate the missing node.

60. The method of claim 59, wherein each cluster head updating its cluster table further comprises communicating a hello message to neighboring cluster heads, said neighboring cluster heads updating their cluster tables, and said neighboring cluster heads replying to said cluster head with their location, ID, and coverage map.

61. The method of claim 59, wherein a source node is operable to send a message to a certain geographical area by sending one or more multicast packets to one or more of said nodes cluster head and said nodes neighbors wherein the one or more multicast packets are routed by comparing the certain geographical area to coverage maps of nodes said one or more multicast packets are routed to.

62. The method of claim 61, wherein the missing node and the cluster head of the missing node update their routing information and inform their neighbors of the updated location of the missing node.

63. The method of claim wherein upon the location discovery locating the missing node, new location packets are sent to the source of the packet, the missing node, and the cluster head of the missing node.

64. A system for establishing a network within a plurality of interconnected and randomly geographically located nodes, comprising:

one or more cluster heads of the plurality of nodes wherein each cluster head is coupled to a corresponding one or more dependent nodes of the plurality of nodes thereby forming a cluster, wherein each cluster head has means to communicate with other cluster heads of the one or more cluster heads and said cluster heads one or more dependent nodes;

means for each cluster head to determine its geographical location using a first location function;

means for each node of the plurality of nodes to determine relative distances to a plurality of neighboring nodes using a second location function;

means for each cluster head of the one or more cluster heads to selectively receive and store location information received from the other cluster heads and said cluster heads one or more dependent nodes; and

means for each cluster head of the one or more cluster heads to selectively communicates its location information to its one or more dependent nodes thereby allowing means for each node of the plurality of nodes to also determine its location with respect to a cluster head of the one or more cluster heads.