A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks
We aim to cover a grid fully by deploying the necessary wireless sensors while maintaining connectivity between the deployed sensors and a base station ( the sink ). The problem is NP - Complete as it can be reduced to a 2 - dimensional critical coverage problem, which is an NP - Complete problem. W...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-02-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1155/2014/769658 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832546743195009024 |
|---|---|
| author | Maher Rebai Matthieu Le Berre Faicel Hnaien Hichem Snoussi Lyes Khoukhi |
| author_facet | Maher Rebai Matthieu Le Berre Faicel Hnaien Hichem Snoussi Lyes Khoukhi |
| author_sort | Maher Rebai |
| collection | DOAJ |
| description | We aim to cover a grid fully by deploying the necessary wireless sensors while maintaining connectivity between the deployed sensors and a base station ( the sink ). The problem is NP - Complete as it can be reduced to a 2 - dimensional critical coverage problem, which is an NP - Complete problem. We develop a branch and bound (B&B) algorithm to solve the problem optimally. We verify by computational experiments that the proposed B&B algorithm is more efficient, in terms of computation time, than the integer linear programming model developed by Rebai et al. (2013), for the same problem. |
| format | Article |
| id | doaj-art-828f8b379e1c4a26a2bc117bcf889ed0 |
| institution | Kabale University |
| issn | 1550-1477 |
| language | English |
| publishDate | 2014-02-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-828f8b379e1c4a26a2bc117bcf889ed02025-02-03T06:47:19ZengWileyInternational Journal of Distributed Sensor Networks1550-14772014-02-011010.1155/2014/769658769658A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor NetworksMaher RebaiMatthieu Le BerreFaicel HnaienHichem SnoussiLyes KhoukhiWe aim to cover a grid fully by deploying the necessary wireless sensors while maintaining connectivity between the deployed sensors and a base station ( the sink ). The problem is NP - Complete as it can be reduced to a 2 - dimensional critical coverage problem, which is an NP - Complete problem. We develop a branch and bound (B&B) algorithm to solve the problem optimally. We verify by computational experiments that the proposed B&B algorithm is more efficient, in terms of computation time, than the integer linear programming model developed by Rebai et al. (2013), for the same problem.https://doi.org/10.1155/2014/769658 |
| spellingShingle | Maher Rebai Matthieu Le Berre Faicel Hnaien Hichem Snoussi Lyes Khoukhi A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks International Journal of Distributed Sensor Networks |
| title | A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks |
| title_full | A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks |
| title_fullStr | A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks |
| title_full_unstemmed | A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks |
| title_short | A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks |
| title_sort | branch and bound algorithm for the critical grid coverage problem in wireless sensor networks |
| url | https://doi.org/10.1155/2014/769658 |
| work_keys_str_mv | AT maherrebai abranchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks AT matthieuleberre abranchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks AT faicelhnaien abranchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks AT hichemsnoussi abranchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks AT lyeskhoukhi abranchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks AT maherrebai branchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks AT matthieuleberre branchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks AT faicelhnaien branchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks AT hichemsnoussi branchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks AT lyeskhoukhi branchandboundalgorithmforthecriticalgridcoverageprobleminwirelesssensornetworks |