Search

International audience; Linear Wireless Sensor Networks (LWSN) are a sub-case of Wireless Sensor Networks where nodes are roughly located through multiple lines. They can be used to monitor many real-life infrastructure e.g. roads, pipelines or natural entities such as rivers. Classical network solutions are mostly inefficient on LWSN because these topologies a tree with very long branches are often a worst-case scenario of many protocols. Therefore few specific protocols have been designed for LWSN. But most of them require manual configuration of the nodes and are static. Real-life conditions require the network to adapt to changing situations addition of new nodes or sets of nodes, node destruction or to solve problems of data congestion. We propose a new network protocol called Dynamic Disco-Proto covering the setting up of the logical topology, address distribution without spoilage, dynamic addition of nodes or branches, and even dynamic addition of new data sinks. All these operations happen without human interaction or knowledge of the topology. Our proposition keeps the benefits of a mainly hierarchical routing without paying the price of address spoilage which can be the aftermath of mainly linear topologies. We evaluate our Dynamic DiscoProto protocol for LWSN using Castalia simulator and demonstrate that it resolves the problem of orphan nodes during network setup and also has good performance for dynamic and large LWSN. Eventually, simulation results demonstrate that our proposition adapts to multi-Sink deployment and improves data packet delivery ratio and data packet latency. more...

The widespread use of wireless devices such as smartphones and connected objects leads to an increasing emergence of infrastructure-less networks relying on device-to-device communication: ad hoc networks. Applications of this type of network vary widely from military operations to emergency situations. Scalability is a key property for some use cases involving a large number of devices, also called nodes. We mean by scalability, the ability of the network to increase in size without drastic loss of performance and with a cost-effective network maintenance. In this thesis, we focus on the scalability from a routing perspective. Routing handles the delivery of data packets from a source to a destination across the network. This is achieved by the exchange of information between nodes. The corresponding traffic may represent a break for scalability in presence of numerous nodes. In this work, we propose an aggregation of routing information. First, we partition the deployment area into smaller hierachical regions based on geographical coordinates. Nodes are assigned hierachical address depending on the regions they are located in. Then, we propose a mixed topological and geographical-based routing protocol. A node maintains precise routing information to other nodes in close proximity and geographically aggregate information for nodes at greater distances. Regions are the units of nodes aggregation. The further the nodes are, the larger the regions referring to them are. The results show that our proposition outperforms regular ad hoc routing in terms of scalability and addresses more efficiently geographical routing-related issues compared to classical geographical routing., La multiplication de l'usage des équipements connectables à un réseau sans fil tels que les smartphones ou les objets connectés peut être mise à profit pour construire des réseaux reposant sur des communications de proximité : les appareils communiquent directement entre eux, sans le support d'une infrastructure centrale. On parle de réseau ad hoc. Ce type de réseau sans infrastructure est exploité dans de nombreux domaines comme le militaire ou la gestion de catastrophes naturelles. Pour certains cas d'utilisation, le passage à l'échelle, c'est-à-dire la capacité à fonctionner avec la croissance de la taille du réseau, est une propriété indispensable. Dans cette thèse, nous nous intéressons à la problématique du routage sous l'aspect du passage à l'échelle. Le routage est la fonction responsable de l'acheminement des données au sein du réseau. Pour cela, des informations de contrôle sont échangées entre les nœuds du réseau. Mais le trafic associé à ces échanges peut être un frein pour passer à l'échelle. Afin de le réduire, nous proposons d'agréger les informations concernant des nœuds géographiquement proches. Dans un premier temps, nous mettons en place une structuration de la zone de déploiement du réseau en régions hiérarchiques. Ces régions servent d'agrégateur de nœuds à travers un adressage de ces derniers selon les régions auxquelles ils appartiennent. Par la suite, nous proposons un protocole de routage combinant les approches topologique et géographique. Il s'agit, pour un nœud donné, de maintenir des routes menant, d’une part, vers d'autres nœuds dans un voisinage proche et, d'autre part, vers des zones géographiques de plus en plus étendues au fur et à mesure de l'éloignement. Cette dernière propriété est obtenue en profitant de la structuration hiérarchique précédente des zones d'agrégation. Les résultats montrent la faculté de notre proposition à monter à grande échelle par rapport aux protocoles de routage ad hoc classique et aussi sa capacité à adresser les problèmes propres aux protocoles de routage purement géographique. more...

