分布式無(wú)線網(wǎng)絡(luò)中正規(guī)化余額擴(kuò)展資源分配機(jī)制研究

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

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

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）22-0069-02

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

1 前言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）最長(zhǎng)潛伏期：數(shù)據(jù)進(jìn)入空隊(duì)列到開(kāi)始傳送的最長(zhǎng)時(shí)間間隔。

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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