Mobile Ad Hoc Networks

Ad Hoc Routing Modeling and Mathematical Analysis  ◾  133

graph G (N, A), the set of flows x

ij

|

(i. j)∈A

is referred to as the flow vector. A path P in a graph is a

sequence of arcs P

1, k

 ≡ (1, 2, … , k), where k ≥ 2. A graph is connected if, for each pair of nodes

i and j, there is a path starting at i and ending at j. e routing algorithms calculate the optimal

routes obtaining paths where the flow vectors x

ij

are constrained between given lower and upper

bounds (i.e., b

ij

 ≤ x

ij

 ≤ c

ij

) in order to limit the available bandwidth for that flow. In fixed networks,

stability is good enough and the end-to-end packet delay and throughput capacity are the only

metrics to be optimized. ese metrics are known in fixed networks, providing an NP-complete