[發明專利]一種基于Kuhn-Munkres算法的收益率時間相關服務數據包的調度算法

有效

• 申請號: 201710360198.8
• 申請日: 2017-05-22
• 公開（公告）號: CN107241813B
• 公開（公告）日: 2020-04-07
• 發明（設計）人: 高振國;孫鵬;陳丹杰;盧志茂;陳炳才;姚念民
• 申請（專利權）人: 大連理工大學
• 主分類號: H04W72/12
• 分類號: H04W72/12
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 梅洪玉

本發明屬于無線通信技術領域，公開了蜂窩信息站集成網絡環境無線網絡下,一種基于Kuhn?Munkres算法的收益率時間相關服務數據包的調度算法。基于該算法，能夠使得在線調度的所有按需服務數據包獲得更大收益。首先建立該環境下數據包調度問題的數學模型，包括時隙模型和按需請求數據模型，將原問題轉化為在線調度問題轉化為0?1整形規劃問題；將該調度問題轉化為加權二分圖，并修改轉化為帶權二分圖的規則，使其滿足按需服務請求在一個時隙內部待分配的數據包的數量不能超過某個上限，然后基于該加權二分圖和其鄰接矩陣，使用Kuhn?Munkres算法設計在線調度算法，求解最優匹配，從而求得近似最優解。仿真結果顯示基于該算法的在線調度算法比現有的算法能夠取得更優的收益。

技術領域

本發明屬于無線通信技術領域，設計了高速鐵路運行中，基于蜂窩信息站集成網絡的無線網絡環境下，一種基于Kuhn-Munkres算法的收益率時間相關服務數據包的調度算法。

背景技術

本文應用一種基于蜂窩信息站集成的三層網絡架構，即內容服務器，信息站(路邊通信單元)和車輛站，系統中的網絡數據服務方式為按需服務方式。這種網絡架構和服務方式現在已經廣泛應用于服務高速列車乘客的網絡需求和V2X車聯網系統通信中。在該系統中，蜂窩網絡基站通過穩定的有線網絡連接與內容服務器相連，提供較低速的網絡信號覆蓋；信息站部署在軌道旁，能夠提供小范圍較大數據傳輸速率的網絡接入。信息站和蜂窩網絡集成的網絡系統，能夠綜合蜂窩網絡和信息站各自的優點。

當車載設備(用戶)按照需求請求數據服務時，數據報文將通過路邊信息站與車載設備或終端(手機，電腦等)之間的無線信道將數據調度和分配給用戶。高速鐵路乘客(網絡用戶)通過蜂窩網絡鏈路請求按需服務數據，服務數據從主干網絡傳遞到信息站，然后再傳輸給車輛站。最后，車輛站(部署在高速列車上)負責分配調度數據包給車廂內部用戶的終端設備。信息站通過穩定的有線網絡鏈路連接到主干網絡核心服務器，車輛站到用戶終端設備的連接可以由Wi-Fi等高速無線局域網技術負責實現。服務數據傳遞到用戶設備后，服務的確認信息由車輛站經由信息站最終由蜂窩集成網絡進行傳輸。

為了滿足車輛在高速行駛過程中基站與車輛通信的需求，克服多普勒效應等對網絡通信的影響，有學者提出一種專門用于基站與車載設備通信的MAC幀結構。這種結構下，每個時間區間被分為時間間隔相等的用于信息傳播的時隙，時間間隔小于信道相干時間(channel coherence time)，劃分的每個時隙的信道增益是固定的，但是由于信號衰減等原因，時隙的容量會因不同的情況而有所差異。考慮時隙中信道增益等信道信息，每個時隙可以發送的數據包數量上限可以確定。

考慮按需數據調度的質量和用戶良好的網絡體驗，高質量、低延遲、低丟包率等要求是在線調度數據包時要追求的目標。同時，在按需請求數據服務下，用戶愿意為不同的服務付出的代價也是不同，另外由于用戶之間的差異，不同用戶愿意為請求服務支付的價格也不相同。在高速鐵路環境下，由于信道狀態不太穩定，以及種種因素，尤其是多普勒效應的限制，數據由信息站到車輛站的調度是整個網絡傳輸的瓶頸，因此，怎樣合理高效利用信道，合理調度服務數據，使得調度的服務數據獲得最大價值，讓服務運營商或提供者獲得最大收益是很重要的目標。本發明所解決的目標問題就是如此。

1.系統模型

本文所述問題中的時隙模型如下，高速鐵路沿線信息站總數為H，假設每個信息站覆蓋范圍不重疊。和表示車輛進入和離開信息站h,h＝1,2,…,H覆蓋范圍的時刻。如上述背景技術所述，時間在每個時間間隔內被劃分為相等時長為T_F的時隙，則第h信息站覆蓋的時間可以分為時隙，則用于數據傳輸的時隙總數為其中時隙n內數據包傳輸容量為C_n,n＝1,2,…,N。

按需請求的數據模型如下，用戶服務請求集合為S，對于S中的每個服務s∈S，使用一個四元組(G_s,Q_s,D_s,W_s(n),L_s(n))來定義，其中：