一種基于節點重要性和空間相關性的無線傳感器網絡MAC協議

摘 要:提出了一種新的基于節點重要性和空間相關性的MAC協議(NISC-MAC)，該協議將數據相關性小的節點，即數據差異大的節點定義為重要節點，并賦予其高的優先權。優先權高的節點發送數據的概率大，退避時間短，從而能優先地競爭到信道。把這些重要性節點選定為代表性節點，確保這些重要的數據發送到sink節點，這樣可保證數據的整體有效性，使收到的數據能更好地反映出物理現象。NISC-MAC協議在去除數據空間相關性的同時確保了數據的整體有效性，仿真實驗表明此協議在較低的能耗和傳輸延時下確保了數據的整體有效性。

關鍵詞:無線傳感器網絡; 媒體訪問控制協議; 空間相關性; 節點重要性

中圖分類號:TP393

文獻標志碼:A

文章編號:1001-3695(2010)02-0664-04

doi:10.3969/j.issn.1001-3695.2010.02.072

Node importance and spatial correlation-based MAC in WSN

LIU Fang-cai， ZHOU Si-wang， LI Lan

(College of Software， Hunan University， Changsha 410082， China)

Abstract:This paper proposed a new node importance and spatial correlation-based MAC protocol(NISC-MAC)， which defined the smaller nodes interrelated， i.e.， the nodes with great data difference， as the important nodes， and attributed it high priority. Those high priority nodes could send data with highly probability and backoff time shortly so that it was given highly priority in the competition to channel. And they could choose out the important nodes as the representative nodes， made sure those vital data send successfully to the sink node. This would ensure the overall effectiveness of data，made the data received reflect the real physical phenomenon. NISC-MAC is not onlyremoval of spatial correlation of data， but also to ensure the overall effectiveness of data; the simulation experiment indicates the protocol ensure the overall effectiveness of data under low energy consumption and transmission delay.

Key words:wireless sensor networks(WSN); medium access control protocol; spatial correlation; node importance

0 引言

在無線傳感器網絡中，一般會通過部署相對密集的節點來保證區域的覆蓋和節點的冗余度，以確保收集傳感數據、可靠的通信和一定的網絡生命周期。當節點越密集，監測到同一事件的節點數越多，各節點收集到的信息就有越高的相關度，空間相關的信息導致的信道競爭就越多。而網絡內的通信資源使用量很有限。無線傳感器節點能量的消耗由三部分組成，即數據的傳感采集、處理和傳輸。在這三部分能量消耗中，大部分能量消耗在數據傳輸的過程中，所以在盡量保證應用需求的情況下，在MAC層減少工作節點的數量，將大大的減少數據的發送量，節省很多傳輸能量。通過選擇代表性節點發送數據，去除了數據的空間相關性，可以大量地減少數據的發送，從而大大節省網絡能量。最近有研究表明在大型的傳感器網絡中，失真度、時空相關性和能量之間有一定關系，WSN中數據有一定的空間相關性并且可以構建出相關性模型[1]。

WSN中，單信道條件下，所有傳感器節點共享一個無線信道，信道資源是非常有限的，因而需要一個有效的媒體訪問控制(medium access control)協議來協調各節點對信道的訪問。沒有MAC協議的協調，多個節點就可能同時在無線信道上傳送數據，從而導致碰撞的發生。而普通的MAC協議一般不適合于無線傳感器網絡，適合無線傳感器網絡中的MAC協議近年來國內外有了很多研究，提出了多種適用于WSN的MAC協議[2]，這些協議大致可以分為兩類[3]，即基于競爭模式(con-tention-based)[4~6]和基于調度模式(schedule-based)[7，8]。由于本文采用的是基于競爭模式，下面僅討論兩種典型的基于競爭模式的MAC協議。

Sift-MAC[4]協議是針對基于事件驅動的基于競爭的無線傳感器網絡MAC協議， 它的核心思想是采用CW值固定的窗口，節點不是從發送窗口選擇發送時槽，而是在不同的時槽中選擇發送數據的概率。節點在不同時槽選擇不同的發送概率。S-MAC[5]是一種最典型的基于競爭模式的協議，它通過協商的一致性睡眠調度機制形成虛擬簇，通過控制節點盡可能處于睡眠狀態來降低能量的消耗。同時，國內外學者對WSN中的空間相關性在MAC協議中的應用問題也開展了較為廣泛深入的研究[1，4，9，10]，提出了多種方案來選擇一部分節點發送其傳感數據，以此減少或消除各節點在MAC層的信道爭用。

