廉 政，鄭加石

(上海理工大學 光電信息與計算機工程學院，上海 200093)

基于節(jié)點緩沖區(qū)與能量的機會路由設計

廉 政，鄭加石

(上海理工大學 光電信息與計算機工程學院，上海 200093)

傳統(tǒng)的機會路由在設計路由測度時僅考慮候選節(jié)點外部鏈路因素，而忽略了節(jié)點自身因素對網絡性能的影響。針對此問題，文中提出了一種基于節(jié)點緩沖區(qū)與能量的機會路由協議。該協議在地理位置策略的基礎上，綜合考慮節(jié)點緩沖區(qū)和能量因素設計新的路由測度，并根據該路由測度設計下一跳轉發(fā)節(jié)點的選取方法和每一跳的數據轉發(fā)過程。仿真結果表明，與EAOR協議相比，BEAOR協議可以獲得更高的網絡吞吐量以及更低的端到端時延，能更好的適應無線傳感網絡。

機會路由；路由協議；吞吐量；端到端時延

機會路由(Buffer-Energy Aware Opportunistic Routing，BEAOR)是近年來研究熱點，雖然研究已取得一定成果，但依然面臨問題與不足[1-2]。目前，候選轉發(fā)節(jié)點集主要是基于不同路由測度進行選擇，主要的路由測度包括基于端到端最短路徑[3]、迭代方式[4]、網絡編碼[5]以及基于地理位置策略(Geographic Random Forwarding，GeRaF)[6-7]等。基于端到端最短路徑的路由測度，考慮了節(jié)點到目的節(jié)點的最短轉發(fā)次數，但是無線信道的時變性會造成數據不按最短路徑進行轉發(fā)；基于迭代方式和網絡編碼的路由測度會進行大量的計算，當網絡中轉發(fā)節(jié)點數增加時，大量的計算量遠超過傳感器節(jié)點數據處理能力；基于地理位置策略的路由測度，僅考慮當前節(jié)點到目的節(jié)點地理位置距離，距離越小，優(yōu)先級越高，該模型簡單易實現，但對于無線傳感器網絡僅考慮節(jié)點地理位置因素過于片面，不具代表性。以上路由測度僅考慮候選轉發(fā)節(jié)點的外部鏈路信息狀態(tài)，較少考慮節(jié)點自身的相關因素，比如節(jié)點能量、節(jié)點緩沖區(qū)中因數據包過多造成的延遲等因素。

1 基于GeRaF思想的網絡工作流程

GeRaF是一種主要考慮節(jié)點地理位置的路由協議[6-7]，該協議需要感知節(jié)點在網絡中的地理位置信息，并將節(jié)點之間的地理位置距離作為路由測度進行候選轉發(fā)節(jié)點集的選擇，同時將距離大小作為確定該鄰居節(jié)點在候選轉發(fā)節(jié)點集中的優(yōu)先級高低的判別因素。

在候選轉發(fā)節(jié)點集中，依據GeRaF的思想，距離目的節(jié)點越近的候選轉發(fā)節(jié)點，優(yōu)先級越高[8]。在節(jié)點間的消息交互中，所有鄰居節(jié)點在收到發(fā)送節(jié)點的RTS控制包后，都會產生定時TBackoff，在TBackoff定時結束后回復CTS。因此使用TBackoff的大小來反映鄰居節(jié)點的優(yōu)先級高低。文獻[9]設計的路由測度公式為

(1)

其中，Ds,d是源節(jié)點s到目的節(jié)點d的距離；Dn,d是當前節(jié)點n到目的節(jié)點d的距離；SIFS為幀間間隔；C是與距離有關的常量。

由式(1)可得，TBackoff與Ds,d和Dn,d的差值成反比。其中，Ds,d在網絡拓撲結構設定后為固定值， 則TBackoff只與當前節(jié)點到目的節(jié)點的距離Dn,d有關。若節(jié)點的TBackoff在候選轉發(fā)節(jié)點集中最小，則該節(jié)點被選定為下一跳轉發(fā)節(jié)點。

