September  2019, 9(3): 361-382. doi: 10.3934/naco.2019024

Optimum sensor placement for localization of a hazardous source under log normal shadowing

1. 

GE Global Research Center, 1 Research Circle, Niskayuna, NY, 12308, USA

2. 

Department of Electrical and Computer Engineering, University of Iowa, Iowa City, IA 52242 USA

3. 

Shandong Computer Science Center, Shandong Provincial Key Laboratory of Computer Networks, China

4. 

Department of Electrical and Computer Engineering, University of California, Davis, CA 95616, USA

* Corresponding author: dasgupta@engineering.uiowa.edu

Received  June 2018 Revised  April 2019 Published  May 2019

We consider the problem of optimum sensor placement for localizing a hazardous source located inside an $ N $-dimensional hypersphere centered at the origin with a known radius $ r_1 $. All one knows about the probability density function (pdf) of the source location is that it is spherically symmetric, i.e. it is a function only of the distance from the center. The sensors must be placed at a safe distance of at least $ r_2>r_1 $ from the center, to avoid damage. Localization must be effected from the strength of a signal emanating from the source, as received by a set of sensors that do not lie on an $ (N-1) - $ dimensional hyperplane. Under the assumption that this signal strength experiences log normal shadowing, we characterize non-coplanar sensor positions that optimize three distinguished parameters associated with the underlying Fisher Information Matrix (FIM): maximizing its smallest eigenvalue, maximizing its determinant, and minimizing the trace of its inverse. We show that all three have the same set of optimizing solutions and involve placing the sensors on the surface of the hypersphere of radius $ r_2. $ As spherical symmetry of the pdf precludes uniqueness we provide certain canonical optimizing solutions where the $ i $-th sensor position $ x_i = Q^{i-1}x_1 $, with $ Q $ an orthogonal matrix. We provide necessary and sufficient conditions on $ Q $ and $ x_1 $ for $ x_i $ to be non-coplanar and optimizing. In addition, we provide a geometrical interpretation of these solutions. We observe the $ N $-dimensional solutions for $ N>3 $ have implications for optimal design of sensing matrices in certain compressed sensing problems.

Citation: Hema K. Achanta, Soura Dasgupta, Raghuraman Mudumbai, Weiyu Xu, Zhi Ding. Optimum sensor placement for localization of a hazardous source under log normal shadowing. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 361-382. doi: 10.3934/naco.2019024
References:
[1]

J. S. Abel, Optimal sensor placement for passive source localization, Proceedings of International Conference on Acoustics, Speech, and Signal Processing(ICASSP), 5 (1990), 2927-2930.

[2]

H. K. Achanta, S. Dasgupta and Z. Ding, Optimum sensor placement for localization in three dimensional under log normal shadowing, Proceedings of the International Congress on Image and Signal Processing (CISP), (2012), 1898–1901.

[3]

H. Achanta, W. Xu and S. Dasgupta, Matrix design for optimal sensing, Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, (2013), 4021–4025.

[4]

I. F. Akyildiz and M. C. Vuran, Wireless Sensor Networks, Advanced Texts in Communications and Networking, John Wiley & Sons, 2010.

[5]

A. N. Bishop, B. Fidan, B. D. O. Anderson, K. Dogancay and P. N. Pathirana, Optimality analysis of sensor-target localization geometries, Automatica, 46 (2010), 479-492. doi: 10.1016/j.automatica.2009.12.003.

[6]

R. BodorA. DrennerP. Schrater and N. Papanikolopoulos, Optimal camera placement for automated surveillance tasks, Journal of Intelligent and Robotic Systems, 50 (2007), 257-295.

[7]

G. Calafiore, F. Dabbene and R. Tempo, Radial and uniform distributions in vector and matrix spaces for probabilistic robustness, Topics in Control and its Applications, Springer London, (1999), 17–31.

[8]

C. D. Cordeiro and D.P. Agrawal, Ad Hoc and Sensor Networks: Theory and Applications, , World Scientific, 2011.

[9]

C. T. Chen, Linear System Theory and Design, 4th Edition, 2013.