The widespread use of wireless devices such as smartphones and connected objects leads to an increasing emergence of infrastructure-less networks relying on device-to-device communication: ad hoc networks. Applications of this type of network vary widely from military operations to emergency situations. Scalability is a key property for some use cases involving a large number of devices, also called nodes. We mean by scalability, the ability of the network to increase in size without drastic loss of performance and with a cost-effective network maintenance. In this thesis, we focus on the scalability from a routing perspective. Routing handles the delivery of data packets from a source to a destination across the network. This is achieved by the exchange of information between nodes. The corresponding traffic may represent a break for scalability in presence of numerous nodes. In this work, we propose an aggregation of routing information. First, we partition the deployment area into smaller hierachical regions based on geographical coordinates. Nodes are assigned hierachical address depending on the regions they are located in. Then, we propose a mixed topological and geographical-based routing protocol. A node maintains precise routing information to other nodes in close proximity and geographically aggregate information for nodes at greater distances. Regions are the units of nodes aggregation. The further the nodes are, the larger the regions referring to them are. The results show that our proposition outperforms regular ad hoc routing in terms of scalability and addresses more efficiently geographical routing-related issues compared to classical geographical routing.; La multiplication de l'usage des équipements connectables à un réseau sans fil tels que les smartphones ou les objets connectés peut être mise à profit pour construire des réseaux reposant sur des communications de proximité : les appareils communiquent directement entre eux, sans le support d'une infrastructure centrale. On parle de réseau ad hoc. Ce type de réseau sans infrastructure est exploité dans de nombreux domaines comme le militaire ou la gestion de catastrophes naturelles. Pour certains cas d'utilisation, le passage à l'échelle, c'est-à-dire la capacité à fonctionner avec la croissance de la taille du réseau, est une propriété indispensable. Dans cette thèse, nous nous intéressons à la problématique du routage sous l'aspect du passage à l'échelle. Le routage est la fonction responsable de l'acheminement des données au sein du réseau. Pour cela, des informations de contrôle sont échangées entre les nœuds du réseau. Mais le trafic associé à ces échanges peut être un frein pour passer à l'échelle. Afin de le réduire, nous proposons d'agréger les informations concernant des nœuds géographiquement proches. Dans un premier temps, nous mettons en place une structuration de la zone de déploiement du réseau en régions hiérarchiques. Ces régions servent d'agrégateur de nœuds à travers un adressage de ces derniers selon les régions auxquelles ils appartiennent. Par la suite, nous proposons un protocole de routage combinant les approches topologique et géographique. Il s'agit, pour un nœud donné, de maintenir des routes menant, d’une part, vers d'autres nœuds dans un voisinage proche et, d'autre part, vers des zones géographiques de plus en plus étendues au fur et à mesure de l'éloignement. Cette dernière propriété est obtenue en profitant de la structuration hiérarchique précédente des zones d'agrégation. Les résultats montrent la faculté de notre proposition à monter à grande échelle par rapport aux protocoles de routage ad hoc classique et aussi sa capacité à adresser les problèmes propres aux protocoles de routage purement géographique. more...

International audience; In recent years, there have been significant efforts to standardize a routing protocol for Low-power and Lossy Networks (LLNs). This effort has culminated in standard IPv6 routing protocol for LLNs (RPL). The main interest of RPL is to improve routing in a LLN minimizing the usage of network resources. For this, RPL build acyclic graphs and applies an Objective Function (OF) which is responsible of choosing the preferred parent and the best links during the construction of the Destination Oriented Directed Acyclic Graph (DODAG). This paper introduces a new OF, based on a Non-Linear Length (NL-OF) which takes into account any number of metrics and constraints for QoS routing. NL-OF ensures that each path in the DODGA respects the input constraints. The NL-OF can be used to meet the requirements of sensible applications, such as real-time applications. A significant part of this work aims at studying the theoretical of the NL-OF. Finally, using Cooja simulator, we evaluate the performance of NL-OF. We show that our new Objective Function gives a good result and outperforms the three existing OFs when considering three QoS parameters which are End-to-End Delay, Packet Loss and Jitter. more...

International audience; Developing highly efficient routing protocols for Vehicular Ad hoc Networks (VANETs) is a challenging task mainly due to the special characters of such networks: large-scale sizes, frequent link disconnections and rapid topology changes. In this paper, we propose an adaptive quality of service (QoS) based routing for VANETs called AQRV. This new routing protocol is to adaptively choose the intersections through which data packets pass to reach the destination, and the selected route should satisfy with the QoS constraints and fulfill the best QoS in terms of three metrics, namely connectivity probability, packet delivery ratio and delay. To achieve the above objectives, we mathematically formulate the routing selection issue as a constrained optimization problem, and propose an Ant Colony Optimization (ACO) based algorithm to solve this problem. In addition, a terminal intersection concept is presented to decrease routing exploration time and alleviate network congestion. Moreover, in order to decrease network overhead, we propose Local QoS Models (LQM) to estimate real-time and complete QoS of urban road segments. Simulation results validate our derived LQM models and show the effectiveness of AQRV. more...

International audience; Mobile ad hoc networks (MANETs) are becoming an emerging technology that offer several advantages to users in terms of cost and ease of use. A MANET is a collection of mobile nodes connected by wireless links that form a temporary network topology that operates without a base station and centralized administration. Routing is a method through which information is forwarded from a transmitter to a specific recipient. Routing is a strategy that guarantees, at any time, the connection between any two nodes in a network. In this work, we propose a novel routing protocol inspired by the cuckoo search method. Our routing protocol is implemented using Network simulator 2. We chose Random WayPoint model as our mobility model. To validate our work, we opted for the comparison with the routing protocol ad hoc on-demand distance vector, destination sequence distance vector and the bio-inspired routing protocol AntHocNet in terms of the quality of service parameters: packet delivery ratio and end-to-end delay (E2ED). more...

International audience; In networks that operate during a long time, the routing protocol might have to be changed: this is the case when the network administrator plans a router change. Loop-free transition algorithms are used to ensure that there is no loop during the migration from the initial routing protocol to the final routing protocol. In this paper, we propose a distributed loop-free transition algorithm, called DLF (distributed loop-free heuristic). The algorithm is based on the fact that routing loops resulting from the removal of a node are localized, and can be detected efficiently. We show through simulations that DLF compares well with the existing centralized algorithms, and outperforms the existing distributed algorithm, in terms of migration duration. more...

