CN108847992A - A kind of video machine meeting transmission route algorithm based on multi-user Cooperation game - Google Patents

Abstract

A video opportunistic transmission routing algorithm based on multi-user cooperative game. Firstly, the two factors of video data itself and transmission network are integrated to establish the edge quality gain model of video data packets; secondly, multiple nodes that meet are regarded as a connected network. And the data exchange process is modeled as a multi-user cooperative game process; finally, based on the optimal Nash solution represented by the geometric space, a decision is made on the replication or forwarding of each video data packet. This algorithm guarantees that under the condition of optimal video transmission quality, the number of video data packet backups in the network is the least, and the simulation results based on synthetic data sets and real data sets show that the video transmission quality of the present invention is 1~2dB higher than similar algorithms , but the average maximum packet backup number is only about 25% of similar algorithms; this algorithm can not only maximize the video transmission quality, but also reduce the average maximum packet backup number, thereby minimizing the network transmission overhead.

Description

A Video Chance Transmission Routing Algorithm Based on Multi-user Cooperative Game

technical field

The invention relates to the technical field of wireless communication, in particular to a video opportunistic transmission routing algorithm based on multi-user cooperative game.

Background technique

The rapid development of microelectronics and wireless communication technology has enabled the rapid popularization of smart terminal devices in the past decade, and various sensor devices embedded in them have also given people the ability to perceive the external environment through video. At the same time, benefiting from the rapid development of the mobile Internet, video data can be shared among users anytime and anywhere, and various applications and services can be provided to users. However, the proliferation of mobile devices has brought about an explosive growth in mobile data traffic, of which video data accounts for a large proportion. According to Cisco's forecast, this value will reach 84% by the end of 2018. However, mobile data traffic is mainly transmitted through mobile cellular networks (3G/4G, LTE). Although mobile communication technology has developed rapidly in recent years, it still cannot meet the demands of massive data streams on the network in terms of transmission rate and network capacity. demand.

The mobile data stream that needs to be transmitted through the mobile cellular network is transmitted and distributed through other auxiliary networks and means, which is called mobile data offloading. Currently, mobile data offloading is considered to be the most effective way to solve the above dilemma. Wi-Fi hotspots are often used as an auxiliary means of mobile cellular networks for data transmission, but due to factors such as deployment costs and transmission distances, it is difficult to form a full-coverage wireless network within a wide area to provide data transmission services . Therefore, how to perform convenient and efficient mobile data offloading, especially video data offloading, has become a problem that is widely concerned by the academic and industrial circles.

There are already many algorithms and mechanisms for the transmission of general data in opportunistic networks, but none of them can be directly applied to the opportunistic transmission of video data for the following reasons. First of all, the nature of video data is very different from general data, and routing algorithms should fully consider its uniqueness, such as persistence and local correlation, when designing routing algorithms; secondly, there are large differences in the performance goals of algorithm design. Transmission mainly regards the delivery rate and transmission delay as performance measurement standards, while video data transmission uses the delivery quality of video data as the measurement index for routing algorithm design, which includes not only transmission delay, but also the reconstruction quality of video data; Finally, the existing opportunistic routing algorithm mainly considers the data transmission between two nodes, while it is normal for multiple nodes to meet in the urban environment, considering the data exchange between multiple nodes can provide more improvement and optimization for data transmission performance space.

To sum up, the increasing popularity of video data transmission among mobile users has made the problem of explosive traffic growth on traditional wireless communication networks more and more serious, and data opportunistic transmission based on D2D communication is considered to be an effective method to realize data offloading. However, data transmission in mobile opportunistic networks is mainly realized by data replication and opportunistic forwarding. In order to obtain a higher delivery rate and lower delivery delay, data replication is often overused. Redundant data packets will not only consume a lot of equipment and network resources, but also increase the transmission load of the network and reduce network performance. . For video data transmission, due to its strong persistence and data volume much higher than that of general scalar data, this problem will be more prominent.

Contents of the invention

In order to solve the deficiencies in the prior art, the present invention provides a video opportunity transmission routing algorithm based on multi-user cooperative game, which realizes the optimization of video transmission quality and transmission overhead, not only can maximize video transmission quality, but also can reduce data The average maximum backup number of packets, so that the transmission overhead of the network is minimized.