[10]

J. Chaffee and J. Abel, GDOP and the Cramer-Rao bound, Proceedings of IEEE Symposium on Position Location and Navigation, (1994), 663–668.

[11]

S. H. Dandach, B. Fidan, S. Dasgupta and B. D. O. Anderson, Adaptive source localization by mobile agents, Proceedings of the 45th IEEE Conference on Decision and Control, (2006), 2045–2050.

[12]

S. H. DandachB. FidanS. Dasgupta and B. D. O. Anderson, A continuous time linear adaptive source localization algorithm, robust to persistent drift, Systems and Control Letters, 58 (2009), 7-16. doi: 10.1016/j.sysconle.2008.07.008.

[13]

S. DasguptaS. R. Ibeawauchi and Z. Ding, Optimum sensor placement for source monitoring under log-normal shadowing, Proceedings of IFAC Workshop on System Identification, 42 (2009), 1710-1714.

[14]

S. Dasgupta, S. C. Ibeawuchi and Z. Ding, Optimum sensor placement for localization under log-normal shadowing, Proceedings of the International Symposium on Communications and Information Technologies (ISCIT), (2010), 204–208.

[15]

S. Dasgupta, S. R. C. Ibeawuchi and Z. Ding, Optimum sensor placement for source monitoring under log-normal shadowing in three dimensions, Proceedings of the 9th International Conference on Communications and Information Technologies, (2009), 376–381.

[16]

B. FidanS. Dasgupta and B. D. O. Anderson, Guaranteeing practical convergence in algorithms for sensor and source localization, IEEE Transactions on Signal Processing, 56 (2008), 4458-4469. doi: 10.1109/TSP.2008.924138.

[17]

G. H. Forman and J. Zahorjan, The challenges of mobile computing, IEEE Computer, 27 (1994), 38-47.

[18]

J. T. Isaacs, D. J. Klein and J. P. Hespanha, Optimal sensor placement for time difference of arrival localization, Proceedings of the 48th IEEE Conference on Decision and Control, (2009), 7878–7884.

[19]

D. B. Jourdan and N. Roy, Optimal sensor placement for agent localization, ACM Transactions on Sensor Networks, 4 (2008), 13: 1–13: 40

[20]

B. Karp and H. T Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, (2000), 243–254.

[21]

P. Lancaster and M. Tismenetsky, The Theory of Matrices,, Computer Science and Applied Mathematics, Academic Press, 1985.

[22]

A. W. Marshall, I. Olkin and B. Arnold, Inequalities: Theory of Majorization and Its Applications, , Springer Series in Statistics, Springer, 2010. doi: 10.1007/978-0-387-68276-1.

[23]

S. Martinez and F. Bullo, Optimal sensor placement and motion coordination for target tracking, Automatica, 42 (2006), 661-668. doi: 10.1016/j.automatica.2005.12.018.

[24]

W. MengL. Xie and W. Xiao, Optimality analysis of sensor-source geometries in Heterogeneous sensor networks, IEEE Transactions on Wireless Communications, 12 (2013), 1958-1967.

[25]

J. Neering, M. Bordier and N. Maizi, Optimal passive source localization, Proceedings of International Conference on Sensor Technologies and Applications (SensorComm), (2007), 295–300.

[26]

T. O'Donovan, J. O'Donoghue, C. Sreenan, D. Sammon, P. O'Reilly and K. A. O'Connor, A context aware wireless body area network (ban), Proceedings of the 3rd International Conference on Pervasive Computing Technologies for Healthcare, (2009), 1–8.

[27]

N. PatwariJ. N. AshS. KyperountasA. O. HeroR. L. Moses and N. S. Correal, Locating the nodes: cooperative localization in wireless sensor networks, IEEE Signal Processing Magazine, 22 (2005), 54-69. doi: 10.1109/MSP.2005.1458287.

[28]

F. Pukelsheim, Optimal Design of Experiments, , Wiley, 1993.

[29]

M. Rabbat and R. Nowak, Distributed optimization in sensor networks, Proceedings of International Symposium on Information Processing in Sensor Networks (IPSN), (2004), 20–27.

