# BiSON: A Bioinspired Self-Organizing Network for Dynamic Auto-Configuration in 5G Wireless

Authors: Abhishek Roy; Navrati Saxena; Bharat J. R. Sahu; Sukhdeep Singh
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Emerging 5G wireless networks are expected to herald significant transformation in industrial applications, with improved coverage, high data rates, and massive device capacity. However, the introduction of 5G wireless makes the network configuration, management, and planning extremely challenging. For efficient network configuration, every cell needs to be allocated a particular Physical Cell Identifier (PCID), which is unique in its vicinity. Wireless standards (e.g., 3GPP) typically specify a limited number of PCIDs. However, the number of cells in 5G Ultradense Networks (UDN) is expected to significantly outnumber these limited PCIDs. Hence, these PCIDs need to be efficiently allocated among the myriad of cells, such that two cells which are neighbors or neighbor’s neighbor are assigned with different PCIDs. This complicated network configuration problem becomes even more complex by dynamic introduction and removal of 5G small cells (e.g., micro, femto, and pico). In this paper, we introduce BiSON, a new Bioinspired Self-Organizing Solution for automated and efficient PCID configuration in 5G UDN. Using two different extensions, namely, “always near-optimal” and “heuristic,” we explain near-optimal and dynamic auto-configuration in computationally feasible time, with negligible overhead. Our extensive network simulation experiments, based on actual 5G wireless trials, demonstrate that the proposed algorithm achieves better optimality (minimum PCIDs in use) than earlier works in a reasonable computational complexity.


---

## Body

## 1. Introduction

Next generation 5G wireless [1] envisions revolutionizing industrial applications, like robotics and smart grids, by providing manifold improvement in latency, data rates, and device capacity. While existing wireless networks are mostly designed for human-centric communications, emerging 5G wireless aims to provide default support to Machine-to-Machine (M2M) communications and Internet-of-Things (IoT). Network densification [1] is already identified as a key factor in meeting explosive device growth, with high spectral efficiency. However, commercial roll out of 5G Ultradense Networks (UDN), consisting of a wide number of relatively small cells, makes the network configuration and management extremely complex. Moreover the dynamic introduction and removal of small 5G cells make it almost impossible to manually configure and manage the already complex networks. Thus, automated configuration and management are considered as two integral features of emerging 5G wireless systems. Self-Organizing Networks (SON) [2] are gradually becoming popular by offering self-configuration, self-optimization, and self-healing of cellular networks, thereby reducing both capital expenditure (capex) and operating expenditure (opex) in network planning, deployment, and operation.Figure1 demonstrates a 5G UDN, connected with SON server for self-configuration and management. Physical Cell Identifier (PCID) is one of the most important cell configuration parameters. Without an assigned PCID, the mobile device cannot even detect the cell, thus failing to setup any radio communication. The number of available PCIDs is generally limited. While the 5G standards are yet to be defined, current 3GPP specification (Self-configuration and self-optimizing network use cases and solutions. 3GPP TS 36.902, 2008.) allows only 504 PCIDs for network configuration. This raises a significant new challenge in emerging 5G wireless configuration, as the number of cells in 5G UDN is expected to be more than the available PCIDs by several multitudes. Thus, an efficient, dynamic, and optimal PCID configuration among the myriad of 5G cells is of utmost important. Collision-free and confusion-free (Self-configuration and self-optimizing network use cases and solutions. 3GPP TS 36.902, 2008.) are two necessary constraints associated with PCID allocation [3].(1)
The connotation of collision-free is “two neighboring cells should not have the same PCID”. An illustration of intricacy arising from colliding PCID is illustrated here: received signals from available base stations (BSs) are monitored by mobile user equipment (UE). Subsequently, handover decisions between two BSs, and potential handover candidate BS selections are performed based on this signal measurement. In the case of identical PCIDs, the cells with weaker signals are discarded by the UE, thus a potential handover candidate recognition fails. Ultimately, when the signal of the potential cell gets stronger than the current cell, the UE tries to use the stronger signal, and the connection fails (EUTRAN Overall Description. 3GPP TS 36.300. 2008).(2)
The confusion-free,, on the other hand, mandates that a cell should not have two neighbors configured with the same PCID. Every BS maintains an automated neighbor relation (ANR) table, containing the information of neighboring cells for possible handover. This includes PCID of potential handover candidates. For a BS with two neighboring cells having identical PCID, the BS keeps only one of those cells in the ANR table. Hence, handover to the cell whose PCID is not in the ANR table fails.Figure 1
5G ultradense network with SON.A massive number of heterogenous cells in 5G are bound to increase the complexity of the already complicated problem. A survey of the recent research works in self-organization and management [4] reveals that a large number of academic researches and international projects reflect the importance of PCID allocation with self-configuration, plug-and-play, self-optimization, self-healing (in case of failure), and automated network management. This motivates us to look into the dynamic self-configuration problem in next generation of 5G wireless networks. In particular, we take a step forward to answer the following fundamental questions. (a) How can we define optimal self-configuration problem in 5G UDN? (b) What is the complexity of optimal self-configuration? (c) How to design feasible, near-optimal solutions for self-configuration in 5G UDN. (d) Is the efficiency vs. overhead trade-off in the solutions enough for real implementation? In this paper we will discuss our answers to these fundamental questions. More specifically our contributions are as follows:(1)
We first discuss and formulate the optimal PCID configuration problem in 5G UDN. Subsequently, we prove that the global optimal solution is computationally complex and NP-complete.(2)
We design a new customized genetic algorithm (GA) to model the optimal PCID configuration problem. Our strategy iteratively reduces the number of PCID using a set of new operations called Fusion Operation. We use the concept of virtual cell or virtual cell cluster [5] to resolve the possible future collisions and confusions, arising from dynamic, new small cell installations (e.g., plug-and-play of 5G indoor cells).(3)
Next, we propose biologically inspired SON (BiSON), a genetic algorithm (GA) based solution which iteratively explores the search space and improves the quality of the candidate solutions in every iteration. BiSON algorithm achieves a near-optimal solution in computationally feasible time.(4)
We perform detailed stochastic modeling and analysis of BiSON to point out the associated convergence speed.(5)
Rigorous simulation of 5G UDN using 5G channel models and RF parameters derived from actual field trials demonstrate the efficiency of our solution. The results dynamically show53%~55% improvement in auto-configuration more than previous works [3, 5] in computationally feasible time.The remainder of the paper is organized as follows. Section2 reviews the major existing works in automated self-configuration of cellular networks. Dynamic, optimal PCID allocation problem and its complexity are illustrated in Section 3. Section 4 details our proposed GA modeling schemes involving a new chromosome design and fitness evaluation. We describe our proposed algorithm which efficiently uses GA to obtain the near-optimal solution in Section 5. Subsequently, we also analyze the convergence and speed of our proposed algorithm in Section 6. Simulation results in Section 7 substantiate the dynamism and efficiency of our scheme. Finally, Section 8 concludes the paper.


## 2. Existing Works on Self-Configuration in Cellular Wireless

