一種能量有效的無線傳感器網(wǎng)絡輪詢接入控制協(xié)議

何敏，趙東風，保利勇，左朝樹

(1.云南大學信息學院，云南昆明 650091;2.西南通信研究所保密通信重點實驗室，四川成都 610041)

無線傳感器網(wǎng)絡(wireless sensor networks，WSN)綜合了傳感器技術、嵌入式計算技術、分布式信息處理技術和無線通信技術，在軍事、環(huán)境監(jiān)測、醫(yī)療、建筑物監(jiān)測、智能家居和安全報警、反恐和公共安全、商業(yè)等領域都有重要的科研價值和廣闊的應用前景.由于傳感器節(jié)點通常依靠電池供電，能量有限，不能直接應用在現(xiàn)有的無線通信協(xié)議中，通常的解決辦法是采用休眠機制，減少節(jié)點在空閑時期的能耗.隨機競爭接入能為突發(fā)性數(shù)據(jù)提供靈活的服務，且控制相對簡單，目前部分應用采用基于802.11的競爭類協(xié)議，但如何降低碰撞造成的能量消耗是這類協(xié)議的一個難題.

輪詢方式既避免了碰撞，又能提供具有QoS保障的服務，因此被廣泛應用到MAC協(xié)議的設計中.研究人員在純 PCF(point coordination function)［1］系統(tǒng)的基礎上，提出了一系列的改進算法［2-8］，如兩級優(yōu)先級輪詢［2］、自適應調度［3］、自適應差額調度［4］等改進的PCF系統(tǒng).這些系統(tǒng)通過對服務策略、調度機制的深入研究，改進了純PCF系統(tǒng)的性能.文獻［5］將沒有處在激活狀態(tài)的站點從輪詢列表中刪除，網(wǎng)絡性能得到了顯著的提高.文獻［6］通過3級門限服務方式，較好地解決了實時業(yè)務在重負載下時延Qos不能得到滿足的問題;但是對于低速傳感器網(wǎng)絡的節(jié)點來說，可能導致部分節(jié)點較長時間占用信道，欠缺公平性.文獻［7］通過為不同業(yè)務類別分配服務配額的方式，采用加權輪詢調度策略，以業(yè)務的平均分組到達率為依據(jù)，降低了排隊的復雜度.文獻［8］基于Zigbee技術，需要服務的節(jié)點采用CSMA/CA機制接入，中心采用輪詢方式為各節(jié)點服務，沒有服務需求的節(jié)點則休眠以節(jié)約能量;但節(jié)點在接入后不斷發(fā)送POLL請求，在ACK響應前一直處于活躍狀態(tài)，會造成能量浪費.不少學者也提出了一系列節(jié)能策略［8-13］，從不同層面解決WSN的能耗問題.

本文在周期性休眠的PCF基礎上，提出了一種具有節(jié)能效果的輪詢控制協(xié)議PCF-SS(point coordination function by site status)，在保證公平性的前提下，依據(jù)節(jié)點狀態(tài)進行資源分配和服務.其基本思想是:中心在為某節(jié)點服務的同時獲取該站點的剩余分組信息，且至少保留連續(xù)2輪的狀態(tài)信息，并依據(jù)節(jié)點狀態(tài)將其分配到不同優(yōu)先級組內;同時，根據(jù)節(jié)點最近2次的狀態(tài)估計下一輪的服務時間，并將預計的開始服務時刻在本輪服務結束前通知該節(jié)點，當節(jié)點接受服務后，即可轉入休眠，直到下一輪服務時刻的到來，達到節(jié)能目的.

1 PCF-SS接入控制機制分析

1.1 PCF-SS接入過程描述

傳感器網(wǎng)絡節(jié)點能量和功率有限，導致傳輸距離有限.同時，在多數(shù)應用中，傳感器網(wǎng)絡一旦部署，節(jié)點的移動性很小，甚至不發(fā)生移動.分簇是實施分層控制的重要方法之一，PCF-SS協(xié)議適用于簇內節(jié)點與中心(簇首)的通信，信息通過簇首間的轉發(fā)到達Sink.