[30]

M. G. Rabbat and R. D. Nowak, Decentralized source localization and tracking [wireless sensor networks], Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 3 (2004).

[31]

L. Ran, S. Helal and S. Moore, Drishti: An integrated indoor/outdoor blind navigation system and service, Proceedings of the Second IEEE International Conference on Pervasive Computing and Communications (PerCom), (2004), 23–30.

[32]

T. S. Rappaport, Wireless Communications: Principles and Practice, , Prentice Hall communications engineering and emerging technologies series, Prentice Hall PTR, 2002.

[33]

A. H. SayedA. Tarighat and and N. Khajehnouri, Network-based wireless location: challenges faced in developing techniques for accurate wireless location information, IEEE Signal Processing Magazine, 22 (2005), 24-40. doi: 10.1109/MSP.2005.1458275.

[34]

L. L. Scharf and L.vT. McWhorter, Geometry of the Cramer-Rao bound}, Signal Processing, 31 (1993), 301-311.

[35]

O. Tekdas and V. Isler, Sensor placement for triangulation-based localization, IEEE Transactions on Automation Science and Engineering, 7 (2010), 681-685.

[36]

H. L. Van Trees, Detection, Estimation, and Modulation Theory: Detection, Estimation, and Linear Modulation Theory, Wiley, 2001.

[37]

Y. Wang and W. Xiong, Anchor-based three-dimensional localization using range measurements, Proceedings of International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), (2012), 1–5.

[38]

S. Wang, B. R. Jackson and R. J. Inkol, Impact of emitter-sensor geometry on accuracy of received signal strength based geolocation, Proceedings of IEEE Conference on Vehicular Technology, (2011), 1–5.

[39]

M. Weiser, Some computer science issues in ubiquitous computing, Communications of the ACM - Special Issue on Computer Augmented Environments: Back to the Real World, 36 (1993), 75–84.

[40]

E. Xu, Z. Ding and S. Dasgupta, Reduced complexity semidefinite relaxation algorithms for source localization based on time difference of arrival, IEEE Transactions on Mobile Computing, (2011), 1276-1282. doi: 10.1109/TMC.2010.263.

[41]

E. Xu, Z. Ding and S. Dasgupta, Robust and low complexity source localization in wireless sensor networks using time difference of arrival measurement, 2010 IEEE Wireless Communication and Networking Conference, (2010), 1-5.

[42]

E. XuZ. Ding and S. Dasgupta, Source localization in wireless sensor networks from signal time-of-arrival measurements, IEEE Transactions on Signal Processing, 59 (2009), 2887-2897. doi: 10.1109/TSP.2011.2116012.

show all references

References:
[1]

J. S. Abel, Optimal sensor placement for passive source localization, Proceedings of International Conference on Acoustics, Speech, and Signal Processing(ICASSP), 5 (1990), 2927-2930.

[2]

H. K. Achanta, S. Dasgupta and Z. Ding, Optimum sensor placement for localization in three dimensional under log normal shadowing, Proceedings of the International Congress on Image and Signal Processing (CISP), (2012), 1898–1901.

[3]

H. Achanta, W. Xu and S. Dasgupta, Matrix design for optimal sensing, Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, (2013), 4021–4025.

[4]

I. F. Akyildiz and M. C. Vuran, Wireless Sensor Networks, Advanced Texts in Communications and Networking, John Wiley & Sons, 2010.

[5]

A. N. Bishop, B. Fidan, B. D. O. Anderson, K. Dogancay and P. N. Pathirana, Optimality analysis of sensor-target localization geometries, Automatica, 46 (2010), 479-492. doi: 10.1016/j.automatica.2009.12.003.

[6]

R. BodorA. DrennerP. Schrater and N. Papanikolopoulos, Optimal camera placement for automated surveillance tasks, Journal of Intelligent and Robotic Systems, 50 (2007), 257-295.

[7]

G. Calafiore, F. Dabbene and R. Tempo, Radial and uniform distributions in vector and matrix spaces for probabilistic robustness, Topics in Control and its Applications, Springer London, (1999), 17–31.

