趙 城潘露萍

(浙江工業(yè)大學(xué)信息工程學(xué)院 杭州 310023)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)由具有傳感、數(shù)據(jù)處理和短距離無線通信功能的傳感器節(jié)點組成，已廣泛應(yīng)用于國防軍事、環(huán)境監(jiān)測、生物醫(yī)療、交通管理、搶險救災(zāi)等眾多領(lǐng)域。傳感器節(jié)點通常都由干電池供電，能量和無線通信能力有限，因此如何快速有效又節(jié)能地采集傳感器數(shù)據(jù)，延長網(wǎng)絡(luò)壽命一直是研究的重點。

匯聚樹路由協(xié)議[1](collection tree protocol, CTP)是基于樹狀結(jié)構(gòu)的匯聚協(xié)議，應(yīng)用非常廣泛[2,3]。在CTP協(xié)議下，每個節(jié)點將各自的數(shù)據(jù)上傳給父節(jié)點，最后匯聚到根節(jié)點sink，采用了基于期望傳輸次數(shù)(expected transmissions count, ETX)的距離向量路由算法。傳統(tǒng)的CTP協(xié)議用ETX[4]來衡量鏈路質(zhì)量，雖然計算比較簡便，但在多跳路徑中，ETX的簡單相加往往會與實際鏈路質(zhì)量產(chǎn)生偏差。對CTP這種逐級上傳的多跳網(wǎng)絡(luò)架構(gòu)，用單跳鏈路質(zhì)量的乘積能更好地表示整條上傳路徑的質(zhì)量。

本論文采用節(jié)點到根節(jié)點整條路徑的數(shù)據(jù)包到達率(packet delivery ratio, PDR)來衡量路徑質(zhì)量。本文的主要貢獻如下：

(1) 提出了基于路徑到達率的PDR-CTP協(xié)議，通過計算和仿真表明，同傳統(tǒng)的基于ETX的CTP協(xié)議相比，可以有效提高路徑端到端數(shù)據(jù)傳遞的成功率，另外還可以節(jié)省平均總傳遞次數(shù)和平均延時，節(jié)省能耗，提高網(wǎng)絡(luò)生存時間。

(2) 提出了動態(tài)延時廣播算法，在建樹過程中，通過動態(tài)延遲，使得質(zhì)量好的節(jié)點先行廣播，提高建樹過程的穩(wěn)定性，減少廣播次數(shù)，節(jié)省能耗。

1 相關(guān)工作

在WSN中，無線鏈路質(zhì)量一直是研究的重點[5]，目前比較常用的衡量指標有ETX、packet reception ratio(PRR)[6]、four-bit(4B)[7]、request number of packets (RNP)[8]、window mean with exponentially weighted moving average (WMEWMA)[9]，這些指標各有側(cè)重點，文獻[10]對這些指標進行了詳細的分析和比較。但這些指標都只衡量了2個相鄰節(jié)點的鏈路質(zhì)量，對于多跳路徑質(zhì)量，只是簡單地將這些指標進行線性疊加，顯然這與實際多跳路徑的質(zhì)量不符。因此如何衡量多跳鏈路的質(zhì)量是本文研究的出發(fā)點。

對CTP協(xié)議，目前已有一些相關(guān)研究工作。文獻[11]和文獻[12]分別對傳統(tǒng)CTP協(xié)議的靜態(tài)和動態(tài)性能進行了評價，并分析了原因。文獻[13]提出了多通道匯聚樹概念，在增加相應(yīng)路由開銷的基礎(chǔ)上提高了匯聚樹的穩(wěn)定性，并可以減少數(shù)據(jù)匯聚時間。為了解決網(wǎng)絡(luò)抖動和擁塞，文獻[14]提出用概率來隨機選擇父節(jié)點，雖然能在一定程度上減少廣播開銷，但顯然有很大概率無法選到最佳的父節(jié)點。文獻[15]提出了衡量鏈路質(zhì)量的fuzzy logic indicator(FLI)指標，它將PRR和其動態(tài)方差以及更新時間統(tǒng)一在一起考慮，利用模糊邏輯控制思維來選擇路由節(jié)點，實驗數(shù)據(jù)顯示比原有協(xié)議有所提高。文獻[16]也對路由選擇指標進行了改進，但它們都只考慮了單跳的鏈路質(zhì)量。文獻[17]將PDR和ETX結(jié)合起來，提出了QoF指標，實驗表明該算法減少了匯聚樹的傳輸開銷，并提高了端到端的到達率，但沒有對建樹時的廣播泛濫進行改進。文獻[18]對通信系統(tǒng)時延進行了研究，指出時延能影響通信性能，因此在CTP協(xié)議中設(shè)置合適的時延很有必要。文獻[19]提出了average transmission time(ATT)用最短傳輸時間來代替ETX，平均減少了17.7%的延遲。文獻[20]提出了一種基于度約束最短傳輸樹的多路徑傳輸協(xié)議，使網(wǎng)絡(luò)中每個節(jié)點均有2條互不相關(guān)路徑到達匯聚節(jié)點并且傳輸距離最短，提高了數(shù)據(jù)傳輸可靠性，但以上算法都沒有考慮多跳鏈路的質(zhì)量。

