Realization of UAV Routing Protocol Evaluation System Based on Game Theory Comprehensive Weighting

Jinze Huang¹, Fengbiao Zan^2*, Xin Liu², Da Chen¹

¹School of Physics and Electronic Information Engineering, Qinghai Minzu University, Xining, China.
²School of Computer Science, Qinghai Minzu University, Xining, China.

DOI: 10.4236/jdaip.2021.94016                

Abstract

Aiming at the issue of the selectivity of routing protocols between UAV groups, a comprehensive weighting evaluation system based on game theory is proposed. Taking network simulation data as an example, three protocols, AODV, DSDV, and OLSR, are selected as the research objects. The results show that the DSDV protocol is suitable for the simple communication environment between UAV groups, the AODV protocol is suitable for the complex communication environment between UAV groups. In addition, the evaluation system is compared with the two evaluation systems of the Covariance Analytic Hierarchy Process (Cov-AHP) and the entropy method to calculate the relative deviation. The comparison results show that the new evaluation system is more reasonable than the other two evaluation systems.

Keywords

Cov-AHP, Entropy Method, Game Theory Comprehensive Empowerment, UAV Routing Protocol

1. Introduction

UAVs are widely used in many fields. Taking the vertical lift drone as an example, many countries are striving to seek new breakthroughs in structure and use, which also makes the application prospects of drones broader [1] [2]. However, due to the complexity of the work environment and cumbersome tasks, a single UAV meets the task requirements due to its own conditions [3]. By adopting the form of drone group, the information fusion and communication cooperation between drones can be completed efficiently and quickly.

When the UAV group is working, due to the limitation of the regional environment, the communication status between the UAVs will be affected, accompanied by delayed information reception and signal quality [4]. When the UAV group is working, it is affected by the regional environment. Due to restrictions, the communication status between drones will be affected, and there will be situations where information is not received in time and the signal quality is weak. At this time, choosing the right routing protocol will help solve this problem.

In the evaluation and selection process for a certain thing, people usually adopt a single evaluation system. Take AHP as an example. AHP mainly relies on expert scoring, which is too subjective and can easily lead to deviations in results. At this stage, many scholars combine AHP or improved AHP with other evaluation methods so as to a new evaluation system. Based on AHP and entropy method, Chunsheng Cui [5] puts forward a comprehensive system of logistics evaluation that is used as a reference for logistics service performance evaluation; Jing Chen [6] proposes a fuzzy water quality evaluation method combining FAHP with CRITIC, which can make the water quality evaluation index of weir area more reasonable; Mengdi Qian [7] argues a combination of AHP and factor analysis for evaluating and analyzing power equipment vendors, which can be taken as a reference for the selection of power equipment vendors; Veera P. Darji [8] applies the evaluation methods of AHP and EVAMIX to promote the decision-making of the industrial environment. It can be seen that the comprehensive evaluation weighting system, as an effective evaluation method [9] - [15], has been widely used in many fields.

In order to select a suitable routing protocol between UAV groups, this paper combines Cov-AHP and entropy weight method to propose an evaluation model based on game theory for comprehensive weighting. According to the characteristics of the UAV group, the pros and cons of the routing protocol and the suitable environment of the UAV group can be comprehensively judged, and the routing protocols suitable for the UAV group in different environments can be screened out.

In the choice of routing protocol, this article selects the common AODV protocol in the on-demand routing protocol and the DSDV protocol and OLSR protocol in the active routing protocol as the research objects for analysis.

2. UAV Routing Protocol and Index Analysis

2.1. Analysis of UAV Routing Protocol

As this article selects on-demand routing protocol and active routing protocol, the two protocols will be briefly introduced below.

On-demand routing protocol: This type of protocol does not need to create a routing table in advance. It will only generate a routing table when the source node needs to send a data packet. Therefore, the routing table does not contain all the routing information in the network topology. Part of the node routing information. The information of this type of routing protocol is updated in a timely manner, the energy consumption is low, but the time delay is large.

