HELLO protocol or neighborhood discovery is essential in wireless ad hoc networks. It makes the rules for nodes to claim their existence/aliveness. In the presence of node mobility, no fix optimal HELLO frequency and optimal transmission range exist to maintain accurate neighborhood tables while reducing the energy consumption and bandwidth occupation. Thus a Turnover based Frequency and transmission Power Adaptation algorithm (TFPA) is presented in this paper. The method enables nodes in mobile networks to dynamically adjust both their HELLO frequency and transmission range depending on the relative speed. In TFPA, each node monitors its neighborhood table to count new neighbors and calculate the turnover ratio. The relationship between relative speed and turnover ratio is formulated and optimal transmission range is derived according to battery consumption model to minimize the overall transmission energy. By taking advantage of the theoretical analysis, the HELLO frequency is adapted dynamically in conjunction with the transmission range to maintain accurate neighborhood table and to allow important energy savings. The algorithm is simulated and compared to other state-of-the-art algorithms. The experimental results demonstrate that the TFPA algorithm obtains high neighborhood accuracy with low HELLO frequency (at least 11% average reduction) and with the lowest energy consumption. Besides, the TFPA algorithm does not require any additional GPS-like device to estimate the relative speed for each node, hence the hardware cost is reduced.

In this paper, we address the problem of peer-to-peer networking for data dissemination among actors in wireless sensor and actor networks (WSANs), which consist of static sensors, responsible for environment monitoring, and mobile actors, in charge of data collection and task performing. This problem has not been received much attention although peer-to-peer networking has achieved great successes in other networks such as the Internet and mobile ad hoc networks (MANETs). Unlike the Internet and MANETs, WSANs contain static sensors that are energy-constrained and actors that cannot communicate with each other directly. These unique characteristics make the data dissemination problem in WSANs extremely challenging. We present an Energy-Efficient Message Dissemination protocol (EMD) to solve this problem in delay-tolerant WSANs. EMD is grounded on a novel principle of "Carry-Disseminate-Store-and-Forward" proposed for the first time here. While traveling, a source actor disseminates messages (data) to sensors upon contact, which will store the messages and forward them to other actors when they come into communication range. The actors receiving the messages from sensors work as source actors and help to distribute the messages. We theoretically analyze the data dissemination strategy under which the original source actor can distribute its messages to all other actors at minimum communication cost within a given delay bound. Through extensive simulations we demonstrate the performance of EMD.

The coverage of Points of Interest (PoI) is a classical requirement in mobile wireless sensor applications. Optimizing the sensors self-deployment over a PoI while maintaining the connectivity between the sensors and the base station is thus a fundamental issue. This paper addresses the problem of autonomous deployment of mobile sensors that need to cover a predefined PoI with a connectivity constraint. In our algorithm, each sensor moves toward a PoI but has also to maintain the connectivity with a subset of its neighboring sensors that are part of the Relative Neighborhood Graph (RNG). The Relative Neighborhood Graph reduction is chosen so that global connectivity can be provided locally. Our deployment scheme minimizes the number of sensors used for connectivity thus increasing the number of monitoring sensors. Analytical results, simulation results and practical implementation are provided to show the efficiency of our algorithm.

We propose a radically new family of geometric graphs, i.e., Hypocomb (HC), Reduced Hypocomb (RHC), and Local Hypocomb (LHC). HC and RHC are extracted from a complete graph; LHC is extracted from a Unit Disk Graph (UDG). We analytically study their properties including connectivity, planarity, and degree bound. All these graphs are connected (provided that the original graph is connected) planar. Hypocomb has unbounded degree while Reduced Hypocomb and Local Hypocomb have maximum degree 6 and 8, respectively. To our knowledge, Local Hypocomb is the first strictly localized, degree-bounded planar graph computed using merely 1-hop neighbor position information. We present a construction algorithm for these graphs and analyze its time complexity. Hypocomb family graphs are promising for wireless ad hoc networking. We report our numerical results on their average degree and their impact on FACE routing. We discuss their potential applications and pinpoint some interesting open problems for future research.

