# Sound Source Localization Indoors Based on Two-Level Reference Points Matching
## 3 Two-Level Matching Method for Adjacent RPs Searching
### Adjacent Subset Searching Based on Greedy Algorithm  
Greedy algorithm refers to choosing the best or most optimized option in each step so as to bring about the best or optimized overall performance of the algorithm [40]. For instance, in the problem of adjacent RPs searching, if the nearest RPs are chosen as the searching center for each searching step, it can be regarded as a kind of greedy algorithm. A greedy algorithm is particularly effective in solving the problem of the optimal substructure. Optimal substructure means that the local optimum can determine the global optimum. Put simply, the problem can be divided into sub-problems for a solution. The optimum for the sub-problems can recur to the optimum for the final problem. Adjacent RPs of the database refers to the RPs that are closest to the target point in the feature space. Therefore, adjacent RP searching is a global optimization problem of spatial distance essentially. As Figure 2 stated previously in Section 3, the TDOA characteristics of samples are of high local correlation in a global range, and the correlation value will rapidly decrease when the physical distance increases. Therefore, the search of adjacent RPs basically meets the greedy rule of optimal substructure in the simple indoor scene. As shown in Figure 3, the matching process of adjacent RPs based on a greedy algorithm is composed of three parts. Figure 2: The correlation coefficient value between RPs in two typical indoor positioning scenes: (**a1**) setting of experimental environment for simple indoor positioning scene; (**a2**) relationship between correlation coefficient and distance of RPs in simple indoor positioning scene; (**a3**) the ratio of the correlation value for RPs beyond 0.6 in simple indoor positioning scene; (**b1**) setting of experimental environment for complex indoor positioning scene; (**b2**) relationship between correlation coefficient and distance of RPs in complex indoor positioning scene; (**b3**) the ratio of the correlation value for RPs beyond 0.6 in complex indoor positioning scene. First, the Euclidean distance between the RPs and the target point in the feature space is selected as the objective function \(f(i)\), and an RP is randomly selected from the location database \(\mathbf{D}{=}[\mathbf{S}_{1},\mathbf{S}_{2},\cdots,\mathbf{S}_{N}]^{T}\) is appointed to be the first search center (i.e., the initial optimal solution). Then, other solutions in the neighborhood of the optimal solution (i.e., the RPs near the search center) and the optimal solution itself constitute the current local search database \(\mathbf{D}^{l}\):  
\[\mathbf{D}^{l}{=}[\mathbf{S}_{1}^{l},\mathbf{S}_{2}^{l},\cdots,\mathbf{S}_{g}^{l}]^{T} \tag{5}\]  
where \(\mathbf{S}_{i}^{l}=[\mathbf{L}_{i}^{l},\mathbf{F}_{i}^{l}]\)\(i=1,2,\ldots,g\). and \(g\) is the total number of samples in a locally searched subset. We then calculate the objective function value of each solution in the local search database \(\mathbf{D}^{l}\):  
\[f(i)=\left\|\mathbf{F}-\mathbf{F}_{i}^{l}\right\|_{2}\,\ i=1,2,\ldots,g. \tag{6}\]  
where \(\mathbf{F}\) is the feature vector of the positioning target and \(\mathbf{F}_{i}^{l}\) is the feature vector of the \(i\)th element in the local search subset. We select the solution that minimizes the value of the objective function as the new optimal solution:  
\[\mathbf{c}=\mathbf{S}_{\arg\min_{i\in\{1,2,\ldots,g\}}f(i)} \tag{7}\]  
If the optimal solution no longer changes, the greedy search process will end. The optimal solution of the current local search process will be the globally optimal solution (i.e., the nearest RPs of the target point). At the same time, the current local search subset \(\mathbf{D}^{l}\) will be the adjacent subset; otherwise, continue to repeat the search process of Equations (5)-(7).