Can anyone tell me to understand the following code?I don't understand which is the function of A in the following algorithhm: A is the set of links or the set of link lifetimes? I have to write this code in matlab.

LLR SELECTION ALGORITHM

In the previous section, we investigate the distributions of

link lifetime and route lifetime based on some fundamental

mobility models. The study on the route lifetime distribu-

tions tells us that despite the higher complexity, a deter-

ministic routing design for LLR is more suitable for real life

scenarios than a probabilistic scheme. In this section, we will

study how to determine long lifetime routes between a pair

of nodes given a random network snapshot. We first provide

a polynomial time algorithm to determine the longest life-

time routes at different route lengths from all the possible

routes between the source and the destination. Using this

algorithm, we are able to gather statistical results on the

achievable maximum route lifetime improvement in random

networks.

Here, we put N nodes randomly in a circle of unit ra-

dius centered at location (0,0). A source node S is placed

at (x s ,0) and a destination node D is placed at (x d ,0). All

the nodes have the same transmission range R t . Nodes are

assigned a speed uniformly distributed in [s min ,s max ] and

a moving direction uniformly distributed in [0,2π]. At time

0, S chooses a route to D, and at time T, the route is bro-

ken. We are interested in the statistical results of following

metrics.

1. The longest route lifetime and its route length.

2. The longest route lifetime of the shortest path. This is

the best case among all the shortest paths.

3. The shortest route lifetime of the shortest routes. This

is the worst case for all the shortest paths.

4. The longest route lifetime at route lengths between the

longest and the shortest route length and their correspond-

ing lifetimes. This metric will be further studied in the next

section to compare with the lifetime of random shortest-path

routes.

The following algorithm is proposed to discover qualified

long lifetime routes within a polynomial time. The basic

idea of this algorithm is to first sort all the links based on

their weights: link lifetime in this case. Then we add the

links in a descending order and adjust route lengths between

each pair of nodes one by one. Meanwhile, we keep a record

(s i , theta i )

(s j , theta j )

i

j

(x i ,y i )

(x j ,y j )

Figure 4: The geometry to calculate link lifetime.

for all the route length changes and their corresponding life-

time changes for the source-destination pair. After every

link is added, we will have a complete record of any lifetime

changes between the source-destination pair.

We are only interested in the lifetime and length of the

path between the source node S and the sink node D. The

arc set A is sorted in descending order by the lifetime c[i,j]

of the link composed of nodes i and j. Given a snapshot of

the network, if the link distance between node i and node

j is shorter than the transmission range, their link lifetime

c[i,j] is determined as in Fig. 4 and equation 5.

D 2 (t) =[(x i + s i cosθ i t) − (x j + s j sincosθ j t)] 2

+ [(y i + s i sinθ i t) − (y j + s j sinθ j t)] 2

(5)

By solving D(t) = R t , we will have the link lifetime t as-

signed to c[i,j]. Notice that when the network snapshot is

given, all the node location and speed information is deter-

ministic.

We denote an edge as e or a link between node i and

j as e[i,j] if node i and j are connected. d[i,j] is the hop

distance between nodes i and j. d prev is the last route length

recorded between the pair. The Long Lifetime Route (LLR)

selection algorithm is shown in Algorithm 1.

Data: A, initial c[i,j] for each link

Result: Record of the longest lifetime achievable for routes

with different hop distances {d[S,D], c[S,D]}

begin

S := ∅;S := A; d prev = ∞;

for all node pairs [i,j] ∈ N × N do

d[i,j] := ∞; pred[i,j] := 0;

end

for all nodes i ∈ N do d[i,i] := 0;

while |S| 6= A do

let e[i,j] ∈ S for which c[i,j] = max{c(e),e ∈ S};

S := S

S {[i,j]}; S := S − {[i,j]};

d[i,j] = d[j,i] = 1;

for each [m,n] ∈ N × N do

if d[m,n] > d[m,i] + d[i,j] + d[j,n] then

d[m,n] := d[m,i] + d[i,j] + d[j,n] and

pred[m,n] := i;

end

if d[m,n] > d[m,j] + d[j,i] + d[i,n] then

d[m,n] := d[m,j] + d[j,i] + d[j,n] and

pred[m,n] := j;

end

end

if d[S,D] < d prev then

d prev = d[S,D] and record {d[S,D],c[S,D]}

