Remotely deployed sensor networks are vulnerable to both physical and electronic security breaches. The sensor nodes, once compromised, can send erroneous data to the base station, thereby possibly compromising network effectiveness. We assume that sensor nodes are organized in a hierarchy and use an offline neural network-based learning technique to predict the data sensed at any node given the data reported by its siblings in the hierarchy. This allows us to detect malicious nodes even when the siblings are not sensing data from the same distribution. The speed of detection of compromised nodes, however, critically depends on the mechanism used to update the reputation of the sensor nodes over time. We compare and contrast the relative strengths of a statistically grounded scheme and a reinforcement learning-based scheme both for their robustness to noise and responsiveness to change in sensor behavior. We first extend an existing mechanism to improve detection capability for smaller errors. Next we analyze the influence of different discount factors, including unweighted, exponential and linear discounts, on the tradeoff between responsiveness and robustness. We both develop a theoretical analysis to understand the tradeoff and perform experimental verification of our predictions by varying the patterns in sensed data.
April 29, 2010
An Optimal Rotation Distance Set
A rotation in a binary tree is a local restructuring that changes the tree into another and preserves the inorder sequence. The rotation distance between two binary trees is the minimum number of rotations needed to transform one into another. However, a polynomial-time algorithm for computing rotation distances between any two binary trees has still not been found. Lucas (The Computer Journal, 47, 259–269, 2004) recently presented an O(n2)-time algorithm for finding the exact rotation distance between two binary trees that are of a restricted form (each node has at most one child in the source tree and there is at most one zig-zag pair in the destination tree), where n is the number of nodes in each binary tree. In this paper, by using the coding technique of left weight sequences, which was proposed by Pallo (The Computer Journal, 9, 171–175, 1986), we find another restricted set of binary trees in which any two of them can be transformed with the exact rotation distance. Our algorithm can be performed in linear time for finding the rotation distance between any two trees in the restricted set. Moreover, the actual sequence of transforming rotations can also be built.
Plant Image Retrieval Using Color, Shape and Texture Features
We present a content-based image retrieval system for plant image retrieval, intended especially for the house plant identification problem. A plant image consists of a collection of overlapping leaves and possibly flowers, which makes the problem challenging. We studied the suitability of various well-known color, shape and texture features for this problem, as well as introducing some new texture matching techniques and shape features. Feature extraction is applied after segmenting the plant region from the background using the max-flow min-cut technique. Results on a database of 380 plant images belonging to 78 different types of plants show promise of the proposed new techniques and the overall system: in 55% of the queries, the correct plant image is retrieved among the top-15 results. Furthermore, the accuracy goes up to 73% when a 132-image subset of well-segmented plant images are considered.
Controlled Multi-Path Routing in Sensor Networks Using Bezier Curves
We address the problem of extending the lifetime of wireless sensor networks using multi-path routing based on a family of flexible routes with soft quality of service guarantees in terms of the packets’ delivery latency. We introduce a methodology based on Bezier curves as guiding trajectories in the routing process and we address the balancing of the workload among neighboring nodes. An added benefit, due to the flexibility of the Bezier curves, is that the shapes of the (alternate) routes can be constructed in a manner that prolongs the lifetime of the nodes in the vicinity of a given source/sink. We describe a forwarding algorithm, where the relay nodes can determine locally the Bezier curve they belong to and which requires only the transmission of the so-called control points that determine the shape of one (boundary) curve. We also show how our forwarding algorithm can be adapted to incorporate the sleep-schedule of the individual nodes, thereby further prolonging the networks’ lifetime. Our simulations demonstrate that the Bezier-based routing algorithms can yield significant improvements in the networks’ overall lifetime.
A Hybrid Adaptive Protocol for Reliable Data Delivery in WSNs with Multiple Mobile Sinks
In this paper, we deal with reliable and energy-efficient data delivery in sparse wireless sensor networks (WSNs) with multiple mobile sinks (MSs). This is a critical task, especially when MSs move randomly, as interactions with sensor nodes are unpredictable, typically of short duration and affected by message losses. In addition, multiple MSs can be simultaneously present in the sensor contact area making the minimum energy data delivery a complex optimization problem. To solve the above issues, in this paper we propose a novel protocol that efficiently combines erasure coding with an Automatic Repeat reQuest (ARQ) scheme. The key features of the proposed protocol are as follows: (i) the use of redundancy to cope efficiently with message losses in the multicast environment and (ii) the ability of adapting the level of redundancy based on feedbacks sent back by MSs through acks. We observed by simulation that our protocol outperforms an alternative protocol that relies only on an ARQ scheme, even when there is a single MS. We also validated our simulation results through a set of experimental measurements based on real sensor nodes. Our results show that the adoption of encoding techniques increases the lifetime of the sensor in the range (40–55%) compared with standard simple ARQ approaches when applied to WSNs with MSs.
Efficient Query-Based Data Collection for Mobile Wireless Monitoring Applications
Considering sensor nodes deployed densely and uniformly a mobile sink moving through the sensing field queries a specific area of interest for monitoring information. The Query packet, injected by the mobile sink, is routed to the specific area and the corresponding Response packet is expected to return via multi-hop communication. In this paper, we analyze such a network model to address the problem of efficient data collection for mobile wireless monitoring applications. We first propose a meeting position-aware routing (MPAR) protocol for routing the Response packet efficiently and then propose an efficient query-based data collection scheme (QBDCS) for mobile wireless monitoring applications based on the MPAR. In order to minimize the energy consumption and packet delivery latency, the QBDCS chooses the optimal query time of injecting the Query packet and tailors the routing mechanism for sensor nodes forwarding packets. Simulation study has verified the analysis and demonstrated that the QBDCS can significantly reduce the energy consumption and end to end delivery latency.
Decentralized Data and Information Systems: Theory and Practice
This special issue is devoted to papers that have emerged from the ALADDIN (Autonomous Learning Agents for Decentralized Data and Information Networks) project (http://www.aladdinproject.org/). ALADDIN is concerned with developing techniques, methods and architectures for modelling, designing and building decentralized systems that can bring together information from a variety of heterogeneous sources in order to take informed actions in a timely manner. To do this, we have taken a total systems view on information and knowledge fusion and considered the feedback that exists between sensing, decision making and acting in such systems. Moreover, we have tackled these objectives in environments in which: control is distributed; uncertainty, ambiguity, imprecision and bias are endemic; multiple stakeholders with different aims and objectives are present; and resources are limited and continually vary during the systems operation.
The Critical Grid Size and Transmission Radius for Local-Minimum-Free Grid Routing in Wireless Ad Hoc and Sensor Networks
In grid routing, the plane is tessellated into equal-sized square cells. Two cells are called neighbor cells if they share a common edge, and two nodes are called routing neighbors if they are in neighbor cells and within each other’s transmission range. If communication parties are in the same cell, packets can be transmitted directly; otherwise, packets are forwarded to routing neighbors that are in cells closer to destination cells. As a greedy strategy, grid routing suffers the existence of local minima at which no neighbor nodes exist for relaying packets. To guarantee deliverability, in this paper, we investigate two vital parameters of grid routing, called the grid size and the transmission radius. Assume that nodes are represented by a Poisson point process with rate n over a unit-area square, and let l denote the grid size and r the transmission radius. First, we show that if
for some constant β and r = 5l, then β = 1 is the threshold for deliverability. In other words, there almost surely do not exist local minima if β > 1 and there almost surely exist local minima if β < 1. Next, for any given β > 1, we give sufficient and necessary conditions to determine the critical transmission radius (CTR) for deliverability. Then, we show that as β 1.092, the CTR is the minimum over all β > 1. Simulation results are given to validate this theoretical work.
Dynamic Multipath Allocation in Ad Hoc Networks
Ad hoc networks are characterized by fast dynamic changes in the topology of the network. A known technique to improve quality of service (QoS) is to use multipath routing, where packets (voice/video/…) from a source to a destination travel in two or more maximal disjoint paths. We observe that the need to find a set of maximal disjoint paths can be relaxed by finding a set of paths S wherein only bottlenecked links are bypassed. In the proposed model, we assume that there is only one edge along a path in S that is a bottleneck and show that by selecting random paths in S the probability that bottlenecked edges get bypassed is high. We implemented this idea in the MRA system, which is a highly accurate visual ad hoc simulator currently supporting two routing protocols, AODV and MRA. We have extended the MRA protocol to use multipath routing by maintaining a set of random routing trees from which random paths can be easily selected. Random paths are allocated/released by threshold rules monitoring the session quality. The experiments show the following: (i) session QoS is significantly improved; (ii) the fact that many sessions use multiple paths in parallel does not depredate overall performances and (iii) the overhead in maintaining multipath in the MRA algorithm is negligible.1
Decentralized Coordination in RoboCup Rescue
Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads and extinguish the fires which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximize the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralized fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long-range communication devices. Against this background, we provide a novel decentralized solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a coalition formation with spatial and temporal constraints (CFST) problem where agents form coalitions to complete tasks, each with different demands. To design a decentralized algorithm for CFST, we formulate it as a distributed constraint optimization problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralized message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralized algorithms used for this problem.