Active routing protocol: This type of protocol actively sends routes, performs packet switching, and updates the routing table. Therefore, when the source node sends a message to the destination node, once the routing path is established, the source node can immediately know the routing information in the routing path. Compared with the on-demand routing protocol, the delay of this type of routing protocol is more minor, but the energy consumption is larger. And because all the routing tables need to be maintained when the topology is updated, it is usually not in a stable state.

Compared with the on-demand routing protocol, the active routing protocol has a smaller delay and relatively large control overhead. In contrast, the on-demand routing protocol has low energy consumption and large delay. Therefore, the network topology scenarios applicable to the two protocols are also different.

2.2. Performance Index Analysis

In the UAV communication routing protocol, the performance indicators of the routing protocol are:

1) Packet delivery rate: In the transmission process, the ratio of the data packet successfully received by the destination node to the data packet sent by the source node [16]. The larger the ratio, the stronger the reliability of the protocol.

2) Average end-to-end delay: This indicator can be expressed as the ratio of the difference between the time of successfully receiving a data packet and the time of sending a data packet to the data packet received by the system [17]. The smaller the delay, the better the routing quality.

3) Average number of hops: It is calculated based on the ratio of the sum of successfully received data packets and forwarded data packets to the received data packets by the source node. In different environments, the UAV group flight distribution form is different, and this article considers the densely distributed UAV group. The smaller the average number of hops between the dense drone groups, the higher the packet delivery rate, the better the received signal, and the lower the cost.

3. Empowerment System Establishment

3.1. Performance Index Analysis

This article establishes an index hierarchical evaluation system by adopting the Cov-AHP proposed by scholar Zhongqiu Xie [18], which is divided into two simulation models: one is the number of drones, which are 20, 30, 40, and 50, respectively, and the moving speed Take a selected value of 20 m/s; the second is the moving speed of the drone, which are 20 m/s, 30 m/s, 40 m/s, 50 m/s, and the fixed number of drones is 20; the experiment uses NS3 for network simulation, The node in the network simulation replaces the UAV, the area is a rectangular area of 4 km × 4 km, and the communication distance is 1 km. The index hierarchy system is shown in Figure 1.

Figure 1. Routing protocol selection hierarchical structure.

After constructing the index hierarchy shown in Figure 1, the weights must be calculated according to Cov-AHP. The calculation steps [19] are as follows:

1) According to different quantitative indicators, establish a covariance matrix. The covariance matrix is shown in Table 1.

2) Construct the judgment matrix according to the covariance matrix in Table 1. According to the formula (1) and formula (2), the judgment matrix can be calculated. The judgment matrix is shown in Table 2.

$c_{ij}=\frac{a_{ij}}{a_{ii}\times \sqrt{\frac{a_{ij}}{a_{ii}}\times \frac{a_{ji}}{a_{jj}}}}$ (1)

$c_{ji}=\frac{1}{c_{ij}}$ (2)

3) Determine the subjective weight, that is, find the eigenvector of the judgment matrix, and obtain the eigenvector according to the square root method.

${\omega }_i=\frac{{\epsilon }_i}{{\displaystyle \underset{j=1}{\overset{m}{\sum }}{\epsilon }_i}}$ (3)

${\epsilon }_i=\sqrt[m]{{\displaystyle \underset{j=1}{\overset{m}{\prod }}{c}_{ij}}}\left(i=1,2,\cdots ,m\right)$ (4)

In formula (3), is the weight to be obtained, and formula (3) and formula (4) are the square root method. The obtained weights are tested for consistency. When the consistency test standard is passed, the weight value is considered to be valid.

$CI=\frac{{\lambda }_{\max }-m}{m-1}$ (5)

$CR=\frac{CI}{RI}$ (6)

Table 1. Covariance matrix.

Table 2. Judgment matrix.

In formula (5), is the maximum characteristic vector obtained by the judgment matrix, and is the consistency deviation standard of the matrix. In formula (6), is the random consistency ratio, which is the random consistency standard of the matrix.

