Brief announcement: Minimum spanning trees and cone-based topology control
Consider a setting where nodes can vary their transmission power thereby changing the network topology, the goal of topology control is to reduce the transmission power while ensuring the communication graph remains connected. Wattenhofer et al. [6] introduced the distributed cone-based topology con...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2010
|
| Online Access: | http://hdl.handle.net/1721.1/51001 https://orcid.org/0000-0003-3045-265X |
| _version_ | 1826209399173021696 |
|---|---|
| author | Cornejo Collado, Alex Lynch, Nancy Ann |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Cornejo Collado, Alex Lynch, Nancy Ann |
| author_sort | Cornejo Collado, Alex |
| collection | MIT |
| description | Consider a setting where nodes can vary their transmission power thereby changing the network topology, the goal of topology control is to reduce the transmission power while ensuring the communication graph remains connected. Wattenhofer et al. [6] introduced the distributed cone-based topology control algorithm with parameter α (CBTC(α)) and proved it correct if α ≤ 2π/3. Li et al. [4] proposed performing asymmetric edge removal or increasing α to 5π/6, and proved that when applied separately these minimizations preserve connectivity. Bahramgiri et al. [1] proved that when α ≤ 2π/3 it was possible to extend the algorithm to work in three dimensions and described a variation to preserve k-connectivity.
We give a short self-contained proof that when α ≤ 2π/3 the minimum spanning tree is contained in the graph produced by CBTC(α). Its interesting to note that by comparison, other popular topology control algorithms are variations of the Gabriel Graph [5], the Relative Neighbor Graph [2] or the Delaunay Triangulation [3]; all of which are structures known to contain the minimum spanning tree. The proof is essentially an application of a lemma proved by Yao [7]. As a consequence of this proof we get as corollaries new short proofs of some of the main results of Wattenhofer et al. [6], Li et al. [4] and Bahramgiri et al. [1]. (1) When α ≤ 2π/3 the algorithm CBTC(α) preserves connectivity [6]. (2) The asymmetric edge removal operation preserves connectivity [4]. (3) The algorithm can be extended to three dimensions [1], and generally to n-dimensional space. |
| first_indexed | 2024-09-23T14:21:54Z |
| format | Article |
| id | mit-1721.1/51001 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:21:54Z |
| publishDate | 2010 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/510012022-09-29T08:59:41Z Brief announcement: Minimum spanning trees and cone-based topology control Cornejo Collado, Alex Lynch, Nancy Ann Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Lynch, Nancy Ann Cornejo Collado, Alex Lynch, Nancy Ann Consider a setting where nodes can vary their transmission power thereby changing the network topology, the goal of topology control is to reduce the transmission power while ensuring the communication graph remains connected. Wattenhofer et al. [6] introduced the distributed cone-based topology control algorithm with parameter α (CBTC(α)) and proved it correct if α ≤ 2π/3. Li et al. [4] proposed performing asymmetric edge removal or increasing α to 5π/6, and proved that when applied separately these minimizations preserve connectivity. Bahramgiri et al. [1] proved that when α ≤ 2π/3 it was possible to extend the algorithm to work in three dimensions and described a variation to preserve k-connectivity. We give a short self-contained proof that when α ≤ 2π/3 the minimum spanning tree is contained in the graph produced by CBTC(α). Its interesting to note that by comparison, other popular topology control algorithms are variations of the Gabriel Graph [5], the Relative Neighbor Graph [2] or the Delaunay Triangulation [3]; all of which are structures known to contain the minimum spanning tree. The proof is essentially an application of a lemma proved by Yao [7]. As a consequence of this proof we get as corollaries new short proofs of some of the main results of Wattenhofer et al. [6], Li et al. [4] and Bahramgiri et al. [1]. (1) When α ≤ 2π/3 the algorithm CBTC(α) preserves connectivity [6]. (2) The asymmetric edge removal operation preserves connectivity [4]. (3) The algorithm can be extended to three dimensions [1], and generally to n-dimensional space. 2010-01-28T15:19:55Z 2010-01-28T15:19:55Z 2009 Article http://purl.org/eprint/type/SubmittedJournalArticle 978-1-60558-396-9 http://hdl.handle.net/1721.1/51001 Cornejo, Alejandro, and Nancy Lynch. “Brief announcement: minimum spanning trees and cone-based topology control.” Proceedings of the 28th ACM symposium on Principles of distributed computing. Calgary, AB, Canada: ACM, 2009. 296-297. https://orcid.org/0000-0003-3045-265X en_US http://dx.doi.org/10.1145/1582716.1582774 Proceedings of the 28th ACM Symposium on Principles of Distributed Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery Joanne Hanley |
| spellingShingle | Cornejo Collado, Alex Lynch, Nancy Ann Brief announcement: Minimum spanning trees and cone-based topology control |
| title | Brief announcement: Minimum spanning trees and cone-based topology control |
| title_full | Brief announcement: Minimum spanning trees and cone-based topology control |
| title_fullStr | Brief announcement: Minimum spanning trees and cone-based topology control |
| title_full_unstemmed | Brief announcement: Minimum spanning trees and cone-based topology control |
| title_short | Brief announcement: Minimum spanning trees and cone-based topology control |
| title_sort | brief announcement minimum spanning trees and cone based topology control |
| url | http://hdl.handle.net/1721.1/51001 https://orcid.org/0000-0003-3045-265X |
| work_keys_str_mv | AT cornejocolladoalex briefannouncementminimumspanningtreesandconebasedtopologycontrol AT lynchnancyann briefannouncementminimumspanningtreesandconebasedtopologycontrol |