Data gathering systems in the Industrial IoT require an end-to-end latency as low as 1 s with coverage of a few hundred meters. The 6TiSCH standard is well suited for these types of applications. A 6TiSCH network is a multihop wireless IPv6 network which uses time-slotted channel hopping (TSCH). TSCH is a medium access mode of IEEE802.15.4 which provides deterministic properties, and increases robustness against external interference and multipath fading. A key component of TSCH is its scheduling function that builds the communication schedule, which greatly impacts network performance. Although there are several proposed TSCH scheduling solutions in the literature, most of them are not directly applicable to 6TiSCH for real-world deployments because they fail to take into consideration the dynamics of a network. Some of them assume afixedrouting topology, which does not match 6TiSCH where the routing topology dynamically changes with the radio environment. In this article, we propose a full-featured 6TiSCH scheduling function called YSF, that autonomously takes into account all aspects of network dynamics, including the network formation phase and parent switching. YSF aims at minimizing latency and maximizing reliability for data gathering applications. We evaluate YSF by simulation, and compare it to MSF, the state-of-art scheduling function being standardized by the IETF 6TiSCH working group.

Wireless sensor networking is a key enabler of Industrial IoT. IETF (Internet Engineering Task Force) has standardized a protocol suite called 6TiSCH (IPv6 over the TSCH mode of IEEE802.15.4e). 6TiSCH builds an IPv6 multi-hop wireless network with the IEEE802.15.4 radio, which achieves low energy consumption and high reliability. Although network formation time is one of key performance indicators of wireless sensor networks, it has not been studied well with 6TiSCH standard protocols such as MSF (6TiSCH Minimal Scheduling Function) and CoJP (Constrained Join Protocol). In this paper, we propose a scheduling function called SF-Fastboot which shortens network formation time of 6TiSCH. We evaluate SF-Fastboot by simulation comparing with MSF, the state-of-the-art scheduling function. The simulation shows SF-Fastboot reduces network formation time by 41 % – 80 %.

Abstract We consider a shared transportation system in an urban environment where human drivers collect vehicles that are no longer being used. Each driver, also called a platoon leader, is in charge of driving collected vehicles as a platoon to bring them back to some given location (e.g., an airport, a railway station). Platoon allocation and route planning for picking up and returning automated vehicles is one of the major issues of shared transportation systems that need to be addressed. In this article, we propose a coalition game approach to compute (1) the allocation of unused vehicles to a minimal number of platoons, (2) the optimized tour of each platoon, and (3) the minimum energy consumed to collect all these vehicles. In this coalition game, the players are the parked vehicles, and the coalitions are the platoons that are formed. This game, where each player joins the coalition that maximizes its payoff, converges to a stable solution. The quality of the solution obtained is evaluated with regard to three optimization criteria and its complexity is measured by the computation time required. Simulation experiments are carried out in various configurations. They show that this approach is very efficient to solve the multiobjective optimization problem considered, since it provides the optimal number of platoons in less than a second for 300 vehicles to be collected, and considerably outperforms other well‐known optimization approaches such as multiobjective particle swarm optimization and nondominated sorting genetic algorithm.

Data Centers (DCs) need to periodically configure their servers in order to meet user demands. Since appropriate proactive management to meet demands reduces the cost, either by improving Quality of Service (QoS) or saving energy, there is a great interest in studying different proactive strategies based on predictions of the energy used to serve CPU and memory requests. The amount of savings that can be achieved depends not only on the selected proactive strategy but also on user-demand statistics and the predictors used. Despite its importance, it is difficult to find theoretical studies that quantify the savings that can be made, due to the problem complexity. A proactive DC management strategy is presented together with its upper bound of energy cost savings obtained with respect to a purely reactive management. Using this method together with records of the recent past, it is possible to quantify the efficiency of different predictors. Both linear and nonlinear predictors are studied, using a Google data set collected over 29 days, to evaluate the benefits that can be obtained with these two predictors.

The main requirement of Industrial Internet of Things (IIoT) is reliability with a targeted reliability of above 99.999%. Then come latency and energy-efficiency requirements. The next step for the IIoT is to target time-critical applications. Even if IIoT technologies are now adopted worldwide, challenges remain and some of the limits of the technologies are still not fully understood. In this paper, we address TSCH-based (Time Slotted Channel Hopping) Wireless Sensor Networks and study their latency and lifetime limits under real-world conditions. We compute theoretical bounds on the end-to-end latency in a perfect radio environment and then in real deployments with unreliable links. We compare the performance of different scheduling algorithms and evaluate the impact of unreliable links on end-to-end latency and network lifetime, by means of simulations using traces collected from real deployed TSCH networks.

Soil degradation and hot climate explain the poor yield of olive groves in North Algeria. Edaphic and climatic data were collected from olive groves and analyzed by Self-Organizing Maps (SOMs). SOM is a non-supervised neural network that projects high-dimensional data onto a low-dimension topological map, while preserving the neighborhood. In this paper, we show how SOMs enable farmers to determine clusters of olive groves, to characterize them, to study their evolution and to decide what to do to improve the nutritional quality of oil. SOM can be integrated in the Intelligent Farming System to boost conservation agriculture.

