Slotted seeded channel hopping for capacity improvement in wireless networks

• US 20050063328A1
• Filed: 09/23/2004
• Published: 03/24/2005
• Est. Priority Date: 05/02/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bahl, Paramvir, Chandra, Ranveer, Dunagan, John D.
• Granted Patent: US 7,379,447 B2
• Time in Patent Office: Days
• US Class Current: 370/324
• 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 partially synchronize a wireless node having a single wireless card participating in a network having a plurality of channels to an other node in the network comprising the steps of:

receiving a channel hopping schedule for at least one slot of the other node;

determining from the channel hopping schedule if at least one slot of the other node overlaps with the wireless node'"'"'s channel hopping schedule; and

changing the wireless node'"'"'s channel hopping schedule to overlap with one of the at least one slot of the other node if there is no overlap.

2. The method of claim 1 wherein the step of receiving a channel hopping schedule of the other node comprises the step of receiving a (channel, seed) pair for each of the at least one slot wherein the channel is a current channel of the at least one slot of the other node and the seed is a rule for updating the channel.

3. The method of claim 1 wherein the wireless node switches between the plurality of channels for a slot duration and wherein the step of changing the wireless node'"'"'s channel hopping schedule comprises the steps of:

determining if there is a non-receiving slot; and

if there is a non-receiving slot, changing a (channel, seed) pair of the non-receiving slot to overlap with the one of the at least one slot of the other node such that there is overlap.

4. The method of claim 3 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.

5. The method of claim 3 further comprising the step of changing a (channel, seed) pair of any slot if there are no non-receiving slots.

6. 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 previous slot of the plurality of slots;

switching the node from the channel in the previous 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 previous 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.

7. The method of claim 6 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.

8. The method of claim 6 further comprising the step of 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.

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

10. The method of claim 9 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.

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

12. The method of claim 10 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.

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

14. The method of claim 6 further comprising the step of switching to a parity slot.

15. The method of claim 6 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.

16. The method of claim 15 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 leas one non-receiving slot to overlap with the nodes for which the node has packets to send such that there is overlap.

17. The method of claim 16 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.

18. The method of claim 6 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.

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

20. The method of claim 6 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.

21. The method of claim 20 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.

22. The method of claim 6 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.

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

24. The method of claim 23 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.

25. The method of claim 23 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.

26. At least one computer-readable medium having computer-executable instructions for performing the steps of claim 6.

27. The at least one computer-readable medium of claim 26 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.

28. The at least one computer-readable medium of claim 26 wherein the channel hopping schedule for each slot comprises a (channel, seed) pair.

29. The at least one computer-readable medium of claim 28 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.

30. The at least one computer-readable medium of claim 29 wherein the predetermined prime number is the number of channels in the plurality of channels if the number of channels is a prime number.

31. The at least one computer-readable medium of claim 29 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.

32. The at least one computer-readable medium of claim 26 further comprising the step of switching to a parity slot.

33. The at least one computer-readable medium of claim 26 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.

34. The at least one computer-readable medium of claim 33 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.

35. The at least one computer-readable medium of claim 34 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.

36. The at least one computer-readable medium of claim 26 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.

37. The at least one computer-readable medium of claim 36 wherein the step of desynchronizing comprises the step of selecting a new (channel, seed) pair for the slot.

38. The at least one computer-readable medium of claim 26 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.

39. The at least one 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.

40. The at least one computer-readable medium of claim 39 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.

41. The at least one computer-readable medium of claim 40 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.

42. The at least one computer-readable medium of claim 40 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.