Wireless infrastructure and ad hoc network integration

• US 7,808,960 B1
• Filed: 05/25/2007
• Issued: 10/05/2010
• Est. Priority Date: 05/25/2006
• Status: Active Grant

• Current Assignee: Hong Kong University of Science and Technology
• Original Assignee: Hong Kong University of Science and Technology
• Inventors: Chen, Jiancong, Li, Shenjie, Wong, Chi Fai, Chan, Shueng Han Gary
• Primary Examiner(s): Afshar; Kamran
• Application Number:
  US11/753,864
• Time in Patent Office: 1,229 Days
• Field of Search: 370/310, 370/328, 370/338, 370254-255, 370/315, 455/423, 455/500, 455/503, 455/507, 709/223
• US Class Current: 370/338
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 28/0247 based on conditions of the access network or the infrastructure network central resource management H04W28/16
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A system and method for integrating infrastructure and ad hoc wireless networks. In one example embodiment, a plurality of nodes and access points exchange beacons and route replies which are forwarded by intervening nodes. Nodes determine whether to switch access points based on cost values contained in the received beacons. Intervening nodes store routes with weights to the source node, such that the access points maintain weights to every node in their zones.

Claims

1. A method for an access point (AP), the method comprising:

intermittently broadcasting, by the AP, a beacon message to be forwarded among a plurality of node devices to solicit joining a zone of the AP;

receiving, by the AP, a reply message in response to the beacon message from a first node device of the plurality of node devices; and

updating, by the AP, a list of node devices in the zone based on the reply message;

wherein the zone of the AP includes second node devices of the plurality of node devices, and each of the second node devices has a default route to the AP through one or more hops.

2. The method of claim 1, wherein the beacon message includes a value in a first field indicating a cost to join the zone of the AP, and the value in the first field is configured to be updated each time the beacon message is forwarded.

3. The method of claim 1, wherein the AP has an initial cost value and each of the plurality of node devices has a corresponding cost value, and the value in the first field of the beacon message is configured to include a sum of the initial cost value of the AP and the cost value of third node devices of the plurality of node devices located on a route through which the beacon message is forwarded.

4. The method of claim 1, wherein the AP is informed, by the reply message, about the first node device joining the zone of the AP, or the AP is provided with, by the reply message, updated routing information of the first node device if the first node device is already in the zone of the AP.

5. The method of claim 1, wherein the beacon message further includes a value in a second field indicating a number of hops that the beacon message is to be forwarded.

6. A method of managing wireless coverage, comprising:

receiving, by a receiving node, a beacon message;

if the beacon message is from a new access point (AP) that is not included in a list of APs of the receiving node, then;

adding, by the receiving node, the new AP to the list;

computing, by the receiving node, a cost to join a zone of the new AP; and

if the cost for the receiving node to join the zone of the new AP is lower by a given threshold than a cost to remain in a zone of another AP, which is already included in the list, then determining, by the receiving node, whether to switch to the zone of the new AP as a default zone; and

if the beacon message is from one of the APs in the list other than the new AP, then;

updating, by the receiving node, a cost to remain in a zone of said one of the APs based on information contained in the beacon message; and

forwarding, by the receiving node, the beacon message with the updated cost if a time-to-live of the beacon message is greater than zero.

7. The method of Claim 6, further comprising if the receiving node changes zones:

sending, by the receiving node a route reply message to the new AP; and

updating, by the receiving node, a default route to the new AP.

8. The method of claim 7, wherein the routing information in the route reply message sent by the receiving node is configured to be updated at intermediate nodes between the receiving node and the new AP.

9. The method of claim 7, wherein the route reply message is sent by the receiving node to enable the new AP to update a zone topology that includes a list of nodes in the zone of the new AP.

10. The method of claim 7, wherein the route reply message sent by the receiving node enables intermediate nodes between the receiving node and the new AP to process the route reply message so as to cache a route with a weight.

11. The method of claim 10, wherein the weight includes a total cost of the intermediate nodes in the cached route to join the zone of the new AP, so as to enable the new AP to have the weights of every node in its zone.

12. The method of claim 10, wherein the weight is a metric indicative of power, stability, or residual bandwidth in a node.

13. The method of Claim 6, wherein the route reply message includes routing information to the receiving node.

14. The method of claim 6, further comprising if the time-to-live of the beacon message from said one of the APs is greater than zero:

updating, by the receiving node, a hop field of that beacon message.

15. The method of claim 6, further comprising:

not sending, by the receiving node after a predetermined number of beacon messages, a route reply message to a particular AP in the list that sent the beacon messages, so as to enable the receiving node to be deleted from that access point'"'"'s list of nodes.