International audience; Low-Power Lossy Networks (LLNs) are at the core of many Internet of Things solutions. Significant standardization effort has been put in creating a protocol stack suited for LLNs. Among these standards, IEEE802.15.4-2011 and RPL allow LLN devices to form a multi-hop mesh network. Today, RPL creates a routing topology without a priori knowledge about the topology created at the MAC layer. This negatively impacts the number of redundant paths, their quality, and the overall performance of the routing protocol. In this article, we highlight the need for an intermediate layer between MAC and network layers to solve these problems. We describe the protocols to be used in future Internet of Things, emphasize their weaknesses when deployed together, and provide areas of improvement. more...

International audience; A wide range of social, technological and communication systems can be described as complex networks. Scale-free networks are one of the well-known classes of complex networks in which nodes degree follow a power-law distribution. The design of scalable, adaptive and resilient routing schemes in such networks is very challenging. In this article we present an overview of required routing functionality, categorize the potential design dimensions of routing protocols among existing routing schemes and analyze experimental results and analytical studies performed so far to identify the main trends/trade-offs and draw main conclusions. Besides traditional schemes such as hierarchical/shortest-path path-vector routing, the article pays attention to advances in compact routing and geometric routing since they are known to significantly improve the scalability in terms of memory space. The identified trade-offs and the outcomes of this overview enable more careful conclusions regarding the (in-)suitability of different routing schemes to large-scale complex networks and provide a guideline for future routing research. more...

International audience; Over recent years, green communications have been proposed as an emerging strategy to reduce the Carbon footprint produced by the networking sector. It consists in using different software and hardware techniques allowing to minimize the energy consumption of network components. A significant amount of energy saving can be obtained by switching redundant or unused network components to inactive mode, referred to as sleep-scheduling. To achieve this, the routing algorithm should aggregate traffic flows over a subset of network routers and their links, allowing other components to be switched off. The objective of this paper is to present a holistic survey on existing sleep-scheduling based green routing protocols in wired networks. First, we propose a classification of main properties of sleep-scheduling based green routing protocols and use the proposed classification to categorize and describe the existing literature. Moreover, we provide a comprehensive comparison of existing green routing protocols and determine the main characteristics, assets and issues of each proposal. In addition, we identify and classify the main metrics for evaluating and comparing the efficiency of green routing protocols using sleep-scheduling. Finally, we identify the open issues and key guidelines towards an ideal green routing protocol for wired networks. more...

International audience; Data transportation and routing in Internet of Things (IoT) is a challenging issue where massive data collection and gathering are predictable. The Routing Protocol for Low- power and Lossy Networks (RPL) is one of the best candidates to ensure routing in 6LoWPAN networks. However, RPL is vulnerable to a number of attacks related to exchanged control messages. In this paper, we propose a new secure routing protocol based on RPL referred to as Secure-RPL (SRPL). The main aim of SRPL is to prevent misbehaving nodes from maliciously changing control message values such as the rank of a node that may disturb a network by creating a fake topology. We introduce the concept of rank threshold along with hash chain authentication technique to deal with internal attacks like sinkhole, black hole, selective forwarding attacks etc. Simulation results show that SRPL is robust and resistant to this kind of attacks based on malicious manipulation of RPL metrics. more...

International audience; Network lifetime is still the key issue when we deploy wireless sensor networks and IoT solutions in real-world applications. Current WSN research trends include duty-cycling at MAC layer and energy efficient routing at network layer, among others. In this study we propose an Optimal Probabilistic Energy-Aware Routing Protocol (OPEAR) for duty-cycled WSNs which aims at maximizing the network lifetime by keeping low energy consumption and balancing network traffic between nodes. Our experimental campaign reveals that our OPEAR protocol outperforms the popular Energy Aware Routing Protocol (EAR) from the literature, proving to be more effective in extending the network lifetime. more...

International audience; Quality of service (QoS) in wireless mesh networks is an active area of research, which is driven by the increasing demand for real-time and multimedia applications, such as Voice over IP and Video on Demand. In this paper, we propose a novel QoS based routing protocol for wireless mesh infrastructure, called Hybrid QoS Mesh Routing (HQMR). It is composed of two QoS based routing sub-protocols: a reactive multi-metric routing protocol for intra-infrastructure communications and a proactive multi-tree based routing protocol for communications with external networks. The proposed routing protocol enables forwarding real-time and streaming applications with QoS guarantee in a mesh wireless environment, by assigning a specific routing path for each defined service class. To this end, three different QoS service classes are defined, depending on the applications requirements. We analyze in this paper the simulation results of different scenarios conducted on the network simulator ns-3 to demonstrate the effectiveness of the HQMR protocol and to compare it to other routing protocols while forwarding real-time applications with QoS guarantee. more...

Software-Defined Networking (SDN) is a recent model of networking architecture which splits the network control from data forwarding functions. Most SDN solutions have in their scope the wired networks, but more recently, some attempts have been made to adapt SDN architecture for the context of wireless mesh networks (WMNs). In the present paper, we examine whether the use of the SDN paradigm in WMNs can help overcome certain limitations of the classic routing algorithms. To that end, we propose a new deployment architecture which exploits the main benefits of this paradigm: faster routing convergence and optimal path identification and takes advantage of multiple communication interfaces that most wireless devices already possess to split the signalling and data transfer. We then propose an hybrid management scheme applicable which mixes our SDN approach with a conventional distributed protocol (OLSR in our case). Through NS3 simulations, an improvement of 20% in both packet delivery ratio and lost packets was observed. Therefore, we can claim that the SDN controller can positively assist the distributed routing protocol operations. more...

