多无线网络共存条件下分布式计算原语的算法理论研究

As a typical distributed system, wireless networks are under rapid development. However, due to the open and shared nature of wireless communication, nodes in wireless networks can easily interfere with each other, degrading the performance of the computation running within the network. To mitigate this problem, in recent years, researchers have proposed several new methods and approaches. This project aims to deepen our understanding towards these new ideas, so as to achieve efficient distributed computing even when multiple wireless networks coexist --- a challenging scenario that is particularly vulnerable to interference...This project includes two major topics: develop distributed algorithms for the emerging cognitive radio networks; and develop resource competitive distributed algorithms for traditional wireless networks. More specifically, we will use randomized algorithms as our primary algorithmic tool, and focus on providing fundamental distributed computing primitives such as neighbor discovery, broadcast, and consensus. For instance, by using random frequency hopping, approximate counting, and edge coloring, it is possible to achieve efficient neighbor discovery and global broadcast in cognitive radio networks. It also seems feasible to derive lower bounds for these problems by studying a combinatorial game called “bipartite graph matching hitting”. On the other hand, in traditional wireless networks, epidemic broadcast may enable resource competitive broadcast; and we also intend to develop resource competitive consensus algorithms in such setting...This project focus on theoretic analysis, which would guarantee the proposed algorithms’ performance even in the worst case. Moreover, we pay attention to the study of lower bounds, which would enrich our understanding towards the nature of the considered problems, and help to examine whether the developed algorithms are close to (or have reached) the optimal.

无线网络作为一典型的分布式系统，正在持续的快速发展。然而，无线通信开放和共享的特性使节点间易于相互干扰，影响网络中计算的效率。本项目将探索一些用于缓解该问题的新兴思路，以期高效的实现多无线网络共存条件下的分布式计算。本项目主要研究内容为认知无线电网络中的分布式算法，以及具有资源竞效特性的分布式算法。本项目关注的具体问题包括邻居发现、广播、共识等分布式计算原语。本项目使用的主要工具为随机算法，强调理论分析，可保证算法复杂度上界。同时，有意探索解决问题所需的复杂度下界，以加深对问题本质的认识，并检验算法是否接近或达到最优。具体来说，准备使用随机跳频、近似计数、边着色等技术实现认知无线电网络中的邻居发现与全网广播，并通过分析“猜测二分图匹配”问题推导上述问题的复杂度下界。另一方面，准备使用“流行病广播”思想实现多信道无线网络中具有资源竞效特性的广播，并尝试设计具有资源竞效特性的共识算法。

无线网络作为一种典型的分布式系统，正在持续的快速发展。然而，无线通信开放和共享的特性使节点间易于相互干扰，影响网络中计算的效率。本项目探索了一些用于缓解该问题的新兴思路，有助于高效的实现多无线网络共存条件下的分布式计算。具体来说，针对认知无线电网络这一新型无线分布式系统，使用近似计数、边着色等技术设计了高效的邻居发现算法与全网广播算法；针对传统的多信道无线网络，使用“流行病广播”思想设计了具有资源竞效特性的抗干扰广播算法，并在算法分析过程中使用耦合技术克服了在线敌手带来的困难。通过推导复杂性下界，进一步证明了上面的算法在很多情况下已经接近或达到渐近最优性能。受上述研究工作启发，项目还对无线网络中的近似邻居计数问题进行了全面深入的研究，得到了一批算法上界以及对应的复杂性下界；这基本标志着无线网络中的近似邻居计数问题已经被完全解决。项目研究成果形成了多篇高水平论文，发表在PODC、SPAA等并行与分布式计算理论的顶级会议上。