基于能量與節點緩沖區的機會路由研究

黃俊杰

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

0 引言

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

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

1 基于能量與節點緩沖區的機會路由的實現

1.1 GeOR 思想的工作過程

GeOR（geographic random forwarding）是一種基于節點地理位置的路由協議，各節點可以獲知自身的地理位置信息。根據地理位置確定轉發節點和優先級 。

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

上式中， Di,dst是源節點到目的節點的距離，Dk,dst是當前節點到目的節點的距離，SIFS為幀間間隔，是一個和距離有關的常量。

Tbackoff時間過后，候選節點回復 CTS給發送節點，發送節點收到高優先級的鄰居節點回復的CTS后，會直接將DATA發送給該鄰居節點，不再接受其他鄰居節點回復的CTS 數據包，即第一個回復CTS的鄰居節點被選為下一跳轉發節點。

由（1）可知，候選節點的優先級與 Tbackoff成反比，即 Tbackoff數值越低，節點優先級越高。

1.2 EBOR 協議

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

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

上式中，1C是電池容量有關的常量；thE 是電池閾值；resE 是節點中的剩余能量百分比；BL是緩沖區優先級，其計算公式如下：

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

其中，n是環境衰減因子。

圖1展示了 Tbackoff在不同能量優先級下的取值。

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

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

2 仿真設計

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

表1 實驗參數Tab.1 Exp erimental parameters

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

2.1 網絡生命周期（Network lifetime）

根據應用場景的不同，對網絡生命周期的定義有很多種。在本文中，網絡生命周期被定義為從網絡開始直至首個節點無法繼續轉發數據包的時間，也就是源節點和目的節點之間沒有連通路徑。兩個協議的網絡存活時間如圖2所示。

EBOR相比 GeOR，顯著的提升了網絡的存活時間。GeOR在源節點與目的節點確定的情況下，傾向于選擇相同的路徑，所以這條路徑上的節點將承擔傳輸任務，導致該路徑上的節點能量消耗過多直至耗盡，而EBOR綜合考慮節點的能量和節點數據包緩存個數，使傳輸任務由候選節點分攤，使得網絡中的能量分布更加均勻，不會出現某幾個節點能量消耗過快導致該節點從網絡中退出的情況。因此，EBOR協議的網絡生命周期要明顯優于GeOR協議。

圖2 網絡生存時間對比Fig.2 Different in NetWork Lifetime

2.2 網絡吞吐量

從圖 3可以看出：本文設計的機會路由協議EBOR比GeOR路由協議的網絡吞吐量有較大的提高。原因在于相較于GeOR協議，EBOR協議考慮到了網絡繁忙情況下，網絡節點緩沖區出現的數據包排隊等候，導致端到端延遲高的情況。EBOR綜合考慮節點緩沖區因素和能量因素的影響，降低了端到端的延遲，從而提高了網絡整體吞吐量。

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

3 結論

本文針對現有機會路由方案中存在的問題，本文提出了一種能夠同時針對節點能量與節點緩沖區進行感知的動態路由方案 EBOR，仿真結果表明，相比GeOR路由方案，EBOR能顯著延長網絡生存時間，提高網絡吞吐量。

[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] 田克, 張寶賢, 馬建, 姚鄭. 無線多跳網絡中的機會路由[J]. 軟件學報, 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] 朱娜. 能源有效的無線傳感器網絡協議[D]. 大連理工大學, 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] 鄭學理, 付敬奇. 基于PDR 和RSSI 的室內定位算法研究[J]. 儀器儀表學報, 2015, 36(5): 1177-1185.

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