International audience; Wireless Mesh Networks (WMNs) are ad-hoc networks where no infrastructure exists and where some of the participating nodes can also act as routers to forward traffic on behalf of others. WMNs have been proposed for various applications and can greatly vary in terms of size (from a handful of nodes to thousands) and complexity (static or mobile nodes, scarce or dense etc.). Efficient and robust IP routing is essential for these networks and its performance can greatly affect all other network performance metrics such as throughput, delay, packet delivery ratio etc. A lot of routing algorithms have been proposed ever since the advent of WMNs and research is still ongoing on the topic. All of the proposed solutions are based on the principle of distributed routing where routers exchange signalization messages in order to discover the network topology. In the present paper we propose a centralized routing based on the relatively recent paradigm of Software Defined Networking (SDN). We have used NS3 to simulate a dynamic mesh network where a subset of nodes are mobile and a source host generates traffic destined to a sink host. We evaluated four common network performance metrics namely packet delivery ratio, packet drop ratio due to route unavailability, average throughput and signalling overhead. By making appropriate assumptions, we compared our solution with three of the most widely used routing protocols for WMNs namely DSDV, AODV and OLSR. Our simulations demonstrate that, under certain conditions, our solution outperforms the aforementioned distributed routing algorithms and can improve network performance. more...

The design of low-power scalable wireless sensor networks remains a key challenge of the research. Clustering and routing have been widely studied for extending the lifetime of a network, which is a critical issue in sensor networks. Routing involves non-negligible operations, which considerably affect the network lifetime and the throughput. The clustering technique with data aggregation on cluster heads has an influence on the overall performance of the network since it is favoring a maximum network lifetime. This paper presents a novel cluster-based routing protocol called ABC-SD. The proposed protocol exploits the biologically inspired fast and efficient searching features of the Artificial Bee Colony metaheuristic to build low-power clusters. For the choice of cluster heads, a multi-objective fitness function is designed by using a Linear Programming formulation. The routing problem is addressed by a cost-based function that makes a trade-off between the energy efficiency and the number of hops of the path. The clustering process is achieved at the Base Station with a centralized control algorithm, which exploits energy levels and the neighborhood information of location-unaware sensors. As for the routing of gathered data, it is realized in a distributed manner. Furthermore, unlike the existing protocols in the literature, a realistic energy model is adopted in the considered network model. The proposed protocol is intensively experimented with a number of topologies in various network scenarios and the results are compared with the well-known cluster-based routing protocols that include the swarm intelligence based protocols. The obtained results demonstrate the effectiveness of the proposed protocol in terms of network lifetime, network coverage and the amount of packets delivered to the Base Station. HighlightsLP formulation of the clustering problem.Routing problem addressed by a CF.ABC-based clustering algorithm with a tradeoff between the energy consumption and the quality of the communication link.Pre-established routing mechanism in which routing paths are less costly in terms of power consumption.Integration of a realistic energy model and realistic network settings and simulation of the proposed protocol to demonstrate its performance compared to some existing protocols. more...

Competitive routing across peering links is a notable problem in Internet routing. A few years ago, a proposal to incrementally modify the Border Gateway Protocol (BGP) decision process was done, to improve routing coordination by leveraging on the existing multi-exit discriminator BGP attribute as signaling medium among peering Internet networks. It is called Peering Equilibrium Multipath (PEMP) routing: based on a non-cooperative potential game, it can improve routing stability and efficiency while respecting unilateral routing choice, by supporting strategic multipath forwarding decisions. The contribution of this paper is twofold. First, we specify how weighted load-balancing should be done in PEMP routing and examine the benefits against even load-balancing. Then we document an implementation of PEMP routing in the Quagga open source router, better specifying some aspects. We provide a performance evaluation of the implemented PEMP routing system, showing that the computing overhead is limited. more...

International audience; In networks that operate during a long time, the routing protocol might have to be changed (in order to apply a routing protocol update, or to take into account a change in the routing metrics). A loop-free transition algorithm has to be used in order to perform the transition to the new routing protocol without generating transient routing loops. In this paper, we propose a loop-free transition algorithm called ACH (avoiding cycles heuristic), which is able to perform the transition in a very small number of steps. Compared to other algorithms of the literature, ACH yields a number of steps which is independent of both the number of nodes and the number of destinations, and thus allows the transition to be performed in a small time. We show through simulations that ACH significantly outperforms other heuristics of the literature, due to its capability to deal with several destinations at once, and due to a priority-based procedure to avoid cycles. more...

International audience; Computer networks generally operate using a single routing protocol. However, there are situations where the routing protocol has to be changed (e.g., because an update of the routing protocol is available, or because an external event has triggered a traffic with different quality of service requirements). In this paper, we show that an uncontrolled change of the routing protocol might yield to transient routing loops (even if the involved routing protocols are loop-free). We show that it is possible to achieve a loop-free change for multiple destinations using a strongly connected component approach producing successive steps, where each step contains nodes that can change the routing protocol in parallel. Our aim is to reduce the number of steps in order to reduce the time required for the network to change from one routing protocol to another. Simulation results show that our strongly connected component approach greatly reduces the number of steps compared to the state of the art, and thus it greatly reduces the time for the change. more...

The need for energy-efficient routing and data gathering protocols in large-scale environments becomes very challenging. Hierarchical routing in WSNs is a very important topic. It has been widely investigated relative to energy efficiency based routing protocols. LEACH (Low Energy Adaptive Clustering Hierarchy algorithm) is the pioneering cluster routing protocol in WSNs. However, it is not suitable for large scale network and wireless channel conditions are ignored during packet forwarding. To address this issue, we proposed a novel multi-hop clustering cross layer protocol based on LEACH. It considers both the SNR of different links and the residual energy of sensor nodes. Simulation results in terms of the average energy consumption, the network lifetime and the Packet Delivery Ratio show clearly the outperformance of the proposed algorithm versus the conventional LEACH. more...