In order to achieve the above object, the specific scheme adopted by the present invention is: a video opportunity transmission routing algorithm based on multi-user cooperative game, at first integrating the two factors of video data itself and transmission network, and establishing the edge quality gain model of video data packets; secondly The multiple nodes that meet are regarded as a connected network, and the data exchange process is modeled as a multi-user cooperative game process; finally, based on the optimal Nash solution represented by the geometric space, the replication or Forward for decision making.

As mentioned above, a video opportunity transmission routing algorithm based on multi-user cooperative game, the algorithm specifically includes the following steps:

Step 1, integrate two factors of video data itself and transmission network, establish the edge quality gain model of video data packet, specifically comprise the following steps:

Step 1.1. Consider the frame structure of video data: each video segment is divided into multiple GoPs, and the GoPs belonging to the same video segment all have the same frame structure. When video data is transmitted in the network, each frame will be divided into multiple GoPs. A video data packet, a plurality of video data packets include three types of I, B and P;

Step 1.2. Quantify the delivery quality of the video through the frame delivery rate: calculate the average delivery probability of different types of video data packets at the same time;

Step 1.3, calculating the edge mass gain by discretizing the partial differential equation;

Step 2. Treat the multiple nodes that meet as a connected network, and model the data exchange process as a multi-user cooperative game process;

Step 3. Calculate the approximate optimal Nash solution of the game based on the geometric space representation method. In step 2, each meeting node copies or forwards data according to the optimal solution, specifically including the following steps:

Step 3.1, the optimal solution of multiplayer cooperative game satisfies the following formula:

Among them, F _i ^* represents the optimal income of user i in the equilibrium state; F _i ⁰ represents the income of user i in the non-cooperative state;

Indicates the Nash product;

Step 3.2, construct utility function;

Step 3.3, calculate the approximate optimal Nash solution of the game based on the geometric space representation method.

As a preferred solution, in step 1.1, video data packets from different frames have different importance, wherein, the I frame is a reference frame, which can be independently reconstructed after the video data packet is successfully delivered; the P frame is a forward prediction frame , its reconstruction depends on the successful recovery of the successfully received video data packet and its previous I or P frame; the B frame is a bidirectional predictive frame, and its reconstruction depends on the successful recovery of the previous and subsequent two video frames.

As a preferred solution, the frame delivery rate in step 1.2 is the ratio between the number of successfully reconstructed video frames at the destination node and the number of all delivered video frames for a video segment delivered in the network.

As a preferred solution, in step 1.2, the specific calculation process of the average delivery probability of the I type video packet at time t is as follows:

(1) For a video segment, NG represents the number of GoPs, NT represents the total number of video frames; MI, MP and MB represent the number of video packets that each I, P and B frame is divided into equally; RI , RP and RB respectively represent the successful delivery probability of three types of video data packets of I, P and B; NI, NP and NB respectively represent the expected value of successfully delivered I, P and B frames; then there is the following formula:

FDR = (N _I +N _P +N _B )/N _T ;

(2) When a video segment is divided and transmitted in the network, the parameters NG, MI, MP and MB related to it are known, so the frame delivery rate is a function of RI, RP and RB as variables ,which is:

FDR = f(R _I , R _P , R _B );

(3) In the video transmission process, it is assumed that the number of different I-type video packets in the network at time t is KI(t), and has the same TTL (Time-to-Live) value; for any I-type The video data packet i, TI, i(t) represents the lifetime of the data packet that has been consumed at time t, MI, i(TI, i(t)) represents the number of nodes that have received the video data packet, NI,i(TI,i(t)) indicates the number of nodes still carrying the video data packet, RI,i(t) indicates the remaining lifetime of the video data packet; in addition, NS indicates all nodes participating in video transmission number; then, the following relationship holds:

(4) The contact time interval between nodes obeys the exponential distribution of λ, so the probability that the video data packet i cannot be successfully delivered is equal to the time when any backup data packet meets the destination node next time is greater than RI,i(t) The probability of , that is, exp(-λRI,i(t)); therefore, using PI,i to represent the probability that type I video packet i can be successfully delivered within its lifetime, then:

(5) To sum up, the average delivery probability of type I packets at time t is:

As a preferred solution, the specific calculation process of the average delivery probability of P and B type video data packets at time t is the same as that of I type video data packets.

As a preferred solution, in step 1.3, the specific process of discretizing the edge mass gain through partial differential equations is as follows:

S1. For any video data packet i of type I, its edge quality gain at time t is calculated as follows:

S2, the edge quality gain MQGP,i and MQGB,i of video data packet i of type P and video data packet i of type B are calculated as follows respectively:

Among them, RI, RP, and RB represent the successful delivery probability of three types of video data packets of I, P, and B respectively; NI, NP, and NB represent the expected values of successfully delivered I, P, and B frames, respectively.

As a preferred solution, in step 3.2, the constructed utility function is as follows:

Among them, N represents the number of nodes encountered, M represents the number of different video packets carried by the node, and V represents the number of video segments transmitted at the same time. Since any video segment v has its own destination node, Therefore pn,v represents the contact probability between node n and the destination node of video segment v, and MQGn,v,m represents the edge quality gain of video packet m carried by node n and belonging to video segment v.

As a preferred solution, in step 3.3, the specific process of calculating the approximate optimal Nash solution of the game based on the geometric space representation method is as follows:

T1. For video data transmission, use pn, vMQGn, v, m to represent the utility value of video data packet m relative to node n, and calculate the utility distance dn between them, as follows:

T2. For video data transmission, the utility distance product φn,m of the normalized video data packet m relative to the gaming user n is specifically calculated as follows:

T3. For a given video data packet, corresponding to all game users having the same utility distance product, the equilibrium condition is expressed as follows:

Wherein, un is used to determine the threshold condition of video data packet distribution termination;

T4. Select the first K video data packets from the list Ln corresponding to mobile node n and distribute them to n, so that the sum of the utility distances of these K video data packets to node n reaches a critical value un, that is, K satisfies the following conditions :

Beneficial effects: (1) The present invention provides a video opportunity transmission routing algorithm based on multi-user cooperative game, which ensures that the number of backups of video data packets in the network is the least when the quality of video transmission is optimal. The simulation results of the data set and the real data set show that the video transmission quality of the present invention is 1-2dB higher than similar algorithms, but the average maximum data packet backup number is only about 25% of similar algorithms;

(2) The present invention provides a video opportunity transmission routing algorithm based on multi-user cooperative game, which can not only maximize the quality of video transmission, but also reduce the average maximum backup number of data packets, thereby minimizing the transmission overhead of the network;

(3) The present invention provides a video opportunistic transmission routing algorithm based on multi-user cooperative game, which fully considers the characteristics of the video data itself and the opportunistic network itself, and establishes a video data reconstruction quality model; based on the video data reconstruction quality model, a A new metric, namely edge quality gain, quantifies the importance of each video data packet; then based on the above model and metrics, with the goal of optimizing video transmission quality and minimizing video transmission overhead, a video transmission-oriented opportunistic routing protocol.

Description of drawings

Fig. 1 is a system model diagram of video data unloading of the present invention;

Fig. 2 is a schematic diagram of the frame structure of the GoP of the present invention.

Detailed ways

The present invention will be described in detail below in conjunction with specific embodiments. This embodiment provides detailed implementation methods and specific operation processes on the premise of the technical solution of the present invention.

System model: Please refer to Figure 1. In urban areas, all mobile users and vehicles equipped with mobile intelligent terminals can be regarded as mobile nodes; and from the perspective of the network, these nodes form a conscious or unconscious way Mobile Opportunity Network. Video data is transmitted through D2D through opportunistic contact between nodes. Therefore, video data offloading is actually the process of transmitting video data through mobile opportunistic networks. As shown in Figure 1, Figure 1 shows the system model of video data offloading, which mainly includes two parts, namely the platform side and the user side. On the platform side, the management platform can be regarded as a server deployed in the traditional network, which is mainly responsible for the recruitment and management of participating users, video data request and response management, video data packet diffusion information collection, etc., and can communicate with mobile users through mobile Cellular network or Wi-Fi network for communication and interaction; on the user side, all users are performing uncontrolled autonomous movement, during which data exchange can be performed directly through D2D, and each user can also communicate through 3G/4G, Wi-Fi -Fi interface for information interaction with the platform. When a user participates in or quits a video offloading task, it must notify the management platform in time, so that the latter can grasp the exact information of the participating users in real time; at the same time, when the carried data changes, each user must also report the change in the form of a data packet to the management platform. Since the user and data packet information can be used to calculate the utility value and user income, thereby assisting the delivery of video data, the present invention refers to these data as control information. During video data transmission, only control information can be transmitted over traditional wireless networks. In Figure 1, ①-⑤ show the video data unloading process: if a user wants to obtain a video segment, he will first send a request message to the management platform (①②); after receiving the request message, the platform will send it to The user who has stored the video (③④); eventually, the latter will send the requested video data to the requester through D2D.

