尚鳳軍，龔文娟，耿哲

?

基于鏈路預(yù)測和網(wǎng)絡(luò)編碼的MAC機(jī)制

尚鳳軍，龔文娟，耿哲

（重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065）

提出了基于鏈路預(yù)測和網(wǎng)絡(luò)編碼的MAC協(xié)議，在EasiLQE的基礎(chǔ)上給出了基于窗口自適應(yīng)的改進(jìn)EF濾波器的鏈路質(zhì)量預(yù)測方法，采用自適應(yīng)周期的主動探測，增加網(wǎng)絡(luò)環(huán)境穩(wěn)定時的估計(jì)準(zhǔn)確性，采用了瞬時主動探測模塊，在保證估計(jì)穩(wěn)定性的前提下提高了突發(fā)狀況下的反應(yīng)速度。在改進(jìn)鏈路質(zhì)量估計(jì)方法的基礎(chǔ)上，給出了一種新的MAC協(xié)議。在協(xié)議中合理地利用了無線網(wǎng)絡(luò)中已經(jīng)存在的廣播特性，在路由算法確定的路由周圍增加高階輔助節(jié)點(diǎn)，從而明顯增加了網(wǎng)絡(luò)編碼機(jī)會，同時又不會引發(fā)由流量集中帶來的諸多問題。最后討論了MAC機(jī)制中最優(yōu)的階數(shù)，在編碼機(jī)會和能量效率上尋求到一個較為合適的平衡點(diǎn)。實(shí)驗(yàn)證明，所提MAC協(xié)議能夠在不集中流量的前提下合理利用節(jié)點(diǎn)的過度偵聽提高編碼機(jī)會，增加網(wǎng)絡(luò)的吞吐量。

鏈路質(zhì)量估計(jì)；網(wǎng)絡(luò)編碼；路徑優(yōu)化；最優(yōu)階數(shù)

1 引言

隨著現(xiàn)代通信、微電子芯片和嵌入式技術(shù)發(fā)展，無線傳感器網(wǎng)絡(luò)(WSN, wireless sensor network)成為了一個新興的研究熱點(diǎn)，引起了眾多研究者和研究機(jī)構(gòu)的密切關(guān)注[1]。作為無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)中的關(guān)鍵之一，介質(zhì)訪問控制層(MAC, medium access control)保證了傳感器網(wǎng)絡(luò)內(nèi)點(diǎn)到點(diǎn)以及點(diǎn)到多點(diǎn)的連接，極大地影響了網(wǎng)絡(luò)的性能，與邏輯連接控制層以及物理層共同構(gòu)成了無線傳感器網(wǎng)絡(luò)的底層基礎(chǔ)，是無線傳感器網(wǎng)絡(luò)研究的重點(diǎn)之一[2]。在MAC協(xié)議中，最為經(jīng)典的是S-MAC[3]，它是在802.11基礎(chǔ)上提出的第一個MAC協(xié)議。T-MAC[4]可以認(rèn)為是5種事件激活的被動變化睡眠周期的改進(jìn)型S-MAC協(xié)議。B-MAC[5]為了實(shí)現(xiàn)低功耗偵聽引入了前導(dǎo)序列的概念，Wise-MAC[6]和X-MAC[7]都是在前導(dǎo)的基礎(chǔ)上做了改進(jìn)。Sift[8]協(xié)議是針對事件驅(qū)動的傳感器網(wǎng)絡(luò)應(yīng)用，當(dāng)多個節(jié)點(diǎn)同時檢測到同一個事件，只保證其中的部分節(jié)點(diǎn)發(fā)送檢測信息，一定程度上降低了網(wǎng)絡(luò)沖突的概率，但協(xié)議基于嚴(yán)格的時鐘同步。D-MAC[9]協(xié)議根據(jù)網(wǎng)絡(luò)傳輸?shù)臉錉罱Y(jié)構(gòu)，調(diào)整休眠調(diào)度策略，使下層節(jié)點(diǎn)的發(fā)送時間與上層節(jié)點(diǎn)的接收時間相對應(yīng)。以后提出的一系列具有影響的MAC協(xié)議還有coopMAC[10]、CD-MAC[11]、Z-MAC[12]和MaxMAC[13]等。

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)采用能量有限的電池供電，無法長時間處于工作狀態(tài)，而網(wǎng)絡(luò)編碼[14]是將不同的數(shù)據(jù)流組合到信道中進(jìn)行傳輸，從而能夠接近香農(nóng)公式的上限[15]，為傳感器網(wǎng)絡(luò)的能量問題提供了新的解決方案。理論上來講，網(wǎng)絡(luò)中能夠編碼的數(shù)據(jù)分組越多，那么網(wǎng)絡(luò)的吞吐量就可以越大。所以網(wǎng)絡(luò)編碼的研究目的之一是設(shè)法增大編碼率[16]，Katti等[17]提出基于網(wǎng)絡(luò)編碼優(yōu)化的COPE方法。隨之又出現(xiàn)了集中式流量感知的編碼方法[18]，通過調(diào)整節(jié)點(diǎn)上的數(shù)據(jù)流而增加編碼機(jī)會，但容易造成負(fù)載不均衡。為了解決流量感知引發(fā)負(fù)載過于集中的問題，Zhang等[19]提出了基于數(shù)據(jù)分散的主動混合編碼BEND。與流量集中相反，這個方法使網(wǎng)絡(luò)中的流量趨于分散，所以不會產(chǎn)生由于負(fù)載不均衡而導(dǎo)致的各種情況，并在一定程度上均衡整個網(wǎng)絡(luò)的負(fù)載。網(wǎng)絡(luò)編碼可以通過尋找網(wǎng)絡(luò)中存在的編碼機(jī)會[20]，以編碼的方式減少傳輸次數(shù)，從而在傳輸相同數(shù)據(jù)量數(shù)據(jù)分組的條件下能夠減少能量消耗，同時可以增加網(wǎng)絡(luò)的吞吐量。Cao等[21]提出了一種隨機(jī)的網(wǎng)絡(luò)編碼算法，不僅可以提高網(wǎng)絡(luò)的吞吐量和頑健性，還可以提高可靠性和安全性[22]。進(jìn)一步，如果將網(wǎng)絡(luò)編碼應(yīng)用在無線網(wǎng)絡(luò)中還可以增加無線網(wǎng)絡(luò)的帶寬，降低時延，改善能源效率和減少干擾[23]。

