Integer programming formulation for contention aware connected dominating set in wireless multi-hop network
dc.contributor.author | Nawrin Ferdous, Chowdhury | |
dc.contributor.author | University of Lethbridge. Faculty of Arts and Science | |
dc.contributor.supervisor | Gaur, Daya | |
dc.date.accessioned | 2020-09-03T21:11:03Z | |
dc.date.available | 2020-09-03T21:11:03Z | |
dc.date.issued | 2020 | |
dc.degree.level | Masters | en_US |
dc.description.abstract | Efficient data propagation across the mobile nodes is an essential concern in wireless networks. Broadcasting with Minimum Connected Dominating Set (MCDS) is used to reduce redundant transmission. Contention occurs when a group of nodes want to transmit over a shared channel at the same time. During contention, nodes defer transmissions for a random time. Using Contention-aware Connected Dominating Set (CACDS) to minimize contention is a new concept. We study computationally (using CPLEX) Integer Programming for MCDS and CACDS and use Benders Decomposition to solve the problem. To find a connected dominating set, we use one state-of-art approach based on the shortest path algorithm, and ours one is based on the number of connected components.We propose IP formulation of selection forwarding-nodes based on Dominant Pruning and Contention-aware Dominant Pruning. The result shows that our approach performs better than the state-of-art approach in large networks. CACDS results better in minimizing contention. | en_US |
dc.identifier.uri | https://hdl.handle.net/10133/5757 | |
dc.language.iso | en | en_US |
dc.proquest.subject | 984 | en_US |
dc.proquestyes | Yes | en_US |
dc.publisher | Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science | en_US |
dc.publisher.department | Department of Mathematics and Computer Science | en_US |
dc.publisher.faculty | Arts and Science | en_US |
dc.relation.ispartofseries | Thesis (University of Lethbridge. Faculty of Arts and Science) | en_US |
dc.subject | Contention | en_US |
dc.subject | Integer Programming | en_US |
dc.subject | Minimum Connected Dominating Set | en_US |
dc.subject | Benders Decomposition | en_US |
dc.subject | Contention resolution protocols (Computer network protocols) | en_US |
dc.subject | Wireless communication systems -- Management | en_US |
dc.subject | Ad hoc networks (Computer networks) | en_US |
dc.subject | Routing (Computer network management) | en_US |
dc.subject | Combinatorial optimization | en_US |
dc.subject | Dissertations, Academic | en_US |
dc.title | Integer programming formulation for contention aware connected dominating set in wireless multi-hop network | en_US |
dc.type | Thesis | en_US |