Problem Modeling: The essence of video data offloading is data transmission through mobile opportunistic networks, so that mobile data traffic bypasses traditional wireless cellular networks. Therefore, the fundamental problem to be solved is to design an efficient video opportunistic routing algorithm that can meet the following requirements : 1) Maximize the quality of video reconstruction; 2) Minimize the cost of video transmission; 3) Applicable to scenarios where multiple users meet. In order to model this problem, the present invention provides the following definition: edge quality gain, that is, for a video data packet delivered in the network, if it is successfully received by the destination node, it will make a certain contribution to the video reconstruction quality . The present invention refers to this contribution as the expected marginal quality gain of the video data packet, expressed by MQG (Marginal Quality Gain).

Assuming that N nodes meet at time t, these nodes carry M different video data packets in total, and these video data packets belong to X different video segments respectively. If the binary number δ is used to mark whether a node carries a data packet, then for any node n(n∈{1,2,…,N}), the vector βn=(δn,1,δn,2,…,δn ,M) indicates the video data packets it carries, and the vector β=(β1,β2,...,βN) indicates the distribution of M video data packets on the N nodes. The goal of the present invention is to maximize the reconstruction quality of video data while reducing the cost of video transmission as much as possible. Therefore, the problem to be solved can be described as maximizing the contribution of each node to video reconstruction quality when nodes meet and reducing as much as possible The number of times the video packet was copied. The problem is modeled as follows:

Among them, MQG'n,m and MQGn,m respectively represent the quality edge gain of the video data packet m carried by node n before and after data transmission; δ'n,m and δn,m respectively represent whether node n carries data packet m before and after data exchange ; β* represents the optimal vector β, which belongs to the vector space (β1×β2×…×βN). In this way, according to the optimal distribution vector β*, the nodes that meet not only know whether the data packet should be forwarded or copied, but also know the object to which the data packet should be forwarded or copied.

The present invention provides a video opportunity transmission routing algorithm based on multi-user cooperative game, specifically as follows:

First, the video data packet edge quality gain is modeled by integrating the two factors of the video data itself and the transmission network.

When the video is transmitted in the network, it is first divided into many video data packets; when enough video data packets are received by the destination node, the video data can be reconstructed. In the process of video data transmission, participating nodes will copy or forward the data packets they carry, but it is very difficult to quantify the contribution of nodes forwarding or copying a video data packet to the video reconstruction quality. The reason mainly comes from the video data itself and the transmission network. The present invention synthesizes two factors of video data itself and transmission network, and the edge quality gain of video data packet is modeled, specifically comprises the following steps: Step 1.1, the frame structure of video data: each video segment is equally divided into a plurality of GoP (Group of Pictures), GoPs belonging to the same video segment all have the same frame structure. Figure 2 shows a schematic diagram of a GoP frame structure, which consists of a fixed number of I frames, P frames, and B frames in a fixed order. The number of frames can be any integer in principle. For the convenience of description, the present invention takes 9 as an example, and each frame is marked as I1, B1, B2, P1, B3, B4, P2, B5, and B6 respectively. When video data is transmitted in the network, each frame will be divided into multiple video data packets, and the multiple video data packets include three types: I, B, and P. Due to the application of compression technology, there is a strong correlation between frames in the same GoP, which makes different frames have different importance to the reconstruction of video data, so that the video packets from different frames also have different importance accordingly. sex. Specifically, the I frame is a reference frame, which can be independently reconstructed after its data packet is successfully delivered; the P frame is a forward prediction frame, and its reconstruction not only needs to successfully receive its data packet, but also depends on its previous I or P The successful restoration of the frame; the B frame is a bidirectional prediction frame, and its reconstruction depends on the successful restoration of the two video frames before and after. As shown in Figure 2, the reconstruction of P2 depends on P1, while the reconstruction of B2 depends on I1 and P1.