After the weights pass the consistency check, the program selection can be prioritized, and the weights need to be normalized when necessary.

3.2. Entropy Method for Weight

According to the related interpretation of the definition of information entropy, information entropy can be understood as the size of the discrete value of the index. The smaller the information entropy, the larger the discrete value of the index. Then the weight calculated by this indicator has a greater impact on the evaluation of things. Therefore, the information entropy value can be used to calculate the entropy weight of each index for comprehensive system evaluation.

The average end-to-end delay and average number of hops are negative indicators and need to be standardized. Suppose n indicators are given $\left(A_1,A_2,\cdots ,A_n\right)$ , the standardized indicators are $\left(B_1,B_2,\cdots ,B_n\right)$ , the calculation formulas for positive and negative indicators are [20] as follows:

Positive indicators:

$B_{ij}=\frac{A_{ij}-\min \left(A_i\right)}{\max \left(A_i\right)-\min \left(A_i\right)}$ (7)

Negative indicators:

$B_{ij}=\frac{\min \left(A_i\right)-A_{ij}}{\max \left(A_i\right)-\min \left(A_i\right)}$ (8)

After the data is standardized, the next step is to obtain the entropy value based on the standardized data:

$H_j=-\frac{1}{\ln \left(n\right)}{\displaystyle \underset{i=1}{\overset{n}{\sum }}\frac{B_{ij}}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{B}_{ij}}}}\ln \frac{B_{ij}}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{B}_{ij}}}$ (9)

Through this formula, the entropy value of other indicators can be obtained $\left(H_1,H_2,\cdots ,H_n\right)$ , Then calculate the entropy weight through information entropy.

$\bar{\omega }=\frac{1-H_j}{n-{\displaystyle \underset{j=1}{\overset{n}{\sum }}{H}_j}}$ (10)

The weight can be obtained by formula (10), the same as the weight obtained by Cov-AHP, and can be normalized when necessary.

3.3. Game Theory Comprehensive Empowerment

This article adopts the game theory method of total weighting, and uses Nash equilibrium as the coordination index to balance the weights. Game theory comprehensive weighting can effectively combine the weights obtained by Cov-AHP and entropy weight method to obtain the optimal weight. Nash equilibrium can reasonably solve the conflict between the combined weights and achieve aoptimal coordination. The specific calculation steps of this method [21] are as follows:

1) First use Cov-AHP and entropy method to obtain weights, assign weights to attributes, and use different methods to get many different weights $\overline{w_k}=\left(\overline{w_1},\overline{w_2},\cdots ,\overline{w_n}\right)$ , ( $k=1,2,\cdots ,m$ ), Among them, m is 2 in this paper. After different weights are obtained, the different weights are combined linearly. Suppose the combination coefficient is, then the combination formula is as shown in formula (11):

$w=k_1\overline{w_1}+k_2\overline{w_2}$ (11)

2) Optimize the linear combination coefficient, optimize the linear combination coefficient according to the data, and minimize the dispersion between and. Here we use the optimization strategy model proposed in the literature [6]:

$\min {\Vert {\displaystyle \underset{k=1}{\overset{n}{\sum }}ak\overline{w_k^{\text{T}}}}-\overline{w_k}\Vert }_2\left(k=1,2,\cdots ,m\right)$ (12)

3) Find the first derivative of Equation (12) and transform it into matrix form:

$\left(\begin{array}{cc}\overline{w_1}\overline{w_1^{\text{T}}}& \overline{w_1}\overline{w_2^{\text{T}}}\\ \overline{w_2}\overline{w_1^{\text{T}}}& \overline{w_2}\overline{w_2^{\text{T}}}\end{array}\right)\left(\begin{array}{c}{k}_1\\ k_2\end{array}\right)=\left(\begin{array}{c}\overline{w_1}\overline{w_1^{\text{T}}}\\ \overline{w_2}\overline{w_2^{\text{T}}}\end{array}\right)$ (13)

