基于Quorum的低占空比WSNs最優延遲可靠路由算法

張長森 胡宇鵬 陳鵬鵬

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

?

基于Quorum的低占空比WSNs最優延遲可靠路由算法

張長森 胡宇鵬 陳鵬鵬

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

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

無線傳感器網絡 低占空比 延遲 Quorum 鏈路質量

0 引 言

無線傳感器網絡WSN綜合了無線通信技術、傳感器技術、嵌入式技術和分布式信息處理技術，是目前國際上前沿熱點研究領域。在WSN中，傳感器節點往往由于體積小、能量有限以及在實際應用過程中的環境因素等影響而不易更換電池，因此能量是WSN中的珍貴資源。低占空比WSN能夠高效地減少節點的能耗，可擴展性強，而且容易實現。然而低占空比會導致很嚴重的鄰居發現延遲[1]。

占空比是無線傳感器網絡中一種節省能量的技術。在低占空比網絡中，節點保持喚醒很短一段時間，其余大部分時間都處于休眠狀態。在異步占空比無線傳感器網絡中，節點的低占空比喚醒將導致鄰居發現延遲隨時間的改變而改變，即在不同時刻兩個鄰居節點間的發現延遲是時變的[2,3]。

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

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

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

1 系統模型

1.1 網絡模型

假設網絡中有N個同構的傳感器節點，傳感器節點分為兩種類型：簇首和簇成員節點。每個節點都有兩種狀態：活躍和休眠狀態。當一個節點處于活躍狀態時，它可以感知周圍的環境、接收和發送數據包。當一個節點處于休眠狀態時，會把除了用于喚醒的計時器之外的所有功能模塊全部關閉[9]。一個節點只有在處于喚醒狀態時才能接收數據包。所有節點之間不需要時間同步，同時具有一定的數據緩存能力。

網絡規模足夠大，而且密度較高，區域沒有邊界效應；除sink節點外所有節點均同構；節點具有位置感知模塊，能夠感知自身的相對位置信息；數據突發性較強，數據流量不高，發生碰撞概率不大；數據包長度較小，因而忽略傳播時延和處理時延。

1.2 Grid Quorum機制

本文選擇文獻[10]中提出的基于質數網格的Quorum能量節省模型，Quorum分為兩種：A-Quorum和S-Quorum。假定網絡中所有節點會根據網絡的擁塞情況、通信量和時延要求等自適應地選擇不同的Quorum類型，以此來實現非對稱性。

2 最優延遲可靠路由算法

在異步低占空比無線傳感器網絡中，兩個節點間的鄰居發現延遲是隨時間改變而改變的。本文采用文獻[13]中的方法計算動態的鄰居發現延遲。最優延遲可靠路由算法ORDA分為三個過程：鄰居發現、計算重疊時隙和成功轉發預期值。

2.1 鄰居發現

假定網格不采用時間同步，根據網絡模型可知，簇首節點之間、簇首節點與成員節點必須保證能夠鄰居發現，而成員節點之間則不必相互發現。在文獻[12]中已經證明在質數Quorum中任意兩個節點無論是分別采用A-Quorum和S-Quorum，還是均采用S-Quorum，在有限個時隙內一定能夠完成鄰居發現，如圖1所示[11]。

圖1 鄰居發現示意圖

(1)

(2)

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

2.2 計算重疊時隙

在本文中，網絡中的節點根據網絡負載自適應選擇Quorum類型。當節點檢測到網絡負載較大，超過預先設置的一個閾值時，表示節點目前的通信量較大，因此采用S-Quorum選擇喚醒工作時隙；否則節點采用A-Quorum選擇喚醒工作時隙。

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

節點A與節點B1、B2的重疊時隙個數計算過程如下：

圖2 節點的喚醒時隙圖

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

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

2.3 最優延遲可靠路由選擇

