Distributed Randomized k-Clustering based PCID Assignment for Ultra-Dense Femtocellular Networks


Next-generation wireless networks are going to have highly dense, small cell structure with a large number of femtocells. The dense deployment of the femtocell network architecture is expected to meet the growing data demand by leveraging millimeter-wave structure of 5G wireless networks. However, arbitrary deployment of large number of femtocells underlying a macrocell will pose a challenge for collision and confusion-free Physical Cell ID (PCID) assignments as the total number of available PCIDs is limited to 504. In this paper we propose a distributed, randomized k-clustering algorithm for collision and confusion-free PCID assignment problem, which is known to be NP-complete. To reduce the total control message flow, we create overlapping clusters in ultra-dense femtocellular networks, where each cluster head runs the distributed randomized PCID allocation algorithm and locally monitors the conflicts to avoid the collision and confusion constraints. We prove the correctness of our proposed algorithm and analyze its time and message complexity. Through simulation experiments, we also show the effect of different parameters on the PCID allocation objectives.


Computer Science

Research Center/Lab(s)

Intelligent Systems Center

Second Research Center/Lab

Center for High Performance Computing Research


The authors sincerely thank the anonymous referees and the associate editor for their insightful comments and suggestions. The work of A. Pratap is financially supported by Council of Scientific and Industrial Research, India. Part of the work was done while R. Singhal was a summer intern at Missouri University of Science and Technology, USA.

Keywords and Phrases

5G mobile communication systems; Coloring; Combinatorial optimization; Computer architecture; Computer resource management; Femtocell; Long Term Evolution (LTE); Microprocessor chips; Millimeter waves; Mobile telecommunication systems; Network architecture; Wireless networks; Wireless telecommunication systems; Clustering; Femto-cells; Femtocell Networks; LTE-A; PCID; Randomized; Resource management; Clustering algorithms; 5G wireless

International Standard Serial Number (ISSN)

1045-9219; 1558-2183

Document Type

Article - Journal

Document Version


File Type





© 2018 IEEE Computer Society, All rights reserved.

Publication Date

01 Jun 2018