近日，香港中文大學（深圳）理工學院楊升浩團隊在信息論領域權威期刊IEEE on Theory上發表了題為“ Network with Delays: and ”的論文。該論文的作者包括楊升浩、馬駿和劉延驍。

論文提出了一套理論框架，用于描述考慮信號傳輸延遲的無線網絡調度，并提供了一套算法來計算最優調度方案。這一研究填補了考慮信號傳輸延遲的網絡調度缺乏理論指導的空白。

論文鏈接：

期刊介紹

IEEE on 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屆電子與信息工程專業的畢業生，在本科階段就參與了本課題的研究工作。他的研究方向主要集中在信息論和無線通信領域，包括有限碼長的信息論、網絡信息論、信息安全和無線通信網絡調度等方面。

供稿 | 楊升浩教授團隊

排版 | 鄭一旻 （理工學院 道揚書院）

點擊以下鏈接，進入理工時刻：