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

關(guān)鍵詞：權(quán)重最大一最小公平;水挹注程序;無線令牌環(huán)通訊協(xié)議

中圖分類號：TP311 文獻標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

1 前言

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

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

2 相關(guān)技術(shù)

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

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

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

2.2 無線令牌環(huán)通訊協(xié)議

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

3 分布式無線網(wǎng)絡(luò)帶寬分配

3.1 分布式無線網(wǎng)絡(luò)傳輸架構(gòu)

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

3.2 帶寬分配規(guī)則原型設(shè)計

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

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

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

3.3 帶寬分配算法設(shè)計

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

B（x）系統(tǒng)帶寬在第x次被使用前的系統(tǒng)優(yōu)惠位準(zhǔn)

bi（k）節(jié)點ni在第k輪使用帶寬前的個體優(yōu)惠基準(zhǔn)

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

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

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

從帶寬分配規(guī)則的原型設(shè)計可知，NRS帶寬分配時序在一個傳輸周期內(nèi)可由原本超前時間L轉(zhuǎn)為對齊標(biāo)準(zhǔn)時序，在此情況下，節(jié)點等待數(shù)據(jù)傳輸?shù)淖铋L潛伏期為一個標(biāo)準(zhǔn)周期長度+L。為了保障節(jié)點的傳輸潛伏期，NRS方法可額外維護L（x），代表系統(tǒng)帶寬在第x次被使用前的傳輸進度超前量，并且限制此超前量不高于Lmax。依據(jù)此限制，NRS方法的帶寬使用量更改為：

當(dāng)帶寬使用期滿時，則將更新后的進度超前量連同系統(tǒng)優(yōu)惠位準(zhǔn)與活化節(jié)點權(quán)重總和傳遞至下一節(jié)點。

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

4 系統(tǒng)仿真與效能分析

我們使用C++仿真WTRP網(wǎng)絡(luò)傳輸系統(tǒng)，實驗WRR與NRS帶寬分配算法。系統(tǒng)仿真參數(shù)如表l所示。

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

（1）輪詢頻率：節(jié)點平均每秒獲得帶寬使用權(quán)的次數(shù)。

（2）帶寬使用率：系統(tǒng)傳送數(shù)據(jù)所使用的帶寬占總帶寬的比例。

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

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

5 結(jié)論

本論文基于水挹注程序概念提出NRS權(quán)重最大一最小資源分配方法，依據(jù)節(jié)點需求而彈性調(diào)整傳輸周期的長度，并且基于公用資源位準(zhǔn)的概念提出正規(guī)化余額的加權(quán)運算方法，將計算節(jié)點帶寬使用量的復(fù)雜度由O（N）降為0（1）。借由網(wǎng)絡(luò)傳輸節(jié)點協(xié)同維護公用變量，可實時回收剩余的帶寬資源并按照權(quán)重比例分配給所有的需求節(jié)點。經(jīng)由實驗?zāi)M驗證，NRS方法可顯著提升網(wǎng)絡(luò)系統(tǒng)帶寬使用率及降低節(jié)點輪詢頻率，在多節(jié)點間歇性實時數(shù)據(jù)傳輸?shù)膽?yīng)用情境下，可大幅改善系統(tǒng)效能。

參考文獻：

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

[2]任廣鵬，楊志恒，申宇豪.分布式無線傳感器網(wǎng)絡(luò)通信協(xié)議分析[J].中國新技術(shù)新產(chǎn)品，2019（7）：37-38.

[3]劉文軍，王喜，林政寬.無線傳感器網(wǎng)絡(luò)延遲約束的MDC分布式軌道規(guī)劃算法[J].傳感技術(shù)學(xué)報，2018，31（8）：1270-1276.

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

【通聯(lián)編輯：代影】

作者簡介：肖堅（1982-），男，湖南益陽人，湖南外貿(mào)職業(yè)學(xué)院講師，碩士，研究方向：無線傳感器網(wǎng)絡(luò)、計算機應(yīng)用、網(wǎng)絡(luò)安全。