Optimal Broadcasting in Faulty Trees

We consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B to inform C and the optimal time to inform C, taken over all components C yielded by configurations of at most k faults, is the k-vulnerability of B. This is the maximum slowdown incurred by B due to the lack of a priori knowledge of fault location, for at most k faults. This measure of fault tolerance is similar to the competitive factor of on-line algorithms: in both cases, the performance of an algorithm lacking some crucial information is compared to the performance of an “off-line” algorithm, one that is given this information as input. It is also the first known tool to measure and compare fault tolerance of broadcasting schemes in trees. We seek broadcasting schemes with low vulnerability, working for tree networks. It turns out that schemes that give the best broadcasting time in a fault-free environment may have very high vulnerability, i.e., poor fault tolerance, for some trees. The main result of this paper is an algorithm that, given an arbitrary tree T and an integer k, computes a broadcasting scheme B with lowest possible k-vulnerability among all schemes working for T. Our algorithm has running time O(kn²+n² log n), where n is the size of the tree. We also give an algorithm to find a “universally fault-tolerant” broadcasting scheme in a tree T: one that approximates the lowest possible k-vulnerability, for all k simultaneously.     

Deterministic broadcasting in ad hoc radio networks

We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes know neither the topology nor the size of the network, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. Such networks are called ad hoc multi-hop networks. We study the time of deterministic broadcasting under this scenario. For the model without collision detection, we develop a linear-time broadcasting algorithm for symmetric graphs, which is optimal, and an algorithm for arbitrary n-node graphs, working in time . Next we show that broadcasting with acknowledgement is not possible in this model at all. For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting in strongly connected graphs. Received: January 2000 / Accepted: June 2001     

Trade-offs Between the Size of Advice and Broadcasting Time in Trees

We study the problem of the amount of information required to perform fast broadcasting in tree networks. The source located at the root of a tree has to disseminate a message to all nodes. In each round each informed node can transmit to one child. Nodes do not know the topology of the tree but an oracle knowing it can give a string of bits of advice to the source which can then pass it down the tree with the source message. The quality of a broadcasting algorithm with advice is measured by its competitive ratio: the worst case ratio, taken over n-node trees, between the time of this algorithm and the optimal broadcasting time in the given tree. Our goal is to find a trade-off between the size of advice and the best competitive ratio of a broadcasting algorithm for n-node trees. We establish such a trade-off with an approximation factor of O(n ^ε ), for an arbitrarily small positive constant ε. This is the first communication problem for which a trade-off between the size of advice and the efficiency of the solution is shown for arbitrary size of advice.     

Broadcasting in UDG radio networks with missing and inaccurate information

We study broadcasting time in radio networks, modeled as unit disk graphs (UDG). Network stations are represented by points in the plane and a station is connected to all stations at distance at most 1 from it. Stations are unaware of the network topology. Each station can send messages from the beginning of the broadcasting process, even before getting the source message. Emek et al. showed that broadcasting time depends on two parameters of the UDG network, namely, its diameter D (in hops) and its granularity g. The latter is the inverse of the density d of the network which is the minimum Euclidean distance between any two stations. They proved that the minimum broadcasting time is Θ(min {D + g ², D log g}), assuming that each node knows the density of the network and knows exactly its own position in the plane. In many situations these assumptions are unrealistic. Does removing them influence broadcasting time? The aim of this paper is to answer this question, hence we assume that density is unknown and nodes perceive their position with some unknown error margin ${\varepsilon}We study broadcasting time in radio networks, modeled as unit disk graphs (UDG). Network stations are represented by points in the plane and a station is connected to all stations at distance at most 1 from it. Stations are unaware of the network topology. Each station can send messages from the beginning of the broadcasting process, even before getting the source message. Emek et al. showed that broadcasting time depends on two parameters of the UDG network, namely, its diameter D (in hops) and its granularity g. The latter is the inverse of the density d of the network which is the minimum Euclidean distance between any two stations. They proved that the minimum broadcasting time is Θ(min {D + g ², D log g}), assuming that each node knows the density of the network and knows exactly its own position in the plane. In many situations these assumptions are unrealistic. Does removing them influence broadcasting time? The aim of this paper is to answer this question, hence we assume that density is unknown and nodes perceive their position with some unknown error margin e{\varepsilon}. It turns out that this combination of missing and inaccurate information substantially changes the problem: the main new challenge becomes fast broadcasting in sparse networks (with constant density), when optimal time is O(D). Nevertheless, under our very weak scenario, we construct a broadcasting algorithm that maintains optimal time O (min {D + g ², D log g}) for all networks with at least 2 nodes, of diameter D and granularity g (previously obtained with exact positions and known density), if each node perceives its position with error margin e = ad{\varepsilon=\alpha d}, for any (unknown) constant α < 1/2. Rather surprisingly, the minimum time of an algorithm working correctly for all networks, and hence stopping if the source is alone, turns out to be Θ(D + g ²). Thus, the mere stopping requirement for the special case of the lonely source causes an exponential increase in broadcasting time, for networks of any density and any small diameter. Finally, if e 3 d/2{\varepsilon\geq d/2}, then broadcasting is impossible.     

