基于隊列理論CSMA/CA機制的無線傳感器異構機制OSTS的實時性分析

呂春峰，朱建平

（上海交通大學 電子信息與電氣工程學院，上海 200240）

隨著無線通信、集成電路、傳感器以及微機電系統(tǒng)（MEMS）等技術的飛速發(fā)展和日益成熟，低成本、低功耗、多功能的微型傳感器的大量生產成為可能。這些傳感器在微小體積內通常集成了信息采集、數據處理和無線通信等多種功能。無線傳感器網絡（WSN）就是由部署在監(jiān)測區(qū)域內大量的微型傳感器節(jié)點通過無線電通信形成的一個多跳的自組織網絡系統(tǒng)，其目的是協(xié)作的感知、采集和處理網絡覆蓋區(qū)域里被監(jiān)測對象的信息，并發(fā)送給觀察者。由于微型傳感器的體積小、重量輕，有的甚至可以像灰塵一樣在空氣中浮動，因此，人們又稱無線傳感器網絡為“智能塵埃”，將它散布于四周以實物感知物理世界的變化。異構性[1]是無線傳感器網絡一個非常重要的特征，眾多因素決定了異構性是無線傳感器網絡內在、泛在的特征。文中根據火場監(jiān)控應用的實時性需要，針對傳輸火場環(huán)境下的溫度及濕度這兩個異構數據包到sink節(jié)點的無線傳感器異構網絡，基于隊列理論分析其網絡傳輸的實時性特征，提出了一種新的CSMA/CA機制OSTS（一次獲得信道，只傳一個數據包機制），以此分析及提高系統(tǒng)監(jiān)控性能。

1 建立模型

隨著IEEE802.15.4標準[2]的發(fā)布，無線傳感器的應用取得突飛猛進的發(fā)展，其應用早已經由軍事國防領域擴展到環(huán)境監(jiān)測、交通管理、醫(yī)療健康、工商服務、反恐抗災等諸多領域，使人們在任何時間、任何地點和任何環(huán)境條件下都能夠獲取大量翔實可靠的信息，最終成為一種“無處不在”的傳感技術。無線傳感器網絡的性能優(yōu)勢使得其應用幾乎涉及到我們生活的方方面面；但是無線傳感器網絡依然在很多方面存在缺陷，諸如使用電池供電引起節(jié)能的需求，公平性、實時性、吞吐量的有待提高等等。

針對于實際應用，提出了異構網絡的實時性要求，詳細、綜合分析兩種不同性質的數據包以公平的機會訪問信道的時間性能，找到合適參數以減少數據包訪問時間、提高實時性要求。

在提出OSTS機制，建立分析模型之前，先作出如下的假設：假設信標指數為4，所以每個包都能在同一個超幀傳送完[3]；數據包的接受確認可以無需通過ACK[4-5]來執(zhí)行；為了避免成功獲取信道的節(jié)點永久占用信道，參與競爭的所有節(jié)點而不僅僅是傳送節(jié)點將其backoff計數器降為最小值；傳完一個數據包后，信道為空的概率μ0與任何時刻信道為空的概率P0不相等；系統(tǒng)中存在2種節(jié)點，節(jié)點個數分別為N1和N2，到達節(jié)點的流量滿足泊松（Poisson）過程且數據包到達率分別為λ1和λ2；參與競爭的數據包都是每個隊列的首數據包，那么可以簡化競爭機制，即只考慮參與競爭的數據包。這樣，采用3個馬爾可夫鏈模型來描述，其中兩個半馬爾可夫鏈分別表示兩種數據包訪問信道的過程，如圖1所示，這個鏈是[5]的改進；一個宏觀馬爾可夫鏈表示信道的狀態(tài)，如圖2所示。

首先，考慮OSTS機制的節(jié)點訪問信道的馬爾可夫過程。每次參與競爭的數據包，無論是哪種類型的節(jié)點包都有公平的機會訪問信道，所以只需要考慮任意一種類型的數據包訪問信道的過程，而圖1的實線過程表示一種節(jié)點的實際訪問過程，虛線過程表示另一種數據包也在同時參與訪問信道，但是并不是真正傳送，僅描述它們的一種并行的公平的競爭關系。定義 S（t）（S∈（0，…，m）），C（t）（C∈（-2，…，Wi-1）），r（t）（r∈（0， …，r）） 分別為在時刻的 backoff階段計數器大小，backoff計數器大小，重傳計數器大小。任何一個節(jié)點獲得信道之后，就開始傳送其隊列中的首包，傳送該包完成后重新參與其他的節(jié)點的競爭信道的過程，即一次獲得信道，只傳一個數據包機制（One Service a Time Scheme）。

圖1 時隙化的IEEE 802.15.4 CSMA/CA機制的馬爾可夫鏈模型Fig.1 Markov chain model for slotted IEEE 802.15.4 CSMA/CA scheme

根據圖1馬爾可夫鏈的鏈式規(guī)則，可以得到關于各個狀態(tài)間的關系式（1）～（4）。 其中式（1）表示節(jié)點獲得了新包，隨機選擇backoff計數器后進行退避過程的轉移概率；式（2）表示節(jié)點不論信道的狀態(tài)，都以概率1遞減其backoff計數器的轉移概率；式（3）表示節(jié)點在任意一個CCA發(fā)現(xiàn)信道忙后進入下一個backoff階段的轉移概率；式（4）表示達到最大backoff階段后節(jié)點選擇下一次重傳的轉移概率。

圖2 宏觀馬爾可夫鏈Fig.2 Macroscopic states transition for two types of nodes

其次，從信道的狀態(tài)來看，兩種數據包的訪問信道的狀態(tài)轉移情況可以直觀地從圖2中宏觀馬爾可夫鏈看出，并且得到式（5）～（11）。 其中式（5）～（7）分別表示任何一種節(jié)點在訪問失敗、最后一次重傳的沖突傳送、每次重傳的成功傳送，若緩存中沒有其他數據包，那么直接轉移到idle狀態(tài)的轉移概率；式（8）表示任何一個節(jié)點都沒有新數據包，處于idle狀態(tài)的概率；式（9）～（11）分別表示任何一種節(jié)點在訪問失敗、最后一次重傳的沖突傳送、每次重傳的成功傳送，若緩存中還有其他數據包，那么重新轉移到競爭傳送狀態(tài)的轉移概率。

定義 bi，k，j=P{s（t），c（t），r（t）=i，k，j}為馬爾可夫鏈的穩(wěn)態(tài)轉移概率，那么根據馬爾可夫鏈和其狀態(tài)轉移的規(guī)則，可以得到式（12）。通過歸一化處理，得到式（13）。式13中每個量分別為表達式（14）和（15）。式（14）表示一種類型的包在訪問信道時backoff過程穩(wěn)態(tài)概率、CCA1概率、CCA2概率、成功傳送概率、沖突傳送概率。式（15）表示空閑概率，其中P0表示任何時刻信道為空的概率，μ0表示傳完一個數據包后，信道為空的概率。

從上面的分析中，看到這些概率實際上都是與信道的操作點α，β，τn有關，且這些操作點參數決定了數據包的訪問時間度量，其中α表示節(jié)點在CCA1后發(fā)現(xiàn)信道忙的概率；β表示節(jié)點在CCA2都發(fā)現(xiàn)信道忙的概率；τn表示節(jié)點偵聽信道的概率。第二部分會詳細分析這個操作點以獲取訪問時間性能分析。

2 延時性能分析

在低速率傳輸的WSN中，除了能耗是個重要的參數，實時性也是一個非常重要的參數，特別是對于這樣的實時性要求比較高的應用環(huán)境。訪問時間度量（delay）是指從數據包到達MAC隊列的時刻到數據包成功傳送的時刻之間的時間。假設理想信道，那么數據包的失敗率只是因為數據包之間的沖突。因每次競爭都是節(jié)點隊列中的首包，那么簡單的從數據包訪問情況來獲得信道的操作點，其中τn就是所有backoff計數器降為0的概率。

從上面的式（18）～（20）可以看到操作點參數可以通過數學迭代的方法唯一求出，從而可以得到數據包的傳輸時間度量。引入M/G/1/K隊列理論分析節(jié)點中的數據包的傳送情況。隊列有K個數據包，每個數據包的長度為L，每個數據包的傳送時間的概率母函數為 Ttr（Z）[6]，那么 P0和 μ0為：

通過迭代的方法，可以求出 μ0n，并且：

數據包的平均訪問時間delay用概率母函數表示如下表達式（23）：

那么，數據包的傳送時間的LST[3]為：

3 仿真驗證

通過NS-2仿真軟件來驗證數據包的實時性能。參考文獻[7]所述的仿真搭建我們的仿真平臺。所有節(jié)點都分布在以sink節(jié)點為圓心、半徑為5 m的圓內；每個節(jié)點都在彼此的傳輸范圍內，節(jié)點的傳輸距離為11 m；每個節(jié)點都能偵聽到其他節(jié)點的傳輸，也就是說不存在隱藏終端。仿真參數如表1所示。

表1 仿真參數Tab.1 Parameters for simulations

根據式（24）的分析，可以看到數據包的傳送時間度量（我們將所有的時間度量歸一化為backoff時間大小）與MAC參數、系統(tǒng)的操作點、數據包長度和緩存大小有關系。MAC的參數選取backoff計數器的初始值為m=5；backoff階段值為23；重傳計數器為r=3；數據包的長度為L=5個backoff大小。而每種情況的操作點可以根據式（18）～（20）用數學的迭代的方法計算出來。把這些參數應用在實際的仿真環(huán)境中，得到了數據包的平均傳送時間，如圖3所示。

圖3 數據包的平均傳送時間（delay）Fig.3 Mean delay for packet transmission

取R=λ1/λ2，以其作為數據包訪問時間的度量基準，并把節(jié)點數目的比例作為度量系統(tǒng)非均勻度即非對稱度的度量，也就是說，系統(tǒng)的最大非均勻度即最大非對稱度是兩種節(jié)點的數目相當如N1=5，N2=5和N1=13，N2=12，而系統(tǒng)的最小非均勻度是兩種節(jié)點的數目相差最大如N1=23，N2=2。從圖中得到：隨著節(jié)點數的增加，數據包的平均delay增加；隨著非均勻度的增加，delay會增加；隨著隊列長度的增加，delay會增加；在R=1時，也就是兩種節(jié)點的數據包到達率相同，總的數據包數λ1N1+λ2N2在不同的節(jié)點組成情況下相等，所有的delay值相同，并且delay達到最大值。從圖中看出，仿真結果與分析結果是基本誤差在3.251%～8.562%范圍內，這個誤差是可以允許的。

分析了在R=1的特殊情況下，也就是系統(tǒng)節(jié)點為均勻分布時的delay性能，如圖4所示。隨著數據包到達率的增加，隊列長度小的情況如K=1，delay會緩慢增加；對于隊列長度大的情況，delay增加比較劇烈；隊列長度為6時，delay在λ=0.756時達到最大值。

圖4 兩種節(jié)點均勻分布時的delayFig.4 Delay for the same traffic of two types of nodes

4 結 論

文中采用了兩個半馬爾可夫鏈和一個宏觀馬爾可夫鏈模型描述了IEEE 802.15.4標準中一種新的CSMA/CA非均勻機制OSTS，并分析提高了網絡實時性能。在有限節(jié)點數和理想信道的情況下，分析了該機制在非均勻的數據包到達率和非飽和條件下各個數據包訪問信道的時間性能，并且通過NS-2仿真驗證了分析結果，發(fā)現(xiàn)文中的分析與仿真的結果是很吻合的。文中最大的特點是，數據包之間沒有優(yōu)先權的限制，所有包都有相同的機會訪問信道，無論是同一種節(jié)點還是不同種節(jié)點之間，這是與先前分析非均勻網絡[8]等中性能僅是各個節(jié)點性能的簡單代數相加最大的區(qū)別。分析了兩種節(jié)點在相同的數據包到達率條件下的實時性能，發(fā)現(xiàn)其訪問時間隨著到達率的增加急劇增加。

[1]Alazemi H M K，Margolis A，Choi J，et al.Stochastic modelling and analysis of 802.11 DCF with heterogeneous non-saturated nodes[J].Computer Communications，2007，30（18）：3652-3661.

[2]IEEE Std 802.15.4-2006， September，Part 15.4：Wireless Medium Access Control （MAC）and physical Layer（PHY）Specifications for Low-Rate Wireless Personal Area Networks（WPANs）[S].2003.

[3]Mi?ic J，Shafi S，Mi?ic V B.Access delay for nodes with finite buffers in ieee 802.15.4 beacon enabled pan with uplink transmission[J].Computer Communications，2005，28（10）：1152-1166.

[4]Ramachandran I，K Das A，Roy S.Analysis of the contention access period of IEEE 802.15.4 MAC[J].ACM Transaction on Sensor Networks，2007，3（1）：1-29.

[5]Park P，Di Marco P，F(xiàn)ischione C，et al.Delay Analysis of Slotted IEEE802.15.4withaFiniteRetryLimitandUnsatu-rated Traffic[C]//IEEE Global Communications Conference，2009：1-8.

[6]Lee T T.M/G/1/N Queue with Vacation Time and Exhaustive Service Discipline[J].Operations Research，1984，32（4）：774-784.

[7]Zheng J，Lee J M.A comprehensive performance study of IEEE 802.15.4[J].Sensor Network Operations，2006：218-237.

[8]Malone D，Duffy K，Leith D J.Modeling the 802.11 distributed coordination function in non-saturated heterogeneous conditions[J].IEEE/ACM Transaction Network，2007，15 （1）：159-172.