多比

b'我们考虑由小型、自主设备组成的网络，这些设备通过无线通信相互通信。在为此类网络设计算法时，最小化能耗是一个重要的考虑因素，因为电池寿命是一种至关重要的有限资源。在发送和侦听消息都会消耗能量的模型中，我们考虑在任意未知拓扑的无线电网络中寻找节点最大匹配的问题。我们提出了一种分布式随机算法，该算法以高概率产生最大匹配。每个节点的最大能量成本为 O (log n )(log \xe2\x88\x86) ，时间复杂度为 O (\xe2\x88\x86log n )。这里 n 是节点数量的任意上限，\xe2\x88\x86是最大度数的任意上限； n 和 \xe2\x88\x86 是我们算法的参数，我们假设它们对所有处理器都是先验已知的。我们注意到，存在一些图族，对于这些图族，我们对能量成本和时间复杂度的界限同时达到多项对数因子的最优，因此任何显著的\xef\xac\x81 改进都需要对网络拓扑做出额外的假设。我们还考虑了相关问题，即为网络中的每个节点分配一个邻居，以便在最终节点发生故障时备份其数据。在这里，一个关键目标是最小化最大负载，定义为分配给单个节点的节点数。我们提出了一种有效的分散式低能耗算法，该算法确定一个邻居分配，其最大负载最多比最优值大一个多项对数 (n) 因子。'

b'我们考虑由小型、自主设备组成的网络，这些设备通过无线通信相互通信。在为此类网络设计算法时，最小化能耗是一个重要的考虑因素，因为电池寿命是一种至关重要的有限资源。在发送和侦听消息都会消耗能量的模型中，我们考虑在任意未知拓扑的无线电网络中寻找节点最大匹配的问题。我们提出了一种分布式随机算法，该算法以高概率产生最大匹配。每个节点的最大能量成本为 O (log n )(log \xe2\x88\x86) ，时间复杂度为 O (\xe2\x88\x86log n )。这里 n 是节点数量的任意上限，\xe2\x88\x86是最大度数的任意上限； n 和 \xe2\x88\x86 是我们算法的参数，我们假设它们对所有处理器都是先验已知的。我们注意到，存在一些图族，对于这些图族，我们对能量成本和时间复杂度的界限同时达到多项对数因子的最优，因此任何显著的\xef\xac\x81 改进都需要对网络拓扑做出额外的假设。我们还考虑了相关问题，即为网络中的每个节点分配一个邻居，以便在最终节点发生故障时备份其数据。在这里，一个关键目标是最小化最大负载，定义为分配给单个节点的节点数。我们提出了一种有效的分散式低能耗算法，该算法确定一个邻居分配，其最大负载最多比最优值大一个多项对数 (n) 因子。'