A NOVEL MINIMIZATION METHOD FOR SENSOR DEPLOYMENT VIA HEURISTIC 2-SAT SOLUTION
Journal Title: Sir Syed University Reseacrh Journal of Engineering and Technology - Year 2017, Vol 7, Issue
Abstract
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.
Authors and Affiliations
Waleed Ahmed, Ali Muhammad Ali Rushdi
Keywords
Related Articles
- EP ID EP432729
- DOI -
- Views 164
- Downloads 0
Deployment of Sensors to Optimize the Network Coverage Using Genetic Algorithm
Wireless Sensor Networks (WSNs) are commonly used in various pervasive applications. Wireless communication is the fastest growing segment of the communication industry that has captured attention of the media and imagin...
Human Heart Disease Prediction System Using Data Mining Techniques
— Prediction of heart disease is a big issue in now a day because in electronic life everyone is busy and due to heavy load of work people do not give attention to their health. To diagnose a disease is a big issue. The...
Learning Analytics: A Data Mining and Machine Learning Perspective
Tremendous proliferation in data generation in the past few years has paved the way for new research and the development of new and improved techniques and algorithms in different fields of science and education. Initial...
Impact of Sales Force Automation System on Performance of Salesman: Pakistani Companies’ Perspective
Rapid growth in advance technologies has changed the life of sales force. Sales Force Automation (SFA) is marketing tool which provides the functions to sales team and managers to monitor sales, forecast sales and analyz...
Audible Tool for Color Identification Using Arduino UNO
This hardware tool is designed for assistance and training for visually impaired people to identify the surrounding colored objects. Several researches are conducted all over the world to design advanced, reliable tool a...