The knowledge of link quality in IoT networks allows a more accurate selection of wireless links to build the routes used for data gathering. The number of retransmissions is decreased, leading to a shorter end-to-end latency, a better end-to-end reliability and a larger network lifetime. We propose to predict link quality by means of machine learning techniques applied on two metrics: RSSI and PDR. The accuracy got by Logistic Regression, Linear Support Vector Machine, Support Vector Machine and Random Forest classifier is computed on the traces of a real IoT network deployed in Grenoble.

Data collected from an operational Google data center during 29 days represent a very rich and very useful source of information for understanding the main features of a data center. In this paper, we highlight the strong heterogeneity of jobs. The distribution of job execution duration shows a high disparity, as well as the job waiting time before being scheduled. The resource requests in terms of CPU and memory are also analyzed. The knowledge of all these features is needed to design models of jobs, machines and resource requests that are representative of a real data center.

Traces collected from an operational Google data center over 29 days represent a very rich and useful source of information for understanding the main features of a data center. In this paper, we characterize the strong heterogeneity of jobs and the medium heterogeneity of machine configurations. We analyze the off-periods of machines. We study the distribution of jobs per category, per scheduling class, per priority and per number of tasks. The distribution of job execution durations shows a high disparity, as does the job waiting time before being scheduled. The resource requests in terms of CPU and memory are also analyzed. The distribution of these parameter values is very useful to develop accurate models and algorithms for resource allocation in data centers.

TSCH (Time Slotted Channel Hopping) networks are excellent candidates to support applications of industry 4.0 with latency, energy and reliability requirements. However, such applications have to face topology, traffic or even application changes. How can TSCH networks adapt to such changes? We propose a solution ranging from network construction to data gathering. We show how the schedule can adapt to changing topology, traffic and application conditions. We compute the theoretical bounds with regard to key performance indicators and compare them with the values obtained by NS3 simulation.

Game theory is a powerful tool that has recently been used in networks to improve the end users' quality of experience (e.g. decreased response time, higher delivery rate). In this paper, we propose to use game theory in the context of Content Delivery Networks (CDNs) to organize video contents into clusters having similar request profiles. The popularity of each content in the cluster can be determined from the popularity of the representative of the cluster and used to store the most popular contents close to end users. A group of experts and a decision-maker predict the popularity of the representative of the cluster. This considerably reduces the number of experts used. More precisely, we model the clustering problem as a hedonic coalition formation game where each coalition represents a cluster. The coalition game converges to a stable partition representing a solution of the problem considered. We compare the results of this approach with the clustering obtained by the K-means algorithm. We evaluate the impact of the content profile observation window considered to establish the clustering. We also evaluate the complexity of the proposed algorithm. Simulation results are obtained on traces of a real CDN. Finally, we extend the proposed approach to model an on-line clustering reflecting the CDN dynamics in terms of proposed contents and contents solicitations.

Wireless Sensor Networks (WSNs) are used in a wide range of applications due to their monitoring and tracking abilities. Depending on the applications goals, sensor nodes are deployed either in a two dimensional (2D) area or in a three-dimensional (3D) area. In addition, WSN deployment can be either in a distributed or a centralized manner. In this paper, we are interested in a fully distributed deployment of WSN in several 3D-flat-surface configurations using autonomous and mobile nodes. Our goal is to ensure full 3D flat surfaces coverage and maintain network connectivity for these surfaces. To reach our goal we propose 3D-DVFA-FSC, a distributed deployment algorithm based on virtual forces strategy to move sensor nodes over different 3D-flat-surface shapes. Simulation results show that 3D-DVFA-FSC provides a full coverage rate regardless of the 3D-flat-surface configuration while maintaining network connectivity.

Time Slotted Channel Hopping (TSCH) networks are emerging as a promising technology for the Internet of Things and the Industry 4.0 where ease of deployment, reliability, short latency, flexibility and adaptivity are required. Our goal is to improve reliability of data gathering in such wireless sensor networks. We present three redundancy patterns to build a reliable path from a source to a destination. The first one is the well-known two node-Disjoint paths. The second one is based on a Triangular pattern, and the third one on a Braided pattern. A comparative evaluation is carried out to analyze the reliability achieved, the number of failures tolerated, the number of message copies generated and the energy consumed by each node to ensure that at least one copy of the message is delivered to the destination. These results are validated by simulations.

