Généralement, les problèmes de conception de réseaux consistent à sélectionner les arcs et les sommets d’un graphe G de sorte que la fonction coût est optimisée et l’ensemble de contraintes impliquant les liens et les sommets dans G sont respectées. Une modification dans le critère d’optimisation et/ou dans l’ensemble de contraintes mène à une nouvelle représentation d’un problème différent. Dans cette thèse, nous nous intéressons au problème de conception d’infrastructure de réseaux maillés sans fil (WMN- Wireless Mesh Network en Anglais) où nous montrons que la conception de tels réseaux se transforme d’un problème d’optimisation standard (la fonction coût est optimisée) à un problème d’optimisation à plusieurs objectifs, pour tenir en compte de nombreux aspects, souvent contradictoires, mais néanmoins incontournables dans la réalité. Cette thèse, composée de trois volets, propose de nouveaux modèles et algorithmes pour la conception de WMNs où rien n’est connu à l’ avance. Le premiervolet est consacré à l’optimisation simultanée de deux objectifs équitablement importants : le coût et la performance du réseau en termes de débit. Trois modèles bi-objectifs qui se différent principalement par l’approche utilisée pour maximiser la performance du réseau sont proposés, résolus et comparés. Le deuxième volet traite le problème de placement de passerelles vu son impact sur la performance et l’extensibilité du réseau. La notion de contraintes de sauts (hop constraints) est introduite dans la conception du réseau pour limiter le délai de transmission. Un nouvel algorithme basé sur une approche de groupage est proposé afin de trouver les positions stratégiques des passerelles qui favorisent l’extensibilité du réseau et augmentent sa performance sans augmenter considérablement le coût total de son installation. Le dernier volet adresse le problème de fiabilité du réseau dans la présence de pannes simples. Prévoir l’installation des composants redondants lors de la phase de conception peut garantir des communications fiables, mais au détriment du coût et de la performance du réseau. Un nouvel algorithme, basé sur l’approche théorique de décomposition en oreilles afin d’installer le minimum nombre de routeurs additionnels pour tolérer les pannes simples, est développé. Afin de résoudre les modèles proposés pour des réseaux de taille réelle, un algorithme évolutionnaire (méta-heuristique), inspiré de la nature, est développé. Finalement, les méthodes et modèles proposés on été évalués par des simulations empiriques et d’événements discrets. / Generally, network design problems consist of selecting links and vertices of a graph G so that a cost function is optimized and all constraints involving links and the vertices in G are met. A change in the criterion of optimization and/or the set of constraints leads to a new representation of a different problem. In this thesis, we consider the problem of designing infrastructure Wireless Mesh Networks (WMNs) where we show that the design of such networks becomes an optimization problem with multiple objectives instead of a standard optimization problem (a cost function is optimized) to take into account many aspects, often contradictory, but nevertheless essential in the reality. This thesis, composed of three parts, introduces new models and algorithms for designing WMNs from scratch. The first part is devoted to the simultaneous optimization of two equally important objectives: cost and network performance in terms of throughput. Three bi-objective models which differ mainly by the approach used to maximize network performance are proposed, solved and compared. The second part deals with the problem of gateways placement, given its impact on network performance and scalability. The concept of hop constraints is introduced into the network design to reduce the transmission delay. A novel algorithm based on a clustering approach is also proposed to find the strategic positions of gateways that support network scalability and increase its performance without significantly increasing the cost of installation. The final section addresses the problem of reliability in the presence of single failures. Allowing the installation of redundant components in the design phase can ensure reliable communications, but at the expense of cost and network performance. A new algorithm is developed based on the theoretical approach of "ear decomposition" to install the minimum number of additional routers to tolerate single failures. In order to solve the proposed models for real-size networks, an evolutionary algorithm (meta-heuristics), inspired from nature, is developed. Finally, the proposed models and methods have been evaluated through empirical and discrete events based simulations.