In mobile-beacon assisted sensor localization, beacon mobility scheduling aims to determine the best beacon trajectory so that each sensor receives sufficient beacon signals and becomes localized with minimum delay. We propose a novel DeteRministic dynamic bEAcon Mobility Scheduling (DREAMS) algorithm, without requiring any prior knowledge of the sensory field. In this algorithm, the beacon trajectory is defined as the track of Depth-First Traversal (DFT) of the network graph, thus deterministic. The mobile beacon performs DFT dynamically, under the instruction of nearby sensors on the fly. It moves from sensor to sensor in an intelligent heuristic manner according to Received Signal Strength (RSS)-based distance measurements. We prove that DREAMS guarantees full localization (every sensor is localized) when the measurements are noise-free, and derive the upper bound of beacon total moving distance in this case. Then, we suggest to apply node elimination and Local Minimum Spanning Tree (LMST) to shorten beacon tour and reduce delay. Further, we extend DREAMS to multibeacon scenarios. Beacons with different coordinate systems compete for localizing sensors. Loser beacons agree on winner beacons' coordinate system, and become cooperative in subsequent localization. All sensors are finally localized in a commonly agreed coordinate systems. Through simulation we show that DREAMS guarantees full localization even with noisy distance measurements. We evaluate its performance on localization delay and communication overhead in comparison with a previously proposed static path-based scheduling method.

We propose a radically new family of geometric graphs, i.e., Hypocomb, Reduced Hypocomb and Local Hypocomb. The first two are extracted from a complete graph; the last is extracted from a Unit Disk Graph (UDG). We analytically study their properties including connectivity, planarity and degree bound. All these graphs are connected (provided the original graph is connected) planar. Hypocomb has unbounded degree while Reduced Hypocomb and Local Hypocomb have maximum degree 6 and 8, respectively. To our knowledge, Local Hypocomb is the first strictly-localized, degree-bounded planar graph computed using merely 1-hop neighbor position information. We present a construction algorithm for these graphs and analyze its time complexity. Hypocomb family graphs are promising for wireless ad hoc networking. We report our numerical results on their average degree and their impact on FACE routing. We discuss their potential applications and some open problems.

In mobile-beacon assisted sensor localization, beacon mobility scheduling aims to determine the best beacon trajectory so that each sensor receives sufficient beacon signals with minimum delay. We propose a novel DeteRministic bEAcon Mobility Scheduling (DREAMS) algorithm, without requiring any prior knowledge of the sensory field. In this algorithm, beacon trajectory is defined as the track of depth-first traversal (DFT) of the network graph, thus deterministic. The mobile beacon performs DFT under the instruction of nearby sensors on the fly. It moves from sensor to sensor in an intelligent heuristic manner according to RSS (Received Signal Strength)-based distance measurements. We prove that DREAMS guarantees full localization (every sensor is localized) when the measurements are noise-free. Then we suggest to apply node elimination and topology control (Local Minimum Spanning Tree) to shorten beacon tour and reduce delay. Through simulation we show that DREAMS guarantees full localization even with noisy distance measurements. We evaluate its performance on localization delay and communication overhead in comparison with a previously proposed static path based scheduling method.

SensLAB's goal is to provide a very large scale open wireless sensor network testbed, by deploying 1024 nodes over 4 interconnected sites, and to offer a reference tool for the wireless sensor network community. Our demonstration purpose is to illustrate what the SensLAB1platform offers through a case study: an animal tracking application needing routing and mobile node geolocalization. Through this example, we will show how to run an application in the large scale testbed SensLAB and some of the tools it provides to help in developing, tuning and monitoring such a large scale application.

