Simplified auto-configuration and service discovery in ad-hoc networks

• US 7,848,263 B2
• Filed: 11/26/2007
• Issued: 12/07/2010
• Est. Priority Date: 11/28/2006
• Status: Expired due to Fees

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Chhabra, Kapil
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): Morlan; Robert M
• Application Number:
  US11/944,980
• Publication Number:
  US 20080123558A1
• Time in Patent Office: 1,107 Days
• Field of Search: 370/254, 370/255, 370/395.3
• US Class Current: 370/255
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 41/0803 Configuration setting
• CPC Class Codes: H04L 41/0886 Fully automatic configuration
• CPC Class Codes: H04L 61/5007 Internet protocol [IP] addresses
• CPC Class Codes: H04L 61/5084 Providing for device mobility network addressing or numbering for mobility support in wireless networks H04W8/26; mobile IP H04W80/04
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 76/11 Allocation or use of connection identifiers
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/02 Terminal devices

Abstract

An ad-hoc network approach for addressing ad-hoc network address assignment, name resolution, and service discovery in ad-hoc networks. The size of the ad-hoc network may be limited to a selected number of ad-hoc network stations. A first portion of the ad-hoc network address assigned to stations joining the ad-hoc network may be fixed and a second portion of the ad-hoc network address may be selected dynamically, as each new station joins the ad-hoc network. A station may generate an information element that may be included in ad-hoc network messages. An exemplary information element may include a last byte of the ad-hoc network address associated with the transmitting station, a 4-byte timestamp field which indicates a number of milliseconds since the station claimed the network address, a user-friendly name to identify the station, a universally unique identifier (UUID) for each service offered by the transmitting station, and a network-address-in-use bitmap.

Claims

1. A method performed by a local station to configure the local station to communicate with one or more peer stations, the method comprising:

retrieving, from a memory of the local station, a local station network address first portion, the local station network address first portion configured to be identical for the local station and a peer station joining dynamically to form an ad-hoc network;

receiving a message from the peer station;

parsing the received message to retrieve a peer station information element, the peer station information element including a peer station bitmap that indicates at least one of allocated and unallocated network addresses within a predetermined set of network addresses; and

changing dynamically a local station network address second portion by selecting the location station network address second portion corresponding to one of the predetermined set of network addresses indicated as unallocated in the peer station bitmap.

2. The method of claim 1, further comprising:

storing the peer station bitmap in association with the peer station.

3. The method of claim 1, further comprising:

generating a timestamp with information related to a time at which the local station network address second portion was allocated by the local station.

4. The method of claim 3, wherein the peer station information element further includes:

a peer station network address second portion allocated by the peer station; and

a timestamp with information related to a time at which the peer station network address second portion was allocated by the peer station.

5. The method of claim 4, further comprising:

receiving at the local station a message from a peer station after the local station has selected the local station network address second portion;

comparing the peer station network address second portion allocated by the peer station to the local station network address second portion allocated by the local station;

determining that the peer station network address second portion is a same as the local station network address second portion;

determining if the peer station network address second portion was allocated by the peer station before the local station network address second portion was allocated by the local station; and

re-selecting a local station network address second portion for the local station corresponding to a network address indicated as unallocated in the peer station bitmap if the peer station network address second portion was allocated by the peer station before the local station network address second portion was allocated by the local station.

6. The method of claim 5, wherein determining if the peer station network address second portion was allocated by the peer station before the local station network address second portion was allocated by the local station is based on a comparison of the timestamp received from the peer station and the timestamp generated by the local station.

7. The method of claim 1, further comprising:

generating and transmitting a message containing a local station information element, the local station information element including the local station network address second portion selected by the local station and a timestamp with information related to a time at which the local station network address second portion was allocated by the local station.

8. The method of claim 7, further comprising:

generating a local station bitmap that indicates at least one of allocated and unallocated network addresses within the set of network addresses; and

including the generated local station bitmap in the local station information element included in the transmitted message.

9. The method of claim 8, wherein the generated local station bitmap is based on information included in peer station bitmaps received from the one or more peer stations.

10. The method of claim 8, further comprising:

compressing the generated local station bitmap prior to its inclusion in the local station information element.

11. The method of claim 7, further comprising:

reducing a beacon contention window for a predetermined number of target beacon transmission times.

12. The method of claim 7, wherein the local station information element within the transmitted message further includes:

an identifier that identifies a service provided by the local station.

13. The method of claim 12, wherein the identifier for the service is a universally unique identifier.

14. The method of claim 1, wherein the peer station information element within the received message further includes:

an identifier that identifies a service provided by the peer station.

15. The method of claim 14, wherein the identifier for the service is a universally unique identifier.

16. The method of claim 14, further comprising:

storing the identifier for the service in a data store in association with the peer station.