International audience; Minimizing the energy consumption and hence ex-tends the network lifetime is a key requirement when designing anefficient sensor network protocol. QoS-aware routing in WirelessSensor Network (WSN), aims to take into account other networksperformance aspects as minimizing end-to-end delay (as well asjitter), reducing packet loss rate while minimizing the energyconsumption of the network during data transmission. Theseobjectives are sometimes conflicting, and therefore tradeoffs mustbe made between energy conservation and QoS considerations.The general problem can be reformulated as a Multi-ConstrainedOptimal Path problem (MCOP), and is known as NP-complete.The latter raises a real challenge, as sensor nodes are verylimited in resources capabilities, we propose to use fuzzy inferencemechanism to seek a good tradeoff between all given metricsand constraints. This paper discusses the implementation ofcombining several routing metric, using fuzzy logic to design aRPL objective function, the routing standard for the Internet ofThings. The proposal is integrated on Contiki operating systemand his deployment were performed on a real world indoor WSN.Obtained results show improvements compared to the commonimplementation of the RPL protocol, and demonstrate relevanceof our contribution. more...

International audience; Node autoconfiguration is one of the main issues in self-organized networks. One class of approaches relies on hierarchical organization of nodes. This kind of structuration aims to deal with scalability issues, especially for wireless networks. But building and maintaining a hierarchy is generally expensive for these resource-limited networks. We propose a low-cost distributed, hierarchical, location-based address au-toconfiguration protocol. Each node infers its address from those of its one-hop neighbors and from its relative position to them. In this way we obtain a globally-consistent organization resulting from local interactions only. This reduces the latency and the overhead generated during address configuration. Moreover this scheme is the first step towards the design of a scalable routing protocol taking advantages of the proposed hierarchical addressing. more...

International audience; Graph coloring was exploited in wireless sensor networks to solve many optimization problems, mainly related to channel assignment. In this paper, we propose to use coloring to jointly manage channel access and routing to the sink. We introduce CHRA, a coloring based hierarchical routing approach. Coloring is exploited to avoid interferences and also to schedule nodes transmissions to the sink. We provide an analytical study assessing the performance of CHRA and present an investigation of various coloring heuristics to study their impact on CHRA performances on maintaining the network connectivity and coverage, while reducing the energy consumption. more...

International audience; Mesh Networks (WMNs) have been considered as a promising alternative to conventional wired networks, thanks to its flexibility and easy deployment. Thus, to ensure a satisfying level of QoS guarantees for real-time and streaming applications such as Voice over IP (VoIP) and Video on Demand (VoD), we propose a novel QoS based routing protocol for wireless mesh environments, called Hybrid QoS Mesh Routing (HQMR), jointly with a clustering algorithm to enhance scalability issues within the mesh infrastructure. HQMR is composed of two routing sub-protocols: a reactive routing sub-protocol for intra-infrastructure communications and a proactive QoS based multi-tree routing sub-protocol for communications with external networks. In this paper, we describe and analyze the simulation results of different scenarios conducted on the network simulator ns-3 to demonstrate the effectiveness of our clustering algorithm and of the Intra-Mesh Infrastructure Reactive Routing (IMRR) protocol in forwarding real-time applications with QoS guarantee while reducing network overhead. more...

Streamline energy consumption in Wireless Sensor Network (WSN) is and stills a topical problem in which several investigations have undertaken. The aim is to develop mechanisms such those based on routing protocols, for prolonging the network lifetime leading to improve its robustness and fluidity of transmissions, and then ensure an overall stable operation. In this paper, we present a robust and hybrid hierarchical multi-hop routing protocol wherein a dynamic clustering mechanism is implemented for optimal clusters construction. The approach combines successfully heterogonous information in terms of residual energy and signal strength of nodes and allows a multipath search by optimizing end-to-end delay and energy consumption. The effectiveness of the proposed approach is illustrated in simulations. For this purpose, a comparative study with LEACH protocol has been carried out for several networks with different densities. more...

In Wireless Sensor Networks, low latency, energy efficiency, and coverage problems are considered as three key issues in designing routing protocols. In this paper we present a new protocol called Low Energy Adaptive Tier Clustering Hierarchy (LEATCH), which offers a good compromise between delay and energy consumption and resolves some coverage problems. For our purpose, a two level hierarchical approach has been proposed to organize a sensor network into a set of clusters, every cluster divided into small clusters that are called Mini Clusters. As the way the clusters are organized, for each mini cluster we define a Mini Cluster- Head (MCH). Every MCH communicates with the cluster-head directly, it aggregates its mini-cluster information. In addition, we have made some changes in the procedure of cluster head and mini cluster head election. LEATCH promises better performances than the conventional LEACH protocol which is one of the most known hierarchical routing protocols using the probabilistic model to manage the energy consumption in WSNs. Simulation results show that LEATCH performs better than LEACH in term of energy, delay, coverage and scalability. more...

International audience; Energy consumption has become a limiting factor for deploying large-scale distributed infrastructures. This work 1 seeks to improve the energy efficiency of backbone networks by providing an intra-domain Software Defined Network (SDN) approach to selectively turn off a subset of links. We propose the STREETE framework (SegmenT Routing based Energy Efficient Traffic Engineering) that dynamically adapts the number of powered-on links to the traffic load. The core of the solution relies on SPRING, a novel protocol being standardized by IETF. It is also known under the name of Segment Routing. The algorithms have been implemented and evaluated using the OMNET++ simulator. Experimental results show that the consumption of 44% of links can be reduced while preserving good quality of service. more...