A primary purpose of sensing in a sensor network is to collect and aggregate information about a phenomenon of interest. The batteries on today's wireless sensor barely last a few days, and nodes typically expend a lot of energy in computation and wireless communication. Hence, the energy efficiency of the system is a major issue. Different representative mechanisms has been proposed to achieve a long lived sensors such as “clustering mechanisms” as well as Aggregation techniques to reduce the amount of data communication generated by sensors. Depending on the data type, ARMA series and forecasting are possible ways to reduce data transmission. In this work, we adopt single-hop clustering mechanism where all sensor nodes in a cluster communicate with their Cluster-Head (or sink) via single hop (such as In/On body sensors for personal health monitoring,..). We propose different data aggregation algorithms based on the AutoRegressive model, to predict local readings and reduce the communication traffic. We evaluate the performance of our work in terms of communication cost and energy consumption. We also extend our work to enhance the prediction accuracy by estimating dynamic prediction threshold. Our simulation shows that depending on data type, communication overhead and rate can be reduced and a considerable accuracy prediction can be obtained.

In this paper, we consider the self-deployment of wireless sensor networks. We present a mechanism which allows to preserve network connectivity during the deployment of mobile wireless sensors. Our algorithm is distributed and is based on a subset of neighbours for motion decision. Our algorithm maintains a connected topology regardless of the direction chosen by each sensor. To preserve connectivity, the distance covered by the mobile nodes is constrained by the connectivity of the node to its neighbours in a connected subgraph like the relative neighbourhood graph (RNG). We show the connectivity preservation property of our algorithm through analysis and present some simulation results for the full coverage problem.

In the anycasting problem, a sensor wants to report event information to one of sinks or actors. We describe the first localized anycasting algorithms that guarantee delivery for connected multi-sink sensor-actor networks. Let S(x) be the closest actor/sink to sensor x, and |xS(x)| be distance between them. In greedy phase, a node s forwards the packet to its neighbor v that minimizes the ratio of cost cost(|sv|) of sending packet to v (here we specifically apply hop-count and power consumption metrics) over the reduction in distance (|sS(s)|-|vS(v)|) to the closest actor/sink. A variant is to forward to the first neighbor on the shortest weighted path toward v. If none of neighbors reduces that distance then recovery mode is invoked. It is done by face traversal toward the nearest connected actor/sink, where edges are replaced by paths optimizing given cost. A hop count based and two variants of localized power aware anycasting algorithms are described. We prove guaranteed delivery property analytically and experimentally.

We describe how to build a relative neighborhood graph on a real network without any positioning system. We base the computation of the RNG on a RSSI weight function and show how to adapt transmission power to the resulting graph.

We propose a localized sensor localization scheme making full use of controlled mobility of a location-aware actor and the connectivity of the sensor network. It contains two new algorithms: a unscented particle filter (UPF) based localization algorithm and an actor mobility scheduling algorithm. The former is an application of UPF. It enables sensor self-localization using received signal strength indicator and actor position. The latter models actor mobility scheduling as traveling salesman problem and aims at fully localized network and minimized time delay. Navigated by sensors, the actor depth-first traverses a local minimum spanning tree of a connected 3-dominating set of the network.

We study the minimum range assignment problem that consists in finding the range assignment that minimizes energy consumption in the network. We exhibit one bad behavior of classical graph reduction-based approaches: they only consider the sum of edges' weight as an optimization criterion. We then design a new graph reduction algorithm (the minimum power tree protocol) and its associated topology control algorithm (the incremental power topology control protocol). After proposing a local version of the protocol, we evaluate and compare their performance of these two protocols to the studied classical reduction-based approaches.

We propose several localized algorithms to achieve energy-efficient broadcasting in wireless multihop networks using directional antennas. Each node needs to know only geographic position of itself and its neighbors. Our first protocol is called DRBOP and it follows the one-to-one communication model to reach to all nodes in the relative neighborhood graph (RNG). Each node that receives a message for the first time from one of its RNG neighbors will rebroadcast it to each of its remaining RNG neighbors separately. The transmission power is adjusted for each transmission to the minimal necessary for reaching the particular neighbor. Next, we describe DLBOP, where RNG is replaced by the localized minimum spanning tree (LMST) graph which is a localized topology resembling the minimum spanning tree. We then observe that, for very dense networks, it is more energy-efficient to reach more than one neighbor at a time. A one-to-many protocol efficient for dense networks is proposed. We then describe an efficient localized protocol which adaptively switches (without any threshold) between one-to-one and one-to-many communication models and is efficient for both sparse and dense networks. Our simulation results show that for different energy models, the adaptive protocol is able to achieve a competitive performance to globalized algorithms while having a fully localized operation.

