• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文OA文献 >Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
【2h】

Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time

机译：局部多值算法：在恒定时间内计算几乎最优的TDma调度

页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We are given a set $V$ of autonomous agents (e.g. the computers of a distributed system) that are connected to each other by a graph $G=(V,E)$ (e.g. by a communication network connecting the agents). Assume that all agents have a unique ID between $1$ and $N$ for a parameter $Nge|V|$ and that each agent knows its ID as well as the IDs of its neighbors in $G$. Based on this limited information, every agent $v$ must autonomously compute a set of colors $S_vsubseteq C$ such that the color sets $S_u$ and $S_v$ of adjacent agents $u$ and $v$ are disjoint. We prove that there is a deterministic algorithm that uses a total of $|C|=ensuremath{mathcal{O}}(Delta^2log(N)/ensuremath{varepsilon}^2)$ colors such that for every node $v$ of $G$ (i.e., for every agent), we have $|S_v|ge |C|cdot(1-ensuremath{varepsilon})/(delta_v+1)$, where $delta_v$ is the degree of $v$ and where $Delta$ is the maximum degree of $G$. For $N=Omega(Delta^2logDelta)$, $Omega(Delta^2+loglog N)$ colors are necessary even to assign at least one color to every node (i.e., to compute a standard vertex coloring). Using randomization, it is possible to assign an $(1-ensuremath{varepsilon})/(delta+1)$-fraction of all colors to every node of degree $delta$ using only $ensuremath{mathcal{O}}(Deltalog|V|/ensuremath{varepsilon}^2)$ colors w.h.p. We show that this is asymptotically almost optimal. For graphs with maximum degree $Delta=Omega(log|V|)$, $Omega(Deltalog|V|/loglog|V|)$ colors are needed in expectation, even to compute a valid coloring.The described multicoloring problem has direct applications in the context of wireless ad hoc and sensor networks. In order to coordinate the access to the shared wireless medium, the nodes of such a network need to employ some medium access control (MAC) protocol. Typical MAC protocols control the access to the shared channel by time (TDMA), frequency (FDMA), or code division multiple access (CDMA) schemes. Many channel access schemes assign a fixed set of time slots, frequencies, or (orthogonal) codes to the nodes of a network such that nodes that interfere with each other receive disjoint sets of time slots, frequencies, or code sets. Finding a valid assignment of time slots, frequencies, or codes hence directly corresponds to computing a multicoloring of a graph $G$. The scarcity of bandwidth, energy, and computing resources in ad hoc and sensor networks, as well as the often highly dynamic nature of these networks require that the multicoloring can be computed based on as little and as local information as possible.
机译：我们给定了一组自治代理（例如分布式系统的计算机）$ V $，它们通过图形$ G =（V，E）$（例如通过连接代理的通信网络）相互连接。假设对于参数$ Nge | V | $，所有代理都具有介于$ 1 $和$ N $之间的唯一ID，并且每个代理都知道其ID以及其邻居在$ G $中的ID。基于此有限信息，每个代理$ v $必须自主计算一组颜色$ S_vsubseteq C $，以使相邻代理$ u $和$ v $的颜色集$ S_u $和$ S_v $不相交。我们证明存在一个确定性算法，该算法使用总计$ | C | = ensuremath {mathcal {O}}（Delta ^ 2log（N）/ ensuremath {varepsilon} ^ 2）$颜色，使得每个节点$ v $ $ G $（即每个代理）中，我们有$ | S_v | ge | C | cdot（1-ensuremath {varepsilon}）/（delta_v + 1）$，其中$ delta_v $是$ v $的度数其中$ Delta $是$ G $的最大程度。对于$ N = Omega（Delta ^ 2logDelta）$，甚至需要为每个节点分配至少一种颜色（即，计算标准顶点着色），也需要$ Omega（Delta ^ 2 + loglog N）$颜色。使用随机化，可以仅使用$ ensuremath {mathcal {O}}（Deltalog）将所有颜色的$（1-ensuremath {varepsilon}）/（delta + 1）$分数分配给度数$ delta $的每个节点| V | / ensuremath {varepsilon} ^ 2）$ colors whp我们证明这是渐近几乎最优的。对于最大度数为$ Delta = Omega（log | V |）$的图，期望甚至需要$ Omega（Deltalog | V | / loglog | V |）$颜色，甚至为了计算有效的颜色。所描述的多色问题直接存在无线ad hoc和传感器网络中的应用程序。为了协调对共享无线介质的访问，这种网络的节点需要采用某种介质访问控制（MAC）协议。典型的MAC协议通过时间（TDMA），频率（FDMA）或码分多址（CDMA）方案控制对共享信道的访问。许多信道访问方案将固定的一组时隙，频率或（正交）码分配给网络的节点，以使相互干扰的节点接收不相交的时隙，频率或码集。因此，找到时隙，频率或代码的有效分配直接对应于计算图形$ G $的多色。 Ad hoc和传感器网络中带宽，能量和计算资源的稀缺性以及这些网络通常具有高度动态性，这就要求可以根据尽可能少的本地信息来计算多色。

著录项

  • 作者

    Kuhn Fabian;

  • 作者单位
  • 年度 2009
  • 总页数
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 入库时间 2022-08-20 21:10:51

相似文献

  • 外文文献
  • 中文文献
  • 专利

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号