Through this matrix equation, the combination coefficient, can be calculated, and the combination coefficient can be put into Equation (11) to calculate the optimal weight.

4. Model Application Results and Analysis

4.1. Simulation Model Raw Data

Run the simulation data code through the NS3 software in the virtual machine, and obtain the data of three evaluation indicators: packet delivery rate, average end-to-end delay, and average number of hops through code result analysis. The original data of the two simulation models are listed as follows (Table 3, Table 4).

Table 3. UAV quantity simulation model data.

Table 4. UAV moving speed simulation model data.

4.2. Comprehensive Evaluation System Calculation Weight

1) Taking the model of the number of drones as an example, first use Cov-AHP to calculate the weights, and take the criterion layer to the target layer as an example to establish the covariance matrix of the criterion layer to the target layer:

In Table 5, X₁ to X₃ refers to the three protocols to be selected. Since some of the calculated indicators are negative, negative numbers are not allowed when computering the weights. Therefore, when calculating the judgment matrix, it is necessary to take the absolute value of these negative indicators, and substitute the covariance matrix into Equations (1) and (2) to obtain the judgment matrix of the criterion layer to the target layer: Table 6.

Substituting the judgment matrix into Equations (3) and (4), the weight vector of the judgment matrix is ${\omega }_i=\left(0.332850926,0.031128045,0.636021029\right)$ . Then calculated by formulas (5) and (6) CI = −1, CR = 1.7241 < 0.1, passing the consistency test, indicating that the weight is valid. In the same way, using this method to obtain the weights of other indicators, and all have passed the consistency test. The weights of other indicators are shown in Table 7:

According to the obtained layer weights, the set weights of the overall elements are calculated. Here, the calculation idea of literature [12] is adopted: the weight matrix corresponding to each indicator is multiplied by the weight column vector of the criterion-level target and then normalized. The set weight is obtained, and the obtained set weight is (0.248661, 0.473024, 0.278315).

2) The entropy method determines the objective weight. In this paper, the larger the group delivery rate evaluation index, the more beneficial the result, and the smaller the average end-to-end delay and the average number of hops, the more beneficial the result. Therefore, when the data is standardized, the group delivery rate is suitable for formula (7), the average end-to-end delay and average number of hops are applicable to Equation (8), taking the packet delivery rate as an example. The standardized data is shown in Table 8:

Table 5. Criterion-to-target covariance matrix.

Table 6. Judgment matrix of criterion level to target level.

Table 7. The weight of each indicator.

Table 8. Standardized data on packet delivery rate.

Substituting the solved index standardized data into Equations (9) and (10) to obtain the entropy weight. The calculated entropy weight is $\bar{\omega }=\left(0.413433,0.389562,0.197006\right)$ .

3) Game theory obtains total weights. Substituting the calculated Cov-AHP weight and entropy weight into Equation (13), the matrix equation is obtained, and then the linear coefficients are obtained according to the matrix equation. The matrix equation is as follows:

$\left(\begin{array}{cc}0.3630& 0.3419\\ 0.3419& 0.3615\end{array}\right)\left(\begin{array}{c}{k}_1\\ k_2\end{array}\right)=\left(\begin{array}{c}0.3630\\ 0.3615\end{array}\right)$

The matrix expression equal sign is multiplied by the inverse matrix of the two-dimensional matrix. Only the coefficient matrix is left on the left, and the two matrices on the right are multiplied to obtain the combined coefficient. According to the matrix equation, the combination coefficients k₁ = 0.0069 and k₂ = 0.9937 are obtained. Substituting Equation (11) can get the optimal weights in Table 3 W = (0.3376, 0.4452, 0.2460). According to the calculation method of the model of the number of drones, in the same way, the optimal weight W = (0.4063, 0.3853, 0.3772) of the moving speed of the drone can be obtained in Table 4.