Periodic Gossiping in Commuted Networks

In this paper we deal with global communication schemes such as broadcasting or multicasting, in a packet (sub)network in which each node participates in the same distributed application. We want the communication scheme to be performed periodically as often as possible and with some bandwidth guarantee. Such periodicity properties are needed, for example, by multimedia and grid computation applications. We consider commuted switches in the network, i.e., each outgoing link of the switch is assigned to at most one incoming link. Each switch avoids intermediate buffering. Given a network G and a global communication scheme S, an algorithm performing S in G consists in commuting each switch and in specifying to each emitting node the infinite sequence of steps at which it will send a message. The period of this algorithm is the greatest number of steps between two messages emitted by a node. The window of the algorithm is the maximal number of steps needed by a message to reach its destination(s). We first give a general definition of the model of network we consider and of the global communication schemes we study, i.e., the many-to-all scheme where many nodes have one message to send to all the other ones. One well-known case of the many-to-all scheme we especially focus on is gossiping. We present a general way of periodically performing these communication schemes, by covering the graph by substructures called octopuses. Then we show that optimizing the period and the windoware two different problems.We end by giving some examples of applications in the torus network.     

基于生成树的无线传感器网络时钟同步算法

考虑到无线传感器网络时钟同步多跳误差累积问题,提出一种基于动态生成树的全网时钟同步算法,只需由根节点开始沿树边广播一次同步消息,全网待同步节点即可采用时钟偏差补偿,并结合贝叶斯后验估计算法对时钟进行准确估计。一个同步轮次内每个节点至多广播两次消息即可完成全网同步。使用OMNeT++软件进行仿真实验表明算法有效降低了多跳累积误差,提高了同步精度,且具有较快的收敛速度和较低的开销。     

Dominating sets and neighbor elimination-based broadcastingalgorithms in wireless networks

In a multihop wireless network, each node has a transmission radius and is able to send a message to all of its neighbors that are located within the radius. In a broadcasting task, a source node sends the same message to all the nodes in the network. In this paper, we propose to significantly reduce or eliminate the communication overhead of a broadcasting task by applying the concept of localized dominating sets. Their maintenance does not require any communication overhead in addition to maintaining positions of neighboring nodes. Retransmissions by only internal nodes in a dominating set is sufficient for reliable broadcasting. Existing dominating sets are improved by using node degrees instead of their ids as primary keys. We also propose to eliminate neighbors that already received the message and rebroadcast only if the list of neighbors that might need the message is nonempty. A retransmission after negative acknowledgements scheme is also described. The important features of the proposed algorithms are their reliability (reaching all nodes in the absence of message collisions), significant rebroadcast savings, and their localized and parameterless behavior. The reduction in communication overhead for the broadcasting task is measured experimentally. Dominating set based broadcasting, enhanced by a neighbor elimination scheme and highest degree key, provides reliable broadcast with ⩽53 percent of node retransmissions (on random unit graphs with 100 nodes) for all average degrees d. Critical d is around 4, with <48 percent for ⩽3, ⩽40 percent for d⩾10, and ⩽20 percent for d⩾25. The proposed methods are better than existing ones in all considered aspects: reliability, rebroadcast savings, and maintenance communication overhead. In particular, the cluster structure is inefficient for broadcasting because of considerable communication overhead for maintaining the structure and is also inferior in terms of rebroadcast savings     

