This paper explores the impact of node mobility on DMAC, a typical clustering protocol for mobile ad hoc networks. In particular, in this paper we evaluate the cost of maintaining the DMAC clustering structures when the nodes move according to three different mobility models, namely, the random way point model, the Brownian motion and the Manhattan mobility model. Via ns2-based simulations we have observed that the mobility models have different impact on protocol performance. The general trend, however, appears to be the same for networks of increasing size. The second contribution of this paper concerns investigating ways of mitigating the impact of mobility on the clustering structure and hence over the overall network performance. We consider a generalization of DMAC (GDMAC) where rules are established to decrease the number of cluster updates. Via simulation we have observed that GDMAC is effective in reducing the clustering overhead imposed by mobility, and the corresponding maintenance cost.

We present the definition and performance evaluation of a protocol for building and maintaining a connected backbone among the nodes of a wireless sensor networks (WSN). Building backbones first, and then coping with network dynamics is typical of protocols for backbone formation. Rules for building the backbone, however, do not take into account the following network dynamics explicitly. This makes maintaining a connected backbone quite costly, especially in terms of reorganization time, overhead and energy consumption. Our protocol includes in the backbone forming operations a fail-safe mechanism for dealing with the addition and the removal of nodes, which are typical events in a WSN. More specifically, the network is kept partitioned into clusters that are cliques, i.e., nodes in each cluster are directly connected to each others. Therefore, removing a node does not disrupt a cluster, and adding one requires simple operations for checking node admission to the cluster. The protocol, termed CC ("double c," for clique clustering), comprises three phases, each designed to render the operations of the others swift and efficient. The first phase partitions the network into clusters that are cliques. Clusters are then joined to form a backbone that is provably connected. Finally, the third, more on-line phase, maintains the backbone connected in face of node additions and removals. We compare the performance of CC with that of DMAC, a protocol that has been previously proposed for building and maintaining clusters and backbones in presence of network dynamics. Our comparison concerns metrics that are central to WSN research, such as time for clustering and backbone reorganization, corresponding overhead, extent of the reorganization (i.e., number of nodes involved in it), and properties of the resulting backbone, such as its size, backbone route length, number of gateway and nodes per cluster. Our ns2-based simulation results show that the design criteria chosen for CC are effective in producing backbones that can be reconfigured quickly and with remarkably lower overhead.

This paper demonstrates the advantages of using controlled mobility in wireless sensor networks (WSNs) for increasing their lifetime i.e., the period of time the network is able to provide its intended functionalities. More specifically, for WSNs that comprise a large number of statically placed sensor nodes transmitting data to a collection point (the sink), we show that by controlling the sink movements we can obtain remarkable lifetime improvements. In order to determine sink movements, we first define a Mixed Integer Linear Programming (MILP) analytical model whose solution determines those sink routes that maximize network lifetime. Our contribution expands further by defining the first heuristics for controlled sink movements that are fully distributed and localized. Our Greedy Maximum Residual Energy (GMRE) heuristic moves the sink from its current location to a new site as if drawn toward the area where nodes have the highest residual energy. We also introduce a simple distributed mobility scheme (Random Movement or RM) according to which the sink moves uncontrolled and randomly throughout the network. The different mobility schemes are compared through extensive ns2-based simulations in networks with different nodes deployment, data routing protocols, and constraints on the sink movements. In all considered scenarios, we observe that moving the sink always increases network lifetime. In particular, our experiments show that controlling the mobility of the sink leads to remarkable improvements, which are as high as sixfold compared to having the sink statically (and optimally) placed, and as high as twofold compared to uncontrolled mobility.

This paper concerns the definition of an analytical model and of a distributed protocol, termed Greedy Maximum Residual Energy (GMRE), for determining the routes of a mobile data collector (sink) traveling through the nodes of a wireless sensor network (WSN). The routes are determined with the overall aim of maximizing the network lifetime. An ns2-based simulation comparison between GMRE, optical static sink placement and random sink mobility shows that GMRE yields remarkable improvements both for network lifetime and for balancing energy consumptions throughout the network

This paper concerns the comparative performance evaluation of protocols for clustering and backbone formation in ad hoc networks characterized by a large number of resource-constrained nodes. Our aim is twofold. We provide the first simulation-based detailed investigation of techniques for clustering and backbone formation that are among the most representative of this area of ad hoc research. Furthermore, we delve into the nature of the selected protocols to assess the effects of the "degree of localization" on their operations, i.e., how being able to execute the protocol based only on local information affects the overall protocol performance. Extensive ns2-based simulation results show that highly localized protocols are rewarded with good performance with respect to all metrics of interest which include protocol duration, energy consumption, message overhead, route length and backbone size.

This paper describes the results of the first ns2-based comparative performance evaluation among four major solutions presented in the literature for forming multi-hop networks of Bluetooth devices (scatternet formation). The four protocols considered in this paper are BlueTrees, BlueStars, BlueNet and the protocol presented by Li and Stojmenovic which proposes geometric techniques for topology reduction combined with cluster-based scatternet formation. We implemented the operations of the four protocols from device discovery to scatternet formation. By means of a thorough performance evaluation we have identified protocol parameters and Bluetooth technology features that affect the duration of the formation process and the properties of the produced scatternet. We have investigated how possible modifications of the BT technology (e.g., backoff duration, possibility for a BT inquirer to identify itself) make device discovery more efficient for scatternet formation in multi-hop networks. We have then discussed implementation concerns for each of the selected protocols. Finally, we have analyzed the protocols overhead as well as the effect of the different protocols operations on key metrics of the generated scatternets, which includes the time needed for forming a scatternet, the number of its piconets, the number of slaves per piconet, the number of roles assumed by each node and the scatternet route lengths.

