基于多服務器的輪詢接入控制協議分析

楊志軍，毛 磊

(1.云南大學 信息學院，云南 昆明 650500；2.云南省教育廳 教育科學研究院，云南 昆明 650223)

0 引 言

互聯網的快速發展使得網絡的規模和業務流量不斷增加，服務器需要具備更加強大的運算能力，才能保證網絡時延和服務效率。因此對于使用單一服務器的接入控制協議而言，服務器的內存、處理器很容易到達瓶頸[1]。物聯網時代，感知層對高密集站點的數據進行采集，通過各種網絡實現實時傳送，這對感知層的接入控制協議要求較高[2]?；谳喸兘尤霗C制的MAC協議，在計算機網絡和物聯網中有著廣泛應用[3-5]，傳統的輪詢系統大多采用單服務器接入控制方式(single server access control mechanism，SSACM)[6,7]，由于單臺服務器的運算能力是有限的，在業務量和網絡規模較大時，網絡時延較高，吞吐量較小，顯然不能滿足物聯網中數據實時傳輸的需求。解決這類問題有兩種方法：一是為服務器配置高性能的硬件設備；二是多服務器并發處理方式[8-11]。但是由于硬件擴展成本較高，通過提升硬件性能并不能從根本上解決這個問題，只有采用多服務器才能滿足大量用戶訪問的需要，實現負載均衡[12,13]。

針對上述單服務器輪詢接入協議的缺陷，本文將多服務器并發處理的方式應用到輪詢接入協議中，旨在實現輪詢系統的負載均衡，提高輪詢系統的服務效率和吞吐量。多個服務器調度時，使用同步控制的方式實現服務器在站點之間的輪詢，然后利用輪詢多址系統理論和排隊論對系統的平均排隊隊長和平均時延等性能進行了近似分析，并通過仿真實驗進行了驗證。

1 輪詢接入控制協議

1.1 背景知識及相關工作

MAC協議是構建無線傳感器網絡(wireless sensor network，WSN)底層結構的基礎，主要用來解決多個節點共享同一鏈路或資源時，信道資源如何分配和劃分的問題。一般分為隨機訪問MAC協議和輪詢訪問MAC協議。在設計一個無線傳感器網絡時，主要考慮能耗、時延、網絡效率等因素?；谳喸兘尤肟刂品绞降腗AC協議，是一種非競爭的協議，其時延和公平性較好，因此在WSN中有著廣泛應用。根據節點占用信道的時間，輪詢接入控制協議主要分為完全、門限和限定3種。完全服務協議[14]是指，當節點占用信道時，只有在發送完所有數據后才會釋放信道；門限服務協議是指，當節點占用信道時，只發送當前時刻節點內存儲的數據；限定服務協議是指，當節點占用信道時，只發送K(K≥1)個信元。3種協議有各自的優勢和應用場景，其中完全服務協議用戶的平均等待時延和平均排隊隊長較低，適用于高優先級或者實時性要求較高的業務。門限服務協議和限定服務協議公平性較好，適用于普通業務。

現階段對輪詢接入控制協議的研究，主要還是集中在區分業務優先級[15]和服務器調度方式[16]上。文獻[17]中提出了一種使用兩個服務器同步控制(dual server synchronization control strategy，DSSCS)的負載均衡策略，在一定程度上提高了系統的服務效率，但當網絡中訪問請求較多時，仍然不能解決系統效率低的問題。文獻[18]提出一種基于忙閑隊列的輪詢控制協議，根據隊列中有無顧客將隊列分為忙隊列和空閑隊列，每次輪詢時，服務器只訪問忙隊列，提高了系統的服務效率，但在網絡規模和業務量較大時，網絡時延仍然較高。上述輪詢機制，雖然在一定程度上改善了系統的性能，但并沒有改變單臺服務器的限制，其數據處理方式仍然比較單一。本文提出的多服務器接入協議，突破了傳統單服務器輪詢接入控制協議的局限，擴展了輪詢接入協議的內容，有效提高了輪詢系統的服務質量。

1.2 MPACP協議

多服務器輪詢接入控制協議(multi-server polling access control protocol，MPACP)由N個站點，S個服務器組成，如圖1所示。服務器按完全服務方式對各個站點提供服務，即只有正在接受服務的站點沒有數據需要被發送，服務器才切換到下一個站點繼續提供服務。多個服務器調度時，可以同時參加站點的服務器的最大數量是1或S。聲明：在任何給定時間內只有一個服務器可以為站點提供服務的服務器利用策略稱為1×N，也可以叫作異步控制策略；所有S個服務器可以同時參加站點的服務器利用策略稱為S×N，也可稱為同步控制策略，當S=1時，兩種策略明顯重合。本文使用同步控制策略實現多個服務器的接入，S個服務器同時為站點提供服務，服務完成后同時離開。