In this paper we propose an analysis of a slotted based protocol designed for devices of the Internet of Thing (IoT). In contrast to other TDMA-based protocols this scheme uses a random technique to access shared slots which presents similarities with CSMA protocols. In practice the transmissions are scheduled in a given back-off window of slots whose duration allows the transmission of a packet and its acknowledgment. Therefore this protocol can be analyzed according to the methodology introduced by Bianchi for the IEEE 802.11 protocol even if the protocol studied differs in many aspects. The model we use is also particular because we succeed in obtaining a Markov model even if the scheme used to send a packet (in a node) may depend on the transmission of the previous packet. We distinguish two protocols; in the first one, at the initial stage or after a successful transmission, the packets are transmitted without any back-off, whereas in the second protocol each transmission is always preceded by the count down of a random back-off. Extensive simulations validate the models of both protocols and a comparative performance evaluation is carried out.

Time Slotted Channel Hopping (TSCH), specified in the IEEE 802.15.4e amendment, has been designed for industrial automation, process control and equipment monitoring. It uses a slotted medium access on several channels in parallel and supports multihop communications. In this paper, we study how applications with data delivery constraints can be supported by a TSCH network. We first propose a framework based on a multislotframe that allows the coexistence of Data Slotframes and Control Slotframes. We then determine a lower bound on the minimum number of slots required to perform data gathering, taking into account the number of channels, the number of interfaces of the sink, the number of packets generated by each sensor node as well as the number of children of the sink. These feasibility conditions are established for two cases: with spatial reuse and without. We propose a debt-based scheduler that for simple topologies, provides a schedule minimizing the slotframe size. Finally, we consider a network configuration representative of an industrial application and evaluate the performance of the TSCH network in terms of data delivery delay and queue size for each sensor node, using the NS-3 simulator. Simulation results confirm the theory.

Deployment of sensor nodes to fully cover an area has caught the interest of many researchers. However, some simplifying assumptions are adopted such as knowledge of obstacles, centralized algorithm... To cope with these drawbacks, we propose OA-DVFA (Obstacles Avoidance Distributed Virtual Forces Algorithm) a self-deployment algorithm to ensure full area coverage and network connectivity. This fully distributed algorithm is based on virtual forces to move sensor nodes. In this paper, we show how to avoid the problem of node oscillations and to detect the end of the deployment in a distributed way. We evaluate the impact of the number, shape and position of obstacles on the coverage rate, the distance traveled by all nodes and the number of active nodes. Simulation results show the very good behavior of OA-DVFA.

Game theory is often used to find equilibria where no player can unilaterally increase its own payoff by changing its strategy without changing the strategies of other players. In this paper, we propose to use coalition formation to compute the optimized tours of mobile sinks in charge of collecting data from static wireless sensor nodes. Mobile sinks constitute a very attractive solution for wireless sensor networks, WSNs, where the application requirements in terms of node autonomy are very strong unlike the requirement in terms of latency. Mobile sinks allow wireless sensor nodes to save energy The associated coalition formation problem has a stable solution given by the final partition obtained. However, the order in which the players play has a major impact on the final result. We determine the best order to minimize the number of mobile sinks needed. We evaluate the complexity of this coalitional game as well as the impact of the number of collect points per surface unit on the number of mobile sinks needed and on the maximum tour duration of these mobile sinks. In addition, we show how to extend the coalitional game to support different latencies for different types of data. Finally, we formalize our problem as an optimization problem and we perform a comparative evaluation.

Most wireless sensor networks that are currently deployed use a technology based on the IEEE 802.15.4 standard. However, this standard does not meet all requirements of industrial applications in terms of latency, throughput and robustness. That is why the IEEE 802.15.4e amendment has been designed, including the Time Slotted Channel Hopping (TSCH) mode. In this paper, we focus on how to build a TSCH network and evaluate the time needed to form the network, using the NS3 simulator. A new beacon advertising algorithm is proposed for TSCH networks. A comparative performance evaluation with solutions already published is done.

Prolonging the network lifetime is a challenging problem in wireless sensor networks. Using additional mobile agents able to gather data from static sensor nodes reveals to be one of the convenient solutions in order to conserve static sensor nodes energy. In this paper, we focus on a conflictual situation between two Data Collectors (DCs) tending to gather maximum sensed data and deliver them to a sink node before a required deadline. A non-cooperative game is used to model this behavior and evaluate the performance of the gathering scheme when two DCs are competing with each other to gain more sensed data. Under this scheme, aggressive behavior is discouraged since each data gathering operation incurs sensor nodes energy decrease and data delivery delay increase.

Machine learning techniques can be used to improve the quality of experience for the end users of Content Delivery Networks (CDNs). In a CDN, the most popular video contents are cached near the end-users in order to minimize the contents delivery latency. The idea developed hereafter consists in using prediction techniques to evaluate the future popularity of video contents in order to decide which should cached. We consider various prediction methods, called experts, coming from different fields (e.g. statistics, control theory). To evaluate the accuracy of the experts' popularity predictions, we assess these experts according to three criteria: cumulated loss, maximum instantaneous loss and best ranking. We also show the importance of a decision maker, called forecaster, that predicts the popularity based on the predictions of selection of several experts. The forecaster based on the best K experts outperforms in terms of cumulated loss the individual experts' predictions and those of the forecaster based on only one expert, even if this expert varies over time.