每個節(jié)點可處于休眠、活躍、發(fā)送3種狀態(tài)之一，分別對應空閑、喚醒(或請求服務)和接受服務，由相應的條件觸發(fā)轉換，如圖1所示.初始布置后，當終端節(jié)點有分組發(fā)送時，即向中心發(fā)送請求，與中心握手后，加入服務隊列，獲得服務時間表，進入休眠等待，以減少能量消耗.如果較長時間沒有分組發(fā)送，中心則將該節(jié)點從服務隊列中刪除，以減少空輪詢次數(shù)，提高服務效率，直到節(jié)點有新的分組到達時，再次蘇醒并申請加入服務隊列.如果中心在一段時間內沒有收到任何服務請求，也將轉入短暫的休眠，并在下一時刻醒來后，監(jiān)測信道，準備服務.

圖1 節(jié)點狀態(tài)轉移圖Fig.1 Status migration of a node

采用上述接入方法，終端節(jié)點可能會被延遲服務或提早蘇醒，這種情況將在1.3節(jié)中進行分析.

1.2 服務策略

通常情況下，輪詢系統(tǒng)中的各節(jié)點都能獲得固定、均勻的服務時間，這對于對稱型的系統(tǒng)是合理的.但是在實際應用中，節(jié)點的負載往往是不均衡的，根據(jù)需求進行可變配置的服務方式普遍存在.因此，系統(tǒng)以限定(K=1)服務為基礎，根據(jù)節(jié)點繁忙程度劃分優(yōu)先級，分別對節(jié)點上一輪分組剩余量、本輪分組剩余量進行標識區(qū)分，并劃分為4類，如表1所示.

表1 節(jié)點負載狀態(tài)Table 1 The loads status of nodes

具體的服務方式如下.

1)初始時，系統(tǒng)按照限定(K=1)服務規(guī)則對N個節(jié)點進行依次服務，在服務過程中，根據(jù)節(jié)點的負載狀態(tài)，將其劃入到不同的優(yōu)先級組內.

2)輕載隊列采用限定(K=1)服務;忙隊列采用可變(K≥1)服務，即在限定(K=1)的基礎上，根據(jù)節(jié)點當前狀態(tài)和上輪狀態(tài)進行預判，調整優(yōu)先級及下一輪的服務時間;繁忙隊列采用門限服務規(guī)則.節(jié)點接受服務后，轉入休眠狀態(tài).

3)中心根據(jù)服務時間表中剩余節(jié)點和前驅節(jié)點的預計服務時間，估算各節(jié)點下一輪服務的開始時間，并在服務結束前通知該節(jié)點.

4)由于節(jié)點接受服務后轉入休眠狀態(tài)，服務器不能感知其后續(xù)是否有分組到達，因此，輕載組內的節(jié)點被服務后，即使處于空閑狀態(tài)，也被劃分到輕負載組，直到下一輪服務時，仍然空閑才轉入空閑組中，并將其從輪詢列表中刪除.

5)優(yōu)先級高的節(jié)點采用逐級向下調整的策略調整其優(yōu)先級，而低優(yōu)先級的節(jié)點則根據(jù)狀態(tài)直接調整到相應的優(yōu)先級組.

6)空閑節(jié)點一直處于休眠狀態(tài)，直到有分組到達，再申請接入網(wǎng)絡接受服務.

7)每次服務結束后，中心都將進行信道檢測，如果有新節(jié)點加入，則將其安排到輪詢列表的最后.

根據(jù)統(tǒng)計原理，參與預測的歷史狀態(tài)次數(shù)越多，預測值就越可靠，但運算也越復雜，額外開銷越大，因此，系統(tǒng)選取節(jié)點最近2輪的狀態(tài)進行預判.此時，中心存儲的輪詢列表結構可表示為(節(jié)點號，服務順序號，上輪剩余分組數(shù)，本輪剩余分組數(shù)，預分配服務數(shù))，以1號站點為例，初始時刻表示為(1，1，0，0，K).

1.3 服務時間表

中心采用統(tǒng)一的服務時間表來確定各節(jié)點的服務時間和喚醒時刻.當中心為某節(jié)點服務時，根據(jù)其狀態(tài)預判下一輪的服務時間，決定該節(jié)點的喚醒時刻，更新服務時間表，當節(jié)點接受服務后，轉入休眠狀態(tài)并啟動一個喚醒時鐘.