圖1 MPACP模型

在該協議中，多個服務器同時為站點提供服務指的是：當站點中有大量數據或訪問請求等待處理時，將其分割成不同的塊，然后發送到多臺服務器上進行處理，以此來降低用戶的平均排隊隊長和平均等待時延；或者是將單個大負載分發到多個服務器上分別處理，然后將每臺服務器的處理結果合并后返回給用戶。

多服務器輪詢接入控制協議的這種結構對每一個客戶來說都是透明的，從客戶角度來說，客戶看不到真正提供服務的多個服務器，只能看到一個虛擬的服務器。當用戶提出發送請求后，首先將請求包傳遞給虛擬服務器，然后虛擬服務器將請求包中的目標MAC地址轉換為選定服務器的MAC地址后，將用戶請求轉發出去，服務器處理后將用戶的請求結果返回給用戶。多服務器輪詢接入機制的工作流程如圖2所示。

圖2 MPACP工作流程

2 MPACP系統分析

一個輪詢系統的性能，主要從系統內用戶的平均排隊隊長、平均循環周期、平均時延等方面來衡量，前兩者是一階特性，后一個是二階特性。相同負載下，隊長、周期、時延越小，說明系統的性能越好，服務效率越高。根據基本輪詢系統的分析方法和排隊理論，我們對多服務器輪詢機制的特征參數進行解析，分析方法和結果如下所示。

2.1 系統工作條件

由于數據傳輸過程中，系統內的業務量或者是用戶的訪問請求隨機性和不確定性較大，情況非常復雜，為了能對系統的性能做出正確的評估，仿真實驗又不失一般性，在本文中考慮具有如下特征的多服務器輪詢接入機制：

(2)系統內，站點數量等于N(N≥1)，服務器數量等于S(S≥1)。

(4)輪詢順序是服務器按升序索引訪問每一個站點，訪問完站點N之后，服務器返回站點1。

(6)系統是對稱的：所有站點都是相同的，所有服務器的行為都是相同的，服務器按照數據到達的先后順序為其提供服務(first come first serve，FCFS)。

2.2 隨機變量和概率母函數

為分析系統的狀態變量，定義以下隨機變量：

vi(n)：服務器對i號站點中的信元進行完全服務所耗費的時間。

ui(n)：服務器從i號站點切換到i+1號站點的時間。

μj(ui)：ui(n)時間內進入j號站點的信元數。

ηj(vi)：vi(n)時間內進入j號站點的信元數。

設tn時刻，S個服務器同時訪問i號站點并提供服務，當服務器處理完該站點存儲器內的信元后轉去查詢i+1號站點，i+1號站點在tn+1時刻接受服務。ξi(n)表示tn時刻，i號站點存儲器內存儲的信元數，則tn時刻系統的狀態變量可表示為{ξ1(n),ξ2(n),…,ξi(n),…,ξN(n)}。通過分析可知，tn+1時刻的系統狀態只與tn時刻有關，網絡的規模，即站點數量是有限的，該系統的狀態變量構成馬爾可夫過程，并且在Nλβ

(1)

定義πi(x1,x2,…,xi,…,xN)的概率母函數為

(2)

tn+1時刻，服務器為i+1號站點提供服務，由此可得

(3)

(4)

2.3 平均排隊隊長

定義系統的平均排隊隊長為：tn時刻，服務器按照完全服務規則對i號節點中的信元進行傳輸時，j號節點存儲器內存儲的信元數，用gi(j)來表示

(5)

由式(4)、式(5)可得MPACP系統中信元的平均排隊隊長為

(6)

式中：N表示站點數量，S表示服務器數量(N,S≥1)。

2.4 平均等待時延

通常使用系統中客戶的平均等待時延來衡量網絡的傳輸能力，時延過大，系統內的每個客戶都需要等待很長時間才能得到服務，因此系統性能較差。定義系統的平均等待時延為：信元從進入節點到其開始被發送出去所經歷的時間間隔。

定義系統的二階偏導為

(7)

由式(4)、式(7)可得

(8)

與單服務器完全服務機制[14]類似，MPACP系統的平均等待時延也由E(wi,1)和E(wi,2)兩部分組成，E(wi,1)表示：服務器輪詢到i號節點開始傳輸數據時，緩沖區內存儲的信元的平均等待時延；E(wi,2)表示，服務器為i號節點提供服務期間，到達i號節點的信元的平均等待時延。由式(6)～式(8)可得

(9)

2.5 系統吞吐量

定義系統吞吐量為：單位時間內，多服務器完全輪詢接入機制所能處理的信元數，用T表示。MPACP采用多個服務器并發處理的結構，增大了系統的吞吐量，其計算方式如下

T=NSλβ

(10)

