kumoh national institute of technology
Networked Systems Lab.

Research Presentation

NSL> Works@NSL> Research Presentation
A Low Complexity Distributed Algorithm for Computing Minimum-Depth Multicast Trees in Wireless Networks
By : Thanh Ngo
Date : 2013-11-14
Views : 554

Abstract—This paper presents a wireless multicast tree construction algorithm, SWIM (Source-initiated WIreless Multicast). SWIM forms one shared tree from source(s) to the multicast destinations; yet, as a side 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. It is proved that SWIMis fully distributed, with a worst case complexity (for multicast) upper-bounded by O(N^3), and average complexity of only O(N^2). SWIM constructs a tree on which each multicast destination has the minimum possible depth (number of hops from the nearest source). In terms of minimizing the number of forwarding nodes (NFN), SWIM is optimal for unicast. Its average NFN in the broadcast and multicast cases is compared with practical algorithms targeting low NFN reported in the literature. In both multicast and unicast, SWIM performs competitively in terms of NFN with the previous solutions, while having smaller maximum depth, and consequently low delay.

Attachment 1:   첨부파일 A low complexity distributed algorithm.pdf(1.4MB)  
(Total:27 articles / page:1/3 )