CN102006237A - Routing decision method for delay tolerant network - Google Patents

Abstract

The invention discloses a routing decision-making method for a delay-tolerant network, which mainly solves the defect that the prior art fails to make full use of network node movement rules and link history information for routing selection. The specific process is: (1) discretize the time-varying link capacity function, and construct a three-dimensional matrix describing the network topology change; (2) perform binary quantization on the link capacity, and obtain the homogeneous Markov function of each link (3) Estimate the arrival rate of the connected and disconnected state of the link by using the node movement law and link history information; (4) Calculate the link at any time according to the obtained arrival rate of the connected and disconnected state of the link. Connectivity probability; (5) Define the routing decision-making process of delay-tolerant network as a Markov decision model with limited stages. (6) According to the Markov decision theory, define the global optimal equation, and use the backward iterative recursive algorithm to calculate the optimal decision sequence. The invention can meet the requirement of the delay-tolerant network with large delay, and select the optimal routing decision-making sequence for it.

Description

Routing Decision Method for Delay Tolerant Networks

technical field

The invention belongs to the technical field of communication, relates to a delay-tolerant network routing decision, and can be used to improve the overall performance of the network in the delay-tolerant network.

Background technique

Delay-tolerant network (DTN) is a new type of network architecture, which generally refers to a type of network that does not have a stable end-to-end transmission path due to node movement and other reasons, and is even in a state of interruption most of the time. This concept was first proposed by K.Fall at the famous international conference SIGCOMM2003, and its application covers many communication networks other than the Internet, such as interstellar network, rural network, war network, wildlife monitoring and tracking network, mobile Ad Hoc Network and wireless sensor network, packet switching network PSN, etc. Research on delay-tolerant networks will provide these networks with a certain quality of network services in the case of dynamic topological changes. It is considered to be a key technology to realize "ubiquitous networks" and has important research significance.

Compared with traditional networks, the topology of delay-tolerant networks changes dynamically, there is no stable transmission path between nodes, and there may not even be a complete transmission path at any time, which makes traditional Ad hoc network routing mechanisms that rely on stable transmission paths It is difficult to play a role in the delay-tolerant network, so a new routing mechanism must be designed according to its characteristics. At present, the existing delay-tolerant network routing methods include flooding algorithm based on the idea of replication, infection routing algorithm, distribution and waiting algorithm, etc. These algorithms can guarantee the transmission rate well when solving the problem of delay-tolerant network routing; The contradiction between the huge network overhead required and the limited network resources such as node caches severely limits their use. In response to this situation, researchers proposed different data discarding strategies, such as the earliest discard DOA and the smallest discard DLE; also proposed the concept of probability diffusion to save network overhead, that is, only spread to neighbor nodes with higher probability, such as probabilistic routing Algorithm method PROPHET; and routing method ERHR based on energy constraints and historical information, etc. Even so, the traditional routing method still fails to make full use of the history of network topology changes and the scheduling information of each future contact to optimize the packet transmission process, resulting in poor overall network performance.

Contents of the invention

The purpose of the present invention is to overcome the deficiencies of the above-mentioned prior art, aiming at the characteristics of delay-tolerant networks, to provide a routing decision-making method for delay-tolerant networks, to fully utilize the nodes themselves for mobility networks with predictable delays The operating rules and the contact probability with neighboring nodes are adjusted, and a new type of routing decision with learning function is formed by using the Markov decision model, so as to realize the improvement of the data packet delivery opportunity of the delay-tolerant network nodes and improve the overall performance of the delay-tolerant network. get improved.

In order to achieve the above object, the technical solution of the present invention is: first, discretize the time-varying link capacity function, and construct a three-dimensional matrix to describe the network topology change; then, carry out binary quantization to the discrete link capacity function, Make each link obtain a homogeneous Markov model; finally, define the routing decision process of the delay-tolerant network as a Markov decision model with limited discrete time decision-making in one stage, and use the global optimum in Markov decision theory Equation definition and backward iterative algorithm, etc., to calculate the optimal decision sequence, the specific implementation process is as follows:

(1) Describe the network topology with discretized link connectivity characteristics:

(1a) During the observation period, discretize the time-varying link capacity function c _ij (t) between any network node i and j with a given sampling interval Δ and smoothing step size, and obtain a discrete sequence c _ij ( t ₀ +aΔ).

(1b) Each node spreads the sampled discrete sequence throughout the entire network, so that each node integrates a three-dimensional matrix represented in a discrete form:

A＝{c _ij (t ₀ +aΔ)} _|V|×|V|×K ,

Among them, V and E represent the nodes and edges in the considered network respectively, and |V| and |E| represent the number of nodes and edges respectively; i, j=0, 1, L, |V|-1; t is the network Running time, t ₀ is the starting point of time statistics, a is the time sequence of sampling, a=0, 1, L K, K is the maximum value of the sampling sequence.

(2) According to the obtained three-dimensional matrix A, the link capacity is represented by binary quantization, and the following homogeneous Markov model is obtained for each link:

${\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; a\&Delta;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{c}\mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}\end{array}\right.<span\; class="notranslate">\; ,</span>$

The model embodies the capacity of each link as a Markov process transitioning between "0" and "1" states; where "0" means the link is connected and "1" means disconnected.

(3) According to the obtained Markov model, taking the movement law of each node in the network and the link history information obtained by statistics as a reference, using the stochastic process parameter estimation method to estimate the connection state and disconnection state of each link Arrival rates μ and λ.

(4) According to the estimated connected and disconnected state arrival rates μ, λ and the Kolmogorov equation, the following differential equations are obtained:

$\left\{\begin{array}{c}{{\mathrm{<span\; class="notranslate">\; P</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>\\ {{\mathrm{<span\; class="notranslate">\; P</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>\end{array}\right.<span\; class="notranslate">\; ,</span>$

Solving the above differential equations gives:

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; \&mu;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}}{\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; ,</span>$

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; \&mu;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}}{\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; .</span>$

In the above formula, P ₀ (t) and P ₁ (t) represent the steady-state probability of state 0 and state 1 at time t, respectively, and P′ ₀ (t) and P′ ₁ (t) represent the state of 0 at time t and the transition probability of state 1.

(5) According to the obtained Markov state model of each link, the routing decision-making process of the delay-tolerant network is defined as a Markov decision-making model of discrete-time decision-making with limited stages: {T, S, A(i), p (j′|i, e _ij ), r(i, e _ij )}, where:

T represents the decision-making moment, T={0, 1, L, |V|-1}, |V|-1 represents the maximum allowable value of routing hops, that is, all other nodes except the source node are allowed to be skipped at most.

S represents a possible state, S=V, that is, a node represents a state.

A(i) represents the possible action set, A(i)=e _ij , e _ij ∈ E, i, j represents the network node, e _ij represents the edge connecting network node i and node j.

该式表示，i节点在t时刻采用行动e_ij到达节点j′的概率，p(e_ij)表示链路e_ij的连通概率，p(e_ij)＝P₀(t)，i，j，j′∈S，e_ij∈E，t∈[0，|V|-1]。P _t (j′|i, e _ij ) represents the transition probability,

This formula expresses the probability that node i takes action e _ij to reach node j′ at time t, p(e _ij ) represents the connection probability of link e _ij , p(e _ij )=P ₀ (t), i, j, j′ ∈ S, e _ij ∈ E, t ∈ [0, |V|-1].

该式表示，i节点在t时刻采用行动e_ij所得到的，其中，c_ij(t)是链路e_ij在t时刻的链路容量，i，j∈S，e_ij∈E，t∈T，N为结束时刻，N∈[0，|V|-1]。r _t (i, e _ij ) represents the compensation value,

This formula expresses what is obtained by node i taking action e _ij at time t, where c _ij (t) is the link capacity of link e _ij at time t, i, j∈S, e _ij ∈ E, t∈ T, N is the end time, N∈[0, |V|-1].

(6) According to the established Markov decision model and Markov decision theory, the global optimal equation is defined as follows:

In this formula, u _t (h _t ) is the optimal value at time t; r _t (i, e _ij ) is the compensation value of action e _ij in state i at time t; p _t (j|i, e _ij ) is At time t, the probability that state i adopts action e _ij to transfer to j; h _t is the trajectory vector before time t, including the states experienced before and the actions taken.

(7) According to the optimal strategy solution process of the finite stage model in Markov decision theory, in the case of known initial state and terminal state, the global optimization equation is calculated by backward iterative recursive algorithm, and a set of connections is obtained Optimal decision sequence for initial state and final state.

Compared with the prior art, the present invention has the following advantages:

1) The present invention transforms complex network topology changes into discrete static topologies by discretizing continuous channel capacity functions, which facilitates the calculation of decision sequences.

2) The present invention uses a Markov model to describe the connection status of the network, and describes the connection status of the link more objectively and clearly.

3) The present invention estimates the arrival rate of the connected state and the disconnected state of the link by using the node movement law and the link history information, so that the routing decision-making process is more reliable.

4) The present invention uses a Markov decision-making model of discrete-time decision-making with limited stages to solve the routing decision-making problem of a delay-tolerant network, so that the algorithm as a whole has the function of reinforcement learning.

Description of drawings

Fig. 1 is a schematic flow sheet of the present invention;

Fig. 2 is a schematic diagram of network topology changes constructed in the present invention;

Fig. 3 is the data packet transmission success rate performance comparison diagram of method of the present invention and traditional routing method;

Fig. 4 is the comparison figure of the data packet average delay performance of the inventive method and the traditional routing method;

Fig. 5 is a performance comparison diagram of the average number of copies of forwarded data packets using the method of the present invention and the traditional routing method.

Detailed ways

The technical solution of the present invention will be further described in detail below with reference to the accompanying drawings.

With reference to Fig. 1, the routing establishment process of the present invention is as follows:

Step 1, discretize the time-varying link capacity function.

Referring to Fig. 2, during the observation period, with a given sampling interval Δ and smoothing step size, the time-varying link capacity function c _ij (t) of the link e _ij between any network node i and j is discretized to obtain Discrete sequence c _ij (t ₀ +aΔ). The continuous change of network topology is discretized into static topological graphs, where, i, j=0, 1, L, |V|-1; e _ij ∈ E; V and E respectively represent the nodes and edges in the considered network, |V|, |E| represent the number of nodes and edges respectively; t is the running time of the network, t ₀ is the starting point of time statistics, a is the time sequence of sampling, a=0, 1, L K, K is the maximum value of the sampling sequence.

Step 2, constructing a three-dimensional matrix describing network topology changes.

Each node spreads the sampled discrete sequence throughout the entire network, so that each node integrates a three-dimensional matrix represented in a discrete form.

A={c _ij (t ₀ +aΔ) _|V|×|V|×K .

The above formula records all information of network topology changes during the observation period.

Step 3, according to the obtained three-dimensional matrix A, use binary quantization to express the link capacity, and obtain the following homogeneous Markov model for each link:

${\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; a\&Delta;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{c}\mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}\end{array}\right.<span\; class="notranslate">\; ,</span>$

This model embodies the capacity of each link as a Markov process transitioning between "0" and "1" states. In the formula, "0" means the link is connected, "1" means disconnected, and the connectivity characteristics of the entire network is defined as |V|×|V| Markov processes.

Step 4, according to the obtained Markov model, taking the movement law of each node in the network and the link history information obtained through statistics as a reference, and using the stochastic process parameter estimation method, the relationship between the connected state and the disconnected state of each link is estimated. Arrival rates μ and λ, the estimate includes two cases:

One is for links between nodes with unknown movement rules, using the link history information obtained through statistics, using the maximum likelihood method or Bayesian method to estimate the arrival rate μ of the connected state and the disconnected state of the link. Arrival rate λ;

Second, for the link between nodes with known movement rules, the deep space communication channel loss model is used to calculate the time-varying link capacity function c _ij (t); and then the time-varying link capacity function c _ij (t) Carry out discrete and binary quantization to obtain the arrival rate μ of the connected state and the arrival rate λ of the disconnected state of the link.

Step 5, according to the estimated connected and disconnected state arrival rates μ, λ and Kolmogorov equation, the following differential equations are obtained:

$\left\{\begin{array}{c}{{\mathrm{<span\; class="notranslate">\; P</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>\\ {{\mathrm{<span\; class="notranslate">\; P</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>\end{array}\right.<span\; class="notranslate">\; ,</span>$

Solving the above differential equations gives:

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; \&mu;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}}{\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; ,</span>$

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; \&mu;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}}{\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; ;</span>$

In the above formula, P ₀ (t) and P ₁ (t) represent the steady-state probability of state 0 and state 1 at time t, respectively, and P′ ₀ (t) and P′ ₁ (t) represent the state of 0 at time t and the transition probability of state 1; through the obtained P ₀ (t) and P ₁ (t), the link connection and disconnection probability at any time t of network operation can be calculated, that is, the specific discrete time point t ₀ +aΔ Put into the equation of P ₀ (t) and P ₁ (t) to calculate the link connection and disconnection probability at any time t.

Step 6, define a delay-tolerant network routing decision model.

According to the obtained Markov state model of each link, the routing decision-making process of the delay-tolerant network is defined as a Markov decision-making model of a stage-finite discrete-time decision: {T, S, A(i), p(j′ |i, e _ij ), r(i, e _ij )}, where:

T represents the decision-making moment, T={0, 1, L, |V|-1}, |V|-1 represents the maximum allowable value of routing hops, that is, all other nodes except the source node are allowed to be skipped at most.

S represents a possible state, S=V, that is, a node represents a state.

A(i) represents the possible action set, A(i)=e _ij , e _ij ∈ E, i, j represents the network node, e _ij represents the edge connecting network node i and node j.

该式表示，i节点在t时刻采用行动e_ij到达节点j′的概率，p(e_ij)表示链路e_ij的连通概率，p(e_ij)＝P₀(t)，i，j，j′∈S，e_ij∈E，t∈[0，|V|-1]。P _t (j′|i, e _ij ) represents the transition probability,

This formula expresses the probability that node i takes action e _ij to reach node j′ at time t, p(e _ij ) represents the connection probability of link e _ij , p(e _ij )=P ₀ (t), i, j, j′ ∈ S, e _ij ∈ E, t ∈ [0, |V|-1].

该式表示，i节点在t时刻采用行动e_ij所得到的，其中，c_ij(t)是链路e_ij在t时刻的链路容量，i，j∈S，e_ij∈E，t∈T，N为结束时刻，N∈[0，|V|-1]；r _t (i, e _ij ) represents the compensation value,

This formula expresses what is obtained by node i taking action e _ij at time t, where c _ij (t) is the link capacity of link e _ij at time t, i, j∈S, e _ij ∈ E, t∈ T, N is the end time, N∈[0, |V|-1];

Through the change of the compensation value in the Markov decision model, the actions taken are continuously revised, so that the routing decision-making process has the ability of reinforcement learning.

Step 7, define the global optimal equation.

According to the established Markov decision model and Markov decision theory, the global optimal equation is defined as follows:

${\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\underset{{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; [</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; S</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 0,1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; LN</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; N</span>}\end{array}\right.<span\; class="notranslate">\; ,</span>$

In the formula, u _t (h _t ) is the optimal value at time t; r _t (i, e _ij ) is the reward value of action e _ij in state i at time t; p _t (j|i, e _ij ) is t The state at time i uses the probability of action e _ij to transfer to j; h _t is the trajectory vector before time t, including the state experienced before and the action taken.

Step 8, calculate the optimal decision sequence.

According to the optimal strategy solution process of the finite stage model in Markov decision theory, when the initial state and the terminal state are known, the backward iterative recursive algorithm is used to calculate the global optimization equation, and a set of connected initial states and The optimal decision sequence for the terminal state. Specific steps are as follows:

(1) It is known that the initial state is s and the final state d, s, d∈S, let t=0, h _t = (s), when h _t = (s, L, s), that is, return to the initial state Decision sequence, u _t (h _t ) = ∞,; when h _t = (s, L, d), that is, the decision sequence at the termination moment, u _t (h _t ) = 0;

(2) Update decision time t=t+1, if t∈T, enter (3); otherwise return to (1);

(3) Bring any network node and action, i∈S, u _t (h _t )≠∞, e _ij ∈ A(i _t ) into the global optimal equation, and calculate the optimal decision value u _t (h _t ), if u _t (h _t )=0, then enter (4); otherwise, update trajectory vector h _t =(h _t , i, e _ij ), return to (2);

(4) Store the trajectory vector h _t to obtain the optimal decision sequence: h _t = (s, iL j, d).

Effect of the present invention can be further illustrated by the following simulation results:

1. Simulation conditions

Assuming that the nine planets in the solar system and the moon are the nodes of the delay-tolerant network, their orbits are approximately circular and in the same plane; each planet has two artificial aircraft located at its Lagrangian stable point, and the aircraft is Relay nodes for large planets. The channel rate is 2Mbps, the bandwidth is 1Mhz, the simulation time is 52 weeks; the data packet size is 1024bits; the data packet transmission interval distribution is 5000s; the allowed number of retransmissions is 2 times; the location update interval is 86410s.

2. Simulation content

This simulation is divided into the following four parts:

1) By adopting the method of the present invention, in a hypothetical delay-tolerant network environment, the emulation of routing selection and data packet delivery is carried out. In the simulation, the success rate of data packet transmission, the average delay of data packets and the average number of copies of forwarded data packets are counted respectively.

2) Using the infection routing method, in a hypothetical delay-tolerant network environment, the simulation of selecting routes and transmitting data packets is carried out. In the simulation, the transmission success rate of the data packet, the average delay of the data packet and the average number of copies of the forwarded data packet are counted separately.

3) Using the probabilistic routing method, in a hypothetical delay-tolerant network environment, carry out the simulation of selecting routes and transmitting data packets. In the simulation, the success rate of data packet transmission, the average delay of data packets and the average number of copies of forwarded data packets are counted respectively.

4) The three sets of transmission success rate data obtained in the above three simulations are made into Fig. 3 . The average delay data of the three groups of data packets obtained in the above three simulations are shown in Figure 4. Figure 5 is made of the three sets of average forwarded packet copy data obtained in the above three simulations.

3. Simulation results

Fig. 3 shows that, compared with the infection routing method and the probability routing method, the present invention can enable the delay-tolerant network to obtain a higher data packet transmission success rate.

Fig. 4 shows that, compared with the infection routing method and the probability routing method, the present invention can enable the delay-tolerant network to obtain a lower average delay of data packets.

Fig. 5 shows that, compared with the infection routing method and the probabilistic routing method, the present invention can enable the delay-tolerant network to obtain a lower average number of copies of forwarded data packets.

To sum up, the overall performance of the delay-tolerant network can be improved by adopting the routing decision-making method of the present invention.

Glossary

DTN Delay Tolerant Network

PSN Packet Switching Network

DOA Earliest Discarded

DLE minimum drop

PROPHET Probabilistic Routing Algorithm

ERHR Energy Constraint and History Information Routing Approach.

Claims (3)

1. routing decision method that is used for Delay Tolerant Network comprises following process:

(1) link with discretization is communicated with characteristic description network topology situation:

(1a) in the observation time section, long with given sampling interval Δ peace sliding steps, with the time change link capacity function c between arbitrary network node i and j _Ij(t) discretization obtains discrete series c _Ij(t ₀+ a Δ);

(1b) each node gained discrete series of will sampling spreads all over the whole network, makes each node integrate out a three-dimensional matrice that characterizes with discrete form:

A＝{c _ij(t ₀+aΔ) _|V|×|V|×K，

Wherein, V, E represent respectively consider node and limit in the network, | V|, | E| represents the number on node and limit respectively; I, j=0,1, L, | V|-1; T is the network operation time, t ₀Be time statistics starting point, a is the time series of sampling, a=0, and 1, L K, K are the sample sequence maximum;

(2) according to the three-dimensional matrice A that has obtained, adopt two-value quantization means link capacity, every link obtains following homogeneous Markov model and is:

$c_{\mathrm{ij}}(t_0+\mathrm{a\&Delta;})=\left\{\begin{array}{c}0\\ 1\end{array}\right.,$

It is a markoff process that shifts between " 0 " and one state that this model has embodied each link capacity; In the formula, " 0 " expression link is communicated with, and " 1 " expression disconnects;

(3) according to the Markov model that obtained, the link historical information that obtains with each node characteristics of motion and statistics in the network is utilized the random process method for parameter estimation as a reference, estimates the connected state of each link and the arrival rate μ and the λ of off-state;

(4), obtain following differential equation group and be according to connection and off-state arrival rate μ, λ and the Kolmogorov equation of estimating gained:

$\left\{\begin{array}{c}{P^{\&prime;}}_0\left(t\right)=-\mathrm{\&lambda;}{P}_0\left(t\right)+\mathrm{\&mu;}{P}_1\left(t\right)\\ {P^{\&prime;}}_1\left(t\right)=\mathrm{\&lambda;}{P}_0\left(t\right)-\mathrm{\&mu;}{P}_1\left(t\right)\end{array}\right.,$

Finding the solution above differential equation group gets:

$P_0\left(t\right)=\frac{\mathrm{\&mu;}}{\mathrm{\&lambda;}+\mathrm{\&mu;}}+\frac{\mathrm{\&lambda;}}{\mathrm{\&lambda;}+\mathrm{\&mu;}}{e}^{-(\mathrm{\&lambda;}+\mathrm{\&mu;})t},$

$P_1\left(t\right)=\frac{\mathrm{\&lambda;}}{\mathrm{\&lambda;}+\mathrm{\&mu;}}+\frac{\mathrm{\&mu;}}{\mathrm{\&lambda;}+\mathrm{\&mu;}}{e}^{-(\mathrm{\&lambda;}+\mathrm{\&mu;})t};$

In the following formula, P ₀(t), P ₁(t) be illustrated respectively in the t probability of stability of 0 state and 1 state constantly, P ' ₀(t), P ' ₁(t) be illustrated respectively in t constantly 0 state and 1 state produce probability;

(5), be the Markovian decision model of limited discrete time decision-making of stage with the routing decision procedure definition of Delay Tolerant Network according to each link Markov state model of obtaining: T, S, A (i), p (j ' | i, e _Ij), r (i, e _Ij), wherein:

T represents decision-making constantly, T={0, and 1, L, | V|-1}, | V|-1 represents the maximum permissible value of hop count, promptly allows to skip all other nodes except that source node at most;

The state that S expresses possibility, S=V, promptly a node is represented a state;

The action collection that A (i) expresses possibility, A (i)=e _Ij, e _Ij∈ E, i, j represents network node, e _IjExpression connects the limit of network node i and node j;

P _t(j ' | i, e _Ij) the expression transition probability,

This formula represents that the i node adopts action e constantly at t _IjArrive the probability of node j ', p (e _Ij) expression link e _IjThe connection probability, p (e _Ij)=P ₀(t), i, j, j ' ∈ S, e _Ij∈ E, t ∈ [0, | V|-1];

r _t(i, e _Ij) expression recompense value, This formula represents that the i node adopts action e constantly at t _IjResulting, wherein, c _Ij(t) be link e _IjAt t link capacity constantly, i, j ∈ S, e _Ij∈ E, t ∈ T, N are the finish time, N ∈ [0, | V|-1];

(6) according to Markovian decision model and the Markovian decision theory set up, definition global optimum equation is as follows:

In this formula, u _t(h _t) be t optimal value constantly; r _t(i, e _Ij) be t i state employing constantly action e _IjThe recompense value; p _t(j|i, e _Ij) be t i state employing constantly action e _IjTransfer to the probability of j; h _tBe the preceding constantly track vector of t, state that is experienced before comprising and the action of being taked;

(7) according in the Markovian decision theory, the optimal policy solution procedure of finite horizon model, under the situation of known initial state and state of termination, adopt the back to the described global optimization equation of iterative recursive algorithm computation, obtain one group of optimizing decision sequence that connects initial condition and state of termination.

2. according to claims 1 described routing decision method that is used for Delay Tolerant Network, wherein the described random process method for parameter estimation that utilizes of process (3) estimates the connected state of each link and the arrival rate μ and the λ of off-state, comprises two kinds of situations:

The one, for the internodal link of characteristics of motion the unknown, be the link historical information of utilizing statistics to obtain, adopt maximum-likelihood method or Bayes's method to estimate the arrival rate μ of this link connected state and the arrival rate λ of off-state;

The 2nd, for the known internodal link of the characteristics of motion, be to utilize deep space communication channel loss Model Calculation, become link capacity function c in the time of must this link _Ij(t); Again to the time become link capacity function c _Ij(t) disperse and two-value quantizes to obtain the arrival rate μ of this link connected state and the arrival rate λ of off-state.

3. according to claims 1 described routing decision method that is used for Delay Tolerant Network, wherein calculate as follows to the described global optimization equation of iterative recursive algorithm computation the described employing of process (7) back:

(7a) known initial state is s and state of termination d, s, and d ∈ S makes t=0, h _t=(s), work as h _t=(s, L s), promptly get back to the sequence of decisions of initial condition, u _t(h _t)=∞; Work as h _t=(s, L d), promptly stop sequence of decisions constantly, u _t(h _t)=0;

(7b) upgrade decision-making t=t+1 constantly,, then enter (7c) if t ∈ is T; Otherwise return (7a);

(7c) with arbitrary network node and action, i ∈ S, u _t(h _t) ≠ ∞, e _Ij∈ A (i _t) bring global optimum's equation into, calculate the t optimal value u that makes a strategic decision constantly _t(h _t), if, u _t(h _t)=0 then enters (7d); Otherwise, upgrade track vector h _t=(h _t, i, e _Ij), return (7b);

(7d) storage track vector h _t, obtain optimizing decision sequence: h _t=(s, iL j, d).

Images