[go: up one dir, main page]

CN102148664B - Inter-multicast network coding control method applied to multi-source multi-destination network - Google Patents

Inter-multicast network coding control method applied to multi-source multi-destination network Download PDF

Info

Publication number
CN102148664B
CN102148664B CN 201110099631 CN201110099631A CN102148664B CN 102148664 B CN102148664 B CN 102148664B CN 201110099631 CN201110099631 CN 201110099631 CN 201110099631 A CN201110099631 A CN 201110099631A CN 102148664 B CN102148664 B CN 102148664B
Authority
CN
China
Prior art keywords
node
data
multicast
network coding
network
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.)
Expired - Fee Related
Application number
CN 201110099631
Other languages
Chinese (zh)
Other versions
CN102148664A (en
Inventor
邹君妮
谭冲
汪敏
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
SHANGHAI UNIVERSITY
Original Assignee
SHANGHAI UNIVERSITY
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by SHANGHAI UNIVERSITY filed Critical SHANGHAI UNIVERSITY
Priority to CN 201110099631 priority Critical patent/CN102148664B/en
Publication of CN102148664A publication Critical patent/CN102148664A/en
Application granted granted Critical
Publication of CN102148664B publication Critical patent/CN102148664B/en
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Landscapes

  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

The invention discloses an inter-multicast network coding control method applied to a multi-source multi-destination network, which comprises that: an intermediate node of the network judges whether inter-multicast network coding is required or not by comparing a transmission gain obtained by direct data storage and forwarding with the transmission gain obtained by the inter-multicast network coding; and simultaneously, the intermediate node judges whether the inter-multicast network coding can be decoded or not according to data information received by exchange with a downstream node of the intermediate node, and selects an optimal multicast group to perform the inter-multicast network coding. By the method, network throughput can be effectively increased, the decoding performance of the inter-multicast network coding is ensured at the same time, and when the bandwidth of a network link is finite, transmission fairness among the multicast groups can be effectively ensured.

Description

应用于多源多汇网络的组播间网络编码控制方法Multicast network coding control method applied to multi-source multi-sink network

技术领域 technical field

本发明涉及的是一种应用于多源多汇网络的组播间网络编码控制方法，网络中的中间节点通过比较单纯存储转发数据的传输增益和进行组播间网络编码增后的传输增益的大小，可以判断是否需要进行网络编码；同时中间节点和其下游节点交换所收到的数据信息可以判断组播间网络编码是否可以解码，以及如何进行组播间网络编码。 The present invention relates to a multicast inter-network coding control method applied to a multi-source multi-sink network. The intermediate node in the network compares the transmission gain of simply storing and forwarding data with the transmission gain after multicast inter-network coding increases. The size can determine whether network coding is required; at the same time, the data information exchanged between the intermediate node and its downstream nodes can determine whether the network coding between multicasts can be decoded, and how to perform network coding between multicasts.

技术背景 technical background

在网络通信中，如何最大化信息交互提高网络吞吐量一直是信息论理论和网络技术研究的热点。网络编码技术允许网络中间节点进行数据融合编码，与不同于传统的存储转发技术相比，可以有效地提高网络的吞吐量。 In network communication, how to maximize information interaction and improve network throughput has always been a hot topic in information theory and network technology research. Network coding technology allows the intermediate nodes of the network to perform data fusion coding, which can effectively improve the throughput of the network compared with the traditional store-and-forward technology.

一般的通信网络，通常存着多个组播组，即有多个源节点和多个目的节点。每一个组播组由一个源节点发起，通过中间转发节点，将采集的数据发送到多个目的节点。传统的网络编码，通常是将网络编码技术应用一个组播组内部，网络中的中间节点可以将收到来自同一个源节点的数据进行线性组合，并将编码生成的数据分发出去。这种组播内的网络编码可以提高单独一个组播的吞吐量，而对于整个网络整体的吞吐量提高并没有贡献。因为多个组播组之间存着大量公用的中间转发节点，相应的链路带宽被多个组播组公用，其有限的链路带宽制约了整个网络的吞吐量提高。 A general communication network usually has multiple multicast groups, that is, multiple source nodes and multiple destination nodes. Each multicast group is initiated by a source node, and the collected data is sent to multiple destination nodes through an intermediate forwarding node. Traditional network coding usually applies network coding technology to a multicast group, and intermediate nodes in the network can linearly combine the data received from the same source node and distribute the data generated by the coding. The network coding in this multicast can improve the throughput of a single multicast, but does not contribute to the improvement of the overall throughput of the entire network. Because there are a large number of common intermediate forwarding nodes between multiple multicast groups, the corresponding link bandwidth is shared by multiple multicast groups, and the limited link bandwidth restricts the throughput improvement of the entire network.

传统的组播内网络编码，可以看作是一种特殊的组播间网络编码。当网络中的只存在一个组播时，组播间网络编码将退化成组播内网络编码。比较起传统组播内网络编码，组播间网络编码更为复杂。如何选择编码的组播组和保证组播间网络编码的可解码性是组播间网络编码的主要研究问题。 Traditional intra-multicast network coding can be regarded as a special inter-multicast network coding. When there is only one multicast in the network, the inter-multicast network coding will degenerate into the intra-multicast network coding. Compared with traditional intra-multicast network coding, inter-multicast network coding is more complicated. How to select the coded multicast group and ensure the decodability of inter-multicast network coding is the main research problem of inter-multicast network coding.

发明内容 Contents of the invention

本发明的目的在于针对如何在多个组播组之间应用网络编码技术的问题，提出了一种应用于多源多汇网络的组播间网络编码的控制方法，该方法能来提高链路利用增加网络的吞吐量，并保证网络编码可解码性。 The purpose of the present invention is to solve the problem of how to apply network coding technology between multiple multicast groups, and propose a control method for network coding between multicast networks applied to multi-source and multi-sink networks. Utilization increases the throughput of the network and guarantees the decodability of network coding.

为达到上述目的，本发明的构思是：网络中间节点在收到来自不同组播组的数据时，比较存储转发获得的传输增益和进行组播间网络编码获得的传输增益的大小，判断是否需要进行组播间网络编码；中间节点与其下游节点交换收到的数据信息，判断组播间网络编码的解码性，从而选择合适的组播组，对它们的数据进行组播间网络编码。 In order to achieve the above object, the idea of the present invention is: when the network intermediate node receives data from different multicast groups, compare the transmission gain obtained by storing and forwarding with the transmission gain obtained by performing multicast inter-network coding, and judge whether it is necessary Perform inter-multicast network coding; the intermediate node exchanges received data information with its downstream nodes, judges the decodability of inter-multicast network coding, and selects appropriate multicast groups to perform multicast inter-network coding on their data.

根据上述发明构思，本发明采用下述技术方案： According to above-mentioned inventive concept, the present invention adopts following technical scheme:

一种应用于多源多汇网络的多组播间网络编码的控制方法，其特征在于具体步骤如下： A control method for multi-multicast network coding applied to a multi-source multi-sink network, characterized in that the specific steps are as follows:

步骤1：初始化，各个组播中的源节点采集数据，并将数据打包依次发送出去； Step 1: Initialize, the source nodes in each multicast collect data, and package the data and send them out sequentially;

步骤2：中间节点接收来自不同源节点的数据包； Step 2: The intermediate node receives data packets from different source nodes;

步骤3：中间节点对收到的数据包进行相关性判断：线性无关则转至步骤5； Step 3: The intermediate node makes a correlation judgment on the received data packets: if it is linearly independent, go to step 5;

步骤4：接收到数据包之间存在线性相关，表明收到的数据包进行过网络编码，则中间节点先进行网络编码解码得到线性无关的数据包； Step 4: There is a linear correlation between the received data packets, indicating that the received data packets have been network encoded, and the intermediate node first performs network encoding and decoding to obtain linearly independent data packets;

步骤5：接收到数据包之间线性无关，将其放入不相关数据队列； Step 5: The received data packets are linearly independent, and put them into the irrelevant data queue;

步骤6：中间节点计算单纯转发每个源节点数据得到的传输增益                                                

Figure 201110099631X100002DEST_PATH_IMAGE001
和发送组播间网络编码数据得到的传输增益
Figure 933104DEST_PATH_IMAGE002
； Step 6: The intermediate node calculates the transmission gain obtained by simply forwarding the data of each source node
Figure 201110099631X100002DEST_PATH_IMAGE001
and the transmission gain obtained by sending network-coded data between multicast
Figure 933104DEST_PATH_IMAGE002
;

步骤7：中间节点得到转发最佳源节点传输增益

Figure 201110099631X100002DEST_PATH_IMAGE003
和最佳组播间网络编码的传输增益
Figure 611603DEST_PATH_IMAGE004
； Step 7: The intermediate node obtains the best source node transmission gain for forwarding
Figure 201110099631X100002DEST_PATH_IMAGE003
and the transmission gain of optimal inter-multicast network coding
Figure 611603DEST_PATH_IMAGE004
;

步骤8：中间节点比较两者增益

Figure 972178DEST_PATH_IMAGE003
和的大小：转发传输增益大于等于编码传输增益时转至步骤9，否则转至步骤10 Step 8: The intermediate node compares the gains of the two
Figure 972178DEST_PATH_IMAGE003
and The size of : when the forwarding transmission gain is greater than or equal to the coding transmission gain, go to step 9, otherwise go to step 10

步骤9：中间节点不进行网络编码而是单纯转发源节点

Figure 201110099631X100002DEST_PATH_IMAGE005
的数据，则返回转至步骤2，如此循环上述步骤直到源节点中的数据发送完毕； Step 9: The intermediate node does not perform network coding but simply forwards the source node
Figure 201110099631X100002DEST_PATH_IMAGE005
data, return to step 2, and repeat the above steps until the data in the source node is sent;

步骤10：中间节点与其下游节点交换收到数据的信息； Step 10: The intermediate node exchanges the information of received data with its downstream node;

步骤11：判断下游节点能否收到用于组播间网络编码解码的数据：能收到用于解码的数据则转至步骤12，否则转至步骤9； Step 11: Determine whether the downstream node can receive the data for network encoding and decoding between multicast: if the data for decoding can be received, go to step 12, otherwise go to step 9;

步骤12：网络编码传输增益

Figure 978366DEST_PATH_IMAGE004
大于转发传输增益时，中间节点对于来自源节点和
Figure 541382DEST_PATH_IMAGE006
的数据进行组播间网络编码； Step 12: Network Coding Transfer Gain
Figure 978366DEST_PATH_IMAGE004
When is greater than the forwarding transmission gain, the intermediate node for the source node and
Figure 541382DEST_PATH_IMAGE006
The data in the multicast inter-network encoding;

步骤13：中间节点发送编码后的数据，则返回转至步骤2，如此循环上述步骤直到源节点中的数据发送完毕。 Step 13: The intermediate node sends the encoded data, then returns to step 2, and repeats the above steps until the data in the source node is sent.

本发明中的多源多汇网络的组播间网络编码控制方法与现有技术相比较，具有的优点： Compared with the prior art, the multi-source and multi-sink network multicast network coding control method in the present invention has the following advantages:

1，该方法中网络中间节点可以根据收到的来自多个组播组的数据，通过比较直接转发和进行组播间网络编码带来的传输增益，判断是否进行组播间网络编码，能最大化网络传输增益，提高网络的整体吞吐量；  1. In this method, the intermediate node of the network can judge whether to perform inter-multicast network coding by comparing the transmission gain brought by direct forwarding and inter-multicast network coding according to the data received from multiple multicast groups, and the maximum energy Maximize the network transmission gain and improve the overall throughput of the network;

2，该方法中网络中间节点通过与下游节点交换数据，可以选择最佳的组播组进行组播间网络编码，在提高网络吞吐量的同时，保证了组播间网络编码的解码性能； 2. In this method, the intermediate nodes of the network can select the best multicast group for inter-multicast network coding by exchanging data with downstream nodes, which improves the network throughput while ensuring the decoding performance of inter-multicast network coding;

3，该方法在网络链路带宽有限时，可以有效保证各个组播组之间的传输公平性。 3. This method can effectively guarantee the fairness of transmission between various multicast groups when the network link bandwidth is limited.

附图说明 Description of drawings

图1本发明应用于多源多汇网络的组播间网络编码控制方法的流程图。 FIG. 1 is a flow chart of the method for controlling network coding between multicasts applied to a multi-source and multi-sink network according to the present invention.

图2本发明的实施例中传输数据进入中间节点后的示意图。 Fig. 2 is a schematic diagram of transmission data entering an intermediate node in an embodiment of the present invention.

图3本发明的实施例中通信网络拓扑示意图。 Fig. 3 is a schematic diagram of a communication network topology in an embodiment of the present invention.

图4在固定链路带宽条件下，组播组

Figure 150218DEST_PATH_IMAGE008
和的传输速率可达区域的示意图。 Figure 4 Under the condition of fixed link bandwidth, the multicast group
Figure 150218DEST_PATH_IMAGE008
and Schematic diagram of the reachable area of the transmission rate.

图5在固定链路带宽条件下，采用本发明传输和传统存储转发方式传输性能比较的示意图。 Fig. 5 is a schematic diagram of a performance comparison between the transmission of the present invention and the traditional store-and-forward mode under the condition of fixed link bandwidth.

图6在随机链路带宽条件下，采用本发明传输和传统存储转发方式传输性能比较的示意图。 Fig. 6 is a schematic diagram of a performance comparison between the transmission of the present invention and the traditional store-and-forward mode under the condition of random link bandwidth.

具体实施方式 Detailed ways

下面结合附图和优选实施例对本发明的实施例作进一步详细的描述。 The embodiments of the present invention will be further described in detail below in conjunction with the accompanying drawings and preferred embodiments.

本实施例以图3所示网络拓扑为例进行说明。 This embodiment is described by taking the network topology shown in FIG. 3 as an example.

用

Figure 700541DEST_PATH_IMAGE010
表示多源多汇通信网络，其中
Figure 201110099631X100002DEST_PATH_IMAGE011
表示网络中的节点集合，
Figure 586589DEST_PATH_IMAGE012
表示网络中的链路集合。
Figure 201110099631X100002DEST_PATH_IMAGE013
和
Figure 928446DEST_PATH_IMAGE014
分别表示网络中的源节点集合和目的节点集合。每个源节点（
Figure 899945DEST_PATH_IMAGE016
）可以通过多条路径发送数据到相应的目的节点
Figure 201110099631X100002DEST_PATH_IMAGE017
。
Figure 988380DEST_PATH_IMAGE018
表示
Figure DEST_PATH_IMAGE019
中的一对源节点和目的节点，
Figure 728934DEST_PATH_IMAGE020
代表
Figure 867791DEST_PATH_IMAGE018
间的多条路径。网络中每条链路
Figure DEST_PATH_IMAGE021
均有一个带宽容量
Figure 825121DEST_PATH_IMAGE022
。 use
Figure 700541DEST_PATH_IMAGE010
Represents a multi-source and multi-sink communication network, where
Figure 201110099631X100002DEST_PATH_IMAGE011
Represents the set of nodes in the network,
Figure 586589DEST_PATH_IMAGE012
Represents a collection of links in the network.
Figure 201110099631X100002DEST_PATH_IMAGE013
and
Figure 928446DEST_PATH_IMAGE014
Respectively represent the source node set and the destination node set in the network. per source node (
Figure 899945DEST_PATH_IMAGE016
) can send data to the corresponding destination node through multiple paths
Figure 201110099631X100002DEST_PATH_IMAGE017
.
Figure 988380DEST_PATH_IMAGE018
express
Figure DEST_PATH_IMAGE019
A pair of source and destination nodes in ,
Figure 728934DEST_PATH_IMAGE020
represent
Figure 867791DEST_PATH_IMAGE018
multiple paths between. Each link in the network
Figure DEST_PATH_IMAGE021
have a bandwidth capacity
Figure 825121DEST_PATH_IMAGE022
.

Figure DEST_PATH_IMAGE023
表示为
Figure 950202DEST_PATH_IMAGE024
个不相关的随机过程，每个随机过程代表相应源节点采集发送的数据。
Figure DEST_PATH_IMAGE025
表示源节点
Figure 935476DEST_PATH_IMAGE026
分配给第
Figure DEST_PATH_IMAGE027
路径到目的节点的传输速率。网络中每个节点，均有
Figure 568156DEST_PATH_IMAGE030
和
Figure DEST_PATH_IMAGE031
两个集合分别表示节点
Figure 995464DEST_PATH_IMAGE032
的上游节点和下游节点。对源节点
Figure 835244DEST_PATH_IMAGE026
而言，
Figure DEST_PATH_IMAGE033
为空集。对目的节点而言，
Figure 483711DEST_PATH_IMAGE034
为空集。对网络中的链路
Figure DEST_PATH_IMAGE035
而言，
Figure 717640DEST_PATH_IMAGE036
表示源节点
Figure 287293DEST_PATH_IMAGE026
到目的节点
Figure 938854DEST_PATH_IMAGE028
的第
Figure 984170DEST_PATH_IMAGE027
路径占用链路
Figure 753281DEST_PATH_IMAGE035
的流量，表示链路
Figure 177440DEST_PATH_IMAGE035
上网络编码后数据的传输速率。
Figure DEST_PATH_IMAGE023
Expressed as
Figure 950202DEST_PATH_IMAGE024
Each random process represents the data collected and sent by the corresponding source node.
Figure DEST_PATH_IMAGE025
Indicates the source node
Figure 935476DEST_PATH_IMAGE026
assigned to the
Figure DEST_PATH_IMAGE027
path to destination node transmission rate. every node in the network , both have
Figure 568156DEST_PATH_IMAGE030
and
Figure DEST_PATH_IMAGE031
Two collections represent nodes respectively
Figure 995464DEST_PATH_IMAGE032
upstream and downstream nodes. source node
Figure 835244DEST_PATH_IMAGE026
in terms of
Figure DEST_PATH_IMAGE033
is an empty set. to the destination node in terms of
Figure 483711DEST_PATH_IMAGE034
is an empty set. link in the network
Figure DEST_PATH_IMAGE035
in terms of
Figure 717640DEST_PATH_IMAGE036
Indicates the source node
Figure 287293DEST_PATH_IMAGE026
to the destination node
Figure 938854DEST_PATH_IMAGE028
First
Figure 984170DEST_PATH_IMAGE027
path occupying link
Figure 753281DEST_PATH_IMAGE035
traffic, Indicates the link
Figure 177440DEST_PATH_IMAGE035
The transmission rate of data after encoding on the network.

多组播网络中，各源节点发送数据到相应目的节点时，存在大量共用的中间节点和链路。当中间节点收到多个组播的数据时，链路带宽被多个源节点共用，其有限的带宽使得链路变成瓶颈链路限制了源节点发送速率和网络的吞吐量。定义

Figure 478250DEST_PATH_IMAGE038
为链路
Figure DEST_PATH_IMAGE039
上，节点
Figure 620650DEST_PATH_IMAGE027
直接转发源节点
Figure 819550DEST_PATH_IMAGE015
获得的传输增益；
Figure 596751DEST_PATH_IMAGE040
为链路
Figure 855694DEST_PATH_IMAGE039
上，节点
Figure 485390DEST_PATH_IMAGE027
将对源节点
Figure 222401DEST_PATH_IMAGE015
和的数据网络编码后获得的传输增益，如下： In a multi-multicast network, when each source node sends data to a corresponding destination node, there are a large number of shared intermediate nodes and links. When the intermediate node receives multiple multicast data, the link bandwidth is shared by multiple source nodes, and its limited bandwidth makes the link a bottleneck link, which limits the source node sending rate and network throughput. definition
Figure 478250DEST_PATH_IMAGE038
for the link
Figure DEST_PATH_IMAGE039
on the node
Figure 620650DEST_PATH_IMAGE027
Forward directly to the source node
Figure 819550DEST_PATH_IMAGE015
The obtained transmission gain;
Figure 596751DEST_PATH_IMAGE040
for the link
Figure 855694DEST_PATH_IMAGE039
on the node
Figure 485390DEST_PATH_IMAGE027
will be to the source node
Figure 222401DEST_PATH_IMAGE015
and The transmission gain obtained after encoding the data network is as follows:

                                     

Figure DEST_PATH_IMAGE043
Figure DEST_PATH_IMAGE043

其中，

Figure 427828DEST_PATH_IMAGE044
是节点
Figure 403874DEST_PATH_IMAGE032
的下游节点，
Figure DEST_PATH_IMAGE045
代表节点
Figure 318479DEST_PATH_IMAGE032
的下游节点收到的用于组播间网络编码解码的数据流量。 in,
Figure 427828DEST_PATH_IMAGE044
is a node
Figure 403874DEST_PATH_IMAGE032
the downstream node of
Figure DEST_PATH_IMAGE045
representative node
Figure 318479DEST_PATH_IMAGE032
The data traffic received by the downstream node for multicast inter-network encoding and decoding.

中间节点通过计算单纯转发每个源节点数据得到的传输增益集合和发送多组播间网络编码数据得到的传输增益集合，可以得到最大的转发传输增益，其最佳的源节点记为，最大的多组播间网络编码的传输增益

Figure DEST_PATH_IMAGE047
，其最佳的源节点集合为
Figure 855027DEST_PATH_IMAGE048
。最大的转发传输增益
Figure 236461DEST_PATH_IMAGE003
和最大的多组播间网络编码的传输增益
Figure 452678DEST_PATH_IMAGE004
分别定义为： The intermediate node calculates the transmission gain set obtained by simply forwarding the data of each source node and the set of transmission gains obtained by sending multi-multicast inter-network coded data , the maximum forwarding transmission gain can be obtained , and its optimal source node is denoted as , the maximum transmission gain of multi-multicast network coding
Figure DEST_PATH_IMAGE047
, the optimal set of source nodes is
Figure 855027DEST_PATH_IMAGE048
. Maximum Forwarding Transmission Gain
Figure 236461DEST_PATH_IMAGE003
and the maximum transmission gain of network coding among multicast
Figure 452678DEST_PATH_IMAGE004
are defined as:

                      

Figure DEST_PATH_IMAGE049
                      
Figure DEST_PATH_IMAGE049

                     

Figure 709085DEST_PATH_IMAGE050
                     
Figure 709085DEST_PATH_IMAGE050

如图1、2所示，本应用于多源多汇网络的多组播间网络编码控制方法，其具体步骤如下: As shown in Figures 1 and 2, the multi-multicast inter-network coding control method applied to the multi-source multi-sink network, its specific steps are as follows:

步骤1：初始化，各个组播中的源节点采集数据，并将数据打包依次发送出去； Step 1: Initialize, the source nodes in each multicast collect data, and package the data and send them out sequentially;

步骤2：中间节点接收来自不同源节点的数据包； Step 2: The intermediate node receives data packets from different source nodes;

步骤3：中间节点对收到的数据包进行相关性判断：线性无关则转至步骤5； Step 3: The intermediate node makes a correlation judgment on the received data packets: if it is linearly independent, go to step 5;

步骤4：接收到数据包之间存在线性相关，表明收到的数据包进行过网络编码，则中间节点先进行网络编码解码得到线性无关的数据包； Step 4: There is a linear correlation between the received data packets, indicating that the received data packets have been network encoded, and the intermediate node first performs network encoding and decoding to obtain linearly independent data packets;

步骤5：接收到数据包之间线性无关，将其放入不相关数据队列； Step 5: The received data packets are linearly independent, and put them into the irrelevant data queue;

步骤6：中间节点计算单纯转发每个源节点数据得到的传输增益和发送组播间网络编码数据得到的传输增益

Figure 879483DEST_PATH_IMAGE002
； Step 6: The intermediate node calculates the transmission gain obtained by simply forwarding the data of each source node and the transmission gain obtained by sending network-coded data between multicast
Figure 879483DEST_PATH_IMAGE002
;

步骤7：中间节点得到转发最佳源节点传输增益

Figure 317418DEST_PATH_IMAGE003
和最佳组播间网络编码的传输增益
Figure 114866DEST_PATH_IMAGE004
； Step 7: The intermediate node obtains the best source node transmission gain for forwarding
Figure 317418DEST_PATH_IMAGE003
and the transmission gain of optimal inter-multicast network coding
Figure 114866DEST_PATH_IMAGE004
;

步骤8：中间节点比较两者增益和

Figure 435306DEST_PATH_IMAGE004
的大小：转发传输增益大于等于编码传输增益时转至步骤9，否则转至步骤10 Step 8: The intermediate node compares the gains of the two and
Figure 435306DEST_PATH_IMAGE004
The size of : when the forwarding transmission gain is greater than or equal to the coding transmission gain, go to step 9, otherwise go to step 10

步骤9：中间节点不进行网络编码而是单纯转发源节点

Figure 235903DEST_PATH_IMAGE005
的数据，则返回转至步骤2，如此循环上述步骤直到源节点中的数据发送完毕； Step 9: The intermediate node does not perform network coding but simply forwards the source node
Figure 235903DEST_PATH_IMAGE005
data, return to step 2, and repeat the above steps until the data in the source node is sent;

步骤10：中间节点与其下游节点交换收到数据的信息； Step 10: The intermediate node exchanges the information of received data with its downstream node;

步骤11：判断下游节点能否收到用于组播间网络编码解码的数据：能收到用于解码的数据则转至步骤12，否则转至步骤9； Step 11: Determine whether the downstream node can receive the data for network encoding and decoding between multicast: if the data for decoding can be received, go to step 12, otherwise go to step 9;

步骤12：网络编码传输增益

Figure 460211DEST_PATH_IMAGE004
大于转发传输增益时，中间节点对于来自源节点
Figure 161188DEST_PATH_IMAGE005
和
Figure 445539DEST_PATH_IMAGE006
的数据进行组播间网络编码； Step 12: Network Coding Transfer Gain
Figure 460211DEST_PATH_IMAGE004
When is greater than the forwarding transmission gain, the intermediate node for the source node
Figure 161188DEST_PATH_IMAGE005
and
Figure 445539DEST_PATH_IMAGE006
The data in the multicast inter-network encoding;

步骤13：中间节点发送编码后的数据，则返回转至步骤2，如此循环上述步骤直到源节点中的数据发送完毕。 Step 13: The intermediate node sends the encoded data, then returns to step 2, and repeats the above steps until the data in the source node is sent.

下面给出使用本发明的方法的数值仿真实验。假设网络中每条链路具有相同的固定带宽容量

Figure DEST_PATH_IMAGE051
，图4给出了组播组和
Figure DEST_PATH_IMAGE053
的传输速率可达区域。不采用组播间网络编码，源节点
Figure 872683DEST_PATH_IMAGE054
和
Figure DEST_PATH_IMAGE055
不能同时达到最大组播传输容量；采用组播间网络编码，组播组
Figure 54265DEST_PATH_IMAGE052
和
Figure 384884DEST_PATH_IMAGE053
可以同时达到最大组播传输容量，即
Figure 284707DEST_PATH_IMAGE056
和。 A numerical simulation experiment using the method of the present invention is given below. Assume that each link in the network has the same fixed bandwidth capacity
Figure DEST_PATH_IMAGE051
, Figure 4 shows the multicast group and
Figure DEST_PATH_IMAGE053
The transfer rate reachable area. Without multicast inter-network coding, the source node
Figure 872683DEST_PATH_IMAGE054
and
Figure DEST_PATH_IMAGE055
Cannot reach the maximum multicast transmission capacity at the same time; use inter-multicast network coding, multicast group
Figure 54265DEST_PATH_IMAGE052
and
Figure 384884DEST_PATH_IMAGE053
can reach the maximum multicast transmission capacity at the same time, that is,
Figure 284707DEST_PATH_IMAGE056
and .

图5中给出了三个组播组，采用组播间网络编码传输和传统存储转发方式传输时，三个组播组各自的吞吐量。由于组播组

Figure 224719DEST_PATH_IMAGE058
中，源节点
Figure DEST_PATH_IMAGE059
到目的节点
Figure 136174DEST_PATH_IMAGE060
的路径均要与另两个组播共用，不进行组播间网络编码，源节点
Figure 762327DEST_PATH_IMAGE059
不能将采集的数据发送到目的节点
Figure 526277DEST_PATH_IMAGE060
，组播的吞吐量为
Figure DEST_PATH_IMAGE061
。 Figure 5 shows the respective throughputs of the three multicast groups when the inter-multicast network coding transmission and the traditional store-and-forward transmission are adopted. multicast group
Figure 224719DEST_PATH_IMAGE058
, the source node
Figure DEST_PATH_IMAGE059
to the destination node
Figure 136174DEST_PATH_IMAGE060
The paths of the two multicasts must be shared with the other two multicasts, without network coding between multicasts, the source node
Figure 762327DEST_PATH_IMAGE059
The collected data cannot be sent to the destination node
Figure 526277DEST_PATH_IMAGE060
, the multicast throughput is
Figure DEST_PATH_IMAGE061
.

考虑网络中链路拥塞和突发错误，网络链路带宽为随机分布。图6中给出了在链路带宽随机下，采用组播间网络编码传输和传统存储转发方式传输时，三个组播组各自的吞吐量。采用组播间网络编码可以提高各个组播的吞吐量，从而提高了网络的整体吞吐量。 Considering link congestion and burst errors in the network, the network link bandwidth is randomly distributed. Figure 6 shows the respective throughputs of the three multicast groups when the link bandwidth is random, when network coding transmission between multicasts and traditional store-and-forward transmission are used. The use of inter-multicast network coding can improve the throughput of each multicast, thereby improving the overall throughput of the network.

为了计算组播间网络编码对整个网络吞吐量的提高量，定义网络吞吐量增益为： In order to calculate the improvement of the overall network throughput by network coding between multicast, the network throughput gain is defined as:

                 

Figure 505866DEST_PATH_IMAGE062
                 
Figure 505866DEST_PATH_IMAGE062

其中，

Figure DEST_PATH_IMAGE063
表示传统存储转发模式下，各个组播组吞吐量之和；
Figure 662041DEST_PATH_IMAGE064
表示组播组网络编码模式下，各个组播组吞吐量之和。表1给出了两种不同带宽下，组播组网络编码的网络吞吐量增益。 in,
Figure DEST_PATH_IMAGE063
Indicates the sum of the throughput of each multicast group in the traditional store-and-forward mode;
Figure 662041DEST_PATH_IMAGE064
Indicates the sum of the throughput of each multicast group in multicast group network coding mode. Table 1 shows the network throughput gain of multicast group network coding under two different bandwidths.

链路带宽(Mbps)Link Bandwidth (Mbps) 固定fixed 随机random 吞吐量增益 throughput gain 0.50.5 0.94400.9440

表1 不同链路带宽下本发明传输的网络吞吐量增益 The network throughput gain that the present invention transmits under the different link bandwidths of table 1

用最大最小公平性系数来衡量表示采用组播间网络编码后，各个组播组之间的公平性： The maximum and minimum fairness coefficients are used to measure the fairness between each multicast group after using inter-multicast network coding:

             最大最小公平性系数 

Figure DEST_PATH_IMAGE065
Max Min Fairness Coefficient
Figure DEST_PATH_IMAGE065

其中，为最小的组播吞吐量，为最大的组播吞吐量。表2给出了用三种不同传输方式（最短路径树方式、最大流传输方式和组播间网络编码方式）下的公平性系数。由于不采用组播网络编码，三个组播组中至少有一个组播组没有吞吐量，所以公平性系数为零。而采用组播组网络编码可以保证三个组播公平地传输数据，其公平性系数为

Figure 317199DEST_PATH_IMAGE008
。 in, is the minimum multicast throughput, for maximum multicast throughput. Table 2 shows the fairness coefficients under three different transmission modes (shortest path tree mode, maximum stream transmission mode and multicast network coding mode). Since no multicast network coding is used, at least one of the three multicast groups has no throughput, so the fairness coefficient is zero. However, the use of multicast group network coding can ensure that the three multicasts can transmit data fairly, and its fairness coefficient is
Figure 317199DEST_PATH_IMAGE008
.

公平性系数Fairness coefficient 最短路径方法shortest path method 最大流方法maximum flow method 组播间网络编码Inter-multicast network coding  the 00 00 11

表2 本发明与其他传输方式的公平性系数比较。 Table 2 Comparison of fairness coefficients between the present invention and other transmission methods.

Claims (2)

1. A multicast network coding control method applied to a multi-source multi-sink network is characterized by comprising the following specific steps:
step 1: initializing, wherein the source nodes in each multicast collect data and pack and send the data out in sequence;
step 2: the intermediate node receives data packets from different source nodes;
and step 3: the intermediate node judges the relevance of the received data packet: if the linearity is not related, the step 5 is carried out;
and 4, step 4: linear correlation exists between the received data packets, which indicates that the received data packets are subjected to network coding, and the intermediate node firstly carries out network coding and decoding to obtain the linearly-independent data packets;
and 5: linearly independent received data packets are put into an unrelated data queue;
step 6: the intermediate node calculates the transmission gain obtained by simply forwarding each source node dataAnd transmission gain by sending inter-multicast network coded data
Figure 657884DEST_PATH_IMAGE002
(ii) a The above-mentioned
Figure 96212DEST_PATH_IMAGE007
Is a link
Figure 466014DEST_PATH_IMAGE008
Upper, node
Figure 999020DEST_PATH_IMAGE009
Direct forwarding source node
Figure 796074DEST_PATH_IMAGE010
The obtained transmission gain;is a link
Figure 188190DEST_PATH_IMAGE008
Upper, node
Figure 198871DEST_PATH_IMAGE009
Will be to the source node
Figure 540728DEST_PATH_IMAGE010
And
Figure 636860DEST_PATH_IMAGE012
the transmission gain obtained after the data network coding is as follows:
Figure 354598DEST_PATH_IMAGE014
wherein, for the link in the network
Figure 493455DEST_PATH_IMAGE008
In the case of a non-woven fabric,
Figure 188135DEST_PATH_IMAGE015
representing a source node
Figure 703430DEST_PATH_IMAGE016
To the destination node
Figure 564069DEST_PATH_IMAGE017
To (1) a
Figure 873828DEST_PATH_IMAGE018
Path occupying link
Figure 678973DEST_PATH_IMAGE008
The flow rate of (a) to (b),
Figure 106281DEST_PATH_IMAGE019
representing nodes
Figure 946061DEST_PATH_IMAGE020
Is to be transmitted to the downstream node set of,represents
Figure 860107DEST_PATH_IMAGE022
A plurality of paths therebetween;
Figure 451626DEST_PATH_IMAGE023
is a nodeThe downstream node of (a) the downstream node,representative node
Figure 118425DEST_PATH_IMAGE020
The downstream node receives the data flow for network coding and decoding among the multicasts;
Figure 513634DEST_PATH_IMAGE025
indicating a linkThe transmission rate of the data after network coding;
and 7: intermediate node obtains transmission gain of optimal forwarding source node
Figure 680198DEST_PATH_IMAGE003
And transmission gain of optimal inter-multicast network coding
Figure 708197DEST_PATH_IMAGE004
；
And 8: the intermediate node compares the gains of both
Figure 266611DEST_PATH_IMAGE003
And
Figure 597229DEST_PATH_IMAGE004
the size of (2): if the transmission gain is greater than or equal to the coding transmission gain, the step 9 is proceeded, otherwise, the step is proceededStep 10
And step 9: the intermediate node does not perform network coding but simply forwards the source node
Figure 497052DEST_PATH_IMAGE005
Returning to the step 2, and repeating the steps until the data in the source node is sent;
step 10: the intermediate node exchanges the information of the received data with the downstream nodes thereof;
step 11: judging whether the downstream node can receive the data for the inter-multicast network coding and decoding: if the data for decoding can be received, the step 12 is carried out, otherwise, the step 9 is carried out;
step 12: network coding transmission gain
Figure 437064DEST_PATH_IMAGE004
When the forward transmission gain is larger, the intermediate node is opposite to the source node
Figure 473153DEST_PATH_IMAGE005
And
Figure 99306DEST_PATH_IMAGE006
performing inter-multicast network coding on the data;
step 13: and (4) the intermediate node sends the coded data, and then returns to the step 2, and the steps are circulated until the data in the source node is sent.
2. The inter-multicast network coding control method applied to the multi-source and multi-sink network according to claim 1, wherein the intermediate node calculates a transmission gain set obtained by simply forwarding data of each source node
Figure 399736DEST_PATH_IMAGE001
And transmitting the network coded data among the multiple multicasts to obtain the transmission gain set
Figure 666770DEST_PATH_IMAGE002
Maximum forwarding transmission gain can be obtained
Figure 242501DEST_PATH_IMAGE026
Its best source node is noted
Figure 911380DEST_PATH_IMAGE005
Maximum transmission gain for inter-multicast network coding
Figure 904743DEST_PATH_IMAGE027
The optimal source node set is(ii) a Maximum forward transmission gain
Figure 537030DEST_PATH_IMAGE003
And maximum transmission gain of network coding between multiple multicasts
Figure 434317DEST_PATH_IMAGE004
Are respectively defined as:
Figure 598582DEST_PATH_IMAGE029
Figure 840207DEST_PATH_IMAGE030
。
CN 201110099631 2011-04-21 2011-04-21 Inter-multicast network coding control method applied to multi-source multi-destination network Expired - Fee Related CN102148664B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN 201110099631 CN102148664B (en) 2011-04-21 2011-04-21 Inter-multicast network coding control method applied to multi-source multi-destination network

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN 201110099631 CN102148664B (en) 2011-04-21 2011-04-21 Inter-multicast network coding control method applied to multi-source multi-destination network

Publications (2)

Publication Number Publication Date
CN102148664A CN102148664A (en) 2011-08-10
CN102148664B true CN102148664B (en) 2013-06-05

Family

ID=44422689

Family Applications (1)

Application Number Title Priority Date Filing Date
CN 201110099631 Expired - Fee Related CN102148664B (en) 2011-04-21 2011-04-21 Inter-multicast network coding control method applied to multi-source multi-destination network

Country Status (1)

Country Link
CN (1) CN102148664B (en)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102572952B (en) * 2011-12-15 2014-04-09 北京航空航天大学 Network-coding-based fair service method for streaming media of wireless MESH network
CN103312443A (en) * 2012-03-16 2013-09-18 上海交通大学 Data transmission method
WO2014043908A1 (en) * 2012-09-24 2014-03-27 北京大学深圳研究生院 Method and apparatus for multi-source dynamic network coding
CN106332287B (en) * 2015-07-01 2022-03-18 西安中兴新软件有限责任公司 Data transmission method and communication node
CN107147470B (en) * 2016-03-01 2020-06-05 中兴通讯股份有限公司 Network coding forwarding rate on-line control method and device

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101325540A (en) * 2007-06-11 2008-12-17 华为技术有限公司 Method and device for improving multicast transmission efficiency based on random network coding
CN101945339A (en) * 2010-07-02 2011-01-12 哈尔滨工程大学 Cognitive radio self-organization network message multicast transmission method

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20040077379A1 (en) * 2002-06-27 2004-04-22 Martin Smith Wireless transmitter, transceiver and method
CN101286823A (en) * 2007-04-12 2008-10-15 中兴通讯股份有限公司 Data-transmission method and system for MIMO system
WO2009026695A1 (en) * 2007-08-27 2009-03-05 Nortel Networks Limited Communication system using mimo based network coding
CN101764675B (en) * 2009-12-23 2013-06-19 北京邮电大学 Coding resource adaptive scheduling algorithm in distributed network

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101325540A (en) * 2007-06-11 2008-12-17 华为技术有限公司 Method and device for improving multicast transmission efficiency based on random network coding
CN101945339A (en) * 2010-07-02 2011-01-12 哈尔滨工程大学 Cognitive radio self-organization network message multicast transmission method

Also Published As

Publication number Publication date
CN102148664A (en) 2011-08-10

Similar Documents

Publication Publication Date Title
CN102355670B (en) A multi-channel wireless mesh network channel allocation method
CN104754688B (en) Method for routing for the Wireless Mesh quantum communication network based on Entangled State
CN106254254B (en) An On-Chip Network Communication Method Based on Mesh Topology
CN103428803B (en) A kind of chance method for routing of combination machine meeting network code
CN102148664B (en) Inter-multicast network coding control method applied to multi-source multi-destination network
CN101267450A (en) Application Layer Multicast Routing Method for Distributed Networks Based on Network Coding
WO2013152589A1 (en) Lacp negotiation processing method, relay node and system
CN101965031B (en) Maximum probability-based cognitive radio multi-path multicast routing method
WO2013174024A1 (en) Seamless redundancy realization method for ring network
CN104243323A (en) Exchange network multicast route method and system
CN102055675A (en) Multipath routing distribution method based on load equilibrium
CN105163354B (en) A Data Stream Delay Guarantee Strategy Using Pairwise Inter-Stream Network Coding Opportunities
CN107682434A (en) A kind of underwater sensor network framework and its implementation
CN103179517A (en) A wireless multicast method for data center
CN104506272B (en) Network code intercepting method in " X " type wireless network topology structure
CN101764675A (en) Coding resource adaptive scheduling algorithm in distributed network
CN103200105B (en) A kind of path selection system of the QKD network based on light path switching and route selection method
CN102223311A (en) Queue scheduling method and device
CN105187326B (en) A kind of network code in double bounce wireless network topology structure intercepts management method
CN102299771A (en) Network coding control method for multi-hop multi-data-stream network
CN109982405B (en) Opportunistic routing mode of inter-session network coding based on multiple data streams
Xing et al. Device-aware routing and scheduling in multi-hop Device-to-Device networks
CN107360595B (en) An implementation method of multi-gateway WMN load balancing based on dynamic clustering under IEEE802.11s
CN103596221B (en) A kind of data transmission method moving Ad Hoc network and system
CN104704760B (en) The method and device of multiple source dynamic network coding

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C14 Grant of patent or utility model
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20130605