17. The method of claim 16, wherein information received from the peer station and stored in the data store is identified with a media access control address of the peer station.

18. The method of claim 16, wherein information received from the peer station and stored in the data store is deleted if a subsequent message is not received from a same peer station within a predetermined period of time.

19. A method of performing auto-configuration and service discovery, comprising:

retrieving, from a memory of a local station, a local station network address first portion, the local station network address first portion configured to be identical for the local station and a peer station joining dynamically to form an ad-hoc network;

receiving at the local station a message from the peer station;

parsing the message to retrieve an incoming peer station information element, the peer station information element including;

a peer station network address second portion allocated by the peer station;

a timestamp with information indicating a time at which the peer station network address second portion was allocated by the peer station;

an identifier representing a service provided by the peer station; and

a peer station bitmap that indicates at least one of allocated and unallocated network addresses within a predetermined set of network addresses;

storing information received in the message in a data store of the local station in association with the peer station;

parsing the data store of the local station on a periodic basis to collect information for use in generating a message for transmission, the generated message including an outgoing local station information element, the outgoing local station information element including;

a local station network address second portion dynamically allocated by the local station, the local station network address second portion corresponding to one of the predetermined set of network addresses indicated as unallocated in the peer station bitmap;

a timestamp with information indicating a time at which the local station network address second portion was allocated by the local station;

an identifier representing a service provided by the local station; and

a local station bitmap that indicates at least one of allocated and unallocated network addresses within the set of network addresses; and

transmitting the generated message from the local station.

20. The method of claim 19, wherein the data store of the local station is parsed and the local station bitmap included in the outgoing local station information element is generated at a time identified by a target beacon transmission time minus a predetermined period of time.

21. The method of claim 20, wherein the generated message is transmitted at a time identified by a target beacon transmission time plus a random delay generated by the local station.

22. The method of claim 21, wherein the random delay is generated to be less than a beacon contention window.

23. The method of claim 22, wherein the beacon contention window is dynamically configurable, and a new random delay is determined in response to a change in the beacon contention window.

24. The method of claim 23, wherein the beacon contention window of the local station is reduced prior to transmitting a probe-request message requesting information from a peer station in the ad-hoc network.

25. The method of claim 24, wherein the beacon contention window of the local station is restored to a predetermined beacon contention window duration after a predetermined number of target beacon transmission time periods.

26. The method of claim 23, wherein the beacon contention window of the local station is reduced prior to transmitting a message generated to announce the local station network address second portion allocated by the local station.

27. The method of claim 26, wherein the beacon contention window of the local station is restored to a predetermined beacon contention window duration after a predetermined number of target beacon transmission time periods.

28. The method of claim 19, wherein the set of network addresses is limited to 256 or less network addresses.

29. A local station that communicates with one or more peer stations, comprising:

a controller that controls communication via an ad-hoc network, the controller retrieving from a memory a local station network address first portion allocated to the local station, the local station network address first portion configured to be identical for the local station and a peer station joining dynamically to form the ad-hoc network;

a physical network unit that receives a message from the peer station; and

a message parsing unit that parses the message to retrieve a peer station information element, the peer station information element including a peer station bitmap that indicates at least one of allocated and unallocated network addresses within a predetermined set of network addresses,

wherein the controller changes dynamically a local station network address second portion by selecting the local station network address second portion corresponding to one of the predetermined set of network addresses indicated as unallocated in the peer station bitmap.

30. The local station of claim 29, further comprising:

a data store unit that stores the peer station bitmap in a data store in association with the peer station.

31. The local station of claim 30, wherein information received from a peer station and stored in the data store is deleted if a subsequent message is not received from a same peer station within a predetermined period of time.

32. The local station of claim 30, wherein information received from a peer station and stored in the data store is identified with an identifier associated with the peer station.

33. The local station of claim 32, wherein the identifier is a media access control address of the peer station.

34. The local station of claim 29, further comprising:

a clock control unit that generates a timestamp with information related to a time at which the local station network address second portion was allocated by the local station.

35. The local station of claim 34, further comprising:

a message generating unit that generates a message containing a local station information element, the local station information element including the local station network address second portion selected by the local station and the timestamp with information related to the time at which the local station allocated the local station network address second portion.

36. The local station of claim 35, further comprising:

a bitmap generator that generates a local station bitmap that indicates at least one of allocated and unallocated network addresses within the set of network addresses based on information contained in the peer station bitmap in the received message,

wherein the generated local station bitmap is included in the local station information element included in the generated message.

37. The local station of claim 36, wherein the bitmap generator further comprises:

a compression unit that compresses the generated local station bitmap.

38. The local station of claim 35, wherein the clock control unit further comprises:

a beacon contention window adjustment module that reduces a beacon contention window of the local station for a predetermined number of target beacon transmission times.

