A Depth-optimal Low-complexity Distributed Wireless Multicast Algorithm

Download
2011-06-01
Akyurek, A. Sinan
Uysal, Elif
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.
COMPUTER JOURNAL

Suggestions

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.