Search

International audience; We propose a novel localized Integrated Location Service and Routing (ILSR) scheme, based on the geographic routing protocol GFG, for data communications from sensors to a mobile sink in wireless sensor networks. The objective is to enable each sensor to maintain a slow-varying routing next hop to the sink rather than the precise knowledge of quick-varying sink position. In ILSR, sink updates location to neighboring sensors after or before a link breaks and whenever a link creation is observed. Location update relies on flooding, restricted within necessary area, where sensors experience (next hop) change in GFG routing to the sink. Dedicated location update message is additionally routed to selected nodes for prevention of routing failure. Considering both unpredictable and predictable (controllable) sink mobility, we present two versions. We prove that both of them guarantee delivery in a connected network modeled as unit disk graph. ILSR is the first localized protocol that has this property. We further propose to reduce message cost, without jeopardizing this property, by dynamically controlling the level of location update. A few add-on techniques are as well suggested to enhance the algorithm performance. We compare ILSR with an existing competing algorithm through simulation. It is observed that ILSR generates routes close to shortest paths at dramatically lower (90% lower) message cost.

International audience; The ultimate test for many network layer protocols designed for wireless sensor networks would be to run on a large scale testbed. However, setting up a real-world large scale wireless sensor network (WSN) testbed requires access to a huge surface as well as extensive financial and human resources. Due to limited access to such infrastructures, the vast majority of existing theoretical and simulation studies in WSN are far from being validated in realistic environments. A more affordable approach is needed to provide preliminary insights on network protocol performances in large WSN. To replace large and expensive realistic testbeds, we introduce a novel approach to emulation. We propose a specifically designed experimental setup using a relatively small number of nodes forming a real one-hop neighborhood used to emulate any real WSN. The source node is a fixed sensor, and all other sensors are candidate forwarding neighbors towards a virtual destination. The source node achieves one forwarding step, then the virtual destination position and neighborhood are adjusted. The same source is used again to repeat the process. The main novelty is to spread available nodes regularly following a hexagonal pattern around the central node, used as the source, and selectively use subsets of the surrounding nodes at each step of the routing process to provide the desired density and achieve changes in configurations. Compared to real testbeds, our proposition has the advantages of emulating networks with any desired node distribution and densities, which may not be possible in a small scale implementation, and of unbounded scalability since we can emulate networks with an arbitrary number of nodes. Finally, our approach can emulate networks of various shapes, possibly with holes and obstacles. It can also emulate recovery mode in geographic routing, which appears impossible with any existing approach.

International audience; We propose to apply the concept of Cost-to-Progress Ratio (CPR) in greedy routing for load reduction and balancing. The load of a node is the percentage of time it is occupied by forwarding traffic or inability to forward due to interference. The resultant routing protocol, named CPR-routing, is a localized parameterless approach, optimizing the ratio of nodal load and geographic progress. Through extensive simulation, we evaluate it in comparison with an existing parameter-based localized solution, α-routing. Our simulation results indicate that CPR-routing outperforms α-routing in per node load, success rate, and average hop count.

International audience; Setting up large experimental testbeds for wireless sensor networks (WSN) requires access to a huge surface as well as extensive financial and human resources. Due to limited access to such infrastructures, the vast majority of existing theoretical and simulation studies on georouting are not evaluated in real environments. A more affordable approach is needed to provide preliminary insights on network protocols performance. To overcome the need for a large number of sensors required to perform realistic experiments we introduce a novel approach to emulation. We propose to emulate large scale experiment by using a smaller number of core sensor nodes. These nodes are the 1-hop neighborhood of node S, currently holding the packet to forward, and are potential next hops. The destination position is virtual, outside of this real neighborhood. Emulation is performed as follows: (i) S transmits the packet over a real wireless channel to the selected forwarding node B, (ii) re-map the node B to S and its neighborhood to core nodes, (iii) adjust the position of the virtual destination by translating it by BS. We repeat these steps until the virtual destination falls into the 1-hop neighborhood of the node currently holding the packet. Compared to real testbeds, our emulation allows testing networks of very high densities and provides unlimited scalability.

