共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
3.
Radio networks model wireless data communication when the bandwidth is limited to one wave frequency. The key restriction
of such networks is mutual interference of packets arriving simultaneously at a node. The many-to-many (m2m) communication
primitive involves p participant nodes from among n nodes in the network, where the distance between any pair of participants is at most d. The task is to have all the participants get to know all the input messages. We consider three cases of the m2m communication
problem. In the ad-hoc case, each participant knows only its name and the values of n, p and d. In the partially centralized case, each participant knows the topology of the network and the values of p and d, but does not know the names of the other participants. In the centralized case, each participant knows the topology of the
network and the names of all the participants. For the centralized m2m problem, we give deterministic protocols, for both
undirected and directed networks, working in
time, which is provably optimal. For the partially centralized m2m problem, we give a randomized protocol for undirected networks
working in
time with high probability (whp), and we show that any deterministic protocol requires
time. For the ad-hoc m2m problem, we develop a randomized protocol for undirected networks that works in
time whp. We show two lower bounds for the ad-hoc m2m problem. One lower bound states that any randomized protocol for the
m2m ad hoc problem requires
expected time. Another lower bound states that for any deterministic protocol for the m2m ad hoc problem, there is a network
on which the protocol requires
time when n−p(n)=Ω(n) and d>1, and that it requires Ω(n) time when n−p(n)=o(n).
The results of this paper appeared in a preliminary form in “On many-to-many communication in packet radio networks” in Proceedings
of the 10th Conference on Principles of Distributed Systems (OPODIS), Bordeaux, France, 2006, Lecture Notes in Computer Science
4305, Springer, Heidelberg, pp. 258–272.
The work of B.S. Chlebus was supported by NSF Grant 0310503. 相似文献
4.
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 相似文献
5.
Gautam K. Das 《Information Processing Letters》2008,106(4):136-143
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(n2) 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(hn2logn) 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]. 相似文献
6.
7.
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. 相似文献
8.
9.
Broadcasting by flooding causes the broadcast storm problem in multi-hop wireless networks. This problem becomes more likely in a wireless mesh network (WMN) because WMNs can bridge wired LANs, increasing broadcast traffic and collision probability. Since the network control, routing, and topology maintenance of a WMN highly rely on layer-2 broadcasting, unreliable broadcast algorithms directly destabilize a WMN. Researchers have developed many algorithms for efficient and reliable broadcast in multi-hop wireless networks. However, real-world systems rarely verify or compare these approaches, especially in a WMN. This paper examines six representative broadcast algorithms: simple flooding, dynamic probabilistic, efficient counter-based broadcast, scalable broadcast, domain pruning, and connected-dominating-set based algorithms. This study addresses both common and algorithm-specific implementation in a real-world IEEE 802.11s WMN testbed. Experiments under various topologies and packet lengths reveal the reliability, forwarding ratio, and efficiency of these six algorithms. Quantitative survey results indicate that the scalable broadcast algorithm possesses the best reliability due to its lower collision probability. The domain-pruning algorithm is the most efficient algorithm when considering both reliability and the forwarding ratio. 相似文献
10.
In this paper, a reachability-guaranteed approach for reducing broadcast storms in MANET is proposed. The approach is based on location awareness of each node, which means each node in the network needs to equip the positioning device like GPS and exchanges location information in the HELLO message with its neighbors. Three mechanisms are included in the proposed approach: Relay Set (RS), Neighbor Coverage (NC), and Transmission Order (TO). RS is a sender-based mechanism in which the sending node of the broadcast message determines the relay set of its neighbors for rebroadcast according to the radio coverage of the neighbors. The idea of the received-based NC is: a node receiving a broadcast message does not have to rebroadcast the message if all its neighbors have received the same message. TO mechanism requires a farther neighbor node away from the sending node to rebroadcast the message earlier than closer nodes so that a closer node may have more chances to save the rebroadcast. Simulation results have shown that the proposed approach ‘RS+NC+TO’ has a better performance than existing solutions like threshold-based schemes and angle-based scheme in terms of 100% reachability, more saved rebroadcast, and shorter average latency. 相似文献
11.
We consider deterministic broadcasting in radio networks whose nodes have full topological information about the network. The aim is to design a polynomial algorithm, which, given a graph G with source s, produces a fast broadcast scheme in the radio network represented by G. The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only possible to get an approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcast scheme of length , for every n-node graph of diameter D, thus improving a result of Gąsieniec et al. (PODC 2005) [17] and solving a problem stated there. Unless the inclusion NP BPTIME( holds, the length of a polynomially constructible deterministic broadcast scheme is optimal.A preliminary version of this paper (with a weaker result) appeared in the Proc. 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’2004), August 2004, Harvard University, Cambridge, USA, LNCS 3122, 171–182. Research of the second author supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais. Part of this work was done during the second author’s visit at the Max-Planck-Institut für Informatik. 相似文献
12.
For wireless mesh networks, it is critical to allocate the limited number of radio channels efficiently while mitigating the co-channel inference to improve network performance. For this reason, after extensively reviewing the related work, we present a new joint radio channel allocation (RCA) and power control (PC) strategy for wireless mesh networks. First, we formulate the RCA problem as a multiple objective optimization problem, with the constraints of transmission power and traffic data rates, while effective channel utilization (ECU) is chosen as the target metric for optimization. Second, we incorporate the channel status into the model of MAC protocols, including as signal-to-noise ratio (SNR) and transmission power. Consequently, the PC is incorporated into the ECU for channel allocation. Third, we propose to directly maximize the ECU to find both optimal radio channel and transmission power. The resulting strategy is a fully distributed RCA/PC algorithm without relying on a coordination mechanism among mesh routers. Our extensive simulation results have demonstrated that the proposed algorithm significantly outperforms the existing RCA strategies and the standard MAC protocols in performance such as throughput, packet dropping, delay and delay jitter. 相似文献
13.
We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the
topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working
in expected time
in n-node radio networks of diameter D, which is optimal, as it matches the lower bounds of Alon et al. [1] and Kushilevitz and Mansour [16]. Our algorithm improves
the best previously known randomized broadcasting algorithm of Bar-Yehuda, Goldreich and Itai [3], running in expected time
. (In fact, our result holds also in the setting of n-node directed radio networks of radius D.) For deterministic broadcasting, we show the lower bound
on broadcasting time in n-node radio networks of diameter D. This implies previously known lower bounds of Bar-Yehuda, Goldreich and Itai [3] and Bruschi and Del Pinto [5], and is sharper
than any of them in many cases. We also give an algorithm working in time
, thus shrinking - for the first time - the gap between the upper and the lower bound on deterministic broadcasting time to
a logarithmic factor.
Received: 1 August 2003, Accepted: 18 March 2005, Published online: 15 June 2005
Dariusz R. Kowalski: This work was done during the stay of Dariusz Kowalski at the Research Chair in Distributed Computing
of the Université du Québec en Outaouais, as a postdoctoral fellow. Research supported in part by KBN grant 4T11C04425.
Andrzej Pelc: Research of Andrzej Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed
Computing of the Université du Québec en Outaouais. 相似文献
14.
We consider ad hoc radio networks in which each node knows only its own identity but is unaware of the topology of the network, or of any bound on its size or diameter. Acknowledged broadcasting (AB) is a communication task consisting in transmitting a message from a distinguished source to all other nodes of the network and making this fact common knowledge among all nodes. To do this, the underlying directed graph must be strongly connected. Working in a model allowing all nodes to transmit spontaneously even before getting the source message, Chlebus et al. [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] proved that AB is impossible, if collision detection is not available, and gave an AB algorithm using collision detection that works in time O(nD) where n is the number of nodes and D is the eccentricity of the source. Uchida et al. [J. Uchida, W. Chen, K. Wada, Acknowledged broadcasting and gossiping in ad hoc radio networks, Theoret. Comput. Sci. 377 (2007) 43-54] showed an AB algorithm without collision detection working in time O(n4/3log10/3n) for all strongly connected networks of size at least 2. In particular, it follows that the impossibility result from [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] is really caused by the singleton network for which AB amounts to realize that the source is alone. We improve those two results by presenting two generic AB algorithms using a broadcasting algorithm without acknowledgement, as a procedure. For a large class of broadcasting algorithms the resulting AB algorithm has the same time complexity. Using the currently best known broadcasting algorithms, we obtain an AB algorithm with collision detection working in time O(min{nlog2D,nlognloglogn}), for arbitrary strongly connected networks, and an AB algorithm without collision detection working in time O(nlognloglogn) for all strongly connected networks of size n?2. Moreover, we show that in the model in which only nodes that already got the source message can transmit, AB is infeasible in a strong sense: for any AB algorithm there exists an infinite family of networks for which this algorithm is incorrect. 相似文献
15.
16.
Rachid Guerraoui 《Distributed Computing》2002,15(1):17-25
This paper addresses the Non-Blocking Atomic Commit (NB-AC) problem in asynchronous distributed systems augmented with failure
detectors. We first show that, in these systems, NB-AC and Consensus are incomparable. Roughly speaking, there is a failure
detector that solves NB-AC but not Consensus and a failure detector that solves Consensus but not NB-AC. Then we introduce
the Anonymously Perfect failure detector . We show that, to solve NB-AC, is necessary (while is not), whereas is sufficient when a majority of the processes are correct. We draw from our results some observations on the practical solvability
of NB-AC.
Received: August 2000 / Accepted: May 2001 相似文献
17.
Andrzej Pelc 《Distributed Computing》2007,19(5-6):361-371
We consider the task of activating an anonymous ad hoc radio network from a single source, by a deterministic algorithm. In
the beginning only the source is active and has to activate other nodes by disseminating messages throughout the network.
Nodes of the network do not know its topology and they do not have distinct labels. In such networks some nodes are impossible
to reach. A node in a network is accessible if it can be activated by some (possibly network-dependent) deterministic algorithm. We show that the problem of recognizing
whether a given node of an anonymous radio network is accessible, can be solved in polynomial time for the synchronous scenario.
A deterministic wake-up algorithm for ad hoc networks is universal if it activates all accessible nodes in all networks. We study the question of the existence of such a universal activating
algorithm. For synchronous communication we design a universal activating algorithm, and for asynchronous communication we
show that no such algorithm exists.
Research partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université
du Québec en Outaouais.
A preliminary version of this paper (with title “Waking up anonymous ad hoc radio networks”) appeared in the Proceedings of
the 19th International Symposium on Distributed Computing (DISC 2005), September 2005, Cracow, Poland. 相似文献
18.
19.
20.
A primary goal of broadcasting in vehicular ad hoc network (VANET) is to improve the road safety by transmitting alert messages to all surrounding vehicles as soon as possible. In this paper, we adopt the concept of opportunistic routing and propose a multiple candidate relays opportunistic broadcast (MCROB) protocol for VANET. The MCROB protocol is a sender-driven broadcast scheme independent of node density. The packet delivery ratio (PDR) is derived and an expected transmission speed (ETS) for the MCROB is proposed. A priority rule for selecting a proper candidate relay and an adaptive algorithm for forwarding timers of candidate relays are also presented in this paper. Simulations show that MCROB is adaptive to the rapid changing of network conditions. It keeps a low communication overhead introduced by the broadcast and increases the average transmission speed by around 40%. 相似文献