[8]

C. D. Cordeiro and D.P. Agrawal, Ad Hoc and Sensor Networks: Theory and Applications, , World Scientific, 2011.

[9]

C. T. Chen, Linear System Theory and Design, 4th Edition, 2013.

[10]

J. Chaffee and J. Abel, GDOP and the Cramer-Rao bound, Proceedings of IEEE Symposium on Position Location and Navigation, (1994), 663–668.

[11]

S. H. Dandach, B. Fidan, S. Dasgupta and B. D. O. Anderson, Adaptive source localization by mobile agents, Proceedings of the 45th IEEE Conference on Decision and Control, (2006), 2045–2050.

[12]

S. H. DandachB. FidanS. Dasgupta and B. D. O. Anderson, A continuous time linear adaptive source localization algorithm, robust to persistent drift, Systems and Control Letters, 58 (2009), 7-16. doi: 10.1016/j.sysconle.2008.07.008.

[13]

S. DasguptaS. R. Ibeawauchi and Z. Ding, Optimum sensor placement for source monitoring under log-normal shadowing, Proceedings of IFAC Workshop on System Identification, 42 (2009), 1710-1714.

[14]

S. Dasgupta, S. C. Ibeawuchi and Z. Ding, Optimum sensor placement for localization under log-normal shadowing, Proceedings of the International Symposium on Communications and Information Technologies (ISCIT), (2010), 204–208.

[15]

S. Dasgupta, S. R. C. Ibeawuchi and Z. Ding, Optimum sensor placement for source monitoring under log-normal shadowing in three dimensions, Proceedings of the 9th International Conference on Communications and Information Technologies, (2009), 376–381.

[16]

B. FidanS. Dasgupta and B. D. O. Anderson, Guaranteeing practical convergence in algorithms for sensor and source localization, IEEE Transactions on Signal Processing, 56 (2008), 4458-4469. doi: 10.1109/TSP.2008.924138.

[17]

G. H. Forman and J. Zahorjan, The challenges of mobile computing, IEEE Computer, 27 (1994), 38-47.

[18]

J. T. Isaacs, D. J. Klein and J. P. Hespanha, Optimal sensor placement for time difference of arrival localization, Proceedings of the 48th IEEE Conference on Decision and Control, (2009), 7878–7884.

[19]

D. B. Jourdan and N. Roy, Optimal sensor placement for agent localization, ACM Transactions on Sensor Networks, 4 (2008), 13: 1–13: 40

[20]

B. Karp and H. T Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, (2000), 243–254.

[21]

P. Lancaster and M. Tismenetsky, The Theory of Matrices,, Computer Science and Applied Mathematics, Academic Press, 1985.

[22]

A. W. Marshall, I. Olkin and B. Arnold, Inequalities: Theory of Majorization and Its Applications, , Springer Series in Statistics, Springer, 2010. doi: 10.1007/978-0-387-68276-1.

[23]

S. Martinez and F. Bullo, Optimal sensor placement and motion coordination for target tracking, Automatica, 42 (2006), 661-668. doi: 10.1016/j.automatica.2005.12.018.

[24]

W. MengL. Xie and W. Xiao, Optimality analysis of sensor-source geometries in Heterogeneous sensor networks, IEEE Transactions on Wireless Communications, 12 (2013), 1958-1967.

[25]

J. Neering, M. Bordier and N. Maizi, Optimal passive source localization, Proceedings of International Conference on Sensor Technologies and Applications (SensorComm), (2007), 295–300.

[26]

T. O'Donovan, J. O'Donoghue, C. Sreenan, D. Sammon, P. O'Reilly and K. A. O'Connor, A context aware wireless body area network (ban), Proceedings of the 3rd International Conference on Pervasive Computing Technologies for Healthcare, (2009), 1–8.

[27]

N. PatwariJ. N. AshS. KyperountasA. O. HeroR. L. Moses and N. S. Correal, Locating the nodes: cooperative localization in wireless sensor networks, IEEE Signal Processing Magazine, 22 (2005), 54-69. doi: 10.1109/MSP.2005.1458287.

