Dynamic hopping sequence computation in channel hopping communication networks

• US 8,948,229 B2
• Filed: 10/13/2011
• Issued: 02/03/2015
• Est. Priority Date: 10/13/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Vasseur, Jean-Philippe
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Ambaye, Mewale
• Application Number:
  US13/272,932
• Publication Number:
  US 20130094537A1
• Time in Patent Office: 1,209 Days
• Field of Search: 370/329
• US Class Current: 375/134
• CPC Class Codes: H04B 1/713 using frequency hopping
• CPC Class Codes: H04B 1/7143 Arrangements for generation of hop patterns
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 48/18 Selecting a network or a communication service

Abstract

In one embodiment, a device in a channel hopping communication network independently maintains a slot counter, and computes a channel identification (ID) based on a function having inputs of i) a unique feature of the device, ii) a current slot of the slot counter, and iii) a set of possible channel IDs. Accordingly, the device configures its radio to receive on the computed channel ID for the respective current slot. In another embodiment, the device may determine, for a neighbor device, a current neighbor slot and unique neighbor feature, and correspondingly computes a neighbor channel ID based on the function using the unique neighbor feature, the current neighbor slot, and the set of possible channel IDs. As such, the device configures its radio to transmit on the computed neighbor channel ID for the respective current neighbor slot.

Claims

1. A method for dynamically computing a channel hopping sequence in a channel hopping communication network, comprising:

providing the channel hopping communication network including a plurality of devices that serve as receivers, each device configured to compute the channel hopping sequence;

independently maintaining a slot counter at each device of the plurality of devices in the channel hopping communication network;

computing, by each device of the plurality of devices, a channel identification (ID) based on a function having inputs of i) a unique feature of the device, ii) a current slot of the slot counter, and iii) a set of possible channel IDs, so as to compute the channel hopping sequence; and

configuring, by each device of the plurality of devices, a radio of the device to receive on the computed channel ID for the respective current slot.

2. The method as in claim 1, wherein the unique feature is a media access control (MAC) address of the device.

3. The method as in claim 1, wherein the function is a hash function.

4. The method as in claim 3, wherein the hash function is a cryptographic hash function.

5. The method as in claim 1, further comprising:

determining, for a neighbor device, a current neighbor slot and unique neighbor feature;

computing a neighbor channel ID based on the function using the unique neighbor feature, the current neighbor slot, and the set of possible channel IDs; and

configuring the radio of the device to transmit on the computed neighbor channel ID for the respective current neighbor slot.

6. The method as in claim 1, further comprising:

dynamically selecting the function based on one or more network characteristics.

7. The method as in claim 6, wherein the network characteristics are selected from a group consisting of:

an amount of computation for the channel ID;

an amount of traffic;

an amount of memory; and

a channel hopping sequence quality.

8. The method as in claim 6, wherein the network characteristics comprise a manual command.

9. The method as in claim 6, wherein selecting is based on at least one of either local determination or centralized global determination.

10. A method for dynamically computing a channel hopping sequence in a channel hopping communication network, comprising:

providing the channel hopping communication work including a plurality of devices that serve as receivers, each device configured to compute the channel hopping sequence;

determining, by each device of the plurality of devices in the channel hopping communication network, a current neighbor slot of a slot counter and unique neighbor feature for a particular neighbor device;

computing, by each device of the plurality of devices, a neighbor channel identification (ID) based on a function having inputs of i) the unique neighbor feature, ii) the current neighbor slot, and iii) a set of possible channel IDs, so as to compute the channel hopping sequence; and

configuring, by each device of the plurality of devices, a radio of the device to transmit on the computed neighbor channel ID for the respective current neighbor slot.

11. The method as in claim 10, wherein the unique neighbor feature is a media access control (MAC) address of the neighbor device.

12. The method as in claim 10, wherein the function is a hash function.

13. The method as in claim 10, further comprising:

determining a current slot time for the neighbor device; and

transmitting based on the current slot time.

14. An apparatus for dynamically computing a channel hopping sequence in a channel hopping communication network, comprising:

a processor adapted to execute one or more processes;

a plurality of transceivers provided in the channel hopping communication network, each transceiver configured to compute the channel hopping sequence;

each transceiver of the plurality of transceivers configured to communicate in the channel hopping communication network; and

a memory configured to store a process executable by the processor, the process when executed operable to;

independently maintain a slot counter at each transceiver of the plurality of transceivers;

compute, by each transceiver of the plurality of transceivers, a channel identification (ID) based on a function having inputs of i) a unique feature of the apparatus, ii) a current slot of the slot counter, and iii) a set of possible channel IDs, so as to compute the channel hopping sequence; and

configure, by each transceiver of the plurality of transceivers, the transceiver to receive on the computed channel ID for the respective current slot.

15. The apparatus as in claim 14, wherein the unique feature is a media access control (MAC) address of the apparatus.

16. The apparatus as in claim 14, wherein the function is a hash function.

17. The apparatus as in claim 14, wherein the process when executed is further operable to:

determine, for a neighbor device, a current neighbor slot and unique neighbor feature;

compute a neighbor channel ID based on the function using the unique neighbor feature, the current neighbor slot, and the set of possible channel IDs; and

configure the transceiver to transmit on the computed neighbor channel ID for the respective current neighbor slot.

18. The apparatus as in claim 14, wherein the process when executed is further operable to:

dynamically select the function based on one or more network characteristics.

19. A tangible, non-transitory, computer-readable medium having software encoded thereon that is configured to dynamically compute a channel hopping sequence in a channel hopping communication network, the software when executed by a processor operable to:

provide the channel hopping communication network including a plurality of devices that serve as receivers, each device configured to compute the channel hopping sequence;

independently maintain a slot counter at each device of the plurality of devices in the channel hopping communication network;

compute, by each device of the plurality of devices, a channel identification (ID) based on a function having inputs of i) a unique feature of the device, ii) a current slot of the slot counter, and iii) a set of possible channel IDs, so as to compute the channel hopping sequence; and

configure, by each device of the plurality of devices, a radio of the device to receive on the computed channel ID for the respective current slot.

20. The tangible, non-transitory computer-readable medium as in claim 19, wherein the unique feature is a media access control (MAC) address of the device, and wherein the function is a hash function.

21. The tangible, non-transitory computer-readable medium as in claim 19, wherein the software when executed is further operable to:

determine, for a neighbor device, a current neighbor slot and unique neighbor feature;

compute a neighbor channel ID based on the function using the unique neighbor feature, the current neighbor slot, and the set of possible channel IDs; and

configure the radio of the device to transmit on the computed neighbor channel ID for the respective current neighbor slot.