In recent years, blockchain technology has seen significant practical growth, yet it has not seen the same advancement from a theoretical perspective. This has led to the creation of numerous blockchains that are very different from each other and behave like isolated worlds. The research and development of theoretical frameworks, which define the fundamental properties of blockchains and define standards to follow for a more homogeneous implementation approach, have become extremely important. A theoretical model can help not only to design blockchains in the future but also to define a set of minimum requirements to be met for the creation of interoperability protocols between existing blockchains. In this work, we propose a theoretical model of blockchain that describes its most significant properties. Starting from our theoretical model, we present Smart Listeners , a blockchain interoperability protocol that finalises an inter-chain transaction with just two transactions: one on the source blockchain and one on the destination blockchain. The protocol is optimistic since changes on the source blockchain occur as if inter-chain transactions were successful. It is hybrid since it combines some properties of watchtowers and oracles in the off-chain components. We provide a benchmark on the performance of the proposed protocol in terms of latency and transactions per second. Finally, we define the minimum requirements that a blockchain should satisfy to allow the application of general-purpose interoperability protocols.

Programmable Matter (PM) has been widely investigated in recent years. It refers to some kind of substance with the ability to change its physical properties (e.g., shape or color) in a programmable way. In this paper, we refer to the SILBOT model, where the particles live and move on a triangular grid, are asynchronous in their computations and movements, and do not possess any direct means of communication (silent) or memory of past events (oblivious). Within SILBOT , we aim at studying Spanning problems, i.e., problems where the particles are required to suitably span all over the grid. We first address the Line Formation problem where the particles are required to end up in a configuration where they all lie on a line, i.e., they are aligned and connected. Secondly, we deal with the more general Scattering problem: starting from any initial configuration, we aim at reaching a final one where no particles occupy neighboring nodes. Furthermore, we investigate configurations where some nodes of the grid can be occupied by unmovable elements (i.e., obstacles) from both theoretical and experimental view points.

Robots with very weak capabilities placed on the vertices of a graph are required to move toward a common vertex from where they do not move anymore. The task is known as the Gathering problem and it has been extensively studied in the last decade with respect to both general graphs and specific topologies. Most of the challenges faced are due to possible isometries observable from the placement of the robots with respect to the underlying topology. Rings, Grids, and Complete graphs are just a few examples of very regular topologies where the placement of the robots and suitable movements are crucial for succeeding in Gathering. Here we are interested in understanding what can be done in Butterfly graphs where really many isometries are present and most importantly unavoidable by any movement. We propose a Gathering algorithm for the so-called leader configurations, i.e., those where the initial placement of the robots admits the detection (and election) of one robot as the leader. We introduce a non-trivial technique to elect the leader which is of its own interest. We also prove that the proposed Gathering algorithm is asymptotically optimal in terms of synchronous rounds required.

Abstract A distributed algorithm $${\mathcal {A}}$$ A solves the Point Convergence task if an arbitrarily large collection of entities, starting in an arbitrary configuration, move under the control of $${\mathcal {A}}$$ A to eventually form and thereafter maintain configurations in which the separation between all entities is arbitrarily small. This fundamental task in the standard $$\mathcal {OBLOT}$$ OBLOT model of autonomous mobile entities has been previously studied in a variety of settings, including full visibility, exact measurements (including distances and angles), and synchronous activation of entities. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm operating under these constraints that solves Point Convergence, for entities moving in two or three dimensional space, with any bounded degree of asynchrony. We also prove that under similar realistic constraints, but unbounded asynchrony, Point Convergence in the plane is not possible in general, contingent on the natural assumption that algorithms maintain the (visible) connectivity among entities present in the initial configuration. This variant, that we call Cohesive Convergence, serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling a long-standing question whether in the Euclidean plane synchronously scheduled entities are more powerful than asynchronously scheduled entities.

We consider Internet of Things (IoT) sensors deployed inside an area to be monitored. Drones can be used to collect the data from the sensors, but they are constrained in energy and storage. Therefore, all drones need to select a subset of sensors whose data are the most relevant to be acquired, modeled by assigning a reward. We present an optimization problem called Multiple-drone Data-collection Maximization Problem (MDMP) whose objective is to plan a set of drones' missions aimed at maximizing the overall reward from the collected data, and such that each individual drone's mission energy cost and total collected data are within the energy and storage limits, respectively. We optimally solve MDMP by proposing an Integer Linear Programming based algorithm. Since MDMP is NP-hard, we devise suboptimal algorithms for single- and multiple-drone scenarios. Finally, we thoroughly evaluate our algorithms on the basis of random generated synthetic data.