[28]

F. Pukelsheim, Optimal Design of Experiments, , Wiley, 1993.

[29]

M. Rabbat and R. Nowak, Distributed optimization in sensor networks, Proceedings of International Symposium on Information Processing in Sensor Networks (IPSN), (2004), 20–27.

[30]

M. G. Rabbat and R. D. Nowak, Decentralized source localization and tracking [wireless sensor networks], Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 3 (2004).

[31]

L. Ran, S. Helal and S. Moore, Drishti: An integrated indoor/outdoor blind navigation system and service, Proceedings of the Second IEEE International Conference on Pervasive Computing and Communications (PerCom), (2004), 23–30.

[32]

T. S. Rappaport, Wireless Communications: Principles and Practice, , Prentice Hall communications engineering and emerging technologies series, Prentice Hall PTR, 2002.

[33]

A. H. SayedA. Tarighat and and N. Khajehnouri, Network-based wireless location: challenges faced in developing techniques for accurate wireless location information, IEEE Signal Processing Magazine, 22 (2005), 24-40. doi: 10.1109/MSP.2005.1458275.

[34]

L. L. Scharf and L.vT. McWhorter, Geometry of the Cramer-Rao bound}, Signal Processing, 31 (1993), 301-311.

[35]

O. Tekdas and V. Isler, Sensor placement for triangulation-based localization, IEEE Transactions on Automation Science and Engineering, 7 (2010), 681-685.

[36]

H. L. Van Trees, Detection, Estimation, and Modulation Theory: Detection, Estimation, and Linear Modulation Theory, Wiley, 2001.

[37]

Y. Wang and W. Xiong, Anchor-based three-dimensional localization using range measurements, Proceedings of International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), (2012), 1–5.

[38]

S. Wang, B. R. Jackson and R. J. Inkol, Impact of emitter-sensor geometry on accuracy of received signal strength based geolocation, Proceedings of IEEE Conference on Vehicular Technology, (2011), 1–5.

[39]

M. Weiser, Some computer science issues in ubiquitous computing, Communications of the ACM - Special Issue on Computer Augmented Environments: Back to the Real World, 36 (1993), 75–84.

[40]

E. Xu, Z. Ding and S. Dasgupta, Reduced complexity semidefinite relaxation algorithms for source localization based on time difference of arrival, IEEE Transactions on Mobile Computing, (2011), 1276-1282. doi: 10.1109/TMC.2010.263.

[41]

E. Xu, Z. Ding and S. Dasgupta, Robust and low complexity source localization in wireless sensor networks using time difference of arrival measurement, 2010 IEEE Wireless Communication and Networking Conference, (2010), 1-5.

[42]

E. XuZ. Ding and S. Dasgupta, Source localization in wireless sensor networks from signal time-of-arrival measurements, IEEE Transactions on Signal Processing, 59 (2009), 2887-2897. doi: 10.1109/TSP.2011.2116012.

Figure 1.  (a) Illustration of optimum sensor placement in two dimensions using four sensors. (b) Illustration of optimum sensor placement in three dimensions using six sensors and sphere of radius of 2 (i.e.r2 = 2)
Figure 2.  Plot of determinant of FIM Versus Number of sensors in the network
Figure 3.  Plot of Minimum Eigenvalue of FIM Versus Number of sensors in the network
Figure 4.  Plot of $10log_{10}$(Average Normalized Mean square error in the source location) Versus Signal to Noise Ratio (dB). Red dotted line represents the performance of the random placement. Blue line represents the performance of the proposed optimum sensor placement
[1]

Yuanjia Ma. The optimization algorithm for blind processing of high frequency signal of capacitive sensor. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1399-1412. doi: 10.3934/dcdss.2019096

[2]

Changzhi Wu, Chaojie Li, Qiang Long. A DC programming approach for sensor network localization with uncertainties in anchor positions. Journal of Industrial & Management Optimization, 2014, 10 (3) : 817-826. doi: 10.3934/jimo.2014.10.817

[3]

