16.5 MOBILE PATHS

Shortest Mobile Path (SMP) Problem: Given a mobile graph G = G1 . . . GT and a spec-

ified source“destination pair s, t, find a mobile path P = P1 . . . PT from s to t, such that the

weight

T T“1

w(P) = wi(Pi) + ctrans(Pi, Pi+1)

i=1 i=1

of the mobile path is minimum.

Two fundamental results were first proven about mobile paths in [6]. The first is a pos-

itive result, as follows. Let the transition cost function be simply an indicator of the path

change, i.e., given as

0 if Pi = Pi+1

ctrans(Pi, Pi+1) = (16.2)

c0 if Pi Pi+1

where c0 is a positive constant. That is, no transition cost is incurred if there is no change

in the path in successive graphs, otherwise a constant cost is incurred if the path has

changed. In this case, the shortest mobile path can be found by a dynamic programming

algorithm that runs in polynomial time. This makes it possible to compute the ideal route

sequence that is used in the MERIT framework as a basis of comparison.

The second result is negative: if the transition cost can be arbitrary (but still efficiently

computable), then the problem becomes NP-hard. Specifically, it is already NP-hard for

the following transition cost function:

ctrans(Pi, Pi+1) = M(|Pi Pi+1| + |wi(Pi) “ wi+1(Pi+1)|)

where M is a constant.

Now we show that mobile paths also fit in the unified path metric framework presented

in Section 16.3, thus, the shortest mobile path problem is a special case of the F-shortest

path problem. For simplicity, let us assume that the weights and transition costs are posi-

tive integers (this is not an essential restriction).

Assume that we are given an instance of the mobile path problem as described above.

Let s and t be the source and terminal nodes of the sought mobile path, respectively.

(These nodes are present in each Gi.) Let us construct a new graph by taking each graph

Gi in the sequence and merge the end node t in Gi with the start node s in Gi+1. Let us call

the resulting new graph G. Let the start node in the first graph G1 be named u and the end

node in the last graph GT be named v. Now it is clear that every path sequence (mobile

path) is in 1“1 correspondence with an u“v path in the amalgamated graph G. (The path in

G is simply the concatenation of the path sequence in the mobile path.)

According to the above construction, we can uniquely represent each possible mobile

path by a u“v path in G. Let us also keep the original edge weights. It would not be suffi-

cient, however, if one simply looked for a minimum-weight u“v path in the amalgamated

graph G, since that would ignore the transition costs. We can define, however, a path met-

ric by Equation (16.1) for every u“v path in G. This metric includes both the static weight

and the transition costs. Clearly, Pi means here the part of the path that falls in Gi. Now we

438 ALGORITHMIC CHALLENGES IN AD HOC NETWORKS

can use the fact that, by Theorem 1, every path metric can be represented by an F-mea-

sure, up to constant translation. Thus, we have that the shortest mobile path problem is

equivalent to an F-shortest path problem. In this sense, the shortest mobile path also be-

comes a special case of the general framework presented in Sections 16.3 and 16.4.

What is the advantage of translating the shortest mobile path problem into an F-shortest

path task? The gain is that any result/algorithm for the F-measure will automatically apply to

mobile paths. For example, if we represent the mobile path cost [Equation (16.1)] by an F-

measure (made possible by Theorem 1), then we can approximate this F by a smaller family

that allows a good approximation algorithm by Theorem 2. This yields the research question:

Open Problem 4. Find a way to approximate the mobile path measure [Equation (16.1)]

with a “small” F-measure.

One can also use the special structure of the SMP problem in a different way. Let us as-

sume that instead of allowing any s“t path in Gi, we restrict ourselves in each Gi to a pres-

elected set Pi of paths. It is not unusual in practical situations that only a restricted set of

paths is considered. Note that this still allows exponentially many mobile paths, since if

|Pi| = Ri, then we can still have R1R2 · . . . · RT different mobile paths. Now we can define a

restricted version of the SMP problem as follows.

Restricted Shortest Mobile Path (R-SMP) Problem: The input is a mobile graph G =

G1 . . . GT and a specified source“destination pair s“t, as well as a set of s“t paths Pi for

each Gi. Find a mobile path P = P1 . . . PT from s to t, such that the restriction Pi Pi

holds for each i and the weight

T T“1

w(P) = wi(Pi) + ctrans(Pi, Pi+1)

i=1 i=1

of the restricted mobile path is minimum.

Now we show that the above-defined restriction is quite useful: the R-SMP problem

behaves in a much more “friendly” way than the original SMP. Specifically, the restricted

shortest mobile path can be found in polynomial time for any transition cost function, giv-

en that the path sets Pi are of polynomially bounded size. The details are shown in the fol-

lowing theorem.

Theorem 3. Let |Pi| = Ri in the R-SMP problem and set R = R1 + . . . + RT. Then, for any

