{'fraction_non_alphanumeric': 0.02322511706841824, 'fraction_numerical': 0.0032999151450391275, 'mean_word_length': 5.268715524034673, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Self-Organizing Relay Selection in UAV Communication Networks: A Matching Game Perspective

For large unmanned aerial vehicle (UAV) networks, the timely communication is needed to accomplish a series of missions accurately and effectively. The relay technology will play an important role in UAV networks by helping drones communicating with long-distance drones, which solves the problem of the limited transmission power of drones. In this paper, the relay selection is seen as the entry point to improve the performance of self-organizing network with multiple optimizing factors. Different from the ground relay models, the relay selection in UAV communication networks presents new challenges, including heterogeneous, dynamic, dense and limited information characteristics. More effective schemes with distributed, fast, robust and scalable features are required to solve the optimizing problem. After discussing the challenges and requirements, we find that the matching game is suitable to model the complex relay model. The advantages of the matching game in self-organizing UAV communications are discussed. Moreover, we provide extensive applications of matching markets, and then propose a novel classification of matching game which focuses on the competitive relationship between players. Specifically, basic preliminary models are presented and some future research directions of matching game in UAV relay models are discussed.


I. INTRODUCTION
With the increasing development of the unmanned aerial vehicle (UAV) technology, the large-scale multi-UAV systems [1] play an important role in military and civilian fields, such as in wars, emergency communications and Internet of Things [2]. Maintaining the communication of large-scale UAV networks becomes an important and timely issue.
From the perspective of requirement, the communication of UAVs can be classified into internal communication and external communication. In the external communication, UAV networks mainly exchange the information with the higher command center via the satellite communication. However, relay selection strategies, such as power control, interference management and carrier selection, may result in heavy communication overhead. As a result, it is timely to develop distributed selection approaches for the future UAV relay networks.
After exploring some relay selection cases, this article analyzes some fundamental challenges and requirements of the self-organizing relay selection in UAV networks. Then, following the attractive features of matching game market [5], we propose and discuss some advantages of the matching game for self-organizing relay selection in UAV communication networks.
Matching game is powerful to tackle the problem of resource allocation by modeling the relationship of players between two distinct sets. It has recently attracted extensive attention in wireless networks [6], [7], such as cell association and cooperative spectrum sharing. Moreover, some preliminary matching solutions have been studied in ground relay models. However, the inherent features and fundamental challenges of relay selection in UAV communication networks need to be further studied. The matching game also needs to be developed to solve the resource assignment problems effectively. Compared with existing matching models [6], [7], i) we mainly focus on UAV relay models based on the featured matching models, the classification of relay models and special features of future UAV communication networks are explored; ii) focusing on the internal competition relationship among drones, we propose a novel classification of matching models in wireless networks, in which they are classified as matching with substitutability, with partial substitutability and without substitutability, respectively. It is noted that from different perspectives of the multi-UAVs system, several UAV architectures were proposed in the existing work.
• UAV swarms: The multi-UAVs system is analyzed from the perspective of the formation configuration, which mainly emphasizes the external physical features of UAV networks. Analysis from this perspective makes the models more intuitive, so problems of transportation planning and control [8] are generally solved by this point of view.
• Flying Ad-Hoc Network (FANET): It develops the networking technology of UAV networks. By analyzing the communication link, the architecture of multi-UAV communication networks can be optimized effectively. From this perspective, problems of the topology construction and routing protocol are mainly studied [4].
• Multi-tier drone architecture: It is analyzed from the perspective of layers of structure [9]. By analyzing different types, flight altitudes and communication objectives of UAVs, multi-tiers UAVs are developed to improve the spectral efficiency of users in cellular networks. It is also an efficient perspective for the multi-UAVs system. Different from these researches, we analyze the UAV networks from the perspective of resource optimization. The optimization of relay model among UAVs is discussed, which makes the topic more targeted so as to research into transmission situations, challenges, and corresponding solutions. We develop effective matching models of resource optimization  based on the formation and communication architectures. The optimizing models proposed in this paper can be applied to the existing classification framework in different analytical perspectives.
The rest of this article is organized as follows. In Section II, after introducing the main classification of internal UAV relay models, the requirements and challenges of the relay selection in UAV communication networks are analyzed. In Section III, the matching game model in UAV networks is presented. In Section IV, extensive applications of matching game model in future UAV communication networks are discussed, new classification focusing on the relationship between players is proposed, and future research directions are given.

NETWORKS
In this section, we introduce the relay model from the perspective of the task planning. Moreover, by exploring the inherent features of UAV communication networks, we briefly discuss some fundamental challenges and requirements of optimizing relay selection in UAV communication networks.