In this paper we describe BlueMesh, a new protocol for the establishment of scatternets, i.e., multi-hop wireless networks of Bluetooth devices. BlueMesh defines rules for device discovery, piconet formation and piconet interconnection so to generate connected scatternets with the following desirable properties. BlueMesh forms scatternets without requiring the Bluetooth devices to be all in each other transmission range. BlueMesh scatternet topologies are meshes with multiple paths between any pair of nodes. BlueMesh piconets are made up of no more than 7 slaves. Simulation results in networks with over 200 nodes show that BlueMesh is effective in quickly generating a connected scatternet in which each node, on average, does not assume more than 2.4 roles. Moreover, the route length between any two nodes in the network is comparable to that of the shortest paths between the nodes.

This paper describes a new protocol for the establishment of multi-hop ad hoc networks based on Bluetooth devices. The protocol proceeds in three phases: Device discovery, partitioning of the network into Bluetooth piconets and interconnection of the piconets into a connected scatternet and has the following desirable properties. It is executed at each node with no prior knowledge of the network topology, thus being fully distributed. The selection of the Bluetooth masters is driven by the suitability of a node to be the ``best fit'' for serving as a master. The generated scatternet is a connected mesh with multiple paths between any pair of nodes, thus achieving robustness. Differently from existing solutions, no extra hardware is required to run the protocol at each node, and there is no need for a designated node to start the scatternet formation process. Simulation results are provided which evaluate the impact of Bluetooth device discovery phase on the performance of the protocol.

This paper introduces Dynamic Source Multicast (DSM), a new protocol for multi-hop wireless (i.e., ad hoc) networks for the multicast of a data packet from a source node to a group of mobile nodes in the network. The protocol assumes that, through the use of positioning system devices, each node knows its own geographic location and the current (global) time, and it is able to efficiently spread these measures to all other nodes. When a packet is to be multicast, the source node first locally computes a snapshot of the complete network topology from the collected node measures. A Steiner (i.e., multicast) tree for the addressed multicast group is then computed locally based on the snapshot, rather than maintained in a distributed manner. The resulting Steiner tree is then optimally encoded by using its unique Prufer sequence and is included in the packet header as in, and extending the length of the header by no more than, the header of packets in source routing (unicast) techniques. We show that all the local computations are executed in polynomial time. More specifically, the time complexity of the local operation of finding a Steiner tree, and the encoding/decoding procedures of the related Prufer sequence, is proven to be O(n²), where n is the number of nodes in the network. The protocol has been simulated in ad hoc networks with 30 and 60 nodes and with different multicast group sizes. We show that DSM delivers packets to all the nodes in a destination group in more than 90% of the cases. Furthermore, compared to flooding, DSM achieves improvements of up to 50% on multicast completion delay.

This paper introduces MWIS, a distributed algorithm for the efficient determination of a maximal weighted independent set in the topology graph G of a wireless network. Motivated by the observation that the problem of partitioning wireless nodes into clusters easily reduces to the problem of finding a maximal weighted independent set of nodes, the proposed algorithm is described by taking into account two main characteristics of wireless networks, namely, the broadcast nature of the wireless medium and the possibility to support nodes mobility. MWIS is executed at each node by means of fast message triggered procedures that require the sole knowledge of the topology local to the node. Moreover, its time complexity is proven to be bounded by a topology dependent parameter of the network (the stability number alpha(G) of the network topology graph G), rather than by the invariant number n of the network nodes. Finally, by using a well known results on the stability number in random graphs, we show that the average time complexity of the MWIS is logarithmic in n.

Broadcast (distributing a message from a source node to all other nodes) is a fundamental problem in distributed computing. Several solutions for solving this problem in mobile wireless networks are available. In current solutions mobility is dealt with either by the use of randomized retransmissions or, in case of deterministic delivery protocols, by using conflict-free transmission schedules which need to be periodically recomputed when topology changes. Randomized solutions can be used only when unbounded delays can be tolerated. Solutions that require schedule recomputation become unstable when the topology rate of change exceeds the schedule recomputation rate. The deterministic broadcast protocol we introduce in this paper overcome the above limitations by using a novel, mobility transparent schedule, thus providing a delivery (time) guarantee without the need to recompute the schedules when topology changes. We show that the proposed protocol is simple and easy to implement, and that it is optimal in networks in which assumptions on the maximum number of the neighbors of a node can be made.

Time-Spread Multiple-Access (TSMA) protocols are scheduled access protocols for mobile multi-hop radio networks that guarantee deterministic access to the shared channel regardless of the possibility of radio interference. In scheduled access methods, time is considered to be slotted and time slots are cyclically organized into frames. In general, the shorter the frame, the more efficient the protocol. An Omega(loglog n) lower bound is known on the minimum length of the frame of TSMA protocols in networks with n nodes. In this note we improve that lower bound by characterizing the multiple access to the radio channel as acombinatorial problem. The proposed characterization allows us to prove that no TSMA protocols can successfully schedule the transmissions of the nodes of a multi-hop radio network in frames with less than log n time slots.

Causal Trees are a variant of Milner's Synchronization Trees which aims at reconciling two antagonistic views of semantics for concurrent systems: the interleaving models and the truly concurrent ones. The original model of Causal Trees provides us with an interleaving description of a concurrent system which faithfully expresses causality by enriching the action labels of a synchronization tree. These enriched labels supply indication of the observable causes of observable actions. In this note we revise the original model of Causal Trees, so that every action label bears the causal indication, and not only the observable actions. This permits to inherit all the results of Milner's original theory in a natural way.

