The Emergence of Scaling Law, Fractal Patterns and Self-Similarity in Wireless Networks

Background

Cellular networks have been undergoing a long history of evolution and gradually accumulated unique spatial distribution pattern, as  BSs are continually deployed to provision the ever-increasing mobile traffic in hotspots accompanied by the global popularity of smart phones and tablets. Accordingly, by taking advantage of realistic traffic records from cellular networks, we can leverage the theory of complex networks to answer what is the intrinsic evolved nature in cellular networks? We first create a spatial traffic correlation model of BSs by regarding BSs as nodes and the traffic correlation between BSs as edges.
Then, we analyze the structure and properties of this spatial traffic correlation model and derive the corresponding results in the networks. Interestingly, we discover that there exist three key properties, i.e., scale-free pattern, fractality, self-similarity, and small-world.

DATA ACQUISITION AND PREPARATION

We acquire the real measurement data from one of the biggest commercial mobile operator in China, which contains the information of traffic and BSs from a second-generation (2G) cellular network in City A and the counterpart from a third-generation (3G) cellular network in City B. Specifically, the traffic data is measured in the unit of bytes that each BS transmits to the serving users. The related traffic for City A and City B lasts 7 days and 1 day, with one-hour and half-hour granularity, respectively. Therefore, for one BS, the traffic series for City A and City B could be regarded as a vector of 168 entries and 48 entries, respectively. Meanwhile, we plot the BS deployment with the geographical landforms in Fig. 1. Moreover, the BS related information such as BS type, location area and geographic location is available as well and more details are summarized in Table I.

1

3

Fig. 1. An illustration of the deployment of base stations in two typical cities with geographical landforms, namely City A, B, respectively.

Box-covering Algorithm

As a widely used technique for characterizing fractal networks and calculating their fractal dimensions, box-covering algorithm has experienced a number of distinct versions since the generalized box-covering algorithm was introduced by Song . The random sequential (RS) box-covering algorithm  is not suitable in our work due to its low efficiency in finding the minimum number of boxes among all the possible tiling configurations. Therefore, we adopt a slightly improved algorithm  and detailed steps is shown in Algorithm. 1.

5

ANALYSIS OF DEGREE DISTRIBUTION

Degree Distribution

The spatial traffic correlation model is built in terms of the traffic loads and contributes to understanding the underlying relationship of BSs, which can not be directly observed from brief information such as locations (e.g., longitude and latitude) or BS types. We provide the fitting results of the degree distributions of City A and City B. In general, the spatial traffic correlation model points to the property of scale-free and help us to know which BSs have higher degree values. The scale-free property from the traffic load correlation model clearly demonstrates that the minority of BSs with larger degree are highly correlated with plenty of other BSs, while the other remaining BSs are only correlated with a few number of BSs.

6

IDENTIFYING INFLUENTIAL BASE STATIONS

Cellular networks have already employed macrocell BS as the signaling node, so the macrocell BSs are more suitable to be influential nodes due to their greater coverage capability and being more easily to predict the tendency of BS traffic loads. As a result, it is imperative to pick out the most important BSs so as to assign them more functions such as signaling control. Based on the theory of influence maximization in complex networks, we further employ the CI algorithm for localizing the most influential BSs.

1

Fig. 3. Performance of CI in correlation model compared with
heuristic methods (HD, HDA).

Afterwards, according to the optimal set of nodes found by the CI algorithm, we display the locations of the most influential 500 base stations of City A in the map and color codes each BS’s degree in Fig. 4 and Fig. 5. From the two figures, we observe that among the most influential base stations extracted by the CI algorithm, a large number of low-degree BSs even exhibit a greater influence than some high-degree BSs. That is to say, we should pay more attention to
those influential BSs even with low-degree, comparing with the high-degree BSs with less influence.

6

7

STRUCTURAL PROPERTIES OF THE TRAFFIC LOAD CORRELATION MODEL

FRACTAL PATTERNS

One important property that exists in many complex and real-world networks is fractality. In fractal geometry, box-covering is widely used to approximately evaluate the fractal dimension of a fractal object.

1

Fig. 6. Fractal patterns of City A and City B with the same
threshold K 0.54.

SKELETON FEATURES

