@unpublished{upm23518,
          author = {Danping He},
            year = {2014},
          school = {Industriales},
           title = {A novel methodology for planning reliable wireless sensor networks},
             url = {https://oa.upm.es/23518/},
        abstract = {Wireless sensor networks (WSNs) have shown their potentials in various applications, which bring a lot of benefits to users from both research and industrial areas. For many setups, it is envisioned thatWSNs will consist of tens to hundreds of nodes that operate on small batteries. However due to the diversity of the deployed environments and resource constraints on radio communication, sensing ability and energy supply, it is a very challenging issue to plan optimized WSN topology and predict its performance before real deployment. During the network planning phase, the connectivity, coverage, cost, network longevity and service quality should all be considered. Therefore it requires designers coping with comprehensive and interdisciplinary knowledge, including networking, radio engineering, embedded system and so on, in order to efficiently construct a reliable WSN for any specific types of environment. Nowadays there is still a lack of the analysis and experiences to guide WSN designers to efficiently construct WSN topology successfully without many trials. Therefore, simulation is a feasible approach to the quantitative analysis of the performance of wireless sensor networks. However the existing planning algorithms and tools, to some extent, have serious limitations to practically design reliable WSN topology:  Only a few of them tackle the 3D deployment issue, and an overwhelming number of works are proposed to place devices in 2D scheme. Without considering the full dimension, the impacts of environment to the performance of WSN are not completely studied, thus the values of evaluated metrics such as connectivity and sensing coverage are not sufficiently accurate to make proper decision.  Even fewer planning methods model the sensing coverage and radio propagation by considering the realistic scenario where obstacles exist. Radio signals propagate with multi-path phenomenon in the real world, in which direct paths, reflected paths and diffracted paths contribute to the received signal strength. Besides, obstacles between the path of sensor and objects might block the sensing signals, thus create coverage hole in the application.  None of the existing planning algorithms model the network longevity and packet delivery capability properly and practically. They often employ unilateral and unrealistic formulations.  The optimization targets are often one-sided in the current works. Without comprehensive evaluation on the important metrics, the performance of planned WSNs can not be reliable and entirely optimized. Modeling of environment is usually time consuming and the cost is very high, while none of the current works figure out any method to model the 3D deployment environment efficiently and accurately. Therefore many researchers are trapped by this issue, and their algorithms can only be evaluated in the same scenario, without the possibility to test the robustness and feasibility for implementations in different environments. In this thesis, we propose a novel planning methodology and an intelligent WSN planning tool to assist WSN designers efficiently planning reliable WSNs. First of all, a new method is proposed to efficiently and automatically model the 3D indoor and outdoor environments. To the best of our knowledge, this is the first time that the advantages of image understanding algorithm are applied to automatically reconstruct 3D outdoor and indoor scenarios for signal propagation and network planning purpose. The experimental results indicate that the proposed methodology is able to accurately recognize different objects from the satellite images of the outdoor target regions and from the scanned floor plan of indoor area. Its mechanism offers users a flexibility to reconstruct different types of environment without any human interaction. Thereby it significantly reduces human efforts, cost and time spent on reconstructing a 3D geographic database and allows WSN designers concentrating on the planning issues. Secondly, an efficient ray-tracing engine is developed to accurately and practically model the radio propagation and sensing signal on the constructed 3D map. The engine contributes on efficiency and accuracy to the estimated results. By using image processing concepts, including the kd-tree space division algorithm and modified polar sweep algorithm, the rays are traced efficiently without detecting all the primitives in the scene. The radio propagation model iv is proposed, which emphasizes not only the materials of obstacles but also their locations along the signal path. The sensing signal of sensor nodes, which is sensitive to the obstacles, is benefit from the ray-tracing algorithm via obstacle detection. The performance of this modelling method is robust and accurate compared with conventional methods, and experimental results imply that this methodology is suitable for both outdoor urban scenes and indoor environments. Moreover, it can be applied to either GSM communication or ZigBee protocol by varying frequency parameter of the radio propagation model. Thirdly, WSN planning method is proposed to tackle the above mentioned challenges and efficiently deploy reliable WSNs. More metrics (connectivity, coverage, cost, lifetime, packet latency and packet drop rate) are modeled more practically compared with other works. Especially 3D ray tracing method is used to model the radio link and sensing signal which are sensitive to the obstruction of obstacles; network routing is constructed by using AODV protocol; the network longevity, packet delay and packet drop rate are obtained via simulating practical events in WSNet simulator, which to the best of our knowledge, is the first time that network simulator is involved in a planning algorithm. Moreover, a multi-objective optimization algorithm is developed to cater for the characteristics of WSNs. The capability of providing multiple optimized solutions simultaneously allows users making their own decisions accordingly, and the results are more comprehensively optimized compared with other state-of-the-art algorithms. iMOST is developed by integrating the introduced algorithms, to assist WSN designers efficiently planning reliable WSNs for different configurations. The abbreviated name iMOST stands for an Intelligent Multi-objective Optimization Sensor network planning Tool. iMOST contributes on: (1) Convenient operation with a user-friendly vision system; (2) Efficient and automatic 3D database reconstruction and fast 3D objects design for both indoor and outdoor environments; (3) It provides multiple multi-objective optimized 3D deployment solutions and allows users to configure the network properties, hence it can adapt to various WSN applications; (4) Deployment solutions in the 3D space and the corresponding evaluated performance are visually presented to users; and (5) The Node Placement Module of iMOST is available online as well as the source code of the other two rebuilt heuristics. Therefore WSN designers will be benefit from v this tool on efficiently constructing environment database, practically and efficiently planning reliable WSNs for both outdoor and indoor applications. With the open source codes, they are also able to compare their developed algorithms with ours to contribute to this academic field. Finally, solid real results are obtained for both indoor and outdoor WSN planning. Deployments have been realized for both indoor and outdoor environments based on the provided planning solutions. The measured results coincide well with the estimated results. The proposed planning algorithm is adaptable according to the WSN designer?s desirability and configuration, and it offers flexibility to plan small and large scale, indoor and outdoor 3D deployments. The thesis is organized in 7 chapters. In Chapter 1, WSN applications and motivations of this work are introduced, the state-of-the-art planning algorithms and tools are reviewed, challenges are stated out and the proposed methodology is briefly introduced. In Chapter 2, the proposed 3D environment reconstruction methodology is introduced and its performance is evaluated for both outdoor and indoor environment. The developed ray-tracing engine and proposed radio propagation modelling method are described in details in Chapter 3, their performances are evaluated in terms of computation efficiency and accuracy. Chapter 4 presents the modelling of important metrics of WSNs and the proposed multi-objective optimization planning algorithm, the performance is compared with the other state-of-the-art planning algorithms. The intelligent WSN planning tool iMOST is described in Chapter 5. RealWSN deployments are prosecuted based on the planned solutions for both indoor and outdoor scenarios, important data are measured and results are analysed in Chapter 6. Chapter 7 concludes the thesis and discusses about future works. vi Resumen en Castellano Las redes de sensores inal{\'a}mbricas (en ingl{\'e}s Wireless Sensor Networks, WSNs) han demostrado su potencial en diversas aplicaciones que aportan una gran cantidad de beneficios para el campo de la investigaci{\'o}n y de la industria. Para muchas configuraciones se prev{\'e} que las WSNs consistir{\'a}n en decenas o cientos de nodos que funcionar{\'a}n con bater{\'i}as peque{\~n}as. Sin embargo, debido a la diversidad de los ambientes para desplegar las redes y a las limitaciones de recursos en materia de comunicaci{\'o}n de radio, capacidad de detecci{\'o}n y suministro de energ{\'i}a, la planificaci{\'o}n de la topolog{\'i}a de la red y la predicci{\'o}n de su rendimiento es un tema muy dif{\'i}cil de tratar antes de la implementaci{\'o}n real. Durante la fase de planificaci{\'o}n del despliegue de la red se deben considerar aspectos como la conectividad, la cobertura, el coste, la longevidad de la red y la calidad del servicio. Por lo tanto, requiere de dise{\~n}adores con un amplio e interdisciplinario nivel de conocimiento que incluye la creaci{\'o}n de redes, la ingenier{\'i}a de radio y los sistemas embebidos entre otros, con el fin de construir de manera eficiente una WSN confiable para cualquier tipo de entorno. Hoy en d{\'i}a todav{\'i}a hay una falta de an{\'a}lisis y experiencias que orienten a los dise{\~n}adores de WSN para construir las topolog{\'i}as WSN de manera eficiente sin realizar muchas pruebas. Por lo tanto, la simulaci{\'o}n es un enfoque viable para el an{\'a}lisis cuantitativo del rendimiento de las redes de sensores inal{\'a}mbricos. Sin embargo, los algoritmos y herramientas de planificaci{\'o}n existentes tienen, en cierta medida, serias limitaciones para dise{\~n}ar en la pr{\'a}ctica una topolog{\'i}a fiable de WSN:  S{\'o}lo unos pocos abordan la cuesti{\'o}n del despliegue 3D mientras que existe una gran cantidad de trabajos que colocan los dispositivos en 2D. Si no se analiza la dimensi{\'o}n completa (3D), los efectos del entorno en el desempe{\~n}o de WSN no se estudian por completo, por lo que los valores de los par{\'a}metros evaluados, como la conectividad y la cobertura de detecci{\'o}n, no son lo suficientemente precisos para tomar la decisi{\'o}n correcta.  A{\'u}n en menor medida los m{\'e}todos de planificaci{\'o}n modelan la cobertura de los sensores y la propagaci{\'o}n de la se{\~n}al de radio teniendo en cuenta un escenario realista donde existan obst{\'a}culos. Las se{\~n}ales de radio en el mundo real siguen una propagaci{\'o}n multicamino, en la que los caminos directos, los caminos reflejados y los caminos difractados contribuyen a la intensidad de la se{\~n}al recibida. Adem{\'a}s, los obst{\'a}culos entre el recorrido del sensor y los objetos pueden bloquear las se{\~n}ales de detecci{\'o}n y por lo tanto crear {\'a}reas sin cobertura en la aplicaci{\'o}n.  Ninguno de los algoritmos de planificaci{\'o}n existentes modelan el tiempo de vida de la red y la capacidad de entrega de paquetes correctamente y pr{\'a}cticamente. A menudo se emplean formulaciones unilaterales y poco realistas.  Los objetivos de optimizaci{\'o}n son a menudo tratados unilateralmente en los trabajos actuales. Sin una evaluaci{\'o}n exhaustiva de los par{\'a}metros importantes, el rendimiento previsto de las redes inal{\'a}mbricas de sensores no puede ser fiable y totalmente optimizado. Por lo general, el modelado del entorno conlleva mucho tiempo y tiene un coste muy alto, pero ninguno de los trabajos actuales propone alg{\'u}n m{\'e}todo para modelar el entorno de despliegue 3D con eficiencia y precisi{\'o}n. Por lo tanto, muchos investigadores est{\'a}n limitados por este problema y sus algoritmos s{\'o}lo se pueden evaluar en el mismo escenario, sin la posibilidad de probar la solidez y viabilidad para las implementaciones en diferentes entornos. En esta tesis, se propone una nueva metodolog{\'i}a de planificaci{\'o}n as{\'i} como una herramienta inteligente de planificaci{\'o}n de redes de sensores inal{\'a}mbricas para ayudar a los dise{\~n}adores a planificar WSNs fiables de una manera eficiente. En primer lugar, se propone un nuevo m{\'e}todo para modelar demanera eficiente y autom{\'a}tica los ambientes interiores y exteriores en 3D. Seg{\'u}n nuestros conocimientos hasta la fecha, esta es la primera vez que las ventajas del algoritmo de \_image understanding\_se aplican para reconstruir autom{\'a}ticamente los escenarios exteriores e interiores en 3D para analizar la propagaci{\'o}n de la se{\~n}al y viii la planificaci{\'o}n de la red. Los resultados experimentales indican que la metodolog{\'i}a propuesta es capaz de reconocer con precisi{\'o}n los diferentes objetos presentes en las im{\'a}genes satelitales de las regiones objetivo en el exterior y de la planta escaneada en el interior. Su mecanismo ofrece a los usuarios la flexibilidad para reconstruir los diferentes tipos de entornos sin ninguna interacci{\'o}n humana. De este modo se reduce considerablemente el esfuerzo humano, el coste y el tiempo invertido en la reconstrucci{\'o}n de una base de datos geogr{\'a}fica con informaci{\'o}n 3D, permitiendo as{\'i} que los dise{\~n}adores se concentren en los temas de planificaci{\'o}n. En segundo lugar, se ha desarrollado un motor de trazado de rayos (en ingl{\'e}s ray tracing) eficiente para modelar con precisi{\'o}n la propagaci{\'o}n de la se{\~n}al de radio y la se{\~n}al de los sensores en el mapa 3D construido. El motor contribuye a la eficiencia y la precisi{\'o}n de los resultados estimados. Mediante el uso de los conceptos de procesamiento de im{\'a}genes, incluyendo el algoritmo del {\'a}rbol kd para la divisi{\'o}n del espacio y el algoritmo \_polar sweep\_modificado, los rayos se trazan de manera eficiente sin la detecci{\'o}n de todas las primitivas en la escena. El modelo de propagaci{\'o}n de radio que se propone no s{\'o}lo considera los materiales de los obst{\'a}culos, sino tambi{\'e}n su ubicaci{\'o}n a lo largo de la ruta de se{\~n}al. La se{\~n}al de los sensores de los nodos, que es sensible a los obst{\'a}culos, se ve beneficiada por la detecci{\'o}n de objetos llevada a cabo por el algoritmo de trazado de rayos. El rendimiento de este m{\'e}todo de modelado es robusto y preciso en comparaci{\'o}n con los m{\'e}todos convencionales, y los resultados experimentales indican que esta metodolog{\'i}a es adecuada tanto para escenas urbanas al aire libre como para ambientes interiores. Por otra parte, se puede aplicar a cualquier comunicaci{\'o}n GSM o protocolo ZigBee mediante la variaci{\'o}n de la frecuencia del modelo de propagaci{\'o}n de radio. En tercer lugar, se propone un m{\'e}todo de planificaci{\'o}n de WSNs para hacer frente a los desaf{\'i}os mencionados anteriormente y desplegar redes de sensores fiables de manera eficiente. Se modelan m{\'a}s par{\'a}metros (conectividad, cobertura, coste, tiempo de vida, la latencia de paquetes y tasa de ca{\'i}da de paquetes) en comparaci{\'o}n con otros trabajos. Especialmente el m{\'e}todo de trazado de rayos 3D se utiliza para modelar el enlace de radio y se{\~n}al de los sensores que son sensibles a la obstrucci{\'o}n de obst{\'a}culos; el enrutamiento de la red se construye utilizando el protocolo AODV; la longevidad de la red, retardo de paquetes ix y tasa de abandono de paquetes se obtienen a trav{\'e}s de la simulaci{\'o}n de eventos pr{\'a}cticos en el simulador WSNet, y seg{\'u}n nuestros conocimientos hasta la fecha, es la primera vez que simulador de red est{\'a} implicado en un algoritmo de planificaci{\'o}n. Por otra parte, se ha desarrollado un algoritmo de optimizaci{\'o}n multi-objetivo para satisfacer las caracter{\'i}sticas de las redes inal{\'a}mbricas de sensores. La capacidad de proporcionar m{\'u}ltiples soluciones optimizadas de forma simult{\'a}nea permite a los usuarios tomar sus propias decisiones en consecuencia, obteniendo mejores resultados en comparaci{\'o}n con otros algoritmos del estado del arte. iMOST se desarrolla mediante la integraci{\'o}n de los algoritmos presentados, para ayudar de forma eficiente a los dise{\~n}adores en la planificaci{\'o}n de WSNs fiables para diferentes configuraciones. El nombre abreviado iMOST (Intelligent Multi-objective Optimization Sensor network planning Tool) representa una herramienta inteligente de planificaci{\'o}n de redes de sensores con optimizaci{\'o}n multi-objetivo. iMOST contribuye en: (1) Operaci{\'o}n conveniente con una interfaz de f{\'a}cil uso, (2) Reconstrucci{\'o}n eficiente y autom{\'a}tica de una base de datos con informaci{\'o}n 3D y dise{\~n}o r{\'a}pido de objetos 3D para ambientes interiores y exteriores, (3) Proporciona varias soluciones de despliegue optimizadas para los multi-objetivo en 3D y permite a los usuarios configurar las propiedades de red, por lo que puede adaptarse a diversas aplicaciones de WSN, (4) las soluciones de implementaci{\'o}n en el espacio 3D y el correspondiente rendimiento evaluado se presentan visualmente a los usuarios, y (5) El \_Node Placement Module\_de iMOST est{\'a} disponible en l{\'i}nea, as{\'i} como el c{\'o}digo fuente de las otras dos heur{\'i}sticas de planificaci{\'o}n. Por lo tanto los dise{\~n}adores WSN se beneficiar{\'a}n de esta herramienta para la construcci{\'o}n eficiente de la base de datos con informaci{\'o}n del entorno, la planificaci{\'o}n pr{\'a}ctica y eficiente de WSNs fiables tanto para aplicaciones interiores y exteriores. Con los c{\'o}digos fuente abiertos, son capaces de comparar sus algoritmos desarrollados con los nuestros para contribuir a este campo acad{\'e}mico. Por {\'u}ltimo, se obtienen resultados reales s{\'o}lidos tanto para la planificaci{\'o}n de WSN en interiores y exteriores. Los despliegues se han realizado tanto para ambientes de interior y como para ambientes de exterior utilizando las soluciones de planificaci{\'o}n propuestas. Los resultados medidos coinciden en gran medida con los resultados estimados. El algoritmo de planificaci{\'o}n x propuesto se adapta convenientemente al deise{\~n}o de redes de sensores inal{\'a}mbricas, y ofrece flexibilidad para planificar los despliegues 3D a peque{\~n}a y gran escala tanto en interiores como en exteriores. La tesis se estructura en 7 cap{\'i}tulos. En el Cap{\'i}tulo 1, se presentan las aplicaciones de WSN y motivaciones de este trabajo, se revisan los algoritmos y herramientas de planificaci{\'o}n del estado del arte, se presentan los retos y se describe brevemente la metodolog{\'i}a propuesta. En el Cap{\'i}tulo 2, se presenta la metodolog{\'i}a de reconstrucci{\'o}n de entornos 3D propuesta y su rendimiento es evaluado tanto para espacios exteriores como para espacios interiores. El motor de trazado de rayos desarrollado y el m{\'e}todo de modelado de propagaci{\'o}n de radio propuesto se describen en detalle en el Cap{\'i}tulo 3, evalu{\'a}ndose en t{\'e}rminos de eficiencia computacional y precisi{\'o}n. En el Cap{\'i}tulo 4 se presenta el modelado de los par{\'a}metros importantes de las WSNs y el algoritmo de planificaci{\'o}n de optimizaci{\'o}n multi-objetivo propuesto, el rendimiento se compara con los otros algoritmos de planificaci{\'o}n descritos en el estado del arte. La herramienta inteligente de planificaci{\'o}n de redes de sensores inal{\'a}mbricas, iMOST, se describe en el Cap{\'i}tulo 5. En el Cap{\'i}tulo 6 se llevan a cabo despliegues reales de acuerdo a las soluciones previstas para los escenarios interiores y exteriores, se miden los datos importantes y se analizan los resultados. En el Cap{\'i}tulo 7 se concluye la tesis y se discute acerca de los trabajos futuros.}
}