A. The classification of relay models in UAV communications
Predictably, large UAV formations will be able to accomplish self-organizing air tasks, and a complicated task can be subdivided into several subtasks. Therefore, the UAV formations can be divided into different coalitions according to different tasks. In this case, the relay transmission will run through the whole UAV communication system. The main applications of relay selection in UAVs are shown as follows: 1) Relay transmission between coalitions of UAVs: Due to the different demands of subtasks, each coalition performs its subtasks and coordinates with each other so as to achieve the overall goal or complete the overall task. Therefore, the information exchange is necessary between the coalitions of UAV systems. Fig. 1 shows that, one coalition of UAVs can communicate with remote coalitions relayed by other coalition leaders or drones which are located between two sides of the communication.

2) Relay transmission between individual devices:
One drone needs to establish communication links with the coalition leader, and it also needs to communicate with the surrounding drones to coordinate the flight missions. As shown in Fig. 1, when one drone is too far away from the coalition leader to establish direct communication link, relay technology can be used to feed back the timely information. In addition, when drones need to share information with surrounding drones, they can also choose relay transmission to improve the transmission efficiency.
The main differences of the two types are given. Firstly, the coalition leader needs to communicate with other coalitions, which requires a strong transmission capability, while drones in the alliance can be small and reusable with lower transmission capability. According to the transmission capacity, full duplex and non-orthogonal multiple access technologies can be used in the inter-coalition transmission, while the half duplex with light loaded transmission can be used in the intracoalition transmission. Moreover, in self-organizing systems, there is a competitive relationship between coalition leaders for channels access, while available resources within the coalition may be assigned by the coalition leader. In addition, when a drone needs to communicate with another drone in another coalition, the corresponding protocols of channel assignment may be required.

B. Discussion of relay selection in UAV communication networks: Challenges and requirements
The technical challenges of the relay selection optimization in UAV communication networks are discussed as follows: • Heterogeneous. The "heterogeneous" has two layers of meaning. On one hand, the network architecture is heterogeneous. The "Gremlins" UAV program 1 and multi-tier drone architecture [9] were proposed to develop the UAV system with various layers. There is a tight relationship between different levels of drones. For example, the reusable drones in "Gremlins" have to maintain stable 1 Available: http://www.darpa.mil/news-events/2015-08-28 communications with large UAVs. On the other hand, in UAV networks, tasks are assigned by the system, and the communication is to ensure the completion of task, while the communication requirement of ground networks is generated spontaneously by users. Different from relay models in ground networks with single task transmission, drones may need to accomplish multiple tasks simultaneously.
• Dynamic networks. The dynamic of UAV communications brings two aspects of challenges. The drastic change of the external environment and the rapid change of the formation may cause the previous communication link unavailable, which requires the rapid adjustment of the selection strategy of UAV networks. On the other hand, the dynamic change of the UAV formation may be the spontaneous movement to perform the task. The mobility of drones can be used to ferry the transmitted information, including the trajectory optimization [10] and the suitable selection of mobile UAVs.
• Dense deployment. As mentioned in [1], there may be hundreds of drones in the air simultaneously. The ground control is not reliable when the UAV network is out of the ground and carries out long-range missions on its own. How to optimize the self-organizing model in such a dense network has not been considered in the ground relay network. The resource optimization for dense deployment environment is different from which for sparse one. Particularly, the problems of transmission power constraint and interferences among drones are more serious.
• Limited information. Without a powerful centralized controller and stable transmission conditions, UAVs with limited transmission power hardly obtain perfect environmental information. UAVs should make strategies according to limited and dynamic information from neighbor drones. In a heterogeneous, dynamic and distributed system, limited information as one constraint of frequency domain is inevitable. By exploring the optimization features, we discuss some featured requirements of relay selection in UAV communication networks, which mainly include four features: distributed, fast, robust, and scalable.
• Distributed: In UAV communication networks, most drones are deployed randomly and dynamically in order to adapt to the flight tasks. The strategy of relay selection becomes more diversified due to dense deployment of drones. The centralized controller will process a large amount of data information and resource consumption. Thus, selection optimization problems for UAV communication networks are suitable to be solved in an effective self-organizing manner.
• Fast: The dynamic feature of networks require drones spending shorter time to make decisions, because the location of drones may move and the sets of active communication drones are random. For example, one drone may change its flight path during the communications. Outdated strategies of relay selection may be meaningless in a short time, while the fast strategy can not only avoid the useless selection but also use the dynamic feature to improve the transmission.
• Robust: The relay selection strategies should be robust for the dynamic environment. As discussed before, there are several complicated optimization factors of UAVs, such as dynamic communication tasks and varying flight paths. The obtained information may also be incomplete or corrupted by noise. Thus, the distributed selection solutions should be robust to address the problems of randomness, dynamics, and uncertainty in UAV communication networks.
• Scalable: The resource optimization for dense deployment of UAV communication networks is different from that for sparse one. Thus, the self-organized selection schemes should have the ability to extend to the application of the dense UAV networks. Due to the limited transmission power of drones, multi-hop relay model will be applied in UAV networks, and the number of transmission hops is uncertain. The self-organizing relay selection models should be extended to multi-hop UAV communication networks.