綜上所述，本文提出的基于路徑PDR和動態(tài)廣播延遲策略的CTP協(xié)議對建立高效節(jié)能的匯聚樹路由具有一定的研究意義。

2 基于鏈路PDR的CTP協(xié)議

2.1 傳統(tǒng)CTP存在問題

在多跳路徑中，ETX的簡單相加往往會與實際鏈路質(zhì)量產(chǎn)生偏差，如圖1所示。

圖中，節(jié)點S為網(wǎng)絡(luò)中的根節(jié)點，即數(shù)據(jù)匯聚中心，B、C、D、E為其子節(jié)點。p1、p2、p3、p4、p5為相鄰節(jié)點間數(shù)據(jù)包傳遞成功的幾率，對節(jié)點E，它到根節(jié)點S有兩條路徑，E→D→B→S和E→C→S。在不考慮失敗重傳的情形下，2條路徑端到端傳遞成功幾率PDR為

PDREDBS=p1×p3×p4=0.729

PDRECS=p2×p5=0.54

可得PDREDBS>PDRECS。

但是2條路徑的ETX卻正好相反：

ETXECS=10/9+5/3=30/9

ETXEDBS=10/9+10/9+5/3=25/9

可得ETXEDBS>ETXECS。

可見，在多跳鏈路中，ETX的簡單相加不能很好地表示整條鏈路的質(zhì)量，因此本文采用單跳鏈路質(zhì)量的乘積這一指標，能更好地刻畫整條上傳路徑的質(zhì)量。

2.2 PDR-CTP路由策略

同傳統(tǒng)CTP協(xié)議類似，本文提出的基于路徑PDR的CTP協(xié)議，在新節(jié)點加入?yún)R聚樹時，計算它通過各條備選路徑到達根節(jié)點的到達率，從中選擇PDR最高的路徑。同時為了避免建樹時的廣播泛濫，在建樹時，對PDR較低的節(jié)點進行延遲發(fā)送廣播，以確保PDR高的節(jié)點先發(fā)送廣播，減少廣播泛濫幾率。PDR-CTP建立樹的過程如下：

(1)sink節(jié)點發(fā)起建立匯聚樹通知，向周圍節(jié)點廣播自身信息，PDRs→s=1。

(2)節(jié)點k收到sink節(jié)點的廣播信號后，更新自己到sink節(jié)點的到達率PDRk→s，并根據(jù)PDRk→s設(shè)置一點的延遲Tdelay后，向周圍節(jié)點廣播自身信息PDRk→s。

(3)中間過程，節(jié)點i收到j(luò)發(fā)出的匯聚樹廣播信號后，計算自身到sink節(jié)點的到達率PDRi→s=PDRi→j×PDRj→s。同時檢查是否已有到達sink節(jié)點的路徑，若沒有則選擇節(jié)點j作為自身的父節(jié)點加入?yún)R聚樹。若已經(jīng)存在，則比較新舊PDRi→s大小，若新PDRi→s較小，則忽略該廣播信息，若新PDRi→s較大，則放棄原來的父節(jié)點，選擇j作為自身的父節(jié)點重新加入?yún)R聚樹。并根據(jù)PDRi→j設(shè)置一定的延遲Tdelay后，向周圍節(jié)點廣播自身信息PDRi→s。

(4)重復(fù)過程(3)直到所有節(jié)點都加入?yún)R聚樹。

本協(xié)議關(guān)鍵在于到達率PDR的計算，對一個單跳鏈路i→j，影響PDRi→j主要有以下2點：

(1)i與j之間單個數(shù)據(jù)包的傳遞成功率pij；

(2)重傳上限r(nóng),當(dāng)i與j之間重傳次數(shù)大于r次時，將放棄數(shù)據(jù)包的再次傳遞。

根據(jù)以上2點，可以計算出i與j間總的數(shù)據(jù)包到達率為

PDRi→j=1-(1-pij)r+1

(1)

這樣i到sink節(jié)點總的數(shù)據(jù)包到達率為

PDRi→s=PDRi→(i-1)×PDR(i-1)→(i-2)×…

×PDR(s-1)→s

(2)

2.3 PDR-CTP性能分析

PDR-CTP協(xié)議從到達率PDR著手，將一個多跳路徑的各鏈路質(zhì)量進行相乘，而傳統(tǒng)CTP則是將多條路徑的各鏈路質(zhì)量進行相加。從理論上講，各鏈路質(zhì)量相乘更能體現(xiàn)整條路徑的質(zhì)量優(yōu)劣。

對到達率要求比較高的網(wǎng)絡(luò)，顯然采用路徑PDR作為選擇路徑的指標會更好一點。特別是在鏈路質(zhì)量比較差的LLN網(wǎng)絡(luò)中，選用PDR指標要明顯優(yōu)于ETX指標。

對某個節(jié)點i，它到sink節(jié)點的到達率和ETX分別為PDRi→s、ETXi→s。由于到達率PDR的下降，i節(jié)點信息成功傳遞到根節(jié)點S的幾率下降，失敗之后，節(jié)點i只能重新發(fā)起上傳任務(wù)。這樣節(jié)點i信息成功傳遞到根節(jié)點S，所需要的總傳遞次數(shù)設(shè)為ETXTi→s(expected transmission count in total)可得：

ETXTi→s=ETXi→s/PDRi→s

(3)

對于一條路徑n→(n-1)→…→1，有：

(4)

(5)

(6)

由上式可以看出，ETXTn→1表示了實際的平均傳遞次數(shù)，與ETXn→1存在很大的差異。而在傳統(tǒng)CTP協(xié)議中，ETXTn→1=ETXn→1因此從理論上用此標準往往無法找到數(shù)據(jù)傳遞的最優(yōu)路徑。

ETXT指標不僅衡量了數(shù)據(jù)節(jié)點i到sink節(jié)點所需要的總傳遞次數(shù)，同時也體現(xiàn)了平均能耗和平均時延的大小。

假設(shè)傳輸一次數(shù)據(jù)包的平均時間為T0，可得T0=ts+tp+tt，其中，ts為數(shù)據(jù)包發(fā)送時間，tp為數(shù)據(jù)包處理時間，tt為數(shù)據(jù)包在空中的傳遞時間。

計算可得i節(jié)點到sink節(jié)點路徑的平均時延Ti→s。

Ti→s=ETXTi→s×T0

(7)

同樣可假設(shè)每次送一個數(shù)據(jù)包所需要的平均能耗為E0(實際中質(zhì)量較差的鏈接可能會選擇更高的發(fā)射功率)，可得i節(jié)點到sink節(jié)點路徑的平均能耗Ei→s為

Ei→s=ETXTi→s×E0

(8)

當(dāng)路徑跳數(shù)為1時，ETX評價指標與實際到達率PDR、總傳遞次數(shù)ETXT相符。隨著跳數(shù)的增加，ETX評價指標與實際到達率PDR、總傳遞次數(shù)ETXT將產(chǎn)生偏差，因此選用鏈路總PDR作為指標能更好地體現(xiàn)實際情況，這不僅可以提高總的到達率，還可以減少總的傳遞次數(shù)，節(jié)省能耗。

以圖1為例，若取p1=p2=p3=p4=0.5，p5=0.3，r=3，有：

ETXTEDBS=10/5+10/5+10/5=6

ETXTECS=10/5+10/3=80/15

可得ETXTEDBS>ETXTECS。

PDREDBS=[1-(1-0.5)4]

×[1-(1-0.5)4]

