In this paper, we propose a general framework of the iterative local solution (ILS) for computing a connected dominating set (CDS) in ad hoc wireless networks, which include mobile ad hoc networks (MANETS) and wireless sensor networks (WSNs). This approach uses an iterative application of a selected local solution. Each application of the local solution enhances the result obtained from the previous iteration, but each is based on a different node priority scheme. Then, we integrate this iterative process into the process for handling a dynamic network topology and propose two extensions: cyclic iterative local solution (CILS) and seamless iterative local solution (SILS). CILS offers a natural extension of ILS to the dynamic environment but suffers from a broken CDS and nonadaptiveness. With a novel use of a monotonically increasing sequence number for dynamic node priority, SILS offers an extension with the desirable properties of correctness, progressiveness, locality, and seamlessness. Extensive simulations are conducted under ns-2 and a custom simulator to evaluate the effectiveness of the proposed approach in both static and dynamic environments.

In this paper, we consider the issue of constructing an energy-efficient virtual network backbone in mobile ad hoc networks (MANETs) for broadcasting applications using directional antennas. In directional antenna models, the transmission/reception range is divided into several sectors and one or more sectors can be switched on for transmission. Therefore, data forwarding can be restricted to certain directions (sectors), and both energy consumption and interference can be reduced. We develop the notation of directional network backbone using the directional antenna model, and form the problem of the directional connected dominating set (DCDS) which is an extreme case of the directional network backbone using an unlimited number of directional antennas. The minimum DCDS problem is proved to be NP-complete. A localized heuristic algorithm for constructing a small DCDS and two extensions of the algorithm are proposed. Performance analysis includes an analytical study in terms of an approximation ratio and a simulation study on the proposed algorithms using both a custom simulator and ns2.

Abstract Sensor nodes are powered by battery and have severe energy constraints. The typical many‐to‐one traffic pattern causes uneven energy consumption among sensor nodes, that is, sensor nodes near the base station or a cluster head have much heavier traffic burden and run out of power much faster than other nodes. The uneven node energy dissipation dramatically reduces sensor network lifetime. In a previous work, we presented the chessboard clustering scheme to increase network lifetime by balancing node energy consumption. To achieve good performance and scalability, we propose to form a heterogeneous sensor network by deploying a few powerful high‐end sensors in addition to a large number of low‐end sensors. In this paper, we design an efficient routing protocol based on the chessboard clustering scheme, and we compute the minimum node density for satisfying a given lifetime constraint. Simulation experiments show that the chessboard clustering‐based routing protocol balances node energy consumption very well and dramatically increases network lifetime, and it performs much better than two other clustering‐based schemes. Copyright © 2006 John Wiley & Sons, Ltd.

Abstract Many data‐gathering protocols for wireless sensor networks use clustering technology for prolonging network lifetime. Cluster‐based protocols reduce the total energy consumption via data aggregation and balance energy consumption via clusterhead rotation. However, most existing protocols focus on load balance within each cluster. The energy consumption of the entire network is still unbalanced and this uneven energy dissipation can significantly reduce network lifetime. We propose an even energy dissipation protocol (EEDP) for efficient cluster‐based data gathering in wireless sensor networks. In EEDP, sensor data are forwarded to the base station (BS) via multiple chains of clusterheads. Each chain uses a rotation scheme to balance energy consumption among clusterheads and avoid the formation of a hot spot. We developed efficient algorithms to organize clusterheads into multiple chains, such that the traffic load is evenly distributed among different chains. Analysis and simulation results show that EEDP achieves better load balance than several existing protocols and significantly increases network lifetime. Copyright © 2007 John Wiley & Sons, Ltd.

