Creation and use of unique hopping sequences in a frequency-hopping spread spectrum (FHSS) wireless communications network

• US 20090168846A1
• Filed: 12/27/2007
• Published: 07/02/2009
• Est. Priority Date: 12/27/2007
• Status: Active Grant

• Current Assignee: Itron Networked Solutions, Inc. (Itron, Inc.)
• Original Assignee: Silver Spring Networks, Inc. (Itron, Inc.)
• Inventors: Filippo III, William San, Greunen, Jana Van, Hughes, Sterling, Vaswani, Raj
• Granted Patent: US 8,442,092 B2
• Time in Patent Office: Days
• US Class Current: 375/133
• CPC Class Codes: H04B 1/7143 Arrangements for generation of hop patterns
• CPC Class Codes: H04B 1/7156 Arrangements for sequence synchronisation

Abstract

A method for generating and using frequency-hopping sequences in frequency-hopping spread spectrum (FHSS) networks, such that no additional network overhead is required to convey a device'"'"'s hopping sequence to another device, is disclosed. Furthermore, a method to maximize the number of unique hopping sequences, without increasing the random access memory (RAM) requirements on the network devices, is disclosed.

Claims

1. A method for generating unique hopping sequences for nodes in a frequency-hopping spread spectrum (FHSS) network, comprising:

selecting a total number of hopping sequence channels;

creating a channel table for the network having the total number of hopping sequence channels;

generating, for a given node, a sequence start and a sequence seed based on a node identifier; and

performing a slot-to-channel conversion to identify a channel in the hopping sequence of the given node by generating a channel index into the channel table based on the sequence start and the sequence seed for the given node, and retrieving the channel from the channel table that corresponds to the channel index.

2. The method of claim 1, wherein the total number of channels is a prime number which is closest to but does not exceed a total number of possible channels for the network.

3. The method of claim 1, wherein the step of creating the channel table comprises:

creating the channel table such that its associated hopping sequences have on average a maximum channel separation per hop.

4. The method of claim 1, wherein the channel table is embedded in node memory.

5. The method of claim 1, wherein the node identifier includes a unique node identifier.

6. The method of claim 5, wherein the unique node identifier includes a media access control (MAC) address of the given node.

7. A method for determining a channel in a hopping sequence of a node in a frequency-hopping spread spectrum (FHSS) network, comprising:

determining the node'"'"'s current slot in the hopping sequence for a given transmission time based on a number of slots per epoch for the network, wherein the number of slots per epoch comprises a prime number and each slot in the epoch has an associated channel frequency;

converting the current slot to its associated channel frequency by using an identifier of the node to generate a channel index into a network channel table; and

transmitting a packet to the node on the associated channel frequency at the given transmission time.

8. The method of claim 7, wherein the step of determining the current slot comprises receiving an epoch tick from the node that establishes where the node is in its hopping sequence.

9. The method of claim 8, wherein the step of determining the current slot comprises:

calculating an epoch start time based on the epoch tick, and receive time of a frame in which the epoch tick was sent;

calculating a current tick in the epoch based on the given transmission time, the calculated epoch start time, and an epoch length, wherein the node dwells on each of the associated frequency channels in its hopping sequence for a slot length, and the epoch length equals the slot length times the number of slots per epoch; and

determining the current slot based on the calculated current tick in the epoch and based on the number of slots per epoch.

10. The method of claim 9, wherein the epoch tick comprises a fractional epoch tick (FET) that represents the epoch tick as a fraction of the epoch length.

11. The method of claim 9, wherein the step of determining the current slot comprises:

calculating a current tick in the current slot based on the calculated current tick in the epoch and based on the slot length.

12. The method of claim 11, further comprising:

determining, based on the calculated current tick in the slot, whether the node will receive enough of the transmitted packet in the current slot to sense reception of the transmitted packet.

13. The method of claim 12, wherein a next slot in the node'"'"'s hopping sequence is selected as the current slot when it is determined that the node will not receive enough of the transmitted packet in the current slot to sense reception of the transmitted packet.

14. The method of claim 7, wherein the step of converting the current slot comprises:

determining a hopping sequence start and a hopping sequence seed for the node based on the node identifier and generating the channel index based on the hopping sequence start and the hopping sequence seed.

15. The method of claim 14, wherein the node identifier includes a media access control (MAC) address.

16. The method of claim 8, wherein the epoch tick is received in response to a request for the epoch tick, during a discovery period when nodes in the network exchange their respective timing information with neighbor nodes, or when the node periodically broadcasts its timing information.

