GAF分簇算法的無線傳感器網(wǎng)絡研究 - 全文

　　無線傳感器網(wǎng)絡由部署在監(jiān)測區(qū)域內(nèi)大量的廉價微型傳感器節(jié)點組成，通過無線通信方式形成的一個多跳的自組織網(wǎng)絡系統(tǒng)，主要用于收集、傳播和處理傳感信息。

　　與傳統(tǒng)的無線自組織網(wǎng)絡不同，無線傳感器網(wǎng)絡節(jié)點數(shù)目龐大，節(jié)點分布密集；由于環(huán)境影響和能量耗盡，節(jié)點更容易出現(xiàn)故障；環(huán)境干擾和節(jié)點故障易造成網(wǎng)絡拓撲結(jié)構(gòu)的變化。另外，節(jié)點的能量、處理能力、存儲能力和通信能力等都有限，因此無線傳感器網(wǎng)絡的首要設(shè)計目標是能源的高效利用。無線傳感網(wǎng)絡介質(zhì)訪問控制（Media Access Control，MAC）協(xié)議必須以節(jié)約能源為主要目標，并且采用折中機制，使用戶可以在延長網(wǎng)絡生命周期和提高網(wǎng)絡吞吐量、降低通信延遲等方面做出選擇。

　　目前針對不同的傳感器網(wǎng)絡應用，研究人員從不同方面提出了多個MAC協(xié)議，缺乏統(tǒng)一的分類方式，根據(jù)采用固定分配信道方式或隨機訪問信道方式，將傳感器網(wǎng)絡MAC協(xié)議分為：時分復用方式（TDMA）、隨機競爭方式和其他MAC協(xié)議。固定分配信道方式的TDMA可以自然完成節(jié)點上的低占空比操作，因為他們只需在自己的時隙里開啟無線模塊完成發(fā)送和接收，但其可擴展性較差，而時間同步對系統(tǒng)是一筆較大的開銷。由于無線傳感網(wǎng)絡數(shù)據(jù)率較低，而且對時延的要求不高，因此目前實用的節(jié)能MAC協(xié)議基本是基于競爭的協(xié)議。大量實驗和理論分析表明無線傳感器節(jié)點的能量浪費主要源自空閑偵聽、沖突、串擾和控制。因此結(jié)合現(xiàn)有的無線傳感器網(wǎng)絡MAC協(xié)議，引入層次型拓撲結(jié)構(gòu)控制思想，建立一種高效節(jié)能的無線傳感器網(wǎng)絡協(xié)議，并進行分析、仿真和驗證，具有研究意義。

　　1 競爭類MAC協(xié)議分析

　　1.1 S-MAC協(xié)議

　　S-MAC協(xié)議是在802.11MAC協(xié)議的基礎(chǔ)上，針對傳感器網(wǎng)絡的節(jié)能需求而提出的傳感器網(wǎng)絡MAC協(xié)議。S-MAC協(xié)議假設(shè)通常情況下傳感器網(wǎng)絡數(shù)據(jù)傳輸量少，節(jié)點協(xié)作完成共同的任務，網(wǎng)絡內(nèi)部能夠進行數(shù)據(jù)處理和融合以減少數(shù)據(jù)通信量，網(wǎng)絡可以容忍一定程度的延遲。研究表明傳感器能量主要消耗在節(jié)點間的通行上，而空閑偵聽大約占節(jié)點通信能量的1/3.為達到節(jié)省能量的目的S-MAC協(xié)議主要采用周期性的偵聽/睡眠的低占空比機制，控制節(jié)點盡可能處于睡眠狀態(tài)來降低節(jié)點能量的消耗。但S-MAC協(xié)議存在以下問題：S-MAC協(xié)議中同一個虛擬簇中的所有節(jié)點要同時從睡眠狀態(tài)轉(zhuǎn)換到活動狀態(tài)，開始對信道的競爭，而大量節(jié)點沒有數(shù)據(jù)傳輸任務，這些節(jié)點對信道的競爭和空閑偵聽浪費了大量的能量。

　　1.2 T-MAC協(xié)議

