Method for frequency sharing and frequency punchout in frequency hopping communications network

• US 5,515,369 A
• Filed: 06/24/1994
• Issued: 05/07/1996
• Est. Priority Date: 06/24/1994
• Status: Expired due to Term

• Current Assignee: Quarterhill Inc. (f/k/a Wi-LAN Inc.)
• Original Assignee: Metricom, Inc.
• Inventors: Galloway, Brett D., Paulsen, David L., Flammer, George H. III
• Primary Examiner(s): Marcelo, Melvin
• Assistant Examiner(s): VU, HUY DUY
• Application Number:
  US08/265,096
• Time in Patent Office: 683 Days
• Field of Search: 370/95.1, 370/95.2, 370/95.3, 370/69.1, 370/76, 370/70, 370/50, 370/94.1, 370/77, 370/18, 375/202, 375/200, 375/203, 375/208, 375/285, 455/61, 455/62, 455/63, 455/69, 455/70, 455/71, 455/138, 455/166.1
• US Class Current: 370/480
• CPC Class Codes: H04B 1/7143 Arrangements for generation of hop patterns
• CPC Class Codes: H04B 1/715 Interference-related aspects
• CPC Class Codes: H04B 2001/7154 with means for preventing interference
• CPC Class Codes: H04B 2001/71563 Acquisition
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 72/044 based on the type of the allocated resource
• CPC Class Codes: H04W 76/10 Connection setup

Abstract

In a wireless packet communication system having a plurality of nodes, each having a transmitter and a receiver, the receiver at each node is assigned a seed value and is provided with a channel punchout mask. A node uses its seed value and punchout mask to generate a specific randomly ordered channel hopping band plan on which to receive signals. A node transmits its seed value and punchout mask to target nodes with which it wants to establish communication links, and those target nodes each use the seed value and punchout mask to generate the randomly ordered channel hopping band plan for that node. Subsequently, when one of the target nodes wish to transmit to the node, the target node changes frequency to the frequency of the node according to that node'"'"'s band plan.

Claims

1. In a communications network having a plurality of channel-agile nodes each node capable of transmitting and receiving data over a plurality of shared channels, said shared channels having a first order, a method for enabling a first node and a second node to follow a shared randomized channel-hopping band plan for transmissions to said first node while avoiding channels containing interference, comprising the steps of:

a) assigning to each node a unique seed value that can be used by a pseudo-random number generator to generate a list of channels in pseudo-random order;

b) determining a channel punchout mask for each node, said channel mask indicating in said first order those channels on which that node experiences interference;

c) at said first node, applying said first node'"'"'s channel mask to a first ordered channel list to eliminate channels on which said first node experiences interference thereby deriving a masked channel list for said first node;

d) at said first node, determining a channel-hopping band plan for receiving transmissions to said first node by ordering the channels in said first node'"'"'s channel list according to a sequence generated by a pseudo-random number generator seeded with said first node'"'"'s seed value;

e) transmitting from said first node to said second node an acquisition packet, said acquisition packet including said first node'"'"'s seed value and said first node'"'"'s channel mask;

f) at said second node, applying said transmitted channel mask from said first node to said first ordered channel list to eliminate channels on which said first node experiences interference to obtain a masked channel list for said first node at said second node;

g) at said second node, determining a channel-hopping band plan for transmissions to said first node by ordering the channels in said first node'"'"'s channel list according to a sequence generated by a pseudo-random number generator seeded with said first node'"'"'s transmitted seed value; and

h) thereafter transmitting data to said first node from said second node according to said first node'"'"'s channel-hopping band plan.

2. The method according to claim 1 wherein said seed values are derived from the addresses of the nodes.

3. The method according to claim 1 wherein said mask is a sequence of bits, each bit having a value of either 0 or 1, where bits of one value correspond to channels in the channel list that are used by the node and bits of the other value correspond to channels in the channel list that are not used by the node and are therefore to be eliminated from the node'"'"'s channel-hopping band plan.

4. The method according to claim 1 further comprising:

i) storing at each node data from which to determine the masked channel hopping band plan of other nodes in the network to facilitate future data transfers.

5. In a node operable on a communications network having a plurality of shared-medium channels and having a plurality of channel-agile nodes each node capable of transmitting and receiving data over a plurality of said channels, a method for establishing a unique channel-hopping band plan for that node and communicating that band plan to other nodes in the network comprising the steps of:

a) assigning to that node a unique seed value;

b) determining a channel punchout mask, said mask indicating those channels on which the node experiences interference or is otherwise unable to receive data;

c) applying said mask to a list of network channels to eliminate undesirable channels and therefore to obtain a list of available node channels;

d) randomizing said list of available node channels by using a deterministic pseudorandom number generator seeded with said seed value thereby obtaining a unique channel-hopping band plan; and

e) communicating said unique channel-hopping band plan to other nodes in the network by transmitting data from which said other nodes may derive said unique channel-hopping band plan.

6. The method according to claim 5 wherein said seed value is derived from an address of the node.

7. The method according to claim 5 wherein said mask is a sequence of bits, each bit having a value of either 0 or 1, where bits of one value correspond to channels in the channel list that are used by the node and bits of the other value correspond to channels in the channel list that are not used by the node and are therefore to be eliminated from the node'"'"'s channel-hopping band plan.

9. The method according to claim 5 wherein said data from which said other nodes may derive said unique channel-hopping band plan comprises said unique seed value and said mask.

10. The method according to claim 5 wherein said data from which said other nodes may derive said unique channel-hopping band plan comprises an ordered list identifying said channel-hopping band plan.

8. A communications network comprising:

a shared medium with a plurality of channels; and

a plurality of intelligent channel-agile nodes wherein each node has the ability of either transmitting on a plurality of channels of said shared medium or receiving on a plurality of channels of said shared medium or both transmitting and receiving on a plurality of channels of said shared medium;

wherein each of said nodes capable of receiving is assigned a seed value and determines a frequency punchout mask for itself from which any node is capable of deriving a unique channel hopping band plan for that node and wherein said band plan is comprised of a random ordering of those network channels on which the node can receive data and wherein the band plans of different nodes in the same communications network are allowed to contain a different number of channels.