III. MATCHING MARKET-BASED OPTIMIZATION FOR UAV COMMUNICATION MODELS
In this section, a brief introduction to the structure of matching game [5]- [7] is given. We will also discuss the special advantages of matching game in UAV communication networks.
In essence, the matching game is defined by two sets of players (S, R) and two preference relations ≻ i , ≻ j , permitting each player i ∈ S, j ∈ R constructing preference lists over one another, i.e., ranking the players in S and R respectively according to their individual preferences [5]. Therefore, the matching game can be expressed as G (S, R, ≻ i , ≻ j , q i , q j ), where the maximum number of each player's ability to match is called quota, q. Each player uses the preference relation to rank the players in the opposing set. The proposed matching game can be fully represented once the preference of each player is defined.   Fig. 2 shows the structure of matching model in UAV communication networks. Driven by different tasks, source drones select relay drones according to transmission objectives, types of transmission data, urgency of tasks, energy consumption and flight path. During the process, the relay selection and transmitting power can be adjusted according to the matching results. Similarly, relay drones will filter and adjust matching source drones according to several factors such as the preference of tasks, the energy consumption and the interference with other drones. It can be noted that the information required by source drones and relay drones is different, which is one of characteristics of the matching game model.
The information is obtained primarily from two ways: one is by sensing the environment and interacting with other drones, and the other is the information obtained from the coalition leader.
• The coalition leader as a temporary database: Coalitions cooperate with each other to accomplish missions, and coalition leaders are used to summarize the information of drones within the coalition and then interact with the ground controller. Therefore, the coalition leader can be used as a temporary database to provide useful information for drones. For example, drones can request relative position and the plan of flight trajectory from the database. Compared to sensing the environment and interacting with other drones, the database approach is more efficient but not real-time.
• Sensing and information exchange: In the large-scale communication environment, drones cannot obtain the whole information from the coalition leader to make strategies, so they need to sense the surrounding environment information and exchange information among neighbors. For example, the channel occupancy can be obtained by energy detection or feature detection, and the information exchange can help with the task cooperation.
As discussed above, not all the information can be stored, drones need to make strategies by themselves to ensure more accurate optimization. Distributed transmissions have relatively strong robustness. When the database is unavailable, it is also possible for drones to make individual decisions by perceiving environment. Thus, it is necessary to develop the database-assisted distributed systems.
Based on different requirements and optimization factors, source drones construct individual matching lists [5] in which the elements are relay drones. Similarly, relay drones choose source drones according to their own requirements. After constructing the preference list, the matching markets with or without peer effects [7] and substitutability are formed. The situation of substitutability will be discussed in Section IV. The matching game is good at modeling the relationship between source drones and relay drones.
Firstly, in distributed UAV models, source drones select the preferred relay drones according to their own transmission requirements. Meanwhile, relay drones filter source drones by their objectives and utilities. Matching game can define individual utilities for source drones and relay drones. The available algorithmic implementations allow a largely distributed solution to the problem of resource allocation without obtaining all of the information in networks.
Secondly, different from other game models, stable matching results are the primary objective in the matching market. In the distributed system, obtaining global optimum needs a long time to make decisions, while the fast changing network environment does not allow such kind of longer decision period. Pursuing the results of optimal relay selection in the whole network is not reasonable. The stable matching can respond to the changes effectively, and also maintain the stability of network communications. Therefore, stable matching is more suitable for UAV communication networks.
Thirdly, in the matching game, each player will learn and update the preference list during the matching process [7]. Due to the nature of the matching game, the previous learning list can guide the matching of players in the selection process. If current matching results are broken by the change of the environment in the matching process, players can make a faster adjustment according to the previous preference lists and the perception prediction results.
Finally, the extensibility of the matching scheme in various sizes of networks has been verified in the existing work such as [11]. Moreover, multi-tier matching models were preliminary designed and used in the wireless network [12], which verified the availability of the matching game in the multi-level. In the future research, more organic combination can be developed. The discussion is given in Section IV. A.