文獻[1]中CC-MAC協議將整個網絡劃分為若干子區域，稱為相關性區域，在每個相關性區域中同時僅選擇一個節點發送數據，以降低或消除信道爭用。文獻[1]是在確保數據一定失真度(DE(M))的前提下共選擇M個代表節點，在競爭信道的初始階段，哪個節點先競爭到信道，就被選為代表性節點，并通過相關半徑確定相關區域。在這個相關區域中，只有代表性節點發送數據，其他的節點不發送。文獻[1]的研究成果是本文工作的基礎。但文獻[1]在選取代表節點時并沒有考慮各個代表節點的重要性，只是將先隨機競爭到信道的節點作為代表節點。而在實際的監測中有些節點是十分重要的，如在監測溫度時，若某個區域只有一個節點是向陽的，其他節點都是向陰的，那么這個向陽的節點就顯得十分重要，若它沒有被選為代表性節點，沒有將數據發送到sink節點，則對整個監測結果的有效性產生很大影響。所以像這種重要性節點必須被優先選為代表性節點。本文認為在選擇代表性節點時，必須考慮節點的重要性，將數據差異大的，即重要性的節點優先競爭到信道，優先選擇為代表性節點，發送數據到sink節點，從而保證數據的整體有效性?；诖?，本文提出了一種新的基于節點重要性和空間相關性的MAC協議(NISC-MAC)，即在去除空間相關性的同時，將重要性的節點選為代表節點。這就是本文要完成的主要工作。

1 問題的描述

1.1 問題的提出

假設有一個隨機部署的稠密無線傳感器網絡應用，它監測森林里某個區域的溫度。在這個區域中隨機部署50個節點，其拓撲圖如圖1所示。

在圖1中假設空心節點n0、n10、n13、n41、n44是向陽的，而其他節點都向陰。針對這樣一個網絡應用，認為這五個節點是很重要的，稱之為重要性節點。它們對整個監測數據的影響比較大，應該被選擇為代表性節點，讓其能優先競爭到信道，發送數據到sink節點。這樣才能更好地確保數據整體的有效性，使接收到的數據能更好地反映整個監測狀況。本文將在后面提出一種方案來實現這個思想，確保圖1中的這五個重要性節點被選為代表性節點。

1.2 節點重要性的定義

假設有一個隨機部署的稠密無線傳感器網絡應用，它監測某個區域的物理特性。節點之間采集到的數據有一定的相關性，通過計算出兩個數據流的歐氏距離來表示兩個數據流之間的相關性，歐氏距離的大小代表了兩個數據流之間的相關性;歐氏距離大的相關性小。而節點采集到的數據與相關區域的其他節點的差異大，則相應的歐氏距離也大。這些差異大的節點，被認為對整個數據的影響會很大，相對而言更重要些。為了描述這些節點的重要性，引入節點重要性的定義。將網絡中節點i的重要性K定義為

K(i)=dis=∑(Si-S-)2

其中:dis表示節點i采集到的數據流Si與節點i所在的相關區域中節點采集到的數據流均值S-之間的歐氏距離。相關性小的，即差別大的節點的K值大，也就是重要性高。K值代表了節點的重要性。

2 NISC-MAC協議

上章提出了節點重要性的概念，本章在此基礎上結合文獻[1]中的節點選擇算法(INS)，提出一種將節點重要性與空間相關性結合起來的MAC協議(node import and spatial correlation-based MAC)。INS算法目標是找出代表節點個數，形成Voronoi分割。Voronoi分割將整塊區域分成很多小區域，定義這些小區域為相關區域。在相關區域內只有代表性節點發送消息到sink節點，其他節點不傳輸信息。Voronoi分解區域的平均半徑定義為相關半徑，記做rcorr。相關區域內的兩個節點的距離小于rcorr時，則為相關鄰居。相關鄰居采集的數據具有很強的空間相關性。NISC-MAC協議通過INS算法選擇代表性節點的個數，去除了節點的空間相關性，同時使用重要性節點篩選策略把重要性節點選為代表性節點，確保數據的整體有效性。下面將具體描述這個協議。

2.1 重要性節點篩選策略

為了使重要性的節點優先競爭到信道，優先選為代表性節點，設計一個權值函數。使用階梯函數f(K)將重要性映射到一個整數權值，如圖2所示。

