Degree Distribution of Arbitrary AANET

Abstract

Taking the safe distance between two adjacent planes in the same airline into account, we give a model for the multiairline aeronautical ad hoc network (AANET). Based on our model, we analyze the plane's degree distribution of any arbitrary AANET. Then, the expressions of the degree distributions of one single plane and the whole networks are both worked out and verified by the simulations, in which we generate several random AANETs. Since our model is a reasonable abstraction of the real situation, the theoretical result we get is very close to the result of the real networks, which is also shown in the simulations.

Xue Liu 1, 2 and Xiaoping Zeng 1 and Zhiming Wang 1 and Li Chen 1 and Yuemei Jin 1

Academic Editor:Ronald M. Barrett

1, College of Communication Engineering, Chongqing University, Chongqing 400044, China
2, Chongqing Communication Institute, Chongqing 400035, China

Received 26 October 2014; Revised 15 February 2015; Accepted 16 February 2015; 28 February 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

With the rapid development of civil aviation, the demands of accessing Internet on board have become stronger than ever before. However, in polar, desert, marine, and other areas where base stations cannot be built, aircrafts have to use satellite links or large span multihop links within AANET to reach base stations. Due to the large delay, high cost, and limited bandwidth of satellite links, AANET is preferred for internet accessing in these regions [1, 2].

For AANET, the Newsky project has proposed networking strategies with mobile IPv6 technology [3]. ATENAA project (advanced technologies for networking in aeronautical applications) has studied Ka-band array antennas and optical communications between aircrafts [4]. Rohrer et al. have presented cross-layer networking solutions among physical, mac, network, and transport layers [5]. Vey et al. have proposed the use of direct sequence CDMA (DS-CDMA) at the access layer [2] while Yan et al. have studied the capacity of single flight path AANET [6].

In an ad hoc network, the number of a node's neighbors is called "degree" of that node. Thus, the degree distribution of an ad hoc network tells the probability that the degree is an exact number by choosing a node randomly. Based on the degree distribution of the network, a lot of work can be done: the analysis of connectivity and robustness of the network by using the method of generating function formalism [7]; the design of routing and mac protocols; for example, we can choose planes with high degree expectation to relay messages, since usually we cannot know where all the planes are; the site selection of base stations; for example, base station can be set at a place to make sure that the average of the degree expectations of planes in coverage region of that base station is high, which makes it reach more planes through multihop links.

The degree distribution of mobile ad hoc networks has been widely discussed, but most of them are based on the scenarios that nodes in the networks move randomly. However, for AANET and vehicle ad hoc networks (VANET), the nodes are moving along specified lines, which is different from the old scenarios. In VANET, which is also studied a lot in recent years, the speed of vehicles can be affected by plenty of factors (such as pedestrian crosswalks, traffic jams, and traffic lights) and the degree distribution which a vehicle is hard to calculate or even to assume. Thus, the problem about calculating the degree distribution of the networks where nodes move along specified lines has not been solved yet.

In this work, we give a model for the AANET, from which we can approximately calculate the degree distribution of any arbitrary AANET.

2. The Model

Since AANET is not deployed currently and none of the achievements mentioned previously is taken as standard or in real use, we do not consider the physical or access layer of AANET and use a fixed value, [figure omitted; refer to PDF] (between 50 nmi and 300 nmi as used in [8]), as the communication range for all planes.

According to the specifications of the International Civil Aviation Organization (ICAO) [9], a safe distance, call it [figure omitted; refer to PDF] (it is around 20 nmi according to ICAO), should be kept between two adjacent planes in the same airline. As the length of an airline is far greater than [figure omitted; refer to PDF] , we take [figure omitted; refer to PDF] as the smallest unit of length. Thus, we assume that the distance between two adjacent planes in the same airline can only be [figure omitted; refer to PDF] . Since the distance of two airlines at different height level is usually several hundred of meters, which is much less than the assumed planes' communication range [figure omitted; refer to PDF] , we ignore the distance of two airlines.

In Figure 1, there are several random lines crossing each other with points uniformly spaced on them. The lines stand for airlines while points denote the possible locations of planes. The distance between two adjacent points in the same line is [figure omitted; refer to PDF] . Furthermore, we assume that the spatial distribution of planes on each airline obeys discrete uniform distribution.

Figure 1: The scenario of this work.

[figure omitted; refer to PDF]

3. The Degree Distribution of a Plane