Through the weight analysis, it can be seen that when the moving speed of drones is stable and the number of drones is gradually increasing, the weight of the DSDV protocol accounts for the largest proportion, and the stable moving speed of drones means that the network topology changes are steady and not drastic. It shows that the DSDV protocol is more steady for a simple communication network environment between drone groups; and when the number of drones is steady and the moving speed is gradually increasing, the weight of AODV accounts for the largest proportion, which shows that in the case of drastic changes in the network topology, the AODV protocol is more suitable for more complex communication environments between drones.

4.3. Evaluation and Comparison Analysis of Calculation Results

According to two different simulation models, the relative deviation between the weight calculated by Cov-AHP and entropy weight method and the weight estimated by the new method in this article is selected to calculate the relative deviation. The weight calculated by Cov-AHP, entropy weight method, and the method in this article is as follows Table 9 and Table 10 show:

Table 9. Weight of UAV number simulation model.

Table 10. UAV moving speed simulation model weight.

Figure 2. Relative deviation of drone quantity simulation model.

Figure 3. Relative deviation of UAV moving speed simulation model.

According to the weights listed in Table 9 and Table 10, the relative deviation between Cov-AHP, entropy weight method, and game theory combination weighting method is calculated. To make the relative deviation distribution visible, the establishment is shown in Figure 2 and Figure 3. The histogram of the distribution, the histogram is as follows:

Through the analysis of Figure 2 and Figure 3, the relative deviation of DSDV in Cov-AHP and game theory combination weighting method in Figure 2 is 6%, the relative deviation of entropy weight method and game theory DSDV is 12%, and the deviation between the two is 6%. Which shows that DSDV has the most minor deviation in the weight analysis of the number of UAVs. The AODV deviation between the two in Figure 3 is 23%, indicating that AODV has the most minor deviation in the UAV moving speed weight analysis. It further verifies the rationality of the analysis weights of the new method in this article. Compared with the other two methods, this article can select protocols with more minor deviations based on indicator analysis, and integrate the objectivity of the two methods to make data analysis more accurate.

5. Conclusion

This paper adopts the game theory method of total weighting, respectively using Cov-AHP and entropy weight method to calculate their respective weights, and then using Nash equilibrium as the indicator to objectively combine the weights to calculate the optimal weights, and according to the relative deviations, analyze the suitable weights. Aiming at the issue of the selection of communication protocols between UAV groups, this method is scientific, and the results are more convincing and have good reference significance. Data analysis proves that this method provides a new reference method for the selection and evaluation of routing protocols between UAVs.

Acknowledgements