In this article, we study the issue of delay optimization and energy efficiency in grid wireless sensor networks (WSNs). We focus on STDMA (Spatial reuse - Time Division Multiple Access) scheduling, where a predefined cycle is repeated, and where each node has fixed transmission opportunities during specific slots of the cycle (defined by colors). We assume a STDMA algorithm that takes advantage of the regularity of grid topology to also provide a spatially periodic coloring ("tiling" of the same color pattern). In this setting, the key challenges are: 1) minimizing the average routing delay by ordering the slots in the cycle 2) being energy efficient. The solution we propose is called ORCHID. It proceeds in two steps. In the first step, ORCHID starts from a colored grid and builds a hierarchical routing based on these colors. In the second step, ORCHID builds a color ordering by considering jointly both routing and scheduling so as to ensure that any node will reach a sink in a single STDMA cycle. Simulation results show the excellent performance of ORCHID in terms of delays and energy compared to shortest-delay path routing. more...

International audience; A fault-tolerant routing algorithm in Network-on-Chip architectures provides adaptivity for on-chip communications. Adding fault-tolerance adaptivity to a routing algorithm increases its design complexity and makes it prone to deadlock and other problems if improperly implemented. Formal verification techniques are needed to check the correctness of the design. This paper performs formal analysis on an extension of the link-fault tolerant Network-on-Chip architecture introduced by Wu et al. that supports multiflit wormhole routing. This paper describes several lessons learned during the process of constructing a formal model of this routing architecture. Finally, this paper presents how the deadlock freedom and tolerance to a single-link fault is verified for a two-by-two mesh version of this routing architecture. more...

The design of efficient Wireless Sensor Networks (WSN) is a very hot topic nowadays. The efficiency could be observed at many levels, from the application layer to the physical part. In order to get better performances over WSN, many parameters could be considered: the application type, the routing protocol, the MAC protocol, the physical protocol, the radio range of nodes, the topology of the networks. In this paper 1 , 2 , we present a support-tool that we have developed in order to manage all these parameters in order to help designers to choose the most appropriate value for each parameter involved in the design of efficient solutions based on WSN. This tool has used a learning step where intensive simulations have been conducted. The results of this step allow the platform to suggest the most appropriate parameter for any situation chosen by the designer. The tool could be handled easily with adequate GUI. In addition, it is also able to generate NS-2 scripts in order to check the efficiency of the proposed configurations. more...

International audience; The devices composing Wireless Sensor Networks (WSN) are very limited in terms of memory, processing power and battery. We need efficient routing algorithms to ensure a long lifetime of the WSN. However, many solutions focus on minimizing the average energy consumption of all the nodes. Since the lifetime is rather given by the death of the first node or by the disconnection of the network, these solutions are currently insufficient. Here, we have rather chosen to focus on identifying the energy bottlenecks (i.e., the nodes that are more likely to be the first ones to run out of energy). Minimizing their energy consumption will surely improve the network lifetime. We define here the Expected LifeTime (ELT) routing metric to estimate the lifetime of these bottlenecks. We take into account both the amount of traffic and the link reliability to estimate how much energy such a bottleneck consumes on average. Moreover, we apply this metric to the RPL architecture, the de facto routing standard in the Internet of Things. We construct the Directed Acyclic Graph structure based on this ELT criteria while avoiding the creation of loops. more...

International audience; Wireless Sensor Networks (WSN) are composed of constrained devices and deployed in unattended and hostile environments. Most papers presenting solutions for WSN evaluate their work over random topologies to highlight some of their "good" performances. They rarely study these behaviors over more than one topology. Yet, the topology used can greatly impact the routing performances. This is what we demonstrate in this paper. We present a study of the impact of the network topology on algorithm performance in WSNs and illustrate it with the geographic routing. Geographic routing relies on node coordinates to route data packets from source to destination. We measure the impact of different network topologies from realistic ones to regular and very popular ones through extensive simulation and experimentation campaigns. We show that different topologies can lead to a difference of up to 25% on delivery ratio and average route length and more than 100% on energy costs. more...

International audience; The most basic function of an Internet router is to decide, for a given packet, which of its interfaces it will use to forward it to its next hop. To do so, routers maintain a routing table, in which they look up for a prefix of the destination address. The routing table associates an interface of the router to this prefix, and this interface is used to forward the packet. We explore here a new measurement method based upon distributed UDP probing to estimate this routing table for Internet routers. more...

International audience; This article presents a future-driven routing architecture for Internet of Things (IoT). This IoT is a novel concept involving a new concept regarding a set of things with the same routing and service polices, denoted by an autonomous system of things (ASoT). In IoT, an ASoT would be connected not only to the others but legacy autonomous systems (ASs) for the Internet in a wide variety of scenarios. Hence, this article firstly addresses classification of diverse features of ASoTs, and then explores new challenges especially on inter-domain routing more...

Geographic routing protocols use location information when they need to route packets. In the meantime, location information are maintained by location-based services provided by network nodes in a distributed manner. Routing and location services are very related but are used separately. Therefore, the overhead of the location-based service is not considered when we evaluate the geographic routing overhead. Our aim is to combine routing protocols with location-based services in order to reduce communication establishment latency and routing overhead. Our main contribution is to reduce the location overhead. Thus, we propose two combinations: (1) a geographic routing protocol with GLS called Hybrid Routing and Grid Location Service (HRGLS) and (2) a geographic routing protocol with HLS denoted Hybrid Routing and Hierarchical Location Service (HRHLS), where instead of launching an exact position request, we send the packet to the old destination position and when the packet is approaching the former position, we request the exact one. The complexity of the location query cost in both proposed schemes is O(logN), while it is O(N) in the case of HLS and GLS. Simulation results also confirm the complexity analysis and show promising results in terms of latency, packet delivery ratio and control message overhead. more...