×[1-(1-0.5)4]=0.8239

PDRECS=[1-(1-0.5)4]×[1-(1-0.3)4]

=0.7124

可得PDREDBS>PDRECS。

以節(jié)點E信息成功傳遞到根節(jié)點S為前提，所需要的總傳遞次數(shù)為ETXT，有：

ETXTEDBS=ETXTEDBS/PDREDBS=6/0.8239

=7.282

ETXTECS=ETXTECS/PDRECS=(80/15)/0.7142

=7.486

可得ETXTECS>ETXTEDBS，這表明鏈路E→D→B→S不僅到達率PDR優(yōu)于鏈路E→C→S，而且總傳遞次數(shù)ETXT也要優(yōu)于E→C→S。

另外可得2條路徑的平均時延分別為

TEDBS=ETXTEDBS×T0=7.282T0

TECS=ETXTECS×T0=7.486T0

TEDBS

能耗方面，假設(shè)每次送一個數(shù)據(jù)包所需要的能耗為E0，同樣可得：

EEDBS=EEDBS×T0=7.282E0

EECS=EECS×T0=7.486E0

EEDBS

2.4 建樹過程中時延Tdelay的選擇

在建立匯聚樹的過程中，PDR較小的節(jié)點有可能先接收到建樹的廣播信息，若其先行繼續(xù)向下廣播，很多節(jié)點會以此節(jié)點作為父節(jié)點。而當(dāng)這些節(jié)點接收到PDR較大的節(jié)點發(fā)出的廣播時，這些節(jié)點會更改自身在樹中的結(jié)構(gòu)并再次廣播，這樣就會產(chǎn)生廣播泛濫。因此，如何讓PDR大的節(jié)點先行廣播也是一個很重要的問題。

本文在建樹過程中，采取了一種動態(tài)延遲策略，當(dāng)一個節(jié)點i接收到建樹的廣播信息后，根據(jù)上一跳的鏈路質(zhì)量(ETX)，設(shè)立一個動態(tài)延時值，Tdelay=K(ETX-1)，K為加權(quán)因子。通過延時值的動態(tài)調(diào)整，加大PDR好的節(jié)點先行廣播的幾率，以減少建樹時廣播的泛濫，節(jié)省能耗。

對于一條路徑1→2→…→n, 假設(shè)pij為節(jié)點i與節(jié)點j之間單次傳遞成功的概率，假設(shè)重傳上限為r，可以得到一個數(shù)據(jù)包經(jīng)過k次重傳，從節(jié)點1成功傳到節(jié)點n的概率為P1→n(重傳=k)。

P1→n(重傳=k)

(9)

數(shù)據(jù)包成功從節(jié)點1傳到n的總傳遞次數(shù)為(n-1+k)。可得節(jié)點1傳到n的總傳遞次數(shù)為m的概率P1→n(總=m)為

P1→n(總=m)=P1→n(重傳=m-n+1)

(10)

以圖1為例，節(jié)點E有很大概率先收到C發(fā)出的廣播信息，若直接向下繼續(xù)廣播，會造成廣播泛濫，因此需要設(shè)置延遲，使節(jié)點E接收到D發(fā)出的廣播信息后，再向下廣播。

假設(shè)重傳上限為r=3，每次傳輸處理時間都一致，則數(shù)據(jù)包時延主要取決于重傳遞次數(shù)。

數(shù)據(jù)包從路徑E→D→B→S走時，當(dāng)總傳播次數(shù)為m, 傳遞成功，概率記為PEDBS(總=m)，有:

PEDBS(總=m)=PEDBS(重傳=m-3)，根據(jù)式(7)計算，可得：

PEDBS(總=3)=p1p3p4=0.729

PEDBS(總=4)=[(1-p1)+(1-p3)

+(1-p4)]p1p3p4=0.2187PEDBS(總=5)=0.04374

PEDBS(總=6)=0.005103

PEDBS(總=loss)=0.002997001

數(shù)據(jù)包從路徑E→C→S走時，有:

PECS(總=m)=PECS(重傳=m-2)

PECS(總=2)=p2p5=0.54

PECS(總=3)=0.27

PECS(總=4)=0.1134

PECS(總=5)=0.0108

PECS(總=6)=0.000864

PECS(總=loss)

=0.064936

則E在收到C建樹信息之前進行向下廣播的概率為Pf=P(ECS

P(ECS2)

+PECS(總=3)PEDBS(總>3)

+PECS(總=4)PEDBS(總>4)

+PECS(總=5)PEDBS(總>5)

+PECS(總=6)PEDBS(總>6)

=0.6191

加入動態(tài)延遲后，廣播泛濫概率Pf將減少。

當(dāng)K=2.5時，有：

P(ECS

=PECS(總=2)PEDBS(總>3)

+PECS(總=3)PEDBS(總>4)

+PECS(總=4)PEDBS(總>5)

+PECS(總=5)PEDBS(總>6)

+PECS(總=6)PEDBS(總>7)

=0.13

但同時付出的代價是建樹時延增加了1.11T0。

當(dāng)K=5時，有：

P(ECS

=PECS(總=2)PEDBS(總>4)

+PECS(總=3)PEDBS(總>5)

+PECS(總=4)PEDBS(總>6)

+PECS(總=5)PEDBS(總>7)

+PECS(總=6)PEDBS(總>8)

=0.0265

付出的代價是建樹時延增加了2.22T0。以上結(jié)果見表1。

表1 動態(tài)時延算法結(jié)果

由以上分析可以得出，動態(tài)延遲算法能夠提高PDR大的節(jié)點先行進行廣播的概率，減少建樹期間的廣播數(shù)量，節(jié)省能源。

對于能量受限和負荷過重的節(jié)點i，同樣可以選擇合適的Tdelay，讓剩余能量較高和空閑的節(jié)點承擔(dān)更多的中繼任務(wù)，以提高整個網(wǎng)絡(luò)的生存時間。剩余能量較多的節(jié)點，選擇較小的Tdelay，可以提高被選中做中繼節(jié)點的概率，承擔(dān)更多的任務(wù)。能量剩余較少的節(jié)點，選擇較大的Tdelay，當(dāng)有別的候選路徑時，能避免被選中，同時在沒有備用路徑時，也可以承擔(dān)起中繼任務(wù)。

3 仿真分析

本節(jié)使用OMNET網(wǎng)絡(luò)仿真軟件對本協(xié)議進行了網(wǎng)絡(luò)仿真驗證。網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖2所示，100個節(jié)點均勻分布在100 m×100 m的平地上。使用IEEE802.15.4協(xié)議，傳輸速率為1～35 kbps，傳輸頻段為2 440 MHz。

圖2 仿真網(wǎng)絡(luò)場景

初始時刻，隨機選取圖中任一節(jié)點為根節(jié)點，分別用CTP和PDR-CTP路由協(xié)議進行建樹。圖3是2種路由協(xié)議在不同速率下的建樹時間和廣播開銷。采用PDR-CTP建樹時，延遲參數(shù)K=3。仿真結(jié)果顯示，PDR-CTP協(xié)議的廣播開銷要明顯小于CTP協(xié)議，而且平均建樹時間只增大了20%。

表2 建樹開銷

樹建立后，選取相同的較遠節(jié)點，分別對2種協(xié)議下的節(jié)點到根節(jié)點S的到達率、時延和吞吐率進行了統(tǒng)計平均。圖3、圖4、圖5為仿真結(jié)果?？梢?，利用PDR-CTP協(xié)議建立起的采集樹，其端到端平均到達率PDR，平均時延和吞吐率要明顯好于CTP協(xié)議，這充分說明根據(jù)PDR-CTP協(xié)議建立起的采集樹成功避免了ETX小但整體質(zhì)量不佳的鏈路。

圖3 平均端到端到達率

圖4 平均延時

圖5 平均數(shù)據(jù)吞吐率

4 結(jié) 論

本文提出了一種基于路徑到達率PDR和動態(tài)廣播時延的匯聚樹路由協(xié)議。同傳統(tǒng)的基于ETX的匯聚樹協(xié)議相比，本協(xié)議能更好地刻畫多跳路徑質(zhì)量，有效提高端到端的數(shù)據(jù)到達率，還可以在一定程度上減少總的數(shù)據(jù)傳遞次數(shù)，減少平均時延。另外建樹時的動態(tài)延遲策略可以減少建樹時經(jīng)常發(fā)生的廣播泛濫，節(jié)省建樹開銷。