Introduction

The computation of the network capacity requires the calculation of each link between cells (\(Q\)) and users (\(U\)) over the channels (\(N\)), determined by the Channel Allocation (CA) matrix \(X_{Q,U,N}\), considering the allocated power \(P_{Q,N}\) over each channel. This function is non-linear due to the calculation of interference, as can be observed in the SNIR (Eq. 1), which represent the sum of all the received signals produced by cells sharing the channel.

\[ C^{Network}(X_{Q,U,N}, P_{Q,N}) = \sum_{q=1}^Q{ \sum_{u=1}^{U}{ \sum_{n=1}^{N}{ \frac{B}{N}log_2(1 + \underbrace{ \frac{ X_{q,u,n} \overbrace{P_{q,n} H(q,u,n)}^\text{DessiredSingal} }{N_0 + I(q,u,n)} }_\text{SNIR}) } } } \qquad(1)\]

A straight forward strategy could be coded as:

Straight forward calculation of the capacity of the network.

C = zeros(U,1);
for q=1:Q
  for u=1:U
    for n=1:N
      if(X(q,u,n)) %if is allocated
        DessiredSingal = P(q,n) * H(q,u,n);
        Interferece = 0;
        for q2=1:Q
          for u2=1:U
            if(X(q2,u2,n))
              Interferece = Interferece + P(q2,n) * H(q2,u2,n);
            end
          end
        end
        % add to the user capacity
        C(u) = C(u) + B/N *...
               log2(1 + DessiredSingal / (Noise + Interferece));
      end
    end
  end
end

The procedure in Alg. ¿lst:alg1? has a complexity of \(\mathcal{O}(Q^2U^2N * \mathcal{O}(H(q,u,n)))\)1 received power calculations in the worst scenario, \(X(q,u,n)=1 \;\forall\; q,u,n\). However, this worst scenario is unrealistic as users are usually attended only by a single cell, and each cell can use once each channel between its users at any time. Therefore, worst case is represent by those allocations on which the cells make use of all channels among their users (Reuse 1), resulting on \(\mathcal{O}(Q^2N*\mathcal{O}(P_{q,n} * H(q,u,n)))\). Such allocations are usually used on works that evaluated the performance of Ultra-Dense Networks (UDNs), such as Nguyen and Kountouris (2017) and Romanous et al. (2015). This means that the evaluation of the network complicates with the network densification exponentially, increasing the delay of solving RA. Also the complexity of calculating the channel gain \(H(q,u,n)\) depends on the channel model, which requires a square root calculation for the Path Loss and generating one or several random number for Shadowing and Multi-Trajectory Losses. For this reason, it is necessary to implement efficient methods for this calculations.

In this case is convenient to pre-calculate the channel gains \(H_{q,u,n} = H(q,u,n)\). This is due to the calculation of a square root requires several basic operations, these gains can be considered fixed over the time on which RA is executed [REFs] and the worst case scenario is highly probable in most implementations of RA algorithms over UDNs. The distance between cells and users (\(D_{q,u}\)) is performed and multiplied by the channel random gains of each channel, . As \(H_{q,u,n}\) remains fix through the RA process, this is calculated only once and reused over all the rest allocation evaluations, thus the \(\mathcal{O}(QU*\mathcal{O}(\sqrt{D_{q,n}}) + UN)\) complexity of this calculation is removed. Given \(H_{q,u,n}\), it is possible to calculate the user signal perceived from all cells as \(S_{q,u,n} = P_{q,n} * H_{q,u,n}\). Consequently, the remained complexity is \(\mathcal{O}(Q^2N + QN)\) which represent the complexity of CA and PA respectively.

One significant improvement for the computer efficiency can be obtained by the vectorization2 of Alg. ¿lst:alg1? as MATLAB® is optimized for operations involving matrices and vectors (similarly to other Programming Languages like Python with Numpy), and it allows the use of parallel GPU computations easily. Making this change in implementation do not affect the calculation computer complexity, but it positively affects the execution time due to the compilation optimizations of the software.

Vectorized calculation of the capacity of the network.

