Opportunistic Use of Wireless Network Stations as Repeaters

• US 20070147338A1
• Filed: 02/16/2007
• Published: 06/28/2007
• 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, Padhye, Jitendra, Yu, Yan
• Granted Patent: US 8,050,212 B2
• Time in Patent Office: Days
• US Class Current: 370/350
• CPC Class Codes: H04J 3/06 Synchronising arrangements for television systems H04N5/04; bit-synchronisation H04L7/00
• CPC Class Codes: H04W 36/14 Reselecting a network or an air interface
• 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/24 Transfer of terminal data
• 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

Implementation of opportunistic use of stations in a wireless network as repeaters is described. In one implementation, a station detects the existence of rate anomaly in a wireless network. In response to the rate anomaly, the station may transform into a software repeater for certain other neighboring stations. The repeater function allows for the relaying of packets sent by these neighboring stations to the access point and vice versa. The other neighboring stations, owing to their relative proximity to the repeater station, transmit data at a higher rate to the repeater station. Thus, the removal of the slower stations reduces clogging of the access point and increases the overall data rate within the wireless network. Further, a zero-overhead network coding protocol may be implemented in conjunction with the repeater function to increase capacity of the wireless network.

Claims

1. A method comprising:

detecting rate anomaly suffered by one or more stations in a wireless network, wherein the rate anomaly exists if the one or more stations transmitting or receiving data suffer from throughput degradation; and

requesting the one or more stations to activate a repeater function implemented as a software at the one or more stations based on the detecting.

2. A method as recited in claim 1, wherein the detecting comprises:

collecting information from one or more other stations in the wireless network, wherein the information comprises at least of MAC identifiers of the one or more other stations, number of packets heard from each of the one or more other stations, average size of the packets heard, RSSI and data rate of the packets heard, and BSSID of the wireless network;

computing airtime consumed by each of the one or more other stations based on the number of packets heard, the average size of the packets heard, and the data rate of the packets heard;

determining utilization of a wireless medium by adding airtime consumed by the one or more other stations from the collected information; and

ascertaining existence of the rate anomaly, wherein the rate anomaly exists if the utilization of the wireless medium is greater than a threshold and the one or more other stations suffer from throughput degradation.

3. A method as recited in claim 2, further comprising:

using a network coding protocol to increase capacity of the wireless network, wherein the network coding protocol comprises;

buffering locally packets sent or received by each of the one or more stations in the wireless network;

receiving at the one or more stations activating the repeater function, a first packet from an access point for a first station using the repeater function, and a second packet from the first station for the access point;

mixing the first packet and the second packet to form a mixed packet;

broadcasting the mixed packet to the one or more other stations in the wireless network; and

decoding the mixed packet at the access point and the first station based on the buffered packets.

4. A method as recited in claim 1, wherein the requesting further comprises determining whether activation of the repeater function at the one or more stations would be beneficial to the one or more stations activating the repeater function and to performance of the wireless network.

5. A method as recited in claim 1, wherein the requesting further comprises broadcasting a message to one or more other stations in the wireless network seeking activation of the repeater function at the one or more other stations to alleviate the rate anomaly.

6. A method as recited in claim 1, wherein the requesting further comprises:

broadcasting a message, by the one or more stations requested to activate the repeater function, with IP addresses of one or more other stations, the message comprising estimated data rates of the one or more other stations;

receiving utility of the repeater function to the one or more other stations as calculated by the one or more other stations;

broadcasting actual utility to a revised set of the one or more other stations based on the received utility calculated by the one or more other stations;

receiving from each of the revised set of the one or more other stations a decision regarding participation if the repeater function is activated; and

initiating the repeater function upon receipt of sufficient decisions in favor of participation from the revised set of the one or more other stations.

7. A method as recited in claim 1, further comprising activating the repeater function comprising:

creating virtual instances of one or more wireless network interfaces to establish a primary virtual interface and a repeater virtual interface, wherein the primary virtual interface supports the wireless network and the repeater virtual interface supports the repeater network; and

switching connectivity between the wireless network and the repeater network to transmit packets received via the repeater network to the wireless network and vice versa.

8. A device comprising:

one or more processors;

