張長森 胡宇鵬 陳鵬鵬

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

?

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

張長森 胡宇鵬 陳鵬鵬

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

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

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

0 引 言

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

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

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

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

在本文之前的工作中，提出一種非對稱Quorum的鄰居發(fā)現(xiàn)機制。實驗表明，Quorum-based協(xié)議是最適合用于解決異步、自適應(yīng)WSN的協(xié)議。因此本文利用基于Grid Quorum的方法，設(shè)計一種在異步占空比WSN網(wǎng)絡(luò)中的最優(yōu)可靠延遲路由算法ORDA。該算法能夠解決以上文獻中提出的路由算法中存在的諸多缺陷。采用Quorum機制可以在保證網(wǎng)絡(luò)連通性的前提下使節(jié)點能夠根據(jù)之前的網(wǎng)絡(luò)負載來自適應(yīng)選擇不同的Quorum喚醒時隙，以此來減少信息量少的節(jié)點的喚醒時隙數(shù)；在異步占空比網(wǎng)絡(luò)中，可以避免全網(wǎng)節(jié)點時間同步所帶來的能耗；在選擇下一跳節(jié)點時綜合考慮了鄰居發(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é)點，傳感器節(jié)點分為兩種類型：簇首和簇成員節(jié)點。每個節(jié)點都有兩種狀態(tài)：活躍和休眠狀態(tài)。當(dāng)一個節(jié)點處于活躍狀態(tài)時，它可以感知周圍的環(huán)境、接收和發(fā)送數(shù)據(jù)包。當(dāng)一個節(jié)點處于休眠狀態(tài)時，會把除了用于喚醒的計時器之外的所有功能模塊全部關(guān)閉[9]。一個節(jié)點只有在處于喚醒狀態(tài)時才能接收數(shù)據(jù)包。所有節(jié)點之間不需要時間同步，同時具有一定的數(shù)據(jù)緩存能力。

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

1.2 Grid Quorum機制

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

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

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

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

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

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

(1)

(2)

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

2.2 計算重疊時隙

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

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

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

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

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

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

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

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

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

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

(3)

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

(4)

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

舉例說明：

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

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

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

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

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

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

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

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

根據(jù)鄰居節(jié)點喚醒時隙集NWi中候選轉(zhuǎn)發(fā)節(jié)點與發(fā)送節(jié)點ni的重疊時隙個數(shù)和時隙標號，利用2.3.1節(jié)中介紹的成功轉(zhuǎn)發(fā)期望來計算在一個周期內(nèi)節(jié)點能夠成功轉(zhuǎn)發(fā)的期望，假設(shè)為Ei,j、Ei,a和Ei,s。成功轉(zhuǎn)發(fā)預(yù)期值E越大，表示根據(jù)兩個節(jié)點間的鏈路質(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 仿真實驗以及性能分析

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

表1 實驗參數(shù)

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

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

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

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

無線網(wǎng)絡(luò)的鏈路質(zhì)量往往不穩(wěn)定，因此對比了算法ORDA、ExOR和DESS在不同的網(wǎng)絡(luò)鏈路質(zhì)量下的時延性能，如圖5所示。明顯可知，算法ORDA在平均鏈路質(zhì)量較低的網(wǎng)絡(luò)中仍能保持遠優(yōu)于算法ExOR和DESS的端到端延遲。這是由于算法ORDA在選擇中繼節(jié)點時根據(jù)鏈路質(zhì)量和重疊時隙個數(shù)計算出一個周期內(nèi)兩個節(jié)點能夠成功轉(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é)點數(shù)的增加，三種算法的網(wǎng)絡(luò)生存時間的變化。從整體上比較，算法ODRA和DESS在生存時間上都要低于算法ExOR。這是由于算法ExOR是一種以端到端最短路徑的ETX值為基準的路由算法。但是仍能看出，算法ORDA的網(wǎng)絡(luò)存活時間仍高于算法DESS。這是由于算法ORDA采用異步低占空比，沒有全網(wǎng)同步所帶來的網(wǎng)絡(luò)負擔(dān)，而且算法對所有節(jié)點進行分級，選擇下一跳中繼節(jié)點時一直從等級小于自身的鄰居節(jié)點中尋找。

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

4 結(jié) 語

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

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

[12] 劉微姍,陳曉江，段任，等.DRAD:一種基于異步休眠調(diào)度的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議[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é)報,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é)基金項目(51174263)；教育部博士點基金項目(20124116120004);省部級項目(142300410144)。張長森，教授，主研領(lǐng)域：礦井監(jiān)控與通信，無線傳感器網(wǎng)絡(luò)。胡宇鵬，碩士生。陳鵬鵬，碩士生。

TP393

A

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