Method for arranging base stations in a communication network
The present invention provides a method and a system for arranging base stations in a millimeter wave communication network. The method establishes a stochastic optimization framework for millimeter-wave base station deployment in the urban street geometry and provides a low-complexity user association arrangement which can well balance the workloads among BSs and reduce the outage probability by taking the time-varying nature of user equipments' positions and the susceptibility of millimeter-wave links to blockage effect into account. Compared with the state-of-the-art approaches, the present invention can effectively and efficiently reduce the outage probability in the long term.
1. A method for arranging base stations in a communication network, comprising the steps of:
designing an optimal deployment of an M number of base stations (BSs), including optimized positions of the plurality of BSs, r BS *, serving for an N number of user equipment (UEs), in an urban area with a building-block geometry, to maximize a long-term performance of an average number of accessible BSs, {right arrow over (M)} ac , with a sample of positions of the N number of UEs, under a bounded inaccessible probability constraint; and
matching the N number of UEs with the M number of BSs based on the optimized positions of the M number of BSs, r BS *, in a given time slot to minimize an outage probability, Po, which is defined as the proportion of the N number of UEs that cannot associate with any of the M number of BSs, under a first matching constraint that a UE n can associate with a BS m only if the BS m is physically accessible for the UE n, a second matching constraint that each of the M number BSs has a maximum workload, and a third matching constraint that each UE can only associate with one BS, where m=1, 2, . . . , M, and n=1, . . . , N.
2. The method of claim 1 , wherein the bounded inaccessible probability constraint is defined as that a long-term average performance of the inaccessible probability P iac is equal or smaller than a bounded value.
3. The method of claim 2 , wherein:
the inaccessible probability, P iac , is dependent on coverage and blockage performance of the communication network; and
the average number of accessible BSs, {right arrow over (M)} ac , is dependent on coverage and blockage performance of the communication network.
4. The method of claim 3 , wherein the optimized positions of the M number of BSs, r BS *, are determined by using a cooperative stochastic approximation (CSA) based scheme.
5. The method of claim 4 , wherein the CSA-based scheme comprises the steps of:
setting initial positions of the M number of BSs, r BS (0); and
iteratively updating the positions of the M number of BSs by performing a T number of iterations of a CSA-based algorithm;
wherein a t th iteration of the CSA-based algorithm, for an iteration index t=0, . . . , T−1, includes the steps of:
determining, with a sample of the N number of UEs' positions r UE (t), a stochastic gradient {tilde over (ω)} BS out (t) related to a plurality of out-of-coverage indicator functions m,n block (t) at the t th iteration;
determining, with the sample of the N number of UEs' positions r UE (t), a stochastic gradient {tilde over (ω)} BS block (t) related to a plurality of blockage indicator functions m,n block (t) at the t th iteration;
determining a step size η out (t) based on the determined stochastic gradient {tilde over (ω)} BS out (t);
determining a step size η block (t) based on the determined stochastic gradient {tilde over (ω)} BS block (t);
updating positions of the M number of BSs from r BS (t) to r BS (t+1) based on the determined stochastic gradients {tilde over (ω)} BS out (t) and {tilde over (ω)} BS block (t), the determined step sizes η out (t) and η block (t); and
determining, with the updated positions of the M number of BSs, r BS (t+1), an updated unbiased estimation of inaccessible probability, {circumflex over (P)} iac (t+1);
assigning the updated positions of the M number of BSs, r BS (t+1), as the optimized positions of the M number of BSs, r BS *, if the updated unbiased estimation of inaccessible probability, {circumflex over (P)} iac (t+1), is smaller or equal to the bounded value P iac *.
6. The method of claim 1 , wherein the matching of the N number of UEs with the M number of BSs is performed by using a low-complexity sub-optimal user association algorithm.
7. The method of claim 6 , wherein the low-complexity sub-optimal user association algorithm comprises:
initiating a candidate set of BSs, 0 , by letting 0 be the M number of BSs;
initiating a candidate set of UEs, 0 , by letting 0 be the set of UEs which have at least one physically accessible BS;
performing, while none of 0 and 0 is empty, a user association process including steps of:
selecting from the candidate set of UEs, 0 , a candidate UE n* which is with the smallest number of accessible BSs,
selecting from the candidate set of BSs, 0 , a candidate BS m*, which is with the smallest number of associated UEs;
associating the candidate UE n* and the candidate BS m*;
removing the candidate UE n* from the candidate set of UEs, 0 ;
removing the candidate BS m* from the candidate set of BSs, 0 if the candidate BS n* has been associated with C UEs.
8. A system for communication network base station arrangement, comprising a processor configured to:
design an optimal deployment of an M number of base stations (BSs), including optimized positions of the plurality of BSs, r BS *, serving for an N number of user equipment (UEs), in an effective area with a building-block geometry, to maximize a long-term performance of an average number of accessible BSs, with a sample of positions of the N number of UEs, under a bounded inaccessible probability constraint; and
match, based on the optimized positions of the M number of BSs, r BS *, the N number of UEs with the M number of BSs, in a given time slot, to minimize an outage probability, Po, which is defined as the proportion of the N number of UEs that cannot associate with any of the M number of BSs, under a first matching constraint that a UE n can associate with a BS m only if the BS m is physically accessible for the UE n, a second matching constraint that each of the M number BSs has a maximum workload, and a third matching constraint that each UE can only associate with one BS.
9. The system of claim 8 , wherein the bounded inaccessible probability constraint is defined as that a long-term average performance of the inaccessible probability P iac is equal or smaller than a bounded value.
10. The system of claim 9 , wherein
the inaccessible probability, P iac , is dependent on coverage and blockage performance of the communication network
and
the average number of accessible BSs, M ac , is dependent on coverage and blockage performance of the communication network.
11. The system of claim 10 , wherein the processor is further configured to determine the optimized positions of the M number of BSs, r BS *, by using a cooperative stochastic approximation (CSA) based scheme.
12. The system of claim 11 , wherein the CSA-based scheme comprises the steps of:
setting initial positions of the M number of BSs, r BS (0);
iteratively updating the positions of the M number of BSs by performing a T number of iterations of a CSA-based algorithm, for an iteration index t=0, . . . , T−1, and wherein a t th iteration including the steps of:
determining, with a sample of the N number of UEs' positions r UE (t), a stochastic gradient {tilde over (ω)} BS out (t) related to a plurality of out-of-coverage indicator functions m,n out (t) at the t th iteration;
determining, with the sample of the N number of UEs' positions r UE (t), a stochastic gradient {tilde over (ω)} BS block (t) related to a plurality of blockage indicator functions m,n block (t) at the t th iteration;
determining a step size η out (t) based on the determined stochastic gradient {tilde over (ω)} BS out (t);
determining a step size η block (t) based on the determined stochastic gradient {tilde over (ω)} BS block (t);
updating positions of the M number of BSs from r BS (t) to r BS (t+1) based on the determined stochastic gradients {tilde over (ω)} BS out (t) and {tilde over (ω)} BS block (t), the determined step sizes η out (t) and η block (t); and
determining, with the updated positions of the M number of BSs, r BS (t+1), an updated unbiased estimation of inaccessible probability, {circumflex over (P)} iac (t+1);
assigning the updated positions of the M number of BSs, r BS (t+1), as the optimized positions of the M number of BSs, r BS *, if the updated unbiased estimation of inaccessible probability, {circumflex over (P)} iac (t+1), is smaller or equal to the bounded value P iac *.
13. The system of claim 12 , wherein the processor is further configured to use a low-complexity sub-optimal user association algorithm for matching the N number of UEs with the M number of BSs.
14. The system of claim 13 , wherein the low-complexity sub-optimal user association algorithm comprises:
initiating a candidate set of BSs, 0 , by letting 0 be the M number of BSs;
initiating a candidate set of UEs, 0 , by letting 0 be the set of UEs which have at least one physically accessible BS;
performing, while none of 0 and 0 is empty, a user association process including steps of:
selecting from the candidate set of UEs, 0 , a candidate UE n* which is with the smallest number of accessible BSs,
selecting from the candidate set of BSs, 0 , a candidate BS m*, which is with the smallest number of associated UEs;
associating the candidate UE n* and the candidate BS m*;
removing the candidate UE n* from the candidate set of UEs, 0 ;
removing the candidate BS m* from the candidate set of BSs, 0 if the candidate BS m* has been associated with C UEs.