MANET Cluster Optimization Using ILP/SAT Techniques
A Master of Science thesis in Computer Engineering by Syed Zohaib Hussain Zahidi entitled, "Manet Cluster Optimization Using ILP/SAT Techniques," submitted in January 2012. Thesis advisor is Dr. Fadi Ahmed Aloul and co-advisor is Dr. Assim Sagahyroon. Available are both soft and hard copie...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | doctoralThesis |
| منشور في: |
2012
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | http://hdl.handle.net/11073/2763 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513437632036864 |
|---|---|
| author | Zahidi, Syed Zohaib Hussain |
| author_facet | Zahidi, Syed Zohaib Hussain |
| author_role | author |
| dc.contributor.none.fl_str_mv | Aloul, Fadi Ahmed Sagahyroon, Assim |
| dc.creator.none.fl_str_mv | Zahidi, Syed Zohaib Hussain |
| dc.date.none.fl_str_mv | 2012-02-15T09:51:14Z 2012-02-15T09:51:14Z 2012-01 |
| dc.format.none.fl_str_mv | application/pdf |
| dc.identifier.none.fl_str_mv | 35.232-2012.04 http://hdl.handle.net/11073/2763 |
| dc.language.none.fl_str_mv | en_US |
| dc.subject.none.fl_str_mv | Clustering ILP formulation Topology Ad hoc networks (Computer networks) Linear programming |
| dc.title.none.fl_str_mv | MANET Cluster Optimization Using ILP/SAT Techniques |
| dc.type.none.fl_str_mv | info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/doctoralThesis |
| description | A Master of Science thesis in Computer Engineering by Syed Zohaib Hussain Zahidi entitled, "Manet Cluster Optimization Using ILP/SAT Techniques," submitted in January 2012. Thesis advisor is Dr. Fadi Ahmed Aloul and co-advisor is Dr. Assim Sagahyroon. Available are both soft and hard copies of the thesis. |
| format | doctoralThesis |
| id | aus_14095b2ace786c4979342e83ad1cd8c1 |
| identifier_str_mv | 35.232-2012.04 |
| language_invalid_str_mv | en_US |
| network_acronym_str | aus |
| network_name_str | aus |
| oai_identifier_str | oai:repository.aus.edu:11073/2763 |
| publishDate | 2012 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | MANET Cluster Optimization Using ILP/SAT TechniquesZahidi, Syed Zohaib HussainClusteringILP formulationTopologyAd hoc networks (Computer networks)Linear programmingA Master of Science thesis in Computer Engineering by Syed Zohaib Hussain Zahidi entitled, "Manet Cluster Optimization Using ILP/SAT Techniques," submitted in January 2012. Thesis advisor is Dr. Fadi Ahmed Aloul and co-advisor is Dr. Assim Sagahyroon. Available are both soft and hard copies of the thesis.In recent years, there have been several improvements in the performance of Integer Linear Programming (ILP) and Boolean Satisfiability (SAT) solvers. These improvements have encouraged the modeling of complex engineering problems as ILP problems. These engineering problems are diverse in nature and include genetics, optimization of power consumption, scheduling, cryptography, and more. One such problem is the "-clustering problem' in Mobile Ad-Hoc Networks (MANETs). The clustering problem in MANETs consists of selecting the most suitable nodes of a given MANET topology as clusterheads and ensuring that regular nodes are connected to clusterheads in such a way that the network lifetime is maximized. This thesis focuses on assessing the performance of state-of-the art generic ILP and 0-1 SAT-based ILP solvers in solving ILP formulations of the clustering problem. The thesis consists of four parts. The first part of this thesis consists of improving the existing ILP formulations of the clustering problem. The second part involves enhancing the ILP formulation of the clustering problem through the addition of intra-cluster communication, coverage constraints and multihop links. The third part focuses on the development of an improved tool to enable conversion of user-created on-screen topologies to an ILP formulation. The fourth and final part of this thesis is the detailed performance comparison of a selected set of Generic ILP and 0-1 SAT-based ILP solvers in solving the improved ILP formulations of the clustering problem generated using the tool. The results obtained indicate that from our selected set of solvers, generic ILP solvers are able to handle relatively large scale MANET topologies, while 0-1 SAT-based ILP solvers are the fastest, for small scale networks. For small scale networks the proposed ILP formulations, such as the Star-Ring base model, together with the high performance solvers would be suitable for use in real-world environments. However for large scale networks, as the time to cluster the network grows exponentially, the solvers will be unable to cluster the network in accordance with the demands of a real-world environment.College of EngineeringDepartment of Computer Science and EngineeringMaster of Science in Computer Engineering (MSCoE)Aloul, Fadi AhmedSagahyroon, Assim2012-02-15T09:51:14Z2012-02-15T09:51:14Z2012-01info:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/doctoralThesisapplication/pdf35.232-2012.04http://hdl.handle.net/11073/2763en_USoai:repository.aus.edu:11073/27632025-06-26T12:35:09Z |
| spellingShingle | MANET Cluster Optimization Using ILP/SAT Techniques Zahidi, Syed Zohaib Hussain Clustering ILP formulation Topology Ad hoc networks (Computer networks) Linear programming |
| status_str | publishedVersion |
| title | MANET Cluster Optimization Using ILP/SAT Techniques |
| title_full | MANET Cluster Optimization Using ILP/SAT Techniques |
| title_fullStr | MANET Cluster Optimization Using ILP/SAT Techniques |
| title_full_unstemmed | MANET Cluster Optimization Using ILP/SAT Techniques |
| title_short | MANET Cluster Optimization Using ILP/SAT Techniques |
| title_sort | MANET Cluster Optimization Using ILP/SAT Techniques |
| topic | Clustering ILP formulation Topology Ad hoc networks (Computer networks) Linear programming |
| url | http://hdl.handle.net/11073/2763 |