This paper considers the problem of designing power efficient routing with guaranteed delivery for sensor networks with known distances between neighbors but unknown geographic locations. We propose Hector, a hybrid energy efficient tree-based optimized routing protocol, based on two sets of virtual coordinates. One set is based on rooted tree coordinates, and the other is based on hop distances toward several landmarks. In our algorithm, the node currently holding the packet forwards it to its neighbor that optimizes ratio of power cost over distance progress with landmark coordinates, among nodes that reduce landmark coordinates and do not increase tree coordinates. If such a node does not exist then forwarding is made to the neighbor that reduces tree based distance and optimizes power cost over tree distance progress ratio. Our simulations show the superiority of our algorithm over existing alternatives while guaranteeing delivery, and only up to 30% additional power compared to centralized shortest weighted path algorithm.

We propose a novel localized routing protocol for wireless sensor networks (WSN) that is energy-efficient and guarantees delivery. We prove that it is constant factor of the optimum for dense networks. To forward a packet, a node s in graph G computes the cost of the energy weighted shortest path (SP) between s and each of its neighbors which are closer to the destination than itself. It then selects node x which minimizes the ratio of the cost of the SP to the progress towards the destination. It then sends the message to the first node on the SP from s to x: say node x'. Node x' restarts the same greedy routing process until the destination is reached or the routing fails. To recover from failure, our algorithm invokes face routing that guarantees delivery. This work is the first to optimize energy consumption of face routing. First, we build a connected dominating set from graph G, second we compute its Gabriel graph to obtain the planar graph G'. Face routing is applied on G' only to decide which edges to follow in the recovery process. On each edge, greedy routing is used. This two-phase (greedy-Face) end-to-end routing process (EtE) reiterates until the final destination is reached. Simulation results show that EtE outperforms several existing geographical routing on energy consumption metric.

We present a localized geographic multicast scheme, MSTEAM, based on the construction of local minimum spanning trees (MSTs), that requires information only on 1-hop neighbors. A message replication occurs when the MST spanning the current node and the set of destinations has multiple edges originated at the current node. Destinations spanned by these edges are grouped together, and for each of these subsets the best neighbor is selected as the next hop. This selection is based on a cost over progress metric, where the progress is approximated by subtracting the weight of the MST over a given neighbor and the subset of destinations to the weight of the MST over the current node and the subset of destinations. Since such greedy scheme may lead the message to a void area (i.e., no neighbor providing positive progress), we propose a new multicast generalization of the well-known face recovery mechanism. We provide a theoretical analysis proving that MSTEAM is loop-free, and achieves delivery of the multicast message as long as a path to the destinations exists. Our results demonstrate that MSTEAM outperforms the best existing localized multicast scheme, and is almost as efficient as a centralized scheme in high densities.

We propose several localized sensor area coverage protocols for heterogeneous sensors, each with arbitrary sensing and transmission radii. Sensors are assumed to be time synchronized, and active sensors are determined at the beginning of each round. The approach has a very small communication overhead since prior knowledge about neighbor existence is not required. Each node selects a random timeout and listens to messages sent by other nodes before the timeout expires. Sensor nodes whose sensing area is not fully covered (or fully covered but with a disconnected set of active sensors) when the deadline expires decide to remain active for the considered round, and transmit an activity message announcing it. There are four variants in our approach, depending on whether or not withdrawal and retreat messages are transmitted. Covered nodes decide to sleep, with or without transmitting withdrawal message to inform neighbors about the status. After hearing from more neighbors, active sensors may observe that they became covered, and may decide to alter their original decision and transmit a retreat message. Our simulation shows reduced message overhead while preserving coverage quality compared to existing method based on hello messages followed by retreat ones.