International audience; Network lifetime has become the key characteristic for evaluating sensor networks in an application-specific way. In this paper, we focus on Mobile Wireless Sensor Networks, which are specific opportunistic networks because of their poor connectivity among the mobile sensors, and thus it is difficult to form a well connected mesh network for transmitting data through end-to-end connections from the sensors to the sink. We propose EXLIOSE (Novel approach to EXtending network LIfetime in Opportunistic SEnsor Networks), a routing protocol that focuses on maximizing network lifetime while keeping high delivery statistics. EXLIOSE is based on a novel routing metric that uses the history of encounters between nodes, and the nodal residual energy. Simulation results show that our approach is able to extend network lifetime and achieve good delivery statistics, as compared to state-of-the-art solutions. © 2014 IEEE. more...

The combined network design and (distributed)traffic routing problem can be formulated as a large-scale multi-period mixed integer optimization problem. This problem com-bines network design decisions and routing decisions, with time-dependent demands. A compact formulation for this problem,based on the aggregation of flows by destination, was proposedin [1]. They observed that the resolution on realistic instancesbecomes intractable and unscalable with state-of-the-art solversdue to the weak linear programming bound provided by theformulation. In this paper, we consider an extended formulationwhere flows are decomposed by origin-destination pairs, whilekeeping the requirement of destination-based routing. The qualityof the extended formulation and the computational time neededto solve it are evaluated on a representative set of networktopologies and traffic demands, and compared to results obtainedwith the base formulation of [1]. The extended formulation canthen be considered for more efficient resolution methods involvingdecomposition and cutting planes approaches., info:eu-repo/semantics/published more...

Language of publication: en; International audience; no abstract

International audience; In this paper, we present a generalized multipath load sharing framework for Internet. Under the hypothesis that edge networks are fully independent in establishing Internet routing policies, we use game theory and a vectorized utility function to solve the Internet multipath routing problem. We first briefly review the existing techniques that apply game theory to improve the Internet routing resiliency. We propose a vectorized routing cost model to consider multiple routing metrics in the network setting, along with a universal refinement method to quantify the profile performance and predict the behavior of the vectorized routing game. Based on the universal refinement method as well as a linear traffic distribution algorithm, we define a generalized multipath load sharing framework to improve the routing resiliency in traffic exchange between two distant edge networks. Running simulations with real measured Internet metrics, we find that the proposed generalized edge-to-edge multipath load sharing framework is able to offer far more resilient solutions than legacy and alternative protocols such as standard BGP and BGP with LISP-based traffic engineering. more...

International audience; —Routing in cooperative vehicular networks is a challenging work due to high mobility of vehicles and difficulty of localization. In this paper, we study the geocast routing problem in Vehicular Ad-Hoc Networks (VANets), which aims at delivering data to a specific group of mobile vehicles identified by their geographical location. Although many geocast routing protocols have been proposed, only partial inherent constraints of VANets (such as mobility, frequent fragmentation and overload) are taken into account. Therefore, we propose two novel robust geocast routing protocols: The first one called Robust Geocast Routing Protocol for Safety Applications (RGRP-SA), while the other one, namely Robust Geocast Routing Protocol for Comfort Applications (RGRP-CA). Simulations conducted in NS-2 demonstrate that our safety-oriented RGRP-SA protocol outperforms the counterpart protocols in terms of number of sent packets and end-to-end delay. Besides, it is also shown that our comfort-oriented RGRP-CA protocol serves well comfort applications by providing reliable data delivery and high throughput. more...

International audience; The hierarchical clustering for wireless sensors networks is treated to solve the scalability problem in routing protocols for multi-hop wireless networks. Also a clustering-based technique is proposed to provide location management of devices for QoS support. To the best of our knowledge there is no protocol that combines the hierarchical partitioning into clusters and cliques taking into account the size of cliques and clusters (a clique is a network where every node can communicate directly with every other node in the same clique). In this paper, we propose a new partitioning scheme motivated by the need to have minimum and maximum size for cliques and clusters. In fact, this size has a direct effect on energy consumption. Indeed, for a large size of clique or cluster the cluster head should register the identities of its cluster members and manage them. That is not always feasible because sensor networks have a very limited memory capacity and energy. In addition, limiting the number of sensors in each clique or cluster avoids a significant number of cluster head re-election where the energy will be the parameter of election. So the characteristics of WSN are not satisfied, the aim of our work is to deal with these cases. more...

International audience; Networks-on-Chip (NoCs) are currently the most appropriate communication structure for many-core embedded systems. Those networks support many real-time data flows. Their performance depends directly on the routing strategy. In this paper, we present a new congestion-aware routing algorithm (FlexOE) based on a simple and flexible scheme of prioritized sets of rules. These sets of rules are based on the Odd-Even turn model, minimal paths checking, congestion information from adjacent routers and availability of output path. The algorithm FlexOE developed is integrated on a Hermes NoC, and then implemented on an FPGA. The evaluation results point out that FlexOE has greater performances than reference algorithms for some test scenarios and similar performances for others test scenarios. more...

