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 136
- Downloads 0
Wireless Security Threats
Wireless Communication Technologies has completely revolutionized the world. Wireless Communication Technologies provide ease to the users such as portability of the devices and mobile access to the internet. These porta...
Detection and Measurement of Displacement and Velocity of Single Moving Object in a Stationary Background
The traditional Harris detector are sensitive to noise and resolution because without the property of scale invariant. In this research, The Harris corner detector algorithm is improved, to work with multi resolution im...
Techno-economic Study for Water Pumping by Solar Power Driven Three Phase Induction Motor
The paper primarily focuses on water pump irrigation by operating the three phase induction motor, using photovoltaic supply. In many far away regions, mainly in villages, the main hindrance in agricultural production is...
Fault Detection and Tolerance in Cluster of Workstations using Message Passing Interface
A Cluster of Workstations (COW) is network based multi-computer system aimed to replace supercomputers. A cluster of workstations works on Divisible Load Theory (DLT) according to which a job is divided into n subtasks a...
Implementation of Genetic Algorithms for Optimization of Transportation Problem
Abstract— Transportation problem is a model which is commonly used in data structure solving a problem (human problem solving due to the computational method) because all the humans are related to transportation in any t...