因此，基于節(jié)點地理位置信息的機會路由協議中，與目的節(jié)點距離越小的候選轉發(fā)節(jié)點，越可能被選為下一跳轉發(fā)節(jié)點。每一跳的轉發(fā)節(jié)點都是動態(tài)選出，避免了無線鏈路不穩(wěn)定的影響。但是，GeRaF協議僅考慮了節(jié)點的地理位置因素，沒有考慮其他因素的影響，路由測度過于簡單。

2 路由測度的影響因素分析

2.1 節(jié)點的能量因素

無線傳感器網絡中，對于傳感器節(jié)點的電池更換和充電較難實現[10-11]。在實際的鏈路數據轉發(fā)過程中，如果節(jié)點耗能過多，則有可能在無線傳感器網絡中消失。因此，在研究路由測度時，為了保證整個網絡節(jié)點能量均勻分布，避免某一個或某一片網絡區(qū)域內的節(jié)點失效，需要考慮節(jié)點能耗對路由測度的影響[12]。

文獻[13]在路由測度中引入了節(jié)點能量因素，據此提出了基于節(jié)點能量的機會路由協議(EAOR)。在該協議中，鄰居節(jié)點收到發(fā)送節(jié)點的RTS數據包后，會在定時TEn_aware結束后回復CTS數據包,其公式為

(2)

式中，Consenergy為該鄰居節(jié)點所消耗的能量；C1為與距離相關的常量；C2為與能量相關的常量。

與基于地理位置信息的路由協議比較，EAOR協議考慮了每一個鄰居節(jié)點的能量。在該協議中，與目的節(jié)點d的距離不是最小的鄰居節(jié)點若具有很高的節(jié)點能量，則有可能成為下一跳轉發(fā)節(jié)點；反之，若節(jié)點能量很低，即使與目的節(jié)點距離最小也不會成為下一跳轉發(fā)節(jié)點。EAOR協議考慮了能量和節(jié)點位置信息，在基于地理位置的機會路由基礎上，進一步提高了網絡的性能，同時也使網絡節(jié)點能量分布更加均勻。

2.2 節(jié)點緩沖區(qū)因素

在實際的無線傳感器網絡中，節(jié)點時刻都在傳輸數據包，部分節(jié)點的緩沖區(qū)內會積壓大量數據包等待轉發(fā)，在信道繁忙的情況下，這些積壓在節(jié)點緩沖區(qū)中的數據包會產生大量的等待時間，進而影響到網絡的吞吐量和延時響[14]。為了減少數據轉發(fā)延時，在候選轉發(fā)節(jié)點集的選擇中，可以降低積壓數據包較多的節(jié)點優(yōu)先級，而提高只有較少數據包轉發(fā)的節(jié)點優(yōu)先級。

為更加直觀的分析節(jié)點緩沖區(qū)對網絡性能的影響，在100個節(jié)點的網絡環(huán)境中，測試源節(jié)點向目的節(jié)點分別發(fā)送50、100、150、200、250個數據包所需的仿真時間。

圖1 發(fā)送不同數目的數據包所需的仿真時間

從圖1可知，相同實驗條件下，發(fā)送相同數目的數據包時，候選轉發(fā)節(jié)點選擇機制中考慮節(jié)點緩沖區(qū)因素的仿真時間較少。這是因為考慮節(jié)點緩沖區(qū)因素可以充分利用網絡中閑置的節(jié)點資源，避免因緩沖區(qū)內數據包積壓而產生延時。因此，節(jié)點緩沖區(qū)對網絡性能有較大影響，在路由測度的設計中需要加以考慮。

3 BEAOR協議設計

3.1 BEAOR的路由測度

