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 176
- Downloads 0
Performance Assessment of High Availability Clustered Computing using LVS-NAT
High availability cluster computing environment attempts to provide high availability to computing services. This paper evaluates building and investigating a highly available computing enviro...
Designing, Planning & Implementation of IT Infrastructure & Security for A Brokerage House
M-Commerce is widely known as wireless network technology, use as the essential means of communication for business transactions. Mobile commerce is seen as an augmentation of E-commerce empowered by cell phones. Transac...
Prototyping Non-holonomic Hovercraft for Path Planning and Obstacle Avoidance
Abstract— By definition, autonomous control systems are the systems that sense the physical quantities from their environment and may execute any dirty, difficult, dull and dangerous task without any intervention. These...
Tackling Demolition Waste – An en route to Sustainable Development
In Pakistan, construction and demolition waste (CDW) is generated in voluminous amount each year. CDW is widely ill-handled and ultimately fed to landfills causing harm to the already alarming environmental conditions. I...
Lifespan and Decomposition Effects of 1st and 3 rd Generation Silicon Solar Cell with respect to Environment and Health
Utilization of solar photovoltaic is increasing day by day to reduce dependence on the power grid. Decomposition of 1st and 3rd generation silicon solar cells not only depends upon the plastic and other materials but als...