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

黃俊杰

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

0 引言

無線傳感器網(wǎng)絡(luò)作為一種新型的信息獲取系統(tǒng)，因為具有自組織性、靈活性和低成本等特點，可以被廣泛應(yīng)用到軍事領(lǐng)域、環(huán)境科學(xué)、醫(yī)療健康等各個方面，是近年來研究的熱點[1-3]。機會路由一經(jīng)提出便備受關(guān)注，它利用了無線傳輸?shù)膹V播特性，在提升無線傳感網(wǎng)性能上具有良好的應(yīng)用前景[4]。2005年 Sanjit Biswas等人提出了極限機會路由（extremely opportunistic routing，ExOR）[5]，ExOR的源節(jié)點首先廣播信息報，協(xié)議選擇一個節(jié)點子集接受信息包，節(jié)點中距離目的節(jié)點最近的節(jié)點再次廣播信息包，循環(huán)該過程直到目的節(jié)點接收到信息包，ExOR基于路由測度ETX（excepted transmission count metric）計算當(dāng)前節(jié)點和目的節(jié)點的距離，綜合考慮跳數(shù)和重傳次數(shù)等因素，極大程度的提高了數(shù)據(jù)包的成功轉(zhuǎn)發(fā)率。Michele等提出了GeOR（geographic random forwarding）協(xié)議[6]，該協(xié)議基于節(jié)點地理位置來選擇轉(zhuǎn)發(fā)節(jié)點，節(jié)約了用于維護全網(wǎng)拓?fù)浜吐酚杀硭鶐淼膮f(xié)議開銷，并進行了跨層設(shè)計，同時通過復(fù)雜的候選轉(zhuǎn)發(fā)節(jié)點間的控制包應(yīng)答協(xié)調(diào)機制，使得節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)時的沖突減少，進一步減小了節(jié)點的能量消耗，從而延長了網(wǎng)絡(luò)的生存時間。GeOR協(xié)議基于地理位置策略，認(rèn)定中繼節(jié)點與目的節(jié)點的距離越小優(yōu)先級越高，該協(xié)議僅僅考慮了地理位置因素，所以簡單易實現(xiàn)[7]。在無線傳感網(wǎng)絡(luò)中，僅僅考慮地理位置信息太過于簡單。在實際網(wǎng)絡(luò)環(huán)境中，傳感器依靠可充電電池供電，電池存儲的能量有限[8]，一旦電池的能量耗盡或是電壓低于電池電壓的保護閾值，會導(dǎo)致電池使用壽命縮短，嚴(yán)重會導(dǎo)致電池失效，所以節(jié)點的能量因素必須考慮在內(nèi)[9]。除此之外，在網(wǎng)絡(luò)繁忙的情況下，會出現(xiàn)某個節(jié)點因為優(yōu)先級過高需要轉(zhuǎn)發(fā)大量數(shù)據(jù)包，而導(dǎo)致數(shù)據(jù)包排隊等待的情況。這種情況會產(chǎn)生大量的端對端的延遲，從而降低網(wǎng)絡(luò)的吞吐量，這也是需要解決的重要問題。

針對上述問題本文對傳統(tǒng)路由算法做出了改進，提出了一種能夠改善網(wǎng)絡(luò)中節(jié)點能量的均衡性，提高網(wǎng)絡(luò)吞吐量、降低端到端時延的機會路由協(xié)議（EBOR：Energy and Buffer Opportunistic Routing）。EBOR采用了能量結(jié)合節(jié)點緩沖區(qū)的度量方法，不但可以延長網(wǎng)絡(luò)生命周期，而且可以明顯改善網(wǎng)絡(luò)吞吐量。

1 基于能量與節(jié)點緩沖區(qū)的機會路由的實現(xiàn)

1.1 GeOR 思想的工作過程

GeOR（geographic random forwarding）是一種基于節(jié)點地理位置的路由協(xié)議，各節(jié)點可以獲知自身的地理位置信息。根據(jù)地理位置確定轉(zhuǎn)發(fā)節(jié)點和優(yōu)先級 。

在GeOR網(wǎng)絡(luò)工作過程中，節(jié)點會以這4 種控制包類型進行通信：RTS（Request To Send）[10], CTS（Clear To Send）[11]，DATA 以及 ACK（acknowledge）[12]。數(shù)據(jù)包發(fā)送之前，發(fā)送節(jié)點首先發(fā)送 RTS,候選節(jié)點在收到RTS之后，會等待一個 Tbackoff時間。Tbackoff公式如下：

