Novel Optimal Multisensor Placement for Indoor Rectilinear Line-of-Sight Coverage
- 24 August 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Sensors Journal
- Vol. 21 (20) , 23435-23451
Abstract
Optimal multisensor placement/deployment for an arbitrary indoor geometry still remains very challenging nowadays. It is preferable to minimize the number of sensors which can still cover the entire indoor space with a balanced load. However, this multi-objective problem is quite complex in practice. In this work, we will study this critical multisensor placement problem mathematically and algorithmically and propose a systematic approach to tackle this problem. In this paper, we focus on the line-of-sight (LoS) coverage within a rectilinear indoor environment and the sensors’ locations are restricted on the perimeter. Our proposed new approach consists of two stages. First, a partitioning algorithm is designed to partition an arbitrary rectilinear geometry into a number (as few as possible) of feasible rectilinear subareas, each of which can be fully covered by a sensor located somewhere on its external perimeter. Second, the average squared Euclidean distance from a sensor to an arbitrary point within its coverage area is taken as an additional objective measure. By minimizing such average squared Euclidean distance, one can find the optimal sensor location. In our new approach, the first stage is related to solving the art gallery problem (AGP) based on discrete optimization while the second stage is based on continuous optimization. Therefore, our proposed new approach involves both continuous and discrete optimization schemes. By simulations, we also show that the number of sensors placed by our new algorithm is equal to or less than the theoretical upper-bound established in the existing AGP study for numerous rectilinear geometries. Moreover, we also show that by minimizing the average squared Euclidean distance, we maximize the average received signal strength indoors using the prevalent Feko wireless-channel emulator. Our proposed new systematic approach can also deal with practical scenarios involving internal obstacle(s) and sensing-range restriction.Keywords
Funding Information
- Louisiana Board of Regents Research Competitiveness Subprogram (LEQSF(2021-22)-RD-A-34)
- National Science Foundation Research Initiation Initiative (CRII) Program (1948524)
This publication has 36 references indexed in Scilit:
- Finding a Guard that Sees Most and a Shop that Sells MostDiscrete & Computational Geometry, 2007
- Optimal sensor placement and motion coordination for target trackingAutomatica, 2006
- Improved approximation algorithms for multilevel facility location problemsOperations Research Letters, 2002
- Edge guards in rectilinear polygonsComputational Geometry, 1998
- Generalized guarding and partitioning for rectilinear polygonsComputational Geometry, 1996
- Tight bounds for the number of edge guards for spiral polygonsJournal of Geometry, 1994
- Recent results in art galleries (geometry)Proceedings of the IEEE, 1992
- Minimum rectangular partition problem for simple rectilinear polygonsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1990
- A combinational approach to polygon similarityIEEE Transactions on Information Theory, 1983
- An efficient algorithm for decomposing a polygon into star-shaped polygonsPattern Recognition, 1981