Table1 shows the summary of major existing works on SON and bioinspired approaches in wireless networks. Geolocation based allocation [8, 9], game-theory based minimum collision assignment [7], and graph coloring optimization [3, 4] are some of the PCID conflict resolution approaches available in literature. SON is gradually coming up as the panacea for the complex configuration and management challenges of 5G UDN [27]. LTE is the first technology to use the SON features, with inherent support of ANR detection. A recent review on SON [2] demonstrates the wide number of industrial and academic research activities on autonomic network configuration and self-management. SON is also providing promises for autonomous capacity enhancement, handover (HO) optimization, interference control, antenna downtilt, and radio resource allocation (RRA) [2, 6]. Similarly, SOCRATES (Socrates—FP7, http://www.fp7-socrates.eu, (October, 2018).) and E32 are major joint initiatives for the design and development of self-configurations, optimization, and healing of wireless networks. Research work of [10] provides the technique for selecting the Key Performance Indicators (KPIs) used as SON function inputs under various network conditions. Authors in [11] focused on self-healing characteristic of SON. They targeted fault diagnosis function of self-healing and proposed an ensemble learning based system for the same. Another recent survey [12] focuses on machine learning algorithms applied to SON in terms of learning solutions and use cases. It also compares various machine learning algorithms on the basis of different SON metrics.Table 1
Major works.
SON: key challenges and solution  Network management RRA, HO, interference, antenna downtilt, & load management [2]  Capacity enhancement RRA & antenna downtilt [6]  Graph coloring Square graph coloring for PCI [3, 4]  Game theory Game theoretic minimum collisions assignment [7]  Location based PCI Geo-location based PCI conflict resolution [8, 9]  KPI Selection Method to automatically select KPIs for self-healing functions [10]  Fault diagnosis (self-healing) Ensemble learning based system [11]  Survey Machine learning algorithms applied to SON in last 15 years [12]  Bio-inspired solution: applications in wireless network  Survey Networking solutions [13, 14], vehicular network routing [15]  Wireless network Resource scheduling [16, 17], cell planning [18], load balance [19]  WSN Routing [20], clustering, and energy harvesting [21], self-synchronization techniques [22], security [23]Bioinspired solutions are a class of algorithms imitating some biological mechanisms to solve complex optimization problems. An extensive survey of bioinspired solution for the communications network is presented in [13, 15]. Bioinspired solutions have been used in wireless networks for scheduling and resource allocation [16, 17], optimal cell planning [18], BS deployment [18], and load balancing [19]. Similarly, ant-colony based optimization [16], bee-colony based optimization [19], and genetic algorithms [28] are the major bioinspired tools used for learningtroubleshooting fuzzy rules and optimization in self-healing wireless networks. On the other hand, wireless sensors networks use bioinspired solution for optimal clustering [21], routing path selection, and energy efficient coverage scheduling [20]. Reference [14] provides an overview of researchers working on solutions related to bioinspired networking along with practical relevance and capabilities of bioinspired networking. Authors in [22] present an idea of utilizing self-synchronization techniques inculcated from biological systems for optimal wireless sensor network decisions. Bioinspired trust and reputation model for WSN, i.e., BTRM-WSN [23], is an ant-colony system based model providing reputation and trust in WSNs to assure security in WSNs.A close look into most of the existing literature of cell configurations reveals that most of the existing solutions perform some local adjustments, involving PCID updates in only one of the conflicting cells. As the algorithms are not designed for minimizing collision and confusion, the resulting solutions do not guarantee any avoidance of consecutive PCID conflicts after the commercial deployment, i.e., during the network’s operational phase. These solutions often do not even guarantee if a valid configuration could be at all found or if the changes will result in oscillating reconfigurations through large parts of 5G UDN. Moreover, the manifold increase in Quality of Experience (QoE) requirements and the increased network complexity require more efficient and low overhead PCID distribution in 5G UDN. This motivates us to look for an efficient, bioinspired solution for the complex PCID allocation problem.


## 3. Complexity of Optimal PCID Allocation

We consider a dense 5G wireless network, with macrocells, small cells, and the SON server. For formulating the optimal PCID assignment problem, we assumeΥ cells and ℘ available PCIDs. As Υ>℘, more than one cell need to have the same PCID. However, assignment of the same PCID to any two neighboring cells creates a collision in frequency. Similarly, the assignment of the same PCID to multiple cells which are neighbor’s neighbor leads to a confusion in managing measurement report during handover. Based on this discussion, we can now define the optimal PCID allocation problem in 5G UDN as follows.Given a 5G network topology with a set ofΥ cells and ℘ PCIDs, the optimal PCID allocation problem is to allocate the minimum number of PCIDs into the set of all cells, so that the entire network is (i) collision-free and (ii) confusion-free.Note that the collision-free and confusion-free constraints need to be maintained not only during the initial assignment, but also during dynamic introduction (plug-and-play) and removal of new small cells, without compromising the network performance. Unfortunately, this dynamic PCID allocation problem turns out to be NP-hard [29]. We prove this by mapping “vertex k-coloring Problem” [30]— a well-known NP-complete problem [29] to our PCID allocation problem. The vertex coloring problem can be defined as follows:For a graphG(V,E), withVvertices andEedges, vertexk-coloring problem is an assignment of one of thekavailable colors to each vertex inV, in such a way that no edge connects two identically colored vertices.Now we map the vertexk-coloring to our optimal PCID allocation problem as follows.(i)
Map the set ofk colors to ℘ PCID, i.e., k↦℘.(ii)
Map the set ofV vertices in the graph to set of Υ cells, i.e., V↦Υ.(iii)
Map the set ofE edges to the combination of both “collision-free” and “confusion-free” property, i.e., E↦collision-free or confusion-free.(iv)
Map the graphG to the entire 5G UDN, i.e., G↦5G UDN.The complexity of the problem is similar to the problem offinding number ofw-length words, over an alphabet ofkletters where each letter appears in each word at least once. As mentioned in [31], the complexity and search space are bounded by(1)∏w,k=∑i=0k-1kkik-iwTable 2 depicts mapping between PCID allocation and vertex k-coloring. The goal of the solution is to find the lowest k that results in a valid coloring. This k is often called the chromatic number [30]. Thus, we can now say thatthe dynamic PCID allocation problem in next generation 5G wireless UDN is NP-hard with exponential complexity. The exponential complexity of (1) compels us to look for a near-optimal solution in computationally feasible time. In the following section, we introduce our new GA-based solution to capture, model, and analyze the self-configuration of 5G cells.Table 2
Mapping between PCID allocation and Vertex k-coloring.
Vertex k-coloring Optimal PCID allocation  Set ofk color Set of℘ PCID  Set of verticesV Set ofΥ cells  Set ofE edges Collision and confusion free  GraphG 5G UDN topology


## 4. Modeling with Genetic Algorithm

In this section, we introduce the general idea of GA. Subsequently, we model our PCID allocation problem into customized GA concept.


### 4.1. Genetic Algorithms

Bioinspired algorithms [32] are gradually emerging as one of the most powerful methods to solve many real world optimization problems. It mimics our mother nature to solve the practical problems. Evolutionary-GA [32] is such a bioinspired approach, which mimics the Darwinian evolutionary principles, likeSurvival of the fittest andNatural Selection, to solve complex combinatorial problems. Evolutionary-GAs are based on the following major steps:(1)
Theinitialization step involves mapping the real world problem into a set of strings where individual strings are often termed aschromosomes orgenotypes, and the entire set is referred to aspopulation.(2)
TheSelection step probabilistically selects a subset of the population based on somefitness value. This fitness value actually determines how good or fit that particular solution is.(3)
The genetic operatorcrossover probabilistically selects two chromosomes for breeding and obtaining a new “child” chromosome for the next generation. The objective is to create new and diverse solution space. The genetic operator,mutation, on the other hand, probabilistically mutates (changes) a chromosome for obtaining a new chromosomes. Mutation attempts to avoid the possible local optimum values by sudden change (alteration) of chromosomes. While iterating from one generation to the next, the algorithms preserve the fittest (best) chromosome of the present generation [32]. However, mutation is an optional operation depending on the problem domain.The above-mentioned steps are continued until a satisfying solution is obtained or a maximum number of iterations are completed. With this inspiration from evolutionary-GA, we designBiSON, for an automatic and near-optimal PCID configuration in 5G UDN.


### 4.2. Chromosome Initialization

In order to capture and analyze the 5G UDN, containing a myriad of small cells, we introduce a new design of chromosome. Unlike traditional GAs which use multirow chromosomes, our customized GA uses multicolumn and multirow chromosomes. Every column in a chromosome represents an individual cell in 5G UDN, and every row represents individual PCID allocation status for that cell. The values of each gene in the chromosome represent the “collision” and “confusion” between small cells arising from the configuration. Each gene in the chromosome can have one of the three values:{ł,ø,χ}. We introduce the following rule for theInitialization of chromosome:(i)
If PCIDρ is assigned to the ith cell, then set the gene(ρ,i) to ł.(ii)
If the assignment of PCIDρ to the cell j violates the collision-free or confusion-free constraint, then the gene(ρ,j) is set to ø.(iii)
Further, if assigning cellj with the same PCID ρ does not violate any constraint, then set the entry gene(ρ,j) to χ.First we start with a universally valid allocation by configuring celli with the PCID i. This allocation is always valid, as in any topology, n cells can always be configured by using n unique PCIDs, without violating collision-free and confusion-free constraints. In our chromosome, this relates to setting the diagonal gene(i,i)=ł. Then for any pair of cells i and j, we set gene(ρ,j)=ø, if and only if ρ=i andcell (i) andcell (j) are either neighbors or neighbors’ neighbors. All the other remaining entries of row ρ are set to χ. Based on this discussion, we can now mathematically formulate the configuration rules as(2)genei,i=ł;geneρ,j=ø,iffρ=i&collisionorconfusion;χ,otherwiseAs an illustrative example, we represent a topology with 8 small cells, shown in Figure 2(a). Figure 3 represents the initial PCID allocation for the topology in Figure 2(a) where every cell is assigned with a unique PCID. Now, the optimal PCID allocation boils down to the minimization of the number of rows in the chromosome, as each row represents a unique PCID.Figure 2
(a) Example cells with PCID. (b) PCID confusion with new cell installation. (c) Virtual cell for PCID allocation.
(a) (b) (c)Figure 3
Initial chromosome for topology in Figure2(a).


### 4.3. Updating Initial Chromosome

Dynamic installation (e.g., plug-and-play) of new small cells between existing cells might result in conflict in PCID allocations. This raises a significant challenge, as the commercial roll out of 5G UDN is expected to be carried out gradually in an incremental manner (i.e., gradual installations of new small cells or repeaters over the time). In order to resolve this challenge, we update the initial chromosome to eliminate such configuration conflicts, expected to come up in near future. As shown in Figure2(a), satisfying initialization steps, initially both cell 4 and cell 8 can be assigned the same PCID. However, as shown in Figure 2(b), a potential problem arises if cell 9 is added in between cells 4 and 8. As a result, either of the two neighbors needs to change their current PCID to meet the “confusion-free” condition for cell 9. In Figure 2(c), we show the process of avoiding such implicit PCID conflicts with the concept of virtual cell or virtual cell cluster following theUpdate rules, mentioned below:(i)
Ifgene(ρ,j)=χ in initial chromosome, then calculate distance ð between cell ρ and cell j.(ii)
Any entrygene(ρ,j) is set to ø, if ð(i,j)≤ðr, Otherwise, gene(ρ,j) is set to χ,whereðr represents the cell radius of specific cell or the size of cell cluster in the unit of cell radius, defined in the SON server. Figure 4 shows the updated chromosome after applying update rules on chromosome in Figure 3. Since cell 4 and cell 8 result in PCID confusion, entry χ in both (4,8) and (8,4) is now replaced by ø.Figure 4
Updated chromosome for topology in Figure2(a).


### 4.4. Fitness Evaluation and Candidate Solutions

Since the number of rows represents the number of PCID allocation, the lower number of rows represents better solution. In order to minimize the number of rows, we now introduceFusion Operation (FO) between two rows. Fusion of two rows is permitted, only when assigning the same PCID to both cells, which does not create an invalid assignment; i.e., the two cells are not neighbors or neighbors’ neighbor. Representing the FO by “⨝”, mathematically we enumerate the FO rules as follows:(i)
Fusion of two rows is not valid if any column in one row is set toø and the corresponding column in other row is set to ł.(ii)
If fusion is allowed between two rows, then the set of rules given below determine the resultant row after FO:(3)ł⨝χ=ł;ł⨝ł=ł;ø⨝χ=ø;ø⨝ø=ø;χ⨝χ=χ;ł⨝ø=Illegal;(iii)
Fusion rules mentioned in (i) and (ii) will be repeated for all possible rows in chromosome till fusion is allowed, i.e., until the fusion between the rows results in “Illegal”.Referring to our original example in Figure2(a), with initial chromosome in Figure 3, a valid set of FOs is FO(1,5), FO(2,6), FO(3,7), and FO(4,8). Chromosome in Figure 5 demonstrates the result of these FOs. It is clear that the rows of chromosome in Figure 5 cannot support further FO. Thus, we can conclude that the given 5G UDN, (shown in Figure 2(a)), could be optimally configured using four unique PCIDs with the combination of cells (1,5); (2,6); (3,7); and (4,8). Furthermore, let us also consider FO over the updated chromosome in Figure 4 with concept of virtual cell in Figure 2(c). Chromosome in Figure 6 delineates the result of similar FO applied over the chromosome in Figure 5. Different from Fusion Operations on chromosome in Figure 5, the same 5G UDN could be allocated with six unique PCIDs, with the combination of cells (1,5); (2,6); (3,7); 4 and 8. This results from the fact that now cell 4 and cell 8 are configured with unique PCID, as FO(4,8) is not permitted according to FO rules. At the end of the FOs, the remaining set of rows provides a viable candidate solution for the PCID configuration problem.Figure 5
Chromosome afterFO in sequence (1, 5), (2, 6), (3, 7), (4, 8) without update rule.Figure 6
Chromosome afterFO in sequence (1, 5), (2, 6), (3, 7), (4, 8) with update.


## 4.1. Genetic Algorithms

Bioinspired algorithms [32] are gradually emerging as one of the most powerful methods to solve many real world optimization problems. It mimics our mother nature to solve the practical problems. Evolutionary-GA [32] is such a bioinspired approach, which mimics the Darwinian evolutionary principles, likeSurvival of the fittest andNatural Selection, to solve complex combinatorial problems. Evolutionary-GAs are based on the following major steps:(1)
Theinitialization step involves mapping the real world problem into a set of strings where individual strings are often termed aschromosomes orgenotypes, and the entire set is referred to aspopulation.(2)
TheSelection step probabilistically selects a subset of the population based on somefitness value. This fitness value actually determines how good or fit that particular solution is.(3)
The genetic operatorcrossover probabilistically selects two chromosomes for breeding and obtaining a new “child” chromosome for the next generation. The objective is to create new and diverse solution space. The genetic operator,mutation, on the other hand, probabilistically mutates (changes) a chromosome for obtaining a new chromosomes. Mutation attempts to avoid the possible local optimum values by sudden change (alteration) of chromosomes. While iterating from one generation to the next, the algorithms preserve the fittest (best) chromosome of the present generation [32]. However, mutation is an optional operation depending on the problem domain.The above-mentioned steps are continued until a satisfying solution is obtained or a maximum number of iterations are completed. With this inspiration from evolutionary-GA, we designBiSON, for an automatic and near-optimal PCID configuration in 5G UDN.


## 4.2. Chromosome Initialization

In order to capture and analyze the 5G UDN, containing a myriad of small cells, we introduce a new design of chromosome. Unlike traditional GAs which use multirow chromosomes, our customized GA uses multicolumn and multirow chromosomes. Every column in a chromosome represents an individual cell in 5G UDN, and every row represents individual PCID allocation status for that cell. The values of each gene in the chromosome represent the “collision” and “confusion” between small cells arising from the configuration. Each gene in the chromosome can have one of the three values:{ł,ø,χ}. We introduce the following rule for theInitialization of chromosome:(i)
If PCIDρ is assigned to the ith cell, then set the gene(ρ,i) to ł.(ii)
If the assignment of PCIDρ to the cell j violates the collision-free or confusion-free constraint, then the gene(ρ,j) is set to ø.(iii)
Further, if assigning cellj with the same PCID ρ does not violate any constraint, then set the entry gene(ρ,j) to χ.First we start with a universally valid allocation by configuring celli with the PCID i. This allocation is always valid, as in any topology, n cells can always be configured by using n unique PCIDs, without violating collision-free and confusion-free constraints. In our chromosome, this relates to setting the diagonal gene(i,i)=ł. Then for any pair of cells i and j, we set gene(ρ,j)=ø, if and only if ρ=i andcell (i) andcell (j) are either neighbors or neighbors’ neighbors. All the other remaining entries of row ρ are set to χ. Based on this discussion, we can now mathematically formulate the configuration rules as(2)genei,i=ł;geneρ,j=ø,iffρ=i&collisionorconfusion;χ,otherwiseAs an illustrative example, we represent a topology with 8 small cells, shown in Figure 2(a). Figure 3 represents the initial PCID allocation for the topology in Figure 2(a) where every cell is assigned with a unique PCID. Now, the optimal PCID allocation boils down to the minimization of the number of rows in the chromosome, as each row represents a unique PCID.Figure 2
(a) Example cells with PCID. (b) PCID confusion with new cell installation. (c) Virtual cell for PCID allocation.
(a) (b) (c)Figure 3
Initial chromosome for topology in Figure2(a).


## 4.3. Updating Initial Chromosome

Dynamic installation (e.g., plug-and-play) of new small cells between existing cells might result in conflict in PCID allocations. This raises a significant challenge, as the commercial roll out of 5G UDN is expected to be carried out gradually in an incremental manner (i.e., gradual installations of new small cells or repeaters over the time). In order to resolve this challenge, we update the initial chromosome to eliminate such configuration conflicts, expected to come up in near future. As shown in Figure2(a), satisfying initialization steps, initially both cell 4 and cell 8 can be assigned the same PCID. However, as shown in Figure 2(b), a potential problem arises if cell 9 is added in between cells 4 and 8. As a result, either of the two neighbors needs to change their current PCID to meet the “confusion-free” condition for cell 9. In Figure 2(c), we show the process of avoiding such implicit PCID conflicts with the concept of virtual cell or virtual cell cluster following theUpdate rules, mentioned below:(i)
Ifgene(ρ,j)=χ in initial chromosome, then calculate distance ð between cell ρ and cell j.(ii)
Any entrygene(ρ,j) is set to ø, if ð(i,j)≤ðr, Otherwise, gene(ρ,j) is set to χ,whereðr represents the cell radius of specific cell or the size of cell cluster in the unit of cell radius, defined in the SON server. Figure 4 shows the updated chromosome after applying update rules on chromosome in Figure 3. Since cell 4 and cell 8 result in PCID confusion, entry χ in both (4,8) and (8,4) is now replaced by ø.Figure 4
Updated chromosome for topology in Figure2(a).


## 4.4. Fitness Evaluation and Candidate Solutions

Since the number of rows represents the number of PCID allocation, the lower number of rows represents better solution. In order to minimize the number of rows, we now introduceFusion Operation (FO) between two rows. Fusion of two rows is permitted, only when assigning the same PCID to both cells, which does not create an invalid assignment; i.e., the two cells are not neighbors or neighbors’ neighbor. Representing the FO by “⨝”, mathematically we enumerate the FO rules as follows:(i)
Fusion of two rows is not valid if any column in one row is set toø and the corresponding column in other row is set to ł.(ii)
If fusion is allowed between two rows, then the set of rules given below determine the resultant row after FO:(3)ł⨝χ=ł;ł⨝ł=ł;ø⨝χ=ø;ø⨝ø=ø;χ⨝χ=χ;ł⨝ø=Illegal;(iii)
Fusion rules mentioned in (i) and (ii) will be repeated for all possible rows in chromosome till fusion is allowed, i.e., until the fusion between the rows results in “Illegal”.Referring to our original example in Figure2(a), with initial chromosome in Figure 3, a valid set of FOs is FO(1,5), FO(2,6), FO(3,7), and FO(4,8). Chromosome in Figure 5 demonstrates the result of these FOs. It is clear that the rows of chromosome in Figure 5 cannot support further FO. Thus, we can conclude that the given 5G UDN, (shown in Figure 2(a)), could be optimally configured using four unique PCIDs with the combination of cells (1,5); (2,6); (3,7); and (4,8). Furthermore, let us also consider FO over the updated chromosome in Figure 4 with concept of virtual cell in Figure 2(c). Chromosome in Figure 6 delineates the result of similar FO applied over the chromosome in Figure 5. Different from Fusion Operations on chromosome in Figure 5, the same 5G UDN could be allocated with six unique PCIDs, with the combination of cells (1,5); (2,6); (3,7); 4 and 8. This results from the fact that now cell 4 and cell 8 are configured with unique PCID, as FO(4,8) is not permitted according to FO rules. At the end of the FOs, the remaining set of rows provides a viable candidate solution for the PCID configuration problem.Figure 5
Chromosome afterFO in sequence (1, 5), (2, 6), (3, 7), (4, 8) without update rule.Figure 6
Chromosome afterFO in sequence (1, 5), (2, 6), (3, 7), (4, 8) with update.


## 5. BiSON: Biologically Inspired Approach for Optimal PCID Allocation

In this section, we introduce our proposed near-optimal PCID configuration algorithm, i.e., BiSON. Subsequently, we also provide two different extensions of BiSON for dynamic introduction and removal of 5G small cells.


### 5.1. Randomized BiSON Algorithm

The flow of BiSON is demonstrated in Figure7. The BiSON algorithm follows the steps as mentioned below:(1)
Based on the Neighbor Relation Table (NRT) of ANR in SON server, a chromosomeCMinit can be initialized usinginitialization rules, and followed byUpdate rules, as discussed in Section 4. Let r represent the total number of rows in CMinit.(2)
Let any chromosomeIi represent r rows in CMinit in any specific order. An initial generation, of size λ, contains randomly generated permutations of the set of r rows in the initial chromosome mathematically, if I→(0) denote the initial generation, then,(4)I→0=I10,I20,…,Iλ0,whereIi0=…Ri0,…&Ii0=r(3)
At each iterationt do the following with the current generation:
(a)
Genetic Operation (G): Probabilistically select two rows Rp and Rq from every chromosome Ii. Generate λ offspring by swapping the selected rows. Now, the generation has 2λ chromosome.(b)
Fitness Evaluation: Perform FO over the sequence ofr rows belonging to each permutation Ii and obtain 2λ candidate solutions. Evaluate the fitness value of each candidate solution. The fitness function is formulated as f(Ii(t))=1/|Ii(t)|, where |Ii(t)| represents the cardinality of set Ii(t). Since the number of rows represents the number of PCID allocation, the lower number of rows represents better solution.(c)
Reproduction (R): Probabilistically, select λ best individual (chromosome) for the new generation I→(t+1). Mathematically, we can say that(5)I→t+1=RGI→t(d)
Store optimal permutationIopt(t+1) from the set I→(t+1) and optimal individual Iopt(t).(4)
Stopping Criteria: The stopping criteria are number of maximum iterationTmax. If Tmax number of iteration is complete, stop the execution, else repeat step (3).Figure 7
Proposed BiSON algorithm.In step(3), the algorithm gradually explores the search spaces and stores the λ best chromosome. Thus, at every iteration, the algorithm tries to improve its candidate solutions. At the end of the algorithm, the chromosome Iopt∈I→(Tmax), with the least number of rows, is selected as the near-optimal PCID allocation strategy. The number of rows, Ropt∈Iopt, represents the number of PCIDs needed to allocate in the 5G UDN with the collision-free and confusion-free constraints.


### 5.2. Dynamic PCID Allocation

New 5G small cells are added to and removed from the industrial network dynamically. Hence, the BiSON algorithm needs periodic re-execution to accept the dynamic inclusion of small cells. We present two distinct extensions which offer compromise between optimal solution and computation complexity. Figure8 shows the flowchart for dynamic PCID allocation algorithm.(1)
Always near-optimal (ANO). The topology of the 5G UDN changes with the addition or removal of single or multiple cells. The BiSON algorithm is executed to obtain the new near-optimal PCID allocation for the new topology. This procedure always provides a new near-optimal PCID allocation. However, it also suffers from more computational overhead, arising from the frequent execution of the entire algorithm.(2)
Heuristic. Initial execution of BiSON during network installation results in specific near-optimal PCID allocation with ROPT different PCIDs. After the initial execution, (℘-ROPT) PCIDs will remain unallocated. When new cells are added, the algorithm allocates a new PCID from this set of (℘-ROPT) unallocated PCIDs, until this set becomes empty. When there is no free PCID, BiSON is re-executed. Comparing with “ANO”, the heuristic provides suboptimal solution, at the cost of lower computational overhead.Figure 8
Dynamic PCID allocation algorithm.On the other hand, the removal dynamics of any cell is quite simple. During removal of cells, both “ANO” and “Heuristic” algorithm check for another small cell with the same PCID. If such a cell does not exist, both approaches add the PCID to the free PCID list.


## 5.1. Randomized BiSON Algorithm

The flow of BiSON is demonstrated in Figure7. The BiSON algorithm follows the steps as mentioned below:(1)
Based on the Neighbor Relation Table (NRT) of ANR in SON server, a chromosomeCMinit can be initialized usinginitialization rules, and followed byUpdate rules, as discussed in Section 4. Let r represent the total number of rows in CMinit.(2)
Let any chromosomeIi represent r rows in CMinit in any specific order. An initial generation, of size λ, contains randomly generated permutations of the set of r rows in the initial chromosome mathematically, if I→(0) denote the initial generation, then,(4)I→0=I10,I20,…,Iλ0,whereIi0=…Ri0,…&Ii0=r(3)
At each iterationt do the following with the current generation:
(a)
Genetic Operation (G): Probabilistically select two rows Rp and Rq from every chromosome Ii. Generate λ offspring by swapping the selected rows. Now, the generation has 2λ chromosome.(b)
Fitness Evaluation: Perform FO over the sequence ofr rows belonging to each permutation Ii and obtain 2λ candidate solutions. Evaluate the fitness value of each candidate solution. The fitness function is formulated as f(Ii(t))=1/|Ii(t)|, where |Ii(t)| represents the cardinality of set Ii(t). Since the number of rows represents the number of PCID allocation, the lower number of rows represents better solution.(c)
Reproduction (R): Probabilistically, select λ best individual (chromosome) for the new generation I→(t+1). Mathematically, we can say that(5)I→t+1=RGI→t(d)
Store optimal permutationIopt(t+1) from the set I→(t+1) and optimal individual Iopt(t).(4)
Stopping Criteria: The stopping criteria are number of maximum iterationTmax. If Tmax number of iteration is complete, stop the execution, else repeat step (3).Figure 7
Proposed BiSON algorithm.In step(3), the algorithm gradually explores the search spaces and stores the λ best chromosome. Thus, at every iteration, the algorithm tries to improve its candidate solutions. At the end of the algorithm, the chromosome Iopt∈I→(Tmax), with the least number of rows, is selected as the near-optimal PCID allocation strategy. The number of rows, Ropt∈Iopt, represents the number of PCIDs needed to allocate in the 5G UDN with the collision-free and confusion-free constraints.


## 5.2. Dynamic PCID Allocation

New 5G small cells are added to and removed from the industrial network dynamically. Hence, the BiSON algorithm needs periodic re-execution to accept the dynamic inclusion of small cells. We present two distinct extensions which offer compromise between optimal solution and computation complexity. Figure8 shows the flowchart for dynamic PCID allocation algorithm.(1)
Always near-optimal (ANO). The topology of the 5G UDN changes with the addition or removal of single or multiple cells. The BiSON algorithm is executed to obtain the new near-optimal PCID allocation for the new topology. This procedure always provides a new near-optimal PCID allocation. However, it also suffers from more computational overhead, arising from the frequent execution of the entire algorithm.(2)
Heuristic. Initial execution of BiSON during network installation results in specific near-optimal PCID allocation with ROPT different PCIDs. After the initial execution, (℘-ROPT) PCIDs will remain unallocated. When new cells are added, the algorithm allocates a new PCID from this set of (℘-ROPT) unallocated PCIDs, until this set becomes empty. When there is no free PCID, BiSON is re-executed. Comparing with “ANO”, the heuristic provides suboptimal solution, at the cost of lower computational overhead.Figure 8
Dynamic PCID allocation algorithm.On the other hand, the removal dynamics of any cell is quite simple. During removal of cells, both “ANO” and “Heuristic” algorithm check for another small cell with the same PCID. If such a cell does not exist, both approaches add the PCID to the free PCID list.


## 6. Modeling and Convergence Analysis of BiSON

In this section, we discuss the stochastic behavior of BiSON algorithm, show its convergence to optimality and subsequently, and analyze asymptotic behavior.


### 6.1. Markov Chain Modeling

The BiSON algorithm, mentioned in Section5.1, shows that at any iteration t, the chromosome-set I→(t) depends only on the chromosome-set of the previous iteration I→(t-1). Hence, mapping every chromosome-set to the corresponding state, the underlying process could be modeled as a Discrete Time Markov Chain [33, 34], with state space Ψ. If Pr represents the corresponding state probability, then mathematically we can say Pr[I→(t)|I→(0),…,I→(t-1)]=Pr[I→(t)|I→(t-1)]. Defining ΨOPT as the globally optimal state set, if any current optimal chromosome Ii(t), at iteration t, is the globally optimal chromosome (fittest), then Ii(t)∈ΨOPT. Following the stopping criteria of BiSON algorithm, as mentioned in step (4), Ii(t+1)=Ii(t) and I→(t+1)∈ΨOPT. Thus, mathematically we get the following relation:(6)Pr⁡I→t+1∉ΨOPT∣I→t∈ΨOPT↝0Based on (6), we can state that I→(t) is an absorbing Markov process, with subspace ΨOPT as an absorbing state subset. Now, let us assume PG and PR represent the probability ofgenetic operation andreproduction operation, mentioned in step (3) of BiSON algorithm. As the genetic operation randomly selects any two row identifiers (Rp,Rq) for each of the λ chromosome (each chromosome containing r rows), mathematically we can say(7)PG=∏i=1λ1rr-1=1rr-1λFurthermore, as thereproduction operation probabilistically selects λ as the best chromosome from the set of 2λ chromosomes, we can say(8)PR=∏i=1λfIi∑j=12λfSj=∏i=1λfIi∑j=12λfSjλLetM represent the state transition probability matrix associated with BiSON, then M can be decomposed as a product of stochastic matrices: M=G·R, where G and R contain probability elements PG≥0 and PR≥0, respectively. Thus, we can say that M is a positive and primitive matrix [34]. At this point we can saythe BiSON algorithm with probabilities mentioned above is an ergodic Markov Chain;i.e., there exists a unique limit distribution with nonzero probability for the states of the chain to be in any state at any time, regardless of the initial distribution.


### 6.2. Convergence Analysis

Before analyzing the convergence of BiSON algorithm, we first define convergence as follows.LetCn, ∀n≥0,be a sequence of random variable.We call thatCnconverges toCif it satisfies the following: (9)limn→∞⁡PrCn∈C=1From above definitions and modeling of BiSON algorithm, we can conclude that the stochastic process associated with I→(t) is reducible, and the optimal state set C is a closed set with aperiodic and irreducible properties. In order to analyze the convergence of Markov Chain I→(t), we use the following important convergence definition [33]:For any reducible stochastic matrix M,the following relation holds: (10)limj→∞⁡Mj=M∞=1m×1′·π∞,which is a stable stochastic matrix where π∞=(π1,….,πm) and ∑i=1m‍πi=1. If Pr[I→(t)] is the probability distribution of I→(t), then from the definition of Markov Chain we can obtain Pr[I→(t)]=Pr[I→(0)]·Mt. From the definition of convergence, we can say that there exists a stable distribution π∞ which satisfies |Mt-1′π∞|→0. The values of π∞ corresponding to Ψ|ΨOPT approach zero, thus resulting in the following relation:(11)PrI→t∈Ψ∣ΨOPT↝0⇒limt→∞⁡PrI→t∈ΨOPT↝1Based on this analysis, now we can conclude thatthe BiSON algorithm converges to the optimal state setΨOPT.


### 6.3. Convergence Speed

In order to analyze the convergence speed of BiSON, we first state the definition of aminorization condition [33] for the Markov Chain:A minorization condition for a Markov Chain{I→(t),t≥0}is a pair(α,β,(·))such thatP(I→(t),X)≥αβ(X),∀I→∈ΨandX⊂Ψ,whereαis a positive real number andβis a probability distribution onΨ. With a stationary distributionPstat, given any initial distribution|P(t)-Pstat|≤(1-α)t [33].Considering the BiSON algorithm, we can say that the number of chromosomes of the corresponding state of associated Markov Chain{I→(t),t≥0} is λ, and each chromosome Ii consists of r rows in any order. As every element of any row in the generation can be either of three values (ł,ø,χ), if l represents the current number of entries of every row, then the total possible number of permutations in Ψ is 3lrλ. Referring to (7) and (8) from Section 6.1, we can have the following relation:(12)PG=1rr-1λ≥1rrλ,andPR=∏i=1λfIi∑j=12λfIjλ≥fIl∑j=12λfIjλ,where f(Il) represents the chromosome S with lowest f(S). Now if we define α=[(3l/r)r(f(Il)/∑j=12λ‍f(Ij))]λ, and β(X)=3-lrλ·|X|, where |X| represents the cardinality of X, then for any (t) and X⊂Ψ, we can say that(13)PI→,X=∑V→∈XPI→,V→≥1rrλfIl∑j=12λfIjλ=αβXHence, we can conclude that (α,β(·)) defined above is a minorization condition for the Markov Chain representation of BiSON. Thus, based on minorization condition definition, we can conclude the following on the speed of convergence of BiSON:the Markov Chain corresponding to the BiSON algorithm, with a stationary probability distributionPand probability distributionP(t)oftthgeneration, satisfies the following equation:(14)Pt-P≤1-3lrrfIl∑j=12λfIjλtBased on the above equation, we can easily infer that the convergence speed of BiSON increases with increasing value off(Il) and reduces with increasing values of λ and r.


## 6.1. Markov Chain Modeling

The BiSON algorithm, mentioned in Section5.1, shows that at any iteration t, the chromosome-set I→(t) depends only on the chromosome-set of the previous iteration I→(t-1). Hence, mapping every chromosome-set to the corresponding state, the underlying process could be modeled as a Discrete Time Markov Chain [33, 34], with state space Ψ. If Pr represents the corresponding state probability, then mathematically we can say Pr[I→(t)|I→(0),…,I→(t-1)]=Pr[I→(t)|I→(t-1)]. Defining ΨOPT as the globally optimal state set, if any current optimal chromosome Ii(t), at iteration t, is the globally optimal chromosome (fittest), then Ii(t)∈ΨOPT. Following the stopping criteria of BiSON algorithm, as mentioned in step (4), Ii(t+1)=Ii(t) and I→(t+1)∈ΨOPT. Thus, mathematically we get the following relation:(6)Pr⁡I→t+1∉ΨOPT∣I→t∈ΨOPT↝0Based on (6), we can state that I→(t) is an absorbing Markov process, with subspace ΨOPT as an absorbing state subset. Now, let us assume PG and PR represent the probability ofgenetic operation andreproduction operation, mentioned in step (3) of BiSON algorithm. As the genetic operation randomly selects any two row identifiers (Rp,Rq) for each of the λ chromosome (each chromosome containing r rows), mathematically we can say(7)PG=∏i=1λ1rr-1=1rr-1λFurthermore, as thereproduction operation probabilistically selects λ as the best chromosome from the set of 2λ chromosomes, we can say(8)PR=∏i=1λfIi∑j=12λfSj=∏i=1λfIi∑j=12λfSjλLetM represent the state transition probability matrix associated with BiSON, then M can be decomposed as a product of stochastic matrices: M=G·R, where G and R contain probability elements PG≥0 and PR≥0, respectively. Thus, we can say that M is a positive and primitive matrix [34]. At this point we can saythe BiSON algorithm with probabilities mentioned above is an ergodic Markov Chain;i.e., there exists a unique limit distribution with nonzero probability for the states of the chain to be in any state at any time, regardless of the initial distribution.


## 6.2. Convergence Analysis

Before analyzing the convergence of BiSON algorithm, we first define convergence as follows.LetCn, ∀n≥0,be a sequence of random variable.We call thatCnconverges toCif it satisfies the following: (9)limn→∞⁡PrCn∈C=1From above definitions and modeling of BiSON algorithm, we can conclude that the stochastic process associated with I→(t) is reducible, and the optimal state set C is a closed set with aperiodic and irreducible properties. In order to analyze the convergence of Markov Chain I→(t), we use the following important convergence definition [33]:For any reducible stochastic matrix M,the following relation holds: (10)limj→∞⁡Mj=M∞=1m×1′·π∞,which is a stable stochastic matrix where π∞=(π1,….,πm) and ∑i=1m‍πi=1. If Pr[I→(t)] is the probability distribution of I→(t), then from the definition of Markov Chain we can obtain Pr[I→(t)]=Pr[I→(0)]·Mt. From the definition of convergence, we can say that there exists a stable distribution π∞ which satisfies |Mt-1′π∞|→0. The values of π∞ corresponding to Ψ|ΨOPT approach zero, thus resulting in the following relation:(11)PrI→t∈Ψ∣ΨOPT↝0⇒limt→∞⁡PrI→t∈ΨOPT↝1Based on this analysis, now we can conclude thatthe BiSON algorithm converges to the optimal state setΨOPT.


## 6.3. Convergence Speed

In order to analyze the convergence speed of BiSON, we first state the definition of aminorization condition [33] for the Markov Chain:A minorization condition for a Markov Chain{I→(t),t≥0}is a pair(α,β,(·))such thatP(I→(t),X)≥αβ(X),∀I→∈ΨandX⊂Ψ,whereαis a positive real number andβis a probability distribution onΨ. With a stationary distributionPstat, given any initial distribution|P(t)-Pstat|≤(1-α)t [33].Considering the BiSON algorithm, we can say that the number of chromosomes of the corresponding state of associated Markov Chain{I→(t),t≥0} is λ, and each chromosome Ii consists of r rows in any order. As every element of any row in the generation can be either of three values (ł,ø,χ), if l represents the current number of entries of every row, then the total possible number of permutations in Ψ is 3lrλ. Referring to (7) and (8) from Section 6.1, we can have the following relation:(12)PG=1rr-1λ≥1rrλ,andPR=∏i=1λfIi∑j=12λfIjλ≥fIl∑j=12λfIjλ,where f(Il) represents the chromosome S with lowest f(S). Now if we define α=[(3l/r)r(f(Il)/∑j=12λ‍f(Ij))]λ, and β(X)=3-lrλ·|X|, where |X| represents the cardinality of X, then for any (t) and X⊂Ψ, we can say that(13)PI→,X=∑V→∈XPI→,V→≥1rrλfIl∑j=12λfIjλ=αβXHence, we can conclude that (α,β(·)) defined above is a minorization condition for the Markov Chain representation of BiSON. Thus, based on minorization condition definition, we can conclude the following on the speed of convergence of BiSON:the Markov Chain corresponding to the BiSON algorithm, with a stationary probability distributionPand probability distributionP(t)oftthgeneration, satisfies the following equation:(14)Pt-P≤1-3lrrfIl∑j=12λfIjλtBased on the above equation, we can easily infer that the convergence speed of BiSON increases with increasing value off(Il) and reduces with increasing values of λ and r.


## 7. Simulation Experiments and Results

In this section, we first introduce our NS3-based network simulator and describe the simulation scenario. Subsequently, we discuss our simulation results and present the efficiency and complexity of proposed algorithms.


### 7.1. Simulation Parameters

(1)
We consider a13,400m2 dense urban environment with 120 macrocells, each having a radius of 400 m. (2)
The 5G small cells have radius~50m and are deployed in a random fashion. The number of small cell deployment gradually increased from 1,000 to 12,000. (3)
The BiSON algorithm runs in the SON server and dynamically allocates PCID to small cells. (4)
We have used dense urban 5G channel model specified in [25] and the RF parameters from Samsung’s 5G field test [24] which states an RRH’s transmission power of 31 dBm, idle power of 5 dBm, penetration loss of 25 dB, shadowing deviation of 0.8, mobile UE’s maximum power of 20 dBm in 27.925 GHz frequency band, and 520 MHz channel bandwidth. Table 3 highlights other 5G networks, and radio parameters used in our simulations. (5)
We also include multistory buildings where small cells are deployed with arbitrary overlapping of one over another.Table 3
Major experimental and simulation parameters.
5G Radio Access Network Models [24, 25]  Penetration loss 20dB  Attenuation factor l+37.6log10R  Path loss compensation 3.8  Macro and Small Cell Parameters  RRH switch-off threshold 20%  RRH switch-on threshold 50%  Additional Simulation Parameter  Number of UEs per macro cell 600  Number of UEs per small cell 100  UE mobility model Random waypoint model [26]  Simulation duration 30 days(Data used for the manuscript is available at http://www.abhishekroy.info/slides.html)


### 7.2. Results and Discussion

We have simulated our algorithm with NS-3 based system simulator, compared our BiSON simulation result with Permutation Merge Model with Guided Random Search (PMM-GRS) algorithm [5], and distributed graph coloring based PCID allocation [3]. Figure 9(a) delineates the competitive PCID allocation using BiSON, PMM-GRS and graph coloring based assignment without confusion. The BiSON algorithm exhibits an average of 53% and 55% enhancement in PCID allocation more than the PMM-GRS, and the graph coloring based PCID assignment strategy, respectively. Using 504 PCIDs, graph coloring based PCID allocation and PMM-GRS can allocate a multiple of ~4,500 and ~5,000 cells, respectively, under the same server, whereas BiSON can support up to 11,000 cells. Using BiSON, only 301 unique PCID can configure up to 7,000 cells including macrocells and small cells. Figure 9(b) presents the execution time of BiSON, compared to graph coloring based PCID assignment and PMM-GRS approach. Proposed BiSON algorithm can find a near-optimal solution in 70~130s for 3000~7000 cells. As compared to BiSON, PMM-GRS needs ~20% additional execution time for a higher number of 5G small cells while graph coloring based PCID allocation without confusion takes ~30% more execution time than the BiSON.Figure 9
(a) Near-optimal PCID allocation, (b) comparative execution time, (c) PCID allocation dynamics, (d) comparative computational overhead, (e) confusion and PCID allocation, (f) confusion and no. of cells supported.
(a) (b) (c) (d) (e) (f)BiSON uses two solution approaches: Heuristic and ANO for both addition and removal of new cells. Comparative PCID allocation for both strategies with500 base stations is shown in Figure 9(c). At the arrival of every new base station, ANO strategy finds an optimal PCID allocation at each time. On the other hand, the heuristic approach computes the near-optimal PCID allocation once and then continues assigning new PCID to the new base stations until all the available PCID get allocated. After all the PCIDs are allocated, it re-executes the algorithm and finds a new near-optimal PCID allocation. Figure 9(d) shows the number of operations performed by both strategies. The heuristic approach shows ~95 times better performance than the ANO approach in regard to computational overhead.Dynamics of future confusion evaluation and avoidance according to update rules are presented in Figure9(e). With more than 80 PCID reserved, future confusion is reduced to almost zero. BiSON can estimate all the possible virtual cells and allocate PCIDs on their arrivals. If less than 10 PCIDs are reserved, the number of confusion can be up to ~180.Figure9(f) presents the trade-off between the number of initial cells supported with the number of future confusions. As shown in this figure, with less than 11,500 small cells, BiSON encounters no future confusion. This is a direct consequence of update rule to reserve some PCIDs for future cells. With a large number of initial cells, the number of reserved PCIDs for future dynamic addition is small, leading to early violation of confusion constraint. For more than 12,000 cells, BiSON incurs ~80 future confusions.Figure10 shows the convergence speed of proposed BiSON with respect to the parameters λ and r. With low value of λ and r, the proposed algorithm completes in less than 10s. With increasing λ and r, the convergence time increases. BiSON’s convergence time increases up to 550s in a deployment scenario where λ=50 and r=500 in a dense urban environment.Figure 10
BiSON convergence.


## 7.1. Simulation Parameters

(1)
We consider a13,400m2 dense urban environment with 120 macrocells, each having a radius of 400 m. (2)
The 5G small cells have radius~50m and are deployed in a random fashion. The number of small cell deployment gradually increased from 1,000 to 12,000. (3)
The BiSON algorithm runs in the SON server and dynamically allocates PCID to small cells. (4)
We have used dense urban 5G channel model specified in [25] and the RF parameters from Samsung’s 5G field test [24] which states an RRH’s transmission power of 31 dBm, idle power of 5 dBm, penetration loss of 25 dB, shadowing deviation of 0.8, mobile UE’s maximum power of 20 dBm in 27.925 GHz frequency band, and 520 MHz channel bandwidth. Table 3 highlights other 5G networks, and radio parameters used in our simulations. (5)
We also include multistory buildings where small cells are deployed with arbitrary overlapping of one over another.Table 3
Major experimental and simulation parameters.
5G Radio Access Network Models [24, 25]  Penetration loss 20dB  Attenuation factor l+37.6log10R  Path loss compensation 3.8  Macro and Small Cell Parameters  RRH switch-off threshold 20%  RRH switch-on threshold 50%  Additional Simulation Parameter  Number of UEs per macro cell 600  Number of UEs per small cell 100  UE mobility model Random waypoint model [26]  Simulation duration 30 days(Data used for the manuscript is available at http://www.abhishekroy.info/slides.html)


## 7.2. Results and Discussion

We have simulated our algorithm with NS-3 based system simulator, compared our BiSON simulation result with Permutation Merge Model with Guided Random Search (PMM-GRS) algorithm [5], and distributed graph coloring based PCID allocation [3]. Figure 9(a) delineates the competitive PCID allocation using BiSON, PMM-GRS and graph coloring based assignment without confusion. The BiSON algorithm exhibits an average of 53% and 55% enhancement in PCID allocation more than the PMM-GRS, and the graph coloring based PCID assignment strategy, respectively. Using 504 PCIDs, graph coloring based PCID allocation and PMM-GRS can allocate a multiple of ~4,500 and ~5,000 cells, respectively, under the same server, whereas BiSON can support up to 11,000 cells. Using BiSON, only 301 unique PCID can configure up to 7,000 cells including macrocells and small cells. Figure 9(b) presents the execution time of BiSON, compared to graph coloring based PCID assignment and PMM-GRS approach. Proposed BiSON algorithm can find a near-optimal solution in 70~130s for 3000~7000 cells. As compared to BiSON, PMM-GRS needs ~20% additional execution time for a higher number of 5G small cells while graph coloring based PCID allocation without confusion takes ~30% more execution time than the BiSON.Figure 9
(a) Near-optimal PCID allocation, (b) comparative execution time, (c) PCID allocation dynamics, (d) comparative computational overhead, (e) confusion and PCID allocation, (f) confusion and no. of cells supported.
(a) (b) (c) (d) (e) (f)BiSON uses two solution approaches: Heuristic and ANO for both addition and removal of new cells. Comparative PCID allocation for both strategies with500 base stations is shown in Figure 9(c). At the arrival of every new base station, ANO strategy finds an optimal PCID allocation at each time. On the other hand, the heuristic approach computes the near-optimal PCID allocation once and then continues assigning new PCID to the new base stations until all the available PCID get allocated. After all the PCIDs are allocated, it re-executes the algorithm and finds a new near-optimal PCID allocation. Figure 9(d) shows the number of operations performed by both strategies. The heuristic approach shows ~95 times better performance than the ANO approach in regard to computational overhead.Dynamics of future confusion evaluation and avoidance according to update rules are presented in Figure9(e). With more than 80 PCID reserved, future confusion is reduced to almost zero. BiSON can estimate all the possible virtual cells and allocate PCIDs on their arrivals. If less than 10 PCIDs are reserved, the number of confusion can be up to ~180.Figure9(f) presents the trade-off between the number of initial cells supported with the number of future confusions. As shown in this figure, with less than 11,500 small cells, BiSON encounters no future confusion. This is a direct consequence of update rule to reserve some PCIDs for future cells. With a large number of initial cells, the number of reserved PCIDs for future dynamic addition is small, leading to early violation of confusion constraint. For more than 12,000 cells, BiSON incurs ~80 future confusions.Figure10 shows the convergence speed of proposed BiSON with respect to the parameters λ and r. With low value of λ and r, the proposed algorithm completes in less than 10s. With increasing λ and r, the convergence time increases. BiSON’s convergence time increases up to 550s in a deployment scenario where λ=50 and r=500 in a dense urban environment.Figure 10
BiSON convergence.


## 8. Conclusion

In this paper, we have proved that the optimal PCID allocation is NP-hard problem. Subsequently, we proposed Bio-inspired Self-Organizing Network (BiSON) algorithm to find a near-optimal PCID allocation for 5G ultradense network. We discussed dynamics of near-optimal PCID allocation strategy and described two distinct approaches to support dynamic addition and removal of small cells in the 5G ultradense network. We analyzed the proposed algorithm and showed its convergence to an upper bound. Simulation results in an ultradense deployment demonstrate that our strategy can improve auto-configuration by53%~55% more than the previous approaches within feasible time and acceptable computational overhead.



---

*Source: 2632754-2018-11-07.xml*