在機會路由中，需要有路由測度來決定候選轉發(fā)節(jié)點集的選取，路由測度設置的好壞決定了候選轉發(fā)節(jié)點集的優(yōu)劣，進而直接影響數據轉發(fā)路徑。本文的BEAOR協議中，基于地理位置策略，綜合考慮節(jié)點緩沖區(qū)和能量因素，設計了一種新的路由測度。

根據式(2)，BEAOR協議的路由測度可表示為

(3)

其中，Numbuffer是節(jié)點緩沖區(qū)目前所存儲的數據包個數；C3是與距離相關的常量；C4是與能量相關的常量；C5是與個數相關的常量。

從式(3)中可知，考慮節(jié)點緩沖區(qū)時，需設計一種數據包計數方法，實時統(tǒng)計鄰居節(jié)點緩沖區(qū)中的數據包個數Numbuffer。設計節(jié)點轉發(fā)和接收數據包的計數方法如圖2和圖3所示。

圖2 節(jié)點轉發(fā)數據包

圖3 節(jié)點接收數據包

3.2 BEAOR協議

本文中BEAOR協議在EAOR協議的基礎上，結合節(jié)點地理位置、能量以及緩沖區(qū)中數據包個數等因素的影響，利用新的路由測度，設計了下一跳轉發(fā)節(jié)點的選取方法以及每一跳的數據轉發(fā)流程。

在BEAOR協議中，下一跳數據轉發(fā)節(jié)點的選擇如圖4所示，需要先根據節(jié)點地理位置確定候選轉發(fā)節(jié)點集，再根據TBEAOR路由測度值確定候選轉發(fā)節(jié)點集中所有節(jié)點的優(yōu)先級，然后選擇優(yōu)先級最高的節(jié)點作為數據轉發(fā)節(jié)點。候選轉發(fā)節(jié)點TBEAOR值越小，則該節(jié)點的地理位置、能量以及節(jié)點緩沖區(qū)因素在候選轉發(fā)節(jié)點集中綜合最優(yōu)，即優(yōu)先級別最高。

完成數據轉發(fā)節(jié)點的選擇后，需進行數據轉發(fā)，BEAOR協議的數據轉發(fā)流程，如圖5所示。高優(yōu)先級的轉發(fā)節(jié)點在TBEAOR定時結束后，向源節(jié)點回復CTS。源節(jié)點在收到第一個CTS控制包后，會選擇該候選轉發(fā)節(jié)點作為下一跳的轉發(fā)節(jié)點，并將DATA數據包發(fā)送給它，同時停止接收其他候選節(jié)點回復的CTS。其他候選轉發(fā)節(jié)點在聽到數據發(fā)送后會停止CTS的回復，等待下一次數據的轉發(fā)。若源節(jié)點在一定時間內沒有收到任何鄰居節(jié)點回復的CTS，發(fā)送節(jié)點則重新發(fā)送RTS。轉發(fā)節(jié)點在收到源節(jié)點的DATA數據包后，會立即給源節(jié)點回復ACK控制包，源節(jié)點收到ACK控制包后，這一跳的數據轉發(fā)結束。如果在一定時間內，源節(jié)點沒有收到轉發(fā)節(jié)點回復的ACK控制包，則會重新向轉發(fā)節(jié)點發(fā)送DATA數據包。

圖5 BEAOR協議中數據轉發(fā)流程

BEAOR協議綜合考慮了節(jié)點地理位置、節(jié)點能量以及緩沖區(qū)中數據包個數等因素的影響，與基于節(jié)點能量的機會路由協議EAOR相比[13]，更加適合實際的無線傳感器網絡環(huán)境，同時降低了節(jié)點緩沖區(qū)因素產生的網絡延時，可以進一步提高網絡吞吐量。

4 仿真實驗

本文使用OMNeT++仿真平臺對提出的BEAOR 協議與基于能量的機會路由協議EAOR 進行比較分析，分別在單信道和多信道網絡中比較網絡吞吐量、延遲以及節(jié)點資源利用情況。

