Topology control

Topology control is a technique used in distributed computing to alter the underlying network (modeled as a graph) to reduce the cost of distributed algorithms if run over the resulting graphs. It is a basic technique in distributed algorithms. For instance, a (minimum) spanning tree is used as a backbone to reduce the cost of broadcast from O(m) to O(n), where m and n are the number of edges and vertices in the graph, respectively.

The term "topology control" is used mostly by the wireless ad hoc and sensor networks research community. The main aim of topology control in this domain is to save energy, reduce interference between nodes and extend lifetime of the network. However, recently the term has also been gaining traction with regards to control of the network structure of electric power systems.

Topology construction and maintenance

Lately, topology control algorithms have been divided into two subproblems: topology construction, in charge of the initial reduction, and topology maintenance, in charge of the maintenance of the reduced topology so that characteristics like connectivity and coverage are preserved.

This is the first stage of a topology control protocol. Once the initial topology is deployed, specially when the location of the nodes is random, the administrator has no control over the design of the network; for example, some areas may be very dense, showing a high number of redundant nodes, which will increase the number of message collisions and will provide several copies of the same information from similarly located nodes. However, the administrator has control over some parameters of the network: transmission power of the nodes, state of the nodes (active or sleeping), role of the nodes (Clusterhead, gateway, regular), etc. By modifying these parameters, the topology of the network can change.

Upon the same time a topology is reduced and the network starts serving its purpose, the selected nodes start spending energy: Reduced topology starts losing its "optimality as soon as full network activity evolves. After some time being active, some nodes will start to run out of energy. Especially in wireless sensor networks with multihopping, intensive packet forwarding causes nodes that are closer to the sink to spend higher amounts of energy than nodes that are farther away. Topology control has to be executed periodically in order to preserve the desired properties such as connectivity, coverage, density.

Topology construction algorithms

There are many ways to perform topology construction:

  • Optimizing the node locations during the deployment phase
  • Change the transmission range of the nodes
  • Turn off nodes from the network
  • Create a communication backbone
  • Clustering
  • Adding new nodes to the network to preserve connectivity (Federated Wireless sensor networks)

Some examples of topology construction algorithms are:

Tx range-based

Hierarchical

Graphical examples

  • Full power network topology
    Full power network topology
  • Reduced network topology via Minimal Spanning Tree (Change in Tx Range)
    Reduced network topology via Minimal Spanning Tree (Change in Tx Range)
  • Reduced network topology via Connected Dominating Set (Select a subset of nodes that cover all the network and turn off non-selected nodes)
    Reduced network topology via Connected Dominating Set (Select a subset of nodes that cover all the network and turn off non-selected nodes)

Topology maintenance algorithms

In the same manner as topology construction, there are many ways to perform topology maintenance:

  • Global Vs. Local
  • Dynamic Vs. Static Vs. Hybrid
  • Triggered by time, energy, density, random, etc.


Some examples of topology maintenance algorithms are:

Global

  • DGTRec (Dynamic Global Topology Recreation):

Periodically, wake up all inactive nodes, reset the existing reduced topology in the network and apply a topology construction protocol.

  • SGTRot (Static Global Topology Rotation):

Initially, the topology construction protocol must create more than one reduced topology (hopefully as disjoint as possible). Then, periodically, wake up all inactive nodes, and change the current active reduced topology to the next, like in a Christmas tree.

  • HGTRotRec (Hybrid Global Topology Rotation and Recreation)

Work as the SGTRot, but when the current active reduced topology detects a certain level of disconnection, reset the reduced topology and invoke the topology construction protocol to recreate that particular reduced topology.

Local

  • DL-DSR (Dynamic Local DSR-based TM)

This protocol, based on the Dynamic Source Routing (DSR) routing algorithm, recreates the paths of disconnected nodes when a node fails.

In all of the above protocols can be found in.[10] In Atarraya,[11] two version of each of these protocols are implemented with different triggers: one by time, and the other one by energy. In addition, Atarraya allows the pairing of all the topology construction and topology maintenance protocols in order to test the optimal maintenance policy for a particular construction protocol; it is important to mention that many papers on topology construction have not performed any study on this regard.

Further reading

