A Depth-optimal Low-complexity Distributed Wireless Multicast Algorithm

Download

index.pdf

Date

2011-06-01

Author

Akyurek, A. Sinan
Uysal, Elif

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

156
views

0
downloads

This paper presents a wireless multicast tree construction algorithm, SWIM (Source-initiated WIreless Multicast). SWIM constructs a tree on which each multicast destination has the minimum possible depth (number of hops from the nearest source). It is proved that SWIM is fully distributed, with a worst case complexity upper-bounded by O(N-3), and an empirically found average complexity of only O(N-2). SWIM forms one shared tree from source(s) to the multicast destinations; yet, as a by-product, it creates a multicast mesh structure by maintaining alternative branches at every tree node, thus providing robustness to link failures. This makes it suitable for both ad hoc networks and access networks with multiple gateways. In terms of minimizing the number of forwarding nodes, SWIM is optimal for unicast and competitive with the state of the art for multicast, outperforming the best known distributed approaches from the literature except for the multicast ad hoc on demand distance vector (MAODV) algorithm. However, simulations of the MAODV algorithm alongside SWIM on a large set of network instances show that the depth minimality of SWIM leads to lower average delay per multicast destination. It is also shown that the delay performance of SWIM is virtually unaffected by the presence of low mobility in the network.

Subject Keywords

General Computer Science

URI

https://hdl.handle.net/11511/39670

Journal

COMPUTER JOURNAL

DOI

https://doi.org/10.1093/comjnl/bxr023

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

A Cascadable Random Neural Network Chip with Reconfigurable Topology Badaroglu, Mustafa; Halıcı, Uğur; Aybay, Isik; Cerkez, Cuneyt (Oxford University Press (OUP), 2010-03-01) A digital integrated circuit (IC) is realized using the random neural network (RNN) model introduced by Gelenbe. The RNN IC employs both configurable routing and random signaling. In this paper we present the networking/routing aspects as well as the performance results of an RNN network implemented by the RNN IC. In the RNN model, each neuron accumulates arriving signals and can fire if its potential at a given instant of time is strictly positive. Firing occurs at random, the intervals between successive ...
Parallel Scalable PDE Constrained Optimization Antenna Identification in Hyperthermia Cancer Treatment Planning SCHENK, Olaf; Manguoğlu, Murat; CHRİSTEN, Matthias; SATHE, Madan (Springer Science and Business Media LLC, 2009-01-01) We present a PDE-constrained optimization algorithm which is designed for parallel scalability on distributed-memory architectures with thousands of cores. The method is based on a line-search interior-point algorithm for large-scale continuous optimization, it is matrix-free in that it does not require the factorization of derivative matrices. Instead, it uses a new parallel and robust iterative linear solver on distributed-memory architectures. We will show almost linear parallel scalability results for t...
A unifying grid approach for solving potential flows applicable to structured and unstructured grid configurations Cete, A. Ruhsen; Yuekselen, M. Adil; Kaynak, Uenver (Elsevier BV, 2008-01-01) In this study, an efficient numerical method is proposed for unifying the structured and unstructured grid approaches for solving the potential flows. The new method, named as the "alternating cell directions implicit - ACDI", solves for the structured and unstructured grid configurations equally well. The new method in effect applies a line implicit method similar to the Line Gauss Seidel scheme for complex unstructured grids including mixed type quadrilateral and triangle cells. To this end, designated al...
Optimum design of grillage systems using harmony search algorithm Erdal, Ferhat; Saka, Mehmet Polat; Department of Engineering Sciences (2007) Harmony search method based optimum design algorithm is presented for the grillage systems. This numerical optimization technique imitates the musical performance process that takes place when a musician searches for a better state of harmony. For instance, jazz improvisation seeks to find musically pleasing harmony similar to the optimum design process which seeks to find the optimum solution. The design algorithm considers the displacement and strength constraints which are implemented from LRFD-AISC (Loa...
Asymptotically Throughput Optimal Scheduling for Energy Harvesting Wireless Sensor Networks Gul, Omer Melih; Demirekler, Mubeccel (Institute of Electrical and Electronics Engineers (IEEE), 2018) In this paper, we investigate a single-hop wireless sensor network in which a fusion center (FC) collects data packets from M energy harvesting (EH) sensor nodes. Energy harvested by each node is stored without battery overflow and leakage at that node. The FC schedules K nodes over its mutually orthogonal channels to receive data from them in each time slot. The FC knows neither the statistics of EH processes nor the battery states of nodes. The FC solely has information on consequences of previous transmi...

Citation Formats

A. S. Akyurek and E. Uysal, “A Depth-optimal Low-complexity Distributed Wireless Multicast Algorithm,” COMPUTER JOURNAL, pp. 988–1003, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/39670.