基于信息年齡優化的多信道無線網絡調度方法

王 恒 段思勰 謝 鑫②

①(重慶郵電大學工業物聯網與網絡化控制教育部重點實驗室 重慶 400065)

②(重慶郵電大學通信與信息工程學院 重慶 400065)

1 引言

隨著無線網絡技術的發展，數據交付的及時性對一些實時性要求較高的應用顯得尤為重要。例如，在自動駕駛場景中，及時地傳輸汽車的速度、位置信息對汽車行駛的安全問題十分關鍵[1]；化工生產場景中，實時的現場數據是安全生產的基本保障；環境監控場景中，環境溫度、語音視頻等一些數據交付的及時性直接影響用戶是否能及時做出正確的決策[2]。因此，如何提高時間敏感類應用中數據交付的及時性，成為無線網絡研究所面臨的重要挑戰。

信息年齡(Age of Information, AoI)是新近提出的一種評價數據及時性的度量標準，用以從目標節點的角度衡量數據的新鮮程度，表示為目標節點最新接收到的數據包自其生成以來所經過的時間[3]。相較于傳統的衡量數據及時性度量標準，AoI的刻畫更加全面。例如，時延是從數據包本身的角度出發，度量數據包從網絡中一端發送到另一端的過程中經歷的時間。而AoI的度量則除了數據包的時延部分，還包括了數據包在數據源由于沒有及時被調度，以及在目標節點沒有進行更新而帶來的停留時間。因此，AoI的大小刻畫了目標節點最近接收到的數據包的新鮮程度，通過對網絡中的AoI進行優化，能夠更好地滿足網絡對數據交付及時性的要求。

近年來，眾多學者以AoI為優化目標，從不同隊列模型、數據更新方式、鏈路調度等角度展開相關研究[3-10]。尤其是在多用戶無線網絡場景中，最小化平均AoI的鏈路調度問題受到了重點關注，主要集中于單信道無線網絡系統進行研究[7-10]。而在現實中，多信道機制也是無線網絡系統中廣泛使用的通信技術。例如，以工業無線傳感器網絡為設計對象的工業無線網絡標準技術(Wireless networks for Industrial Automation Process Automation,WIA-PA)、無線可尋址遠程傳感器高速通道的開放通信標準(Wireless Highway Addressable Remote Transducer, WirelessHART)等國際標準普遍采用了多信道通信技術，能夠利用多條信道進行數據傳輸，有效提升無線網絡的容量和性能[11]。由于多信道無線網絡中存在信道沖突和鏈路沖突等問題，因此AoI鏈路調度策略的設計更加復雜。

面對這一挑戰，本文基于存在信道沖突和鏈路沖突約束的多信道無線網絡，綜合運用李雅普諾夫偏移調度方法和Kuhn-Munkres(KM)匹配算法，提出最小化平均AoI的在線鏈路調度算法，有效地提高網絡的實時性。

2 相關工作

AoI作為一種新的度量指標，最初由Kaul等人[3]引入，用以從目標節點的角度量化數據的新鮮度。自此以后，學術界結合不同的排隊模型，從源更新頻率、服務率等方向展開了AoI相關的理論研究；并且在無線網絡場景中，綜合考慮了信道狀態、吞吐量、能量等因素，對優化AoI的調度方法進行了廣泛而深入的研究。Kaul等人[3]結合排隊論研究了AoI的計算和迭代過程，并在隨機調度策略下給出了平均AoI與服務率、到達率間的解析式。Kam等人[4]探究了固定截止時間約束和隨機指數截止時間約束下，服務率對平均AoI的影響。文獻[5,6]在單源單目的地的邊緣計算場景下，分析了不同計算模式下的AoI。而在無線網絡的鏈路調度方面，文獻[7]研究了周期性數據更新下逐時隙鏈路調度的問題，提出了隨機、貪婪、李雅普諾夫優化、Whittle Index等策略進行鏈路調度以優化網絡的平均AoI。文獻[8]針對數據隨機到達的場景，基于馬爾可夫決策過程分別提出了離線和在線調度算法。文獻[9]和文獻[10]分別研究了在吞吐量約束和能量約束下的優化AoI的鏈路調度問題。