We characterize from the computational point of view the problem of finding a path of length exactly k in a weighted directed graph G. We show that the decision version of the problem is NP-complete not only for the class of all weighted directed graphs G, but also for the special case when G is acyclic and when we deal with undirected graphs. However, when the lengths of the arcs of G are polynomially bounded the problem can be solved by efficient algorithms (i.e., the problem is pseudo-polynomial). In such a case we also devise algorithms for solving the search version of the problem. More precisely, we give a polynomial time algorithm and a random fast parallel algorithm for finding a path of length k for each pair of vertices of a weighted acyclic directed graph G whose length function is polynomially bounded. Finally, we show that other well known routing problems have the same properties of the problem under consideration. All algorithms are designed exploiting the strong link between graph theory and linear algebra.

As a building step of designing integrated solution for forming multi-hop Personal Area Networks (PANs) of Bluetooth devices, in this paper we introduce a new intra-piconet scheduling protocol that defines the interaction among masters and slaves with an eye to the flows passing through their piconets. Differently from previous intra-piconet solutions, such as Pure Round Robin, its E-limited variation, and the more recent Credit Scheme, fairness and traffic adaptivity is now achieved on a per-flow basis. Our FLow-fair Intra-Piconet (FlIP) scheduling identifies the flows passing through each piconet slave. Based on this information the master can efficiently manage intra-piconet resources. FlIP is compared with the three leading solutions for intra-piconet scheduling mentioned. Through ns2-based simulations we show that FlIP is effective in decreasing both packet drop rate as well as end-to-end packet latency.