由文獻[14]可知，SSACM的吞吐量為Nλβ，與其相比，多服務器系統的吞吐量增大了S倍。說明MPACP協議的負載能力更大，相同時間內，MPACP處理的信元數是SSACM的S倍。

2.6 平均查詢周期

系統平均查詢周期定義為：服務器對所有站點完成一次遍歷所花費的時間，也就是服務器連續兩次查詢同一站點之間的時間間隔，用E[θ]表示。平均查詢周期的計算大多是根據平均排隊隊長與平均循環周期的關系推導而出，該方式計算較為復雜[15]。本文根據輪詢系統的工作機制，提出一種計算方法，定義如下：

服務器對所有站點完成一次訪問所花費的時間由兩部分組成：輪詢轉換所花費的總時間Nγ和為每個節點的信元進行傳輸所花費的總時間。后一部分，平均而言，在穩定狀態下(由于對稱性和穩定性)，必須等于一次遍歷期間到達的平均總工作量的1/S,而根據我們的定義，單位時間內到達MPACP系統的平均總工作量為λtotβ=Nλβ，所以可以得到

(11)

3 仿真實驗

根據2.1節理論分析的條件，在MATLAB2018a平臺上構建多服務器輪詢接入控制模型。使用exprnd()函數生成滿足泊松分布的隨機序列，用于模擬到達每個節點的信元數，其均值為λ。假定仿真時，數據通信過程是理想狀態，也就是所有的信元都被發送成功，不會發生丟包和重傳的情況。通信過程中，按時隙劃分時間軸。仿真過程中，需要滿足下面條件：

(1)系統是對稱的：所有隊列都是相同的，所有服務器的行為都是相同的；

(2)在每一個單位時隙內，數據按照泊松過程到達節點，節點的存儲空間無限大；

(3)系統在Nλβ

(4)為確保實驗的準確性，設置每次實驗的循環次數為10萬次以上；

(5)為提高仿真效率，實驗中，網絡規模，即節點數量在5-30個內變化，服務器數量在3-10個內變化，數據包的到達率λ的取值為[0.001∶0.001∶0.01]，單位為Mbps。

在該系統中，其初始條件為：在開始時刻，各個站點內沒有數據需要被發送，當站點提出發送請求后，S個服務器同時去查詢第一個站點，然后按完全服務方式為其提供服務。服務完成后，轉去查詢第二個站點。以此類推，服務完最后一個站點后，又開始對第一個站點提供服務。實驗內容主要分為一下幾個步驟：

步驟1 根據假定的條件，在MATLAB2018a上構建MPACP系統模型；

步驟2 產生滿足泊松分布的數據信息；

步驟3 統計所有的數據信息；

步驟4 計算平均排隊隊長、平均循環周期、平均等待時延的實驗值；

步驟5 根據式(6)～式(11)計算出理論值，然后與實驗值比較，計算出相對誤差；

步驟6 驗證模型的正確性；

步驟7 設置實驗條件，將MPACP模型與SSACM和DSSCS模型比較，評價MPACP模型的優越性；

模型仿真過程中，MPACP模型的控制流程見表1。

表1 MPACP控制流程

4 實驗結果及分析

通過改變網絡中的業務量(即數據包的到達率)、服務器數量和網絡規模，分析系統中用戶的平均排隊隊長、平均循環周期和平均等待時延的變化規律，結果如下所示。

表2是具有固定節點數量(λ=0.05,β=4,N=6,γ=2)，服務器個數在2到7之間變化的系統的平均隊長和平均循環周期對比結果。通過對比發現，理論值與實驗值基本一致，誤差保持在較小范圍內，說明理論分析的可靠性和準確性。

表2 MPACP理論值與實驗值的相對誤差

圖3和圖4是具有固定站點數量(N=5)，服務時間β=10，不同服務器數量情況下，系統的平均排隊隊長和平均等待時延的對比。首先，兩個圖中，各曲線上，理論值與實驗值基本擬合，說明理論分析與仿真實驗的一致性。然后，從兩個圖可以分別看出，隨著服務器數量的增加，MPACP的平均隊長和平均時延不斷降低，說明相同業務量情況下，隨著服務器數量的增加，系統的服務效率逐漸提高，使用多服務器輪詢接入控制方式可以提高系統的性能。進一步分析圖3，在數據包的到達率較小時，MPACP對系統平均隊長的影響不是很明顯；只有在到達率較高時(即高業務量情況下)，使用多服務器才能降低系統的平均隊長。這是因為在業務量較小時，使用單服務器接入方式就能滿足系統數據處理的需求，沒必要使用多服務器。對比圖4發現，在業務量一定時，MPACP的平均時延隨著服務器數量的增加而降低，當服務器數量為10個以上時，其平均時延的下降趨勢逐漸趨于平滑。

圖3 MPACP平均排隊隊長隨服務器數量的變化 (N=5,β=10,γ=1)