　　T-MAC（Timeout MAC）協(xié)議是在S-MAC協(xié)議的基礎(chǔ)上提出的。S-MAC協(xié)議的周期長度受限于延遲要求和緩存大小，而偵聽時間主要依賴于消息速率。因此，為保證消息的可靠傳輸，節(jié)點的周期活動時間必須適應最高的通信負載，從而造成網(wǎng)絡負載較小時，節(jié)點空閑偵聽時間的相對增加，針對這一不足，文獻提出了T-MAC協(xié)議，該協(xié)議在保持周期偵聽長度不變的情況下，根據(jù)通信流量動態(tài)調(diào)整節(jié)點活動時間，用突發(fā)方式發(fā)送消息，減少空閑偵聽時間。但是由于大量無需數(shù)據(jù)傳輸?shù)墓?jié)點對信道的競爭和空閑偵聽仍造成大量能量的浪費，另外T-MAC協(xié)議的執(zhí)行，會出現(xiàn)早睡眠問題，引起網(wǎng)絡的吞吐量降低。為此，它采用兩種方法來提高早睡眠引起的數(shù)據(jù)吞吐量下降：（1）未來請求發(fā)送機制。（2）滿緩沖區(qū)優(yōu)先機制，但效果并不是很理想。

　　2 基于拓撲控制結(jié)構(gòu)的MAC協(xié)議設(shè)計

　　S-MAC、T-MAC虛擬簇中的所有節(jié)點都周期性地從睡眠狀態(tài)轉(zhuǎn)入工作狀態(tài)，參與信道的競爭和數(shù)據(jù)傳輸，而大部分節(jié)點沒有數(shù)據(jù)傳輸任務，造成他們在大部分活動時間處于空閑偵聽狀態(tài)，而浪費了大量能量。針對S-MAC、T-MAC無法避免的問題，提出了新MAC協(xié)議GS-MAC（Geo graphical SeNSor MAC）。GS-MAC協(xié)議引入了GAF拓撲控制算法后，適當減少活動節(jié)點數(shù)量，加快算法的收斂速度，減少大量節(jié)點對信道的空閑偵聽和數(shù)據(jù)碰撞，從而達到節(jié)能的目的。

　　2.1 GAF改進算法

　　GAF（Geographical Adaptive Fidelity）算法是以節(jié)點地理位置為依據(jù)的分簇算法，該算法把監(jiān)測區(qū)域分成虛擬單元格，將節(jié)點按照位置信息劃入相應的單元格；每個單元格中定期選舉產(chǎn)生一個簇頭節(jié)點，只有簇頭節(jié)點保持活動，其他節(jié)點進入睡眠狀態(tài)，GAF算法的執(zhí)行包括兩個階段：第一階段是虛擬單元格的劃分；第二階段是簇頭的選舉產(chǎn)生。

　　虛擬單元格的劃分：根據(jù)節(jié)點的位置信息和通信半徑，將網(wǎng)絡區(qū)域劃分成若干虛擬單元格，保證相鄰單元格中的任意兩個節(jié)點都能夠直接通信。為保證相鄰兩個單元格中任意的兩個節(jié)點都能夠直接通信，需滿足如下關(guān)系式

　　在式（1）中，R為所有節(jié)點的通信半徑；r為正方形虛擬單元格邊長。

　　簇頭的選舉產(chǎn)生：GAF算法中簇頭承擔更多的數(shù)據(jù)處理和通信，消耗的能量相對較大。在改進的GAF算法中簇頭的選舉考慮到了節(jié)點剩余能量問題，選舉剩余能量較多的節(jié)點擔任簇頭。隨機簇頭選舉算法：節(jié)點只知道自己的能量信息和位置信息。假設(shè)某次簇頭選舉在Tr時刻開始，對單元格內(nèi)任意節(jié)點N，以概率P發(fā)送測試消息。概率P與剩余能量成正比，如果測試消息成功，它就發(fā)生消息M（Ep，N），Ep為節(jié)點N剩余能量；如果消息發(fā)送不成功，節(jié)點N進入偵聽狀態(tài)。如果在一個時槽內(nèi)沒有接到發(fā)送消息，表明該時槽內(nèi)沒有節(jié)點競爭成功，開始新一輪的選舉，反之，如果有節(jié)點競爭成功，發(fā)送M（Ep，N）消息擔任簇頭，單元格內(nèi)其他節(jié)點偵聽到消息M加入該簇。

　　2.2 GS-MAC協(xié)議描述

　　在GS-MAC協(xié)議中只有簇頭節(jié)點進入活動狀態(tài)如圖1和圖2所示。

　　在新協(xié)議中，由于引入拓撲結(jié)構(gòu)機制，可以減少一部分節(jié)點的空閑偵聽時間，只保留簇頭節(jié)點處于活動狀態(tài)，在簇頭選舉中考慮到節(jié)點剩余能量，在局部范圍內(nèi)做到平衡節(jié)點剩余能量，延長了網(wǎng)絡生存周期。

　　簇頭節(jié)點維護和S-MAC協(xié)議類似的工作/睡眠機制，每個簇頭節(jié)點周期性的與直接鄰近簇頭節(jié)點通過接收和廣播SYNC數(shù)據(jù)幀來交換調(diào)度信息；采用CSMA/CA機制和隨機退避時間；經(jīng)歷RTS/CTS/DATA/ACK通信過程完成數(shù)據(jù)傳輸，在數(shù)據(jù)傳輸完成之前不遵循其休眠時間安排；采用流量自適應偵聽機制，減少消息的傳輸時延。

　　2.3 性能分析

　　利用NS2對S-MAC協(xié)議和新協(xié)議（GS-MAC）在能量消耗和傳輸時延兩方面進行比較，其中能量消耗為從源節(jié)點發(fā)送一定數(shù)量包到目的節(jié)點的總能耗，時延為端到端時延。仿真場景設(shè)置300 m×300 m，布置10~50個節(jié)點，R=300 m，r=100 m，劃分9個虛擬單元格。仿真參數(shù)選擇如表1所示。

　　從圖3可以看出在節(jié)點數(shù)目等于10時，幾乎每個虛擬單元格都只有1個節(jié)點，GAF拓撲控制算法效率低，基本接近S-MAC協(xié)議，隨著節(jié)點數(shù)目的逐步增加，GAF拓撲控制算法效率顯著提高，能量消耗明顯降低。

　　為比較兩種協(xié)議在網(wǎng)絡延遲性能方面的表現(xiàn)。在300m×300 m的場景中均勻布置50個固定節(jié)點，采用多跳網(wǎng)絡拓撲來測試端到端的數(shù)據(jù)時延，源節(jié)點產(chǎn)生20條消息，每條100 Byte，所有消息不分片，在輕流量載荷條件下重復10次實驗，測的每條平均消息時延如圖4所示，由于源節(jié)點在GS-MAC中競爭簇頭節(jié)點形成的時延，造成兩種協(xié)議中第一個轉(zhuǎn)發(fā)跳時延有較大差異，隨著消息的向前傳遞，后面排隊時延較少，但由于GS-MAC中發(fā)現(xiàn)狀態(tài)的存在，使GS-MAC協(xié)議時延略大于S-MAC協(xié)議時延。

　　綜上所述，引進拓撲結(jié)構(gòu)控制的GS-MAC協(xié)議能夠在正常延時的條件下，進一步降低了節(jié)點能耗，延長了網(wǎng)絡生存期。

　　3 結(jié)束語

　　通過分析無線傳感器網(wǎng)絡S-MAC協(xié)議性能，針對在數(shù)據(jù)業(yè)務量少的情況下，大部分傳感器節(jié)點處于空閑偵聽狀態(tài)，浪費了大量節(jié)點能量，引入GAF拓撲結(jié)構(gòu)控制算法，使得在正常的網(wǎng)絡延遲下，大幅減少了處于空閑偵聽狀態(tài)下的節(jié)點數(shù)量。通過仿真表明，GS-MAC協(xié)議具有較高的能量效率，延長了網(wǎng)絡使用壽命。