一種能量有效的無線傳感器網絡輪詢接入控制協議

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

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

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

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

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

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

1.1 PCF-SS接入過程描述

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

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

圖1 節點狀態轉移圖Fig.1 Status migration of a node

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

1.2 服務策略

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

表1 節點負載狀態Table 1 The loads status of nodes

具體的服務方式如下.

1)初始時，系統按照限定(K=1)服務規則對N個節點進行依次服務，在服務過程中，根據節點的負載狀態，將其劃入到不同的優先級組內.

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

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

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

5)優先級高的節點采用逐級向下調整的策略調整其優先級，而低優先級的節點則根據狀態直接調整到相應的優先級組.

6)空閑節點一直處于休眠狀態，直到有分組到達，再申請接入網絡接受服務.

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

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

1.3 服務時間表

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

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

2 系統仿真及分析

2.1 仿真條件

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

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

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

3)不考慮節點位置對傳輸的影響，節點的轉換時間γ為定值，信道為無差錯狀態.

4)節點的緩存容量足夠大，不會出現分組溢出現象.

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

式中:Nl為剩余分組數.

2.2 結果分析

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

圖2 系統性能比較Fig.2 Comparison of system performances

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

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

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

3 結束語

本文針對無線傳感器網絡的MAC層，提出了一種依據節點狀態進行資源分配和服務的輪詢協議PCF-SS，通過對節點服務時間的預估計，采用統一服務時間表的方式來實現休眠.仿真實驗表明，PCF-SS與周期性休眠的PCF機制相比，具有更好的節能效果和時延性能，特別是中心(簇首)的能量浪費大大減少，緩減了中心能量消耗的瓶頸效應，有利于延長網絡生命周期.下一步的工作將結合節點的分組到達率分布，對服務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］楊志軍，趙東風，丁洪偉，等.兩級優先級控制輪詢系統研究［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中基于負載自適應的動態調度機制［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］黃建輝，錢德沛，王勝靈，等.用于無線傳感器網絡的比例公平隊列調度算法［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］石為人，馮會偉，唐云建.一種無線傳感器網絡MAC層協議設計與實現［J］.計算機科學，2009，36(7):60-62，67.

SHI Weiren，FENG 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:一種新的無線傳感器網絡拓撲控制算法［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］劉亮，秦小麟，戴華，等.能量高效的無線傳感器網絡時空查詢處理算法［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］徐石玉，欒曉明.基于分簇的無線傳感器網絡時間同步方法［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.