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 178
- Downloads 0
AUGMENTING WALKABILITY, VISIBILITY AND ARRANGEMENT FOR KOREAN ICU
Abstract—Clinical teams are facing increasing demands to perform more consistently and efficiently in delivering improved health outcomes. Hospital management team in Korea face difficulties in complex routine task for n...
Factors Affecting the Need for Feasibility Analysis (For Local Construction Projects)
In Pakistan, the majority of the local construction projects are opted without feasibility analysis on the basis of previously worked data without examining the current scenario. However, for foreign-funded project feasi...
Fluid Dispenser Prototype: A Time Based Approach
In today's era when precise, accurate and time efficient systems are in great demand, automated techniques supersede manual practices. As a need of time, we introduce a wireless, automated, cost effective, yet reliable a...
Importance of Information Availability, its effects on Business & the proposed Model
Abstract—Many a time the irony one can face is the unavailability of the resources when they are needed the most causing unavoidable/irreversible loss. These kinds of scenarios can cost organizations their business. Ente...
Design, Development & Evaluation of a Prototype Tracked Mobile Robot for Difficult Terrain
This paper reports the design, development and evaluation of a prototype tracked mobile robot for task execution in both natural and human-made environments with stair climbing feature. First, different types of locomoti...