检索结果-内蒙古大学图书馆

Efficient and competitive broadcast in multi-channel radio networks

INFORMATION AND COMPUTATION 2022年第PartA期289卷

作者： Chen, Haimin Zheng, Chaodong Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China

Consider a single-hop, multi-channel, synchronous radio network in which a source node needs to disseminate a message to all other n -1 nodes. An adversary called Eve, which captures environmental noise and potentially malicious interference, aims to disrupt this process via jamming. Assume sending, listening, or jamming on one channel for one time slot costs one unit of energy. The question is, if Eve spends T units of energy on jamming, can we devise broadcast algorithms in which each node's cost is o(T)? Previous results show such resource competitive algorithms do exist in the single-channel setting: for large T values, each node can receive the message within O(T) time slots while spending only O tilde (root T/n) *** this work, we devise new broadcast algorithms and show that the existence of multiple channels allows faster message dissemination while preserving resource competitiveness. Specifically, if C channels are available, for large T values, our algorithms guarantee each node's runtime is O(T/C), and each node's energy cost is O tilde (root T /n). Moreover, our algorithms require minimal prior knowledge and allow Eve to be adaptive. Our technical contributions lie in using "epidemic broadcast" in algorithm design to achieve time efficiency and resource competitiveness, and employing coupling techniques in the analysis to handle the adaptivity of the *** also complement algorithmic results with lower bounds, proving both the time complexity and the energy complexity of our algorithms are optimal or near-optimal. In particular, to obtain the lower bound on resource competitiveness, we first prove a new lower bound showing any multi-channel 1-to-1 communication algorithm succeeding with root constant probability incurs expected cost of at least S2( T);then, via simulation and reduction arguments, we show for the broadcast problem, some node incurs a cost of at least S2(root T/n), even in the multi-channel setting.(c) 2022 Published by Elsevi

关键词： Broadcast Radio networks Distributed algorithms resource competitive algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast and resource competitive Broadcast in Multi-channel Radio Networks 19

Fast and Resource Competitive Broadcast in Multi-channel Rad...

引用

31st ACM Symposium on Parallelism in algorithms and Architecturess (SPAA)

作者： Chen, Haimin Zheng, Chaodong Nanjing Univ State Key Lab Novel Software Technol Nanjing Peoples R China

ISBN: (纸本)9781450361842

Consider a single -hop, multi-channel, synchronous radio network in which a source node needs to disseminate a message to all other n-1 nodes. An adversary called Eve, which captures environmental noise and potentially malicious interference, aims to disrupt this process via jamming. Assume sending, listening, or jamming on one channel for one time slot costs unit energy. The question is, if Eve spends T units of energy on jamming, can we devise broadcast algorithms in which each node's cost is o(T)? Previous results show such resource competitive algorithms do exist in the single -channel setting: each node can receive the message within 0(T + n) time slots while spending only 6(--T\/71 + 1) energy. In this paper, we show that when Eve is oblivious, the existence of multiple channels allows even faster message dissemination, while preserving resource competitiveness. Specifically, we have identified an efficient "epidemic broadcast" scheme in the multichannel setting that is robust against jamming. Extending this scheme leads to a randomized algorithm called MULTICAST which uses n/2 channels, and accomplishes broadcast in O(T/n + 1) time slots while costing each node only + 1) energy. When the value of n is unknown, we further propose MULTICASTADV, in which each node's running time is a(T / (n1 -2a) + n2a), and each node's cost is O( VT + n2a). Here, 0 < a < 1/4 is a tunable parameter affecting the constant hiding behind the big-O notation. To handle the issue of limited channel availability, we have also devised variants for both MULTICAST and MULTICASTADV that can work in networks in which only C channels are available, for any C > 1. These variants remain to be resource competitive, and have (near) optimal time complexity in many cases.

关键词： broadcast wireless networks resource competitive algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：