在WSN中，實(shí)時、可靠、高效的鏈路質(zhì)量對于上層協(xié)議的正確和高效率的運(yùn)轉(zhuǎn)至關(guān)重要。性能優(yōu)越的鏈路能夠讓上層的協(xié)議以最優(yōu)化的方式和效率執(zhí)行，通過事先預(yù)測鏈路質(zhì)量來確定是否需要強(qiáng)制性將部分流量引入到質(zhì)量較好的鏈路上，從而提高M(jìn)AC協(xié)議性能，包括網(wǎng)絡(luò)編碼率、吞吐量以及信道利用率。

本文研究了無線傳感器網(wǎng)絡(luò)中的MAC協(xié)議，給出了一種新的基于路徑優(yōu)化和網(wǎng)絡(luò)編碼的MAC機(jī)制。本文的主要貢獻(xiàn)包括：1) 在EasiLQE的基礎(chǔ)上給出了基于自適應(yīng)窗口的改進(jìn)EF濾波器的鏈路質(zhì)量估計(jì)方法；2) 在改進(jìn)的鏈路優(yōu)化方法上提出了一種新的MAC協(xié)議，并分析了MAC機(jī)制中最優(yōu)的階數(shù)，為在編碼機(jī)會和能量效率上尋求到一個較為合適的平衡點(diǎn)。

2 基于窗口自適應(yīng)的鏈路質(zhì)量預(yù)測方法

窗口平均指數(shù)加權(quán)移動平均估計(jì)（WMEWMA）[24]是基于軟件的質(zhì)量估計(jì)方法，這種方法穩(wěn)定性較高。2012年，黃庭培等[25]提出了一種突發(fā)性鏈路感知的鏈路估計(jì)方法EasiLQE，綜合了基于硬件的估計(jì)和基于軟件的估計(jì)2種方法，采用長周期和短周期2種主動探測方式以及和EF濾波估計(jì)相結(jié)合的方法，實(shí)現(xiàn)了在較為復(fù)雜的網(wǎng)絡(luò)環(huán)境中對鏈路質(zhì)量的估計(jì)。但是EasiLQE仍然可以進(jìn)一步改進(jìn)，因?yàn)楫?dāng)接收信號強(qiáng)度指示RSSI（received signal strength indication）低于某一閾值時，網(wǎng)絡(luò)處于不穩(wěn)定狀態(tài)，所以在這個閾值條件下，EasiLQE使用了短周期的主動探測方法。但是如果較長時間處于較低值時，頻繁的主動探測不僅有可能帶來預(yù)測誤差的增大，并且會增加網(wǎng)絡(luò)負(fù)載，消耗網(wǎng)絡(luò)資源。本文在此基礎(chǔ)上，改進(jìn)了探測窗口，給出了基于窗口自適應(yīng)的鏈路質(zhì)量估計(jì)方法，減少在長時間低于某一閾值時主動探測的頻率。

2.1 整體架構(gòu)

如圖1所示，改進(jìn)算法的整體架構(gòu)是由鏈路質(zhì)量被動感知、自適應(yīng)窗口探測和鏈路質(zhì)量瞬時探測3個模塊和改進(jìn)的指數(shù)加權(quán)移動平均濾波器EWMA鏈路質(zhì)量估計(jì)模塊4部分構(gòu)成。將被動感知和主動探測合二為一并且結(jié)合了值和值（packet reception ratio）2種信息，在對以上2種信息進(jìn)行處理之后，估計(jì)未來一段時間內(nèi)的鏈路質(zhì)量。和傳統(tǒng)算法一樣，本文同樣采用的估計(jì)值來衡量鏈路的質(zhì)量。

2.2 被動感知

鏈路質(zhì)量被動感知模塊被動地偵聽接收節(jié)點(diǎn)接收到分組的值，并且對接收到的數(shù)據(jù)分組的的數(shù)值進(jìn)行計(jì)算，計(jì)算的變化量。如果要觸發(fā)鏈路質(zhì)量瞬時探測模塊則需要符合下述條件

2.3 主動探測

傳統(tǒng)的WMEWMA鏈路質(zhì)量估計(jì)方法中的探測周期是一個定值，因此對于變化幅度和頻率不大的網(wǎng)絡(luò)條件來說適用性很強(qiáng)。但是在變化頻率較快的網(wǎng)絡(luò)條件下，固定的探測周期很可能導(dǎo)致對某些快速變化的鏈路質(zhì)量的錯誤估計(jì)。雖然EasiLQE在探測模塊中引入了長周期和短周期，這相對于傳統(tǒng)的單一探測周期靈活了很多。但是如果在此基礎(chǔ)上，將探測周期和值相關(guān)聯(lián)，使探測周期由于的變化而進(jìn)行自適應(yīng)調(diào)整，就可使估計(jì)方法的整體性能有所提高。

主動探測包含2個模塊：瞬時鏈路質(zhì)量探測模塊和自適應(yīng)窗口探測模塊。瞬時鏈路質(zhì)量探測模塊是一個快速反應(yīng)模塊，探測周期可以按照不同的網(wǎng)絡(luò)環(huán)境來設(shè)置，當(dāng)網(wǎng)絡(luò)變化較大時，探測周期可以設(shè)置得小一點(diǎn)，這樣可以有更加精確的估計(jì)值，反之則可以設(shè)置得稍微偏大，但由于是快速反應(yīng)模塊，所以這個模塊的探測周期設(shè)置得較小一點(diǎn)是比較適當(dāng)?shù)?。自適應(yīng)窗口探測模塊相對來說探測周期較長，設(shè)置自適應(yīng)窗口探測模塊的目的是讓算法本身根據(jù)網(wǎng)絡(luò)的變化情況來自動調(diào)整下一次地探測時間間隔，在網(wǎng)絡(luò)相對較為穩(wěn)定的時候適當(dāng)?shù)厥固綔y周期延長，反之則使探測周期縮短。自適應(yīng)窗口探測模塊的探測周期記為，計(jì)算如下