Heuristic Contention-Free Broadcast in Heterogeneous Networks of Workstations with Multiple Send and Receive Speeds

This paper presents three efficient contention-free algorithms for broadcasting on heterogeneous networks of workstations (HNOW). In an HNOW, many different speed types of workstations can have distinct send and receive overhead. Previous research has shown that finding an optimal routing scheme in an HNOW is not easy [2,12], because properly arranging all workstations in the scheduling tree is difficult. Therefore, this investigation focuses mainly on enhancing the performance of an HNOW by properly arranging fastest nodes into the internal nodes of upper levels in the scheduling tree. Fastest node first is fundamental in designing an efficient algorithm. This paper presents three schemes called EBS, VBBS, and VBBSWF. All of these three schemes can be executed in O(n log(n)) time, where n is the number of workstations. They are all contention-free when broadcasting in an HNOW. Based on the simulation result, the proposed schemes outperform the broadcast with minimal steps [13] and the scheduling tree [22] generated by dynamic programing in an HNOW.     

Optimal Communication Algorithms on Star Graphs Using Spanning Tree Constructions

In this paper we consider three fundamental communication problems on the star interconnection network: the problem of simultaneous broadcasting of a message from every node to all other nodes, or multinode broadcasting, the problem of a single node sending distinct messages to each one of the other nodes, or single-node scattering, and finally the problem of each node sending distinct messages to every other node, or total exchange. All of these problems are studied under two different assumptions: the assumption that each node can transmit a message of fixed length to one of its neighbors and simultaneously receive a message of fixed length from one of its neighbors (not necessarily the same one) at each time step, or single-link availability, and the assumption that each node can exchange messages of fixed length with all of its neighbors at each time step, or multiple-link availability. In both cases communication is assumed to be bidirectional. The cases where the originating processor wishes to send only one or more than one message to each one of the other processors are distinguished when necessary. Lower bounds are derived for these problems under the stated assumptions, and optimal algorithms are designed in terms of both time and number of message transmissions. Although the algorithms derived for the first two problems require the minimum amount of the above resources, the algorithm designed for the total exchange problem is optimal only to within a multiplicative factor. All the communication algorithms presented in this paper are based on the construction of spanning trees with special properties on the star graph to fit different communication needs. A special framework is developed to facilitate the construction of these trees. The scheduling disciplines that lead to optimal results in each case are described.     

基于大功率消息广播的DTMSN路由机制

提出一种基于基站大功率信号广播的延迟容忍移动传感器网络消息路由机制(High-power Broadcasting based Routing scheme,HBR)。该机制使用两个通信频率f₁ 和f₂,基站以恒定大功率在频率f₁上广播已经接收到的消息,网络中传感器节点根据基站广播信息计算自身转发概率并清理冗余消息副本,节点间利用频率f₂进行通信。为进一步提升网络性能,HBR优先传输转发阈值(M)小且生存时间短的消息,并合理进行消息队列管理。仿真结果表明,与几种经典的路由机制相比,HBR在消息传输成功率、传输延迟方面有着一定的优势。     

An Adaptive Routing Algorithm for WK-Recursive Topologies

