科研速递 | 理工学院杨升浩团队在信息论领域权威期刊IEEE TIT上发表文章

近日，香港中文大学（深圳）理工学院杨升浩团队在信息论领域权威期刊IEEE Transactions on Information Theory上发表了题为“Wireless Network Scheduling with Discrete Propagation Delays: Theorems and Algorithms”的论文。该论文的作者包括杨升浩、马骏和刘延骁。

论文提出了一套理论框架，用于描述考虑信号传输延迟的无线网络调度，并提供了一套算法来计算最优调度方案。这一研究填补了考虑信号传输延迟的网络调度缺乏理论指导的空白。

论文链接：

https://doi.org/10.1109/TIT.2023.3324180

期刊介绍

IEEE Transactions on Information Theory (TIT) 是一本专注于信息理论和相关领域研究的期刊，被广泛认可为信息论领域最具权威性的期刊之一，享有卓越的学术声誉。该期刊发表了许多在信息论和编码理论等领域具有重要意义的经典研究成果。

研究背景

我们可以用一个圆桌会议来比喻无线通信中的干扰问题。假设有二十个人围绕圆桌而坐，每个人都想与对面的人进行对话。如果每个人都同时讲话，由于其他人的干扰，每个人都很难听清对面人的讲话。为了避免干扰，每个时间段只能有一对相对而坐的人在通话。

然而，如果考虑到声波通信的延迟，理论上存在一种方法可以让二十个人同时讲话而不产生干扰。假设两个人进行通话，他们之间的声波传输延迟为T。我们可以将时间分成连续的T长时间段，让两个人在奇数时间段同时讲话，并在偶数时间段倾听。这样，他们都可以无干扰地听到对方的话。即使将时间段分成T的整数分之一，也可以达到相同的效果。

尽管在实际对话中很难实现这种方式，但它有潜力提高通信系统的效率。为了简化问题，我们做一个假设：圆桌正对面两个人之间的声波传输延迟是某个时长T的奇数倍，而非正对面的两个人之间的声波传输延迟是T的偶数倍。将时间分成T长的连续时间段，让所有人在奇数时间段讲话、偶数时间段倾听。这样，所有的通话都不会受到干扰。这种方法可以将通信效率提高10倍！

这种利用信号传输延迟来提高通信效率的潜力在十多年前就被认识到了，能够应用于水下声波通信、毫米波、太赫兹频段的无线通信以及深空通信等场景。然而，对于一般的无线通信网络，信号延迟并不会像上述例子中假设的那样特殊。因此，如何设计最优的网络调度仍然是一个待解决的问题。

研究历程

作为马骏的博士研究课题，团队从2017年开始涉足考虑信号传输延迟的网络调度问题。通过挖掘该问题与周期性图的关系，团队提出了一套全新的方法来解决这个问题：将考虑时延的调度问题等价于在调度图中找到一个环。基于这一方法，在理论上能够找到所有可能的调度方案并计算最优的调度。相关论文于2021年发表于计算机网络领域的顶级国际会议INFOCOM。

在随后的研究中，团队进一步探索了调度图的特性，并提出了一系列简化的调度计算方法。这些进一步的研究工作加深了对考虑延迟调度问题的理解，并为解决调度问题提供了更具实用性的方法。作为一项基础性的理论研究，本论文的研究成果也能够应用于其他领域，例如解决周期性图的独立集问题以及在运筹学中涉及时间关联性的调度问题等。

作者简介

本文第一作者为理工学院杨升浩副教授。

杨升浩教授是香港中文大学（深圳）理工学院的副教授。他于2001年获得南开大学的学士学位，2004年获得北京大学的硕士学位，2008年获得香港中文大学的信息工程博士学位。他曾在加拿大滑铁卢大学（2008-2009）和香港中文大学网络编码研究所（2010-2012）从事博士后研究。在2012年至2015年期间，他任教于清华大学交叉信息研究院。2015年加入香港中文大学（深圳）。他的研究兴趣包括信息论、编码理论和量子信息等领域。他已发表了70多篇论文，并获得了10多项专利授权，其中多项专利已经转让或授权。

本文的第二作者为厦门大学管理学院的博士后研究人员马骏博士。

马骏于2021年在香港中文大学（深圳）获得博士学位。本论文的研究成果是在马骏的博士论文的基础上进一步发展而来的。

本文的第三作者为刘延骁。

刘延骁目前正在香港中文大学攻读信息工程系的博士学位。他是香港中文大学（深圳）2021届电子与信息工程专业的毕业生，在本科阶段就参与了本课题的研究工作。他的研究方向主要集中在信息论和无线通信领域，包括有限码长的信息论、网络信息论、信息安全和无线通信网络调度等方面。

供稿 | 杨升浩教授团队

  排版 | 郑一旻 （理工学院 道扬书院）

点击以下链接，进入理工时刻：