This paper presents the definition and evaluation of a new protocol for providing a wireless sensor network (WSN) with a hierarchical organization. Differently from previously proposed solutions, our protocol, termed CC ("double c," for clique clustering), includes in its operation a fail-safe mechanism for dealing with node failure or removal, which are typical of WSNs. More specifically, the network is partitioned into clusters that are cliques, i.e., nodes in each clusters are directly connected to each others. An efficient mechanism for building a connected backbone among the clusters is provided within CC that is also resilient to node failure. Both clustering and backbone formation are completely localized, in the precise sense that only nodes physically close to a failing node are involved in the reconfiguration process. We compare the performance of CC with that of DMAC, a protocol that has been previously proposed for building and maintaining clusters and backbones in presence of node removal. Our comparison concerns metrics that are central to WSN research, such as time for clustering and backbone reorganization, corresponding overhead (in bytes and transmission energy), backbone size, extent of (i.e., number of nodes involved in) the reorganization, and backbone route length. Our ns2-based simulation results show that the design criteria chosen for CC are effective in producing backbones that can be reconfigured quickly (152% faster than DMAC's) and with remarkably lower overhead (one order of magnitude less than for DMAC).

Among the many ways of improving the performance of a wireless sensor network (WSN) in terms of crucial metrics such as its lifetime and data latency, exploiting the mobility of some of the network components has been recently observed to be among the most promising. In this paper we demonstrate how two very different schemes for WSN mobility leads to different benefits for network performance. More specifically, we consider the data MULEs kind of random, uncontrolled mobility with single-hop data collection and we compare it with the controllable mobility of the data collection point (sink) where sensor-to-sink data routing follows multi-hop paths. Through quite thorough ns2-based simulations we show that data MULEs are to be used in those WSNs deployed for delay tolerant applications. Benefits of this scheme include low energy consumption and easier protocol and nodal design. Data latency, however, can be unbearably high. We therefore show that a good tradeoff between network lifetime gains and data latency increases can be obtained by using those solutions where the mobility of the sink is controlled by the network conditions.

Heterogeneous wireless sensor networks are made up of different kinds of nodes. Some nodes, the sensors, are used as an interface to the physical environment. Other nodes act instead as servers, providing various services to the sensors. In this paper we define an architecture to enable the sensors to efficiently localize the services, and hence the servers. Our is a two-tier server architecture. The first tier is made up of the actual servers. The second tier is formed by nodes that are basically standard nodes (like the sensors). These nodes know the current position of the servers (they are called server locators). Sensors needing service query the server locators to find the corresponding service. The service locator sends a service position to the sensor. Finally, once got ahold of a server location, a sensor uses the service directly. Our server architecture provides load balancing (of queries to the servers) and is tolerant to server faults. Sensor nodes are endowed with caches to maintain the location of popular services. Experiments demonstrate the effectiveness of using caches at the sensor nodes.

This paper briefly reviews the wide variety of methods proposed for localizing wireless sensor nodes. We describe the major recent solutions where sensor nodes may use beacons (devices that know their location and can broadcast it) or not, and ranging measurements or not. Our discussion presents pros and cons of using different information or devices, and ends up with describing where research in this field in going.

Building and deploying multi-hop networks of Bluetooth devices (aka scatternets) concerns devising methods for forming piconets, connecting them through shared gateways, and scheduling the presence of these gateways among the piconets they interconnect (inter-piconet scheduling). There are several types of gateways, and their efficient scheduling is affected by the gateway type. Scatternet formation and scheduling have been dealt with separately in the past. This leads to network performance degradation because of the missed opportunity of designing scatternet formation protocols that best address scheduling requirements and vice-versa. In this paper we propose SS-Blue, an integrated mechanism for the joint design of scatternet formation and scheduling. Specifically, we enhance an efficient scatternet formation protocol by adopting methods for piconets interconnection that favor types of gateways which will result in a better performing inter-piconet scheduling. At the same time, a fair and traffic adaptive mechanism is proposed to schedule all types of gateways (inter-piconet scheduling), and for managing intra-piconet scheduling, i.e., for scheduling traffic transmission within a piconet. Our solution is evaluated through extensive simulations. Our results show that SS-Blue succeeds in producing scatternets whose gateways are efficiently scheduled. The combination of the proposed intra- and inter-piconet scheduling is shown to be remarkably effective in favoring packet forwarding with very low end-to-end latency.

This paper concerns the definition of an analytical model and distributed protocols for determining the routes of a mobile data collector (\emph{sink}) traveling through the nodes of a wireless sensor network (WSN). The routes are determined with the overall aim of maximizing the network lifetime. The contribution of our work is twofold. First, we introduce a novel mixed integer linear programming formulation for determining the sink's route and the sojourn time at the different "sink sites." The model takes into account realistic parameters such as the maximum distance the sink can travel between sites, different sink mobility rates, as well as the costs to support and perform data routing. Solutions to the model provide the route of the sink as a sequence of sites and the sojourn times at those sites that induce the maximum network lifetime. We then propose the Greedy Maximum Residual Energy (GMRE) protocol for sink mobility. GMRE is distributed and localized, thus being suitable for wireless sensor networking. In GMRE the sink greedily keeps moving toward those areas in the network where there is the most residual energy, as if "drawn" to them. This heuristic is then compared with a very simple and energy-unaware protocol where the next site in the sink route is chosen randomly and uniformly each time the sink moves. Simulation results show that GMRE leads to improvements in network lifetime that are four times as much as the lifetime when the sink is kept static, while balancing energy consumption throughout the network. At the same time, we show how the expected increases in data latency are reasonably contained.

This paper describes "Hack Boston," a project carried out by members of the IEEE student chapter at Northeastern University (NU) in Boston, MA. Our purpose was to identify the presence of wireless networks in order to determine qualitatively and quantitatively how secure these networks are, thus monitoring the security awareness of the wireless community around NU. Our study goes beyond common "war driving/war walking." We present statistical results over a range of metrics that go from the number of wireless signals in the scanned areas to the specific encryption method they use (if any). Experiments have been performed in 2004 and 2005, which indicate an increased awareness of the need for securing in-home wireless Internet connections. Our results are analyzed and compared with national statistics. We finally describe the activities that the NU IEEE student chapter is proposing for educating the community about the proper, secure use of wireless technologies.

This paper concerns a study of the process of localizing the nodes of a multi-hop wireless networks, i.e., of having the node computing their coordinates with respect to a suitable reference system. We consider networks where the nodes perform measurements of distance and angle of arrival from nodes within their transmission radius. We describe a simple localization protocol, termed Range-Based Centroid (RBC), that starting from a single node (the beacon) with given coordinates localizes all the network nodes with reasonable accuracy. We then propose a new localization protocol that achieves greater accuracy by containing the propagation of the localization error as the process progresses away from the beacon. We quantify the improvements of the proposed protocol, termed MEC2 (for Minimum Enclosing Circle Containment) by simulations. In the considered scenarios, MEC2 keeps the localization error within 21% of the nodes' transmission radius, with 20-30% improvements over RBC.

In this study we have investigated the effectiveness of building "napping backbones" for data dissemination in wireless sensor networks. The NAPBACK protocol builds connected backbones whose nodes are endowed with a sleep/awake schedule that induces considerable energy savings, and hence prolongs the network lifetime. Via simulations on networks with up to 250 nodes we have observed increases on network lifetime up to almost 70% with respect to previous topology control protocols (S-DMAC). Increased latency is the price to pay for the improvements on lifetime, which currently makes NAPBACK a viable solution for delay-insensitive WSN applications. Multifold are the research directions opened by this initial study. We are planning to design different methods for defining the schedules of the backbone nodes. Final aims include the minimization of the latency, as well as throughput maximization. Sleep/awake scheduling methods should also be independent of nodes synchronization, and could be based on deterministic strategies, rather than the simple randomized technique used here

This paper explores the impact of node mobility on DMAC, a typical clustering protocol for mobile ad hoc networks. Several protocols for clustering have been proposed, which are quite similar in operations and performance. We selected one and evaluate the cost of maintaining the clustering structures when the nodes move according to three different mobility models, namely, the random way point model, the Brownian motion and the Manhattan mobility model. Via ns2-based simulations we have observed that the mobility models have different impact on protocol performance. The general trend, however, appears to be the same for networks of increasing size. The second contribution of this paper concerns mitigating the impact of mobility over the clustering structure and hence on the overall network performance. We consider a generalization of DMAC (GDMAC) where rules are established to decrease the number of cluster updates. Via simulation we have observed that GDMAC is effective in reducing the clustering overhead imposed by mobility, and hence its maintenance cost.

This research concerns the definition of an analytical model and protocols for determining the routes of a mobile data collector (sink) traveling through the nodes of a wireless sensor network (WSN). The routes are determined with the overall aim of maximizing the network lifetime. The contribution of our work is twofold. First, we introduce a novel mixed integer linear programming formulation for determining the sink's route and the sojourn time at the different ``sink sites.'' The model takes into account realistic parameters such as the maximum distance the sink can travel between sites as well as constraints on the sojourn time at a site. Solutions to the model provide the route of the sink as a sequence of sites and the sojourns time at those sites that induce the maximum network lifetime. We then propose the Greedy Maximum Residual Energy (GMRE) protocol for sink mobility. Such protocol is distributed and localized, thus being suitable for wireless sensor networking. In GMRE the sink greedily keeps moving toward those areas in the network where there is the most residual energy, as if ``drawn'' to them. This heuristic is then compared with a very simple and energy-unaware protocol where the next site in the sink route is chosen randomly and uniformly each time the sink moves. Simulation results show remarkable improvements both for network lifetime and for balancing energy consumptions throughout the network in case GMRE is adopted.

Wireless sensor networks (WSNs) are multi-hop wireless networks made up of energy-constrained sensing devices capable of delivering the sensed data to one or more collection points (sinks). In a typical WSN scenario the sink usually keeps stationary among the sensors that are static as well. A recent research trend aims at proposing energy-efficient protocols where the mobility of the sink is exploited for maximizing the lifetime of the network. A Linear Programming (LP) model is used for determining the sink sojourning points (SSPs) and the sojourn times of the sink that maximize network lifetime. Sensor nodes are assumed to be deployed realistically at arbitrary locations and the SSPs are selected among the vertices of the Voronoi Diagram (VD) corresponding to the sensor network topology. Message routing is also determined efficiently using the VD. Experimental results demonstrate the effectiveness of our LP model in determining a sink route and sojourn times along the route that considerably prolong the network lifetime with respect to the case with static sink.

This paper explores the idea of exploiting the mobility of data collection points (sinks) for the purpose of increasing the lifetime of a wireless sensor network with energy-constrained nodes. We give a novel linear programming formulation for the joint problems of determining the movement of the sink and the sojourn time at different points in the network that induce the maximum network lifetime. Differently from previous solutions, our objective function maximizes the overall network lifetime (here defined as the time till the first node "dies" because of energy depletion) rather than minimizing the energy consumption at the nodes. For wireless sensor networks with up to 256 nodes our model produces sink movement patterns and sojourn times leading to a network lifetime up to almost five times that obtained with a static sink. Simulation results are performed to determine the distribution of the residual energy at the nodes over time. These results confirm that energy consumption varies with the current sink location, being the nodes more drained those in the proximity of the sink. Furthermore, the proposed solution for computing the sink movement results in a fair balancing of the energy depletion among the network nodes.

Prolonged lifetime, robustness and scalability are important requirements in wireless sensor networks (WSNs). In this paper we show that via the energy-efficient construction of a connected backbone and a simple stateless routing over the backbone it is possible to achieve these desired goals. We present a ns2 simulation-based comparison between data dissemination in WSNs when a) each sensor routes the sensed data to the sinks directly (flat network organization), and b) a backbone is constructed on top of the flat network topology and only a few nodes are in charge of data delivery to the sinks (hierarchical organization, here termed ViBES: Virtual Backbone for Energy Saving). Multiple targets (i.e., moving nodes) are allowed to roam throughout the network of static sensors. Simulations are performed on networks of increasing densities where up to 3 targets are identified and reported to up to 3 sinks. Our results show that routing through the backbone increases the network lifetime up to seven times over the flat network organization where network lifetime is defined as a) the time till the first node dies because of energy depletion, b) the time required for 30% of the network nodes to die, and c) the time required for the network to get disconnected.

