A Combined Topology Formation and Rate Allocation Algorithm for Aeronautical Ad Hoc Networks

In this paper, we form a topology and allocate rates to the aircraft in aeronautical ad hoc networks (AANETs) according to the number of mounted antennas on aircraft, antenna beamwidth and maximum steering angle so that we maximize the number of aircraft having a data rate higher than a threshold in AANETs. We formulate this problem as a mixed integer linear programming (MILP). Since the formulated MILP reflects the multi-commodity flow problem and it is at least NP-complete, we propose a two-phase heuristic algorithm to efficiently form topology and evaluate maximum number of aircraft exceeding the data rate threshold for higher aircraft node density. Our simulation shows that performance of the heuristic algorithm is only 8% less than the optimal results in terms of the percentage of average connected aircraft in AANETs with low densities. In the highest network densities, the connectivity percentage can reach up to 40% with a 75 Mbps data rate threshold, which is the worst case for the connectivity. Furthermore, the connectivity percentage is investigated for different network parameters such as antenna beamwidth. We observe that the nodal degree has the least effect on the connectivity percentage for the flight activity over the North Atlantic Corridor.