一种基于转发区域的三维地理位置路由协议

陈聪 冀肖榆 农健

摘 要： 在真实的无线传感网络（WSNs）应用环境中，传感节点位于三维空间。为此，提出基于锥形转发区域的三维地理位置路由协议。为了减少冗余数据包数、降低数据包碰撞概率，CFRG协议先建立锥形转发区域，其目的在于限制转发节点数。然后，再估计锥形转发区域内节点的转发概率，最终选择具有最大转发概率的节点转发数据包。当节点遭遇空洞节点问题，就自适应地调整锥形转发区域体积，扩大选择转发节点的空间，即通过锥形转发区域调整，解决VNP问题。仿真结果表明，提出的CFRG协议能够处理VNP问题。与同类的三维路由协议相比，CFRG协议能够提升端到端传输时延和数据包丢失率两方面性能。

关键词： 无线传感网络; 地理位置路由; 三维路由协议; 锥形转发区域; 空洞节点问题; 传输时延

中图分类号： TN915.04?34; TP393 文献标识码： A 文章编号： 1004?373X（2018）09?0035?06

Abstract： In the actual application environment of wireless sensor networks （WSNs）， the sensor nodes are located in three?dimensional space. Therefore， the conical forwarding region?based 3D geographical （CFRG） routing protocol is proposed. In order to decrease the redundant data packets and reduce the collision probability of data packets， the conical forwarding region is constructed for the restriction of the forwarding node numbers. The forwarding probabilities of the nodes in the conical forwarding region are estimated to select the node forwarding data packet with the maximum forwarding probability. When the node experiences a void node problem （VNP）， the volume of the conical forwarding region is adjusted adaptively for enlarging the space of forwarding node selection to solve the VNP. The simulation results show that the proposed protocol can resolve the VNP， and reduce the end?to?end transmission delay and data packet loss ratio in comparison with the similar 3D routing protocols.

Keywords： wireless sensor network; geographical routing; three?dimensional routing protocol; conical forwarding region; void node problem; transmission delay

0 引 言

随着传感技术的迅速发展，无线传感网络（Wireless Sensor Networks，WSNs）得到广泛应用[1?3]。通过部署WSNs传感节点先收集环境数据，再传输至基站，最后通过Internet网络将数据传输至后台管理人员，进而实现实时监控环境的目的。这些应用均要求实时、可靠地传输数据包[4]。地理位置路由（Geographical Routing Protocols，GRPs）无需维护路由和发现路由阶段，因此，相比于拓扑路由协议，GRPs能够提供可靠、实时的数据包传输服务[5?6]。

在真实的WSNs环境中，传感节点部署于三维（3D）空间，如海洋监测[7?8]、森林火灾感测[9]。针对这些应用，GRPs必须利用三维位置坐标。而二维的GRPs只是利用平面路由技术选择路由，与真实的三维空间不符。文献[10?12]的实验结果表明，三维GRPs能够提高数据包傳递的可靠性。

此外，GRPs的关键在于给节点提供位置信息。而利用GPS系统能够获取节点的三维信息[13]。GRPs的另一个问题在于空洞节点问题（Void Node Problem，VNP）。所谓VNP就是在发送节点方向上没有转发节点。二维GRPs通常采用平面路由技术处理VNP问题，然而，这些技术不能应用于三维GRPs中。

为此，本文提出基于锥形转发区域的三维地理位置路由（Conical Forwarding Region?based Geographical，CFRG）协议。CFRG协议通过建立锥形转发区域控制数据包的冗余，并计算转发概率，选择最大概率的节点传输数据包。同时，CFRG路由利用实时调整锥形转发区域，使其包含更多的节点，提升选择转发节点的选择空间。实验数据表明，提出的CFRG路由协议能降低数据包传输时延和数据包丢失率，也能有效地处理VNP问题。

1 约束条件及CFRG路由概述

1.1 约束条件

假定无线传感网络内有[N]个同构节点，且随机分布于兴趣区域内。这些节点是静态的，每个节点的传输距离为[r ]m。[N]个同构节点所形成的三维体积为[V]。

此外，假定网络内所有节点均知道目的节点、源节点的位置。这些信息均载入在数据包的首部中。在多数WSN中，目的节点（基站）均部署在预定位置，因此目的节点位置可认为是已知的。

1.2 CFRG路由概述

CFRG路由目的在于提高数据传输效率，减少传输时延。CFRG路由先构建锥形转发区域，进而控制转发数据包的节点数，降低拥塞。同时，通过估算转发区域内每个节点转发数据包的概率，择优选择概率最大的节点作为转发节点，减少数据包的传输时延。

此外，CFRG路由的另一个特点在于解决了三维VNP问题，这也是GRPs的共性问题。CFRG路由通过实时调整锥形转发区域，解决VNP问题。

2 CFRG路由

2.1 锥形转发区域PFR

首先定义数据包转发区域，即锥形转发区域。该区域内节点被认为是潜在的转发节点。为了减少传输次数，锥形转发区域应尽可能地小。即希望锥形转发区域内只含有一个最理想的转发节点。从另一种角度而言，锥形转发区域应当足够大，即尽可能提高区域内包含最理想的转发节点概率。

当源节点[S]需要发送数据包时，先建立锥形转发区域。最初，为了减少传输次数，尽可能地减少锥形转发区域，使其含有足够少，但存在合适的转发节点。为此，锥形转发角[β]反比于网络密度[ρ=NV]。网络密度越大，锥形转发区域越小，反之，越大。据此，初始的锥形转发角[βinit]为：

2.2 转发节点集

当接收来自源节点或发送节点[S]发送的数据包，接收节点就需要判断自己是否在锥形转发区域内。若在区域内，就可成为候选转发节点，即纳入转发节点集[ψ]内。

假定节点[S]的位置坐标为[Sx，Sy，Sz]。节点[S]所发送的数据包的首部包含其位置坐标信息。任何节点（假定为节点[ni]）接收了该数据包，节点[ni]就确认自己是否在锥形转发区域内。

假定节点[ni]和目的节点[D]的位置坐标分别为[nx，ny，nz，][Dx，Dy，Dz]。先计算两个矢量[SD→]与[Sn→]的夹角[θ]：

式中[β]为锥形转发角。如果满足，则说明该节点在锥形转发区域内，并纳入候选转发集[ψ]（[ψ←ni]），成为潜在转发节点;否则，将该数据包纳入空洞节点数据包清单Void_node_packetlist，便于后续处理。

当然，最初所有节点均按式（3）判断是否在锥形转发区域。如果发送节点在发送数据包后，经一段时间后，节点仍没有监听到数据包被转发，说明该数据包没有被节点接收。因此，源节点或发送节点就重传该数据包，并调整转发角[β]，具体过程见2.4节。

2.3 转发概率

2.3.1 时 延

当锥形转发区域内有多个节点时，就需要计算每个节点的转发概率，主要通过时延估计计算转发概率。

先计算锥形转发区域内每个节点将数据包传输至目的节点所需要的时间，即估计传输时延[τreq。][τreq]主要取决于两个因素：转发节点[ni]和目的节点[D]间的跳数[h];每跳的时延[τh]。

对于跳数[h]可通过[SD→r]决定。而每跳的时延[τh]由多个因素决定：

2.3.2 适度性

如果节点位于锥形转发区域，并发现自己能够在数据包有效期[Tthreshold]前传递数据包，那么该节点就可成为潜在转发节点。如果锥形转发区域中有多个节点时，就进一步分析这些节点中哪个节点更适合传输数据包，即节点传输数据包的“适度性”。

可利用潜在转发节点的队列时延以及它之前传输[m]个数据包的平均传输时延[τav]估算节点的“适度性”。由源节点计算时延[τav，]如式（6）所示：

2.4 VNP处理

在GRPs路由中，节点可能遭遇路由空洞问题，这也是GRPs路由的共性问题。CFRG主要通过自适应调整转发区域体积，即调整[β]角处理VNP问题。