采用服務時間表帶來的一個問題是節(jié)點可能延遲蘇醒(晚醒)或提前蘇醒(早醒).前者是因為中心對剩余節(jié)點的服務規(guī)則可能是門限或可變(K≥1)服務，而節(jié)點的分組到達數(shù)量是隨機的，因此門限服務和可變(K≥1)服務所耗費的時間是不確定的.為此設定了一個門限值Tg來確定門限服務時間，中心可能不需要Tg時間就能完成對某節(jié)點的門限服務，這對后續(xù)節(jié)點來說，相當于延遲蘇醒;同理，對可變(K≥1)服務也一樣，當節(jié)點中的分組數(shù)少于K個時，也將引入延遲.后者正好相反，當中心對某節(jié)點的門限服務在Tg時間內不能完成時，將推遲后續(xù)節(jié)點的服務時間，但后續(xù)節(jié)點并不能感知，仍然按照時間表上的時間喚醒，相當于節(jié)點早醒.上述2種情況是休眠策略不可避免的，晚醒將增加系統(tǒng)時延，早醒則會增加節(jié)點的能耗.此外，當前節(jié)點可能沒有分組發(fā)送，但服務器并不能感知(服務規(guī)則4))，這對服務器來說增加了一個額外的查詢時間，既加大了系統(tǒng)延時，又增加了系統(tǒng)能耗.因此，為了減少延遲或進一步降低能耗，需要更加精確地估計服務時間，這就要求保留站點更多的歷史狀態(tài)，以實時地根據(jù)門限服務時間Tg和可變K值進行調整.

2 系統(tǒng)仿真及分析

2.1 仿真條件

為了便于分析，在仿真過程中進行如下假設.

1)每個節(jié)點在任一時隙內都以均值為λ的相互獨立、同分布的概率分布向各自的存儲器內送入信息分組.

2)任一節(jié)點在接受服務時，由其存儲器內向外發(fā)送一個信息分組所用的時間變量β服從一個相互獨立、同分布的概率分布.

3)不考慮節(jié)點位置對傳輸?shù)挠绊?，?jié)點的轉換時間γ為定值，信道為無差錯狀態(tài).

4)節(jié)點的緩存容量足夠大，不會出現(xiàn)分組溢出現(xiàn)象.

每輪服務結束后，均形成一個新的服務時間表，結構為(節(jié)點號，喚醒時鐘)，在具體實現(xiàn)中，輪詢服務表和服務時間表是結合在一起的.中心為某節(jié)點服務后，依據(jù)最近2次狀態(tài)調整其優(yōu)先級，根據(jù)輪詢服務表中后續(xù)節(jié)點的服務時間，計算下一輪喚醒時刻，預測其分組到達數(shù)，更新輪詢服務表中該節(jié)點的服務數(shù).在仿真中，對忙組內的節(jié)點按照限定K=1+σ服務，其中在仿真中，σ采用了一個分段線性增長函數(shù)，直至最后逼近到門限值，即

式中:Nl為剩余分組數(shù).

2.2 結果分析

在Matlab仿真環(huán)境下，分別對帶休眠的純PCF系統(tǒng)、不訪問空閑節(jié)點的限定(K=1)服務(設為PCF-noempty系統(tǒng))和本文提出的PCF-SS 3個系統(tǒng)進行了仿真.在仿真中，以時隙為單位，假定單位服務時間β=10時隙，中心對節(jié)點的查詢轉換時間γ=1時隙，節(jié)點的分組到達率λ服從泊松分布.實驗對節(jié)點數(shù)N=20和N=30 2種網(wǎng)絡規(guī)模進行了仿真比較，主要收集和比較影響系統(tǒng)性能和能耗的平均等待時間、平均排隊隊長、節(jié)點平均晚醒時間量、節(jié)點平均早醒時間量、中心平均額外查詢時間5個參數(shù)，并進行了歸一化處理，結果如圖2所示.

圖2 系統(tǒng)性能比較Fig.2 Comparison of system performances

從圖2(a)、2(b)可以看出，由于避免了對空閑節(jié)點的訪問，PCF-SS、PCF-noempty系統(tǒng)的平均等待時間和平均排隊隊長與純PCF系統(tǒng)比，性能顯著提高.與PCF-nonempty系統(tǒng)相比，雖然PCF-SS采用了變K服務，但在輕負載下，多數(shù)節(jié)點依然按照限定(K=1)規(guī)則接受服務，所以性能改善不明顯;但隨著負載的加重，PCF-SS中負載重的節(jié)點能夠接受可變(K≥1)服務，從而使系統(tǒng)的整體性能得到了提高.