International audience; This paper proposes a new solution to the problem of self-deploying a network of wireless mobile robots with simultaneous consideration to several criteria, that are, the fault-tolerance (\emph{biconnectivity}) of the resulting network, its \emph{coverage}, its \emph{diameter}, and the {\em quantity of movement} required to complete the deployment. These criteria have already been addressed individually in previous works, but we propose here an elegant solution to address all of them at once. Our approach is based on combining two complementary sets of virtual forces: \emph{spring} forces, whose properties are well known to provide optimal coverage at reasonable movement cost, and \emph{angular} forces, a new type of force proposed here whose effect is to rotate two {\em angularly consecutive} neighbors of a node toward one another when the corresponding angle is larger than $60^\circ$ (even if these two nodes are not themselves neighbors). Angular forces have the global effect of biconnecting the network and reducing its diameter, while not affecting the benefits obtained by spring forces on coverage. In this paper we give a detailed description of both types of forces, whose combination poses a number of technical challenges. We also provide an implementation that relies only on position exchanges within two hops. Extensive simulations are finally presented to evaluate the solution against all criteria (coverage, biconnectivity, quantity of movements, and diameter), and show its advantages over prior solutions.

Vehicular networks are envisioned for large scale deployment, and standardization bodies, car manufacturers, and academic researchers are solving a variety of related challenges. After a brief description of intelligent transportation system (ITS) architectures and the main already-established low-level standards, this tutorial elaborates on four particular aspects of vehicular networks, which are (i) the potential for a large set of innovative applications, (ii) a review of the main modeling approaches used for both roads and traffic, and finally two important communication primitives, that are (iii) data dissemination via broadcasting/geocasting, and (iv) routing in both highway and urban environments. A particular emphasis is on recent protocols that realistically consider the inherently complex nature of vehicular mobility, such as intermittent connectivity, speed variability, and the impact of intersections. Copyright © 2009 John Wiley & Sons, Ltd.

International audience; Existing theoretical and simulation studies on georouting appear detached from experimental studies in real environments. We set up our test environment by using WSN430 wireless sensor nodes. To overcome the need for significant number of wireless nodes required to perform a realistic experiment in high density network, we introduce a novel approach - emulation by using relatively small number of nodes in 1-hop experimental setup. Source node is a fixed sensor, all available sensors are candidate forwarding neighbors with virtual destination. Source node makes one forwarding step, destination position is adjusted, and the same source again searches for best forwarder. We compare three georouting algorithms. We introduce here Greedy geographical routing Algorithms in a REal environment (GARE) which builds a RNG by using ETX(uv) |uv| as edge weight (ETX(uv) counts all transmissions and possibly acknowledgments between two nodes until message is received), and selects RNG neighbor with greatest progress toward destination (if none of RNG neighbors has progress, all neighbors are considered). Our experiments show that GARE is significantly more efficient than existing XTC algorithm (applying RNG on ETX(uv)) in energy consumption. COP GARE selects neighbor with progress that minimizes ETX(uv) |uv| , and outperforms both algorithms.

International audience; This paper considers the problem of designing power efficient routing with guaranteed delivery for sensor networks with known distances between neighbors but unknown geographic locations. We propose HECTOR, a hybrid energy efficient tree-based optimized routing protocol, based on two sets of virtual coordinates. One set is based on rooted tree coordinates, and the other is based on hop distances toward several landmarks. In our algorithm, the node currently holding the packet forwards it to its neighbor that optimizes ratio of power cost over distance progress with landmark coordinates, among nodes that reduce landmark coordinates and do not increase tree coordinates. If such a node does not exist then forwarding is made to the neighbor that reduces tree based distance and optimizes power cost over tree distance progress ratio. Our simulations show the superiority of our algorithm over existing alternatives while guaranteeing delivery, and only up to 30 \% additional power compared to centralized shortest weighted path algorithm.

International audience; We propose several localized sensor area coverage protocols for heterogeneous sensors, each with arbitrary sensing and transmission radii. The approach has a very small communication overhead since prior knowledge about neighbor existence is not required. Each node selects a random time out and listens to messages sent by other nodes before the time out expires. Sensor nodes whose sensing area is not fully covered (or fully covered but with a disconnected set of active sensors) when the deadline expires decide to remain active for the considered round and transmit an activity message announcing it. There are four variants in our approach, depending on whether or not withdrawal and retreat messages are transmitted. Covered nodes decide to sleep, with or without transmitting a withdrawal message to inform neighbors about the status. After hearing from more neighbors, active sensors may observe that they became covered and may decide to alter their original decision and transmit a retreat message. Our simulations show a largely reduced message overhead while preserving coverage quality for the ideal MAC/physical layer. Compared to an existing method (based on hello messages followed by retreat ones and where excessive message loss contributed to excessive coverage holes), our approach has shown robustness in a model with collisions and/or a realistic physical layer.