In the theoretical studies on distributed algorithms for swarm robotics, the complexity and capabilities of the robots are usually reduced to their minimum. Recently, the Moblot model has been introduced in order to deal with robots considered silent, anonymous, and oblivious but capable to aggregate into more complex structures, called molecules. We study the case where robots move along a graph based on a square lattice and we formally define the Molecular Pattern Formation (MPF) problem, where a specific configuration of robots assembled into molecules must be reached. As a preliminary general result, we provide a necessary condition for its solvability. Then, we actually show that dealing with molecules can resolve in some cases the symmetry breaking issue on grids where otherwise robots cannot. Finally, we introduce an interesting case study, representative of the MPF problem, in which the molecules can be formed by the set of the seven tetrominoes (aka Tetris blocks). We provide a complete characterization of this specific problem, providing a distributed algorithm able to form a molecular pattern whenever the necessary condition for the solvability of MPF is verified.

By Programmable Matter (PM) is usually meant a system of weak and self-organizing computational entities, called particles, which can be programmed via distributed algorithms to collectively achieve some global tasks. We consider the SILBOT model where particles are modeled as finite state automata, living and operating in the cells of a hexagonal grid. Particles are all identical, executing the same deterministic algorithm which is based on local observation of the surroundings, up to two hops. Particles are asynchronous, without any direct means of communication and disoriented but sharing a common handedness, i.e., chirality is assumed. Within such a basic model, we consider a foundational primitive for PM, that is Coating: a set of n particles must move so as to ensure the closed surrounding of an object occupying some connected cells of the grid. We present an optimal deterministic distributed algorithm - along with the correctness proof, that in Θ(n²) rounds solves the Coating problem, where a round concerns the minimal time window within which each particle is activated at least once.

Programmable Matter (PM) has been widely investigated in recent years. One reference model is certainly Amoebot, with its recent canonical version (DISC 2021). Along this line, with the aim of simplification and to address concurrency, the SILBOT model has been introduced (AAMAS 2020). Within SILBOT, we consider the Line formation primitive in which particles are required to end up in a configuration where they are all aligned and connected. We propose a simple and elegant distributed algorithm, optimal in terms of number of movements.

The Mutual Visibility is a well-known problem in the context of mobile robots. For a set of n robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robots are collinear. For robots moving on graphs, we consider the Geodesic Mutual Visibility (GMV) problem. Robots move along the edges of the graph, without collisions, so as to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means that there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside. We study this problem in the context of trees and (finite or infinite) square grids, for robots operating under the standard Look-Compute-Move model. In both scenarios, we provide resolution algorithms along with formal correctness proofs, highlighting the most relevant peculiarities arising within the different contexts, while optimizing the time complexity.

In this article, we study the orienteering aisle-graph single-access problem (OASP), a variant of the orienteering problem for a robot moving in a so-called single-access aisle graph, i.e., a graph consisting of a set of rows that can be accessed from one side only. Aisle graphs model, among others, vineyards or warehouses. Each aisle-graph vertex is associated with a reward that a robot obtains when it visits the vertex itself. As the energy of the robot is limited, only a subset of vertices can be visited with a fully charged battery. The objective is to maximize the total reward collected by the robot with a battery charge. We first propose an optimal algorithm that solves the OASP in O (m 2n 2) time for aisle graphs with a single access consisting of m rows, each with n vertices. With the goal of designing faster solutions, we propose four greedy suboptimal algorithms that run in at most O(mn\(m + n)) time. For two of them, we guarantee an approximation ratio of 1 2(1-1 e), where e is the base of the natural logarithm, on the total reward by exploiting the well-known submodularity property. Experimentally, we show that these algorithms collect more than 80% of the optimal reward.