This paper concerns the comparative performance evaluation of protocols for clustering and backbone formation in ad hoc networks characterized by a large number of resource-constrained nodes. A typical example of these networks are wireless sensor networks. We selected protocols that represent the main approaches to clustering and backbone formation for ad hoc networks. The DCA protocol represents those protocols whose backbone construction method is based on selecting nodes as clusterheads and then joining them to form a connected backbone. The algorithm proposed by Wu and Li has been chosen to exemplify those algorithms that build a connected backbone and then prune away redundant nodes. Finally, the algorithm by Wan et al. has been considered here for its more theoretical properties of producing a backbone with a constant approximation factor, linear time complexity and optimal message complexity. Extensive ns2-based simulation results show that simpler algorithms are rewarded with good performance with respect to most metric of interest which include per node energy consumption and message overhead. However, they tend to produce larger backbones. On the other side, more complex solutions produce smaller backbones at greater cost. In order to obtain a backbone reasonably small at reasonable cost we propose an enhancement of the DCA algorithm, termed DCA-S, which enriches the DCA backbone construction with a recently proposed and resource effective sparsification rule. DCA-S leads to a robust backbone close in size to that generated by the Wan et al. protocol without significantly degrading the performance in terms of all the other relevant metrics.

We present Sensor-DMAC (S-DMAC), a new mechanism for topology control in wireless sensor networks. A (connected) fraction of the network nodes is efficiently selected to perform the network operation while all other nodes are switched to an energy-conserving ``sleep mode.'' Based on DMAC, a clustering protocol enhanced with backbone formation, S-DMAC reduces to a minimum the overhead associated to node selection, backbone formation and maintenance, thus increasing the overall network lifetime. Ns2-based simulations have been performed to compare S-DMAC with DMAC and also with GAF, a recent solution for topology control in wireless sensor networks. These results show S-DMAC as more effective in providing connected and energy efficient routes of data from the sensor nodes to the network collection point (sink).

This paper describes the results of an ns2-based comparative performance evaluation among three major solutions presented in the literature for forming multi-hop networks of Bluetooth devices (scatternet formation). The three protocols considered in this paper are BlueTrees, BlueStars, and the ``Yao protocol.'' We observed that device discovery is the most time-consuming operation, independently of the particular protocol to which it is applied. By means of a thorough performance evaluation we have identified protocol parameters and Bluetooth technology features that affect the duration of device discovery. We have also analyzed the effect of the different protocols operations on key metrics of the generated scatternets. The comparative performance evaluation showed that due to the simplicity of its operations and to its basic working requirements BlueStars is by far the fastest protocol for scatternet formation which also yields to scatternets with a lower number of piconets, average route length and number of roles per node. However, BlueStars produces scatternets with an unbounded, possibly large number of slaves per piconet, which imposes the use of potentially inefficient Bluetooth operations. A good compromise when interested in forming scatternets whose piconets have a bounded number of slaves is obtained by combining BlueStars and the Yao protocol. Although the time for scatternet formation and the route lengths are longer than in BlueStars, with the combined solution we obtain an overall good protocol performance and scatternets with desired characteristics.

