Subgrafs d'energia mínima en xarxes ad-hoc
Tutor / Supervisor
Student
Rodríguez Viaplana, Albert
Aymamí Gili, Eva
Document type
Master thesis (pre-Bologna period)
Date
2008
rights
Open Access
Publisher
Universitat Politècnica de Catalunya
UPCommons
Abstract
En una xarxa de comunicacions ad-hoc els diferents nodes són normalment
dispositius sense fils que poden situar-se sobre qualsevol punt de l'espai. En
aquest tipus de xarxes s'ha de definir els enllaços entre els diferents
dispositius sobre la marxa, de manera que existeixi una connectivitat entre tots
els nodes que conformen la xarxa.
El present projecte té com a objectiu el disseny de la topologia d'una xarxa adhoc
amb un doble requeriment. D'una banda, s'ha d'aconseguir connectivitat
completa, és a dir, s'ha de garantir que un node pugui enviar informació a tota
la resta de nodes de la xarxa encara que aquesta operació es faci a través de
nodes intermedis i, en segon lloc, s'ha d'aconseguir que el consum total
d'energia de la xarxa sigui mínim.
Per a resoldre aquest problema, anomenat subgraf de difusió d'energia
mínima (MECBS), es presenten dos algoritmes probabilistes –simulated
annealing i formigues– a més d'un algoritme determinista basat en l'obtenció
d'arbres generadors mínims mitjançant Kruskal. Tots tres algoritmes són
analitzats i comparats detalladament per tal d'extreure les conclusions que
proporcionin una millor solució al problema del MECBS.
