楊志軍，寇倩蘭，丁洪偉

（1.云南大學(xué) 信息學(xué)院，云南 昆明 650500；2.云南省教育廳教學(xué)儀器裝備中心，云南 昆明 650223）

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）實(shí)際上就是一個(gè)分布式動(dòng)態(tài)傳感網(wǎng)絡(luò)，由應(yīng)用層、傳輸層、網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層和物理層五個(gè)部分組成，其中，數(shù)據(jù)鏈路層能夠檢測(cè)復(fù)用數(shù)據(jù)幀以及進(jìn)行差錯(cuò)控制，保證點(diǎn)到點(diǎn)之間的可靠性。輪詢系統(tǒng)作為一種排隊(duì)模型，有門(mén)限、完全和限定3 種服務(wù)策略，在無(wú)線傳感器網(wǎng)絡(luò)中得到廣泛應(yīng)用。其中，針對(duì)減少數(shù)據(jù)沖突性、提高輪詢控制系統(tǒng)工作效率、最小化輪詢向量的長(zhǎng)度，同時(shí)避免無(wú)用通信、降低系統(tǒng)延遲和系統(tǒng)穩(wěn)定性等方面一直是研究的重點(diǎn)。

在對(duì)輪詢系統(tǒng)進(jìn)行改進(jìn)的過(guò)程中，專家們從不同方面做了大量研究。文獻(xiàn)[9]提出了一種新的靈活的限定服務(wù)規(guī)則，旨在最短平均隊(duì)列長(zhǎng)度和可預(yù)測(cè)的周期時(shí)間之間取得良好的平衡。由于無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的能量有限，文獻(xiàn)[10]從無(wú)線傳感器網(wǎng)絡(luò)節(jié)能的角度出發(fā)，基于離散時(shí)間的完全服務(wù)輪詢控制，提出分忙閑站點(diǎn)的完全服務(wù)輪詢控制系統(tǒng)。針對(duì)輪詢系統(tǒng)中不同優(yōu)先級(jí)的業(yè)務(wù)問(wèn)題，文獻(xiàn)[11?12]提出區(qū)分優(yōu)先級(jí)的兩級(jí)輪詢服務(wù)模型，實(shí)驗(yàn)結(jié)果表明，與普通模型相比，該模型提高了模型資源利用率和工作效率，性能大幅度提高。文獻(xiàn)[13]提出站點(diǎn)休眠活動(dòng)狀態(tài)的限定=2 輪詢控制系統(tǒng)，在保障系統(tǒng)公平性不受損害的基礎(chǔ)上，區(qū)分站點(diǎn)的休眠活動(dòng)狀態(tài)又避免了對(duì)無(wú)信息分組的休眠站點(diǎn)的服務(wù)，明顯改善了系統(tǒng)性能。但是上述文獻(xiàn)均是在理想信道環(huán)境下進(jìn)行的，缺乏對(duì)實(shí)際信道因噪聲或衰減而產(chǎn)生差錯(cuò)并進(jìn)行重傳的研究。

在此基礎(chǔ)上，文獻(xiàn)[14]研究了具有重傳特性的休假型排隊(duì)模型和單服務(wù)器多隊(duì)列輪詢模型，并分析其穩(wěn)態(tài)隊(duì)列長(zhǎng)度。文獻(xiàn)[15?16]對(duì)輪詢控制系統(tǒng)的重傳和輪詢轉(zhuǎn)換周期進(jìn)行研究。為了減少控制幀消耗，降低系統(tǒng)接入時(shí)延，文獻(xiàn)[17]提出預(yù)約式門(mén)限服務(wù)輪詢接入策略，為非理想信道環(huán)境和差錯(cuò)重傳機(jī)制下的RoF?DAS WLAN網(wǎng)絡(luò)接入性能分析提供了一種快速評(píng)估機(jī)制。本文也是對(duì)重傳輪詢系統(tǒng)進(jìn)行研究，不同的是本文選擇完全服務(wù)策略和限定=1 服務(wù)策略進(jìn)行探究并對(duì)比其性能，具體是指在非理想信道模型中，數(shù)據(jù)包的分發(fā)存在一個(gè)出錯(cuò)率。在實(shí)際應(yīng)用中，用戶通過(guò)中央服務(wù)器輪詢傳輸，每個(gè)用戶的鏈路層使用自動(dòng)重復(fù)請(qǐng)求確保數(shù)據(jù)包的無(wú)錯(cuò)誤發(fā)送。運(yùn)用嵌入式馬爾科夫鏈和概率母函數(shù)分析方法建立數(shù)據(jù)模型，推導(dǎo)平均排隊(duì)隊(duì)長(zhǎng)、平均輪詢周期、吞吐量等系統(tǒng)服務(wù)性能重要指標(biāo)的精確表達(dá)式。最后通過(guò)Matlab 對(duì)系統(tǒng)進(jìn)行建模仿真和對(duì)比分析，驗(yàn)證系統(tǒng)的正確性及不同服務(wù)策略的改進(jìn)效果。

1 系統(tǒng)工作機(jī)制

輪詢控制實(shí)際上是一個(gè)防沖突協(xié)議，但在實(shí)際應(yīng)用中信道環(huán)境常受噪聲、自身衰減和設(shè)備誤差、數(shù)據(jù)包自身錯(cuò)誤等干擾，即存在一個(gè)數(shù)據(jù)包出錯(cuò)率，故本文在傳統(tǒng)輪詢服務(wù)基礎(chǔ)上加入一個(gè)重傳機(jī)制。傳統(tǒng)完全系統(tǒng)服務(wù)規(guī)則具體指獲得發(fā)送權(quán)的終端站需發(fā)送完當(dāng)前終端站內(nèi)所有數(shù)據(jù)包，直至當(dāng)前終端站為空，服務(wù)器再轉(zhuǎn)向下一終端站進(jìn)行服務(wù)。傳統(tǒng)限定=1 系統(tǒng)服務(wù)規(guī)則具體指獲得發(fā)送權(quán)的終端站每次只發(fā)送站點(diǎn)內(nèi)1 個(gè)數(shù)據(jù)包，其余數(shù)據(jù)包等待下一輪詢周期和新到達(dá)的數(shù)據(jù)包以同樣的服務(wù)規(guī)則進(jìn)行發(fā)送。加入重傳機(jī)制后，如圖1所示，當(dāng)數(shù)據(jù)包受到信道質(zhì)量影響出錯(cuò)時(shí)，出錯(cuò)數(shù)據(jù)包都需要進(jìn)行重傳。即數(shù)據(jù)包再次返回源終端站并加入其緩存隊(duì)列尾部，等待下一輪詢周期重新進(jìn)行傳輸，直到正確發(fā)送或重傳次數(shù)達(dá)到閾值為止。若數(shù)據(jù)包的重傳次數(shù)達(dá)到閾值后仍未發(fā)送成功，則當(dāng)前終端站丟棄該數(shù)據(jù)包，放棄重傳。

圖1 數(shù)據(jù)分發(fā)結(jié)構(gòu)圖

2 模型研究

在實(shí)際通信環(huán)境中，數(shù)據(jù)包傳輸?shù)男诺罏榉抢硐胄诺?。系統(tǒng)在下列條件下展開(kāi)工作：

1）到達(dá)各終端站存儲(chǔ)器內(nèi)的數(shù)據(jù)包均服從泊松分布，且相互之間保持獨(dú)立，其概率母函數(shù)為()，均值為=′(1)，方差為=″(1)+-。

2）任意終端站在接受服務(wù)時(shí)成功發(fā)送一個(gè)數(shù)據(jù)包的時(shí)間獨(dú)立同分布，其概率母函數(shù)為()，均值為=′(1)，方差為=″(1)+-。

3）服務(wù)器在任意兩個(gè)邏輯上相鄰的終端站之間的查詢轉(zhuǎn)換時(shí)間獨(dú)立同分布，其概率母函數(shù)為()，均值為=′(1)，方差為=″(1)+-。

4）各個(gè)終端站存儲(chǔ)器的容量巨大，不會(huì)發(fā)生信息分組丟失。

5）數(shù)據(jù)包在終端站存儲(chǔ)器內(nèi)按照先進(jìn)先出（First Come First Service，F(xiàn)CFS）的規(guī)則進(jìn)行發(fā)送。

6）本文是在對(duì)稱輪詢系統(tǒng)基礎(chǔ)上進(jìn)行研究的，故系統(tǒng)達(dá)到穩(wěn)定工作狀態(tài)的條件為：＜1。

給出定義（,=1,2,…,）如下：

1）非理想信道下的數(shù)據(jù)包錯(cuò)誤率，即重傳概率為p；

2）重傳閾值為，出錯(cuò)數(shù)據(jù)包最多可以重傳次，若次后仍失敗，則放棄重傳，丟棄出錯(cuò)數(shù)據(jù)包；

3）服務(wù)器從號(hào)終端站轉(zhuǎn)向+1 號(hào)終端站的查詢轉(zhuǎn)換時(shí)間為u()；

4）服務(wù)器對(duì)號(hào)終端站內(nèi)的數(shù)據(jù)包進(jìn)行服務(wù)的時(shí)間為υ()；

5）數(shù)據(jù)包在u()時(shí)間內(nèi)進(jìn)入號(hào)終端站的數(shù)量為μ(u)；

6）數(shù)據(jù)包在υ()時(shí)間內(nèi)進(jìn)入號(hào)終端站的數(shù)量為η(υ)。

在t時(shí)刻，+1 號(hào)終端站接受服務(wù)器的服務(wù)，此時(shí)其終端站存儲(chǔ)器內(nèi)的數(shù)據(jù)包數(shù)量為ξ()。故整個(gè)排隊(duì)系統(tǒng)在t時(shí)刻隊(duì)列長(zhǎng)度的狀態(tài)變量為{(),(),…,ξ(),…,ξ()}，其概率分布為[ξ()= x;=1,2,…,]，故個(gè)系統(tǒng)狀態(tài)變量的概率分布函數(shù)為π(,,…,x,…,x)，即：

定義π(,,…,x,…,x)的概率母函數(shù)為：

將式（2）代入式（3）得：

2.1 重傳限定K =1 數(shù)學(xué)模型

由以上描述可知，重傳限定系統(tǒng)各個(gè)時(shí)刻狀態(tài)變量滿足下列關(guān)系式：

將式（5）代入式（4），并由式（1）化簡(jiǎn)得：

定義第號(hào)終端站在t時(shí)刻接受服務(wù)，此時(shí)號(hào)終端站內(nèi)存儲(chǔ)的數(shù)據(jù)包數(shù)量為g()，且：

定義：

故：

由式（9）得：

化簡(jiǎn)得：

2.1.1 平均排隊(duì)隊(duì)長(zhǎng)

平均排隊(duì)隊(duì)長(zhǎng)指等待發(fā)送的數(shù)據(jù)包在終端站存儲(chǔ)器內(nèi)的排隊(duì)長(zhǎng)度。

定義：

由式（14）得：

將式（20）代入式（19）并化簡(jiǎn)得到重傳限定=1 服務(wù)系統(tǒng)的平均排隊(duì)隊(duì)長(zhǎng)為：

2.1.2 平均輪詢周期

平均輪詢周期指服務(wù)器連續(xù)兩次查詢同一個(gè)站點(diǎn)所需要的時(shí)間。由式（13）得到重傳限定=1 服務(wù)系統(tǒng)的平均輪詢周期為：

2.2 重傳完全數(shù)學(xué)模型

由文獻(xiàn)[20]可知，在任一時(shí)段內(nèi)，服務(wù)器對(duì)任意一個(gè)終端站內(nèi)到達(dá)的數(shù)據(jù)包以及在服務(wù)期間到達(dá)的數(shù)據(jù)包使用完全服務(wù)方式所需時(shí)間都服從一個(gè)相互獨(dú)立且同分布的概率分布，其概率母函數(shù)為：

對(duì)式（23）求一階導(dǎo)，得：

對(duì)式（24）求二階導(dǎo)，得：

重傳完全系統(tǒng)各個(gè)時(shí)刻狀態(tài)變量滿足下列關(guān)系式：

將式（26）代入式（4），并由式（1）化簡(jiǎn)得：

2.2.1 平均排隊(duì)隊(duì)長(zhǎng)

由式（9）得：

化簡(jiǎn)后得到重傳完全的平均排隊(duì)隊(duì)長(zhǎng)為：

2.2.2 平均輪詢周期

借用文獻(xiàn)[21]方法，推導(dǎo)得出重傳完全的平均輪詢周期為：

2.3 吞吐量

系統(tǒng)吞吐量指單位時(shí)間內(nèi)系統(tǒng)所能傳輸?shù)臄?shù)據(jù)包的個(gè)數(shù)：

3 性能分析

根據(jù)以上理論分析結(jié)果，本文對(duì)重傳輪詢系統(tǒng)在Matlab 平臺(tái)上進(jìn)行仿真。為驗(yàn)證理論分析模型的正確性，本文將理論值與仿真值進(jìn)行對(duì)比。此外，還具體針對(duì)重傳次數(shù)和重傳概率對(duì)系統(tǒng)平均排隊(duì)隊(duì)長(zhǎng)、平均輪詢周期和吞吐量的影響展開(kāi)研究。

假設(shè)重傳輪詢系統(tǒng)中有5 個(gè)終端站，服務(wù)器在相鄰站點(diǎn)間查詢轉(zhuǎn)換率為1 時(shí)隙，對(duì)各個(gè)站點(diǎn)的服務(wù)率為2 時(shí)隙/數(shù)據(jù)包，重傳閾值為1，重傳概率為0.1。在此條件下進(jìn)行仿真，結(jié)果如圖2~圖7 所示。

圖2 重傳限定K =1 服務(wù)平均排隊(duì)隊(duì)長(zhǎng)

圖7 重傳完全服務(wù)吞吐量

由圖2~圖4 可知，重傳限定=1 的平均排隊(duì)隊(duì)長(zhǎng)、吞吐量隨到達(dá)率的增加而不斷增加，與實(shí)際相符。由于平均輪詢周期只與服務(wù)時(shí)間和查詢轉(zhuǎn)換時(shí)間有關(guān)，故平均周期隨到達(dá)率的變化保持一個(gè)相對(duì)穩(wěn)定的狀態(tài)，與實(shí)際相符，且平均排隊(duì)隊(duì)長(zhǎng)、平均輪詢周期和吞吐量的理論值和仿真值誤差較小，故證明了重傳限定=1 的理論分析的正確性。

圖4 重傳限定K =1 服務(wù)吞吐量

由圖5~圖7 可知，重傳完全的平均隊(duì)長(zhǎng)和吞吐量隨到達(dá)率遞增，平均周期保持相對(duì)穩(wěn)定，與實(shí)際相符，且平均隊(duì)長(zhǎng)、平均周期和吞吐量的理論值與仿真值大致相等，驗(yàn)證了理論分析的正確性。由式（22）、式（32）、式（33）可知，在同一條件下，重傳完全和重傳限定=1 系統(tǒng)各自的平均周期和吞吐量的理論值是相等的。對(duì)比圖3和圖6、圖4 和圖7，可以看出重傳完全的理論值和仿真值的誤差略小于重傳限定=1，仿真效果更好。對(duì)比圖2 和圖5，明顯看出重傳完全平均隊(duì)長(zhǎng)的理論值和仿真值的誤差也略小于重傳限定=1。再次說(shuō)明重傳完全的仿真效果更好，但兩者差距不大。以下將針對(duì)這兩個(gè)系統(tǒng)做更加細(xì)致的研究。

圖3 重傳限定K =1 服務(wù)平均輪詢周期

圖5 重傳完全服務(wù)平均排隊(duì)隊(duì)長(zhǎng)

圖6 重傳完全服務(wù)平均輪詢周期

在上述查詢轉(zhuǎn)換率、服務(wù)率和終端站個(gè)數(shù)的基礎(chǔ)上，將傳統(tǒng)限定和完全模型與重傳限定和完全模型進(jìn)行對(duì)比，如圖8 所示。在相同吞吐量條件下，重傳輪詢系統(tǒng)的平均隊(duì)長(zhǎng)略高于傳統(tǒng)輪詢，這是因?yàn)樵诜抢硐胄诺乐?，部分?jǐn)?shù)據(jù)包出錯(cuò)需要進(jìn)行重傳，直到成功發(fā)送或超過(guò)重傳閾值被丟棄。故數(shù)據(jù)包在終端站的排隊(duì)長(zhǎng)度比理想信道更長(zhǎng)。對(duì)于傳統(tǒng)輪詢系統(tǒng)，當(dāng)?shù)竭_(dá)率小于0.004 時(shí)，限定=1 和完全服務(wù)的平均隊(duì)長(zhǎng)幾乎相等；當(dāng)?shù)竭_(dá)率大于0.004 時(shí)，限定=1 的平均隊(duì)長(zhǎng)略大于完全服務(wù)。加入重傳機(jī)制后，當(dāng)?shù)竭_(dá)率小于0.007 時(shí)，重傳限定=1 和重傳完全服務(wù)的平均隊(duì)長(zhǎng)幾乎相當(dāng)；當(dāng)?shù)竭_(dá)率大于0.007 時(shí)，重傳限定=1 的平均隊(duì)長(zhǎng)逐漸大于完全服務(wù)。由此看出加入重傳機(jī)制后，并沒(méi)有對(duì)限定=1 服務(wù)和完全服務(wù)平均隊(duì)長(zhǎng)的整體趨勢(shì)產(chǎn)生明顯的影響。當(dāng)?shù)竭_(dá)率較小時(shí)，重傳限定=1 服務(wù)的平均排隊(duì)隊(duì)長(zhǎng)與重傳完全大致相等。

圖8 平均隊(duì)長(zhǎng)對(duì)比

同樣地，在以上實(shí)驗(yàn)條件下，對(duì)比重傳概率為0.01，0.1，0.15，0.2 時(shí)系統(tǒng)的平均隊(duì)長(zhǎng)。由圖9、圖10 可知，基于相同負(fù)載，重傳概率越大，系統(tǒng)的平均隊(duì)長(zhǎng)也相應(yīng)增加。隨到達(dá)率增加，不同重傳概率的平均隊(duì)長(zhǎng)之間的差距越明顯，且針對(duì)不同重傳概率的平均隊(duì)長(zhǎng)，重傳限定=1 各隊(duì)長(zhǎng)之間的差距小于重傳完全服務(wù)。故重傳限定=1 的系統(tǒng)性能受重傳概率變化的影響較小，對(duì)比重傳完全服務(wù)其系統(tǒng)性能更加穩(wěn)定。

圖9 重傳限定K =1 服務(wù)平均隊(duì)長(zhǎng)與重傳概率的關(guān)系

圖10 重傳完全服務(wù)平均隊(duì)長(zhǎng)與重傳概率的關(guān)系

設(shè)定系統(tǒng)終端站為5 個(gè)，到達(dá)率為0.005 數(shù)據(jù)包/時(shí)隙，服務(wù)率為2 時(shí)隙/數(shù)據(jù)包，查詢轉(zhuǎn)換率為1 時(shí)隙。取重傳閾值從1~10 以1 為步長(zhǎng)依次遞增，對(duì)比重傳概率為0.01，0.1，0.15，0.2 時(shí)系統(tǒng)平均排隊(duì)隊(duì)長(zhǎng)的變化。由圖11、圖12 可知，在非理想信道環(huán)境下，基于相同負(fù)載重傳閾值對(duì)系統(tǒng)平均隊(duì)長(zhǎng)的影響隨重傳概率的增大而增大。當(dāng)p=0.01 時(shí)，重傳次數(shù)的變化不會(huì)對(duì)平均隊(duì)長(zhǎng)產(chǎn)生影響，隊(duì)長(zhǎng)收斂于一個(gè)特定的數(shù)。當(dāng)p=0.1 和p= 0.15 時(shí)，若≤3，系統(tǒng)平均排隊(duì)隊(duì)長(zhǎng)隨的增大而逐漸增大；若＞3，系統(tǒng)平均排隊(duì)隊(duì)長(zhǎng)收斂于一個(gè)特定的數(shù)。當(dāng)p=0.2 時(shí)，若≤4，系統(tǒng)平均排隊(duì)隊(duì)長(zhǎng)隨增大而增大；若＞4，系統(tǒng)平均排隊(duì)隊(duì)長(zhǎng)收斂于一個(gè)特定的值，且重傳概率越大，平均隊(duì)長(zhǎng)收斂的特定值越大。由此可見(jiàn)，系統(tǒng)平均隊(duì)長(zhǎng)受重傳概率影響較大，當(dāng)重傳概率確定時(shí)，系統(tǒng)平均排隊(duì)隊(duì)長(zhǎng)可收斂于一個(gè)特定的值，不再受重傳次數(shù)的影響。

圖11 重傳限定K=1 服務(wù)平均隊(duì)長(zhǎng)與重傳次數(shù)的關(guān)系

圖12 重傳完全服務(wù)平均隊(duì)長(zhǎng)與重傳次數(shù)的關(guān)系

綜上所述，重傳完全和重傳限定=1 服務(wù)的吞吐量及輪詢周期相同?；谙嗤?fù)載，重傳完全系統(tǒng)的平均隊(duì)長(zhǎng)小于重傳限定=1 系統(tǒng)，故信息處理效率更高。重傳概率即數(shù)據(jù)包出錯(cuò)率，對(duì)系統(tǒng)性能影響較大，換言之，信道質(zhì)量越好，數(shù)據(jù)處理效率越高，反之，效率越低。信道質(zhì)量一定時(shí)，系統(tǒng)性能也趨于穩(wěn)定。

4 結(jié) 語(yǔ)

本文研究了非理想信道環(huán)境下，在傳統(tǒng)輪詢系統(tǒng)中加入重傳機(jī)制，即出錯(cuò)數(shù)據(jù)包需返回源終端站，等待下一次重新發(fā)送，直到發(fā)送成功或重傳次數(shù)超過(guò)閾值該數(shù)據(jù)包被拋棄。具體研究了重傳限定=1 和重傳完全兩種服務(wù)策略。運(yùn)用嵌入式馬爾科夫鏈和概率母函數(shù)方法對(duì)這兩種模型進(jìn)行數(shù)學(xué)分析和理論推導(dǎo)，得出系統(tǒng)平均排隊(duì)隊(duì)長(zhǎng)、平均輪詢周期和吞吐量的理論表達(dá)式，并在Matlab平臺(tái)對(duì)系統(tǒng)進(jìn)行仿真。結(jié)果證明系統(tǒng)的理論值和仿真值誤差較小，驗(yàn)證了理論分析的正確性。本文將非理想信道下的重傳模型與理想信道下的傳統(tǒng)輪詢模型進(jìn)行對(duì)比，結(jié)果發(fā)現(xiàn)，重傳模型的平均排隊(duì)隊(duì)長(zhǎng)略高于傳統(tǒng)服務(wù)方式，與實(shí)際相符，再次驗(yàn)證了其理論分析的正確性。最后，通過(guò)在不同重傳概率和重傳次數(shù)下系統(tǒng)性能的對(duì)比，得出重傳概率對(duì)系統(tǒng)性能的影響較大，重傳次數(shù)對(duì)系統(tǒng)性能的影響較小。未來(lái)工作中，本文將進(jìn)一步在降低重傳概率、提高信息傳輸效率方面展開(kāi)研究。