Ad-hoc, Mobile, and Wireless Networks

Geographic routing is one of the most widely-accepted techniques to route information in wireless sensor networks. The main novelty is that the current node routes the packet to a neighbor which is located closer to the destination than itself. This process is called greedy routing. When the packet reaches a node that has no neighbors located closer to the destination than itself (a.k.a. local minimum) a recovery strategy is used to get to nodes that can again resume greedy routing. However, recent studies have proven that geographic routing may be ineffective in real deployments where location estimation systems introduce location errors. In this paper, we analyze in detail the problems induced by location errors in greedy routing and propose an Effective Greedy Routing supporting Location Errors (EGLE). Our simulation results show that EGLE is able to outperform existing solutions. It achieves nearly a 100% packet delivery ratio with very little additional overhead.

In mobile wireless sensor networks, flows sent from data collecting sensors to a sink could traverse inefficient resource expensive paths. Such paths may have several negative effects such as devices battery depletion that may cause the network to be disconnected and packets to experience arbitrary delays. This is particularly problematic in event-based sensor networks (deployed in disaster recovery missions) where flows are of great importance. In this paper, we use node mobility to improve energy consumption of computed paths. Mobility is a two-sword edge, however. Moving a node may render the network disconnected and useless. We propose CoMNet (Connectivity preservation Mobile routing protocol for actuator and sensor NETworks), a localized mechanism that modifies the network topology to support resource efficient transmissions. To the best of our knowledge, CoMNet is the first georouting algorithm which considers controlled mobility to improve routing energy consumption while ensuring network connectivity. CoMNet is based on (i) a cost to progress metric which optimizes both sending and moving costs, (ii) the use of a connected dominating set to maintain network connectivity. CoMNet is general enough to be applied to various networks (actuator, sensor). Our simulations show that CoMNet guarantees network connectivity and is effective in achieving high delivery rates and substantial energy savings compared to traditional approaches.

Wireless mesh sensor networks (WMSNs) have recently gained a lot of interest due to their communication capability to support various applications with different Quality of Service (QoS) requirements. The most challenging issue is providing a tradeoff between the resource efficiency and the multi-constrained QoS support. For this purpose, we propose a cross-layer algorithm JSAR (Joint duty cycle Scheduling, resource Allocation and multi-constrained QoS Routing algorithm) for WMSNs based on multi-channel multi-time slot Medium Access Control (MAC). To the best of our knowledge, JSAR is the first algorithm that simultaneously combines a duty cycle scheduling scheme for energy saving, a resource allocation scheme for efficient use of frequency channels and time slots, and an heuristic for multi-constrained routing protocol. The performance of JSAR has been evaluated, showing that it is suitable for on-line implementation.

Wireless Mesh Networks (WMN) are easy-to-deploy, low cost solutions for providing networking and internet services in environments with no network infrastructure, e.g., disaster areas and battlefields. Since electric power is not readily available in such environments battery-powered mesh routers, operating in an energy efficient manner, are required. To the best of our knowledge, the impact of energy efficient solutions, e.g., involving duty-cycling, on WMN intrusion detection systems, which require continuous monitoring, remains an open research problem. In this paper we propose that carefully chosen monitoring mesh nodes ensure continuous and complete detection coverage, while allowing non-monitoring mesh nodes to save energy through duty-cycling. We formulate the monitoring node selection problem as an optimization problem and propose distributed and centralized solutions for it, with different tradeoffs. Through extensive simulations and a proof-of-concept hardware/software implementation we demonstrate that our solutions extend the WMN lifetime by 8%, while ensuring, at the minimum, a 97% intrusion detection rate.

