連續時間兩級完全輪詢接入MAC協議分析

楊志軍，毛 磊，丁洪偉，寇倩蘭

1.云南大學 信息學院，昆明650500

2.云南省教育廳 教學儀器裝備中心，昆明650223

物聯網是第三次信息產業革命的產物，其一經提出就獲得了空前發展。它借助各種類傳感器設備，對各類信息進行采集，并將處理后的信息通過互聯網傳遞給用戶，以此來實現人與人、人與物、物與物之間的任意通信。在這個過程中，物聯網感知層內涉及多種不同優先級的業務，對不同業務進行區分非常有必要，這就需要用到媒介訪問控制協議（medium access control，MAC）。MAC 協議規定了節點傳輸數據時占用無線信道的方式，它通過通信協議和通信機制，降低傳輸時延，提高網絡的吞吐量和服務質量[1-2]。因此MAC協議性能的好壞決定了物聯網的數據傳輸能力。通信網絡中MAC協議數據傳輸的可靠性和實時性也一直是研究的熱點[3-5]。文獻[6]基于時分多址（time division multiple access，TDMA）的MAC 協議，提出一種BEST-MAC 協議用于無線傳感器網絡，該協議平均數據包延遲較小，相同時間內能夠傳輸更多的數據。文獻[7]提出一種新穎的基于動態公共控制信道的協議（DCCC-MAC），用于認知無線電網絡，與傳統的基于專用控制信道的MAC 協議不同，該協議消除了用于控制信息交換的專用信道的需求。文獻[8]提出基于異步占空比的MAC 協議（ADPMAC），通過監視傳入流量的變化來切換接收器節點的輪詢間隔分布，研究發現當ADP-MAC的流量到達和輪詢間隔分布一致時，就延遲和能量而言，性能都是最佳的。通過對比可知，上述研究雖然在一定程度上降低了網絡時延，提高了MAC協議的性能，但并未對網絡中業務的優先級進行區分。

基于輪詢接入的MAC協議是一種非爭用的接入機制，它在數據傳輸之前為各個節點分配信道資源，在整個通信過程中，占用信道的節點獨享分配到的各項資源，從而使網絡節點實現數據的無沖突傳輸[9-11]。輪詢系統根據查詢時刻節點發送信息分組的個數，可以分為完全服務[12]、門限服務[13]和限定服務[14]三種，其中完全服務模式用戶的平均等待時延最低，限定服務模式的公平性最好，門限服務模型介于二者之間。由于無沖突的傳輸方式、輪詢接入控制方式在無線傳感器網絡和計算機網絡中有著廣泛應用，隨著研究的發展，它的服務方式也不斷擴展[15-17]。文獻[18]在離散時間基礎上，研究了對稱和非對稱相結合的兩級混合輪詢控制策略，普通站點采用非對稱門限服務模式，優先級站點采用完全服務模式，該系統能對網絡中不同優先級的業務進行區分，但由于優先級用戶和普通用戶的服務模式不同，一定程度上降低了系統的公平性。同時該系統普通站點采用門限服務，用戶的平均等待時延還有待提高。文獻[19]中對站點狀態進行區分，根據站點中是否有發送請求將站點分為忙閑狀態，每次輪詢時，服務器僅對忙站點進行服務，降低了網絡能耗。文獻[20]對門限服務模式進行了改進，將服務時間和輪詢調度時間同步處理，提高了輪詢接入控制MAC 協議的服務效率。兩種MAC 協議分別從能耗和服務效率的角度，對輪詢系統進行了研究，由于兩種系統采用的都是單一服務模式，仍然沒有解決區分優先級業務的問題。

上述對于輪詢接入控制方式的分析，大多是采用時間離散型分析方法，系統的二階特性求解相對復雜，而時間連續型分析方法能對系統的關鍵參數進行拉普拉斯變換，簡化求解過程。本文在此基礎上，提出兩級完全輪詢接入控制MAC協議，對用戶劃分不同的優先級，綜合考慮物聯網對實時性的需求，采用完全服務模式來保障網絡的時延和服務的公平性。然后在時間連續型分析方法的基礎上，構建數學模型，使用概率母函數的方法對該協議的一階、二階特性進行了解析，最后在MATLAB上進行仿真實驗，對理論分析進行驗證，并對該協議的性能進行分析。

1 系統模型

連續時間兩級完全輪詢接入控制模型由N+1 個節點和一個匯聚節點（服務器）共兩級組成，第一級是N個普通站點，站點序號用{1,2,…,i,…,N}來表示，第二級是一個優先級站點，用下標h來表示，系統模型如圖1 所示。物聯網感知層的節點主要分為采集節點和匯聚節點，采集節點對環境中的數據進行采集；匯集節點按照規定的MAC協議接收各個采集節點的數據。在匯集節點接收數據的過程中，門限服務和限定服務模式都會產生中斷，而完全服務只有在服務完一個站點，站點為空之后才會轉去服務下一個站點，不會產生中斷，三種模式中，它的平均等待時延最低。因此采用完全服務模式為優先級節點和普通節點提供數據傳輸服務。

圖1 系統模型Fig.1 System model

在連續時間的基礎上，以時隙為單位劃分時間軸。在任意一個時隙內，都有數據到達優先站點和普通站點等待傳輸。這里的連續時間指的是信息分組的到達是以某一時間點為準的，使用連續型分析方法，主要是為了對系統的關鍵參數做拉普拉斯變換。服務開始后，服務器首先對優先級站點提供服務，服務完成后轉去查詢普通站點，然后再查詢優先級站點，以此類推。優先級站點向普通站點切換的時候，采用同步處理的方式節省轉換時間，提高系統的服務效率，即服務器在為優先級站點提供完全服務的同時順帶查詢i號普通節點。

2 數學模型

輪詢接入MAC協議的性能，通常使用系統的一階、二階特性來描述。一階特性指的是用戶的平均排隊隊長、系統吞吐量和平均循環周期；二階特性指用戶的平均等待時延。因此定義隨機變量，構建數學模型來分析該系統的性能。

2.1 系統工作條件

使用輪詢控制機制進行數據傳輸時，各個節點之間的數據傳輸不會發生碰撞和沖突，但并不排除信道干擾等因素導致的數據傳輸失敗現象。因此假設各節點之間的數據通信正常，匯聚節點的存儲區不會發生數據溢出。

根據輪詢系統的工作機制，通信過程中數據的到達過程和傳輸特性，定義以下工作條件：

（1）數據信息在任一個時隙內到達每一個站點的過程服從相互獨立的泊松分布，普通站點的達到率為λi，優先級站點的到達率為λh。

（2）服務器每傳輸普通站點中的一個數據所需要的時間是獨立、相同分布的概率分布，其隨機變量的拉普拉斯變換（Laplace transform，LST）為，均值為，二階原點矩為；優先級站點的分布為，均值和二階原點矩分別為。

（3）服務器從i號普通站點向優先站點轉移的時間服從獨立、相同分布的概率分布，其隨機變量的LST 為，均值為，二階原點矩為。

（4）服務器按照數據到達的先后順序為站點中的數據提供服務。

2.2 隨機變量

為了對系統的性能參數進行分析，定義以下隨機變量，如表1。

表1 隨機變量定義Table 1 Definition of random variables

在對系統進行建模時，考慮三個時刻，tn、tn*、tn+1(tn+1＞tn*＞tn)。假設tn時刻，服務器開始對i號站點中的數據進行傳輸，此時系統的隨機變量為{ξ1(n),ξ2(n),…,ξi(n),…,ξN(n),ξh(n)}；tn*時刻，服務器完成對i號站點的服務，轉向優先級站點提供完全服務，此時系統的狀態變量可表示為{ξ1(n*),ξ2(n*),…,ξi(n*),…,ξN(n*),ξh(n*)}；tn+1時刻服務器又轉換到i+1 號普通站點，系統的狀態為{ξ1(n+1),ξ2(n+1),…,ξi(n+1),…,ξN(n+1),ξh(n+1)}。通過分析可知，tn時刻系統的狀態只與tn*時刻有關，tn+1時刻系統的狀態只與tn*時刻有關，該系統的N+1 個狀態構成馬爾可夫鏈，由于系統內站點數量是確定的，服務器按照輪詢順序依次訪問各個站點，所以該馬爾可夫過程是有限和各態歷經的。

2.3 概率母函數

根據定義的隨機變量和服務器的輪詢順序，可以得到下列關系式：

為了準確構建系統的數學模型，引入概率母函數的分析方法，上面描述的嵌入式馬爾可夫鏈在的條件下保持穩定，其中ρi=λiβi表示系統負載。

穩態時，系統狀態變量的概率分布函數為：

通過對概率母函數的定義分析可以得到，πi(x1,x2,…,xi,xN,xh)的母函數為：

tn*時刻服務器為優先站點提供服務，此時，系統變量的概率母函數為：

tn+1時刻轉換到i+1 號普通站點，系統變量的概率母函數為：

3 系統特性解析

3.1 平均排隊隊長

定義1每個站點內等待發送的信息分組數為平均排隊隊長。tn時刻，i號站點開始傳輸數據時，j號站點的平均排隊隊長為，則

3.2 平均循環周期

定義2 系統的平均循環周期為服務器按照規定的輪詢順序對所有站點完成一次訪問所經歷的時間，也就是服務器對同一個普通站點連續兩次訪問所經歷的時間間隔，計算如下：

3.3 系統吞吐量

定義3 系統吞吐量為單位時間內完全服務兩級輪詢系統所能傳輸的信息量，用T表示，計算方式為：

3.4 一階特性

定義4表示i號站點接受服務期間，k號站點中等待的數據包的平均排隊隊長，則：

3.5 二階特性

定義5 普通站點隨機變量(xj,xk)的聯合矩為；優先級站點隨機變量(xj,xk)的聯合矩為，則由概率母函數可得：

將式（4）、（5）代入式（12）、（13）可得：

其中，C=(N-1)(2ρρh-N)+2ρh(ρh-1-N)，D=[(N-1)ρ-(1-ρh)][(1-ρh)(1-ρ)2+ρ2]

3.6 平均等待時延

定義6 系統的平均等待時延為信息分組數從進入站點直到其被發送出去的時間間隔。用E[Wi]和E[Wh]分別表示普通站點和優先級站點的平均等待時延，則根據文獻[12]，將式（7）、（8）、（14）、（15）代入可得。

普通站點的平均等待時延為：

優先級站點的平均等待時延為：

4 仿真實驗及性能分析

4.1 仿真實驗

根據3.1節定義的條件，在MATLAB2018a平臺上進行仿真實驗，驗證理論分析的可靠性。系統在+λhβh＜1 的條件下保持穩定，根據式（7）～（10）、（16）、（17）計算出理論值，然后與實驗值比較。

在該系統中，其初始化條件為開始時刻，各個站點內沒有信息分組需要發送。站點提出發送請求后，服務器首先對優先級站點中的數據進行傳輸，直到站點內所有數據被傳輸完畢。然后轉去訪問i號普通站點，對i號站點內的數據進行傳輸，發送完所有的數據后，又再次轉去查詢優先級站點h，以此類推，服務完優先級站點后，又轉去查詢i+1 號普通站點，即輪詢順序為：h→1→h→2…h→N→h→1。系統控制算法流程如下所示：

實驗中相關參數設置參照IEEE802.11n標準。基于Matlab 偽隨機數，生成到達率為λ的泊松分布序列，用于模擬系統各隊列單位時間內到達的信息分組數，到達率越大，單位時間內到達系統的信息分組數越多。在信道傳輸速率和服務器處理能力一定時，排隊等待的數據也就越多。采用服務時間變量記錄系統中數據服務消耗的時間累計，數據序列每減少一個單位，服務時間變量累計一個服務時間，用β表示，β越小，表明系統數據處理能力越強，吞吐量越大。查詢轉換時間γ是衡量輪詢效率的重要指標，γ越大，系統輪詢一周的所花時間越長，效率越低。在無線傳感器網絡中，節點數表示網絡規模，節點數越多網絡規模越大。信道速率表示單位時間內信道上所能傳輸的數據量。實驗中按間時隙劃分時間軸，1 時隙等于10 μs，每個信息分組的長度設定為1 000 Byte。具體參數設置如表2 所示，仿真結果為相同參數下10萬次蒙特卡洛實驗統計。

表2 仿真實驗參數設置Table 2 Parameter setting of simulation experiment

4.2 性能分析

實驗中，通過改變數據的到達率和網絡的節點個數，分析系統平均排隊隊長、平均等待時延和平均循環周期的變化規律，如圖2～5 所示，首先從各圖都可以看出理論值與實驗值一致，說明理論分析是完全正確的，接下來對系統的性能做進一步分析。

圖2 平均排隊隊長與到達率的關系(λ=λh,β=βh=4,γ=1,N=10)Fig.2 Relationship between average queue length and arrival rate

圖2 和圖3 是系統平均排隊隊長、平均等待時延與到達率的關系。從圖可以看出無論是普通站點還是優先級站點，當服務時間、轉移時間和站點數量固定不變時，平均排隊隊長和平均等待時延與到達率是正相關的。普通站點平均排隊隊長和平均時延的變化是同步的，平均排隊隊長越長，相應的平均等待時延也越大。對比普通站點和優先站點的平均排隊隊長和平均等待時延，可以看出，優先站點的平均排隊隊長和平均等待時延遠遠小于普通站點。隨著到達率的增大，這種區分仍然很明顯，說明該系統能對不同優先級的業務進行區分，并且區分的效果很好。

圖3 平均等待時延與到達率的關系(λ=λh,β=βh=4,γ=1,N=10)Fig.3 Relationship between average delay and arrival rate

表3是不同參數下，普通站點和優先級站點平均排隊隊長和平均時延理論值與實驗值的對比，實驗中，優先站點和普通站點的參數不同。首先可以看出，理論值與實驗值基本擬合，誤差保持在較小范圍內。進一步分析，在普通站點和優先站點參數不同的情況下，無論是普通站點的到達率和服務時間大于優先站點，還是優先站點的到達率和服務時間大于普通站點，優先站點的平均排隊隊長和平均時延總是小于普通站點，說明兩級完全服務區分優先級業務的能力較強。

表3 普通站點和優先站點實驗值與理論值對比Table 3 Comparison of experimental values and theoretical values of ordinary stations and priority station

圖4是不同數量站點下，系統平均循環周期隨到達率的變化關系。可以看出，不同數量站點下，系統的平均循環周期隨著到達率的增加而增大。當到達率和站點數量較小時，系統很快就能完成對所有站點的輪詢，說明系統的響應速度較快。從三條曲線的垂直分布來看，站點數量也是影響系統平均循環周期的重要因素，在到達率一定時，站點數量越多，周期越長，系統的響應速度越慢。

圖4 不同站點平均循環周期隨到達率的變化(λ=λh,β=βh=4,γ=1)Fig.4 Change of average cycle with arrival rate at different sites

圖5 是系統吞吐量與到達率的關系，實驗中，可以看出吞吐量隨著到達率線性增加，說明當普通站點和優先站點的到達率相同時，吞吐量與到達率是線性關系，這與理論分析是吻合的。

圖5 吞吐量與到達率的關系(λ=λh,β=βh=4,γ=1,N=10)Fig.5 Relationship between throughput and arrival rate