This paper presents an easy and straightforward routing algorithm for WK-recursive topologies. The algorithm, based on adaptive routing, takes advantage of the geometric properties of such topologies. Once a source node S and destination node D have been determined for a message communication, they characterize, at some level l, two virtual nodes and that respectively contain S but not D and D but not S. Such virtual nodes characterize other (where is the node degree for a fixed topology) virtual nodes of the same level that contain neither S nor D. Consequently, it is possible to locate triangles whose vertices are these virtual nodes with property to share the same path, called the self-routing path, directly connecting to . When the self-routing path is unavailable to transmit a message from S to D because of deadlock, fault, and congestion conditions, the routing strategy can follow what we call the triangle rule to deliver it. The proposed communication scheme has the advantage that 1) it is the same for all three conditions; 2) each node of a WK-recursive network, to transmit messages, does not require any information about their presence or location. Furthermore, this routing algorithm is able to tolerate up to faulty links. Received: July 19, 1998; revised May 17, 1999     

无线传感网络低能耗时间同步的研究

低耗能是无线传感器网络时间同步算法的重要技术要求之一。为了降低同步过程中的能量消耗,提出了一种低能耗LECTS（Low Energy Consumption Time Synchronization）算法。该算法基于TPSN算法的基本思想,在两个阶段同时进行改进来降低能量消耗。在层次发现阶段利用节点之间的距离来限制部分节点广播,降低数据包的发送;在同步阶段结合单向广播和双向报文交换同步机制,也同样降低数据包的发送。通过仿真结果表明,与TPSN算法以及其改进算法STSP算法相比,算法能显著地降低无线传感器网络时间同步的能量消耗,且节点密度越大,节能越显著。     

Fast and proximity-aware multi-source overlay multicast under heterogeneous environment

Overlay multicast has been considered as one of the most important developments for the next generation Internet infrastructure. In this paper, we consider overlay multicast in the scenarios where any participant node is a potential data source. Existing multicast algorithms for single-source always require a long time to deliver messages or have high maintenance overhead when multiple data sources are allowed. There are other algorithms that are designed for multi-source scenarios. But they consume too much network resources and have a long convergence time because of proximity ignorance. To address the issues, we present FPCast, which leverages node heterogeneity and proximity information at the same time. Physically close nodes are grouped into clusters and each cluster selects a powerful, stable node as its rendezvous point. The rendezvous nodes form a DHT-based structure. Data messages are replicated and forwarded along implicit, source specific, and heterogeneity-aware multicast trees. We further reduce the delivery delay by introducing probabilistic forwarding scheme. We show the average delivery path length converges to O(logn) automatically (n is the number of nodes in the overlay). The simulation results demonstrate the superiority of our algorithm in terms of message delivery time and network resource consumption, in comparison with the previous randomized algorithms. The algorithm is also resilient to node failures.     

Optimal NODUP all-to-all broadcast schemes in distributed computingsystems

Broadcast, referring to a process of information dissemination in a distributed system whereby a message originating from a certain node is sent to all other nodes in the system, is a very important issue in distributed computing. All-to-all broadcast means the process by which every node broadcasts its certain piece of information to all other nodes. In this paper, we first develop the optimal all-to-all broadcast scheme for the case of one-port communication, which means that each node can only send out one message in one communication step, and then, extend our results to the case of multi-port communication, i.e., k-port communication, meaning that each node can send out k messages in one communication step. We prove that the proposed schemes are optimal for the model considered in the sense that they not only require the minimal number of communication steps, but also incur the minimal number of messages     

Broadcasting in UDG radio networks with unknown topology

