dc.contributor |
Universitat Politècnica de Catalunya. Departament d'Enginyeria Telemàtica |
dc.contributor |
Ozón Górriz, Francisco Javier |
dc.contributor.author |
Lema Rosas, María Ángel |
dc.date |
2008-07-23 |
dc.identifier.uri |
http://hdl.handle.net/2099.1/5198 |
dc.language.iso |
spa |
dc.publisher |
Universitat Politècnica de Catalunya |
dc.rights |
Attribution-NonCommercial-ShareAlike 2.5 Spain |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.rights |
http://creativecommons.org/licenses/by-nc-sa/2.5/es/ |
dc.subject |
Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Telemàtica i xarxes d'ordinadors |
dc.subject |
Computer networks |
dc.subject |
Redes ad-hoc |
dc.subject |
Teoría de grafos |
dc.subject |
Topología de red |
dc.subject |
Árbol generador mínimo |
dc.subject |
Algoritmo de Kruskal |
dc.subject |
Optimitzación combinatoria |
dc.subject |
Algoritmos heurísticos |
dc.subject |
Algoritmo hormigas |
dc.subject |
Xarxes d'ordinadors |
dc.title |
Diseño de la topología de una red ad-hoc |
dc.type |
info:eu-repo/semantics/bachelorThesis |
dc.description.abstract |
Las redes ad-hoc de comunicación están formadas por diferentes dispositivos,
normalmente inalámbricos, que pueden situarse en cualquier punto del espacio. Para
poder comunicarse se han de definir enlaces entre los diferentes nodos de manera
que exista conectividad entre todos los nodos de la red.
Este proyecto, continuación de trabajos anteriores, tiene como objetivo el diseño de la
topología de una red ad-hoc con un doble requerimiento. Por un lado, se ha de
garantizar conectividad entre todos los nodos de la red (y ello bajo la posibilidad de
utilizar cualquier dispositivo como nodo intermedio de conmutación). Por otro lado, se
ha de conseguir que el consumo total de las baterías de los dispositivos sea mínimo.
El problema presentado por los anteriores proyectos, conocido como subgrafo de
difusión de energía mínima (MECBS), fue resuelto mediante la utilización de
algoritmos probabilistas –simulated annealing y hormigas– y un algoritmo determinista
basado en la obtención de árboles generadores mínimos mediante Kruskal. En ese
caso, un único nodo raíz debe mandar información al resto de la red. El presente
proyecto trata de añadir pequeñas variaciones a los algoritmos de simulated
annealing y hormigas para mejorar sus resultados y generaliza el problema para el
caso en que todos los nodos deban enviar información al resto de nodos (problema
que hemos denominado subgrafo de gossiping de energía mínima, MECGS), lo que
ha de dar como resultado –en comparación con el caso en que sólo un nodo manda
información al resto de la red– topologías ligeramente distintas y de mayor densidad
de enlaces. |