The usual method to calculate the degree distribution of a plane is experimentally based on the scenario that the spatial distribution of planes in each airline follows Poisson point process, and it is easy to tell that the degree distribution of a plane obeys Poisson distribution [6, 10]. However, the scenario does not take the nonignorable safe distance between planes into account, which is significantly different from the real situation in the sky. For instance, in [6, 10], the number of a plane's neighbors can be infinite, but if safe distance is considered, the number of each plane's neighbors has an upper limit.

In Figure 2, there are [figure omitted; refer to PDF] airline segments covered by plane [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] equals 3 in this example). In each segment, there are several possible locations for planes and we denote [figure omitted; refer to PDF] as the number of locations in segment [figure omitted; refer to PDF] , where the location occupied by plane [figure omitted; refer to PDF] is not counted. For each location of segment [figure omitted; refer to PDF] , we denote [figure omitted; refer to PDF] as the probability that a plane is at that location.

Figure 2: The neighbors of a plane.

[figure omitted; refer to PDF]

Since planes can only be at the designed locations on the airlines, the probability that plane [figure omitted; refer to PDF] has [figure omitted; refer to PDF] neighbors is the probability that [figure omitted; refer to PDF] planes are at the locations covered by plane [figure omitted; refer to PDF] . Then, using [figure omitted; refer to PDF] to denote the number of planes on segment [figure omitted; refer to PDF] , we can get [figure omitted; refer to PDF] and the probability that there are [figure omitted; refer to PDF] planes on segment [figure omitted; refer to PDF] is [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] denotes the number of the ways of setting [figure omitted; refer to PDF] planes at [figure omitted; refer to PDF] locations.

In order to set [figure omitted; refer to PDF] planes in total at the locations covered by plane [figure omitted; refer to PDF] , we set planes following this order: [figure omitted; refer to PDF] to segment 1, [figure omitted; refer to PDF] to segment 2, and [figure omitted; refer to PDF] to segment [figure omitted; refer to PDF] . Thus, the value ranges of [figure omitted; refer to PDF] to [figure omitted; refer to PDF] are as shown in Table 1.

Table 1: Value range for [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]	Value range
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]

Therefore, we can obtain the probability that there are [figure omitted; refer to PDF] neighbors around plane [figure omitted; refer to PDF] according to the order we set planes in [figure omitted; refer to PDF] Denoting [figure omitted; refer to PDF] as [figure omitted; refer to PDF] , we can get a simpler expression for [figure omitted; refer to PDF] in [figure omitted; refer to PDF]

4. The Degree Distribution of AANET

Assume [figure omitted; refer to PDF] airlines which are in Figure 1. Each airline has [figure omitted; refer to PDF] locations for planes. [figure omitted; refer to PDF] denotes the probability that a plane is at a location of airline [figure omitted; refer to PDF] . For plane on each location in the networks, we can calculate its degree distribution by using the method in Section 3. Then, we denote [figure omitted; refer to PDF] as the probability that a plane at the [figure omitted; refer to PDF] th location of airline [figure omitted; refer to PDF] has [figure omitted; refer to PDF] neighbors and uses [figure omitted; refer to PDF] to represent the maximum number of neighbors of the plane on that location. Thus, to calculate the probability that a plane in the AANET has [figure omitted; refer to PDF] neighbors, we add all the [figure omitted; refer to PDF] with multiplying plane's existing probability at the [figure omitted; refer to PDF] th location of airline [figure omitted; refer to PDF] , which is [figure omitted; refer to PDF] . Then, we obtain the degree distribution of the AANET in [figure omitted; refer to PDF]

5. Numeric Results

For verifying our work, we generate three random scenarios and draw them in Figures 3 to 5, respectively, whose detailed parameters are listed in the appendix. In each scenario, we use MATLAB to generate plane for each location in airline [figure omitted; refer to PDF] with probability [figure omitted; refer to PDF] (from 0.5 to 1, see the appendix). After the generation, we record the number of the planes and every plane's neighbors (degree). Then, we delete all the planes in the scenario and generate planes again in the same way. We repeatedly generate planes in one scenario for 100000 times. Then, by using [figure omitted; refer to PDF] to denote the total number of planes generated in 100000 times and [figure omitted; refer to PDF] to denote the number of planes with degree [figure omitted; refer to PDF] , we can get the approximate degree distribution of that scenario through [figure omitted; refer to PDF]