The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning. It turns out that broadcasting time depends on two parameters of the UDG network, namely, its diameter D and its granularity g, which is the inverse of the minimum distance between any two stations. We present a deterministic broadcasting algorithm which works in time O (D g) under the conditional wake up model and prove that broadcasting in this model cannot be accomplished by any deterministic algorithm in time better than ${\Omega (D \sqrt{g})}The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning. It turns out that broadcasting time depends on two parameters of the UDG network, namely, its diameter D and its granularity g, which is the inverse of the minimum distance between any two stations. We present a deterministic broadcasting algorithm which works in time O (D g) under the conditional wake up model and prove that broadcasting in this model cannot be accomplished by any deterministic algorithm in time better than W(D ?g){\Omega (D \sqrt{g})} . For the spontaneous wake up model, we design two deterministic broadcasting algorithms: the first works in time O (D + g ²) and the second in time O (D log g). While neither of these algorithms alone is optimal for all parameter values, we prove that the algorithm obtained by interleaving their steps, and thus working in time O ( min{ D + g², D logg}){ O \left( \min\left\{ D + g^2, D \log{g}\right\}\right) }, turns out to be optimal by establishing a matching lower bound.     

Assigning labels in an unknown anonymous network with a leader

We consider the task of assigning distinct labels to nodes of an unknown anonymous network in a distributed manner. A priori, nodes do not have any identities, except for one distinguished node, called the source, and do not know the topology or the size of the network. They execute identical algorithms, apart from the source which plays the role of a leader and starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms. Received: July 2000 / Accepted: February 2001     

A Note on Optimal Time Broadcast in Faulty Hypercubes

This note describes an algorithm for broadcasting a message on the n-dimensional hypercube in optimal time (n time units) and optimal communication (2ⁿ − 1 messages) in the presence of up to n − 2 arbitrary node or edge faults, assuming the set of faults is known to all nodes of the hypercube.     

Data aggregation in wireless sensor networks using ant colony algorithm

Data aggregation is important in energy constraint wireless sensor networks which exploits correlated sensing data and aggregates at the intermediate nodes to reduce the number of messages exchanged network. This paper considers the problem of constructing data aggregation tree in a wireless sensor network for a group of source nodes to send sensory data to a single sink node. The ant colony system provides a natural and intrinsic way of exploring search space in determining data aggregation. Moreover, we propose an ant colony algorithm for data aggregation in wireless sensor networks. Every ant will explore all possible paths from the source node to the sink node. The data aggregation tree is constructed by the accumulated pheromone. Simulations have shown that our algorithm can reduce significant energy costs.     

Efficient Broadcasting Using Network Coding and Directional Antennas in MANETs

In this paper, we consider the issue of efficient broadcasting in mobile ad hoc networks (MANETs) using network coding and directional antennas. Network coding-based broadcasting focuses on reducing the number of transmissions each forwarding node performs in the multiple source/multiple message broadcast application, where each forwarding node combines some of the received messages for transmission. With the help of network coding, the total number of transmissions can be reduced compared to broadcasting using the same forwarding nodes without coding. We exploit the usage of directional antennas to network coding-based broadcasting to further reduce energy consumption. A node equipped with directional antennas can divide the omnidirectional transmission range into several sectors and turn some of them on for transmission. In the proposed scheme using a directional antenna, forwarding nodes selected locally only need to transmit broadcast messages, original or coded, to restricted sectors. We also study two extensions. The first extension applies network coding to both dynamic and static forwarding node selection approaches. In the second extension, we design two approaches for the single source/single message issue in the network coding-based broadcast application. Performance analysis via simulations on the proposed algorithms using a custom simulator and ns2 is presented.     

Ad Hoc网络的加权可靠路由策略

在Ad Hoc网络中,由于网络节点的移动性及拓扑结构的易变性,路由成为最受关注的问题。为了克服在路由算法中,节点的信息存储量大、路径使用效率低下、路由开支庞大等问题。提出了一种加权可靠路由策略W-RR。在该策略中,每个节点都保存稳定性、开销以及邻居节点信息,在进行选路时,对路径的可靠性进行加权,并利用定位系统在源节点和目的节点之间选择一条加权可靠性最大的路径。仿真结果表明,该路由策略在可靠性、建路时间、选路成功率、路径的开销和信息量等方面都具有较好的性能。