上述文獻[7-10]均是在單信道網絡場景中對AoI鏈路調度方法進行研究。而在多信道無線網絡場景中，文獻[12]考慮了能量收集的無線傳感器網絡，研究了最小化平均AoI的調度問題，開發了基于Whittle Index的低復雜度算法。文獻[13]基于多信道網絡場景，分別提出了最小化峰值AoI和平均AoI的調度策略。文獻[14,15]考慮了多信道無線網絡中的鏈路干擾約束，采用遍歷的方式構造可行的調度集合，推導出最小化平均AoI的調度策略。文獻[16]針對信道狀態未知條件下的多信道網絡鏈路調度問題進行了研究，并分別提出了基于虛擬隊列的策略和Age-based策略。文獻[17]考慮了非均勻狀態更新的多信道傳輸問題，并分別在任意采樣和隨機采樣兩種更新方式下，將優化問題構造為馬爾可夫決策過程，研究最小化平均AoI的調度策略。

以上多信道場景中AoI的相關研究均未對鏈路沖突和信道沖突進行綜合考慮，而且現有的AoI的調度研究大多是在假設數據產生時間已知的情況下進行策略設計[7-17]，但在實際網絡中，獲取數據的產生狀態需要消耗一定的網絡資源。因此，在數據產生狀態未知的情況下，針對多信道無線網絡中可能同時存在的鏈路沖突和信道沖突問題，開發最小化系統平均AoI的調度方法是本文的研究重點。

3 系統模型

圖1 網絡拓撲

4 調度方法

在本文的優化問題中，需要逐時隙分配信道給不同鏈路進行數據傳輸以最小化網絡中的平均AoI。首先，將AoI的優化問題構造為李雅普諾夫優化問題[18]，提出了Max-Weight調度策略來最小化系統的李雅普諾夫漂移。然后，針對多信道無線網絡中存在的信道沖突問題，運用KM匹配算法求解最小偏移量的鏈路調度組合。

4.1 Max-Weight調度策略

所提方法使用Max-Weight調度策略逐時隙通過最小化李雅普諾夫漂移量來進行調度決策。在Max-Weight調度策略中，李雅普諾夫函數刻畫了在單個時隙下整個網絡中AoI平方的大小，其偏移量則表示隨著時隙的增加，相鄰時隙中AoI平方的變化趨勢。因此運用Max-Weight調度策略通過優化下一時隙的AoI，能夠有效優化網絡中的平均AoI[18]。

圖2 數據包更新時隙分析

4.2 信道沖突分析

在本文所考慮的網絡中，節點和信道在數據傳輸過程中存在沖突，在沖突約束下合理地進行調度決策是調度方法需要考慮的重要問題。

由于網絡中的可用信道數量M有限，因此調度決策需要滿足約束

4.3 Kuhn-Munkres匹配算法

KM匹配算法用以求解帶權二分圖的最大權匹配問題。其中二分圖為一種圖論的模型，用于構建兩個集合中各點間的邊的權重關系。最大匹配為滿足每個點最多和一個點匹配的條件下，使得匹配的邊權值最大的匹配組合[19]。在本文的方法中，將權重函數值取反并令其定義為匹配的邊權，在約束條件下通過KM匹配算法所得的最大權匹配即為最小的李雅普諾夫偏移量的鏈路調度組合。

首先，將多信道沖突和鏈路調度問題轉換為二分圖的最大匹配問題，能夠滿足約束式(11)、式(13)，即信道數量有限且一個信道只能和一條鏈路進行匹配的約束。但若直接構建源節點和信道間的二分圖，則無法滿足約束條件式(12)，該約束使得同一目標節點下只有一條鏈路可以被調度。

然后，針對約束條件式(12)，為了滿足最小化李雅普諾夫偏移量的目標，同一目標節點b在信道j下只會選擇最小的權重函數值Wb,j，即Wb,j=min{Wi,j|i ∈(lb?1+1, lb?1+2,..., lb)}。因此，需要構建目標節點和信道之間的二分圖，其中目標節點與信道之間的邊權定義為該目標節點和信道下不同源節點的最小權重函數值。在目標節點與信道之間進行最大匹配的情況下，會使得目標節點與信道間進行單一匹配，于是相同目標節點下只會存在單個源節點傳輸數據，從而滿足約束條件式(12)。表1給出了KM匹配算法的具體流程。

表1 KM匹配算法執行過程

如前所述，所提方法使用Max-Weight調度策略并結合KM匹配算法，形成的最大匹配即為最小的李雅普諾夫偏移量的鏈路調度組合。Max-Weight調度策略基于李雅普諾夫優化，在信道約束條件下最小化李雅普諾夫偏移量Δ[A(t)]。通過數據產生概率和傳輸成功率對李雅普諾夫偏移量進行計算分析，得出不同源節點在不同信道下的權重函數，然后使用KM匹配算法獲得最大權匹配，令匹配的鏈路組合的調度決策di,j=1。在復雜度方面，相較于遍歷所有可行的鏈路調度組合的復雜度O(NM)，K M 匹配算法在遞歸過程中的算法復雜度為O(Ma)，從而其算法的總體時間復雜度為O(Ma2)。由此可見所提方法在優化網絡中平均AoI的同時還能進一步降低復雜度。