In this paper, we consider the issue of constructing an energy-efficient virtual network backbone in mobile ad hoc networks (MANETs) for broadcasting applications using directional antennas. In directional antenna models, the transmission/reception range is divided into several sectors and one or more sectors can be switched on for transmission. Therefore, data forwarding can be restricted to certain directions (sectors), and both energy consumption and interference can be reduced. We develop the notation of directional network backbone using the directional antenna model, and form the problem of the directional connected dominating set (DCDS) which is an extreme case of the directional network backbone using an unlimited number of directional antennas. The minimum DCDS problem is proved to be NP-complete. A localized heuristic algorithm for constructing a small DCDS is proposed. Performance analysis includes an analytical study in terms of an approximation ratio and a simulation study on the proposed algorithms using a custom simulator.

Two schools of thought exist in terms of handling mobility in mobile ad hoc networks (MANETs). One is the traditional connection-based model, which views node mobility as undesirable and tries to either remove (through recovery schemes) or mask (through tolerant schemes) the effect of mobility. The other is the mobility-assisted model, which considers mobility as a desirable feature, where routing is based on the store-carry-forward paradigm with random or controlled movement of mobile nodes (called ferries). It is well known that mobility increases the capacity of MANETs by reducing the number of relays in routing. Surprisingly, only two models, diameter hop count in the connection-based model and constant hop count in the mobility-assisted model, which correspond to two extremes of the spectrum, have been systematically studied. In this paper, we propose a new routing model that deals with message routing, as well as trajectory planning, of the ferries that carry the message. A logarithmic number of relays are enforced to achieve a good balance among several contradictory goals, including increasing network capacity, increasing ferry sharing, and reducing moving distance. The model considers the dynamic control of ferries in terms of the number of ferries, trajectory planning of ferries, and node communication and synchronization. The effectiveness of the proposed model is evaluated analytically, as well as through simulation

Many data gathering protocols for wireless sensor networks use clustering technology for prolonging the network lifetime. Cluster-based protocols reduce the total energy consumption via data aggregation, and balance energy consumption via clusterhead rotation. However, most existing protocols focus on load balance within each cluster. The energy consumption of the entire network is still unbalanced, and this uneven energy dissipation can significantly reduce the network lifetime. We propose an even energy dissipation protocol (EEDP) for efficient cluster-based data gathering in wireless sensor networks. In EEDP, the sensor data are forwarded to the base station via multiple chains of clusterheads. Each chain uses a rotation scheme to balance energy consumption among clusterheads and avoid the formation of a hot spot. We developed efficient algorithms to organize clusterheads into multiple chains, such that the traffic load is evenly distributed among different chains. Analysis and simulation results show that EEDP achieves better load balance than several existing protocols and significantly increases network lifetime

In a wireless sensor network (WSN), the sensor distribution is vital to the quality of service (QoS) of the network, because the effectiveness of the network depends on the coverage of the monitoring area. In WSNs where sensors have locomotion facilities, after the initial deployment, the sensors can move around and self-redeploy to ensure global coverage and load balance. The movement-assisted sensor deployment aims at moving sensors to meet coverage and load balance requirements. In this paper, we focus on developing a distributed and localized solution, approximating the global optimal solution. The proposed local solution has similar performance to the Hungarian method, without centralized control. Extensive theoretical analysis together with simulations has been done to verify the effectiveness of the proposed distributed solutions

Multipoint relays (MPR) provide a localized and optimized way of broadcasting messages in a mobile ad hoc network (MANET). Using partial 2-hop information, each node chooses a small set of forward neighbors to relay messages and this set covers the node's 2-hop neighbor set. These selected forward nodes form a connected dominating set (CDS) to ensure full coverage. Adjih et al. later proposed a novel extension of MPR to construct a small CDS and it is source-independent. In this paper, we provide several extensions to generate a smaller CDS using complete 2-hop information to cover each node's 2-hop neighbor set. We extend the notion of coverage in the original MPR. We prove that the extended MPR has a constant local approximation ratio compared with a logarithmic local ratio in the original MPR. In addition, we show that the extended MPR has a constant global probabilistic approximation ratio, while no such ratio exists in the original MPR and its existing extensions. The effectiveness of our approach is confirmed through a simulation study.

Recently, the use of a virtual backbone in various applications in mobile ad hoc networks (MANETs) has become popular. These applications include topology management, point and area coverage, and routing protocol design. In a MANET, one challenging issue is to construct a virtual backbone in a distributed and localized way while balancing several conflicting objectives: small approximation ratio, fast convergence, and low computation cost. Many existing distributed and localized algorithms select a virtual backbone without resorting to global or geographical information. However, these algorithms incur a high computation cost in a dense network. In this paper, we propose a distributed solution based on reducing the density of the network using two mechanisms: clustering and adjustable transmission range. By using adjustable transmission range, we also achieve another objective, energy-efficient design, as a by-product. As an application, we show an efficient broadcast scheme where nodes (and only nodes) in a virtual backbone are used to forward the broadcast message. The virtual backbone is constructed using Wu and Li's marking process (1999) and the proposed density reduction process. The application of the density reduction process to other localized algorithms is also discussed. The efficiency of our approach is confirmed through both analytical and simulation study

Using directional antennas to conserve bandwidth and energy consumption in ad hoc wireless networks (or simply ad hoc networks) is becoming popular. However, applications of directional antennas for broadcasting have been limited. We propose a novel broadcast protocol called directional self-pruning (DSP) for ad hoc wireless networks using directional antennas. DSP is a nontrivial generalization of an existing localized deterministic broadcast protocol using omnidirectional antennas. Compared with its omnidirectional predecessor, DSP uses about the same number of forward nodes to relay the broadcast packet, while the number of forward directions that each forward node uses in transmission is significantly reduced. With the lower broadcast redundancy, DSP is more bandwidth and energy-efficient. DSP is based on 2-hop neighborhood information and does not rely on location or angle-of-arrival (AoA) information. Two special cases of DSP are discussed: the first one preserves shortest paths in reactive routing discoveries; the second one uses the directional reception mode to minimize broadcast redundancy. DSP is a localized protocol. Its expected number of forward nodes is O(1) times the optimal value. An extensive simulation study using both custom and ns2 simulators show that DSP significantly outperforms both omnidirectional broadcast protocols and existing directional broadcast protocols.

We propose a notion of an extended dominating set where each node in an ad hoc network is covered by either a dominating neighbor or several 2-hop dominating neighbors. This work is motivated by cooperative communication in ad hoc networks whereby transmitting independent copies of a packet generates diversity and combats the effects of fading. We first show the NP-completeness of the minimum extended dominating set problem. Then, several heuristic algorithms, global and local, for constructing a small extended dominating set are proposed. These are nontrivial extensions of the existing algorithms for the regular dominating set problem. The application of the extended dominating set in efficient broadcasting is also discussed. The performance analysis includes an analytical study in terms of approximation ratio and a simulation study of the average size of the extended dominating set derived from the proposed algorithms

In most existing localized topology control protocols for mobile ad hoc networks (MANETs), each node selects a few logical neighbors based on location information and uses a small transmission range to cover those logical neighbors. Transmission range reduction conserves energy and bandwidth consumption, while still maintaining network connectivity. However, the majority of these approaches assume a static network without mobility. In a mobile environment network connectivity can be compromised by two types of "bad" location information: inconsistent information, which makes a node select too few logical neighbors, and outdated information, which makes a node use too small a transmission range. In this paper, we first show some issues in existing topology control. Then, we propose a mobility-sensitive topology control method that extends many existing mobility-insensitive protocols. Two mechanisms are introduced: consistent local views that avoid inconsistent information and delay and mobility management that tolerate outdated information. The effectiveness of the proposed approach is confirmed through an extensive simulation study

In localized topology control protocols for mobile ad hoc networks (MANETs), each node selects a few logical neighbors from its 1-hop neighbors based on its local view, constructed by exchanging periodical "Hello" messages among neighbors, and uses a small transmission range to cover those logical neighbors. Transmission range reduction conserves energy and bandwidth consumption, while still maintaining the network connectivity. However, our recent study showed that the majority of localized topology control protocols are unable to maintain connectivity in MANETs, due to network dynamics such as node mobility. One challenging problem involved is to construct consistent local views for the selection of a correct set of logical neighbors. All existing methods that enforce consistent local views require a certain degree of global synchronization. In this paper, we propose a new mobility management mechanism called weak consistency to address this problem. Compared with previous consistency schemes, this new mechanism requires no inter-nodal coordination and incurs no extra overhead. We show that a wide range of localized topology control protocols can be enhanced to ensure correct decisions based on local views that are weakly consistent. It is also proved that two recent "Hello" messages from each node are sufficient to construct weakly consistent local views, when each node updates its local views instantaneously, and three recent "Hello" messages are enough when each node updates its local view once per "Hello" interval.

This paper presents a new routing scheme for wireless ad hoc networks that provides fresh routing information along active routes with affordable cost. The proposed routing mechanism, called proactive route maintenance (PRM), is used to replace the naive route mechanism in existing reactive (on-demand) routing protocols to improve reliability and reduce route discovery cost. The assumption behind PRM is the communication locality, i.e., most data packets are transported along a few active routes. Data packets are forwarded via multiple optimal paths to meet certain QoS requirements, such as fault tolerance and load balance. Routing information is disseminated along active routes and advertised only by active nodes that forward data packets. Alternative paths are dynamically discovered and maintained by active nodes and their 1-hop neighbors (called passive nodes). The routing overhead in passive nodes is light. PRM maintains reliable end-to-end connections in dynamic networks with low overhead, and has the desirable properties including high delivery ratio, low latency, fair load distribution, self-healing, and self-optimization.

We propose a general framework of the iterative local solution (ILS) for computing a connected dominating set (CDS) in ad hoc wireless networks, which include wireless sensor networks (WSNs) and mobile ad hoc networks (MANETs). This approach uses an iterative application of a selected local solution. Each application of the local solution enhances the result obtained from the previous iteration, but each is based on a different node priority scheme. Then, we integrate this iterative process into the process for handling dynamic network topology and propose two extensions: cyclic iterative local solution (CILS) and seamless iterative local solution (SILS). CILS offers a natural extension of ILS to the dynamic environment, but suffers from broken CDS and non-adaptiveness. With a novel use of a monotonically increasing sequence number for dynamic node priority, SILS offers an extension with the desirable properties of correctness, progressiveness, locality, and seamlessness. Extensive simulations are conducted to evaluate the effectiveness of the proposed approach in both static and dynamic environments

We consider a wireless sensor network consisting of a set of sensors deployed randomly. A point in the monitored area is covered if it is within the sensing range of a sensor. In some applications, when the network is sufficiently dense, area coverage can be approximated by guaranteeing point coverage. In this case, all the points of wireless devices could be used to represent the whole area, and the working sensors are supposed to cover all the sensors. Many applications related to security and reliability require guaranteed k-coverage of the area at all times. In this paper, we formalize the k-(connected) coverage set (k-CCSlk-CS) problems, develop a linear programming algorithm, and design two non-global solutions for them. Some theoretical analysis is also provided followed by simulation results

We study an efficient broadcast scheme in mobile ad hoc networks (MANETs). The objective is to determine a small set of forward nodes to ensure full coverage. We first study several methods that guarantee coverage when the local view of each node on its neighborhood information is updated in a timely manner. Then we consider a general case where nodes move even during the broadcast process, making it impractical to maintain up-to-date and consistent local views. A formal framework is used to model inaccurate local views in MANETs, where full coverage is guaranteed if three sufficient conditions, connectivity, link availability, and consistency, are met. Three solutions are proposed to satisfy those conditions. First, we give a minimal transmission range that maintains the connectivity of the virtual network constructed from local views. Then, we use two transmission ranges, one for neighborhood information collection and the other for actual data transmission, to form a buffer zone that guarantees the availability of logical links in the physical network. Finally, we propose a mechanism called aggregated local view to ensure consistent local views. By these, we extend Wu and Dai's coverage condition for broadcasting in a network with mobile nodes. The effectiveness of the proposed scheme is confirmed via both performance analysis and simulation study.

Recently, the use of a virtual backbone (connected dominating set) in various applications in mobile ad hoc networks (MANETs) has become popular. These applications include topology management, point and area coverage, and routing protocol design. In a mobile environment such as a MANET, one challenging issue in constructing a virtual backbone is to accomplish a distributed and localized solution that aims at balancing several contradicting objectives: small approximation ratio, fast convergence, and low computation cost. Many existing distributed and localized algorithms select a virtual backbone without resorting to global or geographical information. However, these algorithms incur a high computation cost in a dense network. In this paper, we propose a distributed solution based on reducing the density of the network using two mechanisms: clustering and adjustable transmission range. By using adjustable transmission range, we also achieve another objective, energy-efficient design, as a by-product. As an application, we show an efficient broadcasting where nodes (and only nodes) in a virtual backbone are used to forward the broadcast message. The virtual backbone is constructed using Wu and Li's marking process [J. Wu et al., (1999)] and the proposed density reduction process. The application of the density reduction process to other localized algorithms is also discussed. The efficiency of our approach is confirmed through both analytic and simulation study.

With the development and application of position devices, location-based routing has received growing attention. However, little study has been done on QoS routing with the aid of location information. The existing location-based routing approaches, such as flooding-based routing schemes and localized routing schemes, have their limitations. Motivated by ticket-based routing, we propose an on-demand location-aided, ticket-based QoS routing protocol (LTBR). Two special cases of LTBR, LTBR-1 and LTBR-2, are discussed in detail. LTBR-1 uses a single ticket to find a route satisfying a given QoS constraint. LTBR-2 uses multiple tickets to search valid routes in a limited area. All tickets are guided via both location and QoS information. LTBR has lower overhead compared with the original ticket-based routing, because it does not rely on an underlying routing table. On the other hand, LTBR can find routes with better QoS qualities than traditional location-based protocols. Our simulation results show that LTBR-1 can find high quality routes in relatively dense networks with high probability and very low overhead. In sparse networks, LTBR-2 can be used to enhance the probability of finding high quality routes with acceptable overhead.

We study an efficient broadcast scheme in mobile ad hoc networks (MANETs). The objective is to determine a small set of forward nodes to ensure full coverage. We first study several methods to select a small forward node set assuming that the neighborhood information can be updated in a timely manner. Then we consider a general case, where each node updates its neighborhood information based asynchronously on a predefined frequency and node move even during the broadcast process. The virtual network constructed from local views of nodes may not be connected, its links may not exist in the physical network, and the global view constructed from collection of local views may not be consistent. In this paper, we first give a sufficient condition for connectivity at the physical network to ensure the connectivity at the virtual network. We then propose a solution using two transmission ranges to address the link availability issue. The neighborhood information as well as the forward node set are determined based on a short transmission range while the broadcast process is done on a long transmission range. The difference between these two ranges is based on the update frequency and the speed of node movement. Finally, we propose a mechanism called aggregated local view to ensure consistency of the global view. By these, we extend Wu and Dai's coverage condition for broadcasting in a network with mobile nodes. The simulation study is conducted to evaluate the coverage of the proposed scheme.

Summary form only given. In most existing localized topology control protocols for mobile ad hoc networks (MANETs), each node selects a few logical neighbors based on location information, and uses a small transmission range to cover those logical neighbors. Transmission range reduction conserves energy and bandwidth consumption, while still maintaining the network connectivity. However, the majority of these approaches assume a static network without mobility. In a mobile environment, however, network connectivity can be compromised by two types of "bad" location information: inconsistent information, which makes a node select too few logical neighbors, and outdated information, which makes a node use too small a transmission range. We first demonstrate the existing problems, and then propose a mobility-sensitive topology control method that extends many existing mobility-insensitive protocols. Two mechanisms are introduced: consistent local views that avoid inconsistent information, and delay and mobility management that tolerate outdated information. The effectiveness of the proposed approach is confirmed through an extensive simulation study.

Self-pruning is an effective method to reduce broadcast redundancy in ad hoc wireless networks. Unlike flooding, in a self-pruning broadcast protocol, a node may not forward a broadcast packet if a certain self-pruning condition is satisfied based on the neighborhood information. For each broadcasting, only a subset of nodes forwards the broadcast packet and still guarantee the complete network delivery under the ideal network situation that no packet is lost due to packet collision and node mobility. We evaluate the performance of the family of self-pruning protocols under various network situations with ns2. The objective is to observe the efficiency and reliability of these protocols as a function of network density, congestion, and mobility, and provide a guideline of implementation in the "real world". Our performance analysis reveals that the protocol reliability is barely affected by packet collision. However, most self-pruning protocols suffer from low delivery ratio in highly mobile networks. We further explore various techniques that improve the delivery ratio and show that both high efficiency and reliability can be achieved in highly mobile networks.

We propose a generic framework for distributed broadcasting in ad hoc wireless networks. The approach is based on selecting a small subset of nodes to form a forward node set to carry out a broadcast process. The status of each node, forward or nonforward, is determined either by the node itself or by other nodes. Node status can be determined at different snapshots of network state along time (called views) without causing problems in broadcast coverage. Therefore, the forward node set can be constructed and maintained through either a proactive process (i.e., "up-to-date") before the broadcast process or a reactive process (i.e., "on-the-fly") during the broadcast process. A sufficient condition, called coverage condition, is given for a node to take the nonforward status. Such a condition can be easily checked locally around the node. Several existing broadcast algorithms can be viewed as special cases of the generic framework with k-hop neighborhood information. A comprehensive comparison among existing algorithms is conducted. Simulation results show that new algorithms, which are more efficient than existing ones, can be derived from the generic framework.

Efficient routing among a set of mobile hosts is one of the most important functions in ad hoc wireless networks. Routing based on a connected dominating set is a promising approach, where the search space for a route is reduced to the hosts in the set. A set is dominating if all the hosts in the system are either in the set or neighbors of hosts in the set. The efficiency of dominating-set-based routing mainly depends on the overhead introduced in the formation of the dominating set and the size of the dominating set. In this paper, we first review a localized formation of a connected dominating set called marking process and dominating-set-based routing. Then, we propose a dominant pruning rule to reduce the size of the dominating set. This dominant pruning rule (called Rule k) is a generalization of two existing rules (called Rule 1 and Rule 2, respectively). We prove that the vertex set derived by applying Rule k is still a connected dominating set. Rule k is more effective in reducing the dominating set derived from the marking process than the combination of Rules 1 and 2 and, surprisingly, in a restricted implementation with local neighborhood information, Rule k has the same communication complexity and less computation complexity. Simulation results confirm that Rule k outperforms Rules 1 and 2, especially in networks with relatively high vertex degree and high percentage of unidirectional links. We also prove that an upper bound exists on the average size of the dominating set derived from Rule k in its restricted implementation.

Self-pruning is an effective scheme for efficient broadcasting in ad hoc wireless networks. In a self-pruning broadcast protocol, a node may not forward a broadcast packet if a certain self-pruning condition is satisfied based on the neighborhood information. In a static network with an ideal MAC layer, only a subset of nodes forward the broadcast packet and still guarantee the complete network delivery. Various protocols have been proposed with different self-pruning conditions. Recently, a generic self-pruning protocol was proposed by Wu and Dai (2003), which combines the strength of previous conditions and is more effective. In this paper, we first propose an enhanced version of the generic protocol, which is more elegant in interpreting existing protocols and has a simpler correctness proof. Then, we evaluate the performance of the family of self-pruning protocols under various network situations with ns2. The objective is to observe the efficiency and reliability of these protocols as a function of network density, congestion, and mobility, and provide a guideline of implementation in the "real world". Our performance analysis reveals that the protocol reliability is barely affected by packet collision. However, most self-pruning protocols suffer from low delivery ratio in highly mobile networks. We further explore various techniques that improve the delivery ratio and show that both high efficiency and reliability can be achieved in highly mobile networks.

Efficient routing among mobile hosts is an important function in ad hoc networks. Routing based on a connected dominating set is a promising approach, where the search space for a route is reduced to the hosts in the set. A set is dominating if all the hosts are either in the set or neighbors of hosts in the set. The efficiency of dominating-set-based routing mainly depends on the overhead introduced in the formation of the dominating set and the size of the dominating set. In this paper, we first review a distributed formation of a connected dominating set called marking process and dominating-set-based routing. Then a generalization of two existing rules (called rules 1 and 2). We prove that the vertex set derived by applying rule k is still a connected dominating set. When implemented with local neighborhood information. Rule k is more effective in reducing the dominating set derived from the marking process than the combination of rules 1 and 2, and has the same communication complexity and less computation complexity. Simulation results confirm that rule k outperforms rules 1 and 2, especially in relatively dense networks with unidirectional links.

We propose a generic framework for distributed broadcasting in ad hoc wireless networks. The approach is based on selecting a small subset of hosts (also called nodes) to form a forward node set to carry out a broadcast process. The status of each node, forwarding or non-forwarding, is determined either by itself (self-pruning) or by other nodes (neighbor-designating). Node status can be determined at different snapshots of network state along time (called views) without causing problems in broadcast coverage. A sufficient condition, called coverage condition, is given for a node to take the non-forward status. Such a condition can be easily checked locally around the node. Several existing broadcast algorithms can be viewed as special cases of the generic framework with k-hop neighborhood information. A comprehensive comparison among existing algorithms is conducted. Simulation results show that new algorithms, which are more efficient than existing ones, can be derived from the generic framework. This work is an extension to an early work in which only self-pruning methods are discussed [16].

We propose a general framework for broadcasting in ad hoc networks through self-pruning. The approach is based on selecting a small subset of hosts (also called nodes) to form a forward node set to carry out a broadcast process. Each node, upon receiving a broadcast packet, determines whether to forward the packet based on two neighborhood coverage conditions. These coverage conditions depend on neighbor connectivity and history of visited nodes, and in general, resort to global network information. Using local information such as k-hop neighborhood information, the forward node set is selected through a distributed and local pruning process. The forward node set can be constructed and maintained through either a proactive process (i.e., "up-to-date") or a reactive process (i.e., "on-the-fly"). Several existing broadcast algorithms can be viewed as special cases of the coverage conditions with k-hop neighborhood information. Simulation results show that new algorithms, which are more efficient than existing ones, can be derived from the coverage conditions, and self-pruning based on 2- or 3-hop neighborhood information is relatively cost-effective.

Link-state routing protocols, such as OSPF and IS-IS, are widely used in the Internet today. In link-state routing protocols, global network topology information is first collected at each node. A shortest path tree (SPT) is then constructed by applying Dijkstra's shortest path algorithm at each node. Link-state protocols usually require the flooding of new information to the entire (sub)network after changes in any link state (including link faults). Narvaez et al. proposed a fault-tolerant link-state routing protocol without flooding. The idea is to construct a shortest restoration path for each unidirectional link fault. Faulty link information is distributed only to the nodes in the restoration path and only one restoration path is constructed. It is shown that this approach is loop-free. However, the Narvaez et al. approach is inefficient when a link failure is bidirectional because a restoration path is unidirectional and routing tables of nodes in the path are partially updated. In addition, two restoration paths may be generated for each bidirectional link fault. In this paper, we extend the Narvaez et al. protocol to efficiently handle a bidirectional link fault by making the restoration path bidirectional. Several desirable properties of the proposed extended routing protocol are also explored. A simulation study is conducted to compare the traditional link-state protocol, the source-tree protocol, the Narvaez et al. unidirectional restoration path protocol, and the proposed bidirectional restoration path protocol.