In this paper we focus on wireless sensor networks deployed to cover some given Points of Interest (PoIs), achieve connectivity with the sink and be robust against link and node failures. The Relay Node Placement problem (RNP) consists in minimizing the number of relays needed and the maximum length of the paths connecting each PoI with the sink. We propose a solution that determines the positions of relay nodes based on the virtual grid computed by the optimal deployment for full area coverage. We compare our solution with two different solutions based respectively on 1) the straight line that builds the shortest path between each PoI and the sink, 2) the Steiner point that connects PoIs together. We then extend these algorithms to achieve k-connectivity. Our solution outperforms the Steiner points solution in terms of maximum path length on the one hand, and the straight line solution in terms of total number of relay nodes deployed on the other hand. We also apply our solution in an area containing obstacles and show that it provides very good performances.

The various reasons of failures that affect reliability of sensor nodes in addition to processing and transfer of large multimedia content (image, audio and video) have posed new challenges that are nowadays a real threat for routing protocols in Wireless Multimedia Sensor Networks (WMSNs), which aim to ensure flow delivery while guaranteeing QoS requirements. Moreover, extending network lifetime and maintaining network stability to cope with breaking links and topology changes (failures or sensor mobility), remain unsolved issues, particularly, during data transmission phase. Therefore, in this paper, we jointly consider multipath transmission, load balancing and fault tolerance, to enhance the reliability of transmitted data. We propose a Geographic Multipath routing protocol reinforced by Fault-Tolerant mechanism (GMFT). Theoricals results and those obtained from both simulation study and experiments on a real testbed demonstrate the validity and efficiency of our proposed protocol, and indicate that it is highly advised for multimedia transmission and network stability.

In Content Delivery Networks (CDNs), knowing the popularity of video content helps the manager to take efficient decisions about which video content should be cached near the end users and also about the duplication degree of each video to satisfy the end user Quality of Experience. This paper focuses on predicting the popularity of video content, in terms of the number of requests. For that purpose, different software entities, called experts, compute the popularity value of each video content. Each expert uses its own prediction method. The accuracy of expert's prediction is evaluated by a loss function as the discrepancy between the prediction value and the real number of requests. We use real traces extracted from YouTube to compare different prediction methods and determine the best tuning of their parameters. The goal is to find the best trade-off between complexity and accuracy of the prediction methods used. Finally, we apply these prediction methods to caching. Prediction methods are compared in terms of cache Hit Ratio and Update Ratio with the well-known LFU caching strategy.

The new IEEE 802.15.4e standard does not specify how the schedule of medium accesses followed by wireless sensors is built. That is why, we propose a distributed interference-aware joint channel and time slot assignment, called DiSCA, for a traffic-aware convergecast in multichannel wireless sensor networks (WSNs). Unlike most previous studies, we consider two cases of transmissions: without acknowledgment and with immediate acknowledgment. We provide the minimum bound on the number of time slots needed for a convergecast with a sink equipped with multiple radio interfaces. Simulations results show that DiSCA is close to the optimal in terms of the number of slots and outperforms TMCP.

In many applications such as precision agriculture (fruit tree plantation, olive groves) or environmental monitoring, wireless sensors are, very often, randomly scattered in the 3D area of interest. Such applications require full three-dimensional coverage. Undoubtedly, an initial random deployment does not achieve neither full coverage of the 3D area of interest, nor network connectivity. Thus, a redeployment algorithm has to be introduced in order to ensure these two goals. Our contribution is the design of 3D-DVFA, a distributed deployment algorithm based on virtual forces in three dimensional wireless sensor networks where sensor nodes are assumed to be mobile and autonomous. We simulate its behavior with NS3. The extensive simulations results demonstrate the effectiveness of the 3D algorithm proposed that provides full 3D area coverage and network connectivity.

Wireless Sensor Networks (WSNs) are deployed in many fields of application. Depending on the application requirements, sensor nodes can either be mobile and autonomous or static. In both cases, they are able to cooperate together in order to monitor a given area or some given Points of Interest (PoIs). Static sensor nodes need one or several agent(s) (humans or robots) to deploy them. In this paper, we focus on the deployment of static sensor nodes in an area containing obstacles, using two mobile robots. We want to minimize the time needed by the two robots to deploy all the sensor nodes and to return to their starting position. We require that each sensor node is placed at a PoI position, no PoI position is empty and no PoI position is occupied by more than one sensor node. The problem consists in determining the best strategy for each robot in order to meet these constraints. We adopt a game theory approach to solve this problem.