5 仿真性能與分析

本文使用Matlab軟件搭建仿真驗證平臺，分別在不同的數據包產生概率、信道傳輸成功率、源節點數量、目標節點數量和信道數量等網絡參數設置下進行了仿真實驗，驗證算法的性能優劣。所用計算機的配置參數為：Intel(R) Core(TM) i5-8500雙核處理器；3.0 GHz主頻；16GB RAM；Windows10操作系統。

圖3展示了幾種算法下網絡中的平均AoI隨信道數量遞增的變化趨勢，其中傳輸成功概率和數據包產生概率在區間[0.2,1]不等，源節點數量N=100，目標節點數量為a=20。從圖中可以看出隨著信道數量的遞增，網絡中的平均AoI呈下降趨勢。這是由于信道數量的增加，源節點被調度的機會更大，從而降低了其在目標節點處的AoI。

圖3 不同信道數量下4種方法對比

圖4 不同信道傳輸成功率和節點產生數據概率下對比

圖4(a)展示了幾種算法下網絡中的平均AoI隨著信道傳輸成功率基準值PB遞增的變化趨勢，不同信道傳輸成功率為PB減去一個[0,0.1]間的隨機數，即Pi,j=PB?0.1×rand(1)。而數據包產生概率在區間[0.5,0.8]不等，源節點數量N=100，目標節點數量a=20，信道數量M=4。在傳輸成功率較小時，幾種調度方法的性能差異也比較明顯，隨著PB的增加，貪婪調度策略和Age-based策略的優化性能逐步接近Max-Weight策略。這是因為Agebased策略和Max-Weight策略的制定均與信道傳輸成功率密切相關，隨著PB的 增加，不同信道傳輸成功率的差異性逐漸減小，對這兩種策略的影響逐漸減弱，因此，當PB接近1時，貪婪調度策略、Agebased策略和Max-Weight策略更有可能做出相似的調度決策，3種算法的性能基本相當。圖4(b)給出了傳輸成功率在區間[0.5,0.8]不等，而數據產生概率為一個基準值αB減去一個[0,0.1]間的隨機數，即αi=αB?0.1×rand(1)時，源節點的數據包產生概率對平均AoI的影響。可以看出隨著數據產生概率的增加，平均AoI呈現出遞減的趨勢。這是因為頻繁的數據產生可以保持源節點處數據的新鮮度，使得數據產生時間趨近于當前時間。

圖5展示了幾種算法下網絡中的平均AoI隨著源節點數量遞增的變化趨勢，其中源節點的傳輸成功概率和數據包產生概率在區間[0.2,1]，目標節點數量a=20，信道數量M=4。可以看出隨著節點數量的遞增，所有方法的AoI基本呈線性增長的趨勢。這是由于隨著源節點數量的增加，每個源節點被調度的機會相應變小。

考慮到算法的實用性，表2給出了使用Matlab軟件進行仿真時，所提方法的平均執行時間。在不同節點規模下，其平均執行時間在1 ms以內，而在實際網絡中，調度算法可運行于系統的管理器(如WIA-PA網絡的網關設備和主控計算機)中，能夠較好地滿足工業無線網絡的傳輸需求。

綜上所述，相較于3種改進的對比策略，所提方法均表現出更好的優化性能。特別是在網絡中的信道傳輸成功率和源節點數量相差較大時，所提方法由于對各種網絡參數的綜合考慮，其優化性能對比其他3種算法，有顯著的提升。

6 結束語

圖5 不同源節點數量下幾種方法對比

表2 Max-Weight方法的平均執行時間(ms)

本文提出一種在考慮鏈路沖突約束的多信道無線網絡中基于平均AoI優化的調度方法。本方法將平均AoI優化問題轉換為李雅普諾夫優化問題，利用Max-Weight調度策略對李雅普諾夫偏移量進行優化，并結合KM匹配算法解決網絡中的信道沖突問題。理論分析和仿真驗證表明，該場景下Max-Weight調度策略優于改進的對比策略，能夠有效優化網絡中的平均AoI，提升網絡數據傳輸的及時性。在未來的研究工作中，將考慮在多信道無線網絡場景下，結合吞吐量、截止時間和能耗等因素對AoI進行聯合優化，使之能夠在提升數據傳輸的及時性的同時滿足更多的應用需求。