Step 1.2. Quantify the delivery quality of the video through the frame delivery rate: calculate the average delivery probability of different types of video data packets at the same time;

(1) Every time the node forwards and replicates the video data packet, it will produce a certain gain to the video reconstruction quality. To quantify this gain, an appropriate metric must first be chosen. PSRN is often used to quantify video quality, but it cannot be applied to mobile opportunistic networks because the frame cannot be reconstructed when the video data packets belonging to a frame have not been fully received, so its PSNR cannot be calculated. Therefore, the present invention proposes a new metric, that is, the frame delivery rate, which quantifies the delivery quality of the video; frame delivery rate: for a video segment delivered in the network, its frame delivery rate is defined as a successful The ratio between the number of reconstructed video frames and the number of all video frames delivered is represented by variable FDR (Frame Delivery Rate);

Assume that for a video segment, NG represents the number of GoPs, NT represents the total number of video frames; MI, MP, and MB represent the number of video packets that each I, P, and B frame can be equally divided into; RI, RP, and RB represent the successful delivery probability of three types of video data packets, I, P, and B respectively; NI, NP, and NB represent the expected values of successfully delivered I, P, and B frames, respectively. Then, the following formula can be obtained:

FDR = (N _I +N _P +N _B )/N _T ;

(2) When a video segment is divided and transmitted in the network, the parameters NG, MI, MP and MB related to it are known, so the frame delivery rate is a function of RI, RP and RB as variables ,which is:

FDR = f(R _I , R _P , R _B );

(3) In the video transmission process, it is assumed that the number of different I-type video packets in the network at time t is KI(t), and has the same TTL (Time-to-Live) value; for any I-type The video data packet i, TI, i(t) represents the lifetime of the data packet that has been consumed at time t, MI, i(TI, i(t)) represents the number of nodes that have received the video data packet, NI,i(TI,i(t)) indicates the number of nodes still carrying the video data packet, RI,i(t) indicates the remaining lifetime of the video data packet; in addition, NS indicates all nodes participating in video transmission number; then, the following relationship holds:

(4) Since the contact time interval between nodes obeys the exponential distribution of λ, the probability that the video data packet i cannot be successfully delivered is equal to the time when any backup data packet meets the destination node next time is greater than RI,i(t ), that is, exp(-λRI,i(t)); therefore, using PI,i to represent the probability that type I video packet i can be successfully delivered within its lifetime, then:

(5) To sum up, the average delivery probability of type I packets at time t is:

Similarly, the specific calculation process of the average delivery probability of P and B type video data packets at time t is the same as that of I type video data packets.

Step 1.3, calculate the edge quality gain through the discretization of the partial differential equation; during the video transmission process, any video data packet that is not successfully received has an expected gain to the video reconstruction quality. According to the formula FDR＝f(R _I , R _P , R _B ) and the formula It can be seen that the frame delivery rate of a video is actually a function of the backup number of its video data packets. For any video data packet, the value of this function will change when the number of backups increases or decreases. In the present invention, the size of the change in the frame delivery rate caused by the unit change of the backup number of a certain video data packet is called the marginal gain of the video data packet relative to the video reconstruction quality. The edge gain can be calculated by discretizing the partial differential equation as follows:

S1. For any video data packet i of type I, its edge quality gain at time t is calculated as follows:

S2, the edge quality gain MQGP,i and MQGB,i of video data packet i of type P and video data packet i of type B are calculated as follows respectively:

Among them, RI, RP, and RB represent the successful delivery probability of three types of video data packets of I, P, and B respectively; NI, NP, and NB represent the expected values of successfully delivered I, P, and B frames, respectively.

2. Treat the multiple nodes that meet as a connected network, and model the data exchange process as a multi-user cooperative game process;

