Slotted seeded channel hopping for capacity improvement in wireless networks

• US 7,379,447 B2
• Filed: 09/23/2004
• Issued: 05/27/2008
• Est. Priority Date: 05/02/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bahl, Paramvir, Chandra, Ranveer, Dunagan, John D.
• Primary Examiner(s): Corsaro; Nick
• Assistant Examiner(s): Lai; Daniel
• Application Number:
  US10/947,838
• Publication Number:
  US 20050063328A1
• Time in Patent Office: 1,342 Days
• Field of Search: 375/132, 455/41, 455/41.1, 455/41.2, 370/324, 370/350, 370/349, 370/436, 370/437, 370/338, 370/329
• US Class Current: 370/350
• CPC Class Codes: H04B 1/713 using frequency hopping
• CPC Class Codes: H04W 48/18 Selecting a network or a communication service
• CPC Class Codes: H04W 8/22 Processing or transfer of terminal data, e.g. status or physical capabilities
• CPC Class Codes: H04W 8/245 from a network towards a terminal
• CPC Class Codes: H04W 88/06 adapted for operation in multiple networks or having at least two operational modes, e.g. multi-mode terminals

Abstract

A system and method that increases the capacity of a wireless network using frequency diversity. A user switches between channels of a network using a single network interface card in such a manner that nodes desiring to communicate overlap while disjoint communications mostly do not overlap. A driver is inserted into a device'"'"'s networking stack and controls the network interface card using a plurality of virtual wireless network adapters. Packets for a recipient are queued when the recipient is not accessible on the node'"'"'s channel. In one embodiment where multiple nodes are switching in and out of channel, the method changes part of a nodes channel hopping schedule to ensure concurrent connectivity in a channel for at least a brief time period such that packets can be received/transmitted with desired nodes.

Claims

1. A method to transmit and receive packets in a node switching between a plurality of slots in a wireless network having a plurality of channels without requiring multiple radios, the method comprising the steps of:

determining a channel hopping schedule such that the channel hopping schedule overlaps with at least one other node for which the node has a packet to send, the channel hopping schedule having a schedule for each slot;

broadcasting the channel hopping schedule;

switching the node to a channel specified for a current slot of the plurality of slots;

switching the node from the channel in the current slot to a channel specified for a next slot in the channel hopping schedule;

repeating the step of switching the node from the channel in the current slot to a channel specified for a next slot in the channel hopping schedule until the channel hopping schedule for each slot has been completed;

incrementing each of the channels in the channel hopping schedule; and

if the node is switched to a channel in which the at least one other node is presently active, sending the packet to the at least one other node.

2. The method of claim 1 wherein the step of incrementing each of the channels in the channel hopping schedule comprises the step of incrementing each of the channels in the channel hopping schedule using addition modulo of a prime integer.

3. The method of claim 1 further comprising the step of delaying the step of switching the node from the channel in the current slot to a channel specified for a next slot in the channel hopping schedule if the node is one of transmitting and receiving a packet.

4. The method of claim 1 wherein the channel hopping schedule for each slot comprises a (channel, seed) pair.

5. The method of claim 4 wherein the step of incrementing each of the channels in the channel hopping schedule comprises the step of incrementing each of the channels in each slot using the seed according to the equation

x_new←

(x_old+seed)mod primenumber

where x_old is the current channel of the slot, x_new is the new channel of the slot, and primenumber is a predetermined prime number.

6. The method of claim 5 wherein the predetermined prime number is the number of channels in the plurality of channels if the number of channels is a prime number.

7. The method of claim 5 wherein the predetermined prime number is a prime number higher than the number of channels in the plurality of channels if the number of channels is not a prime number.

8. The method of claim 7 further comprising the step of mapping down using a modulus to the actual number of channels in the plurality of channels.

9. The method of claim 1 further comprising the step of switching to a parity slot.

10. The method of claim 1 further comprising the step of changing a portion of the channel hopping schedule if the node does not have an overlap with a recipient node for which the node has packets to send.

11. The method of claim 10 wherein the step of changing a portion of the channel hopping schedule if the node does not have an overlap with the recipient node comprises the steps of:

determining if there is a non-receiving slot; and

if there is at least one non-receiving slot, changing a (channel, seed) pair of the at least one non-receiving slot to overlap with the nodes for which the node has packets to send such that there is overlap.

12. The method of claim 11 wherein the step of determining if there is a non-receiving slot comprises the steps of:

maintaining a count of packets received for each slot duration for the number of packets received during the previous time a channel was active;

if any slot has not received more than a predetermined number of packets, identifying that slot as a non-receiving slot.

13. The method of claim 1 further comprising the step of de-synchronizing a slot if a number of other nodes synchronized to the same (channel, seed) pair of the slot is more than twice as many nodes as the node communicated with in the previous occurrence of the slot.

14. The method of claim 13 wherein the step of desynchronizing comprises the step of selecting a new (channel, seed) pair for the slot.

15. The method of claim 1 wherein the step of broadcasting the channel hopping schedule comprises the step of broadcasting the channel hopping schedule in an IEEE 802.11 long control frame header format.

16. The method of claim 15 wherein the step of broadcasting the channel hopping schedule in an IEEE 802.11 long control frame header format comprises the step of using unused bytes to embed (channel, seed) pairs and an offset.

17. The method of claim 1 further comprising the step of attempting to transmit packets to the at least one other node at the beginning of a slot in a round-robin manner among all flows.

18. The method of claim 17 further comprising the step of reducing priority of a flow to a particular node if packet transmission to the particular node fails.

19. The method of claim 18 wherein the step of reducing priority of the flow to the particular node comprises the step of reducing priority of the flow until a period of time equal to one half of a slot duration has passed.

20. The method of claim 18 further comprising the step of dropping an entire flow of packets to the at least one other node if attempts to transmit a packet to the at least one other node have failed for an entire cycle through the channel hopping schedule.

21. A tangible computer-readable medium having stored thereon computer-executable instructions for performing a method to transmit and receive packets in a node switching between a plurality of slots in a wireless network having a plurality of channels without requiring multiple radios, the method comprising the steps of:

determining a channel hopping schedule such that the channel hopping schedule overlaps with at least one other node for which the node has a packet to send, the channel hopping schedule having a schedule for each slot;

broadcasting the channel hopping schedule;

switching the node to a channel specified for a current slot of the plurality of slots;

switching the node from the channel in the current slot to a channel specified for a next slot in the channel hopping schedule;

repeating the step of switching the node from the channel in the current slot to a channel specified for a next slot in the channel hopping schedule until the channel hopping schedule for each slot has been completed;

incrementing each of the channels in the channel hopping schedule; and

if the node is switched to a channel in which the at least one other node is presently active, sending the packet to the at least one other node.

22. The tangible computer-readable medium of claim 21 having further computer executable instructions for performing the steps comprising delaying the step of switching the node from the channel in the previous slot to a channel specified for a next slot in the channel hopping schedule if the node is one of transmitting and receiving a packet.

23. The tangible computer-readable medium of claim 21 wherein the channel hopping schedule for each slot comprises a (channel, seed) pair.

24. The tangible computer-readable medium of claim 23 wherein the step of incrementing each of the channels in the channel hopping schedule comprises the step of incrementing each of the channels in each slot using the seed according to the equation

x_new←

(x_old+seed)mod primenumber

where x_old is the current channel of the slot, x_new is the new channel of the slot, and primenumber is a predetermined prime number.

25. The tangible computer-readable medium of claim 24 wherein the predetermined prime number is the number of channels in the plurality of channels if the number of channels is a prime number.

26. The tangible computer-readable medium of claim 24 wherein the predetermined prime number is a prime number higher than the number of channels in the plurality of channels if the number of channels is not a prime number, the at least one computer-readable medium having further computer executable instructions for performing the step comprising mapping down using a modulus to the actual number of channels in the plurality of channels.

27. The tangible computer-readable medium of claim 21 further comprising the step of switching to a parity slot.

28. The tangible computer-readable medium of claim 21 further comprising the step of changing a portion of the channel hopping schedule if the node does not have an overlap with a recipient node for which the node has packets to send.

29. The tangible computer-readable medium of claim 28 wherein the step of changing a portion of the channel hopping schedule if the node does not have an overlap with the recipient node comprises the steps of:

determining if there is a non-receiving slot; and

if there is at least one non-receiving slot, changing a (channel, seed) pair of the at least one non-receiving slot to overlap with the nodes for which the node has packets to send such that there is overlap.

30. The tangible computer-readable medium of claim 29 wherein the step of determining if there is a non-receiving slot comprises the steps of:

maintaining a count of packets received for each slot duration for the number of packets received during the previous time a channel was active;

if any slot has not received more than a predetermined number of packets, identifying that slot as a non-receiving slot.

31. The tangible computer-readable medium of claim 21 further comprising the step of de-synchronizing a slot if a number of other nodes synchronized to the same (channel, seed) pair of the slot is more than twice as many nodes as the node communicated with in the previous occurrence of the slot.

32. The tangible computer-readable medium of claim 31 wherein the step of desynchronizing comprises the step of selecting a new (channel, seed) pair for the slot.

33. The tangible computer-readable medium of claim 21 wherein the step of broadcasting the channel hopping schedule comprises the step of broadcasting the channel hopping schedule in an IEEE 802.11 long control frame header format.

34. The tangible computer-readable medium of claim 26 having further computer executable instructions for performing the step comprising attempting to transmit packets to the at least one other node at the beginning of a slot in a round robin manner among all flows.

35. The tangible computer-readable medium of claim 34 having further computer executable instructions for performing the step comprising reducing priority of a flow to a particular node if packet transmission to the particular node fails.

36. The tangible computer-readable medium of claim 35 wherein the step of reducing priority of the flow to the particular node comprises the step of reducing priority of the flow until a period of time equal to one half of a slot duration has passed.

37. The tangible computer-readable medium of claim 35 having further computer executable instructions for performing the step comprising dropping an entire flow of packets to the at least one other node if attempts to transmit a packet to the at least one other node have failed for an entire cycle through the channel hopping schedule.