The IEEE 802.11 standard for wireless local area networks (WLANs) employs a mechanism for medium access control (MAC), named distributed coordination function (DCF), which is based on carrier sense multiple access with collision avoidance (CSMA/CA). The collision avoidance mechanism uses the random backoff prior to each frame transmission attempt. The random nature of the backoff reduces the collision probability, but cannot eliminate completely these collisions. It is well known that as the number of contending stations increases, the number of collisions is also likely to increase and the performance of the 802.11 WLAN is significantly compromised. In this paper, we propose a novel distributed MAC protocol, named reduced collision MAC (RC-MAC). In our algorithm, a station access the channel by following a cyclic method. After a certain period of contention resolution, the stations simply organized in a cycle and each of them will access the channel while its turn comes. In this case, there is no more collision in the future and the bandwidth is used efficiently. Through extensive simulations, we show that RC-MAC achieves a significant increase in the overall performance compared to the standard 802.11 DCF.

We consider the problem of activity scheduling and area coverage in sensor networks, and especially focus on problems that arise when using a more realistic physical layer. Indeed, most of the previous work in this area has been studied within an ideal environment, where messages are always correctly received. In this paper, we argue that protocols developed with such an assumption can hardly provide satisfying results in a more realistic world. To show this, we replace the classic unit disk graph model by the lognormal shadowing one. The results show that either the resulting area coverage is not sufficient or the percentage of active nodes is very high. We thus present an original method, where a node decides to turn off when there exists in its vicinity a sufficiently reliable covering set of neighbors. We show that our solution is very efficient as it preserves area coverage while minimizing the quantity of active nodes.

We present a turnover based adaptive HELLO protocol (TAP), which enables nodes in mobile networks to dynamically adjust their HELLO messages frequency depending on the current speed of nodes. To the best of our knowledge, all existing solutions are based on specific assumptions (e.g., slotted networks) and/or require specific hardware (e.g., GPS) for speed evaluation. One of the key aspects of our solution is that no additional hardware is required since it does not need this speed information. TAP may be used in any kind of mobile networks that rely on HELLO messages to maintain neighborhood tables and is thus highly relevant in the context of ad hoc and sensor networks. In our solution, each node has to monitor its neighborhood table to count new neighbors whenever a HELLO is sent. This turnover is then used to adjust HELLO frequency. To evaluate our solution, we propose a theoretical analysis based on some given assumptions that provides the optimal turnover when these assumptions hold. Our experimental results demonstrate that when this optimal value is used as the targeted turnover in TAP, the HELLO frequency is correctly adjusted and provides a good accuracy with regards to the neighborhood tables.

For low-energy, low-throughput Wireless Sensor Networks, geographic forwarding avoids creating and maintaining a structure using clustering or gradient construction. Yet, geographic forwarding assumes position-awareness, which may be not realistic. In this paper, we propose to use virtual coordinates. Each node determines its [x,y] position in a virtual space based on a random or pseudo-random process. It uses these coordinates to route information with geographical-inspired routing protocols. Extensive simulation shows that this approach can be very efficient for low-throughput WSN.

We propose an energy efficient routing protocol, VCost, for sensor networks. We assume that nodes are unaware of their geographic location thus, VCost assigns virtual coordinates to nodes as follows. Based on the node hop count distances from a set of landmarks, our method computes a distance metric to obtain the node's virtual coordinates. VCost, then uses these coordinates to route packets from node u to node v, in its neighborhood, such that the ratio of the cost to send a message to v to the progress in the routing task towards the destination is minimized. Compared to existing algorithms that use virtual locations, our simulation shows that VCost improves significantly energy consumption and preserves the small percentage of successful routings.

Using beam forming antennas and ULB modulations in ad hoc networks have been recently focused on, as they allow to drastically improve ad-hoc network performances. This new technological context implies revisiting common network algorithms. When considering an multi-sector antenna uncommon with an uncommon high switch delay, packets have to be efficiently scheduled on beams at the MAC layer level, in order to improve the network capacity. We consider two optimization criteria: the network throughput and the maximum delay of packets. This paper proposes and studies a MAC scheduler, FIFO TBW, efficiently reducing the overhead due to beam switching delays. We give a first approach to estimate the window duration parameter