Many books and papers have been written in the topic:

  • Topology Control for Wireless Sensor Networks. ACM MobiCom 2003. [12]
  • Topology Control in Wireless Sensor Networks: with a companion simulation tool for teaching and research. Miguel Labrador and Pedro Wightman. Springer. 2009.[10]
  • Topology Control in Wireless Ad Hoc and Sensor Networks. Paolo Santi. Wiley. 2005.[13]
  • Protocols and Architectures for Wireless Sensor Networks. Holger Karl and Andreas Willig. Wiley-Interscience. 2007.[14]
  • Capacity-Optimized Topology Control for MANETs with Cooperative Communications. 2011.[15]
  • Robust Topology control for indoor wireless sensor networks. 2008 .

Simulation of topology control

There are many networking simulation tools, however there is one specifically designed for testing, design and teaching topology control algorithms: Atarraya.[11]

Atarraya is an event-driven simulator developed in Java that present a new framework for designing and testing topology control algorithms. It is an open source application, distributed under the GNU V.3 license. It was developed by Pedro Wightman, a Ph.D. candidate at University of South Florida, with the collaboration of Dr. Miguel Labrador. A paper with the detailed description of the simulator was presented in SIMUTools 2009. The paper can be found in this link.

References

  1. ^ [1], Local Minimal Spanning Tree
  2. ^ [2], Iterative Minimum Spanning Tree
  3. ^ [3][permanent dead link‍], KNEIGH
  4. ^ "Archived copy" (PDF). Archived from the original (PDF) on 2007-07-05. Retrieved 2009-04-30.{{cite web}}: CS1 maint: archived copy as title (link), XTC
  5. ^ [4], COMPOW , Hi
  6. ^ [5], A3: A topology construction protocol for WSN
  7. ^ [6], EECDS
  8. ^ [7], CDS-Rule K
  9. ^ [8], HEED
  10. ^ a b Topology Control by Labrador and Wightman, Topology Control in Wireless Sensor Networks
  11. ^ a b [9], Atarraya, a simulator for topology control in wireless sensor networks
  12. ^ J. Pan, Y. Hou, L. Cai, Y. Shi, and X. Shen, Topology control for wireless sensor networks, Proc. ACM Int'l Conf. on Mobile Comp. and Netw. (MobiCom'03), pp. 286--299, San Diego, California, USA, Sept. 14--19, 2003.
  13. ^ Topology Control by Santi, Topology Control in Wireless Ad Hoc and Sensor Networks
  14. ^ Protocols and Architectures for Wireless Sensor Networks by Holger Karl and Andreas Willig, Protocols and Architectures for Wireless Sensor Networks
  15. ^ Q. Guan, F.R. Yu, S. Jiang, and V.C.M. Leung, “Capacity-Optimized Topology Control for MANETs with Cooperative Communications,” IEEE Trans. Wireless Comm., vol. 10, no. 7, pp. 2162-2170, July 2011.

Read other articles:

Heliocopris japetus

Heliocopris japetus Klasifikasi ilmiah Kerajaan: Animalia Filum: Arthropoda Kelas: Insecta Ordo: Coleoptera Famili: Scarabaeidae Genus: Heliocopris Spesies: Heliocopris japetus Heliocopris japetus adalah spesies kumbang yang berasal dari genus Heliocopris dan famili Scarabaeidae. Kumbang ini juga merupakan bagian dari ordo Coleoptera, kelas Insecta, filum Arthropoda, dan kingdom Animalia. Kumbang ini memiliki antena yang terdiri dari plat yang disebut lamela. Referensi Bisby F.A., Roskov Y.R...

 

 

Jollof rice

Rice dish from West Africa Jollof riceJollof rice with stew and garnishAlternative namesBenachin, riz au gras, ceebu jën, zaamèTypeRice dishCourseMain courseRegion or stateWest Africa[1][2]Serving temperatureHotMain ingredientsRice, tomatoes and tomato paste, onions, chili peppers, cooking oilIngredients generally usedHerbs, spices, aromaticsVariationsVarious meat and seafood versions  Media: Jollof rice Jollof (/dʒəˈlɒf/), or jollof rice, is a rice dish fr...

 

 

Asosiasi Sepak Bola Korea

