分布式無線網絡中正規化余額擴展資源分配機制研究

摘要：基于權重最大一最小公平準則提出正規化余額擴展（ Normalized Residual Scaling，NRS）資源分配方法，適用于無線網絡節點分布式數據傳輸調度，以實現上行帶寬分配等相關應用。通過控制平均傳輸周期長度及調適個別節點的帶寬用量，顯著提升網絡帶寬使用率、降低節點處理控制信息的負擔、保障各節點傳輸數據的最長潛伏期，并且通過正規化資源位準的概念改進算法，降低系統資源分配的計算復雜度。通過系統仿真與效能分析，該方法在輪詢頻率及帶寬使用率皆有良好的效能。

關鍵詞：權重最大一最小公平;水挹注程序;無線令牌環通訊協議

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2020）22-0069-02

開放科學（資源服務）標識碼（OSID）：

1 前言

隨著互聯網的高速發展，使用移動設備通過無線網絡進行各項應用與娛樂已成為很多人日常生活的一部分[1]。因物聯網[2]及傳感網絡的應用不斷增加，這些傳感設備與輕量化終端設備必須通過各式的無線網絡，將其數據傳輸至后端的服務系統。因此，無線網絡已是現今與未來各項應用與服務的重要基礎，學者們持續投入研究以提升無線網絡的各項效能[3]。在無線傳感網絡中，如何有效節省與管理電量以延長整體網絡的存活時間是一項重要的議題[4]。一般而言，傳感節點傳送與接收數據的無線通信動作為最主要的電量消耗來源，因此必須有良好的傳感節點部署架構以及有效且公平的節點媒體訪問控制與資源分配調度方式。

本論文提出一應用于無線網絡中的分布式權重最大一最小公平準則的資源分配方法，本方法通過控制平均傳輸周期及調適個別節點的帶寬用量，將各節點讓出的系統資源按照權重比例實時地分配給網絡中的全部節點，使系統整體資源的分配方式達成權重最大一最小公平準則。本方法具有以下優點：（1河彈性調整服務周期，有效提升資源使用率。（2）能保障各網絡節點對于最小帶寬的質量要求。（3）資源使用時間計算復雜度低。（4）可簡化資源管理，避免控制信息過長而造成額外的成本。

2 相關技術

2.1 最大一最小公平資源分配

最大一最小公平（ Max-Min Faimess）是分時多任務系統中被廣泛采用的資源分配模型，其定義如下：

依據此定義：在固定有限資源的條件下，假設N維實數序列x滿足最大一最小公平資源分配，則對于其他任何分配方式y，任一使用者如果能在y中獲得較多的資源，必定犧牲其他使用者t，使得y.< xt;且在原來的分配方式x中，使用者t獲得的資源比s還要少。

2.2 無線令牌環通訊協議

無線令牌環通訊協議（Wireless Token Ring Protocol，WTRP）是支持分布式無線網絡帶寬分配的通訊協議之一，借由令牌傳遞來同步各節點的帶寬使用時間。其作法系將系統節點在邏輯上組成一環狀結構，所有節點于此結構單向傳遞一令牌，持有令牌的節點擁有帶寬使用權，且必須在MTRT（ Maxi-mum Token Rotation Time）到期之前將令牌傳遞給下一節點。令牌環封包和數據的傳輸區間需保留一傳遞時間。此通訊協議實施一有限狀態機，用以處理網絡運作過程中可能發生的各種事件，包括：節點加入、節點離開、環修復、環重建、令牌同步。

3 分布式無線網絡帶寬分配

3.1 分布式無線網絡傳輸架構

以下先說明一般分布式無線網絡的傳輸架構，假設一無線網絡包括N個節點，依序為n1，n2 ，...，nN，輪流使用網絡帶寬，每一節點ni對應一權重wi，當節點接收控制信息獲得帶寬使用權時，計算本次允許的帶寬使用時間，利用這段時間進行數據傳輸;當使用權到期時，發送控制信息將使用權傳遞給下一節點。其中，帶寬使用權的傳遞方式可為WTRP，或任何支持網絡節點協同運作的傳輸協議。輪詢規則容許在一個周期內多次拜訪同一實體節點，依節點對于數據延遲的敏感度和傳輸量而彈性設計，但在帶寬資源分配過程是將一周期內的每一節點在邏輯上視為不同節點。

3.2 帶寬分配規則原型設計

此法通過輪流調度確保每個節點可得到一定的傳輸時間，并借由縮短傳輸周期回收剩余帶寬再重新分配給未滿足的節點，以改善帶寬資源的使用率;但縮短周期使系統花費過高的時間比例在切換節點的帶寬使用權，導致真正用于傳輸數據的帶寬效能不佳，且過量的控制信息將增加無線網絡的維護負擔以及收發器的耗電量。

假設每一節點n.對應權重給定一基本傳輸時間‘（簡稱基本量），在節點輪流使用帶寬的過程中，若節點傳輸數據所需時間q1（簡稱需求量）低于基本量，除將資源配額凍結之外，可將剩余資源（簡稱剩余量）依權重比例累加至其他未凍結的節點，因而需求量較低節點所節省的傳輸時間可公平轉移至需求量較高的節點，避免傳輸周期縮減導致帶寬使用率下降。

依據上述計算，節點ni在第k周期獲得的帶寬使用量si（k）是由需求量qi（k）和分配量di（k）決定，而分配量為基本量ti與優惠量pi（k）的總和，優惠量則是節點在此次使用帶寬的前一周期內，所有節點釋放的剩余量依權重比例平均分配的累加值，其中，剩余量ei（k）是分配量與使用量的差值。

