Optimizing responses to broadcast messages in radio networks

Algorithms to optimize the performance of response traffic for broadcast messages in a packet-switched radio network are studied. The situation considered here involves a source node sending a broadcast message to all destinations and collecting positive response packets from these destinations in a fully connected packet radio network. The exact value of the number of destination nodes is unknown. A contention-based two-level protocol is described. Based on the protocol, an optimization problem is formulated in order to minimize the time for the source node to receive all the responses. Several algorithms are presented and numerical results of the corresponding optimization problems are obtained. These optimization problems are treated by the methods of dynamic programming. An extension of the basic scheme—multicast instead of full broadcast message—is also studied.This work was supported by the US Army Research Office under Contract No. DAAG29-84-K-0084.     

Weighted broadcast in linear radio networks

The weighted version of the broadcast range assignment problem in ad hoc wireless network is studied. Efficient algorithms are presented for the unbounded and bounded-hop broadcast problems for the linear radio network, where radio stations are placed on a straight line. For the unbounded case of the problem, the proposed algorithm runs in O(n²) time and using O(n) space, where n is the number of radio stations in the network. For the h-hop broadcast problem, the time and space complexities of our algorithm are O(hn²logn) and O(hn), respectively. This improves time complexity of the existing results for the same two problems by a factor of n and , respectively [C. Ambuhl, A.E.F. Clementi, M.D. Ianni, G. Rossi, A. Monti, R. Silvestri, The range assignment problem in non-homogeneous static ad hoc networks, in: Proc. 18th Int. Parallel and Distributed Precessing Symposium, 2004].     

Centralized asynchronous broadcast in radio networks

We study asynchronous broadcasting in packet radio networks. A radio network is represented by a directed graph, in which one distinguished source node stores a message that needs to be disseminated among all the remaining nodes. An asynchronous execution of a protocol is a sequence of events, each consisting of simultaneous deliveries of messages. The correctness of protocols is considered for specific adversarial models defined by restrictions on events the adversary may schedule. A protocol specifies how many times the source message is to be retransmitted by each node. The total number of transmissions over all the nodes is called the work of the broadcast protocol; it is used as complexity measure. We study computational problems, to be solved by deterministic centralized algorithms, either to find a broadcast protocol or to verify the correctness of a protocol, for a given network. The amount of work necessary to make a protocol correct may have to be exponential in the size of network. There is a polynomial-time algorithm to find a broadcast protocol for a given network. We show that certain problems about broadcasting protocols for given networks are complete in NP and co-NP complexity classes.     

Lower bounds for the broadcast problem in mobile radio networks

Summary.  In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol Π, for any n and for any D≦n/2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by Π for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors. Received: August 1994 / Accepted: August 1996     

Efficient forwarding scheme for downlink broadcast messages in IEEE 802.16j multi-hop relay networks

Although the IEEE 802.16j standard introduces a connection identifier (CID)-based forwarding scheme and a tunnel-based forwarding scheme, these schemes exhibit poor performance when forwarding broadcast messages. This study considers a CID translation strategy and proposes two CID-translated forwarding schemes for IEEE 802.16 multi-hop relay networks. The basic CID-translated forwarding scheme does not require to append the relay MAC header of the tunnel-based scheme to the broadcast messages. The enhanced CID-translated forwarding scheme further divides a broadcast message into a common part and a specific part and forwards these parts in a multicast manner and a broadcast manner, respectively. Simulation results validate that the basic CID-translated forwarding scheme uses fewer resources than the tunnel-based forwarding scheme. Moreover, the enhanced CID-translated forwarding scheme outperforms the basic CID-translated forwarding scheme in terms of the system resources used and transmission latency.     

Reliable election in broadcast networks

Election in a computer network is an operation in which one process is selected from among a group of processes to perform a particular task. An election is characterized by (1) the capacities of the candidates, and (2) the agreement reached by all processes to elect the master. In this paper, we show that election is in fact a very general style of computation. Many problems in computer networks can be solved by means of election. We then examine the election problem in computer networks with broadcast support. Basic design issues of election algorithms are addressed, and a number of election algorithms are presented based on various environments. These algorithms allow all nonfaulty processes to elect one and only one process as the master, and, by changing the definition of the capacities, they can be applied to a variety of problems.     