圖4 MPACP平均時延隨服務器數量的變化 (N=5,β=10,γ=1)

兩個圖中，分析S=6，S=10，兩條曲線，即服務器個數取6、10?？梢钥闯?，在不同服務器下，系統的平均隊長和平均時延變化趨于平穩，特別是數據包到達率較小的時候尤為明顯，這說明使用多服務器并不能無限提升系統性能，當系統性能優化到一定程度時，繼續增加服務器數量不僅不能提升系統性能，反而會造成資源的浪費。結合式(6)和式(9)也可以發現，輪詢系統的性能除了與服務器數量有關，還與網絡規模N和輪詢轉換時間γ有關。因此當使用MPACP協議提升系統性能遇到瓶頸時，可以通過優化站點數量、降低輪詢轉換時間和提高服務器的配置來進一步提升系統性能。

圖5是不同數量的服務器下，系統平均循環周期的對比分析。在輪詢系統中，平均循環周期是衡量輪詢系統服務效率的重要指標，相同網絡規模和業務量情況下，平均循環周期越小，系統的服務效率越高。從圖5可以看出，MPACP的平均循環周期隨著數據包到達率的增加而增大。當到達率一定時，隨著服務器數量的增加，系統的平均循環周期逐漸降低，這說明使用MPACP協議，系統的服務效率和穩定性得到了很大提高。

圖5 MPACP平均循環周期隨服務器數量的變化 (N=5,β=10,γ=1)

4.1 網絡規模對MPACP的影響

在實際通信過程中，不同的場合需要應用不同的網絡規模。隨著物聯網的快速發展和感知層高密集節點的接入，網絡規模成為影響WSN系統性能的重要因素。為分析網絡規模對MPACP協議的影響，保持網絡中業務量不變(即每個站點數據包的到達率都為0.004 Mbps)，網絡中節點數量在10-30內變化，然后對比3種協議的平均時延，其中SSACM表示單服務器接入控制方式，DSSCS表示雙服務器同步控制策略，仿真結果如圖6所示。

圖6 不同網絡規模下3種協議平均時延對比

從圖6的對比結果可以看出，在網絡規模一定時，MPACP協議的平均時延最低。MPACP協議的平均時延受網絡規模影響較小，而SSACM和DSSCS協議的平均時延隨著網絡規模的增大而快速增加。當網絡規模為30個節點時，SSACM系統的平均時延爆炸，已經嚴重影響系統的運行，此時與SSACM和DSSCS協議相比，MPACP的平均時延分別降低了72.37%和28.12%左右。

4.2 業務量對MPACP的影響

在網絡部署成功后，即網絡規模不變，業務量是影響網絡性能的主要因素，當網絡規模固定為10個節點，數據包(即業務量)的到達率分別為0.002 Mbps、0.004 Mbps、0.006 Mbps、0.008 Mbps、0.01 Mbps時，3種協議的平均時延、吞吐量變化如圖7、圖8所示。

圖7 不同業務量下3種協議平均時延對比

圖8 不同業務量下3種協議吞吐量對比

從圖7可以看出，3種協議中，MPACP的平均時延最小。說明MPACP協議通過增加服務器數量，使用同步控制策略，將業務量分擔到多個服務器上分別處理，降低了用戶的平均等待時延。具體分析，當業務量增大時，MPACP協議的平均時延比SSACM減小了1到3倍，比DSSCS減小了50%左右。整個實驗過程中，隨著網絡中業務量的增加，MPACP的平均時延變化不大，保持在5 ms左右，MPACP性能較好。

從圖8可以看出，相同業務量下，MPACP的模型的吞吐量遠遠大于SSACM和DSSCS，也就是說，單位時間內，MPACP能夠傳輸更多的信元數和服務更多的用戶，MPACP協議的服務效率更高。隨著業務量的增加，SSACM和DSSCS協議的吞吐量增加較小，這是因為單一的服務器數量和數據處理方式限制了系統性能提升。這也是SSACM和DSSCS在業務量較高時，平均時延較大的原因。

5 結束語

輪詢代表一類調度控制模型，為系統資源分配提供了一種非競爭的訪問控制機制，在無線傳感器網絡中有著廣泛應用?；趥鹘y的單服務器輪詢控制模型，本文提出使用同步控制方式的多服務器輪詢接入控制協議實現負載均衡，提高輪詢接入協議的服務效率，然后對其進行了理論計算和實驗仿真。分析結果表明，在不同網絡規模和不同業務量情況下，MPACP平均排隊隊長和平均時延都遠遠小于SSACM和DSSCS，MPACP響應速度較快。使用MPACP協議，提高了輪詢系統的服務質量，為物聯網感知層的接入提供了一種控制方式。下一步工作中，可將多服務器接入方式擴展到區分優先級的兩級輪詢接入控制模型中。