3.3 帶寬分配算法設計

本文目標為發展實用的無線網絡帶寬資源分配方法，滿足權重最大一最小公平分配準則，且同時解決帶寬使用率、計算復雜度等效能問題。為了克服上述缺點，我們采用了“資源位準”的構想，提出正規化余額擴展（ Normalized Residual Scaling，NRS）資源分配方法。除沿用前述定義，本方法另外基于正規化位準的概念引入下列變量：

B（x）系統帶寬在第x次被使用前的系統優惠位準

bi（k）節點ni在第k輪使用帶寬前的個體優惠基準

NRS方法將各節點讓出的剩余量經過正規化后累加至系統優惠位準。并且定義傳輸節點獲得的優惠量等于系統優惠位準在一周期內的增量、乘以該節點的權重。其中，系統優惠位準在一周期內的增量為節點本次傳輸和上次傳輸時的系統優惠位準的差額，本次傳輸時的系統優惠位準B（x）可通過控制信息傳遞，而上次的系統優惠位準即個體優惠基準bi（k），則借由節點在上一周期所儲存的當時的系統優惠位準得來。

經由前面實例可知本論文所提的NRS方法與原型方法計算所得的分配結果完全相同，下面更通過數學證明來加以驗證。由前述計算步驟可知，兩者的主要差異在于優惠量pi（k）的定義。若將系統帶寬在第x次被使用后的剩余量標示為e（x），則ei（k）=e（N×（k一1）+i）。

NRS方法借由傳輸節點協同維護系統優惠位準以及活化節點權重總和，可將節點讓出的帶寬剩余量按權重比例實時地分配給所有的需求節點，相較于前述所提的帶寬分配原型，節點在單一周期內計算帶寬使用量的復雜度由O（N）降為0（1）。且因兩者的帶寬分配結果完全相同，故NRS方法可保證網絡節點的帶寬用量滿足權重最大一最小公平準則，相較于WRR方法則提升了系統帶寬使用率。

從帶寬分配規則的原型設計可知，NRS帶寬分配時序在一個傳輸周期內可由原本超前時間L轉為對齊標準時序，在此情況下，節點等待數據傳輸的最長潛伏期為一個標準周期長度+L。為了保障節點的傳輸潛伏期，NRS方法可額外維護L（x），代表系統帶寬在第x次被使用前的傳輸進度超前量，并且限制此超前量不高于Lmax。依據此限制，NRS方法的帶寬使用量更改為：

當帶寬使用期滿時，則將更新后的進度超前量連同系統優惠位準與活化節點權重總和傳遞至下一節點。

由計算公式可知，進度超前量是各節點使用量低于基本量的差額累計值，因此，當節點評估本次帶寬讓予將使得進度超前量高于Lmax時，則依據超前量的限制來決定使用量。借此機制，NRS可調整傳輸周期彈性伸縮的最大范圍，并且仍確保平均周期與標準周期長度相等。

4 系統仿真與效能分析

我們使用C++仿真WTRP網絡傳輸系統，實驗WRR與NRS帶寬分配算法。系統仿真參數如表l所示。

假設全部節點的權重皆為1。其中n個負載節點持續要求最大帶寬，另外（20-n）個沉默節點的帶寬需求量為0。改變負載節點數量從2，4，6，…，至20，模擬分析下列各項效能指標：

（1）輪詢頻率：節點平均每秒獲得帶寬使用權的次數。

（2）帶寬使用率：系統傳送數據所使用的帶寬占總帶寬的比例。

（3）最長潛伏期：數據進入空隊列到開始傳送的最長時間間隔。

依據模擬結果可知，NRS方法借由保持傳輸周期平均長度而大幅降低節點輪詢頻率，以節省收發器耗電量及網絡維護的負擔;并且借由彈性調適個別節點的帶寬用量，保障系統維持穩定的帶寬使用率，因而有效提升負載節點的數據傳輸量。本方法付出的代價是稍微地增加了節點等待傳輸的最長潛伏期，但理論上潛伏期達到此最大值的發生概率非常微小。

5 結論

本論文基于水挹注程序概念提出NRS權重最大一最小資源分配方法，依據節點需求而彈性調整傳輸周期的長度，并且基于公用資源位準的概念提出正規化余額的加權運算方法，將計算節點帶寬使用量的復雜度由O（N）降為0（1）。借由網絡傳輸節點協同維護公用變量，可實時回收剩余的帶寬資源并按照權重比例分配給所有的需求節點。經由實驗模擬驗證，NRS方法可顯著提升網絡系統帶寬使用率及降低節點輪詢頻率，在多節點間歇性實時數據傳輸的應用情境下，可大幅改善系統效能。

參考文獻：

[1]賀偉，梁潘.移動無線傳感網絡的分布式協作定位的研究[J].計算機應用與軟件，2019，36（4）：161-165.

[2]任廣鵬，楊志恒，申宇豪.分布式無線傳感器網絡通信協議分析[J].中國新技術新產品，2019（7）：37-38.

[3]劉文軍，王喜，林政寬.無線傳感器網絡延遲約束的MDC分布式軌道規劃算法[J].傳感技術學報，2018，31（8）：1270-1276.

[4]陳倩，駱駿，樂婷婷.無線網絡中分布式機會協作的信道接入算法研究[J].電子科技，2018，31（11）：6-10.

【通聯編輯：代影】

作者簡介：肖堅（1982-），男，湖南益陽人，湖南外貿職業學院講師，碩士，研究方向：無線傳感器網絡、計算機應用、網絡安全。