transition cost function the shortest restricted mobile path can be found in O(R2) time, as-

suming that the transition cost function is computed by a subroutine in unit time. In par-

ticular, if R is polynomially bounded in terms of the size of the mobile graph, then the so-

lution is obtainable in polynomial time.

Proof. Let us construct an auxiliary directed graph G as follows. Let us denote the paths

in Pi by Pi,1,Pi,2, . . . , Pi,Ri, where Ri = |Pi|. For each Pi,j take two nodes ai, j, bi, j, draw an

edge form ai, j to bi, j and assign the weight wi(Pi, j) to this edge. Further, connect each node

bi, j to every ai+1,k by an edge, directed toward ai+1,k, and assign the weight ctrans(Pi, j, Pi+1,k)

to this edge. Finally, add two extra nodes a, b and draw a directed edge from a to each a1, j,

as well a directed edge from each bT, j to b. All edges that are adjacent to a or b are as-

439

16.6 THE INVERSE SHORTEST PATH PROBLEM

signed 0 weight. The whole construction can be done in O(R2) time, assuming that each

transition cost computation is counted as one step.

It is easy to see that every a“b path in G is in a natural 1“1 correspondence with a re-

stricted mobile path in G. (The static component paths of mobile path are marked by the

indices of nodes that the a“b path in G traverses.) Moreover, the weight of any a“b path

in G is precisely the weight of the corresponding mobile path, including transition costs.

Thus, to solve the R-SMP problem optimally, one only needs to find a minimum weight

a“b path in G . Since G has R + 2 vertices, this can be done in O(R2) time by Dijkstra™s

í

algorithm.

As seen above, once the preselected path sets Pi are given, the R-SMP problem can be

solved in a rather straightforward way. A key question, however, remains open:

Open Problem 5. Find a method to choose the preselected path sets, such that the R-SMP

solution provides a good approximation to the SMP.

16.6 THE INVERSE SHORTEST PATH PROBLEM

It is not an unusual case in ad hoc routing protocols that the declared path metric of a pro-

tocol (which is most often the simple hop metric) is not the one that really reflects the ac-

tual choices. The reason is that there is interaction among the various layers in the proto-

col stack and the influence of protocols in other layers (for example, the effect of TCP)

makes certain routes less preferable or even unavailable. The routing protocol can take

this into account via auxiliary mechanisms, for example, maintaining various preferences,

timeout parameters, and so on, rather than explicitely incorporating it into a numerically

defined path metric. As a result, the actual route choices can reflect a metric that is not

defined explicitely. Rather, it is the result of the interaction between the declared path

metric plus a number of auxiliary mechanisms that may depend on a large number of var-

ious factors, influenced by the behavior of other layers.

This impliciteness of the actual path metric complicates the analysis and assessment of

routing protocols. It is not easy to decide whether the protocol choses the “best” (static)

path if we do not even have an explicitely defined path metric. Below, we outline an ap-

proach that may be of help to handle this issue.

In the Inverse Shortest Path (ISP) Problem, we reverse the usual setting of path find-

ing. In the usual setting, a metric is given and the task is to find shortest paths between

various end nodes, according to the given metric. In the ISP problem, the task is just the

opposite: we are given the chosen paths and we would like to find the metric that makes

them shortest paths among their terminal nodes. Thus, if the ISP is solved, then a metric is

constructed that explicitely represents the actual path choices of the protocol as shortest

paths, incorporating the potential effect of auxiliary mechanisms.

It is worth noting at this point that if any metric can be selected to represent the ob-

served path choices of a protocol as shortest paths, then the problem is essentially trivial,

since we can simply assign a small value to the given paths and a large value to every oth-

er path. This wold obviously make the given paths the shortest. On the other hand, this

“brute force” aproach is not a scalable solution, since the metric has to “remember” each

chosen path. What we would like to achieve is to represent the metric in a way that does

not get more complicated with the growing number of paths.

440 ALGORITHMIC CHALLENGES IN AD HOC NETWORKS

A natural choice is to restrict ourselves to a metric that is generated by positive link

weights. It has a number of advantages: it is scalable, as it does not depend on the (poten-

tially exponential) number of paths, and it is algorithmically well tractable to find the

shortest path under this metric.

A potential drawback is, however, that not all path systems can arise as shortest paths

under some positive link weighting. (Exercise: construct such an example, that is, a set of

paths in a graph for which there is no positive edge weigting that makes all the given paths

shortest between their endpoints.) Therefore, we extend the task such that whenever no

weighting exists to precisely capture the path system, then we look for a best approxima-

tion, as defined below.

The following formulation is based on a more general framework presented in [8], spe-

cialized here to shortest paths. For notational convenience, the edge weights are collected

into a weight vector w. The weight of any given path P is denoted by w(P) and the weight

