Method and system to provide a routing protocol for wireless devices

• US 20040143678A1
• Filed: 01/09/2004
• Published: 07/22/2004
• Est. Priority Date: 12/29/2000
• Status: Active Grant

• Current Assignee: Hitachi Energy Limited
• Original Assignee: Amalavoyal Narashima Chari, Devabhaktuni Srikrishna
• Inventors: Chari, Amalavoyal Narashima, Srikrishna, Devabhaktuni
• Granted Patent: US 7,689,224 B2
• Time in Patent Office: Days
• US Class Current: 709/240
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

A method and apparatus for generating connectivity is described. The method includes a server broadcasting a beacon including the server'"'"'s address. The method further includes each client that receives the beacon rebroadcasting the beacon. The result is that each client receiving the beacon knows a way to reach the server.

Claims

1. A method of wireless connectivity comprising:

broadcasting a beacon by a server; and

receiving and storing the beacon at the client, the client further retaining information indicative of a path to the server; and

rebroadcasting the beacon by the client.

2. The method of claim 1, comprising:

storing every beacon received;

designating one path identified by one beacon as the optimal path;

setting a default gateway as identified in the optimal path; and

rebroadcasting only the beacon representing the optimal path.

3. The method of claim 1, wherein the beacon broadcast by the server includes a hop-count set to zero, the method further comprising:

each client that receives the beacon rebroadcasting the beacon with the hop-count incremented by one;

such that each client receiving the beacon knows a way to reach the server and the number of hops in this path.

4. The method of claim 1, wherein the beacon broadcast by the server includes server address, such that each client receiving the beacon knows the address of the server.

5. The method of claim 1 further comprising:

each client that receives the beacon rebroadcasting the beacon with an address of the client added to the beacon;

such that each client receiving the beacon has a complete path to the server.

6. The method of claim 1, wherein the beacon includes a sequence number representing a current routing cycle.

7. The method of claim 6, further comprising, upon a client receiving a beacon,

determining if a beacon has already been received for this routing cycle;

and

if no beacon has already been received for the routing cycle, storing a routing path to the server from the beacon.

8. The method of claim 7, further comprising, if the beacon has already been received for the routing cycle:

determining if this beacon has a higher sequence number than a prior beacon for this routing cycle, and if so,

storing the current beacon in memory.

9. The method of claim 6, further comprising, upon a client receiving a beacon,

determining if a currently received beacon represents an optimal path for this routing cycle;

and

if the current beacon represents the optimal path, identifying a default gateway in the current beacon, and storing the default gateway.

10. The method of claim 2, further comprising:

determining if there is a previous default gateway identified; and

deleting the previous default gateway from memory.

11. The method of claim 1, further comprising, for each client:

collecting all beacons; and

selecting a single beacon to rebroadcast.

12. The method of claim 11, wherein selecting a beacon comprises:

identifying a number of hops between the server and the client for each beacon; and

selecting the beacon with the lowest number of hops.

13. The method of claim 11, wherein selecting a beacon comprises:

identifying a traffic monitoring code (TMC) for each of the beacons; and

selecting the beacon with the lowest TMC.

14. The method of claim 11, wherein selecting a beacon comprises:

identifying a beacon with a highest quality; and

selecting the beacon with the highest quality.

16. The method of claim 14, wherein the highest quality is based on most back end bandwidth capacity at the server.

18. The method of claim 1, further comprising:

sending a reverse beacon to the server; and

constructing a client tree in the server, wherein the server has a path to all clients.

15. The method of daim 14, wherein the highest quality is a best signal-to-noise ratio.

17. The method of daim 14, wherein the highest quality is based on a lowest level of traffic being handled by the server.

19. A server for wireless communications comprising:

a beacon logic to generate a beacon and broadcast the beacon; and

a wireless transceiver to receive a plurality of reverse beacons, the reverse beacons indicating a path to each of the clients; and

a client tree storing the path to each of the clients, such that the server can send data to any client, either directly or through other clients on the network.

20. The server of claim 19, further comprising a monitoring logic to monitor a network, the monitoring logic using the client tree to generate a map of the network of clients.

21. A method of generating a routing path for a system including a server and a plurality of clients, the method comprising each client:

receiving a beacon from the server;

rebroadcasting one beacon received from an upstream node; and

broadcasting a reverse beacon upstream, the reverse beacon being addressed to the known upstream node, the reverse beacon used by the server and each client to set up a routing table.

22. The method of claim 21, wherein a routing table in a particular client includes a default gateway and a path to each client downstream from the particular client.

23. The method of claim 21, further comprising the server broadcasting a dummy reverse beacon to initiate the reverse beacon cycle.

24. The method of claim 21, further comprising each client aggregating the reverse beacons received from downstream clients, and sending a single reverse beacon including the aggregated information.

25. The method of claim 21, wherein receiving a reverse beacon broadcast by a client'"'"'s default gateway triggers the client to start a timer to send the reverse beacon.

26. The method of claim 21, further comprising, if a client receives multiple beacons:

evaluating a link quality of each of the beacons received; and

selecting the default gateway based on the beacon with the best link quality and rebroadcasting that beacon.

27. The method of claim 26, wherein the link quality comprises reliability of the beacon.

28. The method of claim 26, wherein the link quality includes information about the back end bandwidth capacity of the server.

29. The method of claim 26, wherein the link quality includes information about the traffic being handled by the server.

30. The method of claim 21, wherein a connection between the server and the client is a wireless connection.

31. The method of claim 21, wherein a connection between the server and the client is chosen from among the following types of connections:

a wireless connection, a wired connection, and a switched connection.

32. The method of claim 21, further comprising the client:

receiving a plurality of beacons from a plurality of servers; and

selecting one of the plurality of beacons, and setting the server associated with the selected beacon as its preferred server;

thereby self-selecting to belong in a cluster associated with the preferred server.

33. The method of claim 32, further comprising the client:

moving outside the cluster;

upon receiving a beacon from a new cluster, the client setting the server associated with the new beacon and the new cluster as its preferred server.

34. The method of claim 33, further comprising:

expiring a routing table including a previous preferred server and previous default gateway.

35. A routed wireless network comprising:

a plurality of wired access points;

a plurality of clients, each client belonging to a cluster of clients administered by a single server and such that membership in a cluster is elected by the client through the selection of a beacon to rebroadcast.

36. The network of claim 35, wherein the membership in the cluster may change as a result of a client roaming from one region to another within the network.

37. The network of claim 35, wherein the membership in the cluster may change as a result of the addition of a new server to the network.

38. The network of claim 35, wherein the new server may be a client that is converted into a server by adding a wired connection.

39. The network of claim 35, wherein the membership in the cluster may change as a result of the server selected by the client failing to provide adequate service.