當重要性K高于Kmax時，其權值為Lmax，處于較小的某一區間的權值均為Lmin。每級的差值與Lmin均為1。這樣K值大的權值就大，將優先競爭到信道，相關性很近的其權值是一樣的，競爭信道的概率也是一樣的，這樣就可以最大限度地去除節點數據的空間相關性。

節點的權值決定了該節點需發送監測數據的概率，使用一個截斷的、漸增幾何分布函數來表示兩者之間的關系:

Pl=0l=0

(((1-α)×αLmax)/(1-αLmax))×α-ll=1，…，Lmax-1

1l=Lmax

其中:l是節點的權值，0<α現它無須發送數據，就進入睡眠狀態以降低能耗，其函數關系如圖3所示。

2.2 沖突避免策略

通常在基于競爭模式的MAC協議中，各節點都是平等的競爭信道，各節點發送數據的概率都一樣。在基于窗口的競爭協議中，所有節點會在[0，CW-l]中隨機挑選一個競爭時隙傳輸。若兩個或多個節點隨機挑選到同一個時隙，就會造成沖突。為了避免沖突，它們通過調整CW大小來重新選擇時隙。在二進制指數退避算法中，隨機退避時間按以下公式計算:

退避時間= int(CWrandom())×slot_time

其中:int是取整函數;CW是指數競爭窗口參數，取值為CWmin~CWmax，在初始化時，CW值為CWmax。當要發生重傳時，CW按指數級別逐次增大，直到最大值CWmax為止。當CW達到CWmax時，它不再變化，盡管這時會發生較多的沖突。各節點在傳輸成功后，其CW值恢復到初始值CWmin。Random()是產生(0，1) 之間的一個隨機數;slot_time是一個時槽時間，包括發射啟動時間、媒體傳播時延、檢測信道的相應時間等。

本文希望在確保數據一定失真度的情況下，節點在爭用信道時，優先級高的節點擁有媒體接入的優先權。當CW越小，節點退避的時間就越短，接入的機會更大。為了讓不同的節點獲取信道的概率不同，建立了一個發送概率與退避窗口的函數關系。發送概率最高的節點，其初始窗口為CWmin，而其他節點i的初始窗口為

CWmin(i)=21-pi×CWmin

其中:Pi為節點i的發送概率。

那么在新的二進制退避算法中，隨機退避時間按以下公式計算:

退避時間=int(CWmin(i)×random())×slot_time

這樣發送概率高的節點的初始窗口將較小，在退避時，退避時間短，能優先于競爭到信道。

2.3 NISC-MAC協議的包結構

把節點的優先級信息和空間相關性信息封裝在數據包內，在RTS/CTS/DATA預留的空間內劃出1 bit作為KIND域，另外劃出32 bit用來作為PRI域(發送概率域)。KIND域幫助傳感器節點區分數據包的類別，并依此來判定數據包是原始數據包還是要路由的包，節點據此來執行源發送操作還是路由轉發操作;源發送操作就是節點發送自己產生的原始數據包，路由轉發操作就是轉發其他節點的路由包。 PRI域保存了節點的發送概率數值，用來表示節點的發送概率大小，并以此來選定代表性節點。

節點在采集事件信息時，設置自己的RTS、CTS和DATA包的KIND域為0，說明這是節點的原始數據包。當某節點偵聽到某個RTS包中的KIND域為0時，它就認為這是一個原始數據包。接收這個RTS包的節點將CTS包的KIND域設為0，并發送回源節點。這樣，數據的發送者和接收者的鄰居都知道了需要發送的DATA包的類型。它們的某個鄰居節點收到DATA包時，將其KIND域設置為1，顯示此包以后為過路數據包。此節點轉發這個路由數據包到下一跳的節點。而其他節點接收到DATA包時，它檢查其KIND域，若KIND域為1則執行路由轉發操作，此時若節點有源發送操作，則抑制源發送操作，先執行路由轉發操作。

在最初競爭信道時，節點發送RTS包，相關區域的鄰居節點監聽到這個數據包，取出RTS包中的PRI域，并與自己的比較大小，若自己的小，則放棄競爭信道，這樣PRI大的節點將優先競爭到信道，并通過相關半徑確定相關區域。圖4為RTS/CTS/DATA包的結構圖。

frame controldurationRATAKINDPRIFCS

bit 1616484813232

(a)RTS包結構

framecontroldurationRAKINDFCS

bit 161648132

