[發明專利]無線網絡中時變需求驅動的可移動接入點調度方法

有效

• 申請號: 201911183399.0
• 申請日: 2019-11-27
• 公開（公告）號: CN110913412B
• 公開（公告）日: 2023-04-18
• 發明（設計）人: 吳文甲;孫聲宇;羅軍舟;單馮;楊明;凌振
• 申請（專利權）人: 東南大學
• 主分類號: H04W24/02
• 分類號: H04W24/02;H04W48/16;H04W48/08
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 葉涓涓

1.無線網絡中時變需求驅動的可移動接入點調度方法，其特征在于，包括如下步驟：

(1)建立時序需求點模型：劃分子區域，根據歷史記錄估計一段時間的時變用戶需求分布，抽象為需求點，并用三元組表示，三元組中各參數包括：需求點的服務子區域、需求開始時間和所需AP的數量的標號；分析需求點之間的時序關系，完成時序需求點模型的建立；具體包括如下子步驟：

(11)將網絡區域劃分為多個子區域，根據歷史記錄，估計一段時間的時變用戶需求分布，抽象為需求點；

(12)假設需求均為整點提出，且服務時間均為一小時，將需求點表示成三元組的形式；

(13)分析需求點之間的時序關系，構建時序熱點區域模型：使用集合S來表示所有的需求點，S＝{s₁,s₂,…,s_n}；每一個需求點都是一個三元組，即s_i＝(s_id_i,t_s_i,num_id_i)，分別表示需求點的服務子區域、需求開始時間和所需AP的數量的標號；使用集合M表示為滿足所有需求點的服務所需要的可移動AP，M＝{m₁,m₂,…,m_k}；每個被選中的m_i都對應一個待服務的需求點集合，將需求點按照需求開始時間升序排列，獲得集合MS_i＝{s₁,s₂,…,s_q}；模型滿足如下約束條件：

t_s_j≤t_s_j+1?j＝1,2,…,q-1??(1)

t_s_j∈{i:00|i∈Z,0i≤24}j＝1,2,…,q-1???(3)

其中，T為可移動AP的最大服務時間；

(2)建立可移動AP調度方案：所述調度方案包括靜態調度和動態調度兩種方法；靜態調度方法依據當天的需求估計，按照需求點的服務開始時間劃分子集，每次從不同的子集中挑選需求點分配給一臺AP，優先分配集合中剩余需求點個數大于1的子集；動態調度方法僅根據當前的需求，將當前已知的需求點與可用AP構建二分圖，求解其最小權完備匹配；

其中，靜態調度方法具體為：

(211)將這段時間的需求點按照服務開始時間劃分為每個子集合內的需求點的服務開始時間相同，子集合按照服務開始時間從小到大進行排序；

(212)將劃分為內所有的子集合僅包含一個需求點，內所有的子集合內至少包含兩個需求點，初始化k＝1；

(213)對于第k臺AP，每次從的不同子集合內選擇需求點，當中某個子集合剩余需求點為1時，該子集合被移到中；

(214)為空或剩余的需求點均與當前AP已分配到的需求點有時間沖突時，考慮分配中的需求點，直到即將超過該AP的可服務時間或所有需求點都被服務到；

(215)k＝k+1，重復步驟(213)(214)，直到所有的需求點都被服務到；

動態調度方法具體為：

(221)在每個整點時刻收集該時刻的需求點信息，構建二分圖BG(RV∪DV,ME)，RV表示可提供服務的AP集合，DV表示需求點的集合，若AP的剩余服務時間大于等于需求點的服務時間，則兩者之間存在一條邊e∈ME，邊權為AP的剩余服務時間；

(222)采用KM算法，求解二分圖BG(RV∪DV,ME)的最小權完備匹配，獲得當前AP的派遣方案，具體步驟如下：

(1)對所有邊的權值取相反數；

(2)為所有頂點v_i設定一個頂標值L(v_i)，集合RV中的頂點元素的頂標值均為0，集合DV中的頂點元素的頂標值取與該點相連的所有邊的最大權值；

(3)構建二分圖BG(RV∪DV,ME)的等價子圖EBG(RV∪DV,ME')，ME'內的邊e(v_i,v_j)需要滿足v_i和v_j兩點的頂標值之和大于等于邊的權值，使用匈牙利算法在等價子圖EBG中尋找完備匹配；

(4)若未找到完備匹配，則修改頂標值；設頂點集合S表示DV中參與本輪匹配的頂點的集合，頂點集合Y表示RV中發生沖突的頂點的集合，對于所有在S中的點x_i以及不在Y中的點y_j，計算S中的點的頂標減去d，Y中的點的頂標加上d；

(5)重復步驟(3)(4)直到找到等價子圖的完備匹配為止；

(3)采用靜態調度和動態調度相結合的分配策略進行AP的派遣調度：根據歷史記錄估計當前的所有需求，并基于估計需求執行靜態調度，在每個整點時刻，將該時刻的真實需求與歷史需求進行對比，如果比值超出一定閾值，則從此刻起執行動態調度，具體包括如下子步驟：

(31)根據歷史記錄，估計這段時間的時變用戶需求分布，在此基礎上運行步驟(2)中所示的靜態調度；

(32)在每個整點時刻，計算每個子區域當前時刻實際所需AP數量與AP數量需求估計的比值；

(33)如果比值處于閾值范圍之內，則繼續執行靜態調度；

(34)如果比值超出閾值范圍，則終止靜態調度方案，從當前時刻起，在每個整點時刻收集實時需求信息后，運行步驟(2)所示的動態調度，直到當天結束。

2.根據權利要求1所述的無線網絡中時變需求驅動的可移動接入點調度方法，其特征在于：所述一段時間為一天，所述一天為24小時。