Characterizing the capacity region in multi-channel, multi-radio mesh networks

[0001] 1. Field of the Invention

[0002] The present invention relates, generally, to network routing and scheduling, and more particularly, to the computation of capacity, and algorithms to achieve capacity, in multi-channel, multi-radio (e.g., wireless) mesh networks.

[0003] 2. Description of the Related Art

[0004] The emergence of broadband wireless networks has been spurred by the development of standards such as IEEE 802.11 a/b/g and 802.16. These networks are being deployed as a solution to extending the reach of the last-mile access to the Internet, using a multi-hop configuration. In multi-hop networks, communication between two end nodes is carried out through a number of intermediate nodes whose function is to relay information from one point to another. Many such networks are already in use, ranging from prototype testbeds to complete commercial solutions. As shown in FIG. 1, one popular deployment method is to use one standard, such as IEEE 802.16, for intercell communications, i.e., back-hauling traffic on the multi-hop wireless relay backbone, while using another standard, such as 802.11 a/b/g, for intracell communications, i.e., to carry traffic over the last hop to the user. This isolates traffic on the wireless backbone from the fluctuating load and interference from the last-hop end users.

[0005] Fixed multi-channel, multi-hop wireless networks with multiple radios per node are referred to as MC-MR networks. Such MC-MR networks typically have the following characteristics:

[0006] 1. There are multiple wireless channels of operation, and these channels are orthogonal to each other.

[0007] 2. Nodes have multiple radio transceivers, which allow them to communicate, interference-free and simultaneously, with more than one neighbor at the same time using different channels.

[0008] 3. Full-duplex operation is possible at each node, i.e., a node can be receiving from or transmitting to a neighbor i on channel A, while transmitting to or receiving from neighbor j on channel B, where A≠B.

[0009] 4. The number of orthogonal wireless channels could be limited in number, which implies that more than one node in a given region could contend for the same channel at the same time, thereby resulting in interference and collisions.

[0010] 5. The radios (also referred to as Network Interface Cards, or NICs) at each node are capable of fast switching between channels, with a switching overhead. Channels can be assigned for communication between neighbors in a static or dynamic fashion. In a static link-channel assignment, every link between a pair of neighboring nodes is bound to a particular channel, and this binding does not vary over time. In dynamic link-channel assignment, the bindings between a link and the operating channel for that link can vary dynamically with time. While dynamic assignment involves negotiation, it also provides more flexibility to combat interference.

[0011] One of the main goals in the design of fixed wireless broadband networks is capacity planning. Within this realm, given a set of end-to-end demands, there are multiple design goals for which a network can be optimized, e.g., maximizing a function of the rates where the function can be chosen to be a user utility function or a network price function, ensuring some notion of rate fairness, or minimizing end-to-end delays. Every design goal involves designing routes, assigning channels, and scheduling packets to meet such goals. Numerous studies have considered routing, channel assignment, and scheduling for such networks. Some have studied the problem of finding efficient routes to maximize throughput, some have considered only channel assignment and scheduling, and others have considered both routing and scheduling. However, all of these previous studies considered only a subset of the problem, e.g., addressing only the question of how to improve throughput compared to other known algorithms.

[0012] In one embodiment, the present invention provides a method of characterizing a capacity region in a multi-channel, multi-radio mesh network of nodes interconnected by links. The method comprises: (a) modeling the network by determining one or more link-flow feasibility constraints; (b) obtaining a feasible upper-capacity bound by solving an optimization problem using the one or more link-flow feasibility constraints as necessary conditions; and (c) using an algorithm adapted to provide a feasible lower-capacity bound by (i) receiving the solution to the optimization problem as input, (ii) allocating channels to links to meet a demand vector that satisfies the one or more link-flow feasibility constraints, and (iii) scheduling flows along the allocated channels. The upper- and lower-capacity bounds define the capacity region.

[0013] In another embodiment, the present invention provides a multi-channel, multi-radio mesh network of nodes interconnected by links. The network comprises an apparatus for characterizing a capacity region. The apparatus is adapted to: (a) model the network by determining one or more link-flow feasibility constraints; (b) obtain a feasible upper-capacity bound by solving an optimization problem using the one or more link-flow feasibility constraints as necessary conditions; and (c) use an algorithm adapted to a feasible lower-capacity bound by (i) receiving the solution to the optimization problem as input, (ii) allocating channels to links to meet a demand vector that satisfies the one or more link-flow feasibility constraints, and (iii) scheduling flows along the allocated channels. The upper- and lower-capacity bounds define the capacity region.

[0014] In a further embodiment, the present invention provides an apparatus for characterizing a capacity region in a multi-channel, multi-radio mesh network of nodes interconnected by links. The apparatus is adapted to: (a) model the network by determining one or more link-flow feasibility constraints; (b) obtain a feasible upper-capacity bound by solving an optimization problem using the one or more link-flow feasibility constraints as necessary conditions; and (c) use an algorithm adapted to a feasible lower-capacity bound by (i) receiving the solution to the optimization problem as input, (ii) allocating channels to links to meet a demand vector that satisfies the one or more link-flow feasibility constraints, and (iii) scheduling flows along the allocated channels. The upper- and lower-capacity bounds define the capacity region.

[0034] A problem that has not previously been addressed in multi-channel, multi-radio networks is how to characterize the capacity region, i.e., the set of all feasible rate vectors, of the network for a given optimization objective. The present invention, in various embodiments, addresses the question of how to characterize the capacity region of a network for a given optimization objective. This capacity-planning question is addressed herein by developing algorithms to jointly optimize the routing, link-channel assignments, and scheduling for such networks, in order to obtain upper and lower bounds for the capacity region under a given objective function. In certain embodiments, a network model is proposed which captures the important practical aspects of, and characterizes the constraints binding the behavior of, systems involving multiple orthogonal channels and nodes that have the ability to communicate simultaneously with many neighbors using multiple radios over orthogonal channels. Necessary conditions are provided to verify the feasibility of rate vectors in these networks, and these conditions are used to derive upper bounds on the capacity in terms of achievable throughput, using a fast primal-dual algorithm. (As used in this specification, the term “necessary” should be interpreted based on its mathematical definition and not as limiting the scope of the claimed invention.) Two link-channel assignment schemes, one static and the other dynamic, are developed in order to derive lower bounds on the achievable throughput. Through simulations, it is demonstrated that the dynamic link-channel assignment scheme performs close to optimal on the average, while the static link-channel assignment algorithm also performs very well. The methods according to various embodiments of the present invention can provide valuable tools for network designers in planning network deployment and for optimizing different performance objectives.

[0035] A first feature of the present invention, in certain embodiments, is the development of a network model that characterizes the multi-hop and multi-radio features in a fixed broadband wireless network with a limited number of orthogonal channels and with multiple radios at each node. This model provides both necessary and sufficient conditions for a feasible channel assignment and schedule in the network, using a protocol model of interference, e.g., as set forth in Gupta, P., and Kumar, P. R., “The Capacity of Wireless Networks,” IEEE Transactions on Information Theory, 46(2), pp. 388-404, 2000. This model also has the flexibility of specifying neighbors and interferers for each node in an arbitrary fashion to suit the actual system needs. This model may further be extended to permit the modeling of multiple heterogeneous wireless standards that have inherent rate diversity, allowing interoperability among these standards as part of a unified multi-channel multi-radio mesh network.

[0036] A second feature of the present invention, in certain embodiments, is the provision (due to the NP-hardness of the joint routing and scheduling problem) of a relaxation of the above model. This relaxed model uses a linear program that gives the necessary conditions for a valid feasible solution. In addition to computing feasibility of a solution for a given objective function, this model can also identify potential bottlenecks that cause performance to degrade, which is an important requirement for network capacity planning.

[0037] A third feature of the present invention, in certain embodiments, is the consideration, among the many possible capacity-planning objectives, of the fundamental problem of feasibility of a given end-to-end demand vector, and the design of a fast primal-dual algorithm for a fully-polynomial time-approximation solution (FPTAS), which provides an upper bound to the feasibility problem. This algorithm is extensible to the optimization of similar rate-based objective functions that are useful for characterizing the capacity region.

[0038] A fourth feature of the present invention, in certain embodiments, is the proposal of three different link-channel assignment algorithms, which allocate channels to links in order to meet any given demand vector that satisfies the constraints imposed by the network model. These algorithms are referred to herein as (i) Balanced Static-Channel Assignment (BSCA), (ii) Packing Dynamic-Channel Assignment (PDCA), and (iii) Greedy-Channel Scheduling (GCS). These algorithms are applicable to any objective function used for capacity planning. The BSCA algorithm performs static link-channel assignment followed by greedy coloring for conflict resolution, while the PDCA and GCS algorithms perform link-channel assignment and scheduling simultaneously. The PDCA and GCS algorithms give an achievable lower bound on the capacity and can be used to compare the performance of any channel-assignment algorithm and evaluate how it performs with respect to the obtained capacity upper bound.

