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 distributed scheduling of transmission on a shared wireless medium based on hybrid deterministic and non-deterministic distributed scheduling, the method comprising:
deterministically selecting, by a first wireless device sharing a wireless medium with other wireless devices, a deterministic transmit time slot in a contention window, wherein:
the contention window comprises a plurality of time slots among which the deterministic transmit time slot is selected,
the plurality of time slots of the contention window include a plurality of deterministic time slots and a plurality of non-deterministic time slots, and
at least some of the nondeterministic time slots are reserved for at least some of the other wireless devices executing a respective instance of a nondeterministic algorithm to select a transmit time slot, wherein deterministically selecting comprises:
receiving, by the first wireless device, a wireless signal broadcast by a second wireless device indicating another deterministic transmit time slot selected by the second wireless device; and
based on the wireless signal, selecting a different deterministic transmit time slot from that selected by the second wireless device;
determining, by the first wireless device, that another wireless device has finished wirelessly transmitting a previous frame; and
beginning to transmit, by the first wireless device, a first next frame during an instance of the selected deterministic transmit time slot after the previous frame.
2. The method of claim 1 , wherein selecting a different deterministic transmit time slot comprises selecting a next open deterministic transmit time slot in the contention window after the deterministic transmit time slot selected by the second wireless device.
3. The method of claim 2 , wherein the contention window includes a non-deterministic transmit time slot between the deterministic transmit time slots selected by the first wireless device and the second wireless device.
4. The method of claim 3 , wherein:
the contention window includes one and only one non-deterministic transmit time slot between the deterministic transmit time slots selected by the first wireless device and the second wireless device; and
the signal is a beacon periodically transmitted by the second wireless device.
5. The method of claim 1 , wherein the plurality of time slots in the contention window alternate between deterministic time slots and non-deterministic time slots.
6. The method of claim 1 , wherein the nondeterministic algorithm to select a transmit time slot is an exponential randomized back off algorithm.
7. The method of claim 1 , comprising:
determining, by the first wireless device, to use the deterministically selected transmit time slot based on the first next frame being downlink data.
8. The method of claim 1 , comprising;
obtaining, by the first wireless device, a second next frame to transmit;
determining, by the first wireless device, to select a non-deterministic transmit time slot in the contention window;
non-deterministically selecting, by the first wireless device, a non-deterministic transmit time slot in the contention window based on random value; and
transmitting, by the first wireless device, the second next frame during an instance of the non-deterministic transmit time slot after another previous frame.
9. The method of claim 8 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on the second next frame being uplink data.
10. The method of claim 9 , wherein transmitting, by the first wireless device, the second next frame comprises:
relaying up link data in an ad hoc multi-hop wireless network.
11. The method of claim 10 , wherein relaying uplink data in an ad hoc multi-hop wireless network comprises:
receiving the second next frame via a non-cellular radio from another wireless device in a multi-hop wireless route; and
transmitting the second next frame via the non-cellular radio to a gateway wireless device in the multi-hop wireless route configured to transmit the second next frame via a cellular radio.
12. The method of claim 8 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on a quality of service specified for the second next frame.
13. The method of claim 8 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on a queue-length of the first wireless device.
14. The method of claim 8 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on an importance specified for the second next frame.
15. The method of claim 8 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on at least one of the following factors: quality of at least some sinks and relays, quantity of at least some sinks and relays, battery life, source of power, average throughput, bandwidth usage, bandwidth needs, bandwidth availability, type of device, level of mobility, time of day, subscription fees, user profile, non-cellular signal strength and quality, cellular signal strength and quality, level of wireless interference seen by a non-cellular interface, level of wireless interference seen by a cellular interface, number of hops to a sink, and surrounding wireless environment, or a combination thereof.
16. The method of claim 8 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on steps for choosing between a deterministic schedule and a non-deterministic schedule.
17. The method of claim 1 , wherein deterministically selecting the deterministic transmit time slot in the contention window comprises steps for selecting a deterministic transmit time slot in a contention window.
18. The method of claim 1 , comprising:
executing an operating system;
receiving in put via a touchscreen; and
transmitting or receiving data via a cellular network and via a non-cellular network.
19. A first wireless device comprising:
a non-cellular wireless interface;
an antenna coupled to the non-cellular wireless interface; and
program code that when executed, and/or circuitry that when operated, effectuates operations comprising:
deterministically selecting, by a first wireless device sharing a wireless medium with other wireless devices, a deterministic transmit time slot in a contention window, wherein:
the contention window comprises a plurality of time slots among which the deterministic transmit time slot is selected,
the plurality of time slots of the contention window include a plurality of deterministic time slots and a plurality of non-deterministic time slots, and
at least some of the nondeterministic time slots are reserved for at least some of the other wireless devices executing a nondeterministic algorithm to select a transmit time slot, wherein deterministically selecting comprises:
receiving, by the first wireless device, a wireless signal broadcast by a second wireless device indicating another deterministic transmit time slot selected by the second wireless device; and
based on the wireless signal, selecting a different deterministic transmit time slot from that selected by the second wireless device;
determining, by the first wireless device, that another wireless device has finished wirelessly transmitting a previous frame; and
beginning to transmit, by the first wireless device, via the non-cellular wireless interface, a first next frame during an instance of the selected deterministic transmit time slot after the previous frame.
20. The device of claim 19 , wherein selecting a different deterministic transmit time slot comprises selecting a next open deterministic transmit time slot in the contention window after the deterministic transmit time slot selected by the second wireless device.
21. The device of claim 20 , wherein the contention window includes a non-deterministic transmit time slot between the deterministic transmit time slots selected by the first wireless device and the second wireless device.
22. The device of claim 21 , wherein:
the contention window includes one and only one non-deterministic transmit time slot between the deterministic transmit time slots selected by the first wireless device and the second wireless device; and
the signal is a beacon periodically transmitted by the second wireless device.
23. The device of claim 19 , wherein the plurality of time slots in the contention window alternate between deterministic time slots and non-deterministic time slots.
24. The device of claim 19 , wherein the nondeterministic algorithm to select a transmit time slot is an exponential randomized back off algorithm.
25. The device of claim 19 , wherein the operations comprise:
determining, by the first wireless device, to use the deterministically selected transmit time slot based on the first next frame being downlink data.
26. The device of claim 19 , wherein the operations comprise;
obtaining, by the first wireless device, a second next frame to transmit;
determining, by the first wireless device, to select a non-deterministic transmit time slot in the contention window;
non-deterministically selecting, by the first wireless device, a non-deterministic transmit time slot in the contention window based on random value; and
transmitting, by the first wireless device, the second next frame during an instance of the non-deterministic transmit time slot after another previous frame.
27. The device of claim 26 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on the second next frame being uplink data.
28. The device of claim 27 , wherein transmitting, by the first wireless device, the second next frame comprises:
relaying up link data in an ad hoc multi-hop wireless network.
29. The device of claim 28 , wherein relaying uplink data in an ad hoc multi-hop wireless network comprises:
receiving the second next frame via a non-cellular radio from another wireless device in a multi-hop wireless route; and
transmitting the second next frame via the non-cellular radio to a gateway wireless device in the multi-hop wireless route configured to transmit the second next frame via a cellular radio.
30. The device of claim 26 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on a quality of service specified for the second next frame.
31. The device of claim 26 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on a queue-length of the first wireless device.
32. The device of claim 26 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on an importance specified for the second next frame.
33. The device of claim 26 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on at least one of the following factors: quality of at least some sinks and relays, quantity of at least some sinks and relays, battery life, source of power, average throughput, bandwidth usage, bandwidth needs, bandwidth availability, type of device, level of mobility, time of day, subscription fees, user profile, non-cellular signal strength and quality, cellular signal strength and quality, level of wireless interference seen by a non-cellular interface, level of wireless interference seen by a cellular interface, number of hops to a sink, and surrounding wireless environment, or a combination thereof.
34. The device of claim 26 , wherein determining to select a non-deterministic transmit time slot in the contention window comprises:
determining to select a non-deterministic transmit time slot in the contention window based on steps for choosing between a deterministic schedule and a non-deterministic schedule.
35. The device of claim 19 , wherein deterministically selecting the deterministic transmit time slot in the contention window comprises steps for selecting a deterministic transmit time slot in a contention window.
36. The method of claim 19 , wherein the operations comprise:
executing an operating system;
receiving in put via a touchscreen; and
transmitting or receiving data via a cellular network and via a non-cellular network.