Topology control in wireless sensor networks is an important issue for scalability and energy efficiency. It is often based on graph reduction performed through the use of Gabriel Graph or Relative Neighborhood Graph. This graph reduction is usually based on geometric values. In this paper we tackle the problem of possible connectivity loss in the reduced graph by applying a battery level based reduction graph. Experiments are conducted to evaluate our proposition. Results are compared with RNG reduction which takes into account only the strength of the received signal (RSSI). Results show that our algorithm maintains network connectivity longer than solutions from the literature and balances the energy consumption over nodes.

Choosing the appropriate network size to guarantee connectivity in a WSN deployment is a challenging and important question. Classic techniques to answer this question are not up to the challenge because they rarely consider realistic radio models. This work proposes a methodology to evaluate the performance of network size estimation techniques in terms of connectivity efficiency under realistic radio scenarios. This study is carried out using Atarraya, a simulation tool for wireless sensor networks, considering three classical estimation techniques and a radio model based on the specifications of the ZigBee radio from off-the-shelf WaspMote nodes from Libelium. The results show that the hexagon-based optimal grid technique provides the most efficient estimate, offering a high connectivity level with the lowest estimated number of nodes for a given proximity radius parameter, followed by the circle packing and the triangle-based grid distribution. In addition, the results show that packet error rates of 10% could still produce highly connected topologies.

Topology control is one of the main techniques that can be used to decrease energy expenditure and/or interference in wireless sensor networks. Less attention, however, has been devoted to algorithms that address energy and interference efficiency together. In this paper, we describe a localized topology control algorithm called TCO which is very efficient in terms of interference while minimizing energy efficiency. In order to evaluate TCO in terms of interference and compare it with other algorithms, we defined a new metric called PICS (Path Interference Cost based on Sender) Spanning Factor. According to this metric, in our experiments TCO outperformed all related localized topology control algorithms and its performance was extremely close to the performance of a centralized algorithm which is optimal according to the PICS spanning factor (a variation of ATASP based on PICS).

Interference imposes a major challenge for efficient data communication in wireless networks. Increased level of interference may increase number of collisions, energy consumption and latency due to retransmissions of the interfered data. Interference of a link is the number of nodes interfered while a pair of nodes are communicating over a bi-directional link. Approaches have been proposed to reduce interference by dropping links that create high interference. However, dropping links make a network more susceptible to node failure/departure–a frequent phenomenon in ad hoc networks. Thus dropping high interference links while keeping the network significantly connected is an important goal to achieve. In this paper, we formulate the problem of constructing minimum interference path preserving and fault tolerant wireless ad hoc networks and then provide algorithms, both centralized and distributed with local information, to solve the problem. Moreover, for the first time in literature, we conceive the concept of fault tolerant interference spanner and provide a local algorithm to construct such spanner of a communication graph.

Modern medium access control (MAC) protocols for wireless sensor networks (WSN) focus on energy-efficiency by switching a node’s radio on only when necessary. This intoduced rendezvous problem is gracefully handled by modern asynchronous approaches to WSN MAC’s, e.g. X-MAC, using strobed preambles. Nevertheless, most MAC layer ignore the possible benefits in energy consumption and end-to-end latency, supporting opportunistic routing can provide. In this paper we present PaderMAC, a strobed preamble MAC layer which supports cross-layer integration with an arbitrary opportunistic routing layer. This work specifies the PaderMAC protocol, explains its implementation using TinyOS and the MAC layer architecture (MLA), and presents the results of a testbed performance study. The study compares PaderMAC in conjunction with opportunistic routing to X-MAC in conjunction with path-based routing and shows how PaderMAC reduces the preamble length, better balances the load and further improves the end-to-end latency within the network.

Convergecast traffic pattern is predominant in current wireless sensor networks. Few packets are periodically sent toward the sink, but interesting events may generate a burst of packets for a limited period of time. Such burst may create congestion in the surrounding of the event and thus may result in packet loss. Several congestion avoidance solutions exist in the literature but they either involve a lot of control messages or complicate the deployment of sensor networks. We therefore propose a new approach, named CLOMAC, which can be integrated to existing preamble-based MAC protocols.CLOMAC reduces congestion by overhearing and passively creating alternative paths toward the destination. An evaluation by simulation will demonstrate the benefits of our contribution integrated with the B-MAC protocol.