2.4 改進(jìn)的EF濾波器鏈路質(zhì)量估計(jì)方法

EF濾波器是黃庭培等2010年提出來的對指數(shù)加權(quán)移動平均濾波器(EWMA，exponentially-weighted moving average)一種改進(jìn)。相對于傳統(tǒng)的EWMA來說，EF濾波器能夠?qū)︽溌返耐话l(fā)性變化做出迅速的反應(yīng)，又能在一定程度上平滑臨時的波動，能夠在保證估計(jì)準(zhǔn)確性的前提條件下獲得較好的實(shí)時性以及穩(wěn)定性。在此基礎(chǔ)上再次做出改進(jìn)，使主動探測窗口能夠隨著值而變化。改進(jìn)方法如下。

EWMA模型的一般表達(dá)式如下

(4)

(6)

聯(lián)立式(3)~式(6)，獲得本方法中利用上一次估計(jì)值和本次實(shí)際測量值來估計(jì)將來一段時間值的方法。具體表示如下

瞬時探測模塊觸發(fā)之后，將獲得的探測值作為下一個周期的估計(jì)值，并不按照上述公式計(jì)算。

在較為穩(wěn)定的網(wǎng)絡(luò)環(huán)境下根據(jù)鏈路質(zhì)量估計(jì)方法的均方差和協(xié)方差2個方面對比分析EasiLQE和本文方法的性能，用估計(jì)值的均方差來說明估計(jì)值準(zhǔn)確性，協(xié)方差來反映鏈路質(zhì)量估計(jì)方法的穩(wěn)定性。經(jīng)過仿真驗(yàn)證，本文方法的在穩(wěn)定網(wǎng)絡(luò)環(huán)境下的穩(wěn)定性提升了10%，在動態(tài)變化的網(wǎng)絡(luò)環(huán)境下準(zhǔn)確性提升了8%。

3 基于路徑優(yōu)化和網(wǎng)絡(luò)編碼的MAC協(xié)議

本文在BEND[19]基礎(chǔ)上利用高階輔助節(jié)點(diǎn)，提出了一個更加廣義的路徑優(yōu)化方案，不僅在由路由算法確定的路由周圍更大程度上擴(kuò)充了實(shí)際傳輸路徑，更進(jìn)一步優(yōu)化了編碼條件并且加入了鏈路質(zhì)量估計(jì)模塊，讓數(shù)據(jù)在擴(kuò)充的路徑中優(yōu)先選擇更好的鏈路來傳輸。但是，實(shí)際傳輸路徑的擴(kuò)展程度不是無限的。當(dāng)階數(shù)到達(dá)一定程度以后，單純地增加階數(shù)已經(jīng)不能再使編碼機(jī)會有明顯的增加。恰恰相反，由于階數(shù)的增加而使節(jié)點(diǎn)上存儲的拓?fù)滏湵磉^于龐大而變得難以使用和維護(hù)。所以本文在敘述完本協(xié)議的設(shè)計(jì)細(xì)節(jié)之后著重討論了最優(yōu)的擴(kuò)展系數(shù)。

3.1 基本思想

基本思想如圖2所示，節(jié)點(diǎn)要向節(jié)點(diǎn)傳輸數(shù)據(jù)分組，同時節(jié)點(diǎn)要向節(jié)點(diǎn)傳輸數(shù)據(jù)分組。節(jié)點(diǎn)和節(jié)點(diǎn)是2個中間節(jié)點(diǎn)。由路由算法確定的從節(jié)點(diǎn)到節(jié)點(diǎn)的傳輸路徑是。同樣由路由算法確定的從節(jié)點(diǎn)到節(jié)點(diǎn)的傳輸路徑是。節(jié)點(diǎn)、、和的廣播范圍互相重合，同樣節(jié)點(diǎn)、、和的廣播范圍也互相重合。實(shí)際上，當(dāng)節(jié)點(diǎn)接收到來自節(jié)點(diǎn)的數(shù)據(jù)分組時，節(jié)點(diǎn)同樣接收到來自節(jié)點(diǎn)的數(shù)據(jù)分組；同樣的道理，當(dāng)節(jié)點(diǎn)接收到來自節(jié)點(diǎn)的數(shù)據(jù)分組時，節(jié)點(diǎn)也同樣接收到來自節(jié)點(diǎn)的數(shù)據(jù)分組。這樣節(jié)點(diǎn)和節(jié)點(diǎn)上同時擁有數(shù)據(jù)分組和數(shù)據(jù)分組。如果能夠利用和的相對位置關(guān)系，讓其中一個節(jié)點(diǎn)發(fā)送編碼后的數(shù)據(jù)分組，那么則可以增加編碼機(jī)會，同時，有可能緩解信道競爭的壓力。由上面定義可知，節(jié)點(diǎn)是節(jié)點(diǎn)的二階輔助節(jié)點(diǎn)，節(jié)點(diǎn)也是節(jié)點(diǎn)的二階輔助節(jié)點(diǎn)。按照這個思想進(jìn)行拓展，引入更高階數(shù)的輔助節(jié)點(diǎn)是有可能的。

由圖3可以看出，實(shí)際上如果一個節(jié)點(diǎn)協(xié)同它的鄰居節(jié)點(diǎn)連續(xù)廣播2次的極限情況是它的廣播半徑變成原來的2倍，則3次廣播的范圍變成原來廣播半徑的3倍，更加高次的協(xié)同廣播半徑以此類推。一般關(guān)系式是。

分析圖3可以看出，如果隨著高階節(jié)點(diǎn)的引入，由于節(jié)點(diǎn)的廣播范圍是一個圓，那么一定存在一個合適的階數(shù)，其廣播范圍與節(jié)點(diǎn)的廣播范圍重合達(dá)到最大。在這種情況下，輔助節(jié)點(diǎn)的階數(shù)已經(jīng)達(dá)到極限。

3.2 協(xié)議設(shè)計(jì)

