基于隊(duì)列理論CSMA／CA機(jī)制的無(wú)線傳感器異構(gòu)機(jī)制

摘要：自從IEEE 802．15．4標(biāo)準(zhǔn)發(fā)布以來(lái)，基于低功耗、低速率傳輸?shù)?strong>無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用幾乎涉及到現(xiàn)實(shí)生活的方方面面；但是關(guān)于這個(gè)標(biāo)準(zhǔn)的CSMA／CA機(jī)制大部分都是基于均勻、飽和的傳感器網(wǎng)絡(luò)應(yīng)用。文中針對(duì)非飽和、帶緩存的無(wú)線傳感器異構(gòu)網(wǎng)絡(luò)，提出了一種新的異構(gòu)的CSMA／CA機(jī)制OSTS。該機(jī)制采用2個(gè)馬爾可夫鏈來(lái)分別表示異構(gòu)節(jié)點(diǎn)訪問(wèn)信道的過(guò)程、一個(gè)宏觀馬爾可夫鏈來(lái)表達(dá)信道狀態(tài)轉(zhuǎn)移，且結(jié)合M／G／1／K隊(duì)列理論分析數(shù)據(jù)包傳送的實(shí)時(shí)性能，并相應(yīng)地改進(jìn)系統(tǒng)的實(shí)時(shí)性。文中最大的特點(diǎn)是兩組非均勻節(jié)點(diǎn)被賦予了公平的機(jī)會(huì)訪問(wèn)信道，而不存在優(yōu)先權(quán)的問(wèn)題。此外，詳細(xì)分析了這種機(jī)制的數(shù)據(jù)包傳送時(shí)間，包括數(shù)據(jù)包到達(dá)率、包大小、節(jié)點(diǎn)數(shù)量、緩存大小等參數(shù)
對(duì)系統(tǒng)實(shí)時(shí)性的影響；這些分析結(jié)果與我們采用NS-2工具仿真的結(jié)果十分吻合。
關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；實(shí)時(shí)性分析；馬爾可夫鏈；CSMMA／CA機(jī)制；NS-2仿真；M／G／1／K隊(duì)列理論

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

1 建立模型
    隨著IEEE802．15．4標(biāo)準(zhǔn)的發(fā)布，無(wú)線傳感器的應(yīng)用取得突飛猛進(jìn)的發(fā)展，其應(yīng)用早已經(jīng)由軍事國(guó)防領(lǐng)域擴(kuò)展到環(huán)境監(jiān)測(cè)、交通管理、醫(yī)療健康、工商服務(wù)、反恐抗災(zāi)等諸多領(lǐng)域，使人們?cè)谌魏螘r(shí)間、任何地點(diǎn)和任何環(huán)境條件下都能夠獲取大量翔實(shí)可靠的信息，最終成為一種“無(wú)處不在”的傳感技術(shù)。無(wú)線傳感器網(wǎng)絡(luò)的性能優(yōu)勢(shì)使得其應(yīng)用幾乎涉及到我們生活的方方面面；但是無(wú)線傳感器網(wǎng)絡(luò)依然在很多方面存在缺陷，諸如使用電池供電引起節(jié)能的需求，公平性、實(shí)時(shí)性、吞吐量的有待提高等等。
    針對(duì)于實(shí)際應(yīng)用，提出了異構(gòu)網(wǎng)絡(luò)的實(shí)時(shí)性要求，詳細(xì)、綜合分析兩種不同性質(zhì)的數(shù)據(jù)包以公平的機(jī)會(huì)訪問(wèn)信道的時(shí)間性能，找到合適參數(shù)以減少數(shù)據(jù)包訪問(wèn)時(shí)間、提高實(shí)時(shí)性要求。
    在提出OSTS機(jī)制，建立分析模型之前，先作出如下的假設(shè)：假設(shè)信標(biāo)指數(shù)為4，所以每個(gè)包都能在同一個(gè)超幀傳送完；數(shù)據(jù)包的接受確認(rèn)可以無(wú)需通過(guò)ACK來(lái)執(zhí)行；為了避免成功獲取信道的節(jié)點(diǎn)永久占用信道，參與競(jìng)爭(zhēng)的所有節(jié)點(diǎn)而不僅僅是傳送節(jié)點(diǎn)將其backoff計(jì)數(shù)器降為最小值；傳完一個(gè)數(shù)據(jù)包后，信道為空的概率μ0與任何時(shí)刻信道為空的概率P0不相等；系統(tǒng)中存在2種節(jié)點(diǎn)，節(jié)點(diǎn)個(gè)數(shù)分別為N1和N2，到達(dá)節(jié)點(diǎn)的流量滿足泊松(Poisson)過(guò)程且數(shù)據(jù)包到達(dá)率分別為λ1和λ2；參與競(jìng)爭(zhēng)的數(shù)據(jù)包都是每個(gè)隊(duì)列的首數(shù)據(jù)包，那么可以簡(jiǎn)化競(jìng)爭(zhēng)機(jī)制，即只考慮參與競(jìng)爭(zhēng)的數(shù)據(jù)包。這樣，采用3個(gè)馬爾可夫鏈模型來(lái)描述，其中兩個(gè)半馬爾可夫鏈分別表示兩種數(shù)據(jù)包訪問(wèn)信道的過(guò)程，如圖1所示，這個(gè)鏈?zhǔn)堑母倪M(jìn)；一個(gè)宏觀馬爾可夫鏈表示信道的狀態(tài)，如圖2所示。

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

    根據(jù)圖1馬爾可夫鏈的鏈?zhǔn)揭?guī)則，可以得到關(guān)于各個(gè)狀態(tài)間的關(guān)系式(1)～(4)。其中式(1)表示節(jié)點(diǎn)獲得了新包，隨機(jī)選擇backoff計(jì)數(shù)器后進(jìn)行退避過(guò)程的轉(zhuǎn)移概率；式(2)表示節(jié)點(diǎn)不論信道的狀態(tài)，都以概率1遞減其backoff計(jì)數(shù)器的轉(zhuǎn)移慨率；式(3)表示節(jié)點(diǎn)在任意一個(gè)CCA發(fā)現(xiàn)信道忙后進(jìn)入下一個(gè)backoff階段的轉(zhuǎn)移概率；式(4)表示達(dá)到最大backoff階段后節(jié)點(diǎn)選擇下一次重傳的轉(zhuǎn)移概率。
   
    其次，從信道的狀態(tài)來(lái)看，兩種數(shù)據(jù)包的訪問(wèn)信道的狀態(tài)轉(zhuǎn)移情況可以直觀地從圖2中宏觀馬爾可夫鏈看出，并且得到式(5)～(11)。其中式(5)～(7)分別表示任何一種節(jié)點(diǎn)在訪問(wèn)失敗、最后一次重傳的沖突傳送、每次重傳的成功傳送，若緩存中沒(méi)有其他數(shù)據(jù)包，那么直接轉(zhuǎn)移到idle狀態(tài)的轉(zhuǎn)移概率：式(8)表示任何一個(gè)節(jié)點(diǎn)都沒(méi)有新數(shù)據(jù)包，處于idle狀態(tài)的概率；式(9)～(11)分別表示任何一種節(jié)點(diǎn)在訪問(wèn)失敗、最后一次重傳的沖突傳送、每次重傳的成功傳送，若緩存中還有其他數(shù)據(jù)包，那么重新轉(zhuǎn)移到競(jìng)爭(zhēng)傳送狀態(tài)的轉(zhuǎn)移概率。
   
    定義bi,k,j=P{s(t)，c(t)，r(t)=i,k,j}為馬爾可夫鏈的穩(wěn)態(tài)轉(zhuǎn)移概率，那么根據(jù)馬爾可夫鏈和其狀態(tài)轉(zhuǎn)移的規(guī)則，可以得到式(12)。通過(guò)歸一化處理，得到式(13)。式13中每個(gè)量分別為表達(dá)式(14)和(15)。式(14)表示一種類型的包在訪問(wèn)信道時(shí)backoff過(guò)程穩(wěn)態(tài)概率、CCA1概率、CCA2概率、成功傳送概率、沖突傳送概率。式(15)表示空閑概率，其中P0表示任何時(shí)刻信道為空的概率，μ0表示傳完一個(gè)數(shù)據(jù)包后，信道為空的概率。
   
              
    從上面的式(13)～(15)可以看出，每個(gè)量都與變量。和。有關(guān)，而這兩個(gè)變量實(shí)際可以從宏觀馬爾可夫鏈、式(1)看出其關(guān)系，結(jié)合隊(duì)列理論，從而得到關(guān)系式(16)～(17)，式中QL0是信道處于空閑狀態(tài)的長(zhǎng)度。
   
    其中：An=αn+(1-αn)βn
    從上面的分析中，看到這些概率實(shí)際上都是與信道的操作點(diǎn)α，β，τn有關(guān)，且這些操作點(diǎn)參數(shù)決定了數(shù)據(jù)包的訪問(wèn)時(shí)間度量，其中α表示節(jié)點(diǎn)在CCA1后發(fā)現(xiàn)信道忙的概率；β表示節(jié)點(diǎn)在CCA2都發(fā)現(xiàn)信道忙的概率；τ表示節(jié)點(diǎn)偵聽(tīng)信道的概率。第二部分會(huì)詳細(xì)分析這個(gè)操作點(diǎn)以獲取訪問(wèn)時(shí)間性能分析。

2 延時(shí)性能分析
    在低速率傳輸?shù)腤SN中，除了能耗是個(gè)重要的參數(shù)，實(shí)時(shí)性也是一個(gè)非常重要的參數(shù)，特別是對(duì)于這樣的實(shí)時(shí)性要求比較高的應(yīng)用環(huán)境。訪問(wèn)時(shí)間度量(delay)是指從數(shù)據(jù)包到達(dá)MAC隊(duì)列的時(shí)刻到數(shù)據(jù)包成功傳送的時(shí)刻之間的時(shí)間。假設(shè)理想信道，那么數(shù)據(jù)包的失敗率只是因?yàn)閿?shù)據(jù)包之間的沖突。因每次競(jìng)爭(zhēng)都是節(jié)點(diǎn)隊(duì)列中的首包，那么簡(jiǎn)單的從數(shù)據(jù)包訪問(wèn)情況來(lái)獲得信道的操作點(diǎn)，其中τn就是所有backoff計(jì)數(shù)器降為0的概率。
   
    從上面的式(18)～(20)可以看到操作點(diǎn)參數(shù)可以通過(guò)數(shù)學(xué)迭代的方法唯一求出，從而可以得到數(shù)據(jù)包的傳輸時(shí)間度量。引入M／G／1／K隊(duì)列理論分析節(jié)點(diǎn)中的數(shù)據(jù)包的傳送情況。隊(duì)列有K個(gè)數(shù)據(jù)包，每個(gè)數(shù)據(jù)包的長(zhǎng)度為L(zhǎng)，每個(gè)數(shù)據(jù)包的傳送時(shí)間的概率母函數(shù)為Ttr(Z)，那么P0和μ0為：

   

3 仿真驗(yàn)證
    通過(guò)NS-2仿真軟件來(lái)驗(yàn)證數(shù)據(jù)包的實(shí)時(shí)性能。參考文獻(xiàn)所述的仿真搭建我們的仿真平臺(tái)。所有節(jié)點(diǎn)都分布在以sink節(jié)點(diǎn)為圓心、半徑為5 m的圓內(nèi)；每個(gè)節(jié)點(diǎn)都在彼此的傳輸范圍內(nèi)，節(jié)點(diǎn)的傳輸距離為11 m；每個(gè)節(jié)點(diǎn)都能偵聽(tīng)到其他節(jié)點(diǎn)的傳輸，也就是說(shuō)不存在隱藏終端。仿真參數(shù)如表1所示。

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

    取R=λ1／λ2，以其作為數(shù)據(jù)包訪問(wèn)時(shí)間的度量基準(zhǔn)，并把節(jié)點(diǎn)數(shù)目的比例作為度量系統(tǒng)非均勻度即非對(duì)稱度的度量，也就是說(shuō)，系統(tǒng)的最大非均勻度即最大非對(duì)稱度是兩種節(jié)點(diǎn)的數(shù)目相當(dāng)如N1=5，N2=5和N1=13，N2=12，而系統(tǒng)的最小非均勻度是兩種節(jié)點(diǎn)的數(shù)目相差最大如N1 =23，N2=2。從圖中得到：隨著節(jié)點(diǎn)數(shù)的增加，數(shù)據(jù)包的平均delay增加；隨著非均勻度的增加，delay會(huì)增加；隨著隊(duì)列長(zhǎng)度的增加，delay會(huì)增加；在R=1時(shí)，也就是兩種節(jié)點(diǎn)的數(shù)據(jù)包到達(dá)率相同，總的數(shù)據(jù)包數(shù)λ1N1+λ2N2在不同的節(jié)點(diǎn)組成情況下相等，所有的delay值相同，并且delay達(dá)到最大值。從圖中看出，仿真結(jié)果與分析結(jié)果是基本誤差在3．251％～8．562％范圍內(nèi)，這個(gè)誤差是可以允許的。

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

4 結(jié)論
    文中采用了兩個(gè)半馬爾可夫鏈和一個(gè)宏觀馬爾可夫鏈模型描述了IEEE 802．15．4標(biāo)準(zhǔn)中一種新的CSMA／CA非均勻機(jī)制OSTS，并分析提高了網(wǎng)絡(luò)實(shí)時(shí)性能。在有限節(jié)點(diǎn)數(shù)和理想信道的情況下，分析了該機(jī)制在非均勻的數(shù)據(jù)包到達(dá)率和非飽和條件下各個(gè)數(shù)據(jù)包訪問(wèn)信道的時(shí)間性能，并且通過(guò)NS-2仿真驗(yàn)證了分析結(jié)果，發(fā)現(xiàn)文中的分析與仿真的結(jié)果是很吻合的。文中最大的特點(diǎn)是，數(shù)據(jù)包之間沒(méi)有優(yōu)先權(quán)的限制，所有包都有相同的機(jī)會(huì)訪問(wèn)信道，無(wú)論是同一種節(jié)點(diǎn)還是不同種節(jié)點(diǎn)之間，這是與先前分析非均勻網(wǎng)絡(luò)等中性能僅是各個(gè)節(jié)點(diǎn)性能的簡(jiǎn)單代數(shù)相加最大的區(qū)別。分析了兩種節(jié)點(diǎn)在相同的數(shù)據(jù)包到達(dá)率條件下的實(shí)時(shí)性能，發(fā)現(xiàn)其訪問(wèn)時(shí)間隨著到達(dá)率的增加急劇增加。