International audience; In mobile ad hoc networks (MANETs), multi-hop mes- sage relay is the common way for nodes to communicate and participate in network operations, making routing a primary issue. The early research efforts on MANET rout- ing focused mainly on effectiveness and efficiency under the assumption of perfectly cooperative networks. However, MANETs may not be such a friendly environment for var- ious reasons. Routing protocols without any security fea- ture may put entire network at risk. As security becomes an increasingly popular topic, secure mobile ad hoc routing is attracting more and more research attention. In this paper, we conduct a survey on the state-of-art work in this field.

In ad hoc and sensor networks, the simplest and most widely used approach to broadcast is blind flooding, which lets every node in the network to rebroadcast a receiving packet to all its neighbors. This causes redundancy of broadcast packets and results in unnecessary collisions and bandwidth waste. To overcome these problems, a number of research groups have proposed more efficient broadcasting schemes with the goal of minimizing the retransmissions, while still guaranteeing that a broadcast packet is delivered to all the nodes in the network. Multipoint relay (MPR) and dominating set (DS) based broadcasting schemes can effectively improve the broadcasting efficiency while providing reliable broadcasting. The neighbor elimination scheme (NES) can improve any broadcasting protocol as an added feature. In this paper, we evaluate the performance of MPR (source dependent), MPR-DS (source-independent MPR, and DS based broadcasting protocols. We add NES to these three schemes separately and evaluate the performance of the resulted protocols. In our experiments, we use the random unit graphs to model the ad hoc and sensor networks. Each of the studied protocols has scenarios under which it has the best performance. Our experiments demonstrate that, without applying neighbor elimination scheme, MPR based protocol requires fewest retransmissions (however, each retransmission is with a longer message including list of forwarding neighbors). DS and MPR-DS schemes benefit significantly from the neighbor elimination technique in terms of the ratio of re-broadcasting nodes and the message redundancy on both transmitting and non-transmitting nodes, while MPR benefits marginally. After adding the neighbor elimination scheme, three new protocols behave almost equally well in terms of rebroadcast message counts. MPR-NES method is narrowly the best when the message that is broadcasted is a very large one, and the network is dynamic. MPR-DS-NES is narrowly the best when the broadcast message is not very large, and the network is stable (this method requires the third round of preprocessing HELLO messages). Overall, DS-NES appears to be the most robust, taking all measurements and parameters into acount, because it remains competitive under all scenarios, and has significant advantages over MPR-DS-NES in dynamic scenarios, and significant advantages over MPR-NES when the broadcast message is not very large, because MPR has overhead in packet lengths.

In this paper, we consider hybrid ad hoc networks, which are composed of two kinds of nodes, regular ones and nodes with additional capabilities. For example, multi-hop cellular and wireless Internet networks consist of static or mobile nodes, and fixed access points which provide an access to an infrastructure. In such a network, each node may use direct or multihop link to connect to an access point, allowing a greater mobility. The goal of this paper is to provide protocols for broadcasting data in such an environment, by taking advantage of the presence of access points to optimize the broadcast, either from an energy consumption or from a latency point of view. We thus consider known protocols for pure ad hoc networks and adapt them to hybrid ad hoc networks. These protocols are the Blind Flooding, the Neighbor Elimination Scheme, the Multipoint Relay protocol and the generalized Self-Pruning Rule (algorithm that elects some dominant nodes to relay messages). We give some experimental data for these modified protocols to compare them to their original version, so that we are able to emphasize the gain obtained thanks to our proposed modifications.

International audience; In this paper, we focus on the construction of an efficient dominating set in ad hoc and sensor networks. A set of nodes is said to be dominating if each node is either itself dominant or neighbor of a dominant node. Application of such a set may for example be broadcasting, where the size of the set greatly impacts on energy consumption. Obtaining small sets is thus of prime importance. As a basis for our work, we use a heuristic given by Dai and Wu for constructing such a set. Their approach, in conjunction with the elimination of message overhead by Stojmenovic, has been recently shown to be an excellent compromise with respect to a wide range of metrics. In this paper, we present an enhanced definition to obtain smaller sets in the specific case where 2-hop information is considered. In our new definition, a node u is not dominant if there exists in its 2-hop neighborhood a connected set of nodes with higher priorities that covers u and its 1-hop neighbors. This new rule requires the same level of knowledge used by the original heuristic: only neighbors of nodes and neighbors of neighbors must be known to apply it. However, it takes advantage of some topological knowledge originally not taken into account, that may be used to deduce communication links between 1-hop and 2-hop neighbors. We provide the proof that the new set is a subset of the one obtained with the original heuristic. We also give the proof that our set is always dominating for any graph, and connected for any connected graph. Two versions are considered: with topological and positional information, which differ in whether or not nodes are aware of links between their 2-hop neighbors that are not 1-hop neighbors. An algorithm for locally applying the concept at each node is described. We finally provide experimental data that demonstrates the superiority of our rule in obtaining smaller dominating sets. A centralized algorithm is used as a benchmark in the comparisons. The overhead of the size of connected dominating set is reduced by about 15% with the topological variant and by about 30% with the positional variant of our new definition.

We give an extended review of existing energy efficient broadcasting protocols for ad hoc networks.

We investigate minimum energy broadcasting problem where mobile nodes have the capability to adjust their transmission range. The power consumption for two nodes at distance r is r/sup /spl alpha// + c, where /spl alpha/ /spl ges/ 2 and c is a constant that includes signal processing and minimal reception power. We show that, for c > 0 (which is realistic assumption), it is not optimal to minimize transmission range. Furthermore, we demonstrate that there exists an optimal radius, computed with a hexagonal tiling of the network area that minimizes the power consumption. For /spl alpha/ > 2 and c > 0, the optimal radius is r = /spl alpha//spl radic/(2c//spl alpha/-2), which is derived theoretically, and confirmed experimentally. We propose also a localized broadcast algorithm TR-LBOP that takes this optimal radius into account. This protocol is experimentally shown to be efficient compared to existing localized protocol LBOP and globalized BIP protocol. Most importantly, TR-LBOP is shown to have limited energy overhead with respect to BIP for all network densities, which is not the case with LBOP whose overhead explodes for higher densities.

International audience; Cloud computing security is a broad research domain with a large number of concerns, ranging from protecting hardware and platform technologies to protecting clouds data and resource access (through different end- user devices). Although the advantages of cloud computing are tremendous, the security and privacy concerns of cloud computing have always been the focus of numerous cloud customers and impediment to its widespread adaptation by businesses and organizations. The paper presents a systematic literature review in the field of cloud computing with a focus on risk assessment. This would help future research and cloud users/business organizations to have an overview of the risk factors in a cloud environment. And to proactively map their indigenous needs with this technology.

International audience; Distributed operating systems simplify building and executing applications on large-scale infrastructures, such as clusters, grids and clouds. These systems operate in a constantly changing environment characterized by varying application needs and varying physical infrastructure capabilities. To handle the diversity and dynamism of both the applications and the underlying infrastructures, the distributed Operating System (OS) should continually adapt to its changing environment. Two challenges arise in this context: how to design the distributed OS in order to facilitate dynamic adaptation, and how to ensure that OS-level adaptation does not conflict with application-level adaptation. This paper proposes to address these challenges by: (1) building the distributed OS as an assembly of adaptable services following the service-oriented architecture; and (2) using a common multi-level adaptation framework to adapt both the OS and the application layers in a coordinated way. Moreover, the paper presents experimental evidence of the usefulness of this approach in adapting the distributed shared memory service of a specific distributed OS.

International audience; In this article, we compare two self-organization and hierarchical routing protocols for ad hoc networks. These two protocols apply the reverse approach from the classical one, since they use a reactive routing protocol inside the clusters and a proactive routing protocol between the clusters. We compare them regarding the cluster organization they provide and the routing that is then performed over it. This study gives an idea of the impact of the use of recursiveness and of the partition of the DHT on self-organization and hierarchical routing in ad hoc networks.