Cooperative communication(CC) is a promising technique to combat fading in a wireless environment. In our previous work, we proposed Cooperative Preamble Sampling(CPS)-Medium Access Control(MAC) protocol which highlighted the benefits of using CC in Wireless Sensor Networks(WSN). Initially, CPS-MAC performance was evaluated in a 3-node network comprising a single source, partner, and destination node.

In this paper, we evaluate the performance of CPS-MAC in a multi-hop WSN configuration, where a large number of sensor nodes are deployed around a sink to create a data gathering network. All nodes generate traffic, which leads to channel contention, collisions, and idle listening. Results show that, under light traffic load, CPS-MAC performs on par with non-cooperative preamble sampling protocol and performs significantly higher as traffic load increases.

Position verification in wireless sensor networks (WSNs) is quite tricky in presence of attackers (malicious sensor nodes), who try to break the verification protocol by reporting their incorrect positions (locations) during the verification stage. In the literature of WSNs, most of the existing methods of position verification use trusted verifiers, which are in fact vulnerable to attacks by malicious nodes. They also depend on some distance estimation techniques, which are not accurate in noisy channels (mediums). In this article, we propose a secure position verification scheme for WSNs in noisy channels without relying on any trusted entities. Our verification scheme detects and filters out all malicious nodes from the network with a very high probability.

Exchanging items over mobile ad hoc network has been considered a challenging issue in recent years. To tackle this challenge, Verifiably Encrypted Signature (VES), which is employed as primitives when designing a large class of protocols such as certified email, fair exchange, and contract signing in wireless communication, provides a possible solution. However, the limited communication band, low computational ability and weak energy power restrict many existing verifiably encrypted signatures to be applied in ad hoc networks directly.

In this paper, we propose a compact verifiably encrypted signature scheme without random oracles based on the Computational Diffie- Hellman problem (CDH) with pairings. Comparing with prior works, our scheme achieves the following desired features: (1) Our verifiably encrypted signature has compact size (only two group elements) which is optimal for both Elgamal encryption and the Waters signature; (2) The scheme is more efficient in terms of signature generation and verification; (3) Our scheme also achieves provable security under a standard complexity assumption in the standard model. Apparently, our schemes are amongst the most efficient solutions in terms of both signature size and computation (optimal) because these features are important in wireless communication due to limited bandwidth and power. It can be surely applied flexibly to many secure exchange circumstances in mobile ad hoc network that solely allows the minimum cryptographic implementation.

Delay/Disruption tolerant networks (DTNs) are wireless ad-hoc networks, where end-to-end connectivity can not be guaranteed and communications rely on the assumption that the nodes are willing to store-carry-and-forward bundles in an opportunistic way. However, this assumption would be easily violated due to the selfish nodes which are unwilling to consume precious wireless resources by serving as bundle relays. Incentive issue in DTNs is extraordinarily challenging due to the unique network characteristics. To tackle this issue, in this paper, we propose MobiID, a novel user-centric and social-aware reputation based incentive scheme for DTNs. Different from conventional reputation schemes which rely on neighboring nodes to monitor the traffic and keep track of each other’s reputation, MobiID allows a node to manage its reputation evidence and show to demonstrate its reputation whenever necessary. We also define the concepts of self-check and community-check to speed up reputation establishment and allow nodes to form consensus views towards targets in the same community, which is based on our social metric by forwarding willingness. Performance simulation are given to demonstrate the security, effectiveness and efficiency of the proposed scheme.

