# A NOVEL MINIMIZATION METHOD FOR SENSOR DEPLOYMENT VIA HEURISTIC 2-SAT SOLUTION

### Abstract

**The tasks of guard placement or sensor deployment in an art gallery, a museum or in the corridors of public and security buildings pose the same problem, which requires placing the guards or sensors so as to cover a specified set of nodes with a minimum number of sensors or guards, thereby reducing the overall cost of the system as well assist power consumption. Generally, minimization can be done using optimization techniques such as linear programming, but in case of sensor deployment or guard placement there is a need either to place or not to place the sensor or guard, and hence only Boolean or binary values are used. Therefore, in order to optimize such a problem, we use the special case of linear integer programming known as Boolean integer linear programming (0-1 ILP). Other algorithms like Pseudo-Boolean SAT Solvers can also be used for the minimization purpose. In this paper, we introduce these minimization algorithms for the sensor deployment problem. We also contribute a greed-based heuristic, which utilizes the fact that the pertinent propositional formulas have variables of purely un-complemented literals. This heuristic has much less computational cost compared to those of 0-1 ILP and the Pseudo-Boolean SAT Solvers.**

### References

[2] Huang, C. F., & Tseng, Y. C. (2005). The coverage problem in a wireless sensor network. Mobile Networks and Applications, 10(4), 519-528.

[3] Rao, N. S. V. (1993). Computational complexity issues in operative diagnosis of graph-based systems. IEEE Transactions on Computers, 42(4), 447-457.

[4] O'rourke, J. (1987). Art gallery theorems and algorithms (Vol. 57). Oxford: Oxford University Press.

[5] Khan, F. H., Shams, R., Umair, M., & Waseem, M. (2012). Deployment of sensors to optimize the network coverage using genetic algorithm. Sir Syed University Research Journal of Engineering and Technology, 2(1), 8-11.

[6] Liu, J., Yang, X., Liu, H. L., & Qiao, Z. (2014). Sensor nodes deployment strategy for monitoring roadside biomass carbon stocks of tourism destination: a case of Wulong world natural heritage, China. Mathematical Problems in Engineering.

[7] Lovisari, E., de Wit, C. C., & Kibangou, A. Y. (2015, December). Optimal Sensor Placement in Road Transportation Networks using Virtual Variances. In Decision and Control (CDC), 2015 IEEE 54th Annual Conference on(pp. 2786-2791). IEEE.

[8] Matsuoka, Y., Durrant-Whyte, H., & Neira, J. (2011). Robotics: Science and systems VI. MIT Press.

[9] Dhillon, S. S., & Chakrabarty, K. (2003, March). Sensor placement for effective coverage and surveillance in distributed sensor networks. In Wireless Communications and Networking, 2003. WCNC 2003. 2003 IEEE (Vol. 3, pp. 1609-1614). IEEE.

[10] Rafique, F., & Siddiqui, N. (2012). Parametric comparison of selected dual elements PIR sensors. SSU Res. J. of Engg. and Tech, 2(1), 7.

[11] Steffelbauer, D. B., & Fuchs-Hanusch, D. (2016). Efficient sensor placement for leak localization considering uncertainties. Water Resources Management, 30(14), 5517-5533.

[12] Zhao, L., Bai, G., Jiang, Y., Shen, H., & Tang, Z. (2014). Optimal deployment and scheduling with directional sensors for energy-efficient barrier coverage. International Journal of Distributed Sensor Networks, 10(1), 596983.

[13] Chen, J., Jia, J., Wen, Y., & Zhao, D. (2014). Towards an optimal energy consumption for unattended mobile sensor networks through autonomous sensor redeployment. The Scientific World Journal, 2014.

[14] Nemhauser, G. L., & Wolsey, L. A. (1989). Chapter vi integer programming. Handbooks in Operations Research and Management Science, 1, 447-527.

[15] Manquinho, V. M., Silva, J. P. M., Oliveira, A. L., & Sakallah, K. A. (1998, June). Satisfiability-based algorithms for 0-1 integer programming. In Proceedings of the IEEE/ACM International Workshop on Logic Synthesis (IWLS).

[16] Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., & Malik, S. (2001, June). Chaff: Engineering an efficient SAT solver. In Proceedings of the 38th annual Design Automation Conference (pp. 530-535). ACM.

[17] Pipatsrisawat, K., & Darwiche, A. (2008, July). A New Clause Learning Scheme for Efficient Unsatisfiability Proofs. In AAAI(pp. 1481-1484).

[18] Sorensson, N., & Een, N. (2005). Minisat v1. 13-a sat solver with conflict-clause minimization. SAT, 2005(53), 1-2.

[19] Silva, J. P. M., & Sakallah, K. A. (1997, January). GRASP—a new search algorithm for satisfiability. In Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design (pp. 220-227). IEEE Computer Society.

[20] Marques-Silva, J. P., & Sakallah, K. A. (1999). GRASP: A search algorithm for propositional satisfiability. IEEE Transactions on Computers, 48(5), 506-521.

[21] Gomes, C. P., Selman, B., & Kautz, H. (1998). Boosting combinatorial search through randomization. AAAI/IAAI, 98, 431-437.

[22] Luby, M., Sinclair, A., & Zuckerman, D. (1993). Optimal speedup of Las Vegas algorithms. Information Processing Letters, 47(4), 173-180.

[23] Biere, A. (2008, May). Adaptive restart strategies for conflict driven SAT solvers. In International Conference on Theory and Applications of Satisfiability Testing (pp. 28-33). Springer, Berlin, Heidelberg.

[24] Marques-Silva, J. (1999, September). The impact of branching heuristics in propositional satisfiability algorithms. In Portuguese Conference on Artificial Intelligence (pp. 62-74). Springer, Berlin, Heidelberg.

[25] Pipatsrisawat, K., & Darwiche, A. (2007, May). A lightweight component caching scheme for satisfiability solvers. In International conference on theory and applications of satisfiability testing (pp. 294-299). Springer, Berlin, Heidelberg.

[26] De Givry, S., Larrosa, J., Meseguer, P., & Schiex, T. (2003, September). Solving Max-SAT as weighted CSP. In International conference on principles and practice of constraint programming (pp. 363-376). Springer, Berlin, Heidelberg.

[27] Bjørner, N., & Phan, A. D. (2014). νZ-Maximal Satisfaction with Z3. SCSS, 30, 1-9.

[28] Le Berre, D., & Parrain, A. (2010). The sat4j library, release 2.2, system description. Journal on Satisfiability, Boolean Modeling and Computation, 7, 59-64.

[29] Aloul, F. A., Ramani, A., Markov, I., & Sakallah, K. (2002, May). PBS: a backtrack-search pseudo-boolean solver and optimizer. In Proceedings of the 5th International Symposium on Theory and Applications of Satisfiability (pp. 346-353).

[30] Rushdi, A. M. A., & Ahmad, W. (2016). Finding all solutions of the Boolean satisfiability problem, if any, via Boolean-equation solving. Journal of King Abdulaziz University: Engineering Sciences, 27(1), 19-34.

**Sir Syed University Research Journal of Engineering & Technology**, [S.l.], v. 7, n. 1, p. 1-7, apr. 2018. ISSN 2415-2048. Available at: <http://journal.ssuet.edu.pk/index.php/ssurjet/article/view/1>. Date accessed: 24 june 2018.