Recent years witnessed growing concerns regarding scalability of today's Internet architecture. Universality of the single IP numbering space is one cause of unbound growth of entropy and inter-domain routing tables in the core network. Recently, the IAB proposed to review the Internet addressing architecture to separate name and location spaces. In this paper, we propose an instance of VIN-based IPv6 addressing, compatible with other Future Internet efforts, to tackle this issue with regards to the vehicular communications. We design a global hierarchical identification space of up to 235 unique and distinct vehicles per manufacturer (216 manufacturers). An original method of mapping these identifiers to addresses and guarantee the uniqueness conservation is proposed. The objective is to create a sustainable addressing architecture for vehicular communications and introduce the manufacturer as a new vehicular services provider. We also propose a network architecture design that allows to use pseudonyms as a way to tackle identity privacy concerns. more...

International audience; IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) is one of the the emerging routing standards for multihop Wireless Sensor Networks (WSN). The protocol is based on the construction of a Destination-Oriented Direct Acyclic Graph (DODAG), which offers a loop-free topology to route data packets. While several metrics have been proposed in the literature, it is unclear how they perform with RPL. In this paper, we analyze the impact of different PHY and MAC metrics to the stability and the efficiency of RPL. We highlight the fact that realistic conditions lead to instabilities and oscillations in the routing structure. While minimizing the hop length leads to a stable but poor routing structure, more sophisticated link metrics such as ETX reflect more clearly the radio link quality but increase the number of DODAG reconfigurations. We also provided a detailed methodology to measure the DODAG stability and to implement efficiently each routing metric with RPL. more...

International audience; Delay-Tolerant Networks (DTN) model systems that are characterized by intermittent connectivity and frequent partitioning. Routing in DTNs has drawn much research effort recently. Since very different kinds of networks fall in the DTN category, many routing approaches have been proposed. In particular, the routing layer in some DTNs have information about the schedules of contacts between nodes and about data traffic demand. Such systems can benefit from a previously proposed routing algorithm based on linear programming that minimizes the average message delay. This algorithm, however, is known to have performance issues that limit its applicability to very simple scenarios. In this work, we propose an alternative linear programming approach for routing in Delay-Tolerant Networks. We show that our formulation is equivalent to that presented in a seminal work in this area, but it contains fewer LP constraints and has a structure suitable to the application of Column Generation (CG). Simulation shows that our CG implementation arrives at an optimal solution up to three orders of magnitude faster than the original linear program in the considered DTN examples. more...

International audience; IP networks may face issues to support the offered workload due to the increasing number of Internet users, the steady influx of new Internet applications, which require stringent QoS, and applications needing big data transmission. QoS routing can be viewed as an attractive approach to tackle this issue. However, most of the QoS routing solutions are not evaluated in a realistic framework. In this paper we propose a networking evaluation of multi-constrained routing to assess the potential benefit of QoS routing protocol. To do this, we converted a multi-constrained routing algorithm into a protocol, and implemented it in the simulator NS2. Our results indicate that if the monitoring tool of a network can not sustain frequent link-state announcements, the benefits coming from implementing a QoS routing are quite low. On the other hand, if the network is equipped with an adequate measurement tool, then QoS routing can be worth implementing, and the routing based only the available bandwidth at each link arises as the best option (no need to consider the end-to-end delay constraint, nor the loss rate constraint). more...

International audience; Graph coloring was exploited in wireless sensor networks to solve many optimization problems. These problems are related in general to channel assignment. In this paper, we propose to jointly use coloring for routing purposes. We introduce CHRA a coloring based hierarchical routing approach. Coloring is exploited to avoid interferences and also to schedule nodes transmissions to sink. We provide an analytical and experimental study assessing the performance of CHRA in terms of end-to-end delay and energy consumption. In particular, we find that CHRA performs better than LEACH, a well established hierarchical routing protocol. more...

International audience; In this paper, we investigate the problem of determining the routing that minimizes the maximum/average delivery time or the maximum/average delivery delay for a set of packets in a deterministic Delay Tolerant Network, i.e. in a network for which all the nodes' transmission opportunities are known in advance. While the general problem with multiple sources and multiple destinations is NP-hard, we present a polynomial time algorithm that can efficiently compute the optimal routing in the case of a single destination or of a single packet that needs to be routed to multiple destinations. more...

In Delay Tolerant Networks (DTN), contemporaneous end-to-end paths are rarely available. Routing in such networks is therefore one of the challenging issues. When the DTN is made of humans, human mobility characterizes the forwarding opportunities. To leverage the diversity of the strengths of social ties, a number of utility-based routing policies have been proposed. In this paper we first address theoretically the optimization problem of the routing policy in such a social DTN, under a multi-community network model, and we prove that the optimal policies have a per-community threshold structure, thereby generalizing the existing works for homogeneous mobility DTN. We then provide analysis of this result on a numerical example, and discuss the comparison of such optimal policies with the online utility-based policies of the literature. more...

International audience; Controlled mobility is one of the most complex challenges in Wireless Sensor Networks (WSN). Only a few routing protocols consider controlled mobility in order to extend the network lifetime. They are all designed to optimize the physical route topology from a source to a destination. However, there is often more than one sensor which reports an event to the sink in WSN. In existing solutions, this leads to oscillation of nodes which belong to different routes and their premature death. Experiments show that the need of a routing path merge solution is high. As a response we propose the first routing protocol which locates and uses paths crossing to adapt the topology to the network traffic in a fully localized way while still optimizing energy efficiency. Furthermore the protocol makes the intersection to move away from the destination, getting closer to the sources, allowing higher data aggregation and energy saving. Our approach outperforms existing solutions and extends network lifetime up to 37%. more...