<<

. 83
( 87 .)



>>

437
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:

<<

. 83
( 87 .)



>>