Asosiasi Sepak Bola KoreaAFCDidirikan19 September 1933; 90 tahun lalu (19 September 1933)Kantor pusatJongno, SeoulBergabung dengan FIFA21 May 1948; 75 tahun lalu (21 May 1948)Bergabung dengan AFC21 May 1954; 69 tahun lalu (21 May 1954)Bergabung dengan EAFF28 May 2002; 21 tahun lalu (28 May 2002)PresidenChung Mong-gyuWakil ketua7 pejabatWebsitekfa.or.kr Asosiasi Sepak Bola KoreaHangul대한축구협회 Hanja大韓蹴球協會 Alih AksaraDaehan Chukgu HyeophoeMcCune–Reisch...

イスラームにおける結婚

イスラームにおける結婚（イスラームにおけるけっこん）とは、二者の間で行われる法的な契約である。新郎新婦は自身の自由な意思で結婚に同意する。口頭または紙面での規則に従った拘束的な契約は、イスラームの結婚で不可欠だと考えられており、新郎と新婦の権利と責任の概要を示している[1]。イスラームにおける離婚は様々な形をとることができ、個�...

 

 

St Michael South Elmham

Human settlement in EnglandSt Michael South ElmhamSt Michael's churchSt Michael South ElmhamLocation within SuffolkArea2.4 km2 (0.93 sq mi) [1]Population60 (2005 est.)[2]• Density25/km2 (65/sq mi)OS grid referenceTM340840DistrictEast SuffolkShire countySuffolkRegionEastCountryEnglandSovereign stateUnited KingdomPost townBungayPostcode districtNR35Dialling code01986UK ParliamentWaveney List of places UK En...

 

 

T-Online

German news portalYou can help expand this article with text translated from the corresponding article in German. Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Consider adding a topic to this template: there are al...

Несторианство

ХристианствоБиблия Ветхий Завет Новый Завет Евангелие Десять заповедей Нагорная проповедь Апокрифы Бог, Троица Бог Отец Иисус Христос Святой Дух История христианства Апостолы Хронология христианства Раннее христианство Гностическое христианство Вселенские соборы Н...

 

 

Голубянки

Голубянки Самец голубянки икар Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ПервичноротыеБез ранга:ЛиняющиеБез ранга:PanarthropodaТип:ЧленистоногиеПодтип:ТрахейнодышащиеНадкласс:ШестиногиеКласс...

 

 

美国众议院