為減小隨機誤差，本實驗采用5組隨機數對應產生5種隨機分布的節(jié)點數場景，其中發(fā)送方(源節(jié)點)和接收方(目的節(jié)點)位置固定，仿真配置參數如表1所示。實驗結果取5種隨機分布的節(jié)點數場景結果的期望值。

表1 仿真參數

網絡吞吐量是衡量網絡性能的重要指標，圖6和圖7分別是對BEAOR協議以及EAOR協議在單信道和多信道中的網絡吞吐量對比。由圖中可知，隨著網絡規(guī)模的增大，單信道和多信道中的網絡吞吐量都隨之提高，且機會路由協議BEAOR的網絡吞吐量明顯優(yōu)于EAOR協議的。單信道網絡中隨著節(jié)點數目的增多，優(yōu)勢更為明顯，這是因為網絡規(guī)模的增大，使得節(jié)點緩沖區(qū)中的數據包延遲問題更為嚴重，對網絡吞吐量的影響更大。在多信道網絡中，由于節(jié)點可以在多條信道上同時轉發(fā)數據包，網絡吞吐量比單信道提高約60%。但當網絡節(jié)點數增加到250個時，BEAOR協議帶來的網絡吞吐量與EAOR協議帶來的網絡吞吐量相差不多，這是因為在多信道網絡中，節(jié)點數目的增加提升了網絡復雜度，數據碰撞的程度比單信道網絡中的碰撞更為劇烈，對網絡吞吐量的影響已經不能忽視。

圖6 單信道中網絡吞吐量比較

圖7 多信道中網絡吞吐量比較

圖8 單信道中平均端到端延遲比較

圖9 多信道中平均端到端延遲比較

端到端時延是指數據包從發(fā)送方(源節(jié)點)發(fā)出到接收方(目的節(jié)點)收到所經歷時長[15]，反應無線網絡數據包傳輸速率。從圖8和圖9所示，網絡節(jié)點越密集，平均端到端時延越小。同時，相同節(jié)點數目下使用BEAOR協議的網絡平均端到端時延小于EAOR協議，這是因為BEAOR協議考慮了節(jié)點緩沖區(qū)內數據包個數對端到端時延的影響，在下一跳轉發(fā)節(jié)點的選擇中，在候選節(jié)點其他因素相同的情況下，選擇緩沖區(qū)內數據包個數較少的節(jié)點作為下一跳的中繼節(jié)點，避免了數據包擁堵產生的時延。對比圖8和圖9所示，相同節(jié)點數目下，多信道網絡中的平均端到端時延明顯小于單信道網絡的時延，這是因為多信道網絡可提供更多的網絡資源，將信道分配應用到BEAOR協議中也是下一步的研究工作。

圖10 單信道中發(fā)送數據包個數標準差比較

圖10和圖11分別是單信道和多信道下節(jié)點發(fā)送數據包個數標準差的比較。如圖所示，單信道網絡中BEAOR協議的節(jié)點發(fā)送數據包個數標準差比EAOR小，即BEAOR協議充分利用了網絡中的節(jié)點資源，選擇緩沖區(qū)數據包個數較少的節(jié)點進行轉發(fā)數據，分散了數據包轉發(fā)任務，避免使用固定的節(jié)點轉發(fā)數據，從而使得網絡中節(jié)點的使用更加均衡。而多信道下使用BEAOR協議的節(jié)點發(fā)送數據包個數標準差雖比使用EAOR協議的要低，但是差距不如單信道情況下明顯，這是因為多信道的使用進一步增加了網絡復雜度，對網絡資源的調度需要考慮更為合理的分配機制。

5 結束語

本文提出了一種新的無線傳感器網絡機會路由協議BEAOR?；贕eRaF思想，綜合考慮節(jié)點能量和節(jié)點緩沖區(qū)因素，給出了BEAOR的路由測度公式模型、轉發(fā)節(jié)點的選擇方法及數據轉發(fā)流程。實驗表明， BEAOR協議在單信道和多信道中對網絡性能的提升和網絡資源利用都優(yōu)于傳統(tǒng)的EAOR協議。

