Autoconfiguración de redes ad hoc basadas en confianza.

Abstract

[ES] En la presente tesis se aborda el problema del descubrimiento de vecinos en redes estáticas inalámbricas ad hoc, redes sin infraestructura. En estas redes los nodos deben descubrir los vecinos como un primer paso tras el despliegue. Además se aborda el problema de creación de redes espontáneas basadas en la confianza, y el de selección de vecinos. Se han presentado distintos algoritmos que solucionan el problema siguiendo unas premisas que se irán relajando a lo largo de la tesis. Se han implementado esos algoritmos en Castalia 3.2 para su validación y comparación con otros protocolos de referencia. Los protocolos determinísticos presentan mejores resultados de simulación, aunque requieren que sigan una planificación en la transmisión. En cuanto al protocolo aleatorio CDPRR (Collision Detection Probabilistic Round Robin) no sigue una planificación pero requiere el conocimiento del número de nodos de la red. El protocolo CDH (Collision Detection Hello) permite el desconocimiento del número de nodos. Ambos logran el descubrimiento de los vecinos con probabilidad 1 mediante la detección de colisiones. Ambas propuestas obtienen mejores prestaciones que los protocolos usados como referencia. Tanto para CDH como para CDPRR se ha realizado un modelo analítico de determinadas métricas. Se ha propuesto un protocolo aleatorio basado en líder que permite obtener buenas prestaciones y se puede usar de forma asíncrona aunque solo permite su uso en entornos one-hop. Finalmente, se presenta un protocolo aleatorio consciente de la energía que permite buenos resultados para altos duty cycles y redes compuestas de pocos nodos. En cuanto a la creación de redes espontáneas basadas en la confianza, se ha propuesto un modelo que usa el protocolo CDPRR como base. Este protocolo de creación de redes espontáneas basadas en la confianza permite premisas más realistas y mejora un protocolo determinístico de referencia. Finalmente, se propone un protocolo que combina el descubrimiento y la selección de vecinos con el objetivo de proporcionar nodos favoritos. Estos nodos permiten el envío de información al exterior de la red o en futuras operaciones como el encaminamiento.

[CA] En la present tesi s'aborda el problema del descobriment de veïns en xarxes estàtiques sense fil ad hoc, xarxes sense infraestructura. En estes xarxes els nodes han de descobrir els veïns com un primer pas després del desplegament. A més s'aborda el problema de creació de xarxes espontànies basades en la confiança, i el de selecció de veïns. S'han presentat distints algoritmes que solucionen el problema seguint unes premisses que se n'aniran relaxant al llarg de la tesi. S'han implementat eixos algoritmes en Castalia 3.2 per a la seua validació i comparació amb altres protocols de referència. Els protocols determinístics presenten millors resultats de simulació, encara que requerixen que seguisquen una planificació en la transmissió. Quant al protocol aleatori CDPRR (Collision Detection Probabilistic Round Robin) no seguix una planificació però requerix el coneixement del nombre de nodes de la xarxa. El protocol CDH (Collision Detection Hello) permet el desconeixement del nombre de nodes. Ambdós aconseguixen el descobriment dels veïns amb probabilitat 1 per mitjà de la detecció de col·lisions. Ambdós propostes obtenen millors prestacions que els protocols usats com a referència. Tant per a CDH com per a CDPRR s'ha realitzat un model analític de determinades mètriques. S'ha proposat un protocol aleatori basat en líder que permet obtindre bones prestacions i es pot usar de forma asíncrona encara que només permet el seu ús en entorns onehop. Finalment, es presenta un protocol aleatori conscient de l'energia que permet bons resultats per a alts duty cycles i xarxes compostes de pocs nodes. Quant a la creació de xarxes espontànies basades en la confiança, s'ha proposat un model que usa el protocol CDPRR com a base. Este protocol de creació de xarxes espontànies basades en la confiança permet premisses més realistes i millora un protocol determinístic de referència. Finalment, es proposa un protocol que combina el descobriment i la selecció de veïns amb l'objectiu de proporcionar nodes favorits. Estos nodes permeten l'enviament d'informació a l'exterior de la xarxa o en futures operacions com l'encaminament.

[EN] This thesis addresses the neighbor discovery problem in static wireless ad hoc networks, infrastructure-less networks. In these networks the nodes must discover the neighbors as a first step after the deployment. Furthermore, the thesis addresses the problem of creation of spontaneous networks based on trust, and the neighbor selection. Several algorithms have been presented that solve the problem following some assumptions that will be relaxed throughout the thesis. Those algorithms have been implemented in Castalia 3.2 for validation and comparison with other reference protocolos. The deterministic protocols provide better simulation results, although they require a transmission schedule. As for the randomized protocol CDPRR (Collision Detection Probabilistic Round Robin), it does not follow a schedule but it requires the knowledge of the number of nodes in the network. The CDH (Collision Detection Hello) protocol allows the ignorance of the number of nodes. They both achieve the discovery of the neighbors with probability 1 by detecting collisions. Both proposals achieve better performance than the protocols used as reference. For CDH and CDPRR an analytical model has been carried out regarding several metrics. A randomized protocol based on leader has been proposed that achieves a good performance and it can be used in an asynchronous way although it can only be used in one-hop environments. Finally, an energy-aware randomized protocol is proposed, which achieves good results for high duty cycles and networks composed of a small number of nodes. As for the creation of spontaneous networks based on trust, a model has been proposed which is based on the CDPRR protocol. This protocol for the creation of spontaneous networks based on trust allows more realistic assumptions and outperforms a determinsitic protocol used as reference. Finally, a protocol is proposed which combines the discovery and selection of neighbors aiming at providing favourite nodes. These nodes allow sending information towards outside the network or in future operations such as routing.