Methods and devices for routing traffic using a configurable access wireless network
View Patent ↗A configurable access network (CAN) architecture is used to identify primary routing paths that allows each wireless station within a static, multi-hop wireless CAN to route packetized data in a way that simplifies the operation of each station and makes more efficient use of the limited energy available to each station.
1. A method for identifying primary routing paths in a static, multi-hop, configurable access wireless network to maximize the lifetime of the network comprising:
generating a fractional routing solution for each wireless station in the network to form a linear program making use of two constraints, where one constraint ensures traffic withdrawn by each station equals its bandwidth demand, and a second constraint ensures an aggregated flow originating at a source station is a sum of each station's bandwidth demand;
rounding the fractional solution into an integral solution to identify a primary path for each of the wireless stations; and
controlling the routing of traffic through each of the wireless stations using the identified primary paths to maximize a lifetime of the network.
2. The method as in claim 1 wherein the lifetime of the wireless network is at least 50% of an optimal lifetime.
3. The method as in claim 2 wherein each of the wireless stations initially have the same energy levels.
4. The method as in claim 2 wherein each of the wireless stations initially have the same bandwidth demands.
5. The method as in claim 1 further comprising generating the fractional solution using a variable related to the lifetime of the network.
6. A method for identifying primary routing paths in a static, multi-hop, configurable access wireless network to maximize the lifetime of the network comprising:
generating a fractional routing solution, based on those wireless stations in the network that have a sufficient, initial energy level to relay traffic, to form a linear program making use of two constraints, where one constraint ensures traffic withdrawn by each station equals its bandwidth demand, and a second constraint ensures an aggregated flow originating at a source station is a sum of each station's bandwidth demand;
rounding the fractional solution into an integral solution to identify a primary path for each of the wireless stations; and
controlling the routing of traffic through each of the wireless stations using the identified primary paths to maximize a lifetime of the network.
7. The method as in claim 6 wherein the network lifetime of the wireless network is at least
2
2
+
α
of an optimal lifetime, where α is a ratio of upper and lower bandwidth demand bounds.
8. The method as in claim 7 wherein each of the wireless stations initially has an arbitrary energy level and is associated with upper and lower bandwidth demand bounds.
9. The method as in claim 6 wherein the sufficient, initial energy level of each wireless station is at least a level required to route traffic of a station and traffic of at least one other station for a network lifetime.
10. The method as in claim 6 further comprising generating the fractional solution by at least performing a binary search over an estimated network lifetime.
11. A method for identifying primary routing paths in a static, multi-hop, configurable access wireless network to maximize the lifetime of the network comprising:
generating a fractional routing solution for each relay group of wireless stations in the network to form a linear program making use of two constraints, where one constraint ensures traffic withdrawn by each station equals its bandwidth demand, and a second constraint ensures an aggregated flow originating at a source station is a sum of each station's bandwidth demand;
separately rounding each of the fractional solutions into an integral solution to identify a primary path for each of the wireless stations; and
controlling the routing of traffic through each of the wireless stations using the identified primary paths to maximize a lifetime of the network.
12. The method as in claim 11 wherein the lifetime of the wireless network is at least 20% of an optimal lifetime.
13. The method as in claim 12 wherein each of the wireless stations initially has an arbitrary energy level and is not limited by an upper or lower bandwidth demand bound.
14. The method as in claim 11 wherein each of the stations within each relay group has a sufficient, initial energy level to relay traffic.
15. The method as in claim 14 wherein the sufficient, initial energy level of each wireless station within a relay group is at least a level required to route traffic of a station and traffic of at least one other station for a network lifetime.
16. A controller, for identifying primary routing paths in a static, multi-hop, configurable access wireless network to maximize the lifetime of the network, operable to:
generate a fractional routing solution for each wireless station in the network to form a linear program making use of two constraints, where one constraint ensures traffic withdrawn by each station equals its bandwidth demand, and a second constraint ensures an aggregated flow originating at a source station is a sum of each station's bandwidth demand;
round the fractional solution into an integral solution to identify a primary path for each of the wireless stations; and
control the routing of traffic through each of the wireless stations using the identified primary paths to maximize a lifetime of the network.
17. The controller as in claim 16 wherein the lifetime of the wireless network is at least 50% of an optimal lifetime.
18. The controller as in claim 17 wherein each of the wireless stations initially have the same energy levels.
19. The controller as in claim 17 wherein each of the wireless stations initially have the same bandwidth demands.
20. The controller as in claim 16 further operable to generate the fractional solution using a variable related to the lifetime of the network.
21. A controller, for identifying primary routing paths in a static, multi-hop, configurable access wireless network to maximize the lifetime of the network, operable to:
generate a fractional routing solution, based on those wireless stations in the network that initially have a sufficient energy level to relay traffic, to form a linear program making use of two constraints, where one constraint ensures traffic withdrawn by each station equals its bandwidth demand, and a second constraint ensures an aggregated flow originating at a source station is a sum of each station's bandwidth demand;
round the fractional solution into an integral solution to identify a single primary path for each of the wireless stations; and
control the routing of traffic through each of the wireless stations using the identified primary paths to maximize a lifetime of the network.
22. The controller as in claim 21 wherein the network lifetime of the wireless network is at least
2
2
+
α
of an optimal lifetime, where α is a ratio of upper and lower bandwidth demand bounds.
23. The controller as in claim 22 wherein each of the wireless stations initially has an arbitrary energy level and is associated with upper and lower bandwidth demand bounds.
24. The controller as in claim 21 wherein the sufficient, initial energy level of each wireless station is at least a level required to route traffic of a station and traffic of at least one other station for a network lifetime.
25. The controller as in claim 21 wherein the controller is further operable to generate the fractional solution by at least performing a binary search over an estimated network lifetime.
26. A controller, for identifying primary routing paths in a static, multi-hop, configurable access wireless network to maximize the lifetime of the network, operable to:
generate a fractional routing solution for each relay group of wireless stations in the network to form a linear program making use of two constraints, where one constraint ensures traffic withdrawn by each station equals its bandwidth demand, and a second constraint ensures an aggregated flow originating at a source station is a sum of each station's bandwidth demand;
separately round each of the fractional solutions to form an integral solution to identify a primary path for each of the wireless stations; and
control the routing of traffic through each of the wireless stations using the identified primary paths to maximize a lifetime of the network.
27. The controller as in claim 26 wherein the lifetime of the wireless network is at least 20% of an optimal lifetime.
28. The controller as in claim 27 wherein each of the wireless stations initially has an arbitrary energy level and a bandwidth demand that is not limited by an upper or lower bound.
29. The controller as in claim 26 wherein each of the stations within each relay group has a sufficient, initial energy level to relay traffic.
30. The controller as in claim 29 wherein the sufficient, initial energy level of each wireless station within a relay group is at least a level required to route traffic of a station and traffic of at least one other station for a network lifetime.