本文提出的最優延遲可靠路由算法中，算法包含兩部分，分別為鄰居發現時延和成功轉發預期值。當發送節點在有數據需要發送時，首先計算在該時刻所有鄰居節點中比發送節點等級更低的節點作為候選轉發節點，根據喚醒的先后和在一個周期內成功轉發預期值來選擇出最終轉發節點。

2.3.1 在一個周期內能夠成功轉發的預期值

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

(3)

則節點A在一個周期內能夠成功轉發的期望延遲為EA,B：

(4)

根據以上公式可以看出，兩個節點間的成功轉發預期值既考慮到了兩個節點間的重疊時隙個數，即兩個節點間能夠轉發數據的時隙數，又考慮到了兩個節點間的鏈路質量。因而對于網絡鏈路質量低的網絡，能夠在降低傳輸延遲的同時選擇更可靠的節點作為中繼節點。

舉例說明：

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

因此節點A在一個周期內成功向節點B2發送數據的成功轉發的期望為EA,B2：

2.3.2 最優延遲可靠路由選擇

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

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

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

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

最優延遲可靠路由選擇過程：

根據鄰居節點喚醒時隙集NWi中候選轉發節點與發送節點ni的重疊時隙個數和時隙標號，利用2.3.1節中介紹的成功轉發期望來計算在一個周期內節點能夠成功轉發的期望，假設為Ei,j、Ei,a和Ei,s。成功轉發預期值E越大，表示根據兩個節點間的鏈路質量，在一個周期當中可以轉發的次數越多，能夠成功轉發的可靠性更高。

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算法對于網絡性能的提高，在本節中將對不同規模下的ORDA的性能和ExOR[5]、DESS[8]的性能進行對比分析。實驗參數如表1所示。每個節點隨機地產生數據包。實驗采用文獻[14]中的無線損耗模型。在實驗中，端到端延遲是指數據包從源節點發送到匯聚節點接收之間的時延。實驗對比了不同參數下的算法性能，如不同的區域大小、節點密度和網絡鏈路質量。仿真結果為每個實驗在相同的參數下重復運行10遍。

表1 實驗參數

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

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

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

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

無線網絡的鏈路質量往往不穩定，因此對比了算法ORDA、ExOR和DESS在不同的網絡鏈路質量下的時延性能，如圖5所示。明顯可知，算法ORDA在平均鏈路質量較低的網絡中仍能保持遠優于算法ExOR和DESS的端到端延遲。這是由于算法ORDA在選擇中繼節點時根據鏈路質量和重疊時隙個數計算出一個周期內兩個節點能夠成功轉發的預期值，一直選擇預期值最大的作為中繼，因而在鏈路質量低的網絡中能夠提高轉發成功率，減少延遲。當網絡的鏈路質量超過0.9后，此時網絡中的單跳轉發成功率很高，因而基于最優鏈路的算法DESS更優。

圖5 不同網絡鏈路質量下的平均端到端延遲

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

圖6 網絡中不同節點數量下的網絡生存時間

4 結 語

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

[1] 孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京:清華大學出版社,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] 段軼,吳小兵，陳貴海.低占空比無線傳感器網絡中的動態數據傳輸協議[J].計算機研究與發展,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].計算機應用,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] 王俊美.低占空比無線傳感器網絡異步鄰居發現算法研究[J].數字通信,2013,40(2):36-39.

[10] 陳良銀,顏秉姝,張靖宇,等.移動低占空比傳感網鄰居發現算法[J].軟件學報,2014,25(6):1352-1368.

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

[12] 劉微姍,陳曉江，段任，等.DRAD:一種基于異步休眠調度的無線傳感器網絡數據收集協議[J].計算機工程與科學,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] 王辛果,張信明,陳國良.時延受限切能量高效的無線傳感網絡跨曾路由[J].軟件學報,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。國家自然科學基金項目(51174263)；教育部博士點基金項目(20124116120004);省部級項目(142300410144)。張長森，教授，主研領域：礦井監控與通信，無線傳感器網絡。胡宇鵬，碩士生。陳鵬鵬，碩士生。

TP393

A

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