16. The method of claim 6, wherein the cost to join the zone of the new AP depends on a traffic load at the new AP and a number of nodes in the zone of the new AP.

17. A method comprising:

receiving, by a node device, a beacon message transmitted from an access point (AP),

wherein the beacon message includes a cost field that is based on a traffic load and a number of nodes in a zone of the AP;

if the AP is not included in a list of APs of the node device;

determining, by the node device, whether to switch to the zone of the AP; and

sending, by the node device, a route reply message to the AP;

if the AP is included in the list of APs of the node device;

updating, by the node device, the cost field of the beacon message; and

sending, by the node device, a route reply message to the AP that is included in the list;

wherein the route reply messages provides an updated default route between the receiving node and the AP.

18. The method of claim 17, wherein the beacon message includes an AP identifier field, a beacon count field, a time-to-live field, a hop field, and the cost field.

19. A method, comprising:

receiving, by a first of a plurality of node devices, a beacon message from an access point (AP), the beacon message being configured to solicit joining a zone of the AP;

determining, by the first node device, if the AP is new by checking a list of APs of the first node device, wherein the AP is new if not included in the list; and

adding, by the first node device, the AP to the list if the AP is determined to be new;

wherein;

the beacon message includes a value in a first field indicating a cost for the first node device to join the zone of the AP; and

the zone of the AP includes second node devices, of the plurality of node devices and each of the second node devices has a default route to the AP through one or more hops.

20. The method of claim 19, further comprising:

if the AP is new, checking, by the first node device, the value in the first field of beacon message; and

determining, by the first node device, whether to join the zone of the AP based at least in part on a result of said checking.

21. The method of claim 20, wherein the AP has an initial cost value and each of the plurality of node devices has a corresponding cost value, and the value in the first field of the beacon message includes a sum of the initial cost value of the AP and cost values of third node devices of the plurality of node devices located on a route through which the beacon message is sent to the AP by the first node device.

22. The method of claim 21, wherein the initial cost value of the AP is determined based at least in part on traffic load and a number of the second node devices in the zone of the AP.

23. The method of claim 21, wherein the beacon message further includes a value in a second field indicating a number of hops that the beacon message is to be forwarded, the method further comprising:

sending, by the first node device, a reply message to join the zone of the AP if the value in the first field is smaller by a pre-defined amount than a cost to stay in a zone of another AP that the first node device is currently in;

updating, by the first node device, the beacon message by adding the first node device'"'"'s own cost value to the value in the first field; and

forwarding, by the first node device, the updated beacon message if the value in the second field is greater than zero.

24. The method of claim 23, wherein the beacon message further includes a value in a third field indicating a sequence of the beacon message, the method further comprising:

if said determining determines that the AP is not new, checking, by the first node device, the value in the third field;

based on a result of said checking the value in the third field, updating, by the first node device, the list based on routing information of the AP contained in the beacon message;

forwarding, by the first node device, the updated beacon message if the value in the second field is greater than zero.

25. The method of claim 19, wherein the value in the first field is an indicator of power, stability, or residual bandwidth.

26. A method, comprising:

sending, by a first node device of a plurality of node devices, a plurality of request messages that request a route to a destination node device;

receiving, by the first node device, a plurality of reply messages from second node devices of the plurality of node devices and an access point (AP), the reply messages offering a plurality of corresponding routes to the destination node device; and

selecting, by the first node device, a route from the offered plurality of routes based at least in part on the reply messages;

wherein;

each of the reply messages includes a value in a first field indicating a cost to route to the destination node device; and

the value, in the first field of the reply message from the AP, is a sum of an initial cost value of the AP and cost values of third node devices of the plurality of node devices on a route through which the reply message is received by the first node device from the AP.

27. The method of claim 26, wherein the selected route corresponds to a reply message having a smallest value in the first field.

28. The method of claim 27, wherein if the destination node device is one of the second node devices, the value in the first field is zero.

29. The method of claim 26, wherein the plurality of request messages is to be forwarded for a pre-defined number of hops.

30. An article of manufacture, comprising:

a tangible computer-readable medium having stored thereon, computer executable instructions that, if executed by a first node device of a plurality of node devices, cause the first node device to perform operations comprising;

determining, in response to receiving a beacon message from an access point (AP) that solicits joining a zone of the AP, if the AP is new by checking a list of APs of the first node device, wherein the AP is determined to be new if not included in the list; and

adding the AP to the list if the AP is determined to be new;

wherein;

the beacon message includes a value in a first field indicating a cost for the first node device to join the zone of the AP; and

the zone of the AP includes second node devices of the plurality of node devices and each of the second node devices has a default route to the AP through one or more hops.

31. The article of manufacture of claim 30, wherein the operations further comprise:

if the AP is determined to be new, checking the value in the first field of beacon message; and

determining whether to join the zone of the AP based at least in part on a result of said checking.

32. The article of manufacture of claim 31, wherein the AP has an initial cost value and each of the plurality of node devices has a corresponding cost value, and the value in the first field of the beacon message includes a sum of the initial cost value of the AP and cost value of third node devices of the plurality of node devices.

33. The article of manufacture of claim 32, wherein the initial cost value of the AP is indicative of at least in part on traffic load and a number of the second node devices in the zone of the AP.

34. The article of manufacture of claim 33, wherein the beacon message further includes a value in a second field indicating a number of hops that the beacon message is to be forwarded;

and

wherein the operations further comprise;

sending a reply message to join the zone of the AP if the value in the first field is smaller by a pre-defined amount than a cost for staying in a zone of another AP that the first node device is currently in;

updating the beacon message by adding the first node device'"'"'s own cost value to the value in the first field; and

forwarding the updated beacon message if the value in the second field is greater than zero.

35. The article of manufacture of claim 34, wherein the beacon message further includes a value in a third field indicating a sequence of the beacon message;

wherein the operations further comprise;

if said determining determines the AP is not new, checking the value in the third field;

based on a result of said checking, updating the list based on routing information of the AP contained in the beacon message;

forwarding the updated beacon message if the value in the second field is greater than zero.

36. The article of manufacture of claim 30, wherein the value in the first field is an indicator of power, stability, or residual bandwidth.

37. An apparatus, comprising:

a node device that includes;

a receiver configured to receive a beacon message, from an access point (AP), that solicits joining a zone of the AP;

a processor, coupled with the receiver, configured to;

determine if the AP is new by checking a list of APs of the node device, wherein the AP is new if not included in the list; and

add the AP to the list if the AP is determined to be new;

wherein;

the beacon message includes a value in a first field indicating a cost for the node device to join the zone of the AP; and

the zone of the AP includes a first group of node devices and each of the first group of node devices has a default route to the AP through one or more hops.

38. The apparatus of claim 37, wherein the processor is further configured to:

check the value in the first field of beacon message if the AP is new; and

determine whether the node device should join the zone of the AP based at least in part on the checked value.

39. The apparatus of claim 38, wherein the value in the first field of the beacon message includes a sum of an initial cost value of the AP and cost values of a second group of node devices located on a route via which the beacon message is received by the node device from the AP.

40. The apparatus of claim 39, wherein the initial cost value of the AP is indicative of at least in part on traffic load and a number of the first group of node devices in the zone of the AP.

41. The apparatus of claim 39, wherein the beacon message further includes a value in a second field indicating a number of hops that the beacon message is to be forwarded;

wherein the node device further comprises a transmitter, coupled with the processor, configured to send a reply message to join the zone of the AP if the value in the first field is smaller by a pre-defined amount than a cost to stay in a zone of another AP that the node device is currently in;

wherein the processor is further configured to update the beacon message to add the node device'"'"'s own cost value to the value in the first field of the beacon message; and

wherein the transmitter is further configured to forward the updated beacon message if the value in the second field is greater than zero.

42. The apparatus of claim 41, wherein the beacon message further includes a value in a third field indicating a sequence of the beacon message, wherein the processor is further configured to:

check the value in the third field;

based on a result of said check of the value in the third field, update the list based on routing information of the AP contained in the beacon message; and

forward the updated beacon message if the value in the second field is greater than zero.

43. An apparatus, comprising:

an access point (AP) device that includes;

a transmitter, configured to broadcast a beacon message to be forwarded among a plurality of node devices to solicit joining a zone of the AP device;

a receiver, configured to receive a reply message in response to the beacon message from a first node device of the plurality of node devices; and

a processor, coupled with the receiver and transmitter, configured to update a list of node devices in the zone of the AP device based on the reply message;

wherein the zone of the AP device includes second node devices of the plurality of node devices, and each of the second node devices has a default route to the AP device through one or more hops.

44. The apparatus of claim 43, wherein the beacon message includes a value in a first field indicating a cost to join the zone of the AP device, and the value in the first field is configured to be updated each time the beacon message is forwarded.

45. The apparatus of claim 43, wherein the AP device has an initial cost value and each of the plurality of node devices has a corresponding cost value, and the value in the first field of the beacon message includes a sum of the initial cost value of the AP device and cost values of third node devices of the plurality of node devices located on a route that the beacon message is forwarded.

46. The apparatus of claim 43, wherein AP device is configured to determine, from the reply message, about the first node device joining the zone of the AP device, or the AP device is configured to determine, from the reply message, updated routing information of the first node device if the first node device is already in the zone of the AP device.