Jonathan Zinsl. The gradient flow of a generalized Fisher information functional with respect to modified Wasserstein distances. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 919-933. doi: 10.3934/dcdss.2017047

[4]

Klas Modin. Geometry of matrix decompositions seen through optimal transport and information geometry. Journal of Geometric Mechanics, 2017, 9 (3) : 335-390. doi: 10.3934/jgm.2017014

[5]

Sergei Yu. Pilyugin. Variational shadowing. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 733-737. doi: 10.3934/dcdsb.2010.14.733

[6]

João Borges de Sousa, Bernardo Maciel, Fernando Lobo Pereira. Sensor systems on networked vehicles. Networks & Heterogeneous Media, 2009, 4 (2) : 223-247. doi: 10.3934/nhm.2009.4.223

[7]

Weinan E, Weiguo Gao. Orbital minimization with localization. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 249-264. doi: 10.3934/dcds.2009.23.249

[8]

Radu Balan, Peter G. Casazza, Christopher Heil and Zeph Landau. Density, overcompleteness, and localization of frames. Electronic Research Announcements, 2006, 12: 71-86.

[9]

Luisa Berchialla, Luigi Galgani, Antonio Giorgilli. Localization of energy in FPU chains. Discrete & Continuous Dynamical Systems - A, 2004, 11 (4) : 855-866. doi: 10.3934/dcds.2004.11.855

[10]

Seung-Yeal Ha, Dongnam Ko, Yinglong Zhang. Remarks on the critical coupling strength for the Cucker-Smale model with unit speed. Discrete & Continuous Dynamical Systems - A, 2018, 38 (6) : 2763-2793. doi: 10.3934/dcds.2018116

[11]

Thanh-Tung Pham, Thomas Green, Jonathan Chen, Phuong Truong, Aditya Vaidya, Linda Bushnell. A salinity sensor system for estuary studies. Networks & Heterogeneous Media, 2009, 4 (2) : 381-392. doi: 10.3934/nhm.2009.4.381

[12]

Keonhee Lee, Kazuhiro Sakai. Various shadowing properties and their equivalence. Discrete & Continuous Dynamical Systems - A, 2005, 13 (2) : 533-540. doi: 10.3934/dcds.2005.13.533

[13]

Shaobo Gan. A generalized shadowing lemma. Discrete & Continuous Dynamical Systems - A, 2002, 8 (3) : 627-632. doi: 10.3934/dcds.2002.8.627

[14]

Sergey V. Bolotin. Shadowing chains of collision orbits. Discrete & Continuous Dynamical Systems - A, 2006, 14 (2) : 235-260. doi: 10.3934/dcds.2006.14.235

[15]

S. Yu. Pilyugin, A. A. Rodionova, Kazuhiro Sakai. Orbital and weak shadowing properties. Discrete & Continuous Dynamical Systems - A, 2003, 9 (2) : 287-308. doi: 10.3934/dcds.2003.9.287

[16]

S. Yu. Pilyugin. Inverse shadowing by continuous methods. Discrete & Continuous Dynamical Systems - A, 2002, 8 (1) : 29-38. doi: 10.3934/dcds.2002.8.29

[17]

Sergey Kryzhevich, Sergey Tikhomirov. Partial hyperbolicity and central shadowing. Discrete & Continuous Dynamical Systems - A, 2013, 33 (7) : 2901-2909. doi: 10.3934/dcds.2013.33.2901

[18]

Lianfa He, Hongwen Zheng, Yujun Zhu. Shadowing in random dynamical systems. Discrete & Continuous Dynamical Systems - A, 2005, 12 (2) : 355-362. doi: 10.3934/dcds.2005.12.355

[19]

Jifeng Chu, Zhaosheng Feng, Ming Li. Periodic shadowing of vector fields. Discrete & Continuous Dynamical Systems - A, 2016, 36 (7) : 3623-3638. doi: 10.3934/dcds.2016.36.3623

[20]

Will Brian, Jonathan Meddaugh, Brian Raines. Shadowing is generic on dendrites. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 2211-2220. doi: 10.3934/dcdss.2019142

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]