[0039] A fifth feature of the present invention, in certain embodiments, is the performance of extensive simulations on a range of graphs, showing that the aggregate (joint routing, link-channel assignment and scheduling) performance is very close to the optimum in practice for the PDCA and GCS algorithms, even though computing the optimal schedule is a well-known NP-hard problem with no known performance bounds, even for the simple case of one channel and one radio per node for general graphs. The performance of the BSCA algorithm is also quantified, and avenues for further performance improvements are identified.

[0040] The solutions proposed by the present invention for general graphs, in certain embodiments, are non-trivial because the computation of the feasible scheduling space is NP-hard, even if a subset of restrictive classes of graphs also known as (r, s)-civilized graphs is examined, e.g., as set forth in Krumke, S., Marathe, M., and Ravi, S. S., “Models and Approximation Algorithms for Channel Assignment in Radio Networks,” ACM Wireless Networks, vol. 7(6), pp. 575-584, 2001, and Alicherry, M. A., Bhatia, R., and Li, L., “Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks,” ACM Mobicom, 2005. In addition, the link-channel assignment problem is also NP-hard, e.g., as set forth in A. Raniwala, K. Gopalan and T. Chiueh, “Centralized Algorithms for Multi-channel Wireless Mesh Networks,” ACM Mobile Computing and Communications Review, April 2004. Even if it is assumed that there is no interference in the network, the optimum cannot be computed in polynomial time. Thus, the teachings of the present invention, in certain embodiments, extend both to the research community and to network planners and expand the teachings of other references, such as those directed to the optimization of the placement of nodes in a multi-hop wireless access network, e.g., as in Qiu, L., Chandra, R., Jain, K., and Mahdian, M., “Optimizing the Placement of Integration Points in Multi-hop Wireless Networks,” IEEE ICNP, 2004.

[0041] The underlying network model and the definitions and terminology used herein will first be explained.

[0042] In a fixed multi-hop wireless network with n nodes, the network is represented by a directed graph G=(V,E,E¹), where V represents the set of nodes in the network, E represents the set of directed links that can carry data (data links), and E¹ denotes the set of directed links that indicate interference but cannot carry data (interference links). Data links and interference links are assumed herein to be bi-directional. If node u can transmit directly to node v (and vice-versa), then this condition is represented by a link, uvεE, between node u and node v, with the link belonging to the set E. If node u can only interfere with node v (and vice-versa) but cannot transmit data to it, then this condition is represented by a link in uvεE¹. It is noted that a link uvεE implies that node u is within the communication range of node v, while uvεE¹ implies that node u is within the interference and/or carrier-sensing ranges of node v. These ranges need not be fixed but can vary based on the network topology, potential obstacles, and the terrain of deployment.

[0043] There are C orthogonal channels in the network, denoted by the set OC=1, 2, . . . , C. In the IEEE 802.11b standard, C=3. Although IEEE 802.11b actually has 12 channels, only 3 channels can operate simultaneously without interfering with one another. Each node v has κ(v) radios. One of the practical constraints on radios is that it is not useful to have two radios tuned to the same channel at a given node, since local interference at the node will ensure that only one of them is active at any time. Therefore, it is possible that κ(v)≦C, although this is not a restricting factor in the model discussed herein.

[0044] Given a data link eεE, t(e) represents the transmission end of link e, and h(e) the receiving end of link e. A data link e is said to be active when there is a transmission from t(e) to h(e). Each data link e has capacity c_i(e) on channel i. It is assumed that, for a given topology, the capacity is fixed for any given channel across a link. In other words, c_i(e) does not change over time. (If a feasible rate vector is recomputed every T_f time slots, then this assumption can be relaxed to saying that c_i(e) is constant over T_f time slots.) A flow on data link e using channel i is denoted by f_i(e). The variable g_i(e) is defined as the utilization of channel i over link e, wherein g_i(e)=f_i(e)/c_i(e).

[0045] Given a node vεV, N(v) denotes the set of neighbors of node v with data links to and from node v. These data links are denoted by the set E(v). It is also assumed that all link capacities, flows, and rates are rational numbers. The notations in the following Table 1 are used herein:

[0046]

TABLE 1
ν	Set of vertices	N	Number of nodes |V|
E	Set of data links	EI	Set of interference
			links
G	Network graph	τ	Length of a time slot
t(e), eεE	Transmitting node	h(e), eεE	Receiving node of
	of link e		link e
OC	Set of orthogonal	κ(ν)	Number of radios at
	channels,|OC| = C		node ν
ci(e)	Capacity of channel	fi(e)	Flow rate of channel
	i over link e		i over link e
gi(e)	Utilization of channel	ρ(e)	Maximum number of
	i over link e		channels available
	(i.e., fi(e)/ci(e))		for link e
N(ν)	Set of data-link	NI(ν)	Set of interference-
	neighbors of node ν		link neighbors of
			node ν
E(ν)	Set of data links	EI(ν)	Set of interference
	incident on node ν		links incident on
			node ν

[0047] It is assumed that the system operates in a synchronous time-slotted mode, where the length of a time-slot is τ seconds. For an asynchronous system, the results of using the present invention, in certain embodiments described herein, will serve as an upper bound on the performance of the system.

[0048] The present invention, in certain embodiments, employs a protocol interference model, e.g., as given in Gupta, P., and Kumar, P. R., “The Capacity of Wireless Networks,” IEEE Transactions on Information Theory, 46(2), pp. 388-404, 2000. In this model, a transmission on channel i over link e is successful when all potential interferers in the neighborhood of sender t(e) and receiver h(e) are silent on channel i for the duration of the transmission. This is similar to the model used in IEEE 802.11, based on a RTS-CTS-Data-ACK sequence, as set forth in IEEE Std. 802.11-1999, “Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,” 1999. The interference neighborhood of a node v is defined to be the set of nodes that can interfere with node v. This is the set of nodes that have either a data link or an interference link incident on node v. The protocol model of interference captures the behavior of the Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) protocol (a network contention protocol that listens to a network in order to avoid collisions), which assumes bi-directionality of links for correct operation.

[0049] With respect to link-channel assignment, every node makes two decisions at the beginning of each time slot: (i) which node (if any) it is going to communicate with, and (ii) the channel on which this communication is going to take place. Both of these decisions are negotiated between neighboring nodes, and then transmission takes place. The decision of which channel on which to communicate can either (i) be done on a per-time-slot basis or (ii) be fixed for the entire lifetime of the network (or fixed for a long time until the demands change). A method wherein the channel on which communication takes place between neighbors is decided at the beginning of each time slot is referred to as Dynamic Link-Channel Assignment. A method wherein the mapping of links to channels is fixed for the entire lifetime of the network is referred to as Static Link-Channel Assignment.

[0050] In both cases, if the number of radios at a node is less than the number of neighbors (and the number of orthogonal channels available), then the node can be expected to switch its radios to various channels in order to make use of the multiple channels available, as set forth, e.g., in P. Kyasanur and N. Vaidya, “Routing and Interface Assignment in Multi-Channel Multi-Interface Wireless Networks,” IEEE WCNC, 2005. It might be expected that the throughput of static-channel allocation would be lower than dynamic-channel allocation, due to the fact that static-channel allocation is a special case of dynamic-channel allocation. However, under static-channel assignment, the only decision a node makes is to determine which neighbor (if any) with which it is going to communicate in a given time slot, since the channel on which to communicate with the neighbor is already fixed and therefore does not need to be negotiated. Algorithms for both of these versions of the link-channel assignment problems are disclosed herein, as well as results on the performance of both of these algorithms, with varying numbers of channels and radios.

[0051] Several design considerations are relevant to the determination of feasibility constraints, including link-channel restriction, interference links, channel allocation, and multi-path routing.

[0052] As to link-channel restriction, a node can be active simultaneously on κ(v) channels at the same time, and any subset m of these channels can be used to talk to one neighbor, assuming that the neighbor has at least m radios. Each data link e can be restricted to use no more than a certain number of channels (e).

[0053] As to interference links, a description follows explaining how to model the constraints based on data links and interference links. Beyond that, to maintain clarity of presentation, it will be assumed herein that there are no interference links in the graph. It should be understood that this is only to present certain embodiments of the invention in a more focused manner, and that the algorithms set forth herein should not need to be modified when interference links are present.

[0054] As to channel allocation, the network characterization developed below is applicable to both static-channel allocation and dynamic-channel allocation methods. As noted above, existing constraints on hardware, e.g., as set forth in Chandra, R., Bahl, V., and Bahl, P., “MultiNet: Connecting to multiple IEEE 802.11 networks using a single wireless card,” IEEE Infocom, 2004, may preclude fast dynamic switching or impose a non-negligible throughput penalty. Since the goal of certain embodiments of the present invention is to characterize and seek the maximum throughput possible, it is assumed that channel switching can be performed with a negligible overhead, without affecting capacity.

[0055] As to multi-path routing, choosing only one route between a source and a destination does not exploit the inherent multi-path diversity present in mesh networks for maximizing throughput. Therefore, multi-path routing will be used for routing end-to-end flows.