RELAY NETWORKS
The authors in [6], [7] discussed the classification of matching game according to the practical communication scenarios in ground wireless networks. The classification can cope with part of the problems of relay networks. However, novel features and applications of matching game in wireless networks can be further explored. Matching game theory need to be explored and extended so that new features for future relay models in UAV communication systems can be better applied.
A. Extensive application of matching model 1) Multi-level matching game for multi-hop relay models: In UAV communication networks with power constraint, source drones which cannot connect to destination drones by two-hop transmission should choose multi-hop relay models. Nowadays, distributed relay selection solution for multi-hop relay models have not been fully explored. Considering multiple optimization factors, it is necessary to model complex networks as suitable distributed models so as to optimize them with low complex methods. For the multi-hop communication, a multi-level matching market can be modeled, which is the extension from the general matching market. Global matching networks can be divided into multi-level markets and solved by matching approaches. Fig. 3(a) shows that, if two source drones with limited transmission power want to connect with one destination drone, the communication should pass through three-hop transmissions. When source drones choose relay drones at the first level, the possible matching conditions of relay drones at the next level should be evaluated, which provides a good reference factor for the matching filter. Next, the selected relay drones will attend to the next level matching market and match relay drones at the next level. Because of the resource competition, source drones can adjust their selection strategies according to the matching results. Based on the multi-level matching model, the problem of multi-hop route selection can be solved by distributed methods. Therefore, multi-level matching provides an appropriate perspective for multi-hop relay models in UAV networks.
2) Dynamic matching game combined with the trajectory optimization: The trajectory and propulsion energy consumption are the key problems of UAV dynamics [13], it is reasonable to develop the relative mobility of UAVs within networks. Different from the air-to-ground trajectory optimization [10], [13], UAVs in the network have certain relative positions to finish the flight mission. The trajectory of multiple UAVs within the formation cannot be adjusted arbitrarily. During flying as a formation, drones can adjust their relative trajectories within the reasonable range. Therefore, it's a worthy direction to research into the cooperation transmission of multi-drones based on the topology adjustment and trajectory planning.
While UAVs are driven by tasks or impacted by the environment to adjust the relative position, they can be used to ferry information [10] from the other UAVs. Depending on the original trajectory instead of additional flight can The resource of such as one unit time In the matching game with substitutability, resource is a l w a y s d i v i d e d w i t h f i x e d quotas, and players dominate resource blocks fixedly. Lower priority players will be replaced. I n the m a t c h i n g game w i t h partial substitutability, resource is not divided into fixed blocks. The mutual complementary players share the resource, while the other players will be replaced.
In the matching game without substitutability, players share the resource together instead of replacing the other players.  j  j  j  j  2  3  2 2  3  2 2 2  3  2  3 j  2  3  2 2  3  2  3  2 2  save the additional propulsion energy as much as possible. As shown in Fig. 3(b), if UAVs adjust the flight formation during the communication, source UAVs can make use of the adjustment and select the appropriate communication mode effectively (select static UAVs or cooperate with mobile UAVs to help the transmission). Here, the dynamic matching model can be developed, where source drones and relay drones make strategies in advance according to the future dynamic adjustment. Different from the existing matching work which tried to avoid the influence of dynamics [7], the adjustment of the UAV network can be prescient and used to improve the quality of transmission.
3) Matching game with and without substitutability: Conventional classification consists of one-to-one model, manyto-one model and many-to-many model, which is one of the classifications based on the structure of matching market. Authors in [7] classified the matching market as classic matching, matching with externalities and matching with dynamics, which do not refer to the inherently competitive relationships between players. To capture the features of inherent relationship of players in the matching game, beyond the existing classes, the classification according to the relationship of competitors is discussed following and illustrated in Fig. 4.
• Class I: Matching with substitutability: This class constitutes the popular and baseline class, in which the relationship between players is solely competitive. Players replace other competitors when they are successfully accepted by players in the opposing set. Existing literature of matching game in wireless networks always modeled the network as the matching market with substitutability. The most prominent example is the resource allocation model with fixed matching quotas such as base station association with fixed number of channels.
• Class II: Matching with partial substitutability: In the second class, competitive relationships exist among matching applicants. Receiving matching requests, players filter the applicants according to the priority. However, priority is not the only filtering criterion for refusal or acceptance. The matching with partial substitutability considers the internal factors of competition such as resource surplus or tolerance limit of resource demands. The most prominent example is the resource allocation model with unfixed matching quotas, such as channel association considering unfixed time resource.
• Class III: Matching without substitutability: Matching market without substitutability [14] can be used to model future networks with resource sharing. This matching model has been used in social networks. For example, one laboratory needs different types of professors to cooperatively complete research tasks. In this class, the priority of players is not the criterion for filtering. Players do not accept or reject a matching connection according to the unilateral performance of applicants. The performance of the whole network or the applicants with other connections can be considered in the matching process. This class is suitable for the fully sharing networks, such as spectrum sharing equally with unfixed quotas.