17. The method of claim 7, wherein each node in the network traverses the associated frequency channels in its respective hopping sequence in a pseudo-random manner with respect to other nodes in the network.

18. The method of claim 17, wherein the node stops traversing the associated frequency channels in its hopping sequence when receiving the transmitted packet.

19. The method of claim 18, wherein, following reception of the transmitted packet, the node resumes traversing its hopping sequence on the associated frequency channel to which the node would have traversed had the node not stopped traversing the associated frequency channels in its hopping sequence when receiving the transmitted packet.

20. A frequency-hopping spread spectrum (FHSS) network, comprising:

a first node having a hopping sequence; and

a second node having a packet to transmit to the first node, wherein the second node generates a sequence start and a sequence seed based on an identifier of the first node, performs a slot-to-channel conversion to identify a channel in the hopping sequence of the first node, and transmits the packet to the first node on the identified channel.

21. The network of claim 20, wherein the first node and the second node each has embedded in memory a network channel table having a total number of hopping sequence channels.

22. The network of claim 21, wherein the total number of hopping sequence channels is a prime number which is closest to but does not exceed a total number of possible channels for the network.

23. The network of claim 21, wherein, in performing the slot-to-channel conversion, the second node generates a channel index into the channel table based on the sequence start and the sequence seed for the first node and retrieves the identified channel from the channel table that corresponds to the generated channel index.

24. The network of claim 21, wherein the hopping sequences associated with the channel table have on average a maximum channel separation per hop.

25. The network of claim 21, wherein the identifier of the first node includes a unique node identifier.

26. The network of claim 25, wherein the unique identifier of the first node includes a media access control (MAC) address of the first node.

27. A frequency-hopping spread spectrum (FHSS) network, comprising:

a first node having a hopping sequence with a number of slots per epoch, wherein the number of slots per epoch comprises a prime number and each slot in the epoch has an associated channel frequency; and

a second node having a packet to transmit to the first node at a given transmission time, wherein the second node determines the first node'"'"'s current slot in the hopping sequence for the given transmission time based on the number of slots per epoch, converts the current slot to its associated channel frequency by using an identifier of the first node to generate a channel index into a network channel table, and transmits the packet to the first node on the associated channel frequency at the given transmission time.

28. The network of claim 27, wherein the first node transmits to the second node an epoch tick that establishes where the first node is in its hopping sequence.

29. The network of claim 28, wherein the second node calculates an epoch start time based on the epoch tick, and the receive time of a frame in which the epoch tick was sent;

calculates a current tick in the epoch based on the given transmission time, the calculated epoch start time, and an epoch length; and

determines the current slot based on the calculated current tick in the epoch and based on the number of slots per epoch, and

wherein the first node dwells on each of the associated frequency channels in its hopping sequence for a slot length, and the epoch length comprises the slot length times the number of slots per epoch.

30. The network of claim 29, wherein the epoch tick includes a fractional epoch tick (FET) that represents the epoch tick as a fraction of the epoch length.

31. The network of claim 29, wherein the second node calculates a current tick in the current slot based on the calculated current tick in the epoch and based on the slot length.

32. The network of claim 31, wherein the second node determines, based on the calculated current tick in the current slot, whether the first node will receive enough of the transmitted packet in the current slot to sense reception of the transmitted packet.

33. The network of claim 32, wherein the second node selects a next slot in the first node'"'"'s hopping sequence as the current slot when the second node determines that the first node will not receive enough of the transmitted packet in the current slot to sense reception of the transmitted packet.

34. The network of claim 27, wherein the second node generates the channel index based on a hopping sequence start and a hopping sequence seed, which are determined based on the identifier of the first node.

35. The network of claim 34, wherein the identifier includes a media access control (MAC) address.

36. The network of claim 28, wherein the second node receives the epoch tick in response to a request for the epoch tick, during a discovery period when nodes in the network exchange their respective timing information with neighbor nodes, or when the first node periodically broadcasts its timing information.

37. The network of claim 27, wherein each node in the network traverses the associated frequency channels in its respective hopping sequence in a pseudo-random manner with respect to other nodes in the network.

38. The network of claim 37, wherein the first node stops traversing the associated frequency channels in its hopping sequence when receiving the transmitted packet at the given transmission time.

39. The network of claim 38, wherein, following reception of the transmitted packet, the first node resumes traversing its hopping sequence on the associated frequency channel to which the first node would have traversed had the first node not stopped traversing the associated frequency channels in its hopping sequence when receiving the transmitted packet.