Access control of message is required when certain selected vehicles are granted access to information, instead of all vehicles within communication range. In these situations an access policy (consisting of attributes as road situation and vehicle type) is built into the vehicle and messages are encrypted using these access policies. Only valid vehicles possessing these attributes are able to decrypt the message. Huang and Verma [16] had proposed such an access control framework. The scheme assumed that the road-side units (RSU) are not compromised and had a very restricted access structure. We propose a new access control structure which eliminates the drawbacks of their schemes, by providing access control in presence of compromised RSU. Our technique permits a more general boolean access structure. Communication is possible between two vehicles which are monitored by two RSU, which was not permitted in [16]. The costs are comparable to that of [16].

In directional sensor networks (DSNs), motility capability of a directional sensor node has a considerable impact on the coverage enhancement after the initial deployment. Since random deployment may result in overlapped field of views (FoVs) and occluded regions, directional sensor nodes with rotatable mechanisms may reorganize their working directions to improve the coverage. Our proposed algorithm, Attraction Forces of Uncovered Points (AFUP), aims at both minimizing the overlapped areas and facing the working directions towards the area of interest. AFUP is a distributed iterative algorithm and exploits the repel forces exerted by the uncovered points around the sensor nodes. The proposed algorithm improves the coverage by 18%-25% after the initial deployment. Moreover, AFUP outperforms three well-known area coverage enhancement methods [15] [19] [16] in terms of coverage improvement and overlap minimization. Our simulation results show that AFUP converges in five iterations in most of the scenarios.

Wireless sensors networks (WSNs) are deployed to collect huge amounts of data from the environment. This produced data has to be delivered through sensor’s wireless interface using multi-hop communications toward a sink. The position of the sink impacts the performance of the wireless sensor network regarding delay and energy consumption especially for relaying sensors. Optimizing the data gathering process in multi-hop wireless sensor networks is, therefore, a key issue. This article addresses the problem of data collection using mobile sinks in a WSN. We provide a framework that studies the trade-off between energy consumption and delay of data collection. This framework provides solutions that allow decision makers to optimally design the data collection plan in wireless sensor networks with mobile sinks.

Clustering is the most widely used performance solution for Mobile Ad Hoc Networks (MANETs), enabling their scalability for a large number of mobile nodes. The design of clustering schemes is quite complex, due to the highly dynamic topology of such networks. A numerous variety of clustering schemes have been proposed in literature, focusing different characteristics and objectives. In this work, a fully distributed and clusterhead-free clustering scheme is proposed, namely Smart and Balanced Clustering for MANETs (SALSA). The scheme introduces a new cluster balancing mechanism and a best clustering metric, aiming to provide a reduced maintenance overhead. SALSA was evaluated and compared with the Novel Stable and Low-maintenance Clustering Scheme (NSLOC), featuring topologies with up to 1000 nodes and velocities of 20 meters per second. Results confirmed the performance efficiency of the new scheme, providing stability and low maintenance overhead, even in the largest networks.

A WSN consists of numerous nodes gathering observations and combining these observations. Often, the timing of these observations is of importance when processing sensor data. Thus, a need for clock synchronization arises in WSNs. The CS-MNS algorithm has been proposed to fulfil this role. However, the core algorithm suffers from an initial divergence of clocks. This paper shows, through analysis, that introducing a bias factor in the CS-MNS update law significantly reduces this initial divergence. This is then further confirmed via simulation results, using Matlab, and actual testbed measurements in a testbed deploying motes running TinyOS 2.1. The results show that a designer, having some a-priori knowledge about clock characteristics, can choose a bias that allows the algorithm to speed up the convergence time and greately improve the overall protocol performance. The work also demonstrates that rigorous analysis can be helpful in designing protocols and predicting protocol behaviour, which is then verified through simulation and testbed measurements.