In this paper we propose a cluster-based multichannel scheduling algorithm for intra-cluster communications in Cognitive Radio Sensor Networks (CRSNs) to avoid collisions between neighbor clusters. Since nodes having neighbor nodes out of their clusters may cause collisions between neighbor clusters, when transmitting in the same time slot on the same channel, the scheduling of each cluster cannot be established independently. We propose to fix in each cluster the channels used by nodes having conflicting nodes out of their clusters. This channel assignment is done by the cluster heads in a distributed way but according to the decreasing priority order of the clusters. Then, each cluster head executes the scheduling algorithm independently. We evaluate the performance of this algorithm in terms of total number of time slots needed by all the nodes to transmit all their packets to the sink, energy consumption and transmission time interval.

Content delivery networks (CDNs) face a large and continuously increasing number of users solicitations for video contents. In this paper, we focus on the prediction of popularity evolution of video contents. Based on the observation of past solicitations of individual video contents, individual future solicitations are predicted. We compare different prediction strategies: SES, DES and Basic. The best tuning of each strategy is determined, depending on the considered phase of the solicitation curve. Since DES and Basic experts outperform the SES expert, our method combines DES and Basic experts to predict the number of solicitations within a phase and automatically detect the phase changes, respectively. This self-learning and prediction method can be applied to optimize resources allocation in service oriented architectures and self-adaptive networks, more precisely for the CDN cache nodes management.

A main reason to the growth of wireless sensor networks deployed worldwide is their easy and fast deployment. In this paper we consider deployments assisted by mobile robots where static sensor nodes are deployed by mobile robots in a given area. Each robot must make a tour to place its sensor nodes. All sensor nodes must be placed at their precomputed positions. The Multi-Robot Deploying wireless Sensor nodes problem, called the MRDS problem, consists in minimizing the longest tour duration (i.e. the total deployment duration), the number of robots used and the standard deviation between duration of robots tours. After a formal definition of the MRDS problem, we show how to use a multi-objective version of genetic algorithms, more precisely the NSGA-II algorithm, to solve this multi-objective optimization problem. The solutions belonging to the best Pareto front are given to the designer in charge of selecting the best trade-off taking into account various criteria. We then show how to extend this method to take obstacles into account, which is more representative of real situations.

Current Wireless Sensor Networks (WSNs) are deployed over unlicensed frequency bands that face an increased level of interference from various wireless systems. Cognitive Radio Sensor Networks (CRSNs) overcome this problem by allowing sensor nodes to access new spectrum bands to minimize interferences. In this paper, we focus on the MultiChannel Time Slot Assignment problem (MC-TSA) in CRSNs. Each sensor node is assigned the number of time slots it needs to transfer its own data as well as the data received from its children in the rooting tree rooted at the sink without interfering with other secondary users. Besides, sensor nodes cannot transmit on a channel occupied by a primary user. Our objective is to increase the network throughput offered to sensor nodes. We start by formulating the MC-TSA problem as an Integer Linear Program where the goal is to minimize the number of slots in the schedule. We then propose an Opportunistic centralized TIme slot assignment in Cognitive Radio sensor networks (OTICOR). We evaluate its performance in terms of number of slots and throughput.

Communication between sensor nodes in a Wireless Sensor Network (WSN) faces energy and bandwidth constraints. The dynamic behavior over time of the wireless channels makes ephemeral the neighborhood relation between sensors. Link quality estimation is critical for many WSN applications because it drastically influences the success of transmissions. In this paper we resort to machine learning methods to predict the short term evolution of link quality, in order to switch the data transmission on a better quality link. The problem is modeled as a game of prediction based on experts advice, using the Link-Quality Indicator (LQI) metric. A decision maker, called forecaster, advised by several experts, predicts the LQI values. The forecaster is able to learn how to adapt its strategy to predict values as close as possible to real LQI values. The proposed learning and prediction model presents a great flexibility: it is a general model that can be easily adapted to different link-quality metrics or prediction methods.

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.

In this paper, we focus on the deployment of wireless sensor nodes in an arbitrary realistic area with an irregular shape, and with the presence of obstacles that may be opaque. Moreover, we propose a simple projection-based method that tends to minimize the number of sensor nodes needed to fully cover such an area. This method starts with the optimal uniform deployment based on the triangular tessellation encompassing the whole area. Then, it projects some external sensor nodes on the border to ensure full coverage and connectivity. We show that this method outperforms the contour-based one using various types of irregular areas.

In this paper, we apply learning techniques to predict link quality evolution in a WSN and take advantage of wireless links with the best possible quality to improve the packet delivery rate. We model this problem as a forecaster prediction game based on the advice of several experts. The forecaster learns on-line how to adjust its prediction to better fit the environment metric values. Simulations using traces collected in a real WSN show the improvement of the prediction when the experts use the SES prediction strategy, whereas the forecaster uses the EWA learning strategy.

The distributed virtual forces deployment algorithm provides a very good area coverage and guarantees network connectivity for a sufficient number of sensor nodes. It relies on local information between neighboring sensor nodes. However, its main drawback is node oscillations and hence a high amount of sensor node energy wasted. The grid based strategy divides the monitored area into virtual cells. Each cell center determines the position of a sensor node. In this paper we propose GDVFA that combines the advantages of both strategies: on the one hand coverage and connectivity for virtual forces strategy and on the other hand avoidance of node oscillations for grid strategy. Simulation results reported in this paper show that GDVFA considerably reduces the energy consumed by sensor nodes. This comes from: the detection of redundant nodes that are put in sleep mode, and the avoidance of node oscillations by stopping nodes.