上式中， Di,dst是源節(jié)點到目的節(jié)點的距離，Dk,dst是當(dāng)前節(jié)點到目的節(jié)點的距離，SIFS為幀間間隔，是一個和距離有關(guān)的常量。

Tbackoff時間過后，候選節(jié)點回復(fù) CTS給發(fā)送節(jié)點，發(fā)送節(jié)點收到高優(yōu)先級的鄰居節(jié)點回復(fù)的CTS后，會直接將DATA發(fā)送給該鄰居節(jié)點，不再接受其他鄰居節(jié)點回復(fù)的CTS 數(shù)據(jù)包，即第一個回復(fù)CTS的鄰居節(jié)點被選為下一跳轉(zhuǎn)發(fā)節(jié)點。

由（1）可知，候選節(jié)點的優(yōu)先級與 Tbackoff成反比，即 Tbackoff數(shù)值越低，節(jié)點優(yōu)先級越高。

1.2 EBOR 協(xié)議

在實際網(wǎng)絡(luò)環(huán)境中，傳感器依靠可充電電池供電，電池存儲的能量有限，一旦某個節(jié)點能量耗盡，從網(wǎng)絡(luò)中退出，會導(dǎo)致整個網(wǎng)絡(luò)的性能下降。此外，如果可充電電池能量耗盡或者是電壓低于電池的保護電壓，會導(dǎo)致電池的壽命縮短，更可能導(dǎo)致電池的性能下降[13]。因此，研究者考慮能量因素對路由測度的影響，保證整個網(wǎng)絡(luò)節(jié)點能量的均勻分布，并且避免因能量耗盡，對電池壽命、性能產(chǎn)生的負(fù)面影響。研究者提出了參數(shù)thE ，當(dāng)節(jié)點能量等級小于thE ，將會降低該節(jié)點的優(yōu)先級，從而該節(jié)點參與發(fā)送數(shù)據(jù)包的幾率大大減少。此舉不僅保證了網(wǎng)絡(luò)中能量的均勻分布又讓電池受到了保護。除此之外，在網(wǎng)絡(luò)繁忙的情況下，會出現(xiàn)某個節(jié)點因為優(yōu)先級過高需要轉(zhuǎn)發(fā)大量數(shù)據(jù)包，而導(dǎo)致數(shù)據(jù)包排隊等待發(fā)送的情況。這種情況會產(chǎn)生大量的端對端的延遲，從而降低網(wǎng)絡(luò)的吞吐量，為了解決這個問題，可以對數(shù)據(jù)包過多的節(jié)點降低其優(yōu)先級，并對數(shù)據(jù)包較少的節(jié)點提高其優(yōu)先級，從而避免因某節(jié)點待轉(zhuǎn)發(fā)數(shù)據(jù)包過多，而導(dǎo)致的網(wǎng)絡(luò)吞吐量降低。

基于節(jié)點地理位置策略，綜合考慮節(jié)點能量和節(jié)點緩沖區(qū)，EBOR的路由測度可表示為：

上式中，1C是電池容量有關(guān)的常量；thE 是電池閾值；resE 是節(jié)點中的剩余能量百分比；BL是緩沖區(qū)優(yōu)先級，其計算公式如下：

BUFNUM是候選節(jié)點緩沖區(qū)中實際存儲的數(shù)據(jù)包個數(shù)；B U FSIZE是候選節(jié)點緩沖區(qū)中能夠存儲的最大數(shù)據(jù)包個數(shù)；d是計算所得發(fā)送節(jié)點到接收節(jié)點的距離；A是發(fā)射端與接收端相隔一米時的信號強度；SIFS 為幀間間隔；RSSI為接收信號強度[14]，可以用來計算發(fā)送節(jié)點與接收節(jié)點的距離，其計算公式如下：

其中，n是環(huán)境衰減因子。

圖1展示了 Tbackoff在不同能量優(yōu)先級下的取值。

由GeOR思想的工作過程可知，所有候選轉(zhuǎn)發(fā)節(jié)點集中的節(jié)點優(yōu)先級由 Tbackoff路由測度確定，然后選擇優(yōu)先級最高的節(jié)點作為數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點。根據(jù)公式（2）， Tbackoff值越小的候選節(jié)點，則表示該節(jié)點的地理位置、能量因素以及節(jié)點緩沖區(qū)因素在候選轉(zhuǎn)發(fā)節(jié)點集中綜合最優(yōu)，即優(yōu)先級別最高。優(yōu)先級最高的節(jié)點在 Tbackoff時間結(jié)束后，需要向發(fā)送節(jié)點回復(fù) CTS。發(fā)送節(jié)點在收到第一個 CTS 數(shù)據(jù)包后，會選擇該候選轉(zhuǎn)發(fā)節(jié)點作為下一跳的轉(zhuǎn)發(fā)節(jié)點，并將DATA 數(shù)據(jù)包發(fā)送給它，同時停止接收其他候選節(jié)點回復(fù)的CTS。其他候選轉(zhuǎn)發(fā)節(jié)點在聽到數(shù)據(jù)發(fā)送后會停止 CTS 的回復(fù)，等待下一次數(shù)據(jù)的轉(zhuǎn)發(fā)。如果源節(jié)點在一定時間內(nèi)沒有收到任何鄰居節(jié)點回復(fù)的CTS，發(fā)送節(jié)點則重新發(fā)送RTS。轉(zhuǎn)發(fā)節(jié)點在收到源節(jié)點的DATA 數(shù)據(jù)包后，會立即給發(fā)送節(jié)點回復(fù) ACK 控制包，發(fā)送節(jié)點收到 ACK 控制包后，這一跳的數(shù)據(jù)轉(zhuǎn)發(fā)結(jié)束。如果在一定時間內(nèi)，發(fā)送節(jié)點沒有收到轉(zhuǎn)發(fā)節(jié)點回復(fù)的ACK控制包，則會重新向轉(zhuǎn)發(fā)節(jié)點發(fā)送DATA 數(shù)據(jù)包。

在EBOR協(xié)議中，綜合考慮了節(jié)點地理位置、節(jié)點能量以及緩沖區(qū)中數(shù)據(jù)包個數(shù)等因素的影響，與GeOR機會路由相比，更加符合實際的無線傳感器網(wǎng)絡(luò)環(huán)境，可以進一步提高網(wǎng)絡(luò)的吞吐量，降低端到端延遲。

2 仿真設(shè)計

本實驗使用 OMNET++仿真平臺[15]，將本文提出的EBOR與GeOR協(xié)議進行比較分析。具體參數(shù)如表所示。

表1 實驗參數(shù)Tab.1 Exp erimental parameters

本實驗設(shè)置節(jié)點的電池容量為1000 mAh，節(jié)點隨機分布，每個節(jié)點的廣播范圍為12 m，源節(jié)點與目的節(jié)點之間的距離固定。

2.1 網(wǎng)絡(luò)生命周期（Network lifetime）

根據(jù)應(yīng)用場景的不同，對網(wǎng)絡(luò)生命周期的定義有很多種。在本文中，網(wǎng)絡(luò)生命周期被定義為從網(wǎng)絡(luò)開始直至首個節(jié)點無法繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)包的時間，也就是源節(jié)點和目的節(jié)點之間沒有連通路徑。兩個協(xié)議的網(wǎng)絡(luò)存活時間如圖2所示。

EBOR相比 GeOR，顯著的提升了網(wǎng)絡(luò)的存活時間。GeOR在源節(jié)點與目的節(jié)點確定的情況下，傾向于選擇相同的路徑，所以這條路徑上的節(jié)點將承擔(dān)傳輸任務(wù)，導(dǎo)致該路徑上的節(jié)點能量消耗過多直至耗盡，而EBOR綜合考慮節(jié)點的能量和節(jié)點數(shù)據(jù)包緩存?zhèn)€數(shù)，使傳輸任務(wù)由候選節(jié)點分?jǐn)偅沟镁W(wǎng)絡(luò)中的能量分布更加均勻，不會出現(xiàn)某幾個節(jié)點能量消耗過快導(dǎo)致該節(jié)點從網(wǎng)絡(luò)中退出的情況。因此，EBOR協(xié)議的網(wǎng)絡(luò)生命周期要明顯優(yōu)于GeOR協(xié)議。

圖2 網(wǎng)絡(luò)生存時間對比Fig.2 Different in NetWork Lifetime

2.2 網(wǎng)絡(luò)吞吐量

從圖 3可以看出：本文設(shè)計的機會路由協(xié)議EBOR比GeOR路由協(xié)議的網(wǎng)絡(luò)吞吐量有較大的提高。原因在于相較于GeOR協(xié)議，EBOR協(xié)議考慮到了網(wǎng)絡(luò)繁忙情況下，網(wǎng)絡(luò)節(jié)點緩沖區(qū)出現(xiàn)的數(shù)據(jù)包排隊等候，導(dǎo)致端到端延遲高的情況。EBOR綜合考慮節(jié)點緩沖區(qū)因素和能量因素的影響，降低了端到端的延遲，從而提高了網(wǎng)絡(luò)整體吞吐量。

圖3 吞吐量對比Fig.3 Diffe rent in Throughput

3 結(jié)論

本文針對現(xiàn)有機會路由方案中存在的問題，本文提出了一種能夠同時針對節(jié)點能量與節(jié)點緩沖區(qū)進行感知的動態(tài)路由方案 EBOR，仿真結(jié)果表明，相比GeOR路由方案，EBOR能顯著延長網(wǎng)絡(luò)生存時間，提高網(wǎng)絡(luò)吞吐量。

[1] AKYILDIZ IF, SU WL, SANKARASUBRAMANIAM Y. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 44(8): 102-114.

[2] CHEE-YEE CHONG, KUMAR SP. Sensor networks: evolution,opportunities, and challenges[J]. Proceedings of IEEE, 2003,91(8): 1247-1256.

[3] AL-KARAKI JN, KAMAL AE. Routing techniques in wireless sensor networks: a survey[J]. IEEE Wireless Communications, 2004, 11(6): 6-28.

[4] DHURANDHER SK, SHARMA DK, WOUNGANG I,CHAO H. Performance evaluation of various routing protocols in opportunistic networks[C]. IEEE Globecom Workshops, 2011: 1067-1071

[5] SANJIT BISWAS, ROBERT MORRIS. Opportunistic routing in multi-hop wireless networks[C]. ACM SIGCOMM Computer Communication Review, 2004, 34(1): 69-74.

[6] MICHELE Z, RAMESH RR. Geographic random forwarding(geraf) for ad hoc and sensor networks: Energy and latency performance[C]. IEEE Transactions on Mobile Computing,2003, 2(4): 349-365.

[7] 田克, 張寶賢, 馬建, 姚鄭. 無線多跳網(wǎng)絡(luò)中的機會路由[J]. 軟件學(xué)報, 2010, 21(10): 2542-2553.TIAN K, ZHANG B X, MA J, et al. Opportunistic Rounting Protocols for Wireless Multihop Networks[J]. Journal of Software, 2010, 21(10): 2542-2553. (in chinese)

[8] SUN YANJING, HE YANJUN, ZHANG BEIBEI, et al. An energy efficiency clustering routing protocol for WSNs in confined area[J]. Mining Science and Technology, 2011,21(6): 845-850.

[9] 朱娜. 能源有效的無線傳感器網(wǎng)絡(luò)協(xié)議[D]. 大連理工大學(xué), 2006.ZHU N. Energy Efficient Protocol for Wireless Sensor Networks[D]. Dalian University of Technology, 2006.

[10] Lampin Q, Barthel D, Auge-Blum I, et al. QoS oriented Opportunistic Routing protocol for Wireless Sensor Networks[C]// Wireless Days, Ifip. IEEE, 2012:1-6.

[11] Younis M, Youssef M, Arisha K. Energy-aware routing in cluster-based sensor networks[C]//2012 IEEE 20th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. IEEE Computer Society, 2002:0129.

[12] Yuan Y, Yang H, Wong S H Y, et al. ROMER: resilient opportunistic mesh routing for wireless mesh networks[J]. in The 1st IEEE Workshop on Wireless Mesh Networks (WiMesh,2005.

[13] SPACHOS P, CHATZIMISIOS P, HATZINAKOS D. Energy aware opportunistic routing in wireless sensor networks[C].IEEE Globecom Workshops, 2012: 405-409.

[14] 鄭學(xué)理, 付敬奇. 基于PDR 和RSSI 的室內(nèi)定位算法研究[J]. 儀器儀表學(xué)報, 2015, 36(5): 1177-1185.

[15] OMNET++[EB/OL]. http://www.omnetpp.org.