黃俊杰

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

0 引言

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

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

1 基于能量與節(jié)點(diǎn)緩沖區(qū)的機(jī)會(huì)路由的實(shí)現(xiàn)

1.1 GeOR 思想的工作過程

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

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

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

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

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

1.2 EBOR 協(xié)議

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

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

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

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

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

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

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

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

2 仿真設(shè)計(jì)

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

表1 實(shí)驗(yàn)參數(shù)Tab.1 Exp erimental parameters

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

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

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

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

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

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

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

圖3 吞吐量對(duì)比Fig.3 Diffe rent in Throughput

3 結(jié)論

本文針對(duì)現(xiàn)有機(jī)會(huì)路由方案中存在的問題，本文提出了一種能夠同時(shí)針對(duì)節(jié)點(diǎn)能量與節(jié)點(diǎn)緩沖區(qū)進(jìn)行感知的動(dòng)態(tài)路由方案 EBOR，仿真結(jié)果表明，相比GeOR路由方案，EBOR能顯著延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間，提高網(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ú)線多跳網(wǎng)絡(luò)中的機(jī)會(huì)路由[J]. 軟件學(xué)報(bào), 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ú)線傳感器網(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é)報(bào), 2015, 36(5): 1177-1185.

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