基于流量集中的編碼協(xié)議強(qiáng)制性地將流量集中在某些特殊節(jié)點(diǎn)上，從而來增加編碼機(jī)會。對于此類協(xié)議，編碼總是發(fā)生在由路由算法確定的路徑交叉節(jié)點(diǎn)上，這樣做雖然可以增加編碼機(jī)會，但是節(jié)點(diǎn)的負(fù)載差異很大。那些數(shù)據(jù)流被強(qiáng)制通過的節(jié)點(diǎn)，尤其是多條路徑的交叉節(jié)點(diǎn)負(fù)載很高，而其鄰居節(jié)點(diǎn)的負(fù)載可能很低。

圖4采用數(shù)據(jù)分散方式，合理利用了節(jié)點(diǎn)的廣播特性，將數(shù)據(jù)分散在路由確定的路徑周圍。因?yàn)檫@樣做一方面能夠有效地進(jìn)行數(shù)據(jù)的分散，不會由于所有的節(jié)點(diǎn)都進(jìn)行轉(zhuǎn)發(fā)從而引起泛洪。本文首先讓更多圍繞在主節(jié)點(diǎn)周圍的鄰居成為輔助節(jié)點(diǎn)，從而將數(shù)據(jù)分散的程度進(jìn)一步擴(kuò)大。然后尋找和編碼率以及吞吐量有重要相關(guān)關(guān)系的那些條件，以及這些條件和輔助節(jié)點(diǎn)階數(shù)以及網(wǎng)絡(luò)性能之間的影響關(guān)系，從而來找到一個較為合適的階數(shù)，而不是隨意并且漫無目的地使用數(shù)據(jù)分散。

當(dāng)節(jié)點(diǎn)接收到一個數(shù)據(jù)，首先判斷是否需要解碼，如果解碼不成功則要求發(fā)送節(jié)點(diǎn)發(fā)送未編碼數(shù)據(jù)，如果解碼成功或者不需要解碼，節(jié)點(diǎn)則判斷自己是主節(jié)點(diǎn)還是輔助節(jié)點(diǎn)，根據(jù)不同的情況將數(shù)據(jù)分組放到相應(yīng)的隊(duì)列或者丟棄。然后節(jié)點(diǎn)對數(shù)據(jù)進(jìn)行編碼條件查詢，判斷編碼條件并對可編碼數(shù)據(jù)分組進(jìn)行編碼。在執(zhí)行這個過程的同時，節(jié)點(diǎn)按照類似EDCF機(jī)制進(jìn)行信道競爭，如果獲得信道的話，按照下文所述的方式產(chǎn)生一個隨機(jī)數(shù)，按照其取值確定發(fā)送編碼分組或者未編碼分組(包含節(jié)點(diǎn)作為主節(jié)點(diǎn)和輔助節(jié)點(diǎn)2種)。

3.2.1 節(jié)點(diǎn)上拓?fù)滏湵?/p>

當(dāng)一個節(jié)點(diǎn)成功接收數(shù)據(jù)之后，首先判斷是將數(shù)據(jù)分組丟棄或者轉(zhuǎn)發(fā)，而節(jié)點(diǎn)做這個判斷所需要用到的信息如圖5所示。協(xié)議中如果要讓節(jié)點(diǎn)有能力判定本身為三階輔助節(jié)點(diǎn)，那么要求節(jié)點(diǎn)本身的拓?fù)湫畔㈡湵碇辽傩枰４鎯杉夃従庸?jié)點(diǎn)地址信息，這個條件是比較容易實(shí)現(xiàn)的。

節(jié)點(diǎn)具體的判斷過程是：當(dāng)節(jié)點(diǎn)接收到數(shù)據(jù)，節(jié)點(diǎn)會從幀頭尋找接收節(jié)點(diǎn)地址(receiver address)、2nd-和3rd-信息。如果節(jié)點(diǎn)是，則此節(jié)點(diǎn)是這個數(shù)據(jù)的主節(jié)點(diǎn)，節(jié)點(diǎn)會將數(shù)據(jù)存儲到本身的主數(shù)據(jù)隊(duì)列中；如果節(jié)點(diǎn)本身不是，則節(jié)點(diǎn)會按照圖6的數(shù)據(jù)結(jié)構(gòu)來判斷自己的鄰居節(jié)點(diǎn)中是否存在2nd-，或者更進(jìn)一步判斷鄰居的鄰居節(jié)點(diǎn)中是否包含3rd-，若是，這個節(jié)點(diǎn)將數(shù)據(jù)存入輔助數(shù)據(jù)隊(duì)列，如果上述3個條件均不滿足，則節(jié)點(diǎn)丟棄此數(shù)據(jù)分組。這就保證了在增加輔助節(jié)點(diǎn)的同時并不會引起泛洪。

在輔助節(jié)點(diǎn)的階數(shù)為3時，節(jié)點(diǎn)上的鄰居信息鏈表是較為簡單的，所以，上述的做法不會引發(fā)復(fù)雜的查找操作，但是當(dāng)隨著輔助節(jié)點(diǎn)的階數(shù)越來越大，節(jié)點(diǎn)上的數(shù)據(jù)結(jié)構(gòu)越來越復(fù)雜，就會使查找操作變得難以執(zhí)行。不僅如此，隨著階數(shù)的增加，冗余的數(shù)據(jù)量也會越來越多，由此引發(fā)的近似于泛洪的廣播變得難以控制，所以尋找合適的階數(shù)范圍是非常必要的工作之一。

3.2.2 數(shù)據(jù)分組的編碼條件以及約簡形式

由于實(shí)際設(shè)置的條件比理論分析時所需要的條件范圍要更加小一點(diǎn)，所以，設(shè)置的條件相對于理論所需是比較嚴(yán)格的。這樣的后果是，編碼條件的嚴(yán)格化會保證編碼數(shù)據(jù)解碼失敗的幾率保持在一個較低水平，但是也會對編碼率有消極的影響。

3.2.3 幀頭的數(shù)據(jù)結(jié)構(gòu)

幀頭結(jié)構(gòu)如圖6所示，表示接收節(jié)點(diǎn)地址(receiver address)；表示發(fā)送節(jié)點(diǎn)地址(transmitter address)；[]表示接收節(jié)點(diǎn)地址列表(receiver address list)，其中包含了被編碼的數(shù)據(jù)分組中不同的原數(shù)據(jù)分組相應(yīng)的接收地址；_[ ]表示數(shù)據(jù)分組列表；__表示被編碼的數(shù)據(jù)分組個數(shù)。