Figure 3: Scenario 1 (30 airlines).

[figure omitted; refer to PDF]

Figure 4: Scenario 2 (20 airlines).

[figure omitted; refer to PDF]

Figure 5: Scenario 3 (20 airlines).

[figure omitted; refer to PDF]

We calculate the theoretical value in (5) and simulation value in (6) for each scenario in Figures 3 to 5 and draw their results in Figures 6 to 8, respectively, where the theory and simulation lines are overlapped.

Figure 6: Results for scenario 1 ( [figure omitted; refer to PDF] ).

[figure omitted; refer to PDF]

From Figures 6 to 8, we can see that the probability that a plane has no neighbor is nearly zero, because a plane at most of the locations (except the locations near the endpoints of the airlines) can cover at least 6 locations in its own airline in scenarios 2 and 3 ( [figure omitted; refer to PDF] ) and 10 locations in scenario 1 ( [figure omitted; refer to PDF] ). With considering that every [figure omitted; refer to PDF] we choose is larger than 0.5, the probability that a plane has no neighbor should certainly be very small. Another thing we can tell from the figures is that the probability decays to zero for large degrees. As we inform in Section 3, the number of each plane's neighbors has an upper limit since a safe distance should be kept between two planes. When a plane's degree reaches the upper limit, this means that every location covered by that plane should have a plane on it. Thus, when the upper limit is big, the probability of reaching that limit should be very small and, for the degrees beyond the maximum upper limit, it should be zero.

The peaks of Figures 7 to 9 are related mostly on the communication range and safe distance, because those two parameters decide how many locations a plane can cover; for example, plane at most of the locations (more than 50%) in scenario 1 can cover over 15 to 20 locations (counted by computer), so the peak of scenario 1 should most likely be around 15 and 20, and Figure 6 proves that, for scenarios 2 and 3, they are 10 to 20 and 15 to 22, respectively.

Figure 7: Results for scenario 2 ( [figure omitted; refer to PDF] ).

[figure omitted; refer to PDF]

Figure 8: Results for scenario 3 ( [figure omitted; refer to PDF] ).

[figure omitted; refer to PDF]

Figure 9: Results for scenario 1 with random shift ( [figure omitted; refer to PDF] ).

[figure omitted; refer to PDF]

Since, in the real world, planes cannot be exactly at the locations we draw in our scenarios, we give a random shift for every plane after each generation of planes. Then, we run the simulation again to see the deviation between our theoretical model and the real situation. The results are shown in Figures 9 to 11 and the random shift strategy is described in the following paragraph.

For each airline, we move its first plane (left most plane) a distance of [figure omitted; refer to PDF] along the airline, where [figure omitted; refer to PDF] is uniformly distributed between [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . For the second plane, we move it a distance of [figure omitted; refer to PDF] . [figure omitted; refer to PDF] has two different distributions according to whether it is at the location adjacent to the first plane's or not. If yes, [figure omitted; refer to PDF] is uniformly distributed between [figure omitted; refer to PDF] and [figure omitted; refer to PDF] to make sure the distance of the two planes is not less than [figure omitted; refer to PDF] . If no, [figure omitted; refer to PDF] has the same distribution of [figure omitted; refer to PDF] . Following this way, we move the [figure omitted; refer to PDF] th plane according to whether the [figure omitted; refer to PDF] th and [figure omitted; refer to PDF] th planes are at the adjacent locations on that airline.

From Figures 9 to 11, we can see there is only a small deviation between our model and the real situation, and it is believed to be decreasing with the ratio of [figure omitted; refer to PDF] to [figure omitted; refer to PDF] . In Figures 10 and 11, we use the same scenario with different safe distances. The shapes of the two figures are similar, but the mathematical expectation of [figure omitted; refer to PDF] in Figure 10 is nearly the double of that in Figure 11. This is because scenario can form the shape, while safe distance can decide the plane density.

Figure 10: Results for scenario 3 with random shift ( [figure omitted; refer to PDF] ).

[figure omitted; refer to PDF]

Figure 11: Results for scenario 3 with random shift ( [figure omitted; refer to PDF] ).

[figure omitted; refer to PDF]

6. Conclusion

In this paper, we introduce a model of AANET, which considers the nonignorable safe distance between planes. Based on this model, the plane's degree distribution of an arbitrary AANET is analyzed. We find that, different from other works, the degree of each plane in our model has an upper limit, which is coursed by the safe distance. Then, we get from the numeric results of our theoretical method that the peaks of the degree distribution are related mostly on the communication range and safe distance, and the probability of getting large values of degree is very small and it is zero for the degrees beyond the maximum upper limit.

For future research, we will consider simulating a network around some real-world flight paths as opposed to changing the distribution of random paths to show the utility of our method in a real-world case.

Acknowledgments

This research is supported by the National Natural Science Foundation of China (Grants nos. 61171089, 91438104, and 61302054) and Chongqing Science & Technology Commission (Grants nos. cstc2014yykfA40002 and cstc2012jjb40010).

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] E. Sakhaee, A. Jamalipour, "The global in-flight internet," IEEE Journal on Selected Areas in Communications , vol. 24, no. 9, pp. 1748-1757, 2006.

