# On the Optimisation of Practical Wireless Indoor and Outdoor Microcells Subject to QoS Constraints
## 4 The Proposed Binary-Search Based Cell Positioning Algorithm  
It can be noticed that different cell sites may have different coverage areas depending on their antenna characteristics, power allocation as well as practical locations. The cell sites can be therefore sorted in order of the coverage area. In this case, the binary search approach has been shown to provide a faster searching compared to the conventional iterative search without sorting [51]. This accordingly motivates us to propose a BSCP algorithm in this section to solve the NOP in Equation (1) subject to the constraint in Equation (2) following the binary search approach. We first order the cell sites according to their coverage area. Let \(A_{c_{k}}\), \(k=1,2,\ldots,K_{\max}\), denote the measured coverage area of the \(k\)-th cell site. Without loss of generality, let us assume that \(A_{c_{1}}\leq A_{c_{2}}\leq\cdots\leq A_{c_{K_{\max}}}\). Notice that there are a total of \(T=\sum_{k=1}^{K_{\max}}\binom{N}{k}\) possibilities of placing cell sites on \(N\) candidate locations. A special case is if \(K_{\max}=N\), then \(T=2^{N}-1\). Let \(\mathfrak{S}_{T}\) denote the set of these combinations with the corresponding set of the ordered coverage area \(\mathfrak{B}_{T}=\{B_{c_{1}},B_{c_{2}},\ldots,B_{c_{T}}\}\). In the proposed BSCP algorithm, the key idea is that we start searching from the middle element of the data set \(\mathfrak{S}_{T}\) and validate the constraint in Equation (2). If the constraint is not satisfied, then we eliminate the lower half of \(\mathfrak{S}_{T}\) and continue with the search of the remaining upper half of \(\mathfrak{S}_{T}\); and vice versa. The search will stop when the remaining set is null. The optimal coverage area, i.e., \(B_{opt}\) in \(\mathfrak{B}\), the optimal locations for cell sites, i.e., \(\mathfrak{S}_{i_{k_{\min}}}\) in \(\mathfrak{S}_{T}\), and the minimum number of cell sites, i.e., \(k_{\min}=|\mathfrak{S}_{i_{k_{\min}}}|\), can be accordingly determined. Here, \(|\cdot|\) denotes the cardinality of a finite set. The proposed BSCP algorithm is summarised in Algorithm 1 and, for clarity, the flow chart for this algorithm is illustrated in Figure 2.  
```
1:\(N\), \(K_{\max}\), \(P_{\min}\), \(\{A_{c_{k}}\}\), \(k=1,2,\ldots,K_{\max}\): \(A_{c_{1}}\leq A_{c_{2}}\leq\cdots\leq A_{c_{K_{\max}}}\)
2:Sort the coverage area of the \(T=\sum_{k=1}^{K_{\max}}\binom{N}{k}\) possibly combined cell sites: \(\mathfrak{B}=\{B_{c_{1}},B_{c_{2}},\ldots,B_{c_{T}}\}\)
3:Set \(i_{L}\gets 1\), \(i_{U}\gets T\) {smallest and biggest indexes of \(\mathfrak{B}\)}
4:repeat
5: Set \(i_{C}\leftarrow\lceil(i_{L}+i_{U})/2\rceil\) {index of midpoint of \(\mathfrak{B}\)}
6:if\(P(x_{e_{m}},y_{e_{m}})\geq P_{\min}\), \(\forall m=1,2,\ldots,M\)then
7:\(i_{U}\gets i_{C}-1\)
8:else
9:\(i_{L}\gets i_{C}+1\)
10:endif
11:until\(i_{L}>i_{U}\)
12:return\(B_{opt}=B_{c_{i_{C}}}\), \(\mathfrak{S}_{i_{k_{\min}}}=\mathfrak{S}_{i_{C}}\), \(k_{\min}=|\mathfrak{S}_{i_{k_{\min}}}|\)
```  
**Algorithm 1** BSCP Algorithm for WIOM Planning. **Remark 1** (Complexity Analysis). : _Generally, with binary search, finding an item in a sorted array of \(n\) elements requires \(\mathcal{O}(\log n)\) comparisons in the worst case scenario, while a linear or exhaustive search over all elements takes \(\mathcal{O}(n)\) time [51]. As shown in Algorithm 1 for WIOM planning, the proposed BSCP performs the binary search over a set consisting of \(T=\sum_{k=1}^{K_{\max}}\binom{N}{k}\) elements which correspond to the possibilities of placing cell sites on \(N\) candidate locations. Therefore, the BSCP algorithm requires a total of \(\mathcal{O}(\log T)\) comparisons, which is of lower complexity than the conventional ESCP algorithm with \(\mathcal{O}(T)\) time for linear search. For example, let us consider a special scenario when \(K_{\max}=N\), then \(T=2^{N}-1\).