In this paper we describe BlueMesh, a new protocol for the establishment of scatternets, i.e., multihop ad hoc networks of Bluetooth devices. BlueMesh defines rules for device discovery, piconet formation and piconet interconnection so to achieve the following desirable properties. a) BlueMesh generates connected scatternets without requiring the Bluetooth devices to be all in each other transmission range. b) The BlueMesh scatternet topology is a mesh with multiple paths between any pair of nodes. c) BlueMesh piconets are made up of no more than 7 slaves. Simulation results in networks with 200 nodes show that BlueMesh is effective in quickly generating a connected scatternet in which each node, on average, does not assume more than 2.3 roles. Moreover, the length of routes between any two nodes in the network, is comparable to that of the shortest paths between the nodes.

In this paper we evaluate the performance of a new protocol for scatternet formation in Bluetooth multi-hop networks. The protocol implements the three fundamental steps to scatternet formation, namely, device discovery, piconet formation and piconet interconnection. A Bluetooth extension to ns2, the VINT project simulator, has been developed to address all the details pertinent to scatternet formation. The performance evaluation allows us to assess the impact of the device discovery duration over the scatternet formation process, to evaluate the time for the protocol to generate a connected scatternet, and to investigate metrics that pertain to the ``quality'' of the scatternet, such as the average number of piconets, the average number of slaves per piconets, the average number of roles assumed by each node and the average length of the routes between any two Bluetooth devices.

The paper concerns device discovery in multi-hop networks of Bluetooth devices. We start from the observation that forming a Bluetooth scatternet (i.e., a multi-hop wireless topology) requires each pair of neighboring nodes to have a ``symmetric'' knowledge of each other, i.e., if node u knows node v then node v knows node u. We investigate the use of the Bluetooth procedures for device discovery (inquiry procedures) in order to guarantee the needed symmetric knowledge for scatternet formation. Through the use of simulations we observed that despite the long time required for each node to become aware of the presence of all its neighbors, the Bluetooth topologies obtained by using the devices discovered after just 6 seconds are connected. The average number of neighbors of each node and the average route length are also consistently close to the values that we would obtain if all the neighbors of a device were discovered.

This paper describes a new protocol for the establishment of multihop ad hoc networks based on Bluetooth devices. The proposed solution is specification compatible, and achieves the following desirable properties, only a few of which are available in previous solutions. The protocol is executed at each node with no prior knowledge of the network topology, thus being fully distributed. The selection of the Bluetooth masters is driven by the suitability of a node to be the ``best fit'' for serving as a master. The generated topology (a scatternet, according to the Bluetooth terminology) is a connected mesh with multiple paths between any pair of nodes, thus achieving robustness. Differently from existing protocols, the proposed solution does not assume any designated device to start the scatternet formation process, and it is multihop in the precise sense that there is no requirement for each node to be in the transmission range of all the other nodes (one-hop networks).

We consider the problem of securing communication in large ad hoc networks, i.e., wireless networks with no fixed, wired infrastructure and with multi-hop routes. Such networks, e.g., networks of sensors, are deployed for applications such as microsensing, monitoring and control, and for extending the peer-to-peer communication capability of smaller group of network users. Because the nodes of these networks, which we term pebbles for their very limited size and large number, are resource constrained, only symmetric key cryptography is feasible. We propose a key management scheme to periodically update the symmetric keys used by all pebbles. By combining mobility-adaptive clustering and an effective probabilistic selection of the key-generating node, the proposed scheme meets the requirements of efficiency, scalability and security needed for the survivability of networks of pebbles (pebblenets).

In this paper, we propose a new protocol for efficiently managing large ad hoc networks, i.e., networks in which all nodes can be mobile. We observe that, since nodes in such networks are not necessarily equal in that they may have different resources, not all of them should be involved in basic network operations such as packet forwarding, flooding, etc. In the proposed protocol, a small subset of the network nodes is selected based on their status and they are organized to form a backbone (whence the name ``backbone protocol'' or simply B-protocol to our proposed solution). The B-protocol operates in two phases: first the ``most suitable'' nodes are selected to serve as backbone nodes, then the selected nodes are linked to form a backbone which is guaranteed to be connected if the original network is. The effectiveness of the B-protocol in constructing and maintaining in face of node mobility and node/link failure a connected backbone that uses only a small fraction of the nodes and of the links of the original networks is demonstrated via simulation. The obtained results show that both the selected backbone nodes and the links between them in the backbone are considerably smaller than the nodes and the links in the flat network.

Broadcast is the network operation that concerns disseminating a message from a given node to every other node in the network. When a network is comprised of mobile nodes, as in ad hoc networks where potentially all the nodes can be mobile, broadcast protocols need to be distributed, i.e., they should be executed at each node with the minimum possible knowledge of the dynamically changing network topology. This paper presents a general method for proving lower bounds for the problem of distributed broadcast in mobile ad hoc networks. As a consequence of the generality of the proposed method, previously proven lower bounds, both for randomized and deterministic broadcast, can be seen as specific applications of the proposed method. The effectiveness of our framework is also demonstrated by proving in a simpler and direct way the linear lower bound proven for deterministic broadcast in networks with constant diameter.

Bluetooth is an open specification for short-range wireless communication and networking, mainly intended to be a cable replacement between portable and/or fixed electronic devices. The specification also defines techniques for interconnecting large number of nodes in scatternets, thus enabling the establishment of a mobile ad hoc network (MANET). While several solutions and commercial products have been introduced for one-hop Bluetooth communication, the problem of scatternet formation has not yet been dealt with. This problem concerns the assignment of the roles of master and slave to each node so that the resulting MANET is connected. In this paper we introduce two novel protocols for forming connected scatternets. In both cases, the resulting topology is termed a bluetree. In our bluetrees the number of roles each node can assume are limited to two or three (depending on the protocol), thus imposing low slave management overhead. The effectiveness of both protocols in forming MANETs is demonstrated through extensive simulations.

