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

Main Article Content

Ali Muhammad Ali Rushdi Waleed Ahmed

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.

Article Details

How to Cite
RUSHDI, Ali Muhammad Ali; AHMED, Waleed. A NOVEL MINIMIZATION METHOD FOR SENSOR DEPLOYMENT VIA HEURISTIC 2-SAT SOLUTION. 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: 20 sep. 2018.
Section
Articles

References

Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002). Wireless sensor networks: a survey. Computer networks, 38(4), 393-422.
[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.

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.