We propose several localized sensor area coverage protocols, for arbitrary ratio of sensing and transmission radii. Sensors are assumed to be time synchronized, and active sensors are determined at the beginning of each round. The approach has a very small communication overhead since prior knowledge about neighbor existence is not required. Each node selects a random timeout and listens to messages sent by other nodes before the timeout expires. Sensor nodes whose sensing area is not fully covered (or fully covered but with a disconnected set of active sensors) when the deadline expires decide to remain active for the considered round, and transmit a message announcing their activity status. There are four variants in our approach, depending on whether or not negative and retreat messages are transmitted. Experimental results with ideal MAC layer show that, for a similar number of selected active sensors, our methods significantly reduce number of messages to decide activity compared to existing localized protocol, we also consider a MAC layer with collisions, and show that existing compared method, for dense networks, fails to cover the area reasonably. Our methods, however, still remain robust in terms of high area coverage with reasonable amount of active nodes, despite some message collisions.

We investigate the problem of minimum energy broadcasting in ad hoc networks where nodes have capability to adjust their transmission range. The minimal transmission energy needed for correct reception by neighbor at distance r is proportional to r/sup /spl alpha//+c/sub e/, /spl alpha/ and c/sub e/ being two environment-dependent constants. We demonstrate the existence of an optimal transmission radius, computed with a hexagonal tiling of the network area, that minimizes the total power consumption for a broadcasting task. This theoretically computed value is experimentally confirmed. The existing localized protocols are inferior to existing centralized protocols for dense networks. We present two localized broadcasting protocols, based on derived "target" radius, that remain competitive for all network densities. The first one, TR-LBOP, computes the minimal radius needed for connectivity and increases it up to the target one after having applied a neighbor elimination scheme on a reduced subset of direct neighbors. In the second one, TRDS, each node first considers only neighbors whose distance is no greater than the target radius (which depends on the power consumption model used), and neighbors in a localized connected topological structure such as RNG or LMST. Then, a connected dominating set is constructed using this subgraph. Nodes not selected for the set may be sent to sleep mode. Nodes in selected dominating set apply TR-LBOP. This protocol is the first one to consider both activity scheduling and minimum energy consumption as one combined problem. Finally, some experimental results for both protocols are given, as well as comparisons with other existing protocols. Our analysis and protocols remain valid if energy needed for packet receptions is charged.

1 THE SCOPE WE are very proud and honored to have been entrusted to guest edit this special section. The main goal was to put together a strong issue emphasizing quality and relevance to current interests in this important field. Papers were sought to cover comprehensively the algorithmic issues in the “hot” area of ad hoc and sensor networking. The concentration was on the network layer problems which can be divided into two groups: data communication and topology control problems. In data communication problems, such as routing, quality-of-service routing, geocasting, multicasting, and broadcasting, the primary goal is to fulfill a given communication task successfully between nodes in an ad hoc network. The secondary task is to minimize the communication overhead and power consumption given that in the vast majority of applications nodes run on batteries. Topology control problems are further subdivided into neighbor discovery and network organization problems. In the neighbor discovery problem, the problem is to detect neighboring nodes located within transmission range. In the network organization problem, each node should decide what communication links to establish with neighboring nodes (an example is the Bluetooth scatternet formation problem), and what power management schemes to adopt (examples are “sleep” period operations and adjusting transmission ranges). Due to their theoretical challenges and myriads of practical applications, wireless sensor networks are emerging as one of the priority research and development areas. The applications of sensor networks are envisioned primarily for monitoring the environment (e.g., motion detection, chemicals, temperature) or as key components in embedded systems (e.g., biomedical sensor engineering). This special section also sought submissions on this “hot” topic, including problems such as: physical properties, sensor training, security through intelligent node cooperation, medium access, sensor area coverage with random and deterministic placement, object location, sensor position determination, energy efficient broadcasting and activity scheduling, routing, connectivity, data dissemination and gathering, sensor centric quality of routing, path exposure, tree reconfiguration, topology construction, and transport layer. The main paradigm shift is to apply localized schemes as opposed to existing protocols requiring global information. Localized algorithms are distributed algorithms where simple local node behavior achieves a desired global objective. Localized protocols provide scalable solutions, that is, solutions for wireless networks with an arbitrary number of nodes, which is the main goal of this plan. Sensor and rooftop/mesh networks, for instance, have hundreds or thousands of nodes.

