Non interfering group based wireless network protocols

• US 20040228300A1
• Filed: 05/12/2003
• Published: 11/18/2004
• Est. Priority Date: 05/12/2003
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.), Northwestern University
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Lee, Chung-Chieh, Hester, Lance E.
• Granted Patent: US 7,277,394 B2
• Time in Patent Office: Days
• US Class Current: 370/329
• CPC Class Codes: H04W 72/541 using the level of interference

Abstract

A wireless network (100) and method (200) for assigning a set of channels to a set of wireless devices (102-126) in the network where there are less channels than devices such that wireless devices are grouped in channel groups such that the wireless devices assigned to each channel group are positioned so as not to interfere with each other. In assigning an nth wireless device to a kth channel group, the nth and preferably one member of the kth channel group at a time are instructed to transmit simultaneously in order to ascertain if the nth wireless device interferes with or is interfered with by any member of the kth channel group.

Claims

1. A wireless network comprising:

a number N of wireless devices;

a number K of channels used by the number N of wireless devices, wherein the number K of channels is less than the number N of wireless devices, wherein each kth channel among the number K of channels is assigned to a kth subgroup of one or more of the number N of wireless devices, and members of each kth subgroup do not interfere with each other when simultaneously transmitting.

2. The wireless network according to claim 1 wherein:

the members of each kth subgroup do not interfere owing to their being spaced sufficiently apart or shielded from each other by wireless signal obstacles.

3. A wireless network comprising:

a number N of wireless devices in a hierarchical tree routing topology for upstream data transmission the number of wireless devices including a root position wireless device at a root position of the hierarchical tree topology, wherein at least each of the plurality of wireless devices except for the root position wireless device, has a parent node;

each nth wireless device among the plurality of wireless devices, except for the root position wireless device and wireless devices that are in positions of children of the root position, routes messages to the root wireless device through a parent wireless device of the nth wireless device;

the number of wireless devices together conduct communication on a number K of channels that is less than the number N of wireless devices, wherein each kth channel among the number K of channels is assigned to a kth channel group that includes a subset of the number N of wireless devices, wherein the wireless devices of each kth channel group are positioned such that any two wireless devices of each kth channel group do not interfere with each other when simultaneously transmitting on the kth channel to respective parents of the two wireless devices.

4. The wireless network according to claim 3 wherein:

the root position wireless device has sufficient transmit power to transmit directly to substantially all of the number N of wireless devices.

5. The wireless network according to claim 3 wherein:

the number K of channels comprise the number K of time slots of a time division multi-access scheme.

6. The wireless network according to claim 3 wherein:

the number K of channels comprise the number K of spreading codes of a code division multi-access scheme.

7. The wireless network according to claim 3 wherein:

the number K of channels comprise the number K of frequency hopping sequences of a frequency hopping spread spectrum multi-access scheme.

8. The wireless network according to claim 3 wherein:

the number K of channels comprise the number K of frequency bands of a frequency division multi-access scheme.

9. The wireless network according to claim 3 wherein:

the number K of channels comprise two or more attributes selected from the group consisting of;

a frequency, a frequency hop sequence, a direct sequence spread spectrum spreading code, and a time slot.

10. A method of allocating channels to wireless devices in a hierarchical tree topology routing network, the method comprising:

assigning each of a first set of one or more channels to one of a first group wireless devices, so that that each of the first group of wireless devices is assigned one channel from the first set of one or more channels;

for each ith wireless device, among one or more remaining wireless devices in the network, that has yet to be assigned a channel, and for successive jth channels, among one or more channels already assigned in the network, testing if communication by the ith wireless device on the jth channel interferes with or is interfered with, by communication by other wireless devices in the network already assigned to use the jth channel; and

in the case that communication by the ith wireless device on the jth channel is not interfered with and does not interfere with communication by wireless devices using the jth channel, assigning the jth channel to the ith wireless device;

in the case that communication by the ith wireless device interferes with or is interfered with by communication on each channel among the one or more channels already assigned in the network, and more channels remained to be allocated for use in the network, allocating a new channel to the ith wireless device.

11. The method of allocating channels in a hierarchical tree topology routing network according to claim 10 wherein:

assigning each of the first set of one or more channels to one of the first group of wireless devices comprises;

assigning each of the first set of one or more channels to a set of wireless devices that occupy positions of children of a root position wireless device of the hierarchical tree topology network; and

wherein the method assigns channels starting with the set of wireless devices that occupy positions of children of the root position wireless device and working down level-by-level in the hierarchical tree topology.

12. The method according to claim 10 wherein testing if communication by the ith wireless device on the jth channel interferes with or is interfered with, by communication by wireless devices in the network already assigned to use the jth channel comprises:

transmitting one or more messages from the ith device and transmitting a message from each wireless device using the jth channel and determining if the messages transmitted by the ith devices and each other wireless device using the jth channel are received correctly.

13. The method according to claim 12 wherein:

transmitting one or more messages from the ith device and transmitting a message from each wireless device using the jth channel comprise transmitting messages using less channel coding than is used for data transmission in the network.

14. The method according to claim 12 wherein, in testing if communication by the ith wireless device on the jth channel interferes with or is interfered with, by communication by wireless devices in the network using the jth channel:

each wireless device using the jth channel transmits concurrently with the ith device but separately from other wireless devices using the jth channel.

15. The method of allocating channels in a hierarchical tree topology network according to claim 12 wherein:

assigning each of the first set of one or more channels to one of the first group of wireless devices comprises;

assigning each of the first set of one or more channels to a set of wireless devices that occupy positions of children of a root position wireless device of the hierarchical tree topology network; and

wherein the method assigns channels starting with the set of wireless devices that occupy positions of children of the root position wireless device and working down level by level in the hierarchical tree topology.

16. The method according to claim 15 wherein:

transmitting one or more messages from the ith wireless device comprises;

transmitting one or more message destined for the root position wireless device through a parent of the ith wireless device;

transmitting a message from each wireless device using the jth channel comprises;

transmitting a message destined for the root position wireless device from each wireless device using the jth channel, through a respective parent of each wireless device using the jth channel; and

determining if the messages transmitted by the ith devices and each other wireless device already assigned to the jth channel are correctly received comprises;

determining if the messages transmitted by the ith devices and each other wireless device using the jth channel are correctly received at the root position wireless device.

19. The media access control method according to claim 16 wherein:

the wireless devices in each polling group are positioned so as not to interfere with each other, in respect to messages sent to parents of the members of the polling group.

17. A media access control method comprising:

assigning a plurality of wireless devices, selected from a set of wireless devices of a network, to each of a plurality of time slots, wherein the plurality of wireless devices assigned to each time slot are positioned so as not to interfere with each other.

18. The media access control method according to claim 17 further comprising:

during each time slot transmitting a signal to wireless devices assigned to the time slot granting permission to wireless devices assigned to the time slot permission to transmit messages.

20. A method of ascertaining if two wireless devices in a network interfere with each other, the method comprising:

for each of a plurality of pairs of devices that include a first member of the pair, and a second member of the pair;

(a) having the first member of the pair, and the second member of the pair transmit a first message and a second message respectively, wherein the first message and the second message overlap at least partially temporally; and

(b) ascertaining if the first message and the second message are received correctly.

21. The method according to claim 20 wherein (a) and (b) are repeated for each combination of wireless devices in the network, taken two at a time.

22. The method according to claim 20 further comprising:

storing information ascertained in (b) in a matrix of binary valued elements.