Généralement, les problèmes de conception de réseaux consistent à sélectionner les arcs et les sommets d’un graphe G de sorte que la fonction coût est optimisée et l’ensemble de contraintes impliquant les liens et les sommets dans G sont respectées. Une modification dans le critère d’optimisation et/ou dans l’ensemble de contraintes mène à une nouvelle représentation d’un problème différent. Dans cette thèse, nous nous intéressons au problème de conception d’infrastructure de réseaux maillés sans fil (WMN- Wireless Mesh Network en Anglais) où nous montrons que la conception de tels réseaux se transforme d’un problème d’optimisation standard (la fonction coût est optimisée) à un problème d’optimisation à plusieurs objectifs, pour tenir en compte de nombreux aspects, souvent contradictoires, mais néanmoins incontournables dans la réalité. Cette thèse, composée de trois volets, propose de nouveaux modèles et algorithmes pour la conception de WMNs où rien n’est connu à l’ avance. Le premiervolet est consacré à l’optimisation simultanée de deux objectifs équitablement importants : le coût et la performance du réseau en termes de débit. Trois modèles bi-objectifs qui se différent principalement par l’approche utilisée pour maximiser la performance du réseau sont proposés, résolus et comparés. Le deuxième volet traite le problème de placement de passerelles vu son impact sur la performance et l’extensibilité du réseau. La notion de contraintes de sauts (hop constraints) est introduite dans la conception du réseau pour limiter le délai de transmission. Un nouvel algorithme basé sur une approche de groupage est proposé afin de trouver les positions stratégiques des passerelles qui favorisent l’extensibilité du réseau et augmentent sa performance sans augmenter considérablement le coût total de son installation. Le dernier volet adresse le problème de fiabilité du réseau dans la présence de pannes simples. Prévoir l’installation des composants redondants lors de la phase de conception peut garantir des communications fiables, mais au détriment du coût et de la performance du réseau. Un nouvel algorithme, basé sur l’approche théorique de décomposition en oreilles afin d’installer le minimum nombre de routeurs additionnels pour tolérer les pannes simples, est développé. Afin de résoudre les modèles proposés pour des réseaux de taille réelle, un algorithme évolutionnaire (méta-heuristique), inspiré de la nature, est développé. Finalement, les méthodes et modèles proposés on été évalués par des simulations empiriques et d’événements discrets. / Generally, network design problems consist of selecting links and vertices of a graph G so that a cost function is optimized and all constraints involving links and the vertices in G are met. A change in the criterion of optimization and/or the set of constraints leads to a new representation of a different problem. In this thesis, we consider the problem of designing infrastructure Wireless Mesh Networks (WMNs) where we show that the design of such networks becomes an optimization problem with multiple objectives instead of a standard optimization problem (a cost function is optimized) to take into account many aspects, often contradictory, but nevertheless essential in the reality. This thesis, composed of three parts, introduces new models and algorithms for designing WMNs from scratch. The first part is devoted to the simultaneous optimization of two equally important objectives: cost and network performance in terms of throughput. Three bi-objective models which differ mainly by the approach used to maximize network performance are proposed, solved and compared. The second part deals with the problem of gateways placement, given its impact on network performance and scalability. The concept of hop constraints is introduced into the network design to reduce the transmission delay. A novel algorithm based on a clustering approach is also proposed to find the strategic positions of gateways that support network scalability and increase its performance without significantly increasing the cost of installation. The final section addresses the problem of reliability in the presence of single failures. Allowing the installation of redundant components in the design phase can ensure reliable communications, but at the expense of cost and network performance. A new algorithm is developed based on the theoretical approach of "ear decomposition" to install the minimum number of additional routers to tolerate single failures. In order to solve the proposed models for real-size networks, an evolutionary algorithm (meta-heuristics), inspired from nature, is developed. Finally, the proposed models and methods have been evaluated through empirical and discrete events based simulations.