of a shortest (= minimum weight) path between the endpoints of P is denoted by sw(P).

That is, sw(P) = minQ w(Q), where the minimum is taken over all paths Q that have the

same endpoints as P.

Inverse Shortest Path (ISP) Problem

Input: Given paths P1, . . . , Pr among arbitrary (possibly different) end vertices in a

graph G.

Find: A weight vector w 1 that minimizes the maximum absolute error

= max |w(Pi) “ sw(Pi)|

i

Note that the constraint w 1 is needed for normalization purposes, otherwise one

could trivially make the error arbitrarily small by assigning sufficiently small positive

weights to everything. We also note that the absolute value can be omitted from the defin-

ition of , as w(Pi) sw(Pi) must always hold by definition.

Now we show that the ISP problem can be solved in polynomial time. The solution

provides the required best approximation. Moreover, if an exact solution exists, that is,

there is a positive weighting that makes all the given paths shortest among their respective

endpoints, then the the algorithm finds this, since then the achievable best error is = 0.

Theorem 4. The ISP problem can be solved in polynomial time, that is, an optimal

weighting w can be found in polynomial time that minimizes the maximum absolute error

under the conditions of the ISP Problem.

Proof. For easy notation, let us denote the edges by the numbers 1, 2, . . . , m. For each

path Pk, given as input, let Pk be the set of all paths between the endpoints of Pk. Now con-

sider the following linear program.

y max! (16.3)

y 0 (16.4)

wi 1 (i = 1, . . . , m) (16.5)

Pk “ {Pk}, k = 1, . . . , m)

wj “ wj y (P (16.6)

jP j Pk

441

16.6 THE INVERSE SHORTEST PATH PROBLEM

Note that as j Pwj = w(P), we have just used the sums to emphasize that the above

formulation is indeed a linear program. Below, we are going to show that the optimal so-

lution of this linear program provides precisely the required weightings.

First, observe that this system of linear inequalities can contain exponentially many in-

equalities (since the sets Pk can be exponentially large) and, additionally, they are not even

explicitly listed. Nevertheless, we can still solve it in polynomial time if we apply those

linear programming algorithms that do not need an explicit list of the inequalities; they

can work with a so-called separation oracle. A separation oracle is a subroutine that for

any given variable vector can check if it satisfies all inequalities, or, if not, it return a vio-

lated inequality. A well-known method of this type is the Ellipsoid Algorithm, the histori-

cally first polynomial-time solution for linear programming (for an overview see, e.g.,

[20]). It is known that the Ellipsoid Algorithm with separation oracle runs in time that is

polynomially bounded in terms of the number of variables, the number of bits that de-

scribe any given inequality, and the running time of the separation oracle. In our case, the

separation oracle means that for any given setting of the weights wi and the variable y, we

should be able to check in polynomial time whether the above constraints are all satisfied,

or, if not, we have to find a violated inequality. If we can do this, then the Ellipsoid Algo-

rithm finds the solution in polynomial time, since our inequalities have all 0, 1, “1 coeffi-

cients and constants.

Now we construct the needed polynomial-time separation oracle as follows. Given a

vector (w, y), first we directly check if Equations (16.4) and (16.5) are satisfied. If not, we

have directly found a violated inequality. If they are satisfied, then we proceed as follows.

For each index k run a shortest path algorithm (e.g., Dijkstra™s), with weighting w, to find

a shortest path between the endpoints of Pk, where Pk is the kth given input path. Assume

that for a given k and w, the returned minimum weight path is P. Let us compare w(Pk)

and w(P). If w(P) y + w(Pk), then all inequalities with this k must be satisfied in Equa-

tion (16.6), since P is a minimum-weight path under this weighting, so w(P ) w(P)

holds for any other path P between the same endpoints. On the other hand, if w(P) < y +

w(Pk), then this provides a violated inequality, namely

wj “ wj y

jP j Pk

is violated.

Having constructed the polynomial-time separation oracle, we can find an optimum

solution (w0, y0) to the linear program by the Ellipsoid Algorithm in polynomial time. It

follows from the construction that |y0| will be the smallest possible value for which w0(Pk)

í

differs form sw(Pk) ( k) at most by |y0|, which proves the theorem.

The algorithm described in the above proof solves the ISP problem in polynomial time,

but it is still not too practical, as it involves linear programming in the special form in

which instead of explicitely listed inequalities one has to use implicitely defined con-

straints, in terms of a separation oracle (although it runs in polynomial time, most linear

programming software packages do not support this mode of operation; they typically

need explicite constraints). This yields the following open question.

Open Problem 6. Find a method to solve the inverse shortest path problem in a purely

combinatorial way, that is, as a pure graph algorithm that avoids linear programming.

442 ALGORITHMIC CHALLENGES IN AD HOC NETWORKS

Another related question is the following: