無線傳感器網絡公平性算法的分析

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

（云南民族大學云南省高校無線傳感器網絡重點實驗室，云南昆明650500）

無線傳感器網絡公平性算法的分析

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

（云南民族大學云南省高校無線傳感器網絡重點實驗室，云南昆明650500）

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

無線傳感器網絡；調度算法；公平性

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

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

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

1 最大最小公平性調度算法

在最大最小公平性調度算法［10］中，節點以CSMA機制競爭信道，通過計算得到的概率選擇堆棧發送，使發送數據次數少的堆棧，以較大概率被選擇，控制經過它的數據流，實現網絡的公平性.算法模型如圖1.

圖1中，每個堆棧里的數據流Flow（n）都有與之對應的權重管理器W（n）和活動計數器A（n），來實現堆棧管理和數據調度.

在堆棧管理中，當節點收到一個數據包時，如果與產生該數據包的信源節點相對應的堆棧存在的話，那么數據包將要傳入該堆棧，該堆棧相對應的活動計數器設為默認值.否則，要建立一個新的堆棧與之相對應，并且初始化.在數據調度中，節點以計算得到的概率p（k）從堆棧中選擇一個，作為下一個發送數據包的堆棧，w（k）為堆棧Q（k）（1≤k≤n）的權重值.

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

2 多數據包發送調度算法

在大規模無線傳感器網絡中，通常采用樹狀拓撲結構.對于距離網關一跳范圍內的節點，能夠直接把數據傳送給網關，但這些節點之間無法通過控制數據流的發送，來實現數據流之間的公平性.因此，本文提出了一種基于公平性的多數據包發送調度算法.

在多數據包發送的調度算法中，每一個源節點產生的數據包在傳輸過程中，經過中轉節點時都會產生一個與源節點相對應的堆棧來儲存數據包.這些節點內的數據，是按照信源識別的方式來存放的.對于距離網關一跳范圍外的節點，采取改進的最大最小公平性調度算法；對于距離網關一跳范圍內的節點，每次成功競爭信道后，若節點內各個堆棧都有數據，則節點一次發送多個數據包，每個堆棧都發送一個.否則，節點不發送數據包，進入等待狀態，不參與信道競爭，讓其他節點能夠獲取信道資源.

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

對于網關一跳范圍內的節點，它們能夠直接把數據傳送給網關.這些節點之間的數據流卻沒有有效的調度算法來控制，無法保證這些數據流之間的公平性.因此，在這些節點內，每個堆棧里的數據流Flow（n）都有與之對應的狀態管理器S（n）和活躍計數器AC（n）.

當節點收到一個數據包時，如果與該數據包的信源節點相對應的堆棧存在的話，那么數據包將要傳入該堆棧，該堆棧相對應的狀態管理器S（n）和活躍計數器設為默認值.如果與該包的信源節點相對應的堆棧不存在，那么節點要建立一個新的堆棧與之相對應，并且初始化.當堆棧未滿的時候，到達的數據包就傳進堆棧.否則丟棄該數據包.

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

3 仿真結果及分析

為了將本文算法與已有算法的網絡性能進行評估比較，建立算法0：最大最小公平性調度算法；算法1：多數據包發送調度算法.

在無線傳感器網絡中，大量的節點隨機分布在監測區域內，通常形成的都是是樹狀拓撲結構，從中選取一個樹枝狀的子網絡來建立模型，如圖3所示.

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

將節點的負載從100 kbit／s逐漸提高到2 000 kbit／s，考察節點在不同負載下的網絡公平性以及吞吐量.進行10次實驗，仿真結果取平均值，每次仿真時間為120 s.

所有節點在相同負載下，網絡的公平性用公平性指標來衡量，

表1 基本的仿真參數

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

從圖4～5中可以看出，負載很低時，所有的數據包都能到達網關，吞吐量達到上限，公平性為1.網絡的公平性以及吞吐量隨節點負載的增加而發生變化.

當節點負載為1 400 kbit／s時，各節點產生的數據流到達網關的吞吐量，見表2.

對于算法0，隨著節點的負載提高，節點的傳輸任務加重，尤其是節點WN3.雖然節點WN1、WN2、WN3傳輸到網關的吞吐量差不多，但是由于各個節點內的數據流的數量不同，所有數據流之間的吞吐量相差很大，導致網絡整體的公平性能下降；但是節點內的數據流之間，依然有較好的公平性.

表2 節點負載為1 400 kbit／s時網關數據流的吞吐量

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

4 結語

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

［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及其自適應競爭窗口改進算法的仿真研究［J］.計算機工程與設計，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.

（責任編輯 莊紅林）

Analysis of fairness-based algorithm in wireless sensor networks

LI Geng，FAN 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.

國家自然科學基金（61163061，60963026）；云南省應用基礎研究計劃項目（2011FZ174）.

李庚（1988-），男，碩士研究生.主要研究方向：無線傳感器網絡。

范菁（1976-），女，博士研究生，教授，碩士生導師.主要研究方向：無線傳感器網絡.