CN106954242B - Satellite distributed dynamic multipath routing method based on network coding - Google Patents
Satellite distributed dynamic multipath routing method based on network coding Download PDFInfo
- Publication number
- CN106954242B CN106954242B CN201710104206.2A CN201710104206A CN106954242B CN 106954242 B CN106954242 B CN 106954242B CN 201710104206 A CN201710104206 A CN 201710104206A CN 106954242 B CN106954242 B CN 106954242B
- Authority
- CN
- China
- Prior art keywords
- node
- forwarding
- downstream
- probability
- neighbor
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 40
- 230000005540 biological transmission Effects 0.000 claims description 63
- 238000004364 calculation method Methods 0.000 claims description 14
- 230000001447 compensatory effect Effects 0.000 claims description 5
- 230000008030 elimination Effects 0.000 claims description 3
- 238000003379 elimination reaction Methods 0.000 claims description 3
- 238000004891 communication Methods 0.000 description 4
- 238000011160 research Methods 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000001934 delay Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 239000011159 matrix material Substances 0.000 description 1
- 238000012545 processing Methods 0.000 description 1
- 238000012163 sequencing technique Methods 0.000 description 1
- 238000009827 uniform distribution Methods 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04B—TRANSMISSION
- H04B7/00—Radio transmission systems, i.e. using radiation field
- H04B7/14—Relay systems
- H04B7/15—Active relay systems
- H04B7/185—Space-based or airborne stations; Stations for satellite systems
- H04B7/18578—Satellite systems for providing broadband data service to individual earth stations
- H04B7/18584—Arrangements for data networking, i.e. for data packet routing, for congestion control
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
- H04W40/12—Communication route or path selection, e.g. power-based or shortest path routing based on transmission quality or channel quality
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
- H04W40/248—Connectivity information update
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W84/00—Network topologies
- H04W84/02—Hierarchically pre-organised networks, e.g. paging networks, cellular networks, WLAN [Wireless Local Area Network] or WLL [Wireless Local Loop]
- H04W84/04—Large scale networks; Deep hierarchical networks
- H04W84/06—Airborne or Satellite Networks
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- Astronomy & Astrophysics (AREA)
- General Physics & Mathematics (AREA)
- Computing Systems (AREA)
- Aviation & Aerospace Engineering (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明公开了一种基于网络编码的卫星分布式动态多径路由方法，首先，首先，源节点将数据包拆分为大小相等的M个数据包，M个数据包有相同组号，采用随机线性编码将其编码后转发；中间节点收到一个新数据包时与原先缓存的同组数据包进行重新编码并转发；目的节点，则收到m个数据包后解码获得相应信息。在节点转发编码包时，首先依据下游节点时延信息为其分配优先级，然后在数据包转发时依据其优先级及其它信息为其动态分配转发概率，数据包通过某一下游节点转发时会有失败概率，本发明依据失败概率会以一定概率进行“补偿转发”，提高数据包的成功投递率。本发明对网络突发状况具有良好的动态适应性，在较低冗余的情况下保证较高的数据包成功交付率。
The invention discloses a satellite distributed dynamic multi-path routing method based on network coding. First, first, the source node splits the data packets into M data packets of equal size, the M data packets have the same group number, and use random Linear coding encodes it and then forwards it; when the intermediate node receives a new data packet, it re-encodes and forwards the same group of data packets previously buffered; the destination node decodes and obtains the corresponding information after receiving m data packets. When a node forwards an encoded packet, it first assigns a priority based on the delay information of the downstream node, and then dynamically assigns a forwarding probability to it according to its priority and other information when forwarding the data packet. When the data packet is forwarded through a downstream node, the If there is a failure probability, the present invention will perform "compensation forwarding" with a certain probability according to the failure probability, so as to improve the successful delivery rate of the data packets. The invention has good dynamic adaptability to network emergencies, and ensures a higher successful delivery rate of data packets under the condition of lower redundancy.
Description
Technical Field
The invention relates to a distributed dynamic multipath routing method, in particular to a distributed dynamic multipath routing method applied to a low-orbit information network, belonging to the field of satellite communication.
Background
As an important component of a future spatial information transmission network, a satellite communication network is combined with various foundation communication networks into a whole, and ubiquitous global communication services are provided for different users. The low-orbit satellite network has the advantages of low orbit height, small space-to-ground time delay, simple terminal implementation and the like, and is concerned. However, the topology of the low-orbit satellite network changes dynamically, and the inter-satellite link transmission error is large, which results in a large amount of packet loss, and is difficult to provide efficient and reliable information transmission service.
Therefore, designing efficient, stable and reliable routing protocols has been a research focus of low-orbit satellite networks. Early researches mainly aim at the change rule of satellite topology and provide effective single-path routing algorithms, but the algorithms cannot well solve the problem of unreliable transmission caused by packet loss (packet loss caused by error codes or switching) of inter-satellite links.
Compared with single-path routing, the multi-path routing technology has unique advantages in the aspects of effective bandwidth use, congestion control, reliable transmission and the like, and is an effective means for improving the transmission reliability of the dynamic network. Therefore, some researchers have also begun to apply multipath routing to satellite networks, for example, satellite multipath routing protocol — CEMR (Compact Explicit Multi-routing), dynamic on-demand multipath routing algorithms, and the like. However, most of the existing methods are based on a centralized routing mode, and the nodes are required to know the information of the whole network; meanwhile, although the algorithm can reduce packet loss caused by congestion, the algorithm cannot improve the correct delivery rate of the service under the condition of link error code or link switching.
In view of the above problems, in recent years, some scholars have tried to reduce the influence of inter-satellite link packet loss on network reliable transmission by using network coding, and improve network throughput, balance load and improve transmission reliability by using intermediate node coding, and the method is well applicable to a topology-dynamic satellite network. However, most of the existing methods improve the network throughput through inter-stream network coding, and the protocol complexity is high and the practicability is often insufficient.
Disclosure of Invention
The technical problem to be solved by the invention is as follows: the method has the advantages of low protocol complexity, no need of nodes to know the information of the whole network, execution and the like, and is particularly suitable for a low-orbit information network system with dynamic topology and limited on-satellite processing capacity.
The technical solution of the invention is as follows: a satellite distributed dynamic multipath routing method based on network coding is characterized in that after each node i receives a data packet, the following steps are executed:
(1) judging whether a destination node d in the received data packet is a packet which is sent to the destination node d and is received by the node i for the first time, if so, turning to the step (2), and if not, turning to the step (3);
(2) generating a downstream forwarding node information table facing the destination node d, and entering the step (3); the downstream forwarding node information table comprises the maximum sending queue length Q sent by the node i to the neighbor node j' by taking the destination node d as the destination nodemax(j'), average transmit queue length Qavg(j'), shortest path transmission time delay D for the node i to reach the destination node D through the neighbor node jmin(j ', d) and a forwarding probability P from node i to each neighbor node j' in the list of downstream forwarding nodesj'And j' belongs to CT, wherein CT is the condition which is satisfied in the neighbor nodes of the node i: dmin(j',d)<D, the D is a preset maximum time delay threshold, and the downstream forwarding node information table is according to the Dmin(j ', d) are arranged in a sequence from small to large, and after the forwarding node information table is self-established, the nodes contained in the set CT in the downstream forwarding node information table, the arrangement sequence in the downstream forwarding node table and the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node list are adjusted in real time according to a fixed period delta tj'；
(3) Extracting a source node identifier and a destination node identifier in the data packet, comparing the source node identifier and the destination node identifier with the identifier of the node, and if the node identifier is the source node identifier in the data packet, entering the step (4); if the node identifier is equal to the destination node identifier in the data packet, the step (10) is carried out; otherwise, entering the step (5);
(4) splitting the received data packet into a group of M sub-data packets X with equal sizemWhen a data packet cannot be divided by M, zero padding is carried out on the last sub-packet to obtain a length, and the step (6) is carried out after N is equal to M;
(5) receiving the encoded sub-packets andcaching, when receiving at least N 'coded sub data frames with the same group identification, discarding a header of each coded sub data packet to obtain N' sub data packets: xnN ═ 1, 2., N ', where M/3 ≦ N ' ≦ M, and let N ═ N ' proceed to step (6);
(6) adopting a random linear network coding mode to carry out grouping on N sub-data packets XnN is coded to generate N coded sub-data packets Y of equal sizen，n＝1,2,...N；
(7) Adding the group mark and the coding coefficient as frame head to the front of the coding sub data packet to form a coding sub data frame Yn1,2, N and storing;
(8) according to the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node listj'Respectively forwarding the N encoded sub data packets to corresponding neighbor nodes j';
(9) calculating failure probability P ' from node i to each neighbor node j ' in downstream forwarding node list 'j'And by failure probability P'j'Based on this, a compensatory forwarding probability P ″, is generatedj'And forwards the probability P' with the compensationj'Data packet Yn'retransmit to neighbor node j';
(10) and receiving and storing the coded sub-data packets sent by each node, recovering the original M sub-data packets by a Gaussian elimination method when M coded sub-data packets with the same group identifier are received, and continuing to store and wait when M coded sub-data packets with the same group identifier are not received.
The downstream forwarding node information table is generated according to the transmission delay information table of each node, the nodes contained in the set CT in the downstream forwarding node information table and the arrangement sequence in the downstream forwarding node table are updated along with the change of the transmission delay information table, the transmission delay information table of each node i maintains the transmission delay information table of the node according to a fixed period delta t, i belongs to CS, CS is a set of all node numbers in the network, the transmission delay information table comprises the maximum sending queue length sent by the node i to each neighbor node j by taking each other node t in the network as a destination nodeDegree Qmax(j) Average transmit queue length Qavg(j) And shortest path transmission time delay D of the node to the destination node t through each neighbor node jmin(j, t), j belongs to CL, CL is the set of all neighbor node numbers of the node i, and CL belongs to CS.
Shortest path transmission time delay D from node i to destination node t via each neighbor node jmiThe calculation method of n (j, t), j epsilon CL is as follows:
Dmin(j,t)＝D(e(j,t))+D(e(i,j))+dq，
in the formula, D (e (j, t)) and D (e (i, j)) are respectively the shortest link transmission time delay between a neighbor node j and a destination node t and the link transmission time delay between each neighbor node j and a node i, the link transmission time delay is obtained by dividing the length of the shortest path of the geometric topology of the satellite at the time t calculated by ephemeris by the speed of light, and DqFor the transmit queue delay for node i to each neighbor node j,
q (j) is the real-time queue length on node i to each neighbor node j, i.e., the number of packets in a queue, LavIs the average packet length, and the unit bit, C is the link bandwidth.
When the serial number of the downstream neighbor node j' in the downstream forwarding node table is S, S belongs to [1, S ∈]S is the total number of neighbor nodes in the downstream forwarding node list, and the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node listj'The following method was used for calculation:
(2.1) initializing the normalized forwarding probability p corresponding to each downstream neighbor node jsThe specific calculation is as follows: firstly, a random number between 0 and 1 is generated for all nodes j' in a downstream forwarding node table as an initial probability pint(s) then calculating a normalized forwarding probability p for each node js：
(2.2) according to each node j' normalized Forwarding probability psCalculating the relative weight r of the node jj'The specific calculation is as follows:
(2.3) relative weight r according to node jj'And queue status of node j 'calculate normalized relative weight of node j' as
When the downstream node j' transmission queue is full, the normalized relative weight is set as
When the sending queue of the downstream node j ' is not full, namely j ' belongs to BQ, wherein BQ is a non-full queue set, the normalized relative weight of the non-full downstream node j ' in the downstream node list is calculated as follows:
when in the above formulak∈BQrkWhen the value is 0, setting the standardized relative weight of the downstream node of which the last sending queue in the downstream forwarding table is not full as 1, and setting the standardized relative weight of other nodes as 0;
(2.4) normalized relative weight according to compute node j' of
Calculating a forwarding probability P from node i to each neighbor node j' in the downstream forwarding node listj'：
A is the set of all node numbers with sequence numbers before the j' node in the node downstream forwarding node table.
Step (2) according to the fixationIs adjusted in real time from node i to the forwarding probability P of each neighbor node j' in the downstream forwarding node listj'The method comprises the following specific steps:
first, an average transmission queue threshold min is setthAnd maxth；
Then, the average transmission queue length Q is judgedavg(j'), when the average transmission queue length Q isavg(j') is less than minthWhen it is, let Pj'The change is not changed; when average transmission queue length Qavg(j') is greater than maxthWhen it is, let Pj'Is 0; when average queue length Qavg(j')∈[minth,maxth]When is, Pj'Linear decrease, i.e.: pj' (the cycle)＝Pj' (last cycle)Δ P, up to Pj' (the cycle)Less than or equal to 0, when Pj' (the cycle)When less than 0, let Pj'0, said Pj'The variation Δ p is:
Δp＝pj'(minth-Qavg(j'))/(maxth-minth)。
the failure probability P 'in the step (9)'j'The calculation method comprises the following steps:
when in use
Of (m), P'j'＝0；
When Q isavg(j')∈[minth,maxth]The method comprises the following steps:
P′j'＝1-(1-P)(1-Pa)
in the formula, PaIs the average link loss, P is the transmission queue packet loss probability, P is the current average queue length Qavg(j') function:
the compensatory forwarding probability is P'j'～5P′j'A random number in between.
Compared with the prior art, the invention has the beneficial effects that:
(1) the network node of the invention can judge the conditions of link failure, congestion and the like without acquiring the topology information of the whole network to calculate and maintain fixed multipath, and the node only needs the information provided by the neighbor node, so that the proper next path is selected, the protocol complexity and the algorithm overhead are reduced, and the invention can be well applied to the low-orbit information network which has dynamic topology and is difficult to accurately acquire the network state information.
(2) In the data packet forwarding process, the protocol can dynamically distribute the forwarding probability according to the state of the downstream node, reduce network congestion, perform redundancy compensation on the forwarding failure probability, improve the successful delivery rate of the data packet and effectively reduce packet loss caused by inter-satellite switching and inter-satellite link error codes.
(3) The protocol of the invention reduces the correlation between the redundant packet and the original data packet through the network coding in the stream, thereby improving the successful delivery rate of the data packet under the same redundancy.
Drawings
FIG. 1 is a flow chart of a specific implementation of the method of the present invention;
Detailed Description
The present invention will be described in detail below with reference to the accompanying drawings and examples.
As shown in fig. 1, the present invention provides a network coding based satellite distributed dynamic multipath routing method, which has at its core 3 links of initialization, network coding, and probability compensation forwarding. At the beginning of time interval Δ t, i.e. at time t0，t1，...，tnWithin the time interval delta t, the topology of the satellite network is unchanged, and each node updates the transmission delay information from the node to all other nodes according to the ephemeris; when the data packet is transmitted, the method does not need to establish and maintain a plurality of paths in advance, and the data packet is directly delivered according to the information of the neighbor nodes. The method can utilize the feedback information of the neighbor node to detect the conditions of link failure, area congestion and the like in time, change the forwarding strategy of the downstream node in time without any response of the source node, and simultaneously, in order to reduce the packet loss rate, the algorithm introduces network coding and adopts a dynamic probability forwarding party in the coding packet forwarding strategyThe method is carried out. The distributed forwarding process enables data to well avoid a congestion area, reduces time delay, and realizes the adaptability of the algorithm to a dynamic network with minimum time delay and packet loss cost.
The method for distributed dynamic multipath routing of satellite based on network coding will be described in detail below.
Each node i, i belongs to CS, CS is a set of node numbers in the network, a transmission delay information table from the node to other nodes t is updated according to a fixed period delta t, t belongs to CS, t is not equal to i, the transmission delay information table comprises all other nodes t as target nodes, t belongs to CS, t is not equal to i, and the maximum sending queue length Q sent to a neighbor node j by the node imax(j) Average transmit queue length Qavg(j) And shortest path transmission time delay D of the node i to the destination node through the neighbor node jmin(j, t), j belongs to CL, CL is the set of all the neighbor node numbers of the node i, and CL belongs to CS. The transmission delay information table is shown in table 1.
Table 1 transmission delay information table
And each node i updates the transmission delay information according to the distance from the current node to all other nodes by ephemeris update according to a fixed time interval delta t. Qmax(j) And Qavg(j) Can be read directly from the node i router hardware register.
Shortest path transmission time delay D from node i to destination node t via each neighbor node jminThe calculation method of (j, t), j ∈ CL is as follows:
Dmin(j,t)＝D(e(j,t))+D(e(i,j))+dq，
in the formula, D (e (j, t)) and D (e (i, j)) are respectively the shortest link transmission time delay between a neighbor node j and a destination node t and the link transmission time delay between each neighbor node j and a node i, the link transmission time delay is obtained by dividing the length of the shortest path of the geometric topology of the satellite at the time t calculated by ephemeris by the speed of light, and DqTo each neighbor node for node iThe transmit queue delay of point j,
q (j) is the real-time queue length on node i to each neighbor node j, i.e., the number of packets in a queue, LavIs the average packet length, and the unit bit, C is the link bandwidth.
After receiving the data packet, the node i executes the following steps:
(1) and judging whether a destination node d in the received data packet is a packet which is sent to the destination node d and received by the node i for the first time, if the destination node of the packet is the packet which is sent to the destination node and received by the node i for the first time, turning to the step (2), and if not, turning to the step (3).
(2) Extracting a destination node d in the data packet, generating a downstream forwarding node list facing the destination node d according to the transmission delay information from the node to the destination node d, and entering the step (3); as shown in table 2, the information table of the downstream forwarding node includes the maximum transmission queue length Q from the destination node d to the neighboring node j' and from the node imax(j'), average transmit queue length Qavg(j'), shortest path transmission time delay D for the node i to reach the destination node D through the neighbor node jmin(j ', d) and a forwarding probability P from node i to each neighbor node j' in the list of downstream forwarding nodesj'And j' belongs to CT, wherein CT is the condition which is satisfied in the neighbor nodes of the node i: dmin(j',d)<D, the D is a preset maximum time delay threshold, and the D is generally a set { D }min(j ', D), j' e CL } and downstream forwarding node information table according to Dmin(j ', d) are arranged in a sequence from small to large, and after the forwarding node information table is self-established, the nodes contained in the set CT in the downstream forwarding node information table, the arrangement sequence in the downstream forwarding node table and the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node list are adjusted in real time according to a fixed period delta tj'；
Table 2 downstream forwarding node list
In this table, the destination node contains only D, all Dmin(j',d)<D and sorting according to size. This table in fact constitutes a sub-graph of the network. At each subsequent time interval, table 2 will be updated synchronously with table 1.
When the downstream neighbor node j' forwards the sequence number S in the node table downstream, S ═ 1, S]S is the total number of neighbor nodes in the downstream forwarding node list, and the following method is adopted to calculate the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node listj'：
(2.1) initializing the normalized forwarding probability p corresponding to each downstream neighbor node jsThe specific calculation is as follows: firstly, a random number between 0 and 1 is generated for all nodes j' in a downstream forwarding node table as an initial probability pint(s) then calculating a normalized forwarding probability p for each node js：
(2.2) normalizing the forwarding probability p according to each node jsCalculating the relative weight r of the node jj'The specific calculation is as follows:
(2.3) relative weight r according to node jj'And queue status of node j 'calculate normalized relative weight of node j' as
When the downstream node j' transmission queue is full, the normalized relative weight is set as
When the sending queue of the downstream node j ' is not full, namely j ' belongs to BQ, wherein BQ is a non-full queue set, the normalized relative weight of the non-full downstream node j ' in the downstream node list is calculated as follows:
when in the above formulak∈BQrkWhen the value is 0, setting the standardized relative weight of the downstream node of which the last sending queue in the downstream forwarding table is not full as 1, and setting the standardized relative weight of other nodes as 0;
(2.4) normalized relative weight according to compute node j' of
Calculating a forwarding probability P from node i to each neighbor node j' in the downstream forwarding node listj'：
A is the set of all node numbers with sequence numbers before the j' node in the node downstream forwarding node table.
Setting the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node listj'Then, the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node list is adjusted in real time according to a fixed period delta tj'The method comprises the following specific steps:
first, an average transmission queue threshold min is setthAnd maxth；
Then, the average transmission queue length Q is judgedavg(j'), when the average transmission queue length Q isavg(j') is less than minthWhen it is, let Pj'The change is not changed; when average transmission queue length Qavg(j') is greater than maxthWhen it is, let Pj'Is 0; when average queue length Qavg(j')∈[minth,maxth]When is, Pj'Linear decrease, i.e.: pj' (the cycle)＝Pj' (last cycle)Δ P, up to Pj' (the cycle)Less than or equal to 0, when Pj' (the cycle)When less than 0, let Pj'＝0。
The P isj'The variation Δ p is:
Δp＝pj'(minth-Qavg(j'))/(maxth-minth)
(3) extracting a source node identifier and a destination node identifier in the data packet, comparing the source node identifier and the destination node identifier with the identifier of the node, and if the node identifier is equal to the source node identifier, entering the step (4); if the node identifier is equal to the destination node identifier, the step (10) is carried out; otherwise, entering the step (5);
(4) splitting the received data packet into a group of M sub-data packets with equal size as a coding source data packet XmM is 1,2, said, M is a fixed value, when the data packet cannot be divided by M, the last sub-packet is zero-padded to a sufficient length, usually M is a power of 2, such as 32 bytes, 64 bytes, etc., so that N is M, and step (6) is performed;
(5) receiving the encoded sub-data packets and caching, and when receiving at least N 'encoded sub-data frames with the same group identification, discarding a frame header of each encoded sub-data packet to obtain N' sub-data packets: xnN ═ 1, 2., N ', where M/3 ≦ N ' ≦ M, and let N ═ N ' proceed to step (6);
(6) adopting a random linear network coding mode to carry out grouping on N sub-data packets XnN is coded to generate N coded sub-data packets Y of equal sizen，n＝1,2,...N；
Generating N equal-sized coded data packets YnThe specific coding formula of (2) is:
coding coefficient gnmN is 1,2, N, theoretically in a finite field
Randomly selected in a completely independent and uniform manner, i.e. code seriesThe random numbers are generated according to uniform distribution, and the random generation process of different coding coefficients is independent, wherein s represents the range of a finite field Fq, and in the scheme, s is 8. S generally takes the power of 2.
For the intermediate node, the group of N coding sub-data packets is coded in a random linear network coding mode, and the coding coefficients are randomly selected to obtain N forwarding coding sub-data packets YnN is 1,2, 3.. N, with the advantage that: further reducing the correlation between the coded packets, improving the decoding success rate, the linear recoding of the coded packets is still the linear combination of the corresponding original packets:
in the formula, N1The number of the last coded data packet.
(7) Adding the group mark and the coding coefficient as frame headers to the front of the sub-data packet to form a coding sub-data packet Yn1,2, N and storing;
(8) according to the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node listj'And respectively forwarding the N encoded sub data packets to corresponding neighbor nodes j'.
Each node has at least one downstream node, each downstream node corresponds to a transmission queue, and the time delay from the node to the destination node is different. The algorithm assigns forwarding priorities to a plurality of downstream nodes, node to destination node time delays (D)minThe smaller (j', d)), the higher the forwarding priority. And the nodes dynamically allocate forwarding probabilities to the downstream nodes according to the information of the downstream nodes. When the data packet is forwarded, the downstream nodes are polled in sequence from high to low according to the priority. When the data packet is determined to be forwarded through a certain downstream node, the data packet has a certain failure probability. In order to reduce the packet loss rate, the algorithm dynamically performs "compensation forwarding" on the data packet, that is, forwards the duplicated data packet with a certain probability.
The method transmits the queue information according to the downstream node, and carries out the probability forwarding of the coding packet. When N encoded packets need to be forwarded, the downstream node forwards the column from downstreamThe first node in the table begins to be polled. When the neighbor node j' is polled, NxP will bej'Transmitting the coded data packet to a neighbor node j';
(9) calculating failure probability P ' from node i to each neighbor node j ' in downstream forwarding node list 'j'And is in P'j'～5P′j'A random number is generated between the two as the compensation forwarding probability P ″)j'And forwarding the probability with the offset
Pj'The packet is repeatedly forwarded to the neighbor node j'.
Probability of failure P'j'The calculation method comprises the following steps:
when in use
Of (m), P'j'＝0；
When Q isavg(j')∈[minth,maxth]The method comprises the following steps:
P′j'＝1-(1-P)(1-Pa)
in the formula, PaIs the average link loss, P is the transmission queue packet loss probability, P is the current average queue length Qavg(j') function:
without loss of generality, the average packet loss rate P of the linkaAnd maximum packet drop probability max of transmit queuepObtained by counting past data.
Pj′～5Pj' random number between them is used as forwarding threshold, and the generated random number is assumed to be 2Pj', then forward the probability 2P with the offsetj' will data packet Yn'retransmit to neighbor node j', that is, have 1-2PjThe probability of' is not forwarded.
(10) And receiving and storing the coded sub-data packets sent by each node, recovering the original M sub-data packets by a Gaussian elimination method when M coded sub-data packets with the same group identifier are received, and continuing to store and wait when M coded sub-data packets with the same group identifier are not received. .
Suppose the received packet is Y1，Y2，...，YnIf the decoding matrix G corresponding to the encoding packet coefficient vector is [ G ═ Gj1，gj2，...，gjm](j ═ 1, 2.. multidot.m) full rank, then can be passed through [ X ·1,X2,...Xm]T＝G-1[Y1,Y2,...Ym]TAnd recovering the original data packet. If m coded packets are not collected or cannot be decoded, continuing to store and wait.
In summary, the most core design idea of the method is as follows:
(1) for an arriving packet, if the destination node of the packet is the packet which is sent to the destination node and received by the node for the first time, the node needs to be initialized, and the initialization includes parameter definition, downstream node selection and downstream node sequencing.
(2) In a network coding link, a source node divides a data packet into M data packets with equal size, wherein the M data packets have the same group number, and the data packets are coded and then forwarded by adopting random linear coding; when receiving a new data packet, the intermediate node recodes and forwards the same group of data packets cached originally, and then clears the cache; and if the destination node is the destination node, decoding the received M data packets to obtain corresponding information.
(3) For probability compensation forwarding, when a node forwards a coding packet, each downstream node has a forwarding opportunity, when the node is initialized, the node firstly distributes priority to the downstream node according to the time delay information of the downstream node, then dynamically distributes forwarding probability to the data packet according to the priority and other information of the data packet, when the data packet is forwarded through a certain downstream node, the data packet has failure probability, and an algorithm carries out compensation forwarding according to the failure probability and with a certain probability, so that the successful delivery rate of the data packet is improved. In this way, when congestion occurs locally, the probability of failure of forwarding the coded packet increases, the algorithm can increase the compensatory forwarding probability, and when the downstream link fails, the node will remove the failed node from the set of downstream nodes and update the set. The algorithm has good dynamic adaptability to network emergency, and ensures higher successful delivery rate of the data packet under the condition of lower redundancy.
Those skilled in the art will appreciate that those matters not described in detail in the present specification are well known in the art.
Claims (7)
1. A satellite distributed dynamic multipath routing method based on network coding is characterized in that after each node i receives a data packet, the following steps are executed:
(1) if yes, switching to the step (2), and if not, switching to the step (3);
(2) generating a downstream forwarding node information table facing the destination node d, and entering the step (3); the downstream forwarding node information table comprises the maximum sending queue length Q sent by the node i to the neighbor node j' by taking the destination node d as the destination nodemax(j'), average transmit queue length Qavg(j'), shortest path transmission time delay D for the node i to reach the destination node D through the neighbor node jmin(j ', d) and a forwarding probability P from node i to each neighbor node j' in the list of downstream forwarding nodesj'And j' belongs to CT, wherein CT is the condition which is satisfied in the neighbor nodes of the node i: dmin(j',d)<D, the D is a preset maximum time delay threshold, and the downstream forwarding node information table is according to the Dmin(j ', d) are arranged in a sequence from small to large, and after the forwarding node information table is self-established, the nodes contained in the set CT in the downstream forwarding node information table, the arrangement sequence in the downstream forwarding node table and the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node list are adjusted in real time according to a fixed period delta tj'；
(3) Extracting a source node identifier and a destination node identifier in the data packet, comparing the source node identifier and the destination node identifier with the identifier of the node, and if the node identifier is the source node identifier in the data packet, entering the step (4); if the node identifier is equal to the destination node identifier in the data packet, the step (10) is carried out; otherwise, entering the step (5);
(4) splitting the received data packet into a group of M sub-data packets X with equal sizemWhen a data packet cannot be divided by M, zero padding is carried out on the last sub-packet to obtain a length, and the step (6) is carried out after N is equal to M;
(5) receiving the encoded sub-data packets and caching, and when receiving at least N 'encoded sub-data frames with the same group identification, discarding a frame header of each encoded sub-data packet to obtain N' sub-data packets: xnN ═ 1, 2., N ', where M/3 ≦ N ' ≦ M, and let N ═ N ' proceed to step (6);
(6) adopting a random linear network coding mode to carry out grouping on N sub-data packets XnN is coded to generate N coded sub-data packets Y of equal sizen,n＝1,2,...N；
(7) Adding the group mark and the coding coefficient as frame headers to the front of the coding subdata packet to form a coding subdata frame Y'nN ═ 1,2,. N, and stored;
(8) according to the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node listj'Respectively forwarding the N encoded sub data packets to corresponding neighbor nodes j';
(9) calculating failure probability P ' from node i to each neighbor node j ' in downstream forwarding node list 'j'And by failure probability P'j'Based on this, a compensatory forwarding probability P ″, is generatedj'And forwards the probability P' with the compensationj'Will data packet Y'nRetransmitting to the neighbor node j';
(10) and receiving and storing the coded sub-data packets sent by each node, recovering the original M sub-data packets by a Gaussian elimination method when M coded sub-data packets with the same group identifier are received, and continuing to store and wait when M coded sub-data packets with the same group identifier are not received.
2. The network coding-based satellite distributed dynamic multipath routing method of claim 1, wherein said downstream path is a path of a multipathThe forwarding node information table is generated according to the transmission delay information table of each node, the nodes contained in a set CT in a downstream forwarding node information table and the arrangement sequence in the downstream forwarding node table are updated along with the change of the transmission delay information table, the transmission delay information table of each node i maintains the transmission delay information table of the node according to a fixed period delta t, i belongs to CS, CS is a set of all node numbers in the network, the transmission delay information table comprises a maximum sending queue length Q sent to each neighbor node j by the node i by taking each other node t in the network as a destination nodemax(j) Average transmit queue length Qavg(j) And shortest path transmission time delay D of the node to the destination node t through each neighbor node jmin(j, t), j belongs to CL, CL is the set of all neighbor node numbers of the node i, and CL belongs to CS.
3. The method as claimed in claim 2, wherein the shortest path transmission delay D to the destination node is from node i to the destination node t via each neighbor node jminThe calculation method of (j, t), j ∈ CL is as follows:
Dmin(j,t)＝D(e(j,t))+D(e(i,j))+dq，
in the formula, D (e (j, t)) and D (e (i, j)) are respectively the shortest link transmission time delay between a neighbor node j and a destination node t and the link transmission time delay between each neighbor node j and a node i, the link transmission time delay is obtained by dividing the length of the shortest path of the geometric topology of the satellite at the time t calculated by ephemeris by the speed of light, and DqFor the transmit queue delay for node i to each neighbor node j,
q (j) is the real-time queue length on node i to each neighbor node j, i.e., the number of packets in a queue, LavIs the average packet length, and the unit bit, C is the link bandwidth.
4. The network coding based satellite distributed dynamic multipath as claimed in claim 1The routing method is characterized in that when the serial number of a downstream neighbor node j' in a downstream forwarding node table is S, S belongs to [1, S ∈]S is the total number of neighbor nodes in the downstream forwarding node list, and the forwarding probability P from the node i to each neighbor node j' in the downstream forwarding node listj'The following method was used for calculation:
(2.1) initializing the normalized forwarding probability p corresponding to each downstream neighbor node jsThe specific calculation is as follows: firstly, a random number between 0 and 1 is generated for all nodes j' in a downstream forwarding node table as an initial probability pint(s) then calculating a normalized forwarding probability p for each node js：
(2.2) normalizing the forwarding probability p according to each node jsCalculating the relative weight r of the node jj'The specific calculation is as follows:
(2.3) relative weight r according to node jj'And queue status of node j 'calculate normalized relative weight of node j' as
When the downstream node j' transmission queue is full, the normalized relative weight is set as
When the sending queue of the downstream node j ' is not full, namely j ' belongs to BQ, wherein BQ is a non-full queue set, the normalized relative weight of the non-full downstream node j ' in the downstream node list is calculated as follows:
when in the above formulak∈BQrkWhen the value is 0, setting the standardized relative weight of the downstream node of which the last sending queue in the downstream forwarding table is not full as 1, and setting the standardized relative weight of other nodes as 0;
(2.4) normalized relative weight according to compute node j' of
Calculating a forwarding probability P from node i to each neighbor node j' in the downstream forwarding node listj'：
A is the set of all node numbers with sequence numbers before the j' node in the node downstream forwarding node table.
5. The method of claim 1, wherein the step (2) adjusts the forwarding probability P from node i to each neighbor node j' in the downstream forwarding node list in real time according to a fixed period Δ tj'The method comprises the following specific steps:
first, an average transmission queue threshold min is setthAnd maxth；
Then, the average transmission queue length Q is judgedavg(j'), when the average transmission queue length Q isavg(j') is less than minthWhen it is, let Pj'The change is not changed; when average transmission queue length Qavg(j') is greater than maxthWhen it is, let Pj'Is 0; when average queue length Qavg(j')∈[minth,maxth]When is, Pj'Linear decrease, i.e.: pj' (the cycle)＝Pj' (last cycle)Δ P, up to Pj' (the cycle)Less than or equal to 0, when Pj' (the cycle)When less than 0, let Pj'0, said Pj'The variation Δ p is:
Δp＝pj'(minth-Qavg(j'))/(maxth-minth)。
6. the method according to claim 5, wherein the failure probability P 'in step (9) is'j'The calculation method comprises the following steps:
when in use
Of (m), P'j'＝0；
When Q isavg(j')∈[minth,maxth]The method comprises the following steps:
P′j'＝1-(1-P)(1-Pa)
in the formula, PaIs the average link loss, P is the transmission queue packet loss probability, P is the current average queue length Qavg(j') function:
maxpthe maximum packet drop probability for the transmit queue.
7. The network coding-based satellite distributed dynamic multipath routing method of claim 1, wherein said compensatory forwarding probability is P'j'～5P′j'A random number in between.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710104206.2A CN106954242B (en) | 2017-02-24 | 2017-02-24 | Satellite distributed dynamic multipath routing method based on network coding |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710104206.2A CN106954242B (en) | 2017-02-24 | 2017-02-24 | Satellite distributed dynamic multipath routing method based on network coding |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN106954242A CN106954242A (en) | 2017-07-14 |
| CN106954242B true CN106954242B (en) | 2020-04-10 |
Family
ID=59466533
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710104206.2A Active CN106954242B (en) | 2017-02-24 | 2017-02-24 | Satellite distributed dynamic multipath routing method based on network coding |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN106954242B (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109560860B (en) * | 2018-12-25 | 2021-02-09 | 长沙天仪空间科技研究院有限公司 | Satellite communication routing method and system |
| CN111585638B (en) * | 2020-04-22 | 2022-04-15 | 浙江时空道宇科技有限公司 | Inter-satellite network communication method, communication satellite and system |
| CN112887203B (en) * | 2021-01-12 | 2021-10-08 | 中国人民解放军31007部队 | TDMA wireless network multi-path data transmission method based on network coding |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2004028034A1 (en) * | 2002-09-23 | 2004-04-01 | Inmarsat Ltd | Communication method and apparatus |
| CN101651599A (en) * | 2008-08-12 | 2010-02-17 | 中国移动通信集团公司 | Multipath wireless routing method and device |
| CN102143566A (en) * | 2011-02-18 | 2011-08-03 | 上海大学 | Life cycle maximizing method for distributed wireless video sensor network |
| CN102572717A (en) * | 2012-02-20 | 2012-07-11 | 南京中通电气有限公司 | Multipath routing reliable transmission method based on network coding |
| CN105764084A (en) * | 2016-02-05 | 2016-07-13 | 南京邮电大学 | Wireless sensor network multipath routing protocol realization method |
-
2017
- 2017-02-24 CN CN201710104206.2A patent/CN106954242B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2004028034A1 (en) * | 2002-09-23 | 2004-04-01 | Inmarsat Ltd | Communication method and apparatus |
| CN101651599A (en) * | 2008-08-12 | 2010-02-17 | 中国移动通信集团公司 | Multipath wireless routing method and device |
| CN102143566A (en) * | 2011-02-18 | 2011-08-03 | 上海大学 | Life cycle maximizing method for distributed wireless video sensor network |
| CN102572717A (en) * | 2012-02-20 | 2012-07-11 | 南京中通电气有限公司 | Multipath routing reliable transmission method based on network coding |
| CN105764084A (en) * | 2016-02-05 | 2016-07-13 | 南京邮电大学 | Wireless sensor network multipath routing protocol realization method |
Also Published As
| Publication number | Publication date |
|---|---|
| CN106954242A (en) | 2017-07-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR101610715B1 (en) | One-way data transmission and reception system, and one-way data transmission and reception method | |
| US9553956B2 (en) | Self-adaptive network control transmission method and system based on TCP | |
| CN105450357B (en) | The adjustment of coding parameter, feedback information processing method and processing device | |
| WO2013116456A1 (en) | Multi-path data transfer using network coding | |
| CN112751644B (en) | Data transmission method, device and system and electronic equipment | |
| JP2013526098A (en) | System and method for achieving high throughput | |
| CN106954242B (en) | Satellite distributed dynamic multipath routing method based on network coding | |
| CN110138432B (en) | DTN data transmission method based on network coding and relay buffer assistance | |
| CN113141207B (en) | Time-sensitive service-oriented spatial information network data transmission method | |
| CN111711565B (en) | Multi-path routing method for high-speed interconnection dragonfly+ network | |
| CN107210908A (en) | Method and system for the rate adaptation of data traffic | |
| CN108282402B (en) | Packet scattering method based on coding in data center network | |
| CN113055285A (en) | Self-adaptive data transmission method based on MPTCP and network coding | |
| CN107222404A (en) | The parallel route retransmission method of redundancy encoding is carried in WOBAN | |
| Liu et al. | TCP performance in wireless access with adaptive modulation and coding | |
| WO2017161148A1 (en) | Method for congestion relief with network coding | |
| CN102546096A (en) | Real-time multicasting self-adaptation optimization method based on unequal error protection | |
| CN112887203B (en) | TDMA wireless network multi-path data transmission method based on network coding | |
| CN114095418A (en) | A reliable data transmission method for the Industrial Internet of Things in a wireless optical fiber hybrid network scenario | |
| Engelmann et al. | Exploiting parallelism with random linear network coding in high-speed ethernet systems | |
| CN102325009A (en) | A Reliable Transmission Method of Network Coding Multicast Data Stream Based on Forward Error Correction | |
| CN118317388A (en) | A low-orbit satellite routing method based on link quality perception and network coding | |
| CN115378548B (en) | Connectionless-oriented binary superposition determination linear network code transmission method | |
| Nikopour et al. | Linear Packet Network Coding to Enhance Reliability and Resiliency of Next Generation Wireless Networks with Topological Redundancies | |
| Li et al. | Adaptive network coding algorithm for LEO satellite networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |