Cooperative multicast for maximum network lifetime

We consider cooperative data multicast in a wireless network with the objective to maximize the network lifetime. We present the maximum lifetime accumulative broadcast (MLAB) algorithm that specifies the nodes' order of transmission and transmit power levels. We prove that the solution found by MLAB is optimal but not necessarily unique. The power levels found by the algorithm ensure that the lifetimes of the active relays are the same, causing them to fail simultaneously. For the same battery levels at all the nodes, the optimum transmit powers become the same. The simplicity of the solution is made possible by allowing the nodes that are out of the transmission range of a transmitter to collect the energy of unreliably received overheard signals. As a message is forwarded through the network, nodes will have multiple opportunities to reliably receive the message by collecting energy during each retransmission. We refer to this cooperative strategy as accumulative multicast. Cooperative multicast not only increases the multicast energy-efficiency by allowing for more energy radiated in the network to be collected, but also facilitates load balancing by relaxing the constraint that a relay has to transmit with power sufficient to reach its most disadvantaged child. When the message is to be delivered to all network nodes this cooperative strategy becomes accumulative broadcast (Maric and Yates, 2002). Simulation results demonstrate that cooperative broadcast significantly increased network lifetime compared with conventional broadcast. We also present the distributed MLAB algorithm for accumulative broadcast that determines the transmit power levels locally at the nodes.     

Data Broadcast with Adaptive Network Coding in Heterogeneous Wireless Networks

In this paper, we propose a new data broadcast mechanism with network coding in heterogeneous wireless networks. Our mechanism adaptively clusters the mobile hosts in fewer cells to minimize the bandwidth consumption. In addition, we adaptively code the data according to the data temporarily stored in each mobile host with a distributed manner. Our mechanism allows each delivered message to be coded from only a subset of data to further reduce the number of required messages. We formulate the cell selection and broadcast coding problem with integer programming and prove that the problem is NP-hard. We design a distributed algorithm based on Lagrangean relaxation. Our algorithm needs no server to record the location, queried, and stored information of receivers. Moreover, our algorithm is adaptive to the dynamic group membership, mobility, queried, and stored data of receivers.     

On the power efficiency of cooperative broadcast in dense wireless networks

A fundamental problem in large scale wireless networks is the energy efficient broadcast of source messages to the whole network. The energy consumption increases as the network size grows, and the optimization of broadcast efficiency becomes more important. In this paper, we study the optimal power allocation problem for cooperative broadcast in dense large-scale networks. In the considered cooperation protocol, a single source initiates the transmission and the rest of the nodes retransmit the source message if they have decoded it reliably. Each node is allocated an-orthogonal channel and the nodes improve their receive signal-to-noise ratio (SNR), hence the energy efficiency, by maximal-ratio combining the receptions of the same packet from different transmitters. We assume that the decoding of the source message is correct as long as the receive SNR exceeds a predetermined threshold. Under the optimal cooperative broadcasting, the transmission order (i.e., the schedule) and the transmission powers of the source and the relays are designed so that every node receives the source message reliably and the total power consumption is minimized. In general, finding the best scheduling in cooperative broadcast is known to be an NP-complete problem. In this paper, we show that the optimal scheduling problem can be solved for dense networks, which we approximate as a continuum of nodes. Under the continuum model, we derive the optimal scheduling and the optimal power density. Furthermore, we propose low-complexity, distributed and power efficient broadcasting schemes and compare their power consumptions with those-of-a traditional noncooperative multihop transmission     

一种在无线自组织网络中延长网络生存时间的累积广播算法

文章考虑一个无线自组织网络中的广播问题,分析研究了传统累积广播算法及其性能表现,提出了一种新颖的算法,延长生存时间累积广播算法(ELAB算法)。然后通过一个4节点网络模型详细阐述了这一算法,并将它扩展到N节点无线自组织网络中。理论分析和仿真结果证明,相比于传统累积广播算法,对于不同的网络结构和节点数量,ELAB算法可延长网络的生存时间至少50%。     

Asymptotic analysis of multistage cooperative broadcast in wireless networks

Cooperative broadcast aims to deliver a source message to a locally connected network by means of collaborating nodes. In traditional architectures, node cooperation has been at the network layer. Recently, physical layer cooperative schemes have been shown to offer several advantages over the network layer approaches. This form of cooperation employs distributed transmission resources at the physical layer as a single radio with spatial diversity. In decentralized cooperation schemes, collaborating nodes make transmission decisions based on the quality of the received signal, which is the only parameter available locally. In this case, critical parameters that influence the broadcast performance include the source/relay transmission powers and the decoding threshold (the minimum signal-to-noise ratio (SNR) required to decode a transmission). We study the effect of these parameters on the number of nodes reached by cooperative broadcast. In particular, we show that there exists a phase transition in the network behavior: if the decoding threshold is below a critical value, the message is delivered to the whole network. Otherwise, only a fraction of the nodes is reached, which is proportional to the source transmit power. Our approach is based on the idea of continuum approximation, which yields closed-form expressions that are accurate when the network density is high.     

Minimum-energy all-to-all multicasting in wireless ad hoc networks

A wireless ad hoc network consists of mobile nodes that are powered by batteries. The limited battery lifetime imposes a severe constraint on the network performance, energy conservation in such a network thus is of paramount importance, and energy efficient operations are critical to prolong the lifetime of the network. All-to-all multicasting is one fundamental operation in wireless ad hoc networks, in this paper we focus on the design of energy efficient routing algorithms for this operation. Specifically, we consider the following minimum-energy all-to-all multicasting problem. Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, assume that each terminal node has a message to share with each other, the problem is to build a shared multicast tree spanning all terminal nodes such that the total energy consumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-Complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.     

Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks

Network wide broadcasting is a fundamental operation in ad hoc networks. In broadcasting, a source node sends a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc networks. Our objective is to minimize the latency and the number of transmissions in the broadcast. We show that minimum latency broadcasting is NP-complete for ad hoc networks. We also present a simple distributed collision-free broadcasting algorithm for broadcasting a message. For networks with bounded node transmission ranges, our algorithm simultaneously guarantees that the latency and the number of transmissions are within $O(1)$ times their respective optimal values. Our algorithm and analysis extend to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithms perform much better in practice than the analytical guarantees provided for the worst case.      

Maximum lifetime broadcast communications in cooperative multihop wireless ad hoc networks: Centralized and distributed approaches

We investigate the problem of broadcast routing in energy constrained stationary wireless ad hoc networks with an aim to maximizing the network lifetime measured as the number of successive broadcast sessions that can be supported. We propose an energy-aware spanning tree construction scheme supporting a broadcast request, considering three different signal transmission schemes in the physical layer: (a) point-to-point, (b) point-to-multipoint, and (c) multipoint-to-point. First we present a centralized algorithm that requires global topology information. Next, we extend this to design an approximate distributed algorithm, assuming the availability of k-hop neighborhood information at each node, with k as a parameter. We prove that the centralized scheme has time complexity polynomial in the number of nodes and the distributed scheme has a message complexity that is linear in the number of nodes. Results of numerical experiments demonstrate significant improvement in network lifetime following our centralized scheme compared to existing prominent non-cooperative broadcasting schemes proposed to solve the same lifetime maximization problem in wireless ad hoc networks. Due to lack of global topology information, the distributed solution does not produce as much advantage as the centralized solution. However, we demonstrate that with increasing value of k, the performance of the distributed scheme also improves significantly.     

Mobile ad hoc network broadcasting: A multi‐criteria approach

Nodes in a computer network often require a copy of a message to be delivered to every node in the network. The network layer can provide such a service, referred to as network‐wide broadcast routing or simply ‘broadcasting’. Broadcasting has many applications, including its role as a service to many routing protocols. In a mobile ad hoc network (MANET), simplistic broadcast schemes (such as flooding) inundate the network with redundancy, contention, collision, and unnecessary use of energy resources. This can prevent broadcasts from achieving their primary objective of maximizing delivery ratio, while also considering secondary objectives, such as balancing energy resources or reducing the network's burden on congested or busy nodes. As a solution, we propose multiple‐criteria broadcasting (MCB). In MCB, the source of each broadcast specifies the importance assigned to broadcast objectives. Network nodes use these priorities, along with local and neighbor knowledge of distributed factors, to broadcast in accordance with the objective priorities attributed to the message. Using ns2, the performance of MCB is evaluated and compared to that of other broadcast protocols. To present knowledge, MCB constitutes the first reconfigurable, multi‐objective approach to broadcasting. Copyright © 2010 John Wiley & Sons, Ltd.     

Piggyback a Common Message on Half-Duplex Bidirectional Relaying

In this work we consider the achievable rates of a joint resource allocation for a three-node network where a halfduplex relay node enables bidirectional communication between nodes 1 and 2 and thereby adds an own multicast message to the communication. In the multiple access phase nodes 1 and 2 transmit their message to the relay node, which decodes the messages and forwards them in the succeeding broadcast phase. Therefore, the relay node encodes the multicast and bidirectional messages using the superposition encoding strategy. We do not allow cooperation between the encoders of nodes 1 and 2, but since both nodes know a priori its own bidirectional message, both nodes can cancel the interference caused by their own message before decoding the unknown messages. It shows that for both nodes it is always optimal to decode the relay message first. Furthermore, the total sum-rate maximum is determined by the sum-rate optimum of the bidirectional broadcast phase. From the closed form solutions of the combinatorial problems we can characterize the bidirectional rate pairs where the total sum-rate remains constant. In the end the obtained results are discussed and illustrated by means of some working examples. The joint resource allocation improves the overall spectral efficiency and enables new trade-offs between the routing tasks.     

基于分层的水下传感器网络路由策略

提出一种基于分层的水下传感器网络路由协议（Layered-DBR, layered-depth based routing）。节点进行一次信息广播后,只允许指定深度范围内的节点进行消息接收,以达到控制网络副本的目的,最终建立与网络冗余相关的网络分层模型。在分层网络中,节点首先需要计算消息转发前后的相对深度距离与相对剩余能量,进而计算出消息的转发概率。同时,建立一种消息队列管理机制,该队列同时具有消息转发管理和历史记录管理的功能,并给出消息的入列和出列方法。仿真实验表明,Layered-DBR能够有效地控制网络冗余,与DBR和Flooding算法相比,Layered-DBR能有效地减少网络能耗,延长网络寿命。     

DRAND: Distributed Randomized TDMA Scheduling for Wireless Ad Hoc Networks

This paper presents a distributed implementation of RAND, a randomized time slot scheduling algorithm, called DRAND. DRAND runs in O(delta ) time and message complexity where delta is the maximum size of a two-hop neighborhood in a wireless network while message complexity remains O(delta ), assuming that message delays can be bounded by an unknown constant. DRAND is the first fully distributed version of RAND. The algorithm is suitable for a wireless network where most nodes do not move, such as wireless mesh networks and wireless sensor networks. We implement the algorithm in TinyOS and demonstrate its performance in a real testbed of Mica2 nodes. The algorithm does not require any time synchronization and is shown to be effective in adapting to local topology changes without incurring global overhead in the scheduling. Because of these features, it can also be used even for other scheduling problems such as frequency or code scheduling (for FDMA or CDMA) or local identifier assignment for wireless networks where time synchronization is not enforced. We further evaluate the effect of the time-varying nature of wireless links on the conflict-free property of DRAND-assigned time slots. This experiment is conducted on a 55-node testbed consisting of the more recent MicaZ sensor nodes.     

RPB-MD: Providing robust message dissemination for vehicular ad hoc networks

To improve traffic safety and efficiency, it is vital to reliably send traffic-related messages to vehicles in the targeted region in vehicular ad hoc networks (VANETs). In this paper, we propose a novel scheme, relative position based message dissemination (RPB-MD), to reliably and efficiently disseminate messages to the vehicles in the zone-of-relevance. Firstly, the relative position based (RPB) addressing model is proposed to effectively define the intended receivers in the zone-of-relevance. To ensure high message delivery ratio and low delivery delay, directional greedy broadcast routing (DGBR) is introduced to make a group of candidate nodes hold the message for high reliability. Moreover, to guarantee efficiency, the protocol time parameters are designed adaptively according to the message attributes and local vehicular traffic density. The protocol feasibility is analyzed to illustrate the robustness and reliability of RPB-MD. Simulation results show that RPB-MD, compared with representative existing schemes, achieves high delivery ratio, limited overhead, reasonable delay and high network reachability under different vehicular traffic density and data sending rate.     

A minimum-energy path-preserving topology-control algorithm

The topology of a wireless multihop network can be controlled by varying the transmission power at each node. It is not energy efficient to use the communication network G/sub max/ where every node transmits with maximum power. For energy efficient operations, it is desirable to have a subnetwork that preserves a minimum-energy path between every pair of nodes (where a minimum-energy path is one that allows messages to be transmitted with a minimum use of energy). We first identify conditions that are necessary and sufficient for a subnetwork G of G/sub max/ to preserve this property. Using this characterization, we then propose an efficient topology-control algorithm that, given a communication network G/sub max/, computes a subnetwork G that it preserves at least one minimum-energy path between every pair of nodes. We also propose an energy-efficient reconfiguration protocol that maintains this minimum-energy path property as the network topology changes dynamically. We demonstrate the performance improvements of our algorithm over other existing topology-control algorithms through simulation.     

Deterministic collision free communication despite continuous motion

We present a deterministic solution for nodes in a mobile wireless ad hoc network to communicate reliably and maintain local neighborhood information. The nodes are located on a two-dimensional plane and may be in continuous motion. In our solution we tile the plane with hexagons. Each hexagon is assigned a color from a finite set of colors. Two hexagons of the same color are located sufficiently far apart so that nodes in these two hexagons cannot interfere with each other’s broadcasts. Based on this partitioning we develop a periodic deterministic schedule for mobile nodes to broadcast. This schedule guarantees collision avoidance. Broadcast slots are tied to geographic locations instead of nodes and the schedule for a node changes dynamically as it moves from tile to tile. The schedule allows nodes to maintain information about their local neighborhood. This information in turn is used to keep the schedule collision-free. We demonstrate the correctness of our algorithm, and discuss how the periodic schedule can be adapted for different scenarios. The periodic schedule, however, does not address the problem of initial neighbor discovery at start-up. We give a separate algorithm for this problem of initially discovering nodes present within communication range at start-up.     

Improving broadcast performance by traffic isolation in wireless ad hoc networks

In this paper we propose a new broadcasting algorithm. In the proposed method we significantly reduce the broadcast overhead and also improve the broadcast delivery ratio in mobile networks. A novel traffic isolation method has been used which reduces the control message exchange. The proposed broadcasting method is based on a clustering method called ‘stability‐based clustering algorithm’ which had been proposed before. The broadcasting traffic is divided into internal (flow inside a cluster) and external traffic (flow among the clusters). For internal flooding traffic, cluster‐heads and gateways are responsible for re‐broadcasting but for external type, border nodes may perform the forwarding function as well. This simplifies the gateway selection method through the local selection of gateway nodes by its cluster head. Therefore, a cluster head selects gateway in its own cluster without any knowledge of other clusters. Considering the effect of mobility and node density, simulations have been conducted in a number of wireless environments. Simulation results show the broadcast coverage is close to 100% at different node speeds. Moreover, we study the broadcast parameters in light and dense networks and show improvement of the overhead and the number of forward nodes in comparison to other broadcasting methods. Copyright © 2005 John Wiley & Sons, Ltd.     

A combination of wireless multicast advantage and hitch-hiking

In the minimum energy broadcast problem, each node adjusts its transmission power to minimize the total energy consumption while still delivering data to all the nodes in a network. The minimum energy broadcast problem is proved to be NP-complete. The Wireless Multicast Advantage (WMA) is that a single transmission can be received by all the nodes that are within the transmission range of a transmitting node. The Hitch-hiking model introduced recently takes advantage of the physical layer to combine partial signals containing the same data in order to decode a complete message. In this letter, we take advantage of both WMA and Hitch-hiking to design an energy-efficient broadcast tree algorithm with Hitch-hiking (BHH). The approximation ratio of BHH is within a factor of O(logn) where n, is the number of nodes in the network. The simulation results show that BHH reduces the total energy of the broadcast tree greatly.     

Distributed algorithms for lifetime maximization in sensor networks via Min–Max spanning subgraphs

We consider the problem of static transmission-power assignment for lifetime maximization of a wireless sensor network with stationary nodes operating in a data-gathering scenario. Using a graph-theoretic approach, we propose two distributed algorithms, MLS and BSpan, that construct spanning trees with minimum maximum (minmax) edge cost. MLS is based on computation of minmax-cost paths from a reference node, while BSpan performs a binary search over the range of power levels and exploits the wireless broadcast advantage. We also present a simple distributed method for pruning a graph to its Relative Neighborhood Graph, which reduces the worst-case message complexity of MLS under natural assumptions on the path-loss. In our network simulations both MLS and BSpan significantly outperform the recently proposed Distributed Min–Max Tree algorithm in terms of number of messages required.     

Optimal backpressure routing for wireless networks with multi-receiver diversity

We consider the problem of optimal scheduling and routing in an ad-hoc wireless network with multiple traffic streams and time varying channel reliability. Each packet transmission can be overheard by a subset of receiver nodes, with a transmission success probability that may vary from receiver to receiver and may also vary with time. We develop a simple backpressure routing algorithm that maximizes network throughput and expends an average power that can be pushed arbitrarily close to the minimum average power required for network stability, with a corresponding tradeoff in network delay. When channels are orthogonal, the algorithm can be implemented in a distributed manner using only local link error probability information, and supports a “blind transmission” mode (where error probabilities are not required) in special cases when the power metric is neglected and when there is only a single destination for all traffic streams. For networks with general inter-channel interference, we present a distributed algorithm with constant-factor optimality guarantees.     

Balancing transport and physical Layers in wireless multihop networks: jointly optimal congestion control and power control

In a wireless network with multihop transmissions and interference-limited link rates, can we balance power control in the physical layer and congestion control in the transport layer to enhance the overall network performance while maintaining the architectural modularity between the layers? We answer this question by presenting a distributed power control algorithm that couples with existing transmission control protocols (TCPs) to increase end-to-end throughput and energy efficiency of the network. Under the rigorous framework of nonlinearly constrained utility maximization, we prove the convergence of this coupled algorithm to the global optimum of joint power control and congestion control, for both synchronized and asynchronous implementations. The rate of convergence is geometric and a desirable modularity between the transport and physical layers is maintained. In particular, when congestion control uses TCP Vegas, a simple utilization in the physical layer of the queueing delay information suffices to achieve the joint optimum. Analytic results and simulations illustrate other desirable properties of the proposed algorithm, including robustness to channel outage and to path loss estimation errors, and flexibility in trading off performance optimality for implementation simplicity. This work presents a step toward a systematic understanding of "layering" as "optimization decomposition," where the overall communication network is modeled by a generalized network utility maximization problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as the optimization variables coordinating the subproblems. In the case of the transport and physical layers, link congestion prices turn out to be the optimal "layering prices.".