A typical task in wireless sensor networks (WSNs) is to collect data from sensor nodes towards one or many sinks in a multi-hop convergecast structure. In this paper, we focus on the data gathering problem with differentiated traffic, each addressed to a specific sink in multichannel WSNs. In order to find a collision-free optimized multichannel time slot assignment that minimizes the data gathering cycle, we propose a centralized traffic-aware algorithm called MUSIKA. We formulate the problem as a linear program and compute the optimal time needed for a raw data convergecast in an illustrative example. More generally, we run simulations on various network topologies to evaluate the performance of MUSIKA in terms of cycle length, maximum buffer size and slot reuse ratio for different use cases: redundant functional processing chains, different application functionalities per sink.

In aerospace applications, wireless sensor networks (WSNs) collect data from sensor nodes towards a sink in a multi-hop convergecast structure. The throughput requirement of these applications is difficult to meet with a single wireless channel. That is why, in this paper, we focus on a multichannel time slot assignment that minimizes the data gathering cycle. We first formalize the problem as a linear program and compute the optimal time needed for a raw data convergecast in various multichannel topologies. These optimal times apply to sinks equipped with one or several radio interfaces. We then propose our algorithm called MODESA and prove its optimality in various multichannel topologies. We evaluate its performances in terms of number of slots, maximum buffer size and number of active/sleep switches per node. Furthermore, we present variants of MODESA achieving a load balancing between the channels used.

Graph coloring is used in wireless ad hoc and sensor networks to optimize network resources: bandwidth and energy. Nodes access the medium according to their color. It is the responsibility of the coloring algorithm to ensure that interfering nodes do not have the same color. In this paper, we focus on wireless ad hoc and sensor networks with grid topologies. How does a coloring algorithm take advantage of the regularity of grid topology to provide an optimal periodic coloring, that is a coloring with the minimum number of colors? We propose the Vector-Based Coloring Method, denoted VCM, a new method that is able to provide an optimal periodic coloring for any radio transmission range and for any h-hop coloring, he1. In h-hop coloring, no nodes that are p-hop away, with 1 d p d h use the same color. This method consists in determining where a color can be reproduced in the grid without creating interferences while minimizing the number of colors used. We compare the number of colors provided by VCM with the number of colors obtained by a distributed coloring algorithm with line and column priority assignments. Finally, we discuss the applicability of this method to a real wireless network.

Wireless sensor networks (WSN) are generally randomly deployed in a given area. This initial deployment does not achieve neither area coverage, nor network connectivity. Thus, a redeployment algorithm has to be applied in order to achieve these two goals. This algorithm should meet performance criteria like saving energy and achieving stability. Our contribution in this paper is the design of DVFA, a distributed redeployment algorithm based on virtual forces. We simulate its behavior with NS2 and compare its performances with CVFA, a centralized version also based on virtual forces.

In this article, we describe experiments with the multicast protocol MOST (Multicast Overlay minimum Spanning Tree) on a real testbed. The testbed is a wireless multi-hop network with nodes running a MANET protocol, the OLSRv2 routing protocol, and with IEEE 802.11g hardware. We present our specification and implementation of MOST for OLSRv2. Its main feature is to build an (unicast) overlay tree covering members of a group. Through different scenarios and applications such as voice and video, we evaluate MOST performance in term of average packet delivery ratio, jitter and pay a particular attention to the MAC layer statistics. We also evaluate qualitatively and quantitatively the improvements brought by MOST compared with MPR flooding (an optimization of a pure flooding proposed and used in OLSR).

Clustering schemes offer a practical way of providing scalability when dealing with large and dense Mobile Ad hoc Networks (MANETs). The feasibility of clustering can be determined by the complexity of the cluster head selection. Optimizing the cluster head selection allows for the network to be more efficient by minimizing the signaling overhead while ensuring that the network connectivity is maintained despite topology changes. In this paper, we present some new findings on the complexity of the cluster head selection algorithms. Two variants of the cluster head selection are examined: (1) the distance-constrained selection where every node in the network must be located within a certain distance to the nearest cluster head; and (2) the size-constrained selection where each cluster is only allowed to have a limited number of members. We show that the problem of minimizing the set of cluster heads is NP-hard for both variants. We propose two distributed selection algorithms, each having logarithmic approximation ratio, for these variants. We also discuss, using NS-2 simulations, the resulting cluster size distribution and cluster head density, which impact the efficient operation of the network.

