無線傳感器網(wǎng)絡(luò)公平性算法的分析

李 庚，范 菁，王萬升，向昌松

（云南民族大學(xué)云南省高校無線傳感器網(wǎng)絡(luò)重點實驗室，云南昆明650500）

無線傳感器網(wǎng)絡(luò)公平性算法的分析

李 庚，范 菁，王萬升，向昌松

（云南民族大學(xué)云南省高校無線傳感器網(wǎng)絡(luò)重點實驗室，云南昆明650500）

為了保證無線傳感器網(wǎng)絡(luò)具有較好的公平性，同時擁有較高的吞吐量，提出了一種基于公平性的多數(shù)據(jù)包發(fā)送調(diào)度算法.在該算法中，數(shù)據(jù)包是按照信源識別的方式來存放的.距離網(wǎng)關(guān)一跳范圍外的節(jié)點，采用改進(jìn)的最大最小公平性調(diào)度算法；距離網(wǎng)關(guān)一跳范圍以內(nèi)的節(jié)點，每次成功競爭信道后，若節(jié)點內(nèi)各個堆棧都有數(shù)據(jù)包，則節(jié)點一次發(fā)送多個數(shù)據(jù)包，每個堆棧都發(fā)送一個.否則，節(jié)點等待空閑一段時間.通過對比仿真實驗，網(wǎng)絡(luò)具有較好的公平性以及較高的吞吐量.

無線傳感器網(wǎng)絡(luò)；調(diào)度算法；公平性

由于傳感器節(jié)點隨機(jī)分布在網(wǎng)絡(luò)中，節(jié)點所在的位置不同，各個節(jié)點得到的網(wǎng)絡(luò)服務(wù)質(zhì)量（QOS）會有一定的差別；靠近網(wǎng)關(guān)的節(jié)點，容易獲取信道，有利于傳輸數(shù)據(jù)，占據(jù)較多的資源，相對的服務(wù)質(zhì)量較好；而遠(yuǎn)離網(wǎng)關(guān)的節(jié)點會受到靠近網(wǎng)關(guān)的節(jié)點相應(yīng)的壓迫，難以占據(jù)信道，不利于傳輸數(shù)據(jù)，相對的服務(wù)質(zhì)量比較差；因此，常常導(dǎo)致網(wǎng)絡(luò)資源分配的不公平，網(wǎng)絡(luò)整體的服務(wù)質(zhì)量不理想.在多跳的無線傳感器網(wǎng)絡(luò)中，如何讓各節(jié)點公平合理地共享無線信道資源，成為研究熱點之一［1-4］.

國內(nèi)外已有許多調(diào)度算法可以實現(xiàn)多跳網(wǎng)絡(luò)內(nèi)數(shù)據(jù)流的公平性.Izumikawa等［5］提出了一種基于數(shù)據(jù)流的調(diào)度算法，無線傳感器節(jié)點中的數(shù)據(jù)包被分為源節(jié)點產(chǎn)生的數(shù)據(jù)包和來自其他節(jié)點的轉(zhuǎn)發(fā)的數(shù)據(jù)包，數(shù)據(jù)包以輪詢的方式進(jìn)行發(fā)送，只有當(dāng)各節(jié)點負(fù)載相同時，網(wǎng)絡(luò)才具有較好的公平性；Naouel等［6］專注于空間／時分多址（STDMA），提出了在WMNs中的一個MAC層的數(shù)據(jù)包調(diào)度算法，將傳輸權(quán)力分配給鏈路，使空間使用最大化；Giang等［7］提出了在鏈路層上循環(huán)排隊的概率控制（PCRQ），該方法中數(shù)據(jù)包按概率進(jìn)入堆棧，循環(huán)選擇堆棧來傳輸，數(shù)據(jù)包按概率離開堆棧；Nand等［8］針對Impre-cise Extended Inter-Frame Space（EIFS）問題中EIFS值和期望值不匹配產(chǎn)生的不公平和吞吐量降低，提出了一個加強(qiáng)的載波感應(yīng)（enhanced car-rier sensing，ECS），將錯誤類型區(qū)分開來，相應(yīng)地延遲傳輸，解決了這個問題；Cheng等［9］提出了自己的擁塞公平性策略（CCF），針對多對一的樹形拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)，在發(fā)生擁塞時，采用擁塞控制能夠確保節(jié)點公平的傳輸數(shù)據(jù)，同時提出了基于子節(jié)點數(shù)目的傳輸調(diào)度算法，實現(xiàn)數(shù)據(jù)流之間的公平傳輸；Wakuda等［10］提出了在多跳無線傳感器網(wǎng)絡(luò)中，基于最大最小公平性準(zhǔn)則的一種數(shù)據(jù)包調(diào)度算法，當(dāng)節(jié)點要發(fā)送數(shù)據(jù)時，節(jié)點通過計算得到的概率，選擇一定時間內(nèi)節(jié)點內(nèi)發(fā)送數(shù)據(jù)最少的堆棧來發(fā)送數(shù)據(jù)包；如果節(jié)點所選的堆棧沒有數(shù)據(jù)，節(jié)點延遲發(fā)送，不參與信道競爭，讓其他節(jié)點能夠獲取信道資源.

本文在分析已有的最大最小公平性調(diào)度算法的基礎(chǔ)上，提出了一種基于公平性的多數(shù)據(jù)包發(fā)送調(diào)度算法.算法對于距離網(wǎng)關(guān)一跳范圍外的節(jié)點，先以計算得到的概率進(jìn)行堆棧選擇，再檢測對應(yīng)下一跳節(jié)點堆棧的緩沖區(qū)是否已滿，若未滿，節(jié)點才競爭信道，使得節(jié)點能夠有效發(fā)送數(shù)據(jù).否則，節(jié)點進(jìn)入等待狀態(tài)，空閑一段時間.由于數(shù)據(jù)直接傳輸給網(wǎng)關(guān)的一跳節(jié)點之間的公平性沒有得到控制，因此距離網(wǎng)關(guān)一跳范圍內(nèi)的節(jié)點，每次成功競爭信道后，若節(jié)點內(nèi)各個堆棧都有數(shù)據(jù)，則節(jié)點一次發(fā)送多個數(shù)據(jù)包，每個堆棧都發(fā)送一個.否則，節(jié)點不發(fā)送數(shù)據(jù)包，進(jìn)入等待狀態(tài)，空閑一段時間，不參與信道競爭，讓其他節(jié)點能夠獲取信道資源.仿真實驗表明，采用本算法網(wǎng)絡(luò)能夠獲得較好的公平性及較高的吞吐量.

1 最大最小公平性調(diào)度算法

在最大最小公平性調(diào)度算法［10］中，節(jié)點以CSMA機(jī)制競爭信道，通過計算得到的概率選擇堆棧發(fā)送，使發(fā)送數(shù)據(jù)次數(shù)少的堆棧，以較大概率被選擇，控制經(jīng)過它的數(shù)據(jù)流，實現(xiàn)網(wǎng)絡(luò)的公平性.算法模型如圖1.

圖1中，每個堆棧里的數(shù)據(jù)流Flow（n）都有與之對應(yīng)的權(quán)重管理器W（n）和活動計數(shù)器A（n），來實現(xiàn)堆棧管理和數(shù)據(jù)調(diào)度.

在堆棧管理中，當(dāng)節(jié)點收到一個數(shù)據(jù)包時，如果與產(chǎn)生該數(shù)據(jù)包的信源節(jié)點相對應(yīng)的堆棧存在的話，那么數(shù)據(jù)包將要傳入該堆棧，該堆棧相對應(yīng)的活動計數(shù)器設(shè)為默認(rèn)值.否則，要建立一個新的堆棧與之相對應(yīng)，并且初始化.在數(shù)據(jù)調(diào)度中，節(jié)點以計算得到的概率p（k）從堆棧中選擇一個，作為下一個發(fā)送數(shù)據(jù)包的堆棧，w（k）為堆棧Q（k）（1≤k≤n）的權(quán)重值.

當(dāng)堆棧Q（k）被選定且堆棧內(nèi)有數(shù)據(jù)包時，wk置為w，一個數(shù)據(jù)包從堆棧內(nèi)離開.否則，堆棧對應(yīng)的活動計數(shù)器自減1，并且節(jié)點延遲發(fā)送，等待一個固定時間twait，重復(fù)上面的步驟.如果所有的堆棧都沒有數(shù)據(jù)，所有對應(yīng)的權(quán)重管理器的值加1，但是權(quán)重值不能超過上限值wmax.當(dāng)堆棧Q（k）的活動計數(shù)值減為0，移除堆棧Q（k）.當(dāng)節(jié)點有一段時間沒有收到某個節(jié)點產(chǎn)生的數(shù)據(jù)包時，對應(yīng)那個節(jié)點的堆棧的權(quán)重管理器的值加1.

2 多數(shù)據(jù)包發(fā)送調(diào)度算法

在大規(guī)模無線傳感器網(wǎng)絡(luò)中，通常采用樹狀拓?fù)浣Y(jié)構(gòu).對于距離網(wǎng)關(guān)一跳范圍內(nèi)的節(jié)點，能夠直接把數(shù)據(jù)傳送給網(wǎng)關(guān)，但這些節(jié)點之間無法通過控制數(shù)據(jù)流的發(fā)送，來實現(xiàn)數(shù)據(jù)流之間的公平性.因此，本文提出了一種基于公平性的多數(shù)據(jù)包發(fā)送調(diào)度算法.

在多數(shù)據(jù)包發(fā)送的調(diào)度算法中，每一個源節(jié)點產(chǎn)生的數(shù)據(jù)包在傳輸過程中，經(jīng)過中轉(zhuǎn)節(jié)點時都會產(chǎn)生一個與源節(jié)點相對應(yīng)的堆棧來儲存數(shù)據(jù)包.這些節(jié)點內(nèi)的數(shù)據(jù)，是按照信源識別的方式來存放的.對于距離網(wǎng)關(guān)一跳范圍外的節(jié)點，采取改進(jìn)的最大最小公平性調(diào)度算法；對于距離網(wǎng)關(guān)一跳范圍內(nèi)的節(jié)點，每次成功競爭信道后，若節(jié)點內(nèi)各個堆棧都有數(shù)據(jù)，則節(jié)點一次發(fā)送多個數(shù)據(jù)包，每個堆棧都發(fā)送一個.否則，節(jié)點不發(fā)送數(shù)據(jù)包，進(jìn)入等待狀態(tài)，不參與信道競爭，讓其他節(jié)點能夠獲取信道資源.

如圖2所示，對于距離網(wǎng)關(guān)一跳范圍外的節(jié)點，每個堆棧里的數(shù)據(jù)流Flow（n）都有與之對應(yīng)的權(quán)重管理器W（n）和活動計數(shù)器A（n），來實現(xiàn)堆棧管理和數(shù)據(jù)調(diào)度.節(jié)點偵聽DIFS后，先檢測節(jié)點內(nèi)有無數(shù)據(jù)，節(jié)點有數(shù)據(jù)再以概率進(jìn)行堆棧選擇，選擇的堆棧內(nèi)若有數(shù)據(jù)，再檢測下一跳節(jié)點對應(yīng)緩沖區(qū)是否已滿，若未滿，節(jié)點才參與競爭、傳輸數(shù)據(jù)；否則，節(jié)點延遲發(fā)送，等待一段時間，不參與信道競爭，讓其他節(jié)點能夠獲取信道資源.節(jié)點以概率的方式選擇一定時間內(nèi)節(jié)點中發(fā)送數(shù)據(jù)最少的堆棧，來發(fā)送數(shù)據(jù)包，不會出現(xiàn)某個數(shù)據(jù)流獨占信道，該公平性調(diào)度算法能夠有效控制經(jīng)過它的數(shù)據(jù)流，均衡數(shù)據(jù)流的傳輸，實現(xiàn)節(jié)點內(nèi)數(shù)據(jù)流之間的公平性，同時提高吞吐量.

對于網(wǎng)關(guān)一跳范圍內(nèi)的節(jié)點，它們能夠直接把數(shù)據(jù)傳送給網(wǎng)關(guān).這些節(jié)點之間的數(shù)據(jù)流卻沒有有效的調(diào)度算法來控制，無法保證這些數(shù)據(jù)流之間的公平性.因此，在這些節(jié)點內(nèi)，每個堆棧里的數(shù)據(jù)流Flow（n）都有與之對應(yīng)的狀態(tài)管理器S（n）和活躍計數(shù)器AC（n）.

當(dāng)節(jié)點收到一個數(shù)據(jù)包時，如果與該數(shù)據(jù)包的信源節(jié)點相對應(yīng)的堆棧存在的話，那么數(shù)據(jù)包將要傳入該堆棧，該堆棧相對應(yīng)的狀態(tài)管理器S（n）和活躍計數(shù)器設(shè)為默認(rèn)值.如果與該包的信源節(jié)點相對應(yīng)的堆棧不存在，那么節(jié)點要建立一個新的堆棧與之相對應(yīng)，并且初始化.當(dāng)堆棧未滿的時候，到達(dá)的數(shù)據(jù)包就傳進(jìn)堆棧.否則丟棄該數(shù)據(jù)包.

節(jié)點的數(shù)據(jù)調(diào)度通過狀態(tài)管理器S和活躍計數(shù)器AC來實現(xiàn).節(jié)點每次成功競爭信道后，檢測節(jié)點內(nèi)各個堆棧，如果都有數(shù)據(jù)，則節(jié)點一次發(fā)送多個數(shù)據(jù)，每個堆棧都發(fā)送一個.否則，節(jié)點不發(fā)送數(shù)據(jù)，進(jìn)入等待狀態(tài)，不參與信道競爭，讓其他節(jié)點能夠獲取信道資源.假如調(diào)度器管理n個堆棧，堆棧M（k）（1≤k≤n）的狀態(tài)管理器的值為s（k），那么s（k）＝1表示堆棧內(nèi)有數(shù)據(jù)，s（k）＝0表示堆棧內(nèi)沒有數(shù)據(jù)；如圖2，節(jié)點成功競爭信道后，檢測各個堆棧的狀態(tài)值s（k），如果都為1，則節(jié)點一次發(fā)送多個數(shù)據(jù)包，各個堆棧發(fā)送一個，數(shù)據(jù)包從堆棧內(nèi)離開.數(shù)據(jù)包離開后的堆棧內(nèi)，若沒有數(shù)據(jù)包，那么對應(yīng)的狀態(tài)值s（k）置為0，否則，狀態(tài)值s（k）為0的堆棧對應(yīng)的活躍計數(shù)器的值自減1，節(jié)點延遲發(fā)送，等待一個固定時間Twait，重復(fù)上面的步驟.當(dāng)堆棧M（k）的活躍計數(shù)值減為0，移除堆棧M（k）.

3 仿真結(jié)果及分析

為了將本文算法與已有算法的網(wǎng)絡(luò)性能進(jìn)行評估比較，建立算法0：最大最小公平性調(diào)度算法；算法1：多數(shù)據(jù)包發(fā)送調(diào)度算法.

在無線傳感器網(wǎng)絡(luò)中，大量的節(jié)點隨機(jī)分布在監(jiān)測區(qū)域內(nèi)，通常形成的都是是樹狀拓?fù)浣Y(jié)構(gòu)，從中選取一個樹枝狀的子網(wǎng)絡(luò)來建立模型，如圖3所示.

使用Matlab對上述2種算法進(jìn)行仿真，基本的仿真實驗參數(shù)見表1.MAC層采用IEEE 802.11b DCF的RTS／CTS機(jī)制，節(jié)點感知距離220m，傳輸距離120m，節(jié)點間距離100m.其中，活躍計數(shù)器默認(rèn)值設(shè)為6，活動計數(shù)器默認(rèn)值為6，權(quán)重計數(shù)器上限值為22.

將節(jié)點的負(fù)載從100 kbit／s逐漸提高到2 000 kbit／s，考察節(jié)點在不同負(fù)載下的網(wǎng)絡(luò)公平性以及吞吐量.進(jìn)行10次實驗，仿真結(jié)果取平均值，每次仿真時間為120 s.

所有節(jié)點在相同負(fù)載下，網(wǎng)絡(luò)的公平性用公平性指標(biāo)來衡量，

表1 基本的仿真參數(shù)

Xi是在無線鏈路中，沒有數(shù)據(jù)包丟失的數(shù)據(jù)流端到端的吞吐量，是所有數(shù)據(jù)流平均端到端的吞吐量.

從圖4～5中可以看出，負(fù)載很低時，所有的數(shù)據(jù)包都能到達(dá)網(wǎng)關(guān)，吞吐量達(dá)到上限，公平性為1.網(wǎng)絡(luò)的公平性以及吞吐量隨節(jié)點負(fù)載的增加而發(fā)生變化.

當(dāng)節(jié)點負(fù)載為1 400 kbit／s時，各節(jié)點產(chǎn)生的數(shù)據(jù)流到達(dá)網(wǎng)關(guān)的吞吐量，見表2.

對于算法0，隨著節(jié)點的負(fù)載提高，節(jié)點的傳輸任務(wù)加重，尤其是節(jié)點WN3.雖然節(jié)點WN1、WN2、WN3傳輸?shù)骄W(wǎng)關(guān)的吞吐量差不多，但是由于各個節(jié)點內(nèi)的數(shù)據(jù)流的數(shù)量不同，所有數(shù)據(jù)流之間的吞吐量相差很大，導(dǎo)致網(wǎng)絡(luò)整體的公平性能下降；但是節(jié)點內(nèi)的數(shù)據(jù)流之間，依然有較好的公平性.

表2 節(jié)點負(fù)載為1 400 kbit／s時網(wǎng)關(guān)數(shù)據(jù)流的吞吐量

對于算法1，隨著節(jié)點的負(fù)載提高，節(jié)點的傳輸任務(wù)加重，雖然節(jié)點內(nèi)數(shù)據(jù)流之間的公平性與算法0相比有所下降，但是很小，不明顯，網(wǎng)絡(luò)整體的公平性能一直很好.而且節(jié)點WN2、WN3一次可以發(fā)送多個數(shù)據(jù)包，可以有效降低每個數(shù)據(jù)包的平均訪問時間，使得網(wǎng)絡(luò)的吞吐量得到提高.

4 結(jié)語

本文針對無線傳感器網(wǎng)絡(luò)的公平性問題進(jìn)行分析，在此基礎(chǔ)上對最大最小調(diào)度算法進(jìn)行改進(jìn)，并提出了一種基于公平性的多數(shù)據(jù)包發(fā)送調(diào)度算法.針對簡單的網(wǎng)絡(luò)模型，使用Matlab對算法進(jìn)行仿真.仿真結(jié)果表明，提出的算法具有更好的網(wǎng)絡(luò)公平性，同時網(wǎng)絡(luò)吞吐量較高.在網(wǎng)絡(luò)范圍內(nèi)，任意節(jié)點或者同等條件下的數(shù)據(jù)流能夠被公平合理的對待，不會有明顯的差異.

［1］YIGITEL M A，INCEL O D，ERSOY C.QoS-aware MAC protocols for wireless sensor networks：A survey［J］.Computer Networks，2011，55：1982-2004.

［2］CARVALHO M M，GARCIA-LUNA-ACEVES J J.Delay analysis of IEEE 802.11 in single-hop networks［C］／／Proceedings of the 11th IEEE International Conference on Network Protocols（ICNP′03）.IEEE Press，2003：146-155.

［3］范菁，謝建斌，王萬升，等.DCF及其自適應(yīng)競爭窗口改進(jìn)算法的仿真研究［J］.計算機(jī)工程與設(shè)計，2008，29（13）：3298-3302.

［4］TAY Y C，CHUA K C.A capacity analysis for the IEEE 802.11 MAC protocol［J］.ACM／Baltzer Wireless Networks，2001（7）：159-171.

［5］IZUMIKAWA H，ISHIKAWA H，SUGIYAMA K.Scheduling algorithm for fairness improvement among subscribers in multi-hop wireless networks［J］.Electronics and Communications in Japan（Part I：Communications），2007，90（4）：11-22.

［6］NAOUEL B S，JEAN-PIERRE H，A fair scheduling for wireless mesh networks［C］／／A Fair Scheduling for Wireless Mesh Networks.IEEE Press，2005：81-88.

［7］GIANG P T，NAKAGAWA K.Improvement of fairness by PCRQ scheduling in multi-Hop wireless ad hoc networks［C］／／Proceedings of Asia-Pacific Symposium on Queueing Theory and Network Application.IEEE Press，2007：339-348.

［8］LIZ S，GUPTA N A K.ECS：An enhanced carrier sensing mechanism for wireless ad Hoc networks［J］.Computer Communications，2005，28：1970-1984.

［9］CHENG Tien-ee，BAJCSY R.Congestion control and fairness for many-to-one routing in sensor networks［C］／／ACM SenSys.IEEE Press，2004：148-161.

［10］WAKUDA K，KASAHARA S，TAKAHASHI Y.A packet scheduling algorithm for max-min fairness in multi-Hop wireless LANS［J］.Computer Communications，2009，32：1437-1444.

（責(zé)任編輯 莊紅林）

Analysis of fairness-based algorithm in wireless sensor networks

LI Geng，F(xiàn)AN Jing，WANG Wan-sheng，XIANG Chang-song
（Key Laboratory of Wireless Sensor Networks in Universities of Yunnan Province，Yunnan Minzu University，Kunming 650500，China）

In order to guarantee good fairness and high throughput in wireless sensor networks，this research gives an analysis of the existing fairness scheduling algorithm and proposes a multiple packet-scheduling algorithm based on fairness.The node is within one hop to Gateway，after every successful getting the channel in the competition with other nodes，each stack in the node has a packet，and the node will send multiple packets.Otherwise，the node will be waiting for a period of time.Through a simulationexperiment，the network has good fairness and high throughput.

wireless sensor network；scheduling algorithm；fairness

TP393

A

1672-8513（2014）06-0400-04

2014-04-04.

國家自然科學(xué)基金（61163061，60963026）；云南省應(yīng)用基礎(chǔ)研究計劃項目（2011FZ174）.

李庚（1988-），男，碩士研究生.主要研究方向：無線傳感器網(wǎng)絡(luò)。

范菁（1976-），女，博士研究生，教授，碩士生導(dǎo)師.主要研究方向：無線傳感器網(wǎng)絡(luò).