In this paper, we study the problem of spectrum scarcity in a network of unmanned aerial vehicles (UA Vs) during mission-critical applications such as disaster monitoring and public safety missions, where the pre-allocated spectrum is not sufﬁcient to offer a high data transmission rate for real-time video-streaming. In such scenarios, the UA V network can lease part of the spectrum of a terrestrial licensed network in exchange for providing relaying service. In order to optimize the performance of the UA V network and prolong its lifetime, some of the UA Vs will function as a relay for the primary network while the rest of the UA Vs carry out their sensing tasks. Here, we propose a team reinforcement learning algorithm performed by the UA V’s controller unit to determine the optimum allocation of sensing and relaying tasks among the UA Vs as well as their relocation strategy at each time. We analyze the convergence of our algorithm and present simulation results to evaluate the system throughput in different scenarios. Index Terms multi-agent systems, reinforcement learning, spectrum sharing, task allocation, UA V networks I. I NTRODUCTION Unmanned Aerial Vehicles (UA V) have several advantages such as ﬂexibility, agility, wide ﬁeld of imaging view and low deployment cost over ground-based infrastructures; hence, are widely used in many applications such as surveillance, disaster relief, wildlife monitoring, and military applications [1]– [6]. Also, UA Vs face many security challenges based on the vast area of applications. Many methods such as key sharing, authentication, authorization, and so on have been proposed for these devices in the past few years [7], [8]. In some of these missions such as disaster monitoring and military applications, the pre-allocated spectrum for UA Vs is not sufﬁcient to collect and transmit high-throughput imagery data in certain locations or times, hence an on-demand access to additional spectrum is required. In this paper, we propose a solution for securing extra spectrum for the UA V networks. In this solution, the UA V network leases a portion of time access to the licensed spectrum of a terrestrial network. In order to compensate the spectrum access grant, some of the UA Vs provide relaying service for the terrestrial network, while the rest of UA Vs perform their regular sensing and transmission tasks using the leased spectrum. The allocation of relaying and sensing tasks among the UA Vs as well as Distribution A: Approved for Public Release, distribution unlimited. Case Number 88ABW-2019-2375 on 15 May. 2019. The work of F. Afghah, J. Ashdown and K. Turck was supported by AFRL. selecting their motion strategy is performed by a high-capability drone which serves as controller unit of the entire network. This optimization is performed considering various factors such as the position of the UA Vs and ground0based nodes, the quality of communication channels as well as the expected lifetime of the drones. Cooperative spectrum leasing as a property-right model spectrum sharing solution has been studied previously in the context of cognitive radio networks [9]–[14]. The main objective of these works is maximizing the beneﬁts of the primary network through optimal time allocation between the primary and secondary networks. The ignorance of the performance of the secondary network, can cause signiﬁcant operation problems in critical missions. 23 4 5 1 Sensing Coalition Relaying Coalition6UP DownRight Left Fixed Elevation Emergency Center (HAP ) Source Relaying SensingTime Slot 0.5 0.5 Ground Transmitter Ground ReceiverDefinition : Arrow : Sending the PU Packets Relaying the PU Packets Sending the Secondary User (SU) Packets Fig. 1. A sample scheme of the proposed spectrum sharing between a UA V network and a terrestrial licensed network. The task allocation problem to select UA Vs for relaying or sensing tasks can be modeled as a multi- agent reinforcement learning (MARL) problem [15]. In a cooperative MARL problem, multiple learning agents work together to achieve a system-wide optimal solution. There have been efforts to solve task coordination in a fully distributed manner. However, the proposed solutions impose a heavy computation and decision making loads to the UA Vs, and still may not converge to an optimal solution. Hence, distributed task allocation solutions are not practically feasible in highly dynamic systems [16], [17]. In this paper, we consider a remote sensing situation where the UA Vs send their individual information to a UA V node designated for data fusion and overall management of the network. We assume that the UA V network does not own spectrum and opportunistically uses an external spectrum to complete the remote sensing mission. We present an algorithm based on team reinforcement learning to maximize the total utility of the system by re-positioning and determining the proper task for each drone, while minimizing the number of steps to achieve the optimal conﬁguration. We provide experimental results to verify the convergence of the proposed algorithm. 2 II. S YSTEM MODEL Let us assume a network of NUA Vs in a proximity of a licensed transmitter-receiver pair that are willing to share their spectrum with the UA V network in exchange for cooperative relaying service. The primary network is considered as a terrestrial network; while the secondary network consists of the UA Vs that hover in a constant altitude. The primary pair may be in need of cooperative relaying services for experiencing a low quality direct transmission due to several reasons such as long distance between the transmitter and receiver, shadowing and fading effects. In this paper, we assume that there is no direct transmission link between the primary user (PU)’s transmitter and receiver, however, the proposal spectrum sharing method can be used in scenarios where the PU participates in spectrum leasing to take advantage of cooperative diversity gain. We assume that the UA Vs are managed by a high altitude platform (HAP) UA V called as emergency center located in a ﬁxed location [3]. The UA V network owns a dedicated frequency bandwidth for control commands and exchanging critical information, however it requires additional spectrum to transmit high resolution video and images during a disaster monitoring mission. In order to provide additional on-demand spectrum, the UA Vs can participate in a cooperative spectrum leasing transaction with the primary network. In this case, the PU will lease half of its time access to its spectrum to the sensing UA Vs, and the relay UA Vs will assist the PU with forwarding their packets during the other half of the time slot. In other words, the UA Vs can serve in two sensing andrelaying modes. Here, we consider a centralized control scenario in which the emergency center determines the action of each UA V in terms of their motion and their role (relaying or sensing) to maximize the network utility. Let us consider a case where KUA Vs perform as relay, and the remaining NKperform the sensing task. An example of this scenario with N= 6 andK= 3 is depicted in Fig. 1. In this model, we consider a 2-D random walk for the UA Vs, so that they can change their locations into adjacent cells in the grid using one of the four movement actions fUp;Down;Left;Rightg. The UA Vs are not allowed to take diagonal steps. The channels between all nodes including the UA Vs, the emergency center, and the PU are calculated based on pairwise distances during each time slot. Following similar works including [18], we assume that channel state information(CSI) parameters are known for the HAP UA V . Channel coefﬁcient for each pair of users is deﬁned as follows: i) hPT;U iis the channel parameter between the primary transmitter and ithUA V , ii)hUi;PRcarries the channel information between the ithUA V and the primary receiver, and iii) hS;UiandhUi;Edenote the channel parameters between the ithUA V and the source and the emergency center respectively. Moreover, we assume that the noise terms at the receiver sides are normally distributed symmetric complex values, ZCN(0;2). In the literature, many papers including [19], [20] address power optimization; while we assume that the transmission power is arbitrary but constant for all transmitters. Based on Fig. 2, we divide each time slot into two parts. We assume that, relaying UA Vs receive the primary packet and forward them to the primary receiver in the ﬁrst half. And in the second half, sensing UA Vs forward the collected data to the emergency center. In each half slot, UA Vs utilize full-duplex for the transmission. Relaying SensingTime Slot 0.5 0.5 Fig. 2. One time-slot for both networks 3 The received signal for the UA V can be written as follow: yu[n] =hi;uxi[n] +zr[n] (1) In (1), subscript ican be source or PU transmitter, xiis the signal sent by the PU transmitter or the source andyuis the received signal at UA V u. On the other side of the transmission, the received signal for the emergency center or the primary receiver is written as follow: yj[n] =hu;jxu[n] +zj[n]; (2) where subscript jcan represent the emergency center or the PU-receiver, xuis the transmitted signal by UA Vu, andyjis the received signal at the jthreceiver which can be the emergency center or the PU-receiver. In both (1) and (2), hijdeﬁnes the effect of path loss between nodes iandj. In this work, we utilized the Amplify and Forward (AF) relaying mode at the relay UA Vs. Based on [21], [22], the throughput for the emergency center receiver can be obtained as: RSE=1 2log2(1 +PSjhS;Ej2(3) +PSjhS;Uij2PUijhUi;Ej2 2+PSjhS;Uij2+PUijhUi;Ej2); wherePSandPUiare transmission power for source and UA V respectively. 2is the background noise power.idenotes the index for the relay(UA V). On the other hand, the throughput rate for the primary receiver is shown as: RPU=1 2log2(1 +PPTjhPT;PRj2(4) +PPTjhPT;U ij2PUijhUi;PRj2 2+PPTjhPT;U ij2+PUijhUi;PRj2); wherePPTis the primary transmitter power. It is noteworthy that (3) and (4) are true for single relay scenarios. This system involves a multi-agent scenario including Krelay UA Vs and a set of NK sensing UA Vs, hence the transmission rate of the relaying and sensing sub-systems can be deﬁned as follows ifUE=fE1;E2;:::E NKgdenotes the sensing set and UR=fR1;R2;:::;R Kgis the set of relaying UA Vs: RSE(Multi-UA V) =1 2log2(1 +PSjhS;Ej2(5) +X j2UEPSjhS;Ujj2PUjjhUj;Ej2 2+PSjhS;Ujj2+PUjjhUj;Ej2); RPU(Multi-UA V) =1 2log2(1 +PPTjhPT;PRj2(6) +X l2URPPTjhPT;U lj2PUljhUl;PRj2 2+PPTjhPT;U lj2+PUljhUl;PRj2); where,RSE(Multi-UA V )andRPU(Multi-UA V )are the achievable rates using multi UA Vs. Since we assumed the distances between the source and emergency center and also PT and PR are long, we can eliminate both hS;EandhPT;PR terms from the rate ( jhS;Ej'0andjhPT;PRj'0). At the end of each time slot, the PU receiver and the emergency center announce their received throughput to the UA Vs in order to provide them with a feedback (i.e., reward) based on the previous states and their taken actions. 4 Based on the deﬁnitions in our system model, we can deﬁne the reward or gain as a throughput difference for the whole system between to consecutive time slots such as (t)and(t1): Reward = 1(RPU(t)RPU(t1)) (7) + 2(RSE(t)RSE(t1)); where, 1and 2are two control parameters. Reward in (7) is obtained based on the location of the UA Vs, their tasks, and the distance to their destinations or from their sources. The goal of our proposed model is to ﬁnd the best location for UA Vs and the right task that result in an optimal summation throughput rate. In Section III, we use this reward function to develop a reinforcement technique for task allocation and motion planning. III. M ULTI -AGENT TEAM REINFORCEMENT LEARNING Multi-Agent Reinforcement Learning (MARL) algorithms can be categorized into three branches based on the nature of the problem. First, all the agents work cooperatively with each other. In this branch, all the agents have the same goal of maximizing the common discount factor. Also, they all have the same reward function. In the second category, the agents are fully competitive which is known as zero- sum games. In third one, the behavior of agents is a mixture of two previous groups which is neither competitive nor cooperative. Our problem in this paper is the type with fully cooperative agents. Two approaches to solve these kinds of problems are Nash Q-learning and team learning [23], [24]. We aim to use the team Q-learning for our UA Vs. In the team learning approach, a single learner such as the emergency center monitors the behavior of all agents. The reason we chose this algorithm is that the single learner can utilize simple machine learning algorithms such as Q-learning in the multi-agent learning environment similar to the scenario in this paper. To model a single UA V agent in the learning environment, the Markov Decision Process (MDP) is investigated. In each step, the UA V interacts with its environment which is the state of the problem. In this speciﬁc problem, the state for the UA V is the location on the grid size. Let St2S denote the state for each UA V at step t, whereSis the set for all possible states. Time step tis different and it depends on the grid size of the UA Vs. The ithUA V at each state such as si tcan follow an action ai tbased on a policy from an action set A. The action set AisfUp(0), Down(1), Left(2), Right(3), Emergency Task(4) ;Relaying Task(5)g. The ﬁrst four actions change the location for the UA V and keep the previous task from the previous location. However, the last two actions, keep the UA V in same location, but decide on its task. Action ai tchangesSttoSt+12S for the whole system. Based on the new state St+1, the updated reward rt2R is awarded to the system based on the (7). In a single-UA V environment, the goal of the UA V is to ﬁnd the optimal policy which chooses actions that maximize the E(PNumber of Steps t=0 trt)standing for expected discounted reward over time where is a discount factor. SARSA [25] and Q-learning [26] are two general algorithms for the RL problems. Each MPD consists of a 4-tuple (S;A;Pa;Ra)where,Sis a ﬁnite set of states, Ais a ﬁnite set of actions, Pa:SaS0![0;1]orPa(S;S0) =Pr(St+1=s0jSt=s;at=a)is the probability that choosing an action afor a single UA V will change its state from StoS0at the time t+ 1.Ra:Sa!RorRa(S;S0)is the expected awarded reward when a single UA V changes its state fromStoS0due to action a. This immediate reward is obtained based on (7) in this special problem. Then, the single agent can update its Q-value based on: Q(S;a) =(1 )Q(S;a) (8) + [Ra(S;S0) + max a02AQ(S0;a0)]; where (0< 1)is the learning rate. These equations and relations are valid for a single-learner. However, in multi-agent environment, multiple UA Vs follow the taken action at the same time without 5 sharing any information with each other. Hence, the action vector such as At= (a1;a2;:::;a N)t+12A leads the system from SttoSt+1for all UA Vs. Using team Q-learning, (8) can be modiﬁed and written as: Q(S;[a1;a2;:::;a N]) = (1 ) (9) Q(S;[a1;a2;:::;a N]) + [Ra(S;S0) + max A02AQ(S0;A0)]; whereA0= [a0 1;a0 2;:::;a0 N]is the action vector when the UA Vs are placed in state S0andQis the action-value for the whole system. There are three kinds of rewards based on the (7). If the throughput summation in a new state is greater than the previous state, then the positive reward is given to the system. If the difference is zero, then there is no reward for that (zero value). If the difference is negative between the new state and the previous state, then a negative reward is obtained by the system. The issue for team Q-learning is the process of exploration. Considering a 10 10 grid size for 2 UA Vs deﬁnes 100 states for each UA Vs; then, deﬁning a team of 2 UA Vs makes 10,000 states for the system just for locations without considering any tasks. This huge number of states can be time-consuming for the learning process. Action selection method is another important module for the Q-learning which stands for selecting the actions which the UA Vs will perform to proceed the learning process. These methods base a fulcrum for exploration and exploitation searches [27]. In this paper, we used -greedy exploration with a constant value for the which means the system chooses random actions with the probability of and selects the best actions based on the maximum value in the Q-table with the probability of 1. This method is deﬁned in: [a1;a2;:::;a N]t+1: (10) At+1=( argmax AQ(S;A); Probability 1; Random Actions, Probability ; whereNis the number of UA Vs and Ais the action vector for NUA Vs which brings the maximum Q value. Table I summarizes the mapping information for the team Q-learning and the deﬁnitions in this speciﬁc problem. In the past few years, deep learning has absorbed lots of attention in different areas such TABLE I MAPPING THE COMPONENTS BETWEEN THE TEAM Q-LEARNING AND THE SYSTEM MODEL FOR A 66GRID . Component Description Sample size Actions Making decisions about moving or the task 6 # of Agents Number of UA Vs 2 State Considering a grid for all agents together (36)2= 1;296 Q-Table State(Location), Action(Movement or Task) values (366)2= 46;656 Reward Difference of throughput R(S;A;S0)!R as biomedical signal processing [28]–[30], pattern recognition, computer vision, autonomous vehicles, and natural language processing. Moreover, in recent studies, it has been shown that deep learning tools can be utilized alongside with reinforcement learning challenges to give a bright consciousness of the environment to the agents [26], [31]–[34]. 6 IV. S IMULATION RESULTS In the following simulations, we consider a ground-based PU transmitter-receiver pair as well as a pair of drone-based source and emergency center with randomly initialized locations. We split the tiled cover- age area into L1L2tiles, where drones are allowed to move in four directions fUp;Down;Left;Rightg. Channels between nodes are calculated based on the hi;jCN(0;d2 i;j), wheredi;jis Euclidean distance between nodes iandj. We arbitrarily use 1= 1, 2= 1 (deﬁned in Eq. 7), = 0:1, = 0:3,= 0:1, 2= 1nW,PPT= 10mW ,PS= 20mW , andPUi=20mW , unless otherwise speciﬁed explicitly. In the-greedy exploration, we consider a constant rate for the exploration and exploitation phases. The number of states is (L1L2)NforNdrones. We execute the MARL algorithm for 200 episodes to ﬁll in the Q-tables for all drones based on their actions and locations. We use sequential episodes, where the resulting Q-tables for each episode is used to initialize Q-tables for the next episode. The number of steps per episode to cover the entire state space is calculated based on the experience and the number of states. We then repeat each experiment in 10 external iterations for enhanced accuracy and avoiding bias to initialization. Timing value for each scenario is provided for Python implementation with Intel Xeon(R) CPU @ 3.50GHz and 16.0GB RAM. The simulation parameters are summarized in Table II. TABLE II SIMULATION PARAMETERS AND REQUIRED TIMES FOR THE SIMULATION WITH 2 UAV S AND 6ACTIONS . Grid Size: 22 (4) 33 (9) 44(16) 55 (25) 66 (36) 88 (64) 1010 (100) Number of States: 44=16 99=81 1616=256 625 1,296 4,096 10,000 Size of the Q-Table: 576 2,916 9,216 22,500 46,656 147,456 360,000 Number of Iterations: 10 10 10 10 10 10 10 Number of Episodes in each Iteration: 200 200 200 200 200 200 200 Number of Steps in each Episode: 120 800 2,000 5,000 12,000 20,000 30,000 Process Time for each epoch (Sec): 0.102628 0.762713 2.425558 8.757846 49.007077 146.936207 291.176670 Total required time: 205.256s 25.4m 80.85m 4.8h 27.2h 3 days 6 days Figure 3 shows the sum utility for primary and emergency network and the summations of those for each episode. The sum utility represents the accumulated utility during all steps of the episode. We observe that due to using sequential learning, the latter episodes yield a higher sum utility suggesting that the algorithm converges to its ﬁnal value faster. This behavior is valid for both primary and secondary networks. Figure 4 demonstrates the number of times that UA Vs switched their task and also the number of times they changed their locations in each episode. Each value at each point for a speciﬁc episode is the summation for both UA Vs for all taken steps. It is logical that the HAP starts searching all states by switching tasks in each location to get a new reward. However, as simulation goes on, the HAP starts learning from its past experiences and switches the tasks for the UA V networks fewer compared to the beginning of each iteration. Also, HAP forces the UA Vs to explore more locations in smaller episodes. For larger episodes, the number for movements or changing location is less than the beginning of the iteration. These behaviors demonstrate the learning process toward the optimal location and task to gain a higher throughput rate for both networks. Fig. 5 shows the required steps to get 90% of the throughput summation in each episode. The number of steps is decreasing when the number of episodes is increasing which explains the learning behavior and denotes that in less necessary steps, the emergency center can ﬁnd the best states (Location) and actions for all UA Vs to get the optimal reward. All ﬁgures in this section are sketched for the grid 6 6 (36). Based on Table II, the process time for each iteration is increasing exponentially for larger grid size. Moreover, this process time is dependent to the number of UA Vs. This happens due to the nature of the team reinforcement learning. Since we are using distance-based deterministic channel coefﬁcients, ofﬂine learning methods can be used to ﬁll in the Q-tables. 7 0 25 50 75 100 125 150 175 200 Episodes0.100.150.200.250.300.35Total and Emergency Throughput0.0200.0250.0300.035 Primary ThroughputSum Utility Emergency Center Utility Primary UtilityFig. 3. Summation throughput for emergency, primary, and both networks for all UA Vs. V. C ONCLUSION In this paper, we introduced a solution for dynamic spectrum sharing in which a network of search-and- rescue UA Vs needs an additional spectrum to send critical information such as videos to the emergency center. In this method, some of the UA Vs provide a relaying service for a primary network in exchange for borrowing an additional required spectrum. We proposed a team-learning MARL algorithm, in which the emergency center of the UA V networks can determine the optimal actions of the UA Vs in terms of their motion as well as the optimum task. It is worth mentioning that, in practice, the UA V network is trained by this learning mechanism in an ofﬂine manner to identify the best set of actions for different situations and use this knowledge for fast decision making during the missions. Simulation results showed the proposed distributed method converges to the optimal locations and tasks for both the primary and emergency network. The optimal state is the win-win solution for both groups. For the future works, we are working on other learning methods to reduce the effect of states (locations and tasks) and agents (UA Vs) on the performance of the algorithm. Due to the exponential behavior of team learning, it takes time for ofﬂine learning; however, we aim to increase the number of UA Vs and the grid size at the same time. VI. ACKNOWLEDGMENT OF SUPPORT AND DISCLAIMER The authors acknowledge the U.S. Governments support in the publication of this paper. This material is in part based upon work funded by AFRL. Any opinions, ﬁndings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reﬂect the views of the US government or AFRL. 8 0 25 50 75 100 125 150 175 200 Episodes10001500200025003000350040004500Number of Switched Tasks (-) 20004000600080001000012000140001600018000 Movement actions (_._)Number of Switched Tasks Number of movementsFig. 4. Number of switched tasks and movements for all UA Vs in each episode.