In this paper, we consider wireless ad hoc and sensor networks where energy matters. Our contribution deals with energy efficient routing. The idea consists in reducing the energy spent in the transmission of a packet from its source to its destination, while avoiding nodes with low residual energy. The solution we propose, called EOLSR, is based on the link state OLSR routing protocol. It comprises an energy model and three algorithms: selection of energy aware multipoint relays, computation of energy efficient routes and optimized broadcasts. All the design choices made for these algorithms have been validated by simulations. Moreover, EOLSR outperforms the solution that selects routes minimizing the end-to-end energy consumption, as well as the solution that builds routes based on node residual energy.

In wireless sensor networks, energy efficiency is achieved by making nodes sleep. In this paper, we propose SERENA, a node activity scheduling algorithm based on three-hop coloring. We study the performance of SERENA by simulating the conditions of a realistic environment including unidirectional links. The existence of unidirectional links causes color conflicts, which can be solved by exploiting a collaboration with the MAC layer. Such cross layering approach takes into account the real wireless environment and so enables substantial performance improvements (e.g. better reactivity to topology changes). Finally, we evaluate the benefits brought by this solution, namely the increase of network lifetime and spatial reuse.

The technique of multipoint relays (MPRs) has proved its efficiency to optimize network flooding in mobile ad hoc networks (MANETs) and wireless sensor networks. Indeed, the number of redundant retransmissions of a message broadcast in a wireless network is reduced by ensuring that only a subset of nodes selected as multipoint relays are allowed to forward the received packets. The aim of this paper is to provide an efficient solution for broadcasting in a geographical area of a mobile ad hoc network or a sensor network. For this, we define several solutions based on MPRs and compare their respective performances with regard to an optimal solution. Unfortunately, this optimal solution cannot be implemented. A solution is constituted by two modules: the first one deals with MPR selection and the second one defines the strategy for forwarding the received information. We then present an example of application in a sensor network structured in various zones. Each zone is controlled by a robot in charge of replacing failed sensors. We evaluate the benefit brought by our solution in this specific context.

Cross layering enables to have both a generic network design and optimized performance for the desired application and its operational environment. We examine here how to apply cross layering to adapt the OLSR routing protocol to the considered application and its wireless sensor environment. Cross layering with the application leads to (i) adapt OLSR timers to the application phases, (ii) maintain routes only to strategic nodes and (iii) select more stable routes based on the node movement knowledge. Cross layering with the MAC layer increases the reactivity of OLSR to topology changes and improves route stability by choosing only links of good quality. Cross layering with the energy management allows OLSR to be energy efficient and combined with node activity scheduling, to maximize network lifetime.

In wireless ad hoc and sensor networks, an analysis of the node energy consumption distribution shows that the largest part is due to the time spent in the idle state. This result is at the origin of SERENA, an algorithm to SchEdule RoutEr Nodes Activity. SERENA allows router nodes to sleep, while ensuring end-to-end communication in the wireless network. It is a localized and decentralized algorithm assigning time slots to nodes. Any node stays awake only during its slot and the slots assigned to its neighbors, it sleeps the remaining time. Simulation results show that SERENA enables us to maximize network lifetime while increasing the number of user messages delivered. We quantify the slot reuse and evaluate the impact of the frame size on network performance. We then study how to dimension buffers at the router nodes. Finally, we show how SERENA improves the node energy consumption distribution and maximizes the energy efficiency of wireless ad hoc and sensor networks.

We focus on applications with quantitative QoS (quality of service) requirements in their end-to- end response time. Two types of quantitative QoS guarantees can be delivered by a network: deterministic and probabilistic. The deterministic approach is based on a worst case analysis. The probabilistic approach uses a mathematical model to obtain the probability of the response time exceeding a given value. We assume that flows are scheduled according to non-preemptive FP/FIFO. The packet with the highest fixed priority is scheduled first. If two packets share the same fixed priority, the packet that arrives first on the node considered is scheduled first. We compare deterministic and probabilistic QoS guarantees and introduce the concept of p-schedulability: the QoS requested by all flows is met with probability p.

In this paper, we are interested in real-time flows requiring quantitative and deterministic QoS (quality of service) guarantees. We focus more particularly on two QoS parameters: the worst case end-to-end response time and jitter. We consider a FIFO (first in first out) scheduling of flows. The FIFO scheduling is the simplest one to implement and very used. We first establish a bound on the worst case end-to-end response time of any flow in the network, using the trajectory approach. We present an example illustrating our results. Finally, we show how to apply these results to the EF (expedited forwarding) class in a DiffServ (differentiated services) architecture

In this paper, we focus on the quantitative quality of service (QoS) guarantee in a differentiated services (DiffServ) domain that can be granted to an expedited forwarding (EF) flow in terms of end-to-end delay. This study shows that delays much smaller than the deterministic bound can be guaranteed with probabilities close to one. An admission control derived from these results is then proposed, providing a probabilistic QoS guarantee to EF flows.