Basically, skeleton is thought to be a maximum spanning tree. Thus, the skeleton of our correlated BSs network is a spanning tree connected by the most close links, whose topology can be regarded as the core of the correlated BSs network.

After tiling the skeletons with the box-covering algorithm, the number of boxes needed to cover the networks is almost identical with the original networks. The box-covering analysis results of the original network, the skeleton and the random spanning tree are provided in Fig. 7. According to the curves, the relevant results express that although the random spanning tree possesses a different statistics, the fractal dimensions of the random spanning tree and the original network are just the same. Meanwhile, the fractality of the skeleton
matches the fractality of the original correlation model very well. Hence, understanding the properties of the skeleton is of great importance for analyzing the original model.

2

 

FURTHER EXPLORATION ON SMALL-WORLD

The small-world property usually coexists with scale-free networks. Specically, small-world property refers to the average distance d scales logarithmically with the network size N . Another indispensable characteristic of small-world networks is their high clustering coeffcient.

3

We have demonstrated that the spatial traffic correlation model of BSs expresses scale-free, fractal and small-world properties simultaneously, which will further facilitate the performance analysis of complex cellular networks as well as the design of efficient networking protocols. Moreover, for a topological structure with fractality, we can  find some regularities from its special topology and irregularity, which contributes to more effective resource assignment based on dynamic BSs management. Finally, the discovery of small-world property means that, despite the large-scale feature of the traffic load correlation model, the traffic association on base stations is very compact.


  • Chao Yuan, Zhifeng Zhao, Rongpeng Li, M. Li, and Honggang Zhang, “The Emergence of Scaling Law, Fractal Patterns and Small-World in Wireless Networks,” IEEE Access, March 2017. PDF

  • Rongpeng Li, Zhifeng Zhao, Yi Zhong, Chen Qi, and Honggang Zhang, “The Stochastic Geometry Analyses of Cellular Networks with α-Stable Self-Similarity,” IEEE Trans. on Communications, March 2019.  PDF

  • Ying Chen, Rongpeng Li, Zhifeng Zhao, and Honggang Zhang, “Study on Base Station Topology in National Cellular Networks: Take Advantage of Alpha Shapes, Betti Numbers, and Euler Characteristics,” IEEE Systems Journal, Q3/Q4 2019.

  • Ying Chen, Rongpeng Li, Zhifeng Zhao, and Honggang Zhang, “Fundamentals on Base Stations in Urban Cellular Networks: From the Perspective of Algebraic Topology,” IEEE Wireless Communications Letters, April 2019.  PDF

  • Rongpeng Li, Zhifeng Zhao, Yi Zhong, Chen Qi, and Honggang Zhang, “The Stochastic Geometry Analyses of Cellular Networks with alpha-Stable Self-Similarity,” arxiv.org/abs/1709.05733v1, September 2017. PDF

  • Ying Chen, Rongpeng Li, Zhifeng Zhao, and Honggang Zhang, “On the Capacity of Wireless Networks With Fractal and Hierarchical Social Communications,” arxiv.org/abs/1708.04585, August 2017.(http://arxiv.org/abs/1708.04585) PDF

  • Ying Chen, Rongpeng Li, Zhifeng Zhao, and Honggang Zhang, “On the Capacity of Fractal Wireless Networks With Direct Social Interactions,” arXiv:1705.09751, May 27, 2017.(http://arxiv.org/abs/1705.09751) PDF

  • Rongpeng Li, Zhifeng Zhao, Jianchao Zheng, Chengli Mei, Yueming Cai, and Honggang Zhang, “The Learning and Prediction of Application-level Traffic Data in Cellular Networks,” IEEE Trans. Wireless Communications, March 2017. PDF

  • Zhifeng Zhao, Meng  Li, Rongpeng Li, and Yifan Zhou, “Temporal-Spatial Distribution Nature of Traffic and Base Stations in Cellular Networks,” IET Communications, August 2017.

  • Chen Qi, Zhifeng Zhao, Rongpeng Li, and Honggang Zhang, “Characterizing and Modeling Social Mobile Data Traffic in Cellular Networks,” 2016 IEEE 83rd Vehicular Technology Conference (VTC-Spring 2016), Nanjing, May 2016. PDF

 

Leave a Reply

Your email address will not be published. Required fields are marked *