We consider distributed computations, by identical autonomous mobile entities, that solve the Point Convergence problem: given an arbitrary initial configuration of entities, disposed in the Euclidean plane, move in such a way that, for all ε>0, a configuration is eventually reached and maintained in which the separation between all entities is at most ε. The problem has been previously studied in a variety of settings. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm that solves Point Convergence, provided the degree of asynchrony is bounded by some arbitrarily large but fixed constant. This provides a strong positive answer to a decade old open question posed by Katreniak. We also prove that, in an otherwise comparable setting, Point Convergence is impossible with unbounded asynchrony. This serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling at the same time a long-standing question whether in the Euclidean plane synchronous entities are more powerful than asynchronous ones.

In this paper, we study the Orienteering Aislegraphs Single-column Problem (OASP), which is a variant of the route planning problem for an entity/robot moving along a specific aisle-graph consisting of a set of rows connected via just one column at one endpoint of the rows. Such constrained aislegraph may model, for instance, a vineyard or warehouse, where each vertex is assigned with a reward that a robot gains when visiting it for accomplishing a task. As the robot is energy limited, it must visit a subset of vertices before going back to the depot for recharging, while maximizing the total reward gained. It is known that the OASP for constrained aisle-graphs composed by m rows of length n is polynomially solvable in O(m2n2) time, which can be prohibitive for graphs of large dimensions. With the goal of designing more time efficient solutions, we propose four algorithms that iteratively build the solution in a greedy manner. These solutions take at most O(mn (m + n)) time, thus improving the optimal solution by a factor of n. Experimentally, we show that these algorithms collect more than 80% of the optimum reward. For two of them, we also guarantee an approximation ratio of 1/2(1 - 1/e)on the reward function by exploiting the submodularity property, where e is the base of the natural logarithm.

In this paper, we consider the Constant-cost Orienteering Problem (COP) where a robot, constrained by a limited travel budget, aims at selecting a path with the largest reward in an aisle-graph. The aisle-graph consists of a set of loosely connected rows where the robot can change lane only at either end, but not in the middle. Even when considering this special type of graphs, the orienteering problem is known to be intractable. We optimally solve in polynomial time two special cases, COP-FR where the robot can only traverse full rows, and COP-SC where the robot can access the rows only from one side. To solve the general COP, we then apply our special case algorithms as well as a new heuristic that suitably combines them. Despite its light computational complexity and being confined into a very limited class of paths, the optimal solutions for COP-FR turn out to be competitive in terms of achieved rewards even for COP. This is shown by means of extended simulations performed on both real and synthetic scenarios. Furthermore, our new heuristic for the general case outperforms state-of-art algorithms, especially for input with highly unbalanced rewards.

The study of mobile entities, called robots, that have to accomplish global tasks on the basis of local information has attracted many researchers. A well-known scenario is that in which robots operate in Look-Compute-Move (LCM) computational cycles. In each cycle, a robot takes a snapshot of the environment (Look phase), then executes a distributed algorithm on the basis of the obtained snapshot (Compute phase), and finally moves toward a desired destination, if any (Move phase). LCM cycles might be subject to different temporal constraints dictated by the considered schedule. The classic models for the activation and synchronization of mobile robots are the fully-synchronous, semi-synchronous, and asynchronous models. The three models have been shown to constitute a hierarchy, that is fully-synchronous robots can accomplish more tasks than semi-synchronous robots that in turn can accomplish more tasks than asynchronous robots. The computational power of robots based on the different models has been extensively investigated, revealing a big gap between asynchronous robots and the other models. For many problems it is still not known whether the synchronization is crucial for designing resolution algorithms or not. In order to better understand the asynchronous case, here we propose further models referred to as semi-asynchronous, showing that for robots moving on graphs, semi-synchronous robots can accomplish more tasks than semi-asynchronous robots that in turn can accomplish more tasks than asynchronous robots. Whether the same strict hierarchy also holds for robots moving on the Euclidean plane remains open, however our investigation reveals interesting consequences that may help in better characterizing the computational power of robots with respect to the different synchronization models.