圖6和圖7是兩級完全服務與單級完全服務平均排隊隊長、平均等待時延的對比分析。為了保證實驗的準確性，兩種協議的網絡規模應該一致。因此實驗中，單級完全服務設置11個站點，11個站點的優先級一致，兩級完全服務設置10個普通站點和一個優先級站點。首先對比普通站點的平均排隊隊長和平均時延，兩級完全服務普通站點的隊長和時延都小于單級完全服務，說明優先級站點使得整個系統的性能發生了改變，設置兩級服務對不同優先級的業務進行區分，在一定程度上優化了普通站點的性能。然后對比兩級完全服務優先站點的平均隊長和平均等待時延，可以看出，優先站點的隊長和時延遠遠小于普通站點和單級完全服務，說明連續時間兩級完全服務區分業務優先級的效果顯著，達到了提出該系統的初衷。從控制機理的角度來分析，兩級完全服務將原有單級完全服務中的N+1 個同優先級站點劃分為1個優先級站點和N個普通站點，在一次輪詢過程中，服務器對優先級站點提供N次完全服務，而每個普通站點僅提供一次完全服務，所以優先級站點的平均排隊隊長和平均等待時延遠遠小于普通站點。一次輪詢過程中，多次服務優先站點，保障了優先業務能夠及時得到服務，滿足了系統內優先業務或核心業務對實時性的要求。

圖6 兩級與單級完全服務平均排隊隊長對比(N=10,β=4,γ=1)Fig.6 Comparison of average queue length between two-level and single-level exhaustive service

圖7 兩級與單級完全服務平均等待時延對比(N=10,β=4,γ=1)Fig.7 Comparison of average delay between two-level and single-level exhaustive service

4.3 對比分析

圖8是本文協議與文獻[18]提出的混合輪詢控制策略和文獻[20]提出的并行調度門限服務策略的對比分析。在網絡參數相同的情況下，與文獻[18]對比，本文所提協議普通站點和優先級站點的平均等待時延更小，說明本文所提協議性能更優；與文獻[20]對比，本文所提協議在區分優先級業務的同時，降低了普通用戶的平均等待時延，提高了系統的服務質量。

圖8 三種協議平均等待時延的對比分析(N=11,β=βh=2,γ=1)Fig.8 Comparative analysis of average delay of three protocols

表4是文獻[17]提出的門限、完全兩級服務與本文提出的連續時間兩級完全服務模型的平均隊長和時延對比分析。從表中可以看出，在到達率一樣的情況下，兩種模型的平均排隊隊長是一樣的，說明改變服務方式不會影響系統中的顧客數。從平均等待時延來看，連續時間兩級完全服務的時延要小于門限、完全兩級服務。表明本文提出的兩級完全模型性能更優，在區分優先級的同時，又能獲得較小的平均等待時延和更高的服務質量。相同業務量的情況下，本文模型能更好地滿足核心業務或優先業務對于實時性的要求，同時，由于普通站點和優先站點都使用相同的服務方式，進一步確保了用戶的公平性。

表4 兩種模型普通站點平均排隊隊長和平均時延對比Table 4 Comparison of average queue length and average delay between two models

5 結束語

本文使用連續時間的分析方法，提出一種區分優先級業務的兩級輪詢接入協議，普通站點和優先站點都使用完全服務。然后運用數學分析方法對該協議進行建模，精確解析出了該系統的一階特性和二階特性。最后運用仿真實驗對理論分析進行驗證并分析了系統的性能。通過實驗分析，可以看出本文提出的兩級完全服務模型，在對不同優先級業務進行區分的同時，保證了普通站點的服務質量。該系統在一次輪詢中，多次訪問優先站點保證了優先業務可以優先得到服務，而普通站點使用時延較小的完全服務，不僅降低了普通用戶的等待時間，還保證了公平性。與單級完全服務輪詢系統相比，該系統不僅適應了物聯網中優先級業務的需求，還優化了普通業務；與其他兩級輪詢模型相比，該系統普通站點的平均時延較小，實時性更高。在今后的研究工作中，可以劃分更多的優先級來進一步提高該協議的服務質量。