Providing routing paths for wireless devices

• US 7,397,789 B2
• Filed: 10/25/2003
• Issued: 07/08/2008
• Est. Priority Date: 12/29/2000
• Status: Expired due to Term

• Current Assignee: Hitachi Energy Switzerland AG (Hitachi, Ltd.)
• Original Assignee: Tropos Networks Incorporated (ABB Limited)
• Inventors: Srikrishna, Devabhaktuni, Chari, Amalavoyal Narasimha
• Primary Examiner(s): Appiah; Charles N
• Assistant Examiner(s): AJIBADE AKONAI, OLUMIDE
• Application Number:
  US10/693,721
• Publication Number:
  US 20040085928A1
• Time in Patent Office: 1,718 Days
• Field of Search: 455/445, 455/67.11, 455/67.13, 455/453, 709/238, 709/239, 709/240, 709/241, 709/242, 709/243, 709/244, 709/223, 370/329, 370/392, 370/395.3, 370/395.31, 370/252, 370/255, 370/229, 370/230.1, 370/231, 370/232, 370/233, 370/234, 370/235, 370/238, 370/238.1, 370/256, 370351-356, 370/395.32, 370/401, 370/408, 370/409, 370/237, 370/254
• US Class Current: 370/351
• 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:

receiving a broadcast beacon at a client;

the client deriving information from the beacon, the information allowing the client to identify all other clients in a multi-hop path from the client to a server;

further comprising the client;

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.

2. The method of wireless connectivity of claim 1, wherein the information identifying the other clients comprises addresses of the other clients.

3. The method of wireless connectivity of claim 1, wherein beacons are originated and broadcast by the server, and are modified and broadcast by clients.

4. The method of wireless connectivity of claim 1, wherein the client receives a plurality of broadcast beacons, modifies at least one of the received beacons, and transmits the at least one modified beacon.

5. The method of wireless connectivity of claim 3, wherein modified beacons comprise addresses of clients in the path, and an address of the server.

6. The method of claim 3, wherein the beacon broadcast by the server includes a hop-count set to an initial value, the method further comprising:

each client that receives the beacon broadcasting a modified beacon with the hop-count incremented by one;

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

7. The method of claim 1 further comprising:

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

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

8. The method of claim 7, wherein the identifier of the client is a client address.

9. The method of claim 5, further comprising:

determining if there is a previous default gateway identified; and

deleting the previous default gateway from memory.

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

collecting a plurality of beacons; and

selecting a single beacon to broadcast.

11. The method of claim 10, 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.

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

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

selecting the beacon with the lowest TMC.

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

identifying a beacon with a highest quality; and

selecting the beacon with the highest quality.

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

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

16. The method of claim 13, wherein the highest quality is based on a lowest level of traffic being handled by the server.

17. The method of claim 13, wherein the highest quality is based on a reliability of the beacon.

18. The method of claim 17, wherein the reliability is determined by a number of times the beacon is received compared to a number of times the beacon was broadcast.

19. 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.

20. A method of wireless connectivity comprising:

receiving a broadcast beacon at a client;

the client deriving information from the beacon, the information allowing the client to identify all other clients in a multi-hop path from the client to a server;

wherein the broadcast beacon includes a sequence number representing a current routing cycle.

21. The method of claim 20, further comprising upon a client receiving a beacon, determining if a beacon was previously received for this routing cycle;

and

if no beacon was previously received for the routing cycle, storing a routing path to the server from the beacon.

22. The method of claim 20, further comprising, if the beacon was previously 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.

23. The method of claim 20, 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.

24. 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 one of the server or another client, wherein the beacon includes a sequence number representing a current routing cycle;

the client deriving information from the beacon, the information allowing the client to identify all other clients in a multi-hop path from the client to a 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.

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

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

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

28. The method of claim 24, wherein

receiving a reverse beacon broadcast by a client'"'"'s default gateway triggers the client to start a timer to send the reverse beacon.

29. The method of claim 24,

further comprising, if a client receives multiple beacons:

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

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

30. The method of claim 29, wherein the link quality comprises reliability of the beacon.

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

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

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

34. The method of claim 24, 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.

35. The method of claim 24, 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.

36. The method of claim 35, 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.

37. The method of claim 36, further comprising:

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