C = zeros(U, 1);
for n=1:N
  usersInx = X(:,n) ~= 1; %list of users using channel n
  cellsInx = A(usersInx); %cells attending these users
  signalsRx      = S(cellsInx, usersInx, n); %max size of QxQ
  DessiredSingal = signalsRx * eye(size(signalsRx)); %Diagonal
  Interference   = sum(signalsRx, 2) - DessiredSingal;
  C(usersInx)    = C(usersInx) + B/N *...
                   log2(1 + dessiredS / (Noise + Interference));
end

To simplify this implementation the Channel Allocation matrix is divided on a smaller channel allocation between users and channels \(X_{u,n}\), and a separated variable \(A_u\) contains the cell associated to each user. This setup is usually used due to association is performed in a separated pre-processing before RA, if required. Then, as shown in Algorithm ¿lst:alg2? a square matrix of received signal between the users and cells sharing the channel can be obtained. The diagonal of the \(signalsRx\) matrix represent the desired signals and the rest determined the interference perceived. Further vectorization can be implemented, to calculate the capacity or all the channels, but this requires complicated highly dimensional matrix transformations and memory space, which limits its implementation as shown in Appendix #.

Block Allocation Proposal

The proposed block allocation of this work [SELF_REF] allows to further reduce the complexity of the evaluation of the network capacity. The proposal considers CA y PA as two consecutive sub-problems to solve RA, which is well-known strategy in these works [REFs]. To solve CA, the power of each cell is allocated flat over the channels, i.e., \(P(q,n) = P_q/N \;\forall\; q, n\). This simplification added to the use of Path Loss as the only fading factor in the channel model make it is possible to storage the perceived signal of the users from all cells as \(S_{q,u} = P_q/N * H_{q,u,n}\).3 Therefore, the PA part of the complexity is eliminated resulting in \(\mathcal{O}(Q^2N)\).

Furthermore, the exclusive use of Path Loss in the channel model, considers a flat behavior of the channels gains. This means that the same capacity is achieved over any channel with an identical configuration of users sharing it, which incentives to recollect all possible configurations capacities. However, this strategy is unpractical as it requires \(2^U\) computations and space in memory. Nevertheless, due to the block allocation scheme proposed in this work, it is highly probable that multiple adjacent channels are share by the same configuration of users. Therefore, the last configuration of channels and capacity can be recorded, to compare with the consecutive channels and skip those calculations, which lead to the worst case complexity \(\mathcal{O}(Q^2log(N))\). This implementation is exposed in Algorithm ¿lst:alg3? and used for the network simulations on this work.

Vectorized calculation of the capacity of the network.

C = zeros(U,1);
lastUI = [];
lastUC = [];
for n=1:N
  usersInx = X(:,n) ~= 1; %list of users using channel n
  if(n > 1 && all(lastUI==usersInx))
    tempC = lastUC;
  else
    cellsInx = A(usersInx); %cells attending these users
    signalsRx = S(cellsInx, usersInx); %max size of QxQ
    DessiredSingal = signalsRx * eye(size(signalsRx)); %Diagonal
    Interference   = sum(signalsRx, 2) - DessiredSingal;
    tempC = B/N *log2(1 + dessiredS / (Noise + Interference));
  end
  C(usersInx) = C(usersInx) + tempC
  usersInx = usersInx;
  lastUC = tempC;
end

Nguyen, Van Minh, and Marios Kountouris. 2017. “Performance Limits of Network Densification.” IEEE Journal on Selected Areas in Communications 35 (6). Institute of Electrical; Electronics Engineers (IEEE): 1294–1308. https://doi.org/10.1109/jsac.2017.2687638.

Romanous, Bashar, Naim Bitar, Ali Imran, and Hazem Refai. 2015. “Network Densification: Challenges and Opportunities in Enabling 5G.” In 2015 IEEE 20th International Workshop on Computer Aided Modelling and Design of Communication Links and Networks (CAMAD). IEEE. https://doi.org/10.1109/camad.2015.7390494.

  1. This complexity refers to the evaluation of network capacity, not the complexity of solving RA.↩︎

  2. The process of revising loop-based, scalar-oriented code to use MATLAB matrix and vector operations is called vectorization. Vectorizing your code is worthwhile for several reasons: Appearance, Less Error Prone and Performance https://www.mathworks.com/help/matlab/matlab_prog/vectorization.html.↩︎

  3. This calculation is performed to associated users with the cell that offers the highest SNR using the Path Loss Association. So these results can be carried from such stage.↩︎