PASTIC Dspace Repository

A Novel Minimization Method for Sensor Deployment Via Heuristic 2-Sat Solution

Show simple item record

dc.contributor.author Ahmed, Waleed
dc.contributor.author Ali, Muhammad
dc.contributor.author Rushdi, Ali
dc.date.accessioned 2022-10-24T11:30:12Z
dc.date.available 2022-10-24T11:30:12Z
dc.date.issued 2017-01-20
dc.identifier.citation Ahmad, W., & Rushdi, A. M. A. (2017). A novel minimization method for sensor deployment via heuristic 2-sat solution. Sir Syed University Research Journal of Engineering & Technology, 7(1), 1-7. en_US
dc.identifier.issn 19997-0641
dc.identifier.uri http://142.54.178.187:9060/xmlui/handle/123456789/13646
dc.description.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. en_US
dc.language.iso en en_US
dc.publisher Karachi: Sir Syed University Research Journal Engineering and Technology. en_US
dc.subject Boolean Satisfiability (SAT) en_US
dc.subject Integer linear programming en_US
dc.subject Pseudo-Boolean SAT-Solvers, en_US
dc.subject sensor deployment en_US
dc.title A Novel Minimization Method for Sensor Deployment Via Heuristic 2-Sat Solution en_US
dc.type Article en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account