one or more wireless network interfaces to facilitate access to a wireless network, wherein each wireless network interface supports a promiscuous mode;

memory; and

a repeater service module, stored in the memory, executable on the one or more processors and capable of accessing the one or more wireless network interfaces to activate a repeater function at the device.

9. A device as recited in claim 8, wherein the repeater service module comprises:

a rate anomaly detection module to detect a rate anomaly in the wireless network; and

a node requestor module to request one or more stations to activate the repeater function at the one or more stations in the wireless network if activating a repeater network at the one or more stations would reduce the rate anomaly in the wireless network.

10. A device as recited in claim 8, wherein the repeater service module comprises:

a repeater utility module to determine whether activation of the repeater function would be beneficial to the device based on expected throughput improvement, burden on system resources and security concerns to the device and wireless network due to the activation.

11. A device as recited in claim 8, wherein the repeater service module further comprises:

a repeater protocol module to communicate with one or more stations before activating the repeater function at the device for determining utility of the repeater function at the device to the one or more stations.

12. A device as recited in claim 11, wherein the repeater protocol module further comprises:

an initiator module to broadcast a message with IP addresses of each of one or more stations in the wireless network, the message comprising estimated data rates of each of the one or more stations when utilizing the repeater function at the device;

a receiver module to receive messages from the one or more stations wherein the received message comprises utility calculated by the one or more stations if the repeater function is utilized;

a selector module to broadcast a message with recalculated utility to a selected set of the one or more stations based on the received messages; and

an authorize module to authorize activation of the repeater network based upon receipt of a sufficient set of responses in favor of participation from the selected set of the one or more stations.

13. A device as recited in claim 8, wherein the repeater service module further comprises:

an activator module to activate the repeater function, the activator module comprising;

a driver module to load a kernel-based intermediate-layer virtualization driver capable of abstracting the one or more wireless network interfaces into multiple virtual instances to create a primary virtual interface and a repeater virtual interface; and

a loader module to plug the details of a repeater network into the repeater virtual interface to establish the repeater network at the device alongside the wireless network.

14. A device as recited in claim 8, wherein the repeater service module further comprises:

a network coding module to improve capacity of the wireless network, the network coding module comprising;

a buffer module to locally buffer packets sent or received by one or more stations in the wireless network for a certain period of time to form buffered packets;

a mixing module to mix, at the device activating the repeater function, a packet received from a first station for an access point and a packet received from the access point for the first station to form a mixed packet;

a broadcast module to broadcast the mixed packet to the one or more stations in the wireless network; and

a decode module to decode the mixed packets received based on the buffered packets.

15. One or more computer-readable media storing computer-executable instructions that, when executed by one or more processors, perform acts comprising:

activating a repeater function implemented as a software at one or more stations in a wireless network; and

employing a network coding protocol in conjunction with the activated repeater function at the one or more stations to increase capacity of the wireless network.

16. One or more computer-readable media as recited in claim 15, wherein the network coding protocol is a zero-overhead network coding protocol that does not require addition of extra bytes to headers of coded packets to be transmitted in order to identify contents of the coded packets at the one or more stations receiving the coded packets.

17. One or more computer-readable media as recited in claim 15, wherein the employing of the network coding protocol further comprises:

mixing a first packet from a first station utilizing the repeater function for an access point from and a second packet from an access point for the first station at the one or more stations activating the repeater function, the mixing forming a resulting packet; and

broadcasting the resulting packet over the wireless network.

18. One or more computer-readable media as recited in claim 17, wherein the broadcasting comprises unicasting the resulting packet to the first station or the access point, whichever may be farthest from the one or more stations unicasting the resulting packet.

19. One or more computer-readable media as recited in claim 17, wherein the mixing comprises performing a logical operation of Exclusive OR (XOR) on the first packet from the first station for the access point and the second packet from the access point for the first station.

20. One or more computer-readable media as recited in claim 17, further comprising:

buffering locally packets sent by each of the one or more stations in the wireless network;

identifying the resulting packet from all packets received by the one or more stations, wherein the identifying comprises checking value of IP version field of IP header of packets received over the wireless network; and

decoding the resulting packet received at the one or more stations based on the buffered packets at the one or more stations.