Digital watermarking involves embedding copyright marks (watermarks), often imperceptibly, in multimedia objects to enhance or protect their value. In this paper we describe a novel watermarking algorithm suitable for video coding techniques such as MPEG-4 and H.263/.324 and we test it in a wireless environment. The proposed algorithm satisfies critical properties not all of which are available in previous solutions. These properties include: Resistance (robustness) of the embedded watermark to the error-prone nature of wireless channels as well as to video frame loss or misplacement, negligible probability of reading a non embedded watermark, non-degradation of the marked video sequence and the possibility to mark video objects (e.g., MPEG-4 objects) in a single frame separately. Experimental results are given that show how these and other properties are achieved when video sequences are corrupted with errors that are typical of a wireless channel.

This paper introduces OLAM, a novel On-demand Location Aware Multicast protocol for ad hoc networks. The protocol assumes that, through the use of positioning system devices, such as Global Positioning System (GPS) devices, each node knows its own position and the current (global) time, and it is able to efficiently distribute these measures, including its current transmission radius, to all other nodes. As the measures are received, each node updates its local snapshot of the complete network topology. When a packet is to be multicast to a group, a heuristic is then used to locally compute the Steiner (i.e., multicast) tree for the addressed multicast group based on the snapshot rather than maintaining the tree in a distributed manner. The resulting Steiner tree is then optimally encoded by using its unique Prüfer sequence and included along with the packet, extending the length of the header by no more than the header of packets in source routing (unicast) techniques. All local computations are executed using efficient (i.e., polynomial time) algorithms. The protocol has been simulated in ad hoc networks with 30 and 60 nodes and with different multicast group sizes. We show that OLAM delivers packets to all the nodes in a destination group in more than 85% of the cases. Furthermore, compared to flooding, OLAM achieves improvements of up to 50% on multicast completion delay.

This paper presents a uniform solution for multipoint communication in mobile multi-hop wireless networks, spanning the full range of problems from routing to broadcast. Using a dissemination mechanism, each node distributes its own attributes, such as its position, time, and transmission radius, to all other nodes in the network. Through the dissemination, each node becomes aware of the location of all other nodes in the network. Thus when a packet is to be transmitted, the node that is the source of the packet is able to locally compute a ``snapshot'' of the network topology from the collected node attributes. A tree that describes the path(s) to follow to reach the destination(s) of the multipoint communication is then locally computed on the resulting snapshot. The tree obtained is optimally encoded by its unique Prüfer sequence, included in the packet header, and then the path(s) traversed hop-by-hop as in any source routing technique. A finite tree with j nodes can be encoded by a Prüfer sequence of length j-2, thus the Steiner tree for a multicast packet or the spanning tree for a broadcast packet is encoded as efficiently as the longest path in routing. All the local computations are efficient, being executed in polynomial time. Specifically, computing the appropriate tree, and the encoding/decoding procedures of the related Prüfer sequence, requires O(n²) time, where n is the number of nodes in the multi-hop network. Our uniform solution to multipoint communication has been simulated in multi-hop wireless networks with up to n=30 nodes, showing a success rate of 98% and 97% for routing and multicast, respectively.

The problem of routing packets in ad hoc networks is complex due to the lack of network infrastructure, shifting the reliance of packet forwarding onto the nodes of the network, all of which are mobile. In order to improve the robustness and adaptation of protocols for ad hoc networks to node mobility, in this paper we propose a new metric that bases route selection on the probability of the existence of the route (route availability). Specifically, we derive a simple closed form expression for the computation of the availability of a route, that takes into account node mobility and dependencies between links, which can then be used to satisfy the requirements of multimedia applications. In particular, we show how by efficiently collecting measures about the geographic location of other nodes, each node of an ad hoc network can locally and efficiently compute multiple paths to a given destination node, and, based on the introduced metric, choose the route that best meets the strict requirements of multimedia applications.

This paper introduces MWIS, a distributed algorithm for the efficient determination of a Maximum Weighted Independent Set in the topology graph G of a wireless network. Motivated by the observation that the problem of partitioning wireless nodes into clusters easily reduces to the problem of finding a maximum weighted independent set of nodes, the proposed algorithm is described by taking into account two main characteristic of wireless networks, namely, the broadcast nature of the wireless medium and the possibility to support nodes mobility. MWIS is executed at each node by means of fast message-triggered procedures that require the sole knowledge of the topology local to the node. Moreover, its time complexity is proven to be bounded by the (topology dependent) stability number alpha(G), rather than by the (invariant) number n of the network nodes. Finally, by using a well known results on the stability number in random graphs, we show that the average time complexity of the MWIS is logarithmic in n.

This paper proposes a new routing protocol for ad hoc networks built around the source routing technique combined with the location (e.g., GPS coordinates) of nodes obtained by an energy and distance smart dissemination mechanism. The key new observation used is that the location information provides each node with a snapshot of the topology of the complete network from which a source route may be computed locally rather than through route discovery. The resulting protocol has reduced delay, and is more bandwidth and energy efficient, than both traditional (proactive and reactive) ad hoc routing protocols, as well as location based routing protocols.

A distributed algorithm is presented that partitions the nodes of a fully mobile network (multi-hop wireless network) into clusters, thus giving the network a hierarchical organization. The algorithm is proven to be adaptive to changes in the network topology due to nodes' mobility and to nodes addition/removal. A new weight-based mechanism is introduced for the efficient cluster formation/maintenance that allows the cluster organization to be configured for specific applications and adaptive to changes in the network status, not available in previous solutions. Specifically, new and flexible criteria are defined that allow the choice of the nodes that coordinate the clustering process based on mobility parameters and/or their current status. Simulation results are provided that demonstrate up to an 85% reduction on the communication overhead associated with the cluster maintenance with respect to techniques used in clustering algorithms previously proposed.

