© The Institution of Engineering and Technology
In this study, the authors investigate the problem of source localisation based on the time difference of arrival (TDOA) in a group of sensors. Aiming to minimise the squared range-difference errors, the problem leads to a quadratically constrained quadratic programme. It is well known that this approach results in a non-convex optimisation problem. By proposing a relaxation technique, they show that the optimisation problem would be transformed to a convex one which can be solved by semi-definite programming (SDP) and Lagrange multiplier methods. Moreover, these methods offer the exact solution of the original problem and the affirmation of its uniqueness. In contrast to other complicated state-of-the-art SDP algorithms presented in the TDOA localisation literature, the authors methods are derived in a few straightforward reformulations and insightful steps; thus, there are no confusing and unjustifiable changes in the main optimisation problem. Furthermore, complexity analysis and a new approach for performance analysis, which show the merit of their methods, are introduced. Simulations and numerical results demonstrate that the positioning estimators resulted from the proposed algorithms outperform existing SDP-based methods presented so far.
References
-
-
1)
-
22. Xu, E., Ding, Z., Dasgupta, S.: ‘Reduced complexity semidefinite relaxation algorithms for source localization based on time difference of arrival’, IEEE Trans. Mob. Comput., 2010, 10, (9), pp. 1276–1282 (doi: 10.1109/TMC.2010.263).
-
2)
-
K.W. Cheung ,
H.C. So ,
W.K. Ma ,
Y.T. Chan
.
A constrained least squares approach to mobile positioning: algorithms and optimality.
EURASIP J. Appl. Signal Process.
,
1 -
23
-
3)
-
34. Sturm, J.F.: ‘Implementation of interior point methods for mixed semidefinite and second order cone optimization problems’, Optim. Meth. Softw., 2002, 17, (6), pp. 1105–1154 (doi: 10.1080/1055678021000045123).
-
4)
-
K. Yang ,
G. Wang ,
Z. Luo
.
Efficient convex relaxation methods for robust target localization by a sensor network using time differences of arrivals.
IEEE Trans. Signal Process.
,
7 ,
2775 -
2784
-
5)
-
Y. Huang ,
J. Benesty ,
G. Elko ,
R. Mersereati
.
Real-time passive source localization: a practical linear-correction least-squares approach.
IEEE Trans. Speech Audio Process.
,
8 ,
943 -
956
-
6)
-
K. Yang ,
J.P. An ,
X.Y. Bu ,
G.C. Sun
.
Constrained total least-squares location algorithm using time-difference-of-arrival measurements.
IEEE Trans. Veh. Technol.
,
3 ,
1558 -
1562
-
7)
-
6. Schmidt, R.: ‘A new approach to geometry of range difference location’, IEEE Trans. Aerosp. Electron. Syst., 1972, AES-8, (6), pp. 821–835 (doi: 10.1109/TAES.1972.309614).
-
8)
-
62. Luo, Z.-Q., Ma, W.-K., So, A.M.-C., Ye, Y., Zhang, S.: ‘Semidefinite relaxation of quadratic optimization problems’, IEEE Signal Process. Mag., 2010, 27, (3), pp. 20–34 (doi: 10.1109/MSP.2010.936019).
-
9)
-
N. Patwari ,
J.N. Ash ,
S. Kyperountas
.
Locating the nodes: cooperative localization in wireless sensor networks.
IEEE Signal Process. Mag.
,
4 ,
54 -
69
-
10)
-
2. Wang, H., Chu, P.: ‘Voice source localization for automatic camera pointing system in videoconferencing’. Proc. IEEE Workshop Applications Signal Processing Audio Acoustics, 1997.
-
11)
-
18. Fucheng, Q., Ho, K.C.: ‘A quadratic constraint solution method for TDOA and FDOA localization’. IEEE Int. Conf. Acoustics, Speech and Signal Processing (ICASSP), Prague, Czech Republic, 2011, pp. 2588–2591.
-
12)
-
J.O. Smith ,
J.S. Abel
.
The spherical interpolation method of source localization.
IEEE J. Ocean. Eng.
,
246 -
252
-
13)
-
1. Huang, Y., Benesty, J., Elko, G.W.: ‘Microphone arrays for video camera steering’, in Gay, S.L., Benesty, J. (Eds.): ‘Acoustic signal processing for telecommunication’ (Springer, US, 2000), pp. 239–259.
-
14)
-
6. Wax, M., Kailath, T.: ‘Optimum localization of multiple sources by passive arrays’, IEEE Trans. Acoust. Speech Signal Process., 1983, 31, (5), pp. 1210–1218 (doi: 10.1109/TASSP.1983.1164183).
-
15)
-
J.O. Smith ,
J.S. Abel
.
Closed-form least-squares sourse location estimation from range-dirrerence measurements.
IEEE Trans. Acoust., Speech, Signal Process.
,
1661 -
1669
-
16)
-
32. Pataki, G.: ‘Geometry of semidefinite programming’, in Wolkowicz, H., Saigal, R., Vandenberghe, L. (Eds.): ‘Handbook of semidefinite programming: theory, algorithms, and applications’ (Kluwer Academic Publishers, Boston, MA, 2000).
-
17)
-
D.J. Torrieri
.
Statistical theory of passive location systems.
IEEE Trans. Aerosp. Electron. Syst.
,
2 ,
183 -
197
-
18)
-
18. Schau, H.C., Robinson, A.Z.: ‘Passive source localization employing intersecting spherical surfaces from time-of-arrival differences’, IEEE Trans. Acoust. Speech Signal Process., 1987, ASSP-35, pp. 1223–1225 (doi: 10.1109/TASSP.1987.1165266).
-
19)
-
19. Ye, Y., Zhang, S.: ‘New results on quadratic minimization’, SIAM J. Optim., 2003, 14, (l), pp. 245–267 (doi: 10.1137/S105262340139001X).
-
20)
-
31. Pataki, G.: ‘On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues’, Math. Oper. Res., 1998, 23, (2), pp. 339–358 (doi: 10.1287/moor.23.2.339).
-
21)
-
14. Beck, A., Stoica, P., Li, J.: ‘Exact and approximate solutions of source localization problems’, IEEE Trans. Signal Process., 2008, 56, (5), pp. 1770–1778 (doi: 10.1109/TSP.2007.909342).
-
22)
-
4. Wang, C., Brandstein, M.S.: ‘A hybrid real-time face tracking system’. Proc. IEEE ICASSP, 1998, Vol. 6, pp. 3737–3741.
-
23)
-
29. Grant, M., Boyd, S.: .
-
24)
-
23. Xu, E., Ding, Z., Dasgupta, S.: ‘Source localization in wireless sensor networks from signal time-of-arrival measurements’, IEEE Trans. Signal Process., 2011, 59, (6), pp. 2887–2897 (doi: 10.1109/TSP.2011.2116012).
-
25)
-
25. Gholami, M., Gezici, S., Strom, E.: ‘A concave-convex procedure for TDOA based positioning’, IEEE Commun. Lett., 2013, 17, pp. 765–768 (doi: 10.1109/LCOMM.2013.020513.122732).
-
26)
-
2. Beck, A., Eldar, Y.C.: ‘Strong duality in nonconvex quadratic optimization with two quadratic constraints’, SIAM J. Optim., 2006, 17, (3), pp. 844–860 (doi: 10.1137/050644471).
-
27)
-
36. Golub, G.H., Van Loan, C.F.: ‘Matrix computations’ (Johns Hopkins University Press, 1996, 3rd edn.).
-
28)
-
26. Boyd, S., Vandenberghe, L.: ‘Convex optimization’ (Cambridge U.K., Cambridge University Press, 2003).
-
29)
-
28. Lutkepohl, H.: ‘Handbook of matrices’ (John Wiley & Sons Ltd., Chichester, 1996).
-
30)
-
30. Barvinok, A.: ‘Problems of distance geometry and convex properties of quadratic maps’, Discrete Comput. Geom., 1995, 13, (2), pp. 189–202 (doi: 10.1007/BF02574037).
-
31)
-
3. Rabinkin, D.V., Ranomeron, R.J., French, J.C., Flanagan, J.L.: ‘A DSP implementation of source location using microphone arrays’. Proc. SPIE, 1996, Vol. 2846, pp. 88–99.
-
32)
-
Y.T. Chan ,
K.C. Ho
.
A simple and efficient estimator for hyperbolic location.
IEEE Trans. Signal Process.
,
8 ,
1905 -
1915
-
33)
-
33. Jeyakumar, V., Wolkowicz, H.: ‘Generalizations of Slater's constraint qualification for infinite convex programs’, Math. Program., 1992, 57, (1), pp. 85–101 (doi: 10.1007/BF01581074).
-
34)
-
21. Lui, K.W.K., Chan, F.K.W., So, H.C.: ‘Semidefinite programming approach for range-difference based source localization’, IEEE Trans. Signal Process., 2009, 57, (4), pp. 1631–1633 (doi: 10.1109/TSP.2008.2010599).
-
35)
-
16. Yang, K., An, J., Xu, Z.: ‘A quadratic constraint total least-squares algorithm for hyperbolic location’, Int. J. Commun. Netw. Syst. Sci., 2008, 2, pp. 105–206.
-
36)
-
15. Stoica, P., Li, J.: ‘Source localization from range-difference measurements’, IEEE Signal Process. Mag., 2006, 23, pp. 63–69 (doi: 10.1109/SP-M.2006.248717).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-spr.2013.0457
Related content
content/journals/10.1049/iet-spr.2013.0457
pub_keyword,iet_inspecKeyword,pub_concept
6
6