Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks
Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks
复制标题
DOI：
10.1007/s00446-022-00426-w
复制
发表时间：
2021-04
影响因子：
1.3
通讯作者：
Varsha Dani;Aayush Gupta;Thomas P. Hayes;Seth Pettie
中科院分区：
文献类型：
--
作者：
Varsha Dani;Aayush Gupta;Thomas P. Hayes;Seth Pettie
我们考虑由相互无线通信的小型自主设备组成的网络。在为此类网络设计算法时，最大限度地减少能耗是一个重要的考虑因素，因为电池寿命是一项关键且有限的资源。在发送和监听消息都消耗能量的模型中，我们考虑了在任意未知拓扑的无线网络中寻找节点的最大匹配的问题。我们提出了一种分布式随机化算法，该算法以高概率产生最大匹配。每个节点的最大能量成本为\Docentclass[12pt]{Minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$O\BIG(\log\Delta)\BIG)，$$\end{Document}，时间复杂度为。这里是节点数的任何上界，是最大次数的任何上界；我们假设算法的参数是所有处理器先验已知的。我们注意到，存在这样一类图族，对于这些图族，我们对能量成本和时间复杂性的界限同时是最优的，最高可达PolyLog因子，因此，任何显著的改进都需要关于网络拓扑的额外假设。我们还考虑了为网络中的每个节点分配一个邻居以在最终节点故障的情况下备份其数据的相关问题。这里的一个关键目标是最小化最大负载，该负载定义为分配给单个节点的节点数。提出了一种高效的分布式低能量分配算法，该算法找到一个最大负载最大为最优负载的PolyLog(N)因子的邻居分配。
We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology. We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\big ((\log n)(\log \Delta )\big ),$$\end{document} and the time complexity is. Herenis any upper bound on the number of nodes, andis any upper bound on the maximum degree;nandare parameters of our algorithm that we assume are known a priori to all the processors. We note that there exist families of graphs for which our bounds on energy cost and time complexity are simultaneously optimal up to polylog factors, so any significant improvement would need additional assumptions about the network topology. We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of eventual node failure. Here, a key goal is to minimize the maximumload, defined as the number of nodes assigned to a single node. We present an efficient decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog (n) factor bigger that the optimum.