[0056] The approach of the present invention, in one embodiment, is to solve a cross-optimization problem with a given objective for an instance of an MC-MR multi-hop network in three steps: (a) first, the constraints placed by the nodes, channels, interference model, and the network parameters on the feasibility of a flow are determined, (b) link-flow feasibility constraints are used as necessary conditions, and the optimization problem using the stated objective is solved, and (c) link-channel assignment (static and/or dynamic) is performed, along with scheduling based on greedy coloring to resolve potential conflicts, and a feasible schedule from the solution in step (b) is obtained. It is noted that step (c) gives a feasible lower bound on the optimum solution, while step (b) provides an upper bound.

[0057] A mathematical-constraint model for the MC-MR fixed wireless mesh network described above, including channel, node, and-interference constraints, will now be presented. It is assumed that, given a link-flow set f={f_i(e)},f_i(e) is the desired flow on channel iεOC={1, 2, . . . ,C} over link eεE. The objective now is to determine necessary and sufficient conditions for this link-flow vector to be achievable in the network in terms of a valid schedule.

[0058] In order to achieve this link flow, a 0-1 scheduling variable y_i^t(e) is first defined, as follows:

[0059] $y_i^t\left(e\right)=\{\begin{array}{c}1\mathrm{if}\mathrm{link}e\mathrm{is}\mathrm{active}\mathrm{on}\mathrm{channel}i\mathrm{in}\mathrm{time}\mathrm{slot}t\\ 0\mathrm{otherwise}\end{array}$
It is noted that y_i^t(e) is set to 1 if there is a transmission on channel i over link e in time slot t. It is also noted that y_i^t(e)=0, ∀iεOC, ∀t when eεE¹. In other words, interference links do not carry data.

[0060] As to link-channel constraints, by definition, the maximum number of channels that can be active on link e at any time slot t is (e). Thus, the constraint of the following Inequality (1) holds true:

[0061] $\begin{array}{cc}\sum _{i\in \mathrm{OC}}{y}_i^t\left(e\right)\le \varrho \left(e\right),\forall e\in E,\forall t.& \left(1\right)\end{array}$

[0062] As to node-radio constraints, a node can use at most κ(v) radios in a given time slot for transmission, reception, or both transmission and reception, which leads to the constraint of the following Inequality (2):

[0063] $\begin{array}{cc}\sum _{e\in E\left(v\right)}\sum _{i\in \mathrm{OC}}{y}_i^t\left(e\right)\le \kappa \left(v\right),\forall v\in V,\forall t.& \left(2\right)\end{array}$

[0064] As to interference constraints, it is initially assumed that the antennas are omni-directional and that E¹=ø, i.e., there are no interference links in the set. The derivation of the interference constraint using, e.g., the approach in Kodialam, M., and Nandagopal, T., “The Effect of Interference on the Capacity of Multi-hop Wireless Networks,” IEEE Symposium on Information Theory, June 2004, which uses these assumptions, will now be briefly outlined, and will then be extended to cover interference links.

[0065] The IEEE 802.11-based RTS-CTS-DATA-ACK model is considered in order to identify pairs of nodes that can simultaneously transmit. In this model, neighbors of both an intended transmitter and receiver refrain from both transmission and reception. In the ideal case, only transmitters in the neighborhood of the receiver remain silent. While that case can also be modeled using the approach described herein, only the model in which neighbors refrain from both transmission and reception will be used, in order to keep the presentation simple.

[0066] Interference will occur only among users sharing the same channel, e.g., channel i. Given a node v and its neighborhood N(v) in G, one of the links e in E(v) is active on channel i, and node u is the other endpoint of the link. For e to be active on channel i, all other links incident on node v, E(v)\e, are idle, and, in addition, each neighbor of node v remains idle, on channel i. The same argument applies to node u. For silencing N(v), due to the non-overlapping neighborhoods of nodes in N(v), separate constraints are used, as follows:

[0067] $\sum _{e\in E\left(v\right)\bigcup E\left(v^{\prime }\right)}{y}_i^t\left(e\right)\le 1,\forall v^{\prime }\in N\left(v\right),\forall i\in \mathrm{OC},\forall t.$
This is illustrated in FIG. 2(a) for link uv and nodes v₁, V₂εN(v).

[0068] Interestingly, these constraints are the same whenever any link incident on node v is active, since it prevents other links incident on {v}∪N(v) from being active at the same time on the same channel. Therefore, these constraints can be rewritten as follows:

[0069] $\sum _{e\in E\left(v\right)\bigcup E\left(v^{\prime }\right)}{y}_i^t\left(e\right)\le 1,\forall v^{\prime }\in N\left(v\right),\forall v\in V,\forall i\in \mathrm{OC},\forall t.$
This is illustrated in FIG. 2(b) for link vv₁.

[0070] Thus, the interference constraint may be formally stated in terms of a link e, as given in the following Inequality (3):

[0071] $\begin{array}{cc}\sum _{e^{\prime }\in E\left(t\left(e\right)\right)\bigcup E\left(h\left(e\right)\right)}{y}_i^t\left(e^{\prime }\right)\le 1,\forall i\in \mathrm{OC},\forall e\in E,\forall t.& \left(3\right)\end{array}$

[0072] It is noted that, under this approach, there are only |E| interference constraints in all, with the number of variables per constraint never exceeding twice the maximum degree of the graph. The reduction in number of constraints significantly reduces the complexity of modeling interference and increases the convergence speed of any linear optimization problem using these constraints, as will be shown subsequently.

[0073] As to interference links, if there is an interference link, eεE¹ between two nodes v₁ and v₂ on channel i, then whenever one of the data links incident on either of the nodes is active, the other node is silent for that slot on channel i. It can be seen that, if the previous interference constraint is rewritten for an interference link e, then only the data links incident on either of the endpoints can be included. Thus, the interference constraints for the general graph in the following Inequality (4) may be derived, clarifying this distinction:

[0074] $\begin{array}{cc}\sum _{e^{\prime }\in E\left(t\left(e\right)\right)\bigcup E\left(h\left(e\right)\right)}{y}_i^t\left(e^{\prime }\right)\le 1,\forall i\in \mathrm{OC},\forall e\in E\bigcup E^I,\forall t.& \left(4\right)\end{array}$
The following Table 2 lists these three constraints that characterize the MC-MR wireless network G:

[0075]

TABLE 2
Integer Linear Programs:	Linear Programs:
0-1 Variables	Continuous Variables
(Necessary & Sufficient Conditions)	(Necessary Conditions)
ΣiεOCyit(e) ≦ ρ(e), ∀eεE, ∀t	ΣiεOCgi(e) ≦ ρ(e), ∀eεE
ΣeεE(ν)ΣiεOCyit(e) ≦ κ(ν), ∀νεV, ∀t	ΣeεE(ν)ΣiεOCgi(e) ≦ κ(ν), ∀νεV
Σe′εE(t(e))∪E(h(e))yit(e′) ≦ 1, ∀iεOC,	Σe′εE(t(e))∪E(h(e))gi(e′) ≦ 1, ∀iεOC,
∀eεE∪EI, ∀t	∀eεE∪EI

Each of these three constraints characterizes one of a channel constraint, a node constraint, and an interference constraint, respectively, and thus, Inequalities (1), (2), and (4) are conditions, which are both necessary and sufficient, to check for the feasibility of a link schedule in the MC-MR network G.

[0076] While the necessary and sufficient conditions are used to check for the feasibility of link-channel assignments (as will subsequently be explained), the variables in these inequalities are binary variables, and as such, they are inconvenient to use in any optimization problem, as they lead to Integer Linear Programming (ILP) problems that are much harder to solve than linear programs defined on continuous variables. Moreover, the variables are time-indexed, which makes the problem size very large. Therefore, a relaxation of the integer constraints to continuous variables in terms of link flows is desirable.

[0077] Over a period of time [0,T], the fraction of time link e is active on channel i is given by (Σ_t≦Ty_i^t(e))/T . Therefore, the mean flow on channel i over link e is given by the following Equation (5):

[0078] $\begin{array}{cc}{f}_i\left(e\right)=\frac{c_i\left(e\right)\sum _{t\le T}{y}_i^t\left(e\right)}{T}.& \left(5\right)\end{array}$

[0079] The mean utilization g_i(e) of channel i over link e over the period [0,T], has been defined above as g_i(e)=f_i(e)/c_i(e).

[0080] Inequality (1) is summed over all t≦T, the order of summation is interchanged, and the result is divided by T to arrive at:

[0081] $\sum _{i\in \mathrm{OC}}\frac{\sum _{t\le T}{y}_i^t\left(e\right)}{T}\le \varrho \left(e\right),\forall e\in E.$
Now, using Equation (5), the relaxed condition in terms of utilizations and link flows is defined as follows:

[0082] $\sum _{i\in \mathrm{OC}}{g}_i\left(e\right)=\sum _{i\in \mathrm{OC}}\frac{f_i\left(e\right)}{c_i\left(e\right)}\le \varrho \left(e\right),\forall e\in E.$

[0083] The same operations can be performed for the other two necessary and sufficient conditions in Inequalities (2) and (4) to obtain the constraints in terms of link utilizations. Thus, the following Lemma 1 may be stated:

[0084] Lemma 1. For the multi-channel multi-radio multi-hop wireless network under consideration, if a given link-flow set f does not satisfy the following Inequalities (6-8), then the link-flow set f is not schedulable:

[0085] $\begin{array}{cc}\sum _{i\in \mathrm{OC}}{g}_i\left(e\right)\le \varrho \left(e\right),\forall e\in E,& \left(6\right)\\ \sum _{e\in E\left(v\right)}\sum _{i\in \mathrm{OC}}{g}_i\left(e\right)\le \kappa \left(v\right),\forall v\in V,& \left(7\right)\\ \sum _{e^{\prime }\in E\left(t\left(e\right)\right)\bigcup E\left(h\left(e\right)\right)}{g}_i\left(e^{\prime }\right)\le 1,\forall i\in \mathrm{OC},\forall e\in E\bigcup E^I.& \left(8\right)\end{array}$

[0086] Due to the relaxation of the integer variables by averaging, the above Inequalities (6-8) are only necessary conditions and are no longer sufficient conditions. A simple example is a four-cycle ABCDA. If the capacity on each link is 1, then a link flow of 1/3 on each link satisfies the necessary conditions, for a total link utilization of 4/3, but it is not sufficient, since only one link can be active at any time, resulting in a total link utilization of 1. In fact, the gap between the necessary and the optimal conditions can be unbounded, as illustrated by the following example.

[0087] The network shown in FIG. 3, operating on a single channel with one radio per node, will now be considered. In this network, K_2m,m′ represents a complete bipartite graph with 2m vertices in one partition and m′ vertices in another partition, with m′<2m. There are a total of 2m(m′+1)+1 links in the network, all with capacity 1 each. Taking into account all of the necessary conditions, a maximum flow of 1=(m+m′+1) over each link is feasible, resulting in an aggregate link utilization of

[0088] $\frac{2m\left(m^{\prime }+1\right)+1}{m+m^{\prime }+1}=\frac{2\left(m^{\prime }+1\right)+\frac{1}{m}}{\left(1+\frac{1+m^{\prime }}{m}\right)}=O\left(m^{\prime }\right).$

[0089] However, only one link can be active at any time in this network due to interference. This may be seen by considering any link e. The end-points of e are either (i) both A and B or (ii) one of the 2m nodes in the middle. If e=AB, then none of the 2m nodes in the middle can be transmitting or receiving data, thereby silencing the rest of the network. If one of these 2m nodes is communicating with either A or B, then all of the m′ nodes on the right are silent, and this, in turn, implies that the remaining (2m−1) nodes in the middle are silent. The same argument applies if one of nodes in the middle is communicating with one of the nodes on the right. Accordingly, the total optimal link utilization is 1. Thus, the difference between the solution that merely satisfies the necessary conditions and the optimum solution is O(m′), which can be unbounded as m increases.

[0090] Other such configurations are possible, e.g., complete subgraphs (cliques), odd cycles, etc. A complete characterization of these so-called “forbidden” subgraphs may be impractical. (A common characteristic among all forbidden subgraphs is the existence of cycles. It is possible, therefore, that if graph G is a tree, then the relaxed necessary conditions might also be sufficient. Accordingly, there should be no interference links in G and no path redundancy. Since this has no practical application, it will not be further discussed herein.) However, what is important is that the ILP constraints in Table 2 are both necessary and sufficient for any network graph. The gap arises only due to relaxation of the integer constraints. Any solution satisfying the necessary conditions will be an upper bound of the optimal solution. Therefore, by using these necessary conditions as optimization constraints, upper performance bounds can be derived, and then a feasible lower bound can be computed using channel assignment and scheduling, based on the solution from the optimization problem. This approach will mitigate the impact of the optimality gap.

[0091] It is noted that all of the constraints described above have a common structure, namely, sets composed of (link, channel) pairs, S₁, S₂, . . . , Sthat are defined on links e and colors iεOC. The necessary and sufficient conditions (using binary variables) take the general form Σ_(e,i)εSj y_i^t(e)≦β(S_j), ∀j, while the necessary conditions (using continuous variables) have the general form Σ_(e,i)εSj g_i(e)≦β(S_j), ∀j, where β(S_j) is the right-hand side constant associated with the constraint identified by that set. For example, β(S_j)=1 for the sets identified by the interference constraints, and β(S_j)=κ(v) for the sets identified by the node-radio constraints.

[0092] The following Lemma 2 is a restatement of Lemma 1 in a generic form:

[0093] Lemma 2. Let S₁, S₂, . . . , Srepresent sets of (link, channel) pairs identified by the constraints in Lemma 1, with , β(S_j) being the associated constant for each set S_j. Let f represent a link-flow set {f_i(e)}, where f_i(e) represents the flow on channel i over link e. If f does not satisfy the following Inequality (9), then link-flow set f is not schedulable:

[0094] $\begin{array}{cc}\frac{1}{\beta \left(S_j\right)}\sum _{\left(e,i\right)\in S_j}{g}_i\left(e\right)\le 1,\forall j\in \left\{1,2,\dots ,ℒ\right\}.& \left(9\right)\end{array}$

[0095] Given the foregoing set of constraints that characterize an MC-MR wireless mesh network, the problem of optimization of throughput criteria subject to these constraints may now be addressed.

[0096] A standard multi-commodity flow problem on the MC-MR network is defined as follows: a set of sources s want to send data to a set of destinations d with an end-to-end rate demand vector r. There might be multiple objectives of interest to the network planner, e.g., (a) achievability of the demand vector, (b) maximizing aggregate network throughput or the sum of end-to-end rates subject to minimum rate requirements, (c) maximizing the minimum end-to-end rate, (d) maximizing the aggregate utility function of the end-to-end rates, and/or (e) imposing certain fairness criteria on the rates in the network. All of these problems can be solved using the framework described herein. First, the constraints identified earlier from link-flow variables are translated to end-to-end rate variables.

[0097] It is assumed that the traffic demand for different source-destination pairs is given in the form of a rate vector r. It is assumed that rate vector r (depending on the optimization objective, r can also be set to 0) has Q<n(n−1) components. Each source-destination pair between which there is a request will be termed a commodity. The variable q will be used to index the commodities, wherein s(q) represents the source node for commodity q and d(q) the destination node for commodity q. The variable r(q) represents the flow to be routed from s(q) to d(q). The following optimization problem is to be solved:

• • [0098] INPUT: A directed graph G=(V,E,E¹) with a link speed c_i(e) for channel iεOC, data link eεE, Q node pairs (s(q),d(q)), and a desired rate r(q) associated with each node pair q.
  • [0099] OUTPUT: Either (i) a set of routes, link-channel assignments, and associated schedule that achieves the given rates, or else (ii) declare the problem infeasible.
    Recalling that multiple paths can exist between s(q) and d(q) for each commodity q, the result set forth in the following Theorem 3 can be shown:

[0100] Theorem 3. Given a graph G=(V,E,E¹), with link speed c_i(e) associated with data link eεE and channel iεOC, and Q source-destination pairs (s(q),d(q)) for q=1, 2, . . . , Q with a desired flow rate r(q) between s(q) and d(q), let x_i^q (e) be the flow on channel i over data link e that belongs to end-to-end flow q. A necessary condition for rate vector r to be achievable is the existence of link flows x_i^q (e), ∀i,q,e that satisfy the following constraints:

[0101] $\sum _{e\text{:}t\left(e\right)=s\left(q\right)}\sum _{i\in \mathrm{OC}}{x}_i^q\left(e\right)=r\left(q\right),\forall q,\sum _{e\in E_{\mathrm{in}}\left(v\right)}\sum _{i\in \mathrm{OC}}{x}_i^q\left(e\right)=\sum _{e\in E_{\mathrm{out}}\left(v\right)}\sum _{i\in \mathrm{OC}}{x}_i^q\left(e\right),\forall v\ne s\left(q\right),d\left(q\right),\forall q,\frac{1}{\beta \left(S_j\right)}\sum _{\left(e,i\right)\in S_j}\frac{\sum _{q\le Q}{x}_i^q\left(e\right)}{c_i\left(e\right)}\le 1,\forall q,j.$
The first constraint ensures that the end-to-end rate is met. The second constraint maintains flow balance at intermediate nodes in the network for each end-to-end flow. The third constraint is a restatement of Inequality (9) in terms of x_i^q (e), since f_i (e)=Σ_q≦Qx_i^q (e).

[0102] An alternative formulation of the above conditions is an arc-path formulation. If P_q represents the set of (link, channel) pairs for source-destination pair q, and considering a path PεP_q, with x(P) representing the amount of flow sent on path P, this path leads from s(q) to d(q). From the demand requirements, it is noted that

[0103] $\sum _{P\in {𝒫}_q}x\left(P\right)=r\left(q\right),\forall q.$
The total amount of flow on channel i over link e, represented by f_i(e) is given by

[0104] $f_i\left(e\right)=\sum _q\sum _{P\in {𝒫}_q\text{:}\left(e,i\right)\in P}x\left(P\right).$

[0105] The variable I(Pj) represents the set of (link, channel) pairs that are on path P and are also in set Sj , i.e., I(P, j)={(e,i):(e,i)εP}∩{(e,i):(e,i)εS_j}. Since f_i(e)=g_i(e)c_i(e), from Inequality (9), the amount of flow permitted by set S_j on path P is given by

[0106] $F\left(P,j\right)=\beta \left(S_j\right){\left(\sum _{e\in I\left(P,j\right)}\frac{1}{c_i\left(e\right)}\right)}^{-1}.$
The flow that can be sent on path P is denoted by F(P)=min_jεF(Pj). The variable F( ) represents flow on paths and the variable f( ) represents flow on links. The necessary conditions for a rate vector r to be achievable are given by

[0107] $\sum _{P\in {𝒫}_q}x\left(P\right)=r\left(q\right),\forall q,\sum _{\left(e,i\right)\in S_j}\frac{\sum _q\sum _{P\in {𝒫}_q\text{:}P\ni \left(e,i\right)}x\left(P\right)}{\beta \left(S_j\right)c_i\left(e\right)}\le 1,\forall j\in \left\{1,2,\dots ,ℒ\right\}.$
Given a rate vector r, the strategy then is to solve for the x variables that satisfy the necessary conditions.

[0108] As mentioned above, there are many objectives of interest for the network capacity planner that can be solved using an optimization framework. Each objective is associated with some additional constraints that are specific to the chosen objective. For example, maximizing the sum of end-to-end rates might be associated with a minimum rate constraint for each source-destination pair.

[0109] The characterization of certain embodiments of the present invention permits these constraints to be “plugged in” to the optimization problem, together with necessary rate constraints identified above, to obtain an upper bound on the performance for that objective.

[0110] To demonstrate the flexibility of the approach of certain embodiments of the present invention, the fundamental optimization problem of feasibility is considered, i.e., whether a given rate-demand vector can be achieved in the network. The optimization framework of certain embodiments of the present invention is used to derive upper bounds, and the procedure to obtain lower bounds for this problem will be described below.

[0111] Instead of solving the feasibility problem directly, the feasibility problem is instead written in the form of a concurrent flow problem. In this concurrent flow problem, the desired rate vector is scaled, and the objective is to determine the maximum scaling factor that still satisfies the necessary conditions. It is noted that there can be an exponential number of paths between two given nodes in the network, resulting in an exponential number of variables in the path-arc formulation. A formulation consistent with certain embodiments of the present invention permits avoidance of this problem, however, using a primal-dual approach based on shortest-path routing.

[0112] First, the feasibility problem is written as a concurrent flow problem, and then a primal-dual algorithm is used to solve the linear programming problem.

[0113] The primal and dual problems and solutions may be characterized as follows:

[0114] 1. If the primal problem has a variables and b resource constraints, then the dual problem will have b variables and a resource constraints, where the constraint matrix of the dual problem is the transpose of the constraint matrix of the primal problem.

[0115] 2. There is a one-to-one correspondence between the primal constraints and the dual variables, i.e., a variable in the dual problem is paired with an inequality in the primal problem, and similarly for the primal variables and the dual constraints.

[0116] 3. The objective function of the dual problem is determined by the right-hand side of the primal constraints, and similarly for the objective function of the primal problem and the right-hand side of the dual constraints.

[0117] The problem of determining the achievability of rate vector r can be formulated as the following exemplary Linear Programming Formulation (I):

• • [0118] maximize λ, subject to:

[0119] $\begin{array}{cc}\sum _{\left(e,i\right)\in S_j}\frac{\sum _q\sum _{P\in {𝒫}_q\text{:}P\ni \left(e,i\right)}x\left(P\right)}{\beta \left(S_j\right)c_i\left(e\right)}\le 1,\forall j\in \left\{1,2,\dots ,L\right\},\sum _{P\in P_q}x\left(P\right)=1r\left(q\right),\forall q,x\left(P\right)\ge 0,\forall P\in P_q,\forall q.& \left(I\right)\end{array}$

[0120] The optimal solution to the linear programming problem above is represented by λ*, which represents the maximum scaling factor by which flows can be scaled up and still satisfy the necessary constraints. Therefore, if λ*<1, then the rate vector is not feasible. The largest rate vector that still satisfies the necessary constraints is λ* r, given by the optimal path flow vector x*. Given a slot length of r seconds, a determination is made whether r bits can be scheduled in a schedule of length at most 1/τ. Thus, if L* is the smallest length of a schedule that can schedule x*=λ* r bits, then the schedule corresponds to a flow vector

[0121] $\frac{{\lambda }^{*}\stackrel{\_}{r}}{L^{*}\tau }.$
For this achievable flow to be at least r, λ* should be greater than or equal to L*τ. The sufficiency gap created by relaxing the integer constraints (given by Inequalities (1), (2), and (4)) is denoted by the interval [1, L*τ), which represents the interval during which the existence of a schedule cannot be guaranteed.

[0122] The dual to this problem will now be formulated, and a fully-polynomial time-approximation algorithm (FPTAS) will be computed using a primal-dual algorithm. The FPTAS' algorithm and its analysis follows, e.g., as in the method presented in Garg, N., and Könemann, J., “Faster and Simpler Algorithms for Multi-commodity Flow and other Fractional Packing Problems,” Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp.300-309, 1998.

[0123] The dual to the linear program set forth above assigns a weight a(u) to each set Sj in the network, and the dual variable z(q) for the rate-scaling constraint (the second set of constraints) in the linear program, as follows:

[0124] $\mathrm{minimize}\sum _j\alpha \left(j\right),\mathrm{subject}\mathrm{to}\text{:}$ $\sum _{\left(e,i\right)\in P}\frac{\sum _{j\text{:}\left(e,i\right)\in S_j}\alpha \left(j\right)/\beta \left(S_j\right)}{c_{i\left(e\right)}}\ge z\left(q\right),\forall P\in {𝒫}_q,\forall q,\sum _{q=1}^{Q}r\left(q\right)z\left(q\right)\ge 1,\alpha \left(j\right)\ge 0,\forall j\in \left\{1,\dots ,ℒ\right\}.$

[0125] FIG. 4 shows exemplary pseudo-code for implementing an algorithm to solve this primal-dual program in order to solve the sizing problem, which starts by assigning a weight of δ to all sets S_j. The algorithm proceeds in phases. In each phase, for each commodity q, r(q) units of flow are routed from s(q) to d(q). A phase ends when commodity Q is routed. The r(q) units of flow from s(q) to d(q) for commodity q are sent via multiple iterations. In each iteration, a path P* from s(q) to d(q) is determined, and F(P*) represents the capacity of this path. A flow of at most F(P*) units can be sent during this iteration. Since r(q) units of flow are sent for commodity q in each phase, the actual amount of flow sent is the lesser of (i) F(P*) and (ii) the remaining amount of flow to make up r(q) in this phase. Once the flow is sent, the weights of the nodes that carry the flow are increased. The algorithm then alternates between sending flow along shortest-path pairs and adjusting the length of the links along which flow has been sent, until the optimal solution is reached. Therefore, the primal-dual algorithm solves a sequence of shortest-path problems. It can be shown that, by choosing ε and δ appropriately, the optimal solution can be approximated as closely as desired. The running time increases with the accuracy needed. The following Theorem 4 states the running time and the correctness of the algorithm set forth in the pseudo-code of FIG. 4.

[0126] Theorem 4. The algorithm in FIG. 4 computes a (1−ε)⁻³-optimal solution to the flow-scaling problem in time that is polynomial in Q, , n, and 1/ε, where Q is the number of commodities, is the number of constraining sets, and n is the number of nodes.

[0127] The linear program described above gives an upper bound on the achievable rates in the mesh network. The solution to this linear program is used to assign channels to the links and also to schedule the time slots in which each link and channel are active. Both of these problems are NP-hard, and variations of the greedy approach may be used to solve the problem. There are two versions of this problem that are solved herein. The first version is the Static Link-Channel Assignment Problem, wherein link-channel assignments are made to the links at the beginning and subsequently remain fixed over all time slots. The second version of the problem, which assigns channels to links every T_d slots (T_d≧1), is the Dynamic Link-Channel Assignment problem. The dynamic link-channel assignment results for the case of T_d=1 will provide a basis for comparison of the performance of all link-channel assignment algorithms, since it provides the maximum flexibility in link-channel assignment and scheduling. The following discussion assumes that only one channel can be allotted to a given link, i.e., a (node, neighbor) pair. In other words, (e)=1∀eεE. The algorithms set forth herein can be easily generalized for (e)>1. The GCS algorithm (described below) is a generalization of the Dynamic-Link Assignment case when (e)>1.

[0128] In the Balanced Static-Channel Assignment (BSCA) algorithm, an (almost) greedy approach is first used in solving the static-channel assignment problem. Once this link-channel assignment is done, time slots are assigned to each channel using a coloring algorithm. This assignment of time slots to channels is done almost independently for each channel. The channels interact during assignment of time slots only to resolve the node-radio constraint (Inequality (2)) at each node in the network. Recalling that network model constraints are modeled by sets S₁, S₂, . . . , S_Λ, these sets are specified by (link, channel) pairs. If the link-channel assignment results in a large number of channels being assigned to one set, then a large number of time slots will be used to resolve the conflicts in this set, which will result in an inefficient schedule. Therefore, the main idea behind the BSCA is to ensure that none of the constraint sets are loaded by any channel. Accordingly, the total load that is assigned to each constraint set is tracked. At the end of solving the linear programming problem, {circumflex over (x)}_i^q (e) represents the flow on link e corresponding to commodity q and channel i. First, f_i(e), which represents the flow on link e corresponding to channel i and all commodities q, is determined as

[0129] $f_i\left(e\right)=\sum _{q\le Q}{\hat{x}}_i^q\left(e\right).$
Given a particular link e, T(e,i) denotes the constraint sets that contain pair (e,i). The variable l_s, which denotes the total flow that has been assigned to constraint set S, is initialized to zero for all sets. At a generic step in the algorithm, it is assumed that a channel is to be assigned to link e. (An elaboration of how this link is selected will be described below.) First, it is determined, for each channel iεOC, that m(e,i)=max_SεT(e.i) l_S, representing the maximum load on any constraint set that contains the (link, channel) pair (e,i). Then, link e is assigned to channel j that attains the minimum value of m(e,i) over all channels. That is to say, link e is assigned to the channel j, where j=arg min_i m(e,i). Once this is done, the flow on all of the sets in T(e,j) is incremented by Σ_if_i(e), since all of the flow on link e becomes assigned to channel j. As stated earlier, the main intuition behind the scheme is to not allow any interference set to be overloaded with any channel. This is the reason for selecting a min-max allocation, since it ensures that the load on the constraint sets is distributed as much as possible among the given channels.

[0130] The inventors experimented with three different methods of selecting link e: (1) selecting a link at random, (2) selecting links in a predetermined order, and (3) selecting a link whose min_i m(e,i) is the lowest. From these experiments, it has been determined that the third option outperforms the first two, and all of the results given below reflect this implementation.

[0131] FIG. 5 shows exemplary pseudo-code for implementing a Balanced Static-Channel Assignment algorithm consistent with one embodiment of the present invention. At the end of static link-channel assignment, the result is a set of flows assigned to links that have been assigned to a particular channel. All of the flows are then scaled so that they are integers. All of the flows are multiplied by a large number M, with the fractional part ignored. Time slots are then assigned to each channel separately, while ensuring that the node-radio constraint is met, so that the number of active links incident on a node in a given time slot is always, at most, the number of radios at the node. This is done via a greedy coloring algorithm applied to each channel separately.

[0132] A link e is assigned to channel i with a scaled flow f_i′(e). The collection of constraint sets that contain pair (e,i) is represented by T_l(e,i). The greedy coloring algorithm is as follows:

[0133] 1. The link e with the highest residual flow f_i′(e) is considered;

[0134] 2. The smallest color (time slot) k that does not occur more than β(S_j) times in set S_jεT₁(e,i), ∀j is assigned;

[0135] 3. Smallest color k is added to all sets in T₁(e,i);

[0136] 4. The scaled flow is reduced by c_i(e)τ, where τ is the length of a time slot; and

[0137] 5. Steps 1-4 are repeated until all flows have been scheduled.

[0138] If NS denotes the maximum number of time slots taken by any channel, then the demand met by this system is given by

[0139] $\frac{M}{\mathrm{NS}}\lambda *\stackrel{\_}{r},$
where λ* r is the linear-program-optimal solution, and M is the multiplicative factor used to convert the link flows to integer values.

[0140] In static link-channel assignment, it is assumed that each link is assigned to a channel, and that channels cannot be switched during different time slots. In dynamic link-channel assignment, it is assumed that every link has the ability to switch channels once every T_d time slots (T_d≧1). The channels still should respect the constraints imposed by Inequalities (1), (2), and (4). This implies that, apart from the coordination of the nodes at the end of the links, there is coordination across different links to perform link-channel assignment at the beginning of each time period. Though this may be difficult in practice, when T_d=1, dynamic link-channel assignment gives the highest flexibility to maximize the achievable performance for any link channel-assignment scheme.

[0141] Since the problem of determining the optimal link-channel assignment is NP-hard, a packing-based heuristic may be used to approximate the optimal solution. The desired flow on link e corresponding to channel i is represented by f_i(e)=Σ_q≦Q{circumflex over (x)}_i^q(e). Once the solution of the linear programming problem is obtained, all of the link flows are scaled to make them integers. If all of the data is rational, then the solution of the linear program is rational and therefore can be scaled to integers. Since a primal-dual scheme is being used, the answers will be fractional, and therefore, the flows are scaled by a suitably large value M, so that the eliminated fractional portion is negligible. (In the experiments described herein, M=100.) Once these flows are obtained, the objective is to assign these flows to channels in as few time periods as possible.

[0142] In the Packing Dynamic-Channel Assignment (PDCA) algorithm consistent with one embodiment of the invention, flows are packed in a greedy manner in each time period. In this embodiment, each link can be assigned to only one channel in each time period. Since the link flows do not necessarily have to be assigned to channels that are given by the solution to the linear program, all of the flows on the different channels on a given link can first be aggregated into a single scaled flow on the link denoted by f^M (e)=Σ_if_i(e). As the flows are packed in each time period, the amount of unassigned flow on link e is denoted by d(e). At the beginning of each time period T_d, the links are sorted in descending order of the unassigned flows. The first link e is assigned to the channel j=arg max_i c_i(e), and the value of d(e) is decremented by c_j(e)T_d. Then, a determination is made whether the next link in the ordered list can be assigned to some channel in this time period. If this can be done, then such a channel with the highest capacity is selected and the link is assigned to that channel. If this link cannot be assigned to any channel, then this process is attempted for the next link, and is repeated until the end of the list is reached. If there are still unassigned flows, this process moves to the next time period, and the link assignment process is repeated. The objective is to assign all flows in as few time periods as possible.

[0143] One way to determine whether a particular channel is feasible for a data link in a time period is by having a binary variable z_S associated with each constraint set S. At the beginning of each time period of length T_d, binary variable z_S is set to zero. Whenever a data link e is assigned channel i and (e,i)εS, binary variable z_S is set to 1. It is also ensured that the node-radio constraint is respected at each node by verifying that the number of channels allocated to a given node in any time period is not greater than the number of radios at that node.

[0144] FIG. 6 shows exemplary pseudo-code for implementing a PDCA algorithm, wherein T(e,i) is used to denote the collection of constraint sets that are associated with link-channel pair (e,i), and NS is used to count the number of time periods. As in the static-channel allocation, the demand met by the system is computed as

[0145] $\frac{M}{\mathrm{NS}}\lambda *\stackrel{\_}{r},$
where λ* r is the optimal solution to the linear program, and M is the multiplicative factor used to convert the link flows to integer values.

[0146] Results of simulations evaluating the performance of certain embodiments of the present invention will now be discussed, highlighting the following three aspects:

[0147] 1. The ability of the necessary conditions, based on continuous flow variables, to model the capacity of the network in practical circumstances;

[0148] 2. The performance of the (dynamic) PDCA algorithm for T_d=1 with respect to the capacity of the network; and

[0149] 3. The performance of the simpler (static) BSCA algorithm along with greedy scheduling with respect to the dynamic link-channel assignment algorithm.

[0150] While the algorithms presented herein were evaluated for various random topologies, grids, full meshes, and other types of topologies, results from only grids and random topologies will be discussed. As has been previously discussed, in these simulations, (e)=1,∀eεE. Also, only networks with no separate interference links, i.e., E¹=Ø, were considered. In all of the experiments, the number of radios per node were set to be the same across all nodes, i.e., κ(v)=κ, ∀vεV, and the links were set to be of unit capacity for all channels, c_i(e)=1,∀iεOC, ∀eεE. It is also noted that all channels were orthogonal. Wireless-channel errors were not modeled, since the goal was to estimate the maximum capacity of the network.

[0151] First, a fixed 5×6 grid topology with 30 nodes was considered, with each node having, at most, 4 neighbors in the grid. The grid was divided into four quadrants, and one node in each quadrant was assigned to be a sink node for flows. Then, for each node in the grid, the closest sink node was assigned as the destination for its flow, with all flows having a demand of 1 unit.

[0152] The number of flows in the grid was varied from 5 to 25. Three parameters were measured for each set of flows: (a) the capacity upper bound, (b) the BSCA (static assignment) lower bound, and (c) the PDCA (dynamic assignment) lower bound. All of these values were given in terms of the scaling factor λ by which the demands were scaled in order to make the scaled demand vector feasible in the network. FIGS. 7, 8, and 9 show the simulation results, with each data point representing the average of the performance attained by varying the number of flows (5, 10, 15, 20, 25) in the grid.

[0153] In FIG. 7, the y-axis is normalized with respect to the upper bound for the case of 1 radio per node and 1 channel. Since the maximum degree of a node in the grid is only 4, the number of radios was varied from 1 to 4, and the number of channels was varied from 1 to 10. From FIG. 7, it can be seen that the capacity curve is convex, as might be expected. However, an interesting observation emerges from this data. Given κ radios per node, the capacity increases almost linearly up to κ+1 channels. This is counter-intuitive, since it would be expected that the near-linear capacity increase would stop after κ channels. The results seem to indicate that this trend continues for one additional channel. This pattern is not observed when the number of radios is 4, since the maximum degree of nodes is only 4, and only one channel can be assigned for each link to a neighbor ((e)=1).

[0154] In FIG. 8, the performance of the PDCA algorithm is compared for T_d=1 with respect to the upper bound. Recalling that the performance of the link-channel assignment algorithm is given by

[0155] $\frac{M}{\mathrm{NS}}\lambda *\stackrel{\_}{r},$
where λ* r is the upper bound from the linear program,

[0156] $\frac{M}{\mathrm{NS}}$
is thus plotted as a percentage in this plot. Once again, the values were averaged over multiple flow sets. It is evident that when channels are assigned dynamically at every time period, the PDCA algorithm performs within 80% of the capacity upper bound. The algorithm, in fact, achieves close to the capacity when the number of channels exceeds the number of radios by 2. This is a result of the flexibility in packing afforded by the greater number of channels.

[0157] In FIG. 9, the performance of the static BSCA algorithm is evaluated with respect to the PDCA algorithm. It can be seen that the BSCA algorithm does not really match the PDCA algorithm even when the number of channels is increased. However, this is to be expected, since, once the channels are bound, the greedy-coloring-based scheduling algorithm will account for most of the sub-optimal behavior. It is noted that, when there is only one channel in the network, the greedy coloring is the cause for the performance penalty. While this penalty is reduced when more channels are available, it still remains a significant component. In spite of this, the BSCA algorithm still performs within 60% of the PDCA algorithm.

[0158] The PDCA and BSCA algorithms were also tested on randomly-generated connected-graph topologies. The sources and destinations were randomly chosen in this scenario, as opposed to the grid corresponding to FIGS. 7, 8, and 9. The numbers of nodes, links, and flows in the graphs were varied, and correlation was measured between various graph parameters, such as maximum and average degree, maximum and average path length of flows, and connectivity of the graph to the solutions generated by the linear program and the PDCA and BSCA algorithms. Ten random-graph topologies were tested. The number of nodes in random graphs varied from 15 to 50, with the average node degree varying from 3 to 9. The maximum degree of the graph varied from 7 to 20, while the connectivity of the graphs varied from 1 to 4. The path length of the flows ranged from 1 to 10. The results suggest that the relative performance of the algorithms with respect to the linear program was not dependent on any combination of the above graph parameters.

[0159] The results from these experiments are presented in FIGS. 10, 11, and 12. The y-axes in all of these figures show that the performance (feasible demand-scaling factor) is normalized with respect to that of the capacity upper bound for (link, channel)=(1, 1). Each data point was averaged over the 10 random graph topologies.

[0160] FIG. 10 shows that the capacity increases almost linearly with κradios for up to κ+1 channels. This suggests that, in order to make the best use of X available orthogonal channels, at least X−1 radios per node may be needed. The gains in capacity diminish quickly beyond this point. Based on Kyasanur, P., and Vaidya, N., “Capacity of Multi-Channel Wireless Networks: Impact of Number of Channels and Interfaces,” ACM Mobicom, 2005, it is observed that, in this model, a linear increase in capacity can be expected, as long as the ratio of X/κ is O(log n). The results tend to agree with this observation in both the grid and random-graph topologies.

[0161] FIGS. 11 and 12 show the performance of the PDCA and BSCA algorithms for the random graphs. The results show that, while the trend in capacity improvement is similar to that of the upper bounds, the PDCA algorithm uses more channels to achieve the same gain as the upper bound, and the BSCA algorithm uses even more channels than the PDCA algorithm. Interestingly, in both algorithms, the performance with 3 or 4 radios is similar to the performance for up to 5 channels. The performance in this case will differ when more channels are included.

[0162] In FIG. 13, the PDCA algorithm is compared with the capacity upper bound, and it is found to achieve 75% of the upper bound on the average. The worst-case performance that was observed with PDCA in all tested topologies was 55% of the capacity upper bound. Another interesting fact is that, if there are fewer channels than the number of radios per node, then the relative performance of the link-channel assignment algorithms decreases with an increasing number of channels. The relative performance improves steadily beyond a certain point until it saturates at a latter point. This pattern is observed even in the results for the grid topology of the previous example, and for both the PDCA and BSCA algorithms. This is believed to reflect the efficiencies in these algorithms.

[0163] In FIG. 14, similar results are shown for the performance of the BSCA algorithm versus that of the PDCA algorithm. The BSCA algorithm performs, in the worst case, within 50% of the PDCA algorithm, based on the experimental observations. It is noted that the small gap between the capacity upper bound and the PDCA performance implies not only that the PDCA performs close to capacity, but also that the linear program models the achievable capacity with good accuracy. Thus, the relaxation of the integer constraints in Inequalities (1), (2) and (4) to flow constraints in Lemma 1 does not significantly penalize the model for practical instances of wireless mesh networks.

[0164] The network modeling described above may be extended in at least several respects. In a practical wireless network scenario, there might be directional antennas at some nodes, and the network might use heterogeneous radios as part of the multiple-orthogonal channel regime. For example, 802.11b and 802.11a radios may co-exist in the network, for a total of 3+12=15 orthogonal channels. However, if a node has two 802.11b radios and one 802.11a radio, then the two 802.11b transceivers share only the three channels, while the one 802.11a radio has the flexibility of choosing any one of the 12 channels. These restrictions should be modeled in any network characterization.

[0165] As to heterogeneous radios, it is assumed that there are M different radio systems in the network. In the model presented above, the interference constraints remain unchanged, since they are specified for each individual channel. The link-channel and node-radio constraints given by Inequalities (1) and (2), respectively, may be rewritten as follows. For radio system j, where j=1,2, . . . , M, OC_j is the channel set, C_j is the number of channels, _j(e) is the maximum number of channels over link e, and κ(e) is the number of radios at node v, these radio-system-indexed variables can be substituted in place in the link-channel and node-radio constraints and can be specified for every radio system in the network to obtain the constraints for a heterogeneous radio network. The relaxation to continuous variables follows similarly, using radio-system-indexed parameters. However, the link-channel allocation algorithms should be redesigned to accommodate the splitting of link flows between the various radio systems.

[0166] Directional antennas may be used to reduce interference between links, apart from other uses. The impact of including directional antennas is felt in the interference constraints. The constraint described in Inequality (4) represents a group of mutually-interfering links. With directional antennas leading to directional data and interference links, this is no longer true. Instead of considering all links incident on two neighbors as mutual interferers, a subset of these links are treated as mutual interferers. To deal with this, the approach proposed above may be combined, e.g., with the modeling used in Jain, K., Padhye, J., Padmanabhan, V., and Qiu, L., “Impact of Interference on Multi-hop Wireless Network Performance,” ACM Mobicom, September 2003. The set of links incident on either endpoint of a given link e are taken as a subgraph, and the conflict graph for this restricted subgraph is derived. Then, the maximal subgraphs are computed, and the interference constraints can be written for each link represented in the subgraph. Since this is done on a smaller subgraph, this approach is more scalable than the original approach proposed by Jain, Padhye, et al. The main observation is that the proposed model is extremely flexible and permits accommodation of a wide range of network constraints.

[0167] Thus, a network characterization has been presented that captures the constraints associated with multi-channel multi-radio (MC-MR) multi-hop wireless mesh networks. The model presented herein is extensible and can cover a wide variety of cases that reflect a range of practical constraints. An algorithm was presented that computes the optimal routes for a given objective of meeting a set of demands in the network using a set of necessary conditions as constraints. The approach used herein can be applied to optimize many other objective functions. Two link-channel assignment algorithms were also proposed, one static and the other dynamic, which permit the scheduling of flows on the links in the network. Simulations demonstrated that the proposed routing, link-channel assignment, and scheduling algorithms are able to characterize network capacity and achieve a performance that is close to optimal.

[0168] Accordingly, the teachings of certain embodiments of the present invention are believed to provide valuable tools for network designers in planning network deployment and in controlling performance objectives in the emerging field of wireless mesh networks.

[0169] A method consistent with one embodiment of the present invention may provide one or more of the advantages of more efficient utilization of network capacity, reduced congestion at network nodes, and higher packet throughput of the network. The method may be implemented for a requested path by either a centralized network management system (e.g., using a centralized server, such as the gateway of FIG. 1, to implement the method at a single node to serve the entire network), or by each node of the network (e.g., using a server implementing the method at each node), or both. An implementation employing a centralized network management system that distributes results to network nodes may be preferred for coordination of provisioning of new paths. A distributed implementation in each node of the network may be preferred when no centralized network management system exists and/or if the requested path is a distributed request implemented with control packets routed through a network.

[0170] The Greedy Channel-Scheduling (GCS) Algorithm is another embodiment of a dynamic channel-assignment algorithm, in which a link can be assigned to multiple channels in a given time period, i.e., (e)≧1. The linear program described above with regard to the PDCA algorithm, e.g., as given in Linear Programming Formulation (I), provides an upper bound on the achievable rates in the mesh network. The linear programming solution is used to assign channels to the links and also to schedule the time periods in which each link and channel is active. Both of these problems are NP-hard. As a first-cut approach, a variation of the greedy coloring algorithm proposed above is used to solve the problem. However, unlike the algorithm set forth above, the following greedy algorithm is simpler, due to the fact that there are no restrictions on the number of channels that can be assigned simultaneously to a particular link. The following solution approximates the optimal solution by using a greedy packing-based heuristic.

[0171] The desired flow in link e corresponding to channel i is represented by the equation f_i(e)=Σ_q≦Q{circumflex over (x)}_i^q(e). Since the link flows do not necessarily have to be assigned to channels that are provided by the linear program solution, all of the flows on the different channels on a given link can first be aggregated into a single scaled flow on the link denoted by the equation f^M(e)=MΣ_if_i(e). The value of M was set to 100 in experiments performed by the inventors, in order to make the fractional part negligible. As the flows are packed in each time period, the amount of unassigned flow on link e is denoted by the variable d(e).

[0172] At the beginning of each time period, the links are sorted in descending order of the unassigned flows. The first link e is assigned to the channel j=arg max_i c_i (e), and the value of d(e) is decremented by c_j (e)T_d. It is then determined whether the next link in the ordered list can be assigned to some channel in this time period. If so, then such a channel is selected having the highest capacity, and the link is assigned to that channel. If this link cannot be assigned to any channel, then the algorithm moves on to the next link, and this procedure is repeated until the end of the list is reached. The foregoing procedure is then repeated until no channels have been assigned to any link in an iteration. If unassigned flows still remain, then the algorithm moves on to the next time period, and the assignment process is repeated. The objective is to assign all flows in as few time periods as possible.

[0173] To determine whether a particular channel is feasible for a data link in a given time period, a binary variable z_s is associated with each constraint set S. At the beginning of each time period, z_s is set to zero. The variable z_s is set to one whenever a data link e is assigned channel i, and (e,i)εS. It is ensured that the node-ratio constraint is respected at each node by verifying that the number of channels allocated to a given node in any time period is not greater than the number of radios at that node.

[0174] FIG. 15 shows exemplary pseudo-code for implementing the foregoing-described greedy scheduling algorithm. In this algorithm, the variable T(e,i) is used to denote the collection of constraint sets that are associated with the link-channel pair (e,i), and the variable NS is used to count the number of time periods. The demand met by the system is computed as

[0175] $\frac{M}{\mathrm{NS}}{\lambda }^{*}\stackrel{\_}{r},$
where λ* r is the optimal solution to the linear program, and M is the multiplicative factor used to convert the link flows to integral values.

[0176] Using simulations, the performance of the foregoing-described greedy channel-scheduling algorithm was quantitatively evaluated against the upper bounds on capacity derived using the optimization framework described above. Three key aspects are highlighted: (i) the ability of the necessary conditions based on continuous flow variables to model the capacity of the network in practical circumstances, (ii) the performance of the greedy channel-scheduling algorithm with respect to the capacity of the network, and (iii) the variation in achievable channel capacity as the number of radios ad channels vary. In the simulations, mesh network topologies were simulated wherein the product of the number of links and the number of orthogonal channels did not exceed 10,000.

[0177] The goal of the test methodology was to measure the achievable capacity for a large network. The optimization framework allowed for a multi-commodity flow problem formulation. Therefore, each node was permitted to select a randomly chosen node as its destination, and a demand of 1 unit of flow, end-to-end, for all source-destination pairs, was set. When the feasibility/concurrent flow problem was solved in this scenario, a scaling factor λ* was obtained, which implies that all end-to-end flows can send at most λ* units of flow. Thus, the total network capacity was upper-bounded as n.λ*. The greedy channel-scheduling algorithm was then run to obtain an achievable schedule, and a lower bound on the capacity from the schedule was computed. A “good” schedule is on that has a very small gap between the upper and lower bounds on capacity.

[0178] The number of radios per node was set to be the same across all nodes, i.e., κ(v)=κ, ∀vεV, and the links were set to be of unit capacity for all channels, c_i(e)=1, ∀iεOC, eεE. All channels were orthogonal. Wireless channel errors were not modeled, as the goal was to estimate the maximum capacity of the network. The experiments were conducted for large topologies, and the results presented below are an average of five random topologies, each with 100 nodes. The number of links in each of these topologies varied from 350 to 900. There are no partitions in the network graph, and all links were bi-directional. Multi-path routing was enabled in all of these instances, and the number of channels varied from 1 to 8. Two parameters were measured for each topology: (a) the capacity lower bound and (b) the greedy channel-scheduling lower bound. All of these values are in terms of scaling factor λ.

[0179] FIGS. 16, 17, and 18 summarize the results of the foregoing simulations. FIG. 16 illustrates the first set of results and shows the performance of the GCS algorithm. For all combinations of channels and numbers of radio interfaces per node, the greedy channel-scheduling algorithm performed within 80% of the upper bound and was typically within 90% of the upper bound in most instances. While the “worst” cases were not encountered in the topologies considered herein, the inventors tested this algorithm on many other smaller topologies, and the results presented herein are typical of those cases.

[0180] In addition to proving the efficacy of the GCS algorithm, FIG. 16 can also be used to infer that the upper bounds are a valid approximation of the network capacity. Hence, the upper-bound numbers will now be used to explain the capacity of the network.

[0181] The inventors have observed that the network capacity of an MC-MR network depends primarily on the ratio of the number of channels to the number of interfaces per node, and not on the individual values themselves. The results shown in FIGS. 17 and 18 confirm this observation.

[0182] For example, in FIG. 17, network capacity n.λ*, which is normalized with respect to the upper-bound of the capacity of a network with 1 channel and 1 radio interface per node, is shown on the y-axis. Each data point is averaged over 5 random graph topologies with 100 nodes each, as described above. The results confirm that network capacity starts declining as soon as the ratio C/κ, exceeds a certain threshold.

[0183] In FIG. 18, the network capacity is shown for each channel, again normalized by the network capacity for the 1-channel, 1-radio case. These results affirm that network capacity of an MC-MR network depends primarily on the ratio of the number of channels to the number of interfaces per node, and not on the individual values themselves. These results also show that the

[0184] $\theta \left(W\sqrt{\frac{n}{\log n}}\right)$
function is tightly-bounded, since the per-channel network capacity does not vary significantly at all. (When f( )=θ(g( )) is tightly-bounded, it implies that c₁ g( )≦f( )≦c₂ g, with c₂/c₁≈1.)

[0185] However, the most significant inference from these results is the fact that the threshold for C/κ beyond which network capacity begins to decrease is very small, in fact, close to 1.5. Since the network capacity of an MC-MR network depends primarily on the ratio of the number of channels to the number of interfaces per node, and not on the individual values themselves, the network capacity decrease threshold is O(log n). It is noted that, for a 100-node network, log₁₀100=2 and log_e100=4.61. This suggests that the constants associated with the O( ) notation are small enough to deny any potential benefits that might be expected from this capacity trend for a reasonably large MC-MR network. Clearly, this threshold will increase for a larger network, but the increase will be meaningful only when the network size increases by a few orders of magnitude. Thus, the notion that a single radio per node might be potentially good enough to maximize network capacity might be valid only for networks with either millions of nodes, or networks with only one channel of operation. A single radio could also perform similar to a multiple radio-per-node network when the traffic load is light, although this does not mean capacity will be the same.

[0186] It should be recognized that, while the networks described in the above embodiments are wireless multi-hop mesh networks, the present invention could be used with other types of wireless networks, wired networks, optically-connected networks, or hybrid networks that include combinations of wired, wireless, and/or optically-connected elements.

[0187] The various functions of a method consistent with one embodiment of the present invention may be implemented with circuit elements or may also be implemented in the digital, domain as processing steps in a software program. Such software may be employed in, for example, a digital signal processor, micro-controller, or general-purpose computer.

[0188] The present invention can be embodied in the form of methods and apparatuses for practicing those methods. The present invention can also be embodied in the form of program code embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. The present invention can also be embodied in the form of program code, for example, whether stored in a storage medium, loaded into and/or executed by a machine, or transmitted over some transmission medium, such as over electrical wiring or cabling, through fiber optics, or via electromagnetic radiation, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code segments combine with the processor to provide a unique device that operates analogously to specific logic circuits.

[0189] It should be understood that the steps of the exemplary methods set forth herein are not necessarily required to be performed in the order described, and the order of the steps of such methods should be understood to be merely exemplary. Likewise, additional steps may be included in such methods, and certain steps may be omitted or combined, in methods consistent with various embodiments of the present invention.

[0190] Although the steps in the following method claims, if any, are recited in a particular sequence with corresponding labeling, unless the claim recitations otherwise imply a particular sequence for implementing some or all of those steps, those steps are not necessarily intended to be limited to being implemented in that particular sequence.

[0191] It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain the nature of this invention may be made by those skilled in the art without departing from the principle and scope of the invention as expressed in the following claims.