B. Preliminary applications of the proposed classification in relay networks
1) Classic matching with substitutability: It is the classic matching model which is well studied in the existing researches. Authors such as in [5]- [7] verified that the communication systems with fixed resource blocks can achieve the stable results efficiently by the matching schemes.
2) Multi-users selection with partial substitutability: In [11], we studied the problem of relay selection with multinodes using a many-to-one matching model.
The source nodes' preferences capture the data rates while the relay nodes filter source nodes according to the transmission efficiency and the residual resource. Due to the uncertain quota and the heterogeneous requirements, some source nodes

Global satisfaction
Global optimum (exhaustive search) The proposed matching game without substitutability The best response of many−to−many selection The many to many random selection (b) The matching game without substitutability achieving the nearly global optimum of satisfaction in non-substitutive relay models.  with high data rates can not replace those with low data rates in the matching process. The reason is that the chosen source nodes are more complementary for the resource of relay nodes. It is illustrated in Fig. 5(a) that, the proposed distributed matching approach based on the matching game with partial substitutability has a significant advantage in terms of satisfaction for all network sizes.
3) Many-to-many matching networks without substitutability: In [15], we consider a UAV communication network with multi-drones equipped with multi-access interface. 20 source drones sharing 10 relay radios of 5 relay drones. Choosing the same channel resource, source drones will share the time resource of relay drones equally. The chosen relay drones take not only their own performance but also the matching results of other relay drones into consideration. In this case, the relay model of UAV communication networks can be modeled as a matching market without substitutability.
The average convergence performance of the distributed relay selection model is shown in Fig. 5(b). The solution based on the matching game without substitutability catches up with the global optimum. It can be noted that matching game without substitutability is better than other relay selection solutions such as best response solution, which validates the performance of matching game in the model without substitutability.
The robustness of the matching algorithm is also investigated. At iteration t = 15 and 30, we let 8 source drones leave the model and 5 new source drones enter the model, respectively. The results in Fig. 5(c) show that the system can quickly converge to a stable result after the perturbations occur. This verifies that the matching game algorithm is robust to the dynamics of communication tasks in the UAV networks.

C. Future research direction
It can be seen that the matching game for self-organizing relay selection optimization in UAV communication networks has definitely drawn an exciting future, while current researches are still far away from the expected vision. We list some future research problems for matching game models and relay selection in UAV communication networks below:

1) Diversified communications in UAV communication networks:
It can be noted that multiple transmission models exist in large UAV communication networks. Drones will join with different transmission tasks at the same time. For example, one drone connected to the coalition leader may be chosen as a relay node to assist another transmission pairs. In order to achieve better performance of UAV communication networks, some new features of game models should be developed to improve the applicability in resource allocation.
2) Matching game with imperfect information: Knowledge can be viewed as the high-level intelligence obtained from the contextual information, which is truly beneficial to decisionmaking. In most existing studies, it is assumed that all players can obtain correct information, while the information acquisition may be incomplete or even incorrect in complex systems. Such imperfect information brings about new challenges since players make selection decisions depending on the knowledge. Optimizing matching performance with imperfect information is useful for the future UAV communication networks.
3) Design and analysis of the heterogeneous matching market: Most existing studies assumed that players in one side of the matching market employed the same utility objective. However, the assumption is not practical in reality. In practice, drones in the network belong to different UAV coalitions, which have different service requirements or types. In addition, the same type of drones may have heterogeneous matching utilities due to different processing abilities. Introducing heterogeneity into the matching market will enhance the flexibility in optimization, which needs to be further studied.

V. CONCLUSION
This article provided a distributed matching model perspective for relay selection in UAV communication networks. First, this article introduced different situations of relay selections in large UAV communication networks, and pointed out the challenges and requirements of relay models. Then, the fundamental concepts of the matching theory and the advantages in UAV communication networks were presented. In order to understand the selection issues of relay models, this article showed the extensive applications of the matching game in wireless networks. The preliminary simulations validated the performances of the relay selection strategies. Finally, research directions of the matching model in UAV communication networks were discussed.