Algorithmic problems emerging in new networking technologies

新网络技术中出现的算法问题

• 批准号: RGPIN-2018-03900
• 负责人: Stacho, Ladislav
• 金额: $ 2.04万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=682074
• 关键词: Algorithmic; problems; emerging; new; networking

Over the past few years, my research interests centered around three main areas: theoretical aspects and algorithms for communication in interconnection networks, computational biology, and graph theory. In the future I expect to continue to be active in all three areas, however I will focus on problems related to the first area as problems emerging from fascinating new technologies often utilize methods from combinatorics, graph theory, computational geometry, design theory, and algebraic combinatorics that are main tools in my research.******In particular, I want to focus, but not restrict, on ad-hoc, sensor, and social networks. My goal is to build on my expertise, develop techniques, and answer some of the emerging questions. I briefly describe some of them in what follows.******1) Modern networks of all kinds may have millions of nodes and connections and, in fact, many of them may not be even present at a time. It is impossible to utilize classical algorithms to solve problems on such networks. In past years, local algorithms that utilize a robot moving on the network and at each step the robot can use only a local portion of the network have been proposed for several fundamental problems. Traversal, or s,t-connectivity, is one of such fundamental problems and has been extensively studied for many years. In a seminal work, Omer Reingold showed that there is a local algorithm that solves s,t-connectivity in log n space provided we know n the number of nodes in the network. If we allow for extra information, for example geometric (nodes of network will have coordinates available to the robot geometric graphs), then much stronger local traversal can be guaranteed. I propose to continue my research in this direction.******2) Some of the techniques for local traversal on geometric graphs that I have developed required the geometric graph to satisfy certain structural condition. I propose to relax this conditions by over-imposing a "virtual" network that will consist of virtual nodes and connections, and will be build by the robot in its memory and will guarantee that the structural condition in the "union" of the two networks is satisfied. The virtual network will be regular, for example a grid, so that it can be computed and amalgamated with the existing local part of the network. This is a new approach that I believe will be very useful in approaching many network problems in local way. ******3) The maze traversal algorithms have been extensively studied in literature. With current technology advent and initiatives moving towards mapping and navigating interior, such algorithms are gaining more and more popularity. I propose to study problems of maze traversal with very simple and limited robots when the maze is unknown or when the position of robot in the maze is unknown.

在过去的几年里，我的研究兴趣集中在三个主要领域：互连网络中通信的理论方面和算法，计算生物学和图论。在未来，我希望继续活跃在这三个领域，但我将专注于与第一个领域相关的问题，因为从迷人的新技术中出现的问题通常使用组合学，图论，计算几何，设计理论和代数组合学的方法，这些方法是我研究的主要工具。特别是，我想集中，但不限于，ad-hoc，传感器和社交网络。我的目标是建立在我的专业知识，开发技术，并回答一些新出现的问题。我在下面简要介绍其中的一些。* 1)现代各种网络可能有数百万个节点和连接，事实上，其中许多节点和连接可能一次都不存在。这是不可能利用经典的算法来解决这样的网络上的问题。在过去的几年中，本地算法，利用机器人在网络上移动，并在每一步的机器人可以使用网络的本地部分已经提出了几个基本问题。traffic或s，t-连通性是这些基本问题之一，多年来一直被广泛研究。在一个开创性的工作，奥默Reingold表明，有一个本地算法，解决了s，t-连接在log n空间提供我们知道n的节点数在网络中。如果我们允许额外的信息，例如几何（网络节点将具有可用于机器人几何图形的坐标），则可以保证更强的局部遍历。我想继续我的研究方向 *。2)我开发的一些几何图局部遍历技术要求几何图满足一定的结构条件。我建议放宽这一条件，通过过度强加一个“虚拟”网络，将包括虚拟节点和连接，并将由机器人在其内存中建立，并将保证在“联盟”的两个网络的结构条件得到满足。虚拟网络将是规则的，例如网格，使得它可以被计算并与网络的现有本地部分合并。这是一种新的方法，我相信在以本地方式处理许多网络问题时会非常有用。**3）迷宫遍历算法在文献中已经被广泛研究。随着当前技术的出现和朝向内部映射和导航的倡议，这样的算法越来越受欢迎。我建议研究问题的迷宫遍历非常简单和有限的机器人时，迷宫是未知的或机器人在迷宫中的位置是未知的。