MACheaderKINDframebodyFCS

bit 24010~1849632

(b)CTS包結構

(c)DATA包結構

圖4 RTS/CTS/DATA包結構圖

2.4 NISC-MAC協議的思想

NISC-MAC協議的核心思想是:通過INS算法確定代表性節點的數量，去除節點數據的空間相關性;同時把重要性的節點設置高的優先級，使其發送數據的概率大，從而更易競爭到信道，優先被選為代表性節點，發送數據到sink節點，確保整個監測數據的有效性。在競爭時，本協議采用了本文定義的二進制退避算法。

在網絡初始化的過程中，先傳輸很短一段時間t(這個時間可根據具體的實驗選定)的數據到sink節點，sink節點取每個節點的一個數據流進行分析，計算出K值;然后通過預置或定期廣播通知的方式將K值傳播到監測區域內的所有節點。節點通過接收到的K值計算出自己的優先級、Pi和CWmin(i);同時運行INS算法計算出相關半徑并廣播給各個節點;然后節點開始競爭信道。所有事件節點使用RTS/CTS/DATA/ACK第一次競爭信道，節點發送RTS包，其相關鄰居節點監聽到這個包，取出包中的PRI域，與自己的比較。若比自己的大，則放棄競爭信道;否則繼續競爭。競爭過程中將運行本文定義的二進制退避算法。

在這個最初的競爭階段之后，競爭到信道的節點i根據相關半徑形成相關區域，節點i繼續發送信息到sink節點，作為相關區域的惟一代表。當消息在發送時，節點rcorr根據聽到的信息計算出它到i的距離d(i，j)。如果d(i，j)小于rcorr，則j為i的相關鄰居節點。如果大于rcorr并且有包發送，則競爭信道。

相關區域確定后，代表性節點發送數據，為了節省能量，其他節點進入睡眠狀態(SS)。在SS的傳輸期間，相關鄰居節點進入睡眠狀態;然而，為了能夠轉發路由的數據包和維持網絡的連通性，在一個隨機睡眠間隔時間T后，相關鄰居節點開始監聽信道。當一個相關鄰居節點收到一個關于路由的RTS包，它從SS狀態轉到接收狀態并接收數據包再轉發。若代表性節點接到一個數據包，則查看其KIND域，若其值為1則優先路由轉發這個數據包，抑制源發送操作。在SS之后，節點再進入網絡初始化過程，重復整個過程。

3 仿真實驗

本章利用仿真實驗和分析的方法對本文提出的NISC-MAC協議進行性能分析，并與IEEE 802.11、S-MAC和CC-MAC協議進行了性能的比較分析。

筆者選擇國際上流行的無線傳感器網絡仿真軟件OMNET++[11]來模擬本協議。在200m×200m的區域內隨機部署了50個節點，并將其中一個節點設置為sink節點，其位置坐標設為(199，0)。通過改變節點采集和發送數據的周期，從而產生不同的網絡負載，來驗證分析NISC-MAC協議的性能，仿真時間為600s。主要考察協議的兩個性能指標:

a)平均能耗。每個節點的平均能耗，單位為毫焦耳(10-3J)。

b)媒體接入延時。從發送節點將數據包交給MAC層到下一跳接收節點收到數據包的平均時間差。這個性能參數在基于競爭的MAC協議中主要用來衡量競爭時延。

仿真實驗初始化的主要參數配置如表1所示。仿真實驗結果分析如圖5所示。

圖5描述了四種MAC協議在不同網絡負載情況下的平均能量消耗。從中可以看出，NISC-MAC協議的平均能耗略小于CC-MAC，這是因為NISC-MAC協議在節點競爭媒體時，給節點設置了優先級，各節點有不同的發送概率，減少了相關區域的節點的競爭;同時當節點在退避狀態時，NISC-MAC協議每個節點的初始化窗口不一樣，從而各個節點的退避時間不一樣，減少了節點發送沖突的可能。與其他的兩個協議相比，NISC-MAC顯著地節約了大量的能量，這是因為它利用了空間相關性，大大地減少了數據的發送量。

圖6描述了四種MAC協議在不同網絡負載的情況下媒體訪問延時。從中可以看出，四種MAC協議的延時時間都很小。NISC-MAC的延時略小于CC-MAC，這是因為NISC-MAC協議相關區域的節點競爭減少。

本文用采集到的原始數據在文獻[1]和本文方案下接收到的數據作一個比較。為了進行更好的比較，引入以下方差概念:

D(S)=E[(Si-E(S))2] (i=1，2)

其中:D(S)為方差;Si代表兩種方案收到的數據;S代表所有節點采集的原始數據。本數值實驗中，S的原始數據是50個節點采集到的數據，Si的數據是兩種方案下選擇不同個數的代表節點分別采集到的數據。i=1代表文獻[1]中的方案，i=2代表本文方案。方差的大小代表Si與E(S)的偏離值。偏離值越大，說明Si與S的差異越大。理論上將重要性節點，即數據差異大的節點選為代表性節點，那么收到的數據的方差比隨機選擇的要大，可以用這個方差來衡量重要性節點是否被選擇。數值模擬實驗結果如圖7所示。

圖7中，橫坐標為選擇的代表性節點個數，縱坐標為D(S)。從圖7中看出，在選擇的代表性節點少于30個時，NISC-MAC協議的D(S)明顯大于CC-MAC。這是因為，NISC-MAC協議將大部分重要性節點選擇為代表性節點，而CC-MAC協議是隨機選擇的，只隨機地選到了小部分或沒有選到重要性節點。這說明，本文方案將重要性節點優先選擇為代表性節點，讓重要性數據發送到了sink節點，確保了數據的整體有效性，與筆者的理論分析是一致的。

4 結束語

節點數量眾多且分布稠密的傳感器網絡產生的數據中存在著很強的空間相關性。基于空間相關性的MAC協議能減輕網絡中數據傳輸量和減輕網絡沖突，從而達到節省能量的目的;同時將一些重要性節點優先選擇為代表性節點，將數據發送到sink節點，能夠確保監測數據的整體有效性。本文將空間相關性與節點重要性結合起來，提出了一個新的基于節點重要性和空間相關性的MAC協議(NISC-MAC)。仿真實驗表明，NISC-MAC協議在延時不大的情況下，不僅大大地節省了網絡的能量，而且確保了監測數據的整體有效性，使監測的數據更能反映出實際的物理現象。

下一步將研究相關性區域的重要性，在重要的相關區域中選擇k個代表性節點，根據具體的應用要求來確定k值。

參考文獻:

[1]VURAN M C，AKYILDIZ I F.Spatial correlation based collaborative medium access control in wireless sensor networks [J]. IEEE/ACM Trans on Networking，2006，14(2):316-329.

[2]蹇強，龔正虎，朱培棟，等.無線傳感器網絡MAC協議研究進展[J].軟件學報，2008，19(2):389-403.

[3]孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京:清華大學出版社，2005:59-88.

[4]JAMIESON K， BALAKRISHNAN H，TAY Y.Sift:a MAC protocol for event: driven wireless sensor networks， LCS-TR-894[R]. [S.l.]:MIT，2003.

[5]YE W ，HEIDEMANN J，ESTRIN D.Medium access control with coordinated adaptive sleeping for wireless sensor networks[J]. IEEE Trans on Networking，2004，12(3):493-506.

[6]DAM T van. LANGENDOEN K.An adaptive energy-efficient MAC protocol for wireless sensor networks[C]//Proc of Conference on Embedded Networked Sensor Systerns. New York: ACM Press， 2003:171-180.

[7]RAJENDRAN V，OBRACZKA K， GARCIA-LUNA-ACEVES J J.Energy-efficient， collision-free medium access control for wireless sensor networks[C]//Proc of the 1st ACM International Conference on Embedded Networked Sensor Systems. New York: ACM Press，2003:181-192.

[8]CARLEY TW， BA MA， BARUA R， et al. Contention-free periodic message scheduler medium access control in wireless sensor/actuator networks[C]//Proc of the 24th IEEE Real-time Systems Symposium. Washington DC: IEEE Computer Society，2003:298-307.

[9]ZHOU Xi， XUE Guang-tao， QIAN C， et al. Efficient data suppression for wireless sensor networks[C]//Proc of the 14th IEEE Interanational Conference on Parallel and Distributed Systems. Washington DC: IEEE Computer Society，2008:599-606.

[10]ZOGH M R， KAHAEI M H. Sensor selection for target tracking in WSN using modified INS algorithm[C]//Proc of the 3rd Information and Communication Technologies: From Theory to Applications.2008:1-6.

[11]石為人，黃河，鮮曉東，等.OMNET++與NS2在無線傳感器網絡仿真中的比較研究[J].計算機科學，2008，35(10):53-57.