圖2(c)、2(d)對非空閑節(jié)點的平均晚醒時間和早醒時間進行了比較，在純PCF系統(tǒng)中，不論節(jié)點是否空閑，中心均對其進行輪詢，導致空閑節(jié)點浪費時間，而有業(yè)務的節(jié)點卻只能休眠到其輪次到來時才能接受服務，相反，其早醒情況就幾乎不會發(fā)生，所以早醒時間接近0(如圖2(d)所示).而當負載變繁重后(如當 N=30，λ ＞0.002，此時 Nλ ×(β+γ)＞0.66)，節(jié)點空閑率大大下降，純PCF 的空輪詢也隨之減少，節(jié)點的晚醒反而開始呈下降趨勢.同理，在PCF-noempty系統(tǒng)中，雖然避免了對空閑節(jié)點的輪詢，但由于采用限定(K=1)服務，即各節(jié)點分配的服務時間是相同的，在負載較輕時，周期性休眠后部分節(jié)點處于空閑狀態(tài)，但仍然需要被輪詢1次后才能被確認為空閑節(jié)點(由休眠機制決定)，相當于增加了非空閑節(jié)點的休眠時間(晚醒)，相反，早醒時間就能得到較好控制;隨著負載的加重，節(jié)點空閑率降低，晚醒也呈明顯下降趨勢，但上輪空閑的節(jié)點在下一輪服務時很可能不再空閑，而非空閑節(jié)點并不能感知，依然周期性地醒來，相當于早醒，因此早醒時間呈上升趨勢.而在PCF-SS系統(tǒng)中，雖然也需要對空閑節(jié)點空輪詢1次，但由于采用了服務時間預估計的可變(K≥1)服務，非空閑節(jié)點的平均服務時間比PCF-noempty系統(tǒng)要長，空輪詢1次的時間在總的服務時間中所占比例減小，等效于節(jié)點晚醒時間比值減小，但也因為服務時間是預估的，節(jié)點的實際服務時間比估計時間可能還要長，而后續(xù)節(jié)點依然按照服務時間表上的喚醒時間喚醒，即等效于早醒;因此，在負載不太重時，PCF-SS系統(tǒng)的早醒時間比PCF-noenpty系統(tǒng)有所增加，而隨著負載加重，節(jié)點幾乎都處于忙隊列中，實際服務時間與估計服務時間趨于一致，早醒因素變得單一，這與PCF-noempty系統(tǒng)相同，因此兩者早醒的走勢一致.

圖2(e)對中心(簇首)每輪次的平均額外查詢時間進行了比較，平均額外查詢時間即空閑節(jié)點的查詢時間，可反映中心的能量浪費度.從圖中可以看出，由于純PCF系統(tǒng)對所有節(jié)點都依次輪詢，因此能量浪費最大，但隨著負載變大，空閑節(jié)點數(shù)減少，浪費量呈下降趨勢.而在PCF-noempty和PCF-SS系統(tǒng)中，由于避免了對空閑節(jié)點的輪詢，當輕負載時，空閑節(jié)點數(shù)多，額外查詢時間比值很小，隨著負載加大，節(jié)點在空閑與非空閑間切換，空輪詢1次的概率增加，因此額外查詢時間逐漸增加;但隨著負載變得繁重，系統(tǒng)中幾乎不存在空閑節(jié)點，空閑查詢量又呈下降趨勢.由于PCF-SS系統(tǒng)采用了服務時間預估計的可變(K≥1)服務，服務相同量的信息，所用的服務輪次比PCF-noempty少，空閑查詢導致的能量浪費量比PCF-noempty系統(tǒng)有所降低，因此PCF-SS系統(tǒng)對延長中心(簇首)壽命更加有利.

3 結束語

本文針對無線傳感器網(wǎng)絡的MAC層，提出了一種依據(jù)節(jié)點狀態(tài)進行資源分配和服務的輪詢協(xié)議PCF-SS，通過對節(jié)點服務時間的預估計，采用統(tǒng)一服務時間表的方式來實現(xiàn)休眠.仿真實驗表明，PCF-SS與周期性休眠的PCF機制相比，具有更好的節(jié)能效果和時延性能，特別是中心(簇首)的能量浪費大大減少，緩減了中心能量消耗的瓶頸效應，有利于延長網(wǎng)絡生命周期.下一步的工作將結合節(jié)點的分組到達率分布，對服務K值進行更精確的估計，以進一步提升服務性能，降低等待能耗.