Performing work in broadcast networks

We consider the problem of how to schedule t similar and independent tasks to be performed in a synchronous distributed system of p stations communicating via multiple-access channels. Stations are prone to crashes whose patterns of occurrence are specified by adversarial models. Work, defined as the number of the available processor steps, is the complexity measure. We consider only reliable algorithms that perform all the tasks as long as at least one station remains operational. It is shown that every reliable algorithm has to perform work Ω(t+p√t) even when no failures occur. An optimal deterministic algorithm for the channel with collision detection is developed, which performs work (t+p√t). Another algorithm, for the channel without collision detection, performs work (t+p √t+ p min {f,t}), where f < p is the number of failures. This algorithm is proved to be optimal, provided that the adversary is restricted in failing no more than f stations. Finally, we consider the question if randomization helps against weaker adversaries for the channel without collision detection. A randomized algorithm is developed which performs the expected minimum amount (t+p√t) of work, provided that the adversary may fail a constant fraction of stations and it has to select failure-prone stations prior to the start of an execution of the algorithm. The work of the first author is supported by the NSF Grant 0310503. A preliminary version of this paper appeared as “The do-all problem in broadcast networks,” in Proceedings, 20th ACM Symposium on Principles of Distributed Computing, Newport, Rhode Island, 2001, pp. 117–126.     

A gradual noisy chaotic neural network for solving the broadcast scheduling problem in packet radio networks

In this paper, we propose a gradual noisy chaotic neural network (G-NCNN) to solve the NP-complete broadcast scheduling problem (BSP) in packet radio networks. The objective of the BSP is to design an optimal time-division multiple-access (TDMA) frame structure with minimal TDMA frame length and maximal channel utilization. A two-phase optimization is adopted to achieve the two objectives with two different energy functions, so that the G-NCNN not only finds the minimum TDMA frame length but also maximizes the total node transmissions. In the first phase, we propose a G-NCNN which combines the noisy chaotic neural network (NCNN) and the gradual expansion scheme to find a minimal TDMA frame length. In the second phase, the NCNN is used to find maximal node transmissions in the TDMA frame obtained in the first phase. The performance is evaluated through several benchmark examples and 600 randomly generated instances. The results show that the G-NCNN outperforms previous approaches, such as mean field annealing, a hybrid Hopfield network-genetic algorithm, the sequential vertex coloring algorithm, and the gradual neural network.     

Key continual-leakage resilient broadcast cryptosystem from dual system in broadcast networks

In order to tolerate possible leakage of secret keys, leakage-resilient cryptosystem models a class of attractive leakage output by allowing an adversary to provide any computable leakage function and learning the partial keys or other possible intemal states from the output of function. In this work, we present an adaptively secure broadcast encryption resilient to key continual leakage in the standard model. Our scheme provides the tolerance of continual leakage, in which any user can generate multiple private keys per user by periodically updating the key. We use the dual system encryption mechanism to implement the leakage resilience and adaptive security, and intrinsically set an algorithm to refresh a key and produce a same distributed new key. We also give the evaluation of the leakage bound and leakage fraction, and the simulations show that our scheme can tolerate about 71% leakage fraction with 3.34× 10^-52 failure probability in standard 80-bit security level when we adjust the leakage factor to allow the private key to be 100 Kb.     

Energy efficient all-to-all broadcast in all-wireless networks

All-to-all broadcast is a communication pattern in which every node initiates a broadcast. In this paper, we investigate the problem of building a unique cast tree of minimum total energy, which we call Minimum Unique Cast (MUC) tree, to be used for all-to-all broadcast. The MUC tree is unoriented and unrooted. We study three known heuristics for the minimum-energy broadcast problem: the Broadcast Incremental Power (BIP) algorithm, the Wireless Multicast Advantage-conforming Minimum Spanning Tree (WMA-conforming MST) algorithm, and the Iterative Maximum-Branch Minimization (IMBM) algorithm. Experimental results conducted on various types of networks are reported. We show that neither of these methods is best overall for building all-to-all broadcast trees.     

Optimizing channel selection for cognitive radio networks using a distributed Bayesian learning automata-based approach

Consider a multi-channel Cognitive Radio Network (CRN) with multiple Primary Users (PUs), and multiple Secondary Users (SUs) competing for access to the channels. In this scenario, it is essential for SUs to avoid collision among one another while maintaining efficient usage of the available transmission opportunities. We investigate two channel access schemes. In the first model, an SU selects a channel and sends a packet directly without Carrier Sensing (CS) whenever the PU is absent on this channel. In the second model, an SU invokes CS in order to avoid collision among co-channel SUs. For each model, we analyze the channel selection problem and prove that it is a so-called “Exact Potential” game. We also formally state the relationship between the global optimal point and the Nash Equilibrium (NE) point as far as system capacity is concerned. Thereafter, to facilitate the SU to select a proper channel in the game in a distributed manner, we design a Bayesian Learning Automaton (BLA)-based approach. Unlike many other Learning Automata (LA), a key advantage of the BLA is that it is learning-parameter free. The performance of the BLA-based approach is evaluated through rigorous simulations and this has been compared with the competing LA-based solution reported for this application, whence we confirm the superiority of our BLA approach.     

Static analysis of topology-dependent broadcast networks

Broadcast semantics poses significant challenges over point-to-point communication when it comes to formal modelling and analysis. Current approaches to analysing broadcast networks have focused on fixed connectivities, but this is unsuitable in the case of wireless networks where the dynamically changing network topology is a crucial ingredient. In this paper, we develop a static analysis that automatically constructs an abstract transition system, labelled by actions and connectivity information, to yield a mobility-preserving finite abstraction of the behaviour of a network expressed in a process calculus with asynchronous local broadcast. Furthermore, we use model checking based on a 3-valued temporal logic to distinguish network behaviour which differs under changing connectivity patterns.     

A recursion-based broadcast paradigm in wormhole routed networks

A novel broadcast technique for wormhole-routed parallel computers based on recursion is presented in this paper. It works by partitioning the interconnection graph into a number of higher-level subgraphs. Then, we identify the transmission subgraph (TSG) in each subgraph. Both the higher-level subgraphs and the TSGs are recursively defined, i.e., we split each level i subgraph into several level i+1 subgraphs and identify-level i+1 TSGs accordingly. We first split and scatter the source message into the TSG of the original graph. Next, in each recursive round message transmissions are from lower-level TSGs to higher-level TSGs and all transmissions at the same level happen concurrently. The algorithm proceeds recursively from lower-level subgraphs to higher level subgraphs until each highest-level subgraph (a single node) gets the complete message. We have applied this general paradigm to a number of topologies including two or higher dimension mesh/torus and hypercube. Our results show considerable improvements over all other algorithms for a wide range of message sizes under both one-port and all-port models.     

Broadcasting in dynamic radio networks

It is reasonable to claim that almost all major questions related to radio broadcasting can be considered closed as far as static networks are considered: the network never changes during the entire protocol's execution. On the other hand, theoretical results on communication protocols in any scenario where the network topology may change during protocol's execution (i.e. a dynamic radio network) are very few.In this paper, we present a theoretical study of broadcasting in radio networks having dynamic unknown topology. The dynamic network is modeled by means of adversaries: we consider two of them. We first analyze an oblivious, memoryless random adversary that can be seen as the dynamic version of the average-case study presented by Elsässer and Gasieniec in JCSS, 2006. We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). This is the dynamic version of the worst-case study provided by Bar-Yehuda, Goldreich and Itai in JCSS, 1992.In both cases we provide tight bounds on the completion time of randomized broadcast protocols.     

On the number of broadcast schemes in networks