Video delivery in mobile ad-hoc networks (MANETs) is an exciting and challenging research field. In the past, most works addressing this issue have resorted to simulation due to the complexity of deploying QoS-enabled testbeds and retrieving video quality indexes in such environments. In this paper we introduce a methodology that allows testing the effectiveness of video codecs in ad-hoc networks. Our methodology relies on a well-defined video quality evaluation framework that is able to combine different video codecs and transmission environments. In particular, our evaluation procedures encompass a preliminary quality assessment, which relies on a point-to-point wireless channel, to establish the general behavior of a video codec under lossy channel conditions, along with tests in static and mobile ad-hoc network environments to determine the impact of factors such as congestion, hop count, and mobility on video quality. To validate our methodology we compare the H.264/AVC and the MPEG-4/ASP video codecs, showing that, in general, the former outperforms the later in terms of video quality, although, for very high loss rates, the differences between both become minimal. Additionally, we show that the number of hops between video transmitter and receiver is a decisive factor affecting performance in the presence of background traffic. Moreover, in mobile scenarios, we find that the impact of congestion and routing delay affects video streaming quality in different manners, being congestion mainly responsible for random losses, while routing delay is usually associated with large loss burst patterns.

In this paper we improve the well-known localization algorithms Lateration, Weighted Centroid Localization and Min-Max by using a improved distance estimation. It does not only consider the hop count between two nodes, but also the neighbor degree information. Simulation studies show the performance improvements.

In the vision of an IoT, trillions of tiny devices extend the Internet to the physical world and enable novel applications that have not been possible before. Such applications emerge out of the interaction of these devices with each other and with more powerful server-class computers on the Internet. Programming such applications is challenging due to the massively distributed nature of these networks combined with the challenges of embedded programming. In addition, resource constraints, device heterogeneity, and the integration with the Internet further complicate this situation. In this paper, we present a programming-in-the-large approach for resource-constraint devices such as wireless sensor nodes. Our approach is to model such applications using the Business Process Execution Language (BPEL), which is successfully and widely used in the Internet to model complete applications and business processes. However, BPEL and its associated technologies are too resource-demanding to be directly applied in resource-constraint environments. We therefore use the BPEL model as input to a code generation process that generates custom-tailored, lean code for different target platforms. The resulting code is fully standard-compliant and allows a seamless integration of IoT devices in enterprise IT environments. We present an exhaustive evaluation on real hardware showing the first-rate performance of the approach.

We address the problem of efficient gathering of data from a wireless network to a single sink node. Network’s communication and interference pattern are assumed to be captured by the unit-disk model. We consider the objective of minimizing the maximum latency (the time between release and delivery of a packet). We prove that the problem is NP-complete even when all packets are released from the same source node, or at the same time. To our knowledge, these are the first results about the wireless gathering problem in the plane. They can be seen as an extension of recent inapproximability results of Bonifaci et al., which hold in three dimensions.

In this article we address the problem of estimating a size of wireless sensor networks (WSNs). We restrict our attention to sensors with very limited storage capabilities. The problem arises when sensors have to quickly obtain approximate size of the network to use algorithms which require such information. Another application area is the problem of counting the number of different objects (e.g. people in public bus transportation) and use of such information to optimize the routes and frequency of buses. In this paper we present two-phase probabilistic algorithm based on order statistics and balls-bins model which effectively solves the presented problem.

The past decade has seen intensive research efforts on highly dynamic wireless and mobile networks (variously called delay-tolerant, disruptive-tolerant, challenged, opportunistic, etc) whose essential feature is a possible absence of end-to-end communication routes at any instant. As part of these efforts, a number of important concepts have been identified, based on new meanings of distance and connectivity. The main contribution of this paper is to review and integrate the collection of these concepts, formalisms, and related results found in the literature into a unified coherent framework, called TVG (for time-varying graphs).Besides this definitional work, we connect the various assumptions through a hierarchy of classes of TVGs defined with respect to properties with algorithmic significance in distributed computing. One of these classes coincides with the family of dynamic graphs over which population protocols are defined. We examine the (strict) inclusion hierarchy among the classes. The paper also provides a quick review of recent stochastic models for dynamic networks that aim to enable analytical investigation of the dynamics.