Supervisor: Kaisa Sere

Download 298.62 Kb.

Page	14/18
Date	31.01.2017
Size	298.62 Kb.
	#12944

1 ... 10 11 12 13 14 15 16 17 18

6PROOFS

If we assume that at some point in time, the complete ad hoc network could be freezed and represented by a connected graph G=(V, E) with vertices V (nodes) and edges E (links). It is also assumed that all routing information has converged then a proof of shortest path discovery can be given. In a network with mobile nodes one can never guarantee full connectivity at all time. In the proof we will use the graph theoretical definition of a tree, which is the following:

(1) - In a tree, only one loop-free path exists between two nodes.
We restate the rules for forwarding route query messages if the forwarding node does not have a route to the sought node. Points 2 through 4 are concepts from the routing algorithm which will be used to prove discovery of shortest path from a global point of view of the network in a constructive manner. The RQMs are forwarded to:
(2) - The preferred neighbor

- Extralink and interlinks

- Subtrees with extralinks or interlinks
The following things are also reminded of:
(3) - Updates are sent along the tree (preferred neighbors) from leaf nodes to the root. This means that every subroot knows the members of its subtree.
Every RQM is a tuple with the elements _s, m_s, h_s> received by node i are stored in T_i regarding a RQM sent by source s. s_s is the node ID integer of the source of the RQM, m_s is the message ID integer and h_s is the hops_traversed value corresponding the number of edges on the path between s and i.
(4) Say that node d receives RQM _r, m_r, h_r> from r.

If m, h>T_d s_r=s  m_r=m  h_rthen the RQM is forwarded and _r, m_r, h_r> replaces , m, h> in T_d.

Or if < s_r, m_r, _>T_dthen _r, m_r, h_r> is forwarded and inserted into T_d.
If we would view the network as a tree, one path is guaranteed but not necessarily the shortest (1). The network is only viewed as a tree in the first part of the routing phase, that is, how the nodes align themselves in order create a tree which branches will carry the updates. When the second phase of the routing stage is initialized, the network has to be viewed as a graph again, so that the shortest path is found. This is when the extra- and interlinks are used.
Let [x, y] is an edge from node x to node y.
In a path with n nodes, P_{(0, n-1)} is a path with edges {[v₀, v₁], …, [v_n-2, v_n-1]}E_P where E_PE and the nodes v₀ to v_n-1 are a subset of V. Each node is enumerated so the identity of every node is known.
c(P_{(0, n-1)}) returns the cost for traversing path P_{(0, n-1)} with edges E_P and

c(P_{(0, n-1)})=|E_P|=n-1 (The “cost” of traversing one edge is 1).
min(SP) can choose the shortest path (least edges) from a set of paths SP because of (4) where every traversed path (by RQM) longer than the shortest is dropped.
D-E tree is a dead-end subtree DE=(V_DE, E_DE) where V_DEV and E_DEE with no edges of the following form: [t, e] where tV_DE and eV_DE (no extra- nor interlinks). The subroot of the subtree is the node currently forwarding the RQM will calculate whether a subtree is a D-E tree.
Theorem 1: Every root’s routing table contains the shortest route to every node in its tree.
Proof 1: Every new node aspiring to connect to a tree chooses the shallowest node from a set of neighbors for association. The updates contain the shortest routes. (Analogously: every subroot knows shortest paths to all nodes in its subtree)

Theorem 2: The shortest path from a source node s to an arbitrarily chosen destination node d can be found if s and d belong to the same network.

Proof 2: The following 3 steps prove how the shortest path is constructed. N_ndenotes the set of neighbors of n. M is a set of nodes. L is a set of edges.
1. Set M={s}
2. For every node m in M, add every edge [m, g] where g N_m to the set L, and also add g to M if the following is true:

-2a. [m, g] is not an edge leading to a D-E subtree which does

not contain d (this is known because of Proof 1).

-2b. [m, g] L

-2c. If 2a and 2b is true but g M then add just [m, g] to L.

3. Recursive step: Go to step 2 if d is not in M.
From L, every distinct path in SP={P1_{(s, d)}, P2_{(s, d)}, …, PN_{(s, d)}} from s to d can be formed by constructing different combinations of elements in L.

From SP can min( c(P1_{(s, d)}), c(P2_{(s, d)}), …, c(PN_{(s, d)}) ) be extracted which is the shortest route because of (4).


In practice TRP has a property that prevents the shortest path of being used in certain situations. For instance, if one node n has in its cache, an old valid path to the destination while a newer shorter path might have been formed since then. Since n will not forward the RQM, but rather acknowledge with the old path in its cache, a longer path might be used. Because of (2) the RQM will traverse every link but those that are in D-E trees which do not contain the sought node. D-E trees and the members of the subtree can be detected because of (3).

Example of proof 2 – find a shortest path from node 4 to node 1 in figure 6-1:

add start node 4

Node 4:
- add edges [4,2], [4,3], [4,5]; nodes 2, 3, 5

Node 2:
- add edge [2, 1]; node 1 ([2,4] is already in L)

Node 3:
-add edge [3, 1] [3, 5] (use rule 2c because 5 and 1 is in M)

Node 5:
-nothing to be done; ([5,4][5,3] is in L and subtree of nodes 6 and 7 is D-E)

Node 1:
-nothing to be done

Fig. 6 26: Two shortest paths are found between node 4 and node 1.

At this point L={[4, 2], [4, 3], [4, 5], [2, 1], [3, 1], [3, 5]} from which non-cyclic paths P1_{(4, 1)}= {[4, 2], [2, 1]}, P2_{(4, 1)}={[4, 3], [3,1]} and P3_{(4, 1)}={[4, 5], [5,3], [3,1]} can be combined. Min(P1_{(4, 1)}, P2_{(4, 1)}, P3_{(4, 1)}) yields P1_{(4, 1)} and P2_{(4, 1)} which is c(P1_{(4, 1)}) = c(P2_{(4, 1))}) = 2.
Lemma 3: The discovered routes are loop-free.
Proof 3: Every message that traverses a loop will have a greater hops_traversed value and therefore discarded after the loop is traversed.


Corollary 4: D-E trees that do not contain the sought destination d are never searched. (RQMs are never disseminated in D-E Trees).

Proof 4: In proof 2 step 2a will ensure that no edges from a D-E tree not containing d, will ever be put to the set L.


Download 298.62 Kb.

Share with your friends:

1 ... 10 11 12 13 14 15 16 17 18