Emergence of Scaling Law and Fractal 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, and small-world.

Big 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).

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

 

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. 


[Reference]

  1. 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)

  2. Ying Chen, Rongpeng Li, Zhifeng Zhao, and Honggang Zhang, “On the Capacity of D2D Social Networks With Fractal Communications,” 25th International Conference on Telecommunications (ICT 2018), Saint Malo, France, June 2018. (Accepted)

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

  4. 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.(https://arxiv.org/abs/1708.04585) (PDF)

  5. 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)

  6. 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)

  7. 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. PDF

  8. 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)