[2] Q. Vey, A. Pirovano, J. Radzik, F. Garcia, "Aeronautical Ad Hoc network for civil aviation," Communication Technologies for Vehicles , vol. 8435, of Lecture Notes in Computer Science, pp. 81-93, Springer International Publishing, 2014.

[3] M. Schnell, S. Scalise, "NEWSKY-concept for NEtworking the SKY for civil aeronautical communications," IEEE Aerospace and Electronic Systems Magazine , vol. 22, no. 5, pp. 25-29, 2007.

[4] K. Karras, T. Kyritsis, M. Amirfeiz, S. Baiotti, "Aeronautical mobile ad hoc networks," in Proceedings of the 14th European Wireless Conference, pp. 1-6, June 2008.

[5] J. P. Rohrer, A. Jabbar, E. K. Cetinkaya, E. Perrins, J. P. G. Sterbenz, "Highly-dynamic cross-layered aeronautical network architecture," IEEE Transactions on Aerospace and Electronic Systems , vol. 47, no. 4, pp. 2742-2765, 2011.

[6] J. Yan, C. Hua, C. Chen, X. Guan, "The capacity of aeronautical ad-hoc networks," Wireless Networks , vol. 20, no. 7, pp. 2123-2130, 2014.

[7] R. Albert, A.-L. Barabasi, "Statistical mechanics of complex networks," Reviews of Modern Physics , vol. 74, article 47, 2002.

[8] D. Medina, F. Hoffmann, S. Ayaz, C.-H. Rokitansky, "Feasibility of an aeronautical mobile ad hoc network over the north atlantic corridor," in Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, pp. 109-116, usa, June 2008.

[9] The Convention of International Civil Aviation Organization, Annex 2, 'rules of air', 2012

[10] B. Zheng, H.-Y. Zhang, P. Sun, G.-C. Huang, "Connectivity on one- and two-way flight routes in aeronautical Ad hoc networks," Journal of Shanghai Jiaotong University , vol. 46, no. 4, pp. 624-629, 2012.

Appendix

Appendix

See Tables 2, 3, and 4.

Table 2: Parameters of scenario 1.

  Airline  Range of [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   

1   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.6  

2   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.89  

3   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.89  

4   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.82  

5   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.95  

6   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.75  

7   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.72  

8   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.53  

9   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.65  

10   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.73  

11   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.55  

12   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.74  

13   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.69  

14   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.52  

15   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.87  

16   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.64  

17   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.77  

18   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.75  

19   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.57  

20   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.55  

21   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.51  

22   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.77  

23   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.53  

24   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.67  

25   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.74  

26   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.55  

27   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.83  

28   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.87  

29   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.96  

30   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.95  

Table 3: Parameters of scenario 2.

  Airline  Range of [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   

1   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.53  

2   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.66  

3   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.73  

4   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.73  

5   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.81  

6   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.69  

7   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.6  

8   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.53  

9   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.82  

10   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.91  

11   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.55  

12   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.56  

13   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.66  

14   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.81  

15   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.71  

16   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.79  

17   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.84  

18   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.83  

19   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.73  

20   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.91  

Table 4: Parameters of scenario 3.

  Airline  Range of [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   

1   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.86  

2   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.71  

3   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.57  

4   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.88  

5   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.74  

6   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.98  

7   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.94  

8   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.58  

9   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.91  

10   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.83  

11   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.94  

12   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.9  

13   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.75  

14   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.83  

15   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.77  

16   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.87  

17   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.82  

18   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.87  

19   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.76  

20   [figure omitted; refer to PDF]    [figure omitted; refer to PDF]   0.55