The distributed setting of computational mobile entities, called robots, thathave to perform tasks without global coordination has been extensively studied in the literature. A well-known scenario is that in which robots operate in Look-Compute-Move (LCM) cycles. During each cycle, a robot acquires asnapshot of the surrounding environment (Look phase), then executes an appropriate algorithm by using the obtained snapshot as input (Computephase), and finally moves toward a desired destination, if any (Movephase). Look-Compute-Move cycles might be subject to different temporal constraints dictated by the considered schedule. The classic models for theactivation and synchronization of mobile robots are the well-known fully-synchronous, semi-synchronous, and asynchronous models. A first comprehensive evaluation of the computational power of robots operating in the LCM model and moving within the Euclidean plane, under different levels of synchronization, has been proposed in [Das et al., Int.'l Conf. on Distributed Computing Systems, 2012]. In detail, the authors provide a series of results that prove relations between classic models and variations of them, which consider the possibility that robots are endowed with a visible light, i.e. they are luminous, or with the capability to store some past snapshots, or combinations of them. In this paper, we are interested in similar settings but for robots moving on graphs. In particular, we propose a characterization of the computational power of mobile robots on graphs as follows. First, we show the relations among the three classic activation and synchronization models. Second, we compare the models where robots are endowed with lights against the models without lights. Third, we highlight the relations among the different models concerning luminous robots. Finally, we provide a detailed comparison of the proposed results with the case of robots moving in the Euclidean plane.

In a sensor network, data might be stored in so-called storage nodes, which receive raw data from other nodes, compress them, and send them toward a sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging the raw data to the storage nodes as well as to converge the compressed data to the sink. This is known as the minimum k-storage problem. In general, the problem is NP-hard. However, we are able to devise a polynomial-time algorithm that optimally solves the problem in bounded-tree width graphs. We then characterize the minimum k-storage problem from the approximation viewpoint. We first prove that it is NP-hard to be approximated within a factor smaller than 1 + 1/e. We then propose a local search algorithm that guarantees a constant approximation factor. We conducted extended experiments to show that the algorithm performs very well, exhibiting very small deviation from the optimum and computational time. It is worth to note that our problem is a generalization to the well-known metric k-median problem and then the obtained results also hold for this case.

In heterogeneous networks, devices communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available ones, each device might establish several connections. A connection may be established when the devices at its endpoints share at least one active interface. In this paper, we consider two fundamental optimization problems. In the first one (Maximum Flow in Multi-Interface Networks, MFMI), we aim to establish the maximal bandwidth that can be guaranteed between two given nodes of the input network. In the second problem (Minimum-Cost Flow in Multi-Interface Networks, MCFMI), we look for activating the cheapest set of interfaces among a network to guarantee a minimum bandwidth B of communication between two specified nodes. We show that MFMI is polynomially solvable while MCFMI is NP-hard even for a bounded number of different interfaces and bounded degree networks. Moreover, we provide polynomial approximation algorithms for MCFMI and exact algorithms for relevant subproblems. Finally, we experimentally analyze the proposed approximation algorithm, showing that in practical cases it guarantees a low approximation ratio.

A Wireless Sensor Network (WSN) consists of spatially distributed autonomous sensors that monitor environmental data such as temperature, humidity, light, speed and sound. WSNs pose new security challenges because of their unattended nature and limited resources. Although prevention measures such as encryption and firewalls have been successfully applied, the attacker can physically access the node and modify it. Intrusion Detection Systems (IDSs) are a second line of defence that can be used to mitigate this problem. Building IDSs for WSNs is a new challenge because of the limited resources of the WSN nodes. IDS solutions for sensor networks should try to minimise the use of battery of the sensor nodes in order to prolong the network lifetime. In this paper we analyse different solutions that have been proposed for intrusion detection in wireless sensor networks. More specifically we analyse the impact of popular intrusion detection systems on the life time of the WSNs. Our study is quite general since we consider IDSs that are distributed on the sensor nodes and continuously monitor the networks for evidence of attacks. We also consider IDSs that are event triggered, which means that they require agreement between nodes when a suspicious activity is detected. The agreement is used to detect the attack and isolate the attacker. We analyse the effects of IDSs on battery life. The results show that, popular oral message algorithm of Byzantine generals problem should be considered for small scale WSNs because of the overhead introduced in terms of messages exchanged for decision. We conclude our paper with properties and recommendations for IDSs working for WSNs and some future works.

Abstract We propose novel localization and routing protocols in an actor‐centric wireless sensor network consisting of an actor node and a large number of energy‐constrained sensors operating under L different periodic sleep–awake schedules. Specifically, we propose a semidistributed localization algorithm in which a small subset of sensors extracts their positions in polar coordinates based on the messages received from the actor, and subsequently localizes (also in polar coordinates) the remaining sensors. By modeling the deployed sensors as a two‐dimensional Poisson point process and applying well‐known results from the coupon collector's problem and Chernoff bounds, we analytically derive and also validate, by simulation, the sensor density required to localize all sensors in the network with high probability. The actor‐centric network can be modeled by a cluster adjacency graph G with the help of the already localized polar coordinates that logically partition the network into concentric coronas (around the actor), each subdivided in a varying number of clusters (of almost the same area). To avoid intercluster collisions in G, sensors in different clusters transmit on different channels. A lower bound on the number of channels required to schedule the transmissions without collisions is obtained by solving a distance‐2 vertex coloring problem on G. Optimal and quasioptimal fully distributed algorithms are provided to determine the channel assigned to each cluster in constant time. Finally, we apply these results to develop a geographic routing protocol: the messages generated from the sensors in a given cluster are routed toward the actor through the unique shortest path of G that starts from the node associated with the cluster and goes up to the corona where the actor resides. In each cluster, to avoid redundant retransmissions toward the actor, we select L leaders, one for each periodic sleep–awake schedule. © Wiley Periodicals, Inc. NETWORKS, Vol. 2012.

In the context of scheduling and timetabling, we study a challenging combinatorial problem which is very interesting for both practical and theoretical points of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disruptions, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled activities in order to be "prepared” if a delay occurs, and absorb it without the necessity of rescheduling all the activities from scratch. This realizes the concept of designing robust timetables. During the planning phase, one should also consider recovery features that might be applied at runtime if disruptions occur. This leads to the concept of recoverable robust timetables. In this new concept, it is assumed that recovery capabilities are given as input along with the possible disruptions that must be considered. The main objective is the minimization of the overall needed time. The quality of a robust timetable is measured by the price of robustness, i.e., the ratio between the cost of the robust timetable and that of a nonrobust optimal timetable. We show that finding an optimal solution for this problem is NP-hard even though the topology of the network, which models dependencies among activities, is restricted to trees. However, we manage to design a paeudopolynomial time algorithm based on dynamic programming and apply it on both random networks and real case scenarios provided by Italian railways. We evaluate the effect of robustness on the scheduling of the activities and provide the price of robustness with respect to different scenarios. We experimentally show the practical effectiveness and efficiency of the proposed algorithm.

In this work, we consider a large-scale geographic area populated by tiny sensors and some more powerful devices called actors, authorized to organize the sensors in their vicinity into short-lived, actor-centric sensor networks. The tiny sensors run on miniature nonrechargeable batteries, are anonymous, and are unaware of their location. The sensors differ in their ability to dynamically alter their sleep times. Indeed, the periodic sensors have sleep periods of predefined lengths, established at fabrication time; by contrast, the free sensors can dynamically alter their sleep periods, under program control. The main contribution of this work is to propose an energy-efficient location training protocol for heterogeneous actor-centric sensor networks where the sensors acquire coarse-grain location awareness with respect to the actor in their vicinity. Our theoretical analysis, confirmed by experimental evaluation, shows that the proposed protocol outperforms the best previously known location training protocols in terms of the number of sleep/awake transitions, overall sensor awake time, and energy consumption.

Exploiting high density features of wireless sensor networks represents a challenging issue. In this context, anonymous, asynchronous and randomly distributed sensors are considered along with few devices, called actors, which are more powerful than sensors in terms of energy and transmission capabilities. The paper proposes a new distributed training protocol for coarse-grain localization purposes in high density environments. The aim is to auto-organize the sensors with respect to a virtual infrastructure centered at actors and constituted of concentric rings divided into sectors. Analytical study as well as experiments on the proposed protocol are provided. The obtained results show under which theoretical and practical settings the training process can be performed in a fast and high quality way with respect to the granularity of the required localization and the energy consumption.

Abstract Distributed greedy coloring is an interesting and intuitive variation of the standard coloring problem. Given an order among the colors, a coloring is said to be greedy if there does not exist a vertex for which its associated color can be replaced by a color of lower position in the fixed order without violating the property that neighboring vertices must receive different colors. We consider the problems of Greedy Coloring and Largest First Coloring (a variant of greedy coloring with strengthened constraints) in the Linial model of distributed computation, providing lower and upper bounds and a comparison to the (Δ + 1)‐Coloring and Maximal Independent Set problems, with Δ being the maximum vertex degree in G. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract Given a graph G = (V,E) with |V| = n and |E| = m, which models a set of wireless devices (nodes V) connected by multiple radio interfaces (edges E), the aim is to switch on the minimum cost set of interfaces at the nodes to satisfy all the connections. A connection is satisfied when the endpoints of the corresponding edge share at least one active interface. Every node holds a subset of all the possible k interfaces. Depending on whether k is a priori bounded or not, the problem is called Cost Minimization in Multi‐Interface Networks or Cost Minimization in Unbounded Multi‐Interface Networks, respectively. We distinguish two main variations for both problems by treating the cost of maintaining an active interface as uniform (i.e., the same for all interfaces), or nonuniform. For bounded k, we show that the problem is APX‐hard while we obtain an approximation factor of min ${\{\lceil {k + 1 \over 2} \rceil, {2m \over n}}\}$ for the uniform caseand a (k − 1)‐approximation for the nonuniform case. For unbounded k, i.e., k is not set a priori but depends on the given instance, we prove that the problem is not approximable within O(log k) while the same approximation factor of the k‐bounded case holds in the uniform case, and a min $\{k-1, \, \sqrt{n} \, {(1 + {\rm In} \, n)} \}$ ‐approximation factor holds for the nonuniform case. Next, we also provide hardness and approximation results for several classes of networks: with bounded degree, trees, planar, and complete graphs. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

SYNTHESIS is a tool for automatically assembling correct and distributed component-based systems. In our context, a system is correct when it is deadlock-free and performs only specified component interactions. In order to automatically synthesize the correct composition code, SYNTHESIS takes as input an high-level behavioural description for each component that must form the system to be built and a specification of the component interactions that must be enforced in the system. The automatically derived composition code is implemented as a set of distributed component wrappers that cooperatively interact with each other and with their wrapped components in order to prevent possible deadlocks and make the composed system exhibit only the specified interactions. The current version of SYNTHESIS supports two possible development platforms: Microsoft COM/DCOM, and EJB (Enterprise Java Beans).

We consider the problem of localizing random sensor networks by means of time of arrival capabilities. Interactions among sensors are modeled by a mass-spring system. Masses (sensors) initially have a random estimation of their position. The knowledge of their distance from other masses is translated into connect masses with springs whose length should reach the estimated distances. This determines a set of forces to which masses are subject to. Starting from this configuration we propose several strategies reducing the overall time needed to reach the desired level of equilibrium.

We present an approach to provide intrusion detection systems (IDS) facilities into wireless sensors networks (WSN). WSNs are usually composed of a large number of low power sensors. They require a careful consumption of the available energy in order to prolong the lifetime of the network. From the security point of view, the overhead added to standard protocols must be as light as possible according to the required security level. Starting from the DESERT tool (P. Inverardi et al., 2005) which has been proposed for component-based software architectures, we derive a new framework that permits to dynamically enforce a set of properties of the sensors behavior. This is accomplished by an IDS specification that is automatically translated into few lines of code installed in the sensors. This realizes a distributed system that locally detects violation of the sensors interactions policies and is able to minimize the information sent among sensors in order to discover attacks over the network

We present a protocol that manages wireless ad-hoc sensor networks in several scenarios including large scale, high density and high mobility deployments. One of the main applications is to communicate important information from inaccessible areas by spreading just "enough" mobile sensors which must self-configure and assemble. According to our protocol, connectionless probabilistic (CoP) routing, the information is routed in a multi-hop, cluster level fashion by enabling each sensor to make individual decisions regarding its mode of operation. The aim is to prolong the network's lifetime by minimizing the energy spent for each communication. CoP is capable of addressing high mobility requirements as it is completely independent of any kind of topological knowledge and control messages. We show by extended experiments that CoP performs very well in terms of consumed energy by comparing it to a standard directed flooding and a greedy forwarding protocol.

In this paper we present a new upper bound on the approximation ratio of the minimum spanning tree heuristic for the basic problem on ad-hoc networks given by the minimum-energy broadcast routing (MEBR) problem. We introduce a new analysis allowing to establish a 6.33-approximation ratio in the 2-dimensional case, thus decreasing the previously known 7.6 upper bound (M. Flammini et al., 2004).