對已編碼的數(shù)據(jù)分組，在節(jié)點(diǎn)接收到以后會進(jìn)行解碼，所以實(shí)際上在任何一個節(jié)點(diǎn)上，轉(zhuǎn)發(fā)判斷和編碼條件判斷都是當(dāng)作未編碼分組來處理的。

在幀頭結(jié)構(gòu)中，和2nd-以及3rd-3個信息構(gòu)成了節(jié)點(diǎn)判斷自己是主節(jié)點(diǎn)、輔助節(jié)點(diǎn)或兩者都不是所依靠的數(shù)據(jù)信息。即節(jié)點(diǎn)依據(jù)、2nd-以及3rd-來判斷自己是否需要對接收的這個數(shù)據(jù)分組進(jìn)行轉(zhuǎn)發(fā)。而節(jié)點(diǎn)編碼操作所需要進(jìn)行的編碼條件則利用和2nd-這2個信息來判斷，因?yàn)閷τ诮邮盏綌?shù)據(jù)的節(jié)點(diǎn)來說，是數(shù)據(jù)分組的上一跳節(jié)點(diǎn)，而2nd-則是下一跳節(jié)點(diǎn)。

3.2.4 數(shù)據(jù)分組傳輸優(yōu)先級以及信道競爭

任何一個數(shù)據(jù)分組在任何一個節(jié)點(diǎn)上都會排隊(duì)，改進(jìn)的主要目標(biāo)之一就是要增加數(shù)據(jù)分組的編碼機(jī)會，讓信道的傳輸效率更高，最大化信道的容量?；谶@個原因，給予編碼數(shù)據(jù)分組更高的傳輸優(yōu)先級。

3.3 模型分析

3.3.1 吞吐量模型分析

為了分析模型，對網(wǎng)絡(luò)傳輸模型作以下假設(shè)。

1) 無線網(wǎng)絡(luò)節(jié)點(diǎn)是完全按照隨機(jī)分布的，也就是基于均勻分布的模型。

5) 每個節(jié)點(diǎn)存在的數(shù)據(jù)分組類型和個數(shù)服從均勻分布，即近似認(rèn)為處于同一組競爭關(guān)系的節(jié)點(diǎn)上的數(shù)據(jù)分組基本相似。

(9)

所以，此時

(11)

由于每個節(jié)點(diǎn)上的數(shù)據(jù)分組是相類似的，則在信道中發(fā)送的數(shù)據(jù)分組度數(shù)的期望值是

(13)

聯(lián)立式(8)~式(13)，得

(15)

因?yàn)楦偁幍墓?jié)點(diǎn)數(shù)和節(jié)點(diǎn)獲得信道的概率成反比，所以，當(dāng)節(jié)點(diǎn)數(shù)增加，信道的吞吐量會降低，最小吞吐量是

3.3.2 最大階數(shù)分析

階數(shù)的增加可能會使網(wǎng)絡(luò)的性能有所提升，但并不是階數(shù)越高網(wǎng)絡(luò)的性能就越好，當(dāng)階數(shù)超過某個值后，性能就會達(dá)到極限，甚至由于冗余數(shù)據(jù)的增加而出現(xiàn)有效吞吐量降低的情況，原因是隨著階數(shù)的增加，能夠納入傳輸路徑的新節(jié)點(diǎn)越來越少；同時，由于節(jié)點(diǎn)位置的變化，新納入的節(jié)點(diǎn)上編碼概率的增加量也會減小，此時編碼率已經(jīng)較為接近極限，那隨之而來的一個問題就是如何在冗余和編碼率之間找到平衡。

如圖8所示，假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)均勻分布，并且一跳節(jié)點(diǎn)距離源節(jié)點(diǎn)的距離較為接近廣播半徑。該假設(shè)中，前者是為了簡化分析過程，后者是為了避免出現(xiàn)數(shù)據(jù)分組經(jīng)過兩跳以后還仍然處在源節(jié)點(diǎn)的廣播范圍之內(nèi)，顯然這種情況是不切合實(shí)際的。如果節(jié)點(diǎn)和節(jié)點(diǎn)之間存在節(jié)點(diǎn)的二階輔助節(jié)點(diǎn)，那么輔助節(jié)點(diǎn)必須遵循一個條件，就是這個輔助節(jié)點(diǎn)必須在以節(jié)點(diǎn)和節(jié)點(diǎn)為圓心的，以廣播半徑為半徑的2個圓的重合面積中，只有這樣才符合文中的二階輔助節(jié)點(diǎn)的定義。同樣，如果節(jié)點(diǎn)和節(jié)點(diǎn)之間存在三階輔助節(jié)點(diǎn)，那么三階輔助節(jié)點(diǎn)一定存在陰影區(qū)域中。所以，如果為網(wǎng)絡(luò)的節(jié)點(diǎn)分布密度，則網(wǎng)絡(luò)中任何一個節(jié)點(diǎn)理論上獨(dú)自占有的面積是。

那么，如果存在高階輔助節(jié)點(diǎn)，則一定有

利用解析幾何的知識，近似得到

(18)

如圖9所示，將均勻分布的節(jié)點(diǎn)抽象為蜂窩形態(tài)，在這種近似中，節(jié)點(diǎn)密度和節(jié)點(diǎn)距離的關(guān)系為

聯(lián)立以上方程，可得

圖9 均勻節(jié)點(diǎn)分布模型

整理式(20)，得

(21)

令

(23)

將式(23)化簡為

解式（24）得

(25)

(27)

從上述分析中本文傾向于認(rèn)為，對于不同參數(shù)的網(wǎng)絡(luò)，包括不同的節(jié)點(diǎn)分布、不同的路由算法以及不同的廣播半徑和不同的數(shù)據(jù)流分布，這些參數(shù)對編碼率和吞吐量的影響都非常明顯，不同的網(wǎng)絡(luò)參數(shù)下會出現(xiàn)不同的最優(yōu)階數(shù)。

3.4 仿真結(jié)果和性能分析

本文實(shí)驗(yàn)是在64 bit Windows操作系統(tǒng)，內(nèi)存4 GB，CPU頻率為3.0 GHz的電腦上運(yùn)行MATLAB7.0仿真軟件進(jìn)行實(shí)驗(yàn)結(jié)果仿真，其仿真參數(shù)設(shè)置和說明如下。

1) 節(jié)點(diǎn)個數(shù)為50個，隨機(jī)分布在100 m′100 m的范圍內(nèi)。

2) 廣播半徑=30 m。

3) 任何實(shí)驗(yàn)都分為數(shù)據(jù)流較稀疏和數(shù)據(jù)流較密集2種情況分析。稀疏場景下考慮不同方向，相互距離較遠(yuǎn)的4對左右節(jié)點(diǎn)進(jìn)行通信，產(chǎn)生數(shù)據(jù)流；密集場景下考慮不同方向，相互距離較遠(yuǎn)的至少10對節(jié)點(diǎn)間通信，產(chǎn)生數(shù)據(jù)流。

4) 數(shù)據(jù)流的設(shè)定對改進(jìn)方法的影響是比較明顯的，文中設(shè)置數(shù)據(jù)流的方式是在節(jié)點(diǎn)中較為均勻的隨機(jī)選擇相互距離較遠(yuǎn)的幾組節(jié)點(diǎn)作為源節(jié)點(diǎn)和目的節(jié)點(diǎn)，并且按照類似最短路徑算法設(shè)定數(shù)據(jù)流路徑。

5) 每種情況下分別對=2、3、4、5進(jìn)行仿真。

6) 每個數(shù)據(jù)分組的長度為2 000 bit，帶寬為1 Mbit/s。

圖10和圖11分別是在不同的流量情況下，階數(shù)=2、3、4、5的編碼率隨時間變化的對比。圖10為數(shù)據(jù)較為密集的情況下編碼率對比曲線，從圖中可以看出，階數(shù)越大，擴(kuò)散速率較大，就能在較短的時間內(nèi)達(dá)到平衡狀態(tài)。隨著階數(shù)的增加，編碼率在階數(shù)從2到5的實(shí)驗(yàn)中基本上呈現(xiàn)上升后穩(wěn)定趨勢，但是在某些情況下，階數(shù)過高時也可能出現(xiàn)編碼率降低，因?yàn)檫^高的階數(shù)將不可避免地引發(fā)過高的冗余，并抵消了編碼增益。相對于=2的情況，編碼率提高最大可以達(dá)到7%。

圖11為數(shù)據(jù)較為稀疏的情況下編碼率對比曲線，同圖10一樣，擴(kuò)散的速率基本上和階數(shù)成正比。隨著階數(shù)的增加，編碼率的總體趨勢與圖12基本類似。相對于=2的情況，編碼率提高最大可以達(dá)到8%。分析原因可知，當(dāng)數(shù)據(jù)流較為稀疏時，數(shù)據(jù)本身存在的編碼可能性較小，兩圖中最高編碼率的差異同樣可以驗(yàn)證這一點(diǎn)。所以，在數(shù)據(jù)本身編碼可能性較小的時候，即使是階數(shù)很高，擴(kuò)散的數(shù)據(jù)仍然只有較小的編碼可能性。甚至由于階數(shù)太高而引發(fā)的冗余數(shù)據(jù)增多而使網(wǎng)絡(luò)的無效負(fù)載增大。但是當(dāng)數(shù)據(jù)流較為密集時，則數(shù)據(jù)流本身的編碼可能性較大，同時這種情況下的最優(yōu)階數(shù)也要比數(shù)據(jù)流稀疏時要高。

圖13是編碼率在2種不同情況下，到達(dá)平衡狀態(tài)時不同階數(shù)的編碼率對比。

圖14是2種情況下，不同階數(shù)的吞吐量對比，從圖中可以看出吞吐量隨著階數(shù)變化關(guān)系基本上和編碼率隨著階數(shù)的變化規(guī)律相一致。從2組圖中可以看出，當(dāng)數(shù)據(jù)流比較稀疏和比較密集的情況下，編碼率的提高程度和網(wǎng)絡(luò)性能達(dá)到平衡態(tài)時的階數(shù)都是不一樣的。在數(shù)據(jù)流較為稀疏時，階數(shù)從2增加到3時編碼率和吞吐量增加比數(shù)據(jù)流密集情況下的增加程度要多。同時，由于數(shù)據(jù)流稀疏時網(wǎng)絡(luò)對數(shù)據(jù)流的編碼機(jī)會本來就小，所以在=3時基本上已經(jīng)接近編碼率上限。但是在數(shù)據(jù)流密集的情況下，由于網(wǎng)絡(luò)對數(shù)據(jù)流編碼率的極限較高，所以，階數(shù)在從3提升到4時，編碼率仍有提升，階數(shù)為4時，編碼率接近上限。值得一提的是，階數(shù)過高時，有效吞吐量可能降低。

能量效率比是指定義某種情況下的能量效率為標(biāo)準(zhǔn)，在此基礎(chǔ)上，其他情況下的能量效率和標(biāo)準(zhǔn)情況求比值，這個比值稱為能量效率比，能量效率比量化傳感器節(jié)點(diǎn)能耗情況，比值越大，則傳感器節(jié)點(diǎn)能量消耗越多，其計(jì)算公式如下

圖12是2種情況下的4種不同階數(shù)的能量效率對比。從圖中容易看出，在數(shù)據(jù)流較為稀疏的情況下，當(dāng)階數(shù)較低時，確實(shí)有一部分節(jié)點(diǎn)處于閑置狀態(tài)，隨著階數(shù)的增加，越來越多的節(jié)點(diǎn)開始進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，所以能量效率降低，當(dāng)階數(shù)上升到3時，幾乎所有節(jié)點(diǎn)都已經(jīng)開始參與數(shù)據(jù)流轉(zhuǎn)發(fā)，所以網(wǎng)絡(luò)的能量消耗進(jìn)入一種平衡態(tài)。但是當(dāng)數(shù)據(jù)流比較均勻且較為密集的時候，只要階數(shù)為2時，基本上大多數(shù)的節(jié)點(diǎn)就已經(jīng)開始參與數(shù)據(jù)流的轉(zhuǎn)發(fā)，所以可以看出，階數(shù)上升到4或者5時，能耗增加不大。由圖11和圖13得到的結(jié)論是：隨著階數(shù)的增加，能量效率的總體趨勢是下降的，但是下降幅度不是很大。