A Distributed Clustering Algorithm (DCA) and a Distributed Mobility-Adaptive Clustering (DMAC) algorithm are presented that partition the nodes of a fully mobile network (ad hoc network) into clusters, thus giving the network a hierarchical organization. Nodes are grouped by following a new weight-based criterion that allows the choice of the nodes that coordinate the clustering process based on node mobility-related parameters. The DCA is suitable for clustering ``quasi-static'' ad hoc networks. It is easy to implement and its time complexity is proven to be bounded by a network parameter that depends on the topology of the network rather than on its size, i.e., the invariant number of the network nodes. The DMAC algorithm adapts to the changes in the network topology due to the mobility of the nodes, and it is thus suitable for any mobile environment. Both algorithms are executed at each node with the sole knowledge of the identity of the one hop neighbors, and induce on the network the same clustering structure.

This paper presents a network layer mechanism for the efficient dissemination of Global Positioning System (GPS) based node position in ad hoc networks, and shows its application to problems involving geographic awareness. In particular, we describe how, based on a ``position database'' maintained through the dissemination mechanism, a node of the network can direct messages to all the nodes currently present in a precise geographic area. The effectiveness and accuracy of the dissemination mechanism is demonstrated through the use of simulations. We show that for ad hoc networks with up to 60 nodes, the position database correctly determines which nodes are actually in the expected geographic area the 97% of the time.

This paper describes the use of Time-Spread Multiple-Access (TSMA) protocols for realizing the dissemination (``flooding'') of data and/or control packets in networks characterized by the lack of a fixed infrastructure (ad hoc networks). We show that, due to the unique characteristics of TSMA, namely, that it is independent of the changes in the network topology due to node mobility and it is deterministic, it is effective for implementing and/or supporting those ad hoc networks primitives that are crucial for delay-sensitive applications, such as multimedia. Through the use of simulation, we finally show that the average broadcast delay for TSMA-based flooding remains stable for higher network loads when compared to the average delay of simple TDMA-, Aloha- and Slotted Aloha- based flooding.

An algorithm is presented for designing the logical topology of the virtual path (VP) network, an important task in ATM network design. We prove that the algorithm provides a VP network topology that is asymptotically optimal with respect to both connectivity and the diameter of the network. These optimality properties are combined with algorithmic simplicity and polynomial running time, thus overcoming the notorious ``optimality vs. scalability'' dilemma. This result is made possible by applying the theory of random graphs to this type of networks. This theory has the methodological advantage of increased accuracy with growing network size, thus turning the ``curse of dimensionality'' into a blessing. Therefore, the paper exemplifies that the theory of random graphs, beyond supporting analysis purposes, may serve as a useful tool in the design of algorithms that overcome the ``scalability bottleneck,'' a problem that prevents current approaches from finding near-optimal solutions as today's networks grow in size and complexity.

In this paper we introduce a new routing protocol for ad hoc networks built around two novel observations. One, called the distance effect, uses the fact that the greater the distance separating two nodes, the slower they appear to be moving with respect to each other. Accordingly, the location information in routing tables can be updated as a function of the distance separating nodes without compromising the routing accuracy. The second idea is that of triggering the sending of location updates by the moving nodes autonomously, based only on a node's mobility rate. Intuitively, it is clear that in a directional routing algorithm, routing information about the slower moving nodes needs to be updated less frequently than that about highly mobile nodes. In this way each node can optimize the frequency at which it sends updates to the networks and correspondingly reduce the bandwidth and energy used, leading to a fully distributed and self-optimizing system. Based on these routing tables, the proposed directional algorithm sends messages in the ``recorded direction'' of the destination node, guaranteeing delivery by following the direction with a given probability. We show by detailed simulation that our protocol always delivers more than 80% of the data messages by following the direction computed, without using any recovery procedure. In addition, it minimizes the overhead used for maintaining routes using the two new principles of update message frequency and distance. Lastly, the algorithm is fully distributed, provides loop-free paths, and is robust, since it supplies multiple routes.

Broadcasting (distributing a message from a source to all other nodes) is a fundamental requirement of distributed computing. In this paper we propose deterministic, delivery-guaranteed distributed protocols for solving this problem in wireless networks that have a peer-to-peer (i.e., non-cellular) organization. Deterministic and delivery-guaranteed protocols are defined as solutions which are always executed within an a priori determined period of time, and such that their success does not depend on, or require, collision detection mechanisms. The proposed protocols are distributed in the sense that they can be executed at each node without topology knowledge and, moreover, they do not assume any underlying network architecture. We characterize the broadcast problem as a combinatorial problem for the solution of which we propose here a novel, explicit and completely deterministic method. The derived protocol is proved to complete the broadcast of a message in time that is polylogarithmic in the size n of the network, and we prove that it is optimal for networks with specific topologies.

An algorithm is proposed for efficiently clustering the nodes of a mobile wireless network that has a ``peer-to-peer'' (i.e., non-cellular) organization. The algorithm is a common generalization of different methods proposed for this problem so far in the literature. We define the worst case performance ratio rho of the algorithm in a way that indicates how well the proposed heuristic performs compared to the optimum algorithm. We show that rho is non trivially bounded by a function of the degree of the network. Moreover, we prove that our algorithm is optimal. Specifically, given that NP-complete problems cannot be solved in polynomial time, we show that in an unconstrained topology we cannot devise efficient clustering algorithms that perform better than ours.