此條目需要补充更多来源。 (2021年7月4日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：美国众议院 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。 美國眾議院 United States House of Representatives第118届美国国会众议院徽章 众议院旗...

Athenais (daughter of Herodes Atticus)

Roman noblewoman (143-161) Statue, believed to be of Athenais, from the Nymphaeum of Herodes Atticus at Olympia, dating from between 149 and 153 AD, Olympia Archaeological Museum, Greece. Marcia Annia Claudia Alcia Athenais Gavidia Latiaria,[1] (Greek: Μαρκία Κλαυδία Άλκία Άθηναΐς Γαβιδία Λατιαρία) otherwise most commonly known as Athenais (Greek: Αθηναΐς)[2] (143-161[1]) was a Roman noblewoman of Greek Athenian and Italia...

 

 

Fußball-Club Gelsenkirchen-Schalke 04

F.C.G. Schalke 04Calcio Die Knappen (i Minatori), Die Königsblauen (i Blu reali) Segni distintiviUniformi di gara Casa Trasferta Terza divisa Colori sociali Blu reale, bianco InnoBlau und weiss wie lieb ich Dich e Königsblauer S04 Dati societariCittàGelsenkirchen Nazione Germania ConfederazioneUEFA Federazione DFB Campionato2. Bundesliga Fondazione1904 Presidente Axel Hefer Allenatore Karel Geraerts StadioVeltins-Arena(61 482 posti) Sito webwww.schalke04.de Palmarès Titoli di Ge...

 

 

1831 in Russia

Years in Russia: 1828 1829 1830 1831 1832 1833 1834 Centuries: 18th century · 19th century · 20th century Decades: 1800s 1810s 1820s 1830s 1840s 1850s 1860s Years: 1828 1829 1830 1831 1832 1833 1834 Sergei Bibikov by Pimen Orlov Events from the year 1831 in Russia. Incumbents Monarch – Nicholas I Events This section needs expansion. You can help by adding to it. (October ...

2010 Toulouse Olympique season

Rugby league team season 2010 Toulouse Olympique seasonChallenge CupRound 4, knocked out by St. HelensTeam informationChairmanCarlos ZalduendoCoachGilles DumasCaptainÉric AnselmeStadiumStade des MinimesAvg. attendance1,905 (Average Home attendance as of 18 April 2010) ← 2009 2011 → 2010 is the second year of participation to the Championship for the TO. The team loses few players with Damien Couturier, Matthieu Almarcha, Jean-Christophe Borlin and Olivier Pramil leaving. On th...

 

 

川村幼稚園

川村幼稚園 国公私立の別 私立学校設置者 学校法人川村学園設立年月日 1952年創立者 川村文子共学・別学 男女共学所在地 〒171-0031 東京都豊島区目白2丁目20番24号外部リンク [1]プロジェクト:学校/幼稚園テンプレートテンプレートを表示 川村幼稚園（かわむらようちえん）は、東京都豊島区目白2丁目に所在する私立共学幼稚園。大半の女子園児は川村小学校へ進学する�...

 

 

Audit

Independent examination of an organization For other uses, see Audit (disambiguation). Auditing redirects here. For the Scientology practice, see Auditing (Scientology). Paper trail redirects here. For the T.I. album, see Paper Trail. Part of a series onAccounting Historical costConstant purchasing powerManagementTax Major typesAuditBudgetCostForensicFinancialFundGovernmentalManagementSocialTax Key conceptsAccounting periodAccrualConstant purchasing powerEconomic entityFair valueGoing concern...

Roscoe Lee Brown

Untuk the Tuskegee Airman, lihat Roscoe Brown. Roscoe Lee BrowneRoscoe Lee Browne (in 1979)Lahir(1922-05-02)2 Mei 1922[1]Woodbury, New Jersey, U.S.Meninggal11 April 2007(2007-04-11) (umur 84)Los Angeles, California, U.S.Sebab meninggalKanker perutAlmamaterUniversitas LincolnPekerjaanAktor, sutradara panggungTahun aktif1960–2007 Penghargaan(1986) Primetime Emmy Award for Outstanding Guest Actor in a Comedy Series (en) Penghargaan Emmy Roscoe Lee Browne (Mei 2, 1922[...

 

 

Paul Cézanne

Ne doit pas être confondu avec Langlois de Sézanne. Pour les articles ayant des titres homophones, voir Sézanne et Sézane. Paul CézannePhotographie de Paul Cezanne, en 1899Naissance 19 janvier 1839Aix-en-ProvenceDécès 22 octobre 1906 (à 67 ans)Aix-en-ProvenceSépulture Cimetière Saint-Pierre d'Aix-en-ProvenceNationalité FrançaiseActivité PeintreFormation Académie de Charles SuisseMaître Joseph Gilbert, Antoine Guillemet, Camille PissarroÉlève Émile Bernard, Maurice Deni...

 

 

Yugo-Vostochnaya (Moscow Metro)

Moscow Metro station Yugo-VostochnayaЮго-ВосточнаяMoscow Metro stationGeneral informationLocationVykhino-Zhulebino District, South-Eastern Administrative OkrugMoscowRussiaCoordinates55°42′18″N 37°49′05″E / 55.705000°N 37.818055°E / 55.705000; 37.818055Owned byMoskovsky MetropolitenLine(s) Nekrasovskaya linePlatforms2 side platformsConstructionStructure typeThree-span shallow-column station[1]Platform levels1ParkingNoHistoryOpened27 ...

Composition of the Torah

Part of a series on theBible Canons and books Tanakh Torah Nevi'im Ketuvim Old Testament (OT) New Testament (NT) Deuterocanon Antilegomena Chapters and verses Apocrypha Jewish OT NT Authorship and development Authorship Dating Hebrew canon Old Testament canon New Testament canon Composition of the Torah Mosaic authorship Pauline epistles Petrine epistles Johannine works Translations and manuscripts Dead Sea scrolls Masoretic Text Samaritan Pentateuch Targumim Septuagint Peshitta Vetus Latina...

 

 

Diegetic music

Music in a drama that is part of the fictional setting Source music redirects here. For the South Korean entertainment company, see Source Music. Andrew Lloyd Webber's Phantom of the Opera uses the in-universe setting of an opera house to mix diegetic and non-diegetic sources of music and singing. Inside Broadway, 2018. Diegetic music, also called source music, is music that is part of the fictional world portrayed in a piece of narrative media (such as a film, show, play, or video game) and ...