圖15和圖16是在4層節(jié)點(diǎn)拓?fù)湎碌木幋a率和吞吐量仿真曲線。仿真有2個方向的數(shù)據(jù)流，向左向右各2個。由于BEND算法只考慮將鄰居節(jié)點(diǎn)作為輔助節(jié)點(diǎn)來擴(kuò)展路徑，而本文提出的方法則可以將更多的節(jié)點(diǎn)納入路徑中，從而進(jìn)一步擴(kuò)展傳輸路徑，當(dāng)階數(shù)不超過最優(yōu)階數(shù)之前，編碼率和吞吐量都有提升，所以本文只考慮階數(shù)為3時與BEND算法的比較。當(dāng)采用BEND方法時，從圖中可以看出，由于在第一種情況下，所有的數(shù)據(jù)流都被強(qiáng)制通過同一個節(jié)點(diǎn)，所以編碼率能達(dá)到96%。但是當(dāng)同一層的節(jié)點(diǎn)數(shù)增加時，編碼率降低明顯。而由于增加同一層的節(jié)點(diǎn)數(shù)打破了所有數(shù)據(jù)流被強(qiáng)制通過同一個節(jié)點(diǎn)這種瓶頸，雖然編碼率降低了，但是吞吐量卻有十分明顯的上升趨勢。雖然再繼續(xù)增加同一層上的節(jié)點(diǎn)個數(shù)時，編碼率逐漸降低，但是吞吐量卻略有下降。當(dāng)=3時，本文方法的編碼率的變化趨勢和=2時基本一致，但是略有提高。這是由于擴(kuò)展系數(shù)的增加時數(shù)據(jù)分組擴(kuò)散的更加明顯，使編碼機(jī)會有所提升。吞吐量的趨勢也基本保持不變，但是，節(jié)點(diǎn)的個數(shù)越多，兩者的差距越為明顯。在每層的節(jié)點(diǎn)數(shù)都為4的時候，編碼率和吞吐量與BEND[19]方法相比分別提升8%和4%，說明擴(kuò)展系數(shù)的增加能給本文方法帶來良好的效果。

4 結(jié)束語

無線傳感器網(wǎng)絡(luò)的MAC協(xié)議作為整個網(wǎng)絡(luò)體系結(jié)構(gòu)的重要基礎(chǔ)之一，對無線網(wǎng)絡(luò)的性能有十分重大的影響。本文研究了基于路徑優(yōu)化和網(wǎng)絡(luò)編碼的無線傳感器網(wǎng)絡(luò)MAC協(xié)議，并且明確分析階數(shù)，對以后的工作有指導(dǎo)性意義。

首先研究了基于EWMA的鏈路質(zhì)量估計(jì)方法中探測窗口特性，改進(jìn)了主動探測模塊的探測周期，并通過結(jié)合軟件估計(jì)方法和硬件估計(jì)方法，使用了帶有觸發(fā)條件的瞬時主動探測模塊，在較為穩(wěn)定性的網(wǎng)絡(luò)條件下提高了突發(fā)狀況下的反應(yīng)速度和估計(jì)準(zhǔn)確性，同時減小了網(wǎng)絡(luò)開銷。

然后研究了網(wǎng)絡(luò)編碼和路徑優(yōu)化在MAC中的應(yīng)用，合理地利用無線網(wǎng)絡(luò)的廣播特性，通過在節(jié)點(diǎn)周圍增加輔助節(jié)點(diǎn)的方式，將數(shù)據(jù)分散應(yīng)用在MAC中，并且在此基礎(chǔ)上加入了網(wǎng)絡(luò)編碼機(jī)制，從而增加了網(wǎng)絡(luò)中的編碼率和網(wǎng)絡(luò)的吞吐量，同時又不會引發(fā)由流量集中帶來的諸多問題，并提高了傳感器節(jié)點(diǎn)的能量效率。最后分析了過多地增加輔助節(jié)點(diǎn)對網(wǎng)絡(luò)造成的不利影響。

[1] AKYILDIZ I F, SU W L, SANKARASUBRAMANIAM Y, CAYIRCI E. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114.

[2] 李延曉,張?jiān)铝?管樺,等.一種無線傳感器網(wǎng)絡(luò)MAC層能量有效算法[J].西安電子科技大學(xué)學(xué)報,2012,(1):168-171.

LI Y X, ZHANG Y L, GUAN H, et al. Novel low energy consumption MAC protocol for the wireless sensor networks[J]. Journal of Xidian University, 2012, (1): 168-171.

[3] YE W, HEIDEMANN J, ESTRIN D. An energy-efficient MAC protocol for wireless sensor networks[C]//INFOCOM 2002, Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. c2002: 1567-1576.

[4] VAN D T, LANGENDOEN K. An adaptive energy-efficient MAC protocol for wireless sensor networks[C]//The 1st International Conference on Embedded Networked Sensor Systems. ACM, c2003: 171-180.

[5] POLASTRE J,HIL1 J,CULLER D.Versatile low power media access for wireless sensor networks[C]//The 2nd ACM Conference on Embedded Networked Sensor Systems.Baltimore,USA, c2004:95-107.

[6] EL-HOIYDI A, DECOTIGNIE J D. WiseMAC: an ultralow power MAC protocol for the downlink of infrastructure wireless sensor networks[C]//ISCC 2004, Ninth International Symposium. IEEE, c2004: 244-251.

[7] BUETTNER M, YEE G V, ANDERSON E, et al. X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks[C]//The 4th International Conference on Embedded Networked Sensor Systems. ACM, c2006: 307-320.

[8] JAMIESON K, BALAKRISHNAN H, TAY Y C. Sift: A MAC protocol for event-driven wireless sensor networks[C]//Wireless Sensor Networks. Springer Berlin Heidelberg, c2006: 260-275.