［1］LAN/MAN Standards Committee of the IEEE Computer Society.Part 11:wirelessLAN medium accesscontrol(MAC)and physical layer(PHY)pecifications［S］.New York，USA:IEEE-SA，1999.

［2］楊志軍，趙東風，丁洪偉，等.兩級優(yōu)先級控制輪詢系統(tǒng)研究［J］.電子學報，2009，37(7):1452-1456.

YANG Zhijun，ZHAO Dongfeng，DING Hongwei，et al.Research on two-class priority based polling system［J］.Acta Electronica Sinica，2009，37(7):1452-1456.

［3］廖勇，楊士中，徐昌彪.自適應 IEEE802.11 PCF調度算法［J］.計算機科學，2007，34(12):46-47，55.

LIAO Yong，YANG Shizhong，XU Changbiao.Adaptive scheme on IEEE 802.11 PCF［J］.Computer Science，2007，34(12):46-47，55.

［4］廖勇，楊士中，徐昌彪.基于NS2的自適應差額IEEE802.11 PCF輪詢機制［J］.計算機科學，2009，36(11):36-39，96.

LIAO Yong，YANG Shizhong，XU Changbiao.Adaptive deficit IEEE 802.11 PCF polling scheme based on NS-2［J］.Computer Science，2009，36(11):36-39，96.

［5］CROW B，WIDJAJA I，KIM J G，et a1.IEEE 802.11 wireless loca1 area networks［J］.IEEE Communication Magazine，1997，35(9):116-126.

［6］李琰，朱光喜.3-gated:WLAN中基于負載自適應的動態(tài)調度機制［J］.計算機科學，2008，35(4):28-32.

LI Yan， ZHU Guangxi. 3-gated:dynamicscheduling scheme based on load adaptation over WLAN［J］.Computer Science，2008，35(4):28-32.

［7］黃建輝，錢德沛，王勝靈，等.用于無線傳感器網(wǎng)絡的比例公平隊列調度算法［J］.西安交通大學學報，2008，42(2):129-132，151.HUANG Jianhui，QIAN Depei，WANG Shengling，et al.Proportional fairness scheduling algorithm used for wireless sensor network［J］.Journal of Xi’an Jiaotong University，2008，42(2):129-132，151.

［8］石為人，馮會偉，唐云建.一種無線傳感器網(wǎng)絡MAC層協(xié)議設計與實現(xiàn)［J］.計算機科學，2009，36(7):60-62，67.

SHI Weiren，F(xiàn)ENG Huiwei，TANG Yunjian.Design and implement of wireless sensor network medium access control protocol［J］.Computer Science，2009，36(7):60-62，67.

［9］SHWE H Y，JIANG Xiaohong，HORIGUCHI S.Energy saving in wireless sensor networks［J］.Journal of Communication and Computer，2009，6(5):20-27.

［10］李云，周嫻，尤肖虎，等.IMECN:一種新的無線傳感器網(wǎng)絡拓撲控制算法［J］.電子學報，2010，38(1):48-53.

LI Yun，ZHOU Xian，YOU Xiaohu，et al.IMECN—a new topology control algorithm for wireless sensor networks［J］.Acta Electronica Sinica，2010，38(1):48-53.

［11］劉亮，秦小麟，戴華，等.能量高效的無線傳感器網(wǎng)絡時空查詢處理算法［J］.電子學報，2010，38(1):54-59.

LIU Liang，QIN Xiaolin，DAI Hua，et al.An energy efficient spatio-temporal query processing algorithm in wireless sensor networks［J］.Acta Electronica Sinica，2010，38(1):54-59.

［12］徐石玉，欒曉明.基于分簇的無線傳感器網(wǎng)絡時間同步方法［J］.應用科技，2010，37(6):27-30.

XU Shiyu，LUAN Xiaoming.Cluster-based time synchronization method for wireless sensor networks［J］.Applied Science and Technology，2010，37(6):27-30.

［13］EU Z A，TAN H P，SEACH W K G.Design and performance analysis of MAC schemes for wireless sensor networks powered by ambient energy harvesting［J］.Ad Hoc Networks，2011，9(3):300-323.