end

end

end

Algorithm 1: LLR selection algorithm.

LLR SELECTION ALGORITHM

In the previous section, we investigate the distributions of

link lifetime and route lifetime based on some fundamental

mobility models. The study on the route lifetime distribu-

tions tells us that despite the higher complexity, a deter-

ministic routing design for LLR is more suitable for real life

scenarios than a probabilistic scheme. In this section, we will

study how to determine long lifetime routes between a pair

of nodes given a random network snapshot. We first provide

a polynomial time algorithm to determine the longest life-

time routes at different route lengths from all the possible

routes between the source and the destination. Using this

algorithm, we are able to gather statistical results on the

achievable maximum route lifetime improvement in random

networks.

Here, we put N nodes randomly in a circle of unit ra-

dius centered at location (0,0). A source node S is placed

at (x s ,0) and a destination node D is placed at (x d ,0). All

the nodes have the same transmission range R t . Nodes are

assigned a speed uniformly distributed in [s min ,s max ] and

a moving direction uniformly distributed in [0,2π]. At time

0, S chooses a route to D, and at time T, the route is bro-

ken. We are interested in the statistical results of following

metrics.

1. The longest route lifetime and its route length.

2. The longest route lifetime of the shortest path. This is

the best case among all the shortest paths.

3. The shortest route lifetime of the shortest routes. This

is the worst case for all the shortest paths.

4. The longest route lifetime at route lengths between the

longest and the shortest route length and their correspond-

ing lifetimes. This metric will be further studied in the next

section to compare with the lifetime of random shortest-path

routes.

The following algorithm is proposed to discover qualified

long lifetime routes within a polynomial time. The basic

idea of this algorithm is to first sort all the links based on

their weights: link lifetime in this case. Then we add the

links in a descending order and adjust route lengths between

each pair of nodes one by one. Meanwhile, we keep a record

(s i , theta i )

(s j , theta j )

i

j

(x i ,y i )

(x j ,y j )

Figure 4: The geometry to calculate link lifetime.

for all the route length changes and their corresponding life-

time changes for the source-destination pair. After every

link is added, we will have a complete record of any lifetime

changes between the source-destination pair.

We are only interested in the lifetime and length of the

path between the source node S and the sink node D. The

arc set A is sorted in descending order by the lifetime c[i,j]

of the link composed of nodes i and j. Given a snapshot of

the network, if the link distance between node i and node

j is shorter than the transmission range, their link lifetime

c[i,j] is determined as in Fig. 4 and equation 5.

D 2 (t) =[(x i + s i cosθ i t) − (x j + s j sincosθ j t)] 2

+ [(y i + s i sinθ i t) − (y j + s j sinθ j t)] 2

(5)

By solving D(t) = R t , we will have the link lifetime t as-

signed to c[i,j]. Notice that when the network snapshot is

given, all the node location and speed information is deter-

ministic.

We denote an edge as e or a link between node i and

j as e[i,j] if node i and j are connected. d[i,j] is the hop

distance between nodes i and j. d prev is the last route length

recorded between the pair. The Long Lifetime Route (LLR)

selection algorithm is shown in Algorithm 1.

Data: A, initial c[i,j] for each link

Result: Record of the longest lifetime achievable for routes

with different hop distances {d[S,D], c[S,D]}

begin

S := ∅;S := A; d prev = ∞;

for all node pairs [i,j] ∈ N × N do

d[i,j] := ∞; pred[i,j] := 0;

end

for all nodes i ∈ N do d[i,i] := 0;

while |S| 6= A do

let e[i,j] ∈ S for which c[i,j] = max{c(e),e ∈ S};

S := S

S {[i,j]}; S := S − {[i,j]};

d[i,j] = d[j,i] = 1;

for each [m,n] ∈ N × N do

if d[m,n] > d[m,i] + d[i,j] + d[j,n] then

d[m,n] := d[m,i] + d[i,j] + d[j,n] and

pred[m,n] := i;

end

if d[m,n] > d[m,j] + d[j,i] + d[i,n] then

d[m,n] := d[m,j] + d[j,i] + d[j,n] and

pred[m,n] := j;

end

end

if d[S,D] < d prev then

d prev = d[S,D] and record {d[S,D],c[S,D]}

end

end

end

Algorithm 1: LLR selection algorithm.

## Comment