Network routing system, method, and computer program product
A method, system, or computer program product to enhance the performance of multi-hop cellular networks or other wireless networks is provided. A wireless device (e.g., cellular telephone) is able to communicate with a base-station in a cell of the cellular network over a non-cellular interface via another wireless device in the cell through the use of multi-hopping. By enabling wireless devices to communicate with a base station in such a manner, the effective coverage area of the cellular network is expanded and the effective capacity of the cellular network is improved. Distributed routing, device management, adaptive scheduling, and distributed algorithms can be used to enhance the overall performance of multi-hop cellular networks.
1. A method of coordinating use of a wireless medium among wireless devices that are out of range of one another, the method comprising:
receiving, by a first wireless device operating as a node of a hybrid cellular and non-cellular multi-hop wireless network, a first request-to-send (RTS) signal transmitted from a second wireless device to a third wireless device, the RTS signal being wirelessly transmitted by the second wireless device in response to data in an output buffer of the second wireless device destined for the third wireless device;
receiving, by the first wireless device, a second RTS signal transmitted from a fourth wireless device to the first wireless device, the second RTS signal being wirelessly transmitted by the fourth wireless device in response to data in an output buffer of the fourth wireless device destined for the first wireless device, the fourth wireless device being out of range of the second wireless device;
in response to the first RTS signal, determining, by the first wireless device, to delay a transmission of a first clear-to-send (CTS) signal from the first wireless device until an acknowledgement (ACK) signal is transmitted from the third wireless device to the second wireless device;
receiving the ACK signal, by the first wireless device, the ACK signal being wirelessly transmitted from the third wireless device to the second wireless device in response to receipt of data by the third wireless device from the second wireless device; and
in response to the ACK signal, wirelessly transmitting a second CTS signal from the first wireless device to the fourth wireless device.
2. The method of claim 1 , comprising receiving data frames, by the first wireless device, from the fourth wireless device after transmitting the second CTS signal.
3. The method of claim 1 , wherein the first wireless device is a cell phone.
4. The method of claim 1 , wherein receiving the ACK signal comprises receiving the ACK signal via a non-cellular interface of the first wireless device.
5. A method of routing data in a multi-hop wireless network, the method comprising:
obtaining, by a first wireless device, data indicative of whether signal-quality of transmissions from a second wireless device to the first wireless device are above a first threshold, wherein the first threshold is greater than or equal to approximately 0 decibels;
obtaining, by the first wireless device, data indicative of whether signal-quality of transmissions from a third wireless device to the first wireless device are above a second threshold, wherein the second threshold is greater than or equal to approximately 30 decibels;
based on the obtained data, by the first wireless device, determining to route data from the first wireless device to the second wireless device through the third wireless device; and
in response to the determination, transmitting data to the third wireless device for relay to the second wireless device.
6. The method of claim 5 , wherein the data indicative of whether signal-quality of transmissions from the second wireless device to the first wireless device are above the first threshold comprises a beacon frame transmitted by the second wireless device.
7. The method of claim 5 , wherein the data indicative of whether signal-quality of transmissions from the second wireless device to the first wireless device are above the first threshold indicates signal-quality above the first threshold and less than the second threshold.
8. The method of claim 5 , wherein the data indicative of whether signal-quality of transmissions from the second wireless device to the first wireless device are above the first threshold indicates low signal-quality above the first threshold and less than the second threshold.
9. The method of claim 8 , wherein the low signal-quality is less than 20 decibels.
10. The method of claim 8 , wherein the second threshold is indicative of a high signal-quality.
11. The method of claim 5 , wherein determining to route data from the first wireless device to the second wireless device through the third wireless device based on the obtained data comprises:
determining the signal-quality of transmissions from the second wireless device to the first wireless device are above the first threshold and less than the second threshold; and
determining the signal-quality of transmissions from the third wireless device to the first wireless device are above the second threshold.
12. The method of claim 11 , wherein:
the signal-quality of transmissions above the first threshold and less than the second threshold are of lower quality, and
the signal-quality of transmissions above the second threshold are of high quality.
13. The method of claim 5 , wherein determining to route data from the first wireless device to the second wireless device through the third wireless device based on the obtained data comprises:
determining the signal-quality of transmissions from the second wireless device to the first wireless device are less than 20 decibels; and
determining the signal-quality of transmissions from the third wireless device to the first wireless device are greater than 30 decibels.
14. A method of relaying data in a multi-hop network, the method comprising:
receiving, by a first wireless device, a data frame and a first value both wirelessly transmitted from a second wireless device, the first value having a size smaller than or approximately equal to 4 bytes;
determining, by the first wireless device, to relay the data frame based on the first value;
in response to the determination, selecting, by the first wireless device, a third wireless device to receive the data frame; and
in response to the determination, transmitting, by the first wireless device, the data frame and a second value calculated by the first wireless device to the third wireless device.
15. The method of claim 14 , wherein the first value is based on a medium-access control (MAC) address of the second wireless device.
16. The method of claim 14 , wherein the first value is based on a destination MAC address.
17. The method of claim 14 , wherein the data frame comprises the first value.
18. A method of reconstructing an acknowledgement signal, the method comprising:
wirelessly receiving, by a first wireless device operating as a node of a hybrid cellular and non-cellular multi-hop network, data frames from a second device to be relayed to a third wireless device;
snooping, by the first wireless device, frame-reconstruction-helper-values from header information of the data frames;
wirelessly transmitting, by the first wireless device, the data frames to the third wireless device along with a signal commanding the third wireless device to not transmit an acknowledgement signal for the second device;
constructing, by the first wireless device, based on frame-reconstruction-helper-values, an acknowledgement signal; and
transmitting the acknowledgement signal to the second device.
19. The method of claim 18 , wherein the frame-reconstruction-helper-values are based on internet protocol and transmission control protocol (TCP) headers of an encapsulated TCP segment.