Search

Several sensor network applications based on data diffusion and data management can determine the communication transfer rate between two sensors beforehand. In this framework, we consider the problem of energy efficient communication among nodes of a wireless sensor network and propose an application-driven approach that minimizes radio activity intervals and prolongs network lifetime. On the basis of possible communication delays we estimate packet arrival intervals at any intermediate hop of a fixed-rate data path. We study a generic strategy of radio activity minimization wherein each node maintains the radio switched on just in the expected packet arrival intervals and guarantees low communication latency. We define a probabilistic model that allows the evaluation of the packet loss probability that results from the reduced radio activity. The model can be used to optimally choose the radio activity intervals that achieve a certain probability of successful packet delivery for a specific radio activity strategy. Relying on the probabilistic model we also define a cost model that estimates the energy consumption of the proposed strategies, under specific settings. We propose three specific strategies and numerically evaluate the associated costs. We finally validate our work with a simulation made with TOSSIM (the Berkeley motes' simulator). The simulation results confirm the validity of the approach and the accuracy of the analytic models.

Underwater communications through acoustic modems rise several networking challenges for the Underwater Acoustic Sensor Networks (UASN). In particular, opportunistic routing is a novel but promising technique that can remarkably increase the reliability of the UASN, but its use in this context requires studies on the nature of mobility in UASN. Our goal is to study a real-world mobility dataset obtained from the Argo project. In particular, we observe the mobility of 51 free-drifting floats deployed on the Mediterranean Sea for approximately one year and we analyze some important properties of the underwater network we built. Specifically, we analyze the contact-time, inter- contact time as well density and network degree while varying the connectivity degree of the whole dataset. We then consider three known routing algorithms, namely Epidemic, PROPHET and Direct Delivery, with the goal of measuring their performance in real conditions for USAN. We finally discuss the opportunities arising from the adoption of opportunistic routing in UASN showing that, even in a very sparse and strongly disconnected network, it is still possible to build a limited but working networking framework.

Mobile Social Networks represent a convergence between mobile communications and service-oriented paradigms, which are supported by the large availability and heterogeneity of resources and services offered by recent mobile devices. In particular, the service-oriented nature of MSN is in the capability of sharing resources and services among devices that lie in proximity and that opportunis- tically interact. Service discovery is thus of primary importance to sustain the most intimate mechanisms of MSN. Despite of their centrality, studies on service discovery in MSN are still in their youth. We contribute to frame the results achieved so far and to identify some possible perspectives of the research in this field, by giving a transversal review of the scientific outcomes in the different steps of service discovery, namely advertisement, query, selection and access.

The distributed gradient protocol is a common building block to perform several tasks in a wireless sensor network. The gradient calculates the minimum hop-distances between each sensor and a specified set of anchor sensors. This calculation is performed using a distributed greedy forwarding of messages in the network. Several virtual localization protocols use gradients to compute the virtual coordinates of the sensors. The quality of these coordinate systems depends on the relation between the value of the gradient and the real geographic distances between sensors. In this paper a formal proof of such relation is provided in the case of dense sensor networks with homogeneous sensor communication range r. The minimum-hop distances between a sensor and an achor is bounded to be in a range defined by two geographic distances. The size of this range decreases with increasing density of the network and it is equal to the maximum resolution (the communication range r) when the density is high enough.

Underwater Sensor Networks (USN) are used for harsh oceanographic missions where human operation is dangerous or impossible. Localization is essential for USNs. It is required for data tagging, node tracking and position-based routing algorithms. Localization is challenging because Global Positioning System(GPS) is not available in underwater; at the same time, existing GPS-less schemes based on fixed landmarks have high communication cost. Such cost is critical in Mobile Underwater Sensor Networks (MUSN), since sensor nodes drift with the ocean currents, thus requiring continuous refresh. In this paper, we propose a multi-stage localization scheme using mobile beacons. The beacons periodically ascent and descent in the water column. When they resurface, they receive new GPS coordinates. Then, they dive to the level of the underwater sensors to advertise these coordinates. In turn, localized sensors become proxy beacons and propagate their own coordinates, etc. This iterative, multi-stage localization is the major innovation of this paper. The goal is to localize the nodes with the smallest number of beacons using proxies instead, yet achieving an adequate accuracy. The major benefit is the reduction in operating costs. Mobility is a critical factor in determining performance. In this paper, performance (i.e., the percentage of localized nodes during a cycle, accuracy, delay and communication cost) is tested in a simulation scenario based on a realistic mobility model. The "Meandering Current Mobility with Surface Effect" (MCM-SE) model - a composite model combining surface and subsurface currents.

We consider the problem of routing with guaranteed de- livery in wireless sensor networks where physical locations of the sensors are not known. We propose a naming proto- col which defines a 2-dimensional coordinate system and a routing protocol (Ibrid) which ensures guaranteed delivery of packets. We show by means of simulation that in realis- tic settings where the network includes voids and obstacles, Ibrid finds routess hortest than those obtained with existing geographic routing algorithms over physical coordinates.

System-level diagnosis aims at the identification of faulty units in a system by the analysis of the system syndrome, that is, the outcomes of a set of interunit tests. For any given syndrome, it is possible to produce a correct (although possibly incomplete) diagnosis of the system if the number of faults is below a syndrome-dependent bound and the degree of diagnosis completeness, that is, the number of correctly diagnosed units, is also dependent on the actual syndrome sigma. The worst-case diagnosis completeness is a syndrome-independent bound that represents the minimum number of units that the diagnosis algorithm correctly diagnoses for any syndrome. This paper provides a lower bound to the worst-case diagnosis completeness for regular graphs for which vertex- isoperimetric inequalities are known and it shows how this bound can be applied to toroidal grids. These results prove a previous hypothesis about the influence of two topological parameters of the diagnostic graph, that is, the bisection width and the diameter, on the degree of diagnosis completeness.

A novel routing protocol for wireless, mobile ad hoc networks is presented. This protocol incorporates features that enhance routing reliability, defined as the ability to provide almost 100% packet delivery rate. The protocol is based on a virtual structure, unrelated to the physical network topology, where mobile nodes are connected by virtual links and are responsible for keeping physical routes to their neighbors in the virtual structure. Routes between pairs of mobiles are set up by using information to translate virtual paths discovered in the virtual structure. Route discovery and maintenance phases of the protocol are based on unicast messages travelling across virtual paths, with sporadic use of flooding protocol. Most flooding is executed in the background using low priority messages. The routing protocol has been evaluated and compared with the Dynamic Source Routing protocol and with the Zone Routing Protocol by means of simulation.

Wireless ad hoc networks are generally characterised by random node locations and multi-hop routes. A quantitative knowledge of the relation between hop count and Euclidean distance could provide a better understanding of important network parameters such as end-to-end delay, power consumption along the route, and node localisation. In this paper, we present an analytic approach to capture the statistics on hop count for a given source-to-destination Euclidean distance in a greedy routing approach. We also show that, for a given hop count, the bounds on Euclidean distance can be computed from the distribution characteristics of per-hop progress.

This paper defines a novel semantic for multicast in vehicular ad hoc networks (VANETs) and it defines a middleware, the Localized Vehicular Multicast Middleware (LVMM) that enables minimum cost, source-based multicast communications in VANETs. The middleware provides support to find vehicles suitable to sustain multicast communications, to maintain multicast groups, and to execute a multicast routing protocol, the Vehicular Multicast Routing Protocol (VMRP), that delivers messages of multicast applications to all the recipients utilizing a loop-free, minimum cost path from each source to all the recipients. LVMM does not require a vehicle to know all other members: only knowledge of directly reachable nodes is required to perform the source-based routing.

The problem of fault diagnosis in grid-connected systems is considered. A diagnosis algorithm, called DAGS and based on the PMC model, is presented. DAGS provides a diagnosis which is shown to be correct, although possibly incomplete, if the cardinality of the actual fault set is below a bound T_sigma dependent of the actual syndrome sigma. A syndrome independent bound T is also derived by a worst-case analysis covering the cases of triangular, square, hexagonal and octagonal grids. T is shown to be Θ(n^2/3), where n is the size of the system, for all the grids considered.

We present a new diagnosis algorithm (NDA) for regular interconnected structures. The diagnosis algorithm has time complexity O(kn) when applied to k-regular systems of n units. It provides a correct diagnosis, although incomplete. The diagnosis is correct if the number of faulty units is not above a specified bound asserted by the algorithm itself. The correctness and completeness of NDA is studied through simulations on toroidal grids and hypercubes. Simulation results show that NDA provides a correct diagnosis even when the number of faults is very high (near half of the system size). The comparison between algorithm NDA and other diagnostic algorithms shows that NDA provides a better diagnosis, i.e., it has a higher degree of completeness than other diagnostic algorithms.

This paper introduces an efficient diagnosis algorithm for regular structures (EDARS). The algorithm provides a diagnosis which is correct, but possibly incomplete, if the cardinality of the actual fault set is below a 'syndrome-dependent bound', asserted by the algorithm itself. The time complexity of EDARS is O(nt) when executed on t-regular structures of size n. The correctness and the degree of completeness of the diagnosis provided by EDARS, were evaluated by means of simulation. Grids, hypercubes and Cube-Connected Cycles (CCC) structures were considered. Simulation results with grid structures showed a strong influence of structure degree over diagnosis performance. Furthermore, comparisons of simulation results obtained with grids, hypercubes and CCCs of same size and degree, showed that diameter and bisection width also appear to influence the performance of EDARS, particularly with respect to diagnosis completeness.

A novel approach aimed at evaluating the diagnosability of regular systems under the PMC model is introduced. The diagnosability is defined as the ability to provide a correct diagnosis, although possibly incomplete. This concept is somehow intermediate between one-step diagnosability and sequential diagnosability. A lower bound to diagnosability is determined by lower bounding the minimum of a ''syndrome-dependent'' bound $t_\sigma$ over the set of all the admissible syndromes. In turn, $t_\sigma$ is determined by evaluating the cardinality of the smal\-lest consistent fault set containing an aggregate of maximum cardinality. The new approach, which applies to any regular system, relies on the ''edge-isoperimetric inequalities'' of connected components of units declaring each other non-faulty. This approach has been used to derive tight lower bounds to the diagnosability of toroidal grids and hypercubes, which improve the existing bounds for the same structures.

An abstract is not available.

We present a methodology, based on the theory system-level diagnosis, to execute the wafer,scale test of fCs. With the new methodology, ail fe's on the wafer undergo an intensive test before they are cut, bonded and packaged. The tests are executed by means of comparisons of adjacent ICs, and the faulty ICs are identified by a diagnosis algorithm which provides correct and almost complete identification of good ICs under realistic fault situations. The paper considers different implementations comparison logic and discusses their consistency with the standard diagnostic models.

An efficient diagnosis algorithm for grid-connected systems is presented and evaluated The algorithm provides correct, but possibly incomplete, diagnosis if the number faults occurring in the system does not exceed a bound T_ ? returned by the algorithm itself along with diagnosis. The diagnosis may be validated by probing a very small number of units. The performance of the algorithm when applied to grids of different sizes and degrees was evaluated by means of simulation. The results of the simulation experiments displayed a trade-off between the performance of the algarithm and the degree, hence the cost, of the interconnection structure.

Popular ad hoc routing protocols such as DSDV and AODV use “predecessor” based forwarding, namely, the packet is forwarded to the “predecessor” that advertised the shortest path to destination during the last update. However, if the “predecessor” moves, the routing table entry becomes invalid and “predecessor” based forwarding fails! To overcome the stale forward table problem, in this paper we propose a novel packet forwarding scheme called “direction” forwarding (DFR). When an update is received, a node records the “geographical direction” to where the update came from. When “predecessor” forwarding fails, the packet is forwarded to the “most promising” neighbor in the recorded direction. If the network is sufficiently dense and the routing algorithm includes periodic refresh from destination, direction forwarding will recover from most “predecessor” failures due to motion. We evaluate DFR in a LANMAR routing scenario where the direction to each Landmark is periodically refreshed. Through simulation we show that DFR considerably enhances LANMAR performance in large, mobile network scenarios.

In this paper, we present a novel packet forwarding scheme for wireless ad hoc networks --- “Direction” Forwarding (DFR). Popular routing protocols such as DSDV and AODV use “predecessor” based forwarding, namely, the packet is forwarded to the predecessor on the shortest path from the destination, as advertised during the last update. Predecessor forwarding may fail in large scale networks where the routing update rate must be reduced by the need to maintain link O/H below reasonable levels. However, if nodes are mobile, routing table entries may become “stale” very rapidly. DFR is designed to overcome the “stale” routing table entry problem. When the routing update arrives, the node remembers not only the predecessor delivering the update, but also the update “direction” of arrival. When a packet must be forwarded to destination, it is first forwarded to the node ID found in the routing table. If the node has moved and ID forwarding fails, the packet is “direction” forwarded to the “most promising” node in the indicated direction. At first glance, DFR seems to combine the features of table based routing and geo-routing. However, direction forwarding differs from geo-routing in that the direction is learned from the routing updates, instead of being computed from the destination coordinates. Thus, DFR does not require destination coordinates, a global coordinate system, or a Geo Location Server. In the paper we show the application of DFR to a scalable routing scheme, LANMAR. Through simulation experiments we show that DFR substantially enhances LANMAR performance in large, mobile network scenarios.

In this paper we consider the problem of constructing a coordinate system in a sensor network where location information is not available. To this purpose we introduce the Virtual Coordinate assignment protocol (VCap) which defines a virtual coordinate system based on hop distances. As compared to other approaches, VCap is simple and have very little requirements in terms of communication and memory overheads. We compare by simulations the performances of greedy routing using our virtual coordinate system with the one using the physical coordinates. Results show that the virtual coordinate system can be used to efficently support geographic routing.

The problem of identifying the faulty units in regularly interconnected systems is addressed. The diagnosis is based on mutual tests of units, which are adjacent in the "system graph" describing the interconnection structure. This paper evaluates an algorithm named EDARS (Efficient Diagnosis Algorithm for Regular Structures). The diagnosis provided by this algorithm is provably correct and almost complete with high probability. Diagnosis correctness is guaranteed if the cardinality of the actual fault set is below a "syndrome-dependent bound," asserted by the algorithm itself along with the diagnosis. Evaluation of EDARS relies upon extensive simulation which covered grids, hypercubes, and cube-connected cycles (CCC). Simulation experiments showed that the degree of the system graph has a strong impact over diagnosis completeness and affects the "syndrome-dependent bound," ensuring correctness. Furthermore, a comparative analysis of the performance of EDARS, with hypercubes and CCCs on one side and grids of the same size and degree on the other side, showed that diameter and bisection width of the system graph also influence the diagnosis correctness and completeness.