3. The approximate optimal Nash solution of the game is calculated based on the geometric space representation method, and each meeting node performs data replication or forwarding respectively according to the optimal solution. The original intention of the routing algorithm design of the present invention is to maximize the transmission quality of video data , while reducing the cost of video data transmission as much as possible. In order to achieve this purpose, the present invention models video transmission among multiple users as a multi-user cooperative game, and uses Nash Pareto optimization theory to give an optimal solution.

Multiplayer cooperative game is a non-zero-sum game model, each player participating in the game is rational and selfish, and hopes to achieve a win-win goal through competition and compromise. All users participating in the game are represented by the set Q={1,2,...,n}; all possible strategies adopted by user i form a strategy space, represented by si, then S=s1×s2×...×sn Represents the set of policies for the federation. During the game, any user i has a utility function Fi, and its utility value will change with different strategies. For a multi-person cooperative game, if there is no other joint strategy besides the current joint strategy set that can make each user obtain a higher utility value at the same time, then the game is considered to have reached equilibrium.

Step 3.1. The optimal solution of multi-person cooperative game can satisfy the following four characteristics: invariance, symmetry, independence and Pareto optimality, etc. The optimal solution of multi-person cooperative game satisfies the following formula:

Among them, Fi* represents the optimal income of user i in the equilibrium state; Fi0 represents the income of user i in the non-cooperative state; Denotes the Nash product.

Step 3.2, constructing a utility function; when multiple mobile nodes meet at time t, they form a fully connected subnetwork, and the nodes that meet can use this contact opportunity to transmit video data. The present invention uses N to represent the number of nodes that meet, M to represent the number of different video data packets carried by them, and V to represent the number of video segments transmitted at the same time. Because, for any video segment v, it has its own destination node, the present invention uses pn, v to represent the contact probability between node n and the destination node of video segment v, and uses MQGn, v, m to represent the , the edge quality gain of video packet m belonging to video segment v. Then the contribution of mobile node n to the delivery quality can be quantified by the sum of the edge quality gains of all the video data packets it carries. Therefore, the utility function of node n is designed as follows:

When the nodes meet, each node hopes to increase its contribution to the video reconstruction quality as much as possible through this data exchange, that is, max(F _n -F _n '), where F _n ' represents the node n before contact utility value. Therefore, each node will not directly forward the video data packet for free; similarly, the duplication of the video data packet will increase the number of backups, thereby reducing the edge quality gain of the data packet to the video reconstruction quality, so the mobile node also Unwilling to make free copies of the video data packets it carries. Therefore, it can be said that each node has conflicting interests from its own point of view. On the other hand, all nodes involved in video transmission hope to complete the task of video transmission, so they all have a strong willingness to cooperate. Based on this, the present invention models the video data transmission between multiple nodes as a multi-node cooperative game. According to the concept of edge quality gain, the solution that maximizes the Nash product is the Nash equilibrium solution, which can make the multiple nodes that meet each other obtain the maximum benefit. Therefore, the following formula is obtained:

Among them, F _n and F _n 'represent the edge quality gain of data packets carried by node n before and after data exchange; in this way, if β ^* can be found, then the forwarding and copying of video data packets by each meeting node can be based on β ^* To achieve the purpose of algorithm design. The solution of multiplayer cooperative game can approach the optimal solution through infinite bargaining, but the computational complexity will increase exponentially with the increase of the number M of data packets. In order to solve this problem, the present invention proposes to use a geometric space representation algorithm to find the optimal solution.

Step 3.3, calculate the approximate optimal Nash solution of the game based on the geometric space representation method. The specific process of calculating the approximate optimal Nash solution of the game based on the geometric space representation method is as follows:

T1. For video data transmission, use pn, vMQGn, v, m to represent the utility value of video data packet m relative to node n, and calculate the utility distance dn between them, as follows:

T2. For video data transmission, the utility distance product φn,m of the normalized video data packet m relative to the gaming user n is specifically calculated as follows:

T3. For a given video data packet, corresponding to all game users having the same utility distance product, the equilibrium condition is expressed as follows:

Wherein, un is used to determine the threshold condition of video data packet distribution termination;

T4. Select the first K video data packets from the list Ln corresponding to mobile node n and distribute them to n, so that the sum of the utility distances of these K video data packets to node n reaches a critical value un, that is, K satisfies the following conditions :

Mobile data offloading is a research topic that has attracted much attention in recent years, and data opportunity transmission based on D2D communication is considered to be an ideal method to solve this problem. The invention proposes a video opportunistic transmission routing algorithm based on multi-user cooperative game, which is used to solve the problem of efficient transmission of video data in mobile opportunistic networks. The algorithm models the data transmission between multiple users as a multi-user cooperative game, and uses the Nash optimal solution to guide the replication and forwarding of video data packets, so as to maximize the quality of video transmission and minimize the overhead of video transmission. The performance of the algorithm is verified on both synthetic and real datasets.

The above descriptions are only preferred embodiments of the present invention, and do not limit the present invention in any form. Although the present invention has been described above with preferred embodiments, it is not intended to limit the present invention. Anyone familiar with this field Those skilled in the art, without departing from the scope of the technical solution of the present invention, may use the above-mentioned technical content to make some changes or modifications that are equivalent embodiments of equivalent changes, but if they do not depart from the content of the technical solution of the present invention, according to this Technical Essence of the Invention Any simple modifications, equivalent changes and modifications made to the above embodiments still fall within the scope of the technical solutions of the present invention.

Claims (9)

1. a kind of video machine meeting transmission route algorithm based on multi-user Cooperation game, it is characterised in that：Comprehensive video number first According to itself and two factors of transmission network, the edge quality gain model of video data packet is established；Secondly the multiple sections to meet Point regards the network of a connection as, and data exchange process therebetween is modeled as the process of a multi-user Cooperation game；Most The optimal Nash solution indicated afterwards based on geometric space carries out decision to the duplication or forwarding of each video data packet.

2. a kind of video machine meeting transmission route algorithm based on multi-user Cooperation game as described in claim 1, feature exist In：The algorithm specifically comprises the following steps：

Two factors of step 1, video data synthesis itself and transmission network, establish the edge quality gain mould of video data packet Type specifically comprises the following steps：

Step 1.1, the frame structure for considering video data：Each video-frequency band is divided into multiple GoP, belongs to the GoP of same video-frequency band Frame structure all having the same, when video data transmits in a network, each frame can be divided into multiple video data packets, Multiple video data packets include I, B and P three types；

Step 1.2 is quantified by delivery quality of the frame delivery ratio to video：Different types of video data packet is calculated same The average delivery probability at one moment；

Step 1.3 calculates edge quality gain by partial differential equation discretization；

Step 2, the network for the multiple nodes to meet being regarded as a connection, and data exchange process therebetween is modeled as one The process of a multi-user Cooperation game；

Step 3, the near-optimization Nash solution that the game is calculated based on geometric space representation method, respectively meet in step 2 node The duplication or forwarding for carrying out data respectively according to the optimal solution, specifically comprise the following steps：

Step 3.1, the optimal solution of multiple person cooperational game meet following formula：

Wherein, F_i ^*Indicate optimal income of the user i under equilibrium state；F_i ⁰Indicate the income of the user i under non-cooperating state；Assorted product is received in expression；

Step 3.2, building utility function；

Step 3.3, the near-optimization Nash solution that the game is calculated based on geometric space representation method.

3. a kind of video machine meeting transmission route algorithm based on multi-user Cooperation game as claimed in claim 2, feature exist In：In step 1.1, the video data packet from different frame has different importance, wherein I frame is reference frame, works as video counts It can independently be rebuild later according to coating successful delivery；P frame is forward predicted frame, is rebuild dependent on the video data being properly received The successful recovery of packet and its previous I or P frame；B frame is bi-directional predicted frames, is rebuild extensive dependent on the success of former and later two video frames It is multiple.

4. a kind of video machine meeting transmission route algorithm based on multi-user Cooperation game as claimed in claim 2, feature exist In：Frame delivery ratio described in step 1.2 is the video-frequency band delivered in a network for one in destination node successful reconstitution The number of video frame and all video frame quantity of delivery between ratio.

5. a kind of video machine meeting transmission route algorithm based on multi-user Cooperation game as claimed in claim 2, feature exist In：In step 1.2, the video data packet of I type is as follows in the specific calculating process of the average delivery probability of t moment：

(1) for a video-frequency band, N_GIndicate GoP number, N_TIndicate total video frame number；M_I、M_PAnd M_BIt respectively indicates each I, P and B frame is averaged the video data packet number being divided into；R_I、R_PAnd R_BRespectively indicate the video data of I, P and B three types The successful delivery probability of packet；N_I、N_PAnd N_BRespectively indicate the desired value for I, P and B frame successfully delivered；Then there is following formula：

FDR=(N_I+N_P+N_B)/N_T；

(2) when a video-frequency band is divided and is transmitted in a network, relative parameter N_G、M_I、M_PAnd M_BIt is all Know, therefore, frame delivery ratio is with R_I、R_P、R_BFor the function of variable, i.e.,：

FDR=f (R_I,R_P,R_B)；

(3) in video transmitting procedure, it is assumed that the video data packet number of different I type is K in moment t network_I(t), And TTL (Time-to-Live) value having the same；To the video data packet i, T of any I type_I,i(t) indicating should in moment t The life duration that data packet has consumed, M_I,i(T_I,i(t)) node number for once receiving the video data packet, N are indicated_I,i (T_I,i(t)) node number for currently still carrying the video data packet, R are indicated_I,i(t) the remaining life of the video data packet is indicated Order duration；In addition, N_SIndicate all node numbers for participating in transmission of video；So, following relationships are set up：

(4) exponential distribution of λ is obeyed at the time of contact interval between node, therefore video data packet i cannot be delivered successfully Probability is equal to its any one backup data package and is both greater than R with the time that destination node is met next time_I,i(t) probability, i.e., exp(-λR_I,i(t))；Therefore, P is used_I,iIndicate that the video data packet i of I type can be by successful delivery in its life span Probability then has：

(5) to sum up, the data packet of I type is in the average delivery probability of moment t：

6. a kind of video machine meeting transmission route algorithm based on multi-user Cooperation game as claimed in claim 5, feature exist In：The video data packet of P and B type is in the specific calculating process of the average delivery probability of t moment and the video data packet of I type It is identical.

7. a kind of video machine meeting transmission route algorithm based on multi-user Cooperation game as claimed in claim 2, feature exist In：In step 1.3, calculating edge quality gain by partial differential equation discretization, detailed process is as follows：

S1, to the video data packet i of any I type, calculated in the edge quality gain of t moment as follows：

The edge quality gain MQG of the video data packet i of video data packet i and the B type of S2, P type_P,iAnd MQG_B,iIt counts respectively It calculates as follows：

Wherein, R_I、R_PAnd R_BRespectively indicate the successful delivery probability of the video data packet of I, P and B three types；N_I、N_PAnd N_BPoint Not Biao Shi successful delivery I, P and B frame desired value.

8. a kind of video machine meeting transmission route algorithm based on multi-user Cooperation game as claimed in claim 2, feature exist In：

In step 3.2, the utility function of building is as follows：

Wherein, N indicates the node number met, and M indicates the different video data packet number that the node carries, and V indicates same When the video-frequency band number transmitted, due to having respective destination node, therefore p to any video-frequency band v_n,vIndicate node n and Contact probability between the destination node of video-frequency band v, MQG_n,v,mVideo data that expression is carried by node n, belonging to video-frequency band v Wrap the edge quality gain of m.

9. a kind of video machine meeting transmission route algorithm based on multi-user Cooperation game as claimed in claim 2, feature exist In：In step 3.3, calculating the near-optimization Nash solution of the game based on geometric space representation method, detailed process is as follows：

T1, for video data transmission, use p_n,vMQG_n,v,mIt indicates value of utility of the video data packet m relative to node n, calculates it Between effectiveness distance d_n, it is specific as follows：

T2, video data transmission, the effectiveness distance product by normalized video data packet m relative to game user n are directed to φ_n,mSpecific calculating is as follows：

T3, to a given video data packet, correspond to all game users effectiveness distance product all having the same, Equilibrium condition is expressed as follows：

Wherein, u_nFor determining the threshold condition of video data packet distribution termination；

T4, from correspond to mobile node n list L_nK video data packet distributes to n before middle selection, so that this K video data Packet reaches critical value u to the effectiveness sum of the distance of node n_n, i.e. K meets following conditions：