This work was supported by the Tianjin University-Qinghai Minzu University Independent Innovation Fund Project “Huangshui River Ecological Environment Monitoring and Governance” and the Qinghai Minzu University Graduate Student Innovation Project (10M2021005).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Yu, S., Heo, J., Jeong, S. and Kwon, Y. (2016) Technical Analysis of VTOL UAV. Journal of Computer and Communications, 4, 92-97. https://doi.org/10.4236/jcc.2016.415008
[2]	Jo, D. and Kwon, Y.J. (2017) Analysis of VTOL UAV Propellant Technology. Journal of Computer and Communications, 5, 76-82. https://doi.org/10.4236/jcc.2017.57008
[3]	Cui, C.S., Wang, Y. and Li, Q. (2019) Logistics Service Performance Evaluation Based on Comprehensive Weighting of Game Theory Indicators. Mathematics in Practice and Knowledge, No. 2, 110-118.
[4]	Gu, X.P., Tang, D.Q. and Tang, G.Z. (2021) Overview of the Research on Key Echnologies of UAV Clusters. Automation and Instrumentation, No. 4, 21-26+30.
[5]	Ma, Z.Y., He, M., Liu, Z.J., Gu, L.F. and Liu, J.T. (2021) Overview of Research on UAV Collaborative Control. Computer Applications, No. 5, 1477-1483.
[6]	Chen, J., Zhao, M., Zhou, H. and Yi P. (2019)Fuzzy Comprehensive Water Quality Evaluation Method and Application in JiangYan District Based on Combination Weighting of Game Theory. Hydropower Energy Science, No. 9, 32-35+91.
[7]	Men, Y.K., Qian, M.D., Yu, Z., et al. (2020) Fuzzy Comprehensive Evaluation of Power Equipment Suppliers Based on Combination Weighting of Game Theory. Power System Protection and Control, 48, 179-186.
[8]	Darji, V.P. and Rao, R.V. (2013) Application of AHP/EVA MIX Method for Decision Making in the Industrial Environment. American Journal of Operations Research, 3, 542-569. https://doi.org/10.4236/ajor.2013.36053
[9]	Zhang, G.L., Chen, S. and Xiao, P. (2020) Research on Extension Evaluation of Rural Road Maintenance Quality Based on Game Theory. Applied Mathematics, 11, 670-677. https://doi.org/10.4236/am.2020.117045
[10]	Zhan, S.W. and Qi, J. (2021) Research on The Evaluation Index System of Rural Public Service Quality Based on AHP-Fuzzy Comprehensive Evaluation Method. Operation and Management, No. 7, 168-174.
[11]	He, R.H., Wan, F.M., Xiang, L.S. and Su, Y.Y. (2019) Construction of a Credit Index System for Cigarette Retail Households Based on Group Decision-Making and Analytic Hierarchy Process. Computer Applications and Software, No. 12, 81-86.
[12]	Liu, T.Y., Deng,Y. and Chan, F.L. (2018) Evidential Supplier Selection Based on DEMATEL and Game Theory. International Journal of Fuzzy Systems, 20, 1321-1333. https://doi.org/10.1007/s40815-017-0400-4
[13]	Zhu, D.R., Wang, R., Duan, J.D. and Cheng, W.J. (2021) Comprehensive Weight Method Based on Game Theory for Identify Critical Transmission Lines in Power System. Electrical Power and Energy Systems, 124, Article ID: 106362. https://doi.org/10.1016/j.ijepes.2020.106362
[14]	Zhou, H.Y., Yuan, Y.B., Liu, C.L., Wu, C. and Zhang, M.Y. (2018) Extension Model for Safety Appraisal of Existing Concrete Members Based on an Improved Comprehensive Weighting Method. Advances in Civil Engineering, 2018, Article ID: 1217543. https://doi.org/10.1155/2018/1217543
[15]	Gao, Z.W., Ma, D.H., Guo, X.D., Wang, W. and Wang, Z.T. (2019) The Comprehensive Assessment Method ofConcrete Damage after Disastrous Fire Based on Game Theory-Normal Cloud Model. Mathematical Problems in Engineering, 2019, Article ID: 5159497. https://doi.org/10.1155/2019/5159497
[16]	Song, Z.D., Jiang, X.B. and Zhang, R.F. (2010) The Selection Method of Tactical Internet Routing Protocol. Firepower and Command Control, No. S1, 44-46+59.
[17]	Lium F.G. (2020) Simulation of AODV Routing Protocol Based on NS2. Information and Computer (Theoretical Edition), No. 18, 167-169.
[18]	Xie, Z.Q. (2015) Cov-AHP: An Improvement of the Analytic Hierarchy Process. Quantitative Economics and Technical Economics Research, No. 8, 137-148.
[19]	Li, L.J., Dong, N., Xiong, F., Luo, L.L. and Li, H.Y. (2019) Research on Construction Project Management Performance Evaluation Based on Cov-AHP and Hierarchical Connection. Journal of Guangxi Normal University (Natural Science Edition), No. 3, 111-119.
[20]	Zhang, B. (2021) Surrounding Rock Classification Method of Tunnel Construction Based on Entropy Method. Journal of Yangtze River Scientific Research Institute.
[21]	Chen, J.L. (2003) Research on the Evaluation Method of Combination Weighting Based on Game Theory. Fujian Computer, No. 9, 15-16.