基于能量与节点缓冲区的机会路由研究

黄俊杰

（上海理工大学光电信息与计算机工程学院，上海 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.