[1] Hsu C J, Liu H I, Seah W K G. Opportunistic routing - A review and the challeng- es ahead[J].Computer Networks,2011, 55(15):3592-3603.

[2] Patel T,Kamboj P.Opportunistic routing in wireless sensor networks:A review[C].MI,USA:Advance Computing Conference,IEEE, 2015.

[3] Biswas S,Morris R.Opportunistic routing in multihop wireless networks[J].ACM Sigcomm Computer Communication Review,2005,34(1):69-74.

[4] Dubois-Ferriere H, Grossglauser M.Least-cost opportunistic routing[J].EPFL, 2007(6):33-39.

[5] Chachulski S,Jennings M,Katti S,et al. Trading structure for randomness in wire- less opportunistic routing[J].ACM Sigcomm Computer Communication Review, 2007,37(4):169-180.

[6] Zorzi M,Rao R R.Geographic random forwarding (GeRaF) for ad hoc and sensor networks: energy and latency performance[J].IEEE Transactions on Mobile Computing,2003,2(4):349-365.

[7] Zori B M,Rao R.Geographic random forwarding (Geraf) for Ad hoc ad sensor networks: multihop performance[C].UT, USA: IEEE Transactions on Mobile Computing, 2003.

[8] Casari P, Marcucci A, Nati M, et al. A detailed simulation study of geographic random forwarding (GeRaF) in wireless sensor networks[C].France:Military Communications Conference, 2005.

[9] Spachos P,Song L,Hatzinakos D.Performance comparison of opportunistic routing schemes in wireless sensor networks[C].Hangzhou:Communication Networks and Services Research Conference,IEEE,2011.

[10] Heo J,Hong J,Cho Y.EARQ:energy aware routing for realtime and reliable communication in wireless industrial sensor networks[J].IEEE Transactions on Industrial Informatics,2009,5(1):3-11.

[11] 劉睿瓊,齊小剛,孫正海.基于節(jié)點位置的無線傳感器網絡分簇路由協議[J].電子科技,2013,26(3):130-133.

[12] 史雨雨,郁進明,李雪.基于能量和密度的WSNs動態(tài)分區(qū)成簇路由算法[J].電子科技,2016,29(6):47-50.

[13] Spachos P,Chatzimisios P,Hatzinakos D. Energy aware opportunistic routing in wireless sensor networks[C].HK:Globecom Workshops,2012.

[14] 孫國棟,廖明宏,邱碩.無線傳感器網絡中一種避免節(jié)點擁塞的算法[J].計算機研究與發(fā)展,2009, 46(6):934-939.

[15] 徐晶,楊宗凱,趙三謙.多信道多跳無線網絡端到端時延最小化路由評價指標的研究[J].小型微型計算機系統(tǒng),2012,33(8):1660-1664.

The Design of Opportunistic Routing Based on Buffer and Energy of the Relays

LIAN Zheng，ZHENG Jiashi

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

The traditional opportunistic routing considers only the external link factors of the candidate node while designing the routing metric, while ignoring the influence of the node’s own factors on the network performance. To solve this problem, this paper proposes an opportunistic routing protocol BEAOR considering node buffer and energy. Based on the GeRaF, this protocol takes into account the node buffer and the energy to design a new routing metric, and according to the metric, the selection method of next hop forwarding node and the data forwarding process of each hop are designed. The experimental results demonstrated that the proposed protocol can obtain higher network throughput and lower end-to-end delay compared to EAOR, and it can better adapt to the wireless sensor network.

opportunistic routing;routing protocol;throughput;end-to-end delay

2017- 02- 23

上海市經信委科研立項(155511107700)

廉政(1990-)，男，碩士研究生。研究方向：認知無線電網絡等。鄭加石(1990-)，男，碩士研究生。研究方向：計算機技術等。

10.16180/j.cnki.issn1007-7820.2017.12.026

TN915.03；TP393

A

1007-7820(2017)12-096-06