Broadcasting is the process of spreading one piece of information among a group of individuals connected by an interconnection network. In this paper we give exact lower and upper bounds for the number of broadcast schemes in arbitrary networks. Also, we give the exact value for complete bipartite graphs and an upper bound for regular networks. Based on the counting method we describe a new random algorithm for broadcasting in networks.     

Scheduling time-constrained multicast messages in circuit-switched tree networks

In this paper, we consider a kind of multicast scheduling problem in a tree network. Each multicast message is transmitted through a directed subtree within the tree network. The transmission time of each multicast message is assumed to be one unit. Two messages can be transmitted at the same time if their subtrees are edge-disjoint. Each message is constrained by a ready time and a deadline, and has a weight we can gain if it is scheduled within its deadline. The optimality criterion is the total weight we gain. We assume that the degree of each subtree is bounded by a constant d and present an approximation algorithm of which the approximation ratio is at most 4d+15.     

Multihop all-to-all broadcast on WDM optical networks

Wavelength-division multiplexing (WDM) optical networks provide huge bandwidth by allowing multiple data streams transmitted simultaneously along the same optical fiber, with each stream assigned a distinct wavelength. A key issue on WDM optical networks is to minimize the number of wavelengths for communications. All-to-all broadcast (gossiping) is a fundamental communication application on computer/communication networks. It is known that the minimum numbers of wavelengths for realizing gossiping in one-hop of optical routing on the ring and the two-dimensional torus of N nodes are cN/sup 2/ and cN/sup 3/2/, c /spl ap/ 1/8, respectively. These numbers can be too large even for moderate values of N. One approach to reduce the number of wavelengths is to realize gossiping in multihops of routing. We give routing algorithms which realize gossiping in k-hops (k /spl ges/ 2) by O(N/sup 1+1/k/) wavelengths on the ring, O(N/sup 1+1/(2k)/) wavelengths on the 2D torus, and O(N/sup 1+1/(3k)/) wavelengths on the 3D torus on a simple multihop routing model. We also discuss the multihop routing for gossiping on a merge model. We give the upper bounds on the numbers of wavelengths for gossiping in two-hops and three-hops for the ring, 2D torus, and 3D torus on the merge model.     

Structuring unreliable radio networks

In this paper we study the problem of building a constant-degree connected dominating set (CCDS), a network structure that can be used as a communication backbone, in the dual graph radio network model (Clementi et al. in J Parallel Distrib Comput 64:89–96, 2004; Kuhn et al. in Proceedings of the international symposium on principles of distributed computing 2009, Distrib Comput 24(3–4):187–206 2011, Proceedings of the international symposium on principles of distributed computing 2010). This model includes two types of links: reliable, which always deliver messages, and unreliable, which sometimes fail to deliver messages. Real networks compensate for this differing quality by deploying low-layer detection protocols to filter unreliable from reliable links. With this in mind, we begin by presenting an algorithm that solves the CCDS problem in the dual graph model under the assumption that every process $u$ is provided with a local link detector set consisting of every neighbor connected to $u$ by a reliable link. The algorithm solves the CCDS problem in $O\left( \frac{\varDelta \log ^2{n}}{b} + \log ^3{n}\right) $ rounds, with high probability, where $\varDelta $ is the maximum degree in the reliable link graph, $n$ is the network size, and $b$ is an upper bound in bits on the message size. The algorithm works by first building a Maximal Independent Set (MIS) in $\log ^3{n}$ time, and then leveraging the local topology knowledge to efficiently connect nearby MIS processes. A natural follow-up question is whether the link detector must be perfectly reliable to solve the CCDS problem. With this in mind, we first describe an algorithm that builds a CCDS in $O(\varDelta $ polylog $(n))$ time under the assumption of $O(1)$ unreliable links included in each link detector set. We then prove this algorithm to be (almost) tight by showing that the possible inclusion of only a single unreliable link in each process’s local link detector set is sufficient to require $\varOmega (\varDelta )$ rounds to solve the CCDS problem, regardless of message size. We conclude by discussing how to apply our algorithm in the setting where the topology of reliable and unreliable links can change over time.