锥形转发区域调整机制如图2所示。若基于初始[βinit]角建立的转发区域[PFR1]内没有转發节点，就意味着遭遇VNP。因此，一旦转发节点[S]遭遇VNP，就需要重新建立锥形转发区域。转发节点[S]发送了数据包后，经时期[τω]后，若没有监测到邻居节点重传数据包，说明它（转发节点[S]）遭遇VNP问题。在这种情况下，转发节点[S]就重传数据包。此外，时间[τω]可依据文献[14]调整。

位于初始锥形转发区域外的节点，通过确认Void_node_packetlist内数据包ID号。若数据包在它的Void_node_packetlist内，就将[β]扩大1倍，即将锥形转发区域扩大，使其包含更多潜在转发节点。将这一过程称为锥形转发区域调整过程。

如图2所示，其描述了锥形转发区域调整机制。最初，源节点[S]通过[PFR1]区域转发数据包，后发现[PFR1]区域内没有转发节点;然后调整[β]形成了[PFR2]区域，再试图转发数据包，仍发现[PFR2]区域内没有转发节点，无法将数据包传递至目的节点[D]。至此，再次调整[β]形成[PFR3]区域。最后，发现[PFR3]区域内有节点[n1]，且其能够将数据包传输至目的节点。尽管节点[n1]不是通过最短路径向目的节点[D]传输数据包，但是它能够解决VNP问题。

3 数值分析

3.1 仿真场景

利用OMNeT++[15]仿真软件建立仿真平台。仿真运行时间为5 min，且每个数据包的截止时长为250 ms。具体仿真参数如表1所示。

此外，为了更好地评估CFRG协议性能，选择ABLAR和3D 贪婪（Greedy）路由作为参考。前者利用随机转发技术解决3D VNP问题，而后者是典型的GRPs策略，并利用平面路由技术解决3D VNP问题。这两者与CFRG协议存在可比性。

在分析CFRG协议性能时，选择端到端传输时延和数据包丢失率作为性能指标。每次实验独立重复10次，取平均值作为最终的仿真数据，最终的仿真数据如图4～图7所示。

3.2 CFRG协议性能

单独分析CFRG协议性能时，主要分析其端到端传输时延、数据包丢失率随锥形转发角[β]的变化情况， 且[β]从0～360°间变化，仿真结果如图4，图5所示。

图4描述了端到端传输时延随[β]的变化曲线。从图4可知，在网络密集区域，[β]越大，端到端传输时延也就越大，原因在于密集区域，一旦[β]增加，意味着更多的节点需要转发数据包，加剧网络拥塞，最终提升了端到端传输时延。

图5绘制了数据包丢失率随锥形转发角[β]的变化曲线。从图5可知，在网络负担（12 packets/s）大的环境下，锥形转发角[β]对数据包丢失率有重要的影响。原因在于网络负担越大，节点需要传输更多的数据包，这也会造成数据包传输拥塞，甚至数据包碰撞，便增加了数据包丢失率。这些数据表明，依据网络密度选择合适的[β]是非常重要的。

3.3 对比分析

本小节主要分析网络流量对端到端传输时延、数据包丢失率的影响，其中网络流量用源节点每秒产生的数据包数表征。假定网络内有1 000个节点，4个源节点，源节点每秒产生数据包数从1～14变化。

3.3.1 端到端传输时延

首先，分析端到端传输时延随网络流量变化情况，如图6所示。

从图6可知，与3D Greedy和ABLAR相比，提出的CFRG协议的端到端传输时延最低，并且随网络流量变化波动小。这主要是因为CFRG协议在决策转发数据包时，考虑了转发拥塞问题，并将时延信息融入了转发概率，这有利于降低拥塞概率。

3.3.2 数据包丢失率

数据包丢失率是反映路由协议性能的重要指标。三个协议的数据包丢失率随网络流量的变化曲线如图7所示。从图7可知，三个协议的数据包丢失率随网络流量的增加而上升。而与ABLAR协议和3D Greedy 协议相比，CFRG协议的数据包丢失率最低，特别是在低网络流量情况下，CFRG协议在数据包丢失率方面的优势特别明显。例如，在低网络流量时，即当数据包产生率不大于6 packets/s，CFRG协议的平均数据包丢失率约为8%，而3D Greedy协议、ABLAR协议分别高达32%，44%。

然而，当数据包产生率大于6 packets/s后，CFRG协议的数据包丢失率急剧增加。尽管如此，CFRG协议的数据包丢失率仍远优于ABLAR和3D Greedy协议。这主要归功于CFRG协议能够实时调整、扩大转发区域，增加了选择转发节点的空间，进而有利于处理VNP问题。

4 结 语

本文针对无线传感网络的路由问题，提出基于锥形转发区域的三维地理位置路由协议CFRG。CFRG路由充分考虑了节点位置的三维空间特性，通过网络密度构建锥形转发区域。只有锥形转发区域内的节点才能转发数据包，通过这种方式控制转发数据包的数量，降低数据包碰撞概率。一旦节点遭遇VNP问题，就调整锥形转发区域。最终，通过计算锥形转发区域内每个节点的转发概率，择优选择转发节点传输数据包。仿真结果表明，提出的CFRG路由能够有效处理VNP问题。与同类的3D地理位置路由相比，CFRG路由降低了数据包传递时延，并提高了数据包传输成功率。

参考文献

[1] YICK J， MUKHERJEE B， GHOSAL D. Wireless sensor network survey [J]. Computer networks， 2008， 52（12）： 2292?2330.

[2] AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. A survey on sensor networks [J]. IEEE communications magazine， 2002， 40（8）： 102?114.

[3] DIETRICH I， DRESSLER F. On the lifetime of wireless sensor networks [J]. ACM transactions on sensor networks， 2013， 5（1）： 34?41.

[4] GUO W， ZHANG W. A survey on intelligent routing protocols in wireless sensor networks [J]. Journal of network & computer applications， 2014， 38（1）： 185?201.

[5] CADGER F， CURRAN K， SANTOS J， et al. A survey of geographical routing in wireless Ad?Hoc networks [J]. IEEE communications surveys & tutorials， 2013， 15（2）： 621?653.

[6] ABD M A， SINGH B K， RUBEAAI S F A， et al. Game theoretic energy balanced （GTEB） routing protocol for wireless sensor networks [C]// Proceedings of 2014 IEEE Wireless Communications and Networking Conference. Istanbul： IEEE， 2014： 2564?2569.

[7] CHEN Y S， LIN Y W. Mobicast routing protocol for underwater sensor networks [J]. IEEE sensors journal， 2013， 13（2）： 737?749.

[8] AYAZ M， BAIG I， ABDULLAH A， et al. A survey on routing techniques in underwater wireless sensor networks [J]. Journal of network & computer applications， 2011， 34（6）： 1908?1927.

[9] BOUABDELLAH K， NOUREDDINE H， LARBI S. Using wireless sensor networks for reliable forest fires detection [J]. Procedia computer science， 2013， 19（2）： 794?801.

[10] KADI M， ALKHAYAT I. The effect of location errors on location based routing protocols in wireless sensor networks [J]. Egyptian informatics journal， 2015， 16（1）： 113?119.

[11] ARSLAN M G， ONEL T， ERSOY C. Effect of 3D topographical surfaces for the performance evaluation of wireless sensor networks [C]// Proceedings of IEEE the 19th International Symposium on Personal， Indoor Mobile Radio Communications. Cannes： IEEE， 2008： 1?6.

[12] POMPILI D， MELODIA T， AKYILDIZ I F. Three?dimensional and two?dimensional deployment analysis for underwater acoustic sensor networks [J]. Ad Hoc networking， 2013， 7（4）： 778?790.

[13] AMUNDSON I， KOUTSOUKOS X D. A survey on localization for mobile wireless sensor networks [C]// Proceedings of 2011 International Conference on Mobile Entity Localization and Tracking in GPS?Less Environments. Berlin， Germany： Springer?Verlag， 2011： 235?254.

[14] Information Sciences Institute. Transmission control protocol， RFC 793 [EB/OL]. [2015?10?21]. https：//tools.ietf.org/html/rfc793.

[15] OpenSim Ltd. OMNeT++ discrete event simulator [EB/OL]. [2015?10?21]. https：//omnetpp.org/.