[9] LU G, KRISHNAMACHARI B, RAGHAVENDRA C S. An adaptive energy-efficient and low-latency MAC for data gathering in wireless sensor networks[C]//Parallel and Distributed Processing Symposium. IEEE, c2004:224.

[10] LIU P, TAO Z, NARAYANAN S, et al. CoopMAC: a cooperative MAC for wireless LANs[J]. Selected Areas in Communications, 2007, 25(2): 340-354.

[11] MOH S, YU C, PARK S M, et al. CD-MAC: cooperative diversity MAC for robust communication in wireless ad hoc networks[C]//ICC'07, IEEE International Conference. IEEE, c2007: 3636-3641.

[12] RHEE I, WARRIER A, AIA M, et al. Z-MAC: a hybrid MAC for wireless sensor networks[J]. IEEE/ACM Transactions on Networking (TON), 2008, 16(3): 511-524.

[13] HURNI P, BRAUN T. MaxMAC: a maximally traffic-adaptive MAC protocol for wireless sensor networks[C]//Wireless Sensor Networks. Springer Berlin Heidelberg, c2010: 289-305.

[14] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.

[15] FRAGOULI C, LE BOUDEC J Y, WIDMER J. Network coding: an instantprimer[J]. ACM SIGCOMM Computer Communication Review,2006,36 (1): 63-68.

[16] POLYANSKIY Y, POOR H V, VERDú S. Channel coding rate in the finite blocklength regime[J]. IEEE Transactions on Information Theory, 2010, 56(5): 2307-2359.

[17] KATTI S, RAHUL H, HU W, et al. XORs in the air: practical wireless network coding[J].ACM SIGCOMM Computer Communication Review. 2006, 36(4): 243-254.

[18] NI B, SANTHAPURI N, ZHONG Z, et al. Routing with opportunistically coded exchanges in wireless mesh networks[C]//Wireless Mesh Networks,WiMesh 2006, 2nd IEEE Workshop on IEEE.c2006:157-159.

[19] ZHANG J, CHEN Y P, MARSIC I. MAC-layer proactive mixing for network coding in multi-hop wireless networks[J]. Computer Networks,2010, 54(2): 196-207.

[20] LE J, LUI J C S, CHIU D M. DCAR: distributed coding-aware routing in wireless networks[J]. IEEE Transactions on Mobile Computing, 2010, 9(4): 596-608.

[21] CAO C,GONG P,CHOU L. Random network coding based the effective wireless MAC protocol[C]//2013 IEEE 4th International Conference on Software Engineering and Service Science. Beijing, China, c2013:393-396.

[22] YI T M, YANG C C, CHEN J Y. Performance evaluation of cross-layer QoS framework for WiMAXMesh networks[J]. JCIT, c2012,7(1): 180-187.

[23] LING Y T, YI B S, WU J B. A novel access selection scheme in heterogeneous wireless environments[J]. IJACT, 2012, 4(1): 24-32.

[24] WOO A. CULLER D. Evaluation of Efficient Link Reliability Estimators for Low-power Wireless Networks[R]. Technical Report UCB/CSD-03-1270, EECS Department, University of California, Berkeley, 2003.

[25] 黃庭培,李棟,張招亮,等. 突發(fā)性鏈路感知的自適應(yīng)鏈路質(zhì)量估計(jì)方法[J].通信學(xué)報, 2012, 33(6):30-39.

HUANG T P, LI D, ZHANG Z L, et al. Bursty-link-awane adaptive link quality estimation method[J]. Journal on Communications, 2012, 33(6): 30-39.

MAC mechanism based on link prediction and network coding

SHANG Feng-jun, GONG Wen-juan, GENG Zhe

(College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

A MAC mechanism was proposed based on network coding and link prediction for wireless sensor network. Firstly, an adaptive-window scheme was given based on EasiLQE which uses improved EWMA link quality estimation method and combines the methods of hardware and software, so the accuracy is increased.As a result of the instantaneous active detection, reaction rate became more rapid when unexpected situation was occurring in the network. Secondly, a MAC protocol was improved based on the existing MAC protocol. In the protocol improved, high-level secondary nodes around the path determined is increased by the routing module using the broadcast nature of wireless networks that already exists rationally, so that significantly increased the network coding opportunity, without many problems caused by the concentrating flows. Finally, to seek a more appropriate balance between data diffusion and coding opportunities, the optimal factor was discussed. Experiment results show that this improved MAC protocol can increase network throughput and balance the load of the whole network effectively by using over-heard of nodes rationally, without causing concentrating flows at the same time.

link quality estimation, network coding, path optimization, optimal factor

TP393

A

10.11959/j.issn.1000-436x.2016003

2014-12-21；

2015-11-02

重慶市自然科學(xué)基金資助項(xiàng)目（No.cstc2012jjA40038）；重慶市基礎(chǔ)與前沿研究計(jì)劃基金資助項(xiàng)目（No.cstc2013jcyjA40023）；工信部物聯(lián)網(wǎng)發(fā)展專項(xiàng)基金資助項(xiàng)目（工信部科[2012]583）；重慶市青年科技人才培養(yǎng)基金資助項(xiàng)目（No.cstc2014kjrc-qnrc40002）

The Natural Science Foundation of Chongqing (No.cstc2012jjA40038), Chongqing Basic and Frontier Research Project(cstc2013jcyjA40023), The Ministry of Industry and Information Technology for the Special Funds of Development of the Internet of Things(No.[2012]583), The Special Foundation for Young Scientists of Chongqing (No.cstc2014kjrc-qnrc40002)

尚鳳軍（1972-），男，內(nèi)蒙古寧城人，博士，重慶郵電大學(xué)教授、碩士生導(dǎo)師，主要研究方向?yàn)槲锫?lián)網(wǎng)、云計(jì)算和新一代互聯(lián)網(wǎng)。

龔文娟（1990-），女，四川遂寧人，重慶郵電大學(xué)碩士生，主要研究方向?yàn)樾乱淮ヂ?lián)網(wǎng)、軟件定義網(wǎng)絡(luò)。

耿哲（1987-），男，河北石家莊人，重慶郵電大學(xué)碩士生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。