More and more applications supported by MANETs require quality of service (QoS). QoS can be expressed in terms of bandwidth or delay. In this paper, we study the impact of the scheduling policy used by each MANET node on the QoS granted to flows. We first show how to use WCBQ, a class based queueing scheduling, in a wireless network. We then compare the performances achieved by WCBQ and priority queueing. Simulation results show that WCBQ protects flows with low throughput. All flows receive a bandwidth proportionally to their weights. WCBQ tends to minimize the variations of the average bandwidth granted to a flow as well as the end-to-end delay. We finally propose two solutions allowing the coexistence of flows with delay requirements and bandwidth requirements. These solutions guarantee a low delay to low throughput flows without penalizing the bandwidth granted to other flows

In this paper, we focus on a Bluetooth piconet, analyzing its ability to support the quality of service (QoS) requirements defined by QoS sensitive applications. We consider two QoS parameters: (i) an application constraint denoting the importance degree of a message, and (ii) an end-to-end delivery deadline. The QoS perceived by the application depends on the scheduling algorithms chosen at the medium access layer. We determine the average response time of a message obtained with three different scheduling algorithms. This evaluation takes into account message segmentation in the Bluetooth MAC layer. The first scheduling is the Bluetooth native scheduling called One-Round Robin (1-RR). The second is a variant of 1-RR where the local scheduling is based on the two QoS parameters considered. The last one, called Class-Based Earliest Deadline First (CB-EDF), takes into account the two QoS parameters both at the local level and at the global level.

Ad-hoc wireless networks are made up of mobile devices that use wireless transmission for communication. They can be set up anywhere and at any time because they neither require infrastructure nor central administration. Hence they have enormous commercial and military potential. However, the bandwidth offered to users is strongly affected by radio interferences. This paper proposes a solution taking into account radio interferences at the routing level in mobile ad-hoc networks. This solution is based on an admission control and a modified version of OLSR routing protocol that considers bandwidth reservation and interferences. A comparative performance evaluation done by NS simulations shows that this solution outperforms classical OLSR in terms of maximum number of acceptable flows, bandwidth amount granted to a flow and route stability.

In full-IP networks, IP-based protocols are used for mobility management. Therefore, one of the most important issues is to design efficient IP-based mobility management schemes and evaluate their performance. In a recent work we proposed an integration of mobile-IP with OLSR, a routing protocol for ad-hoc networks, to manage universal mobility. In this paper we present the performance measurements of this implementation in the presence of both macro-mobility and micro-mobility. The measurements we obtained justify the choice of OLSK for managing micro-mobility and show the advantage of using multipoint relays to optimize flooding of mobile-IP Agent Advertisements in the ad-hoc network.

We investigate the problem of guaranteed end-to-end response times for video/audio broadcast systems. A flow is sent by a video/audio source and recorded by video servers for local clients. Because of transmission delay variability, the video/audio flows suffer release jitter. This end-to-end guarantee is based on an admission control run only by the nodes belonging to the path of the requesting flow. The requesting flow is accepted only if it does not endanger the guarantees already granted. All nodes use a non-preemptive non-idling scheduling: video/audio servers use earliest deadline first (EDF) and other nodes use fixed priority/highest priority first (FP/HPF).

A solution for a hard real time scheduling problem in a distributed system is designed and proved. The constraints of our problem are first to preserve consistency even in the presence of concurrency and second to preserve the order of task releases, provided that task release times differ more than clock precision. That is achieved by FIFO based scheduling. The feasibility conditions resulting from the worst case response time analysis of each task set are given. The solution complexity is shown to be pseudo polynomial.

The LTPB (linear token passing bus) protocol is a timed token protocol designed by the SAE (Society of Automotive Engineers) to guarantee a specified (and usually low) latency delay for the highest-priority traffic class, even in the case of traffic peaks in other priority classes, fair access among all the stations connected to the bus, and an efficient use of the bus bandwidth. These requirements are met by requiring that each station regulate the token rotation time through a token holding timer and token rotation timers. No station faults, no modification of the logical ring, and no token loss are assumed. The behavior of the LTB protocol is analyzed under various traffic conditions. Performance evaluation is conducted using the simulation tool SPHINX. Rules are established for choosing timer values in order to achieve the required latency delay for any priority class for a given bus load. The optimum message size for file transfers is also determined. The main difference between LTPB and IEEE 802.4 in an error-free environment concerns the use of the token holding timer. How the conclusions can be applied to the IEEE 802.4 protocol is examined.>

GAM-T-103 is a French military standard specifying services provided by a real-time transport layer called the transfer layer. The main features of connection-oriented services are described. Three such features are evaluated: automatic point-to-point sampling, centralized multicast and centralized concentration. In order to compare GAM-T-103 with the ISO 8073 protocol, a generic model has been developed and implemented under a simulation tool called SPHINX. Simulation results highlight the benefits resulting from GAM-T-103 protocols: lower resource utilization ratios and better response times. GAM-T-103 protocols take advantage of the multicast capacity inherent with broadcast LANs and they relieve user application software from tedious tasks such as those related to periodic data transmissions or multipeer data transmissions.>