Surveillance wireless sensor networks (WSNs) are highly vulnerable to the failure of the base station (BS) because attackers can easily render the network useless for relatively long periods of time by only destroying the BS. The time and effort needed to destroy the BS is much less than that needed to destroy the numerous sensing nodes. Previous works have tackled BS failure by deploying a mobile BS or by using multiple BSs, which requires extra cost. Moreover, despite using the best electronic countermeasures, intrusion tolerance systems and anti-traffic analysis strategies to protect the BSs, an adversary can still destroy them. The new BS cannot trust the deployed sensor nodes. Also, previous works lack both the procedures to ensure network reliability and security during BS failure such as storing then sending reports concerning security threats against nodes to the new BS and the procedures to verify the trustworthiness of the deployed sensing nodes. Otherwise, a new WSN must be re-deployed which involves a high cost and requires time for the deployment and setup of the new WSN. In this thesis, we address the problem of reliable recovery from a BS failure by proposing a new security architecture called Surveillance Security (SurvSec). SurvSec continuously monitors the network for security threats and stores data related to node security, detects and authenticates the new BS, and recovers the stored data at the new BS. SurvSec includes encryption for security-related information using an efficient dynamic secret sharing algorithm, where previous work has high computations for dynamic secret sharing. SurvSec includes compromised nodes detection protocol against collaborative work of attackers working at the same time where previous works have been inefficient against collaborative work of attackers working at the same time. SurvSec includes a key management scheme for homogenous WSN, where previous works assume heterogeneous WSN using High-end Sensor Nodes (HSN) which are the best target for the attackers. SurvSec includes efficient encryption architecture against quantum computers with a low time delay for encryption and decryption, where previous works have had high time delay to encrypt and decrypt large data size, where AES-256 has 14 rounds and high delay. SurvSec consists of five components, which are: 1. A Hierarchical Data Storage and Data Recovery System. 2. Security for the Stored Data using a new dynamic secret sharing algorithm. 3. A Compromised-Nodes Detection Algorithm at the first stage. 4. A Hybrid and Dynamic Key Management scheme for homogenous network. 5. Powerful Encryption Architecture for post-quantum computers with low time delay. In this thesis, we introduce six new contributions which are the followings: 1. The development of the new security architecture called Surveillance Security (SurvSec) based on distributed Security Managers (SMs) to enable distributed network security and distributed secure storage. 2. The design of a new dynamic secret sharing algorithm to secure the stored data by using distributed users tables. 3. A new algorithm to detect compromised nodes at the first stage, when a group of attackers capture many legitimate nodes after the base station destruction. This algorithm is designed to be resistant against a group of attackers working at the same time to compromise many legitimate nodes during the base station failure. 4. A hybrid and dynamic key management scheme for homogenous network which is called certificates shared verification key management. 5. A new encryption architecture which is called the spread spectrum encryption architecture SSEA to resist quantum-computers attacks. 6. Hardware implementation of reliable network recovery from BS failure. The description of the new security architecture SurvSec components is done followed by a simulation and analytical study of the proposed solutions to show its performance.

Surveillance wireless sensor networks (WSNs) are highly vulnerable to the failure of the base station (BS) because attackers can easily render the network useless for relatively long periods of time by only destroying the BS. The time and effort needed to destroy the BS is much less than that needed to destroy the numerous sensing nodes. Previous works have tackled BS failure by deploying a mobile BS or by using multiple BSs, which requires extra cost. Moreover, despite using the best electronic countermeasures, intrusion tolerance systems and anti-traffic analysis strategies to protect the BSs, an adversary can still destroy them. The new BS cannot trust the deployed sensor nodes. Also, previous works lack both the procedures to ensure network reliability and security during BS failure such as storing then sending reports concerning security threats against nodes to the new BS and the procedures to verify the trustworthiness of the deployed sensing nodes. Otherwise, a new WSN must be re-deployed which involves a high cost and requires time for the deployment and setup of the new WSN. In this thesis, we address the problem of reliable recovery from a BS failure by proposing a new security architecture called Surveillance Security (SurvSec). SurvSec continuously monitors the network for security threats and stores data related to node security, detects and authenticates the new BS, and recovers the stored data at the new BS. SurvSec includes encryption for security-related information using an efficient dynamic secret sharing algorithm, where previous work has high computations for dynamic secret sharing. SurvSec includes compromised nodes detection protocol against collaborative work of attackers working at the same time where previous works have been inefficient against collaborative work of attackers working at the same time. SurvSec includes a key management scheme for homogenous WSN, where previous works assume heterogeneous WSN using High-end Sensor Nodes (HSN) which are the best target for the attackers. SurvSec includes efficient encryption architecture against quantum computers with a low time delay for encryption and decryption, where previous works have had high time delay to encrypt and decrypt large data size, where AES-256 has 14 rounds and high delay. SurvSec consists of five components, which are: 1. A Hierarchical Data Storage and Data Recovery System. 2. Security for the Stored Data using a new dynamic secret sharing algorithm. 3. A Compromised-Nodes Detection Algorithm at the first stage. 4. A Hybrid and Dynamic Key Management scheme for homogenous network. 5. Powerful Encryption Architecture for post-quantum computers with low time delay. In this thesis, we introduce six new contributions which are the followings: 1. The development of the new security architecture called Surveillance Security (SurvSec) based on distributed Security Managers (SMs) to enable distributed network security and distributed secure storage. 2. The design of a new dynamic secret sharing algorithm to secure the stored data by using distributed users tables. 3. A new algorithm to detect compromised nodes at the first stage, when a group of attackers capture many legitimate nodes after the base station destruction. This algorithm is designed to be resistant against a group of attackers working at the same time to compromise many legitimate nodes during the base station failure. 4. A hybrid and dynamic key management scheme for homogenous network which is called certificates shared verification key management. 5. A new encryption architecture which is called the spread spectrum encryption architecture SSEA to resist quantum-computers attacks. 6. Hardware implementation of reliable network recovery from BS failure. The description of the new security architecture SurvSec components is done followed by a simulation and analytical study of the proposed solutions to show its performance.