基于Quorum的低占空比WSNs最優(yōu)延遲可靠路由算法

張長森 胡宇鵬 陳鵬鵬

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)

?

基于Quorum的低占空比WSNs最優(yōu)延遲可靠路由算法

張長森 胡宇鵬 陳鵬鵬

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)

在無線傳感器網(wǎng)絡(luò)中，異步低占空比技術(shù)可以極大地降低能耗，但是由于節(jié)點(diǎn)的低占空比喚醒會造成極大的端到端數(shù)據(jù)時延。針對這個問題提出一種基于Quorum的異步自適應(yīng)低占空比路由算法ORDA(Optimal-Reliable delay routing algorithm for low duty cycle WSNs based on Quorum)，將異步占空比網(wǎng)絡(luò)和實(shí)際鏈路模型相結(jié)合，在異步占空比網(wǎng)絡(luò)中節(jié)點(diǎn)在不同時刻的鄰居發(fā)現(xiàn)延遲也在不斷變化。首先為每個節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)負(fù)載選擇自身的Quorum類型，并利用Quorum特性來計(jì)算鄰居節(jié)點(diǎn)的重疊時隙個數(shù)；然后根據(jù)鏈路質(zhì)量進(jìn)一步計(jì)算出這一跳范圍內(nèi)鄰居節(jié)點(diǎn)間的成功轉(zhuǎn)發(fā)預(yù)期值，并在即將喚醒的節(jié)點(diǎn)中選擇更可靠的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。仿真實(shí)驗(yàn)證明，該算法不僅能夠降低端到端延遲，而且能獲得很好的轉(zhuǎn)發(fā)成功率。

無線傳感器網(wǎng)絡(luò) 低占空比 延遲 Quorum 鏈路質(zhì)量

0 引 言

無線傳感器網(wǎng)絡(luò)WSN綜合了無線通信技術(shù)、傳感器技術(shù)、嵌入式技術(shù)和分布式信息處理技術(shù)，是目前國際上前沿?zé)狳c(diǎn)研究領(lǐng)域。在WSN中，傳感器節(jié)點(diǎn)往往由于體積小、能量有限以及在實(shí)際應(yīng)用過程中的環(huán)境因素等影響而不易更換電池，因此能量是WSN中的珍貴資源。低占空比WSN能夠高效地減少節(jié)點(diǎn)的能耗，可擴(kuò)展性強(qiáng)，而且容易實(shí)現(xiàn)。然而低占空比會導(dǎo)致很嚴(yán)重的鄰居發(fā)現(xiàn)延遲[1]。

占空比是無線傳感器網(wǎng)絡(luò)中一種節(jié)省能量的技術(shù)。在低占空比網(wǎng)絡(luò)中，節(jié)點(diǎn)保持喚醒很短一段時間，其余大部分時間都處于休眠狀態(tài)。在異步占空比無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的低占空比喚醒將導(dǎo)致鄰居發(fā)現(xiàn)延遲隨時間的改變而改變，即在不同時刻兩個鄰居節(jié)點(diǎn)間的發(fā)現(xiàn)延遲是時變的[2,3]。

在WSNs中，多跳數(shù)據(jù)路由已經(jīng)受到越來越多的關(guān)注，很多不同的路由算法被設(shè)計(jì)用來優(yōu)化WSNs網(wǎng)絡(luò)的性能。例如基于地理位置的路由GPSR中[4]，節(jié)點(diǎn)知道自己的地理位置，數(shù)據(jù)包發(fā)送時節(jié)點(diǎn)選擇距離最遠(yuǎn)的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)，以此來達(dá)到最小跳數(shù)傳輸。文獻(xiàn)[5]提出的ExOR能夠在很大程度上提高數(shù)據(jù)包轉(zhuǎn)發(fā)率，但是由于其以全網(wǎng)鏈路狀態(tài)為基礎(chǔ)，因此網(wǎng)絡(luò)中每個節(jié)點(diǎn)需要定期向全網(wǎng)廣播自己鄰接鏈路的ETX值，帶來較大的網(wǎng)絡(luò)負(fù)擔(dān)。這幾種方法都是在假定一跳的傳輸延遲是靜態(tài)固定的，對于低占空比無線傳感器網(wǎng)絡(luò)是不適用的[6]。

在另外的一些路由協(xié)議中，路由路徑是隨時間改變的。文獻(xiàn)[7]介紹了一種動態(tài)路由機(jī)制DSF，綜合考慮了包發(fā)送率、端到端時延和能量消耗。雖然表現(xiàn)出了良好的性能，但是工作在同步占空比下，需要消耗大量能量來用于節(jié)點(diǎn)的時鐘同步。文獻(xiàn)[8]中提出的DESS算法是基于鏈路質(zhì)量較好的網(wǎng)絡(luò)，為了減少數(shù)據(jù)包傳輸延遲，每次重傳都是選擇最早醒來的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。其不足之處在于WSN中鏈路質(zhì)量往往是不穩(wěn)定的，因此最先醒來的節(jié)點(diǎn)可能是鏈路質(zhì)量差的節(jié)點(diǎn)。

在本文之前的工作中，提出一種非對稱Quorum的鄰居發(fā)現(xiàn)機(jī)制。實(shí)驗(yàn)表明，Quorum-based協(xié)議是最適合用于解決異步、自適應(yīng)WSN的協(xié)議。因此本文利用基于Grid Quorum的方法，設(shè)計(jì)一種在異步占空比WSN網(wǎng)絡(luò)中的最優(yōu)可靠延遲路由算法ORDA。該算法能夠解決以上文獻(xiàn)中提出的路由算法中存在的諸多缺陷。采用Quorum機(jī)制可以在保證網(wǎng)絡(luò)連通性的前提下使節(jié)點(diǎn)能夠根據(jù)之前的網(wǎng)絡(luò)負(fù)載來自適應(yīng)選擇不同的Quorum喚醒時隙，以此來減少信息量少的節(jié)點(diǎn)的喚醒時隙數(shù)；在異步占空比網(wǎng)絡(luò)中，可以避免全網(wǎng)節(jié)點(diǎn)時間同步所帶來的能耗；在選擇下一跳節(jié)點(diǎn)時綜合考慮了鄰居發(fā)現(xiàn)延遲和數(shù)據(jù)發(fā)送成功轉(zhuǎn)發(fā)預(yù)期(鏈路質(zhì)量)。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

假設(shè)網(wǎng)絡(luò)中有N個同構(gòu)的傳感器節(jié)點(diǎn)，傳感器節(jié)點(diǎn)分為兩種類型：簇首和簇成員節(jié)點(diǎn)。每個節(jié)點(diǎn)都有兩種狀態(tài)：活躍和休眠狀態(tài)。當(dāng)一個節(jié)點(diǎn)處于活躍狀態(tài)時，它可以感知周圍的環(huán)境、接收和發(fā)送數(shù)據(jù)包。當(dāng)一個節(jié)點(diǎn)處于休眠狀態(tài)時，會把除了用于喚醒的計(jì)時器之外的所有功能模塊全部關(guān)閉[9]。一個節(jié)點(diǎn)只有在處于喚醒狀態(tài)時才能接收數(shù)據(jù)包。所有節(jié)點(diǎn)之間不需要時間同步，同時具有一定的數(shù)據(jù)緩存能力。

網(wǎng)絡(luò)規(guī)模足夠大，而且密度較高，區(qū)域沒有邊界效應(yīng)；除sink節(jié)點(diǎn)外所有節(jié)點(diǎn)均同構(gòu)；節(jié)點(diǎn)具有位置感知模塊，能夠感知自身的相對位置信息；數(shù)據(jù)突發(fā)性較強(qiáng)，數(shù)據(jù)流量不高，發(fā)生碰撞概率不大；數(shù)據(jù)包長度較小，因而忽略傳播時延和處理時延。

1.2 Grid Quorum機(jī)制

本文選擇文獻(xiàn)[10]中提出的基于質(zhì)數(shù)網(wǎng)格的Quorum能量節(jié)省模型，Quorum分為兩種：A-Quorum和S-Quorum。假定網(wǎng)絡(luò)中所有節(jié)點(diǎn)會根據(jù)網(wǎng)絡(luò)的擁塞情況、通信量和時延要求等自適應(yīng)地選擇不同的Quorum類型，以此來實(shí)現(xiàn)非對稱性。

2 最優(yōu)延遲可靠路由算法

在異步低占空比無線傳感器網(wǎng)絡(luò)中，兩個節(jié)點(diǎn)間的鄰居發(fā)現(xiàn)延遲是隨時間改變而改變的。本文采用文獻(xiàn)[13]中的方法計(jì)算動態(tài)的鄰居發(fā)現(xiàn)延遲。最優(yōu)延遲可靠路由算法ORDA分為三個過程：鄰居發(fā)現(xiàn)、計(jì)算重疊時隙和成功轉(zhuǎn)發(fā)預(yù)期值。

2.1 鄰居發(fā)現(xiàn)

假定網(wǎng)格不采用時間同步，根據(jù)網(wǎng)絡(luò)模型可知，簇首節(jié)點(diǎn)之間、簇首節(jié)點(diǎn)與成員節(jié)點(diǎn)必須保證能夠鄰居發(fā)現(xiàn)，而成員節(jié)點(diǎn)之間則不必相互發(fā)現(xiàn)。在文獻(xiàn)[12]中已經(jīng)證明在質(zhì)數(shù)Quorum中任意兩個節(jié)點(diǎn)無論是分別采用A-Quorum和S-Quorum，還是均采用S-Quorum，在有限個時隙內(nèi)一定能夠完成鄰居發(fā)現(xiàn)，如圖1所示[11]。

圖1 鄰居發(fā)現(xiàn)示意圖

(1)

(2)

其中，Ti和Tj分別為節(jié)點(diǎn)i和j的時隙長度。

2.2 計(jì)算重疊時隙

在本文中，網(wǎng)絡(luò)中的節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)負(fù)載自適應(yīng)選擇Quorum類型。當(dāng)節(jié)點(diǎn)檢測到網(wǎng)絡(luò)負(fù)載較大，超過預(yù)先設(shè)置的一個閾值時，表示節(jié)點(diǎn)目前的通信量較大，因此采用S-Quorum選擇喚醒工作時隙；否則節(jié)點(diǎn)采用A-Quorum選擇喚醒工作時隙。

在每輪的初始階段中，每個節(jié)點(diǎn)更新自身的鄰居節(jié)點(diǎn)集和鄰居節(jié)點(diǎn)喚醒時隙集，然后計(jì)算鄰居節(jié)點(diǎn)集中的所有鄰居節(jié)點(diǎn)與自身節(jié)點(diǎn)在一個周期內(nèi)的重疊時隙個數(shù)。

節(jié)點(diǎn)A與節(jié)點(diǎn)B1、B2的重疊時隙個數(shù)計(jì)算過程如下：

圖2 節(jié)點(diǎn)的喚醒時隙圖

由圖2可知，節(jié)點(diǎn)A的喚醒時隙是{0，1，2，4，7}，節(jié)點(diǎn)B1的喚醒時隙為{0，3，6}，節(jié)點(diǎn)B2的喚醒時隙是{1,4,6,7,8}。

節(jié)點(diǎn)B1在開始階段向節(jié)點(diǎn)A發(fā)送一個消息數(shù)據(jù)包，包含節(jié)點(diǎn)B1的喚醒時隙{0，3，6}。節(jié)點(diǎn)A接收消息數(shù)據(jù)包后，可知節(jié)點(diǎn)A和B1的重疊時隙只有一個:{0}。同理，節(jié)點(diǎn)A和B2的重疊喚醒時隙有三個：{1，4，7}。

2.3 最優(yōu)延遲可靠路由選擇

本文提出的最優(yōu)延遲可靠路由算法中，算法包含兩部分，分別為鄰居發(fā)現(xiàn)時延和成功轉(zhuǎn)發(fā)預(yù)期值。當(dāng)發(fā)送節(jié)點(diǎn)在有數(shù)據(jù)需要發(fā)送時，首先計(jì)算在該時刻所有鄰居節(jié)點(diǎn)中比發(fā)送節(jié)點(diǎn)等級更低的節(jié)點(diǎn)作為候選轉(zhuǎn)發(fā)節(jié)點(diǎn)，根據(jù)喚醒的先后和在一個周期內(nèi)成功轉(zhuǎn)發(fā)預(yù)期值來選擇出最終轉(zhuǎn)發(fā)節(jié)點(diǎn)。

2.3.1 在一個周期內(nèi)能夠成功轉(zhuǎn)發(fā)的預(yù)期值

在WSNs中，無線鏈路的一跳傳輸是不可靠的。因此在尋找最短鏈路時間路徑時必須考慮一跳傳輸失敗的情況，一旦發(fā)送失敗，發(fā)送節(jié)點(diǎn)則需要等到兩個節(jié)點(diǎn)的下一個重疊時隙內(nèi)才能繼續(xù)發(fā)送數(shù)據(jù)。若兩個節(jié)點(diǎn)在一個周期內(nèi)只有一個重疊時隙，則需要等待一整個周期之后才能再次發(fā)送；即使兩個節(jié)點(diǎn)有多個重疊時隙，若重疊時隙間隔較大，同樣會造成較大的延遲。為了解決這個問題，本文根據(jù)兩個節(jié)點(diǎn)之間的重疊時隙個數(shù)和無線鏈路質(zhì)量，提出一個周期內(nèi)兩個節(jié)點(diǎn)成功轉(zhuǎn)發(fā)預(yù)期值Ei,j，用來表示在鏈路(i,j)上，節(jié)點(diǎn)i成功將數(shù)據(jù)發(fā)送給節(jié)點(diǎn)j的預(yù)期。成功轉(zhuǎn)發(fā)預(yù)期值就是兩個節(jié)點(diǎn)在一個周期內(nèi)轉(zhuǎn)發(fā)數(shù)據(jù)的所有可能情況之和，預(yù)期值越大，表明在一個周期內(nèi)能夠重傳的次數(shù)越多，能夠成功轉(zhuǎn)發(fā)的可能性越大。

(3)

則節(jié)點(diǎn)A在一個周期內(nèi)能夠成功轉(zhuǎn)發(fā)的期望延遲為EA,B：

(4)

根據(jù)以上公式可以看出，兩個節(jié)點(diǎn)間的成功轉(zhuǎn)發(fā)預(yù)期值既考慮到了兩個節(jié)點(diǎn)間的重疊時隙個數(shù)，即兩個節(jié)點(diǎn)間能夠轉(zhuǎn)發(fā)數(shù)據(jù)的時隙數(shù)，又考慮到了兩個節(jié)點(diǎn)間的鏈路質(zhì)量。因而對于網(wǎng)絡(luò)鏈路質(zhì)量低的網(wǎng)絡(luò)，能夠在降低傳輸延遲的同時選擇更可靠的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。

舉例說明：

例如簇首節(jié)點(diǎn)A和B2、成員節(jié)點(diǎn)B1分別采用圖2中(a)、(b)、(c)中的喚醒時隙。由2.2節(jié)可知，節(jié)點(diǎn)A和B1在一個周期內(nèi)的重疊時隙有{0}，節(jié)點(diǎn)A和B2在一個周期中有重疊時隙{1，4，7}。節(jié)點(diǎn)A和B1、B2之間的鏈路質(zhì)量分別為P1和P2。

因此節(jié)點(diǎn)A在一個周期內(nèi)成功向節(jié)點(diǎn)B2發(fā)送數(shù)據(jù)的成功轉(zhuǎn)發(fā)的期望為EA,B2：

2.3.2 最優(yōu)延遲可靠路由選擇

在最優(yōu)延遲可靠路由(ORDA)選擇中，所有傳感器節(jié)點(diǎn)都維護(hù)兩個關(guān)于鄰居節(jié)點(diǎn)的集合，即鄰居節(jié)點(diǎn)集Ni和鄰居節(jié)點(diǎn)喚醒時隙集NWi。用2.1節(jié)中的方法將無線傳感器網(wǎng)絡(luò)構(gòu)建為一個有向圖G=(V,E,C)。在全網(wǎng)初始階段，?(i,j)∈E，計(jì)算在t0時刻C={Δi,j(t0)|(i,j)∈E}。

節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集Ni和鄰居節(jié)點(diǎn)喚醒時隙集NWi更新過程如下：

在網(wǎng)絡(luò)初始化階段，每個節(jié)點(diǎn)在網(wǎng)絡(luò)運(yùn)行前根據(jù)網(wǎng)絡(luò)負(fù)載自適應(yīng)地在一個n×n的Quorum中選擇自己在本輪運(yùn)行中的喚醒時隙Wi。包含sink節(jié)點(diǎn)在內(nèi)的所有節(jié)點(diǎn)將自身的節(jié)點(diǎn)等級設(shè)置為0，sink節(jié)點(diǎn)在一跳范圍內(nèi)發(fā)送一個節(jié)點(diǎn)等級數(shù)據(jù)包，包含一個節(jié)點(diǎn)等級Node Level=1、發(fā)送節(jié)點(diǎn)ID和發(fā)送節(jié)點(diǎn)的喚醒時隙集Wsink。一跳范圍內(nèi)的所有節(jié)點(diǎn)ni接收到等級數(shù)據(jù)包后，根據(jù)數(shù)據(jù)包中的Node Level來更新自身的節(jié)點(diǎn)等級。將sink的ID和喚醒時隙集Wsink分別加入節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)集Ni和鄰居節(jié)點(diǎn)喚醒時隙集NWi中，然后將節(jié)點(diǎn)等級Node Level加1，以及節(jié)點(diǎn)ni的ID和喚醒時隙集Wi替換數(shù)據(jù)包中原有的信息，并在一跳范圍內(nèi)轉(zhuǎn)發(fā)出去。

若一個節(jié)點(diǎn)ni接收到多個數(shù)據(jù)包時，將所有數(shù)據(jù)包中最小的節(jié)點(diǎn)等級Node Level設(shè)置為自身的等級，并按照以上過程更新自身信息。對于其他接收到的數(shù)據(jù)包，若發(fā)送節(jié)點(diǎn)ID沒有在鄰居節(jié)點(diǎn)集中，則節(jié)點(diǎn)僅將發(fā)送節(jié)點(diǎn)ID和發(fā)送節(jié)點(diǎn)喚醒時隙集分別加入自身的鄰居節(jié)點(diǎn)集Ni和鄰居節(jié)點(diǎn)喚醒時隙集NWi；否則，節(jié)點(diǎn)ni丟棄該數(shù)據(jù)包，以此來避免數(shù)據(jù)包重復(fù)發(fā)送。

最優(yōu)延遲可靠路由選擇過程：

根據(jù)鄰居節(jié)點(diǎn)喚醒時隙集NWi中候選轉(zhuǎn)發(fā)節(jié)點(diǎn)與發(fā)送節(jié)點(diǎn)ni的重疊時隙個數(shù)和時隙標(biāo)號，利用2.3.1節(jié)中介紹的成功轉(zhuǎn)發(fā)期望來計(jì)算在一個周期內(nèi)節(jié)點(diǎn)能夠成功轉(zhuǎn)發(fā)的期望，假設(shè)為Ei,j、Ei,a和Ei,s。成功轉(zhuǎn)發(fā)預(yù)期值E越大，表示根據(jù)兩個節(jié)點(diǎn)間的鏈路質(zhì)量，在一個周期當(dāng)中可以轉(zhuǎn)發(fā)的次數(shù)越多，能夠成功轉(zhuǎn)發(fā)的可靠性更高。

Input:Ni,NWi

Output:CNi

Forj=1 tondo

ifnj∈Nithen

if NodeLevel(nj) < NodeLevel(ni)

then

CNi←nj

calculateEi,jformnitonjin one period using equation (4)

end if

end if

end for

returnCNj

Input:CNi

Output:the optimal and reliable forwarding node opl

min1←∞

min2←∞

Number1←0

Number2←0

forj=1 tondo

ifnj∈CNithen

Number1←nj

Number2←nj

end if

end if

end for

opl= min{Ei,min1,Ei,min2}

return opl

3 仿真實(shí)驗(yàn)以及性能分析

為了更好地證明ORDA算法對于網(wǎng)絡(luò)性能的提高，在本節(jié)中將對不同規(guī)模下的ORDA的性能和ExOR[5]、DESS[8]的性能進(jìn)行對比分析。實(shí)驗(yàn)參數(shù)如表1所示。每個節(jié)點(diǎn)隨機(jī)地產(chǎn)生數(shù)據(jù)包。實(shí)驗(yàn)采用文獻(xiàn)[14]中的無線損耗模型。在實(shí)驗(yàn)中，端到端延遲是指數(shù)據(jù)包從源節(jié)點(diǎn)發(fā)送到匯聚節(jié)點(diǎn)接收之間的時延。實(shí)驗(yàn)對比了不同參數(shù)下的算法性能，如不同的區(qū)域大小、節(jié)點(diǎn)密度和網(wǎng)絡(luò)鏈路質(zhì)量。仿真結(jié)果為每個實(shí)驗(yàn)在相同的參數(shù)下重復(fù)運(yùn)行10遍。

表1 實(shí)驗(yàn)參數(shù)

圖3給出了在相同的節(jié)點(diǎn)密度、不同網(wǎng)絡(luò)區(qū)域大小下三種算法的平均端到端延遲。算法在矩形區(qū)域邊長從100到300時，網(wǎng)絡(luò)區(qū)域中節(jié)點(diǎn)數(shù)從200個依次增加來保證節(jié)點(diǎn)密度保持一致。從圖3中可以明顯看出，由于區(qū)域大小的增加導(dǎo)致端到端的距離增加，因而算法的端到端延遲隨著區(qū)域的增加而增加，但算法ORDA始終優(yōu)于ExOR和DESS。這是因?yàn)樵谒惴∣RDA中，節(jié)點(diǎn)選擇下一跳中繼節(jié)點(diǎn)時，始終從最先醒來兩個候選鄰居節(jié)點(diǎn)中選擇最終下一跳節(jié)點(diǎn)。這樣在區(qū)域增大的情況下，始終保持最優(yōu)或次優(yōu)的單跳鄰居發(fā)現(xiàn)延遲。

圖3 不同區(qū)域大小下的平均端到端延遲

在圖4中，網(wǎng)絡(luò)的區(qū)域大小保持不變，即200×200，但網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)不斷增加，即網(wǎng)絡(luò)中節(jié)點(diǎn)密度不斷增大。從圖4中可以看出，隨著節(jié)點(diǎn)密度的增加，三種算法的平均端到端延遲不斷降低。ORDA算法在節(jié)點(diǎn)數(shù)為500之前明顯低于其他算法，之后ORDA算法和DESS算法比較接近。這是由于當(dāng)節(jié)點(diǎn)密度小時，ORDA算法中節(jié)點(diǎn)會選擇在一個周期內(nèi)成功轉(zhuǎn)發(fā)預(yù)期值大的作為下一跳，可以在降低每一跳延遲的基礎(chǔ)上保證單跳的傳輸成功率，減少重傳造成的延遲。而隨著節(jié)點(diǎn)密度的增加，節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)增加，可以作為下一跳的中繼節(jié)點(diǎn)增加，即使單次傳輸失敗，重傳造成的延遲不會太大，因而算法DESS漸漸接近ORDA。

圖4 不同節(jié)點(diǎn)密度下的平均端到端延遲

無線網(wǎng)絡(luò)的鏈路質(zhì)量往往不穩(wěn)定，因此對比了算法ORDA、ExOR和DESS在不同的網(wǎng)絡(luò)鏈路質(zhì)量下的時延性能，如圖5所示。明顯可知，算法ORDA在平均鏈路質(zhì)量較低的網(wǎng)絡(luò)中仍能保持遠(yuǎn)優(yōu)于算法ExOR和DESS的端到端延遲。這是由于算法ORDA在選擇中繼節(jié)點(diǎn)時根據(jù)鏈路質(zhì)量和重疊時隙個數(shù)計(jì)算出一個周期內(nèi)兩個節(jié)點(diǎn)能夠成功轉(zhuǎn)發(fā)的預(yù)期值，一直選擇預(yù)期值最大的作為中繼，因而在鏈路質(zhì)量低的網(wǎng)絡(luò)中能夠提高轉(zhuǎn)發(fā)成功率，減少延遲。當(dāng)網(wǎng)絡(luò)的鏈路質(zhì)量超過0.9后，此時網(wǎng)絡(luò)中的單跳轉(zhuǎn)發(fā)成功率很高，因而基于最優(yōu)鏈路的算法DESS更優(yōu)。

圖5 不同網(wǎng)絡(luò)鏈路質(zhì)量下的平均端到端延遲

圖6顯示了隨著節(jié)點(diǎn)數(shù)的增加，三種算法的網(wǎng)絡(luò)生存時間的變化。從整體上比較，算法ODRA和DESS在生存時間上都要低于算法ExOR。這是由于算法ExOR是一種以端到端最短路徑的ETX值為基準(zhǔn)的路由算法。但是仍能看出，算法ORDA的網(wǎng)絡(luò)存活時間仍高于算法DESS。這是由于算法ORDA采用異步低占空比，沒有全網(wǎng)同步所帶來的網(wǎng)絡(luò)負(fù)擔(dān)，而且算法對所有節(jié)點(diǎn)進(jìn)行分級，選擇下一跳中繼節(jié)點(diǎn)時一直從等級小于自身的鄰居節(jié)點(diǎn)中尋找。

圖6 網(wǎng)絡(luò)中不同節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)生存時間

4 結(jié) 語

在無線傳感器網(wǎng)絡(luò)中，最迫切的問題就是怎樣在能量受限的情況下降低時延、提高網(wǎng)絡(luò)傳輸效率等。本文針對異步低占空比WSNs，提出一種基于Quorum的最短延遲路由算法ORDA。根據(jù)Quorum的特性提出一種方法，根據(jù)重疊時隙個數(shù)和鏈路質(zhì)量來計(jì)算數(shù)據(jù)包在一個周期內(nèi)成功轉(zhuǎn)發(fā)的預(yù)期值，以此來選擇可靠性最高的節(jié)點(diǎn)中繼。在減少網(wǎng)絡(luò)傳輸延遲的同時，在數(shù)據(jù)傳輸過程中選擇成功轉(zhuǎn)發(fā)的預(yù)期值最大的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，這樣既減少了網(wǎng)絡(luò)中數(shù)據(jù)包重傳次數(shù)，又提高了節(jié)點(diǎn)間傳輸成功率。實(shí)驗(yàn)結(jié)果分析表明，算法ORDA相比于ExOR，雖然在節(jié)省能耗方面有不足，但是在減少傳輸延遲性能上遠(yuǎn)遠(yuǎn)優(yōu)于ExOR。即使相對于算法DESS，算法ORDA不僅在網(wǎng)絡(luò)延遲上更加高效，而且在鏈路質(zhì)量低的網(wǎng)絡(luò)中擁有更好的時延性能。下一步工作是解決基于Quorum機(jī)制的異步占空比WSNs中的自適應(yīng)問題，使節(jié)點(diǎn)能夠自適應(yīng)地通過改變循環(huán)長度改變自身的占空比，以及如何將其運(yùn)用到多匯聚節(jié)點(diǎn)的網(wǎng)絡(luò)中，使得算法能夠更加節(jié)能、更加切合實(shí)際應(yīng)用場景。

[1] 孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005.

[2] Polastre J,Hill J,Culler D.Versatile low power media access for wireless sensor networks[C]//Proceedings of the 2nd international conference on Embedded networked sensor systems.ACM,2004:95-107.

[3] 段軼,吳小兵，陳貴海.低占空比無線傳感器網(wǎng)絡(luò)中的動態(tài)數(shù)據(jù)傳輸協(xié)議[J].計(jì)算機(jī)研究與發(fā)展,2011,48(S2):145-151.

[4] Karp B,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]//Proceedings of the 6th annual international conference on Mobile computing and networking.ACM,2000:243-254.

[5] Biswas S,Morris R.ExOR:opportunistic multi-hop routing for wireless networks[J].ACM SIGCOMM Computer Communication Review.ACM,2005,35(4):133-144.

[6] 徐丹,陳曉江，黃駿杰，等.基于低占空比的機(jī)會匯聚樹路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,2013,33(12):3394-3397.

[7] Hao J,Zhang B X,Mouftah H T.Routing protocols for duty cycled wireless sensor networks:A survey[J].IEEE Communications Magazine,2012,50(12):116-123.

[8] Lu G,Sadagopan N,Krishnamachari B,et al.Delay efficient sleep scheduling in wireless sensor networks[C]//24th Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE,2005,4:2470-2481.

[9] 王俊美.低占空比無線傳感器網(wǎng)絡(luò)異步鄰居發(fā)現(xiàn)算法研究[J].數(shù)字通信,2013,40(2):36-39.

[10] 陳良銀,顏秉姝,張靖宇,等.移動低占空比傳感網(wǎng)鄰居發(fā)現(xiàn)算法[J].軟件學(xué)報(bào),2014,25(6):1352-1368.

[11] 楊璐.一種基于Quorum系統(tǒng)的異步傳感網(wǎng)局部時間分配算法[J].東南大學(xué)學(xué)報(bào):自然科學(xué)版,2013,43(1):6-11.

[12] 劉微姍,陳曉江，段任，等.DRAD:一種基于異步休眠調(diào)度的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議[J].計(jì)算機(jī)工程與科學(xué),2010,32(11):40-43，51.

[13] Lai S W,Ravindran B.Least-latency routing over time-dependent wireless sensor networks[J].Computers,IEEE Transactions on,2013,62(5):969-983.

[14] 王辛果,張信明,陳國良.時延受限切能量高效的無線傳感網(wǎng)絡(luò)跨曾路由[J].軟件學(xué)報(bào),2011,22(7):1626-1640.

OPTIMAL-RELIABLE DELAY ROUTING ALGORITHM FOR LOW DUTY CYCLE WSNS BASED ON QUORUM

Zhang Changsen Hu Yupeng Chen Pengpeng

(CollegeofComputerSienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)

In wireless sensor networks,asynchronous duty cycle technique can significantly reduce energy consumption.However,a high end-to-end time delay is caused by low-duty-cycle networks.Therefore,an Optimal-Reliable delay routing algorithm for low duty cycle WSNs based on Quorum(ORDA) is proposed to solve the problem.This algorithm combines the asynchronous duty cycle networks with the actual link,and the neighbor discovery delay of each node is constantly changed at different time.Firstly,each node chooses its own quorum type according to the network load and calculates the overlapping time slots numbers of neighbor nodes by the quorum characteristics.Then,the expected value of successful forwarding between neighbor nodes is computed with the link quality,and the more reliable node is chosen as a forwarding node.The simulation experiments show that the algorithm can not only reduce the end-to-end delay,but also obtain a high forwarding success rate.

Wireless sensor network Low duty cycle Delay Quorum link quality

2015-08-04。國家自然科學(xué)基金項(xiàng)目(51174263)；教育部博士點(diǎn)基金項(xiàng)目(20124116120004);省部級項(xiàng)目(142300410144)。張長森，教授，主研領(lǐng)域：礦井監(jiān)控與通信，無線傳感器網(wǎng)絡(luò)。胡宇鵬，碩士生。陳鵬鵬，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2016.11.019