基于路徑到達(dá)率和動(dòng)態(tài)廣播時(shí)延的匯聚樹協(xié)議①

趙 城潘露萍

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

0 引 言

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

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

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

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

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

1 相關(guān)工作

在WSN中，無線鏈路質(zhì)量一直是研究的重點(diǎn)[5]，目前比較常用的衡量指標(biāo)有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]，這些指標(biāo)各有側(cè)重點(diǎn)，文獻(xiàn)[10]對(duì)這些指標(biāo)進(jìn)行了詳細(xì)的分析和比較。但這些指標(biāo)都只衡量了2個(gè)相鄰節(jié)點(diǎn)的鏈路質(zhì)量，對(duì)于多跳路徑質(zhì)量，只是簡(jiǎn)單地將這些指標(biāo)進(jìn)行線性疊加，顯然這與實(shí)際多跳路徑的質(zhì)量不符。因此如何衡量多跳鏈路的質(zhì)量是本文研究的出發(fā)點(diǎn)。

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

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

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

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

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

圖中，節(jié)點(diǎn)S為網(wǎng)絡(luò)中的根節(jié)點(diǎn)，即數(shù)據(jù)匯聚中心，B、C、D、E為其子節(jié)點(diǎn)。p1、p2、p3、p4、p5為相鄰節(jié)點(diǎn)間數(shù)據(jù)包傳遞成功的幾率，對(duì)節(jié)點(diǎn)E，它到根節(jié)點(diǎn)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的簡(jiǎn)單相加不能很好地表示整條鏈路的質(zhì)量，因此本文采用單跳鏈路質(zhì)量的乘積這一指標(biāo)，能更好地刻畫整條上傳路徑的質(zhì)量。

2.2 PDR-CTP路由策略

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

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

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

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

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

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

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

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

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

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

(1)

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

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

×PDR(s-1)→s

(2)

2.3 PDR-CTP性能分析

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

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

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

ETXTi→s=ETXi→s/PDRi→s

(3)

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

(4)

(5)

(6)

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

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

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

計(jì)算可得i節(jié)點(diǎn)到sink節(jié)點(diǎn)路徑的平均時(shí)延Ti→s。

Ti→s=ETXTi→s×T0

(7)

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

Ei→s=ETXTi→s×E0

(8)

當(dāng)路徑跳數(shù)為1時(shí)，ETX評(píng)價(jià)指標(biāo)與實(shí)際到達(dá)率PDR、總傳遞次數(shù)ETXT相符。隨著跳數(shù)的增加，ETX評(píng)價(jià)指標(biāo)與實(shí)際到達(dá)率PDR、總傳遞次數(shù)ETXT將產(chǎn)生偏差，因此選用鏈路總PDR作為指標(biāo)能更好地體現(xiàn)實(shí)際情況，這不僅可以提高總的到達(dá)率，還可以減少總的傳遞次數(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é)點(diǎn)E信息成功傳遞到根節(jié)點(diǎn)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不僅到達(dá)率PDR優(yōu)于鏈路E→C→S，而且總傳遞次數(shù)ETXT也要優(yōu)于E→C→S。

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

TEDBS=ETXTEDBS×T0=7.282T0

TECS=ETXTECS×T0=7.486T0

TEDBS

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

EEDBS=EEDBS×T0=7.282E0

EECS=EECS×T0=7.486E0

EEDBS

2.4 建樹過程中時(shí)延Tdelay的選擇

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

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

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

P1→n(重傳=k)

(9)

數(shù)據(jù)包成功從節(jié)點(diǎn)1傳到n的總傳遞次數(shù)為(n-1+k)?？傻霉?jié)點(diǎn)1傳到n的總傳遞次數(shù)為m的概率P1→n(總=m)為

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

(10)

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

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

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

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

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走時(shí)，有:

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建樹信息之前進(jìn)行向下廣播的概率為Pf=P(ECS

P(ECS2)

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

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

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

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

=0.6191

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

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

P(ECS

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

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

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

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

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

=0.13

但同時(shí)付出的代價(jià)是建樹時(shí)延增加了1.11T0。

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

P(ECS

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

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

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

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

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

=0.0265

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

表1 動(dòng)態(tài)時(shí)延算法結(jié)果

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

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

3 仿真分析

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

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

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

表2 建樹開銷

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

圖3 平均端到端到達(dá)率

圖4 平均延時(shí)

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

4 結(jié) 論

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