Sensor networks consist of autonomous nodes with limited battery and of base stations with theoretical infinite energy. Nodes can be sleep to extend the lifespan of the network without compromising neither area coverage nor network connectivity. This paper addresses the area coverage problem with equal sensing and communicating radii. The goal is to minimize the number of active sensors involved in coverage task, while computing a connected set able to report to monitoring stations. Our solution is fully localized, and each sensor is able to make decision on whether to sleep or to be active based on two messages sent by each sensor. The first message is a "hello" message to gather position of all neighboring nodes. Then each node computes its own relay area dominating set, by taking the furthest neighbor as the first node, and then adding neighbors farthest to the isobarycenter of already selected neighbors, until the area covered by neighbors is fully covered. The second message broadcasts this relay set to neighbors. Each node decides to be active if it has highest priority among its neighbors or is a relay node for its neighbor with the highest priority.

As broadcasting is widely used for miscellaneous maintenance operations in wireless ad hoc networks, where energy is a scarce resource, an efficient broadcasting protocol is of prime importance. One of the best known algorithm, named BIP (broadcast incremental power), constructs a spanning tree rooted at a given node. This protocol offers very good results in terms of energy savings, but its computation is unfortunately centralized, as the source node needs to know the entire topology of the network to compute the tree. Many localized protocols have since been proposed, but none of them has ever reached the performances of BIP. Even distributed versions of the latter have been proposed, but they require a huge transmission overhead for information exchange and thus waste energy savings obtained thanks to the efficiency of the tree, in this paper, we propose and analyze a localized version of this protocol. In our method, each node is aware of the position of all the hosts in the set of its 2-hop neighborhood and compute the BIP tree on this set, based on information provided by the node from which it got the packet. That is, a tree is incrementally built thanks to information passed from node to node in the broadcast packet. Only the source node computes an initially empty tree to initiate the process. We also provide experimental results showing that this new protocol has performances very close to other good ones for low densities, and is very energy-efficient for higher densities with performances that equal the ones of BIP.

We investigate minimum energy broadcasting problem where mobile nodes have the capability to adjust their transmission range. The power consumption for two nodes at distance r is r/sup /spl alpha// + c, where /spl alpha/ /spl ges/ 2 and c is a constant that includes signal processing and minimal reception power. We show that, for c > 0 (which is realistic assumption), it is not optimal to minimize transmission range. Furthermore, we demonstrate that there exists an optimal radius, computed with a hexagonal tiling of the network area that minimizes the power consumption. For /spl alpha/ > 2 and c > 0, the optimal radius is r = /spl alpha//spl radic/(2c//spl alpha/-2), which is derived theoretically, and confirmed experimentally. We propose also a localized broadcast algorithm TR-LBOP that takes this optimal radius into account. This protocol is experimentally shown to be efficient compared to existing localized protocol LBOP and globalized BIP protocol. Most importantly, TR-LBOP is shown to have limited energy overhead with respect to BIP for all network densities, which is not the case with LBOP whose overhead explodes for higher densities.

In the minimum energy broadcasting problem, each node can adjust its transmission power in order to minimize total energy consumption but still enable a message originated from a source node to reach all the other nodes in an ad-hoc wireless network. In all existing solutions each node requires global network information (including distances between any two neighboring nodes in the network) in order to decide its own transmission radius. We describe a new localized protocol where each node requires only the knowledge of its distance to all neighboring nodes and distances between its neighboring nodes (or, alternatively, geographic position of itself and its neighboring nodes). In addition to using only local information, our protocol is shown experimentally to be comparable to the best known globalized BIP solution. Our solutions are based on the use of relative neighborhood graph, which preserves connectivity and is defined in localized manner.