39. The local station of claim 35, wherein the local station information element further includes:

an identifier that identifies a service provided by the local station.

40. The local station of claim 39, wherein the identifier for the service is a universally unique identifier.

41. The local station of claim 29, wherein the message parsing unit is configured to receive a peer station information element that further includes:

a peer station network address second portion allocated by the peer station; and

a timestamp with information related to a time at which the peer station network address second portion was allocated by the peer station.

42. The local station of claim 41, wherein on determining that the peer station network address second portion included in the message from the peer station matches the local station network address second portion allocated by the local station, and determining that the peer station network address second portion was allocated by the peer station before the local station network address second portion was allocated by the local station, the controller re-selects a local station network address second portion for the local station corresponding to a network address indicated as unallocated in the peer station bitmap.

43. The local station of claim 42, wherein the controller determines that the peer station network address second portion was allocated by the peer station before the local station network address second portion was allocated by the local station based on a comparison of the timestamp received from the peer station and the timestamp generated by the local station.

44. The local station of claim 29, wherein the peer station information element included in the received message further includes:

an identifier that identifies a service provided by the peer station.

45. The local station of claim 44, wherein the identifier for the service is a universally unique identifier.

46. The local station of claim 45, wherein the identifier for the service is stored in a data store in association with the peer station.

47. The local station of claim 29, wherein the local station is one of a portable computing device, a fixed location computing device, a input device, an output device, a connectivity providing device, an information service device, and an appliance.

48. An ad-hoc network that supports auto-configuration and service discovery, wherein a local station within the ad-hoc network comprises:

a memory unit that stores a local station network address first portion, the local station network address first portion configured to be identical for the local station and a peer station joining dynamically to form the ad-hoc network;

a physical network unit that receives at the local station a message from the peer station;

a message parsing unit that parses the message to retrieve an incoming peer station information element, the peer station information element including;

a peer station network address second portion allocated by the peer station;

a timestamp with information indicating a time at which the peer station network address second portion was allocated by the peer station;

an identifier representing a service provided by the peer station; and

a peer station bitmap that indicates at least one of allocated and unallocated network addresses within a predetermined set of network addresses;

a data store unit that stores information included in the message in a data store in association with the peer station; and

a controller that parses the data store on a periodic basis to collect information for use in generating a message for transmission, the generated message including an outgoing local station information element, the outgoing local station information element including;

a local station network address second portion dynamically allocated by the local station, the local station network address second portion corresponding to one of the predetermined set of network addresses indicated as unallocated in the peer station bitmap;

a timestamp with information indicating a time at which the local station network address second portion was allocated by the local station;

an identifier representing a service provided by the local station; and

a local station bitmap that indicates at least one of allocated and unallocated network addresses within the set of network addresses,

wherein the physical network unit transmits the generated message from the local station.

49. The ad-hoc network of claim 48, the local station further comprising:

a bitmap generator that generates the local station bitmap; and

a clock control unit that notifies the controller at a target beacon transmission time minus a first predetermined period of time, and notifies the controller at a target beacon transmission time plus a random delay generated by the local station; and

a message generator,

wherein at the target beacon transmission time minus the first predetermined period of time, the bitmap generator parses the data store and generates the local station bitmap, the generated local station bitmap being included in a message generated by the message generator.

50. The ad-hoc network of claim 49, wherein the physical network unit of the local station transmits the generated message at a time identified by a target beacon transmission time plus the random delay generated by the local station.

51. The ad-hoc network of claim 50, wherein the random delay of the local station is generated to be less than a beacon contention window of the local station.

52. The ad-hoc network of claim 51, wherein the beacon contention window of the local station is dynamically configurable by the clock control unit, and a new random delay of the local station is determined by the clock control unit of the local station in response to a change in the beacon contention window.

53. The ad-hoc network of claim 52, wherein the clock control unit of the local station reduces the beacon contention window of the local station prior to transmitting a probe-request message requesting information from a peer station in the ad-hoc network.

54. The ad-hoc network of claim 53, wherein the clock control unit of the local station restores the beacon contention window of the local station to a predetermined beacon contention window duration after a predetermined number of target beacon transmission time periods.

55. The ad-hoc network of claim 52, wherein the clock control unit of the local station reduces the beacon contention window of the local station prior to transmitting a message generated to announce the second portion of a new network address allocated by the local station.

56. The ad-hoc network of claim 55, wherein the clock control unit of the local station restores the beacon contention window of the local station to a predetermined beacon contention window duration after a predetermined number of target beacon transmission time periods.

57. The ad-hoc network of claim 48, wherein the set of network addresses is limited to 256 or less network addresses.

58. The ad-hoc network of claim 48, wherein the local station is one of a portable computing device, a fixed location computing device, an input device, an output device, a connectivity providing device, an information service device, and an appliance.